📊 statistics

An Odd Estimator for Shapley Values

Cet article introduit OddSHAP, un nouvel estimateur de la valeur de Shapley qui atteint une précision de pointe en prouvant théoriquement que l'échantillonnage par paires élimine les composantes paires non pertinentes de la fonction d'ensemble, permettant ainsi une régression polynomiale efficace uniquement sur le sous-espace impair.

Auteurs originaux : Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

Publié 2026-06-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

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 voiture autonome ou un outil de diagnostic médical, et qu'elle prenne une décision. Vous voulez savoir : quelles parties spécifiques (caractéristiques) de l'entrée ont été responsables de cette décision ?

Dans le monde de l'apprentissage automatique (machine learning), la « valeur de Shapley » est l'outil mathématique de référence utilisé pour répondre à cette question. Elle répartit équitablement le « crédit » d'une décision entre toutes les caractéristiques d'entrée. Cependant, calculer la valeur de Shapley exacte revient à essayer de compter chaque grain de sable sur une plage pour voir quelle part de chaque grain a contribué au poids total. C'est mathématiquement possible, mais informatiquement impossible pour des problèmes complexes car il y a trop de combinaisons à vérifier.

Cet article présente une nouvelle façon plus intelligente d'estimer ces valeurs, appelée OddSHAP. Voici comment cela fonctionne, expliqué par des analogies simples.

1. Le problème : Le piège des « trop nombreuses combinaisons »

Pour déterminer l'importance d'une caractéristique, il faut généralement tester la machine avec toutes les mélanges possibles de caractéristiques activées et désactivées.

L'ancienne méthode : Imaginez que vous essayez de deviner la saveur d'une soupe en goûtant toutes les combinaisons possibles d'ingrédients. Si vous avez 100 ingrédients, le nombre de combinaisons est astronomique. Vous ne pouvez pas tous les goûter.
La meilleure méthode actuelle : Les scientifiques utilisent une astuce appelée « échantillonnage par paires » (paired sampling). Au lieu de goûter un bol de soupe au hasard, ils goûtent un bol et son exact opposé (tout ce qui manque est ajouté, tout ce qui est ajouté est retiré). Cela aide à annuler une partie du bruit, mais personne ne savait pourquoi cela fonctionnait si bien jusqu'à présent.

2. La grande découverte : Le secret de l'« Impair » (Odd)

Les auteurs de cet article ont découvert une règle mathématique fondamentale : la valeur de Shapley ne s'intéresse qu'aux parties « impaires » (odd) de l'histoire.

Considérez une fonction de valeur (la logique de la machine) comme une chanson. Cette chanson possède deux types de notes :

Notes Paires (Even) : Elles sont symétriques. Si vous retournez la chanson, elle sonne de la même manière. En termes mathématiques, ce sont des motifs qui s'annulent lors du calcul des valeurs de Shapley. Elles sont un « bruit non pertinent » pour ce calcul spécifique.
Notes Impaires (Odd) : Elles sont asymétriques. Si vous les retournez, elles changent. Ce sont les seules notes qui comptent réellement pour la valeur de Shapli.

L'analogie : Imaginez que vous essayiez de mesurer le poids d'une personne spécifique debout sur une balance, mais que la balance pèse également un nuage de brouillard symétrique et géant qui l'entoure. Le brouillard est lourd, mais il est parfaitement équilibré (pair), donc il ne pousse pas la balance davantage à gauche ou à droite. L'intuition d'« OddSHAP » est de réaliser que vous pouvez simplement ignorer le brouillard et vous concentrer uniquement sur la personne.

3. La solution : OddSHAP

Les auteurs ont construit un nouvel estimateur appelé OddSHAP qui utilise cette intuition « Impair vs Pair » pour gagner du temps et améliorer la précision.

Comment ça marche : Au lieu d'essayer d'apprendre toute la chanson (toute la logique de la machine), OddSHAP utilise une astuce d'échantillonnage intelligente (l'échantillonnage par paires) pour filtrer automatiquement les notes « Paires ». Il construit ensuite un modèle en utilisant uniquement les notes « Impaires ».
L'astuce du proxy : Pour trouver les notes « Impaires » les plus importantes sans toutes les vérifier, il utilise un modèle « proxy » (un arbre de décision rapide et simple) pour agir comme un éclaireur. L'éclaireur identifie rapidement les quelques interactions à fort impact (les notes « Impares » les plus fortes) et ignore le reste.
Le résultat : Il résout un problème mathématique beaucoup plus petit. C'est comme essayer de résoudre un puzzle en ne regardant que les pièces qui ont une forme unique, en ignorant les milliers de pièces carrées identiques qui n'aident pas à résoudre l'image.

4. Pourquoi est-ce meilleur ?

L'article a testé cette méthode par rapport à de nombreuses autres méthodes de haut niveau sur divers ensembles de données (comme la prédiction des prix de l'immobilier, le diagnostic du cancer ou l'analyse de texte).

