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

Die Arbeit stellt „Local Shapley" vor, ein Framework, das die inhärente Lokalität moderner Modelle nutzt, um die Shapley-Wert-Berechnung von einer exponentiell komplexen globalen Aufgabe auf effiziente, modellinduzierte Teilmenge-Prozesse zu reduzieren, und führt dabei den optimalen Algorithmus LSMR sowie dessen Monte-Carlo-Erweiterung LSMR-A ein, die die Anzahl notwendiger Neutraining-Schritte drastisch verringern, ohne die Genauigkeit zu beeinträchtigen.

Das Wesentliche

Stell dir vor, du hast eine riesige Bibliothek voller Bücher (das sind deine Trainingsdaten), und du möchtest ein neues, intelligentes Buch schreiben (das ist dein KI-Modell). Jetzt stellt sich die Frage: Welches der alten Bücher hat am meisten dazu beigetragen, dass dein neues Buch so gut ist?

Das ist das Problem der Datenbewertung. Eine sehr faire Methode, das zu berechnen, nennt man den Shapley-Wert. Aber hier liegt das Problem: Um genau zu berechnen, wie wichtig jedes einzelne Buch war, müsste man theoretisch jede denkbare Kombination von Büchern ausprobieren. Bei einer großen Bibliothek wäre das so, als würdest du versuchen, jeden möglichen Satz von Buchkombinationen im Universum durchzuprobieren. Das dauert länger als das Leben des Universums selbst – es ist rechnerisch unmöglich.

Die Autoren dieses Papers haben eine geniale Lösung gefunden, die sie „Local Shapley" nennen. Hier ist die Erklärung, wie das funktioniert, mit ein paar einfachen Vergleichen:

1. Das große Missverständnis: „Jeder kennt jeden"

Die alten Methoden gingen davon aus, dass jedes Buch in deiner Bibliothek für jede neue Frage wichtig sein könnte. Das ist wie bei einer riesigen Party, bei der man annimmt, dass jeder Gast mit jedem anderen Gast gesprochen hat, um die Stimmung zu beeinflussen.

Aber in der Realität ist das nicht so. Wenn du jemanden fragst: „Wie komme ich zum Bahnhof?", dann interessieren sich nur die Leute, die in der Nähe des Bahnhofs wohnen oder dort gearbeitet haben. Die Leute, die am anderen Ende der Stadt wohnen, haben keinen Einfluss auf diese spezifische Antwort.

2. Die Entdeckung: Der „Einflussbereich" (Support Set)

Die Autoren sagen: „Warte mal! Für jede einzelne Frage (Test-Datum) gibt es nur eine kleine Gruppe von Büchern (Datenpunkten), die wirklich wichtig sind."

• Bei einem KNN-Modell (Nachbarschafts-Modell): Nur die 5 nächsten Nachbarn zählen.
• Bei einem Entscheidungsbaum: Nur die Blätter, auf die der Pfad führt, zählen.
• Bei Graphen (wie sozialen Netzwerken): Nur die Freunde deiner Freunde zählen.

Sie nennen diese kleine, wichtige Gruppe den „Support" (den Einflussbereich). Statt die ganze Bibliothek zu durchsuchen, schauen wir nur in dieses kleine Regal. Das ist wie wenn man für eine Wegbeschreibung nur die Karte des Stadtteils betrachtet, in dem man sich gerade befindet, statt die ganze Weltkarte zu studieren.

3. Das Problem der doppelten Arbeit

Selbst wenn wir uns nur auf dieses kleine Regal beschränken, gibt es immer noch ein Problem. Stell dir vor, du hast 100 verschiedene Fragen. Für jede Frage schaust du in ein kleines Regal. Oft sind diese Regale aber fast identisch!

• Frage A braucht Bücher aus Regal 1.
• Frage B braucht fast dieselben Bücher aus Regal 1.

Die alten Methoden würden für Frage A das Regal 1 neu sortieren und für Frage B wieder das Regal 1 neu sortieren. Das ist extrem ineffizient. Es ist, als würde ein Koch für jeden Gast, der ein ähnliches Gericht bestellt, die Zutaten von Grund auf neu kaufen und schneiden, anstatt die vorbereiteten Schüsseln zu teilen.

