🤖 machine learning

Efficient Banzhaf-Based Data Valuation for $k$ -Nearest Neighbors Classification

Dit artikel adresseert de computationele onbehandelbaarheid van Banzhaf-gebaseerde datawaardering voor $k$ -naaste-buren-classificatoren door te bewijzen dat het probleem \#P-moeilijk is en vervolgens efficiënte exacte algoritmen met pseudo-polynoom- en lineaire tijdscomplexiteit, naast Monte Carlo-schattingmethoden, te ontwikkelen om een praktische en eerlijke beoordeling van data-bijdragen mogelijk te maken.

Oorspronkelijke auteurs: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Gepubliceerd 2026-05-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

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

Stel je voor dat je een enorme pot soep hebt (je machine learning-model) gemaakt van duizenden verschillende ingrediënten (je datapunten). Je wilt weten: Welk specifiek ingrediënt zorgde ervoor dat de soep het lekkerst smaakte? Maakte een snufje zout uit? Was de wortel essentieel? Of nam dat rare kruid alleen maar ruimte in beslag?

In de wereld van machine learning heet dit Data Valuation. Het artikel dat je hebt aangeleverd, behandelt een specifieke, lastige versie van dit probleem: het bepalen van de waarde van ingrediënten bij het gebruik van een specifieke kookmethode genaamd k-Nearest Neighbors (kNN).

Hier volgt de uiteenzetting van hun werk in eenvoudige bewoordingen:

1. Het Probleem: Tellen is Onmogelijk

Om precies te bepalen hoeveel een enkel ingrediënt (datapunt) bijdraagt, is de "eerlijke" manier om dit te doen, om elke mogelijke combinatie van ingrediënten die je in de pot zou kunnen doen, te bedenken, te proeven hoe de soep smaakt met dat ingrediënt, en vervolgens te zien hoe het smaakt zonder dat ingrediënt.

De Analogie: Stel je voor dat je 1.000 ingrediënten hebt. Om volledig eerlijk te zijn, zou je de soep moeten proeven met elke mogelijke mix van die ingrediënten (wel en niet met je doel-ingrediënt).
De Realiteit: Er zijn meer combinaties van ingrediënten dan er atomen in het universum zijn. Het uitvoeren van deze wiskunde is zo moeilijk dat computerwetenschappers het #P-hard noemen. Het is alsof je probeert elk zandkorreltje op een strand te tellen door ze één voor één op te pakken. Het zou langer duren dan de leeftijd van het universum.

2. De Oplossing: Een Slimme Afkorting

De auteurs realiseerden zich dat k-Nearest Neighbors (kNN) een speciaal soort "soep" is. Bij kNN hangt de smaak van de soep alleen af van de dichtstbijzijnde paar ingrediënten (de "naaste buren"), niet van de hele pot.

De Metafoor: Als je besluit wat je moet dragen op basis van het weer, maakt alleen de temperatuur en de wind op dit moment uit. Je hoeft het weer van drie dagen geleden of drie mijl verderop niet te kennen. De "ver weg" gelegen ingrediënten doen er niet toe.
De Doorbraak: Omdat kNN alleen om de "dichtstbijzijnde" buren geeft, bouwden de auteurs een Dynamic Programming-algoritme. Denk hierbij aan een slimme rekenmachine die niet elke mogelijke soepcombinatie proeft. In plaats daarvan bouwt het een "receptkaart" die het mogelijk maakt om de waarde van elk ingrediënt direct te berekenen door te kijken hoe de "dichtstbijzijnde buren" veranderen.

Ze creëerden drie versies van deze slimme rekenmachine:

Voor Weighted kNN: Een snelle methode die omgaat met ingrediënten met verschillende "sterktes" (gewichten).
Voor Unweighted kNN: Een nog snellere methode die alle ingrediënten als gelijk behandelt. Deze is zo efficiënt dat deze bijna lineair schaalt, wat betekent dat het enorme datasets (miljoenen ingrediënten) kan verwerken die andere methoden zouden laten crashen.
Monte Carlo Schatting: Als de dataset te groot is, zelfs voor hun slimme rekenmachine, bieden ze een "steekproef"-methode. In plaats van elke soep te proeven, proef je een paar willekeurige batches en raadt je het gemiddelde. Het is niet perfect, maar het is zeer snel.

3. Waarom Banzhaf? (De "Stemkracht"-Analogie)

Het artikel richt zich op een specifieke wiskundige formule genaamd de Banzhaf-waarde.

