Thomas G. Dietterich

2

PlanLa position des tests statistiques en apprentissage

5 tests :Le test de McNemar

Le test des différences de proportions

Le t-test reéchantillonné couplé (resampled paired t-test)

Le k-fois validation croisée t-test (k-fold cross-validated paired t-test)

Le 5x2cv paired t-test

Comparaison sur des données Artificielles

réelles

3

Rappel sur les tests d’hypothèses

IL s’agit de tester une hypothèse H1 contre une hypothèse H0 en utilisant une variable de décision X qui doit être une statistique.

Le comportement de X doit être connu sous H0 ;

On se donne une région d’acceptation Rok de l’hypothèse H0 pour X ;α erreur de première espèce (ou niveau du test) ;β erreur de seconde espèce ;1-β est la puissance du test ;

H0 vraie H1 vraie

P(H0 décidée) = P(XRok) 1-α β

P(H1 décidée) = P(XRok) α 1- β

4

Les statistiques en apprentissage

5

Les sources de problèmes

Sélection des données de test.

Sélection des données d’apprentissage (pbms avec arbres comme CART).

Certains algorithmes ont une variabilité interne (ex : rétropropagation)

Erreurs d’étiquetage de la base d’apprentissage

Un test idéal devrait prendre en compte tous ces points lors de l’établissement de sa région d’acceptation

6

NotationsSoit X l’ensemble des points de la population.

Il n’y a que deux classes possibles

f, fonction cible telle que xX, f(x) est la classe de x.

Pour apprendre, on dispose :d’un ensemble d’exemple S extraits de X selon une distribution fixée D.

Typiquement on divisera S en R et T

R « ensemble d’apprentissage »

T « ensemble de test »

On notera A et B les deux algorithmes que l’on souhaite comparer. le classifieur issu de l’application de A sur R

le classifieur issu de l’application de B sur R

L’hypothèse nulle H0 sera « et ont le même taux d’erreur sur X »

Af̂

Bf̂

Af̂ Bf̂

7

Test de McNemarOn effectue la division de S en R et T (typiquement répartition 2/3, 1/3)

On utilise A et B pour obtenir deux classifieurs

On construit la table de contingence

n00 nombre d’exemples mal classés par et

n01 nombre d’exemples mal classés par mais bien classés par

n10 nombre d’exemples mal classés par mais bien classés par

n00 nombre d’exemples bien classés par et

Sous H0 on attend :

Test de 2 a 1 ddl

Rejet au niveau 5% si

Pas de mesure de la variabilité de l’ensemble d’apprentissage

Pas de mesure de la variabilité interne de l’algorithme

La mesure se fait sur des ensemble de taille |R| et non |S|

n00 n01

n10 n11

Af̂ Bf̂

Af̂

Af̂

Af̂

Bf̂

Bf̂

Bf̂

n00 (n01 + n10 )/2

(n01 + n10 )/2 n11

841459.3

1

1001

2

1001

nn

nn

8

Différence de proportionsPrincipe :

pA=(n00+n10)/n : proportion d’individus mal classés par A

pB=(n00+n01)/n : proportion d’individus mal classés par B

On suppose que A a une probabilité pA de mal classer ; le nombre d’erreurs suit donc une loi binômiale. De même pour B. Si n est assez grand on peut les approximer par des lois normales donc Si on suppose que pA et pB sont indépendants pA-pB suit une loi normale.

Sous H0 c’est une avec p=(pA+pB)/2

donc on rejette H0 (test au niveau 5%) si

Problèmes :pA et pB sont mesurés sur T tous les deux et ne sont pas indépendants

Variations dus à l’ensemble d’apprentissage et à l’algorithme

Mesure des performances sur |R| et non sur |S|

Remarques : Rq : Il existe pour ces 2 tests des variantes sans approximations normales

Rq : on peut lever la dépendance en utilisant

n

