🤖 machine learning

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

Dieser Beitrag adressiert die rechnerische Unlösbarkeit der Banzhaf-basierten Datenbewertung für $k$ -nächste-Nachbar-Klassifikatoren, indem er nachweist, dass das Problem \#P-schwer ist, und anschließend effiziente exakte Algorithmen mit pseudo-polynomieller und linearer Zeitkomplexität sowie Monte-Carlo-Schätzverfahren entwickelt, um eine praktische und faire Bewertung des Datenbeitrags zu ermöglichen.

Ursprüngliche Autoren: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Veröffentlicht 2026-05-21

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben einen riesigen Topf Suppe (Ihr maschinelles Lernmodell), der aus Tausenden verschiedener Zutaten (Ihren Datenpunkten) besteht. Sie möchten wissen: Welche spezifische Zutat hat die Suppe am besten schmecken lassen? Hatte die Prise Salz eine Bedeutung? War die Karotte unverzichtbar? Oder nahm nur dieses seltsame Gewürz unnötig Platz ein?

In der Welt des maschinellen Lernens nennt man dies Datenbewertung (Data Valuation). Die von Ihnen bereitgestellte Arbeit behandelt eine spezifische, knifflige Variante dieses Problems: die Ermittlung des Wertes von Zutaten bei Verwendung einer bestimmten Kochmethode namens k-Nächste-Nachbarn (kNN).

Hier ist die Aufschlüsselung ihrer Arbeit in einfachen Worten:

1. Das Problem: Zählen ist unmöglich

Um genau herauszufinden, wie sehr eine einzelne Zutat (ein Datenpunkt) beiträgt, wäre der „faire" Weg, jede mögliche Kombination von Zutaten vorzustellen, die man in den Topf geben könnte, zu prüfen, wie die Suppe mit dieser Zutat schmeckt, und dann zu prüfen, wie sie ohne sie schmeckt.

Die Analogie: Stellen Sie sich vor, Sie haben 1.000 Zutaten. Um völlig fair zu sein, müssten Sie die Suppe mit jeder einzelnen möglichen Mischung dieser Zutaten probieren (mit und ohne Ihre Zielzutat).
Die Realität: Es gibt mehr Kombinationen von Zutaten als Atome im Universum. Diese Mathematik zu betreiben ist so schwierig, dass Informatiker sie als #P-hart bezeichnen. Es ist wie der Versuch, jeden Sandkorn an einem Strand zu zählen, indem man sie einzeln aufhebt. Es würde länger dauern als das Alter des Universums.

2. Die Lösung: Ein intelligenter Shortcut

Die Autoren erkannten, dass k-Nächste-Nachbarn (kNN) eine besondere Art von „Suppe" ist. Bei kNN hängt der Geschmack der Suppe nur von den nächsten wenigen Zutaten ab (den „nächsten Nachbarn"), nicht vom ganzen Topf.

Die Metapher: Wenn Sie entscheiden, was Sie aufgrund des Wetters anziehen, interessieren Sie sich nur für die Temperatur und den Wind gerade jetzt. Sie müssen das Wetter nicht von vor drei Tagen oder drei Meilen entfernt wissen. Die „entfernten" Zutaten spielen keine Rolle.
Der Durchbruch: Da kNN nur die „nächsten" Nachbarn berücksichtigt, entwickelten die Autoren einen Dynamischen-Programmierung-Algorithmus. Stellen Sie sich dies als einen intelligenten Rechner vor, der nicht jede einzelne Suppenkombination probiert. Stattdessen erstellt er eine „Rezeptkarte", die es ihm ermöglicht, den Wert jeder Zutat sofort zu berechnen, indem er betrachtet, wie sich die „nächsten Nachbarn" ändern.

Sie schufen drei Versionen dieses intelligenten Rechners:

