Synthesis of MCMC and Belief Propagation
Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus approach which allows to express the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we first propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.
This article deals with the computation of the partition function (or normalization constant) of graphical models involving discrete variables. The approach used here is based on first, an estimation of the BP partition function (or Bethe-Peierls), which is corrected by a loop-series expansion on the considered system. The main focus of this paper is to design first, an algorithmic method computing the 2-regular generalized loops term of the expansion (which is an approximation of the true loop expansion in most cases) and converging in polynomial time. Second, they extend their algorithm in order to compute the whole loop expansion by a similar algorithm but, in this case, without providing theoretical guarantee.  Finally, their second algorithm is tested on the K_4 graph (a clique of four nodes) and compared to a MCMC estimation and a BP estimation of the log of the partition function for many different types of systems : ferromagnet, antiferromagnet and disordered (random) interactions. 
 The authors develop an very interesting method to the hard problem of computing the partition function of GM. In particular, there is no method to compute Z for general graphs accurately and log(Z) is a particularly interesting component in many fields: it is related to the likelihood in Machine Learning, it gives all the statistical information of a system in statistical mechanic, ... I think therefore that any effort toward that direction is an important contribution.  Concerning the work presented here, I have some questions and concerns that I would like the authors to answer:  1) the authors mentioned that BP in general fail to converge on general graph but that more involved convergent alternative exists. I think the author should be more specific, precising if all the convergent algorithms do provide the same estimation of the BP partition function and it they are indeed linear in the system size.  2) I guess that, in line 101/102, the Ising model means the 2D Ising model ?  3) I have some concern about the estimation of the full loop expansion. The 2-reg loop can be proven to converge in polynomial time but the full loop does not have these garranty. Can the author provide at least some empirical estimation of the convergence time for some systems or at least some arguments why this method will not suffer from exponential slowing down when using it on a large system ?  4) Concerning the experimental results:  * it is not specified the number of systems at different temperature that were used for the estimation of the loop series. * it is not clear to me what is the MCMC estimation of log(Z), is it the estimation obtained by integrating the average energy function over \beta ? I guess not, but I think that the authors should specify how they estimate log(Z) using MCMC. * if the estimation of MCMC is not obtained by integrating over many \beta, I would like to know why it is faster to compute Z_2-loop using many different \beta instead of integrating the average energy function over many \beta ?   Finally, maybe the most important point to me that would justify the whole method. The experiments are done over very small systems (4 nodes). I agree with the authors about the importance of being able to compute the true Z, but it is possible with a modest computer to reach systems with at least 20/25 nodes. Therefore I don't understand the choice of the author nor can I be sure that their method work at larger sizes. I therefore strongly advice the author to explain why such a choice. They might want as well to provide some test on larger systems comparing some estimation obtained by integration with MCMC with their method.