Automatische Akquisition linguistischen Wissens

WS 05/06 Automatische Akquisition linguistischen Wissens 1

Automatische Akquisition linguistischen Wissens

Automatisches Taggen von Wortklassen, bzw. Part of Speech (POS) Induction

1. Definition Wortklassen, • klassischer Konstituententest (Grewendorf)

2. Anwendungen

3. Algorithmen

4. Evaluierungen

• Referat: (Rapps Algorithmus)


1. Problemstellung

• Die meisten bisher behandelten halb-automatischen Algorithmen sind nur deshalb halb-automatisch, da sie Informationen über Wortklassen zum Funktionieren benötigen

• Wenn diese Information vollautomatisch extrahierbar wäre, würden eine Menge Algorithmen als vollautomatisch klassifizierbar sein

• Aus vergangenem Seminar wissen wir, dass einfache Modellierung des Konstituententests bereits sehr Wortklassenhomogene Wörter zu einem Eingabewort liefert


1.1. Konstituententest: Ersetzungsprobe

Einführung in Syntax (Dr. Tania Avgustinova):

• Teilketten, die in gleicher syntaktischer Position in einer gegebenen Kette austauschbar sind, ohne dass die neu entstandene Kette ungrammatisch ist, können gegebenenfalls Konstituenten sein– Für sich genommen reicht der Substitutionstest nicht aus, um eine

befriedigende Satzanalyse zu erzeugen.

– Beim Substitutionstest wird auch darauf geachtet, wie viele Syntagmen ein Paradigma umfasst und in wie vielen verschiedenen Umgebungen ein Paradigma vorkommen kann .

– In der tatsächlichen Anwendung muss er von der Intuition überprüft und vor allen Dingen durch andere Verfahren ergänzt werden.


1.2. Weitere Tests

Woran können überhaupt Strukturkomponenten erkannt werden?

• Ersetzungsprobe

• Pronominalisierungstest

• Weglassprobe– Hängt mit Redundanzprinzip zusammen

• Fragetest– wer, wann, wohin, warum, …

• Koordinierungstest– Welche Einheiten können (wie) miteinander kombiniert werden

• Verschiebeprobe– Nur bei freier Wortstellung


1.3. Definition Wortklasse

• Ergebnis der Klassifizierung der Wörter einer Sprache nach grammatischen und/oder semantischen Merkmalen; je nach den zugrunde liegenden Klassifizierungskriterien unterscheidet sich die Zahl der Wortarten in einer Sprache. (Kim Kluckhohn, Leipzig)

• Frage: Was sind die grammatischen und/oder semantischen Merkmale (außer wenn der Intuition entnommen)

• Was kennen wir bislang:– Syntagm. Auftreten

– Paradigmatische Selektion

– Morphologie (Kodierung grammatischer Merkmale?)

– Ambiguität (lexikalische oder syntaktische?)


2. Anwendungen

… es gibt keine/kaum direkte Anwendungen, aber:

• Automatisches Grammatiklernen, erster Schritt Wortklassen– wirklich? Vielleicht gibt es auch eine Vorstufe zu Wortklassen

• Tagger folgen als nächstes

• Grammar induction (siehe nächstes Seminar)

• Direkte Nutznießer wären allerdings fast alle Applikationen, die mit Sprache zu tun haben, IR, Schreibhilfen, usw.


3. Algorithmen• Der intuitiv erste Ansatz ist der, Features zu definieren

– grammatische/semantische Merkmale– Oder auch praktisch Satz- oder Nachbarschaftskookkurrenzen

• Anschließend ein beliebiges Clusterverfahren– Allerdings Komplexität problematisch:

• Finde ähnlichstes Paar, fasse zusammen: n^2• Wiederhole so oft, wie es Elemente gibt: n*n^2=n^3• N = Anzahl der Wörter = 500.000 für BNC, 200.000 für unseren

Studentenkorpus, • also 8.000.000.000.000.000 Operationen, bei 2 GHz (also grob 2Mio

Operationen pro Sekunde) sind das 126 Jahre! Und nur für eine Parametereinstellung…

– Daher oft stark vereinfachte Clusterverfahren (Buckshot, Single Pass), so dass nicht klar, ob mangelnde Performanz nicht nur am Clusterverfahren liegt

– Plausibel, weil auch bei Sprachlernern Sprache nicht plötzlich auf einmal gelernt wird, sondern Stückchenweise

• Evaluierung– Perplexität, Goldstandard (Cluster purity), coverage


3.1. Features

• Nutzbare Features wären idealerweise grammatische Informationen, wie sie rund um das Wort auftreten:– Dass „Fisch“ als Argument von „schwimmt“ verwendet werden

kann

– Dass „schwimmt“ mindestens ein Argument benötigt (Wer schwimmt), aber auch z.B. zwei möglich (Wer schwimmt wohin) oder drei (Wer schwimmt wie/warum wohin)

