Introduction Au Machine Learning
Introduction Au Machine Learning
au Machine
Learning
Big Data et Machine Learning
2e édition
Pirmin Lemberger, Marc Batty. . .
272 pages
Dunod, 2016
© Dunod, 2018
11 rue Paul Bert, 92240 Malakoff
[Link]
ISBN 978-2-10-078594-0
PRÉAMBULE
v
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
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
TABLE DES MATIÈRES
ix
Table des matières
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
Table des matières
INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
xi
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
Chapitre 1 r Présentation du machine learning
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
1.1 Qu’est-ce que le machine learning ?
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
Chapitre 1 r Présentation du machine learning
4
1.2 Types de problèmes de machine learning
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
Chapitre 1 r Présentation du machine learning
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
1.2 Types de problèmes de machine learning
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
Chapitre 1 r Présentation du machine learning
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
1.2 Types de problèmes de machine learning
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
Chapitre 1 r Présentation du machine learning
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
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
Chapitre 1 r Présentation du machine learning
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.
[Link]
Barto, R. S. et Sutton A. G. (1998). Reinforcement Learning : An Introduc-
tion. MIT Press, Cambridge, MA. [Link]
[Link].
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
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
2 APPRENTISSAGE
SUPERVISÉ
OBJECTIFS INTRODUCTION
14
2.1 Formalisation d’un problème d’apprentissage supervisé
attributs prédicteurs
variables explicatives features p
étiquette
variable cible
observations
exemples X y
n
échantillons
matrice de données
matrice de design
Figure 2.1 – Les données d’un problème d’apprentissage supervisé sont organisées
en une matrice de design 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 di-
rectement la forme d’une fonction f à valeurs dans {0, 1}, ou utiliser une fonction
© Dunod - Toute reproduction non autorisée est un délit.
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 pro-
babilité que cette observation appartienne à la classe positive. On obtient alors f en
seuillant g, qui est appelée fonction de décision.
15
Chapitre 2 r Apprentissage supervisé
16
2.2 Espace des hypothèses
exemples. Soit gck la fonction de décision du classifieur binaire qui sépare la classe
c de la classe k. L’étiquette de x est déterminée selon :
⎛ ⎞
= arg max ⎝
f (x) ⎠.
gck (x)
c=1,...,C k =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é algorith-
mique : 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 pren-
dra 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é.
17
Chapitre 2 r Apprentissage supervisé
Figure 2.2 – Les exemples positifs (+) et négatifs (x) semblent être
séparables par une ellipse.
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 » fonction, 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 générique,
il sera plus difficile et intensif en temps de calcul d’y trouver une bonne fonction de
modélisation.
É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.
18
2.3 Minimisation du risque empirique
y)].
R(h) = EX [L(h(x),
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 au-
tomatique. Étant données n observations étiquetées {( x i , yi )}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 données n observa-
tions étiquetées (x i , y i ) i=1,...,n , on appelle risque empirique l’estimateur
n
1
Rn (h) = L(h(x i ), y i ).
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).
© Dunod - Toute reproduction non autorisée est un délit.
La loi des grands nombres nous garantit que le risque empirique converge vers le
risque :
∀h ∈ F, Rn (h) −−−→ R(h). (2.3)
n→∞
19
Chapitre 2 r Apprentissage supervisé
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.
20
2.4 Fonctions de coût
L0/1 : Y × Y → R
1 =y
si f (x)
y, f (x) →
0 sinon.
1 − yf (
x)
x)) =
L0/1 (y, f ( .
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 :
L0/1 : Y × R → R
1 ≤0
si yf (x)
→
© Dunod - Toute reproduction non autorisée est un délit.
y, f (x)
0 sinon.
L’inconvénient de cette fonction de coût est qu’elle n’est pas dérivable, ce qui com-
pliquera les problè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).
21
Chapitre 2 r Apprentissage supervisé
Erreur hinge
Lhinge : {−1, 1} × R → R
0 ≥1
si yf (x)
→
y, f (x)
1 − yf (x) sinon.
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.
Lsquare : {−1, 1} × R → R
2
→ 1 − yf (x)
y, f (x) .
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
Si l’on préfère utiliser Y = {0, 1}, le coût logistique est équivalent à l’entropie
croisée.
22
2.4 Fonctions de coût
Entropie croisée
L’entropie croisée est issue de la théorie de l’information, d’où son nom. En consi-
dé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
à ce qu’elle soit la plus proche possible de Q. On utilise pour cela la divergence de
Kullback-Leibler :
Q(y = c|x)
KL(Q||P) = log
Q(y = c|x)
P(y = c|x)
c=0,1
=− log P(y = c|x)
Q(y = c|x) + log Q(y = c|x)
Q(y = c|x)
c=0,1 c=0,1
Les fonctions de perte pour la classification binaire sont illustrées sur la figure 2.4.
coût 0/1
coût quadratique
coût logistique
© Dunod - Toute reproduction non autorisée est un délit.
23
Chapitre 2 r Apprentissage supervisé
Coût quadratique
24
2.4 Fonctions de coût
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 :
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.
Coût de Huber
© Dunod - Toute reproduction non autorisée est un délit.
25
Chapitre 2 r Apprentissage supervisé
coût absolu
coût quadratique
coût ɛ-insensible
coût de Huber
26
2.5 Généralisation et sur-apprentissage
2.5.2 Sur-apprentissage
L’exemple, certes extrême, que nous avons pris plus haut, illustre que l’on peut fa-
cilement 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 mo-
dè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, les 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 ;
• par des erreurs d’étiquetage (souvent appelés teacher’s noise en anglais) dues à la
faillibilité des opérateurs 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 mau-
vais 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.
© Dunod - Toute reproduction non autorisée est un délit.
On voit ici que le choix des variables utilisées pour représenter les données est
une étape très importante 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 repré-
sentation pertinente. Les techniques présentées dans le chapitre 11 pourront être
utilisées pour guider le choix des variables prédictives à utiliser.
27
Chapitre 2 r Apprentissage supervisé
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.
(a) Pour séparer les observations négatives (x) des (b) Les étiquettes y des observations (représentées
observations positives (+), la droite pointillée sous- par des points) ont été générées à partir d’un poly-
apprend. La frontière de séparation en trait plein ne nôme de degré d = 3. Le modèle de degré d = 2
fait aucune erreur sur les données mais est suscep- approxime très mal les données et sous-apprend,
tible de sur-apprendre. La frontière de séparation en tandis que celui de degré d = 13, dont le risque
trait discontinu est un bon compromis. empirique est plus faible, sur-apprend.
28
2.5 Généralisation et sur-apprentissage
∗ ∗
R(f ) − R = R(f ) − min R(h) + min R(h) − R . (2.4)
h∈F h∈F
Exemple
© Dunod - Toute reproduction non autorisée est un délit.
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
29
Chapitre 2 r Apprentissage supervisé
modèle. C’est ce que permet de faire la régularisation, une technique que nous ver-
rons 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
r 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).
r Le compromis biais-variance traduit le compromis entre l’erreur d’approxi-
mation, correspondant au biais de l’algorithme d’apprentissage, et l’erreur
d’estimation, correspondant à sa variance.
r 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 minimi-
ser leur erreur de prédiction sur les données observées seront généralisables
aux données pour lesquelles il nous intéresse de faire des prédictions ?
Bibliographie
Crammer, K. et Singer, Y. (2001). On the algorithmic implementation of
multiclass kernel-based vector machines. J. Machine Learning Research,
2:265-292.
Friedman, J. H. (1997). On bias, variance, 0/1-loss and the curse of dimensio-
nality. Data Mining and Knowledge Discovery, 1:55-77.
30
Exercices
Exercices
2.1 Quels sont les avantages et inconvénients d’un modèle simple sur un modèle
complexe ?
2.2 Adèle veut identifier automatiquement lesquelles de ses photos de vacances
ont été prises en intérieur, en extérieur, de jour ou de nuit. Doit-elle plutôt utiliser
4 classifieurs binaires, 2 classifieurs binaires, ou un classifieur multi-classe ?
2.3 Bill a entraîné un modèle de classification binaire sur 1 000 observations.
Son modèle se trompe pour 10 de ses observations. Est-il en situation de sous-
apprentissage, de sur-apprentissage, ou aucune des deux ?
2.4 Claire a un problème de classification binaire. Ses données sont représentées
en deux dimensions. Elle considère l’ensemble de tous les cercles comme espace
des hypothèses. Combien de paramètres doit-elle déterminer ? Comment peut-elle
les déterminer ?
2.5 Dany cherche à résoudre un problème de classification binaire pour des don-
nées en deux dimensions. Il considère comme espace des hypothèses l’ensemble des
© Dunod - Toute reproduction non autorisée est un délit.
unions de m rectangles. Quel est l’avantage de cet espace des hypothèses ? Y a-t-il un
risque de sur-apprentissage ?
2.6 Pour un problème de classification binaire, représenter pour une observation
positive l’erreur 0/1, l’erreur hinge, l’erreur quadratique, et l’entropie croisée en fonc-
tion de la valeur de la fonction de décision pour cette observation. Faire de même avec
une observation négative.
2.7 Le bruit est une source d’erreurs dans le processus d’apprentissage. Ella
cherche donc à détecter les observations aberrantes dans son jeu de données.
Pouvez-vous lui suggérer une procédure ?
31
Chapitre 2 r Apprentissage supervisé
Solutions
2.1 Avantages : éviter le sur-apprentissage ; meilleure généralisation ; moins de
temps de calcul. Inconvénient : si le modèle est trop simple, mauvaises performances.
2.4
F = {
x → (x1 − a)2 + (x2 − b)2 − r2 }.
Il y a 3 paramètres à déterminer : a, b et r. Pour les déterminer, il faut choisir une
fonction de coût, par exemple, la perte 0/1, et minimiser le risque empirique.
2.5 Cet espace des hypothèses permet une modélisation très fine, lorsque m est
suffisamment grand. On pourra toujours minimiser le risque empirique. Cependant,
pour m grand, on augmente le risque de sur-apprentissage.
2.6
coût 0/1
coût quadratique
entropie croisée
2.7 Les observations aberrantes sont difficiles à étiqueter correctement car elles
ne suivent pas la même loi que les autres observations. Ella peut donc s’intéresser
aux observations pour lesquelles le risque empirique est le plus grand.
32
SÉLECTION DE MODÈLE
ET ÉVALUATION
3
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 er-
INTRODUCTION
d’apprentissage supervisé.
Choisir un ou des critères d’évaluation d’un modèle d’apprentissage
supervisé.
Estimer la performance en généralisation d’un modèle d’apprentissage
supervisé.
empirique peut être proche de zéro voire nulle, tandis que l’erreur de généralisation
peut être arbitrairement grande.
Comme nous n’avons pas utilisé le jeu de test pour entraîner notre modèle, il peut
être considéré comme un jeu de données « nouvelles ». La perte calculée sur ce jeu
de test est un estimateur de l’erreur de généralisation.
Mais quelle est son erreur de généralisation ? Comme nous avons utilisé Dte pour
sélectionner le modèle, il ne représente plus un jeu indépendant composé de données
nouvelles, inutilisées pour déterminer le modèle.
La solution est alors de découper notre jeu de données en trois parties :
• un jeu d’entraînement Dtr sur lequel nous pourrons entraîner nos K algorithmes
d’apprentissage ;
• un jeu de validation (validation set en anglais) Dval sur lequel nous évaluerons les
K modèles ainsi obtenus, afin de sélectionner un modèle définitif ;
• un jeu de test Dte sur lequel nous évaluerons enfin l’erreur de généralisation du
modèle choisi.
34
3.1 Estimation empirique de l’erreur de généralisation
On voit ici qu’il est important de distinguer la sélection d’un modèle de son
évaluation : les faire sur les mêmes données peut nous conduire à sous-estimer
l’erreur de généralisation et le sur-apprentissage du modèle choisi.
Une fois un modèle sélectionné, on peut le réentraîner sur l’union du jeu
d’entraînement et du jeu de validation afin de construire un modèle final.
35
Chapitre 3 r Sélection de modèle et évaluation
• soit évaluer la qualité de chacun des K prédicteurs sur le jeu de test Dk cor-
respondant, et moyenner leurs performances. Cette deuxième approche permet
aussi de rapporter l’écart-type de ces performances, ce qui permet de se faire une
meilleure idée de la variabilité de la qualité des prédictions en fonction des données
d’entraînement.
Stratification
Leave-one-out
Un algorithme d’apprentissage apprendra d’autant mieux qu’il y a d’avantage de
données disponibles pour l’entraînement : plus on connaît d’étiquettes pour des ob-
servations de l’espace X, plus on peut contraindre le modèle à les respecter. Or pour
un jeu de données de taille n, un jeu de test d’une validation croisée à K folds contient
(K−1)n
K points : les modèles entraînés apprendront d’autant mieux sur chacun des folds
qu’ils sont grands, ce qui nous pousse à considérer le cas où K = n.
Définition 3.4 (Validation croisée leave-one-out)
Une validation croisée dont le nombre de folds est égal au nombre d’observations
dans le jeu d’entraînement, et dont chaque fold est donc composé d’un jeu d’entraî-
nement de taille n − 1 et d’un jeu de test de taille 1, est appelée leave one out (on
met de côté, pour chaque fold, un unique exemple).
L’évaluation par leave-one-out présente deux inconvénients. Tout d’abord, elle re-
quiert un grand temps de calcul : on entraîne n modèles, chacun sur n−1 observations,
au lieu de (dans le cas K = 10) 10 modèles, chacun sur 90 % des observations. De
plus, les jeux d’entraînement ainsi formés sont très similaires entre eux. Les modèles
36
3.2 Critères de performance
entraînés seront eux aussi très similaires, et généralement peu différents d’un modèle
entraîné sur l’intégralité du jeu de données. Par contre, les jeux de test seront disjoints,
et les performances pourront ainsi avoir une grande variabilité, ce qui compliquera
leur interprétation.
3.1.4 Bootstrap
Une autre façon de rééchantillonner les données afin d’estimer l’erreur de généralisa-
tion est connue sous le nom de bootstrap.
Définition 3.5 (Bootstrap)
Étant donné un jeu D de n observations, et un nombre B, on appelle bootstrap la
procédure qui consiste à créer B échantillons D1 , D2 , . . . , DB de D, obtenus cha-
cun en tirant n exemples de D avec remplacement. Ainsi, chaque exemple peut
apparaître plusieurs fois, ou pas du tout, dans Db .
La probabilité que (x i , y i ) apparaisse dans Db peut être calculée comme le com-
plémentaire à 1 de la probabilité que (x i , y i ) ne soit tiré aucune des n fois. La
probabilité de (x i , y i ) soit tiré une fois vaut 1n . Ainsi
i i 1 n
P[(x , y ) ∈ Db ] = 1 − 1 − .
n
Quand n est grand, cette probabilité vaut donc environ 1 − e−1 ≈ 0,632, car la
limite en +∞ de 1 + n x n vaut ex .
37
Chapitre 3 r Sélection de modèle et évaluation
Mais toutes les erreurs ne se valent pas nécessairement. Prenons l’exemple d’un
modèle qui prédise si oui ou non une radiographie présente une tumeur inquiétante :
une fausse alerte, qui sera ensuite infirmée par des examens complémentaires, est
moins problématique que de ne pas déceler la tumeur et de ne pas traiter la personne
concernée. Les performances d’un modèle de classification, binaire comme multi-
classe, peuvent être résumée dans une matrice de confusion.
Classe réelle
0 1
Classe 0 vrais négatifs (TN) faux négatifs (FN)
prédite 1 faux positifs (FP) vrais positifs (TP)
On appelle vrais positifs (en anglais true positives) les exemples positifs correc-
tement classifiés ; faux positifs (en anglais false positives) les exemples négatifs
étiquetés positifs par le modèle ; et réciproquement pour les vrais négatifs (true
negatives) et les faux négatifs ( false negatives). On note généralement TP le nombre
de vrais positifs, FP le nombre de faux positifs, TN le nombre de vrais négatifs et
FN le nombre de faux négatifs.
Les faux positifs sont aussi appelés fausses alarmes ou erreurs de type I, par
opposition aux erreurs de type II qui sont les faux négatifs.
Il est cependant très facile d’avoir un bon rappel en prédisant que tous les exemples
sont positifs. Ainsi, ce critère ne peut pas être utilisé seul. On lui adjoint ainsi souvent
la précision :
38
3.2 Critères de performance
De même que l’on peut facilement avoir un très bon rappel au détriment de la
précision, il est aisé d’obtenir une bonne précision (au détriment du rappel) en faisant
très peu de prédictions positives (ce qui réduit le risque qu’elles soient erronées)
L’anglais distingue precision (la précision ci-dessus) et accuracy, qui est la pro-
portion d’exemples correctement étiquetés, soit le complémentaire à 1 du taux
d’erreur, aussi traduit par précision en français. On utilisera donc ces termes avec
précaution.
Exemple
© Dunod - Toute reproduction non autorisée est un délit.
Prenons l’exemple d’un test clinique pour illustrer ces différents critères. Il ne s’agit
pas ici d’un modèle d’apprentissage automatique, mais d’un frottis de dépistage
du cancer du col de l’utérus : il s’agit d’un examen beaucoup plus simple et moins
invasif qu’un examen histologique, qui doit être interprété par un expert, et servira
de vérité terrain.
Les résultats d’une expérience menée sur 4 000 femmes âgées de 40 ans et plus
sont présentés sur le tableau 3.1.
Le rappel est de 95 %, la spécificité de 94,5 %, mais la précision ne vaut que 47,5 %.
En effet, ce test est un bon outil de dépistage : la probabilité de n’avoir effective-
ment pas de cancer quand le frottis est négatif est élevée (3590/3600 ≈ 99,7 %).
Cependant, c’est un mauvais outil diagnostique, au sens où la probabilité de fausse
alarme est très élevée.
39
Chapitre 3 r Sélection de modèle et évaluation
Tableau 3.1 – Matrice de confusion pour une expérience sur le dépistage du cancer
du col de l’utérus par frottis.
Courbe ROC
Définition 3.11 (Courbe ROC)
On appelle courbe ROC, de l’anglais Receiver-Operator Characteristic la courbe
décrivant l’évolution de la sensibilité en fonction du complémentaire à 1 de la
spécificité, parfois appelé antispécificité, lorsque le seuil de décision change.
Le terme vient des télécommunications, où ces courbes servent à étudier si un
système arrive à séparer le signal du bruit de fond.
On peut synthétiser une courbe ROC par l’aire sous cette courbe, souvent abrégée
AUROC pour Area Under the ROC.
Un exemple de courbe ROC est présenté sur la figure 3.2. Le point (0, 0) apparaît
quand on utilise comme seuil un nombre supérieur à la plus grande valeur retournée
par la fonction de décision : ainsi, tous les exemples sont étiquetés négatifs. À l’in-
verse, le point (1, 1) apparaît quand on utilise pour seuil une valeur inférieure au plus
petit score retourné par la fonction de décision : tous les exemples sont alors étiquetés
positifs.
Pour construire la courbe ROC, on prend pour seuil les valeurs successives de la
fonction de décision sur notre jeu de données. Ainsi, à chaque nouvelle valeur de
seuil, une observation que l’on prédisait précédemment négative change d’étiquette.
Si cette observation est effectivement positive, la sensibilité augmente de 1/np (où
np est le nombre d’exemples positifs) ; sinon, c’est l’antispécificité qui augmente de
1/nn , où nn est le nombre d’exemples négatifs. La courbe ROC est donc une courbe
en escaliers.
40
3.2 Critères de performance
Un classifieur idéal, qui ne commet aucune erreur, associe systématique des scores
plus faibles aux exemples négatifs qu’aux exemples positifs. Sa courbe ROC suit
donc le coin supérieur gauche du carré [0, 1]2 ; il a une aire sous la courbe de 1.
La courbe ROC d’un classifieur aléatoire, qui fera sensiblement la même pro-
portion d’erreurs que de classifications correctes quel que soit le seuil utilisé, suit
la diagonale de ce carré. L’aire sous la courbe ROC d’un classifieur aléatoire vaut
donc 0,5.
Exemple
Pour illustrer la construction d’une courbe ROC, prenons l’exemple décrit sur le
tableau 3.2.
Étiquette + − + + − −
© Dunod - Toute reproduction non autorisée est un délit.
Pour un seuil supérieur à 0,9, les 6 exemples sont étiquetés négatifs. On commence
donc par le point (0,0). Pour un seuil entre 0,95 et 0,9, seule la première observation
est étiquetée positive. La sensibilité est donc de 1 3
tandis que l’antispécificité reste
nulle. On peut continuer ainsi jusqu’à utiliser un seuil inférieur à 0,1 :
Seuil > 0,9 0,8-0,9 0,6-0,8 0,4-0,6 0,3-0,4 0,1-0,3 < 0,1
TP/P 0 1/3 1/3 2/3 1 1 1
FP/P 0 0 1/3 1/3 1/3 2/3 1
41
Chapitre 3 r Sélection de modèle et évaluation
On peut enfin utiliser la courbe ROC pour choisir un seuil de décision, à partir de
la sensibilité (ou de la spécificité) que l’on souhaite garantir.
Courbe précision-rappel
La courbe précision-rappel vient souvent complémenter la courbe ROC.
Définition 3.12 (Courbe précision-rappel)
On appelle courbe précision-rappel, ou Precision-Recall curve en anglais, la courbe
décrivant l’évolution de la précision en fonction du rappel, lorsque le seuil de
décision change.
Pour synthétiser cette courbe, on peut utiliser l’aire sous celle-ci, souvent abrégée
AUPR pour Area Under the Precision-Recall curve.
Un exemple de courbe précision-rappel, pour les mêmes données que la figure 3.2,
est présenté sur la figure 3.4.
Pour le seuil le plus élevé, aucun exemple n’est étiqueté positif, et la précision n’est
donc pas définie. Par convention, on utilise généralement une précision de 1 si la
première observation à considérer est positive, et une précision de 0 sinon.
Exemple
Reprenons l’exemple précédent pour construire une courbe précision-rappel. Les
valeurs de la précision et du rappel sont les suivantes :
Seuil > 0,9 0,8-0,9 0,6-0,8 0,4-0,6 0,3-0,4 0,1-0,3 < 0,1
Rappel 0 1/3 1/3 2/3 1 1 1
Précision - 1 1/2 2/3 3/4 3/5 3/6
43
Chapitre 3 r Sélection de modèle et évaluation
1 2
n
MSE = f (x i ) − y i .
n
i=1
Pour mesurer l’erreur dans la même unité que la cible, on lui préfère souvent sa
racine :
Dans le cas où les valeurs cibles couvrent plusieurs ordres de grandeur, on pré-
x i ) à yi , afin de ne pas donner plus
fère parfois passer au log avant de comparer f (
d’importance aux erreurs faites pour des valeurs plus élevées.
44
3.2 Critères de performance
n 2
i
i=1 f (x ) − y
i
RSE = 2 .
n 1 n
i=1 y − n
i i
i=1 y
Ce coefficient indique à quel point les valeurs prédites sont corrélées aux valeurs
réelles ; attention, il sera élevé aussi si elles leur sont anti-corrélées.
45
Chapitre 3 r Sélection de modèle et évaluation
Points clefs
r Pour éviter le sur-apprentissage, il est essentiel lors de l’étape de sélection du
modèle de valider les différents modèles testés sur un jeu de données différent
de celui utilisé pour l’entraînement.
r Pour estimer la performance en généralisation d’un modèle, il est essentiel de
l’évaluer sur des données qui n’ont été utilisées ni pour l’entraînement, ni pour
la sélection de ce modèle.
r De nombreux critères permettent d’évaluer la performance prédictive d’un
modèle. On les choisira en fonction de l’application.
r Pour interpréter la performance d’un modèle, il peut être utile de le comparer à
une approche naïve.
46
Exercices
données D peuvent être représentées par, d’une part une représentation d’un
modèle, et d’autre part une représentation de la différence entre les prédic-
tions du modèle et leurs vraies étiquettes dans D. Le meilleur modèle est celui
pour lequel la somme des tailles de ces représentations est minimale : un bon
modèle permet de compresser efficacement les données.
r Pour une discussion détaillée des procédures de validation croisée, on pourra
consulter Arlot et Celisse (2010).
Bibliographie
Arlot, S. et Celisse, A. (2010). A survey of cross-validation procedures for model
selection. Statistics Surveys, 4:40-79.
Davis, J. et Goadrich, M. (2006). The relationship between Precision-Recall and
ROC curves. In Proceedings of the 23rd International Conference on Machine
Learning, ICML ’06, pages 233-240, New York, NY, USA. ACM.
Dodge, Y. et Rousson, V. (2004). Analyse de régression appliquée. Dunod.
Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition
Letters, 27:861-874.
Rissanen, J. (1978). Modeling by shortest data description. Automatica,
14(5):465-471.
Wolpert, D. H. et Macready, W. G. (1997). No free lunch theorems for
optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82.
Exercices
3.2 Agnès écrit un algorithme de détection de fraude bancaire. Une fraude non
détectée coûte plus cher à la banque que le traitement manuel d’une transaction qui
© Dunod - Toute reproduction non autorisée est un délit.
n’est en fait pas frauduleuse. Doit-elle en priorité s’intéresser au taux de faux positifs,
faux négatifs, vrais négatifs ou vrais positifs ?
3.3 Basile teste un algorithme de classification binaire qui retourne aléatoirement
« négatif » ou « positif » avec une probabilité de 0,5 pour chacune des classes. Le jeu
d’évaluation contient 85 % d’exemples positifs et 15 % d’exemples négatifs. Quels
seront l’accuracy, le rappel et la précision ?
3.4 Carole teste un algorithme de classification binaire qui étiquette toute obser-
vation comme positive. Le jeu d’évaluation contient 85 % d’exemples positifs et 15 %
d’exemples négatifs. Quels seront l’accuracy, le rappel et la précision ?
47
Chapitre 3 r Sélection de modèle et évaluation
Solutions
3.1 Un modèle qui a une bonne précision peut être peu performant, par exemple
dans le cas de la détection d’événements rares : un modèle qui prédit que toutes les
observations appartiennent à la classe majoritaire aura une très bonne précision, mais
sera peu performant au sens où il sera inutile.
3.2 Les faux négatifs sont ce qui coûte le plus cher à la banque et c’est l’aspect
sur lequel il faut se concentrer en priorité.
48
INFÉRENCE BAYÉSIENNE
4
Un des problèmes fondamentaux auxquels nous faisons face dans le
cadre du machine learning est celui de l’incertitude : notre compré-
INTRODUCTION
49
Chapitre 4 r Inférence bayésienne
la réalisation d’une loi de Bernoulli que de modéliser toutes les informations biochi-
miques qui ont pu aboutir à ce résultat. C’est dans ce cadre que nous allons maintenant
nous placer.
Chacun des éléments de cette équation joue un rôle bien précis et porte ainsi un
nom :
• P(Y = c) est la distribution a priori des étiquettes, avant d’avoir observé les
données ;
• P(x|Y = c) est la vraisemblance. Elle quantifie à quel point il est vraisemblable que
l’on observe la réalisation x de X sachant que la classe est c ;
50
4.1 Modèles génératifs pour la classification binaire
• P(Y = c|x ) est la distribution a posteriori des étiquettes, après avoir observé les
données.
Le dénominateur P( x ) est la probabilité marginale que x soit observée, indépen-
damment de sa classe. Il peut être réécrit sous la forme P( x ) = P(
x|Y = 0)P(Y = 0)
C
+ P(
x|Y = 1)P(Y = 1). Dans le cas multi-classe, on écrira P( x ) = c = 1 P(x|Y = c)
P(Y = c).
Exemple
Prenons le cas du dépistage du cancer du col de l’utérus par frottis sanguin. Ce test,
bien que simple à réaliser, est assez imprécis : il a une sensibilité (la proportion de
personnes atteintes pour lequel il est positif) d’environ 70 %1 , et une spécificité (la
proportion de personnes non atteintes pour lequel il est négatif) d’environ 98 %.
(Pour plus de détails sur la sensibilité et la spécificité, voir section 3.2.1.) De plus,
l’incidence de la maladie est d’environ 1 femme sur 10 0002 .
Quelle est la probabilité qu’une personne testée soit atteinte d’un cancer si le test
est positif ? C’est un problème d’inférence bayésienne.
Soient X une variable aléatoire à valeurs dans {0, 1} modélisant le résultat du test
(1 pour positif, 0 pour négatif), et Y une variable aléatoire à valeurs dans {0, 1}
modélisant le statut de la personne testée (1 pour malade, 0 pour non atteintes).
Inférence : Nous cherchons à calculer P(Y = 1|X = 1). Appliquons la loi de Bayes :
P(X = 1|Y = 1)P(Y = 1)
P(Y = 1|X = 1) = .
P(X = 1)
P(X = 1|Y = 1) n’est autre que la sensibilité du test, autrement dit, P(X = 1|Y = 1)
= 0,70. P(Y = 1) est l’incidence de la maladie, soit 10−4 . Enfin, P(X = 1) = P(X = 1|
Y = 1)P(Y = 1) + P(X = 1|Y = 0)P(Y = 0). Nous connaissons déjà les deux premiers
termes de cette équation. De plus, P(X = 1|Y = 0) = 1 − P(X = 0|Y = 0) = 1 − 0,98 =
0,02, et P(Y = 0) = 1 − P(Y = 1) = 0,9999. Ainsi,
0,70 × 10−4
P(Y = 1|X = 1) = = 0,0035.
0,70 × 10−4 + 0,02 × 0,9999
Prédiction : Ainsi, la probabilité qu’une personne dont le test est positif soit at-
teinte est seulement de 0,35 %. Sans autre information, P(Y = 0|X = 1) > P(Y = 0
|X = 1) et la règle de décision 4.1 retournera une prédiction négative pour tous les
© Dunod - Toute reproduction non autorisée est un délit.
tests positifs.
51
Chapitre 4 r Inférence bayésienne
La règle de décision par maximum a posteriori peut être reformulée comme ce que
l’on appelle un test du rapport de vraisemblance :
1 si ( x ) > P(Y=0)
P(Y=1)
ŷ = (4.4)
0 sinon.
52
4.2 Règles de décision
Dans le cas où l’on fait l’hypothèse d’égalité des distributions a priori, P(Y = 0) =
P(Y = 1) et l’on comparera le rapport de vraisemblance à 1.
Définition 4.3 (Décision par maximum de vraisemblance)
La règle de décision
1 = 1) > P(x|Y
si P(x|Y = 0)
ŷ =
0 sinon.
ou, de manière équivalente,
1 si >1
(x)
ŷ =
0 sinon.
est appelée règle de décision par maximum de vraisemblance.
Dans de nombreux cas, on préférera passer au log et évaluer le signe de log (x ).
Exemple
Supposons que nous disposions d’un échantillon d’une population de guppies,
parmi lesquels se trouvent des mâles et des femelles. Nous cherchons à détermi-
ner leur sexe, modélisé comme une variable aléatoire binaire Y (0 pour les mâles,
1 pour les femelles), uniquement à partir de leur longueur, modélisée comme
une variable aléatoire continue X . Nous allons supposer la distribution des lon-
gueurs des mâles normalement distribuée, centrée en 4 cm et d’écart-type 1 cm,
et celle des longueurs des femelles normalement distribuée, centrée en 6 cm, et
d’écart-type 1 cm.
P(x|Y = 0) ∼ N(4, 1) et P(x|Y = 1) ∼ N(6, 1).
Le rapport de vraisemblance s’écrit
2
P(x|Y = 1) e−(x−6) /2
=
P(x|Y = 0) e(x−4) /2
2
53
Chapitre 4 r Inférence bayésienne
valeur seuil en accord avec notre connaissance a priori du problème. Cette règle de
décision est illustrée sur la figure 4.1b.
(a) Si les deux classes sont également probables, (b) Si un poisson a cinq fois plus de chances a priori
les poissons dont la taille est inférieure à 5 cm sont d’être femelle, les poissons dont la taille est infé-
étiquetés mâles et les autres femelles. rieure à 4,58 cm sont étiquetés mâles et les autres
femelles.
Figure 4.1 – Règle de décision pour le sexe d’un guppy en fonction de sa taille.
Exemple
Dois-je prendre ou non mon parapluie ce matin ? Nous pouvons modéliser ce pro-
blème de la façon suivante : A contient deux actions (« prendre mon parapluie » et
« ne pas prendre mon parapluie »). Y contient les vérités « il ne pleut pas », « il
pleut un peu », « il pleut fort », « il y a beaucoup de vent ». Enfin, X est un espace
décrivant les informations sur lesquelles je peux m’appuyer, comme les prévisions
météorologiques et la couleur du ciel quand je pars de chez moi. Je peux choisir la
fonction de coût suivante :
54
4.2 Règles de décision
Définir une stratégie qui minimise le risque de Bayes est équivalent à appliquer la
règle de décision de Bayes.
Coût 0/1
On retrouve le coût 0/1 (voir section 2.4) en utilisant λck = 1 − δ(k, c). L’équation 4.8
devient
1 si P(Y = 0| x ) ≤ P(Y = 1|x)
ŷ = (4.10)
0 sinon.
et ainsi la règle de décision de Bayes est équivalente à la règle décision par maximum
a posteriori. Ceci est vrai aussi dans le cas multi-classe.
Le coût 0/1 n’est pas la seule fonction de coût possible, même pour un problème
de classification binaire. En particulier, toutes les erreurs de classification ne sont pas
nécessairement également coûteuses. Par exemple, prédire qu’une patiente atteinte
d’un cancer est en bonne santé peut être largement plus problématique que l’inverse.
Régions de décision
Les règles de décision peuvent aussi s’exprimer en termes de régions de décision (cf.
section 2.1) : la règle de décision consiste simplement à étiqueter l’observation x en
accord avec la région de décision à laquelle elle appartient :
1 si x ∈ R1
ŷ = (4.11)
0 sinon.
56
4.2 Règles de décision
Cette règle de décision est équivalente à la règle de décision de Bayes si l’on définit
comme fonction discriminante la fonction :
x ) = (λ01 P(Y = 1|
f ( x ) + λ00 P(Y = 0| x )) −
(4.12)
(λ11 P(Y = 1|
x ) + λ10 P(Y = 0| x )) ,
ou, dans le cas multi-classe
C
x) = −
fc ( λck P(Y = k|
x ).
k=1
Définir les régions de décision de sorte à minimiser le risque de Bayes est équi-
valent à utiliser la fonction discriminante définie par l’équation 4.12. Cela vaut aussi
pour le cas multi-classe, où
C
C
r= λck P(
x|Y = c)P(Y = c) dx.
© Dunod - Toute reproduction non autorisée est un délit.
Rejet
Pour certaines applications, il peut être intéressant que l’algorithme refuse de prendre
une décision quand sa confiance en sa prédiction est faible, autrement dit, quand le
rapport de vraisemblance est très proche de 1. Dans ce cas, on pourra rajouter une
classe artificielle C + 1 de rejet. On peut adapter le coût 0/1 à ce cas en proposant
⎧
⎪
⎨0 si k = c
λck = λ si k = C + 1 (4.14)
⎪
⎩1 sinon,
57
Chapitre 4 r Inférence bayésienne
avec 0 < λ < 1. La règle de décision par minimisation de la perte espérée devient
alors
c si P(Y = c|
x ) ≥ P(Y = k|
x ) ∀k = c
ŷ = (4.15)
rejet sinon.
Dans ce cas, les régions de décision R1 , . . . RC ne couvrent pas X et leur
complémentaire est la zone de rejet.
Pour trouver θ̂MLE , nous allons supposer que les n observations sont indépendantes et
identiquement distribuées (ou iid). Cela nous permet de décomposer la vraisemblance
comme
n
P(D|θ) = P(X = x i |θ). (4.17)
i=1
Enfin, remarquons que pour simplifier les calculs, on choisira souvent de maximi-
ser non pas directement la vraisemblance mais son logarithme :
n
θ̂MLE = arg max log P(X = x i |θ). (4.18)
θ i=1
Exemple
Prenons l’exemple d’un jeu de pile ou face. Nous modélisons l’observation « pile » ou
« face » comme la réalisation d’une variable aléatoire X , définie sur l’univers X =
{0, 1} (0 correspondant à « pile » et 1 à « face »), et suivant une loi de probabilité P.
Un choix classique pour cette loi de probabilité est d’utiliser une loi de Bernoulli :
p si x = 1
P(X = x) = (4.19)
(1 − p) si x = 0,
58
4.3 Estimation de densité
et donc
n
1 i
p̂MLE = x . (4.20)
n
i=1
L’estimateur par maximum de vraisemblance de p est tout simplement la moyenne
de l’échantillon.
Exemple
Reprenons l’exemple du test de dépistage du cancer du col de l’utérus. Alors que
dans l’exemple précédent, P(X |Y = 0) et P(X |Y = 1) était données, nous allons main-
tenant les estimer à partir de données observées. Supposons que nous observions
un jeu D0 de n0 personnes non atteintes, parmi lesquelles t0 ont un test négatif,
© Dunod - Toute reproduction non autorisée est un délit.
59
Chapitre 4 r Inférence bayésienne
Nous pouvons remplacer dans cette équation p0 et p1 par leurs estimateurs par
maximum de vraisemblance (équation 4.20) :
t t
p̂0 = 1 − 0 et p̂1 = 1 . (4.21)
n0 n1
Il s’agit respectivement de la spécificité et de la sensibilité estimées du test. En
utilisant n0 = 0,98, nt1 = 0,70 et π = 10−5 , on retrouve les résultats précédents.
t
0 1
60
4.3 Estimation de densité
où B(α, β) = (α)(β)
(α+β)
α .
et est la fonction gamma. L’espérance de cette loi est α+β
Pour calculer l’estimateur de Bayes de p0 , il nous faut connaître la loi P(p0 |D0 ). La
loi de Bayes nous permet d’écrire
P(D0 |p0 )P(p0 )
P(p0 |D0 ) =
P(D0 )
n0
1 x i (1 − p )1−x i pα0 −1 (1 − p )β0 −1
= p0 0 0 (hypothèse iid)
P(D0 )B(α0 , β0 ) 0
i=1
1 n −t +α −1
= p 0 0 0 (1 − p0 )t0 +β0 −1 .
P(D0 )B(α0 , β0 ) 0
Ainsi p0 |D0 suit une distribution bêta de paramètres (n0 − t0 + α0 ) et (t0 + β0 ).
L’estimateur de Bayes de p0 est ainsi
(n0 − t0 + α0 ) n − t0 + α0
p̃0 = E[p0 |D0 ] = = 0 . (4.26)
(n0 − t0 + α0 ) + (t0 + β0 ) n0 + α0 + β0
En utilisant l’équation 4.21, on peut réécrire l’équation 4.26 sous la forme
n0 α0 + β0 α0
p̃0 = p̂ + .
n0 + α0 + β0 0 n0 + α0 + β0 α0 + β0
Quand le nombre d’observations n0 est grand, l’estimateur de Bayes p̃0 est proche
de l’estimateur par maximum de vraisemblance p̂0 . À l’inverse, si n0 est faible,
α0
l’estimateur de Bayes est proche de α +β qui est l’espérance de la distribution
0 0
a priori sur p0 . Ainsi, plus on a de données, plus on leur fait confiance et plus
l’estimateur s’éloigne de l’espérance a priori du paramètre, dont on sera plus proche
avec peu d’observations.
Le même raisonnement s’applique à p1 , dont l’estimateur de Bayes est
t1 + α1 n1 α1 + β1 α1
p̃1 = = p̂ + . (4.27)
n1 + α1 + β1 1 n1 + α1 + β1 α1 + β1
© Dunod - Toute reproduction non autorisée est un délit.
n1 + α1 + β1
61
Chapitre 4 r Inférence bayésienne
Cette dernière égalité est obtenue en remarquant que E[θ̂ ] − θ est déterministe
et que E[(E[θ̂ ] − θ)] = E[E[θ̂]] − E[θ] = 0. Ainsi l’erreur quadratique moyenne
d’un estimateur est la somme de sa variance et du carré de son biais. C’est pourquoi
un estimateur biaisé peut, si sa variance est plus faible, avoir une erreur quadra-
tique moyenne plus faible qu’un estimateur non biaisé. On retrouve ici la notion de
compromis biais-variance de la section 2.5.3.
4.4.1 Principes
Dans les exemples que nous avons vus jusqu’à présent, les variables aléatoires que
nous avons utilisées étaient unidimensionnelles. Cependant, dans la plupart des ap-
plications, les données sont multidimensionnelles. Cela peut grandement compliquer
les calculs, sauf dans le cas où nous faisons l’hypothèse naïve que les variables sont
conditionnellement indépendantes.
Supposons n observations en p dimensions : { x 1 , x 2 , . . . , x n } telles que x i ∈ Rp , et
leurs étiquettes y , y , . . . , y . Nous allons modéliser chacune des p variables comme
1 2 n
une variable aléatoire Xj . L’hypothèse d’indépendance conditionnelle signifie que
P(Xj = xj |Y = y, Xm = xm ) = P(Xj = xj |Y = y) ∀1 ≤ j = m ≤ p. (4.28)
Cette hypothèse permet d’écrire la vraisemblance de la façon suivante :
p
j=1 P(Xj = xj |Y = y)P(Y = y)
P(Y = y|X1 = x1 , X2 = x2 , . . . , Xp = xp ) =
P(X1 = x1, X2 = x2 , . . . , Xp = xp )
(4.29)
Définition 4.8 (Classifieur bayésien naïf)
On appelle classifieur bayésien naïf , ou naive Bayes classifier en anglais, un clas-
sifieur construit en appliquant la règle de décision par maximum a posteriori à
des observations multidimensionnelles dont on suppose que les variables sont
indépendantes conditionnellement à l’étiquette.
La règle de décision prend la forme
p
ŷ = arg max P(Y = c) P(Xj = xj |Y = c). (4.30)
c=1,...,C j=1
62
4.4 Classification naïve bayésienne
Maximum a posteriori
La règle de décision par maximum a posteriori (équation 4.30) est
p p
1 si P(Y = 1) j=1 P(Xj = xj |Y = 1) > P(Y = 0) j=1 P(Xj = xj |Y = 0)
ŷ =
0 sinon.
(4.31)
Inférence
© Dunod - Toute reproduction non autorisée est un délit.
Il nous reste donc à déterminer P(Y = 1), P(Y = 0) et, pour chaque variable Xj ,
P(Xj = xj |Y = 0) et P(Xj = xj |Y = 1).
P(Y = 1) est tout simplement la fréquence des spams dans notre jeu de données
d’entraînement, et P(Y = 0) = 1 − P(Y = 0) la fréquence des e-mails légitimes. On
peut aussi utiliser des statistiques sur la question, qui donnent la proportion de spams
parmi les e-mails qui circulent aux alentours de 80 %.
Comme nous avons fait le choix de modéliser Xj comme une variable aléatoire
x
suivant une loi de Bernoulli, P(Xj = xj |Y = 1) = pj j (1 − pj )1−xj . On pourrait utiliser,
S
pour estimer pj , l’estimateur par maximum de vraisemblance (équation 4.20) : p̂j = Sj
où Sj est le nombre de spams contenant le j-ème mot et S le nombre de spams dans
notre jeu de données.
63
Chapitre 4 r Inférence bayésienne
Cependant, cet estimateur est peu adapté aux mots rares : si notre j-ème mot
n’apparaît pas du tout dans le jeu d’entraînement, Sj = S = 0. Pour cette raison,
on préférera appliquer ce que l’on appelle un lissage de Laplace pour obtenir
l’estimateur suivant :
Sj + 1
p̂j = . (4.32)
S+2
Pour un mot qui n’apparaît pas dans le jeu d’entraînement, p̂j = 0,5.
Points clefs
r La modélisation d’un problème d’apprentissage de manière probabiliste se
divise en deux tâches :
un problème d’inférence, qui consiste à déterminer la loi de probabilité
P(Y = c|X ) ;
une tâche de prédiction, qui consiste à appliquer une règle de décision.
r Le raisonnement probabiliste s’appuie sur la loi de Bayes.
r Généralement, la loi de probabilité P(Y = c|X ) est modélisée de manière paramé-
trique et le problème d’inférence se résout en s’appuyant d’une part sur la loi de
Bayes, et d’autre part sur des estimateurs tels que l’estimateur par maximum de
vraisemblance ou l’estimateur de Bayes pour en déterminer les paramètres.
r La règle de décision de Bayes, qui consiste à minimiser l’espérance de la perte,
contraste avec la règle de minimisation du risque empirique.
64
Exercices
Bibliographie
Barber, D. (2012). Bayesian Reasoning and Machine Learning. Cambridge
University Press. [Link]
Hand, D. J. et Yu, K. (2001). Idiot’s Bayes: not so stupid after all? International
Statistical Review / Revue Internationale de Statistique, 69(3):385-398.
Murphy, K. P. (2013). Machine Learning: A Probabilistic Perspective. MIT
Press, Cambridge, MA, 4th edition. [Link]
MLbook/.
Ross, S. M. (1987). Introduction to Probability and Statistics for Engineers and
Scientists. Wiley, New York.
Exercices
65
Chapitre 4 r Inférence bayésienne
4.4 Charlotte a mélangé des cartons de verres en provenance de deux usines dif-
férentes. Elle veut donc construire un classifieur qui lui permette de réassigner chaque
carton à sa provenance en fonction de la proportion de verres cassés dans ce carton.
Elle sait avoir reçu 5 fois plus de verres de l’usine B que de l’usine A. Elle estime
deux fois plus problématique d’affirmer qu’un carton vient de l’usine A quand il est
en fait de l’usine B que l’inverse. Enfin, elle choisit de modéliser la proportion d’ob-
jets défectueux dans chacune des usines par une loi bêta ; comme elle sait que l’usine
A produit des verres un peu moins fragiles que l’usine B, elle choisit une loi de pa-
ramètres α = 2 et β = 11 pour l’usine A et une loi de paramètres α = 2 et β = 10
pour l’usine B.
Rappelons que pour n ∈ N, (n) = (n − 1)!.
1. Quelle fonction de coût choisir ?
2. Quelle est la règle de décision par maximum de vraisemblance ?
3. Quelle est la règle de décision par maximum a posteriori ?
4. Quelle est la règle de décision de Bayes ?
D’après un classifieur naïf bayésien, y a-t-il une corbeille de recyclage dans un petit
bureau d’étudiants du département de mathématiques ? Utiliser le lissage de Laplace.
66
Exercices
4.6 Considérons une variable aléatoire X pouvant prendre d valeurs. Nous repré-
sentons une observation de X par le vecteur x ∈ {0, 1}d , où xj vaut 1 si l’observation
prend la j-ème valeur et 0 sinon. Modélisons X par une loi multinomiale : chaque
x
valeur a une probabilité pj d’apparaître, dj=1 pj = 1, et P(X = x ) = dj=1 pj j .
Étant données n observations x 1 , x 2 , . . . , x n de X, calculer l’estimateur
n pari maximum
de vraisemblance de pj pour tout j = 1, . . . , d. On notera nj = i=1 xj le nombre
d’observations prenant la valeur j.
4.7 Considérons une variable aléatoire X suivant une loi normale de paramètres
μ et σ :
1 (x − μ)2
P(X = x|μ, σ ) = √ exp − .
2π 2σ 2
Solutions
4.1 Non.
4.3
© Dunod - Toute reproduction non autorisée est un délit.
67
Chapitre 4 r Inférence bayésienne
4.4
1. λAA = λBB = 0 ; λAB = 2 ; λBA = 1.
2. Appelons X la variable aléatoire réelle modélisant la proportion de verres cassés
dans un carton, et Y la variable aléatoire binaire modélisant la provenance du
carton. D’après les hypothèses de Charlotte,
(13)x(1 − x)10 (12)x(1 − x)9
P(X = x|Y = A) = et P(X = x|Y = B) = .
(2) + (11) (2) + (10)
La fonction discriminante par maximum de vraisemblance est
P(X = x|Y = A) 12
f (X = x) = − 1 = (1 − x) − 1
P(X = x|Y = B) 10
Charlotte estime que le carton provient de l’usine A si la proportion de verres
brisés est inférieure à 16 ≈ 0,17, et de l’usine B sinon.
3. La fonction discriminante par maximum a posteriori est
P(X = x|Y = A)P(Y = A) 1 12
f (X = x) = − 1 = × (1 − x) − 1
P(X = x|Y = B)P(Y = B) 5 10
Charlotte estime que le carton provient de l’usine A si la proportion de verres
25 = 0,76, et de l’usine B sinon. L’information a priori lui
brisés est inférieure à 19
fait fortement préférer la classe A.
4. La fonction discriminante de Bayes est f (X = x) = 2P(Y = A|X = x) − P(Y = B
|X = x) ou, de manière équivalente,
2P(X = x|Y = A)P(Y = A) 2 12
f (X = x) = − 1 = × (1 − x) − 1
P(X = x|Y = B)P(Y = B) 5 10
Charlotte estime que le carton provient de l’usine A si la proportion de verres
25 = 0,52, et de l’usine B sinon. La fonction de coût lui fait
brisés est inférieure à 13
modérer sa préférence pour la classe A.
Donc P(R|etud, maths, petit) > P(¬R|etud, maths, petit) et le robot de Dimitri prédit
la présence d’une corbeille de recyclage.
68
Exercices
d
Prenons l ∈ {1, . . . , d} \ {j}. La contrainte k=1 pk = 1 impose pl = 1 − k=l pk .
Le log de la vraisemblance s’écrit alors
⎛ ⎞
x 1 , x 2 , . . . , x n |p) = nj log pj + nl log ⎝1 − pj −
log P( pk ⎠ + nk log pk
k=j,l k=j,l
∂L nj nl
Il s’agit d’une fonction concave dont le gradient en pj vaut : ∂pj = pj − pl .
Pour la maximiser, on annule donc son gradient (voir section A.3.1). En annulant le
np
gradient du log de la vraisemblance, on obtient p̂j = nj l l pour tout j.
n
Comme dk=1 p̂k = 1, dk=1 nnk pl l = 1 et donc p̂j = nj .
4.7
1. En supposant les n observations iid, le log de vraisemblance vaut
n √ (xi − μ)2
log P(D|μ, σ ) = − log(σ 2π ) − .
2σ 2
i=1
∂L
Il s’agit d’une fonction concave dont le gradient en μ vaut ∂μ =
n i 1 n
1
σ2
nμ − i=1 x . En annulant ce gradient, on obtient μMLE = n i=1 xi
(moyenne empirique).
∂L
Le gradient en σ du log de la vraisemblance vaut ∂σ = −nσ 2 + ni=1 (xi −
μMLE )2 . En l’annulant, on obtient σMLE
2 = 1n ni=1 (xi − μMLE )2 et σMLE est donc
l’écart-type empirique.
2. L’estimateur de Bayes de μ est μ̂ = E[μ|D]. La densité de cette distribution est
donnée par
n ! n "
P(D|μ)P(μ) 1 1 (xi − μ)2 (μ − m)2
P(μ|D) = = √ exp − −
P(D) P(D) σ 2π 2σ 2 2τ 2
i=1
! "
1 (μ − a)2 1
= K1 exp − exp − K2
© Dunod - Toute reproduction non autorisée est un délit.
2 b2 2
n #
xi τ 2 +mσ 2 τ 2 +σ 2
où K1 et K2 ne dépendent pas de μ, a = i=1nτ 2 +σ 2 et b = nτ 2 +σ 2 .
L’intégrale d’une densité de probabilité vaut 1. Cela vaut pour la loi normale
centrée en a et d’écart-type b, comme pour P(μ|D), et donc K1 exp − 12 K2 = 1.
Ainsi,μ|D suit une loi normale centrée en a. Son espérance vaut donc a, et ainsi
n
i=1 x τ +mσ
i 2 2
μ̂ = nτ +σ
2 2 .
2 2
3. μ̂ = n/σn/σ 1/τ
2 +1/τ 2 μMLE + n/σ 2 +1/τ 2 m. Plus il y a de données et plus l’estimateur
de Bayes est proche de la moyenne empirique. Quand il y a peu de données,
l’estimateur de Bayes est plus proche de la valeur a priori du paramètre.
69
5 RÉGRESSIONS
PARAMÉTRIQUES
Un modèle de régression paramétrique suppose que la forme ana-
lytique de la fonction de décision est connue. Dans ce contexte, ce
chapitre se concentre principalement sur des problèmes de régression
linéaire, c’est-à-dire ceux pour lesquels la fonction de décision est une
INTRODUCTION
70
5.1 Apprentissage supervisé d’un modèle paramétrique
71
Chapitre 5 r Régressions paramétriques
et provient d’une
Dans cette dernière équation, C est une constante par rapport à β,
part du coefficient √ de la distribution normale et d’autre part des P(X = x i ).
1
2π
2
Ainsi, maximiser la vraisemblance revient à minimiser ni=1 yi − f (
x i |β) :
c’est ce que l’on appelle la minimisation des moindres carrés, une méthode bien
connue depuis Gauss et Legendre. Notons aussi que cela revient à minimiser le
risque empirique quand il est défini en utilisant la fonction de coût quadratique (voir
section 2.4.3).
5.2.1 Formulation
Nous choisissons une fonction de décision f de la forme
p
f : x → β0 + βj x j . (5.3)
j=1
Ici, β ∈ Rp+1 et donc m = p + 1.
5.2.2 Solution
Définition 5.1 (Régression linéaire)
p
On appelle régression linéaire le modèle de la forme f : x → β0 + j=1 βj xj dont
les coefficients sont obtenus par minimisation de la somme des moindres carrés, à
savoir :
72
5.2 Régression linéaire
⎛ ⎞2
n
p
arg min ⎝y i − β0 + β j xj ⎠ . (5.4)
p+1 i=1
β∈R j=1
Nous pouvons réécrire le problème 5.4 sous forme matricielle, en ajoutant une
colonne de 1 sur la gauche de la matrice d’observations X ∈ Rp :
⎛ ⎞
1 x11 · · · xp1
⎜ ⎟
X ← ⎝ ... ... · · · ... ⎠ . (5.5)
1 x 1 · · · xp
n n
Il s’agit d’une forme quadratique convexe que l’on peut donc minimiser en
en β,
annulant son gradient ∇β RSS = −2X y − X β . On obtient alors
X X β ∗ = X y. (5.7)
Théorème 5.1
Si le rang de la matrice X est égal à son nombre de colonnes, alors la somme des
moindres carrés 5.6 est minimisée pour
−1
β ∗ = X X X y .
Démonstration
Si X est de rang colonne plein, alors X X est inversible.
On peut aussi (et ce sera préférable quand p est grand et que l’inversion de la ma-
trice X X ∈ Rp×p est donc coûteuse) obtenir une estimation de β par un algorithme
à directions de descente (voir section A.3.3).
On fera attention à ne pas confondre les variables, qui sont les p valeurs
x1 , x2 , . . . , xp qui décrivent les données, et les paramètres, qui sont les p+1 valeurs
β0 , β1 , . . . , βp qui paramètrent le modèle.
73
Chapitre 5 r Régressions paramétriques
Cette interprétation n’est valide que si les variables ne sont pas corrélées, et que xj
peut être modifiée sans perturber les autres variables. De plus, si les variables sont
corrélées, X n’est pas de rang colonne plein et X X n’est donc pas inversible. Ainsi
la régression linéaire admet plusieurs solutions. Intuitivement, on peut passer de
l’une à l’autre de ces solutions car une perturbation d’un des poids βj peut être
compensée en modifiant les poids des variables corrélées à xj .
1. ω∗ est un estimateur linéaire de ω, autrement dit il existe une matrice A telle que
ω∗ = Ay .
2. ω∗ est non biaisé, autrement dit, E[ω∗ ] = ω.
3. Quel que soit l’estimateur linéaire non biaisé ω̃ de ω, la variance de cet estimateur
est supérieure ou égale à celle de ω∗ .
Théorème 5.2
Soient n observations x 1 , x 2 , . . . , x n ∈ Rp et leurs étiquettes y 1 , y 2 , . . . , y n ∈ R. Sous
p
l’hypothèse que, pour tout i, y i = β0 + j=1 βj xji + i et que les i sont normalement
distribuées et centrées en 0, alors l’estimateur de β par la méthode des moindres
carrés en est l’unique BLUE.
Démonstration
−1
Tout d’abord, β ∗ = X X X y et β ∗ est donc linéaire.
−1
∗
Son espérance est E[β ] = E X X X
Xβ + ε .
Sa variance vaut :
Var(β ∗ ) = Var (X X )−1 X y = Var (X X )−1 X X β + ε
= Var (X X )−1 X ε = σ 2 (X X )−1 .
Enfin, supposons que β̃ = Ay soit un autre estimateur linéaire &et non biaisé
' de β.
En remplaçant y par sa valeur, on a E A X β + ε = β et
Par définition, E[β̃] = β.
ainsi AX β = β. Comme cela est vrai pour tout β, on en conclut que AX = I.
Posons D = A − (X X )−1 X , de sorte à ce que β̃ − β ∗ = D y . La variance de β̃ vaut
Var(β̃) = Var(Ay ) = Var(Aε) = AA σ 2 .
74
5.3 Régression logistique
L’hypothèse de normalité sur ε n’est pas nécessaire : il suffit que les erreurs
{εi }i=1,...,n aient une espérance nulle, aient la même variance finie σ 2 (on parle
d’homoscédasticité), et ne soient pas corrélées entre elles (Cov(εi , εl ) = 0 pour i = l).
petite perturbation de x n’affecte cette probabilité. C’est pour cela qu’il est classique
de modéliser une transformation logit de P(Y = y|X = x) comme une combinaison
linéaire des variables.
Définition 5.3 (Fonction logit)
On appelle fonction logit la fonction
logit : [0, 1] → R
p
p → log
1−p
75
Chapitre 5 r Régressions paramétriques
σ : R → [0, 1]
1 eu
u → −u = .
1+e 1 + eu
5.3.1 Formulation
P(Y=1| x)
Ainsi, nous cherchons donc à modéliser log 1−P(Y=1| x) comme la combinaison li-
néaire β x, où, de manière équivalente, P(Y = 1| x) comme σ (β x). Nous utilisons
ici la transformation 5.5 de x.
Étant données n observations D = { x i , yi }i=1,...,n , que l’on suppose iid, le log de la
vraisemblance de β est
n
log P D|β = log P X = x i , Y = yi |β
i=1
n
n
i i
= log P Y = y |
x , β + log P X = x i
i=1 i=1
(5.8)
n yi
= x i , β
log P Y = 1| 1−yi + C
x i , β)
1 − P(Y = 1|
i=1
n
= yi log σ β x i + (1 − yi ) log 1 − σ (β x i ) + C,
i=1
76
5.4 Régression polynomiale
5.3.2 Solution
La vraisemblance de la régression logistique 5.8 est une fonction concave.
Théorème 5.3
Le gradient en β du maximum de vraisemblance de la régression logistique vaut
n
1
yi − x i .
1 + e−β x i
i=1
Démonstration
Ce résultat s’obtient en utilisant une propriété remarquable de la fonction logis-
tique : σ (u) = σ (u)(1 − σ (u)).
77
Chapitre 5 r Régressions paramétriques
Points clefs
r On peut apprendre les coefficients d’un modèle de régression paramétrique par
maximisation de vraisemblance, ce qui équivaut à minimiser le risque empirique
en utilisant le coût quadratique comme fonction de perte, et revient à la méthode
des moindres carrés.
−1
r La régression linéaire admet une unique solution β ∗ = X X X y si et seule-
ment si X X est inversible. Dans le cas contraire, une infinité de solutions
existent.
r La régression polynomiale se ramène à une régression linéaire.
r Pour un problème de classification binaire, utiliser le coût logistique comme
fonction de perte dans la minimisation du risque empirique revient à maximiser
la vraisemblance d’un modèle dans lequel la probabilité d’appartenir à la classe
positive est la transformée logit d’une combinaison linéaire des variables.
r La régression logistique n’a pas de solution analytique, mais on peut utiliser un
algorithme à directions de descente pour apprendre le modèle.
Bibliographie
Hastie, T., Tibshirani, R., et Friedman, J. (2009). The Elements of Statistical
Learning : Data Mining, Inference, and Prediction, Second Edition. Springer-
Verlag, New York, 2nd edition. [Link]
ElemStatLearn/.
Exercices
5.1 Quel algorithme utiliser pour entraîner une régression linéaire sur un jeu de
données contenant 105 observations et 5 variables ? 105 variables et 5 observations ?
105 variables et des centaines de millions d’observations ?
78
Exercices
5.2 Pour trouver les coefficients d’une régression linéaire par maximum de vrai-
semblance, doit-on faire l’hypothèse que les observations sont iid ? Que le bruit est
gaussien ? Que les observations x i sont indépendantes des étiquettes yi ?
5.3 Après avoir entraîné une régression polynomiale, Anaïs se rend compte que
l’erreur d’entraînement est beaucoup plus faible que l’erreur de validation. Que se
passe-t-il, et que peut-elle faire ?
5.4 Considérons 5 observations en 2 dimensions, étiquetées par y :
1. Quels sont les paramètres d’une régression linéaire sur ces données ?
2. Quelle est l’erreur quadratique moyenne du modèle sur ces données ?
3. Qu’arrive-t-il si on multiplie x1 par 10 et qu’on lui retranche 1 ?
5.5 Une régression linéaire est-elle affectée par la présence de données aber-
rantes ?
5.6 Après avoir entraîné une régression linéaire, Bertrand constate que les rési-
dus, c’est-à-dire les différences entre valeurs prédites et valeurs réelles, sont corrélés
aux valeurs prédites. Doit-il s’inquiéter de son modèle ?
5.7 Clémence entraîne une régression polynomiale de degré 4 sur des données qui
ont en fait été générées par un polynôme de degré 3. Que va-t-il vraisemblablement
se passer ?
5.8 Damien a entraîné une régression linéaire sur ses données. Il se rend compte
que le modèle sous-apprend. Doit-il ajouter ou enlever des variables ? Est-ce une
bonne idée d’essayer une régression polynomiale ?
5.9 Élodie souhaite utiliser une régression logistique pour un problème de
© Dunod - Toute reproduction non autorisée est un délit.
Solutions
5.1 Lorsque la matrice X X est de petite taille (peu de variables), on pourra utili-
ser un algorithme d’inversion de matrice. Sinon, un algorithme du gradient sera plus
approprié.
5.2 Les observations sont iid et le bruit gaussien, mais les étiquettes ne sont pas
indépendantes des observations : c’est justement leur dépendance que l’on cherche à
modéliser.
79
Chapitre 5 r Régressions paramétriques
5.4
−1
1. β = X X X y nous donne y ≈ −0,577 + 1,499x1 + 0,744x2 .
2
2. 15 5i=1 yi − −0,577 + 1,499x1i + 0,744x2i ≈ 0,016.
3. Multiplier x1 par 10 conduit à diviser β1 par 10. Lui retrancher 1 va se refléter sur
le biais β0 et l’erreur quadratique moyenne reste la même.
5.5 Oui (elles auront tendance à déplacer la fonction de décision vers elles).
5.6 Dans une régression linéaire, on modélise le bruit comme étant aléatoire. Il
ne devrait pas être corrélé aux prédictions.
5.8 Le modèle n’est pas assez complexe : on peut ajouter des variables, et essayer
d’augmenter le degré polynomial du modèle.
80
RÉGULARISATION
6
Lorsque les variables explicatives sont corrélées, ou trop nombreuses,
OBJECTIFS INTRODUCTION
81
Chapitre 6 r Régularisation
Coefficient de régularisation
Le coefficient de régularisation λ est un hyperparamètre de la régression linéaire
régularisée.
Quand λ tend vers +∞, le terme de régularisation prend de plus en plus
d’importance, jusqu’à ce qu’il domine le terme d’erreur et que seule compte la mi-
nimisation du régulariseur. Dans la plupart des cas, le régulariseur est minimisé
et il n’y a plus d’apprentissage.
quand β = 0,
À l’inverse, quand λ tend vers 0, le terme de régularisation devient négligeable
devant le terme d’erreur, et β prendra comme valeur une solution de la régression
linéaire non régularisée.
Comme tout hyperparamètre, λ peut être choisi par validation croisée. On
utilisera généralement une grille de valeurs logarithmique.
82
6.2 La régression ridge
6.2.2 Solution
Le problème 6.4 est un problème d’optimisation convexe (voir appendice, en fin
d’ouvrage) : il s’agit de minimiser une forme quadratique. Il se résout en annulant
le gradient en β de la fonction objective :
(( ((2 (( ((2
(( (( (( ((
∇β ((y − X β (( + λ ((β(( = 0
(6.5)
2 2
À l’inverse, dans le cas de la régression ridge, remplacer xj par αxj affecte aussi
le terme de régularisation, et a un effet plus complexe. L’échelle relative des dif-
férentes variables peut donc fortement affecter la régression ridge. Il est ainsi
recommandé de standardiser les variables avant l’apprentissage, c’est-à-dire de
toutes les ramener à avoir un écart-type de 1 en les divisant par leur écart-type :
xji
xji ← (6.8)
1 n i 1 n x i 2
n i=1 xj − n i=1 j
Attention : pour éviter le sur-apprentissage, il est important que cet écart-type soit
calculé sur le jeu d’entraînement uniquement, puis appliqué ensuite aux jeux de
test ou validation.
83
Chapitre 6 r Régularisation
84
6.3 Le lasso
Démonstration
L’équivalence s’obtient par dualité et en écrivant les conditions de Karun-Kush-
Tucker.
La régression ridge peut donc être formulée comme un problème d’optimisation
(( ((2 (( ((2
(( (( (( ((
quadratique (minimiser ((y − X β(( ) sous contrainte (((β(( ≤ t) : la solution doit
2 √ 2
être contenue dans la boule 2 de rayon t. Sauf dans le cas où l’optimisation sans
contrainte vérifie déjà la condition, cette solution sera sur la frontière de cette boule,
comme illustré sur la figure 6.2.
Figure 6.2 – La solution du problème d’optimisation sous contrainte 6.9 (ici en deux
dimensions) se situe sur une ligne de niveau de la somme
√ des moindres carrés
tangente à la boule 2 de rayon t.
© Dunod - Toute reproduction non autorisée est un délit.
6.3 LE LASSO
6.3.1 Parcimonie
Dans certaines applications, il peut être raisonnable de supposer que l’étiquette que
l’on cherche à prédire n’est expliquée que par un nombre restreint de variables. Il
est dans ce cas souhaitable d’avoir un modèle parcimonieux, ou sparse, c’est-à-dire
dans lequel un certain nombre de coefficients sont nuls : les variables correspondantes
peuvent être retirées du modèle.
85
Chapitre 6 r Régularisation
Le nom de lasso est en fait un acronyme, pour Least Absolute Shrinkage and Selection
Operator : il s’agit d’une méthode qui utilise les valeurs absolues des coefficients (la
norme 1 ) pour réduire (shrink) ces coefficients, ce qui permet de sélectionner les
variables qui n’auront pas un coefficient nul. En traitement du signal, le lasso est
aussi connu sous le nom de poursuite de base (basis pursuit en anglais).
En créant un modèle parcimonieux et en permettant d’éliminer les variables ayant
un coefficient nul, le lasso est une méthode de sélection de variable supervisée.
Il s’agit donc aussi d’une méthode de réduction de dimension.
6.3.3 Solution
Le lasso 6.11 n’admet pas de solution explicite. On pourra utiliser un algorithme
à directions de descente (voir section A.3.3) pour le résoudre. De plus, il ne s’agit
pas toujours d’un problème strictement convexe (en particulier, quand p > n) et il
n’admet donc pas nécessairement une unique solution. En pratique, cela pose surtout
problème quand les variables ne peuvent pas être considérées comme les réalisations
de lois de probabilité continues. Néanmoins, il est possible de montrer que les coeffi-
cients non nuls dans deux solutions ont nécessairement le même signe. Ainsi, l’effet
d’une variable a la même direction dans toutes les solutions qui la considèrent, ce qui
facilite l’interprétation d’un modèle appris par le lasso.
86
6.3 Le lasso
Théorème 6.2
Étant donnés λ ∈ R+ , X ∈ Rn×p et y ∈ Rn , il existe un unique t ∈ R+ tel que le
problème 6.11 soit équivalent à
(( ((2 (( ((
(( (( (( ((
arg min ((y − X β(( tel que ((β(( ≤ t. (6.12)
p+1 2 1
β∈R
87
Chapitre 6 r Régularisation
Stabilité
Si plusieurs variables corrélées contribuent à la prédiction de l’étiquette, le lasso
va avoir tendance à choisir une seule d’entre elles (affectant un poids de 0 aux
autres), plutôt que de répartir les poids équitablement comme la régression
ridge. C’est ainsi qu’on arrive à avoir des modèles très parcimonieux. Cepen-
dant, le choix de cette variable est aléatoire, et peut changer si l’on répète la
procédure d’optimisation. Le lasso a donc tendance à être instable.
88
6.4 Elastic net
Points clefs
r Ajouter un terme de régularisation, fonction du vecteur des coefficients β, au
risque empirique de la régression linéaire permet d’éviter le sur-apprentissage.
r La régression ridge utilise la norme 2 de β comme régulariseur ; elle admet
toujours une unique solution analytique, et a un effet de regroupement sur les
variables corrélées.
r Le lasso utilise la norme 1 de β comme régulariseur ; il crée un modèle
parcimonieux, et permet donc d’effectuer une réduction de dimension
supervisée.
r De nombreux autres régulariseurs sont possibles en fonction de la structure du
problème.
des variables qui respectent une structure (graphe, groupes, ou arbre) don-
née a priori. Ces approches sont utilisées en particulier dans des applications
bio-informatiques, par exemple quand on cherche à construire des modèles
parcimonieux basés sur l’expression de gènes sous l’hypothèse que seul un
petit nombre de voies métaboliques (groupes de gènes) est pertinent. Pour
plus de détails, on se référera à l’article de Huang et al. (2011).
r En ce qui concerne l’unicité de la solution du lasso, on se reportera à l’article
de Tibshirani (2013).
r L’ouvrage de Hastie et al. (2015) est entièrement consacré au lasso et ses
généralisations.
89
Chapitre 6 r Régularisation
Bibliographie
Hastie, T., Tibshirani, R., et Wainwright, M. (2015). Statistical Learning
with Sparsity: The Lasso and Generalizations. CRC Press. [Link]
[Link]/~hastie/StatLearnSparsity/.
Huang, J., Zhang, T., et Metaxas, D. (2011). Learning with structured sparsity.
Journal of Machine Learning Research, 12:3371-3412.
Tibshirani, R. J. (2013). The lasso problem and uniqueness. Electronic Journal
of Statistics, 7:1456-1490.
Exercices
90
Exercices
Solutions
6.1 Quand λ est faible, c’est le risque empirique qui domine et le modèle est plus
susceptible de sur-apprendre.
6.2 Quand λ est élevé, c’est le terme de régularisation qui domine et les poids
seront donc contraints à être faibles.
6.3 Les variables reliées sur le graphe vont avoir des coefficients proches : elle
pense que deux villes proches ont des contributions similaires à l’étiquette qu’elle
essaie de modèliser.
6.7 Oui (et toute régression) : il s’agit juste d’ajouter des variables.
91
7 RÉSEAUX DE NEURONES
ARTIFICIELS
De l’annotation automatique d’images à la reconnaissance vocale, en
passant par des ordinateurs capables de battre des champions de go et
par les véhicules autonomes, les récents succès de l’intelligence artifi-
cielle sont nombreux à reposer sur les réseaux de neurones profonds,
INTRODUCTION
7.1 LE PERCEPTRON
L’histoire des réseaux de neurones artificiels remonte aux années 1950 et aux ef-
forts de psychologues comme Franck Rosenblatt pour comprendre le cerveau humain.
Initialement, ils ont été conçus dans le but de modéliser mathématiquement le traite-
ment de l’information par les réseaux de neurones biologiques qui se trouvent dans
le cortex des mammifères. De nos jours, leur réalisme biologique importe peu et
c’est leur efficacité à modéliser des relations complexes et non linéaires qui fait leur
succès.
Le premier réseau de neurones artificiels est le perceptron (Rosenblatt, 1957).
Loin d’être profond, il comporte une seule couche et a une capacité de modélisation
limitée.
92
7.1 Le perceptron
7.1.1 Modèle
Le perceptron (figure 7.1) est formé d’une couche d’entrée de p neurones, ou unités,
correspondant chacune à une variable d’entrée. Ces neurones transmettent la valeur
de leur entrée à la couche suivante. À ces p neurones on rajoute généralement une
unité de biais, qui transmet toujours la valeur 1. Cette unité correspond à la colonne
de 1 que nous avons ajoutée aux données dans les modèles linéaires (équation 5.5).
On remplacera dans ce qui suit tout vecteur x = (x1 , x2 , . . . , xp ) par sa version
augmentée d’un 1 : x = (1, x1 , x2 , . . . , xp ).
p
f ( x )) = a ⎝w0 +
x ) = a(o( wj xj ⎠ = a (w,
x ) . (7.1)
j=1
Fonctions d’activation
Dans le cas d’un problème de régression, on utilisera tout simplement l’identité
comme fonction d’activation. Dans le cas d’un problème de classification binaire,
on pourra utiliser :
93
Chapitre 7 r Réseaux de neurones artificiels
Classification multi-classe
Dans le cas d’un problème de classification multi-classe, on modifiera l’architecture
du perceptron de sorte à n’avoir non plus 1 mais C neurones dans la couche de sortie,
où C est le nombre de classes. Les p+1 neurones de la couche d’entrée seront ensuite
tous connectés à chacun de ces neurones de sortie (on aura donc (p + 1)C poids de
connexion, notés wcj .) Cette architecture est illustrée sur la figure 7.2.
On utilise alors comme fonction d’activation la fonction softmax :
Définition 7.1 (Fonction softmax)
On appelle fonction softmax, ou fonction exponentielle normalisée, la fonction σ :
RC → [0, 1]C définie par :
eoc
σ (o1 , o2 , . . . , oC )c = .
C
k=1
eok
94
7.1 Le perceptron
7.1.2 Entraînement
Pour entraîner un perceptron, nous allons chercher, comme par exemple pour la
régression paramétrique, à minimiser le risque empirique. Cependant, nous allons
supposer que les observations ( x i , yi ) ne sont pas disponibles simultanément, mais
qu’elles sont observées séquentiellement. Cette hypothèse découle de la plasticité des
réseaux de neurones biologiques : ils s’adaptent constamment en fonction des signaux
qu’ils reçoivent. Nous allons donc utiliser un algorithme d’entraînement incrémental,
qui s’adapte à des observations arrivant les unes après les autres.
Définition 7.2 (Apprentissage incrémental vs hors-ligne)
Un algorithme d’apprentissage qui opère sur un unique ensemble de n observations
est appelé hors-ligne. En anglais, on parlera de batch learning.
Par contraste, un algorithme d’apprentissage qui effectue une ou plusieurs opéra-
tions à chaque nouvelle observation qui lui est fournie est appelé incrémental ou
en ligne. En anglais, on parlera de online learning.
Pour minimiser le risque empirique de manière itérative, nous allons nous ap-
puyer sur l’algorithme du gradient (voir section A.3.3). L’algorithme commence par
(0) (0) (0)
une initialisation aléatoire du vecteur de poids de connexion w0 , w1 , . . . , wp , par
exemple, w = 0.
Puis, à chaque observation, on ajuste ce vecteur dans la direction opposée au gra-
dient du risque empirique. En effet, ce gradient indique la direction de plus forte pente
du risque empirique ; le redescendre nous rapproche d’un point où ce risque est mini-
mal. Formellement, à une itération de l’algorithme, on tire une nouvelle observation
x i , yi ) et on actualise, pour tout j, les poids de connexion de la façon suivante :
(
∂L( f (
x i ), yi )
w j ← wj − η . (7.4)
∂wj
Il est possible (et même recommandé dans le cas où les données ne sont pas ex-
trêmement volumineuses) d’itérer plusieurs fois sur l’intégralité du jeu de données.
Typiquement, on itère jusqu’à ce que l’algorithme converge à ε près.
© Dunod - Toute reproduction non autorisée est un délit.
Vitesse d’apprentissage
Cet algorithme a un hyperparamètre, η > 0, qui est le pas de l’algorithme du gradient
et que l’on appelle la vitesse d’apprentissage (ou learning rate) dans le contexte des
réseaux de neurones artificiels. Cet hyperparamètre joue un rôle important : s’il est
trop grand, l’algorithme risque d’osciller autour de la solution optimale, voire de
diverger. À l’inverse, s’il est trop faible, l’algorithme va converger très lentement. Il
est donc essentiel de bien choisir sa vitesse d’apprentissage.
En pratique, on utilise souvent une vitesse d’apprentissage adaptative : relative-
ment grande au début, puis de plus en plus faible au fur et à mesure que l’on se
95
Chapitre 7 r Réseaux de neurones artificiels
Classification binaire
Le cas de la classification binaire, utilisant un seuil comme fonction d’activation, est
historiquement le premier à avoir été traité. La fonction de coût utilisée est connue
sous le nom de critère du perceptron :
x i ), yi ) = max(0, −yi o(
L( f ( x i )) = max(0, −yi w,
x ) (7.5)
Ce critère est proche de la fonction d’erreur hinge. Quand la combinaison linéaire
des entrées a le bon signe, le critère du perceptron est nul. Quand elle a le mauvais
signe, le critère du perceptron est d’autant plus grand que cette combinaison linéaire
est éloignée de 0. En utilisant ce critère, la règle d’actualisation 7.4 devient :
0 x i) > 0
si yi o(
wj ←
−y xj sinon.
i i
Régression
Dans le cas de la régression, on utilise pour le coût empirique la fonction de coût
quadratique :
1 1 i 2
x i ), yi ) = (yi − f (
L( f ( x i ))2 = y − w,
x . (7.6)
2 2
La règle d’actualisation 7.4 devient :
wj ← wj − η( f (
x i ) − yi )xji . (7.7)
96
7.1 Le perceptron
Classification probabiliste
Dans le cas de la classification (binaire ou multi-classe), on utilise l’entropie croisée
comme fonction de coût :
C
C
exp(w c , x
x ), y ) = −
L( f (i i
δ( y , c) log fc (
i i
x )=− δ( yi , c) log C .
c=1 c=1 k=1 exp(w k , x )
Quelques lignes de calcul montrent que l’on obtient alors la même règle d’actuali-
sation que pour la régression (7.7) :
Ces calculs sont aussi valables dans le cas de la classification binaire, et la règle
est exactement celle de la formule 7.7.
97
Chapitre 7 r Réseaux de neurones artificiels
7.2.1 Architecture
On appelle perceptron multi-couche, ou multi-layer perceptron (MLP) en anglais, un
réseau de neurones construit en insérant des couches intermédiaires entre la couche
d’entrée et celle de sortie d’un perceptron. On parlera parfois de couches cachées par
référence à l’anglais hidden layers. Chaque neurone d’une couche intermédiaire ou de
la couche de sortie reçoit en entrée les sorties des neurones de la couche précédente.
Il n’y a pas de retour d’une couche vers une couche qui la précède ; on parle ainsi
aussi d’un réseau de neurones à propagation avant, ou feed-forward en anglais.
En utilisant des fonctions d’activation non linéaires, telles que la fonction logis-
tique ou la fonction tangente hyperbolique, on crée ainsi un modèle paramétrique
hautement non linéaire.
Exemple
Prenons l’exemple d’un perceptron avec deux couches intermédiaires comme illus-
h le poids de la connexion du neurone j de la couche
tré sur la figure 7.3. Notons wjq
h − 1 au neurone q de la couche h, ah la fonction d’activation utilisée en sortie de
la couche h, et ph le nombre de neurones dans la couche h.
La sortie zq1 du q-ième neurone de la première couche cachée vaut
⎛ ⎞
p
z q = a1 ⎝
1 wjq xj ⎠ .
1
j=0
Ainsi, en supposant qu’on utilise une fonction logistique pour tous les neurones des
couches cachées, la sortie du perceptron vaut
⎛ ⎞
⎜ ⎟
⎜ p2 3 1 ⎟
f (x ) = a3 ⎜
⎜ wjq ! "⎟
⎟,
⎝j=0 p 1 2 1 ⎠
1 + exp − j=0
wjq
p 1x
1+exp − j=0 wjq j
rones font partie des hyperparamètres : on les suppose fixés, ce ne sont pas
© Dunod - Toute reproduction non autorisée est un délit.
eux que l’on apprend.) Ce modèle a donc d’autant plus de paramètres (c’est-à-dire
de poids de connexion) qu’il y a de couches intermédiaires et de neurones dans
ces couches. C’est pour éviter le sur-apprentissage que les réseaux de neurones
profonds requièrent souvent des quantités massives de données pour apprendre
de bons modèles.
99
Chapitre 7 r Réseaux de neurones artificiels
100
7.2 Perceptron multi-couche
gradient par rapport à un poids dans une des premières couches intermédiaires est
souvent instable. Il aura tendance à être soit très faible, ce qui ralentira l’apprentissage
(c’est ce que l’on appelle le problème de la disparition du gradient, ou vanishing gra-
dient en anglais), soit à prendre des valeurs de plus en plus élevées à chaque itération,
conduisant à l’inverse à un problème d’explosion du gradient (exploding gradient en
anglais.)
L’initialisation des poids de connexion, la standardisation des variables, le choix
de la vitesse d’apprentissage et celui des fonctions d’activation ont tous un impact sur
la capacité du perceptron multi-couche à converger vers une bonne solution.
C’est pour cela que l’entraînement d’un réseau de neurones à plusieurs couches est
délicat, et qu’il a fallu attendre 2006 pour que les travaux de Geoff Hinton et d’autres,
ainsi que l’amélioration de la puissance de calcul des ordinateurs, pour commencer
à surmonter cette difficulté, remettant les réseaux de neurones sur le devant de la
scène.
Saturation
Un autre problème du perceptron multi-couche apparaît quand la plupart des uni-
tés logistiques retournent des valeurs soit très proches de 0 soit très proches de 1.
Cela arrive quand la somme pondérée ohj des signaux qu’ils reçoivent en entrée a une
amplitude trop grande, autrement dit quand les poids de connexion ont eux-mêmes
une amplitude trop élevée. Dans ces conditions, les actualisations de ces poids n’au-
ront plus qu’un impact marginal sur les prédictions. On dit alors que le réseau est
saturé.
Pour éviter cette situation, on peut se tourner vers la régularisation 2 (cf. sec-
tion 6.2), appelée dégradation des pondérations ou weight decay dans le contexte des
x i ), yi ) la
réseaux de neurones artificiels. Il s’agira d’ajouter au risque empirique L( f (
norme euclidienne du vecteur de poids de connexion.
Rétropropagation
Néanmoins, le principe fondamental de l’apprentissage d’un perceptron multi-
© Dunod - Toute reproduction non autorisée est un délit.
101
Chapitre 7 r Réseaux de neurones artificiels
∂L( f (
x i ), yi ) x i ), yi ) ∂ohq
∂L( f ( ∂L( f (x i ), yi ) ∂zhq ∂ohq
= =
∂whjq ∂ohq ∂whjq ∂zhq ∂ohq ∂whjq
!ph+1 "
∂L(f ( x i ), yi ) ∂oh+1 ∂zhq ∂ohq
r
= (7.8)
∂oh+1
r ∂zhq ∂ohq ∂whjq
r=1
!ph+1 "
∂L(f ( x i ), yi ) h+1 h h−1
= h+1
wqr ah (oq ) zj .
r=1
∂o r
Exemple
Reprenons le réseau à deux couches intermédiaires décrit sur la figure 7.3, en
utilisant l’identité comme dernière fonction d’activation a3 , une fonction d’erreur
quadratique, et des activations logistiques pour a1 et a2 . Nous rappelons que la
dérivée de la fonction logistique peut s’écrire σ (u) = u σ (u)(1 − σ (u)).
Lors de la propagation avant, nous allons effectuer les calculs suivants :
p
oq1 = 1 x ; z 1 = σ (o1 )
wjq j q q
j=0
p1
oq2 = 2 z 1 ; z 2 = σ (o2 )
wjq j q q
j=1
p2
o3 = wj3 zj2 ; f (x i ) = z 3 = o3 .
j=1
102
7.2 Perceptron multi-couche
en utilisant les valeurs de f (x i ) et zj2 que nous avons mémorisées lors de la
propagation avant. Ainsi
wj3 ← wj3 − η f (x i ) − y i zj2 .
2
∂L(f (x i ), y i ) ∂L(f (x i ), y i ) ∂oq
=
2
∂wjq ∂oq2 2
∂wjq
où
et
∂oq2
= zj1 .
2
∂wjq
Nous pouvons donc utiliser les valeurs de f (x i ), zq2 et zj1 mémorisées lors de la
propagation avant, et wq3 que nous venons d’actualiser, pour actualiser wjq 2 par
2 ← w 2 − η f (x i ) − y i w 3 z 2 (1 − z 2 ) z 1 .
wjq jq q q q j
Encore une fois, nous disposons de tous les éléments nécessaires : zq1 a été calculé
© Dunod - Toute reproduction non autorisée est un délit.
lors de la propagation avant, les poids wqr 2 ont été actualisés à l’étape précé-
i i
dente, et les dérivées partielles ∂L(f (x 2),y ) ont elles aussi été calculées à l’étape
∂oq
précédente (7.9). Nous pouvons donc effectuer aisément notre dernière étape de
rétropropagation :
⎛ ⎞
p2
∂L(f ( i ), y i ) 2
x
wjq ← wjq − η ⎝
1 1 wqr ⎠ zq1 (1 − zq1 ) xj .
∂o 2
r=1 r
Il est possible d’ajouter une unité de biais à chaque couche intermédiaire ; les
dérivations se font alors sur le même principe.
103
Chapitre 7 r Réseaux de neurones artificiels
L’apprentissage de représentations
On associe souvent aux réseaux de neurones profond la notion de representation
learning. En effet, il est possible de considérer que chacune des couches intermé-
diaires successives apprend une nouvelle représentation des données (zh1 , zh2 , . . . , zhph )
104
7.2 Perceptron multi-couche
Points clefs
r Le perceptron permet d’apprendre des modèles paramétriques linéaires et est
entraîné par des actualisations itératives de ses poids grâce à un algorithme à
directions de descente.
r Le perceptron multi-couche permet d’apprendre des modèles paramétriques non
linéaires et offre une grande flexibilité de modélisation.
r Le perceptron multi-couche est entraîné par rétropropagation, qui combine le
théorème de dérivation des fonctions composées avec une mémoïsation pour
une grande efficacité de calcul.
r Le problème d’optimisation du perceptron multi-couche et, plus généralement,
de tout réseau de neurones artificiel profond, n’est pas convexe, et il n’est pas
facile d’obtenir un bon minimum.
Bibliographie
Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function.
Mathematics of Control, Signals and Systems, 2(4):303-314.
© Dunod - Toute reproduction non autorisée est un délit.
Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep learning. MIT Press,
Cambridge, MA. [Link]
Hornik, K. (1991). Approximation capabilities of multilayer feedforward
networks. Neural Networks, 4(2):251-257.
Minsky, M. and Papert, S. (1972). Perceptrons: an Introduction to Computatio-
nal Geometry. MIT Press, Cambridge, MA.
Novikoff, A. B. J. (1962). On convergence proofs on perceptrons. In Symposium
on the Mathematical Theory of Automata, pages 615-622.
Rosenblatt, F. (1957). The perceptron–a perceiving and recognizing automa-
ton. Technical Report 85-460-1, Cornell Aeronautical Laboratory.
105
Chapitre 7 r Réseaux de neurones artificiels
Exercices
Solutions
7.1 f (x1 , x2 , x3 ) = w0 + w1 x1 + w2 x2 + w3 x3 et la seule valeur pour laquelle f doit
être négative est (0, 0, 0). Il faut donc w0 < 0 et pour tout j = 1, 2, 3, w0 + wj > 0.
On peut choisir w0 = −1 et w1 = w2 = w3 = 2.
106
Exercices
commencer par un réseau plus petit, qui risquera moins de sur-apprendre ou d’être
bloqué dans un minimum local.
7.6 On ajoute des poids w10j de l’unité de biais de la couche d’entrée aux neu-
rones la première couche intermédiaire, w20j de l’unité de biais de la première couche
intermédiaire aux neurones de la deuxième, et w30 de l’unité de la deuxième couche
intermédiaire au neurone de sortie.
x ), y) = −y log f (
L( f ( x )) et σ (u) = u σ (u)(1 − σ (u)). Ainsi :
x ) − (1 − y) log(1 − f (
∂L( f (
x i ), yi ) ∂f (
x i) f (x i) − y
= x i ) − yi z2j
= f (
∂w3j ∂w3j x i )(1 − f (
f ( x i)
∂L( f (
x i ), yi ) x i ), yi ) ∂o2q
∂L( f (
= = f (
x i ) − yi w3q z2q (1 − z2q )z1j .
∂w2jq ∂o2q ∂w2jq
2
∂L( f (
x i ), yi )
w10q ← w10q − η w2qr z1q (1 − z1q )
∂o2r
r=1
7.7 Notons wjh le poid de la connexion de l’unité d’entrée j vers l’unité intermé-
diaire h, vhk le poids de la connexion de l’unité intermédiaire h vers l’unité de sortie k,
107
Chapitre 7 r Réseaux de neurones artificiels
108
MÉTHODE DES PLUS
PROCHES VOISINS
8
Ce chapitre présente un algorithme de prédiction non paramétrique
conceptuellement très simple mais néanmoins puissant, qui permet de
construire des frontières de décision complexes sans faire aucune hy-
pothèse sur la distribution des données. Cet algorithme, dit des plus
INTRODUCTION
x i )
f (x ) = y arg mini=1,...,n d(x, .
109
Chapitre 8 r Méthode des plus proches voisins
Une cellule de Voronoï est un ensemble convexe, et l’union de toutes les cellules de
Voronoï forme une partition de X appelée diagramme de Voronoï :
)
X= ).
Vor(u
∈S
u
110
8.2 Méthode des plus proches voisins
Ainsi, cet algorithme très simple permet de construire une frontière de décision
beaucoup plus complexe qu’un algorithme paramétrique linéaire, comme on le voit
sur la figure 8.2.
représentation) mal positionnée, tous les points dans sa cellule de Voronoï seront mal
étiquetés. Pour rendre cette méthode plus robuste, on se propose de combiner les
« opinions » de plusieurs voisins de l’observation que l’on cherche à étiqueter.
111
Chapitre 8 r Méthode des plus proches voisins
d’entraînement dont elle est la plus proche. En notant Nk (x ) l’ensemble des k plus
proches voisins de x dans D :
r Pour un problème de classification, on applique le vote de la majorité, et x prend
l’étiquette majoritaire parmi celles de ces k plus proches voisins :
f (x ) = arg max δ(y i , c).
c
i:x i ∈Nk (x )
Figure 8.3 – Frontière de décision d’un algorithme des 5 plus proches voisins
pour les données des figures 8.1 et 8.2.
112
8.2 Méthode des plus proches voisins
8.2.4 Variantes
ε-voisins
Plutôt que de considérer un nombre fixe de voisins les plus proches, on peut préférer
considérer tous les exemples d’apprentissage suffisamment proches de l’observation
à étiqueter : cela permet de mieux utiliser le jeu d’entraînement dans les zones où il
est dense. De plus, les prédictions faites en se basant sur des exemples proches (non
pas relativement, mais dans l’absolu) sont intuitivement plus fiables que celles faites
© Dunod - Toute reproduction non autorisée est un délit.
113
Chapitre 8 r Méthode des plus proches voisins
Une limitation évidente de cet algorithme est qu’il est nécessaire de définir une
stratégie alternative en l’absence d’exemples dans la boule de rayon ε choisi.
8.3.1 Distances
Rappelons ici la définition d’une distance :
114
8.3 Distances et similarités
, v ) = max |uj − vj |.
d∞ (u
j=1,...,p
Théorème 8.1
La distance ∞ est la limite quand q → ∞ de la distance de Minkowski.
Démonstration
Posons k = arg maxj=1,...,p |uj − vj |. Alors
© Dunod - Toute reproduction non autorisée est un délit.
car pour tout j, |uj − vj | ≤ |uk − vk |, avec égalité au maximum p fois. D’autre part,
⎛ ⎞1/q
dq (u , v ) = ⎝|uk − vk |q + |uj − vj |q ⎠ ≥ |uk − vk |
j =k
115
Chapitre 8 r Méthode des plus proches voisins
, v ) ≤ |uj − vj |p1/q .
|uk − vk | ≤ dq (u
, v ) = |uk − vk |.
Comme limq→∞ p1/q = 1, limq→∞ dq (u
Remarquons que si l’on appelle u (resp. v ) la version centrée de u (resp. v), c’est-
le vecteur obtenu en lui retranchant la moyenne de ses coordonnées : u =
à-dire
p
u − 1p j=1 uj , ce coefficient se simplifie en
p
j=1 uj vj u , v
ρ(u, v) = # # =
p
u 2
p
v 2 ||u||2 ||v||2
j=1 j j=1 j
et vaut donc le cosinus de l’angle entre u et v . C’est pour cette raison qu’on appelle
parfois ρ la similarité cosinus.
Si en plus d’être centrés, les vecteurs u et v sont normalisés, la similarité cosinus
se réduit au produit scalaire entre u et v. Ce produit scalaire est d’autant plus grand
que les vecteurs u et v sont colinéaires, et vaut 0 quand les vecteurs sont orthogonaux.
Nous verrons au chapitre 10 comment étendre la notion de produit scalaire sur Rp
à celle de noyau sur X, ce qui nous permettra de définir aisément d’autres mesures de
similarité.
116
8.3 Distances et similarités
de Manhattan.
Deux ensembles sont considérés être d’autant plus semblables qu’ils ont d’élé-
ments en commun. Attention, si l’on compare des ensembles susceptibles d’être de
tailles très différentes, cela doit être comparé au nombre d’éléments qu’ils pour-
raient avoir en commun : deux ensembles de grande taille auront naturellement plus
d’éléments communs que deux ensembles de petite taille. On utilisera pour cela la
similarité de Jaccard.
117
Chapitre 8 r Méthode des plus proches voisins
J : 2E × 2E → [0, 1]
|S ∩ T|
S, T → .
|S ∪ T|
Ici 2E désigne l’ensemble des parties de E, autrement dit l’ensemble de ses
sous-ensembles. Cette notation est choisie car, du moins dans le cas fini, un sous-
ensemble S ⊆ E peut être représenté comme une fonction binaire de E vers {0, 1}
qui associe 1 à un élément de E présent dans S, et 0 aux autres.
Si les éléments sont susceptibles d’apparaître plusieurs fois dans chaque « en-
semble » (il ne s’agira alors plus d’ensembles, mais de multi-ensembles), on peut
prendre en compte la multiplicité des éléments en utilisant la similarité MinMax :
Définition 8.11 (Similarité MinMax)
Étant donné un multi-ensemble S de E, et un élément e ∈ E, on note mS (e) la multi-
plicité de e dans S, autrement dit son nombre d’occurrences dans S. Étant donné un
ensemble E d’éléments, on appelle similarité MinMax entre deux multi-ensembles S
et T de E la fonction qui retourne
min(mS (e), mT (e))
MinMax(S, T) = e∈S∩T .
e∈S∪T max(mS (e), mT (e))
118
8.4 Filtrage collaboratif
Exemple
Supposons que nos observations soient des articles de journaux, et que nous
disposions d’une variable catégorique identifiant leur sujet comme un parmi « po-
litique », « société », « économie », « sport », « science » ou « culture ». L’encodage
one-hot de cette variable consistera à la remplacer par 6 variables binaires, va-
lant (1, 0, 0, 0, 0, 0) si l’article parle de politique et (0, 0, 0, 0, 0, 1) s’il parle de
science.
Une fois les données ainsi encodées, on peut leur appliquer les distances et
similarités définies sur les vecteurs réels.
Dans le cas des jours de la semaine (ou des mois de l’année), le problème de
l’encodage par un nombre de 1 à 7 (ou de 1 à 12) est la nature cyclique de ces
catégories : février (2) est certes plus proche – temporellement – de mai (5−2=3)
que de juillet (7−2=5), mais il est encore plus proche de décembre (12−2=10).
Pour conserver cette proximité temporelle, on pourra positionner ces valeurs de
manière équidistante sur un cercle de rayon 1, et représenter chacune d’entre elles
par deux variables, le cosinus et le √sinus de cette position. On représentera
√ ainsi
février par (cos( 2π
6
), sin( 2π
6
)) = ( 1 , 3 ), mai par (cos( 5π
2 2 6
), sin( 5π
6
)) = (− 23 , 1
2
), et
décembre
√ par (cos(2π ), sin(2π )) = (1, 0). La distance euclidienne de février à mai
est de 2 tandis que celle de février à décembre est de 1.
Plus précisément, étant donnés un ensemble S d’objets (films, livres, achats, etc.),
un ensemble X d’utilisateurs, nous supposons l’existence d’une fonction r : X × S →
R telle que r(u, a) est la note donnée par l’utilisateur u à l’objet a. Cette fonction est
partiellement connue, au sens où tous les utilisateurs n’ont pas noté tous les objets.
En notant, pour tout (a, b) ∈ S × S, U(a, b) le sous-ensemble de X contenant uni-
quement les utilisateurs qui ont noté à la fois a et b, et pour tout u ∈ X, r̄(u) la note
moyenne donnée par u, on peut alors définir une similarité entre objets sur la base de
la similarité cosinus :
u∈U(a,b) (r(u, a) − r̄(u)) (r(u, b) − r̄(u))
s(a, b) = # . (8.1)
2
u∈U(a,b) (r(u, a) − r̄(u)) u∈U(a,b) (r(u, b) − r̄(u))
2
119
Chapitre 8 r Méthode des plus proches voisins
Appelons maintenant Nuk (a) les k plus proches voisins de a parmi les objets notés
par u. On peut recommander l’objet a pour l’utilisateur u par :
b∈Nk (a) s(a, b)r(u, b)
f (u, a) = u .
b∈Nuk (a) |s(a, b)|
Points clefs
r L’algorithme des k plus proches voisins a un entraînement paresseux ; pour
compenser, le coût algorithmique d’une prédiction peut être élevé si la base
de données d’entraînement est grande.
r La qualité des prédictions d’un algorithme des k plus proches voisins dépend
principalement du choix d’une bonne distance ou similarité.
r L’algorithme des k plus proches voisins fonctionne mieux en faible dimension :
son exécution est plus rapide ;
il est moins susceptible d’être biaisé par des variables qui ne sont pas
pertinentes ;
il est moins susceptible de souffrir du fléau de la dimension.
Bibliographie
Aggarwal, C. C. (2016). Recommender Systems. Springer.
Aha, D. W. (1997). Special issue on lazy learning. Artificial Intelligence Review,
11(1-5):7-423.
Bentley, J. L. (1957). Multidimensional binary search trees used for associative
searching. Communications of the ACM, 18(9):509-517.
120
Exercices
Exercices
x1 1 2 2 2 3 3
x2 2 1 2 3 1 2
y + + − + − +
121
Chapitre 8 r Méthode des plus proches voisins
8.6 Diego veut prédire si une boisson est un thé ou un café. Il a recueilli les
données suivantes :
Solutions
8.1
1. 2.
122
Exercices
8.3 Non, il s’agit d’un algorithme paresseux qui n’a pas de temps d’entraînement.
8.5
1. Représentations sur 7 bits (1 par note) : A = 1100111 ; B = 1110000 ;
C = 0000111. d(A, B) = 4 ; d(A, C) = 2 ; d(B, C) = 6.
2. s(A, B) = 2
6 ≈ 0, 33 ; s(A, C) = 3
5 = 0, 6 ; s(B, C) = 0
6 = 0.
3. Représentations sur 7 octets : A = (2, 2, 0, 0, 4, 3, 4) ; B = (5, 4, 2, 0, 0, 0, 0) ;
5+4+2+0+4+3+4 = 11 ≈ 0, 18 ; s(A, C) =
C = (0, 0, 0, 0, 4, 3, 4). s(A, B) = 2+2+0+0+0+0+0 2
8.6
1. L’observation dont notre boisson est la plus proche est (125 ; 0,050). Diego prédit
donc qu’il s’agit d’un café.
2. Cette boisson ressemble en fait plus à un thé, au vu de son contenu en caféine. Le
volume domine le contenu de caféine. Il faut donc normaliser les données.
© Dunod - Toute reproduction non autorisée est un délit.
123
9 ARBRES ET FORÊTS
tions. Cela n’est pas toujours chose aisée, et les arbres de décision
approchent le problème différemment. Non métriques, hiérarchiques,
et non paramétriques, ils présentent d’intéressantes propriétés, en
particulier en ce qui concerne les attributs discrets. Cependant, ils
ont tendance à mal apprendre, et avoir de faibles propriétés de
généralisation.
Dans ce chapitre, après avoir exploré plus en détail les propriétés
des arbres et leur construction, nous verrons comment les combiner
pour en faire des modèles puissants, dits modèles ensemblistes, qui
sont bien plus que la somme de leurs parties.
OBJECTIFS
124
9.1 Arbres de décision
La figure 9.1 nous permet d’illustrer trois propriétés des arbres de décision :
• Ils permettent de traiter des attributs discrets (comme ici la forme, la taille et la
couleur), sans nécessiter une notion de similarité ou d’ordre sur ces attributs (on
parle d’apprentissage non métrique).
• Ils permettent de traiter un problème de classification multi-classe sans passer par
des classifications binaires.
• Ils permettent de traiter des classes multi-modales (comme ici pour l’étiquette
« pomme », qui est affectée à un fruit grand et rouge ou à un fruit jaune et rond).
125
Chapitre 9 r Arbres et forêts
Dans ce chapitre, nous ne traiterons pas séparément du cas binaire et du cas multi-
classe car le premier découle du second en étiquetant les deux classes 1 et 2 plutôt
que 0 et 1 comme nous en avons l’habitude.
Pour un problème de régression, cette étiquette est l’étiquette moyenne des
observations dans cette région :
R
1 i
x) =
f ( δx∈Rr y. (9.2)
|Rr | i
r=1 x ∈Rr
i:
126
9.2 Comment faire pousser un arbre
Comme illustré sur la figure 9.2, CART partitionne les données une variable à la
fois, ce qui produit une frontière de décision orthogonale aux axes.
Nous supposons par la suite que les données sont définies dans un espace X de
dimension p.
Dans le cas où la variable de séparation est une variable discrète pouvant prendre
plus de deux valeurs (ou modalités), elle s’accompagne alors d’un sous-ensemble
© Dunod - Toute reproduction non autorisée est un délit.
Enfin, dans le cas où la variable de séparation est une variable réelle, elle s’accom-
pagne alors d’un point de séparation (splitting point) s qui est la valeur de l’attribut
par rapport à laquelle va se faire la décision. Les deux régions sont alors
Rl (j, s) = {x : xj < s}; Rr (j, s) = {x : xj ≥ s}.
À chaque itération de l’algorithme CART, on itère sur toutes les valeurs possibles
de j et, le cas échéant, toutes les valeurs possibles de s ou S pour déterminer le
couple (j, s) qui minimise un critère prédéfini.
127
Chapitre 9 r Arbres et forêts
Dans le cas d’une variable continue xj , si l’on suppose les valeurs prises par cette
variable dans D ordonnées : xj1 ≤ xj2 ≤ . . . , ≤ xjn , alors les valeurs possibles de s
xji+1 −xji
sont 2
pour toutes les valeurs de i telles que xji+1 = xji .
où yl (j, s) (resp. yr (j, s)) est l’étiquette associée à la région Rl (j, s) (resp. Rr (j, s)) à ce
stade, soit donc la moyenne des étiquettes de cette région.
Dans le cas d’un problème de classification, on utilise plutôt que l’erreur qua-
dratique moyenne un critère d’impureté, ainsi appelé car il quantifie à quel point la
région considérée est « polluée » par des éléments des classes qui n’y sont pas majo-
ritaires. En notant Imp ce critère, on choisit donc la variable et le point de séparation
comme
|Rl (j, s)| |Rr (j, s)|
arg min Imp(Rl (j, s)) + Imp(Rr (j, s)).
j,s n n
Encore une fois, il s’agit d’un algorithme glouton : il n’y a aucune garantie que
cette stratégie aboutisse à l’arbre de décision dont l’impureté ou l’erreur quadratique
moyenne est minimale.
128
9.2 Comment faire pousser un arbre
C
Imp(R) = − pc (R) log2 pc (R). (9.4)
c=1
129
Chapitre 9 r Arbres et forêts
|T|
Cλ (T) = nr Imp(Rr ) + λ|T|, (9.5)
r=1
Exemple
Pour illustrer ce concept, imaginons une tâche de classification en deux dimen-
sions, dans laquelle les deux classes sont séparées par une diagonale, mais que le
seul algorithme d’apprentissage dont nous disposions ne puisse apprendre qu’une
frontière de décision en escaliers, avec un nombre limité de paliers. Combiner des
dizaines voire des centaines de ces frontières de décision en escalier peut nous
donner une bien meilleure approximation de la véritable frontière de décision. Cet
exemple est illustré sur la figure 9.4.
130
9.3 Méthodes ensemblistes : la sagesse des foules
La théorie des méthodes ensemblistes montre que lorsque les modèles que l’on
combine ont été appris par des apprenants faibles, c’est-à-dire simples à entraîner
et peu performants permet d’améliorer la performance par rapport à celle du mei-
leur de ces modèles individuels. En pratique, si les modèles individuels sont déjà
performants et robustes au bruit, le modèle ensembliste ne sera pas nécessaire-
ment meilleur. On utilise le plus souvent des arbres de décision comme modèles
individuels.
131
Chapitre 9 r Arbres et forêts
mais ils font des erreurs sur des régions différentes de l’espace, qui se compensent
lorsqu’on les combine.
Figure 9.5 – Performance sur un jeu de test d’un classifieur entraîné par bagging
(en bas à droite) et des 5 premiers arbres qui le composent.
Forêts aléatoires
La puissance des méthodes ensemblistes se révèle lorsque les apprenants faibles sont
indépendants conditionnellement aux données, autrement dit aussi différents les uns
des autres que possible, afin que leurs erreurs puissent se compenser les unes les
autres. Pour atteindre cet objectif, l’idée des forêts aléatoires, proposée toujours par
Leo Breiman, est de construire les arbres individuels non seulement sur des échan-
tillons différents (comme pour le bagging), mais aussi en utilisant des variables
différentes (Breiman, 2001).
Plus précisément, les arbres construits pour former une forêt aléatoire diffèrent
de ceux appris par CART en ce que, à chaque nœud, on commence par sélectionner
q < p variables aléatoirement, avant de choisir la variable séparatrice parmi celles-
√
ci. En classification, on utilise typiquement q ≈ p, ce qui permet aussi de réduire
considérablement les temps de calculs puisqu’on ne considère que peu de variables
à chaque nœud (5 pour un problème à 30 variables, 31 pour un problème avec 1000
variables). Pour la régression, le choix par défaut est plutôt de q ≈ p3 .
132
9.3 Méthodes ensemblistes : la sagesse des foules
Le fait de moyenner les réponses des différents arbres permet d’utiliser les forêts
aléatoires aussi bien pour des problèmes de régression que de classification.
En pratique, les forêts aléatoires sont un des algorithmes les plus performants
et les plus simples à mettre en place. Elles ont aussi l’avantage de peu dépendre
de leurs hyperparamètres, à savoir du nombre q de variables considérées à chaque
nœud, du nombre d’observations utilisées pour chaque arbre (n dans la procédure
que nous avons décrite, mais que l’on pourrait réduire), du nombre maximum d’ob-
servations dans les feuilles de l’arbre (généralement fixé à 1 en classification et 5 en
régression), et du nombre d’arbres, à partir du moment où celui-ci est suffisamment
grand.
AdaBoost
AdaBoost, dont le nom vient de Adaptive Boosting, est un algorithme qui permet
de construire un classifieur de manière itérative, en forçant un classifieur faible à se
concentrer sur les erreurs du modèle grâce à un système de pondération des exemples
d’entraînement.
Définition 9.4 (AdaBoost)
© Dunod - Toute reproduction non autorisée est un délit.
133
Chapitre 9 r Arbres et forêts
1 1 − εm
αm = log . (9.7)
2 εm
αm est d’autant plus élevé que l’erreur globale du modèle est faible : on pourra
alors lui faire plus confiance.
d. Actualiser les poids, de sorte à donner plus d’importance à un exemple
d’entraînement sur lequel fm se trompe :
n
1 m −αm y i fm (x i )
wlm e−αm y fm (x ) .
l l
wim+1 = wi e où Zm = (9.8)
Zm
l=1
Boosting du gradient
AdaBoost se trouve en fait être un cas particulier d’une famille de techniques appelées
boosting du gradient (gradient boosting, ou GBOOST), dont le cadre théorique a été
développé en 1999 par, d’une part Jerome H. Friedman, et d’autre part Llew Mason,
Jonathan Baxter, Peter Bartlett et Marcus Frean (Friedman, 2001; Mason et al.,
1999).
134
9.3 Méthodes ensemblistes : la sagesse des foules
{−1, 1} × R → R
→ e−yf (x)
y, f (x) .
Reprenons l’algorithme
AdaBoost, et appelons Fm la fonction de décision cumu-
lative Fm : x → m α
k=1 k k x).
f (
À l’étape m, l’erreur exponentielle de Fm sur le jeu d’entraînement vaut
! "
1
n m−1
Em = exp −y i
αk fk (
x ) exp −αm yi fm (
i
x i)
n
i=1 k=1
1
n
= exp −yi Fm−1 (
x i ) exp −αm yi fm (
x i) .
n
i=1
i = exp −y Fm−1 (
Définissons maintenant wm i x i ) ; alors
1 m
n
Em = wi exp −αm yi fm (
x i) .
n
i=1
1 m −αm 1
n
αm
Em = + wm − e−αm .
© Dunod - Toute reproduction non autorisée est un délit.
wi e i e
n n
i=1 x i )=yi
i:fm (
Cette erreur est minimale quand αm a la forme donnée par l’équation 9.7. Ainsi,
AdaBoost combine les apprenants faibles de sorte à minimiser, à chaque étape,
l’erreur exponentielle du classifieur global.
L’erreur exponentielle peut être remplacée par une autre fonction de coût, telle
que l’entropie croisée ou l’erreur quadratique : c’est ce que l’on appelle le boos-
ting du gradient. GBOOST est aujourd’hui un des algorithmes les plus populaires en
machine learning.
135
Chapitre 9 r Arbres et forêts
Points clefs
r Les arbres de décision sont des modèles interprétables, qui manient naturel-
lement des variables de plusieurs natures (réelles, discrètes et binaires) et se
prêtent aisément à l’apprentissage multi-classe de distributions multi-modales.
r Les arbres de décision ont le grand inconvénient d’être des apprenants faibles,
et d’avoir en général une capacité de modélisation trop limitée pour avoir de
bonnes performances en pratique.
r Les méthodes ensemblistes permettent de remédier aux limitations des appre-
nants faibles tels que les arbres de décision, en combinant ces modèles de sorte
à compenser leurs erreurs respectives.
r Les méthodes ensemblistes parallèles, telles que le bagging ou les forêts aléa-
toires, construisent un grand nombre de modèles faibles entraînés sur un
échantillonage bootstrap des données.
r Les forêts aléatoires entraînent leurs arbres de façon à ce qu’ils soient indé-
pendants les uns des autres conditionnelement aux données, en sélectionnant
aléatoirement les variables à considérer à la création de chaque nœud.
r Les algorithmes de boosting combinent des modèles faibles entraînés séquen-
tiellement pour donner plus d’importance aux exemples d’entraînement sur
lesquels les prédictions sont les moins bonnes.
Bibliographie
Breiman, L. (1996). Bagging predictors. Machine Learning, 26:123-140.
Breiman, L. (2001). Random forests. Machine Learning, 45(1):5-32.
Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification
and Regression Trees. Wadsworth International Group, Belmont, CA.
136
Exercices
Exercices
Label + + + + + + − − − −
© Dunod - Toute reproduction non autorisée est un délit.
Longueur (cm) 6,7 6,7 6,3 6,5 6,2 5,9 6,1 6,4 6,6 6,8
Largeur (cm) 3,3 3,0 2,5 3,0 3,4 3,0 2,8 2,9 3,0 2,8
1. Calculer l’impureté de Gini pour tous les points de séparation possibles en utilisant
la longueur des sépales comme variable séparatrice.
2. Calculer l’impureté de Gini pour tous les points de séparation possibles en utilisant
la largeur des sépales comme variable séparatrice.
3. Quel est le premier nœud d’un arbre de décision entraîné sur ces données avec
l’impureté de Gini ?
137
Chapitre 9 r Arbres et forêts
9.4 Djamel aimerait prédire si son bus sera à l’heure ou non. Il récolte des don-
nées sur 7 jours : la météo, s’il essaie de prendre le bus en heure creuse ou en heure
pleine, et s’il a ou non une réunion importante ce jour-là.
Solutions
9.1 De mauvaises performances (apprenants faibles).
9.3
1.
s <5,9 5,9 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8
GI – 0,444 0,475 0,476 0,450 0,480 0,467 0,476 0,400 –
2.
s <2,5 2,5 2,8 2,9 3,0 3,3 3,4
GI – 0,444 0,419 0,317 0,400 0,444 –
3. La valeur d’impureté de Gini la plus faible est 0,317, obtenue en séparant sur la
longueur au seuil de 2,9 cm. Le premier nœud de l’arbre de décision compare donc
la longueur des sépales à la valeur 2,9. À gauche, 4 plantes dont 1 Iris virginica ;
à droite, 6 plantes dont 5 Iris virginica.
138
Exercices
9.4
Heure creuse
|_ oui _ [+]
|_ non _ soleil
|_ non _ [-]
|_ oui _ réunion
|_ non _ [+]
|_ oui _ [-]
9.7
1. Chaque feuille contient au moins une observation, donc n.
2. Chaque feuille contient au moins une observation, donc n (si chaque nœud sur le
chemin entre la racine et une feuille contient une observation).
© Dunod - Toute reproduction non autorisée est un délit.
139
10 MACHINES À VECTEURS
DE SUPPORT ET
MÉTHODES À NOYAUX
Les machines à vecteurs de support (aussi appelées machines à
vecteurs supports), ou SVM de l’anglais support vector machines,
INTRODUCTION
140
10.1 Le cas linéairement séparable : SVM à marge rigide
Dans ce cas, il existe en fait une infinité d’hyperplans séparateurs qui ne font
aucune erreur de classification (voir figure 10.1). Ces hyperplans sont des modèles
équivalents du point de vue de la minimisation du risque empirique.
Figure 10.1 – Une infinité d’hyperplans (en deux dimensions, des droites) séparent
les points négatifs (x) des points positifs (+).
L’hyperplan séparateur que nous cherchons est donc celui qui maximise la marge.
Il y a alors au moins une observation négative et une observation positive qui sont à
une distance γ de l’hyperplan séparateur : dans le cas contraire, si par exemple toutes
les observations négatives étaient à une distance supérieure à γ de l’hyperplan sépa-
rateur, on pourrait rapprocher cet hyperplan des observations négatives et augmenter
la marge.
Nous pouvons alors définir, en plus de l’hyperplan séparateur H, les hyperplans
H+ et H− qui lui sont parallèles et situés à une distance γ de part et d’autre. H+
141
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
contient au moins une observation positive, tandis que H− contient au moins une
observation négative.
Figure 10.2 – La marge γ d’un hyperplan séparateur (ici en trait plein) est sa
distance à l’observation la plus proche. Quand cette marge est maximale, au moins
une observation négative et une observation positive sont à une distance γ de
l’hyperplan séparateur. Les hyperplans (ici en pointillés) parallèles à l’hyperplan
séparateur et passant par ces observations définissent la zone d’indécision.
Les observations situées sur ces hyperplans (cerclées) sont les vecteurs de support.
142
10.1 Le cas linéairement séparable : SVM à marge rigide
garantissent donc que la fonction objective de la SVM à marge rigide (minimisée dans
l’équation 10.1) est minimisée aux mêmes points que son dual (voir section A.4.3).
Nous pouvons donc en déduire une deuxième formulation équivalente du problème :
143
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Démonstration
Il s’agit de la formulation duale d’un problème d’optimisation convexe sous
contraintes (voir section A.4). Introduisons n multiplicateurs de Lagrange
{αi }i=1,...,n , un pour chaque contrainte. Le lagrangien est donc la fonction
L : Rp × R × R n
+ → R (10.4)
1 (((( ((((2 i
n
b, α
w, → 2−
w x i + b − 1 .
αi y w,
2
i=1
q : Rn
+ → R (10.5)
α → inf b, α )
L(w,
p ,b∈R
w∈R
Enfin, le problème dual de celui présenté par l’équation 10.1 est donc
1 (((( ((((2 i
n
max inf 2−
w x i + b − 1
αi y w, (10.6)
n p ,b∈R 2
α ∈R+ w∈R
i=1
De plus, il est affine en b. Son infimum est donc −∞, sauf si son gradient en b est
nul (auquel cas la fonction affine est « plate »), à savoir si
n
αi y i = 0. (10.8)
i=1
Pour résoudre le problème primal (équation 10.1), on peut donc commencer par
résoudre le problème dual (équation 10.3). Supposons α ∗ solution du problème
10.3.
L’équation 10.7 nous donne la solution en w de l’équation 10.1 : w ∗ = ni=1 αi∗ yi x i .
144
10.2 Le cas linéairement non séparable : SVM à marge souple
Complexité algorithmique
La formulation primale de la SVM est un problème d’optimisation en p + 1 di-
mensions, tandis que la formulation duale est un problème d’optimisation en n
dimensions. Si l’on a peu de données et beaucoup de variables, on préférera la
formulation duale ; dans le cas inverse, on préférera résoudre le problème primal.
Ainsi, les vecteurs de support sont les observations du jeu de données correspon-
dant à un multiplicateur de Lagrange αi∗ non nul.
145
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Figure 10.3 – Aucun classifieur linéaire ne peut séparer parfaitement ces données.
Les observations marquées d’un carré sont des erreurs de classification.
L’observation marquée d’un triangle est correctement classifiée mais est située
à l’intérieur de la zone d’indécision. Si elle était à sa frontière, autrement dit,
si elle était vecteur de support, la marge serait beaucoup plus étroite.
1 n
arg min ||w||
22 + C x i + b, yi ).
L(w, (10.10)
w∈Rp ,b∈R 2
i=1
146
10.2 Le cas linéairement non séparable : SVM à marge souple
n &
'
1 (((( ((((2
arg min 2+C
w 1 − y i f (x i ) . (10.11)
p ,b∈R 2
w∈R +
i=1
Cette formulation est celle d’une régularisation de la minimisation d’un risque em-
pirique par un terme de norme 2 . Elle est similaire à la régression ridge (voir
chapitre 6), C étant inversement proportionnel à λ, mais la fonction d’erreur est
différente.
ξi ≥ 0, i = 1, . . . , n.
i=1
Démonstration
Introduisons 2n multiplicateurs de Lagrange {αi , βi }i=1,...,n et écrivons le lagran-
gien :
L : R p × R × R n × Rn n
+ × R+ → R (10.14)
n
1 (((( ((((2
b, ξ , α , β
w, → 2+C
w ξi
2
i=1
n
n
− αi y i w,
x i + b − 1 + ξi − βi ξi .
i=1 i=1
147
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
q : Rn n
+ × R+ → R (10.15)
α , β → inf b, ξ , α , β)
L(w,
p ,b∈R,ξ ∈Rn
w∈R
n
1 (((( ((((2
max inf 2+C
w ξi
p ,b∈R,ξ ∈Rn 2
n+ w∈R
α ∈Rn+ ,β∈R i=1
n
n
− αi y i w,
x i + b − 1 + ξi − βi ξi . (10.16)
i=1 i=1
Comme dans le cas de la SVM à marge rigide, le lagrangien est minimal quand son
est nul, à savoir quand
gradient en w
n
=
w αi y i x i . (10.17)
i=1
Toujours comme précédemment, il est affine en b et son infimum est donc −∞,
sauf si son gradient en b est nul, à savoir si
n
αi y i = 0. (10.18)
i=1
De plus, il est affine en ξ et son infimum est donc −∞, sauf si son gradient en ξ est
nul, à savoir si
βi = C − αi , i = 1, . . . , n. (10.19)
La fonction duale q est donc maximisée quand les équations 10.18 et 10.19 sont
vérifiés.
En remplaçant w par son expression (équation 10.17) dans l’expression de la
fonction duale, l’équation 10.16 peut donc être reformulée comme
n n n n n n
1
max − αi αl y i y l x i , x l + αi + C ξi − (C − αi )ξi − αi ξi
α ∈Rn 2
i=1 l=1 i=1 i=1 i=1 i=1
n
t. q. αi y i = 0 ; αi ≥ 0, i = 1, . . . , n ; C − αi ≥ 0, i = 1, . . . , n.
i=1
148
10.3 Le cas non linéaire : SVM à noyau
Il est possible d’utiliser les SVM pour construire un classifieur multi-classe, grâce à
une approche une-contre-toutes ou une-contre-une (cf. section 2.1.2).
x22 = R2 semble bien mieux indiqué qu’une droite pour séparer les deux classes. Or
si la fonction f : R2 → R, x → x12 + x22 − R2 n’est pas linéaire en x = (x1 , x2 ),
elle est linéaire en (x12 , x22 ). Définissons donc l’application φ : R2 → R2 , (x1 , x2 ) →
(x12 , x22 ). La fonction de décision f est linéaire en φ( x ) = φ(
x ) : f ( x )1 + φ(
x )2 − R2 .
Nous pouvons donc l’apprendre en utilisant une SVM sur les images des données par
l’application φ.
Plus généralement, nous allons maintenant supposer que les observations sont défi-
nies sur un espace quelconque X, qui peut être Rp mais aussi par exemple l’ensemble
des chaînes de caractères sur un alphabet donné, l’espace de tous les graphes, ou un
espace de fonctions.
149
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
(a) Un cercle semble bien mieux indiqué qu’une (b) Après transformation par l’application φ :
droite pour séparer ces données. (x1 , x2 ) → (x12 , x22 ), les données sont linéairement
séparables dans l’espace de redescription.
150
10.3 Le cas non linéaire : SVM à noyau
Que ce soit pour entraîner la SVM ou pour l’appliquer, nous n’avons pas besoin de
connaître φ explicitement, mais il nous suffit de connaître le noyau k. Cela signifie que
nous n’avons pas besoin de faire de calcul dans H, qui est généralement de très grande
dimension : c’est ce que l’on appelle l’astuce du noyau. L’astuce du noyau s’applique
de manière générale à d’autres algorithmes d’apprentissage linéaires, comme la ré-
gression ridge (cf. section 6.2), l’ACP (cf. section 11.3.1) ou encore la méthode des
k-moyennes (cf. section 12.4).
© Dunod - Toute reproduction non autorisée est un délit.
10.3.4 Noyaux
Caractérisation mathématique
Définition 10.10 (Noyau)
Nous appelons noyau toute fonction k de deux variables s’écrivant sous la forme
d’un produit scalaire des images dans un espace de Hilbert de ses variables. Ainsi,
un noyau est une fonction continue, symétrique, et semi-définie positive :
∀ N ∈ N, ∀ (x 1 , x 2 , . . . x N ) ∈ XN
N
N
et (a1 , a2 , . . . aN ) ∈ RN , ai al k(x i , x l ) ≥ 0.
i=1 l=1
151
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Démonstration
On trouvera une preuve de ce résultat dans l’article original de Nachman Aronszajn,
qui l’attribue à E. Hastings Moore (Aronszajn, 1950).
Intuitivement, un noyau peut être interprété comme un produit scalaire sur un es-
pace de Hilbert, autrement dit comme une fonction qui mesure la similarité entre
deux objets de X. Ainsi, on peut définir des noyaux en construisant une similarité
entre objets, puis en vérifiant qu’elle est semi-définie positive.
152
10.3 Le cas non linéaire : SVM à noyau
mun, plus elles sont semblables. Étant donnée une longueur k ∈ N de sous-chaînes,
nous transformons une chaîne x en un vecteur de longueur |A|k grâce à l’application
φ : x → (ψu (x))u∈Ak , où ψu (x) est le nombre d’occurrences de u dans x. ψ peut être
modifiée pour permettre les alignements inexacts, ou autoriser en les pénalisant les
« trous » (ou gaps).
On peut alors définir le noyau pour chaînes de caractères suivant :
k : A∗ × A∗ → R
x, x → ψu (x)ψu (x ).
u∈Ak
153
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Démonstration
La preuve de ce théorème repose sur un résultat de Gower (1971).
154
10.4 Régression ridge à noyau
α = y − XX α et donc
Ainsi λ
−1
α = λIn + XX y.
α = xX (λIn + XX )−1 y.
f (x ) = xX (10.26)
où ∈ Rn×d est la matrice dont la i-ème ligne est l’image par φ dans H (supposé ici
de dimension d) de x i . On peut réécrire cette fonction comme
Points clefs
r La SVM à marge souple est un algorithme linéaire de classification binaire qui
© Dunod - Toute reproduction non autorisée est un délit.
155
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Bibliographie
Aronszajn, N. (1950). Theory of reproducing kernels. Transactions of the
American Mathematical Society, 68(3):337-404.
Boser, B. E., Guyon, I. M., and Vapnik, V. N. (1992). A training algorithm for
optimal margin classifiers. In Proceedings of the Fifth annual Workshop on
Computational Learning Theory, pages 144-152, Pittsburgh, Pennsylvania,
United States. ACM.
156
10.4 Régression ridge à noyau
157
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
Exercices
10.1 Noyaux Parmi les fonctions suivantes, lesquelles sont des noyaux ?
1.
k : [0, 1] × [0, 1] → R
x, x → min(x, x )
2.
k :R×R→R
x, x → max(x, x )
3.
k :R×R→R
#
x − x ||22 + 1
x, x → ||
4.
k : Rp × Rp → R
p ! "
xj − a xj − a
x, x → h h
b b
j=1
avec h : u → exp(−u2 ) et a, b ∈ R.
158
Exercices
10.4 Peut-on appliquer l’astuce du noyau au lasso (cf. section 6.3) de la même
manière qu’à la régression ridge ?
10.5 Cléa a un jeu de données contenant des millions d’observations et des cen-
taines de variables. Lui recommandez-vous d’utiliser la forme primale du problème
d’optimisation ou sa forme duale pour entraîner une SVM linéaire ?
10.6 Driss a entraîné une SVM avec un noyau polynomial sur ses données
et remarque qu’elle semble sous-apprendre. Quel(s) hyperparamètre(s) changer, et
comment ?
© Dunod - Toute reproduction non autorisée est un délit.
159
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
3. Quelle mesure de performance utiliser pour évaluer l’algorithme sur les données ?
Solutions
10.1
n
n
n 1 1
ai aj k(x , x ) =
i j
ai aj δt≤xi δt≤xj dt
i=1 j=1 i=1 0 0
! n "⎛ n ⎞
1
= ai δt≤xi ⎝ aj δt≤xj ⎠ dt
0 i=1 j=1
n
qui est donc l’intégrale du carré de la fonction x → i=1 ai δt≤xi et est donc
positive.
0 1
2. Non. Prenons x = 0, x = 1. La matrice K =
1 2 n’est pas définie car le
1 1
produit (a1 , a2 ) K (a1 , a2 ) peut être positif ou négatif.
160
Exercices
10.2
10.3
1. Une valeur élevée de C signifie que la SVM fera peu d’erreurs sur le jeu d’en-
traînement. Le noyau quadratique conduit à une frontière de décision ellipsoïdale.
Voir figure 10.5a.
2. Une valeur faible de C signifie que la SVM aura une large marge, quitte à faire
des erreurs sur le jeu d’entraînement. Voir figure 10.5b.
© Dunod - Toute reproduction non autorisée est un délit.
161
Chapitre 10 r Machines à vecteurs de support et méthodes à noyaux
(a) La nouvelle observation (x) de la classe « tri- (b) La nouvelle observation (x) de la classe « tri-
angle » n’affecte pas la frontière de décision. angle » affecte la frontière de décision.
10.4 Non : la norme 1 ne s’écrit pas sous forme de produit scalaire entre les
images.
10.5 La forme primale sera beaucoup plus efficace à résoudre que la duale.
10.7
1. En introduisant 2n multiplicateurs de Lagrange :
1 n n
L = ||w||
22 − αi ε − yi + w,
x i + b − αi∗ ε + yi − w,
x i − b .
2
i=1 i=1
162
Exercices
n
x) =
2. f ( i=1 (αi − αi∗ )
x i , x + b.
3. Les conditions de Karush-Kuhn-Tucker nous donnent αi (ε − yi + w, x i + b) = 0
∗
et αi (ε + y − w,
i x − b) = 0. Ainsi, αi = 0 si et seulement si y − w,
i i x i + b = ε
∗
et αi = 0 si et seulement si y − w,
i x + b = −ε.
i
Les observations dont l’étiquette est à une distance ε de la prédiction sont vecteurs
de support. Ils définissent w et donc f .
4. Oui. Étant donné un noyau k : X × X → R, on peut réécrire la forme duale sans
utiliser explicitement l’espace de redescription ni l’application correspondante :
arg max − 12 ni,j=1 (αi −αi∗ )(αj −αj∗ )k(xi , xj )−ε ni=1 (αi −αi∗ )+ ni=1 yi (αi −αi∗ ),
sous la contrainte ni=1 (αi − αi∗ ) = 0.
De même pour l’expression de f : f ( x ) = ni=1 (αi − αi∗ )k( x i , x ) + b.
Le problème peut donc être posé et résolu sans faire appel à l’espace de
redescription, uniquement en utilisant des noyaux.
10.8
1. La norme 1 induit un modèle parcimonieux.
2.
n
p
min ξi + λ (v+ −
j + vj )
v + >0,v − >0,ξi >0
i=1 j=0
⎛ ⎞
p
sous les contraintes yi ⎝w0 + (v+ − i⎠
j + vj )xj ≥ 1 − ξi
j=1
5. Oui, à cause du terme de régularisation, le modèle sera différent selon que les
variables sont normalisées ou non.
163
11 RÉDUCTION DE
DIMENSION
Dans certaines applications, le nombre de variables p utilisé pour
représenter les données est très élevé. C’est le cas par exemple du trai-
INTRODUCTION
données.
Faire la différence entre la sélection de variables et l’extraction de variables.
Connaître les principales techniques pour ces deux approches.
Comprendre l’analyse en composantes principales à partir d’une définition
de maximisation de la variance et comme une technique de factorisation
de matrice.
11.1 MOTIVATION
Le but de la réduction de dimension est de transformer une représentation X ∈ Rn×p
des données en une représentation X ∗ ∈ Rn×m où m p. Les raisons de cette
démarche sont multiples, et nous les détaillons dans cette section.
164
11.1 Motivation
Enfin, nous faisons face en haute dimension à un phénomène connu sous le nom
de fléau de la dimension, ou curse of dimensionality en anglais. Ce terme quali-
fie le fait que les intuitions développées en faible dimension ne s’appliquent pas
nécessairement en haute dimension.
En effet, en haute dimension, les exemples d’apprentissage ont tendance à tous
être éloignés les uns des autres. Pour comprendre cette assertion, plaçons-nous en
dimension p et considérons l’hypersphère S( x, r) de rayon R ∈ R+ centrée sur
165
Chapitre 11 r Réduction de dimension
une observation x, ainsi que l’hypercube C( x, R) circonscrit à cette hypersphère. Le
2Rp π p/2
volume de S(x ) vaut p(p/2) , tandis que celui de C(
x, R), dont le côté a pour longueur
2R, vaut 2p Rp . Ainsi
Vol(S(
x, R))
lim = 0.
p→∞ Vol(R(
x, R))
Cela signifie que la probabilité qu’un exemple situé dans C( x, R) appartienne à
x, R), qui vaut π4 ≈ 0,79 lorsque p = 2 et π6 ≈ 0,52 lorsque p = 3 (cf. figure 11.2),
R(
devient très faible quand p est grand : les données ont tendance à être éloignées les
unes des autres.
Cela implique que les algorithmes développés en utilisant une notion de simi-
larité, comme les plus proches voisins, les arbres de décision ou les SVM, ne
fonctionnent pas nécessairement en grande dimension. Ainsi, réduire la dimension
peut être nécessaire à la construction de bons modèles.
Deux possibilités s’offrent à nous pour réduire la dimension de nos données :
• la sélection de variables, qui consiste à éliminer un nombre p − m de variables de
nos données ;
• l’extraction de variables, qui consiste à créer m nouvelles variables à partir des p
variables dont nous disposons initialement.
La suite de ce chapitre détaille ces deux approches.
166
11.2 Sélection de variables
167
Chapitre 11 r Réduction de dimension
données sans l’avoir entraîné. Il n’est pas raisonnable d’adopter une stratégie exhaus-
tive, sauf pour un très faible nombre de variables, car le nombre de sous-ensembles de
p variables est de 2p − 1 (en excluant {0}). On adoptera donc une approche gloutonne.
Quelques exemples de ces approches sont la recherche ascendante, la recherche
descendante, et la recherche flottante que nous détaillons ci-dessous.
Étant donnés un jeu de données D = (X, y) où X ∈ Rn×p , un sous-ensemble
de variables E ⊂ {1, 2, . . . , p}, et un algorithme d’apprentissage, on notera XE ∈
Rn×|E| la matrice X restreinte aux variables apparaissant dans E, et ED (E) l’estimation
de l’erreur de généralisation de cet algorithme d’apprentissage, entraîné sur (XE , y).
Cette estimation est généralement obtenue sur un jeu de test ou par validation croisée.
La recherche ascendante consiste à partir d’un ensemble de variables vide, et à lui
ajouter variable par variable celle qui améliore au mieux sa performance, jusqu’à ne
plus pouvoir l’améliorer.
Définition 11.2 (Recherche ascendante)
On appelle recherche ascendante, ou forward search en anglais, la procédure
gloutonne de sélection de variables suivante :
1. Initialiser F = ∅ ;
2. Trouver la meilleure variable à ajouter à F :
j ∗ = arg min ED (F ∪ { j}) ;
j∈{1,...,p}\F
Dans le pire des cas (celui où on devra itérer jusqu’à ce que F = {1, 2, . . . , p}), cet
algorithme requiert de l’ordre de O( p2 ) évaluations de l’algorithme d’apprentissage
sur un jeu de données, ce qui peut être intensif, mais est bien plus efficace que O(2p )
comme requis par l’approche exhaustive.
À l’inverse, la recherche descendante consiste à partir de l’ensemble de toutes
les variables, et à lui retirer variable par variable celle qui améliore au mieux sa
performance, jusqu’à ne plus pouvoir l’améliorer.
Définition 11.3 (Recherche descendante)
On appelle recherche descendante, ou backward search en anglais, la procédure
gloutonne de sélection de variables suivante :
1. Initialiser F = {1, . . . , p} ;
2. Trouver la meilleure variable à retirer de F :
j ∗ = arg min ED (F \ { j}) ;
j∈F
168
11.3 Extraction de variables
1. Initialiser F = ∅ ;
2. Trouver les q meilleures variables à ajouter à F :
S∗ = arg min ED (F ∪ S) ;
S⊆{1,...,p}\F, |S|=q
3. Si ED (F ∪ S) < ED (F) : F ← F ∪ S ;
4. Trouver les r meilleures variables à retirer de F :
S∗ = arg min ED (F \ S) ;
S⊆{1,...,p}\F, |S|=r
de ces techniques est le lasso, que nous avons vu dans la section 6.3.
Dans le même ordre d’idée, la mesure d’importance des variables dans les forêts
aléatoires (voir chapitre 9) peut être utilisée pour décider quelles variables éliminer.
169
Chapitre 11 r Réduction de dimension
Maximisation de la variance
L’idée centrale d’une ACP est de représenter les données de sorte à maximiser leur
variance selon les nouvelles dimensions, afin de pouvoir continuer à distinguer les
exemples les uns des autres dans leur nouvelle représentation (cf. figure 11.3).
Formellement, une nouvelle représentation de X est définie par une base orthonor-
mée sur laquelle projeter la matrice de données X.
Définition 11.5 (Analyse en composantes principales)
Une analyse en composantes principales, ou ACP, de la matrice X ∈ Rn×p est une
transformation linéaire orthogonale qui permet d’exprimer X dans une nouvelle
base orthonormée, de sorte que la plus grande variance de X par projection s’aligne
sur le premier axe de cette nouvelle base, la seconde plus grande variance sur le
deuxième axe, et ainsi de suite.
Les axes de cette nouvelle base sont appelés les composantes principales, abrégées
en PC pour Principal Components.
Dans la suite de cette section, nous supposons que les variables ont été standardi-
sées de sorte à toutes avoir une moyenne de 0 et une variance de 1, pour éviter que
les variables qui prennent de grandes valeurs aient plus d’importance que celles
qui prennent de faibles valeurs. C’est un prérequis de l’application de l’ACP. Cette
standardisation s’effectue en centrant la moyenne et en réduisant la variance de
chaque variable :
n
xji − 1
n l=1 xj
l
i ← (11.2)
xj 2 .
1 n l 1 n l
n l=1 xj − n l=1 xj
On dira alors que X est centrée : chacune de ses colonnes a pour moyenne 0.
Théorème 11.1
Soit X ∈ Rn×p une matrice centrée de covariance = 1
n X X . Les composantes
principales de X sont les vecteurs propres de , ordonnés par valeur propre
décroissante.
170
11.3 Extraction de variables
Démonstration
Commençons par démontrer que, pour tout vecteur w ∈ Rp , la variance de la
vaut w w.
projection de X sur w
∈ Rp est le vecteur z = Xw. Comme X est centrée,
La projection de X ∈ Rn×p sur w
la moyenne de z vaut
n n p p n
1 1 i 1
zi = xj wj = wj xji = 0.
n n n
i=1 i=1 j=1 j=1 i=1
Sa variance vaut
n
1 2 1
=
Var[z] zzi = w X Xw w.
=w
n n
i=1
(( ((
w 2 = arg max w w avec ((w w
2 ((2 = 1 et w 1 = 0. (11.4)
p
w∈R
Cette dernière contrainte nous permet de garantir que la base des composantes
principales est orthonormée.
Nous introduisons donc maintenant deux multiplicateurs de Lagrange α2 > 0 et
β2 > 0 et obtenons le lagrangien
(( ((
w
=w
L(α2 , β2 , w) − α2 ((w
((2
2 − 1 − β2 w w 1 .
171
Chapitre 11 r Réduction de dimension
En multipliant à gauche par w 1 , on obtient
2w 1 w
2 − 2α2 w 1w
2 − β2 w 1 = 0
1w
d’où l’on conclut que β2 = 0 et, en remplaçant dans l’équation précédente, que,
comme pour w 2 = 0. Ainsi (α2 , w
2 − 2α1 w
1 , 2 w 2 ) sont un couple (valeur propre,
vecteur propre) de et α2 est maximale : il s’agit donc nécessairement de la
deuxième valeur propre de .
Le raisonnement se poursuit de la même manière pour les composantes principales
suivantes.
w 1 w
1 = w 1Q
Qw 1
1 = Qw 1 .
Qw
Démonstration
Si l’on écrit X sous la forme UDV où U ∈ Rn×n , V ∈ Rp×p , et D ∈ Rn×p diagonale,
alors
= X X = VDU UDV = VD 2 V
et les valeurs singulières de X (les entrées de D) sont les racines carrées des valeurs
propres de , tandis que les vecteurs singuliers à droite de X (les colonnes de V )
sont les vecteurs propres de .
172
11.3 Extraction de variables
α1 + α2 + · · · + αm
Tr()
(a) Pourcentage de variance expliqué par chacune des (b) Pourcentage cumulé de variance expliquée par
composantes principales. À partir de 6 composantes chacune des composantes principales. Si on se fixe
principales, ajouter de nouvelles composantes n’est une proportion de variance expliquée de 95 %, on
plus vraiment informatif. peut se contenter de 10 composantes principales.
173
Chapitre 11 r Réduction de dimension
Analyse factorielle
Cette factorisation s’inscrit dans le cadre plus général de l’analyse factorielle.
Supposons que les observations { x 1 , x 2 , . . . , x n } soient les réalisations d’une
variable aléatoire p-dimensionnelle x, générée par le modèle
x = W h + ε, (11.7)
où h est une variable aléatoire m-dimensionnelle qui est la représentation latente de
x, et ε un bruit gaussien : ε ∼ N(0, ).
Supposons les données centrées en 0, et les variables latentes h 1 , h 2 , . . . , h n (qui
sont des réalisations de h) indépendantes et gaussiennes de variance unitaire, c’est-à-
dire h ∼ N(0, Im ) où Im est la matrice identité de dimensions m × m. Alors W h est
centrée en 0, et sa covariance est WW . Alors x ∼ N(0, WW + ).
Si on considère de plus que ε est isotropique, autrement dit que = σ 2 Ip ,
alors x ∼ N(0, WW + σ 2 Ip ), on obtient ce que l’on appelle ACP probabiliste
(Tipping et Bishop, 1999). Les paramètres W et σ de ce modèle peuvent être obtenus
par maximum de vraisemblance.
L’ACP classique est un cas limite de l’ACP probabiliste, obtenu quand la
covariance du bruit devient infiniment petite (σ 2 → 0).
Plus généralement, on peut faire l’hypothèse que les variables observées
x1 , x2 , . . . , xp sont conditionnellement indépendantes étant données les variables la-
tentes h1 , h2 , . . . , hm . Dans ce cas, est une matrice diagonale, = diag(ψ1 ,
ψ2 , . . . , ψp ), où ψj décrit la variance spécifique à la variable xj . Les valeurs de
W, σ et ψ1 , ψ2 , . . . , ψp peuvent encore une fois être obtenues par maximum de
vraisemblance. C’est ce que l’on appelle l’analyse factorielle.
174
11.3 Extraction de variables
Dans l’analyse factorielle, nous ne faisons plus l’hypothèse que les nouvelles
dimensions sont orthogonales. En particulier, il est donc possible d’obtenir des di-
mensions dégénérées, autrement dit des colonnes de W dont toutes les coordonnées
sont 0.
où ||.||F désigne la norme de Frobenius d’une matrice, autrement dit la racine carrée
de la somme des carrés de ses entrées. Ainsi, ||X − WH||2F compare les matrices X et
de WH entrée par entrée.
Le problème 11.8 peut être résolu par un algorithme à directions de descente (voir
section A.3.3).
Exemple
Cette technique peut être appliquée, par exemple, dans l’analyse des notes données
par des spectateurs à différents films. Supposons avoir n spectateurs qui ont donné
des notes entre 0 et 5 à p films ; une factorisation non négative permet d’interpréter
une de ces notes (xji ) comme la combinaison de l’importance pour le spectateur i
des m aspects d’un film (donnée par h i ∈ Rm ), et de la présence de chacun de ces
+
aspects dans le film (donnée par la j-ème ligne de W ).
© Dunod - Toute reproduction non autorisée est un délit.
Cette technique peut aussi être utilisée pour faire de la complétion de matrice,
c’est-à-dire dans le cas où X a des valeurs manquantes (tous les spectateurs n’ont
pas noté tous les films). Plutôt que de chercher à minimiser ||X −WH||2
F
, on restreint
cette somme aux entrées connues de X : le problème 11.8 devient alors
2
arg min Xij − (WH)ij . (11.9)
p×m
W ∈R+ ,H∈Rm×n
+ i,jnon manquants
175
Chapitre 11 r Réduction de dimension
11.3.3 Auto-encodeurs
Nous avons vu à la section 7.2.5 qu’il est possible d’interpréter les réseaux de neu-
rones artificiels comme un outil pour apprendre une représentation des données (celle
issue de la dernière couche intermédiaire) qui se prête bien à un apprentissage super-
visé linéaire. Cette idée a conduit à la notion d’auto-encodeur, qui permet d’utiliser
les réseaux de neurones pour faire de la réduction de dimension non supervisée.
Définition 11.6 (Auto-encodeur)
On appelle auto-encodeur un réseau de neurones dont la couche de sortie est
identique à la couche d’entrée, en passant par une couche intermédiaire de taille
inférieure à celles-ci. La sortie de cette couche intermédiaire constitue alors une
nouvelle représentation plus compacte des données.
Bien qu’il existe des auto-encodeurs linéaires, on leur préfère généralement les
machines de Boltzmann restreintes, ou RBM pour Restricted Boltzmann Machines.
Elles ont été proposées par Paul Smolensky (1986).
Une machine de Boltzmann restreinte contient deux couches de neurones, comme
illustré sur la figure 11.5. La première couche contient p neurones, une par variable
xj représentant les données ; la deuxième en contient m, où m < p. Le vecteur
z = (z1 , z2 , . . . , zm ) en sortie de cette couche constitue une représentation réduite
de x. Nous supposerons ces variables binaires, à valeur dans {0, 1} : elles peuvent
correspondre à la couleur d’un pixel sur une image en noir et blanc.
Cette architecture est dite restreinte car il n’y a pas de connexions entre neu-
rones d’une même couche, contrairement aux machines de Boltzmann proposées
précédemment et utilisées dans le cadre de la physique statistique. Par contre, les
connexions entre les deux couches vont dans les deux sens : de la couche d’entrée
vers la couche intermédiaire, et aussi de la couche intermédiaire vers la couche d’en-
trée. Les poids de connexion seront choisis de sorte à minimiser la différence entre
l’entrée et la sortie, obtenue après un passage vers l’avant puis un retour vers l’arrière
dans le réseau.
176
11.3 Extraction de variables
Ainsi, nous pouvons apprendre les coefficients {aj }j=1,...,p , {bq }q=1,...,m , et
{wjq }j=1,...,p,q=1,...,m par maximum de vraisemblance.
Pour une observation x i donnée, l’opposé du log de la vraisemblance vaut :
e−E(u,v) − log e−E(x ,v) . (11.15)
i
− log P( x i ) = − log x i , v) = log
P(
v u,v v
© Dunod - Toute reproduction non autorisée est un délit.
177
Chapitre 11 r Réduction de dimension
Il est possible d’empiler les RBM pour obtenir une architecture profonde, appelée
deep belief network (ou DBN). Cette architecture permet d’effectuer une réduction
de dimension non supervisée, mais peut aussi être utilisée dans un cadre super-
visé. Il s’agit alors de connecter la dernière couche du DBN à une couche de sortie ;
178
11.3 Extraction de variables
on obtiendra alors un réseau de neurones supervisé. Les DBN, proposés par Geoff
Hinton et Ruslan Salakhutdinov, figurent parmi les premiers réseaux de neurones
profonds réalisés (Hinton et Salakhutdinov, 2006).
Positionnement multidimensionnel
Le positionnement multidimensionnel, ou multidimensional scaling (MDS)
(Cox et Cox, 1994), se base sur une matrice de dissimilarité D ∈ Rn×n entre
les observations : il peut s’agir d’une distance métrique, mais ce n’est pas nécessaire.
Le but de l’algorithme est alors de trouver une représentation des données qui
préserve cette dissimilarité :
n ((
n (( 2
(( i ((
X ∗ = arg min ((z − z l (( − Dil . (11.19)
Z∈Rn×m i=1 l=i+1 2
Il s’applique par exemple très bien à repositionner des villes sur une carte à partir
uniquement des distances entre ces villes.
Une des limitations de MDS est de ne chercher à conserver la distance entre les
observations que globalement. Une façon efficace de construire la matrice de dissi-
milarité de MDS de sorte à conserver la structure locale des données est l’algorithme
IsoMap (Tenenbaum et al., 2000). Il s’agit de construire un graphe de voisinage entre
les observations en reliant chacune d’entre elles à ses k plus proches observations
voisines. Ces arêtes peuvent être pondérée par la distance entre les observations
qu’elles relient. Une dissimilarité entre observations peut ensuite être calculée sur
ce graphe de voisinage, par exemple via la longueur du plus court chemin entre deux
points.
179
Chapitre 11 r Réduction de dimension
t-SNE
Enfin, l’algorithme t-SNE, pour t-Student Neighborhood Embedding, proposé
en 2008 par Laurens van der Maaten and Geoff Hinton, propose d’appro-
cher la distribution des distances entre observations par une loi de Student
(van der Maaten et Hinton, 2008). Pour chaque observation x i , on définit Pi comme
la loi de probabilité définie par
! (( (( "
1 ((x − x i ((2
x) = √
Pi ( exp − 2
. (11.20)
2π σ 2 2σ 2
Points clefs
r Réduire la dimension des données avant d’utiliser un algorithme d’apprentissage
supervisé permet d’améliorer ses besoins en temps et en espace, mais aussi ses
performances.
r On distingue la sélection de variables, qui consiste à éliminer des variables
redondantes ou peu informatives, de l’extraction de variable, qui consiste à
générer une nouvelle représentation des données.
r Projeter les données sur un espace de dimension 2 grâce à, par exemple, une
ACP ou t-SNE, permet de les visualiser.
r De nombreuses méthodes permettent de réduire la dimension des variables.
180
11.3 Extraction de variables
Bibliographie
Cox, T. F. et Cox, M. A. A. (1994). Multidimensional Scaling. Chapman & Hall,
London.
Guyon, I. et Elisseeff, A. (2003). An introduction to variable and feature
selection. Journal of Machine Learning Research, 3:1157-1182.
Hinton, G. E. (2002). Training product of experts by minimizing contrastive
divergence. Neural Computation, 14:1771-1800.
Hinton, G. E. et Salakhutdinov, R. R. (2006). Reducing the dimensionality of
data with neural networks. Science, 313:504-507.
Kozachenko, L. F. et Leonenko, N. N. (1987). A statistical estimate for the
entropy of a random vector. Problemy Peredachi Informatsii, 23:9-16.
Lee, D. D. et Seung, H. S. (1999). Learning the parts of objects by non-negative
matrix factorization. Nature, 401(6755):788-791.
Miller, A. J. (1990). Subset Selection in Regression. Chapman & Hall, London.
Shlens, J. (2014). A Tutorial on Principal Component Analysis. arXiv [cs, stat].
arXiv:1404.1100.
Smolensky, P. (1986). Information processing in dynamical systems : founda-
tions of harmony theory. In Parallel Distributed Processing : Explorations in
the Microstructure of Cognition, volume 1 : Foundations, chapter 6, pages
194-281. MIT Press, Cambridge, MA.
© Dunod - Toute reproduction non autorisée est un délit.
181
Chapitre 11 r Réduction de dimension
Exercices
11.1 Alicia a des données en deux dimensions qui sont alignées sur la diagonale
d’équation x2 = x1 .
1. Quelles sont les coordonnées des deux composantes principales obtenues par
ACP ?
2. Quelles sont les coordonnées des deux composantes principales obtenues par
analyse factorielle ?
182
Exercices
1. Soit (λ, v) une paire (valeur propre, vecteur propre) de . Montrer que v peut
s’écrire comme une combinaison linéaire des φ( x i ).
2. Montrer que nλKα = K 2 α.
3. Montrer que les composantes principales des images des observations dans H
peuvent être obtenues par décomposition spectrale de K.
4. Montrer que la projection de l’image φ(x ) d’une observation x ∈ X sur une
composante principale des images des observations dans H peut se calculer sans
utiliser la fonction φ ni l’espace H.
11.8 Soient deux boules A et B dans Rp , centrées sur l’origine. A est de rayon 1
et B de rayon 1 − ε.
1. Quelle est la proportion relative du volume de A qui n’est pas dans B ?
2. Quel est le rapport avec le fléau de la dimension ?
Solutions
11.1
1. La première composante
√ √principale est le vecteur directeur de la diagonale, de
norme 1, soit donc ( 22 , 22 ). La deuxième lui est orthogonale, de norme 1, et est
√ √
donc ( 2
2
, − 2
2 ).
2. La première composante principale est celle obtenue par ACP. Comme celle-ci
explique toute la variance, et que la deuxième composante n’est pas contrainte
à être orthogonale à la première, la deuxième composante aura les coordonnées
(0, 0).
11.2 En général, non ! La réduction de dimension peut être vue comme une
compression avec pertes.
© Dunod - Toute reproduction non autorisée est un délit.
11.3
1. Une seule.
2. Environ 90.
11.4 Oui : les données qui étaient représentées en 6 dimensions le sont mainte-
nant en 3.
183
Chapitre 11 r Réduction de dimension
11.6
1. 10 : les 5 variables informatives + leurs 5 copies.
2. 5.
11.7
n
1. Par définition, λv = v donc nλv = i=1 φ( x i ) v. En posant αi =
x i )φ(
x i ) v, on a la décomposition attendue.
nλ φ(
1
2. En remplaçant v par ni=1 αi φ( x i ) dans λv = v, on obtient
n
1
n n
λ αi φ(
x )=
i
φ(xi )φ(xi ) αk (
x k ).
n
i=1 i=1 k=1
Par définition
de K, lKα est un vecteur de dimension n, de l-ième coordonnée
x ) φ(
(Kα)l = ni=1 αi φ( x l ) , on obtient
x i ). En multipliant à gauche par φ(
n
1
n n
1
l
λ αi φ(
x ) φ(
x )= i
x l ) φ(xi )φ(xi ) φ(
φ( x k )αk = (KKα)l
n n
i=1 i=1 k=1
d’où le résultat.
3. La décomposition spectrale de K est donc équivalente à la décomposition spectrale
de , et nous donne les composantes principales dans H.
4. La projection de φ( x ) sur une composante principale,
nc’est-à-dire un vec-
teur propre
v de , se calcule comme φ(
x )
v = α φ(
x ) φ(
x i) =
n i=1 i
i=1 αi k(
x, x i ).
11.8
1.
2π p/2 2(1−ε)p π p/2
p(p/2) − p(p/2)
ρ= = 1 − (1 − ε)p
2π p/2
p(p/2)
2. Cette proportion tend vers 0 quand p tend vers l’infini. En grande dimension, les
points à l’intérieur d’une boule sont concentrés à sa frontière, et il n’y a pour ainsi
dire aucun point plus proche de l’origine. Tous les points sont donc très éloignés
et il est difficile d’utiliser la notion de proximité pour faire de l’inférence.
184
CLUSTERING
12
OBJECTIFS INTRODUCTION
185
Chapitre 12 r Clustering
Le médoïde est le point du cluster le plus proche du centroïde (il peut ne pas être
unique, auquel cas il sera choisi arbitrairement). Il sert de représentant du cluster :
C = arg min d(x,
m μ C ).
x∈C
Que des observations proches appartiennent au même cluster peut se traduire par
la notion d’homogénéité, illustrée sur la figure 12.1.
186
12.2 Évaluer la qualité d’un algorithme de clustering
Pour quantifier à quel point les clusters sont distants les uns des autres, nous
pouvons utiliser le critère de séparabilité, illustré sur la figure 12.2.
© Dunod - Toute reproduction non autorisée est un délit.
Figure 12.2 – Les trois clusters représentés sur le panneau de gauche sont bien
séparés, contrairement à ceux représentés sur le panneau de droite qui sont proches
les uns des autres.
187
Chapitre 12 r Clustering
Plutôt que de considérer les deux critères de séparabilité (que l’on souhaite éle-
vée) et d’homogénéité (que l’on souhaite faible) séparément, il est possible de les
comparer l’un à l’autre grâce à l’indice de Davies-Bouldin.
Définition 12.4 (Indice de Davies-Bouldin)
On appelle indice de Davies-Bouldin du cluster Ck la valeur
T + Tl
Dk = max k .
l =k Skl
L’indice de Davies-Bouldin global d’un clustering de D se calcule comme la moyenne
des indices de Davies-Bouldin des clusters :
K
1
D= Dk .
C
k=1
188
12.2 Évaluer la qualité d’un algorithme de clustering
différents :
n
n
2
RI = δ(k(x i ) = k(x l ))δ(y i = y l ) + δ(k(x i ) = k(x l ))δ(y i = y l ).
n(n − 1)
i=1 l=i+1
189
Chapitre 12 r Clustering
En effet, le terme sous la somme est la probabilité que, lorsqu’on tire |Ck | éléments
parmi n, s d’entre eux appartiennent à G.
Muni de ces différentes façons d’évaluer un algorithme de partitionnement de
données, nous pouvons maintenant découvrir ces algorithmes eux-mêmes. Ces al-
gorithmes cherchent à optimiser les critères d’homogénéité et de séparabilité que
nous venons de définir. Comme il n’est pas possible de le faire de manière exacte,
il s’agit de le faire de manière approchée. Nous nous concentrerons dans ce chapitre
sur les trois principales familles d’algorithmes de clustering : clustering hiérarchique,
clustering par centroïdes, et clustering par densité.
12.3.1 Dendrogramme
Le résultat d’un clustering hiérarchique peut se visualiser sous la forme d’un den-
drogramme. Il s’agit d’un arbre dont les n feuilles correspondent chacune à une
observation. Chaque nœud de l’arbre correspond à un cluster :
• la racine est un cluster contenant toutes les observations ;
• chaque feuille est un cluster contenant une observation ;
• les clusters ayant le même parent sont agglomérés en un seul cluster au niveau
au-dessus ;
• un cluster est subdivisé en ses enfants au niveau au-dessous.
Ce sont donc les nœuds intermédiaires qui nous intéresseront le plus.
Enfin, la longueur d’une branche de l’arbre est proportionnelle à la distance entre
les deux clusters qu’elle connecte.
La figure 12.3 représente un exemple de dendrogramme. Dans le cas où n est trop
grand pour représenter l’intégralité de l’arbre, il est classique de le couper et de n’en
représenter que la partie de la racine à un niveau que l’on choisit.
Cette facilité à représenter visuellement le résultat d’un algorithme de clustering
hiérarchique fait qu’il est très utilisé dans des domaines comme la bio-informatique.
190
12.3 Clustering hiérarchique
191
Chapitre 12 r Clustering
On peut aussi choisir d’agglomérer deux clusters si tous leurs éléments sont
proches. On utilise alors le lien complet, qui est la distance maximale entre un élément
du premier cluster et un élément du deuxième.
1 1
dmoyen (Ck , Cl ) = , v ).
d(u
|Ck | |Cl |
∈Ck v ∈Cl
u
Cette distance est aussi parfois appelée UPGMA pour Unweighted Paired Group
Method with Arithmetic mean.
Une alternative au lien moyen est le lien centroïdal, qui considère la distance entre
les centroïdes des clusters.
Cette distance est aussi parfois appelée UPGMC pour Unweighted Paired Group
Method with Centroid.
192
12.4 Méthode des k-moyennes
Tk = |C1k | x∈Ck ||
x−μ k ||2 . Le clustering de Ward utilise une formulation similaire :
il s’agit d’agglomérer deux clusters de sorte à minimiser la variance intra-cluster du
résultat.
Définition 12.11 (Inertie)
On appelle variance intra-cluster, ou inertie du cluster C la valeur
1 (((( ((2
Varin (C) = ((2 .
x − μ
|C|
x∈C
L’inertie globale d’un clustering de D est alors donnée par la somme des inerties
des clusters :
K
1 (((( ((2
V= k ((2 .
x − μ
|Ck |
k=1 k
x∈C
à deux entre toutes les paires d’observations du jeu de données, pour une complexité
en O(pn2 ). Une alternative est de stocker ces distances en mémoire pour pouvoir les
réutiliser, ce qui a une complexité quadratique en le nombre d’observations.
Le clustering hiérarchique est donc plus adapté aux jeux de données contenant peu
d’échantillons.
193
Chapitre 12 r Clustering
K
1
arg min || k ||22 .
x−μ (12.2)
C1 ,C2 ,...,CK |Ck |
k=1 x∈Ck
4. Répéter les opérations 2-3 jusqu’à convergence, c’est-à-dire jusqu’à ce que les
affectations ne changent plus.
194
12.4 Méthode des k-moyennes
Données aberrantes
L’algorithme du k-means est sensible aux données aberrantes : elles vont en effet
tirer un cluster à elle. Si une observation x i est très éloignée des autres observations,
alors elle se retrouvera dans son propre cluster, tandis que le reste des données sera
partitionné en K − 1 clusters.
Cette propriété est néanmoins intéressante, car elle permet d’utiliser l’algorithme
des k-moyennes justement pour détecter les observations aberrantes : ce sont celles
qui sont seules dans leur cluster.
12.4.3 Variantes
k-means++
L’algorithme du k-means est stochastique : on peut obtenir des résultats différents
selon l’initialisation, et certains de ces résultats peuvent avoir une inertie bien plus
grande que la solution optimale.
Pour éviter ce problème, l’algorithme k-means++ commence par initialiser les
centroïdes de manière à les disperser au maximum parmi les données. Plus précisé-
ment, la procédure consiste à
1. Choisir un premier centroïde u 1 aléatoirement parmi les observations D ;
2. Pour k = 2, . . . , K :
Choisir le k-ième centroïde u k parmi D\u k−1 , en suivant une loi proportionnelle
© Dunod - Toute reproduction non autorisée est un délit.
195
Chapitre 12 r Clustering
Démonstration
Soit κ : X × X → R un noyau. Il existe un espace de Hilbert H et une application
φ : X → H telle que, pour tout x, x ∈ X × X, κ(x, x ) = x,
x H .
Pour appliquer l’algorithme de Lloyd aux images {φ(x 1 ), φ(x 2 ), . . . , φ(x n )} des élé-
ments de D dans H, nous avons besoin de calculer, à chaque itération, la distance
de φ(x i ) à chacun des K centroïdes h ,h
1 2 , . . . , hK .
La position d’un centroïde h se calcule comme la moyenne des images des
k
observations appartenant à Ck :
= 1
h φ(x i ).
k |Ck |
x i ∈Ck
On peut ainsi réécrire l’étape (2) de l’algorithme de Lloyd sans faire appel à
l’application φ, et sans avoir besoin de recalculer explicitement les centroïdes à
l’étape (3).
196
12.5 Clustering par densité
(a) Il nous semble naturel de par- (b) Partitionnement en 3 clusters (c) Partitionnement en 3 clusters
titionner ces données en 3 cercles par clustering agglomératif (lien par k-moyennes.
concentriques. moyen).
Pour formaliser cette idée, nous allons avoir besoin de quelques définitions.
Définition 12.13 (ε-voisinage)
Soient D = {x 1 , x 2 , . . . , x n } le jeu d’éléments de X à partitionner, d une distance sur
X, et ε > 0. On appelle ε-voisinage d’un élément x ∈ X l’ensemble des observations
de D dont la distance à x est inférieure à ε :
= {u
Nε (x) ∈ D : d(x,
u ) < ε}.
197
Chapitre 12 r Clustering
Sinon :
• créer un cluster C = {x},
ε, nmin ) ;
• augmenter ce cluster par la procédure grow_cluster(C, Nε (x),
3. Ajouter C à la liste des clusters : K ← K ∪ C ;
4. Marquer tous les éléments de C comme visités : V ← V ∪ C.
La procédure grow_cluster(C, N, ε, nmin ) est définie comme suit :
∈N:
Pour tout u
1. Si u ∈/ V :
• créer N = Nε (u
),
• si |N | ≥ nmin : actualiser N de sorte à prendre les éléments de N en
considération : N ← N ∪ N ,
198
12.5 Clustering par densité
Un des avantages de DBSCAN est sa robustesse aux données aberrantes, qui sont
identifiées lors de la formation des clusters.
Le fléau de la dimension (voir section 11.1.3) rend DBSCAN difficile à appli-
quer en très grande dimension : les ε-voisinages auront tendance à ne contenir que
leur centre. De plus, la densité étant définie par les paramètres ε et nmin , DBSCAN
ne pourra pas trouver de clusters de densité différente. Cependant, DBSCAN ne re-
quiert pas de prédéfinir le nombre de clusters, et est efficace en temps de calcul. Son
application aux données de la figure 12.4a est illustrée sur la figure 12.6.
Points clefs
r Le clustering, ou partitionnement de données, cherche à identifier des classes
sans utiliser d’étiquettes.
r En l’absence d’étiquette, la qualité d’une partition peut s’évaluer sur des critères
de séparabilité et d’homogénéité.
r Le clustering hiérarchique partitionne les données de manière itérative. Son
résultat peut être visualisé sur un dendrogramme.
r Le clustering par la méthode des k-moyennes s’effectue grâce à l’algorithme
de Lloyd ou une de ses variantes. Il permet de trouver efficacement K clusters
convexes.
199
Chapitre 12 r Clustering
Bibliographie
Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). A density-based algorithm
for discovering clusters in large spatial databases with noise. In Proceedings
of the Second International Conference on Knowledge Discovery and Data
Mining, pages 226-231, Portland (OR). AAAI Press.
Jain, A. K. and Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice
Hall, New York.
Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on
Information Theory, 28(2):129-137.
Steinhaus, H. (1957). Sur la division des corps matériels en parties. Bulletin de
l’Académie polonaise des sciences, 4(12):801-804.
Xu, R. and Wunsch II, D. (2005). Survey of clustering algorithms. IEEE
Transactions on Neural Networks, 16:645-678.
Exercices
12.2 Blaise veut partitionner les données en deux dimensions représentées sur la
figure ci-dessous. Il utilise les deux carrés comme centroïdes initiaux.
200
Exercices
12.3 Quels soint les points communs et les différences entre la méthode des k
plus proches voisins et celle des k moyennes ?
12.4 Courtney applique DBSCAN à ses données, et remarque qu’elle obtient un
clustering très fragmenté, formé de beaucoup de petits clusters assez proches les uns
des autres. Sur quel(s) paramètre(s) peut-elle jouer et comment pour obtenir moins
de clusters ?
12.5 Darius a implémenté sa propre version de l’algorithme de Lloyd. Il re-
marque qu’il arrive qu’en réassignant les observations à leurs clusters, l’algorithme
retrouve une partition des observations qu’il avait déjà utilisée à une étape précédente.
Est-ce normal ?
12.6 Elsie veut appliquer un algorithme de clustering hiérarchique à des données
représentées par des variables binaires. Quelle distance utiliser ?
© Dunod - Toute reproduction non autorisée est un délit.
Solutions
12.1
2. Avec des variables binaires, il est impossible que les observations soient très
éloignées les unes des autres (ce qui est nécessaire pour ne pas agglomérer
deux clusters contenant plus d’une seule observation). La profondeur sera donc
inférieure à n.
201
Chapitre 12 r Clustering
12.2
1.
2. Non.
12.3 Elles forment toutes les deux une partition convexe de l’espace des observa-
tions, et on un unique hyper-paramètre k. Il s’agit sinon de méthodes bien différentes
(l’une supervisée, l’autre non ; k n’a pas la même signification pour les deux ; etc.)
202
APPENDICE : NOTIONS
D’OPTIMISATION
A
CONVEXE
Dans cet ouvrage, nous formulons de nombreux modèles de machine
INTRODUCTION
A.1 CONVEXITÉ
Commençons par définir la notion de convexité, pour un ensemble puis pour une
fonction.
+ (1 − t)v ∈ S.
tu
203
Appendice : Notions d’optimisation convexe
Figure A.1 – Les trois ensembles de R2 présentés sur la rangée du haut sont
convexes. Les trois ensembles sur la rangée du bas ne sont pas convexes, et un
exemple de segment reliant deux points de l’ensemble mais n’étant pas entièrement
inclus dans cet ensemble est présenté pour chacun d’entre eux.
Exemple
Les fonctions ci-dessous sont convexes
• f : R → R, u → u2a a∈N
• f : R∗+ → R, u → ua a ∈]0,
/ 1[
• f : R → R, u → eau a∈R
• f : R∗+ → R, u → − log(au) a∈R
→
• f : Rn → R, u a u +b ∈ Rn , b ∈ R
a
n
• f : R → R, u→ 1 u
Qu +a
u +b ∈ Rn , b ∈ R, Q
a 0
2
n 1
→ ||u
• f : Rn → R, u ||p = i=1 |ui |
p p .
204
A.2 Problèmes d’optimisation convexe
).
min f (u
∈U
u
205
Appendice : Notions d’optimisation convexe
∗ est un point de maximum global de f sur U s’il est un point de minimum global
u
de −f sur U.
∗ est un point de maximum local de f sur U s’il est un point de minimum local
u
de −f sur U.
206
A.3 Optimisation convexe sans contrainte
Théorème A.1
∗ ∈ U un point de minimum local de f sur U. Alors
Soit U ⊆ Rn , f : U → R, et u
∗ est un point de minimum global ;
• si f est convexe, alors u
• si f est strictement convexe, alors u ∗ est l’unique point de minimum global.
Démonstration
∗ étant un point de minimum local, il existe ε > 0 tel que
u
(( ((
vérifiant ((u
pour tout u ∗ ((2 ≤ ε, f (u
−u ∗ ) ≤ f (u
). (A.1)
∗ :
Supposons qu’il existe un point de minimum global v de f sur U différent de u
∗ ),
f (v ) < f (u (A.2)
et
(( ((
∗ ((2 > ε
((v − u (A.3)
Soit u = (1 − λ)u ∗ + λv , avec λ = 1 ε . D’après l’équation A.3, 0 ≤ λ < 1. Par
2 ||v −u ∗ ||
convexité de U, u ∈ U.
(( (( (( (( (( ((
((u −u ∗ ((2 = (((1 − λ)u ∗ + λv ((2 = λ ((v − u ∗ ((2 = 2ε < ε, et d’après l’équation A.1,
f (u ) ≥ f (u ¯ ). Mais par convexité de f , f (u ) ≤ (1 − λ)f (u ∗ ) + λf (v ) = f (u
∗ ) + λ(f (v ) −
∗ )) < f (u
f (u ), cette dernière inégalité étant due à l’équation A.2.
On obtient donc une contradiction, et il est impossible que le minimum global v
soit différent du minimum local u ∗.
Nous allons maintenant voir comment résoudre un problème d’optimisation
convexe.
bilité souvent vérifiées pour les problèmes posés dans le cadre de l’apprentissage
statistique.
207
Appendice : Notions d’optimisation convexe
, v ∈ U,
• quels que soient u
f (v ) ≥ f (u ) (v − u
) + ∇f (u ). (A.4)
Démonstration
, v ∈ U. Supposons f convexe. Alors
Soient t ∈ [0, 1] et u
1
lim + t(v − u
f (u )) − f (u ) (v − u
) = ∇f (u ). (A.5)
t→0+ t
Par convexité de f , on peut écrire
+ t(v − u
f (u )) = f ((1 − t)u
+ t v ) ≤ (1 − t)f (u
) + tf (v ), (A.6)
et donc
1
+ t(v − u
f (u )) − f (u
) ≤ f (v ) − f (u
). (A.7)
t
En passant à la limite dans l’équation A.5 on obtient l’inégalité A.4.
Réciproquement, étant donnés u , v ∈ U et t ∈]0, 1[, posons w = tu
+ (1 − t)v . Par
convexité de U, w ∈ U. En supposant l’inégalité A.4,
) ≥ f (w)
f (u (u
+ ∇f (w) − w)
f (v ) ≥ f (w) (v − w).
+ ∇f (w)
En additionnant la première inégalité multipliée par t à la deuxième multipliée par
(1 − t), on obtient
) + (1 − t)f (v ) ≤ f (w)
tf (u (w
+ ∇f (w) − w)
(A.8)
et donc la convexité de f .
208
A.3 Optimisation convexe sans contrainte
Démonstration
Soient u ∈ U et v ∈ Rn . Posons I = {t ∈ R|u + t v ∈ U} et définissons φ : I → R, t →
+ t v ). Alors I est un intervalle et la fonction φ est convexe.
f (u
En effet, supposons que I contient au moins deux points distincts t1 et t2 . (Dans le
cas contraire, I est soit un singleton, soit l’intervalle vide. C’est donc un intervalle,
et de plus, la convexité de φ est triviale.) Soit s ∈]0, 1[ et w =u + st1 + (1 − s)t2 v .
Alors w = su 2 avec u
1 + (1 − s)u + t1 v et u
1 = u 2 = u + t2 v . Comme t1 = t2 , u
1 = u2
et par convexité de U, w ∈ U donc st1 + (1 − s)t2 ∈ I. Ce raisonnement étant vrai
pour tout s ∈]0, 1[, I est donc un intervalle. De plus, par convexité de f ,
© Dunod - Toute reproduction non autorisée est un délit.
209
Appendice : Notions d’optimisation convexe
I = {t ∈ R|u + t v ∈ U}. Alors, par l’équation A.9, φ est positive sur I et donc φ est
convexe sur I. Enfin, I contient les points t1 = 1 et t2 = 0. Alors, pour tout s ∈]0, 1[,
s = s t1 + (1 − s)t2 et
1 + (1 − s)u
f su 2 = φ(s) ≤ sφ(t1 ) + (1 − s)φ(t2 ) = sf (u
1 ) + (1 − s)f (u
2) (A.10)
et donc f est convexe.
210
A.3 Optimisation convexe sans contrainte
Plus la tolérance est faible, plus le point de minimum sera proche numériquement
du point de minimum global.
Le pas α est un paramètre très important de l’algorithme du gradient. Si α est très
faible, l’algorithme mettra très longtemps à converger. À l’inverse, si α est très
élevé, u oscillera autour du minimum global et l’algorithme peut même diverger.
On utilisera donc souvent un pas adaptatif qui varie à chaque itération et
commencera par prendre des valeurs relativement élevées avant de diminuer
progressivement lorsqu’on se rapproche de la solution.
(a) Quand f (u − αf (u)) > f (u) − f (u) α2 f (u), le (b) Quand f (u − αf (u)) ≤ f (u) − f (u) α2 f (u), le
pas α est trop élevé et u − αf (u) va se retrouver pas α est suffisamment petit pour que u − αf (u)
de l’autre côté du point de minimum. Il faut donc soit entre le point de minimum et u.
le réduire.
211
Appendice : Notions d’optimisation convexe
α ← βα
:u
• actualiser u ←u
− α∇f (u
).
−1
Ainsi, la méthode de Newton consiste à utiliser comme pas α = ∇ 2 f (u) . Cette
méthode suppose que la hessienne est inversible, ce qui est, entre autres, le cas pour
les fonctions fortement convexes. Dans le cas contraire, on pourra ajouter un peu de
bruit à la hessienne (en lui ajoutant εIn , avec ε > 0 petit) afin de la rendre inversible.
212
A.3 Optimisation convexe sans contrainte
−1
)
• calculer le pas : α = ∇ 2 f (u ,
:u
• actualiser u ←u
− α∇f (u
).
1. Initialisation :
• choisir aléatoirement x (0) ∈ Rn ,
− Ax (0) ;
• initialiser v0 = r0 = b
2. Pour t = 1, . . . , n :
© Dunod - Toute reproduction non autorisée est un délit.
a. Actualiser x :
r rt−1
x (t) = x (t−1) + t−1 vt−1 . (A.17)
vt−1 Avt−1
b. Actualiser le résiduel :
− Ax (t) .
rt = b (A.18)
c. Actualiser v :
r rt
vt = rt + t vt−1 . (A.19)
rt−1 rt−1
213
Appendice : Notions d’optimisation convexe
Théorème A.5
La méthode du gradient conjugué assure que vi Avj ∀i = j.
Démonstration
r
rt−1 t−1 r r
Posons αt = et βt = t t .
vt−1 Avt−1 rt−1 rt−1
Commençons par montrer que pour tout t = 1, . . . , n,
si rt rt−1 = 0, alors vt Avt−1 = 0. (A.20)
En remplaçant x (t) par sa valeur (équation A.17) dans l’équation A.18, on obtient
rt = rt−1 − αt Avt−1 . (A.21)
D’après l’équation A.19, on a donc vt Avt−1 = rt Avt−1 + βt vt−1
Avt−1 et donc
r rt
vt Avt−1 = rt Avt−1 + t v Avt−1 .
rt−1 rt−1 t−1
En remplaçant αt par sa valeur, on obtient vt Avt−1 = rt Avt−1 + α1t rt rt . D’après
l’équation A.21, Avt−1 = α1t (rt−1 − rt ), et donc
1 1 1
vt Avt−1 = r (r − rt ) + rt rt = r r =0
αt t t−1 αt αt t t−1
Ar
d’où le résultat A.20. Montrons maintenant par récurrence que rt−1 t = 0 et
vt−1 Avt = 0 pour tout t ≥ 1.
et r r = 0. D’après l’équation A.20, on a donc bien
Pour t = 1, rt−1 = r0 = 0 1 0
v1 Av0 = 0.
Av
Pour t > 1, supposons vt−2 t−1 = 0. D’après l’équation A.21,
Comme A 0, A = A et donc
! Ar
"
vt−1 t−1
rt rt−1 = rt−1
r t−1 1− . (A.22)
vt−1 Avt−1
214
A.3 Optimisation convexe sans contrainte
formantes, est la méthode BFGS, ainsi nommée d’après Charles George Broyden,
Roger Fletcher, Donald Goldfarb et David Shanno qui l’ont proposée tous les quatre
indépendamment en 1970.
Dans cette méthode, l’approximation itérative de l’inverse de la hessienne est
donnée par
dt δt W (t−1) + W (t−1) δt dt δt , W (t−1) δt dt dt
W =W
(t) (t−1)
− + 1+ (A.23)
δt , dt δt , dt δt , dt
où dt = u (t) − u (t−1) et δt = ∇f (u (t) ) − ∇f (u (t−1) ).
Il en existe une version moins gourmande en mémoire, appelée L-BFGS pour
Limited-memory BFGS, qui évite d’avoir à stocker en mémoire l’intégralité de la
matrice W (t) .
215
Appendice : Notions d’optimisation convexe
n
f (u) = fi (u). (A.24)
i=1
n
∇f (u) = ∇fi (u). (A.25)
i=1
Exemple
C’est le cas par exemple lorsque l’on cherche à minimiser une somme de moindres
carrés (voir section 5.1.2) : cette somme s’écrit
n
2
=
f (β)
y i − φ(x i |β)
i=1
où φ est la fonction de prédiction.
Étant donnés un pas α > 0 et une tolérance ε > 0, on appelle algorithme du gradient
stochastique l’algorithme suivant :
216
A.4 Optimisation convexe sous contraintes
hj (u) = 0 ∀j = 1, . . . , r,
où les fonctions f , gi , hj sont supposées à valeurs réelles et de classe C1 .
De nombreuses méthodes permettent de résoudre ce type de problèmes. Nous
détaillerons dans ce qui suit la méthode des multiplicateurs de Lagrange.
A.4.1 Lagrangien
Pour résoudre (P), nous allons introduire son lagrangien.
Définition A.15 (Lagrangien)
Soit (P) un problème de minimisation sous contraintes de la forme A.27.
217
Appendice : Notions d’optimisation convexe
Démonstration
α1 , β1 ), (
Soient ( α2 , β2 ) et 0 ≤ λ ≤ 1.
Prenons α = λ α1 + (1 − λ) α2 et β = λβ1 + (1 − λ)β2 .
Alors
) + α g
= inf f (u
α , β)
Q(
+ β h,
∈D
u
= (g1 (u
), g2 (u
), . . . gm (u = (h (u
)) et h
où g 1 ), h2 (u
), . . . hr (u
)). Ainsi,
= inf f (u
α , β)
Q( ) + λα1 g + (1 − λ)α2 g + (1 − λ)β h
+ λβ1 h
∈D 2
u
= inf λ f (u ) + α g + (1 − λ) f (u
+ β h ) + α g ,
+ β h
∈D 1 1 2 2
u
218
A.4 Optimisation convexe sous contraintes
Théorème A.7
Soit p∗ une solution de (P). Alors quels que soient α1 , α2 , . . . , αm ≥ 0 et
β1 , β2 , . . . , βr ∈ R,
Q(α, β) ≤ p∗ .
Démonstration
un point admissible. gi (u
Soit u ) ≤ 0 pour tout i = 1, . . . , m et hj (u
) = 0 pour tout
j = 1, . . . , r.
r
= f (u
, α , β) ) + n
Ainsi, L(u i=1 αi gi (u) + j=1 βj hj (u) ≤ f (u) et donc, pour tout point
admissible, L(u
, α , β) ≤ f (u
). On en déduit que
219
Appendice : Notions d’optimisation convexe
La condition de Slater est une condition suffisante (mais non nécessaire) pour
garantir la dualité forte, que l’on doit à Morton L. Slater (1950).
Théorème A.9 (Condition de Slater)
Soit (P) un problème de minimisation sous contraintes de la forme A.27. Si (P) est
convexe, c’est-à-dire f , g1 , g2 , . . . , gm sont convexes et h1 , h2 , . . . , hr sont convexes,
et qu’il existe au moins un point admissible pour lesquelles les contraintes
d’inégalités gi non affines soient vérifiés strictement, alors la dualité forte est
garantie.
220
A.4 Optimisation convexe sous contraintes
Démonstration
Soit un triplet (u ∗ , α ∗ , β ∗ ) qui vérifie les conditions de KKT. La condition d’admissi-
bilité primale implique que u ∗ est admissible.
La fonction u → L(u , α , β ∗ ) est convexe en u
∗ . En effet, L(u , α ∗ , β ∗ ) = f (u ) +
n ∗ r ∗ ∗ sont po-
α
i=1 i g i (
u ) + j=1 j β h j (
u ), les fonctions f et g i sont convexes, les αi
sitifs, et les hj sont affines. La condition de stationnarité implique donc que u ∗
minimise L(u , α ∗ , β ∗ ).
Par définition de la fonction duale de Lagrange, Q( α ∗ , β ∗ ) = L(u
∗ , α ∗ , β ∗ ) = f (u
∗ ). En
n ∗
effet, la condition de complémentarité des contraintes implique i=1 αi gi (u ∗ ) = 0,
r ∗ ∗
et celle d’admissibilité primale implique j=1 βj hj (u ) = 0.
Soient p∗ la solution de (P) et d ∗ celle de (Q). Par définition de d ∗ , f (u ∗ ) = Q(
α ∗ , β ∗ ) ≤
∗ ∗ ∗
d , et par dualité faible, d ≤ p . Ainsi, f (u ∗ ∗
) ≤ p et donc f (u ∗
)=p :u ∗ ∗ est un
point de minimisation de (P), et toutes les inégalités précédentes sont donc des
égalités et, en particulier, Q(α ∗ , β ∗ ) = d ∗ et (
α ∗ , β ∗ ) est un point de maximisation
de (Q).
221
Appendice : Notions d’optimisation convexe
domaine
maine des contraintes
ma contrain
in lignes de niveau de la
fonction objectif
222
A.4 Optimisation convexe sous contraintes
Bibliographie
Bertsekas, D. P., Nedi´, A., et Ozdaglar, A. E. (2003). Convex Analysis and
Optimization. Athena Scientific, Belmont, MA.
Bonnans, J., Gilbert, J., Lemaréchal, C., et Sagastizábal, C. (1997). Optimi-
sation numérique: aspects théoriques et pratiques. Sprinver-Verlag, Berlin
Heidelberg.
Bottou, L. (2012). Stochastic gradient descent tricks. [Link]
org/publications/pdf/[Link].
Boyd, S. et Vandenberghe, L. (2004). Convex Optimization. Cambridge
University Press. [Link]
Hestenes, M. et Stiefel, E. (1952). Methods of conjugate gradients for solving
linear systems. Journal of Research of the National Bureau of Standards,
19(6).
Kuhn, H. W. et Tucker, A. W. (1951). Nonlinear programming. In Neyman,
J., editor, Proceedings of the Second Berkeley Symposium on Mathematical
© Dunod - Toute reproduction non autorisée est un délit.
223
INDEX
A B concave, 205
condition de Slater, 220
accuracy, 39 backtracking line search, 212 conditionnement, 100
AdaBoost, 133 bagging, 131 convexité, 203
algorithme à directions de BFGS, 215 corrélation, 45, 116, 167
descente, 210 BLUE, 74 couche cachée voir couche
algorithme de Lloyd, 194 boosting, 133 intermédiaire
algorithme des k plus proches boosting du gradient, 134 couche intermédiaire, 98
voisins, 111 bootstrap, 37, 131 courbe précision-rappel, 42
algorithme du gradient, 211 courbe ROC, 40
algorithme du plus proche C coût ε-insensible, 25
voisin, 109 coût 0/1, 21, 56
analyse en composantes caractéristique voir variable coût absolu, 25
principales, 169, 179 CART, 126 coût de Huber, 25
analyse factorielle, 174 centroïde, 186 coût logistique, 22
apprenant faible, 130, 131 chemin de régularisation, 84, coût quadratique, 22, 96
apprentissage hors-ligne, 95 87 critère du perceptron, 96
apprentissage incrémental, 95 classification binaire, 5, 14
apprentissage non classification multi-classe, 6, D
métrique, 125 14, 16, 24, 94, 125
apprentissage non classifieur bayésien naïf, 62 DBSCAN, 198
paramétrique, 112 clustering deep belief network, 178
apprentissage non supervisé, 7 voir partitionnement deep learning
apprentissage par clustering agglomératif, 191 voir apprentissage profond
renforcement, 9 clustering de Ward, 193 dendrogramme, 190
apprentissage paresseux, 113 clustering divisif, 191 descente de coordonnées, 217
apprentissage profond, 104, clustering hiérarchique, 190 descripteur voir variable
179 clustering par densité, 196 déséquilibre, 46
apprentissage semi-supervisé, coût quadratique, 24 diagramme de Voronoï, 110,
9 coefficient de détermination, 195
apprentissage supervisé, 45 discriminant, 16
4, 14 coefficient de régularisation, distance, 115, 180, 186, 191
approximation universelle, 99 82 distribution a posteriori, 51
arbre de décision, 125 coefficient de silhouette, 188 distribution a priori, 50
astuce du noyau, 151, 154, complexité d’un modèle, 30, divergence contrastive, 178
179, 195 64, 70, 81, 129 divergence de
attribut voir variable compromis biais-variance, 28, Kullback-Leibler, 23, 180
auto-encodeur, 176 62 dual, 219
225
Index
226
Index
227