An Introduction to Tree Adjoining Grammars GUO, Yuqing NCLT, DCU 15 Nov. 2006

Outline •

Introduction – Basic Mechanisms – Properties – Variants

•

Applications – TAG Resource Induction – Parsing with TAG

NCLT Seminar Series 2006/2007

~2~

Introduction •

Tree Adjoining Grammar – Introduced in [Joshi & Takahashi, 1975] – A formal tree rewriting system

•

Basics of TAG Formalism – Primitive elements: elementary trees • Initial trees • Auxiliary trees

– Operations

• Substitution • Adjoining

– Derivations

• Derived trees • Derivation trees NCLT Seminar Series 2006/2007

~3~

Domain of Locality of CFGs • •

One level tree corresponding to a rule Not every rule is lexicalized

CFG G:

•

Is a grammar capable of – Lexicalization of each elementary domain – Encapsulation of the arguments of the lexical anchor NCLT Seminar Series 2006/2007

~4~

Lexicalization of Grammars

•

Elementary objects are elementary trees

•

Each tree contains at least one frontier node labeled with a terminal symbol (lexical anchor)

NCLT Seminar Series 2006/2007

~5~

Initial Trees & Substitution •

An initial tree – all interior nodes are labelled with non-terminal symbols – the nodes on the frontier are either labelled with terminal symbols, or with non-terminal symbols marked for substitution (↓)

γ

α

=> β

β substitution NCLT Seminar Series 2006/2007

~6~

Tree Substitution Grammar •

Are CFG, G and TSG, G’ strongly equivalent? Not only the string languages but also the sets of structure descriptions are the same. CFG G: S -> S S (non-lexical) S -> a (lexical)

γ

TSG G’:

α1

α2

α3

Can’t be derived in TSG NCLT Seminar Series 2006/2007

~7~

Auxiliary Trees & Adjoining •

An auxiliary tree – one of its frontier nodes must be marked as foot node (*) – the foot node must be labeled with a non-terminal symbol which is identical to the label of the root node.

α

γ β *

=>

β *

adjoining NCLT Seminar Series 2006/2007

~8~

Lexicalized TAG α

β *

=>

*

=>

γ *

=>

NCLT Seminar Series 2006/2007

~9~

Derivation & Derived tree e.g. ‘Harry likes peanuts passionately ’ TAG G

step 1 substitution

*

+

+

step 2 adjoining +

*

=>

=>

NCLT Seminar Series 2006/2007

~10~

Derivation & Derivation tree •

A derivation tree -- Specifies how a derived

tree was constructed

– The root node is labeled by an S-type initial tree – Other nodes are labeled by auxiliary trees in the case of adjoining or initial trees in the case of subsititution – A tree address of the parent tree is associated with each node (Gorn address is used as tree address: the root of a tree has address 0, and the jth child of the node with address i has address i.j )

substitution adjoining

NCLT Seminar Series 2006/2007

~11~

Long Distance Dependency 1/3

•

LFG – Stated on f-structures – Resolved by functional uncertainties ↑TOPIC = ↑COMP*OBJ

•

TAG [Joshi & Vijay-Shanker, 1998] – Localized in the elementary trees – Functional uncertainty is not necessary NCLT Seminar Series 2006/2007

~12~

Long Distance Dependencies 2/3 e.g. ‘Whoi did John tell Sam that Bill likes ei’

↓

↓

↓

NCLT Seminar Series 2006/2007

↓

~13~

Long Distance Dependencies 3/3

The derived tree NCLT Seminar Series 2006/2007

~14~

Summarization 1/2

•

Definition of TAG G

– I: a finite set of initial trees – A: a finite set of auxiliary trees – T(G): the set of all derived trees starting from S-type initial trees in I whose frontier consists of terminal nodes – L(G): the set of all terminal strings on the frontier of the trees in T(G)

•

Correspondence to embedded pushdown automata (EPDA) NCLT Seminar Series 2006/2007

