Évaluation de l’apprentissage: méthodes

A. Cornuéjols

LRI

(basé sur Sebastian Thrun CMU class)

Évaluation de l’apprentissage:méthodes

A. Cornuéjols

Évaluation 2

Questions

L’induction est une forme d’inférence faillible, il faut donc savoir évaluer sa qualité

Questions types:

– Quelle est la performance d’un système sur un type de tâche ?

– Est-ce que mon système est meilleur que l’autre ?

– Comment dois-je régler mon système ?

A. Cornuéjols

Évaluation 3

Approches

Évaluation théorique a priori– Dimension de Vapnik-Chervonenkis

– Critères sur la complexité des modèles : MDL / AIC / BIC

• Estimer l’optimisme de la méthode et ajouter ce terme au taux d’erreur

Évaluation empirique– E.g. taux d’erreur : (dans le cas d’un classifieur binaire avec une

fonction de coût lié au nombre derreurs)

A. Cornuéjols

Évaluation 4

Plan

1. Mesurer la performance

2. Méthodes de validation

3. Matrices de confusion et courbe ROC

4. La comparaison de méthodes d’apprentissage

5. Autres mesures de performance

A. Cornuéjols

Évaluation 5

Évaluation des hypothèses produites

beaucoup

de donnéstrès peu

de données

données illimitées

A. Cornuéjols

Évaluation 6

Ensembles de données(collections)

Toutes les données disponibles

Ensemble d’apprentissage

Ensemble de test

Ensemble de validation

A. Cornuéjols

Évaluation 7

Prédiction asymptotique(le cas idéal)

Useful for very large data sets

A. Cornuéjols

Évaluation 8

Le sur-apprentissage (over-learning)

Erreur

t

erreur sur basede test

erreur sur based'apprentissage

Arrêt de l'apprentissage

Sur-apprentissage

A. Cornuéjols

Évaluation 9

Utilisation de l’ensemble de validation

On règle les paramètres de l’algorithme

d’apprentissage

• E.g. : nb de couches cachées, nb de neurones, ...

– en essayant de réduire l’erreur de test

Pour avoir une estimation non optimiste de

l’erreur, il faut recourir à une base d’exemples non

encore vus : la base de validation

A. Cornuéjols

Évaluation 10


beaucoup peu de données

A. Cornuéjols

Évaluation 11

Évaluation de l’erreur

Erreur vraie:

Erreur de test:

∫ −=D

