📊 statistics

Fast approximate estimation of conditional Shapley values when using a linear explainer

Dieses Paper führt drei neue Methoden ein, einschließlich eines exakten Ansatzes und zweier approximativer Ansätze, die die Theorie der beschränkten Gaußschen Markov-Random-Felder sowie die dünnbesetzte Matrixalgebra nutzen, um bedingte Shapley-Werte für lineare Modelle durch die gleichzeitige Berechnung aller Teilmodelle schnell und präzise zu schätzen, wodurch die Rechenzeit im Vergleich zu bestehenden sequentiellen oder iterativen Techniken signifikant reduziert wird, während gleichzeitig die Genauigkeit beibehalten oder verbessert wird.

Ursprüngliche Autoren: Fredrik Lohne Aanes

Veröffentlicht 2026-07-28

📖 3 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Fredrik Lohne Aanes

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 versuchen herauszufinden, warum eine bestimmte Vorhersage von einem komplexen Computerprogramm getroffen wurde, wie etwa einem System zur Kreditgenehmigung oder einem Werkzeug zur medizinischen Diagnose. Sie wollen wissen: „Wie viel hat Ihr Alter beigetragen? Wie viel hat Ihr Einkommen beigetragen?“ In der Welt der Datenwissenschaft wird dies als das Finden von „Shapley-Werten“ bezeichnet. Denken Sie an ein Teamprojekt, bei dem jeder eine Note erhält, aber Sie müssen genau berechnen, wie viel Anerkennung jedes einzelne Teammitglied für die Endnote verdient. Der schwierige Teil dabei ist, dass diese Teammitglieder (die Datenmerkmale) oft aufeinander angewiesen sind. Wenn Sie wissen, dass jemand groß ist, könnten Sie vermuten, dass er älter ist, also können Sie sie nicht einfach isoliert betrachten; Sie müssen sehen, wie sie zusammenwirken.

Um dies mathematisch zu lösen, verwenden Wissenschaftler einen „linearen Erklärer“, was im Wesentlichen ein Werkzeug ist, das viele kleine, einfache Modelle erstellt, um zu sehen, wie sich die Vorhersage verändert, wenn man verschiedene Informationsstücke hinzufügt oder entfernt. Es gibt jedoch ein massives Problem: Wenn man 20 verschiedene Informationseinheiten hat, ist die Anzahl der möglichen Kombinationen, die man prüfen müsste, über eine Million ( $2^{20}$ ). Der Versuch, ein Modell für jede einzelne Kombination nacheinander zu erstellen, ist so, als würde man versuchen, jedes Sandkorn an einem Strand zu zählen, indem man sie einzeln aufhebt. Das dauert ewig, und Computer bleiben oft hängen oder laufen aus dem Speicher. Dies ist der Flaschenhals, der die Erklärung komplexer KI-Vorhersagen so langsam und schwierig macht.

Dieses Papier, geschrieben von Fredrik Lohne Aanes, führt einen cleveren neuen Weg vor, um dieses Zählproblem zu lösen. Anstatt eine Million Modelle einzeln zu erstellen, schlägt der Autor vor, ein riesiges „Super-Modell“ zu bauen, das alle kleineren Modelle gleichzeitig enthält, unter Verwendung einiger ausgeklügelter mathematischer Tricks mit „dünnbesetzten Matrizen“ (sparse matrices – das sind im Grunde Zahlengitter, bei denen die meisten Stellen leere Nullen enthalten). Das Papier schlägt drei neue Methoden vor, um diese Werte schnell zu schätzen. Zwei davon sind „approximativ“, was bedeutet, dass sie eine mathematische Abkürzung nutzen, um das Ergebnis fast perfekt zu erhalten, während die dritte Methode „exakt“ ist, was bedeutet, dass sie das Ergebnis perfekt ohne Abkürzungen liefert.