Précision : Lorsqu'on lui donne suffisamment de données (un grand « budget »), OddSHAP est la méthode la plus précise disponible. Elle bat les meilleures méthodes précédentes, en particulier pour les modèles de deep learning complexes (comme ceux utilisés pour la reconnaissance d'images).
Efficacité : Elle évite l'« explosion combinatoire ». Alors que d'autres méthodes s'embourbent en essayant de calculer trop de combinaisons, OddSHAP va droit aux plus pertinentes.
Explication du mystère : L'article explique enfin pourquoi l'ancienne astuce de l'« échantillonnage par paires » fonctionnait si bien. Il s'avère que l'appariement des échantillons faisait exactement ce que fait OddSHAP de manière intentionnelle : cela annule mathématiquement le bruit « Pair », ne laissant que le signal utile « Impair ».

Résumé

OddSHAP est un nouvel outil pour expliquer les décisions de l'IA. Il réalise que pour comprendre pourquoi une décision a été prise, il n'est pas nécessaire d'analyser tous les scénarios possibles. Il suffit d'analyser les motifs asymétriques spécifiques qui pilotent réellement le résultat. En ignorant le « bruit » symétrique, il calcule la réponse plus rapidement et plus précisément que jamais auparavant.

Note sur les limites : L'article note que, bien que cette méthode soit excellente pour les modèles de deep learning complexes, elle est légèrement moins efficace que certaines méthodes plus anciennes et rigides lorsqu'elle traite des modèles basés sur des arbres simples (comme les arbres de décision standards) où le « bruit » est naturellement très faible. Cependant, pour les problèmes larges et complexes où l'IA est la plus mystérieuse, OddSHAP est le nouveau standard de pointe (state-of-the-art).

Résumé Technique : Un Estimateur Impair pour les Valeurs de Shapley

Énoncé du Problème

La valeur de Shapley est le cadre standard pour l'attribution en apprentissage automatique, utilisé pour l'importance des caractéristiques, la valorisation des données et l'inférence causale. Cependant, son calcul exact est généralement intraitable en raison du nombre exponentiel de coalitions ( $2^d$ ) requises pour l'évaluation. Bien que des méthodes d'approximation existent, les estimateurs les plus efficaces reposent souvent sur l'« échantillonnage par paires » (échantillonner une coalition $S$ et son complémentaire $S^c$ ), un heuristique qui améliore empiriquement la précision mais qui manque de justification théorique rigoureuse quant à la raison de son efficacité, particulièrement concernant les interactions d'ordre supérieur. De plus, les méthodes existantes de régression polynomiale d'ordre supérieur (par exemple, PolySHAP) font face à un goulot d'étranglement de scalabilité où le coût computationnel croît de manière quadratique avec la taille de la base polynomiale, limitant leur application dans des contextes de haute dimension.

Méthodologie

Les auteurs proposent OddSHAP, un nouvel estimateur qui exploite une propriété structurelle fondamentale de la valeur de Shapley : elle dépend exclusivement de la composante impaire de la fonction de valeur $f$ .

Fondement Théorique

Décomposition Impair-Pair : Toute fonction d'ensemble $f$ peut être décomposée de manière unique en une composante impaire ( $f_{odd}$ ) et une composante paire ( $f_{even}$ ), où $f_{odd}(S) = -f_{odd}(S^c)$ et $f_{even}(S) = f_{even}(S^c)$ .
Propriété de la Valeur de Shapley : Les auteurs prouvent que $\phi_i(f) = \phi_i(f_{odd})$ pour tous les joueurs $i$ . La composante paire contribue de manière nulle à la valeur de Shapley.
Mécanisme d'Échantillonnage par Paires : L'article fournit la première justification théorique générale de l'échantillonnage par paires. En échantillonnant des paires $(S, S^c)$ avec des poids symétriques, le problème de régression par moindres carrés pondérés se orthogonalise (se découple) en problèmes d'optimisation indépendants pour les composantes impaire et paire. Puisque la composante paire est non pertinente, l'échantillonnage par paires isole efficacement le signal requis pour les valeurs de Shapley. Cela résout une conjecture selon laquelle l'échantillonnage par paires avec un ajustement d'ordre- $k$ (pour un $k$ impair) est équivalent à un ajustement d'ordre- $(k+1)$ .
Conception de l'Algorithme : OddSHAP
Pour exploiter cette intuition tout en évitant l'explosion combinatoire de l'ajustement de tous les termes d'ordre supérieur, OddSHAP opère dans la base de Fourier plutôt que dans la base d'unanimité.
- Avantage de la Base de Fourier : Dans la base de Fourier, une fonction de base $\chi_T$ est impaire si et seulement si la cardinalité $|T|$ est impaire. Cela permet une séparation nette des termes impairs et pairs, contrairement à la base d'unanimité.
- **Processus en Deux Étapes :
  1. Écran d'Interaction : Un modèle proxy basé sur un arbre de boosting de gradient (GBT) est ajusté aux coalitions échantillonnées. En utilisant une méthode telle que ProxySPEX, l'algorithme extrait un ensemble creux de coefficients de Fourier d'ordre impair à fort impact. Cela évite d'ajuster toutes les interactions possibles.
  2. Régression Impaire : Une régression par moindres carrés pondérés est effectuée strictement sur les termes de Fourier d'ordre impair sélectionnés (plus les termes linéaires), sous la contrainte de correspondre à la fonction de valeur sur les ensembles vide et complet.
