Elamur Research⌕
☰
home / papers / 2010 / Practical Very Large Scale CRFs

Practical Very Large Scale CRFs

Paper · 2010 · Thomas Lavergne, Olivier Cappé and François Yvon

Summary

Linear-chain CRFs become expensive as the label set grows. Training and decoding costs rise quadratically with the number of labels, and so does the number of features that look at pairs of neighbouring labels. Practitioners have therefore tended to keep label sets small or prune label-pair features by hand.

Lavergne, Cappé and Yvon show that sparsity from an ℓ1 penalty (combined with ℓ2 as an elastic net) solves much of this problem. It shortens training and produces very compact models that decode faster and use less memory. Within one software package, they reimplement and compare three recent ℓ1 training methods: orthant-wise quasi-Newton (OWL-QN), stochastic gradient descent (SGD) and block coordinate descent (BCD). They test them on text phonetization (Nettalk), a harder Nettalk+prosody variant and part-of-speech tagging.

Models with over a hundred labels and billions of candidate features proved trainable. Accuracy kept improving as feature sets grew, matching or beating the best published results. The resulting toolkit, Wapiti, is open source, which makes very large structured models practical for NLP sequence labelling.

Key points

  • The parameter count is roughly |Y|² × |X|train once each label-pair feature is conjoined with an observation test. Some tools cannot express such features at all; for example, CRFsuite only allows label bigrams without observation tests.
  • The three ℓ1 training methods compared are:
    • OWL-QN (Andrew and Gao, 2007)
    • SGD with ℓ1 (Tsuruoka et al., 2009)
    • coordinate descent (Sokolovska et al., 2010)
  • The authors' recommendations:
    • OWL-QN suits small or moderate problems.
    • BCD shines with huge feature sets over small observation alphabets and is the most memory-efficient.
    • SGD followed by fine tuning is the usual best choice for large-scale problems.
  • On Nettalk+prosody, the biggest model OWL-QN could handle was the 3-gram model, with 69 million features and 48 minutes of training. SGD and BCD scaled further, and performance rose steadily with feature count.
  • For POS tagging, incremental BCD training produced a model with about 4 billion features, of which roughly 400,000 were active. Its error rate was 2.63% on dev and 2.78% on test, which compares well with strong earlier systems. The code is released as Wapiti (wapiti.limsi.fr).

Interesting ideas

  • I1. Using ℓ1 sparsity to save compute, not only to select features. Zeroed weights mean fewer features to extract and smaller potential tables, so both training and inference get cheaper. This is worth applying to any model with a huge, mostly useless feature space.
  • I2. Growing features hierarchically. Training proceeds in stages, and a more specific feature (a longer n-gram or wider window) is added only if its shorter "parent" survived the ℓ1 selection. This keeps the combinatorial explosion of context features manageable and could transfer to other feature-rich taggers or classifiers.
  • I3. Using an elastic net instead of pure ℓ1. Adding a small ℓ2 term alongside ℓ1 lets you control sparsity while avoiding numerical trouble in very high dimensions. It is a cheap safeguard for any large sparse linear model.
  • I4. Comparing optimizers inside one codebase. Reimplementing all competing optimizers in the same package makes speed and accuracy comparisons fair. This is a good practice when benchmarking training algorithms for our own projects.
  • I5. Choosing the optimizer by problem shape. The best training method depends on the problem's size and on how many observation values there are. Profiling these properties before committing to an optimizer can save substantial training time.

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, topics and concepts

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

Cite

Cite as Thomas Lavergne, Olivier Cappé and François Yvon. 2010. Practical Very Large Scale CRFs. Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{lavergne2010practical,
  title = {{Practical Very Large Scale CRFs}},
  author = {Thomas Lavergne, Olivier Cappé and François Yvon},
  booktitle = {Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/P10-1052/}
}

