Classification Supervisée

1 Introduction

La classification supervisée est une tâche fondamentale de l’apprentissage automatique. Son objectif est d’apprendre une fonction de mappage à partir de données d’entrée (caractéristiques) vers une sortie discrète (classe ou catégorie). Contrairement à la régression où la sortie est continue, la classification prédit une étiquette de classe.

Exemples courants :

• Filtrage des spams (spam vs non-spam)
• Diagnostic médical (malade vs non-malade)
• Reconnaissance d’images (chat, chien, voiture, etc.)
• Approbation de crédit (approuvé vs refusé)

2 Cadre Formel

Pour aborder la classification de manière rigoureuse, nous introduisons les notations et concepts suivants :

2.1 Espace d’Entrée (X)

L’espace d’entrée, noté \(\mathcal{X}\), est l’ensemble de toutes les instances ou observations possibles que notre modèle peut recevoir en entrée. Chaque instance \(x \in \mathcal{X}\) est généralement représentée par un vecteur de caractéristiques (ou features).

\[ x = (x_1, x_2, \dots, x_d) \]

Où \(d\) est le nombre de caractéristiques (la dimensionnalité de l’espace d’entrée). Ces caractéristiques peuvent être :

• Numériques : continues (ex: température, prix) ou discrètes (ex: nombre d’enfants).
• Catégorielles : nominales (ex: couleur, pays) ou ordinales (ex: niveau d’éducation).

2.2 Espace de Sortie (Y)

L’espace de sortie, noté \(\mathcal{Y}\), est l’ensemble des classes ou étiquettes possibles que notre modèle doit prédire. En classification, \(\mathcal{Y}\) est un ensemble discret et fini.

\[ \mathcal{Y} = \{c_1, c_2, \dots, c_K\} \]

Où \(K\) est le nombre de classes.

• Classification Binaire : \(K=2\). Par exemple, \(\mathcal{Y} = \{0, 1\}\) ou \(\mathcal{Y} = \{\text{spam, non-spam}\}\).
• Classification Multiclasse : \(K > 2\). Par exemple, \(\mathcal{Y} = \{\text{chat, chien, oiseau}\}\).

2.3 Ensemble de Données d’Apprentissage (D)

Nous disposons d’un ensemble de données d’apprentissage (ou training set), noté \(\mathcal{D}\), composé de \(N\) paires d’exemples :

\[\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N\]

Où \(x_i \in \mathcal{X}\) est le vecteur de caractéristiques de la \(i\)-ème instance, et \(y_i \in \mathcal{Y}\) est l’étiquette de classe correspondante (la vérité terrain).

On suppose généralement que les paires \((x_i, y_i)\) sont des réalisations indépendantes et identiquement distribuées (i.i.d.) d’une distribution de probabilité jointe inconnue \(P(X, Y)\).

2.4 Espace des Hypothèses (H)

L’espace des hypothèses, noté \(\mathcal{H}\), est l’ensemble de toutes les fonctions de classification possibles que notre algorithme d’apprentissage peut considérer. Une hypothèse \(h \in \mathcal{H}\) est une fonction qui prend une instance \(x \in \mathcal{X}\) en entrée et retourne une classe prédite \(\hat{y} \in \mathcal{Y}\).

\[ h: \mathcal{X} \rightarrow \mathcal{Y} \]

Le choix de \(\mathcal{H}\) est crucial et dépend du type de modèle utilisé (ex: classifieurs linéaires, arbres de décision, machines à vecteurs de support, réseaux de neurones).

2.5 Fonction de Perte (L)

La fonction de perte (ou loss function), notée \(L(y, \hat{y})\), mesure le coût ou l’erreur commise lorsque la vraie classe est \(y\) et que le modèle prédit \(\hat{y}\).

La fonction de perte la plus courante en classification est la perte 0-1 (zero-one loss) :

\[ L_{0-1}(y, \hat{y}) = \begin{cases} 0 & \text{si } \hat{y} = y \\ 1 & \text{si } \hat{y} \neq y \end{cases} \]

Elle pénalise toutes les erreurs de classification de manière égale. D’autres fonctions de perte existent (ex: perte logistique, perte charnière) et peuvent être plus adaptées à certains algorithmes ou pour des raisons d’optimisation.

2.6 Objectif de l’Apprentissage

L’objectif de l’apprentissage supervisé est de trouver une hypothèse \(h^* \in \mathcal{H}\) qui minimise l’erreur de généralisation (ou risque attendu) sur de nouvelles données invisibles, tirées de la même distribution \(P(X,Y)\).

Risque et Classifieur cible

