📊 statistics

Fast approximate estimation of conditional Shapley values when using a linear explainer

Cet article introduit trois nouvelles méthodes, comprenant une approche exacte et deux approches approximatives, qui exploitent la théorie des champs aléatoires de Markov gausiens contraints et l'algèbre des matrices creuses pour estimer rapidement et précisément les valeurs de Shapley conditionnelles pour les modèles linéaires en calculant conjointement tous les sous-modèles, réduisant ainsi considérablement le temps de calcul par rapport aux techniques séquentielles ou itératives existantes tout en maintenant ou en améliorant la précision.

Auteurs originaux : Fredrik Lohne Aanes

Publié 2026-07-28

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Fredrik Lohne Aanes

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 essayez de comprendre pourquoi une prédiction spécifique a été faite par un programme informatique complexe, comme un système d'approbation de prêt ou un outil de diagnostic médical. Vous voulez savoir : « Dans quelle mesure votre âge a-t-il contribué ? Dans quelle mesure votre revenu a-t-il contribué ? » Dans le monde de la science des données, cela s'appelle trouver des « valeurs de Shapley ». Considérez cela comme un projet de groupe où tout le monde reçoit une note, mais vous devez calculer exactement quel crédit chaque membre de l'équipe mérite pour le score final. La partie délicate est que ces membres de l'équipe (les caractéristiques des données) dépendent souvent les uns des autres. Si vous savez que quelqu'un est grand, vous pourriez deviner qu'il est plus âgé, donc vous ne pouvez pas simplement l'observer de manière isolée ; vous devez voir comment ils travaent ensemble.

Pour faire cela mathématiquement, les scientifiques utilisent un « explicateur linéaire », qui est essentiellement un outil qui construit de nombreux petits modèles simples pour voir comment la prédiction change lorsque l'on ajoute ou retire différentes pièces d'information. Cependant, il existe un problème massif : si vous avez 20 informations différentes, le nombre de combinaisons possibles que vous devez vérifier est de plus d'un million ( $2^{20}$ ). Essayer de construire un modèle pour chaque combinaison possible une par une, c'est comme essayer de compter chaque grain de sable sur une plage en les ramassant individuellement. Cela prend un temps infini, et les ordinateurs se bloquent souvent ou manquent de mémoire. C'est le goulot d'étranglement qui rend l'explication des prédictions de l'IA complexe si lente et difficile.

Ce document, écrit par Fredrik Lohne Aanes, introduit une nouvelle façon astucieuse de résoudre ce problème de comptage. Au lieu de construire un million de modèles un par un, l'auteur suggère de construire un « super-modèle » géant qui contient tous les petits modèles à la fois, en utilisant des astuces mathématiques sophistiquées impliquant des « matrices creuses » (qui sont simplement des grilles de nombres où la plupart des emplacements sont des zéros vides). Le document propose trois nouvelles méthodes pour estimer ces valeurs rapidement. Deux d'entre elles sont « approximatives », ce qui signifie qu'elles utilisent un raccourci mathématique pour obtenir la réponse presque parfaitement, tandis que la troisième est « exacte », ce qui signifie qu'elle obtient la réponse parfaitement sans aucun raccourci.

L'auteur a testé ces nouvelles méthodes par rapport au logiciel standard actuel (appelé shapr) en utilisant des données réelles sur les revenus des adultes, des données simulées et des statistiques mondiales sur l'espérance de vie. Les résultats ont été frappants. Dans les cas où l'ancien logiciel mettait des heures à calculer les valeurs parce qu'il devait vérifier presque toutes les combinaisons possibles, les nouvelles méthodes ont terminé le travail en quelques secondes ou minutes. Par exemple, sur le jeu de données des revenus des adultes, l'ancienne méthode a pris environ 17 à 19 minutes, tandis que les nouvelles méthodes ont pris entre 2,5 et 9 secondes. Même dans une simulation où l'ancienne méthode était rapide car elle ne vérifiait que quelques combinaisons, les nouvelles méthodes ont réussi à vérifier les 2 millions de combinaisons possibles en moins de trois minutes.

Le document suggère que, bien que les méthodes approximatives soient incroyablement rapides, la « méthode de transformation exacte » est le meilleur choix car elle ne nécessite aucun réglage de boutons de commande et donne des résultats tout aussi précis que les autres. L'auteur conclut qu'en utilisant ces nouvelles techniques, nous pouvons enfin expliquer les modèles complexes beaucoup plus rapidement, même en traitant de nombreuses variables différentes, sans sacrifier la précision. C'est comme remplacer un processus de comptage manuel et lent par un scanner à haute vitesse qui voit toute la plage en un seul regard.

Résumé technique : Estimation rapide des valeurs de Shapley conditionnelles par des expliqueurs linéaires

Énoncé du problème