Der Autor testete diese neuen Methoden gegen die aktuelle Standardsoftware (genannt shapr) unter Verwendung von realen Daten über Einkommen von Erwachsenen, simulierten Daten und globalen Statistiken zur Lebenserwartung. Die Ergebnisse waren beeindruckend. In Fällen, in denen die alte Software Stunden brauchte, um die Werte zu berechnen, weil sie fast jede mögliche Kombination prüfen musste, erledigten die neuen Methoden die Aufgabe in Sekunden oder Minuten. Beispielsweise dauerte die alte Methode beim Datensatz über das Einkommen von Erwachsenen etwa 17 bis 19 Minuten, während die neuen Methoden zwischen 2,5 und 9 Sekunden benötigten. Selbst in einer Simulation, in der die alte Methode schnell war, weil sie nur wenige Kombinationen prüfte, schafften es die neuen Methoden sogar, alle 2 Millionen möglichen Kombinationen in weniger als drei Minuten zu prüfen.

Das Papier legt nahe, dass die approximativen Methoden zwar unglaublich schnell sind, die „Exact transformation method“ jedoch die beste Wahl ist, da sie keine Einstellregler benötigt, um angepasst zu werden, und Ergebnisse liefert, die genauso genau sind wie die der anderen. Der Autor kommt zu dem Schluss, dass wir durch die Verwendung dieser neuen Techniken komplexe Modelle viel schneller erklären können, selbst wenn wir mit vielen verschiedenen Variablen zu tun haben, ohne dabei die Genauigkeit zu opfern. Es ist so, als würde man einen langsamen, manuellen Zählprozess gegen einen Hochgeschwindigkeitsscanner austauschen, der den gesamten Strand mit einem einzigen Blick erfasst.

Technisches Resümee: Schnelle approximative Schätzung bedingter Shapley-Werte mit linearen Erklärern

Problemstellung

Die Arbeit adressiert den Rechenengpass bei der Schätzung bedingter Shapley-Werte für lineare Regressionsmodelle, wenn die Kovariaten abhängig sind. Während Shapley-Werte eine spieltheoretische Aufschlüsselung der Merkmalsbeiträge zu einer spezifischen Vorhersage liefern, erfordert die Berechnung der bedingten Werte die Schätzung des erwarteten Modellausgangs für alle möglichen Teilmengen (Koalitionen) von Merkmalen.

Für ein Modell mit $p$ Prädiktoren gibt es $2^p$ mögliche Koalitionen. Bestehende Methoden, wie die sequenzielle und iterative Ansätze im R-Paket shapr, stehen vor erheblichen Herausforderungen:

Sequenzielle Schätzung: Erfordert das Anpassen von $2^p$ separaten Regressionsmodellen, was mit steigendem $p$ rechnerisch untragbar wird.
Iterative Schätzung: Stichproben aus Koalitionen ziehen, bis ein Konvergenzkriterium erfüllt ist. Obwohl dies schneller sein kann, wenn nur wenige Koalitionen ausreichen, kann es in schwierigen Fällen immer noch einen großen Bruchteil aller $2^p$ Koalitionen erfordern, was zu Laufzeiten (Stunden) führt, die mit der sequenziellen Methode vergleichbar sind.
Merkmalsabhängigkeit: Im Gegensatz zu marginalen Shapley-Werten müssen bedingte Werte die Abhängigkeitsstruktur unter den Kovariaten berücksichtigen, was komplexe Berechnungen der bedingten Erwartungswerte erfordert.

Die Autoren zielen darauf ab, Methoden zu entwickeln, die die Koeffizienten für alle $2^p$ Submodelle gleichzeitig und schnell schätzen können, indem sie die Sparsamkeit der zugrunde liegenden mathematischen Strukturen nutzen.

Methodik

Der vorgeschlagene Ansatz nutzt die Theorie der Constraint Gaussian Markov Random Fields (GMRF) und die dünnbesetzte Matrixalgebra (sparse matrix algebra), um die Regressionskoeffizienten für alle Submodelle gemeinsam statt sequenziell zu schätzen. Die Autoren leiten drei verschiedene Algorithmen ab:

1. Die Diagonal-Korrektur-Methode (Approximativ)

Diese Methode approximiert die eingeschränkte Regression, indem sie die Präzisionsmatrix ( $Q = X^T X$ ) des Vollmodells modifiziert.

