🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

Cet article introduit un nouveau cadre de sélection de données qui exploite l'approximation par rang faible et l'échantillonnage basé sur les résidus pour choisir efficacement un sous-ensemble pondéré de points de données, offrant des garanties théoriques et des améliorations empiriques par rapport aux méthodes traditionnelles basées sur le partitionnement de données pour les ensembles de données présentant une structure algébrique globale.

Auteurs originaux : Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Publié 2026-06-16

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

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

Imaginez que vous êtes un chef essayant de créer la meilleure soupe du monde. Vous avez un entrepôt massif rempli de milliers de légumes, d'épices et de bouillons différents (votre jeu de données). Pour préparer la soupe parfaite, vous devez goûter et mélanger chacun d'entre eux. Mais voici le problème : votre cuisine est minuscule, votre cuisinière est faible et vous ne disposez que de quelques heures. Cuisiner avec l'intégralité de l'entrepôt est impossible.

Vous devez choisir une petite poignée d'ingrédients parfaits qui donneront exactement la même saveur que l'ensemble de l'entrepôt. C'est le problème de la Sélection de Données.

L'ancienne méthode : Choisir par la « Distance »

Pendant un certain temps, les meilleurs chefs ont utilisé une méthode appelée Clustering (Regroupement). Imaginez que vous entrez dans l'entrepôt et que vous choisissez un légume de chaque coin distinct. Vous prenez une carotte au nord, une pomme de terre au sud, un poivron à l'est et une tomate à l'ouest.

La logique était la suivante : « Si je choisis des éléments qui sont éloignés les uns des autres, je dois couvrir tous les aspects. » Cela fonctionnait assez bien pour des recettes simples. Mais dans le monde moderne, où les données sont massives et complexes (comme un entrepôt contenant des millions d'articles), cette méthode présente une faille. Elle se concentre sur où se trouvent les éléments, et non sur ce qu'ils font réellement. Vous pourriez vous retrouver avec un sac rempli de légumes d'apparences différentes qui ont tous exactement le même goût, tout en manquant l'épice secrète qui définit réellement la saveur de la soupe.

La nouvelle méthode : Choisir par la « Structure »

Les auteurs de cet article disent : « Arrêtez de regarder où se trouvent les légumes. Regardez la forme de la saveur. »

Ils proposent une nouvelle méthode basée sur la Structure de Bas Rang (Low-Rank Structure).
Considérez vos ingrédients de soupe non pas comme des articles individuels, mais comme une sculpture 3D complexe. Même si la sculpture semble compliquée, elle pourrait en réalité être construite à partir de seulement quelques poutres et supports principaux. Le reste n'est que décoration.

Les Poutres Principales (Bas Rang) : Ce sont les directions de saveur les plus importantes. Si vous maîtrisez ces éléments, vous réussissez votre soupe.
La Décoration (Résidus) : Ce sont les petits détails insignifiants qui ne changent pas beaucoup le goût.

La méthode des auteurs utilise une « radiographie » mathématique (appelée Approximation de Bas Rang) pour trouver ces poutres principales. Au lieu de choisir des légumes qui sont éloignés les uns des autres, ils choisissent les ingrédients spécifiques qui soutiennent les poutres principales de la structure de la saveur.

Comment ils procèdent : L'échelle de « Sensibilité »

Pour déterminer quels ingrédients sont les « poutres principales », ils utilisent une technique appelée Échantillonnage par Sensibilité (Sensitivity Sampling).

Imaginez que vous avez une balance géante. Vous posez un légume dessus, et la balance vous dit : « Si vous laissez cet élément de côté, à quel point la saveur de la soupe va-t-elle changer ? »

Si la saveur change beaucoup, la balance s'affole. Ce légume est hautement sensible (très important).
Si la saveur change à peine, la balance reste basse. Ce légume a une faible sensibilité (redondant).

Leur algorithme calcule ce score pour chaque article de l'entrepôt, puis choisit un petit groupe d'ingrédients, mais de manière pondérée par leur importance. Vous avez beaucoup plus de chances de choisir les articles à « haute sensibilité ».

Les résultats : Pourquoi c'est important

Les auteurs ont testé cette idée de deux manières :

Le test de la carte de crédit : Ils ont tenté de prédire qui manquerait un paiement de carte de crédit en utilisant un jeu de données financières standard. Leur méthode « Bas Rang » a sélectionné un petit groupe de clients qui prédisait le résultat bien mieux que l'ancienne méthode de « Clustering » ou un choix aléatoire.
Le test du Cerveau Géant (LLM) : Ils ont tenté d'apprendre à une IA massive (Llama3-8B) à faire des mathématiques et à répondre à des questions. Entraîner l'IA sur l'ensemble du jeu de données prend un temps infini et coûte une fortune. En utilisant leur méthode pour ne choisir que 6 % à 25 % des données, ils ont entraîné l'IA pour qu'elle soit plus intelligente que si elles avaient utilisé des données aléatoires ou l'ancienne méthode de clustering.

La grande conclusion

L'article affirme que pour les jeux de données modernes et massifs, la « forme » des données (sa structure algébrique) est plus importante que la « distance » entre les points de données.

En se concentrant sur les principales structures porteuses des données plutôt que de simplement essayer de couvrir tous les coins, vous pouvez jeter 90 % de vos données et toujours entraîner un modèle d'apprentissage automatique qui performe aussi bien, ou même mieux, qu'avec l'intégralité de vos données. C'est comme réaliser que vous n'avez pas besoin de goûter chaque grain de sel dans l'océan pour savoir si la soupe est salée ; vous avez juste besoin de goûter la cuillerée qui représente le véritable caractère de l'océan.

Résumé Technique : Apprentissage Actif avec Structure de Bas Rang pour la Sélection de Données

Définition du Problème

Le papier traite du problème de la sélection de données en apprentissage automatique, plus précisément le défi consistant à identifier un sous-ensemble représentatif de petite taille (un coreset) qui permet un entraînement efficace des modèles sans compromettre significativement les performances. Bien que les jeux de données modernes et les modèles de fondation aient favorisé le succès, ils engendrent des coûts de calcul élevés pour l'entraînement et le réglage fin (fine-tuning).

Les approches existantes, telles que celles de Sener et Savarese [SS18] et Axiotis et al. [ACH+24], reposent sur des heuristiques basées sur le partitionnement (clustering) (par exemple, $k$ -center ou $k$ -means) appliquées aux plongements (embeddings) de données. Ces méthodes supposent que les données possèdent une structure géométrique intrinsèque où la diversité et la distance entre les points sont les principaux moteurs de l'informativité. Cependant, les auteurs soutiennent que de nombreux jeux de données modernes, particulièrement dans les espaces de haute dimension, présentent une structure algébrique globale mieux capturée par des approximations de bas rang (par exemple, l'Analyse en Composantes Principales) plutôt que par un partitionnement géométrique local. Les méthodes de clustering peuvent échouer à capturer les directions dominantes de variance, risquant ainsi de manquer des composantes critiques pour l'entraînement du modèle.

