Machine Deep Learning

y1

x1

17

L’apprentissage supervisé : un exemple L’arbre de décision – Données Iris

Attribute Information: 1. sepal length in cm 2. sepal width in cm 3. petal length in cm 4. petal width in cm 5. class: -- Iris Setosa -- Iris Versicolour -- Iris Virginica

Extrait de la base d’apprentissage

5.1,3.5,1.4,0.2,Iris-setosa 4.9,3.0,1.4,0.2,Iris-setosa 4.7,3.2,1.3,0.2,Iris-setosa 4.6,3.1,1.5,0.2,Iris-setosa 6.4,3.2,4.5,1.5,Iris-versicolor 6.9,3.1,4.9,1.5,Iris-versicolor 5.5,2.3,4.0,1.3,Iris-versicolor 6.5,2.8,4.6,1.5,Iris-versicolor 6.8,3.2,5.9,2.3,Iris-virginica 6.7,3.3,5.7,2.5,Iris-virginica 6.7,3.0,5.2,2.3,Iris-virginica 6.3,2.5,5.0,1.9,Iris-virginica

18

9

Machine Deep Learning

M2-MP2L

L’apprentissage supervisé : un exemple L’arbre de décision

 La phase d’apprentissage : construction de l’arbre de décision (cette approche sera vue plus loin dans le cours)

Petal.Le

19

20

L’apprentissage supervisé : un exemple L’arbre de décision

 La phase de reconnaissance : prédiction de l’espèce d’une nouvelle fleur d’Iris I1 à partir de sa description

I1 Petal.Le

I1 sepal length : 5.9 sepal width: 3.5 petal length: 5.8 petal width: 1.8

La classe prédite est setosa

10

Machine Deep Learning

M2-MP2L

L’apprentissage supervisé

Population P

• Xi variables prédictives : les attributs • y variable à prédire : la classe

Population P

W W

’

y

Avec nos exemples ?

• Prix des appartements • Iris

y(p ) Ensemble des classes C

c( p )=(X1(p ),..., Xp(p )) Espace de Représentation R

f ? (fonction de classement

ou classifieur)

[Zighed et al. 92]

21

L’apprentissage supervisé : ex. Iris de Fisher Population P

X1= sepal length, D1= [4.3, 7.9] X2= sepal width, D2= [2.0, 4.4 ] X3= petal length, D3= [1.0, 6.9 ] X4= petal width, D4= [0.1, 2.5]

: des iris

• Xi variables prédictives : 4 attributs • y variable à prédire : la classe (3 espèces d’Iris)

p

Population P des iris

:

y

y(p ) C = {Setosa,

c( p )=(X1(p ),..., X4(p )) Espace de Représentation R = D1xD2xD3xD4

f ? (fonction de classement

ou classifieur)

Versicolour, Virginica}

22

11

c p c Machine Deep Learning

M2-MP2L

L’apprentissage supervisé

 Si y est une fonction continue

Régression Estimation de densité

 Si y est une fonction discrète

Classement / discrimination (en anglais on parle de classification !)

 Si y est une fonction binaire (booléenne)

Apprentissage de concepts

23

24

L’apprentissage supervisé : Exemples de méthodes

 k plus proches voisins [Cover et al. 67] [Aha et al.91]

 Réseaux de neurones [Dreyfus et al.,02]

 Séparateurs à Vastes Marges (SVM) [Vapnik, 95]

 Arbres de décisions [Breiman et al. 84] [Quinlan 86, 93]

 Espace des versions [Mitchell, 82]

 Approches probabilistes [Saporta 2006][Cornuejols et al. 2018]

 Analyse discriminante [Saporta 2006]

 Systèmes d’Inférence Floue [Ishibuchi et al.92]

 …

12

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé

25

L’apprentissage non supervisé

 On dispose d’un ensemble de données ou d’observations {O1, O2, …, Om} (contrairement au cas de l’apprentissage supervisé, les données ne sont pas étiquetées par une classe).

 Objectif :

