Konstituenten- und kontextfreies Parsing

Berechnung des Phrasenstrukturbaums eines Satzes unter Verwendung kontextfreier Grammatiken, dynamischer Programmieralgorithmen wie CKY und Earley sowie probabilistischer Grammatiken zur Auflösung von Ambiguitäten.

Definition

Das Konstituenten-Parsing weist einem Satz gemäß einer kontextfreien Grammatik einen verschachtelten Phrasenstrukturbaum zu, wobei typischerweise der wahrscheinlichste Baum unter einer probabilistischen Grammatik ausgewählt wird.

Scope

Behandelt das Parsing mit kontextfreien Grammatiken: die CKY- und Earley-Algorithmen, die Chomsky-Normalform, probabilistische kontextfreie Grammatiken und deren lexikalisierte Verfeinerungen sowie mit Treebanks trainierte statistische Parser. Es befasst sich mit der Ambiguitätsauflösung und der Evaluierung von Parsern. Dependenzdarstellungen und nicht-kontextfreie Formalismen werden in verwandten Themen behandelt.

Core questions

• Wie parst der CKY-Algorithmus einen Satz in kubischer Zeit?
• Warum müssen Grammatiken oft zuerst in die Chomsky-Normalform konvertiert werden?
• Wie verbessern probabilistische und lexikalisierte Grammatiken die Disambiguierung?
• Wie wird die Parser-Genauigkeit anhand einer Treebank gemessen?

Key concepts

• kontextfreie Grammatik
• CKY-Algorithmus
• Earley-Algorithmus
• Chomsky-Normalform
• probabilistische kontextfreie Grammatik
• Lexikalisierung
• Ableitungsbaum
• Treebank

Key theories

Dynamisches Programmier-Parsing

Die CKY- und Earley-Algorithmen berechnen alle Parses in polynomialer Zeit, indem sie eine Tabelle von Unterkonstituenten füllen, wodurch die exponentielle Explosion der naiven Suche vermieden wird.

Lexikalisiertes probabilistisches Parsing

Die Konditionierung von Regelwahrscheinlichkeiten auf Kopfwörter verbessert die Parsing-Genauigkeit erheblich, indem lexikalische Präferenzen erfasst werden, die in einfachen PCFGs nicht vorhanden sind.

History

Der CKY-Algorithmus (1960er Jahre) und Earleys Algorithmus von 1970 ermöglichten eine effiziente kontextfreie Erkennung. Mit der Penn Treebank erreichten probabilistische und später lexikalisierte Parser von Collins und Charniak Ende der 1990er Jahre eine hohe Genauigkeit, was die Ära des statistischen Parsings vor den neuronalen Modellen prägte.

Debates

Wie viel Lexikalisierung ist notwendig?

Lexikalisierte Parser sind genau, aber spärlich; die Debatte drehte sich darum, ob unlexikalisierte PCFGs mit sorgfältiger Zustandsaufteilung mithalten könnten, was spätere Arbeiten teilweise als möglich erwiesen.

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

Was ist ein Chart im Parsing?

Ein Chart ist eine Tabelle, die jede gefundene partielle Konstituente über jede Spanne des Satzes speichert, sodass gemeinsame Unterstrukturen einmal berechnet und wiederverwendet werden, was ein Parsing in polynomialer Zeit ermöglicht.