Apprentissage: cours 6

Théorie, concentration, borne PAC

Simon Lacoste-Julien
31 octobre 2014

Résumé
Aujourd’hui on couvre les bases théoriques pour l’analyse des algorithmes d’apprentissage de clas-
sification. On distingue l’analyse statistique traditionnelle (risque fréquentiste), de celle utilisée en
informatique inspirée de l’approche PAC (Probably Approximately Correct). L’outil mathématique
central qui explique l’apprentissage sont les bornes de concentrations (par exemple, borne de Cher-
noff). Finalement, nous allons prouver une des bornes les plus simples d’erreur de généralisation,
la borne “d’Occam”, qui justifie le principe du rasoir d’Occam et donne une interprétation de la
régularisation en terme d’à-priori sur les hypothèses.

1 Risque fréquentiste vs. borne PAC

1.1 Rappel de définitions
Données d’entrainement : Dn = (Xi , Yi )16i6n i.i.d. de loi P .
[
Algorithme d’apprentissage : A : (X × Y)n 7→ F
n∈N
Famille d’algorithmes d’apprentissage : ( Am )m∈M
Prédicteur fb
Exemples : Dans ce cours par abus de notation on écrira souvent fb pour A et fb(Dn ) pour A (Dn ).
Pour être rigoureux, il faudrait toujours utiliser fbDn := A (Dn ). fb(x; Dn ) dénote fbDn évalué à x.
 
Excès de risque (Vapnik) : RP fb(Dn ) − RP ( f ? ) − − RP ( · ) rend la dépendance
sur P explicite.
Risque (Vapnik) : Le risque (au sens de Vapnik) donne l’erreur de généralisation de notre prédicteur
– on veut le minimiser.
Consistance : Un algorithme d’apprentissage est consistant pour la loi P si
h i
lim EDn ∼P ⊗n RP (fb) − RP (fP? ) = 0.
n→∞

1.2 Risque fréquentiste RFP (·)

En théorie de la décision statistique (traditionnelle) [à différencier de la théorie de la décision ‘ver-
sion apprentissage’ présentée au premier cours], on veut analyser la performance d’un estimateur en
moyenne sur les observations possibles. Dans le cadre de l’apprentissage automatique, les observations
possibles sont les données d’entraı̂nement Dn ; l’estimateur est l’algorithme d’apprentissage A ; et la per-
formance est l’erreur de généralisation, i.e. le risque au sens de Vapnik : RP ( A (Dn ) ). La performance
moyenne est l’espérance du risque de Vapnik par rapport aux données d’entraı̂nement et s’appelle le
P (A ; n) :
risque fréquentiste 1 RF

P ( A ; n ) := EDn ∼P ⊗n [RP (fn )]

RF (fbn = A (Dn )).
b

1. Vous voyez donc le dédoublement de sens du mot risque et pourquoi nous précisons risque au sens de Vapnik vs.
risque fréquentiste.

1
On voit donc que notre notion de consistance étudiait le comportement de limn→∞ RF P ( A ; n ).
Pour deux algorithmes d’apprentissage donnés A1 et A2 , si RF P ( A1 ; n ) 6 RP ( A2 ; n ) pour tout n,
F

l’analyse traditionnelle fréquentiste dira que A1 est meilleur que A2 . Par contre, on considère plutôt
RF P ( A ; n ) comme une fonction de P pour P ∈ P, au quel cas il devient difficile de comparer les
algorithmes (voir dessin au tableau). D’ailleurs, le théorème de no free lunch pour la classification que nous
avons démontré dans le cours 3 implique en gros que si X est infini, alors pour toute paire d’algorithmes,
il existe deux distributions P1 et P2 telle que A1 est meilleur que A2 sur P1 , mais A2 est meilleur
que A1 sur P2 . Pour avoir des comparaisons non-triviales, il faut donc faire des suppositions sur P. En
statistique, un exemple d’approche est d’analyser la performance d’un algorithme d’apprentissage en
considérant le pire des cas sur P, i.e. on veut trouver un algorithme qui minimise supP ∈P RF P (A ; n)
– c’est l’approche minimax. Des résultats existent pour certains P (et par exemple, nous rappelons la
consistance universelle uniforme pour la règle de la classe la plus fréquente quand X est fini mentionnée
dans le cours 3).

1.3 Approche PAC

Un désavantage du risque fréquentiste est qu’il ne donne aucune information sur la variance de
la performance de l’algorithme d’apprentissage sur les données d’entraı̂nement possibles (voir dessin
au tableau). En informatique, l’approche d’analyse se concentre plutôt sur des intervalles de confiance
pour la performance de l’algorithme d’apprentissage. Plutôt que de considérer l’espérance de l’erreur de
généralisation, on quantifie une borne de queue, c’est-à-dire, on donne une borne supérieure sur l’erreur
de généralisation qui est valide avec probablité supérieure à 1 − δ (pour un petit δ > 0), où l’aléat vient
des données Dn possibles :
 
P RP (A (Dn )) 6 borne(A , n, δ, P ) > 1 − δ

Le PAC (Probably Approximately Correct) implique que la borne n’est valide qu’avec probabilité plus
grande que 1 − δ. À noter l’analyse PAC est plus fine que celle du risque fréquentiste : avec des arguments
probabilistes standards, nous pouvons transformer une borne PAC en une borne sur l’espérance de l’erreur
de généralisation.

1.4 Les outils – pourquoi l’apprentissage fonctionne

En gros, nous voulons trouver une fonction f avec une petite erreur de généralisation ; rappelons :

RP ( f ) := E(X,Y )∼P [`(f (X), Y )].

Nous avons accès à l’erreur empirique sur les données d’entraı̂nement :

n
b n ( f ) = En [`(f (X), Y )] = 1
X
R `(f (xi ), yi ).
n i=1

Puisque les données sont i.i.d, nous avons par la la loi forte des grands nombres :
p.s.
R
bn ( f ) −−→ RP ( f ) .

Si la variance de la perte existe, nous avons même par le théorème de la limite centrale :
√  
d
n R b n ( f ) − RP ( f ) −→ N (0, varP [`(f (X), Y )]) .