Comme seules les observations {O1, O2, …, Om} sont disponibles, on cherche des régularités sous-jacentes.

 En extraire des sous-ensembles homogènes  Décrire comment les données sont organisées  Trouver des relations entre les données

26

13

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé

On distingue essentiellement deux familles d’approches :

 Classification automatique

 Clustering

 Classification hiérarchique

 Découverte automatique

27

L’apprentissage non supervisé

 L’univers numérique

 En 2007 : ~ 281 exaoctets (281 milliards de

gigaoctets = 2,81.1020)

 En 2011 : ~3.1021 En 2019 : ~ 50 zettaoctets Surtout des images et des vidéos

Comment organiser cette masse énorme de données ?

28

14

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé Classification automatique

 Organiser un ensemble de « formes » en

groupes contrastés

 Comprimer les données en y découvrant une

structure

Afin

de « comprendre » les données

[Cornuejols et al. 2018]

29

L’apprentissage non supervisé Classification / Clustering

On dispose d’une masse de données indifférenciées, et l’on désire savoir si elles possèdent une quelconque structure de groupes.

 Regrouper en classes des objets en se basant

sur des similarités entre eux.

 Maximiser la similarité intra-classes et minimiser la similarité inter-classes

30

15

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé Classification / Clustering

Masse de données indifférenciées

Résultat du clustering : 3 clusters (ou classes) détectés

L’apprentissage non supervisé Classification hiérarchique

La classification hiérarchique consiste à fournir un ensemble de partitions des données d’apprentissage en classes de moins en moins fines obtenues par regroupements successifs de parties.

31

32

16

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé

Extrait de la classification taxinomique de Linné

Embranchements

Classe

Ordre

Famille

...

...

...

Genre

Espèces

...

...

...

...

...

...

...

...

33

L’apprentissage non supervisé

La découverte automatique

 Trouver les lois les plus simples possibles pour expliquer des phénomènes naturels ou des invariants dans les bases de données.

 Découvrir de nouvelles relations dans les données.

 Exemple : Un pg de découverte automatique pourrait retrouver la loi d’Ohm (U = RI) à partir de mesures sur l’intensité du courant, la valeur de la résistance électrique et la tension. Mieux il pourrait établir des lois inconnues ou mal connues en fouillant de grosses bases de données.

34

17

Machine Deep Learning

M2-MP2L

L’apprentissage non supervisé Les règles d’association

 Consiste à déterminer les valeurs qui sont

associées.

 Exemple type : détermination des articles qui se

retrouvent ensemble sur un même ticket de supermarché

 Intéressant pour identifier des opportunités

de vente croisée et concevoir des groupements attractifs de produit.

 Nécessite de très grands jeux de données

35

Méthodes d’apprentissage non supervisé  Seules les observations sont disponibles, on cherche

des régularités sous-jacentes :

 Sous forme d’une fonction : régression

 Sous forme de nuages de points : clustering

(e.g. K-means)

 Sous forme d’une classification hiérarchique

