Structural maxent models

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.

• Machine Intelligence