Value Elimination: Bayesian Inference via Backtracking Search

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.

Appears in Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI2003)

References in corpus (2)

• Context-Specific Independence in Bayesian Networks
• Stochastic Constraint Programming

Cited by in corpus (6)

• Formula-Based Probabilistic Inference
• Join-Graph Propagation Algorithms
• The Relationship Between AND/OR Search and Variable Elimination
• AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models
• Learning Branching Heuristics for Propositional Model Counting
• Non-Minimal Triangulations for Mixed Stochastic/Deterministic Graphical Models