Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Ce papier propose LSMR, un algorithme qui exploite la localité induite par le modèle pour réduire la complexité du calcul de la valeur de Shapley en réutilisant optimalement l'entraînement sur des sous-ensembles de données pertinents, permettant ainsi une estimation rapide et précise sans perte de fidélité.

L'essentiel

Voici une explication simple de l'article de recherche, imagée avec des analogies pour rendre le tout plus clair.

🍕 Le Problème : Qui mérite sa part de pizza ?

Imaginez que vous avez organisé une grande fête (c'est votre modèle d'intelligence artificielle) et que vous avez invité des centaines de personnes (vos données d'entraînement) pour aider à cuisiner le repas.

Maintenant, vous voulez savoir : qui a vraiment contribué à la réussite du plat ?

• Est-ce Marie qui a apporté les tomates ?
• Est-ce Paul qui a coupé les oignons ?
• Ou est-ce que c'est juste le chef qui a tout fait ?

En mathématiques, on utilise une méthode très juste appelée la valeur de Shapley pour répondre à cette question. Elle calcule la contribution de chaque personne en imaginant tous les groupes possibles qu'on pourrait former (toutes les combinaisons de convives) et en voyant comment le plat change si on enlève ou ajoute une personne.

Le problème ? Si vous avez 100 invités, le nombre de combinaisons possibles est astronomique (plus que le nombre d'atomes dans l'univers !). Calculer cela exactement prendrait des milliers d'années. C'est ce qu'on appelle un problème "impossible" à résoudre rapidement.

---

🕵️‍♂️ La Révolution : La "Localité" (Le Secret de la Cuisine)

Les auteurs de cet article ont remarqué quelque chose d'évident mais qu'on ignorait souvent : pour un plat spécifique, tout le monde n'est pas nécessaire.

• Si vous voulez savoir qui a fait le meilleur café, peu importe que Paul ait apporté des tomates. Seuls ceux qui ont touché au café comptent.
• Si vous voulez savoir qui a aidé à prédire la météo, peu importe que Marie ait cuisiné le dessert. Seuls les météorologues comptent.

C'est ce qu'ils appellent la "Localité induite par le modèle".
Pour chaque situation (chaque "test"), seule une petite poignée de données a vraiment influencé le résultat. Les autres sont des spectateurs invisibles.

L'analogie du feu de camp :
Imaginez un grand feu de camp. Si vous vous asseyez tout près, vous ressentez la chaleur. Si vous êtes à 50 mètres, vous ne ressentez rien.

• L'ancienne méthode (Shapley global) disait : "Pour savoir qui chauffe le feu, il faut vérifier l'impact de chaque brindille, même celles à l'autre bout du monde."
• La nouvelle méthode (Local Shapley) dit : "Attends, pour cette personne précise qui est assise ici, seules les brindilles autour d'elle comptent. On peut ignorer le reste !"

---

🚀 La Solution : LSMR (Le Super-Organisateur)

Même en se limitant à la "petite poignée" de données importantes, il reste encore trop de combinaisons à tester. C'est là qu'intervient l'algorithme LSMR (Local Shapley via Model Reuse).

L'analogie du Chef Cuisinier Intelligent :
Imaginez un chef qui doit tester des milliers de recettes.

1. L'ancienne façon : Il cuisine chaque recette, la goûte, la jette, puis cuisine la suivante. Il perd un temps fou à refaire exactement la même chose.
2. La façon LSMR : Le chef a une carte mentale. Il se dit : "Ah, cette recette avec des tomates et du basilic, je l'ai déjà faite pour le client A. Je vais juste réutiliser ce que j'ai cuisiné pour le client B qui veut la même chose."

LSMR utilise deux astuces magiques :

1. La Carte des Supports : Il identifie exactement qui est dans le "cercle de chaleur" (le groupe de données pertinent) pour chaque test.
2. Le Réemploi Intelligent : Si deux tests différents ont besoin de la même combinaison de données, le modèle ne l'entraîne qu'une seule fois. Il sauvegarde le résultat et le réutilise partout où c'est nécessaire.

C'est comme si vous alliez au supermarché : au lieu d'acheter des ingrédients séparément pour chaque recette, vous faites un seul gros panier de courses et vous cuisinez tout à partir de là.

---

📊 Les Résultats : Plus Vite, Plus Juste

Les chercheurs ont testé leur méthode sur différents types de modèles (comme les arbres de décision, les réseaux de neurones, etc.) et ont obtenu des résultats impressionnants :

• Vitesse Éclair : Ils ont réduit le temps de calcul de plusieurs ordres de grandeur. Là où il fallait des jours, ils ont fini en quelques minutes.
• Économie d'Énergie : Ils ont évité des millions d'entraînements inutiles de modèles.
• Fiabilité : Même en allant plus vite, les résultats restent très justes. La "valeur" attribuée à chaque donnée reste cohérente avec la vérité absolue.

💡 En Résumé

Cette recherche nous dit : "Arrêtez de chercher l'aiguille dans la botte de foin en fouillant toute la botte !"

Au lieu de tout calculer, utilisez la structure du modèle pour savoir où regarder. En se concentrant uniquement sur les données qui comptent vraiment pour une situation donnée, et en réutilisant intelligemment les calculs déjà faits, on peut évaluer la valeur des données de manière juste, rapide et économique.

C'est une avancée majeure pour rendre l'analyse de données plus accessible et écologique (moins de gaspillage de puissance de calcul) dans un monde où les données sont devenues la nouvelle monnaie.

Résumé technique

Voici un résumé technique détaillé de l'article "Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation", structuré selon les aspects demandés.

1. Problématique

La valuation des données vise à quantifier la contribution de chaque point de données d'entraînement à la performance d'un modèle. La valeur de Shapley, issue de la théorie des jeux coopératifs, est la méthode de référence pour garantir l'équité et la rigueur de cette attribution.

Cependant, le calcul exact de la valeur de Shapley est un problème #P-difficile. Il nécessite d'évaluer la performance du modèle sur un nombre exponentiel de coalitions ($2^{|D|}$, où$|D|$ est la taille de l'ensemble de données), ce qui implique un nombre prohibitif de réentraînements de modèles.

Les méthodes d'accélération existantes (échantillonnage Monte Carlo, truncation, fonctions d'influence) restent globales : elles supposent implicitement que chaque point de données peut influencer chaque prédiction via le réentraînement. Or, les prédicteurs modernes (KNN, arbres de décision, GNN, SVM) présentent une sparsité structurelle : pour une instance de test donnée, seule une petite sous-ensemble de points d'entraînement influence réellement la prédiction. Les méthodes actuelles ignorent cette propriété, entraînant des calculs redondants et inefficaces.