Par contre, si nous voulons comparer les optima de R b n ( f ) vs. ceux de RP ( f ), pour être rigoureux,
nous aurions besoin par exemple (condition suffisante mais non nécessaire) de la convergence uniforme
sur une la classe de fonctions F :
P
sup |R
b n ( f ) − RP ( f ) | −
→ 0.
f ∈F

2
Ce genre de résultat est étudié par la théorie des processus empiriques (par exemple, classe de Glivenko-
Cantelli et classe de Donsker qui généralise la loi des grands nombres et la loi du théorème central limite,
respectivement, pour les processus empiriques).
Tous ces résultats sont asymptotiques par contre. En apprentissage automatique, nous voulons des
résultats pour un n fini. Pour ceci, nous regardons des analogues non-asymptotiques du théorème de la
limite centrale : les bornes de concentration. Par exemple, la borne de Chernoff que vous allez prouver
dans le TD à partir de l’inégalité de Markov (et qui donne l’inégalité de Hoeffding qui est plus générale).

Borne de Chernoff : Soit {Zi }ni=1 des variables de Bernouilli i.i.d de probabilité p (i.e. Zi = 1 avec
probabilité p et 0 autrement). Alors :
 X n 
1 2
P Zi > p + ε 6 e−2nε ∀ε > 0.
n i=1

En appliquant cette borne pour le risque en classification binaire, on obtient :

 
2
P Rn ( f ) > RP ( f ) + ε 6 e−2nε ∀ε > 0
b

Nous allons utiliser cette borne pour montrer la Borne d’Occam pour la classification binaire.

2 Borne d’Occam
Pour le reste du cours 2 , nous considérons la classification binaire. Pour avoir un résultat simple,
nous allons considérer un ensemble de fonctions F dénombrable (aussi appelé ensemble d’hypothèses
traditionnellement en informatique). La borne d’Occam utilise un à-priori π sur les fonctions possibles,
c’est à dire une ‘distribution’ (au sens Bayésien) sur les fonctions dans F. Cette distribution π sert à
définir une mesure de complexité pour les fonctions (au sens du rasoir d’Occam) via la relation :
1
|f |π := log2 . (1)
π
En théorie de l’information, on peut faire correspondre un langage fixe (un code) à une distribution de
probabilité sur un nombre dénombrable d’objets via la relation (1) (modulo des fonctions partie entière
que l’on ignore ici pour simplifier la présentation). Sous cette perspective, |f |π pourrait représenter le
nombre de bits nécessaires pour décrire la fonction f (en utilisant un code préfixe, comme un code de
Huffman, par exemple).

