Efficient Principled Learning of Thin Junction Trees

December 2007

Efficient Principled Learning of Thin Junction Trees

Authors:

Anton Chechetka and Carlos Ernesto Guestrin
Conference Paper
Proceedings of (NeurIPS) Neural Information Processing Systems

Abstract:

We present the first 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 efficient exact inference. For a constant treewidth, our algorithm has polynomial time and sample complexity. If a junction tree with sufficiently 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 significant 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 fixed-size subsets of variables, if the underlying distribution can be approximated by a bounded-treewidth junction tree.
@conference{Chechetka-2007-9884,
author = {Anton Chechetka And Carlos Ernesto Guestrin},
title = {Efficient Principled Learning of Thin Junction Trees},
booktitle = {Proceedings of (NeurIPS) Neural Information Processing Systems},
year = {2007},
month = {December},
pages = {273 - 280},
}
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.