Label Propagation

Résumé

La Label Propagation (ou propagation d’étiquettes) est un algorithme d’apprentissage semi-supervisé qui classe des données non étiquetées en diffusant progressivement les informations contenues dans les quelques échantillons étiquetés disponibles. Plutôt que de construire un modèle paramétrique explicite, cet algorithme exploite la structure locale du jeu de données entier : il construit un graphe de similarité entre tous les points, puis propage les étiquettes connues à travers les arêtes de ce graphe de manière itérative, jusqu’à convergence. Son frère, le Label Spreading, introduit un paramètre de régularisation alpha qui contrôle le compromis entre la fidélité aux labels initiaux et l’influence des voisins propagés. Ces deux algorithmes sont particulièrement utiles lorsque l’acquisition de labels est coûteuse — un scénario extrêmement fréquent dans la pratique industrielle.

Principe Mathématique

La Label Propagation repose sur une formulation matricielle élégante qui transforme le problème de classification en un processus de diffusion sur graphe. Voici les ingrédients mathématiques fondamentaux.

Matrice de similarité

On commence par construire une matrice de similarité W entre toutes les paires de points. L’entrée W_ij mesure la proximité entre deux échantillons x_i et x_j. La définition la plus courante utilise un noyau à base radiale (RBF) :

W_ij = exp(-||x_i - x_j||² / (2·sigma²))

où sigma est un paramètre de diffusion qui contrôle la portée du noyau. Une autre approche populaire utilise les k plus proches voisins : on ne conserve les arêtes qu’entre chaque point et ses k voisins les plus proches, ce qui rend la matrice W creuse et accélère considérablement les calculs.

Matrice des labels

On définit une matrice de labels Y de dimension n × C, où n est le nombre total d’échantillons (étiquetés et non étiquetés) et C est le nombre de classes. Les lignes correspondant aux échantillons étiquetés contiennent des vecteurs one-hot (un 1 à la position du label connu, des 0 ailleurs). Les lignes des échantillons non étiquetés sont initialisées à des valeurs uniformes ou nulles.

Dans le cas du Label Propagation classique, les labels connus sont clamps (fixés) à chaque itération : ils ne changent jamais. Seules les lignes correspondant aux données non étiquetées sont mises à jour.

Propagation itérative

L’itération fondamentale s’écrit sous la forme suivante :

F(t+1) = S · F(t)

où S = D^{-1/2} W D^{-1/2} est la matrice de transition normalisée symétrique et D est la matrice diagonale des degrés (D_ii = somme_j W_ij). La normalisation symétrique garantit que les valeurs propres de S sont bornées entre -1 et 1, ce qui est crucial pour la stabilité numérique.

Pour le Label Spreading, l’itération devient :

F(t+1) = alpha · S · F(t) + (1 - alpha) · Y(0)

