🤖 AI

Constraint-Data-Value-Maximization: Utilizing Data Attribution for Effective Data Pruning in Low-Data Environments

Ce papier introduit la maximisation de la valeur des données sous contraintes (CDVM), une approche novatrice qui formule l'élagage des données comme un problème d'optimisation sous contraintes afin de maximiser efficacement l'influence du modèle tout en pénalisant les contributions excessives par test, surpassant ainsi les méthodes traditionnelles basées sur la valeur de Shapley dans les scénarios à faible quantité de données.

Auteurs originaux : Danilo Brajovic, David A. Kreplin, Marco F. Huber

Publié 2026-05-13

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Danilo Brajovic, David A. Kreplin, Marco F. Huber

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 soupe parfaite. Vous avez un garde-manger immense rempli d'ingrédients (vos données), mais votre cuisine est petite, votre fourneau est faible, et vous n'avez que le temps de cuisiner avec une infime fraction de ce que vous possédez. Vous devez jeter la plupart des ingrédients, mais conserver ceux qui donnent le meilleur goût à la soupe.

C'est le problème auquel les modèles d'apprentissage automatique sont confrontés aujourd'hui. Ils ont besoin de quantités massives de données pour apprendre, mais stocker et traiter toutes ces données est coûteux et lent. L'objectif est le élagage des données : déterminer quels morceaux spécifiques de données sont les « épices secrètes » et lesquels ne sont que du « remplissage » qu'on peut jeter sans gâcher le plat.

L'Ancienne Méthode : Le « Concours de Popularité »

Pendant un certain temps, les scientifiques ont tenté de résoudre ce problème en utilisant une méthode basée sur les valeurs de Shapley (un concept issu de la théorie des jeux). Imaginez cela comme un concours de popularité où chaque ingrédient reçoit un score basé sur la mesure dans laquelle il aide la soupe lorsqu'il est ajouté à différentes combinaisons d'autres ingrédients.

L'article soutient que cette ancienne méthode présente un défaut fatal : Elle déteste les groupes.

Imaginez que votre garde-manger contient :

100 pommes de terre identiques (un grand groupe).
1 truffe unique et rare (un petit groupe).

L'ancienne méthode observe les pommes de terre et dit : « Eh bien, nous en avons tant que n'importe quelle pomme de terre individuelle n'est pas si spéciale. Vous êtes tous redondants. » Elle leur attribue donc un score très bas. Elle observe la truffe unique et dit : « Vous êtes unique ! Vous êtes essentiel ! » Elle lui attribue donc un score élevé.

Le Désastre : Lorsque le chef commence à jeter les ingrédients « à faible score », il jette d'abord 99 pommes de terre. Mais ensuite, il n'a plus de pommes de terre du tout. Soudain, la soupe n'a plus d'amidon du tout et elle a un goût terrible. La méthode a éliminé le groupe entier de pommes de terre trop tôt car elle n'a pas réalisé que, même si les pommes de terre étaient similaires, le groupe dans son ensemble était vital.

La Nouvelle Solution : CDVM (Le Chef de la « Couverture Équitable »)

Les auteurs introduisent une nouvelle méthode appelée Maximisation de la Valeur des Données Contrainte (CDVM). Au lieu de simplement attribuer un score à chaque ingrédient individuel et de les trier du meilleur au pire, le CDVM agit comme un chef intelligent qui se soucie de l'équilibre.

Voici comment le CDVM fonctionne, en utilisant une analogie simple :

