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

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een gigantische, superkrachtige voorspellingsmachine bouwt. Om deze machine te laten werken, heb je duizenden of zelfs miljoenen voorbeelden nodig (bijvoorbeeld foto's van katten en honden, of medische dossiers). Maar niet elk voorbeeld is even belangrijk. Sommige foto's zijn cruciaal om de machine slim te maken, terwijl andere misschien wel 100 keer zijn gebruikt maar eigenlijk niets toevoegen.

De vraag is: Wie betaalt wat? Ofwel: hoe bepaal je eerlijk welke data-punten de meeste waarde hebben voor het eindresultaat?

In de wereld van data-wetenschap gebruiken ze hiervoor een wiskundig concept uit de speltheorie, genaamd de Shapley-waarde. Dit is als een eerlijke verdelingsrekening: je kijkt naar elke mogelijke combinatie van data-punten om te zien hoeveel een specifiek punt bijdraagt.

Het probleem? Dit is een rekenkundige nachtmerrie. Als je 1000 data-punten hebt, zijn er meer mogelijke combinaties dan er atomen in het heelal zijn. Het is onmogelijk om ze allemaal uit te rekenen. Bestaande methoden proberen dit te versnellen door te gissen (steekproeven), maar ze behandelen het als een wereldwijd probleem: ze doen alsof elk data-punt invloed heeft op elk ander punt.

De auteurs van dit paper zeggen: "Wacht even, dat klopt niet!"

De Grote Ontdekking: De "Locatie" van Invloed

Stel je voor dat je een voorspelling doet voor een specifieke klant (bijvoorbeeld: "Zal deze persoon een auto kopen?").

De oude manier: Je kijkt naar alle klanten in de database om te zien wie er invloed op heeft. Alsof je de hele wereldraad moet uitnodigen om te beslissen over één persoon.
De nieuwe manier (Local Shapley): De auteurs merken op dat moderne AI-modellen heel lokaal werken. Voor een specifieke klant, bepalen slechts een handjevol andere, vergelijkbare klanten het antwoord.
- Bij een KNN-model (een soort "zoek de gelijkenis"-machine) zijn het alleen de K dichtstbijzijnde buren.
- Bij een Beslissingsboom is het alleen de groep mensen die in hetzelfde eindvakje (blad) terechtkomen.
- Bij een GNN (voor netwerken) zijn het alleen de directe vrienden in het netwerk.

De rest van de database is voor die specifieke voorspelling volkomen irrelevant. Het is alsof je probeert te voorspellen of het morgen regent in Amsterdam, en je kijkt ook naar de weersvoorspelling voor een dorp in de Sahara. Die Sahara-data heeft geen enkele invloed op Amsterdam.

De Oplossing: LSMR (De Slimme Hergebruiker)

De auteurs hebben een nieuwe methode bedacht, genaamd LSMR (Local Shapley via Model Reuse). Ze gebruiken twee slimme trucs:

Focus op het Belangrijke (De "Locatie"):
In plaats van de hele wereldraad te raadplegen, kijken ze alleen naar de kleine groep "belangrijke buren" (de support set). Dit verkleint de rekenklus enorm.
Nooit Twee keer hetzelfde doen (Hergebruik):
Dit is de echte magische truc. Stel je voor dat je een enorme hoeveelheid soep moet koken voor een groot feest.
- De domme manier: Iedere kok kookt zijn eigen potje soep, zelfs als ze exact dezelfde ingrediënten gebruiken.
- De LSMR-methode: Ze maken één grote, centrale pot soep. Als kok A en kok B beide soep nodig hebben met dezelfde ingrediënten, halen ze gewoon uit die ene pot. Ze koken nooit twee keer dezelfde soep.

In de wereld van data betekent dit: als twee verschillende klanten precies dezelfde groep "belangrijke buren" hebben, hoeft het model maar één keer te worden getraind op die groep. Het resultaat wordt dan gedeeld.

Waarom is dit geweldig?

Snelheid: Omdat ze niet elke combinatie opnieuw hoeven te berekenen, wordt het proces tot wel duizenden keren sneller.
Eerlijkheid: Ze krijgen nog steeds een heel nauwkeurig antwoord over welke data waardevol is, zonder dat ze de hele wereld hoeven te doorzoeken.
Slimme Gissingen: Voor heel grote groepen hebben ze ook een versie (LSMR-A) die slim gissen gebruikt, maar ook hierbij zorgen ze dat ze nooit twee keer hetzelfde "gokje" doen als het resultaat al bekend is.

De Gouden Regel: Pas de Kaart aan het Territorium aan

Een belangrijke les uit het paper is dat je de "belangrijke groep" moet definiëren op basis van hoe het model werkt.

Als je een netwerk-model (zoals Facebook-vrienden) gebruikt, moet je kijken naar de vrienden in het netwerk.
Als je dat probeert te doen met een geografische kaart (wie woont het dichtstbij), werkt het niet. Het is alsof je probeert de smaak van een Italiaanse pizza te bepalen door te kijken naar de buren in de straat, terwijl de pizza eigenlijk wordt beïnvloed door de ingrediënten uit Italië. De "kaart" moet matchen met het "terrein".

Samenvatting in één zin

De auteurs hebben ontdekt dat je niet de hele wereld hoeft te analyseren om te weten wat data waard is; je hoeft alleen te kijken naar de kleine, directe omgeving die echt invloed heeft, en je kunt slimme trucs gebruiken om nooit twee keer hetzelfde werk te doen, waardoor data-waardering plotseling haalbaar wordt voor enorme datasets.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation" in het Nederlands.

Probleemstelling

De Shapley-waarde biedt een fundamentele, eerlijke basis voor het waarderen van data (data valuation) door de marginale bijdrage van elk trainingspunt te berekenen over alle mogelijke coalities. Echter, de exacte berekening is #P-hard vanwege de exponentiële grootte van de coalitiestruktuur ($2^{|D|}$).

Bestaande versnellingstechnieken (zoals Monte Carlo-sampling of truncated coalition evaluation) opereren nog steeds over de globale coalitiestruktuur. Ze gaan er impliciet van uit dat elk trainingspunt potentieel invloed heeft op elke testinstance via hertraining. Dit is een te pessimistische aanname voor moderne voorspellers. Deze modellen vertonen vaak sterke structurele sparsiteit: voor een specifieke testinstance wordt de voorspelling slechts bepaald door een klein subset van de trainingsdata (bijv. de $K$ -naaste buren bij KNN, de bladeren bij beslissingsbomen, of het receptieve veld bij GNN's). De huidige methoden negeren deze "model-geïnduceerde localiteit", wat leidt tot onnodige berekeningen en redundantie.

Methodologie

De auteurs introduceren een nieuw raamwerk dat Shapley-berekening herformuleert als een gestructureerd dataverwerkingsprobleem, gebaseerd op model-geïnduceerde localiteit.

1. Model-Geïnduceerde Localiteit en Support Sets

Voor elke testinstance $t$ wordt een support set $N(t)$ gedefinieerd. Dit is het subset van trainingspunten dat daadwerkelijk invloed heeft op de voorspelling van $t$ via het computatiepad van het model.

Exacte localiteit: Bij modellen zoals KNN of beslissingsbomen is de voorspelling strikt afhankelijk van $N(t)$ .
Benaderde localiteit: Bij modellen zoals SVM of GNN's kan de invloed buiten $N(t)$ verwaarloosbaar klein zijn. De auteurs bewijzen dat de afwijking van de globale Shapley-waarde begrensd kan worden door de aggregatie van de invloed van punten buiten de support set.

Dit leidt tot de Local Shapley Value, waarbij de coalitiestruktuur wordt geprojecteerd op $N(t)$ in plaats van de volledige dataset $D$ . Dit reduceert de intrinsieke complexiteit van $2^{|D|} $naar$ 2^{|N(t)|}$.

2. Intrinsieke Subset-Complexiteit en Ondergrens

Een cruciale inzichten is dat de complexiteit niet alleen afhangt van de grootte van de support set, maar van het aantal distincte subsets dat over alle testinstances en support sets voorkomt.

De auteurs bewijzen een informatietheoretische ondergrens: Elk correct algoritme moet elke unieke subset die invloed heeft op minstens één waardering, ten minste één keer trainen.
Naïeve lokale berekeningen leiden nog steeds tot redundantie:
- Intra-support redundantie: Dezelfde subsets worden herhaaldelijk getraind voor verschillende punten binnen dezelfde support set.
- Inter-support redundantie: Overlappende support sets tussen verschillende testinstances leiden tot dubbele trainingen van identieke subsets.

3. De LSMR-algoritme (Exact)

Om deze redundantie te elimineren, stellen de auteurs LSMR (Local Shapley via Model Reuse) voor.

Subsets-gerichte herformulering: In plaats van te rekenen per trainingspunt, wordt de berekening georganiseerd rondom subsets. Een enkele evaluatie van een subset $S$ wordt gebruikt om de Shapley-waarden van alle punten in $S$ bij te werken.
Globale hergebruik (Pivot Scheduling): Een bipartiete graaf koppelt trainingspunten aan testpunten. Een "pivot"-regel (gebaseerd op een vaste volgorde van testpunten) zorgt ervoor dat elke unieke subset $S$ slechts één keer wordt getraind (door de eerste testinstance die deze subset nodig heeft). De resultaten worden vervolgens hergebruikt voor alle andere testinstances waarvoor $S$ geldig is.
Resultaat: LSMR bereikt de theoretische ondergrens van het aantal benodigde hertrainingen.

4. De LSMR-A-algoritme (Monte Carlo)

Voor grote support sets waar exacte enumeratie ($2^{|N(t)|}$) nog steeds te duur is, introduceren ze LSMR-A.

Dit is een hergebruik-bewuste Monte Carlo-schatter.
Het combineert stochastische sampling met de pivot-mechanisme van LSMR.
Als een subset $S$ wordt gesampled, wordt deze alleen getraind als de huidige testinstance de "pivot" is voor $S$ . Anders wordt het resultaat van de pivot hergebruikt.
Statistische garanties: De schatter is onbevooroordeeld (unbiased) en vertoont exponentiële concentratie (de foutkans daalt exponentieel met het aantal samples).
Variance Reduction: Door hergebruik wordt de variantie verminderd, vooral onder distributieveranderingen (distribution shift), omdat irrelevante punten nooit worden gesampled.

Belangrijkste Bijdragen

Conceptuele Innovatie: Formalisering van "model-geïnduceerde localiteit" via support sets, wat de Shapley-berekening transformeert van een globaal enumeratieprobleem naar een lokaal, gestructureerd probleem.
Theoretische Ondergrens: Bewijs dat de intrinsieke complexiteit wordt bepaald door het aantal distincte invloedrijke subsets, wat een onmisbare ondergrens stelt voor het aantal hertrainingen.
Optimale Algoritmen:
- LSMR: Een exact algoritme dat de ondergrens bereikt door intra- en inter-support redundantie volledig te elimineren.
- LSMR-A: Een schatter die sampling en hertraining ontkoppelt, onbevooroordeeld blijft en een lagere variantie biedt dan standaard Monte Carlo-methoden.
Uitgebreide Evaluatie: Validatie over vier model-families (Weighted KNN, Decision Trees, RBF-SVM, GNNs) en diverse datasets.

Resultaten

Experimentele resultaten tonen aanzienlijke verbeteringen ten opzichte van bestaande methoden (zoals Global-MC, TMC-S, en Local-MC zonder hergebruik):

Efficiëntie: LSMR-A reduceert het aantal modelhertrainingen met meer dan drie ordes van grootte (bijv. van 1,126 miljoen naar 0,9 miljoen trainingen bij WKNN op MNIST) en versnelt de runtime aanzienlijk.
Schaalbaarheid: Waar globale methoden exponentieel groeien met de datasetgrootte, blijft de runtime van LSMR-A bijna constant of groeit sublineair, dankzij het hergebruik van subsets.
Fidelity (Nauwkeurigheid): De lokale Shapley-waarden vertonen een sterke correlatie met de globale waarden (Pearson $r$ tot 0,839), vooral bij modellen met sterke localiteit.
Downstream Utility: Bij data-selectie taken (het selecteren van de beste trainingsdata) presteert LSMR-A even goed of beter dan globale methoden, maar met veel minder rekenkosten.
Robuustheid: De methode is gevoelig voor de uitlijning tussen het model en de support set. Als de support set niet overeenkomt met het model (bijv. GNN-supports gebruiken voor KNN), daalt de nauwkeurigheid, wat benadrukt dat localiteit model-specifiek is.

Betekenis

Dit werk verandert het paradigma van data valuation. Het toont aan dat Shapley-berekening niet noodzakelijk een onoplosbaar combinatorisch probleem hoeft te zijn, maar gezien kan worden als een gestructureerd data-managementprobleem. Door de inherent aanwezige localiteit in moderne modellen te benutten en hergebruik van berekeningen optimaal te plannen, wordt data valuation schaalbaar gemaakt voor grote datasets en complexe modellen. Dit opent de deur voor eerlijke en efficiënte data-markten, dataset-compressie en model-debugging in real-world scenario's waar globale berekeningen onmogelijk zijn.