Il y a exactement vingt-cinq ans, une nouvelle discipline se détachait du substrat académique déjà bien établi de l'Intelligence Artificielle au sein duquel elle avait mûri. Résultat de deux ateliers de travail organisés au tout début des années 1980, la publication du livre de référence Machine Learning par les fondateurs de la spécialité, Ryszard Michalski (1937-2007), Jaime Carbonell et Tom Mitchell et le lancement d'un nouveau journal scientifique du même nom en 1986, signalaient la maturité et l'homogénéité des travaux de nombreuses équipes universitaires.
C'est dans ce contexte d'émergence enthousiaste d'un programme original de recherche, qu'un spécialiste de la combinatoire et de la complexité algorithmique, Leslie Valiant, faisait paraître un article théorique dont la portée devait s'étendre sur plusieurs décennies, Une théorie de « l'apprenable » (A Theory of the Learnable). Un examen rapide de la liste impressionnante de ses publications montre d'ailleurs que Valiant a certainement l'art de ciseler les titres de ses papiers scientifiques : On Time versus Space, Negation can be exponentially powerful, Optimally universal parallel computers, Rationality, Cognitive computation, Circuits of the Mind, Robust Logics, Knowledge infusion, Evolvability et le borgésien Accidental algorithms ! Sa contribution à l'informatique ne se limite cependant pas aux seuls algorithmes d'apprentissage automatique mais se ramifie au calcul parallèle (A scheme for fast parallel communication) et aux architectures matérielles (General purpose parallel architectures). C'est ce chercheur tout à fait original, aux travaux fondateurs, enseignant à Harvard depuis plus de vingt ans, que le prestigieux Prix Turing vient récompenser pour 2010.
Dès la naissance de la discipline du Machine Learning, Valiant lui donnait donc un fondement théorique novateur, connu depuis sous le nom singulièrement curieux d'algorithmes probablement approximativement corrects (PAC). L'idée directrice étant de se concentrer sur l'amélioration de l'efficacité (en temps et mémoire) des algorithmes d'apprentissage automatique, l'approche PAC s'attache à donner une caractérisation approximative, mais précise, des concepts à apprendre et mesure (pour l'améliorer) la probabilité d'atteinte de la cible, dans cette marge d'approximation, par l'algorithme en question. Saluée comme révolutionnaire à l'époque, cette conception théoriquement fondée a démontré depuis sa validité pratique dans de nombreuses applications dans autant de domaines industriels.
Pour retracer à grandes lignes l'évolution du programme de recherche du Machine Learning, de relativement informels qu'étaient les premiers travaux de recherche avant Valiant — souvent des exposés commentés de quelques applications d'une méthode d'apprentissage à de petit jeux de données ou à des problèmes volontairement simplifiés — les papiers, postérieurs à la théorie de Valiant, se caractérisèrent par un formalisme plus recherché. L'idée centrale qui s'imposait alors, déjà proposée par Herbert Simon (1916-2001) dans Why Should Machines Learn? (encore un titre somptueux !), voulait que l'objectif de l'apprentissage soit l'amélioration effective de l'exécution d'une tâche donnée. Dès lors toute recherche algorithmique sur l'apprentissage automatique devait également prendre en compte une ou plusieurs tâches et un système d'exécution de ces tâches, pompeusement nommé système performatif (performance system). Un second courant, venu des recherches expérimentales menées en psychologie, porté par Dennis Kibler et Pat Langley dans Machine Learning as an Experimental Science, précisait ensuite les techniques d'expérimentation contrôlée à appliquer aux problèmes d'apprentissage automatique.
Ce mouvement expérimental, auquel la constitution progressive par David Aha d'un référentiel de jeux de données standardisés, le Machine Learning Repository de UC Irvine, a également fortement contribué en permettant de comparer les algorithmes sur les mêmes jeux de données, était aussi caractérisé par l'accent mis sur les méthodes dites symboliques. Par contraste avec les méthodes numériques, elles visaient à apprendre des connaissances dont la représentation naturelle était directement intelligible : règles de production, arbres de décision, formules de logique, etc.
Mais au fur et à mesure que croissait l'accent mis sur l'importance du système performatif, les études de Machine Learning visèrent de plus en plus large et inclurent progressivement toute méthode permettant, avec l'expérience, d'améliorer la performance. Ainsi d'autres idées issues de la reconnaissance des formes et des images, des approches probabilistes et statistiques, ou à base de cas (instance-based learning) poussèrent petit à petit les idées de Valiant vers le fond de la scène. Paradoxalement, la formalisation des jeux de données aidant, la variété des méthodes employées entraînait également une simplification des tâches auxquelles elles étaient appliquées — ce qui en facilitait certes la comparaison, mais donnait une importance hors de proportion aux tâches de classification et de régression. Aujourd'hui encore, l'algorithme AdaBoost de Yoav Freund et Robert Schapire (1999) et la prolifération de ses déclinaisons, par exemple, a donné naissance à une branche entière de recherches très active sur ce qu'il est convenu d'appeler les systèmes collectifs d'apprentissage (Ensemble-Based Learning). Dans le même temps, la représentation des données et des connaissances apprises s'appauvrissait : les listes attribut-valeur et les formules du calcul propositionnel devenaient le modèle formel prépondérant dans les implémentations. Cette opacification progressive des connaissances reflétait aussi leur rôle décroissant dans l'élaboration et la mesure des algorithmes d'apprentissage automatique.
La reconnaissance actuelle de l'importance des travaux de Valiant jette un nouvel éclairage sur cette évolution, parfois radicale, par rapport aux premiers objectifs du Machine Learning. À l'heure ou l'hypercroissance des volumes de données liées au Web pose avec une nouvelle acuité la question de faire sens — courant de réflexion identifié sous la dénomination de Big Data et mené tambour battant, entre autres, par Microsoft, Google, et la communauté Hadoop — la théorie de Valiant prend alors un relief nouveau. Terrence Sejnowski du Salk Institute, dans son allocution Graeme Clark, hier encore, appellait de ses voeux à une intensification de la recherche sur les nouvelles architectures parallèles — matérielles et logicielles — pour percer la barrière calculatoire que représente encore le cerveau humain malgré le succès récent de Watson ou les 2,57 petaflops/s de Tianhe-1A.
Comme il y a vingt cinq ans, exactement les sujets de prédilection du Prix Turing 2010.
