📊 statistics

Proxy-Based Approximation of Shapley and Banzhaf Interactions

Cet article présente ProxySHAP, une méthode novatrice qui combine des modèles proxy basés sur des arbres avec une correction des résidus et un calcul exact en temps polynomial pour les ensembles d'arbres afin d'atteindre une précision et une efficacité de pointe dans l'estimation des interactions de Shapley et de Banzhaf, surpassant nettement les estimateurs existants tels que ProxySPEX et KernelSHAP-IQ.

Auteurs originaux : Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli

Publié 2026-05-22

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli

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 possédez une machine complexe, comme une intelligence artificielle sophistiquée qui décide si un prêt doit être approuvé ou qui prédit la météo. Vous voulez savoir pourquoi elle a pris une décision spécifique. S'est-elle appuyée principalement sur le revenu du demandeur ? Était-ce le score de crédit ? Ou s'agissait-il d'une combinaison étrange des deux ?

Dans le monde de l'IA, nous utilisons les mathématiques pour décomposer ces décisions en « contributions ». La méthode la plus célèbre s'appelle les valeurs de Shapley (du nom d'un économiste lauréat du prix Nobel). Pensez-y comme à un projet d'équipe : si l'équipe réussit, quel crédit chaque personne mérite-t-elle ?

Mais voici le problème : les modèles d'IA modernes sont si complexes qu'ils ne reposent pas uniquement sur des facteurs isolés. Ils reposent sur des interactions. Peut-être que l'IA n'approuve le prêt que si le revenu est élevé ET que le score de crédit est élevé. Si vous les examinez séparément, ils semblent faibles. Si vous les examinez ensemble, ils sont puissants.

Calculer ces interactions de « collaboration » est incroyablement difficile. C'est comme essayer de compter chaque combinaison possible de joueurs dans une équipe sportive pour voir qui gagne. Pour une petite équipe, c'est facile. Pour une équipe de 1 000 joueurs (ce qui est courant en IA), le nombre de combinaisons est si énorme que même les supercalculateurs les plus rapides mettraient plus de temps que l'âge de l'univers pour le calculer exactement.

Le Problème : Vitesse contre Précision

Les scientifiques ont tenté de résoudre ce problème avec deux approches principales, mais toutes deux présentent des défauts :

La méthode de « devinette » : Vous prenez quelques échantillons aléatoires et vous devinez le reste. C'est rapide, mais souvent imprécis. C'est comme essayer de deviner le goût d'une gigantesque soupe en goûtant une seule cuillère.
La méthode « exacte » : Vous essayez de tout calculer avec précision. C'est précis, mais si lent qu'il est inutile pour les grands problèmes.

La Solution : ProxySHAP

Les auteurs de cet article introduisent une nouvelle méthode appelée ProxySHAP. Imaginez-la comme une stratégie de détective astucieuse en deux étapes qui offre le meilleur des deux mondes.

Étape 1 : Le « Dessinateur de croquis » (Le Proxy)

D'abord, l'IA jette un coup d'œil à la machine complexe et dessine un croquis simplifié de celle-ci. Ce croquis est un modèle « proxy ».

Analogie : Imaginez un chef étoilé (l'IA complexe) qui prépare un ragoût à 100 ingrédients. Au lieu d'essayer de goûter chaque ingrédient individuellement dans la gigantesque marmite, le chef prépare rapidement une petite soupe simple qui ressemble beaucoup au grand ragoût.
L'astuce : Les auteurs utilisent un type spécifique de croquis (un modèle « basé sur des arbres », comme un organigramme) qui est facile à analyser. Parce que le croquis est simple, ils peuvent instantanément calculer exactement comment les ingrédients interagissent sans effectuer les mathématiques impossibles sur le grand ragoût.

Étape 2 : La « Correction » (Le Résidu)

Le croquis n'est pas parfait. Il est proche, mais il manque quelques détails minuscules.

Analogie : La petite soupe ressemble à 95 % au grand ragoût, mais peut-être qu'il manque une pincée de sel ou une pointe d'épice.
La solution : La méthode examine ensuite la différence (le « résidu ») entre le vrai ragoût et le croquis. Elle utilise une technique d'échantillonnage intelligente pour estimer uniquement ces détails manquants.
L'innovation : L'article montre que pour les interactions très complexes (comme 3 ou 4 ingrédients travaillant ensemble), essayer de « corriger » le croquis par un échantillonnage aléatoire peut en fait empirer les choses (comme ajouter trop de sel). Ainsi, ProxySHAP est assez intelligente pour savoir quand appliquer la correction et quand se fier simplement au croquis.

Pourquoi cela compte

L'article affirme que ProxySHAP est le nouveau « standard d'or » pour trois raisons :

C'est rapide : Il peut gérer des modèles d'IA avec des milliers de caractéristiques (ingrédients) dans un délai raisonnable.
C'est précis : Il est beaucoup plus précis que les anciennes méthodes de « devinette », surtout lorsque vous n'avez pas un énorme budget de temps de calcul.
C'est polyvalent : Il fonctionne sur différents types d'IA, de celles qui analysent des images et du texte (comme reconnaître une girafe dans une rivière) à celles qui prédisent les risques financiers.

La Conclusion

Avant cela, si vous vouliez comprendre comment une IA complexe prenait une décision impliquant de nombreux facteurs interactifs, vous deviez choisir entre une réponse rapide et bâclée ou une réponse lente et impossible. ProxySHAP vous offre une réponse rapide et hautement précise en utilisant une stratégie intelligente de « croquis et correction ». C'est comme avoir un chef étoilé qui peut vous dire instantanément exactement quels ingrédients ont rendu le plat délicieux, même si la recette comporte des milliers d'étapes.

Résumé Technique : Approximation par Proxy des Interactions de Shapley et de Banzhaf

Énoncé du Problème
Les applications modernes d'apprentissage automatique reposent de plus en plus sur la théorie des jeux coopératifs pour interpréter le comportement des modèles, en utilisant spécifiquement les valeurs de Shapley et de Banzhaf pour attribuer les contributions aux caractéristiques individuelles. Cependant, la compréhension de dynamiques complexes et non linéaires nécessite souvent l'analyse d'interactions d'ordre supérieur (sous-ensembles de caractéristiques) plutôt que de simples effets singuliers. Le calcul exact des indices d'interaction cardinaux-probabilistes est intraitable sur le plan computationnel pour un grand nombre de caractéristiques ( $n$ ) en raison de la croissance exponentielle de l'espace des coalitions ( $2^n$ ).

Les estimateurs existants font face à un compromis critique entre vitesse et précision :

Les méthodes basées sur l'échantillonnage (par exemple, SHAP-IQ, KernelSHAP-IQ) sont souvent précises mais nécessitent des budgets d'échantillonnage impraticables pour ajuster le grand nombre de termes d'ordre supérieur, souffrant d'une variance élevée qui s'aggrave avec l'ordre de l'interaction.
Les méthodes basées sur des proxies (par exemple, ProxySPEX) offrent de la rapidité mais reposent sur une extraction basée sur Fourier à partir de surrogates arborescents. Cette approche souffre d'une complexité exponentielle par rapport à la profondeur de l'arbre et nécessite souvent un tronquage agressif qui compromet la précision. De plus, les méthodes par proxy existantes retournent généralement les interactions du proxy plutôt que celles de la fonction de valeur sous-jacente, introduisant un biais.

Méthodologie : ProxySHAP
Les auteurs proposent ProxySHAP, un cadre qui concilie l'efficacité d'échantillonnage des modèles proxy basés sur des arbres avec une voie fondée sur des principes vers la cohérence via une correction des résidus. La méthode décompose l'indice d'interaction cible $\phi^p_S(\nu)$ en deux composantes :
$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Proxy Exact}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Résidu}}$

