La valeur de Shapley est un concept de solution en théorie des jeux coopératifs qui fournit une méthode pour répartir équitablement les gains ou les coûts totaux entre un groupe de joueurs ayant collaboré. Elle a été introduite par Lloyd Shapley en 1951 et est depuis devenue un outil fondamental en économie, en science politique et, plus récemment, en apprentissage automatique pour interpréter les prédictions des modèles. La valeur attribue à chaque joueur une part du gain total basée sur sa contribution marginale moyenne à travers toutes les coalitions possibles des autres joueurs. C'est la distribution unique qui satisfait quatre propriétés clés : l'efficacité, la symétrie, l'additivité et la propriété du joueur factice, ce qui en fait une norme largement acceptée pour l'allocation équitable.
Dans le contexte de l'apprentissage automatique, la valeur de Shapley est utilisée pour expliquer les prédictions individuelles en attribuant la contribution de chaque caractéristique à la sortie du modèle. Cette approche, souvent appelée SHAP (SHapley Additive exPlanations), fournit un cadre unifié pour l'importance des caractéristiques qui est à la fois théoriquement fondé et pratiquement applicable. La complexité de calcul des valeurs de Shapley exactes croît de manière exponentielle avec le nombre de caractéristiques, ce qui a conduit au développement de diverses méthodes d'approximation.
Définition et formule
Formellement, considérons un jeu coopératif avec un ensemble de joueurs \( N \) et une fonction de valeur \( v \) qui attribue un nombre réel à chaque sous-ensemble (coalition) \( S \subseteq N \). La valeur de Shapley pour le joueur \( i \) est définie comme :
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) \]
où \( n = |N| \). Cette formule peut être interprétée comme la contribution marginale moyenne du joueur \( i \) sur tous les ordres possibles dans lesquels la coalition peut être formée. Une formulation équivalente somme sur toutes les \( n! \) permutations des joueurs, où \( P_i^R \) est l'ensemble des joueurs précédant \( i \) dans l'ordre \( R \) :
\[ \phi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right] \]
La fonction de valeur \( v(S) \) représente le gain total que la coalition \( S \) peut atteindre en coopérant. La valeur de Shapley distribue la valeur totale \( v(N) \) entre tous les joueurs, garantissant que chaque joueur reçoit sa contribution moyenne au résultat global.
Propriétés
La valeur de Shapley est le seul concept de solution qui satisfait les quatre axiomes suivants, considérés comme essentiels pour une distribution équitable :
- Efficacité : La somme de toutes les valeurs de Shapley est égale à la valeur totale de la grande coalition, \( \sum_{i \in N} \phi_i(v) = v(N) \). Cela garantit que la totalité du gain est distribuée.
- Symétrie : Si deux joueurs \( i \) et \( j \) contribuent de manière égale à toutes les coalitions (c'est-à-dire \( v(S \cup \{i\}) = v(S \cup \{j\}) \) pour tout \( S \subseteq N \setminus \{i,j\} \)), alors ils reçoivent la même valeur de Shapley. Cela garantit l'équité entre les contributeurs identiques.
- Additivité : Pour deux jeux \( v \) et \( w \), la valeur de Shapley du jeu combiné \( v + w \) est la somme des valeurs de Shapley des jeux individuels, \( \phi_i(v + w) = \phi_i(v) + \phi_i(w) \). Cette propriété permet la décomposition de jeux complexes.
- Propriété du joueur factice : Si un joueur \( i \) n'ajoute aucune valeur à aucune coalition (c'est-à-dire \( v(S \cup \{i\}) = v(S) \) pour tout \( S \subseteq N \setminus \{i\} \)), alors \( \phi_i(v) = 0 \). Cela garantit que les joueurs qui ne contribuent pas ne reçoivent rien.
Ces propriétés font de la valeur de Shapley une méthode unique et fondée sur des principes pour attribuer le crédit ou le coût entre les participants.
Applications en apprentissage automatique
En apprentissage automatique, la valeur de Shapley est appliquée pour interpréter les prédictions des modèles en traitant chaque caractéristique comme un joueur et la sortie du modèle comme la fonction de valeur. Pour une prédiction donnée, la valeur de Shapley d'une caractéristique quantifie sa contribution à la différence entre la sortie du modèle et la prédiction moyenne. Cette approche, connue sous le nom de SHAP, a été popularisée par Scott Lundberg et Su-In Lee en 2017. Les valeurs SHAP fournissent une mesure unifiée de l'importance des caractéristiques qui est cohérente avec les axiomes de la valeur de Shapley, ce qui en fait un outil fiable pour l'interprétabilité des modèles.
L'utilisation des valeurs de Shapley en apprentissage automatique a considérablement augmenté, en particulier dans les domaines où la compréhension des décisions des modèles est critique, comme la finance, la santé et les systèmes autonomes. Par exemple, dans la notation de crédit, les valeurs SHAP peuvent révéler quels facteurs influencent le plus une décision d'approbation de prêt, facilitant la conformité réglementaire et les audits d'équité. Dans le diagnostic médical, elles aident les cliniciens à comprendre pourquoi un modèle prédit une certaine condition, augmentant la confiance dans les décisions assistées par l'IA.
Défis computationnels
Le calcul des valeurs de Shapley exactes nécessite l'évaluation de la fonction de valeur pour toutes les \( 2^n \) coalitions possibles, ce qui est computationnellement infaisable pour les modèles avec de nombreuses caractéristiques. Pour un modèle avec \( n \) caractéristiques, la complexité est \( O(2^n) \), rendant le calcul exact impraticable au-delà de quelques dizaines de caractéristiques. Pour y remédier, plusieurs méthodes d'approximation ont été développées :
- Échantillonnage de Monte Carlo : Échantillonner aléatoirement des permutations de caractéristiques et moyenner les contributions marginales, fournissant une estimation sans biais avec une variance contrôlable.
- TreeSHAP : Un algorithme spécifiquement conçu pour les modèles basés sur des arbres (par exemple, forêts aléatoires, boosting de gradient) qui calcule des valeurs de Shapley exactes en temps polynomial en exploitant la structure des arbres de décision.
- KernelSHAP : Une méthode indépendante du modèle qui utilise une régression linéaire pondérée pour approximer les valeurs de Shapley, adaptée à tout modèle boîte noire.
- Méthodes basées sur le gradient : Pour les réseaux de neurones, des approximations utilisant des gradients ou des mécanismes d'attention peuvent fournir des estimations rapides, bien qu'elles puissent ne pas satisfaire tous les axiomes de Shapley.
Ces approximations ont rendu possible l'application des valeurs de Shapley à des modèles d'apprentissage automatique à grande échelle, y compris les réseaux de neurones profonds et les grands modèles de langage, où l'interprétabilité est de plus en plus importante.
Concepts et extensions connexes
La valeur de Shapley a été étendue et adaptée de diverses manières pour répondre à différents besoins. En théorie des jeux coopératifs, l'indice de pouvoir de Shapley-Shubik et l'indice de pouvoir de Banzhaf sont des applications spécialisées pour les jeux de vote. En apprentissage automatique, SHAP a été étendu pour gérer les interactions entre caractéristiques, fournissant des attributions de second ordre qui capturent les effets synergiques. De plus, le concept a été appliqué pour expliquer le comportement des grands modèles de langage, où il aide à identifier quelles parties du texte d'entrée influencent le plus la sortie générée.
La valeur de Shapley est également liée à d'autres méthodes d'attribution, telles que LIME (Local Interpretable Model-agnostic Explanations), mais elle offre des garanties théoriques plus fortes en raison de sa fondation axiomatique. Alors que LIME se concentre sur la fidélité locale, SHAP assure la cohérence et la précision locale, ce qui en fait un choix préféré dans de nombreuses applications pratiques.
Contexte historique
Lloyd Shapley a introduit le concept dans son article de 1951 "A Value for n-Person Games", qui a jeté les bases de la théorie des jeux coopératifs. Son travail lui a valu le prix Nobel Memorial en sciences économiques en 2012, partagé avec Alvin Roth, pour ses contributions à la théorie des allocations stables et à la pratique de la conception de marché. La valeur de Shapley est depuis devenue une pierre angulaire de la théorie économique, influençant des domaines tels que l'allocation des coûts, le partage des bénéfices et l'analyse des réseaux.
Dans les années 2010, l'essor de l'apprentissage automatique et le besoin d'interprétabilité des modèles ont mis la valeur de Shapley sous les projecteurs. Les chercheurs ont reconnu que les axiomes d'équité dans les jeux coopératifs correspondent aux exigences pour expliquer les prédictions des modèles, conduisant au développement de SHAP et à son adoption généralisée. Aujourd'hui, la valeur de Shapley est un outil standard dans la boîte à outils des scientifiques des données et des chercheurs en IA, comblant le fossé entre la théorie des jeux et l'intelligence artificielle moderne.
Voir aussi
- Machine Learning
- Intelligence Artificielle
- Apprentissage Profond
- Réseau de Neurones
- Élagage de Modèle
- Augmentation de Données
Références
- Shapley, L. S. (1951). "A Value for n-Person Games." In Contributions to the Theory of Games, volume II.
- Lundberg, S. M., & Lee, S.-I. (2017). "A Unified Approach to Interpreting Model Predictions." Advances in Neural Information Processing Systems.
- Strumbelj, E., & Kononenko, I. (2014). "Explaining Prediction Models and Individual Predictions with Feature Contributions." Knowledge and Information Systems.