-
Die vorliegende Erfindung betrifft Computer-basierte Textverarbeitung, und besonders
Techniken für das Part-of-Speech-Tagging durch Finite-Zustands-Transducer (FST,
finite state transducer), die von einem Hidden-Markov-Modell (HMM) abgeleitet sind.
-
Das Tagging (Etikettieren) der Wortbedeutung von Maschinen lesbarem Text, wodurch
Tags den Worten in einem Satz zugewiesen werden, um die Bedeutung eines Worts im
Satz zu identifizieren (z. B. Hauptwort-Singular, Verb-Präsenz-Erste-Person-Plural) ist
bekannt. Solche Etikette sind typisch in einer standardisierten Form, wie etwa nach der
Text Encoding initiative (TEI) spezifiziert ist. Ein Text oder ein Korpus, der einmal
etikettiert wurde, findet Verwendung z. B. bei der Informationssuche des Textes und bei
statistischen Analysen des Textes.
-
"Deterministic part-of-speech tagging with finite state transducers" von Roche E. et al.
(Computational Linguistics, Juni 1995, USA, Band 21, Nr. 2, Seiten 227-253, ISSN
0891-2017) legt Transducer offen, die einen lexikalischen Tagger, einen Tagger
unbekannter Wörter und einen Kontext-Tagger enthalten. Der Kontext-Tagger, der Tags als
Eingabe aufnimmt, und Tags als Ausgabe abgibt, wird konstruiert durch Wandlung jeder
Kontextregel in einen Finite-Zustände-Transducer; danach Wandlung der Transducer in
Transducer, die auf der Eingabe in einem Pass global arbeiten; dann Kombinntion aller
Transducer zu einem einzigen Transducer, etwa durch Komposition; und dann
Transformation der sich ergebenden Transducer in einen äquivalenten, subsequentiellen
(deterministischen) Transducer.
-
"Weighted rational transductions and their application to human language processing"
von Pereira F. et al. (Human language technology, workshop proceedings, 1. Januar
1994, Seiten 262-267) zeigt, dass jede Transduction in einer Kaskade häufig durch
eine Finite-Zustände-Vorrichtung modelliert wird, wie etwa ein Hidden-Markov-Modell. Es
kann gezeigt werden, dass Hidden-Markov-Modelle und Wahrscheinlichkeits-orientierte
Finite-Zustände-Sprachmodelle äquivalent zu gewichteten Finite-Zustände-Aufnehmern
sind. Ein konventioneller HMM-Decodierer kann natürlich als äquivalent zu einer
Kaskade gewichteter Transductionen angesehen werden.
-
Wahrscheinlichkeits-orientierte, HMM-basierte Tagger sind von Bahl und Mercer (1976)
und Church (1988) bekannt; siehe Abschnitt H: Referenzen am Ende dieser
Offenlegungsschrift. Sie wählen aus den in einem Wörterbuch für ein Wort gefundenen
Wortbedeutungs-Etiketten das auf der Basis des Kontextes des Wortes, d. h. der
benachbarten Worte, wahrscheinlichste Etikett aus.
-
Jedoch ist ein Problem eines konventionellen, HMM-basierten Taggers, dass er nicht mit
anderen Finite-Zustände-Werkzeugen integriert werden kann, die andere Schritte der
Textanalyse/-manipulation durchführen.
-
Ein Verfahren ist es, ein FST-durchführendes Wortbedeutungs-Etikettieren (Tagging)
von einem Satz von Regeln zu erzeugen, die durch Linguistiker geschrieben wurden
(Chanod und Tapanainen, 1995). Dies beansprucht jedoch beträchtliche Zeit und
erzeugt sehr große Automaten (oder Mengen von Automaten, die aufgrund der Größe
nicht miteinander integriert werden können), die das Etikettieren ziemlich langsam
durchführen. Solch ein FST kann auch nicht-deterministisch sein, d. h. für einen
Eingabesatz kann er mehr als eine Lösung oder überhaupt keine Lösungen bieten.
-
Die vorliegende Erfindung sieht Verfahren vor, um ein für das
Wortbedeutungs-Etiketfieren (Part-of-speech tagging) verwendetes H idden-Markov-Modell (HMM) durch einen
Finite-Zustände-Transducer zu approximieren. (Ein identisches Modell eines HMM
durch einen Transducer (ohne Gewichte) ist in vielen Fällen nicht möglich) In
spezifischen Ausführungsformen wird vorgesehen: (a) ein Verfahren (n-Typ-Approximation
genannt) der Ableitung eines einfachen Finite-Zustände-Transducers, der in allen Fällen
anwendbar ist, aus HMM-Wahrscheinlichkeitsmatrizen, (b) ein Verfahren (s-Typ-
Approximation genannt) für die Bildung eines präzisen HMM-Transducers für
ausgewählte Fälle, die von einem Trainingskorpus genommen werden, (c) ein Verfahren für
die Vervollständigung des präzisen (s-Typ-)Transducers mit Sequenzen von dem
einfachen (n-Typ-)Tranducer, was den präzisen Transducer in allen Fällen anwendbar
macht, und (d) ein Verfahren (b-Typ-Approximation genannt) für die Bildung eines HMM-
Tranducers mit variabler Präzision, der in allen Fällen anwendbar ist.
-
Die Erfindung sieht ein Verfahren vor zur Erzeugung eines Text-etikettierenden FST
nach irgendeinem der Ansprüche 1,5 und 9 der angefügten Ansprüche, oder nach
irgendeiner der hier beschriebenen, besonderen Ausführungsformen.
-
Die Erfindung sieht ferner ein Verfahren vor zur Erzeugung eines zusammengesetzten
Finite-Zustände-Transducers mit einem oder mehreren Text-manipulierenden FST.
-
Die Erfindung sieht ferner ein Verfahren vor zur Etikettierung eines Textes unter
Verwendung der vorgestellten, HMM-abgeleiteten FST oder des zusammengesetzten FST.
-
Die Erfindung sieht ferner ein Textverarbeitungssystem nach Anspruch 11 der
angefügten Ansprüche vor, und ein beschreibbares Medium nach Anspruch 12 der angefügten
Ansprüche.
-
Die HMM-Transducer bauen auf den Daten (Wahrscheinlichkeitsmatrizen) des
unterlegten HMM auf. Die Genauigkeit der in dem HMM-Trainingsprozeß gesammelten Daten
hat Wirkung auf die Etikettierungsgenauigkeit sowohl des HMM selbst als auch des
abgeleiteten Transducers. Das Training dieses HMM kann sowohl auf einem Korpus ohne
Tags als auch auf einem Korpus mit Tags erfolgen, und wird nicht im Detail diskutiert, da
es in der Literatur (Bahl und Mercer, 1976; Church, 1988) beschrieben ist.
-
Ein Vorteil des Finite-Zustände-Taggers nach der Erfindung ist, dass die Tagging-
Geschwindigkeit bei der Benutzung von Tranducer bis zu fünfmal höher ist als wenn das
unterlegte HMM benutzt wird (siehe Abschnitt F unten).
-
Ein Hauptvorteil der Erfindung ist jedoch, dass die Integration mit Werkzeugen, die
weitere Schritte der Textanalyse durchführen, möglich ist: die Transformation eines HMM in
einen FST bedeutet, dass dieser Transducer mit dem Finite-Zustände-Calculus
behandelt werden kann, und deshalb direkt in andere
Finite-Zustände-Textverarbeitungswerkzeuge integriert werden kann, wie sie von XEROX Corp. und anderen Stellen verfügbar
sind. Da der Tagger in der Mitte einer Kette von Textanalysewerkzeugen ist, von denen
alle anderen Werkzeuge Finite-Zustände-basiert sein können (wie dies der Fall ist bei
den von XEROX Corp. verfügbaren Textverarbeitungswerkzeugen), macht die
Konvertierung des HMM in einen FST diese Kette homogen, und ermöglicht so, dass die
Kettenkomponenten mittels Komposition in einen einzigen FST zusammengebracht
werden.
-
Insbesondere ist es möglich, einen HMM-abgeleiteten Transducer unter anderem mit
einem oder mehreren der folgenden Transducer zusammenzulegen, die codieren:
-
- Korrekturregeln für die häufigsten Tagging-Fehler, um die Tagging-Genauigkeit
signifikant zu verbessern. Diese Regeln können entweder automatisch von einem Korpus
extrahiert werden (Brill, 1992), oder manuell geschrieben werden (Chanod und
Tapanamen, 1995). Die Regeln können Abhängigkeiten über große Abstände enthalten,
die von HMM-Taggern gewöhnlich nicht gehandhabt werden.
-
- weitere Schritte der Textanalyse, z. B. leichtes Parsen oder Herausziehen von
Hauptwort-Phrasen oder anderen Phrasen (Ait-Mokhtar und Chanod, 1997).
-
- Kriterien, die über die Relevanz eines Korpus hinsichtlich einer besonderen Suchfrage
bei der Informationsaufsuche entscheiden (z. B. Vorkommen von bestimmten Worten
in bestimmten syntaktischen Strukturen).
-
Diese Transducer können getrennt oder alle zusammen aufgebaut sein (Kaplan und
Kay, 1994). Solche Komposition ermöglicht komplexe, von einem einzigen Transducer
durchgeführte Textanalyse (siehe EP-A-583,083).
-
Es ist zu erkennen, dass die hier beschriebenen Algorithmen Verwendung finden
können über die Anwendungen hinaus, die mit Blick auf die besonderen, unten angeführten
Ausführungsformen diskutiert werden: d. h. bei jeder Art von Analyse geschriebener oder
gesprochener Sprache auf der Basis sowohl von Finite-Zustände-Technologie als auch
HMM, wie etwa Korpusanalyse, Spracherkennung, u. s. w. Die Algorithmen sind
vollständig verwirklicht worden.
-
Nun werden Ausführungsformen der Erfindung beispielhaft beschrieben, mit Bezug auf
die begleitenden Zeichnungen, in denen:
-
Fig. 1 Entscheidungen über Tags mit einem n-Typ-Tranducer nach einer
Ausführungsform der Erfindung veranschaulicht;
-
Fig. 2 schematisch die Erzeugung eines n-Typ-Transducers nach einer
Ausführungsform der Erfindung veranschaulicht;
-
Fig. 3 die Prozedur der Bildung eines n-Typ-Transducers nach einer Ausführungsform
der Erfindung veranschaulicht;
-
Fig. 4 ein Diagramm ist, das die Klassen-Untersequenzen eines Satzes
veranschaulicht;
-
Fig. 5 ein schematisches Diagramm der Schritte in der Prozedur für die Bildung eines
s-Typ-Transducers nach einer alternativen Ausführungsform der Erfindung ist;
-
Fig. 6 ein Diagramm ist, das die Auflösung von Mehrdeutigkeiten von Klassen
zwischen zwei ausgewählten Tags veranschaulicht;
-
Fig. 7 ein Diagramm ist, das die gültigen Pfade durch den Raum der Tags eines
Satzes veranschaulicht;
-
Fig. 8 ein Diagramm ist, das b-Typ-Sequenzen veranschaulicht;
-
Fig. 9 ein schematisches Flußdiagramm ist, das die Prozedur der Bildung eines b-
Typ-Transducers veranschaulicht;
-
Fig. 10 ein Veranschaulichung des Tagging eines Satzes unter Verwendung entweder
des in Fig. 3 gebildeten n-Typ-Transducers oder des in Fig. 5 gebildeten s-Typ-
Transducers oder des in Fig. 9 gebildeten b-Typ-Transducers ist; und
-
Fig. 11 ein schematisches Flußdiagramm der Schritte ist, die nach einer
Ausführungsform der Erfindung in der Prozedur enthalten sind, in welcher das Tagging eines
Textkorpus mit einem Finite-Zustände-Tagger unter Benutzung eines HMM-
Transducers durchgeführt wird.
A. Systemkonfiguration
-
Es ist zu würdigen, dass die Techniken nach der Erfindung unter Verwendung
konventioneller Computer-Technik genutzt werden können. Es ist zu würdigen, dass die
Erfindung verwirklicht werden kann unter Verwendung eines mit WindowsTM arbeitenden PC,
eines mit MacOS arbeitendne Mac oder eines mit UNIX arbeitenden Minicomputers,
was in der Technik wohlbekannt ist. Z. B. wird die PC-Hardware-Konfiguration im Detail
diskutiert in The Art of Electronics, 2. Ausgabe, Kapitel 10, P. Horowitz und W. Hill,
Cambridge Universita Press, 1989. Die Erfindung wurde auf einer Sun Sparc20
Workstation, die mit UNIX arbeitet, in C verwirklicht.
B. FST-Ableitung
-
Die Erfindung wird mit Bezug auf drei Verfahren zur Ableitung eines Transducers für das
Part-of-speech-Tagging von einem HMM beschrieben. Diese Verfahren und Transducer
werden hier mit n-Typ, s-Typ und b-Typ bezeichnet.
-
Ein für Tagging verwendetes HMM codiert wie ein Transducer eine Beziehung zwischen
zwei Sprachen. Eine Sprache enthält Sätze von Mehrdeutigkeitsklassen, die durch
Nachschlagen aller Wörter eines Satzes in einem Lexikon ermittelt werden. Die andere
Sprache enthält Sequenzen von Tags, die durch statistisches Beseitigen der
Mehrdeutigkeiten der Klassensequenzen ermittelt werden. Von außen betrachtet verhält sich ein
HMM-Tagger wie ein sequentieller Transducer, der deterministisch jede Sequenz von
Mehrdeutigkeitsklassen (die mit einem Satz korrespondieren) auf eine eindeutige
Sequenz von Tags abbildet, z. B.:
C. Transducer vom n-Typ
-
Dieser Abschnitt stellt ein Verfahren vor, das ein Hidden-Markov-Modell (HMM) erster
Ordnung durch einen Finite-Zustände-Transducer (FST) approximiert, was als eine n-
Typ-Approximation bezeichnet wird. Fig. 1 veranschaulicht die Entscheidungen über
Tags mit einem n-Typ-transducer nach einer Ausführungsform der Erfindung.
-
Wie in einem HMM erster Ordnung berücksichtigen wir Anfangswahrscheinlichkeiten π,
Übergangswahrscheinlichkeiten a und Klassen-(d. h.
Beobachtungssymbol-)Wahrscheinlichkeiten b. Jedoch werden Wahrscheinlichkeiten über Pfade nicht abgeschätzt.
Anders als in einem HMM beeinflußt eine einmal getroffene Entscheidung die folgenden
Entscheidungen, ist aber selbst nicht umkehrbar.
-
Fig. 1 veranschaulicht dieses Verhalten mit einem Beispiel: für die Klasse c&sub1; des Wortes
w&sub1; wird das Tag t&sub1;&sub2; ausgewählt, welches das wahrscheinlichste Tag in einer
Anfangsposition ist. Für das Wort w&sub2; wird das Tag t&sub2;&sub2; ausgewählt, das wahrscheinlichste Tag bei
gegebener Klasse c&sub2; und zuvor ausgewähltem Tag t&sub1;&sub2;, u. s. w.
-
Ein Transducer, der dieses Verhalten codiert, kann erzeugt werden, wie in Fig. 2
veranschaulicht: diese Zeichnung zeigt schematisch einen n-Typ-Transducer nach einer
Ausführungsform der Erfindung. In diesem Beispiel gibt es eine Menge von drei Klassen, c,
mit den zwei Tags t&sub1;&sub1; und t&sub1;&sub2;, c&sub2; mit den drei Tags t&sub2;&sub1;, t&sub2;&sub2; und t&sub2;&sub3; und c&sub3; mit einem Tag t&sub3;&sub1;.
Unterschiedliche Klassen können dasselbe Tag enthalten, z. B. können t&sub1;&sub2; und t&sub2;&sub3; sich
auf dasselbe Tag (z. B. [NOUN]) beziehen. Fig. 3 veranschaulicht die Prozedur der
Bildung eines n-Typ-Transducers nach einer Ausführungsform der Erfindung.
-
Beginnend mit der Menge der Tags und der Menge der Klassen (allgemein mit 2
bezeichnet) wird für jedes mögliche Paar einer Klasse und eines Tags (z. B. c&sub1; : t&sub1;&sub2; oder
[ADJ,NOUN] : NOUN) ein eindeutiger Zustand erzeugt (Schritt s1) und mit diesem selben
Paar bezeichnet. Diese Menge von Zuständen wird es ermöglichen, jede Klasse auf
jedes ihrer Tags abzubilden. Ein Anfangszustand, der nicht mit irgendeinem Paar
korrespondiert, wird ebenfalls in Schritt s1 erzeugt. Alle Zustände sind Endzustände und werden
mit Doppelkreisen markiert. Dies produziert eine Menge von Zuständen, die mit
Klasse-Tag-Paaren bezeichnet sind, und einen Anfangszustand (allgemein mit 4
bezeichnet).
-
Für jeden Zustand werden so viele abgehende Bögen erzeugt (Schritt s2), wie es
Klassen gibt (drei in Fig. 2). Jeder solcher Bogen für eine bestimmte Klasse zeigt auf das
wahcscheinlichste Paar dieser selben Klasse. Die Menge der abgehenden Bögen eines
Zustands ermöglicht es, über das folgende Tag zu entscheiden, basierend auf der
folgenden Klasse und dem Tag des gegenwärtigen Zustands. Falls der Bogen von dem
Anfangszustand kommt, wird das wahrscheinlichste Paar einer Klasse und eines Tags
(Zielzustand) nach der Anfangs- und Klassenwahrscheinlichkeit des Tags abgeschätzt.
-
arg p&sub1;(ci,tik) = π(tik)·b(ci tik)
-
Falls der Bogen von einem Zustand anders als der Anfangszustand kommt, wird das
wahrscheinlichste Paar durch die Übergangs- und Klassenwahrscheinlichkeit des Tag
geschätzt:
-
arg p&sub2;(ci,tik) = α(tik tvoriges)·b(ci tik)
-
In dem Beispiel (Fig. 2) ist c&sub1; : t&sub1;&sub2; das wahrscheinlichste Paar von Klasse c&sub1;, und c&sub2; : t&sub2;&sub3;
das wahrscheinlichste Paar der Klasse c&sub2;, wenn von dem Anfangszustand ausgegangen
wird, und c&sub2; : t&sub2;&sub1; ist das wahrscheinlichste Paar der Klasse c&sub2;, wenn vom Zustand C&sub3; : t&sub3;&sub1;
ausgegangen wird. Jeder Bogen ist mit demselben Zeichenpaar bezeichnet wie sein
Zielzustand, mit dem Klassenzeichen in der oberen Sprache und dem Tag-Zeichen in
der unteren Sprache. Z. B. ist jeder Bogen, der zu dem Zustand c&sub1; : t&sub1;&sub2; führt, mit c&sub1; : t&sub1;&sub2;
bezeichnet. Das Ergebnis ist der nicht minimale und nicht deterministische FST 6.
-
Schließlich können alle Zustandsbezeichnungen entfernt werden, da das oben
beschriebene Verhalten in den Bogenbezeichnungen und der Netzwerkstruktur codiert ist. Das
Netzwerk kann minimiert und eindeutig gemacht werden (Schritt s3), um den n-Typ-FST
8 zu produzieren.
-
Das obige mathematische Modell wird als ein n1-Typ-Modell bezeichnet, der
resultierende Finite-Zustände-Transducer als ein n9-Typ-Transducer und der gesamte
Algorithmus, der von dem HMM zu diesem Transducer führt, als eine n1-Typ-Approximation
eines HMM erster Ordnung.
-
Angepaßt auf ein HMM zweiter Ordnung würde dieser Algorithmus eine
n2-Typ-Approximation abgeben.
-
Jeder n-Typ-Transducer ist sequentiell, d. h. deterministisch auf der Eingabeseite. In
jedem Zustand gibt es für jedes Klassenzeichen genau einen abgehenden Bogen. Ein n-
Typ-Transducer erzeugt für irgendeinen Korpus die Tags deterministisch.
D. Transducer vom s-Typ
-
Dieser Abschnitt stellt ein Verfahren nach einer anderen Ausführungsform der Erfindung
vor, das ein Hidden-Markov-Modell (HMM) erster Ordnung durch einen Finite-Zustände-
Transducer (FST) approximiert, und das hier als s-Typ-Approximation bezeichnet wird.
D.1 Mathematischer Hintergrund
-
Um einen Satz zu etikettieren (mit Tag versehen), d. h. seine Klassen-Sequenz auf die
wahrscheinlichste Tag-Seguenz abzubilden, kann die Klassensequenz bei den nicht
mehrdeutigen Klassen (die nur ein Tag enthalten) in Untersequenzen aufgeteilt werden,
diese getrennt mit Tag versehen werden und dann wieder verkettet werden. Dieses
Ergebnis ist äquivalent zu dem, das ermittelt wird, wenn der Satz als Ganzes mit Tag
versehen wird.
-
Fig. 4 ist ein Diagramm, das die Klassen-Untersequenzen eines Satzes veranschaulicht.
Zwei Typen von Untersequenzen von Klassen werden unterschieden: anfängliche und
mittlere. Die abschließende (finale) Untersequenz eines Satzes ist äquivalent zu einer
mittleren Untersequenz, falls angenommen wird, dass das Schlußzeichen des Satzes
(".", "!" oder "?") immer mit einer nicht mehrdeutigen Klasse cu korrespondiert.
-
Eine anfängliche Untersequenz ci beginnt mit der Anfangsposition des Satzes, hat
irgendeine Anzahl (einschließlich null) von mehrdeutigen Klassen und endet mit der
ersten nicht mehrdeutigen Klasse cu des Satzes. Sie kann durch den regulären Ausdruck
beschrieben werden:
-
ci = ca * cu
-
Es sei eine anfängliche Klassen-Untersequenz ci der Länge r gegeben. Dann kann die
vereinte Wahrscheinlichkeit zusammen mit der korrespondierenden anfänglichen Tag-
Untersequenz Ti geschätzt werden zu:
-
p(Ci,Ti) = π(t&sub1;)·b(c&sub1; t&sub1;)·[ aj(tj tj-1)·b(cj tj)]·a(tr tr-1)
-
Eine mittlere Untersequenz cm beginnt unmittelbar nach einer nicht mehrdeutigen
Klasse cm, hat irgendeine Anzahl (einschließlich null) von mehrdeutigen Klassen und endet
mit der ersten nicht mehrdeutigen Klasse ca des Satzes. Sie kann durch den regulären
Ausdruck beschrieben werden:
-
cm = ca * cu
-
Um die Wahrscheinlichkeit der mittleren Tag-Sequenzen Tm korrekt abzuschätzen,
haben wir die unmittelbar vorangehende, nicht mehrdeutige Klasse cue einzubeziehen, die
aktuell zu der vorangehenden Untersequenz ci oder cm gehört. So wird eine erweiterte
mittlere Untersequenz ermittelt:
-
cme = cue ca * cu
-
Die vereinigte Wahrscheinlichkeit einer erweiterten, mittleren Klassen-Untersequenz cme
der Länge s zusammen mit einer korrespondierenden Tag-Untersequenz Tme kann
abgeschätzt werden durch:
D.2 Bildung eines Transducer vom s-Typ
-
Um einen s-Typ-Transducer zu bilden, wird eine große Anzahl anfänglicher Klassen-
Sequenzen ci und erweiterter, mittlerer Klassen-Sequenzen cme erzeugt, wie in D.3
unten beschrieben, und jede von ihnen wird auf der Basis eines HMM erster Ordnung
unter Verwendung des Viterbi-Algorithmus für Effizienz (Viterbi, 1967; Rabiner 1990)
eindeutig gemacht (d. h. mit Tag versehen).
-
Jede Klassen-Untersequenz wird mittels einer Kreuz-Produkt-Operation mit ihrer
wahrscheinlichsten Tag-Untersequenz verbunden:
-
Si = Ci·x·Ti = c&sub1; : t&sub1; c&sub2; : t&sub2; ... cn : tn
-
Sme = Cme·x·Tme = c1e : t1e c&sub2; : t&sub2; ... cn : tn
-
Dann werden die Vereinigung uSi aller anfänglichen Untersequenzen Si und die
Vereinigung uSme aller erweiterten, mittleren Untersequenzen Sme gebildet.
-
In allen erweiterten, mittleren Untersequenzen Sme, wie z. B.
-
werden das erste Klassenzeichen auf der oberen Seite und das erste Tag-Zeichen auf
der unteren Seite als eine Erweiterung markiert, die nicht wirklich zu der mittleren
Sequenz gehört, aber notwendig ist, um sie korrekt eindeutig zu machen. Das obige
Beispiel wird zu:
-
Nun ist es möglich, ein vorläufiges Satzmodell zu formulieren, das eine anfängliche
Untersequenz gefolgt von einer Anzahl (einschließlich null) erweiterter, mittlerer
Untersequenzen enthält:
-
uS0 = uSi uSm0*
-
wo alle mittleren Untersequenzen Sm0 noch in dem Sinn markiert und erweitert werden,
dass jedes Vorkommen aller nicht mehrdeutigen Klassen zweimal angeführt wird:
einmal am Ende eines jeden Satzes (nicht markiert) und auch am Beginn eines jeden
folgenden Satzes (markiert).
-
Um eine korrekte Verkettung der anfänglichen und mittleren Untersequenzen zu sichern,
wird eine Verkettungsbeschränkung für Klassen formuliert:
-
Rc = [~ $[\cu c ]]j
-
die aussagt; dass jede mittlere Untersequenz mit derselben markierten, nicht
mehrdeutigen Klasse cu0 beginnen muß (d. h. 0.[DET]), die nicht markiert als cu (d. h. [DET]) am
Ende der vorangehenden Untersequenz vorkommt, da beide Zeichen auf dasselbe
Vorkommen dieser nicht mehrdeutigen Klassen verweisen.
-
Nach Sichestellung einer korrekten Verkettung durch Kornposition der vorläufigen
Satzmodelle uS0 mit der Verkettungsbeschränkung Rc werden alle markierten Klassen auf
der oberen Seite und alle markierten Tags auf der unteren Seite der Beziehung entfernt.
-
Das obige mathematische Modell wird als s-Typ-Modell bezeichnet, der
korrespondierende Finite-Zustände-Transducer als s-Typ-Transducer und der gesamte Algorithmus,
der von dem HMM zu dem Transducer führt, als s-Typ-Approximation eines HMM.
-
Ein s-Typ-Transducer versieht jeden Korpus, der nicht unbekannte Untersequenzen
enthält, auf genau dieselbe Weise, d. h. mit denselben Fehlern, mit Tags wie es der
korrespondierende HMM-Tagger macht. Ein s-Typ-Transducer ist jedoch unvollständig, weil er
nur eine begrenzte Menge von Untersequenzen von Mehrdeutigkeitsklassen codiert.
Deshalb kann ein s-Typ-Transducer keine Sätze mit einer oder mehrerer
Untersequenzen mit Tags versehen, welche nicht in dieser Menge sind. Ein s-Typ-Transducer kann
vervollständigt werden, wie unten in D.4 beschrieben wird.
D.3 Erzeugung von Mehrdeutigkeitsklassen-Untersequenzen
-
Dieser Abschnitt beschreibt drei Wege, um Klassen-Untersequenzen zu ermitteln, die
für die Bildung eines s-Typ-Transducers benötigt werden. Fig. 5 ist ein schematisches
Diagramm der Schritte in der Prozedur der Bildung eines s-Typ-Transducers nach einer
alternativen Ausführungsform der Erfindung.
(a) Herausziehen aus einem Korpus
-
Auf der Basis eines Lexikons und eines Schätzers wird ein Trainingskorpus (10) ohne
Tags auf genau dieselbe Weise mit Klassenetikette versehen, wie es später zum Zweck
der Ausweisung von Tags geschehen wird.
-
Aus jedem Satz wird (Schritt 4) die anfängliche Klassen-Untersequenz Ci
herausgezogen, die mit der ersten nicht mehrdeutigen Klasse cu endet, und alle erweiterten,
mittleren Untersequenzen Cm0, die von einer nicht mehrdeutigen Klasse cu in dem Satz bis zu
der folgenden nicht mehrdeutigen Klasse reichen. Dies erzeugt die unvollständige
Menge der Klassen-Untersequenzen (s-Typ), wie mit 12 bezeichnet.
(b) Erzeugung aller möglichen Untersequenzen
-
Hier wird die Menge der Tags und die Menge der Klassen (allgemein mit 2 bezeichnet)
als Startpunkt verwendet. Die Menge aller Klassen s wird in die Untermenge von nicht
mehrdeutigen Klassen cu und die Untermenge von mehrdeutigen Klassen ca aufgeteilt.
-
Dann werden alle möglichen anfänglichen und erweiterten mittleren
Klassen-Untersequenzen Ci und Cme bis zu einer definierten Länge erzeugt (Schritt s5).
-
Wie in D.3(a) wird eine unvollständige Menge von Klassen-Sequenzen (s-Typ) 12
ermittelt, und das HMM kann verwendet werden (Schritt s7), um daraus eine unvollständige
Menge von Klassen- und Tag-Sequenzen (s-Typ) 14 zu ermitteln. Diese Menge 14 kann
mit dem Finite-Zustände-Calculus verwendet werden, um einen s-Typ-Transducer 16 zu
bilden (Schritt s8); und dieser unvollständige s-Typ-Transducer wiederum wird benutzt,
um die unvollständige Menge 14 durch Herausziehen aller Klassen-Sequenzen
abzuleiten (Schritt s10).
(c) Extraktion von einem Tranducer
-
Falls ein n-Typ-Transducer N, der ein HMM approximiert, bereits verfügbar ist, können
anfängliche und erweiterte mittlere Klassen- und Tag-Untersequenzen Si und Sme unter
Verwendung des Finite-Zustände-Calculus herausgezogen werden (Schritt s6), um eine
vollständige Menge 17 von Klassen- und Tag-Sequenzen (n-Typ) zu produzieren.
D.4 Vervollständigung von dem Transducer vom s-Typ
-
s-Typ-Transducer mit Klassen-Untersequenzen, die wie oben in D.3(a) oder D.3(b)
beschrieben erzeugt wurden, sind allgemein auf der Eingabeseite nicht vollständig. Sie
akzeptieren nicht alle möglichen Mehrdeutigkeitsklassen-Sequenzen. Dies jedoch ist für
einen Transducer notwendig, der dazu verwendet wird, Klassensequenzen von
irgendeinem Korpus eindeutig zu machen, da ein neuer Korpus Sequenzen enthalten kann,
denen im Trainingskorpus nicht begegnet wurde.
-
Ein unvollständiger s-Typ-Transducer S kann vervollständigt werden mit
Untersequenzen von einem zur Hilfe verwendeten, vollständigen n-Typ-Transducer N, wie folgt:
-
Zuerst werden die Vereinigungen der anfänglichen und der erweiterten mittleren
Untersequenzen usSi und usSme aus dem primären s-Typ-Transducer S herausgezogen, und
die Vereinigungen unSi und unSme werden von dem zur Hilfe verwendeten
n-Typ-Transducer N herausgezogen, wie oben in Abschnitt D.3(c) beschrieben.
-
Dann wird eine gemeinsame Vereinigung uSi der anfänglichen Untersequenzen
gemacht:
-
uSi = uSi [[\cunSi·u - usSi·u]·o·unSi]
-
und eine gemeinsame Vereinigung uSme der erweiterten mittleren Untersequenzen:
-
uSme = uSme [[\cunSme·u - usSme·u]·o·unSme]
-
In beiden Fällen werden die Untersequenzen von dem Hauptmodell S mit allen den
Untersequenzen von dem zur Hilfe verwendeten Model N vereinigt, die nicht in S sind.
-
Schließlich wird der vollständige s + n-Typ-Transducer 18 von den gemeinsamen
Vereinigungen der Untersequenzen uSi und uSme erzeugt (Schritt s14), wie oben in Abschnitt
D.2 beschrieben.
-
Ein auf diese Weise vervollständigter Transducer macht alle Untersequenzen, die dem
unvollständigen Hauptmodell vom s-Typ bekannt sind, genau so eindeutig, wie es das
unterlegte HMM macht, und alle anderen Untersequenzen so, wie es das zur Hilfe
verwendete n-Typ-Modell macht.
E. Transducer vom b-Typ
-
Dieser Abschnitt stellt ein Verfahren nach einer anderen Ausführungsform der Erfindung
vor, das ein Hidden-Markov-Modell (HMM) erster Ordnung durch einen Finite-Zustände-
Transducer (FST) approximiert, und das hier als b-Typ-Approximation bezeichnet wird.
Die in diesem Abschnitt verwendeten, regulären Ausdrucksoperatoren sind im Anhang
erklärt.
E.1 Grundlegende Idee
-
Das Tagging eines Satzes auf der Basis eines HMM (erster Ordnung) schließt das
Finden der wahrscheinlichsten Tag-Sequenz bei gegebener Klassensequenz des Satzes
ein.
-
Bei diesem Ansatz wird eine Mehrdeutigkeitsklasse hinsichtlich eines Kontextes
eindeutig gemacht. Ein Kontext besteht aus einer Sequenz von Mehrdeutigkeitsklassen, die an
beiden Enden durch einige ausgewählte Tags begrenzt sind. Für den linken Kontext der
Länge β wird der Begriff Rückschau benutzt, und für den rechten Kontext der Länge α
wird der Begriff Vorschau benutzt.
-
In Fig. 6 kann das Tag t2i, aus der Klasse ci ausgewählt werden, weil es zwischen zwei
ausgewählten Tags liegt, die t1i-2 bei einer Rückschauentfernung von β = 2 und t2i+2 bei
einer Vorschauentfernung von α = 2 sind. Tatsächlich erlauben die zwei ausgewählten
Tags t1i-2 und t2i+2 ermöglichen nicht nur die Schaffung von Eindeutigkeit der Klasse ci
sondern aller Klasse dazwischen, d. h. ci-1, ci, und ci+1.
-
Das Tagging eines ganzen Satzes wird approximiert durch das Tagging von
Untersequenzen mit ausgewählten Tags an beiden Enden (Fig. 6) und anschließendes
Überlappen. Die wahrscheinlichsten Pfade in dem Tag-Raum eines Satzes, d. h. die gültigen
Pfade nach diesem Ansatz können gefunden werden, wie in Fig. 7 skizziert. Eine
geordnete Menge überlappender Sequenzen, in der jeder Satz um ein Tag hinsichtlich der
vorherigen Sequenz nach rechts verschoben wird, bildet einen gültigen Pfad. Es kann
mehr als ein gültiger Pfad in dem Tag-Raum eines Satzes existieren (Fig. 7). Mengen
von Sequenzen, die sich nicht auf solche Weise überlappen, sind nach diesem Model
inkompatibel, und sie bilden keinen gültigen Satz.
E.2 b-Typ-Sequenzen
-
Bei gegebener Länge β der Rückschau und gegebener Länge α der Vorschau wird für
jede Klasse c&sub0;, jede Rückschau-Sequenz tβ c-β+1... c&submin;&sub1; und jede Vorschau-Sequenz c&sub1;
... cα-1, tα, eine b-Typ-Sequenz gebildet:
-
tβc-β+1 ... c&submin;&sub1; c&sub0; c&sub1; ... cα-1tα
-
Z. B.:
-
CONJ [DET,PRON] [ADJ,NOUN,VERB] [NOUN,VERB] VERB
-
Jede solche ursprüngliche b-Typ-Sequenz (Fig. 8) wird auf der Basis eines HMM erster
Ordnung eindeutig gemacht. Hier wird für Effizienz der Viterbi-Algorithmus (Viterbi,
1967; Rabiner, 1990) verwendet.
-
Der Algorithmus wird für ein HMM erster Ordnung erläutert. Im Fall eines HMM zweiter
Ordnung müssen b-Typ-Sequenzen mit zwei statt einem ausgewählten Tags beginnen
und enden.
-
Für eine ursprüngliche b-Typ-Seguenz kann die zusammengeführte Wahrscheinlichkeit
ihrer Klassen-Sequenz C mit ihrer Tag-Sequenz T (Fig. 8) abgeschätzt werden durch:
-
p(C,T = p(c&submin;β+1...cα-1, t&submin;β...tα) = [ α(ti ti-1)b(ci ti)]·α(tα tα-1)
-
Ein Grenze, d. h. ein Satzanfang oder ein Satzende, kann an einer Position in der
Rückschau-Sequenz und in der Vorschau-Sequenz auftreten. Keine Rückschau (β = 0) oder
keine Vorschau (α = 0) sind ebenfalls zugelassen. Die obige
Wahrscheinlichkeitsabschätzung kann dann allgemeiner ausgedrückt werden (Fig. 8) als:
-
p(C,T) = pstart · pmitte · pende
-
wobei für pstrt gilt:
-
pstart = a(t&submin;β+1 t-β) für festgestelltes Tag t&submin;β
-
pstart = π(t&submin;β+1) für mit # beginnenden Satz
-
pstart = 1 für β = 0, d. h. keine Rückschau
-
und wobei für pmitte gilt:
-
Pmitte = b(c&submin;β+1) t&submin;β+1)·α(ti ti-1)b(ci ti) für β + α > 0
-
Pmitte = b(c&sub0; t&sub0;) für β + α = 0
-
und wobei für pende gilt:
-
pende = a(tα tα-1) für festgestelltes Tag tα
-
pende = 1 für mit # endenden Satz oder α = 0, d. h. keine Vorschau
-
Wenn die wahrscheinlichste Tag-Sequenz für eine ursprüngliche b-Typ-Sequenz
gefunden ist, wird die Klasse c&sub0; in der Mittenposition mit ihrem wahrscheinlichsten Tag t&sub0;
assoziiert. Es werden Beschränkungen für die anderen Tags t-β und tα und die Klassen
c-β+1 ... c&submin;&sub1; und c&sub1; ... cα-1 der ursprünglichen b-Typ-Sequenz formuliert. So wird eine b-
Typ-Sequenz mit Tags ermittelt:
-
t-β c-β+1 ... c&submin;&sub1; c&sub0; : t&sub0; c&sub1; ... cα-1 tα
-
die aussagt, dass t&sub0; das wahrscheinlichste Tag in der Klasse c&sub0; ist, falls ihm t-β c-β+1 ...
c&submin;&sub1; vorangeht und es gefolgt wird von c&sub1; ... cα-1 tα.
-
In dem Beispiel:
-
CONJ-B2 [DET,PRON]-B1 [ADJ,NOUN,VERB] : ADJ [NOUN,VERB]-A1 VERB-A2
-
ADJ ist das wahrscheinlichste Tag in der Klasse [ADJ,NOUN,VERB], falls das Tag
CONJ zwei Positionen zurück (B2) ihm vorangeht, die Klasse [DET,PRON] eine Position
zurück (B1) ihm vorangeht, es gefolgt wird durch die Klasse [NOUN,VERB] auf einer
Position nach vorn (A1) und durch das Tag VERB auf zwei Positionen nach vorn (A2).
-
Grenzen werden durch ein besonderes Zeichen # bezeichnet, und können irgendwo in
der Rückschau und in der Vorschau vorkommen. Z. B.:
-
#-B2 [DET,PRONJ-B1 [ADJ,NOUN,VERB]:ADJ [NOUN,VERBJ-A1 VERB-A2
CONJ-B2 [DET,PRON]-B1 [ADJ,NOUN,VERB] : NOUN #-A1
-
Es wird bemerkt, dass die Rückschau-Länge β und die Vorschau-Länge α auch alle
Sequenzen einschließen, die kürzer als β bzw. α sind, die durch eine Grenze # begrenzt
sind.
-
Fig. 9
ist ein schematisches Diagramm, das die Schritte in der Prozedur der Bildung
eines b-Typ-Transducers nach einer Ausführungsform der Erfindung veranschaulicht.
-
Für eine gegebene Länge β der Rückschau und einer gegebenen Länge α der Vorschau
und unter Verwendung der Menge der Tags und der Menge der Klassen wird jede
mögliche ursprüngliche b-Typ-Sequenz erzeugt (Schritt s90). Dann werden diese statistisch
eindeutig gemacht und in einer b-Typ-Sequenz B1 mit Tags codiert, wie oben
beschrieben (Viterbi; Schritt s92). Alle Sequenzen B1 werden dann vereinigt und es wird ein
vorläufiges Tagger-Modell B' erzeugt (Schritt s94):
-
B' = [ Bi]*
-
wo alle Sequenzen Bi in irgendeiner Reihenfolge und Anzahl (einschließlich null mal)
vorkommen können, weil bisher keine Beschränkungen angewendet wurden.
E.3 Verkettungsbeschränkungen
-
Um eine korrekte Verkettung von Sätzen zu sichern, ist es abzusichern notwendig, dass
jeder Sequenz Bi andere Sequenzen Bi vorangehen und sie von anderen Sequenzen Bi
gefolgt wird, entsprechend dem, was in der Rückschau und in der Vorschau codiert ist,
wie oben erläutert.
-
Beschränkungen werden erzeugt für die vorangehenden und die nachfolgenden Tags,
Klassen und Satzgrenzen. Für die Rückschau wird ein bestimmtes Tag ti oder Klasse ci
für einen bestimmten Abstand von δ ≤ -1 verlangt, durch:
-
Rδ (ti) = ~[~[?*ti[\ t] [ t[\ t]*]^(-δ-1) t (-δ)?*]
-
Rδ (cj) = ~[~[?*cj[\ c] [ c[\ c]*]^(-δ-1) c (-δ)?*]
-
wobei ut und uc die Vereinigung aller Tags bzw. aller Klassen ist. Ein Satzanfang, #, wird
für einen bestimmte Rückschau-Abstand von δ ≤ -1 verlangt durch:
-
Rδ (#) = ~[~[[\ t] [ t[\ t]*]^(-δ-1) #B(-δ)?*]
-
für δ ≤ -1
-
In dem Fall von Vorschau wird in ähnlicher Weise für einen bestimmten Abstand von
δ ≥ 1 ein bestimmtes Tag ti oder Klasse ci oder ein Satzende # verlangt durch
-
Rδ (ti) = ~[?*t δ ~[[\ t] [ t[\ t]*]^(δ-1) ti?*]]
-
Rδ (cj) = ~[?*c δ ~[[\ c] [ c[\ c]*]^(δ-1) cj?*]]
-
Rδ (#) = ~[?*#Aδ ~[[\ t] [ t[\ t]*]^(δ-1)]]für δ ≥ 1
-
Die Schnittmenge Rt aller Tag-Beschränkungen Rδ(ti), die Schnittmenge Rc aller
Klassen-Beschränkungen Rδ(ci) und die Schnittmenge R# aller
Satzgrenzen-Beschränkungen Rδ(#):
-
Rt = Rδ(ti)
-
Rc = Rδ(cj)
-
R# = Rδ(#)
-
Alle Beschränkungen (für Tags, Klassen und Satzgrenzen) werden erzwungen (Schritt
s96 in Fig. 9) durch Komposition mit dem vorläufigen Tagger-Modell B'. Die Klassen-
Beschränkung Rc muß auf der oberen Seite von B' eingebracht werden, welches die
Seite der Klassen ist, und sowohl die Tag-Beschränkung Rt und die Satzgrenzen-
Beschränkung R# muß auf der unteren Seite von B' eingebracht werden, welches die
Seite der Tags ist:
-
B" = Rc·o·B'·o·Rt·o·R#
-
Nach Absicherung korrekter Verkettung werden alle Zeichen (von B") entfernt (Schritt
s98), die dazu dienten, Tags, Klassen oder Satzgrenzen zu enthalten. Schließlich wird
der FST determinisiert und minimiert.
-
Das oben angeführte mathematische Modell wird als ein b-Typ-Modell, der
korrespondierende FST als ein b-Typ-Transducer und der gesamte Algorithmus, der von dem
HMM zu dem Transducer führt, als eine b-Typ-Approximation eines HMM bezeichnet.
E.4 Eigenschaften der Transducer vom b-Typ
-
Es gibt zwei Gruppen von b-Typ-Transducern mit unterschiedlichen Eigenschaften. FST
ohne Rückschau oder ohne Vorschau und FST sowohl mit Rückschau als auch mit
Vorschau. Beide akzeptieren jede Sequenz von Mehrdeutigkeitsklassen.
-
b-Typ-FST ohne Rückschau oder ohne Vorschau sind immer sequentiell. Sie bilden eine
Klassensequenz, die mit der Wort-Sequenz eines Satzes korrespondiert, immer auf
genau eine Tag-Sequenz ab. Ihre Tagging-Genauigkeit und ihre Ähnlichkeit mit dem
unterlegten HMM vergrößert sich mit wachsender Rückschau oder Vorschau. Ein b-Typ-
FST mit Rückschau β = 1 und ohne Vorschau (α = 0) ist äquivalent zu einem n1-Typ-
FST (Abschnitt C).
-
b-Typ-FST mit Rückschau und mit Vorschau sind im Allgemeinen nicht sequentiell. Für
eine Klassen-Sequenz, die mit der Wort-Sequenz eines Satzes korrespondiert, liefern
sie eine Menge von alternativen Tag-Sequenzen ab, was bedeutet, dass die Tagging-
Ergebnisse mehrdeutig sind. Diese Menge ist nie leer, und die wahrscheinlichste Tag-
Sequenz nach dem unterlegten HMM ist immer in dieser Menge. Je länger der
Rückschau-Abstand β und der Vorschau-Abstand α sind, desto größer ist der FST und desto
kleiner ist die Menge der alternativen Tagging-Ergebnisse. Für hinreichend große
Rückschau plus Vorschau kann diese Menge immer nur ein Tagging-Ergebnis enthalten. In
diesem Fall ist der b-Typ-Transducer äquivalent zu dem unterlegten HMM. Aufgrund der
Größe jedoch ist dieser FST nur berechnebar für HMM mit kleinen Tag-Mengen.
F. Ein verwirklichter Finite-Zustände-Tagger
-
Der verwirklichte Tagger benötigt drei Transducer, die ein Lexikon, einen Schätzer und
eine Approximation eines HMM darstellen. Fig. 10 ist eine Veranschaulichung des
Tagging eines Satzes unter Verwendung entweder des n-Typ-Transducers von Fig. 3, des
s-Typ-transducers, der in Fig. 5 gebildet wird, oder des b-Typ-Transducers, der in Fig. 9
gebildet wird. Fig. 11 ist nach einer Ausführungsform der Erfindung ein schematisches
Flußdiagramm der Schritte, die in der Prozedur befasst sind, des Tagging eines
Textkorpus 20 mit einem Finite-Zustände-Tagger unter Verwendung eines
HMM-Transducers.
-
Jedes Wort 21 eines eingegebenen Satzes wird von dem Korpus gelesen (Schritt s71)
und wird anfänglich in dem Lexikon nachgeschlagen; und falls dies versagt, fährt die
Suche in dem Schätzer fort (Schritt s72), was zu einem mit einer Klasse etikettierten
Wort führt (22). Sobald ein eingegebenes Zeichen mit der Satzendeklasse etikettiert
wird (z. B. [SENT] in Fig. 10) beendet der Tagger das Lesen von Worten von der
Eingabe (Schritt s73). An diesem Punkt hat der Tagger die Worte eines ganzen Satzes
gelesen und gespeichert (Fig. 6, Spalte 1) und die korrespondierenden Sequenzen von
Klassen 23 erzeugt (siehe Fig. 10, Spalte 2).
-
Die Klassensequenz 23 ist nun deterministisch mittels des HMM-Tranducers auf eine
Tag-Sequenz 24 abgebildet (Schritt s74) (siehe Fig. 10, Spalte 3).
-
Der Tagger gibt die gespeicherte Wort- und Tag-Sequenz 24 des Satzes aus (Schritt
s75) und fährt auf dieselbe Weise mit den restlichen Sätzen des Korpus fort (Schritt
s76), und stoppt (Schritt s77), wenn das ende des Korpus erreicht ist. Das Endergebnis
ist der mit Tags versehene Textkorpus 25.
G. Tests und Ergebnisse
-
Tabelle 1 vergleicht einen Transducer vom n-Typ und einen Transducer vom s-Typ mit
dem mit dem unterlegten HMM bei einem Testfall in Englisch. Wie erwartet, führen die
Transducer das Tagging schneller durch als das HMM.
Tabelle 1: Genauigkeit, Geschwindigkeit, Größe und Erzeugungszeit von HMM-
Transducer
-
Da beide Transducer Approximationen von HMM sind, zeigen sie eine geringfügig
niedrigere Tagging-Genauigkeit als die HMM. Jedoch kann eine Verbesserung der HMM
erwartet werden, da diese Transducer zusammengebaut werden können mit Transducer,
die Korrekturregeln für häufige Fehler codieren, wie oben im einleitenden Teil dieser
Offenlegung beschrieben ist.
-
Der s-Typ-Transducer ist im Tagging genauer, aber auch größer und langsamer als der
n-Typ-transducer.
-
Tabelle 2 vergleicht die Tagging-Genauigkeit von s-Typ-Transducer und n-Typ-
Transducer und dem unterlegten HMM für verschiedene Sprachen.
Tabelle 2: Genauigkeit von HMM-Transducern für verschiedene Sprachen
-
Für den Test von b-Typ-Transducern wurde ein Korpus, Lexikon und Schätzer in
Englisch verwendet, der ursprünglich mit 74 Tags versehen war. Die Tags wurden
automatisch neu codiert, d. h. in einigen Fällen wurde mehr als eines der ursprünglichen Tags in
ein und dasselbe neue Tag neu codiert. Es wurden unterschiedliche neue Codierungen
angesetzt, so dass Korpus, Lexika und Schätzer in Englisch mit reduzierten Mengen von
45, 36, 27, 18 bzw. 9 Tags ermittelt wurden.
Tabelle 3: Genauigkeit, Tagging-Geschwindigkeit und Größe einiger HMM-Transducer
-
Tabelle 3 vergleicht b-Typ-Transducer mit unterschiedlicher Länge von Rückschau und
Vorschau für eine Tag-Menge von 27 Tags. Die höchste Genauigkeit (97,06%) konnte
mit einem b-Typ-FST mit β = 2 und α = 1 ermittelt werden. Dieserb-Typ-FST erzeugt in
einigen Fällen mehrdeutige Tagging-Ergebnisse. In diesen Fällen wurde nur das erste
gefundene Ergebnis beibehalten.
Tabelle 4: Tagging-Genauigkeit mit Tag-Mengen unterschiedlicher Größe
-
Tabelle 4 zeigt die Tagging-Genauigkeit unterschiedlicher b-Typ-Transducer mit Tag-
Mengen von unterschiedlicher Größe. Um Ergebnisse zu bekommen, die fast äquivalent
zu denen eines HMM sind, muß der b-Typ-FST eine Rückschau von mindesten β = 2 und
eine Vorschau von α = 1 oder umgekehrt haben. Aufgrund der Größe konnte diese Art
von FST nur für Tag-Mengen von 36 Tags oder weniger berechnet werden. Ein b-Typ-
FST mit β = 3 und α = 1 konnte nur mit einer Tag-Menge von 9 Tags berechnet werden.
Dieser FST ergab genau dieselben Tagging-Ergebnisse wie das unterlegte HMM.
H. Referenzen
-
Ait-Mokhtar, Salah und Chanod, Jean-Pierre (1997), Incremental Finite-State Parsing.
In: Proceedings of the 5th Conference of Applied Natural Language Processing. ACL,
Seiten 72-79. Washington, DC, USA.
-
Bahl, Lalit R. und Mercer, Robert L. (1976). Part of Speech Assignment by a Statistical
Decision Algorithm. In: IEEE international Symposium an Information Theory. Seiten 88
-89. Ronneby.
-
Brill, Eric (1992). A Simple Rule-based Part-of-Speech Tagger. In: Proceedings of the
3rd Conference an Applied Natural Language Processing, Seiten 152-155. Trento,
Italy.
-
Chanod, Jean-Pierre und Tapanainen, Pasi (1995). Tagging Fcench - Comparing a
Statistical and a Constraint Based Method. In: Proceedings of the 7th Conference of the
EACL. Seiten 149-156. ACL. Dublin, Ireland.
-
Church, Kenneth W. (1988). A Stochastic Parts Program and Noun Phrase Parsing for
Unrestricted Text. In: Proceedings on fhe 2nd Conference an Applied Natural Language
Processing. ACL. Seiten 136-143.
-
Kaplan, Ronald M. und Kay, Martin (1994). Regular Models of Phonological Rule
Systems. In: Computational Linguistics. 20: 3, Seiten 331-378.
-
Rabiner; Lawrence R. (1990). A Tutorial an Hidden Markov Models and Selected
Applications in Speech Recognition. In: Readings in Speech Recognition (eds. A. Waibel, K.
F. Lee). Morgan Kaufmann Publishers, Inc. San Mateo, CA., USA.
-
Viterbi, A. J. (1967). Error Bounds for Convolutional Codes and an Asymptotical
Optimal Decoding Algorithm. In: Proceedings of IEEE, Band 61, Seiten 268-278.
-
Anhang: Operatoren regulärer Ausdrücke des XEROX-Finite-Zustände-Calculus
Im Folgenden bezeichnen a und b Zeichen, A und B bezeichnen Sprachen und R und Q
bezeichnen Beziehungen zwischen zwei Sprachen. Mehr Details über die folgenden
Operatoren und Verweise auf Finite-Zustände-Literatur sind zu finden in:
-
http://www.rxrc.xerox.com/research/mltt/fst
-
$A Enthält. Menge von Ketten, die mindestens ein Vorkommen einer Kette von
A als Unterkette enthält.
-
~A Komplement (Negation). Alle Ketten außer der von A
-
[A - Aufgabe der Erfindung]
-
Term-Komplement. Irgendein Zeichen außer a.
-
A* Kleene-Stern. Null oder mehr Male A mit sich selbst verkettet.
-
A^n A n mal. Sprache A, n mal mit sich selbst verkettet.
-
A+ Kleene plus. Ein oder mehr Male A, mit sich selbst verkettet.
-
a -> b Ersetze. Beziehung, in der jedes a auf der oberen Seite auf ein b auf der
unteren Seite abgebildet wird.
-
a < - b Ersetze invers. Beziehung, in der jedes b auf der unteren Seite auf ein a auf
der oberen Seite abgebildet wird.
-
a : b Zeichen-Paar mit einem a auf der oberen und b auf der unteren Seite.
-
R.u Obere Sprache der Beziehung R.
-
R.I Untere Sprache der Beziehung R.
-
R.i Inverse Beziehung, in der die obere und die untere Sprache hinsichtlich R
ausgetauscht werden.
-
A B Verkettung aller Ketten von A mit allen Ketten von B.
-
A B Vereinigung der Sprachen A und B.
-
A & B Schnittmenge der Sprachen A und B.
-
A - B Relatives Komplement (Minus). Alle Ketten der Sprache A, die nicht in B
sind.
-
A .x. B Kreuzprodukt (Kartesisches Produkt) der Sprachen A und B.
-
R .o. Q Komposition der Beziehungen R und Q.
-
0 oder [] leere Kette (Epsilon)
-
? Irgendein Zeichen in dem bekannten Alphabet und seinen Erweiterungen.