Mechanismus: Um eine Beschränkung durchzusetzen, bei der ein bestimmter Koeffizient Null sein muss (d. h. das Merkmal ist in einem Submodell ausgeschlossen), wird ein großer Skalarwert $\kappa$ zum entsprechenden Diagonalelement der Präzisionsmatrix hinzugefügt.
Theoretische Basis: Basierend auf der Woodbury-Matrix-Identität approximiert das Hinzufügen von $\kappa A^T A$ (wobei $A$ eine Beschränkungsmatrix ist) zur Präzisionsmatrix $Q$ die bedingte Kovarianzmatrix für $\kappa \to \infty$ .
Implementierung: Eine gemeinsame Beschränkungsmatrix $A$ wird für alle $2^p$ Modelle konstruiert. Die Methode löst das lineare System $(Q_F + \kappa A^T A)^{-1}m$ , wobei $Q_F$ eine Blockdiagonalmatrix ist, die die Präzisionsmatrix des Vollmodells $2^p$ -mal wiederholt.
Tuning: Erfordert einen Tuning-Parameter $\kappa$ , der als das $10^5$ -fache des größten Eigenwerts der ursprünglichen Präzisionsmatrix vorgeschlagen wird.

2. Die Projektionsmethode (Approximativ)

Diese Methode projiziert den Parameterraum, um beschränkte Parameter zu entfernen.

Mechanismus: Eine Projektionsmatrix $Z = I - A^T A$ wird auf die Präzisionsmatrix angewendet. Das beschränkte Modell wird als intrinsisches GMRF behandelt. Um die numerische Stabilität (positive Definitheit) zu gewährleisten, wird ein kleiner Skalar $\epsilon$ zur projizierten Präzisionsmatrix (diagonal) hinzugefügt ( $Z Q Z + \epsilon I$ ).
Theoretische Basis: Wenn $\epsilon \to 0^+$ , konvergiert die Lösung gegen die exakten Schätzwerte.
Implementierung: Löst das System $Z(Z Q_F Z + \epsilon I)^{-1} Z m$ .
Tuning: Erfordert einen kleinen Tuning-Parameter $\epsilon$ (z. B. $10^{-5}$ ), der klein im Verhältnis zum kleinsten Eigenwert von $Q$ , aber groß genug für eine stabile Cholesky-Zerlegung gewählt wird.

3. Die Exakte Transformationsmethode (Exakt)

Diese Methode liefert eine exakte Lösung ohne Approximationsfehler oder Tuning-Parameter.

Mechanismus: Anstatt im vollen Parameterraum zu arbeiten und Koeffizienten zu Null zu erzwingen, transformiert diese Methode das Problem in einen niederdimensionalen Raum, der nur die nicht-Null-Parameter enthält.
Implementierung: Eine Mapping-Matrix $E$ wird konstruiert, um nur die aktiven Parameter für jedes Submodell auszuwählen. Das System wird als $(E Q_F E^T)^{-1} E m$ gelöst.
Vorteil: Eliminiert die Notwendigkeit für große Strafterme ( $\kappa$ ) oder kleine Regularisierungsterme ( $\epsilon$ ) und vermeidet so potenzielle numerische Instabilität oder Approximationsbias.

Alle drei Methoden nutzen dünnbesetzte Matrixalgebra (insbesondere die Cholesky-Zerlegung), um die gemeinsame Schätzung von Tausenden von Modellen effizient zu handhaben. Die gemeinsame Präzisionsmatrix ist hochgradig dünnbesetzt, da die Modelle unabhängig sind (Blockdiagonalstruktur) und die Off-Diagonal-Nullen auf bedingte Unabhängigkeit hinweisen.

Wichtigste Beiträge

Drei neue Algorithmen: Das Paper führt zwei approximative Methoden (Diagonal-Korrektur, Projektion) und eine exakte Methode (Exakte Transformation) für die gemeinsame Schätzung aller Submodelle in der linearen Regression ein.
Konvergenzbeweise: Die Autoren liefern mathematische Beweise, die zeigen, dass die approximativen Methoden mit ihren jeweiligen Tuning-Parametern ( $\kappa \to \infty$ und $\epsilon \to 0^+$ ) gegen die wahren bedingten Schätzwerte konvergieren.
Recheneffizienz: Durch die Nutzung von Sparsity und der gemeinsamen Schätzung reduzieren die Methoden die Rechenzeit von Stunden (typisch für shapr) auf Sekunden oder Minuten, selbst wenn alle $2^p$ Koalitionen aufgeführt werden.
Empirische Validierung: Umfangreiche numerische Studien vergleichen die neuen Methoden mit dem shapr-Paket (sowohl sequenziell als auch iterativ) über drei Datensätze: Adult Income, ein simuliertes Gauß-Datenset und das WHO Life Expectancy Dataset.