(Clustering Hierarchique Ascendant (AHC), Clustering Descendant (e.g.Cobweb [Doug Fisher,1987])

 Sous forme d’une base de règles (e.g. extraction de

règles, algorithme A Priori)

 …

[Cornuéjols et al. 2018] [Saporta 90]

36

18

Machine Deep Learning

M2-MP2L

L’apprentissage semi-supervisé

37

Apprentissage semi-supervisé

 Parmi les observations {x1, x2, …, xm} seulement

un petit nombre d’entre elles ont un label yi

 L’objectif est le même que pour l’apprentissage

supervisé mais on aimerait tirer profit des observations non labellisées.

 Exemple : pour la discrimination de pages Web, le nombre d’exemples peut être très grand mais leur associer un label est coûteux.

38

19

Machine Deep Learning

M2-MP2L

L’apprentissage par renforcement

39

Apprentissage par renforcement

 Etant donnés : un agent, un environnement dans lequel certaines actions induisent des récompenses,

 L’apprentissage par renforcement c’est

l’ensemble des méthodes et algorithmes permettant à un agent d’apprendre à se comporter dans un environnement, afin d’obtenir le plus de récompenses possible sur le long terme.

40

20

Machine Deep Learning

M2-MP2L

Apprentissage par renforcement

Les données d’apprentissage  Une séquence de perceptions, d’actions et de récompenses :

(st, at, rt)t = 1, ¥  Avec un renforcement rt  rt peut sanctionner des

actions très antérieures à t

Environnement

Perception (état)

Récompense

Action

Le problème : inférer une application : situation perçue

action

afin de maximiser un gain sur le long terme

[Sutton et al. 98] [Cornuéjols et al. 03 ; www.lri.fr/~antoine/]

41

Apprentissage par renforcement

 Difficile pour deux raisons principales  signaux de renforcement pauvres  délai séparant le signal de renforcement des

décisions qui y ont conduit

 environnement incertain et inconnu

42

21

Machine Deep Learning

M2-MP2L

Apprentissage par renforcement  Applications

 commande des systèmes,  robotique,  informatique,  des actions quotidiennes dans la vie,  jeux,  ...

Agent

Environnement

Récompense à lg terme

Robot aspirateur

Appartement

Degré de propreté à la fin

Agent négociant

Ens. d’agents acheteurs/vendeurs

Gain obtenu

Prog. de jeu d’échec

Échiquier+autre joueur

Gain de la partie

Routeurs

Réseau informatique

Nb de paquets acheminés

Evaluation de l’apprentissage

43

44

22

Machine Deep Learning

M2-MP2L

Evaluation

 Objectif : évaluer et valider le résultat de

l’apprentissage.

 La validation dépend de la nature de la tâche

et du problème considéré.

 Deux modes de validation :

 Statistique

 Par expertise

45

Validation

 Objectif de la validation statistique :

obtenir des informations qui permettront de juger le résultat obtenu, ou d'estimer la qualité ou les biais des données d’apprentissage.

 Utilise des échantillons de test

 Utilise des mesures d’évaluation du résultat

(performance, qualité, …)

46

23

Machine Deep Learning

M2-MP2L

Validation

 Le critère de succès dépend à la fois du domaine

étudié et de l’objectif de l’apprentissage

 Pour certains domaines d'application (le

diagnostic médical, par exemple), il est essentiel que le modèle produit soit compréhensible. Il y a donc une première validation du modèle produit par l'expert, celle-ci peut être complétée par une validation statistique sur des bases de cas existantes.

47

Apprentissage non supervisé

 Validation essentiellement du ressort de l'expert.

 Ex. Clustering : l’algorithme de clustering construit des

groupes homogènes

 Le niveau d’homogénéité peut être estimé par la

similarité inter-classes et intra-classes

 Mais seul un expert peut juger de la pertinence des

groupes constitués.

 Ex. Règles d’associations : des mesures permettent d’estimer la qualité des règles. L'expert du domaine jugera de leur pertinence : l'algorithme fournit des règles porteuses d'information, mais peut également produire des règles triviales et sans intérêt.

48

24

Machine Deep Learning

M2-MP2L

Apprentissage supervisé

Quel critère de performance ?

 La base d’apprentissage est un échantillon de m

exemples de classes connue

W ={(xi,yi)}1..m

 Chaque exemple xi comporte p attributs : (Xi

1,…, Xi

p)

xi: iième exemple (ou instance, vecteur) yi: iième étiquette (ou attribut de décision, classe)

 But : trouver le modèle ou fonction de classement f(x)

qui soit le plus proche de y

49

Apprentissage supervisé Quel critère de performance ?

On cherche une fonction de classement f qui minimise un critère…

 Critère naïf : minimiser l’erreur empirique

err

emp

=

1 m

m



