Generalized Priority-Aware Shapley Value

Énoncé du problème

Les valeurs de Shapley et leurs extensions sensibles aux priorités sont des outils standards pour attribuer de la valeur aux contributeurs en apprentissage automatique (par exemple, points de données, caractéristiques ou composants de modèle). Cependant, les méthodes existantes sensibles aux priorités, telles que la Valeur de Shapley Sensible aux Priorités (PASV), reposent sur des hypothèses restrictives qui échouent souvent dans les applications modernes d'IA/ML :

1. Contraintes binaires et acycliques : La PASV exige que les relations de priorité binaires soient encodées sous la forme d'un graphe orienté acyclique (DAG). Cela interdit les cycles (par exemple, $A \succ B \succ C \succ A$) et traite la priorité comme une contrainte binaire rigide. Les données réelles, telles que les préférences humaines agrégées (cycles de Condorcet) ou les comparaisons multicritères, présentent fréquemment des structures cycliques.
2. Perte de l'ampleur : La PASV écarte la force des preuves de priorité. Dans des scénarios tels que les comptes de victoires en tournoi, les log-odds de Bradley-Terry ou les classements ELO, l'ampleur de la préférence importe, mais les méthodes basées sur les DAG ne capturent que l'existence d'une antériorité.
3. Attaques par copieur : Les valeurs de Shapley standard sont vulnérables aux « attaques par copieur » où un contributeur qui copie un autre reçoit un crédit égal. Bien que la PASV remédie à cela via des priorités rigides, elle ne peut pas gérer la nature nuancée, pondérée ou cyclique de l'antériorité réelle.

Méthodologie : Valeur de Shapley Sensible aux Priorités Généralisée (GPASV)

Les auteurs proposent la GPASV, une Valeur d'Ordre Aléatoire (ROV) définie sur des graphes orientés pondérés arbitraires, qui gère simultanément les structures cycliques, les priorités binaires pondérées et les priorités « douces » individuelles.

1. Définition de base
Contrairement à la PASV, qui restreint les permutations à celles compatibles avec un DAG, la GPASV définit une distribution de probabilité $p(\lambda, \omega)$ sur l'ensemble entier des permutations $\Pi$.

• Priorité binaire ($\omega$) : Représentée par un graphe orienté pondéré où $\omega_{ij} \ge 0$ encode la force avec laquelle le joueur $i$ devrait précéder $j$. Les cycles sont autorisés.
• Priorité douce ($\lambda$) : Des poids individuels représentant la confiance, le coût ou le risque de conformité.
• Pénalité de violation : Pour une permutation $\pi$, le coût total de violation $V_\omega(\pi)$ est la somme des poids pour toutes les paires où l'antériorité est violée.
• Formulation de la distribution : La distribution combine une pénalité de style Gibbs pour les violations avec un mécanisme de priorité douce étape par étape :
  $$p(\lambda, \omega)(\pi) \propto \prod_{t=1}^n \left[ \frac{\lambda_{\pi_t} \exp\{-\beta \cdot V_\omega(\pi_t; S_t)\}}{\sum_{k \in S_t} \lambda_k \exp\{-\beta \cdot V_\omega(k; S_t)\}} \cdot \sum_{k \in S_t} \exp\{-\beta \cdot V_\omega(k; S_t)\} \right]$$
  Ici, $\beta$ est un paramètre de température contrôlant la rigueur de la priorité binaire. Lorsque $\beta \to \infty$, la méthode retrouve la PASV sur les DAG ; lorsque $\beta = 0$, elle se réduit à une distribution de Plackett-Luce.

2. Caractérisation axiomatique
L'article établit la GPASV à travers un ensemble d'axiomes qui généralisent ceux de la PASV :

