Uncategorized
28/10/2015

Une petite histoire du Machine Learning


Temps de lecture : 19 minutes
Quantmetry.com : Une petite histoire du Machine Learning

Le Machine Learning (ML) (1) a émergé dans la seconde moitié du XXème siècle du domaine de l’intelligence artificielle et correspond à l’élaboration d’algorithmes capables d’accumuler de la connaissance et de l’intelligence à partir d’expériences, sans être humainement guidés au cours de leur apprentissage, ni explicitement programmés pour gérer telle ou telle expérience ou donnée spécifique.

LES DÉBUTS DE L’INTELLIGENCE ARTIFICIELLE

L’intelligence artificielle (IA) est l’une des disciplines scientifiques et d’ingénierie les plus récentes et les plus florissantes. Les pionniers de l’IA ont commencé leurs travaux vers la fin de la seconde guerre mondiale. En 1956, dix pionniers de la recherche américaine en théorie des automates, des réseaux de neurones  et de l’intelligence se sont réunis pour un workshop de deux mois à Dartmouth College : J. McCarthy (Dartmouth), Minsky (Princeton), C. Shannon (Bell Labs/MIT), N. Rochester (IBM), T. More (Princeton), A. Newell (Carnegie Tech), H. Simon (Carnegie Tech), A. Samuel (IBM), R. Solomonoff (MIT), O. Selfridge (MIT). C’est lors de ce workshop, que le terme d’IA est apparu : l’IA était officiellement née.

Rapidement, l’IA a suscité beaucoup de débats parmi les spécialistes quant à l’approche à adopter. Plusieurs écoles ont vu le jour. Les comportementalistes cherchaient à construire des IA capables de penser ou agir comme les humains. Les rationalistes s’orientaient vers une vision rationnelle des IA qui devaient selon eux produire des fonctionnements et des raisonnements rationnels, plutôt que d’essayer à tout prix d’imiter le cerveau humain.

Les rationalistes ont donc d’abord tenté de construire des programmes capables de résoudre n’importe quel problème décrit par une notation logique. Néanmoins, la traduction d’une connaissance complexe ou informelle dans le cadre de la logique est très ardue. D’autre part, construire des IA capables de produire un raisonnement et un comportement rationnel suppose le traitement exact de nombreux paramètres : une capacité de calcul inaccessible à l’époque.

