Efficient decomposed learning for structured prediction

Rajhans Samdani, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Structured prediction is the cornerstone of several machine learning applications. Unfortunately, in structured prediction settings with expressive inter-variable interactions, exact inference-based learning algorithms, e.g. Structural SVM, are often intractable. We present a new way, Decomposed Learning (DecL), which performs efficient learning by restricting the inference step to a limited part of the structured spaces. We provide characterizations based on the structure, target parameters, and gold labels, under which DecL is equivalent to exact learning. We then show that in real world settings, where our theoretical assumptions may not completely hold, DecL-based algorithms are significantly more efficient and as accurate as exact learning.

Original languageEnglish (US)
Title of host publicationProceedings of the 29th International Conference on Machine Learning, ICML 2012
Pages217-224
Number of pages8
StatePublished - Oct 10 2012
Event29th International Conference on Machine Learning, ICML 2012 - Edinburgh, United Kingdom
Duration: Jun 26 2012Jul 1 2012

Publication series

NameProceedings of the 29th International Conference on Machine Learning, ICML 2012
Volume1

Other

Other29th International Conference on Machine Learning, ICML 2012
CountryUnited Kingdom
CityEdinburgh
Period6/26/127/1/12

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Education

Fingerprint Dive into the research topics of 'Efficient decomposed learning for structured prediction'. Together they form a unique fingerprint.

  • Cite this

    Samdani, R., & Roth, D. (2012). Efficient decomposed learning for structured prediction. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (pp. 217-224). (Proceedings of the 29th International Conference on Machine Learning, ICML 2012; Vol. 1).