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é. Nommée d'après Lloyd Shapley, qui l'a introduite en 1951, elle répond à la question de savoir quel crédit ou quel blâme chaque participant mérite lorsqu'un résultat collectif est produit. La méthode calcule la contribution marginale moyenne de chaque joueur sur toutes les coalitions possibles, garantissant une répartition qui satisfait quatre propriétés fondamentales : l'efficacité, la symétrie, l'additivité et la propriété du joueur factice. Au-delà de ses origines en économie, la valeur de Shapley est devenue un pilier de l'interprétabilité en apprentissage automatique, où elle est utilisée pour attribuer les prédictions de modèles complexes à des caractéristiques d'entrée individuelles.
L'idée centrale est d'évaluer comment le résultat global change lorsqu'un joueur rejoint chaque sous-ensemble possible des autres joueurs, puis de faire la moyenne de ces changements sur tous les sous-ensembles et tous les ordres d'arrivée possibles. Cette approche tient compte des interactions entre les joueurs, reconnaissant qu'une contribution peut dépendre de qui est déjà dans la coalition. Parce qu'elle est la seule règle de répartition qui satisfait simultanément les quatre propriétés axiomatiques, elle est souvent décrite comme la manière unique et équitable de diviser les gains coopératifs.
Définition
Dans un jeu coopératif, un ensemble de joueurs \(N\) peut former des coalitions \(S \subseteq N\), et une fonction de valeur \(v(S)\) assigne le gain total que les membres de \(S\) peuvent obtenir en coopérant. La valeur de Shapley pour un joueur \(i\) est donnée par la formule :
\[\varphi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))\]
où \(n\) est le nombre total de joueurs. Le terme \(v(S \cup \{i\}) - v(S)\) est la contribution marginale du joueur \(i\) à la coalition \(S\). Le coefficient combinatoire \(\frac{|S|! (n - |S| - 1)!}{n!}\) représente le nombre de permutations dans lesquelles les joueurs de \(S\) précèdent \(i\) et les joueurs restants le suivent. Une formulation équivalente fait la moyenne de la contribution marginale sur les \(n!\) ordres possibles des joueurs, où \(P_i^R\) désigne l'ensemble des joueurs précédant \(i\) dans l'ordre \(R\) :
\[\varphi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right]\]
Cette interprétation imagine la coalition se formant un joueur à la fois, chaque joueur recevant sa contribution marginale comme compensation, puis on fait la moyenne sur toutes les séquences de formation possibles.
Propriétés axiomatiques
La valeur de Shapley est caractérisée de manière unique par quatre axiomes, largement acceptés comme définissant une répartition équitable :
- Efficacité : La somme des valeurs de Shapley de tous les joueurs est égale à la valeur totale de la grande coalition, \(\sum_{i \in N} \varphi_i(v) = v(N)\). Cela garantit qu'aucune valeur n'est perdue ou créée.
- Symétrie : Si deux joueurs \(i\) et \(j\) contribuent de manière identique à chaque coalition (c'est-à-dire \(v(S \cup \{i\}) = v(S \cup \{j\})\) pour tout \(S\) ne contenant ni l'un ni l'autre), ils reçoivent des parts égales.
- Additivité : Pour deux jeux \(v\) et \(w\), la valeur de Shapley du jeu combiné \(v+w\) est la somme des valeurs de Shapley individuelles, \(\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)\). Cette propriété soutient la décomposition de problèmes complexes.
- Joueur factice : Si un joueur \(i\) n'ajoute aucune valeur à aucune coalition (c'est-à-dire \(v(S \cup \{i\}) = v(S)\) pour tout \(S\)), sa valeur de Shapley est nulle.
Ces axiomes ont été formalisés dans l'article de Shapley de 1951 et affinés dans sa publication de 1953. Ils garantissent que la valeur n'est pas arbitraire mais découle de critères d'équité.
Applications en économie et en entreprise
En théorie des jeux coopératifs, la valeur de Shapley a été utilisée pour répartir les coûts et les bénéfices dans divers contextes économiques. Par exemple, dans un partenariat commercial, les partenaires peuvent l'utiliser pour diviser les profits en fonction de leurs contributions marginales à différents projets. Elle a été appliquée à la répartition des coûts dans les coentreprises, comme le partage des coûts d'une infrastructure commune entre plusieurs utilisateurs. Dans la gestion de la chaîne d'approvisionnement, elle aide à déterminer des prix équitables pour les composants lorsque des entreprises collaborent pour produire un produit final. La méthode est également utilisée dans l'analyse du pouvoir de vote, où elle mesure l'influence de chaque électeur dans un système de vote pondéré, bien que l'indice de pouvoir de Banzhaf, étroitement lié, soit parfois préféré dans ce contexte.
Valeur de Shapley en apprentissage automatique
En apprentissage automatique, la valeur de Shapley a été adaptée pour expliquer les prédictions individuelles des modèles, un domaine connu sous le nom d'attribution de caractéristiques. Les joueurs sont les caractéristiques d'entrée, et la fonction de valeur \(v(S)\) est la prédiction du modèle lorsque seules les caractéristiques du sous-ensemble \(S\) sont connues, généralement en marginalisant les autres caractéristiques. La valeur de Shapley d'une caractéristique mesure sa contribution moyenne à la prédiction, en tenant compte des interactions avec toutes les autres caractéristiques. Cette approche est indépendante du modèle, ce qui signifie qu'elle peut être appliquée à tout modèle prédictif, y compris les réseaux de neurones profonds, les ensembles de modèles et les grands modèles de langage.
Une implémentation clé est SHAP (SHapley Additive exPlanations), introduit par Scott Lundberg et Su-In Lee en 2017. SHAP fournit des algorithmes pour approximer les valeurs de Shapley pour des modèles complexes, car le calcul exact est exponentiel en nombre de caractéristiques. La méthode est devenue un outil standard pour l'interprétabilité des modèles, aidant les scientifiques des données et les régulateurs à comprendre pourquoi un modèle a pris une décision particulière.
Défis computationnels et approximations
Le calcul exact de la valeur de Shapley nécessite de sommer sur \(2^n\) sous-ensembles, ce qui est computationnellement infaisable pour les modèles avec de nombreuses caractéristiques. Par exemple, pour un modèle avec 30 caractéristiques, il y a plus d'un milliard de coalitions possibles. Plusieurs techniques d'approximation ont été développées :
- Échantillonnage de Monte Carlo : Échantillonner aléatoirement des permutations ou des sous-ensembles et faire la moyenne des contributions marginales. Cela fournit une estimation sans biais avec une variance contrôlable.
- TreeSHAP : Pour les modèles basés sur des arbres comme les forêts aléatoires et le boosting de gradient, TreeSHAP calcule les valeurs de Shapley en temps polynomial en exploitant la structure de l'arbre.
- 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, souvent utilisée pour les modèles en boîte noire.
- Méthodes basées sur le gradient : Pour les modèles différentiables, des approximations peuvent être calculées à l'aide de gradients, bien qu'elles puissent ne pas satisfaire exactement tous les axiomes.
Ces approximations ont rendu les valeurs de Shapley pratiques pour des applications réelles, notamment le scoring de crédit, le diagnostic médical et le traitement du langage naturel.
Relation avec d'autres méthodes d'attribution
La valeur de Shapley est souvent comparée à d'autres techniques d'attribution de caractéristiques. Contrairement à des méthodes simples comme l'importance par permutation ou les cartes de saillance basées sur le gradient, les valeurs de Shapley tiennent compte des interactions entre les caractéristiques et satisfont la propriété d'efficacité, garantissant que les attributions somme au résultat du modèle. Cependant, elle suppose que les caractéristiques sont indépendantes lors de la marginalisation, ce qui peut conduire à des échantillons irréalistes si les caractéristiques sont fortement corrélées. Des alternatives comme LIME (Local Interpretable Model-agnostic Explanations) sont plus rapides mais ne garantissent pas les mêmes propriétés axiomatiques. En théorie des jeux coopératifs, la valeur de Shapley est l'un des nombreux concepts de solution, y compris le nucléole et le cœur, mais elle est la seule à satisfaire simultanément les quatre axiomes.
Extensions et variantes
Plusieurs extensions de la valeur de Shapley ont été proposées pour différents contextes. La valeur de Shapley pondérée permet aux joueurs d'avoir des poids différents, reflétant un pouvoir de négociation inégal. L'indice de pouvoir de Shapley-Shubik applique la valeur aux jeux de vote, mesurant la probabilité qu'un joueur soit pivot. En apprentissage automatique, des variantes comme les indices d'interaction de Shapley décomposent l'attribution totale en effets principaux et effets d'interaction entre les caractéristiques. Pour les données de séries temporelles, les valeurs de Shapley dynamiques tiennent compte des dépendances temporelles. Ces extensions préservent l'idée centrale de la moyenne des contributions marginales équitables tout en s'adaptant à des structures de problèmes spécifiques.
Limites et critiques
Malgré son attrait théorique, la valeur de Shapley présente des limites. L'hypothèse d'indépendance des caractéristiques dans les applications d'apprentissage automatique peut produire des attributions trompeuses lorsque les caractéristiques sont corrélées. Le coût computationnel exponentiel, même avec des approximations, peut être prohibitif pour des données à très haute dimension. De plus, la fonction de valeur dans les modèles prédictifs n'est pas toujours bien définie, car marginaliser les caractéristiques nécessite une distribution sur l'espace des caractéristiques, qui peut ne pas être connue. Les critiques soutiennent que les propriétés axiomatiques, bien qu'élégantes, peuvent ne pas toujours correspondre aux notions humaines d'équité dans des scénarios pratiques. Néanmoins, la valeur de Shapley reste un concept fondamental dans la théorie des jeux et l'IA interprétable, avec une recherche active pour relever ces défis.
Contexte historique
Lloyd Shapley a introduit la valeur en 1951 alors qu'il travaillait à la RAND Corporation, et elle a été formellement publiée en 1953. Son travail s'est appuyé sur des idées antérieures en théorie des jeux coopératifs, en particulier les travaux de John von Neumann et Oskar Morgenstern. Shapley a ensuite reçu le prix Nobel Memorial en sciences économiques en 2012, conjointement avec Alvin Roth, pour ses contributions à la théorie des jeux. L'adoption de la valeur de Shapley en apprentissage automatique a commencé dans les années 2010, motivée par le besoin d'interprétabilité des modèles à mesure que les systèmes d'IA devenaient plus complexes. Aujourd'hui, c'est un outil standard dans la boîte à outils des scientifiques des données, implémenté dans des bibliothèques majeures telles que SHAP et scikit-learn.