next up previous contents index
Next: Definition der Wortarten für Up: Kontextorientierte Wortartenbestimmung Previous: Programme für die automatische

 

Ein Tagger mit variabler Kontextbreite

 

Allen bisher besprochenen statistischen Taggern ist gemeinsam, daß sie nur einen sehr engen Kontext von zwei bis maximal drei Wörtern berücksichtigen. Der Neuronale-Netze-Ansatz von Benello et al. (1989) erweitert die betrachtete Wortfolge zwar auf vier Vorgängerwörter und ein Nachfolgerwort. Die Codierung der Vorgängerwörter enthält jedoch wenig Redundanz. Dies und die berichtete Tendenz des Netzwerkes zur Übergeneralisierung (Benello et al., 1989, S. 212) läßt es als eher unwahrscheinlich erscheinen, daß der in den Vorgänger-Wörtern steckende Informationsgehalt auch tatsächlich vollständig genutzt wird.

Sicherlich spricht der Erfolg der vorgestellten Systeme dafür, daß offenbar in den meisten Fällen die Betrachtung des unmittelbaren Kontextes für die Wortarten-Disambiguierung ausreicht. Beispiele wie ``Hans und Kurt tex2html_wrap_inline23685 ein Fahrrad'' zeigen jedoch, daß in einigen Fällen ein weiterer Kontext berücksichtigt werden muß. Der Idealfall wäre es, jeweils ganze Sätze zu betrachten.

Versuchsweise wurde dieser Fall im Rahmen der vorliegenden Arbeit auf der Basis des Brown-Korpus programmiert. Das Programm arbeitet wie folgt: Mit Hilfe des Brown-Korpus wird zunächst eine Wort/Tag-Liste  erstellt, d. h. eine Tabelle, in der zu jeder Wortform alle möglichen Tags eingetragen sind. Soll ein Satz analysiert werden, so werden aus dem Brown-Korpus alle Tagfolgen herausgesucht, die zu Sätzen gleicher Wortzahl gehören. Es wird berechnet, ob sich den Wörtern des zu analysierenden Satzes auf Grund der Wort/Tag-Liste Tags in der Weise zuordnen lassen, daß sich eine dieser Tagfolgen ergibt. Ist dies der Fall bedeutet dies zweierlei:

  1. Zum einen wurde eine zu 100% korrekte Tagzuordnung für den zu analysierenden Satz gefunden (sofern das Brown-Korpus keine Fehler enthält).
  2. Zum anderen muß der zu analysierende Satz syntaktisch korrekt sein (sofern das Tag-System keine Schwächen aufweist).
Werden mehrere vollständig matchende Tagfolgen gefunden, so bedeutet dies, daß der Satz mehrdeutig ist. Ein Beispiel hierfür wäre etwa ``flying planes can be dangerous''. Dieser Satz kann einerseits im Sinne von ``fliegende Flugzeuge können gefährlich sein'' mit ``JJ NNS MD BE RB'' annotiert werden, andererseits aber auch im Sinne von ``Flugzeuge zu fliegen kann gefährlich sein'' mit ``VBG NNS MD BE RB'' (zur Bedeutung der Tags vergl. Tabelle gif).

 1.5mm

