Efficient Unsupervised Recursive Word Segmentation Using Minimum Description Length

Efficient Unsupervised Recursive Word Segmentation Using Minimum Description Length Shlomo ARGAMONa Navot AKIVAb Amihood AMIRb Oren KAPAHb aIllinois Institute of Technology, Dept. of Computer Science, Chicago, IL 60616, USA argamon@iit.edu bBar-Ilan University, Dept. of Computer Science, Ramat Gan 52900, ISRAEL {navot,amir,kapaho}@cs.biu.ac.il Abstract Automatic word segmentation is a basic re- quirement for unsupervised learning in morpho- logical analysis. In this paper, we formulate a novel recursive method for minimum descrip- tion length (MDL) word segmentation, whose basic operation is resegmenting the corpus on a prefix (equivalently, a suffix). We derive a local expression for the change in description length under resegmentation, i.e., one which de- pends only on properties of the specific prefix (not on the rest of the corpus). Such a formula- tion permits use of a new and efficient algorithm for greedy morphological segmentation of the corpus in a recursive manner. In particular, our method does not restrict words to be segmented only once, into a stem+affix form, as do many extant techniques. Early results for English and Turkish corpora are promising. 1 Introduction Although computational morphological analyzers have existed for many years for a number of lan- guages, there are still many languages for which no such analyzer exists, but for which there is an abun- dance of electronically-available text. Developing a morphological analyzer for a new language by hand can be costly and time-consuming, requiring a great deal of effort by highly-specialized experts. Supervised learning methods, on the other hand, re- quire annotated data, which is often scarce or non- existent, and is also costly to develop. For this reason, there is increasing interest in unsupervised learning of morphology, in which unannotated text is analysed to find morphological structures. Even approximate unsupervised morphological analysis can be useful, as an aid to human annotators. This paper addresses a key task for unsuper- vised morphological analysis: word segmentation, segmenting words into their most basic meaning- ful constituents (substrings), called morphs (ortho- graphic realizations of morphemes). We adopt the minimum description length (MDL) approach to word segmentation, which has been shown to be ef- fective in recent work (notably (Goldsmith, 2001) and (Brent et al., 1995)). The minimum descrip- tion length principle (Barron et al., 1998) is an information-theoretic criterion to prefer that model for observed data which gives a minimal length cod- ing of the observed data set (given the model) to- gether with the model itself. 1.1 Our approach Our approach in this paper is to better clarify the use of MDL for morphological segmentation by en- abling direct use of a variety of MDL coding criteria in a general and efficient search algorithm. Issues of computational efficiency have been a bottleneck in work on unsupervised morphological analysis, lead- ing to various approximations and heuristics being used. Our key contribution is to show how a lo- cal formulation of description length (DL) for word segmentation enables an efficient algorithm (based on pattern-matching methods) for greedy morpho- logical segmentation of the corpus. We thus provide a search framework method …

Content truncated to 500 words