Introduction

Risque, risque empirique

Estimation d’un risque
Discrimination à deux classes et courbe ROC

Apprentissage automatique / Statistique

Qualité de Prévision et Risque

P HILIPPE B ESSE

INSA de Toulouse
Institut de Mathématiques

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Objectif
Estimation d’un risque Risques et choix de modèle
Discrimination à deux classes et courbe ROC

Objectif
Mesurer la performance d’un modèle, sa capacité de
prévision ou de généralisation
Optimiser la sélection au sein d’une famille de modèles
choix de la méthode en comparant chacun des modèles
estimer la confiance accordée à une prévision
Enjeu : estimation sans biais de l’erreur de prévision
Capacité de généralisation du modèle ou algorithme

Sans modèle probabiliste, trois stratégies :

1 Pénalisation de l’erreur d’ajustement ou risque empirique
2 Partition de l’échantillon : apprentissage, (validation), test
3 Simulation : validation croisée, bootstrap

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Objectif
Estimation d’un risque Risques et choix de modèle
Discrimination à deux classes et courbe ROC

Régression polynomiale de degré 1, 2, 5 et 10

INSA de Toulouse - Apprentissage Statistique Qualité de prévision
 Introduction
Risque, risque empirique Modèle statistique
Estimation d’un risque Minimisation du risque empirique
Discrimination à deux classes et courbe ROC

Notations
Dn observations d’un n-échantillon
Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} de loi conjointe inconnue P sur
X ×Y
x observation de la variable X multidimensionnelle
Dn est appelé échantillon d’apprentissage
Dn est supposé indépendant de (X, Y)
Une règle de prévision (ou prédicteur) est une fonction
(mesurable) f : X → Y, x → f (x)
Une fonction l : Y × Y → R+ est une fonction de perte si
l(y, y) = 0 et l(y, y0 ) > 0 pour y 6= y0
Si f est une règle de prévision, l(y, f (x)) mesure la perte de
f en x

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Modèle statistique
Estimation d’un risque Minimisation du risque empirique
Discrimination à deux classes et courbe ROC

Définitions
Régression réelle : pertes Lp (p ≥ 1) : l(y, y0 ) = |y − y0 |p
perte absolue si p = 1, perte quadratique si p = 2
|y−y0 | (y−y0 )2
Discrimination binaire : l(y, y0 ) = 1Iy6=y0 = 2 = 4
Risque d’une règle f : RP (f ) = E(X,Y)∼P [l(Y, f (X))]
Risque empirique associé à Dn :
1 Pn
Rn (f , Dn ) = n i=1 l(Yi , f (Xi ))
c
Minimisation du risque empirique sur un sous-ensemble F
(un modèle) de F : f̂F (Dn ) ∈ argminf ∈F R
cn (f , Dn )
Problème : choix de F !
La règle oracle est telle que : RP (f ∗ ) = inff RP (f )

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Modèle statistique
Estimation d’un risque Minimisation du risque empirique
Discrimination à deux classes et courbe ROC

Décomposition du risque empirique

RP (f̂F (Dn )) − RP (f ∗ ) =
n o n o
RP (f̂F (Dn )) − inf RP (f ) + inf RP (f ) − RP (f ∗ )
f ∈F f ∈F
| {z } | {z }
Erreur d’estimation et d’approximation
(Variance) (Biais)
% & (taille de F)
Plus le modèle F est complexe ou flexible,
plus le biais est réduit mais
plus la partie variance risque d’augmenter
Enjeu : meilleur compromis biais / variance

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Risque empirique ou qualité d’ajustement

n
cn (bf (Dn ), Dn ) = 1
X
R l(yi , bf (Dn )(xi ))
n
i=1

Minimum des moindres carrés dans le cas quantitatif

Taux de mal classés dans le cas qualitatif
Estimation biaisée, par optimisme

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Estimation sans biais sur un échantillon indépendant

