🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Cet article présente KNNG-CS, une méthode de sélection de coreset légère qui exploite les graphes des K plus proches voisins pour identifier efficacement des sous-ensembles de données représentatifs avec des coûts en temps et en mémoire considérablement réduits, tout en maintenant une précision comparable aux approches d'approximation de gradient existantes.

Auteurs originaux : Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Publié 2026-08-18

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Les modèles d'apprentissage automatique sont les moteurs de nombreux outils modernes, de la reconnaissance de visages sur des photos à la prédiction des tendances boursières. Pour apprendre à accomplir ces tâches, ces modèles doivent être nourris avec de quantités massives de données. Imaginez essayer d'enseigner à un étudiant en lui donnant chaque livre d'une bibliothèque ; il finirait par apprendre, mais le processus serait incroyablement lent et épuisant. Dans le monde de l'intelligence artificielle, c'est la réalité de l'entraînement sur de gigantesques ensembles de données. Cela nécessite une puissance de calcul et une mémoire énormes, ce qui rend souvent l'opération trop coûteuse ou trop lente pour de nombreuses applications pratiques. Pour résoudre ce problème, les scientifiques utilisent une technique appelée sélection de coreset. L'objectif est simple : au lieu d'utiliser toute la bibliothèque, trouver un petit sous-ensemble parfait de livres qui contient toutes les leçons essentielles. Si vous pouvez entraîner le modèle sur cet échantillon minuscule et représentatif, il apprendra aussi bien que s'il avait tout lu, mais en une fraction du temps et avec beaucoup moins de mémoire.

Pendant des années, les meilleures méthodes pour trouver ces petits sous-ensembles parfaits se sont appuyées sur une méthode très gourmande en calculs. Ces approches existantes tentent de mesurer la distance entre chaque point de donnée et tous les autres points de donnée pour voir lesquels sont les plus similaires. C'est comme essayer de trouver le meilleur représentant d'une foule en demandant à chaque personne de mesurer sa distance par rapport à toutes les autres personnes de la pièce. Bien que cela fonctionne, cela crée une quantité massive de données difficiles à stocker et à traiter, surtout lorsque l'ensemble de données devient volumineux. Les chercheurs de l'Université Xidian et leurs collaborateurs ont réalisé que cette approche consistant à « tout mesurer » était inefficace. Ils ont observé que les représentants les plus utiles dans un ensemble de données sont généralement ceux qui se situent au milieu de groupes denses d'éléments similaires, plutôt que ceux qui sont isolés. Un échantillon proche de nombreux autres est susceptible de représenter un motif commun, tandis qu'un échantillon isolé est moins susceptible d'être un bon substitut pour un groupe important.

Pour remédier à cela, l'équipe a développé une nouvelle méthode appelée KNNG-CS. Au lieu de forcer chaque élément à mesurer sa distance par rapport à tous les autres éléments, ils ont construit une carte qui ne connecte chaque élément qu'à ses dix plus proches voisins. Cela crée un réseau creux, ou un graphe, qui capture les relations locales entre les points de données sans le fardeau écrasant du calcul de toutes les connexions possibles. Une fois cette carte construite, les chercheurs ont attribué un score à chaque élément en fonction du nombre d'autres éléments le désignant comme voisin et de la proximité de ces voisins. Les éléments qui étaient fréquemment choisis comme voisins proches par de nombreux autres recevaient un score élevé, les marquant comme des représentants hautement importants. L'algorithme a ensuite sélectionné de manière gloutonne les éléments ayant les scores les plus élevés pour former le sous-ensemble final. À mesure que chaque élément à haut score était choisi, l'algorithme le retirait, ainsi que ses voisins, du groupe, garantissant que le groupe sélectionné couvre l'ensemble des données de manière efficace et sans redondance.

Les résultats de cette nouvelle approche ont été frappants lors des tests sur quatre ensembles de données réels, allant des types de couverture forestière aux évaluations de films et aux défauts de cartes de crédit. La nouvelle méthode a produit un ensemble d'entraînement réduit qui a permis au modèle d'apprentissage automatique d'atteindre une précision comparable aux meilleures méthodes existantes. Cependant, la différence d'efficacité était spectaculaire. La nouvelle méthode s'est exécutée entre 2,3 et 41,2 fois plus vite que les techniques de pointe précédentes. Plus impressionnante encore fut la réduction de l'utilisation de la mémoire. Alors que les anciennes méthodes nécessitaient de stocker des tables de distances massives pouvant consommer des gigaoctets de mémoire, la nouvelle approche n'en utilisait que 0,3 % à 7,5 %. En termes pratiques, cela signifie que des tâches qui nécessitaient auparavant des serveurs coûteux et haut de gamme peuvent désormais être effectuées sur des machines beaucoup plus petites et plus accessibles. Les chercheurs ont constaté que même avec un sous-ensemble de données très réduit, le modèle apprenait efficacement, convergeant vers une solution stable bien plus rapidement que s'il avait été entraîné sur l'ensemble complet des données.

