📊 statistics

Approximate Shapley value estimation using sampling without replacement and variance estimation via the new Symmetric bootstrap and the Doubled half bootstrap

Dit artikel stelt een verbeterd KernelSHAP-algoritme voor dat de Wallenius' nietcentrale hypergeometrische verdeling gebruikt voor bemonstering zonder teruglegging en de symmetrische bootstrap introduceert voor variantie-inschatting, waarbij wordt aangetoond dat de prestaties vergelijkbaar met of beter zijn dan die van bestaande state-of-the-art methoden in simulatiestudies.

Oorspronkelijke auteurs: Fredrik Lohne Aanes

Gepubliceerd 2026-01-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Fredrik Lohne Aanes

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De Taart Eerlijk Verdelen

Stel je voor dat jij en een groep vrienden een enorme taart bakken (dit is de voorspelling van jouw AI-model). Je wilt precies weten hoeveel elke vriend heeft bijgedragen aan de uiteindelijke smaak. Heeft de bakker de meeste bloem toegevoegd? Heeft de decorateur de meeste suiker toegevoegd?

In de wereld van data science wordt dit Shapley-waarden genoemd. Het is een wiskundige manier om de "credit" voor een voorspelling eerlijk te verdelen onder verschillende kenmerken (zoals leeftijd, inkomen of gezondheidscijfers).

Het probleem is dat het berekenen van de exacte bijdrage van elke afzonderlijke vriend ongelooflijk traag is. Als je 20 vrienden hebt, zijn er meer dan een miljoen verschillende manieren waarop zij kunnen combineren om de taart te bakken. Je kunt niet elke mogelijke combinatie proeven.

De Oude Manier: De "Met Vervanging" Loterij

De standaardmethode (genaamd KernelSHAP) probeert dit op te lossen door een kortere route te nemen. Het werkt als een loterij:

Het stopt alle mogelijke vriendengroepen (coalities) in een grote hoed.
Het trekt een paar groepen eruit om te proeven.
De Haken en ogen: Het trekt ze eruit met vervanging. Dit betekent dat als je "Bakker + Decorateur" eruit haalt, je ze weer terug in de hoed doet. Je kunt diezelfde combinatie opnieuw trekken, of je trekt misschien nooit "Bakker + Chef" eruit.

Hierdoor kun je dezelfde groep twee keer proeven en andere groepen volledig missen. Het is als het proberen te verzamelen van een volledige set ruilkaarten door telkens uit een stapel te trekken en de kaart weer terug te leggen; je blijft misschien steeds dezelfde veelvoorkomende kaart trekken en vindt nooit de zeldzame exemplaren.

De Nieuwe Methode: Het Proeven "Zonder Vervanging"

De auteur, Fredrik Lohne Aanes, stelt een slimmere manier voor om deze groepen te bemonsteren.

