Tree Adjoining Grammar

Tree-adjoining grammars (TAG), auch Baumadjunktions-Grammatiken, sind formale Grammatiken, die von Aravind Joshi eingeführt wurden und in der Computerlinguistik für die Beschreibung von natürlichen Sprachen verwendet werden.

TAGs ähneln kontextfreien Grammatiken, verwenden aber Bäume statt Symbole als kleinste Elemente. Diese Elementarbäume werden nach festgelegten Regeln, Substitution und Adjunktion, miteinander zu immer größeren Bäumen kombiniert. Am Ende des Prozesses kann an den Blättern des entstandenen Baumes ein Satz als Folge von Worten abgelesen werden. Die Menge der durch eine konkrete Baumadjunktionsgrammatik beschreibbaren Sätze bildet die Sprache dieser TAG.

TAGs werden als schwach kontextsensitiv (mildly context-sensitive) beschrieben; sie sind also stärker als kontextfreie Grammatiken, aber schwächer als kontextsensitive Grammatiken in der Chomsky-Hierarchie. Daher sind sie vermutlich stark genug, um natürliche Sprachen zu erzeugen, aber auch schwach genug, um noch effizient parsebar zu sein.

Einstiegsbeispiel

Eine Baumadjunktionsgrammatik, die sowohl den Satz Rumo schnarcht als auch Rumo schnarcht nie verarbeiten kann, lässt sich zum Beispiel mit drei Elementarbäumen darstellen:

ein Initalbaum $α_{1}$ für die Nominalphrase für das Wort Rumo. Der Baum besteht aus dem Symbol NP (einem Nichtterminalsymbol), welches zu dem Wort Rumo (einem Terminalsymbol) expandiert.
ein Initalbaum $α_{2}$ für das Verb schnarcht. Der Baum zeigt an, dass dem Verb zu einem ganzen Satz noch eine Nominalphrase (NP) fehlt. Der Baumknoten NP ist mit $↓$ als Substitutionsknoten markiert, um zu signalisieren, dass an dieser Stelle noch ein Baum mit einer NP als Wurzel eingesetzt werden muss. Ansonsten besteht der $α_{2}$ -Baum noch aus einer Verbalphrase (VP), welche wiederum aber lediglich aus dem Verb schnarcht besteht.
ein Auxiliarbaum $β_{1}$ für das Adverb nie. Der Baum besteht neben dem Adverb nie noch aus zwei weiteren VP-Knoten. Jeder Auxiliarbaum besitzt einen speziellen Fußknoten, markiert durch $*$ , der das gleiche Nichtterminal wie die Wurzel des Baums aufweisen muss. In diesem Fall ist das eine VP. Dieser Baum kann also dazu genutzt werden, um Verbalphrasen zu modifizieren.

Um den Satz Rumo schnarcht zu erhalten, müssen nur die zwei Initialbäume $α_{1}$ und $α_{2}$ mittels Substitution miteinander kombiniert werden. Dazu wird der Substitutionsknoten mit der Wurzel des NP-Baums ersetzt. Soll der Satz um das Adverb nie erweitert werden, kommt die Adjunktion zum Einsatz, die den Baumadjunktionsgrammatiken auch ihren Namen gab. Bei der Adjunktion wird der Baum des bisherigen Satzes am VP-Knoten quasi in zwei Teile gerissen. Der Teilbaum des Satzes oberhalb des ursprünglichen VP-Knotens endet nun in der Wurzel des Auxiliarbaums $β_{1}$ , während der unter Teilbaum nun an dem ehemaligen Fußknoten des Auxiliarbaums beginnt. Theoretisch kann diese Adjunktion beliebig oft wiederholt werden (Rumo schnarcht nie nie nie nie ...).

Definition

Eine TAG ist ein 5-Tupel $(Σ, N T, I, A, S)$ bestehend aus

$Σ$ , einer endlichen Menge von Terminalsymbolen;
$N T$ , einer endlichen Menge von Nichtterminalsymbolen, die mit der Menge der Terminale disjunkt ist;
I, einer endlichen Menge von Initialbäumen. Initialbäume sind solche Bäume, die
- als innere Knoten Nichtterminale besitzen und
- als Blätter Nichtterminale oder Terminale, wobei Nichtterminale mit $↓$ markiert sind, um Substitution anzuzeigen.
A, einer endlichen Menge an Auxiliarbäumen. Auxiliarbäume sind solche Bäume, die
- als innere Knoten Nichtterminale besitzen und
- als Blätter Nichtterminale oder Terminale, wobei Nichtterminale üblicherweise mit $↓$ markiert werden, um Substitution anzuzeigen. Einer der Nichtterminalblätter ist hingegen nicht zur Substitution bestimmt, sondern ein Fußknoten (markiert als $*$ ) mit dem gleichen Nichtterminal wie die Wurzel des Auxiliarbaums.
$S$ , dem speziellen Startsymbol der TAG, welches ein Nichtterminal ist: $S \in N T$

