59
1 Introduction à la théorie de l’apprentissage statistique Gilbert Saporta Chaire de Statistique Appliquée & CEDRIC CNAM 292 rue Saint Martin, F-75003 Paris [email protected] http://cedric.cnam.fr/~saporta

Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

1

Introduction à la théorie de l’apprentissage statistique

Gilbert SaportaChaire de Statistique Appliquée & CEDRIC CNAM292 rue Saint Martin, F-75003 Paris

[email protected]://cedric.cnam.fr/~saporta

Page 2: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

2

Guillaume d’Ockham 1320

Norbert Wiener 1948

Frank Rosenblatt 1962

Vladimir Vapnik 1982

Page 3: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

3

Une introduction aux théories de V.Vapnik(rédigée en collaboration avec Michel Béra, chaire de modélisation statistique du risque)

Page 4: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

4

Le problème de la boîte noire et l’apprentissage supervisé

Etant donnée une entrée x, un système non déterministe renvoie une variable y = f(x)+e. On dispose de n paires (xi,yi) et on cherche une fonction qui approxime la fonction inconnue f.Deux conceptions:

• Une bonne approximation est une fonction proche de f• Une bonne approximation est une fonction qui donne

un taux d’erreur voisin de celui de la boîte noire

Page 5: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

5

Risque d’apprentissage

Apprentissage “supervisé” Y réponse à prédire, X prédicteurs

Y numérique régression ; binaire (-1;+1) discriminationUn modèle calcule un prédicteur

