Elamur Research⌕
☰
home / papers / 2007 / Why Doesn't EM Find Good HMM POS-Taggers?

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

Paper · 2007 · Mark Johnson

Summary

The paper asks why HMMs trained with Expectation-Maximization (EM) make poor unsupervised part-of-speech taggers. Johnson trains first-order (bitag) HMMs on the words of the Penn Treebank (PTB) Wall Street Journal corpus and compares the induced hidden states with the gold PTB tags. He uses three measures: many-to-1 accuracy, 1-to-1 accuracy, and Variation of Information (VI).

The central diagnosis is that EM spreads word tokens fairly evenly across hidden states, while real POS tag frequencies are heavily skewed toward a few common tags. This explains why EM looks reasonable under many-to-1 mapping but weak under 1-to-1 mapping and VI. Two remedies are tested:

  • Bayesian estimation with sparse Dirichlet priors. Both Gibbs Sampling and Variational Bayes are tried, and VB is the more effective of the two.
  • Many fewer hidden states for EM.

Both remedies raise 1-to-1 accuracy to about 46%, compared with about 40% for plain EM. The work also shows that these estimators converge much more slowly than commonly assumed and vary strongly between random restarts. This matters for how unsupervised models should be trained and compared.

Key points

  • Setup and evaluation: Bitag HMMs are trained on the PTB WSJ words and evaluated against PTB POS tags. The metrics are many-to-1 accuracy, greedy 1-to-1 accuracy (following Haghighi and Klein, 2006), and VI (following Meilă, 2003).
  • Plain EM:
    • It reaches a mean 1-to-1 accuracy of about 40%, close to the 41.3% that Haghighi and Klein report for their MRF model.
    • Ten random restarts ended between 0.38 and 0.45 in 1-to-1 accuracy.
    • Accuracy kept shifting by around 5% even after several hundred iterations, so every run used 1,000 iterations, taking roughly 2.5 days each on a 3.6GHz Pentium 4.
  • VB with Dirichlet priors:
    • VB converges faster than Gibbs Sampling and costs about the same per iteration as EM.
    • The best 1-to-1 accuracy came with α_x = 0.1, while the best many-to-1 accuracy came with α_x = 10⁻⁴.
    • The transition prior α_y had little effect on results.
  • EM-25: An EM-trained HMM with only 25 states matches the best VB model on both 1-to-1 accuracy and VI. It runs about 4× faster because it has half as many states.
  • Methods that did not help: Annealing schedules did not yield better likelihood or free energy. Maximum marginal decoding nearly always beat Viterbi decoding, by over 5% at low iteration counts.

Interesting ideas

  • I1. Compare frequency profiles. Sorting induced clusters and gold labels by frequency and plotting both distributions can reveal a mismatch that explains a metric's behaviour. This cheap diagnostic applies to any clustering or latent-variable task.
  • I2. Report several mapping-based metrics. Many-to-1 mapping can hide a flat cluster distribution, while 1-to-1 mapping and VI expose it. Using all of them gives a more honest view of unsupervised taggers or clusterers.
  • I3. Treat run-to-run variance as part of the result. Report the mean and standard deviation over multiple random initializations, and train far longer than seems necessary. Single short runs can mislead when comparing estimators.
  • I4. Let a sparse prior decide model capacity. A sparse prior can leave some latent states unused, so the effective number of states is learned rather than fixed in advance. A simpler alternative is to shrink the state count deliberately, accepting errors on rare labels in exchange for better performance on frequent ones.
  • I5. Prefer maximum marginal decoding over Viterbi. It reuses the forward-backward tables, so it is faster, and here it also scored better. This is useful whenever a model must be decoded and evaluated after every training iteration.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Brown UniversityProvidence · United States58 works · 25,310 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Part-of-speech tagging · 91 works

Cite

