Gauges, Loops, and Polynomials for Partition Functions of Graphical Models
Graphical models represent multivariate and generally not normalized probability distributions. Computing the normalization factor, called the partition function, is the main inference challenge relevant to multiple statistical and optimization applications. The problem is of an exponential complexity with respect to the number of variables. In this manuscript, aimed at approximating the PF, we consider Multi-Graph Models where binary variables and multivariable factors are associated with edges and nodes, respectively, of an undirected multi-graph. We suggest a new methodology for analysis and computations that combines the Gauge Function technique with the technique from the field of real stable polynomials. We show that the Gauge Function has a natural polynomial representation in terms of gauges/variables associated with edges of the multi-graph. Moreover, it can be used to recover the Partition Function through a sequence of transformations allowing appealing algebraic and graphical interpretations. Algebraically, one step in the sequence consists in application of a differential operator over gauges associated with an edge. Graphically, the sequence is interpreted as a repetitive elimination of edges resulting in a sequence of models on decreasing in size graphs with the same Partition Function. Even though complexity of computing factors in the sequence models grow exponentially with the number of eliminated edges, polynomials associated with the new factors remain bi-stable if the original factors have this property. Moreover, we show that Belief Propagation estimations in the sequence do not decrease, each low-bounding the Partition Function.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Belief Propagation, Bethe Approximation and Polynomials
Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partit…
The Bethe Partition Function of Log-supermodular Graphical Models
Sudderth, Wainwright, and Willsky conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound o…
Belief propagation for networks with loops
Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortco…
Approximating Partition Functions in Constant Time
We study approximations of the partition function of dense graphical models. Partition functions of graphical models play a fundamental role is statistical physics, in statistics and in machine learning. Two of the main …
Majorization for CRFs and Latent Likelihoods
The partition function plays a key role in probabilistic modeling including conditional random fields, graphical models, and maximum likelihood estimation. To optimize partition functions, this article introduces a quadr…