Poly Apprauto FSur
Poly Apprauto FSur
Poly Apprauto FSur
Frédéric S UR
[email protected]
https://members.loria.fr/FSur/
2023-2024
1 Introduction 9
1.1 Qu’est-ce que l’apprentissage automatique ? . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Les données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Apprentissage non-supervisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Apprentissage supervisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Pour approfondir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Problèmes de partitionnement 39
3.1 Méthodes hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Partitionnement en K -moyennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Méthodes de partitionnement basées sur la densité . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Pour approfondir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Index 175
À l’attention des étudiants FICM 2A
(à lire attentivement avant la première séance)
Page Arche du cours Le calendrier, les supports de cours, les sujets de TP et leur correction,
ainsi que les passages à lire en prévision de chaque séance seront disponibles sur la page
Arche du cours. Une heure de lecture attentive est à prévoir avant chaque séance.
Évaluation Le cours cherchant à satisfaire des aspirations diverses, vous pouvez légitime-
ment vous demander sur quels éléments portera l’évaluation. Une note de TP (sur 4 points)
sera attribuée par les encadrants de TP, sur la base de votre travail en séance et des résultats
aux QCM en ligne au début de chaque séance. L’examen final (sur 16 points) aura pour ob-
jectif de vérifier la compréhension des grands principes de l’apprentissage, des principaux
algorithmes, et du traitement de données réelles. Vous trouverez sur Arche des sujets d’exa-
men des années passées.
Frédéric Sur
10 novembre 2023
(première version de ce document : janvier 2020)
Notations
Dans ce document, les vecteurs figurent en gras et les matrices en lettres capitales. On
identifiera souvent un vecteur et la matrice colonne le représentant.
Voici les principales notations utilisées :
— le produit scalaire euclidien de deux vecteurs x et y est noté x · y. Rappelons que si les
composantes de ces vecteurs sont x = (x 1 , x 2 , . . . x d ) et y = (y 1 , y 2 , . . . , y d ), alors x · y =
Pd i i
i =1 x y ;
— la norme euclidienne d’un vecteur x est notée ∥x∥2 . Elle vérifie ∥x∥22 = x · x et pour tous
vecteurs x et y et scalaire λ ∈ R, ∥x + λy∥22 = ∥x∥22 + ∥y∥22 + 2λx · y ;
— la transposée d’une matrice A est noté A T ;
— le déterminant d’une matrice carrée A est noté |A| ;
— l’inverse d’une matrice carrée inversible B est noté B −1 ;
— le cardinal d’un ensemble fini S est noté #S ;
— l’espérance d’une variable aléatoire X est notée E (X ) ;
— lorsqu’on cherche à optimiser une fonction f , on notera arg min x f (x) ou arg max x f (x)
une valeur de x où f (x) atteint son minimum ou maximum (« la » valeur dans le cas
d’un extremum unique).
Chapitre 1
Introduction
Exemple 1.2
Supposons que l’on dispose d’un certain nombre d’images représentant des chiens, et
d’autres représentant des chats. Comment classer automatiquement une nouvelle image
dans une des catégories « chien » ou « chat » ?
Exemple 1.3
Supposons que l’on dispose d’une base de données regroupant les caractéristiques de
logements dans une ville : superficie, quartier, étage, prix, année de construction, nombre
d’occupants, montant des frais de chauffage. Comment prédire la facture de chauffage à
partir des autres caractéristiques pour un logement qui n’appartiendrait pas à cette base ?
jeu de données étiquetées. Dans le premier cas, il « suffit » de collecter des données après pré-
traitement automatique minimal, alors que dans le second cas une intervention humaine
potentiellement coûteuse est souvent nécessaire pour définir les étiquettes. 1
Les données peuvent être vues comme des points dans un certain espace. Il est souvent
nécessaire de comparer ces points, et il est alors bien pratique que l’espace des données soit
muni d’une distance. Dans le cas de données décrites dans un espace vectoriel, les normes
usuelles ∥ · ∥1 ou ∥ · ∥2 (norme euclidienne) font souvent l’affaire. Rappelons que si x est un
vecteur de Rd , de composantes (x 1 , . . . , x d ), alors
v
d d
u
uX
|x i |
X
∥x∥1 = et ∥x∥2 = t |x i |2
i =1 i =1
1. Dans l’actualité récente des Facebook papers, “Internal Facebook documents show some staff expres-
sing skepticism and include evidence that the company’s moderation technology is less effective in emerging
markets. One reason for that is a shortage of human-labeled content needed to train machine learning al-
gorithms to flag similar content by themselves.” Wired, 25 octobre 2021. https://www.wired.com/story/
facebooks-global-reach-exceeds-linguistic-grasp/
F IGURE 1.1 – Apprentissage non-supervisé. Ici, les données non-étiquetées sont des points dans
un espace bidimensionnel de composantes (x 1 , x 2 ). On peut chercher une densité de probabilité
ayant permis de générer les observations représentées sur la figure. On peut aussi chercher à
identifier des groupes. Dans cet exemple, il semble naturel d’identifier trois groupes. Notons
qu’ils ne sont pas nécessairement isotropes (la « forme » d’un groupe n’est pas sphérique), n’ont
pas le même nombre d’éléments, et que l’appartenance de certains points à un groupe ou l’autre
est ambiguë.
visé. La question à résoudre est : étant donné un ensemble d’observations, quelle distribu-
tion de probabilité pourrait l’avoir généré ? Nous donnerons des éléments de réponse au cha-
pitre 5 où nous verrons des méthodes d’estimations non-paramétriques (histogrammes, fe-
nêtres de Parzen) et des méthodes paramétriques (en particulier le mélange de gaussiennes).
F IGURE 1.2 – Classification supervisée. Ici, l’espace des observations est le plan bidimensionnel.
Les observations ont des coordonnées (x 1 , x 2 ) et sont étiquetées par trois catégories (triangle,
rond, carré). L’objectif est de déterminer quelle catégorie associer à une nouvelle observation
non-étiquetée (représentée par une croix), à partir des observations étiquetées formant la base
d’apprentissage. Si, pour l’observation marquée « ? », la tâche peut sembler facile (la classe est
vraisemblablement « rond »), la classe de l’observation « ? ? » est plus discutable (« rond » ou
« carré » ?).
carrés, car elle est très proche de quelques carrés ? Autrement dit, la frontière de séparation
entre cercles et carrés doit-elle être peu complexe, quitte à mal classer certaines observations
de la base d’apprentissage, ou bien très complexe, de manière à séparer finement cercles et
carrés et ne pas faire d’erreur de prédiction sur la base d’apprentissage ? Ce dilemme est illus-
tré par la figure 1.3 ; sa discussion sera formalisée au chapitre 2.
Le cadre de la théorie statistique de la décision, abordée au chapitre 4, permet de définir
un classifieur théorique optimal, à savoir le classifieur de Bayes. Néanmoins, ce classifieur
reste théorique et ne peut pas être mis en œuvre en pratique sans hypothèses supplémen-
taires. Selon les hypothèses que l’on impose, le classifieur de Bayes s’incarne en différents
modèles de classification supervisée : la classification aux plus proches voisins, le classifieur
de la régression logistique (chapitre 6), les machines à vecteurs supports (chapitre 8), ou les
réseaux de neurones artificiels (chapitre 9).
Nous verrons aussi comment combiner plusieurs classifieurs dont les performances in-
dividuelles sont limitées à l’aide des méthodes ensemblistes au chapitre 7.
La classification biclasse (ou binaire) s’avère la plus courante : on cherche à classer les
observations dans deux classes. Lorsqu’on s’intéresse à K > 2 classes, on peut adapter les
classifieurs binaires de la manière suivante :
— Classification « un contre tous » (one versus all, one against all, ou one versus rest). Pour
chaque classe k ∈ {1, . . . , K }, on entraîne un classifieur biclasse f k permettant de discri-
F IGURE 1.3 – Frontières de séparation sur deux exemples. Quelle frontière de séparation est-elle
la plus adaptée : une frontière complexe, permettant de classer correctement toutes les observa-
tions de la base d’apprentissage (à gauche), ou une frontière plus régulière, quitte à mal classer
certaines de ces observations (à droite) ?
miner les observations de la classe k des observations des autres classes, de telle sorte
que f k prend des valeurs positives sur les observations de la classe k et négatives sur les
autres observations. Ensuite, on affecte une nouvelle observation x à arg max k f k (x) :
la classe dont le classifieur associé a la plus grande valeur. Naturellement, cela sup-
pose que les valeurs prises par les classifieurs soient comparables. D’autre part, tous
les classifieurs ne permettent pas de discriminer efficacement deux classes dont l’une
(celle regroupant les observations des classes différentes de la k-ème) est de cardinal
beaucoup plus grand que l’autre.
— Classification « un contre un » (one versus one). Dans cette approche, on entraîne un
classifieur pour chaque paire de classes. Il faut donc entraîner K (K − 1)/2 classifieurs.
Ensuite, une possibilité est d’affecter une nouvelle observation x à la classe majoritaire
parmi celles prédites par les K (K − 1)/2 classifieurs. Outre le temps de calcul potentiel-
lement grand pour entraîner un tel nombre de classifieurs, il faut gérer les cas d’égalité
dans la règle de classification.
Certains classifieurs sont naturellement « multiclasses », comme le classifieur des plus proches
voisins, le classifieur naïf de Bayes, ou les réseaux de neurones artificiels. Ils ne nécessitent
donc pas d’utiliser une stratégie « un contre tous » ou « un contre un ».
1.4.2 Régression
Lorsque les étiquettes y n prennent des valeurs scalaires ou vectorielles, on parle de pro-
blème de régression. L’exemple 3 est un problème de régression, car on cherche à prédire
le montant de la facture de chauffage qui est une grandeur scalaire. La figure 1.4 illustre un
problème de régression d’une variable scalaire. On rencontre un dilemme semblable à celui
évoqué dans le cas de la classification supervisée. Il est illustré par la figure 1.5.
F IGURE 1.4 – Régression. Les observations sont des scalaires x ; elles sont étiquetées par des
scalaires y, les couples (x, y) étant représentés dans le plan. L’objectif est de prédire la valeur de
l’étiquette y ∗ associée à un scalaire x ∗ , à partir de la base d’apprentissage (x n , y n ) représentée
par les ronds. La difficulté est que certaines observations semblent entachées de perturbations
aléatoires, certaines observations semblent même aberrantes.
F IGURE 1.5 – Deux exemples de courbes de régression sur la même base d’apprentissage. Vaut-il
mieux une courbe passant très près des observations d’apprentissage (à gauche), ou une courbe
plus régulière évitant les observations aberrantes et robuste à des perturbations aléatoires des
observations, voire robuste à des observations aberrantes (à droite) ?
La régression étant abordée dans d’autres cours à Mines Nancy, nous nous concentrerons
plutôt sur les problèmes de classification.
Revenons néanmoins brièvement, avec le vocabulaire de l’apprentissage, sur la régres-
sion linéaire multivariée que vous connaissez déjà. Dans ce cadre, les étiquettes y sont sca-
laires, et les fonctions f w sont affines sur l’espace Rd des observations. Ces fonctions s’écrivent
sous la forme
f w (x) = w 0 + w 1 · x
où w 0 ∈ R, w 1 ∈ Rd , et w 1 · x désigne le produit scalaire entre w 1 et x.
Les paramètres w 0 et w 1 sont obtenus par la méthode des moindres carrés, c’est-à-dire en
minimisant la somme des carrés des résidus du modèle sur la base d’apprentissage (x n , y n )1ÉnÉN :
N
|y n − w 0 − w 1 · x|2
X
n=1
De manière générale, on appelle « résidu » l’écart entre valeur prédite f w (x) et « vraie » va-
leur y.
Si x est un scalaire et x = (x, x 2 , . . . , x p ) est constitué de puissances de x (jusqu’au degré
p > 0), on voit que la régression polynomiale apparaît comme un cas particulier de la régres-
Pp
sion linéaire multivariée. En effet, dans ce cas, f w (x) = w 0 + i =1 w 1,i x i , où w 1 = (w 1,1 , . . . , w 1,p ).
Rappelons que les cours de statistique nous donnent l’expression de w 0 et w 1 en fonc-
tion de la base d’apprentissage. Notons W le vecteur-colonne des paramètres, Y le vecteur-
colonne des étiquettes, et X la matrice des observations, c’est-à-dire :
y1 1 x 11 x 12 . . . x 1d
y2 1 x 21 x 22 . . . x 2d
µ ¶
w0
W= , Y = . , X = .
.. .. .. ..
w1 .. .. . . . .
yN 1 xN 1 xN 2 . . . xN d
Proposition 1.1 Avec ces notations, on obtient l’estimation de W au sens des moindres carrés
par les équations dites normales :
W = (X T X )−1 X T Y
Démonstration
En effet, la quantité à minimiser en fonction des composantes de W est
N
|y n − w 0 − w 1 · x|2 = ||Y − X W ||22
X
n=1
et on développe :
||Y − X W ||22 = (Y − X W )T (Y − X W ) = Y T Y − 2W T X T Y + W T X T X W
Il s’agit d’une fonction quadratique convexe en W , car X T X est symétrique positive (voir
annexes B.1 et A.3). L’unique minimum est donc atteint en W où le gradient s’annule (voir
annexe B.1) ; on déduit en calculant les dérivées partielles par rapport à chaque composante :
−2X T Y + 2X T X W = 0
Les cours de statistique discutent l’effet des observations influentes, qui sont telles que
leur variation peut entraîner une forte variation des paramètres w 0 et w 1 , et des caractéris-
tiques colinéaires (ou fortement corrélées) qui peuvent entraîner la singularité (ou des pro-
blèmes de conditionnement) de la matrice X T X . Notons également que si le nombre d’ob-
servations N est inférieur à la dimension d , alors la matrice X T X n’est pas inversible. En effet,
si N É d , les colonnes de X sont nécessairement liées.
N d
|y n − w 0 − w 1 · x n |2 + λ |w j |2
X X
n=1 j =1
où λ est un paramètre positif ou nul. Il s’agit de la régression ridge, dont la régression linéaire
est un cas particulier (pour λ = 0).
Le premier terme est dit « d’attache aux données » car il reflète la capacité du modèle à
bien représenter les observations d’apprentissage. Le second terme est dit « de régularisa-
tion ».
On démontre que le problème précédent équivaut à minimiser la somme des carrés des
résidus, sous contrainte ∥w 1 ∥2 < C où C est un paramètre positif (il suffit de constater que le
Lagrangien du problème d’optimisation sous contrainte est l’expression dépendant du mul-
tiplicateur de Lagrange λ ci-dessus). La norme euclidienne de w 1 qui apparaît dans l’expres-
sion à minimiser contraint les paramètres à ne pas prendre de trop grandes valeurs et a pour
effet de limiter la dépendance du modèle aux données, d’où l’effet de régularisation.
W = (X T X + Λ)−1 X T Y
Démonstration
En effet, la fonction à minimiser est :
qui est convexe car λ Ê 0. En dérivant par rapport aux composantes de W , on obtient la rela-
tion : −2X T Y + 2X T X W + 2ΛW = 0, d’où l’expression annoncée. □
Habituellement, w 0 n’est pas intégré dans le terme de régularisation et n’est donc pas
contraint. La raison est que lorsque λ est grand, la régression ridge fournit des w j très petit.
Lorsque w 0 n’est pas contraint, ce paramètre apparaît alors comme minimisant |y n − w 0 |2
P
(les autres termes étant quasiment nuls), donc w 0 est la moyenne des y n (voir lemme 1
page 45). Le prédicteur de la régression ridge est alors constant, égal à cette moyenne. Cela
fait davantage sens que le prédicteur nul que l’on obtiendrait pour λ grand si on intégrait w 0
dans le terme de régularisation.
Par ailleurs, de manière à ne pas favoriser une caractéristique par rapport à une autre, il
vaut mieux que les composantes des observations x n varient dans la même gamme de va-
leurs, quitte à normaliser chaque caractéristique au préalable en retranchant sa moyenne et
en divisant par son écart-type.
1.4.2.3 Le Lasso
N d
|y n − w 0 − w 1 · x n |2 + λ
X X
|w j |
n=1 j =1
qui correspond à la régression Lasso (Least absolute shrinkage and selection operator), pro-
posée par Robert Tibshirani en 1996. La seule différence par rapport à la régression ridge est
l’utilisation de la norme ∥ · ∥1 à la place de la norme ∥ · ∥2 dans le terme de régularisation.
On démontre que le problème précédent est équivalent à minimiser la somme des carrés
des résidus, sous contrainte dj=1 |w j | < C où C est un paramètre positif.
P
L’intérêt d’utiliser la norme ∥ · ∥1 plutôt que la norme euclidienne est que la résolution
du problème de minimisation tendra à annuler certains des w j , comme illustré par la fi-
gure 1.6. Cela aura pour effet que les caractéristiques correspondantes n’apparaîtront plus
dans le modèle : le Lasso permet donc de faire de la sélection de caractéristiques (ou sélec-
tion de variables). On parle de modèle parcimonieux (sparse model).
Néanmoins, la fonction à minimiser dans le Lasso n’est pas différentiable en w = 0 et il n’y
a pas de solution analytique au Lasso : il faut utiliser des algorithmes d’optimisation dédiés
que l’on n’étudiera pas dans ce cours.
F IGURE 1.6 – Illustration de la minimisation de la somme des carrés des résidus, sous
contraintes ∥w ∥1 É C (Lasso, à gauche) ou ∥w ∥2 É C (régression ridge, à droite). L’ensemble
des w satisfaisant les contraintes forme un carré (cas du Lasso) ou un disque (cas de la régres-
sion ridge). La fonction objectif (somme des carrés des résidus) est quadratique et convexe en
les composantes de w ; ses lignes de niveau sont donc des ellipses centrées en w ∗ , la solution
de la régression linéaire classique. La solution w l∗ du Lasso ou w r∗ de la régression ridge est
obtenue respectivement comme point du carré ou du disque appartenant à la ligne de niveau
de valeur la plus faible. Il s’agit donc d’un point de la frontière du carré ou du disque lorsque
w ∗ ne satisfait pas les contraintes. Sur cet exemple bidimensionnel, on voit que la solution
du Lasso a une composante nulle qui n’interviendra donc pas dans le modèle linéaire. Il s’agit
d’une propriété générale de la régularisation par norme ∥ · ∥1 , quelle que soit la dimension des
observations : on a de bonne chance pour que l’optimum soit atteint en un point extremal de
l’hypercube unité, où une ou plusieurs composantes sont nulles. Le Lasso sélectionne automa-
tiquement les variables pertinentes dans le modèle et fournit donc des modèles parcimonieux.
Illustration adaptée de la figure 2 de l’article Regression Shrinkage and Selection via the Lasso,
R. Tibshirani, 1996.
Apprentissage par renforcement Les élèves intéressé·e·s par l’apprentissage par renforce-
ment pourront consulter :
R.S. Sutton, A.G. Barto, Reinforcement learning : an introduction, 2nd edition, MIT Press,
2018.
Régression ridge et Lasso Concernant les régressions ridge et Lasso, l’article original de Tib-
shirani peut être lu (au moins l’introduction) :
R. Tibshirani, Regression Shrinkage and Selection via the Lasso, Journal of the Royal Sta-
tistical Society Series B (Methodological), Vol. 58, No. 1, p. 267-288, 1996.
Supposons que l’on partitionne le cube unité de Rd en « petits » cubes de côté 1/n. Cela
nécessite n d petits cubes, ce nombre grandissant de manière exponentielle avec la dimen-
sion d , comme illustré par la figure 2.1. Imaginons que l’on cherche à estimer une distribution
CHAPITRE 2. DEUX LIMITES FONDAMENTALES DE L’APPRENTISSAGE 24
F IGURE 2.1 – Évolution du nombre de cubes de côté 1/n nécessaires pour remplir le cube unité
dans Rd (ici, n = 3).
de probabilité à partir d’un échantillon de 100 points : cela consiste à calculer la proportion
de points « tombant » dans chaque petit cube. Si d = 1 et n = 10, on peut envisager cette ap-
proche, car il n’y a que 10 intervalles (cubes en dimension 1) à considérer. Pour obtenir la
même finesse de discrétisation (1/10) en dimension 10, il faudra considérer 1010 soit dix mil-
liards de cubes. L’échantillon devrait être de taille proportionnelle car dans le cas contraire
de nombreux cubes seraient vides. On voit qu’estimer une distribution de probabilité en di-
mension grande est souvent inaccessible sans information additionnelle : cela nécessiterait
un échantillon de taille gigantesque.
On peut démontrer que le volume Vd de la boule de Rd de rayon 1 est donné par la for-
mule :
πd /2
Vd =
Γ(d /2 + 1)
où Γ est la « fonction Gamma », définie par
Z +∞
∀ x > 0, Γ(x) = t x−1 e −t dt
0
2πe d /2
µ ¶
1
Vd ∼d →+∞ p
πd d
Le volume de la boule unité tend donc très vite vers 0 quand la dimension augmente. Cette
propriété n’est pas nécessairement très intuitive, mais il y a « pire ». . .
10 0
10 -10
10 -20
10 -30
10 -40
10 -50
10 -60
10 -70
0 20 40 60 80 100
dimension
En effet, cette boule est obtenue de la boule unité par homothétie de rapport 1 − ε. Ainsi :
Vd − Vd1−ε
= 1 − (1 − ε)d
Vd
Autrement dit, la proportion de la boule unité concentrée dans une couche d’épaisseur ε > 0
aussi petite que l’on veut, située à la surface de la boule, tend vers 1 lorsque la dimension d
grandit. Ainsi, en grande dimension, tout le volume d’une boule est concentré à sa surface !
Une autre situation paradoxale, lié à ceux présentés ci-dessus, est qu’en grande dimen-
sion, toutes les observations sont à la même distance l’une de l’autre. Le graphique de la
figure 2.3 illustre l’évolution des distances euclidiennes en grande dimension. Un million de
points sont répartis selon la loi aléatoire uniforme dans le cube [−1, 1]d de Rd , et on calcule,
10 3
10 2
10 1
10 0
0 20 40 60 80 100
dimension
F IGURE 2.3 – Évolution du rapport entre la plus grande distance au centre et la plus petite
distance au centre parmi un million de points répartis uniformément dans le cube [−1, 1]d , en
fonction de la dimension d .
Le phénomène de Hughes indique qu’à base d’apprentissage de taille fixée, le taux d’er-
reur d’un classifieur diminue avec la dimension des observations (c’est-à-dire le nombre des
caractéristiques qui les composent), atteint un minimum, puis croît lorsque la dimension
augmente encore.
0.4 0.4
m=5 m=5
m=20 m=20
0.35 m=50 0.35 m=50
m=100 m=100
0.3 0.3
0.25 0.25
taux d'erreur
taux d'erreur
0.2 0.2
0.15 0.15
0.1 0.1
0.05 0.05
0 0
10 0 10 1 10 2 10 0 10 1 10 2
dimension dimension
5-ppv GNB
Nous allons illustrer le phénomène sur un exemple numérique 1 . On considère des ob-
servations de Rd réparties en deux classes : m observations distribuées aléatoirement selon
une loi gaussienne de variance identité centrée en µ1 (classe 1), et m observations distribuées
aléatoirement selon une loi gaussienne de variance identité centrée en µ2 = −µ1 (classe 2).
p
La n-ème composante de µ1 est 1/ n, de sorte que
d 1
||µ1 − µ2 ||22 = 4
X
n=1 n
Comme la série harmonique diverge, plus la dimension d est grande, plus la distance
entre les centres µ1 et µ2 des classes est grande. On pourrait donc penser que le problème de
classification devient plus simple lorsque la dimension augmente (car les classes sont davan-
tage « écartées »), et que les performances des classifieurs augmentent.
La figure 2.4 montre le taux d’erreur de deux classifieurs en fonction de la dimension,
pour quatre valeurs m du nombre d’observations dans chaque classe servant à l’apprentis-
sage. À m et d fixés, on considère les 2m observations comme base d’apprentissage pour un
classifieur (5 plus proches voisins ou classifieur de Bayes naïf gaussien, que l’on verra au cha-
pitre 6). Le taux d’erreur est estimé à partir de 200 observations générées aléatoirement selon
les lois précédentes : on calcule simplement la proportion de ces observations correctement
classées par le classifieur. Pour limiter les fluctuations d’échantillonnage, on répète 100 fois
l’expérience et on représente la moyenne des taux d’erreurs.
Les courbes d’erreur obtenues sont typiques du phénomène de Hughes. Le taux d’er-
reur des classifieurs augmente lorsque la dimension dépasse un certain seuil dépendant du
1. Exemple inspiré de : G.V. Trunk, A problem of dimensionality : A simple example, IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 1, no. 3, 1979.
nombre d’observations. Le taux d’erreur tend même vers 1/2 lorsque la dimension tend vers
l’infini : en très grande dimension les classifieurs ne font donc pas mieux qu’un tirage à pile
ou face. . .On peut remarquer dans cette expérience que, selon la taille de la base d’apprentis-
sage et la dimension, l’un ou l’autre des deux classifieurs peut être bien plus performant.
Il s’agit d’une manifestation de la malédiction de la dimension et du fait que les distances
ne permettent plus de discriminer les observations lorsque la dimension augmente.
Le phénomène de Hughes est général, on le retrouve dans de nombreuses situations. Ce
qu’il faut retenir est qu’essayer de classifier (ou régresser) en grande dimension est rarement
une bonne idée, sauf à disposer d’un (potentiellement très) grand nombre d’observations.
fini des catégories possibles. L’objectif est de faire une prédiction h(x) à partir d’une obser-
vation x dont on ne connaît pas l’étiquette. On suppose que le prédicteur h est cherché dans
une famille H correspondant à un modèle de prédiction. Par exemple, dans le cadre de la ré-
gression linéaire multivariée où x ∈ Rd , on cherche h dans l’ensemble des fonctions affines :
n o
H = h : x 7→ w 0 + w 1 · x, tel que w 0 ∈ R, w 1 ∈ Rd
Pour un problème de classification supervisée, on peut par exemple chercher h parmi les
réseaux de neurones à une couche cachée formée de cinq neurones. Dans tous les cas, h ∈ H
dépend de paramètres qu’il faudra déterminer en fonction des observations étiquetées.
Le classifieur h est susceptible de faire des erreurs sur la base d’apprentissage, auquel cas
h(x n ) ̸= y n . On introduit une fonction ℓ (loss function) quantifiant le coût d’une erreur sur
l’observation (x n , y n ) : ℓ(y n , h(x n )). Par exemple :
— dans le cadre de la régression, on peut choisir
¢2
ℓ(y n , h(x n )) = y n − h(x n )
¡
moyen sur tout l’espace des observations. Il est donc pertinent pour quantifier les perfor-
mances de h face à de nouvelles observations. Le risque moyen de prédiction s’écrit formel-
lement comme :
R p (h) = E (X ,Y ) (ℓ(Y , h(X )))
Démonstration
Par définition de f : R p ( f ) ≤ R p ( fe), d’où la première inégalité.
Par ailleurs :
Donc
R p ( fe) − R e ( fe) + R e ( f ) − R p ( f ) ≤ 2 max |R p (h) − R e (h)|
h∈H
En pratique, on va réserver une partie (disons 20%) des observations de la base de données
pour former une base de test T (certains auteurs parlent de base de validation), le reste (80%)
formant la base d’apprentissage. Le prédicteur h sera choisi en minimisant R e calculé sur la
base d’apprentissage, et on calculera ensuite le risque empirique sur la base de test :
1
ℓ y n , h(x n )
X ¡ ¢
R t (h) =
#T (x n ,y n )∈T
Notons que le prédicteur feH ∗ sélectionné n’est pas forcément celui qui présente le plus
petit risque empirique sur la base d’apprentissage parmi tous les prédicteurs feH .
Ce que l’on vient de décrire est la validation holdout.
On parle de learning loss (ou training loss) pour R e et de test loss pour R t .
L’inconvénient de cette approche est qu’il vaut mieux réserver une part assez importante
des données pour l’apprentissage. Le risque calculé sur la base de test, de taille nécessaire-
ment limitée, présente des fluctuations d’échantillonnage potentiellement importantes. Ces
fluctuations sont gênantes lorsqu’on sélectionne H ∗ car la valeur plus petite de R t ( feH ∗ )
parmi les R t ( feH ) peut très bien être le résultat du hasard de la construction de la base de
test T plutôt que des mérites du modèles H ∗ . On peut moyenner ces fluctuations en décou-
pant la base de données en K sous-ensembles puis en calculant successivement R t sur l’un
de ces sous-ensembles, l’apprentissage étant fait au préalable sur les K − 1 sous-ensembles
restants. Un score moyen est alors calculé comme la moyenne des K valeurs de R t obtenues.
On sélectionne finalement le modèle de score moyen minimal.
Il s’agit de la « validation croisée à K plis » (K -fold cross validation). Le cas extrême K =
N correspond à la situation suivante : on entraîne N fois le prédicteur sur un ensemble de
N −1 observations, l’ensemble de test T étant réduit à la N ème observation. On parle alors de
validation croisée leave-one-out. Bien entendu, le temps de calcul peut être assez important
car il faut procéder à N entraînements successifs. En pratique, on se contente souvent d’une
validation croisée à K = 5 ou K = 10 plis. La figure 2.6 illustre la validation croisée à cinq plis.
S1 S2 S3 S4 S5
A A A A T → coût d’erreur sur T : R 1
A A A T A → coût d’erreur sur T : R 2
A A T A A → coût d’erreur sur T : R 3
A T A A A → coût d’erreur sur T : R 4
T A A A A → coût d’erreur sur T : R 5
F IGURE 2.6 – Validation croisée à cinq plis : la base des observations est séparée en cinq sous-
ensembles (plis) S 1 . . .S 5 de taille identique, chaque sous-ensemble est à tour de rôle dans la
base d’apprentissage ou dans la base de test. L’apprentissage se fait sur les quatre plis d’ap-
prentissage, et un coût d’erreur est calculé sur le pli de test. Le score de validation croisée est la
moyenne des cinq coûts d’erreur obtenus.
La validation croisée (ou la validation holdout) permet de choisir un prédicteur pour dif-
férents modèles H . Souvent, ce qui distingue les modèles H sont les valeurs des hyperpara-
mètres. Par exemple, l’hyperparamètre λ dans la régression ridge ou le Lasso du chapitre 1,
ou la taille de la couche cachée d’un réseau de neurones. La validation croisée fournit donc
une méthode pour fixer les hyperparamètres parmi un ensemble fini de valeurs : on calcule
le score de validation croisée des prédicteurs optimaux trouvés pour différentes valeurs (en
nombre fini) des hyperparamètres, et on sélectionne le jeu d’hyperparamètres donnant le
meilleur score.
Réduction de dimension Pour en savoir plus, les deux articles suivants sont disponibles sur
Internet :
C. Burges, Dimension Reduction : A Guided Tour, Foundations and Trends in Machine Lear-
ning, vol. 2, no. 4, p. 275-365, 2009.
E. Bingham and H. Mannila, Random projection in dimensionaly reduction : applications to
image and text data, proceedings of the ACM International Conference on Knowledge Disco-
very and Data Mining (SIGKDD), p. 245-250, 2001.
tion x sur l’ensemble des observations étiquetées possibles fournissant chacun un prédic-
teur h E .
On calcule successivement :
µ³ ´2 ¶
2
¡ ¢
E E (y − h E (x)) = E E y − h(x) + h(x) − h E (x)
µ³ ´2 ¶ µ³ ´2 ¶ ³³ ´³ ´´
= E E y − h(x) + E E h E (x) − h(x) + 2E E y − h(x) h E (x) − h(x)
Or :
µ³ ´2 ¶ ³ ´2
— EE y − h(x) = y − h(x) car la variable aléatoire dont on calcule l’espérance ne
dépend pas de E ;
³³ ´³ ´´ ³ ´ ³ ´ ³ ´
— E E y − h(x) h E (x) − h(x) = E E yh E (x) +E E h(x)2 −E E yh(x) −E E h E (x)h(x) =
¡ ¢
³ ´ ³ ´
0. En effet : E E yh E (x) = yh(x), E E h(x)2 = h(x)2 , E E yh(x) = yh(x), et enfin
¡ ¢
³ ´
E E h E (x)h(x) = h(x)2 . Les termes s’annulent donc deux à deux.
On conclut. La moyenne sur les ensembles d’apprentissage de l’erreur quadratique de pré-
diction est : ´2 µ³ ´2 ¶
¡ 2
¢ ³
E E (y − h E (x)) = y − h(x) + E E h E (x) − h(x)
Le biais mesure l’écart entre prédiction moyenne et vraie étiquette. En cas de sous-appren-
tissage, le biais est élevé : le modèle ne capture pas suffisamment d’information et fournit, en
moyenne, des prédictions assez éloignées de ce qui est attendu. C’est le cas par exemple si on
cherche une régression linéaire alors que les étiquettes y ne sont pas liées aux x de manière
linéaire. La variance mesure l’amplitude des changements dans la prédiction si on change
l’ensemble d’apprentissage. En cas de sur-apprentissage, la variance est élevée : le modèle
s’adapte trop à la base d’apprentissage et varie fortement lorsque la base change.
Un modèle simple sera donc affecté d’un biais élevé mais d’une variance faible (car il
n’est pas très affecté par des modifications de la base d’apprentissage), tandis qu’un modèle
complexe sera affecté d’un biais faible (avec suffisamment d’observations la prédiction sera
correcte) mais d’une variance élevée. Il faut donc réaliser un compromis entre biais et va-
riance.
Complexité des modèles La présentation du dilemme biais-fluctuation est adaptée des notes
du cours de Stéphane Mallat au Collège de France en 2018 (chaire sciences des données), dis-
ponible à cette URL :
https://www.college-de-france.fr/site/stephane-mallat/course-2017-2018.htm
En effet, on peut utiliser le résultat de l’annexe A.1 avec les notations : X n = ℓ(Yn , h(X n )),
∀ n, [a n , b n ] = [0, 1], X = R e (h), et E (X ) = N1 n=1
PN
E (ℓ(Yn , h(X n ))) = R p (h).
Maintenant, la fluctuation est maxh∈H |R e (h) − R p (h)|, donc elle est supérieure à ε si au
moins un des h de H vérifie l’inégalité précédente. Autrement dit :
µ ¶
Pr max |R e (h) − R p (h)| Ê ε = Pr ∪h∈H |R e (h) − R p (h)| Ê ε
¡ £ ¤¢
h∈H
Pr |R e (h) − R p (h)| Ê ε
X ¡ ¢
É
h∈H
En effet, la probabilité de l’union finie d’événements est inférieure à la somme des probabi-
lités des événements.
Par conséquent, µ ¶
Pr max |R e (h) − R p (h)| Ê ε É 2 #H e −2N ε
2
h∈H
s µ ¶
1 2 #H
ε= log
2N δ
d’où Ã s µ ¶!
1 2 #H
Pr max |R e (h) − R p (h)| Ê log Éδ
h∈H 2N δ
soit : Ã s µ ¶!
1 2 #H
Pr max |R e (h) − R p (h)| É log Ê 1−δ
h∈H 2N δ
q
log(2 #H )−log(δ)
Ainsi, avec une probabilité supérieure à 1 − δ, la fluctuation est bornée par 2N .
On peut noter que cette borne ne dépend pas de la loi (inconnue) de (X , Y ).
Comme pour tout h ∈ H , R p (h) − R e (h) É maxh∈H |R e (h) − R p (h)|, on peut conclure par
la proposition suivante.
Proposition 2.2 Si H est un modèle de cardinal fini, pour tout h ∈ H , avec probabilité au
moins 1 − δ, s
log(2 #H ) − log(δ)
R p (h) É R e (h) +
2N
Avec une probabilité au moins 1−δ, le risque moyen de prédiction est majoré par l’expression
donnée par la proposition précédente, et on espère que le majorant soit petit.
D’un point de vue pratique, cette borne sur le risque moyen de prédiction fait apparaître
un compromis entre risque empirique et log(#H )/N . Minimiser le risque empirique n’assu-
rera un faible risque moyen de prédiction que si le modèle H n’est pas trop complexe par
rapport à la taille N de l’ensemble d’apprentissage, la complexité étant mesurée par le cardi-
nal de H .
Bien entendu, H n’a pas de raison d’être fini, car en général H est un ensemble de
classifieurs dépendant de paramètres réels. Dans ce cas, des développements théoriques
dans les années 1980-1990 ont permis de mesurer la complexité par la dimension de Vapnik-
Chervonenkis ou la complexité de Rademacher. Le problème est que les bornes obtenues
sont assez larges : on peut difficilement s’en servir dans un cas pratique pour fixer la taille de
l’ensemble d’apprentissage de manière à assurer un risque de prédiction satisfaisant.
Le lecteur souhaitant approfondir le sujet pourra consulter :
V. Vapnik, Statistical learning theory, Wiley, 1998.
Problèmes de partitionnement
1
D UA (A , B) =
X
d (x, y)
#A #B (x,y)∈A ×B
— critère de Ward :
#A #B
D W (A , B) = ∥m A − m B ∥2
#A + #B
1 P 1 P
où m A = #A x∈A x et m B = #B x∈B x sont les barycentres des deux groupes, et #A
et #B leur cardinal.
Notons que même si d vérifie les propriétés d’une distance sur un espace métrique, ce
n’est pas forcément le cas de D.
Pour que deux groupes soient proches au sens du critère single linkage, il suffit que deux
de leurs points soient proches, alors qu’au sens du critère complete linkage il faut que les
points les plus éloignés entre les deux groupes soient proches (donc que tous les points
soient proches). Le critère average linkage porte sur la moyennes des distances entre toutes
les paires de points des groupes.
Pour que deux groupes soient proches au sens du critère de Ward, il faut que leurs bary-
centres soient proches, la notion de proximité étant pondérée par le nombre de points dans
les groupes. Pour une même distance euclidienne entre barycentres, deux groupes de tailles
similaires donneront un D plus élevé que deux groupes de tailles très différentes. En effet,
dans le premier cas (#A ≃ #B), #A #B/(#A +#B) ≃ #A /2, et dans le second cas (#A >> #B),
#A #B/(#A + #B) ≃ #B. Le critère de Ward tend donc à rapprocher les « gros » groupes des
« petits » groupes.
Par ailleurs, on peut noter que :
D W (A , B) = ∥x − m A ∪B ∥2 − ∥x − m A ∥2 − ∥x − m B ∥2
X X X
x∈A ∪B x∈A x∈B
Lorsque l’étape 2 est itérée, il faut calculer la distance entre le nouveau groupe obtenu
par fusion et les groupes restants de l’itération précédente.
On construit ainsi un arbre binaire appelé dendrogramme :
1. les feuilles de l’arbre sont les observations, placées sur l’axe des abscisses,
2. pour chaque paire de groupes (A , B) fusionnant, on trace des segments verticaux issus
des deux groupes, jusqu’à la distance D(A , B), et on représente la fusion entre (A et
B) par un segment horizontal à la « hauteur » D(A , B) figurant sur l’axe des ordonnées.
On construit donc une structure hiérarchique en partant des observations isolées, et à chaque
étape, la hauteur des segments augmente. Ceci justifie l’appellation « méthode hiérarchique
ascendante ».
Du point de vue du temps de calcul, l’algorithme de construction de la classification hié-
rarchique ascendante nécessite au moins de calculer les distances entre points deux à deux
et de les trier, ce qui est relativement lent. Par ailleurs, l’occupation mémoire peut également
être importante si on n’y prend pas garde, si par exemple on calcule à l’initialisation de l’al-
gorithme le tableau des distances entre toutes les observations deux à deux.
3.1.4 Illustration
La figure 3.1 montre des classifications hiérarchiques obtenues à partir d’un ensemble de
points très simple, de manière à illustrer la construction du dendrogramme. Le nombre de
groupes à trouver a été fixé à deux. Il s’agit donc des deux dernières groupes fusionnant dans
la construction du dendrogramme. La mesure de dissimilarité d est la distance euclidienne.
On voit que le critère single linkage ne convient pas ici. Il souffre du problème de « chaînage » :
il a tendance à progressivement fusionner les groupes liés par une chaîne de points. Le critère
complete linkage est basé sur la plus grande distance entre points de deux groupes, ce qui
explique que les points 4 et 5 appartiennent à deux groupes différents. Les critères average
linkage et de Ward, basés sur des moyennes, fournissent des groupes homogènes et relative-
ment bien séparés les uns des autres. Notez l’aspect similaire des dendrogrammes construits
selon ces deux critères.
D’après le paragraphe 3.1.3, on pourrait fixer le nombre de groupes à sept dans la classifi-
cation single linkage (groupe {3, 4, 5} et les six autres observations dans autant de groupes), à
trois, peut-être deux dans la classification complete linkage (groupes {1, 2, 3, 4}, {5, 7}, {6, 8, 9}),
et à deux dans les classifications average linkage et Ward (groupes {1, 2, 3, 4, 5} et {6, 7, 8, 9}). On
se rend compte que selon la distribution des observations, l’un ou l’autre des critères devra
être préféré. Toute la difficulté pratique est de choisir lequel.
La figure 3.2 est une autre illustration du phénomène de chaînage.
2 4 5 8
1
3 7
0.8 9
0.6
1 6
0.4
0.5 1 1.5 2 2.5 3
single linkage
0.55
0.5
0.4
1
0.8
0.35
0.6
0.3
0.4
3 4 5 6 8 7 1 2 9 0.5 1 1.5 2 2.5 3
complete linkage
2.5
complete linkage
1.5
1
1
0.8
0.6
0.5
0.4
3 4 1 2 5 7 6 8 9 0.5 1 1.5 2 2.5 3
average linkage
1.6
1.4
1.2
average linkage
1
1
0.8
0.8
0.6
0.6
0.4
0.4
3 4 5 1 2 6 8 9 7 0.5 1 1.5 2 2.5 3
Ward criterion
2.5
2
Ward criterion
1
1.5
0.8
1
0.6
0.5
0.4
3 4 5 1 2 6 8 9 7 0.5 1 1.5 2 2.5 3
F IGURE 3.1 – Exemples de partitionnement avec quatre mesures de dissimilarité entre groupes,
sur le même ensemble de point. De haut en bas : ensemble d’observations à partitionner, critère
single linkage, critère complete linkage, critère average linkage, critère de Ward. Le dendro-
gramme est à gauche et la partition en deux groupes obtenue à droite.
Voici sa description.
0.4 0.4
0.2 0.2
0 0
-0.2 -0.2
-0.4 -0.4
-0.6 -0.6
-0.8 -0.8
-1 Cluster 1 -1 Cluster 1
Cluster 2 Cluster 2
-1.2 Cluster 3 -1.2 Cluster 3
Cluster Centroid Cluster Centroid
-1.4 -1.4
-1.5 -1 -0.5 0 0.5 1 1.5 2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0.4 0.4
0.2 0.2
0 0
-0.2 -0.2
-0.4 -0.4
-0.6 -0.6
-0.8 -0.8
-1 Cluster 1 -1 Cluster 1
Cluster 2 Cluster 2
-1.2 Cluster 3 -1.2 Cluster 3
Cluster Centroid Cluster Centroid
-1.4 -1.4
-1.5 -1 -0.5 0 0.5 1 1.5 2 -1.5 -1 -0.5 0 0.5 1 1.5 2
F IGURE 3.3 – Algorithme de Lloyd : illustration. Évolution des moyennes (barycentres des
groupes) et affectation des observations au cours des itérations. Attention, sur chaque gra-
phique sont représentés les clusters à l’étape t − 1 et les barycentres à l’étape t , conformément
au déroulement de l’algorithme.
∥x − y∥22
X
y 7→
x∈A
définie sur tout l’espace est minimale pour la moyenne des points de A :
1 X
y= x
#A x∈A
Démonstration
On développe successivement, pour tout y :
1 P
est bien minimal pour y = #A x∈A x qui annule le seul terme dépendant de y. □
Démonstration
Avec les notations de la description de l’algorithme, en notant E t l’inertie à la fin de l’itéra-
tion t , on peut écrire :
K X ° °2
Et °x − m tj +1 °
X
=
° °
2
j =1 x∈C jt
K X ° °2
°x − m tj +1 °
X
Ê
° °
2
j =1 x∈C t +1
j
d’où E t Ê E t +1 .
La suite des inerties E t est donc décroissante. Comme il n’y a qu’un nombre fini de pos-
sibilités pour former K groupes parmi N observations (il s’agit du nombre de Stirling de se-
∗ ∗
conde espèce s(N , K )), il existe un t ∗ tel que : E t = E t +1 . Pour obtenir cette égalité, les deux
inégalités précédemment établies doivent être des égalités, donc pour tout j , m t ∗ +1 = m t ∗ +2 ,
∗ ∗
et pour tout j , C tj +1 = C tj . Les assignations des observations aux classes ne changent donc
plus pour t > t ∗ . C’est en ce sens qu’on parle de minimum local de l’inertie (et pas dans un
sens habituel faisant intervenir le voisinage dans un espace métrique : ici l’inertie est définie
sur l’ensemble fini des partitions en K groupes). Une autre initialisation pourrait conduire à
∗
une partition (et une valeur de E t ) différente. □
3.2.2 Discussion
La description de l’algorithme de Lloyd ne repose pas explicitement sur la notion de
norme euclidienne : cet algorithme ne fait appel qu’à une distance et à la notion de moyenne.
Pourtant, la convergence de l’algorithme est bien assurée par le lemme 1, qui caractérise la
moyenne à l’aide de la norme euclidienne. Utiliser une norme non-euclidienne n’assure plus
la convergence : il faut alors employer d’autres algorithmes que celui de Lloyd.
L’algorithme de Lloyd converge vers un minimum local de l’inertie : l’initialisation étant
aléatoire, un autre minimum local peut être trouvé à chaque exécution. Il est d’usage d’exécu-
ter l’algorithme plusieurs fois, et de garder la partition d’inertie minimale parmi celles trou-
vées.
Concernant le nombre d’itérations nécessaire avant de converger, la démonstration nous
dit qu’il est borné par le nombre de Stirling de seconde espèce s(N , K ), dont on dispose de
l’équivalent :
s(N , K ) ∼N →+∞ K N /K !
à K fixé. En pratique, le nombre de groupes K est bien inférieur au nombre N d’observa-
tions à classer. Des grandeurs typiques, qui peuvent être bien plus grandes dans certaines
applications, sont par exemple N = 1000, K = 10, d’où un nombre astronomique de possi-
bilités à tester (rappelons que le nombre d’atomes dans l’univers est estimé à 1080 ). Il est
illusoire de tester exhaustivement toutes ces possibilités : un algorithme guidant la recherche
du minimum de l’inertie est nécessaire. En pratique l’algorithme de Lloyd s’arrête bien avant
que le nombre d’itérations atteigne cette borne ; il permet donc de guider efficacement la re-
cherche. De plus, il est possible d’arrêter l’algorithme avant convergence au bout de quelques
itérations car en général seuls quelques points mal classés subsistent alors.
Comme l’inertie mesure la dispersion de chaque groupe autour de sa moyenne par l’in-
termédiaire de la norme euclidienne, l’algorithme des K -moyennes sera adapté à l’identifi-
cation de groupes de forme sphérique, bien représentés par leur moyenne.
Le paramètre K est critique, et bien entendu on ne sait pas à l’avance combien de groupes
sont recherchés. On se rend compte qu’une partition optimale à K + 1 groupes a une inertie
inférieure à celle d’une partition optimale à K groupes. En effet, considérons la partition op-
timale à K groupes et formons une partition à K + 1 groupes en retirant une observation x̃
du K -ème groupe pour en faire le K + 1-ème groupe. L’inertie de la partition optimale à K
groupes est :
K X ° KX
−1 X °
°x − m j °2 = °x − m j °2 + ∥x − m K ∥22 + ∥x̃ − m K ∥22
X ° ° X
2 2
j =1 x∈C j j =1 x∈C j x∈C K \{x̃}
où les m j sont les moyennes des C j . Les barycentres des groupes C 1 , . . . , C K −1 ne changent
pas, et si on note m K′ le barycentre du groupe C K \{x̃} et m K′ +1 celui de C K +1 (m K′ +1 = x̃ tout
simplement), alors :
°2
— x∈C K \{x̃} ∥x − m K ∥22 ≥ x∈C K \{x̃} °x − m K′ °2 d’après le lemme 1,
P P °
°2
— ∥x̃ − m K ∥22 ≥ °x̃ − m K′ °2 = 0.
°
L’inertie minimale à K groupes est donc supérieure à une inertie obtenue pour K +1 groupes.
Elle est donc également supérieure à l’inertie minimale à K + 1 groupes.
Par conséquent, si on trace le graphe de l’inertie minimale en fonction de K , on observe
une courbe décroissante. En pratique, la partition optimale trouvée par l’algorithme de Lloyd
n’est pas l’optimum global de l’inertie, donc la courbe peut ne pas être strictement décrois-
sante. On peut envisager de choisir comme nombre de groupes la valeur de K à partir de
laquelle l’inertie ne décroît plus franchement. Il s’agit de la méthode du coude (la courbe
marque un coude), ou elbow method, que l’on reverra lors des travaux pratiques.
3.3.1 DBSCAN
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est un algorithme
de partitionnement très utilisé datant de 1996.
Il peut être décrit de la manière suivante, avec les paramètres ε > 0 et N entier :
1. Pour chaque observation, chercher les observations (les « voisins ») à une distance
inférieure à ε, et définir les observations possédant plus de N voisins comme les
« points centraux » ;
2. Construire le graphe de voisinage des points centraux, et définir les groupes comme
les composantes connexes de ce graphe ;
3. Assigner les observations qui ne sont pas des points centraux au groupe du point
central le plus proche parmi les observations voisines, et les assigner au bruit si
aucun voisin n’est point central.
Rappelons que le graphe de voisinage des points centraux est le graphe dont les sommets
sont les points centraux, pour lequel deux sommets sont liés par une arête s’ils sont voisins
(c’est-à-dire à une distance inférieure à ε). Deux sommets du graphe sont dans la même com-
posante connexe s’il existe une suite d’arêtes les connectant.
Dans l’étape 2, on ne considère que les points centraux : deux points centraux sont liés
s’ils sont voisins l’un de l’autre. Le graphe résultant présente des composantes connexes : des
ensembles de points centraux qui ne sont liés par aucun chemin à une autre composante
connexe.
Dans l’étape 1, on voit que les points centraux sont les observations se situant dans des
zones de forte densité.
Pour assurer une complexité optimale en occupation mémoire et en temps de calcul,
il faut implanter l’algorithme de manière réfléchie : trouver les observations voisines et les
suppose disposer d’une fenêtre, c’est-à-dire une fonction W concentrée autour de 0, d’inté-
grale 1 sur l’espace des observations.
L’estimation de la densité en un point x de l’espace des observations est donnée par :
1 N ³x −x ´
X n
p W (x) = W
N hd n=1 h
1 N x −x ³x −x ´
X n n
∇p W (x) = − 2
W
N h d n=1 h h
1 X N ³x −x ´ x x
n n
= d
W 2
− p W (x) 2
N h n=1 h h h
D’où PN ¡ x−xn ¢
h 2 ∇p W (x) n=1 W h xn
= PN ¡ x−xn ¢ − x
p W (x) n=1 W h
Une étape de montée de gradient à pas variable consisterait à remplacer x par x+λ(x)∇p W (x)
où λ(x) > 0 est le pas de la montée. Si la montée de gradient converge bien, les itérés succes-
sifs se rapprochent de plus en plus d’un maximum local.
Si on note : PN ¡ x−xn ¢
n=1 W h xn h 2 ∇p W (x)
m h (x) = PN ¡ x−xn ¢ ) = x +
n=1 W h
p W (x)
2
remplacer x par m h (x) revient à faire une étape de montée de gradient avec λ(x) = pWh (x) . La
fonction λ assure un pas de montée grand lorsque p W est petit (on est loin du maximum, on
peut accélérer) et petit lorsque p W est grand (on s’approche du maximum, il faut ralentir). La
quantité m h (x) est la moyenne des observations pondérée par leur distance à x.
F IGURE 3.5 – Cinq exemples d’évolution des itérés de l’algorithme mean shift (fenêtre gaus-
sienne, largeur de bande h = 0, 5). Les cinq observations initiales sont identifiées par un sym-
bole plus grand : on voit qu’au fur et à mesure, la suite des moyennes converge vers un des deux
extrema locaux de la densité des observations. Le partitionnement par mean shift consiste à
associer au même groupe les observations qui convergent vers le même point.
x n0 = x n
½
jusque convergence ;
— affecter à un même groupe les observations qui ont convergé vers la même limite
La figure 3.5 montre, dans un cas pratique, les itérés successifs obtenus à partir de quelques
points d’initialisation. On peut rendre la discussion précédente un peu plus rigoureuse et
démontrer que mean shift converge effectivement. Nous avons supposé utiliser une fenêtre
gaussienne. En fait, on voit que si ∇W (x) = −c xK (x) (où c est une constante positive), alors
l’algorithme mean shift utilisant la fenêtre K peut toujours être interprété comme une mon-
tée de gradient sur la densité estimée par la méthode de Parzen avec la fenêtre W . N’importe
quelle fonction ne convient pas : il faut que W et K soient des fenêtres (c’est-à-dire concen-
trées autour de 0). Ceci justifie l’utilisation fréquente de la fenêtre
½
1 si |x| É 1
K (x) =
0 sinon
dans l’algorithme mean shift, au lieu d’une fenêtre gaussienne. La convergence est assurée
L’algorithme mean shift peut trouver des groupes de forme quelconque. En pratique, le
choix de la largeur de bande h peut être critique. Néanmoins, la largeur de bande a une inter-
prétation « physique » : elle dépend de la densité des observations. Des heuristiques existent
pour choisir sa valeur a priori, contrairement au nombre de classes K qui est le paramètre de
l’algorithme des K -moyennes. Enfin, le calcul de m h est lourd, ce qui rend l’algorithme assez
lent en pratique.
La figure 3.6 montre un exemple de partitionnement par mean shift.
F IGURE 3.6 – Deux exemples de partitionnement obtenus par mean shift (implantation de
scikit-learn). Première ligne : largeur de bande de 0,5 ; 9 groupes sont identifiés. Seconde ligne :
0,8 ; 4 groupes sont identifiés. On voit l’influence de la largeur de bande : plus elle est grande
plus l’estimation de la densité est « lissée » et moins cette densité présente de maxima (voir la
figure 5.2 au chapitre 5). Le disque de couleur montre la limite des itérés successifs des obser-
vations associées à chaque groupe : il s’agit d’un maximum de l’estimation de la densité de
probabilité par la méthode des fenêtres de Parzen.
au prix d’une inertie un peu plus grande que la solution de Lloyd localement optimale. Mini-
Batch K -means est décrit dans cet article :
D. Sculley, Web-Scale K-Means Clustering, proceedings of the 19th International Conference
Lecture Pour plus de détails sur les K -moyennes et le partitionnement en général, vous
pouvez consulter :
Anil K. Jain, Data clustering : 50 years beyond K-means, Pattern Recognition Letters, vol. 31,
no. 8, p. 651-666, 2010.
Nous nous plaçons dans le cadre de l’apprentissage supervisé. On suppose disposer d’une
base de N observations étiquetées (x n , y n )1ÉnÉN , avec y n une étiquette qui prend une valeur
scalaire ou vectorielle dans le cas de la régression, ou une valeur dans un ensemble fini de
classes dans le cas de la classification. Rappelons qu’on cherche une fonction f w capable de
prédire l’étiquette d’une nouvelle observation x en se basant sur les observations étiquetées.
Cette fonction dépend généralement d’un ensemble de paramètres w .
La question à laquelle on essaie d’apporter des éléments de réponse est la suivante : com-
ment choisir les paramètres w de f w de manière à minimiser le risque d’erreur face à une
nouvelle observation absente de la base initiale des N observations ? Nous savons depuis le
chapitre 2 qu’il ne suffit pas de chercher w tel que f w minimise le risque d’erreur sur la base
d’apprentissage (le risque empirique), comme le montre l’exemple de l’apprentissage « par
cœur ».
Dans ce chapitre, nous définissons le prédicteur optimal dans le cadre d’une modélisa-
tion probabiliste de l’ensemble des observations.
Supposons un instant que la loi de (X , Y ) est connue, et notons-la p(x, y). Bien entendu,
toute la difficulté est qu’elle est, en pratique, inconnue. Que peut-on dire d’un classifieur h
CHAPITRE 4. THÉORIE STATISTIQUE DE LA DÉCISION 56
Pour alléger les notations, on omettra l’indice 2 de la norme dans la suite du chapitre : il
s’agira toujours de la norme euclidienne.
En développant ∥y − h(x)∥2 = ∥y∥2 + ∥h(x)∥2 − 2y · h(x) :
Ï Z µZ ¶
= ∥h(x)∥2 p(x)p(y|x) dx dy − 2 y p(y|x) dy · h(x)p(x) dx
Néanmoins,
µZ ¶ ° Z °2 °Z °2
2
° ° ° °
∥h(x)∥ − 2 y p(y|x) dy · h(x) = °h(x) − y p(y|x) dy ° − ° y p(y|x) dy °
° ° °
°
Le second terme ne dépendant pas de h, on peut conclure : minimiser R p (h) par rapport à h
revient à minimiser Z ° Z °2
° °
°h(x) − y p(y|x) dy ° p(x) dx
° °
F IGURE 4.1 – Régression pour un coût quadratique. Dans ces exemples, on souhaite prédire y ∈
R en fonction de l’observation x ∈ R. L’estimateur optimal est représenté en trait plein et est
R
donné en chaque x par : h(x) = y p(y|x) dy = E (Y |X = x). À gauche : situation générale dans
laquelle la forme de la densité p(y|x) varie selon x. À droite : lorsque (X , Y ) est un vecteur
gaussien, h est un estimateur linéaire.
c’est-à-dire choisir :
Z
h(x) = y p(y|x) dy
Proposition 4.1 Le régresseur minimisant le risque moyen de prédiction pour un coût d’erreur
quadratique est donné par la relation :
Z
h(x) = E (Y |X = x) = y p(y|x) dy
4.1.1.2 En pratique
E (Y |X = x) = E (Y ) + ΣT0 Σ−1
X (x − E (X ))
10
4
y
-2
-4
-1 0 1 2 3
x
F IGURE 4.2 – Régression à noyau de Nadaraya-Watson. Le noyau est ici une fonction gaus-
sienne d’écart-type h.
R R R R
En effet, yWh (y − y i ) dy = y i Wh (y) dy + yWh (y) dy = y i car Wh (y) dy = 1 dans la mé-
R
thode de Parzen, et Wh étant une fonction paire, yWh (y) dy = 0.
On obtient donc, à partir des observations étiquetées (x i , y i )1Éi ÉN , la fonction de régres-
sion suivante :
PN
y i Wh (x − x i )
h(x) = Pi =1
N
i =1 Wh (x − x i )
On écrit plus succinctement ℓ(y, h(x)) = 1F (x, y), où 1F est la fonction indicatrice du sous-
ensemble F = {(x, y), h(x) ̸= y} de l’ensemble des observations étiquétées. Autrement dit, F
est l’ensemble des observations étiquetées dont la classe n’est pas correctement prédite par h.
Rappelons que la fonction indicatrice d’un ensemble vaut 1 sur cet ensemble et 0 en dehors.
— p(C k ) est la probabilité a priori (prior probability) de chaque classe. Bien entendu,
PK
k=1
p(C k ) = 1. Il s’agit de l’information potentiellement connue avant d’avoir observé
des données.
Par exemple, dans un problème de reconnaissance de caractères, le but est d’associer
des imagettes figurant les caractères au caractère représenté. On peut connaître la pro-
babilité a priori d’un caractère à partir des fréquences d’apparition dans la langue du
document : p(a) = 0.07, p(b) = 0.01, p(c) = 0.03, etc.
— p(x|C k ) est la probabilité conditionnelle. On devrait parler en fait de densité (ou vrai-
semblance, likelihood) mais bon nombre d’auteurs parlent abusivement de probabilité
dans la littérature de l’apprentissage automatique. Il s’agit de la densité de la loi de pro-
babilité d’une observation tirée dans la classe C k .
Un choix classique est le modèle gaussien. Dans le cas où x ∈ Rd ,
1 1 T
Σ−1
p(x|C k ) = e − 2 (x−µk ) k
(x−µk )
(2π)d /2 |Σk |1/2
p(x|C k )p(C k )
∀ 1 ≤ k ≤ K , p(C k |x) =
p(x)
K K
p(x, C k ) =
X X
p(x) = p(x|C k )p(C k )
k=1 k=1
Pour simplifier les notations, nous nous restreignons au cas biclasse (K = 2) dans la suite
du chapitre.
Avec un coût 0-1, le risque de prédiction s’écrit :
De plus, l’ensemble F (des couples (x, y) pour lesquels la prédiction h(x) est différente de y,
donc fausse) s’écrit comme une union disjointe :
F = F1 ∪ F2
où
F 1 = (x, y) tel que h(x) = C 1 et y = C 2
© ª
(couples mal classés car la prédiction est C 1 alors que la vraie classe est C 2 ), et
(couples mal classés car la prédiction est C 2 alors que la vraie classe est C 1 ).
Ainsi,
Z Z
R p (h) = 1F1 (x, C 2 )p(x, C 2 ) dx + 1F2 (x, C 1 )p(x, C 1 ) dx
Z Z
= p (x, C 2 ) dx + p (x, C 1 ) dx
R1 R2
où
R 1 = x tel que h(x) = C 1
© ª
et
R 2 = x tel que h(x) = C 2
© ª
Ces deux ensembles séparent les observations respectivement en celles classées dans C 1
par h et celles classées dans C 2 .
Remarquons que si k = 1 ou k = 2, p(x, C k ) = p(x|C k )p(C k ) = p(C k |x)p(x).
F IGURE 4.3 – Minimisation du risque de prédiction. Nous représentons les densités p(x, C 1 )
et p(x, C 2 ) dans le cas où x ∈ R (les observations sont des scalaires). Les ensembles R 1 et
R 2 réalisent une partition de l’espace des observations. Le risque de prédiction R p (h) =
R 1 p (x, C 2 ) dx + R 2 p (x, C 1 ) dx apparaît comme la somme des surfaces hachurées hori-
R R
Proposition 4.3 Le classifieur minimisant le risque moyen de prédiction pour un coût d’erreur
0-1 est défini par :
h(x) = arg max p(x|C k )p(C k )
Ck
On remarque que le classifieur de Bayes peut classer une observation x dans une classe C 1 ,
même si p(x|C 1 ) n’est pas la vraisemblance la plus élevée parmi les p(x|C k ), à condition que
la probabilité a priori p(C 1 ) ait une valeur élevée.
Comme dans la discussion sur la régression, il ne faut pas perdre de vue que le raison-
nement a été mené en supposant les différentes distributions de probabilités connues. Le
classifieur de Bayes est le classifieur idéal dans le cas du risque 0-1, dans le sens où il réalise
le minimum du risque de prédiction (ce minimum s’appelle d’ailleurs « risque de Bayes »).
Néanmoins, pour le mettre en œuvre il faut être capable d’estimer les distributions de pro-
babilité de manière fiable (voir le chapitre 5), ou d’imposer des hypothèses additionnelles,
comme nous le ferons dans le chapitre 6.
N
ρ(y n − f θ (x n ))
X
n=1
avec ρ une fonction donnant un coût moins grand aux données aberrantes, de résidus élevés.
Par exemple, le coût de Huber (Huber loss) s’exprime comme :
x2 si |x| É δ
½
ρ(x) =
2δ|x| − δ2 sinon
si |x| É δ
½
0
ρ(x) =
1 sinon
4
Huber loss
3.5 0-1 loss
square loss
2.5
1.5
0.5
0
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x
F IGURE 4.4 – Croissance comparée des coûts de Huber (δ = 1), 0-1, et quadratique.
1 1
0.8 0.8
0.6 0.6
0.4 0.4
0.2 0.2
0 0
0 0.5 1 1.5 2 2.5 0 0.5 1 1.5 2 2.5
F IGURE 5.1 – Estimation de densité par histogramme. Dans cet exemple, les observations (les
mêmes dans les deux cas) sont des réels et sont représentées par des croix sur l’axe des abs-
cisses. Les histogrammes sont définis comme la proportion d’observations « tombant » dans
les baquets (des intervalles dont les limites sont marquées par un petit disque), normalisée
de manière à ce que l’intégrale sous l’histogramme soit égale à 1. On constate que la fonction
constante par morceaux censée approcher la densité dépend fortement du choix de la discré-
tisation de l’espace des observations (ici une légère translation de la position des « baquets »
change drastiquement l’aspect des histogrammes, mais un changement de largeur aurait aussi
pu avoir un impact important).
5.1.1 Histogrammes
Pour estimer une densité de probabilité par histogramme, on commence par définir une
discrétisation de l’espace des observations pour construire des « baquets » (bins), puis on cal-
cule la proportion des observations tombant dans chaque baquet. La densité de probabilité
est estimée comme la proportion divisée par la mesure du baquet, de manière à ce que l’in-
tégrale de la densité estimée sur l’espace soit égale à 1. La densité estimée est donc constante
sur chaque baquet.
Dans le cas d’observations scalaires (d = 1), les baquets sont des intervalles, et en dimen-
sion plus grande des pavés.
Dans cette méthode, le choix de la discrétisation est parfois critique, comme l’illustre la
figure 5.1.
Lorsqu’on souhaite une estimation plus régulière qu’une fonction constante par mor-
ceaux, on utilise l’estimation par fenêtre de Parzen.
L’estimation est faite en centrant une fonction (obtenue à partir d’une fenêtre, ou noyau,
notée W ) sur chaque observation et en moyennant les fonctions sur l’ensemble des observa-
1 2.5
0.9
0.8 2
0.7
0.6 1.5
0.5
0.4 1
0.3
0.2 0.5
0.1
0 0
0 0.5 1 1.5 2 2.5 0 0.5 1 1.5 2 2.5
F IGURE 5.2 – Estimation de densité par la méthode de Parzen : ici, fenêtre gaussienne. À
gauche : h = 0.2 ; à droite : h = 0.05. En bleu : densité estimée ; en rouge : W ((x − x n )/h) pour
chaque x n . Une largeur de bande h trop petite fait apparaître des détails indésirables, et une
largeur trop grande lisse des détails pertinents.
1 N ³x −x ´
X n
p W (x) = W
N hd n=1 h
où W est une fonction concentrée autour de 0, d’intégrale 1 sur l’espace des observations, et
où h > 0 est appelée « largeur de bande » (bandwidth).
L’estimation p W a la même régularité que W : si W est de classe C ∞ , alors p W aussi.
Le paramètre h gouverne l’influence de chaque observation x n : si h est grand, p W (x)
dépendra de x n même si x est éloigné de x n .
La normalisation 1/(N h d ) est telle que l’intégrale de p W sur l’espace des observations
est 1 (ce qui est logique pour une densité).
On parle d’estimation par noyaux ou par fenêtres de Parzen, ce qu’illustre la figure 5.2.
Un choix classique de W est la fenêtre gaussienne :
Donc :
K
Z
≃ φ(y) dy ≃ φ(x) × Volume(B x )
N Bx
K
φ(x) =
N VK (x)
où VK (x) est le volume d’une boule centrée en x contenant les K plus proches voisins de x,
sur laquelle la densité est supposée constante.
En fait, cette méthode est rarement utilisée pour estimer des densités, mais elle apparaîtra
dans la méthode des K plus proches voisins pour la classification supervisée au chapitre 6.
1 XN 1 X N
µ= xn et σ2 = (x n − µ)2
N n=1 N − 1 n=1
Rappelons que pour un vecteur aléatoire gaussien, des estimateurs de la moyenne (qui est
alors un vecteur) µ et de la matrice de covariance Σ sont :
1 XN 1 X N
µ= xn et Σ= (x n − µ)(x n − µ)T
N n=1 N − 1 n=1
Le paragraphe 5.3 discute les problèmes pratiques posés en grande dimension par l’estima-
teur Σ.
De manière générale, dans les méthodes paramétriques, on suppose la densité de la forme
f θ où θ représente un ou plusieurs paramètres. La méthode du maximum de vraisemblance
(Fisher 1922) permet alors d’estimer θ à partir des observations.
Exemple 5.1
On suppose (x 1 , x 2 , . . . , x N ) réalisations de variables aléatoires i.i.d. gaussiennes. La vrai-
semblance s’écrit :
à !
1 1 XN ³ x − µ ´2
2 n
L (µ, σ ) = N exp −
σ (2π)N /2 2 n=1 σ
¢ 1 X N ³ x − µ ´2
n
L(µ, σ2 ) = − log σN (2π)N /2 −
¡
2 n=1 σ
et s’annulent pour :
1 PN
µMV =
(
N i =n x n
1 PN
σ2MV = N n=1 (x n − µMV )
2
1. https://fr.wikipedia.org/wiki/Fonction_de_vraisemblance
Dans l’exemple précédent, on a pu faire les calculs et trouver une expression explicite
de θMV . Si ce n’est pas possible, on utilise une méthode d’optimisation numérique.
M
φθ (x) = πm Gµm ,Σm (x)
X
m=1
PM
où m=1 πm = 1 et Gµm ,Σm désigne la densité gaussienne de moyenne µm et matrice de cova-
riance Σm :
1
e −(x−µm ) Σm (x−µm )/2
T −1
Gµm ,Σm (x) = d /2 1/2
(2π) |Σm |
Les paramètres d’un mélange de gaussiennes sont alors θ = (πm , µm , Σm )m∈{1,...,M } .
Dans ce cas, il n’y a pas de formule explicite permettant de trouver les paramètres maxi-
misant la vraisemblance. Néanmoins, il est possible de démontrer que l’algorithme numé-
rique Espérance-Maximisation (EM), décrit ci-après, permet d’estimer ces paramètres à par-
tir des observations.
∂L N
γnm Σ−1
m (x n − µm ) = 0
X
=
∂µm n=1
4.5
0.1
4
0.5
0.6
0.2
3.5
0.1
0.03.2
0.2
0.3
0.4
0
4 0.5 0..43
y
0. 0.6
0.1
3
0.
0.5
0.1
0.2
3
0.
0.3
0.1
0.4
2.5
0.1
0.2
2
4 4.5 5 5.5 6 6.5 7 7.5 8
x
F IGURE 5.3 – La densité des observations bidimensionnelles (représentées par des points) est
ici modélisée comme un mélange de trois gaussiennes. Les paramètres du mélange sont esti-
més par l’algorithme EM. À gauche : représentation des lignes de niveau de la densité dans le
plan des observations. Rappelons que les lignes de niveau d’une densité gaussienne bidimen-
sionnelle sont des ellipses (cf. annexe A.3.3). À droite : représentation tridimensionnelle : les
observations sont représentées dans le plan x-y, et l’axe des z représente la valeur de la densité
estimée.
n γnm
P
Donc en notant Nm = :
1 XN
µm = γnm x n
Nm n=1
1 XN
Σm = γnm (x n − µm )(x n − µm )T
Nm n=1
Enfin,
∂ N Gµm ,Σm (x n )
µ µ ¶¶
L(θ) + λ πm − 1 +λ
X X
=
∂πm
PM
m n=1 l =1 πl Gµl ,Σl (x n )
N γ
nm
+λ = 0
X
=
π
n=1 m
On peut conclure :
1 X N
πm = γnm
N n=1
Le problème est que πm , µm , Σm dépendent de γnm , qui dépend lui-même de ces para-
mètres.
— M-step :
1 N
i +1
µ γinm x n
X
m = i
γ
P
n nm n=1
N
i +1 1
Σm = P i γinm (x n − µim )(x n − µim )T
X
∀ m ∈ {1, . . . , M },
γ
n nm n=1
1 XN
i +1
πm = γi
N n=1 nm
— incrémenter i
Proposition 5.1 Cet algorithme converge vers un maximum local ou un point-selle de la vrai-
semblance L ou, de manière équivalente, de la log-vraisemblance L.
les matrices de covariances sont diagonales (pour tout m, Σm = σm Id), #{θ} = M −1+M d +M .
Plusieurs critères d’information sont possibles, que l’on peut justifier par différentes consi-
dérations que l’on ne détaillera pas.
10 1
10 0
10 -1
10 -2
10 -3
0 2 4 6 8 10
10 4
d 1
Y −|x −µ |2 /(2σ2j )
p(x) = p e j j
j =1 2πσ j
1 −
P
j |x j −µ j |2 /(2σ2j )
= e
d /2 σj
Q
(2π) j
1 T
Σ−1 (x−µ)/2
= e −(x−µ)
(2π)d /2 |Σ| 1/2
où µ est le vecteur des µ j , Σ est la matrice diagonale formée des variances σ2j et |Σ| désigne
son déterminant.
Supposer l’indépendance permet de passer d’une matrice de covariance générale possé-
dant d (d − 1)/2 paramètres à une matrice de covariance diagonale à d paramètres. Estimer Σ
nécessite alors nettement moins d’observations.
On peut interpréter les πm comme la probabilité a priori p(C m ) d’une classe, et les Gµm ,Σm (x)
comme les vraisemblances p(x|C m ) de ces classes.
πm Gµm ,Σm (x n )
Ainsi, le terme γnm = PM calculé dans l’algorithme EM apparaît comme la pro-
l =1 πl G µl ,Σl (x n )
babilité a posteriori :
p(C m )p(x n |C m )
p(C m |x n ) = PM
l =1
p(C l )p(x n |C l )
1 2 2
Gµm ,σ2 Id (x) = e −∥x−µm ∥2 /(2σ )
(2π)d /2 σd
Donc lorsque σ → 0,
πm Gµm ,σ2 Id (x)
PM
πG 2 (x)
l =1 l µl ,σ Id
converge vers :
si m est le maximum des πm Gµm ,σ2 Id (x)
½
1
0 sinon
c’est-à-dire :
si m = arg min l ∥x n − µl ∥2
½
1
∀n, lim γnm =
σ→0 0 sinon
En effet, tous les πl Gµl ,σ2 Id tendent vers 0 lorsque σ → 0, mais on peut conclure en écrivant :
πm Gµm ,σ2 I (x)
d
= P 1 avec αl → 0 lorsque m maximise πm Gµm ,σ2 Id (x) (détails laissés
1+ l ∈{1,...,M }\m αl
PM
l =1 πl G µ ,σ2 I (x)
l d
en exercice).
On remarque que les πm et les Σm = σ2 Id n’interviennent plus dans la définitions des γnm .
— E-step :
si m = arg min l ∥x n − µl ∥2
½
1
∀m, n, γinm
+1
=
0
sinon
n o
i
Cm = x n t.q. γinm
+1
=1
— M-step :
1
∀m, n, µim+1 =
X
i
x
#C m i
x∈C m
Une manière de lutter contre la malédiction de la dimension est de supposer les com-
posantes de x = (x 1 , x 2 , . . . , x d ) ∈ Rd indépendantes conditionnellement à chaque classe C k .
La loi jointe étant alors le produit des lois marginales, on peut écrire l’égalité suivante pour
CHAPITRE 6. MISE EN ŒUVRE DU CLASSIFIEUR DE BAYES 78
chaque classe C k :
d ³ ´
p(x | C k ) = p xi | Ck
Y
i =1
Le gros avantage de cette approche est qu’on est ramené à l’estimation des d lois de pro-
babilité p x i | C k sur R à la place de la loi p(x | C k ) sur Rd .
¡ ¢
Ce classifieur est qualifié de naïf car il fait l’hypothèse que les composantes sont condi-
tionnellement indépendantes, ce qui est en pratique très optimiste. Ce classifieur présente
malgré tout de bonnes performances dans un certain nombre de cas pratiques.
à !
µi ,1 − µi ,2
α1 =
σ2i 1Éi Éd
Nous avons donc démontré, sous l’hypothèse d’égalité des variances des composantes
(∀i , σi ,1 = σi ,2 ), que le classifieur naïf de Bayes gaussien sépare linéairement les deux classes.
Autrement dt, la frontière de classification est un hyperplan de Rd . Attention, ceci n’est pas
vrai si les variances ne sont pas supposées égales. Dans ce cas, le calcul précédent montrerait
que la fonction de décision est quadratique, conduisant en dimension d = 2 à une frontière
de décision en ellipse, parabole, ou hyperbole (voir section 6.5).
p(C 1 )p(x|C 1 )
p(C 1 |x) =
p(C 1 )p(x|C 1 ) + p(C 2 )p(x|C 2 )
1
= p(C )p(x|C )
1 + p(C 21 )p(x|C 21 )
0.5
0
-4 -3 -2 -1 0 1 2 3 4
x
Posons :
p(x|C 1 ) p(C 1 )
µ ¶ µ ¶
f (x) = log + log
p(x|C 2 ) p(C 2 )
Ainsi :
e f (x) 1
p(C 1 |x) = =
1 + e f (x) 1 + e − f (x)
1
La fonction définie sur R par σ(t ) = 1+e −t
est appelée fonction logistique (ou sigmoïde),
et est représentée par la figure 6.2.
x classé dans C 1 si f (x) > 0 (c’est-à-dire p(C 1 |x) = σ( f (x)) > 1/2)
½
x classé dans C 2 si f (x) < 0 (c’est-à-dire p(C 2 |x) = 1 − p(C 1 |x) = σ(− f (x)) > 1/2)
La fonction f étant affine, les deux classes sont donc séparées par un hyperplan de Rd .
Au passage, lorsque p(x|C 1 ) et p(x|C 2 ) sont des distributions gaussiennes de même ma-
trice de covariance Σ, la fonction f est bien affine, ceci n’est pas une hypothèse simplifica-
1
trice. En effet, si p(x|C k ) = (2π)d /21 |Σ|1/2 e − 2 (x−µk ) Σ (x−µk ) pour k = 1 ou k = 2, alors :
T −1
p(C 1 )
µ ¶
1 T −1 1 T −1
f (x) = − (x − µ1 ) Σ (x − µ1 ) + (x − µ2 ) Σ (x − µ2 ) + log
2 2 p(C 2 )
p(C 1 )
µ ¶
1 T −1 T −1 1 T −1 T −1
= − µ1 Σ µ1 + x Σ µ1 + µ2 Σ µ2 − x Σ µ2 + log
2 2 p(C 2 )
³ ´
p(C 1 )
d’où f (x) = β0 + β1 · x avec : β0 = 21 µT2 Σ−1 µ2 − 21 µT1 Σ−1 µ1 + log p(C 2 ) et β1 = Σ−1 (µ1 − µ2 )
car p(C 1 |x) = σ( f (x)) = e f (x) /(1 + e f (x) ) donc log(p(C 1 |x)) = f (x) − log(1 + e f (x) ) et log(1 −
p(C 1 |x)) = log(1 − σ( f (x))) = − log(1 + e f (x) ).
La fonction L(β0 , β1 ) est concave en (β0 , β1 ) comme somme de fonctions concave : d’une
part les fonctions affines ou nulles (β0 , β1 ) 7→ y n (β0 + β1 · x n ) sont concaves et d’autre part
les (β0 , β1 ) 7→ − log(1 + exp(β0 + β1 · x n )) aussi, pour toute valeur de n. Le maximum de la
vraisemblance conditionnelle est donc unique (voir annexe B.1). Il est donc légitime de par-
ler du classifieur de « la » régression logistique : quelle que soit la manière de maximiser la
vraisemblance conditionnelle, on aboutira toujours aux mêmes paramètres (β0 , β1 ) (aux im-
précisions numériques près). Généralement, c’est un algorithme de montée de gradient qui
est utilisé pour maximiser L(β0 , β1 ) (voir annexe B.3).
Attention au vocabulaire : la régression logistique permet de déterminer β0 et β1 ; le clas-
sifieur de la régression logistique, discuté dans le paragraphe suivant, implémente le principe
du maximum a posteriori sous l’hypothèse p(C 1 |x) = σ(β0 + β1 · x).
x classé dans C 1
½
si f (x) > 0
x classé dans C 2 si f (x) < 0
n
L(β0 , β1 ) =
X
y i log(σ( f (x i ))) + (1 − y i ) log(σ(− f (x i )))
i =1
Lorsqu’on maximise cette fonction, on se rend compte qu’on a tout intérêt à avoir f (x i ) = β0 +
β1 ·x i > 0 lorsque y i = 1 et f (x i ) < 0 lorsque y i = 0, c’est-à-dire, à bien classer les observations.
Par ailleurs, la sigmoïde est peu sensible à l’éloignement de x i au plan d’équation f (x) =
0, car cette fonction admet deux asymptotes (1 en +∞ et 0 en −∞) : les points tels que | f (x)|
est « grand » ont une influence dans l’expression de la log-vraisemblance limitée par cette
propriété. Ce n’est pas le cas dans la régression linéaire : dans ce cas on minimise la norme
au carré d’un résidu, et les observations de résidu élevé vont avoir une forte influence sur
l’estimation des paramètres de la droite cherchée.
Il est possible d’introduire une régularisation dans la régression logistique en contrai-
gnant les valeurs pouvant être prises par les paramètres par l’intermédiaire de la norme eu-
clidienne de β1 . Pour ce faire, il suffit de chercher à minimiser
Pk
p(x|C k ) =
Nk VP (x)
Les probabilités a priori peuvent pour leur part être estimées comme la proportion d’ob-
servations du jeu de données appartenant à une certaine classe :
Nk
p(C k ) =
N
p(C k )p(x|C k ) Pk
p(C k |x) = =
p(x) N VP (x) p(x)
On remarque que seul P k dépend de k. La règle de Bayes consiste donc à classer x dans la
classe C k telle que P k est maximum, c’est-à-dire dans la classe majoritaire parmi les P plus
proches voisins de x.
6.3.3 Discussion
Si cet algorithme est très simple, il présente les mêmes limites que celles discutées pour
l’estimation des distributions de probabilité : problème de la dimension, « densité » des ob-
servations qui doit être suffisante autour de x. . .
On a intérêt à utiliser la classification aux P plus proches voisins avec P « un peu grand »
(P = 5 ? P = 10 ?) de manière à ne pas dépendre uniquement « du » plus proche voisin et limiter
ainsi le sur-apprentissage (en d’autres termes, à augmenter le biais et diminuer la fluctuation
ou la variance, cf section 2.3 au chapitre 2). Néanmoins, plus P est grand, plus VP devient
grand, donc moins on a de chance de respecter l’hypothèse « φ constante sur VP (x) » qui est
à la base de l’estimation des densités. Augmenter P conduit donc à s’écarter du classifieur
idéal de Bayes.
Nous n’avons pas discuté des aspects algorithmiques du problème. La classification aux P
plus proches voisins nécessite de trouver, comme son nom l’indique, les P plus proches voi-
sins d’une nouvelle observation à classifier. Lorsque le jeu de données est grand (N =1 million
d’observations étiquetées ?), il est très coûteux de tester exhaustivement les N observations
pour déterminer les P plus proches de x. Une manière efficace de faire est d’organiser les
observations dans un arbre k-d (k-d tree). Cependant, lorsque la dimension augmente, il se
trouve que la performance d’une recherche par arbre k-d tree se rapproche de celle de la mé-
thode exhaustive : il s’agit encore d’une manifestation de la malédiction de la dimension. Des
algorithmes ont récemment été proposés pour chercher des plus proches voisins approchés
(on s’autorise des erreurs dans la liste des P plus proches voisins), ou de manière adaptée à
la recherche dans un espace de grande dimension, voir le paragraphe 6.5.
Au delà des classifieurs linéaires On peut se demander pourquoi chercher des surfaces
séparatrices sous forme d’hyperplan plutôt que sous forme d’une surface quadratique, ou
d’une autre nature géométrique. Une réponse sera donnée dans le chapitre suivant : lorsque
les observations appartiennent à un espace de grande dimension, il sera « facile » de séparer
les classes par un simple hyperplan. Un classifieur linéaire étant défini par un produit sca-
laire, on verra également qu’il est possible de le rendre non-linéaire par l’astuce du noyau.
Il y a toutefois des situations où il est utile d’imposer la géométrie de la surface de sépa-
ration. Il est possible de choisir une surface a priori : on verra par exemple que le choix d’un
noyau judicieux permet de s’assurer que les surfaces sont quadratiques. En général, on n’im-
pose pas la surface en elle-même (comment choisir sa nature géométrique a priori ?) mais on
fait plutôt des hypothèses dans le cadre d’un modèle probabiliste des observations. Nous ne
développerons pas ce point de vue dans le cours, mais nous allons discuter rapidement un
exemple.
Plaçons-nous dans le cadre d’un problème de classification biclasse pour des observa-
tions de Rd , dans lequel on modélise chaque vraisemblance p(x|C k ) (k ∈ {1, 2}) par une loi
gaussienne de moyenne µk et matrice de covariance Σk . Le principe du maximum a poste-
riori associe une observation x à la classe C 1 si :
1 1 1 1
e − 2 (x−µ1 ) Σ1 (x−µ1 ) > p(C 2 ) p e − 2 (x−µ2 ) Σ2 (x−µ2 )
T −1 T −1
p(C 1 ) p
d
(2π) |Σ1 | d
(2π) |Σ2 |
soit, en passant au logarithme :
K 1 − (x − µ1 )T Σ1 (x − µ1 ) > K 2 − (x − µ2 )T Σ2 (x − µ2 )
hyperboles, et des cas dégénérés comme les droites, voir annexe A.3 (on sait déjà que le maxi-
mum a posteriori conduit à un classifieur linéaire pour des matrices de covariances bien
choisies, voir Section 6.2). D’autres modèles probabilistes induiraient des séparations de géo-
métrie encore différente.
Recherche efficace des plus proches voisins Concernant la recherche des plus proches voi-
sins, de manière approchée ou en grande dimension, l’article suivant :
M. Muja and D. Lowe, Scalable Nearest Neighbor Algorithms for High Dimensional Data, IEEE
Transactions on Image Processing, vol. 36, no. 11, p. 2227-2240, 2011
ainsi que la très utile bibliothèque FLANN (Fast Library for Approximate Nearest Neighbors) :
https://github.com/flann-lib/flann
font référence.
La probabilité que la majorité des classifieurs prédise la mauvaise classe est donc :
à !
N N k
p (1 − p)N −k
X
k=⌈N /2⌉ k
Si m = ⌈N /2⌉ et p < 1/2, la condition d’application de l’inégalité est bien vérifiée et on déduit :
à !
N N k 2
p (1 − p)N −k É e −2N (p−1/2)
X
k=⌈N /2⌉ k
Ce majorant décroît effectivement très vite lorsque N croît dès que p < 1/2.
On a donc tout intérêt à associer des classifieurs faibles pour en faire un classifieur fort.
Attention néanmoins, le classifieur fort construit ici en choisissant la classe majoritaire parmi
les classes prédites par les classifieurs faibles n’a l’assurance d’obtenir de bonnes perfor-
mances que si les classifieurs faibles fournissent des réponses statistiquement indépendantes.
Dans le cas contraire, notre calcul n’est plus valable.
Associer les réponses de classifieurs faibles pour construire un classifieur fort est l’objet
des « méthodes ensemblistes ». Nous discutons à présent les deux grandes familles de mé-
thodes ensemblistes, les approches de type bagging et de type boosting.
classifieur est majoré par la somme du biais (l’erreur de prédiction minimale que peut réa-
liser tout classifieur de cette famille) et de la fluctuation (une grande fluctuation peut nous
mettre en situation de sur-apprentissage).
Le bagging est généralement bien adapté aux méthodes d’apprentissage à forte fluctua-
tion. En effet, dans ce cas chaque classifieur faible entraîné sur un échantillon bootstrap peut
présenter du surapprentissage, donc fortement dépendre de l’échantillon bootstrap, mais le
vote pour la prédiction majoritaire lissera la dépendance du classifieur fort à la base d’ap-
prentissage originale. Par contre, le bagging ne permet pas de réduire le biais, qui est indé-
pendant de la base d’apprentissage.
Les forêts aléatoires (random forests) sont une application du bagging aux arbres de déci-
sion considérés comme classifieurs faibles.
Les arbres de décision permettent de faire une prédiction (une classe dans notre cas
d’étude) à partir de décisions successives portant sur les caractéristiques d’une observation.
Les arbres de décision sont très populaires car, contrairement à beaucoup des méthodes
de l’apprentissage automatique, il est possible d’interpréter les décisions fournies. En effet,
ces décisions résultent de la succession de décisions élémentaires sur chaque caractéristique
de l’observation dont on cherche à prédire la classe. On parle de « boîte blanche », par opposi-
tion à une « boîte noire ». Il s’agit d’une méthode ancienne, développée dans les années 1960.
Les médecins (ou garagistes !) utilisent des arbres de décision de manière routinière : la tem-
pérature est-elle supérieur à 37.5° ? si oui, le rythme cardiaque est-il inférieur à 40bpm ? etc.,
la conclusion de ces tests diagnostiques étant telle ou telle pathologie. La figure 7.2 donne
un exemple d’arbre de décision pour un problème de classification d’observations bidimen-
sionnelles.
On dispose d’algorithmes permettant de construire un arbre de décision à partir d’un
ensemble d’observations, par exemple l’algorithme CART (classification and regression trees)
que nous allons décrire. CART construit des arbres binaires de décision : chaque décision
est « oui » ou « non », autrement dit avec le vocabulaire de la théorie des graphes, chaque
nœud de l’arbre a deux enfants, à l’exception des feuilles. Il s’agit d’un algorithme récursif,
qui construit successivement les règles de décision binaires. Chaque règle sera de la forme
« x i < T ? » où x i est une des caractéristiques de l’observation testée et T un seuil à déterminer.
CART est basé sur un critère de segmentation. Un critère de segmentation est une valeur
K
X
C =− p k log(p k )
k=1
— le critère de Gini :
K
X
C= p k (1 − p k )
k=1
profondeur=4 profondeur=5
classées. Les arbres de décision sont également représentés : on indique la règle de décision,
la valeur du critère de segmentation (critère de Gini), ainsi que le nombre total d’observa-
tions (samples) et le nombre d’observation de chaque classe (value) dans les sous-arbres
du nœud courant. La couleur d’un nœud indique la classe majoritaire dans le sous-arbre.
Notons que le critère d’arrêt impose qu’une branche s’arrête de « pousser » dès qu’elle ne
contient plus que des observations d’une seule classe.
On a déjà dit que l’interprétabilité des décisions expliquait le succès des arbres de dé-
cision. Néanmoins les règles de décision générées dépendent fortement de la base d’obser-
vations. En effet, dans CART, les seuils sont choisis parmi les valeurs prises par les caracté-
ristiques. Par ailleurs, les décisions se font uniquement sur les caractéristiques : dans le cas
d’observations de R2 , la surface de séparation est une union de segments parallèles à l’un
ou l’autre des axes. Cette manière de définir l’arbre de décision peut être largement sous-
optimale. Pensez par exemple à des observations dans le plan appartenant à deux classes sé-
parées par une droite penchée à 45 degrés : de nombreuses décisions sur les caractéristiques
peuvent être nécessaires alors qu’une seule décision combinant linéairement les caractéris-
tiques serait nécessaire.
Les arbres de décision sont susceptibles de fortement dépendre des observations d’ap-
prentissages. Cette famille de classifieur a donc probablement une forte fluctuation : la tech-
nique du bagging est par conséquent toute indiquée.
Comme on l’a déjà dit, cette technique est censée bien fonctionner lorsque les classi-
fieurs faibles ont des probabilités d’erreur indépendantes, ce qui motive l’échantillonnage
bootstrap. Dans le cas des arbres de décision, on introduit un aléa supplémentaire dans l’al-
gorithme de construction expliqué précédemment, en choisissant au hasard m caractéris-
tiques parmi les d disponibles pour calculer les valeurs du critère de segmentation, à la place
de toutes les caractéristiques disponibles.
L’algorithme de classification de la forêt aléatoire (random forest) consiste à construire
de tels arbres de décision aléatoires à partir d’échantillons bootstrap, puis à sélectionner la
classe majoritaire parmi les classes prédites par ces classifieurs faibles. On parle aussi de forêt
d’arbres aléatoires. La figure 7.4 montre un exemple de classification par forêt aléatoire.
Remarquons que l’on perd l’interprétabilité des résultats des arbres de décision : les forêts
aléatoires sont, elles, des « boîtes noires ».
Les principaux paramètres à régler sont le nombre d’arbres dans la forêt, le nombre de
caractéristiques sélectionnées aléatoirement dans la construction des arbres de décision, le
critère de segmentation, et la méthode d’élagage des arbres de décision. Pour fixer les idées,
7.3.1 Adaboost
L’exemple le plus connu de méthode de type boosting est sans doute Adaboost (pour
ADAptive BOOsting). Il s’agit d’une technique générale pour construire un classifieur fort à
partir de classifieurs faibles. Supposons que l’on dispose d’une famille de classifieurs faible H .
1. Voir A. Criminisi, J. Shotton, E. Konukoglu, Decision forests for classification, regression, density es-
timation, manifold learning and semi-supervised learning, Microsoft Research technical report TR-2011-
114. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/decisionForests_
MSR_TR_2011_114.pdf
rifie :
K 0 = C 0 est le classifieur de H minimisant
où αm > 0. La règle de décision pour le classifieur ensembliste associé à K m est comme sou-
vent d’associer une observation x à la classe -1 si K m (x) < 0 et à la classe 1 si K m (x) > 0.
Remarquons que le classifieur ensembliste obtenu n’appartient pas a priori à la famille de
classifieurs faibles H . Nous espérons ainsi diminuer le biais d’apprentissage de la famille H .
La question est de savoir comment choisir les poids αm et les classifieurs h m à chaque
étape, de manière à obtenir un classifieur fort intéressant après quelques étapes. Nous allons
faire les choix de manière à minimiser un risque empirique calculé sur la base d’apprentis-
sage. Dans Adaboost, on introduit le risque empirique du classifieur K m associé à une fonc-
tion de perte exponentielle (exponential loss) :
N
e −y i K m (xi )
X
Em =
i =1
Il s’agit bien d’une fonction de perte valide : e −y i K m (xi ) est plus grand lorsque y i et K m (x i ) ont
des signes différents (erreur de prédiction de K m ) que lorsque y i et K m (x i ) ont même signe
(prédiction correcte). Le choix d’une fonction de perte exponentielle va permettre de mener
à bien les calculs suivants. Il est possible d’utiliser une perte logistique (voir section 8.4.1 au
chapitre 8), conduisant à l’algorithme LogitBoost.
Par définition de K m :
N N
e −y i (K m−1 (xi )+αm hm (xi )) = w im e −y i αm hm (xi )
X X
Em =
i =1 i =1
où w im = e −y i K m−1 (xi ) .
Comme y i h m (x i ) = 1 si h m (x i ) = y i et y i h m (x i ) = −1 si h m (x i ) ̸= y i , on peut séparer dans
l’expression de E m les observations bien et mal classées par le classifieur h m et écrire :
w im e −αm + w im e αm
X X
Em =
i t.q. h m (x i )=y i i t.q. h m (x i )̸= y i
soit : Ã !
N
w im + w im
−αm
X X ¡ 2α ¢
Em = e e m −1
i =1 i t.q. h m (x i )̸= y i
On voit que seule la seconde somme dépend du choix de h m . Minimiser E m sur l’en-
semble des classifieurs faibles H revient donc à minimiser ce terme (car on verra que e 2αm −
1 > 0). On sélectionne donc le classifieur faible h m qui minimise : i t.q. hm (xi )̸= y i ) w im , c’est-à-
P
tout i puisque la somme à minimiser est alors proportionnelle au nombre d’observations mal
classées.
Il faut également choisir le poids αm . On minimise E m par rapport à αm en annulant la
dérivée. Comme :
∂E m
= −αm e −αm w im + αm e αm w im
X X
∂αm i t.q. h m (x i )=y i i t.q. h m (x i )̸= y i
m
ÃP !
1 i t.q. h m (x i )=y i ) w i
αm = log P m
2 i t.q. h m (x i )̸= y i ) w i
Nous avons donc une stratégie pour choisir un classifieur h m et mettre à jour son poids αm .
Concernant la mise à jour des poids des observations w i ,m , on remarque que, par définition
de K m :
w im+1 = w im e αm
½
si h m (x i ) ̸= y i :
si h m (x i ) = y i : w im+1 = w im e −αm
Dans les implantations logicielles, on normalise les poids à chaque étape de manière à ce que
PN m
i =1 w i = 1 pour éviter des problèmes d’instabilité numérique.
En notant εm = i t.q. hm (xi )̸= y i w im le coût des erreurs, si les poids sont normalisés on a
P
1 − εm
αm =
2εm
1−εm
Au passage, e 2αm − 1 = e εm − 1 > 0. L’algorithme Adaboost s’écrit donc de la manière sui-
vante :
Initialisation : ∀ 1 É i É N , w i0 = 1/N .
Pour m = 0 à M ,
1. sélectionner le classifieur faible h m dans H minimisant le coût des erreurs
εm = w im
X
i t.q. h m (x i )̸= y i
1 − εm
αm =
2εm
w im+1 = w im e αm
½
si h m (x i ) ̸= y i :
∀1 É i É N,
si h m (x i ) = y i : w im+1 = w im e −αm
PN m+1
les normaliser tels que i =1 w i =1
4. revenir en 1.
Le nombre d’étapes M est fixé par l’utilisateur : une trop grande valeur de M peut conduire
à un sur-apprentissage.
Dans Adaboost, les observations sont « stimulées » (boosted) par la mise à jour des poids :
une observation correctement classée par h m à un poids qui diminue à l’étape m + 1 (car
e −αm < 1) et une observation mal classée à un poids qui augmente (car e αm > 1). Le classi-
fieur faible h m+1 est donc choisi pour se focaliser sur les observations mal classées par les
classifieurs faibles précédents.
Le classifieur obtenu par Adaboost combine les classifieurs faibles par un vote pondéré de
leurs prédictions. Plus un classifieur faible est performant (εm faible), plus son poids est élevé
(αm grand). Par comparaison, le bagging combine les réponses par un vote non pondéré.
Nous avons décrit le principe de base d’Adaboost : de nombreuses variantes existent,
ainsi qu’une bibliographie foisonnante sur les propriétés théoriques.
Adaboost est souvent utilisé avec des arbres de décisions comme famille H de classi-
fieurs faibles, ce qui permet de résoudre l’étape 1 de l’algorithme en un temps raisonnable.
Pour ce faire, il suffit de prendre comme critère de segmentation le coût des erreurs. Un choix
très répandu est même d’utiliser des « souches de classification » (decision stumps) qui sont
des arbres de décision de profondeur 1. Ce sont donc des classifieurs qui se contentent de
tester si une caractéristique de l’observation est inférieure à un seuil.
Adaboost a rencontré de nombreux succès dans des applications diverses. Il est par exemple
utilisé dans l’algorithme de Viola-Jones de détection d’objets (en particulier de visages) dans
les images, qui peut fonctionner en temps réel avec de bonnes performances. 2
La figure 7.6 montre un exemple de classification par Adaboost.
2. Voir les exemples dans l’article original : P. Viola, M. Jones, Robust real-time object detection, International
Journal of Computer Vision, 57(2), p. 137-154, 2004.
N
ℓ(y i , K m (x i ))
X
Em =
i =1
N
ℓ(y i , K m−1 (x i ) + αm h m (x i ))
X
Em =
i =1
N N ∂ℓ
ℓ(y i , K m−1 (x i )) + αm
X X
≃ (y i , K m−1 (x i ))h m (x i )
i =1 i =1 ∂y
N ∂ℓ
= E m−1 + αm
X
(y i , K m−1 (x i ))h m (x i )
i =1 ∂y
∂ℓ
où ∂ydésigne la dérivée partielle de ℓ par rapport à sa deuxième composante.
Pour minimiser E m en suivant la plus forte pente, il faut donc :
PN ∂ℓ
— choisir h m dans la classe H de manière à minimiser − i =1 ∂y (y i , K m−1 (x i ))h m (x i ) qui
est un produit scalaire entre vecteurs de dimension N ,
— choisir αm > 0 minimisant E m (problème d’optimisation 1D, cf line search dans les
algorithmes de descente).
Selon le choix de la fonction de perte ℓ, le gradient boosting s’adapte à des problèmes de
classification ou de régression.
XGBoost (eXtreme Gradient Boosting), « extrêmement » populaire parmi les participants
aux défis Kaggle pour ses très bonnes performances pratiques, est un exemple de gradient
boosting où les classifieurs faibles sont des arbres de décision ou de régression, qui consiste
à utiliser une approximation d’ordre 2 plutôt que d’ordre 1 dans la minimisation, ainsi qu’un
terme de régularisation afin d’éviter le surapprentissage. Plus de détails ici :
T. Chen, C. Guestrin. XGBoost : A scalable tree boosting system. Proceedings of the ACM Inter-
national Conference on Knowledge Discovery and Data Mining (SIGKDD), 2016.
L’implémentation de référence est là :
https://github.com/dmlc/xgboost
Dans notre cours, nous discutons des classifieurs linéaires comme le classifieur de la ré-
gression logistique au chapitre 6, ou le perceptron de Rosenblatt dans le prochain chapitre.
Dans le cas biclasse, la surface de séparation est un hyperplan de l’espace des observations.
Lorsque les deux classes sont bien séparées (sans erreur) par un tel hyperplan, on dit qu’elles
sont linéairement séparables. Ce chapitre traite des machines à vecteurs supports (Support
Vector Machines, SVM), dont la version la plus simple fait également partie de la famille
des classifieurs linéaires. Elles se prêtent bien à l’« astuce du noyau » qui leur permettent de
s’adapter à des données non linéairement séparables. Les SVM à noyau sont les classifieurs
phares de la fin des années 1990 et début des années 2000 et ont rencontré de nombreux
succès. Elles sont toujours utilisées, en particulier lorsqu’on dispose de données en quantité
limitée.
Démonstration
En effet, le point de l’hyperplan le plus proche de x ∗ est sa projection orthogonale, qui
CHAPITRE 8. MACHINES À VECTEURS SUPPORTS 102
s’écrit sous la forme x ∗ + λw où λ ∈ R car w est orthogonal à l’hyperplan. Comme cette pro-
jection appartient à l’hyperplan, λ vérifie w · (x ∗ + λw ) + b = 0, soit λ = −(b + w · x ∗ )/||w ||22 .
Ainsi, la distance d’un point x ∗ à sa projection orthogonale est ∥x ∗ + λw − x ∗ ∥2 = |λ| ∥w ∥2 =
|w · x ∗ + b|/∥w ∥2 . □
Notons que si les deux classes sont linéairement séparables, la solution de ce problème
de maximisation est bien un hyperplan séparateur car les hyperplans qui ne sont pas sépa-
rateurs sont tels que minn y n (w · x n + b) < 0 (car au moins un point n’est pas correctement
classé), au contraire des hyperplans séparateurs pour lesquels minn y n (w · x n + b) Ê 0 pour
tout n.
Le séparateur de plus grande marge définit un classifieur : si w · x + b > 0 alors l’observa-
tion x est classée dans 1, et dans −1 sinon.
Les observations x n qui réalisent le minimum dans minn y n (w ·x n +b) sont appelés « vec-
teurs de support » ou « vecteurs supports ». On reviendra sur cette notion plus tard.
Les séparateurs à vaste marge, dont SVM est l’acronyme en français, ainsi définis sont
appelés machines à vecteurs supports (support vector machines, SVM).
Marge, hyperplan séparateur et vecteurs supports sont illustrés par la figure 8.1.
arg min 1 ∥w ∥2
2
(primal 1) w ,b 2
sous contraintes : ∀ 1 É n É N , y n (w · x n + b) Ê 1
Ce problème est qualifié de primal. Notons que chaque observation étiquetée (x n , y n ) induit
une contrainte.
F IGURE 8.1 – Discrimination entre deux classes : marge d’une droite séparatrice d’équation
w · x + b = 0 et vecteurs supports entourés.
Il s’agit d’un problème convexe (voir annexe B.1), appartenant à la famille des problèmes
de programmation quadratique car la fonction objectif est quadratique et les contraintes sont
linéaires. Le problème admet donc une unique solution.
Nous allons exprimer le dual de ce problème d’optimisation sous contraintes.
Dans le problème (primal 1), la fonction objectif et les contraintes sont convexes et diffé-
rentiables. On peut donc appliquer les résultats de l’annexe B.2 sur la dualité de Wolfe.
Dans le problème des SVM, (w , b) joue le rôle de la variable x de l’annexe B.2, les contraintes
sont g n (x) = −(y n (w · x n + b) − 1), et le Lagrangien est :
1 N
L(w , b, λ) = ∥w ∥22 − λn (y n (w · x n + b) − 1)
X
2 n=1
D’après les conditions Karush, Kuhn et Tucker (KKT), nécessaires et suffisantes ici, (w ∗ , b ∗ )
est solution optimale du primal si et seulement s’il existe λ∗ = (λ1 , λ2 , . . . , λN ) où ∀1 É i É
N , λi Ê 0, tel que (w ∗ , b ∗ ) vérifie :
∀ 1 É n É N , λ∗n (y n (w ∗ · x n + b ∗ ) − 1) = 0
∂L ∂L
et λ∗ maximise L(w ∗ , b ∗ , λ) sous les contraintes ∂w = 0 et ∂b = 0, ce qui est respectivement
équivalent à
N
w∗ = λn y n x n
X
n=1
et
N
λn y n = 0
X
n=1
On obtient :
° °2 Ã ÃÃ ! ! !
1° N ° N N
∗ ∗ ∗
L(w , b , λ) = ° λn y n x n ° − λ y λ y x · xn + b − 1
°X ° X X
2 °n=1 ° n=1 n n m=1 m m m
2
Or : ° °2
°XN ° N X N
λn y n x n ° = λn λm y n y m x n · x m
° ° X
°
°n=1 ° n=1 m=1
2
et :
à Ãà ! ! !
N N N
N X N N
∗
λn y n λm y m x m · x n + b λn λm y n y m x n · x m + b λn y n − λn
X X X X X
−1 =
n=1 m=1 n=1 m=1 n=1 n=1
PN
Comme n=1 λn y n = 0, on simplifie l’expression du Lagrangien en :
N 1 XN X N
L(w ∗ , b ∗ , λ) = λn − λn λm y n y m x n · x m
X
n=1 2 n=1 m=1
8.1.3 Résumé
Le problème primal des SVM s’écrit :
arg min 1 ∥w ∥2
2
(primal 1) w ,b 2
sous contraintes : ∀ 1 É n É N , y n (w · x n + b) Ê 1
Dans les deux cas, il s’agit de programmes quadratiques. Le primal admet d +1 inconnues
et N contraintes, le dual N inconnues et une contrainte en plus des contraintes de signes sur
les λn .
Résoudre le problème dual nous fournit λ∗ , ensuite on déduit w ∗ par l’expression :
N
w∗ = λ∗n y n x n
X
n=1
où les termes non nuls dans cette somme sont ceux relatifs aux vecteurs supports. Les ob-
servations qui ne sont pas vecteurs supports ne participent pas à la définition de l’hyperplan
optimal. Ce résultat est cohérent avec l’interprétation géométrique du problème : sur la fi-
gure 8.1, la position des observations qui ne sont pas des vecteurs supports n’influence pas
la position du séparateur de plus grande marge.
Enfin, on calcule b ∗ à partir des vecteurs supports sachant que pour tout vecteur sup-
port, w ∗ · x n +b ∗ = y n . On peut bien estimer numériquement b ∗ , par exemple en calculant la
moyenne sur les vecteurs supports x n des valeurs de y n − w ∗ · x n .
F IGURE 8.2 – SVM : marge souple et variables d’écart. Notons les valeurs prises par ξi selon la
position de l’observation x i par rapport à la droite de séparation. Ici, f (x) = w · x + b.
1 N N N
L(w , b, ξ, λ, µ) = ∥w ∥2 +C ξn − λn (y n (w · x n + b) − 1 + ξn ) − µn ξn
X X X
2 n=1 n=1 n=1
où pour tout n, λn Ê 0 et µn Ê 0.
1 N
L(w , b, λ, µ) = ∥w ∥2 − λn (y n (w · x n + b) − 1)
X
2 n=1
On remarque que la seule différence avec le problème (dual 1) est la borne supérieure
des λn , égale à C . L’introduction des variables d’écart agit comme une régularisation : on
contraint l’espace des solutions possibles du dual.
supports (qui sont tels que λn ̸= 0), pour lesquels la contrainte correspondante est saturée,
ce qui s’écrit : y n (w · x n + b) = 1 − ξn . Ainsi, les vecteurs supports sont les observations x n
vérifiant :
Une remarque très importante à ce stade est que le problème dual ne fait apparaître les
observations que par l’intermédiaire de produits scalaires x n · x m . Ceci justifie l’introduction
de « l’astuce du noyau ».
D’une part, le problème dual des SVM (à marge dure ou souple) ne fait intervenir les
observations que par l’intermédiaire de leur produit scalaire.
D’autre part, nous allons voir que des problèmes de classification non linéairement sé-
parables peuvent le devenir lorsqu’on plonge les observations dans un espace vectoriel de
dimension plus grande que l’espace initial.
Ces deux remarques justifient la mise en œuvre de « l’astuce du noyau » (kernel trick), qui
permet de transformer les machines à vecteurs supports en classifieurs non-linéaires.
F IGURE 8.3 – Séparation de points du plan par une droite. Trois points sont toujours séparables
quelles que soient les étiquettes. Par contre, certains quadruplets ne sont pas séparables, comme
montré à droite.
Le fait que les d vecteurs (x n − x d +1 ) forment une famille libre est le pendant de la condition
« les points ne sont pas alignés » dans l’exemple de la figure 8.3 en dimension 2.
Démonstration
Notons A la matrice dont les colonnes sont formées des vecteurs x n − x d +1 . La matrice A
admet une décomposition A = QR, où Q est une matrice orthogonale et R une matrice trian-
gulaire supérieure, inversible comme A.
Considérons alors la fonction f affine en x d’équation :
d ¢T
(y n − y d +1 ) R −1 (x n − x d +1 ) R −1 (x − x d +1 ) + y d +1
X ¡
f (x) =
n=1
Donc pour tout n entre 1 et d + 1, f (x n ) = y n . L’hyperplan d’équation f (x) = 0 sépare bien les
points, quelles que soient les valeurs des étiquettes. □
Il est possible de démontrer que pour tout ensemble de d +2 points de Rd , certaines affec-
tations d’étiquettes rendent impossible la séparation, comme dans l’exemple de la figure 8.3
pour d = 2. Au passage, et sans entrer dans les détails, ces deux propriétés permettent d’af-
firmer que la dimension de Vapnik-Chervonenkis (évoquée au chapitre 2, section 2.3) des
hyperplans de Rd est d + 1.
Il est donc plus « facile » de séparer linéairement deux classes lorsque la dimension est
grande, en particulier lorsque la dimension est supérieure au nombre d’observations. On
peut également interpréter la proposition 8.1 comme une justification de l’utilisation des
classifieurs linéaires (régression logistique, perceptron de Rosenblatt, SVM linéaire) lorsque
les observations appartiennent à un espace de grande dimension, comme dans le cas de la
classification de textes ou d’images.
La figure 8.4 illustre d’une autre manière cette propriété : des observations non linéaire-
ment séparables le deviennent lorsqu’on les plonge dans un espace vectoriel de dimension
supérieure.
L’« astuce du noyau » (kernel trick) utilisée dans les SVM fait qu’on n’aura pas besoin de
déterminer explicitement le plongement φ, on aura seulement besoin des valeurs des pro-
duits scalaires φ(x) · φ(y).
douce qui introduit les écarts à la marge (et permet des erreurs de classifications) afin d’éviter
le sur-apprentissage.
Nous avons établi plus haut la formulation duale de la SVM séparant les observations une
fois celles-ci plongées dans H par φ :
N 1 XN X N
λn − λn λm y n y m φ(x n ) · φ(x m )
X
arg max
(dual 2’) λ n=1 2 n=1 m=1
sous contraintes : ∀1 É n É N , 0 É λ É C et PN λ y = 0
n n=1 n n
Remarquons que seuls des produits scalaires φ(x n ) · φ(x m ) apparaissent. Si on définit le
noyau k tel que k(x, y) = φ(x) · φ(y), le problème devient :
N 1 XN X N
λn − λn λm y n y m k(x n , x m )
X
arg max
(dual 3) λ n=1 2 n=1 m=1
sous contraintes : ∀1 É n É N , 0 É λ É C et PN λ y = 0
n n=1 n n
N
λn y n k(x n , x) + b
X
f (x) =
n=1
Notons qu’on n’a pas besoin de l’expression de w , vecteur normal à l’hyperplan séparateur
dans l’espace de redescription, mais seulement de calculer les k(x n , x) pour les vecteurs sup-
ports x n . En dimension d ′ grande, il est bien plus rapide de calculer f (x) grâce au noyau et
aux vecteurs supports (cela nécessite une somme avec autant de termes que de vecteurs sup-
ports, qui sont généralement en nombre limité) qu’en utilisant le calcul explicite du produit
scalaire avec w (qui nécessite au moins d ′ produits).
Que ce soit pour trouver les λn ou ensuite pour classifier de nouvelles observations, nous
n’avons jamais besoin de manipuler φ, mais seulement le noyau k.
Exemple 8.1
Dans l’exemple de la figure 8.4, le plongement s’écrit
φ(x 1 , x 2 ) = (x 1 , x 2 , x 12 + x 22 )
Ainsi, avec x = (x 1 , x 2 ) et x ′ = (x 1′ , x 2′ ) :
Nous avons explicité le plongement φ pour des raisons pédagogiques, mais en règle gé-
nérale on construit un noyau adapté à la nature des données, et le plongement φ dans
F IGURE 8.5 – Exemples de classification obtenues dans un problème biclasse (classe 0 en rouge
et classe 1 en vert) pour quatre valeurs de C . Les vecteurs supports sont marqués d’une étoile.
On indique à chaque fois le nombre de vecteurs supports dans chaque classe ainsi que le score
de classification obtenues sur des observations test (non représentées) qui n’ont pas servi à l’ap-
prentissage. La marge apparaît en clair. Cette expérience illustre qu’un C petit induit un sous-
apprentissage, et un C trop grand un sur-apprentissage. Figure à voir en couleur.
l’espace vectoriel de redescription H n’est pas explicité (souvent ce n’est d’ailleurs pas
facile, et pas informatif) : tout ce dont nous avons besoin est le noyau k.
Exemple 8.2
La figure 8.5 montre des exemples de classifications obtenues avec un noyau RBF (voir la
section suivante) pour différentes valeurs de l’hyperparamètre C .
S’il est vrai qu’on n’a pas besoin de manipuler le plongement φ de Rd vers l’espace de re-
description H mais uniquement le noyau k, on ne peut tout de même pas choisir n’importe
quelle fonction comme noyau : k doit représenter un produit scalaire dans un espace H de
manière à ce que la SVM cherchée soit un séparateur linéaire dans H .
Sans rentrer dans les détails, un noyau vérifiant les conditions suivantes, dites conditions
de Mercer, est valide (c’est-à-dire qu’il permet la représentation d’un produit scalaire dans
un espace de redescription H ).
Proposition 8.2 Soit une fonction k définie sur Rd × Rd à valeur dans R. Si k est continue
symétrique et est telle que pour tout n et tout ensemble de vecteurs x 1 , . . . x n de Rd , la matrice
¡ ¢
symétrique k(x i , x j ) 1Éi , j Én est positive, alors k est un noyau valide.
Rappel (voir annexe A.3) : la matrice carrée d’ordre n (k(x i , x j ))1Éi , j Én est symétrique positive
P
si pour tout n-uplet (c 1 , . . . , c n ), i , j k(x i , x j )c i c j Ê 0.
PN PN
Remarque. Si k est un noyau valide, alors le terme n=1 m=1 λn λm y n y m k(x n , x m ) appa-
raissant dans le problème (dual 3) est positif ou nul, et est une fonction convexe des λn . La
fonction objectif du problème (dual 3) est donc concave et la solution du problème de maxi-
misation est unique. Voir la caractérisation de la convexité pour les fonctions de classe C 2 en
annexe B.1.
Par exemple, lorsque k(x, y) = x · y (produit scalaire canonique), k vérifie bien les condi-
tions de Mercer car la matrice des k(x n , x m ) est une matrice de Gram. Dans ce cas, le plon-
gement φ associé est tout simplement l’identité. Il s’agit du noyau linéaire, et on parle dans
ce cas de SVM linéaire. Bien entendu, il s’agit tout simplement de la solution des problèmes
(primal 2)/(dual 2) introduits précédemment.
Proposition 8.3 Supposons que k 1 et k 2 sont des noyaux valides, c > 0, A une matrice symé-
trique positive, x = (x a , x b ) où x a et x b sont des variables sur E a et E b et k a et k b des noyaux
valides sur ces espaces. Alors :
— k(x, y) = ck 1 (x, y) + k 2 (x, y)
— k(x, y) = x T Ay
— k(x, y) = k 1 (x, y)k 2 (x, y)
— k(x, y) = k a (x a , y a ) + k b (x b , y b )
— k(x, y) = k a (x a , y a )k b (x b , y b )
définissent des noyaux valides.
Il y a un certain nombre d’autres recettes du même type, voir la littérature sur le sujet.
Démonstration
Ce noyau est valide d’après la proposition 8.3. Il est possible de démontrer que l’espace
de redescription a pour dimension d +δ
¡ ¢
δ . □
Un autre noyau populaire sur Rd × Rd est le noyau RBF (Radial basis function, ou noyau
gaussien) :
k(x, y) = exp(−γ∥x − y∥22 )
où γ > 0 est un paramètre.
Il s’agit d’un noyau dit invariant par translation car il s’écrit sous la forme h(x − y) et,
vérifie donc la relation ∀t ∈ Rd , ∀(x, y) ∈ Rd × Rd , k(x + t, y + t) = k(x, y).
Démonstration
Rappelons tout d’abord que si la transformée de Fourier h
b d’une fonction intégrable h est
définie par l’expression : Z
h(ξ) = h(x)e −i x·ξ dx
b
1 X
Z
i (x j −x k )·ξ
X
c j c k h(x j − x k ) = c j c k h(ξ)e
b dξ
2π j ,k
à !
1
Z
i x ·ξ −i x ·ξ
X
= h(ξ)
b c j e j ck e k dξ
2π j ,k
¯ ¯2
1
Z ¯X ¯
= b ¯ c j e i x j ·ξ ¯¯ dξ
h(ξ)
¯
2π ¯ j ¯
Selon cette démonstration, on peut généraliser et dire que tout fonction continue inva-
riante par translation dont la transformée de Fourier est une fonction réelle positive définit
un noyau valide.
On peut démontrer que l’espace de redescription associé au noyau RBF est un espace de
Hilbert, une sorte d’espace vectoriel de dimension infinie, muni d’un produit scalaire.
Les noyaux précédents sont définis sur des observations vectorielles. Il se trouve que l’on
peut également définir des noyaux sur des chaînes de caractères, des ensembles, ou même
des graphes. Les noyaux sur les chaînes de caractères sont particulièrement intéressants dans
le cadre de la bioinformatique. Par exemple, les protéines sont décrites par des séquences
d’acides aminés. Or les protéines de tous les êtres vivants connus ne sont constituées que de
22 acides aminés, représentés par une lettre de l’alphabet : prédire des propriétés de protéine
à l’aide de machines à noyau revient à utiliser des noyaux sur des chaînes de 22 caractères.
SVM avec variables d’écart Comme les écarts ξn vérifient ξn = max{0, 1 − y n (w · x n + b)}, on
peut dire que l’on cherche (w , b) minimisant :
N
∥w ∥2 +C
X © ª
max 0, 1 − y n (w · x n + b)
n=1
Régression logistique On a vu au chapitre 6 (section 6.2), que l’on cherche (β0 , β1 ) maximi-
sant la log-vraisemblance conditionnelle
N
L(β0 , β1 ) =
X
y n log(σ( f (x n ))) + (1 − y n ) log(σ(− f (x n )))
n=1
XN
= log(σ((2y n − 1) f (x n )))
n=1
N
L(β0 , β1 ) = log σ(y n f (x n ))
X ¡ ¢
n=1
soit à minimiser :
N
log 1 + exp(−y n (β0 + β1 · x n ))
X ¡ ¢
n=1
où C > 0.
Fonction de perte Ces classifieurs Adaboost et les trois classifieurs linéaires SVM, régres-
sion logistique, et perceptron)résolvent tous un problème d’optimisation. Ils diffèrent par la
manière dont le coût des erreurs sur la base d’apprentissage est intégré. Dans tous les cas, le
classifieur f fait une erreur sur l’observation étiquetée (x n , y n ) lorsque z n = y n f (x n ) < 0, et le
coût d’une erreur est défini par la fonction de perte (loss function) ℓ comme suit :
— SVM : ℓ(z) = max {0, 1 − z} (on parle de hinge loss, perte « charnière ») ;
— Régression logistique : ℓ(z) = log 1 + exp(−z) (logistic loss, perte logistique) ;
¡ ¢
3
0-1 loss
square loss
hinge loss
2.5
logistic loss
exponential loss
perceptron loss
2
loss
1.5
0.5
0
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
z
F IGURE 8.6 – Comparaison des fonctions de perte : z < 0 correspond à une observation mal
classée, z > 0 à une observation bien classée.
ℓ(z) = ∥1 − z∥22
Cette fonction n’est pas adaptée aux problèmes de classification car elle donne une valeur
très élevée aux observations trop mal classées (z << 0) ou trop bien classées (z >> 0) qui de-
viennent alors des observations influentes (voir la discussion du chapitre 1 et dans un cours
de statistique). Ce coût est utilisé dans les problèmes de régression mais dans ce cas il faut
tout de même discuter les observations influentes ou aberrantes, voir le cours de statistique.
Les fonctions de perte de la SVM (hinge loss), d’Adaboost (exponential loss) et de la régres-
sion logistique (logistic loss) présentent des graphes similaires, avec une limite nulle lorsque z
tend vers l’infini. Comparée aux SVM, la régression logistique est un peu plus sensible aux
observations mal classées et aux observations « trop bien classées » qui sont alors des obser-
vations influentes, dans une mesure certes moindre que pour le coût quadratique. Les SVM
ne dépendent pas du tout des données bien classées au delà du bord de la marge, car le hinge
loss est nul pour z > 1. Adaboost pénalise les observations bien classées de la manière sem-
blable à la régression logistique, mais pénalise bien plus les observations mal classées.
Les classifieurs linéaires fournissent un hyperplan séparateur entre les classes, défini de
manière unique dans le cas de la régression logistique ou des SVM. Cet hyperplan diffère
d’un modèle à l’autre car il n’est pas solution du même problème d’optimisation. Une SVM
présente l’avantage de séparer les deux catégories « au maximum », mais la régression logis-
tique fournit des probabilités a posteriori, ce qui est intéressant pour certains problèmes.
Attention néanmoins, ces probabilités sont basées sur une modélisation parfois peu réaliste,
comme discuté en section 6.2 du chapitre 6.
Les considérations précédentes nous permettent de donner un guide de choix des mo-
dèles discutés dans ce cours.
Si la dimension du problème est grande par rapport au nombre d’observations, un classi-
fieur linéaire est possible (car on sait qu’il est « facile » de séparer les classes par un hyperplan
en grande dimension) : SVM linéaire ou régression logistique peuvent être envisagées. La
SVM linéaire peut être préférée à la régression logistique pour les raisons précédemment évo-
quées (dépendance uniquement aux vecteurs supports, qui vérifient z < 1 dans la figure 8.6).
Néanmoins les probabilités estimées par la régression logistique peuvent être utiles, notam-
ment en cas d’observations proches de la surface de séparation entre les classes, pour les-
quelles on aimerait avoir une indication de confiance. Par ailleurs, on peut tout de même
questionner la pertinence d’un problème de classification dans lequel le nombre d’obser-
vations est faible par rapport à la dimension, en raison de la malédiction de la dimension
(cf. problème de Hughes au paragraphe 2.1.4). Il serait sans doute plus pertinent de réduire
la dimension du problème au préalable, plutôt que chercher à classifier les observations
« brutes ».
Dans le cas où les classes ne sont pas linéairement séparables, une SVM à noyau est à
favoriser. Le noyau RBF donne souvent de bons résultats lorsque les observations sont vec-
torielles. Adaboost avec des troncs de décision comme classifieurs faibles est une méthode
assez appréciée en pratique. Bien entendu, on ne sait pas a priori si un problème donné cor-
respond à des classes linéairement séparables.
Dans tous les cas, les réseaux de neurones artificiels du prochain chapitre représentent
généralement une solution convenable, mais la convergence de l’apprentissage peut être
lente et les hyperparamètres peuvent être délicats à fixer.
Dans le cadre de la régression à vecteurs supports, nous cherchons f qui induit un écart
d’au plus ε entre prédictions et étiquettes : les (x n , y n ) doivent être dans un « tube » de rayon ε
autour des prédictions (x, f (x)) (appelé ε-tube). De plus, nous cherchons la relation affine f
la plus « plate » possible, c’est à dire avec la plus petite valeur de w . Cela signifie que dans
le cas où les observations x n sont réelles, on cherche la droite de régression de pente la plus
petite possible satisfaisant la contrainte.
Nous sommes donc amenés à résoudre le problème d’optimisation suivant :
arg min 1 ∥w ∥2
2
w ,b 2
sous contraintes : ∀ 1 É n É N , |y n − (w · x n + b)| É ε
Ce problème n’ayant pas forcément de solution réalisable lorsque ε est trop petit, on in-
troduit des écarts E n Ê 0 tels que :
0 si |y n − (w · x n + b)| É ε
½
En =
|y n − (w · x n + b)| − ε sinon
afin de relaxer les contraintes.
Cela nous conduit à minimiser en fonction de w , b, et les E n la fonction :
1 N
∥w ∥22 +C
X
En
2 n=1
N
1 2
(ξn + ξ∗n )
X
arg min ∥w ∥2 +C
w ,b,ξ,ξ∗ 2
(primal SVR) n=1 où ξ =
sous contraintes : ∀ 1 É n É N , y n − w · x n + b É ε + ξn
∀ 1 É n É N , w · x n + b − y n É ε + ξ∗n
(ξ1 , . . . , ξn ) et ξ = (ξ1 , . . . , ξn ).
∗ ∗ ∗
La figure 8.8 montre comment interpréter les variables d’écart. Les vecteurs supports sont
les observations x n telles que (x n , y n ) soit en dehors du ε-tube.
On démontre alors (exactement comme en section 8.1.2 pour le problème de classifica-
tion) que le problème dual associé est :
1 X N N N
∗ ∗ ∗
λ λ ε λ y i (λi − λ∗i )
X X
arg min − (λ − )(λ − ) x · x − (λ + ) +
i j i j i
i j i
λ,λ∗
2 i , j =1 i =1 i =1
(dual SVR) sous contraintes : ∀ 1 É n É N , 0 É λi É C
∀ 1 É n É N , 0 É λ∗i É C
PN
i =1 (λi − λi ) = 0
∗
où seuls les vecteurs supports contribuent. On trouve également la valeur de b à partir des
vecteurs supports.
F IGURE 8.8 – Valeurs possibles pour les variables d’écart selon la position relative des observa-
tions et de la courbe de régression optimale. Cette représentation anticipe un peu la discussion
et l’introduction du noyau pour rendre la prédiction non-linéaire. Trois cas sont possibles à
l’optimum du problème de minimisation sous-contrainte définissant la SVR : soit l’observa-
tion est dans le ε-tunnel et dans ce cas ξn = ξ∗n = 0, soit l’observation est « au-dessus » et ξn > 0,
ξ∗n = 0, soit l’observation est « en-dessous » et ξ∗n > 0, ξn = 0.
Le problème dual ne faisant intervenir les observations que par des produits scalaires,
il est possible d’utiliser l’astuce du noyau pour traiter des problèmes de régression non-
linéaire. Le régresseur obtenu sera de la forme :
N
(λi − λ∗i )k(x i , x) + b
X
f (x) =
i =1
F IGURE 8.9 – Régression à vecteurs supports, noyau RBF. Parmi les observations d’apprentis-
sage, les vecteurs supports sont indiqués comme des cercle, les observations dans le ε-tube (re-
présenté par les lignes pointillées) comme des disques noirs. Rappelons que seuls les vecteurs
supports interviennent dans la définition du régresseur. Première ligne : C = 1, et de gauche à
droite ε = 0.1, 0.5, et 1. Plus ε est grand, moins il y a de vecteurs supports. Seconde ligne : ε = 0.1,
et de gauche à droite C = 0.01, 0.1, et 1. À ε fixé, plus C est grand plus les variables d’écart sont
pénalisées.
menus des restaurants sont les mêmes, seuls les prix des plats sont permutés (les classifieurs
ont des performances différentes sur les problèmes). Pour un client choisissant ses plats au
hasard, il n’y a pas de restaurant meilleur marché qu’un autre, le coût moyen est constant. Il
n’y a pas de choix de restaurant conduisant à un menu gratuit. Autrement dit, il n’y a pas de
classifieur ayant des performances meilleures en moyenne sur tous les problèmes.
Une présentation rigoureuse du no-free-lunch theorem est disponible dans l’article :
D.H. Wolpert, The Supervised Learning No-Free-Lunch Theorems, in Soft Computing and In-
dustry : Recent Applications, p. 25-42, 2002.
Un article de vulgarisation récent montre la difficulté de la recherche du « meilleur » mo-
dèle d’apprentissage et relativise les progrès de certains domaines applicatifs :
M. Hutson, Eye-catching advances in some AI fields are not real, in Science News, May 27, 2020.
https://www.science.org/content/article/eye-catching-advances-some-ai-fields-are-not-real
Régression ridge à noyau La régression ridge (section 1.4.2.2 du chapitre 1) définit la fonc-
tion f (x) = w · x + b (en adoptant les notations du présent chapitre), de telle manière que w
minimise :
N
|y n − b − w · x n |2 + λ||w ||22
X
n=1
N
|y n − b − w · φ(x n )|2 + λ||w ||22
X
n=1
Grâce au matrix inversion lemma aussi appelé identité de Woodbury (demandez à Google) :
(X T X + λI d )−1 X T = λX T (I N − X X T )−1
et donc :
W = X T (X X T + λI N )−1 Y
Ici, X X T est la matrice carrée d’ordre N dont l’élément en ligne i colonne j est φ(x i ) · φ(x j ) =
k(x i , x j ). Notons K = X X T (remarquons que le raisonnement est ici un peu heuristique : si
1. Si b ̸= 0, il faut remplacer λI d par Λ (paragraphe 1.4.2.2 du chapitre 1) dans ce qui suit et l’identité de
Woodbury ne peut pas être utilisée car Λ n’est pas inversible
F IGURE 8.10 – Régression ridge à noyau RBF. Plus C est grand, plus les écarts sont pénalisés et
plus la courbe de régression s’approche des observations. Un C trop faible implique un sous-
apprentissage, un C trop élevé un sur-apprentissage. À comparer à la figure 8.9.
les observations sont plongées dans un espace de Hilbert de dimension infinie, les matrices
W et X ne sont pas définies ; l’important est que K le soit bien, ce qui est le cas car le nombre
d’observations N est fini). On a alors W = X T (K + λI N )−1 Y . Notons que K est symétrique.
Réintégrons la moyenne b des y n . Face à une nouvelle observation x, la fonction f s’éva-
lue alors comme :
on fait apparaître un paramètre C > 0 qui joue un rôle équivalent au paramètre C de la SVR.
La figure 8.10 illustre la régression ridge à noyau sur des observations réelles et le rôle de C .
Machines à noyau Des noyaux peuvent être définis pour des observations qui ne sont pas
facilement représentables sous forme vectorielle, comme des graphes, des chaînes de carac-
tères. . . Par ailleurs, l’astuce du noyau est utilisable dès qu’une méthode ne fait apparaître
que des produits scalaires. La première utilisation de l’astuce est le kernel perceptron en 1964.
Une version « à noyau » de l’analyse en composante principale existe (kernel PCA), ainsi qu’un
kernel k-means.
L’article suivant présente plusieurs modèles de « machines à noyaux » ainsi que différents
noyaux, pour des données vectorielles ou non :
T. Hofmann, B. Schölkopf, A. Smola, Kernel methods in machine learning, Annals of Statistics,
vol. 36 no. 3, 1171-1220, 2008.
Nous discutons à présent les réseaux de neurones artificiels : un modèle qui, au cours des
soixante dernières années, s’est incarné sous différentes formes, a suscité des attentes par-
fois démesurées, est retombé dans l’oubli (relatif), mais a fini par surpasser la concurrence
sur certains problèmes au point d’être souvent synonyme d’Intelligence Artificielle dans le
discours public.
Pd
F IGURE 9.1 – Modèle de perceptron de Rosenblatt : y = 1 si w 0 + i =1 w i x i > 0 ; y = −1 sinon.
visée à partir d’observations qui seraient des images ou des sons. Une telle présentation du
perceptron est très optimiste, mais, par certains aspects, les réseaux de neurones convolutifs
apparus il y a quelques années commencent à atteindre cet objectif.
— Initialisation : w = 0
— Tant que la valeur de w est mise à jour lors d’un parcours de la base d’exemples,
répéter :
— Pour n de 1 à N :
calculer ybn = signe(w · x n )
si ybn ̸= y n alors mettre à jour w : w ← w + y n x n
— Retourner w
Théorème 9.1 (Novikoff 1962) Si les observations étiquetées sont linéairement séparables,
alors l’algorithme du perceptron aboutit en un nombre fini d’étapes aux paramètres d’un hy-
perplan séparateur.
Démonstration
Soit w définissant un hyperplan séparateur des deux classes (qui existe par hypothèse).
Les poids du perceptron correspondant sont définis à une constante multiplicative près (seul
le signe de w · x n importe), on suppose donc sans perte de généralité ∥w ∥2 = 1.
Chaque hyperplan séparateur définit une marge entre les deux classes comme la plus
petite distance entre les observations de chaque classe et l’hyperplan. Rappelons que la dis-
tance entre une observation x et l’hyperplan défini par w est |w · x|/∥w ∥2 . La marge γ est
donc γ = min1ÉnÉN y n w · x n car on suppose ∥w ∥2 = 1.
Notons également R = max1ÉnÉN ∥x n ∥2 .
Considérons la k-ème erreur de l’algorithme, commise sur l’observation étiquetée (x n , y n ).
On a : y n w k · x n < 0 (car y n et w k · x n ont des signes différentes), et la mise à jour s’écrit
w k+1 = w k + y n x n .
D’une part : w k+1 · w = w k · w + y n x n · w Ê w k · w + γ par définition de γ.
Donc par récurrence : w k+1 · w Ê kγ car w 0 = 0.
D’autre part : ∥w k+1 ∥22 = ∥w k + y n x n ∥22 = ∥w k ∥22 + 2y n x n · w k + ∥x n ∥22 É ∥w k ∥22 + R 2 car
y n w k · x n < 0 et ∥x n ∥22 É R 2 .
Donc par récurrence : ∥w k+1 ∥22 É kR 2 .
Comme ∥w ∥2 = 1, w k+1 · w /∥w k+1 ∥2 est le cosinus de l’angle formé par les vecteurs w k+1
et w . Nous déduisons des deux inégalités précédentes, pour tout k :
p
kγ/R É w k+1 · w /∥w k+1 ∥2 É 1
Autrement dit, au cours des mises à jour l’hyperplan défini par le perceptron (paramètre w k )
tend à s’aligner sur l’hyperplan séparateur de paramètre w , car le cosinus de leur angle se
rapproche de 1. p
Par ailleurs, kγ/R É 1, donc k É R 2 /γ2 : cela signifie que le nombre de mises à jour est
au plus R 2 /γ2 avant que le perceptron ne fasse plus d’erreurs. □
La démonstration nous indique que plus la marge γ entre les deux classes à discrimi-
ner est grande (relativement à R), plus la convergence est rapide. Le nombre de mises à jour
est indépendant de la dimension d , ainsi que du nombre d’observations N . Cela ne signifie
pas que la vitesse de convergence est indépendante de N , car plus N est grand plus on peut
mettre de temps à « tomber » sur les erreurs de classification permettant la mise à jour.
Si les données ne sont pas séparables, l’algorithme ne converge pas. Il faut alors arrêter
après un certain nombre de parcours des données. Un parcours de la base d’apprentissage
en entier est appelé époque, ou epoch.
L’algorithme d’apprentissage du perceptron nous fournit un des hyperplans séparateurs,
de manière relativement arbitraire (cela dépend de l’ordre de parcours des observations).
Comme l’illustre la figure 9.2, l’indétermination pose problème pour la prédiction de la classe
de nouvelles observations.
L’algorithme du perceptron peut être vu comme la descente de gradient stochastique mi-
nimisant le coût d’erreur
N
ℓ(w ) =
X © ª
max 0, −y n w · x n
n=1
(voir l’annexe B.3, en particulier la section B.3.3 pour le gradient stochastique, ainsi que la
section 8.4.1 pour le discussion des fonctions de perte).
En effet, si y n w · x n > 0 (prédiction correcte) alors ℓ(w ) = 0 sur un voisinage de w donc
∇ℓ(w ) = 0, et si y n w · x n < 0 (prédiction incorrecte) alors ℓ(w ) = −y n w · x n donc ∇ℓ(w ) =
−y n x n . L’algorithme de descente de gradient à pas η = 1 (voir annexe B.3) correspond bien à
l’algorithme d’apprentissage du perceptron.
Le théorème 9.1 nous assure la convergence dans le cas où les classes sont séparables, et
seulement dans ce cas.
F IGURE 9.2 – Perceptron : ambiguïté de l’hyperplan séparateur obtenu. Selon l’hyperplan re-
tenu, une observation non étiquetée sera associée à une classe ou à l’autre.
AND et OR. Rappelons que, si l’on note 0 le booléen « faux » et 1 le booléen « vrai », les tables
de vérité de ces opérateurs sont les suivantes :
x1 x2 y x1 x2 y
0 AND 0 0 0 OR 0 0
0 AND 1 0 0 OR 1 1
1 AND 0 0 1 OR 0 1
1 AND 1 1 1 OR 1 1
Comme l’illustre la figure 9.3, le calcul de ces deux opérateurs revient à un problème de
classification pour deux classes linéairement séparables. On pourrait penser qu’il s’agit là
d’un argument fort pour assimiler le perceptron à une brique essentielle dans la construction
d’une « intelligence artificielle ». Cependant, le perceptron ne peut pas calculer l’opérateur
logique XOR (« ou exclusif »), qui a pour table de vérité :
x1 x2 y
0 XOR 0 0
0 XOR 1 1
1 XOR 0 1
1 XOR 1 0
F IGURE 9.3 – Les calculs de AND, OR, ou XOR peuvent être vus comme des problèmes de clas-
sification biclasse. Les opérateurs logiques AND et OR sont calculés par un classifieur linéaire
(donc un perceptron), contrairement à l’opérateur XOR.
En effet, comme l’illustre la figure 9.3, calculer le XOR est équivalent à résoudre un pro-
blème de classification non linéaire, ce dont est incapable le perceptron. Ce genre de limita-
tions du perceptron a été la cause de l’abandon des méthodes dites connexionistes en faveur
des méthodes dites symboliques, cause du premier « hiver de l’IA » dans les années 1970.
Une solution à ce problème était en fait connue, et s’est révélee particulièrement fruc-
tueuse par la suite. . . On remarque la relation suivante entre XOR et OR/AND : quels que
soient les booléens x 1 et x 2 ,
Pour établir cette relation, on peut calculer la table de vérité de l’expression de droite et
constater qu’elle est identique à celle du XOR. La relation précédente permet de construire
un réseau de perceptrons à une couche cachée entre la couche d’entrée et la couche de sortie,
représenté sur la figure 9.4.
Il y a même mieux : on peut démontrer que toute formule logique (une fonction de n
booléens, à valeurs booléennes) peut être calculée par un réseau de perceptrons à une couche
cachée. En effet, les logiciens démontrent le théorème suivant.
Théorème 9.2 Toute formule logique peut être convertie en une formule équivalente sous
forme normale conjonctive.
Une forme normale conjonctive est une conjonction (AND) de disjonction(s) (OR) de litté-
raux, un littéral étant une variable booléenne ou la négation d’une variable booléenne. La
décomposition précédente du XOR est justement une forme normale conjonctive.
On peut alors construire un réseau de perceptrons à une couche cachée calculant une
formule logique exprimée sous forme normale conjonctive en appliquant les « recettes » sui-
vantes :
1. on définit la couche d’entrée faites des variables x 1 , x 2 , . . .x n
F IGURE 9.4 – Perceptron à une couche cachée calculant le « ou exclusif » (XOR). On vérifie que,
selon les valeurs de x 1 et x 2 (0 ou 1), la valeur de y en sortie correspond bien à x 1 XOR x 2 .
Ici, la fonction d’activation H est telle que H (z) = 0 si z < 0, et H (z) = 1 sinon.
Sans rentrer dans les détails, pour convertir une formule logique en forme normale conjonc-
tive, il peut être nécessaire de faire apparaître un grand nombre de disjonctions (plus préci-
sément, une fonction exponentielle du nombre de variables). Cela signifie que le réseau de
perceptrons à une couche cachée peut certes calculer toute formule logique, mais parfois au
prix d’un grand nombre de neurones dans la couche cachée.
x1
x2 y1
x3
x4 y2
x5
F IGURE 9.5 – Un réseau de neurones artificiels (perceptron multicouche) à une couche cachée.
L’« information » en entrée est ici un vecteur de R5 , et en sortie un vecteur de R2 . Avec d neurones
en entrée, n neurones dans la couche cachée, et s neurones en sortie, le nombre de paramètres
(poids et biais) dans ce modèle est (d +1)n +(n +1)s (« +1 » à cause du biais en chaque neurone).
où :
— la somme porte sur l’ensemble des neurones i de la couche précédente k −1 connectés
avec le neurone j ,
— w j i est le poids de la connexion entre le i -ème neurone de la couche k − 1 et le neu-
rone j ,
— b j (appelé « biais ») est un scalaire,
— et z i est le signal émis par ce i -ème neurone.
Le neurone j émet ensuite l’information σ(a j ) à tous les neurones de la couche suivante k +1
auxquels il est connecté, où σ est une fonction d’activation dont on verra les propriétés dans
la section 9.2.1.
Enfin, la dernière couche émet le vecteur ou le scalaire de sortie du réseau. Sa nature
exacte dépend du problème traité (classification ou régression) ; cela sera abordé à la sec-
tion 9.2.2.
L’apprentissage consiste à adapter les paramètres (poids et biais) du réseau de manière
à prédire correctement les étiquettes d’une base d’exemples. Il est l’objet de la section 9.4.
Avant de traiter l’apprentissage, on aura évoqué en section 9.3 quelques résultats théoriques
permettant de se représenter ce que peuvent calculer les réseaux de neurones.
Remarque. Dans la suite de ce chapitre, nous utilisons les notations du livre Pattern recogni-
tion and machine learning de C. Bishop : z est le signal en sortie d’un neurone appartenant
à une couche cachée (donc après activation), et a est la somme pondérée des signaux en en-
trée d’un neurone (donc avant activation). Notez que la convention inverse est adoptée sur
la page web suivante : https://en.wikipedia.org/wiki/Backpropagation
où la somme porte sur les neurones de la couche précédente connectés au neurone consi-
déré, chacun ayant une sortie z i , les poids des connexions étant w j i et le biais b j . Il est fon-
damental de considérer des activations non linéaires. Un réseau de neurones avec des activa-
tions linéaires ne ferait que des compositions de fonctions linéaires des entrées. Un tel réseau
émettrait donc en sortie une combinaison linéaire des entrée, ce qui limiterait grandement
son intérêt.
Une activation en échelon comme pour le perceptron de Rosenblatt restreint les signaux z i
aux seules valeurs 0 ou 1. Différentes activations ont été proposées. Toutes sont continues et
croissantes, et sont (presque partout) dérivables pour des raisons qui apparaîtront dans la
suite de ce chapitre. La figure 9.6 représente certaines des fonctions d’activation définies ci-
dessous.
1.5
step
sigmoide
RELU
softsign
0.5
-3 -2 -1 0 1 2 3
step 0 si a < 0
s(a) =
(voir perceptron)
1 si a Ê 0
1
sigmoide σ(a) = 1+e −a
e a −e −a
tangente hyperbolique tanh(a) = e a +e −a = 2σ(2a) − 1
a
softsign softsign(a) = 1+|a|
Étant donnée une observation x ∈ Rd , la sortie d’un réseau de neurones possédant d neu-
rones en entrée se calcule en propageant les calculs « de gauche à droite » dans la figure 9.5.
La forme de la sortie change selon le problème d’apprentissage que l’on souhaite traiter.
Dans les problèmes de régression, les étiquettes des observations sont des scalaires ou
des vecteurs. Un réseau de neurones adapté à un problème de régression a autant de neu-
rones de sortie que la dimension des étiquettes à prédire, comme représenté ci-dessous.
Dans cet exemple, le problème de régression consiste à prédire y ∈ R2 à partir de x ∈ R5 avec
une seule couche cachée de trois neurones. Pour un problème de régression dans lequel on
cherche à prédire une valeur réelle, il n’y a qu’un seul neurone de sortie. Bien entendu, l’ar-
chitecture est à adapter au problème traité.
x1
x2 y1
x3
x4 y2
x5
Il n’y a pas de fonction d’activation sur les neurones de la couche de sortie : avec les no-
tations habituelles, la j -ème composante de sortie est :
X
yj = w j i zi + b j
i
Dans les problèmes de classification où il faut distinguer deux classes, les étiquettes sont 1
ou 0 ; elles correspondent respectivement aux classes C 1 ou C 2 . Un exemple de réseau de
neurones pour la classification biclasse d’observations x ∈ R5 est représenté ci-dessous.
x1
x2
x3 y
x4
x5
en fonction des poids w i reliant le neurone de sortie à ceux de la couche cachée et des si-
gnaux z i émis par les neurones de la dernière couche cachée.
Pour obtenir une probabilité a posteriori p(C 1 |x) (et pour permettre l’apprentissage, comme
on le verra plus loin), on utilise une fonction d’activation σ sur le neurone de sortie de ma-
nière à normaliser la sortie à une valeur entre 0 et 1, supérieure à 1/2 pour la classe C 1 et
inférieure à 1/2 pour la classe C 2 . Il est courant de choisir la fonction sigmoïde. La fonction
d’activation des neurones des couches cachées n’est pas nécessairement comprise entre 0 et
1, et peut donc être choisie différemment.
— si i w i z i + b < 0, dans C 2 .
P
On suppose que K > 2 classes sont à discriminer. Il faut encoder les classes par des éti-
quettes scalaires, mais choisir arbitrairement des numéros de classes (y = 2, y = 5, etc.) n’a
pas vraiment de sens. On utilise un encodage particulier des étiquettes : l’encodage « un
parmi n », ou one-hot encoding. Cela consiste à définir l’étiquette y comme un vecteur de
dimension K , tel que la composante y i est nulle sauf en l’indice correspondant à la classe à
coder pour laquelle y i = 1.
L’exemple ci-dessous montre un réseau de neurones adapté à un problème de classifica-
tion en K = 3 catégories à partir d’observations dans R5 .
x1
x2 y1
x3 y2
x4 y3
x5
Dans cet exemple, la classe 2 est encodé par l’étiquette (0, 1, 0).
La règle de décision est alors d’associer l’observation à la classe i telle que y i a la plus
grande valeur parmi les sorties.
Comme dans le cas biclasse, on fait apparaître des probabilités a posteriori en normali-
sant les sorties entre 0 et 1. On utilise la règle dite « SoftMax » sur chaque sortie y i :
1
y i = PK exp(a i )
k=1
exp(a k )
où chaque a k représente le signal en entrée du neurone de sortie k, qui est une combinaison
linéaire des signaux émis par les neurones de la couche précédente.
Cette opération a pour effet d’« écarter » numériquement la plus grande valeur des autres,
et de normaliser les y i entre 0 et 1 (d’où l’expression SoftMax : il s’agit d’une version « douce »
du maximum qui consisterait à mettre toutes les valeurs à 0 sauf la valeur maximale à 1). Par
P
ailleurs, on est assuré que i y i = 1.
Il ne s’agit pas d’une fonction d’activation à proprement parler car la normalisation est
commune à tous les neurones de sortie. On parle de « couche SoftMax » (SoftMax layer) en
sortie.
Avant d’aborder l’apprentissage, nous discutons de l’« expressivité » des réseaux de neu-
rones artificiels : quelles fonctions peuvent bien être calculées par ces modèles ?
Commençons par discuter le réseau de neurones artificiels le plus simple, possédant une
couche cachée. Supposons d neurones en entrée lisant x ∈ Rd , M neurones dans la couche
cachée (fonction d’activation σ), et un neurone en sortie émettant F (x) ∈ R. Il s’agit d’une
architecture pour un problème de régression dans R.
Les règles de propagation permettent d’écrire l’expression de la sortie F (x) en fonction
de l’entrée x :
M
w ks σ (w k · x + b k ) + b
X
F (x) =
k=1
Le théorème suivant nous indique ce qu’il est possible de calculer avec une fonction de
cette forme.
Théorème 9.3 Théorème de Cybenko (1989) (et autres chercheurs), ou théorème d’approxima-
tion universelle.
Soient φ une fonction strictement croissante continue bornée, et C un compact de Rd .
Pour tout ε > 0 et f continue sur C , il existe M ∈ N , et pour tout i ∈ {1, . . . , M }, v i , b i ∈ R,
w i ∈ Rd , tels que la fonction :
M
v i φ(w i · x + b i )
X
F (x) =
i =1
vérifie :
∀x ∈ C , |F (x) − f (x)| < ε
Des théorèmes équivalents ont été démontrés pour certaines fonctions φ non bornées
comme la fonction ReLU. Le théorème de Cybenko nous dit que toute fonction réelle conti-
nue sur un compact peut être approchée d’aussi près que l’on veut par la sortie d’un percep-
tron à une couche cachée possédant M neurones. La fonction φ joue le rôle de l’activation σ
qui en possède bien les propriétés (qu’elle soit bornée comme la sigmoïde, ou non-bornée
en ajoutant certaines hypothèses).
On se rend compte que la non-linéarité de l’activation joue un rôle essentiel : si φ était
une fonction affine, alors F (x) serait également affine. Bien entendu les fonctions affines ne
peuvent pas approcher toute fonction continue sur un compact à une précision arbitraire.
Remarque. Il s’agit d’un résultat d’existence (pour les matheux, il s’agit d’une variante du
théorème de Stone-Weierstrass). Le théorème ne dit pas comment construire le réseau (choix
de M , qui est potentiellement grand) ni comment fixer les poids pour approcher une fonction
donnée avec une précision ε donnée. De fait, les techniques modernes de deep learning pri-
vilégient un grand nombre de couches cachées, architecture plus adaptée à l’apprentissage
qu’une seule couche cachée faite d’un très grand nombre de neurones.
Le théorème précédent nous permet de dire que les réseaux de neurones sont également
des classifieurs universels, dans le sens suivant.
Supposons que l’espace des observations C (supposé compact) soit partitionné en l’union
des K classes à identifier C = C 1 ∪ · · · ∪ C K .
Chaque observation x appartenant à une des classes, on introduit la fonction de classifi-
cation multiclasse : f (x) = k si x ∈ C k . On ne peut pas appliquer le théorème de Cybenko à f
car cette fonction n’est pas continue.
Néanmoins, le théorème de Lusin nous indique que, pour ε > 0, il existe un ensemble
D ⊂ C de mesure λ(D) ≥ (1 − ε)λ(C ) tel que f coïncide sur D avec une fonction g continue.
On peut appliquer le théorème de Cybenko à g , ce qui nous permet de conclure : il
existe un réseau de neurones qui approche f à ε près, sauf sur un ensemble de mesure au
plus ελ(C ).
Remarque. Certes, les réseaux de neurones pour la classification n’ont pas cette architecture
(cf. la couche de sortie qui emploie une sigmoïde ou est une couche SoftMax). Néanmoins, il
ne faut pas perdre de vue qu’il ne s’agit de toute façon que d’un résultat d’existence. L’ensei-
gnement principal est que les réseaux de neurones ont une expressivité suffisante pour re-
présenter correctement toutes les frontières de classification. Ce n’est pas le cas par exemple
du perceptron de Rosenblatt ou du classifieur de la régression logistique qui sont restreints
aux frontières linéaires.
L’apprentissage des poids d’un réseau de neurones en fonction d’une base d’exemples
se fait en minimisant un coût d’erreur global par descente de gradient (voir la section B.3
en annexe). On parle aussi d’entraînement du réseau (training). Le calcul exact du gradient,
c’est-à-dire sans utiliser de schéma numérique approché, est possible grâce à un algorithme
astucieux popularisé dans les années 1980 : la « rétropropagation des erreurs » (backpropaga-
tion).
Pour alléger les notations, on suppose que la première composante de chaque obser-
vation est égale à 1, ce qui permet de traiter les biais comme des poids pour simplifier les
équations.
9.4.1 Notations
Le risque empirique (coût d’erreur moyen sur la base d’apprentissage) est la moyenne
des coûts des erreurs E n sur chaque observation étiquetée (x n , y n ) :
1 XN
E (w ) = E n (w )
N n=1
Il faut choisir la fonction E n en fonction du problème traité. Les choix les plus courants
sont :
1°° y n − ŷ n °2
°
E n (w ) = 2
2
K
X
E n (w ) = − y n j log( ŷ n j )
j =1
Dans tous les cas, E n est positif (car si x É 1, − log(x) Ê 0) et est minimal (et nul) lorsque
y n = ybn . En effet, dans le cas de la classification biclasse, y n = 0 ou y n = 1 donc E n est minimal
lorsque ybn = y n , et dans le cas de K > 2 classes, la convention sur le logarithme et l’utilisation
du one-hot encoding font que seul un terme est non-nul dans la somme.
L’objectif de l’apprentissage est de trouver les poids w qui minimisent l’erreur moyenne E (w ).
Remarque. Dans le cas de la classification, la fonction mesurant le coût d’erreur (loss) n’étant
pas un coût 0-1, l’erreur E n’est pas directement liée à la proportion de fausses classifications.
∂E
w ji ← w ji − η (w )
∂w j i
∂E N ∂E
1 X n
= (w )
∂w j i N n=1 ∂w j i
Nous allons donc commencer par calculer les dérivées partielles ∂E n /∂w j i .
La formule de dérivation composée (voir l’annexe A.2) nous indique (ici, avec les nota-
tions de cette annexe, a j = g (w j i ) ∈ R) :
∂E n ∂E n ∂a j
=
∂w j i ∂a j ∂w j i
∂a j ∂E n
On a ∂w j i = z i , donc, en posant δ j = ∂a j :
∂E n
= δ j zi
∂w j i
Il s’avère qu’il existe une astuce pour calculer efficacement les δ j en chaque neurone : l’al-
gorithme de rétropropagation des erreurs (backpropagation). Il s’appuie sur le calcul des δ j
aux neurones de sortie, puis calcule, de proche en proche, les δ j des couches cachées jus-
qu’aux neurones de la couche cachée la plus proche de l’entrée du réseau.
— problème de régression : E n = 12 ∥y n − ybn ∥22 où ybn = (a l )1≤l ≤s est le vecteur des sorties de
chacun des s neurones de la dernière couche.
Par conséquent, aux neurones de sortie :
∂E n
δj = = ybn j − y n j
∂a j
∂E n e −a 1
δ= = 1 − yn − = − yn
∂a 1+e −a 1 + e −a
soit :
δ = ybn − y n
Ps
log( ŷ nl ) où ŷ nl = e al / am
P
— problème de classification à s > 2 classes : E n = − y
l =1 nl me
(couche SoftMax). Autrement écrit :
s
X
µ µ
X a
¶¶
En = − y nl a l − log e m
l =1 m
Par conséquent : Ã !
∂E n eaj X s
δj = = − yn j − P a y nl
∂a j me
m
l =1
P
Comme pour tout n, l y nl = 1 (cf one-hot encoding), on peut conclure. Au neurone de
sortie j :
δ j = ybn j − y n j
Pour toutes les fonctions de coût vues ici, on voit que δ j est calculé en un neurone de
sortie comme la différence entre la sortie attendue y et la sortie observée yb.
∂E n X ∂E n ∂a l
δj = =
∂a j l ∂a l ∂a j
F IGURE 9.7 – Illustration des deux étapes successives de propagation avant puis rétropropaga-
tion pour calculer les z et δ intervenant dans les dérivée partielle ∂E /∂w j i . Dans cette figure,
on a isolé le neurone j , et représenté uniquement les neurones qui lui sont connectés dans la
couche précédente et dans la couche suivante.
De plus :
∂a l ∂ X
= w l i σ(a i ) = w l j σ′ (a j )
∂a j ∂a j i
δ j = σ′ (a j ) w l j δl
X
l
On peut calculer tous les δ sur le réseau par rétropropagation des erreurs. On commence
par calculer les erreurs comme différence entre sortie attendue y n et sortie du réseau ybn
(paragraphe 9.4.3.1), puis on propage les δ j vers les couches d’entrée à l’aide de la formule
concluant le paragraphe 9.4.3.2.
L’algorithme de calcul des δ j avec propagation avant suivie de rétropropagation est illus-
tré par la figure 9.7.
∂E n
(d) calcul des dérivées partielles : ∂w j i (w ) = δ j z i
∂E 1 PN ∂E n
2. pour chaque poids w j i , calcul de ∂w j i (w ) = N n=1 ∂w j i (w ) et mise à jour :
∂E
w ji ← w ji − η (w )
∂w j i
— version mini-batch / par mini-lot : mise à jour des poids après parcours d’un sous-
ensemble B m d’observations :
X ∂E n
w ji ← w ji − η
n∈B m ∂w j i
9.4.5 Remarques
La rétropropagation est une astuce pour calculer le gradient ∇E , ce n’est pas l’appren-
tissage proprement dit, même si par abus de langage on peut parler d’« apprentissage par
rétropropagation ».
On voit que toutes les formules employées sont exactes, et nécessitent des fonctions d’ac-
tivation dérivables. Au passage, on remarque que les neurones peuvent avoir chacun leur
propre fonction d’activation.
E (w ) + λ∥w ∥22
avec un hyperparamètre λ > 0. On remarque que cela ajoute le terme 2λw j i dans la dé-
rivée partielle ∂E /∂w j i de l’algorithme d’apprentissage, ce qui ne pose pas de difficulté
particulière.
Il ne faut pas perdre de vue les nombreux paramètres restant à fixer par l’utilisateur :
— l’architecture du réseau : combien de couches cachées ? combien de neurones dans
chaque couche ?
— le nombre d’époques dans l’apprentissage en cas d’arrêt prématuré, ou le paramètre
de régularisation λ ;
— le taux d’apprentissage η qui peut être amené à varier (intuitivement, on peut com-
mencer l’apprentissage avec une grande valeur de η puis diminuer cette valeur lorsque
la descente de gradient commence à converger) ;
— les valeurs initiales des poids et biais (l’initialisation est assez critique pour les per-
formances d’apprentissage : elle est généralement aléatoire et différentes stratégies
existent) ;
— le critère d’arrêt de la descente de gradient ;
— les tailles de lots (batches) dans l’algorithme du gradient stochastique par lot.
S’il peut être possible de s’aider de la validation croisée, au prix d’un temps de calcul parfois
rédhibitoire, une large partie des réglages reste tributaire de l’expérience de l’utilisateur.
Pour conclure ce cours, nous souhaitons donner quelques éléments permettant de com-
prendre les enjeux de l’apprentissage profond (deep learning).
Si les réseaux convolutifs ont été introduits par Yann Le Cun et ses co-auteurs dans les années
1990, c’est bien la disponibilité de grandes bases d’apprentissage, l’amélioration du matériel,
ainsi que le développement de bibliothèques logicielles qui ont permis la révolution de l’ap-
prentissage profond. Notons que la notion de « profondeur » est relative : dans certaines ap-
plications on se satisfait d’un réseau possédant seulement quelques couches de convolution.
10.2.1 Convolution
Le traitement du signal est la discipline scientifique qui s’intéresse aux signaux numé-
riques ou analogiques et à la manière de les transformer. Les signaux peuvent être par exemple
des images ou des enregistrements sonores.
Considérons un système H transformant un signal d’entrée e en signal de sortie s = H (e).
Des propriétés naturelles d’un tel système sont :
— H est linéaire : si e 1 et e 2 sont des signaux et α ∈ R, alors H (e 1 + αe 2 ) = H (e 1 ) + αH (e 2 ) ;
— H est continu
— H est invariant par translation : si ∀ t , H (e(t )) = s(t ), alors ∀ t , H (e(t − τ)) = s(t − τ)
On parle de système (ou filtre) linéaire, continu, et invariant. Ce sont des propriétés natu-
relles : la linéarité traduit que la réponse à deux signaux superposés est la superposition des
réponses des signaux considérés de manière indépendante ; la continuité implique qu’une
petite perturbation du signal en entrée induira une petite perturbation du signal en sortie ;
l’invariance par translation implique que lorsqu’on traite un son, l’origine du temps n’im-
porte pas, ou lorsqu’on traite une image, un « objet » est transformé de la même manière s’il
est en haut à gauche ou en bas à droite de l’image.
On démontre alors que pour tout filtre vérifiant ces trois propriétés, il existe une fonc-
tion h (en fait, une distribution au sens de Laurent Schwartz. . .) telle que pour tout signal en
F IGURE 10.1 – LeNet (à gauche) et AlexNet (à droite). Ces réseaux permettent de résoudre des
problèmes de classification : 10 classes pour LeNet et 1000 classes pour AlexNet. LeNet admet
en entrée des imagettes en niveaux de gris de taille 32 × 32 pixels (28 × 28 indiqué ici à cause de
la gestion des bords par les convolutions). Ce réseau est généralement utilisé pour la reconnais-
sance de chiffres manuscrits. AlexNet admet en entrée des images couleur de taille 224 × 224
pixels. LeNet a de l’ordre de 61 000 paramètres, et AlexNet 62 millions. Source de l’illustration :
By Cmglee - Own work, CC BY-SA 4.0, https: // commons. wikimedia. org/ w/ index. php?
curid= 104937230
entrée e,
H (e) = h ∗ s
où ∗ désigne le produit de convolution. Rappelons que si h et s sont deux fonctions réelles
intégrables, la convolution h ∗ s est définie par :
Z Z
∀ t ∈ R, h ∗ s(t ) = h(t − u)s(u) du = h(u)s(t − u) du
R R
Tout filtre s’exprime donc comme un produit de convolution et est caractérisé par une
fonction h appelée « réponse impulsionnelle », ou noyau de convolution. On parle de réponse
impulsionnelle car, dans le cadre de la théorie des distributions, la convolution de h avec la
distribution de Dirac (une impulsion) est h elle-même.
Les convolutions apparaissent comme l’outil de base du traitement du signal. Lorsqu’on
souhaite construire des réseaux de neurones traitant des signaux comme des images ou des
sons, il semble donc naturel de s’appuyer sur les convolutions.
On s’intéresse en fait aux signaux numériques, qui sont discrets : ce sont des vecteurs
(s n )n , indexés sur un espace discret plutôt que sur un espace continu comme la fonction s
précédente.
On définit la convolution discrète de réponse impulsionnelle h comme :
∀ n ∈ Z, h ∗ s(n) =
X
h(k)s(n − k)
k∈Z
En pratique, le noyau h est non nul pour un nombre fini de valeurs, la somme précédente ne
concerne donc qu’un nombre fini de termes.
Dans le cas où le signal est une image, la convolution s’écrit comme une somme double :
∀ (m, n) ∈ Z2 , h ∗ s(m, n) =
X
h(k, l )s(m − k, n − l )
(k,l )∈Z2
L’opération de convolution étant linéaire, elle peut très bien être réalisée par une couche
de neurones : les neurones d’entrées lisent le signal (fini), la couche cachée faite du même
nombre de neurones calcule les h ∗ s, mais pour ce faire les neurones cachés ne sont reliés
qu’aux neurones d’entrée jouant un rôle dans la somme, et les poids des liaisons sont les
coefficients du noyau. On voit que les poids des liaisons en entrée des neurones cachées sont
les mêmes d’un neurone caché à l’autre : ce sont les coefficients du noyau de convolution.
Par exemple, pour réaliser la convolution d’un signal s(1), s(2), . . . , s(n) avec un noyau dont
la taille de support est 3 :
X
∀ i ∈ {1, 2, . . . , n}, h ∗ s(n) = h(k)s(n − k)
k∈{−1,0,1}
donc le neurone caché d’indice n est relié aux neurones d’entrée d’indices n −1, n, n +1 avec
des poids respectifs h(1), h(0), h(−1). Tous les neurones sont traités de la même manière :
le noyau ne dépend pas de n. Dans cet exemple, les transitions entre les deux couches ne
dépendent que de trois paramètres. Notons qu’il faudrait traiter les « bords » du signal s de
manière particulière afin de donner un sens plus précis à la formule.
La figure 10.2 montre un exemple de l’effet de plusieurs filtres de convolution sur une
image.
Comme en traitement du signal classique, on peut définir un « banc de filtres », qui sépare
le signal en plusieurs composantes, chacune étant obtenue par un filtre autonome. Ici, le
banc de filtre est implanté par des couches de convolution indépendantes utilisées sur la
même entrée.
En toute généralité, l’entrée est d’« épaisseur » d . Par exemple d = 3 pour une image
couleur, car chaque pixel est représenté par un triple de composantes (rouge,vert,bleu). Un
noyau de convolution sur une telle entrée est également d’« épaisseur » d .
La figure 10.3 représente une couche convolutive.
La sortie de chaque couche de convolution est rendue non-linéaire par une fonction
d’activation. Afin d’assurer une certaine complexité au réseau, les couches de convolution
peuvent se succéder. Si une première couche est formée de k filtres (elle représente un banc
de filtres, comme précédemment évoqué), les noyaux de la seconde couche agiront sur toute
F IGURE 10.2 – Effet de différents filtres sur une image (en haut) et noyau de convolution (en
bas). De gauche à droite : image originale (invariante par le filtre de Dirac), flou gaussien,
filtre de Prewitt selon l’axe vertical, filtre de Prewitt selon l’axe horizontal. Le filtre gaussien
(ici, support de taille 5 × 5 et σ = 1 pixel) rend l’image un peu floue, et les filtres de Prewitt
mettent en évidence les contours horizontaux et verticaux (dans ces deux dernières images, par
convention le noir représente une valeur élevée). Pour pouvoir calculer les convolutions sur les
bords de l’image, on considère les niveaux de gris des pixels extérieurs à l’image comme égaux
à 0, ce qui explique les effets de bords visibles.
Les couches de convolution peuvent donc être vues comme des couches de neurones
classiques auxquelles on impose des contraintes particulières sur les poids. Il se trouve que
l’algorithme de rétropropagation s’adapte (la démonstration est tout de même un peu tech-
nique), et qu’on peut entraîner un réseau convolutif de manière similaire à ce qu’on a discuté
au paragraphe 9.4 du chapitre 9. Plutôt qu’utiliser des filtres prédéfinis dédiés à des tâches
précises comme en traitement du signal « classique », tel qu’illustré par la figure 10.2, l’ap-
prentissage permet d’adapter les filtres en optimisant leurs paramètres. Cette approche est
donc bien plus flexible que l’approche « traitement du signal » historique dans laquelle le
spécialiste construisait des filtres ad-hoc.
10.2.2 Pooling
Pour limiter les coefficients à estimer et le temps de calcul, le support des noyaux de
convolution est de taille petite. Par exemple, pour traiter des images on peut utiliser des
noyaux de taille 3 × 3 ou 5 × 5 pixels (ou 3 × 3 × 3 ou 5 × 5 × 3 pour des images à trois canaux
de couleur). Cependant, il semble légitime de vouloir intégrer des informations distantes de
plus de trois ou cinq pixels. Une possibilité est de faire se succéder les convolutions. Une
F IGURE 10.3 – Représentation d’une couche convolutive : entrée de la couche à gauche, sortie
à droite. On suppose que l’entrée est formée d’un champ de dimension l × L × d . C’est le cas des
signaux bidimensionnels comme les images, pour lesquelles d = 3 si l’image a trois canaux de
couleur. Un signal unidimensionnel serait représenté par un champ de dimension l ×1×d , avec
d = 1 si le signal est univarié comme une onde sonore par exemple. Un filtre de support de taille
l ′ × L ′ × d donne une valeur stockée dans un champ de dimension (l − l ′ ) × (L − L ′ ) × 1 (sauf à
traiter de manière particulière les bords, par exemple en mettant à zéro les valeurs manquantes
pour obtenir une dimension de l × L), comme représenté par les pointillés noirs dans la figure.
Ici, la couche convolutive implante un banc de D = 5 filtres, la sortie de cette couche convolu-
tive est donc un champ de dimension (l − l ′ ) × (L − L ′ ) × D. Cette couche dépend de D(l ′ L ′ d + 1)
paramètres (« +1 » pour le biais). Elle est équivalente à une couche de réseau de neurones à pro-
pagation avant dans laquelle les poids sont partagés entre certaines connexions de manière à
implanter des convolutions. Pour des raisons de lisibilité, on représente une couche convolutive
par des blocs comme ici, plutôt qu’en disposant les neurones en colonne comme au chapitre 9.
autre possibilité est de réduire la taille des couches représentant le signal convolué par sous-
échantillonnage, par exemple en prenant le plus grand élément parmi deux éléments consé-
cutifs (ou parmi un bloc de 2 × 2 pixels dans le cas des images). Un noyau opérant ensuite
sur une couche sous-échantillonnée par un facteur 2 aurait un effet semblable à un noyau
de support de taille double sur la couche originale. L’avantage est de limiter le nombre de
paramètre des noyaux successifs.
On appelle couche de pooling (« mise en commun ») les couches du réseau effectuant une
telle opération. Le max-pooling illustré par la figure 10.4 introduit une nouvelle non-linéarité.
Notons que les couches de pooling n’introduisent pas de nouveaux paramètres à apprendre.
10.2.3 Dropout
Pour éviter le sur-apprentissage, le dropout est couramment utilisé dans les couches com-
plètement connectées du réseau (généralement les couches près de la sortie, comme on le
F IGURE 10.4 – Exemple de pooling par sous-échantillonnage d’un facteur 2 : on passe ici d’une
couche de dimension 4 × 4 à une couche de dimension 2 × 2. Chaque bloc de dimension 2 × 2
est remplacé par une valeur unique, égale au maximum des valeurs présentes dans le cas du
max-pooling. On peut envisager d’autres formes de pooling, par exemple un average-pooling
où on remplace un bloc par sa valeur moyenne.
verra dans l’exemple de VGG16, figure 10.5). Cette procédure consiste à « déconnecter » aléa-
toirement certains neurones d’une couche avec une probabilité p (par exemple p = 0.5),
pendant une itération de l’apprentissage par gradient stochastique. Les poids relatifs à ces
neurones ne sont donc pas mis à jour. Cela a pour effet de limiter le sur-apprentissage (et
joue donc un rôle de régularisation), en particulier en évitant d’apprendre des caractéris-
tiques communes à un groupe de neurones. En effet, la probabilité qu’un groupe donné de k
neurones soit actif dans une itération de l’apprentissage est (1 − p)k , ce qui est très faible.
Pour donner une intuition dans un problème de classification de chiens et chats où les
images de chiens montrent systématiquement un ciel bleu et celles de chats un gazon vert, le
dropout devrait permettre d’éviter que toute image montrant un ciel bleu (respectivement un
gazon) soit reconnue comme un chien (respectivement un chat), en forçant l’apprentissage
à également prendre en compte d’autres caractéristiques.
Pour la prédiction, tous les neurones sont utilisés. Le dropout n’est employé que pour la
phase d’apprentissage.
F IGURE 10.5 – Un exemple de réseau convolutif profond : VGG16 (K. Simonyan and A. Zisser-
man, 2014). L’entrée est constitué de 224 × 224 × 3 = 150528 neurones, ce qui correspond à une
image couleur (trois canaux) de 224 × 224 pixels. Le premier bloc de convolutions est constitué
de 64 filtres indépendants de support de taille 3 × 3 × 3, chacun étant suivi d’une activation
ReLU. Un second bloc réalise la même opération. Ensuite, un seul pixel sur deux est gardé dans
le pooling. Les blocs de convolution et de pooling se succèdent jusqu’à atteindre un réseau com-
plètement connecté classique constitué de deux couches de 4096 neurones, une couche de 1000
neurones, puis une couche SoftMax de 1000 neurones (il s’agit d’un problème de classifica-
tion à 1000 classes). Ce réseau est gouverné par 138 millions de paramètres. Par exemple les
connexions entre l’entrée et la première couche de convolution nécessitent (3 × 3 × 3 + 1) × 64 =
1792 paramètres (64 filtres 3×3 sur les 3 composantes RVB, et un biais par filtre), et entre la pre-
mière et la deuxième couche de convolution (3 × 3 × 64 + 1) × 64 = 36928 paramètres. Source de
l’illustration : https: // neurohive. io/ en/ popular-networks/ vgg16/ où sont fournis
les détails de l’architecture.
1. 2021 : 7210 ; 2020 : 6194 ; 2019 : 4150 ; 2018 : 2791 ; 2017 : 1360 ; 2016 : 500. . .
construits pour différents problèmes. Nous aimerions pouvoir réemployer ces réseaux pour
faire de l’apprentissage profond sur nos propres problèmes, sans refaire un long apprentis-
sage. . .
Cependant, que faire si on s’intéresse à un problème de reconnaissance d’images qui ne
seraient pas issues d’ImageNet ? Et si on cherche à identifier non pas 1000 catégories comme
dans ImageNet mais 5 qui ne figureraient pas dans cette base d’images ? Les couches de
convolution apprennent des descripteurs des images, qui sont ensuite fournis en entrée à
la partie fully connected supérieure du réseau. En supposant les images de la base Image-
Net « pas trop éloignées » des images de notre problème, on peut imaginer réutiliser les des-
cripteurs de VGG16 et donc utiliser les couches de convolution correspondantes. Ensuite, on
change la couche SoftMax de sortie de manière à prédire 5 classes, on change éventuelle-
ment le nombre de neurones des couches fully connected, puis on entraîne uniquement les
dernières couches du réseau qui servent à la classification. Alors qu’on ne pouvait pas en-
traîner intégralement un réseau comme VGG16 sur une petite base d’images, il est possible
d’entraîner uniquement les dernières couches sur cette base, en gardant fixes les poids des
couches convolutives. On pourrait d’ailleurs même envisager d’utiliser un autre classifieur
que la partie fully connected, par exemple en classifiant les sorties de la partie convolutive à
l’aide d’une SVM. Cette manière de procéder s’appelle « apprentissage par transfert » (transfer
learning).
Une approche complémentaire est de poursuivre l’apprentissage d’un réseau « pré-appris »
(pre-trained network) comme VGG16, avec les observations qui nous intéressent. En initiali-
sant l’apprentissage avec les poids originaux du réseau et en utilisant un taux d’apprentissage
faible, on ne fait que modifier légèrement les poids en les adaptant à nos observations. On
parle de « réglage fin » du réseau (fine tuning).
Lecture Nous n’avons fait qu’esquisser quelques éléments sur l’apprentissage profond à
travers les réseaux convolutifs, et n’avons évoqué que l’application à la classification d’images.
Par exemple, les approches modernes de l’apprentissage par réseaux de neurones permettent
l’apprentissage non-supervisé (voir les auto-encodeurs) ou l’apprentissage de séries tempo-
relles ou de données textuelles (voir les réseaux de neurones récurrents). Un point d’entrée
Enfin un livre gratuit très récent présente une excellente introduction à l’apprentissage
profond, des architectures dépassant les réseaux convolutifs aux applications modernes :
F. Fleuret, The little book of deep learning, 2023.
https://fleuret.org/francois/lbdl.html
1X n
X= Xi
n i =1
la moyenne empirique.
−2n 2 t 2
³ ´ µ ¶
Pr X − E (X ) Ê t É exp Pn 2
i =1 (b i − a i )
et :
−2n 2 t 2
³¯ ¯ ´ µ ¶
Pr ¯ X − E (X )¯ Ê t É 2 exp Pn
¯ ¯
2
i =1 (b i − a i )
Il s’agit de la formule de dérivation des fonctions composées (chain rule). Le cas particulier
p = q = r = 1 donne la formule bien connue : h ′ (x) = g ′ (x) f ′ (g (x)).
Dans le chapitre 9 (section 9.4.3), nous avons besoin de ce résultat dans deux cas particu-
liers :
1. Cas particulier de deux fonctions différentiables : g de Rp dans Rq et f de Rq dans R (ici
r = 1). On souhaite calculer les dérivées partielles de la fonction composée h = f ◦ g de
Rp dans R.
Si x = (x 1 , . . . , x p ) ∈ Rp et y = g (x) = (y 1 , . . . , y q ) ∈ Rq , alors la dérivée partielle de h par
rapport à la i -ème composante de sa variable est donnée par l’expression suivante :
∂h X q
∂f ∂g j
∀i ∈ [1, p], (x) = (y) (x)
∂x i j =1 ∂y j ∂x i
∂f ∂g j
où ∂y j désigne la dérivée partielle de f par rapport à sa j -ème composante, et ∂xi la
dérivée partielle de g j , j -ème composante de g , par rapport à sa i -ème composante.
2. Cas q = r = 1 :
∂h ∂g
(x) = f ′ (y)
∀i ∈ [1, p], (x)
∂x i ∂x i
où f ′ désigne la dérivée de la fonction réelle f .
A.3.1 Rappels
Une matrice carrée A à coefficients réels est dite symétrique si elle est égale à sa transpo-
sée : A = A T .
Une matrice carrée P à coefficients réels est dite orthogonale si son inverse est égal à sa
transposée : P P T = P T P = Id. Autrement dit, les vecteurs colonnes et les vecteurs lignes de P
forment une base orthonormée de Rn .
Proposition A.3 Une matrice A symétrique d’ordre n est diagonalisable à l’aide de matrices de
passage orthogonale, c’est-à-dire qu’il existe des matrices D et P d’ordre n telles que :
A = P DP T
Proposition A.4 Les valeurs propres d’une matrice symétrique positive sont positives ou
nulles.
Les valeurs propres d’une matrice symétrique définie positive sont strictement positives. En
particulier, cette matrice est inversible.
Démonstration
Si A est une matrice symétrique positive, soient λ une valeur propre de A et x un vecteur
propre associé. On a x T Ax = λ|x|2 et x T Ax Ê 0, donc λ Ê 0. Le cas défini se traite de la même
manière avec des inégalités strictes. □
Proposition A.5 Si A est une matrice symétrique définie positive, alors A −1 aussi.
Démonstration
Si A est symétrique définie positive, ses valeurs propres sont strictement positives donc A
est inversible. (A −1 )T = (A T )−1 = A −1 donc l’inverse de A est symétrique. Soient P orthogo-
nale et D diagonale telles que A = P DP T . Alors A −1 = P D −1 P T car P −1 = P T . Les éléments
diagonaux de D −1 sont comme ceux de D strictement positifs, donc pour tout x non nul :
x T A −1 x = (P T x)T D −1 P T x > 0. □
a 11 x 12 + a 22 x 22 + a 33 x 32 + a 12 x 1 x 2 + a 13 x 1 x 3 + a 23 x 2 x 3 + b 1 x 1 + b 2 x 2 + b 3 x 3 + c = 0
b1 2 b2 2 b3 2
µ ¶ µ ¶ µ ¶
a 11 x 1 + + a 22 x 2 + + a 33 x 3 +
2a 11 2a 22 2a 33
b1 b2 b1 b3 b2 b3
µ ¶µ ¶ µ ¶µ ¶ µ ¶µ ¶
+ a 12 x 1 + x2 + + a 13 x 1 + x3 + + a 23 x 2 + x3 +
2a 11 2a 22 2a 11 2a 33 2a 22 2a 33
2 2 2
b b b a 12 b 1 b 2 a 13 b 1 b 3 a 23 b 2 b 3
+c − 1 − 2 − 3 − − − =0
4a 11 4a 22 4a 33 4a 11 a 22 4a 11 a 33 4a 22 a 33
qui est la forme canonique de la quadrique, dans laquelle on a fait apparaître le centre de la
conique de coordonnées : ³ ´
− 2ab111 − 2ab222 − 2ab333
a 11 a 12 /2 a 13 /2
A = a 12 /2 a 22 a 23 /2
a 13 /2 a 23 /2 a 33
s 1 y 12 + s 2 y 22 + s 3 y 32 = δ
Les lignes de niveaux d’une densité de probabilité gaussienne sont des ellipses en dimen-
sion d = 2 ou des ellipsoïdes en dimension d = 3, centrées en la moyenne de la densité. En
effet, une densité gaussienne de moyenne µ et de matrice de covariance Σ s’écrit :
1 1 T
Σ−1 (x−µ)
f µ,Σ (x) = e − 2 (x−µ)
(2π)d /2 |Σ|1/2
Une ligne de niveau est formée des x tels que f µ,Σ (x) = c où c est une constante positive, donc
(en passant au logarithme) ses points vérifient :
(x − µ)T Σ−1 (x − µ) = K
où K est un paramètre réel.
Une matrice de covariance est symétrique définie positive par définition, donc son in-
verse également. Les lignes de niveau des densités de probabilité gaussiennes sont donc bien
des ellipses ou ellipsoïdes centrés en µ lorsque K > 0, ou l’ensemble vide lorsque K < 0. La
discussion précédente nous indique que les vecteurs propres de Σ portent les axes de l’el-
lipse ou ellipsoïde, et que la longueur de ces axes est proportionnelle aux valeurs propres
de Σ. Dans le cas où la matrice de covariance est diagonale (les composantes du vecteur
gaussien étant alors décorrélées), la longueur des axes est proportionnelle à l’écart-type de la
composante. Les ellipses ou ellipsoïdes correspondant aux lignes de niveau montrent bien la
répartition des réalisations du vecteur gaussien.
Rappels d’optimisation
À plusieurs reprises dans ce cours nous avons à optimiser des fonctions convexes. Rap-
pelons quelques propriétés de ces fonctions.
B.1.1 Définition
Résoudre un problème d’optimisation convexe consiste à chercher le minimum d’une
fonction f convexe sur un ensemble (domaine) E ⊂ Rd convexe.
On rappelle qu’un ensemble E est convexe si pour toute paire de points (x 1 , x 2 ) ∈ E ×E , le
segment [x 1 , x 2 ] est inclus dans E , soit :
Une fonction à valeurs réelles est convexe sur E convexe si pour toute paire de points (x 1 , x 2 ) ∈
E × E , la corde joignant f (x 1 ) et f (x 2 ) est au dessus du graphe de f entre x 1 et x 2 , soit :
Lorsque l’inégalité est stricte avec x 1 ̸= x 2 et α ∈]0, 1[, f est dite strictement convexe.
B.1.2 Propriétés
La convexité implique l’inégalité suivante (appelée inégalité de Jensen), souvent très utile.
Proposition B.1 Soient f est une fonction convexe sur un domaine E convexe, x 1 , . . . , x n ∈ E ,
α1 , . . . , αn Ê 0 tels que i αi = 1 alors :
P
à !
n n
αi x i É αi f (x i )
X X
f
i =1 i =1
ANNEXE B. RAPPELS D’OPTIMISATION 168
En d’autres termes, l’image par f d’une moyenne pondérée d’un ensemble de points est in-
férieure à la même moyenne pondérée des images de ces points.
Si f est de classe C 1 , on dispose de la caractérisation suivante :
∀ (x 1 , x 2 ) ∈ E × E , f (x 1 ) Ê f (x 2 ) + (x 1 − x 2 ) · ∇ f (x 2 )
Ceci signifie que le graphe d’une fonction convexe est au dessus de tout hyperplan tangent à
ce graphe.
Si f est de classe C 2 , on dispose de la caractérisation suivante :
Démonstration
Si x ∗ est minimum local, soit y ∈ E . Par définition de la convexité, pour tout α ∈ [0, 1]
et y ∈ E ,
f (αy + (1 − α)x ∗ ) É α f (y) + (1 − α) f (x ∗ )
soit :
f (αy + (1 − α)x ∗ ) − f (x ∗ ) É α( f (y) − f (x ∗ ))
Comme x ∗ est minimum local, pour α assez petit le membre de gauche est positif, donc le
membre de droite aussi, quel que soit y ∈ E . x ∗ est donc minimum global.
Supposons f de classe C 1 et E ouvert. Si x ∗ est minimum local, alors ∇ f (x ∗ ) = 0. Réci-
proquement, si ∇ f (x ∗ ) = 0, d’après la caractérisation de la convexité ci-dessus :
∀ y ∈ E , f (y) Ê f (x ∗ ) + (y − x ∗ ) · 0
En effet, soit x satisfait les contraintes et alors maxλi Ê0 L(x, λ) = f (x) (car pour maximiser
L(x, λ) il faut annuler les λi , les g i (x) étant négatifs), soit x ne satisfait pas les contraintes et
alors maxλÊ0 L(x, λ) = +∞ (car pour au moins un i , g i (x) > 0) mais dans ce cas x ne sera pas
minimum de f .
Le problème dual au sens de Lagrange du problème d’optimisation original consiste donc
à résoudre :
arg max minn L(x, λ)
λÊ0 x∈R
Comme f et les g i sont convexes et les λi sont positifs, L(x, λ) est convexe en la va-
riable x. Cette fonction, qui est différentiable, est donc minimum en x qui annule le gradient
∇x L(x, λ), et cette condition suffit à définir x optimal.
Le problème dual s’écrit donc :
Proposition B.5 x ∗ est solution du problème primal si et seulement s’il existe λ∗ Ê 0 tel que :
∇x L(x ∗ , λ∗ ) = 0
½
∀ 1 ≤ i ≤ N , λ∗i g i (x ∗ ) = 0
f (x 1 ) = f x 0 − η f ′ (x 0 ) = f (x 0 ) − η f ′ (x 0 )2 + o(|x 1 − x 0 |)
¡ ¢
∀ n ∈ N∗ , x n+1 = x n − η f ′ (x n )
les valeurs de f (x n ) sont décroissantes jusqu’à un certain rang n ∗ au delà duquel la suite (x n )
est susceptible d’osciller autour de l’optimum cherché. Il faut donc définir un critère d’arrêt
pour éviter de boucler indéfiniment. Par exemple, on peut définir à l’avance un petit τ >
0 et arrêter l’algorithme lorsque | f ′ (x n )| É τ. Par ailleurs, le comportement de l’algorithme
dépend fortement du pas η : un trop grand pas peut entraîner des oscillations de grande
amplitude autour de l’optimum que l’on n’atteint jamais, et un trop petit pas impliquera une
convergence lente.
Bien entendu, par cette méthode on ne peut trouver qu’un minimum local : selon le point
de départ x 0 on pourrait converger vers un autre minimum local.
La figure B.1 illustre la discussion.
∀ n ∈ N∗ , x n+1 = x n − η∇ f (x n )
où η > 0 est un paramètre et ∇ f (x) désigne le gradient de f en x : c’est le vecteur fait des d
dérivées partielles de f en x.
Autrement écrit, pour la i -ème composante (1 É i É d ) :
i ∂ fi
∀ n ∈ N∗ , x n+1 = x ni − η (x n )
∂x i
F IGURE B.1 – Illustration de la recherche du minimum d’une fonction réelle. La suite des (x n )
a l’air de converger vers le minimum local x ∗ . Par contre, la suite des (x n′ ) oscille autour d’un
minimum local à cause d’un pas η choisi trop grand. Rappelons que plus la pente du graphe
de f est prononcée en x, plus | f ′ (x)| est grand et donc plus l’écart η| f ′ (x n )| entre x n et x n+1 est
grand.
Si le pas η est assez petit, un développement limité nous fournit pour tout n ∈ N, f (x n+1 ) =
f (x n − η∇ f (x n )) = f (x n ) − η∇ f (x n ) · ∇ f (x n ) + o(∥x n+1 − x n ∥), soit, à l’ordre 1 :
°2
f (x n+1 ) = f (x n ) − η °∇ f (x n )°2
°
Les valeurs successives de f (x n ) sont décroissantes jusqu’à un certain rang pour η « pas trop
grand », comme dans l’exemple introductif.
Cet algorithme cherchant un minimum avec un pas η constant est l’algorithme du gra-
dient à pas constant. Consultez un cours sur ce sujet pour savoir comment choisir η n à
chaque itération, voire choisir une matrice A n telle que x n+1 = x n − ηA n ∇ f (x n ), de manière à
accélérer la convergence.
N
X
E (x) = E i (x)
i =1
E(w 1 ,w 2 ) - E(w 1 ,w 2 )
2
1.5
15 1
10
0.5
5
E
w2
0
0
-5 -0.5
-10 -1
2
2 -1.5
0
0 -2
w2 w1
-2 -2 -2 -1 0 1 2
w1
N
x n+1 = x n − η
X
∇E i (x n )
i =1
— stocker tous les ∇E i (x n ) avant d’en faire la somme peut prendre de la place en mémoire,
— certains termes ∇E i (x n ) peuvent être petits devant d’autres (ou devant la somme par-
tielle à laquelle il faut les ajouter) et ne pas être pris en compte dans la somme à cause
de la précision limitée de l’arithmétique des ordinateurs 1 ,
— il faut sommer les N gradients avant de mettre à jour x. Pensez à la difficulté de pro-
céder à l’apprentissage d’un réseau de neurones avec un nombre d’exemples N de un
1. Selon la norme IEEE 754 (implantée par tout compilateur/machine raisonnable), en double précision, 1 +
x = 1 dès que x É 2−53 ≃ 1.1102e − 16. En simple précision 1 + x = 1 dès que x É 2−24 ≃ 5.96e − 8. Même si cela
change depuis peu, les GPU ont longtemps été beaucoup plus rapides à effectuer des calculs en simple précision
qu’en double précision.
million par exemple : il faudrait parcourir toute la base d’apprentissage avant de com-
mencer à mettre à jour les poids du réseau.
Les E n étant traités successivement, on parle d’algorithme online. Dans le cas d’un pro-
blème d’apprentissage, cela revient à présenter les observations étiquetées les unes après les
autres après les avoir mélangées aléatoirement. À chaque étape, la valeur de la fonction E ne
diminue pas forcément. Comme x est mis à jour après le calcul de chaque gradient ∇E i , x
ne se déplace pas forcément dans la direction du minimum de E cherché : on observe géné-
ralement des oscillations qui « ralentissent » la convergence. Pour limiter ce phénomène, on
peut faire la mise à jour après le calcul (potentiellement en parallèle) de quelques gradients
dont on moyenne l’influence. On parle alors d’algorithme par « mini-lot », compromis entre
le gradient stochastique et la descente classique qui prend en compte le lot complet des N
termes E i . Il semble que ces oscillations dues au caractère stochastique de l’algorithme ont
pour avantage de lui permettre de ne pas rester piégé dans des minima locaux comme l’algo-
rithme de descente classique.
Une autre manière de réduire les oscillations dans la descente est de remplacer, dans la
mise à jour x ← x − ∆x où
∆x = η∇E φ(n) (x)
où β ∈ [0, 1]. Cela permet d’amortir l’influence du gradient en le moyennant avec la dernière
valeur de ∆x.
Généralement, on intègre le terme (1 − β) dans le pas η pour écrire :
Il s’agit de la méthode du moment (SGD with momentum) : on fait une moyenne pondérée
entre l’ancienne valeur de ∆x et le gradient courant.
La méthode du moment de Nesterov consiste à calculer :
Unsupervised learning, 11
Validation
holdout, 33
leave-one-out, 33
croisée, 20, 33
Vanishing gradient, 145, 153
Variable, 11, 19
d’écart, 105
Volume de la boule unité, 24