Le Menu (L'Ensemble de Test) : Imaginez que vous avez un menu de 100 clients différents, chacun ayant une préférence gustative spécifique (par exemple, certains aiment le salé, d'autres le sucré, d'autres le pimenté).
L'Objectif : Vous voulez choisir un petit panier d'ingrédients (disons 10 articles) qui satisfera tout le monde sur le menu.
La Contrainte : Le CDVM ne se contente pas de demander : « Quel ingrédient rend la soupe meilleure dans l'ensemble ? » Il demande : « Si je choisis cet ingrédient, aide-t-il les clients pimentés ? Aide-t-il les clients sucrés ? »

Le CDVM établit une règle : Aucun client sur le menu ne doit être laissé complètement insatisfait.

Si l'ancienne méthode choisirait 9 pommes de terre et 1 truffe (en ignorant que les pommes de terre sont nécessaires pour les clients « féculents »), le CDVM dit : « Attendez une minute. Si je choisis 9 pommes de terre, j'ignore les clients « pimentés » qui ont besoin d'un poivron. Remplaçons quelques pommes de terre par un poivron pour nous assurer que tout le monde obtient quelque chose. »

Il traite le problème comme un puzzle où vous devez maximiser le bonheur total des clients tout en veillant à ce qu'aucun client unique ne soit ignoré. Il force la sélection à conserver au moins un représentant de chaque « groupe » d'ingrédients jusqu'à ce qu'elle doive absolument les laisser partir.

Pourquoi Cela Importe

L'article a testé cette nouvelle méthode contre les anciennes méthodes de concours de popularité sur six ensembles de données différents (comme des images de voitures, des critiques de texte et des données médicales).

Le Résultat : Lorsque les chefs ont été forcés d'utiliser de très petites quantités de données (comme ne garder que 5 % ou 10 % des ingrédients d'origine), la méthode CDVM a produit des soupes (modèles) bien meilleures que les anciennes méthodes.
L'Insight « Budget » : L'article a également découvert quelque chose de surprenant : les 10 % « meilleurs » d'ingrédients ne sont pas nécessairement un sous-ensemble des 20 % « meilleurs ». Parfois, les 10 % parfaits incluent un ingrédient étrange que vous auriez gardé dans le tas des 20 % mais que vous auriez jeté dans le tas des 5 %. Le CDVM est assez intelligent pour recalculer le mélange parfait pour chaque taille de budget spécifique, plutôt que d'utiliser simplement une seule liste « du meilleur au pire ».

La Conclusion

L'article affirme qu'en changeant notre façon de considérer les données — passant du « classement des individus » à « l'optimisation pour une couverture équilibrée » — nous pouvons réduire considérablement la taille de nos ensembles de données d'entraînement sans perdre en performance. Cela économise de l'énergie et de l'argent, surtout lorsque nous travaillons avec des données très limitées.

En bref : L'ancienne méthode consistait à jeter toutes les pommes de terre parce qu'une pomme de terre individuelle n'est pas spéciale. La nouvelle méthode (CDVM) dit : « Gardons quelques pommes de terre, quelques carottes et quelques épices, afin que, peu importe ce que le client veut, nous ayons quelque chose à offrir. »

Résumé technique : Maximisation de la valeur des données sous contraintes pour l'élagage efficace des données dans des environnements à faible volume de données

1. Énoncé du problème

Les modèles d'apprentissage automatique, en particulier les grands modèles de langage, font face à une demande insatiable de données alors que la disponibilité de celles-ci stagne. Les méthodes d'évaluation des données visent à attribuer l'influence des instances d'entraînement individuelles sur les performances du modèle afin de réduire la taille des jeux de données, économisant ainsi de l'énergie et améliorant l'efficacité de l'entraînement. Cependant, les approches existantes pour l'élagage des données (suppression des données à faible valeur) souffrent de limitations critiques, en particulier dans les environnements à faible volume de données où seule une petite fraction du jeu de données subsiste.

Les auteurs identifient trois lacunes principales dans les méthodes actuelles de l'état de l'art (spécifiquement les approches basées sur les valeurs de Shapley et Banzhaf) :