4. Die Lösung: LSMR (Die „Wiederverwendungs-Maschine")

Hier kommt die eigentliche Innovation ins Spiel: LSMR (Local Shapley via Model Reuse).

Die Autoren haben einen cleveren Plan entwickelt, der sicherstellt, dass jede Kombination von Büchern nur einmal sortiert wird.

• Sie erstellen eine Art „Karte", die zeigt, welche Bücher für welche Fragen wichtig sind.
• Wenn eine neue Frage kommt, schauen sie: „Haben wir diese Kombination von Büchern schon einmal sortiert?"
• Ja? Super! Wir nehmen die Ergebnisse einfach wieder.
• Nein? Dann sortieren wir sie einmal und speichern das Ergebnis für alle zukünftigen Fragen, die diese Kombination brauchen.

Das ist wie ein Baukasten-System: Statt jedes Haus neu zu bauen, bauen wir einmal die Wände und das Dach und nutzen diese Teile für viele verschiedene Häuser. Das spart enorm viel Zeit und Energie.

5. Der Zufalls-Trick (LSMR-A)

Manchmal ist das kleine Regal trotzdem noch zu groß, um alles genau zu berechnen. Dann nutzen sie einen Zufalls-Trick (Monte-Carlo-Simulation). Aber auch hier wenden sie die „Wiederverwendungs"-Logik an.
Statt zufällige Kombinationen zu würfeln und jedes Mal neu zu kochen, würfeln sie, schauen nach, ob sie diese Kombination schon gekocht haben, und nutzen das Ergebnis. Das macht die Schätzung nicht nur schneller, sondern auch genauer, weil weniger „Rauschen" (zufällige Fehler) entsteht.

Zusammenfassung in einem Satz

Statt zu versuchen, jeden einzelnen Stein in einem riesigen Mauerwerk zu zählen, um zu sehen, wer den Bau am meisten unterstützt hat, schauen wir uns nur die relevanten Ecken an und teilen uns die Arbeit, sodass niemand zweimal denselben Stein schleppen muss.

Das Ergebnis:

• Schneller: Die Berechnung ist um ein Vielfaches schneller (manchmal tausendfach).
• Faire: Die Bewertung der Daten bleibt trotzdem sehr genau und fair.
• Praktisch: Man kann Daten jetzt endlich in großen Mengen bewerten, was für Datenmärkte, KI-Entwicklung und faire Bezahlung von Datenlieferanten entscheidend ist.

Kurz gesagt: Die Autoren haben den „Flaschenhals" der Datenbewertung gefunden und ihn durch kluges Organisieren und Wiederverwenden von Arbeit entfernt.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation" auf Deutsch.

1. Problemstellung

Die Datenbewertung (Data Valuation) zielt darauf ab, den Beitrag einzelner Trainingsdatenpunkte zur Leistung eines maschinellen Lernmodells fair und effizient zu quantifizieren. Der Shapley-Wert aus der kooperativen Spieltheorie gilt hierfür als theoretischer Goldstandard, da er faire Verteilungseigenschaften garantiert.

Das zentrale Problem ist jedoch die extreme Rechenkomplexität:

• Die exakte Berechnung des Shapley-Werts erfordert die Auswertung aller möglichen Teilmengen (Koalitionen) der Trainingsdaten.
• Da die Anzahl der Teilmengen exponentiell mit der Datengröße ($2^{|D|}$) wächst, ist die exakte Berechnung #P-schwer.
• Bestehende Beschleunigungsmethoden (z. B. Monte-Carlo-Sampling, Truncation) behandeln das Problem weiterhin global. Sie gehen implizit davon aus, dass jeder Trainingspunkt jeden Testpunkt durch Neutraining beeinflussen kann.
• Diese Annahme ignoriert eine strukturelle Eigenschaft moderner Vorhersagemodelle: Für eine gegebene Testinstanz ist oft nur ein kleiner, lokaler Teil der Trainingsdaten für die Vorhersage relevant (z. B. Nachbarn bei KNN, Blätter bei Entscheidungsbäumen, Receptive Fields bei GNNs).

Die Autoren identifizieren daher eine massive strukturelle Redundanz in der globalen Koalitionsraum-Berechnung, die ausgenutzt werden kann.

2. Methodik

Die Arbeit führt das Konzept der modellinduzierten Lokalität (Model-Induced Locality) ein und entwickelt darauf aufbauend zwei Algorithmen: LSMR (exakt) und LSMR-A (approximativ).

A. Modellinduzierte Lokalität und Support-Sets

Die Autoren definieren für jeden Testpunkt $t$ eine Support-Menge $N(t) \subseteq D$. Diese Menge enthält nur die Trainingsdatenpunkte, die den Pfad der Berechnung für $t$ im Modell tatsächlich beeinflussen (z. B. die $K$ nächsten Nachbarn bei KNN oder die Support-Vektoren bei SVM).

• Projektion: Der Nutzen $v_t(S)$ wird so projiziert, dass er nur von $S \cap N(t)$ abhängt.
• Theoretische Grundlage: Es wird bewiesen, dass die Abweichung zwischen dem globalen Shapley-Wert und dem lokalen Shapley-Wert durch die kumulierte Einflussstärke der Punkte außerhalb von $N(t)$ begrenzt ist. Bei stabilen Algorithmen ist dieser Fehler vernachlässigbar klein.

B. Intrinsische Komplexität und Untere Schranke

Ein zentraler theoretischer Beitrag ist die Erkenntnis, dass die Komplexität nicht durch die Gesamtzahl der Teilmengen bestimmt wird, sondern durch die Anzahl der unterschiedlichen, einflussreichen Teilmengen, die über alle Support-Sets hinweg auftreten.

• Es wird eine informationstheoretische untere Schranke für die Anzahl der notwendigen Neutraining-Operationen bewiesen: Jeder Algorithmus muss jede distincte einflussreiche Teilmenge mindestens einmal trainieren.

C. Der LSMR-Algorithmus (Exakt)

LSMR (Local Shapley via Model Reuse) ist ein exakter Algorithmus, der diese untere Schranke erreicht:

1. Subset-zentrische Reformulierung: Statt den Shapley-Wert pro Trainingspunkt zu berechnen, wird die Berechnung auf die Teilmengen (Subsets) der Support-Mengen umgestellt. Eine einzelne Evaluation einer Teilmenge aktualisiert gleichzeitig die Werte aller darin enthaltenen Punkte.
2. Globale Wiederverwendung (Reuse): Ein bipartiter Graph verknüpft Trainings- und Testpunkte. Eine Pivot-Scheduling-Strategie sorgt dafür, dass jede eindeutige Teilmenge $S$ über den gesamten Datensatz hinweg exakt einmal trainiert wird. Das Ergebnis wird dann für alle Testpunkte wiederverwendet, deren Support-Menge $S$ enthalten.
3. Ergebnis: LSMR eliminiert sowohl Redundanz innerhalb eines Supports als auch zwischen überlappenden Supports.

D. Der LSMR-A-Algorithmus (Approximativ)

Für große Support-Sets, wo eine vollständige Enumeration ($2^{|N(t)|}$) zu teuer ist, wird LSMR-A vorgeschlagen:

• Dies ist ein Wiederverwendungs-bewusster Monte-Carlo-Schätzer.
• Anstatt jede gezogene Teilmenge unabhängig zu behandeln, wird die Pivot-Regel angewendet: Eine gezogene Teilmenge wird nur dann trainiert, wenn der aktuelle Testpunkt der „Pivot" (der erste in einer globalen Reihenfolge) für diese Teilmenge ist.
• Statistische Garantien: Der Schätzer bleibt erwartungstreu (unbiased) und weist eine exponentielle Konzentration auf.
• Vorteil: Die Laufzeit hängt von der Anzahl der unterschiedlichen gezogenen Teilmengen ab, nicht von der Gesamtzahl der Ziehungen. Dies reduziert die Varianz signifikant, insbesondere bei Verteilungsverschiebungen (Distribution Shift), da irrelevante Punkte strukturell nicht gesampelt werden.

3. Wichtige Beiträge

1. Konzeptuelle Neuausrichtung: Formalisierung der „modellinduzierten Lokalität" als strukturelle Abstraktion, die den Shapley-Wert von der globalen auf die lokale Ebene projiziert, ohne Genauigkeit zu verlieren (bei exakter Lokalität).
2. Theoretische Untere Schranke: Beweis, dass die intrinsische Komplexität der Datenbewertung durch die Anzahl der distincten einflussreichen Teilmengen bestimmt wird, nicht durch die Größe des globalen Raums.
3. Optimaler Algorithmus (LSMR): Entwicklung eines exakten Algorithmus, der die informationstheoretische untere Schranke für Neutraining-Operationen erreicht, indem er Subsets global wiederverwendet.
4. Effiziente Approximation (LSMR-A): Ein Monte-Carlo-Schätzer, der Sampling-Komplexität von Neutraining-Komplexität entkoppelt und durch strukturelle Wiederverwendung die Varianz reduziert.
5. Breite Anwendbarkeit: Das Framework ist nicht auf KNN beschränkt, sondern gilt für Entscheidungsbäume, Kernel-Methoden, SVMs und Graph Neural Networks (GNNs).

4. Ergebnisse

Die Autoren evaluieren das Framework auf vier Modellfamilien (WKNN, Entscheidungsbäume, RBF-SVM, GNN) und verschiedenen Datensätzen (MNIST, Iris, Breast Cancer, Cora).

• Genauigkeit (Fidelity): Lokale Shapley-Werte korrelieren stark mit globalen Werten (Pearson-Korrelation bis zu 0,84 bei WKNN). Selbst bei approximativer Lokalität (z. B. GNN) bleibt die Korrelation positiv und signifikant.
• Downstream-Aufgaben (Datenauswahl): Bei der Aufgabe, die besten Trainingsdaten für das Neutraining auszuwählen, erreicht LSMR-A oft bessere oder gleichwertige Ergebnisse wie globale Methoden, benötigt aber deutlich weniger Daten, um die gleiche Genauigkeit zu erreichen.
• Effizienz (Laufzeit & Neutraining):
  • LSMR-A reduziert die Anzahl der erforderlichen Modell-Trainings um Größenordnungen (bis zu 3 Größenordnungen bei WKNN) im Vergleich zu globalen Monte-Carlo-Methoden.
  • Bei WKNN ist LSMR-A um den Faktor $10^5$ schneller als globale Baselines.
  • Die Skalierbarkeit ist überlegen: Während globale Methoden bei wachsender Datenmenge exponentiell langsamer werden, bleibt die Laufzeit von LSMR-A nahezu konstant oder wächst sublinear, da sich die Anzahl der distincten Teilmengen bei überlappenden Supports nicht linear erhöht.
• Robustheit: Die Methode ist robust gegenüber Verteilungsverschiebungen, da irrelevante Datenpunkte strukturell aus dem Sampling ausgeschlossen werden.

5. Bedeutung und Fazit

Das Paper stellt einen Paradigmenwechsel in der Datenbewertung dar. Es zeigt, dass das eigentliche Rechenproblem nicht die Exponentialität des globalen Raums ist, sondern die ineffiziente Behandlung von struktureller Redundanz.

• Theoretische Bedeutung: Es liefert die ersten informationstheoretischen Untergrenzen für die Komplexität der Shapley-Berechnung unter Berücksichtigung von Modellstruktur.
• Praktische Bedeutung: Es ermöglicht die Anwendung von Shapley-Werten auf große Datensätze und komplexe Modelle (wie GNNs), die bisher aufgrund der Rechenkosten unzugänglich waren.
• Zukunftsperspektive: Das Framework öffnet die Tür für effiziente, faire und skalierbare Datenbewertung in dynamischen und verteilten Umgebungen (Federated Learning), indem es die Datenbewertung als strukturiertes Datenverwaltungsproblem behandelt.

Zusammenfassend beweist die Arbeit, dass durch die Ausnutzung der inhärenten Lokalität moderner Modelle und die optimale Wiederverwendung von Berechnungen (Reuse) eine theoretisch optimale und praktisch skalierbare Datenbewertung möglich ist.