Feuille Tage
Feuille Tage
Feuille Tage
Introduction
au Machine
Learning
“TP18-0200-1” (Col.:ScienceSup17x24) — 31/07/2018 16:32 — page ii — #0
Introduction
au Machine
Learning
Chloé-Agathe Azencott
Chargée de recherche au CBIO (Centre de bio-informatique)
de MINES ParisTech, de l’Institut Curie et de l’INSERM
Enseignante à CentraleSupelec
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page iv — #0
© Dunod, 2018
11 rue Paul Bert, 92240 Malakoff
www.dunod.com
ISBN 978-2-10-078080-8
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page v — #0
PRÉAMBULE
v
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page vi — #0
Préambule
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’opti-
misation (chapitre 1) et pose en annexe les bases d’optimisation 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’apprentissage
supervisé paramétriques (chapitre 5). Le chapitre 6 présente les variantes régulari-
sé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). Sui-
vront 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 chapitre 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 premiers 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.
vi
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page vii — #0
Préambule
Remerciements : Cet ouvrage n’aurait pas vu le jour sans Jean-Philippe Vert, qui
m’a fait découvrir le machine learning, avec lequel 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 Mi-
ning 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 Tibshirani, 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.
Merci à Alix Deleporte, enfin, pour ses relectures et son soutien.
© Dunod - Toute reproduction non autorisée est un délit.
vii
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page viii — #0
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page ix — #0
ix
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page x — #0
CHAPITRE 6 • RÉGULARISATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.1 Qu’est-ce que la régularisation ? . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 La régression ridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3 Le lasso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.4 Elastic net . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
x
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:31 — page xi — #0
INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
xi
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 13:41 — page xii — #0
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 1 — #0
PRÉSENTATION DU
MACHINE LEARNING
1
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
INTRODUCTION
1
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 2 — #0
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 manifestement pas toutes les informa-
tions 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 ma-
chine learning pour qu’il en tire un modèle prédictif nous permettant d’apporter une
réponse à notre question.
2
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 3 — #0
Exemple
Voici quelques exemples de reformulation de problèmes de machine learning sous
la forme d’un problè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.
r Un vendeur en ligne peut chercher à modéliser des types représentatifs de clien-
tèle, à partir des transactions passées, en maximisant la proximité entre clients
et clientes affectés à un même type.
r Une compagnie automobile peut chercher à modéliser la trajectoire d’un véhi-
cule dans son environnement, à partir d’enregistrements vidéo de voitures, en
minimisant le nombre d’accidents.
3
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 4 — #0
4
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 5 — #0
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.
Classification binaire
Dans le cas où les étiquettes sont binaires, elles indiquent l’appartenance à une classe.
On parle alors de classification binaire.
© Dunod - Toute reproduction non autorisée est un délit.
Exemple
Voici quelques exemples de problèmes de classification binaire :
r Identifier si un email est un spam ou non.
r Identifier si un tableau a été peint par Picasso ou non.
5
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 6 — #0
Classification multi-classe
Dans le cas où les étiquettes sont discrètes, et correspondent donc à plusieurs 1
classes, on parle de classification multi-classe.
Définition 1.3 (Classification multi-classe)
Un problème d’apprentissage supervisé dans lequel l’espace des étiquettes est dis-
cret et fini, autrement dit Y = {1, 2, . . . , C} est appelé un problème de classification
multi-classe. C est le nombre de classes.
Exemple
Voici quelques exemples de problèmes de classification multi-classe :
r Identifier en quelle langue un texte est écrit.
r Identifier lequel des 10 chiffres arabes est un chiffre manuscrit.
r Identifier l’expression d’un visage parmi une liste prédéfinie de possibilités
(colère, tristesse, joie, etc.).
r Identifier à quelle espèce appartient une plante.
r 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 :
r Prédire le nombre de clics sur un lien.
r Prédire le nombre d’utilisateurs et utilisatrices d’un service en ligne à un moment
donné.
r Prédire le prix d’une action en bourse.
r Prédire l’affinité de liaison entre deux molécules.
r 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.
6
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 7 — #0
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.
Cette définition est très vague, et sera certainement plus claire sur des exemples.
© Dunod - Toute reproduction non autorisée est un délit.
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 clustering un problème d’apprentissage non super-
visé pouvant être formalisé comme la recherche d’une partition K k=1 Ck des n
observations {x i }i=1,...,n . Cette partition doit être pertinente au vu d’un ou plusieurs
critères à préciser.
7
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 8 — #0
Exemple
Voici quelques exemples de problèmes de partitionnement
r La segmentation de marché consiste à identifier des groupes d’usagers ou de
clients ayant un comportement similaire. Cela permet de mieux comprendre
leur profil, et cibler une campagne de publicité, des contenus ou des actions
spécifiquement vers certains groupes.
r 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.
r La compression d’image peut être formulée comme un problème de partitionne-
ment consistant à regrouper des pixels similaires pour ensuite les représenter
plus efficacement.
r La segmentation d’image consiste à identifier les pixels d’une image appartenant
à la même région.
r 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.
Réduction de dimension
La réduction de dimension est une autre famille importante de problèmes d’apprentis-
sage 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
8
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 9 — #0
mémoire nécessaire au stockage les données, mais aussi souvent d’améliorer les per-
formances 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’apprentissage non supervisé pou-
vant ê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.
Estimation de densité
Enfin, une grande famille de problèmes d’apprentissage non supervisé est en fait un
problème traditionnel 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.
plus, les étiquettes données par des humains sont susceptibles de reproduire des biais
humains, qu’un algorithme entièrement supervisé reproduira à son tour. L’apprentis-
sage 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.
9
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 10 — #0
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.
10
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 11 — #0
1.4 Notations
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 : xji 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 ;
• δ représente la fonction Dirac, c’est-à-dire
δ : X × X → {0, 1}
1 si u = v
(u, v) →
0 sinon ;
• δz représente la fonction indicatrice
δz : {Vrai, Faux} → {0, 1}
1 si b est vrai
b →
0 sinon ;
• ., . représente le produit scalaire sur Rp ;
• ., .H représente le produit scalaire sur H ;
• M 0 signifie que M est une matrice semi-définie positive.
© Dunod - Toute reproduction non autorisée est un délit.
Points clefs
r 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.
r 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.
r Les algorithmes de machine learning peuvent être divisés selon la nature du pro-
blème qu’ils cherchent à résoudre, en apprentissage supervisé, non supervisé,
semi-supervisé, et par renforcement.
11
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 12 — #0
Bibliographie
BakIr, G., Hofmann, T., Schölkopf, B., Smola, A. J., Taskar, B., et Vishwana-
than, 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 Introduc-
tion. 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 Bordeaux.
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.
Exercices
1.1 Alice veut écrire un programme qui utilise la fréquence des mots « science »,
« public », « accès », « université », « gouvernement », « financer », « éducation »,
« budget », « justice »et « loi » pour déterminer si un article traite ou non de politique
scientifique. Elle a commencé par annoter un millier d’articles selon leur sujet. Quel
genre de problème d’apprentissage automatique doit-elle résoudre ?
1.2 Parmi les problèmes suivants, lesquels se prêtent bien à être traités par le
machine learning ?
1. Déterminer l’horaire optimal pour poster un contenu sur une page web.
2. Déterminer le chemin le plus court entre deux nœuds dans un graphe.
3. Prédire le nombre de vélos à mettre en location à chaque station d’un système de
location de vélos citadins.
4. Évaluer le prix qu’un tableau de maître pourra atteindre lors d’une vente aux
enchères.
5. Débruiter un signal radio.
12
“TP18-0200” (Col.:ScienceSup17x24) — 30/07/2018 12:26 — page 13 — #0
Exercices
1.3 Benjamin dispose de 10 000 articles de journaux qu’il souhaite classer par
leur thématique. Doit-il utiliser un algorithme supervisé ou non supervisé ?
1.4 Les données de Cécile sont décrites par 10 variables. Elle aimerait cepen-
dant les représenter sur un graphique en deux dimensions. Quel type d’algorithme
d’apprentissage doit-elle utiliser ?
1.5 David gère un outil qui permet d’organiser les liens HTML qui ont été sau-
vegardés. Il souhaite suggérer des catégories auxquelles affecter un nouveau lien, en
fonction des catégories déjà définies par l’ensemble des utilisateurs du service. Quel
type d’algorithme d’apprentissage doit-il utiliser ?
1.6 Elsa veut examiner ses spams pour déterminer s’il existe des sous-types de
spams. Quel type d’algorithme d’apprentissage doit-elle utiliser ?
1.7 Tom Mitchell définit le machine learning comme suit : « Un programme in-
formatique est dit apprendre de l’expérience E pour la tâche T et une mesure de
performance P si sa performance sur T, comme mesurée par P, s’améliore avec l’ex-
périence E ». Fred écrit un programme qui utilise des données banquaires dans le but
de détecter la fraude bancaire. Que sont E, T, et P ?
Solutions
1.1 Apprentissage supervisé (classification binaire).
1.2 1, 3, 4. (2 se résout par des algorithmes de recherche sur graphe, 5 par des
algorithmes de traitement du signal).
13