Intelligence Artificielle

Pr. Hiba Chougrad

Année-universitaire: 2019-2020

11/03/2020 1
11/03/2020 2

Plan
1. Introduction générale et Agents Intelligents
2. Logique du premier ordre
3. Machine Learning : Pré-traitement des données
4. Machine Learning : Supervised vs Unsupervised
5. Machine Learning : Construire un bon modèle
6. Machine Learning : Raisonnement probabiliste et réseaux bayésiens
7. Machine Learning: Algorithmes d’apprentissage automatique
8. Machine Learning: Apprentissage par renforcement, vision par ordinateur,
NLP, Deep Learning
11/03/2020 3

Plan
1. Introduction générale et Agents Intelligents
2. Logique du premier ordre
3. Machine Learning : Pré-traitement des données
4. Machine Learning : Supervised vs Unsupervised
5. Machine Learning : Construire un bon modèle
6. Machine Learning : Raisonnement probabiliste et réseaux bayésiens
7. Machine Learning: Algorithmes d’apprentissage automatique
8. Machine Learning: Apprentissage par renforcement, vision par ordinateur,
NLP, Deep Learning
11/03/2020 4

Machine Learning :
Algorithmes d’apprentissage automatique
11/03/2020 5

Arbres de décision
11/03/2020 6

Arbre de décision
• A set of training examples is broken down into smaller and smaller subsets
while at the same time an associated decision tree is incrementally developed.
• At the end of the learning process, a decision tree covering the training set is
returned. [Mitchell, 1997]

• Un ensemble de données d'entrainement (Training set) est divisé en sous-ensembles de plus

en plus petits, tandis qu'un arbre de décision associé est développé en même temps.
• À la fin du processus d'apprentissage, un arbre de décision couvrant l'ensemble des données
d'apprentissage (Training set) est renvoyé.
11/03/2020 7

Arbre de décision
L'arbre de décision construit des modèles de classification ou de régression en
forme d'une structure d'arbre.

Il décompose une dataset en sous-ensembles de plus en plus petits et développe en

même temps incrémentalement un arbre de décision associé.
11/03/2020 8

Arbre de décision
• Le résultat final est un arbre avec deux sortes de noeuds "Decision nodes"
et "Leaf nodes":
Decision node (ex., Outlook) peut avoir deux branches ou plus (ex. Sunny, Overcast et
Rainy)
Leaf node (ex., Play) représente une classification ou une décision

• Le nœud de décision le plus haut dans un arbre correspond au meilleur

prédicteur et est appelé "Root node"
11/03/2020 9

Arbre de décision
11/03/2020 10

Arbre de décision
L'arbre de décision construit des modèles de classification ou de régression en
forme d'une structure d'arbre.

Il décompose la dataset en sous-ensembles de plus en plus petits et développe en

même temps incrémentalement un arbre de décision associé.

Le résultat final est un arbre avec deux sortes de noeuds "Decision nodes" et "Leaf
nodes":
 Decision node (ex., Outlook) peut avoir deux branches ou plus (ex. Sunny, Overcast et Rainy)
 Leaf node (ex., Play) représente une classification ou une décision

Le nœud de décision le plus haut dans un arbre correspond au meilleur prédicteur et
est appelé "Root node"

Les arbres de décision peuvent gérer les données catégoriques et numériques.

11/03/2020 11

Arbre de décision
11/03/2020 12

Arbre de décision: comment?!

• L'algorithme de base pour la construction d'un arbre de décision est appelé
"ID3" crée par J. R. Quinlan qui utilise une recherche descendante et "greedy"
à travers l'espace des branches possibles sans retour en arrière.

• ID3 utilise l'Entropie (Entropy) et le gain de l'information (Information Gain)

pour construire un arbre de décision.
11/03/2020 13

Rappel: Entropie de Shannon

L'entropie de Shannon, crée par Claude Shannon, est une fonction
mathématique qui, intuitivement, correspond à la quantité
d'information contenue ou délivrée par une source d'information.