Cite as Mark Johnson. 2007. 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 (EMNLP-CoNLL).

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{johnson2007why,
  title = {{Why Doesn't EM Find Good HMM POS-Taggers?}},
  author = {Mark Johnson},
  booktitle = {Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)},
  year = {2007},
  url = {https://aclanthology.org/D07-1031/}
}

References

29 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Michele Banko and Robert C. Moore. 2004. Part of speech tagging in context. In Proceedings, 20th International Conference on Computational Linguistics (Coling 2004), pages 556–561, Geneva, Switzerland. find
  2. M.J. Beal, Z. Ghahramani, and C.E. Rasmussen. 2002. The infinite Hidden Markov Model. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14, pages 577–584. The MIT Press. find
  3. Matthew J. Beal. 2003. Variational Algorithms for Approximate Bayesian Inference. Ph.D. thesis, Gatsby Computational Neuroscience unit, University College London. find
  4. Julian Besag. 2004. An introduction to Markov Chain Monte Carlo methods. In Mark Johnson, Sanjeev P. Khudanpur, Mari Ostendorf, and Roni Rosenfeld, editors, Mathematical Foundations of Speech and Language Processing, pages 247–270. Springer, New York. find
  5. Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning. Springer. find
  6. M. Brand. 1999. An entropic estimator for structure discovery. Advances in Neural Information Processing Systems, 11:723–729. find
  7. Glenn Carroll and Eugene Charniak. 1992. Two experiments on learning probabilistic dependency grammars from corpora. In Proceedings of the AAAI Workshop on Statistically-Based Natural Language Processing Techniques, San Jose, CA. find
  8. Alexander Clark. 2003. Combining distributional and morphological information for part of speech induction. In 10th Conference of the European Chapter of the Association for Computational Linguistics, pages 59–66. Association for Computational Linguistics.
  9. Victoria Fromkin, editor. 2001. Linguistics: An Introduction to Linguistic Theory. Blackwell, Oxford, UK. find
  10. Sharon Goldwater and Tom Griffiths. 2007. A fully Bayesian approach to unsupervised part-of-speech tagging. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics.
  11. Joshua Goodman. 2001. A bit of progress in language modeling. Computer Speech and Language, 14:403– 434. find
  12. Aria Haghighi and Dan Klein. 2006. Prototype-driven learning for sequence models. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 320–327, New York City, USA, June. Association for Computational Linguistics.
  13. Frederick Jelinek. 1997. Statistical Methods for Speech Recognition. The MIT Press, Cambridge, Massachusetts. find
  14. Mark Johnson, Tom Griffiths, and Sharon Goldwater. 2007. Bayesian inference for PCFGs via Markov chain Monte Carlo. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 139–146, R…
  15. Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Sau. 1999. An introduction to variational methods for graphical models. Machine Learning, 37(2):183–233. find
  16. Dan Klein. 2005. The Unsupervised Learning of Natural Language Structure. Ph.D. thesis, Stanford University. find
  17. Kenichi Kurihara and Taisuke Sato. 2006. Variational Bayesian grammar induction for natural language. In 8th International Colloquium on Grammatical Inference. find
  18. David J.C. MacKay. 1997. Ensemble learning for hidden Markov models. Technical report, Cavendish Laboratory, Cambridge. find
  19. Chris Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, Massachusetts. find
  20. Michell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330.
  21. Marina Meilǎ. 2003. Comparing clusterings by the variation of information. In Bernhard Schölkopf and Manfred K. Warmuth, editors, COLT 2003: The Sixteenth Annual Conference on Learning Theory, volume 2777 of Lecture Notes in Computer Science, pages 173–187. Springer. find
  22. Bernard Merialdo. 1994. Tagging English text with a probabilistic model. Computational Linguistics, 20:155–171.
  23. M. Mitzenmacher. 2003. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226–251. find
  24. Christian P. Robert and George Casella. 2004. Monte Carlo Statistical Methods. Springer. find
  25. Noah A. Smith and Jason Eisner. 2005. Contrastive estimation: Training log-linear models on unlabeled data. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 354–362, Ann Arbor, Michigan, June. Association for Computational Linguistics.
  26. Noah A. Smith. 2006. Novel Estimation Methods for Unsupervised Discovery of Latent Structure in Natural Language Text. Ph.D. thesis, Johns Hopkins University. find
  27. Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. 2006. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(476):1566–1581. find
  28. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 2…
  29. Qin Iris Wang and Dale Schuurmans. 2005. Improved estimation for unsupervised part-of-speech tagging. In Proceedings of the 2005 IEEE International Conference on Natural Language Processing and Knowledge Engineering (IEEE NLP-KE’2005), pages 219–224, Wuhan, China. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/johnson-2007-why-doesn-t-em-find/