🤖 machine learning

Tractable Shapley Values and Interactions via Tensor Networks

Cet article introduit TN-SHAP, une méthode basée sur les réseaux de tenseurs qui approxime les valeurs de Shapley et les indices d'interaction avec une complexité polynomiale en remplaçant l'énumération exhaustive des coalitions par une application multilinéaire factorisée, atteignant ainsi des accélérations significatives par rapport aux approches existantes tout en maintenant la précision.

Auteurs originaux : Farzaneh Heidari, Chao Li, Guillaume Rabusseau

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Farzaneh Heidari, Chao Li, Guillaume Rabusseau

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 un modèle d'IA sophistiqué) qui fait des prédictions. Vous voulez savoir : « Quels boutons et curseurs spécifiques (caractéristiques) ont causé cette prédiction précise, et comment ont-ils fonctionné ensemble ? »

Dans le monde de l'IA, on appelle cela les Valeurs de Shapley. C'est une façon de répartir équitablement le « crédit » d'une prédiction entre toutes les caractéristiques d'entrée.

Cependant, il existe un problème massif avec la méthode traditionnelle : elle est trop lente.

L'ancienne méthode : Le problème du « pot de cookies »

Imaginez que vous avez un bocal contenant 50 types différents de cookies (caractéristiques). Pour déterminer exactement la contribution de chaque cookie au goût final d'une fournée, l'ancienne méthode dit que vous devez goûter chaque combinaison possible de cookies.

Avec 10 cookies, cela fait 1 024 combinaisons.
Avec 50 cookies, cela fait plus de combinaisons qu'il n'y a d'atomes dans l'univers ( $2^{50}$ ).

Essayer de goûter chaque combinaison est impossible. Cela prend une éternité, donc nous nous contentons généralement de deviner ou de goûter quelques poignées au hasard, ce qui n'est pas très précis.

La nouvelle méthode : TN-SHAP (La « Carte de Recette Magique »)

Le document présente une nouvelle méthode appelée TN-SHAP. Au lieu de goûter chaque combinaison possible de cookies, elle utilise une astuce ingénieuse impliquant des réseaux de tenseurs (un type de structure mathématique) et des polynômes (des courbes mathématiques).

Voici l'analogie :

1. La « Carte de Recette Magique » (Le Substitut)

D'abord, la méthode crée une version simplifiée et « magique » de la machine complexe. Considérez cela comme une carte de recette qui imite parfaitement le comportement de la machine, mais de manière très structurée et organisée.

Le document appelle cela un Substitut par Réseau de Tenseurs (Tensor Network Surrogate).
Il décompose la machine complexe en une série de blocs plus petits et connectés (comme une chaîne de briques Lego). Cette structure est efficace et facile à lire.

2. L L'astuce du « Curseur » (Les Sélecteurs Diagonaux)

Au lieu de tester chaque combinaison de cookies, la méthode utilise un curseur spécial (un outil mathématique appelé matrice de sélection).

Imaginez que vous avez un cadran qui contrôle la quantité de chaque cookie dans le mélange.
Vous tournez le cadran vers la position 0 (pas de cookie), la position 0,5 (demi-cookie), la position 1 (cookie entier), etc.
Parce que la « Carte de Recette Magique » est construite d'une manière mathématique spéciale (appelée multilinéaire), tourner ce cadran crée une courbe fluide (un polynôme) qui révèle toutes les informations sur la façon dont les cookies interagissent en une seule fois.