L'article traite du goulot d'étranglement computationnel associé à l'estimation des valeurs de Shapley conditionnelles pour les modèles de régression linéaire lorsque les covariables sont dépendantes. Bien que les valeurs de Shapley fournissent une décomposition de la contribution des caractéristiques à une prédiction spécifique selon la théorie des jeux, le calcul de leurs versions conditionnelles nécessite d'estimer l'espérance mathématique de la sortie du modèle pour toutes les sous-populations possibles (coalitions) de caractéristiques.

Pour un modèle possédant $p$ prédicteurs, il existe $2^p$ coalitions possibles. Les méthodes existantes, telles que les approches Séquentielle et Itérative du package R shapr, font face à des défis importants :

Estimation Séquentielle : Nécessite l'ajustement de $2^p$ modèles de régression distincts, ce qui devient computationnellement intraitable à mesure que $p$ augmente.
Estimation Itérative : Échantillonne des coalitions jusqu'à ce qu'un critère de convergence soit atteint. Bien que plus rapide lorsque peu de coalitions suffisent, elle peut tout de même nécessiter une grande fraction de toutes les $2^p$ coalitions pour atteindre la convergence, entraînant des temps d'exécution longs (des heures) comparables à la méthode séquentielle dans les cas difficiles.
Dépendance des caractéristiques : Contrairement aux valeurs de Shapley marginales, les valeurs conditionnelles doivent tenir compte de la structure de dépendance entre les covariables, ce qui nécessite des calculs d'espérance conditionnelle complexes.

Les auteurs visent à développer des méthodes capables d'estimer les coefficients pour toutes les $2^p$ sous-populations simultanément et rapidement, en exploitant la parcimonie des structures mathématiques sous-jacentes.

Méthodologie

L'approche proposée utilise la théorie des Champs de Markov Gaussiens contraints (GMRF) et l'algèbre matricielle creuse pour estimer conjointement les coefficients de régression pour toutes les sous-populations. Les auteurs dérivent trois algorithmes distincts :

1. La méthode de correction diagonale (Approximative)

Cette méthode approxime la régression contrainte en modifiant la matrice de précision ( $Q = X^T X$ ) du modèle complet.

Mécanisme : Pour imposer une contrainte où un coefficient spécifique est nul (c'est-à-dire que la caractéristique est exclue d'une sous-population), une valeur scalaire élevée $\kappa$ est ajoutée à l'élément diagonal correspondant de la matrice de précision.
Base théorique : Basée sur l'identité de la matrice de Woodbury, l'ajout de $\kappa A^T A$ (où $A$ est une matrice de contrainte) à $Q$ approxime la matrice de covariance conditionnelle lorsque $\kappa \to \infty$ .
Implémentation : Une matrice de contrainte jointe $A$ est construite pour l'ensemble des $2^p$ modèles. La méthode résout le système linéaire $(Q_F + \kappa A^T A)^{-1}m$ , où $Q_F$ est une matrice bloc-diagonale contenant la matrice de précision du modèle complet répétée $2^p$ fois.
Réglage : Nécessite un paramètre de réglage $\kappa$ , suggéré comme étant $10^5$ fois la plus grande valeur propre de la matrice de précision originale.

2. La méthode de projection (Approximative)

Cette méthode projette l'espace des paramètres pour supprimer les paramètres contraints.

Mécanisme : Une matrice de projection $Z = I - A^T A$ est appliquée à la matrice de précision. Le modèle contraint est traité comme un GMRF intrinsèque. Pour assurer la stabilité numérique (définition positive), un petit scalaire $\epsilon$ est ajouté au diagonal de la matrice de précision projetée ( $Z Q Z + \epsilon I$ ).
Base théorique : À mesure que $\epsilon \to 0^+$ , la solution converge vers les estimations contraintes exactes.
Implémentation : Résout le système $Z(Z Q_F Z + \epsilon I)^{-1} Z m$ .
Réglage : Nécessite un petit paramètre de réglage $\epsilon$ (par exemple, $10^{-5}$ ), choisi pour être petit par rapport à la plus petite valeur propre de $Q$ mais suffisamment grand pour une décomposition de Cholesky stable.

3. La méthode de transformation exacte (Exacte)

Cette méthode fournit une solution exacte sans erreurs d'approximation ni paramètres de réglage.

Mécanisme : Au lieu de travailler dans l'espace des paramètres complet et de forcer les coefficients à zéro, la méthode transforme le problème dans un espace de dimension inférieure ne contenant que les paramètres non nuls.
Implémentation : Une matrice de correspondance $E$ est construite pour sélectionner uniquement les paramètres actifs pour chaque sous-population. Le système est résolu comme $(E Q_F E^T)^{-1} E m$ .
Avantage : Élimine le besoin de grands termes de pénalité ( $\kappa$ ) ou de petits termes de régularisation ( $\epsilon$ ), évitant ainsi l'instabilité numérique ou le biais d'approximation.

