(English below)

Jeudi 19 Décembre 2019 à 17h à l'amphithéâtre du Bâtiment 660, Rue Noetzlin, 91190 Gif-sur-Yvette

Soutenance de thèse de Lisheng Sun-Hosoya

Titre
Meta-Learning en tant que Processus de décision Markovien

Résumé
L'apprentissage automatique (ML) a connu d'énormes succès ces dernières années et repose sur un nombre toujours croissant d'applications réelles. Cependant, la conception d'algorithmes prometteurs pour un problème spécifique nécessite toujours un effort humain considérable. L'apprentissage automatique (AutoML) a pour objectif de sortir l'homme de la boucle. AutoML est généralement traité comme un problème de sélection d'algorithme / hyper-paramètre. Les approches existantes incluent l'optimisation Bayésienne, les algorithmes évolutionnistes et l'apprentissage par renforcement. Parmi eux, auto-sklearn, qui intègre des techniques de meta-learning à l'initialisation de la recherche, occupe toujours une place de choix dans les challenges AutoML. Cette observation a orienté mes recherches vers le domaine du meta-learning. Cette orientation m'a amené à développer un nouveau cadre basé sur les processus de décision Markovien (MDP) et l'apprentissage par renforcement (RL).
Après une introduction générale, mon travail de thèse commence par une analyse approfondie des résultats du Challenge AutoML. Cette analyse a orienté mon travail vers le meta-learning, menant tout d'abord à proposer une formulation d'AutoML en tant que problème de recommandation, puis à formuler une nouvelle conceptualisation du problème en tant que MDP. Dans le cadre du MDP, le problème consiste à remplir de manière aussi rapide et efficace que possible une matrice S de meta-learning, dans laquelle les lignes correspondent aux tâches et les colonnes aux algorithmes. Un élément de matrix S(i,j) est la performance de l'algorithme j appliqué à la tâche i. La recherche efficace des meilleures valeurs dans S nous permet d'identifier rapidement les algorithmes les mieux adaptés à des tâches données. Après avoir examiné le cadre classique d'optimisation des hyper-paramètres, nous introduisons une première approche de meta-learning, ActivMetaL, qui combine des techniques d'apprentissage actif et de filtrage collaboratif pour prédire les valeurs manquantes dans S. Nos dernières recherches appliquent RL au problème du MDP défini pour apprendre une politique efficace d'exploration de S. Nous appelons cette approche REVEAL et proposons une analogie avec une série de jeux pour permettre de visualiser les stratégies des agents pour révéler progressivement les informations.
Les principaux résultats de mon projet de thèse sont :
- Sélection HP / modèle : j'ai exploré la méthode Freeze-Thaw et optimisé l'algorithme pour entrer dans le challenge AutoML 2015-2016, obtenant la 3ème place du tour final.
- ActivMetaL : j'ai conçu un nouvel algorithme pour le meta-learning actif et l'ai comparé à d'autres méthodes de base sur des données réelles et artificielles. Cette étude a démontré qu'ActivMetaL est généralement capable de découvrir le meilleur algorithme plus rapidement que les méthodes de base.
- REVEAL : j'ai développé une nouvelle conceptualisation du meta-learning en tant que processus de décision Markovien et je l'ai intégrée dans le cadre plus général des jeux REVEAL. Avec un stagiaire en master, j'ai développé des agents qui apprennent (avec l'apprentissage par renforcement) à prédire le meilleur algorithme à essayer.
Le travail présenté dans ma thèse est de nature empirique. Plusieurs méta-données du monde réel ont été utilisées dans cette recherche. Des méta-données artificielles et semi-artificielles sont également utilisées dans mon travail. Les résultats indiquent que RL est une approche viable de ce problème, bien qu'il reste encore beaucoup à faire pour optimiser les algorithmes et les faire passer à l'échelle aux problèmes de meta-learning plus vastes.

Directrice de thèse
Mme Isabelle Guyon, Professeure, UPSud/INRIA Université Paris-Saclay, France

Co-encadrante de thèse
Mme Michèle Sebag, Dir. Recherche, CNRS Université Paris-Saclay, France

