🤖 machine learning

Priority-Aware Shapley Value

Cet article introduit le Priority-Aware Shapley Value (PASV), un nouveau cadre qui étend les valeurs de Shapley traditionnelles en incorporant des contraintes de précédence strictes et des poids de priorité souples afin de mieux gérer les contributeurs dépendants et les facteurs de confiance, soutenu par un algorithme d'échantillonnage efficace et validé par des expériences sur des tâches de valorisation de données et d'attribution de caractéristiques.

Auteurs originaux : Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

Publié 2026-06-16

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

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 organisiez un immense dîner de type « potluck » où chaque invité apporte un plat, et que l'objectif soit de déterminer exactement la contribution de chaque personne à la délicieuseté du festin final. Dans le monde de l'apprentissage automatique (machine learning), ce « potluck » est un modèle entraîné sur des données, et les « plats » sont des points de données individuels ou des caractéristiques (features).

Pendant des décennies, les scientifiques ont utilisé un outil mathématique appelé Valeur de Shapley pour répartir les mérites de manière équitable. La règle traditionnelle est simple : imaginez tous les ordres possibles dans lesquels les invités pourraient arriver à la fête. Si vous arrivez en premier, vous recevez le crédit pour toute la table. Si vous arrivez en dernier, vous ne recevez le crédit que pour ce que vous avez ajouté à une table déjà remplie. La Valeur de Shapley fait la moyenne de votre contribution à travers tous les ordres d'arrivée possibles.

Le Problème : L'hypothèse de l'« Interchangeabilité »
L'ancienne méthode suppose que tous les invités sont interchangeables. Elle traite le potluck comme si cela n'avait pas d'importance de savoir qui apporte la salade en premier ou qui apporte le gâteau en dernier. Mais dans la vraie vie, ce n'est pas vrai.

