Shivani Bathla

Shivani Bathla, Vinita Vasudevan

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 accuracy-complexity trade-off is also non-trivial in many of these methods. We propose a novel incremental build-infer-approximate (IBIA) framework for approximate inference that addresses these issues. In this framework, the probabilistic graphical model is converted into a sequence of clique tree forests (SCTF) with bounded clique sizes. We show that the SCTF can be used to efficiently compute the partition function. We propose two new algorithms which are used to construct the SCTF and prove the correctness of both. The first is an algorithm for incremental construction of CTFs that is guaranteed to give a valid CTF with bounded clique sizes and the second is an approximation algorithm that takes a calibrated CTF as input and yields a valid and calibrated CTF with reduced clique sizes as the output. We have evaluated our method using several benchmark sets from recent UAI competitions and our results show good accuracies with competitive runtimes.

Shivani Bathla, Vinita Vasudevan

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 in loopy graphs which is slow to converge for many benchmarks. In this paper, we propose a new algorithm for marginal inference that is based on the incremental build-infer-approximate (IBIA) paradigm. Our algorithm converts the PGM into a sequence of linked clique tree forests (SLCTF) with bounded clique sizes, and then uses a heuristic belief update algorithm to infer the marginals. For the special case of Bayesian networks, we show that if the incremental build step in IBIA uses the topological order of variables then (a) the prior marginals are consistent in all CTFs in the SLCTF and (b) the posterior marginals are consistent once all evidence variables are added to the SLCTF. In our approach, the belief propagation step is non-iterative and the accuracy-complexity trade-off is controlled using user-defined clique size bounds. Results for several benchmark sets from recent UAI competitions show that our method gives either better or comparable accuracy than existing variational and sampling based methods, with smaller runtimes.

Shivani Bathla, Vinita Vasudevan

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.

Shivani Bathla, Vinita Vasudevan

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 clique sizes are more accurate than structure based methods, but expensive since they involve inference of beliefs in a large number of candidate structure or region graphs. We propose an alternative approach for approximate inference based on an incremental build-infer-approximate (IBIA) paradigm, which converts the Bayesian network into a data structure containing a sequence of linked clique tree forests (SLCTF), with clique sizes bounded by a user-specified value. In the incremental build stage of this approach, CTFs are constructed incrementally by adding variables to the CTFs as long as clique sizes are within the specified bound. Once the clique size constraint is reached, the CTs in the CTF are calibrated in the infer stage of IBIA. The resulting clique beliefs are used in the approximate phase to get an approximate CTF with reduced clique sizes. The approximate CTF forms the starting point for the next CTF in the sequence. These steps are repeated until all variables are added to a CTF in the sequence. We prove that our algorithm for incremental construction of clique trees always generates a valid CT and our approximation technique preserves the joint beliefs of the variables within a clique. Based on this, we show that the SLCTF data structure can be used for efficient approximate inference of partition function and prior and posterior marginals. More than 500 benchmarks were used to test the method and the results show a significant reduction in error when compared to other approximate methods, with competitive runtimes.