JdS2012


 English   -  Français  

Résumé de communication



Résumé 294 :

Une relaxation convexe pour les pénalités combinatoires
Obozinski, Guillaume
Ecole Normale Supérieure

Les dernières années ont vu l'émergence des méthodes dites de parcimonie structurée, dont le but est d'identifier un modèle de faible complexité, étant donné une connaissance a priori de sa structure. Précisément, les modèles présentant de la parcimonie structurée sont des modèles dont l'ensemble des paramètres non nuls --- qui correspondent le plus souvent à un ensemble de variables sélectionnées --- est supposé être non seulement de cardinalité faible mais obéir également à un certaine structure de patterns autorisés. Deux exemples importants sont: la parcimonie par groupes, où des groupes de paramètres sont contraints à être simultanément nuls ou non nuls, et la parcimonie hiérarchique où des variables ne peuvent être sélectionnées que suivant un ordre partiel encodé par un arbre ou un graphe orienté acyclique. Une approche naturelle pour induire de la parcimonie structurée dans un modèle est d'ajouter au risque empirique une pénalité implicite ou explicite de la structure des patterns de non zéros. L'objet de cet exposé est de présenter une formulation générale dans laquelle les structures autorisées sont codées par pénalité prenant la forme d'une fonction combinatoire et de montrer que si elle est associée à une régularisation continue, comme une norme Lp, il est possible de construire une régularisation convexe qui fournit un relaxation en un sens optimale du problème combinatoire. Cette relaxation permet de traiter dans un cadre unifié un nombre d'approches a priori disparates pour la parcimonie structurée (dont les normes pour les groupes avec chevauchement, le codage par blocs, et les fonctions sous-modulaires) et d'obtenir des résultats généraux de consistance ou d'estimation du support pour les estimateurs du risque empirique régularisé.