3. Le « Détective Mathématique » (L'Interpolation Polynomiale)

Au lieu de goûter 1 000 000 de combinaisons, la méthode n'a besoin de goûter que 50 points spécifiques sur la courbe de ce cadran.

Elle prend ces 50 points et utilise une technique mathématique standard (appelée interpolation polynomiale) pour reconstruire la courbe entière.
Une fois qu'elle possède la courbe, elle peut calculer instantanément exactement quel crédit chaque cookie (et chaque groupe de cookies) mérite.

Pourquoi est-ce une avancée majeure ?

Le document revendique trois victoires majeures :

Vitesse :
- Ancienne méthode : Prend un temps exponentiel. Si vous ajoutez une caractéristique, le temps double. Pour 50 caractéristiques, cela pourrait prendre des années.
- TN-SHAP : Prend un temps linéaire. Elle évolue de manière progressive. Pour 50 caractéristiques, cela prend des millisecondes.
- Le résultat : Le document montre qu'elle est 25 à 1 000 fois plus rapide que les meilleures méthodes actuelles (comme KernelSHAP-IQ) tout en conservant le même niveau de précision.
Précision :
- Parce qu'elle ne repose pas sur des suppositions aléatoires (échantillonnage), elle obtient la réponse exacte pour la « Carte de Recette Magique ».
- Le document prouve que si la « Carte de Recette Magique » est une bonne copie de la vraie machine, l'explication sera très proche de la vérité.
Crédit de Groupe (Interactions) :
- Elle ne vous dit pas seulement quel cookie individuel est important. Elle vous dit comment des groupes de cookies travaillent ensemble (par exemple : « Le chocolat et la vanille se marient très bien, mais le chocolat et le sel sont mauvais ensemble »).
- Elle peut calculer ces interactions de groupe aussi rapidement que les caractéristiques individuelles.

Le revers de la médaille (Limites)

Le document est honnête sur les cas où cela fonctionne le mieux :

Voisinages Locaux : La « Carte de Recette Magique » est construite pour une zone spécifique. Si vous interrogez la machine sur une combinaison de cookies qu'elle n'a jamais vue auparavant, la carte pourrait ne pas être parfaite. La méthode fonctionne mieux lorsque vous examinez une prédiction spécifique et ses voisins immédiats.
Complexité : Si la machine est extrêmement chaotique et ne possède pas de motif structuré, la « Carte de Recette Magique » pourrait devoir être immense pour être précise. Cependant, le document a constaté que même pour des données réelles complexes (comme prédire le diabète ou la résistance du béton), une carte relativement petite fonctionnait parfaitement.

Résumé

TN-SHAP est comme engager un chef étoilé qui n'a pas besoin de cuisiner chaque plat possible pour connaître la recette. Au lieu de cela, il examine les ingrédients, utilise un raccourci mathématique spécial pour comprendre le profil de saveur, et vous indique instantanément quels ingrédients font le plus gros du travail et lesquels travaillent ensemble. Il transforme une tâche qui prenait autrefois des années en une tâche qui ne prend qu'un clin d'œil.

Résumé Technique : Valeurs de Shapley et Interactions Tractables via les Réseaux de Tenseurs

Énoncé du Problème

Expliquer les prédictions de l'apprentissage automatique via les valeurs de Shapley et leurs généralisations d'ordre supérieur (Indices d'Interaction de Shapley, SII) est fondamental pour le support à la décision et l'interprétabilité. Cependant, le calcul de ces indices est extrêmement coûteux pour des modèles possédant $n$ caractéristiques, car cela nécessite traditionnellement l'énumération de $O(2^n)$ coalitions. Les solutions existantes font face à des compromis importants :

Hypothèses Structurelles : Des méthodes comme TreeSHAP ou celles destinées aux Modèles Additifs Généralisés (GAM) ne sont exactes que pour des architectures spécifiques (ex: arbres, modèles linéaires).
Approximations par Échantillonnage : Les approches comme KernelSHAP ou SHAP-IQ reposent sur un échantillonnage intensif, nécessitant un réglage délicat de la variance et échouant souvent à passer à l'échelle pour les interactions d'ordre supérieur sans des coûts de calcul massifs.
Estimation Amortie : Les méthodes qui entraînent des modèles auxiliaires entraînent souvent un surcoût d'entraînement significatif et peuvent manquer de garanties théoriques sur la fidélité de l'explication.

Le défi central est de calculer les valeurs de Shapley et les interactions de manière exacte (ou avec une erreur contrôlée) pour des prédicteurs généraux sans énumération exponentielle ni échantillonnage excessif.

Méthodologie : TN-SHAP

Les auteurs proposent TN-SHAP, une méthode qui remplace l'énumération exhaustive des coalitions par un schéma de quelques évaluations sur un surrogat de Réseau de Tenseurs (TN). L'approche tire parti de trois idées clés pour réduire la complexité de $O(2^n)$ à $O(n \cdot \text{poly}(\chi))$ , où $\chi$ est la dimension de liaison maximale du réseau de tenseurs.

1. Représentation Multilinéaire et Extraction de Coefficients

La méthode suppose que le prédicteur $f$ peut être bien approximé par une fonction multilinéaire $g$ dans un espace de caractéristiques élevé (lifted space). Dans une expansion multilinéaire, $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$ , les valeurs de coalition correspondent à des combinaisons linéaires de coefficients de tenseurs. Crucialement, les valeurs de Shapley dépendent uniquement des contributions marginales agrégées par taille (sommes des contributions pour des coalitions de taille $s$ ), plutôt que des appartenances spécifiques aux coalitions.

2. Sélecteurs Diagonaux et Interpolation Polynomiale

Au lieu de requêter $2^n$ coalitions, TN-SHAP utilise des matrices de sélection diagonale $S_r(t) = \text{Diag}(t, 1)$ appliquées aux caractéristiques élevées $\tilde{x}_r = [\phi(x_r), 1]^\top$ .

En évaluant le surrugat $g$ en des points où les caractéristiques sont mises à l'échelle par un paramètre $t$ , la méthode agrège toutes les coalitions de taille $s$ dans le coefficient de $t^s$ d'un polynôme résultant $P(t)$ .
Plus précisément, pour une caractéristique cible $i$ , une fonction de sonde $G_i(t)$ est construite pour isoler la contribution marginale de $i$ à travers tous les sous-ensembles des autres caractéristiques.
Cela transforme le problème combinatoire en une interpolation polynomiale. En évaluant $G_i(t)$ en $n$ points distincts (par exemple, des nœuds de Chebyshev-Gauss), le système résout un système linéaire de Vandermonde pour récupérer les contributions marginales agrégées par taille $\{m_s^{(i)}\}$ .
La valeur de Shapley est ensuite calculée comme une somme pondérée de ces coefficients récupérés.

3. Surrogats de Réseaux de Tenseurs

Pour rendre l'évaluation de la carte multilinéaire traitable à grande échelle, le tenseur de coefficients est factorisé en un Réseau de Tenseurs (TN) (par exemple, Tensor Train ou Arbre Hiérarchique) avec une dimension de liaison $\chi$ .

Cartes de Caractéristiques (Feature Maps) : Pour gérer des données réelles non linéaires, les caractéristiques scalaires sont élevées via des cartes $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ apprises ou artisanales avant d'entrer dans le TN. Cela préserve la multilinéarité dans l'espace élevé tout en permettant au surrugat de modéliser les non-linéarités dans l'espace d'entrée original.
Efficacité : Chaque passage avant (forward pass) à travers le TN coûte $O(\text{poly}(\chi))$ . Puisque seulement $O(n)$ évaluations sont nécessaires pour l'interpolation, la complexité totale pour calculer les interactions d'ordre $k$ devient polynomiale en $n$ .

Contributions Clés

Schéma de Sonde-Interpolation Unifié : Un algorithme exact pour calculer les valeurs de Shapley et les interactions de $k$ voies sur un surrugat multilinéaire TN utilisant uniquement $O(n)$ passages avant structurés, évitant ainsi $O(2^n)$ requêtes.
Surrogats Améliorés par Cartes de Caractéristiques : Un cadre démontrant comment les élévations de caractéristiques apprises préservent la multilinéarité requise pour un calcul exact tout en améliorant la fidélité du surrugat pour les modèles non linéaires.
Garanties Théoriques :
- Exactitude : La méthode calcule exactement les valeurs de Shapley sur le surrugat multilinéaire ajusté.
- Erreur d'Approximation : L'erreur par rapport au modèle original est bornée par l'erreur d'approximation de coalition la plus défavorable du surrugat ( $\epsilon$ ). Pour les valeurs de Shapley, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$ .
- Tractabilité : Réduction prouvée de la complexité temporelle de l'exponentiel au polynomial $O(n \cdot \text{poly}(\chi) + n^2)$ .

Résultats Expérimentaux

Les auteurs ont évalué TN-SHAP sur des fonctions multilinéaires synthétiques et des jeux de données de régression UCI réels (Concrete, Diabetes, Energy) en utilisant des enseignants MLP (Perceptron Multicouche).

Validation Synthétique : Sur des fonctions exactement multilinéaires, TN-SHAP a atteint l'exactitude théorique avec des temps d'exécution de l'ordre de la milliseconde, surpassant KernelSHAP-IQ de plusieurs ordres de grandeur (ex: 3,5 ms contre 18,7 ms pour $n=10$ ; 19,7 ms contre 447,3 ms pour $n=50$ ).
Précision sur le Monde Réel : Sur les jeux de données UCI avec des enseignants MLP :
- TN-SHAP a obtenu des accélérations de 25 à 1000× en temps de calcul réel par rapport à KernelSHAP-IQ pour une précision comparable.
- Pour les attributions de premier ordre ( $k=1$ ), TN-SHAP a atteint une similitude cosinus quasi parfaite (0,994) avec la vérité terrain.
- Pour les interactions d'ordre supérieur ( $k=2, 3$ ), TN-SHAP a maintenu une précision compétitive tandis que les bases par échantillonnage luttaient avec la variance ou nécessitaient beaucoup plus de calcul pour atteindre une fidélité similaire.
Ablation de Rang : Les expériences ont montré qu'un rang étudiant de TN de $r=5-6$ était suffisant pour récupérer toutes les ordres d'interaction avec un $R^2 > 0,99$ lorsque l'enseignant avait un rang de 16. Les rangs plus faibles sous-ajustent les interactions d'ordre supérieur.
Stabilité de Haute Dimension : Dans des contextes synthétiques de haute dimension ( $D=50, 100$ ), TN-SHAP a maintenu une forte fidélité du surrugat ( $R^2 > 0,95$ ) et une forte récupération des caractéristiques Top- $k$ sous des budgets de requêtes à coût linéaire.

Signification et Revendications

L'article affirme que TN-SHAP comble le fossé entre la rigueur théorique du calcul exact de Shapley et la nécessité pratique de l'efficacité. En exploitant la structure algébrique des fonctions multilinéaires et l'efficacité des réseaux de tenseurs, la méthode :

Transforme un problème d'énumération exponentielle en un petit nombre d'évaluations structurées.
Fournit des garanties structurelles (via les bornes de rang) qui répondent aux problèmes de fidélité courants dans les méthodes de surrugat local non contraintes comme LIME.
Unifie les explications de Shapley locales avec les structures additives globales (GAM), car l'ajustement d'un surrugat d'ordre $k$ produit des coefficients $k$ -SII exacts correspondant aux termes GAM correspondants.
Offre une alternative scalable aux méthodes par échantillonnage, particulièrement pour les interactions d'ordre supérieur où la variance de l'échantillonnage est typiquement élevée.

Les auteurs notent que la performance de la méthode dépend de la qualité de l'ajustement du surrugat TN et du choix des cartes de caractéristiques, mais les résultats empiriques suggèrent que même des élévations de caractéristiques modestes et des rangs de tenseurs raisonnables sont suffisants pour capturer des structures de coalition complexes en pratique.