Dependenzparsing

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.

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.

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.^[1]

Geschichte

Durch die Verbreitung von Dependenzbaumbanken wurde die Entwicklung von datengetriebenen Parsingverfahren wie dem transitions- und graphbasierten Parsing beschleunigt.^[2][3]

Covington (2001)^[4] und Nivre (2003)^[5] beschreiben zuerst transitionsbasierte Parsingansätze, ein Jahr später kontrastiert Nivre den arc-standard mit dem und arc-eager Transitionsansatz.^[6][7] Kuhlmann u. a. (2011)^[8] kombinieren diese zum arc-hybrid Ansatz.

Ein graph-basiertes Verfahren von Dependenzparsing haben zuerst^[9] McDonald u. a.^[10][11] im Jahr 2005 vorgestellt. Die Idee, eine Kantenfaktorisierung zu nutzen taucht dabei schon etwa zehn Jahre vorher bei Eisner auf.^[12]

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.^[2]

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.^[13]

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.^[3] Auch die HDT wurde konvertiert in deren Format von Dependenzrelationen.^[14]

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^[9] zählte Chan und Manning (2014)^[15] mit einem transitionsbasierten Parser (arc-standard) und Kiperwasser und Goldberg (2016)^[16] 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.^[7]

Der arc-standard Regelsatz zum Beispiel erlaubt drei Parser-Aktionen:^[6][7]

• 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.^[7]

Beispiel

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“.

