--- title: "Bayesian Unsupervised Word Segmentation with Nested" description: "The authors propose the Nested Pitman-Yor Language Model (NPYLM). 97% accuracy on Japanese. 2 references, cited by 72 papers here." authors: ["Daichi Mochihashi", "Takeshi Yamada", "Naonori Ueda"] year: 2009 venue: "Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP" source: "https://aclanthology.org/P09-1012/" 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/mochihashi-2009-bayesian-unsupervised-word-segmentation-nested/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mochihashi-2009-bayesian-unsupervised-word-segmentation-nested/) [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/) / Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling # Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling **Authors:** Daichi Mochihashi, Takeshi Yamada and Naonori Ueda · **Year:** 2009 · **Venue:** [Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2009](https://md.research.elamur.ai/free/en/venues/acl/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/P09-1012/) · [PDF](https://aclanthology.org/P09-1012.pdf) · [OpenAlex](https://openalex.org/W2140991203) **Citations:** 240 citations (OpenAlex, 2026-10-14) · [72](https://md.research.elamur.ai/free/en/papers/mochihashi-2009-bayesian-unsupervised-word-segmentation-nested/cited-by/) in our library, of the 141,840 papers whose bibliographies we read ## Summary The paper addresses fully unsupervised word segmentation for text without explicit word boundaries, such as Chinese, Japanese, phonetic transcripts, or unknown languages. Earlier Dirichlet-process segmenters had three weaknesses: crude priors over word spellings, slow character-by-character Gibbs sampling, and a limit of bigram word context. The authors propose the Nested Pitman-Yor Language Model (NPYLM). A word-level hierarchical Pitman-Yor language model (HPYLM, a Bayesian form of Kneser-Ney smoothing) uses a character-level ∞-gram HPYLM as its base measure, so any character string can be a word with a sensible prior. Inference uses a blocked Gibbs sampler that resamples the segmentation of an entire sentence at once, using forward-backward dynamic programming. The model is evaluated on English phonetic transcripts and on standard Chinese and Japanese segmentation datasets, where it beats previously reported unsupervised results. It also produces a word n-gram language model learned directly from raw characters. That language model reaches lower per-character perplexity than one trained on supervised segmentations. This makes the approach attractive for speech transcripts, colloquial text, classical texts, and languages that lack annotated data. ## Key points - NPYLM embeds a character HPYLM, specifically a variable-order ∞-gram model, as the base measure of the word HPYLM. The final character prior is uniform over the language's characters. - The two levels are linked through a nested Chinese Restaurant Process: - when the word model draws a word from its base measure, that word's characters are added to the character model as data; - when a table empties, those characters are removed again. - The spelling model's word-length behavior is corrected toward a Poisson distribution, and its parameter is estimated per language and word type rather than set by hand. - The blocked Gibbs sampler with dynamic programming supports word trigram dependencies. In contrast, earlier samplers (Goldwater et al., 2006) were bigram-limited, needed annealing, and needed about 20,000 sampling passes per character. - Supervised segmentation reaches up to about 97% accuracy on Japanese, but it gives worse per-character perplexity than unsupervised NPYLM. A semi-supervised setup with only 10K reference segmentations reaches about 90% accuracy and the lowest perplexity. - Qualitative demos include: - segmenting "The Tale of Genji"; - segmenting "Alice in Wonderland" with spaces removed and no dictionary; - discovering frequent phrases as "words" in 100K Penn Treebank sentences, by treating tokens as characters. ## Interesting ideas - **Character model as the prior over words.** Using a character-level language model as the base distribution of a word-level model removes the unknown-word problem and favors plausible spellings. This could help any open-vocabulary model, for example Ukrainian morphology-rich text or noisy user-generated data. - **Sampling a whole sentence's segmentation at once.** Resampling all boundaries of a sentence jointly via forward-backward dynamic programming avoids the slow mixing of local boundary flips. The same trick applies to other latent sequence problems such as tokenization, morpheme splitting, or chunking. - **Judging segmentation by the language model it yields.** The paper evaluates segmentations by per-character perplexity, not only by agreement with gold boundaries. This shows that human-annotated segmentations are not necessarily optimal for modeling, which is a useful lens when deciding on tokenization standards. - **Reusing the hierarchy one level up.** Treating word tokens as "characters" lets the same model discover multiword phrases without supervision. This could aid collocation or named-entity-like unit discovery, for instance trade or geographic terms. - **Mixing a little supervision with raw data.** Adding a small set of gold segmentations into the same Bayesian model yields a strong accuracy/perplexity trade-off. This is a cheap recipe for low-resource languages or historical texts. *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 - [NTT](https://md.research.elamur.ai/free/en/companies/ntt/) — Company, Tokyo, Japan · 20 works · 4,949 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 (2): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 1,344 works · [✂️ Tokenization & segmentation](https://md.research.elamur.ai/free/en/topics/tokenization/) · 77 works ## Cite Cite as: Daichi Mochihashi, Takeshi Yamada and Naonori Ueda. 2009. Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{mochihashi2009bayesian, title = {{Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling}}, author = {Daichi Mochihashi, Takeshi Yamada and Naonori Ueda}, booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP}, year = {2009}, doi = {10.3115/1687878.1687894}, url = {https://doi.org/10.3115/1687878.1687894} } ``` - [← previous Unsupervised Semantic Parsing](https://md.research.elamur.ai/free/en/papers/poon-2009-unsupervised-semantic-parsing/) - [next → Unsupervised Type and Token Identification of Idiomatic Expressions](https://md.research.elamur.ai/free/en/papers/fazly-2009-unsupervised-type-token-identification-idiomatic/) - [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/) ## References 2 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. David Aldous, 1985. Exchangeability and Related Topics, pages 1–198. Springer Lecture Notes in Math. 1117. [find](https://scholar.google.com/scholar?q=David+Aldous%2C+1985%2E+Exchangeability+and+Related+Topics%2C+pages+1%E2%80%93198%2E+Springer+Lecture+Notes+in+Math%2E+1117%2E) 2. Rie Kubota Ando and Lillian Lee. 2003. Mostly-Unsupervised Statistical Segmentation of Japanese [find](https://scholar.google.com/scholar?q=Rie+Kubota+Ando+and+Lillian+Lee%2E+2003%2E+Mostly%2DUnsupervised+Statistical+Segmentation+of+Japanese) *Updated 24 October 2026*