Ergebnisse

Die numerischen Fallstudien liefern folgende Erkenntnisse:

Genauigkeit: Die von den neuen Methoden produzierten Shapley-Wert-Schätzungen sind nahezu identisch mit der sequenziellen Methode in shapr (die als Ground Truth für die vollständige Enumeration dient).
- Im Adult-Datensatz ( $p=11$ ) lag der Median Absolute Error (MedAE) zwischen den neuen Methoden und der sequenziellen Methode bei etwa $10^{-9}$ .
- Im simulierten Datensatz ( $p=21$ ) lag der MedAE im Bereich von $10^{-7}$ bis $10^{-5}$ .
- Im WHO-Datensatz ( $p=16$ ) lag der MedAE im Bereich von $10^{-6}$ .
Geschwindigkeit:
- Adult-Datensatz: Die neuen Methoden liefen in 2,5 bis 9 Sekunden, während shapr (Sequenziell und Iterativ) 17 bis 19 Minuten dauerte.
- Simulierter Datensatz: Die neuen Methoden benötigten 1,4 bis 2,5 Minuten, um alle $2^{21} \approx 2,1$ Millionen Modelle zu schätzen. Die shapr-Iterative Methode war mit 6,48 Sekunden schneller, schätzte jedoch nur 200 Koalitionen, nicht den gesamten Satz.
- WHO-Datensatz: Die neuen Methoden dauerten 1,1 bis 1,2 Minuten. Die shapr-Sequenzielle Methode dauerte 131 Minuten (2,2 Stunden), und die Iterative Methode dauerte 16 Minuten (parallel) bzw. 36 Minuten (seriell).
Skalierbarkeit: Die Methoden schätzten erfolgreich über zwei Millionen Submodelle in der simulierten Studie innerhalb von Minuten. Die primäre Identifizierte Einschränkung ist der Speicherbedarf (Fluch der Dimensionalität), wenn $p$ auf Standardhardware etwa 21 überschreitet, obwohl die Autoren anmerken, dass dies durch mehr RAM oder spezialisierte Sparse-Matrix-Pakete gemildert werden kann.

Bedeutung und Behauptungen

Das Paper behauptet, dass die vorgeschlagenen Methoden eine erhebliche Verbesserung der Recheneffizienz bei der Schätzung bedingter Shapley-Werte für lineare Modelle bieten, ohne die Genauigkeit zu beeinträchtigen.

Überlegenheit bei der vollständigen Enumeration: Wenn die shapr-Iterative Methode eine große Anzahl von Koalitionen benötigt, um zu konvergieren (wie in den Adult- und WHO-Datensätzen zu sehen), sind die neuen Methoden "erheblich schneller", während sie eine "gleiche oder bessere Genauigkeit" beibehalten.
Umfassende Enumeration: Im Gegensatz zum iterativen Ansatz, der Koalitionen stichprobenartig zieht, liefern die neuen Methoden eine vollständige Enumeration aller $2^p$ Submodelle und stellen sicher, dass durch Sampling keine Informationen verloren gehen.
Empfehlung: Die Autoren empfehlen die Exakte Transformationsmethode für die praktische Anwendung. Obwohl alle drei Methoden vergleichbare Ergebnisse liefern, benötigt die exakte Methode keine Tuning-Parameter, wodurch die Notwendigkeit der Hyperparameter-Auswahl und potenzielle Quellen für Approximationsfehler entfallen.
Zukünftiges Potenzial: Die Autoren deuten an, dass die Methodik auf Splines (z. B. aus dem rms-Paket) ausgeweitet werden kann und dass eine Parallelisierung (z. B. via OpenMP) die Laufzeiten weiter reduzieren könnte, obwohl die aktuelle Implementierung für einen fairen Vergleich mit dem parallelisierten shapr-Paket auf serieller Ausführung beruht.

Das Paper schließt damit ab, dass diese Methoden die exakte Berechnung bedingter Shapley-Werte für lineare Modelle mit gemischten Kovariattypen in Szenarien machbar machen, in denen dies zuvor rechnerisch prohibitiv war.