Apprentissage statistique
Cadre de la classification supervisée
Problématique de choix de modèles
Jean-Michel Marin
Université de Montpellier
Institut Montpelliérain Alexander Grothendieck (IMAG)
Institut de Biologie Computationelle (IBC)
HMMA 303
Jean-Michel Marin (IMAG) Objectifs HMMA 303 1 / 33
1 Prédiction
Contexte
Formalisation
Prédicteur optimal
2 Risque
3 Stratégies d’estimation
4 Problématique de sélection de modèles et complexité
5 Risque et complexité
6 Méthodes pratiques de sélection de modèles
Méthode de validation
Méthode de la validation croisée
Jean-Michel Marin (IMAG) Objectifs HMMA 303 2 / 33
Prédiction
Contexte
On dispose des données (x1 , y1 ), . . . , (xn , yn ) fournies par l’ob-
servation d’un système
On fait l’hypothèse qu’il y a une dépendance entre les compor-
tements des couples (x, y) ∈ E × F
On souhaite, à partir des données, extraire cette dépendance
pour prédire y lorsque l’on observe x
Jean-Michel Marin (IMAG) Objectifs HMMA 303 3 / 33
Prédiction
Contexte
Example (filtrage de spams)
Dans une base de données de courriels classés spam ou non
spam se trouve les fréquences relatives de 60 mots
On veut construire un filtre automatique de spam qui déciderait
au vu des fréquences relatives des 60 mots si l’on a affaire à un
spam ou non
n correspond au nombre de courriels dans la base de données
d’apprentissage (x1 , y1 ), . . . , (xn , yn )
E = [0, 1]⊗60 et F = {spam, non spam}
Jean-Michel Marin (IMAG) Objectifs HMMA 303 4 / 33
Prédiction
Contexte
Example (reconnaissance de caractères manuscrits)
Un procédé de lecture optique produit des images 16 × 16 de
chiffres manuscrits
On veut construire un système de reconnaissance automatique
qui interprète une image quelconque
Si chaque pixel est binaire, alors E = {0, 1}⊗256 et
F = {0, 1, . . . , 9}
Jean-Michel Marin (IMAG) Objectifs HMMA 303 5 / 33
Prédiction
Contexte
Example (credit scoring)
On dispose de données sur les risques de crédit
x vecteur contenant des informations sur la personne ayant
sollicité un crédit
y est binaire et code le fait qu’il y a eu ou pas un incident de
paiement
Objectif : construire un prédicteur qui identifie les individus à
risque
Jean-Michel Marin (IMAG) Objectifs HMMA 303 6 / 33
Prédiction
Contexte
Example (aide au diagnostic médical)
Des données relatives au risque d’infarctus du myocarde ont
été collectées pour plusieurs centaines d’individus males d’une
population
x est le vecteur de 7 coordonnées relatives à la pression
sanguine, la consommation de tabac, le cholestérol, la
présence d’antécédents familiaux, l’obésité, la consommation
d’alcool et l’âge
y, binaire, code le fait que l’individu a ou non fait un infarctus
Objectif : construire un prédicteur qui détecte les sujets à risque
Jean-Michel Marin (IMAG) Objectifs HMMA 303 7 / 33
Prédiction
Formalisation
Hypothèse : (X1 , Y1 ), . . . , (Xn , Yn ), la base de données d’ap-
prentissage, constituent un n-échantillon du couple (X, Y) à va-
leurs dans E × F :
I (Xi , Yi ) ⊥
⊥ (Xj , Yj ) pour tout i , j
I les couples (Xi , Yi ) ont la même loi de probabilités
I (xi , yi ) est la réalisation de (Xi , Yi )
Y est la variable à prédire, la réponse
X est le vecteur des variables prédictives
Jean-Michel Marin (IMAG) Objectifs HMMA 303 8 / 33
Prédiction
Formalisation
Definition
On appelle prédicteur de Y à partir de X toute fonction
g : E −→ F
La qualité d’un prédicteur est mesurée par son coût moyen
Definition
Le coût moyen d’un prédicteur g est
C(g) = E [h(Y, g(X))]
où h est une fonction de coût unitaire h : F × F −→ R+ qui
facture l’écart entre la valeur prédite et la valeur observée
Jean-Michel Marin (IMAG) Objectifs HMMA 303 9 / 33
Prédiction
Formalisation
Example (classification binaire)
Y ∈ F = {0, 1}
Supposons que h(0, 0) = h(1, 1) = 0
h(0, 1) = a > 0 et h(1, 0) = b > 0
Comparons deux classifieurs
0 avec proba 1/2
I le hasard g1 (x) =
1 avec proba 1/2
I celui consistant à affecter tout le monde à la classe 1
g2 (x) = 1
Jean-Michel Marin (IMAG) Objectifs HMMA 303 10 / 33
Prédiction
Formalisation
Example (classification binaire - suite)
Calculons le coût moyen de g1
g1 (x) = 1U>1/2 où U est une variable aléatoire suivant une loi
uniforme sur [0, 1]
C(g1 ) = E [h(Y, g1 (X))]
= aP({Y = 0} ∩ {U > 1/2}) + bP({Y = 1} ∩ {U < 1/2})
a b
= P(Y = 0) + P(Y = 1)
2 2
Jean-Michel Marin (IMAG) Objectifs HMMA 303 11 / 33
Prédiction
Formalisation
Example (classification binaire - suite)
Calculons le coût moyen de g2
C(g2 ) = E [h(Y, 1)]
= aP(Y = 0)
Jean-Michel Marin (IMAG) Objectifs HMMA 303 12 / 33
Prédiction
Formalisation
Example (classification binaire - suite)
Comparons les deux coûts
C(g1 ) 6 C(g2 )
a b
P(Y = 0) + P(Y = 1) 6 aP({Y = 0}
2 2
a b b
P(Y = 0) + P(Y = 0) >
2 2 2
b
P(Y = 0) >
a+b
Cas particulier du coût symétrique a = b
1
C(g1 ) 6 C(g2 ) ⇐⇒ P(Y = 0) >
2
Jean-Michel Marin (IMAG) Objectifs HMMA 303 13 / 33
Prédiction
Prédicteur optimal
Definition
Le prédicteur optimal est celui qui a le coût moyen le plus faible
On se place dans le cas de la classification supervisée binaire
F = {0, 1}
On considère la fonction de coût élémentaire la plus générale
h(0, 0) = h(1, 1) = 0, h(0, 1) = a, h(1, 0) = b
On cherche le classifieur g∗ qui minimise le coût moyen
g∗ ∈ arg min C(g)
g
Jean-Michel Marin (IMAG) Objectifs HMMA 303 14 / 33
Prédiction
Prédicteur optimal
Nous remarquons que C(g) = E [h(Y, g(X))] = E[E[h(Y, g(X))|X]]
Minimiser C(g) est équivalent à minimiser
E[h(Y, g(X))|X = x] pour tout x ∈ E
Le minimum point par point minimise également l’intégrale
On cherche donc à minimiser
E[h(Y, g(X))|X = x] =
a1g(x)=1 P(Y = 0|X = x) + b1g(x)=0 P(Y = 1|X = x)
Jean-Michel Marin (IMAG) Objectifs HMMA 303 15 / 33
Prédiction
Prédicteur optimal
On obtient
a
1 si P(Y = 1|X = x) > a+b
∗ a
g (x) = 0 si P(Y = 1|X = x) <
a+b
a
1 ou 0 si P(Y = 1|X = x) = a+b
Cas particulier coût symétrique a = b
1 si P(Y = 1|X = x) > 1/2
g∗ (x) = 0 si P(Y = 1|X = x) < 1/2
1 ou 0 si P(Y = 1|X = x) = 1/2
Jean-Michel Marin (IMAG) Objectifs HMMA 303 16 / 33
Prédiction
Prédicteur optimal
g∗ (x) = 1P(Y=1|X=x)>1/2
est appelé le classifieur de Bayes
Ne pas confondre avec la règle de Bayes
P(B|A)P(A)
P(A|B) =
P(B)
Jean-Michel Marin (IMAG) Objectifs HMMA 303 17 / 33
Prédiction
Prédicteur optimal
Lorsque a = b = 1,
h(Y, g(X)) = 0 si classification correcte
h(Y, g(X)) = 1 si erreur de classification
=⇒ C(g) est alors le taux d’erreur de classification
Le classifieur de Bayes est celui qui minimise le taux d’erreur de
classification
Jean-Michel Marin (IMAG) Objectifs HMMA 303 18 / 33
Risque
Un algorithme d’apprentissage prend en entrée un échantillon
An = {(X1 , Y1 ), . . . , (Xn , Yn )} et rend en sortie un prédicteur
ĝAn : E −→ F
ĝAn est une fonction aléatoire, sa performance s’apprécie à la
valeur de son risque R
R(ĝAn ) = E[C(ĝAn )]
= EAn E(X,Y) [h(Y, ĝAn (X)]
Jean-Michel Marin (IMAG) Objectifs HMMA 303 19 / 33
Stratégies d’estimation
Definition
Le coût empirique du prédicteur g, noté CAn (g), est tel que
1X
n
CAn (g) = h(Yi , g(Xi ))
n
i=1
Dans le cas de la classification supervisée binaire et pour la
fonction de coût symétrique avec a = b = 1, le coût empi-
rique correspond à la proportion de mal classés par g dans
l’échantillon d’apprentissage
1X
n
CAn (g) = 1Yi ,g(Xi )
n
i=1
Jean-Michel Marin (IMAG) Objectifs HMMA 303 20 / 33
Stratégies d’estimation
Il existe trois stratégies
Méthode 1 on minimise le coût empirique par rapport à g ∈ G
où G est une certaine classe de fonction
Cette stratégie ne fait sens que si les fonctions appartenant à G
sont de même niveau de complexité
Méthode 2 le seconde stratégie vise dans un premier temps à
l’estimation de PY|X=x pour tout x ∈ E, la loi de probabilité de
Y|X = x
puis à utiliser cette estimation pour construire un classifieur, en
singeant éventuellement le classifieur ayant le coût moyen mini-
mal
Jean-Michel Marin (IMAG) Objectifs HMMA 303 21 / 33
Stratégies d’estimation
Pour estimer P(Y = 1|X = x) on procède comme suit
I on estime les densités conditionnelles de X sachant Y = 0
et Y = 1 par f̂0 (x) et f̂1 (x)
I on estime la loi marginale de Y, π0 = P(Y = 0) et
π1 = P(Y = 1), par π̂0 et π̂1
I on applique la règle de Bayes et on estime P(Y = 0|X = x)
par
π̂0 f̂0 (x)
P̂(Y = 0|X = x) =
π̂0 f̂0 (x) + π̂1 f1 (x)
On peut alors construire un classifieur à l’aide de P̂(Y = 0|X = x)
et P̂(Y = 1|X = x) = 1 − P̂(Y = 0|X = x)
Jean-Michel Marin (IMAG) Objectifs HMMA 303 22 / 33
Stratégies d’estimation
Méthode 3 on modélise directement P(Y = 1|X = x)
C’est ce que l’on fait dans le cas de la régression logistique
tout est conditionné à x
Jean-Michel Marin (IMAG) Objectifs HMMA 303 23 / 33
Problématique de sélection de modèles et complexité
Les méthodes d’apprentissage laissent souvent à l’utilisateur le
soin du réglage de paramètres qui ont un impact sur la com-
plexité des prédicteurs auxquels elles donnent accès
Une fois fixé les valeurs de ces paramètres, l’ensemble des
prédicteurs potentiels est ce que l’on appelle un modèle
Jean-Michel Marin (IMAG) Objectifs HMMA 303 24 / 33
Problématique de sélection de modèles et complexité
Example (classification par régression)
E = Rp et F = {0, 1} classification supervisée binaire et p
variables prédictives quantitatives
On utilise la procédure suivante
I on estime un régresseur linéaire par la méthode des
moindres carré
f̂An (x) = α̂0 + α̂1 x(1) + . . . + α̂p x(p)
à l’aide de An
I on propose comme classifieur
ĝAn (x) = 1 ⇐⇒ f̂An (x) > 1/2
Jean-Michel Marin (IMAG) Objectifs HMMA 303 25 / 33
Problématique de sélection de modèles et complexité
Example (classification par régression - suite)
Pour toute sorte de raison, on peut envisager d’appliquer cette
procédure à des parties + ou - restreintes de l’ensemble des
variables
Fixer un sous-ensemble de régresseurs c’est choisir un modèle
Une mesure de complexité est par exemple le nombre de
variables
Jean-Michel Marin (IMAG) Objectifs HMMA 303 26 / 33
Problématique de sélection de modèles et complexité
Example (méthode des k-plus-proches voisins)
E = Rd et F = {0, 1}
Elle fonctionne comme suit
I pour tout x ∈ E on note VAn ,k (x) l’ensemble contenant les
k-plus-proches voisins de x au sens d’une distance bien
choisie
I ĝAn ,k (x) est la classe majoritaire dans VAn ,k (x)
En cas d’égalité, on prend la classe majoritaire sur les
k − 1-plus-proches voisins
L’entier k joue sur le comportement du classifieur : plus k est
grand moins le classifieur est complexe
Jean-Michel Marin (IMAG) Objectifs HMMA 303 27 / 33
Risque et complexité
Le coût empirique sous-estime le risque pour les modèles com-
plexes
Avec le coût empirique, on choisit toujours le modèle le plus
complexe
Donner trop de flexibilité au modèle conduit à des classifieurs
de mauvaise qualité, c’est le phénomène de sur-apprentissage
(overfitting)
Jean-Michel Marin (IMAG) Objectifs HMMA 303 28 / 33
Méthodes pratiques de sélection de modèles
Idée de base ne pas se fier au coût empirique calculé
sur l’échantillon qui a servi à faire l’estimation/la prédiction
1X
n
CAn (ĝAn ) = h(Yi , ĝAn (Xi ))
n
i=1
est un mauvais estimateur de
R(ĝAn ) = EAn E(X,Y) [h(Y, ĝAn (X)]
On voudrait choisir un modèle, ie un niveau de complexité en
fonction du risque
On veut déterminer le modèle de risque le plus faible et pour
cela nous devons estimer le risque
Jean-Michel Marin (IMAG) Objectifs HMMA 303 29 / 33
Méthodes pratiques de sélection de modèles
Méthode de validation
Lorsque l’on a beaucoup de données (n très grand) un usage
courant est de séparer les données en 2 parties à peu près
égales
I A données d’apprentissage à l’aide desquelles sont
construits les prédicteurs A ⊂ AN , #A ≈ n/2
I T données de test qui servent à évaluer la qualité des
prédicteurs à l’aide de
1 X
CT (ĝA ) = h(y, ĝA (x))
#T
(x,y)∈T
T ⊂ An et #T ≈ n/2
Jean-Michel Marin (IMAG) Objectifs HMMA 303 30 / 33
Méthodes pratiques de sélection de modèles
Méthode de la validation croisée
Dans le cas précédent, on peut renverser les rôles joués par A
et T , on croise
De manière générale, lorsque la masse des données est insuf-
fisante on découpe notre jeu de données en plus de 2 parties.
on utilise la méthode de la validation croisée à K ensembles (K-
fold-cross-validation)
Objectif : estimer les risques associés aux différents modèles et
comparer les risques pour choisir un modèle
Jean-Michel Marin (IMAG) Objectifs HMMA 303 31 / 33
Méthodes pratiques de sélection de modèles
Méthode de la validation croisée
Algorithme
I on divise les données en K parties disjointes (partition) de
taillesP
égales (si possible) B1 , . . . , BK de tailles n1 , . . . , nK
avec K i=1 ni = n
I pour chaque i ∈ {1, . . . , K}
on utilise A−i = AnP /Bi pour calculer ĝA−i (x) ∈ F
on calcule R̂i = n1i (x,y)∈Bi h(y, ĝAi (x))
I on calcule l’estimateur final du risque
1X
K
R̂ = R̂i
K
i=1
Jean-Michel Marin (IMAG) Objectifs HMMA 303 32 / 33
Méthodes pratiques de sélection de modèles
Méthode de la validation croisée
Si n est grand relativement à p = dim(E) (nombre de variables
prédictives) on prend K = 2
Si n est de taille moyenne, on prend K = 5 ou K = 10
Si n est petit, on prend K = n, leave-one-out cross validation
Jean-Michel Marin (IMAG) Objectifs HMMA 303 33 / 33