Partition : Dn = DAppr
n1 ∪ DValid
n2 ∪ DTest
n3
cn (bf (DAppr
R Appr b Appr
n1 ), Dn1 ) pour estimer un modèle choisi f (Dn1 )
cn (bf (DAppr
R Valid
n1 ), Dn ) pour optimiser un modèle
2

cn (bf , DTest
R n3 ) pour comparer les meilleurs modèles

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Cp de Mallows
Décomposition de l’erreur de prévision ou risque
quadratique :

cP (bf (dn )) = R
R cn (bf (dn ), dn ) + Optim

Estimation normalisée :

cn (bf (dn ), dn ) + 2 d σ
Cp = R b2
n

d : nombre de paramètres du modèle

n : nombre d’observations
s2 : estimation de la variance de l’erreur par modèle de
faible biais

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Régression polynomiale : Cp de Mallows fonction du degré et

modèle sélectionné.

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Critère d’Akaı̈ke
Basé sur la dissemblance de Kullback
compare la loi de Y et celle de Y
b
Suppose que la famille de lois du modèle contient la “vraie”
loi de Y
Pour tout modèle estimé par minimisation d’une
log-vraisemblance L

d
AIC = −2L + 2
n
Cas gaussien et variance connue : AIC et Cp équivalents
AICc adapté aux petits échantillons gaussiens

n+d
AICc = −2L +
n−d−2

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Critère BIC de Schwarz

BIC (Bayesian information criterion)
modèle de plus grande probabilité a posteriori

d
BIC = −2L + log(n)
n
Cas gaussien et variance connue : BIC proportionnel à AIC
n > e2 ≈ 7, 4, BIC pénalise plus les modèles complexes
Asymptotiquement, la probabilité pour BIC de choisir le bon
modèle tend vers 1
différent d’AIC qui tend à choisir des modèles trop
complexes
À Taille fini, BIC risque de se limiter à des modèles trop
simples

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Algorithme de V-fold cross validation

Découper aléatoirement l’échantillon en V segments
(V-fold) de tailles similaires selon une loi uniforme ;
for k=1 à V
Mettre de côté le segment k,
Estimer le modèle sur les V − 1 segments restants,
Calculer la moyenne des erreurs sur le segment k
end for
Moyenner toutes les erreurs

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Utilisation
Soit τ : {1, . . . , n} 7→ {1, . . . , V} la fonction d’indexation
bf (−v) estimation de f sans le vième segment de l’échantillon
Estimation par validation croisée de l’erreur de prévision :
n
1X
CV =
Rd l(yi , bf (−τ (i)) (xi ))
n
i=1

Choix de V : n (variance), petit (biais), 10 par défaut

Utilisation fréquente en choix de modèle :

θb = arg min Rd
CV (θ)
θ

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Introduction au Bootstrap
Simulation (Monte Carlo) de la distribution d’un estimateur
Principe : substituer Pn , à la distribution inconnue P
Tirage avec remise d’un échantillon bootstrap de même
taille
Itération et convergence

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Estimateur bootstrap naı̈f

