Why Doesn’t EM Find Good HMM POS-Taggers?

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 296–305, Prague, June 2007. c⃝2007 Association for Computational Linguistics Why doesn’t EM find good HMM POS-taggers? Mark Johnson Microsoft Research Brown University Redmond, WA Providence, RI t-majoh@microsoft.com Mark Johnson@Brown.edu Abstract This paper investigates why the HMMs es- timated by Expectation-Maximization (EM) produce such poor results as Part-of-Speech (POS) taggers. We find that the HMMs es- timated by EM generally assign a roughly equal number of word tokens to each hid- den state, while the empirical distribution of tokens to POS tags is highly skewed. This motivates a Bayesian approach using a sparse prior to bias the estimator toward such a skewed distribution. We investigate Gibbs Sampling (GS) and Variational Bayes (VB) estimators and show that VB con- verges faster than GS for this task and that VB significantly improves 1-to-1 tagging ac- curacy over EM. We also show that EM does nearly as well as VB when the number of hidden HMM states is dramatically reduced. We also point out the high variance in all of these estimators, and that they require many more iterations to approach conver- gence than usually thought. 1 Introduction It is well known that Expectation-Maximization (EM) performs poorly in unsupervised induction of linguistic structure (Carroll and Charniak, 1992; Merialdo, 1994; Klein, 2005; Smith, 2006). In ret- rospect one can certainly find reasons to explain this failure: after all, likelihood does not appear in the wide variety of linguistic tests proposed for identi- fying linguistic structure (Fromkin, 2001). This paper focuses on unsupervised part-of- speech (POS) tagging, because it is perhaps the sim- plest linguistic induction task. We suggest that one reason for the apparent failure of EM for POS tag- ging is that it tends to assign relatively equal num- bers of tokens to each hidden state, while the em- pirical distribution of POS tags is highly skewed, like many linguistic (and non-linguistic) phenomena (Mitzenmacher, 2003). We focus on first-order Hid- den Markov Models (HMMs) in which the hidden state is interpreted as a POS tag, also known as bitag models. In this setting we show that EM performs poorly when evaluated using a “1-to-1 accuracy” evalua- tion, where each POS tag corresponds to at most one hidden state, but is more competitive when evaluated using a “many-to-1 accuracy” evaluation, where sev- eral hidden states may correspond to the same POS tag. We explain this by observing that the distribu- tion of hidden states to words proposed by the EM- estimated HMMs is relatively uniform, while the empirical distribution of POS tags is heavily skewed towards a few high-frequency tags. Based on this, we propose a Bayesian prior that biases the sys- tem toward more skewed distributions and show that this raises the 1-to-1 accuracy significantly. Finally, we show that a similar increase in accuracy can be achieved by reducing the number of hidden states in the models estimated by EM. There is certainly much useful …

Content truncated to 500 words