Die Menge an Initial- und Auxiliarbäumen $I \cup A$ wird Menge der Elementarbäume genannt.

Zur Kombination von Bäumen stehen zwei Operationen zur Verfügung: Substitution und Adjunktion:

Substitution: bei dieser Operation wird ein Nichtterminalblatt eines Baumes durch die Wurzel eines anderen Baumes, der aus Initialbäumen abgeleitet wurde, ersetzt und damit die beiden Bäume verbunden.

Adjunktion: bei dieser Operation wird ein Auxiliarbaum in einen anderen Baum eingefügt. Dieser zweite Baum muss dafür ein Nichtterminal besitzen, welches der Wurzel und dem Fußknoten des Auxiliarbaums entspricht. Adjunktion an für die Substitution markierten Blättern ist nicht erlaubt. Adjunktion sieht dabei wie folgt aus:

Daneben gibt es noch die Möglichkeit, Adjunktions-Constraints für Knoten einzuführen:

Selektive Adjunktion (SA(T)): nur eine bestimmte Teilmenge T an Auxiliarbäumen darf an diesem Knoten adjungieren.
Null Adjunktion (NA): an einem mit NA markierten Knoten darf nicht adjungiert werden.
Obligatorische Adjunktion (OA(T)): an einem mit OA markierten Knoten muss adjungiert werden. Dazu muss ein Auxiliarbaum aus einer bestimmten Teilmenge T verwendet werden.

In der Definition von Joshi et al. (1975) gab es hingegen noch keine Constraints und Substitutionsknoten.

Expressivität

Obwohl TAGs aus Bäumen bestehen, fokussiert sich dieser Abschnitt auf die String-Sprachen von TAGs. Das sind die Sprachen, die sich an den Blättern der Bäume aus den Terminalsymbolen ablesen lassen.

Relation zu kontextfreien Grammatiken

Zu jeder kontextfreien Grammatik (CFG, für englisch context-free grammar) kann eine TAG erzeugt werden, die die gleiche String-Sprache akzeptiert. Damit können TAGs alle kontextfreien Sprachen beschreiben.

Schwach kontextsensitive Sprachen

TAGs können aber mehr Sprachen beschreiben als kontextfreie Grammatiken. Denn mit TAGs können auch einige, aber nicht alle kontextsensitiven Sprachen beschrieben werden, wie folgende Beispiele verdeutlichen.

Zu den Beispielen von kontextsensitiven Sprachen, die von TAGs akzeptiert werden können, zählen folgende:

Die Copy-Sprache $𝖢𝖮𝖯𝖸 = {w w ∣ w \in Σ^{*}}$ kann von TAGs mit Adjunktionsconstraints ausgedrückt werden. Wenn das Vokabular $Σ = {a, b}$ ist, reichen nur drei Bäume aus, um die Sprache zu beschreiben. Ein Baum für das leere Wort und je ein weiterer für das Symbol a und b. Zur Sprache gehören Sätze wie abab und abaaba.

Die Count-4-Sprache, bei der genau gleich viele Symbole a, b, c und d generiert werden sollen, kann auch von TAGs mit Adjunktionsconstraints beschrieben werden. Formal ist diese definiert als ${𝖢𝖮𝖴𝖭𝖳}_{4} = {a^{n} b^{n} c^{n} d^{n} ∣ n \geq 0}$ und lässt sich mit nur zwei Bäumen generieren.

Zwei Beispiele für kontextsensitive Sprachen, die TAGs nicht beschreiben können, sind die Count-5-Sprache ${𝖢𝖮𝖴𝖭𝖳}_{5} = {a^{n} b^{n} c^{n} d^{n} f^{n} ∣ n \geq 0}$ und die doppelte Copy-Sprache $𝖣𝖮𝖴𝖡𝖫𝖤-𝖢𝖮𝖯𝖸 = {w w w ∣ w \in Σ^{*}}$ .

TAGs können die gleichen schwach kontextsensitiven Sprachen von Strings wie zum Beispiel kombinatorische Kategorialgrammatiken (Combinatory Categorical Grammars, CCGs) erzeugen.

Parsing

TAGs können mit einem CYK- oder Early-ähnlichen Parsing-Algorithmus geparst werden. Sie sind daher noch in polynomieller Zeit, genauer in $𝒪 (n^{6})$ , parsebar (siehe Landau-Notation).

Varianten und Erweiterungen

Lexikalisierte TAG (LTAG): bei einer LTAG enthält jeder Elementarbaum mindestens ein Terminalsymbol, welches auch (lexikalischer) Anker genannt wird.
Feature-TAG (FTAG): Bäume werden mit Merkmalsstrukturen annotiert, um Kongruenz zu erzwingen, zum Beispiel zwischen einem Verb im Singular und dem Subjekt, das auch im Singular sein soll.

