A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Cet article propose ESENSC_rev2, une méthode d'attribution de caractéristiques axiomatique et polynomialle qui offre une alternative efficace et précise au SHAP en combinant des règles de répartition proportionnelle et de surplus égal pour garantir l'échelle dans les contextes d'explicabilité à haute dimension.

L'essentiel

Imaginez que vous avez un gâteau délicieux (c'est la prédiction de votre intelligence artificielle) et que vous voulez savoir qui a contribué à sa fabrication : le chef, le boulanger, ou celui qui a apporté les œufs ?

Dans le monde de l'IA, on appelle cela l'attribution de caractéristiques. La méthode la plus célèbre aujourd'hui pour partager ce gâteau s'appelle SHAP. C'est comme un juge très juste, basé sur des mathématiques complexes (la théorie des jeux coopératifs), qui calcule exactement combien chaque ingrédient a apporté au goût final.

Le problème ? Ce juge est très lent. Plus il y a d'ingrédients (de caractéristiques) dans votre recette, plus le temps de calcul explose. Si vous avez 500 ingrédients, SHAP mettrait des années à partager le gâteau équitablement. C'est comme si vous deviez peser chaque grain de sucre individuellement avant de servir le gâteau.

C'est là que cette recherche intervient. Les auteurs proposent une nouvelle méthode, plus rapide et tout aussi juste, qu'ils appellent ESENSC_rev2.

Voici comment cela fonctionne, expliqué simplement :

1. Le problème de la "Générosité" (Le Null Player)

Dans les méthodes mathématiques classiques, il arrive parfois qu'un ingrédient qui n'a aucun effet sur le goût (un "joueur nul") reçoive quand même un petit morceau de gâteau par pure générosité mathématique.

• Pour un humain : C'est gentil.
• Pour une IA : C'est faux. Si l'âge du client n'influence pas le risque de défaut de paiement, il ne doit rien recevoir.
  La nouvelle méthode ESENSC_rev2 est stricte : si un ingrédient ne sert à rien, il ne reçoit rien. C'est plus logique pour expliquer une décision.

2. La méthode du "Juste Milieu" (La recette secrète)

Pour calculer la part de chacun sans attendre des heures, les auteurs ont créé une recette simple en deux étapes :

1. Regarder le début : Combien le gâteau a-t-il changé quand on a ajouté un seul ingrédient ?
2. Regarder la fin : Combien le gâteau a-t-il changé quand on a retiré un ingrédient du gâteau fini ?

Ensuite, ils font la moyenne de ces deux points de vue. C'est comme si vous disiez : "Regardons ce que cet ingrédient apporte s'il est le premier, et ce qu'il apporte s'il est le dernier, puis on fait la moyenne."
C'est une astuce mathématique qui permet de calculer la part de chacun en une fraction de seconde, même avec des centaines d'ingrédients, tout en restant très proche du résultat du "juge lent" (SHAP).

3. Le test de la réalité

Les chercheurs ont testé leur méthode sur de vraies données (comme prédire le prix des maisons en Californie) avec des modèles d'IA complexes (comme des réseaux de neurones).

• Résultat : Leur méthode est beaucoup plus rapide que SHAP (elle ne ralentit pas quand le nombre de caractéristiques augmente).
• Précision : Elle donne un résultat presque identique à celui du "juge lent". C'est comme si vous aviez un compte-rendu ultra-rapide qui dit la même chose que le rapport détaillé de 100 pages.

4. Pourquoi c'est important ?

Aujourd'hui, les entreprises veulent expliquer leurs décisions d'IA (pour respecter les lois ou rassurer les clients), mais elles ne peuvent pas attendre des heures pour chaque explication.
Cette nouvelle méthode est comme un moteur de formule 1 : elle est conçue pour aller vite sans sacrifier la précision. Elle offre une alternative théoriquement solide (elle est basée sur des règles mathématiques strictes) et pratiquement utile.

En résumé :
Si SHAP est un artisan qui sculpte chaque détail du gâteau avec un couteau de chirurgien (très précis, mais très lent), ESENSC_rev2 est un chef étoilé qui utilise une technique de coupe intelligente pour obtenir le même résultat en un clin d'œil. C'est une solution idéale pour l'IA moderne, où la vitesse compte autant que la justesse.

Résumé technique

1. Problématique

L'explicabilité des modèles d'intelligence artificielle (XAI) repose souvent sur l'attribution de caractéristiques (Feature Attribution), qui vise à décomposer la prédiction d'un modèle en contributions spécifiques à chaque variable d'entrée. La méthode la plus répandue est SHAP (SHapley Additive exPlanations), basée sur la valeur de Shapley de la théorie des jeux coopératifs.

Cependant, SHAP présente deux limitations majeures :

1. Coût computationnel prohibitif : Le calcul exact de la valeur de Shapley nécessite d'évaluer toutes les coalitions possibles de caractéristiques, ce qui entraîne une complexité exponentielle ($O(2^n)$) par rapport au nombre de caractéristiques $n$. Cela rend le calcul exact impossible pour les jeux de données à haute dimension.
2. Instabilité des approximations : Les algorithmes d'approximation existants (comme Kernel SHAP ou Permutation SHAP) nécessitent des paramètres de réglage, peuvent être instables en termes de précision et ne garantissent pas toujours les propriétés théoriques souhaitées.

L'objectif de cet article est de proposer une alternative à SHAP qui soit à la fois théoriquement fondée (garantie par des axiomes) et computationnellement efficace (temps polynomial), tout en conservant une haute précision d'approximation.

2. Méthodologie

Les auteurs formalisent le problème d'attribution de caractéristiques comme un jeu coopératif à utilité transférable (TU) spécifique au domaine de l'IA, qu'ils appellent jeu XAI-TU.

A. Définition du Jeu XAI-TU

Pour une observation donnée, le jeu est défini par une fonction caractéristique $v(S)$, représentant l'espérance de la prédiction du modèle lorsque les caractéristiques de l'ensemble $S$ sont connues et les autres sont traitées selon leur distribution empirique.

• Particularité : Contrairement aux jeux TU classiques où $v(\emptyset)=0$, ici $v(\emptyset)$ correspond à la prédiction de base (sans aucune information). De plus, les valeurs des coalitions peuvent être positives ou négatives, créant des situations où des contributions marginales de signes opposés coexistent.

B. Proposition de nouvelles règles d'attribution

Les auteurs explorent deux classes de solutions issues de la théorie des jeux coopératifs, connues pour leur faible coût de calcul :

1. Règles de type "Surplus Égal" (Equal Surplus - ES) :

   • Ils partent du concept de mélange 50/50 entre la solution Equal Surplus (ES) et la Egalitarian Nonseparable Contribution (ENSC).
   • Problème initial : Le mélange simple ne satisfait pas la propriété du joueur nul (un joueur qui n'apporte aucune contribution marginale devrait recevoir 0).
   • Solution proposée ($\psi_{ESENSC\_rev2}$) : Ils modifient le mélange ES-ENSC pour redistribuer le surplus résiduel uniquement aux joueurs ayant une contribution marginale non nulle. Cette règle, notée ESENSC_rev2, satisfait la propriété du joueur nul tout en restant calculable en temps polynomial ($O(n)$ évaluations de la fonction caractéristique).

2. Règles de type "Allocation Proportionnelle" (Proportional Allocation - PA) :

   • Ils identifient un problème d'inversion d'ordre (order-reversal) dans les jeux XAI-TU : lorsque les contributions totales et les contributions marginales ont des signes opposés, une règle proportionnelle simple peut attribuer une valeur plus élevée à un joueur ayant une contribution marginale plus faible.
   • Ils proposent des règles ajustées (comme $\psi_{PARPA}$) pour éviter ce problème, mais les résultats empiriques montrent que ces règles souffrent d'instabilité intrinsèque et s'écartent fortement de SHAP.

C. Caractérisation Axiomatique

Pour justifier théoriquement la règle ESENSC_rev2, les auteurs établissent un théorème d'unicité. Ils démontrent que cette règle est la seule solution satisfaisant un ensemble d'axiomes adaptés au contexte XAI :

• Efficacité : La somme des attributions égale la différence entre la prédiction complète et la prédiction de base.
• Propriété du joueur nul : Les caractéristiques sans impact reçoivent une attribution nulle.
• Différentialité marginale restreinte : Une version affaiblie de l'axiome de Shapley, adaptée aux contraintes de calcul.
• Propriété de jeu inessentiel intermédiaire : Une règle de répartition basée sur une perspective intermédiaire entre les contributions marginales directes et les contributions marginales inverses.
• Réduction de la complexité computationnelle : La règle ne nécessite pas l'évaluation des coalitions de taille intermédiaire (de 2 à $n-2$), se limitant aux tailles 0, 1, $n-1$ et $n$.

3. Résultats Expérimentaux

Les auteurs ont évalué leurs méthodes sur des tâches de régression tabulaire (jeu de données California Housing) en utilisant des modèles XGBoost et des réseaux de neurones, avec un nombre de caractéristiques allant de 8 à 512.

• Précision d'approximation :

  • La règle ESENSC_rev2 s'approche très étroitement des valeurs SHAP exactes. Son erreur est comparable, voire inférieure, à celle des approximations par échantillonnage (Permutation SHAP) et nettement supérieure à Kernel SHAP.
  • Les règles de type proportionnel (PA) montrent des écarts significatifs et instables par rapport à SHAP, confirmant leur inadéquation pour ce type de jeu.

• Coût computationnel :

  • ESENSC_rev2 est extrêmement rapide. Sa complexité est linéaire par rapport au nombre de caractéristiques.
  • Alors que le SHAP exact devient ingérable dès $n > 16$, et que les méthodes d'approximation (Permutation/Kernel) nécessitent des milliers d'évaluations de modèle, ESENSC_rev2 reste instantané même pour $n=512$.
  • Contrairement aux méthodes d'approximation, ESENSC_rev2 ne nécessite aucun paramètre de réglage (comme le nombre d'échantillons).

4. Contributions Clés

1. Formalisation des jeux XAI-TU : Mise en évidence des propriétés structurelles uniques des jeux d'attribution de caractéristiques (valeurs de coalition mixtes, $v(\emptyset) \neq 0$) qui distinguent ce domaine de la théorie des jeux classique.
2. Développement d'une règle polynomiale : Proposition de ESENSC_rev2, une règle d'attribution additive qui combine faible coût de calcul, satisfaction de la propriété du joueur nul et haute précision.
3. Caractérisation Axiomatique : Première démonstration axiomatique d'une règle d'attribution de caractéristiques en temps polynomial qui approxime SHAP. Cela fournit une base théorique solide pour son utilisation en pratique.
4. Analyse comparative : Démonstration empirique que les règles proportionnelles, bien que rapides, sont intrinsèquement instables dans les jeux XAI-TU, tandis que les règles de type "Surplus Égal" offrent un compromis optimal.

5. Signification et Impact

Cet article propose une alternative viable et théoriquement justifiée à SHAP pour les pipelines d'explicabilité modernes.

• Praticité : Il résout le goulot d'étranglement computationnel de SHAP, permettant l'explicabilité en temps réel sur des modèles à haute dimension sans sacrifier la précision.
• Théorie : Il élargit le cadre de la théorie des jeux coopératifs pour l'IA, montrant que des solutions alternatives à la valeur de Shapley peuvent être à la fois axiomairement fondées et adaptées aux contraintes de l'apprentissage automatique.
• Futur : Les résultats suggèrent que les méthodes basées sur le "Surplus Égal" modifié sont préférables aux méthodes proportionnelles pour l'attribution de caractéristiques, ouvrant la voie à de nouvelles recherches sur des règles adaptées spécifiquement aux structures des jeux XAI-TU.

En résumé, ESENSC_rev2 se positionne comme une solution "prête à l'emploi" qui offre le meilleur équilibre entre rigueur théorique, précision et efficacité computationnelle, comblant le fossé entre les méthodes exactes trop lentes et les approximations trop imprécises.