Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows

Julien Mairal 1, * Bin Yu 2
* Auteur correspondant
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or obtain results that are easier to interpret. Regularization or penalty functions for selecting features in graphs have recently been proposed, but they raise new algorithmic challenges. For example, they typically require solving a combinatorially hard selection problem among all connected subgraphs. In this paper, we propose computationally feasible strategies to select a sparse and well-connected subset of features sitting on a directed acyclic graph (DAG). We introduce structured sparsity penalties over paths on a DAG called ''path coding'' penalties. Unlike existing regularization functions that model long-range interactions between features in a graph, path coding penalties are tractable. The penalties and their proximal operators involve path selection problems, which we efficiently solve by leveraging network flow optimization. We experimentally show on synthetic, image, and genomic data that our approach is scalable and leads to more connected subgraphs than other regularization functions for graphs.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2013, 14, pp.2449-2485. 〈http://jmlr.org/papers/volume14/mairal13a/mairal13a.pdf〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00806372
Contributeur : Julien Mairal <>
Soumis le : jeudi 29 août 2013 - 14:57:29
Dernière modification le : mercredi 11 avril 2018 - 02:00:05
Document(s) archivé(s) le : jeudi 6 avril 2017 - 10:34:46

Fichiers

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

Identifiants

  • HAL Id : hal-00806372, version 2

Collections

Citation

Julien Mairal, Bin Yu. Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows. Journal of Machine Learning Research, Journal of Machine Learning Research, 2013, 14, pp.2449-2485. 〈http://jmlr.org/papers/volume14/mairal13a/mairal13a.pdf〉. 〈hal-00806372v2〉

Partager

Métriques

Consultations de la notice

5335

Téléchargements de fichiers

791