Elamur Research⌕
☰
home / papers / 2000 / Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar

Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar

Paper · 2000 · David Chiang

Summary

The paper asks whether lexicalized tree-adjoining grammar (LTAG) is a practical replacement for lexicalized PCFG in statistical parsing. Chiang argues that PCFG parsers capture word-to-word dependencies only indirectly, by passing head words up the phrase-structure tree. This fails for cases such as auxiliary and raising verbs and relative clauses unless the grammar is transformed. In TAG, each composition step joins two lexically anchored elementary trees, so both word-pair and tree-pair dependencies come built in. The author uses a TIG-like variant with an extra operation, sister-adjunction, which produces the Penn Treebank's flat structures while keeping parsing cubic-time and weakly context-free. Head/argument/adjunct heuristics rebuild TAG derivations from the Penn Treebank, and a smoothed probabilistic model is estimated directly from those derivations. The induced grammar beats the EM-based induction of Hwa (1998). Its labeled precision and recall fall in the middle of the published lexicalized PCFG parsers. This shows that PTAG is a viable and conceptually cleaner basis for statistical parsing.

Key points

  • Comparison with Hwa (1998): the model was trained on Penn Treebank sections 02–09 and tested on section 23 (sentences of up to 40 words, parsing from POS tags). The score was the share of predicted brackets that cross no gold bracket: 84.4% versus 82.4%, about an 11% error reduction.
  • Full setup (train on sections 02–21, test on section 23):
    • Sentences ≤40 words: LR 86.9 and LP 86.6. This is above Magerman (1995) and Collins (1996) but below Collins (1997) and Charniak (2000).
    • Sentences ≤100 words: LR 86.2 and LP 85.8.
  • Grammar coverage on held-out section 00: out of 45,082 tree tokens, 0.2% of tree templates were unseen in training (about one every 20 sentences). For fully lexicalized trees, the unseen share was 4%.
  • Training and parsing details:
    • Words seen fewer than four times were mapped to UNKNOWN and tagged with Ratnaparkhi's tagger.
    • Tree templates seen only once in training were discarded.
    • Parsing used a CKY-style parser with beam pruning: an item was dropped if its score was below 10⁻⁵ of the best item in its cell.
  • Formalism: the grammar has three tree types (initial, auxiliary, modifier) and three operations (substitution, adjunction, sister-adjunction). Each modifier probability is conditioned on a flag marking whether it is the first modifier next to the head.

Interesting ideas

  • I1. Choose the formalism so the right context is local. Instead of patching a PCFG with ad hoc transformations (grandparent labels, subject markers, NP fixes), pick a representation whose basic units already contain that context. This avoids redesigning the transformations for every new language or corpus.
  • I2. Extract derivations heuristically rather than with EM. Head/argument/adjunct rules convert treebank trees into explicit derivations, so the model can be estimated by simple counting. This outperformed EM-based grammar induction and could transfer to other formalisms that need hidden derivations, including those built from UD trees.
  • I3. Treat auxiliaries as recursive auxiliary trees. This keeps the lexical verb linked directly to its subject, whereas head percolation lets auxiliaries "steal" the dependency. It is a useful reminder that how heads are chosen shapes which dependencies a model can learn.
  • I4. Let probabilities constrain an unconstrained operation. Sister-adjunction is deliberately permitted anywhere, and the probability model decides where it is plausible. Pushing constraints from the grammar into the statistics is a design choice that can simplify grammar engineering.
  • I5. Future directions proposed in the paper: - Group elementary trees into families linked by transformations, such as active and passive forms of a verb, so they share statistics and reduce sparsity. - Use trees with several lexical anchors so that attachment decisions, such as PP attachment, can depend on more than one word.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of PennsylvaniaPhiladelphia · United States170 works · 60,739 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 161 works

Cite

Cite as David Chiang. 2000. Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar. Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/1075218.1075276

