---
title: "Statistical Parsing with an Automatically-Extracted Tree Adjoining"
description: "Chiang argues that PCFG parsers capture word-to-word dependencies only indirectly, by passing… 22 references, cited by 65 papers here."
authors: ["David Chiang"]
year: 2000
venue: "Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P00-1058/"
doi: "10.3115/1075218.1075276"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/chiang-2000-statistical-parsing-automatically-extracted-tree/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/chiang-2000-statistical-parsing-automatically-extracted-tree/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2000](https://md.research.elamur.ai/free/en/papers/2000/) / Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar

# Statistical Parsing with an Automatically-Extracted Tree Adjoining Grammar

**Authors:** [David Chiang](https://md.research.elamur.ai/free/en/authors/david-chiang/) · **Year:** 2000 · **Venue:** [Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2000](https://md.research.elamur.ai/free/en/venues/acl/2000/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P00-1058/) · [PDF](https://aclanthology.org/P00-1058.pdf) · [DOI 10.3115/1075218.1075276](https://doi.org/10.3115/1075218.1075276) · [OpenAlex](https://openalex.org/W2110651511)

**Citations:** 163 citations (OpenAlex, 2026-10-14) · [65](https://md.research.elamur.ai/free/en/papers/chiang-2000-statistical-parsing-automatically-extracted-tree/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## 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
- **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.
- **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.
- **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.
- **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.
- **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 Pennsylvania](https://md.research.elamur.ai/free/en/universities/university-of-pennsylvania/) — University, Philadelphia, United States · 170 works · 60,739 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 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.

```bibtex
@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}
}
```

- [← previous Exploiting a Probabilistic Hierarchical Model for Generation](https://md.research.elamur.ai/free/en/papers/bangalore-2000-exploiting-probabilistic-hierarchical-model-generation/)
- [next → Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies](https://md.research.elamur.ai/free/en/papers/radev-2000-centroid-based-summarization-multiple-documents/)
- [↑ back to papers of 2000](https://md.research.elamur.ai/free/en/papers/2000/)

## 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](https://scholar.google.com/scholar?q=B%2E+Srinivas%2E+1997%2E+Complexity+of+lexical+descriptions%3A+relevance+to+partial+parsing+%2E+Ph%2ED%2E+thesis%2C+Univ%2E+of+Pennsylvania%2E)
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](https://scholar.google.com/scholar?q=Daniel+M%2E+Bikel%2C+Scott+Miller%2C+Richard+Schwartz%2C+and+Ralph+Weischedel%2E+1997%2E+Nymble%3A+a+high%2Dperformance+learning+name%2D+nder%2E+In+Proceedings+of+the+Fifth+Conference+on+Applied+Natural+Language+Processi)
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](https://scholar.google.com/scholar?q=John+Carroll+and+David+Weir%2E+1997%2E+Encoding+frequency+information+in+lexicalized+grammars%2E+In+Proceedings+of+the+Fifth+International+Workshop+on+Parsing+Technologies+%28IWPT+%2797%29+%2C+pages+8%7B17%2E)
4. Eugene Charniak. 2000. [A maximum-entropy-inspired parser](https://md.research.elamur.ai/free/en/papers/charniak-2000-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](https://scholar.google.com/scholar?q=Ciprian+Chelba+and+Frederick+Jelinek%2E+1998%2E+Exploiting+syntactic+structure+for+language+modeling%2E+In+Proceedings+of+COLING%2DACL+%2798+%2C+pages+225%7B231%2E)
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](https://scholar.google.com/scholar?q=John+Chen+and+K%2E+Vijay%2DShanker%2E+2000%2E+Automated+extraction+of+TAGs+from+the+Penn+Treebank%2E+In+Proceedings+of+the+Sixth+International+Workshop+on+Parsing+Technologies+%28IWPT+2000%29+%2C+pages+65%7B76%2E)
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](https://scholar.google.com/scholar?q=Michael+Collins%2E+1996%2E+A+new+statistical+parser+based+on+bigram+lexical+dependencies%2E+In+Proceedings+of+the+34th+Annual+Meeting+of+the+Assocation+for+Computational+Linguistics+%2C+pages+184%7B191%2E)
8. Michael Collins. 1997. [Three generative lexicalised models for statistical parsing](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/). 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](https://scholar.google.com/scholar?q=Michael+Collins%2E+1999%2E+Head%2Ddriven+statistical+models+for+natural+language+parsing+%2E+Ph%2ED%2E+thesis%2C+Univ%2E+of+Pennsylvania%2E)
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](https://scholar.google.com/scholar?q=Joshua+Goodman%2E+1997%2E+Global+thresholding+and+multiple%2Dpass+parsing%2E+In+Proceedings+of+the+Second+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%2D2%29+%2C+pages+11%7B25%2E)
11. Rebecca Hwa. 1998. An empirical evaluation of probabilistic lexicalized tree insertion grammars. In Proceedings of COLING-ACL '98 , pages 557{563. [find](https://scholar.google.com/scholar?q=Rebecca+Hwa%2E+1998%2E+An+empirical+evaluation+of+probabilistic+lexicalized+tree+insertion+grammars%2E+In+Proceedings+of+COLING%2DACL+%2798+%2C+pages+557%7B563%2E)
12. Mark Johnson. 1998. [PCFG models of linguistic tree representations](https://md.research.elamur.ai/free/en/papers/johnson-1998-pcfg-models-linguistic-tree-representations/). Computational Linguistics , 24:613{632.
13. David M. Magerman. 1995. [Statistical decision-tree models for parsing](https://md.research.elamur.ai/free/en/papers/magerman-1995-statistical-decision-tree-models-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](https://scholar.google.com/scholar?q=G%7Funter+Neumann%2E+1998%2E+Automatic+extraction+of+stochastic+lexicalized+tree+grammars+from+treebanks%2E+In+Proceedings+of+the+4th+International+Workshop+on+TAG+and+Related+Formalisms+%28TAG%2B4%29+%2C+pages+120%7B1)
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](https://scholar.google.com/scholar?q=Owen+Rambow%2C+K%2E+Vijay%2DShanker%2C+and+David+Weir%2E+1995%2E+D%2Dtree+grammars%2E+In+Proceedings+of+the+33rd+Annual+Meeting+of+the+Assocation+for+Computational+Linguistics+%2C+pages+151%7B158%2E)
16. Adwait Ratnaparkhi. 1996. [A maximum-entropy model for part-of-speech tagging](https://md.research.elamur.ai/free/en/papers/ratnaparkhi-1996-maximum-entropy-model-part-speech/). 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](https://scholar.google.com/scholar?q=Philip+Resnik%2E+1992%2E+Probabilistic+tree%2Dadjoining+grammar+as+a+framework+for+statistical+natural+language+processing%2E+In+Proceedings+of+the+Fourteenth+International+Conference+on+Computational+Linguis)
18. Yves Schabes and Stuart M. Shieber. 1994. [An alternative conception of tree-adjoining derivation](https://md.research.elamur.ai/free/en/papers/schabes-1994-alternative-conception-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](https://scholar.google.com/scholar?q=Yves+Schabes+and+Richard+C%2E+Waters%2E+1995%2E+Tree+insertion+grammar%3A+a+cubic%2Dtime+parsable+formalism+that+lexicalizes+context%2Dfree+grammar+without+changing+the+trees+produced%2E+Computational+Linguistics+%2C)
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](https://scholar.google.com/scholar?q=Yves+Schabes+and+Richard+Waters%2E+1996%2E+Stochastic+lexicalized+tree%2Dinsertion+grammar%2E+In+H%2E+Bunt+and+M%2E+Tomita%2C+editors%2C+Recent+Advances+in+Parsing+Technology+%2C+pages+281%7B294%2E+Kluwer+Academic+Press%2C+L)
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](https://scholar.google.com/scholar?q=Yves+Schabes%2E+1992%2E+Stochastic+lexicalized+tree%2Dadjoining+grammars%2E+In+Proceedings+of+the+Fourteenth+International+Conference+on+Computational+Linguistics+%28COLING%2D92%29+%2C+pages+426%7B432%2E)
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](https://scholar.google.com/scholar?q=Fei+Xia%2E+1999%2E+Extracting+tree+adjoining+grammars+from+bracketed+corpora%2E+In+Proceedings+of+the+5th+Natural+Language+Processing+Paci+c+Rim+Symposium+%28NLPRS%2D99%29+%2C+pages+398%7B403%2E)

*Updated 24 October 2026*