Learning Bounded Treewidth Bayesian Networks
Gal Elidan, Stephen Jay Gould · ANU Open Research (Australian National University) · 2008
With the increased availability of real data for complex domains, it is desirable to automatically learn Bayesian network structures that are sufficiently expressive while at the same time allowing for tractable inference. While the method of thin junction trees can, in principle, be used for this purpose, its fully greedy nature makes it prone to overfitting, particularly when the data is sparse. In this work we present a novel method for efficiently learning Bayesian networks of bounded treewidth that employs global structure modifications. At the heart of our method is a dynamic triangulation that we update in a way that facilitates the addition of chain structures that increase the treewidth bound of the current 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 also show that by making use of global operators, we are able to achieve better generalization even when learning Bayesian networks of unbounded treewidth.