---
title: "Towards History-based Grammars — paper by Black et al. (1993)"
description: "The authors propose History-based Grammars (HBG), a generative model in which the probability of… 11 references, cited by 65 papers here."
authors: ["Ezra Black", "Fred Jelinek", "John Lafrerty", "David M. Magerman", "Robert Mercer", "Salim Roukos"]
year: 1993
venue: "31st Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P93-1005/"
doi: "10.3115/981574.981579"
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/black-1993-history-based-grammars-richer-models/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/black-1993-history-based-grammars-richer-models/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1993](https://md.research.elamur.ai/free/en/papers/1993/) / Towards History-based Grammars: Using Richer Models for Probabilistic Parsing

# Towards History-based Grammars: Using Richer Models for Probabilistic Parsing

**Authors:** [Ezra Black](https://md.research.elamur.ai/free/en/authors/ezra-black/), [Fred Jelinek](https://md.research.elamur.ai/free/en/authors/fred-jelinek/), John Lafrerty, [David M. Magerman](https://md.research.elamur.ai/free/en/authors/david-m-magerman/), [Robert Mercer](https://md.research.elamur.ai/free/en/authors/robert-l-mercer/) and [Salim Roukos](https://md.research.elamur.ai/free/en/authors/salim-roukos/) · **Year:** 1993 · **Venue:** [31st Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 1993](https://md.research.elamur.ai/free/en/venues/acl/1993/)) · **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/P93-1005/) · [PDF](https://aclanthology.org/P93-1005.pdf) · [DOI 10.3115/981574.981579](https://doi.org/10.3115/981574.981579) · [OpenAlex](https://openalex.org/W2167434254)

**Citations:** 146 citations (OpenAlex, 2026-10-14) · [65](https://md.research.elamur.ai/free/en/papers/black-1993-history-based-grammars-richer-models/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper addresses structural ambiguity in parsing. Earlier probabilistic models, such as the standard P-CFG, condition each rule choice on very little context. The authors propose History-based Grammars (HBG), a generative model in which the probability of expanding each node may depend on anything already built in the leftmost derivation. This includes words, syntactic and semantic categories, lexical heads and tree structure. Decision trees group derivation histories into equivalence classes, which makes such rich conditioning estimable. In this implementation, only the path from the current node to the root and the child index are examined.

The experiments use a broad-coverage feature-based unification grammar, IBM computer-manual text and the Lancaster Treebank as the gold standard. On 760 test sentences of 7–17 words, HBG raises the Viterbi rate from 60% (P-CFG) to 75%, cutting errors by 37%. The result suggests that statistical models learned from treebanks can take over much of the disambiguation burden. Traditionally, grammarians handled that burden through manual tuning.

## Key points
- **Data and domain:**
  - The vocabulary is the 3,000 most frequent words from a 600,000-word corpus of 10 computer manuals.
  - The authors kept a few million words of fully covered sentences, drawn from 40M words of manuals.
  - Gold parses come from the Lancaster Treebank, which uses 17 non-terminal labels and 240 tags.
- **Grammar:**
  - It is a unification grammar with 21 features and 672 rule templates, of which 400 were used on 15,000 sentences.
  - Its more than 10,000 non-terminal labels are mapped onto Treebank labels for evaluation. Tags are ignored in that evaluation.
- **Evaluation metrics:**
  - The *any-consistent rate* is the share of sentences where the grammar proposes the correct parse anywhere among its candidates. It reaches 90%.
  - The *Viterbi rate* is the share of sentences where the model's top parse is correct. It is 60% for P-CFG and 75% for HBG.
  - A simpler head-annotated model scores 66%.
- **Baseline training:** The P-CFG baseline was trained with a Treebank-constrained version of the Inside-Outside algorithm.
- **HBG estimation:**
  - A decision tree models only the rule-template component of HBG. The other four factors use n-gram models with deleted interpolation.
  - Training used about 9,000 sentence-tree pairs, yielding about 240,000 tuples and a tree of roughly 40,000 nodes.
  - Building the tree took 18 hours and produced a model of nearly 100 MB.

## Interesting ideas
- **Two separate metrics.** The paper measures grammar coverage (any-consistent rate) apart from model selection (Viterbi rate). This shows whether errors come from a missing parse or a wrong choice, and it is a useful diagnostic for any parse-and-rank system.
- **Division of labour.** The grammarian works only on coverage, while statistics learned from a treebank pick the best parse. This clean split could organise rule-based pipelines for low-resource languages.
- **Decision trees over histories.** Asking questions about the derivation history lets a model use rich context without an explosion of parameters. The same trick could be applied to any sequential prediction task with structured context.
- **Bit-string encoding of categories and words.** Similar items share prefixes in their codes. Categories and rules were coded by hand, and words via mutual-information clustering. This lets the decision tree ask questions at varying levels of granularity, which helps generalise from sparse data.
- **Functional parent versus immediate parent.** The functional parent skips over unit productions such as NP2 → NP1, so that informative context is not hidden behind uninformative chain nodes. This is relevant to any tree-based feature extraction.

*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

- [IBM Research - Thomas J. Watson Research Center](https://md.research.elamur.ai/free/en/labs/ibm-research-thomas-j-watson-research-center/) — Research institute, Yorktown Heights, United States · 41 works · 46,197 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 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

## Cite

Cite as: Ezra Black, Fred Jelinek, John Lafrerty, David M. Magerman, Robert Mercer and Salim Roukos. 1993. Towards History-based Grammars: Using Richer Models for Probabilistic Parsing. 31st 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{black1993history,
  title = {{Towards History-based Grammars: Using Richer Models for Probabilistic Parsing}},
  author = {Ezra Black, Fred Jelinek, John Lafrerty, David M. Magerman, Robert Mercer and Salim Roukos},
  booktitle = {31st Annual Meeting of the Association for Computational Linguistics},
  year = {1993},
  doi = {10.3115/981574.981579},
  url = {https://doi.org/10.3115/981574.981579}
}
```

- [← previous Two-level Description of Turkish Morphology](https://md.research.elamur.ai/free/en/papers/oflazer-1993-two-level-description-turkish-morphology/)
- [next → Structural Ambiguity and Lexical Relations](https://md.research.elamur.ai/free/en/papers/hindle-1993-structural-ambiguity-lexical-relations/)
- [↑ back to papers of 1993](https://md.research.elamur.ai/free/en/papers/1993/)

## References

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

1. Baker, J. K., 1975. Stochastic Modeling for Automatic Speech Understanding. In Speech Recognition, edited by Raj Reddy, Academic Press, pp. 521-542. [find](https://scholar.google.com/scholar?q=Baker%2C+J%2E+K%2E%2C+1975%2E+Stochastic+Modeling+for+Automatic+Speech+Understanding%2E+In+Speech+Recognition%2C+edited+by+Raj+Reddy%2C+Academic+Press%2C+pp%2E+521%2D542%2E)
2. Brent, M. R. 1991. Automatic Acquisition of Subcategorization Frames from Untagged Free-text Corpora. In Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics. Berkeley, California. [find](https://scholar.google.com/scholar?q=Brent%2C+M%2E+R%2E+1991%2E+Automatic+Acquisition+of+Subcategorization+Frames+from+Untagged+Free%2Dtext+Corpora%2E+In+Proceedings+of+the+29th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2E+Berkel)
3. Brill, E., Magerman, D., Marcus, M., and Santorini, B. 1990. Deducing Linguistic Structure from the Statistics of Large Corpora. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania. [find](https://scholar.google.com/scholar?q=Brill%2C+E%2E%2C+Magerman%2C+D%2E%2C+Marcus%2C+M%2E%2C+and+Santorini%2C+B%2E+1990%2E+Deducing+Linguistic+Structure+from+the+Statistics+of+Large+Corpora%2E+In+Proceedings+of+the+June+1990+DARPA+Speech+and+Natural+Language+Works)
4. Brown, P. F., Della Pietra, V. J., deSouza, P. V., Lai, J. C., and Mercer, R. L. Class-based ngram Models of Natural Language. In Proceedings of ~he IBM Natural Language ITL, March, 1990. Paris, France. [find](https://scholar.google.com/scholar?q=Brown%2C+P%2E+F%2E%2C+Della+Pietra%2C+V%2E+J%2E%2C+deSouza%2C+P%2E+V%2E%2C+Lai%2C+J%2E+C%2E%2C+and+Mercer%2C+R%2E+L%2E+Class%2Dbased+ngram+Models+of+Natural+Language%2E+In+Proceedings+of+%7Ehe+IBM+Natural+Language+ITL%2C+March%2C+1990%2E+Paris%2C+Franc)
5. Church, K. 1988. [A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text](https://md.research.elamur.ai/free/en/papers/church-1988-stochastic-parts-program-noun-phrase/). In Proceedings of the Second Conference on Applied Natural Language Processing. Austin, Texas.
6. Gale, W. A. and Church, K. 1990. Poor Estimates of Context are Worse than None. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania. [find](https://scholar.google.com/scholar?q=Gale%2C+W%2E+A%2E+and+Church%2C+K%2E+1990%2E+Poor+Estimates+of+Context+are+Worse+than+None%2E+In+Proceedings+of+the+June+1990+DARPA+Speech+and+Natural+Language+Workshop%2E+Hidden+Valley%2C+Pennsylvania%2E)
7. Harrison, M. A. 1978. Introduction to Formal Language Theory. Addison-Wesley Publishing Company. [find](https://scholar.google.com/scholar?q=Harrison%2C+M%2E+A%2E+1978%2E+Introduction+to+Formal+Language+Theory%2E+Addison%2DWesley+Publishing+Company%2E)
8. Hindle, D. and Rooth, M. 1990. Structural Ambiguity and Lexical Relations. In Proceedings of the :June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania. :Jelinek, F. 1985. Self-organizing Language Modeling for Speech Recognition. IBM Report. [find](https://scholar.google.com/scholar?q=Hindle%2C+D%2E+and+Rooth%2C+M%2E+1990%2E+Structural+Ambiguity+and+Lexical+Relations%2E+In+Proceedings+of+the+%3AJune+1990+DARPA+Speech+and+Natural+Language+Workshop%2E+Hidden+Valley%2C+Pennsylvania%2E+%3AJelinek%2C+F%2E+1985%2E+)
9. Magerman, D. M. and Marcus, M. P. 1991. Pearl: A Probabilistic Chart Parser. In Proceedings of the February 1991 DARPA Speech and Natural Language Workshop. Asilomar, California. [find](https://scholar.google.com/scholar?q=Magerman%2C+D%2E+M%2E+and+Marcus%2C+M%2E+P%2E+1991%2E+Pearl%3A+A+Probabilistic+Chart+Parser%2E+In+Proceedings+of+the+February+1991+DARPA+Speech+and+Natural+Language+Workshop%2E+Asilomar%2C+California%2E)
10. Derouault, A., and Merialdo, B., 1985. Probabilistic Grammar for Phonetic to French Transcription. ICASSP 85 Proceedings. Tampa, Florida, pp. 1577-1580. [find](https://scholar.google.com/scholar?q=Derouault%2C+A%2E%2C+and+Merialdo%2C+B%2E%2C+1985%2E+Probabilistic+Grammar+for+Phonetic+to+French+Transcription%2E+ICASSP+85+Proceedings%2E+Tampa%2C+Florida%2C+pp%2E+1577%2D1580%2E)
11. Sharman, R. A., :Jelinek, F., and Mercer, R. 1990. Generating a Grammar for Statistical Training. In Proceedings of the :June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania. [find](https://scholar.google.com/scholar?q=Sharman%2C+R%2E+A%2E%2C+%3AJelinek%2C+F%2E%2C+and+Mercer%2C+R%2E+1990%2E+Generating+a+Grammar+for+Statistical+Training%2E+In+Proceedings+of+the+%3AJune+1990+DARPA+Speech+and+Natural+Language+Workshop%2E+Hidden+Valley%2C+Pennsylvan)

*Updated 24 October 2026*