Machine Learning: Supervised Learning

Mohamed El Gorrim

1 Introduction
1.1 Apprentissage Supervisé
Ce type d’apprentissage se base sur des données étiquetées. C-à-d on a une class (output)
dans les données. On a 2 types d’apprentissage :

• Régression : La régression consiste à apprendre la relation entre les features et

l’output. Le modèle prédit donc des valeurs numériques continues.

• Classification : La classification consiste à prédire la classe à laquelle appartient

une donnée. L’output (Label) est une valeur discrète/catégorielle.

1.2 Notation
• ∀x ∈ Rn

• Y = θ1 x1 + θ2 x2 + ... + θn xn + θ0

• Classification : ∀x ∈ Rn : Y ∈ [0, 1, ...n]. Le modèle choisit l’une des classes.

• Régression : y ∈ R. Output est une valeur continue.

2 Modèles de Régression
Les modèles de régression :
• Régression Linéaire Simple.

• Régression Linéaire Multiple.

• Régression Polynomiale.

2.1 Régression Linéaire Simple

Ce modèle établit une relation Linéaire entre input (feature) et l’output. On peut mod-
éliser les données comme suivant :

y = hθ (x) = θ0 + θ1 x1

ŷ = θ0 + θ1 X
Où :

1
Supervised Learning Machine Learning Notes

• y : valeur réelle

• ŷ : valeur prédite

• θ0 : L’interception

• θ1 : La pente (relation entre output et input)

2.1.1 Calcul des paramètres θ0 , θ1

Méthode de Moindre Carrée (Méthode Statistique):
P
Cov(x, y) (xi − x)(yi − y)
θ1 = = P
V ar(x) (xi − x)2

θ0 = y − θ1 x
Avec :
1X 1X
x= xi ; y = yi
n n
Après calcul, on obtient notre modèle : ŷ = θ0 + θ1 x. Maintenant, on passe à faire des
estimation des erreurs via :
r
1X 1X
RM SE = (yi − ŷi )2 ou M AE = |yi − ŷi |
n n
Cette méthode ne donne pas toujours des résultats optimaux.

2.1.2 Stochastic Gradient Descent (Méthode d’Optimization)

Cette méthode met à jour les paramètres θ0 , θ1 après chaque data point (ou les exemples
(xi , yi ) choisi aléatoirement/Stochastiquement).

θnew := θold − α∇J(θ; xi , yi )

Les étapes :

1. Choisir des valeurs initiales pour les paramètres θ0 , θ1 .

2. Calculer les valeurs prédites ŷ = θ0 + θ1 x.

3. Calculer l’Erreur ŷ − y pour chaque exemple.

4. Mettre à jour les paramètres pour chaque exemple xi :

θjnew := θjold − α · Erreur · xi

5. Répéter plusieurs fois (epoch) jusqu’à convergence.

Note: Learning rate α is a hyperparameter (e.g., 0.1, 0.01, 0.001).

2
Supervised Learning Machine Learning Notes

2.2 Exemple Numérique (SGD)

Données :
X Y
1 2
2 3
3 6

1er époch : Prenons les paramètres suivants : θ0 = 0, θ1 = 0, α = 0.1.

Modèle initial : ŷ = θ0 + θ1 x = 0.

• 1er point (1,2) :

ŷ = 0
Erreur = ŷ − y = 0 − 2 = −2
Mettre à jour :
θ0 := θ0 − α · Erreur = 0 − 0.1(−2) = 0.2
θ1 := θ1 − α · Erreur · x = 0 − 0.1(−2) · 1 = 0.2
Nouveaux paramètres : θ0 = 0.2, θ1 = 0.2.
• 2ème point (2,3) :
ŷ = θ0 + θ1 x = 0.2 + 0.2(2) = 0.6
Erreur = ŷ − y = 0.6 − 3 = −2.4
Mettre à jour :
θ0 := 0.2 − 0.1(−2.4) = 0.44
θ1 := 0.2 − 0.1(−2.4)(2) = 0.68
Nouveaux paramètres : θ0 = 0.44, θ1 = 0.68.
• 3ème point (3,6) : De même manière pour 3ème ligne.

Après 1 epoch, on trouve que θ0 ≈ 0.792, θ1 ≈ 1.736.

