---
title: "Improving nonparameteric Bayesian inference: experiments on"
description: "The paper asks how much the design and inference details of adaptor grammars matter. 23 references, cited by 64 papers here."
authors: ["Mark Johnson", "Sharon Goldwater"]
year: 2009
venue: "Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics"
source: "https://aclanthology.org/N09-1036/"
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/johnson-2009-improving-nonparameteric-bayesian-inference-experiments/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/johnson-2009-improving-nonparameteric-bayesian-inference-experiments/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / Improving nonparameteric Bayesian inference: experiments on unsupervised word segmentation with adaptor grammars

# Improving nonparameteric Bayesian inference: experiments on unsupervised word segmentation with adaptor grammars

**Authors:** [Mark Johnson](https://md.research.elamur.ai/free/en/authors/mark-johnson/) and [Sharon Goldwater](https://md.research.elamur.ai/free/en/authors/sharon-goldwater/) · **Year:** 2009 · **Venue:** [Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/naacl/) ([NAACL 2009](https://md.research.elamur.ai/free/en/venues/naacl/2009/)) · **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/N09-1036/) · [PDF](https://aclanthology.org/N09-1036.pdf) · [OpenAlex](https://openalex.org/W7099414206)

**Citations:** 0 citations (OpenAlex, 2026-10-14) · [64](https://md.research.elamur.ai/free/en/papers/johnson-2009-improving-nonparameteric-bayesian-inference-experiments/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
The paper asks how much the design and inference details of adaptor grammars matter. Adaptor grammars are a grammar-based framework for building hierarchical nonparametric Bayesian models that learn reusable units, such as words, syllables and collocations, along with their probabilities. The authors test this on unsupervised word segmentation, using the Brent version of the Bernstein-Ratner corpus of child-directed speech in unsegmented phonemic form. They compare three grammars: unigram, collocation and collocation-syllable. They also vary several choices:
- CRP versus Pitman-Yor adaptors;
- Bayesian sampling of the adaptor hyperparameters instead of fixing them;
- batch versus incremental initialization of the Gibbs sampler;
- a new step called table label resampling.

These choices change accuracy dramatically. The best setup reaches an 87% word token f-score, an error reduction of more than 35% over the best earlier result on this corpus. The lesson extends beyond segmentation: in nonparametric Bayesian models, inference and hyperparameter decisions can matter as much as the model itself.

## Key points
- The headline result is an 87% token f-score on the Brent/Bernstein-Ratner corpus, cutting errors by more than 35% compared with Johnson (2008).
- Sampling the adaptor hyperparameters raised the collocation-syllable grammar's accuracy by almost 10%.
- The unigram adaptor grammar reproduces the Goldwater et al. (2006a) unigram model and shares its tendency to undersegment. Modelling collocations explicitly reduces this problem.
- In runs of 2,000 iterations, incremental initialization gave better f-scores, even though its parses had lower posterior probability than those from batch initialization.
- Without table label resampling, the collocation-syllable sampler failed to burn in or mix within 2,000 iterations. The authors released the inference software from Mark Johnson's Brown University page.

## Interesting ideas
- **Resampling cached units.** Table label resampling re-analyses a cached unit, such as a collocation, and thereby updates every sentence that uses it in a single move. Block moves like this could help any hierarchical sampler that otherwise gets stuck in local configurations.
- **Inferring hyperparameters.** Putting the concentration and discount parameters inside the inference, rather than tuning them by hand, removes manual search. It can also produce large accuracy gains in other nonparametric models.
- **Posterior versus accuracy.** The paper keeps "best under the model" separate from "best on the metric." Tracking both the posterior probability of samples and the task score shows whether gains come from the model or from search biases, such as greedy initialization favouring short words.
- **Grammar as a modelling interface.** Encoding linguistic hypotheses (words, syllables, collocations) as interchangeable grammars over one generic inference engine allows quick comparison of structural assumptions. The same approach could be used to explore Ukrainian morphology or other segmentation tasks.

*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

- [Brown University](https://md.research.elamur.ai/free/en/universities/brown-university/) — University, Providence, United States · 76 works · 25,952 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

🧭 Topics (1): [✂️ Tokenization & segmentation](https://md.research.elamur.ai/free/en/topics/tokenization/) · 119 works

## Cite

Cite as: Mark Johnson and Sharon Goldwater. 2009. Improving nonparameteric Bayesian inference: experiments on unsupervised word segmentation with adaptor grammars. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.

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

```bibtex
@inproceedings{johnson2009improving,
  title = {{Improving nonparameteric Bayesian inference: experiments on unsupervised word segmentation with adaptor grammars}},
  author = {Mark Johnson and Sharon Goldwater},
  booktitle = {Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://aclanthology.org/N09-1036/}
}
```

- [← previous Improving the Arabic Pronunciation Dictionary for Phone and Word Recognition with Linguistically-Based Pronunciation Rules](https://md.research.elamur.ai/free/en/papers/biadsy-2009-improving-arabic-pronunciation-dictionary-phone/)
- [next → A global model for joint lemmatization and part-of-speech prediction](https://md.research.elamur.ai/free/en/papers/toutanova-2009-global-model-joint-lemmatization-part/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## References

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

1. N. Bernstein-Ratner. 1987. The phonology of parent-child speech. In K. Nelson and A. van Kleeck, editors, Children’s Language, volume 6. Erlbaum, Hillsdale, NJ. [find](https://scholar.google.com/scholar?q=N%2E+Bernstein%2DRatner%2E+1987%2E+The+phonology+of+parent%2Dchild+speech%2E+In+K%2E+Nelson+and+A%2E+van+Kleeck%2C+editors%2C+Children%E2%80%99s+Language%2C+volume+6%2E+Erlbaum%2C+Hillsdale%2C+NJ%2E)
2. Daniel Blanchard and Jeffrey Heinz. 2008. Improving word segmentation by simultaneously learning phonotactics. In CoNLL 2008: Proceedings of the Twelfth Conference on Computational Natural Language Learning, pages 65–72, Manchester, England, August. [find](https://scholar.google.com/scholar?q=Daniel+Blanchard+and+Jeffrey+Heinz%2E+2008%2E+Improving+word+segmentation+by+simultaneously+learning+phonotactics%2E+In+CoNLL+2008%3A+Proceedings+of+the+Twelfth+Conference+on+Computational+Natural+Language+Le)
3. David Blei, Thomas L. Griffiths, Michael I. Jordan, and Joshua B. Tenenbaum. 2004. Hierarchical topic models and the nested chinese restaurant process. In Sebastian Thrun, Lawrence Saul, and Bernhard Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=David+Blei%2C+Thomas+L%2E+Griffiths%2C+Michael+I%2E+Jordan%2C+and+Joshua+B%2E+Tenenbaum%2E+2004%2E+Hierarchical+topic+models+and+the+nested+chinese+restaurant+process%2E+In+Sebastian+Thrun%2C+Lawrence+Saul%2C+and+Bernhard+)
4. Rens Bod. 1998. Beyond grammar: an experience-based theory of language. CSLI Publications, Stanford, California. [find](https://scholar.google.com/scholar?q=Rens+Bod%2E+1998%2E+Beyond+grammar%3A+an+experience%2Dbased+theory+of+language%2E+CSLI+Publications%2C+Stanford%2C+California%2E)
5. M. Brent and T. Cartwright. 1996. Distributional regularity and phonotactic constraints are useful for segmentation. Cognition, 61:93–125. [find](https://scholar.google.com/scholar?q=M%2E+Brent+and+T%2E+Cartwright%2E+1996%2E+Distributional+regularity+and+phonotactic+constraints+are+useful+for+segmentation%2E+Cognition%2C+61%3A93%E2%80%93125%2E)
6. M. Brent. 1999. An efficient, probabilistically sound algorithm for segmentation and word discovery. Machine Learning, 34:71–105. [find](https://scholar.google.com/scholar?q=M%2E+Brent%2E+1999%2E+An+efficient%2C+probabilistically+sound+algorithm+for+segmentation+and+word+discovery%2E+Machine+Learning%2C+34%3A71%E2%80%93105%2E)
7. Jeffrey Elman. 1990. Finding structure in time. Cognitive Science, 14:197–211. [find](https://scholar.google.com/scholar?q=Jeffrey+Elman%2E+1990%2E+Finding+structure+in+time%2E+Cognitive+Science%2C+14%3A197%E2%80%93211%2E)
8. Margaret M. Fleck. 2008. Lexicalized phonotactic word segmentation. In Proceedings of ACL-08: HLT, pages 130–138, Columbus, Ohio, June. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Margaret+M%2E+Fleck%2E+2008%2E+Lexicalized+phonotactic+word+segmentation%2E+In+Proceedings+of+ACL%2D08%3A+HLT%2C+pages+130%E2%80%93138%2C+Columbus%2C+Ohio%2C+June%2E+Association+for+Computational+Linguistics%2E)
9. Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2006a. [Contextual dependencies in unsupervised word segmentation](https://md.research.elamur.ai/free/en/papers/goldwater-2006-contextual-dependencies-unsupervised-word-segmentation/). In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 673–680, Sydney,…
10. Sharon Goldwater, Tom Griffiths, and Mark Johnson. 2006b. Interpolating between types and tokens by estimating power-law generators. In Y. Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, pages 459–466, Cambridge, MA. MIT Press. [find](https://scholar.google.com/scholar?q=Sharon+Goldwater%2C+Tom+Griffiths%2C+and+Mark+Johnson%2E+2006b%2E+Interpolating+between+types+and+tokens+by+estimating+power%2Dlaw+generators%2E+In+Y%2E+Weiss%2C+B%2E+Scho%CC%88lkopf%2C+and+J%2E+Platt%2C+editors%2C+Advances+in+Neur)
11. Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2007. Distributional cues to word boundaries: Context is important. In David Bamman, Tatiana Magnitskaia, and Colleen Zaller, editors, Proceedings of the 31st Annual Boston University Conference on Language Development, pages 239–250, Somervil… [find](https://scholar.google.com/scholar?q=Sharon+Goldwater%2C+Thomas+L%2E+Griffiths%2C+and+Mark+Johnson%2E+2007%2E+Distributional+cues+to+word+boundaries%3A+Context+is+important%2E+In+David+Bamman%2C+Tatiana+Magnitskaia%2C+and+Colleen+Zaller%2C+editors%2C+Proceedi)
12. H. Ishwaran and L. F. James. 2003. Generalized weighted Chinese restaurant processes for species sampling mixture models. Statistica Sinica, 13:1211– 1235. [find](https://scholar.google.com/scholar?q=H%2E+Ishwaran+and+L%2E+F%2E+James%2E+2003%2E+Generalized+weighted+Chinese+restaurant+processes+for+species+sampling+mixture+models%2E+Statistica+Sinica%2C+13%3A1211%E2%80%93+1235%2E)
13. Mark Johnson, Thomas Griffiths, and Sharon Goldwater. 2007a. [Bayesian inference for PCFGs via Markov chain Monte Carlo](https://md.research.elamur.ai/free/en/papers/johnson-2007-bayesian-inference-pcfgs-markov-chain/). In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 139–14…
14. Mark Johnson, Thomas L. Griffiths, and Sharon Goldwater. 2007b. Adaptor Grammars: A framework for specifying compositional nonparametric Bayesian models. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19, pages 641–648. MIT Press, Cambridge, MA… [find](https://scholar.google.com/scholar?q=Mark+Johnson%2C+Thomas+L%2E+Griffiths%2C+and+Sharon+Goldwater%2E+2007b%2E+Adaptor+Grammars%3A+A+framework+for+specifying+compositional+nonparametric+Bayesian+models%2E+In+B%2E+Scho%CC%88lkopf%2C+J%2E+Platt%2C+and+T%2E+Hoffman%2C+ed)
15. Mark Johnson. 2008. Using adaptor grammars to identifying synergies in the unsupervised acquisition of linguistic structure. In Proceedings of the 46th Annual Meeting of the Association of Computational Linguistics, Columbus, Ohio. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Mark+Johnson%2E+2008%2E+Using+adaptor+grammars+to+identifying+synergies+in+the+unsupervised+acquisition+of+linguistic+structure%2E+In+Proceedings+of+the+46th+Annual+Meeting+of+the+Association+of+Computation)
16. Aravind Joshi. 2003. Tree adjoining grammars. In Ruslan Mikkov, editor, The Oxford Handbook of Computational Linguistics, pages 483–501. Oxford University Press, Oxford, England. [find](https://scholar.google.com/scholar?q=Aravind+Joshi%2E+2003%2E+Tree+adjoining+grammars%2E+In+Ruslan+Mikkov%2C+editor%2C+The+Oxford+Handbook+of+Computational+Linguistics%2C+pages+483%E2%80%93501%2E+Oxford+University+Press%2C+Oxford%2C+England%2E)
17. David J.C. MacKay. 2003. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. [find](https://scholar.google.com/scholar?q=David+J%2EC%2E+MacKay%2E+2003%2E+Information+Theory%2C+Inference%2C+and+Learning+Algorithms%2E+Cambridge+University+Press%2E)
18. Radford M. Neal. 2003. Slice sampling. Annals of Statistics, 31:705–767. [find](https://scholar.google.com/scholar?q=Radford+M%2E+Neal%2E+2003%2E+Slice+sampling%2E+Annals+of+Statistics%2C+31%3A705%E2%80%93767%2E)
19. J. Pitman and M. Yor. 1997. The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator. Annals of Probability, 25:855–900. [find](https://scholar.google.com/scholar?q=J%2E+Pitman+and+M%2E+Yor%2E+1997%2E+The+two%2Dparameter+Poisson%2DDirichlet+distribution+derived+from+a+stable+subordinator%2E+Annals+of+Probability%2C+25%3A855%E2%80%93900%2E)
20. J. Pitman. 1995. Exchangeable and partially exchangeable random partitions. Probability Theory and Related Fields, 102:145–158. [find](https://scholar.google.com/scholar?q=J%2E+Pitman%2E+1995%2E+Exchangeable+and+partially+exchangeable+random+partitions%2E+Probability+Theory+and+Related+Fields%2C+102%3A145%E2%80%93158%2E)
21. Christian P. Robert and George Casella. 2004. Monte Carlo Statistical Methods. Springer. [find](https://scholar.google.com/scholar?q=Christian+P%2E+Robert+and+George+Casella%2E+2004%2E+Monte+Carlo+Statistical+Methods%2E+Springer%2E)
22. Andreas Stolcke and Stephen Omohundro. 1994. Inducing probabilistic grammars by Bayesian model merging. In Rafael C. Carrasco and Jose Oncina, editors, Grammatical Inference and Applications, pages 106– 118. Springer, New York. [find](https://scholar.google.com/scholar?q=Andreas+Stolcke+and+Stephen+Omohundro%2E+1994%2E+Inducing+probabilistic+grammars+by+Bayesian+model+merging%2E+In+Rafael+C%2E+Carrasco+and+Jose+Oncina%2C+editors%2C+Grammatical+Inference+and+Applications%2C+pages+10)
23. Y. W. Teh, M. Jordan, M. Beal, and D. Blei. 2006. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101:1566–1581. [find](https://scholar.google.com/scholar?q=Y%2E+W%2E+Teh%2C+M%2E+Jordan%2C+M%2E+Beal%2C+and+D%2E+Blei%2E+2006%2E+Hierarchical+Dirichlet+processes%2E+Journal+of+the+American+Statistical+Association%2C+101%3A1566%E2%80%931581%2E)

*Updated 29 October 2026*