Minimized Models for Unsupervised Part-of-Speech Tagging

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 504–512, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Minimized Models for Unsupervised Part-of-Speech Tagging Sujith Ravi and Kevin Knight University of Southern California Information Sciences Institute Marina del Rey, California 90292 {sravi,knight}@isi.edu Abstract We describe a novel method for the task of unsupervised POS tagging with a dic- tionary, one that uses integer programming to explicitly search for the smallest model that explains the data, and then uses EM to set parameter values. We evaluate our method on a standard test corpus using different standard tagsets (a 45-tagset as well as a smaller 17-tagset), and show that our approach performs better than existing state-of-the-art systems in both settings. 1 Introduction In recent years, we have seen increased interest in using unsupervised methods for attacking differ- ent NLP tasks like part-of-speech (POS) tagging. The classic Expectation Maximization (EM) algo- rithm has been shown to perform poorly on POS tagging, when compared to other techniques, such as Bayesian methods. In this paper, we develop new methods for un- supervised part-of-speech tagging. We adopt the problem formulation of Merialdo (1994), in which we are given a raw word sequence and a dictio- nary of legal tags for each word type. The goal is to tag each word token so as to maximize accuracy against a gold tag sequence. Whether this is a real- istic problem set-up is arguable, but an interesting collection of methods and results has accumulated around it, and these can be clearly compared with one another. We use the standard test set for this task, a 24,115-word subset of the Penn Treebank, for which a gold tag sequence is available. There are 5,878 word types in this test set. We use the standard tag dictionary, consisting of 57,388 word/tag pairs derived from the entire Penn Tree- bank.1 8,910 dictionary entries are relevant to the 5,878 word types in the test set. Per-token ambigu- ity is about 1.5 tags/token, yielding approximately 106425 possible ways to tag the data. There are 45 distinct grammatical tags. In this set-up, there are no unknown words. lem.Figure 1 shows prior results for this prob- While the methods are quite different, they all make use of two common model ele- ments. One is a probabilistic n-gram tag model P(ti|ti−n+1...ti−1), which we call the grammar. The other is a probabilistic word-given-tag model P(wi|ti), which we call the dictionary. The classic approach (Merialdo, 1994) is expectation-maximization (EM), where we esti- mate grammar and dictionary probabilities in or- der to maximize the probability of the observed word sequence: P(w1...wn) = � t1...tn P(t1...tn) · P(w1...wn|t1...tn) ≈ � t1...tn n � i=1 P(ti|ti−2 ti−1) · P(wi|ti) Goldwater and Griffiths (2007) report 74.5% accuracy for EM with a 3-gram tag model, which we confirm by replication. They improve this to 83.9% by employing a fully Bayesian approach which integrates over all possible parameter val- ues, rather than estimating a single distribution. They …

Content truncated to 500 words