Introduction au Machine Learning PDF

1 Introduction au Machine Learning Chloé-Agathe Azencott Cet ouvrage s’adresse aux étudiantes et étudiants en fin de licence et en master d’informatique ou de maths appliquées, ainsi qu’aux élèves d’école d’ingénieurs. L’apprentissage...

1 Introduction au Machine Learning Chloé-Agathe Azencott Cet ouvrage s’adresse aux étudiantes et étudiants en fin de licence et en master d’informatique ou de maths appliquées, ainsi qu’aux élèves d’école d’ingénieurs. L’apprentissage automatique, ou machine Learning, est une discipline dont les outils puissants permettent aujourd’hui à de nombreux secteurs d’activité de réaliser des progrès spectaculaires grâce à l’exploitation de grands volumes de données. Le but de cet ouvrage est de vous fournir des bases solides sur les concepts et les algorithmes de ce domaine en plein essor. Il vous aidera à identifier les problèmes qui peuvent être résolus par une approche machine learning, à les formaliser, à identifier les algorithmes les mieux adaptés à chaque cas, à les mettre en oeuvre, et enfin à savoir évaluer les résultats obtenus. Ce document est la version électronique d’un ouvrage publié aux éditions Dunod dans la collection InfoSup 1 , qui contient aussi 86 exercices corrigés. 1. https://www.dunod.com/sciences-techniques/introduction-au-machine-learning-0 Préambule Le machine learning (apprentissage automatique) est au cœur de la science des données et de l’intelli- gence artificielle. Que l’on parle de transformation numérique des entreprises, de Big Data ou de straté- gie nationale ou européenne, le machine learning est devenu incontournable. Ses applications sont nom- breuses et variées, allant des moteurs de recherche et de la reconnaissance de caractères à la recherche en génomique, l’analyse des réseaux sociaux, la publicité ciblée, la vision par ordinateur, la traduction auto- matique ou encore le trading algorithmique. À l’intersection des statistiques et de l’informatique, le machine learning se préoccupe de la modélisa- tion des données. Les grands principes de ce domaine ont émergé des statistiques fréquentistes ou bayé- siennes, de l’intelligence artificielle ou encore du traitement du signal. Dans ce livre, nous considérons que le machine learning est la science de l’apprentissage automatique d’une fonction prédictive à partir d’un jeu d’observations de données étiquetées ou non. Ce livre se veut une introduction aux concepts et algorithmes qui fondent le machine learning, et en propose une vision centrée sur la minimisation d’un risque empirique par rapport à une classe donnée de fonctions de prédictions. Objectifs pédagogiques : Le but de ce livre est de vous accompagner dans votre découverte du machine learning et de vous fournir les outils nécessaires à 1. identifier les problèmes qui peuvent être résolus par des approches de machine learning ; 2. formaliser ces problèmes en termes de machine learning ; 3. identifier les algorithmes classiques les plus appropriés pour ces problèmes et les mettre en œuvre ; 4. implémenter ces algorithmes par vous-même afin d’en comprendre les tenants et aboutissants ; 5. évaluer et comparer de la manière la plus objective possible les performances de plusieurs algo- rithmes de machine learning pour une application particulière. Public visé : Ce livre s’adresse à des étudiants en informatique ou maths appliquées, niveau L3 ou M1 (ou deuxième année d’école d’ingénieur), qui cherchent à comprendre les fondements des principaux algo- rithmes utilisés en machine learning. Il se base sur mes cours à CentraleSupélec 2 et sur OpenClassrooms 3 et suppose les prérequis suivants : — algèbre linéaire (inversion de matrice, théorème spectral, décomposition en valeurs propres et vec- teurs propres). — notions de probabilités (variable aléatoire, distributions, théorème de Bayes). 2. http://tinyurl.com/ma2823-2017 3. https://openclassrooms.com/paths/data-scientist 2  3 Plan du livre : Ce livre commence par une vue d’ensemble du machine learning et des différents types de problèmes qu’il permet de résoudre. Il présente comment ces problèmes peuvent être formulés mathé- matiquement comme des problèmes d’optimisation (chapitre 1) et pose en appendice les bases d’optimi- sation convexe nécessaires à la compréhension des algorithmes présentés par la suite. La majeure partie de ce livre concerne les problèmes d’apprentissage supervisé ; le chapitre 2 détaille plus particulièrement leur formulation et introduit les notions d’espace des hypothèses, de risque et perte, et de généralisation. Avant d’étudier les algorithmes d’apprentissage supervisé les plus classiques et fréquemment utilisés, il est essentiel de comprendre comment évaluer un modèle sur un jeu de données, et de savoir sélectionner le meilleur modèle parmi plusieurs possibilités, ce qui est le sujet du chapitre 3. Il est enfin pertinent à ce stade d’aborder l’entraînement de modèles prédictifs supervisés. Le livre aborde tout d’abord les modèles paramétriques, dans lesquels la fonction modélisant la distribution des données ou permettant de faire des prédictions a une forme analytique explicite. Les bases sont posées avec des éléments d’inférence bayésienne (chapitre 4), qui seront ensuite appliqués à des modèles d’ap- prentissage supervisé paramétriques (chapitre 5). Le chapitre 6 présente les variantes régularisées de ces algorithmes. Enfin, le chapitre 7 sur les réseaux de neurones propose de construire des modèles paramé- triques beaucoup plus complexes et d’aborder les bases du deep learning. Le livre aborde ensuite les modèles non paramétriques, à commencer par une des plus intuitives de ces approches, la méthode des plus proches voisins (chapitre 8). Suivront ensuite les approches à base d’arbres de décision, puis les méthodes à ensemble qui permettront d’introduire deux des algorithmes de machine learning supervisé les plus puissants à l’heure actuelle : les forêts aléatoires et le boosting de gradient (cha- pitre 9). Le chapitre 10 sur les méthodes à noyaux, introduites grâce aux machines à vecteurs de support, permettra de voir comment construire des modèles non linéaires via des modèles linéaires dans un espace de redescription des données. Enfin, le chapitre 11 présentera la réduction de dimension, supervisée ou non supervisée, et le cha- pitre 12 traitera d’un des problèmes les plus importants en apprentissage non supervisé : le clustering. Chaque chapitre sera conclu par quelques exercices. Comment lire ce livre : Ce livre a été conçu pour être lu linéairement. Cependant, après les trois pre- miers chapitres, il vous sera possible de lire les suivants dans l’ordre qui vous conviendra, à l’exception du chapitre 6, qui a été écrit dans la continuité du chapitre 5. De manière générale, des références vers les sections d’autres chapitres apparaîtront si nécessaire. Remerciements : Cet ouvrage n’aurait pas vu le jour sans Jean-Philippe Vert, qui m’a fait découvrir le machine learning, avec qui j’ai enseigné et pratiqué cette discipline pendant plusieurs années, et qui m’a fait, enfin, l’honneur d’une relecture attentive. Ce livre doit beaucoup à ceux qui m’ont enseigné le machine learning, et plus particulièrement Pierre Baldi, Padhraic Smyth, et Max Welling ; à ceux avec qui je l’ai pratiqué, notamment les membres du Baldi Lab à UC Irvine, du MLCB et du département d’inférence empirique de l’Institut Max Planck à Tübingen, et du CBIO à Mines ParisTech, et bien d’autres encore qu’il serait difficile de tous nommer ici ; à ceux avec qui je l’ai enseigné, Karsten Borgwardt, Yannis Chaouche, Frédéric Guyon, Fabien Moutarde, mais aussi Judith Abecassis, Eugene Belilovsky, Joseph Boyd, Peter Naylor, Benoît Playe, Mihir Sahasrabudhe, Jiaqian Yu, et Luc Bertrand ; et enfin à ceux auxquels je l’ai enseigné, en particulier les étudiants du cours Data Mining 4 in der Bioinformatik de l’Université de Tübingen qui ont subi ma toute première tentative d’enseignement des méthodes à noyaux en 2012, et les étudiants centraliens qui ont essuyé les plâtres de la première version de ce cours à l’automne 2015. Mes cours sont le résultat de nombreuses sources d’inspirations accumulées au cours des années. Je remercie tout particulièrement Ethem Alpaydin, David Barber, Christopher M. Bishop, Stephen Boyd, Hal Daumé III, Jerome Friedman, Trevor Hastie, Tom Mitchell, Bernhard Schölkopf, Alex Smola, Robert Tibshi- rani, Lieven Vandenberghe, et Alice Zhang pour leurs ouvrages. Parce que tout serait différent sans scikit-learn, je remercie chaleureusement tous ses core-devs, et en particulier Alexandre Gramfort, Olivier Grisel, Gaël Varoquaux et Nelle Varoquaux. Je remercie aussi Matthew Blaschko, qui m’a poussée à l’eau, et Nikos Paragios, qui l’y a encouragé. Parce que je n’aurais pas pu écrire ce livre seule, merci à Jean-Luc Blanc des Éditions Dunod, et à tous ceux qui ont relu tout ou partie de cet ouvrage, en particulier Judith Abecassis, Luc Bertrand, Caroline Petitjean, Denis Rousselle, Erwan Scornet. La relecture attentive de Jean-Marie Monier, ainsi que les commentaires d’Antoine Brault, ont permis d’éliminer de nombreuses coquilles et approximations de la deuxième version de ce texte. Merci à Alix Deleporte, enfin, pour ses relectures et son soutien. Table des matières 1 Présentation du machine learning 10 1.1 Qu’est-ce que le machine learning ?................................ 10 1.1.1 Pourquoi utiliser le machine learning ?.......................... 11 1.2 Types de problèmes de machine learning............................. 13 1.2.1 Apprentissage supervisé.................................. 13 1.2.2 Apprentissage non supervisé............................... 15 1.2.3 Apprentissage semi-supervisé............................... 17 1.2.4 Apprentissage par renforcement............................. 17 1.3 Ressources pratiques........................................ 17 1.3.1 Implémentations logicielles................................ 17 1.3.2 Jeux de données...................................... 18 1.4 Notations.............................................. 18 2 Apprentissage supervisé 20 2.1 Formalisation d’un problème d’apprentissage supervisé..................... 20 2.1.1 Décision........................................... 21 2.1.2 Classification multi-classe................................. 22 2.2 Espace des hypothèses....................................... 23 2.3 Minimisation du risque empirique................................ 24 2.4 Fonctions de coût.......................................... 25 2.4.1 Fonctions de coût pour la classification binaire..................... 26 2.4.2 Coûts pour la classification multi-classe......................... 28 2.4.3 Coûts pour la régression.................................. 29 2.5 Généralisation et sur-apprentissage................................ 30 2.5.1 Généralisation....................................... 30 2.5.2 Sur-apprentissage..................................... 31 2.5.3 Compromis biais-variance................................. 32 2.5.4 Régularisation....................................... 34 3 Sélection de modèle et évaluation 36 3.1 Estimation empirique de l’erreur de généralisation....................... 36 3.1.1 Jeu de test.......................................... 37 3.1.2 Jeu de validation...................................... 37 3.1.3 Validation croisée..................................... 37 3.1.4 Bootstrap.......................................... 39 3.2 Critères de performance...................................... 40 3.2.1 Matrice de confusion et critères dérivés......................... 40 3.2.2 Évaluation de méthodes de classification binaire retournant un score......... 42 5 6 TABLE DES MATIÈRES 3.2.3 Erreurs de régression.................................... 45 3.2.4 Comparaison à des algorithmes naïfs........................... 46 4 Inférence bayésienne 49 4.1 Modèles génératifs pour la classification binaire......................... 49 4.1.1 Inférence et prédiction................................... 50 4.1.2 Loi de Bayes......................................... 50 4.1.3 Modélisation paramétrique................................ 51 4.2 Règles de décision......................................... 51 4.2.1 Tests du rapport de vraisemblance............................ 52 4.2.2 Théorie de la décision bayésienne............................. 53 4.3 Estimation de densité....................................... 57 4.3.1 Estimation par maximum de vraisemblance....................... 57 4.3.2 Estimateur de Bayes.................................... 59 4.3.3 Décomposition biais-variance............................... 60 4.4 Classification naïve bayésienne.................................. 60 4.4.1 Principes.......................................... 60 4.4.2 Filtrage bayésien du spam................................. 61 4.5 Sélection de modèle bayésienne.................................. 62 5 Régressions paramétriques 64 5.1 Apprentissage supervisé d’un modèle paramétrique....................... 64 5.1.1 Modèles paramétriques.................................. 64 5.1.2 Estimation par maximum de vraisemblance et méthode des moindres carrés..... 66 5.2 Régression linéaire......................................... 66 5.2.1 Formulation......................................... 66 5.2.2 Solution........................................... 66 5.2.3 Théorème de Gauss-Markov................................ 67 5.3 Régression logistique........................................ 68 5.3.1 Formulation......................................... 69 5.3.2 Solution........................................... 70 5.4 Régression polynomiale...................................... 70 6 Régularisation 72 6.1 Qu’est-ce que la régularisation ?.................................. 72 6.2 La régression ridge......................................... 73 6.2.1 Formulation de la régression ridge............................ 73 6.2.2 Solution........................................... 74 6.2.3 Chemin de régularisation................................. 74 6.2.4 Interprétation géométrique................................ 75 6.3 Le lasso............................................... 76 6.3.1 Parcimonie......................................... 76 6.3.2 Formulation du lasso.................................... 76 6.3.3 Solution........................................... 77 6.3.4 Interprétation géométrique................................ 77 6.3.5 Chemin de régularisation................................. 77 6.4 Elastic net.............................................. 78 TABLE DES MATIÈRES 7 7 Réseaux de neurones artificiels 81 7.1 Le perceptron............................................ 81 7.1.1 Modèle........................................... 82 7.1.2 Entraînement........................................ 83 7.1.3 Modélisation de fonctions booléennes.......................... 85 7.2 Perceptron multi-couche...................................... 86 7.2.1 Architecture........................................ 86 7.2.2 Approximation universelle................................ 87 7.2.3 Modéliser XOR avec un perceptron multi-couche.................... 88 7.2.4 Entraînement par rétropropagation............................ 88 7.2.5 Et le deep learning dans tout ça ?............................. 91 8 Méthode des plus proches voisins 93 8.1 Méthode du plus proche voisin.................................. 93 8.1.1 Méthode.......................................... 93 8.1.2 Diagramme de Voronoï................................... 94 8.2 Méthode des plus proches voisins................................. 95 8.2.1 Méthode des k plus proches voisins............................ 95 8.2.2 Apprentissage paresseux.................................. 96 8.2.3 Nombre de plus proches voisins.............................. 96 8.2.4 Variantes.......................................... 97 8.3 Distances et similarités....................................... 98 8.3.1 Distances.......................................... 98 8.3.2 Similarités entre vecteurs réels.............................. 99 8.3.3 Similarités entre ensembles................................ 100 8.3.4 Similarités entre données catégoriques.......................... 101 8.4 Filtrage collaboratif......................................... 102 9 Arbres et forêts 104 9.1 Arbres de décision......................................... 104 9.1.1 Apprentissage hiérarchique................................ 104 9.1.2 Partition de l’espace par un arbre de décision...................... 105 9.2 Comment faire pousser un arbre................................. 106 9.2.1 CART............................................ 106 9.2.2 Critères d’impureté..................................... 108 9.2.3 Élaguer un arbre...................................... 108 9.3 Méthodes ensemblistes : la sagesse des foules.......................... 109 9.3.1 Méthodes parallèles : le bagging.............................. 110 9.3.2 Méthodes séquentielles : le boosting........................... 111 10 Machines à vecteurs de support et méthodes à noyaux 116 10.1 Le cas linéairement séparable : SVM à marge rigide....................... 116 10.1.1 Marge d’un hyperplan séparateur............................. 117 10.1.2 Formulation de la SVM à marge rigide.......................... 118 10.1.3 Formulation duale..................................... 119 10.1.4 Interprétation géométrique................................ 121 10.2 Le cas linéairement non séparable : SVM à marge souple.................... 121 10.2.1 Formulation de la SVM à marge souple.......................... 121 8 TABLE DES MATIÈRES 10.2.2 Formulation duale..................................... 122 10.2.3 Interprétation géométrique................................ 124 10.3 Le cas non linéaire : SVM à noyau................................. 124 10.3.1 Espace de redescription.................................. 125 10.3.2 SVM dans l’espace de redescription............................ 125 10.3.3 Astuce du noyau...................................... 125 10.3.4 Noyaux........................................... 126 10.4 Régression ridge à noyau...................................... 128 11 Réduction de dimension 132 11.1 Motivation............................................. 132 11.1.1 Visualiser les données................................... 132 11.1.2 Réduire les coûts algorithmiques............................. 133 11.1.3 Améliorer la qualité des modèles............................. 133 11.2 Sélection de variables....................................... 134 11.2.1 Méthodes de filtrage.................................... 134 11.2.2 Méthodes de conteneur.................................. 135 11.2.3 Méthodes embarquées................................... 137 11.3 Extraction de variables....................................... 137 11.3.1 Analyse en composantes principales........................... 137 11.3.2 Factorisation de la matrice des données......................... 140 11.3.3 Auto-encodeurs....................................... 142 11.3.4 Autres approches non linéaires.............................. 145 12 Clustering 148 12.1 Pourquoi partitionner ses données................................ 148 12.2 Évaluer la qualité d’un algorithme de clustering......................... 149 12.2.1 La forme des clusters.................................... 149 12.2.2 La stabilité des clusters................................... 152 12.2.3 Les connaissances expert................................. 152 12.3 Clustering hiérarchique...................................... 153 12.3.1 Dendrogramme....................................... 153 12.3.2 Construction agglomérative ou divisive.......................... 154 12.3.3 Fonctions de lien...................................... 154 12.3.4 Choix du nombre de clusters............................... 155 12.3.5 Complexité algorithmique................................. 155 12.4 Méthode des k-moyennes..................................... 156 12.4.1 Algorithme de Lloyd.................................... 156 12.4.2 Forme des clusters..................................... 156 12.4.3 Variantes.......................................... 157 12.5 Clustering par densité....................................... 158 A Notions d’optimisation convexe 162 A.1 Convexité.............................................. 162 A.1.1 Ensemble convexe..................................... 162 A.1.2 Fonction convexe...................................... 163 A.2 Problèmes d’optimisation convexe................................ 164 A.2.1 Formulation et vocabulaire................................ 164 TABLE DES MATIÈRES 9 A.2.2 Extrema locaux et globaux................................. 165 A.3 Optimisation convexe sans contrainte.............................. 166 A.3.1 Caractérisation différentielle de la convexité....................... 166 A.3.2 Caractérisation du deuxième ordre de la convexité................... 167 A.3.3 Algorithme du gradient.................................. 168 A.3.4 Recherche linéaire par rebroussement.......................... 169 A.3.5 Méthode de Newton.................................... 170 A.3.6 Méthode de Newton par gradient conjugué....................... 171 A.3.7 Méthodes de quasi-Newton................................ 173 A.3.8 Algorithme du gradient stochastique........................... 174 A.3.9 Descente de coordonnées................................. 175 A.4 Optimisation convexe sous contraintes.............................. 175 A.4.1 Lagrangien......................................... 175 A.4.2 Dualité faible........................................ 176 A.4.3 Dualité forte........................................ 177 A.4.4 Conditions de Karush-Kuhn-Tucker............................ 178 A.4.5 Programmes quadratiques................................. 179 Chapitre 1 Présentation du machine learning Le machine learning est un domaine captivant. Issu de nombreuses disciplines comme les statistiques, l’optimisation, l’algorithmique ou le traitement du signal, c’est un champ d’études en mutation constante qui s’est maintenant imposé dans notre société. Déjà utilisé depuis des décennies dans la reconnaissance automatique de caractères ou les filtres anti-spam, il sert maintenant à protéger contre la fraude bancaire, recommander des livres, films, ou autres produits adaptés à nos goûts, identifier les visages dans le viseur de notre appareil photo, ou traduire automatiquement des textes d’une langue vers une autre. Dans les années à venir, le machine learning nous permettra vraisemblablement d’améliorer la sécurité routière (y compris grâce aux véhicules autonomes), la réponse d’urgence aux catastrophes naturelles, le développement de nouveaux médicaments, ou l’efficacité énergétique de nos bâtiments et industries. Le but de ce chapitre est d’établir plus clairement ce qui relève ou non du machine learning, ainsi que des branches de ce domaine dont cet ouvrage traitera. Objectifs — Définir le machine learning — Identifier si un problème relève ou non du machine learning — Donner des exemples de cas concrets relevant de grandes classes de problèmes de machine learning. 1.1 Qu’est-ce que le machine learning ? Qu’est-ce qu’apprendre, comment apprend-on, et que cela signifie-t-il pour une machine ? La question de l’apprentissage fascine les spécialistes de l’informatique et des mathématiques tout autant que neuro- logues, pédagogues, philosophes ou artistes. Une définition qui s’applique à un programme informatique comme à un robot, un animal de compagnie ou un être humain est celle proposée par Fabien Benureau (2015) : « L’apprentissage est une modification d’un comportement sur la base d’une expérience ». Dans le cas d’un programme informatique, qui est celui qui nous intéresse dans cet ouvrage, on parle d’apprentissage automatique, ou machine learning, quand ce programme a la capacité d’apprendre sans que cette modification ne soit explicitement programmée. Cette définition est celle donnée par Arthur Samuel 10 1.1. Qu’est-ce que le machine learning ? 11 (1959). On peut ainsi opposer un programme classique, qui utilise une procédure et les données qu’il reçoit en entrée pour produire en sortie des réponses, à un programme d’apprentissage automatique, qui utilise les données et les réponses afin de produire la procédure qui permet d’obtenir les secondes à partir des premières. Exemple Supposons qu’une entreprise veuille connaître le montant total dépensé par un client ou une cliente à partir de ses factures. Il suffit d’appliquer un algorithme classique, à savoir une simple addition : un algorithme d’apprentissage n’est pas nécessaire. Supposons maintenant que l’on veuille utiliser ces factures pour déterminer quels produits le client est le plus susceptible d’acheter dans un mois. Bien que cela soit vraisemblablement lié, nous n’avons manifes- tement pas toutes les informations nécessaires pour ce faire. Cependant, si nous disposons de l’historique d’achat d’un grand nombre d’individus, il devient possible d’utiliser un algorithme de machine learning pour qu’il en tire un modèle prédictif nous permettant d’apporter une réponse à notre question. 1.1.1 Pourquoi utiliser le machine learning ? Le machine learning peut servir à résoudre des problèmes — que l’on ne sait pas résoudre (comme dans l’exemple de la prédiction d’achats ci-dessus) ; — que l’on sait résoudre, mais dont on ne sait formaliser en termes algorithmiques comment nous les résolvons (c’est le cas par exemple de la reconnaissance d’images ou de la compréhension du langage naturel) ; — que l’on sait résoudre, mais avec des procédures beaucoup trop gourmandes en ressources informa- tiques (c’est le cas par exemple de la prédiction d’interactions entre molécules de grande taille, pour lesquelles les simulations sont très lourdes). Le machine learning est donc utilisé quand les données sont abondantes (relativement), mais les connais- sances peu accessibles ou peu développées. Ainsi, le machine learning peut aussi aider les humains à apprendre : les modèles créés par des al- gorithmes d’apprentissage peuvent révéler l’importance relative de certaines informations ou la façon dont elles interagissent entre elles pour résoudre un problème particulier. Dans l’exemple de la prédic- tion d’achats, comprendre le modèle peut nous permettre d’analyser quelles caractéristiques des achats passés permettent de prédire ceux à venir. Cet aspect du machine learning est très utilisé dans la recherche scientifique : quels gènes sont impliqués dans le développement d’un certain type de tumeur, et comment ? Quelles régions d’une image cérébrale permettent de prédire un comportement ? Quelles caractéristiques d’une molécule en font un bon médicament pour une indication particulière ? Quels aspects d’une image de télescope permettent d’y identifier un objet astronomique particulier ? Ingrédients du machine learning Le machine learning repose sur deux piliers fondamentaux : — d’une part, les données, qui sont les exemples à partir duquel l’algorithme va apprendre ; — d’autre part, l’algorithme d’apprentissage, qui est la procédure que l’on fait tourner sur ces données pour produire un modèle. On appelle entraînement le fait de faire tourner un algorithme d’appren- tissage sur un jeu de données. Ces deux piliers sont aussi importants l’un que l’autre. D’une part, aucun algorithme d’apprentissage ne pourra créer un bon modèle à partir de données qui ne sont pas pertinentes – c’est le concept garbage in, garbage out qui stipule qu’un algorithme d’apprentissage auquel on fournit des données de mauvaise qualité 12 Chapitre 1. Présentation du machine learning ne pourra rien en faire d’autre que des prédictions de mauvaise qualité. D’autre part, un modèle appris avec un algorithme inadapté sur des données pertinentes ne pourra pas être de bonne qualité. Cet ouvrage est consacré au deuxième de ces piliers – les algorithmes d’apprentissage. Néanmoins, il ne faut pas négliger qu’une part importante du travail de machine learner ou de data scientist est un travail d’ingénierie consistant à préparer les données afin d’éliminer les données aberrantes, gérer les données manquantes, choisir une représentation pertinente, etc. Attention Bien que l’usage soit souvent d’appeler les deux du même nom, il faut distinguer l’algorithme d’apprentis- sage automatique du modèle appris : le premier utilise les données pour produire le second, qui peut ensuite être appliqué comme un programme classique. Un algorithme d’apprentissage permet donc de modéliser un phénomène à partir d’exemples. Nous consi- dérons ici qu’il faut pour ce faire définir et optimiser un objectif. Il peut par exemple s’agir de minimiser le nombre d’erreurs faites par le modèle sur les exemples d’apprentissage. Cet ouvrage présente en effet les algorithmes les plus classiques et les plus populaires sous cette forme. Exemple Voici quelques exemples de reformulation de problèmes de machine learning sous la forme d’un pro- blème d’optimisation. La suite de cet ouvrage devrait vous éclairer sur la formalisation mathématique de ces problèmes, formulés ici très librement. — un vendeur en ligne peut chercher à modéliser des types représentatifs de clientèle, à partir des tran- sactions passées, en maximisant la proximité entre clients et clientes affectés à un même type ; — une compagnie automobile peut chercher à modéliser la trajectoire d’un véhicule dans son environ- nement, à partir d’enregistrements vidéo de voitures, en minimisant le nombre d’accidents ; — des chercheurs en génétique peuvent vouloir modéliser l’impact d’une mutation sur une maladie, à partir de données patient, en maximisant la cohérence de leur modèle avec les connaissances de l’état de l’art ; — une banque peut vouloir modéliser les comportements à risque, à partir de son historique, en maxi- misant le taux de détection de non solvabilité. Ainsi, le machine learning repose d’une part sur les mathématiques, et en particulier les statistiques, pour ce qui est de la construction de modèles et de leur inférence à partir de données, et d’autre part sur l’informatique, pour ce qui est de la représentation des données et de l’implémentation efficace d’algo- rithmes d’optimisation. De plus en plus, les quantités de données disponibles imposent de faire appel à des architectures de calcul et de base de données distribuées. C’est un point important mais que nous n’abor- dons pas dans cet ouvrage. Et l’intelligence artificielle, dans tout ça ? Le machine learning peut être vu comme une branche de l’intelligence artificielle. En effet, un système incapable d’apprendre peut difficilement être considéré comme intelligent. La capacité à apprendre et à tirer parti de ses expériences est en effet essentielle à un système conçu pour s’adapter à un environnement changeant. L’intelligence artificielle, définie comme l’ensemble des techniques mises en œuvre afin de construire des machines capables de faire preuve d’un comportement que l’on peut qualifier d’intelligent, fait aussi appel aux sciences cognitives, à la neurobiologie, à la logique, à l’électronique, à l’ingénierie et bien plus encore. 1.2. Types de problèmes de machine learning 13 Probablement parce que le terme « intelligence artificielle » stimule plus l’imagination, il est cependant de plus en plus souvent employé en lieu et place de celui d’apprentissage automatique. 1.2 Types de problèmes de machine learning Le machine learning est un champ assez vaste, et nous dressons dans cette section une liste des plus grandes classes de problèmes auxquels il s’intéresse. 1.2.1 Apprentissage supervisé L’apprentissage supervisé est peut-être le type de problèmes de machine learning le plus facile à appré- hender : son but est d’apprendre à faire des prédictions, à partir d’une liste d’exemples étiquetés, c’est-à-dire accompagnés de la valeur à prédire (voir figure 1.1). Les étiquettes servent de « professeur » et supervisent l’apprentissage de l’algorithme. Définition 1.1 (Apprentissage supervisé) On appelle apprentissage supervisé la branche du machine learning qui s’intéresse aux problèmes pouvant être formalisés de la façon suivante : étant données n obser- vations {~x i }i=1,...,n décrites dans un espace X , et leurs étiquettes {y i }i=1,...,n décrites dans un espace Y, on suppose que les étiquettes peuvent être obtenues à partir des observations grâce à une fonction φ : X → Y fixe et inconnue : y i = φ(~x i ) + i , où i est un bruit aléatoire. Il s’agit alors d’utiliser les données pour dé- terminer une fonction f : X → Y telle que, pour tout couple (~x, φ(~x)) ∈ X × Y, f (~x) ≈ φ(~x).  L’espace sur lequel sont définies les données est le plus souvent X = Rp. Nous verrons cependant aussi comment traiter d’autres types de représentations, comme des variables binaires, discrètes, catégoriques, voire des chaînes de caractères ou des graphes. Algorithme Modèle Observations de ML prédictif Étiquettes Figure 1.1 – Apprentissage supervisé. Classification binaire Dans le cas où les étiquettes sont binaires, elles indiquent l’appartenance à une classe. On parle alors de classification binaire. Définition 1.2 (Classification binaire) Un problème d’apprentissage supervisé dans lequel l’espace des étiquettes est binaire, autrement dit Y = {0, 1} est appelé un problème de classification binaire.  14 Chapitre 1. Présentation du machine learning Exemple Voici quelques exemples de problèmes de classification binaire : — Identifier si un email est un spam ou non ; — Identifier si un tableau a été peint par Picasso ou non ; — Identifier si une image contient ou non une girafe ; — Identifier si une molécule peut ou non traiter la dépression ; — Identifier si une transaction financière est frauduleuse ou non. Classification multi-classe Dans le cas où les étiquettes sont discrètes, et correspondent donc à plusieurs 1 classes, on parle de clas- sification multi-classe. Définition 1.3 (Classification multi-classe) Un problème d’apprentissage supervisé dans lequel l’es- pace des étiquettes est discret et fini, autrement dit Y = {1, 2,... , C} est appelé un problème de classifi- cation multi-classe. C est le nombre de classes.  Exemple Voici quelques exemples de problèmes de classification multi-classe : — Identifier en quelle langue un texte est écrit ; — Identifier lequel des 10 chiffres arabes est un chiffre manuscrit — Identifier l’expression d’un visage parmi une liste prédéfinie de possibilités (colère, tristesse, joie, etc.) ; — Identifier à quelle espèce appartient une plante ; — Identifier les objets présents sur une photographie. Régression Dans le cas où les étiquettes sont à valeurs réelles, on parle de régression. Définition 1.4 (Régression) Un problème d’apprentissage supervisé dans lequel l’espace des étiquettes est Y = R est appelé un problème de régression.  Exemple Voici quelques exemples de problèmes de régression : — Prédire le nombre de clics sur un lien ; — Prédire le nombre d’utilisateurs et utilisatrices d’un service en ligne à un moment donné ; — Prédire le prix d’une action en bourse ; — Prédire l’affinité de liaison entre deux molécules ; — Prédire le rendement d’un plant de maïs. 1. Nous utilisons ici la définition bourbakiste de « plusieurs », c’est-à-dire strictement supérieur à deux. 1.2. Types de problèmes de machine learning 15 Régression structurée Dans le cas où l’espace des étiquettes est un espace structuré plus complexe que ceux évoqués précé- demment, on parle de régression structurée – en anglais, structured regression, ou structured output prediction. Il peut par exemple s’agir de prédire des vecteurs, des images, des graphes, ou des séquences. La régression structurée permet de formaliser de nombreux problèmes, comme ceux de la traduction automatique ou de la reconnaissance vocale (text-to-speech et speech-to-text, par exemple). Ce cas dépasse cependant le cadre du présent ouvrage, et nous nous concentrerons sur les problèmes de classification binaire et multi-classe, ainsi que de régression classique. L’apprentissage supervisé est le sujet principal de cet ouvrage, et sera traité du chapitre 2 au chapitre 9. 1.2.2 Apprentissage non supervisé Dans le cadre de l’apprentissage non supervisé, les données ne sont pas étiquetées. Il s’agit alors de mo- déliser les observations pour mieux les comprendre (voir figure 1.2). Définition 1.5 (Apprentissage non supervisé) On appelle apprentissage non supervisé la branche du machine learning qui s’intéresse aux problèmes pouvant être formalisés de la façon suivante : étant don- nées n observations {~x i }i=1,...,n décrites dans un espace X , il s’agit d’apprendre une fonction sur X qui vérifie certaines propriétés.  Algorithme Observations de ML Observations réduites Figure 1.2 – Apprentissage non supervisé. Cette définition est très vague, et sera certainement plus claire sur des exemples. Clustering Tout d’abord, le clustering, ou partitionnement, consiste à identifier des groupes dans les données (voir figure 1.3). Cela permet de comprendre leurs caractéristiques générales, et éventuellement d’inférer les propriétés d’une observation en fonction du groupe auquel elle appartient. Définition 1.6 (Partitionnement) On appelle partitionnement ou clusteringS un problème d’apprentis- sage non supervisé pouvant être formalisé comme la recherche d’une partition K k=1 Ck des n observations i {~x }i=1,...,n. Cette partition doit être pertinente au vu d’un ou plusieurs critères à préciser.  Exemple Voici quelques exemples de problèmes de partitionnement — La segmentation de marché consiste à identifier des groupes d’usagers ou de clients ayant un compor- tement similaire. Cela permet de mieux comprendre leur profil, et cibler une campagne de publicité, des contenus ou des actions spécifiquement vers certains groupes. — Identifier des groupes de documents ayant un sujet similaire, sans les avoir au préalable étiquetés par sujet. Cela permet d’organiser de larges banques de textes. 16 Chapitre 1. Présentation du machine learning Algorithme Observations de ML Figure 1.3 – Partitionnement des données, ou clustering. — La compression d’image peut être formulée comme un problème de partitionnement consistant à re- grouper des pixels similaires pour ensuite les représenter plus efficacement. — La segmentation d’image consiste à identifier les pixels d’une image appartenant à la même région. — Identifier des groupes parmi les patients présentant les mêmes symptômes permet d’identifier des sous-types d’une maladie, qui pourront être traités différemment. Ce sujet est traité en détail au chapitre 12. Réduction de dimension La réduction de dimension est une autre famille importante de problèmes d’apprentissage non supervisé. Il s’agit de trouver une représentation des données dans un espace de dimension plus faible que celle de l’espace dans lequel elles sont représentées à l’origine (voir figure 1.4). Cela permet de réduire les temps de calcul et l’espace mémoire nécessaire au stockage les données, mais aussi souvent d’améliorer les perfor- mances d’un algorithme d’apprentissage supervisé entraîné par la suite sur ces données. Définition 1.7 (Réduction de dimension) On appelle réduction de dimension un problème d’appren- tissage non supervisé pouvant être formalisé comme la recherche d’un espace Z de dimension plus faible que l’espace X dans lequel sont représentées n observations {~x i }i=1,...,n. Les projections {~z i }i=1,...,n des données sur Z doivent vérifier certaines propriétés à préciser.  Algorithme Observations Observations réduites de ML Figure 1.4 – Réduction de dimension. Remarque Certaines méthodes de réduction de dimension sont supervisées : il s’agit alors de trouver la représen- tation la plus pertinente pour prédire une étiquette donnée. Nous traiterons de la réduction de dimension au chapitre 11. 1.3. Ressources pratiques 17 Estimation de densité Enfin, une grande famille de problèmes d’apprentissage non supervisé est en fait un problème tradi- tionnel en statistiques : il s’agit d’estimer une loi de probabilité en supposant que le jeu de données en est un échantillon aléatoire. Le chapitre 4 aborde brièvement ce sujet. 1.2.3 Apprentissage semi-supervisé Comme on peut s’en douter, l’apprentissage semi-supervisé consiste à apprendre des étiquettes à par- tir d’un jeu de données partiellement étiqueté. Le premier avantage de cette approche est qu’elle permet d’éviter d’avoir à étiqueter l’intégralité des exemples d’apprentissage, ce qui est pertinent quand il est fa- cile d’accumuler des données mais que leur étiquetage requiert une certaine quantité de travail humain. Prenons par exemple la classification d’images : il est facile d’obtenir une banque de données contenant des centaines de milliers d’images, mais avoir pour chacune d’entre elles l’étiquette qui nous intéresse peut requérir énormément de travail. De plus, les étiquettes données par des humains sont susceptibles de re- produire des biais humains, qu’un algorithme entièrement supervisé reproduira à son tour. L’apprentissage semi-supervisé permet parfois d’éviter cet écueil. Il s’agit d’un sujet plus avancé, que nous ne considérerons pas dans cet ouvrage. 1.2.4 Apprentissage par renforcement Dans le cadre de l’apprentissage par renforcement, le système d’apprentissage peut interagir avec son en- vironnement et accomplir des actions. En retour de ces actions, il obtient une récompense, qui peut être positive si l’action était un bon choix, ou négative dans le cas contraire. La récompense peut parfois ve- nir après une longue suite d’actions ; c’est le cas par exemple pour un système apprenant à jouer au go ou aux échecs. Ainsi, l’apprentissage consiste dans ce cas à définir une politique, c’est-à-dire une stratégie permettant d’obtenir systématiquement la meilleure récompense possible. Les applications principales de l’apprentissage par renforcement se trouvent dans les jeux (échecs, go, etc) et la robotique. Ce sujet dépasse largement le cadre de cet ouvrage. 1.3 Ressources pratiques 1.3.1 Implémentations logicielles De nombreux logiciels et librairies open source permettent de mettre en œuvre des algorithmes de machine learning. Nous en citons ici quelques uns : — Les exemples de ce livre ont été écrits en Python, grâce à la très utilisée librairie scikit-learn (http: //scikit-learn.org) dont le développement, soutenu entre autres par Inria et Télécom Paris- Tech, a commencé en 2007. — De nombreux outils de machine learning sont implémentés en R, et recensés sur la page http: //cran.r-project.org/web/views/MachineLearning.html — Weka (Waikato environment for knowledge analysis, https://www.cs.waikato.ac.nz/ml/weka/) est une suite d’outils de machine learning écrits en Java et dont le développement a commencé en 1993. — Shogun (http://www.shogun-toolbox.org/) interface de nombreux langages, et en particulier Python, Octave, R, et C#. Shogun, ainsi nommée d’après ses fondateurs Søren Sonnenburg et Gunnar Rätsch, a vu le jour en 1999. — De nombreux outils spécialisés pour l’apprentissage profond et le calcul sur des architectures distri- buées ont vu le jour ces dernières années. Parmi eux, TensorFlow (https://www.tensorflow.org) implémente de nombreux autres algorithmes de machine learning. 18 Chapitre 1. Présentation du machine learning 1.3.2 Jeux de données De nombreux jeux de données sont disponibles publiquement et permettent de se faire la main ou de tester de nouveaux algorithmes de machine learning. Parmi les ressources incontournables, citons : — Le répertoire de l’Université de Californie à Irvine, UCI Repository (http://www.ics.uci.edu/ ~mlearn/MLRepository.html) — Les ressources listées sur KDNuggets : http://www.kdnuggets.com/datasets/index.html — La plateforme de compétitions en sciences des données Kaggle (https://www.kaggle.com/) 1.4 Notations Autant que faire se peut, nous utilisons dans cet ouvrage les notations suivantes : — Les lettres minuscules (x) représentent un scalaire ; — les lettres minuscules surmontées d’une flèche (~x) représentent un vecteur ; — les lettres majuscules (X) représentent une matrice, un événement ou une variable aléatoire ; — les lettres calligraphiées (X ) représentent un ensemble ou un espace ; — les indices correspondent à une variable tandis que les exposants correspondent à une observation : xij est la j-ème variable de la i-ème observation, et correspond à l’entrée Xij de la matrice X ; — n est un nombre d’observations, p un nombre de variables, C un nombre de classes ; — [a]+ représente la partie positive de a ∈ R, autrement dit max(0, a). — P(A) représente la probabilité de l’événement A ; — δ est la fonction Dirac, c’est-à-dire. δ : X × X → {0, 1} ( 1 si u = v (u, v) 7→ 0 sinon ; — δz est la fonction indicatrice δz : {Vrai, Faux} → {0, 1} ( 1 si best vrai b 7→ 0 sinon ; — h.,.i représente le produit scalaire sur Rp ; — h.,.iH représente le produit scalaire sur H ; — M  0 signifie que M est une matrice symétrique semi-définie positive. Points clefs — Un algorithme de machine learning est un algorithme qui apprend un modèle à partir d’exemples, par le biais d’un problème d’optimisation. — On utilise le machine learning lorsqu’il est difficile ou impossible de définir les instructions explicites à donner à un ordinateur pour résoudre un problème, mais que l’on dispose de nombreux exemples illustratifs. — Les algorithmes de machine learning peuvent être divisés selon la nature du problème qu’ils cherchent à résoudre, en apprentissage supervisé, non supervisé, semi-supervisé, et par renforcement.  19 Pour aller plus loin Pour plus de détails sur l’estimation de densité, on consultera le livre de Scott (1992). Sur la régression structurée, on pourra se référer à BakIr et al. (2007). L’ouvrage de Barto (1998) est un bon point de départ pour se plonger dans le sujet de l’apprentissage par renforcement. Bibliographie BakIr, G., Hofmann, T., Schölkopf, B., Smola, A. J., Taskar, B., et Vishwanathan, S. V. N. (2007). Predicting Structured Data. MIT Press, Cambridge, MA. https://mitpress.mit.edu/books/ predicting-structured-data. Barto, R. S. et Sutton A. G. (1998). Reinforcement Learning : An Introduction. MIT Press, Cambridge, MA. http: //incompleteideas.net/book/the-book-2nd.html. Benureau, F. (2015). Self-Exploration of Sensorimotor Spaces in Robots. Thèse de doctorat, Université de Bor- deaux. Samuel, A. L. (1959). Some studies in machine learning using the game of checkers. IBM Journal of Research and Development, 44(1.2) :206–226. Scott, D. W. (1992). Multivariate density estimation. Wiley, New York. Chapitre 2 Apprentissage supervisé Dans cet ouvrage, nous nous intéresserons principalement aux problèmes d’apprentissage supervisé : il s’agit de développer des algorithmes qui soient capables d’apprendre des modèles prédictifs. À partir d’exemples étiquetés, ces modèles seront capables de prédire l’étiquette de nouveaux objets. Le but de ce chapitre est de développer les concepts généraux qui nous permettent de formaliser ce type de problèmes. Objectifs — Formaliser un problème comme un problème d’apprentissage supervisé ; — Choisir une fonction de coût ; — Lier la capacité d’un modèle à généraliser avec sa complexité. 2.1 Formalisation d’un problème d’apprentissage supervisé Un problème d’apprentissage supervisé peut être formalisé de la façon suivante : étant données n ob- servations {~x 1 , ~x 2 ,... , ~x n }, où chaque observation ~x i est un élément de l’espace des observations X , et leurs étiquettes {y 1 , y 2 ,... , y n }, où chaque étiquette y i appartient à l’espace des étiquettes Y, le but de l’apprentissage supervisé est de trouver une fonction f : X → Y telle que f (~x) ≈ y, pour toutes les paires (~x, y) ∈ X × Y ayant la même relation que les paires observées. L’ensemble de D = {(~x i , y i )}i=1,...,n forme le jeu d’apprentissage. Nous allons considérer dans cet ouvrage trois cas particuliers pour Y : — Y = R : on parle d’un problème de régression ; — Y = {0, 1} : on parle d’un problème de classification binaire, et les observations dont l’étiquette vaut 0 sont appelées négatives tandis que celles dont l’étiquette vaut 1 sont appelées positives. Dans certains cas, il sera mathématiquement plus simple d’utiliser Y = {−1, 1} ; — Y = {1, 2,... , C}, C > 2 : on parle d’un problème de classification multi-classe. Dans de nombreuses situations, on se ramènera au cas où X = Rp. On dira alors que les observations sont représentées par p variables. Dans ce cas, la matrice X ∈ Rn×p telle que Xij = xij soit la j-ème variable de la i-ème observation est appelée matrice de données ou matrice de design. 20 2.1. Formalisation d’un problème d’apprentissage supervisé 21 Le machine learning étant issu de plusieurs disciplines et champs d’applications, on trouvera plusieurs noms pour les mêmes objets. Ainsi les variables sont aussi appelées descripteurs, attributs, prédicteurs, ou caractéristiques (en anglais, variables, descriptors, attributes, predictors ou encore features). Les observations sont aussi appelées exemples, échantillons ou points du jeu de donnée (en anglais, samples ou data points). Enfin, les étiquettes sont aussi appelées variables cibles (en anglais, labels, targets ou outcomes). Ces concepts sont illustrés sur la figure 2.1. Figure 2.1 – Les données d’un problème d’apprentissage supervisé sont organisées en une matrice de de- sign et un vecteur d’étiquettes. Les observations sont représentées par leurs variables explicatives. 2.1.1 Décision Dans le cas d’un problème de classification, le modèle prédictif peut prendre directement la forme d’une fonction f à valeurs dans {0, 1}, ou utiliser une fonction intermédiaire g à valeurs réelles, qui associe à une observation un score d’autant plus élevé qu’elle est susceptible d’être positive. Ce score peut par exemple être la probabilité que cette observation appartienne à la classe positive. On obtient alors f en seuillant g ; g est appelée fonction de décision. Définition 2.1 (Fonction de décision) Dans le cadre d’un problème de classification binaire, on appelle fonction de décision, ou fonction discriminante, une fonction g : X 7→ R telle que f (~x) = 0 si et seulement si g(~x) ≤ 0 et f (~x) = 1 si et seulement si g(~x) > 0. Cette définition se généralise dans le cas de la classification multi-classe : on a alors C fonctions de décision gc : X 7→ R telles que f (~x) = arg maxc=1,...,C gc (~x).  Le concept de fonction de décision permet de partitionner l’espace en régions de décision : Définition 2.2 (Région de décision) Dans le cas d’un problème de classification binaire, la fonction discriminante partitionne l’espace des observations X en deux régions de décision, R0 et R1 , telles que R0 = {~x ∈ X |g(~x) ≤ 0} et R1 = {~x ∈ X |g(~x) > 0}. 22 Chapitre 2. Apprentissage supervisé Dans le cas multi-classe, on a alors C régions de décision Rc = {~x ∈ X |gc (~x) = max gk (~x)}. k  Les régions de décision sont séparées par des frontières de décision : Définition 2.3 (Frontière de décision) Dans le cadre d’un problème de classification, on appelle fron- tière de décision, ou discriminant, l’ensemble des points de X où une fonction de décision s’annule. Dans le cas d’un problème binaire, il y a une seule frontière de décision ; dans le cas d’un problème multi-classe à C classes, il y en a C.  2.1.2 Classification multi-classe Parmi les méthodes d’apprentissage supervisé que présente cet ouvrage, certaines permettent de ré- soudre directement des problèmes de classification multi-classe. Cependant, tout algorithme de classifi- cation binaire peut être utilisé pour résoudre un problème de classification à C classes, par une approche une-contre-toutes ou une approche une-contre-une. Définition 2.4 (Une-contre-toutes) Étant donné un problème de classification multi-classe à C classes, on appelle une-contre-toutes, ou one-versus-all, l’approche qui consiste à entraîner C classifieurs binaires. Le c-ème de ces classifieurs utilise tous les exemples de la classe c comme exemples positifs, et toutes les autres observations comme exemples négatifs, pour apprendre une fonction de décision gc. Ainsi, chaque classi- fieur apprend à distinguer une classe de toutes les autres. L’étiquette de ~x est donnée par celle des fonctions de décision qui retourne le score le plus élevé : f (~x) = arg max gc (~x). c=1,...,C  Définition 2.5 (Une-contre-une) Étant donné un problème de classification multi-classe à C classes, on appelle une-contre-une, ou one-versus-one, l’approche qui consiste à créer C(C − 1) classifieurs binaires séparant chacun une classe d’une autre, en ignorant tous les autres exemples. Soit gck la fonction de déci- sion du classifieur binaire qui sépare la classe c de la classe k. L’étiquette de ~x est déterminée selon :   X f (~x) = arg max  gck (~x). c=1,...,C k6=c  Il est difficile de dire laquelle de ces deux approches est la plus performante. En pratique, le choix sera souvent guidé par des considérations de complexité algorithmique : est-il plus efficace d’entraîner C modèles sur n observations, ou C(C − 1) modèles sur Cn observations (en supposant les classes équilibrées, autrement dit que D contient sensiblement autant d’exemples de chaque classe) ? Par ailleurs, on prendra aussi en compte le nombre d’exemples disponibles pour chaque classe : s’il est plus efficace d’entraîner un modèle sur peu de données, si ce nombre est trop faible, il sera difficile d’obtenir un modèle de bonne qualité. 2.2. Espace des hypothèses 23 2.2 Espace des hypothèses Pour poser un problème d’apprentissage supervisé, il nous faut décider du type de fonctions de modé- lisation que nous allons considérer. Définition 2.6 (Espace des hypothèses) On appelle espace des hypothèses l’espace de fonctions F ⊆ Y X décrivant les fonctions de modélisation que nous allons considérer. Cet espace est choisi en fonction de nos convictions par rapport au problème.  Dans l’exemple de la figure 2.2, on pourra décider de se restreindre à des discriminants qui soient des ellipses à axes parallèles aux axes de coordonnées. Ainsi, l’espace des hypothèse sera F = {~x 7→ α(x1 − a)2 + β(x2 − b)2 − 1}. Figure 2.2 – Les exemples positifs (+) et négatifs (x) semblent être séparables par une ellipse. Étant donnés un jeu de n observations étiquetées D = {(~x i , y i )}i=1,...,n et un espace d’hypothèses F. La tâche d’apprentissage supervisé consiste à supposer que les étiquettes y i ont été calculées grâce à une fonction φ : X → Y, et à trouver une hypothèse f ∈ F qui approche au mieux la fonction cible φ. Pour réaliser une telle tâche, nous allons avoir alors besoin de deux outils supplémentaires : 1. Une façon de quantifier la qualité d’une hypothèse, afin de pouvoir déterminer si une hypothèse satis- faisante (voire optimale) a été trouvée. Pour cela, nous allons définir dans la section 2.4 la notion de fonction de coût. 2. Une façon de chercher une hypothèse optimale dans F. Dans cet ouvrage, nous allons nous concentrer sur les méthodes d’apprentissage par optimisation : les algorithmes d’apprentissage supervisé que nous allons étudier auront pour but de trouver dans F l’hypothèse optimale au sens de la fonction de coût (cf. section 2.3). Différents algorithmes définiront différents F, et selon les cas cette recherche sera exacte ou approchée. Le choix de l’espace des hypothèses est fondamental. En effet, si cet espace ne contient pas la « bonne » fonc- tion, par exemple si l’on choisit comme espace des hypothèses pour les données de la figure 2.2 l’ensemble des droites, il sera impossible de trouver une bonne fonction de décision. Cependant, si l’espace est trop 24 Chapitre 2. Apprentissage supervisé générique, il sera plus difficile et intensif en temps de calcul d’y trouver une bonne fonction de modélisa- tion. 2.3 Minimisation du risque empirique Résoudre un problème d’apprentissage supervisé revient à trouver une fonction f ∈ F dont les pré- dictions soient les plus proches possibles des véritables étiquettes, sur tout l’espace X. On utilise pour formaliser cela la notion de fonction de coût : Définition 2.7 (Fonction de coût) Une fonction de coût L : Y ×Y → R, aussi appelée fonction de perte ou fonction d’erreur (en anglais : cost function ou loss function) est une fonction utilisée pour quantifier la qualité d’une prédiction : L(y, f (~x)) est d’autant plus grande que l’étiquette f (~x) est éloignée de la vraie valeur y.  Étant donnée une fonction de coût L, nous cherchons donc f qui minimise ce coût sur l’ensemble des valeurs possibles de ~x ∈ X , ce qui est formalisé par la notion de risque. Définition 2.8 (Risque) Dans le cadre d’un problème d’apprentissage supervisé, on appelle risque l’es- pérance d’une fonction de coût (voir chapitre 4 pour la modélisation probabiliste d’un problème d’appren- tissage supervisé) : R(h) = EX [L(h(~x), y)].  La fonction f que nous cherchons vérifie donc f = arg minh∈F E[L(h(~x), y)]. Ce problème est géné- ralement insoluble sans plus d’hypothèses : si nous connaissions les étiquettes de tous les points de X , nous n’aurions pas besoin d’apprentissage automatique. Étant données n observations étiquetées {(~x i , y i )}i=1,...,n , on approchera donc le risque par son estimation sur ces données observées Définition 2.9 (Risque empirique) Dans le cadre d’un problème d’apprentissage supervisé, étant don- nées n observations étiquetées {(~x i , y i )}i=1,...,n , on appelle risque empirique l’estimateur n 1X Rn (h) = L(h(~x i ), y i ). n i=1  Le prédicteur par minimisation du risque empirique est donc n 1X f = arg min L(h(~x i ), y i ). (2.1) h∈F n i=1 Selon le choix de F, l’équation 2.1 peut avoir une solution analytique explicite. Cela ne sera pas souvent le cas ; cependant on choisira souvent une fonction de coût convexe afin de résoudre plus facilement ce problème d’optimisation (voir l’annexe A sur l’optimisation convexe). La minimisation du risque empirique est généralement un problème mal posé au sens de Hadamard, c’est-à-dire qu’il n’admet pas une solution unique dépendant de façon continue des conditions initiales. Il se peut par exemple qu’un nombre infini de solutions minimise le risque empirique à zéro (voir figure 2.3). 2.4. Fonctions de coût 25 Figure 2.3 – Une infinité de droites séparent parfaitement les points positifs (+) des points négatifs (x). Chacune d’entre elles a un risque empirique nul. De plus, le prédicteur par minimisation du risque empirique n’est pas statistiquement consistant. Rap- pelons qu’un estimateur θn (dépendant de n observations) d’un paramètre θ est consistant s’il converge en probabilité vers θ quand n croit vers l’infini : ∀ > 0, lim P(|θn − θ| ≥ ) = 0. (2.2) n→∞ La loi des grands nombres nous garantit que le risque empirique converge vers le risque : ∀h ∈ F, Rn (h) −−−→ R(h). (2.3) n→∞ Cela ne suffit cependant pas à garantir que le minimum du risque empirique minh∈F Rn (h) converge vers le minimum du risque. En effet, si F est l’espace des fonctions mesurables, minh∈F Rn (h) vaut générale- ment 0, ce qui n’est pas le cas de R(h). Il n’y a donc aucune garantie que la fonction fn qui minimise Rn (h) soit un bon estimateur du minimiseur f de R(h). La consistance de la minimisation du risque empirique dépend de l’espace des versions F. L’étude de cette consistance est un des principaux éléments de la théorie de l’apprentissage de Vapnik-Chervonenkis, qui dépasse l’ambition de cet ouvrage. 2.4 Fonctions de coût Il existe de nombreuses fonctions de coût. Le choix d’une fonction de coût dépend d’une part du pro- blème en lui-même, autrement dit de ce que l’on trouve pertinent pour le cas pratique considéré, et d’autre part de considérations pratiques : peut-on ensuite résoudre le problème d’optimisation qui résulte de ce choix de façon suffisamment exacte et rapide ? Cette section présente les fonctions de coûts les plus cou- ramment utilisées et on pourra s’y référer tout au long de la lecture de cet ouvrage. 26 Chapitre 2. Apprentissage supervisé 2.4.1 Fonctions de coût pour la classification binaire Pour définir des fonctions de coût pour la classification binaire, on considèrera souvent Y = {−1, 1}. En effet, dans le cas d’une classification parfaite, le produit yf (~x) est alors égal à 1. Coût 0/1 pour la classification binaire Définition 2.10 (Coût 0/1 – classification binaire) Dans le cas d’une fonction f à valeurs binaires, on appelle fonction de coût 0/1, ou 0/1 loss, la fonction suivante : L0/1 : Y × Y → R ( 1 si f (~x) 6= y y, f (~x) 7→ 0 sinon.  En utilisant Y = {−1, 1}, on peut la réécrire de la manière suivante : 1 − yf (~x) L0/1 (y, f (~x)) =. 2 Quand on utilise cette fonction de coût, le risque empirique est le nombre moyen d’erreurs de prédiction. Si l’on considère pour f une fonction de décision (à valeurs réelles) plutôt qu’une fonction de prédiction à valeurs binaires, on peut définir la fonction de coût 0/1 comme suit : Coût 0/1 pour la régression Définition 2.11 (Coût 0/1 – régression) Quand on considère une fonction de décision à valeurs réelles, on appelle fonction de coût 0/1, ou 0/1 loss, la fonction suivante : L0/1 : Y × R → R ( 1 si yf (~x) ≤ 0 y, f (~x) 7→ 0 sinon.  L’inconvénient de cette fonction de coût est qu’elle n’est pas dérivable, ce qui compliquera les pro- blèmes d’optimisation l’utilisant. De plus, elle n’est pas très fine : l’erreur est la même que f (~x) soit très proche ou très loin du seuil de décision. Rappelons que pour une classification parfaite, quand Y = {−1, 1}, yf (~x) = 1. On peut ainsi définir une fonction de coût qui soit d’autant plus grande que yf (~x) s’éloigne de 1 à gauche ; on considère qu’il n’y a pas d’erreur si yf (~x) > 1. Cela conduit à la définition d’erreur hinge, ainsi appelée car elle forme un coude, ou une charnière (cf. figure 2.4). Erreur hinge 2.4. Fonctions de coût 27 Définition 2.12 (Erreur hinge) On appelle fonction d’erreur hinge, ou hinge loss, la fonction suivante : Lhinge : {−1, 1} × R → R ( 0 si yf (~x) ≥ 1 y, f (~x) 7→ 1 − yf (~x) sinon. De manière plus compacte, l’erreur hinge peut aussi s’écrire Lhinge (f (~x), y) = max (0, 1 − yf (~x)) = [1 − yf (~x)]+.  On peut aussi considérer que f (~x) doit être la plus proche possible de 1 pour les observations positives (et −1 pour les observations négatives). Ainsi, on pénalisera aussi les cas où yf (~x) s’éloigne de 1 par la droite, ce que l’on peut faire avec le coût quadratique. Coût quadratique pour la classification binaire Définition 2.13 (Coût quadratique) Dans le cadre d’un problème de classification binaire, on appelle coût quadratique, ou square loss, la fonction suivante : Lsquare : {−1, 1} × R → R y, f (~x) 7→ (1 − yf (~x))2.  Enfin, on peut chercher à définir une fonction de décision dont la valeur absolue quantifie notre confiance en sa prédiction. On cherche alors à ce que yf (~x) soit la plus grande possible, et on utilise le coût logistique. Coût logistique Définition 2.14 (Coût logistique) On appelle fonction de coût logistique, ou logistic loss, la fonction sui- vante : Llog : {−1, 1} × R → R y, f (~x) 7→ log (1 + exp(−yf (~x))).  Si l’on préfère utiliser Y = {0, 1}, le coût logistique est équivalent à l’entropie croisée. Entropie croisée Définition 2.15 (Entropie croisée) Dans le cas binaire, on appelle entropie croisée, ou cross-entropy, la fonction suivante : LH : {0, 1}×]0, 1[ → R y, f (~x) 7→ −y log f (~x) − (1 − y) log(1 − f (~x)).  28 Chapitre 2. Apprentissage supervisé Remarque L’entropie croisée est issue de la théorie de l’information, d’où son nom. En considérant que la véritable classe de ~x est modélisée par une distribution Q, et sa classe prédite par une distribution P , nous allons chercher à modéliser P de sorte qu’elle soit la plus proche possible de Q. On utilise pour cela la divergence de Kullback-Leibler : X Q(y = c|~x KL(Q||P ) = Q(y = c|~x) log P (y = c|~x) c=0,1 X X =− Q(y = c|~x) log P (y = c|~x) + Q(y = c|~x) log Q(y = c|~x) c=0,1 c=0,1 Comme Q(y = c|~x) vaut soit 0 (c n’est pas la classe de ~x) soit 1 (dans le cas contraire), le deuxième terme de cette expression est nul et on retrouve ainsi la définition ci-dessus de l’entropie croisée. Les fonctions de perte pour la classification binaire sont illustrées sur la figure 2.4. Figure 2.4 – Fonctions de perte pour la classification binaire. 2.4.2 Coûts pour la classification multi-classe Entropie croisée La définition de l’entropie croisée dans le cas binaire se généralise naturellement au cas multi-classe en considérant C fonctions de décision fc : X → Y. 2.4. Fonctions de coût 29 Définition 2.16 (Entropie croisée) Dans le cas multi-classe, on appelle entropie croisée, ou cross-entropy, la fonction suivante : LH : {1, 2,... , C} × R → R C X y, f (~x) 7→ − δ(y, c) log fc (~x) = − log fy (~x). c=1  Extension de la fonction d’erreur hinge Plusieurs propositions permettent de généraliser la fonction d’erreur hinge au cas multi-classe. Dans tous les cas, il s’agit d’assurer que la fonction de décision pour la véritable classe de ~x, fy (~x), prend une valeur supérieure à toutes les autres fonctions de décision fc (~x), c 6= y. Weston and Watkins (1999) proposent la définition suivante : X Lhinge (y, f (~x)) = [1 + fc (~x) − fy (~x)]+. c6=y Crammer and Singer (2001), eux, utilisent un maximum plutôt qu’une somme : définition suivante :   Lhinge (y, f (~x)) = 1 + max fc (~x) − fy (~x). c6=y + Ces fonctions de coût sont rarement utilisées en pratique, et on a tendance à leur préférer l’utilisation de la perte hinge binaire dans une approche une-contre-une ou une-contre-toutes. 2.4.3 Coûts pour la régression Dans le cas d’un problème de régression, nous considérons maintenant Y = R. Le but de notre fonction de coût est de pénaliser les fonctions de prédiction f dont la valeur est éloignée de la valeur cible ~x. Coût quadratique Définition 2.17 (Coût quadratique) On appelle fonction de coût quadratique, ou quadratic loss, ou encore squared error, la fonction suivante : LSE : R × R → R 1 y, f (~x) 7→ (y − f (~x))2. 2  Le coefficient 12 permet d’éviter d’avoir des coefficients multiplicateurs quand on dérive le risque em- pirique pour le minimiser. 30 Chapitre 2. Apprentissage supervisé Coût -insensible Le coût quadratique a tendance à être dominé par les valeurs aberrantes : dès que quelques observations dans le jeu de données ont une prédiction très éloignée de leur étiquette réelle, la qualité de la prédiction sur les autres observations importe peu. On peut ainsi lui préférer le coût absolu : Définition 2.18 (Coût absolu) On appelle fonction de coût absolu, ou absolute error, la fonction suivante : LAE : R × R → R y, f (~x) 7→ |y − f (~x)|.  Avec cette fonction de coût, même les prédictions très proches de la véritable étiquette sont pénalisées (même si elles le sont faiblement). Cependant, il est numériquement quasiment impossible d’avoir une prédiction exacte. Le coût -insensible permet de remédier à cette limitation. Définition 2.19 (Coût -insensible) Étant donné  > 0, on appelle fonction de coût -insensible, ou - insensitive loss, la fonction suivante : L : R × R → R y, f (~x) 7→ max (0, |y − f (~x)| − ).  Coût de Huber Le coût -insensible n’est dérivable ni en − ni en +, ce qui complique l’optimisation du risque empi- rique. La fonction de coût de Huber permet d’établir un bon compromis entre le coût quadratique (dérivable en 0) et le coût absolu (qui n’explose pas dans les valeurs extrêmes). Définition 2.20 (Coût de Huber) On appelle fonction de coût de Huber, ou Huber loss, la fonction suivante : LHuber : R × R → R ( 1 2 (y − f (~x))2 si |y − f (~x)| <  y, f (~x) 7→ |y − f (~x)| − 12 2 sinon.  Le terme − 12 2 permet d’assurer la continuité de la fonction. Les fonctions de coût pour la régression sont illustrées sur la figure 2.5. 2.5 Généralisation et sur-apprentissage 2.5.1 Généralisation Imaginons un algorithme qui, pour prédire l’étiquette d’une observation ~x, retourne son étiquette si ~x appartient aux données dont l’étiquette est connue, et une valeur aléatoire sinon. Cet algorithme aura une erreur empirique minimale quelle que soit la fonction de coût choisie, mais fera de très mauvaises prédictions pour toute nouvelle observation. Ce n’est pas vraiment ce que l’on a en tête quand on parle d’apprentissage. 2.5. Généralisation et sur-apprentissage 31 Figure 2.5 – Fonctions de coût pour un problème de régression. Attention Ainsi, évaluer un algorithme de machine learning sur les données sur lesquelles il a appris ne nous permet absolument pas de savoir comment il se comportera sur de nouvelles données, en d’autres mots, sa capacité de généralisation. C’est un point essentiel ! Définition 2.21 (Généralisation) On appelle généralisation la capacité d’un modèle à faire des prédic- tions correctes sur de nouvelles données, qui n’ont pas été utilisées pour le construire.  2.5.2 Sur-apprentissage L’exemple, certes extrême, que nous avons pris plus haut, illustre que l’on peut facilement mettre au point une procédure d’apprentissage qui produise un modèle qui fait de bonnes prédictions sur les données utilisées pour le construire, mais généralise mal. Au lieu de modéliser la vraie nature des objets qui nous intéressent, un tel modèle capture aussi (voire surtout) un bruit qui n’est pas pertinent pour l’application considérée. En effet, dans tout problème d’apprentissage automatique, nos données sont inévitablement bruitées — par des erreurs de mesure dues à la faillibilité des capteurs utilisés pour mesurer les variables par lesquelles on représente nos données, ou à la faillibilité des opérateurs humains qui ont entré ces mesures dans une base de données ; 32 Chapitre 2. Apprentissage supervisé — par des erreurs d’étiquetage (souvent appelés teacher’s noise en anglais) dues à la faillibilité des opéra- teurs humains qui ont étiqueté les données ; — enfin, parce que les variables mesurées ne suffisent pas à modéliser le phénomène qui nous intéresse, soit qu’on ne les connaisse pas, soit qu’elles soient coûteuses à mesurer. Exemple Supposons que nous voulions classifier des photographies selon qu’elles représentent des pandas ou non. Chaque image est représentée par les valeurs RGB des pixels qui la composent. Nous aimerions faire en sorte que le modèle que nous construisons capture la véritable nature d’un panda. Nous pouvons cependant être exposés à des erreurs de mesure (erreurs techniques des capteurs de l’appareil photo) ainsi que des erreurs d’étiquetage (erreurs de la personne qui a dû décider, pour chaque photo, s’il s’agissait ou non d’un panda, et a pu cliquer sur le mauvais choix, ou confondre un panda avec un ours). De plus, nous sommes limités par notre choix de variables : nos pixels ne capturent pas directement le fait qu’un panda est un animal rondouillard, avec un masque autour des yeux, généralement entouré de bambous. Remarque On voit ici que le choix des variables utilisées pour représenter les données est une étape très impor- tante du processus de modélisation. Nous verrons d’ailleurs au chapitre 7 que la puissance des réseaux de neurones profonds qui sont si populaires de nos jours vient de leur capacité à extraire des données une re- présentation pertinente. Les techniques présentées dans le chapitre 11 pourront être utilisées pour guider le choix des variables prédictives à utiliser. Définition 2.22 (Sur-apprentissage) On dit d’un modèle qui, plutôt que de capturer la nature des objets à étiqueter, modélise aussi le bruit et ne sera pas en mesure de généraliser qu’il sur-apprend. En anglais, on parle d’overfitting.  Un modèle qui sur-apprend est généralement un modèle trop complexe, qui « colle » trop aux données et capture donc aussi leur bruit. À l’inverse, il est aussi possible de construire un modèle trop simple, dont les performances ne soient bonnes ni sur les données utilisées pour le construire, ni en généralisation. Définition 2.23 (Sous-apprentissage) On dit d’un modèle qui est trop simple pour avoir de bonnes performances même sur les données utilisées pour le construire qu’il sous-apprend. En anglais, on parle d’underfitting.  Ces concepts sont illustrés sur la figure 2.6a pour un problème de classification binaire et la figure 2.6b pour un problème de régression. 2.5.3 Compromis biais-variance Pour mieux comprendre le risque d’un modèle f : X → Y, nous pouvons le comparer à l’erreur minimale R∗ qui peut être atteinte par n’importe quelle fonction mesurable de X dans Y : c’est ce qu’on appelle l’excès d’erreur, et que l’on peut décomposer de la façon suivante :     ∗ ∗ R(f ) − R = R(f ) − min R(h) + min R(h) − R (2.4) h∈F h∈F 2.5. Généralisation et sur-apprentissage 33 (a) Pour séparer les observations négatives (x) des (b) Les étiquettes y des observations (représentées par observations positives (+), la droite pointillée sous- des points) ont été générées à partir d’un polynôme de apprend. La frontière de séparation en trait plein ne fait degré d = 3. Le modèle de degré d = 2 approxime très aucune erreur sur les données mais est susceptible de mal les données et sous-apprend, tandis que celui de de- sur-apprendre. La frontière de séparation en trait dis- gré d = 13, dont le risque empirique est plus faible, sur- continu est un bon compromis. apprend. Figure 2.6 – Sous-apprentissage et sur-apprentissage Le premier terme, R(f ) − minh∈F R(h), quantifie la distance entre le modèle f et le modèle optimal sur F. C’est ce que l’on appelle l’erreur d’estimation. Le second terme, minh∈F R(h) − R∗ , quantifie la qualité du modèle optimal sur F, autrement dit, la qualité du choix de l’espace des hypothèses. C’est ce que l’on appelle l’erreur d’approximation. Si F est l’ensemble des fonctions mesurables, alors l’erreur d’approximation est nulle. Ainsi, l’écriture 2.4 permet de décomposer l’erreur entre un terme qui découle de la qualité de l’espace des hypothèses et un autre qui découle de la qualité de la procédure d’optimisation utilisée. En pratique, sauf dans des cas très particuliers où cela est rendu possible par construction, il n’est pas possible de calcu- ler ces termes d’erreur. Cependant, cette écriture nous permet de comprendre le problème suivant : choisir un espace des hypothèses plus large permet généralement de réduire l’erreur d’approximation, car un mo- dèle plus proche de la réalité a plus de chances de se trouver dans cet espace. Cependant, puisque cet espace est plus vaste, la solution optimale y est aussi généralement plus difficile à trouver : l’erreur d’estimation, elle, augmente. C’est dans ce cas qu’il y a sur-apprentissage. Un espace des hypothèses plus large permet généralement de construire des modèles plus complexes : par exemple, l’ensemble des droites vs. l’ensemble des polynômes de degré 9 (cf. figure 2.6b). C’est une variante du principe du rasoir d’Ockham, selon lequel les hypothèses les plus simples sont les plus vraisem- blables. Il y a donc un compromis entre erreur d’approximation et erreur d’estimation : il est difficile de ré- duire l’une sans augmenter l’autre. Ce compromis est généralement appelé compromis biais-variance : l’er- reur d’approximation correspond au biais de la procédure d’apprentissage, tandis que l’erreur d’estimation correspond à sa variance. On retrouvera ce compromis dans l’estimation bayésienne de paramètres à la 34 Chapitre 2. Apprentissage supervisé section 4.3.3. Exemple Considérons pour un problème de régression un espace des hypothèses naïf qui ne contient que des fonctions constantes. Supposons que les étiquettes soient générées par une distribution normale centrée en a. Quelles que soient les données observées, la procédure d’apprentissage va construire un modèle qui retourne a quelle que soit l’observation concernée : la variance de la procédure par rapport au jeu de don- nées est très faible. À l’inverse, comme la fonction de prédiction apprise est très peu sensible au jeu de données, il y a un biais très important qui conduit à construire des prédicteurs qui retournent a pour toutes les observations. 2.5.4 Régularisation Plus un modèle est simple, et moins il a de chances de sur-apprendre. Pour limiter le risque de sur- apprentissage, il est donc souhaitable de limiter la complexité d’un modèle. C’est ce que permet de faire la régularisation, une technique que nous verrons plus en détail au cours de cet ouvrage (à commencer par le chapitre 6), et qui consiste à ajouter au terme d’erreur que l’on cherche à minimiser un terme qui mesure la complexité du problème (par exemple, dans le cas précédent, le degré du polynôme ou le nombre de coefficients du modèle). Ainsi, un modèle complexe qui a une erreur empirique faible peut être défavorisé face à une modèle plus simple, même si celui-ci présente une erreur empirique plus élevée. Points clefs — Les trois ingrédients d’un algorithme d’apprentissage supervisé sont : — l’espace des hypothèses, — la fonction de coût, — l’algorithme d’optimisation qui permet de trouver l’hypothèse optimale au sens de la fonction de coût sur les données (minimisation du risque empirique). — Le compromis biais-variance traduit le compromis entre l’erreur d’approximation, correspondant au biais de l’algorithme d’apprentissage, et l’erreur d’estimation, correspondant à sa variance. — La généralisation et le sur-apprentissage sont des préoccupations majeures en machine learning : comment s’assurer que des modèles entraînés pour minimiser leur erreur de prédiction sur les don- nées observées seront généralisables aux données pour lesquelles il nous intéresse de faire des pré- dictions ? Pour aller plus loin La notion de complexité d’un modèle a été formalisée par Vladimir Vapnik et Alexey Chervonenkis dans les années 1970, et est détaillée par exemple dans l’ouvrage de Vapnik (1995). Pour en savoir plus sur la théorie de l’apprentissage, on pourra se référer au livre de Kearns et Va- zirani (1994). On trouvera une discussion détaillée du compromis biais-variance dans Friedman (1997).  35 Bibliographie Crammer, K. and Singer, Y. (2001). On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2 :265–292. Friedman, J. H. (1997). On bias, variance, 0/1-loss and the curse of dimensionality. Data Mining and Knowledge Discovery, 1 :55–77. Kearns, M. J. et Vazirani, U. V. (1994). An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA. Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer, New York. Weston, J. and Watkins, C. (1999). Support vector machines for multi-class pattern recognition. In European Symposium on Artificial Neural Networks. Chapitre 3 Sélection de modèle et évaluation Nous avons formalisé au chapitre 2 l’apprentissage supervisé comme la recherche d’un modèle dont l’erreur empirique est minimale sur un ensemble donné d’observations. Cependant, minimiser cette erreur empirique ne garantit pas de minimiser l’erreur du modèle sur la totalité de l’espace des données. En effet, dans une situation de sur-apprentissage, l’erreur du modèle sera sous-estimée. C’est cependant cette erreur, ou, en d’autres mots, notre capacité à faire des prédictions sur des choses qui ne sont pas connues, qui nous intéresse. Ce chapitre présente comment mettre en place un cadre expérimental qui permette d’évaluer un modèle en évitant le biais du sur-apprentissage. Dans cette optique, nous veillerons à distinguer l’évaluation d’un modèle, qui consiste à déterminer sa performance sur l’espace des données dans sa totalité, de sa sélection, qui consiste à choisir le meilleur modèle parmi plusieurs. Objectifs — concevoir un cadre expérimental dans l