Randomized Algorithms for the Loop Cutset Problem
Abstract
We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inference. Our randomized algorithm for finding a loop cutset outputs a minimum loop cutset after O(c 6kkn) steps with probability at least 1 - (1 - 1/6k)c6k, where c > 1 is a constant specified by the user, k is the minimal size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm often finds a loop cutset that is closer to the minimum weight loop cutset than the ones found by the best deterministic algorithms known.
Cite
Text
Becker et al. "Randomized Algorithms for the Loop Cutset Problem." Journal of Artificial Intelligence Research, 2000. doi:10.1613/JAIR.638Markdown
[Becker et al. "Randomized Algorithms for the Loop Cutset Problem." Journal of Artificial Intelligence Research, 2000.](https://mlanthology.org/jair/2000/becker2000jair-randomized/) doi:10.1613/JAIR.638BibTeX
@article{becker2000jair-randomized,
title = {{Randomized Algorithms for the Loop Cutset Problem}},
author = {Becker, Ann and Bar-Yehuda, Reuven and Geiger, Dan},
journal = {Journal of Artificial Intelligence Research},
year = {2000},
pages = {219-234},
doi = {10.1613/JAIR.638},
volume = {12},
url = {https://mlanthology.org/jair/2000/becker2000jair-randomized/}
}