Learning Thin Junction Trees via Graph Cuts

Dafna Shahaf, Anton Chechetka, and Carlos Ernesto Guestrin
Artificial Intelligence and Statistics (AISTATS), April, 2009.

  • Adobe portable document format (pdf) (2MB)
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.

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.

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
   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",