Latent-Descriptor Clustering for Unsupervised POS Induction

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 799–809, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Latent-Descriptor Clustering for Unsupervised POS Induction Michael Lamar Department of Mathematics and Computer Science Saint Louis University 220 N. Grand Blvd. St.Louis, MO 63103, USA mlamar@slu.edu Yariv Maron Gonda Brain Research Center Bar-Ilan University Ramat-Gan 52900, Israel syarivm@yahoo.com Elie Bienenstock Division of Applied Mathematics and Department of Neuroscience Brown University Providence, RI 02912, USA elie@brown.edu Abstract We present a novel approach to distributional- only, fully unsupervised, POS tagging, based on an adaptation of the EM algorithm for the esti- mation of a Gaussian mixture. In this approach, which we call Latent-Descriptor Clustering (LDC), word types are clustered using a series of progressively more informative descriptor vectors. These descriptors, which are computed from the immediate left and right context of each word in the corpus, are updated based on the previous state of the cluster assignments. The LDC algorithm is simple and intuitive. Us- ing standard evaluation criteria for unsupervised POS tagging, LDC shows a substantial im- provement in performance over state-of-the-art methods, along with a several-fold reduction in computational cost. 1 Introduction Part-of-speech (POS) tagging is a fundamental natural-language-processing problem, and POS tags are used as input to many important appli- cations. While state-of-the-art supervised POS taggers are more than 97% accurate (Toutanova et al., 2003; Tsuruoka and Tsujii, 2005), unsu- pervised POS taggers continue to lag far behind. Several authors addressed this gap using limited supervision, such as a dictionary of tags for each word (Goldwater and Griffiths, 2007; Ravi and Knight, 2009), or a list of word prototypes for each tag (Haghighi and Klein, 2006). Even in light of all these advancements, there is still in- terest in a completely unsupervised method for POS induction for several reasons. First, most languages do not have a tag dictionary. Second, the preparation of such resources is error-prone. Third, while several widely used tag sets do ex- ist, researchers do not agree upon any specific set of tags across languages or even within one language. Since tags are used as basic features for many important NLP applications (e.g. Headden et al. 2008), exploring new, statistically motivated, tag sets may also be useful. For these reasons, a fully unsupervised induction algo- rithm has both a practical and a theoretical val- ue. In the past decade, there has been a steady improvement on the completely unsupervised version of POS induction (Schütze, 1995; Clark, 2001; Clark, 2003; Johnson, 2007; Gao and Johnson, 2008; Graça et al., 2009; Abend et al., 2010; Lamar et al., 2010; Reichart et al., 2010; Berg-Kirkpatrick et al., 2010). Some of these methods use morphological cues (Clark, 2001; Clark, 2003; Abend et al., 2010; Reichart et al., 2010; Berg-Kirkpatrick et al., 2010), but all rely heavily on distributional information, i.e., bi- 799 gram statistics. Two recent papers advocate non- disambiguating models (Abend et al., 2010; Lamar et al., 2010): these assign the same tag to …

Content truncated to 500 words