SLP Notizen

Teil I
Kapitel 5: statistische Modelle für Aussprache und Rechtschreibung

Inhalt

1. Schreibfehler behandeln
• OCR
• Handschrifterkennung
• Tippfehler
2. Schreibfehler-Muster
• mechanisch:
• Einfügung (Sonderfall: Dopplung): Peterr
• Auslassung: eter
• Ersetzung: Petet
• Vertauschung: Epter
• (Tastaturverschiebung: Pwrwe)
• kognitiv: "Fehla"
• OCR: ähnlich aussehende Buchstaben, häufig Buchstaben vs. Buchstabenpaare: m <-> rn
• confusion-matrix: enthält Verwechslungswahrscheinlichkeiten zwischen den Buchstaben
• lernen anhand von annotiertem Korpus
3. Nicht-Wort-Fehler erkennen
• 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)
• häufig sehr stark übergenerierende Automaten, riesige Lexika. 
• es hat sich gezeigt, dass größere Lexika im Vorteil sind
• 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
4. Wahrscheinlichkeitsmodelle: das Modell des verrauschten Kanals
• Informationstheorie:
• Quelle sendet Signal
• Kanal transformiert (verrauscht/verzerrt/whatever) das Signal
• Senke interpretiert Signal: "Was wollte mir Q damit sagen?"
• Ziel: schätzen des ursprünglichen Signals
• Mittel: Wissen über den Kanal und das Signal (also Echokompensation oder N-Gramme)
• Algorithmus: Bayes'sche Inferenz: ŵ = argmax_{w ∈ V} P(w|O)
• Bayes'sche Regel: P(x|y) = (P(y|x) × P(x)) / P(y)
• argmax kürzt den Nenner heraus, daher: ŵ = argmax_{w ∈ V} P(O|w) × P(w)
• P(w): a priori-Wahrscheinlichkeit
• P(O|w): a posteriori-Wahrscheinlichkeit
5. Anwendung der Bayes'schen Methode auf die Rechtschreibung
• TODO
6. 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)
7. Varianz in englischer Aussprache
• lexikalische Variation (Schrippe, Rundstück, Brötchen, Bemme, ...)
• allophonische Variation
• regional/dialektal ([rʊndstʏk]  vs. [rʊndʃtʏk])
• soziolinguistisch
• Reduktion: weglassen, verschleifen, zentralisieren von Lauten
8. Anwendung der Bayes'schen Methode auf Aussprache
• Entscheidungsbäume für Aussprachevarianz
9. gewichtete Automaten (= Markov-Ketten)
• hier: Moore-Automaten (emitiertes Symbol hängt nur vom Zustand ab, nicht vom Übergang)
• jeweils ein nicht-emittierender Start- und Endzustand
• Übergangswahrscheinlichkeiten (summieren zu 1)
1. Forwärts-Algorithmus
• berechnet die Emissionswahrscheinlichkeit des Modells bei gegebener Symbolfolge
• P(O|λ)
• summiert über alle möglichen Pfade im Modell
• W.keit eines Pfades forward[t, j] ist die Summe der Produkte möglichen Teilpfade mit Ziel i aus
• W.keit des Teilpfades bis zum letzten Zustand (forward[t-1, i])
• Übergangsw.keit vom letzten zum jetzigen Zustand (a_ij)
• Ausgabewahrscheinlichkeit/observation likelihood b_jt 
• hier zunächst binär. bei echten HMMs reellwertig
2. Viterbi-Algorithmus
• berechnet den wahrscheinlichsten Pfad durch ein Modell
• berücksichtigt also nicht den ähnlichen, nur ein kleinwenig schlechteren Pfad
• P(s|O, λ)
• Berechnung wie Forwärts-Algorithmus, nur wird jeweils das Maximum statt der Summe gewählt
• ein Backpointer wird mitgespeichert, damit später der Pfad rekonstruiert werden kann
• Anwendung: 
• die Wörter werden über ihre Start-/Endzustände aneinandergebunden (mit N-Gramm-Übergangswahrscheinlichkeiten)
• der wahrscheinlichste Pfad läuft durch die "korrekten" Wörter (aber nicht die wahrscheinlichsten!)
• Vorteil: es muss nicht für jedes Wort ein eigenes Modell getestet werden, sondern nur ein großes
• das kann besser gepruned werden, bzw. bei Suchstrategien werden wahrscheinliche bevorzugt
• Nachteil: "ähnliche" Pfade werden nicht mehr summiert
10. 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
• gesprochene Sprache kennt keine Wortgrenzen
• gewichtete Automaten und Segmentierung
• TODO

letzte Änderung: 19. August 2006.