Entire Relaxation Path for Maximum Entropy Problems

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 941–948, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Entire Relaxation Path for Maximum Entropy Problems Moshe Dubiner Google moshe@google.com Yoram Singer Google singer@google.com Abstract We discuss and analyze the problem of find- ing a distribution that minimizes the relative entropy to a prior distribution while satisfying max-norm constraints with respect to an ob- served distribution. This setting generalizes the classical maximum entropy problems as it relaxes the standard constraints on the ob- served values. We tackle the problem by in- troducing a re-parametrization in which the unknown distribution is distilled to a single scalar. We then describe a homotopy between the relaxation parameter and the distribution characterizing parameter. The homotopy also reveals an aesthetic symmetry between the prior distribution and the observed distribu- tion. We then use the reformulated problem to describe a space and time efficient algorithm for tracking the entire relaxation path. Our derivations are based on a compact geomet- ric view of the relaxation path as a piecewise linear function in a two dimensional space of the relaxation-characterization parameters. We demonstrate the usability of our approach by applying the problem to Zipfian distribu- tions over a large alphabet. 1 Introduction Maximum entropy (max-ent) models and its dual counterpart, logistic regression, is a popular and ef- fective tool in numerous natural language process- ing tasks. The principle of maximum entropy was spelled out explicitly by E.T. Jaynes (1968). Ap- plications of maximum entropy approach to natural language processing are numerous. A notable ex- ample and probably one of the earliest usages and generalizations of the maximum entropy principle to language processing is the work of Berger, Della Pietra×2, and Lafferty (Berger et al., 1996, Della Pietra et al., 1997). The original formulation of max-ent cast the problem as the task of finding the distribution attaining the highest entropy subject to equality constraints. While this formalism is aes- thetic and paves the way to a simple dual in the form of a unique Gibbs distribution (Della Pietra et al., 1997), it does not provide sufficient tools to deal with input noise and sparse representation of the target Gibbs distribution. To mitigate these issues, numerous relaxation schemes of the equality con- straints have been proposed. A notable recent work by Dudik, Phillips, and Schapire (2007) provided a general constraint-relaxation framework. See also the references therein for an in depth overview of other approaches and generalizations of max-ent. The constraint relaxation surfaces a natural param- eter, namely, a relaxation value. The dual form of this free parameter is the regularization value of pe- nalized logistic regression problems. Typically this parameter is set by experimentation using cross val- idation technique. The relaxed maximum-entropy problem setting is the starting point of this paper. In this paper we describe and analyze a frame- work for efficiently tracking the entire relaxation path of constrained max-ent problems. We start in Sec. 2 with a generalization in which we discuss …

Content truncated to 500 words