SLP Notizen

Teil I
Kapitel 3: Morphologie und FSTs (finite-state transducer, Moore-Automat, Mealy-Automat)

Inhalt

1. Morphologie behandelt die Lehre von den Formen der Wörter, die aus Morphemen, den kleinsten funktionistragenden Einheiten der Sprache zusammengesetzt sind
• die Disambiguierung und Strukturisierung von Wörtern heißt morphologisches Parsen
• man unterscheidet vielfach zwischen einer zugrundeliegenden lexikalische (Tiefen-)Form und der realisierten Oberflächenform
• Morphologie hilft bei:
• Lemmatisierung: Zurückführung eines Worts auf seine "Grundform", komplexe Form des stemmings
• Tokenisierung: Zerteilung einer Äußerung in seine Wörter/Bestandteile
• Erkennung neuer Wörter, die durch Produktion entstanden sind
• Morphologie ist ein tatsächlicher Schritt in der Sprache, deswegen kann man ohne morphologische Methoden nicht/kaum Sprache verarbeiten
• Morphologische Prozesse lassen sich gut durch FSTs (endliche Transduktoren) beschreiben
2. Morpheme
• lassen sich unterscheiden in Wortstämme und Affixe (Prefixe, Suffixe, Infixe und Zirkumfixe). 
• Die Zahl der Stämme und Affixe in einem Wort ist sprachabhängig (agglutinierende Sprachen besonders hoch)
• die Affixe lassen sich häufig auch als Merkmale ansehen (engl -s: 3. sg, -bar: VB->ADJ)
3. Morphotaktische Prozesse
   
