An Efficient Algorithm for Unsupervised Word Segmentation with Branching Entropy and MDL

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 832–842, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics An Efficient Algorithm for Unsupervised Word Segmentation with Branching Entropy and MDL Valentin Zhikov Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology zhikov@lr.pi.titech.ac.jp Hiroya Takamura Precision and Intelligence Laboratory Tokyo Institute of Technology takamura@pi.titech.ac.jp Manabu Okumura Precision and Intelligence Laboratory Tokyo Institute of Technology oku@pi.titech.ac.jp Abstract This paper proposes a fast and simple unsuper- vised word segmentation algorithm that uti- lizes the local predictability of adjacent char- acter sequences, while searching for a least- effort representation of the data. The model uses branching entropy as a means of con- straining the hypothesis space, in order to ef- ficiently obtain a solution that minimizes the length of a two-part MDL code. An evaluation with corpora in Japanese, Thai, English, and the ”CHILDES” corpus for research in lan- guage development reveals that the algorithm achieves an accuracy, comparable to that of the state-of-the-art methods in unsupervised word segmentation, in a significantly reduced computational time. 1 Introduction As an inherent preprocessing step to nearly all NLP tasks for writing systems without orthographical marking of word boundaries, such as Japanese and Chinese, the importance of word segmentation has lead to the emergence of a micro-genre in NLP fo- cused exclusively on this problem. Supervised probabilistic models such as Condi- tional Random Fields (CRF) (Lafferty et al., 2001) have a wide application to the morphological anal- ysis of these languages. However, the development of the annotated training corpora necessary for their functioning is a labor-intensive task, which involves multiple stages of manual tagging. Because of the scarcity of labeled data, the domain adaptation of morphological analyzers is also problematic, and semi-supervised algorithms that address this issue have also been proposed (e.g. Liang, 2005; Tsuboi et al., 2008). Recent advances in unsupervised word segmen- tation have been promoted by human cognition re- search, where it is involved in the modeling of the mechanisms that underlie language acquisition. An- other motivation to study unsupervised approaches is their potential to support the domain adaptation of morphological analyzers through the incorporation of unannotated training data, thus reducing the de- pendency on costly manual work. Apart from the considerable difficulties in discovering reliable cri- teria for word induction, the practical application of such approaches is impeded by their prohibitive computational cost. In this paper, we address the issue of achiev- ing high accuracy in a practical computational time through an efficient method that relies on a combina- tion of evidences: the local predictability of charac- ter patterns, and the reduction of effort achieved by a given representation of the language data. Both of these criteria are assumed to play a key role in native language acquisition. The proposed model allows experimentation in a more realistic setting, where the learner is able to apply them simultaneously. The 832 method shows a high performance in terms of accu- racy and speed, can be applied …

Content truncated to 500 words