où:f classe de fonctionw est un paramètre qui définit le modèle, estimé surl’ensemble d’apprentissage

),(ˆ wXfy =

Page 6: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

6

Fonction de perte L(y;f(x,w))Régression L(y;f(x,w))=(y-f(x))2

Discrimination : taux (ou coût) d’erreur de classement• y et à valeurs dans {-1 ;+1}

Risque (erreur de généralisation sur de nouvelles données z = (X, y) )

( ) ( , ) ( )R E L L z w dP z= = ∫

( )21 1ˆ ˆ ˆ( ; )2 4

L y y y y y y= − = −

y

Page 7: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

7

Objectif impossible: minimiser sur w le Risque

P(z) probabilité inconnue

On dispose seulement de n casd’apprentissage (z1, .. , zn) tirés suivant la loiP(z), au lieu de minimiser R, on minimise le Risque Empirique :

1

1 ( ; ( ; ))n

emp i ii

R L y fn =

= ∑ x w

Page 8: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

8

Problème central en théorie de l’apprentissage:Quelle est la relation entre le Risque R et le risque empirique Remp ?

Quelle est la capacité de généralisation de ce genre de modèle?

Page 9: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

9

Le dilemme biais-variance

Modèle y=f(x )+ε, f estimé sur données d’apprentissageErreur de prédiction

Doublement aléatoire

Erreur quadratique moyenne de prédiction (risque R)

0 0 0 0ˆˆ ( ) ( )y y f x f xε− = + −

( ) ( ) ( )( ) ( )222 2 20 0 0 0 0 0 0

ˆ ˆ ˆˆ ( ) ( ) ( ) ( ) ( )E y y E f x f x E f x f x V f xσ σ− = + − = + − +

biais variance

Page 10: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

10

• premier terme: aléa irréductible• deuxième terme: carré du biais du modèle • troisième terme: variance de la prédiction

Plus un modèle sera complexe plus le biais sera faible, mais au détriment de la variance.

Mais comment mesurer la complexité?

( ) ( ) ( )( ) ( )222 2 20 0 0 0 0 0 0

ˆ ˆ ˆˆ ( ) ( ) ( ) ( ) ( )E y y E f x f x E f x f x V f xσ σ− = + − = + − +

Page 11: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

11

Robustesse

Modèle robuste: erreurs en apprentissage et en généralisation du même ordre de grandeur

Page 12: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

12

Modele robuste bon ajustement

Compromis

x

Y

x

Y

x

Y

Page 13: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

13

Consistence

Un processus d’apprentissage est consistent sil’erreur sur l’ensemble d’apprentissageconverge, lorsque la taille de cet ensemble augmente, vers l’erreur en généralisation.

Page 14: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

14

%erreur

Taille ens. d’apprentissage

Erreur en généralisation

Erreur d’apprentissage

Apprentissage consistent

Page 15: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

15

Taille ens. d’apprentissage

%erreurErreur en généralisation

Erreur d’apprentissage

Apprentissage non consistent

Page 16: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

16

Les quatre piliers de la théorie de l’apprentissage

1 Consistence (garantit la généralisation)Sous quelles conditions un modèle peut-il généraliser?

2 Vitesse de convergence en fonction du nombred’exemples (mesure de la généralisation)

Comment s’améliore la généralisation lorsque le nombred’exemples augmente ?

Page 17: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

17

Quatre piliers de la théoriede l’apprentissage

3 Contrôle de la capacité de généralisationComment contrôler efficacement la généralisation à partirde l’information contenue dans un ensemble d’apprentissage de taille finie ?

4 Construire des algorithmes d’apprentissageExiste-t-il une stratégie pour construire des algorithmesqui garantissent, mesurent et contrôlent la capacité de généralisation de modèles d’apprentissage ?

Page 18: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

18

La VC dimension

Dimension de Vapnik-Cervonenkis: une mesure dupouvoir séparateur (complexité) d’une famille de fonctionsVC dimension : un nombre entier attaché à unefamille F de fonctionsChaque f de F – c’est-à-dire, pour un w donné –peut-être utilisé pour de la classification :

f (X,w) >= 0 : X classé en 1f (X,w) < 0 : X classé en -1

( , ) : pf X w →

Page 19: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

19

VC dimension suite

Pour un échantillon de n points (x1, .. , xn) de R p Il existe 2n manières différentes de séparer cet échantillon en deux sous-échantillonsUn ensemble F de fonctions f(X,w) “hache” (shatters) l’échantillon si les 2n séparationspeuvent être faites par des f(X,w) différentesde la famille F

Page 20: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

20

Aucune ligne droite ne peut séparer les points noirs des points roses

Exemple

En 2-D, les fonctions linéaires (droites) peuvent “hacher” 3 points, mais pas 4

Page 21: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

21

Un ensemble de fonctions de R p -> R a la dimension h si :

Il existe un jeu de h points de R p qui peutêtre “haché”, quel que soit l’étiquetage des pointsAucun ensemble de h+1 points ne peut êtrehaché par cet ensemble de fonctions.

Page 22: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

22

Quelques exemples

La VC dimension de l’ensemble des hyperplans de R p est p+1

Hyper-rectangles de R p parallèles aux axesh=2p

(V.Cherkassky, F.Mulier, 1998)

Sphères de R p

h=p+1

Page 23: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

23

Mais les VC dimensions ne sont PAS égales au nombre de paramètres libres

La VC dimension de l’ensemble de fonctionsf(x,w) = sign (sin (w.x) ),c < x < 1, c>0,

avec un paramètre libre w est infinie.

Hastie et al. 2001

Page 24: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

24

Deux cas importants:a) régression ridge

La VC dimension de l’ensemble des indicatrices linéaires

satisfaisant à la condition :

dépend de C et peut prendre toute valeur de 0 à p+1.

( )( )1( , ) 1p

i iif X sign w x

X R=

= +

∑w

2 21

1pii

W wC=

= ≤∑

2

2min ; 1Rh ent pC

⎡ ⎤⎛ ⎞≤ +⎢ ⎥⎜ ⎟

⎝ ⎠⎣ ⎦

Page 25: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

25

b) L’hyperplan de marge maximale

Même résultat:

2

2min ; 1Rh ent pC

⎡ ⎤⎛ ⎞≤ +⎢ ⎥⎜ ⎟

⎝ ⎠⎣ ⎦

Page 26: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

26

Théorème de Vapnik :

