Computer Science – Artificial Intelligence
Scientific paper
2011-09-08
Computer Science
Artificial Intelligence
Scientific paper
This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the sum-product Belief Propagation (BP) algorithm of artificial intelligence. The Bethe approximation reduces the problem of computing the partition function in a graphical model to that of solving a set of non-linear equations, so-called the Bethe equation. On the other hand, the BP algorithm is a popular heuristic method for estimating marginal distributions in a graphical model. Although they are inspired and developed from different directions, Yedidia, Freeman and Weiss (2004) established a close connection: the BP algorithm solves the Bethe equation if it converges (however, it often does not). This naturally motivates the following important question to understand their limitations and empirical successes: the Bethe equation is computationally easy to solve? We present a message passing algorithm solving the Bethe equation in polynomial number of operations for arbitrary binary graphical models of n variables where the maximum degree in the underlying graph is O(log n). Our algorithm, an alternative to BP fixing its convergence issue, is the first fully polynomial-time approximation scheme for the BP fixed point computation in such a large class of graphical models, while the approximate fixed point computation is known to be (PPAD-)hard in general. We believe that our technique is of broader interest to understand the computational complexity of the cavity method in statistical physics.
No associations
LandOfFree
The Complexity of Approximating a Bethe Equilibrium does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Approximating a Bethe Equilibrium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Approximating a Bethe Equilibrium will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-475301