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 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 ).

 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

 

Das Verfahren arbeitet für kurze Sätze zufriedenstellend. Die Antwortzeiten liegen bei wenigen Sekunden. Tabelle  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 , Abb. ), 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 . 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:
   • Kriterium 1: Häufigkeit der betreffenden Tagfolge im Brown-Korpus.
   • Kriterium 2: Bilde für jede Tagfolge das Produkt aus den Wahrscheinlichkeiten, daß das jeweilige Wort das zugeordnete Tag annimmt (diese Wahrscheinlichkeiten werden dem Brown-Korpus entnommen).
   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  zeigt am Beispiel einer Fabel (aus Aesop's Fables, s. Anhang ) 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  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 . . .

 

 

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 . . .

 

  1.4mm

Lückentext Tagfolge Interpretation

he went to the city . PPS VBD IN AT NN . he went to the city.

went to the city . NP VBD IN AT NN . Jack went to the city.

he to the city . PPS VBD IN AT NN . he went to the city.

he went the city . PPS VBD IN AT NN . he went to the city.

he went to city . PPS VBD IN AT NN . he went to the city.

he went to the . PPS VBD IN AT NN . he went to the city.

he went to the city PPS VBD IN AT NN . he went to the city.

to the city . NP VBD IN AT NN . he went to the city.

he the city . PPS VBD IN AT NN . he went to the city.

he went city . PPS VBD IN DT NN . he went to this city.

he went to . PPS VBD TO VB RB . he wanted to go fast.

he went to the PPS VBD IN AT NN . he went to the city.

the city . NP VBD IN AT NN . Jack went to the city.

he city . PPS BEDZ AT NN NN . he was the head officer.

he went . PPS VBD IN DT NN . he went to this city.

he went to PPS VBD IN VBG NNS . he came from eating apples.

city . PPS VBD IN DT NN . he went to this city.

he . PPS VBD IN DT NN . he went to this city.

he went PPS VBD IN VBG NNS . he came from eating apples.

. PPS VBD IN DT NN . he went to this city .

he PPS VBD IN VBG NNS . he came from eating apples.

PPS VBD IN VBG NNS . he came from eating apples.

 

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