Last modified: 2020-05-05

#### 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 the evidence in input, 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 promoted to the evidence. The sequential iteration of this procedure leads to a MMAP explanation, whose confidence can be identified with the minimum information gain obtained during the process. A preliminary empirical analysis shows that the proposed confidence measure is properly detecting instances for which the algorithm is reliable and, for sufficient high reliability levels, the algorithm gives the exact solution or an approximation whose Hamming distance from the exact one is small.