Cette source peut être un texte écrit dans une langue donnée, un signal
électrique ou encore un fichier informatique quelconque (collection d'octets).
11/03/2020 14

Rappel: Entropie de Shannon

Du point de vue d'un récepteur, plus la source émet d'informations différentes,
plus l'entropie (ou incertitude sur ce que la source émet) est grande.

 Ainsi, si une source est réputée envoyer toujours le même symbole, par
exemple la lettre 'a', alors son entropie est nulle, c'est-à-dire minimale.

Par contre, si la source est réputée envoyer un 'a' la moitié du temps et un 'b'
l'autre moitié, le récepteur est incertain de la prochaine lettre à recevoir. L'entropie
de la source dans ce cas est donc non nulle (positive) et représente
quantitativement l'incertitude qui règne sur l'information émanant de la source.
11/03/2020 15

Arbre de décision: comment?!

• L'algorithme ID3 utilise l'entropie pour calculer l'homogénéité d'un échantillon.
• Si l'échantillon est complètement homogène, l'entropie est égal à 0 et si
l'échantillon est divisé équitablement, il a une entropie égal à 1
11/03/2020 16

Arbre de décision: comment?!

• Pour construire un arbre de décision, nous devons calculer deux types
d'entropie en utilisant des tables de fréquence:
a) L’Entropie utilisant la table de fréquence de l’attribut « class »
b) L’Entropie utilisant la table de fréquence de l’attribut « class » et un
prédicteur
11/03/2020 17

Rappel: Logarithme
• Le logarithme de base b d'un nombre réel strictement positif est
la puissance à laquelle il faut élever la base b pour obtenir ce nombre.
• Par exemple, le logarithme décimale:
Pour 𝑥 > 0, si 𝑦 = 𝑙𝑜𝑔10 (𝑥) alors 𝑥 = 10𝑦
• Le logarithme décimale s’écrit aussi comme « Log(x) ».

Astuce de calcule:
Pour calculer le logarithme binaire (𝑙𝑜𝑔2 (x)) à l’aide de la calculatrice:
𝑙𝑜𝑔10 x
𝑙𝑜𝑔2 x =
𝑙𝑜𝑔10 2
11/03/2020 18

Arbre de décision: comment?!

a) L’Entropie utilisant la table de fréquence de l’attribut « class »:
11/03/2020 19
11/03/2020 20

Arbre de décision: comment?!

b) L’Entropie utilisant la table de fréquence de l’attribut « class » et un
prédicteur: On prend d’abord les tables de fréquences
11/03/2020 21

Arbre de décision: comment?!

b) L’Entropie utilisant la table de fréquence de deux attributs (l’attribut
« class » et un prédicteur): On prend d’abord les tables de fréquences
11/03/2020 22

Arbre de décision: comment?!

• Une fois qu’on calculé les deux entropies (celle de l’attribut « class » et celle
qui unis l’attribut « class » et chaque prédicteur) . On peut alors calculé le
gain d’information.
11/03/2020 23

Comparaison du gain d’information

• On calcule le gain pour chaque prédicteur comme on a fait pour l’attribut
Outlook.
11/03/2020 24

Règle 1: Comparaison du gain d’information

• On choisit l'attribut avec le plus grand gain d'information en tant que « Root
Node »
11/03/2020 25

Root Node
• On choisit l'attribut avec le plus grand gain d'information en tant que « Root
Node »
11/03/2020 26

Régle 1: « Root Node » et aussi le premier noeud « Decision Node»

• On choisit l'attribut avec le gain d'information le plus grand en tant que "Decision
Node", Et on divise la dataset par ses branches. On répète le même processus sur
chaque branche.
11/03/2020 27

Règle 2
• Une branche avec entropie égal à 0 est un nœud «Leaf Node». Par exemple (
Outlook= Overcast)
11/03/2020 28