Borne d’Occam. La borne d’Occam est une borne PAC uniforme pour toutes les fonctions f ∈ F,
pour un F dénombrable. Elle dit que, pour tout δ > 0, avec probabilité d’au moins 1 − δ sur les jeux
de données Dn possibles, nous avons la borne uniforme suivante qui est valide (pour le risque de la
classification binaire) :
v
1
bn ( f ) + √ u
u 1
∀f ∈ F, RP ( f ) 6 R |f |π + ln .
tln(2) |{z} (2)
2n δ
complexite

Commençons par prouver la borne, pour voir d’où vient l’utilité de π.

2.1 Preuve de la borne d’Occam

La preuve de la borne d’Occam utilise trois inégalités très simples :
— Concentration : borne de Chernoff :
 
2
P Rn ( f ) > RP ( f ) + ε 6 e−2nε ∀ε > 0
b

2. Ces notes sont inspirées du cours de David McAllester disponibles à [Link]

ttic101-07/lectures/generalization/[Link].

3
 P
— Borne d’union : P{∃xProp(x)} 6 x P{Prop(x)}
— Inégalité de Kraft : f ∈F 2−|f |π 6 1
P
L’inégalité de Kraft devient évidente avec la définition de |f |π à partir d’une distribution π.
Démonstration. Pour prouver la borne d’Occam, nous allons définir qu’une fonction f est ‘mauvaise’
(par rapport à un jeu de données Dn ) quand elle viole l’inégalité du théorème. Plus précisément, nous
définissons la proposition (qui peut être vraie au fausse) :
" r #
1 1
mauvaise(f ) := RP ( f ) > Rn ( f ) + √
b ln(2)|f |π + ln
2n δ

Par Chernoff sur les jeux de données, nous avons :

   2
−2n √12n Ω(f ;δ)
P mauvaise(f ) 6 e = δ2−|f |π

En utilisant une borne d’union sur toutes les fonctions f ∈ F, suivie de l’inégalité de Kraft, nous obtenons
le résultat :   X
P ∃f ∈ F, mauvaise(f ) 6 δ2−|f |π 6 δ
f ∈F

On voit donc que l’utilité de π était de pouvoir sommer la borne de Chernoff sur toutes les fonctions.

2.2 Borne comme un algorithme

Après avoir dérivé une borne de généralisation PAC uniforme, cela donne naturellement un algorithme
d’apprentissage (du style du rasoir d’Occam) qui minimise la borne :
( r )
bn ( f ) + √1 1
fbn := argminf ∈F R ln(2)|f |π + ln . (3)
2n δ
q
Définissons Ω(f ; δ) := ln(2)|f |π + ln 1δ , qui représente en quelque sorte une mesure de complexité
pour f . Puisque la borne d’Occam est valide pour tout f ∈ F, elle est aussi valide pour fbn ; donc avec
probabilité supérieure à 1 − δ sur Dn , nous avons :

b n fbn + √1 Ω(fbn ; δ).

   
RP fbn 6 R
2n
Cette borne est utile seulement si le côté droit est plus petit que 1 (car l’erreur de généralisation est
toujours plus petite que 1). Ce sera le cas seulement si il existe dans F une fonction avec, à la fois, une
√
petite erreur empirique et aussi une petite complexité Ω(fbn ; δ) par rapport à n. Si notre à-priori π est
mauvais, nous allons assigner une grande complexité |f |π à des fonctions qui auraient pu bien expliquer
les données, ce qui fera un mauvais algorithme. Pour une distribution P donnée, nous pourrions définir
π de telle sorte que |fP∗ |π soit minime ; l’algorithme d’apprentissage (3) serait alors très bon pour cette
distribution, car bien calibré pour celle-ci. Par contre, nous voulons considérer un ensemble de P possible,
et donc, il y a un analogue de no free lunch ici que nous ne pouvons pas mettre une grande probabilité
à toutes les fonctions fP∗ possibles pour un large éventail de P .

2.3 Consistence forte universelle

L’algorithme (3) est consistent (au sens de faire le mieux dans la classe F possible pour toute dis-
tribution P , et donc elle est ’universelle’ 3 ). La consistence est même forte (la convergence est presque
sûre) :   p.s.
∀P, RP fbn −−→ min RP ( f )
f ∈F

3. Attention ! À noter que la consistence n’est pas uniforme (sinon, cela contredirait le ‘no free lunch’ !).

4
La consistence forte (convergence presque sûre) implique aussi la consistence au sense du risque fréquentiste
car la perte est bornée :
lim EDn ∼P ⊗n RP (fbn ) = min RP ( f )
n→∞ f ∈F

