Elamur Research⌕
☰
home / papers / 2005 / Contrastive Estimation: Training Log-Linear Models on Unlabeled Data

Contrastive Estimation: Training Log-Linear Models on Unlabeled Data

Summary

The paper tackles a practical gap: log-linear models such as CRFs can use rich, overlapping features, but they are normally trained on labeled data, and there are few good ways to fit them to raw text. Smith and Eisner propose contrastive estimation (CE). Each observed sentence is paired with a "neighborhood" of perturbed variants, for example sentences with one word deleted or two adjacent words swapped. Training shifts probability mass from these implicit negatives toward the real sentence. The neighborhoods are encoded as finite-state lattices, so the costly global partition function never has to be computed. CE also includes EM, conditional estimation and Riezler's approximation as special cases.

The method is tested on unsupervised POS tagging, using a tagging dictionary plus unlabeled text and modeled with WFSAs. Good neighborhoods beat EM with the same features. They also cope better when the dictionary is weakened, and with added spelling features they recover most of the lost accuracy. This shows that the choice of negative evidence can inject domain knowledge into unsupervised learning.

Key points

  • CE maximizes the probability of each sentence relative to its neighborhood N(x), marginalizing over hidden tag sequences. All objectives are written as a ratio of sums over a set A_i and a contrast set B_i, which removes the need for Z(θ).
  • The neighborhoods compared are DELORTRANS1, TRANS1 and LENGTH, against EM. The model is a WFSA whose states are POS tags.
  • Dictionary dilution conditions were:
    • all words in the dictionary,
    • a dictionary from the first 500 sentences,
    • only words with count ≥ 2,
    • only words with count ≥ 3.
  • Results on the 24K dataset with coarse tags:
    • With spelling features, DELORTRANS1 and TRANS1 recover almost fully from dilution, while LENGTH recovers far less.
    • The authors report that CE's gain over EM is twice what EM would get from ten times more data plus better search.
  • A KL-divergence analysis covered the ten tags that make up 95.6% of the data. LENGTH learned word distributions closer to the empirical ones, yet this did not help tagging.
  • There is a sizable gap between unsupervised and oracle model selection. The models used a single zero-mean, constant-variance Gaussian prior.

Interesting ideas

  • I1. Negatives from cheap perturbations: Deletions and transpositions of a real sentence can serve as negatives that are mostly worse than the original. This trick suits any task where corrupted inputs are easy to generate, such as self-supervised pretraining or grammaticality modeling.
  • I2. Choosing the denominator: Defining a small, tractable contrast set avoids intractable normalization. The same framing lets one move smoothly between joint, conditional, EM-style and margin-like training.
  • I3. Neighborhoods as an inductive bias: Neighborhoods that keep the sentence's words fixed stop the model from "cheating" through emission weights, so it must explain the data through the tags. Designing contrasts that block shortcuts is a general tool for steering latent structure.
  • I4. Dictionary dilution as a stress test: Progressively weakening prior knowledge reveals how dependent a method is on resources. This is a useful evaluation protocol for low-resource languages.
  • I5. Neighborhoods tailored to downstream tasks: The authors suggest picking neighborhoods to support tasks like spelling correction or punctuation restoration, rather than to reproduce linguists' annotations. This links unsupervised training directly to the intended application.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Part-of-speech tagging

Cited by

140 papers of our library cite it (of the 140884 whose bibliographies we read); 7 of them have a page here, 133 not yet.

Cite

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