Règle 3
• Une branche avec une entropie supérieure à 0 nécessite une division
supplémentaire. Par exemple (Outlook=Sunny)
11/03/2020 29

Règle 3
• Une branche avec une entropie supérieure à 0 nécessite une division
supplémentaire. Par exemple (Outlook=Sunny)
11/03/2020 30

Règle 3
• Une branche avec une entropie supérieure à 0 nécessite une division
supplémentaire. Par exemple (Outlook=Sunny)
11/03/2020 31

Règle 4
• L'algorithme ID3 est exécuté récursivement sur les branches « non-leaf »,
jusqu'à ce que toutes les données soient classées.
11/03/2020 32

« Arbre de décision » à « Règles de Décision »

• Un arbre de décision peut facilement être transformé en un ensemble de
règles (instructions conditionnelles) en considérant un par un les nœuds
depuis le nœud "Root Node" vers les nœuds "Leaf Nodes".
11/03/2020 33

Arbre de décision- Régression

11/03/2020 34

Arbre de décision- Régression

11/03/2020 35

Entropy vs Standard deviation

11/03/2020 36

Arbre de décision_régression: comment?!

• Pour construire un arbre de décision, nous devons calculer deux types

d’écart-type:

a) Standard deviation de l’attribut « class »

b) Standard deviation de l’attribut « class » et un prédicteur.
11/03/2020 37

Entropy vs Standard deviation

𝟏 𝑵
La moyenne (Mean): 𝝁= 𝒊=𝟏 𝒙𝒊
𝑵
𝟏 𝑵 𝟐
L’écart-type (Standard deviation): 𝝈= 𝒊=𝟏 𝒙𝒊 − 𝝁
𝑵
11/03/2020 38

Arbre de décision_régression: comment?!

a) On calcule d’abord « Standard deviation » pour l’attribut « class »:
11/03/2020 39

Arbre de décision_régression: comment?!

b) On calcule Standard deviation de l’attribut « class » et un prédicteur.
11/03/2020 40

Arbre de décision_régression: comment?!

• On construit ainsi les tables d’écart type pour chaque prédicteur étant donné
la classe.
11/03/2020 41

Standard Deviation Reduction (SDR)

• On calcule alors la réduction de l’écart-type pour chaque prédicteur comme
suit: (Exemple pour Outlook)
11/03/2020 42

Comparaison du SDR
• On calcule le SDR de la même façon pour chaque prédicteur
11/03/2020 43

Règle 1: « Root Node» et aussi le premier « Decision Node »

• L’attribut avec le plus grand SDR est choisit en tant que « Root Node » et
aussi il sera le premier nœud « Decision Node ».
11/03/2020 44

Règle 1: « Root Node» et aussi le premier « Decision Node »

• Et on divise la dataset par les branches du nœud « Root Node ». On répète le même
processus sur chaque branche.
11/03/2020 45

Arbre de décision_régression: comment?!

• Cas du nœud « Decision Node » ‘Sunny’
11/03/2020 46

Arbre de décision_régression: comment?!

• Cas du nœud « Decision Node » ‘Sunny’
11/03/2020 47

Règle 2
• Une branche avec un écart-type supérieur à 0 doit être divisée davantage.
11/03/2020 48

Règle 2
• En pratique, nous avons besoin d'un critère d'arrêt. Par exemple, lorsque l'écart-type
pour la branche devient inférieur à une certaine fraction (par exemple, 5%) d'écart
type de la dataset complet OU lorsqu'il reste trop peu d'instances dans la branche
(par exemple, 3)
11/03/2020 49

Arbre de décision_régression: comment?!

• Cas du nœud « Decision Node » ‘Rainy’
11/03/2020 50

Règle 3
• Le processus est exécuté récursivement sur les branches « non-leaf », jusqu'à ce que toutes
les données sont traitées.
• Lorsque le nombre d'instances est supérieur à 1 sur un nœud «Leaf Node», on calcule la
moyenne comme valeur finale pour la cible.
11/03/2020 51