he PPS waited VBD a AT long JJ time NN 5
he PPS pushed VBD the AT radio NN button NN 5
he PPS opened VBD the AT inner JJ door NN 5
he PPS hit VBD the AT radio NN button NN 5
he PPS felt VBD a AT spectator NN interest NN 5
he PPS drew VBD a AT deep JJ breath NN 5
he PPS considered VBD the AT sober JJ possibility NN 5
he PPS boomed VBD a AT 280-yard NN drive NN 5
this DT explained VBD a AT great JJ deal NN 4
she PPS was BEDZ a AT real JJ experience NN 4
she PPS topped VBD the AT sextet NN brilliantly RB 4
it PPS was BEDZ the AT old JJ story NN 4
it PPS was BEDZ an AT excellent JJ concert NN 4
he PPS put VBD the AT bottle NN down RP 4
he PPS has HVZ the AT magical JJ eye NN 4
Alec NP heard VBD a AT faint JJ sound NN 4
what WDT are BER the AT relevant JJ data NN 3
this DT was BEDZ a AT profound JJ statement NN 3
this DT cuts VBZ the AT absentee NN rate NN 3
there EX was BEDZ a AT long JJ silence NN 3
that DT became VBD their PP$ home NN range NN 3
she PPS was BEDZ a AT juicy JJ one CD 3
peace NN is BEZ a AT worthy JJ objective NN 3
last RB comes VBZ the AT retention NN stage NN 3
it PPS was BEDZ not * candy NN wrapping NN 3
it PPS was BEDZ a AT big JJ one PN 3
he PPS was BEDZ the AT funniest JJT man NN 3
he PPS put VBD his PP$ head NN out RP 3
he PPS pushed VBD his PP$ way NN inside RB 3
he PPS peered VBD from IN a AT loophole NN 3
he PPS got VBD into IN the AT car NN 3
he PPS came VBD with IN his PP$ son NN 3
he PPS called VBD Pike NP a AT thief NN 3
don't DO* forget VB the AT foreign JJ press NN 3
Susan NP was BEDZ an AT active JJ character NN 3
I PPSS knew VBD the AT boy NN well RB 3
I PPSS am BEM a AT carpet NN salesman NN 3
I PPSS admire VB the AT English JJ lady NN 3
Gross NP swung VBD his PP$ swivel NN chair NN 3
Tabelle: Auswahl von Sätzen aus dem Brown-Korpus, die mit dem Beispielsatz ``he made the right decision'' am besten matchen. Die rechte Spalte gibt die Anzahl der Matches an. In der Wort/Tag-Liste finden sich folgende relevante Einträge: he (PPS), made (VBD, VBN), the (AT), right (NN, NR, JJ, RB, QL), decision (NN).

 

Das Verfahren arbeitet für kurze Sätze zufriedenstellend. Die Antwortzeiten liegen bei wenigen Sekunden. Tabelle gif gibt eine Auswahl derjenigen Sätze aus dem Brown-Korpus, die mit dem Beispielsatz ``he made the right decision'' am besten matchen. Es werden nicht nur Sätze mit vollständig matchenden Tagfolgen aufgeführt, sondern auch solche mit Abweichungen an einer oder zwei Positionen. Unter den Sätzen mit vollständig matchenden Tagfolgen finden sich solche, bei denen das vorletzte Wort mit ``JJ'', aber auch andere, bei denen es mit ``NN'' annotiert ist. Dies spiegelt eine Ambiguität des Beispielsatzes wieder: Er könnte nicht nur im Sinne von ``er traf die richtige Entscheidung'' interpretiert werden, sondern auch im Sinne von ``er traf die Rechtsentscheidung''. Unter Punkt 4 des weiter unten beschriebenen Algorithmus wird gezeigt, wie für mehrere formal richtige Tagzuordnungen die wahrscheinlichere berechnet werden kann.

Für längere Sätze (mehr als etwa 8 Wörter) ist es erwartungsgemäß sehr unwahrscheinlich, daß im Korpus Sätze mit vollständig matchenden Tagfolgen gefunden werden. Mit dazu bei trägt der Umstand, daß das Brown-Korpus mit einem Umfang von einer Million Wortformen ein nach heutigen Maßstäben eher kleines Korpus ist. Deshalb liegt es nahe, an jeder Wortposition ein Matching durchzuführen, das wenigstens die Anzahl der matchenden Tags maximiert, und nicht - wie es die im vorigen Abschnitt beschriebenen Systeme tun - den betrachteten Kontext willkürlich auf eine Anzahl von zwei oder drei Tags zu begrenzen. Diese wohl aus Gründen des Rechen- und Programmieraufwandes vorgenommene Beschränkung ist insofern unzweckmäßig, als es sich in Versuchen mit zufällig ausgewählten Beispieltexten gezeigt hat, daß sich an den meisten Textstellen Matches von etwa 4 bis 7 Tags erzielen lassen. Im Vergleich dazu liegt der Matchbereich beim direkten Vergleich der Wörter in der Regel bei 1 bis 3 (vergl. Kapitel gif, Abb. gif), d. h. in diesem Fall bringt es keine wesentlichen Verbesserungen, wenn längere Wortketten als Trigramme betrachtet werden.

