FAST: Topology-Aware Frequency-Domain Distribution Matching for Coreset Selection

Each language version is independently generated for its own context, not a direct translation.

Imaginez que vous devez préparer un grand dîner pour 10 000 personnes, mais votre cuisine est minuscule et votre four ne peut cuire que 10 plats à la fois. Si vous essayez de cuisiner tout le menu d'un coup, vous allez épuiser votre énergie, brûler votre four et mettre des jours à tout préparer.

C'est exactement le problème que rencontrent les intelligences artificielles (IA) aujourd'hui : elles ont besoin de milliards de données pour apprendre, ce qui demande une énergie colossale et des ordinateurs gigantesques.

La solution habituelle ? Essayer de choisir les "meilleurs" 100 plats (les données) pour que l'IA apprenne aussi bien qu'avec les 10 000. C'est ce qu'on appelle la sélection de "Coreset" (un sous-ensemble représentatif).

Mais jusqu'à présent, les méthodes pour choisir ces plats avaient deux gros défauts :

Elles étaient trop dépendantes de la recette du chef : Elles utilisaient un modèle IA spécifique pour juger les données, ce qui biaisait le choix (comme si un chef italien ne choisissait que des pâtes parce qu'il ne connaît que ça).
Elles regardaient mal les plats : Elles se contentaient de comparer la couleur ou le poids moyen des ingrédients (des statistiques simples), sans voir la texture, le goût complexe ou les saveurs cachées.

Voici comment FAST change la donne, expliqué simplement :

1. Le Concept : La "Carte des Saveurs" (Le Domaine Fréquentiel)

Imaginez que chaque image ou texte est comme une symphonie musicale.

Les basses fréquences sont les notes graves : elles donnent la structure globale, la forme générale du plat (c'est un steak ou une salade ?).
Les hautes fréquences sont les aigus : elles donnent les détails fins, les textures, les bords nets, les épices (la croûte croustillante, les herbes hachées).

Les anciennes méthodes écoutaient seulement les basses notes. Elles savaient que c'était un steak, mais elles ne savaient pas s'il était bien cuit ou s'il avait des herbes. FAST, lui, écoute toute la symphonie, des graves aux aigus, pour s'assurer que le petit menu choisi a exactement le même "goût" et la même "texture" que le grand menu original.

2. Le Problème du "Silence des Aigus"

Il y avait un petit souci technique : dans les méthodes précédentes, plus on montait dans les aigus (les détails fins), plus le signal devenait faible et difficile à entendre. C'était comme essayer d'entendre un chuchotement dans une tempête. Les détails importants (comme les bords d'un oiseau ou la texture d'une pierre) étaient ignorés.

FAST a inventé un nouveau "microphone" (appelé PD-CFD) qui amplifie spécifiquement ces chuchotements dans les hautes fréquences, sans se laisser brouiller par le bruit. Il permet de voir les détails les plus fins que les autres méthodes rataient.

3. La Méthode : Une Danse Organisée (Topologie)

Pour choisir les bons plats, FAST ne se contente pas de les regarder isolément. Il regarde comment ils sont connectés entre eux, comme une carte de métro.

Il crée une toile d'araignée (un graphe) qui relie les données similaires.
Il s'assure que le petit menu choisi garde la même structure de connexion que le grand menu. Si dans le grand menu, les "steaks" sont connectés aux "pommes de terre" et aux "vins rouges", le petit menu doit garder ces liens. Cela évite de choisir 10 steaks identiques et d'oublier les légumes.

4. L'Entraînement Progressif : Du Gros au Fin

Au lieu de tout apprendre d'un coup, FAST utilise une stratégie d'apprentissage progressif (comme un étudiant qui apprend d'abord l'alphabet, puis les mots, puis les phrases) :

D'abord, il s'assure que le contour global est bon (les basses fréquences).
Ensuite, il affine les détails (les hautes fréquences).
Cela évite que l'IA ne se trompe en essayant de mémoriser des détails trop tôt, ce qui la rendrait confuse.

Pourquoi c'est génial ? (Les Résultats)

Pas de chef IA nécessaire : Contrairement aux autres méthodes, FAST n'a pas besoin d'une IA lourde pour choisir les données. Il fait le travail tout seul, comme un chef qui a un palais très fin sans avoir besoin de tester chaque plat.
Économie d'énergie massive : Parce qu'il est si efficace, il consomme 96% moins d'énergie que les méthodes actuelles. C'est comme passer d'une voiture qui consomme 20L/100km à une trottinette électrique.
Performance supérieure : Même avec un ordinateur portable basique (sans carte graphique puissante), il bat les meilleurs systèmes du monde. Il améliore la précision de l'IA de près de 9% en moyenne, ce qui est énorme dans ce domaine.

En résumé :
FAST est comme un sommelier génial qui, au lieu de goûter chaque bouteille d'un vignoble immense, écoute la "fréquence" de tout le vin pour sélectionner le petit échantillon parfait. Il garantit que le verre que vous buvez a exactement la même complexité, la même texture et le même goût que le tonneau entier, le tout en utilisant une fraction de l'énergie nécessaire.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

La sélection de coreset (sous-ensemble représentatif) vise à compresser de grands ensembles de données en des sous-ensembles compacts pour réduire les coûts énergétiques et computationnels de l'entraînement des réseaux de neurones profonds (DNN). Cependant, les méthodes existantes souffrent de limitations majeures :

Approches basées sur DNN (DNN-based) : Elles utilisent un réseau proxy pour évaluer l'importance des échantillons. Cela introduit un biais architectural (les résultats dépendent de l'architecture spécifique du réseau) et limite la généralisation. De plus, elles sont coûteuses en calcul.
Approches sans DNN (DNN-free) : Elles reposent sur des heuristiques (comme la distance euclidienne ou des critères de diversité) qui manquent de garanties théoriques rigoureuses pour assurer la stabilité et la précision.
Défaillance de l'alignement distributionnel : Ni l'une ni l'autre ne contraint explicitement l'équivalence distributionnelle complète. Les métriques classiques (MSE, KL, CE, MMD) échouent souvent à capturer les différences de moments d'ordre supérieur et les corrélations multivariées complexes.
Le fossé continu-discret : Les méthodes d'optimisation continue (comme l'appariement de distribution par gradient) sont difficiles à appliquer directement à la sélection discrète d'échantillons sans perdre la correspondance avec le manifold de données original.

