Value Elimination: Bayesian Inference via Backtracking Search
This work addresses Bayesian inference for AI and machine learning practitioners, offering a novel algorithmic approach that is incremental in adapting existing techniques.
The paper tackles the problem of Bayesian inference by applying backtracking search, showing that it can achieve performance guarantees similar to standard algorithms and potentially perform much better on certain problems, with a competitive implementation demonstrated.
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.