Theoretische Garantien für Laufzeiten von Glaubensvermittlungsmethoden?

14

Durch die Erforschung probabilistischer grafischer Modelle hat sich die Glaubensausbreitung als sehr leistungsfähige Methode erwiesen.

Ich weiß jedoch nichts über BP, das mit MCMC-Methoden vergleichbar ist, bei denen wir für # P-vollständige Probleme vollständig polynomielle randomisierte Approximationsschemata (FPRAS) haben können.

Könnte mich jemand auf einige Referenzen hinweisen?

cc.complexity-theory reference-request graph-algorithms machine-learning st.statistics Tianyang Li
quelle
2
Versionen der Glaubensausbreitung erscheinen in Expander-Codes und in Alon & Kahales A-Spektraltechnik zum Färben von zufälligen 3-farbigen Graphen (sowie in zahlreichen späteren Arbeiten, die ihre Ideen ausnutzen). Während dies in gewissem Maße Ihren Titel beantwortet, beantwortet es nicht den Hauptteil Ihrer Frage.
Yuval Filmus
2
Übrigens, ich habe deinen letzten Satz nicht bekommen. Was meinst du damit? "MCMC-Methoden, bei denen wir vollständig polynomielle randomisierte Approximationsschemata (FPRAS) für # P-vollständige Probleme haben können." Irgendwelche Hinweise?
Daniel
@ Daniel Ich war auf der Suche nach Lösungen für Probleme mit BP, bei denen gute theoretische Garantien für die Laufzeit bestehen.
Tianyang Li
Dann müssen Sie wohl die Aussage Ihres Problems ändern. Ich habe etwas anderes verstanden.
Daniel

Antworten:

12

BP und die meisten seiner Varianten konvergieren nachweislich in Diagrammen ohne Zyklen. Wenn Sie Zyklen haben, zeigen sie manchmal sehr merkwürdiges Verhalten. In diesen Fällen haben die Leute verschiedene Approximationsschemata ausprobiert, zum Beispiel Sherali-Adams, Lovász-Schrijver und Lasserre Hierarchies.

Siehe [1] für einen umfassenden Überblick über diese Annäherungen. Auch (Wainwright and Jordan, 2008) enthält andere Klassen von Annäherungen.

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

Daniel
quelle
3
Dies ist auch der Grund, warum die Umfrageweitergabe (ein Cousin der Glaubensweitergabe) bei der Lösung großer zufälliger 3-SAT-Probleme so gut funktioniert. Bei Zufallsfaktordiagrammen sieht das Diagramm lokal wie ein Baum aus, sodass die Umfrageausbreitung Fortschritte machen kann.
User834
5

Hier ist ein Papier , wo die Autoren verwendeten BP ein voll polynomialzeit-randomisierte Approximationsschema für die das kapazitierten Mindest-Cost - Netzwerk fl ow Problem zu erhalten.

Tianyang Li
quelle