Semi-Supervised Learning of Sequence Models with Method of Moments

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 287–296, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Semi-Supervised Learning of Sequence Models with the Method of Moments Zita Marinho∗♯ Andr´e F. T. Martins†♥♦ Shay B. Cohen♣ Noah A. Smith♠ ∗Instituto de Sistemas e Rob´otica, Instituto Superior T´ecnico, 1049-001 Lisboa, Portugal †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, 1049-001 Lisboa, Portugal ♯School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA ♥Unbabel Lda, Rua Visconde de Santar´em, 67-B, 1000-286 Lisboa, Portugal ♦Priberam Labs, Alameda D. Afonso Henriques, 41, 2o, 1000-123 Lisboa, Portugal ♣School of Informatics, University of Edinburgh, Edinburgh EH8 9AB, UK ♠Computer Science & Engineering, University of Washington, Seattle, WA 98195, USA zmarinho@cmu.edu, andre.martins@unbabel.com, scohen@inf.ed.ac.uk, nasmith@cs.washington.edu Abstract We propose a fast and scalable method for semi-supervised learning of sequence models, based on anchor words and moment matching. Our method can handle hidden Markov mod- els with feature-based log-linear emissions. Unlike other semi-supervised methods, no de- coding passes are necessary on the unlabeled data and no graph needs to be constructed— only one pass is necessary to collect moment statistics. The model parameters are estimated by solving a small quadratic program for each feature. Experiments on part-of-speech (POS) tagging for Twitter and for a low-resource lan- guage (Malagasy) show that our method can learn from very few annotated sentences. 1 Introduction Statistical learning of NLP models is often lim- ited by the scarcity of annotated data. Weakly su- pervised methods have been proposed as an alter- native to laborious manual annotation, combining large amounts of unlabeled data with limited re- sources, such as tag dictionaries or small annotated datasets (Merialdo, 1994; Smith and Eisner, 2005; Garrette et al., 2013). Unfortunately, most semi- supervised learning algorithms for the structured problems found in NLP are computationally expen- sive, requiring multiple decoding passes through the unlabeled data, or expensive similarity graphs. More scalable learning algorithms are in demand. In this paper, we propose a moment-matching method for semi-supervised learning of sequence models. Spectral learning and moment-matching approaches have recently proved a viable alternative to expectation-maximization (EM) for unsupervised learning (Hsu et al., 2012; Balle and Mohri, 2012; Bailly et al., 2013), supervised learning with latent variables (Cohen and Collins, 2014; Quattoni et al., 2014; Stratos et al., 2013) and topic modeling (Arora et al., 2013; Nguyen et al., 2015). These methods have learnability guarantees, do not suffer from lo- cal optima, and are computationally less demanding. Unlike spectral methods, ours does not require an orthogonal decomposition of any matrix or tensor. Instead, it considers a more restricted form of super- vision: words that have unambiguous annotations, so-called anchor words (Arora et al., 2013). Rather than identifying anchor words from unlabeled data (Stratos et al., 2016), we extract them from a small labeled dataset or from a dictionary. Given the an- chor words, the estimation of the model parameters can be made efficient by collecting moment statistics from unlabeled data, then solving a small quadratic program for each …

Content truncated to 500 words