Skip to content
Retour aux résultats

Apprentissage actif K-plus proches voisins

Introduite par
Settles, B. (active learning framework); Fix & Hodges (KNN base)
Année
1951–2010
Type
Active learning with KNN base learner
Famille
Machine learning

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

Taille de police

À quoi sert-elle ?

L'apprentissage actif avec les K plus proches voisins combine la prédiction basée sur les instances de KNN avec une stratégie de requête itérative qui sélectionne les exemples non étiquetés les plus informatifs à annoter.

Le modèle demande des étiquettes uniquement pour les instances où les marges de vote du voisinage sont les plus étroites, atteignant une précision compétitive avec beaucoup moins d'exemples étiquetés que le KNN entièrement supervisé sur des données tabulaires.

L’intuition derrière la méthode

KNN classe un point en examinant ses k voisins étiquetés les plus proches et en procédant à un vote majoritaire. Lorsque ces voisins sont presque également répartis entre les classes, le modèle est véritablement incertain — et cette incertitude indique quel exemple non étiqueté vaudrait le plus la peine d'être étiqueté. L'apprentissage actif exploite ce signal : à chaque itération, l'algorithme trouve le point non étiqueté dont le voisinage est le plus uniformément divisé, demande à un oracle de l'étiqueter, l'ajoute au pool étiqueté, et répète. Le résultat est que l'effort d'étiquetage se concentre près des frontières de décision, où les nouvelles étiquettes enseignent le plus.

Histoire

Le classifieur des K plus proches voisins trouve son origine dans Fix et Hodges (1951) et a été formalisé par Cover et Hart (1967). L'apprentissage actif en tant que cadre principiel a été systématiquement examiné par Burr Settles (2010), qui a documenté l'échantillonnage par incertitude basé sur un pool, la requête par comité et les stratégies pondérées par la densité. KNN a été utilisé comme apprenant de base dans les benchmarks d'apprentissage actif basé sur un pool depuis au moins les travaux fondamentaux de Cohn, Atlas et Ladner (1994), apprécié pour son signal d'incertitude transparent et son coût de réapprentissage nul par itération.

Quand l’utiliser

Utilisez l'apprentissage actif avec KNN lorsque les données étiquetées sont rares ou coûteuses à obtenir, que les instances non étiquetées sont abondantes, que l'espace des caractéristiques est de dimensionnalité modérée et que la frontière de décision est censée être localement lisse. C'est particulièrement pratique dans les projets de classification à un stade précoce où l'étiquetage doit être rationné. Évitez-le lorsque l'ensemble de données est de très haute dimension (les métriques de distance KNN se dégradent dans les hautes dimensions, la malédiction de la dimensionnalité), lorsque le pool étiqueté est déjà grand (KNN passif suffit), lorsque la prédiction à faible latence est requise à grande échelle (la prédiction KNN est O(n) par rapport à l'ensemble étiqueté), ou lorsque le budget d'étiquettes est si faible que les estimations du voisinage ne sont pas fiables.

Limites et points d’attention

  • Le coût de prédiction est proportionnel à la taille de l'ensemble étiqueté, rendant l'inférence lente à mesure que le pool s'agrandit au fil des itérations.
  • L'incertitude basée sur la distance se dégrade rapidement dans les espaces de haute dimension en raison de la malédiction de la dimensionnalité.
  • Le plafond de précision de KNN est inférieur à celui des méthodes d'ensemble ; la stratégie active ne peut pas compenser la capacité limitée de l'apprenant de base.
  • Sensible au choix de k et de la métrique de distance ; des défauts de réglage conduisent à des estimations d'incertitude peu fiables.
  • Tous les points étiquetés sont stockés en mémoire ; des budgets importants entraînent une consommation de mémoire élevée.

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

Points forts

  • Non paramétrique et sans hypothèses : aucune hypothèse distributionnelle sur les données n'est requise.
  • L'estimation de l'incertitude est naturelle et interprétable — elle reflète directement la répartition des votes parmi les voisins les plus proches.
  • L'apprentissage paresseux signifie aucun coût de réapprentissage par itération ; l'ensemble étiqueté élargi est le modèle mis à jour.
  • Efficace pour concentrer les étiquettes près des frontières de décision, offrant une bonne résolution des frontières avec peu d'annotations.
  • Fonctionne bien sur des données tabulaires de dimensionnalité modérée avec des caractéristiques continues et binaires.

Applications

  • Annotation de dossiers médicaux ou d'images où le temps d'étiquetage expert est limité et les frontières de décision sont localement lisses.
  • Classification de textes ou de documents avec de petits corpus étiquetés et d'abondants documents non étiquetés en utilisant des distances basées sur des plongements (embeddings).
  • Tâches de détection de défauts de capteurs et industriels où seule une fraction des événements peut être vérifiée manuellement.
  • Enquêtes écologiques où la confirmation sur le terrain des étiquettes d'espèces est coûteuse et localement groupée.
  • Classifieurs prototypes à un stade précoce avant de passer à un modèle de plus grande capacité une fois que suffisamment d'étiquettes sont collectées.

