Standard algorithms for machine learning

Reading time20 min

En bref

Résumé de l’article

Dans cette page, nous expliquons deux algorithmes standards pour l’apprentissage automatique, $k$-plus proches voisins (pour l’apprentissage supervisé), et $k$-moyennes (pour le clustering non supervisé).

Ces algorithmes sont parmi les exemples les plus simples en pratique, mais beaucoup d’autres existent pour l’apprentissage supervisé ou non supervisé.

Points clés

  • $k$-plus proches voisins ($k$-NN) est une méthode simple d’apprentissage supervisé qui consiste à stocker des échantillons d’un jeu de données d’entraînement, et à calculer les distances entre un nouvel exemple (inconnu) et tous les exemples du jeu d’entraînement.

  • $k$-NN fait une prédiction sur un nouvel échantillon en considérant les vraies étiquettes associées aux $k$ échantillons d’entraînement les plus proches de la requête.

  • Le clustering $k$-moyennes est une méthode itérative simple qui considère un ensemble fixe de centroïdes maximisant la variance inter-cluster.

Contenu de l’article

1 — Apprentissage supervisé

L’apprentissage supervisé est un concept fondamental en apprentissage automatique où un algorithme apprend une correspondance entre des données d’entrée $X$ et des étiquettes de sortie $y$, en utilisant un jeu de données étiqueté. L’objectif est d’apprendre une fonction $f:X \to y$ qui minimise l’erreur de prédiction sur de nouvelles données non vues. Ce type d’apprentissage est dit “supervisé” car les données d’entraînement incluent à la fois les entrées et les sorties correctes correspondantes, guidant ainsi le processus d’apprentissage.

1.1 — Formalisme

Étant donné un jeu de données $\{(x_i, y_i)\}_{i=1}^N$, où $x_i \in \mathbb{R}^d$ sont les caractéristiques d’entrée et $y_i \in \mathcal{Y}$ les étiquettes associées, l’apprentissage supervisé cherche à optimiser un modèle $f_\theta(x)$, paramétré par $\theta$, afin de minimiser une fonction de perte $\mathcal{L}(y, f_\theta(x))$.

Ici, la fonction de perte mesure l’erreur que le modèle commet sur le jeu de données d’entraînement.

Le problème d’optimisation peut être formellement exprimé comme suit : \[ \theta^* = \arg\min_\theta \frac{1}{N} \sum_{i=1}^N \mathcal{L}(y_i, f_\theta(x_i)). \]

1.2 — Types de problèmes d’apprentissage supervisé

Il existe de nombreuses tâches à résoudre en apprentissage supervisé. Voici les deux plus courantes que vous pouvez rencontrer :

  1. Classification :

    • La sortie $y$ est discrète, représentant des étiquettes de classes.
    • Exemple – Prédire si un email est “spam” ou “non spam”.
    • Fonction de perte courante – Perte d’entropie croisée pour des sorties probabilistes : \[ \mathcal{L}(y, \hat{y}) = -\frac{1}{N} \sum_{i=1}^N \sum_{c=1}^C y_{i,c} \log(\hat{y}_{i,c}), \] où $C$ est le nombre de classes, $y_{i,c}$ est une étiquette encodée en one-hot, et $\hat{y}_{i,c}$ est la probabilité prédite pour la classe $c$.

  2. Régression :

    • La sortie $y$ est continue, représentant des valeurs numériques.
    • Exemple – Prédire les prix des maisons en fonction de caractéristiques comme la taille et la localisation.
    • Fonction de perte courante – Erreur quadratique moyenne (MSE) : \[ \mathcal{L}(y, \hat{y}) = \frac{1}{N} \sum_{i=1}^N (y_i - \hat{y}_i)^2. \]

1.3 — L’algorithme des $k$-plus proches voisins

L’algorithme des $k$-plus proches voisins ($k$-NN) est une méthode d’apprentissage supervisé sans paramètre utilisée à la fois pour la classification et la régression. Il prédit la sortie pour un point de requête donné en se basant sur les $k$ échantillons d’entraînement les plus proches dans l’espace des caractéristiques.

Voici un pseudo-code de l’algorithme :

​
Input:
    - Training dataset: {(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)}
    - Query point: q
    - Number of neighbors: k
    - Distance metric: d(·, ·)

Output:
    - Predicted label (classification) or value (regression) for q

--

Steps:

    1. (compute distances):
        - For each training point (x_i, y_i), calculate d(q, x_i).

    2. (Find k nearest neighbors)
        - Identify the k training points with the smallest distances to q.

    3. (make a prediction):
        - If classification, perform a majority vote among the labels of the k nearest neighbors.
        - If regression, compute the average of the labels of the k nearest neighbors.

    4. (return the prediction)

