Elamur Research⌕
☰
home / papers / 2010 / Painless Unsupervised Learning with Features

Painless Unsupervised Learning with Features

Paper · 2010 · Taylor Berg-Kirkpatrick, Alexandre Bouchard-Côté, John DeNero et al.

Summary

The paper argues that domain knowledge in unsupervised NLP models usually has to be encoded through conditional independence structure. That approach is subtle to get right and often forces researchers to design new inference procedures. The authors propose a lightweight alternative. They keep the familiar locally normalized generative models, but replace each component multinomial with a small multi-class logistic regression over hand-designed features. Training still uses EM with an unchanged E-step, and the M-step becomes gradient-based optimization of the kind used for maximum-entropy classifiers. They also describe a second option: optimizing the regularized marginal likelihood directly with LBFGS. The approach is tested on four tasks, each with a few linguistically motivated feature templates:

  • POS induction with an HMM
  • DMV grammar induction
  • word alignment with IBM Model 1 and the HMM aligner
  • word segmentation

In every case the feature-enhanced model beats its plain multinomial version. In several cases it matches or exceeds more complex state-of-the-art systems. The significance is practical: rich features become usable in unsupervised learning with standard, well-understood building blocks.

Key points

  • With only indicator (BASIC) features, the logistic parameterization is exactly equivalent to a standard multinomial; extra coarse features are shared across many outcomes.
  • Directly optimizing marginal likelihood with LBFGS gave higher accuracy than EM for several models. EM remains attractive when computing expected counts is costly.
  • Word alignment: feature-enhanced training cut AER by 2.4 for IBM Model 1 and 3.8 for the HMM model. The dictionary and edit-distance features received large positive weights.
  • Word segmentation on the phonetic Bernstein-Ratner corpus (9790 child-directed utterances) reached F1 88.0:
    • baseline (Liang and Klein's unigram model): F1 76.9
    • sampling-based nonparametric Bayesian models: F1 87
  • Locally normalized feature models outperformed globally normalized MRF counterparts in the authors' experiments. They also avoid computing expectations over the full joint distribution.

Interesting ideas

  • I1. Features inside each multinomial. Turning each conditional distribution of a generative model into a tiny log-linear classifier injects knowledge without changing the dependency structure. Existing dynamic programs such as forward-backward therefore keep working, which could help any HMM- or count-based model for Ukrainian data, such as tagging or morphology induction.
  • I2. Reusing the supervised gradient. The unsupervised M-step gradient has the same form as supervised logistic regression, with expected counts in place of observed counts. Existing maxent code can therefore be reused almost unchanged.
  • I3. Direct gradient on marginal likelihood. The direct LBFGS optimization needs no machinery beyond what EM already requires, yet often finds better solutions. It is an inexpensive experiment to run alongside EM.
  • I4. Coarse projections of the input. Mapping phonemes to broader classes and adding prefix/suffix indicators lets the model learn general word shapes. The same trick, applied to characters or morphemes, could support segmentation or tokenization in other languages and scripts.
  • I5. Inspecting learned weights. Checking which features get large weights, as with the dictionary and edit-distance features in alignment, is a simple way to sanity-check whether the injected knowledge is actually being used.

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

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 works

Cite

Cite as Taylor Berg-Kirkpatrick, Alexandre Bouchard-Côté, John DeNero and Dan Klein. 2010. Painless Unsupervised Learning with Features. Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics.

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

@inproceedings{bergkirkpatrick2010painless,
  title = {{Painless Unsupervised Learning with Features}},
  author = {Taylor Berg-Kirkpatrick, Alexandre Bouchard-Côté, John DeNero and Dan Klein},
  booktitle = {Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/N10-1083/}
}

References

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

  1. N. F. Ayan, B. Dorr, and C. Monz. 2005. Combining word alignments using neural networks. In Empirical Methods in Natural Language Processing. find
  2. N. Bernstein-Ratner. 1987. The phonology of parent-child speech. K. Nelson and A. van Kleeck. find
  3. M. Bisani and H. Ney. 2008. Joint-sequence models for grapheme-to-phoneme conversion. find
  4. A. Bouchard-Côté, P. Liang, D. Klein, and T. L. Griffiths. 2008. A probabilistic approach to language change. In Neural Information Processing Systems. find
  5. P. F. Brown, S. A. Della Pietra, V. J. Della Pietra, and R. L. Mercer. 1994. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics. find
  6. S. F. Chen. 2003. Conditional and joint models for grapheme-to-phoneme conversion. In Eurospeech. find
  7. S. B. Cohen and N. A. Smith. 2009. Shared logistic normal distributions for soft parameter tying in unsupervised grammar induction. In North American Chapter of the Association for Computational Linguistics.
  8. A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological). find
  9. J. DeNero and D. Klein. 2007. Tailoring word alignments to syntactic machine translation. In Association for Computational Linguistics. find
  10. D. Elworthy. 1994. Does Baum-Welch re-estimation help taggers? In Association for Computational Linguistics. find
  11. S. Goldwater and T. L. Griffiths. 2007. A fully Bayesian approach to unsupervised part-of-speech tagging. In Association for Computational Linguistics.
  12. S. Goldwater, T. L. Griffiths, and M. Johnson. 2006. Contextual dependencies in unsupervised word segmentation. In International Conference on Computational Linguistics/Association for Computational Linguistics.
  13. A. Haghighi and D. Klein. 2006. Prototype-driven learning for sequence models. In Association for Computational Linguistics.
  14. A. Haghighi, J. Blitzer, J. DeNero, and D. Klein. 2009. Better word alignments with supervised ITG models. In Association for Computational Linguistics.
  15. M. Johnson and S. Goldwater. 2009. Improving non-parametric Bayesian inference: Experiments on unsupervised word segmentation with adaptor grammars. In North American Chapter of the Association for Computational Linguistics. find
  16. M. Johnson, T. L. Griffiths, and S. Goldwater. 2007. Adaptor grammars: a framework for specifying compositional nonparametric Bayesian models. In Neural Information Processing Systems. find
  17. M. Johnson. 2007. Why doesnt EM find good HMM POS-taggers? In Empirical Methods in Natural Language Processing/Computational Natural Language Learning.
  18. D. Klein and C. D. Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Association for Computational Linguistics. find
  19. P. Liang and D. Klein. 2009. Online EM for unsupervised models. In North American Chapter of the Association for Computational Linguistics. find
  20. P. Liang, B. Taskar, and D. Klein. 2006. Alignment by agreement. In North American Chapter of the Association for Computational Linguistics.
  21. D. C. Liu, J. Nocedal, and C. Dong. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming. find
  22. M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini. 1993. Building a large annotated corpus of English: the penn treebank. Computational Linguistics.
  23. B. Merialdo. 1994. Tagging English text with a probabilistic model. Computational Linguistics.
  24. R. Neal and G. E. Hinton. 1998. A view of the EM algorithm that justifies incremental, sparse, and other variants. In Learning in Graphical Models. Kluwer Academic Publishers. find
  25. H. Ney and S. Vogel. 1996. HMM-based word alignment in statistical translation. In International Conference on Computational Linguistics. find
  26. F. J. Och and H. Ney. 2000. Improved statistical alignment models. In Association for Computational Linguistics.
  27. R. Salakhutdinov, S. Roweis, and Z. Ghahramani. 2003. Optimization with EM and expectation-conjugate-gradient. In International Conference on Machine Learning. find
  28. N. A. Smith and J. Eisner. 2005. Contrastive estimation: Training log-linear models on unlabeled data. In Association for Computational Linguistics.
  29. N. A. Smith and M. Johnson. 2007. Weighted and probabilistic context-free grammars are equally expressive. Computational Linguistics. find
  30. I. G. Varea, F. J. Och, H. Ney, and F. Casacuberta. 2002. Refined lexicon models for statistical machine translation using a maximum entropy approach. In Association for Computational Linguistics. find
  31. N. Xue, F-D Chiou, and M. Palmer. 2002. Building a large-scale annotated Chinese corpus. In International Conference on Computational Linguistics.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kirkpatrick-2010-painless-unsupervised-learning-features/