Comment ça marche

Comment ça marche

1

Un petit ensemble initial d'instances étiquetées est assemblé pour amorcer le processus, ainsi qu'un plus grand pool d'instances non étiquetées. Une sélection aléatoire stratifiée est recommandée pour garantir la présence d'au moins un exemple par classe, donnant à KNN un voisinage de départ significatif avant le début de la boucle active.

2

Un classifieur KNN est ajusté sur l'ensemble étiqueté actuel en utilisant un k et une métrique de distance choisis (communément euclidienne ou cosinus). Parce que KNN est paresseux et stocke tous les points d'entraînement, l'ajustement est instantané, mais le coût de prédiction est proportionnel à la taille de l'ensemble étiqueté — une considération pertinente à mesure que le pool s'agrandit au fil des itérations.

3

Chaque instance non étiquetée est évaluée selon un critère d'informativité. L'échantillonnage de marge calcule l'écart entre les parts de vote des deux classes principales parmi les k voisins ; l'échantillonnage d'entropie calcule H(y-chapeau | x) sur toutes les proportions de classes. L'instance avec la plus petite marge ou la plus haute entropie est interrogée : x* = argmax H(y-chapeau | x).

Formule
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

L'instance interrogée est envoyée à un oracle — un annotateur humain ou un mécanisme d'étiquetage automatisé — pour sa véritable étiquette. L'étiquette est ajoutée à l'ensemble d'entraînement et l'instance est retirée du pool non étiqueté. La fiabilité de l'annotateur doit être surveillée, car les étiquettes bruitées dégradent fortement les performances de KNN près des frontières.

5

Étant donné que KNN est un apprenant paresseux, aucun réapprentissage explicite n'est nécessaire ; l'ensemble étiqueté élargi constitue immédiatement le nouveau modèle. Le cycle requête-score-étiquette se répète jusqu'à ce que le budget d'étiquetage soit épuisé, qu'un seuil de précision de validation soit atteint, ou qu'un nombre maximum d'itérations soit atteint. La performance finale est rapportée sur un ensemble de test indépendant mis de côté.

Pièges courants

  • Échec de la normalisation des caractéristiques avant le calcul des distances, provoquant la domination des caractéristiques de grande magnitude sur le voisinage.
  • Utilisation de l'ensemble de test pour guider ou évaluer la sélection des requêtes, ce qui constitue une fuite de données.
  • Définition de k trop petit (k=1) près de la frontière de décision, produisant des scores d'incertitude très variables qui ne reflètent pas l'ambiguïté réelle.
  • Ignorer le déséquilibre des classes dans l'ensemble d'amorçage, ce qui biaise les premières requêtes vers les frontières de la classe majoritaire.
  • Traiter la précision de l'apprentissage actif comme équivalente à une base entièrement supervisée sans rapporter le nombre d'étiquettes utilisées.

Questions fréquentes

Pourquoi utiliser KNN plutôt qu'un modèle plus puissant comme apprenant de base pour l'apprentissage actif ?

L'incertitude de la répartition des votes de KNN est peu coûteuse à calculer et ne nécessite aucun réapprentissage — l'ajout d'un nouveau point étiqueté met immédiatement à jour le modèle. Cela le rend attrayant lorsque le coût computationnel par itération est important. Pour une précision maximale avec un budget d'étiquettes fixe, les apprenants de base d'ensemble tels que la forêt aléatoire ou le gradient boosting surpassent généralement KNN.

Comment choisir k pour l'apprentissage actif ?

Une plage de départ courante est k = 5 à 15. Des valeurs de k plus petites produisent des estimations d'incertitude plus bruitées ; des valeurs de k plus grandes lissent la frontière mais peuvent manquer une ambiguïté fine. Validez croisée k sur l'ensemble d'amorçage étiqueté initial et ajustez au fur et à mesure que le pool étiqueté s'agrandit.

La mise à l'échelle des caractéristiques est-elle importante ?

Oui, de manière critique. La distance KNN est dominée par les caractéristiques de grande magnitude si les caractéristiques ne sont pas normalisées. Appliquez toujours une mise à l'échelle min-max ou une standardisation par score z avant de calculer les distances et les scores d'incertitude.

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

Au minimum, une ou deux instances étiquetées par classe sont nécessaires pour que KNN puisse former des voisinages pour toutes les classes. En pratique, 5 à 20 instances étiquetées fournissent des estimations d'incertitude initiales plus stables ; moins risquent des voisinages dégénérés qui produisent des requêtes précoces non informatives.

Quand dois-je arrêter la boucle active ?

Définissez un budget d'étiquetage à l'avance, ou surveillez la précision de validation et arrêtez-vous lorsque l'amélioration par nouvelle étiquette tombe en dessous d'un seuil significatif. N'utilisez jamais l'ensemble de test comme signal d'arrêt, car cela divulgue des informations dans le processus de requête.

Méthodes associées

Sources

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    Ouvrir la référence de la publication
    Copié.
  2. Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.

    Ouvrir la référence de la publication
    Copié.