Inference in Markov Networks
Willem Obbens, Siegfried Nijssen, Johannes Schmidt-Hieber · 2014
This thesis covers methods for performing exact as well as approximate inference in Markov and Bayesian networks. Specifically, we study MPE inference where the problem is to find states of probability distributions with maximal probability. As Markov networks are strictly more general than Bayesian networks, the majority of the algorithms in this thesis are designed for the former type of network. We propose a methodology consisting of three components: ant colony optimisation, belief propagation and integer linear programming. In previous research, [Dar09] considered variable elimination and a branch-and-bound depth first search algorithm on the assignment tree to compute exact solutions to the problem of MPE inference. Furthermore, [GBH04] created an ant colony algorithm to find approximate solutions. Finding an exact solution to this problem is NP-complete in general [Dar09], so exact MPE inference is intractable in the case of big networks. In this scenario, one would normally resort to approximation algorithms. However, sometimes an exact solution is required, such as when important decisions have to be made depending on the solution. In that respect it is also useful to be able to quickly compute an approximate solution and use it as a lower bound constraint to compute an exact solution more quickly. The problem is that the current exact algorithms have no way to easily integrate such a constraint into a problem. As a solution, this thesis provides a reduction of the problem of MPE inference in Markov networks to integer linear programming (ILP) problems, where it is straightforward to add a lower bound constraint on the objective function. There is also a wealth of literature on ILP solvers and several decades of work, something we can benefit from greatly [Nie]. As for approximation algorithms, we designed a hybrid belief propagation/ant colony algorithm for MPE inference in Markov networks and a pure ant colony algorithm for MPE inference in Bayesian networks, inspired by [GBH04]. The hybrid algorithm is exponential in the maximum clique size and its core performs belief propagation on a spanning tree which is generated by the ant colony spanning tree search component. The pure ant colony algorithm is linear in the number of network variables. For benchmarking, the algorithms were programmed in the non-strict functional programming language Haskell. The experiments, using datasets from the Probabilistic Inference Challenge 2011, show that neither of these two algorithms outperforms the other and that they perform approximately equally fast on small datasets. They also show that solutions found by the approximation algorithms can decrease the execution time of the ILP solver if the approximation is used as a lower bound constraint.