Der im Rahmen dieser Arbeit entwickelte Tagger arbeitet wie folgt:

  1. Finde für jedes Wort eines Eingabetextes alle bei isolierter Betrachtung möglichen Tags. (Diese Informationen werden der Wort/Tag-Liste entnommen.)
  2. Setze den Wortpositionszähler auf Wort 1 des Eingabetextes.
  3. Finde für die augenblickliche Wortposition im Eingabetext diejenigen Tagfolgen im Korpus, die mit möglichst vielen der bereits ermittelten Vorgänger-Tags übereinstimmen und gleichzeitig mit möglichst vielen der potentiellen Nachfolger-Tags matchen. (Gezählt wird - auch über Satzgrenzen hinweg - jeweils bis zum ersten nicht matchenden Tag.) Berechne für jede Tagfolge den Wert tex2html_wrap_inline25425 . Hierbei ist V die Anzahl der übereinstimmenden Vorgänger-Tags und N die Anzahl der matchenden Nachfolger-Tags. Die Formel gewichtet symmetrisches Matching 10 mal stärker als asymmetrisches.
  4. Wähle die Tagfolge mit dem höchsten Wert für Q. Wird der Maximalwert von mehreren unterschiedlichen Tagfolgen gleichermaßen erreicht, suche unter diesen nach folgenden Kriterien die optimale heraus: Sortiere die betrachteten Tagfolgen zunächst nach Kriterium 1, dann nach Kriterium 2 (mit einem sich stabil verhaltenden Sortieralgorithmus, der die Reihenfolge identischer Objekte nicht ändert, vergl. Porth, 1992). Die Tagfolge an der ersten Rangposition der sortierten Liste gilt als die optimale.
  5. Ordne der augenblicklichen Wortposition das dieser Position entsprechende Tag der optimalen Tagfolge zu.
  6. Falls das letzte Wort noch nicht erreicht wurde, inkrementiere den Wortpositionszähler und gehe zurück zu Schritt 3.

Dieser Algorithmus führt bei Sätzen, für die eine vollständig matchende Tagfolge gefunden wird, zum selben Ergebnis, als ob vollständige Sätze gematcht würden. Bei unbekannten Wörtern im Eingabetext wird angenommen, daß diesen alle Tags zugeordnet werden können, d. h. unbekannte Wörter matchen immer (ebenso Wortpositionen vor dem Textanfang bzw. nach dem Textende). Durch die Berücksichtigung eines weiten Kontextes macht das System auch für unbekannte Wörter gute Prognosen selbst dann, wenn mehrere aufeinander folgen. Dadurch erscheint es denkbar, die Wort/Tag-Liste automatisch zu erweitern. Zusammengesetzte Wörter müssen durch das Morphologieprogramm zerlegt werden. Ihre grammatische Beschreibung richtet sich nach der letzten Konstituente.