2. Méthodologie

Les auteurs proposent un cadre basé sur la localité induite par le modèle et la réutilisation optimale des sous-ensembles.

A. Formalisation de la Localité Induite par le Modèle

L'article introduit la notion de ensemble de support $N(t)$ pour une instance de test $t$. Cet ensemble contient uniquement les points d'entraînement qui participent au chemin de calcul du modèle pour prédire $t$ (ex: les $K$ voisins les plus proches en KNN, les vecteurs de support en SVM, les feuilles dans un arbre, ou le champ réceptif dans un GNN).

• Utilité projetée : L'utilité $v_t(S)$ est redéfinie pour ne dépendre que de l'intersection $S \cap N(t)$.
• Valeur de Shapley Locale : Le calcul est restreint aux sous-ensembles de $N(t)$.
• Garantie d'approximation : Si la localité est exacte (ex: KNN à seuil), la valeur locale est égale à la valeur globale. Si elle est approximative, l'erreur est bornée par la masse d'interaction des points hors du support (Assomption 1).

B. Complexité Intrinsèque et Réutilisation Optima

Les auteurs démontrent que la complexité réelle ne dépend pas du nombre total de coalitions, mais du nombre de sous-ensembles distincts qui influencent au moins une valuation.

• Borne inférieure informationnelle : Tout algorithme correct doit évaluer chaque sous-ensemble distinct au moins une fois.
• Réduction de la redondance :
  • Intra-support : Plusieurs points d'entraînement dans le même support partagent les mêmes sous-ensembles.
  • Inter-support : Différents points de test partagent des supports qui se chevauchent.

C. Algorithmes Proposés

