Learning Bounded Treewidth Bayesian Networks

Gal Elidan (joint work with Stephen Gould)

Stanford University

Abstract

With the increased availability of real data for complex domains, it is particularly appealing to automatically learn Bayesian network structures that are sufficiently expressive but where inference is still tractable. While the method of thin junction trees can, in principle, be used for this purpose, its fully greedy nature makes it somewhat prone to over-fitting, particularly when the data is sparse and when the desired treewidth is not trivial.
In this talk I will present a novel method for efficiently learning Bayesian networks of bounded treewidth that employs global structure modifications. At the heart of our method is the idea of dynamically updating a triangulation in a way that facilitates the addition of optimal chain structures (with respect to some ordering) that are guaranteed to increase the treewidth bound of the model by at most one. We demonstrate the effectiveness of our "treewidth friendly" method on real-life datasets and show that it is superior to the greedy approach as soon as the bound on the treewidth is nontrivial. Importantly, we show that by employing global operators that are closer in spirit to those used by Chow and Liu for learning optimal trees, we are able to learn better networks even when the treewidth of the model is not bounded.