🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Cet article introduit des algorithmes efficaces pour le calcul des valeurs de Shapley asymétriques en exploitant les graphes causaux, démontrant que le calcul exact est possible en temps polynomial pour les arbres dirigés enracinés et proposant une méthode d'approximation uniforme basée sur l'échantillonnage pour les DAG arbitraires afin de surmonter la complexité #P-difficile des calculs standards de la valeur de Shapley.

Auteurs originaux : Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Publié 2026-06-25

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

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 avez une équipe de joueurs (les caractéristiques) travaillant ensemble pour gagner un match (faire une prédiction). Vous voulez savoir exactement quel crédit chaque joueur mérite pour la victoire. Dans le monde de l'IA, cela s'appelle l'Explicabilité.

La méthode la plus célèbre pour y parvenir est appelée les Valeurs de Shapley. Considérez cela comme un arbitre équitable qui examine tous les ordres possibles dans lesquels les joueurs pourraient être entrés dans le match. Si le Joueur A entre en premier, en deuxième ou en dernier, l'arbitre calcule de combien le score de l'équipe a changé grâce à lui. Le score final pour le Jouier A est la moyenne de tous ces changements.

Le problème avec l'ancienne méthode
Le problème est que calculer cela pour chaque ordre possible est un cauchemar. Si vous avez 20 joueurs, il y a des milliards d'ordres à vérifier. Pour les modèles d'IA complexes, ce calcul est si difficile qu'il est pratiquement impossible à réaliser de manière exacte.

De plus, l'ancienne méthode traite tous les joueurs comme égaux. Si le Joueur B est une copie du Joueur A, ils reçoivent le même score. Mais dans la réalité, il arrive parfois qu'un joueur provoque l'action d'un autre. Si le Joueur A provoque le mouvement du Joueur B, le Joueur A est le véritable patron. L'ancienne méthode manque cette relation de « cause à effet ».

La nouvelle solution : Les Valeurs de Shapley Asymétriques (ASV)
Ce document présente un arbitre plus intelligent appelé Valeurs de Shapley Asymétriques (ASV). Au lieu d'examiner chaque ordre possible, cet arbitre ne regarde que les ordres qui font sens selon une Carte Causale (un diagramme montrant qui cause quoi).

L'analogie : Imaginez une chaîne de montage d'usine. On ne peut pas peindre une voiture avant d'avoir construit le châssis. La Carte Causale dit : « Le châssis d'abord, puis la peinture ». L'arbitre ASV ignore tout ordre où quelqu'un essaie de peindre avant de construire. Il ne compte que les ordres logiques de cause à effet.
Le bénéfice : Cela donne une explication plus honnête de ce qui a réellement causé le résultat. Cela rend aussi, de manière surprenante, le calcul plus facile dans certains cas où l'ancienne méthode était impossible.

Comment ils l'ont rendu rapide (Les tours de magie)
Même avec la Carte Causale, vérifier chaque ordre valide peut encore être trop lent. Les auteurs ont trouvé deux astuces ingénieuses pour accélérer cela :

L L'astuce du « Groupement » (Classes d'équivalence) :
Imaginez que vous comptez de combien de façons les gens peuvent se mettre en rang. Vous réalisez que, pour les besoins du calcul, peu importe si deux personnes échangent leurs places si elles se trouvent toutes les deux après le grand patron. Elles appartiennent au même « groupe ».
Les auteurs ont trouvé un moyen de regrouper des milliers d'ordres similaires en de simples « seaux » (appelés classes d'équivalence). Au lieu de vérifier 1 000 000 d'ordres, ils n'auraient peut-être besoin de vérifier que 500 groupes. Cela transforme une tâche impossible en une tâche rapide, surtout si la Carte Causale ressemble à un arbre simple (comme un arbre généalogique).
L'astuce de l'« Échantillonnage » (Deviner avec un échantillon) :
Si la carte est trop désordonnée pour être regroupée proprement, ils utilisent une méthode d'échantillonnage. Au lieu de vérifier chaque ordre valide, ils choisissent aléatoirement quelques centaines d'ordres qui respectent les règles et calculent la moyenne.

L'analogie : Au lieu de goûter chaque grain de riz dans une grande marmite pour voir s'il est salé, vous prenez une cuillerée à différents endroits. Si les cuillerées sont salées, vous savez que toute la marmite est salée. Le document montre que cette méthode de la « cuillerée » est rapide et donne une très bonne estimation.

