A Caltech Library Service

Learning Markov Structure by Maximum Entropy Relaxation

Johnson, Jason K. and Chandrasekaran, Venkat and Willsky, Alan S. (2007) Learning Markov Structure by Maximum Entropy Relaxation. JMLR Workshop and Conference Proceedings, 2 . pp. 203-210. ISSN 1938-7228.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We propose a new approach for learning a sparse graphical model approximation to a specified multivariate probability distribution (such as the empirical distribution of sample data). The selection of sparse graph structure arises naturally in our approach through solution of a convex optimization problem, which differentiates our method from standard combinatorial approaches. We seek the maximum entropy relaxation (MER) within an exponential family, which maximizes entropy subject to constraints that marginal distributions on small subsets of variables are close to the prescribed marginals in relative entropy. To solve MER, we present a modified primal-dual interior point method that exploits sparsity of the Fisher information matrix in models defined on chordal graphs. This leads to a tractable, scalable approach provided the level of relaxation in MER is sufficient to obtain a thin graph. The merits of our approach are investigated by recovering the structure of some simple graphical models from sample data.

Item Type:Article
Related URLs:
URLURL TypeDescription
Record Number:CaltechAUTHORS:20121009-082035601
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34771
Deposited By: Tony Diaz
Deposited On:09 Oct 2012 18:46
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page