Méthodologie

Le papier propose un nouveau cadre pour la sélection de données basé sur l'approximation de bas rang et l'échantillonnage de sensibilité basé sur le résidu. L'idée centrale est de prioriser la préservation des directions spectrales dominantes des données plutôt que de simplement maximiser la diversité géométrique.

Cadre Théorique

L'approche est fondée sur le problème de la Sélection de Sous-ensembles de Lignes (Row Subset Selection) et la construction de coreset préservant la perte. Les auteurs introduisent l'Hypothèse 2.1, qui postule que pour un jeu de données $D$ avec une matrice d'embedding, la fonction de perte $\ell$ peut être décomposée par rapport à un sous-espace $V$ de dimension $k$ (engendré par les vecteurs singuliers supérieurs ou les composantes principales) :

Pénalité Orthogonale : La déviation de la perte pour un point $y$ hors du sous-espace $V$ est bornée de manière quadratique par la norme de sa composante résiduelle $r(y)$ orthogonale à $V$ , mise à l'échelle par une constante $\lambda$ .
Approximation de Sous-espace : À l'intérieur du sous-espace $V$ , la perte est bien approximée par une somme pondérée des pertes le long des directions de base, mise à l'échelle par une constante $\gamma$ .

Cette hypothèse formalise l'intuition selon laquelle les directions orthogonales au sous-espace de bas rang dominant contribuent moins à la perte ou sont moins informatives, une propriété observée dans des tâches telles que la PCA, la complétion de matrice et l'Adaptation de Bas Rang (LoRA).

Algorithme : Échantillonnage de Sensibilité

L'algorithme proposé (Algorithme 2) construit un coreset pondéré $S$ via les étapes suivantes :

Sketch de Bas Rang : Calculer une approximation de rang- $k$ du jeu de données (par exemple, via SVD) pour définir le sous-espace $V$ et sa base $\{v_1, \dots, v_k\}$ .
Décomposition : Pour chaque point de donnée $x$ , décomposer l'élément en une projection $v(x)$ sur $V$ et un résidu $r(x)$ orthogonal à $V$ .
Calcul du Score de Sensibilité : Calculer un score de sensibilité $\sigma(x)$ $σ (x)$ pour chaque point qui combine :
- La perte pondérée le long des directions de base : $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ .
- Une pénalité pour le résidu : $\lambda \|r(x)\|_2^2$ .
- Un terme constant lié à la perte maximale dans la base.
Échantillonnage : Échantillonner des points à partir du jeu de données avec remise, proportionnellement à leurs scores de sensibilité normalisés $p(x) = \sigma(x) / \sum \sigma(y)$ .
Pondération : Assigner des poids $w(x) = 1/(s \cdot p(x))$ aux points échantillonnés pour garantir que l'estimateur soit non biaisé.

