Garanties théoriques pour les temps d'exécution des méthodes de propagation des croyances?

14

La propagation de la croyance s'est avérée être une méthode très puissante grâce à la recherche de modèles graphiques probabilistes.

Cependant, je ne connais rien de BP comparable aux méthodes MCMC où nous pouvons avoir des schémas d'approximation randomisés entièrement polynomiaux (FPRAS) pour les problèmes # P-complets.

Quelqu'un pourrait-il m'indiquer quelques références?

cc.complexity-theory reference-request graph-algorithms machine-learning st.statistics Tianyang Li
la source
2
Des versions de la propagation des croyances apparaissent dans les codes d'expansion et dans la technique spectrale A d' Alon & Kahale pour colorer des graphiques aléatoires à 3 couleurs (ainsi que de nombreux articles ultérieurs exploitant leurs idées). Bien que cela réponde dans une certaine mesure à votre titre, cela ne répond pas au corps de votre question.
Yuval Filmus
2
BTW, je n'ai pas eu ta dernière phrase. Que veux-tu dire par là? "Méthodes MCMC où nous pouvons avoir des schémas d'approximation entièrement polynomiaux randomisés (FPRAS) pour les problèmes # P-complets." Des pointeurs?
Daniel
@Daniel Je cherchais à résoudre des problèmes en utilisant BP où ils ont de bonnes garanties théoriques pour le temps de fonctionnement.
Tianyang Li
Ensuite, je suppose que vous devez modifier l'énoncé de votre problème. J'ai compris autre chose.
Daniel

Réponses:

12

Il est prouvé que BP et la plupart de ses variantes convergent sur des graphiques sans cycles. Lorsque vous avez des cycles, ils présentent parfois un comportement très étrange. Pour ces cas, les gens ont essayé différents schémas d'approximations, par exemple les hiérarchies Sherali-Adams, Lov? Asz-Schrijver et Lasserre.

Voir [1] pour un examen complet de ces approximations. Également (Wainwright et Jordan, 2008) inclut d'autres classes d'approximations.

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

Daniel
la source
3
C'est aussi pourquoi la propagation de l'enquête (un cousin de la propagation des croyances) fonctionne si bien pour résoudre de gros problèmes aléatoires 3-SAT. Pour les graphiques à facteurs aléatoires, localement, le graphique ressemble à un arbre et la propagation de l'enquête peut donc progresser.
user834
5

Voici un article dans lequel les auteurs ont utilisé BP pour obtenir un schéma d'approximation randomisée en temps polynomial complet pour le problème de débit de réseau à coût minimum capacitif.

Tianyang Li
la source