Timezone: »

Efficient Principled Learning of Thin Junction Trees
Anton Chechetka · Carlos Guestrin

Mon Dec 03 10:30 AM -- 10:40 AM (PST) @
We present the first truly polynomial algorithm for 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, and provides strong theoretical guarantees in terms of $KL$ divergence from the true distribution. We also present a lazy extension of our approach that leads to very significant speed ups 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 random variables with only a polynomial number of mutual information computations on fixed-size subsets of variables, when the underlying distribution can be approximated by a bounded treewidth junction tree.

Author Information

Anton Chechetka (Carnegie Mellon University)
Carlos Guestrin (Apple & University of Washington)

More from the Same Authors