14
$\begingroup$

Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.

However, I don't know anything about BP that's comparable to MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems.

Could someone point me to some references?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Versions of belief propagation appear in expander codes and in Alon & Kahale's A spectral technique for coloring random 3-colorable graphs (as well as numerous later papers exploiting their ideas). While that answers your title to some extent, it doesn't answer the body of your question. $\endgroup$
    – Yuval Filmus
    Commented Nov 2, 2013 at 7:18
  • 2
    $\begingroup$ BTW, I didn't get your last sentence. What do you mean by this? "MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems." Any pointers? $\endgroup$
    – Daniel
    Commented Nov 3, 2013 at 21:24
  • $\begingroup$ @Daniel I was looking for solving problems using BP where they have good theoretical guarantees for running time. $\endgroup$
    – Tianyang Li
    Commented Nov 4, 2013 at 17:24
  • $\begingroup$ Then I guess you need to change the statement of your problem. I understood different thing. $\endgroup$
    – Daniel
    Commented Nov 5, 2013 at 0:55

2 Answers 2

Reset to default
12
$\begingroup$

BP and most of its variants are proved to converge on graphs without cycles. When you have cycles they show very strange behavior sometimes. For these cases people have tried different approximations schemes, for example Sherali-Adams, Lovasz-Schrijver, and Lasserre Hierarchies.

See [1] for a comprehensive review of these approximations. Also (Wainwright and Jordan, 2008) includes other class of approximations.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This is also why survey propagation (a cousin of belief propagation) works so well on solving large random 3-SAT problems. For random factor graphs, locally, the graph looks like it's a tree and so survey propagation can make progress. $\endgroup$
    – user834
    Commented Nov 4, 2013 at 16:51
5
$\begingroup$

Here's a paper where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network flow problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.