• Le risque attendu (ou vraie erreur) \(R(h)\) d’une hypothèse \(h\) est défini comme l’espérance de la fonction de perte sur la distribution de données \(p(x, y)\):

\[R(h) = \mathbb{E}_{(X,Y)}[L(Y, h(X))]\]

• Le classifieur cible est \[ g^*=\arg\min_h R(h) \]

Dans la pratique, la distribution \(p(x,y)\) est inconnue. Alors nous ne pouvons pas calculer \(R(h)\) directement. À la place, nous cherchons à minimiser le risque empirique (ou erreur d’apprentissage) \(R_{emp}(h)\) sur l’ensemble d’apprentissage \(\mathcal{D}\):

\[R_{emp}(h) = \dfrac{1}{N} \sum_{i=1}^N L(y_i, h(x_i))\]

C’est le principe de la Minimisation du Risque Empirique (MRE). L’espoir est qu’une hypothèse qui performe bien sur les données d’apprentissage généralisera bien aux données non vues.

Warning

3 Concepts Clés Associés

• Frontière de Décision : La surface dans l’espace des caractéristiques \(\mathcal{X}\) qui sépare les régions assignées à différentes classes par le classifieur \(h\).
• Surapprentissage (Overfitting) : Le modèle apprend trop bien les données d’apprentissage, y compris le bruit, et performe mal sur de nouvelles données. \(R_{emp}(h)\) est faible, mais \(R(h)\) est élevé.
• Sous-apprentissage (Underfitting) : Le modèle est trop simple pour capturer la structure sous-jacente des données. \(R_{emp}(h)\) et \(R(h)\) sont tous deux élevés.
• Compromis Biais-Variance : Un concept central expliquant la tension entre la complexité du modèle et sa capacité à généraliser.
• Généralisation : La capacité du modèle à bien performer sur des données non vues après avoir été entraîné sur un ensemble de données limité.

4 Classifieur de Bayes

Le classifieur de Bayes est le classifieur idéal pour le risque 0-1: \[ g^*=\arg\min_{g}\mathbb{P}\left(g(X)\neq Y\right) \]

Il sert de référence pour évaluer la performance d’autres classifieurs.

En utilisant le théorème de Bayes, la probabilité a posteriori peut être exprimée comme suit :

\[ P(Y=c_k | X=x) = \frac{P(X=x | Y=c_k) P(Y=c_k)}{P(X=x)} \]

Où :

• \(P(Y=c_k | X=x)\) est la probabilité a posteriori : la probabilité que l’instance appartienne à la classe \(c_k\) étant donné ses caractéristiques \(x\).
• \(P(X=x | Y=c_k)\) est la vraisemblance (likelihood) : la probabilité d’observer les caractéristiques \(x\) si l’instance appartient à la classe \(c_k\).
• \(P(Y=c_k)\) est la probabilité a priori (prior) : la probabilité de la classe \(c_k\) avant d’observer les données.
• \(P(X=x)\) est la preuve (evidence) ou probabilité marginale de \(x\) : \(P(X=x) = \sum_{j=1}^K P(X=x | Y=c_j) P(Y=c_j)\).

Puisque \(P(X=x)\) est le même pour toutes les classes lors de la maximisation, la règle de décision du classifieur de Bayes peut être simplifiée en :

\[ \hat{y}_{\text{Bayes}}(x) = \underset{c_k \in \mathcal{Y}}{\operatorname{argmax}} P(X=x | Y=c_k) P(Y=c_k) \]

4.1 Erreur de Bayes

L’erreur minimale possible qui peut être atteinte par n’importe quel classifieur est appelée l’erreur de Bayes (ou taux d’erreur de Bayes). Elle est donnée par :

\[ R^* = \mathbb{E}_{X} [1 - P(Y=\hat{y}_{\text{Bayes}}(X) | X)] \]

L’erreur de Bayes est non nulle si les distributions de classes se chevauchent, c’est-à-dire s’il existe des régions de l’espace des caractéristiques où des instances de différentes classes peuvent avoir les mêmes valeurs de caractéristiques.

4.2 Importance et Limites

Le classifieur de Bayes est principalement un concept théorique car, en pratique, les distributions de probabilités \(P(X=x | Y=c_k)\) et \(P(Y=c_k)\) sont inconnues. Les algorithmes de classification (comme le Naive Bayes, les classifieurs bayésiens discriminants, etc.) tentent d’estimer ces probabilités à partir des données d’apprentissage ou de faire des hypothèses simplificatrices.

Il fournit cependant une limite inférieure théorique pour l’erreur de classification, servant de “gold standard” pour évaluer d’autres modèles.

