Elamur Research⌕
☰
home / 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

Paper · 2009 · Mark Johnson and Sharon Goldwater

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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 UniversityProvidence · United States76 works · 25,952 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Tokenization & segmentation · 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.

@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/}
}

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
  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
  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
  4. Rens Bod. 1998. Beyond grammar: an experience-based theory of language. CSLI Publications, Stanford, California. find
  5. M. Brent and T. Cartwright. 1996. Distributional regularity and phonotactic constraints are useful for segmentation. Cognition, 61:93–125. find
  6. M. Brent. 1999. An efficient, probabilistically sound algorithm for segmentation and word discovery. Machine Learning, 34:71–105. find
  7. Jeffrey Elman. 1990. Finding structure in time. Cognitive Science, 14:197–211. find
  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
  9. Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2006a. Contextual dependencies in 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
  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
  12. H. Ishwaran and L. F. James. 2003. Generalized weighted Chinese restaurant processes for species sampling mixture models. Statistica Sinica, 13:1211– 1235. find
  13. Mark Johnson, Thomas Griffiths, and Sharon Goldwater. 2007a. Bayesian inference for PCFGs via Markov chain Monte Carlo. 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
  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
  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
  17. David J.C. MacKay. 2003. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. find
  18. Radford M. Neal. 2003. Slice sampling. Annals of Statistics, 31:705–767. find
  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
  20. J. Pitman. 1995. Exchangeable and partially exchangeable random partitions. Probability Theory and Related Fields, 102:145–158. find
  21. Christian P. Robert and George Casella. 2004. Monte Carlo Statistical Methods. Springer. find
  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
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/johnson-2009-improving-nonparameteric-bayesian-inference-experiments/