Parsing und Grammatikformalismen
Die maschinelle Wiederherstellung der grammatischen Struktur von Sätzen: die Grammatikformalismen, die zulässige Strukturen beschreiben, und die Algorithmen, die diese berechnen, von Konstituentenbäumen bis zu Dependenzgraphen.
Definition
Parsing ist die rechnerische Zuweisung einer grammatischen Struktur zu einer Eingabezeichenkette gemäß einer Grammatik; Grammatikformalismen sind die Systeme, die verwendet werden, um festzulegen, welche Strukturen zulässig sind.
Scope
Umfasst die syntaktische Analyse in der Computerlinguistik – kontextfreies Konstituenten-Parsing und seine probabilistischen und Chart-basierten Algorithmen, Dependenz-Parsing, die wichtigsten Grammatikformalismen jenseits einfacher kontextfreier Grammatiken und die Sequenz-Labeling-Aufgaben (wie Part-of-Speech-Tagging), die das Parsing speisen. Ausgeschlossen sind die semantische Interpretation, die in der Computersemantik behandelt wird, und die zugrunde liegende Automatentheorie, die in den Grundlagen behandelt wird.
Sub-topics
Core questions
- Wie kann einem Satz effizient ein syntaktischer Baum oder Dependenzgraph zugewiesen werden?
- Welche Grammatikformalismen erfassen die Syntax natürlicher Sprachen adäquat?
- Wie helfen Wahrscheinlichkeiten, unter vielen möglichen Parses zu disambiguieren?
- Wie unterstützen Tagging und Chunking das vollständige Parsing?
Key concepts
- Konstituenten-Parse
- Dependenz-Parse
- kontextfreie Grammatik
- Chart-Parsing
- probabilistische Grammatik
- Part-of-Speech-Tagging
- Treebank
- strukturelle Ambiguität
Key theories
- Chart-Parsing
- Dynamische Programmieralgorithmen wie CKY und Earley, die alle möglichen Analysen eines Satzes in polynomialer Zeit berechnen, indem sie gemeinsame Teil-Parsings wiederverwenden.
- Probabilistische kontextfreie Grammatiken
- Zuweisung von Wahrscheinlichkeiten zu Grammatikregeln, sodass der wahrscheinlichste Parse ausgewählt werden kann, wodurch die allgegenwärtige strukturelle Ambiguität natürlicher Sprache adressiert wird.
History
Frühes Parsing basierte auf handerstellten Grammatiken und erschöpfender Suche; die CKY- und Earley-Algorithmen machten das kontextfreie Parsing effizient. Die Veröffentlichung von Treebanks in den 1990er Jahren ermöglichte datengesteuertes probabilistisches Parsing, und in den 2000er Jahren gewann das Dependenz-Parsing aufgrund seiner sprachübergreifenden Robustheit an Bedeutung, später abgelöst durch neuronale Parser.
Debates
- Konstituenten- versus Dependenzdarstellung
- Ob Syntax am besten als verschachtelte Phrasen oder als gelabelte Kopf-Dependenz-Beziehungen dargestellt wird; beide sind weit verbreitet, wobei Dependenz für Sprachen mit freier Wortstellung und nachgelagerte Aufgaben bevorzugt wird.
Key figures
- Jay Earley
- Joakim Nivre
- Christopher Manning
- Mitchell Marcus
Related topics
Seminal works
- manning1999
- kubler2009
- jurafsky2025
Frequently asked questions
- Warum ist Parsing schwierig, wenn Grammatikregeln bekannt sind?
- Natürliche Sätze sind massiv mehrdeutig: Eine einzelne Zeichenkette kann viele zulässige Strukturen haben. Parsing muss daher nicht nur Strukturen finden, sondern diese auch rangieren, weshalb probabilistische und gelernte Modelle unerlässlich sind.