Démonstration. La technique de preuve pour la borne d’Occam (2) peut être modifié pour borner les
deux directions (avec un coût de ln 2δ dans la borne plutôt que ln 1δ ) : avec probabilité d’au moins 1 − δ
sur les jeux de données Dn possibles, nous avons :

∀f ∈ F, b n ( f ) | 6 √1 Ω(f ; δ )
|RP ( f ) − R (4)
2n 2

Nous supposons que à la fois (2) et (4) sont valides en même temps (donc avec probabilité 1 − 2δ sur
Dn , car chaque borne a une probabilité δ d’échouer). Nous avons :

b n fbn + √1 Ω(fbn ; δ)
 
 
RP 6Rfbn (en utilisant (2))
2n
6R b n ( f ) + √1 Ω(f ; δ) ∀f ∈ F (par la définition (3))
2n
1 δ
6 RP ( f ) + 2 √ Ω(f ; ) ∀f ∈ F (en utilisant (4))
2n 2
 
  1 δ
RP fbn 6 min RP ( f ) + 2 √ Ω(f ; )
f ∈F 2n 2
1 δ
6 RP ( fP∗ ) + 2 √ Ω(fP∗ ; )
2n 2

où nous avons défini fP∗ ∈ argminf ∈F RP ( f ).

n→∞
Maintenant, soit un ε > 0 donné. Pour chaque n, définissons δn = 1
n2 . Nous avons 2 √12n Ω(f ; δ2n ) −−−−→
0. Donc pour n plus grand qu’un nε , nous avons 2 √12n Ω(f ; δ2n ) 6 ε. Selon nos inégalités PAC, nous avons
donc que  
  2
P RP fbn > RP ( fP∗ ) + ε 6 2δn = 2 ∀n > nε
n
   
Par la définition de fP∗ nous avons évidemment que RP fbn > RP ( fP∗ ), et donc RP fbn −RP ( fP∗ ) =
 
|RP fbn − RP ( fP∗ ) |. Ainsi, nous avons :

X     X 2
∗
P |RP fn − RP ( fP ) | > ε 6
b <∞
n2
n>nε n>nε

et ce, pour tout ε > 0, et donc par le lemme de Borel-Cantelli sur la convergence presque sûre, nous
concluons que :   p.s.
RP fbn −−→ RP ( fP∗ )

2.4 Exemple avec régularisation

Pour donner un exemple concret et faire le lien avec la régularisation standard, considérons X = Rd ,
Y = {−1, 1} et F l’espace des frontières de décision linéaires passant par 0 : F := {fw | w ∈ W} où
fw : x 7→ sign(hw, xi) et W est un sous-ensemble dénombrable de Rd . Par exemple, on pourrait décider
d’encoder chaque coordonnée de w sous la forme de q. d1 · · · dk où q est un nombre entier ; pour un k fixe
| {z }
k décimales
2
donné, le nombre de possibilités est dénombrables. On considère maintenant l’à-priori π(w) := Z1k 2−kwk ,
où Z est une constante à déterminer en sommant sur le nombre dénombrable de possibilités dans W. À

5
noter que souvent ces constantes ne sont pas très importantes, car elles apparaissent dans un facteur log.
Par exemple, avec cet à-priori, nous avons :

|fw |π = − log2 π(w) = kwk2 + log2 Zk

Pour avoir l’ordre de grandeur de Zk :

d
!
−kwk2 −wi2 2
/102k d
X Y X X
Zk = 2 = 2 =( 2−u )
w∈W i=1 wi ∈Wi u∈Z
!d
X 1
u2
−
6 2 2 102k

u∈N
!d  d
X 1
u 2
−
6 2 2 102k = 1
u∈N 1 − 2− 102k

Avec un peu de calcul, on peut montrer que :

log2 Zk ≈ d(1 + 2k log2 (10) + log2 ln(2)) = O(d ∗ k).

Nous avons donc que la pénalité de complexité ressemble à :

|fw |π = kwk2 + C d k

Et la minimisation de la borne d’Occam donne une minimisation de risque empirique régularisé :

( r )
b n ( fw ) + √1 1
fbn := argminw∈W R ln(2)(kwk2 + Cdk) + ln .
2n δ

À noter que en général, la minimisation du risque empirique est NP-difficile, alors cet algorithme n’est
pas réaliste d’un point de vue computationnel. Des techniques analogues à la borne d’Occam peuvent
être développées avec une version convexe (en w) du risque empirique à droite (avec des ‘pertes convexes
de substitut’). Vous allez voir des algorithmes inspirés de cette approche dans le cours sur les pertes
convexes.