~15~

Summarization 2/2

•

Important Properties of TAG – An extended domain of locality – Factoring recursion from the domain of dependencies

Localize the dependencies • Mildly context-sensitive: CFL TAL •

CSL

– strong generative capacity – efficiently parsable (in polynomial time) NCLT Seminar Series 2006/2007

~16~

Variations of TAGs 1/2 •

Feature Structure Based TAG (FTAG) each of the nodes of an elementary tree is associated with two feature structures: top & bottom

Substitution with features

Adjoining with features NCLT Seminar Series 2006/2007

~17~

Variations of TAGs 2/2 •

Synchronous TAG – A pair of TAGs characterize correspondences between languages – Semantic interpretation, language generation and translation

•

Muti-component TAG (MCTAG) – A set of auxiliary tree can be adjoined to a given elementary tree

•

Probabilistic TAG (PTAG) – Associating a probability with each elementary tree – Compute the probability of a derivation NCLT Seminar Series 2006/2007

~18~

Relationship to Other Formalisms •

Lexical Functional Grammar – Translate LFG to LTAG [Kameyama,1984] • Replace c-structure by LTAG structures • Map them into LTAG-like f-structures

•

Head-Driven Phrase Structure Grammar – Compile HPSG to LTAG [Kasper,1995]

•

Combinatory Categorial Grammar – Encapsulate the arguments in categorial grammar framework – Construct a categorial system with LTAGlike properties [Joshi etc,1997 & 1999] NCLT Seminar Series 2006/2007

~19~

Applications •

