Apprentissage automatique (Machine Learning)

Article
04/24/2013

L’apprentissage automatique, c’est la capacité d’un ordinateur à apprendre sans avoir été explicitement programmé.

Arthur Samuel

Hier matin, en me rendant dans les locaux de Microsoft France où se déroule au Centre de conférence ces 23 et 24 avril le Microsoft Research Machine Learning Summit - une conférence au sommet autour du Big Data et du « Machine Learning » à destination d’un public de chercheurs et universitaires venus de toute l’Europe -, un panneau au pied du pont du Garigliano indiquait :

Périphérique intérieur => fluide
Périphérique extérieur => 6 min Porte d’Orléans

De là est partie la (petite) réflexion suivante : si nous changeons le second affichage (c.à.d. Périphérique extérieur) par ceci :

Périphérique intérieur => fluide
L’autre : 6min Porte d’Orléans

Nous comprenons que l’affichage, « l’autre » en l’occurrence, correspond au périphérique extérieur. Cette relation, nous la faisons naturellement et sans réfléchir au préalable.

Des associations comme celle-ci nous en faisons régulièrement et si, par exemple, nous changeons le sujet en prenant comme phrase « La voiture est en panne, je prends l’autre », l’autre correspond cette fois à une deuxième voiture implicite.

Le mot « autre » est associé dans ces deux exemples à des entités complètement différentes. Pourtant notre cerveau arrive à faire la déduction naturellement grâce au contexte.

Le premier exemple sur le périphérique décrit deux types : intérieur et extérieur. Ce sont des termes opposés c’est-à-dire que l’alternative à intérieur est extérieur.

Comment le sait-on ? Cela fait partie de notre cadre de référence qui est constitué d’informations et d’expériences dépendantes de l’environnement dans lequel nous évoluons et de l’apprentissage que nous avons reçu.

Nous possédons donc déjà un cadre de référence qui nous permet de faire des déductions, de prendre des décisions en fonction du contexte. Par contre, si nous prenons le cas d’un enfant, plus il sera jeune, moins il déduira le déroulement d’actions car sa phase d’apprentissage sera moindre.

Principes de fonctionnement

Pour une machine, le fonctionnement est similaire. Il faut partir du principe qu’elle n’a pas encore de cadre de référence et qu’il va falloir qu’elle apprenne pour se constituer une mémoire qui, à son tour, l’aidera à faire un choix sur une situation avec un contexte particulier. Plus la machine possédera de comportements différents en fonction des contextes, plus elle répondra avec pertinence.

Le temps de réflexion augmentera en fonction du nombre de situations vécues et des comportements effectués ce qui n’est pas toujours amusant. En effet, si l’ordinateur prend trois jours à se décider pour déplacer le cavalier droit aux échecs, l’utilisateur aura déjà fermé le programme.

Quand l’ensemble de tous les comportements devient trop important, il augmente au fil du temps pour affiner la pertinence de l’algorithme. Pour pallier à ce problème complexe, il est nécessaire de séparer les rôles. On va donc créer un modèle qui sera mis à jour par un programme indépendant. Ce modèle simplifie la complexité précédente car il ne s’agrandit pas, il s’ajuste simplement. Vient ensuite, l’algorithme principal qui est de type adaptif et utilise le modèle pour s’auto-améliorer.

Comment est constitué un modèle ?

Il est bien souvent composé de probabilités Ainsi, dans le cas d’algorithmes de prédiction, une action donne un état, auquel correspondent plusieurs actions nouvelles possibles. Chaque action possède une probabilité de se produire, associée à l’état courant. Un des modèles régulièrement utilisé est la « chaîne de Markove ».

Vous avez dit chaîne de Markov ?

Une définition simpliste nous suffira pour aborder ici ce modèle : il s’agit de décrire sous forme d’un graphe une série d’états (représentées par des nœuds) et reliées par des probabilités (qui sont les arrêtes). Lorsque nous sommes dans un état, il existe une certaine probabilité pour être dans un deuxième état ou un troisième. A partir de ce constat, nous pouvons écrire une équation prédisant l’état du système dans 5 minutes.

A titre d’illustration, la chaîne de Markov ci-dessous indique que nous avons 9 chances sur 10 de faire l’activité « Autre activité » lorsque nous sommes dans l’état de départ, alors qu’il y a 1 chance sur 10 pour que nous soyons directement amenés à « l’activité de fin ». La somme de toutes les probabilités étant égale à 1.

