Maximizing submodular functions using probabilistic graphical models

K. S. Sesh Kumar 1, 2 Francis Bach 1, 2
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 maximizing submodular functions; while this problem is known to be NP-hard, several numerically efficient local search techniques with approximation guarantees are available. In this paper, we propose a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models. In a graphical model, the entropy of the joint distribution decomposes as a sum of marginal entropies of subsets of variables; moreover, for any distribution, the entropy of the closest distribution factorizing in the graphical model provides an bound on the entropy. For directed graphical models, this last property turns out to be a direct consequence of the submodularity of the entropy function, and allows the generalization of graphical-model-based upper bounds to any submodular functions. These upper bounds may then be jointly maximized with respect to a set, while minimized with respect to the graph, leading to a convex variational inference scheme for maximizing submodular functions, based on outer approximations of the marginal polytope and maximum likelihood bounded treewidth structures. By considering graphs of increasing treewidths, we may then explore the trade-off between computational complexity and tightness of the relaxation. We also present extensions to constrained problems and maximizing the difference of submodular functions, which include all possible set functions.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00860575
Contributeur : Ks Seshkumar <>
Soumis le : mardi 10 septembre 2013 - 17:16:48
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : jeudi 6 avril 2017 - 17:17:49

Fichiers

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

Identifiants

  • HAL Id : hal-00860575, version 1
  • ARXIV : 1309.2593

Collections

Citation

K. S. Sesh Kumar, Francis Bach. Maximizing submodular functions using probabilistic graphical models. 2013. 〈hal-00860575〉

Partager

Métriques

Consultations de la notice

525

Téléchargements de fichiers

703