Universität des Saarlandes
FB 8.7 Computerlinguistik
Seminar Dependenzgrammatiken
Prof. Hans Uszkoreit, Karel Oliva

Towards an implementable dependency grammar

Vorgetragen am 17.6.1999 von
Ronald Bieber, robi@coli.uni-sb.de

Basiert auf dem gleichnamigen Paper von
Timo Järvinen und Pasi Tapanainen
Research Unit for Multilingual Language Technology
University of Helsinki, Finnland
Aus den Proceedings der CoLing-ACL'98 in Montreal

Zielsetzungen des Papers

• Erstes Ziel: Der entwickelte Formalismus soll linguistisch adäquat sein, da Mängel in diesem Punkt das Resultat weniger brauchbar machen würden und Verbesserungen im Verständnis des Themas nicht möglich wären.
• Zweites Ziel: Der entwickelte Formalismus soll sich praktisch verwenden lassen, er soll parsbar sein.
• Der Formalismus soll außerdem einer Reihe von formalen Kriterien genügen.
• Exemplarisch werden am Ende einige Aspekte behandelt, mit denen sich jedes System mit Breitenabdeckung befassen muss.

Grundsätzliche Probleme der Vergangenheit

• Grammatische Modelle wurden zuerst von Linguisten ohne Beachtung von Notwendigkeiten der Implementierung entwickelt, dadurch waren die entstandenen Modelle schlecht implementierbar.
• Spätere Modelle wurden von Informatikern entwickelt, die von einem handhabbaren mathematischen Modell ausgingen und dann die Linguistik einzupassen versuchten, was jedoch aufgrund der dabei oft eingeführten (linguistischen) Beschränkungen im Resultat nicht zufriedenstellend war.
• Beispiel: In Systemen der 60er wurden oft einfache mathematische Modelle verwendet, und um deren Abdeckung zu erweitern wurden ad-hoc Lösungen ohne theoretische Basis entwickelt.
• Neuerdings Ansätze mit linguistischer Basis, aber selbst Hudson verwendet einige Annahmen, die eher einem mathematischen Modell entspringen (z.B. "x+1"?).

Ansatz dieses Papers:

• Ein Mittelweg zwischen den beiden Wegen soll beschritten werden.
• Beispielsweise soll das Modell nicht beschränkt sein durch das Modell der Kontext-freien Grammatiken.
• Behauptung: Obwohl man sich damit in den Bereich der (theoretisch) NP-harten Probleme begibt, lässt sich der Formalismus in der Praxis parsen. Zur Zeit der Abfassung des Papers existierte eine Implementation füer das Englische mit einiger Parsgeschwindigkeit von mehreren hundert Wörtern pro Sekunde.

Der Europäische Strukturalismus

• Die Arbeit bezieht sich stark auf die Arbeit von Tesnière.
• Sein empirischer Ansatz wird in den mehr als 60 Sprachen aus denen Beispiele stammen deutlich, auch wenn diese Beispiele vor allem exemplarisch genutzt wurden und nicht etwa die Theorie hierraus induziert wurde.
• Obwohl sein Ansatz nicht formell ist, scheinen keine Einschränkungen der Beschreibung erkennbar.

Konstituenten vs Dependenz

• Problem aller Konstituentenformalismen: Unzusammenhängende Elemente.
• Lösungsansatz von Wells (1947), nimmt an, dass syntaktische Struktur und semantische Interpretation kompatibel sind.
• Schwammiger Grund für Ablehnung der KGs:
  Formale Eigenschaften für adäquate Konstituenten-basierte Grammatiken sind unbekannt.

Oberflächensyntax

• Parallelität zwischen Syntax und Semantik.
• Bei Entscheidung zwischen verschiedenen syntaktischen Konstruktionen wird semantisch motivierte Variante gewählt.
  Beispiel: "I asked John to go home", John wird (aufgrund der Semantik) eher als Subject des erweiterten Infinitivs klassifiziert und nicht als Komplement von asked.
• Praktisches Problem: Wie bildet man die syntaktische Struktur?
• Umdefinierungen zum Erreichen der Parsbarkeit sollten immer linguistisch motiviert sein und nicht als Einschränkung des Modells resultieren.

Parallelität Syntax - Sematik

• Syntaktische Beschreibungen sollten kompatibel sein mit semantischer Interpretation.
• Aber: Wenn der Zusammenhang so groß ist, warum sollte man diese Ebenen überhaupt trennen?
• Sgall beispielsweise möchte die Wortreihenfolge der Morphologie zuschlagen und die Syntax der Semantik trennen.
• Mel'cuk aber bringt Beispiele, bei denen unterschiedliche morphologische Abhängigkeiten in verschiedenen Sprachen existieren.
  Beispiel: professor's book. Russisch: "kniga professor+a", Ungarisch: "Professzor könyw+e". Die Morphologische Abhängigkeit ist also nicht mit der syntaktischen Abhängigkeit identisch.
• Ein weiterer Beleg ist die Intuition, dass syntaktische Strukturen auch in semantisch sinnlosen Sätzen wahrgenommen werden können.
  Beispiel: "Peter sang das Auto".
