Liva Ralaivola : « Identifier les caractéristiques des algorithmes d’apprentissage »

Vous travaillez dans le domaine de l’apprentissage, à la jonction entre mathématiques et informatique.

Liva Ralaivola : L’apprentissage automatique (le machine learning) réunit plusieurs communautés. C’est au départ une branche de l’intelligence artificielle, discipline qui trouve ses origines en informatique, et qui connaît des premières contributions importantes dès les années 40-50 avec les travaux de McCullogh et Pitts sur les neurones formels. À partir des années 1990, à la suite de l’avènement des « méthodes à noyaux », le domaine de l’apprentissage automatique a été investi par les mathématiciens. Le concept d’ « apprentissage statistique », qui commande l’usage de techniques relevant de la statistique mathématique et d’optimisation convexe, a pris une place prépondérante dans les travaux liés à l’apprentissage. 

Dans mon projet de recherche, je souhaite remettre la dimension informatique de l’apprentissage en avant. Je m’intéresse plus particulièrement à l’algorithmique qui peut être mise en œuvre, et aux structures de données discrètes qui peuvent être pertinentes dans des tâches d’apprentissage. J’imagine notamment que les algorithmes d’optimisation discrète ont intrinsèquement des vertus importantes pour la notion fondamentale de « généralisation ». Cette notion vise à ce qu’une intelligence artificielle, un prédicteur, qui a appris à partir d’un échantillon fini de données soit capable de se comporter correctement (c’est-à-dire de faire des prédictions justes) lorsqu’on lui fournit des données qui n’étaient pas présentes lors de la phase d’apprentissage. 

À quel type d’apprentissage vous êtes-vous intéressé ?

L. R. : J’ai concentré mon travail sur les aspects théoriques de l’apprentissage. Je me suis notamment beaucoup intéressé à l’apprentissage à partir de données dépendantes, en travaillant sur ce qu’on appelle les inégalités de concentration. Ces inégalités ont par exemple une utilisation directe pour le problème des bandits manchots. Imaginez un casino où vous avez 10 machines à sous, chacune ayant une probabilité de gain différente. Comment trouver la machine qui vous fera gagner le plus ? Quelle est la stratégie de jeu qui vous permet de maximiser vos gains ? Ces questions amènent naturellement à ce qu’on appelle le « dilemme exploration/exploitation ». En effet, vous pouvez commencer à jouer avec deux machines, comparer les gains avec chacune d’elle, puis vous concentrer sur celle qui vous rapporte le plus : ce serait une stratégie d’exploitation, où vous exploitez au maximum l’information partielle obtenue. Mais rien ne vous dit qu’il n’y a pas une autre machine qui a une probabilité de gain plus élevée : pour la trouver, il est naturel de miser sur de nouvelles machines, ce qui constitue une stratégie d’exploration. L’objectif d’un joueur est de savoir comment répartir l’effort entre les processus d’exploitation et d’exploration. 

Les inégalités de concentration servent de base à l’élaboration de stratégies « optimales » de jeu. Travailler sur des inégalités de concentration où les tirages dépendent les uns des autres permet d’étudier la situation où les récompenses des machines à sous ont une influence les unes sur les autres. Ces algorithmes de bandits ont des multitudes d’applications, notamment dans le cas du jeu de Go, la recommandation de films, mais aussi dans le cas moins poétique du placement publicitaire sur internet. 

Quels sont les prochaines thématiques auxquelles vous allez vous consacrer ?

L. R. : Il y en a plusieurs. Pour pousser l’exemple précédent encore un peu plus loin, je travaille sur un problème de bandits manchots où l’on estime que l’on ne tire pas un seul bras de machine, mais deux à la fois, voire plus, afin d’obtenir une information sur le « meilleur » bras. Mais je m’intéresse aussi au cas où il n’y a pas de comparaison possible et qu’il n’existe pas de meilleur bras. Soit parce que le niveau est équivalent : pour des films ce serait comme comparer le Parrain 1 et 2. Soit parce que les données ne sont pas comparables, comme Le Parrain et Star Wars. Dans le cas de ces ensembles partiellement ordonnés (qui conjuguent à la fois des données comparables et non comparables), comment aborder l’apprentissage ? Il s’agira pour moi d’étudier comment des structures de données dédiées à la manipulation d’objets partiellement ordonnés (les Poset pour Partially Ordered Sets) peuvent se marier avec des inégalités de concentration bien calibrées. 

Un autre point de recherche qui m’intéressera concerne la manière dont la complexité, c’est-à-dire le temps et la difficulté que demande l’exécution d’un algorithme, a une influence directe sur le pouvoir de généralisation des prédicteurs appris. Je travaillerai notamment à voir comment la complexité en moyenne d’algorithmes d’apprentissage peut directement être prise en compte, de manière théorique et pratique, dans cette capacité de généralisation – c’est une démarche qui s’écarte de ce qui est habituellement fait, où la complexité dans le pire des cas est plutôt retenue comme paramètre important.