Data Mining
CHIII: Apprentissage supervisé
Tableau de données
Statut des variables
Principes de l’apprentissage supervisé
Apprentissage Bayésien
Cas de deux classes
• Classification de deux classes: positive, négative.
Apprentissage en 2 étapes:
• Estimer la probabilité d’affectation 𝑃(𝑌/𝑋)
• Prédire 𝑌 = + 𝑠𝑖 𝑃 𝑌 = +Τ𝑋 > 𝑃(𝑌 = −Τ𝑋)
Généralisation su K classes
Théorème Bayésien
𝑃 𝑋Τ𝑌 𝑃(𝑌)
• Théorème Bayésien: 𝑃(𝑌ൗ𝑋) =
𝑃(𝑋)
Objectif:
X Y
avec:
Exemple
• P(Y/X) reflète la confiance qu’on donne pour que X soit une pomme
sachant qu’elle est rouge et arrondie=> Probabilité à postériori
Y/X
• P(Y) probabilité qu’un exemple donné soit une pomme
• P(X|Y) probabilité que X: rouge et arrondie sachant que c’est une pomme
• P(X) probabilité de l’échantillon
Exemple
• Pour faire la classification d’un nouvel échantillon ( à savoir dans
l’exemple on veut classer un nouveau fruit), que doit-on faire ??
• On calcule le P(Y/X) pour chaque classe Y
• On compare la probabilité et on affecte X à la classe ayant la plus grande
probabilité
Estimation de P(X), P(Y) et P(X/Y) => Phase d’apprentissage
Naïve Bayes Classifier
• On suppose qu’on a n Classes 𝐶1 , 𝐶2 , … , 𝐶𝑛 . Sachant un échantillon X
inconnu, Le classifieur calcule les probabilités à postériori P(𝐶𝑖 /X).
• Maximise => maximise
=> Indépendance entre les descripteurs
Les hypothèses de base pour un algorithme Bayésien:
Utilise tous les descripteurs pour faire une décision
Tous les descripteurs ont la même importance.
Tous les descripteurs sont indépendants les uns des autres.
Exercice
• On a des nouveaux mesures pour le jour,
on veut savoir si le mache va se jouer ou
non.
• Quelles sont les Y et le X dans cet
exemple?
Jeux de données pour le
matche de tennis
• On calcule 𝑃 𝑦𝑒𝑠Τ𝐸 𝑒𝑡 𝑃 𝑦𝑒𝑠Τ𝐸 où E est l’échantillon suivant:
• Les descripteurs de E sont:
o E1 avec outlook=sunny
o E2 avec temperature =cool
o E3 avec humuidity= true
o E4 avec windy=true
• Les descripteurs sont considérés comme indépendants sachant la classe
=> On peut faire la multiplication des probabilités de chacun des
descripteurs sachant la classe
=>
Pour le nouveau jour la probabilité d’avoir play = no et 4 fois plus
grande.
Problème du Naïve Bayes
• On suppose que le descripteur (outlook=sunny) est associé (play=no) et
(outlook=sunny) n’a jamais coincide avec (play = yes).
P(play = yes|outlook = sunny) = 0 et P(play = yes|outlook = sunny) =1
𝑃(𝑋1Τ𝑌𝑒𝑠)𝑃(𝑋2Τ𝑌𝑒𝑠)𝑃(𝑋3Τ𝑌𝑒𝑠)𝑃(𝑋4Τ𝑌𝑒𝑠)
P(yes|X) =
𝑃(𝑋)
P(yes|X) = 0
• Peut arriver dans certains cas d’apprentissage et donne une mauvaise
prédiction pour le nouvel échantillon.
• Solution: On utilise l’estimateur Laplacien pour calculer la probabilité
=> On ajoute 1 pour chaque numérateur et k pour le dénoménateur avec
K le nombre de descripteurs
Correction de Laplace
• Exemple sur les données après modification (P(play = yes|outlook = sunny) = 0
• La correction de Laplace ajoute 1 au numérateur et 3 au dénominateur
• On s’assure que même si le descripteur
(variable) n’est pas arrivé dans l’ensemble
d’apprentissage, il aura une faible probabilité
mais, pas nulle.
Correction de Laplace
• Correction de Laplace sur les données originaux (P(play = yes|outlook = sunny) = 0
Traitement des valeurs manquantes
• Que faire lorsqu’on a une donnée à classer avec une variable ayant
valeur manquante?
On doit omettre la variable et ne pas l’intégrer dans le calcul.
333 9
9 9 9 14 0,0238
𝑃 𝑦𝑒𝑠 𝑋 = =
𝑃 𝑋 𝑃(𝑋)
143 5
5 5 5 14 0,0343
𝑃 𝑛𝑜 𝑋 = =
𝑃 𝑋 𝑃(𝑋)
Que pensez-vous de ces résultats par rapport à ceux retrouver lorsque la
valeur de la variable outlook existe?
Les probabilités dans ce cas sont plus grandes puisqu’il y a une valeur manquante, mais les résultats
de la comparaison ne changent pas puisqu’elle ne rentre pas dans le calcul dans la probabilité à
postériori des deux classes
Traiter les variables numériques
• On veux classer l’échantillon suivant:
• Comment on peut calculer les probabilités??
P(temperature=66|yes) ?? P(temperature=66|no)??
Problème dans ce cas P(temperature=66|yes) =0
On assume que chaque variable numérique a une distribution de probabilité normal
(Suit la loi Gaussienne)
Alors la probabilité de la température prend une valeur dans une
région entre 64 et 68.
X
X X
X
X X
Donc P(yes|X) <P(no|X) alors play = no
Réseau de neurones
Réseau de neurones (NN)
• Le réseau de neurones est composé de couches de neurones
interconnectés.
• Le message passe par les connexions entre les neurones
Réseau de neurones (NN)
• Chaque connexion entre les neurones présente un poids (weight).
• L’entrée de chaque neurone provient des sorties des neurones qui lui
sont connectés.
• La sortie de chaque neurone présente son entrée et le poids de la
connexion.
Réseau de neurones (NN): Apprentissage
• Apprentissage: La procédure de modifier les poids pour effectuer une
tache donnée.
• L’apprentissage peut également se faire par le changement de
quelques connexions. => Ajout et élimination des connexions entre
les neurones.
Réseau de neurones (NN): Model
• La connexion entre deux neurones 𝑖 et 𝑗 est définie par le poids 𝑤𝑖𝑗
• 𝑤𝑖𝑗 => La force de la connexion entre les deux neurones
• Chaque neurone calcule la somme des entrées des différents
neurones pondérée par le poids de leurs connexions.
• Un poids spécial est également ajouté à cette somme pondérée.
Fonction d’activation
𝑦𝑖 = 𝑓(𝑤11 𝑥11 + ⋯ + 𝑤1𝑛 𝑥1𝑛 + 𝑏1 )
• Dans le cas de classification : une classe 1 et une classe -1:
➢La fonction la plus basique est 𝑓 𝑦𝑖 = 𝑠𝑖𝑔𝑛(𝑦𝑖 ) => Aucune idée sur le degré
de confiance
1
➢La fonction 𝑠𝑖𝑔𝑚𝑜𝑖𝑑(𝑦𝑖 ) = => traduit la sortie en probabilité
1+𝑒 −𝑦𝑖
➢La fonction Relu = max(𝑦𝑖 , 0)
Les étapes d’apprentissage du réseau de
neurones
1. Construction du réseau de neurone (nombre de neurones, nombre
de couches)
2. Apprentissage du réseau
3. « Purning » le réseau
4. Interprète le résultat
Apprentissage du réseau
• L’objectif de l’apprentissage est d’avoir des poids qui font que la
prédiction des échantillons d’apprentissage seront bien classés.
• Les étapes:
• Les poids sont fixés au début de façon aléatoire
• Les échantillons d’apprentissage sont donnés un par un.
• Calcul des fonctions d’activation des nœuds.
• Calcul du vecteur de sortie.
• Ajustement des poids suivant le calcul d’erreur (label – vecteur_obtenu).
Network Pruning
• La connexion de tous les neurones augmente le nombre de poids à
gérer.
• n neurones en entrée, h neurones dans la couche cachée et m
neurones dans la couche de sortie représente un nombre de h(n+m)
liens [poids].
Solution:
Pruning : éliminer des liens entre les neurones sans affecter la
classification.
Exemple
Base d’apprentissage
Comment on définit l’architecture du
réseau de neurones??
Un neurone pour chaque
classe
Neurones en sorties
Couche cachée
Neurones en entrées
Un neurone
Un neurone pourpour
chaque
descripteur
• FeedForward : chaque neurone reçoie en entrée les sorties des
neurones de la couche précédente => Dans le cas d’un réseau
entièrement connectée, chaque neurone sera connecté avec les
neurones de la couche précédente.
• Initialisation des poids se fait de façon aléatoire avec des valeurs
entre [-1,1]
• Modèle : somme pondérée des entrées + biais sur laquelle est
appliquée une fonction de transfert différentiable
Architecture: nombre de neurones
• Données numérique : un neurone pour chaque entrée
• Données catégorique:
• Nominal: un neurone pour chaque valeur de l’entrée (one-hot encoding)
Exemple: color ==> « red », « green », « blue »
Red Green Blue
1 0 0
0 1 0
0 0 1
• Ordinal : un neurone pour la variable et la valeur code les différents rangs
Exemple: place ➔ « first », « second », « third »
First : 1, second: 2, third :3
➢Combien de neurones doit-on avoir pour le vecteur weather ?
Exemple: vecteur1: sunny, hot, high, false => 100 100 10 10
On peut coder autrement, par exemple la variable Windy peut être représenter par un seule
neurone et prend comme valeur 0 ou 1.
Architecture: nombre de neurones
On peut coder autrement, on peut avoir un seule neurone pour coder la sortie Yes or No (1 ou 0)
Architecture: nombre de neurones
• Nombre de neurone dans la couche cachée ???
=> la réponse n’est pas évidente, il faut tester et affiner selon le
taux d’erreur obtenu
➢Un taux élever de couches et de neurones => beaucoup de poids
Overfitting
Le réseau n’arrive pas à généraliser
➢ Un taux bas de neurones => peu de poids
Underfitting
Le réseau n’arrive pas à apprendre la relation entre l’entrée et la sortie.
Idée: On peut commencer par une couche cachée avec n neurones
𝑒𝑛𝑡𝑟é𝑒𝑠𝑛𝑒𝑢𝑟𝑜𝑛𝑒 +𝑠𝑜𝑟𝑡𝑖𝑒𝑛𝑒𝑢𝑟𝑜𝑛𝑒𝑠
𝑛=
2
Apprentissage par Backpropagation
Apprentissage par backpropagation:
Pour chaque exemple d’apprentissage p:
• On calcule la sortie a et on calcule l’erreur par rapport au label d.
• On met à jour les poids du réseau pour minimiser l’erreur
Jusqu’à erreur de tous les échantillons < Seuil
• Backpropagation ?? Ajustement des poids par un retour en arrière
(des neurones de sorties vers les neurones d’entrées) en ajoutant le
changement des poids ∆𝑤
• Une fonction classique pour calculer l’erreur E est la somme au carré
de l’erreur.
• E : erreur pour un échantillon d’apprentissage
• di: la sortie désirée par le neurone i
• ai: la valeur obtenue par le neurone i
Comment peut-on calculer le changement des poids???
• On peut considérer la backpropagation comme une optimisation de la
recherche dans l’espace des poids.
• Objectif: retrouver l’ensemble des poids pour lesquels l’erreur est minimal
• Méthode de recherche : réduit l’erreur pour chaque exemple d’apprentissage.
𝜕𝐸
• Réduire la fonction d’erreur => Faire des petits pas (gradient )
𝜕𝑤
• Une fonction décroit rapidement lorsque la direction du mouvement est
dans la direction du négatif du gradient.
=> Pour ajuster les poids, on effectue des petits pas dans le sens inverse du
sens du gradient jusqu’à trouver un minimum local de la fonction de l’erreur E
• L’algorithme de « backpropagation » ajuste les poids en projetant vers
l’arrière l’erreur, d’une couche à une autre en partant de la couche de
sortie vers la couche d’entrée.
• Trois approches sont utilisées:
• Approche descente de gradient classique (batch): Les poids sont calculés
après le passage de tous les exemples d’apprentissage. Une moyenne des
gradients sur tous les échantillons d’apprentissage est effectuée pour faire la
mise à jours des poids, au bout d’une « epoch ». Plusieurs « epochs » sont
nécessaires pour améliorer les résultats. ➔ epoch ???
-> On suppose que dataset = 1000 exemples
epoch1
epoch2 Après la 1ERE epoch, on fait une mise à jour des poids
L’application de plusieurs epochs améliore les poids
epoch3
• Approche incrémentale (online) : Les poids sont ajustés après chaque
exemple d’apprentissage.
• Approche descente de gradient par lot (Mini-batch) : Les poids sont calculés
après le passage d’un ensemble des exemples d’apprentissage. Une moyenne
des gradients sur l’ensemble des échantillons du lot est effectuée pour la mise
à jour des poids.
Le traitement par lots:
➢ Améliore les problèmes de mémoire qu’on peut rencontrer dans l’approche classique. Il permet de se
contenter de charger partiellement les données en mémoire au fur et à mesure.
➢ Améliorer la convergence en réduisant le nombre de passage sur la base entière.
➢ Le plus utilisé dans les problèmes d’apprentissage
➢ Le choix de la taille de batch est purement expérimental.
Mise à jour des poids
• : Poids du neurone p vers le neurone q à l’instant t
• Mise à jour du poids
le pas de changement avec :
𝑜𝑝 𝑠𝑜𝑟𝑡𝑖𝑒 𝑑𝑒 𝑙𝑎 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛 𝑑′ 𝑎𝑐𝑡𝑖𝑣𝑎𝑡𝑖𝑜𝑛 𝑑𝑢 𝑛𝑒𝑢𝑟𝑜𝑛𝑒 𝑝 et
𝛿𝑞 (𝑒𝑟𝑟𝑒𝑢𝑟 𝑑𝑢 𝑛𝑒𝑢𝑟𝑜𝑛𝑒 𝑞)
• 𝛿 est calculé de deux façon différentes:
Mise à jour des poids
• La fonction sigmoid :
• Dérivée de la fonction sigmoid :
• Donc l’erreur de la backpropagation avec sigmoid comme fonction
d’activation