1. De Wallenius-verdeling (De Gewogen Hoed)
In plaats van een willekeurige trekking, gebruikt de auteur een speciale wiskundige regel (de Wallenius' niet-centrale hypergeometrische verdeling) om te beslissen hoeveel groepen van elke grootte geproefd moeten worden.

Analogie: Stel je voor dat de hoed verschillende gekleurde ballen bevat. Sommige kleuren zijn "zwaarder" (belangrijker) dan andere. De auteur berekent precies hoeveel van elke kleur er in je steekproef zou moeten zitten om een eerlijk beeld te krijgen, in plaats van er alleen maar op te hopen dat het geluk meezit.

2. Bemonsteren Zonder Vervanging
Zodra de auteur heeft besloten hoeveel groepen er geproefd worden, haalt hij ze uit de hoed zonder ze terug te leggen.

Waarom dit ertoe doet: Als je "Bakker + Decorateur" eruit haalt, weet je dat je ze niet nog een keer zult trekken. Dit garandeert dat je een diverse set unieke combinaties krijgt. Het is als het delen van een hand kaarten; zodra een kaart is gedeeld, is deze weg. Dit maakt de data efficiënter en minder "ruisachtig".

Het Nieuwe Probleen: Hoe Zeker Zijn We?

Wanneer je iets schat met behulp van een steekproef, moet je weten hoeveel je die schatting kunt vertrouwen. In de statistiek wordt dit de variantie of de standaarddeviatie genoemd. Het is als de vraag: "Als ik dit experiment opnieuw zou doen, zou ik dan hetzelfde resultaat krijgen?"

De auteur betoogt dat de oude manier om deze zekerheid te controleren (met behode "bootstrap"-methoden) gebrekkig is voor dit specifieke type bemonstering.

De Fout: Traditionele bootstrapping gaat ervan uit dat je trekt uit een oneindige poel waar je steeds hetzelfde item kunt kiezen. Maar omdat de auteur zonder vervanging bemonstert uit een eindige lijst met mogelijkheden, klopt de oude wiskunde niet meer. Het is alsof je een regel voor een oneindige oceaan probeert te gebruiken om een kleine, eindige zwembad te meten.

De Oplossing: Twee Nieuwe "Zekerheidscheckers"

Om de controle op de zekerheid te repareren, introduceert de auteur twee nieuwe methoden:

1. De Doubled Half Bootstrap (De Upgrade van de "Oude Betrouwbare")
Dit is een bekende methode die is aangepast voor dit specifieke probleem. Het is alsof je je steekproef neemt, deze in tweeën splitst, en vervolgens de helft die niet is gekozen verdubbelt om een nieuwe "nep" steekproef te maken om tegen te testen.

2. De Symmetrische Bootstrap (De Nieuwe Ster)
Dit is de nieuwe uitvinding van de auteur.

Hoe het werkt: Stel je voor dat je een lijst hebt van de groepen die je geproefd hebt. Om een nieuwe teststeekproef te maken, beslis je voor elke groep: "Kiezen we deze groep 0 keer, 1 keer, of 2 keer?"
De Symmetrie: De magie is dat de methode ervoor zorgt dat, gemiddeld genomen, het aantal groepen dat je 0 keer kiest gelijk is aan het aantal groepen dat je 2 keer kiest.
De Analogie: Het is als een evenwichtige wipwap. Als je een groep van de linkerkant verwijdert (0 keer), moet je een duplicaat van een andere groep aan de rechterkant toevoegen (2 keer) om de wipwap perfect in balans te houden. Dit zorgt ervoor dat de wiskunde accuraat blijft voor bemonstering zonder vervanging.

De Resultaten: Heeft het Gewerkt?

De auteur heeft deze ideeën getest met echte gegevens over de levensverwachting (factoren zoals BBP, scholing en zuigelingensterfte).

Het Proeven (Schatting): De nieuwe methode (bemonsteren zonder vervanging) presteerde net zo goed als de beste bestaande tool (genaamd shapr). Het gaf even nauwkeurige antwoorden over wie wat heeft bijgedragen aan de voorspelling.
De Zekerheidscontrole (Variantie):
- De oude "Doubled Half"-methode was oké, maar had soms moeite met de wiskunde (de getallen kwamen niet altijd perfect uit).
- De nieuwe Symmetrische Bootstrap werkte erg goed. Het was snel, gemakkelijk te begrijpen en gaf zeer nauwkeurige schattingen van hoe zeker we moeten zijn over de resultaten. Sterker nog, het presteerde iets beter dan de ingebouwde zekerheidschecker in de bestaande shapr-software.

De Conclusie

Het artikel beweert niet dat het ziekten geneest of de aandelenmarkt voorspelt. Het zegt simpelweg:

We kunnen AI-uitleg efficiënter berekenen door unieke groepen kenmerken te bemonsteren (zonder vervanging) met behulp van een specifieke wiskundige regel.
We kunnen die resultaten beter vertrouwen door een nieuwe, gebalanceerde manier (Symmetrische Bootstrap) te gebruiken om de foutenmarge te berekenen.

De nieuwe aanpak is net zo goed als de huidige industriestandaard voor het verkrijgen van het antwoord, maar biedt een betere, snellere en wiskundig meer solide manier om te controleren hoe zeker we zijn van dat antwoord.

Technische Samenvatting: Benadering van de Shapley-waarde via de schatting van de werkelijke waarde met steekproeven zonder teruglegging en nieuwe bootstrap-variantie-estimators

1. Probleemstelling

Het klassieke KernelSHAP-framework (Lundberg en Lee, 2017) beoogt de computationele kosten van de Shapley-waarde-schatting te verminderen door een steekproef te nemen van een deelverzameling coalities, in plaats van de bijdragefunctie voor alle $2^p$ mogheden te evalueren. De huidige implementaties maken echter doorgaans gebruik van steekproeven met teruglegging. Deze aanpak introduceert specifieke statistische uitdagingen:

Inefficiëntie van de steekproef: Steekproeven met teruglegging leiden tot een gewogen versie van het Coupon Collector-probleem, waarbij het verkrijgen van unieke coalities steeds moeilijker wordt naarmate de steekproefomvang groeit, met name voor coalities met een laag gewicht.
Beperkingen in de variantie-inschatting: Traditionele bootstrap-methoden gaan uit van onafhankelijke en identiek verdeelde (i.i.d.) steekproeven. Deze aanname wordt geschonden wanneer er zonder teruglegging wordt getrokken uit een eindige populatie (de verzameling van alle mogelijke coalities). Bijgevolg kunnen standaard bootstrap-technieken incorrecte variantieschattingen geven voor Shapley-waarden, omdat ze er niet in slagen rekening te houden met de beperking van de eindige populatie, waarbij de variantie theoretisch naar nul zou moeten gaan als alle coalities worden geëvalueerd.

Het artikel adresseert deze problemen door een framework voor te stellen dat gebruikmaakt van steekproeven zonder teruglegging en nieuwe bootstrap-methodologieën introduceert die compatibel zijn met de theorie van eindige populaties om de variantie van benaderde Shapley-waarden nauwkeurig te schatten.

2. Methodologie

2.1 Steekproeven zonder teruglegging via de Wallenius-verdeling

Het voorgestelde algoritme wijzigt de KernelSHAP-procedure om coalities zonder teruglegging te trekken. Het proces omvat twee hoofdstappen:

Stratificatie: Coalities worden gegroepeerd op basis van het aantal kenmerken (grootte) dat ze bevatten.
Bepaling van de steekproefomvang: In plaats van coalities stochastisch één voor één te trekken, berekent het algoritme het verwachte aantal coalities dat uit elke groep moet worden getrokken met behulp van de Wallenius' niet-centrale hypergeometrische verdeling. Deze verdeling modelleert vertekende steekproeven zonder teruglegging waarbij items verschillende gewichten hebben.
- Het algoritme gebruikt de verwachte waarden van deze verdeling, afgerond naar het dichtstbijzijnde gehele getal, om het aantal coalities te bepalen dat uit elk stratum moet worden getrokken.
- Zodra de aantallen zijn bepaald, worden coalities zonder teruglegging binnen elke groep getrokken.
- Paarstrategie: Om de variantie verder te verminderen, hanteert de methode een paarstrategie (Kroese et al., 2013). Als een coalitie $S$ wordt getrokken, wordt ook de complementaire coalitie $S^c$ meegenomen in de berekening, waardoor de som van de kenmerken in gepaarde groepen constant blijft.

2.2 Variantie-inschatting via Bootstrap-methoden

Het artikel evalueert drie benaderingen voor het schatten van de standaarddeviatie van Shapley-waarden onder het nieuwe steekproefontwerp:

Ongeldige intuïtieve methode: Een standaard Horvitz-Thompson variantie-estimator die direct wordt toegepast op het gewogen kleinste kwadraten-probleem. De auteur toont aan dat dit ongeldig is omdat het geen rekening houdt met de specifieke afhankelijkheden die door de paarstrategie worden geïntroduceerd en de structuur van de $Z^T W Z$ matrix in de KernelSHAP-context.
Doubled Half Bootstrap (Antal en Tillé, 2014): Een bekende methode voor eindige populaties waarbij eenheden via Bernoulli-steekproeven worden geselecteerd en niet-geselecteerde eenheden tweemaal willekeurig worden getrokken. Deze methode wordt geïmplementeerd voor vergelijking.
Symmetrische Bootstrap (Nieuwe bijdrage): Een nieuwe bootstrap-methode ontwikkeld specifiek voor deze context.
- Mechanisme: In elke bootstrap-steekproef kan elke eenheid uit de oorspronkelijke steekproef 0, 1 of 2 keer voorkomen.
- Symmetrie: De methode zorgt ervoor dat het totaal aantal eenheden dat 0 keer voorkomt gelijk is aan het totaal aantal eenheden dat 2 keer voorkomt.
- Kansen: De kansen dat een eenheid $k$ $k$ $S_k$ $S_{k}$ keer voorkomt, zijn gedefinieerd als:
  - $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
  - $Pr(S_k = 1) = \frac{n}{N}$
- Eigenschappen: Deze constructie zorgt ervoor dat de verwachte waarde $E(S_k) = 1$ en de variantie $Var(S_k) = 1 - \frac{n}{N}$ is, wat voldoet aan de noodzakelijke voorwaarden voor geldige variantie-inschatting in eindige populatie-steekproeven (Horvitz-Thompson consistentie).
- Afhandeling van niet-gehele getallen: Wanneer het verwachte aantal "0" of "2" voorkomens geen geheel getal is, wordt een Bernoulli-toevalsvariabele geïntroduceerd om tussen aangrenzende gehele getallen te wisselen, zodat de procedure volledig automatisch blijft.

2.3 Computationele Implementatie

De bijdragefunctie $v(S)$ wordt geschat met behulp van regressie op de getrokken coalities. De implementatie maakt gebruik van ijle matrices (sparse matrices) en Cholesky-decompositie (Matrix package) om lineaire modellen efficiënt te verwerken, in staat om gemiddelden over 65.000 lineaire modellen te schatten binnen enkele minuten op een enkele kern (Aanes, 2025).

3. Belangrijkste Bijdragen

Steekproefframework: Integratie van de Wallenius' niet-centrale hypergeometrische verdeling in het KernelSHAP-framework om efficiënte steekproeven zonder teruglegging mogelijk te maken, waardoor de inefficiënties van het Coupon Collector-probleem die inherent zijn aan steekproeven met teruglegging worden vermeden.
Symmetrische Bootstrap: De introductie van een nieuwe, computationeel efficiënte bootstrap-methode die is afgestemd op steekproeven zonder teruglegging in eindige populaties. Deze voldoet aan de noodzakelijke momentvoorwaarden (gemiddelde en variantie) voor onbevooroordeelde variantie-inschatting in deze context.
Analyse van de variantie-inschatting: Een rigoureuze vergelijking van variantie-estimators, die aantoont dat standaard bootstrapping ongeldig is voor dit specifieke ontwerp en dat de nieuwe Symmetrische bootstrap de bestaande Doubled half bootstrap (Antal en Tillé, 2014) evenaart of overtreft.

4. Resultaten

Er zijn twee simulatiestudies uitgevoerd met de "Life Expectancy" dataset van Kaggle, waarbij de nieuwe methode werd vergeleken met de state-of-the-art shapr R-package (versie 1.0.7), die steekproeven met teruglegging neemt.

Kleine simulatiestudie (5 kenmerken, 16 coalities):
- De nieuwe steekproefmethode produceerde schattingen van de Shapley-waarden met standaarddeviaties die vergelijkbaar waren met die van shapr.
- De Antal-Tillé bootstrap presteerde slecht, wat vaak resulteerde in matrices met een niet-volledige rang ( $Z^T W Z$ ) en onnauwkeurige variantieschattingen.
- De Symmetrische bootstrap presteerde aanzienlijk beter dan Antal-Tillé, hoewel deze soms iets "liberale" (kleinere) standaarddeviaties produceerde vergeleken met de grondwaarheid (het opnieuw trekken van alle coalities).
Grote simulatiestudie (16 kenmerken, 402 coalities):
- De Symmetrische bootstrap en de Antal-Tillé methoden produceerden onderscheidbare schattingen van de standaarddeviatie.
- Beide nieuwe bootstrap-methoden presteerden iets beter dan de ingebouwde bootstrap-procedure in shapr, die de neiging had om de standaarddeviaties voor verschillende variabelen te onderschatten.
- Het nieuwe steekproefalgoritme (zonder teruglegging) presteerde vergelijkbaar met de shapr-methode (met teruglegging) wat betreft de nauwkeurigheid van de Shapley-waarde schattingen zelf.

5. Betekenis en Conclusie

Het artikel concludeert dat het voorgestelde algoritme, dat de steekproef zonder teruglegging via de Wallenius-verdeling combineert met de nieuwe Symmetrische bootstrap, een robuust alternatief biedt voor bestaande KernelSHAP-implementaties.

Prestaties: De nieuwe methode presteert "vergelijkbaar" met de verbeterde KernelSHAP-methode in het shapr pakket wat betreft punt-schattingen.
Variantie-inschatting: De Symmetrische bootstrap wordt benadrukt als een "zeer computationeel snelle, gemakkelijk te begrijpen" methode die goed presteert, vooral in grotere simulatiestudies. Het vult het gat in de literatuur voor een "standaard" bootstrap-methode voor willekeurige steekproeven zonder teruglegging in eindige populaties.
Beperkingen: De auteur merkt bescheiden op dat in de kleinste studie de Symmetrische bootstrap voor bepaalde variabelen soms standaarddeviaties produceerde die iets te klein (liberaal) waren, hoewel deze consequent de grootste standaarddeviaties vastlegde.
Toepasbaarheid: De methode is ontworpen voor scenario's waarin de bijdragefunctie wordt geschat via lineaire of gegeneraliseerde lineaire modellen (waar voorspellingen lineair zijn op een getransformeerde schaal), waarbij gebruik wordt gemaakt van snelle computationele technieken.

Het werk stelt vast dat de theorie van eindige populaties succesvol kan worden toegepast op de schatting van de Shapley-waarde om de efficiëntie van de steekproef te verbeteren en geldige variantie-inschattingen te bieden, waarmee de theoretische beperkingen van traditionele i.i.d. bootstrap-aannames in dit domein worden overwonnen.