Q : Quelles sont les conditions nécessaires et suffisantes pour assurer la consistence ?R : Le processus d’apprentissage est consistent si et seulement si la famille de modèles a une VC dimension finie hLa VC dimension finie ne garantit pas seulement la généralisation, mais c’est LA SEULE MANIERE qui permet à la généralisation de se produire.

Page 27: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

27

Vitesse de convergence

Taille de l’ens. d’apprentissage: n

IntervalleErreur en généralisation

Erreur d’apprentissage

% erreur

Page 28: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

28

Vitesse de convergence (2)

Q : Quelle est la différence entre les erreursd’apprentissage et de test pour une tailledonnée de l’ensemble d’apprentissage ? R : La différence entre les erreursd’apprentissage et de test dépend du rapport entre la VC dimension, h, et la taille de l’ensemble d’apprentissage, n.

Page 29: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

29

Inégalité de Vapnik

Avec la probabilité 1- α :

ne fait pas intervenir p mais la VC dimension hNe fait pas intervenir la distribution de probabilité P

( )( )emp

ln 2 1 ln ( 4)h n hR R

nα+ −

< +

Page 30: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

30

n fixé

Page 31: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

31

De Guillaume d’Ockham àVapnik

wikipedia

Guillaume d’Occam (1285 - 3 avril 1349), dit le « docteur invincible » franciscain philosophe logicien et théologien scolastique.Etudes à Oxford, puis Paris. Enseigne quelques années à Oxford. Accusé d'hérésie, convoqué pour s’expliquer à Avignon, excommunié , se réfugie à Munich, à la cour de Louis de Bavière, lui-même excommunié. Meurt de l'épidémie de peste noire.A inspiré le personnage du moine franciscain Guillaume de Baskerville dans le « Nom de la rose » d'Umberto Eco. Premier jour, vêpres : « il ne faut pas multiplier les explications et les causes sans qu'on en ait une stricte nécessité. »

Page 32: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

32

Le rasoir d’Ockham ou principe de parcimonie

Principe de raisonnement attribué à Ockham : « Les multiples ne doivent pas être utilisés sans nécessité » (pluralitas non est ponenda sine necessitate).

Rasoir d'Ockham et science moderne

Le rasoir d'Ockham n'est malheureusement pas un outil très incisif, car il ne donne pas de principe opératoire clair pour distinguer entre les hypothèses en fonction de leur complexité : ce n'est que dans le cas où deux hypothèses ont la même vraisemblance qu'on favorisera l'hypothèse la plus simple (ou parcimonieuse). Il s'agit en fait d'une application directe du théorème de Bayes où l'hypothèse la plus simple a reçu la probabilité a priori la plus forte. Des avatars modernes du rasoir sont les mesures d'information du type AIC, BIC où des mesures de pénalité de la complexité sont introduites dans la log-vraisemblance.

wikipedia

Page 33: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

33

Choix de modèles par vraisemblance pénalisée

Comparer des modèles ayant des nombres de paramètres différents: K nombre de paramètres àestimer.Critère d’Akaike :

AIC = -2 ln(L) + 2K

Critère de Schwartz :BIC = -2 ln(L) + K ln(n)

On préférera le modèle pour lequel ces critères ont la valeur la plus faible.

Page 34: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

34

En régression multiple

2ln( ) 2( 1) ln( ) 2( 1) (ln 1)

2 ln( ) ln( )( 1) ln( ) ln( )( 1) (ln 1)

SSEAIC L k n k nn

SSEBIC L n k n n k nn

π

π

= − + + = + + + +

= − + + = + + + +

SSE= somme des carrés des résidus du modèle à k variables

Page 35: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

35

Obs NOM CYL PUIS LON LAR POIDS VITESSE NAT FINITION PRIX