Schritt	Stapel	Buffer	Nächste Parse-Aktion	Neu erzeugte Relation
0	[root]	[Momo, grüßt, die, Kinder]	SHIFT
1	[root, Momo]	[grüßt, die, Kinder]	SHIFT
2	[root, Momo, grüßt]	[die, Kinder]	LEFT-REDUCEsubj	grüßt ${\displaystyle \xrightarrow {\textit {subj}} }$ Momo
3	[root, grüßt]	[die, Kinder]	SHIFT
4	[root, grüßt, die]	[Kinder]	SHIFT
5	[root, grüßt, die, Kinder]	[]	LEFT-REDUCEdet	Kinder ${\displaystyle \xrightarrow {\textit {det}} }$ die
6	[root, grüßt, Kinder]	[]	RIGHT-REDUCEobj	grüßt ${\displaystyle \xrightarrow {\textit {obj}} }$Kinder
7	[root, grüßt]	[]	RIGHT-REDUCEroot	root ${\displaystyle \xrightarrow {\textit {root}} }$ grüßt
8	[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 Klassifkator trainiert werden, der die Auswahl der Aktion übernimmt.^[7]

Statt gierig (englisch greedy) die beste Parser-Aktion auszuwählen, kann mit Beam-Search auch der aktuelle Parsing-Verlauf bewertet werden.^[7]

Weitere Regelsätze

Neben dem arc-standard Regelsatz, gibt es noch weitere vorgeschlagene Systeme, zum Beispiel arc-eager^[5][6] und arc-hybrid^[8]. Letzteres wurde unter anderem genutzt im neuronalen Parser von Kiperwasser und Goldberg (2016).^[16]

Die drei genannten Regelsätze sind in der folgenden Tabelle noch einmal aufgelistet. Dabei ist ${\displaystyle S}$ der Stapel, ${\displaystyle B}$ der Buffer und ${\displaystyle A}$ die Menge der bisher erzeugten Kanten (englisch arcs). Dass das oberste Element des Stapels das Wort ${\displaystyle i}$ ist, wird als ${\displaystyle S\cdot i}$ notiert, beim Buffer wird das oberste Element ${\displaystyle j}$ hingegen links vom Buffer als ${\displaystyle j\cdot B}$ notiert. Die Schreibweise ist angelehnt an Kuhlmann u. a. (2011).^[8] 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[6]	arc-eager[5][6]	arc-hybrid[8]
${\displaystyle {\begin{aligned}{\textsf {SHIFT}}&\quad \langle S\quad ,i\cdot B,A\rangle \\\vdash &\quad \langle S\cdot i,\quad B,A\rangle \\{\textsf {LEFT-RE}}&\quad \langle S\cdot {\color {green}i}\cdot j,B,A\rangle \\\vdash &\quad \langle S\quad \cdot j,B,A\cup \{j\to {\color {green}i}\}\rangle \\{\textsf {RIGHT-RE}}&\quad \langle S\cdot i\cdot {\color {blue}j},B,A\rangle \\\vdash &\quad \langle S\cdot i\quad ,B,A\cup \{i\to {\color {blue}j}\}\rangle \\\end{aligned}}}$	${\displaystyle {\begin{aligned}{\textsf {SHIFT}}&\quad \langle S\quad ,i\cdot B,A\rangle \\\vdash &\quad \langle S\cdot i,\quad B,A\rangle \\{\textsf {REDUCE}}&\quad \langle S\cdot i,B,A\rangle \\\vdash &\quad \langle S\quad ,B,A\rangle \\&\quad {\text{wenn }}i{\text{ einen Kopf hat}}\\{\textsf {LEFT-ARC}}&\quad \langle S\cdot {\color {green}i},\ j\cdot B,A\rangle \\\vdash &\quad \langle S\quad ,\ j\cdot B,A\cup \{j\to {\color {green}i}\}\rangle \\&\quad {\text{wenn }}{\color {green}i}{\text{ bisher kein Kopf hatte}}\\{\textsf {RIGHT-ARC}}&\quad \langle S\cdot i\quad ,\ {\color {blue}j}\cdot B,A\rangle \\\vdash &\quad \langle S\cdot i\cdot {\color {blue}j},\ \quad B,A\cup \{i\to {\color {blue}j}\}\rangle \\\end{aligned}}}$	${\displaystyle {\begin{aligned}{\textsf {SHIFT}}&\quad \langle S\quad ,i\cdot B,A\rangle \\\vdash &\quad \langle S\cdot i,\quad B,A\rangle \\{\textsf {LEFT}}&\quad \langle S\cdot {\color {green}i}\quad ,\ j\cdot B,A\rangle \\\vdash &\quad \langle S\quad \cdot j,\ \quad B,A\cup \{j\to {\color {green}i}\}\rangle \\{\textsf {RIGHT-ARC}}&\quad \langle S\cdot i\cdot {\color {blue}j},B,A\rangle \\\vdash &\quad \langle S\cdot i\quad ,B,A\cup \{i\to {\color {blue}j}\}\rangle \\\end{aligned}}}$

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.

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.^[17][16]

Bewertung eines Dependenzbaumes

Formal soll der Parsebaum ${\displaystyle {\hat {T}}}$ für Satz ${\displaystyle S}$ vorhergesagt werden, welcher aus allen für den Satz möglichen Dependenzbäumen ${\displaystyle {\mathcal {G}}_{S}}$ derjenige mit dem maximalen Score ist:^[17]

${\displaystyle {\hat {T}}(S)=\arg \max _{t\in {\mathcal {G}}_{S}}{\text{Score}}(t,S)}$

Dieser Score für einen Baum ${\displaystyle t}$ und Satz ${\displaystyle S}$ könnte zum Beispiel die Summe der angenommenen Scores der Kanten sein (Kanten-Faktorisierung):^[17]

${\displaystyle {\text{Score}}(t,S)=\sum _{e\in t}{\text{Score}}(e)}$

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 ${\displaystyle {\text{Score}}\left(e\right)}$ zur Bewertung von Kanten kann statistisch aus Daten gelernt werden, zum Beispiel von einem künstlichen neuronalen Netz. Bei Kiperwasser und Goldberg (2016)^[16] 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

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.^[17][11]

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 sowol Momo als auch Beppo fungiert. Der Score für den gesamten Baum ${\displaystyle {\hat {t}}}$ ist hier also die Summe der Scorewerte der drei gezeigten Kanten:

${\displaystyle {\begin{aligned}{\text{Score}}\left({\hat {t}},S\right)&=\sum _{e\in {\hat {t}}}{\text{Score}}\left(e\right)\\&=10+25+25\\&=60\end{aligned}}}$

Weitere Parsingverfahren

Die Baumstruktur von Dependenzen kann auch zu einer Wortsequenz linearisiert werden, sodass neuronale seq2seq-Ansätze zum Parsing genutzt werden können.^[18]

Neben datengetriebenen Verfahren, wie den transitions- und graphbasierten, können auch Parser auf einer definierten Menge an Regeln (Grammatik) erstellt werden. Ein Nachteil gegenüber den beiden datengetriebenen Verfahren ist, das die Definition von Regeln zeitaufwendig ist und linguistische Expertise verlangt, während die datengetriebenen Parser anhand von Baumbanken ohne explizite Grammatik trainiert werden.^[2] Ein regelbasierter deutscher Parser ist zum Beispiel der CDG Parser von Foth u. a. (2004)^[19], welcher einen Parsebaum erzeugt, der alle vorher definierten Constraints erfüllt.^[2]

Dependenzbaumbanken

Siehe auch: Baumbank (Linguistik)

Um datengetriebene Parser zu trainieren und um Parser generell zu evaluieren, sind Dependenzbaumbanken von zentraler Bedeutung.^[3] Da Dependenzbaumbanken aber mit zum Teil unterschiedlichen Regelwerken und Mengen an Relationstypen erstellt wurden, lassen sich Parser zwischen solchen Baumbanken schwer vergleichen.

Mit über 200.000 Dependenz-annotierten Sätzen ist die 2014 veröffentlichte Hamburg Dependency Treebank (HDT) die bis dahin größte Dependenzbaumbank.^[13] Die Sätze stammen aus Technik-Nachrichten von heise online und wurden mit Wortarten gemäß dem Stuttgart-Tübingen Tag Set annotiert.^[13] Die in der HDT zu findenden Dependenzbäume basieren auf einer eigens entwickelten Constraint-Dependenzgrammatik des Deutschen.^[13][20] Ein paar Jahre danach wurden die Bäume in das Format universeller Dependenzrelationen konvertiert.^[14] Die HDT enthält über drei Millionen syntaktisch annotierte Tokens.^[21]

Eine weitere große Dependenzbaumbank ist die Prague Dependency Treebank (PDT) für die tschechische Sprache, wie auch Deutsch eine Sprache mit freierer Wortfolge als Englisch. Die Baumbank enthält nicht nur mittlerweile über zwei Millionen syntaktisch annotierten Tokens, sondern darüber hinaus auch weitere linguistische Annotationen, zum Beispiel zur Morphologie.^[22][23] Für die Dependenzrelationen kommt ein eigenes Format zur Anwendung.^[24][25] Die PDT lieferte die Vorlage für weitere Projekte zur Erstellung von Dependenzbaumbanken für slawische Sprachen.^[22][2]

Im Rahmen des Projektes Universal Dependencies werden immer weitere Baumbanken für unterschiedlichste Sprachen einheitlich mit universellen Dependenzrelationen veröffentlicht. Wie auch der Projektwebseite zu entnehmen ist, sind mittlerweile deutlich über 100 Sprachen mit über 200 Baumbanken vertreten.^[26]

Neben Baumbanken, die direkt aus der Annotation von Sätzen mit Dependenzbäumen entstanden sind wie die HDT, sind auch Konvertierungen von Phrasenstruktur- oder Konstituenten-Baumbanken in Dependenzbaumbanken möglich. Hierzu müssen jeweils die Köpfe der Phrasen markiert werden.^[2]

Ein verbreitetes Format zur Speicherung von linguistischen Dependenzbaumbanken ist das CoNLL-Format und davon abgleitete Varianten, benannt nach der Conference on Computational Natural Language Learning, welche es einführte. Auch Universal Dependencies verwendet ein darauf basierendes Format namens CoNLL-U.^[27] Pro Zeile werden Attribute zu einem Wort in Spalten gespeichert, dazu zählen neben der Position im Satz (Index) und dem Wort selbst, gegebenenfalls weitere morphologische sowie Wortart-Informationen, auch die Art der Dependenzrelation und der Kopf dieses Wortes (genauer dessen Index im Satz).^[28]

Evaluation

Zur Evaluation von Dependenzparsern wird üblicherweise die Vorhersage des Parsers mit dem in der Baumbank als Referenz hinterlegten Dependenzbaum verglichen.

Standardmetriken für die Evaluation von syntaktischen Dependenzparsern sind Unlabelled Attachment Score (UAS) und Labelled Attachment Score (LAS). Der labelled attachment score beschreibt, für wie viel Prozent der Wörter sowohl der Kopf der Dependenzrelation als auch die Art der Dependenzrelation (das Kanten-Label) korrekt vorhergesagt wurden. Beim unlabelled attachment score hingegen ist das Label irrelevant und es zählt nur, für wie viel Prozent der Wörter der richtige Kopf vorhergesagt wurde.^[2][29][28] Außerdem gibt es noch den label accuracy score (LS), welcher den Anteil der Worte (Dependenten) mit dem korrekten Label unabhängig vom Kopf wiedergibt.^[29] Interpunktion zählt hierbei manchmal mit oder wird ignoriert.^[28][30][31]

${\displaystyle {\begin{aligned}LAS&={\frac {\text{Wörter mit korrektem Kopf und korrektem Relationstyp}}{\text{Anzahl Wörter}}}\\UAS&={\frac {\text{Wörter mit korrektem Kopf}}{\text{Anzahl Wörter}}}\\LS&={\frac {\text{Wörter mit korrektem Relationstyp}}{\text{Anzahl Wörter}}}\end{aligned}}}$

Um einen detaillierteren Blick auf die Performanz des Parsers per Relationstyp zu haben, können Genauigkeit (englisch Precision) und Trefferquote (englisch Recall) je Relationstyp berechnet (vergleiche Precision und Recall), sowie eine Konfusionsmatrix verwendet werden.^[29]

Eine weitere mögliche Metrik wäre Exact Match (EM, deutsch: exakte Übereinstimmung), also wie oft der Parsebaum exakt der Referenz entspricht. Dies würde aber Teilerfolge, wenn etwa alle bis auf eine Relation korrekt vorhergesagt wurden, nicht würdigen, und ist daher für den Entwicklungsprozess weniger geeignet.^[29] Ähnlich wie bei der Unterscheidung von UAS und LAS kann auch hier entweder der Dependenzbaum inklusive oder exklusive Kanten-Label betrachtet werden.

Für Universal Dependencies wurden auch weitere Metriken postuliert, die zusätzlich morphologische Merkmale miteinbeziehen.^[31]

Zusätzlich zur Qualität der Parsing-Vorhersage kann auch die Geschwindigkeit des Parsers allgemein und bei länger werdenden Sätzen im Besonderen zum Vergleich herangezogen werden.^[30] Je länger die zu parsenden Sätze sind, desto mehr Dependenzrelationen muss ein Parser vorhersagen. Das steigert nicht nur die Anzahl möglicher falscher Vorhersagen, sondern auch die Dauer des Parsingvorgangs. Trägt man die Länge der Sätze gegenüber der Parsinggeschwindigkeit als auch der -genauigkeit (beispielsweise UAS) auf, ist deshalb ein abnehmender Trend zu erwarten.

Auch die (Nicht)-Projektivität kann einen Einfluss auf die Parsinggenauigkeit haben.

Projektivität und asymptotische Zeitkomplexität

Bei syntaktischen Dependenzbäumen wird zwischen projektiven und nicht-projektiven Bäumen unterschieden. Dies hat Einfluss darauf, welche Verfahren zum Parsing geeignet sind und wie viel Zeit das Parsing im schlechtmöglichsten Fall benötigt.

(Nicht-)Projektivität

Gerade in Sprachen mit freierer Wortstellung können nicht-projektive Bäume häufiger vorkommen.^[3] So machen nicht-projektive Sätze in der deutschen Baumbank HDT etwa 12 Prozent aller Bäume aus.^[13]

Zwei Darstellungen (a,b) der Dependenzrelationen für den Teilsatz dass sich die Leute unterhalten wollen mit einer nicht-projektiven Relation. Die Kante zwischen den Wörtern sich und unterhalten ist nicht-projektiv; sie kreuzt die gepunkteten Linien von den dazwischen stehenden Wörtern die und Leute.

Ein Baum ist projektiv, wenn alle seine Kanten (Dependenzrelationen) projektiv sind. Er ist demnach nicht-projektiv, wenn mindestens eine Relation nicht-projektiv ist. Eine Relation wiederum ist projektiv, wenn für jedes Wort, das in der Wortfolge im Satz zwischen Kopf und Dependent der Relation liegt, über einen Pfad vom Kopf der Relation erreicht werden kann.^[3] In dem in der nebenstehenden Abbildung dargestellten Beispiel ist die Kante zwischen den Wörtern unterhalten und sich nicht-projektiv, da es keinen Pfad vom Kopf unterhalten zu den Worten die oder Leute gibt, welche im Satz zwischen Kopf und Dependent liegen.

Manche Parsing-Verfahren können nur projektive Dependenzbäume erzeugen, scheitern ohne entsprechende Anpassungen^[32] also an nicht-projektiven Sätzen.^[3] Anders als viele transitionsbasierte Ansätze, sind graphbasierte Verfahren generell in der Lage auch nicht-projektive Bäume zu erzeugen.^[17]

Dependenzbäume, die über Kopf-Findungsregeln automatisch aus Phrasenstruktur-Baumbanken erzeugt wurden, sind immer projektiv.^[3]

Parsing-Komplexität im schlechtesten Fall

Die asymptotische Zeitkomplexität beim Parsing kann im Verhältnis zur Länge des Satzes (Anzahl der Wörter) ${\displaystyle n}$ angegeben werden, hierfür wird die Groß-O-Notation (siehe auch Komplexitätstheorie: Landau-Notation) verwendet: ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$ bedeutet beispielsweise, dass mit einem Parseverfahren Sätze der Länge ${\displaystyle n}$ im schlechtesten Fall in kubischer Zeit geparst werden können. Für das Parsen von kontextfreie Sprachen lässt sich eine asymptotische Laufzeit von ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$ feststellen (siehe auch CYK-Algorithmus). Durch das Erlauben von Nicht-Projektivität bei Dependenzbäumen landen wir aber in der Chomsky-Hierarchie im Bereich der schwach kontextsensitiven Sprachen, für die die Parsing-Komplexität bei Polynomen höherer Ordnung als drei liegt.^[33]

Literatur

• Ines Rehbein: Der Einfluss der Dependenzgrammatik auf die Computerlinguistik. In: Zeitschrift für germanistische Linguistik. Band 38, Nr. 2, September 2010, ISSN 0301-3294, S. 224–248, doi:10.1515/zgl.2010.015 (bsz-bw.de [PDF; abgerufen am 21. Juni 2025]).
• Daniel Jurafsky, James H. Martin: Speech and Language Processing. 3. Auflage (Entwurf). Abgerufen am 21. Juni 2025 (englisch, Entwurf vom 12. Januar 2025). Speziell Kapitel 19 „Dependency Parsing“.
• Sandra Kübler, Ryan McDonald, Joakim Nivre: Dependency Parsing. In: Graeme Hirst (Hrsg.): Synthesis Lectures on Human Language Technologies. Morgan & Claypool, 2009, ISSN 1947-4040, doi:10.1007/978-3-031-02131-2 (englisch, springer.com [abgerufen am 22. Juni 2025]).
• Günter Neumann: Einführung in die Dependenzgrammatik. LT lab, DFKI. Universität Saarland, 2. Juli 2013

Weblinks

• Hamburg Dependency Treebank (englisch)
• Universal Dependencies (englisch)
• Visualisierung
  • displaCy Dependency Visualizer (englisch): parst und visualisiert Sätze. Geparst wird mit Modellen von spaCy.
  • Download des MaltEval Tools (englisch) zur Visualisierung von Dependenzbäumen und zur Evaluierung von Dependenzparsern. Das MaltEval Tool wurde wissenschaftlich publiziert.^[34]