• Flektionsmorphologie (Beugung)
• gehen -> geh + INF, ging -> {geh + 1. sg, Prät, geh + 3. sg,m Prät.}
• verändert die Wortart nicht
• es gibt regelmäßige und unregelmäßige Beugung, teilweise unterschiedliche Flektionsgruppen. 
• Unregelmäßige Beugung besonders häufig bei häufigen Wörtern, meist ist nur die regelmäßige Klasse produktiv
• Derivationelle Morphologie (Ableitung)
• Abgang -> Ab + (geh + NN)
• Affixe die aus Wörtern einer bestimmten Wortart ein Wort einer anderen (oder auch derselben) Wortart erzeugen
• genaue Semantik nur sehr selten präzise deduzierbar
• Komposition (Zusammensetzung, sehr produktiv im Deutschen)
• Schultisch -> Schule + Tisch
• Klitisierung
• haste -> hast du, I'm -> I + am, l'hôtel -> le + hôtel, 
• nicht-konkatenative Morphologie: komplexere Zusammenhänge als durch Reihung bzw. Infixe und Zirkumfixe
• template morphology: Konsonanten bestimmen den Wortsinn, Vokalpattern die Wortart (semitische Sprachen)
• Vokalharmonie: Vokale innerhalb eines Wortes müssen einer Gruppe angehören (finno-ugrische Sprachen, türkisch)
4. FST parsing
• Erzeugung der Wortstruktur zu einem gegebenen Wort (in Oberflächenform)
• die Wortstruktur ist nicht immer eindeutig (probabilistische Modelle, POS tagging)
• nutzt zwei-Schichtiges Morphologisches Parsing
• lexikalische Darstellung -> Zwischenrepräsentation (Morphemgrenzen, Merkmale in Form und nicht Funktion)
• Zwischenrepräsentation -> Oberflächenform
• benötigt:
• Lexikon: enthält die Stämme und Affixe zusammen mit Informationen über ihre morphologischen Eigenschaften (z. B. unregelmäßig, nicht steigerbar, Konjugationsgruppe 2, ...)
• Morphotaktik: Modell der Zusammensetzung von Morphemen zu Wörtern
• orthographische und phonologische Regeln: erklären Schreib- bzw. Aussprachebesonderheiten (Fugen-S im Deutschen, y -> ie im Englischen vor Plural-S)
• Kompilation: Entfernung der Abstraktionsschichten (Wortarten, unterschiedliche Regeln) zur Effizienzsteigerung
• Lexikon: Wörter werden bestimmten "Klassen" zugeordnet, die im weiteren im FST an die Kantenübergänge geschrieben werden (ermöglicht die leichte Erweiterbarkeit der Morphologie, letztendlich wird der FST häufig aus dem Lexikon "kompiliert" und erst dann eingesetzt -> höhere Effizienz)
• endliche Automaten können (mit Einschränkungen: Morphologie ist nicht immer in jeder Sprache regulär) benutzt werden um Wörter der Sprache zu akzeptieren und Nichtwörter zurückzuweisen
• aus einem Startzustand führen Kanten (mit leerem Wort oder für Morpheme) in andere Zustände. Bestimmte Zustände sind Endzustände. Alle gültigen Wörter führen in einen Endzustand, ungültige Wörter nicht
• solche Modelle sind wegen vieler Ausnahmen und dem schieren Umfang des Regelwerks sehr komplex
• in kompilierten Automaten stehen an den Übergängen Buchstaben (bzw. das leere Wort), sodass die Akzeptanz sehr effizient geprüft werden kann
• FSTs erweitern endliche Automaten indem sie nicht nur von einem Eingabeband lesen, sondern auch auf ein Ausgabeband schreiben
• das Schreiben kann an den Zustand gebunden sein (Moore-Automat) oder an die Zustandsübergänge (Mealy-Automat). in diesem Kapitel werden Mealy-Automaten benutzt, sie sind aber äquivalent zu Moore-Automaten
• FSTs definieren eine Relation zwischen Wort-Mengen
• der FST besteht aus
• endlicher Zustandsmenge Q
• endliches Alphabet Σ komplexer Symbole i:o, mit i ∈ I und o ∈ O, also Σ ⊆ I × O, das leere Wort ε darf in I und O enthalten sein
• komplexe Symbole a:a werden einfach als a geschrieben
• @ steht für das Jokersymbol, das jedes Symbol repräsentiert
• "other" steht für sonst nicht im Automaten besonders vorkommende Symbole
• Startzustand q₀
• Menge der Endzustände F ⊆ Q
• Übergangsfunktion δ: Q × Σ → Q für deterministische FSTs bzw.
• Übergangsrelation δ: Q × Σ → 2^Q für nichtdeterministische FSTs
• FSTs sind geschlossen bezüglich Vereinigung aber nicht bezüglich Differenz, Komplement und Schnitt
• FSTs sind außerdem geschlossen bezüglich 
• Umkehrung (Inversion, Vertauschung von I und O)
• brauchbar, wechselt zwischen Erkennung und Generierung
• Komposition (Hintereinanderschaltung mehrerer FSTs ist wieder ein FST)
• Kaskaden von FSTs verhalten sich wie FSTs, sehr nützlich!
• für FSTs muss das Lexikon um lexikalische und Oberflächen-Ebene erweitert werden, indem Paare i:o angegeben werden (g o:e o:e s e)
5. Two level morphology
• zunächst wird aus der lexikalischen Ebene in eine Zwischenebene übersetzt, danach in die Oberfläche
• bisher: Automat liest Stamm + Merkmale (fox + N + PL) und schreibt Morphemfolge, mit Grenzen und Wortende (fox + ^ + s + #)
• diese Zwischendarstellung muss nach orthographischen bzw. phonologischen Regeln in die Oberflächenform gebracht werden
• Darstellung phonologischer/orthographischer Regeln: a → b / c __ d bedeutet: a wird zu b zwischen c und d (Notation nach Chomsky und Halle '68)
• diese Regeln können durch Transduktoren ausgedrückt werden (die Transduktoren können automatisch aus der Regel erstellt werden)
• die orthographischen Transduktoren laufen parallel, der Lexikon-FST davor kaskadiert
• beim Parsen können Mehrdeutigkeiten auftauchen (bei komplizierten Worten sehr häufig → probabilistische FSTs)
• TODO Algorithmus zur Automaten-Schneidung
6. Stemming:
• einfache Verfahren um abgeleitete Morpheme auf einen Stamm zurückzuführen (indizierte Wörter werden gestemmt, später kann das gestemmte Suchwort direkt verglichen werden)
• meist kaskadierte Rewrite-Regeln
• "Wort-Hashing"
7. menschliche Morphologie-Verarbeitung
• teilweise ist Morphologie lexikalisch, teilweise nicht, teilweise beides
• Sprechfehler als Zeichen des Vorhandenseins eines Morphologiemoduls

8. Tokenisierung
• Zerlegung des Eingabetextes/-stromes in 
• Sätze: nicht jeder Punkt beendet einen Satz
• Wörter: nicht jedes Leerzeichen trennt Wörter, nicht immer steht zwischen Wörtern ein Leerzeichen
• einfache Heuristiken (Abkürzungslisten, ggf. Großschreibung, etc.)
• komplexere Modelle: HMMs, N-Gramme, integriert in POS-Tagger, ...
• das Chinesische (zum Beispiel) kennt keine Wortgrenzen, sie müssen komplett geschätzt werden
• TODO Algorithmus
• gesprochene Sprache kennt keine Wortgrenzen
9. Rechtschreibfehler erkennen und korrigieren (nicht probabilistisch)
• relativ große Tippfehlerraten
• gleiches Problem wie OCR und Handschrifterkennung
• meist probabilistische Modelle (HMMs), hier nur einführende Algorithmen
• man unterscheidet:
• non-word errors (Graffe)
• isolierte Korrektur (Graffe-> Giraffe)
• isolierte Erkennung nur von non-word errors möglich
• kontextabhängige Erkennung und Korrektur
• erlaubt auch die Erkennung von real-word errors (Giroaffe)
• braucht statistische Modelle um zu funktionieren (N-Gramme)
• mit endlichen Automaten lässt sich die Zugehörigkeit eines Worts zur Sprache prüfen (Lexikon + Morphologie)
• bei Neueinträgen kann ein FST den Stamm + Endungen erkennen und sofort werden auch abgeleitete Wörter erkannt
• zur Fehlerkorrektur braucht man eine Metrik, die die Distanz zwischen Wörtern errechnet
• meist statistisches Modell, zugrundeliegend jedoch die Minimum Edit Distance
10. Minimum Edit Distance (Wagner und Fischer, 1974)
• eine Metrik die die "Ähnlichkeit" von Zeichenketten bezeichnet
• Algorithmus nutzt dynamische Programmierung (optimale Teillösungen sind Teil der optimalen Lösung, werden also zuerst berechnet)
• siehe auch CYK-, Early-Parser, Viterbi-, forward-Algorithmen, DTW?)
• erreicht "alignment" (Abgleich, Anordnung) der Zeichenketten durch die Operationen Entfernung, Einfügung, Ersetzung
• den Operationen werden Kosten zugewiesen, Levenshtein-distance: 
• Entfernung = Einfügung = 1, 
• Ersetzung = 2 = Entfernung + Einfügung. Ersetzung ist also redundant.
• alignment lässt sich durch Backtrace rausfinden
• TODO: Algorithmus genau ausführen (Papier)

letzte Änderung: 17. August 2006.