🤖 machine learning

Shapley Value Approximation Based on k-Additive Games

Ce papier présente SVA $k_{\text{ADD}}$ , une nouvelle méthode d'approximation qui estime les valeurs de Shapley en ajustant un jeu de substitution $k$ -additif pour surmonter la complexité computationnelle exponentielle inhérente aux calculs exacts pour le partage équitable et l'interprétabilité de l'apprentissage automatique.

Auteurs originaux : Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Publié 2026-05-13

📖 6 min de lecture🧠 Analyse approfondie

CC0 1.0

Auteurs originaux : Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Article original placé dans le domaine public sous CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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

La vue d'ensemble : Partager la tarte équitablement

Imaginez que vous et un groupe d'amies gérez un stand de limonade. À la fin de la journée, vous réalisez un bénéfice. La grande question est : Qui mérite combien d'argent ?

La personne qui a pressé les citrons a-t-elle fait le plus de travail ?
La personne qui se tenait près de l'enseigne a-t-elle attiré le plus de clients ?
La personne qui a apporté le sucre a-t-elle rendu la boisson plus savoureuse ?

Dans le monde de l'apprentissage automatique (IA), c'est le même problème. Un modèle d'IA fait une prédiction (comme diagnostiquer une maladie ou deviner si un e-mail est un spam). Nous voulons savoir : Quelle pièce spécifique de données (caractéristique) était responsable de cette prédiction ?

La « Valeur de Shapley » est une formule mathématique inventée par un théoricien des jeux nommé Lloyd Shapley. C'est la référence absolue en matière d'équité. Elle calcule exactement combien chaque « joueur » (caractéristique) a contribué au résultat final en examinant chaque combinaison possible de joueurs.

Le problème : Les mathématiques sont trop difficiles

Voici le hic : pour calculer parfaitement la Valeur de Shapley, vous devez vérifier chaque combinaison d'équipe possible.

Si vous avez 10 amis, il y a 1 024 combinaisons.
Si vous avez 20 amis, il y a plus de 1 million de combinaisons.
Si vous avez 50 amis, le nombre est si énorme qu'il faudrait plus de temps que l'âge de l'univers pour le calculer.

Parce que les modèles d'IA modernes ont souvent des centaines ou des milliers de caractéristiques, calculer la Valeur de Shapley exacte est impossible. C'est comme essayer de compter chaque grain de sable sur une plage pour partager équitablement la valeur de la plage. Nous avons besoin d'un raccourci, mais ce raccourci doit être assez précis pour être fiable.

La solution : SVAkADD (La méthode du « Substitut Intelligent »)

Les auteurs de ce papier proposent une nouvelle méthode appelée SVAkADD. Au lieu d'essayer de compter chaque grain de sable, ils construisent un modèle simplifié (un « substitut ») qui imite le vrai jeu mais qui est beaucoup plus facile à résoudre.

Voici comment ils procèdent, en utilisant une analogie créative :

1. L'hypothèse de la « Collaboration » (k-additivité)

Les auteurs supposent que, bien que la contribution de chacun compte, la collaboration complexe s'arrête généralement à une certaine taille.

1-additif : Seule l'effort individuel compte. (Vous êtes bon dans votre travail, peu importe avec qui vous travaillez).
2-additif : Les paires comptent. (Vous et votre meilleur ami travaillez très bien ensemble, mais un groupe de trois pourrait devenir chaotique).
3-additif : Les petits groupes comptent. (Un trio fonctionne bien, mais un comité de dix personnes est trop désordonné pour avoir un effet « magique » unique).

Le papier appelle cela la k-additivité. Ils supposent que les interactions entre 4, 5 ou 10 personnes à la fois sont si rares ou négligeables que nous pouvons les ignorer. Cela transforme un problème mathématiquement impossible en un problème gérable.

2. Le « Test de goût » (Échantillonnage)

Au lieu de tester chaque recette de limonade possible (coalition), les chercheurs prennent un échantillon aléatoire de recettes.

Ils mélangent quelques combinaisons spécifiques d'ingrédients.
Ils goûtent le résultat (calculent la valeur).
Ils utilisent ces quelques tests de goût pour « ajuster » leur modèle simplifié.

3. La « Formule Magique » (L'optimisation)

Une fois qu'ils ont les tests de goût, ils résolvent une énigme mathématique spécifique (un problème d'optimisation) pour trouver les paramètres de leur modèle simplifié.

