[PDF] [PDF] Cours, Exercices et Travaux Pratiques - Enseeiht

[PDF] Synthèse de cours exercices corrigés - ACCUEIL

PEARSON Education France — Exercices d'Économétrie – 2e édition — ( Scriptex : 4e 1 1 DÉFINITION GÉNÉRALE ET NOTATION GÉNÉRALE Lorsqu'on fait l'hypothèse d'un modèle linéaire à coefficients constants reliant des pro-

[PDF] Exercices et examens résolus: Mécaniques des Systèmes de

Ce recueil d'exercices et examens résolus de mécanique des systèmes ( Source : https:// wikisource org/wiki/Les Merveilles de la science/Bateaux à vapeur)

[PDF] Synthèse de cours exercices corrigés - Cours, examens et exercices

définition, la rentabilité attendue d'un placement est égale au rapport entre le fonde son argumentation sur la rentabilité moyenne de l'ensemble des pro- jets

[PDF] Tome I ANALYSE DANS R Partie COURS 1er et - FP BENI-MELLAL

lecteur Les connaissances requises pour la lecture sont celles des pro- grammes de d'un degré de difficulté couramment rencontré dans les examens et les

[PDF] Examens corrigés Mécanique du Point Matériel - FP BENI-MELLAL

Examens corrigés Mécanique du Point Correction d'examen 1 (session ordinaire) Exercice 1: 1) 2) ρ ρe 3) Donner la définition de : a) Plan Osculateur

[PDF] Cours, Exercices et Travaux Pratiques - Enseeiht

Cours, Exercices et 9 2 Définition d'un Processus décisionnels de Markov Définition 1 On appelle Composante Principale, la coordonnée ci du point pro-

[PDF] Recueil dexercices corrigés en INFORMATIQUE I - USTO

Associez chaque concept de la liste suivante avec une des définitions proposées : c) Windows 7 Professional est plus rapide que Windows 7 Home

[PDF] Logique, ensembles, raisonnements - Exo7 - Exercices de

D'autre part la définition de f nous donne f(p) = fp(p)+1 Nous avons utiliser la definition de fn+2, puis la proposition sn, puis l'associativité de la composition,

[PDF] Statistiques descriptives et exercices

