Apprentissage

Objectifs

L'apprentissage est un champ de l'intelligence artificielle où l'on se propose de concevoir des machines dont les performances s'améliorent avec l'expérience. En d'autres termes, une telle machine simule le comportement évolutif d'un être humain. Aujourd'hui, cette discipline est très diversifiée allant de la fouille de données aux systèmes multi-agents en passant par la programmation logique inductive et la théorie de l'information. On tentera dans ce cours de donner un aperçu de l'ensemble en évoquant aussi les problèmes classiques de test de performance et d'évaluation de complexité.

Pré-réquis
Aucun

Description détaillée

Classification : Formalisation du problème

Le cadre standard : PAC apprenabilité de Valiant
A partir d'un exemple introductif (rectangles dans R2), on se pose le problème de définir formellement un modèle de l'apprentissage : on apprend un concept à partir d'exemples. On s'aperçoit alors qu'il y a une certain nombre de concepts apprenables et d'autres qui ne le sont pas !

La dimension de Vapnik-Chervonenkis
Immédiatement se pose la question de la qualité de notre apprentissage, que l'on va mesurer en calculant ou estimant l'erreur que l'on fait (erreur empirique) ou que l'on va faire (erreur réelle). Intuitivement, on comprend que cette erreur va dépendre du nombre d'exemples dont on dispose. Apparaît alors une autre donnée essentielle pour estimer/encadrer ces erreurs : la dimension de Vapnik-Chervonenkis.

Apprentissage numérique

Lorsque les attributs des objets qu'on manipule prennent leurs valeurs dans l'ensemble des nombres réels, on peut classer les objets à l'aide de règles de la forme
SI coef₁ × Attribut₁ + coef₂ × Attribut₂ + … > 0 ALORS …
On parle alors de séparateurs linéaires.
Les réseaux de neurones permettent de représenter des séparatrices (linéaires ou non) par une grille de fonctions (pseudo) linéaires élémentaires, appelées neurones. Les coefficients de ces neurones sont appris par une méthode de descente en gradient. Les fonctions à noyaux généralisent les réseaux de neurones, et permettent de représenter et apprendre des séparatrices non linéaires en passant par des séparatrices linéaires dans un espace de dimension supérieure. On apprend de telles fonctions en transformant le problème initial en un problème d'optimisation, on parle alors de séparateurs à vaste marge (SVM).

Apprentissage Bayésien et par approximation

Le raisonnement bayésien, basé sur l'idée qu'on peut atteindre des décisions optimales en raisonnant sur des probabilités, est important en apprentissage car il fournit une mesure quantitative des évidences supportant les hypothèses. Cela conduit à des algorithmes d'apprentissage très efficaces dans certains cas (on les utilise par exemple notamment pour apprendre à filtrer les messages indésirables dans les logiciels de messagerie électronique).

Apprentissage symbolique

Les approches à base de réseaux de neurones et de SVM sont principalement utilisées pour traiter des données numériques et leur aspect "boîte noire" empêche une compréhension intuitive du modèle que l'on apprend. L'apprentissage symbolique permet de traiter des données "qualitatives". En plus de la recherche de performances on s'intéresse aussi à la lisibilité du modèle appris. On présentera tout d'abord l'espace des versions qui est la première approche théorique de l'espace des version. On s'intéressera ensuite à l'apprentissage d'arbres de décision, la méthode d'apprentissage symbolique la plus couramment utilisée, puis à la programmation logique inductive dont les modèles et les données sont décrits en logique du premier ordre et qui permet de traiter des données relationnelles. Enfin, on verra la différence entre l'apprentissage artificiel et la fouille de données à travers l'extraction de règles d'association.

Méthodes d'évaluation

De part la nature statistique de l'apprentissage artificiel, l'évaluation des performances des modèles appris est une tache cruciale. En effet, mesurer la performance d'un algorithme en se basant sur les données d'apprentissage ne permet pas en général de s'assurer de ses performances sur de nouvelles données. On étudiera les différents critères d'évaluation des algorithmes d'apprentissage (minimisation du risque empirique, vraisemblance du modèle, compression des données) ainsi que les méthodes d'évaluation comme la validation croisée et les courbes ROC. On présentera rapidement la plate-forme WEKA qui permet de développer et de tester des algorithmes d'apprentissage.

Boosting

Lorsque notre agent apprenant fait un peu moins de 50% d'erreurs, on peut dire que l'on n'a pas très bien appris ! La question que l'on se pose alors est de savoir comment combiner intelligemment des agents apprenants pas très performants pour obtenir un agent performant. Une réponse se trouve dans le boosting qui décrit formellement une telle combinaison.

Apprentissage par renforcement

Lorsqu'on cherche à faire apprendre à un système ce qu'il convient de faire dans certaines situations, à partir d'expérience, on sort du cadre de la classification. On donnera un bref aperçu d'une méthode – le Q-learning – qui permet d'apprendre par exploration la fonction de transition d'un processus de décision Markovien.

Ouvrages conseillés

  • Machine Learning, Tom Mitchell, McGraw Hill, 1997
  • Apprentissage artificiel - Concepts et algorithmes, Antoine Cornuéjols, Laurent Miclet et Yves Kodratoff, Eyrolles, 2002
  • Data mining: Practical machine learning tools and techniques, Ian H. Witten et Eibe Frank, Elsevier, 2005 (2nd edition)
Equipe pédagogique :
Marie-Pierre Gleizes, Jérôme Mengin, Gilles Richard, Mathieu Serrurier
Responsable :
Jérôme Mengin (Jerome.Mengin at irit.fr, 05 61 55 64 51)