Modèle final après 1 epoch : y = 0.792 + 1.736x.

3
Supervised Learning Machine Learning Notes

Calcul des Erreurs (Résumé) :

X y ŷ Erreur Erreur2
1 2 2.46 0.46 0.2116
2 3 4.2 1.2 1.44
3 6 5.94 -0.06 0.0036
Somme 1.6552

r
1.6552
RM SE = = 0.74
3

2.3 Régression Linéaire Multiple

Ce modèle forme une relation entre plusieurs features (x1 ...xn ) et l’output "y".
n
X
ŷ = hθ (x) = θ0 + θ1 x1 + ... + θn xn = θ0 + θi xi
i=1

Forme vectorielle : hθ (x) = θT x (avec x0 = 1). Par exemple : hθ (x) = θ0 + θ1 x1 + θ2 x2 .

2.3.1 Optimisation
Comme la régression Linéaire Simple, la méthode d’optimization utilisée pour ce modèle
est Stochastic Gradient Descent. Cost function (MSE):
n
1 X
J(θ) = (hθ (xi ) − yi )2
2n i=1

n
∂J(θ) 1X
⇒ = (hθ (xi ) − yi )xi,j
∂θj n i=1
Après dérivation partielles, on obtient la formule pour mettre à jour les paramètres :

θj := θj − α · Erreur · xi,j

2.4 Exemple (Régression Multiple)

Supposons une dataset avec 2 features :

Point Taille (x1 ) Chambre (x2 ) Prix (y)

P1 1 2 3
P2 2 1 4

1er Epoch : Les paramètres initiaux : θ0 = θ1 = θ2 = 0. Learning rate α = 0.1.

• Point P1 (1, 2, 3) :
hθ (x) = 0 + 0(1) + 0(2) = 0
Erreur = ŷ − y = 0 − 3 = −3

4
Supervised Learning Machine Learning Notes

Mettre à jour :
θ0 := 0 − 0.1(−3) = 0.3
θ1 := 0 − 0.1(−3)(1) = 0.3
θ2 := 0 − 0.1(−3)(2) = 0.6
Nouveaux paramètres : θ0 = 0.3, θ1 = 0.3, θ2 = 0.6.

• Point P2 (2, 1, 4) :

hθ (x) = 0.3 + 0.3(2) + 0.6(1) = 1.5

Erreur = 1.5 − 4 = −2.5

Mettre à jour :
θ0 := 0.3 − 0.1(−2.5) = 0.55
θ1 := 0.3 − 0.1(−2.5)(2) = 0.8
θ2 := 0.6 − 0.1(−2.5)(1) = 0.85

Résultats après updates : θ0 = 0.55, θ1 = 0.8, θ2 = 0.85.

Calcul final :

x1 x2 y hθ (x) Erreur
1 2 3 3.05 0.05
2 1 4 3 -1

r
(−1)2 + (0.05)2
RM SE = = 0.7
2

2.5 Régression Polynomiale

Utilisée lorsque la relation entre inputs (x1 ...xn ) et output y n’est pas linéaire mais plutôt
parabolique ou généralement curviligne.
n
X
hθ (x) = θ0 + θ1 x1 + θ2 x22 + ... + θn xnn = θ i xi
i=0

La méthode d’optimisation est similaire au celle du Régression Linéaire multiple

(SGD), car la régression polynomiale est un cas particulier de la régression linéaire mul-
tiple (on pose x2 = x2 , x3 = x3 , etc.).
Attention : L’utilisation des régression polynomial avec grand degré conduit souvent
au Sur-apprentissage (Overfitting), car le modèle devient trop flexible et apprend le
bruit (noise) au lieu du pattern.

5
Supervised Learning Machine Learning Notes

3 Classification
3.1 Modèles de Classification
• Regression Logistique (binary)
• KNN (binary-multi)
• Decision Tree
• SVM
Types :
• Binary classification : ∀x ∈ Rn : Y ∈ [0, 1]
• Multi-class classification

3.2 Régression Logistique