= 1

i

(

xf (

i

)

i

)

y

m : nombre d’exemples d’apprentissage

Une fois le modèle f construit, on l’utilise pour prédire la classe des exemples d’apprentissage, on compare alors la classe réelle (yi)) à la classe prédite (f(xi)).

Erreur empirique = Taux d’erreur en resubstitution

50

25

„ Machine Deep Learning

M2-MP2L

Apprentissage supervisé Quel critère de performance ?

On cherche une fonction de classement f qui minimise un critère…

 Critère idéal : mesurer l’erreur de prédiction

err pred

=

Pr[

xf )(

y

]

 Plusieurs approches pour estimer

cette probabilité

51

Apprentissage supervisé Evaluation de l’erreur de prédiction

 L’erreur de prédiction peut être estimée par l’erreur

empirique. = Pr[

err pred

xf )(

y

]

estimée par

err

emp

=

1 m

m



= 1

i

(

xf (

i

)

i

)

y

 Cette estimation est grossière : c’est un taux trop

optimiste.

 Un des objectifs de l’apprentissage étant de minimiser l’erreur, le classifieur a de fortes chances d’être meilleur sur l’échantillon d’apprentissage que sur de nouveaux exemples qui ne lui ont jamais été présentés.

 L’erreur empirique n’est pas un bon estimateur de l’erreur

de prédiction.

52

26

„ „ „ Machine Deep Learning

M2-MP2L

Apprentissage supervisé

Evaluation de l’erreur de prédiction

Schéma apprentissage-validation

 Décomposer les données en deux ensembles

disjoints :

Ensemble d'apprentissage : permet de

générer le modèle

Ensemble de test : permet d'évaluer l'erreur

réelle du modèle sur un ensemble indépendant (calcul du taux d’erreur sur l’ensemble de test)

53

Apprentissage supervisé Evaluation de l’erreur de prédiction

 Validation croisée ou cross-validation

 Méthode d’évaluation de l’erreur de prédiction

 Réponse au problème de la trop grande

dépendance vis-à-vis de l’ensemble de test

 Cette technique procède à une répétition du

schéma apprentissage/validation sur différentes fractions constituées à partir des données initiales.

54

27

Machine Deep Learning

M2-MP2L

Apprentissage supervisé Evaluation de l’erreur de prédiction

 Validation croisée ou cross-validation Taux d’erreur (schéma apprentissage validation)

e1

e2

e3 e4

Estimation du taux d’erreur réel par la moyenne :

4



ie =i 1 4

Apprentissage supervisé : sur-apprentissage

55

56

28

Machine Deep Learning

M2-MP2L

Précision vs. Généralisation

 Grand dilemme de l’apprentissage supervisé.

 Précision : écart entre une valeur mesurée

ou prédite et une valeur réelle.

 Apprendre avec trop de précision conduit à

un « sur-apprentissage ».

 Accroît le risque de modéliser le bruit et de faire

coïncider le modèle avec la base d’apprentissage  Réduit le pouvoir de prédiction d’un exemple inconnu

 Apprendre avec trop peu de précision conduit

à une « sur-généralisation »

57

Sur-apprentissage Phénomène typique lors d’un sur-apprentissage :

 Le taux de prédiction augmente sur

la base d’apprentissage

 Le taux de prédiction commence à baisser

sur les exemples inconnus

précision

Sur-apprentissage à partir de cette zone

Précision sur les données d’apprentissage

Précision sur les données inconnues

temps

58

29

Machine Deep Learning

M2-MP2L

Conclusion

Points clés pour effectuer une tâche d’apprentissage

 Avant l’apprentissage, bien choisir

 L’échantillon d’apprentissage  La représentation des données  Le type de modèle (et l’algorithme)  Le critère (nombre d’erreurs, erreur empirique...)  Autres critères : intelligibilité des résultats, coûts

 Après l’apprentissage  Interpréter le modèle  L’évaluer

59

60

30