@inproceedings{smith2005contrastive,
  title = {{Contrastive Estimation: Training Log-Linear Models on Unlabeled Data}},
  author = {Smith, Noah A. and Eisner, Jason},
  booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
  year = {2005},
  doi = {10.3115/1219840.1219884},
  url = {https://doi.org/10.3115/1219840.1219884}
}

References

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

  1. S. P. Abney. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23(4):597–617. find
  2. Y. Altun, M. Johnson, and T. Hofmann. 2003. Investigating loss functions and optimization methods for discriminative learning of label sequences. In Proc. of EMNLP. find
  3. E. Charniak. 1993. Statistical Language Learning. MIT Press. find
  4. S. Clark, J. R. Curran, and M. Osborne. 2003. Bootstrapping POS taggers using unlabelled data. In Proc. of CoNLL. find
  5. M. Collins. 2000. Discriminative reranking for natural language parsing. In Proc. of ICML. find our card
  6. K. Crammer and Y. Singer. 2001. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2(5):265–92. find
  7. A. Dempster, N. Laird, and D. Rubin. 1977. Maximum likelihood estimation from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B, 39:1–38. find
  8. J. Eisner. 2002. Parameter estimation for probabilistic finite-state transducers. In Proc. of ACL. find
  9. G. E. Hinton. 2003. Training products of experts by minimizing contrastive divergence. Technical Report GCNU TR 2000-004, University College London. find
  10. T. Jebara and A. Pentland. 1998. Maximum conditional likelihood via bound maximization and the CEM algorithm. In Proc. of NIPS. find
  11. M. Johnson, S. Geman, S. Canon, Z. Chi, and S. Riezler. 1999. Estimators for stochastic “unification-based” grammars. In Proc. of ACL. find
  12. M. Johnson. 2001. Joint and conditional estimation of tagging and parsing models. In Proc. of ACL. find
  13. B.-H. Juang and S. Katagiri. 1992. Discriminative learning for minimum error classification. IEEE Trans. Signal Processing, 40:3043–54. find
  14. D. Klein and C. D. Manning. 2002. Conditional structure vs. conditional estimation in NLP models. In Proc. of EMNLP. find
  15. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML. find
  16. D. C. Liu and J. Nocedal. 1989. On the limited memory method for large scale optimization. Mathematical Programming B, 45(3):503–28. find
  17. A. McCallum and W. Li. 2003. Early results for named-entity extraction with conditional random fields. In Proc. of CoNLL. find
  18. B. Merialdo. 1994. Tagging English text with a probabilistic model. Computational Linguistics, 20(2):155–72. find our card
  19. Y. Miyao and J. Tsujii. 2002. Maximum entropy estimation for feature forests. In Proc. of HLT. find
  20. A. Ratnaparkhi, S. Roukos, and R. T. Ward. 1994. A maximum entropy model for parsing. In Proc. of ICSLP. find
  21. S. Riezler, D. Prescher, J. Kuhn, and M. Johnson. 2000. Lexicalized stochastic modeling of constraint-based grammars using log-linear measures and EM training. In Proc. of ACL. find
  22. S. Riezler. 1999. Probabilistic Constraint Logic Programming. Ph.D. thesis, Universität Tübingen. find
  23. R. Rosenfeld. 1994. Adaptive Statistical Language Modeling: A Maximum Entropy Approach. Ph.D. thesis, CMU. find
  24. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of HLT-NAACL. find
  25. N. A. Smith and J. Eisner. 2004. Annealing techniques for unsupervised statistical language learning. In Proc. of ACL. find
  26. N. A. Smith and J. Eisner. 2005. Guiding unsupervised grammar induction using contrastive estimation. In Proc. of IJ-CAI Workshop on Grammatical Inference Applications. find
  27. R. E. Tarjan. 1981. A unified approach to path problems. Journal of the ACM, 28(3):577–93. find
  28. V. Valtchev, J. J. Odell, P. C. Woodland, and S. J. Young. 1997. MMIE training of large vocabulary speech recognition systems. Speech Communication, 22(4):303–14. find
  29. S. Wang, R. Rosenfeld, Y. Zhao, and D. Schuurmans. 2002. The latent maximum entropy principle. In Proc. of ISIT. find
  30. D. Yarowsky. 1995. Unsupervised word sense disambiguation rivaling supervised methods. In Proc. of ACL. find our card
  31. X. Zhu and Z. Ghahramani. 2002. Towards semi-supervised classification with Markov random fields. Technical Report CMU-CALD-02-106, Carnegie Mellon University. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/smith-2005-contrastive-estimation-training-log-linear/