Structural maxent models
Venue
Proceedings of the Thirty-Second International Conference on Machine Learning (ICML 2015)
Publication Year
2015
Authors
Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Umar Syed
BibTeX
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 L1-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.
