An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference

Aleksandra Petrova, Javier Larrosa, Emma Rollon
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:427-437, 2024.

Abstract

In this paper, we address the use of the implicit hitting set approach (HS) for MAP (Markov Random Fields) and MPE (Bayesian Networks). Since the HS approach is quite general and finding the best version is very problem-dependent, here we present an adaptive algorithm that learns a reasonably good version for the instance being solved. The algorithm, which follows a Multi-armed Bandit structure, explores the different alternatives as it iterates and adapts their weights based on their performance. The weight is used to decide on the probability of selecting a given alternative in the next iteration.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-petrova24a, title = {An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference}, author = {Petrova, Aleksandra and Larrosa, Javier and Rollon, Emma}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {427--437}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/petrova24a/petrova24a.pdf}, url = {https://proceedings.mlr.press/v246/petrova24a.html}, abstract = {In this paper, we address the use of the implicit hitting set approach (HS) for MAP (Markov Random Fields) and MPE (Bayesian Networks). Since the HS approach is quite general and finding the best version is very problem-dependent, here we present an adaptive algorithm that learns a reasonably good version for the instance being solved. The algorithm, which follows a Multi-armed Bandit structure, explores the different alternatives as it iterates and adapts their weights based on their performance. The weight is used to decide on the probability of selecting a given alternative in the next iteration.} }
Endnote
%0 Conference Paper %T An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference %A Aleksandra Petrova %A Javier Larrosa %A Emma Rollon %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-petrova24a %I PMLR %P 427--437 %U https://proceedings.mlr.press/v246/petrova24a.html %V 246 %X In this paper, we address the use of the implicit hitting set approach (HS) for MAP (Markov Random Fields) and MPE (Bayesian Networks). Since the HS approach is quite general and finding the best version is very problem-dependent, here we present an adaptive algorithm that learns a reasonably good version for the instance being solved. The algorithm, which follows a Multi-armed Bandit structure, explores the different alternatives as it iterates and adapts their weights based on their performance. The weight is used to decide on the probability of selecting a given alternative in the next iteration.
APA
Petrova, A., Larrosa, J. & Rollon, E.. (2024). An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:427-437 Available from https://proceedings.mlr.press/v246/petrova24a.html.

Related Material