Value elimination: A new algorithm for Bayesian inference

Based on the paradigm of backtracking search, Value Elimination (ValElim) is a new algorithm for inference in Bayesian networks. It represents an advance over previous algorithms in the sense that it can achieve all of their performance guarantees (up to a constant factor) while provably achieving an exponential speedup on some problems. Also, by incurring only a small (polynomial) extra cost, ValElim offers considerably more flexibility in terms of its ability to exploit context specific structure, logical reasoning, and dynamic variable orderings. Moreover, ValElim provides the same space-time tradeoff as Recursive Conditioning. An initial implementation of ValElim demonstrates very promising performance, often being one or two orders of magnitude faster than a commercial Bayesian inference engine, despite the fact that it does not as yet take advantage of context specific structure.