Pour le cas où nous sommes en train de faire l’autre activité, nous pouvons finir par l’activité de fin (7/10), ou bien recommencer au départ (3/10).

Un exemple plus détaillé et bien expliqué - enfin je trouve – est disponible sur la page Wikipédia dédiée à la chaîne de Markov, à savoir Doudou le hamster.

Une autre variante consiste à ajouter un facteur décisionnel à chaque état ; on appelle cela un processus de Markove décisionnel (MDP). On l’utilise pour que l’algorithme ait la capacité de faire un choix. Par la suite, une fois le graphe construit, on peut aisément en déduire des équations transformées en calcules matriciels. Et les matrices, les ordinateurs savent très bien les manipuler ;)

Revenons à nos hamsters. Nous parlions de constitutions de modèle. Il peut aussi se trouver sous forme d’arbre (binaire, quelconque, etc.) ou encore de courbe, pertinent lorsque l’analyse se fonde sur des données temporelles.

Une fois que notre algorithme a appris à apprendre, il fonctionne en autonomie.

Apprentissages et élaboration du modèle

La première phase pour nos algorithmes d’apprentissage automatique doit donc être la classification des données d’apprentissage. Cette phase est un « pré mâchage » de l’information qui sera utilisée pour constituer le modèle. Elle est étiquetée pour être associée à une classe précise. Il existe plusieurs systèmes pour la phase d’apprentissage.

Apprentissage supervisé

Un modèle de classement est soumis par une personne, puis l’information du jeu de données est classée suivant celui-ci. Un expert est en charge de construire le modèle de classement qui contient des étiquettes (tag) à placer sur la donnée. Le professeur de l’université de Stanford Andrew Ng l’explique dans son cours Machine Learning (CS 229) avec l’exemple suivant (Module 1).

Supposons que nous collections des statistiques sur la taille de maisons au mètre carré et le prix correspondant. Nous avons donc spécifié que, dans notre jeu de données, il y a des maisons avec un attribut « surface » et un autre « prix ». Nous créons le graphique ci-dessous :

Les points bleus correspondent aux maisons, la ligne rouge représente la moyenne. Si nous voulons connaitre le prix pour une maison de surface 80 m², l’algorithme va en déduire grâce au jeu de données que le prix sera de l’ordre de 115 000 €. (Vous l’aurez deviné, ces prix de l’immobilier ne correspondent pas à ceux pratiqués sur Paris…)

Il est possible de définir plus de deux critères (la surface et le prix) ; ce qui conduit à faire évoluer le graphique ci-dessus vers un graphique multidimensionnel. Le graphique ci-dessus modélise un problème connu sous le nom de problème de régression (faisant référence au modèle de régression linéaire en statistique).

Apprentissage non-supervisé

Comme son nom l’indique, il est l’opposé du premier. Dans le premier, l’apprentissage s’effectue de manière subjective c’est-à-dire qu’une personne décrit au préalable quels critères existent dans son jeu de données à analyser et classer. Dans cet apprentissage ci, l’algorithme ne possède pas d’étiquette : il est autodidacte. Il va procéder par regroupement en cherchant les données similaires. Il est très intéressant d’utiliser cette technique lorsque vous ne savez pas ce que vous cherchez. Typiquement quand vous voulez faire éclore quelque chose qui ne vous viendrait pas à l’esprit. Ce type d’apprentissage est aussi appelé « clustering », qui signifie « groupement ».

Pour l’exemple, on l’utilise dans un traitement d’image particulier, qui sélectionne les pixels similaires et en déduit qu’ils sont liés à un objet précis. Une reconstitution 3D à partir d’une photo peut être réalisée ensuite par ce biais (on appelle ce domaine la « Computer Vision »).

Dans l’illustration ci-dessous, un algorithme de clustering a permis de regrouper les pixels par région et d’en séparer les différents composants. D’autres algorithmes sont ensuite utilisés pour recréer une projection en trois dimensions.

Une des bibliothèques couramment utilisée dans ce domaine (à savoir le computer vision) est OPenCV (Open Source Computer Vision) disponible sur la forge GitHub. (Un tutoriel est disponible ici pour une utilisation avec Visual Studio 2012).

Apprentissage par renforcement