ppN

)1(2,0

96,1/)1(2

npp

pp BA

96.1

1

1001

1001

nn

nn

9

Encart : test de Fisher-SnedecorCe test s’applique à deux échantillons gaussiens de même variance (à tester)

le 1er est tiré selon une N(m1,) (n1 tirages )et le 2ème une N(m2,) (n2 tirages )

H0 : « m1=m2 »

On sait que (ni si

2 / 2) suit un 2 à (ni-1) ddl (si écart type estimé dans les données)

La moyenne des xi suit une loi normale d’écart type (/ni)

(n1 s12 + n2 s2

2 )/ 2 suit un 2 à (n1+n2-2) ddl

La moyenne des x1 moins la moyenne des x2 suit une loi normale de moyenne m1-m2 et d’écart type (1/n1+1/n2).

Pour éliminer (inconnu) on utilise

On rejette H0 si |T|>cste tq P(|T|>cste / m1=m2)<

Si la taille de l’échantillon est suffisamment grande l’égalité des variances n’est plus nécessaire (qqes dizaines de mesures)

21

222

211

21

2121

212

222

211

21

2121

2

11

)(

)2(

11

)(

21nn

SnSnnn

mmXX

nn

SnSn

nn

mmXX

T nn

10

Resampled t-testPrincipe :

Un essai i (on en réalise k) est une division de S en R(i) et T(i)

A chaque essai i on estime pA(i)

et pB(i)

Si on suppose que les différences p(i) = pA

(i) - pB

(i) sont tirées indépendamment selon une loi normale, on peut utiliser un test de Student sur t (k-1 ddl):

Pour 30 essais on rejette (test au niveau 95%) si |t|>2.04523

Problèmes :p(i) n’a pas une distribution normale (pA

(i) et pB

(i) ne sont pas indépendants)

Les p(i) ne sont pas indépendants (à cause des intersections non vides des R (i) et T(i)).

2

1

)(

1

)(

.

k

pp

kpt

k

i

i

11

k-fold cross-validated paired t-test

Principe :Au lieu de diviser S en deux, on le divise en k ensembles disjoints de même taille :

T1,…,Tk

On fait k essais. Dans l’essai i Ti est l’ensemble de test et tous les autres T j sont utilisés pour l’apprentissage. On utilise la même statistique t que précédemment.

Avantage : Chacun des ensembles de tests sont indépendants les uns des autres

Problème : les ensembles d’apprentissages se chevauchent beaucoup

2

1

)(

1

)(

.

k

pp

kpt

k

i

i

12

5x2cv paired t-testPrincipe :

Dans le k-cross validated t-test, la variance n’est que légèrement sous-estimée à cause des chevauchements des ensembles d’apprentissage. Par contre l’évaluation des proportions (numérateur) est occasionnellement mauvais (grand)

Si le numérateur est remplacé par celui d’une 2-fold cross validation, expérimentalement, les choses se passent mieux.

On effectue 5 répétitions d’un 2-fold cross-validated test.

A chaque répétition i, S est divisé en Si,1 et Si,2. On obtient 4 estimateurs de taux d’erreur :

pi,A(1) et pi,B

(1) (entraînés sur S1 testés sur S2) pi(1) = pi,A

(1) - pi,B(1)

pi,A(2) et pi,B

(2) (entraînés sur S2 testés sur S1) pi(2) = pi,A

(2) - pi,B(2)

soit si l’écart type estimé dans la ième réplication

On définit la statistique :

Sous H0 elle suit approximativement un Student à 5 degrés de libertés. (On utilise l’approximation d’une binômiale par une loi normale et on suppose l’indépendance deux à deux des p i

(1) et pi(2) )

2

1

)(

1

)(

.

k

pp

kpt

k

i

i

2)2(2)1(2 )()( iiiii pppps

5

1

2

)1(1

5

1

~

iis

pt

13

Simulations d’algorithmes

14

Erreur de première espèce1000 tests ; 300 exemples/test ; niveau 0.05

10-fold cross validated test ; taux d’erreur décalé de [-0.02,0.02] aléatoirement

Pas de simulation de la variation des ensembles d’apprentissage ni de la dépendance entre les données.

Erreur de première espèce : on rejette H0 alors qu’elle est vraie

15

Pourquoi ?Tout est dans la forme de la région d’acceptation.

Identiques du point de vue du test des proportions mais pas du test de McNemar

Mauvaises performances du Resampled t-test sont dues au fait que les sous ensembles peuvent ne pas contenir le même nombre de bien classés et de mal classés assez facilement car les régions de performances des deux algorithmes sont différentes.

0 40

60 0

40 0

20 40

16

Sur des données réelles Comparaison entre C4.5 et plus proches voisins sur 3 jeux de données.

Il faut « endommager » les algorithmes pour qu’ils aient les mêmes performances.

Pour les plus proches voisins, on perturbe la métrique (2 premiers jeux de données)

Pour C4.5 on le force à faire des erreurs à un taux spécifié.

17

Puissance (1) C’est la probabilité de rejeter H0 alors que H0 est fausse

On fait varier entre 0 et 1 pour que C4.5 et NN aient les mêmes performances.

18

Puissance (2)

19

Conclusion

Tous les tests statistiques font des approximations qui peuvent se révéler gênantes

Pour conclure sur le fait que A et B ont des performances différentes, Il est recommandé d’utiliser soit le 5x2cv t-test (si l’algorithme d’apprentissage peut-être répété 10 fois) ou le test de McNemar.

Si le but est de conclure que A et B ont des performances identiques, c’est 10-fold cross-validated t-test qui doit être utilisé.

Resampled t-test ne devrait pas être utilisé (erreur de type I élevée)