1.4 — Remarques sur $k$-NN

1.4.1 — Métrique de distance

Le choix de la métrique de distance impacte significativement la performance. Les choix courants incluent :

  • Distance euclidienne : \[ d(q, x_i) = \sqrt{\sum_{j=1}^d (q_j - x_{i,j})^2}. \]

  • Distance de Manhattan : \[ d(q, x_i) = \sum_{j=1}^d |q_j - x_{i,j}|. \]

1.4.2 — Influence de $k$

Un petit $k$ (par exemple, $k = 1$) peut conduire à un surapprentissage. Cela signifie que le modèle devient trop spécialisé sur le jeu d’entraînement, mais a une mauvaise capacité de généralisation sur de nouvelles données.

À l’inverse, un grand $k$ lisse les prédictions mais peut perdre des détails locaux.

1.4.3 — Complexité

La complexité d’entraînement est $O(1)$ puisqu’elle consiste à stocker le jeu de données (pour l’utiliser comme points de référence).

La complexité de prédiction est $O(Nd)$ par point de requête, ce qui rend l’algorithme coûteux en calcul pour de grands jeux de données ($N$ calculs de distance entre des vecteurs de dimension $d$).

Information

Notez que $k$ n’est pas un paramètre appris par l’algorithme, mais doit être donné a priori. $k$-NN est en fait sans paramètre, mais nécessite tout de même une phase d’entraînement pour stocker les échantillons du jeu d’entraînement.

$k$ est appelé un hyper-paramètre (différent des paramètres $\theta$ de $f_\theta$ qui peuvent être appris).

2 — Apprentissage non supervisé

L’apprentissage non supervisé est un type d’apprentissage automatique où l’algorithme apprend des motifs ou structures dans les données sans sorties étiquetées. Contrairement à l’apprentissage supervisé, où l’objectif est de prédire des résultats, l’apprentissage non supervisé vise à découvrir des structures cachées, des regroupements ou des représentations dans les données d’entrée. Il est particulièrement utile pour l’analyse exploratoire des données, l’extraction de caractéristiques et la réduction de dimensionnalité.

2.1 — Formalisme

