Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 100–108, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling Daichi Mochihashi Takeshi Yamada Naonori Ueda NTT Communication Science Laboratories Hikaridai 2-4, Keihanna Science City, Kyoto, Japan {daichi,yamada,ueda}@cslab.kecl.ntt.co.jp Abstract In this paper, we propose a new Bayesian model for fully unsupervised word seg- mentation and an efficient blocked Gibbs sampler combined with dynamic program- ming for inference. Our model is a nested hierarchical Pitman-Yor language model, where Pitman-Yor spelling model is em- bedded in the word model. We confirmed that it significantly outperforms previous reported results in both phonetic tran- scripts and standard datasets for Chinese and Japanese word segmentation. Our model is also considered as a way to con- struct an accurate word n-gram language model directly from characters of arbitrary language, without any “word” indications. 1 Introduction “Word” is no trivial concept in many languages. Asian languages such as Chinese and Japanese have no explicit word boundaries, thus word seg- mentation is a crucial first step when processing them. Even in western languages, valid “words” are often not identical to space-separated tokens. For example, proper nouns such as “United King- dom” or idiomatic phrases such as “with respect to” actually function as a single word, and we of- ten condense them into the virtual words “UK” and “w.r.t.”. In order to extract “words” from text streams, unsupervised word segmentation is an important research area because the criteria for creating su- pervised training data could be arbitrary, and will be suboptimal for applications that rely on seg- mentations. It is particularly difficult to create “correct” training data for speech transcripts, col- loquial texts, and classics where segmentations are often ambiguous, let alone is impossible for un- known languages whose properties computational linguists might seek to uncover. From a scientific point of view, it is also inter- esting because it can shed light on how children learn “words” without the explicitly given bound- aries for every word, which is assumed by super- vised learning approaches. Lately, model-based methods have been intro- duced for unsupervised segmentation, in particu- lar those based on Dirichlet processes on words (Goldwater et al., 2006; Xu et al., 2008). This maximizes the probability of word segmentation w given a string s : ˆw = argmax w p(w|s) . (1) This approach often implicitly includes heuristic criteria proposed so far1, while having a clear sta- tistical semantics to find the most probable word segmentation that will maximize the probability of the data, here the strings. However, they are still na¨ıve with respect to word spellings, and the inference is very slow ow- ing to inefficient Gibbs sampling. Crucially, since they rely on sampling a word boundary between two neighboring words, they can leverage only up to bigram word dependencies. In this paper, we extend this work to pro- pose a more efficient and accurate unsupervised word segmentation that will optimize the …

Content truncated to 500 words