GREediness: Theory and Algorithms – GRETA
GRETA -- GREdiness: Theory and Algorithms
Over the past few years, many problems of automatically computing sparse representations of data have been addressed through convex optimization formulations. However, aiming for sparsity actually involves an l0 “norm” regularization/constraint, and the convex optimization way is essentially a proxy to achieve this sparsity. Here, we want to set the focus on another way of dealing with the sparsity objective, which, to our opinion, has been overlooked: greedy methods.
Connexions entre apprentissage et traitement du signal, le point de vue glouton
L'objectif principal de GRETA est d'établir et d'identifier des liens méthodologiques entre l'apprentissage automatique et traitement du signal du point de vue des méthodes gloutonnes. Plus précisément , nous allons aborder et apporter des solutions originales aux problèmes partiellement résolus suivantes :<br />• le développement de nouvelles procédures MP / OMP pour le cas de dictionnaires qui ne sont pas associés à des transformées rapides : i ) des propositions algorithmiques sont visées, qui s'appuieront sur la création de structures de données appropriées , ii ) des questions relatives à la parcimonie structurée seront d'un intérêt primordial , et iii ) le problème de l'apprentissage de dictionnaires appropriés sera abordé.<br />• le développement de nouvelles procédures MP / OMP pour le cas de fonctions de perte arbitraires, autres que la perte des moindres carrés : i ) la vitesse de convergence des algorithmes proposés sera au centre de ce problème et ii ) la pertinence des algorithmes pour diverses tâches d'apprentissage (par exemple, l'apprentissage semi-supervisé, la transduction et sa connexion à inpainting ) sera étudiée ;<br />• la bénédiction de la gloutonnerie : au-delà de la simple efficacité de calcul apportée par les méthodes gloutonnes, nous pensons qu'il y a un certain nombre de situations où elles ont des conséquences positives du point de vue de la généralisation ; en conséquence, nous allons travailler sur la proposition de nouveaux outils pour l'apprentissage statistique qui permettraient de lier formellement les propriétés des algorithmes gloutons et la généralisation : ces outils peuvent largement s'appuyer sur les quantités comme telles que le «spark« ou l'incohérence .
Les membres de l'ANR Greta s'appuient principalement sur les outils et théories suivantes pour effectuer leurs travaux : optimisation convexe, optimisation combinatoriale, théorie de l'apprentissage computationel et informatique fondamentale.
Le stratégie implémentée par le groupe est de revisiter des résultats connus sous un nouvel angle porté par les perspectives ouvertes par les domaines précédemment cités. Nous essayons de comprendre de cette manière quelles méthodes existantes peuvent être étendues et le cas échéant, de préciser leurs limites.
Voici les principaux résultats obtenus jusqu'à présent dans le projet Greta:
- Un nouveau principe d'accélération des méthodes d'optimisation visant à trouver des solutions parcimonieuses à des problèmes convexes, le «Dynamic Screening«, a été développé. Antoine Bonnefoy, doctorant financé par le projet a reçu pour ce travail le prix du meilleur papier étudiant dans la conférence internationale «Eusipco 2014«.
- Une méthode gloutonne d'optimisation basée sur une stratégie d'«Active Sets« a été développée. Elle permet d'identifier par un ensemble infini de caractéristiques, celles qui rendent essentiellement compte du signal.
- Une famille de méthodes gloutonnes pour traiter le coût quadratique a été généralisée pour la recherche de zéros d'un opérateur dans le cadre Hilbertien. Cette méthode a été appliquée au débruitage d'images corrompues par un bruit de Poisson via la régularisation de Moreau-Yosida.
Par ailleurs, une journée thématique permettant la rencontre des chercheurs dans les domaines du traitement de signal, de l'apprentissage statistique et de l'optimisation combinatoriale a eu lieu avec succès en septembre 2014. Un workshop d'audience plus large est prévu pour 2015.
Un certain nombre de chercheurs ont fait (ou ont planifié) un séjour scientifique sur les sites du projet Greta.
Les principales perspectives sont les suivantes :
- revisiter la question de l'«inpainting« du point de vue de la «transduction« et de l'optimisation gloutonne;
- explorer dans quelle mesure les résultats théoriques de l'estimation exacte du support d'un signal («recovery«) peuvent être adaptés au cas de la procédure d'optimisation de Franck-Wolfe, qui est par ailleurs très efficace.
- établir les liens entre méthodes gloutonnes et techniques d'apprentissage développée pour les problèmes de bandits, sachant qu'elles ont en commun de s'appuyer principalement sur des stratégies locales;
- comprendre comment utiliser les méthodes gloutonnes pour dériver de nouveaux algorithmes d'apprentissage actif.
Jusqu'à présent :
- 2 articles de journaux, 1 en révision mineure
- 9 articles de conférences internationales.
Coordination du projet
Liva RALAIVOLA (Laboratoire d'Informatique Fondamentale de Marseille)
L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.
Partenaire
CNRS - LATP Centre National de Recherche Scientifique Délégation Provence et Corse - Laboratoire d'Analyse, Topologie, Probabilités
LITIS- Laboratoire d'Informatique, du Traitement de l'Information et des Systèmes
LIF Laboratoire d'Informatique Fondamentale de Marseille
Aide de l'ANR 372 330 euros
Début et durée du projet scientifique :
August 2012
- 36 Mois
