Approximate MMAP by Marginal Search
This work addresses a specific computational bottleneck in probabilistic inference for graphical models, offering an incremental improvement over existing methods.
The paper tackles the problem of computing marginal MAP (MMAP) explanations in graphical models by proposing a heuristic algorithm that reduces the task to multiple marginal inference computations, using marginal information gain to sequentially select variables and their states. Preliminary experiments show that for high confidence levels, the algorithm provides exact solutions or approximations with small Hamming distances from the exact ones.
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.