Tabelle gif zeigt am Beispiel einer Fabel (aus Aesop's Fables, s. Anhang gif) die Ergebnisse, die mit dem beschriebenen Algorithmus beim maschinellen Annotieren eines für das System unbekannten Textes erzielt wurden. Im Rahmen der durch die Wort/Tag-Liste vorgegebenen Auswahl von Tags für jede Wortform traf das System in fast allen Fällen die bestmögliche Entscheidung. Lediglich die Wortfolge ``a second time'' wurde mit der Tagfolge ``AT NN NN'' (anstatt ``AT OD NN'') versehen, was der Interpretation ``eine Sekunde Zeit'' anstelle von ``ein zweites Mal'' entspricht. Diese ist in dem gegebenen Zusammenhang falsch.

In Tabelle gif wird gezeigt, daß der Tagger recht stabil reagiert, wenn er einige im zu bearbeitenden Text vorkommende Wörter nicht kennt, d. h. wenn zu einigen Wörtern in der Wort/Tag-Liste keine Einträge vorhanden sind. Zu diesem Zweck wurden die Wörter eines Beispielsatzes in systematischer Weise durch unbekannte Wörter ersetzt. Für die vom Tagger erzeugten Tagfolgen ist in der Tabelle jeweils eine Interpretation in Form eines zu dieser Tagfolge passenden Satzes angegeben.

 

The AT AT assured VBD VBN VBD
Bat NN NN VB him PPO PPO
and CC CC that CS CS DT WPS WPO QL
the AT AT he PPS PPS
Weasels NNS NNS was BEDZ BEDZ
. . . not * *
A AT AT NP a AT AT
Bat NN NN VB bird NN NN
who WPS WPS WPO , , ,
fell VBD VBD VB JJ but CC CC IN RB
upon IN IN RB a AT AT
the AT AT mouse NN NN
ground NN NN VBN VBD VB , , ,
and CC CC and CC CC
was BEDZ BEDZ thus RB RB QL
caught VBN VBD VBN was BEDZ BEDZ
by IN IN RB set VBN VBN VB NN VBD
a AT AT free JJ JJ VB RB
Weasel NN NN . . .
pleaded VBD VBD Shortly RB RB
to TO TO IN NPS QL afterwards RB RB
be BE BE the AT AT
spared VBN VBN VBD Bat NN NN VB
his PP$ PP$ PP$$ again RB RB
life NN NN fell VBD VBD VB JJ
. . . to IN TO IN NPS QL
The AT AT the AT AT
Weasel NN NN ground NN NN VBN VBD VB
refused VBD VBD VBN and CC CC
, , , was BEDZ BEDZ
saying VBG VBG NN caught VBN VBD VBN
that CS CS DT WPS WPO QL by IN IN RB
he PPS PPS another DT DT
was BEDZ BEDZ Weasel NN NN
by IN IN RB , , ,
nature NN NN whom WPO WPO
the AT AT he PPS PPS
enemy NN NN likewise RB RB
of IN IN entreated VBD VBD
all RB ABN QL RB not * *
birds NNS NNS to TO TO IN NPS QL
. . . eat VB VB
The AT AT him PPO PPO
Bat NN NN VB . . .
Tabelle: Beispiel für einen automatisch mit Tags versehenen Text. Zu jedem Wort sind neben dem berechneten Tag auch alle in der Wort/Tag-Liste enthaltenen Tags in nach absteigender Häufigkeit geordneter Reihenfolge angegeben (Fortsetzung s. nächste Seite).

 

 

The AT AT , , ,
Weasel NN NN but CC CC IN RB
said VBD VBD VBN a AT AT
that CS CS DT WPS WPO QL bat NN NN VB
he PPS PPS , , ,
had HVD HVD HVN and CC CC
a AT AT thus RB RB QL
special JJ JJ NN a AT AT
hostility NN NN second NN OD NN RB QL
to IN TO IN NPS QL time NN NN VB
mice NNS NNS escaped VBD VBN VBD
. . . . . .
The AT AT It PPS PPS PPO
Bat NN NN VB is BEZ BEZ
assured VBD VBN VBD wise JJ JJ
him PPO PPO to TO TO IN NPS QL
that CS CS DT WPS WPO QL turn VB VB NN
he PPS PPS circumstances NNS NNS
was BEDZ BEDZ to IN TO IN NPS QL
not * * good JJ JJ NN RB
a AT AT account NN NN VB
mouse NN NN . . .
Tabelle: Beispiel für einen automatisch mit Tags versehenen Text (Fortsetzung).

 

  1.4mm

Lückentext Tagfolge Interpretation
he went to the city . PPS VBD IN AT NN . he went to the city.
tex2html_wrap_inline23685 went to the city . NP VBD IN AT NN . Jack went to the city.
he tex2html_wrap_inline23685 to the city . PPS VBD IN AT NN . he went to the city.
he went tex2html_wrap_inline23685 the city . PPS VBD IN AT NN . he went to the city.
he went to tex2html_wrap_inline23685 city . PPS VBD IN AT NN . he went to the city.
he went to the tex2html_wrap_inline23685 . PPS VBD IN AT NN . he went to the city.
he went to the city tex2html_wrap_inline23685 PPS VBD IN AT NN . he went to the city.
tex2html_wrap_inline23685 tex2html_wrap_inline23685 to the city . NP VBD IN AT NN . he went to the city.
he tex2html_wrap_inline23685 tex2html_wrap_inline23685 the city . PPS VBD IN AT NN . he went to the city.
he went tex2html_wrap_inline23685 tex2html_wrap_inline23685 city . PPS VBD IN DT NN . he went to this city.
he went to tex2html_wrap_inline23685 tex2html_wrap_inline23685 . PPS VBD TO VB RB . he wanted to go fast.
he went to the tex2html_wrap_inline23685 tex2html_wrap_inline23685 PPS VBD IN AT NN . he went to the city.
tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 the city . NP VBD IN AT NN . Jack went to the city.
he tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 city . PPS BEDZ AT NN NN . he was the head officer.
he went tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 . PPS VBD IN DT NN . he went to this city.
he went to tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 PPS VBD IN VBG NNS . he came from eating apples.
tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 city . PPS VBD IN DT NN . he went to this city.
he tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 . PPS VBD IN DT NN . he went to this city.
he went tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 PPS VBD IN VBG NNS . he came from eating apples.
tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 . PPS VBD IN DT NN . he went to this city .
he tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 PPS VBD IN VBG NNS . he came from eating apples.
tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 tex2html_wrap_inline23685 PPS VBD IN VBG NNS . he came from eating apples.
Tabelle: Tagfolgen zu Lückentext-Variationen des Satzes ``he went to the city.'' Um einen Kontext zur Verfügung zu stellen, wurden die Sätze ``he was hungry.'' und ``there he had lunch.'' voran- bzw. nachgestellt.

 

In seiner momentanen Implementierungsstufe erreicht das System bei willkürlich ausgewählten Texten eine Quote von etwa 94% richtig annotierter Wörter. Dieses Ergebnis ist trotz der Berücksichtigung langer Tagfolgen nicht besser als die Ergebnisse der im vorigen Abschnitt beschriebenen Systeme. Es sollte jedoch beim Vergleich berücksichtigt werden, daß diese Systeme durch eine Reihe von Heuristiken optimiert wurden (zum Beispiel durch gezielte Erweiterung der Wort/Tag-Liste oder durch a-priori-Wissen wie etwa, daß groß geschriebene Wörter, die nicht am Satzanfang stehen, normalerweise mit NP annotiert werden müssen). Beim hier vorgestellten System hingegen stand die Einfachheit des Algorithmus und die Sprachunabhängigkeit im Vordergrund. Dadurch ist das Potential, durch Einbau ähnlicher Heuristiken die Trefferquote zu steigern, noch ungenutzt.

Empfindlich ist der Algorithmus gegenüber Fehlern im als Referenz verwendeten Korpus und gegenüber unvollständigen Einträgen in der Wort/Tag-Liste, d. h. gegenüber Wörtern, für die in der Wort/Tag-Liste zwar einige, aber nicht alle möglichen Tags angegeben sind. Das erste Problem stellt sich beim Brown-Korpus nicht, da dieses weitgehend fehlerfrei sein dürfte. Das zweite Problem könnte gelöst werden, indem man auch Matches erlaubt, die nicht durch die Wort/Tag-Liste abgedeckt werden, wenn dadurch die Anzahl der matchenden Tags erheblich steigt. Dies würde aber zu einer wesentlich längeren Rechenzeit führen. Die Geschwindigkeit für das Annotieren liegt in der augenblicklichen Implementierung auf einem 70 MIPS-Rechner bei etwa fünf Wörtern pro Sekunde, könnte aber bei Bedarf durch Optimierung der verwendeten Suchalgorithmen noch um ein bis zwei Zehnerpotenzen gesteigert werden


next up previous contents index
Next: Definition der Wortarten für Up: Kontextorientierte Wortartenbestimmung Previous: Programme für die automatische

Reinhard Rapp
Fri Jul 18 19:19:31 MET DST 1997