|Publications & Technical Reports|
Cutset Sampling with Likelihood WeightingBozhena Bidyuk and Rina Dechter
The paper extends the principle of cutset sampling over Bayesian networks, presented previously for Gibbs sampling, to likelihood weighting (LW). Cutset sampling is motivated by the Rao-Blackwell theorem which implies that sampling over a subset of variables requires fewer samples for convergence due to the reduction in sampling variance. The scheme exploits the network structure in selecting cutsets that allow efficient computation of the sampling distributions. In particular, as we show empirically, likelihood weighting over a loop-cutset (abbreviated LWLC), is time-wise cost-effective. We also provide an effective way for caching the probabilities of the generated samples which improves the performance of the overall scheme. We compare LWLC against regular liklihood-weighting and against Gibbsbased cutset sampling.