Structural maxent models

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Umar Syed

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

Abstract

We present a new class of density estimation models, Structural Maxent models, with feature functions selected from a union of possibly very complex sub-families and yet benefiting from strong learning guarantees. The design of our models is based on a new principle supported by uniform convergence bounds and taking into consideration the complexity of the different sub-families composing the full set of features. We prove new data-dependent learning bounds for our models, expressed in terms of the Rademacher complexities of these sub-families. We also prove a duality theorem, which we use to derive our Structural Maxent algorithm. We give a full description of our algorithm, including the details of its derivation, and report the results of several experiments demonstrating that its performance improves on that of existing Li-norm regularized Maxent algorithms. We further similarly define conditional Structural Maxent models for multi-class classification problems. These are conditional probability models also making use of a union of possibly complex feature subfamilies. We prove a duality theorem for these models as well, which reveals their connection with existing binary and multi-class deep boosting algorithms.

Original languageEnglish (US)
Title of host publication32nd International Conference on Machine Learning, ICML 2015
EditorsFrancis Bach, David Blei
PublisherInternational Machine Learning Society (IMLS)
Pages391-399
Number of pages9
ISBN (Electronic)9781510810587
StatePublished - 2015
Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
Duration: Jul 6 2015Jul 11 2015

Publication series

Name32nd International Conference on Machine Learning, ICML 2015
Volume1

Other

Other32nd International Conference on Machine Learning, ICML 2015
CountryFrance
CityLile
Period7/6/157/11/15

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Structural maxent models'. Together they form a unique fingerprint.

  • Cite this

    Cortes, C., Kuznetsov, V., Mohri, M., & Syed, U. (2015). Structural maxent models. In F. Bach, & D. Blei (Eds.), 32nd International Conference on Machine Learning, ICML 2015 (pp. 391-399). (32nd International Conference on Machine Learning, ICML 2015; Vol. 1). International Machine Learning Society (IMLS).