Algorithmes gloutons pour l'optimisation sous contrainte de parcimonie

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

30 personnes membres du GdR ISIS, et 14 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 58 personnes.

Annonce

La notion de parcimonie a connu une grande popularité ces dernières années suite à l'essor de la théorie de l'échantillonnage comprimé. La prise en compte de la parcimonie en traitement du signal et de l'image a ainsi suscité de nombreux développements méthodologiques dans le domaine de l'optimisation.

En effet, la contrainte de parcimonie est associée à la minimisation d'un critère impliquant la "norme" l0 qui conduit à un problème de minimisation NP difficile. Pour résoudre ce problème, de nombreux algorithmes ont vu le jour tels que les algorithmes gloutons, les approches proximales, par majoration-minimisation, par relaxation, ... Leurs performances sont analysées en termes de garanties de convergence et de garanties théoriques assurant la reconstruction du support du vecteur original.

Cette journée s'intéressera plus particulièrement aux algorithmes gloutons, leurs formulations dans le cadre générique de la théorie des matroïdes et dans celui de l'approximation parcimonieuse.

Programme

09h50-10h00 : Introduction de la journée
10h00-10h50 : Cédric Herzet (Inria, Centre Rennes - Bretagne Atlantique) -- Quelques garanties théoriques de reconstruction pour les algorithmes gloutons.
10h50-11h20 : Leïla Belmerhnia (CRAN, Univ. Lorraine) -- Méthodes gloutonnes pour l'approximation parcimonieuse simultanée : application à la sélection de variables des spectres proche-infrarouge de déchets de bois
11h20-11h40 : pause café
11h40-12h30 : Thomas Blumensath (ISVR, University of Southampton) -- Iterative Projection algorithms for non-convexly constrained optimisation
12h30-14h00 : pause déjeuner
14h00-14h50 : Victor Chepoï (LIF, Marseille) -- Matroïdes et algorithme glouton
14h50-15h20 : Loïc Landrieu (Ecole des Ponts ParisTech) -- Cut pursuit : algorithmes rapides pour l'apprentissage de fonctions constantes par morceaux.
15h20-15h40 : pause café
15h40-16h30 : Nicolas Keriven (Inria, Centre Rennes - Bretagne Atlantique) -- Algorithme glouton pour l'estimation compressée de modèles de mélange sur grandes bases de données.

Résumés des contributions

** Auteur : Cédric Herzet
Titre : Quelques garanties théoriques de reconstruction pour les algorithmes gloutons.
Résumé : Depuis une vingtaine d'années, les représentations parcimonieuses constituent un sujet de recherche très actif. Elément clé de leur exploitation dans des scénarios pratiques, la conception d'algorithmes de faible complexité a en particulier fait l'objet de nombreuses contributions. Parmi ces derniers, les algorithmes "gloutons" sont devenus très populaires. Pourtant découverts très tôt, ils offrent en effet un bon compromis "complexité-performance" encore peu égalé. Dans cette présentation, nous rappellerons les principaux algorithmes de cette famille (MP, OMP, OLS, ...) et ferons un rapide tour d'horizon des conditions théoriques permettant d'assurer leur succès.

** Auteurs : Leïla Belmerhnia, El-Hadi Djermoune, David Brie et Cédric Carteret
Titre : Méthodes gloutonnes pour l'approximation parcimonieuse simultanée : application à la sélection de variables des spectres proche-infrarouge de déchets de bois
Résumé : Ce travail est motivé par une application de classification de spectres proche-infrarouge de déchets de bois. L'objectif est de sélectionner les longueurs d'onde les plus pertinentes pour la classification à partir d'une large bande spectrale dans le domaine infrarouge ([1, 2.5] micromètres). Ici, nous abordons la sélection de variables comme un problème d'approximation parcimonieuse simultanée. Ce problème consiste à décomposer simultanément plusieurs signaux d'entrée dans une dictionnaire prédéfini. Les versions simultanées des algorithmes gloutons, CoSaMP, OLS et SBR, sont d'abord présentées. Ensuite, en supposant que les colonnes de la matrice de données sont rangées dans un ordre significatif, (les spectres correspondant au même groupe de bois apparaissent dans des colonnes adjacentes), nous proposons d'incorporer une contrainte de régularité le long des lignes de la matrice de coefficients afin d'imposer une forme constante par morceaux. Ce problème est résolu en deux étapes: d'abord, une approximation parcimonieuse simultanée de la matrice de données est obtenue en utilisant un algorithme glouton. Ensuite, la contrainte de régularité est prise en compte en utilisant la méthode d'optimisation ADMM (Alternate Direction Method of Multipliers). La technique proposée est appliquée sur des mesures proche-infrarouge de spectrométrie de déchets de bois. Chaque spectre est composé de 1647 longueurs d'onde, l'objectif étant de classifier les spectres en deux groupes (recyclable / non recyclable). Les tests expérimentaux valident les avantages de cette approche en termes de taux de classification.