De Analogie: Stel je een comité voor dat stemt over een beslissing. De Shapley-waarde (een andere populaire methode) is alsof je telt hoe vaak een persoon de "uitslagbepalende stem" is in elke mogelijke samenstelling van het comité, waarbij extra gewicht wordt gegeven aan kleine groepen en enorme groepen.
Het Banzhaf-verschil: De Banzhaf-waarde is simpeler. Het vraagt gewoon: "In hoeveel scenario's verandert de stem van deze persoon daadwerkelijk de uitkomst?"
Waarom dit hier belangrijk is: De auteurs ontdekten dat Banzhaf vaak sparsamer en robuuster is.
- Sparsiteit: Het geeft een waarde van nul aan ingrediënten die niet echt uitmaken, waardoor het gemakkelijker wordt om de "sterren" van de show te identificeren.
- Robuustheid: Als iemand een hoop slechte, willekeurige ingrediënten (ruis) in smokkelt, negeert de Banzhaf-methode ze volledig. De Shapley-methode zou kunnen verwarren raken en die slechte ingrediënten een klein beetje krediet geven, wat de hele berekening verstoort.

4. Wat Ze Testten (Bewijs uit de Wereld van Alledag)

De auteurs deden niet alleen wiskunde op papier; ze testten hun "slimme rekenmachines" op echte data (zoals het herkennen van handgeschreven cijfers of het opsporen van creditcardfraude).

Snelheid: Hun nieuwe algoritmen waren duizenden keren sneller dan de oude "brute force"-methoden. Ze konden datasets met honderdduizenden punten in enkele uren verwerken, terwijl anderen dagen zouden nodig hebben of volledig zouden falen.
Data Opschonen: Ze toonden aan dat hun methode uitstekend is in het vinden van "rotte appels". Als je de datapunten verwijdert die hun methode als "minst waardevol" bestempelt, daalt de prestatie van het model scherp. Dit bewijst dat ze de belangrijke data correct hebben geïdentificeerd.
Fouten Opsporen: Ze testten of de methode data met verkeerde labels kon vinden (bijvoorbeeld een foto van een kat gelabeld als "hond").
- Zacht vs. Hard: Ze ontdekten dat "Zachte" methoden (die kijken naar kansen) beter zijn in het vinden van willekeurige fouten. Echter, hun "Harde" Banzhaf-methode is beter in het vinden van de kritieke fouten – die specifieke slechte datapunten die de prestaties van het model het meest naar beneden slepen.

Samenvatting

Dit artikel lost een enorm snelheidsprobleem op. Het maakt van een wiskundig onmogelijke taak (het eerlijk waarderen van elk datapunt in een kNN-model) een praktisch, snel instrument.

De Oude Manier: Probeer elk zandkorreltje te tellen (te traag, onmogelijk).
De Nieuwe Manier: Gebruik een kaart om alleen de korrels te tellen die het pad daadwerkelijk raken (snel, accuraat).

Ze bewezen dat voor kNN-modellen je niet de hele universum aan soepcombinaties hoeft te proeven om te weten welk ingrediënt het belangrijkst is. Je hoeft alleen naar de buren te kijken.

Technische Samenvatting: Efficiënte Banzhaf-gebaseerde Datawaardering voor $k$ -Nearest Neighbors Classificatie

Probleemstelling

Datawaardering, de taak om de bijdrage van individuele datapunten aan modelprestaties te kwantificeren, is een fundamentele uitdaging in machine learning. Hoewel game-theoretische benaderingen zoals de Banzhaf-waarde principiële kaders bieden voor eerlijke waardering, lijden ze onder exponentiële computationele complexiteit. Specifiek vereist het berekenen van exacte Banzhaf-waarden het evalueren van de waardenfunctie over alle mogelijke deelverzamelingen van de dataset, een taak die in het algemeen is bewezen #P-hard te zijn. Deze computationele last maakt exacte berekening onuitvoerbaar voor real-world datasets met duizenden of miljoenen samples, waardoor het grootste deel van het bestaande werk afhankelijk is van benaderingsmethoden die nauwkeurigheid inruilen voor efficiëntie.

Dit artikel adresseert de specifieke uitdaging van het berekenen van exacte Banzhaf-waarden voor $k$ -nearest neighbor ( $k$ NN)-classificatoren. De auteurs beogen de kloof te overbruggen tussen de theoretische fundamenten van coöperatieve speltheorie en de praktische eisen van real-world machine learning door algoritmen te ontwikkelen die gebruikmaken van de unieke lokaliteits eigenschappen van $k$ NN om aanzienlijke computationele verbeteringen te realiseren zonder terug te vallen op benadering.

