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

Unsupervised Part-Of-Speech Tagging with Anchor Hidden Markov Models Karl Stratos, Michael Collins∗ and Daniel Hsu Department of Computer Science, Columbia University {stratos, mcollins, djhsu}@cs.columbia.edu Abstract We tackle unsupervised part-of-speech (POS) tagging by learning hidden Markov models (HMMs) that are particularly well-suited for the problem. These HMMs, which we call an- chor HMMs, assume that each tag is associ- ated with at least one word that can have no other tag, which is a relatively benign con- dition for POS tagging (e.g., “the” is a word that appears only under the determiner tag). We exploit this assumption and extend the non-negative matrix factorization framework of Arora et al. (2013) to design a consistent estimator for anchor HMMs. In experiments, our algorithm is competitive with strong base- lines such as the clustering method of Brown et al. (1992) and the log-linear model of Berg- Kirkpatrick et al. (2010). Furthermore, it pro- duces an interpretable model in which hidden states are automatically lexicalized by words. 1 Introduction Part-of-speech (POS) tagging without supervision is a quintessential problem in unsupervised learning for natural language processing (NLP). A major ap- plication of this task is reducing annotation cost: for instance, it can be used to produce rough syntactic annotations for a new language that has no labeled data, which can be subsequently refined by human annotators. Hidden Markov models (HMMs) are a natural choice of model and have been a workhorse for this problem. Early works estimated vanilla HMMs ∗Currently on leave at Google Inc. New York. with standard unsupervised learning methods such as the expectation-maximization (EM) algorithm, but it quickly became clear that they performed very poorly in inducing POS tags (Merialdo, 1994). Later works improved upon vanilla HMMs by incorporat- ing specific structures that are well-suited for the task, such as a sparse prior (Johnson, 2007) or a hard-clustering assumption (Brown et al., 1992). In this work, we tackle unsupervised POS tagging with HMMs whose structure is deliberately suitable for POS tagging. These HMMs impose an assump- tion that each hidden state is associated with an ob- servation state (“anchor word”) that can appear un- der no other state. For this reason, we denote this class of restricted HMMs by anchor HMMs. Such an assumption is relatively benign for POS tagging; it is reasonable to assume that each POS tag has at least one word that occurs only under that tag. For example, in English, “the” is an anchor word for the determiner tag; “laughed” is an anchor word for the verb tag. We build on the non-negative matrix factoriza- tion (NMF) framework of Arora et al. (2013) to de- rive a consistent estimator for anchor HMMs. We make several new contributions in the process. First, to our knowledge, there is no previous work di- rectly building on this framework to address unsu- pervised sequence labeling. Second, we generalize the NMF-based learning algorithm to obtain exten- sions that are important for empirical performance (Table 1). Third, we perform extensive experiments on unsupervised POS tagging …

Content truncated to 500 words