Contrastive Estimation: Training Log-Linear Models on Unlabeled Data

Noah A. Smith, Jason EisnerACL 2005 · OpenReview

Abstract

Conditional random fields (CRFs) are effective at sequence labeling tasks but typically require supervised training. To leverage unlabeled data, we describe contrastive estimation (CE), a novel unsupervised approach for log-linear models. CE exploits implicit negative evidence by moving probability mass from "neighborhoods" of perturbed, incorrect sentences toward observed ones. Applied to part-of-speech (POS) tagging, CE outperforms Expectation-Maximization (EM), is more robust to dictionary degradation, and effectively incorporates additional features.

Introduction

Unsupervised learning of hidden structures, such as POS tags, often relies on the Expectation-Maximization (EM) algorithm. However, EM faces challenges with modern log-linear models like CRFs. First, calculating the global partition function for normalization is often computationally intractable. Second, EM lacks explicit guidance on where to draw probability mass from, often converging to linguistically poor local maxima. Contrastive Estimation addresses these by focusing on local "neighborhoods" of observations.

Methods: Contrastive Estimation

The core principle of CE is that natural language is "delicate": minor perturbations to a valid sentence usually result in ungrammaticality. These perturbations serve as implicit negative evidence. Instead of maximizing the probability of an observation $x$ relative to all possible strings, CE maximizes it relative to a neighborhood $N(x)$.

Neighborhood Functions and Lattices

The authors define several neighborhood functions to generate "near-miss" negative examples:

  • DEL1WORD: Strings formed by deleting one word.
  • TRANS1: Strings formed by transposing adjacent words.
  • LENGTH: All strings of the same length as the original.

These neighborhoods are represented as acyclic lattices, enabling efficient dynamic programming to sum over the neighborhood without a global partition function.

Lattice representations of neighborhood functions for the sentence "natural language is a delicate thing".

Experimental Setup

Evaluation was conducted on the Wall Street Journal (WSJ) portion of the Penn Treebank. The task was unsupervised POS tagging given a tagging dictionary. Training sets ranged from 12,000 to 96,000 words, with a 5,000-word development set for hyperparameter tuning.

Results and Discussion

CE significantly outperformed standard HMMs trained with EM. On the 96,000-word dataset, the LENGTH neighborhood achieved 78.9% accuracy, while EM reached only 60.9%.

Comparison of CE neighborhoods and EM performance. The table shows accuracy across different training set sizes, highlighting CE's superior performance.

Key Insights

  • Source of Probability Mass: CE demonstrates that where probability mass is taken from is critical. By contrasting observed sentences with "nearly correct" ones, the model learns fine-grained syntactic features.
  • Domain Knowledge: Neighborhood selection allows researchers to inject linguistic intuition (e.g., TRANS1 emphasizes word order).
  • Robustness: CE is more resilient to incomplete tagging dictionaries. Unlike EM, CE can easily incorporate "spelling features" (suffixes, capitalization) to recover accuracy lost from dictionary decay.

Conclusion

Contrastive Estimation provides a computationally efficient and linguistically grounded framework for training log-linear models on unlabeled data. While performance depends on neighborhood design and initialization, CE's ability to exploit local contrastive evidence makes it a powerful alternative to EM for unsupervised sequence labeling. Future work includes extending CE to more complex structures like grammar induction.

Summary updated

Abstract

Conditional random fields (Lafferty et al., 2001) are quite effective at sequence labeling tasks like shallow parsing (Sha and Pereira, 2003) and named-entity extraction (McCallum and Li, 2003). CRFs are log-linear, allowing the incorporation of arbitrary 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 exploiting implicit negative evidence and is computationally efficient. Applied to a sequence labeling problem---POS tagging given a tagging dictionary and unlabeled text---contrastive estimation outperforms EM (with the same feature set), is more robust to degradations of the dictionary, and can largely recover by modeling additional features.
BibTeX
@inproceedings{smith2005contrastive,
  author = {Noah A. Smith and Jason Eisner},
  title = {{Contrastive Estimation: Training Log-Linear Models on Unlabeled Data}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2005},
  url = {https://openreview.net/forum?id=HkbxUiluWH},
}
Figure