Было доказано, что распространение убеждений является очень мощным методом исследования вероятностных графических моделей.
Однако я ничего не знаю о BP, сравнимом с методами MCMC, где у нас могут быть полностью полиномиальные схемы рандомизированной аппроксимации (FPRAS) для # P-полных задач.
Может ли кто-нибудь указать мне на некоторые ссылки?
Ответы:
Доказано, что BP и большинство его вариантов сходятся на графах без циклов. Когда у вас есть циклы, они иногда показывают очень странное поведение. В этих случаях люди пробовали схемы различных аппроксимаций, например иерархии Шерали-Адамса, Ловеша-Шрайвера и Лассерра.
См. [1] для всестороннего обзора этих приближений. Также (Wainwright and Jordan, 2008) включает в себя другой класс приближений.
[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf
источник
Вот статья, где авторы использовали BP, чтобы получить полностью рандомизированную схему аппроксимации за полиномиальное время для задачи обтекаемой сети с минимальными затратами.
источник