Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Random Algorithms for the Loop Cutset Problem
Ann Becker, Reuven Bar-Yehuada, Dan Geiger
Abstract:
We show how to find a minimum loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in Pearl's method of conditioning for inference. Our random algorithm for finding a loop cutset, called ``Repeated WGuessI", outputs a minimum loop cutset, after O(c 6^k k n) steps, with probability at least 1-(1 over{6^k})^{c 6^k}), where c>1 is a constant specified by the user, k is the size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm, called WRA, often finds a loop cutset that is closer to the minimum loop cutset than the ones found by the best deterministic algorithms known.
Keywords:
Pages: 49-56
PS Link:
PDF Link: /papers/99/p49-becker.pdf
BibTex:
@INPROCEEDINGS{Becker99,
AUTHOR = "Ann Becker and Reuven Bar-Yehuada and Dan Geiger",
TITLE = "Random Algorithms for the Loop Cutset Problem",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "49--56"
}


hosted by DSL   •   site info   •   help