Methodologie

Het artikel stelt een reeks dynamische programmerings (DP) algoritmen voor die zijn toegesneden op de $k$ NN-classificatiesetting, naast efficiënte Monte Carlo-schattingmethoden.

1. Theoretische Moeilijkheidsgraad

De auteurs stellen eerst de theoretische moeilijkheidsgraad van het probleem vast. Zij bewijzen dat het berekenen van Banzhaf-waarden voor het $k$ NN-classificatiemodel #P-hard is. Dit wordt aangetoond via een reductie van het Weighted-Majority-Game (WMG)-probleem, een klassiek #P-hard probleem in de coöperatieve speltheorie. Dit resultaat impliceert dat, onder standaard complexiteitsaannames, geen sterk polynoomtijd-algoritme bestaat voor het algemene geval.

2. Dynamische Programmeringskaders

Ondanks het hardheidsresultaat maken de auteurs gebruik van de lokaliteitseigenschap van $k$ NN (waarbij alleen de $k$ dichtstbijzijnde buren de voorspelling beïnvloeden) om exacte algoritmen te ontwikkelen met verbeterde tijdscomplexiteiten.

Standaard DP voor Gewogen $k$ NN:
De auteurs presenteren aanvankelijk een DP-algoritme met een tijdscomplexiteit van $O(W n^4)$ , waarbij $n$ het aantal datapunten is en $W$ de maximale som van de top- $k$ gewichten. Deze benadering definieert een toestandsfunctie $f_i(w, s, m)$ die het aantal deelverzamelingen van grootte $s$ met een specifieke gewichtssom $w$ en een specifiek $m$ -dichtstbijzijnd punt voorstelt.
Verbeterde DP voor Gewogen $k$ NN:
Om de complexiteit te verminderen, introduceren de auteurs nieuwe technieken:
- Voorberekening van Partiële Sommen: Voor het geval dat de deelverzamelinggrootte $s \le k$ , berekenen zij partiële sommen vooraf om de recurrentierelatie te versnellen, waardoor de bijdrage van deze term aan de complexiteit wordt verminderd.
- Binomiale Coëfficiënt Recurrentie: Voor $s > k$ maken zij gebruik van recurrentierelaties van binomiale coëfficiënten om de som van toestanden efficiënt te berekenen.
- Resultaat: Deze optimalisaties leveren een algoritme op met een tijdscomplexiteit van $O(W k n^2)$ .
Gespecialiseerde DP voor Ongewogen $k$ NN:
Voor het ongewogen geval (waarbij alle gewichten 1 zijn) stellen de auteurs een gespecialiseerd algoritme voor dat een tijdscomplexiteit van $O(n k^2)$ bereikt.
- Herdessign van Toestandsruimte: Zij reduceren de toestandsruimte door de noodzaak om de specifieke identiteit van het $m$ -dichtstbijzijnde punt bij te houden, weg te laten.
- Voorwaartse en Achterwaartse Aggregatie: Zij maken gebruik van voorwaartse ( $f_i$ ) en achterwaartse ( $b_i$ ) functies, samen met voorziene achterwaartse functies ( $b^+_i, b^-_i$ ) om labeltekens te verwerken.
- Resultaat: Aangezien $k$ typisch een kleine constante is, draait dit algoritme in bijna lineaire tijd met betrekking tot het aantal datapunten.

3. Monte Carlo Schatting

Erkend dat zelfs kwadratische complexiteit prohibitief kan zijn voor massale datasets, biedt het artikel twee efficiënte op steekproeven gebaseerde methoden:

Coalitie-gebaseerde Steekproeven: Geoptimaliseerd door alleen de top $k+1$ spelers in een gesorteerde lijst bij te houden, waardoor de complexiteit wordt gereduceerd tot $O(m n \log k)$ voor $m$ steekproeven.
Permutatie-gebaseerde Steekproeven: Past de permutatieformulering van Banzhaf-waarden toe via een herwegingsschema, en bereikt eveneens een complexiteit van $O(m n \log k)$ .

Belangrijkste Bijdragen