Für gewichtetes kNN: Eine schnelle Methode, die Zutaten mit unterschiedlichen „Stärken" (Gewichten) handhabt.
Für ungewichtetes kNN: Eine noch schnellere Methode, die alle Zutaten als gleich behandelt. Diese ist so effizient, dass sie sich fast linear skaliert, was bedeutet, dass sie massive Datensätze (Millionen von Zutaten) bewältigen kann, die andere Methoden zum Absturz bringen würden.
Monte-Carlo-Schätzung: Wenn der Datensatz zu groß ist, selbst für ihren intelligenten Rechner, bieten sie eine „Stichproben"-Methode an. Anstatt jede Suppe zu probieren, probieren Sie einige zufällige Chargen und schätzen den Durchschnitt. Es ist nicht perfekt, aber sehr schnell.

3. Warum Banzhaf? (Die „Stimmkraft"-Analogie)

Die Arbeit konzentriert sich auf eine spezifische mathematische Formel namens Banzhaf-Wert.

Die Analogie: Stellen Sie sich ein Komitee vor, das über eine Entscheidung abstimmt. Der Shapley-Wert (eine andere beliebte Methode) zählt, wie oft eine Person in jeder möglichen Aufstellung des Komitees die „entscheidende Stimme" ist, wobei kleinen und großen Gruppen zusätzliches Gewicht gegeben wird.
Der Banzhaf-Unterschied: Der Banzhaf-Wert ist einfacher. Er fragt einfach: „In wie vielen Szenarien ändert die Stimme dieser Person tatsächlich das Ergebnis?"
Warum das hier wichtig ist: Die Autoren stellten fest, dass Banzhaf oft spärlicher und robuster ist.
- Spärlichkeit: Er weist Zutaten, die wirklich keine Rolle spielen, einen Wert von null zu, was es einfacher macht, die „Stars" der Show zu identifizieren.
- Robustheit: Wenn jemand eine Menge schlechter, zufälliger Zutaten (Rauschen) einschmuggelt, ignoriert die Banzhaf-Methode sie vollständig. Die Shapley-Methode könnte verwirrt werden und diesen schlechten Zutaten ein winziges bisschen Gutschrift geben, was die gesamte Berechnung verfälscht.

4. Was sie testeten (Beweis aus der realen Welt)

Die Autoren haben nicht nur Mathematik auf Papier betrieben; sie testeten ihre „intelligenten Rechner" an realen Daten (wie beim Erkennen handschriftlicher Zahlen oder beim Aufspüren von Kreditkartenbetrug).

Geschwindigkeit: Ihre neuen Algorithmen waren Tausende Male schneller als die alten „Brute-Force"-Methoden. Sie konnten Datensätze mit Hunderttausenden von Punkten in Stunden bewältigen, während andere Tage brauchen würden oder komplett versagen würden.
Bereinigung von Daten: Sie zeigten, dass ihre Methode hervorragend darin ist, „schlechte Äpfel" zu finden. Wenn Sie die Datenpunkte entfernen, die ihre Methode als „am wenigsten wertvoll" bezeichnet, sinkt die Leistung des Modells drastisch. Dies beweist, dass sie die wichtigen Daten korrekt identifiziert haben.
Fehler finden: Sie testeten, ob die Methode Daten mit falschen Labels finden kann (z. B. ein Bild einer Katze, das als „Hund" gekennzeichnet ist).
- Weich vs. Hart: Sie stellten fest, dass „Weiche" Methoden (die Wahrscheinlichkeiten betrachten) besser darin sind, zufällige Fehler zu finden. Ihre „Harte" Banzhaf-Methode ist jedoch besser darin, die kritischen Fehler zu finden – jene spezifischen schlechten Datenpunkte, die die Leistung des Modells tatsächlich am meisten nach unten ziehen.

Zusammenfassung

Diese Arbeit löst ein massives Geschwindigkeitsproblem. Sie verwandelt eine mathematisch unmögliche Aufgabe (die faire Bewertung jedes Datenpunkts in einem kNN-Modell) in ein praktisches, schnelles Werkzeug.

Der alte Weg: Versuchen, jedes Sandkorn zu zählen (zu langsam, unmöglich).
Der neue Weg: Eine Karte verwenden, um nur die Körner zu zählen, die tatsächlich den Pfad berühren (schnell, genau).

Sie bewiesen, dass man für kNN-Modelle nicht den ganzen Universum an Suppenkombinationen probieren muss, um zu wissen, welche Zutat am wichtigsten ist. Man muss nur die Nachbarn betrachten.

Technische Zusammenfassung: Effiziente Banzhaf-basierte Datenbewertung für die $k$ -Nächste-Nachbarn-Klassifikation

Problemstellung

Die Datenbewertung, also die Aufgabe, den Beitrag einzelner Datenpunkte zur Modellleistung zu quantifizieren, stellt eine fundamentale Herausforderung im maschinellen Lernen dar. Obwohl spieltheoretische Ansätze wie der Banzhaf-Wert prinzipielle Rahmenwerke für eine faire Bewertung bieten, leiden sie unter exponentieller rechnerischer Komplexität. Die Berechnung exakter Banzhaf-Werte erfordert insbesondere die Auswertung der Wertefunktion über alle möglichen Teilmengen des Datensatzes, eine Aufgabe, die im Allgemeinen als #P-schwer nachgewiesen wurde. Diese rechnerische Last macht die exakte Berechnung für reale Datensätze mit Tausenden oder Millionen von Stichproben unpraktikabel und zwingt die meisten bestehenden Arbeiten dazu, auf Approximationsmethoden zurückzugreifen, die Genauigkeit zugunsten der Effizienz opfern.

Dieser Beitrag adressiert die spezifische Herausforderung der Berechnung exakter Banzhaf-Werte für $k$ -Nächste-Nachbarn-Klassifikatoren ( $k$ NN). Die Autoren zielen darauf ab, die Lücke zwischen den theoretischen Grundlagen der kooperativen Spieltheorie und den praktischen Anforderungen des maschinellen Lernens im realen Einsatz zu schließen, indem sie Algorithmen entwickeln, die die einzigartigen Lokalitätseigenschaften von $k$ NN ausnutzen, um signifikante rechnerische Verbesserungen zu erzielen, ohne auf Approximationen zurückgreifen zu müssen.

Methodik

Der Beitrag schlägt eine Suite von dynamischen Programmierungs (DP) Algorithmen vor, die auf das $k$ NN-Klassifikationsszenario zugeschnitten sind, sowie effiziente Monte-Carlo-Schätzverfahren.

1. Theoretische Härte

Die Autoren etablieren zunächst die theoretische Schwierigkeit des Problems. Sie beweisen, dass die Berechnung von Banzhaf-Werten für das $k$ NN-Klassifikationsmodell #P-schwer ist. Dies wird durch eine Reduktion vom Weighted-Majority-Game (WMG)-Problem demonstriert, einem klassischen #P-schweren Problem in der kooperativen Spieltheorie. Dieses Ergebnis impliziert, dass unter Standard-Komplexitätsannahmen kein Algorithmus mit stark polynomieller Laufzeit für den allgemeinen Fall existiert.

2. Dynamische Programmierungsrahmen

Trotz des Härteergebnisses nutzen die Autoren die Lokalitätseigenschaft von $k$ NN (bei der nur die $k$ nächsten Nachbarn die Vorhersage beeinflussen), um exakte Algorithmen mit verbesserter Zeitkomplexität zu entwickeln.

Standard-DP für gewichtete $k$ NN:
Die Autoren stellen zunächst einen DP-Algorithmus mit einer Zeitkomplexität von $O(W n^4)$ vor, wobei $n$ die Anzahl der Datenpunkte und $W$ die maximale Summe der Top- $k$ -Gewichte ist. Dieser Ansatz definiert eine Zustandsfunktion $f_i(w, s, m)$ , die die Anzahl der Teilmengen der Größe $s$ mit einer bestimmten Gewichtssumme $w$ und einem bestimmten $m$ -ten nächsten Punkt darstellt.
Verbesserte DP für gewichtete $k$ NN:
Um die Komplexität zu reduzieren, führen die Autoren neuartige Techniken ein:
- Teilsummen-Vorberechnung: Für den Fall, dass die Teilmengengröße $s \le k$ ist, berechnen sie Teilsummen vor, um die Rekursionsbeziehung zu beschleunigen und den Komplexitätsbeitrag dieses Terms zu verringern.
- Rekursion für Binomialkoeffizienten: Für $s > k$ nutzen sie Rekursionsbeziehungen von Binomialkoeffizienten, um die Summe der Zustände effizient zu berechnen.
- Ergebnis: Diese Optimierungen ergeben einen Algorithmus mit einer Zeitkomplexität von $O(W k n^2)$ .
Spezialisierte DP für ungewichtete $k$ NN:
Für den ungewichteten Fall (bei dem alle Gewichte 1 sind) schlagen die Autoren einen spezialisierten Algorithmus vor, der eine Zeitkomplexität von $O(n k^2)$ erreicht.
- Neugestaltung des Zustandsraums: Sie reduzieren den Zustandsraum, indem sie die Notwendigkeit eliminieren, die spezifische Identität des $m$ -ten nächsten Punkts zu verfolgen.
- Vorwärts- und Rückwärtsaggregation: Sie nutzen Vorwärtsfunktionen ( $f_i$ ) und Rückwärtsfunktionen ( $b_i$ ) sowie signierte Rückwärtsfunktionen ( $b^+_i, b^-_i$ ), um die Vorzeichen der Labels zu behandeln.
- Ergebnis: Da $k$ typischerweise eine kleine Konstante ist, läuft dieser Algorithmus in nahezu linearer Zeit bezüglich der Anzahl der Datenpunkte.

3. Monte-Carlo-Schätzung

In Anerkennung dessen, dass selbst quadratische Komplexität für massive Datensätze prohibitiv sein kann, bietet der Beitrag zwei effiziente stichprobenbasierte Methoden:

Koalitionsbasierte Stichprobenziehung: Optimierte durch Beibehaltung nur der Top $k+1$ Spieler in einer sortierten Liste, wodurch die Komplexität für $m$ Stichproben auf $O(m n \log k)$ reduziert wird.
Permutationsbasierte Stichprobenziehung: Passt die Permutationsformulierung von Banzhaf-Werten über ein Neugewichtungsschema an und erreicht ebenfalls eine Komplexität von $O(m n \log k)$ .

Hauptbeiträge

Härtebeweis: Der Beitrag beweist, dass die Berechnung von Banzhaf-Werten für $k$ NN-Klassifikatoren #P-schwer ist.
Erster exakter DP für gewichtete $k$ NN: Er stellt den ersten dynamischen Programmierungsalgorithmus zur Berechnung exakter Banzhaf-Werte in gewichteten $k$ NN-Klassifikatoren mit pseudo-polynomieller Zeitkomplexität vor.
Optimierter gewichteter Algorithmus: Er verbessert die Zeitkomplexität des gewichteten Algorithmus durch neuartige algorithmische Techniken, die Teilsummen und Binomialrekursionen beinhalten, signifikant auf $O(W k n^2)$ .
Nahezu linearer ungewichteter Algorithmus: Er führt einen spezialisierten Algorithmus für ungewichtete $k$ NN mit einer Zeitkomplexität von $O(n k^2)$ ein, der den ersten nahezu linearen Zeitalgorithmus zur Berechnung von spieltheoretischen Werten auf Basis von $k$ NN mit harten Labels darstellt.
Effiziente Stichprobenziehung: Er bietet optimierte koalitionsbasierte und permutationsbasierte Monte-Carlo-Methoden, die die $k$ NN-Lokalität für schnellere approximative Schätzungen ausnutzen.

Experimentelle Ergebnisse

Die Autoren führten umfangreiche Experimente auf 12 realen Datensätzen (mit Größen von 5.404 bis 1.000.000 Datenpunkten) und synthetischen Daten durch.

Rechnerische Effizienz:
- Der Brute-Force-Algorithmus schaffte es nicht, Datensätze mit nur 30 Punkten innerhalb von 10 Stunden zu vervollständigen.
- Der ungewichtete DP-Algorithmus (bv-uw) zeigte eine fast lineare Skalierung und bewältigte Datensätze mit bis zu $10^6$ Punkten innerhalb des Zeitbudgets.
- Der verbesserte gewichtete DP (bv-fast) skalierte bis zu $10^4$ Punkten und übertraf bestehende Hard-Label-Shapley-Baselines (sv, sv-uw), die für $n \ge 10^4$ keine Ausführungen abschließen konnten.
- Monte-Carlo-Methoden boten bei einer akzeptierten Abweichung von ungefähr 0,02 Geschwindigkeitssteigerungen von bis zu 25-fach gegenüber dem gewichteten DP.
Praktische Anwendungen:
- Punktentfernung: Das Entfernen von Datenpunkten mit den höchsten Banzhaf-Werten führte zu einem schärferen Abfall der Modellgenauigkeit im Vergleich zu anderen Methoden (wie LOO oder Einflussfunktionen), was darauf hindeutet, dass diese Punkte für die Leistung kritisch waren.
- Datenselektion: Die schrittweise Auswahl von Punkten mit den höchsten Werten verbesserte die Modellgenauigkeit schneller als eine zufällige Auswahl oder andere Baselines.
- Fehlbeschriftungserkennung: Die Studie hob einen Trade-off zwischen Bewertungstypen hervor. Soft-Label-Shapley-Werte waren besser darin, zufällig umgekippte Labels zu erkennen (hoher $F_1$ -Score). Allerdings waren Hard-Label-Banzhaf-Werte überlegen bei der Identifizierung entscheidender Punkte niedriger Qualität, deren Korrektur die Modellleistung erheblich verbesserte. Hard-Label-Werte waren robuster gegenüber Rauschen und besser für die Datenbereinigung geeignet, bei der das Ziel darin besteht, Punkte zu beheben, die tatsächlich Vorhersagen ändern.

Bedeutung und Behauptungen

Der Beitrag behauptet, die schnellsten Algorithmen für die Hard-Label-Banzhaf-Bewertung in $k$ NN bereitzustellen, die sogar die Effizienz ihrer Hard-Label-Shapley-Pendants übertreffen. Die Bedeutung liegt darin, die exakte spieltheoretische Datenbewertung für große Datensätze rechnerisch machbar zu machen, eine Aufgabe, die zuvor auf Approximationen beschränkt war.

Die Autoren betonen, dass der Banzhaf-Wert zwar ohne Normalisierung das Effizienzaxiom (die Summe der Werte entspricht dem Gesamtwert) nicht erfüllt, aber distincte praktische Vorteile bietet:

Sparsamkeit: Er erzeugt sparsamere Werte, die eine konzentrierte Menge einflussreicher Punkte hervorheben, was für exemplarbasierte Interpretierbarkeit vorteilhaft ist.
Robustheit: Er ist robuster gegenüber Rauschen und duplizierten Datenpunkten als Shapley-Werte, die gegenüber extremen Teilmengen überempfindlich sein können.
Praktikabilität: Die entwickelten Algorithmen ermöglichen die Anwendung rigoroser Datenbewertung in Szenarien wie Datenerwerb, Bereinigung und kollaborativem Lernen, wo das Verständnis der relativen Reihenfolge der Wichtigkeit von Datenpunkten entscheidend ist.

Der Beitrag schließt, dass das Framework zwar aufgrund nicht-dekomponierbarer Normalisierungsterme nicht direkt auf $k$ NN-Regression übertragbar ist, aber erfolgreich die Lücke zwischen kooperativer Spieltheorie und praktischen Anwendungen des maschinellen Lernens für Klassifikationsaufgaben schließt.