Faculté des sciences

Eine statistische Methode zur Erkennung von Dokumentstrukturen

Brugger, Rolf ; Ingold, Rolf (Dir.)

Thèse de doctorat : Université de Fribourg : 1999 ; Nr. 1251.

Die vorliegende Dissertation behandelt die Erkennung von Dokumenten. Es werden schwerpunktmässig die Aspekte des Lernens von Dokumentmodellen und der Erkennung der logischen Struktur von Dokumenten betrachtet. Um sowohl eine hohe Zuverlässigkeit als auch Bedienungsfreundlichkeit zu erreichen, wird ein interaktives System beschrieben, das sich leicht an neue Dokumentklassen anpassen lässt. Das... Plus

Ajouter à la liste personnelle
    Summary
    This PhD thesis is on the topic of document recognition. It particularly discusses the aspects of learning document models and the recognition of the logical structure of documents. In order to achieve high reliability and user friendliness, we describe an interactive system which can easily be adapted to new document classes. In an initial learning session the system is able to generate a recognition model based on a small set of completely tagged logical documents. In the successive recognition sessions, the user interactively corrects the recognition errors of the system. In order to prevent it from repeating the same errors again, these corrections are automatically integrated to the model thanks to the system's incremental learning capabilities. The representation of the document model is based on a novel, statistical formalism. It is based on n-grams, which have been generalized to be able to represent tree structures. The basic principle consists in the representation of local patterns in tree structures using the conditional probabilities of n-grams. Such a statistical model is able to represent one document class at a time. In the discussion of the expressiveness of the statistical model, we introduce the notion of the entropy of a model. We further introduce a learning algorithm, which estimates the n-gram probabilities of the model based on a set of sample documents. The same algorithm is again used in the incremental learning steps. The recognition of the physical structure of a document is based on classical methods that have been documented in the literature. However, the logical structure tree is here constructed stepwise on top of the physical structure, using a heuristic bottom-up procedure. The optimal solution is found in an efficient way by a quality measure and a best-first search strategy. The approach has been empirically validated on three different document classes, the main test series consisting in 25 documents of an article collection with average structural complexity and containing a total of 400 pages. The tests revealed that the recognition rate of the system constantly improves with the number of recognized documents. When the end of this training and recognition phase has been reached, about one correction is necessary every four pages. Finally, possibilities of integrating the statistical n-gram model with existing standards like SGML/DSSSL are discussed. To this purpose, a method which translates a statistical model into the corresponding DTD is described.
    Zusammenfassung
    Die vorliegende Dissertation behandelt die Erkennung von Dokumenten. Es werden schwerpunktmässig die Aspekte des Lernens von Dokumentmodellen und der Erkennung der logischen Struktur von Dokumenten betrachtet. Um sowohl eine hohe Zuverlässigkeit als auch Bedienungsfreundlichkeit zu erreichen, wird ein interaktives System beschrieben, das sich leicht an neue Dokumentklassen anpassen lässt. Das System benötigt eine initiale Lernfähigkeit, indem es aus vollständigen, logischen Dokumenten ein vorläufiges Erkennungsmodell generieren kann. In darauf folgenden Erkennungsvorgängen werden allfällige Fehler interaktiv vom Benutzer korrigiert. Durch die inkrementelle Lernfähigkeit des Systems werden die Korrekturen in das Modell integriert, und so die Wiederholung desselben Fehlers verhindert. Für die Darstellung des Dokumentmodells wird ein neuartiger, statistischer Formalismus verwendet. Er basiert auf n-Grammen, die in einer Weise erweitert wurden, dass sie auch Baumstrukturen repräsentieren können. Das Grundprinzip basiert auf der Darstellung lokaler Muster in Baumstrukturen durch die bedingten Wahrscheinlichkeiten von n-Grammen. Ein derartiges statistisches Modell vermag jeweils eine Dokumentklasse vollständig zu beschreiben. In der Diskussion um die Repräsentationsfähigkeit des statistischen Modells wird der Begriff der Entropie eingeführt. Es wird ein Lernalgorithmus vorgestellt, der die n-Gramm-Wahrscheinlichkeiten aus vorgelegten Beispieldokumenten schätzt. Derselbe Algorithmus gelangt auch in inkrementellen Lernphasen zur Anwendung. Die Erkennung der physischen Struktur eines Dokuments erfolgt mit klassischen Methoden aus der einschlägigen Literatur. Auf der physischen Struktur eines zu erkennenden Dokuments wird mit einem bottom-up Verfahren der logische Strukturbaum konstruiert. Die Heuristik wählt unter Verwendung einer Bewertungsfunktion und einer best-first Suchstrategie effizient eine optimale Lösung aus. Der Ansatz wird an Dokumenten aus drei verschiedenen Klassen validiert. Die Haupttestserie besteht aus 25 Dokumenten mit insgesamt 400 Seiten einer Serie von Artikeln mittlerer Komplexität. Die Tests belegen, dass die Erkennungsleistung des Systems mit der Anzahl erkannter Dokumente zunimmt, so dass schliesslich etwa eine Korrektur pro vier Seiten nötig ist. Schliesslich werden Integrationsmöglichkeiten des statistischen n-Gramm-Modells mit bestehenden Standards wie zum Beispiel SGML/DSSSL erforscht. Es wird dazu eine Methode vorgestellt, die ein statistisches Modell in eine entsprechende DTD übersetzt.