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

Structure learning algorithms usually focus on the compactness of the learned model. However, for general compact models, both exact and approximate inference are still NP-hard. Therefore, the focus only on compactness leads to learning models that require approximate inference techniques, thus reducing their prediction quality. In this paper, we propose a method for learning an attractive class of models: bounded-treewidth junction trees, which permit both compact representation of probability distributions and efficient exact inference. Using Bethe approximation of the likelihood, we transform the problem of finding a good junction tree separator into a minimum cut problem on a weighted graph. Using the graph cut intuition, we present an efficient algorithm with theoretical guarantees for finding good separators, which we recursively apply to obtain a thin junction tree. Our extensive empirical evaluation demonstrates the benefit of applying exact inference using our models to answer queries. We also extend our technique to learning low tree-width conditional random fields, and demonstrate significant improvements over state of the art block-L1 regularization techniques.

Notes

Sponsor: NSF, ARO

Text Reference

Dafna Shahaf, Anton Chechetka, and Carlos Ernesto Guestrin, "Learning Thin Junction Trees via Graph Cuts," Artificial Intelligence and Statistics (AISTATS), April, 2009.

BibTeX Reference

@inproceedings{Chechetka_2009_6568,
   author = "Dafna Shahaf and Anton Chechetka and Carlos Ernesto Guestrin",
   title = "Learning Thin Junction Trees via Graph Cuts",
   booktitle = "Artificial Intelligence and Statistics (AISTATS)",
   month = "April",
   year = "2009",
}

The Robotics Institute

Menu