1 ALFASUD-TI-1350 1350 79 393 161 870 165 I B 305702 AUDI-100-L 1588 85 468 177 1110 160 D TB 399903 SIMCA-1307-GLS 1294 68 424 168 1050 152 F M 296004 CITROEN-GS-CLUB 1222 59 412 161 930 151 F M 282505 FIAT-132-1600GLS 1585 98 439 164 1105 165 I B 349006 LANCIA-BETA-1300 1297 82 429 169 1080 160 I TB 354807 PEUGEOT-504 1796 79 449 169 1160 154 F B 323008 RENAULT-16-TL 1565 55 424 163 1010 140 F B 320009 RENAULT-30-TS 2664 128 452 173 1320 180 F TB 4770010 TOYOTA-COROLLA 1166 55 399 157 815 140 J M 2654011 ALFETTA-1.66 1570 109 428 162 1060 175 I TB 4239512 PRINCESS-1800-HL 1798 82 445 172 1160 158 GB B 3399013 DATSUN-200L 1998 115 469 169 1370 160 J TB 4398014 TAUNUS-2000-GL 1993 98 438 170 1080 167 D B 3501015 RANCHO 1442 80 431 166 1129 144 F TB 3945016 MAZDA-9295 1769 83 440 165 1095 165 J M 2790017 OPEL-REKORD-L 1979 100 459 173 1120 173 D B 3270018 LADA-1300 1294 68 404 161 955 140 U M 22100

Un exemple

Page 36: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

36

Analysis of Variance

Sum of Mean Valeur Source DDL Squares Square F Pr > F

Model 6 520591932 86765322 4.47 0.0156 Error 11 213563858 19414896 Corrected Total 17 734155790

Root MSE 4406.23379 R-Square 0.7091 Dependent Mean 34159 Adj R-Sq 0.5504 Coeff Var 12.89934

Parameter Estimates

Parameter Standard Variance Variable DDL Estimate Error t Value Pr > |t| Inflation

Intercept 1 -8239.36268 42718 -0.19 0.8506 0 CYL 1 -3.50518 5.55060 -0.63 0.5406 3.77201 PUIS 1 282.16880 174.88297 1.61 0.1349 11.11882 LON 1 -15.03766 129.74749 -0.12 0.9098 7.20420 LAR 1 208.69377 412.04788 0.51 0.6225 4.19760 POIDS 1 12.57468 24.62219 0.51 0.6197 9.95728 VITESSE 1 -111.11355 222.25657 -0.50 0.6270 6.37511

Résultats

Page 37: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

37

Adjusted R-Square Selection MethodNombre dans R carréle modèle ajusté R-carré AIC BIC Variables du modèle

2 0.6366 0.6820 285.0800 289.8602 PUIS POIDS3 0.6241 0.6946 286.3954 292.6816 CYL PUIS POIDS3 0.6196 0.6909 286.5979 292.7777 PUIS LAR VITESSE3 0.6169 0.6888 286.7168 292.8340 PUIS POIDS VITESSE3 0.6156 0.6877 286.7743 292.8612 PUIS LON VITESSE1 0.6137 0.6379 285.2916 288.5249 PUIS2 0.6136 0.6619 286.1222 290.5380 PUIS VITESSE2 0.6128 0.6612 286.1601 290.5624 PUIS LON3 0.6098 0.6829 287.0320 292.9829 PUIS LAR POIDS3 0.6089 0.6823 287.0683 293.0000 PUIS LON POIDS2 0.6077 0.6567 286.3822 290.7054 PUIS LAR4 0.5968 0.6976 288.2281 295.9091 CYL PUIS POIDS VITESSE4 0.5967 0.6975 288.2312 295.9099 CYL PUIS LAR POIDS4 0.5952 0.6964 288.2918 295.9270 CYL PUIS LAR VITESSE4 0.5940 0.6955 288.3449 295.9420 PUIS LAR POIDS VITESSE4 0.5938 0.6953 288.3533 295.9443 CYL PUIS LON POIDS4 0.5902 0.6926 288.5046 295.9871 PUIS LON LAR VITESSE3 0.5897 0.6666 287.8850 293.3848 CYL PUIS LON4 0.5894 0.6920 288.5366 295.9962 CYL PUIS LON VITESSE4 0.5894 0.6920 288.5377 295.9965 PUIS LON POIDS VITESSE2 0.5864 0.6381 287.2815 291.2802 CYL PUIS3 0.5839 0.6620 288.1210 293.4958 CYL PUIS VITESSE3 0.5839 0.6619 288.1216 293.4961 CYL PUIS LAR3 0.5839 0.6619 288.1230 293.4968 PUIS LON LAR4 0.5773 0.6830 289.0285 296.1362 PUIS LON LAR POIDS2 0.5761 0.6291 287.6967 291.5440 POIDS VITESSE5 0.5721 0.7058 289.7570 299.1768 CYL PUIS LAR POIDS VITESSE5 0.5648 0.7008 290.0464 299.2005 CYL PUIS LON POIDS VITESSE5 0.5619 0.6988 290.1594 299.2101 CYL PUIS LON LAR VITESSE5 0.5603 0.6977 290.2213 299.2155 CYL PUIS LON LAR POIDS

