PAC-learning bounded tree-width graphical models
Mukund Narasimhan, Jeff Bilmes · 2004
We show that the class of strongly connected graphical models with treewidth at most k can be properly efficiently PAC-learnt with respect to the Kullback-Leibler Divergence. Previous approaches to this problem, such as those of Chow ([1]), and Hoffgen ([7]) have shown that this class is PAClearnable by reducing it to a combinatorial optimization problem. However, for k> 1, this problem is NPcomplete ([15]), and so unless P=NP, these approaches will take exponential amounts of time. Our approach differs