TY - GEN

T1 - Approximate MMAP by Marginal Search

AU - Antonucci, Alessandro

AU - Tiotto, Thomas

N1 - To be presented at the 33rd International Florida Artificial Intelligence Research Society Conference (Flairs-33)

PY - 2020/2/12

Y1 - 2020/2/12

N2 - 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.

AB - 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.

KW - Computer Science - Artificial Intelligence

M3 - Conference contribution

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

BT - FLAIRS-33: The 33rd International Conference of the Florida Artificial Intelligence Research Society

PB - arXiv

T2 - FLAIRS-33

Y2 - 17 May 2020 through 20 May 2020

ER -