Résumé Technique : Estimation de la Valeur de Shapley Approchée par Échantillonnage Sans Remise et Nouveaux Estimateurs de Variance par Bootstrap

1. Énoncé du Problème

Le cadre classique de KernelSHAP (Lundberg et Lee, 2017) vise à réduire le coût computationnel de l'estimation des valeurs de Shapley en échantillonnant un sous-ensemble de coalitions plutôt qu'en évaluant la fonction de contribution pour les $2^p$ sous-ensembles possibles. Cependant, les implémentations existantes échantillonnent généralement les coalitions avec remise. Cette approche introduit des défis statistiques spécifiques :

1. Inefficacité de l'échantillonnage : L'échantillonnage avec remise conduit à une version pondérée du problème du collectionneur de coupons (Coupon Collector's Problem), où l'obtention de coalitions uniques devient de plus en plus difficile à mesure que la taille de l'échantillon augmente, particulièrement pour les coalitions de faible poids.
2. Limites de l'estimation de la variance : Les méthodes de bootstrap traditionnelles supposent des échantillons indépendants et identiquement distribués (i.i.d.). Cette hypothèse est violée lors d'un échantillonnage sans remise à partir d'une population finie (l'ensemble de toutes les coalitions possibles). Par conséquent, les techniques de bootstrap standard peuvent produire des estimations de variance incorrectes pour les valeurs de Shapley, ne parvenant pas à rendre compte de la contrainte de la population finie où la variance devrait théoriquement tendre vers zéro si toutes les coalitions étaient évaluées.

Le présent article traite ces problèmes en proposant un cadre qui utilise un échantillonnage sans remise et introduit de nouvelles méthodologies de bootstrap compatibles avec la théorie de la population finie pour estimer avec précision la variance des valeurs de Shapley approximées.

2. Méthodologie

2.1 Échantillonnage sans remise via la distribution de Wallenius

L'algorithme proposé modifie la procédure KernelSHAP pour échantillonner des coalitions sans remise. Le processus comprend deux étapes principales :

1. Stratification : Les coalitions sont regroupées par le nombre de caractéristiques (taille) qu'elles contiennent.
2. Détermination des tailles d'échantillon : Au lieu d'échantillonner les coalitions une par une de manière stochastique, l'algorithme calcule le nombre attendu de coalitions à prélever de chaque groupe en utilisant la distribution non centrale hypergéométrique de Wallenius. Cette distribution modélise l'échantillonnage biaisé sans remise où les éléments possèdent des poids différents.
   • L'algorithme utilise les valeurs attendues de cette distribution, arrondies à l'entier le plus proche, pour déterminer le nombre de coalitions à échantillonner dans chaque strate.
   • Une fois les comptes déterminés, les coalitions sont échantillonnées sans remise au sein de chaque groupe.
   • Stratégie de couplage : Pour réduire davantage la variance, la méthode emploie une stratégie de couplage (Kroese et al., 2013). Si une coalition $S$ est échantillonnée, sa complémentaire $S^c$ est également incluse dans le calcul, garantissant que la somme des caractéristiques dans les groupes appariés reste constante.

2.2 Estimation de la variance via les méthodes de Bootstrap

L'article évalue trois approches pour estimer l'écart-type des valeurs de Shapley sous le nouveau design d'échantillonnage :

1. Méthode intuitive invalide : Un estimateur de variance de Horvitz-Thompson standard appliqué directement au problème des moindres carrés pondérés. L'auteur démontre que cela est invalide car cela ne tient pas compte des dépendances spécifiques introduites par la stratégie de couplage et la structure de la matrice $Z^T W Z$ dans le contexte de KernelSHAP.
2. Double moitié de Bootstrap (Antal et Tillé, 2014) : Une méthode connue pour les populations finies où les unités sont sélectionnées via un échantillonnage de Bernoulli, et les unités non sélectionnées sont sélectionnées deux fois de manière aléatoire. Cette méthode est implémentée à des fins de comparaison.
3. Bootstrap Symétrique (Nouvelle contribution) : Une nouvelle méthode de bootstrap développée spécifiquement pour ce contexte.
   • Mécanisme : Dans chaque échantillon de bootstrap, chaque unité de l'échantillon original peut apparaître 0, 1 ou 2 fois.
   • Symétrie : La méthode garantit que le nombre total d'unités apparaissant 0 fois est égal au nombre total d'unités apparaissant 2 fois.
   • Probabilités : Les probabilités qu'une unité $k$ apparaisse $S_k$ fois sont définies par :
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • Propriétés : Cette construction garantit que l'espérance $E(S_k) = 1$ et la variance $Var(S_k) = 1 - \frac{n}{N}$, satisfaisant les conditions nécessaires pour une estimation de variance valide dans l'échantillonnage de population finie (consistance de Horvitz-Thompson).
   • Gestion des non-entiers : Lorsque le nombre attendu d'occurrences "0" ou "2" n'est pas un entier, une variable aléatoire de Bernoulli est introduite pour alterner entre les valeurs entières adjacentes, garantissant que la procédure reste entièrement automatique.