The XTAG Project (http://www.cis.upenn.edu/~xtag) – An on-going project to develop a wide-coverage grammar for English using the LTAG formalism. – An system for the development of TAGs and consists of a parser, an X-windows grammar development interface and a morphological analyzer. – Contains diverse linguistic resources • • • •

Subcategorization information Syntax of various constructions Frequency information Morphological information NCLT Seminar Series 2006/2007

~20~

Extraction Procedure 1/2 •

[Chen, 2000] – Find headword for each local tree, the path through the nodes of headword is a trunk – Classify the sibling nodes of the headword as complements (arguments) or adjuncts – Excise at a complement nodes to form initial trees, leaving behind a substitution node – Adjuncts are factored into modifier auxiliary trees

↓

*

*

NCLT Seminar Series 2006/2007

~21~

Extraction Procedure 2/2 – If node n has a right corner node n’ which is an complement with the same label as n, excise the subtree from n down to n’ to form a predicate auxiliary trees

•

Special strategies for coordinations, punctuations and empty elements etc. NCLT Seminar Series 2006/2007

~22~

Evaluation •

Data

– Extract from sections 2-21 of the Penn Treebank – Test on section 22

•

Different Grammars

– CA1: use labels and functional tags of the current node and the parent node for argument determination – CA2: use labels and functional tags of the current node and the head node and the distance for argument determination – ALL: include all empty elements – SOME: include some crucial empty elements – FULL: use the original Penn Treebank label set – MERGED: use a reduced set of labels

NCLT Seminar Series 2006/2007

~23~

Qualitative Evaluation

NCLT Seminar Series 2006/2007

~24~

Parsing •

A variant of LTAG [Chiang, 2000] – Elementary trees • Initial tree • Predicative auxiliary tree • Modifier tree

– Composition operation • Substitution • Adjoining (Adjunct) • Sister-adjunction

NCLT Seminar Series 2006/2007

~25~

Probabilistic TAG •

Parameters of PTAG

•

Probability of a derivation

(1) (2) (3) (4)

•

A decomposed model

α: initial trees β: auxiliary trees γ: modifier trees η: nodes : beginning a derivation with α : substituting α atη : adjoining β atη : sister-adjoiningγbetween the ith and i+1th children ofη

NCLT Seminar Series 2006/2007

~26~

Parsing Result • •

A modified CKY-style parser Data – Training: sections 2-21 of Penn Treebank – Test: section 23

NCLT Seminar Series 2006/2007

~27~

Reference Joshi, A. K. 2003. Tree-Adjoining Grammars. In R. Mitkov (eds.), The Oxford Handbook of Computational Linguistics. 483-498, Oxford University Press, New York. Joshi, A. K., L. S. Levy, and M. Takahashi. 1975. Tree Adjunct Grammars. Journal of Computer and Systems Sciences, 10(1), 55-75. Joshi, A. K. and Y. Schabes. 1997. Tree-adjoining grammars, In G. Rosenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol. 3, 69-123, Springer-Verlag, New York, NY. Joshi, A. K. and K. Vijay-Shanker. 1998. Treatment of Long Distance Dependencies in LFG And TAG: Functional Uncertainty in LFG is a Corollary in TAG. In Proceedings of

the 27th Annual Meeting of the Association for Computational Linguistics, 220-227, Vancouver, BC. NCLT Seminar Series 2006/2007

~28~

Reference The XTAG project: http://www.cis.upenn.edu/~xtag Chen, J., K. Vijay-Shanker. 2000. Extraction Of TAGs From The Penn Treebank, In Proceedings of the 6th International Workshop on Parsing Technologies, Trento, Italy. Neumann, G. 1998. Automatic Extraction of Stochastic Lexicalized Tree Grammars from Treebanks, In Proceedings

of the 4th International Workshop on Tree Adjoining Grammars and Related Frameworks, 120-123

Schabes,Y., A. Abeillé, 1988. Parsing Strategies with 'Lexicalized' Grammars: application to tree adjoining grammars, in Proceedings of the 12th International Conference On Computational Linguistics, 578-583, Budapest, Hungary. Chiang, D. 2000. Statistical Parsing With an AutomaticallyExtracted Tree Adjoining Grammar, In Proceedings of the

38th Annual Meeting of the Association for Computational Linguistics (ACL-2000), 456-463, Hong Kong. NCLT Seminar Series 2006/2007

~29~

Thanks ! & Questions?

Outline •

Introduction – Basic Mechanisms – Properties – Variants

•

Applications – TAG Resource Induction – Parsing with TAG

NCLT Seminar Series 2006/2007

~2~

Introduction •

Tree Adjoining Grammar – Introduced in [Joshi & Takahashi, 1975] – A formal tree rewriting system

•

Basics of TAG Formalism – Primitive elements: elementary trees • Initial trees • Auxiliary trees

– Operations

• Substitution • Adjoining

– Derivations

• Derived trees • Derivation trees NCLT Seminar Series 2006/2007

~3~

Domain of Locality of CFGs • •

One level tree corresponding to a rule Not every rule is lexicalized

CFG G:

•

Is a grammar capable of – Lexicalization of each elementary domain – Encapsulation of the arguments of the lexical anchor NCLT Seminar Series 2006/2007

~4~

Lexicalization of Grammars

•

Elementary objects are elementary trees

•

Each tree contains at least one frontier node labeled with a terminal symbol (lexical anchor)

NCLT Seminar Series 2006/2007

~5~

Initial Trees & Substitution •

An initial tree – all interior nodes are labelled with non-terminal symbols – the nodes on the frontier are either labelled with terminal symbols, or with non-terminal symbols marked for substitution (↓)

γ

α

=> β

β substitution NCLT Seminar Series 2006/2007

~6~

Tree Substitution Grammar •

Are CFG, G and TSG, G’ strongly equivalent? Not only the string languages but also the sets of structure descriptions are the same. CFG G: S -> S S (non-lexical) S -> a (lexical)

γ

TSG G’:

α1

α2

α3

Can’t be derived in TSG NCLT Seminar Series 2006/2007

~7~

Auxiliary Trees & Adjoining •

An auxiliary tree – one of its frontier nodes must be marked as foot node (*) – the foot node must be labeled with a non-terminal symbol which is identical to the label of the root node.

α

γ β *

=>

β *

adjoining NCLT Seminar Series 2006/2007

~8~

Lexicalized TAG α

β *

=>

*

=>

γ *

=>

NCLT Seminar Series 2006/2007

~9~

Derivation & Derived tree e.g. ‘Harry likes peanuts passionately ’ TAG G

step 1 substitution

*

+

+

step 2 adjoining +

*

=>

=>

NCLT Seminar Series 2006/2007

~10~

Derivation & Derivation tree •

A derivation tree -- Specifies how a derived

tree was constructed

– The root node is labeled by an S-type initial tree – Other nodes are labeled by auxiliary trees in the case of adjoining or initial trees in the case of subsititution – A tree address of the parent tree is associated with each node (Gorn address is used as tree address: the root of a tree has address 0, and the jth child of the node with address i has address i.j )

substitution adjoining

NCLT Seminar Series 2006/2007

~11~

Long Distance Dependency 1/3

•

LFG – Stated on f-structures – Resolved by functional uncertainties ↑TOPIC = ↑COMP*OBJ

•

TAG [Joshi & Vijay-Shanker, 1998] – Localized in the elementary trees – Functional uncertainty is not necessary NCLT Seminar Series 2006/2007

~12~

Long Distance Dependencies 2/3 e.g. ‘Whoi did John tell Sam that Bill likes ei’

↓

↓

↓

NCLT Seminar Series 2006/2007

↓

~13~

Long Distance Dependencies 3/3

The derived tree NCLT Seminar Series 2006/2007

~14~

Summarization 1/2

•

Definition of TAG G

– I: a finite set of initial trees – A: a finite set of auxiliary trees – T(G): the set of all derived trees starting from S-type initial trees in I whose frontier consists of terminal nodes – L(G): the set of all terminal strings on the frontier of the trees in T(G)

•

Correspondence to embedded pushdown automata (EPDA) NCLT Seminar Series 2006/2007

~15~

Summarization 2/2

•

Important Properties of TAG – An extended domain of locality – Factoring recursion from the domain of dependencies

Localize the dependencies • Mildly context-sensitive: CFL TAL •

CSL

– strong generative capacity – efficiently parsable (in polynomial time) NCLT Seminar Series 2006/2007

~16~

Variations of TAGs 1/2 •

Feature Structure Based TAG (FTAG) each of the nodes of an elementary tree is associated with two feature structures: top & bottom

Substitution with features

Adjoining with features NCLT Seminar Series 2006/2007

~17~

Variations of TAGs 2/2 •

Synchronous TAG – A pair of TAGs characterize correspondences between languages – Semantic interpretation, language generation and translation

•

Muti-component TAG (MCTAG) – A set of auxiliary tree can be adjoined to a given elementary tree

•

Probabilistic TAG (PTAG) – Associating a probability with each elementary tree – Compute the probability of a derivation NCLT Seminar Series 2006/2007

~18~

Relationship to Other Formalisms •

Lexical Functional Grammar – Translate LFG to LTAG [Kameyama,1984] • Replace c-structure by LTAG structures • Map them into LTAG-like f-structures

•

Head-Driven Phrase Structure Grammar – Compile HPSG to LTAG [Kasper,1995]

•

Combinatory Categorial Grammar – Encapsulate the arguments in categorial grammar framework – Construct a categorial system with LTAGlike properties [Joshi etc,1997 & 1999] NCLT Seminar Series 2006/2007

~19~

Applications •

The XTAG Project (http://www.cis.upenn.edu/~xtag) – An on-going project to develop a wide-coverage grammar for English using the LTAG formalism. – An system for the development of TAGs and consists of a parser, an X-windows grammar development interface and a morphological analyzer. – Contains diverse linguistic resources • • • •

Subcategorization information Syntax of various constructions Frequency information Morphological information NCLT Seminar Series 2006/2007

~20~

Extraction Procedure 1/2 •

[Chen, 2000] – Find headword for each local tree, the path through the nodes of headword is a trunk – Classify the sibling nodes of the headword as complements (arguments) or adjuncts – Excise at a complement nodes to form initial trees, leaving behind a substitution node – Adjuncts are factored into modifier auxiliary trees

↓

*

*

NCLT Seminar Series 2006/2007

~21~

Extraction Procedure 2/2 – If node n has a right corner node n’ which is an complement with the same label as n, excise the subtree from n down to n’ to form a predicate auxiliary trees

•

Special strategies for coordinations, punctuations and empty elements etc. NCLT Seminar Series 2006/2007

~22~

Evaluation •

Data

– Extract from sections 2-21 of the Penn Treebank – Test on section 22

•

Different Grammars

– CA1: use labels and functional tags of the current node and the parent node for argument determination – CA2: use labels and functional tags of the current node and the head node and the distance for argument determination – ALL: include all empty elements – SOME: include some crucial empty elements – FULL: use the original Penn Treebank label set – MERGED: use a reduced set of labels

NCLT Seminar Series 2006/2007

~23~

Qualitative Evaluation

NCLT Seminar Series 2006/2007

~24~

Parsing •

A variant of LTAG [Chiang, 2000] – Elementary trees • Initial tree • Predicative auxiliary tree • Modifier tree

– Composition operation • Substitution • Adjoining (Adjunct) • Sister-adjunction

NCLT Seminar Series 2006/2007

~25~

Probabilistic TAG •

Parameters of PTAG

•

Probability of a derivation

(1) (2) (3) (4)

•

A decomposed model

α: initial trees β: auxiliary trees γ: modifier trees η: nodes : beginning a derivation with α : substituting α atη : adjoining β atη : sister-adjoiningγbetween the ith and i+1th children ofη

NCLT Seminar Series 2006/2007

~26~

Parsing Result • •

A modified CKY-style parser Data – Training: sections 2-21 of Penn Treebank – Test: section 23

NCLT Seminar Series 2006/2007

~27~

Reference Joshi, A. K. 2003. Tree-Adjoining Grammars. In R. Mitkov (eds.), The Oxford Handbook of Computational Linguistics. 483-498, Oxford University Press, New York. Joshi, A. K., L. S. Levy, and M. Takahashi. 1975. Tree Adjunct Grammars. Journal of Computer and Systems Sciences, 10(1), 55-75. Joshi, A. K. and Y. Schabes. 1997. Tree-adjoining grammars, In G. Rosenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol. 3, 69-123, Springer-Verlag, New York, NY. Joshi, A. K. and K. Vijay-Shanker. 1998. Treatment of Long Distance Dependencies in LFG And TAG: Functional Uncertainty in LFG is a Corollary in TAG. In Proceedings of

the 27th Annual Meeting of the Association for Computational Linguistics, 220-227, Vancouver, BC. NCLT Seminar Series 2006/2007

~28~

Reference The XTAG project: http://www.cis.upenn.edu/~xtag Chen, J., K. Vijay-Shanker. 2000. Extraction Of TAGs From The Penn Treebank, In Proceedings of the 6th International Workshop on Parsing Technologies, Trento, Italy. Neumann, G. 1998. Automatic Extraction of Stochastic Lexicalized Tree Grammars from Treebanks, In Proceedings

of the 4th International Workshop on Tree Adjoining Grammars and Related Frameworks, 120-123

Schabes,Y., A. Abeillé, 1988. Parsing Strategies with 'Lexicalized' Grammars: application to tree adjoining grammars, in Proceedings of the 12th International Conference On Computational Linguistics, 578-583, Budapest, Hungary. Chiang, D. 2000. Statistical Parsing With an AutomaticallyExtracted Tree Adjoining Grammar, In Proceedings of the

38th Annual Meeting of the Association for Computational Linguistics (ACL-2000), 456-463, Hong Kong. NCLT Seminar Series 2006/2007

~29~

Thanks ! & Questions?