proc reg;title Regression OLS;id nom;model prix=cyl puis lon lar poids vitesse/AIC BIC ADJRSQ selection=ADJRSQUARE ;run;

Page 38: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

38

Nombre dans R carréle modèle ajusté R-carré AIC BIC Variables du modèle

1 0.5586 0.5862 287.5579 290.3050 POIDS4 0.5577 0.6683 289.8011 296.3600 CYL PUIS LON LAR5 0.5572 0.6956 290.3398 299.2259 PUIS LON LAR POIDS VITESSE3 0.5502 0.6346 289.4448 294.1209 CYL POIDS VITESSE3 0.5455 0.6307 289.6222 294.2052 LAR POIDS VITESSE3 0.5450 0.6303 289.6429 294.2151 LON POIDS VITESSE6 0.5293 0.7058 291.7567 302.5767 CYL PUIS LON LAR POIDS VITESSE2 0.5290 0.5879 289.4883 292.6779 CYL POIDS2 0.5278 0.5869 289.5308 292.7048 LON POIDS2 0.5272 0.5863 289.5553 292.7203 LAR POIDS4 0.5146 0.6360 291.3804 296.8377 CYL LAR POIDS VITESSE4 0.5146 0.6359 291.3821 296.8382 CYL LON POIDS VITESSE4 0.5078 0.6308 291.6176 296.9123 LON LAR POIDS VITESSE3 0.4933 0.5883 291.4700 295.0959 CYL LON POIDS3 0.4928 0.5879 291.4882 295.1048 CYL LAR POIDS3 0.4917 0.5870 291.5235 295.1221 LON LAR POIDS 5 0.4709 0.6362 293.3685 299.5832 CYL LON LAR POIDS VITESSE4 0.4515 0.5886 293.4578 297.5212 CYL LON LAR POIDS2 0.4341 0.5048 292.6099 294.6691 LON VITESSE2 0.4166 0.4896 293.1266 295.0038 CYL LON3 0.4074 0.5185 294.1329 296.4390 CYL LON VITESSE1 0.3979 0.4355 292.8372 294.3548 LON3 0.3947 0.5082 294.4956 296.6288 LON LAR VITESSE3 0.3758 0.4928 295.0167 296.9045 CYL LON LAR2 0.3732 0.4516 294.3463 295.8018 CYL VITESSE4 0.3629 0.5222 296.0034 298.4649 CYL LON LAR VITESSE2 0.3576 0.4379 294.7664 296.0795 LON LAR1 0.3566 0.3969 293.9634 295.2214 CYL2 0.3543 0.4350 294.8529 296.1369 LAR VITESSE3 0.3523 0.4737 295.6452 297.2421 CYL LAR VITESSE2 0.3511 0.4322 294.9357 296.1919 CYL LAR1 0.3330 0.3747 294.5769 295.6955 VITESSE1 0.2380 0.2856 296.8401 297.4603 LAR

Page 39: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

39

AIC et BIC ne sont semblables qu’en apparenceThéories différentes

