Convex Surrogates and Stable Message-passing in Markov Random Fields: Combined Approximation of Marginals and Parameters

• Activity Number: 38
• Type: Invited
• Date/Time: Sunday, August 7, 2005 : 4:00 PM to 5:50 PM
• Sponsor: IMS
• Author(s): Martin J. Wainwright*+
• Companies: University of California, Berkeley
• Keywords: graphical models ; Markov random fields ; approximate computation ; parameter estimation ; model selection ; relaxation

Abstract

Key statistical problems that arise in applications of Markov random fields (MRFs) are computing local marginal distributions and estimating model parameters from data. Although easily solved for trees, these problems are intractable for general MRFs, which motivates the use of approximate methods. We discuss a class of variational methods, based on convex relaxations of the exact variational principle for exponential family MRFs, that yield deterministic approximations to marginals and parameter estimates. We show how the underlying convexity of the formulations lead to important advantages over traditional nonconvex methods. We consider an M-estimator based on a convex surrogate to the cumulate generating function and show that it is asymptotically Gaussian but also \emph{inconsistent}. Nonetheless, we demonstrate that such inconsistency is useful for joint estimation and prediction; in particular, we provide theoretical bounds on the performance loss of our computationally tractable method relative to the unattainable Bayes optimum.