Tree Adjoining Grammars.ppt

1、Tree Adjoining Grammars,CIS 530 Intro to NLP,CIS 530 - Intro to NLP,2,Context Free Grammars,S,NP,S,V,does,S,NP,V,think,VP,S,NP,who,Harry,Bill,Who does Bill think Harry likes?,Context Free Grammars: Derivations,CIS 530 - Intro to NLP,3,Context Free Grammars,S,NP,S,V,does,S,NP,V,think,VP,S,NP,who,Harr

2、y,Bill,Who does Bill think Harry likes?,Context Free Grammars: Semantics,Meaning relations of the predicate/argument structures is lost in the tree likes (Harry, who),CIS 530 - Intro to NLP,4,Context Free Grammars,CFGs can be parsed in time proportional to n3, where n is the length of the input in w

3、ords by algorithms like CKY.,Context Free Grammars: Complexity,CIS 530 - Intro to NLP,5,Transformational Grammars,S,NP,S,V,does,S,NP,V,think,VP,S,NP,V,NP,likes,VP,Harry,Bill,Who does Bill think Harry likes?,Context Free Deep Structure plus Movement Transformations,CIS 530 - Intro to NLP,6,TGs can be

4、 parsed in exponential time 2n, where n is the length of the input in words Exponential time is intractable, because exponentials grow so quickly,Transformational Grammars: Complexity,CIS 530 - Intro to NLP,7,Lexicalized LTAG,Finite set of elementary trees anchored on lexical items - encapsulates sy

5、ntactic and semantic dependencies Elementary trees: Initial and Auxiliary,CIS 530 - Intro to NLP,8,LTAG: A set of Elementary Trees,CIS 530 - Intro to NLP,9,a1:,S,NP,V,NP,likes,a2:,S,NP,V,NP,likes,NP,e,S,transitive,object extraction,some other trees for likes: subject extraction, topicalization, subj

6、ect relative, object relative, passive, etc.,VP,VP,LTAG: Examples,CIS 530 - Intro to NLP,10,Lexicalized LTAG,Finite set of elementary trees anchored on lexical items - encapsulates syntactic and semantic dependencies Elementary trees: Initial and Auxiliary Operations: Substitution and Adjoining,CIS

7、530 - Intro to NLP,11,a:,X,b:,X,g:,X,b,Substitution,CIS 530 - Intro to NLP,12,a:,X,b:,X*,X,g:,X,X,b,Tree b adjoined to tree a at the node labeled X in the tree a,Adjoining,CIS 530 - Intro to NLP,13,LTAG: A derivation,CIS 530 - Intro to NLP,14,LTAG: A derivation,CIS 530 - Intro to NLP,15,LTAG: A deri

8、vation,CIS 530 - Intro to NLP,16,LTAG: A derivation,NP,S,a2:,CIS 530 - Intro to NLP,17,LTAG: A derivation,NP,S,a2:,CIS 530 - Intro to NLP,18,LTAG: A derivation,NP,S,a2:,NP,S,a2:,S,CIS 530 - Intro to NLP,19,LTAG: A derivation,NP,S,a2:,S,NP,V,NP,likes,e,VP,b1:,S,CIS 530 - Intro to NLP,20,LTAG: A deriv

9、ation,NP,S,a2:,CIS 530 - Intro to NLP,21,LTAG: Semantics,S,NP,S,V,does,S,NP,V,think,VP,S,NP,V,NP,likes,e,VP,who,Harry,Bill,who does Bill think Harry likes,Meaning relations of the predicate/argument structures are clear in the original base trees!,CIS 530 - Intro to NLP,22,S,NP,V,NP,likes,NP,e,S,VP,

10、S,NP,V,S*,b1:,think,VP,b2:,V,S,does,S*,NP,NP,NP,who,Harry,Bill,a3:,a2:,a4:,a5:,substitution,adjoining,who does Bill think Harry likes,LTAG: A Derivation,CIS 530 - Intro to NLP,23,who does Bill think Harry likes,a2:,likes,a3:,who,b1:,think,a4:,Harry,b2:,does,a5:,Bill,* Compositional semantics on this

11、 derivation structure * Related to dependency diagrams,substitution,adjoining,LTAG: Derivation Tree,TAGs: Complexity,TAGs can be parsed in polynomial time n5 rather than n3 for CFGs TAGS are a prime example of mildly context sensitive grammars (MCSGs) Plausible: MCSGs are sufficient to capture the g

