Dechter, R.


Cutset Sampling for Bayesian Networks

arXiv.org Artificial Intelligence

The paper presents a new sampling methodology for Bayesian networks that samples only a subset of variables and applies exact inference to the rest. Cutset sampling is a network structure-exploiting application of the Rao-Blackwellisation principle to sampling in Bayesian networks. It improves convergence by exploiting memory-based inference algorithms. It can also be viewed as an anytime approximation of the exact cutset-conditioning algorithm developed by Pearl. Cutset sampling can be implemented efficiently when the sampled variables constitute a loop-cutset of the Bayesian network and, more generally, when the induced width of the networks graph conditioned on the observed sampled variables is bounded by a constant w. We demonstrate empirically the benefit of this scheme on a range of benchmarks.


Constraint networks

Classics

See also:Rina Dechter, Itay Meiri, Judea Pearl, Temporal constraint networks, Artificial Intelligence, Volume 49, Issues 1–3, May 1991, Pages 61-95.Rina Dechter, Judea Pearl, Tree clustering for constraint networks, Artificial Intelligence, Volume 38, Issue 3, April 1989, Pages 353-366.Rina Dechter and Avi Dechter. Belief Maintenance in Dynamic Constraint Networks. In Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88), St. Paul, MN, August 1988, pp. 37-42.Peter van Beek and Rina Dechter. 1995. On the minimality and global consistency of row-convex constraint networks. J. ACM 42, 3 (May 1995), 543-561.Eddie Schwalb, Rina Dechter, Processing disjunctions in temporal constraint networks, Artificial Intelligence, Volume 93, Issues 1–2, June 1997, Pages 29-61.Rina Dechrer and Judea Pearl. Directed Constraint Networks: A Relational Framework for Causal Modeling. UCLA Computer Science Department Technical Report CSD-910023, July 1991.Avi Dechter, Rina Dechter. Removing Redundancies in Constraint Networks. AAAI-87.Robert Mateescu, Rina Dechter. Compiling Constraint Networks into AND/OR Multi-valued Decision Diagrams (AOMDDs). In Principles and Practice of Constraint Programming - CP 2006 Lecture Notes in Computer Science Volume 4204, 2006, pp 329-343.Itay Meiri, Rina Dechter, Judea Pearl, Uncovering trees in constraint networks, Artificial Intelligence, Volume 86, Issue 2, October 1996, Pages 245-267.In Shapiro, S. (Ed.), Encyclopedia of Artificial Intelligence., pp. 276-285. Wiley and Sons