Priorité Forte (La « Règle de la Recette ») : Parfois, vous devez apporter la pâte avant de pouvoir apporter les garnitures de la pizza. Si vous essayez d'ajouter les garnitures avant la pâte, la pizza est ruinée. En termes de données, certaines données sont « copiées » à partir d'autres données, ou certaines caractéristiques (comme l'âge) doivent logiquement précéder d'autres (comme la profession). L'ancienne méthode ignore ces règles, permettant à des scénarios impossibles (comme des garnitures avant la pâte) de fausser les résultats.
Priorité Douce (La « Règle du VIP ») : Parfois, nous faisons plus confiance à certains invités qu'à d'autres. Peut-être qu'un invité est un chef célèbre (haute confiance), tandis qu'un autre est connu pour apporter des toasts brûlés (faible confiance/risque). L'ancienne méthode les traite de la même manière, simplement parce qu'ils sont arrivés à des moments différents. Nous avons besoin d'un moyen de dire : « Nous faisons davantage confiance à la contribution du chef », sans pour autant modifier la recette.

La Solution : La Valeur de Shapley Sensible à la Priorité (PASV)
Les auteurs proposent une nouvelle méthode appelée PASV. Voyez cela comme un organisateur de potluck plus intelligent qui comprend deux choses :

Les Règles Strictes (Le DAG) : Il respecte la « recette ». Il sait que la pâte doit venir avant les garnitures. Il ne considère que les ordres d'arrivée qui font sens (par exemple, pas de garnitures avant la pâte).
Les Poids Doux (Les VIP) : Il sait que certains invités sont plus « dignes de confiance » ou « risqués » que d'autres. Il ajuste les calculs pour que les invités de haute confiance soient plus susceptibles d'être évalués dans des contextes où leur véritable valeur brille, tandis que les invités risqués sont évalués plus prudemment pour voir s'ils apportent réellement une valeur ajoutée ou s'ils ne sont que du bruit.

Comment cela fonctionne (L'analogie créative)
Imaginez que vous essayiez de juger une équipe de détectives résolvant un mystère.

L'Ancienne Méthode : Vous demandez à chaque ordre possible de détectives de résoudre l'affaire. Vous faites la moyenne de leur succès. Mais c'est injuste si le Détective A doit trouver l'indice avant que le Détective B puisse résoudre l'énigme. L'ancienne méthode compte des scénarios où B essaie de résoudre l'énigme en premier, ce qui est impossible.
La Méthode PASV :
- Priorité Forte : Vous ne laissez les détectives résoudre l'affaire que dans des ordres qui respectent les indices (A avant B).
- Priorité Douce : Vous avez un « compteur de confiance » pour chaque détective. Si le Détective C est un menteur connu (risque élevé), PASV ne se contente pas de l'ignorer ; il simule des scénarios où il arrive plus tard dans l'enquête. Cela permet de tester : « Si nous avons déjà des preuves solides, est-ce que l'indice de ce menteur aide réellement, ou est-ce qu'il sème la confusion ? » Si c'est un génie (haute confiance), PASV le teste dans des contextes riches pour voir tout son potentiel.

L'Outil de « Balayage de Priorité » (Priority Sweeping)
L'une des fonctionnalités les plus intéressantes de PASV est un outil de diagnostic que les auteurs appellent le « Priority Sweeping ».
Imaginez que vous soyez le gestionnaire du potluck. Vous n'êtes pas sûr de la confiance à accorder à l'invité qui a apporté le « casserole mystère ».

Avec PASV, vous pouvez lancer une simulation : « Que se passe-t-il pour le score de crédit si je traite cet invité comme un "Super VIP" (confiance maximale) ? » Ensuite, « Et si je le traite comme un "Risque Élevé" (confiance minimale) ? »
En faisant glisser un curseur de la « Confiance Totale » vers la « Méfiance Totale », vous pouvez voir si sa note de contribution reste stable ou s'effondre. Si elle s'effondre, vous savez que sa valeur est instable et dépend fortement de la confiance que vous lui accordez. Cela vous aide à prendre des décisions plus sûres sur les personnes à inviter la prochaine fois.

Ce que l'article a réellement découvert
Les auteurs ont testé cela sur deux scénarios principaux :

Évaluation des Données (Le Potluck) : Ils ont simulé un marché de données où certaines données étaient originales, certaines étaient des copies, et certaines étaient « empoisonnées » (mauvaises données).
- Les anciennes méthodes attribuaient du crédit aux « copieurs » car elles ne réalisaient pas que les données n'étaient qu'une copie.
- PASV a correctement pénalisé les copieurs et les « empoisonneurs », accordant plus de crédit aux sources originales, surtout lorsque les paramètres de « confiance » étaient ajustés.
Attribution de Caractéristiques (L'équipe de détectives) : Ils ont analysé un ensemble de données prédisant le revenu.
- Ils ont montré que la façon dont on ordonne les caractéristiques (par exemple, est-ce que l'âge vient avant l'éducation ?) modifie les résultats.
- PASV leur a permis de voir quelles caractéristiques étaient robustes (leur valeur ne changeait pas beaucoup quel que soit le niveau de confiance) et lesquelles étaient instables (comme le « pays d'origine », qui oscillait radicalement selon les réglages).

En résumé
PASV est une nouvelle façon de répartir équitablement le mérite dans l'apprentissage automatique. Il corrige l'aveuglement de l'ancienne méthode face aux règles (on ne peut pas avoir de garnitures avant la pâte) et à la confiance (certaines données sont plus risquées que d'autres). Il nous donne un outil non seulement pour obtenir une réponse unique, mais aussi pour tester la résistance de nos décisions en demandant : « À quel point ma confiance envers ce point de donnée change-t-elle réellement le résultat ? »

Résumé Technique : Valeur de Shapley Sensible aux Priorités (PASV)

Énoncé du Problème

Les valeurs de Shapley sont l'outil standard pour la valorisation des données et l'attribution de caractéristiques (features) agnostiques au modèle, reposant sur l'axiome selon lequel les contributeurs (joueurs) sont interchangeables. Cette hypothèse nécessite de moyenner les contributions marginales sur toutes les permutations possibles de joueurs. Cependant, dans les applications modernes d'apprentissage automatique, cette échangeabilité est souvent invalide pour deux raisons principales :

Contraintes de Précedence : Les contributeurs peuvent présenter des relations de précédence strictes. Par exemple, les données d'entraînement peuvent être augmentées ou copiées à partir de sources en amont (rendant les contributions en aval dérivées), ou la connaissance métier peut dicter que certaines caractéristiques (ex: ancêtres causaux) doivent être considérées avant d'autres. Les méthodes existantes comme la Valeur de Shapley de Précedence (PSV) gèrent ces contraintes mais traitent tous les prolongements linéaires valides de manière uniforme, ignorant les différences individuelles.
Poids de Priorité Souples : Les praticiens ont souvent des considérations contextuelles telles que la confiance, le risque ou les coûts de curation. Par exemple, un point de donnée peut être moins fiable ou comporter un risque juridique plus élevé. Les méthodes de Valeur de Shapley Pondérée (WSV) existantes intègrent de tels poids mais sont limitées à des hypothèses structurelles spécifiques (partitions ordonnées) et ne peuvent pas gérer les Graphes Orientés Acycliques (DAG) généraux.

Les approches actuelles traitent généralement la précédence stricte et les poids souples de manière isolée. Il existe un manque de cadre unifié capable d'incorporer simultanément des contraintes de précédence générales et des poids de priorité spécifiques aux joueurs tout en restant calculablement faisable.

Méthodologie : Valeur de Shapley Sensible aux Priorités (PASV)

Les auteurs proposent la Valeur de Shapley Sensible aux Priorités (PASV), une méthode d'attribution de type Shapley unifiée qui intègre à la fois des contraintes de précédence strictes et des poids de priorité souples au sein d'un cadre de permutation aléatoire unique.

1. Formulation Théorique

La PASV définit la valeur d'un joueur $i$ comme l'espérance de la contribution marginale sur une distribution $p$ supportée par l'ensemble des prolongements linéaires $\Pi_{\preceq}$ d'un poset (ou DAG) $([n], \preceq)$ . La distribution $p$ est construite pour satisfaire :

Priorité Stricte : Le support est restreint à $\Pi_{\preceq}$ , garantissant qu'aucune permutation ne viole les contraintes de précédence.
Priorité Souple : Parmi les candidats admissibles à chaque étape de la construction de la permutation, la probabilité de sélection est biaisée par les poids spécifiques aux joueurs $\lambda = (\lambda_1, \dots, \lambda_n)$ .

La probabilité d'une permutation $\pi = (\pi_1, \dots, \pi_n)$ est donnée par :
$p^{(\preceq, \lambda)}(\pi) \propto \prod_{t=1}^n \frac{\lambda_{\pi_t} |\max_{\preceq}(S_t)|}{\sum_{k \in \max_{\preceq}(S_t)} \lambda_k}$
où $S_t = \{\pi_1, \dots, \pi_t\}$ est l'ensemble des joueurs sélectionnés jusqu'à présent, et $\max_{\preceq}(S_t)$ désigne l'ensemble des éléments maximaux dans $S_t$ (les candidats admissibles pour la position suivante).

2. Caractérisation Axiomatique

L'article fournit une caractérisation axiomatique rigoureuse qui identifie de manière unique la PASV. La dérivation procède par :

Valeur d'Ordre Aléatoire de Précedence (PROV) : Une famille de valeurs satisfaisant l'Efficacité, la Linéarité, le Joueur Nul, la Monotonie et le Support Maximal (le crédit ne va qu'aux éléments maximaux dans les ensembles réalisables).
Factorisation par Choix d'État (SCF) : Restriction de la distribution à une forme factorisée où la probabilité d'une permutation est le produit d'un facteur "état" (biais global provenant du DAG) et d'un facteur "choix" (biais local provenant des poids).
Axiomes de Limite :
- Proportionnalité des Poids (WP) : Les probabilités de sélection parmi les candidats admissibles sont proportionnelles à leurs poids $\lambda$ .
- Uniformité des Poids Égaux (EWU) : Si tous les poids sont égaux, la distribution se réduit à la distribution uniforme sur $\Pi_{\preceq}$ (récupérant la PSV).
  La combinaison de PROV, SCF, WP et EWU produit de manière unique la PASV.

3. Régimes Limites

Les auteurs analysent le comportement de la PASV lorsque les poids deviennent extrêmes ( $\lambda_i \to \infty$ ou $\lambda_i \to 0$ ). Ils démontrent que les poids extrêmes peuvent induire un mécanisme de départage des ex æquo presque déterministe parmi les joueurs simultanément admissibles. Dans des cas spécifiques (ex: partitions ordonnées ou joueurs globalement maximaux), les poids extrêmes se traduisent efficacement par de nouvelles arêtes dans le DAG, affinant la structure de précédence.

4. Calculabilité à Grande Échelle

Puisque le nombre de prolongements linéaires croît de manière exponentielle, le calcul exact est intraitable pour de grands $n$ . Les auteurs développent un échantillonneur de Metropolis-Hastings (M-H) par échange adjacent efficace :

Initialisation : Un prolongement linéaire valide est trouvé via un tri topologique.
Transition : L'échantillonneur propose un échange d'éléments adjacents incomparables dans la permutation actuelle.
Acceptation : Le ratio d'acceptation de Metropolis-Hastings est calculé à l'aide d'informations locales (Lemme 4.1), permettant à l'échantillonneur de converger vers la distribution non uniforme $p^{(\preceq, \lambda)}$ sans énumérer toutes les permutations.
Estimation : La PASV est estimée via la moyenne de Monte Carlo des contributions marginales sur les permutations échantillonnées.

5. Outil de Diagnostic : Balayage de Priorité (Priority Sweeping)

Au-delà des estimations ponctuelles, la PASV permet une analyse de "balayage de priorité". En faisant varier le poids $\lambda_i$ d'un seul joueur (ou d'un groupe) tout en maintenant les autres fixes, les praticiens peuvent tracer l'évolution de la valorisation. Cela sert d'analyse de sensibilité pour identifier les contributeurs dont le crédit est instable ou fortement dépendant des hypothèses de confiance/risque.

Résultats Clés

L'article évalue la PASV sur deux ensembles de données :

Valorisation de Données (MNIST/CIFAR10) :
- Configuration : Un scénario de marché de données avec 8 fournisseurs, incluant des données originales, des données augmentées, des sorties de modèles génératifs (Boosters), des copies et des données empoisonnées. Un DAG complexe encode la lignée des données (ex: les copies dépendent des originaux).
- Résultats : La Valeur de Shapley (SV) standard sur-attribue le crédit aux données réutilisées. La PSV pénalise correctement les copies mais traite toutes les données synthétiques de la même manière. La PASV, en ajustant les poids, parvient à différencier les données synthétiques de haute qualité (Boosters) des données de faible qualité ou réutilisées (Copier/Poisoner). L'analyse de "balayage de priorité" révèle que la valeur des données copiées/empoisonnées est très sensible aux ajustements de poids, tandis que les données originales restent stables.
Attribution de Caractéristiques (Census Income) :
- Configuration : Prédiction de revenu >50k avec 12 caractéristiques. Les auteurs comparent un DAG de "partition ordonnée" grossier (démographie $\prec$ socio-économique) contre un DAG détaillé dérivé de la connaissance métier (ex: éducation $\prec$ profession).
- Résultats : Le choix du DAG modifie considérablement les valeurs d'attribution. Le balayage de priorité de la PASV identifie que certaines caractéristiques (ex: pays de naissance, relation) ont des attributions instables selon leur poids de priorité, tandis que d'autres (ex: état civil) sont robustes. Cela souligne l'importance de modéliser correctement la précédence et fournit un outil pour diagnostiquer la sensibilité de l'attribution.

Signification et Revendications

L'article affirme que la PASV offre un cadre unifié, expressif et pratiquement faisable pour l'attribution dans des contextes de dépendances et de niveaux de confiance variables. Ses principales contributions sont :

Unification : C'est la première méthode traitant simultanément des contraintes de précédence générales (DAG) et des poids de priorité souples, récupérant la PSV et la WSV comme cas particuliers.
Fondement Théorique : Elle fournit une base axiomatique solide, prouvant que la PASV est la règle unique satisfaisant les propriétés naturelles pour une valorisation sensible à la précédence et aux poids.
Scalabilité : L'échantillonneur MCMC proposé permet l'application à de grands ensembles de joueurs où l'énumération exacte est impossible.
Utilité Pratique : Le diagnostic de "balayage de priorité" fournit un mécanisme de sensibilité novateur, permettant aux praticiens de quantifier l'impact des hypothèses de confiance/risque sur les résultats de valorisation.

Les auteurs soulignent que la PASV ne prétend pas être une solution "boîte noire", mais plutôt un outil qui rend les hypothèses structurelles (DAG) et les hypothèses de priorité (poids) explicites et ajustables, soutenant ainsi une prise de décision plus robuste et interprétable dans l'IA centrée sur les données.