12、rammars of all human languages E.g. can parse Swiss German,CIS 530 - Intro to NLP,24,CIS 530 - Intro to NLP,25,Context Free Grammars Structure doesnt well represent “domains of locality” reflecting meaning Parsed in polynomial time n3 (n is the length of the input) Transformational Grammars Captures

13、 domains of locality, accounting for surface word order by “movement” Parsing is intractable, requring 2n time Tree Adjoining Grammars Captures domains of locality, with surface discontiguities the result of adjunction Parsed in polynomial time n5 (rather than n3 for CFGs),Adequacy vs. Complexity,TA

14、Gs & Mildly Context Sensitive Languages: Swiss German,CIS 530 - Intro to NLP,26,CIS 530 - Intro to NLP,27,English relative clauses are nested,NP1 The mouse VP1 ate the cheese Form: NP1 VP1 NP1 The mouse NP2 the cat VP2 chased VP1 ate the cheese Form: NP1 NP2 VP2 VP1 Theorem: Languages of form wwr ar

15、e context free,CIS 530 - Intro to NLP,28,CFG trees naturally nest structure,V,NP,ate,the cheese,VP1,S,NP,VP2,S,CIS 530 - Intro to NLP,29,Swiss German sentences are harder.,In English: NP1 Claudia VP1 watched NP2 Eva vp2 make NP3 Ulrich VP2 work Form: NP1 VP1 NP2 VP2 NP3 VP3 Not hard In Swiss German:

16、 NP1 Claudia NP2 Eva NP3 Ulrich VP1 watched vp2 make VP3 work Form: NP1 NP2 NP3 VP1 VP2 VP3 Theorem: Languages of form ww cannot be generated by Context Free Grammars,CIS 530 - Intro to NLP,30,Scrambling: N1 N2 N3 V1 V2 V3,V1,VP,N1 VP,VP,VP,N1,e,VP,N2 VP,VP,VP,N2,V2,e,VP,VP,N3 VP,VP,VP,N3,V3,e,VP,CI

17、S 530 - Intro to NLP,31,Scrambling: N1 N2 N3 V1 V2 V3,VP,N1,VP,N2 VP,VP,VP,VP,N3 VP,VP,VP,N3,V3,e,VP,CIS 530 - Intro to NLP,32,Scrambling: N1 N2 N3 V1 V2 V3,VP,VP,VP,N3,V3,e,CIS 530 - Intro to NLP,33,A Simple Synchronous TAG translator,CIS 530 - Intro to NLP,34,Substituting in “John” and “Mary”,CIS

18、530 - Intro to NLP,35,Substituting “Apparently”,Parsing TAGs by “Supertagging”:Reducing parsing to POS tagging + ,CIS 530 - Intro to NLP,37,Supertag disambiguation - supertagging,Given a corpus parsed by an LTAG grammar We have statistics of supertags - unigram, bigram, trigram, etc. These statistic

19、s combine the lexical statistics as well as the statistics of the constructions in which the lexical items appear,CIS 530 - Intro to NLP,38,Supertagging,the purchase price includes two ancillary companies,a9,b2,a1,.,.,.,a10,a6,a2,.,.,.,b1,a11,a7,a3,.,.,.,b3,a12,b4,a4,.,.,.,a13,a8,a5,.,.,.,On the ave

20、rage a lexical item has about 8 to 10 supertags,CIS 530 - Intro to NLP,39,Supertagging,the purchase price includes two ancillary companies,a9,b2,a1,.,.,.,a10,a6,a2,.,.,.,b1,a11,a7,a3,.,.,.,b3,a12,b4,a4,.,.,.,a13,a8,a5,.,.,.,- Select the correct supertag for each word - shown in blue - Correct supert

21、ag for a word means the supertag that corresponds to that word in the correct parse of the sentence,CIS 530 - Intro to NLP,40,Supertagging - performance,- Performance of a trigram supertagger,- Performance on the WSJ corpus,Size of the training corpus,Size of the test corpus,# of words correctly sup

22、ertagged,% correct,Baseline,47,000,35,391,75.3%,1 million,47,000,43,334,92.2%,Srinivas (1997),CIS 530 - Intro to NLP,41,Abstract character of supertagging,Complex (richer) descriptions of primitives Contrary to the standard mathematical convention Descriptions of primitives are simple Complex descri

23、ptions are made from simple descriptions Associate with each primitive all information associated with it,CIS 530 - Intro to NLP,42,Complex descriptions of primitives,Making descriptions of primitives more complex Increases the local ambiguity, i.e., there are more descriptions for each primitive However, these richer descriptions of primitive