@inproceedings{chiang2000statistical,
  title = {{Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar}},
  author = {David Chiang},
  booktitle = {Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics},
  year = {2000},
  doi = {10.3115/1075218.1075276},
  url = {https://doi.org/10.3115/1075218.1075276}
}

References

22 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. B. Srinivas. 1997. Complexity of lexical descriptions: relevance to partial parsing . Ph.D. thesis, Univ. of Pennsylvania. find
  2. Daniel M. Bikel, Scott Miller, Richard Schwartz, and Ralph Weischedel. 1997. Nymble: a high-performance learning name- nder. In Proceedings of the Fifth Conference on Applied Natural Language Processing (ANLP 1997) , pages 194{ 201. find
  3. John Carroll and David Weir. 1997. Encoding frequency information in lexicalized grammars. In Proceedings of the Fifth International Workshop on Parsing Technologies (IWPT '97) , pages 8{17. find
  4. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of the First Meeting of the North American Chapter of the Association for Computational Linguistics (ANLP-NAACL2000) , pages 132{139.
  5. Ciprian Chelba and Frederick Jelinek. 1998. Exploiting syntactic structure for language modeling. In Proceedings of COLING-ACL '98 , pages 225{231. find
  6. John Chen and K. Vijay-Shanker. 2000. Automated extraction of TAGs from the Penn Treebank. In Proceedings of the Sixth International Workshop on Parsing Technologies (IWPT 2000) , pages 65{76. find
  7. Michael Collins. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annual Meeting of the Assocation for Computational Linguistics , pages 184{191. find
  8. Michael Collins. 1997. Three generative lexicalised models for statistical parsing. In Proceedings of the 35th Annual Meeting of the Assocation for Computational Linguistics , pages 16{23.
  9. Michael Collins. 1999. Head-driven statistical models for natural language parsing . Ph.D. thesis, Univ. of Pennsylvania. find
  10. Joshua Goodman. 1997. Global thresholding and multiple-pass parsing. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing (EMNLP-2) , pages 11{25. find
  11. Rebecca Hwa. 1998. An empirical evaluation of probabilistic lexicalized tree insertion grammars. In Proceedings of COLING-ACL '98 , pages 557{563. find
  12. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics , 24:613{632.
  13. David M. Magerman. 1995. Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting of the Assocation for Computational Linguistics , pages 276{283.
  14. Gunter Neumann. 1998. Automatic extraction of stochastic lexicalized tree grammars from treebanks. In Proceedings of the 4th International Workshop on TAG and Related Formalisms (TAG+4) , pages 120{123. find
  15. Owen Rambow, K. Vijay-Shanker, and David Weir. 1995. D-tree grammars. In Proceedings of the 33rd Annual Meeting of the Assocation for Computational Linguistics , pages 151{158. find
  16. Adwait Ratnaparkhi. 1996. A maximum-entropy model for part-of-speech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing , pages 1{10.
  17. Philip Resnik. 1992. Probabilistic tree-adjoining grammar as a framework for statistical natural language processing. In Proceedings of the Fourteenth International Conference on Computational Linguistics (COLING-92) , pages 418{424. find
  18. Yves Schabes and Stuart M. Shieber. 1994. An alternative conception of tree-adjoining derivation. Computational Linguistics , 20(1):91{124.
  19. Yves Schabes and Richard C. Waters. 1995. Tree insertion grammar: a cubic-time parsable formalism that lexicalizes context-free grammar without changing the trees produced. Computational Linguistics , 21:479{513. find
  20. Yves Schabes and Richard Waters. 1996. Stochastic lexicalized tree-insertion grammar. In H. Bunt and M. Tomita, editors, Recent Advances in Parsing Technology , pages 281{294. Kluwer Academic Press, London. find
  21. Yves Schabes. 1992. Stochastic lexicalized tree-adjoining grammars. In Proceedings of the Fourteenth International Conference on Computational Linguistics (COLING-92) , pages 426{432. find
  22. Fei Xia. 1999. Extracting tree adjoining grammars from bracketed corpora. In Proceedings of the 5th Natural Language Processing Paci c Rim Symposium (NLPRS-99) , pages 398{403. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chiang-2000-statistical-parsing-automatically-extracted-tree/