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 = {Frederik Eaton and Zoubin Ghahramani}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {145--152}, year = {2009}, editor = {David van Dyk and Max Welling}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 145--152 %U http://proceedings.mlr.press %V 5 %W PMLR %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 PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-eaton09a PB - PMLR SP - 145 DP - PMLR EP - 152 L1 - http://proceedings.mlr.press/v5/eaton09a/eaton09a.pdf UR - http://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 PMLR 5:145-152

Related Material