Skip to Main content Skip to Navigation
Conference papers

Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs

K. S. Sesh Kumar 1, 2 Francis Bach 2, 1
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this paper, we pose it as a combinatorial optimization problem, which is then relaxed to a convex optimization problem that involves searching over the forest and hyperforest polytopes with special structures, independently. A supergradient method is used to solve the dual problem, with a run-time complexity of $O(k^3 n^{k+2} \log n)$ for each iteration, where $n$ is the number of variables and $k$ is a bound on the treewidth. We compare our approach to state-of-the-art methods on synthetic datasets and classical benchmarks, showing the gains of the novel convex approach.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00763921
Contributor : Ks Seshkumar <>
Submitted on : Tuesday, December 11, 2012 - 6:43:15 PM
Last modification on : Thursday, July 1, 2021 - 5:58:07 PM
Long-term archiving on: : Tuesday, March 12, 2013 - 10:30:58 AM

Files

convextjt_long.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00763921, version 1
  • ARXIV : 1212.2573

Collections

Citation

K. S. Sesh Kumar, Francis Bach. Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs. International Conference on Machine Learning, Jun 2013, Atlanta, United States. ⟨hal-00763921⟩

Share

Metrics

Record views

434

Files downloads

452