References

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

  1. Galen Andrew and Jianfeng Gao. 2007. Scalable training of l1-regularized log-linear models. In Proceedings of the International Conference on Machine Learning, pages 33–40, Corvalis, Oregon. find
  2. Léon Bottou. 2004. Stochastic learning. In Olivier Bousquet and Ulrike von Luxburg, editors, Advanced Lectures on Machine Learning, Lecture Notes in Artificial Intelligence, LNAI 3176, pages 146–168. Springer Verlag, Berlin. find
  3. Léon Bottou. 2007. Stochastic gradient descent (sgd) implementation. http://leon.bottou.org/projects/sgd. ↗
  4. Stanley Chen. 2009. Performance prediction for exponential language models. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 450–458, Boulder, Colorado, June. find
  5. Trevor Cohn. 2006. Efficient inference in large conditional random fields. In Proceedings of the 17th European Conference on Machine Learning, pages 606–613, Berlin, September. find
  6. Thomas G. Dietterich, Adam Ashenfelter, and Yaroslav Bulatov. 2004. Training conditional random fields via gradient tree boosting. In Proceedings of the International Conference on Machine Learning, Banff, Canada. find
  7. Miroslav Dudı́k, Steven J. Phillips, and Robert E. Schapire. 2004. Performance guarantees for regularized maximum entropy density estimation. In John Shawe-Taylor and Yoram Singer, editors, Proceedings of the 17th annual Conference on Learning Theory, volume 3120 of Lecture Notes in Computer Science… find
  8. Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. 2008. Efficient, feature-based, conditional random field parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pages 959–967, Columbus, Ohio.
  9. Jerome Friedman, Trevor Hastie, and Rob Tibshirani. 2008. Regularization paths for generalized linear models via coordinate descent. Technical report, Department of Statistics, Stanford University. find
  10. Jianfeng Gao, Galen Andrew, Mark Johnson, and Kristina Toutanova. 2007. A comparative study of parameter estimation methods for statistical natural language processing. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 824–831, Prague, Czech republic. find
  11. Minwoo Jeong, Chin-Yew Lin, and Gary Geunbae Lee. 2009. Efficient inference of crfs for large-scale natural language data. In Proceedings of the Joint Conference of the Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processi… find
  12. Jun’ichi Kazama and Jun’ichi Tsujii. 2003. Evaluation and extension of maximum entropy models with inequality constraints. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing, pages 137–144. find
  13. Taku Kudo. 2005. CRF++: Yet another CRF toolkit. http://crfpp.sourceforge.net/. ↗
  14. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning, pages 282–289. Morgan Kaufmann, San Francisco, CA. find
  15. Percy Liang, Hal Daumé, III, and Dan Klein. 2008. Structure compilation: trading structure for features. In Proceedings of the 25th international conference on Machine learning, pages 592–599. find
  16. Dong C. Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45:503–528. find
  17. Gideon Mann, Ryan McDonald, Mehryar Mohri, Nathan Silberman, and Dan Walker. 2009. Efficient large-scale distributed training of conditional maximum entropy models. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A.Culotta, editors, Advances in Neural Information Processing Systems… find
  18. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2):313–330.
  19. Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer. find
  20. Naoaki Okazaki. 2007. CRFsuite: A fast implementation of conditional random fields (CRFs). http://www.chokkan.org/software/crfsuite/. ↗
  21. Chris Pal, Charles Sutton, and Andrew McCallum. 2006. Sparse forward-backward using minimum divergence beams for fast training of conditional random fields. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Toulouse, France. find
  22. Simon Perkins, Kevin Lacker, and James Theiler. 2003. Grafting: Fast, incremental feature selection by gradient descent in function space. Journal of Machine Learning Research, 3:1333–1356. find
  23. Vasin Punyakanok, Dan Roth, Wen tau Yih, and Dav Zimak. 2005. Learning and inference over constrained output. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1124–1129. find
  24. Xian Qian, Xiaoqian Jiang, Qi Zhang, Xuanjing Huang, and Lide Wu. 2009. Sparse higher order conditional random fields for improved sequence labeling. In Proceedings of the Annual International Conference on Machine Learning, pages 849–856. find
  25. Stefan Riezler and Alexander Vasserman. 2004. Incremental feature selection and l1 regularization for relaxed maximum-entropy modeling. In Dekang Lin and Dekai Wu, editors, Proceedings of the conference on Empirical Methods in Natural Language Processing, pages 174–181, Barcelona, Spain, July. find
  26. Antoine Rozenknop. 2002. Modèles syntaxiques probabilistes non-génératifs. Ph.D. thesis, Dpt. d’informatique, École Polytechnique Fédérale de Lausanne. find
  27. Terrence J. Sejnowski and Charles R. Rosenberg. 1987. Parallel networks that learn to pronounce english text. Complex Systems, 1. find
  28. Libin Shen, Giorgio Satta, and Aravind Joshi. 2007. Guided learning for bidirectional sequence classification. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 760–767, Prague, Czech Republic. find
  29. Nataliya Sokolovska, Thomas Lavergne, Olivier Cappé, and François Yvon. 2010. Efficient learning of sparse conditional random fields for supervised sequence labelling. IEEE Selected Topics in Signal Processing. find
  30. Charles Sutton and Andrew McCallum. 2006. An introduction to conditional random fields for relational learning. In Lise Getoor and Ben Taskar, editors, Introduction to Statistical Relational Learning, Cambridge, MA. The MIT Press. find
  31. Jun Suzuki and Hideki Isozaki. 2008. Semi-supervised sequential labeling and segmentation using gigaword scale unlabeled data. In Proceedings of the Conference of the Association for Computational Linguistics on Human Language Technology, pages 665–673, Columbus, Ohio. find
  32. Robert Tibshirani. 1996. Regression shrinkage and selection via the lasso. J.R.Statist.Soc.B, 58(1):267– 288. find
  33. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, pages 173…
  34. Yoshimasa Tsuruoka, Jun’ichi Tsujii, and Sophia Ananiadou. 2009. Stochastic gradient descent training for l1-regularized log-linear models with cumulative penalty. In Proceedings of the Joint Conference of the Annual Meeting of the Association for Computational Linguistics and the International Join… find
  35. S. V. N. Vishwanathan, Nicol N. Schraudolph, Mark Schmidt, and Kevin Murphy. 2006. Accelerated training of conditional random fields with stochastic gradient methods. In Proceedings of the 23th International Conference on Machine Learning, pages 969–976. ACM Press, New York, NY, USA. find
  36. Hui Zhou and Trevor Hastie. 2005. Regularization and variable selection via the elastic net. J. Royal. Stat. Soc. B., 67(2):301–320. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lavergne-2010-practical-very-large-scale-crfs/