Contributions Clés

Garanties Théoriques (Théorèmes 2.2 & 2.3) : Le papier prouve qu'un sous-ensemble pondéré de taille $\tilde{O}(k + 1/\varepsilon^2)$ peut approximer la perte moyenne du jeu de données complet avec une erreur relative de $(1 \pm \varepsilon)$ , jusqu'à un terme additif proportionnel au coût d'approximation de rang- $k$ optimal $\Phi_k(D)$ .
- Le Théorème 2.2 garantit cela pour un sous-ensemble pondéré général.
- Le Théorème 2.3 étend cela à la Sélection de Sous-ensembles de Lignes, garantissant que le sous-ensemble sélectionné est composé de points de données réels issus du jeu de données d'entrée.
- La borne d'erreur dépend explicitement de $\Phi_k(D)$ , indiquant que les jeux de données présentant une forte structure de bas rang produisent des bornes plus serrées et des coresets plus précis.
Innovation Algorithmique : Les auteurs introduisent un algorithme d'échantillonnage de sensibilité qui exploite la structure de bas rang pour calculer des scores d'importance, se distinguant des métriques de distance géométrique utilisées dans les méthodes de clustering.
Validation Empirique : Le cadre est validé sur des données tabulaires (jeu de données Credit Card Default) et sur le réglage fin de grands modèles de langage (Llama3-8B et Qwen2.5-3B sur les tâches GSM8k, ViGGO et SQL).

Résultats Expérimentaux

Le papier évalue la méthode proposée Low-Rank Sensitivity Sampling (Low-rank SS) par rapport à plusieurs bases : Échantillonnage Uniforme, $k$ -Center, Échantillonnage de Sensibilité basé sur le Clustering, et Graph Cut.

Données Tabulaires (Jeu de données Credit Card) :
- Low-rank SS a obtenu l'erreur d'approximation la plus faible en somme des carrés, réduisant l'erreur d'un ordre de grandeur par rapport à l'échantillonnage aléatoire et d'environ 50 % par rapport au clustering pour de petits échantillons ( $s=1000$ ).
- Dans la régression logistique en aval, Low-rank SS a atteint jusqu'à 74 % de précision de test à $s=5000$ , surpassant le clustering (70 %) et l'échantillonnage aléatoire (67 %).
Réglage Fin de LLM (Llama3-8B & Qwen2.5-3B) :
- Sur les tâches GSM8k, ViGGO et SQL, Low-rank SS a systématiquement surpassé l'échantillonnage uniforme et les méthodes basées sur le clustering.
- Par exemple, sur ViGGO avec Llama3-8B à 25 % de compression de données, Low-rank SS a atteint 77,6 % de précision contre 74,9 % pour le SS basé sur le clustering.
- Transférabilité : Les sous-ensembles sélectionnés à l'aide d'un modèle plus grand (Llama3-8B) ont été transférés avec succès à un modèle plus petit (Qwen2.5-3B), surpassant même les sous-ensembles sélectionnés directement par le modèle cible, ce qui suggère que le critère de bas rang capture des propriétés intrinsèques des données.
- Ablation : La méthode s'est révélée robuste au choix de la sélection de la base, l'échantillonnage par score de levier (leverage score) étant le plus performant, bien que même la sélection de base uniforme ait donné des résultats compétitifs.
Analyse de Structure : Les expériences sur GSM8k ont démontré que le jeu de données présente une erreur d'approximation plus faible sous les hypothèses de bas rang par rapport au clustering, validant l'applicabilité de l'Hypothèse 2.1.

Signification et Revendications

Le papier prétend fournir une alternative robuste et efficace au sous-échantillonnage naïf et à la sélection de données basée sur le clustering, particulièrement pour les contextes de haute dimension et de grande échelle.

Contribution Théorique : Il établit des garanties rigoureuses pour la sélection de données sous des hypothèses de perte de bas rang, liant la qualité du coreset directement à l'alignement du jeu de données avec une structure de bas rang ( $\Phi_k(D)$ ).
Impact Pratique : Les auteurs démontrent que des embeddings simples provenant de modèles pré-entraînés (comme BERT) sont suffisants pour approximer la structure de bas rang nécessaire pour sélectionner des points informatifs, même pour des modèles cibles beaucoup plus grands (LLM).
Efficacité : L'approche évite les contraintes computationnelles liées au calcul des scores d'incertitude sur l'ensemble des données (courant en apprentissage actif) et les problèmes de redondance des sélections par lots basées sur le clustering.
Modestie : Les auteurs reconnaissent que si le clustering conserve de la valeur dans certains cas, leur approche de bas rang offre une base plus fiable pour l'entraînement efficace des modèles à grande échelle où les directions spectrales dominantes sont critiques. Ils ne revendiquent pas une optimalité universelle mais un progrès significatif dans les configurations où les données présentent une structure algébrique globale.