Anytime Marginal MAP Inference
This provides an incremental improvement for researchers and practitioners needing efficient approximate solutions to marginal MAP problems in probabilistic graphical models.
The paper tackles the marginal MAP inference problem in graphical models by developing a new anytime algorithm that provides guaranteed bounds within fixed computational resources. Experiments show it outperforms Park and Darwiche's systematic search, especially for problems with many MAP variables and moderate tree-width.
This paper presents a new anytime algorithm for the marginal MAP problem in graphical models. The algorithm is described in detail, its complexity and convergence rate are studied, and relations to previous theoretical results for the problem are discussed. It is shown that the algorithm runs in polynomial-time if the underlying graph of the model has bounded tree-width, and that it provides guarantees to the lower and upper bounds obtained within a fixed amount of computational resources. Experiments with both real and synthetic generated models highlight its main characteristics and show that it compares favorably against Park and Darwiche's systematic search, particularly in the case of problems with many MAP variables and moderate tree-width.