An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference
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
Text
Petrova et al. "An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference." Proceedings of The 12th International Conference on Probabilistic Graphical Models, 2024.Markdown
[Petrova et al. "An Adaptive Implicit Hitting Set Algorithm for MAP and MPE Inference." Proceedings of The 12th International Conference on Probabilistic Graphical Models, 2024.](https://mlanthology.org/pgm/2024/petrova2024pgm-adaptive/)BibTeX
@inproceedings{petrova2024pgm-adaptive,
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},
year = {2024},
pages = {427-437},
volume = {246},
url = {https://mlanthology.org/pgm/2024/petrova2024pgm-adaptive/}
}