- Efficacité : En restreignant la régression au sous-espace impair et en utilisant un proxy pour sélectionner les termes, la méthode atteint une complexité temporelle polynomiale par rapport au budget d'échantillonnage, contournant l'échelle $O(d^k)$ des méthodes polynomiales à ordre fixe.

Contributions Clés

Unification Théorique de l'Échantillonnage par Paires : Le papier prouve que l'échantillonnage par paires découple implicitement l'objectif de régression en composantes impaires et paires, fournissant une explication rigoureuse de son succès empirique et généralisant les découvertes précédentes limitées aux interactions de bas ordre.
L'Estimateur OddSHAP : Un estimateur cohérent qui effectue une régression polynomiale uniquement sur une sélection creuse de fonctions de base de Fourier d'ordre impair. Il filtre les composantes paires non pertinentes et identifie les interactions à fort impact via un modèle proxy.
Performance de l'État de l'Art : Des tests approfondis démontrent qu'OddSHAP atteint une précision d'estimation supérieure aux méthodes existantes (incluant RegressionMSR, LeverageSHAP et PolySHAP) sous des budgets d'échantillonnage plus importants, particulièrement dans les contextes de haute dimension.

Résultats Expérimentaux

Les auteurs ont évalué OddSHAP sur huit fonctions de valeur allant de $d=14$ (DistilBERT) à $d=101$ (jeu de données Crime), couvrant les domaines du deep learning (image et texte) et des données tabulaires.

Précision : OddSHAP a systématiquement obtenu l'erreur quadratique moyenne (MSE) la plus faible et le meilleur rang moyen sur les benchmarks, particulièrement lorsque le budget d'échantillonnage $m$ est suffisant pour détecter les interactions ( $m > \eta \cdot d$ ).
Comparaison avec FFD : OddSHAP a surpassé le plan factoriel fractionnaire à budget fixe (FFD-RD) sur les architectures de deep learning (ViT, DistilBERT), où les interactions d'ordre supérieur sont significatives. Inversement, FFD-RD a légèrement mieux performé sur les jeux de données tabulaires basés sur des arbres, où les interactions d'ordre supérieur décroissent rapidement, validant ainsi les compromis spécifiques au domaine.
Études d'Ablation :
- Paires vs Non-Paires : L'échantillonnage par paires a systématiquement surpassé l'échantillonnage non apparié.
- Interactions Impaires vs Toutes les Interactions : Sous échantillonnage par paires, l'inclusion d'interactions paires n'a apporté aucun bénéfice et a légèrement dégradé la performance en consommant le budget d'interaction avec des termes qui s'annulent mathématiquement.
- Sparsité (Rareté) : L'incorporation d'un nombre modéré d'interactions impaires (contrôlé par le facteur de variable de régression $\eta$ ) a considérablement réduit l'erreur par rapport aux lignes de base linéaires, bien qu'un surapprentissage se soit produit avec trop d'interactions.

Signification et Revendications

Le papier affirme qu'OddSHAP offre un cadre à budget flexible qui s'adapte de manière robuste à travers divers structures d'interaction. Sa principale signification réside dans :

Résolution d'une Conjecture Ouverte : Il fournit le mécanisme théorique fondamental expliquant pourquoi l'échantillonnage par paires fonctionne, passant de l'observation empirique à la preuve structurelle.
Scalabilité : Il conserve le pouvoir expressif des approximations d'ordre supérieur sans subir leurs coûts combinatoires prohibitifs en se restreignant au sous-espace impair.
3.Robustesse : Contra \text{à} des méthodes reposant sur des hypothèses de troncature rigides (comme FFD), OddSHAP reste efficace dans les domaines complexes du deep learning où les interactions d'ordre élevé ne sont pas négligeables, tout en restant compétitif dans les domaines tabulaires creux.

Les auteurs notent des limites, spécifiquement que le temps d'exécution de l'algorithme passe au cube avec le budget en raison du coût de régression quadratique sur les interactions sélectionnées, et que l'échantillonnage par paires réduit le nombre effectif d'échantillons indépendants, ce qui peut accroître la variance. Cependant, ils concluent que la méthode représente une approche de pointe pour l'estimation de la valeur de Shapley dans des contextes agnostiques au modèle.