1. LSMR (Local Shapley via Model Reuse) : Un algorithme exact qui élimine toute redondance.

   • Il construit un graphe biparti reliant les sous-ensembles aux points de test concernés.
   • Il utilise un ordonnancement par pivot : chaque sous-ensemble distinct $S$ est entraîné exactement une fois par son "pivot" (le premier point de test dans l'ordre global pour lequel $S$ est valide).
   • Les résultats sont réutilisés pour tous les autres points de test concernés.
   • Optimalité : LSMR atteint la borne inférieure théorique du nombre de réentraînements ($|S|$, le nombre de sous-ensembles distincts).

2. LSMR-A (LSMR Approximatif) : Un estimateur Monte Carlo réutilisant la stratégie de pivot.

   • Au lieu de traiter chaque coalition échantillonnée indépendamment, LSMR-A partage chaque sous-ensemble échantillonné entre tous les supports compatibles.
   • Il reste non biaisé et bénéficie d'une concentration exponentielle.
   • Sa complexité de temps dépend du nombre de sous-ensembles distincts échantillonnés, et non du nombre total de tirages, réduisant ainsi la variance, surtout en cas de décalage de distribution (distribution shift).

3. Contributions Clés

1. Abstraction Structurelle : Introduction de la "localité induite par le modèle" comme principe fondamental pour la valuation des données, formalisée via les ensembles de support.
2. Borne Théorique : Preuve d'une borne inférieure informationnelle sur le nombre d'opérations de réentraînement nécessaires, basée sur la complexité des sous-ensembles distincts.
3. Algorithmes Optimaux :
   • Développement de LSMR, un algorithme exact optimal qui élimine la redondance intra et inter-support.
   • Développement de LSMR-A, un estimateur Monte Carlo qui découple la complexité d'échantillonnage de la complexité de réentraînement.
4. Garanties Statistiques : Preuve de l'absence de biais et de la réduction de variance de LSMR-A par rapport aux méthodes Monte Carlo classiques, grâce à l'amortissement de la redondance structurelle.

4. Résultats Expérimentaux

Les expériences ont été menées sur quatre familles de modèles (KNN pondéré, Arbres de décision, SVM à noyau RBF, GNN) et divers jeux de données (MNIST, Iris, Breast Cancer, Cora).

• Fidélité d'Approximation : La valeur de Shapley locale corrèle fortement avec la valeur globale (coefficient de Pearson jusqu'à 0.84 pour KNN), confirmant que les ensembles de support capturent les voies d'influence dominantes.
• Utilité en Sélection de Données : Les scores de Shapley locaux permettent une sélection de données aussi efficace (voire meilleure) que les méthodes globales pour l'entraînement de modèles, en identifiant les échantillons les plus influents.
• Efficacité Computationnelle :
  • LSMR-A réduit le nombre de réentraînements de plusieurs ordres de grandeur par rapport aux méthodes globales (ex: réduction de $10^3$à$10^5$ fois sur KNN).
  • Le temps d'exécution est considérablement réduit, permettant de traiter des ensembles de données où les méthodes globales deviennent inapplicables.
  • La réutilisation structurelle permet une convergence plus rapide et une variance plus faible.
• Sensibilité à la Taille du Support : Une petite taille de support suffit souvent pour capturer l'influence dominante, offrant un excellent compromis entre précision et coût.
• Alignement du Modèle : La précision dépend de l'alignement entre la construction de l'ensemble de support et l'architecture du modèle évalué. Un mauvais alignement (ex: utiliser un support KNN pour un GNN) dégrade la performance, soulignant l'importance de la localité structurelle spécifique au modèle.

5. Signification et Impact

Cet article transforme la perception du calcul de Shapley : d'un problème d'énumération combinatoire globale, il devient un problème de gestion de données structurées.

• Théorique : Il établit que la complexité intrinsèque est gouvernée par la structure du modèle et non par la taille brute des données.
• Pratique : Il rend la valuation des données à grande échelle et sur des modèles complexes (comme les réseaux de neurones profonds) réalisable en pratique.
• Futur : Le cadre ouvre la voie à des applications dans des environnements dynamiques et fédérés, où les structures de support évoluent ou sont décentralisées.

En résumé, Local Shapley démontre que l'exploitation de la sparsité structurelle des modèles modernes, couplée à une réutilisation optimale des calculs, permet d'atteindre une scalabilité théorique et pratique pour la valorisation équitable des données.