Approximate MMAP by Marginal Search

Alessandro Antonucci, Thomas Tiotto

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

30 Downloads (Pure)

Abstract

We present a heuristic strategy for marginal MAP (MMAP) queries in graphical models. The algorithm is based on a reduction of the task to a polynomial number of marginal inference computations. Given an input evidence, the marginals mass functions of the variables to be explained are computed. Marginal information gain is used to decide the variables to be explained first, and their most probable marginal states are consequently moved to the evidence. The sequential iteration of this procedure leads to a MMAP explanation and the minimum information gain obtained during the process can be regarded as a confidence measure for the explanation. Preliminary experiments show that the proposed confidence measure is properly detecting instances for which the algorithm is accurate and, for sufficiently high confidence levels, the algorithm gives the exact solution or an approximation whose Hamming distance from the exact one is small.
Original languageEnglish
Title of host publicationFLAIRS-33: The 33rd International Conference of the Florida Artificial Intelligence Research Society
Subtitle of host publicationProceedings
PublisherarXiv
Publication statusPublished - 12-Feb-2020
EventFLAIRS-33: The 33rd International Conference of the Florida Artificial Intelligence Research Society - North Miami Beach, United States
Duration: 17-May-202020-May-2020

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
ISSN (Print)2159-5399

Conference

ConferenceFLAIRS-33
CountryUnited States
City North Miami Beach
Period17/05/202020/05/2020

Keywords

  • Computer Science - Artificial Intelligence

Cite this