Choosing a Variable to Clamp

Frederik Eaton, Zoubin Ghahramani
Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:145-152, 2009.

Abstract

In this paper we propose an algorithm for approximate inference on graphical models based on belief propagation (BP). Our algorithm is an approximate version of Cutset Conditioning, in which a set of variables is instantiated to make the rest of the graph singly connected. We relax the constraint of single-connectedness, and select variables one at a time for conditioning, running belief propagation after each selection. We consider the problem of determining the best variable to clamp at each level of recursion, and propose a fast heuristic which applies backpropagation to the BP updates. We demonstrate that the heuristic performs better than selecting variables at random, and give experimental results which show that it performs competitively with existing approximate inference algorithms.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-eaton09a, title = {Choosing a Variable to Clamp}, author = {Eaton, Frederik and Ghahramani, Zoubin}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {145--152}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/eaton09a/eaton09a.pdf}, url = {https://proceedings.mlr.press/v5/eaton09a.html}, abstract = {In this paper we propose an algorithm for approximate inference on graphical models based on belief propagation (BP). Our algorithm is an approximate version of Cutset Conditioning, in which a set of variables is instantiated to make the rest of the graph singly connected. We relax the constraint of single-connectedness, and select variables one at a time for conditioning, running belief propagation after each selection. We consider the problem of determining the best variable to clamp at each level of recursion, and propose a fast heuristic which applies backpropagation to the BP updates. We demonstrate that the heuristic performs better than selecting variables at random, and give experimental results which show that it performs competitively with existing approximate inference algorithms.} }
Endnote
%0 Conference Paper %T Choosing a Variable to Clamp %A Frederik Eaton %A Zoubin Ghahramani %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-eaton09a %I PMLR %P 145--152 %U https://proceedings.mlr.press/v5/eaton09a.html %V 5 %X In this paper we propose an algorithm for approximate inference on graphical models based on belief propagation (BP). Our algorithm is an approximate version of Cutset Conditioning, in which a set of variables is instantiated to make the rest of the graph singly connected. We relax the constraint of single-connectedness, and select variables one at a time for conditioning, running belief propagation after each selection. We consider the problem of determining the best variable to clamp at each level of recursion, and propose a fast heuristic which applies backpropagation to the BP updates. We demonstrate that the heuristic performs better than selecting variables at random, and give experimental results which show that it performs competitively with existing approximate inference algorithms.
RIS
TY - CPAPER TI - Choosing a Variable to Clamp AU - Frederik Eaton AU - Zoubin Ghahramani BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-eaton09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 145 EP - 152 L1 - http://proceedings.mlr.press/v5/eaton09a/eaton09a.pdf UR - https://proceedings.mlr.press/v5/eaton09a.html AB - In this paper we propose an algorithm for approximate inference on graphical models based on belief propagation (BP). Our algorithm is an approximate version of Cutset Conditioning, in which a set of variables is instantiated to make the rest of the graph singly connected. We relax the constraint of single-connectedness, and select variables one at a time for conditioning, running belief propagation after each selection. We consider the problem of determining the best variable to clamp at each level of recursion, and propose a fast heuristic which applies backpropagation to the BP updates. We demonstrate that the heuristic performs better than selecting variables at random, and give experimental results which show that it performs competitively with existing approximate inference algorithms. ER -
APA
Eaton, F. & Ghahramani, Z.. (2009). Choosing a Variable to Clamp. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:145-152 Available from https://proceedings.mlr.press/v5/eaton09a.html.

Related Material