SLP Notizen

Teil I
Kapitel 6: N-Gramme (Kapitel 4 in der zweiten Ausgabe)

Inhalt

0. Motivation
• auf ein ort folgt nicht mit gleicher Wahrscheinlichkeit jedes andere Wort, manche sind wahrscheinlicher als andere
• man spricht von Sprachmodellen (Language Modell, LM)
• gleiches gilt für Buchstaben, Sätze, Gesten, Mensaessen
• mit großen Korpora lassen sich solche Wahrscheinlichkeiten schätzen und nutzen um
• ohne tieferes Verständnis (Morphologie) Vorhersagen zu treffen (Morphemgrenzen), also Unwissen auszugleichen
• tatsächlich nicht durch Regelsysteme repräsentierbares Wissen (Wahrscheinlichkeiten) einzufangen
• Phänomene unterschiedliche Herkunft mit einem System greifen
• Nachteile
• man arbeitet direkt auf der Oberflächenstruktur, zum Beispiel Auswirkungen syntaktischer Strukturen werden ignoriert
• Korpora zu erstellen ist teuer, schwierig und im Prinzip immer wieder neu notwendig (für andere Anwendungsgebiete)
• man hat immer zu wenig Daten um Sprache wirklich repräsentativ zu erfassen
• es gilt also zwischen Generalisierung und Spezialisierung abzuwägen
• was macht man mit Beobachtungen, die im Korpus nicht auftraten, die nur einmal auftraten?
• Anwendungen
• überall: Spracherkennung, Handschrifterkennung, OCR, stochastische MT, POS-tagging, T9, ...
1. Wörter zählen
• was ist ein Wort
• "multi words", zusammengesetzte Wörter mit Leerzeichen (New York)
• zählen Satzzeichen als Wörter?
• zählen Wortfragmente und Füllwörter in gesprochener Sprache?
• Tokens: Zahl der Wörter (absolut) in einem Text
• Types: Zahl der unterschiedlichen Wörter
• jeweils muss angegeben werden, ob die Tokens und Types irgendwie lemmatisiert werden oder Vollformen (wordforms) gezählt werden
• die Zahl der Types wächst mit der Zahl der Tokens an, Types > O(sqrt(N)
• wenige Wörter sind häufig, viele sind sehr selten (Zipfs Gesetz), man wird also nie alle Types gesehen haben, egal wie groß das zugrundeliegende Korpus
2. einfache N-Gramme (ungeglättete)
• Berechnung der (bedingten) Wahrscheinlichkeit für ein Wort w mit gegebener Historie h. 
• empirische Schätzung: P(w|h) = C(h w) / C(h)
• Beispiel: P(und | er kam, sah) = C(er kam, sah und) / C(er kam, sah). laut Google ~ 0.8
• Markov-Annahme: Kappung der Historie auf N Wörter, N = 1, 2, 3, 4, ... (Bigramme, Trigramme, ...) ändert die Wahrscheinlichkeiten nur geringfügig
• P(w_n|w₁^n-1) ≈ P(w_n|w_n-N+1^n-1)
• sinnvolle Einschränkung, da man eh nie, die ganze Äußerung (seit der Geburt) kennt
• Maximum Likelihood Estimation (MLE)
• N-Gramme zählen und normalisieren, sodass sie zwischen 0 und 1 liegen P(w_n|h_N) := C(h_N w) / C(h_N)
• erzeugt relative Frequenz
3. Smoothing (Glättung)
• Grund: gerade für seltene Ereignisse sind die Zählergebnisse sehr ungenau
• dank Zipf's Law ist die Klasse der seltenen Wörter sehr groß
• Add-One (Laplacian) Smoothing
• erhöht Wahrscheinlichkeit für selten gesehene Wörter
• zu jeder Beobachtung wird 1 dazugezählt und entsprechend bei der Wahrscheinlichkeit durch N + V (V Zahl der Klassen) geteilt
• sehr schlechtes Verfahren, aber einfach
• Witten-Bell Discounting
• Zahl einmaliger Ereignisse als Basis für nie gesehene Ereignisse
• ordnet ungesehenen Ereignissen eine Wahrscheinlichkeitsmasse (äquivalent zur W.keitsmasse der einmal gesehenen Ereignisse) zu
• kein Problem mehr mit ungesehenen Ereignissen!
• Good-Turing Discounting
• nutzt nicht nur die Zahl der 1-mal gesehenen für die W.keit 0-mal gesehener, sondern
• nutzt Zahl der (N+1)-mal gesehenen für die Ermittlung der N-mal gesehenen
• wird meist nur für die am seltensten (1 - 5 mal gesehenen) Wörter benutzt
• Kneyser-Ney Discounting
• TODO
4. Backoff
• wenn es kein N-Gramm gibt, so gibt es vielleicht ein (N-1)-Gramm!
• Backoff-Modelle müssen jeweils gewichtet werden, damit die Wahrscheinlichkeitsmasse nicht über 1 steigt
5. Deleted Interpolation
• wir benutzen immer auch die (N-x)-Gramme in unseren N-Grammen, jeweils gewichtet mit λ_i
6. N-Gramme für Rechtschreibung und Aussprache
• Real-Word-Fehler können erkannt und korrigiert werden (vielleicht lieber erst nach Nachfrage!)
7. Entropie & Perplexität
• TODO!!!

• Evaluation, Training und Test Sets
• man "trainiert" die N-Gramme, indem man die Wahrscheinlichkeiten aus einem Trainingskorpus ermittelt
• man "testet" die N-Gramme, indem man prüft, wie gut sie die Gegebenheiten in einem Testkorpus modellieren
• Test- und Trainingssets müssen disjunkt sein! (sonst bekommt man keine Aussage über das generalisierte Wissen im Modell)
• gegebenenfalls Wörter mit gleichem Stamm nur einmal benutzen (bei Buchstaben-N-Grammen)
• Unterteilung des gegebenen Korpus in Training und Test, übliches Verhältnis 90% zu 10%
• cross-validation: mehrfaches Training und Testen jeweils mit unterschiedlichen Stripes (10 Stripes, jeweils einer ist das Test-Set, die anderen das Trainingsset)
• das Verhalten eines Modells hängt im hohen Maße vom Trainingsset ab, es muss jeweils auf "richtigen", das heißt das Problem korrekt beschreibenden Daten trainiert werden 
• ungesehene Wörter müssen berücksichtigt werden (zum Beispiel Einfügung des Worts <unknown> für Wörter die nicht in einem vorgegebenen Lexikon vorkommen
• Evaluation von N-Grammen: Perplexität
• Perplexität ist ein Maß für die Vorhersagequalität eines Modells (ob die Verbesserung einer Komponente sich auch positiv auf das Gesamtsystem auswirkt ist dann immer noch fraglich)
• PP =
• TODO: Abgleich mit Menzels Folien
• Klassenbasierte N-Gramme
1. (siehe Kapitel 8, Seite 316)
• Sprachmodell-Adaption
• Informationstheoretischer Hintergrund
• Cross Entropy

letzte Änderung: 20. August 2006.