AND/OR Search Spaces for Anytime Probabilistic Reasoning
summary
Connects AND/OR search graphs to arithmetic circuits and uses compiled, graph-guided heuristics to drive anytime algorithms for MAP, marginal MAP and partition function estimation. Builds AND/OR multivalued decision diagram tools and uses minibucket heuristic (with weighted/minibucket importance sampling) to get admissible bounds while searching. Introduces abstraction sampling that samples subtrees (unbiased estimator, probe-size bounded by abstraction granularity) using context- and heuristic-based abstractions. Empirical UAI-benchmark results and revived competitions show strong anytime performance; abstraction sampling improves variance but currently lacks deterministic bounds on every run.
AI-written summary · about