Stochastic Anytime Search for Bounding Marginal MAP
Abstract
The Marginal MAP inference task is known to be extremely hard particularly because the evaluation of each complete MAP assignment involves an exact likelihood computation (a combinatorial sum). For this reason, most recent state-of-the-art solvers that focus on computing anytime upper and lower bounds on the optimal value are limited to solving instances with tractable conditioned summation subproblems. In this paper, we develop new search-based bounding schemes for Marginal MAP that produce anytime upper and lower bounds without performing exact likelihood computations. The empirical evaluation demonstrates the effectiveness of our new methods against the current best-performing search-based bounds.
Cite
Text
Marinescu et al. "Stochastic Anytime Search for Bounding Marginal MAP." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/704Markdown
[Marinescu et al. "Stochastic Anytime Search for Bounding Marginal MAP." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/marinescu2018ijcai-stochastic/) doi:10.24963/IJCAI.2018/704BibTeX
@inproceedings{marinescu2018ijcai-stochastic,
title = {{Stochastic Anytime Search for Bounding Marginal MAP}},
author = {Marinescu, Radu and Dechter, Rina and Ihler, Alexander},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5074-5081},
doi = {10.24963/IJCAI.2018/704},
url = {https://mlanthology.org/ijcai/2018/marinescu2018ijcai-stochastic/}
}