Maximum Entropy Relaxation

Jason K. Johnson, Venkat Chandrasekaran

Maximum entropy relaxation (MER) is a convex optimization approach for thinning MRF models that was originally formulated as a method to select cavity models in the context of Jason's RCM algorithm. The usual approach to model thinning is to select a tractable approximation to a given MRF, based on a sub-graph of the original MRF, which involves both selection of a sub-graph and parameter optimization in the class of MRFs defined on that sub-graph to minimize relative entropy. Because sub-graph selection is combinatorial, the MER approach was formulated as a tractable alternative that simultaneously selects both the sub-graph and corresponding parameters through solution of a convex optimization problem. Formally, we seek to maximize entropy subject to a relaxed set of marginal constraints, which require that the marginals of the relaxed distribution are close to the corresponding marginals in the orginal distribution in the sense of relative entropy.

In joint work with Venkat, this idea was formalized in an exponential family representation for Gaussian and Boltzmann models. An approach was developed to solve these problems using a modified primal-dual interior point method, which exploits sparsity of Fisher information in chordal MRFs, and an incremental method for identifying the active set of constraints in the MER problem.