Ce travail démontre qu'en se concentrant sur les relations locales plutôt que sur les comparaisons globales, il est possible de simplifier considérablement le processus de préparation des données pour l'apprentissage automatique. L'étude confirme qu'il n'est pas nécessaire de calculer toutes les distances possibles pour trouver les points de données les plus importants ; une carte locale intelligente est suffisante. En utilisant cette stratégie basée sur les graphes, les chercheurs ont montré qu'un entraînement de haute qualité peut être obtenu avec une fraction du temps et des ressources auparavant jugés nécessaires. Cela ouvre la voie à des processus d'entraînement plus efficaces, permettant aux modèles complexes d'être développés et déployés dans des environnements où la puissance de calcul est limitée, sans sacrifier la qualité du résultat final.

Résumé Technique : Sélection de Coreset Efficace via des Graphes K-Plus Proches Voisins

Énoncé du Problème

La sélection de coreset vise à réduire les coûts de calcul et de mémoire de l'entraînement de modèles d'apprentissage automatique en remplaçant un grand ensemble d'entraînement par un sous-ensemble restreint et représentatif. L'article se concentre sur la sélection de coreset basée sur l'approximation de gradient (GA). Dans ce cadre, l'objectif est de sélectionner un sous-ensemble $C$ de taille $M$ à partir d'un ensemble d'entraînement $T$ tel que les gradients de l'ensemble complet soient bien approximés par le sous-ensemble. Ce problème est mathématiquement réduit à la minimisation de l'erreur de représentativité dans l'espace des caractéristiques (Éq. 1), où chaque point de données est représenté par son plus proche voisin dans le coreset sélectionné.

Les méthodes existantes basées sur la GA, telles que CRAIG et FastCore, reposent sur des stratégies de sélection gourmandes (greedy). Cependant, elles font face à des problèmes dables de scalabilité :

CRAIG pré-calcule une matrice de distances par paires dense, nécessitant $O(n^2)$ d'espace et $O(n^2d)$ de temps, ce qui devient prohibitif sur de grands ensembles de données.
FastCore remplace les distances élément-élément par des bornes supérieures élément-cluster pour économiser de l'espace, mais nécessite souvent un nombre massif de clusters (des centaines à des dizaines de milliers) pour maintenir la précision, entraînant une surcharge considérable dans le calcul et le stockage des grandes matrices de bornes.

Les auteurs observent que la représentativité dans l'espace des caractéristiques est intrinsèquement locale : un échantillon qui sert de voisin proche à de nombreux autres échantillons est susceptible de représenter une région locale dense avec une faible erreur d'approximation. Les méthodes existantes ne parviennent pas à exploiter efficacement cette localité car elles reposent sur des structures denses plutôt que sur des relations de voisinage éparses.

Méthodologie : KNNG-CS

L'article propose KNNG-CS, une méthode de sélection de coreset légère basée sur un graphe de K-plus proches voisins (KNNG). La méthode opère en trois étapes principales :

1. Construction d'un KNNG Approximatif

Au lieu de calculer toutes les distances par paires, la méthode construit un KNNG approximatif $G=(V, E)$ sur les vecteurs de caractéristiques. Chaque nœud $x_i$ est connecté à ses $K$ plus proches voisins.

Efficacité : En utilisant des méthodes approximatives de pointe (ex: KGraph), le temps de construction est de $O(n^{1.14}d)$ , et la complexité spatiale est linéaire, $O(nK) $, où$ K$ est une petite constante (fixée à 10 dans les expériences). Cela évite l'exigence d'espace quadratique des matrices denses.

2. Notation de Nœuds Sensible à la Distance

L'innovation centrale est une fonction de notation qui estime l'importance de chaque nœud (élément de donnée) en fonction de sa structure de voisinage locale au sein du KNNG.