Dans l’approche comportementaliste, le test de Turing (très récemment revenu sur le devant de la scène avec Eugene Goostman (2), ou certains films médiatisés comme Ex machina (3) a été pensé pour fournir une définition de l’intelligence. Une IA passe le test de Turing si un humain n’est pas capable de déterminer dans une conversation si l’IA est un humain ou un ordinateur. Une telle prouesse suppose un certain nombre de capacités : traitement automatique de la langue humaine (Natural Language Processing), représentation (stockage ordonné) des connaissances et des expériences passées, facultés de raisonnement automatique et du ML, c’est-à-dire une capacité d’adaptation en fonction des circonstances. Cet ensemble de facultés nécessaires pour une intelligence sont particulièrement difficiles à développer simultanément dans une IA.

A ce jour, on ne peut pas dire qu’une IA ait encore passé le test de Turing de façon incontestable, même si la perspective devient plus plausible avec les avancées scientifiques et technologiques.

Le tableau 1 montre une comparaison des capacités d’un supercalculateur, d’un PC et d’un cerveau humain. Chaque génération de hardware représente une amélioration de la vitesse et de la capacité de calcul, ainsi qu’une baisse des coûts. Jusque vers 2005, les constructeurs amélioraient surtout la vitesse de calcul, puis on a commencé à multiplier le nombre de CPUs. Actuellement, la tendance est à la parallélisation massive des calculs et du stockage qui offre des perspectives impressionnantes de puissance.

LA SINGULARITÉ

Le concept de singularité technologique contient l’idée, qu’à partir d’un point de l’évolution humaine (la singularité), les IA dépasseront les performances humaines de raisonnement d’une part et les capacités d’évolution de l’humanité d’autre part. Les progrès seraient alors portés par des IA que la société humaine ne serait plus capable de contrôler. L’idée remonte aux années 1950 avec John von Neumann et a été débattue par I. J. Good, V. Vinge (4) ou  R. Kurzweil (5). On la retrouve fréquemment dans la culture populaire avec 2001 Odyssée de l’espace, Terminator, Minority Report, Matrix, et plus récemment Her ou encore Transcendance.

La pertinence de ce concept est encore très contestée et débattue dans la communauté scientifique aujourd’hui. Nous nous contentons ici de mentionner l’existence du concept, car il est intéressant de le connaître, mais sans engager de débat.

PREMIÈRES AVANCÉES

Les premiers travaux d’IA reconnus comme tels ont été menés par McCulloch et Pitts en 1943 avec le premier modèle de neurones artificiels : chaque neurone est caractérisé comme étant ouvert ou fermé et a la capacité de s’ouvrir en réponse à une stimulation par un nombre suffisant de neurones voisins afin de transmettre un signal. Un autre pionnier de l’IA, Hebb, a proposé en 1949 un système de neurones où les connections entre neurones sont pondérées avec des règles de modification des poids constituant un apprentissage.

La période qui a suivi jusque dans les années 60 a été ponctuée de grandes avancées et de grands espoirs (6) : le « General Problem Solver » de Newell et Simon, qui tentait d’imiter les méthodes humaines de résolution des problèmes ; le « Geometry Theorem Prover », de Gelernter, capable de prouver des théorèmes mathématiques difficiles ; les premiers programmes de jeu d’échecs (A. Samuel) ; la création de Lisp                  (J. McCarthy), devenu par la suite le langage de programmation dominant pour les IA ; le « Advice Taker » de McCarthy, un programme hypothétique construit pour utiliser la connaissance acquise afin de résoudre des problèmes : la première apparition des principes de représentation formelle et explicite des connaissances et la manipulation de cette représentation par des processus de déduction.

Bien des personnes, incluant des responsables de programmes gouvernementaux se sont alors enflammées en imaginant des IA capables d’atteindre les capacités du cerveau humain.

UN COUP D’ARRÊT À L’IA

Après l’emballement des années 50, les années 60 ont ramené plus de réalisme et de pragmatisme dans le domaine. D’abord, on s’est rendu compte que la plupart des IA fonctionnaient surtout par manipulations syntaxiques simples et non par des raisonnements véritablement basés sur la connaissance. Dans le cas de la traduction par exemple, la machine a besoin d’avoir une compréhension fine du contexte pour traduire sans ambiguité. Les IA échouaient à traduire des textes même simples. Outre la traduction, beaucoup de problèmes (théorèmes mathématiques, raisonnements par déduction, problèmes complexes impliquant plusieurs sous tâches) s’avéraient impossibles à résoudre en raison du nombre de paramètres en jeu.

Enfin, les structures de réseaux de neurones proposées étaient beaucoup trop limitées en taille et en capacité de représentation de la connaissance pour espérer produire un comportement intelligent. En 1969, Minsky et Papert ont démontré que les perceptrons (des modèles simples basés sur les travaux de McCulloch et Pitts) ne pouvaient construire qu’une représentation très minime : ils n’étaient par exemple pas capables d’implémenter la fonction XOR (7) qui permet de reconnaître si deux inputs sont différents.

La perspective de construire des systèmes plus complexes était en décalage avec la quantité de données disponibles et le stockage (c’est-à-dire la représentation des connaissances) nécessaire. D’autre part, la puissance de calcul des ordinateurs de l’époque ne permettait pas de mettre en oeuvre un apprentissage de ces modèles. Les espoirs placés dans l’IA ont donc été considérablement déçus et beaucoup de programmes de recherche ont été arrêtés. Ceci a amené un ralentissement brutal des investissements dans la recherche, en particulier celle axée sur les réseaux de neurones et cherchant à reproduire les raisonnements humains.

PRAGMATISME ET MODESTIE : L’ÉMERGENCE DU MACHINE LEARNING

Entre les années 70 et 80, les efforts se sont portés sur des systèmes d’expertise restreints à des domaines spécifiques comme l’analyse en chimie, le diagnostic médical, les systèmes experts de l’industrie, et les robots ou logiciels très spécialisés.

Des travaux sur les modèles de Markov, les avancées théoriques et techniques sur les simulations Monte Carlo, et le développement du formalisme des réseaux Bayésien ont ponctué cette période de vingt ans, avec une utilisation dans des domaines spécifiques avec relativement peu d’échanges interdisciplinaires. La fin des années 80 a également vu le retour des réseaux de neurones, avec la (ré)-invention de l’apprentissage par backpropagation et son application à des problèmes spécifiques comme la reconnaissance de caractères. Mais il faudra encore attendre le milieu des années 2000 pour voir des succès sur des problèmes plus complexes et dans des domaines plus larges.

L’émergence du ML en tant que discipline à part entière s’inscrit dans cette dynamique de pragmatisme et de modestie ; elle a eu lieu dans les années 90 avec la volonté de s’attacher à résoudre des problèmes très concrets et plus humbles, en lien direct avec les données à disposition.

Parallèlement à cela, l’arrivée d’Internet a permis d’établir des collaborations plus fortes entre les différents groupes de recherche, une communication plus rapide des résultats et surtout la possibilité de reproduire les expériences en utilisant des dépots de données test et de codes. L’interdisciplinarité avec l’ingénierie et l’informatique a également permis d’avancer beaucoup plus vite sur ces systèmes. Avec une approche scientifique plus systématique, les experts ont pu concentrer leurs efforts à améliorer ensemble les théories et les modèles existants et prometteurs, plutôt que de fonctionner de manière isolée.

Notons que c’est environ à ce moment de l’histoire que les mathématiques et plus particulièrement les statistiques ont été réintroduites dans le développement des aspects théoriques et appliqués du ML.

ENTRÉE DU BIG DATA

Il faut aussi noter l’importance de l’arrivée du Big Data : la disponibilité d’ensembles de plus variés de données massives et l’augmentation des capacités de calcul et de stockage.

Le développement des technologies Big Data a permis de dépasser des limites importantes du ML : l’absence d’une quantité suffisante de données ne permet pas d’entraîner efficacement un algorithme de prédiction. Par conséquent, en l’absence de telles données, on ne dispose pas d’expérimentations probantes ; il est alors plus difficile de développer les fondements théoriques d’un algorithme de ML.

Le Big Data pose également des challenges d’ordre théorique pour le ML, comme les problèmes de grandes dimensions : le croisement de nombreuses sources de données diluent fortement l’information. On augmente ainsi le nombre de variables à explorer, mais pas le nombre d’exemples disponibles.

QU’EST-CE QUE LE ML ?

Le ML est une sous-partie de l’intelligence artificielle qui s’attache a créer des machines qui se comportent et opèrent de manière intelligente ou qui simulent cette intelligence.

L’IA n’implique pas forcément un apprentissage de la machine. Par exemple dans le cas des machines qui jouent aux échecs. : une IA ne saura pas faire face à une stratégie nouvelle d’un joueur humain en apprenant de l’expérience pour adapter son comportement, à moins d’avoir été conçue dans le cadre du ML.

Pour qu’une machine apprenne et s’adapte automatiquement, la connaissance qu’elle peut extraire de ses expériences doit être stockée sous une certaine forme, de façon à pouvoir être utilisée dans un but précis. En général, le but est de prédire le futur (un comportement, un nombre, etc.), mais une machine peut également être construite pour générer artificiellement de nouvelles données (machines génératives) ressemblant statistiquement aux données originales, ou bien pour détecter des schémas de fonctionnement (causalités, structure d’un réseau, etc.).

Comme nous l’avons mentionné plus haut, le ML a beaucoup puisé dans les mathématiques et les statistiques. Classiquement, les statistiques s’attachent à permettre une compréhension globale des données : quelles sont les caractéristiques d’une variable (minimum, maximum, moyenne) ? De façon plus avancée, quelle est la distribution statistique ? Peut-on modéliser le processus de génération des données en essayant d’extraire le bruit contenu dans les données ? Le modèle le plus simple est la régression, très utilisée dans de nombreux domaines. Entraîner (faire apprendre) un modèle de régression c’est faire du ML. On peut donc faire remonter le machine learning au XVIIème siècle avec Legendre et Gauss et leur méthode des moindres carrés.

Le ML peut être vu comme l’ensemble des méthodes permettant de déterminer la meilleure manière de modéliser les données. Parmi ces méthodes, la plus centrale et la plus importante est l’apprentissage. L’apprentissage consiste, pour un modèle donné, à choisir les meilleurs paramètres possibles pour décrire les données. Pour une régression simple, il s’agit de choisir le meilleur couple a, b (voir figure 1). Dans ce cas, la connaissance acquise par l’expérience (les différents échantillons de données sont autant de micro-expériences), est stockée dans ces deux coefficients a et b. Un modèle plus complexe stocke sa connaissance dans un nombre beaucoup plus grand de coefficients pouvant dépasser le million voire le milliard (pour les réseaux de neurones complexes par exemple), mais le principe est le même : le ML permet à une machine (le modèle, simple ou complexe) d’apprendre et de stocker sa compréhension du monde.

Les modèles et leurs procédures d’apprentissag