This semester we did a project in machine intelligence, however, as I find probability calculus and Bayesian networks utterly boring I convinced my group to do a project about triangulation of Bayesian networks. A triangulation of an undirected graph G, is a set of edges called fill-ins, such that G with these fill-ins added is a chordal graph (a graph that doesn’t have a chord-less cycle of more than 3 node). Triangulation is of graphs is used for many purposes, and with difference optimality criteria, such as minimum fill-ins, minimum clique size (tree width) and minimum maximal clique sum (optimal table size), as is relevant for Bayesian networks.

The problem of finding an optimal triangulation is NP-Hard (with respect to mentioned optimality criteria). And since there’s many fairly good simple greedy heuristics, it can be argued that algorithms for optimal triangulation of Bayesian networks are uninteresting. However, to check of a greedy heuristic is good, optimal triangulations are needed. It’s also possible that optimal triangulation might be worthwhile if  computed offline, especially if the application needs to process a lot of data or work on an embedded platform. Or whatever, optimality is always slightly interesting, if not for anything useful, than for the fun of finding them…

In this project we implemented some simple greedy triangulation heuristics, compared their result to the optimal solutions. But most interesting is probably our work on search algorithms for optimal triangulations of Bayesian networks. We based our work on two articles by Thorsten J. Ottosen and Finn V. Jensen, who does a best or depth first search in the space of all elimination orders. As far as we’re aware these articles are the only ones that proposes algorithms for optimal triangulation of  Bayesian networks.

In this project we’ve created good improvements to the optimal triangulation algorithms. We reduce the search space by excluding elimination orders resulting in the same triangulation. Our improvements provides around 5x speedup on sparse graphs, and can be applied to regardless of the optimality criterion. I think this project was really cool, because I got to play with something that was new and fairly untouched. And the fact that I managed to propose a a few interesting improvements didn’t make it any less cool 🙂

Report and source code:

• Project report (0.7 MiB PDF)
• Source code for implementation (47.8 MiB tarball)