New Understanding of the Bethe Approximation and the Replica Method
arXiv:1303.2168
Abstract
In this thesis, new generalizations of the Bethe approximation and new understanding of the replica method are proposed. The Bethe approximation is an efficient approximation for graphical models, which gives an asymptotically accurate estimate of the partition function for many graphical models. The Bethe approximation explains the well-known message passing algorithm, belief propagation, which is exact for tree graphical models. It is also known that the cluster variational method gives the generalized Bethe approximation, called the Kikuchi approximation, yielding the generalized belief propagation. In the thesis, a new series of generalization of the Bethe approximation is proposed, which is named the asymptotic Bethe approximation. The asymptotic Bethe approximation is derived from the characterization of the Bethe free energy using graph covers, which was recently obtained by Vontobel. The asymptotic Bethe approximation can be expressed in terms of the edge zeta function by using Watanabe and Fukumizu's result about the Hessian of the Bethe entropy. The asymptotic Bethe approximation is confirmed to be better than the conventional Bethe approximation on some conditions. For this purpose, Chertkov and Chernyak's loop calculus formula is employed, which shows that the error of the Bethe approximation can be expressed as a sum of weights corresponding to generalized loops, and generalized for non-binary finite alphabets by using concepts of information geometry.
Doctoral thesis
References in corpus (22)
- The large deviation approach to statistical mechanics
- Ising models on locally tree-like graphs
- Sufficient conditions for convergence of the Sum-Product Algorithm
- Loop series for discrete statistical models on graphs
- Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- The glassy phase of Gallager codes
- Exact solutions for diluted spin glasses and optimization problems
- Loop Calculus in Statistical Physics and Information Science
- Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
- Normal Factor Graphs and Holographic Transformations
- The Bethe Partition Function of Log-supermodular Graphical Models
- Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
- Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
- Partition function loop series for a general graphical model: free energy corrections and message-passing equations
- A frozen glass phase in the multi-index matching problem
- Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
- Partition Function Expansion on Region-Graphs and Message-Passing Equations
- New Generalizations of the Bethe Approximation via Asymptotic Expansion
- Statistical Mechanical Analysis of Low-Density Parity-Check Codes on General Markov Channel
- Effects of Single-Cycle Structure on Iterative Decoding for Low-Density Parity-Check Codes
- A conjecture on independent sets and graph covers