Échantillon bootstrap : z∗
Estimateur plug-in Pn (remplacer F par F de RP (f̂ (dn )) :
b
bn (f̂z∗ , dn ) = 1
R n i=1 l(yi , f̂z∗ (xi ))
f̂z∗ désigne l’estimation de f à partir de z∗
Estimation bootstrap de l’erreur moyenne de prévision
EDn ∼P⊗n [RP (f̂ (Dn )] :
bn (f̂Z∗ , Dn )] = E ∗ b 1 n l(yi , fZ∗ (xi ))
 P 
RBoot = E ∗ b [R Z ∼F Z ∼F n i=1

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Estimation bootstrap par simulation

B n
1X1X
Boot =
R[ l(yi , fz∗b (xi ))
B n
b=1 i=1

Estimation biaisée par optimisme

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Estimateur bootstrap out-of-bag

Distinguer les observations de l’échantillon bootstrap et les
autres
n
1X 1 X
Roob =
d l(yi , fz∗b (xi ))
n Bi
i=1 b∈Ki

Ki est l’ensemble des indices b des échantillons bootstrap

ne contenant pas la ième observation à l’issue des B
simulations
Bi = |Ki | est le nombre de ces échantillons
oob résout le problème d’un biais optimiste de RBoot mais
Rd [
biais pessimiste comme en validation croisée (Rd CV )

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Estimateur .632-bootstrap
Correctif basé sur la
probabilité qu’une observation soit tirée dans un
échantillon bootstrap :
1 1
P[xi ∈ x∗b ] = 1 − (1 − )n ≈ 1 − ≈ 0, 632
n e
Sur-évaluation de l’erreur analogue à celle de la validation
croisée avec K = 2
Compensation :

b.632 = 0, 368 × R
R bn (f̂ (Dn ), Dn ) + 0, 632 × R
boob

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Estimation sur échantillons indépendants
Risque, risque empirique
Estimation par pénalisation
Estimation d’un risque
Estimation par simulation
Discrimination à deux classes et courbe ROC

Remarques
Estimations de l’erreur asymptotiquement équivalentes
Pas de choix a priori
Bootstrap plus compliqué et encore peu utilisé mais
Central dans les algorithmes de combinaison de modèles
Problèmes du .632-bootstrap en sur-ajustement
Rectificatif complémentaire : le .632+bootstrap
Utiliser le même estimateur pour comparer deux méthodes

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Matrice de confusion
Estimation d’un risque Courbes ROC
Discrimination à deux classes et courbe ROC

Matrice de confusion - Notations

Prévision : Si π
bi > s, byi = 1 sinon byi = 0
Prévision Observation Total
Y=1 Y=0
byi = 1 n11 (s) n10 (s) n1+ (s)
byi = 0 n01 (s) n00 (s) n0+ (s)
Total n+ 1 n+ 0 n

Nombre de conditions positives P = n+1

Nombre de conditions négatives N = n0+
Vrais positifs TP = n11 (s) bien classés (byi = 1 et Y = 1),
Vrais négatifs TN = n00 (s) bien classés (byi = 0 et Y = 0),
Faux négatifs FN = n01 (s) mal classés (byi = 0 et Y = 1),
Faux positifs FP = n10 (s) mal classés (byi = 1 et Y = 0),
INSA de Toulouse - Apprentissage Statistique Qualité de prévision
 Introduction
Risque, risque empirique Matrice de confusion
Estimation d’un risque Courbes ROC
Discrimination à deux classes et courbe ROC

Notations
TN+TP FN+FP
Accuracy et Taux d’erreur : ACC = N+P =1− N+P
Taux de vrais positifs, sensitivity, recall TPR = TP
P
Taux de vrais négatifs spécificity, selectivity TNR = TN
N
Précision ou positive predictive value
TP
PPV = TP+FP = 1 − FDR
FP
Taux de faux positifs FPR = N = 1 − TNR
Taux de faux négatifs FNR = FN
P = 1 − TPR
FP
Taux de fausses découvertes FDR = FN+TN
F1 score ou moyenne harmonique de la précision et de la
2×TP
sensibilité, F1 = 2 × PPV×TPR
PPV+TPR = 2×TP+FP+FN ,
Fβ (β ∈ R+ ) score, Fβ = (1 + β 2 ) βPPV×TPR
2 PPV+TPR .

INSA de Toulouse - Apprentissage Statistique Qualité de prévision

 Introduction
Risque, risque empirique Matrice de confusion
Estimation d’un risque Courbes ROC
Discrimination à deux classes et courbe ROC

Taux de vrais positifs : TPR

ou sensibilité
Taux de faux positifs :
= FPR = 1 − Spécificité
AUC : aire sous la courbe
Score de Pierce :
H − F = TPR − FPN
Log loss
n L
1 XX
Ll = − πik )
yik log(c Banque : Courbes ROC et aire
n
i=1 k=1 sous la courbe

INSA de Toulouse - Apprentissage Statistique Qualité de prévision