MPE inference using an Incremental Build-Infer-Approximate Paradigm
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.
Code (0)
등록된 구현이 없습니다.
Tasks
validSimilar Papers 제목 키워드 기반
IBIA: Bayesian Inference via Incremental Build-Infer-Approximate operations on Clique Trees
Exact inference in Bayesian networks is intractable and has an exponential dependence on the size of the largest clique in the corresponding clique tree (CT), necessitating approximations. Factor based methods to bound c…
Bayesian InferenceApproximate inference of marginals using the IBIA framework
Exact inference of marginals in probabilistic graphical models (PGM) is known to be intractable, necessitating the use of approximate methods. Most of the existing variational techniques perform iterative message passing…
IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function
Exact computation of the partition function is known to be intractable, necessitating approximate inference techniques. Existing methods for approximate inference are slow to converge for many benchmarks. The control of …
validEfficient Incremental Belief Updates Using Weighted Virtual Observations
We present an algorithmic solution to the problem of incremental belief updating in the context of Monte Carlo inference in Bayesian statistical models represented by probabilistic programs. Given a model and a sample-ap…
Probabilistic ProgrammingDual Decomposition from the Perspective of Relax, Compensate and then Recover
Relax, Compensate and then Recover (RCR) is a paradigm for approximate inference in probabilistic graphical models that has previously provided theoretical and practical insights on iterative belief propagation and some …