Modèle de classification binaire (∀x; y ∈ {0, 1}). Contrairement à la régression linéaire qui
prédit des valeurs continues, ce modèle prédit une probabilité : P (y = 1|x) ou P (y = 0|x).
Ce modèle utilise la fonction Sigmoïde :
1
σ(z) =
1 + e−z
Hypothèse du modèle :
1
ŷ = hθ (x) = σ(θ0 + θ1 x1 + ... + θn xn ) =
1 + e−(θT x)
On calcule d’abord z = θT x, puis on applique la sigmoïde : ŷ = σ(z).

3.2.1 Cost function (Log Loss / Binary Cross Entropy)

n
1X
J(θ) = − [yi log(ŷi ) + (1 − yi ) log(1 − ŷi )]
n i=1
Pour un seul exemple d’entraînement :
L(ai , yi ) = −[yi log(ai ) + (1 − yi ) log(1 − ai )]
• Si y = 1, Coût = − log(ai )
• Si y = 0, Coût = − log(1 − ai )

6
Supervised Learning Machine Learning Notes

3.2.2 SGD pour la Régression Logistique

La mise à jour des paramètres est similaire à la régression Linéaire :

1. Prédiction : ŷ = σ(θT x)

2. Erreur : e = ŷ − y

3. Mise à jour (pour chaque θj ) : θj := θj − α · e · xj

3.2.3 Décision finale pour classification

Après calcul des paramètres et application au modèle, on calcule la probabilité pour
chaque nouvel exemple. Si la probabilité prédite :

• ŷ ≥ 0.5 ⇒ classe 1

• ŷ < 0.5 ⇒ classe 0

3.3 KNN (K-Nearest Neighbors)

KNN repose sur une idée très simple : "Dis moi qui tu ressembles, je te dirai qui tu es!".
Idée générale : Pour classifier (ou prédire) un nouveau point, voir les K proches
points d’entraînement (voisins).

• Faire un vote en se basant sur les voisins (classification).

• Ou prendre la moyenne (régression).

Les Distances utilisées :

• Euclidienne : d(p, q) =
pP
(pi − qi )2

• Manhattan : d(p, q) =
P
|pi − qi |

• Minkowski : d(p, q) = ( |pi − qi |k )1/k (Généralisation des deux précédentes).

P

Les étapes essentielles pour KNN :

1. Choisir la valeur du hyperparameter K.

2. Calculer la distance entre le point d’exemple et tout les points d’entraînement.

3. Trier par distance et prendre les K plus proches.

4. Faire un vote (majority vote pour classification) ou prendre la moyenne (pour ré-
gression).

5. Retourne la classe prédite.

7
Supervised Learning Machine Learning Notes

3.3.1 Exemple numérique

Dataset (Features X1 , X2 , Label) :
• (7, 7) -> bon
• (7, 4) -> bon
• (3, 3) -> pas bon
• (1, 4) -> bon
Pour mon nouvelle point (X1 = 3, X2 = 7).
Calcul des distances :
• d1 = (7 − 3)2 + (7 − 7)2 = 4 (bon)
p

• d2 = (7 − 3)2 + (4 − 7)2 = 5 (bon)

p

• d3 = (3 − 3)2 + (3 − 7)2 = 4 (pas bon)

p

• d4 = (1 − 3)2 + (4 − 7)2 ≈ 3.6 (bon)

p
√
On trie les distances : [3.6, 4, 4, 5]. Pour K = 3, on prend les 3 valeurs [ 13, 4, 4] avec
les labels [bon, pas bon, bon]. Vote : 2 "bon", 1 "pas bon". Classe "bon" gagne. Alors
(3,7) sera classifié en classe "bon".

3.3.2 Comment choisir K ?

• Pour K = 1, le modèle mémorise les données, c-à-d une variance élevée (Overfitting).
• Pour K trop grand, tout les points peuvent faire un vote, par conséquence un bias
élevée (Underfitting).
• Technique appelée Elbow Method : on mesure l’erreur pour chaque K de 1 à
40, puis on choisit où l’erreur stabilise.

Note : KNN est un algorithme paresseux (Lazy Learner). KNN est sensible à l’échelle
des features, donc il faut normaliser/Standariser les features.

3.4 Naïve Bayes

