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, ENS Paris - École normale supérieure - Paris, 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.
Type de document :
Communication dans un congrès
International Conference on Machine Learning, Jun 2013, Atlanta, United States. 2013
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00763921
Contributeur : Ks Seshkumar <>
Soumis le : mardi 11 décembre 2012 - 18:43:15
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : mardi 12 mars 2013 - 10:30:58

Fichiers

convextjt_long.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2013. 〈hal-00763921〉

Partager

Métriques

Consultations de la notice

340

Téléchargements de fichiers

217