Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Value Elimination: Bayesian Inference via Backtracking Search
Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi
Abstract:
Backtracking search is a powerful algorithmic paradigm that can be used to solve many problems. It is in a certain sense the dual of variable elimination; but on many problems, e.g., SAT, it is vastly superior to variable elimination in practice. Motivated by this we investigate the application of backtracking search to the problem of Bayesian inference (Bayes). We show that natural generalizations of known techniques allow backtracking search to achieve performance guarantees similar to standard algorithms for Bayes, and that there exist problems on which backtracking can in fact do much better. We also demonstrate that these ideas can be applied to implement a Bayesian inference engine whose performance is competitive with standard algorithms. Since backtracking search can very naturally take advantage of context specific structure, the potential exists for performance superior to standard algorithms on many problems
Keywords:
Pages: 20-28
PS Link:
PDF Link: /papers/03/p20-bacchus.pdf
BibTex:
@INPROCEEDINGS{Bacchus03,
AUTHOR = "Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi",
TITLE = "Value Elimination: Bayesian Inference via Backtracking Search",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "20--28"
}


hosted by DSL   •   site info   •   help