2. Méthodologie : Le Framework FAST

Les auteurs proposent FAST (Frequency-domain Aligned Sampling via Topology), le premier cadre de sélection de coreset sans DNN basé sur l'appariement de distribution dans le domaine fréquentiel, résolvant le problème continu-discret via la théorie des graphes spectraux.

A. Construction du Graphes et Contraintes Topologiques

Pour combler le fossé entre l'optimisation continue et la sélection discrète, FAST construit un graphe pondéré multi-échelle basé sur la théorie topologique floue (inspirée de UMAP).

Encodage Spectral : Les vecteurs propres du Laplacien normalisé du graphe servent d'approximation discrète de l'opérateur de Laplace-Beltrami, capturant la géométrie intrinsèque du manifold des données.
Contraintes d'Alignement : L'optimisation du coreset continu $\tilde{Y}$ $\tilde{Y}$ est guidée par :
- Une contrainte de diversité (basée sur les Processus Ponctuels Déterminantaux - DPP) pour éviter la redondance.
- Une contrainte d'alignement topologique (inspirée de GUNN) qui assure une correspondance bijective entre les points optimisés et les échantillons originaux via l'algorithme hongrois, préservant ainsi la structure locale du graphe.

B. Distance de Fonction Caractéristique (CFD) et PD-CFD

Au lieu de métriques spatiales, FAST utilise la Distance de Fonction Caractéristique (CFD) dans le domaine fréquentiel.

Avantage théorique : La fonction caractéristique (transformée de Fourier de la distribution) capture de manière unique tous les moments et les corrélations intrinsèques, garantissant une équivalence distributionnelle complète.
Problème du gradient de phase : Les auteurs identifient que la CFD standard souffre d'un problème de "gradient de phase qui s'évanouit" dans les régions de fréquence moyenne et élevée. En effet, l'amplitude du spectre diminue avec la fréquence (lemme de Riemann-Lebesgue), ce qui atténue le gradient de phase et empêche l'optimiseur de capturer les détails fins (textures, bords).
Solution : PD-CFD (Phase-Decoupled CFD) : Ils introduisent une fonction de perte où la pénalité de phase est découplée de l'amplitude. Une fonction de pondération adaptative $\lambda_\phi(\omega)$ atténue le bruit dans les hautes fréquences tout en amplifiant le signal de phase dans les fréquences moyennes, permettant de préserver les structures fines.

