The Complexity of Approximating a Bethe Equilibrium

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 322
  • Download : 0
This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the belief propagation (BP) algorithm of artificial intelligence. The Bethe approximation and the BP algorithm are heuristic methods for estimating the partition function and marginal probabilities in graphical models, respectively. The computational complexity of the Bethe approximation is decided by the number of operations required to solve a set of nonlinear equations, the so-called Bethe equation. Although the BP algorithm was inspired and developed independently, Yedidia, Freeman, and Weiss showed that the BP algorithm solves the Bethe equation if it converges (however, it often does not). This naturally motivates the following question to understand limitations and empirical successes of the Bethe and BP methods: is the Bethe equation computationally easy to solve? We present a message-passing algorithm solving the Bethe equation in a polynomial number of operations for general binary graphical models of n variables, where the maximum degree in the underlying graph is O(log n). Equivalently, it finds a stationary point of the Bethe free energy function. Our algorithm can be used as an alternative to BP fixing its convergence issue and is the first fully polynomial-time approximation scheme for the BP fixed-point computation in such a large class of graphical models, whereas the approximate fixed-point computation is known to be polynomial parity arguments on directed graphs (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.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2014-07
Language
English
Article Type
Article
Keywords

LOOPY BELIEF PROPAGATION; ALGORITHMS; MODELS

Citation

IEEE TRANSACTIONS ON INFORMATION THEORY, v.60, no.7, pp.3959 - 3969

ISSN
0018-9448
DOI
10.1109/TIT.2014.2317487
URI
http://hdl.handle.net/10203/191187
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0