Random Forest
 Les arbres de décisions sont très prônes à
l’Overfitting (bonne performance sur les
données d’entrainement mais pas sur le test)

 Pour lutter contre cela, on peut construire

plusieurs arbres de décision alternatifs et les
laisser «voter» sur le classement final:
 Ré-échantillonner au hasard les données d'entrée
pour chaque arbre (bootstrap aggregating
bagging)
 Rendre aléatoire un sous-ensemble des attributs
pour limiter le choix dans chaque étape.
11/03/2020 52

Random Forest (Forêt Aléatoire)

• 𝑧 = { 𝑥1 , 𝑦1 … 𝑥𝑛 , 𝑦𝑛 } échantillon d’apprentissage, 𝑥𝑖 décrit par 𝑝
variables.
• Pour 𝑎 = 1 … 𝐴 (𝐴 représente le nombre d’arbres formés dans la Forêt )
• Tirer un échantillon aléatoire 𝑧𝑎 avec remise parmi 𝑧
• Estimer un arbre sur 𝑧𝑎 avec randomisation des variables
• Pour la construction de chaque nœud de chaque arbre, on tire uniformément 𝑞
variables parmi 𝑝 pour former la décision associée au nœud

• En fin d’algorithme, on possède 𝐴 arbres que l’on moyenne ou qu’on fait

voter pour la régression ou la classification
• En général, un choix optimal pour 𝑞 est à peu près 𝑞 ≈ 𝑝
11/03/2020 53

K-nearest Neighbors
11/03/2020 54

K-nearest Neighbors
• L’algorithme K-nearest Neighbors (ou K-plus-proche voisins en français)
est un algorithme simple qui stocke tous les cas disponibles et classe les
nouveaux cas en fonction d'une mesure de similarité (par exemple, une
fonction de distance)

• Une nouvelle instance est classée par un vote majoritaire de ses voisins. Ainsi
l'instance est classifiée (labélisée) comme appartenant à la classe la plus
commune parmi ses K plus proches voisins et ces derniers sont mesurés en
utilisant une fonction de distance.

• Si K = 1, alors l'instance est simplement labélisée comme appartenant à la

classe de son voisin le plus proche
11/03/2020 55

K-nearest Neighbors: comment?!

Une nouvelle instance est classée par un vote majoritaire de ses voisins. Ainsi
l'instance est classifiée (labélisée) comme appartenant à la classe la plus commune
parmi ses K plus proches voisins et ces derniers sont mesurés en utilisant une fonction
de distance.
11/03/2020 56

Les fonctions de distance

• La distance Euclidienne:

• La distance de Minkowski:

• La distance de Hamming:
11/03/2020 57

Les variables catégoriques

• Dans le cas où on a des variables catégoriques on doit utiliser la distance de
Hamming.
• Ceci fait aussi appel à la normalisation des variables numériques entre 0 et 1
lorsqu'on a un mélange de variables numériques et catégoriques dans la
dataset.
11/03/2020 58

La similarité – distance de Hamming

11/03/2020 59

Comment choisir le nombre de voisins (K)?

• Pour choisir la valeur optimale pour K, il est conseillé de d'abord inspecter les
données.
• En général, un K qui est grand donne plus de précision car il réduit le bruit
global mais il n'y a pas de garantie.
• La validation croisée est un autre moyen à utiliser pour déterminer une bonne
valeur pour K, en utilisant une dataset indépendante pour valider sa valeur.
• Historiquement, le K optimal pour la plupart des datasets est entre 3-10. Cela
produit de bien meilleurs résultats que 1NN.
11/03/2020 60

K-nearest neighbors (Exemple)

On considère la dataset suivant sur le défaut de crédit. "Âge" et "Loan" sont deux variables
numériques (prédicteurs) et "Default" est la cible.
11/03/2020 61

K-nearest neighbors (Exemple)

