Scaling Up AND/OR Abstraction Sampling
Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, Rina Dechter
Abstract
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.
BibTeX
@inproceedings{ijcai2020p589,
title = {Scaling Up AND/OR Abstraction Sampling},
author = {Kask, Kalev and Pezeshki, Bobak and Broka, Filjor and Ihler, Alexander and Dechter, Rina},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {4266--4274},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/589},
url = {https://doi.org/10.24963/ijcai.2020/589},
}