** Auteur : Thomas Blumensath
Titre : Iterative Projection algorithms for non-convexly constrained optimisation
Abstract: Sparsity constraints are popular in signal and image processing applications. Sparse signals can be thought of as signals from a non-convex set so that the solution of inverse problems under sparsity constraints becomes a constraint optimisation problem where the constraint is non-convex. Sparsity constraints are useful as they can encode many useful signal structures encountered in typical applications. However, not all structures can be expressed naturally in terms of sparsity. Other useful constraints, such as low rank constraints or the requirement for a signal to lie on a manifold can also be useful. In this talk I will discuss a simple iterative greedy algorithm that can solve optimisation problems under a range of non-convex constraints. A greedy locally optimal projection step is iterated with a descend step. Surprisingly, under certain conditions on the optimisation problem, this simple approach will lead to globally near optimal solutions despite the non-convex nature of the constraints, which typically do not allow for such guarantees.

** Auteur : Victor Chepoï
Titre : Matroïdes et algorithme glouton
Résumé : Dans cette présentation, nous présenterons une introduction aux structures de matroïdes et leurs relations avec les algorithmes gloutons. Nous rappellerons les principales caractérisations axiomatiques des matroïdes par ensembles indépendants, bases, circuits, rang, fermeture et dualité. Nous présenterons aussi la caractérisation classique des matroïdes via l'algorithme glouton et l'utilisation de l'algorithme glouton pour la minimisation de fonctions sous-modulaires sur les matroïdes. S'il reste du temps, nous considérerons des généralisations des matroïdes dans le cadre de l'analyse convexe discrète.

** Auteurs : Loïc Landrieu et Guillaume Obozinski :
Titre : Cut pursuit : algorithmes rapides pour l'apprentissage de fonctions constantes par morceaux.
Résumé : Nous proposons une famille d'algorithmes reposant sur des principes d'active set et gloutons pour l'optimisation d'énergies pénalisées par la variation totale ou son équivalent L0, la longueur des contours (Piecewise-Constant Mumford-Shah Penalty). Nos algorithmes exploitent computationnellement la parcimonie du gradient de la solution, et sont donc particulièrement efficaces quand les solutions de ces problèmes sont "simples", i.e. présentent un petit nombre de régions constantes.
Le principe de Cut Pursuit est d'exploiter cette structure en découpant récursivement les régions constantes des solutions intermédiaires à l'aise de graph cuts. Nos algorithmes présentent une accélération signifiante des temps de résolution pour des images "simples" pour des tâches de défloutage et débruitage. De plus dans le cadre L0 les minimums locaux sont meilleurs et atteints plus vite que pour les algorithmes de l'état de l'art. Je présenterai également des résultats très encourageants sur la segmentation d'espaces géographiques et de nuages de points LIDAR.

**Auteurs : Nicolas Keriven, Anthony Bourrier, Rémi Gribonval et Patrick Pérez
Titre : Algorithme glouton pour l'estimation compressée de modèles de mélange sur grandes bases de données.
Résumé : Dans cette présentation, nous parlerons de travaux récemment présentés à ICASSP [1]. Nous proposons une méthode "d'apprentissage compressé" (compressive learning) ayant pour but d'estimer certains paramètres à partir d'une base de données volumineuse. Se basant sur les principes de l'acquisition comprimée en dimension infinie, celle-ci consiste à calculer des moments généralisés, choisis aléatoirement, de la distribution de probabilité sous-jacente aux données obtenant ainsi une version comprimée de la base de donnée appelée sketch, puis à "reconstruire" cette distribution en estimant ses paramètres à partir du sketch. La notion de parcimonie dans l'espace des distributions est ici assimilée à un modèle de mélange de distributions, et nous proposons des variantes d'algorithmes gloutons classiques pour la reconstruction. Nous appliquons ce cadre à un problème d'estimation de Mélanges de Gaussiennes, en utilisant un échantillonnage aléatoire de la fonction caractéristique comme sketch. Une heuristique adaptée pour le choix des fréquences d'échantillonnage est également proposée.
Expérimentalement, notre méthode donne des résultats d'estimation de précision comparable à ceux d'EM, en étant bien moins gourmande en temps et mémoire lorsque la base de donnée est grande. En particulier, l'opération de compression s'effectue aisément sur GPU ou clusters de machines, ou encore de manière incrémentale. Nous illustrons ainsi notre approche sur un problème de reconnaissance de locuteur, pour lequel nous exploitons pleinement un corpus de 1000 heures d'enregistrement, compressé dans un seul sketch de taille extrêmement réduite.

Enfin, principalement dans une perspective de travaux futurs, nous évoquerons des résultats théoriques préliminaires récents concernant la préservation de l'information par l'opérateur de sketch du point de vue de l'acquisition comprimée, en utilisant certaines variantes de notions classiques de ce domaine.

[1] Nicolas Keriven, Anthony Bourrier, Rémi Gribonval, and Patrick Pérez. Sketching for Large-Scale Learning of Mixture Models. In ICASSP, 2016.

Organisateurs :