🤖 AI

PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

Cet article présente PolySHAP, une méthode qui étend KernelSHAP en utilisant une régression polynomiale de degré supérieur pour mieux capturer les interactions entre les caractéristiques, tout en fournissant la première preuve théorique que l'échantillonnage apparié est équivalent à PolySHAP du second ordre, justifiant ainsi son succès empirique.

Auteurs originaux : Fabian Fumagalli, R. Teal Witter, Christopher Musco

Publié 2026-05-14

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Fabian Fumagalli, R. Teal Witter, Christopher Musco

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

La Vue d'Ensemble : Pourquoi en Avons-Nous Besoin ?

Imaginez que vous possédez une machine complexe (comme un modèle d'apprentissage automatique) qui émet une prédiction, telle que « Ce prêt devrait être approuvé » ou « Cette image représente un chat ». Vous voulez savoir pourquoi. Quelles caractéristiques spécifiques (comme le revenu, l'âge ou les couleurs des pixels) ont le plus contribué à cette décision ?

Dans le monde de l'IA, nous utilisons un outil mathématique appelé valeurs de Shapley pour y répondre. Considérez les valeurs de Shapley comme un moyen de répartir équitablement une « récompense » (la prédiction) parmi une équipe de joueurs (les caractéristiques) en fonction de la mesure dans laquelle chacun a aidé l'équipe à gagner.

Le Problème :
Calculer la valeur de Shapley exacte revient à essayer de compter chaque combinaison possible de joueurs dans une équipe sportive pour voir qui compte le plus. Si vous avez 10 caractéristiques, il y a plus de 1 000 combinaisons. Si vous en avez 20, il y a plus d'un million. Il faut trop de temps pour les vérifier toutes.

La Solution Actuelle (KernelSHAP) :
La méthode populaire actuelle, appelée KernelSHAP, est comme un raccourci intelligent. Au lieu de vérifier chaque combinaison, elle sélectionne quelques groupes aléatoires de joueurs, observe leur performance, puis trace une ligne droite à travers les données pour deviner le reste. Elle suppose que la relation entre les caractéristiques est simple et additive (comme ajouter des ingrédients à un gâteau : 1 tasse de sucre + 2 tasses de farine = un goût spécifique).

La Limite :
La vie réelle n'est pas toujours une ligne droite. Parfois, les ingrédients interagissent de manière étrange. Peut-être que le sucre et la farine ensemble font un gâteau, mais le sucre seul ne fait rien, et la farine seule n'est que de la poussière. Une ligne droite ne peut pas capturer cette « combinaison magique » (interaction).

La Nouvelle Solution : PolySHAP

Les auteurs introduisent PolySHAP. Au lieu de tracer une ligne droite à travers les données, PolySHAP trace une ligne courbe et ondulée (un polynôme).

L'Analogie : Imaginez que vous essayez de prédire la hauteur d'une plante en fonction de la lumière du soleil et de l'eau.
- KernelSHAP (Linéaire) : Suppose que plus de soleil équivaut toujours à plus de hauteur, et plus d'eau équivaut toujours à plus de hauteur, et qu'ils s'additionnent simplement.
- PolySHAP (Polynomial) : Réalise que peut-être la plante ne pousse grande que si elle reçoit à la fois du soleil et de l'eau. Elle capture cette « interaction ».

En utilisant ces lignes courbes, PolySHAP peut comprendre que les caractéristiques fonctionnent parfois mieux ensemble que séparément. Le papier démontre que cette méthode offre une répartition équitable « plus précise » de la prédiction que l'ancienne méthode à ligne droite.

Le « Tour de Magie » : L'Échantillonnage Apparié

Le papier examine également un tour populaire utilisé dans l'ancienne méthode, appelé Échantillonnage Apparié.