La partie cool : Les auteurs ont prouvé mathématiquement que s'ils choisissent les bons « poids » pour leurs tests de goût, la réponse qu'ils obtiennent de ce modèle simplifié est exactement la même que la Valeur de Shapley parfaite l'aurait été, s'ils avaient testé chaque combinaison.
Même s'ils ignorent les interactions complexes de 10 personnes, les mathématiques garantissent que les chiffres finaux de « part équitable » sortent corrects pour les scénarios qu'ils ont testés.

Pourquoi c'est mieux que d'autres raccourcis

D'autres méthodes tentent de deviner la réponse en faisant des suppositions aléatoires et en faisant des moyennes (comme lancer des dés de nombreuses fois).

La méthode du papier : C'est comme construire un plan basé sur quelques mesures. Une fois le plan construit, vous pouvez lire la réponse instantanément.
Le résultat : Le papier montre que leur méthode converge (devient précise) beaucoup plus rapidement que les méthodes de devinette aléatoire. Vous avez besoin de moins de « tests de goût » (échantillons) pour obtenir une réponse fiable.

Ce qu'ils ont trouvé (Les résultats)

Les chercheurs ont testé cela sur des ensembles de données réels (comme prédire la survie du Titanic, la qualité du vin ou la détection du cancer du sein).

Vitesse vs Précision : Ils ont découvert que supposer que les interactions se produisent dans des groupes de 3 (3-additif) était généralement le « juste milieu ». C'était assez complexe pour être précis, mais assez simple pour être rapide.
Battre la concurrence : Dans de nombreux tests, leur méthode (SVAkADD) était plus précise que les meilleures méthodes actuelles (comme KernelSHAP) lorsqu'on leur donnait la même quantité de temps de calcul ou d'échantillons de données.
Pas de règles spéciales nécessaires : Cette méthode fonctionne sur n'importe quel type de jeu ou modèle d'IA. Peu importe que les données concernent des dossiers médicaux, des cours boursiers ou des statistiques sportives.

Résumé en une phrase

Le papier introduit une nouvelle façon de partager équitablement les crédits entre les caractéristiques d'une IA en construisant un « modèle de collaboration » simplifié qui ignore les interactions de groupe trop complexes, nous permettant de calculer rapidement et précisément des parts équitables sans avoir à vérifier chaque possibilité unique.

Résumé technique : Approximation de la valeur de Shapley basée sur les jeux k-additifs

Énoncé du problème

La valeur de Shapley est la solution standard pour les problèmes de répartition équitable, largement adoptée dans l'IA explicable (XAI) pour quantifier la contribution individuelle des caractéristiques ou des points de données aux performances d'un modèle. Cependant, son calcul exact nécessite d'évaluer les $2^n$ coalitions possibles de $n$ joueurs, ce qui entraîne une complexité computationnelle exponentielle. Cela rend le calcul exact irréalisable pour les modèles comportant un nombre modéré de caractéristiques ou lors de l'évaluation de modèles complexes et gourmands en ressources. Par conséquent, des méthodes d'approximation sont nécessaires, mais les approches existantes peinent souvent à équilibrer l'efficacité computationnelle avec la précision des scores d'importance résultants.

Méthodologie : SVAkADD

Les auteurs proposent SVAkADD (Approximation de la valeur de Shapley sous k-additivité), une méthode novatrice qui approxime les valeurs de Shapley en ajustant un jeu de substitution k-additif structuré à un sous-ensemble échantillonné de valeurs de coalition.

Concept de base : la k-additivité

Au lieu d'estimer directement la valeur de Shapley par échantillonnage de Monte Carlo des contributions marginales, SVAkADD suppose que le jeu sous-jacent peut être approximé par un jeu k-additif. Dans un tel jeu, les indices d'interaction (interactions de Shapley) pour les coalitions de taille supérieure à $k$ sont supposés nuls.

Représentation : La fonction de valeur $\nu_k$ du jeu de substitution est exprimée comme une transformation linéaire des indices d'interaction de Shapley $I(B)$ pour toutes les coalitions $B$ où $|B| \leq k$ .
Réduction des paramètres : Cette hypothèse réduit considérablement le nombre de paramètres nécessaires pour définir le jeu, passant de $2^n$ à un nombre polynomial (par exemple, $O(n^k)$ ), rendant ainsi l'optimisation traitable.

Cadre d'optimisation

La méthode formule l'approximation comme un problème de moindres carrés pondérés contraint :

Objectif : Minimiser l'erreur quadratique pondérée entre les valeurs de coalition observées $\nu(A)$ du jeu original et les valeurs prédites par le substitut k-additif $\nu_k(A)$ .
Contraintes : L'optimisation impose l'axiome d'efficacité, garantissant que la somme des valeurs de Shapley du substitut est égale à la différence entre la valeur de la grande coalition et celle de l'ensemble vide ( $\nu(N) - \nu(\emptyset)$ ).
Pondération : Les auteurs dérivent analytiquement des poids spécifiques $w^*_A = \binom{n-2}{|A|-1}^{-1}$ pour le problème des moindres carrés. Ils prouvent que si toutes les coalitions étaient observées, la résolution de cette optimisation spécifique produit les valeurs de Shapley exactes, indépendamment du fait que le jeu original soit véritablement k-additif.