Les trois méthodes utilisent l'algèbre matricielle creuse (spécifiquement la décomposition de Cholesky) pour gérer efficacement l'estimation conjointe de milliers de modèles. La matrice de précision jointe est hautement creuse car les modèles sont indépendants (structure bloc-diagonale), et les zéros hors-diagonaux indiquent une indépendance conditionnelle.

Contributions clés

Trois nouveaux algorithmes : L'article introduit deux méthodes approximatives (Correction Diagonale, Projection) et une méthode exacte (Transformation Exacte) pour l'estimation conjointe de toutes les sous-populations dans la régression linéaire.
Preuves de convergence : Les auteurs fournissent des preuves mathématiques démontrant que les méthodes approximatives convergent vers les estimations conditionnelles réelles à mesure que leurs paramètres de régl respectifs ( $\kappa \to \infty$ et $\epsilon \to 0^+$ ).
Efficacité computationnelle : En exploitant la parcimonie et l'estimation conjointe, les méthodes réduisent le temps de calcul de plusieurs heures (typiquement avec shapr) à quelques secondes ou minutes, même en énumérant l'intégralité des $2^p$ coalitions.
Validation empirique : Des études numériques approfondies comparent les nouvelles méthodes au package shapr (versions Séquentielle et Itérative) sur trois jeux de données : Adult Income, un jeu de données gaussien simulé, et le jeu de données WHO Life Expectancy.

Résultats

Les études de cas numériques produisent les conclusions suivantes :

Précision : Les estimations des valeurs de Shapley produites par les nouvelles méthodes sont virtuellement identiques à la méthode Séquentielle de shapr (utilisée comme vérité de terrain pour l'énumération complète).
- Dans le jeu de données Adult ( $p=11$ ), l'erreur absolue médiane (MedAE) entre les nouvelles méthodes et la méthode Séquentielle était de l'ordre de $10^{-9}$ .
- Dans le jeu de données Simulée ( $p=21$ ), la MedAE était de l'ordre de $10^{-7}$ à $10^{-5}$ .
- Dans le jeu de données WHO ( $p=16$ ), la MedAE était de l'ordre de $10^{-6}$ .
Vitesse :
- Jeu de données Adult : Les nouvelles méthodes se sont exécutées en 2,5 à 9 secondes, tandis que shapr (Séquentiel et Itératif) a pris 17 à 19 minutes.
- Jeu de données Simulée : Les nouvelles méthodes ont pris 1,4 à 2,5 minutes pour estimer l'intégralité des $2^{21} \approx 2,1$ millions de modèles. La méthode Itérative de shapr était plus rapide (6,48 secondes) mais n'a estimé que 200 coalitions, et non l'ensemble complet.
- Jeu de données WHO : Les nouvelles méthodes ont pris 1,1 à 1,2 minute. La méthode Séquentielle de shapr a pris 131 minutes (2,2 heures), et la méthode Itérative a pris 16 minutes (en parallèle) ou 36 minutes (en série).
Scalabilité : Les méthodes ont réussi à estimer plus de deux millions de sous-populations dans l'étude simulée en quelques minutes. La principale limitation identifiée est la contrainte de mémoire (fléau de la dimensionnalité) lorsque $p$ dépasse environ 21 sur un matériel standard, bien que les auteurs notent que cela peut être atténué avec plus de RAM ou des packages de matrices creuses spécialisés.

Signification et affirmations

L'article affirme que les méthodes proposées offrent une amélioration substantielle de l'efficacité computationnelle pour l'estimation des valeurs de Shapley conditionnelles sans sacrifier la précision.

Supériorité dans l'énumération complète : Lorsque la méthode Itérative de shapr nécessite une grande fraction de coalitions pour converger (comme observé dans les jeux de données Adult et WHO), les nouvelles méthodes sont « sensiblement plus rapides » tout en maintenant une « précision égale ou supérieure ».
Énumération complète : Contra-rément à l'approche itérative qui échantillonne des coalitions, les nouvelles méthodes fournissent une énumération complète des $2^p$ sous-populations, garantissant qu'aucune information n'est perdue à cause de la variance d'échantillonnage.
Recommandation : Les auteurs recommandent la Méthode de Transformation Exacte. Bien que les trois méthodes produisent des résultats comparables, la méthode Exacte ne possède pas de paramètres de réglage, éliminant ainsi le besoin de sélection d'hyperparamètres et les sources potentielles d'erreur d'approximation.
Potentiel futur : Les auteurs suggèrent que la méthodologie peut être étendue pour traiter les splines (par exemple, du package rms) et que la parallélisation (par exemple, via OpenMP) pourrait réduire davantage les temps d'exécution, bien que l'implémentation actuelle repose sur une exécution sérielle pour une comparaison équitable avec le package shapr parallélisé.

L'article conclut que ces méthodes rendent le calcul exact des valeurs de Shapley conditionnelles pour les modèles linéaires avec des types de covariables mixtes réalisable dans des scénarios qui étaient auparavant trop coûteux sur le plan computationnel.