Le Tour : Au lieu de simplement sélectionner des groupes aléatoires de joueurs, vous choisissez un groupe (par exemple, {Soleil, Eau}) et choisissez immédiatement son opposé (par exemple, {Pas de Soleil, Pas d'Eau}). Vous les examinez toujours par paires.
Le Mystère : Tout le monde savait que ce tour améliorait les résultats, mais personne ne savait pourquoi cela fonctionnait si bien mathématiquement.

La Découverte du Papier :
Les auteurs ont prouvé une connexion surprenante : L'Échantillonnage Apparié fait en réalité exactement la même chose que PolySHAP avec un type spécifique de courbe (un polynôme de degré 2), même s'il ne trace jamais réellement la courbe.

La Métaphore : C'est comme un magicien qui fait apparaître un lapin. Tout le monde pensait que le magicien se contentait de sortir un lapin d'un chapeau (une supposition heureuse). Les auteurs ont prouvé que le magicien utilisait en réalité un piège mécanique caché (la logique du polynôme de degré 2) pour faire apparaître le lapin.
Le Résultat : Cela explique pourquoi le tour de l'« Échantillonnage Apparié » a été si efficace pendant des années. Il capturait secrètement ces effets d'« interaction » tout au long du processus, simplement sans le coût mathématique supplémentaire de tracer la courbe.

Qu'Ont-ils Découvert Exactement ?

Meilleure Précision : Lorsqu'ils ont testé PolySHAP sur divers ensembles de données (comme la prédiction des prix de l'immobilier, le diagnostic de maladies ou l'identification d'images), il a constamment fourni des explications plus précises que la méthode standard, surtout lorsqu'ils ont permis aux mathématiques d'examiner des interactions plus complexes (comme des combinaisons de 3 ou 4 caractéristiques).
La Mise à Niveau « Gratuite » : Ils ont montré que si vous utilisez le tour de l'« Échantillonnage Apparié » avec l'ancienne méthode, vous obtenez la même précision que la nouvelle méthode PolySHAP de « 2e degré », mais sans avoir à effectuer le travail supplémentaire d'ajustement de la courbe.
Quand Utiliser Quoi :
- Si vous voulez juste une réponse rapide et décente, l'ancienne méthode avec Échantillonnage Apparié est excellente.
- Si vous avez besoin de la réponse la plus précise et que vous disposez de la puissance de calcul, utiliser PolySHAP avec des courbes de degré supérieur (examinant 3 ou 4 caractéristiques interagissant simultanément) est le gagnant.

Résumé

Le papier présente PolySHAP, une nouvelle façon d'expliquer les décisions de l'IA qui cherche la « travail d'équipe » entre les caractéristiques, et non pas seulement les contributions individuelles. Il prouve qu'un raccourci populaire appelé Échantillonnage Apparié effectuait secrètement le gros du travail de cette nouvelle méthode tout au long du processus. Essentiellement, ils nous ont offert une meilleure carte pour naviguer dans les interactions complexes à l'intérieur des modèles d'IA et expliqué pourquoi une boussole spécifique (Échantillonnage Apparié) pointait dans la bonne direction tout ce temps.

Résumé technique : PolySHAP – Extension de KernelSHAP par régression polynomiale informée par les interactions

Énoncé du problème

Les valeurs de Shapley constituent un outil central de la théorie des jeux en IA explicable (XAI) pour attribuer la prédiction d'un modèle à ses caractéristiques d'entrée. Cependant, le calcul exact des valeurs de Shapley nécessite d'évaluer le modèle sur toutes les $2^d$ sous-ensembles possibles de caractéristiques, ce qui est computationnellement irréalisable pour les modèles comportant un grand nombre de caractéristiques $d$ .

KernelSHAP (Lundberg & Lee, 2017) s'est imposé comme une méthode de premier plan pour approximer efficacement les valeurs de Shapley. Il formule le problème comme une régression des moindres carrés pondérée, en approximating le jeu coopératif $\nu$ par une fonction linéaire ajustée à un échantillon de sous-ensembles aléatoires de caractéristiques. Bien qu'efficace, cette approximation linéaire suppose intrinsèquement l'additivité des caractéristiques, échouant à capturer les interactions non linéaires entre elles. Par conséquent, KernelSHAP peut produire des estimations sous-optimales lorsque le jeu sous-jacent présente des interactions d'ordre supérieur significatives.

Méthodologie : PolySHAP

Les auteurs proposent PolySHAP, une généralisation de KernelSHAP qui approxime le jeu $\nu$ en utilisant des polynômes de degré supérieur plutôt qu'une fonction linéaire. Cette approche modélise explicitement les interactions non linéaires entre les caractéristiques.

Mécanisme central

Représentation informée par les interactions : Au lieu d'ajuster un modèle linéaire $\sum \phi_i \mathbb{1}[i \in S]$ , PolySHAP ajuste un polynôme de degré $k$ sur les indicateurs binaires de caractéristiques $\mathbb{1}[i \in S]$ . L'approximation inclut une « frontière d'interaction » $\mathcal{I}$ , un sous-ensemble de termes d'interaction (sous-ensembles de caractéristiques de taille $\ge 2$ ).
$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$
où $\mathcal{D}$ représente les caractéristiques individuelles et $\mathcal{I}$ représente les termes d'interaction.
Formulation de la régression : PolySHAP résout un problème de moindres carrés pondérés similaire à KernelSHAP, mais avec une matrice de design étendue contenant des colonnes pour les effets principaux et les termes d'interaction sélectionnés. L'objectif minimise la perte $\ell_2$ pondérée entre les valeurs de jeu échantillonnées $\nu(S_\ell)$ et l'approximation polynomiale.
Extraction des valeurs de Shapley : Un résultat théorique clé (Théorème 4.3) démontre que les valeurs de Shapley du jeu original peuvent être récupérées directement à partir des coefficients de l'approximation polynomiale. Plus précisément, la valeur de Shapley pour la caractéristique $i$ est la somme du coefficient de l'effet principal $\phi_i$ et des coefficients de tous les termes d'interaction contenant $i$ , divisée par la taille de ces ensembles d'interaction :
$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$
Stratégies d'échantillonnage : La méthode prend en charge l'échantillonnage standard et l'échantillonnage apparié (échantillonnage de sous-ensembles $S$ et de leurs compléments $D \setminus S$ ). Les auteurs utilisent l'échantillonnage par score de levier pour améliorer la qualité de l'estimation, notant que pour les interactions d'ordre supérieur, les scores de levier d'ordre 1 (uniformes sur les tailles de sous-ensembles) fonctionnent bien en pratique.

Contributions clés

1. Cohérence théorique et extension

L'article démontre que PolySHAP fournit des estimations cohérentes des valeurs de Shapley. À mesure que le nombre d'échantillons $m$ approche le nombre total de sous-ensembles $2^d$ , les estimations PolySHAP convergent exactement vers les vraies valeurs de Shapley (Théorème 4.3). Cela contraste avec certaines méthodes d'approximation basées sur les arbres (par exemple, RegressionMSR) qui nécessitent des étapes supplémentaires de réglage par régression pour atteindre la cohérence.

2. Équivalence théorique entre échantillonnage apparié et 2-PolySHAP

Une contribution théorique majeure est la preuve que KernelSHAP avec échantillonnage apparié est mathématiquement équivalent au 2-PolySHAP (Théorème 5.1).

Lorsque les sous-ensembles sont échantillonnés par paires ( $S$ et $D \setminus S$ ), la solution de régression linéaire de KernelSHAP produit exactement les mêmes approximations de valeurs de Shapley qu'une régression polynomiale d'ordre deux (2-PolySHAP).
Cette découverte fournit la première justification théorique solide du succès empirique de l'échantillonnage apparié, expliquant qu'il capture implicitement toutes les interactions d'ordre deux sans ajuster explicitement un polynôme de degré 2.

3. Performance empirique

Des expériences extensives menées sur 15 jeux d'explication locale (couvrant les domaines tabulaires, image et langage) démontrent que :

Précision d'ordre supérieur : L'augmentation du degré polynomial (par exemple, 3-PolySHAP) améliore systématiquement la qualité de l'approximation (mesurée par MSE, Precision@5 et corrélation de Spearman) par rapport à KernelSHAP (1-PolySHAP) et à l'échantillonnage par permutation, à condition que le budget d'échantillonnage soit suffisant.
Efficacité de l'échantillonnage apparié : Sous échantillonnage apparié, KernelSHAP atteint des performances comparables au 2-PolySHAP, validant l'équivalence théorique.
Résultats de l'état de l'art : Dans des configurations de dimension faible à modérée, PolySHAP (spécifiquement 3-PolySHAP) surpasse souvent d'autres références, y compris RegressionMSR (qui repose sur des approximations XGBoost) et SVARM.

Importance et affirmations

L'article prétend offrir une extension fondée sur des principes du cadre largement utilisé KernelSHAP. En passant d'approximations linéaires à polynomiales, PolySHAP adresse la limitation consistant à ignorer les interactions entre caractéristiques, conduisant à des explications plus précises pour les modèles complexes.

Crucialement, ce travail comble un fossé entre les pratiques heuristiques et la théorie. En prouvant que l'heuristique populaire de « l'échantillonnage apparié » est équivalente à la modélisation des interactions d'ordre deux, les auteurs fournissent une base rigoureuse expliquant pourquoi cette stratégie d'échantillonnage fonctionne si bien en pratique. Les auteurs notent modestement que, bien que les interactions d'ordre supérieur améliorent la précision, elles nécessitent des budgets d'échantillonnage plus importants, et dans des configurations de très haute dimension ( $d \ge 60$ ), les gains sont plus modestes en raison de l'explosion combinatoire des termes d'interaction.

L'article conclut que PolySHAP est une méthode robuste, cohérente et empiriquement supérieure pour l'estimation des valeurs de Shapley, en particulier lorsque le jeu sous-jacent implique des interactions non linéaires entre caractéristiques.