Ajustement du Proxy (Phase 1) : Un modèle basé sur des arbres (par exemple, XGBoost, LightGBM) ou un modèle linéaire avec des caractéristiques d'interaction est entraîné sur des coalitions échantillonnées pour approximer la fonction de valeur sous-jacente $\nu$ .
Extraction Exacte du Proxy (Phase 2) : Contrairement aux méthodes précédentes qui extraient des coefficients de Fourier, ProxySHAP introduit une généralisation en temps polynomial de TreeSHAP interventionnel. Cela permet le calcul exact de n'importe quel indice d'interaction cardinaux-probabiliste (y compris Shapley et Banzhaf) directement à partir de la structure de l'arbre.
- La méthode exploite la représentation de Möbius des jeux d'indicateurs définis par les feuilles de l'arbre.
- Elle évite la complexité exponentielle $O(4^d)$ de l'extraction basée sur Fourier (où $d$ est la profondeur de l'arbre), atteignant un temps d'exécution de $O(n_{nodes})$ par interaction.
Ajustement des Résidus : Pour corriger le biais introduit par le proxy ne correspondant pas parfaitement à $\nu$ $ν$ , la méthode estime les interactions du jeu résiduel $(\nu - \hat{\nu}_T)$ $(ν - \overset{ν}{^}_{T})$ en utilisant le Rééchantillonnage Maximum (MSR).
- L'article fournit une analyse théorique montrant que la variance de l'estimateur MSR pour les interactions d'ordre $k$ évolue comme $O(n^{k-1}/|T|)$ .
- Par conséquent, les auteurs dérivent les conditions dans lesquelles l'ajustement MSR est bénéfique : principalement pour des environnements de faible dimension ( $n < 30$ ) ou lorsque le budget d'échantillonnage $|T|$ est suffisamment grand par rapport à $n^{k-1}$ . Pour les interactions d'ordre élevé dans de grands jeux, la variance de la correction peut l'emporter sur la réduction du biais.