Nous nous intéressons au caractéristique des unités qui peuvent prendre différentes valeurs Définition 4 On appelle caractère (ou variable statistique, dénotée 

[PDF] MECANIQUE DES FLUIDES Cours et exercices corrigés

Ils sont extraits, pour la plupart, des examens et devoirs surveillés que j'ai proposé à l'Institut 2 Définitions Cours, exercices et problèmes corrigés Classes 

[PDF] 3eme prepa pro emploi du temps PDF Cours,Exercices ,Examens

[PDF] 3ème prépa pro lettre de motivation PDF Cours,Exercices ,Examens

[PDF] 3eme prepa pro mecanique PDF Cours,Exercices ,Examens

[PDF] 3ème prépa pro programme PDF Cours,Exercices ,Examens

[PDF] 3eme prop du ? Viètes sur un DM de math 3ème Mathématiques

[PDF] 3eme proposition dues ? Viète 3ème Mathématiques

[PDF] 3eme question d'un exo de maths sur les suites (terminale ES) 2nde Mathématiques

[PDF] 3eme republique cm2 PDF Cours,Exercices ,Examens

[PDF] 3ème république résumé PDF Cours,Exercices ,Examens

[PDF] 3eme S'il VOUS PLAIT JUST 1CALCUL A FAIREE 4ème Mathématiques

[PDF] 3ème SVT Devoir 6 CNED 3ème SVT

[PDF] 3ème Techno Devoir 5 CNED 3ème Autre

[PDF] 3eme | DM sur racine carée 3ème Mathématiques

[PDF] 3x ( 2x + 5 ) - 7 ( 2x +3x ( 2x + 5 ) - 7 ( 2x + 5 ) = ( + )( - ) 3ème Mathématiques

[PDF] 3x 2 ² PDF Cours,Exercices ,Examens

Cours, Exercices et

Travaux PratiquesVincent Charvillat

Département Informatique et

Mathématiques Appliquées

Copyright

c

2011 INPT-ENSEEIHT

Tables des matières

1 Introduction à l"apprentissage 6

1.1 Terminologie illustrée . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2 Une multitude de prédicteurs possibles . . . . . . . . . . . . . . . . .

7

1.2.1 Classifieurs binaires et quadratiques . . . . . . . . . . . . . . .

8

1.2.2 Arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3 Les trois modes d"apprentissage . . . . . . . . . . . . . . . . . . . . .

11

1.3.1 Apprentissage supervisé . . . . . . . . . . . . . . . . . . . . .

11

1.3.2 Apprentissage par renforcement . . . . . . . . . . . . . . . . .

11

1.3.3 Apprentissage non-supervisé . . . . . . . . . . . . . . . . . . .

12

1.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2 Généralisation 13

2.1 Complexité optimale d"un classifieur . . . . . . . . . . . . . . . . . .

13

2.1.1 Fonctions de perte pour la classification . . . . . . . . . . . . .

13

2.1.2 Hiérarchie de modèles de complexité croissante . . . . . . . . .

14

2.1.3 Minimisation du risque empirique . . . . . . . . . . . . . . . .

15

2.2 Risque espéré et généralisation . . . . . . . . . . . . . . . . . . . . . .

1 6

2.3 Prédiction et régression . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3.1 Fonctions de perte pour la régression . . . . . . . . . . . . . .

18

2.3.2 Hiérarchie de modèles de complexité croissante . . . . . . . . .

19

2.3.3 Minimisation du risque empirique pour la régression . . . . . .

21

2.4 Bilan autour du vrai risque : l"EPE . . . . . . . . . . . . . . . . . . .

22

3 Prétraitements 23

3.1 Analyse en Composantes Principales (ACP) . . . . . . . . . . . . . .

24

3.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.1.2 Caractéristique d"ordre 1 : tendance centrale des variables . .

24

3.1.3 Caractéristiques d"ordre 2 : dispersion et dépendance des vari-

ables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.4 Corrélation entre variables . . . . . . . . . . . . . . . . . . . .

26

3.1.5 Analyse enq= 1Composante Principale . . . . . . . . . . . .26

3.1.6 Cas général : analyse enq >1composantes principales . . . .30

3.1.7 Reconstruction du tableau des données au moyen des com-

posantes principales et des facteurs principaux . . . . . . . . . 32

3.1.8 Conclusion et propriétés de l"ACP . . . . . . . . . . . . . . . .

32

3.2 Application directe de l"ACP : les "eigenfaces» . . . . . . . . . . . . .

33
2

3.3 Analyse Factorielle Discriminante (AFD) . . . . . . . . . . . . . . . .36

3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.3.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.4 Exercice reliant classification et régression . . . . . . . . . . . . . . .

38

4 Rappels sur la régression 40

4.1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.2 Des échantillons simples à manipuler . . . . . . . . . . . . . . . . . .

41

4.3 Modèle gaussien et maximum de vraisemblance . . . . . . . . . . . .

41

4.3.1 Modèle gaussien . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.3.2 Maximum de vraisemblance . . . . . . . . . . . . . . . . . . .

43

4.4 Modèle de régression linéaire simple . . . . . . . . . . . . . . . . . . .

44

4.4.1 Modèle linéaire avec bruits gaussiens . . . . . . . . . . . . . .

44

4.4.2 Moindres carrés linéaires . . . . . . . . . . . . . . . . . . . . .

45

4.5 Bilan vis-à-vis de l"apprentissage . . . . . . . . . . . . . . . . . . . . .

46

4.6 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

5 Approximations de l"EPE 49

5.1 Estimateur empirique de l"EPE . . . . . . . . . . . . . . . . . . . . .

49

5.1.1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

5.1.2 Propriétés de l"estimateur du risque empirique . . . . . . . . .

50

5.1.3 Du bon usage du risque empirique . . . . . . . . . . . . . . . .

51

5.2 Validation croisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

5.2.1 Validation croisée, "K-fold" . . . . . . . . . . . . . . . . . . .

52

5.2.2 Validation croisée, "Leave-One-Out" . . . . . . . . . . . . . .

52

5.2.3 Variance du score de validation croisée . . . . . . . . . . . . .

53

5.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

6 Solutions de l"EPE et méthodes dérivées 54

6.1 Solution de l"EPE pour la régression . . . . . . . . . . . . . . . . . .

5 4

6.1.1 Espérance conditionnelle . . . . . . . . . . . . . . . . . . . . .

54

6.1.2 Méthode des k plus proches voisins (kppv) . . . . . . . . . . .

55

6.1.3 Fléau de Bellman ("Curse of dimensionality") . . . . . . . . .

56

6.2 Solution de l"EPE pour la classification . . . . . . . . . . . . . . . . .

57

6.2.1 Solution pour une perte générale . . . . . . . . . . . . . . . .

58

6.2.2 Solution pour une perte non-informative . . . . . . . . . . . .

58

6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

6.3.1 Solution de l"EPE pour la régression avec une perteLp. . . .59

6.3.2 Classifieur binaire optimal . . . . . . . . . . . . . . . . . . . .

60

6.3.3 Classification aux kppv . . . . . . . . . . . . . . . . . . . . . .

61

6.3.4 Classification Bayésienne . . . . . . . . . . . . . . . . . . . . .

63

7 Compromis Biais-Variance 64

7.1 Décomposition de l"EPE . . . . . . . . . . . . . . . . . . . . . . . . .

6 4

7.1.1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

7.1.2 Décompositions bruit-biais-variance . . . . . . . . . . . . . . .

65

7.1.3 Illustration pratique . . . . . . . . . . . . . . . . . . . . . . .

66
3

7.1.4 Cas du prédicteur aux kppv . . . . . . . . . . . . . . . . . . .68

7.2 Régularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

7.2.1 Splines de lissage . . . . . . . . . . . . . . . . . . . . . . . . .

69

7.2.2 Régularisation via l"estimateur MAP . . . . . . . . . . . . . .

70

7.2.3 Ridge regression . . . . . . . . . . . . . . . . . . . . . . . . . .

71

7.3 Sélection de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

7.3.1 Critère AIC d"Akaïke . . . . . . . . . . . . . . . . . . . . . . .

73

7.3.2 Autres Critères . . . . . . . . . . . . . . . . . . . . . . . . . .

74

7.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

7.4.1 Régression aux moindres carrés et Apprentissage supervisé . .

75

7.4.2 Décomposition Biais-Variance pour un modèle linéaire . . . .

75

8 Apprentissage non-supervisé 77

8.1 Problèmes usuels . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

8.1.1 Estimation de densité . . . . . . . . . . . . . . . . . . . . . . .

77

8.1.2 Réduction de dimension . . . . . . . . . . . . . . . . . . . . .

78

8.1.3 Extraction de caractéristiques . . . . . . . . . . . . . . . . . .

79

8.1.4 Classification non-supervisée . . . . . . . . . . . . . . . . . . .

79

8.1.5 Inférence semi-supervisée . . . . . . . . . . . . . . . . . . . . .

80

8.2 Méthodes declustering. . . . . . . . . . . . . . . . . . . . . . . . . .81

8.2.1 Méthode des k-moyennes. . . . . . . . . . . . . . . . . . . . .

81

8.2.2 Classification Ascendante Hiérarchique . . . . . . . . . . . . .

82

8.3 Estimation d"un mélange de lois parEM. . . . . . . . . . . . . . . .85

9 Apprentissage par renforcement 88

9.1 Décision séquentielle dans l"incertain . . . . . . . . . . . . . . . . . .

88

9.2 Définition d"un Processus décisionnels de Markov . . . . . . . . . . .

89

9.3 Résolution et Apprentissage par renforcement . . . . . . . . . . . . .

91

9.4 Exercice sur les PDM. . . . . . . . . . . . . . . . . . . . . . . . . . .

93

10 Travaux Pratiques 95

4

Avant-propos

Ce document regroupe des notes de cours, des exercices et des sujets de travaux pratiques utiles à l"unité d"enseignement intitulée "Apprentissage et Applications». Ce cours est dispensé au sein de la majeure mathématique en seconde année du dé- partement informatique et mathématiques appliquées de l"ENSEEIHT. Ce document repose naturellement sur un socle bibliographique important. Certains passages du cours sont ainsi directement inspirés des ouvrages suivants : The Elements of Statistical Learning, Trevor Hastie, Robert Tibshirani, Jerome

Friedman, second edition, Springer, 2009

Pattern Recognition and Machine Learning, Christopher M. Bishop, Springer, 2006
Pattern Classification, R. Duda, P. Hart, G. Stork, second edition, Wiley, 2001 Reinforcement Learning: An Introduction, R. Sutton and A. Barto, MIT Press, 1998
Apprentissage Artificiel, A. Cornuéjols L. Miclet, Eyrolles, 2003 Le premier ouvrage, bien qu"assez technique, est vraisemblablementlaréférence principale. Certaines figures (mises à la disposition des enseignants) sont issues de ces ouvrages. Les cours de J-Y. Tourneret , P. Besse, M. Marchand, T. Jaakkola, F. Garcia ainsi que plusieurs thèses de doctorat (C. Goutte, H. La Rochelle), m"ont également permis de reprendre et d"adapter quelques démarches que j"ai trouvées particulièrement didactiques. Enfin, les sujets de travaux pratiques doivent beau- coup aux intervenants qui m"ont récemment accompagné dans cet enseignement : P.

Parisot, J. Guenard et J.D. Durou.

5

Thème 1

Introduction à l"apprentissage

Vincent Charvillat

Septembre 2010Ce premier thème introduit le cours d"apprentissage et les premiers éléments de terminologie au travers d"applications de reconnaissance de formes. Quelques classifieurs élémentaires sont également présentés.

1.1 Terminologie illustrée

En apprentissage articificiel, on s"intéresse à desmécanismes de prédictiondans des contextes où les données manipulées sontaléatoires. Ces dernières étant vues comme des réalisations de variables aléatoires, on parlera donc aussi d"apprentissage statistique. L"exemple introductif classique est celui de la reconnaissance automatique de l"écriture manuscrite. La figure 1.1 montre des réalisations manuscrites aléatoires des chiffres. Un algorithme d"apprentissage artificiel permet de mettre au point un

mécanisme de prédiction du nombre écrit à partir d"une donnée d"entrée (par exemple

une imagette numérique de6464pixels). En d"autres mots, on veut prédire la classe d"appartenance d"une imagette quelconque (2R6464) parmi les dix classes possibles associées aux chiffresf0;1;:::;9gpossibles. Un tel problème de prédiction d"une classe d"appartenance est aussi appelé un problème declassification. Plus formellement, on considèrera pour la classification, un espace d"entréeX (R6464dans l"exemple ci-dessus) et un espace discret de sortie àkclassesY= f0;:::k1g(k= 10dans l"exemple). Unprédicteur(ouclassifieur) est une fonc- tionh:X ! Yqui prédit pour une donnée d"entréexi2 X(une imagette dans l"exemple), sa classe :byi=h(xi)2 Y.quotesdbs_dbs18.pdfusesText_24