---
title: "Contextual Dependencies in Unsupervised Word Segmentation"
description: "As an alternative, they build Bayesian nonparametric models: a Dirichlet process (DP) unigram model… 15 references, cited by 67 papers here."
authors: ["Sharon Goldwater", "Thomas L. Griffiths", "Mark Johnson"]
year: 2006
venue: "Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P06-1085/"
doi: "10.3115/1220175.1220260"
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/goldwater-2006-contextual-dependencies-unsupervised-word-segmentation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/goldwater-2006-contextual-dependencies-unsupervised-word-segmentation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Contextual Dependencies in Unsupervised Word Segmentation

# Contextual Dependencies in Unsupervised Word Segmentation

**Authors:** [Sharon Goldwater](https://md.research.elamur.ai/free/en/authors/sharon-goldwater/), [Thomas L. Griffiths](https://md.research.elamur.ai/free/en/authors/thomas-l-griffiths/) and [Mark Johnson](https://md.research.elamur.ai/free/en/authors/mark-johnson/) · **Year:** 2006 · **Venue:** [Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2006](https://md.research.elamur.ai/free/en/venues/acl/2006/)) · **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/P06-1085/) · [PDF](https://aclanthology.org/P06-1085.pdf) · [DOI 10.3115/1220175.1220260](https://doi.org/10.3115/1220175.1220260) · [OpenAlex](https://openalex.org/W2122228338)

**Citations:** 305 citations (OpenAlex, 2026-10-14) · [67](https://md.research.elamur.ai/free/en/papers/goldwater-2006-contextual-dependencies-unsupervised-word-segmentation/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper asks whether modeling relations between neighboring words helps unsupervised word segmentation, the task of finding word boundaries in unsegmented text or phonemically transcribed speech. Earlier explicit probabilistic systems, Brent's MBDP and Venkataraman's NGS, showed almost no difference between unigram, bigram and trigram variants, which suggested that context does not matter. The authors argue that this finding was an artifact of approximate search. For each older model they exhibit a segmentation that the model scores higher but that is less accurate. They also show that the true maximum-likelihood NGS solution leaves utterances unsegmented. As an alternative, they build Bayesian nonparametric models: a Dirichlet process (DP) unigram model and a hierarchical Dirichlet process (HDP) bigram model. Both use Gibbs sampling, which converges to the posterior over segmentations. The bigram HDP model clearly beats the unigram DP model and the bigram NGS. It reached the best published token and lexicon accuracy on the corpus used. The work shows that bigram dependencies are important, mainly for avoiding under-segmentation of frequent collocations. It also shows why model and search should be evaluated separately.

## Key points
- The baselines are Brent's MBDP, which uses a unigram distribution with a prior favoring smaller lexicons, and Venkataraman's NGS (unigram, bigram and trigram). Both rely on online approximate search that fixes each utterance's segmentation before moving to the next.
- Because NGS uses a uniform prior, its optimum is the corpus with no utterance-internal boundaries, where each utterance is treated as one "word".
- The unigram model is based on a DP(α0, P0). It is understood through the Chinese restaurant process, which acts like a cache: a word is either reused in proportion to its count or newly generated from P0. P0 is a simple unigram phoneme model with stop probability p#.
- The bigram HDP model on the bigram setup reached P/R/F of 79.4/74.0/76.6 and LP/LR/LF of 67.9/58.9/63.1. The bigram NGS scored 68.1/68.6/68.3 and 54.5/57.0/55.7. The HDP settings were p# = .5, α0 = 1000 and α1 = 10.
- In the bigram model, the negative relationship between lexicon and token accuracy seen in the unigram model disappears. Only a small number of collocations are still listed as lexical entries, and the errors that persist mostly concern infrequent words.

## Interesting ideas
- **Separate the model from the search.** Show that a less accurate segmentation receives a higher score than the one the search returned. This test reveals whether reported results come from the model's assumptions or from quirks of the search, and it applies to any system that relies on heuristic decoding.
- **Prefer sparse solutions with a prior.** A uniform prior rewards simply memorizing the training data. A prior that favors fewer parameters or lexical items prevents this degenerate outcome, which is a useful safeguard for any unsupervised lexicon or vocabulary induction.
- **Keep the word generator and the frequency model separate.** The base distribution P0 (what new words look like) is defined apart from the CRP adaptor (how often words recur). Each part can therefore be changed independently, for example by adding phonotactics or morphology for a specific language such as Ukrainian.
- **Back off hierarchically by sharing table labels.** In the HDP bigram model, all context-specific restaurants draw from a shared unigram process. This acts as smoothing that is learned from the data rather than tuned by hand, and the same pattern works for other sparse conditional distributions.
- **Score both tokens and lexicon.** Reporting precision, recall and F-score for word tokens and for lexicon types exposes trade-offs that a single metric hides, such as the unigram model merging collocations. This makes it a sound evaluation practice for segmentation and tokenization tools.

*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 · 58 works · 25,310 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

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

## Cite

Cite as: Sharon Goldwater, Thomas L. Griffiths and Mark Johnson. 2006. Contextual Dependencies in Unsupervised Word Segmentation. Proceedings of the 21st International Conference on Computational Linguistics and 44th 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{goldwater2006contextual,
  title = {{Contextual Dependencies in Unsupervised Word Segmentation}},
  author = {Sharon Goldwater, Thomas L. Griffiths and Mark Johnson},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220260},
  url = {https://doi.org/10.3115/1220175.1220260}
}
```

- [← previous The Third International Chinese Language Processing Bakeoff: Word Segmentation and Named Entity Recognition](https://md.research.elamur.ai/free/en/papers/levow-2006-third-international-chinese-language-processing/)
- [next → Learning for Semantic Parsing with Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/wong-2006-learning-semantic-parsing-statistical-machine/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

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

1. D. Aldous. 1985. Exchangeability and related topics. In École d’été de probabilités de Saint-Flour, XIII—1983, pages 1–198. Springer, Berlin. [find](https://scholar.google.com/scholar?q=D%2E+Aldous%2E+1985%2E+Exchangeability+and+related+topics%2E+In+E%CC%81cole+d%E2%80%99e%CC%81te%CC%81+de+probabilite%CC%81s+de+Saint%2DFlour%2C+XIII%E2%80%941983%2C+pages+1%E2%80%93198%2E+Springer%2C+Berlin%2E)
2. C. Antoniak. 1974. Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. The Annals of Statistics, 2:1152–1174. [find](https://scholar.google.com/scholar?q=C%2E+Antoniak%2E+1974%2E+Mixtures+of+Dirichlet+processes+with+applications+to+Bayesian+nonparametric+problems%2E+The+Annals+of+Statistics%2C+2%3A1152%E2%80%931174%2E)
3. 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)
4. 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)
5. P. Cohen and N. Adams. 2001. An algorithm for segmenting categorical timeseries into meaningful episodes. In Proceedings of the Fourth Symposium on Intelligent Data Analysis. [find](https://scholar.google.com/scholar?q=P%2E+Cohen+and+N%2E+Adams%2E+2001%2E+An+algorithm+for+segmenting+categorical+timeseries+into+meaningful+episodes%2E+In+Proceedings+of+the+Fourth+Symposium+on+Intelligent+Data+Analysis%2E)
6. H. Feng, K. Chen, X. Deng, and W. Zheng. 2004. [Accessor variety criteria for chinese word extraction](https://md.research.elamur.ai/free/en/papers/feng-2004-accessor-variety-criteria-chinese-word/). Computational Lingustics, 30(1).
7. W.R. Gilks, S. Richardson, and D. J. Spiegelhalter, editors. 1996. Markov Chain Monte Carlo in Practice. Chapman and Hall, Suffolk. [find](https://scholar.google.com/scholar?q=W%2ER%2E+Gilks%2C+S%2E+Richardson%2C+and+D%2E+J%2E+Spiegelhalter%2C+editors%2E+1996%2E+Markov+Chain+Monte+Carlo+in+Practice%2E+Chapman+and+Hall%2C+Suffolk%2E)
8. S. Goldwater, T. Griffiths, and M. Johnson. 2006. Interpolating between types and tokens by estimating power-law generators. In Advances in Neural Information Processing Systems 18, Cambridge, MA. MIT Press. [find](https://scholar.google.com/scholar?q=S%2E+Goldwater%2C+T%2E+Griffiths%2C+and+M%2E+Johnson%2E+2006%2E+Interpolating+between+types+and+tokens+by+estimating+power%2Dlaw+generators%2E+In+Advances+in+Neural+Information+Processing+Systems+18%2C+Cambridge%2C+MA%2E+MIT)
9. Z. Harris. 1954. Distributional structure. Word, 10:146–162. [find](https://scholar.google.com/scholar?q=Z%2E+Harris%2E+1954%2E+Distributional+structure%2E+Word%2C+10%3A146%E2%80%93162%2E)
10. B. MacWhinney and C. Snow. 1985. The child language data exchange system. Journal of Child Language, 12:271– 296. [find](https://scholar.google.com/scholar?q=B%2E+MacWhinney+and+C%2E+Snow%2E+1985%2E+The+child+language+data+exchange+system%2E+Journal+of+Child+Language%2C+12%3A271%E2%80%93+296%2E)
11. J. Saffran, E. Newport, and R. Aslin. 1996. Word segmentation: The role of distributional cues. Journal of Memory and Language, 35:606–621. [find](https://scholar.google.com/scholar?q=J%2E+Saffran%2C+E%2E+Newport%2C+and+R%2E+Aslin%2E+1996%2E+Word+segmentation%3A+The+role+of+distributional+cues%2E+Journal+of+Memory+and+Language%2C+35%3A606%E2%80%93621%2E)
12. M. Sun, D. Shen, and B. Tsou. 1998. Chinese word segmentation without using lexicon and hand-crafted training data. In Proceedings of COLING-ACL. [find](https://scholar.google.com/scholar?q=M%2E+Sun%2C+D%2E+Shen%2C+and+B%2E+Tsou%2E+1998%2E+Chinese+word+segmentation+without+using+lexicon+and+hand%2Dcrafted+training+data%2E+In+Proceedings+of+COLING%2DACL%2E)
13. Y. Teh, M. Jordan, M. Beal, and D. Blei. 2005. Hierarchical Dirichlet processes. In Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Y%2E+Teh%2C+M%2E+Jordan%2C+M%2E+Beal%2C+and+D%2E+Blei%2E+2005%2E+Hierarchical+Dirichlet+processes%2E+In+Advances+in+Neural+Information+Processing+Systems+17%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
14. Y. Teh. 2006. A Bayesian interpretation of interpolated kneser-ney. Technical Report TRA2/06, National University of Singapore, School of Computing. [find](https://scholar.google.com/scholar?q=Y%2E+Teh%2E+2006%2E+A+Bayesian+interpretation+of+interpolated+kneser%2Dney%2E+Technical+Report+TRA2%2F06%2C+National+University+of+Singapore%2C+School+of+Computing%2E)
15. A. Venkataraman. 2001. A statistical model for word discovery in transcribed speech. Computational Linguistics, 27(3):351–372. [find](https://scholar.google.com/scholar?q=A%2E+Venkataraman%2E+2001%2E+A+statistical+model+for+word+discovery+in+transcribed+speech%2E+Computational+Linguistics%2C+27%283%29%3A351%E2%80%93372%2E)

*Updated 24 October 2026*