• Tesnière: Syntax folgt aus Semantik, aber nicht umgekehrt.
• Zu jeder syntaktischen Beziehung gibt es eine semantische in umgekehrter Richtung.
• Es existiert aber keine vollständige Abhängigkeit:
  Beispiel: anaphorische Beziehungen haben keine syntaktische Beziehung.

Nukleus

• Kleinste syntaktische Einheit.
• Knoten im Parsbaum sind Nuklei.
• Oft, aber nicht notwendigerweise, einzelne Wörter.
• Auch unzusammenhängende Wörter können einen Nukleus bilden.
• Unterteilung fällt in den Bereich der Linearisierung, welche sprachabhängig ist.

Linearisierung

• Tesnière unterscheidet zwischen der linearen Ordnung und der (zweidimensionalen) strukturellen Ordnung.
• Die strukturelle Ordnung beschreibt Abhängigkeiten, dadurch sind mehrere Oberflächen-Strukturen aus einer strukturellen Ordnung möglich.
• Tesnière nimmt an, dass Nachbarschaft nicht aus syntaktischen Gründen verletzt wird, sondern, wenn überhaupt, eher aus stilistischen Gründen (oder, moderner, aus Gründen des Diskurses).
• Einige Sprachen haben aufgrund reichhaltiger Morphologie die Möglichkeit, durch Wortreihenfolge Diskursfunktionen auszudrücken.
• Auch daraus folgt, dass Linearisierungsregeln sprachabhängig sein müssen.
• Keine einfachen Regeln, auch wenn man mit wenigen Regeln schon große Abdeckung erzielen kann.
  Beispiel (Englisch): Attributive Adjektive gehen dem jeweiligen Kopf voran:
  "The strange comedian."
  Aber es kann auch anders sein:
  "It is a phenomenon consistent with this theory."

Gaifman, Hays & Robinson

• Gaifman formalisiert eine Art von Dependenzgrammatik, die jedoch nicht eng verbunden mit Tesnières Ansatz ist.
  Regeln: Kategorie X hat Regeln der Form X(Y₁, Y₂ ... Y_i * Y_i+1 ... Y_n), Y₁ bis Y_n hängen von X in dieser Reihenfolge ab, X belegt Prosition des *.
• Hays behauptet, das diese Formalisierung Chomskys Klasse der Kontext-freien Sprache entspricht.
• Robinson verstärkt die Verbindung zwischen beiden, DGs sollen schwach equivalent zu kontextfreien PSGs sein.
• Resultat: Das Interesse an formalen Eigenschaften der DGs lässt stark nach.

Marcus

• Tesnière hat Linearisierung nur insofern besprochen, als das er sie aus seiner Konzeption ausschließt.
• Marcus formuliert Projektivität, und beschreibt somit Mengen von Strings und nicht (mehrdimensionale) Strukturen.

Formale Eigenschaften der FDG

• Der Nukleus ist das primitive Element der Struktur.
• Syntaktische Struktur durch Verbindungen zwischen Nuklei.
• Verbindungen als binäre Funktion zwischen Regent und Dependent.
• Jeder Nukleus stellt einen Knoten im Syntaxbaum dar und hat genau einen Regenten.
• Jeder Regent repräsentiert den gesamten Unterbaum.
• Der höchste Regent ist der zentrale Knoten des Satzes.

Daraus ergibt sich als Konsequenz:

• Gerichteter, azyklischer, zusammenhängender Graph.
• Keine multiplen Abhängigkeiten oder Zykel.
• Struktur muss nicht projektiv sein.

Die Funktionale Dependenz Grammatik

• FDG Parser besteht aus:
• Lexikon
• Morphologische Disambiguierungs-Komponente CG2
• Die eigentlich (FD) Grammatik
• Eine Beispielimplementation für das Englische existiert (Web-demo).
• Problem der praktischen Implementation: Word-order.

Linearisierung in der FDG

• Lösung: Sowohl lineare als auch strukturelle Ordnung werden erhalten (Erweiterung von Tesnières Ansatz).
• Möglich, indem funktionale Informationen nicht durch kanonische Ordnung der Dependenten, sondern durch solche Verbindungen repräsentiert wird, die Labels mit syntaktischen Funktionen tragen.
• Zur Zeit existieren mehr als 30 solcher syntaktischen Funktionen (subj:, obj:, loc: ...).

Nutzung des Nukleus

• Im Beispiel: Es ist einfach, alle Sätze zu finden, bei denen der Hauptknoten verbhaft ist und auf die Stammform "run" zurückgeht.
• Nukleus kann ggf. weitere Informationen tragen (z.B. Negation).
• Wörter werden nur dann neuen Knoten zugeordnet, wenn dies syntaktisch erforderlich wird

Koordination

• Behauptung: Phrasenstruktur ist nicht notwendig zur Behandlung von Koordination.
• Ansatz: K. ist spezielle Verbindung zwischen funktional gleichen Elementen (mittels cc:-Bogen).

• cc: drückt keine Abhängigkeit aus!
• Alle Kombinationen möglich:
  "Bill loves Mary", "John loves Mary"

Gapping

• Behandlung ähnlich Koordination, Koordinator erbt alle Eigenschaften des fehlenden verbhaften Elements.

• Genauso möglich für nicht verbhaftes Gapping:
  "John gave the lecture on Tuesday and Bill on Wednesday."