Algorithme

L'algorithme SVAkADD procède comme suit :

Échantillonnage : Il évalue de manière déterministe l'ensemble vide $\emptyset$ et la grande coalition $N$ . Il échantillonne ensuite $T-2$ coalitions supplémentaires à partir de l'ensemble des parties (en excluant $\emptyset$ et $N$ ) selon une distribution de probabilité proportionnelle aux poids dérivés $w^*_A$ .
Ajustement : Il résout le problème de moindres carrés pondérés contraint en utilisant les données échantillonnées pour estimer les indices d'interaction $I(B)$ pour $|B| \leq k$ .
Extraction : Les valeurs de Shapley pour le jeu de substitution sont obtenues immédiatement comme les indices d'interaction des singletons ( $I(\{i\})$ ), qui servent d'estimations pour le jeu original.

Contributions clés

Nouvelle méthode d'approximation : Introduction de SVAkADD, qui ajuste un jeu de substitution k-additif à des données échantillonnées, offrant une alternative structurée à l'échantillonnage direct des contributions marginales.
Solidité théorique : Preuve analytique que pour $k=1, 2, 3$ , l'optimisation proposée des moindres carrés pondérés produit les valeurs de Shapley exactes lorsque l'ensemble complet des coalitions est observé. Cela établit que la k-additivité est un outil d'approximation plutôt qu'une hypothèse restrictive sur la structure du jeu.
Agnosticisme du modèle et du domaine : La méthode ne nécessite pas de propriétés structurelles spécifiques de la fonction de valeur, ce qui la rend applicable à tout jeu coopératif, y compris les explications de caractéristiques locales et globales en apprentissage automatique.
Évaluation empirique : Comparaison complète par rapport à des références de l'état de l'art (KernelSHAP, SVARM stratifié, échantillonnage stratifié) sur divers ensembles de données et types d'explications (globales, locales, non supervisées).

Résultats expérimentaux

Les auteurs ont évalué SVAkADD sur des ensembles de données allant de 9 à 14 caractéristiques, couvrant des tâches globales, locales et non supervisées.

Convergence : La méthode démontre des performances compétitives. Bien qu'elle puisse présenter une erreur plus élevée avec des budgets d'échantillons très faibles par rapport à certaines références, elle converge plus rapidement vers les valeurs de Shapley exactes à mesure que le budget augmente, en particulier pour les tâches d'attribution locale sur les ensembles de données Adult et ImageNet.
Choix de $k$ : Les expériences mettent en évidence un compromis entre flexibilité et vitesse de convergence.
- Un $k$ faible (1 ou 2) converge souvent lentement en raison d'une flexibilité insuffisante pour modéliser des interactions complexes entre caractéristiques.
- Un $k$ plus élevé (3 ou 4) converge généralement beaucoup plus rapidement et surpasse les modèles d'ordre inférieur après quelques échantillons.
- Les auteurs suggèrent $k=3$ comme valeur par défaut préférable, offrant un bon équilibre entre réduction de l'erreur et nombre de paramètres requis.
Comparaison : SVAkADD rivalise constamment avec ou surpasse KernelSHAP et SVARM stratifié, en particulier dans les scénarios nécessitant une haute précision avec des budgets d'échantillons modérés.

Importance et affirmations

L'article affirme que SVAkADD fournit une approche théoriquement fondée et pratiquement efficace pour l'approximation de la valeur de Shapley. En tirant parti de la structure des jeux k-additifs, la méthode transforme le problème d'estimation en une optimisation de temps polynomial qui garantit une récupération exacte sous des conditions de pondération spécifiques.

Les auteurs soulignent que leur approche est agnostique du modèle et indépendante du domaine, capable de gérer toute formulation de jeu coopératif. Ils concluent que, bien qu'aucune méthode d'approximation unique ne domine dans tous les scénarios (selon l'ensemble de données, la tâche et le budget), SVAkADD offre une alternative robuste qui exploite les propriétés théoriques des interactions de Shapley pour atteindre une haute précision. L'article note également que la méthode fournit naturellement des estimations pour les effets d'interaction (redondance ou complémentarité) lorsque $k \geq 2$ , offrant une interprétabilité supplémentaire au-delà de l'importance individuelle des caractéristiques.