Degré Entrant (In-Degree) : Un nœud possédant un degré entrant élevé (de nombreux nœuds pointent vers lui comme étant un voisin proche) est un candidat fort pour la représentativité.
Sensibilité à la Distance : Le degré entrant seul est insuffisant. La méthode incorpore les distances des arêtes en les convertissant en probabilités via une fonction softmax (Éq. 2).
Formule de Notation : Le score d'importance $P_i$ pour un nœud $v_i$ est la somme des probabilités softmax de toutes les arêtes entrantes (Éq. 3) :
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
où $p_{ji}$ représente le poids de proximité normalisé du voisin $v_j$ vers $v_i$ . Cela permet à la méthode de distinguer les nœuds ayant des degrés entrants égaux mais des proximités différentes avec leurs voisins.

3. Sélection Gourmande avec Suppression de Redondance

Le processus de sélection est un algorithme gourmand en un seul passage :

Calculer le score d'importance $P_i$ pour tous les nœuds.
Sélectionner le nœud ayant le score le plus élevé et l'ajouter au coreset $C$ .
Suppression de Redondance : Supprimer immédiatement le nœud sélectionné ainsi que tous ses voisins entrants du graphe. Le raisonnement est que si un nœud est sélectionné, ses voisins entrants (qui le considèrent comme un voisin proche) seront représentés par celui-ci et n'ont pas besoin d'être sélectionnés eux-mêmes.
Répéter jusqu'à ce que $M$ éléments soient sélectionnés.

Cette approche évite le recalcul répété des bénéfices, un goulot d'étranglement majeur dans les méthodes gourmandes traditionnelles.

Contributions Clés

Algorithme KNNG-CS : Une méthode de sélection de coreset basée sur la GA et scalable, qui utilise un graphe de K-plus proches voisins épars pour éviter les structures de distance denses coûteuses.
Mécanisme de Notation Novateur : Une fonction de notation des voisins entrants sensible à la distance qui estime la représentativité locale directement à partir du KNNG sans stocker de distances par paires denses.
Gains d'Efficacité : Validation empirique démontrant que la méthode réduit considérablement le temps de sélection et l'utilisation de la mémoire tout en maintenant une qualité de coreset comparable aux méthodes de pointe.

Résultats Expérimentaux

Les auteurs ont évalué KNNG-CS sur quatre jeux de données réels : CovType, IMDB, Brazil, et Card. Ils ont comparé leur méthode à l'échantillonnage aléatoire (Random sampling), CRAIG et FastCore.

Efficacité (Précision) : KNNG-CS a atteint une précision de test comparable à celle de CRAIG et FastCore, et nettement supérieure à l'échantillonnage aléatoire. Bien que CRAIG ait montré une précision légèrement plus élevée sur certains jeux de données (IMDB, Card, Brazil) en raison de son utilisation de distances exactes, KNNG-CS a maintenu des performances compétitives.
Efficacité (Temps) : KNNG-CS a démontré des accélérations substantielles :
- 2,3× à 41,2× plus rapide que CRAIG.
- 2,3× à 4,9× plus rapide que FastCore.
  L'accélération est attribuée à la construction efficace du KNNG et à la stratégie de sélection gourmande en un seul passage qui évite les calculs matriciels.
Utilisation de la Mémoire : KNNG-CS a drastiquement réduit la consommation de mémoire de pointe :
- N'a requis que 0,3 % à 3,4 % de la mémoire de pointe utilisée par CRAIG.
- N'a requis que 4,1 % à 7,5 % de la mémoire de pointe utilisée par FastCore.
  Cela s'explique par le fait que KNNG-CS ne stocke que $O(nK)$ arêtes, alors que ses concurrents stockent des matrices de distance $O(n^2)$ ou de grandes matrices de bornes élément-cluster.
Convergence : L'entraînement sur le coreset sélectionné a convergé beaucoup plus rapidement (en termes d'itérations) que l'entraînement sur l'ensemble complet, la taille du coreset $M=0.01n$ offrant un bon équilibre entre efficacité et effectivité.

Signification et Revendications

L'article affirme que KNNG-CS offre une solution pratique pour la sélection de coreset à grande échelle en passant de structures de distance globales et denses à des structures de voisinage locales et éparses. En exploitant la localité inhérente des espaces de caractéristiques, la méthode atteint :

Une complexité de stockage linéaire ($O(nK)$) comparée à la complexité quadratique ( $O(n^2)$ ) des méthodes précédentes de pointe.
Des réductions significatives des coûts de temps et de mémoire sans sacrifier la qualité du sous-ensemble sélectionné.
Un processus de sélection léger qui ne nécessite qu'un seul passage de sélection gourmante après la construction du graphe, éliminant le besoin de calculs de distance répétés.

Les auteurs concluent que cette approche permet une sélection de coreset efficace pour les grands jeux de données où les méthodes traditionnelles d'approximation de gradient sont trop coûteuses en termes de calcul ou de mémoire.