Survey Propagation beyond Constraint Satisfaction Problems

Christopher Srinivasa, Siamak Ravanbakhsh, Brendan Frey
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:286-295, 2016.

Abstract

Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assumptions do not hold. For this, SP messages represent distributions over BP messages. Unfortunately this requirement makes SP intractable beyond constraint satisfaction problems because, to perform general SP updates, one has to operate on distributions over a continuous domain. We propose an approximation scheme to efficiently extend the application of SP to marginalization in binary pairwise graphical models. Our approximate SP has O(DK\log(DK)t) complexity per iteration, where t is the complexity of BP per iteration, D is the maximum node degree and K is a resolution constant controlling the approximation’s fidelity. Our experiments show that this method can track many BP fixed points, achieving a high marginalization accuracy within a few iterations, in difficult settings where BP is often non-convergent and inaccurate.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-srinivasa16, title = {Survey Propagation beyond Constraint Satisfaction Problems}, author = {Srinivasa, Christopher and Ravanbakhsh, Siamak and Frey, Brendan}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {286--295}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/srinivasa16.pdf}, url = {https://proceedings.mlr.press/v51/srinivasa16.html}, abstract = {Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assumptions do not hold. For this, SP messages represent distributions over BP messages. Unfortunately this requirement makes SP intractable beyond constraint satisfaction problems because, to perform general SP updates, one has to operate on distributions over a continuous domain. We propose an approximation scheme to efficiently extend the application of SP to marginalization in binary pairwise graphical models. Our approximate SP has O(DK\log(DK)t) complexity per iteration, where t is the complexity of BP per iteration, D is the maximum node degree and K is a resolution constant controlling the approximation’s fidelity. Our experiments show that this method can track many BP fixed points, achieving a high marginalization accuracy within a few iterations, in difficult settings where BP is often non-convergent and inaccurate.} }
Endnote
%0 Conference Paper %T Survey Propagation beyond Constraint Satisfaction Problems %A Christopher Srinivasa %A Siamak Ravanbakhsh %A Brendan Frey %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-srinivasa16 %I PMLR %P 286--295 %U https://proceedings.mlr.press/v51/srinivasa16.html %V 51 %X Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assumptions do not hold. For this, SP messages represent distributions over BP messages. Unfortunately this requirement makes SP intractable beyond constraint satisfaction problems because, to perform general SP updates, one has to operate on distributions over a continuous domain. We propose an approximation scheme to efficiently extend the application of SP to marginalization in binary pairwise graphical models. Our approximate SP has O(DK\log(DK)t) complexity per iteration, where t is the complexity of BP per iteration, D is the maximum node degree and K is a resolution constant controlling the approximation’s fidelity. Our experiments show that this method can track many BP fixed points, achieving a high marginalization accuracy within a few iterations, in difficult settings where BP is often non-convergent and inaccurate.
RIS
TY - CPAPER TI - Survey Propagation beyond Constraint Satisfaction Problems AU - Christopher Srinivasa AU - Siamak Ravanbakhsh AU - Brendan Frey BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-srinivasa16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 286 EP - 295 L1 - http://proceedings.mlr.press/v51/srinivasa16.pdf UR - https://proceedings.mlr.press/v51/srinivasa16.html AB - Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assumptions do not hold. For this, SP messages represent distributions over BP messages. Unfortunately this requirement makes SP intractable beyond constraint satisfaction problems because, to perform general SP updates, one has to operate on distributions over a continuous domain. We propose an approximation scheme to efficiently extend the application of SP to marginalization in binary pairwise graphical models. Our approximate SP has O(DK\log(DK)t) complexity per iteration, where t is the complexity of BP per iteration, D is the maximum node degree and K is a resolution constant controlling the approximation’s fidelity. Our experiments show that this method can track many BP fixed points, achieving a high marginalization accuracy within a few iterations, in difficult settings where BP is often non-convergent and inaccurate. ER -
APA
Srinivasa, C., Ravanbakhsh, S. & Frey, B.. (2016). Survey Propagation beyond Constraint Satisfaction Problems. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:286-295 Available from https://proceedings.mlr.press/v51/srinivasa16.html.

Related Material