où Y(0) est la matrice des labels initiaux (qui reste fixe), et alpha ∈ ]0, 1[ contrôle le compromis entre la propagation (premier terme) et la rétention de l’information initiale (second terme). Lorsque alpha est proche de 1, l’algorithme fait confiance principalement à la structure du graphe ; lorsque alpha est proche de 0, il reste fidèle aux labels initiaux.

Convergence garantie

La convergence est mathématiquement garantie parce que 0 < alpha < 1. Les valeurs propres de la matrice alpha · S sont strictement comprises entre -1 et 1, ce qui signifie que la suite F(t) converge vers un point fixe unique. En pratique, la convergence est généralement atteinte en moins d’une centaine d’itérations, même pour des jeux de données de taille significative.

Une fois la convergence atteinte, la classe prédite pour chaque échantillon non étiqueté est simplement celle qui maximise la valeur correspondante dans la matrice F finale :

y_i_pred = argmax_c F_ic

Intuition

Imaginez une grande salle remplie de personnes. Quelques-uns d’entre elles connaissent déjà la réponse à une question — disons, elles savent à quel groupe appartient chaque individu. Les autres ne savent rien du tout.

Maintenant, imaginez que chaque personne regarde ses voisins les plus proches (ceux qui lui ressemblent le plus) et leur transmet ce qu’elle sait. Les personnes qui possèdent déjà l’information d’origine (labels connus) répètent constamment leur réponse : à chaque tour, elles réaffirment leur position. Les personnes sans information initiale, elles, accumulent progressivement ce qu’elles entendent de leurs voisins pondéré par la similarité.

Au fil des itérations, une sorte de rumeur structurée se propage dans la foule. Chaque personne finit par entendre davantage de messages d’un certain type que des autres, et ce message dominant devient son étiquette prédite. Les personnes qui étaient rất proches (très similaires) des individus étiquetés reçoivent une information claire rapidement ; celles qui sont plus éloignées reçoivent un signal plus diffusé, mais qui converge tout de même vers la réponse correcte grâce à la répétition itérative.

Cette analogie capture parfaitement l’essence de l’algorithme : la similarité locale remplace la modélisation globale. Plutôt que d’apprendre une frontière de décision complexe comme le ferait un réseau de neurones ou un SVM, la Label Propagation laisse la structure intrinsèque des données « parler d’elle-même ». Le graphe de similarité encode toute la géométrie du problème, et la propagation fait le reste.

Implémentation Python

Préparation des données synthétiques

Commençons par générer des données synthétiques avec un petit pourcentage d’échantillons étiquetés, puis comparons les deux algorithmes de scikit-learn.

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.semi_supervised import LabelPropagation, LabelSpreading
from sklearn.metrics import accuracy_score, classification_report

# Générer des données synthétiques en forme de cercles concentriques
X, y_true = datasets.make_circles(n_samples=1000, factor=0.5, noise=0.1, random_state=42)

# Créer les labels : seulement 10% sont étiquetés
rng = np.random.RandomState(42)
labeled_mask = rng.random(len(y_true)) < 0.10
y_labeled = -1 * np.ones(len(y_true), dtype=int)  # -1 = non étiqueté
y_labeled[labeled_mask] = y_true[labeled_mask]

print(f"Échantillons totaux : {len(y_true)}")
print(f"Échantillons étiquetés : {labeled_mask.sum()}")
print(f"Échantillons non étiquetés : {(~labeled_mask).sum()}")

Label Propagation : noyau RBF et k-plus-proches-voisins

scikit-learn propose deux noyaux pour la Label Propagation : le noyau RBF (kernel="rbf") et le noyau k-NN (kernel="knn"). Voyons les deux approches.

# --- Label Propagation avec noyau RBF ---
lp_rbf = LabelPropagation(kernel="rbf", gamma=20, max_iter=100)
lp_rbf.fit(X, y_labeled)
y_pred_rbf = lp_rbf.predict(X)

# --- Label Propagation avec noyau k-NN ---
lp_knn = LabelPropagation(kernel="knn", n_neighbors=7, max_iter=100)
lp_knn.fit(X, y_labeled)
y_pred_knn = lp_knn.predict(X)

# --- Label Spreading avec noyau RBF ---
ls_rbf = LabelSpreading(kernel="rbf", gamma=20, alpha=0.2, max_iter=100)
ls_rbf.fit(X, y_labeled)
y_pred_ls = ls_rbf.predict(X)

# --- Label Spreading avec noyau k-NN ---
ls_knn = LabelSpreading(kernel="knn", n_neighbors=7, alpha=0.2, max_iter=100)
ls_knn.fit(X, y_labeled)
y_pred_ls_knn = ls_knn.predict(X)

# Évaluation
print("\n=== Résultats ===")
for name, y_pred in [
    ("LP RBF", y_pred_rbf),
    ("LP k-NN", y_pred_knn),
    ("LS RBF", y_pred_ls),
    ("LS k-NN", y_pred_ls_knn),
]:
    acc = accuracy_score(y_true, y_pred)
    print(f"{name:15s} — Précision : {acc:.4f}")

Visualisation des frontières de décision

Visualiser les frontières de décision aide à comprendre comment chaque variante partitionne l’espace des caractéristiques.

def plot_decision_boundaries(X, y_true, y_labeled, title):
    # Grille pour la frontière
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(
        np.linspace(x_min, x_max, 300),
        np.linspace(y_min, y_max, 300),
    )
    grid_points = np.c_[xx.ravel(), yy.ravel()]

    kernel_type = "rbf" if "RBF" in title else "knn"
    if "Spreading" in title:
        model = LabelSpreading(
            kernel=kernel_type,
            gamma=20 if kernel_type == "rbf" else None,
            n_neighbors=7 if kernel_type == "knn" else None,
            alpha=0.2,
            max_iter=100,
        )
    else:
        model = LabelPropagation(
            kernel=kernel_type,
            gamma=20 if kernel_type == "rbf" else None,
            n_neighbors=7 if kernel_type == "knn" else None,
            max_iter=100,
        )
    model.fit(X, y_labeled)
    Z = model.predict(grid_points).reshape(xx.shape)

    fig, ax = plt.subplots(1, 1, figsize=(10, 8))
    ax.contourf(xx, yy, Z, alpha=0.3, cmap="RdBu")

    unlabeled_mask = y_labeled == -1
    ax.scatter(X[unlabeled_mask, 0], X[unlabeled_mask, 1],
        c=y_true[unlabeled_mask], cmap="RdBu", s=20, alpha=0.4, label="Non étiqueté")
    ax.scatter(X[~unlabeled_mask, 0], X[~unlabeled_mask, 1],
        c=y_true[~unlabeled_mask], cmap="RdBu", s=80,
        edgecolors="black", linewidths=1.5, label="Étiqueté")

    ax.set_title(title, fontsize=14, fontweight="bold")
    ax.set_xlabel("x₁")
    ax.set_ylabel("x₂")
    ax.legend(loc="upper right")
    plt.tight_layout()
    plt.savefig(f"./frontiere_{title.lower().replace(' ', '_').replace('-', '_')}.png", dpi=150)
    plt.show()


plot_decision_boundaries(X, y_true, y_labeled, "LP RBF")
plot_decision_boundaries(X, y_true, y_labeled, "LP k-NN")
plot_decision_boundaries(X, y_true, y_labeled, "LS RBF")
plot_decision_boundaries(X, y_true, y_labeled, "LS k-NN")

Comparaison et analyse des résultats

Un aspect crucial de la Label Propagation est la possibilité d’accéder aux distributions de probabilités sur les classes grâce à la méthode predict_proba(). Cela permet non seulement de connaître la classe prédite, mais aussi d’estimer la confiance de la prédiction.

# Probabilités pour les exemples non étiquetés
probas = lp_rbf.predict_proba(X[~labeled_mask])
confiance = probas.max(axis=1)

print(f"Confiance moyenne : {confiance.mean():.3f}")
print(f"Confiance minimale : {confiance.min():.3f}")
print(f"Écart-type : {confiance.std():.3f}")

# Identifier les prédictions « incertaines »
seuil_confiance = 0.6
incertains = confiance < seuil_confiance
print(f"\nPrédictions incertaines (confiance < {seuil_confiance}) : {incertains.sum()}")

L’analyse des niveaux de confiance révèle des informations précieuses sur la géométrie du jeu de données : les points proches des frontières entre clusters présentent naturellement une confiance plus faible, tandis que ceux au cœur des clusters bénéficient d’une attribution très sûre.

Hyperparamètres

Le choix des hyperparamètres influence profondément le comportement de la Label Propagation. Examinons chacun d’entre eux.

kernel : choix du noyau

Le paramètre kernel détermine la manière dont la matrice de similarité est construite. Deux options sont disponibles dans scikit-learn :

• "rbf" (noyau à fonction de base radiale) : calcule la similarité entre toutes les paires de points. Cela donne un graphe complet et dense. Le noyau RBF est lisse et produit des frontières de décision progressives, mais il peut être très coûteux en mémoire pour de grands jeux de données : la matrice W a une complexité en O(n²).
• "knn" (k plus proches voisins) : ne connecte chaque point qu’à ses n_neighbors voisins les plus proches. La matrice W est creuse, ce qui réduit la complexité en O(n·k·log(n)) et permet de traiter des jeux de données de taille bien plus importante. Les frontières de décision sont plus anguleuses mais capturent bien la structure locale.

gamma : largeur du noyau RBF

Le paramètre gamma correspond à 1 / (2·sigma²) dans la formule du noyau RBF. Un gamma élevé produit des noyaux étroits : seuls les points très proches contribuent significativement. Un gamma faible produit des noyaux larges : des points plus éloignés influencent aussi la propagation.

Le réglage de gamma est crucial. Un mauvais choix peut soit fragmenter le graphe en composantes isolées (gamma trop élevé), soit noyer le signal dans un bruit homogène (gamma trop faible).

alpha : compromis propagation / rétention (Label Spreading uniquement)

Le paramètre alpha n’existe que pour le Label Spreading. Il contrôle l’équilibre entre deux forces opposées : la propagation des labels à travers le graphe d’un côté, et la rétention des labels initiaux de l’autre.

• alpha proche de 1 (par exemple 0,8) : forte propagation, faible rappel. L’algorithme fait largement confiance à la structure du graphe. Risque de propagation d’erreurs si les labels initiaux sont bruités.
• alpha proche de 0,5 (par exemple 0,2-0,5) : équilibre modéré entre propagation et fidélité aux labels connus.
• alpha proche de 0 (par exemple 0,05) : faible propagation, fort rappel. L’algorithme reste très fidèle aux labels initiaux mais explore peu la structure du graphe.

n_neighbors : nombre de voisins (noyau k-NN)

Lorsque kernel="knn", le paramètre n_neighbors détermine le nombre de voisins connectés à chaque point. Un k petit capture la structure locale fine mais risque de fragmenter le graphe. Un k grand assure une meilleure connectivité mais peut introduire des arêtes entre clusters distincts. Comme règle empirique, des valeurs entre 5 et 15 fonctionnent bien en pratique.

max_iter : itérations maximales

Le paramètre max_iter fixe la limite supérieure du nombre d’itérations. En pratique, la convergence intervient généralement bien avant d’atteindre cette limite (souvent en 10 à 50 itérations). L’algorithme s’arrête lorsque la norme de la différence entre deux itérations successives est inférieure à un seuil de tolérance interne (par défaut, tol=1e-3 dans scikit-learn).

Avantages et Limites

Avantages

La Label Propagation présente plusieurs atouts majeurs qui expliquent son utilisation persistante dans de nombreux domaines d’application.

• Zéro paramètre de modèle à apprendre : contrairement aux méthodes supervisées classiques, il n’y a pas de phase d’entraînement avec descente de gradient. L’algorithme est purement transductif : il produit directement des prédictions sur les points donnés.
• Exploitation naturelle de la géométrie des données : en construisant un graphe de similarité, l’algorithme capture automatiquement les structures non linéaires et les variétés de basse dimension qui seraient difficiles à modéliser avec des approches paramétriques.
• Simplicité conceptuelle : le principe de diffusion itérative est facile à comprendre et à expliquer, ce qui en fait un outil pédagogique précieux et un bon point d’entrée vers l’apprentissage sur graphes.
• Convexité et convergence garantie : le Label Spreading optimise une fonction objectif convexe, ce qui garantit l’absence de minima locaux et une convergence vers l’unique solution optimale.
• Efficacité avec peu de labels : l’algorithme tire profit de l’ensemble du jeu de données (étiqueté et non étiqueté) et peut produire d’excellents résultats même avec seulement 1 à 5 % de données étiquetées.

Limites

Malgré ses qualités, la Label Propagation présente des inconvénients importants qu’il faut connaître.

• Complexité en mémoire : avec un noyau RBF, la matrice de similarité W occupe O(n²) en mémoire. Pour des jeux de données de plusieurs dizaines de milliers d’échantillons, cela peut rapidement devenir problématique. Même le noyau k-NN, bien que plus efficace, nécessite de stocker une matrice creuse de taille O(n·k).
• Sensibilité aux hyperparamètres : le choix de gamma (ou de n_neighbors) et d’alpha impacte fortement les résultats. Il n’existe pas de règle universelle pour les déterminer, et une validation croisée sur le sous-ensemble étiqueté reste nécessaire.
• Nature transductive : l’algorithme ne produit pas un modèle réutilisable. Pour classifier un nouveau point, il faut relancer l’algorithme en l’incluant dans le graphe, ce qui est coûteux. C’est une différence majeure avec les méthodes inductives comme les Random Forests ou les réseaux de neurones.
• Sensibilité au bruit et aux labels erronés : si quelques labels initiaux sont incorrects, la propagation peut amplifier ces erreurs, en particulier avec des valeurs d’alpha élevées. Le Label Spreading avec un alpha modéré atténue ce risque, mais ne l’élimine pas totalement.
• Difficulté avec les clusters non séparables : lorsque les classes se mélangent fortement dans l’espace des caractéristiques, la similarité locale ne suffit plus à distinguer les frontières. Dans ces cas, des méthodes supervisées classiques peuvent surpasser la Label Propagation.

Cas d’Usage

1. Classification de documents avec annotation partielle

Dans la fouille de textes, annoter manuellement des milliers de documents est long et coûteux. La Label Propagation permet d’exploiter un petit corpus annoté (par exemple 200 documents étiquetés manuellement) et des milliers de documents non annotés. En construisant un graphe de similarité basé sur les embeddings TF-IDF ou des représentations vectorielles issues de modèles de langue, l’algorithme diffuse les étiquettes à travers le graphe sémantique. Cette approche est particulièrement efficace pour la catégorisation thématique où les documents du même topic forment naturellement des clusters denses dans l’espace des caractéristiques.

2. Annotation d’images médicales

L’annotation d’images médicales (radiographies, IRM, scanners) nécessite l’expertise de radiologues qualifiés, ce qui rend chaque label extrêmement précieux. Un hôpital peut disposer de quelques centaines d’images annotées et de plusieurs milliers d’images brutes stockées dans ses archives. En extrayant des caractéristiques visuelles (via un réseau de neurones pré-entraîné par exemple) et en construisant un graphe de similarité entre images, la Label Propagation permet de pré-étiqueter automatiquement les images non annotées. Le radiologue peut ensuite réviser et corriger uniquement les prédictions les plus incertaines, réduisant considérablement la charge de travail.

3. Détection de communautés dans les réseaux sociaux

Bien que les algorithmes de détection de communautés (comme Louvain ou Infomap) soient plus couramment utilisés, la Label Propagation offre une approche alternative intéressante pour identifier des groupes dans des graphes sociaux. Ici, les « labels connus » correspondent à quelques utilisateurs dont on connaît l’appartenance communautaire (par exemple, via des profils publics ou des déclarations explicites). La propagation diffuse cette information à travers le réseau, révélant la structure communautaire sous-jacente. Cette méthode est particulièrement utile dans les réseaux partiellement observés ou lorsque certaines communautés sont bien documentées tandis que d’autres restent inconnues.

4. Prédiction de fonction des protéines

En bioinformatique, la Label Propagation est historiquement l’une des premières méthodes semi-supervisées utilisées pour prédire la fonction de protéines non caractérisées. On construit un graphe où les nœuds sont des protéines et les arêtes représentent une similarité de séquence ou d’interaction. Quelques protéines ont des fonctions connues (étiquetées), tandis que la grande majorité reste non annotée. La propagation diffuse les annotations fonctionnelles à travers le réseau d’interactions, permettant de formuler des hypothèses sur la fonction de protéines inconnues. Cette approche est particulièrement pertinente car les protéines qui interagissent physiquement ont statistiquement plus de chances de participer à des voies biologiques communes.

Voir aussi

• Python : Apprendre à utiliser pandas
• Créer des Ellipses Croisées en Python : Guide Complet pour la Visualisation et la Manipulation