Fast, Greedy Model Minimization for Unsupervised Tagging

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 940–948, Beijing, August 2010 Fast, Greedy Model Minimization for Unsupervised Tagging Sujith Ravi and Ashish Vaswani and Kevin Knight and David Chiang University of Southern California Information Sciences Institute {sravi,avaswani,knight,chiang}@isi.edu Abstract Model minimization has been shown to work well for the task of unsupervised part-of-speech tagging with a dictionary. In (Ravi and Knight, 2009), the authors in- voke an integer programming (IP) solver to do model minimization. However, solving this problem exactly using an integer programming formulation is in- tractable for practical purposes. We pro- pose a novel two-stage greedy approxima- tion scheme to replace the IP. Our method runs fast, while yielding highly accurate tagging results. We also compare our method against standard EM training, and show that we consistently obtain better tagging accuracies on test data of varying sizes for English and Italian. 1 Introduction The task of unsupervised part-of-speech (POS) tagging with a dictionary as formulated by Meri- aldo (1994) is: given a raw word sequence and a dictionary of legal POS tags for each word type, tag each word token in the text. A common ap- proach to modeling such sequence labeling prob- lems is to build a bigram Hidden Markov Model (HMM) parameterized by tag-bigram transition probabilities P(ti|ti−1) and word-tag emission probabilities P(wi|ti). Given a word sequence w and a tag sequence t, of length N, the joint prob- ability P(w, t) is given by: P(w, t) = N � i=1 P(wi|ti) · P(ti|ti−1) (1) We can train this model using the Expectation Maximization (EM) algorithm (Dempster and Ru- bin, 1977) which learns P(wi|ti) and P(ti|ti−1) that maximize the likelihood of the observed data. Once the parameters are learnt, we can find the best tagging using the Viterbi algorithm. ˆt = arg max t P(w, t) (2) Ravi and Knight (2009) attack the Merialdo task in two stages. In the first stage, they search for a minimized transition model (i.e., the small- est set of tag bigrams) that can explain the data using an integer programming (IP) formulation. In the second stage, they build a smaller HMM by restricting the transition parameters to only those tag bigrams selected in the minimization step. They employ the EM algorithm to train this model, which prunes away some of the emission parameters. Next, they use the pruned emission model along with the original transition model (which uses the full set of tag bigrams) and re- train using EM. This alternating EM training pro- cedure is repeated until the number of tag bigrams in the Viterbi tagging output does not change be- tween subsequent iterations. The final Viterbi tag- ging output from their method achieves state-of- the-art accuracy for this task. However, their mini- mization step involves solving an integer program, which can be very slow, especially when scal- ing to large-scale data and more complex tagging problems which use bigger tagsets. In this pa- per, we present a novel method that optimizes the same objective function …

Content truncated to 500 words