Siehe auch

Literatur

Stefan Müller: Grammatiktheorie. In: Stauffenburg Einführungen. Band 20. Stauffenberg Verlag, Tübingen 2010, ISBN 978-3-86057-805-6 (hu-berlin.de [PDF]). , insbesondere Kapitel 10 zu TAG.
Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, doi:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).
Laura Kallmeyer: Parsing Beyond Context-Free Grammars (= Cognitive Technologies). Springer Berlin Heidelberg, Berlin, Heidelberg 2010, ISBN 978-3-642-14845-3, doi:10.1007/978-3-642-14846-0 (englisch, springer.com [abgerufen am 23. Juni 2025] Kapitel zu TAG auf Seiten 53 - 108).
Aravind K. Joshi, Yves Shabes: Tree-Adjoining Grammars. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of Formal Languages. Springer, Berlin, Heidelberg 1997, ISBN 978-3-642-59126-6, doi:10.1007/978-3-642-59126-6_2.

Weblinks

XTAG project, verwendet eine TAG für natürliche Sprache
Seminar zu TAG von Laura Kallmeyer und Simon Petitjean für das Wintersemester 2015/16 mit Foliensätzen zu verschiedenen Bereichen von TAGs.

Einzelnachweise

1 2 3 Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, doi:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).
1 2 David Jeremy Weir: Characterizing mildly context-sensitive grammar formalisms. University of Pennsylvania, United States Januar 1988 (englisch, acm.org – Dissertation in Computer and Information Science).
1 2 3 4 5 Aravind K. Joshi, Yves Schabes: Tree-Adjoining Grammars and Lexicalized Grammars. University of Pennsylvania Department of Computer and Information Science, 1. März 1991 (upenn.edu – Technical Report No. MS-CIS-91-22.).
1 2 K. Vijay-Shankar, Aravind K. Joshi: Some Computational Properties of Tree Adjoining Grammars. In: Strategic Computing - Natural Language Workshop: Proceedings of a Workshop Held at Marina del Rey, California, May 1-2, 1986. Mai 1986, S. 212–223 (englisch, aclanthology.org [PDF]).
1 2 3 4 Aravind K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: D. Dowty, L. Karttunen, and A. Zwicky (Hrsg.): Natural Language Parsing. Cambridge University Press, 1985, S. 206–250 (englisch, sfu.ca [PDF; abgerufen am 23. Juni 2025]).
↑ Yves Schabes, Aravind K. Joshi: An Earley-Type Parsing Algorithm for Tree Adjoining Grammars. In: 6th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Buffalo, New York, USA Juni 1988, S. 258–269, doi:10.3115/982023.982055 (englisch, aclanthology.org [PDF]).
↑ K. Vijay-Shanker, A.K. Joshi: Feature Structures Based Tree Adjoining Grammars. In: Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics. 1988 (englisch, aclanthology.org [abgerufen am 26. Juni 2025]).

[:0-1] 1 2 3 Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, doi:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).

[:1-2] 1 2 David Jeremy Weir: Characterizing mildly context-sensitive grammar formalisms. University of Pennsylvania, United States Januar 1988 (englisch, acm.org – Dissertation in Computer and Information Science).

[:4-3] 1 2 3 4 5 Aravind K. Joshi, Yves Schabes: Tree-Adjoining Grammars and Lexicalized Grammars. University of Pennsylvania Department of Computer and Information Science, 1. März 1991 (upenn.edu – Technical Report No. MS-CIS-91-22.).

[:2-4] 1 2 K. Vijay-Shankar, Aravind K. Joshi: Some Computational Properties of Tree Adjoining Grammars. In: Strategic Computing - Natural Language Workshop: Proceedings of a Workshop Held at Marina del Rey, California, May 1-2, 1986. Mai 1986, S. 212–223 (englisch, aclanthology.org [PDF]).

[:3-5] 1 2 3 4 Aravind K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: D. Dowty, L. Karttunen, and A. Zwicky (Hrsg.): Natural Language Parsing. Cambridge University Press, 1985, S. 206–250 (englisch, sfu.ca [PDF; abgerufen am 23. Juni 2025]).

[6] Yves Schabes, Aravind K. Joshi: An Earley-Type Parsing Algorithm for Tree Adjoining Grammars. In: 6th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Buffalo, New York, USA Juni 1988, S. 258–269, doi:10.3115/982023.982055 (englisch, aclanthology.org [PDF]).

[7] K. Vijay-Shanker, A.K. Joshi: Feature Structures Based Tree Adjoining Grammars. In: Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics. 1988 (englisch, aclanthology.org [abgerufen am 26. Juni 2025]).