Elamur Research⌕
☰
home / papers / 2016 / Unsupervised Part-Of-Speech Tagging with Anchor Hidden Markov Models

Unsupervised Part-Of-Speech Tagging with Anchor Hidden Markov Models

Paper · 2016 · Karl Stratos, Michael Collins and Daniel Hsu

Summary

Inducing part-of-speech tags from raw text without any labels is a long-standing unsupervised NLP problem. It is useful for bootstrapping annotation in languages that lack labeled data. Plain HMMs trained with EM tend to do poorly at it. The authors propose anchor HMMs, a restricted HMM family in which every hidden state has at least one "anchor" word that no other state can emit. This is a mild assumption for tagging: "the", for instance, is only ever a determiner. Building on the anchor-based non-negative matrix factorization of Arora et al. (2013), they design a provably consistent method-of-moments estimator. It factorizes context-based word representations to locate anchors and emission probabilities, then computes initial and transition parameters in closed form. On the universal treebank and WSJ, the method rivals Brown clustering and the log-linear HMM of Berg-Kirkpatrick et al. (2010) when universal tags are used, but trails the latter with fine-grained tags. A practical advantage is interpretability: each learned state is named by its anchor word, so labeling only the anchors labels the entire corpus.

Key points

  • The anchor assumption was checked on 10 universal treebank languages: German, English, Spanish, French, Indonesian, Italian, Japanese, Korean, Brazilian Portuguese, and Swedish. Every tag has an anchor in every language. Between 91.5% (en) and 99.5% (ja) of words are unambiguous, so the stricter Brown-model assumption fails only slightly.
  • English many-to-one accuracy with universal tags, compared against EM (BW):
    • BW: 59.8
    • CLUSTER (Brown): 62.9
    • ANCHOR: 66.1
    • ANCHOR-FEATURES: 71.4
  • The anchor models achieve the highest accuracy despite lower normalized log-likelihood (−7.05 vs −6.45 for BW), showing that likelihood and tagging accuracy diverge.
  • On the full 45-tag WSJ setting, LOG-LINEAR (Berg-Kirkpatrick et al., 2010) reaches 74.9, ahead of ANCHOR-FEATURES at 67.7. The authors attribute the gap to spelling features mattering more for fine-grained tags.
  • Proposed future work includes extending the method to log-linear or neural models and relaxing the anchor condition.

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

🎓Columbia UniversityNew York · United States241 works · 54,053 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

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

Cite

Cite as Karl Stratos, Michael Collins and Daniel Hsu. 2016. Unsupervised Part-Of-Speech Tagging with Anchor Hidden Markov Models. Transactions of the Association for Computational Linguistics.

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

@article{stratos2016unsupervised,
  title = {{Unsupervised Part-Of-Speech Tagging with Anchor Hidden Markov Models}},
  author = {Karl Stratos, Michael Collins and Daniel Hsu},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.1162/tacl\_a\_00096},
  url = {https://doi.org/10.1162/tacl_a_00096}
}

References

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

  1. Animashree Anandkumar, Daniel Hsu, and Sham M. Kakade. 2012. A method of moments for mixture models and hidden Markov models. In Twenty-Fifth Annual Conference on Learning Theory. find
  2. Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. 2014. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(1):2773– 2832. find
  3. Sanjeev Arora, Rong Ge, and Ankur Moitra. 2012. Learning topic models–going beyond SVD. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 1–10. find
  4. IEEE. Sanjeev Arora, Rong Ge, Yonatan Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. 2013. A practical algorithm for topic modeling with provable guarantees. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), pages 280–288. find
  5. Leonard E. Baum and Ted Petrie. 1966. Statistical inference for probabilistic functions of finite state Markov chains. The Annals of Mathematical Statistics, 37(6):1554–1563. Taylor Berg-Kirkpatrick, Alexandre Bouchard-Côté, John DeNero, and Dan Klein. 2010. Painless unsupervised learning with fea… find
  6. Peter F. Brown, Peter V. Desouza, Robert L. Mercer, Vincent J. Della Pietra, and Jenifer C. Lai. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467–479. find
  7. Christos Christodoulopoulos, Sharon Goldwater, and Mark Steedman. 2010. Two decades of unsupervised POS induction: How far have we come? In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 575–584. Association for Computational Linguistics.
  8. Shay B. Cohen and Michael Collins. 2014. A provably correct learning algorithm for latent-variable PCFGs. In Proceedings of ACL. find
  9. Dipanjan Das and Slav Petrov. 2011. Unsupervised part-of-speech tagging with bilingual graph-based projections. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 600– 609. Association for Computational Linguistics.
  10. Marguerite Frank and Philip Wolfe. 1956. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95–110. find
  11. Aria Haghighi and Dan Klein. 2006. Prototype-driven learning for sequence models. In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, pages 320– 327. Association for Computational Linguistics.
  12. Daniel Hsu, Sham M. Kakade, and Tong Zhang. 2012. A spectral algorithm for learning hidden Markov models. Journal of Computer and System Sciences, 78(5):1460–1480. find
  13. Mark Johnson. 2007. Why doesn’t EM find good HMM POS-taggers? In EMNLP-CoNLL, pages 296–305. Shen Li, Joao V. Graça, and Ben Taskar. 2012. Wiki-ly supervised part-of-speech tagging. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Nat…
  14. Percy Liang and Dan Klein. 2008. Analyzing the errors of unsupervised learning. In ACL, pages 879–887. find
  15. Percy Liang. 2005. Semi-supervised learning for natural language. Master’s thesis, Massachusetts Institute of Technology. Ryan T. McDonald, Joakim Nivre, Yvonne Quirmbach-Brundage, Yoav Goldberg, Dipanjan Das, Kuzman Ganchev, Keith B. Hall, Slav Petrov, Hao Zhang, Oscar Täckström, Claudia Bedini,… find
  16. Bernard Merialdo. 1994. Tagging English text with a probabilistic model. Computational Linguistics, 20(2):155–171.
  17. Slav Petrov, Dipanjan Das, and Ryan McDonald. 2012. A universal part-of-speech tagset. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12).
  18. Noah A. Smith and Jason Eisner. 2005a. Contrastive estimation: Training log-linear models on unlabeled data. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 354–362. Association for Computational Linguistics.
  19. Noah A. Smith and Jason Eisner. 2005b. Guiding unsupervised grammar induction using contrastive estimation. In Proc. of IJCAI Workshop on Grammatical Inference Applications, pages 73–82. find
  20. Karl Stratos, Do-kyum Kim, Michael Collins, and Daniel Hsu. 2014. A spectral algorithm for learning class-based n-gram models of natural language. In Proceedings of the thirtieth conference on Uncertainty in Artificial Intelligence. find
  21. Karl Stratos, Michael Collins, and Daniel Hsu. 2015. Model-based word embeddings from decompositions of count matrices. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long… find
  22. Sebastiaan A. Terwijn. 2002. On the learnability of hidden Markov models. In Grammatical Inference: Algorithms and Applications, pages 261–268. find
  23. Springer. Kristina Toutanova and Mark Johnson. 2007. A Bayesian LDA-based model for semi-supervised part-of-speech tagging. In Advances in Neural Information Processing Systems, pages 1521–1528. find
  24. Stephen A. Vavasis. 2009. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, 20(3):1364–1377. find
  25. Tianyi Zhou, Jeff A. Bilmes, and Carlos Guestrin. 2014. Divide-and-conquer learning by anchoring a conical hull. In Advances in Neural Information Processing Systems, pages 1242–1250. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/stratos-2016-unsupervised-part-speech-tagging-anchor/