Contrastive Estimation: Training Log-Linear Models on Unlabeled Data

Proceedings of the 43rd Annual Meeting of the ACL, pages 354–362, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Contrastive Estimation: Training Log-Linear Models on Unlabeled Data∗ Noah A. Smith and Jason Eisner Department of Computer Science / Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {nasmith,jason}@cs.jhu.edu Abstract Conditional random fields (Lafferty et al., 2001) are quite effective at sequence labeling tasks like shal- low parsing (Sha and Pereira, 2003) and named- entity extraction (McCallum and Li, 2003). CRFs are log-linear, allowing the incorporation of arbi- trary features into the model. To train on unlabeled data, we require unsupervised estimation methods for log-linear models; few exist. We describe a novel approach, contrastive estimation. We show that the new technique can be intuitively understood as ex- ploiting implicit negative evidence and is computa- tionally efficient. Applied to a sequence labeling problem—POS tagging given a tagging dictionary and unlabeled text—contrastive estimation outper- forms EM (with the same feature set), is more robust to degradations of the dictionary, and can largely re- cover by modeling additional features. 1 Introduction Finding linguistic structure in raw text is not easy. The classical forward-backward and inside-outside algorithms try to guide probabilistic models to dis- cover structure in text, but they tend to get stuck in local maxima (Charniak, 1993). Even when they avoid local maxima (e.g., through clever initializa- tion) they typically deviate from human ideas of what the “right” structure is (Merialdo, 1994). One strategy is to incorporate domain knowledge into the model’s structure. Instead of blind HMMs or PCFGs, one could use models whose features ∗This work was supported by a Fannie and John Hertz Foundation fellowship to the first author and NSF ITR grant IIS- 0313193 to the second author. The views expressed are not nec- essarily endorsed by the sponsors. The authors also thank three anonymous ACL reviewers for helpful comments, colleagues at JHU CLSP (especially David Smith and Roy Tromble) and Miles Osborne for insightful feedback, and Eric Goldlust and Markus Dreyer for Dyna language support. are crafted to pay attention to a range of domain- specific linguistic cues. Log-linear models can be so crafted and have already achieved excellent perfor- mance when trained on annotated data, where they are known as “maximum entropy” models (Ratna- parkhi et al., 1994; Rosenfeld, 1994). Our goal is to learn log-linear models from unannotated data. Since the forward-backward and inside-outside algorithms are instances of Expectation-Maximization (EM) (Dempster et al., 1977), a natural approach is to construct EM algo- rithms that handle log-linear models. Riezler (1999) did so, then resorted to an approximation because the true objective function was hard to normalize. Stepping back from EM, we may generally en- vision parameter estimation for probabilistic mod- eling as pushing probability mass toward the train- ing examples. We must consider not only where the learner pushes the mass, but also from where the mass is taken. In this paper, we describe an alterna- tive to EM: contrastive estimation (CE), which …

Content truncated to 500 words