NB est un algorithme de classification (aussi un modèle génératif) basé sur le théorème
de Bayes.
Modèle discriminatif vs modèle génératif :
• Discriminatif : Apprennent la frontière entre les classes, ils prédisent directement
P (y|x; θ). Exemple : Régression Logistique.
• Génératif : Apprennent comment chaque classe génère les données, ils modélisent
P (x, y; θ). Il peut donc estimer la classe, et générer des nouvelles exemples.
Théorème de Bayes :
P (x|wi ) · P (wi )
P (wi |x) =
P (x)

8
Supervised Learning Machine Learning Notes

• P (wi |x) : Probabilité que x appartient au classe i (Posterior).

• P (x|wi ) : Probabilité que la classe i génère x (Vraisemblance / Likelihood).

• P (wi ) : Fréquence de la classe (Prior).

• P (x) : Constante (Evidence).

Si nous utilisons le théorème de Bayes comme classificateur, notre but est de maximiser
la probabilité (posterior) :

classe prédite = arg max P (wi |xi )

Comme P (x) est constante pour toutes les classes, on l’ignore.

Le coté "Naïve" de l’algorithme : Ça veut dire que "Toutes les features sont
indépendantes".
P (x|wi ) = P (x1 |wi ) · P (x2 |wi ) · ...
En pratique, c’est la partie "naïve" de Naïve Bayes. Cette hypothèse n’est probablement
jamais satisfaites.

3.4.1 Exemple (Naïve Bayes)

Données :

Type Long Sucrée Jaune Total

Banane 400 350 450 500
Orange 0 150 300 300
Autre 100 150 50 200
Total 500 650 800 1000

Objectif : Classifier un fruit inconnu (Long, Sucrée, Jaune).

Étape 1 : Calcul des priors
500 300 200
P (Banane) = = 0.5, P (Orange) = = 0.3, P (Autre) = = 0.2
1000 1000 1000
Étape 2 : Probabilité Globales des features :
500 650 800
P (long) = = 0.5 / P (sucre) = = 0.65 / P (jaune) = = 0.8
1000 1000 1000
Étape 3 : Probabilités conditionnelles (exemple banane) :

Card(Banane ∩ Long) 400

P (long|banane) = = = 0, 8
Card(Banane) 500
350
P (sucre|banane) = = 0, 7
500
450
P (jaune|banane) = = 0, 9
500

9
Supervised Learning Machine Learning Notes

Étape 4 : Posterior pour banane :

P (long|banane) · P (sucre|banane) · P (jaune|banane) · P (banane)

P (banane|long, sucre, jaune) =
P (long) · P (sucre) · P (jaune)
0, 8 · 0, 7 · 0, 9 · 0, 5
= ≈ 0, 969
0, 5 · 0, 65 · 0, 8
De la même manière pour les autres probabilités :

P (Orange| . . . ) ≈ 0

P (Autre| . . . ) ≈ 0.072
Résultat : Le fruit inconnu est Banane.

3.5 SVM (Support Vector Machine)

Les SVM sont des algorithmes très utilisés pour la classification, et plus rarement pour
régression (SVR).
Idée principale : SVM cherche un hyperplan qui sépare les classes avec la plus
grande marge possible, c-à-d la distance entre la frontière et les points les plus proches.
Concepts :

• Hyperplan : la frontière optimale qui sépare les classes (Ligne en 2D, plan en 3D,
hyperplan en nD).

• Support Vector : points plus proches de l’hyperplan, essentiels pour le modèle.

Il existe 2 types de SVM :

• SVM Linéaire : utilisé lorsque les données sont séparables par la droite. Le modèle
cherche un hyperplan optimal avec :

– Si wT x + b ≥ 1 ⇒ classe (+1)
– Si wT x + b ≤ −1 ⇒ classe (-1)

• SVM Non-Linéaire : utilisé quand les données ne sont pas séparables par une
droite linéaire, on utilise les Kernel (RBF ou Gaussien, Polynomiale) pour projeter
les données dans un espace où elles deviennent séparables.

3.5.1 Math de SVM Linéaire (Primal)

La fonction de décision : Y = wT x + b. Pour un problème linéairement séparé :

• wT x + b = 1 est une droite passant par les SV positifs.

• wT x + b = −1 est une droite passant par les SV négatifs.

