Unsupervised Morphological Segmentation with Log-Linear Models

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 209–217, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Unsupervised Morphological Segmentation with Log-Linear Models Hoifung Poon∗ Dept. of Computer Sci. & Eng. University of Washington Seattle, WA 98195 hoifung@cs.washington.edu Colin Cherry Microsoft Research Redmond, WA 98052 colinc@microsoft.com Kristina Toutanova Microsoft Research Redmond, WA 98052 kristout@microsoft.com Abstract Morphological segmentation breaks words into morphemes (the basic semantic units). It is a key component for natural language pro- cessing systems. Unsupervised morphologi- cal segmentation is attractive, because in ev- ery language there are virtually unlimited sup- plies of text, but very few labeled resources. However, most existing model-based systems for unsupervised morphological segmentation use directed generative models, making it dif- ficult to leverage arbitrary overlapping fea- tures that are potentially helpful to learning. In this paper, we present the first log-linear model for unsupervised morphological seg- mentation. Our model uses overlapping fea- tures such as morphemes and their contexts, and incorporates exponential priors inspired by the minimum description length (MDL) principle. We present efficient algorithms for learning and inference by combining con- trastive estimation with sampling. Our sys- tem, based on monolingual features only, out- performs a state-of-the-art system by a large margin, even when the latter uses bilingual in- formation such as phrasal alignment and pho- netic correspondence. On the Arabic Penn Treebank, our system reduces F1 error by 11% compared to Morfessor. 1 Introduction The goal of morphological segmentation is to seg- ment words into morphemes, the basic syntac- tic/semantic units. This is a key subtask in many ∗ This research was conducted during the author’s intern- ship at Microsoft Research. NLP applications, including machine translation, speech recognition and question answering. Past approaches include rule-based morphological an- alyzers (Buckwalter, 2004) and supervised learn- ing (Habash and Rambow, 2005). While successful, these require deep language expertise and a long and laborious process in system building or labeling. Unsupervised approaches are attractive due to the the availability of large quantities of unlabeled text, and unsupervised morphological segmentation has been extensively studied for a number of languages (Brent et al., 1995; Goldsmith, 2001; Dasgupta and Ng, 2007; Creutz and Lagus, 2007). The lack of supervised labels makes it even more important to leverage rich features and global dependencies. However, existing systems use directed generative models (Creutz and Lagus, 2007; Snyder and Barzi- lay, 2008b), making it difficult to extend them with arbitrary overlapping dependencies that are poten- tially helpful to segmentation. In this paper, we present the first log-linear model for unsupervised morphological segmentation. Our model incorporates simple priors inspired by the minimum description length (MDL) principle, as well as overlapping features such as morphemes and their contexts (e.g., in Arabic, the string Al is likely a morpheme, as is any string between Al and a word boundary). We develop efficient learning and infer- ence algorithms using a novel combination of two ideas from previous work on unsupervised learn- ing with log-linear models: contrastive estimation (Smith …

Content truncated to 500 words