Résumé Technique : ShaplEIG

Énoncé du Problème

Les valeurs de Shapley (SV) servent de mesure d'attribution fondée sur des principes dans l'apprentissage automatique interprétable, pourtant leur calcul exact est souvent intraitable. La charge de calcul provient de deux facteurs : la croissance exponentielle des coalitions ($2^p$) avec le nombre de joueurs $p$, et le coût élevé de l'évaluation de la fonction de valeur $\nu$ pour chaque coalition. Dans des applications telles que l'importance des caractéristiques basée sur le réentraînement, la valorisation des données et l'importance des hyperparamètres, les évaluations de la fonction de valeur peuvent impliquer un réentraînement complet du modèle ou une inférence coûteuse, ce qui limite sévèrement le budget d'évaluation.

Les méthodes d'approximation existantes, incluant l'échantillonnage de Monte Carlo et les approches basées sur des substituts (par exemple, Kernel SHAP, Regression MSR), reposent généralement sur des distributions d'échantillonnage fixes et non adaptatives. Cela soulève la question de savoir si la précision de l'approximation peut être améliorée en sélectionnant de manière adaptative les coalitions à évaluer en fonction des observations précédentes, particulièrement dans les régimes à faible budget. Bien que le Design Expérimental Bayésien (BED) offre un cadre pour la conception séquentielle utilisant le Gain d'Information Attendu (EIG), son adoption dans l'estimation des SV est limitée par l'absence d'expressions d'EIG en forme fermée et par l'intraitabilité computationnelle de l'estimation de l'EIG pour les espaces discrets de haute dimension.

Méthodologie

Les auteurs proposent ShaplEIG, une approche de design expérimental bayésien qui sélectionne de manière adaptative les coalitions pour maximiser le gain d'information concernant les valeurs de Shapley.

1. Substitut par Processus Gaussien avec Noyau de Hamming

ShaplEIG modélise la fonction de valeur $\nu$ à l'aide d'un substitut par Processus Gaussien (GP). Pour gérer l'espace d'entrée binaire des coalitions (représentées comme des vecteurs indicateurs $z \in \{0, 1\}^p$), la méthode emploie un noyau de distance de Hamming. Ce noyau quantifie la similitude entre les coalitions sur la base de distances de Hamming pondérées, avec des hyperparamètres de longueur d'échelle $\xi$ apprenables. Le GP fournit une distribution postérieure sur la fonction de valeur à travers toutes les $2^p$ coalitions étant donné un ensemble de données $D_t$ d'évaluations observées.

2. Estimation Consistante des SV via la Linéarité

Une intuition théorique clé est la linéarité des valeurs de Shapley par rapport à la fonction de valeur. Les SV $\phi$ peuvent être exprimées comme une transformation linéaire du vecteur de la fonction de valeur $\nu$ : $\phi = A\nu$, où $A$ est une matrice connue dérivée de la formule de Shapley. Par conséquent, sous le substitut GP, la distribution postérieure sur les SV est également gaussienne et disponible en forme fermée :
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
Les auteurs extraient les estimations de SV à partir de la moyenne postérieure, $\hat{\phi} = A\mu_{\nu|D_t}$. Crucialement, pour les GP sans bruit (ou quasi-sans bruit), cet estimateur est consistant : si toutes les $2^p$ coalitions sont évaluées, les estimations convergent exactement vers les vraies valeurs de Shapley.

3. EIG en Forme Fermée

La contribution centrale est la dérivation d'une expression en forme fermée de l'EIG pour une coalition candidate $z^{(i)}$ concernant les SV. En formulant la sélection séquentielle comme un problème inverse linéaire bayésien où les SV sont un objectif linéaire final, l'EIG est montré comme dépendant uniquement de la covariance postérieure des SV :
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
Cela évite les espérances imbriquées typiquement requises dans le BED, car l'EIG dépend uniquement du design expérimental (la coalition sélectionnée) et non du résultat spécifique $y(x)$.

4. Calcul Efficace via les Polynômes Symétriques Élémentaires

Le calcul direct de l'EIG implique des opérations sur des matrices de taille $2^p \times 2^p$, menant à une complexité exponentielle. Les auteurs proposent un schéma de calcul efficace qui réduit la complexité en temps polynomial ($O(p^4 + t^3)$) en exploitant la structure multiplicative du noyau de Hamming.

• Les termes requis pour l'EIG (spécifiquement $A\Sigma_{\nu|D_t}e_i$ et $A\Sigma_{\nu|D_t}A^\top$) sont réécrits comme des sommes pondérées d'évaluations de noyaux.
• Ces sommes sont identifiées à des polynômes symétriques élémentaires (ESP) mis à l'échelle.
• En calculant ces polynômes efficacement (en utilisant la programmation dynamique et des tables de préfixes/suffixes), la méthode évite l'énumération explicite de toutes les coalitions.

