Résumé technique : NASH - Agrégation non linéaire de composantes informatives de Shapley

Énoncé du problème

La sélection de données vise à identifier des sous-ensembles de haute qualité de données d'entraînement pour optimiser l'utilité du modèle (par exemple, la précision de validation $u_V$) sous des contraintes de taille. Bien que la valeur de Shapley des données et ses généralisations (semi-valeurs) soient théoriquement fondées sur la théorie des jeux coopératifs pour prendre en compte les interactions entre les données, des études empiriques récentes indiquent qu'elles sont souvent inefficaces en pratique. Plus précisément, sélectionner les $m$ points de données les mieux classés selon les valeurs de Shapley calculées par rapport à des fonctions d'utilité complexes (comme la précision de validation) peut produire des sous-ensembles non meilleurs, voire pires, qu'une sélection aléatoire.

L'article identifie deux raisons principales à cet échec :

1. Manque d'information de Shapley : Les fonctions d'utilité complexes impliquent plusieurs « rôles » distincts (par exemple, différentes classes ou sous-populations dans l'ensemble de validation). Une seule valeur de Shapley pour une donnée échoue à capturer sa force unique à travers ces rôles. Par conséquent, des données ayant des forces différentes peuvent recevoir des scores de Shapley identiques, conduisant à un traitement interchangeable malgré leurs contributions différentes à l'utilité.
2. Agrégation inappropriée : L'objectif réel (par exemple, la précision de validation) agrège les performances à travers ces rôles de manière non linéaire. Cependant, l'heuristique standard du top-$m$ repose sur une agrégation linéaire (somme des valeurs de Shapley), qui échoue à capturer les interactions synergiques où la contribution d'une donnée dépend des autres données déjà sélectionnées (par exemple, une donnée est plus précieuse si elle couvre un rôle sous-représenté).

Méthodologie : Cadre NASH

Les auteurs proposent NASH (Agrégation non linéaire de composantes informatives de Shapley), un cadre qui décompose la fonction d'utilité complexe en composantes plus simples où les valeurs de Shapley sont efficaces, puis les agrège de manière non linéaire.

1. Information de Shapley et décomposition

L'article formalise l'information de Shapley comme une propriété où la somme des valeurs de Shapley pour un sous-ensemble est indicative de son utilité réelle. Les auteurs prouvent que les fonctions d'utilité arbitraires ne sont généralement pas informatives de Shapley. Cependant, ils démontrent que des fonctions d'utilité plus simples, spécifiquement la prédiction correcte sur une seule donnée de validation ($u_v$), sont prouvées comme informatives de Shapley sous l'hypothèse du « Joueur cohérent » (où une donnée est constamment bonne ou mauvaise pour un point de validation spécifique).

Au lieu de calculer les valeurs de Shapley pour la précision de validation agrégée $u_V$, NASH décompose $u_V$ en composantes individuelles $u_v$ pour chaque donnée de validation $v \in V$. Les valeurs de Shapley $\phi_i(u_v)$ sont calculées pour ces composantes plus simples. Notamment, le calcul de ces vecteurs n'engendre aucun coût supplémentaire d'exécution par rapport au calcul de la valeur de Shapley pour l'agrégat $u_V$, car $u_V$ est simplement la moyenne des $u_v$.

2. Agrégation non linéaire

Pour reconstruire l'objectif complexe à partir de ces composantes informatives, NASH évite la sommation linéaire (qui retrouve l'heuristique de Shapley top-$m$ défectueuse). Au lieu de cela, il optimise un objectif d'agrégation non linéaire :
$$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$$
où $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$ est la somme des valeurs de Shapley pour la composante $v$, et $F_T$ est une fonction de distribution cumulative (CDF) inspirée des courbes d'apprentissage (par exemple, une loi exponentielle). Cette fonction non linéaire garantit que le processus de sélection privilégie les données qui aident à « franchir le seuil » pour les points de validation mal prédits (rôles non couverts) plutôt que d'accumuler des scores élevés sur des points déjà bien prédits.

3. Optimisation

L'objectif NASH est optimisé à l'aide d'un algorithme glouton. Les auteurs montrent que lorsque les valeurs de Shapley sont non négatives, l'objectif est sous-modulaire monotone, garantissant une approximation de $(1 - 1/e)$. Même avec des valeurs négatives (issues de données bruitées), l'algorithme glouton fonctionne bien empiriquement car les données nuisibles (qui causent la non-sous-modularité) sont naturellement dépriorisées. L'algorithme introduit un coût d'exécution supplémentaire minimal, car le travail lourd (approximation de Shapley) est partagé avec les méthodes existantes.

Contributions clés

1. Analyse théorique : L'article formalise la propriété d'information de Shapley, expliquant pourquoi les fonctions d'utilité complexes du ML (comme la précision de validation) échouent à la satisfaire, conduisant aux performances incohérentes de la valeur de Shapley des données.
2. Composantes prouvées informatives : Les auteurs identifient et prouvent que la prédiction correcte sur des points de données de validation individuels sert de composantes informatives de Shapley sous des hypothèses raisonnables.
3. Cadre NASH : Un nouveau cadre de sélection de données qui décompose les objectifs complexes en composantes informatives de Shapley et les agrège de manière non linéaire pour sélectionner des sous-ensembles de haute qualité.
4. Validation empirique : Des expériences extensives sur des ensembles de données standards (régression logistique, KNN) et un ajustement fin de modèles de langage à grande échelle (BERT, Llama-2) démontrent que NASH surpasse systématiquement la valeur de Shapley des données standard, d'autres semi-valeurs et la sélection aléatoire.

Résultats

• Sélection de données générale : Dans des configurations sans bruit injecté (qualité homogène), la valeur de Shapley des données standard ne fait souvent pas mieux que le hasard. NASH améliore considérablement les performances dans ces scénarios, surpassant systématiquement les références à travers divers ratios de sélection.
• Ensembles de données à qualité hétérogène : Dans des configurations avec bruit d'étiquetage, la valeur de Shapley des données standard s'améliore (car elle peut distinguer les mauvaises données), mais NASH la surpasse toujours systématiquement. Cela suggère que les avantages de NASH (gestion des interactions de rôles) sont distincts et complémentaires à la capacité de la valeur de Shapley des données à filtrer le bruit.
• Compatibilité : NASH est compatible avec diverses semi-valeurs (par exemple, Beta Shapley, Data Banzhaf) et des méthodes d'approximation efficaces (par exemple, échantillonnage MC, FreeShap), améliorant systématiquement leurs performances de sélection.
• Robustesse : La méthode est robuste au choix de l'hyperparamètre $\lambda$ dans la fonction d'agrégation et fonctionne efficacement avec différentes fonctions d'utilité (par exemple, perte de validation, MSE).

Importance

L'article affirme que NASH élimine largement la restriction selon laquelle la valeur de Shapley des données/les semi-valeurs ne sont efficaces que sur des ensembles de données limités ou des configurations spécifiques (par exemple, celles avec du bruit injecté). En fournissant un cadre qui rend la sélection basée sur Shapley fiable de manière constante et robuste à travers divers ensembles de données et échelles de modèles, NASH permet une adoption plus large des méthodes de valorisation de données fondées sur des principes. Cette avancée soutient la recherche future visant à améliorer l'efficacité de l'approximation et la sélection de données pour les modèles de base, garantissant que les avantages théoriques des valeurs de Shapley (interaction non myope et équité) se concrétisent en pratique.