Graphical Models, Exponential Families, and Variational InferenceThe formalism of probabilistic graphical models provides a unifying framework for capturing complex dependencies among random variables, and building large-scale multivariate statistical models. Graphical models have become a focus of research in many statistical, computational and mathematical fields, including bioinformatics, communication theory, statistical physics, combinatorial optimization, signal and image processing, information retrieval and statistical machine learning. Many problems that arise in specific instances-including the key problems of computing marginals and modes of probability distributions-are best studied in the general setting. Working with exponential family representations, and exploiting the conjugate duality between the cumulant function and the entropy for exponential families, Graphical Models, Exponential Families and Variational Inference develops general variational representations of the problems of computing likelihoods, marginal probabilities and most probable configurations. It describes how a wide variety of algorithms- among them sum-product, cluster variational methods, expectation-propagation, mean field methods, and max-product-can all be understood in terms of exact or approximate forms of these variational representations. The variational approach provides a complementary alternative to Markov chain Monte Carlo as a general source of approximation methods for inference in large-scale statistical models. |
Contents
Introduction | 1 |
Graphical Models as Exponential Families | 35 |
SumProduct Bethe Kikuchi | 73 |
Mean Field Methods | 125 |
Variational Methods in Parameter Estimation | 147 |
Convex Relaxations and Upper Bounds | 165 |
Integer Programming Maxproduct and Linear | 195 |
Moment Matrices Semidefinite Constraints | 235 |
Discussion | 257 |
A Background Material | 263 |
Exponential Families | 271 |
Proof of Theorem 4 2b | 277 |
Clustering and Augmented Hypergraphs | 285 |
Common terms and phrases
associated belief propagation binary canonical parameters cliques codeword computing condition consider constraint set convergence convex combination convex function convex set corresponding cumulant function defined denote density discussed dual function edge entropy approximation Equation equivalent exact Example expectation-propagation exponential family extreme points factor graph first-order LP relaxation fixed point given graph G graph with cycles graphical models hyperedge hypergraph hypertree illustrated indicator functions inequality inference Ising model junction tree algorithm Lagrangian likelihood linear programming lower bound LP relaxation Markov random field matrix maximal mean field methods mean parameters message-passing naive mean field nodes optimization problem outer bound overcomplete pairwise parameterization parity check particular Proposition pseudomarginals random variables random vector representation reweighted Section singleton specified subset sufficient statistics sum-product algorithm surrogate tion tractable tree-reweighted tree-structured treewidth undirected updates variational methods variational principle vertex