Cours Machine Learning
Cours Machine Learning
20252026
★ Rééchissez 30 secondes
Comment écririez-vous un programme qui reconnaît un chat dans une photo ? Quelles
règles coderiez-vous ?
★ Rééchissez 30 secondes
Comment écririez-vous un programme qui reconnaît un chat dans une photo ? Quelles
règles coderiez-vous ?
Il faudrait des millions de règles... et elles ne couvriraient jamais tous les cas !
★ Rééchissez 30 secondes
Comment écririez-vous un programme qui reconnaît un chat dans une photo ? Quelles
règles coderiez-vous ?
Il faudrait des millions de règles... et elles ne couvriraient jamais tous les cas !
☞ À retenir
Certains problèmes sont trop complexes pour être résolus par des règles manuelles. C'est exactement
le type de problème pour lequel le ML a été inventé.
4 Résultat : un modèle capable de reconnaître des chats sur des données qu'il n'a jamais vues
4 Résultat : un modèle capable de reconnaître des chats sur des données qu'il n'a jamais vues
Au lieu de programmer les règles, on programme la capacité d'apprendre les règles à partir
de données. L'humain fournit les exemples, l'algorithme découvre les patterns.
Données
Règles (humain)
Résultats
Ex :
Calcul TVA : prix × 20%
Calcul salaire net
Conversion de devises (MAD → EUR)
Tri d'un tableau
Pr. ADDOU ML Séance 1 Partie 1 5/38
Programmation classique vs Machine Learning
Programmation classique Machine Learning
L'humain écrit les règles, le programme les L'humain fournit les exemples, l'algo décou-
applique. vre les règles.
Ex :
Ex : Détecter la fraude bancaire
Calcul TVA : prix × 20%
Diagnostic médical
Calcul salaire net
Prédire le prix immobilier à Oujda
Conversion de devises (MAD → EUR)
Reconnaissance d'images.
Tri d'un tableau
Pr. ADDOU ML Séance 1 Partie 1 5/38
Retenez cette inversion fondamentale
☞ À retenir
C'est une inversion du paradigme. En classique, vous codez comment résoudre. En ML,
vous montrez quoi résoudre et l'algo découvre le comment.
☞ À retenir
C'est une inversion du paradigme. En classique, vous codez comment résoudre. En ML,
vous montrez quoi résoudre et l'algo découvre le comment.
★ Question
Donnez un exemple de votre quotidien où le ML est utilisé sans que vous le sachiez.
☞ À retenir
C'est une inversion du paradigme. En classique, vous codez comment résoudre. En ML,
vous montrez quoi résoudre et l'algo découvre le comment.
★ Question
Donnez un exemple de votre quotidien où le ML est utilisé sans que vous le sachiez.
Réponses possibles :
Le ltre anti-spam de votre email (Gmail, Outlook)
Les recommandations YouTube / Netix / Spotify
La correction automatique de votre téléphone (clavier prédictif)
La reconnaissance faciale pour déverrouiller votre smartphone
Pr. ADDOU ML Séance 1 Partie 1 6/38
Le ML est utilisé dans votre quotidien
Finance NLP
Détection fraude ChatGPT, Claude
scoring crédit traduction auto
Médecine trading algo correction clavier Vision
Diagnostic IRM Reconnaissance
détection tumeurs faciale, OCR
analyse ECG voitures autonomes
ML
Commerce Sécurité
Amazon, Netix Cybersécurité
Spotify
publicité ciblée Transport Jeux détection malware
vidéosurveillance
Un programme informatique apprend d'une expérience E par rapport à une tâche T et une
mesure de performance P, si sa performance sur T, mesurée par P, s'améliore avec E.
Un programme informatique apprend d'une expérience E par rapport à une tâche T et une
mesure de performance P, si sa performance sur T, mesurée par P, s'améliore avec E.
Un programme informatique apprend d'une expérience E par rapport à une tâche T et une
mesure de performance P, si sa performance sur T, mesurée par P, s'améliore avec E.
n
1 X
R̂(f ) = L f (xi ), yi
n
i=1
n
1 X
R̂(f ) = L f (xi ), yi
n
i=1
Intuition : on cherche f qui commet le moins d'erreurs possible sur nos n exemples. C'est
comme un étudiant qui s'entraîne sur des exercices pour minimiser ses fautes.
Intuition : on cherche f qui commet le moins d'erreurs possible sur nos n exemples. C'est
comme un étudiant qui s'entraîne sur des exercices pour minimiser ses fautes.
★ Question
Si on trouve f avec R̂(f ) = 0 (zéro erreur sur les 5 000 patients), est-ce que f est parfait ?
Intuition : on cherche f qui commet le moins d'erreurs possible sur nos n exemples. C'est
comme un étudiant qui s'entraîne sur des exercices pour minimiser ses fautes.
★ Question
Si on trouve f avec R̂(f ) = 0 (zéro erreur sur les 5 000 patients), est-ce que f est parfait ?
Réponse : NON ! R̂(f ) = 0 signie que le modèle ne fait aucune erreur sur les 5 000 patients
d'entraînement. Mais cela ne garantit rien sur un nouveau patient jamais vu.
Un modèle avec zéro erreur sur l'entraînement peut être catastrophique sur de nouvelles
données. Pourquoi ? Parce qu'il a peut-être mémorisé les réponses au lieu de comprendre les
patterns.
★ Question
Si on trouve f avec R̂(f ) = 0 (zéro erreur sur les 5 000 patients), est-ce que f est parfait ?
★ Question
Si on trouve f avec R̂(f ) = 0 (zéro erreur sur les 5 000 patients), est-ce que f est parfait ?
Un étudiant qui mémorise les réponses des annales a R̂ = 0 sur les annales. Mais à l'examen
(nouvelles questions), il échoue car il n'a rien compris.
C'est exactement l'overtting : le modèle mémorise au lieu de comprendre.
⇒ On étudiera ce phénomène en détail dans la Partie 3 (biais-variance).
★ Question
Si on trouve f avec R̂(f ) = 0 (zéro erreur sur les 5 000 patients), est-ce que f est parfait ?
Un étudiant qui mémorise les réponses des annales a R̂ = 0 sur les annales. Mais à l'examen
(nouvelles questions), il échoue car il n'a rien compris.
C'est exactement l'overtting : le modèle mémorise au lieu de comprendre.
⇒ On étudiera ce phénomène en détail dans la Partie 3 (biais-variance).
☞ À retenir
L'objectif n'est pas de minimiser l'erreur sur les données d'entraînement, mais de généraliser : bien
prédire sur des données jamais vues.
Supervisé = le prof donne un TD avec corrigé. Vous comparez vos réponses au corrigé et apprenez
de vos erreurs. Objectif : réussir à l'examen (= nouvelles données).
Non supervisé = on vous donne 200 articles scientiques et on dit : regroupez-les par thème.
Personne ne vous dit quels thèmes existent. Vous découvrez la structure.
Renforcement = vous apprenez un jeu vidéo sans lire les règles. Vous essayez des actions : +1 si
bien, -1 si mal. Par essai-erreur, vous découvrez la stratégie optimale.
Dénition
Dénition
Pourquoi supervisé ? Parce qu'un superviseur (humain expert) a fourni les bonnes
réponses yi .
Dénition
Pourquoi supervisé ? Parce qu'un superviseur (humain expert) a fourni les bonnes
réponses yi . Processus étape par étape (diagnostic diabète) :
1 Collecte : 5 000 patients avec mesures (glucose, HbA1c, âge, IMC) et diagnostic du médecin
(yi ∈ {0, 1})
2 Entraînement : l'algo cherche f qui minimise l'erreur sur ces 5 000 cas
3 Test : on évalue f sur 1 000 nouveaux patients (jamais vus pendant le training !)
4 Prédiction : nouveau patient glucose=155, IMC=32 → ŷ = f (155, . . . , 32) = diabétique
Dénition
Pourquoi supervisé ? Parce qu'un superviseur (humain expert) a fourni les bonnes
réponses yi . Processus étape par étape (diagnostic diabète) :
1 Collecte : 5 000 patients avec mesures (glucose, HbA1c, âge, IMC) et diagnostic du médecin
(yi ∈ {0, 1})
2 Entraînement : l'algo cherche f qui minimise l'erreur sur ces 5 000 cas
3 Test : on évalue f sur 1 000 nouveaux patients (jamais vus pendant le training !)
4 Prédiction : nouveau patient glucose=155, IMC=32 → ŷ = f (155, . . . , 32) = diabétique
Le point clé : le modèle doit fonctionner sur des données qu'il n'a jamais vues. S'il ne fonctionne
que sur les données d'entraînement, c'est de l'overtting (mémorisation).
4
Prix
0
50 100 150 200
Surface (m2 )
Exemples :
Prix d'une maison
Température demain
Chire d'aaires mensuel
Durée d'un trajet
2 4 Classe 1
Feature 2
2
0
50 100 150 200
0
Surface (m2 )
0 2 4 6
Feature 1
Exemples :
Prix d'une maison
Spam / non-spam
Température demain
Diabétique / sain
Chire d'aaires mensuel
Chat / chien / oiseau
Durée d'un trajet
Chire manuscrit 09
☞ À retenir
Spam ou non-spam ?
Mention (TB/B/AB/P)
Nombre de visiteurs d'un site web Rég. Variable discrète mais traitée
comme continue
Nb d'étoiles d'un avis (15) Les deux ! Rég. si valeur continue possible,
classif. si valeurs discrètes
Dénition
On a des données {x1 , . . . , xn } sans labels. Personne ne nous dit la bonne réponse. L'algo
découvre des structures cachées par lui-même.
Dénition
On a des données {x1 , . . . , xn } sans labels. Personne ne nous dit la bonne réponse. L'algo
découvre des structures cachées par lui-même.
★ Rééchissez
Stratégie B : photocopier tous les corrigés. À l'examen, vous cherchez le corrigé le plus
similaire et vous adaptez.
Quelle stratégie est model-based ? Quelle stratégie est instance-based ?
★ Rééchissez
Stratégie B : photocopier tous les corrigés. À l'examen, vous cherchez le corrigé le plus
similaire et vous adaptez.
Quelle stratégie est model-based ? Quelle stratégie est instance-based ?
Réponse :
Stratégie A = Model-Based : vous avez appris un modèle (la formule). Les corrigés
ne sont plus nécessaires.
★ Rééchissez
Stratégie B : photocopier tous les corrigés. À l'examen, vous cherchez le corrigé le plus
similaire et vous adaptez.
Quelle stratégie est model-based ? Quelle stratégie est instance-based ?
Réponse :
Stratégie A = Model-Based : vous avez appris un modèle (la formule). Les corrigés
ne sont plus nécessaires.
L'algorithme utilise les données pour apprendre un modèle (une formule, des poids). Après
l'entraînement, les données d'entraînement ne sont plus nécessaires pour la prédiction : la
formule sut.
L'algorithme utilise les données pour apprendre un modèle (une formule, des poids). Après
l'entraînement, les données d'entraînement ne sont plus nécessaires pour la prédiction : la
formule sut.
L'algorithme mémorise toutes les données. Pour prédire, il compare le nouveau cas aux
plus proches voisins stockés en mémoire.
L'algorithme mémorise toutes les données. Pour prédire, il compare le nouveau cas aux
plus proches voisins stockés en mémoire.
6 patients mémorisés :
Glucose HbA1c IMC Diabétique ?
88 5.2 22 Non
92 5.5 24 Non
155 7.1 31 Oui
165 7.8 33 Oui
98 5.8 25 Non
145 6.9 29 Oui
Model-Based Instance-Based
Apprend un modèle (fonc- Mémorise les données
Principe tion/règle) d'entraînement
☞ À retenir
La quasi-totalité des algorithmes de ce cours sont model-based. L'exception notable est KNN, qui
est un algorithme instance-based.
★ Question fréquente
Le Deep Learning est plus puissant, pourquoi ne pas toujours l'utiliser ?
★ Question fréquente
Le Deep Learning est plus puissant, pourquoi ne pas toujours l'utiliser ?
3 Coût de calcul : les modèles profonds nécessitent beaucoup de ressources (GPU, temps).
Un Random Forest peut s'entraîner rapidement sur un ordinateur standard.
★ Question fréquente
Le Deep Learning est plus puissant, pourquoi ne pas toujours l'utiliser ?
★ Question fréquente
Le Deep Learning est plus puissant, pourquoi ne pas toujours l'utiliser ?
☞ À retenir
Pour les donnéestabulaires (très fréquentes en entreprise), les méthodes Shallow (RF, XGBoost)
sont souventaussi performantes voire meilleures que le Deep. Le Deep excelle sur les données
non structurées (images, texte, audio, vidéo).
★ Question fréquente
Le Deep Learning est plus puissant, pourquoi ne pas toujours l'utiliser ?
☞ À retenir
Pour les donnéestabulaires (très fréquentes en entreprise), les méthodes Shallow (RF, XGBoost)
sont souventaussi performantes voire meilleures que le Deep. Le Deep excelle sur les données
non structurées (images, texte, audio, vidéo).
Nouveau x
Données train Algorithme Modèle fθ
ŷ
TRAINING (1 fois, coûteux)
SCORING (répété, rapide)
Nouveau x
Données train Algorithme Modèle fθ
ŷ
TRAINING (1 fois, coûteux)
SCORING (répété, rapide)
Training Scoring
Quand 1 fois (ou périodiquement) En continu, en production, 24h/24
Durée Minutes à heures Millisecondes
Ce qui se passe Ajuste les paramètres θ Applique ŷ = fθ (xnew )
Coût Élevé (CPU/GPU, stockage) Très faible (calcul rapide)
Pr. ADDOU ML Séance 1 Partie 1 30/38
Training vs Scoring exemples concrets
Exemple : Gmail ltre anti-spam
Training (périodique) : Google entraîne des modèles sur des volumes massifs d'emails étiquetés.
Durée : de l'ordre de plusieurs heures sur des infrastructures distribuées.
Scoring (en continu) : à chaque nouvel email, le modèle le classe en quelques millisecondes. Le
modèle est xe entre deux phases d'entraînement.
Training (périodique) : Google entraîne des modèles sur des volumes massifs d'emails étiquetés.
Durée : de l'ordre de plusieurs heures sur des infrastructures distribuées.
Scoring (en continu) : à chaque nouvel email, le modèle le classe en quelques millisecondes. Le
modèle est xe entre deux phases d'entraînement.
Training (périodique) : modèle entraîné sur de grandes quantités de données (trajets, trac, météo,
horaires).
Scoring (en continu) : lors d'une requête, le modèle prédit le temps de trajet en temps réel en
combinant les données actuelles avec le modèle pré-entraîné.
Training (périodique) : Google entraîne des modèles sur des volumes massifs d'emails étiquetés.
Durée : de l'ordre de plusieurs heures sur des infrastructures distribuées.
Scoring (en continu) : à chaque nouvel email, le modèle le classe en quelques millisecondes. Le
modèle est xe entre deux phases d'entraînement.
Training (périodique) : modèle entraîné sur de grandes quantités de données (trajets, trac, météo,
horaires).
Scoring (en continu) : lors d'une requête, le modèle prédit le temps de trajet en temps réel en
combinant les données actuelles avec le modèle pré-entraîné.
☞ À retenir
3 questions avant tout projet ML : (1) Ai-je assez de données ? (2) Une solution simple sut-elle
? (3) Le ML apporte-t-il un gain réel ?
☞ À retenir
3 questions avant tout projet ML : (1) Ai-je assez de données ? (2) Une solution simple sut-elle
? (3) Le ML apporte-t-il un gain réel ?
À retenir
Règle simple : ML si complexe + données + objectif mesurable
Pr. ADDOU ML Séance 1 Partie 1 34/38
ML ou pas ? 10 situations (Quiz)
★ Rééchissez : ML ou pas ?
À retenir
Règle simple : ML si complexe + données + objectif mesurable
Pr. ADDOU ML Séance 1 Partie 1 34/38
Récapitulatif de la Partie 1
☞ À retenir
Dénition en 1 phrase
Concept
Apprendre les règles à partir de données, pas les coder
Machine Learning
Performance P sur la tâche T s'améliore avec l'expérience
Dénition Mitchell E
☞ À retenir
Dénition en 1 phrase
Concept
Apprend une formule, jette les données. Ex : rég. lin.
Model-Based
Mémorise tout, compare. KNN = seul du cours
Instance-Based
Shallow = tabulaire (ce cours). Deep = images/texte
Shallow vs Deep
Apprendre θ (1 fois, lent, coûteux)
Training
Prédire ŷ = fθ (x) (continu, rapide, ms)
Scoring
Pause 10 minutes
20252026
Pensez à un tableau Excel. Chaque ligne est un exemple. Chaque colonne est une mesure.
Pensez à un tableau Excel. Chaque ligne est un exemple. Chaque colonne est une mesure.
Les algorithmes ML travaillent avec des nombres. Si une colonne contient du texte (Rabat,
Oujda), il faut d'abord la convertir en nombres. Le type de feature détermine comment
la convertir.
Les algorithmes ML travaillent avec des nombres. Si une colonne contient du texte (Rabat,
Oujda), il faut d'abord la convertir en nombres. Le type de feature détermine comment
la convertir.
Elles sont universelles : utilisées dans les livres, articles et bibliothèques (scikit-learn, Ten-
sorFlow). Les maîtriser permet de lire n'importe quelle ressource ML.
Lecture : Le patient 1 a glucose = 148, pression = 72, âge = 50, IMC = 33.6, et est diabétique
(y1 = 1).
La diérence entre ŷi = fθ (xi ) et yi est mesurée par une fonction de perte L.
θ = (w1 , . . . , wd )
θ ∗ = arg min L fθ (X ), y
θ
θ = (w1 , . . . , wd )
θ ∗ = arg min L fθ (X ), y
θ
À retenir
1 Colonnes inutiles : ID et Nom sont des identiants, pas des features prédictives. Le
nom d'un patient ne prédit pas le diabète ! → Supprimer.
2 Valeur manquante (NaN) : l'âge de Samir est vide → Imputer (ex : médiane).
3 Valeur manquante : le glucose de Ibrahim est vide → Imputer.
4 Valeur aberrante (outlier) : glucose de Sara = 999. Le glucose humain ne dépasse pas
∼ 500 mg/dL. C'est probablement une erreur de saisie. → Remplacer par NaN puis
imputer.
ID et Nom supprimés. NaN imputés. Outlier corrigé. Doublon supprimé. Ville → One-Hot (2 colonnes).
Label → 0/1. Âge et Glucose → Z-score.
Attention
Règle critique : calculer la moyenne/médiane sur le train uniquement, puis appliquer la même
transformation au test. Sinon ⇒ data leakage (les statistiques du test inuencent le modèle).
One-Hot Encoding
Chaque catégorie → une colonne binaire.
Rabat 1 0 0
Oujda 0 1 0
Tanger 0 0 1
Rabat 1 0 0 Bac 0
Oujda 0 1 0 Licence 1
Tanger 0 0 1 Master 2
Doctorat 3
✓ Aucun ordre articiel
✗ K catégories → K colonnes (coût mémoire si ✓ Compact (1 colonne)
K grand) ✗ Introduit un ordre numérique (interprété par
Utiliser pour : ville, couleur, type de véhicule certains modèles)
Utiliser uniquement pour : variables ordinales
(Bac < Licence < Master)
Pr. ADDOU ML Séance 1 Partie 2 15/35
Étape 2 : Encodage des catégories
One-Hot Encoding Encodage ordinal (Label Encoding)
Chaque catégorie → une colonne binaire. Chaque catégorie → un entier.
Rabat 1 0 0 Bac 0
Oujda 0 1 0 Licence 1
Tanger 0 0 1 Master 2
Doctorat 3
Attention
Si vous appliquez cet encodage à ville : Rabat=0, Oujda=1, Tanger=2. Certains modèles interprètent
cela comme Tanger > Oujda > Rabat, ce qui est incorrect.
Cas dicile : catégorie non ordinale avec grand K
⇒ One-Hot trop grand, Label incorrect
⇒ utiliser Target Encoding ou Embeddings
Si une feature varie de 0 à 100 (âge) et une autre de 0 à 200 000 (revenu), les algorithmes
basés sur des distances seront dominés par les variables de grande échelle.
Si une feature varie de 0 à 100 (âge) et une autre de 0 à 200 000 (revenu), les algorithmes
basés sur des distances seront dominés par les variables de grande échelle.
Distance
s entre Patient A et Patient B : √
d= (50 − 45)2 + (80000 − 20000)2 = 25 + 3.6 × 109 ≈ 60 000
| {z } | {z }
âge revenu
L'âge contribue 25, le revenu contribue 3.6 × 109 . L'âge est négligeable !
Après
pZ-score (features centrées-réduites) :√
d= (0.5 − (−0.3))2 + (1.2 − (−0.8))2 = 0.64 + 4 = 2.15
Les deux features contribuent de manière comparable.
Arbre de décision ✗ Pas nécessaire Basé sur des seuils, invariant à l'échelle
Naïve Bayes ✗ Pas nécessaire Dépend des distributions, pas des dis-
Pr. ADDOU tances
ML Séance 1 Partie 2 19/35
ML Pipeline les 5 étapes d'un projet
1. Collecte : extraire les données de 200 000 clients (durée d'abonnement, consommation data/appels,
nombre de réclamations, type de forfait, 15 features au total).
2. Prétraitement : séparation train/test, 3% de NaN imputés (médiane sur le train), forfait → One-Hot (3
colonnes), consommation → Z-score, suppression de la colonne nom du client.
3. Modélisation : tester 3 algorithmes Régression Logistique, Random Forest, XGBoost. Comparer avec la
baseline jamais de churn (accuracy = 92%, rappel churn = 0%).
4. Évaluation : XGBoost gagne avec F1_churn = 0.61 (vs 0.52 RF, 0.45 LogReg) sur le jeu de validation.
Test nal : F1 = 0.58 (cohérent, pas d'overtting).
5. Déploiement : API interne. Chaque semaine, le modèle identie les clients à plus haut risque. Les
commerciaux les contactent avec une ore de rétention.
Résultat : churn réduit de 8% à 5.5% en 6 mois ⇒ ∼5 000 clients retenus.
Si vous évaluez votre modèle sur les mêmes données qu'il a utilisées pour apprendre, que
se passe-t-il ? (Pensez à l'analogie de l'examen.)
Si vous évaluez votre modèle sur les mêmes données qu'il a utilisées pour apprendre, que
se passe-t-il ? (Pensez à l'analogie de l'examen.)
Réponse : c'est comme passer un examen en ayant les réponses sous les yeux. Même un
modèle qui a mémorisé (sans généraliser) peut obtenir 100%.
Si vous évaluez votre modèle sur les mêmes données qu'il a utilisées pour apprendre, que
se passe-t-il ? (Pensez à l'analogie de l'examen.)
Réponse : c'est comme passer un examen en ayant les réponses sous les yeux. Même un
modèle qui a mémorisé (sans généraliser) peut obtenir 100%.
Si vous évaluez votre modèle sur les mêmes données qu'il a utilisées pour apprendre, que
se passe-t-il ? (Pensez à l'analogie de l'examen.)
Réponse : c'est comme passer un examen en ayant les réponses sous les yeux. Même un
modèle qui a mémorisé (sans généraliser) peut obtenir 100%.
☞ À retenir
1 Le test set ne sert qu'une seule fois, à la toute n. Si vous l'utilisez pour ajuster quoi
que ce soit, il devient un 2ème validation set et l'estimation est biaisée.
2 Séparer avant tout prétraitement. Sinon les statistiques du test fuient dans le train
(data leakage).
3 Pour les classes déséquilibrées (ex : 8% de churn), utiliser un split stratié : conserver
la même proportion (8/92%) dans chaque ensemble.
☞ À retenir
1 Le test set ne sert qu'une seule fois, à la toute n. Si vous l'utilisez pour ajuster quoi
que ce soit, il devient un 2ème validation set et l'estimation est biaisée.
2 Séparer avant tout prétraitement. Sinon les statistiques du test fuient dans le train
(data leakage).
3 Pour les classes déséquilibrées (ex : 8% de churn), utiliser un split stratié : conserver
la même proportion (8/92%) dans chaque ensemble.
200k clients, 8% churn (16k). Si le split est aléatoire, le test set pourrait contenir, par hasard, 2%
de churn au lieu de 8%. Les résultats seraient non représentatifs.
≈ 8% de churn.
Avec stratication : chaque ensemble contient
En Python : train_test_split(X, y, test_size=0.2, stratify=y)
En machine learning, une baseline est un algorithme simple utilisé comme point de compara-
ison. Elle peut être basée sur :
du hasard (random),
En machine learning, une baseline est un algorithme simple utilisé comme point de compara-
ison. Elle peut être basée sur :
du hasard (random),
La baseline fournit une référence minimale. Tout modèle plus avancé doit faire mieux que
cette performance.
Sans baseline, vous ne savez pas si votre modèle est bon ou mauvais. 90% d'accuracy
semble bien... mais si la baseline fait déjà 95%, votre modèle est moins performant.
Conguration :
Distance standard (euclidienne)
Performance :
Accuracy = 82%
F1-score = 0.78
Conguration : Principe :
Distance standard (euclidienne) Variante du KNN
Conguration : Principe :
Distance standard (euclidienne) Variante du KNN
Conclusion
Conguration : Principe :
Distance standard (euclidienne) Variante du KNN
Conclusion
Une baseline peut être simple, mais elle est indispensable : elle dénit le niveau minimum à battre
pour justier un modèle plus complexe.
10 millions de transactions par an. 0.01% sont des fraudes = 1 000 fraudes.
10 millions de transactions par an. 0.01% sont des fraudes = 1 000 fraudes.
À retenir
L'accuracyseule est trompeuse lorsque les classes sont déséquilibrées. Toujours analyser le rappel, le
F1-score et l'AUC-ROC.
Dans une régression linéaire ŷ = w1 x1 + w2 x2 + b, les poids w1 , w2 , b sont-ils choisis par vous
ou par l'algorithme ?
Dans une régression linéaire ŷ = w1 x1 + w2 x2 + b, les poids w1 , w2 , b sont-ils choisis par vous
ou par l'algorithme ?
Centroïdes µk (K-Means)
Dans une régression linéaire ŷ = w1 x1 + w2 x2 + b, les poids w1 , w2 , b sont-ils choisis par vous
ou par l'algorithme ?
☞ À retenir
Paramètres θ Hyperparamètres
Qui décide ? algorithme (automatique)
L' L'utilisateur
Quand ? Pendant l'entraînement Avant l'entraînement
Comment les choisir ? Par optimisation (minimisation de Par recherche (Grid Search, CV)
la perte)
Arbre de décision Seuils de split à chaque n÷ud Profondeur max, min samples
Random Forest Paramètres des arbres (seuils, structures) Nombre d'arbres, profondeur max
Arbre de décision Seuils de split à chaque n÷ud Profondeur max, min samples
Random Forest Paramètres des arbres (seuils, structures) Nombre d'arbres, profondeur max
☞ À retenir
Cas spécial KNN : c'est le seul algo du cours qui n'apprend aucun paramètre. Il stocke les données
(instance-based). Son hyperparamètre principal est k.
Pr. ADDOU ML Séance 1 Partie 2 30/35
Récapitulatif de la Partie 2
☞ À retenir
Dénition en 1 phrase
Concept
Tableau : lignes = exemples, colonnes = features (utilisées
Données tabulaires dans ce cours)
☞ À retenir
Dénition en 1 phrase
Concept
Collecte → Prétraitement → Modélisation → Évaluation
Pipeline → Déploiement
Pause 10 minutes
20252026
Risque réel R(f ) ce qu'on veut Risque empirique R̂(f ) ce qu'on peut
minimiser calculer
n
R(f ) = E(x,y )∼D L(f (x), y ) 1 X
R̂(f ) = L(f (xi ), yi )
L'erreur sur toutes les données possibles n
i=1
(passées, présentes et futures).
L'erreur moyenne sur nos n exemples
Problème : on ne connaît pas la distribution D, d'entraînement.
donc R(f ) est impossible à calculer
directement.
Avantage : on le calcule facilement. C'est en
général ce que l'apprentissage cherche à
minimiser.
Risque réel R(f ) ce qu'on veut Risque empirique R̂(f ) ce qu'on peut
minimiser calculer
n
R(f ) = E(x,y )∼D L(f (x), y ) 1 X
R̂(f ) = L(f (xi ), yi )
L'erreur sur toutes les données possibles n
i=1
(passées, présentes et futures).
L'erreur moyenne sur nos n exemples
Problème : on ne connaît pas la distribution D, d'entraînement.
donc R(f ) est impossible à calculer
directement.
Avantage : on le calcule facilement. C'est en
général ce que l'apprentissage cherche à
minimiser.
Le piège : minimiser R̂ (erreur sur le train) ne garantit pas de minimiser R (erreur réelle). Un
modèle peut avoir R̂ ≈ 0 mais R très élevé. C'est l'overtting.
Cas 1 Comprend (R ≈ R̂ ) : l'étudiant comprend les méthodes. Il réussit les annales (R̂ faible)
ET l'examen (R faible). Il généralise.
Risque empirique vs réel l'analogie de l'examen
Cas 3 N'étudie pas (R̂ et R élevés) : l'étudiant n'a même pas regardé les annales. Il échoue
partout. C'est l'undertting.
☞ À retenir
L'objectif du ML n'est pas zéro erreur sur le train, mais de généraliser : bien prédire sur des données
jamais vues.
Ligne horizontale
Overtting vs Undertting illustration visuelle
Degré 0 Trop simple Degré 1 Juste bien Degré élevé Trop complexe
★ Règle de diagnostic
Un premier diagnostic consiste à comparer l'erreur sur le train et l'erreur sur le test.
C'est l'écart entre la prédiction moyenne du modèle (sur tous les échantillons possibles) et
la vraie valeur. Si le biais est élevé, le modèle se trompe systématiquement.
C'est l'écart entre la prédiction moyenne du modèle (sur tous les échantillons possibles) et
la vraie valeur. Si le biais est élevé, le modèle se trompe systématiquement.
☞ À retenir
On ne peut pas réduire σ 2 simplement en changeant d'algorithme. Pour le diminuer, il faut surtout
améliorer l'information disponible : meilleures variables, meilleures mesures, moins d'erreurs de
mesure. C'est le plancher de l'erreur.
Hypothèses
On xe un point x et les données suivent : y = f (x) + ε où f est la vraie fonction (inconnue)
Théorème à démontrer :
2
E (y − fˆ(x))2 = f (x) − E[fˆ(x)] + E (fˆ(x) − E[fˆ(x)])2 + |{z}
σ2
Bruit
| {z } | {z }
Biais2 Variance
1) Linéarité de l'espérance
Pour toutes constantes a, b, c ∈ R :
E (aX + b) = aE (X ) + b
Plus généralement :
E (aX + bY + c) = aE (X ) + bE (Y ) + c
Cas particuliers :
E (X + Y ) = E (X ) + E (Y ), E (X − Y ) = E (X ) − E (Y )
E (c) = c, E (cX ) = cE (X )
On part de : E[(y − fˆ(x))2 ]. Pour alléger les notations, on écrira simplement fˆ au lieu de
fˆ(x) et f au lieu de f (x).
Remplaçons y par f +ε :
E[(y − fˆ)2 ] = E[(f + ε − fˆ)2 ]
Réorganisons en regroupant (f − fˆ) ensemble :
ε )2
− f}ˆ + |{z}
= E (f| {z
a b
Donc :
E[(f − fˆ) ε] = E[f − fˆ] · E[ε] =0
|{z}
=0 (hypothèse)
Et le dernier terme :
E[ε2 ] = Var(ε) + (E[ε])2 = σ 2 + 0 = σ 2
f − fˆ = (f − µ) + (µ − fˆ)
| {z } | {z }
terme déterministe terme aléatoire
Développons le carré :
E[(f − fˆ)2 ] = E ((f − µ) + (µ − fˆ))2
Théorème démontré :
σ2 Bruit dans les données Données bruitées ✗ Non (pas via le modèle seul)
Lecture de la courbe :
Biais
2
À gauche (modèle simple) : le biais
domine →
Variance
Undertting Overtting
Erreur totale
undertting
σ2 À droite (modèle complexe) : la
Erreur
Undertting Overtting
Erreur
Zone optimale
Complexité du modèle
☞ À retenir
À retenir :
Modèle trop simple → biais élevé → undertting
★ La question pratique
Mon modèle ne marche pas. J'ai diagnostiqué le problème (biais ou variance). Comment
corriger concrètement ?
☞ À retenir
Workow de diagnostic en 3 étapes :
1. Calculer erreur train et erreur test.
2. Grand écart train/test → variance → colonne droite du tableau.
3. Erreur train élevée en absolu → biais → colonne gauche du tableau.
Erreur
Nb exemples Nb exemples
Signe : les 2 courbes convergent haut. Signe : grand écart entre train et validation.
Ajouter des données aide peu. Ajouter des données peut aider.
→ Modèle + complexe ou + features. → Régularisation ou modèle + simple.
Pr. ADDOU ML Séance 1 Partie 3 25/32
Courbes d'apprentissage comment les lire en pratique
☞ À retenir
En Python, vous pouvez tracer ces courbes avec sklearn.model_selection.learning_curve.
C'est l'un des premiers réexes à avoir quand un modèle ne marche pas.
1 Pn
Risque empirique R̂(f ) = n i=1 L(f (xi ), yi )
x−xmin
Min-Max x′ = xmax −xmin ∈ [0, 1]
x−µ
Z-score x′ = σ (moyenne=0, écart-type=1)
☞ À retenir
20252026
Objectif : comprendre le modèle de régression linéaire, sa fonction de coût, ses méthodes d'optimisation
et ses extensions.
★ Petit test
Quelle est la diérence entre régression et classication ?
★ Petit test
Quelle est la diérence entre régression et classication ?
★ Petit test
Quelle est la diérence entre régression et classication ?
☞ À retenir
La régression linéaire est le modèle fondamental du Machine Learning supervisé :
elle introduit la notion de modèle paramétrique (w , b),
elle permet de comprendre la fonction de coût et l'optimisation,
elle constitue la base de nombreux modèles plus avancés.
★ Mise en situation
Vous êtes agent immobilier. Un client vous demande : Mon appartement fait 85 m2 .
Combien vaut-il ? Vous disposez des données de 5 ventes récentes. Comment estimer ce
prix ?
(m2 ) (k$)
40 80
Prix (k$)
200
60 130
80 165
100 210 100
120 250
Objectif : estimer le prix correspondant à une 20 40 60 80 100 120 140
m2 .
2
Surface (m )
surface de 85
(m2 ) (k$)
40 80
Prix (k$)
200
60 130
80 165
100 210 100
120 250
Objectif : estimer le prix correspondant à une 20 40 60 80 100 120 140
2
surface de 85 m .
2
Surface (m )
☞ À retenir
La valeur cherchée pour x= 85 n'est pas observée dans les données : c'est une prédiction. Le but
de la régression est d'apprendre une fonction permettant de prédire une valeur numérique à partir
de données observées.
Observation : les points semblent suivre une tendance linéaire (quand la surface augmente,
le prix augmente proportionnellement).
Idée : trouver la droite qui passe au plus près de tous les points. Ensuite, pour 85 m2 , on lit
simplement le prix sur cette droite.
300
Prix (k$)
200
≈ 180 k$
100
Observation : les points semblent suivre une tendance linéaire (quand la surface augmente,
le prix augmente proportionnellement).
Idée : trouver la droite qui passe au plus près de tous les points. Ensuite, pour 85 m2 , on lit
simplement le prix sur cette droite.
300
Prix (k$)
200
≈ 180 k$
100
☞ À retenir
La régression linéaire cherche la droite ŷ = wx + b qui passe au plus près de tous les points. Le plus
près sera déni mathématiquement par la fonction de coût.
Pr. ADDOU ML S2 Régression linéaire (1/3) 7/46
Le modèle : ŷ = wx + b
ŷ = wx + b
x : variable explicative (ex : surface en m2 )
ŷ : valeur prédite (ex : prix estimé)
w pente de la droite
: poids =
ŷ = wx + b
x : variable explicative (ex : surface en m2 )
ŷ : valeur prédite (ex : prix estimé)
w pente de la droite
: poids =
★ Interprétation intuitive
w mesure combien ŷ change quand x augmente de 1 unité.
Exemple : si w = 2.1, chaque m2 supplémentaire augmente le prix prédit de 2.1 k$.
Eet de w (pente) :
w = 0.5 (pente faible)
10 w = 2 (pente forte)
w = −1 (pente négative)
5
ŷ
0 1 2 3 4 5
x
5
ŷ
ŷ
5
0 0
0 1 2 3 4 5 0 1 2 3 4 5
x x
5
ŷ
ŷ
5
0 0
0 1 2 3 4 5 0 1 2 3 4 5
x x
☞ À retenir
Dans le modèle ŷ = wx + b , le paramètre w contrôle l'inclinaison de la droite, tandis que b contrôle
sa position verticale.
Pr. ADDOU ML S2 Régression linéaire (1/3) 9/46
w et b sont les paramètres du modèle
☞ À retenir
w et b sont les paramètres du modèle : ce sont les quantités que l'algorithme doit apprendre
automatiquement à partir des données.
L'objectif est de trouver les valeurs de w et b pour lesquelles la droite ŷ = wx + b approxime
au mieux les points observés.
La question centrale est donc : comment mesurer mathématiquement la qualité d'une
droite ?
★ Rééchissez
Regardez ces deux droites. Laquelle semble meilleure ? Comment le quantier de manière
objective ?
Droite B
Prix (k$)
Droite A
2
Surface (m )
★ Rééchissez
Regardez ces deux droites. Laquelle semble meilleure ? Comment le quantier de manière
objective ?
Droite B
Prix (k$)
Droite A
2
Surface (m )
☞ À retenir
Pour comparer plusieurs droites candidates, on a besoin d'une mesure quantitative de l'erreur. La
plus classique en régression linéaire est la somme des erreurs au carré, qui conduit à la fonction
de coût.
ei = yi − ŷi = yi − (wxi + b)
Un résidu est :
Résidu
Pour un point (xi , yi ), le résidu est : ei = yi − ŷi
200
Prix (k$)
e4 e5
e2 e3
100
e1
☞ À retenir
Cette droite est très mauvaise : les résidus sont globalement très grands.
Résidu
Pour un point (xi , yi ), le résidu est : ei = yi − ŷi
e4 e5
200
Prix (k$) e3
e2
100
e1
☞ À retenir
Cette droite est meilleure, mais plusieurs résidus restent encore importants.
Résidu
Pour un point (xi , yi ), le résidu est : ei = yi − ŷi
e4 e5
200
Prix (k$)
e3
e2
100
e1
☞ À retenir
meilleure droite possible pour ce nuage.
Cette droite est la Mais comme les données ne sont pas
parfaitement linéaires, les résidus restent encore visibles.
Pr. ADDOU ML S2 Régression linéaire (1/3) 15/46
L'erreur de prédiction pour un point
e4 e5
200
Prix (k$)
e3
e2
100
e1
☞ À retenir
Une bonne droite de régression est une droite dont les résidus sont globalement petits. Il faut
maintenant dénir une manière de combiner toutes les erreurs en une seule quantité.
★ Question piège
P
Si on additionne tous les résidus i ei , peut-on obtenir 0 même si la droite est mauvaise ?
Réponse : oui. Les résidus positifs et négatifs peuvent se compenser même si les erreurs
sont importantes.
Exemple : piège de la somme simple Idée correcte : utiliser les carrés des résidus :
(− 2 2 (30)2 = 900
Considérons 3 points et une droite donnée : P330) 2= 900, 0 = 0,
(yi − ŷi )2 Le carré du résidu pour le point i . Cette quantité est toujours ≥ 0.
1 Pn
i=1 La moyenne des erreurs quadratiques sur l'ensemble des n exemples.
n
(yi − ŷi )2 Le carré du résidu pour le point i . Cette quantité est toujours ≥ 0.
1 Pn
i=1 La moyenne des erreurs quadratiques sur l'ensemble des n exemples.
n
☞ À retenir
le carré des erreurs permet à la fois de mieux punir les grandes erreurs et de faciliter
l'optimisation.
Pr. ADDOU ML S2 Régression linéaire (1/3) 18/46
MSE : Mean Squared Error fonction de coût de la régression linéaire
☞ À retenir
Objectif de la régression linéaire : trouver les paramètres optimaux w∗ et b∗ qui minimisent la
fonction de coût :
n
1
(yi − (wxi + b))2
X
(w ∗ , b ∗ ) = arg min J(w , b) = arg min
w ,b w ,b n
i=1
☞ À retenir
La fonction de coût transforme la qualité d'une droite en une valeur numérique unique. Le problème
d'apprentissage devient alors un problème d'optimisation.
J(w , b)
le cas de la régression 10
☞ À retenir
En régression linéaire, minimiser la MSE revient à
15
chercher le point le plus bas d'une surface convexe.
J(w , b)
C'est cette propriété qui rend l'optimisation partic- 10
On a déni la fonction de coût J(w , b). Comment trouver les paramètres optimaux (w ∗ , b ∗ )
qui la minimisent ? Il existe deux grandes approches :
On a déni la fonction de coût J(w , b). Comment trouver les paramètres optimaux (w ∗ , b ∗ )
qui la minimisent ? Il existe deux grandes approches :
On a déni la fonction de coût J(w , b). Comment trouver les paramètres optimaux (w ∗ , b ∗ )
qui la minimisent ? Il existe deux grandes approches :
On a déni la fonction de coût J(w , b). Comment trouver les paramètres optimaux (w ∗ , b ∗ )
qui la minimisent ? Il existe deux grandes approches :
On a déni la fonction de coût J(w , b). Comment trouver les paramètres optimaux (w ∗ , b ∗ )
qui la minimisent ? Il existe deux grandes approches :
☞ À retenir
Ces deux approches poursuivent le même objectif : minimiser la fonction de coût. La diérence
est que l'une calcule directement la solution, tandis que l'autre l'approche progressivement.
Pour trouver le minimum de J(w , b), nous aurons besoin de calculer ses dérivées partielles,
puis d'étudier les points où elles s'annulent.
Pour trouver le minimum de J(w , b), nous aurons besoin de calculer ses dérivées partielles,
puis d'étudier les points où elles s'annulent.
Gradient :
∂f
! !
∂x 6x + 2y
∇f (x, y ) = ∂f
=
∂y 2x + 2y
∂f
= 2x + 2y
Le gradient regroupe toutes ces variations
∂y
et joue un rôle central dans les méthodes
car : 3x 2 7→ 0, 2xy 7→ 2x, y 2 7→ 2y d'optimisation.
Gradient :
∂f
! !
∂x 6x + 2y
∇f (x, y ) = ∂f
=
∂y 2x + 2y
☞ À retenir
Idée fondamentale : pour une fonction diérentiable, un point critique est un point où toutes les
dérivées partielles s'annulent :
∂J ∂J
=0 et =0
∂w ∂b
Si, en plus, la fonction J est convexe, alors tout point critique est un minimum global.
☞ À retenir
Idée fondamentale : pour une fonction diérentiable, un point critique est un point où toutes les
dérivées partielles s'annulent :
∂J ∂J
=0 et =0
∂w ∂b
Si, en plus, la fonction J est convexe, alors tout point critique est un minimum global.
Dans le cas de la régression linéaire avec MSE, la fonction de coût est convexe. Ainsi, résoudre
∇J = ⃗0
∂J ∂J
Pour chercher le minimum, on impose :
∂w =0 et
∂b =0
On obtient alors le système suivant :
Pn
i=1 xi (yi − wxi − b) = 0 (1)
Pn
i=1 (yi − wxi − b) = 0 (2)
∂J ∂J
Pour chercher le minimum, on impose :
∂w =0 et
∂b =0
On obtient alors le système suivant :
Pn
i=1 xi (yi − wxi − b) = 0 (1)
Pn
i=1 (yi − wxi − b) = 0 (2)
☞ À retenir
La minimisation de la MSE se ramène à la résolution d'un système de deux équations à deux inconnues
: w et b.
Pr. ADDOU ML S2 Régression linéaire (1/3) 29/46
Résolution du système : trouver w∗ et b∗
À partir de l'équation (2) :
Pn Pn
i=1 yi −w i=1 xi − nb = 0
☞ À retenir
Ces formules donnent directement les paramètres optimaux du modèle de régression linéaire simple.
Aucune itération n'est nécessaire : la solution est obtenue par calcul direct.
Pr. ADDOU ML S2 Régression linéaire (1/3) 30/46
L'équation normale en notation matricielle
Pour la régression linéaire multiple, le modèle peut s'écrire sous forme matricielle :
ŷ = Xθ
θ ∗ = (X T X )−1 X T y
Remarque importante : si l'on inclut le biais b dans θ, alors la matrice X doit contenir une colonne
de 1.
Limites :
Limites :
✗ Le calcul de (X T X )−1 peut devenir coûteux lorsque le nombre de variables est grand
T
✗ La matrice X X peut être singulière (non inversible)
✗ Cette approche n'est pas adaptée aux grands problèmes ou à certains modèles plus complexes
Limites :
✗ Le calcul de (X T X )−1 peut devenir coûteux lorsque le nombre de variables est grand
T
✗ La matrice X X peut être singulière (non inversible)
✗ Cette approche n'est pas adaptée aux grands problèmes ou à certains modèles plus complexes
En pratique, l'équation normale est surtout utile pour des problèmes de taille modérée. Pour les
problèmes de grande dimension, on préfère souvent des méthodes itératives comme la descente de
gradient.
☞ À retenir
Le point (x̄, ȳ ) = (80, 167) est le centre de gravité empirique du nuage de points. Dans la
régression linéaire simple avec biais, la droite de régression passe toujours par ce point.
Pn
∗ 1 (xi − x̄)(yi − ȳ ) 8400
w = i=P n 2
= = 2.1
i=1 (xi − x̄) 4000
☞ À retenir
Le coecient w ∗ = 2.1 signie que, selon le modèle appris, une augmentation de 1 m2 est associée
à une augmentation moyenne prédite de 2.1 k$ du prix.
Pr. ADDOU ML S2 Régression linéaire (1/3) 34/46
Exemple complet étape 3 : calculer b∗ et prédire
Étape 3 : calculer b∗
b ∗ = ȳ − w ∗ x̄ = 167 − 2.1 × 80 = 167 − 168 = −1
Le modèle nal obtenu est donc :
ŷ = 2.1x − 1
Étape 4 : prédire le prix pour 85 m2
ŷ (85) = 2.1 × 85 − 1 = 178.5 − 1 = 177.5 (k$)
☞ À retenir
Vérication importante : la droite de régression passe bien par le point moyen (x̄, ȳ ) = (80, 167)
En eet : ŷ (80) = 2.1 × 80 − 1 = 167
C'est une propriété fondamentale de la régression linéaire simple avec biais.
Le fait que le MSE optimal soit non nul signie simplement que les données ne sont pas parfaitement
alignées sur une droite. Il reste donc une erreur de modélisation / approximation, qui peut provenir
:
Le fait que le MSE optimal soit non nul signie simplement que les données ne sont pas parfaitement
alignées sur une droite. Il reste donc une erreur de modélisation / approximation, qui peut provenir
:
☞ À retenir
Minimiser le MSE ne signie pas rendre l'erreur nulle, mais trouver la meilleure droite possible
parmi toutes les droites candidates selon ce critère.
3 Calculer b∗ = ȳ − w ∗ x̄.
4 Écrire le modèle de régression obtenu : ŷ = w ∗ x + b∗ .
5 Prédire la note d'un étudiant qui étudie 5 heures.
6 Calculer le MSE du modèle et interpréter sa valeur.
7 Selon le modèle, quelle serait la note prédite pour un étudiant qui n'étudie pas du tout (x = 0) ?
Cette prédiction a-t-elle un sens en pratique ?
Pr. ADDOU ML S2 Régression linéaire (1/3) 38/46
✓ Solution Exercice 1 solution (1/2)
1. Calcul des moyennes empiriques
2+4+6+8 6 + 10 + 13 + 17
x̄ = = 5, ȳ = = 11.5
4 4
2. Calcul de w ∗
xi yi xi − x̄ yi − ȳ (xi − x̄)(yi − ȳ )
2 6 −3 −5.5 16.5
4 10 −1 −1.5 1.5
6 13 1 1.5 1.5 Interprétation : selon le modèle, une heure d'étude
8 17 3 5.5 16.5 supplémentaire est associée à une augmentation
moyenne prédite de 1.8 point.
Somme : 36
3. Calcul de b∗
4 b ∗ = ȳ − w ∗ x̄ = 11.5 − 1.8 × 5 = 11.5 − 9 = 2.5
(xi − x̄)2 = 9 + 1 + 1 + 9 = 20
X
6. Calcul du MSE
☞ À retenir
Un modèle de régression est able principalement dans le domaine des données d'entraînement.
L'extrapolation peut conduire à des prédictions peu réalistes.
est multiplié par 2, tandis que le dénominateur reste inchangé, donc w ∗ est multiplié par 2.
Pr. ADDOU ML S2 Régression linéaire (1/3) 43/46
Récapitulatif de la Partie 1
☞ À retenir
Idée essentielle
Concept
ŷ = wx + b . Le modèle approxime la relation entre une
Modèle linéaire variable explicative x et une variable cible y.
Ce sont les paramètres appris à partir des données. w
w et b contrôle la pente, b la position verticale de la droite.
MSE 1
n
(yi − wxi − b)2
X
J(w , b) =
n
i=1
☞ À retenir
Idée essentielle
Concept
Pour empêcher l'annulation entre résidus positifs et négat-
Pourquoi le carré ifs, et pénaliser davantage les grandes erreurs.
Solution analytique
P
∗ (xi − x̄)(yi − ȳ )
w = , b ∗ = ȳ − w ∗ x̄
(xi − x̄)2
P
Pause : 10 minutes
20252026
★ Rappel de la Partie 1
On a trouvé une formule exacte pour la régression linéaire.
Dans le cas simple (à une seule variable) :
P
∗ (xi − x̄)(yi − ȳ )
w = , b ∗ = ȳ − w ∗ x̄
(xi − x̄)2
P
θ ∗ = (X T X )−1 X T y
Quand l'utiliser Régression linéaire avec dimen- Quand la dimension est grande
sion modérée ou qu'il n'existe pas de solution
analytique fermée
3 Répéter jusqu'à ce que la pente devienne très faible → c'est l'idée de la convergence
3 Répéter jusqu'à ce que la pente devienne très faible → c'est l'idée de la convergence
☞ À retenir
Le gradient ∇J pointe vers la direction de la plus forte augmentation locale de J. Pour faire
diminuer J, on avance dans la direction opposée, d'où la mise à jour :
θ ← θ − α∇J
★ Idée centrale
On veut minimiser une fonction de coût J(θ).
min J(θ)
θ
La question est :si on est au point courant θ, dans quelle direction faut-il bouger
pour faire diminuer J ?
★ Idée centrale
On veut minimiser une fonction de coût J(θ).
min J(θ)
θ
La question est :si on est au point courant θ, dans quelle direction faut-il bouger
pour faire diminuer J ?
☞ À retenir
La règle
θ ← θ − α∇J(θ)
n'est pas choisie au hasard : elle vient d'une approximation locale de la fonction J .
★ Question fondamentale
La règle de mise à jour
θ ← θ − α∇J(θ)
est au c÷ur de toute la descente de gradient.
Mais d'où vient-elle ?
★ Question fondamentale
La règle de mise à jour
θ ← θ − α∇J(θ)
est au c÷ur de toute la descente de gradient.
Mais d'où vient-elle ?
★ Question fondamentale
La règle de mise à jour
θ ← θ − α∇J(θ)
est au c÷ur de toute la descente de gradient.
Mais d'où vient-elle ?
☞ À retenir
Cette formule vient d'une idée simple : faire un petit déplacement local qui fait diminuer J le
plus possible.
θnouveau = θ + ∆
θnouveau = θ + ∆
Question
Comment choisir le petit déplacement ∆ pour que
θnouveau = θ + ∆
Question
Comment choisir le petit déplacement ∆ pour que
Math Conséquence
P
∇J(θ)T ∆ < 0
Math Conséquence
P
∇J(θ)T ∆ < 0
☞ À retenir
Le gradient ∇J(θ) contient l'information locale sur la variation de J autour du point courant.
★ Résultat clé
Parmi tous les vecteurs ∆ de même norme, celui qui rend
∇J(θ)T ∆
le plus petit est celui qui pointe dans la direction opposée au gradient :
∆ ∝ −∇J(θ)
★ Résultat clé
Parmi tous les vecteurs ∆ de même norme, celui qui rend
∇J(θ)T ∆
le plus petit est celui qui pointe dans la direction opposée au gradient :
∆ ∝ −∇J(θ)
Conclusion :
∇J(θ) = direction de la plus forte augmentation locale
−∇J(θ) = direction de la plus forte diminution locale
★ Point clé
Si on xe la taille du déplacement ∥∆∥, alors le terme
∇J(θ)T ∆
★ Point clé
Si on xe la taille du déplacement ∥∆∥, alors le terme
∇J(θ)T ∆
∆ ∝ −∇J(θ)
★ Point clé
Si on xe la taille du déplacement ∥∆∥, alors le terme
∇J(θ)T ∆
∆ ∝ −∇J(θ)
☞ À retenir
Le gradient pointe vers la plus forte augmentation locale de J . La direction opposée donne la plus
forte diminution locale.
Pr. ADDOU ML S2 Descente de gradient 12/50
Que signie ∆ ∝ −∇J(θ)?
Notation
∆ ∝ −∇J(θ)
signie que le vecteur ∆ a la même direction que −∇J(θ).
∆ = −α∇J(θ)
∆ = −α∇J(θ)
Exemple : Interprétation
−∇J(θ) donne la direction
α donne la taille du pas
∆ = −α∇J(θ)
Exemple : Interprétation
−∇J(θ) donne la direction
α donne la taille du pas
En remplaçant dans
θnouveau = θ + ∆
on obtient :
θnouveau = θ − α∇J(θ)
Pr. ADDOU ML S2 Descente de gradient 13/50
Pourquoi le signe moins ?
Lecture :
10
∇J montée
pointe vers la
−∇J
+∇J ⇒ monter
0
−1 0 1 2 3 4 5 6
−∇J ⇒ descendre
w
Exemple : Si w = 0
J ′ (0) = 2(0 − 3) = −6
Donc :
w ← w − α(−6) = w + 6α
Le paramètre augmente : on va vers la droite, donc vers le minimum w ∗ = 3.
J ′ (5) = 2(5 − 3) = 4
Donc :
w ← w − 4α
Le paramètre diminue : on va vers la gauche, donc encore vers le minimum.
J ′ (5) = 2(5 − 3) = 4
Donc :
w ← w − 4α
Le paramètre diminue : on va vers la gauche, donc encore vers le minimum.
☞ À retenir
En une dimension :
si J ′ (w ) > 0, on diminue w
′
si J (w ) < 0, on augmente w
Pr. fait
La formule ADDOU
cela automatiquement. ML S2 Descente de gradient 16/50
Rôle du learning rate α
Savoir la direction ne sut pas. Il faut aussi choisir combien avancer.
On note cette taille par α > 0.
On prend donc :
∆ = −α∇J(θ)
☞ À retenir
θ ← θ − α∇J(θ)
C'est la règle de la descente de gradient.
Le gradient donne la direction. Le learning rate α xe la longueur du pas.
☞ À retenir
1 On veut minimiser J(θ)
2 On fait un petit déplacement ∆
3 Localement :
J(θ + ∆) ≈ J(θ) + ∇J(θ)T ∆
4 Pour faire baisser J, on choisit la direction opposée au gradient
☞ À retenir
1 On veut minimiser J(θ)
2 On fait un petit déplacement ∆
3 Localement :
J(θ + ∆) ≈ J(θ) + ∇J(θ)T ∆
4 Pour faire baisser J, on choisit la direction opposée au gradient
★ Phrase à retenir
Le gradient indique la direction de plus forte augmentation locale de la fonction de coût.
Pour la faire diminuer, on se déplace donc dans la direction opposée, avec un pas de taille α.
∂J ∂J
Pour la descente de gradient, on a besoin de calculer
∂w et ∂b .
∂J ∂J
Pour la descente de gradient, on a besoin de calculer
∂w et ∂b .
∂J ∂J
Pour la descente de gradient, on a besoin de calculer
∂w et ∂b .
2
1
Étape 1 :
Pn
écrivons J en détail : J(w , b) = n i=1 yi − wxi − b
| {z }
ui
Dérivation de ∂J
∂w
pas à pas
2
1
Étape 1 :
Pn
écrivons J en détail : J(w , b) = n i=1 yi − wxi − b
| {z }
ui
1
Étape 2 : ui2
∂J Pn ∂
dérivons par rapport à w. Par linéarité de la dérivation :
∂w = n i=1 ∂w
Dérivation de ∂J
∂w
pas à pas
2
1
Étape 1 :
Pn
écrivons J en détail : J(w , b) = n i=1 yi − wxi − b
| {z }
ui
1
Étape 2 : ui2
∂J Pn ∂
dérivons par rapport à w. Par linéarité de la dérivation :
∂w = n i=1 ∂w
2
1
Étape 1 :
Pn
écrivons J en détail : J(w , b) = n i=1 yi − wxi − b
| {z }
ui
1
Étape 2 : ui2
∂J Pn ∂
dérivons par rapport à w. Par linéarité de la dérivation :
∂w = n i=1 ∂w
1 −2
Étape 4 : ∂J Pn Pn
on obtient :
∂w = n i=1 2(yi − wxi − b)(−xi ) = n i=1 xi (yi − wxi − b)
n
∂J 1 X ∂ui
= 2(yi − wxi − b) ·
∂b n ∂b
i=1 |{z}
=−1
∂ui
Car ui = yi − wxi − b , donc
∂b = −1.
Dérivation de ∂J
∂b
même méthode
n
∂J 1 X ∂ui
= 2(yi − wxi − b) ·
∂b n ∂b
i=1 |{z}
=−1
∂ui
Car ui = yi − wxi − b , donc
∂b = −1.
n
∂J −2 X
= (yi − wxi − b)
∂b n
i=1
☞ À retenir
Interprétation : ∂J ∂J
∂b dépend de la moyenne des erreurs, tandis que ∂w dépend d'une moyenne des
erreurs pondérées par les valeurs xi . La mise à jour θ ← θ − α∇J ajuste donc w et b dans la direction
qui fait diminuer la MSE.
Attention ! Les deux gradients doivent être calculés au même point courant (wt , bt ), puis
les paramètres sont mis à jour ensemble :
Attention ! Les deux gradients doivent être calculés au même point courant (wt , bt ), puis
les paramètres sont mis à jour ensemble :
✓ Correct : simultané
Attention ! Les deux gradients doivent être calculés au même point courant (wt , bt ), puis
les paramètres sont mis à jour ensemble :
Attention ! Les deux gradients doivent être calculés au même point courant (wt , bt ), puis
les paramètres sont mis à jour ensemble :
xi yi
1 2
2 3
ŷ1 = 0 × 1 + 0 = 0, ŷ2 = 0 × 2 + 0 = 0
ŷ1 = 0 × 1 + 0 = 0, ŷ2 = 0 × 2 + 0 = 0
Étape 2 : erreurs :
e1 = y1 − ŷ1 = 2 − 0 = 2, e2 = y2 − ŷ2 = 3 − 0 = 3
ŷ1 = 0 × 1 + 0 = 0, ŷ2 = 0 × 2 + 0 = 0
Étape 2 : erreurs :
e1 = y1 − ŷ1 = 2 − 0 = 2, e2 = y2 − ŷ2 = 3 − 0 = 3
Étape 3 : gradients :
2
∂J −2 X
× 2 + 2 × 3 = −(2 + 6) = -8
= xi ei = − 1
∂w 2
i=1
2
∂J −2 X
= ei = −(2 + 3) = -5
∂b 2
i=1
ŷ1 = 0 × 1 + 0 = 0, ŷ2 = 0 × 2 + 0 = 0
Étape 2 : erreurs :
e1 = y1 − ŷ1 = 2 − 0 = 2, e2 = y2 − ŷ2 = 3 − 0 = 3
Étape 3 : gradients :
2
∂J −2 X
× 2 + 2 × 3 = −(2 + 6) = -8
= xi ei = − 1
∂w 2
i=1
2
∂J −2 X
= ei = −(2 + 3) = -5
∂b 2
i=1
☞ À retenir
∂J ∂J
Au point initial (w0 , b0 ) = (0, 0), les deux gradients sont négatifs :
∂w = −8, ∂b = −5
J(w0 , b0 ) = 12 (22 + 32 ) = 13
2 = 6.5
J(w0 , b0 ) = 12 (22 + 32 ) = 13
2 = 6.5
☞ À retenir
J0 = 6.5 −→ J1 = 0.65 La fonction de coût a donc fortement diminué dès la première itération.
1 2
1
= 0.29 + 0.242 = (0.0841 + 0.0576) = 0.07085
2 2
1 2
1
= 0.29 + 0.242 = (0.0841 + 0.0576) = 0.07085
2 2
Itération (w , b) J(w , b)
0 (0, 0) 6.5
1 (0.8, 0.5) 0.65
2 (1.05, 0.66) 0.07085
1 2
1
= 0.29 + 0.242 = (0.0841 + 0.0576) = 0.07085
2 2
Itération (w , b) J(w , b)
0 (0, 0) 6.5
1 (0.8, 0.5) 0.65
2 (1.05, 0.66) 0.07085
☞ À retenir
On voit clairement que la descente de gradient fait diminuer la fonction de coût à chaque itération.
☞ À retenir
Cet exemple n'a pas été choisi pour être réaliste, mais pour être simple à calculer à la main.
L'objectif est de comprendre clairement le mécanisme de la descente de gradient avant de passer à
des cas plus grands.
★ Question cruciale
Que se passe-t-il concrètement quand α est trop petit, bien choisi, ou trop grand ? Regardons
les 3 cas.
Signes observables :
15
Beaucoup de petits pas
Signes observables :
15
Beaucoup de petits pas
Interprétation : si la courbe J en
fonction des itérations descend
régulièrement mais très lentement, on peut
essayer d'augmenter α.
Signes observables :
15
Pas assez grands pour progresser
10
ecacement, mais pas trop grands pour
J(w )
Signes observables :
15
Pas assez grands pour progresser
10
ecacement, mais pas trop grands pour
J(w )
La courbe J vs itérations :
Descente rapide puis plateau.
40
Signes observables :
DIVERGE !
Les pas sautent d'un côté à l'autre du
30
minimum
J(w )
20
J peut augmenter au lieu de diminuer
10 Les paramètres peuvent devenir très
grands
0
−4 −2 0 2 4 6 8
Dans certains cas, cela peut conduire à
w
des problèmes numériques (overow,
NaN)
40
Signes observables :
DIVERGE !
Les pas sautent d'un côté à l'autre du
30
minimum
J(w )
20
J peut augmenter au lieu de diminuer
10 Les paramètres peuvent devenir très
grands
0
−4 −2 0 2 4 6 8
Dans certains cas, cela peut conduire à
w
des problèmes numériques (overow,
NaN)
J
20
0
0 20 40 60 80 100
Itération
J
20
0
0 20 40 60 80 100
Itération
☞ À retenir
En pratique : des valeurs comme α = 0.01 ou α = 0.001 sont souvent de bons points de départ.
Des méthodes comme Adam ou RMSProp adaptent le pas eectif pendant l'entraînement, mais
conservent en général un learning rate de base à choisir.
Exemple : En pratique
On combine souvent plusieurs critères, par exemple : nombre maximal d'itérations + seuil de variation
de la fonction de coût + seuil sur la norme du gradient.
Pr. ADDOU ML S2 Descente de gradient 36/50
✎ TD Exercice 1 Descente de gradient à la main (15 min)
Soit J(w ) = (w − 3)2 + 1 (parabole). Départ : w0 = 0.
1 dJ
Calculer dw .
3 dJ
Vérier en résolvant dw =0 directement.
5 Avec α = 0.01 : calculer w1 . Donner ensuite une estimation du nombre d'itérations nécessaires pour
atteindre wt ≥ 2.9.
6 Quelle valeur de α choisiriez-vous parmi {0.01, 0.2, 1.5} et pourquoi ?
Donc : ln(1/30)
t≥ ≈ 168.4
ln(0.98)
Il faut donc 169 itérations pour atteindre wt ≥ 2.9.
Conclusion : la convergence est correcte, mais lente.
✓ Solution Exercice 1 (2/2)
5. Avec α = 0.01 : w1 = 0 − 0.01 × 2(0 − 3) = 0 + 0.06 = 0.06
La mise à jour s'écrit :
wt+1 = wt − 0.01 · 2(wt − 3) = 0.98 wt + 0.06
wt = 3 1 − 0.98t
Avec w0 = 0, on obtient :
Donc : ln(1/30)
t≥ ≈ 168.4
ln(0.98)
Il faut donc 169 itérations pour atteindre wt ≥ 2.9.
Conclusion : la convergence est correcte, mais lente.
★ Observation clé
∂J −2 Pn
Dans la formule
∂w = n i=1 xi (yi − ŷi ), la somme porte sur les n exemples. Si n= 10
millions, chaque itération demande de parcourir les 10M de lignes pour faire un seul pas.
C'est très lent.
★ Observation clé
∂J −2 Pn
Dans la formule
∂w = n i=1 xi (yi − ŷi ), la somme porte sur les n exemples. Si n= 10
millions, chaque itération demande de parcourir les 10M de lignes pour faire un seul pas.
C'est très lent.
Ordre de grandeur :
Le coût d'une itération de Batch GD est souvent de l'ordre de O(n d)
Si n = 107 et d = 103 , 10 opérations par itération
cela représente environ 10
★ Observation clé
∂J −2 Pn
Dans la formule
∂w = n i=1 xi (yi − ŷi ), la somme porte sur les n exemples. Si n= 10
millions, chaque itération demande de parcourir les 10M de lignes pour faire un seul pas.
C'est très lent.
Ordre de grandeur :
Le coût d'une itération de Batch GD est souvent de l'ordre de O(n d)
Si n = 107 et d = 103 , 10 opérations par itération
cela représente environ 10
☞ À retenir
En pratique, le Mini-Batch GD est très souvent utilisé, en particulier en deep learning, car il ore
un bon compromis entre coût de calcul et stabilité. Le batch size B est un hyperparamètre.
Pr. ADDOU ML S2 Descente de gradient 41/50
Visualiser les 3 variantes trajectoire vers le minimum
Batch (B = n)
Départ
Min
Batch (B = n) SGD (B = 1)
Départ Départ
Min Min
Trajectoire typiquement plus Trajectoire plus bruitée. Chaque Bon compromis. Plus rapide que
régulière. Chaque pas utilise tous pas utilise 1 seul exemple. Rapide Batch GD et souvent plus stable
les exemples. Stable mais coûteux. par itération, mais irrégulier. que SGD pur.
Réponse en 3 points :
1 En moyenne, l'information reste utile. Sous un échantillonnage aléatoire, le gradient
stochastique peut être vu comme une estimation bruitée du gradient complet, mais il
conserve souvent une direction globalement utile pour l'optimisation.
Réponse en 3 points :
1 En moyenne, l'information reste utile. Sous un échantillonnage aléatoire, le gradient
stochastique peut être vu comme une estimation bruitée du gradient complet, mais il
conserve souvent une direction globalement utile pour l'optimisation.
2 Le bruit peut parfois aider. Dans les problèmes non convexes, les uctuations du SGD
peuvent aider à quitter certaines zones plates ou certains minima locaux peu profonds.
Réponse en 3 points :
1 En moyenne, l'information reste utile. Sous un échantillonnage aléatoire, le gradient
stochastique peut être vu comme une estimation bruitée du gradient complet, mais il
conserve souvent une direction globalement utile pour l'optimisation.
2 Le bruit peut parfois aider. Dans les problèmes non convexes, les uctuations du SGD
peuvent aider à quitter certaines zones plates ou certains minima locaux peu profonds.
3 On adapte souvent le learning rate. En pratique, on utilise souvent une décroissance
du pas d'apprentissage : pas plus grands au début, puis plus petits ensuite pour stabiliser
l'entraînement.
Réponse en 3 points :
1 En moyenne, l'information reste utile. Sous un échantillonnage aléatoire, le gradient
stochastique peut être vu comme une estimation bruitée du gradient complet, mais il
conserve souvent une direction globalement utile pour l'optimisation.
2 Le bruit peut parfois aider. Dans les problèmes non convexes, les uctuations du SGD
peuvent aider à quitter certaines zones plates ou certains minima locaux peu profonds.
3 On adapte souvent le learning rate. En pratique, on utilise souvent une décroissance
du pas d'apprentissage : pas plus grands au début, puis plus petits ensuite pour stabiliser
l'entraînement.
☞ À retenir
Le SGD pur est surtout important comme idée de base. En pratique, on utilise très souvent des
variantes mini-batch, qui orent un bon compromis entre coût de calcul, bruit du gradient et stabilité.
Pr. ADDOU ML S2 Descente de gradient 43/50
Vocabulaire essentiel Époque, Itération, Batch Size
3 termes à connaître absolument
Itération = 1 mise à jour des paramètres (= 1 pas de la descente)
Batch size B = nombre d'exemples utilisés par itération
Époque (Epoch) = 1 passage complet sur l'ensemble des données
En général, au cours d'une époque, chaque exemple est vu une fois, souvent dans un ordre mélangé
En général, au cours d'une époque, chaque exemple est vu une fois, souvent dans un ordre mélangé
Problème sans mélange : imaginons que les 100 premiers exemples soient tous des
appartements chers, et les 100 suivants des appartements bon marché. Le modèle verrait
d'abord surtout des prix élevés, puis surtout des prix bas. Les gradients successifs pourraient
alors être fortement inuencés par l'ordre des données.
Problème sans mélange : imaginons que les 100 premiers exemples soient tous des
appartements chers, et les 100 suivants des appartements bon marché. Le modèle verrait
d'abord surtout des prix élevés, puis surtout des prix bas. Les gradients successifs pourraient
alors être fortement inuencés par l'ordre des données.
Avec mélange : les mini-batches ont davantage de chances de contenir des exemples variés. Le
gradient calculé à chaque itération est alors souvent plus représentatif de l'ensemble du dataset.
Problème sans mélange : imaginons que les 100 premiers exemples soient tous des
appartements chers, et les 100 suivants des appartements bon marché. Le modèle verrait
d'abord surtout des prix élevés, puis surtout des prix bas. Les gradients successifs pourraient
alors être fortement inuencés par l'ordre des données.
Avec mélange : les mini-batches ont davantage de chances de contenir des exemples variés. Le
gradient calculé à chaque itération est alors souvent plus représentatif de l'ensemble du dataset.
☞ À retenir
Règle pratique : en apprentissage par mini-batch ou SGD, il est généralement préférable de mélanger
les données à chaque époque. En Python, SGDRegressor le fait typiquement avec shuffle=True.
7 Pour la régression linéaire (MSE convexe), la descente de gradient converge vers la même solution que
l'équation normale.
8 En SGD ou en mini-batch, il est généralement préférable de mélanger les données à chaque époque.
3 ✗ Faux. Le SGD utilise un seul exemple par itération, donc chaque itération est généralement
beaucoup plus rapide que Batch GD, même si davantage d'itérations peuvent être nécessaires.
4 ✗ Faux. Une époque correspond à un passage complet sur l'ensemble des données, soit environ n/B
mises à jour.
6 ✓ Vrai. Si α est trop grand, J peut augmenter au lieu de diminuer, et l'algorithme peut osciller ou
diverger.
7 ✓ Vrai. Pour la régression linéaire avec une MSE convexe, la descente de gradient converge vers la
même solution que l'équation normale lorsque le learning rate est bien choisi.
8 ✓ Vrai, en général. En SGD ou en mini-batch, le mélange aléatoire des données réduit les eets dus à
l'ordre des exemples et rend souvent les gradients plus représentatifs du dataset.
∂J
Règle de mise à jour w ← w − α ∂w , b ← b − α ∂J
∂b
n
−2
X
∂J
Gradient / w ∂w = n xi (yi − wxi − b)
i=1
n
−2
X
∂J
Gradient / b ∂b = n (yi − wxi − b)
i=1
n
Itérations / époque ≈ B
Pause 10 minutes
20252026
compromis biaisvariance
★ Ce qu'on a vu en Partie 1
ŷ = wx + b
★ Ce qu'on a vu en Partie 1
ŷ = wx + b
d
X
ŷ = w1 x1 + w2 x2 + · · · + wd xd + b = wj xj + b
j=1
d
X
ŷ = w1 x1 + w2 x2 + · · · + wd xd + b = wj xj + b
j=1
w3 = 0.3 : chaque année plus récente ajoute 300 $, à surface et étage xés
w3 = 0.3 : chaque année plus récente ajoute 300 $, à surface et étage xés
ŷ = wx + b
1 variable explicative : x
1 poids : w
1 biais : b
Le graphe est une droite dans le plan
(x, y )
Elle utilise une seule feature d'entrée. Elle utilise plusieurs features d'entrée.
ŷ = wx + b ŷ = w1 x1 + w2 x2 + · · · + wd xd + b
1 poids : w x1 , . . . , x d
1 biais : b un poids par feature
Elle utilise une seule feature d'entrée. Elle utilise plusieurs features d'entrée.
ŷ = wx + b ŷ = w1 x1 + w2 x2 + · · · + wd xd + b
1 poids : w x1 , . . . , x d
1 biais : b un poids par feature
☞ À retenir
La diérence entre simple et multiple dépend uniquement du nombre de features d'entrée :
simple : une seule feature
multiple : plusieurs features
Pr. ADDOU ML S2 Régression multiple 6/53
Le problème : comment généraliser l'équation normale ?
★ Question centrale
En Partie 1, on avait une formule simple pour w∗ et b ∗ avec une seule feature. Mais main-
tenant qu'on a d features (w1 , w2 , . . . , wd , b ), on a d + 1 paramètres à estimer. Comment
faire ?
En Partie 1, on avait une formule simple pour w∗ et b ∗ avec une seule feature. Mais main-
tenant qu'on a d features (w1 , w2 , . . . , wd , b ), on a d + 1 paramètres à estimer. Comment
faire ?
θ ∗ = (XT X)−1 XT y
En Partie 1, on avait une formule simple pour w∗ et b ∗ avec une seule feature. Mais main-
tenant qu'on a d features (w1 , w2 , . . . , wd , b ), on a d + 1 paramètres à estimer. Comment
faire ?
θ ∗ = (XT X)−1 XT y
T
Cette formule est la même quel que soit le nombre de features, à condition que X X soit inversible.
C'est la force de l'algèbre linéaire : une seule formule généralise tout.
En Partie 1, on avait une formule simple pour w∗ et b ∗ avec une seule feature. Mais main-
tenant qu'on a d features (w1 , w2 , . . . , wd , b ), on a d + 1 paramètres à estimer. Comment
faire ?
θ ∗ = (XT X)−1 XT y
T
Cette formule est la même quel que soit le nombre de features, à condition que X X soit inversible.
C'est la force de l'algèbre linéaire : une seule formule généralise tout.
Exemple : Concret
2
1 2 3
A2×3 = , v3×1 = 5
4 5 6
1
P
Math Règle du produit A·B
Pour que A·B soit déni : le nombre de colonnes de A doit égaler le nombre de lignes de
B.
Am×n · Bn×p = Cm×p
Pn
Chaque élément : cij = k=1 aik bkj (produit scalaire ligne i de A par colonne j de B ).
P
Math Règle du produit A·B
Pour que A·B soit déni : le nombre de colonnes de A doit égaler le nombre de lignes de
B.
Am×n · Bn×p = Cm×p
Pn
Chaque élément : cij = k=1 aik bkj (produit scalaire ligne i de A par colonne j de B ).
A−1
P
Math Matrice inverse (pour matrices carrées uniquement)
n
∥v ∥2 = v T v = v12 + v22 + · · · + vn2 = vi2
X
i=1
n
∥v ∥2 = v T v = v12 + v22 + · · · + vn2 = vi2
X
i=1
∥a − b∥2 = (a − b)T (a − b)
n
∥v ∥2 = v T v = v12 + v22 + · · · + vn2 = vi2
X
i=1
∥a − b∥2 = (a − b)T (a − b)
Cette identité va nous permettre de réécrire la MSE en forme matricielle. C'est la clé de toute la
démonstration qui suit.
ŷ = Xw + b 1
où 1 est le vecteur colonne de taille n contenant uniquement des 1.
ŷ = Xθ
Le biais b est absorbé dans θ grâce à la colonne de 1.
ŷi = 1
|{z} ·b + xi 1 · w1 + xi 2 · w2 + · · · + xid · wd
colonne de 1
= b + w1 xi 1 + w2 xi 2 + · · · + wd xid
C'est exactement la formule de la régression multiple ! Le biais b est retrouvé.
ŷi = 1
|{z} ·b + xi 1 · w1 + xi 2 · w2 + · · · + xid · wd
colonne de 1
= b + w1 xi 1 + w2 xi 2 + · · · + wd xid
C'est exactement la formule de la régression multiple ! Le biais b est retrouvé.
☞ À retenir
Désormais, quand on écrit θ ∗ = (XT X)−1 XT y, on suppose que X contient déjà la colonne de 1,
et θ contientb comme première composante.
En Python : X = np.column_stack([[Link](n), X_original]).
1
J(θ) = (y − Xθ)T (y − Xθ)
n
1
J(θ) = (y − Xθ)T (y − Xθ)
n
Cette forme matricielle contient exactement la même information que la forme en somme. Mais elle
est bien plus pratique pour calculer les gradients.
(y − Xθ)T = yT − (Xθ)T = yT − θ T XT
Puis on distribue :
(y − Xθ)T = yT − (Xθ)T = yT − θ T XT
Puis on distribue :
Scalaire :
d
dx (cx) = c
∂
↔ Matriciel : ∂θ (θ T c) = c
d 2 ↔ Matriciel : ∂θ ∂
(θ T Aθ)
Scalaire :
dx (ax ) = 2ax = 2Aθ
C'est la même logique, juste étendue aux vecteurs.
Scalaire :
d
dx (cx) = c
∂
↔ Matriciel : ∂θ (θ T c) = c
d 2 ↔ Matriciel : ∂θ ∂
(θ T Aθ)
Scalaire :
dx (ax ) = 2ax = 2Aθ
C'est la même logique, juste étendue aux vecteurs.
Gradient total :
1 2 T
− 2XT y + 2XT Xθ = − XT y
∇J(θ) = 0 X Xθ
n n
FORMULE FINALE :
θ ∗ = (XT X)−1 XT y ■
X
T X est inversible si et seulement si :
1 n ≥d +1 : condition nécessaire
☞ À retenir
Solutions si XT X n'est pas inversible : (1) supprimer les features redondantes, (2) ajouter de
la régularisation (Ridge Partie 3), (3) utiliser la pseudo-inverse ou des méthodes d'optimisation
comme la descente de gradient.
inverse de labels
T
X X ((d +1)×(d +1)) n× 1
θ∗ = (XT X)−1 XT y
paramètres appris
(d + 1) × n
((d + 1) × 1)
x1 x2 y
+1 +1 6
+1 −1 4
−1 +1 2
−1 −1 0
Pourquoi XT X est-elle diagonale ici ? Parce que les colonnes de X sont orthogonales (⟨coli , colj ⟩ =
0 pour i ̸= j ). C'est un cas idéal, pratique pour illustrer la méthode.
T
Sur de vraies données, X X serait en général une matrice avec des termes hors diagonale non nuls.
En pratique, on ne calcule pas son inverse à la main : on résout plutôt le système linéaire associé à
l'aide d'outils numériques stables.
6
1 1 1 1
T
4
X y = 1 1 −1 −1
2
1 −1 1 −1
0
6+4+2+0 12
= 6 + 4 − 2 − 0 = 8
6−4+2−0 4
θ ∗ = (XT X)−1 XT y
1 0 0 12
1
= 0 1 0 8
4
0 0 1 4
12 3
1
= 8 = 2
4
4 1
Résultat nal :
b ∗ = 3, w1∗ = 2, w2∗ = 1
Modèle : ŷ = 2x1 + 1 · x2 + 3
x1 x2 y ŷ = 2x1 + x2 + 3 Erreur
+1 +1 6 2(1)
+1+3=6 0
+1 −1 4 2(1)+ (−1) + 3 = 4 0
−1 +1 2 2(−1) + 1 + 3 = 2 0
−1 −1 0 2(−1) + (−1) + 3 = 0 0
Pourquoi MSE = 0 ici ? Parce que les données ont été générées exactement par le modèle y =
2x1 +x2 + 3, sans bruit. Avec des données réelles bruitées, on aurait généralement une MSE strictement
positive.
ŷ = 2 · 2 + 1 · (−1) + 3 = 4 − 1 + 3 = 6
Ou en forme matricielle :
3
ŷ = 1 2 −1 2 = 1 · 3 + 2 · 2 + (−1) · 1 = 3 + 4 − 1 = 6
1
☞ À retenir
Une fois que vous avez θ ∗ , la prédiction pour n'importe quel nouveau point xnouveau se fait en calculant
T ∗
ŷ = xnouveau θ (en ajoutant un 1 au début pour le biais).
★ Le problème
La régression linéaire trace une droite (simple) ou un hyperplan (multiple). Mais certaines
données suivent une courbe. Une droite devient alors trop restrictive.
y
Données Droite : ŷ = 4
Polynôme : ŷ = −x 2 + 6x − 3
★ Le problème
La régression linéaire trace une droite (simple) ou un hyperplan (multiple). Mais certaines
données suivent une courbe. Une droite devient alors trop restrictive.
☞ À retenir
Ici, les données ont une forme courbe. Une ré-
y
Données Droite : ŷ = 4
Polynôme : ŷ = −x 2 + 6x − 3
Features polynomiales
Features polynomiales
Exemple : Transformation
x −→ (x, x 2 , x 3 , . . . , x p )
Le nombre d'exemples ne change pas ; seul le nombre de features augmente.
Features polynomiales
Exemple : Transformation
x −→ (x, x 2 , x 3 , . . . , x p )
Le nombre d'exemples ne change pas ; seul le nombre de features augmente.
☞ À retenir
On ne change pas l'idée de la régression : on change seulement la représentation des données.
Posons : z1 = x, z2 = x 2
Alors ŷ = w1 x + w2 x 2 + b
devient ŷ = w1 z1 + w2 z2 + b
Posons : z1 = x, z2 = x 2
Alors ŷ = w1 x + w2 x 2 + b
devient ŷ = w1 z1 + w2 z2 + b
★ Idée essentielle
Une fois les nouvelles features construites, on obtient simplement une régression linéaire
multiple sur les variables (z1 , z2 ).
Posons : z1 = x, z2 = x 2
Alors ŷ = w1 x + w2 x 2 + b
devient ŷ = w1 z1 + w2 z2 + b
★ Idée essentielle
Une fois les nouvelles features construites, on obtient simplement une régression linéaire
multiple sur les variables (z1 , z2 ).
☞ À retenir
En machine learning, linéaire signie ici : linéaire par rapport aux paramètres, pas nécessaire-
ment linéaire par rapport à x.
☞ À retenir
La régression linéaire signie linéaire par rapport aux paramètres, pas nécessairement par rapport
aux features. Toute la théorie (MSE, équation normale, gradient) s'applique sans modication, tant
que le modèle reste linéaire par rapport aux paramètres.
ŷ = wx + b
P
i (x − x̄)(yi − ȳ )
x w =∗ Pi 2
, b ∗ = ȳ − w ∗ x̄
i (xi − x̄)
Données Droite : ŷ = 4
Polynôme : ŷ = −x 2 + 6x − 3
ŷ = wx + b
P
i (x − x̄)(yi − ȳ )
x w =∗ Pi 2
, b ∗ = ȳ − w ∗ x̄
i (xi − x̄)
Données Droite : ŷ = 4
Polynôme : ŷ = −x 2 + 6x − 3
★ x̄; ȳ
1 +2+3+4+5 2 +5+6+5+2
x̄ = = 3, ȳ = =4
5 5
Donc :
0
w∗ = = 0, b∗ = 4
10
x y ŷ (y − ŷ )2
1 2 4 4
2 5 4 1
3 6 4 4
4 5 4 1
5 2 4 4
14
MSE = = 2.8
5
☞ À retenir
Même la meilleure droite garde ici une erreur non nulle, car les données ont une structure courbe.
ŷ = w1 x + w2 x 2 + b
Avec colonne de 1 :
b
ŷ = Xθ, θ = w1
w2
1 1 1 2
1 2 4 5
X = 1 3 9 , y = 6
1 4 16 5
1 5 25 2
5 15 55
T
X X = 15 55 225
55 225 979
20
T
X y = 60
206
(XT X)θ = XT y
Sa solution est :
−3
θ∗ = 6
−1
Donc :
b = −3, w1 = 6, w2 = −1
ŷ = −x 2 + 6x − 3
ŷ = 4 ŷ = −x 2 + 6x − 3
MSE = 2.8 ŷi = yi pour tous les points
MSE =0
☞ À retenir
La régression polynomiale améliore ici fortement l'ajustement, car elle peut représenter une courbe
que la droite ne peut pas capturer.
☞ À retenir
Le degré p est un hyperparamètre. Si p augmente, le biais diminue, mais la variance peut augmenter.
Il faut donc choisir le degré sur un ensemble de validation.
x1 , x2 , x12 , x22 , x1 x2
x1 , x2 , x12 , x22 , x1 x2
Exemple : Exemple
Si x1 est la surface et x2 l'étage, le terme x1 x2 capture un eet combiné entre ces deux
variables.
x1 , x2 , x12 , x22 , x1 x2
Exemple : Exemple
Si x1 est la surface et x2 l'étage, le terme x1 x2 capture un eet combiné entre ces deux
variables.
☞ À retenir
Le nombre de paramètres augmente vite avec le degré : il faut donc rester prudent pour éviter
l'overtting.
☞ À retenir
Le pipeline reste toujours le même :
2 T
Calculer X X (matrice 3 × 3). Vérier qu'elle est symétrique.
3 T
Calculer X y.
5 −2 −2
4 En supposant que (XT X)−1 = 1
4
−2 2 0 (donné), calculer θ∗ .
−2 0 2
x1 x2 y ŷ = 2x1 + 2x2 + 1 y − ŷ
1 0 3 2+0+1=3 0
2 1 7 4+2+1=7 0
0 1 3 0+2+1 = 3 0
1 2 7 2+4+1 = 7 0
1 T
La matrice X X est toujours symétrique.
2 T
Si deux features sont identiques (colonnes copiées), X X est non inversible.
3 Pour d = 100 000 features, l'équation normale est plus rapide que la descente de gradient.
7 T
X X est inversible même si n < d + 1.
2 ✓ Vrai. T
Deux colonnes identiques impliquent une dépendance linéaire, donc X X n'est pas inversible.
3 ✗ Faux. Quand le nombre de features est très grand, l'équation normale devient en général coûteuse,
alors que la descente de gradient peut être plus adaptée.
5 ✓ Vrai. Les features polynomiales permettent de capturer des relations non linéaires tout en gardant
un modèle linéaire par rapport aux paramètres.
Concept Dénition/formule
Régression multiple ŷ = w1 x1 + · · · + wd xd + b
Notation matricielle ŷ = Xθ
Astuce colonne de 1 Ajouter une colonne de 1 à X pour absorber b
MSE matricielle J(θ) = n1 ∥y − Xθ∥2
Équation normale θ ∗ = (XT X)−1 XT y si XT X est inversible
Dimensions X : n × (d + 1), y : n × 1, θ : (d + 1) × 1
T
Inversibilité de X X Colonnes de X lin. indépendantes ; en particulier, il faut n≥
d +1
Features polynomiales x → [x, x 2 , . . . , x p ] puis rég. lin. classique sur ces features
Interactions x1 x2 = eet combiné de 2 features (degré 2 multi-features)
Degré = hyperparam. Degré ↑ : biais ↓ mais variance ↑. Choisir sur validation set
Complexité La résolution devient coûteuse quand d est grand
Alternative Descente de gradient ou méthodes numériques adaptées si d
est grand
Pr. ADDOU ML S2 Régression multiple 51/53
Formules clés de cette partie
Pd
Modèle multiple ŷ = j=1 wj xj +b
Forme matricielle ŷ = Xθ
∗
Prédiction nouvelle ŷnew = xT
new θ
2
Métriques : R , MAE, RMSE
Pause 10 minutes
Régression (Ch. 2)
y ∈R (variable continue)
Modèle : ŷ = wT x + b
Métriques : MSE, RMSE, R
2
Modèle linéaire
1 (maligne)
ŷ
Seuil 0.5
/
0.5 (seuil)
y
0 (bénigne)
0 1 2 3 4 5 6 7 8 9 10
Dans ce cas simple, le seuillage du modèle linéaire semble produire une séparation correcte entre les
deux classes. Cependant, cette approche reste fragile : que se passe-t-il si l'on ajoute une observation
extrême ?
Pr. ADDOU ML Ch.3 Rég. logistique 4/39
Le problème : sensibilité aux points extrêmes
Point extrême
Modèle initial
1 (maligne) Modèle après ajout du point extrême
points positifs mal classés
ŷ
Seuil 0.5
/
0.5 (seuil)
y
0 (bénigne)
0 2 4 6 8 10 12 14 16 18 20 22
Point extrême
Modèle initial
1 (maligne) Modèle après ajout du point extrême
points positifs mal classés
ŷ
Seuil 0.5
/
0.5 (seuil)
y
0 (bénigne)
0 2 4 6 8 10 12 14 16 18 20 22
☞ À retenir
Trois limites principales de la régression linéaire pour la classication :
1 ŷ peut sortir de l'intervalle [0, 1] : par exemple, des valeurs comme −3 ou 5 ne peuvent pas être
interprétées comme des probabilités.
2 Un point extrême peut fortement déplacer la droite ajustée et donc modier la frontière de décision
obtenue par seuillage.
3 La MSE n'est pas la fonction de coût la plus adaptée lorsque y ∈ {0, 1}, car elle ne modélise pas
directement une probabilité binaire.
Pr. ADDOU ML Ch.3 Rég. logistique 5/39
La solution : transformer le score en probabilité
★ Idée intuitive
z ∈R
x (features) z = wT x + b p̂ = σ(z) p̂ ∈ (0, 1)
★ Idée intuitive
z ∈R
x (features) z = wT x + b p̂ = σ(z) p̂ ∈ (0, 1)
★ Idée intuitive
z ∈R
x (features) z = wT x + b p̂ = σ(z) p̂ ∈ (0, 1)
★ Idée intuitive
z ∈R
x (features) z = wT x + b p̂ = σ(z) p̂ ∈ (0, 1)
1
σ(z) = , z ∈R
1 + e −z
avec
σ(z) ∈ (0, 1).
1 1
σ(z) = z → +∞ ⇒ σ(z) → 1
1 + e −z
0.75
σ(z)
0.5
σ(0) = 0.5
0.25
z → −∞ ⇒ σ(z) → 0
0
−8 −6 −4 −2 0 2 4 6 8
z
Pr. ADDOU ML Ch.3 Rég. logistique 7/39
Propriétés fondamentales de σ(z)
P
Math 5 propriétés à connaître
☞ À retenir
σ ′ (z) = σ(z)
La relation : 1 − σ(z)
est particulièrement importante : elle exprime la dérivée de la sigmoïde en fonction de la sigmoïde
elle-même. Cette propriété simplie le calcul du gradient lors de l'entraînement du modèle logistique.
P
Math Preuve
1 1
σ(−z) = = .
1 + e −(−z) 1 + ez
En multipliant le numérateur et le dénominateur par e −z , on obtient :
e −z e −z e −z
σ(−z) = = = .
e −z (1 + e z ) e −z + 1 1 + e −z
D'autre part :
1 1 + e −z − 1 e −z
1 − σ(z) = 1 − = = .
1 + e −z 1 + e −z 1 + e −z
Ainsi :
σ(−z) = 1 − σ(z). ■
P
Math Preuve
1
On part de la dénition : σ(z) = 1+e −z = (1 + e −z )−1 .
Par la règle de la chaîne : σ ′ (z) = −(1 + e −z )−2 × (−e −z ) = e −z
(1+e −z )2
.
1 e −z e −z
On factorise ensuite : σ ′ (z) = 1+e −z × 1+e −z = σ(z) × 1+e −z .
e −z 1
Or :
1+e −z =1− = 1 − σ(z).
1+e −z
σ ′ (z) = σ(z) 1 − σ(z) .
Donc : ■
′
On a montré que : σ (z) = σ(z) 1 − σ(z) .
Cette fonction est une parabole concave, car le coecient de u2 est négatif. Son maximum est
donc atteint au sommet.
1
p̂ = P(y = 1 | x) = σ(wT x + b) = .
1 + e −(wT x+b)
Règle de décision avec un seuil 0.5 :
(
1, si p̂ ≥ 0.5,
ŷ =
0, si p̂ < 0.5.
☞ À retenir
Malgré son nom, la régression logistique est principalement utilisée pour la classication.
Elle combine un score linéaire avec la fonction sigmoïde an d'estimer une probabilité
d'appartenance à la classe positive.
La régression logistique ne produit pas directement une simple étiquette classe 0 ou classe
1. Elle estime d'abord une probabilité :
p̂ = P(y = 1 | x).
Par exemple :
Sara (p̂ = 0.55) est classé dans la classe positive avec le seuil 0.5, mais sa probabilité estimée
est proche de la frontière de décision. Dans une application médicale, ce type de cas doit
être interprété avec prudence et peut justier des informations ou examens complémentaires.
★ Point de départ
Question importante
Si p̂ est une probabilité, alors elle est facile à interpréter.
Mais que représente exactement le score z ? z = 2.5 ? z = −1.2 ?
Peut-on donner une interprétation statistique à ce score linéaire ?
★ Point de départ
Question importante
Si p̂ est une probabilité, alors elle est facile à interpréter.
Mais que représente exactement le score z ? z = 2.5 ? z = −1.2 ?
Peut-on donner une interprétation statistique à ce score linéaire ?
☞ À retenir
Pour répondre à cette question, nous allons introduire deux notions : odds et log-odds.
Elles permettront de montrer que le score linéaire z n'est pas arbitraire : il représente lelog-odds de
la classe positive.
☞ À retenir
Les notions d' odds et de log-odds sont introduites pour trois raisons :
1 comprendre ce que représente le score linéaire z = wT x + b ;
3 montrer que la régression logistique est linéaire dans le log-odds, et non directement dans la
probabilité.
★ Idée intuitive
★ Idée intuitive
★ Idée intuitive
☞ À retenir
La probabilité p̂ donne une information absolue, tandis que les odds donnent une information relative
: elles comparent la classe positive à la classe négative.
Pr. ADDOU ML Ch.3 Rég. logistique 19/39
Les odds : dénition et lecture
Odds
P(y = 0 | x) = 1 − p̂.
p̂
p̂ odds = Interprétation
1 − p̂
0.20
0.20 = 0.25 Classe positive moins probable
0.80
0.50 1 Les deux classes sont aussi probables
0.80 4 Classe positive 4 fois plus probable
0.90 9 Classe positive 9 fois plus probable
Pr. ADDOU ML Ch.3 Rég. logistique 20/39
Du odds au log-odds : le logit
Log-odds ou logit
Log-odds ou logit
☞ À retenir
Le logit transforme une probabilité p̂ ∈ (0, 1) en une valeur réelle : logit(p̂) ∈ R. C'est cette
T
transformation qui permet de relier une probabilité au score linéaire w x + b.
Donc :
1
p̂ 1+e −z 1
= e −z
= = ez .
1 − p̂ e −z
1+e −z
En appliquant le logarithme :
p̂
ln = ln(e z ) = z.
1 − p̂
Ainsi : p̂
ln = wT x + b
1 − p̂
Interprétation du score
Interprétation du score
Interprétation du score
☞ À retenir
La régression logistique est linéaire dans le log-odds, pas directement dans la probabilité.
Pr. ADDOU ML Ch.3 Rég. logistique 23/39
Pourquoi le nom régression logistique ?
★ Origine du nom
1
Le terme logistique vient de la fonction logistique : σ(z) = 1+e −z .
Cette fonction transforme un score réel z ∈ R en une probabilité strictement comprise entre 0 et 1 :
σ(z) ∈ (0, 1).
★ Origine du nom
1
Le terme logistique vient de la fonction logistique : σ(z) = 1+e −z .
Cette fonction transforme un score réel z ∈ R en une probabilité strictement comprise entre 0 et 1 :
σ(z) ∈ (0, 1).
★ Pourquoi régression ?
Le mot régression vient du fait que le modèle estime une quantité continue, ici une probabilité :
p̂ = P(y = 1 | x).
Cependant, cette probabilité est ensuite utilisée pour prendre une décision de classication.
★ Origine du nom
1
Le terme logistique vient de la fonction logistique : σ(z) = 1+e −z .
Cette fonction transforme un score réel z ∈ R en une probabilité strictement comprise entre 0 et 1 :
σ(z) ∈ (0, 1).
★ Pourquoi régression ?
Le mot régression vient du fait que le modèle estime une quantité continue, ici une probabilité :
p̂ = P(y = 1 | x).
Cependant, cette probabilité est ensuite utilisée pour prendre une décision de classication.
☞ À retenir
La régression logistique est donc un modèle de classication qui :
calcule un score linéaire z = wT x + b ;
☞ À retenir
Une augmentation d'une unité de xj , toutes les autres variables étant xées, multiplie les odds par
: e wj . Ainsi :
wj
wj < 0 ⇒ e <1 : les odds diminuent.
Supposons :
w1 = 0.8, w2 = 2.5, w3 = −0.1, b = −3.
Interprétation des poids wj
Supposons :
w1 = 0.8, w2 = 2.5, w3 = −0.1, b = −3.
w1 = 0.8 : chaque mot supplémentaire en majuscules multiplie les odds de spam par e 0.8 ≈ 2.23,
toutes les autres variables étant xées.
Interprétation des poids wj
Supposons :
w1 = 0.8, w2 = 2.5, w3 = −0.1, b = −3.
w1 = 0.8 : chaque mot supplémentaire en majuscules multiplie les odds de spam par e 0.8 ≈ 2.23,
toutes les autres variables étant xées.
w2 = 2.5 : la présence du mot urgent multiplie les odds de spam par e 2.5 ≈ 12.18, toutes les autres
variables étant xées.
Interprétation des poids wj
Supposons :
w1 = 0.8, w2 = 2.5, w3 = −0.1, b = −3.
w1 = 0.8 : chaque mot supplémentaire en majuscules multiplie les odds de spam par e 0.8 ≈ 2.23,
toutes les autres variables étant xées.
w2 = 2.5 : la présence du mot urgent multiplie les odds de spam par e 2.5 ≈ 12.18, toutes les autres
variables étant xées.
w3 = −0.1 : une augmentation d'une unité de la longueur de l'email multiplie les odds par
e −0.1 ≈ 0.90, ce qui diminue légèrement les odds de spam.
Interprétation des poids wj
Supposons :
w1 = 0.8, w2 = 2.5, w3 = −0.1, b = −3.
w1 = 0.8 : chaque mot supplémentaire en majuscules multiplie les odds de spam par e 0.8 ≈ 2.23,
toutes les autres variables étant xées.
w2 = 2.5 : la présence du mot urgent multiplie les odds de spam par e 2.5 ≈ 12.18, toutes les autres
variables étant xées.
w3 = −0.1 : une augmentation d'une unité de la longueur de l'email multiplie les odds par
e −0.1 ≈ 0.90, ce qui diminue légèrement les odds de spam.
b = −3 : lorsque toutes les variables valent 0, le log-odds vaut −3, donc p̂ = σ(−3) ≈ 0.047.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
L'équation wT x +b =0 dénit :
En dimension 1 : un point sur l'axe des x : x ∗ = − wb , si w ̸= 0.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
L'équation wT x +b =0 dénit :
En dimension 1 : un point sur l'axe des x : x ∗ = − wb , si w ̸= 0.
En dimension 2 : une droite : w1 x1 + w2 x2 + b = 0.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
L'équation wT x +b =0 dénit :
En dimension 1 : un point sur l'axe des x : x ∗ = − wb , si w ̸= 0.
En dimension 2 : une droite : w1 x1 + w2 x2 + b = 0.
En dimension 3 : un plan.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
L'équation wT x +b =0 dénit :
En dimension 1 : un point sur l'axe des x : x ∗ = − wb , si w ̸= 0.
En dimension 2 : une droite : w1 x1 + w2 x2 + b = 0.
En dimension 3 : un plan.
En dimension d : un hyperplan de dimension d − 1, si w ̸= 0.
Frontière de décision
La frontière de décision est l'ensemble des points x pour lesquels le modèle est exactement
au seuil de classication : p̂ = 0.5.
Comme p̂ = σ(z) et que σ(0) = 0.5, on obtient :
T
p̂ = 0.5 ⇔ σ(z) = 0.5 ⇔ z =0 ⇔ w x + b = 0.
L'équation wT x +b =0 dénit :
En dimension 1 : un point sur l'axe des x : x ∗ = − wb , si w ̸= 0.
En dimension 2 : une droite : w1 x1 + w2 x2 + b = 0.
En dimension 3 : un plan.
En dimension d : un hyperplan de dimension d − 1, si w ̸= 0.
☞ À retenir
Avec un seuil xé à 0.5, la frontière de décision de la régression logistique est une frontière linéaire,
T
dénie par l'hyperplan ane : w x + b = 0. Cette propriété rend le modèle simple et interprétable,
mais limite sa capacité à séparer directement des classes dont la frontière naturelle est fortement non
linéaire.
Pr. ADDOU ML Ch.3 Rég. logistique 27/39
Visualisation en 2D
Lecture du graphique :
z >0
4 ŷ = 1 ◦ : observations de la classe 0.
• : observations de la classe 1.
w
2 Droite épaisse : frontière de décision.
x2
x1
0
+
z = x1 + x2 − 2.5 = 0 ⇒
x2
p̂ = 0.5.
−
2
.5
=
−2 Si z < 0, alors p̂ < 0.5 et ŷ = 0.
0
−2 0 2 4
Si z > 0, alors p̂ > 0.5 et ŷ = 1.
x1
Le vecteur w = (w1 , w2 ) est
perpendiculaire à la frontière de décision.
Il pointe vers la région où le score z
augmente, ici la région associée à la classe
1.
1
1 −1.0 −3.0 ≈ 0.047 0 p̂ < 0.5
1 + e3
1
2 0.0 −1.0 ≈ 0.269 0 p̂ < 0.5
1 + e1
1
3 0.5 0.0 = 0.500 1 Au seuil de décision
1 + e0
1
4 2.0 3.0 ≈ 0.953 1 p̂ > 0.5
1 + e −3
1
1 −1.0 −3.0 ≈ 0.047 0 p̂ < 0.5
1 + e3
1
2 0.0 −1.0 ≈ 0.269 0 p̂ < 0.5
1 + e1
1
3 0.5 0.0 = 0.500 1 Au seuil de décision
1 + e0
1
4 2.0 3.0 ≈ 0.953 1 p̂ > 0.5
1 + e −3
A 0 0
B 2 0
C 0 1
D 4 1
E 6 0
Observations :
Observations :
Le coecient du mot urgent est plus grand que celui du nombre de mots en majuscules :
w2 = 3.0 contre w1 = 0.5. Son eet sur le log-odds est donc plus important.
Observations :
Le coecient du mot urgent est plus grand que celui du nombre de mots en majuscules :
w2 = 3.0 contre w1 = 0.5. Son eet sur le log-odds est donc plus important.
Sans le mot urgent (x2 = 0), la condition z ≥ 0 donne : 0.5x1 − 2 ≥ 0 ⇔ x1 ≥ 4.
Observations :
Le coecient du mot urgent est plus grand que celui du nombre de mots en majuscules :
w2 = 3.0 contre w1 = 0.5. Son eet sur le log-odds est donc plus important.
Sans le mot urgent (x2 = 0), la condition z ≥ 0 donne : 0.5x1 − 2 ≥ 0 ⇔ x1 ≥ 4.
Il faut donc au moins 4 mots en majuscules pour atteindre la classe spam.
Avec le mot urgent (x2 = 1), même lorsque x1 = 0, on obtient : z =1 ⇒ p̂ = σ(1) ≈ 0.731.
Observations :
Le coecient du mot urgent est plus grand que celui du nombre de mots en majuscules :
w2 = 3.0 contre w1 = 0.5. Son eet sur le log-odds est donc plus important.
Sans le mot urgent (x2 = 0), la condition z ≥ 0 donne : 0.5x1 − 2 ≥ 0 ⇔ x1 ≥ 4.
Il faut donc au moins 4 mots en majuscules pour atteindre la classe spam.
Avec le mot urgent (x2 = 1), même lorsque x1 = 0, on obtient : z =1 ⇒ p̂ = σ(1) ≈ 0.731.
Paramètres appris w, b w, b
1
z = wx + b, p̂ = σ(z) = .
1 + e −z
Les paramètres du modèle sont :
w = 1.5, b = −3.
✓ Solution Exercice 1
1. Le score linéaire est :
z = wx + b = 1.5x − 3.
x z = 1.5x − 3 e −z p̂ = σ(z) ŷ
1
0 −3 20.09 ≈ 0.047 0
21.09
1
2 0 1 = 0.500 1
2
1
4 3 0.050 ≈ 0.953 1
1.050
1
6 6 0.0025 ≈ 0.998 1
1.0025
x = 0 ⇒ ŷ = 0, x = 2 ⇒ ŷ = 1, x = 4 ⇒ ŷ = 1, x = 6 ⇒ ŷ = 1.
✓ Solution Exercice 1
3. La frontière de décision est obtenue en résolvant z =0 :
Ainsi, avec le seuil 0.5, les observations telles que x ≥2 sont classées dans la classe positive.
4. Pour z =2 :
1 1
σ(2) = ≈ 0.881, σ(−2) = ≈ 0.119.
1 + e −2 1 + e2
Donc :
σ(2) + σ(−2) ≈ 0.881 + 0.119 = 1.000.
5. Comme σ(0) = 0.5, on a :
σ ′ (0) = σ(0)
1 − σ(0) = 0.5(1 − 0.5) = 0.25.
z = w1 x1 + w2 x2 + b.
w1 = 2, w2 = −1, b = 1.
Ainsi :
z = 2x1 − x2 + 1.
✓ Solution Exercice 2
1. La frontière de décision est obtenue en résolvant z =0 :
2x1 − x2 + 1 = 0 ⇔ x2 = 2x1 + 1.
2. Pour tracer la droite sur l'intervalle x1 ∈ [0, 5], on peut utiliser deux points :
x1 = 0 ⇒ x2 = 1, x1 = 2 ⇒ x2 = 5.
La droite passe donc par les points (0, 1) et (2, 5), avec une pente égale à 2.
3. Calculs pour les trois points :
☞ À retenir
Fin de la Partie 1
Suite : Partie 2 Entraînement du modèle logistique
Fonction de coût : cross-entropy / log-loss
Gradient de la cross-entropy
Pause : 10 minutes
☞ À retenir
La MSE peut être calculée, mais elle n'est pas le critère naturel pour apprendre une probabilité de
classe.
On considère : 1
ℓi = (yi − p̂i )2 , p̂i = σ(zi ), zi = wT xi + b.
2
MSE avec sigmoïde : calcul du gradient
Math Pour un seul exemple
P
On considère : 1
ℓi = (yi − p̂i )2 , p̂i = σ(zi ), zi = wT xi + b.
2
Par la règle de la chaîne : ∂ℓi ∂ℓi ∂ p̂i ∂zi
= · · .
∂wj ∂ p̂i ∂zi ∂wj
MSE avec sigmoïde : calcul du gradient
Math Pour un seul exemple
P
On considère : 1
ℓi = (yi − p̂i )2 , p̂i = σ(zi ), zi = wT xi + b.
2
Par la règle de la chaîne : ∂ℓi ∂ℓi ∂ p̂i ∂zi
= · · .
∂wj ∂ p̂i ∂zi ∂wj
On considère : 1
ℓi = (yi − p̂i )2 , p̂i = σ(zi ), zi = wT xi + b.
2
Par la règle de la chaîne : ∂ℓi ∂ℓi ∂ p̂i ∂zi
= · · .
∂wj ∂ p̂i ∂zi ∂wj
☞ À retenir
Le facteur important est : p̂i (1 − p̂i ). Il devient presque nul lorsque la sigmoïde est saturée.
σ(z)(1 − σ(z))
0.2
0.6
σ(z)
0.4
0.1
0.2
saturation ≈0 ≈0
0 0
−6 −4 −2 0 2 4 6 −6 −4 −2 0 2 4 6
z z
☞ À retenir
Avec la MSE, le gradient contient le facteur p̂i (1 − p̂i ). Lorsque zi est très négatif ou très positif, la
sigmoïde sature et ce facteur devient proche de 0. La correction par gradient peut alors devenir très
lente.
☞ À retenir
Même si l'erreur est importante, le gradient peut être très faible à cause de la saturation de la
sigmoïde.
Pr. ADDOU ML Ch.3 Cross-entropy 6/62
Pourquoi passer à la cross-entropy ?
☞ À retenir
On cherche une fonction de coût qui vérie trois propriétés :
Yi | xi ∼ Bernoulli(p̂i ).
1
∇J = X T (p̂ − y).
n
Cette fonction est la cross-entropy, aussi appelée log loss ou log-vraisemblance négative du
modèle de Bernoulli.
y = (y1 , . . . , yn ),
on écrit :
L(w, b) = P(Y = y | X ; w, b).
Autrement dit, les données observées sont xées, et l'on évalue la qualité d'un choix de
paramètres (w, b).
☞ À retenir
La vraisemblance est une fonction des paramètres. Plus L(w, b) est grande, plus le modèle attribue
une forte probabilité aux labels réellement observés dans le dataset.
★ Intuition simple
Si plusieurs événements sont indépendants, alors la probabilité qu'ils se réalisent tous ensemble
est le produit de leurs probabilités individuelles.
Par exemple, si deux événements indépendants ont des probabilités 0.8 et 0.7, alors la prob-
abilité qu'ils se réalisent tous les deux est : 0.8 × 0.7 = 0.56.
☞ À retenir
Le produit apparaît parce que la vraisemblance mesure la probabilité de l'ensemble des labels
observés dans le dataset. Sous l'hypothèse d'indépendance conditionnelle, cette probabilité
jointe devient un produit de probabilités individuelles.
Apprendre le modèle revient à choisir les paramètres w et b qui maximisent L(w, b). C'est le principe
du maximum de vraisemblance.
Pr. ADDOU ML Ch.3 Cross-entropy 12/62
Pourquoi passer à la log-vraisemblance ?
★ Problème avec le produit
yi
− p̂i )1−yi .
Qn
La vraisemblance est un produit de probabilités : L(w, b) = i=1 p̂i (1
Or, un produit de nombreuses probabilités peut devenir très petit :
0.9100 ≈ 2.7 × 10−5 , 0.91000 ≈ 1.7 × 10−46 .
Cela peut créer des problèmes numériques et rend les dérivées moins pratiques.
☞ À retenir
On maximise donc la log-vraisemblance au lieu de maximiser directement la vraisemblance
: le problème reste équivalent, mais devient plus stable et plus facile à dériver.
Pr. ADDOU ML Ch.3 Cross-entropy 13/62
De la log-vraisemblance à la cross-entropy
Math Calcul de la log-vraisemblance
P
− p̂i )1−yi ,
yi
Qn
À partir de la vraisemblance : L(w, b) = i=1 p̂i (1
Cross-entropy binaire
On dénit donc la fonction de coût comme la log-vraisemblance négative moyenne :
1
J(w, b) = − ln L(w, b).
n
n
1X
Ainsi : J(w, b) = − [yi ln(p̂i ) + (1 − yi ) ln(1 − p̂i )] avec : p̂i = σ(wT xi + b).
n
i=1
Pr. ADDOU ML Ch.3 Cross-entropy 15/62
Pourquoi le signe négatif ?
☞ À retenir
Le signe − transforme la maximisation de la log-vraisemblance en une minimisation. Le
facteur n1 ne change pas le minimiseur ; il permet d'obtenir une perte moyenne par exemple,
comparable entre datasets de tailles diérentes.
Binary Cross-Entropy
La fonction de coût utilisée en régression logistique est la log-vraisemblance négative
moyenne :
1
J(w, b) = − ln L(w, b).
n
Donc :
n
1X
J(w, b) = − [yi ln(p̂i ) + (1 − yi ) ln(1 − p̂i )]
n
i=1
avec :
p̂i = σ(wT xi + b).
Cette fonction est appelée cross-entropy, Binary Cross-Entropy ou log loss. Minimiser cette
fonction revient à maximiser la vraisemblance des labels observés sous un modèle de Bernoulli.
☞ À retenir
La cross-entropy pénalise fortement les erreurs conantes : la perte devient très grande lorsque le
modèle attribue une probabilité quasi nulle au label réellement observé.
4 4
Erreur conante Erreur conante
Coût ℓ
Coût ℓ
2 2
Si y = 1, le vrai label est la classe positive. Si y = 0, le vrai label est la classe négative.
Le coût est élevé car le modèle attribue une très Le coût est élevé car le modèle attribue une forte
faible probabilité au label observé. probabilité à la mauvaise classe.
1 3.321
J = (0.105 + 1.204 + 0.105 + 1.897 + 0.010) = ≈ 0.664.
5 5
☞ À retenir
Le patient 4, avec y = 0 mais p̂ = 0.85, contribue par 1.897 à la somme des pertes, soit environ 57%
de cette somme. La cross-entropy pénalise donc fortement les erreurs conantes : ici, le modèle
attribue une forte probabilité à la classe malade alors que le patient appartient à la classe négative.
Pr. ADDOU ML Ch.3 Cross-entropy 20/62
Convexité de la cross-entropy
Théorème : pour la régression logistique linéaire, la cross-entropy
n
1X
J(w, b) = − [yi ln(p̂i ) + (1 − yi ) ln(1 − p̂i )] ,
n
i=1
Math Intuition
P
La convexité signie qu'il n'existe pas de mauvais minimum local. Cependant, le minimiseur n'est
pas forcément unique, et il peut même ne pas être ni lorsque les classes sont parfaitement séparables.
La régularisation Ridge améliore la stabilité du problème en pénalisant les grandes valeurs des poids.
où
ℓi = − [yi ln(p̂i ) + (1 − yi ) ln(1 − p̂i )] ,
avec
p̂i = σ(zi ), zi = wT xi + b.
☞ À retenir
Pour montrer que J est convexe, il sut de montrer que chaque perte individuelle ℓi est convexe,
puis d'utiliser le fait qu'une moyenne de fonctions convexes reste convexe.
zi = wT xi + b, p̂i = σ(zi ).
On utilise :
1
σ(zi ) = .
1 + e −zi
On va montrer que cette perte peut se réécrire sous la forme :
ℓi (zi ) = ln(1 + e zi ) − yi zi
Pr. ADDOU ML Ch.3 Cross-entropy 23/62
Étape 2 : calcul de ln(σ(zi ))
Math Premier terme
P
On sait que : 1
σ(zi ) = .
1 + e −zi
Donc :
1
ln(σ(zi )) = ln .
1 + e −zi
Ainsi :
ln(σ(zi )) = − ln(1 + e −zi ).
Or : 1 + e zi
1 + e −zi = .
e zi
Donc : ln(1 + e −zi ) = ln(1 + e zi ) − ln(e zi ) = ln(1 + e zi ) − zi .
Finalement :
ln(σ(zi )) = zi − ln(1 + e zi )
On a : 1
σ(zi ) = .
1 + e −zi
Donc : 1
1 − σ(zi ) = 1 − .
1 + e −zi
En mettant au même dénominateur :
1 + e −zi − 1 e −zi
1 − σ(zi ) = = .
1 + e −zi 1 + e −zi
En multipliant numérateur et dénominateur par e zi :
1
1 − σ(zi ) = .
1 + e zi
Donc : ln(1 − σ(zi )) = − ln(1 + e zi )
ln(σ(zi )) = zi − ln(1 + e zi ),
En développant :
ℓi = −yi zi + yi ln(1 + e zi ) + (1 − yi ) ln(1 + e zi ).
yi + (1 − yi ) = 1,
Comme :
on obtient : ℓi (zi ) = ln(1 + e zi ) − yi zi
On a : dℓi
= σ(zi ) − yi .
dzi
Comme yi est une constante par rapport à zi , on obtient :
d 2 ℓi
= σ ′ (zi ).
dzi2
σ ′ (zi ) = σ(zi ) 1 − σ(zi ) .
Or, pour la sigmoïde :
Donc : d 2 ℓi
1
= σ(z ) − σ(z )
dzi2
i i
☞ À retenir
La deuxième dérivée mesure la courbure. Pour montrer la convexité, on veut vérier qu'elle est
toujours positive ou nulle.
Par conséquent : d 2 ℓi
= σ(zi ) 1 − σ(zi ) ≥ 0.
dzi 2
☞ À retenir
La perte individuelle est convexe car sa deuxième dérivée est toujours positive ou nulle.
☞ À retenir
Le passage du score zi aux paramètres (w, b) ne détruit pas la convexité, car zi dépend linéairement
des paramètres.
On vient de montrer que chaque perte individuelle ℓi (w, b) est convexe en (w, b).
Or, une somme de fonctions convexes reste convexe, et multiplier par une constante positive
conserve la convexité.
Donc :
J(w, b) est convexe en (w, b).
La convexité signie qu'il n'existe pas de mauvais minimum local. Tout minimum local est global.
Cependant, cela ne garantit pas toujours l'existence d'un minimiseur ni, notamment lorsque les
classes sont parfaitement séparables.
☞ À retenir
La démonstration repose sur quatre idées :
ℓi (zi ) = ln(1 + e zi ) − yi zi .
Gradient pour erreur Peut devenir faible à cause du fac- Reste plus informatif : ce facteur
conante teur p̂(1 − p̂) supplémentaire disparaît
Usage pratique Peu utilisée pour entraîner une ré- Standard en classication binaire
gression logistique probabiliste
☞ À retenir
La cross-entropy est préférée car elle provient du maximum de vraisemblance d'un modèle de
Bernoulli, conduit à une fonction de coût convexe et donne un gradient simple.
Si X contient une colonne de 1 pour le biais et si θ = (b, w1 , . . . , wd )T , alors : ∇θ J = n1 X T (p̂ − y).
★ Pourquoi ?
Pour appliquer la descente de gradient, on met à jour les paramètres dans la direction opposée
au gradient : ∂J
w ← w − α∇w J, b ←b−α .
∂b
Il faut donc calculer les dérivées de J par rapport à chaque paramètre.
Stratégie de la démonstration :
1 Dériver la perte d'un seul exemple ℓi par rapport à la probabilité prédite : ∂ℓi
∂ p̂i .
∂ p̂i
2 Dériver la probabilité prédite par rapport au score linéaire : ∂zi , p̂i = σ(zi ).
3 Dériver le score linéaire par rapport aux paramètres :
zi = wT xi + b, ∂zi
∂wj = xij , ∂zi
∂b = 1.
4 Appliquer la règle de la chaîne : ∂ℓi
∂wj = ∂ℓi
∂ p̂i · ∂ p̂i
∂zi · ∂zi
∂wj .
∂ℓi p̂i − yi
=
∂ p̂i p̂i (1 − p̂i )
Pr. ADDOU ML Ch.3 Cross-entropy 35/62
Étape 2 : calcul de ∂ p̂i
∂zi
et règle de la chaîne
Math Dérivation par rapport à zi
P
On a : p̂i = σ(zi ).
∂ p̂i
D'après la propriété de la sigmoïde vue dans la Partie 1 : = σ(zi ) 1 − σ(zi ) = p̂i (1 − p̂i ).
∂zi
En appliquant la règle de la chaîne :
∂ℓi ∂ℓi ∂ p̂i p̂i − yi
· · 1−
p̂i ) = p̂i − yi .
= = p̂i (
∂zi ∂ p̂i ∂zi p̂
i (
1 −
p̂ i )
∂ℓi
= p̂i − yi
∂zi
☞ À retenir
Les termes p̂i (1 − p̂i ) se simplient. Le gradient par rapport au score linéaire zi devient simplement :
p̂i − yi . Ce terme représente l' erreur probabiliste entre la probabilité prédite et le label observé. Sa
forme est analogue au résidu utilisé en régression linéaire.
Comme d
X
zi = wj xij + b,
j=1
on a : ∂zi ∂zi
= xij , = 1.
∂wj ∂b
Or : ∂ℓi
= p̂i − yi .
∂zi
Donc : ∂ℓi ∂ℓi
= (p̂i − yi )xij = p̂i − yi
∂wj ∂b
☞ À retenir
Pour un exemple, le gradient est proportionnel à l'erreur probabiliste p̂i − yi .
Comme 1X
n
J(w, b) = ℓi ,
n
i=1
on obtient : ∂J 1X
n
∂J 1X
n
= (p̂i − yi )xij = (p̂i − yi )
∂wj n ∂b n
i=1 i=1
θ = (b, w1 , . . . , wd )T ,
alors : 1 T
∇θ J = X (p̂ − y) avec : p̂ = σ(X θ).
n
Prédiction ŷ = Xθ p̂ = σ(X θ)
Type de sortie Valeur réelle Probabilité de la classe positive
1 T 1 T
Gradient
nX (ŷ − y) nX (p̂ − y)
Interprétation Résidu sur une sortie réelle Erreur probabiliste
☞ À retenir
Les deux gradients ont une structure algébrique analogue : n1 X T (prédiction − valeur observée).
Mais l'interprétation change : en régression linéaire, la prédiction est une valeur réelle ; en régression
logistique, la prédiction est une probabilité. Cette forme simple vient du couple sigmoïde + cross-
entropy, issu de la log-vraisemblance négative d'un modèle de Bernoulli.
Algorithme complet
Entrées : X ∈ Rn×(d+1) avec une colonne de 1 pour le biais,
y ∈ {0, 1}n , α > 0, Tmax : nombre maximal d'itérations.
Initialisation : θ(0) = 0.
Pour t = 0, . . . , Tmax − 1 :
1 Calculer les scores linéaires : z(t) = X θ(t) .
Calculer les probabilités prédites : p̂
(t)
2 = σ(z(t) ),
où σ est appliquée élément par élément.
☞ À retenir
La boucle garde la même logique que la descente de gradient du Chapitre 2 : calcul du score,
prédiction, gradient, puis mise à jour. La diérence essentielle est que la prédiction devient probabiliste
: p̂ = σ(X θ), et que le gradient provient de la cross-entropy.
Pr. ADDOU ML Ch.3 Cross-entropy 41/62
Exemple : 4 points, 1 variable, 2 itérations
σ(0) 0.5
0.5 − 1 −0.5
Étape 4 : gradient
1
∇J = X T (p̂ − y)
4
0.5
1 1 1 1 1 0.5
=
4 −2 −1 1 2 −0.5
−0.5
1 0 0
= = .
4 −3 −0.75
Étape 5 : mise à jour
0 0 0
θ 1 = θ 0 − α∇J = − 0.5 = .
0 −0.75 0.375
0.679
0.679 − 1 −0.321
Pr. ADDOU ML Ch.3 Cross-entropy 45/62
Itération 2 gradient et mise à jour
Étape 4 : gradient
1
∇J = X T (p̂ − y)
4
0.321
1 1 0.407
1 1 1
≈
4 −2 −1 1 2 −0.407
−0.321
1 0 0
≈ = .
4 −2.098 −0.525
Étape 5 : mise à jour
0 0 0
θ 2 = θ 1 − α∇J = − 0.5 ≈ .
0.375 −0.525 0.637
Le modèle améliore progressivement ses probabilités prédites : les points négatifs reçoivent des prob-
abilités de plus en plus proches de 0, tandis que les points positifs reçoivent des probabilités de plus
en plus proches de 1.
☞ À retenir
La régularisation ne change pas le modèle probabiliste p̂i = P(Yi = 1 | xi ; w, b), mais elle modie la
fonction de coût an de pénaliser les modèles trop complexes, c'est-à-dire ceux avec des poids trop
grands.
Lasso (L1) :
d
X
JLasso (w, b) = JCE (w, b) + λ |wj |.
j=1
En général, le biais b n'est pas régularisé : la pénalité porte seulement sur les poids w1 , . . . , wd .
La régularisation est particulièrement importante lorsque les classes sont linéairement séparables :
sans pénalité, la régression logistique non régularisée peut faire diverger les poids. Augmenter leur
norme rend les probabilités de plus en plus proches de 0 ou 1.
Le premier coecient de θ ′ est nul car il correspond au biais b . En pratique, le biais n'est généralement
pas régularisé.
Exemple : En Python
for t in range(max_iter):
p_hat = sigmoid(X @ theta)
theta_pen = [Link]()
theta_pen[0] = 0 # ne pas pénaliser le biais
i yi p̂i ℓi
1 1 0.95
2 0 0.20
3 1 0.10
4 0 0.70
4 Si le modèle améliore sa prédiction pour le patient 3 de p̂3 = 0.10 à p̂3 = 0.80, calculer la nouvelle
valeur de ℓ3 . De combien la cross-entropy moyenne J diminue-t-elle ?
Jnouveau =
0.051 + 0.223 + 0.223 + 1.204
4
=
1.701
4
≈ 0.425.
La diminution de la cross-entropy moyenne est donc :
0.520
0.945
× 100 ≈ 55%.
Pr. ADDOU ML Ch.3 Cross-entropy 54/62
Exercice d'application
✎ TD Exercice 2 Une itération de descente de gradient
On considère un modèle de régression logistique avec une seule caractéristique. Les données sont normalisées
b0 0
et p̂ = P(y = 1 | x). On xe le pas d'apprentissage : α = 1. On initialise : θ0 = = .
w0 0
i xi yi
1 −1 0
2 0 0
3 +1 1
Eectuer une itération de descente de gradient :
2. Probabilités prédites
0.5
p̂= σ(z) = 0.5 .
0.5
3. Erreurs probabilistes
0.5 − 0
0.5
p̂ −y = 0.5 − 0 = 0.5 .
0.5 − 1 −0.5
1 La MSE est le critère statistique naturel pour entraîner une régression logistique.
2 La cross-entropy tend vers 0 quand le modèle attribue une probabilité proche de 1 à la classe
réellement observée.
3 Avec le couple sigmoïde + cross-entropy, le gradient a une structure algébrique analogue à celui de la
régression linéaire.
4 En régression logistique Ridge, le principe de régularisation L2 est le même qu'en régression linéaire,
mais il s'ajoute à une autre fonction de coût.
5 Sans régularisation, les poids peuvent diverger vers ±∞ si les classes sont parfaitement linéairement
séparables.
2 ✓ Vrai. y =
Si p̂ =
i 1 et ℓ = − ln( ) =
i 1, alors : i 1 0. Si yi = 0 et p̂i = 0, alors :
ℓ = − ln( − p̂ ) = − ln( ) = .
i 1 i 1 0 Ainsi, une prédiction parfaite donne une perte nulle.
3 ✓ Vrai, avec nuance. En régression linéaire, avec la convention J = 21n ∥ŷ − y∥2 , on obtient :
1 T 1 T
∇J = n X (ŷ − y). En régression logistique avec cross-entropy : ∇J = n X (p̂ − y). Les deux
gradients ont donc une structure algébrique analogue, mais l'interprétation est diérente : ŷ est une
sortie réelle, tandis que p̂ est une probabilité.
4 ✓ Vrai.
Le principe de la régularisation Ridge est le même qu'au Chapitre 2 : on ajoute une pénalité
L2 sur les poids, par exemple : 2
λ
Pd 2
j=1 wj . Cependant, cette pénalité s'ajoute ici à la , cross-entropy
alors qu'en régression linéaire elle s'ajoutait à la MSE. En général, le biais b n'est pas régularisé.
5 ✓ Vrai. Si les données sont parfaitement linéairement séparables, la régression logistique non
régularisée peut ne pas admettre de minimiseur ni : les poids peuvent croître indéniment an de
rendre les probabilités de plus en plus proches de 0 ou 1. La régularisation limite cette divergence en
pénalisant les grandes valeurs de ∥w∥.
Pr. ADDOU ML Ch.3 Cross-entropy 59/62
Récapitulatif de la Partie 2
☞ À retenir
☞ À retenir
+ λ2
Pd 2 Pd
|wj |.
Régularisation Ridge : j=1 wj ; Lasso : +λ j=1 En général, le
biais b n'est pas pénalisé.
Données séparables Sans régularisation, les poids peuvent diverger si les classes
sont linéairement séparables. La régularisation limite cette
divergence.
Pause : 10 minutes
20252026
Message clé : en classication, un modèle peut obtenir une accuracy très élevée tout en étant peu
utile pour la classe d'intérêt (ex. détection de fraude rare). Cette partie montre comment choisir des
métriques d'évaluation adaptées au problème, aux données et au coût des erreurs.
★ Le problème
Le modèle obtient 99% d'accuracy, mais il ne détecte aucune transaction frauduleuse. Les
100 fraudes sont donc toutes classées comme légitimes. Dans un contexte médical analogue,
cela reviendrait à ne détecter aucun patient malade appartenant à la classe d'intérêt.
★ Le problème
Le modèle obtient 99% d'accuracy, mais il ne détecte aucune transaction frauduleuse. Les
100 fraudes sont donc toutes classées comme légitimes. Dans un contexte médical analogue,
cela reviendrait à ne détecter aucun patient malade appartenant à la classe d'intérêt.
☞ À retenir
L'accuracy est utile, mais elle peut être insusante seule lorsque les classes sont déséquilibrées. Il
faut analyser les types d'erreurs : confondre un patient malade avec un patient sain n'a pas le même
coût que confondre un patient sain avec un patient malade.
Réel négatif (y = 0) FP TN
Faux positif Vrai négatif
Lecture : parmi les 50 patients atteints d'un cancer, le modèle en détecte 25 (TP), mais en manque 25
(FN). Parmi les 150 patients sains, il en identie correctement 145 (TN), mais classe à tort 5 patients
comme atteints d'un cancer (FP).
TP + TN 25 + 145 170
Accuracy = = = = 85%.
Total 200 200
Lecture : parmi les 50 patients atteints d'un cancer, le modèle en détecte 25 (TP), mais en manque 25
(FN). Parmi les 150 patients sains, il en identie correctement 145 (TN), mais classe à tort 5 patients
comme atteints d'un cancer (FP).
TP + TN 25 + 145 170
Accuracy = = = = 85%.
Total 200 200
Une accuracy de 85% peut sembler correcte, mais elle masque ici un problème important : 25
patients atteints d'un cancer ne sont pas détectés (FN = 25). En contexte médical, ce type
d'erreur peut avoir des conséquences graves. Il faut donc compléter l'accuracy par d'autres métriques,
comme le rappel, la précision, la spécicité et le F1-score.
☞ À retenir
Précision élevée = peu de faux positifs. Elle est importante lorsque le coût d'une fausse alerte
est élevé, par exemple lorsqu'une prédiction positive entraîne un examen invasif, un traitement inutile
ou une décision critique.
☞ À retenir
Rappel élevé = peu de faux négatifs. Il est particulièrement important lorsque manquer un
exemple positif peut avoir des conséquences graves, par exemple en détection de maladie, de fraude
ou d'anomalie critique.
☞ À retenir
Baisser le seuil augmente généralement le rappel, mais peut augmenter le nombre de fausses
alertes. Monter le seuil rend les prédictions positives plus sélectives, mais peut augmenter le
nombre de positifs manqués. Le choix du seuil dépend du contexte et du coût relatif des
faux positifs et des faux négatifs.
☞ À retenir
Règle pratique :
Si manquer un positif est plus grave qu'une fausse alerte → privilégier le rappel .
Si une fausse alerte est plus coûteuse qu'un positif manqué → privilégier la précision.
Justice Cas positif non identié Personne innocente accusée à tort Précision
Pub ciblée Client potentiel manqué Publicité envoyée à un client peu F1-score
pertinent
☞ À retenir
Règle pratique :
Si manquer un positif est plus grave qu'une fausse alerte → privilégier le rappel .
Si une fausse alerte est plus coûteuse qu'un positif manqué → privilégier la précision.
☞ À retenir
La moyenne harmonique est fortement inuencée par la plus petite des deux valeurs. Le
F1-score n'est élevé que si la précision et le rappel sont toutes les deux élevées. Il est
particulièrement utile lorsque l'on veut évaluer la performance sur la classe positive, mais il
ne tient pas compte des vrais négatifs TN .
Deux modèles peuvent être diciles à comparer à partir d'un seul seuil. La courbe ROC et l'AUC
permettent d'analyser la capacité de discrimination du modèle en considérant tous les seuils pos-
sibles.
☞ À retenir
La courbe ROC n'étudie pas un seul seuil. Elle étudie le comportement du modèle lorsque le seuil s
varie. Elle permet donc d'analyser le compromis entre la détection des positifs et la production de
faux positifs.
☞ À retenir
La courbe ROC trace :
Alors : TP = 0, FP = 0.
Donc : TPR = 0, FPR = 0.
La courbe commence au point : (0, 0).
Alors : TP = 0, FP = 0. Alors : FN = 0, TN = 0.
Donc : TPR = 0, FPR = 0. Donc : TPR = 1, FPR = 1.
La courbe commence au point : (0, 0). La courbe se termine au point : (1, 1).
Alors : TP = 0, FP = 0. Alors : FN = 0, TN = 0.
Donc : TPR = 0, FPR = 0. Donc : TPR = 1, FPR = 1.
La courbe commence au point : (0, 0). La courbe se termine au point : (1, 1).
☞ À retenir
Une courbe ROC complète commence en (0, 0) et se termine en (1, 1). Les points intermé-
diaires correspondent aux diérents seuils possibles.
0.5 at
alé Le point (1, 1) correspond au cas où tous les
exemples sont prédits positifs.
★ Dénition
L'AUC signie Area Under the Curve , c'est-à-dire l'aire sous la courbe ROC.
Mathématiquement, si la courbe ROC est vue comme une fonction reliant TPR à FPR , alors :
1
AUC =
Z
TPR(FPR) dFPR.
0
1
☞ À retenir
hasard Plus l'AUC est grande, plus la courbe ROC est
TPR
☞ À retenir
La ROC est une courbe obtenue en variant le seuil.
L'AUC est une valeur numérique qui mesure l'aire sous cette courbe :
1
AUC =
Z
TPR(FPR) dFPR.
0
Le modèle associe à chaque exemple un score p̂(x). Une paire (x + , x − ) est dite bien ordonnée si :
p̂(x + ) > p̂(x − ).
Le modèle associe à chaque exemple un score p̂(x). Une paire (x + , x − ) est dite bien ordonnée si :
p̂(x + ) > p̂(x − ).
Si le jeu de test contient n+ exemples positifs et n− exemples négatifs, alors le nombre total de paires
positifnégatif est :
n+ × n − .
L'AUC mesure la proportion de ces paires dans lesquelles le positif reçoit un score plus élevé que le
négatif.
+
, x − ) ∈ P × N : p̂(x + ) > p̂(x − )}
AUC = # {(x |P| |N |
.
+
, x − ) ∈ P × N : p̂(x + ) > p̂(x − )}
AUC = # {(x |P| |N |
.
☞ À retenir
Une AUC de 0,92 signie que, parmi tous les couples positifnégatif possibles, environ 92 % sont bien
ordonnés : le modèle attribue un score plus grand au positif qu'au négatif.
+
, x − ) ∈ P × N : p̂(x + ) > p̂(x − )}
AUC = # {(x |P| |N |
.
☞ À retenir
Une AUC de 0,92 signie que, parmi tous les couples positifnégatif possibles, environ 92 % sont bien
ordonnés : le modèle attribue un score plus grand au positif qu'au négatif.
En présence d'égalités de scores, une paire avec p̂(x + ) = p̂(x − ) est généralement comptée comme
une demi-victoire.
AUC = P
1
p̂(x + ) > p̂(x − ) + P p̂(x + ) = p̂(x − )
2
La courbe ROC étudie tous les seuils possibles. Si les exemples positifs reçoivent généralement des
scores plus élevés que les exemples négatifs, alors il existe beaucoup de seuils pour lesquels :
La courbe ROC se rapproche alors du coin supérieur gauche, et l'AUC devient grande.
AUC = P
1
p̂(x + ) > p̂(x − ) + P p̂(x + ) = p̂(x − )
2
La courbe ROC étudie tous les seuils possibles. Si les exemples positifs reçoivent généralement des
scores plus élevés que les exemples négatifs, alors il existe beaucoup de seuils pour lesquels :
La courbe ROC se rapproche alors du coin supérieur gauche, et l'AUC devient grande.
☞ À retenir
L'AUC résume donc la qualité du classement des scores, indépendamment d'un seuil particulier.
Pr. ADDOU ML Ch.3 Évaluation 26/43
Exemple 1 : AUC parfaite
Exemple : Tous les positifs sont mieux classés que les négatifs
Exemple Vraie classe Score p̂
A Positif 0.90
B Positif 0.70
C Négatif 0.40
D Négatif 0.20
0.90 > 0.40, 0.90 > 0.20, 0.70 > 0.40, 0.70 > 0.20.
☞ À retenir
Les 4 paires sur 4 sont bien ordonnées : AUC = 44 = 1. Le modèle classe parfaitement les positifs
avant les négatifs.
Pr. ADDOU ML Ch.3 Évaluation 27/43
Exemple 2 : une paire mal ordonnée
Exemple : Un positif reçoit un score plus faible qu'un
négatif
Exemple Vraie classe Score p̂
A Positif 0.90
B Positif 0.30
C Négatif 0.40
D Négatif 0.20
Exemple 2 : une paire mal ordonnée
Exemple : Un positif reçoit un score plus faible qu'un
négatif
Exemple Vraie classe Score p̂
A Positif 0.90
B Positif 0.30
C Négatif 0.40
D Négatif 0.20
☞ À retenir
Une AUC élevée signie que le modèle ordonne bien les exemples : les positifs ont tendance à recevoir
des scores plus grands que les négatifs. Cela ne signie pas automatiquement que l'accuracy sera
maximale pour n'importe quel seuil.
Stratégies courantes :
Maximiser une métrique cible : tester plusieurs seuils s sur le jeu de validation et garder celui
qui maximise la métrique choisie, par exemple le F1-score, le rappel ou la précision.
Stratégies courantes :
Maximiser une métrique cible : tester plusieurs seuils s sur le jeu de validation et garder celui
qui maximise la métrique choisie, par exemple le F1-score, le rappel ou la précision.
Stratégies courantes :
Maximiser une métrique cible : tester plusieurs seuils s sur le jeu de validation et garder celui
qui maximise la métrique choisie, par exemple le F1-score, le rappel ou la précision.
Coût applicatif : si un faux négatif est beaucoup plus coûteux qu'un faux positif, on choisit
souvent un seuil plus bas an d'augmenter le rappel. Inversement, si les faux positifs sont très
coûteux, on choisit souvent un seuil plus élevé.
Règle : le seuil de décision se choisit sur le jeu de validation, jamais sur le jeu de test. Il
doit être considéré comme un hyperparamètre du système de classication.
Exemple : Données
Dans cet exemple, la classe positive est la classe malade : y = 1 signie patient malade et y = 0 signie
patient sain. Le score p̂ représente la probabilité estimée de la classe positive.
1 1 0.95 1 ✓ TP
2 1 0.85 1 ✓ TP
3 1 0.70 1 ✓ TP
4 1 0.40 0 ✗ FN
5 1 0.30 0 ✗ FN
6 0 0.60 1 ✗ FP
7 0 0.20 0 ✓ TN
8 0 0.15 0 ✓ TN
9 0 0.10 0 ✓ TN
10 0 0.05 0 ✓ TN
Interprétation : un rappel de 60% signie que le modèle détecte 3 patients malades sur 5,
mais en manque 2. En contexte médical, ce taux de faux négatifs peut être problématique.
Si l'objectif est d'augmenter le rappel, on peut choisir un seuil plus bas, par exemple
s = 0.35. Dans ce cas, le patient 4 (p̂ = 0.40) passe de ŷ = 0 à ŷ = 1.
TP = 4, FN = 1, FP = 1, TN = 4. Le rappel devient alors : Rappel = 4+4 1 = 45 = 80%.
Cependant, le choix du seuil doit être eectué sur un jeu de validation, car modier le seuil change
aussi les autres métriques.
3 Calculer la précision. Interpréter le résultat : parmi les emails prédits comme spam, quelle proportion
est réellement un spam ?
4 Calculer le rappel. Interpréter le résultat : parmi les vrais spams, quelle proportion est correctement
détectée ?
5 Calculer le F1-score.
6 Ici, 30 emails légitimes sont envoyés à tort dans le dossier spam (FP = 30). Si l'on veut éviter de
perdre des emails professionnels importants, faut-il privilégier la précision ou le rappel ? Justier.
TP = 85 : vrais spams correctement détectés ; FP = 30 : emails légitimes classés à tort comme spams ;
TN = 370 : emails légitimes correctement classés ; FN = 15 : spams non détectés.
2.
Accuracy =
TP + TN
500
=
85 + 370
500
=
455
500
= 91%.
Cette valeur est informative, car le déséquilibre n'est pas extrême (100 spams contre 400 emails légitimes).
Cependant, elle ne sut pas à elle seule : il faut aussi regarder les faux positifs et les faux négatifs.
3.
Précision =
TP
TP + FP
=
85
85
+ 30
=
85
115
= 73.9%.
Parmi les emails prédits comme spam, environ 73.9% sont réellement des spams. Autrement dit, environ
26.1% des emails classés comme spams sont en réalité légitimes.
4.
Rappel =
TP
TP + FN
=
85
85
+ 15
=
85
100
= 85%.
Le ltre détecte 85 spams sur 100. Les 15 spams restants passent dans la boîte de réception.
6. On devrait privilégier la précision pour la classe Spam. En eet, un faux positif correspond à un email
légitime envoyé à tort dans le dossier spam. Pour des emails professionnels importants, ce type d'erreur peut
être coûteux. Il vaut donc mieux réduire les faux positifs, quitte à laisser passer quelques spams.
2 L'AUC de 0.72 du modèle B signie que, si l'on choisit au hasard un exemple positif et un exemple
négatif, le modèle B attribue un score plus élevé à l'exemple positif dans environ . . . % des cas.
4 Un modèle a une AUC égale à 0.45. Comment interpréter ce résultat ? Quelle vérication simple
peut-on faire ?
5 Pourquoi l'AUC peut-elle être plus informative que l'accuracy pour comparer deux modèles produisant
des scores ?
p̂ ′ = 1 − p̂.
1 − 0.45 = 0.55.
Cela reste faible, mais cela permet de vérier si le problème vient de l'orientation du score.
5. L'AUC peut être plus informative que l'accuracy pour comparer des modèles produisant des scores, car elle
ne dépend pas d'un seuil de décision xe. Elle résume la capacité du modèle à classer les positifs au-dessus des
négatifs. Cependant, elle ne remplace pas toujours les autres métriques : en cas de classes très déséquilibrées,
la courbe Precision-Recall et le F1-score peuvent aussi être importants.
Accuracy (TP + TN)/Total : utile, mais insusante seule si les classes sont
déséquilibrées
AUC Aire sous la courbe ROC ; mesure la capacité de discrimination des scores
Choix du seuil Se choisit sur le jeu de validation, selon l'objectif et le coût des erreurs
Pr. ADDOU ML Ch.3 Évaluation 41/43
Récapitulatif complet du Chapitre 3
✓ Odds et log-odds
✓ Descente de gradient
✓ Courbe ROC et AUC
évaluer un classieur avec la matrice de confusion, la précision, le rappel, le F1-score, la ROC et l'AUC
★ Rappel du Chapitre 3
La régression logistique linéaire, appliquée aux variables d'origine, apprend une frontière
de décision linéaire (droite en 2D, plan en 3D, hyperplan en dimension supérieure). Cette
simplicité est un avantage en termes d'interprétabilité et de coût de calcul, mais elle devient
limitante lorsque la séparation entre classes est fortement non linéaire.
x2
x2
x1
Des frontières en escalier. L'arbre peut séparer cette
x1
Une seule frontière linéaire. Elle ne peut pas séparer
correctement cette structure non linéaire. structure par des régions rectangulaires.
Pr. ADDOU ML Ch.4 Arbres de décision 3/34
La limite des modèles linéaires
☞ À retenir
Un arbre de décision standard partitionne l'espace des variables en régions rectangulaires
en 2D (et plus généralement en hyperrectangles). Il peut ainsi représenter des frontières de
décision non linéaires, contrairement à une régression logistique linéaire appliquée directement
aux variables d'origine.
Oui Non
Accepte
Achats préc. >1 ?
Oui Non
Accepte Refuse
Oui Non
Accepte
Achats préc. >1 ?
Oui Non
Accepte Refuse
☞ À retenir
Un arbre de décision applique une cascade de tests simples : la variable dépasse-t-elle un seuil
?. Chaque exemple suit un seul chemin, de la racine jusqu'à une feuille, qui fournit la prédiction
nale. L'arbre est un modèle interprétable : la prédiction peut être expliquée par la suite des tests
rencontrés sur ce chemin.
Pr. ADDOU ML Ch.4 Arbres de décision 5/34
Avantages et limites des arbres de décision
Avantages Limites
Peu sensibles à l'échelle des variables Instables : petites variations des données
peuvent changer l'arbre
Gèrent des variables numériques et caté- Frontières en escalier, parallèles aux axes
gorielles
Capturent des interactions et des non- Un arbre unique présente souvent une
linéarités forte variance
Les forêts aléatoires, étudiées en Partie 3, combinent plusieurs arbres an de réduire la variance,
l'instabilité et le risque d'overtting d'un arbre unique. Elles améliorent souvent la performance, au
prix d'une interprétabilité globale plus faible.
Racine
← n÷ud racine
Terminologie
Racine : n÷ud initial de l'arbre, où
x1 > 5 ?
Oui Non
commence la prédiction
N÷ud interne : n÷ud contenant un
test sur une variable
Classe A
n÷ud interne → x2 > 3 ?
Oui Non
Branche : issue possible d'un test, par
Classe A Classe B exemple Oui ou Non
feuilles Feuille : n÷ud terminal fournissant la
prédiction
Racine
← n÷ud racine
Terminologie
Racine : n÷ud initial de l'arbre, où
x1 > 5 ?
Oui Non
commence la prédiction
N÷ud interne : n÷ud contenant un
test sur une variable
Classe A
n÷ud interne → x2 > 3 ?
Oui Non
Branche : issue possible d'un test, par
Classe A Classe B exemple Oui ou Non
feuilles Feuille : n÷ud terminal fournissant la
prédiction
Profondeur : nombre d'arêtes du plus long chemin allant de la racine à une feuille. Taille : nombre
total de n÷uds de l'arbre. Ces deux quantités caractérisent la complexité structurelle de l'arbre :
plus elles augmentent, plus le risque d' overtting peut devenir important.
Test à un n÷ud
Pour une variable numérique xj , un test standard a la forme : xj ≤ s ? avec s ∈ R.
Le seuil s dénit une coupure entre deux sous-ensembles d'observations.
Pour une variable catégorielle, un test peut prendre la forme : xj ∈ A ?
où A est un sous-ensemble des modalités possibles de la variable.
Test à un n÷ud
Pour une variable numérique xj , un test standard a la forme : xj ≤ s ? avec s ∈ R.
Le seuil s dénit une coupure entre deux sous-ensembles d'observations.
Pour une variable catégorielle, un test peut prendre la forme : xj ∈ A ?
où A est un sous-ensemble des modalités possibles de la variable.
Convention : on dirige souvent l'observation vers la gauche si le test est vrai, et vers la
droite sinon. Cette convention peut varier selon les bibliothèques.
Test à un n÷ud
Pour une variable numérique xj , un test standard a la forme : xj ≤ s ? avec s ∈ R.
Le seuil s dénit une coupure entre deux sous-ensembles d'observations.
Pour une variable catégorielle, un test peut prendre la forme : xj ∈ A ?
où A est un sous-ensemble des modalités possibles de la variable.
Convention : on dirige souvent l'observation vers la gauche si le test est vrai, et vers la
droite sinon. Cette convention peut varier selon les bibliothèques.
Exemple : Tests valides
glucose ≤ 126 ? (variable numérique)
age ≤ 50 ? (variable numérique)
couleur ∈ {rouge, bleu} ? (variable catégorielle)
☞ À retenir
Dans un arbre de décision standard, chaque test porte sur une seule variable à la fois. Les
coupures sont donc parallèles aux axes, ce qui produit des frontières de décision en escalier.
Les tests obliques, comme x1 + x2 > 3, appartiennent à des variantes plus avancées appelées
arbres obliques.
★ Remarque importante
Un arbre de décision n'est pas nécessairement binaire. Cependant, dans les arbres standards
de type CART, très utilisés en pratique, chaque n÷ud interne eectue un test binaire et
possède donc deux branches.
★ Remarque importante
Un arbre de décision n'est pas nécessairement binaire. Cependant, dans les arbres standards
de type CART, très utilisés en pratique, chaque n÷ud interne eectue un test binaire et
possède donc deux branches.
cas typique des arbres CART et des forêts aléatoires. Avec certaines variables catégorielles, un n÷ud peut
avoir plus de deux branches, par exemple une branche
par modalité.
Pr. ADDOU ML Ch.4 Arbres de décision 10/34
Un arbre est-il toujours binaire ?
☞ À retenir
Dans ce chapitre, sauf mention contraire, on considère principalement des arbres binaires,
car les tests utilisés sont de la forme xj ≤ s ? ou xj ∈ A ?. Mais, en général, certains
algorithmes comme ID3 ou certaines variantes de C4.5 peuvent produire des arbres avec
plusieurs branches par n÷ud.
x1 ≤ 5 ? Ce qu'on observe :
Oui Non
La variable x2 apparaît dans deux
branches diérentes :
x2 ≤ 3 ? x2 ≤ 7 ?
Oui Oui
x2 ≤ 3 et x2 ≤ 7.
Non Non
Classe A
x1 ≤ 2 ?
Classe B Classe C
La variable x1 apparaît aussi deux fois sur
Oui Non
un même chemin :
Classe D Classe E x1 ≤ 5 −→ x1 ≤ 2.
☞ À retenir
La prédiction suit un seul chemin de la racine jusqu'à une feuille. Si chaque test a un coût constant,
la complexité de prédiction est
O(h),
où h est la profondeur de l'arbre. Pour un arbre bien équilibré, h peut être de l'ordre de log L, où
L est le nombre de feuilles. En revanche, un arbre très déséquilibré peut conduire à une profondeur
beaucoup plus grande.
Pr. ADDOU ML Ch.4 Arbres de décision 13/34
Exemple de prédiction détaillé
Visites site ≤3 ?
Exemple : Client A : Visites = 5,
Oui Non
Achats préc. = 3, Âge = 22
1 Racine : Visites site ≤ 3 ? 5 ≤ 3 ? Non
Âge ≤ 30 ? Achats préc. ≤1 ? → droite
Oui Non Oui Non 2 N÷ud : Achats préc. ≤ 1 ? 3 ≤ 1 ? Non
→ droite
Non Oui Non Oui
Visites site ≤3 ?
Exemple : Client A : Visites = 5,
Oui Non
Achats préc. = 3, Âge = 22
1 Racine : Visites site ≤ 3 ? 5 ≤ 3 ? Non
Âge ≤ 30 ? Achats préc. ≤1 ? → droite
Oui Non Oui Non 2 N÷ud : Achats préc. ≤ 1 ? 3 ≤ 1 ? Non
→ droite
Non Oui Non Oui
Visites site ≤3 ?
Exemple : Client B : Visites = 2,
Oui Non
Achats préc. = 5, Âge = 24
1 Racine : Visites site ≤ 3 ? 2 ≤ 3 ? Oui
Âge ≤ 30 ? Achats préc. ≤1 ? → gauche
Oui Non Oui Non 2 N÷ud : Âge ≤ 30 ? 24 ≤ 30 ? Oui →
Non Oui Non Oui
gauche
3 Feuille atteinte : Non
Dans ce chemin, le nombre d'achats précédents
n'est pas consulté. Le modèle prédit que le
client n'accepte pas l'ore, car la suite des
tests conduit à la feuilleNon.
L'arbre
x1 ≤ 4 ?
Oui Non
B
x2 ≤ 3 ?
Oui Non
A B
Oui Non B
x2
B B
x2 ≤ 3 ?
Oui Non A
A B
4
x1
Oui Non B
x2
B B
x2 ≤ 3 ?
Oui Non A
A B
4
x1
La région de classe A est : {(x1 , x2 ) : x1 ≤ 4 et x2 ≤ 3}. Les deux régions de classe B sont
distinctes dans l'espace, mais elles atteignent des feuilles portant la même étiquette. Cette partition
rectangulaire est la traduction géométrique de l'arbre.
Pr. ADDOU ML Ch.4 Arbres de décision 16/34
Comparaison des frontières : logistique vs arbre
x2
x2
ŷ = 0 ŷ = 0
x1 x1
Frontière linéaire : une droite en dimension 2. Frontière en escalier : segments parallèles aux axes.
☞ À retenir
Diérence fondamentale : une régression logistique linéaire, appliquée aux variables d'origine, pro-
duit une frontière de décision linéaire. Un arbre de décision standard produit une frontière par
morceaux, composée de segments parallèles aux axes. Avec une profondeur susante, il peut
représenter des frontières complexes par une partition en régions rectangulaires, mais cela augmente
le risque d'overtting.
Pr. ADDOU ML Ch.4 Arbres de décision 17/34
Arbre de régression : principe
★ Même structure, sortie numérique
Un arbre de régression utilise la même structure qu'un arbre de classication : des n÷uds
internes, des tests, des branches et des feuilles. La diérence est que la variable cible y est
numérique.
Classication Régression
x1 ≤ 5 ? Surface ≤ 80 ?
La feuille retourne une classe, par exemple A ou B. La feuille retourne une valeur numérique, par
exemple un prix.
☞ À retenir
Dans un arbre de régression, la prédiction d'une feuille est souvent la moyenne des valeurs cibles
des exemples d'entraînement arrivant dans cette feuille.
Ainsi, tout nouvel exemple qui arrive dans cette feuille recevra la prédiction : ŷ = 200 kMAD.
Oui Non
Âge ≤ 30 ? Ancienneté ≤2 ?
Oui Non Oui Non
x1 ≤ 4 ?
Oui Non
x2 ≤ 6 ? x2 ≤ 3 ?
Oui Non
Classe 0 Classe 1
C1
6 C0 C1
x2
3 C0
C1
4 8
x1
4. Complexité de l'arbre :
Profondeur = 3, car le plus long chemin contient trois tests.
Oui Non
Âge ≤ 30 ? Ancienneté ≤2 ?
2 Donner la classe prédite par chaque feuille avec le seuil standard 0.5.
3 Prédire la classe et la probabilité estimée pour : A : (Revenu = 2500, ge = 25, Anciennet = 5)
B : (Revenu = 4200, ge = 40, Anciennet = 4) C : (Revenu = 2500, ge = 40, Anciennet = 1)
4 Si l'on exige un seuil plus strict 0.7 pour prédire Oui, quelles prédictions obtient-on pour A, B et C ?
Pr. ADDOU ML Ch.4 Arbres de décision 29/34
✓ Solution Exercice 3 Probabilités dans les feuilles
1. Probabilité empirique dans chaque feuille :
☞ À retenir
Changer le seuil peut modier la classe prédite. Le client C illustre ce cas :
Avec un seuil plus élevé, le modèle devient plus exigeant pour prédire Oui.
Pr. ADDOU ML Ch.4 Arbres de décision 32/34
Récapitulatif de la Partie 1
☞ À retenir
Pause 10 minutes
Transition depuis la Partie 1 : dans la Partie 1, nous avons appris à lire un arbre déjà construit.
Dans cette partie, nous allons comprendre comment construire automatiquement un arbre à partir
des données.
L'idée centrale est simple : dans CART, à chaque n÷ud, on cherche le test binaire qui produit le
meilleur split, c'est-à-dire le meilleur découpage des exemples en deux groupes enfants. Un bon split
rend ces groupes les plus purs possible.
variable + split .
Pour une variable numérique, le split est souvent de la forme :
xj ≤ s ?
où s est un seuil à choisir.
Pour une variable catégorielle, le split peut être de la forme :
X ∈A ?
où A est une modalité ou un groupe de modalités.
Idée directrice : un bon test produit un bon split. Après le test, on veut que les deux groupes
enfants soient les plus purs possible, c'est-à-dire composés principalement d'une seule classe.
Entropie
Pour un groupe contenant des exemples répartis en K classes, on note pk la proportion
d'exemples appartenant à la classe k :
K
nk X
pk = et pk = 1.
n
k=1
L'entropie de Shannon est dénie par :
K
X
H=− pk log2 (pk ).
k=1
Par convention :
0 log2 (0) = 0.
☞ À retenir
L'entropie mesure le désordre ou l'incertitude dans un groupe. Elle vaut 0 lorsque le groupe est
pur.
Exemple : Calculs
Groupe pur (10 Oui, 0 Non) : p = 1
H = −1 log2 (1) − 0 = 0.
1 Propriétés de H :
Maximum : H = 1
H = 0 si le groupe est pur : p = 0 ou p = 1.
H est en binaire si le groupe est
H(p)
maximale
0.5
équilibré :
p = 0.5.
Pur Pur H est symétrique : H(p) = H(1 − p).
0
0 0.5 1
p (proportion de la classe 1)
Pour K classes, l'entropie maximale est :
Hmax = log2 (K ),
Indice de Gini
Pour un groupe contenant des exemples répartis en K classes, on note pk la proportion
d'exemples appartenant à la classe k. L' indice de Gini est déni par :
K
pk2 .
X
G =1−
k=1
☞ À retenir
L'indice de Gini mesure aussi l'impureté d'un groupe. Il vaut 0 lorsque le groupe est pur. Pour K
classes, sa valeur maximale est :
1
Gmax = 1 − ,
K
atteinte lorsque les classes sont équilibrées.
Exemple : Calculs
Groupe pur (p = 1) :
G = 1 − 12 − 02 = 0.
☞ À retenir
Le Gini est plus simple à calculer que l'entropie, car il ne contient pas de logarithme.
0.5
L'entropie atteint 1 en binaire, tandis que le Gini at-
teint 0.5. En pratique, ces deux critères conduisent
Entropie
Gini souvent à des arbres proches, mais ils ne garantissent
0 pas toujours exactement les mêmes splits.
0 0.5 1
p (proportion de la classe 1)
☞ À retenir
Avec l'entropie, on parle souvent de gain d'information.
Avec le Gini, on parle plutôt de réduction de Gini.
Dans les deux cas, CART choisit le test qui réduit le plus l'impureté.
★ Idée
Un split est utile s'il transforme un n÷ud parent mélangé en deux groupes enfants plus purs.
Dans CART, chaque test produit un split binaire :
Eg et Ed ,
de tailles respectives ng et nd .
Le gain d'information est :
Gain = H(parent) −
hn nd i
g
H(Eg ) + H(Ed ) .
n n
Le terme entre crochets est l' entropie moyenne pondérée après le split.
Pr. ADDOU ML Ch.4 Construction 10/95
Le gain d'information : mesurer l'amélioration
☞ À retenir
Un bon split est celui qui diminue fortement l'entropie :
gain élevé ⇐⇒ groupes enfants plus purs.
☞ À retenir
Dans CART, on ne choisit pas seulement une variable. On choisit le test binaire qui maximise le
gain d'information.
Autrement dit, CART choisit le meilleur couple :
variable + split .
Pour une variable numérique, un test est souvent de la forme :
xj ≤ s ?
où s est un seuil.
Pour une variable catégorielle, un test est souvent de la forme :
X ∈A ?
où A est une modalité ou un groupe de modalités.
Le test retenu est celui qui donne la plus forte réduction d'impureté.
Pr. ADDOU ML Ch.4 Construction 12/95
Cas d'une variable numérique
X ≤ s1 ?, X ≤ s2 ?, ...
X ≤s et X > s.
Gain(X , s) = H(parent) −
hn n>s i
≤s
H(E≤s ) + H(E>s ) .
n n
On garde le seuil qui donne le gain maximal :
Gain(X ) = max
s
Gain(X , s)
Pr. ADDOU ML Ch.4 Construction 13/95
Cas d'une variable numérique
☞ À retenir
Pour une variable numérique, CART cherche le meilleur seuil.
Par exemple, si :
X ∈ {A, B, C },
CART peut tester :
X ∈ {A} ? X ∈ {B} ? X ∈ {C } ?
Ces tests correspondent aux splits binaires :
☞ À retenir
Pour une variable catégorielle, CART cherche le meilleur regroupement binaire des modal-
ités.
★ Cas simple
Si une variable catégorielle possède seulement deux modalités :
X ∈ {A, B},
alors les deux tests : X =A ? et X =B ?
sont équivalents.
En eet : X =A ?
donne : branche Oui :A branche Non : B.
Tandis que : X =B ?
donne : branche Oui :B branche Non : A.
☞ À retenir
Les deux tests produisent le même split, seulement avec les branches inversées. Il sut donc de
calculer le gain d'un seul des deux tests.
Pr. ADDOU ML Ch.4 Construction 17/95
Exemple de calcul du gain d'un split binaire
☞ À retenir
Dans CART, à chaque n÷ud, on maximise le gain d'information d'un test binaire.
Pour une variable numérique, les tests possibles sont des seuils :
X ≤s ?
Pour une variable catégorielle, les tests possibles sont des regroupements binaires de modalités
:
X ∈A ?
Glouton (greedy) signie qu'à chaque n÷ud, CART choisit le meilleur test localement, sans garantir
que l'arbre nal soit globalement optimal. Cette stratégie est utilisée car elle est simple, rapide et
ecace en pratique.
Pr. ADDOU ML Ch.4 Construction 20/95
Quels sont les tests binaires candidats ?
★ Rappel
Dans CART, chaque n÷ud est binaire. L'algorithme ne choisit donc pas seulement une
variable : il choisit un test binaire, c'est-à-dire un couple :
variable + split .
☞ À retenir
Ces critères sont des hyperparamètres. Ils contrôlent la complexité de l'arbre et donc le compromis
biaisvariance. Un arbre trop profond risque l'overtting, tandis qu'un arbre trop simple risque
l'undertting. En pratique, ces hyperparamètres sont souvent choisis par validation croisée.
Pr. ADDOU ML Ch.4 Construction 22/95
Exemple complet : le jeu de données
2 2 3 3
H(Bas) = − log2 − log2 = 0.529 + 0.442 = 0.971.
5 5 5 5
3 5
Haprès split = (0) + (0.971) = 0.607.
8 8
1 1 3 3
H(Jeune) = − log2 − log2 = 0.500 + 0.311 = 0.811.
4 4 4 4
4 4
Haprès split = (0) + (0.811) = 0.406.
8 8
CART choisit le test binaire qui maximise le gain d'information. Ici, le test Âge = Vieux ? sépare
mieux ce petit jeu de données ctif que le test Glucose = Haut ?.
Après ce split :
Âge = Vieux → groupe pur : 4 Oui, 0 Non → feuille Risque Oui .
Âge = Jeune → groupe impur : 1 Oui, 3 Non → il faut continuer la construction.
Pr. ADDOU ML Ch.4 Construction 26/95
Remarque : variables catégorielles dans CART
☞ À retenir
Ici, les variables catégorielles possèdent seulement deux modalités.
Par exemple : Age ∈ {Vieux, Jeune}.
Les deux tests suivants sont donc équivalents :
Age = Vieux ? et Age = Jeune ?
Ils produisent le même split, seulement avec les branches inversées.
Si une variable catégorielle possède plus de deux modalités, par exemple :
X ∈ {A, B, C },
CART ne crée pas trois branches. Il cherche un split binaire, par exemple :
X ∈ {A} ?
ce qui donne deux groupes : {A} et {B, C }.
CART teste les regroupements binaires possibles et garde celui qui donne la plus forte réduction
d'impureté.
Pr. ADDOU ML Ch.4 Construction 27/95
Pourquoi ne pas retester Âge dans la branche Jeune ?
Après le test :
Age = Vieux ?
la branche droite correspond à :
Age = Jeune.
Dans cette branche, tous les exemples ont donc la même modalité :
Age = Jeune.
Dans CART, une variable peut être retestée plus bas seulement si elle possède encore plusieurs valeurs
possibles dans le n÷ud courant.
☞ À retenir
Ici, dans le n÷ud Âge = Jeune, la variable Âge est constante. Elle ne peut donc plus séparer les
exemples de ce n÷ud.
En revanche, une variable numérique peut souvent être retestée plus bas avec un autre seuil, car ses
valeurs peuvent rester variées dans les branches.
Haprès split = 0.
Ainsi : Gain(Glucose = Haut ?) = 0.811 − 0 = 0.811
☞ À retenir
Le split sur Glucose est parfait dans cette branche : il transforme le groupe impur en deux feuilles
pures.
Pr. ADDOU ML Ch.4 Construction 29/95
L'arbre nal
x2
x1 x1
Frontière simple : moins de variance, mais risque Frontière trop complexe : elle suit fortement les
d'undertting si l'arbre est trop simple. points du train et risque l'overtting.
Pr. ADDOU ML Ch.4 Construction 31/95
Le problème de l'overtting
☞ À retenir
Un arbre très profond a souvent un biais faible, mais une variance élevée : il devient instable
et sensible au bruit. Un arbre trop simple a moins de variance, mais peut avoir un biais plus
fort. C'est le compromis biaisvariance.
☞ À retenir
Ces hyperparamètres contrôlent la complexité de l'arbre. On les choisit souvent par validation
croisée ou sur un jeu de validation. Le jeu de test ne doit être utilisé qu'à la n, pour
l'évaluation nale.
☞ À retenir
L'objectif n'est pas d'obtenir l'arbre le plus profond possible, mais un arbre qui généralise bien. On
cherche donc un compromis entre la simplicité du modèle et sa capacité à capturer la structure des
données.
Dans CART, même si une variable catégorielle possède plusieurs modalités, on cherche toujours un
split binaire. On ne crée pas directement une branche par modalité.
Canal = Réseaux ?
Canal = Boutique ?
Chaque question produit deux groupes :
Oui au test et Non au test.
Par exemple, le test : Canal = Email ?
sépare les exemples en deux groupes :
Email et Non Email.
Pr. ADDOU ML Ch.4 Construction 38/95
Meilleur split binaire pour la variable Canal
On a :
H(racine) ≈ 0.971.
On calcule le gain des splits binaires possibles produits par Canal :
☞ À retenir
Canal = Email ?
avec un gain :
Gain = 0.420.
Pr. ADDOU ML Ch.4 Construction 39/95
Comparaison des meilleurs splits à la racine
☞ À retenir
Dans CART, on choisit toujours le meilleur test binaire. Pour une variable catégorielle avec plusieurs
modalités, on teste plusieurs regroupements binaires, puis on garde celui qui donne le gain maximal.
Pr. ADDOU ML Ch.4 Construction 40/95
Après la racine : quel groupe continuer ?
Après le split :
Canal = Email ?
on obtient deux groupes :
Canal = Email : exemples 1, 2, 3, 4
4 Oui, 0 Non.
Ce groupe est pur ⇒ feuille Achat Oui.
Canal ̸= Email : exemples 5, 6, 7, 8, 9, 10
2 Oui, 4 Non.
Ce groupe est impur ⇒ il faut continuer à le diviser.
Canal = Email ?
Email ̸= Email
Dans ce groupe :
2 Oui, 4 Non ⇒ H(parent) ≈ 0.918.
On compare maintenant les tests binaires possibles dans ce n÷ud.
Coupon = Oui ?
Coupon = Oui : exemples 7 et 8
2 Oui, 0 Non ⇒ H = 0.
Ce groupe devient une feuille Achat Oui.
Coupon = Non : exemples 5, 6, 9 et 10
0 Oui, 4 Non ⇒ H = 0.
Ce groupe devient une feuille Achat Non.
Canal = Email ?
Email ̸= Email
Lecture de l'arbre :
★ Où en sommes-nous ?
Dans la construction à la main précédente, les variables étaient catégorielles :
Dans ce cas simple, CART pouvait utiliser des tests binaires comme :
★ La question de ce complément
Pour une variable numérique xj , un test CART standard a la forme :
xj ≤ s ?
★ La question de ce complément
Pour une variable numérique xj , un test CART standard a la forme :
xj ≤ s ?
☞ À retenir
On n'a pas besoin de tester une innité de seuils. Il sut de construire un ensemble ni de seuils
candidats. Ensuite, la logique reste la même : pour chaque seuil, on calcule le gain, puis on choisit
le test binaire qui réduit le plus l'impureté.
Il sut donc de choisir un seul seuil entre 90 et 110, par exemple le milieu :
90 + 110
s= = 100.
2
☞ À retenir
Il sut de tester un seuil entre chaque paire de valeurs consécutives distinctes. Pour m
valeurs distinctes, il y a au plus m−1 seuils candidats.
On choisit généralement le milieu entre deux valeurs consécutives :
vi + vi+1
si = .
2
☞ À retenir
Pour une variable numérique, CART transforme le problème en une recherche du meilleur seuil :
xj ≤ s ?
Chaque seuil produit deux groupes, puis on choisit celui qui réduit le plus l'impureté.
i 1 2 3 4 5 6
Glucose 85 90 110 125 140 160
Risque Non Non Non Oui Oui Oui
☞ À retenir
Comme la variable Glucose est numérique, CART doit chercher le meilleur seuil dans un test de la
forme : Glucose ≤ s ?
Pr. ADDOU ML Ch.4 Construction 52/95
Seuils candidats pour la variable Glucose
85 + 90 90 + 110
s1 = = 87.5, s2 = = 100,
2 2
☞ À retenir
Chaque seuil candidat dénit un test binaire :
Glucose ≤ s ?
Pour chaque seuil, on calcule le gain d'information, puis on choisit celui qui donne le gain maximal.
85 + 90 90 + 110
s1 = = 87.5, s2 = = 100,
2 2
☞ À retenir
Chaque seuil candidat dénit un test binaire :
Glucose ≤ s ?
Pour chaque seuil, on calcule le gain d'information, puis on choisit celui qui donne le gain maximal.
★ Idée pratique
Lorsque les valeurs d'une variable numérique sont triées, les seuils les plus intéressants se
trouvent souvent aux endroits où la classe change.
Ainsi, on peut souvent réduire le nombre de seuils candidats en testant en priorité les seuils
situés entre deux exemples de classes diérentes.
Exemple : Sur notre exemple
La liste triée est : 85(N), 90(N), 110(N), 125(O), 140(O), 160(O).
Les classes changent entre 110 et 125. Le seuil candidat correspondant est :
110 + 125
s= = 117.5.
2
C'est justement ce seuil qui donne le meilleur split dans cet exemple.
Glucose ≤ 117.5 ?
Glucose ≤ 145 ?
☞ À retenir
Pour une variable numérique, l'algorithme cherche le meilleur seuil parmi un ensemble ni de seuils
candidats. Une même variable peut ensuite réapparaître plus bas dans l'arbre avec un autre seuil.
☞ À retenir
L'idée importante pour les étudiants est la suivante : CART ne teste pas une innité de seuils. Il
construit un ensemble ni de seuils candidats, puis choisit celui qui maximise la réduction d'impureté.
☞ À retenir
Variable catégorielle CART cherche un split binaire entre les modalités, par exemple
X ∈A?
Variable numérique CART cherche un seuil s dans un test de la forme xj ≤ s ?
Test produit Dans les deux cas, le test est binaire : il produit deux groupes
enfants.
Choix du test CART choisit le test qui donne la plus forte réduction
d'impureté.
Réutilisation Une variable numérique peut être retestée plus bas avec un
autre seuil.
Avec l'entropie, cette réduction correspond au gain d'information. Avec le Gini, on parle plutôt de
réduction de Gini. Dans les deux cas, l'objectif est le même : choisir le meilleur test binaire.
i 1 2 3 4
Heures de révision 2 4 6 8
Réussite Non Non Oui Oui
Gain = H(parent) −
hn nd i
Rappels : g
H(Eg ) +
H(Ed ) ,
n n
H(1 Oui, 2 Non) = H(2 Oui, 1 Non) = 0.918.
Heures ≤ 5 ?
≤5 >5
☞ À retenir
Le seuil s = 5 sépare parfaitement les deux classes. Les deux groupes enfants sont purs, donc le gain
vaut 1.
i 1 2 3 4 5 6
Âge 22 25 30 35 40 45
Achat Non Non Oui Non Oui Oui
H(3 Oui, 1 Non) = H(1 Oui, 3 Non) = 0.811, H(1 Oui, 2 Non) = H(2 Oui, 1 Non) = 0.918.
Pr. ADDOU ML Ch.4 Construction 65/95
Correction racine et seuils candidats
Après le test :
Age ≤ 27.5 ?
on obtient deux groupes :
Âge ≤ 27.5 : exemples 1 et 2
0 Oui, 2 Non.
Ce groupe est pur ⇒ feuille Achat Non.
Âge > 27.5 : exemples 3, 4, 5 et 6
3 Oui, 1 Non.
Ce groupe est impur ⇒ il faut continuer à le diviser.
Âge ≤ 27.5 ?
≤ 27.5 > 27.5
1 3
Hpond = (0) + (0.918) = 0.689.
4 4
Gain(32.5) = 0.811 − 0.689 = 0.122.
Gain du seuil s = 37.5 :
≤ 37.5 : 1 Oui, 1 Non > 37.5 : 2 Oui, 0 Non
2 2
Hpond = (1) + (0) = 0.5.
4 4
Gain(37.5) = 0.811 − 0.5 = 0.311.
Le meilleur test dans ce groupe est donc :
ge ≤ 37.5 ?
☞ À retenir
Le test suivant sera donc :
ge ≤ 32.5 ?
Pr. ADDOU ML Ch.4 Construction 71/95
Dernier split
l'entropie est :
H(1 Oui, 1 Non) = 1.
On teste :
Age ≤ 32.5 ?
Âge ≤ 32.5 : exemple 3
1 Oui, 0 Non ⇒ H = 0.
Âge > 32.5 : exemple 4
0 Oui, 1 Non ⇒ H = 0.
Les deux groupes enfants sont purs, donc :
Haprès split = 0.
Gain = 1 − 0 = 1.
☞ À retenir
Tous les groupes terminaux sont maintenant purs. On peut tracer l'arbre nal.
Pr. ADDOU ML Ch.4 Construction 72/95
Arbre nal de l'exercice 2
Âge ≤ 27.5 ?
≤ 27.5 > 27.5
☞ À retenir
Le premier split n'était pas parfait. CART continue donc uniquement sur les groupes impurs jusqu'à
obtenir des feuilles susamment pures ou jusqu'à atteindre un critère d'arrêt.
Pr. ADDOU ML Ch.4 Construction 73/95
Récapitulatif variables numériques
☞ À retenir
Étape Action
Message essentiel : gérer une variable numérique consiste à générer des seuils candidats, puis à
choisir celui qui réduit le plus l'impureté des groupes enfants.
Pr. ADDOU ML Ch.4 Construction 74/95
Exemple : arbre avec deux variables numériques
22, 25, 28, 31, 45, 50, 55, 60, 65, 70. 1, 2, 5, 6.
☞ À retenir
avec un gain :
Gain = 0.322.
Pr. ADDOU ML Ch.4 Construction 77/95
Calcul du meilleur seuil pour Visites site
☞ À retenir
Après avoir calculé le meilleur seuil de chaque variable, on compare les deux meilleurs tests
binaires :
Âge ≤ 38 et Visites site ≤ 3.5.
☞ À retenir
On ne continue pas à diviser les groupes purs. On continue seulement les groupes impurs.
Pr. ADDOU ML Ch.4 Construction 80/95
Choisir le split dans le groupe impur
Âge ≤ 38.
Ce groupe contient les exemples 1, 2, 3 et 4 :
Dans CART, à chaque nouveau n÷ud, on cherche de nouveau le meilleur couple variable + seuil.
On peut donc retester Âge, ou tester une autre variable comme Visites site.
Les deux tests donnent deux groupes purs. Ils ont donc le même gain maximal :
Gain = 1.
☞ À retenir
Dans cet exemple, il existe une égalité entre deux tests candidats. Les deux choix sont scientique-
ment corrects.
☞ À retenir
Le choix de Visites site ≤ 3.5 n'est donc pas le seul choix possible. Le test Âge ≤ 26.5 est aussi
correct.
Dans cet exemple, on garde Visites site ≤ 3.5 pour montrer qu'un arbre peut combiner plusieurs
variables numériques.
Âge ≤ 38 ?
≤ 38 > 38
☞ À retenir
Cet arbre utilise deux variables numériques : Âge à la racine, puis Visites site dans la branche
gauche.
Ce choix est possible car, dans le groupe impur, le test
Visites site ≤ 3.5 ?
donne un gain maximal.
Pr. ADDOU ML Ch.4 Construction 84/95
✎ TD Exercice 3 Arbre avec deux variables numériques
On veut prédire si un client achète un produit à partir de deux variables numériques : Distance
magasin et Visites site.
Les données sont ctives :
i Distance magasin Visites site Achat 1 Calculer l'entropie de la racine.
1 1 1 Non 2 Calculer le meilleur seuil pour Distance magasin.
2 2 6 Oui
3 3 2 Non 3 Calculer le meilleur seuil pour Visites site.
4 4 7 Oui 4 Choisir le meilleur test binaire à la racine.
5 8 1 Non
6 9 2 Non 5 Continuer la construction sur le groupe impur.
7 10 1 Non
8 11 6 Non
6 Dessiner l'arbre nal.
9 12 7 Non
10 13 7 Non
2 2 8 8
=− log2 − log2 ≈ 0.722.
10 10 10 10
☞ À retenir
H(racine) = 0.722.
Cette valeur servira à calculer les gains d'information des tests candidats.
2 Oui, 2 Non.
Ce groupe est impur ⇒ il faut continuer à le diviser.
Distance ≤ 6 ?
≤6 >6
Distance magasin ≤ 6.
Ce groupe contient les exemples 1, 2, 3 et 4 :
Dans ce nouveau n÷ud, CART recherche encore le meilleur couple variable + seuil. On compare
donc Distance magasin et Visites site.
Le meilleur gain avec Distance magasin est : Le meilleur gain avec Visites site est :
0.311. 1.
Dans le groupe impur, le meilleur test est donc : Visites site ≤ 4 ? car il donne un gain parfait :
Gain = 1.
Pr. ADDOU ML Ch.4 Construction 92/95
Arbre nal avec deux variables numériques
Distance ≤ 6 ?
≤6 >6
☞ À retenir
Cet arbre utilise deux variables numériques : Distance magasin à la racine, puis Visites site dans
la branche gauche.
Dans le groupe impur, Visites site est choisi car le test :
Visites site ≤ 4 ?
donne le gain maximal.
Pr. ADDOU ML Ch.4 Construction 93/95
Récapitulatif de la Partie 2
☞ À retenir
Concept Formule / idée
Entropie k pk log2 (pk ) ; nulle si le groupe est pur, maximale si les classes sont
P
H=−
équilibrées.
Gini G = 1 − k pk2 ; autre mesure d'impureté,plus simple à calculer que l'entropie.
P
Gain Gain = H(parent)− nng H(Eg ) + nnd H(Ed ) ; réduction d'entropie après un split
d'information binaire.
Test binaire Dans CART, chaque n÷ud choisit un test binaire de la forme xj ≤ s ? pour
une variable numérique, ou X ∈ A ? pour une variable catégorielle.
Choix du split Choisir le test binaire qui réduit le plus l'impureté des deux groupes enfants.
Algorithme Construction gloutonne et récursive : choisir le meilleur test local à chaque
n÷ud, puis continuer sur les groupes impurs.
Critères d'arrêt N÷ud pur, max_depth, min_samples_split, min_samples_leaf, améliora-
tion trop faible, etc.
Overtting Un arbre trop profond peut mémoriser les données d'entraînement, avoir une
variance élevée et mal généraliser.
Élagage Pré-élagage : limiter la croissance ; post-élagage : supprimer des branches après
construction.
Pr. ADDOU ML Ch.4 Construction 94/95
Fin de la Partie 2
Suite : Partie 3 Forêts aléatoires
Bagging (Bootstrap Aggregating)
Pause 10 minutes
20252026
Pour l'étudiant absent : un arbre seul est puissant mais instable. L'idée géniale de cette partie :
combiner des centaines d'arbres pour obtenir un modèle robuste. C'est le principe de la sagesse
des foules appliqué au machine learning.
★ Rappel de la Partie 2
Un arbre profond peut capturer des relations complexes : il a souvent un biais faible.
Mais il peut aussi avoir une variance élevée : il devient alors très sensible aux données
d'entraînement.
Résultat possible : l'arbre obtenu peut être très diérent : autre racine, autres seuils, autres branches.
B x1 ≤ 7 ?
A B
☞ À retenir
Cette instabilité correspond à une variance élevée. Une solution consiste à ne pas utiliser un seul
arbre, mais à combiner plusieurs arbres an d'obtenir une prédiction plus stable.
Pr. ADDOU ML Ch.4 Forêts aléatoires 4/39
L'idée : la sagesse des foules
★ Analogie
Pour estimer le nombre de billes dans un bocal, l'estimation d'une seule personne peut être très
imprécise. Mais si l'on moyenne les estimations de nombreuses personnes, les erreurs individuelles
peuvent se compenser.
Échantillon bootstrap
À partir d'un jeu de données contenant n exemples, un échantillon bootstrap est obtenu
en tirant n exemples avec remise.
Cela signie qu'un même exemple peut être tiré plusieurs fois, tandis que d'autres exemples
peuvent ne pas être tirés du tout.
☞ À retenir
Un échantillon bootstrap a toujours n tirages, mais il contient souvent moins de n exemples
distincts. C'est cette diérence qui permet de construire des arbres diérents.
Pour un jeu de données de grande taille, un échantillon bootstrap contient en moyenne environ :
63.2%
Pour un exemple donné, la probabilité de ne pas être tiré lors d'un tirage est :
1
1− .
n
La probabilité de ne jamais être tiré pendant les n tirages est donc :
1 n
1− .
n
Lorsque n est grand :
1 n
1
1− −→ ≈ 0.368.
n e
☞ À retenir
En moyenne, chaque arbre est entraîné sur un échantillon bootstrap et laisse de côté environ 37%
des exemples. Ces exemples OOB serviront plus tard à estimer l'erreur du modèle.
Arbre 1
bootstrap 1
bootstrap 2
Jeu de données Arbre 2 Vote / Moyenne Prédiction
bootstrap B ···
Arbre B
☞ À retenir
Comme chaque arbre est entraîné sur un échantillon bootstrap diérent, les arbres obtenus
sont généralement diérents. L'agrégation de leurs prédictions permet de réduire la variance
et de rendre le modèle plus stable.
Vote majoritaire :
3 votes Oui contre 2 votes Non.
La prédiction nale de l'ensemble est donc :
Oui .
Score de conance associé à la classe Oui :
3
p̂(Oui) = = 0.6.
5
☞ À retenir
En classication, le bagging agrège les arbres par vote majoritaire. La classe nale est celle qui
reçoit le plus grand nombre de votes.
Supposons d'abord que l'on dispose de B prédictions indépendantes, chacune ayant une
variance σ 2 . La variance de leur moyenne est alors :
B 2
!
1 X
Var B Xb = σB .
b=1
Mais attention : dans le bagging, les arbres ne sont pas totalement indépendants. Ils sont entraînés
sur des échantillons bootstrap issus du même jeu de données, donc leurs prédictions peuvent être
corrélées.
Si les arbres ont une corrélation moyenne ρ, alors la variance moyenne peut s'écrire approximativement
:
1 −ρ 2
ρσ 2 + σ .
B
Quand B augmente, le second terme diminue, mais le premier terme ρσ 2 reste présent.
☞ À retenir
Le bagging réduit surtout la variance en moyennant plusieurs arbres. Cependant, pour réduire
encore davantage la variance, il faut aussi rendre les arbres moins corrélés.
C'est exactement l'idée de la forêt aléatoire : ajouter de l'aléatoire dans le choix des variables
pour décorréler les arbres.
Valeurs usuelles de m :
en classication : √
m≈ d
par exemple, si d = 100, alors m ≈ 10 ;
en régression :
d
m≈ .
3
☞ À retenir
Une Random Forest combine deux idées :
☞ À retenir
Ces deux sources d'aléa rendent les arbres plus diérents les uns des autres. Leur corrélation moyenne
ρ diminue, ce qui permet de réduire la variance de l'ensemble.
Hyperparamètres principaux :
n_estimators : nombre d'arbres, par exemple 100, 300 ou 500 ;
max_features : nombre de variables candidates à chaque n÷ud ;
max_depth : profondeur maximale des arbres ;
min_samples_leaf : nombre minimal d'exemples dans une feuille.
Augmenter le nombre d'arbres améliore souvent la stabilité jusqu'à saturation, mais augmente
le temps de calcul.
Entraînement
Pour b = 1 à B :
1 Tirer un échantillon bootstrap de n exemples à partir du jeu de données d'entraînement.
2 Construire un arbre sur cet échantillon. À chaque n÷ud :
tirer au hasard m variables parmi les d variables disponibles ;
chercher le meilleur split uniquement parmi ces m variables ;
diviser le n÷ud selon le meilleur test trouvé.
3 Laisser l'arbre croître assez profondément, souvent sans élagage fort, an de garder un biais
faible.
Prédiction
Pour un nouvel exemple x :
Classication : chaque arbre vote pour une classe, puis on prend la classe majoritaire.
Régression : chaque arbre donne une valeur, puis on moyenne les prédictions des B arbres.
☞ À retenir
L'erreur OOB est une estimation pratique de la performance du modèle. Cependant, pour
une évaluation nale rigoureuse, un jeu de test indépendant reste préférable lorsqu'il est
disponible.
☞ À retenir
L'importance des features aide à interpréter globalement une forêt et peut guider la sélection
de features.
Mais elle ne doit pas être interprétée comme une preuve causale : une feature importante
pour le modèle n'est pas forcément une cause directe du phénomène étudié.
L'importance par réduction d'impureté est utile, mais elle a des limites.
Elle peut favoriser :
les features numériques continues ;
☞ À retenir
Il existe donc deux idées principales :
Importance par impureté : combien la feature réduit Gini ou l'entropie dans les arbres ?
Importance par permutation : combien la performance baisse si on perturbe cette feature ?
Dans les deux cas, l'importance reste une mesure d'association avec le modèle, pas une preuve
de causalité.
Type de frontière En escalier, par régions Combinaison de nom- Linéaire dans l'espace des
rectangulaires breuses frontières en features
escalier
Biais Faible si l'arbre est pro- Faible à modéré Faible si relation linéaire,
fond plus élevé si relation très non
linéaire
Variance Élevée Réduite par agrégation Généralement faible à mod-
érée
Risque d'overtting Important si arbre trop Plus robuste qu'un arbre Contrôlable par régularisa-
profond seul tion
Interprétabilité Très bonne : règles ex- Moyenne : importance Bonne : coecients inter-
plicites des features, mais beau- prétables avec prudence
coup d'arbres
Normalisation des Pas nécessaire Pas nécessaire Souvent recommandée,
features surtout avec régularisation
Temps Rapide Plus coûteux : plusieurs Rapide à modéré
d'entraînement arbres
Probabilités Proportions dans les Proportion de votes ou Probabilités via sigmoïde ou
feuilles moyenne des probabilités softmax
☞ À retenir
En résumé : un arbre seul est facile à interpréter mais instable. La Random Forest améliore la
robustesse en combinant plusieurs arbres diversiés. Elle garde une bonne capacité à capturer
des relations non linéaires, mais elle devient moins interprétable qu'un arbre unique.
La régression logistique reste un modèle simple, rapide et interprétable, mais elle est moins
adaptée si la frontière de décision est fortement non linéaire.
Avec les arbres et les forêts, il n'est généralement pas nécessaire de normaliser les features.
Patient A1 A2 A3 A4 A5 A6 A7
P1 Oui Oui Non Oui Oui Non Oui
P2 Non Non Oui Non Oui Non Non
P3 Oui Non Oui Oui Non Oui Non
1 Pour chaque patient, donner la prédiction nale de la forêt par vote majoritaire.
2 Pour chaque patient, calculer le score de conance associé à la classe Oui :
nombre d'arbres votant Oui
p̂(Oui) = .
nombre total d'arbres
3 Quel patient a la prédiction la plus incertaine ? Pourquoi ?
{1, 2, 3, 4, 5}.
Bootstrap 1 : {1, 1, 3, 4, 5} ;
Bootstrap 2 : {2, 2, 3, 3, 4} ;
Bootstrap 3 : {1, 2, 4, 5, 5}.
1 Pour chaque bootstrap, donner les exemples Out-Of-Bag (OOB), c'est-à-dire les exemples non tirés.
2 L'exemple 3 est OOB pour quel(s) arbre(s) ? Pour prédire sa classe par OOB, quels arbres feraient
voter ?
3 Théoriquement, quel pourcentage d'exemples est OOB en moyenne ? Comparer avec ce qu'on observe
ici.
3∈
/ {1, 2, 4, 5, 5}.
Donc l'exemple 3 est OOB uniquement pour l'arbre 3.
Pour prédire sa classe par OOB, on ferait voter uniquement :
l'arbre 3.
1 Augmenter le nombre d'arbres dans une forêt est généralement la principale cause du
sur-apprentissage.
2 Dans une Random Forest, on élague fortement chaque arbre.
3 La sélection aléatoire de features sert à décorréler les arbres.
4 L'erreur OOB fournit une estimation interne de la performance du modèle.
5 Une forêt a une variance plus élevée qu'un arbre seul.
6 Une forêt nécessite de normaliser les features.
Dans cette première partie, nous étudions les SVM, une famille de classieurs qui cherchent une
frontière de décision robuste, en maximisant la marge entre les classes.
Au programme :
1 La notion de marge : choisir la frontière la plus robuste ;
2 Le classieur à marge maximale et les vecteurs de support ;
3 La marge souple et le paramètre C ;
4 La hinge loss ;
5 L'astuce du noyau pour traiter les frontières non linéaires.
★ Rappel du Chapitre 3
La régression logistique apprend une frontière linéaire de la forme wT x + b = 0. Lorsque les
données sont linéairement séparables, plusieurs frontières peuvent correctement séparer les
deux classes. La question est donc : laquelle choisir ?
Plusieurs frontières possibles La frontière choisie par le SVM
marge
x2
x2
marge
frontière
x1 x1
Plusieurs droites peuvent séparer correctement les Le SVM choisit la frontière qui maximise la marge,
deux classes. Mais elles ne laissent pas toutes le c'est-à-dire l'espace libre entre les deux classes.
même espace de sécurité.
☞ À retenir
Le SVM ne cherche pas seulement une frontière qui sépare les classes. Il cherche la frontière
la plus robuste, c'est-à-dire celle qui reste la plus éloignée possible des points d'entraînement
les plus proches.
☞ À retenir
Les points entourés, situés sur les
lignes pointillées, sont les vecteurs de
marge support. Ce sont les points les plus
bords de marge proches de la frontière : ils détermi-
x2
x1
Pr. ADDOU ML Ch.5 SVM 5/37
Formalisation : l'hyperplan et la marge
f (x) = wT x + b.
ŷ = sign f (x) .
H: wT x + b = 0
est :
wT x + b
d(x, H) = .
∥w∥
Dans le cas linéairement séparable, on peut choisir l'échelle de w et b de sorte que les points
les plus proches vérient :
yi wT xi + b = 1.
yi wT xi + b ≥ 1.
☞ À retenir
Les deux bords de la marge sont les hyperplans wT x + b = +1 et wT x + b = −1. La
1
demi-marge vaut et la largeur totale de la marge vaut :
∥w∥
2
.
∥w∥
1
Ainsi, maximiser la marge revient à minimiser ∥w∥, ou plus pratiquement ∥w∥2 .
2
Vecteurs de support
Les vecteurs de support sont les points pour lesquels la contrainte est active :
yi (wT xi + b) = 1.
☞ À retenir
La frontière optimale est déterminée par les points les plus proches : les vecteurs de support. Les
points loin de la marge n'inuencent généralement pas directement l'hyperplan nal. C'est pourquoi
le SVM est souvent qualié de modèle parcimonieux.
Observation : les points de classe −1 sont sur la droite x1 = 2, tandis que les points de classe
+1 sont sur la droite x1 = 4.
Par symétrie, la meilleure frontière est donc la droite verticale située au milieu : x1 = 3.
Équation de la frontière : x1 − 3 = 0.
On peut donc prendre :
Vérication de la forme canonique : les points les plus proches doivent vérier
yi f (xi ) = 1.
Par exemple :
P1 = (2, 1), y = −1 : yf (P1 ) = (−1)(2 − 3) = 1
P3 = (4, 1), y = +1 : yf (P3 ) = (+1)(4 − 3) = 1
x2
2
largeur totale de la marge = =2;
∥w∥ 1
largeur totale = 2
vecteurs de support : les 4 points, car ils sont
tous sur les bords : |wT x + b| = 1. 0
2 3 4
☞ À retenir
La frontière est placée au milieu du couloir vide entre les deux classes. C'est le principe du SVM :
choisir l'hyperplan qui maximise la marge et reste le plus éloigné possible des points les plus proches.
Pr. ADDOU ML Ch.5 SVM 13/37
Quand les données ne sont pas séparables
☞ À retenir
Le terme C ξi pénalise les violations de marge. Le paramètre C contrôle le compromis entre une
P
i
marge large et un faible nombre de violations.
Pr. ADDOU ML Ch.5 SVM 15/37
Le rôle du paramètre C
☞ À retenir
Le paramètre C contrôle le compromis entre large marge et respect des exemples
d'entraînement. On le choisit par validation croisée, comme k , λ ou max_depth.
La quantité yf (x) mesure si le point est du bon côté de la frontière et avec quelle marge.
dans la marge.
1 log-loss Si yf (x) ≥ 1 : le point est bien classé et sur ou
au-delà de la marge, donc la hinge loss vaut 0.
☞ À retenir
Le SVM peut s'écrire sous la forme
n
1
min ∥w∥2 + C
X
max 0, 1 − yi f (xi ) .
w,b 2
i=1
Le premier terme favorise une grande marge ; le second pénalise les violations de marge.
Pr. ADDOU ML Ch.5 SVM 19/37
Les frontières non linéaires
★ Limite du SVM linéaire
Certains problèmes ne sont pas linéairement séparables dans l'espace original. Par exemple,
une classe peut se trouver au centre et l'autre autour. Dans ce cas, aucune droite ne sépare
correctement les deux classes.
L'idée est alors de transformer les données dans un espace de plus grande dimension, où
une séparation linéaire devient possible.
Espace original : non linéairement Après transformation ϕ
séparable frontière linéaire
x2
z = ∥x∥2
2
x1 En ajoutant z = ∥x∥ , les points du centre ont de
Une droite ne sut pas. Il faudrait une frontière petites valeurs de z , alors que les points extérieurs ont
circulaire. de grandes valeurs.
Pr. ADDOU ML Ch.5 SVM 20/37
Les frontières non linéaires
☞ À retenir
Transformer x en ϕ(x) permet parfois de rendre les données linéairement séparables. Mais
calculer explicitement ϕ(x) peut devenir très coûteux, surtout si l'espace transformé est de
très grande dimension.
Dans la formulation duale du SVM, le vecteur normal de l'hyperplan peut s'écrire comme une
combinaison des points d'entraînement : n
X
w= αi yi xi .
i=1
Si l'on transforme les données par une application ϕ, ces produits deviennent :
ϕ(xi )T ϕ(xj ).
Pr. ADDOU ML Ch.5 SVM 22/37
L'astuce du noyau (kernel trick)
Noyau (kernel)
Un noyau est une fonction qui calcule directement le produit scalaire dans l'espace transformé,
sans calculer explicitement ϕ(x) :
K (xi , xj ) = ϕ(xi )T ϕ(xj ).
L'astuce du noyau consiste donc à remplacer :
xT
i xj par K (xi , xj ).
☞ À retenir
Idée centrale : on travaille comme si les données avaient été projetées dans un espace de
grande dimension, mais sans construire cet espace explicitement.
Attention : pour n exemples, il faut souvent calculer de nombreuses valeurs K (xi , xj ), ce qui
peut devenir coûteux lorsque n est grand.
Noyau linéaire : simple, rapide et plus interprétable. Il est souvent ecace en grande dimension,
par exemple pour des données textuelles.
Noyau polynomial : utile lorsque l'on veut capturer des interactions non linéaires d'ordre limité.
Le degré d doit être choisi.
Noyau RBF : très courant en pratique. Le paramètre γ contrôle la portée d'inuence des points :
γ grand ⇒ inuence locale, frontière plus sinueuse ; γ petit ⇒ inuence large, frontière plus lisse.
Pr. ADDOU ML Ch.5 SVM 25/37
Les noyaux usuels
☞ À retenir
Les hyperparamètres à choisir par validation croisée sont : le type de noyau, ses paramètres
(d , c ou γ ), et le paramètre de marge C .
[Link](X_train, y_train)
y_pred = [Link](X_test)
Attention : le SVM est sensible à l'échelle des variables, car il utilise des distances ou des produits
scalaires. Il est donc important de normaliser les données, par exemple avec StandardScaler.
Le Pipeline permet d'apprendre la normalisation uniquement sur X_train, puis de l'appliquer
correctement à X_test.
Pr. ADDOU ML Ch.5 SVM 27/37
SVM : forces, faiblesses et comparaison
Forces Faiblesses
SVM vs régression logistique : les deux peuvent apprendre une frontière linéaire. La régression
logistique minimise la log-loss et fournit directement des probabilités. Le SVM, lui, cherche une
frontière à marge maximale en minimisant la hinge loss. Avec un noyau, le SVM peut aussi
produire des frontières non linéaires.
Pr. ADDOU ML Ch.5 SVM 28/37
✎ TD Exercice 1 Marge et vecteurs de support (12 min)
On considère les 4 points suivants en 2D :
Point x1 x2 y
A 1 0 −1
B 0 1 −1
C 3 0 +1
D 0 3 +1
14. Tous les points sont bien classés car yi f (xi ) > 0. De plus, tous les points vérient :
yi f (xi ) = 1.
Ils sont donc tous situés sur le bord de la marge : les 4 points sont des vecteurs de support.
√
5. ∥w∥ = 12 + 12 = 2.
p
D'après l'exercice 1 :
Point A :
yA f (A) = 1 ⇒ ℓA = max(0, 1 − 1) = 0.
Point C :
yC f (C ) = 1 ⇒ ℓC = max(0, 1 − 1) = 0.
Les points exactement sur la marge ont une perte nulle, mais ils restent importants : ce sont des vecteurs
de support.
2. Point bruité E
E = (1.5, 1), yE = −1.
f (E ) = 1.5 + 1 − 2 = 0.5.
Donc :
yE f (E ) = (−1) × 0.5 = −0.5.
Comme yE f (E ) < 0, le point E est mal classé.
Sa hinge loss est :
ℓE = max 0, 1 − yE f (E ) = max(0, 1 − (−0.5)) = 1.5.
4. Faux.
Un point bien classé et situé au-delà de la marge vérie :
yi f (xi ) ≥ 1.
Donc :
1 − yi f (xi ) ≤ 0 ⇒ ℓi = 0.
Seuls les points dans la marge ou mal classés contribuent à la hinge loss.
2 Vrai. Le noyau RBF permet de construire des frontières de décision non linéaires et très exibles.
3 Vrai. En grande dimension, notamment pour le texte, un noyau linéaire est souvent ecace, plus
rapide et plus simple à régler qu'un noyau non linéaire.
4 Faux. Dans le noyau RBF, un γ grand donne une inuence plus locale des points d'entraînement. La
frontière devient plus sinueuse, avec un risque plus élevé d'overtting. Un γ petit donne une frontière
plus lisse.
5 Vrai. Le SVM repose sur des produits scalaires, des marges et parfois des distances implicites. Si les
features ont des échelles très diérentes, certaines peuvent dominer le calcul. La normalisation est
donc nécessaire en pratique.
Marge Distance entre la frontière et les points les plus proches ; le SVM cherche à la
maximiser.
1
Marge maximale Maximiser la marge revient à minimiser ∥w∥2 sous les contraintes yi (wT xi + b) ≥
2
1.
Vecteurs de support Points situés sur les bords de la marge ; ils jouent un rôle déterminant dans la
position de la frontière.
2
Largeur totale de marge Les deux bords sont wT x + b = +1 et wT x + b = −1 ; la largeur totale vaut .
∥w∥
Marge souple Introduit des variables d'écart ξi pour autoriser certaines violations de marge.
Paramètre C C petit → violations faiblement pénalisées, marge plus large ; C grand → violations
fortement pénalisées, modèle plus exible.
Hinge loss max(0, 1 − yf (x)) ; elle est nulle pour les points bien classés sur ou au-delà de la
marge.
Kernel trick Remplace les produits scalaires xT i xj par K (xi , xj ) pour obtenir des frontières non
linéaires.
Noyaux usuels Linéaire, polynomial (xT x′ + c)d , RBF exp(−γ∥x − x′ ∥2 ).
Pause 10 minutes
Dans cette deuxième partie, nous étudions le KNN, un algorithme simple et intuitif qui classe un
nouvel exemple en regardant les exemples d'entraînement les plus proches.
Au programme :
1 Le principe du KNN : classer par ressemblance ;
2 Les distances : euclidienne, Manhattan, Minkowski, cosinus ;
3 L'importance de la normalisation des variables ;
4 Le choix de k : compromis biaisvariance ;
5 La frontière de décision et le KNN pondéré ;
6 Le KNN pour la régression, son coût et ses limites.
Contraste avec le SVM : le SVM apprend une frontière de décision pendant l'entraînement. Le
KNN, lui, ne construit pas de modèle explicite : il mémorise les données et décide au moment de la
prédiction. On dit que c'est un algorithme non paramétrique et paresseux (lazy learning).
Pr. ADDOU ML Ch.5 KNN 2/28
L'idée intuitive
★ Dis-moi qui sont tes voisins, je te dirai qui tu es
Pour classer un nouveau point, on cherche les exemples d'entraînement qui lui ressemblent le
plus, c'est-à-dire ses plus proches voisins. La classe prédite est ensuite la classe majoritaire
parmi ces voisins.
☞ À retenir
Deux choix déterminent fortement le comportement du KNN : la distance utilisée et la valeur de k .
Ces deux choix doivent être adaptés aux données.
Mesure Formule
qP
− xj′ )2
d
Euclidienne (L2 ) d(x, x′ ) = j=1 (xj
Pd
Manhattan (L1 ) d(x, x′ ) = j=1 |xj − xj′ |
P 1/p
d
Minkowski (Lp ) d(x, x′ ) = |xj − xj′ |p
j=1 (p ≥ 1)
x x
T ′
Cosinus (dissimilarité) dcos (x, x′ ) = 1 − (x, x′ ̸= 0)
∥x∥ ∥x′ ∥
Le KNN repose sur des distances. Si une variable a une grande échelle, elle peut dominer
le calcul de distance et masquer l'eet des autres variables.
Deux individus : A = (âge 30, salaire 2000), B = (âge 50, salaire 2050).
√
La distance euclidienne vaut : d(A, B) = (30 − 50)2 + (2000 − 2050)2 = 400 + 2500 ≈ 53.9.
p
La diérence d'âge est de 20 ans, ce qui est important. Pourtant, dans le calcul, elle contribue
seulement par 400, alors que la diérence de salaire de 50 kMAD contribue par 2500.
le salaire domine la distance simplement parce qu'il est mesuré sur une plus grande échelle.
☞ À retenir
Solution : normaliser les variables avant d'appliquer le KNN
P4
P1 2 3 A 4
P1 q P5
P2 1 1 A
x2
P3 4 1 A 2
4 4 B
P2 P3
P4
P5 5 3 B 0
0 2 4 6
P6 5 5 B x1
• classe A ▲ classe B ⋆ à classer
Point à classer : q = (3, 3).
P1 (A, 1.00) ≺ P4 (B, 1.41) ≺ P5 (B, 2.00) ≺ P3 (A, 2.24) ≺ {P2 (A, 2.83), P6 (B, 2.83)}.
Les points P2 et P6 sont à la même distance de q . Pour terminer l'exemple, on adopte la convention
suivante : en cas d'égalité de distance, on conserve l'ordre du tableau. Ainsi, P2 est placé avant P6 .
P1 (A, 1.00) ≺ P4 (B, 1.41) ≺ P5 (B, 2.00) ≺ P3 (A, 2.24) ≺ {P2 (A, 2.83), P6 (B, 2.83)}.
Étape 3 : vote selon k :
☞ À retenir
Le choix de k peut changer la prédiction : ici k = 1 → A, k = 3 → B et k = 5 → A. Le paramètre
k est donc un hyperparamètre important, à choisir par validation croisée. En classication binaire,
on utilise souvent un k impair pour limiter les égalités de vote, mais des égalités de distance peuvent
aussi apparaître.
Dans KNN, il n'y a pas de phase d'apprentissage de paramètres comme w et b . Le modèle mémorise
les données. Mais il faut choisir un hyperparamètre essentiel :
k = nombre de voisins utilisés pour voter.
☞ À retenir
On ne choisit pas k sur l'ensemble de test. Le test doit rester réservé à l'évaluation nale. Le choix
de k se fait sur validation ou par validation croisée.
Pr. ADDOU ML Ch.5 KNN 10/28
Le KNN pondéré (weighted KNN)
★ Tous les voisins ne se valent pas
Dans le vote simple, un voisin très proche compte autant qu'un voisin plus lointain. Le KNN
pondéré corrige cette limite en donnant plus de poids aux voisins les plus proches.
Chaque voisin i reçoit un poids qui décroît avec sa distance di au point à classer. Par exemple
:
1 1
wi = ou wi = .
d2
i di
La classe prédite est celle qui maximise la somme des poids de ses voisins :
X
ŷ = arg max wi ⊮(yi = c).
c
i∈Nk (x)
Remarque : si di = 0, le voisin est identique au point à classer ; on lui donne alors une
priorité particulière an d'éviter la division par zéro.
☞ À retenir
La pondération peut changer la décision : un voisin très proche peut peser plus fortement que
plusieurs voisins plus éloignés. Elle peut aussi limiter certains eets d'égalité, mais le choix de k reste
important.
Pour prédire une valeur numérique, on ne fait plus un vote majoritaire. On prend la
moyenne des valeurs observées chez les k plus proches voisins.
KNN régression
1 X
ŷ (x) = yi .
k
i∈Nk (x)
On peut aussi utiliser une moyenne pondérée, par exemple avec wi = 1/di :
P
i∈Nk (x) wi yi
ŷ (x) = P .
i∈Nk (x) wi
Les 3 appartements les plus similaires, selon la surface, le quartier, l'état du logement, etc., coûtent :
☞ À retenir
En classication, le KNN utilise un vote majoritaire. En régression, il utilise une moyenne. Dans
les deux cas, les choix importants restent les mêmes : distance, valeur de k et normalisation des
variables.
P
Math Complexité d'une prédiction
Pour classer un nouveau point, le KNN calcule sa distance à tous les n exemples
d'entraînement, chacun décrit par d variables :
O(n · d).
Il faut ensuite trouver les k plus proches voisins :
ou environ
O(n log k) avec une sélection partielle.
Mémoire : le KNN doit conserver les données d'entraînement, soit environ O(n · d) valeurs.
Paramètres clés : n_neighbors pour choisir k , weights pour choisir un vote uniforme ou pondéré, et metric
pour choisir la distance.
Le Pipeline est important : il apprend la normalisation sur X_train uniquement, puis l'applique correctement
à X_test. Cela évite une fuite d'information entre l'entraînement et le test.
Pr. ADDOU ML Ch.5 KNN 16/28
KNN : forces, faiblesses et comparaison
Forces Faiblesses
Très simple, intuitif et facile à expliquer Prédiction parfois lente : environ O(nd) par point
Pas d'apprentissage paramétrique complexe Mémoire importante : il faut stocker les données
d'entraînement
Frontières non linéaires naturelles Sensible aux variables non pertinentes ou bruitées
Utilisable en classication et en régression Sensible à l'échelle des variables : normalisation
nécessaire en pratique
Peu d'hyperparamètres principaux : k , dis- Se dégrade en grande dimension : éau de la di-
tance, pondération mension
Point P1 P2 P3 P4 P5 P6
(x1 , x2 ) (3, 4) ( 2, 2) (5, 3) (1, 2) ( 1, 1) (6, 3)
Classe V V R R R R
1 Calculer les distances euclidiennes entre q et chaque point. On pourra d'abord calculer d 2 , puis
prendre la racine.
2 Trier les points par distance croissante.
3 Donner la prédiction pour k = 1, k = 3 et k = 5. Que constatez-vous ?
1
4 KNN pondéré : avec k = 5 et des poids wi = di2
, calculer le poids total de chaque classe, puis donner
la décision pondérée.
5 Comparer la décision du vote simple et celle du vote pondéré pour k = 5.
√ √ √
Aide : 2 ≈ 1.41, 5 ≈ 2.24, 8 ≈ 2.83.
Pr. ADDOU ML Ch.5 KNN 18/28
✓ Solution Exercice 1 (1/3)
d(q, Pi ) = (3 − x1 )2 + (3 − x2 )2 .
p
Point Classe d2 d
3. Vote selon k
k=1 : P1 (V) ⇒ V.
40 − 20 3000 − 2000
q′ = , = (0.40, 0.25).
50 4000
38 − 20 5000 − 2000
A′ = , = (0.36, 0.75).
50 4000
70 − 20 3100 − 2000
B′ = , = (1.00, 0.275).
50 4000
q √
d(q ′ , B ′ ) = (0.40 − 1.00)2 + (0.25 − 0.275)2 = 0.36 + 0.000625 ≈ 0.601.
Après normalisation, le plus proche voisin devient A. Le 1-NN prédit donc la classe Refusé.
Conclusion : sans normalisation, le revenu domine et le voisin choisi est B. Après normalisa-
tion, les variables sont comparables et le voisin choisi devient A. La normalisation peut donc
changer la décision du KNN.
☞ À retenir
Pause 10 minutes
Une approche diérente : le SVM et le KNN raisonnent surtout en termes de géométrie (frontières,
distances, voisinage). Naive Bayes raisonne en termes de probabilités. Il estime comment les features
apparaissent dans chaque classe, puis applique le théorème de Bayes pour prendre une décision.
Pr. ADDOU ML Ch.5 Naive Bayes 2/37
Classer, c'est répondre à une question de probabilité
★ La question posée
Étant donné un exemple
x = (x1 , . . . , xd ),
quelle est la probabilité qu'il appartienne à chaque classe possible ?
On cherche donc les probabilités :
P(y | x).
La classe prédite est celle qui semble la plus probable sachant les features observées.
Diculté : on ne connaît pas directement P(y | x). Pour la calculer, Naive Bayes utilise
le théorème de Bayes, qui permet de relier cette probabilité à des quantités plus faciles à
estimer à partir des données.
P(x | y ) P(y )
P(y | x) = .
P(x)
☞ À retenir
Pour comparer les classes, P(x) est identique pour toutes les valeurs possibles de y . Il n'inuence
donc pas le arg max.
P(x | y ) = P(x1 , x2 , . . . , xd | y )
☞ À retenir
Cette hypothèse est dite naïve, car elle est souvent fausse en pratique : les features peuvent être
corrélées.
Mais elle simplie fortement le calcul : au lieu d'estimer la probabilité de toutes les combinaisons de
features, on estime séparément les probabilités de chaque feature dans chaque classe.
Astuce numérique : multiplier beaucoup de probabilités inférieures à 1 peut produire des nombres
très petits, avec un risque d'underow. En pratique, on travaille souvent avec les logarithmes :
d
X
ŷ = arg max log P(y ) + log P(xj | y ) .
y
j=1
☞ À retenir
Naive Bayes a un apprentissage très rapide : il consiste essentiellement à estimer des fréquences, des
moyennes ou des variances selon la variante utilisée. Contrairement au KNN, la prédiction est aussi
rapide, car il n'y a pas de recherche de voisins.
Lissage de Laplace
Pour éviter les probabilités nulles, on ajoute une constante α > 0 à chaque comptage.
nj,v ,y + α
P(xj = v | y ) = .
ny + αKj
☞ À retenir
Le lissage de Laplace évite les zéros qui annulent tout le produit dans Naive Bayes. Il rend le modèle
plus robuste, surtout lorsque le jeu de données est petit.
Dans scikit-learn, ce lissage est contrôlé par le paramètre alpha.
Pr. ADDOU ML Ch.5 Naive Bayes 15/37
L'eet du lissage sur l'exemple
Reclassons x′ = (Météo = Pluie, Week-end = Non)
avec le lissage de Laplace : α = 1 et K = 2 valeurs par feature.
Score de la classe Oui (4 exemples) :
SOui = P(Oui)P(Pluie | Oui)P(Week-end=Non | Oui)
1+1 0+1
= 0.5 × ×
4+2 4+2
| {z } | {z }
= 1/3 = 1/6
1 1 1
= 0.5 × × = ≈ 0.0278.
3 6 36
Score de la classe Non (4 exemples) :
SNon = P(Non)P(Pluie | Non)P(Week-end=Non | Non)
2+1 3+1
= 0.5 × ×
4+2 4+2
| {z } | {z }
= 1/2 = 2/3
1 2 1
= 0.5 × × = ≈ 0.167.
2 3 6
Pr. ADDOU ML Ch.5 Naive Bayes 16/37
L'eet du lissage sur l'exemple
☞ À retenir
Décision : Non, car
SNon > SOui .
La classe Oui n'est plus impossible : son score n'est plus nul. Le lissage corrige donc le
problème du zéro sans changer la décision du modèle sur cet exemple.
Catégoriel Valeurs discrètes non numériques Probabilités par comptage des valeurs
(couleur, oui/non, météo) dans chaque classe, avec lissage.
Bernoulli Features binaires 0/1 (présence ou Probabilité qu'une feature soit
absence) présente ou absente dans chaque
classe.
Multinomial Comptages (nombre de mots, Probabilités des mots ou des occur-
fréquences) rences dans chaque classe.
Gaussien Valeurs continues (âge, taille, score) Densité normale N (µjy , σjy2 ) estimée
dans chaque classe.
Pr. ADDOU ML Ch.5 Naive Bayes 18/37
Les variantes de Naive Bayes
☞ À retenir
Le multinomial est très utilisé en classication de texte avec une représentation bag-of-words.
Le gaussien est adapté aux features continues, en supposant que chaque feature suit une
loi normale dans chaque classe. Le catégoriel convient aux features discrètes comme dans
notre exemple.
Vraisemblance gaussienne
Pour une feature continue xj , on suppose que, dans chaque classe y , cette feature suit une loi normale
2
xj | y ∼ N (µjy , σjy ).
La vraisemblance utilisée par Naive Bayes est alors la densité :
(xj − µjy )2
!
1
f (xj | y ) = q exp − .
2πσjy2 2σjy2
☞ À retenir
Pour chaque classe, on résume la distribution de la feature par deux nombres : la moyenne µ et la
variance σ2 .
☞ À retenir
Comme SPremium > SStandard ,
Naive Bayes gaussien prédit : ŷ = Premium.
Le score 75 est plus proche de la distribution des produits Premium que de celle des produits Standard.
Pr. ADDOU ML Ch.5 Naive Bayes 22/37
Naive Bayes en pratique scikit-learn
Exemple : Choisir la classe selon le type de features
from sklearn.naive_bayes import GaussianNB, MultinomialNB, BernoulliNB, CategoricalNB
# Features continues (prix, score, taille...) :
modele = GaussianNB()
# Comptages non négatifs (ex. nombre de mots dans un texte) :
modele = MultinomialNB(alpha=1.0)
# Features binaires 0/1 (présence/absence) :
modele = BernoulliNB(alpha=1.0)
# Features catégorielles encodées en entiers :
modele = CategoricalNB(alpha=1.0)
[Link](X_train, y_train)
y_pred = [Link](X_test)
proba = modele.predict_proba(X_test)
Naive Bayes ne repose pas sur une distance : il ne demande donc pas de normalisation comme KNN.
Le paramètre alpha contrôle le lissage pour MultinomialNB, BernoulliNB et CategoricalNB.
Pour GaussianNB, on utilise plutôt le paramètre var_smoothing.
Pr. ADDOU ML Ch.5 Naive Bayes 23/37
Naive Bayes : forces, faiblesses et comparaison
Forces Faiblesses
Très rapide en apprentissage et en prédiction Hypothèse d'indépendance souvent approxi-
mative
Ecace en grande dimension, notamment Probabilités parfois mal calibrées
pour le texte
Peut fonctionner avec peu de données Sensible aux fortes corrélations entre features
Fournit des scores probabilistes par classe Naive Bayes gaussien suppose une forme nor-
male des features continues
Ne repose pas sur une distance : pas de nor- Risque de probabilités nulles sans lissage
malisation obligatoire
3 1 1
SOui = P(Oui)P(Rév=Oui | Oui)P(Mauvais | Oui) = 0.5 × × = ≈ 0.1667.
3 3 6
1 2 1
SNon = P(Non)P(Rév=Oui | Non)P(Mauvais | Non) = 0.5 × × = ≈ 0.1111.
3 3 9
4 Avec le lissage, recalculer les scores des deux classes : SOui et SNon . Donner ensuite la décision
nale.
On appliquera aussi le lissage à la classe Réussite=Non.
2 Vrai. Le terme P(x) est identique pour toutes les classes. Il ne change donc pas le résultat du arg max.
3 Vrai. Dans les variantes discrètes, ajouter α aux comptages empêche d'obtenir une probabilité nulle.
4 Faux. Naive Bayes ne repose pas sur une distance. Il n'exige donc pas une normalisation des features
comme KNN ou SVM.
5 Faux. Pour des features continues, on utilise plutôt le Naive Bayes gaussien. Le Naive Bayes
multinomial est adapté aux comptages, par exemple les occurrences de mots.
6 Vrai. Le logarithme transforme le produit en somme :
!
Y X
log P(y ) P(xj | y ) = log P(y ) + log P(xj | y ).
j j
☞ À retenir
Concept Idée clé
Approche Modèle probabiliste génératif ; décision MAP : ŷ = arg maxy P(y | x).
Théorème de Bayes P(y | x) ∝ P(x | y )P(y ) ; le terme P(x) est ignoré dans l'arg max.
Hypothèse naïve Les featuresQsont supposées indépendantes conditionnellement à la classe :
P(x | y ) = j P(xj | y ).
Règle de décision ŷ = arg maxy P(y ) j P(xj | y ).
Q
Astuce numérique Travailler en logarithme : log P(y ) + j log P(xj | y ) ; le produit devient une
P
somme.
nj,v ,y + α
Lissage de Laplace P(xj = v | y ) = ; évite les probabilités nulles.
ny + αKj
Catégoriel / Bernoulli Features discrètes ou binaires ; probabilités estimées par comptage avec lissage.
Multinomial Comptages, notamment texte et occurrences de mots.
Gaussien Features continues ; vraisemblance modélisée par une densité normale
N (µ, σ 2 ).
Atouts Très rapide, adapté à la grande dimension, souvent ecace comme baseline.
Avec les chapitres précédents, vous disposez maintenant d'une boîte à outils solide pour traiter des
problèmes de classication et de prédiction : régression linéaire, régression logistique, arbres de
décision, forêts aléatoires, SVM, KNN et Naive Bayes.
Changement de paradigme : dans les chapitres 2 à 5, on disposait de labels y pour apprendre une
relation entre les observations et leurs classes. Ici, les labels ne sont pas utilisés pendant l'apprentissage
: on cherche à découvrir une structure dans les données, par exemple des groupes d'observations
similaires. C'est l'apprentissage non supervisé.
Le clustering (partitionnement)
Regrouper les exemples en clusters tels que les points d'un même cluster soient similaires, et les
points de clusters diérents dissim similaires, sans utiliser de labels pendant l'apprentissage.
☞ À retenir
Exemples d'usage : segmentation de clients, regroupement de prols similaires, com-
pression d'images, organisation de documents. Le clustering propose une organisation des
données que l'on ne connaît pas nécessairement à l'avance.
x2
x1 x1
On observe seulement des points, sans classes connues. L'algorithme a partitionné les données en 3 clusters.
☞ À retenir
L'objectif du clustering est de regrouper automatiquement les points en groupes cohérents, de
sorte que les points d'un même groupe soient plus similaires entre eux que ceux de groupes diérents.
K-Means est l'un des algorithmes les plus utilisés pour cela.
Segmentation d'image
La segmentation d'image consiste à diviser une image en plusieurs régions homogènes, par
exemple selon la couleur, l'intensité ou la texture.
☞ À retenir
La segmentation est une application importante du clustering : elle permet de simplier une image
en regroupant automatiquement des pixels proches selon leurs caractéristiques.
2 Mise à jour : chaque centroïde est recalculé comme la moyenne des points qui lui sont
aectés.
très peu.
☞ À retenir
K est xé à l'avance par l'utilisateur : c'est un hyperparamètre. K-Means converge vers une partition
stable, qui peut dépendre de l'initialisation.
☞ À retenir
K-Means ne comprend pas le contenu sémantique de l'image : il ne sait pas identier une voiture,
une route ou un visage. Il regroupe simplement les pixels selon leur similarité numérique, par exemple
la couleur.
Pr. ADDOU ML Ch.6 K-Means 9/37
La fonction objectif : l'inertie
K-Means cherche à minimiser la somme des distances au carré entre chaque point et le
centroïde de son cluster :
K X
∥xi − µk ∥2
X
J=
k=1 xi ∈Ck
Une inertie faible signie que les clusters sont compacts : les points sont proches de leur
centroïde.
À centroïdes xés, l'étape d'aectation choisit pour chaque point le centroïde le plus proche,
donc elle ne peut pas augmenter J .
À aectations xées, l'étape de mise à jour place chaque centroïde à la moyenne des points de
son cluster, ce qui minimise la somme des carrés dans ce cluster.
Pr. ADDOU ML Ch.6 K-Means 10/37
La fonction objectif : l'inertie
☞ À retenir
À chaque itération, l'inertie J diminue ou reste inchangée. Comme il existe un nombre
ni d'aectations possibles des points aux clusters, K-Means converge en un nombre ni
d'itérations vers une partition stable. Cette solution n'est pas forcément le minimum global
de J .
A 1 1 E
B 1 2 4 D F
x2
C 2 1 2 B
D 5 4 A C
E 5 5 0
0 2 4 6
F 6 4 x1
Initialisation volontairement maladroite : on choisit deux points situés dans la même zone du
nuage :
µ1 = A = (1, 1) µ2 = C = (2, 1).
Les deux centroïdes initiaux sont donc proches l'un de l'autre. Dans cet exemple, nous allons
voir comment les aectations et les centroïdes évoluent au l des itérations.
Les centroïdes ont bougé : µ2 a été attiré vers le groupe de droite. Visuellement, le point C
semble plutôt appartenir au groupe de gauche. Dans cet exemple, l'itération suivante va modier son
aectation.
☞ À retenir
Itération 3 : les aectations ne changent plus → convergence. Dans cet exemple, K-Means obtient
une partition visuellement cohérente : C1 = {A, B, C }, C2 = {D, E , F }.
L'inertie nale vaut J = 38 ≈ 2.67.
À chaque itération, J diminue ou reste inchangée. Comme il existe un nombre ni d'aectations
possibles des points aux clusters, K-Means converge en un nombre ni d'itérations vers une partition
stable. Mais cette partition n'est pas forcément le minimum global.
Pr. ADDOU ML Ch.6 K-Means 15/37
Pourquoi l'initialisation est importante ?
★ K-Means peut converger vers des solutions diérentes
L'objectif de K-Means n'est pas convexe par rapport aux aectations des points. Donc deux initiali-
sations diérentes peuvent conduire à deux partitions diérentes, avec des inerties diérentes.
Mauvais départ possible Meilleur départ possible
µ2
µ1 µ2 µ1
Deux centroïdes peuvent être initialisés dans la même Des centroïdes initiaux mieux répartis donnent
zone. L'algorithme converge, mais le départ peut souvent une convergence plus rapide et une inertie
inuencer le résultat. nale plus faible.
☞ À retenir
Solution pratique : exécuter K-Means plusieurs fois avec des initialisations diérentes, puis garder
la solution ayant la plus faible inertie. C'est le rôle du paramètre n_init dans scikit-learn.
Pr. ADDOU ML Ch.6 K-Means 16/37
K-Means++ : l'idée intuitive
★ Choisir des centres initiaux mieux répartis
K-Means++ ne choisit pas tous les centroïdes initiaux de façon totalement uniforme au hasard. Après
avoir choisi un premier centroïde, il favorise les points qui sont loin des centroïdes déjà choisis.
Principe de K-Means++
On note D(xi ) la distance entre le point xi et le centroïde déjà choisi le plus proche.
1 Choisir le premier centroïde au hasard parmi les points.
2 Pour chaque point xi , calculer D(xi )2 .
2
3 Choisir le prochain centroïde avec une probabilité : P(xi choisi) = PD(xi ) 2 .
j D( xj)
Un point proche d'un centroïde déjà choisi a une faible probabilité d'être sélectionné. Un point éloigné
a une probabilité plus grande. Ainsi, K-Means++ réduit le risque de placer plusieurs centroïdes dans
la même zone.
Pr. ADDOU ML Ch.6 K-Means 17/37
Exemple simple de K-Means++
Exemple : Choix du deuxième centroïde
On considère cinq points sur une droite : A = 1, B = 2, C = 4, D = 8, E = 11.
Supposons que le premier centroïde choisi au hasard soit : µ1 = A = 1.
On calcule la distance au centroïde choisi le plus proche, ici seulement µ1 :
Point Position D(x) D(x)2 Probabilité
A 1 0 0 0/159
B 2 1 1 1/159
C 4 3 9 9/159
D 8 7 49 49/159
E 11 10 100 100/159
Le point E n'est pas choisi automatiquement, mais il a la probabilité la plus élevée car il est le plus
loin du premier centroïde.
★ Le problème
K doit être xé avant de lancer l'algorithme. Mais quel nombre de clusters est pertinent pour
les données ? Augmenter K ne peut pas augmenter l'inertie optimale : avec K = n, chaque
point peut former son propre cluster et on obtient J = 0. On ne peut donc pas choisir K en
minimisant simplement J .
10
Méthode du coude (elbow
8 method)
inertie J
6
Tracer l'inertie J en fonction de K . On
4
coude K = 3 cherche un coude : un point à partir
2 duquel ajouter un cluster supplémentaire
0
ne réduit plus beaucoup l'inertie. Ce
1 2 3 4 5 6 7 choix reste une heuristique.
nombre de clusters K
☞ À retenir
Avant le coude, chaque cluster supplémentaire réduit fortement l'inertie ; après le coude, le
gain devient plus faible. Une autre approche est le score de silhouette, qui mesure à la fois
la cohésion des clusters et leur séparation. Son score varie entre −1 et 1, et une valeur plus
grande indique en général un meilleur clustering.
Limite Explication
Il faut xer K Le nombre de clusters doit être choisi avant
l'apprentissage
Clusters compacts K-Means est surtout adapté aux groupes compacts, con-
vexes et de densité comparable ; il peut échouer sur
des formes allongées, imbriquées ou de densités très dif-
férentes
Sensible aux outliers La moyenne est inuencée par les points extrêmes
Sensible à l'initialisation Des initialisations diérentes peuvent conduire à des min-
ima locaux diérents (d'où n_init et K-Means++)
Sensible à l'échelle Les variables à grande échelle dominent la distance eu-
clidienne ; une normalisation est donc fortement recom-
mandée
Clusters non sphériques : si les groupes ont des formes complexes ou imbriquées, par
exemple deux croissants, K-Means peut produire une partition peu pertinente. La Partie 2
présentera DBSCAN, qui peut mieux traiter certains clusters de formes non sphériques.
☞ À retenir
Comme pour KNN et souvent pour SVM, il est important de mettre les features sur une
échelle comparable avant K-Means. Sinon, une variable numériquement plus grande peut
dominer les distances et donc inuencer fortement les clusters obtenus.
☞ À retenir
Les centroïdes achés par cluster_centers_ sont exprimés dans l'espace standardisé. Pour
les interpréter dans les unités originales, il faut appliquer l'inverse de la transformation du
StandardScaler.
Point P1 P2 P3 P4 P5 P6
(x1 , x2 ) (1, 1) (1, 3) (2, 2) (6, 2) (7, 1) (7, 3)
1 Itération 1 : aecter chaque point au centroïde le plus proche en utilisant les distances euclidiennes au
carré d 2 , puis recalculer les deux centroïdes.
2 Itération 2 : refaire l'aectation des points, puis recalculer les centroïdes.
3 Convergence : eectuer une troisième aectation pour vérier que les clusters ne changent plus.
Donner les deux clusters naux et leurs centroïdes.
Point d 2 à µ1 d 2 à µ2 Cluster
P1 = (1, 1) 0 2 1
P2 = (1, 3) 4 2 2
P3 = (2, 2) 2 0 2
P4 = (6, 2) 26 16 2
P5 = (7, 1) 36 26 2
P6 = (7, 3) 40 26 2
C1 = {P1 }, C2 = {P2 , P3 , P4 , P5 , P6 }.
Mise à jour des centroïdes :
µ1 = (1, 1)
1+2+6+7+7 3+2+2+1+3 23 11
µ2 = , = , ≈ (4.6, 2.2).
5 5 5 5
Pr. ADDOU ML Ch.6 K-Means 28/37
✓ Solution Exercice 1 (2/3)
Itération 2 µ1 = (1, 1), µ2 = (4.6, 2.2) :
Point d 2 à µ1 d 2 à µ2 Cluster
P1 = (1, 1) 0 14.4 1
P2 = (1, 3) 4 13.6 1
P3 = (2, 2) 2 6.8 1
P4 = (6, 2) 26 2.0 2
P5 = (7, 1) 36 7.2 2
P6 = (7, 3) 40 6.4 2
C1 = {P1 , P2 , P3 }, C2 = {P4 , P5 , P6 }.
L'inertie nale vaut :
16
J= ≈ 5.33.
3
P∈C1
4
Indice :
3 ≈ 1.33.
2 Par symétrie, donner l'inertie de C2 , puis l'inertie totale J .
3 On envisage maintenant K = 3. L'inertie optimale peut-elle augmenter ? Justier.
4 Pourquoi ne peut-on pas choisir K en minimisant simplement l'inertie ? Quelle méthode peut-on
utiliser ?
Pr. ADDOU ML Ch.6 K-Means 31/37
✓ Solution Exercice 2
1. µ1 = ( 43 , 2). Distances au carré :
P1 = (1, 1) :
2
(1 − 43 )2 + (1 − 2)2 = − 31 +1= 1
9 +1= 10
9 ≈ 1.111.
P2 = (1, 3) :
2
(1 − 43 )2 + (3 − 2)2 = − 13 +1= 10
9 ≈ 1.111.
P3 = (2, 2) :
2 2
(2 − 43 )2 + (2 − 2)2 = 4
≈ 0.444.
3 = 9
Donc :
10 10 4 24 8
J(C1 ) = 9 + 9 + 9 = 9 = 3 ≈ 2.667.
2. Par symétrie, le cluster C2 a la même inertie :
8
J(C2 ) = 3 ≈ 2.667.
En eet, ajouter un cluster donne plus de exibilité au modèle. L'inertie peut donc diminuer, ou rester
identique dans certains cas. À l'extrême, si K = n et si tous les points sont distincts, chaque point peut
former son propre cluster, et on obtient J = 0.
4. On ne peut pas choisir K en minimisant simplement l'inertie, car cela conduirait à choisir un nombre trop
grand de clusters, jusqu'à K = n. Ce choix n'est pas utile : il ne résume plus les données. On utilise donc des
méthodes heuristiques comme la méthode du coude, ou des critères internes comme le score de silhouette.
Pause 10 minutes
Motivation : K-Means impose de xer K et il est surtout adapté aux clusters compacts, convexes
et de densité comparable. Dans cette partie, nous étudions deux alternatives : le clustering
hiérarchique, qui construit une hiérarchie avant de choisir une coupe, et DBSCAN, qui cherche des
régions denses, peut détecter du bruit et peut mieux traiter certains clusters de forme non sphérique.
Deux formes imbriquées : avec la distance DBSCAN peut séparer des clusters de forme non
euclidienne, K-Means produit des frontières linéaires sphérique lorsqu'ils sont séparés par des zones de
par morceaux, ce qui peut donner une partition peu faible densité.
pertinente.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 3/30
Pourquoi d'autres méthodes de clustering ?
☞ À retenir
Les deux méthodes de cette partie répondent à ces limites par des approches diérentes : le
clustering hiérarchique construit une hiérarchie de fusions, tandis que DBSCAN exploite la
densité locale et peut identier des points de bruit.
☞ À retenir
Contrairement à K-Means, on ne choisit pas directement K au moment de construire la hiérarchie.
On construit d'abord le dendrogramme, puis on obtient une partition nale en le coupant a posteriori,
soit à une hauteur choisie, soit pour obtenir un nombre de clusters donné.
Ensuite, l'algorithme fusionne la paire de clus- Ensuite, l'algorithme fusionne la paire dont
ters dont cette distance minimale est la plus cette distance maximale est la plus faible.
faible. Intuition : deux clusters sont proches seule-
Intuition : il sut qu'un point de A soit proche ment si tous leurs points restent relativement
d'un point de B pour que les deux clusters soient proches.
considérés proches.
Single linkage peut produire des clusters allongés à cause de l'eet de chaîne. Complete linkage
est plus strict : il limite les clusters trop allongés et favorise souvent des groupes plus compacts.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 8/30
Comprendre les linkages (2/2) : average et Ward
Average linkage Ward linkage
Average linkage mesure la distance entre deux Ward ne regarde pas directement la distance
clusters par la moyenne des distances entre minimale, maximale ou moyenne. Il choisit la
toutes les paires de points : fusion qui provoque la plus faible augmentation
de l'inertie intra-cluster.
1 XX
Avec la distance euclidienne :
d(A, B) = d(a, b).
|A||B|
a∈A b∈B
|A||B|
∆(A, B) = ∥µ − µB ∥2 .
Ensuite, l'algorithme fusionne la paire dont |A| + |B| A
cette distance moyenne est la plus faible.
Ici, |A| et |B| désignent les nombres de points dans
Intuition : il donne une vision globale de les clusters A et B , et µA , µB leurs centroïdes.
la proximité entre deux clusters, sans regarder Intuition : Ward fusionne les clusters qui gardent
seulement le meilleur ou le pire cas. les groupes les plus compacts possible.
Average linkage est un compromis entre single et complete. Ward est souvent utilisé avec la
distance euclidienne, car il cherche à minimiser la variance intra-cluster et produit souvent des groupes
compacts.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 9/30
Les distances entre clusters (linkage)
☞ À retenir
Le choix du linkage inuence fortement le résultat. Single peut produire un eet de chaîne ; complete
favorise des clusters plus compacts ; average est un compromis ; Ward est souvent utilisé avec la
distance euclidienne car il cherche à limiter l'augmentation de la variance intra-cluster.
Dendrogramme hauteur
4
Un dendrogramme est un arbre qui représente l'ordre coupe
des fusions entre clusters. La hauteur d'une fusion 3
indique le niveau auquel deux clusters sont regroupés,
selon le critère de linkage choisi. Plus deux clusters 2
fusionnent bas, plus ils sont proches selon ce critère.
1
A B C D E
☞ À retenir
Couper le dendrogramme à une hauteur donnée dénit une partition. Ici, couper entre les hauteurs
3 et 4 donne 2 clusters :
{A, B, C } et {D, E }.
Plus on coupe haut, moins on obtient de clusters ; plus on coupe bas, plus on obtient de clusters.
A B C D E
A − 1 3 7 10
B − 2 6 9
C − 4 7
D − 3
E −
Avec le single linkage, la distance entre deux clusters est la plus petite distance entre deux points
appartenant à ces clusters.
3 D +E à hauteur 3 1
☞ À retenir
En coupant le dendrogramme entre les hauteurs 3 et 4, on obtient 2 clusters :
{A, B, C } et {D, E }.
☞ À retenir
Un point appartient à une zone dense si son voisinage de rayon ε contient au moins MinPts points.
DBSCAN ne demande pas de xer K : le nombre de clusters est déduit de la structure de densité
des données. Mais le résultat dépend fortement du choix de ε et de MinPts.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 16/30
Les trois types de points
Classication des points avec ε = 1.5 et MinPts = 4
Point c÷ur (core point) : son voisinage de rayon ε contient au moins MinPts points, en
comptant le point lui-même.
Point frontière (border point) : il n'est pas un point c÷ur, mais il appartient au voisinage
d'un point c÷ur.
Point bruit (noise point) : il n'est ni c÷ur ni frontière. Il n'est aecté à aucun cluster.
bruit
frontière
x2
c÷ur
x1
☞ À retenir
• c÷ur : point situé dans une zone dense ; • frontière : point relié à une zone dense ; • bruit :
point isolé selon les paramètres choisis. La détection des points de bruit est un atout important de
DBSCAN.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 17/30
Les trois types de points
Classication des points avec ε = 1.5 et MinPts = 4
Point c÷ur (core point) : son voisinage de rayon ε contient au moins MinPts points, en
comptant le point lui-même.
Point frontière (border point) : il n'est pas un point c÷ur, mais il appartient au voisinage
d'un point c÷ur.
Point bruit (noise point) : il n'est ni c÷ur ni frontière. Il n'est aecté à aucun cluster.
point bruit
point c÷ur
point frontière
x2
x1
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 18/30
Exemple : appliquer DBSCAN
Exemple : 6 points, ε = 1.5, MinPts = 3
On considère le voisinage de rayon ε en comptant le point lui-même. Les points sont :
A = (1, 1), B = (1, 2), C = (2, 1), D = (2, 2), E = (3.4, 2), F = (6, 6).
Faut-il xer K ? Oui Pas au départ, mais il faut Non, mais il faut choisir ε et
choisir une coupe MinPts
Forme des clusters Compacts, convexes, den- Variable selon le linkage Formes non sphériques, si les
sité comparable densités sont bien séparées
Gère le bruit ? Non Pas directement Oui : points de bruit/outliers
☞ À retenir
Quand utiliser quoi ? K-Means est adapté aux grands jeux de données avec des clusters
compacts. Le clustering hiérarchique est utile pour explorer la structure sur des jeux de
taille modérée grâce au dendrogramme. DBSCAN est utile pour des clusters de forme non
sphérique et pour la détection de bruit, mais il dépend fortement de ε et de MinPts.
Pour DBSCAN, le label -1 désigne les points de bruit. Le choix de eps est délicat : trop petit,
beaucoup de points deviennent du bruit ; trop grand, plusieurs groupes peuvent fusionner en un seul
cluster. On peut s'aider du graphe des k-distances, par exemple la distance au min_samples-ième
voisin.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 22/30
✎ TD Exercice 1 Clustering hiérarchique à la main (15 min)
On considère 5 points décrits par la matrice de distances suivante :
P1 P2 P3 P4 P5
P1 − 2 6 10 9
P2 − 5 9 8
P3 − 4 5
P4 − 3
P5 −
On applique un clustering hiérarchique agglomératif avec le single linkage, c'est-à-dire que la distance
entre deux clusters est la plus petite distance entre deux points appartenant à ces clusters.
1 Donner l'ordre des fusions et la hauteur de chaque fusion.
2 Dessiner le dendrogramme correspondant.
3 Couper le dendrogramme pour obtenir 2 clusters. Quels sont-ils ?
et d({P1 , P2 }, P3 ) = min(6, 5) = 5.
La plus petite distance est donc d(P4 , P5 ) = 3 : {P4 }, {P5 } −→ {P4 , P5 } à hauteur 3.
Étape 3 : d({P4 , P5 }, P3 ) = min(4, 5) = 4,
d({P1 , P2 }, P3 ) = min(6, 5) = 5,
d({P1 , P2 }, {P4 , P5 }) = min(10, 9, 9, 8) = 8.
La plus petite distance est 4 : {P3 }, {P4 , P5 } −→ {P3 , P4 , P5 } à hauteur 4.
Étape 4 : il reste {P1 , P2 } et {P3 , P4 , P5 }. Leur distance est min(6, 10, 9, 5, 9, 8) = 5. Fusion nale à
hauteur 5.
Pr. ADDOU ML Ch.6 Hiérarchique & DBSCAN 24/30
✓ Solution Exercice 1
2. Dendrogramme :
h
5 coupe
P1 P2 P3 P4 P5
1 Pour chaque point, compter le nombre de voisins dans le rayon ε = 2, en incluant le point lui-même.
2 Classer chaque point en c÷ur, frontière ou bruit.
3 Donner les clusters obtenus et les points de bruit.
4 Si on passait à MinPts = 5, que deviendraient les points A, B , C et D ?
√
Distances utiles : les côtés du carré valent 1 et les diagonales valent 2 ≈ 1.41.