|We present the ?rst truly polynomial algorithm for PAC-learning the structure of bounded-treewidth junction trees ? an attractive subclass of probabilistic graphical models that permits both the compact representation of probability distributions and ef?cient exact inference. For a constant treewidth, our algorithm has polynomial time and sample complexity. If a junction tree with suf?ciently strong intra-clique dependencies exists, we provide strong theoretical guarantees in terms of KL divergence of the result from the true distribution. We also present a lazy extension of our approach that leads to very signi?cant speedups in practice, and demonstrate the viability of our method empirically, on several real world datasets.
One of our key new theoretical insights is a method for bounding the conditional mutual information of arbitrarily large sets of variables with only polynomially many mutual information computations on ?xed-size subsets of variables, if the underlying distribution can be approximated by a bounded-treewidth junction tree.
Grant ID: IIS-0644225
Number of pages: 8
|Anton Chechetka and Carlos Ernesto Guestrin, "Efficient Principled Learning of Thin Junction Trees," Advances in Neural Information Processing Systems (NIPS 2007), December, 2007.|
author = "Anton Chechetka and Carlos Ernesto Guestrin",
title = "Efficient Principled Learning of Thin Junction Trees",
booktitle = "Advances in Neural Information Processing Systems (NIPS 2007)",
month = "December",
year = "2007",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions