Improved Unsupervised POS Induction Using Intrinsic Clustering Quality and a Zipfian Constraint

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 57–66, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Improved Unsupervised POS Induction Using Intrinsic Clustering Quality and a Zipfian Constraint Roi Reichart ICNC The Hebrew University roiri@cs.huji.ac.il Raanan Fattal Institute of computer science The Hebrew University raananf@cs.huji.ac.il Ari Rappoport Institute of computer science The Hebrew University arir@cs.huji.ac.il Abstract Modern unsupervised POS taggers usually apply an optimization procedure to a non- convex function, and tend to converge to local maxima that are sensitive to start- ing conditions. The quality of the tag- ging induced by such algorithms is thus highly variable, and researchers report av- erage results over several random initial- izations. Consequently, applications are not guaranteed to use an induced tagging of the quality reported for the algorithm. In this paper we address this issue using an unsupervised test for intrinsic cluster- ing quality. We run a base tagger with different random initializations, and select the best tagging using the quality test. As a base tagger, we modify a leading un- supervised POS tagger (Clark, 2003) to constrain the distributions of word types across clusters to be Zipfian, allowing us to utilize a perplexity-based quality test. We show that the correlation between our quality test and gold standard-based tag- ging quality measures is high. Our re- sults are better in most evaluation mea- sures than all results reported in the liter- ature for this task, and are always better than the Clark average results. 1 Introduction Unsupervised part-of-speech (POS) induction is of major theoretical and practical importance. It counters the arbitrary nature of manually designed tag sets, and avoids manual corpus annotation costs. The task enjoys considerable current inter- est in the research community (see Section 3). Most unsupervised POS tagging algorithms ap- ply an optimization procedure to a non-convex function, and tend to converge to local maxima that strongly depend on the algorithm’s (usually random) initialization. The quality of the tag- gings produced by different initializations varies substantially. Figure 1 demonstrates this phe- nomenon for a leading POS induction algorithm (Clark, 2003). The absolute variability of the in- duced tagging quality is 10-15%, which is around 20% of the mean. Strong variability has also been reported by other authors (Section 3). The common practice in the literature is to re- port mean results over several random initializa- tions of the algorithm (e.g. (Clark, 2003; Smith and Eisner, 2005; Goldwater and Griffiths, 2007; Johnson, 2007)). This means that applications us- ing the induced tagging are not guaranteed to use a tagging of the reported quality. In this paper we address this issue using an unsupervised test for intrinsic clustering quality. We present a quality-based algorithmic family Q. Each of its concrete member algorithms Q(B) runs a base tagger B with different random initializa- tions, and selects the best tagging according the quality test. If the test is highly positively corre- lated with external tagging quality measures (e.g., those based on gold standard tagging), Q(B) will produce …

Content truncated to 500 words