--- title: "Immediate-Head Parsing for Language Models — Charniak 2001" description: "Grammar-based language models for speech recognition had so far used strict left-to-right parsers." authors: ["Eugene Charniak"] year: 2001 venue: "Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics" source: "https://aclanthology.org/P01-1017/" doi: "10.3115/1073012.1073029" 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/charniak-2001-immediate-head-parsing-language-models/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/charniak-2001-immediate-head-parsing-language-models/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2001](https://md.research.elamur.ai/free/en/papers/2001/) / Immediate-Head Parsing for Language Models # Immediate-Head Parsing for Language Models **Authors:** [Eugene Charniak](https://md.research.elamur.ai/free/en/authors/eugene-charniak/) · **Year:** 2001 · **Venue:** Proceedings of the 39th 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/P01-1017/) · [PDF](https://aclanthology.org/P01-1017.pdf) · [DOI 10.3115/1073012.1073029](https://doi.org/10.3115/1073012.1073029) · [OpenAlex](https://openalex.org/W2155693943) **Citations:** 293 citations (openalex-snapshot · 2026-10-14) · [93](#cited-by) in our library, of the 140673 papers whose bibliographies we read ## Summary Grammar-based language models for speech recognition had so far used strict left-to-right parsers. These predict each word from earlier words and do not revise their estimates later. The most accurate statistical parsers work differently: they are "immediate-head" parsers, which condition everything inside a constituent on that constituent's lexical head, and this head can appear to the right of the material it conditions. Charniak tests whether this stronger parsing technology also yields better language models. He adapts his maximum-entropy-inspired generative parser so that it outputs true probabilities, which it can then sum over parses to score sentences. Two changes make this possible: hand-tuned interpolation smoothing replaces unnormalized scores, and explicit right-boundary conditioning replaces a multiplicative branching heuristic. The models are trained on Penn treebank data that has been converted to look like speech transcripts. Both resulting models beat a trigram baseline and the strongest earlier grammar-based model. The better one cuts perplexity by 24% and 14% respectively. The paper argues that better parsers, for example ones using prosody, could eventually make trigram-free language models practical. ## Key points - Two earlier systems serve as reference points, Chelba & Jelinek (C&J) and Roark, evaluated on the same data: - The trigram baseline scores about 167 perplexity. - The grammar-only models score 158.28 (C&J) and 152.26 (Roark). - Interpolating each with the trigram gives 148.90 and 137.26, using weights of 0.36 for the trigram and 0.64 for the grammar. - The parser builds each constituent top-down in a fixed order: - It first guesses the pre-terminal tag, then the lexical head, then the expansion. - The expansion starts from a head child and adds left and right siblings outward until a stop symbol is generated. - Each distribution conditions on at most one lexical item, except head prediction, which uses two. Trigram-like models use three. - The data was "speechified": - Punctuation and capitalization were removed. - The vocabulary was capped at 10,000 words, with all other words mapped to UNK. - All digits and symbols were replaced by N. - The right-branching bonus/penalty (1.2/0.8) was replaced by conditioning on whether a constituent ends at the sentence boundary. This costs about 0.1% in precision/recall but gives genuine probabilities. - The model is effectively a PCFG estimated from the Penn treebank, which guarantees a proper distribution over strings. The author also checked empirically that the individual conditional distributions sum to one. ## Interesting ideas - **Reuse a strong generative parser as a language model.** Any generative parser that computes a joint probability of tree and sentence also defines a sentence probability, obtained by summing over trees. Tasks that need sentence scoring can therefore inherit progress in parsing. - **Hand-craft smoothing instead of computing partition functions.** Careful hand-designed interpolation smoothing matched the accuracy of the unnormalized max-ent-style scoring while keeping the probabilities properly normalized. This is useful whenever a model must output calibrated probabilities rather than just rankings. - **Turn heuristics into conditioning features.** The ad hoc branching multipliers were replaced with an explicit conditioning variable for the right sentence boundary. This keeps the model principled at almost no accuracy cost, and the same move applies to other models carrying score "hacks." - **Sanity-check normalization empirically.** Sampling many random conditioning contexts and confirming that each distribution sums to one is a cheap test that catches smoothing bugs. - **Provisional left-to-right estimates.** For incremental decoding, a system can emit rough probabilities early and correct them once the true head appears. Redefining heads so they fall earlier, as the paper did inside noun phrases, reduces how often such corrections are needed. *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: [Machine translation](https://md.research.elamur.ai/free/en/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/) ## Cited by Cited by 93 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 87 not yet. - [Accurate Unlexicalized Parsing](https://md.research.elamur.ai/free/en/papers/aclbulk-2003-klein-accurate-unlexicalized-parsing/) - [Head-Driven Statistical Models for Natural Language Parsing](https://md.research.elamur.ai/free/en/papers/cl-2003-collins-head-driven-statistical-models-natural/) - [Training Tree Transducers](https://md.research.elamur.ai/free/en/papers/graehl-2004-training-tree-transducers/) - [The Importance of Syntactic Parsing and Inference in Semantic Role Labeling](https://md.research.elamur.ai/free/en/papers/punyakanok-2008-importance-syntactic-parsing-inference-semantic/) - [Context-Sensitive Convolution Tree Kernel for Pronoun Resolution](https://md.research.elamur.ai/free/en/papers/zhou-2008-context-sensitive-convolution-tree-kernel/) - [Global Learning of Noun Phrase Anaphoricity in Coreference Resolution via Label Propagation](https://md.research.elamur.ai/free/en/papers/zhou-2009-global-learning-noun-phrase-anaphoricity/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{charniak2001immediate, title = {{Immediate-Head Parsing for Language Models}}, author = {Charniak, Eugene}, booktitle = {Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics}, year = {2001}, doi = {10.3115/1073012.1073029}, url = {https://doi.org/10.3115/1073012.1073029} } ``` - [← previous Identification des reprises et interprétation automatique des expressions pronominales dans des textes en français](https://md.research.elamur.ai/free/en/papers/trouilleux-2001-identification-reprises-interpretation-automatique/) - [next → Knowledge-Free Induction of Inflectional Morphologies](https://md.research.elamur.ai/free/en/papers/aclbulk-2001-schone-knowledge-free-induction-inflectional-morphologies/) - [↑ back to papers of 2001](https://md.research.elamur.ai/free/en/papers/2001/) ## References 6 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. B OD , R. What is the minimal set of fragments that achieves maximal parse accuracy. In Proceedings of Association for Computational Linguistics 2001 . 2001. [find](https://scholar.google.com/scholar?q=B+OD+%2C+R%2E+What+is+the+minimal+set+of+fragments+that+achieves+maximal+parse+accuracy%2E+In+Proceedings+of+Association+for+Computational+Linguistics+2001+%2E+2001%2E) 2. C HARNIAK , E. Tree-bank grammars. In Proceedings of the Thirteenth National Conference on Artificial Intelligence . AAAI Press/MIT Press, Menlo Park, 1996, 1031– 1036. 14. R ATNAPARKHI , A. Learning to parse natural [find](https://scholar.google.com/scholar?q=C+HARNIAK+%2C+E%2E+Tree%2Dbank+grammars%2E+In+Proceedings+of+the+Thirteenth+National+Conference+on+Artificial+Intelligence+%2E+AAAI+Press%2FMIT+Press%2C+Menlo+Park%2C+1996%2C+1031%E2%80%93+1036%2E+14%2E+R+ATNAPARKHI+%2C+A%2E+Learning+) 3. C HARNIAK , E. A maximum-entropy-language with maximum entropy models. Ma-inspired parser. In Proceedings of the 2000 chine Learning 34 1/2/3 (1999), 151–176. Conference of the North American Chapter of 15. R OARK , B. Probabilistic top-down parsing the Association for Computational Linguistics . an… [find](https://scholar.google.com/scholar?q=C+HARNIAK+%2C+E%2E+A+maximum%2Dentropy%2Dlanguage+with+maximum+entropy+models%2E+Ma%2Dinspired+parser%2E+In+Proceedings+of+the+2000+chine+Learning+34+1%2F2%2F3+%281999%29%2C+151%E2%80%93176%2E+Conference+of+the+North+American+Chapter+) 4. C HELBA , C. AND J ELINEK , F. Exploiting 16. S TOLCKE , A. An efficient probabilistic syntactic structure for language modeling. In context-free parsing algorithm that computes Proceedings for COLING-ACL 98 . ACL, New prefix probabilities. Computational Linguistics Brunswick NJ, 1998, 225–231. 21 (… [find](https://scholar.google.com/scholar?q=C+HELBA+%2C+C%2E+AND+J+ELINEK+%2C+F%2E+Exploiting+16%2E+S+TOLCKE+%2C+A%2E+An+efficient+probabilistic+syntactic+structure+for+language+modeling%2E+In+context%2Dfree+parsing+algorithm+that+computes+Proceedings+for+COLING) 5. C HI , Z. AND G EMAN , S. Estimation of 17. S TOLCKE , A. AND S EGAL , J. Precise nprobabilistic context-free grammars. Computa-gram probabilities from stochastic context-free tional Linguistics 24 2 (1998), 299–306. grammars. In Proceedings of the 32th Annual [find](https://scholar.google.com/scholar?q=C+HI+%2C+Z%2E+AND+G+EMAN+%2C+S%2E+Estimation+of+17%2E+S+TOLCKE+%2C+A%2E+AND+S+EGAL+%2C+J%2E+Precise+nprobabilistic+context%2Dfree+grammars%2E+Computa%2Dgram+probabilities+from+stochastic+context%2Dfree+tional+Linguistics+24+2+) 6. C OLLINS , M. J. Three generative lexicalized Meeting of the Association for Computational models for statistical parsing. In Proceedings Linguistics . 1994, 74–79. of the 35th Annual Meeting of the ACL . 1997, 16–23. 12. M AGERMAN , D. M. Statistical decision-tree models for parsing. In Proceedings… [find](https://scholar.google.com/scholar?q=C+OLLINS+%2C+M%2E+J%2E+Three+generative+lexicalized+Meeting+of+the+Association+for+Computational+models+for+statistical+parsing%2E+In+Proceedings+Linguistics+%2E+1994%2C+74%E2%80%9379%2E+of+the+35th+Annual+Meeting+of+the+A)