Value Elimination: Bayesian Inference via Backtracking Search
  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.