5. Algorithme

L'algorithme procède de manière gloutonne :

1. Initialiser avec un petit design (ex: échantillonnage par score de levier).
2. Ajuster le substitut GP et optimiser les hyperparamètres.
3. Calculer l'EIG pour toutes les coalitions candidates en utilisant le schéma polynomial efficace.
4. Sélectionner la coalition avec l'EIG maximal, évaluer la fonction de valeur, et mettre à jour l'ensemble de données.
5. Répéter jusqu'à épuisement du budget.

Contributions Clés

1. Cadre ShaplEIG : Introduction d'une nouvelle méthode basée sur le BED pour l'estimation des SV qui utilise un substitut GP avec un noyau de Hamming et sélectionne les coalitions de manière adaptative selon l'EIG.
2. EIG en Forme Fermée : Démonstration que l'EIG pour les valeurs de Shapley admet une expression en forme fermée sous un substitut GP, en tirant parti de la linéarité des SV dans la fonction de valeur.
3. Complexité Polynomiale : Proposition d'un schéma de calcul efficace pour l'EIG qui réduit la complexité de l'exponentielle au temps polynomial en nombre de joueurs ($p$) via les polynômes symétriques élémentaires.
4. Estimation Consistante : Fourniture d'un estimateur de SV consistant qui converge vers les valeurs exactes lorsque toutes les coalitions sont évaluées, contrastant avec certaines méthodes de substituts basées sur des arbres qui nécessitent des étapes d'ajustement supplémentaires.

Résultats Expérimentaux

Les auteurs évaluent ShaplEIG à travers diverses applications coûteuses impliquant des jeux de petite à moyenne taille ($8 \le p \le 101$) :

• Tâches : Importance globale des caractéristiques (TabPFN), valorisation des données (Random Forest, Gradient Boosting), importance des hyperparamètres (XGBoost, LCBench), et explications locales (ResNet, ViT, Random Forest).
• Baselines : Comparaison avec Kernel SHAP, Leverage SHAP, Échantillonnage par Permutation, et l'état de l'art Regression MSR (couplé avec XGBoost).
• Ablations : Comparaison avec des variantes utilisant le même substitut GP mais des stratégies de sélection différentes (Aléatoire, Échantillonnage par Incertitude, Échantillonnage par Score de Levier).

Résultats :

• Efficacité d'Échantillonnage : ShaplEIG atteint systématiquement la meilleure précision globale (MSE la plus faible) dans le régime à faible budget pour la plupart des tâches. Il domine souvent strictement ses concurrents, particulièrement dans les jeux asymétriques où les interactions entre joueurs sont non uniformes.
• Insights d'Ablation : La forte performance est principalement attribuée à la stratégie de sélection basée sur l'EIG plutôt qu'à l'utilisation seule d'un substitut GP. L'Échantillonnage par Incertitude (US) a souvent performé moins bien que l'échantillonnage aléatoire, soulignant que maximiser la variance marginale ne revient pas à maximiser l'information concernant les SV linéairement transformés.
• Scalabilité : Pour les jeux plus grands ($p > 16$), la méthode reste efficace même si le réajustement des hyperparamètres est effectué selon un calendrier plutôt qu'à chaque itération.
• Coût de Calcul : Bien que le calcul de l'EIG soit efficace (secondes), l'ajustement des hyperparamètres peut devenir un goulot d'étranglement pour de grands $p$ (jusqu'à 25 minutes par itération pour $p \approx 100$). Les auteurs notent que ShaplEIG est plus approprié lorsque les évaluations de la fonction de valeur sont véritablement coûteuses, justifiant ainsi la surcharge de calcul.

Signification et Revendications

L'article affirme que ShaplEIG fournit un cadre fondé sur des principes pour améliorer l'efficacité de l'échantillonnage dans l'estimation des SV pour les jeux coûteux. En dérivant un EIG en forme fermée et un schéma de calcul efficace en temps polynomial, les auteurs surmontent les principaux obstacles à l'application du Design Expérimental Bayésien dans ce domaine.

Les auteurs déclarent modestement que, bien que la méthode induise une surcharge de calcul due à l'optimisation répétée du GP, elle offre des gains substantiels en précision d'estimation lorsque les budgets d'évaluation sont limités. Ils reconnaissent que pour des jeux très vastes ou des fonctions de valeur moins coûteuses, cette surcharge peut être prohibitive, suggérant que les travaux futurs devraient se concentrer sur de nouvelles améliorations de calcul pour élargir l'applicabilité de la méthode. Le travail ne prétend pas résoudre l'estimation des SV pour tous les scénarios, mais cible spécifiquement le régime des fonctions de valeur coûteuses où la sélection adaptative est critique.