MPE inference using an Incremental Build-Infer-Approximate Paradigm
This addresses the computational challenge of MPE inference for users of Bayesian networks, though it is incremental as it builds on the IBIA framework.
The paper tackles the NP-complete problem of exact most probable explanation (MPE) inference in Bayesian networks by proposing an approximate algorithm based on the incremental build-infer-approximate (IBIA) framework, which obtains valid assignments in 100 out of 117 benchmarks with accuracy comparable to branch and bound search and competitive run times.
Exact inference of the most probable explanation (MPE) in Bayesian networks is known to be NP-complete. In this paper, we propose an algorithm for approximate MPE inference that is based on the incremental build-infer-approximate (IBIA) framework. We use this framework to obtain an ordered set of partitions of the Bayesian network and the corresponding max-calibrated clique trees. We show that the maximum belief in the last partition gives an estimate of the probability of the MPE assignment. We propose an iterative algorithm for decoding, in which the subset of variables for which an assignment is obtained is guaranteed to increase in every iteration. There are no issues of convergence, and we do not perform a search for solutions. Even though it is a single shot algorithm, we obtain valid assignments in 100 out of the 117 benchmarks used for testing. The accuracy of our solution is comparable to a branch and bound search in majority of the benchmarks, with competitive run times.