Membres de jury
M. Nicolas Thiéry, Professeur, LRI, Université Paris-Sud, France | Président
Mme Cécile Capponi, Maîtresse de Conférences HDR, Université d'Aix-Marseille, France | Rapporteur
M. Daniel Silver, Professeur, Acadia University, Canada | Rapporteur
M. Hugo Jair Escalante, Professeur, Instituto Nacional de Astrofisica, Optica y Electronica, Mexique | Examinateur
M. Joaquin Vanschoren, Professeur, Eindhoven University of Technology, Pays-Bas | Examinateur


-----------------
English
-----------------

Title
Meta-Learning as a Markov Decision Process

Summary
Machine Learning (ML) has enjoyed huge successes in recent years and an evergrowing number of real-world applications rely on it. However, designing promising algorithms for a specific problem still requires a huge human effort. Automated Machine Learning (AutoML) aims at taking the human out of the loop and develops machines that generate/recommend good algorithms for a given ML task. AutoML is usually treated as an algorithm/hyper-parameter selection problem, existing approaches include Bayesian optimization, evolutionary algorithms as well as reinforcement learning. Among them, auto-sklearn which incorporates meta-learning techniques in their search initialization, ranks consistently well in AutoML challenges. This observation oriented my research to the Meta-Learning domain, I then develop a novel framework based on Markov Decision Processes (MDP) and reinforcement learning (RL).
After a general introduction, my thesis work started with an in-depth analysis of the results of the AutoML challenge. This analysis then oriented my work towards meta-learning, leading me first to propose a formulation of AutoML as a recommendation problem, and ultimately to formulate a novel conceptualization of the problem as a MDP. In the MDP setting, the problem is brought back to filling up, as quickly and efficiently as possible, a meta-learning matrix S, in which lines correspond to ML tasks and columns to ML algorithms. A matrix element S(i,j) is the performance of algorithm j applied to task i. Searching efficiently for the best values in S allows us to identify quickly algorithms best suited to given tasks.
After reviewing the classical hyper-parameter optimization framework, I will introduce my first meta-learning approach, ActivMetaL, that combines active learning and collaborative filtering techniques to predict the missing values in S. Then, our latest research applies RL to the MDP problem we defined to learn an efficient policy to explore S. We call this approach REVEAL and propose an analogy with a series of toy games to help visualize agents' strategies to reveal information progressively.
The main results of my Ph.D. project are:
- HP/model selection: I have explored the Freeze-Thaw method and optimized the algorithm to enter the AutoML 2015-2016 challenge, achieving 3rd place in the final round.
- ActivMetaL: I have designed a new algorithm for active meta-learning and compared it with other baseline methods on real-world and artificial data. This study demonstrated that ActivMetaL is generally able to discover the best algorithm faster than baseline methods.
- REVEAL: I developed a new conceptualization of meta-learning as a MDP and put it into the more general framework of REVEAL games. With a master student intern, I developed agents that learn (with reinforcement learning) to predict the next best algorithm to be tried.
The work presented in my thesis is empirical in nature. Several real-world meta-datasets were used in this research, each of which corresponds to one score matrix S. Artificial and semi-artificial meta-datasets are also used. The results indicate that reinforcement learning is a viable approach to this problem, although much work remains to be done to optimize algorithms to make them scale to larger meta-learning problems.

PhD supervisor
Mme Isabelle Guyon, Professor, UPSud/INRIA Université Paris-Saclay, France

PhD co-advisor
Mme Michèle Sebag, Research Director, CNRS Université Paris-Saclay, France

Thesis Committee
M. Nicolas Thiéry, Professor, LRI, Université Paris-Sud, France | President
Mme Cécile Capponi, Maîtresse de Conférences HDR, Université d'Aix-Marseille, France | Rapporteur
M. Daniel Silver, Professor, Acadia University, Canada | Rapporteur
M. Hugo Jair Escalante, Professor, Instituto Nacional de Astrofisica, Optica y Electronica, Mexico | Examiner
M. Joaquin Vanschoren, Professor, Eindhoven University of Technology, Netherlands | Examiner