SLP Notizen

Teil II
Kapitel 10: Parsing mit CFGs (neues Kapitel 11)

Inhalt

1. Parsen als Suche
• Welcher Syntaxbaum gehört zum Eingabesatz?
• Suche im Raum der Syntaxbäume (die durch die Grammatik generiert werden)
• Top-Down (goal-directed) Suche: S ist die Wurzel des Baumes, dann mal sehen
• Vorteil: alle Hypothesen sind Sätze
• Nachteil: Hypothese passt nicht unbedingt auf die Eingabe
• Bottom-Up (data directed) Suche: die Wörter sind die Blätter des Baumes, ansonsten mal sehen
• Hypothesen sind zur Eingabe kompatibel ergeben aber nicht unbedingt Sätze
• also braucht man vielleicht noch ausgefeiltere Suchstrategien
2. Mehrdeutigkeit
• Mehrdeutigkeit der Wortart (POS-Ambiguity)
• strukturelle Mehrdeutigkeit
• attachment ambiguity: wo gehört die PP hin? "I saw the Eiffel Tower flying to Granada."
• bei Koordination
• lokale Mehrdeutigkeit:
• im Verlauf des Parsens auftretenden Ambiguität, die sich später auflöst ("Die s(S)uche ich")
• es braucht also syntaktische Disambiguierung
• oder: alle möglichen Parses extrahieren und dann später entscheiden, welcher richtig ist
3. Suche mit Ambiguität
• einfacher Ansatz: Agenda und Backtracking
• Effizienzprobleme, da Teilstrukturen mehrfach aufgebaut werden müssen (werden beim Backtracking "vergessen")
• -> Vermeidung von Mehrfacharbeit durch dynamische Programmierung
4. Parsing mit dynamischer Programmierung
• Tabelle wird mit Lösungen zu Teilproblemen aufgefüllt
• kein Mehrfachparsing
• Lösung für Mehrdeutigkeit, da die Tabelle am Ende implizit alle möglichen Parses enthält (Lattice statt Tree)
• Erkenner vs. Parser, für Parser müssen immer noch Herkunftspointer mitgespeichert werden (dabei ist auch mehrfache Herkunft erlaubt)
1. CKY Parser
• benötigt die Grammatik in CNF
• vereinfacht den Algorithmus
• im Anschluss kann der Parse wieder "denormalisiert" werden, falls gewünscht
• dreieckige Matrix (N * N)
• left-to-right, bottom-up
• zunächst nur Erkenner, um Bäume konstruieren zu können, müssen Pointer mitgespeichert werden
2. Earley Parser
• beliebige CFG
• "dotted Rule", Punkt beschreibt, wieviel der Regel schon abgearbeitet/zugeordnet ist
• eindimensionales Feld, (N  + 1)
• left-to-right, top down
• 3 Schritte, die in jedem Feld der Tabelle mit den Einträgen gemacht werden:
1. Predict: wenn nächster Teil der Regel eine Regel ist, dann den entsprechenden Zustand (Regel mit Punkt am Anfang) eintragen
2. Scan: wenn nächster Teil der Regel ein POS ist, prüfen ob das aktuelle Wort passt und gegebenenfalls Regel mit vorgeschobenem Punkt eintragen
3. Complete: bei fertig abgearbeiteten Regeln prüfen, ob eine andere Regel dadurch weiterverarbeitet werden kann und diese entsprechend weiterschieben
• zunächst nur Erkenner
3. Chart Parsing
• Problem mit Earley und CKY: Reihenfolge des Ablaufs ist im Algorithmus jeweils fest vorgegeben und kann nicht beeinflusst werden
• Lösung: Agenda, die die nächsten Zustände zunächst aufnimmt, bevor sie in die Chart eingetragen werden
• Reihenfolge der Agenda kann von außen beeinflusst werden (vgl. A*-Decoding: Reihenfolge hängt von W.keit ab)
• Komplexität: 
• Als Erkenner und zum Füllen der Chart jeweils O(N³)
• um alle (exponentiell viele) Parses zu extrahieren natürlich mehr
• mehrere Parses können auch als Lattice gefaltet weitergegeben werden (schneller)
5. Partial Parsing, Chunking
• TODO
6. Parser auf Basis endlicher Automaten
7. Parsing mit WCDG

letzte Änderung: 12. August 2006.