Contextual Dependencies in Unsupervised Word Segmentation

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 673–680, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Contextual Dependencies in Unsupervised Word Segmentation∗ Sharon Goldwater and Thomas L. Griffiths and Mark Johnson Department of Cognitive and Linguistic Sciences Brown University Providence, RI 02912 {Sharon Goldwater,Tom Griffiths,Mark Johnson}@brown.edu Abstract Developing better methods for segment- ing continuous text into words is impor- tant for improving the processing of Asian languages, and may shed light on how hu- mans learn to segment speech. We pro- pose two new Bayesian word segmenta- tion methods that assume unigram and bi- gram models of word dependencies re- spectively. The bigram model greatly out- performs the unigram model (and previous probabilistic models), demonstrating the importance of such dependencies for word segmentation. We also show that previous probabilistic models rely crucially on sub- optimal search procedures. 1 Introduction Word segmentation, i.e., discovering word bound- aries in continuous text or speech, is of interest for both practical and theoretical reasons. It is the first step of processing orthographies without explicit word boundaries, such as Chinese. It is also one of the key problems that human language learners must solve as they are learning language. Many previous methods for unsupervised word segmentation are based on the observation that transitions between units (characters, phonemes, or syllables) within words are generally more pre- dictable than transitions across word boundaries. Statistics that have been proposed for measuring these differences include “successor frequency” (Harris, 1954), “transitional probabilities” (Saf- fran et al., 1996), mutual information (Sun et al., ∗This work was partially supported by the following grants: NIH 1R01-MH60922, NIH RO1-DC000314, NSF IGERT-DGE-9870676, and the DARPA CALO project. 1998), “accessor variety” (Feng et al., 2004), and boundary entropy (Cohen and Adams, 2001). While methods based on local statistics are quite successful, here we focus on approaches based on explicit probabilistic models. Formulat- ing an explicit probabilistic model permits us to cleanly separate assumptions about the input and properties of likely segmentations from details of algorithms used to find such solutions. Specifi- cally, this paper demonstrates the importance of contextual dependencies for word segmentation by comparing two probabilistic models that dif- fer only in that the first assumes that the proba- bility of a word is independent of its local context, while the second incorporates bigram dependen- cies between adjacent words. The algorithms we use to search for likely segmentations do differ, but so long as the segmentations they produce are close to optimal we can be confident that any dif- ferences in the segmentations reflect differences in the probabilistic models, i.e., in the kinds of de- pendencies between words. We are not the first to propose explicit prob- abilistic models of word segmentation. Two successful word segmentation systems based on explicit probabilistic models are those of Brent (1999) and Venkataraman (2001). Brent’s Model- Based Dynamic Programming (MBDP) system as- sumes a unigram word distribution. Venkatara- man uses standard unigram, bigram, and trigram language models in three …

Content truncated to 500 words