Contributions Clés

Cadre ProxySHAP : Une stratégie d'estimation novatrice qui combine un proxy basé sur des arbres avec une correction des résidus, permettant une approximation efficace et précise des interactions d'ordre supérieur.
Avancement Théorique :
- Dérivation d'un algorithme en temps polynomial sous forme fermée pour extraire les indices d'interaction cardinaux-probabilistes exacts à partir d'ensembles d'arbres, contournant la dépendance exponentielle à la profondeur des méthodes Fourier antérieures.
- Caractérisation formelle de la croissance de la variance du MSR pour les interactions d'ordre supérieur, établissant des conditions explicites (en termes de $n$ , de budget et d'ordre d'interaction $k$ ) sous lesquelles l'ajustement des résidus améliore ou dégrade les performances.
Performances Empiriques : Des benchmarks extensifs sur 47 jeux de données (tableaux, vision, langage, graphes et vision-langage) démontrent que ProxySHAP établit une nouvelle référence de l'état de l'art. Il atteint l'erreur la plus faible à la fois dans les régimes à petit budget (où il surpasse ProxySPEX) et dans les régimes à grand budget (où il surpasse KernelSHAP-IQ).

Résultats

Précision : ProxySHAP surpasse systématiquement les lignes de base (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) en termes d'Erreur Quadratique Moyenne Relative (MSE). Dans les applications à grande échelle avec des milliers de caractéristiques (par exemple, Bioresponse avec $n=1776$ ), ProxySHAP reste efficace là où d'autres méthodes deviennent computationnellement infeasibles ou imprécises.
Efficacité : L'algorithme d'extraction en temps polynomial offre des accélérations de plusieurs ordres de grandeur (10x à 1000x) par rapport à l'extraction basée sur Fourier, particulièrement lorsque la profondeur de l'arbre augmente.
Tâches en Aval : Dans une application spécifique à l'explication du modèle vision-langage SigLIP-2 (jeu FIxLIP), ProxySHAP a démontré une fidélité supérieure (mesurée par la surface sous la courbe d'insertion-suppression) par rapport aux lignes de base de régression linéaire et à ProxySPEX.
Sensibilité aux Hyperparamètres : L'étude met en évidence que la qualité du proxy est critique. L'optimisation des hyperparamètres (HPO) améliore considérablement les performances, et une configuration par défaut "informée par HPO" (utilisant de nombreux arbres peu profonds) est proposée pour équilibrer coût et précision.

Signification et Revendications
L'article revendique que ProxySHAP résout le compromis de longue date entre vitesse et précision dans l'estimation des interactions. En fournissant un mécanisme d'extraction exact pour les proxies arborescents et une stratégie théoriquement fondée pour la correction des résidus, il permet la quantification évolutive des dépendances complexes dans les systèmes d'IA modernes. Les auteurs soulignent que leur méthode est particulièrement précieuse pour :

Les applications à grande échelle : La gestion de jeux de données comportant des milliers de caractéristiques où le calcul exact est impossible.
Les interactions d'ordre supérieur : La fourniture d'estimations fiables pour les interactions au-delà des effets binaires, cruciales pour comprendre les dépendances inter-modales (par exemple, dans les modèles vision-langage) et les synergies complexes de caractéristiques.
Le déploiement pratique : L'offre d'un estimateur "de l'état de l'art" robuste face à des contraintes budgétaires variables et à des types de modèles, soutenu par une implémentation C++ évolutive.

Les auteurs notent modestement des limitations, spécifiquement que la qualité de l'approximation dépend du proxy ajusté (nécessitant un réglage attentif des hyperparamètres) et que la variance de la correction des résidus limite son utilité dans des environnements de très haute dimension pour les interactions d'ordre élevé. Des travaux futurs sont suggérés pour explorer d'autres classes de proxies et estimateurs de résidus qui évoluent plus gracieusement.