R240
Sampling over Search Trees Using Abstractions
Rina Dechter, Filjor Broka, Kalev Kask, and Alexander Ihler.

Abstract
We present a new sampling scheme for approximating hard to compute summation queries over graphical models (e.g., partition function). The scheme builds upon exact algorithms that traverse a weighted directed state-space tree representing a global probability function over a graphical model. With the aid of an abstraction function and randomization, the state space can be compacted to facilitate tractable computation, yielding a Monte Carlo Estimate that is unbiased.

[pdf]