2.3 Implémentation computationnelle

La fonction de contribution $v(S)$ est estimée par régression sur les coalitions échantillonnées. L'implémentation exploite les matrices creuses et la décomposition de Cholesky (paquet Matrix) pour gérer efficacement les modèles linéaires, capable d'estimer des moyennes sur 65 000 modèles linéaires sur un seul cœur en quelques minutes (Aanes, 2025).

3. Principales Contributions

1. Cadre d'échantillonnage : Intégration de la distribution non centrale hypergéométrique de Wallenius dans le cadre KernelSHAP pour permettre un échantillonnage sans remise efficace, évitant les inefficacités du problème du collectionneur de coupons inhérentes à l'échantillonnage avec remise.
2. Bootstrap Symétrique : Introduction d'une nouvelle méthode de bootstrap, computationnellement efficace, adaptée à l'échantillonnage sans remise de population finie. Elle satisfait les conditions de moments nécessaires (moyenne et variance) pour une estimation de variance sans biais dans ce contexte.
3. Analyse de l'estimation de la variance : Une comparaison rigoureuse des estimateurs de variance, démontrant que le bootstrap standard est invalide pour ce design spécifique et que le nouveau bootstrap symétrique surpasse ou égale le "Double moitié de Bootstrap" existant (Antal et Tillé, 2014).

4. Résultats

Deux études de simulation ont été menées en utilisant le jeu de données "Life Expectancy" de Kaggle, comparant la nouvelle méthode à l'état de l'art, le paquet R shapr (version 1.0.7), qui échantillonne avec remise.

• Petite étude de simulation (5 caractéristiques, 16 coalitions) :
  • La nouvelle méthode d'échantillonnage a produit des estimations de valeurs de Shapley avec des écarts-types comparables à ceux de shapr.
  • Le bootstrap d'Antal-Tillé a mal performé, produisant fréquemment des matrices de rang non plein ($Z^T W Z$) et des estimations de variance inexactes.
  • Le bootstrap symétrique a nettement mieux performé qu'Antal-Tillé, bien qu'il ait occasionnellement produit des écarts-types légèrement "libéraux" (plus petits) par rapport à la vérité de terrain (rééchantillonnage de toutes les coalitions).
• Grande étude de simulation (16 caractéristiques, 402 coalitions) :
  • Les méthodes de Bootstrap Symétrique et d'Antal-Tillé ont produit des estimations d'écart-type indiscernables.
  • Les deux nouvelles méthodes de bootstrap ont performé légèrement mieux que la procédure de bootstrap intégrée dans shapr, qui avait tendance à sous-estimer les écarts-types pour plusieurs variables.
  • Le nouvel algorithme d'échantillonnage (sans remise) a performé de manière similaire à la méthode shapr (avec remise) en termes de précision des estimations des valeurs de Shapley elles-mêmes.

5. Signification et Conclusion

L'article conclut que l'algorithme proposé, qui combine l'échantillonnage sans remise via la distribution de Wallenius avec le nouveau bootstrap symétrique, offre une alternative robuste aux implémentations existantes de KernelSHAP.

• Performance : La nouvelle méthode est jugée "similaire" à la méthode améliorée de KernelSHAP du paquet shapr concernant les estimations ponctuelles.
• Estimation de la variance : Le bootstrap symétrique est mis en avant comme une méthode "très rapide à calculer et facile à comprendre" qui performe bien, particulièrement dans les grandes études de simulation. Il comble le vide dans la littérature pour une méthode de bootstrap "de référence" pour l'échantillonnage aléatoire sans remise dans les populations finies.
• Limites : L'auteur note modestement que dans la plus petite étude, le bootstrap symétrique a occasionnellement produit des écarts-types légèrement trop faibles (libéraux) pour certaines variables, bien qu'il ait systématiquement capturé les écarts-types les plus élevés.
• Applicabilité : La méthode est conçue pour des scénarios où la fonction de contribution est estimée via des modèles linéaires ou généralisés linéaires (où les prédictions sont linéaires sur une échelle transformée), en exploitant des techniques de calcul rapide.

Ce travail établit que la théorie de la population finie peut être appliquée avec succès à l'estimation des valeurs de Shapley pour améliorer l'efficacité de l'échantillonnage et fournir des estimations de variance valides, surmontant les limites théoriques des hypothèses traditionnelles de bootstrap i.i.d. dans ce domaine.