Biais de taille de cluster : Les valeurs de Shapley et Banzhaf répartissent l'utilité totale d'un cluster parmi ses membres. Par conséquent, les points appartenant à de grands clusters de données reçoivent des valeurs marginales plus faibles que ceux des petits clusters. Cela conduit à la suppression prématurée de clusters entiers, provoquant des chutes brutales des performances du modèle une fois que le dernier représentant d'un cluster est élagué.
Biais de redondance : Les méthodes Leave-One-Out (LOO) attribuent souvent une valeur nulle aux échantillons redondants, échouant à distinguer l'utilité de conserver un représentant unique par rapport à plusieurs.
Sous-ensembles optimaux non imbriqués : Le sous-ensemble de données qui maximise la précision pour un budget de rétention spécifique (par exemple 10 %) n'est pas nécessairement un sous-ensemble de l'ensemble optimal pour un budget différent (par exemple 5 %). Les stratégies d'élagage standard qui supposent une imbrication échouent à s'adapter à ces optima spécifiques au budget.

2. Méthodologie : Maximisation de la valeur des données sous contraintes (CDVM)

Pour remédier à ces limitations, les auteurs proposent la Maximisation de la valeur des données sous contraintes (CDVM), un cadre basé sur l'optimisation qui traite l'élagage des données comme un problème d'optimisation sous contraintes sur une matrice d'attribution de données.

Concepts de base

Matrice d'attribution de données ( $T$ ) : Contrairement aux valeurs scalaires des données, la CDVM utilise une matrice $T \in \mathbb{R}^{n \times m}$ où $n$ est le nombre d'instances d'entraînement et $m$ le nombre d'instances de test. L'entrée $T_{i,j}$ quantifie l'influence de l'instance d'entraînement $i$ sur la prédiction de l'instance de test $j$ . Cette matrice est estimée en utilisant le principe de réutilisation maximale des échantillons (MSR), en entraînant des modèles sur des sous-ensembles échantillonnés pour approximer l'influence sans réentraînement complet pour chaque instance.
Formulation de l'optimisation : La CDVM formule l'élagage comme la sélection d'un vecteur binaire $w \in \{0, 1\}^n$ $w \in {0, 1}^{n}$ (indiquant quelles $S$ $S$ instances d'entraînement conserver) pour maximiser une fonction d'utilité sous contraintes.
- Objectif : Maximiser l'influence totale sur les échantillons de test tout en pénalisant une concentration excessive de l'influence sur quelques échantillons de test.
- Contrainte : Le nombre d'instances conservées doit être égal au budget $S$ .
- Variables d'écart : Pour éviter le scénario du « gagnant prend tout » où quelques échantillons de test dominent l'utilité, la méthode introduit des variables d'écart $t_j$ qui plafonnent l'influence par échantillon de test à un seuil $\kappa$ . Toute influence dépassant $\kappa$ est pénalisée.

Le problème d'optimisation formel est :
$\begin{aligned} \max_{w, t} \quad & \alpha \sum_{j=1}^m v_j - (1-\alpha) \sum_{j=1}^m t_j \\ \text{s.t.} \quad & v = T^\top w \\ & \sum_{i=1}^n w_i = S \\ & t_j \ge 0, \quad t_j \ge v_j - \kappa \\ & w_i \in \{0, 1\} \end{aligned}$
où $v_j$ est l'utilité induite pour l'échantillon de test $j$ , et $\alpha$ équilibre l'utilité totale par rapport à la pénalité pour dépassement du seuil.

Implémentation

Les auteurs relâchent la contrainte binaire $w_i \in \{0, 1\}$ vers $w_i \in [0, 1]$ pour résoudre le problème comme un Programme Linéaire en Nombres Entiers Mixtes (MILP) en utilisant le cadre de Programmation Paramétrée Disciplinée. Après résolution, les $S$ premières entrées de $w$ sont conservées. Cette approche assure une couverture équilibrée, garantissant qu'aucun échantillon de test (et donc aucun cluster de données implicite) ne se retrouve avec une influence totale nulle tant que le budget le permet.

3. Contributions clés

L'article apporte quatre contributions principales :