Ce qu'ils ont testé
Les auteurs ont testé ces idées sur des structures de données réelles (comme des réseaux utilisés pour prédire le cancer ou le développement de l'enfant) et sur des structures d'arbres fictives.

Ils ont constaté que pour les structures de type arbre, leur méthode de « Groupement » était incroyablement rapide, réduisant le travail par des millions de fois par rapport à l'ancienne méthode.
Pour les structures plus désordonnées, leur méthode d'« Échantillonnage » était suffisamment rapide et précise pour être utile.

L'essentiel à retenir
Ce document prouve qu'en respectant les règles de « cause à effet » des données, nous pouvons expliquer les modèles d'IA de manière plus précise et plus rapide. Ils ont montré que pour certains types de données, une méthode qui était auparavant impossible à calculer exactement peut désormais être réalisée rapidement, et que pour d'autres, une estimation rapide et précise est facile à obtenir.

Résumé Technique : Au-delà de Shapley : Calcul efficace des valeurs de Shapley asymétriques

Énoncé du Problème

Le document traite des défis computationnels et d'interprétabilité associés à l'attribution de caractéristiques dans l'IA explicable (XAI). Bien que les valeurs de Shapley (et leur instanciation en apprentissage automatique, SHAP) constituent une méthode théoriquement fondée pour distribuer la prédiction d'un modèle entre les caractéristiques d'entrée, elles souffrent de deux limitations principales :

Intraitabilité Computationnelle : Le calcul exact des valeurs de Shapley est souvent #P-difficile, particulièrement pour les modèles expressifs (ex: réseaux de neurones) ou lorsque la distribution sous-jacente des données est complexe (ex: distributions de type Naive Bayes).
Déficits d'Interprétabilité : Les valeurs de Shapley standards traitent toutes les caractéristiques de manière symétrique. Cela ne permet pas de capturer les relations causales, pouvant attribuer une importance égale à une cause et à son effet déterministe, masquant ainsi le véritable processus générateur de données.

Pour remédier à ce second problème, les Valeurs de Shapley Asymétriques (ASV) ont été proposées, lesquelles restreignent le calcul aux permutations de caractéristiques qui respectent un graphe causal donné (un graphe orienté acyclique ou DAG). Cependant, la complexité computationnelle de l'ASV n'avait pas été explorée de manière approfondie. Ce document examine si l'incorporation de contraintes causales peut réellement rendre le calcul des scores d'attribution plus traitable que les valeurs de Shapley standard dans certains contextes spécifiques.

Méthodologie

Les auteurs proposent une suite d'algorithmes pour calculer l'ASV de manière exacte et approximative, en exploitant la structure du graphe causal et la distribution de probabilité sous-jacente (modélisée comme un réseau bayésien).

1. Analyse de la Traitabilité Théorique

Les auteurs établissent un résultat théorique concernant la complexité de l'ASV sous des distributions de type Naive Bayes. Ils prouvent que, si le calcul des valeurs de Shapley standard est intraitable pour certaines familles de modèles sous des distributions Naive Bayes, le calcul de l'ASV est polynomialement traitable pour ces mêmes familles si le graphe causal utilisé pour l'ASV est identique à la structure du réseau Naive Bayes. Cela suggère que les contraintes causales imposées par la distribution peuvent briser les symétries qui rendent autrement le problème difficile.

2. Calcul Exact via les Classes d'Équivalence

Pour étendre la traitabilité à des structures causales plus générales, spécifiquement les arbres orientés enracinés, les auteurs introduisent une méthode pour réduire l'espace de recherche des permutations :

Classes d'Équivalence : Ils définissent une relation d'équivalence sur l'ensemble des ordonnancements topologiques du graphe causal. Deux ordonnancements sont équivalents par rapport à une caractéristique $x$ si l'ensemble des caractéristiques précédant $x$ est identique dans les deux ordonnancements.
Algorithme : Au lieu d'itérer à travers tous les ordonnancements topologiques (ce qui peut être exponentiel), l'algorithme calcule l'ensemble des classes d'équivalence ( $\Lambda_x^C$ ) et la taille de chaque classe. L'ASV est ensuite calculée en sommant les contributions marginales pondérées par la taille de chaque classe d'équivalence.
Complexité : Pour les arbres orientés enracinés, le nombre de classes d'équivalence est borné par $h \cdot l + 1$ (où $h$ est la profondeur et $l$ le nombre de feuilles). Les auteurs fournissent un algorithme en temps polynomial (en termes de nombre de classes d'équivalence) pour calculer ces classes et leurs tailles.

