Paper: Entire Relaxation Path for Maximum Entropy Problems

ACL ID D11-1087
Title Entire Relaxation Path for Maximum Entropy Problems
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2011

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 relaxatio...