• GSCF (Factorisation généralisée choix d'état) : Garantit que la distribution suit une forme canonique étape par étape compatible avec le schéma d'échantillonnage.
• GWP (Proportionnalité généralisée des poids) : Les log-odds de choisir le joueur $i$ plutôt que $j$ à n'importe quelle étape dépendent de leurs poids doux $\lambda$ et de leurs coûts de violation relatifs.
• PVF (Factorisation de la violation binaire) : Lorsque les poids doux sont uniformes, la distribution se réduit à la forme de Gibbs pénalisant les violations totales.
  Les auteurs démontrent que la GPASV est la ROV unique satisfaisant ces axiomes.

3. Cadre de calcul
Le calcul de la GPASV est difficile en raison de la distribution non uniforme sur les permutations. Les auteurs développent :

• Échantillonnage : Une chaîne de Metropolis-Hastings (MH) par échange adjacent avec un ratio d'acceptation local qui annule la plupart des termes globaux, la rendant efficace.
• Initialisation : Une initialisation gloutonne étape par étape (Algorithme 2) qui échantillonne les joueurs à rebours de la position $n$ pour atténuer le problème de « démarrage à froid » dans les graphes cycliques où aucune extension linéaire valide n'existe.
• Accélération :
  • Mise en cache des utilités : Réutilisation des évaluations $U(S)$ pour les sous-ensembles répétés.
  • SNIS (Échantillonnage par importance auto-normalisé) : Réutilisation des échantillons de permutations à travers différents réglages de température ($\beta$) ou échelles de priorité douce ($\lambda$) lors de la « balayage des priorités ».
  • Estimation assistée par substitut : Utilisation de substituts basés sur la régression (linéaire ou quadratique) pour réduire la variance, bien que les auteurs notent que cela entraîne des coûts mémoire plus élevés pour la GPASV par rapport à la PASV en raison de l'impossibilité de mettre à zéro les termes d'interaction pour les arêtes de DAG.

Résultats clés et validation empirique

1. Simulations

• Temps de mélange : L'initialisation gloutonne accélère considérablement le mélange de la chaîne MH par rapport à une initialisation aléatoire, en particulier dans les graphes denses ou cycliques.
• Précision : L'estimation directe par Monte Carlo converge comme prévu. Les méthodes assistées par substitut améliorent la précision mais introduisent une surcharge substantielle de temps d'exécution et de mémoire, en particulier pour les substituts quadratiques, qui ne peuvent pas exploiter la parcimonie des DAG.
• Balayage des priorités : Un outil de diagnostic où les priorités douces ($\lambda$) sont variées. Les auteurs constatent que sous la GPASV, l'impact des priorités douces est substantiellement plus grand que sous la PASV. Parce que la GPASV « adoucit » les contraintes rigides, les priorités douces individuelles peuvent remodeler plus efficacement la valorisation, alors que les contraintes de DAG rigides de la PASV limitent leur influence.

2. Application : Valorisation d'ensembles de LLM
La méthode est appliquée pour valoriser 20 grands modèles de langage (LLM) en utilisant :

• Utilité : Performance sur MT-Bench (agrégée et jugée par un LLM).
• Priorité binaire : Un graphe cyclique et pondéré dérivé des préférences humaines de Chatbot Arena.
• Priorité douce : Une préférence pour les modèles open-source par rapport aux API propriétaires payantes.

Constatations :

• Valorisation non unique : La valorisation n'est pas un seul nombre « correct ». Différents équilibres entre les préférences binaires ($\beta$) et les priorités douces ($\alpha$) produisent des classements substantiellement différents.
• Domination de la priorité douce : Dans les balayages conjoints, la priorité douce au niveau des nœuds (préférence open-source) tend à dominer la priorité du graphe au niveau des arêtes. Par exemple, augmenter la priorité douce pour les modèles open-source peut les élever aux premiers rangs même lorsque le graphe de préférence binaire favorise les modèles payants.
• Hubs du graphe : Lorsqu'on privilégie uniquement les préférences binaires ($\beta$), la valorisation se concentre sur des « hubs » spécifiques du graphe de préférence (par exemple, GPT-4), plutôt que de répartir la valeur sur une catégorie de modèles.

Signification et revendications

L'article revendique que la GPASV est une extension fondée sur des principes et expressive des variantes de Shapley existantes. Sa signification principale réside dans :

1. Gestion de la complexité réelle : C'est la première méthode à gérer simultanément les priorités binaires pondérées cycliques et les priorités douces individuelles, couvrant la Shapley classique, la PSV, la WSV et la PASV comme cas particuliers.
2. Transparence des compromis : Les auteurs soutiennent que la valorisation sensible aux priorités n'est « pas une opération à un bouton ». La GPASV expose le compromis entre différentes sources d'informations de priorité (par exemple, graphes de préférences humaines vs contraintes de déploiement) comme une entrée explicite et balayable.
3. Nécessité diagnostique : Le diagnostic de « balayage des priorités » révèle que les priorités douces ont un impact beaucoup plus grand sous la GPASV que ce qui était précédemment pensé sous la PASV, suggérant que les métadonnées concernant les priorités douces (confiance, coût, risque) sont beaucoup plus déterminantes pour la valorisation qu'on ne le reconnaissait auparavant.

L'article conclut que bien que la GPASV introduise des défis computationnels, sa capacité à modéliser des structures cycliques et pondérées la rend essentielle pour des applications comme l'évaluation des LLM où les hypothèses standard de DAG sont violées.