Étant donné un jeu de données $\{x_i\}_{i=1}^N$, où $x_i \in \mathbb{R}^d$, l’apprentissage non supervisé cherche à découvrir des structures ou représentations qui décrivent au mieux les données. Selon la tâche, cela implique d’optimiser différents types de fonctions objectifs. Globalement, ces tâches se répartissent en deux grandes catégories :

  1. Clustering – Partitionner les données en $k$ clusters, où des points de données similaires sont regroupés ensemble. Formellement, l’objectif est d’assigner chaque point de données $x_i$ à un cluster $C_k$ tel qu’une métrique de similarité ou de distance (par exemple, distance euclidienne) soit minimisée à l’intérieur des clusters et maximisée entre les clusters.

    Exemple de fonction objectif pour le clustering : \[ \text{Minimiser } \sum_{k=1}^K \sum_{x_i \in C_k} \|x_i - \mu_k\|^2, \] où $\mu_k$ est le centroïde du cluster $C_k$.

  2. Décomposition / Apprentissage de variété – Apprendre une représentation de dimension inférieure des données qui capture leur structure intrinsèque. Cela implique souvent d’approximer les données à l’aide d’un ensemble de vecteurs de base ou de mappings non linéaires.

    Exemple de fonction objectif pour la réduction de dimension : \[ \text{Minimiser l'erreur de reconstruction : } \sum_{i=1}^N \|x_i - \hat{x}_i\|^2, \] où $\hat{x}_i$ est l’entrée reconstruite à partir de la représentation apprise.

2.2 — Algorithme des $k$-moyennes

L’algorithme des $k$-moyennes vise à partitionner $N$ points de données en $k$ clusters en minimisant la variance intra-cluster.

Voici un pseudo-code :

​
Input:
    - Dataset: {x_1, x_2, ..., x_N}, where x_i ∈ ℝ^d
    - Number of clusters: K
    - Convergence threshold: ε (e.g., 10^-4)

Output:
    - K cluster centroids {μ_1, μ_2, ..., μ_K} and cluster assignments {C_1, C_2, ..., C_K}

--

Steps:

    1. (initialize centroids):
        - Randomly select K data points as the initial centroids {μ_1, μ_2, ..., μ_K}.

    2. (repeat until convergence):
    |
    |   a. (assign points to nearest centroid):
    |       - For each data point x_i:
    |       - Assign x_i to the cluster C_k where k = argmin_j ||x_i - μ_j||^2.
    |
    |   b. (update centroids):
    |       - For each cluster C_k, recompute the centroid:
    |       - Set μ_k = (1 / |C_k|) Σ_{x_i ∈ C_k} x_i.
    |
    |   c. Check for convergence:
    |       - Compute the change in centroids Δ = Σ_k ||μ_k^new - μ_k^old||.
    |       - If Δ < ε, stop the iteration.

    3. (return the final centroids and cluster assignments)

2.3 — Remarques sur $k$-moyennes

L’algorithme peut rester bloqué dans des minima locaux selon l’initialisation des centroïdes. Des techniques comme “$k$-means++”" améliorent l’initialisation en sélectionnant des centroïdes bien répartis.

La complexité computationnelle est $O(NKId)$, où $I$ est le nombre d’itérations.

$k$-means fonctionne mieux lorsque les clusters sont à peu près sphériques et séparables dans l’espace des caractéristiques.

Pour aller plus loin

3 — Prétraitement des caractéristiques

En général, les caractéristiques doivent être normalisées ou standardisées si elles ont des échelles différentes afin d’assurer une contribution équitable aux calculs de distance. Cela s’appelle le prétraitement des caractéristiques, et c’est très standard lors de l’application de ML sur un nouveau jeu de données. Consultez cet ensemble de techniques décrites sur feature preprocessing using sklearn.

Une autre étape importante avant d’appliquer des algorithmes ML est la sélection des caractéristiques. Quelques exemples d’approches simples pour la sélection de caractéristiques :

  • Suppression des caractéristiques à faible variance (par exemple, suppression basée sur un seuil de variance).
  • Sélection des caractéristiques utilisant des statistiques sur le jeu de données (par exemple, sélectionner les caractéristiques ayant une relation linéaire significative avec les changements d’étiquettes).

4 — Autres algorithmes d’apprentissage supervisé

En plus de $k$-NN, voici quelques algorithmes courants d’apprentissage supervisé. La liste n’est évidemment pas exhaustive.

  1. Régression linéaire :

    • Utilisée pour les tâches de régression.
    • Apprend une correspondance linéaire des caractéristiques d’entrée vers des sorties continues.

  2. Régression logistique :

    • Utilisée pour la classification binaire.
    • Produit des probabilités d’appartenance à une classe via une fonction sigmoïde.

  3. Machines à vecteurs de support (SVM) :

    • Efficace pour la classification et la régression.
    • Maximise la marge entre les points de données et une frontière de décision.

  4. Arbres de décision / Forêt aléatoire :

    • Construit un modèle en forme d’arbre des décisions et de leurs conséquences pour la classification et la régression.

  5. Réseaux de neurones / Deep learning :

    • Composés de couches de nœuds interconnectés pour capturer des relations complexes dans les données.
    • Très polyvalents, utilisés dans des tâches allant de la reconnaissance d’images à la prévision financière.
    • Plus de détails dans l’article dédié deep learning.

5 — Autres algorithmes d’apprentissage non supervisé

En plus de $k$-NN, voici quelques algorithmes courants d’apprentissage non supervisé. La liste n’est évidemment pas exhaustive.

5.1 — Clustering

  • Clustering hiérarchique :

    • Construit une structure en arbre (dendrogramme) de clusters imbriqués en fusionnant ou divisant successivement les clusters.
    • Peut être agglomératif (de bas en haut) ou divisif (de haut en bas).

  • Clustering basé sur la densité (DBSCAN) :

    • Regroupe les points en régions denses séparées par des zones plus clairsemées.
    • Ne nécessite pas de spécifier le nombre de clusters à l’avance.

5.2 — Décomposition / Apprentissage de variété

  • t-Distributed Stochastic Neighbor Embedding (t-SNE) :

    • Projette des données de haute dimension dans un espace de faible dimension (généralement 2D ou 3D) tout en préservant les relations de voisinage local.
    • Idéal pour visualiser des clusters.

  • Uniform Manifold Approximation and Projection (UMAP) :

    • Similaire à t-SNE mais souvent plus rapide et meilleur pour préserver la structure globale des données.
    • L’algorithme UMAP est détaillé ici

  • Autoencodeurs :

    • Modèle de Deep Learning entraîné pour compresser (encoder) les données en une représentation de dimension inférieure puis les reconstruire (décoder).
    • Utile pour la réduction de dimension non linéaire.

Pour aller encore plus loin

On dirait que cette section est vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être que nous pourrons l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !