FONDEMENTS MATHÉMATIQUES

DE L’APPRENTISSAGE STATISTIQUE

par

Christophe Giraud

Résumé. L’objectif d’un algorithme de classification est de prédire

au mieux la classe d’un objet à partir d’observations de cet objet. Un
exemple typique est le filtre à spam des messageries électroniques
qui prédisent (plus ou moins bien) si un courriel est un spam ou
non. Nous introduisons dans ces notes les principaux concepts fon-
damentaux de la théorie de la classification statistique supervisée
et quelques uns des algorithmes de classification les plus populaires.
Nous soulignons chemin faisant l’importance de certains concepts
mathématiques, parmi lesquels la symétrisation, la convexification,
les inégalités de concentration, le principe de contraction et les es-
paces de Hilbert à noyau reproduisant.

1. Introduction
En ce début de siècle, nous observons un accroissement phéno-
ménal de l’utilisation des mathématiques, à la fois dans l’industrie
et dans les laboratoires scientifiques. Cet essor de l’importance des
mathématiques va de pair avec l’explosion des volumes de données
collectées et l’accroissement de la puissance de calculs des ordinateurs.
Dans l’industrie, la modélisation mathématique apparait à tous les
stades de la vie d’un produit. Depuis la conception technique, avec
force de simulations numériques, via la production, avec l’optimisa-
tion des ressources et des flux, jusqu’au marketing et la distribution
avec des prévisions basées sur l’analyse de grandes bases de données.
Dans les laboratoires scientifiques, la modélisation mathématique de-
vient de plus en plus cruciale, en particulier en biologie et médecine
où les scientifiques doivent extraire des informations pertinentes des
54 CHRISTOPHE GIRAUD

données massives qu’ils produisent grâce aux récents développements

biotechnologiques.
La classification automatique est peut-être l’un des usages quoti-
diens les plus invasifs des mathématiques. L’objectif de la classifica-
tion automatique est de prédire au mieux la classe y d’un objet x à
partir d’observations de ce dernier. Un exemple typique est le filtre à
spam de notre messagerie électronique qui prédit (plus ou moins bien)
si un courriel est un spam ou non. La classification automatique est
omniprésente dans notre quotidien, filtrant nos courriels, lisant auto-
matiquement les codes postaux sur nos lettres ou reconnaissant les
visages sur les photos que nous publions sur les réseaux sociaux. Elle
est aussi extrêmement importante en sciences, par exemple en mé-
decine pour effectuer des diagnostics précoces à partir de données à
hauts débits, ou pour la recherche in silico de médicaments efficaces.
Nous introduisons dans ces notes les principaux concepts fonda-
mentaux de l’apprentissage statistique (supervisé). Nous décrivons
dans la partie 2 la modélisation mathématique d’un problème géné-
rique de classification. Dans la partie 3, nous analysons la précision
prédictive d’un algorithme universel de classification et dans la par-
tie 4 nous dérivons de cet algorithme théorique des algorithmes numé-
riquement implémentables et populaires. Les appendices rassemblent
des résultats techniques nécessaires pour la définition et l’analyse des
algorithmes de classification.

2. Modélisation mathématique
Par soucis de simplicité, nous allons nous restreindre au cas où il y a
seulement deux classes (comme pour le filtre à spam). Le problème de
la classification automatique peut alors être modélisé de la manière
suivante. Soit X un espace mesuré. On observe conjointement un
point X œ X et une étiquette Y œ {≠1, +1}. Notre objectif est de
construire une fonction h : X æ {≠1, +1}, appelée classifieur, telle
que h(X) prédit au mieux l’étiquette Y .
Supposons que le couple (X, Y ) œ X ◊ {≠1, +1} est issu d’un
tirage selon une loi P. Pour un classifieur h : X æ {≠1, +1} donné,
la probabilité de mauvaise classification est
L(h) = P(Y ”= h(X)).
 APPRENTISSAGE STATISTIQUE 55

Comme |Y ≠h(X)| œ {0, 2}, nous avons par le théorème de Pythagore

1 Ë È
L(h) = E (Y ≠ h(X))2
4
1 Ë È 1 Ë È
= E (Y ≠ E [Y |X])2 + E (E [Y |X] ≠ h(X))2 .
4 4
En conséquence, L(h) est minimal pour le classifieur de Bayes
hú (X) = sign(E [Y |X]) où sign(x) = 1x>0 ≠ 1x60 pour x œ R.
Lorsque la loi P est connue, il suffit donc d’utiliser le classifieur de
Bayes hú pour avoir la plus petite probabilité possible de mauvaise
classification.
Malheureusement, la loi P est en général inconnue et on ne peut
donc pas calculer le classifieur de Bayes hú . En pratique, nous avons
uniquement accès à des données dites d’apprentissage (Xi , Yi )i=1,...,n
i.i.d. de loi P et notre objectif est de construire à partir de ces données
d’apprentissage un classifieur h ‚ : X æ {≠1, +1} tel que L(h)≠L(h
‚ ú)
est aussi petit que possible.

3. Minimisation du risque empirique

Comme la loi P est inconnue, nous ne pouvons pas calculer la pro-
babilité de mauvaise classification L(h). On peut cependant calculer
à la place la probabilité empirique de mauvaise classification
1ÿ
n
Ln (h) :=
‚ 1Yi ”=h(Xi ) = P
‚ n (Y ”= h(X)),
n i=1

‚ n = 1 qn ”
où P n i=1 (Xi ,Yi ) . À un ensemble H de classifieurs, appelé
dictionnaire, on peut associer le classifieur de minimisation du risque
empirique
(1) ‚ œ argmin L
h H
‚ n (h).
hœH

La définition de ce classifieur est très naturelle, cependant deux ques-

tions fondamentales se posent immédiatement : quel dictionnaire H
choisir ? et comment h‚ se comporte-t-il comparativement à hú ? Ces
H
deux questions sont bien évidemment fortement reliées. En décom-
posant la différence entre les probabilités de mauvaise classification
56 CHRISTOPHE GIRAUD

Figure 1. Exemples de classifications produites par différents

dictionnaires. Gauche : avec des classifieurs linéaires Hlin . Centre :
avec des classifieurs polygonaux Hpoly . Droite : avec des classi-
fieurs basés sur des formes quadratiques.

‚ ) et L(hú ), on obtient
L(h H

0 6 L(h
‚ ) ≠ L(hú ) = min L(h) ≠ L(hú ) + L(h
H
‚ ) ≠ min L(h) .
H
hœH hœH
¸ ˚˙ ˝ ¸ ˚˙ ˝
erreur d’approximation erreur stochastique
Le premier terme mesure la qualité de l’approximation de hú par
un classifieur h œ H . Cette erreur d’approximation est purement
déterministe et élargir le dictionnaire H ne peut que la réduire. Le
second terme mesure l’erreur résultant de la minimisation sur h œ H
de la probabilité empirique de mauvaise classification L ‚ n (h) au lieu
de la vraie probabilité de mauvaise classification L(h). Ce terme est
stochastique et il tend à augmenter lorsque H grossit. Ce phéno-
mène est illustré Figure 1. Dans cette illustration dans X = R2 , les
classifieurs du dictionnaire Hlin = {h(x) = sign(Èw, xÍ) : ÎwÎ = 1}
ne sont pas suffisamment flexibles et ils produisent une classi-
fication de mauvaise qualité. Dans ce cas, l’erreur d’approxi-
mation est grande. À l’opposé, les classifieurs du dictionnaire
Hpoly = {h(x) = 2 1A (x) ≠ 1 : A polygone dans X } sont très
flexibles et ils peuvent toujours reproduire exactement la classi-
fication des données (Xi , Yi )i=1,...,n . L’erreur empirique L ‚ n (h
‚
Hpoly )
est donc toujours nulle, mais hHpoly tend a mal classifier une nouvelle
‚
donnée (X, Y ) et l’erreur stochastique L(h ‚ ) ≠ min
H hœH L(h) est
grande. Le dernier exemple, basé sur un ensemble moins flexible de
classifieurs quadratiques produit de meilleurs résultats.
Pour choisir un bon dictionnaire H , il faut donc trouver un bon
équilibre entre les propriétés d’approximation de H et sa taille. La
 APPRENTISSAGE STATISTIQUE 57

première étape pour développer un principe de sélection de diction-

naire H est de quantifier la probabilité de mauvaise classification du
minimiseur du risque empirique h ‚ .
H

3.1. Probabilité de mauvaise classification avec h

‚
H

Comme mentionné ci-dessus, augmenter la taille de H tend à

augmenter l’erreur stochastique L(h ‚ ) ≠ min
H hœH L(h). En fait,
ce n’est pas exactement la taille du dictionnaire qui compte, mais
plutôt sa flexibilité en terme de classification. Par exemple, nous
ne pouvons pas classifier correctement les trois points étiquetés
)! " ! " ! "*
(0, 1), +1 , (1, 1), ≠1 , (1, 0), +1 avec les classifieurs dans Hlin .
A l’inverse, pour tout ensemble (xi , yi )i=1,...,n de points étiquetés, il
existe h œ Hpoly tel que h(xi ) = yi .
Nous quantifions cette flexibilité de classification par le coefficient
d’éclatement

(2) Sn (H ) = max card {(h(x1 ), . . . , h(xn )) : h œ H } ,

(x1 ,...,xn )œX n

qui donne le nombre maximum d’étiquetages différents de n points

qui peuvent être produits par les classifieurs dans H . Par exemple,
comme on peut obtenir à partir de Hpoly tous les étiquetages pos-
sibles de n points (distincts), nous avons Sn (Hpoly ) = 2n . À l’in-
verse, le nombre d’étiquetages possibles de n points avec les classi-
fieurs dans Hlin est plus limité. En effet, la Proposition 1 Partie 3.3
implique que Sn (Hlin ) 6 (n + 1)2 . Le prochain théorème nous four-
nit une borne supérieure de l’erreur stochastique et un intervalle de
confiance pour la probabilité de mauvaise classification L(h ‚ ) en
H
terme du coefficient d’éclatement.

Théorème 1 (Contrôle de l’erreur stochastique). Pour tout t > 0, nous

avons avec probabilité au moins 1 ≠ e≠t
Û Ú
2 log(2 SH (n)) 2t
(3) ‚
L(h H ) ≠ min L(h) 6 4 +
hœH n n
et
Û Ú
- - 2 log(2 SH (n)) t
(4) ‚ )≠L
-L(h ‚ n (h
‚ )- 6 2 +
2n
H H
n
58 CHRISTOPHE GIRAUD

Démonstration. Nous segmentons la preuve en trois lemmes. Le pre-

mier lemme montre que les termes de gauche dans (3) et (4) peuvent
être bornés à l’aide du maximum sur H de la différence entre l’erreur
empirique de mauvaise classification et la vraie erreur de mauvaise
classification
- -
(5) ‚ (H ) = sup -L
n
‚ n (h) ≠ L(h)-.
hœH

Lemme 1.1. Pour tout dictionnaire H et entier n, nous avons les

bornes supérieures
- -
‚ ) ≠ min L(h) 6 2 ‚ n (H )
L(h et ‚ )≠L
-L(h ‚ n (h
‚ )- 6 ‚ n (H ).
H H H
hœH

Démonstration. Pour tout h œ H , nous avons L

‚ n (h
‚ ) 6 L
H
‚ n (h) et
donc
‚ ) ≠ L(h) = L(h
L(h ‚ )≠L
‚ n (h
‚ )+L
‚ n (h
‚ ) ≠ L(h)
H H H H
‚ )≠L
6 L(h ‚ n (h
‚ )+L
‚ n (h) ≠ L(h)
H H

6 2 ‚ n (H ).
Comme cette inégalité est vraie pour tout h œ H , nous en déduisons
directement la première borne du Lemme 1.1. La seconde borne est
évidente.
Pour démontrer le Théorème 1, il reste à prouver qu’on a
Û Ú
‚ (H ) 6 2 2 log(2 SH (n)) t
+
2n
n
n
avec probabilité au moins 1≠e≠t . Nous segmentons la preuve de cette
borne en deux lemmes.
Lemme 1.2. Avec probabilité 1 ≠ e≠t , nous avons
Ë È Ú t
‚ (H ) 6 E ‚ (H ) + .
2n
n n

Démonstration. Nous avons ‚ n (H ) = F ((X1 , Y1 ), . . . , (Xn , Yn ))

avec
F : (X ◊ {≠1, +1})n ≠æ R
1 -ÿ
-
n -
-
((x1 , y1 ), . . . , (xn , yn )) ‘≠æ sup - 1yi ”=h(xi ) ≠ L(h)- .
n hœH i=1
 APPRENTISSAGE STATISTIQUE 59

Pour tout (x1 , y1 ), . . . , (xn , yn ), (xÕi , yiÕ ) œ X ◊ {≠1, +1}, nous avons
-
-F ((x1 , y1 ), . . . , (xÕ , y Õ ), . . . , (xn , yn ))
i i
1 -
≠ F ((x1 , y1 ), . . . , (xi , yi ), . . . , (xn , yn ))- 6
.
n
En conséquence, l’inégalité de concentration de McDiarmid (voir
Théorème 4 de l’Appendice B), nous assure
Ë qu’avec
È probabilité au
2
moins 1≠e≠2ns , nous avons n (H ) 6 E n (H ) +s. Le Lemme 1.2
‚ ‚

en découle (avec le changement de variable s = t/(2n)).

Il reste à borner l’espérance de ‚ n (H ) à l’aide de SH (n).

Lemme 1.3. Pour tout dictionnaire H , nous avons l’inégalité

Û
Ë È 2 log(2 SH (n))
E ‚ n (H ) 6 2 .
n
Démonstration. La preuve du Lemme 1.3 est basée sur un argument
classique et élégant de symétrisation.
La première étape de la symétrisation est de représenter la proba-
bilité de mauvaise classification L(h) comme l’espérance de la proba-
bilité empirique de mauvaise classification
C D
1ÿn
L(h) = P(Y =
” h(X)) = E
 1Y ”=h(X ) ,
n i i
i=1

où (X
 i , YÂi )i=1,...,n est indépendant de (Xi , Yi )i=1,...,n et est identique-
ment distribué. Dans la suite, nous noterons E Â pour l’espérance par
rapport aux variables (Xi , Yi )i=1,...,n et E pour l’espérance par rap-
 Â
port aux variables (Xi , Yi )i=1,...,n . Les inégalités de Jensen et Fatou
nous donnent
- C C D -D
Ë È -1 ÿ n
1 ÿn -
- -
E ‚ n (H ) = E sup - 1Yi =
” h(Xi ) ≠ E
 1Y ”=h(X ) -
hœH - n n i i -
i=1 i=1
C D
 sup -- 1
- ÿ n 1 2-
-
6 EE 1Yi ”=h(Xi ) ≠ 1YÂ ”=h(XÂ ) - .
hœH n i=1
i i

La seconde étape consiste à capitaliser sur la symétrie des va-

riables 1Yi ”=h(Xi ) ≠ 1YÂ ”=h(XÂ ) . Nous introduisons n variables aléa-
i i

toires i.i.d. (‡i )i=1,...,n indépendantes de (Xi , Yi , X

 i , YÂi )i=1,...,n et
60 CHRISTOPHE GIRAUD

de loi P‡ (‡i 1= 1) = P‡ (‡i = ≠1) =2 1/2. Par symétrie, on re-

! "
marque que ‡i 1Yi ”=h(Xi ) ≠ 1YÂ ”=h(XÂ ) a la même loi que
1 2 i i i=1,...,n
1Yi ”=h(Xi ) ≠ 1YÂ ”=h(XÂ ) , donc nous obtenons
i i i=1,...,n
C D
Ë È -1 ÿ
n 1 2-
- -
E ‚ n (H ) 6 EEE
 ‡ sup - ‡i 1Yi ”=h(Xi ) ≠ 1Y ”=h(X ) -
hœH n i=1
i i

C D
-1 ÿn -
- -
6 2EE‡ sup - ‡i 1Yi ”=h(Xi ) -
hœH n i=1
C D
-1 ÿ
n -
- -
62 max max E‡ sup - ‡i 1yi ”=h(xi ) - ,
yœ{≠1,+1}n xœX n hœH n i=1

où la seconde inégalité découle de l’inégalité triangulaire. Pour tout

(x, y) œ X n ◊ {≠1, +1}n , nous introduisons l’ensemble
Ó Ô
VH (x, y) = (1y1 ”=h(x1 ) , . . . , 1yn ”=h(xn ) ) : h œ H .
Ë È
La dernière majoration de E ‚ n (H ) peut s’écrire comme
C D
Ë 2 È
E ‚ n (H ) 6 ◊ max n maxn E‡ sup |ȇ, vÍ| ,
n yœ{≠1,+1} xœX vœVH (x,y)

où Èx, yÍ est le produit scalaire canonique sur Rn . Remarquons au

passage qu’entre le membre de gauche et le membre de droite nous
avons remplacé l’espérance sous la probabilité inconnue P par une
espérance sous la probabilité connue P‡ . Pour tout y œ {≠1, +1}n
remarquons aussi qu’il y a une bijection entre VH (x, y) et l’ensemble
{(h(x1 ), . . . , h(xn )) : h œ H }. En conséquence, nous avons la majo-
ration
max max card(VH (x, y)) 6 Sn (H ).
yœ{≠1,+1}n xœX n

Au regard des deux dernières inégalités, il suffit de démontrer que

C D
Ò
(6) E‡ sup |ȇ, vÍ| 6 2n log (2 card(V )),
vœV
pour tout ensemble V µ {≠1, 0, +1}n
 APPRENTISSAGE STATISTIQUE 61

pour conclure la preuve du Lemme 1.3. Démontrons (6). Avec la nota-

tion V # = V fi ≠V , l’inégalité de Jensen nous donne pour tout s > 0
C D C D C D
1
E‡ sup |ȇ, vÍ| = E‡ sup ȇ, vÍ 6 log E‡ sup e sȇ,vÍ
vœV vœV # s vœV #
Q R
1 ÿ Ë È
(7) 6 log a E‡ esȇ,vÍ b .
s # vœV

En combinant le fait que les ‡i sont indépendants, que (ex + e≠x ) 6

2
2ex /2 pour tout x œ R et que vi2 œ {0, 1} pour tout v œ V # , nous
obtenons
Ë È n
Ÿ n
Ÿ 1
E‡ esȇ,vÍ = E‡ [esvi ‡i ] = (esvi + e≠svi )
i=1 i=1
2
Ÿn
2 v 2 /2 2 /2
6 es i 6 ens .
i=1

En injectant cette majoration dans (7), nous obtenons

C D
log(card(V # ) ns
E‡ sup |ȇ, vÍ| 6 + pour tout s > 0.
vœV s 2
Ò
Le terme de droite est minimal pour s = 2 log(card(V # ))/n, ce qui
nous donne la majoration
C D Ò
E‡ sup |ȇ, vÍ| 6 2n log(card(V # )) .
vœV

Nous obtenons finalement la borne (6) en remarquant que card(V # ) 6

2 card(V ). La preuve du Lemme 1.3 est complète.

Les bornes (3) et (4) s’obtiennent directement en combinant les

trois lemmes.

3.2. Sélection de dictionnaire

Soit {H1 , . . . , HM } une collection de dictionnaires de classifieurs.
Nous aimerions sélectionner parmi cette collection, le dictionnaire Hú
avec la plus petite probabilité de mauvaise classification L(h ‚ ). Ce
Hú
dictionnaire Hú , dit dictionnaire oracle, dépend de la probabilité in-
connue P, il n’est donc malheureusement pas connu du statisticien.
Dans cette partie, nous allons développer à partir du Théorème 1 une
62 CHRISTOPHE GIRAUD

procédure reposant sur les données pour sélectionner parmi la col-

lection {H1 , . . . , HM } un dictionnaire Hm ‚ ayant des performances
similaires à celles de Hú .
Le dictionnaire oracle Hú est obtenu en minimisant la probabilité
de mauvaise classification L(h ‚ ) sur H œ {H1 , . . . , HM }. Une pre-
H
mière idée est de sélectionner Hm ‚ en minimisant sur la collection
{H1 , . . . , HM } la probabilité empirique de mauvaise classification
‚ n (h
L ‚ ). Cette procédure de sélection ne donne pas de bons résultats
H
car pour tout H µ H Õ on a toujours L ‚ n (h
‚ Õ) 6 L
H
‚ n (h
‚ ), donc
H
la procédure tend à sélectionner le dictionnaire le plus gros possible.
Pour bâtir une bonne procédure de sélection, nous devons prendre en
compte les fluctuations de L ‚ n (h
‚ ) autour de L(h
H
‚ ). La borne (4) du
H
Théorème 1 nous offre un contrôle de ces fluctuations. En élaborant
à partir de cette borne, nous obtenons le résultat suivant.

Théorème 2 (Sélection de dictionnaire). Considérons la procédure de

sélection de dictionnaire
Ó Ô
‚ = argmin
m ‚ n (h
L ‚
Hm ) + pen(Hm ) ,
m=1,...,M
Û
2 log(2 Sn (H ))
avec pen(H ) = 2 .
n
Alors, pour tout t > 0, avec probabilité au moins 1 ≠ e≠t nous avons

(8) L(h
‚
H ) Û
‚
m ; <
2 log(M ) + 2t
6 min inf L(h) + 2 pen(Hm ) + .
m=1,...,M hœHm n
Avant de prouver le Théorème 2, commentons la borne (8). Comme
minhœH L(h) 6 L(h‚ ), nous obtenons avec probabilité 1 ≠ e≠t que
H
Û
2 log(M ) + 2t
H ) 6 L(hHú ) + 2 pen(Hú ) +
‚
L(h ‚ .
‚
m n
En particulier, cela nous permet de comparer la probabilité de mau-
vaise classification du classifieur sélectionné à celle du meilleur clas-
) *
sifieur parmi la collection h ‚ ,...,h
H1
‚
HM .
Remarquons aussi que le second terme de la borne (8) augmente

en 2 log(M )/n avec le nombre M de dictionnaires candidats. Enfin,
nous noterons que les résultats restent valides si on prend pen(H )

plus grand que 2 2 log(2 Sn (H ))/n.
 APPRENTISSAGE STATISTIQUE 63

Démonstration du Théorème 2 - -
Rappelons la notation ‚ n (H ) = suphœH -‚ Ln (h)≠L(h)-. Les Lemmes 1.2
et 1.3 nous assurent qu’avec probabilité au moins 1 ≠ e≠t nous avons
Ú
log(M ) + t
(9) ‚ n (Hm ) 6 pen(Hm ) + ,
2n
simultanément pour tout m = 1, . . . , M.

En conséquence, le Lemme 1.1 et la définition du critère de sélection nous

donnent qu’avec probabilité au moins 1 ≠ e≠t
Ú
log(M ) + t
L(‚hH ) 6 L ‚ n (‚
hH ) + pen(Hm ) +
‚ ‚ ‚ 2n
(10)
m m
Ú
Ó Ô log(M ) + t
6 min L‚ n (‚
hHm ) + pen(Hm ) + .
m=1,...,M 2n

Pour conclure, il nous suffit de contrôler L ‚ n (‚

hHm ) en fonction de
inf hœHm L(h). Cela peut être fait directement en combinant les inéga-
lités (3) et (4), mais la majoration résultante peut être améliorée par le
raisonnement ci-dessous.
Pour comparer L ‚ n (‚
hHm ) à inf hœHm L(h), commençons par remarquer
que pour tout h œ Hm nous avons
‚ n (‚
L h Hm ) 6 L
‚ n (h) 6 L(h) + ‚ n (Hm ),

donc en prenant l’infimum sur h œ Hm nous obtenons pour tout m =

1, . . . , M
‚ n (‚
L hHm ) 6 inf L(h) + ‚ n (Hm ).
hœHm

En combinant cette majoration avec (9) et (10), on trouve

; < Ú
log(M ) + t
L(hH ) 6 min
‚ inf L(h) + 2 pen(Hm ) + 2 .
‚
m m=1,...,M hœHm 2n
La preuve du Théorème 2 est complète.

Remarque. En combinant (9) avec le Lemme 1.1, on obtient un inter-

valle de confiance pour la probabilité de mauvaise classification
1 # $ 2
H ) œ Ln (hH ) ≠ ”(m,
‚ n (h
H ) + ”(m,
‚ t) > 1 ≠ e≠t
‚
P L(h ‚ ‚ ‚ t), L ‚
‚
m ‚
m ‚
m
Û
log(M ) + t
avec ‚ t) = pen(Hm
”(m, ‚) + .
2n
64 CHRISTOPHE GIRAUD

3.3. Dimension combinatoire de Vapnik-Chervonenkis

Le calcul des coefficients d’éclatement Sn (H ) peut être complexe
en pratique. Cependant, une propriété combinatoire remarquable de
ces coefficients d’éclatement permet d’obtenir une majoration simple
de Sn (H ), ne dépendant de H qu’à travers une unique quantité, la
dimension de Vapnik-Chervonenkis de H définie ci-dessous.
Par convention on posera S0 (H ) = 1. On appelle VC-dimension
de H l’entier dH défini par
Ó Ô
dH = sup d œ N : Sd (H ) = 2d œ N fi {+Œ} .
Elle correspond au nombre maximum de points de X qui peuvent
être classifiés de toutes les façons possibles par les classifieurs de H .
La proposition suivante donne une majoration du coefficient d’écla-
tement Sn (H ) en fonction de la VC-dimension dH .

Proposition 1 (Lemme de Sauer). Soit H un ensemble de classifieurs

de VC-dimension dH finie. Pour tout n œ N, on a
Y
n!
] pour n > i
d
ÿH
Sn (H ) 6 Cn 6 (n + 1)
i dH
avec Cn = i! (n ≠ i)!
i
[
i=0 0 pour n < i.
Démonstration. Nous commençons par prouver par récurrence sur k
l’inégalité
d
ÿH
(11) Sk (H ) 6 Cki
i=0
pour tout H de VC-dimension finie dH .
Considérons dans un premier temps le cas k = 1. Si dH = 0, aucun
point ne peut être étiqueté de deux manières différentes, donc tous
les points ne peuvent être étiquetés que d’une seule manière. Il en
découle que S1 (H ) = 1, qui est égal à C10 . Si dH > 1, nous avons
S1 (H ) = 2 qui est égal à C10 + C11 .
Supposons maintenant que (11) est vraie pour tout k 6 n ≠ 1.
Considérons H de VC-dimension dH finie. Comme on vient de le
voir, lorsque dH = 0 tous les points peuvent être étiqueté d’une seule
manière donc Sk (H ) = 1 et (11) est vraie pour tout k. Considérons
maintenant le cas dH > 1. Soient x1 , . . . , xn œ X et définissons
H (x1 , . . . , xn ) = {(h(x1 ), . . . , h(xn )) : h œ H } .
 APPRENTISSAGE STATISTIQUE 65

L’ensemble H (x1 , . . . , xn ) ne dépend que des valeurs de h sur

{x1 , . . . , xn }, donc on peut remplacer H par F = {h|{x1 ,...,xn } : h œ H }
dans la définition de H (x1 , . . . , xn ). Comme dF est inférieur à dH ,
on peut supposer sans perte de généralité que X = {x1 , . . . , xn } et
H = F , ce que nous faisons par la suite. Considérons l’ensemble
Ó Ô
H Õ = h œ H : h(xn ) = 1 et hÕ = h ≠ 2 ◊ 1{xn } œ H .

Comme H (x1 , . . . , xn ) = H Õ (x1 , . . . , xn ) fi (H r H Õ )(x1 , . . . , xn )

nous avons

! "
(12) card (H (x1 , . . . , xn )) 6 card H Õ (x1 , . . . , xn )
! "
+ card (H r H Õ )(x1 , . . . , xn ) .

Nous allons majorer séparément le cardinal de H Õ (x1 , . . . , xn ) et

celui de (H r H Õ )(x1 , . . . , xn ).
(1) Pour commencer, remarquons que card (H Õ (x1 , . . . , xn )) =
card (H Õ (x1 , . . . , xn≠1 )) car on a h(xn ) = 1 pour tout h œ H Õ .
Ensuite, on observe que la VC-dimension dH Õ de H Õ est au plus
dH ≠ 1. En effet, si d points xi1 , . . . , xid de X = {x1 , . . . , xn }
peuvent être étiquetés de toutes les manières possibles par H Õ , alors
xn œ/ {xi1 , . . . , xid } vu que h(xn ) = 1 pour tout h œ H Õ . De plus,
l’ensemble {xi1 , . . . , xid , xn } peut être étiqueté de toutes les manières
possibles par H par définition de H Õ , donc d + 1 6 dH , ce qui
implique dH Õ 6 dH ≠ 1. En appliquant (11) avec k = n ≠ 1 on
obtient
! " ! "
card H Õ (x1 , . . . , xn ) = card H Õ (x1 , . . . , xn≠1 )
(13) dH
ÿ ≠1
6 i
Cn≠1 .
i=0

(2) Si h, hÕ œ H rH Õ vérifient h(xi ) = hÕ (xi ) pour i = 1, . . . , n≠1,

alors ils vérifient aussi h(xn ) = hÕ (xn ) par définition de H Õ . En consé-
quence, on a comme précédemment l’égalité
! " ! "
card (H r H Õ )(x1 , . . . , xn ) = card (H r H Õ )(x1 , . . . , xn≠1 ) .
66 CHRISTOPHE GIRAUD

De plus dH rH Õ est inférieur à dH car H r H Õ µ H donc l’équa-

tion (11) avec k = n ≠ 1 donne
! "
(14) card (H r H Õ )(x1 , . . . , xn )
d
ÿH
! "
= card (H r H Õ )(x1 , . . . , xn≠1 ) 6 i
Cn≠1 .
i=0

En combinant (12), (13) et (14), on obtient

d
ÿH d
ÿH d
ÿH
card (H (x1 , . . . , xn )) 6 i≠1
Cn≠1 + i
Cn≠1 = Cni ,
i=1 i=0 i=0

car Cn≠1
i + Cn≠1
i≠1
= Cni pour i > 1. Il en découle que (11) est vrai
pour k = n et la récurrence est établie.
La seconde borne de la proposition est obtenue par
d
ÿ d
ÿ d
ÿ
ni
Cni 6 6 Cdi ni = (1 + n)d .
i=0 i=0
i! i=0

La preuve de la Proposition 1 est complète.

Donnons quelques exemples de VC-dimension pour quelques dic-

tionnaires simples de X = Rd . Les preuves sont laissées en exercice.

Exemple 1 : classifieurs linéaires. La VC-dimension de l’ensemble

H = {h(x) = sign(Èw, xÍ) : ÎwÎ = 1} de classifieurs linéaires est d.

Exemple 2 : classifieurs affines. La VC-dimension de l’ensemble

H = {h(x) = sign(Èw, xÍ + b) : ÎwÎ = 1, b œ R}
de classifieurs affines est d + 1.

Exemple 3 : classifieurs hyper-rectangulaires. La VC-dimension de

l’ensemble
Ó Ô
H = h(x) = 2 1A (x) ≠ 1 : A hyper-rectangle de Rd
de classifieurs hyper-rectangulaires est 2d.

Exemple 4 : classifieurs à polygones convexes. La VC-dimension de

l’ensemble
Ó Ô
H = h(x) = 2 1A (x) ≠ 1 : A polygone convexe de Rd
 APPRENTISSAGE STATISTIQUE 67

de classifieurs par polygones convexes est +Π(prendre n points sur la

sphère unité : pour tout sous-ensemble de ces points, on peut prendre
leur enveloppe convexe comme polygone convexe).

4. De la théorie vers la pratique

4.1. Convexification du risque empirique
Les classifieurs par minimisation du risque empirique analysés pré-
cédemment possèdent de bonnes qualités statistiques, mais ils ne
peuvent pas être mis en œuvre en pratique à cause de leur coût en
temps de calcul. En effet, il n’existe pas de façon efficace de mini-
miser (1) car ni H ni L ‚ n ne sont convexes. Un certain nombre des
algorithmes de classification les plus populaires sont obtenus par une
simple relaxation convexe du problème de minimisation (1). La pro-
babilité empirique de mauvaise classification L ‚ n est remplacée par un
substitut convexe et l’ensemble des classifieurs H est remplacé par
un ensemble fonctionnel convexe F µ RX .
Considérons un ensemble convexe F de fonctions de X dans R.
Une fonction f œ F n’est pas un classifieur, mais on peut l’utiliser
pour classifier en étiquetant les points en fonction du signe de f . En
d’autres mots, on peut associer à f le classifieur sign(f ). La proba-
bilité empirique de mauvaise classification de ce classifieur peut être
réécrite sous la forme
‚ n (sign(f )) = 1 1ÿ
ÿn n
L 1{Yi sign(f )(Xi )<0} = 1 .
n i=1 n i=1 {Yi f (Xi )<0}
Remplaçons maintenant la probabilité empirique de mauvaise classi-
fication L‚ n par un substitut convexe se prêtant bien au calcul numé-
rique. Un moyen simple et efficace d’obtenir un critère convexe est
de remplacer la fonction de perte z æ 1z<0 par une fonction convexe
z æ ¸(z). Nous allons développer cette idée et considérer dans la suite
les classifieurs obtenus par la procédure

(15) h
‚ = sign(f‚ )
F F
1ÿ n
où f‚F = argmin L
‚ ¸ (f ) avec
n
‚ ¸ (f ) =
L n ¸(Yi f (Xi )).
f œF n i=1
Ce classifieur peut être calculé numériquement de façon efficace car
à la fois F et L
‚ ¸ sont convexes. De nombreux classifieurs populaires
n
68 CHRISTOPHE GIRAUD

sont obtenus en résolvant (15) pour des choix spécifiques de F et ¸,

voir par exemple les Parties 4.3 et 4.4 pour quelques exemples.
Quelques fonctions de perte convexes ¸ classiques. Il est naturel de
considérer une fonction de perte ¸ qui est décroissante et positive.
Habituellement, on demande aussi que ¸(z) > 1z<0 pour tout z œ R
car cela nous permet de donner une majoration de la probabilité de
mauvaise classification, voir le Théorème 3. Quelques fonctions de
pertes classiques sont
• la perte exponentielle ¸(z) = e≠z
• la perte logit ¸(z) = log2 (1 + e≠z )
• la perte hinge ¸(z) = (1 ≠ z)+ (avec (x)+ = max(0, x))
voir la Figure 2 pour un tracé de ces trois fonctions.

classical losses
3.0

initial
hinge
exponential
2.5

logit
2.0
loss

1.5
1.0
0.5
0.0

-2 -1 0 1 2

Figure 2. Tracé des pertes exponentielle, hinge et logit

Quelques exemples classiques d’ensembles fonctionnels F . Les prin-

cipaux exemples classiques d’ensembles fonctionnels F peuvent être
regroupés en deux classes.
 APPRENTISSAGE STATISTIQUE 69

Une première classe d’ensembles F est obtenue en prenant des

combinaisons linéaires d’une famille finie H = {h1 , . . . , hp } de clas-
sifieurs
; p
ÿ <
(16) F = f : f (x) = —j hj (x) avec —j œ C ,
j=1

où C est un sous-ensemble Ó convexe de Rq. Des choix

p
Ô typiques
pour C sont le simplexe — œ R : —j > 0, pj=1 —j 6 1 , la boule
p

{— œ Rp : |—|1 6 R} ou tout l’ensemble Rp . Ces choix apparaissent

notamment dans les méthodes de "boosting", voir Partie 4.4. Les
classifieurs de base {h1 , . . . , hp } sont souvent appelés weak learners.
Un choix populaire pour les weak learners est hj (x) = sign(xj ≠ tj )
avec tj œ R.
Un seconde classe classique d’ensembles F est obtenue en pre-
nant une boule d’une espace de Hilbert à noyaux reproduisant (qu’on
appelle RKHS, pour Reproducing Kernel Hilbert Space en anglais).
On renvoie à l’Appendice A pour une brève introduction aux RKHS.
Plus précisément, considérons un RKHS Fk de noyau k et notons
par Îf ÎF la norme hilbertienne de f œ Fk . Pour alléger les nota-
tions, dans la suite on écrira simplement F pour Fk . Minimiser L ‚¸
n
sur la boule {f œ F : Îf ÎF 6 R} est équivalent à minimiser sur F
le problème lagrangien dual

(17) f‚F = argmin L

 ¸ (f )
n
f œF
1ÿ n
avec  ¸ (f ) =
L n ¸(Yi f (Xi )) + ⁄Îf Î2F ,
n i=1

pour un certain ⁄ > 0. Ce type de classifieur apparaît notamment

dans les algorithmes de type Support Vector Machine, présentés Par-
tie 4.3. Il s’avère que le minimiseur f‚F de (17) est de la forme
n
ÿ
(18) f‚F = —‚i k(Xi , .).
i=1

En effet, notons V l’espace linéaire engendré par k(X1 , .), . . . , k(Xn , .)

et décomposons f = fV + fV ‹ sur V ü V ‹ . Par la propriété de
reproduction on a f (Xi ) = Èf, k(Xi , .)ÍF = ÈfV , k(Xi , .)ÍF = fV (Xi ),
70 CHRISTOPHE GIRAUD

donc la formule de Pythagore nous donne

1ÿ n
! "
 ¸ (fV + f ‹ ) =
L n V ¸ Yi fV (Xi ) + ⁄ÎfV Î2F + ⁄ÎfV ‹ Î2F .
n i=1

Comme ⁄ est strictement positif, tout minimiseur de f‚ of L Â ¸ doit

n
satisfaire fV ‹ = 0, donc il est de la forme (18). De plus, la propriété
‚
de reproduction nous assure de nouveau que Èk(Xi , .), k(Xj , .)ÍF =
k(Xi , Xj ) donc
.ÿ .2
. n . n
ÿ
.
. —j k(X j , .).
. = —i —j k(Xi , Xj ).
j=1 F i,j=1

Le problème de minimisation (17) est donc équivalent à

n
ÿ
(19) f‚F = —‚j k(Xj , .) avec
j=1
Y Z
n 3ÿ
]1 ÿ n 4 n
ÿ ^
—‚ = argmin ¸ —j Yi k(Xj , Xi ) + ⁄ —i —j k(Xi , Xj ) .
—œRn [n \
i=1 j=1 i,j=1

Cette formulation est cruciale en pratique, car elle réduit le problème

de minimisation infini-dimensionnel (17) à un problème de minimi-
sation n-dimensionnel qui peut être résolu efficacement. Dans la Par-
tie 4.3 sur les Support Vector Machines, nous donnerons une descrip-
tion plus précise des solutions de ce problème lorsque ¸ est la perte
Hinge.

4.2. Propriétés statistiques

Le classifieur h
‚ donné par (15) avec F et ¸ convexes a l’avan-
F
tage de se calculer facilement, mais a-t-il de bonnes propriétés statis-
tiques ?
Lien avec le classifieur de Bayes. Le minimiseur du risque empi-
rique h‚
H de la Partie 3 était un minimiseur de la version empi-
rique de la probabilité de mauvaise classification P(Y ”= h(X)) sur
un ensemble H de classifieurs. La fonction f‚F minimise à la place
la version empirique de E [¸(Y f (X))] sur un ensemble fonctionnel F .
Le classifieur h
‚ peut donc être vu comme une version empirique du
H
classifieur de Bayes hú qui minimise P(Y ”= h(X)) sur l’ensemble des
fonctions mesurables h : X æ {≠1, +1}, alors que la fonction f‚F est
 APPRENTISSAGE STATISTIQUE 71

une version empirique de la fonction fú¸ qui minimise E [¸(Y f (X))]

sur l’ensemble des fonctions mesurables f : X æ R. Une première
étape est de comprendre le lien entre le classifieur de Bayes hú et
le signe de la fonction fú¸ . Il s’avère que sous des hypothèses très
faibles sur ¸, le signe de fú¸ coïncide exactement avec le classifieur de
Bayes hú , donc sign(fú¸ ) minimise la probabilité de mauvaise classifi-
cation P(Y ”= h(X)). Démontrons maintenant ce résultat.
En conditionnant par X on obtient
E [¸(Y f (X)] = E [E [¸(Y f (X)|X]]
Ë È
= E ¸(f (X))P(Y = 1|X) + ¸(≠f (X))(1 ≠ P(Y = 1|X)) .
Supposons que ¸ est décroissante, dérivable et strictement convexe
(par exemple perte exponentielle ou logit). En minimisant l’expres-
sion ci-dessus on obtient que fú¸ (X) est solution de
¸Õ (≠f (X)) P(Y = 1|X)
= .
¸ (f (X))
Õ 1 ≠ P(Y = 1|X)
Comme ¸ est strictement convexe, on a f (X) > 0 si et seulement si
¸Õ (≠f (X))/¸Õ (f (X)) > 1, donc
fú¸ (X) > 0 ≈∆ P(Y = 1|X) > 1/2
≈∆ E[Y |X] = 2P(Y = 1|X) ≠ 1 > 0 .
Comme hú (X) = sign(E [Y |X]) (voir Partie 2), on obtient sign(fú¸ )=hú .
Cette égalité reste vraie pour la perte Hinge (exercice !).
Pour résumer la discussion ci-dessus, la fonction cible fú¸ approchée
par f‚F est intéressante pour le problème de classification car son signe
coïncide avec le meilleur classifieur possible hú .
Majoration de la probabilité de mauvaise classification. Nous nous
concentrons maintenant sur la probabilité de mauvaise classification
L(h‚ ) du classifieur h
‚ = sign(f‚ ) défini par (15). En pratique, il
F F F
est intéressant d’avoir une majoration de la probabilité de mauvaise
classification L(h
‚ ) qui puisse être évaluée à partir des données. Le
F
prochain théorème fournit une telle majoration pour des exemples
typiques d’ensembles F .
Théorème 3 (Borne de confiance pour L(h ‚ )). Pour tout R > 0, on
F
définit ¸(R) = |¸(R)≠¸(≠R)|. On suppose que la fonction de perte ¸
est convexe, décroissante, positive, –-Lipschitz sur [≠R, R] et vérifie
72 CHRISTOPHE GIRAUD

¸(z) > 1z<0 pour tout z dans R. On s’intéresse au classifieur h ‚

F
défini par (15).
(a) Lorsque F est de la forme (16) avec C = {— œ Rp : |—|1 6 R},
nous avons avec probabilité au moins 1 ≠ e≠t
Û Ú
2 log(2p) t
(20) ‚ ) 6 L
L(h ‚ ¸ (f‚ ) + 2–R + ¸(R) .
2n
F n F
n
(b) Soit F une boule de rayon R d’un RKHS de noyau k vérifiant
k(x, x) 6 1 pour tout x œ X . Alors, avec probabilité au moins 1≠e≠t ,
on a
Ú
(21) L(h ‚ ¸ (f‚ ) + 2–R
‚ ) 6 L Ô + ¸(R)
t
.
2n
F n F
n

Démonstration. Commençons par prouver une majoration générale

de L(h
‚ ) très similaire au Théorème 1.
F

Lemme 3.1. Supposons que supf œF |f (x)| 6 R < +Œ. Alors pour
toute fonction de perte ¸ vérifiant les hypothèses du Théorème 3, on a
avec probabilité au moins 1 ≠ e≠t

(22) L(h
‚ )6L
F
‚ ¸ (f‚ )
n F
C - -D Ú
2– -ÿn - t
+ maxn E‡ sup -- ‡i f (xi )-- + ¸(R)
n xœX f œF i=1 2n

où ‡1 , . . . , ‡n sont des variables aléatoires i.i.d. de loi P‡ (‡i = 1) =

P‡ (‡i = ≠1) = 1/2.

Démonstration du Lemme 3.1. La preuve de ce lemme repose sur

exactement les mêmes arguments que la preuve du Théorème 1. La
première étape est de remarquer que l’inégalité ¸(z) > 1z<0 pour
tout réel z nous donne
‚ ) = P(Y f‚ (X) < 0) 6 L¸ (f )
L(h avec L¸ (f ) = E [¸(Y f (X))]
F F
‚ ¸ (f ) + ‚ ¸ (F )
6L n n
- ¸ -
où ‚ ¸n (F ) = sup -L
‚ (f ) ≠ L¸ (f )-.
n
f œF

Comme dans le Lemme 1.2, l’inégalité de concentration de McDiarmid

(Théorème 4 de l’Appendice B) assure qu’avec probabilité au moins
 APPRENTISSAGE STATISTIQUE 73

1 ≠ e≠t on a
Ë È Ú
t
‚ ¸ (F ) 6 E ‚ ¸ (F ) +. ¸(R)
n n
2n
Pour conclure la preuve du lemme, il suffit de montrer que
C -ÿ -D
Ë È 2– - n -
(23) E n (F ) 6
‚ ¸
maxn E‡ sup -
- ‡i f (xi )-- .
n xœX f œF i=1

En suivant exactement les mêmes arguments que dans la preuve du

Lemme 1.3 (en remplaçant 1Yi ”=h(Xi ) par ¸(Yi f (Xi ))) on obtient
C
- n -D
Ë
‚ ¸ (F )
È 2 -ÿ -
E n 6 max n maxn E‡ sup -- ‡i ¸(yi f (xi ))-- .
n yœ{≠1,+1} xœX f œF i=1

Finalement, on utilise que ¸ est –-Lipschitz pour conclure : le principe

de Contraction (Proposition 5 de l’Appendice B) nous donne
C - n -D C - n -D
-ÿ - -ÿ -
E‡ sup -- ‡i ¸(yi f (xi ))-- 6 – E‡ sup -- ‡i yi f (xi )--
f œF i=1 f œF i=1
C - n -D
-ÿ -
= – E‡ sup -- ‡i f (xi )-- .
f œF i=1

En combinant les deux dernières majorations on obtient (23) et le

Lemme 3.1 est démontré.

(a) Prouvons maintenant la borne (20). L’application — æ

qn qp
i=1 ‡i j=1 —j hj (xi ) est linéaire, donc elle atteint à l’un des som-
mets de C son maximum et son minimum sur la boule C . En
conséquence, on a
C -ÿ -D C -ÿ -D
- n - - n -
E‡ sup -
- ‡i f (xi )- = R E‡ max -
- - ‡i hj (xi )-- .
f œF j=1,...,p
i=1 i=1

En appliquant l’inégalité (6) avec

V = {(hj (x1 ), . . . , hj (xn )) : j = 1, . . . , p} ,
dont le cardinal est inférieur à p, on obtient
C - n -D
-ÿ - Ò
E‡ sup -- ‡i f (xi )-- 6 R 2n log(2p).
f œF i=1

La borne (20) découle du Lemme 3.1.

74 CHRISTOPHE GIRAUD

(b) Démontrons maintenant la borne (21). On note Î.ÎF la norme

dans le RKHS. La formule de reproduction et l’inégalité de Cauchy-
Schwartz nous donne
-ÿ - -= ÿ > - .ÿ .
- n - - n - . n .
-
- ‡i f (xi )-- = - f,
- ‡i k(xi , .) - 6 Îf ÎF .
- . ‡i k(xi , .).
. .
i=1 i=1 F i=1 F

En appliquant de nouveau l’inégalité de Cauchy-Schwartz, on obtient

C -ÿ -D C. n . D
- n - .ÿ .
E‡ sup -
- ‡i f (xi )- 6 R E‡ .
- . ‡i k(xi , .).
.
Îf ÎF 6R i=1 i=1 F
ı̂ C. n .2 D
ı .ÿ .
Ù
6 R E‡ .
. ‡i k(xi , .).
.
i=1 F
ı̂ n
ıÿ Ô
6 R Ù k(xi , xi )E‡ [‡i2 ] 6 R n,
i=1

où on a utilisé k(x, x) 6 1 dans la dernière inégalité et E [‡i ‡j ] = 0

pour i ”= j dans l’avant-dernière. En combinant de nouveau la pro-
priété de reproduction avec l’inégalité de Cauchy-Schwartz, on obtient
Ò
|f (x)| = |Èf, k(x, .)ÍF | 6 R k(x, x) 6 R.
Le Lemme 3.1 donne alors
Ú
L(h ‚ ¸ (f‚ ) + 2–R
‚ )6L Ô + ¸(R)
t
,
2n
F n F
n
ce qui achève la preuve du Théorème 3.

Il est possible de démontrer des bornes de risque similaire à (3) pour

H ), nous renvoyons à Bousquet, Boucheron et Lugosi [1] pour un
‚
L(h
panorama de tels résultats. Dans la dernière partie de ces notes, nous
allons décrire deux algorithmes de classification très populaires : les
Support Vector Machines et AdaBoost.

4.3. Support Vector Machine

Les Support Vector Machines (SVM) correspondent à l’estima-
teur (17) avec la perte Hinge ¸(z) = (1 ≠ z)+ . La classification fi-
nale s’effectue avec h
‚ (x) = sign(f‚ (x)). Nous allons donner une
F F
interprétation géométrique de la solution f‚F , interprétation qui est
à l’origine du nom "Support Vector Machine".
 APPRENTISSAGE STATISTIQUE 75

Proposition 2 (Vecteurs supports). La solution de (17) avec ¸(z) =

q
(1 ≠ z)+ est de la forme f‚F (x) = ni=1 —‚i k(Xi , x) avec
Y
]—i = 0 si Yi f‚F (Xi ) > 1
_ ‚
_
—‚i = Yi /(2⁄n) si Yi f‚F (Xi ) < 1
_
_
[
0 6 Yi —‚i 6 1/(2⁄n) si Yi f‚F (Xi ) = 1 .

Les vecteurs Xi d’indice i tel que —‚i =

” 0 sont appelés vecteurs sup-
ports.

Démonstration. Notons K la matrice [k(Xi , Xj )]i,j=1,...,n . Nous

savons par (19) que la solution de (17) est de la forme f‚F =
qn ‚
j=1 —j k(Xj , .) avec
; <
1ÿ n
! "
—‚ = argmin 1 ≠ Yi [K—]i + + ⁄— T K— .
—œRn n i=1
Le problème de minimisation ci-dessus n’est pas régulier, donc on
introduit des variables de relâchement ›‚i = (1 ≠ Yi [K —]
‚ i )+ et on
reformule le problème de minimisation comme suit
; <
1ÿ n
(24) (—, ‚ =
‚ ›) argmin ›i + ⁄— T K— .
—,›œRn tels que n i=1
›i >1≠Yi [K—]i
›i >0

Ce problème est maintenant régulier et convexe et les conditions de

Karush-Kuhn-Tucker pour le problème lagrangien dual
; <
1ÿ n ÿn
! "
(—, ‚ = argmin
‚ ›) ›i +⁄— T K— ≠ –i (›i ≠1+Yi [K—]i )+“i ›i .
—,›œRn n i=1 i=1
donnent les formules
conditions de 1er ordre :
n
ÿ 1
2⁄[K —]
‚j = Kij –i Yi et –j + “j = ,
i=1
n
conditions de relâchement :
min(–i , ›‚i ≠ 1 + Yi [K —]
‚ i ) = 0 et min(“i , ›‚i ) = 0.
On déduit de la première condition de premier ordre que —‚i =
–i Yi /(2⁄). Comme f‚F (Xi ) = [K —]
‚ i , la première condition de re-
lâchement donne —i = 0 si Yi fF (Xi ) > 1. La seconde condition
‚ ‚
de relâchement couplée à la seconde condition de premier ordre
76 CHRISTOPHE GIRAUD

Figure
) 3. Classification*par un SVM linéaire : l’hyperplan fron-
tière x œ Rd : Èw,
‚ xÍ = 0 est représenté en noir, les hyperplans
) * ) *
de marge x œ Rd : Èw,
‚ xÍ = +1 et x œ Rd : Èw, ‚ xÍ = ≠1 sont
représentés en pointillés bleus et rouges respectivement. Les vec-
teurs supports sont représentés par des carrés.

implique que —‚i = Yi /(2⁄n) si ›‚i > 0 et 0 6 Yi —‚i 6 1/(2⁄n) sinon.

Pour conclure la preuve de la proposition, on remarque que lorsque
que ›‚i > 0 on a —‚i et –i non nuls, et donc Yi f‚F (Xi ) = 1 ≠ ›‚i < 1 vu
la première condition de relâchement.
Interprétons géométriquement la Proposition 2.
Interprétation géométrique : noyau linéaire. Considérons le noyau le
plus simple k(x, y) = Èx, yÍ pour tout
Ó x, y œ R . LeÔRKHS associé est
d

l’espace des formes linéaires F = Èw, .Í : w œ Rd . Dans ce cas

n
ÿ n
ÿ
f‚F (x) = —‚i ÈXi , xÍ = Èw,
‚ xÍ avec ‚=
w —‚i Xi ,
i=1 i=1

donc le classifieur h ‚ (x) = sign(Èw,

F ‚ xÍ) classe Óles points en fonction
Ô
de leur position par rapport à l’hyperplan x œ Rd : Èw, ‚ xÍ = 0 .
La normale à l’hyperplan w ‚ est une combinaison linéaire des vec-
teurs supports, qui sont les points Xi tels que Yi Èw, ‚ Xi Í 6 1. Ils
sont
Ó représentés par Ôdes carrés
Ó sur la Figure 3.
Ô Les hyperplans
x œ R : Èw,
d ‚ xÍ = +1 et x œ R : Èw, d ‚ xÍ = ≠1 sont habituel-
lement appelés hyperplans de marge. Pour finir, notons la pro-
priété suivante des SVM. Si on ajoute à l’ensemble d’apprentissage
(Xi , Yi )i=1,...,n un point Xn+1 vérifiant Yn+1 Èw,
‚ Xn+1 Í > 1, alors le
 APPRENTISSAGE STATISTIQUE 77

X F

Figure 4. Classification avec un noyau non linéaire : la clas-

sification linéaire dans F produit une classification non linéaire
dans X via l’image réciproque de „.

vecteur w ‚ et le classifieur h‚ ne changent pas. En d’autres mots,

F
seules les données mal classifiées ou classifiées avec une marge
insuffisante
Ó (i.e. Yi ÈÔw,
‚ Xi Í 6 1) influencent l’hyperplan frontière
x œ R : Èw,
d ‚ xÍ = 0 .

Interprétation géométrique : noyau défini positif quelconque. Notons

par „ : X æ F l’application „(x) = k(x, .). La propriété de repro-
duction combinée à la Proposition 2 nous donne
=ÿ
n >
f‚F (x) = Èf‚F , „(x)ÍF = —‚i „(Xi ), „(x) .
i=1 F

Un point x œ X est classifié selon le signe du produit scalaire ci-

dessus. En conséquence, les points „(x) œ F sont classifiés selon le
classifieur linéaire sur F
n
ÿ
f ‘æ sign (Èw
‚„ , f ÍF ) où w
‚„ = —‚i „(Xi ).
i=1
) *
La frontière x œ X : f‚F (x) = 0 du classifieur h ‚ est donc l’image
F
réciproque par „ de l’hyperplan {f œ F : Èw ‚„ , f ÍF = 0}, comme re-
présenté Figure 4. Nous observons que le noyau k délinéarise le SVM,
dans le sens où il produit un classifieur non linéaire h‚ pour le même
F
coût numérique qu’un classifieur linéaire dans R . n

Vous pouvez observer les SVM à l’œuvre avec la petite démo :

http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml
Pourquoi les RKHS sont-ils utiles ? Il y a principalement deux raisons
pour utiliser un RKHS. La première raison est de permettre de déli-
néariser un algorithme en envoyant X dans F avec „ : x æ k(x, .),
78 CHRISTOPHE GIRAUD

X F

Figure 5. Classification de molécules à l’aide d’un SVM.

comme représenté dans la Figure 4. Cela permet d’obtenir un algo-

rithme non linéaire pour un coût similaire à celui d’un algorithme
linéaire.
La seconde raison pour utiliser un RKHS est de pouvoir employer
sur n’importe quel ensemble X des algorithmes définis pour des vec-
teurs. Imaginons par exemple qu’on veuille classifier des protéines ou
des molécules en fonction de leur propriétés thérapeutiques. Notons
par X notre ensemble de molécules. Pour tout x, y œ X , représen-
tons par k(x, y) leur similarité (selon des critères à définir). Si le noyau
résultant k : X ◊X æ R est défini positif, on peut alors directement
appliquer un SVM pour les classifier, comme illustré Figure 5. Bien
sûr, le point clef dans ce cas est de construire le noyau k. En général,
le noyau k(x, y) est défini en fonction de certaines propriétés de x, y
qui sont connues pour avoir de l’importance pour le problème de clas-
sification. Par exemple, le nombre de courtes séquences communes est
un indice utile pour quantifier la similarité entre deux protéines. La
complexité du calcul de k(x, y) est aussi un critère crucial pour les
applications sur des données complexes. Nous renvoyons aux excel-
lents slides de Jean-Philippe Vert pour la description d’applications
prometteuses en biologie et médecine :
http://cbio.ensmp.fr/~jvert/talks/120302ensae/ensae

4.4. AdaBoost
AdaBoost est un algorithme qui tend à calculer une solution
approximative de l’estimateur (15) avec la perte exponentielle
¸(z) = e≠z et l’espace fonctionnel F = span {h1 , . . . , hp } où
h1 , . . . , hp sont p classifieurs donnés.
 APPRENTISSAGE STATISTIQUE 79

Le principe de l’algorithme AdaBoost est de réaliser une minimisa-

tion dite agressive de (15). Plus précisément, AdaBoost produit une
suite de fonctions f‚m pour m = 0, . . . , M en partant de f‚0 = 0 puis
en résolvant récursivement pour m = 1, . . . , M

f‚m = f‚m≠1 + —m hjm

1ÿ n 1 ! "2
où (—m , jm ) = argmin exp ≠Yi f‚m≠1 (Xi ) + —hj (Xi ) .
j=1,...,p n i=1
—œR

La classification finale est effectuée à l’aide de h

‚ M (x) = sign(f‚M (x))
qui est une approximation de hH défini par (15).
‚
La perte exponentielle permet de calculer (—m , jm ) très efficace-
(m)
ment. En effet, en posant wi = n≠1 exp(≠Yi f‚m≠1 (Xi )), on peut
écrire

1ÿ n 1 ! "2
exp ≠Yi f‚m≠1 (Xi ) + —hj (Xi )
n i=1
n
ÿ n
ÿ
(m) (m)
= (e— ≠ e≠— ) wi 1hj (Xi )”=Yi + e≠— wi .
i=1 i=1

Lorsque la condition suivante

qn (m)
i=1 wi 1hj (Xi )”=Yi 1
errm (j) = qn 6 pour tout j = 1, . . . , p,
(m) 2
i=1 wi

est satisfaite, les minimiseurs (—m , jm ) sont donnés par

3 4
1 1 ≠ errm (jm )
jm = argmin errm (j) et —m = log .
j=1,...,p 2 errm (jm )

En remarquant que ≠Yi h(Xi ) = 21Yi ”=h(Xi ) ≠ 1 on obtient la formu-

lation standard de l’algorithme AdaBoost.
80 CHRISTOPHE GIRAUD

AdaBoost
(1)
Init : wi = 1/n, for i = 1, . . . , n
Iterate : For m = 1, . . . , M do
jm = argmin errm (j)
j=1,...,p
2—m = log(1 ≠ errm (jm )) ≠ log(errm (jm ))
(m+1) (m)
wi = wi exp(2—m 1hjm (Xi )”=Yi ), for i = 1, . . . , n
STOP if min errm+1 (j) > 1/2
j=1,...,p
q
Output : f‚M (x) = M
m=1 —m hjm (x).

On remarque que l’algorithme AdaBoost donne de plus en plus de

poids dans errm (j) aux points Xi qui sont mal classifiés à l’étape m.
Vous pouvez observer AdaBoost à l’œuvre (pour des classifieurs hj
par demi-espaces) avec l’application récréative :
http://cseweb.ucsd.edu/~yfreund/adaboost/

5. Pour aller au-delà de cette introduction

Nous renvoyons le lecteur intéressé à aller au-delà des concepts
présentés dans ces notes à l’article de synthèse de Boucheron, Bous-
quet et Lugosi [1]. Cet article comprend notamment une bibliographie
assez exhaustive. D’un point de vue plus pratique et appliqué, l’incon-
tournable livre de Hastie, Tibshirani et Friedman [5] décrit et discute
de très nombreux algorithmes opérationnels. Enfin, nous soulignons
que les concepts introduits ici apparaissent aussi pour le problème de
ranking (ordonner au mieux des données, l’exemple le plus célèbre
étant les moteurs de recherche sur internet), voir Clémençon, Lugosi
et Vayatis [3].

Appendice A. Espace de Hilbert à noyaux reproduisants

(RKHS)
Les espaces de Hilbert à noyaux reproduisants, dit Reproducing
Kernel Hilbert Spaces (RKHS) en anglais, sont des espaces de Hilbert
fonctionnels dont la norme décrit la régularité des fonctions. Les
RKHS vérifient aussi une propriété de reproduction particulière, qui
 APPRENTISSAGE STATISTIQUE 81

s’avère cruciale en pratique car elle permet une mise œuvre numérique
efficace.
Une fonction k : X ◊ X æ R est dite définie positive si elle est
symétrique (k(x, y) = k(y, x) pour tout x, y œ X ) et si pour tout
N œ N, x1 , . . . , xN œ X et a1 , . . . , aN œ R on a
N
ÿ
(25) ai aj k(xi , xj ) > 0.
i,j=1

Exemples de noyaux définis positifs :

• noyau linéaire : k(x, y) = Èx, yÍ
2 2
• noyau gaussien : k(x, y) = e≠Îx≠yÎ /2‡
• noyau histogramme (d = 1) : k(x, y) = min(x, y)
• noyau exponentiel : k(x, y) = e≠Îx≠yÎ/‡

On peut associer à un noyau défini positif k un sous-espace de

Hilbert F de RX appelé espace de Hilbert de noyau reproduisant k.

Proposition 3 (Espace de Hilbert à noyau reproduisant (RKHS))

À tout noyau défini positif k sur X , on peut associer un (unique)
espace de Hilbert F µ RX vérifiant
• k(x, .) œ F pour tout x œ X
• propriété de reproduction : f (x) = Èf, k(x, .)ÍF pour tout x œ X

et f œ F .
L’espace F est appelé espace de Hilbert de noyau reproduisant k.

Démonstration. Considérons l’espace linéaire F0 engendré par la fa-

mille {k(x, .) : x œ X }
; N
ÿ
F0 = f : X ≠æ R : f (x) = ai k(xi , x), N œ N,
i=1 <
x1 , . . . , xN œ X , a1 , . . . , aN œ R .

qN qM
À tout f = i=1 ai k(xi , .) et g = j=1 bj k(yj , .) on associe
N ÿ
ÿ M N
ÿ M
ÿ
Èf, gÍF0 := ai bj k(xi , yj ) = ai g(xi ) = bj f (yj ).
i=1 j=1 i=1 j=1
82 CHRISTOPHE GIRAUD

Les deux dernières égalités indiquent que Èf, gÍF0 ne dépend pas du
choix de la décomposition de f et g, donc cette quantité est bien défi-
nie. De plus, l’application (f, g) æ Èf, gÍF0 est bilinéaire, symétrique,
positive (vu (25)) et on a la propriété de reproduction

f (x) = Èf, k(x, .)ÍF0 pour tout x œ X et f œ F0 .

L’inégalité de Cauchy-Schwartz Èf, gÍF0 6 Îf ÎF0 ÎgÎF0 combinée à

la formule de reproduction donne
Ò
(26) |f (x)| 6 k(x, x) Îf ÎF0 .

En conséquence Îf ÎF0 = 0 implique f = 0 donc Èf, gÍF0 est un

produit scalaire. L’espace F0 est donc un espace pré-hilbertien et
pour obtenir F il nous suffit de le compléter.
Considérons deux suites (xi ) œ X N et (ai ) œ RN vérifiant
q
i,j>1 ai aj k(xi , xj ) < +Œ. L’inégalité (26) nous assure que pour
tout M < N et x œ X on a
- ÿ
N - Ò N
ÿ
- -
- ai k(xi , x)- 6 k(x, x) ai aj k(xi , xj ).
i=M +1 i,j=M +1
q
Lorsque i,j>1 ai aj k(xi , xj ) est fini, le membre de droite tend
vers 0 lorsque M, N tendent vers l’infini, donc les séries partielles
qN
i=1 ai k(xi , x) sont de Cauchy et convergent lorsque N æ Œ. On
peut donc définir l’espace
; Œ
ÿ
F = f : X ≠æ R : f (x) = ai k(xi , x), (xi ) œ X N ,
i=1 ÿ <
(ai ) œ R , N
ai aj k(xi , xj ) < +Œ
i,j>1

et la forme bilinéaire
Œ
ÿ Œ
ÿ Œ
ÿ
Èf, gÍF := ai bj k(xi , yj ) = ai g(xi ) = bj f (yj )
i,j=1 i=1 j=1
q q
pour f = Πi=1 ai k(xi , .) et g = j=1 bj k(yj , .). Exactement comme
Œ

précédemment, l’application (f, g) æ Èf, gÍF est un produit scalaire

vérifiant la propriété de reproduction

f (x) = Èf, k(x, .)ÍF pour tout x œ X et f œ F .

 APPRENTISSAGE STATISTIQUE 83

Finalement, l’espace F muni du produit scalaire È., .ÍF est la complé-

tion dans RX de F0 muni de È., .ÍF0 , donc c’est un espace de Hilbert
à noyau reproduisant.
La norme d’une fonction f dans un RKHS F est fortement reliée à
la régularité de f . Cette propriété apparait clairement dans l’inégalité
|f (x) ≠ f (xÕ )| = |Èf, k(x, .) ≠ k(xÕ , .)ÍF | 6 Îf ÎF Îk(x, .) ≠ k(xÕ , .)ÎF .
Nous illustrons ce point en décrivant le RKHS associé aux noyaux
histogrammes et gaussiens.

Exemple 1 : RKHS associé au noyau histogramme

L’espace de Sobolev
Ó
F = f œ C([0, 1], R) : f est p.p. différentiable Ô
avec f Õ œ L2 ([0, 1]) et f (0) = 0
s
muni du produit scalaire Èf, gÍF = 01 f Õ g Õ est un RKHS de noyau
reproduisant k(x, y) = min(x, y) sur [0, 1]. En effet, k(x, .) œ F pour
tout x œ [0, 1] et
⁄ 1
f (x) = f Õ (y)1y6x dy = Èf, k(x, .)ÍF , pour tout f œ F et x œ [0, 1].
0
Dans ce cas, la norme Îf ÎF correspond simplement à la norme L2
de la dérivée de f . Plus cette norme est petite, plus f est régulière.

Exemple 2 : RKHS associé au noyau gaussien. Notons par F[f ] la trans-

formée de Fourier dans Rd de normalisation
⁄
1
F[f ](Ê) = f (t)e≠iÈÊ,tÍ ,
(2fi)d/2 Rd
pour f œ L1 (Rd ) fl L2 (Rd ) et Ê œ Rd .
Pour tout ‡ > 0, l’espace fonctionnel
; ⁄ <
- -
F‡ = f œ C0 (Rd )flL1 (Rd ) tel que -F[f ](Ê)-2 e‡|Ê|2 /2 dÊ < +Œ ,
Rd
muni du produit scalaire
⁄
2 /2
Èf, gÍF‡ = (2fi‡ 2 )≠d/2 F[f ](Ê)F[g](Ê)e‡|Ê| dÊ
Rd
est un RKHS associé au noyau gaussien
k(x, y) = exp(≠Îy ≠ xÎ2 /2‡ 2 ).
84 CHRISTOPHE GIRAUD

En effet, pour tout x œ Rd la fonction k(x, .) appartient à F‡ et un

calcul direct donne
# $
Èk(x, .), f ÍF‡ = F≠1 F[f ] (x) = f (x) pour tout f œ F et x œ Rd .

L’espace F‡ est composé de fonctions très régulières et la norme

Îf ÎF‡ contrôle directement la régularité de f . Remarquons que
lorsque ‡ augmente l’espace F‡ rétrécit pour ne contenir que des
fonctions de plus en plus régulières.

Appendice B. Inégalités probabilistes

Les analyses non asymptotiques en apprentissage statistique re-
posent très souvent sur l’inégalité de concentration de McDiarmid [6].

Théorème 4 (McDiarmid (1989)). Soit X un ensemble mesurable et

considérons F : X n æ R telle qu’il existe ”1 , . . . , ”n vérifiant
- -
-F (x1 , . . . , xÕ , . . . , xn ) ≠ F (x1 , . . . , xi , . . . , xn )- 6 ”i ,
i

pour tout x1 , . . . , xn , xÕi œ X , pour i = 1, . . . , n. Alors, pour tout t > 0

et pour toutes variables indépendantes X1 , . . . , Xn , on a
A B
! " 2t2
P F (X1 , . . . , Xn ) > E [F (X1 , . . . , Xn )] + t 6 exp ≠ 2 .
”1 + · · · + ”n2

Nous renvoyons le lecteur au Chapitre 9 du livre de Devroye, Györfi

et Lugosi [4] pour la preuve classique de ce résultat, preuve qui com-
bine simplement l’inégalité de Markov avec un argument martingale
(par conditionnements télescopiques). Une preuve plus conceptuelle
basée sur la méthode d’entropie est donnée dans le livre de Bouche-
ron, Lugosi et Massart [2], Chapitre 6.
Un second concept important en apprentissage statistique est le
principe de contraction.

Théorème 5 (Principe de contraction). Soit Z un sous-ensemble borné

de Rn et Ï : R æ R une fonction –-Lipschitz vérifiant Ï(0) = 0. Pour
des variables aléatoires ‡1 , . . . , ‡n i.i.d. de loi

P‡ (‡i = 1) = P‡ (‡i = ≠1) = 1/2,

 APPRENTISSAGE STATISTIQUE 85

nous avons
C -ÿ -D C -ÿ -D
- n - - n -
E‡ sup -- ‡i Ï(zi )-- 6 – E‡ sup -- ‡i zi -- .
zœZ i=1 zœZ i=1

Un preuve concise est donnée dans le Chapitre 11 du livre de Bou-

cheron, Lugosi et Massart [2].

Références
[1] Boucheron, S., Bousquet, O. and Lugosi, G. Theory of classification :
some recent advances. ESAIM Probability & Statistics, 9 (2005) : 323–
375.
[2] Boucheron, S., Lugosi, G. and Massart, P. Concentration Inequalities.
Oxford University Press, 2013.
[3] Clémençon, S., Lugosi, G. and Vayatis, N. Ranking and empirical risk
minimization of U-statistics. The Annals of Statistics, 36 (2008) : 844–
874.
[4] Devroye, L., Györfi, L. and Lugosi, G. A Probabilistic Theory of Pattern
Recognition. Springer, 1996.
[5] Hastie, T., Tibshirani, R. and Friedman, J. The element of statistical
learning. Springer, 2009.
[6] McDiarmid, C. On the Method of Bounded Differences. Surveys in Com-
binatorics 141 (1989) : 148–188.

Christophe Giraud, Département de Mathématiques, Bât. 425, Faculté des

Sciences d’Orsay, Université Paris-Sud, F-91405 Orsay Cedex
CMAP, UMR CNRS 7641, Ecole Polytechnique, Route de Saclay, 91128
Palaiseau Cedex • E-mail : [email protected]
Url : http://www.cmap.polytechnique.fr/~giraud/