5 Conclusion

Cette formalisation fournit un cadre unifié pour comprendre et analyser les algorithmes de classification. Elle nous permet de définir clairement le problème, les objectifs et les composants clés impliqués dans la construction de modèles de classification efficaces. Les chapitres suivants s’appuieront sur ces fondations pour explorer des algorithmes spécifiques et des techniques d’évaluation.

6 Quiz

6.1 Question 1

Quel est l’objectif principal de la classification supervisée ?

• Prédire une valeur continue pour une nouvelle observation.
• Regrouper des observations similaires en clusters.
• Apprendre une fonction qui mappe des caractéristiques d’entrée à une classe ou catégorie discrète.
• Réduire le nombre de caractéristiques dans un ensemble de données.

6.2 Question 2

Dans le cadre formel de la classification, que représente l’espace de sortie \(\mathcal{Y}\) ?

• L’ensemble de toutes les instances possibles.
• L’ensemble des caractéristiques utilisées pour décrire les instances.
• L’ensemble des classes ou étiquettes possibles que le modèle peut prédire.
• L’ensemble des fonctions de classification possibles.

6.3 Question 3

Quelle est la fonction de perte la plus courante en classification ?

• L’erreur quadratique moyenne (MSE).
• La perte absolue (MAE).
• La perte 0-1 (zero-one loss).
• La perte logistique.

6.4 Question 4

Que mesure le risque empirique \(R_{emp}(h)\) d’une hypothèse \(h\) ?

• L’erreur de généralisation attendue sur de nouvelles données.
• L’erreur moyenne commise par \(h\) sur l’ensemble d’apprentissage.
• La complexité du modèle \(h\).
• La variance des prédictions de \(h\).

6.5 Question 5

Qu’est-ce que le surapprentissage (overfitting) en classification ?

• Le modèle est trop simple et ne capture pas la structure des données.
• Le modèle apprend trop bien les données d’apprentissage, y compris le bruit, et généralise mal.
• Le modèle est incapable de faire des prédictions.
• Le modèle prend trop de temps à s’entraîner.

6.6 Question 6

Quel est le but du classifieur de Bayes ?

• Minimiser le risque empirique sur l’ensemble d’apprentissage.
• Trouver la frontière de décision la plus simple.
• Maximiser la probabilité a posteriori de la classe étant donné les caractéristiques.
• Minimiser le nombre de caractéristiques utilisées pour la classification.

6.7 Question 7

Quelle est la principale différence entre la classification binaire et la classification multiclasse ?

• La classification binaire utilise des caractéristiques numériques, tandis que la multiclasse utilise des caractéristiques catégorielles.
• La classification binaire prédit entre deux classes possibles, tandis que la multiclasse prédit parmi plus de deux classes.
• La classification binaire minimise toujours la perte 0-1, tandis que la multiclasse minimise la perte logistique.
• La classification binaire ne peut pas souffrir de surapprentissage, contrairement à la multiclasse.

6.8 Question 8

Dans la formule du classifieur de Bayes, $ _{}(x) = P(X=x | Y=c_k) P(Y=c_k) $, pourquoi le terme \(P(X=x)\) (la preuve) est-il souvent omis lors de la recherche de la classe la plus probable ?

• Parce que \(P(X=x)\) est toujours égal à 1.
• Parce que \(P(X=x)\) est inconnu et ne peut pas être estimé.
• Parce que \(P(X=x)\) est une constante pour une instance \(x\) donnée et n’affecte pas la maximisation par rapport aux classes \(c_k\).
• Parce que \(P(X=x)\) est toujours plus petit que les probabilités a priori \(P(Y=c_k)\).

6.9 Question 9

Qu’est-ce que le “compromis biais-variance” implique généralement en apprentissage supervisé ?

• Un modèle avec un biais élevé aura toujours une faible variance.
• Augmenter la complexité d’un modèle tend à diminuer le biais mais à augmenter la variance.
• Le biais et la variance peuvent être minimisés simultanément et indépendamment.
• Un modèle simple a toujours une faible variance et un faible biais.

6.10 Question 10

Si l’erreur de Bayes pour un problème de classification donné est nulle, qu’est-ce que cela implique ?

• Toutes les classes ont la même probabilité a priori.
• Les distributions de probabilités des classes \(P(X | Y=c_k)\) sont parfaitement séparables dans l’espace des caractéristiques.
• N’importe quel classifieur atteindra une erreur de 0% sur l’ensemble d’apprentissage.
• Il n’est pas nécessaire d’utiliser un ensemble de données d’apprentissage pour ce problème.

Copyright

2025 W. Toussile