Dans le cas présent, l’algorithme apprend de l’environnement dans lequel il évolue. Ce type d’apprentissage tente de concevoir une stratégie la plus optimisée possible. Le système fonctionne avec des récompenses que renvoie l’environnement à celui-ci. Ces récompenses peuvent être encourageantes, ou punitives.

Un autre exemple que donne le professeur Andrew Ng dans son cours Machine Learning (CS 229) est le dressage d’un chien. Lorsque notre chien est en phase de dressage, nous allons lui apprendre ce que nous voulons de lui quand nous lui disons « couché ! ». S’il ne le fait pas correctement, on lui dit « mauvais chien », s’il le fait correctement c’est un « bon chien ». ;)

Le principe de fonctionnement pour l’algorithme de type renforcement est le même que pour le chien. Il va donc s’améliorer au fur et à mesure que l’environnement lui donne des récompenses.

Domaines d’application

L’apprentissage automatique est très utilisé, beaucoup plus qu’on ne le croit de prime abord :

Par exemple avec l’utilisation de notre mobile favori pour taper du texte, les suggestions de mots sont produites par des algorithmes utilisant principalement des chaines de Markov avec un graphe de type N-Gramme.
La reconnaissance manuscrite utilise un algorithme de reconnaissance de forme et un processus Markovien pour la reconnaissance de langage naturel. Les deux algorithmes combinés contribuent à améliorent fortement les performances et l’efficacité.
La reconnaissance vocale, en particulier l’isolation de la voix par rapport à un environnement bruyant, utilise un algorithme d’apprentissage non-supervisé constitué de réseaux neuronaux (un modèle conçu à la manière d’un cerveau humain).

Ce ne n’est qu’un rapide aperçu de ce qui existe déjà grâce au domaine de l’apprentissage automatique. Toutes ces fonctions se trouvent maintenant dans nos téléphones intelligents (smartphone).

Mais aujourd’hui, avec des architectures de type Big Data, un nouvel horizon s’ouvre au « Machine Learning » comme cela a été évoqué lors de l’édition 2013 des Microsoft TechDays : Bienvenue dans l'océan numérique (KEY203).

Le « Machine Learning » constitue donc une vraie révolution dans le logiciel : probabilités et statistiques sur les masses de données permettent au logiciel « d’apprendre » et non seulement calculer. Nouvelle frontière, nouvelle façon de penser le logiciel et de le programmer, c’est une révolution qui replace la « Big Science » au cœur de l’innovation. Nous aurons très prochainement l’occasion de revenir sur la conférence Microsoft Research Machine Learning Summit .

Big Data et « Machine Learning »

Avec l’arrivée de Hadoop, nous l’avons vu à l’occasion de précédents billets, fidèles lectrices et lecteurs de ce blog, un écosystème de Frameworks en sus s’est rapidement constitué. Et donc rapidement, l’apprentissage automatique a fait son apparition dans cet écosystème comme la puissance offerte par Hadoop crée une opportunité au domaine sans précédent.

En effet, les algorithmes de « Machine Learning » et d’intelligence artificielle en général sont bien souvent très gourmands en ressources de calcul et prennent dès lors beaucoup de temps à s’exécuter. Néanmoins des optimisations sont régulièrement apportées sur ces algorithmes, mais elles sacrifient la précision contre le temps.

Apache Mahout est la réponse à la question (celle que vous vous êtes posée intérieurement). C’est un projet Apache, comme Hadoop, à ceci près qu’il n’est pas encore en version finale. Le projet consiste en un entrepôt d’algorithmes d’apprentissage automatique, tous portés afin de s’exécuter sur Map/Reduce. Une vingtaine d’algorithmes sont déjà portés sur le paradigme ; ce qui suffit pour la très grande majorité des problèmes.

En voici quelques-uns.

Pour ce qui est du contexte d’apprentissage supervisé :

