Skip to content
Retour aux résultats

Propagation d'étiquettes

Introduite par
Zhu, X. & Ghahramani, Z.
Année
2002
Type
Graph-based semi-supervised classification

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Propagation d'étiquettes est un algorithme d'apprentissage semi-supervisé basé sur les graphes, introduit par Zhu et Ghahramani en 2002, qui diffuse les étiquettes de classe d'un petit ensemble de nœuds étiquetés vers un grand ensemble de nœuds non étiquetés en diffusant itérativement l'information d'étiquetage le long des arêtes d'un graphe de similarité, exploitant ainsi la structure de variété des données.

L’intuition derrière la méthode

Imaginez un réseau social où quelques personnes se sont déjà vu attribuer une catégorie. Une rumeur se propage naturellement : chaque personne a tendance à adopter l'étiquette la plus courante parmi ses voisins proches. La Propagation d'étiquettes formalise cette intuition : elle construit un graphe pondéré dans lequel des points de données similaires sont connectés par des arêtes fortes, puis laisse les étiquettes connues s'écouler pas à pas jusqu'à ce que chaque point non étiqueté ait absorbé suffisamment de signal pour être classifié. Comme la diffusion suit la géométrie des données plutôt que des frontières de décision arbitraires, elle peut produire des prédictions très précises même lorsque les exemples étiquetés sont rares.

Histoire

Xiaojin (Jerry) Zhu et Zoubin Ghahramani ont introduit la Propagation d'étiquettes dans un rapport technique de la Carnegie Mellon University en 2002 (CMU-CALD-02-107). L'année suivante, Zhu, Ghahramani et John Lafferty ont publié le cadre étroitement lié des champs gaussiens et des fonctions harmoniques à l'ICML 2003, fournissant une interprétation probabiliste via des marches aléatoires et des champs de Markov gaussiens. Ces travaux ont catalysé une vague de méthodes semi-supervisées basées sur les graphes tout au long du milieu des années 2000. Dengyong Zhou et ses collègues ont proposé la Propagation d'étiquettes (Label Spreading) en 2004 — une variante régularisée qui permet à l'information d'étiquette de remplacer partiellement les étiquettes contraintes, offrant une robustesse aux annotations bruitées. Ces deux méthodes sont maintenant des références standard dans les benchmarks d'apprentissage semi-supervisé et sont incluses dans des bibliothèques d'apprentissage automatique largement utilisées. Avec l'essor des réseaux neuronaux sur graphes dans les années 2010, la Propagation d'étiquettes est devenue un précurseur conceptuel et une référence compétitive, toujours citée pour sa simplicité et ses garanties en forme fermée.

Quand l’utiliser

La Propagation d'étiquettes est appropriée lorsque les exemples étiquetés sont rares par rapport à la taille totale de l'ensemble de données, que les données ont une structure de cluster ou de variété sous-jacente qu'un graphe de similarité peut capturer, et qu'il y a une raison de croire que l'hypothèse de régularité est valide — que les points proches (dans l'espace des caractéristiques) partagent la même étiquette. Les scénarios typiques incluent la catégorisation de texte avec peu de documents annotés, la classification d'images avec des étiquettes humaines éparses, et la classification de nœuds de réseau. La méthode exige que le graphe soit connecté (ou du moins que chaque nœud non étiqueté soit accessible depuis un nœud étiqueté). Elle n'est pas adaptée lorsque l'espace des caractéristiques ne reflète pas la similarité sémantique, lorsque la frontière de décision traverse des régions denses, ou lorsque toutes les données sont déjà étiquetées.

Limites et points d’attention

  • Scalabilité : le stockage et l'exploitation d'une matrice de poids n x n sont prohibitifs pour les grands ensembles de données sans approximations éparses.
  • La construction du graphe est sensible au choix de la bande passante du noyau sigma et de la taille du voisinage k ; de mauvais choix dégradent considérablement la précision.
  • Suppose l'hypothèse de régularité (cluster) : la violer — lorsque les frontières de décision traversent des régions denses — conduit à une classification erronée systématique.
  • Transductive par défaut : les prédictions pour de nouveaux points de test non vus nécessitent de réexécuter l'algorithme ou une extension inductive.
  • Le bruit d'étiquette sur les quelques nœuds étiquetés se propage et peut corrompre une grande partie du graphe.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Exploite efficacement les données non étiquetées, produisant une forte précision avec très peu d'exemples étiquetés.
  • Garantie de convergence en forme fermée : la mise à jour itérative atteint toujours un point fixe unique.
  • Gère naturellement les problèmes multi-classes sans modification.
  • Interprétation géométrique intuitive fondée sur la diffusion de graphes et l'analyse harmonique.
  • Aucun paramètre de modèle à optimiser au-delà des choix de construction du graphe (bande passante du noyau, taille du voisinage).

Applications

  • Classification de textes et de documents lorsque seule une petite fraction des documents porte des étiquettes attribuées par l'homme.
  • Annotation d'images ou de vidéos où l'étiquetage manuel est coûteux et les images non étiquetées sont abondantes.
  • Classification de nœuds de réseaux sociaux et de graphes de citation (par exemple, inférer les intérêts des utilisateurs ou les sujets des articles).
  • Bioinformatique : prédiction de la fonction génique ou des rôles d'interaction protéique à partir de réseaux biologiques partiellement annotés.
  • Détection d'anomalies semi-supervisée en propageant des étiquettes normales/anormales connues à travers un graphe de similarité.