3. Calcul Approximatif via l'Échantillonnage

Pour les DAG arbitraires où le calcul exact peut être irréalisable, les auteurs proposent un schéma d'approximation basé sur l'échantillonnage.

Échantillonnage des Ordonnancements Topologiques : La méthode repose sur l'échantillonnage d'ordonnancements topologiques de manière uniforme et aléatoire. Les auteurs implémentent deux approches :
1. Un algorithme de comptage récursif pour les polytrees (graphes possédant au plus un chemin entre deux nœuds quelconques) qui compte les ordonnancements topologiques pour pondérer correctement les nœuds sources.
2. Un algorithme basé sur une marche aléatoire (basé sur Bubley & Dyer, 1999) pour les DAG généraux.
Bornes d'Erreur : Ils formalisent que si l'échantillonneur d'ordonnancement topologique est $\epsilon_{samp}$ -proche de l'uniformité et que la fonction caractéristique (valeur attendue du modèle) est approximée avec une erreur $\epsilon_{\nu}$ , l'estimation de l'ASV résultante présente une erreur additive de $O(\epsilon_{samp} + \epsilon_{\nu})$ .

Résultats Clés

Les auteurs ont évalué leurs méthodes sur des réseaux bayésiens réels (Cancer, Child) et des structures artificielles (arbres équilibrés, Naive Bayes, chemins multiples).

Réduction de l'Espace de Recherche : L'approche par classes d'équivalence réduit considérablement la charge de calcul par rapport à l'énumération de tous les ordres topologiques. Dans le réseau "Child", le nombre d'ordonnancements topologiques était d'environ $7,41 \times 10^{11}$ , alors que le nombre de classes d'équivalence n'était que d'environ $2003$ en moyenne.
Efficacité du Temps d'Exécution :
- Le calcul des classes d'équivalence pour des tailles de graphes pratiques a pris moins d'une seconde.
- Le temps d'exécution de l'algorithme exact était fortement corrélé au nombre de classes d'équivalence, permettant au pré-calcul des comptes de classes de servir de prédicteur du coût de calcul.
- L'énumération de tous les ordres topologiques est devenue irréalisable pour des graphes plus grands, tandis que la méthode des classes d'équivalence est restée traitable.
Performance de l'Échantillonnage :
- L'algorithme d'échantillonnage récursif personnalisé pour les polytrees était efficace, avec une mise à l'échelle non linéaire par rapport au nombre d'échantillons en raison de la génération parallèle de candidats.
- L'utilisation de 1 000 échantillons a produit une erreur relative moyenne d'environ 8 % pour les valeurs d'ASV. L'erreur était plus faible pour les valeurs d'ASV élevées et plus élevée pour les valeurs réelles très faibles.

Signification et Revendications

Le document affirme que l'ASV est un cadre viable et potentiellement supérieur pour l'explicabilité lorsque la structure causale est pertinente, car elle capture les dépendances que SHAP standard manque. La contribution principale est de démontrer que les contraintes causales peuvent transformer un problème intraitable en un problème traitable pour des paires modèle-distribution spécifiques (ex: arbres de décision sous Naive Bayes).

Les auteurs soulignent que, bien que l'ASV offre ces avantages théoriques et pratiques, sa scalabilité dépend fortement de la topologie du graphe causal :

Pour les arbres orientés en racines et les polytrees, le calcul exact est réalisable via les classes d'équivalence.
Pour les DAG denses ou de grande taille, le nombre de classes d'équivalence peut tout de même croître de manière trop importante, nécessissant l'usage d'approximations par échantillonnage.

Le travail conclut que l'ASV est une direction prometteuse pour l'XAI, à condition que le graphe causal soit connu et que la structure du graphe permette une énumération ou un échantillonnage efficace des ordonnancements topologiques. Des travaux futurs sont suggérés pour généraliser les algorithmes exacts à des classes de graphes plus larges (ex: polytrees généraux) et pour optimiser les mécanismes d'échantillonnage.