The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

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.

Notes

Sponsor: NSF

Grant ID: IIS-0644225

Number of pages: 8

Text Reference

Anton Chechetka and Carlos Ernesto Guestrin, "Efficient Principled Learning of Thin Junction Trees," Advances in Neural Information Processing Systems (NIPS 2007), December, 2007.

BibTeX Reference

@inproceedings{Chechetka_2007_6218,
   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

Menu