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

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?

— Tianyang Li
źródło

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,

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:

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

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

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