Anytime Recursive Best-First Search for Bounding Marginal MAP

Autor:	Alexander T. Ihler, Adi Botea, Radu Marinescu, Akihiro Kishimoto, Rina Dechter
Rok vydání:	2019
Předmět:	Scheme (programming language) Memory management Theoretical computer science Computer science Bounding overwatch Inference Best-first search General Medicine Graphical model computer Upper and lower bounds computer.programming_language Task (project management)
Zdroj:	AAAI Scopus-Elsevier
ISSN:	2374-3468 2159-5399
DOI:	10.1609/aaai.v33i01.33017924
Popis:	Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art solvers for this task are based on a hybrid best-first and depth-first search scheme that allows them to compute upper and lower bounds on the optimal solution value in an anytime fashion. These methods however are memory intensive schemes (via the best-first component) and do not have an efficient memory management mechanism. For this reason, they are often less effective in practice, especially on difficult problem instances with very large search spaces. In this paper, we introduce a new recursive best-first search based bounding scheme that operates efficiently within limited memory and computes anytime upper and lower bounds that improve over time. An empirical evaluation demonstrates the effectiveness of our proposed approach against current solvers.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9e9560ef96b28c2e782a623f26f7980b https://doi.org/10.1609/aaai.v33i01.33017924 Zobrazit plný text záznamu