--- title: "Statistical Decision-Tree Models for Parsing — Magerman 1995" description: "Magerman presents SPATTER, a statistical parser that learns every parsing choice from a treebank instead of relying on a hand-built grammar." authors: ["David M. Magerman"] year: 1995 venue: "33rd Annual Meeting of the Association for Computational Linguistics" source: "https://aclanthology.org/P95-1037/" doi: "10.3115/981658.981695" 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/magerman-1995-statistical-decision-tree-models-parsing/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/magerman-1995-statistical-decision-tree-models-parsing/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1995](https://md.research.elamur.ai/free/en/papers/1995/) / Statistical Decision-Tree Models for Parsing # Statistical Decision-Tree Models for Parsing **Authors:** David M. Magerman · **Year:** 1995 · **Venue:** 33rd Annual Meeting of the 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/P95-1037/) · [PDF](https://aclanthology.org/P95-1037.pdf) · [DOI 10.3115/981658.981695](https://doi.org/10.3115/981658.981695) · [OpenAlex](https://openalex.org/W2153439141) **Citations:** 567 citations (openalex-snapshot · 2026-10-14) · [165](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## Summary Magerman presents SPATTER, a statistical parser that learns every parsing choice from a treebank instead of relying on a hand-built grammar. These choices include part-of-speech tags, constituent structure and constituent labels. Each choice is scored by a decision-tree model that selects which context features to use, such as words, relations between words, and already-built constituents. The probability of a full tree is the product of its decision probabilities. Search combines a stack decoder with breadth-first expansion and probabilistic pruning. The paper also shows formally that decision trees match interpolated n-gram models in expressive power. Their real advantage is that they can be learned automatically when the context space is huge. SPATTER beat IBM's long-developed grammar-based parser on a computer-manuals task. On Penn Treebank WSJ sentences of up to 40 words, it reached about 86% precision and 86% recall, with 1.3 crossing brackets per sentence. The work matters because it showed that a richly lexicalized statistical model, trained only on annotated data, can outperform expert-written grammars on broad-coverage parsing. ## Key points - Data: Penn Treebank v2, WSJ portion, with 46 POS tags and 27 non-terminal labels. Training used sections 02–21 (about 40,000 sentences) and testing used section 00 (1,920 sentences). Only sentences of 40 words or fewer were evaluated. - PARSEVAL results for sentences of up to 40 words were roughly 86% precision, 86% recall and 1.3 crossings per sentence. For sentences of 10–20 words, the figures were about 91% precision, 90% recall and 0.5 crossings. - Against the IBM computer-manuals parser, which had over ten years of grammar development, SPATTER produced zero-crossing parses for 76% of sentences versus IBM's 69%. - The parser takes raw words and weighs all tag sequences probabilistically rather than committing to one pre-tagged sequence. On an SGI R4400 machine equipped with 160 MB of RAM, the average parsing time was roughly 12 seconds for each sentence. - Sections 00 and 01 were kept out of training because they carry coreference annotation for a separate project. Using them could have biased later coreference experiments. ## Interesting ideas - **Parsing as a sequence of scored decisions.** Treating a tree as a chain of probabilistic choices lets one model family handle tagging, bracketing and labeling. The same framing works for any structured-prediction task. - **Decision trees as learned smoothing.** The author shows a tree is an interpolated n-gram model in which only the leaf's history gets weight. This is a useful way to explain why feature-selecting models can scale to very large contexts where full deleted interpolation becomes impractical. - **Binary encoding of words.** Words are represented by about 30 yes/no questions that together identify each word. This lets a tree split on partial lexical information, which could help low-resource or morphologically rich vocabularies such as Ukrainian. - **No hard commitment to upstream predictions.** Keeping all tag hypotheses alive, weighted by probability, avoids the cascading errors of a pipeline. The same approach applies to tokenization or NER feeding into later stages. - **Careful split hygiene.** Reserving annotated sections needed by a downstream study, and reporting results by sentence length, are good evaluation habits for any shared corpus. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/) Topics: [Treebanks](https://md.research.elamur.ai/free/en/topics/treebanks/) · [Part-of-speech tagging](https://md.research.elamur.ai/free/en/topics/part-of-speech-tagging/) ## Cited by Cited by 165 papers of our library cite it (of the 140884 whose bibliographies we read); 23 of them have a page here, 142 not yet. - [Corpus Variation and Parser Performance](https://md.research.elamur.ai/free/en/papers/aclbulk-2001-gildea-corpus-variation-parser-performance/) - [Accurate Unlexicalized Parsing](https://md.research.elamur.ai/free/en/papers/aclbulk-2003-klein-accurate-unlexicalized-parsing/) - [Deterministic Dependency Parsing of English Text](https://md.research.elamur.ai/free/en/papers/aclbulk-2004-nivre-deterministic-dependency-parsing-english-text/) - [Supertagging: An Approach to Almost Parsing](https://md.research.elamur.ai/free/en/papers/bangalore-1999-supertagging-approach-almost-parsing/) - [A Dependency Treebank for English](https://md.research.elamur.ai/free/en/papers/bank-2002-rambow-dependency-treebank-english/) - [Using the Penn Treebank to Evaluate Non-Treebank Parsers](https://md.research.elamur.ai/free/en/papers/bank-2004-ringger-penn-treebank-evaluate-non-treebank/) - [Parsing Noun Phrases in the Penn Treebank](https://md.research.elamur.ai/free/en/papers/bank-2011-vadas-parsing-noun-phrases-penn-treebank/) - [Immediate-Head Parsing for Language Models](https://md.research.elamur.ai/free/en/papers/charniak-2001-immediate-head-parsing-language-models/) - [Hierarchical Phrase-Based Translation](https://md.research.elamur.ai/free/en/papers/chiang-2007-hierarchical-phrase-based-translation/) - [Head-Driven Statistical Models for Natural Language Parsing](https://md.research.elamur.ai/free/en/papers/cl-2003-collins-head-driven-statistical-models-natural/) - [Three Generative, Lexicalised Models for Statistical Parsing](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/) - [A Statistical Parser for Czech](https://md.research.elamur.ai/free/en/papers/collins-1999-statistical-parser-czech/) - [A Novel Discourse Parser Based on Support Vector Machine Classification](https://md.research.elamur.ai/free/en/papers/duverle-2009-novel-discourse-parser-based-support/) - [HILDA: A Discourse Parser Using Support Vector Machine Classification](https://md.research.elamur.ai/free/en/papers/hernault-2010-hilda-discourse-parser-support-vector/) - [A Semi-Supervised Approach to Improve Classification of Infrequent Discourse Relations Using Feature Vector Extension](https://md.research.elamur.ai/free/en/papers/hernault-2010-semi-supervised-approach-improve-classification/) - [CODRA: A Novel Discriminative Framework for Rhetorical Analysis](https://md.research.elamur.ai/free/en/papers/joty-2015-codra-novel-discriminative-framework-rhetorical/) - [Syntactic disambiguation using presupposition resolution](https://md.research.elamur.ai/free/en/papers/knott-2003-syntactic-disambiguation-presupposition-resolution/) - [Name Tagging with Word Clusters and Discriminative Training](https://md.research.elamur.ai/free/en/papers/miller-2004-name-tagging-word-clusters-discriminative/) - [MaltParser: A Data-Driven Parser-Generator for Dependency Parsing](https://md.research.elamur.ai/free/en/papers/nivre-2006-maltparser-data-driven-parser-generator/) - [CoNLL-X Shared Task on Multilingual Dependency Parsing](https://md.research.elamur.ai/free/en/papers/parsers-2006-buchholz-conll-x-shared-task-multilingual/) - [A Maximum Entropy Model for Part-Of-Speech Tagging](https://md.research.elamur.ai/free/en/papers/ratnaparkhi-1996-maximum-entropy-model-part-speech/) - [A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model](https://md.research.elamur.ai/free/en/papers/shen-2008-new-string-dependency-machine-translation/) - [Sentence Level Discourse Parsing using Syntactic and Lexical Information](https://md.research.elamur.ai/free/en/papers/soricut-2003-sentence-level-discourse-parsing-syntactic/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{magerman1995statistical, title = {{Statistical Decision-Tree Models for Parsing}}, author = {Magerman, David M.}, booktitle = {33rd Annual Meeting of the Association for Computational Linguistics}, year = {1995}, doi = {10.3115/981658.981695}, url = {https://doi.org/10.3115/981658.981695} } ``` - [← previous Reflections on the history and present state of MT](https://md.research.elamur.ai/free/en/papers/hutchins-1995-reflections-history-present-state-mt/) - [next → Text Chunking using Transformation-Based Learning](https://md.research.elamur.ai/free/en/papers/ramshaw-1995-text-chunking-transformation-based-learning/) - [↑ back to papers of 1995](https://md.research.elamur.ai/free/en/papers/1995/) ## References 8 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. L. R. Bahl, P. F. Brown, P. V. deSouza, and R. L. Mercer. 1989. A tree-based statistical language model for natural language speech recognition. [find](https://scholar.google.com/scholar?q=L%2E+R%2E+Bahl%2C+P%2E+F%2E+Brown%2C+P%2E+V%2E+deSouza%2C+and+R%2E+L%2E+Mercer%2E+1989%2E+A+tree%2Dbased+statistical+language+model+for+natural+language+speech+recognition%2E) 2. IEEE ~Pransactions on Acoustics, Speech, and Signal Processing, Vol. 36, No. 7, pages 1001-1008. [find](https://scholar.google.com/scholar?q=IEEE+%7EPransactions+on+Acoustics%2C+Speech%2C+and+Signal+Processing%2C+Vol%2E+36%2C+No%2E+7%2C+pages+1001%2D1008%2E) 3. L. E. Baum. 1972. An inequality and associated maximization technique in statistical estimation of probabilistic functions of markov processes. Inequalities, Vol. 3, pages 1-8. [find](https://scholar.google.com/scholar?q=L%2E+E%2E+Baum%2E+1972%2E+An+inequality+and+associated+maximization+technique+in+statistical+estimation+of+probabilistic+functions+of+markov+processes%2E+Inequalities%2C+Vol%2E+3%2C+pages+1%2D8%2E) 4. E. Black and et al. 1991. A procedure for quantitatively comparing the syntactic coverage of english grammars. Proceedings o/ the February 1991 [find](https://scholar.google.com/scholar?q=E%2E+Black+and+et+al%2E+1991%2E+A+procedure+for+quantitatively+comparing+the+syntactic+coverage+of+english+grammars%2E+Proceedings+o%2F+the+February+1991) 5. DARPA Speech and Natural Language Workshop, pages 306-311. E. Black, R. Garside, and G. Leech. 1993. [find](https://scholar.google.com/scholar?q=DARPA+Speech+and+Natural+Language+Workshop%2C+pages+306%2D311%2E+E%2E+Black%2C+R%2E+Garside%2C+and+G%2E+Leech%2E+1993%2E) 6. Statistically-driven computer grammars of english: the ibm/lancaster approach. Rodopi, Atlanta, Georgia. [find](https://scholar.google.com/scholar?q=Statistically%2Ddriven+computer+grammars+of+english%3A+the+ibm%2Flancaster+approach%2E+Rodopi%2C+Atlanta%2C+Georgia%2E) 7. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. 1984. Ci~ssi]ication and Regression Trees. Wadsworth and Brooks, Pacific Grove, California. [find](https://scholar.google.com/scholar?q=L%2E+Breiman%2C+J%2E+H%2E+Friedman%2C+R%2E+A%2E+Olshen%2C+and+C%2E+J%2E+Stone%2E+1984%2E+Ci%7Essi%5Dication+and+Regression+Trees%2E+Wadsworth+and+Brooks%2C+Pacific+Grove%2C+California%2E) 8. P. F. Brown, V. Della Pietra, P. V. deSouza, J. C. Lai, and R. L. Mercer. 1992. "Class-based n-gram models of natural language." Computational Linguistics, 18(4), pages 467-479. 1994. Natural Language Parsing as Statistical Pattern Recognition. Doctoral D. M. Magerman. dissertation. Stanford Univers… [find](https://scholar.google.com/scholar?q=P%2E+F%2E+Brown%2C+V%2E+Della+Pietra%2C+P%2E+V%2E+deSouza%2C+J%2E+C%2E+Lai%2C+and+R%2E+L%2E+Mercer%2E+1992%2E+%22Class%2Dbased+n%2Dgram+models+of+natural+language%2E%22+Computational+Linguistics%2C+18%284%29%2C+pages+467%2D479%2E+1994%2E+Natural+Language)