Analyse des limitations existantes : Les auteurs démontrent théoriquement et empiriquement que les attributions de Shapley et Banzhaf allouent des contributions marginales plus faibles aux instances appartenant à de grands clusters de données, conduisant à des schémas de suppression déséquilibrés et à des performances d'élagage sous-optimales dans les régimes à faible volume de données.
Insight sur la spécificité du budget : Ils montrent que les ensembles de rétention optimaux sont spécifiques au budget ; le sous-ensemble maximisant la précision pour un niveau de rétention donné ne contient pas nécessairement le sous-ensemble optimisé pour un autre.
Algorithme CDVM : L'introduction de la CDVM, qui pose l'élagage comme une optimisation sur une matrice d'attribution, traitant explicitement les biais de redondance et de taille de cluster en imposant une influence équilibrée sur les échantillons de test.
Étalonnage : Évaluation complète sur six jeux de données du benchmark OpenDataVal, démontrant de fortes performances et un temps d'exécution compétitif par rapport aux techniques de l'état de l'art.

4. Résultats expérimentaux

Les auteurs ont évalué la CDVM sur six jeux de données du benchmark OpenDataVal (incluant CIFAR-10, Adult, IMDB, BBC, Pol et Nomao) sur des niveaux de rétention allant de 5 % à 30 %.

Performance : La CDVM a atteint des performances de l'état de l'art dans 28 configurations sur 36 (6 jeux de données × 6 taux d'élagage). Elle a systématiquement surpassé la suppression aléatoire, DataBanzhaf et les méthodes DataOob/Mémorisation.
Comparaison avec l'optimisation de l'influence : Bien que la méthode d'optimisation de l'influence (Yang et al., 2023) ait été compétitive sur certains jeux de données (notamment Nomao), la CDVM était la seule méthode à battre systématiquement les bases aléatoires sur les six benchmarks lorsque les hyperparamètres étaient correctement ajustés.
Efficacité temporelle : La CDVM offre un meilleur compromis vitesse-précision. Bien que le calcul de la matrice d'attribution $T$ soit le principal goulot d'étranglement (partagé par toutes les méthodes basées sur des semi-valeurs), l'étape d'optimisation est rapide. La CDVM avec 5 000 modèles a obtenu des résultats comparables ou supérieurs à des méthodes nécessitant 10 000 modèles, avec un temps d'optimisation significativement inférieur à celui de l'optimisation de l'influence (qui nécessite l'inversion de la Hessienne).
Robustesse : La méthode est robuste aux choix d'hyperparamètres. Une configuration par défaut ( $\alpha=0.5$ , $\kappa$ dérivé des statistiques du jeu de données) a performé presque aussi bien que des paramètres recherchés par grille, sans aucun surcoût de recherche.

5. Signification et revendications

L'article revendique que la CDVM fournit une solution robuste pour l'élagage des données dans les régimes à faible volume de données, un scénario où les méthodes existantes basées sur Shapley échouent souvent en raison de leurs biais inhérents. En passant de valeurs scalaires de données à une optimisation sous contraintes sur une matrice d'attribution, la CDVM garantit que le jeu de données restant maintient une couverture équilibrée de la distribution de test.

Les auteurs soulignent que leurs résultats mettent en évidence « une marge substantielle d'amélioration de l'élagage des données », ce qui se traduit directement par une réduction des coûts d'entraînement et de la consommation d'énergie. Ils notent que, bien que la CDVM soit compétitive sur le plan computationnel, le principal goulot d'étranglement reste le calcul et le stockage de la matrice d'attribution $T$ . Un travail futur pourrait explorer des estimateurs d'attribution plus efficaces ou exploiter la parcimonie de $T$ pour passer à l'échelle sur des jeux de données plus volumineux comme ImageNet.

L'article conclut que la CDVM exploite efficacement les attributions de données pour élaguer les exemples à faible valeur sans sacrifier la qualité du modèle, offrant une alternative pratique à la sélection aléatoire et aux stratégies d'élagage existantes basées sur l'évaluation.