Hardheidsbewijs: Het artikel bewijst dat het berekenen van Banzhaf-waarden voor $k$ NN-classificatoren #P-hard is.
Eerste Exacte DP voor Gewogen $k$ NN: Het presenteert het eerste dynamische programmeringsalgoritme voor het berekenen van exacte Banzhaf-waarden in gewogen $k$ NN-classificatoren met pseudo-polynoomtijdscomplexiteit.
Geoptimaliseerd Gewogen Algoritme: Het verbetert de tijdscomplexiteit van het gewogen algoritme aanzienlijk tot $O(W k n^2)$ door middel van nieuwe algoritmische technieken die partiële sommen en binomiale recurrenties omvatten.
Bijna Lineair Ongewogen Algoritme: Het introduceert een gespecialiseerd algoritme voor ongewogen $k$ NN met een tijdscomplexiteit van $O(n k^2)$ , wat het eerste bijna lineaire tijdsalgoritme is voor het berekenen van speltheoretische waarden op basis van hard-label $k$ NN.
Efficiënte Steekproeven: Het biedt geoptimaliseerde coalitie-gebaseerde en permutatie-gebaseerde Monte Carlo-methoden die $k$ NN-lokaliteit benutten voor snellere benaderende schatting.

Experimentele Resultaten

De auteurs hebben uitgebreide experimenten uitgevoerd op 12 real-world datasets (variërend van 5.404 tot 1.000.000 datapunten) en synthetische data.

Computationele Efficiëntie:
- Het brute-force algoritme slaagde er niet in binnen 10 uur te voltooien voor datasets zo klein als 30 punten.
- Het ongewogen DP-algoritme (bv-uw) vertoonde bijna lineaire schaling en verwerkte datasets tot $10^6$ punten binnen het tijdsbudget.
- Het verbeterde gewogen DP (bv-fast) schaarde tot $10^4$ punten en presteerde beter dan bestaande hard-label Shapley-baselines (sv, sv-uw), die geen runs konden voltooien voor $n \ge 10^4$ .
- Monte Carlo-methoden boeten snelheidswinsten tot 25 $\times$ op ten opzichte van het gewogen DP bij het accepteren van een afwijking van ongeveer 0,02.
Praktische Toepassingen:
- Verwijdering van Punten: Het verwijderen van datapunten met de hoogste Banzhaf-waarden veroorzaakte een scherpere daling in modelnauwkeurigheid vergeleken met andere methoden (zoals LOO of Invloedfuncties), wat aangeeft dat deze punten kritiek waren voor de prestaties.
- Dataselectie: Het selecteren van punten met de hoogste waarden verbeterde de modelnauwkeurigheid stapsgewijs sneller dan willekeurige selectie of andere baselines.
- Detectie van Foutieve Labels: De studie benadrukte een afweging tussen waarderingstypen. Soft-label Shapley-waarden waren beter in het detecteren van willekeurig omgekeerde labels (hoge $F_1$ -score). Echter, hard-label Banzhaf-waarden waren superieur in het identificeren van beslissende punten van lage kwaliteit wier correctie de modelprestaties aanzienlijk verbeterde. Hard-label waarden waren robuuster tegen ruis en beter geschikt voor dataopruiming waarbij het doel is om punten te repareren die daadwerkelijk voorspellingen veranderen.

Betekenis en Beweringen

Het artikel beweert de snelste algoritmen te bieden voor hard-label Banzhaf-waardering in $k$ NN, zelfs de efficiëntie van hun hard-label Shapley- tegenhangers overtreffend. De betekenis ligt in het computationeel haalbaar maken van exacte game-theoretische datawaardering voor grootschalige datasets, een taak die eerder beperkt was tot benaderingen.

De auteurs benadrukken dat hoewel de Banzhaf-waarde zonder normalisatie niet voldoet aan het efficiëntie-axioma (de som van waarden gelijk is aan de totale waarde), het unieke praktische voordelen biedt:

Spartheid: Het produceert sparsere waarden, waarbij een geconcentreerde set van invloedrijke punten wordt benadrukt, wat gunstig is voor exemplaar-gebaseerde interpreteerbaarheid.
Robuustheid: Het is robuuster tegen ruis en dubbele datapunten in vergelijking met Shapley-waarden, die overgevoelig kunnen zijn voor extreme deelverzamelingen.
Praktijktoepasbaarheid: De ontwikkelde algoritmen maken de toepassing van rigoureuze datawaardering mogelijk in scenario's zoals dataacquisitie, opschoning en collaboratief leren, waarbij het begrijpen van de relatieve volgorde van het belang van datapunten cruciaal is.

Het artikel concludeert dat hoewel het kader zich niet direct uitbreidt naar $k$ NN-regressie vanwege niet-decomposeerbare normalisatietermen, het succesvol de kloof overbrugt tussen coöperatieve speltheorie en praktische machine learning-toepassingen voor classificatietaken.