Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2007 | Submitted
Journal Article Open

Learning Markov Structure by Maximum Entropy Relaxation

Abstract

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.

Attached Files

Submitted - jcw_mer_aistats07.pdf

Files

jcw_mer_aistats07.pdf
Files (315.0 kB)
Name Size Download all
md5:abe0a2547ed4b306de5ba95975a47475
315.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 19, 2023