– Allerdings unterliegt das dem acquisition bottleneck: Wenn diese Information bereits vorliegt, brauchen wir nichts mehr zu tun

• Anderes Extrem: reine Nachbarschaftskookkurrenzen– Keinerlei Verallgemeinerung

– Data sparseness, da selbst 50 maliges Vorkommen nur maximal 50 verschiedene Vorkommen, in Wirklichkeit oft viel weniger


3.2. Features optimal

• Optimal vermutlich: weiter gefasste Nachbarschaftskookkurrenzen mit leichten Verallgemeinerungen– Vorclustern z.B. dass alle Fischrelevanten Dingen zusammen zu

kleiner Gruppe und daher statt

• Der Hering schwimmt durch das Wasser

• Der Fisch schwimmt durch den Fluss

– Besser wäre

• Der <Gruppe4563> schwimmt durch <Gruppe9873>

– Daraus dann Nachbarschaftskookkurrenzen

– Evtl. nicht direkte Nachbarschaftskookkurrenzen, ein wenig mehr Struktur vermutlich hilfreich


3.3. Weitere Features

• Offensichtlich sollten Wörter wie glückliche, glücklicher, unglückliche, glücklichster, usw. zu einer Wortgruppe gehören, – aber nicht glückte!

• Morphologie spielt also vermutlich eine wichtige Rolle, einfach Grundformreduzierung zur Vorclusterung reicht allerdings nicht

• Offenbar gibt es auch verschiedene syntaktische Bedeutungen eines Wortes: „may“ (could, would, should) oder (april, june, july)– Würde Disambiguierungsalgorithmus helfen?

– Unterscheidet dieser denn zwischen syntaktischen Klassen?

• Nur dann, wenn sie sich auch thematisch unterscheiden, also bei may ja, aber bei „walk“ (to have a walk, to walk away) aber leider nicht.


3.4. Vorhandene Algorithmen

• Bisher relativ wenig und verstreute Forschung zu diesem Thema (Übersicht dank C. Biemann):– Finch 92, 93 (und Chater) – hierarchisches clustern

• 5000 Wörter– Schütze 93 – heute : cosinus zw. Kontextvekt., Buckshot clustern

• Brown Korpus– Gauch & Futrelle : mut. inf. hierarch. agglom. Clustern

• 1000 Wörter– Clark 00 : Kullback-Leibler divergence– Clark 03: Addiert auch morphologische Information– Freitag 04 : – Rapp 05 : SVD hierarch. Clustern

• 50 Wörter

• Verwenden oft nur 150-250 frequenteste Wörter als Features oder benutzen SVD zur Dimensionalitätsreduzierung (Rapp)


3.5. Beispiele


3.5.1. Beispiel semantischen Einflusses

• Cluster #186288: (20 Wörter)• A=5 · N=80 · S=10 · V=5• Arbeitslehre · Ethik · Faches · Fachs · Islamkunde · LER ·

Lebensgestaltung · Lebensgestaltung-Ethik-Religion · Lebensgestaltung-Ethik-Religionskunde · Lebenskunde · Lehrfach · Pflichtfach · Pflichtfaches · Pflichtfachs · Religion · Schulfach · Unterrichtsfach · Unterrichtsfaches · ordentlichen · unterrichtet

• Cluster #174381: (7 Wörter)• A=85 · S=14• eigenständiges · freiwilliges · normales · ordentlichem · ordentliches ·

reguläres · verbindliches

• Diese beiden Cluster werden leider im nächsten Schritt vereinigt.


4. Evaluierung

• Goldstandard (Cluster purity)– Misst wie viele Prozent eines Clusters von der am meisten

vorkommenden Wortklasse sind

– Gewichtet das nach Clustergröße

• Problem, dass hohe Baseline (da unter Umständen einfach zufällig sortiert bei 80% Nomen eben 80% purity erreicht wird)

• Problem, dass zu viele Cluster nicht „bestraft“ werden

• Coverage– Wie viele der Wörter wurden überhaupt insgesamt gesehen der

richtigen Wortklasse zugewiesen, wenn nachträglich Clustern Wortklassen vergeben werden

– Oder wieviele Wörter überhaupt geclustert wurden


4.1. Evaluierung (Perplexity)

• Perplexity ist das maß, wie perplex etwas ist, wenn es etwas entscheiden soll.

• Falls ich die Tag-Sequenz DET ADJ NN VVFIN PP vorliegt und das nächste tag DET ist, – Dann prüfen, mit welcher Wahrscheinlichkeit Modell DET

vorhersagt

– z.B. 0.2, perplexity ist dann 1/p = 5

• Allerdings kann das natürlich nicht auf globale Cluster gemessen werden, sondern auf konkreten Anwendungen in Sätzen, für welche vorher ein entsprechendes Modell angelernt wurde.


Referat

Documents

Automatische Akquisition linguistischen Wissens