• La marge est donc d = 2

||w||
.

10
Supervised Learning Machine Learning Notes

Pour Maximiser la marge, il faut Minimiser ||w||2 . C’est la formulation Hard Margin,
pas d’erreurs tolérées. Condition : yi (wT xi + b) ≥ 1.
Dans le cas où on doit éviter l’Overfitting (Soft Margin) :
N
||w||2
  X
min +C ξk
2 k=1

Avec ξk : erreurs tolérées, C > 0 : paramètre de régularisation qui équilibre marge et

erreurs.
Hinge Loss function : Définie par : L(y, f (x)) = max(0, 1 − yf (x)). Si la marge
(1 − yf (x)) est > 0, la classification est incorrecte ou trop proche de la marge.

3.5.2 SVM Non-Linéaire & Kernel Trick

Quand les données ressemblent à un cercle ou une spirale, il n’existe aucune ligne droite
possible en 2D, mais dans un espace 3D, c’est possible !
Kernel Trick : On utilise une Kernel function qui calcul directement le produit Scalaire
dans l’espace transformé.
Types de Kernel :

• Linéaire : K(x, y) = xT y

• Polynomiale : K(x, y) = (xT y + 1)d (d ≥ 2)

||x−y||2
• RBF/Gaussian : K(x, y) = e− 2σ 2

• Sigmoïde : K(x, y) = tanh(αxT y + C)

3.6 Decision Trees (Arbre de décision)

Un arbre de décision est un modèle d’apprentissage qui représente le processus de décision
sous forme d’un arbre. Structure :

• Nœud Interne : Condition sur un attribut.

• Branche : Résultat du test.

• Feuille : Décision finale (Classe).

Chaque racine → feuille correspond à une règle Logique [SI condition 1 ET condi-
tion 2 ALORS Yes.]
Principaux Algorithmes :

• ID3 : Crée un arbre multivoies, et Utilise l’entropie et le Gain d’information.

• C4.5 : Amélioration de ID3 par une étape de l’élagage (Pruning) pour améliorer la
capacité de l’arbre à généraliser.

• CART : (Classification and Regression Trees) Similaire à C4.5, mais construit des
arbres binaires et utilise l’indice de Gini.

11
Supervised Learning Machine Learning Notes

3.6.1 Notion Mathématique (ID3)

Entropie : X
Entropy(S) = − pi log2 (pi )
i
Gain d’information :
X
Gain(S, A) = Entropy(S) − p(Sv )Entropy(Sv )
v∈A

On choisit l’attribut qui maximise le gain.

3.6.2 Exemple (Decision Tree)

Données "Weather" :
Outlook Temp Humidity Wind Decision
Sunny Hot High Weak No
Sunny Hot High Strong No
Overcast Hot High Weak Yes
Rain Mild High Weak Yes
Rain Cool Normal Weak Yes
Rain Cool Normal Strong No
Overcast Cool Normal Strong Yes
Sunny Mild High Weak No
Sunny Cool Normal Weak Yes
Rain Mild Normal Weak Yes

1. Entropie de la décision :
6 6 4 4
Entropy(Decision) = −
log2 ( ) − log2 ( ) = 1.026
10 10 10 10
2. Calcul de Gain pour "Wind" : Valeurs possibles :
• Weak : 7 exemples (5 Yes, 2 No). Entropy = − 57 log2 ( 57 ) − 27 log2 ( 72 ) = 0.863
• Strong : 3 exemples (1 Yes, 2 No). Entropy = 0.91
7 3
Gain(Decision, W ind) = 1.026 − [ (0.863) + (0.91)] = 0.1489
10 10
De la même manière on calcul le Gain de tous les attributs :
• Outlook : 0.3772
• Humidity : 0.1805
• Temp : 0.1508
• Wind : 0.1489
Outlook est choisi comme la racine. Les branches seront Sunny, Rain et Overcast.
• Pour Overcast, la décision est toujours Yes.
• Pour Sunny, on calcule le gain d’information sur le sous-ensemble. On trouve que
l’attribut "Humidity" est choisi (High → N o, N ormal → Y es).
• Pour Rain, l’attribut "Wind" est choisi (W eak → Y es, Strong → N o).

12