Régression logistique (SGV) . Son domaine de prédilection est celui de la prédiction de probabilité d’apparition d’évènements comme par exemple dans le domaine de la fraude bancaire ou encore dans celui de la publicité pour le ciblage de clients fidélisables.
Classification Bayésienne. Une utilisation courante de notre boîte aux lettres électronique nous amène à utiliser un programme basé sur cet algorithme. Les filtres de spam sont en fait des règles de classification qui servent à l’algorithme bayésien contenu dans l’agent anti-spam pour séparer les « bons courriels des mauvais ».
Machine à vecteurs de support (SVM) . Il s’agit d’un ensemble de techniques destinées à résoudre des problèmes de discrimination (prédiction d’appartenance à des groupes prédéfinis) et de régression (analyse de la relation d’une variable par rapport à d’autres).
Réseau neuronaux. A l’inverse des algorithmes de déduction, ce dernier est un algorithme de type induction c’est-à-dire que, par le biais d’observations limitées, il essaie de tirer des généralisations plausibles. C’est un système basé sur l’expérience : il se constitue une mémoire lors de sa phase d’apprentissage (qui peut être aussi non-supervisée) que l’on appelle entrainement.
Forêts d’arbres décisionnels (Random Forest) . C’est une application de graphe en arbres de décision permettant ainsi la modélisation de chaque résultat sur une branche en fonction de choix précédents. On prend ensuite la meilleure décision en fonction des résultats qui suivront. On peut considérer cela comme une forme d’anticipation.
Le Boosting. Il s’agit d’une méthode de classification émettant des hypothèses qui sont au départ de moindre importance. Plus une hypothèse est vérifiée, et plus son indice de confiance augmente et donc elle prend plus d’importance dans la classification.

Et pour le contexte d’apprentissage non-supervisé :

K-moyennes (KMeans) . KMeans est un algorithme de partitionnement des données en K nombre de groupes. Il est utilisé notamment dans la bibliothèque OpenCV précédemment mentionnée vis-à-vis du domaine de la « computer vision ». Dans Mahout, on l’utilise typiquement afin de déterminer quelle suggestion peut être faite à un utilisateur en fonction des préférences que d’autres utilisateurs similaires ont eues (utilisateurs du même groupe).
Fuzzy KMeans. Il s’agit d’une variante du précédent algorithme proposant qu’un objet ne soit associé qu’à un seul groupe.
Espérance-Maximisation (EM) . Comme on peut le deviner, cet algorithme utilise des probabilités pour décrire qu’un objet appartient à un groupe. Le centre du groupe est ensuite recalculé par rapport à la moyenne des probabilités de chaque objet du groupe.
Regroupement hiérarchique. Deux sous-algorithmes en découlent, à savoir d’une part le « bottom up » qui a pour fonction d’agglomérer des groupes similaires, donc en réduire le nombre (plus lisible) et d’en proposer un ordre hiérarchique, et d’autre part, le « top down » qui fait le résonnement inverse en divisant le premier groupe récursivement en sous-ensembles.

Nous présentons ici les principaux algorithmes rapidement dans la mesure où ce billet a simplement vocation à introduire le sujet. Nous aurons l’occasion d’y revenir à l’occasion de prochains billet. Ceci étant, dans l’intervalle, rien ne vous empêche d’aller plus loin dans vos recherches. Nous ne serions d’ailleurs que vous encourager à le faire. Il est en effet nécessaire de regarder dans le détail les algorithmes proposés par Mahout ainsi que leurs implémentations, et ce, afin d’utiliser au mieux ceux-ci dans votre application.

Pour aller plus loin

Nous espérons vous avoir intéressé avec cette introduction qui touche un large panel de domaines scientifiques ou d’autres domaines d’ailleurs. Comme nous l’avons suggéré, nous prévoyons un prochain billet sur l’application d’un algorithme de « Machine Learning », Soyez patient.

En attendant voici quelques ressources. Pour commencer, mentionnons le site officiel du projet Mahout sur lequel vous trouverez la liste complète des algorithmes proposés aujourd’hui dans ce contexte.

Vous pouvez aussi suivre le cours Machine Learning (CS 229) du professeur Andrew Ng de l’université de Stanford (le premier module du cours commence réellement à la 32^ème minute).

Pour les plus impatients, Microsoft Research a élaboré un prototype (les données d’entrainements et les sources se trouvent sur GitHub) d’application basé sur le jeu de données 1 million song réunissant les musiques préférées d’un million d’utilisateurs. Vous retrouvez les travaux, projets et publications de Microsoft Research sur le « Machine Learning » ici.

Enfin, comme un certain nombre de billets ont été récemment consacrés à HDInsight, nous vous invitons à consulter le tutoriel de l’équipe HDInsight qui propose de créer un moteur de recommandations avec Mahout et le jeu de données 1 million song précédent.

S’agit-il de bonnes recommandations ? Vous nous le direz ;)