C. Échantillonnage Progressif Sensible aux Disparités (PDAS)

Pour une convergence stable, FAST n'utilise pas toutes les fréquences simultanément.

Stratégie Curriculum : L'algorithme sélectionne progressivement les fréquences, des basses (structure globale) vers les hautes (détails locaux).
Initialisation Anisotrope : Un espace de fréquences anisotrope est construit pour être sensible à la distribution spécifique des données.
Échantillonnage : À chaque itération, les fréquences les plus discriminantes (celles où la disparité distributionnelle est maximale) sont sélectionnées, évitant ainsi l'instabilité causée par une optimisation prématurée des détails fins.

3. Contributions Clés

Premier cadre DNN-free d'appariement de distribution : FAST élimine le biais architectural en ne dépendant d'aucun réseau de neurones pour la sélection, tout en permettant l'application de l'optimisation par gradient dans le domaine discret grâce aux contraintes topologiques.
Utilisation innovante de la CFD : C'est la première application de la distance de fonction caractéristique pour la sélection de coreset, offrant une garantie théorique sur l'alignement complet de la distribution.
Innovation PD-CFD : Résolution du problème de gradient de phase s'évanouissant, permettant une capture précise des moments d'ordre supérieur et des structures à haute fréquence.
Stratégie PDAS : Une méthode d'échantillonnage curriculum qui assure une convergence stable et rapide avec un nombre minimal de fréquences.

4. Résultats Expérimentaux

Les expériences ont été menées sur divers benchmarks (CIFAR-10/100, SVHN, TinyImageNet, DTD, RESISC45) et sur des tâches de LLM (Alpaca/LLaMA).

Performance Précision : FAST surpasse systématiquement les méthodes de l'état de l'art (SOTA), tant basées sur DNN que sans DNN.
- Gain moyen de 9,12 % par rapport aux méthodes DNN-free SOTA.
- Gain moyen de 17,63 % par rapport aux méthodes basées sur DNN.
- Performances exceptionnelles sur les données riches en textures (DTD, RESISC45) où les méthodes basées sur des métriques classiques échouent.
Généralisation Cross-Architecture : Le coreset sélectionné par FAST fonctionne efficacement sur des architectures variées (ResNet, ViT, MobileNet) sans perte de performance significative, prouvant son indépendance vis-à-vis de l'architecture.
Efficacité Énergétique et Computationnelle :
- Réduction de la consommation d'énergie de 96,57 % par rapport aux méthodes basées sur DNN.
- Accélération moyenne de 2,2x même sur CPU (avec seulement 1,7 Go de mémoire).
- Le temps de sélection est drastiquement réduit car aucune inférence de réseau profond n'est requise.
Tâches LLM : Sur le dataset Alpaca pour le fine-tuning de LLaMA-7B, FAST améliore la précision de 2,6 % par rapport à la méthode SOTA sans DNN, démontrant sa capacité à préserver la structure sémantique complexe.

5. Signification et Impact

Ce travail marque un tournant dans la sélection de données pour l'apprentissage automatique :

Théorique : Il démontre que l'appariement de distribution complet (via la fonction caractéristique) est réalisable et supérieur aux heuristiques ou aux métriques de moments d'ordre inférieur (comme le KL ou le MSE) pour la compression de données.
Pratique : En éliminant la dépendance aux DNN pour la sélection, FAST rend le processus de compression de données économe en énergie et déployable sur des appareils périphériques (edge devices) aux ressources limitées.
Généralité : La capacité à capturer les structures de haute fréquence et les dépendances complexes rend cette méthode particulièrement adaptée aux tâches de reconnaissance fine (textures, images satellites) et de compréhension sémantique (LLM), là où les méthodes précédentes échouaient.

En résumé, FAST propose une approche rigoureuse, mathématiquement fondée et extrêmement efficace pour réduire la taille des ensembles de données tout en préservant l'intégrité de la distribution originale, ouvrant la voie à un entraînement de modèles d'IA plus durable et accessible.