• On considère la dataset suivant sur le défaut de crédit. " Age" et "Loan" sont deux variables numériques
(prédicteurs) et "Default" est la cible.
• On peut maintenant utiliser le training set pour classifier une nouvelle instance (Age = 48 et Loan = 142
000 $) en utilisant la distance euclidienne.
11/03/2020 62

K-nearest neighbors (Exemple)

• Pour K=1 quelle sera la valeur de la cible « Default »?

• Et pour K= 3?
11/03/2020 63

K-nearest neighbors (Exemple)

Pour K= 1 on a:
D = Sqrt[(48-33)^2 + (142000-150000)^2] = 8000.01
La réponse est Default=Y
11/03/2020 64

K-nearest neighbors (Exemple)

Pour K=3 on :
Sur les trois plus proches voisins on a deux voisins étiquetés par Default = Y et un voisin qui est
classé comme Default = N. La prédiction pour la nouvelle instance est donc Default = Y
11/03/2020 65

Distance normalisée
• Un inconvénient majeur dans le calcul des mesures de distance directement
à partir du training set est dans le cas où les variables ont différentes
échelles de mesure ou dans le cas où on a un mélange de variables
numériques et catégoriques.

• Exemple: si un attribut est basé sur le revenu annuel en dollars, et l'autre

attribut est basé sur l'âge en années. Par conséquence, le revenu aura une
influence beaucoup plus élevée sur la distance calculée.
• Une solution consiste à normaliser le training set.
11/03/2020 66

Distance normalisée
En utilisant la distance normalisée sur la même dataset de l'exemple, la nouvelle instance a
renvoyé un voisin différent ce qui n'est pas un bon signe de robustesse.
11/03/2020 67

KNN régression- distance

• Cas de K=1
• La valeur de « House Price Index » prédite est : 264
11/03/2020 68

KNN régression- distance normalisée

• Cas de K=1
• La valeur de « House Price Index » prédite est : 231
11/03/2020 69

K-nearest neighbors (Règle)

• Si K = 1, sélectionnez le voisin le plus proche

• Si K> 1,
• Pour la classification, sélectionnez le voisin le plus fréquent.
• Pour la régression calculer la moyenne de K voisins.
11/03/2020 70

Algorithme d’apprentissage:
Par Clustering / Cas du non-supervisé
11/03/2020 71

K-means
11/03/2020 72

Clustering
11/03/2020 73

K-means clustering
• K-means a l'intention de partitionner n points en k clusters dans lesquels chaque
point appartient au cluster qui a la moyenne la plus proche. Cette méthode produit
exactement k clusters différents et distincts les uns des autres.
• Le meilleur nombre de clusters k qui donnerait la meilleure séparation(distance) n'est
pas connu a priori et doit être calculé à partir des données. L'objectif de K-Means est
de minimiser la variance totale intra-cluster, ou bien la fonction d'erreur quadratique:
11/03/2020 74

K-means: comment?!
1. Regroupe les données en k groups avec k
qui est prédéfini.
2. Sélectionne k points au hasard comme
centres de cluster.
3. Attribue les données d'entrainement au
centre du cluster le plus proche en utilisant
la distance euclidienne.
4. Calcule le centroïd ou la moyenne de
toutes les instances de chaque groupe.
5. Répète les étapes 3 et 4 jusqu'à ce que les
mêmes points soient attribués au même
groupe à tours consécutifs.
11/03/2020 75

K-means
• K-Means est une méthode relativement efficace.
• Cependant, nous devons d'abord spécifier le nombre de clusters et les
résultats à la fin sont sensibles à l'initialisation et se terminent souvent à un
optimum local.
• Malheureusement, il n'existe pas de méthode théorique globale pour trouver
le nombre optimal de clusters K.
• Une approche pratique consiste à comparer les résultats de plusieurs
passages avec des K différents et à choisir le meilleur en fonction d'un critère
prédéfini.
• En général, un grand K diminue probablement l'erreur mais augmente le
risque d'overfitting.
11/03/2020 76

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant
seulement leur âge (un espace unidimensionnel) comme suit:

15,15,16,19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65
11/03/2020 77

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge
(un espace unidimensionnel) comme suit:

15,15,16,19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65

On choisit K=2
Les clusters initiaux:
• Centroid (C1) = 16 [16]
• Centroid (C2) = 22 [22]
11/03/2020 78

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un
espace unidimensionnel) comme suit:

15,15,15.33,16,19,19,20,20,21,22,28,35,36.25,40,41,42,43,44,60,61,65

On choisit K=2
Les clusters initiaux:
• Centroid (C1) = 16 [16]
• Centroid (C2) = 22 [22]
Itération 1:
• C1 = 15.33 [15,15,16]
• C2 = 36.25 [19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65]
11/03/2020 79

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un
espace unidimensionnel) comme suit:

15,15,15.33,16,19,19,20,20,21,22,28,35,36.25,40,41,42,43,44,60,61,65

On choisit K=2
Les clusters initiaux:
• Centroid (C1) = 16 [16]
• Centroid (C2) = 22 [22]
Itération 1:
• C1 = 15.33 [15,15,16]
• C2 = 36.25 [19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65]
11/03/2020 80

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un espace
unidimensionnel) comme suit:

15,15,16,18.56,19,19,20,20,21,22,28,35,40,41,42,43,44,45.90,60,61,65

On choisit K=2
Les clusters initiaux:
• Centroid (C1) = 16 [16]
• Centroid (C2) = 22 [22]
Itération 1:
• C1 = 15.33 [15,15,16]
• C2 = 36.25 [19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65]
Itération 2:
• C1 = 18.56 [15,15,16,19,19,20,20,21,22]
• C2 = 45.90 [28,35,40,41,42,43,44,60,61,65]
11/03/2020 81

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un espace
unidimensionnel) comme suit:

15,15,16,19,19,19.50,20,20,21,22,28,35,40,41,42,43,44,47.89,60,61,65

On choisit K=2
Itération 1:
• C1 = 15.33 [15,15,16]
• C2 = 36.25 [19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65]
Itération 2:
• C1 = 18.56 [15,15,16,19,19,20,20,21,22]
• C2 = 45.90 [28,35,40,41,42,43,44,60,61,65]
Itération 3:
• C1 = 19.50 [15,15,16,19,19,20,20,21,22,28]
• C2 = 47.89 [35,40,41,42,43,44,60,61,65]
11/03/2020 82

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un espace
unidimensionnel) comme suit:

15,15,16,19,19,19.50,20,20,21,22,28,35,40,41,42,43,44,47.89,60,61,65

On choisit K=2
Itération 2:
• C1 = 18.56 [15,15,16,19,19,20,20,21,22]
• C2 = 45.90 [28,35,40,41,42,43,44,60,61,65]
Itération 3:
• C1 = 19.50 [15,15,16,19,19,20,20,21,22,28]
• C2 = 47.89 [35,40,41,42,43,44,60,61,65]
Itération 4:
• C1 = 19.50 [15,15,16,19,19,20,20,21,22,28]
• C2 = 47.89 [35,40,41,42,43,44,60,61,65]
11/03/2020 83

K-means: (exemple)
Supposons qu'on souhaite regrouper les visiteurs d'un site Web en utilisant seulement leur âge (un
espace unidimensionnel) comme suit:

15,15,16,19,19,19.50,20,20,21,22,28,35,40,41,42,43,44,47.89,60,61,65

Conclusion
• Aucun changement entre les itérations 3 et 4 n'a été noté.
• En utilisant k-means clustering, 2 groupes ont été identifiés 15-28 et 35-65.
• Le choix initial des centroïds peut affecter les clusters de sortie, c'est pourquoi
l'algorithme est souvent exécuté plusieurs fois avec des conditions de départ
différentes afin d'avoir une vision juste de ce que les clusters devraient être.
11/03/2020 84

Apprentissage automatique
11/03/2020 85

Algorithmes d’apprentissage