Annealed MAP
This addresses the computational bottleneck in probabilistic inference for researchers and practitioners using Bayesian networks, though it is an incremental improvement over existing methods.
The paper tackles the NP-hard problem of Maximum a Posteriori (MAP) assignment in Bayesian networks, which previous methods often fail to solve for large networks, by proposing the AnnealedMAP algorithm based on simulated annealing. The results show that it maintains good solution quality and solves many previously intractable problems.
Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables given the partial evidence on the other variables in a Bayesian network. MAP has been shown to be a NP-hard problem [22], even for constrained networks, such as polytrees [18]. Hence, previous approaches often fail to yield any results for MAP problems in large complex Bayesian networks. To address this problem, we propose AnnealedMAP algorithm, a simulated annealing-based MAP algorithm. The AnnealedMAP algorithm simulates a non-homogeneous Markov chain whose invariant function is a probability density that concentrates itself on the modes of the target density. We tested this algorithm on several real Bayesian networks. The results show that, while maintaining good quality of the MAP solutions, the AnnealedMAP algorithm is also able to solve many problems that are beyond the reach of previous approaches.