AIC : approximation de la divergence de Kullback-Leibler entre la vraie distribution f et le meilleur choix dans une famille paramétrée

Asymptotiquement:

( )( ; ) ( ) ln (ln( ( )) (ln( ( ))( ) f f

f tI f g f t dt E f t E g tg t

= = −∫

ˆˆ ˆ(ln( ( ; )) ln( ( ))fE E g t L k

θθ θ −∼

Page 40: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

40

BIC : choix bayesien de modèlesm modèles Mi paramétrés par θi de probabilités a priori P(Mi) égales.

Distribution a priori de θi pour chaque modèle P(θi / Mi).Distribution a posteriori du modèle sachant les données ou vraisemblance

intégrée P(Mi/x)Choix du modèle le plus probable a posteriori revient à maximiser

ˆln( ( / ) ln( ( / , )) ln( )2i i ikP M P M nθ −x x∼

0.5

0.5

1

( / )i

j

BIC

i mBIC

j

eP Me

=

=

∑x

Page 41: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

41

Comparaison AIC BIC

Si n tend vers l’infini la probabilité que le BIC choisisse le vrai modèle tend vers 1, ce qui est faux pour l’AIC. AIC va choisir le modèle qui maximisera la vraisemblance de futures données et réalisera le meilleur compromis biais-varianceL’AIC est un critère prédictif tandis que le BIC est un critère explicatif. Pour n fini: résultats contradictoires. BIC ne choisit pas toujours le vrai modèle: il a tendance à choisir des modèles trop simples en raison de sa plus forte pénalisation

Page 42: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

42

AIC BIC réalistes?

Vraisemblance pas toujours calculable.Nombre de paramétres non plus: ridge, PLS etc. « Vrai » modèle?

« tous les modèles sont faux ; certains sont utiles » G.Box

Vapnik: choisir selon la VC dimension

Page 43: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

43

De Guillaume d’Ockham àVapnik

Si deux familles de modèles expliquent les donnéesavec une qualité égale, alors la famille qui a la plus faible VC dimension doit être préférée.

1re découverte: La VC (Vapnik-Chervonenkis) dimension mesure lacomplexité d’une famille de modèles.

Page 44: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

44

De Guillaume d’Ockham à Vapnik

Si deux modèles expliquent les données avec une qualité égale, alors celui qui provient d’une famille à plus faible VC dimension a une meilleure performance en généralisation.

2ème découverte: La VC dimension peut être reliée à des résultats degénéralisation (résultats sur de nouvelles données).

Page 45: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

45

De Guillaume d’Ockham à Vapnik

Pour construire le meilleur modèle à partir de données, il faut tenter d’optimiser à la fois sa performance surl’ensemble d’apprentissage,et sa performance de généralisation tirée de la VC dimension : pour ce faire, il faut parcourir une suite de familles d’applications pour y construire ce modèle

3ème découverte: Au lieu d’observer des différences entre desmodèles, mieux vaut les contrôler..

Page 46: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

46

Contrôle de la Capacité de Généralisation

Risque = Risque d’Apprentissage + Intervalle de ConfianceMinimiser la seule erreur d’apprentissage nedonnera pas une espérance d’erreur faible(une bonne généralisation)

minimiser la somme de l’erreurd’apprentissage et de l’intervalle de confiance.

( )( )emp

ln 2 1 ln ( 4)h n hR R

nα+ −

< +

Page 47: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

47

Principe de minimisation structurée durisque (SRM) (1)

lorsque n/h est faible (h trop grand), le deuxième terme est grandL’idée générale du SRM est de minimiser la somme des deux termes à la droite de l’inéquation.

( )( )L

qhLhwEwR ln12ln)()( −++<

( )( )emp

ln 2 1 ln( / 4)h n hR R

nα+ −

< +

Page 48: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

48

Principe de minimisation structurée durisque (SRM)(2)

Considérons une structure S1 ⊂ S2 ⊂ .. ⊂ SL surl’ensemble des fonctions vérifiant la propriété

h1 < h2 < .. < hL

Pour chaque élément Si de la structure, l’inégalité est valide

( )( )emp

ln 2 1 ln( / 4)i ih n hR R

nα+ −

< +

SRM : Trouver i tel que la somme devienne minimale,

Page 49: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

49

Avec/sans l’approche SRM de Vapnik

Sans le SRM:Hypothèses sur la distribution statistique (inconnue) des donnéesUn grand nombre de dimensions signifie un modèle à grand nombre de paramètres, ce qui pose des problèmes de généralisationModéliser revient à chercher le meilleur ajustement

Avec le SRM:On étudie la famille de modèles, contrôlant sa VC dimension hLe nombre de paramètres peut être très grand, car on contrôle par définition la généralisationModéliser c’est rechercher le meilleur compromis entre ajustement et robustesse

Page 50: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

50

Borne supérieure trop grande,mais:

Théorème (Devroye, Vapnik) :Pour toute distribution le SRM fournit la meilleure

solution possible avec probabilité 1

(universally strongly consistent)

Page 51: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

51

Contrôle de h

h doit être fini h/n doit être petit: si n augmente, on peut augmenter la complexité du modèle (opposé de BIC)h décroit avec:

Réduction de dimension (cf. Disqual)La marge (SVM)k en régression ridge

Mais h difficile à obtenir

Page 52: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

52

Les 3 échantillons:Apprentissage: pour estimer les paramètres des modèlesTest : pour choisir le meilleur modèleValidation : pour estimer la performance sur des données futures

Rééchantillonner: validation croisée, bootstrap

Modèle final: avec toutes les données disponibles

Page 53: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

53

Page 54: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

54

Principes d’induction

Ne pas chercher à résoudre un problème plus général que nécessaire

Ne pas estimer une densité si on veut estimer une fonctionNe pas estimer une fonction si on veut seulement estimer une valeur en un point

Page 55: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

55

Sur le rôle des modèles

Modèles pour comprendre ou modèles pour prédire?La modélisation statistique a pour but de:

Fournir une compréhension des données et de leur mécanisme générateur à travers une représentation parcimonieuse. Nécessite la collaboration d’un expert du domaine. Prédire de nouvelles observations avec une précision élevée

Page 56: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

56

Comprendre vs Prédire ne se confond pas avec la distinction supervisé vs non-supervisé

« Comprendre » signifie soit un modèle parametrique de distribution d’un vecteur aléatoire soit un modèle prédictif de type régression y= f(x;θ)+εUn modèle doit être simple, ses paramétres

interpretables pour les experts du domaine : elasticité, odds-ratio, etc. • D’où la préference pour la régression logistique sur

l’analyse discriminante.

Page 57: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

57

Paradoxe 1Un « bon » modèle statistique doit aider à la compréhension mais ne donne pas forcément de bonnes prévisions au niveau individuel. En épidémiologie: facteurs de risques mais pas de pronostic individuel

Paradoxe 2On peut prédire sans comprendre: CRM, scoring.

Une théorie du consommateur ou de l’emprunteur est illusoire et inutile: un bon score suffit

Page 58: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

58

Deux conceptions très différentes sous le même nom de « modèle »: modèles de données ≠ modèles pour prédireEn Data mining les modèles ne sont que des algorithmes, eventuellement des boites noires dont la qualité se mesure par la performance pour prédire de nouvelles observations.

Page 59: Introduction à la théorie de l’apprentissage statistiquecedric.cnam.fr/~saporta/apprentissage_mai2012.pdf1 Introduction à la théorie de l’apprentissage statistique Gilbert

59

Les modèles pour comprendre correspondent à la partie de la statistique considérée comme auxiliaire de la science. Les modèles pour prédire relèvent de la statistique comme méthodologie d’aide à la décision.Doit-on opposer science et action ? Une technique qui prédit bien améliore notre connaissance. La modélisation prédictive fait partie de l’empirisme(une théorie de la connaissance à ne pas confondre avec le pragmatisme).