Structural Maxent Models
Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Umar Syed · 2015
We present a new class of density estimation models, Structural Maxent models, with fea-ture functions selected from a union of possi-bly very complex sub-families and yet benefit-ing from strong learning guarantees. The de-sign 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 per-formance improves on that of existing L1-norm regularized Maxent algorithms. We further sim-ilarly define conditional Structural Maxent mod-els for multi-class classification problems. These are conditional probability models also making use of a union of possibly complex feature sub-families. We prove a duality theorem for these models as well, which reveals their connection with existing binary and multi-class deep boost-ing algorithms.