Teoretyczne gwarancje dla czasów działania metod propagowania przekonań?

14

Wykazano, że propagacja przekonań jest bardzo skuteczną metodą dzięki badaniom w probabilistycznych modelach graficznych.

Jednak nie wiem nic o BP, które byłoby porównywalne z metodami MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z # P-zupełnością.

Czy ktoś mógłby wskazać mi jakieś odniesienia?

cc.complexity-theory reference-request graph-algorithms machine-learning st.statistics Tianyang Li
źródło
2
Wersje propagacji przekonań pojawiają się w kodach ekspanderów oraz w widmowej technice Alon & Kahale A do barwienia losowych trójkolorowych grafów (a także wielu późniejszych prac wykorzystujących ich pomysły). Chociaż w pewnym stopniu odpowiada to na Twój tytuł, nie odpowiada na treść twojego pytania.
Yuval Filmus,
2
BTW, nie dostałem twojego ostatniego zdania. Co przez to rozumiesz? „Metody MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z P-zupełnym zakończeniem.” Jakieś wskazówki?
Daniel
@Daniel Szukałem rozwiązywania problemów za pomocą BP, które mają dobre teoretyczne gwarancje czasu pracy.
Tianyang Li
Więc myślę, że musisz zmienić opis swojego problemu. Zrozumiałem inną rzecz.
Daniel

Odpowiedzi:

12

Udowodniono, że BP i większość jego wariantów zbiegają się na wykresach bez cykli. Kiedy masz cykle, czasami wykazują bardzo dziwne zachowanie. W tych przypadkach ludzie próbowali różnych schematów przybliżenia, na przykład Sherali-Adams, Lov? Asz-Schrijver i Lasserre Hierarchies.

Wyczerpujący przegląd tych przybliżeń znajduje się w [1]. Również (Wainwright i Jordan, 2008) obejmuje inną klasę przybliżeń.

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

Daniel
źródło
3
Dlatego też propagacja badań (kuzyn propagacji przekonań) działa tak dobrze w rozwiązywaniu dużych losowych problemów 3-SAT. W przypadku losowych wykresów czynnikowych, lokalnie wykres wygląda jak drzewo, więc rozpowszechnianie ankiet może robić postępy.
user834
5

Oto artykuł, w którym autorzy wykorzystali BP do uzyskania w pełni wielomianowego losowego schematu aproksymacji dla problemu pojemnościowego minimalnego kosztu przepływu sieci.

Tianyang Li
źródło