Value-Based Abstraction Functions for Abstraction Sampling

Bobak Pezeshki, Kalev Kask, Alexander Ihler, Rina Dechter
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:2861-2901, 2024.

Abstract

Monte Carlo methods are powerful tools for solving problems involving complex probability distributions. Despite their versatility, these methods often suffer from inefficiencies, especially when dealing with rare events. As such, importance sampling emerged as a prominent technique for alleviating these challenges. Recently, a new scheme called Abstraction Sampling was developed that incorporated stratification to importance sampling over graphical models. However, existing work only explored a limited set of abstraction functions that guide stratification. This study introduces three new classes of abstraction functions combined with seven distinct partitioning schemes, resulting in twenty-one new abstraction functions, each motivated by theory and intuition from both search and sampling domains. An extensive empirical analysis on over 400 problems compares these new schemes highlighting several well-performing candidates.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-pezeshki24a, title = {Value-Based Abstraction Functions for Abstraction Sampling}, author = {Pezeshki, Bobak and Kask, Kalev and Ihler, Alexander and Dechter, Rina}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {2861--2901}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/pezeshki24a/pezeshki24a.pdf}, url = {https://proceedings.mlr.press/v244/pezeshki24a.html}, abstract = {Monte Carlo methods are powerful tools for solving problems involving complex probability distributions. Despite their versatility, these methods often suffer from inefficiencies, especially when dealing with rare events. As such, importance sampling emerged as a prominent technique for alleviating these challenges. Recently, a new scheme called Abstraction Sampling was developed that incorporated stratification to importance sampling over graphical models. However, existing work only explored a limited set of abstraction functions that guide stratification. This study introduces three new classes of abstraction functions combined with seven distinct partitioning schemes, resulting in twenty-one new abstraction functions, each motivated by theory and intuition from both search and sampling domains. An extensive empirical analysis on over 400 problems compares these new schemes highlighting several well-performing candidates.} }
Endnote
%0 Conference Paper %T Value-Based Abstraction Functions for Abstraction Sampling %A Bobak Pezeshki %A Kalev Kask %A Alexander Ihler %A Rina Dechter %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-pezeshki24a %I PMLR %P 2861--2901 %U https://proceedings.mlr.press/v244/pezeshki24a.html %V 244 %X Monte Carlo methods are powerful tools for solving problems involving complex probability distributions. Despite their versatility, these methods often suffer from inefficiencies, especially when dealing with rare events. As such, importance sampling emerged as a prominent technique for alleviating these challenges. Recently, a new scheme called Abstraction Sampling was developed that incorporated stratification to importance sampling over graphical models. However, existing work only explored a limited set of abstraction functions that guide stratification. This study introduces three new classes of abstraction functions combined with seven distinct partitioning schemes, resulting in twenty-one new abstraction functions, each motivated by theory and intuition from both search and sampling domains. An extensive empirical analysis on over 400 problems compares these new schemes highlighting several well-performing candidates.
APA
Pezeshki, B., Kask, K., Ihler, A. & Dechter, R.. (2024). Value-Based Abstraction Functions for Abstraction Sampling. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:2861-2901 Available from https://proceedings.mlr.press/v244/pezeshki24a.html.

Related Material