Comment ça marche

Comment ça marche

1

Un graphe de similarité pondéré est construit sur l'ensemble des n points de données — étiquetés et non étiquetés. Un choix courant est le noyau gaussien (RBF) : le poids de l'arête W_ij est une fonction décroissante de la distance euclidienne au carré entre les points i et j, contrôlée par un paramètre de bande passante sigma. Seuls les k plus proches voisins ou les voisins dans un rayon epsilon sont conservés afin que le graphe reste épars.

Formule
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

La matrice de poids W est normalisée par colonne pour produire une matrice de transition T stochastique par ligne, où chaque entrée T_ij représente la probabilité que l'information d'étiquetage circule du nœud j vers le nœud i. Cela garantit que l'influence totale reçue par chaque nœud somme à un.

Formule
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

À partir d'une matrice d'étiquettes initiale F (une colonne par classe), l'algorithme itère : multiplier F par T, puis contraindre les lignes correspondant aux nœuds étiquetés à leurs étiquettes 'one-hot' vraies Y_L. Ce contrainte empêche les étiquettes connues de dériver et agit comme une condition de frontière absorbante. L'itération est répétée jusqu'à ce que les entrées non étiquetées de F convergent.

Formule
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

La solution au point fixe pour le bloc non étiqueté F_U* est donnée sous forme fermée par (I - T_UU)^{-1} T_UL Y_L, où T_UU est la sous-matrice des transitions entre nœuds non étiquetés et T_UL capture les transitions des nœuds étiquetés vers les nœuds non étiquetés. En pratique, la version itérative est préférée pour les grands graphes car elle évite l'inversion de matrice ; les deux approches donnent la même solution unique.

Formule
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Pièges courants

  • Utilisation d'un graphe entièrement connecté sans sparsification, ce qui masque la structure locale et est calculatoirement intraitable à grande échelle.
  • Choix de sigma par défaut sans validation croisée sur l'ensemble étiqueté, conduisant à des distributions d'étiquettes trop lissées ou pas assez.
  • Ignorer le déséquilibre des classes : si une classe domine l'ensemble étiqueté, son étiquette inonde le graphe ; une repondération ou un échantillonnage est nécessaire.
  • Traiter les prédictions transductives comme un modèle entraîné et les appliquer à de nouveaux points sans wrapper inductif.
  • Ne pas vérifier la connectivité du graphe : les nœuds non étiquetés dans des composantes isolées ne reçoivent aucun signal et adoptent par défaut des probabilités de classe uniformes.

Questions fréquentes

Quelle est la différence entre la Propagation d'étiquettes et la Propagation d'étiquettes (Label Spreading) ?

La Propagation d'étiquettes (Label Spreading), proposée par Zhou et al. (2004), introduit un paramètre de régularisation alpha qui contrôle dans quelle mesure chaque nœud conserve son étiquette initiale par rapport à l'adoption des étiquettes de ses voisins. Dans la Propagation d'étiquettes classique, les nœuds étiquetés sont contraints rigidement, ce qui les rend entièrement absorbants. La Propagation d'étiquettes (Label Spreading) permet aux nœuds étiquetés d'être partiellement remplacés, ce qui la rend plus robuste au bruit d'étiquette au prix d'un hyperparamètre supplémentaire.

La Propagation d'étiquettes est-elle scalable pour de grands ensembles de données ?

La solution naïve en forme fermée nécessite l'inversion d'une matrice (n_U x n_U), ce qui est infaisable pour un grand n. En pratique, un graphe éparse de k plus proches voisins ou de rayon epsilon réduit la mémoire à O(nk), et la mise à jour itérative est alors à peu près linéaire par rapport au nombre d'arêtes par itération. Pour des graphes très grands, des méthodes de voisins les plus proches approximatifs et des variantes par mini-lots sont utilisées.

Combien d'exemples étiquetés sont nécessaires ?

La Propagation d'étiquettes est spécifiquement conçue pour le régime extrême de faible nombre d'étiquettes. Même un seul nœud étiqueté par classe peut produire des prédictions significatives si la structure du graphe s'aligne avec les frontières de classe, bien qu'avoir au moins quelques exemples étiquetés par classe soit fortement recommandé pour la fiabilité. Les performances se dégradent à mesure que le bruit d'étiquette augmente ou que le graphe devient moins informatif sur l'appartenance à une classe.

La Propagation d'étiquettes peut-elle prédire sur de nouvelles données non vues ?

Sous sa forme transductive standard, non — l'algorithme opère sur un graphe fixe et n'a pas de mécanisme pour prédire en dehors de ce graphe. Pour une utilisation inductive, une approche courante consiste à connecter de nouveaux points à leurs k plus proches voisins dans le graphe existant et à exécuter une étape de propagation partielle, ou à utiliser la matrice d'étiquettes convergée pour entraîner un classificateur supervisé standard comme second étape.

Méthodes associées

Sources

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Ouvrir la référence de la publication
    Copié.
  2. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

    Ouvrir la référence de la publication
    Copié.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN : 978-0-262-03358-9
    Copié.