Scaling Up AND/OR Abstraction Sampling

Scaling Up AND/OR Abstraction Sampling

Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, Rina Dechter

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4266-4274. https://doi.org/10.24963/ijcai.2020/589

Abstraction Sampling (AS) is a recently introduced enhancement of Importance Sampling that exploits stratification by using a notion of abstractions: groupings of similar nodes into abstract states. It was previously shown that AS performs particularly well when sampling over an AND/OR search space; however, existing schemes were limited to ``proper'' abstractions in order to ensure unbiasedness, severely hindering scalability. In this paper, we introduce AOAS, a new Abstraction Sampling scheme on AND/OR search spaces that allow more flexible use of abstractions by circumventing the properness requirement. We analyze the properties of this new algorithm and, in an extensive empirical evaluation on five benchmarks, over 480 problems, and comparing against other state of the art algorithms, illustrate AOAS's properties and show that it provides a far more powerful and competitive Abstraction Sampling framework.
Keywords:
Uncertainty in AI: Approximate Probabilistic Inference
Uncertainty in AI: Bayesian Networks
Uncertainty in AI: Graphical Models