D ydxyxpxfye ,),(),( θ

∑∈

−=Syx

S xfym

e,

),(1

ˆ θ

D = toutes les données possibles

m = # de données test

T = données test

(Risque réel)

(Risque empirique) T

A. Cornuéjols

Évaluation 12

Exemple:

L’hypothèse classe mal 12 des 40 exemples dans l’ensemble de test T.

Q : Quelle sera l’erreur sur des exemples non vus ?

R : ???

A. Cornuéjols

Évaluation 13

Intervalle de confiance (1)

Définition : un intervalle de confiance à N% pour une variable p est l’intervalle dans lequel sa valeur est attendue avec une probabilité de N%

Soit une probabilité d’erreur (pour 2 classes) de p, la probabilité d’avoir r erreurs sur n évènements est :

(loi binomiale)

Espérance du nombre d’erreurs

Variance

Ecart-type

A. Cornuéjols

Évaluation 14

Intervalles de confiance (2)

La loi binomiale peut être estimée par la loi normale si n p (1 - p) ≥ 5 de même moyenne et même variance

A. Cornuéjols

Évaluation 15


Que l’on estime par la loi normale

– De moyenne :

– D’écart-type :

Je voudrais évaluer erreurD(h).

Je l’estime en utilisant erreurT(h) qui est régie par une loi binomiale

– De moyenne

– D’écart-type

A. Cornuéjols

Évaluation 16


Loi normale Loi normale

A. Cornuéjols

Évaluation 17


Avec une probabilité de N%, l’erreur vraie erreurD est dans l’intervalle :

N% 50% 68% 80% 90% 95% 98% 99%

zN 0.67 1.0 1.28 1.64 1.96 2.33 2.58

A. Cornuéjols

Évaluation 18

Intervalles de confiance (cf. Mitchell 97)

Si– T contient m exemples tirés indépendamment

– m 30

Alors

– Avec une probabilité de 95%, l’erreur vraie eD est dans

l’intervalle :

m

eee SS

S

)ˆ1(ˆ96.1ˆ

−±

A. Cornuéjols

Évaluation 19

Exemple:

L’hypothèse classe mal 12 des40 exemples dans la base de test T.

Q: Quelle sera l’erreur vraie sur les exemples non vus ?

A: Avec 95% de confiance, l’erreur vraie sera dans l’intervalle :

m

eee SS

S

)ˆ1(ˆ96.1ˆ]44.0;16.0[

−±≈

3.040

12ˆ ==Se40=m 14.0

)ˆ1(ˆ96.1 ≈

−m

ee SS

A. Cornuéjols

Évaluation 20

Intervalles de confiance à 95%

A. Cornuéjols

Évaluation 21

Courbes de performance

Erreur de test

intervalle de confiance à 95%

Erreur d’apprentissage

A. Cornuéjols

Évaluation 22

Comparaison de différentes hypothèses

On cherche la différence vraie:

On estime par :

Qui est une loi normale différence de 2 lois normales

Intervalle de confiance à 95% :

)(ˆ)(ˆˆ21 θθ SS eed −=

)()( 21 θθ DD eed −=

2

22

1

11 ))(ˆ1()(ˆ))(ˆ1()(ˆ96.1ˆ

m

ee

m

eed SSSS θθθθ −

+−

±

Rq : il faudrait normalement ne pas tester les deux hypothèses sur le même ensemble de test. La variance obtenue avec un même ensemble de test est un peu plus faible (cf. paired t tests).

A. Cornuéjols

Évaluation 23


Beaucoup

de données

peu

A. Cornuéjols

Évaluation 24

Différents ensembles

Données

test erreurapprentissage

A. Cornuéjols

Évaluation 25

Validation croisée à k plis (k-fold)Données

Apprend sur jaune, test sur rose erreur5








erreur = erreuri / k

k-way split

A. Cornuéjols

Évaluation 26

Procédure “leave-one-out”Données

Faible biais

Haute variance

Tend à sous-estimer l’erreur si les données ne sont pas vraiment i.i.d.

[Guyon & Elisseeff, jMLR, 03]

A. Cornuéjols

Évaluation 27

Le Bootstrap

Données

Répéter et faire la moyenne

Apprend sur jaune, test sur rose erreur

A. Cornuéjols

Évaluation 28

Problème

Le calcul des intervalles de confiance suppose l’indépendance des estimations.

Mais nos estimations sont dépendantes.

Estimation du risqueréel pour h finale

Moy. du risque surles k ens. de test

Moy. du risque surl’ens. des données

A. Cornuéjols

Évaluation 29

La comparaison de différentes hypothèses : Paired t test

Vraie différence:

Pour chaque partition k:

Moyenne:

Intervalle de confiance à N% :

∑=

=k

iid

kd

1

ˆ1ˆ

)()( 21 θθ DD eed −=

∑=

− −−

±k

iikN kk

td1

21, )ˆˆ(

)1(

1ˆ δδ

erreur de test

pour la partition k

)(ˆ)(ˆˆ2,1, θθ kSkSk eed −=

k-1 degrés de liberté N : intervalle de confiance

tN, 90% 95% 98% 99%

=2 2.92 4.30 6.96 9.92

=5 2.02 2.57 3.36 4.03

=10 1.81 2.23 2.76 3.17

=20 1.72 2.09 2.53 2.84

=30 1.70 2.04 2.46 2.75

=120 1.66 1.98 2.36 2.62

= 1.64 1.96 2.33 2.58

A. Cornuéjols

Évaluation 30

Les types d’erreurs

A. Cornuéjols

Évaluation 31

Matrice de confusion

Réel

Estimé + -

+ VP FP

- FN VN

A. Cornuéjols

Évaluation 32

Matrice de confusion14% des poissons sont pris pour des papillons

A. Cornuéjols

Évaluation 33

Types d’erreurs

Erreur de type 1 (alpha) : faux positifs– Probabilité d’accepter l’hypothèse alors qu’elle est

fausse

Erreur de type 2 (beta) : faux négatifsfaux négatifs– Probabilité de rejeter l’hypothèse alors qu’elle est vraie

Comment arbitrer entre ces types d’erreurs ?

A. Cornuéjols

Évaluation 34

Courbe ROC

Critère de décision

Probabilité

de la classe

Classe '+'Classe '-'

ROC = Receiver Operating Characteristic

A. Cornuéjols

Évaluation 35

La courbe ROC


Probabilité

de la classe

Classe '+'


Probabilité

de la classe

Classe '-'

Vraispositifs

Fauxnégatifs

Fauxpositifs

Vraisnégatifs

(50%)(50%)

(90%)(10%)

A. Cornuéjols

Évaluation 36

La courbe ROCPROPORTION DE VRAIS NEGATIFS

PROPORTION DE FAUX POSITIFS

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

PROPORTION DE VRAIS POSITIFS

PROPORTION DE FAUX NEGATIFS

Ligne de hasard(pertinence = 0,5)

Courbe ROC(pertinence = 0,90)

A. Cornuéjols

Évaluation 37

La courbe ROC

PROPORTION DE VRAIS NEGATIFS

PROPORTION DE FAUX POSITIFS0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0



Ligne de hasard(pertinence = 0,5)

Courbe ROC(pertinence = 0,90)

PROPORTION DE VRAIS NEGATIFS

PROPORTION DE FAUX POSITIFS0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

0,1

0,2

0

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0



Critère de déci-sion

Probabilitéde la classeClasse '+'


Probabilitéde la classeClasse '-'

VraispositifsFauxnégatifs

FauxpositifsVraisnégatifs


Probabilitéde la classeClasse '+'


Probabilitéde la classeClasse '-'

VraispositifsFauxnégatifs

FauxpositifsVraisnégatifs(50%)(50%)

(90%)(10%)

Seuil "laxiste"

Seuil "sévère"

A. Cornuéjols

Évaluation 38

Courbe ROC

Spécificité

Sensibilité

VP

VP + FN

Réel

Estimé

+ -

+ VP FP

- FN VN

VN

FP + VN

Rappel

Précision

VP

VP + FN

VP

VP + FP

A. Cornuéjols

Évaluation 39

Résumé Attention à votre fonction de coût :

– qu’est-ce qui importe pour la mesure de performance ?

Données en nombre fini: – calculez les intervalles de confiance

Données rares : – Attention à la répartition entre données d’apprentissage et données test. Validation

croisée.

N’oubliez pas l’ensemble de validation

L’évaluation est très importante– Ayez l’esprit critique

– Convainquez-vous vous même !

A. Cornuéjols

Évaluation 40

Problèmes particuliers

Distribution des exemples + / - très déséquilibrée (e.g. 1% ou 1%O )

Existence de « zones grises » (étiquettes peu informées)

Tâche multi-objectif

A. Cornuéjols

Évaluation 41

Autres critères d’évaluation

Intelligibilité des résultats (hypothèses produites)– E.g. exit les réseaux de neurones

Performances en généralisation– Pas toujours en adéquation totale avec le point précédent

Coûts – de préparation (des données)

– coût computationnel (e.g. coût d’une passe et nombre de passes nécessaires, …)

– coût de l’expertise en apprentissage

– coût de l’expertise sur le domaine

A. Cornuéjols

Évaluation 42

Références

Littérature très vaste sur les tests statistiques

Dietterich, T. G., (1998). Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms. Neural Computation, 10 (7) 1895-1924.

Guyon, I., & Elisseeff, A. (2003). An introduction to variable and feature selection. Journal of Machine Learning Research, 3, 1157-1182.

Documents

Évaluation de l’apprentissage: méthodes