mini|359x359px|Ergebnis eines syntaktischen Dependenzparsings ist ein Dependenzbaum, wie der hier für den englischen Satz „Peter and Mary bought a car“ (übersetzt ‚Peter und Mary kauften ein Auto‘) gezeigte. Die Eingabe des Parsings war nur der Satz selbst. Dependenzparsing beschreibt in der Computerlinguistik den Vorgang, Äußerungen mit Dependenzbäumen zu versehen, die die syntaktische Struktur derselben Äußerungen widerspiegeln. Grundlage hierfür kann eine manuell erstellte Dependenzgrammatik oder auch eine statistisch (datengetrieben) aus einer Baumbank gelernte implizite Grammatik sein. Die Verfahren zum Parsing von Dependenzbäumen unterscheiden sich zum Teil von denen, die beim Konstituentenparsing verwendet werden.
Eingabe eines Parsers für Dependenzen ist ein Satz oder Phrase in natürlicher Sprache. Die Ausgabe des Dependenzparsers ist ein zu der Eingabe passender Dependenzbaum. Dieser Baum besteht aus Dependenzrelationen (auch Kanten oder Dependenzen genannt) zwischen Paaren von Wörtern. Jeweils ein Wort in der Relation gilt als Kopf, das andere als Dependent. Grafisch wird das meist durch eine gerichtete Kante vom Kopf hin zum Dependenten dargestellt. Diese Kanten sind üblicherweise auch mit einem Label versehen, das die syntaktische Beziehung der Wörter näher beschreibt, beispielsweise die Relation eines Nomens als Subjekt zu einem Verb oder die eines Artikels als Determinierer eines Nomens.
Neben dem syntaktischen Parsing findet auch im Bereich semantisches Parsing (Semantic Parsing) Dependenzparsing eine Anwendung, sofern die jeweils zugrunde gelegte Bedeutungsrepräsentation als Dependenzgraph beschrieben werden kann.
Geschichte
Durch die Verbreitung von Dependenzbaumbanken wurde die Entwicklung von datengetriebenen Parsingverfahren wie dem transitions- und graphbasierten Parsing beschleunigt.Vgl. Rehbein 2010Vgl. Jurafsky & Martin (2025) Abschnitt 19.1 „Dependency Relations“
Covington (2001) und Nivre (2003) beschreiben zuerst transitionsbasierte Parsingansätze, ein Jahr später kontrastiert Nivre den arc-standard mit dem und arc-eager Transitionsansatz.Jurafsky & Martin (2025), Abschnitt 19.2 „Transition-based dependency parsing“ Kuhlmann u. a. (2011) kombinieren diese zum arc-hybrid Ansatz.
Ein graph-basiertes Verfahren von Dependenzparsing haben zuerstVgl. Jurafsky & Martin (2025) Abschnitt „Bibliographical and historical notes“ McDonald u. a. im Jahr 2005 vorgestellt. Die Idee, eine Kantenfaktorisierung zu nutzen taucht dabei schon etwa zehn Jahre vorher bei Eisner auf.
Um datengetriebene Dependenzparser zu vergleichen, fanden in den Jahren 2006 und 2007 zwei shared tasks der CoNLL (Conference on Computational Natural Language Learning) statt. In diesen Forschungswettbewerben wurden die eingereichten Systeme auf einem einheitlichen Datensatz und nach einheitlicher Evaluationsmethode getestet und miteinander verglichen. Hierbei zeigte sich, dass manche der im Datensatz vorhandenen Sprachen schwieriger zu parsen waren als andere.
Mit der Hamburg Dependency Treebank (HDT) wurde 2014 die bis dahin größte Dependenzbaumbank veröffentlicht, mit Dependenzbäumen für über 200.000 deutsche Sätze.
Das Universal Dependencies Projekt führte ein gleichnamiges Schema für Dependenzrelationen (Universelle Dependenzrelationen, UD) ein. Mit Baumbanken in über 100 Sprachen ermöglicht das Projekt multilinguales Parsing in großem Stil. Auch die HDT wurde konvertiert in deren Format von Dependenzrelationen.
Seit dem Aufkommen von künstlichen neuronalen Netzen in der Computerlinguistik und dem Natural Language Processing werden auch zum statistischen Dependenzparsing solche Netze genutzt. Zu den ersten neuronalen Dependenzparsern zählte Chan und Manning (2014) mit einem transitionsbasierten Parser (arc-standard) und Kiperwasser und Goldberg (2016) mit einem transitions- (arc-hybrid) und einem graphbasierten Parser, welche auf bidirektionalen LSTMs basierten.
Verfahren
Transitionsbasiertes Parsing Transitionsbasiertes Parsing ähnelt dem Shift-Reduce-Parsing für kontextfreie Grammatiken (siehe Bottom-up-parsing): auch hier gibt es einen Stapel (englisch stack) und einen Eingabespeicher (englisch buffer). Der Satz wird von links nach rechts abgearbeitet, indem nacheinander basierend auf dem aktuellen Zustand eine Regel (Parser-Aktion) ausgewählt und ausgeführt wird, um einen neuen Parsingzustand (auch Konfiguration genannt) herbeizuführen.
Der arc-standard Regelsatz zum Beispiel erlaubt drei Parser-Aktionen:
SHIFT: schiebt das oberste Wort vom Buffer auf den Stapel. LEFT-REDUCE: erzeugt eine Dependenzrelation vom obersten Wort des Stapels zum zweitobersten Wort des Stapels. Das zweitoberste Wort wird vom Stapel gelöscht. RIGHT-REDUCE: erzeugt eine Dependenzrelation vom zweitobersten Wort des Stapels zum obersten Wort des Stapels. Das oberste Wort wird vom Stapel gelöscht.
Am Anfang des Parsings ist der Stapel bis auf ein spezielles Wurzel-Symbol (englisch root) leer und der Buffer enthält alle Worte des Satzes. Nun wird wiederholt eine Parser-Aktion ausgewählt und ausgeführt, sodass Stapel oder Buffer verändert werden. Ziel ist es, dass alle Wörter vom Buffer gelöscht und verarbeitet werden konnten und auf dem Stapel nur noch das Wurzelsymbol verbleibt.
Beispiel mini|277x277px|Dependenzbaum für den Satz „Momo grüßt die Kinder“ mit Hilfsknoten root, um die Wurzel des Dependenzbaums zu markieren.
Für den Satz „Momo grüßt die Kinder“ führt die in der nachfolgenden Tabelle angegebene Schrittfolge von Parser-Aktionen zum gewünschten Dependenzbaum.
Dabei erzeugt LEFT-REDUCE Dependenzrelationen, die im Baum von rechts nach links zeigen. Im Beispiel sind das die Subjekt-Relation (subj) zwischen Momo als Dependent und grüßt als Kopf, sowie die Determinierer-Relation (det) zwischen die und Kinder. Analog erzeugen RIGHT-REDUCE Aktionen Relationen, die im Baum von links nach rechts zeigen. In diesem Beispiel die Objekt-Relation (obj) zwischen grüßt und Kinder, sowie die spezielle Wurzelmarkierung von grüßt als Wurzel des Dependenzbaumes.
Wird in einem Schritt eine neue Dependenzrelation erzeugt zwischen zwei Worten, muss auch die Art der syntaktischen Abhängigkeit (zum Beispiel subj für die Kante zwischen Momo und grüßt) mit angegeben werden.
+Abfolge von Parsing-Schritten mit dem arc-standard System für den Satz „Momo grüßt die Kinder“.SchrittStapelBufferNächste Parse-AktionNeu erzeugte Relation0[root][Momo, grüßt, die, Kinder]SHIFT1[root, Momo][grüßt, die, Kinder]SHIFT2[root, Momo, grüßt][die, Kinder]LEFT-REDUCEsubjgrüßt Momo3[root, grüßt][die, Kinder]SHIFT4[root, grüßt, die][Kinder]SHIFT5[root, grüßt, die, Kinder][]LEFT-REDUCEdetKinder die6[root, grüßt, Kinder][]RIGHT-REDUCEobjgrüßt Kinder7[root, grüßt][]RIGHT-REDUCErootroot grüßt8[root][]Fertig
Auswahl der Parser-Aktion Ein transitionsbasierter Parser muss in jedem neu entstandenen Parsing-Zustand eine Entscheidung treffen, welche Parser-Aktion als Nächstes angewandt werden sollte. Um die beste Parser-Aktion zu bestimmen, kann mittels traditioneller maschineller Lernverfahren oder künstlicher neuronaler Netze ein Klassifikator trainiert werden, der die Auswahl der Aktion übernimmt.
Statt gierig (englisch greedy) die beste Parser-Aktion auszuwählen, kann mit Beam-Search auch der aktuelle Parsing-Verlauf bewertet werden.
Weitere Regelsätze Neben dem arc-standard Regelsatz, gibt es noch weitere vorgeschlagene Systeme, zum Beispiel arc-eager und arc-hybrid. Letzteres wurde unter anderem genutzt im neuronalen Parser von Kiperwasser und Goldberg (2016).
Die drei genannten Regelsätze sind in der folgenden Tabelle noch einmal aufgelistet. Dabei ist der Stapel, der Buffer und die Menge der bisher erzeugten Kanten (englisch arcs). Dass das oberste Element des Stapels das Wort ist, wird als notiert, beim Buffer wird das oberste Element hingegen links vom Buffer als notiert. Die Schreibweise ist angelehnt an Kuhlmann u. a. (2011). Die Farbe einzelner Elemente hat keine Bedeutung und soll lediglich die Übersichtlichkeit unterstützen. +Erlaubte Parser-Aktionen für drei Transitionssysteme im Vergleich. arc-standard arc-eager arc-hybrid
Graphbasiertes Parsing Beim graphbasierten Parsing wird nach demjenigen Dependenzbaum gesucht, der einen bestimmen Wert (englisch Score) maximiert. Der Name graphbasiertes Parsing signalisiert die Verbindung zur Graphentheorie, denn laut dieser ist ein Baum eine spezielle Unterart von Graphen.
mini|221x221px|Nahezu vollständig verbundener, gerichteter Graph mit einem Gewichtswert an jeder Kante. Die Knoten sind die Wörter des Satzes „Momo winkt Beppo“ plus ein spezieller Wurzel-Knoten (root).
Wenn man also alle möglichen Dependenzen (Kanten) zwischen den Wörtern des Satzes (Knoten) betrachtet, gilt es die bestmöglichen auszuwählen, die zusammen eine Dependenzstruktur erzeugen. Für den Beispielsatz „Momo winkt Beppo“ zeigt der Graph in der nebenstehenden Abbildung alle möglichen gerichteten Kanten (zu den Zahlen an den Kanten gleich mehr) zwischen den Wörtern als Knoten. Wie auch beim transitionsbasierten Parsing wird hier ein Hilfswort als zusätzlicher Knoten ergänzt, mit dem später die Wurzel des Baumes markiert werden soll.
Um das Problem, den besten Baum zu finden, zu vereinfachen, können zuerst die Relationstypen (Labels) weggelassen werden. Nachdem der beste Baum gefunden ist, können dann in einem zweiten Schritt für dessen Relationen das jeweilig beste Label ermittelt werden.Vgl. Jurafsky & Martin (2025) Abschnitt 19.3 „Graph-based dependency parsing“
Bewertung eines Dependenzbaumes Formal soll der Parsebaum für Satz vorhergesagt werden, welcher aus allen für den Satz möglichen Dependenzbäumen derjenige mit dem maximalen Score ist:
Dieser Score für einen Baum und Satz könnte zum Beispiel die Summe der angenommenen Scores der Kanten sein (Kanten-Faktorisierung):
Also müssen alle möglichen Kanten zwischen Wortpaaren bewertet werden. Das Ergebnis einer Bewertung aller Kanten könnte für den Beispielsatz „Momo winkt Beppo“ wie in der bereits oben genannten Abbildung gezeigt aussehen: Zum Beispiel erhält die Kante von winkt nach Momo einen Score von 25, während die Kante der Gegenrichtung von Momo nach winkt nur einen Score von 11 erhält.
Die Funktion zur Bewertung von Kanten kann statistisch aus Daten gelernt werden, zum Beispiel von einem künstlichen neuronalen Netz. Bei Kiperwasser und Goldberg (2016) zum Beispiel werden hierzu BiLSTM-Repräsentationen der beiden Worte durch ein Multi-Layer-Perzeptron geschleust, um einen Kantenwert für das Wortpaar zu berechnen.
Finden des besten Dependenzbaumes anhand der Bewertungen mini|Linguistisch sinnvoller Dependenzbaum für den Satz „Momo winkt Beppo“ mit den höchsten Gewichten an den Kanten als mögliche Ausgabe des Chu-Liu-Edmonds-Algorithmus.
Um den besten Dependenzbaum gemäß der Bewertungsfunktion zu finden, lässt sich der Chu-Liu-Edmonds-Algorithmus aus dem Bereich der Graphentheorie einsetzen. In diesem Algorithmus werden die best-bewertesten Kanten ausgewählt, aber auch darauf geachtet, dass der resultierende Graph die Eigenschaften eines Dependenzbaums erfüllt, der alle Worte abdeckt.
Die Eingabe des Algorithmus ist also ein Graph, in welchem alle Knoten (Wörter) über gerichtete Kanten miteinander verbunden sind. Ein solcher wurde bereits oben für den Beispielsatz „Momo winkt Beppo“ gezeigt. Diese Kanten tragen jeweils ein Gewicht, den Score dieser Kante.
Die Ausgabe des Algorithmus ist ein Dependenzbaum mit den bestmöglichen Kantengewichten, der idealerweise auch linguistisch sinnvoll ist. Für das Beispiel „Momo winkt Beppo“ zeigt nebenstehende Abbildung das Ergebnis des Algorithmus: als Wurzel wurde das Wort winkt bestimmt, welches wiederum als Kopf für sowohl Momo als auch Beppo fungiert. Der Score für den gesamten Baum ist hier also die Summe der Scorewerte der drei gezeigten Kanten:
Weitere Parsingverfahren