🤖 machine learning

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

Der Artikel stellt Quadrature-TreeSHAP vor, eine numerisch stabile, tiefenunabhängige Methode, die Path-Dependent TreeSHAP unter Verwendung der Gauss-Legendre-Quadratur neu formuliert, um Shapley-Werte und Wechselwirkungen höherer Ordnung effizient zu berechnen und dabei sowohl auf CPUs als auch auf GPUs erhebliche Geschwindigkeitssteigerungen zu erzielen.

Ursprüngliche Autoren: Ron Wettenstein, Rory Mitchell, Peng Yu

Veröffentlicht 2026-05-07

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Ron Wettenstein, Rory Mitchell, Peng Yu

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 eine sehr intelligente, aber komplizierte Entscheidungsmaschine (wie einen Baum, der Tausende von Ästen gewachsen ist). Sie möchten genau wissen, warum sie eine bestimmte Vorhersage getroffen hat. Hat sie „Ja" aufgrund von Merkmal A entschieden? Oder war es eine Teamleistung zwischen Merkmal B und Merkmal C?

Um dies zu beantworten, verwenden Datenwissenschaftler ein mathematisches Werkzeug namens SHAP. Denken Sie an SHAP als eine Möglichkeit, den „Beitrag" zur Vorhersage fair unter allen Merkmalen aufzuteilen, ähnlich wie man eine Pizza danach aufteilt, wer die meisten Zutaten mitgebracht hat.

Lange Zeit hatte die Standardmethode dafür (genannt TreeSHAP) drei Hauptprobleme:

Sie war langsam: Je tiefer der Baum wuchs, desto länger dauerte die Berechnung der Beiträge. Es war, als würde man versuchen, jedes einzelne Blatt an einer riesigen Eiche einzeln zu zählen.
Sie war wackelig: Je tiefer die Bäume wurden, desto unübersichtlicher und ungenauer wurde die Mathematik, ähnlich wie beim Versuch, einen Turm aus Jenga-Blöcken zu balancieren, der ständig wackelt.
Sie übersah das große Ganze: Sie war hervorragend darin, einzelne Merkmale zu erklären, aber sehr langsam und umständlich, wenn es darum ging, zu erklären, wie Merkmale zusammen wirken (Interaktionen).

Die Autoren dieses Papiers stellten eine neue Methode namens Quadrature-TreeSHAP vor. So funktioniert sie, unter Verwendung einfacher Analogien:

1. Der „Schnappschuss" versus der „Film"

Frühere Methoden versuchten, den Beitrag zu berechnen, indem sie Schritt für Schritt jeden einzelnen Pfad des Baumes durchgingen. Wenn der Baum tief war, dauerte dies ewig.

Quadrature-TreeSHAP ändert das Spiel. Anstatt den gesamten Baum zu durchlaufen, behandelt es die Berechnung wie einen Film. Es erkennt, dass die Mathematik hinter dem Baum tatsächlich eine glatte, vorhersagbare Kurve (ein Polynom) ist.

Anstatt den gesamten Film Bild für Bild anzusehen, nimmt diese neue Methode 8 spezifische „Schnappschüsse" (mathematisch Quadraturpunkte genannt) der Kurve auf.

Die Magie: Die Autoren bewiesen, dass für diese Baummodelle das Aufnehmen von nur 8 Schnappschüssen ausreicht, um den gesamten Film mit perfekter Genauigkeit wiederherzustellen.
Das Ergebnis: Es spielt keine Rolle, ob der Baum 10 Ebenen tief oder 100 Ebenen tief ist. Die Methode benötigt immer noch genau dieselben 8 Schnappschüsse. Sie ignoriert die Tiefe vollständig, was sie unglaublich schnell und konsistent macht.

2. Die „Stabile Brücke"

Die alte Methode war wie der Bau einer Brücke aus wackeligen, unebenen Bohlen. Je länger die Brücke wurde (tiefere Bäume), desto mehr verschoben sich die Bohlen, und die Mathematik brach zusammen (numerische Instabilität).

Die neue Methode baut die Brücke aus glatten, massiven Beton. Indem sie die Antwort an diesen 8 festen Punkten berechnet, vermeidet sie die „wackeligen Bohlen" vollständig. Das Ergebnis ist eine Berechnung, die selbst auf den tiefsten und komplexesten Bäumen perfekt stabil bleibt.

3. Die „Teamwork"-Superkraft

Die alte Methode hatte Schwierigkeiten zu erklären, wie Merkmale zusammenwirkten (z. B. „Merkmal A und Merkmal B zusammen verursachten das Ergebnis"). Es war, als würde man versuchen, zu zählen, wie viele Personen sich in einem Raum befinden, indem man sie bittet, sich in Zweiergruppen, dann Dreiergruppen und dann Vierergruppen aufzustellen – es wurde exponentiell langsamer.

Quadrature-TreeSHAP bewältigt dies mühelos. Da sie denselben „8-Schnappschuss"-Trick für Gruppen beliebiger Größe verwendet, kann sie komplexe Teamwork-Interaktionen (3-fach, 4-fach oder sogar 6-fach) fast augenblicklich berechnen.

Die Geschwindigkeit: In ihren Tests war die Berechnung dieser komplexen Interaktionen bis zu 1.200-mal schneller als die bisher beste Methode.

4. Das „Fließband" (Hardware-Effizienz)

Schließlich machten die Autoren diese Methode für moderne Computerchips (CPUs und GPUs) kompatibel.

Die Analogie: Stellen Sie sich eine Fabrik-Fließband vor. Die alte Methode war wie ein Arbeiter, der für jedes einzelne Item anders anhalten und nachdenken musste. Die neue Methode ist wie eine Maschine, die 8 Items zur exakt gleichen Zeit in einem perfekten Rhythmus verarbeitet.
Das Ergebnis: Da die Mathematik so regelmäßig ist, läuft sie sowohl auf Standardcomputern als auch auf leistungsstarken Grafikkarten (GPUs) extrem effizient, was zu Geschwindigkeitssteigerungen von bis zu 10-fach auf Standardcomputern und 7-fach auf Grafikkarten führt.

Zusammenfassung der Ergebnisse

Die Autoren testeten dies an 12 verschiedenen realen Datensätzen (wie der Vorhersage von Immobilienpreisen oder der Identifizierung von Objekten auf Fotos).

Geschwindigkeit: Sie ist durchgängig schneller als die alten Methoden, manchmal um den Faktor 10.
Stabilität: Sie bricht nicht zusammen oder wird ungenau, selbst auf sehr tiefen Bäumen, bei denen die alten Methoden versagten.
Übernahme: Sie haben dies bereits in XGBoost integriert, eines der beliebtesten Machine-Learning-Tools der Welt. Wenn Sie XGBoost in Zukunft verwenden, wird diese neue, schnellere und stabilere Art, Ihre Modelle zu erklären, direkt eingebaut sein.

Kurz gesagt: Quadrature-TreeSHAP ist wie der Upgrade von einem langsamen, wackeligen, manuellen Rechner zu einem Hochgeschwindigkeits-, superstabilen digitalen Computer, der komplexe Teamwork-Rätsel im Handumdrehen lösen kann.

Technischer Überblick: Quadrature-TreeSHAP

Problemstellung

Die Erklärbarkeit von Ensemble-Modellen auf Basis von Entscheidungsbäumen (z. B. XGBoost, Random Forests) stützt sich stark auf Shapley-Werte. Während Path-Dependent SHAP aufgrund seiner Effizienz der Standardansatz ist, bestehen bei den vorhandenen Methoden erhebliche Kompromisse hinsichtlich laufzeitabhängiger Tiefe, numerischer Stabilität und Unterstützung höherer Ordnungen von Interaktionen.

Der aktuelle Stand der Technik weist spezifische Einschränkungen auf:

TreeSHAP und GPUTreeSHAP arbeiten mit einer Zeitkomplexität von $O(MTLD^2)$ (wobei $M$ die Anzahl der Stichproben, $T$ die Anzahl der Bäume, $L$ die Anzahl der Blätter und $D$ die Tiefe bezeichnet).
FastTreeSHAP v2 und Woodelf reduzieren die Komplexität auf $O(MTLD)$, führen jedoch Vorverarbeitungsschritte ein, die exponentiell mit der Tiefe skalieren, was sie für tiefe Bäume unpraktisch macht.
Linear TreeSHAP erreicht $O(MTND)$, leidet jedoch aufgrund von Operationen in der Monombasis unter numerischer Instabilität.
TreeGrad-Shap verbessert die Stabilität durch Gradientenformulierungen, ist jedoch auf Attributionen erster Ordnung beschränkt.
TreeSHAP-IQ erweitert die Methode auf Interaktionen höherer Ordnung, weist jedoch eine Komplexität von $O(MTLD \binom{F-1}{s-1})$ auf, die sich bei steigender Anzahl von Merkmalen ( $F$ ) und Interaktionsordnung ( $s$ ) schlecht skaliert.

Methodik

Die Autoren schlagen Quadrature-TreeSHAP vor, eine Reformulierung von Path-Dependent TreeSHAP, die auf Gauss-Legendre-Quadratur und einem gewichteten Banzhaf-Interaktionspolynom basiert.

1. Theoretische Grundlage

Die Methode nutzt die Beziehung zwischen Shapley-Werten und gewichteten Banzhaf-Werten.

Gewichtetes Banzhaf-Polynom: Für ein Blatt $v$ eines Entscheidungsbaums wird der path-abhängige gewichtete Banzhaf-Interaktionswert für eine Teilmenge von Merkmalen $S$ bei einer Einbeziehungswahrscheinlichkeit $p$ als Polynom $B^{(S)}_{p,v}$ ausgedrückt. Dieses Polynom wird aus der Pfadstruktur des Blattes und den Kantengewichten abgeleitet.
Integralwiederherstellung: Shapley-Interaktionswerte werden durch Integration dieser Banzhaf-Polynome über die Beteiligungswahrscheinlichkeit $p \in [0, 1]$ wiederhergestellt:
$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$
Quadraturapproximation: Anstelle einer symbolischen Integration bewerten die Autoren dieses Integral mittels Gauss-Legendre-Quadratur. Das Integral wird als gewichtete Summe des Polynoms, ausgewertet an festen Knoten $t_m$ , angenähert:
$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$

2. Algorithmische Implementierung

Fixpunkt-Formulierung: Der Algorithmus führt eine einzige Tiefensuche (DFS) durch den Baum aus. Während der Durchlauf werden die Werte des Pfadpolynoms an einem festen Satz von Gauss-Legendre-Knoten (typischerweise 8) propagiert, anstatt Polynome symbolisch zu erweitern.
Komplexitätsreduktion:
- Theoretisch beträgt der Grad des Integranden für Interaktionen der Ordnung $s$ höchstens $d-s$ (wobei $d$ die maximale Anzahl eindeutiger Merkmale auf einem Pfad ist).
- Praktisch zeigen die Autoren, dass 8 feste Quadraturpunkte ausreichen, um die Maschinenpräzision (float32) selbst für sehr tiefe Bäume zu erreichen.
- Dies entfernt die Abhängigkeit von der Baumbreite $d$ aus der inneren Berechnung und reduziert die effektive Komplexität von $O(MTN \lceil d/2 \rceil)$ auf $O(MTN)$ für die erste Ordnung sowie von $O(MTN d^s)$ auf $O(MTN d^{s-1})$ für Interaktionen der Ordnung $s$ .
Hardware-Beschleunigung: Da die Berechnung die Auswertung desselben festen Punktesatzes für jeden Pfad beinhaltet, ist die Arithmetik regelmäßig. Dies ermöglicht eine effiziente SIMD-Ausführung (Single Instruction, Multiple Data) auf CPUs und SIMT (Single Instruction, Multiple Threads) auf GPUs und eliminiert den für GPUTreeSHAP erforderlichen Overhead durch Bin-Packing und Scheduling.

Hauptbeiträge

Algorithmus für Interaktionen beliebiger Ordnung: Die Arbeit stellt einen Algorithmus zur Berechnung von Shapley-Interaktionswerten beliebiger Ordnung vor, der die State-of-the-Art-Komplexität von TreeSHAP-IQ von $O(MTLD \binom{F-1}{s-1})$ auf $O(MTN d^s)$ verbessert. Dies führt zu erheblichen Gewinnen, wenn die Anzahl der Merkmale die Baumbreite übersteigt ( $F > D \ge d$ ).
Quadraturbasierte Reformulierung: Die Autoren liefern eine theoretische und empirische Analyse, die zeigt, dass 8 Gauss-Legendre-Punkte ausreichen, um für Shapley-Werte und -Interaktionen die Maschinenpräzision zu erreichen, wodurch die Laufzeit in der Praxis effektiv von der Baumbreite entkoppelt wird.
Numerische Stabilität: Durch die Auswertung des Zusammenfassungspolynoms an beschränkten, positiven Knoten anstatt der Erweiterung von Koeffizienten in einer Monombasis vermeidet die Methode katastrophale Auslöschung. Die Autoren behaupten, dass Quadrature-TreeSHAP numerisch stabiler ist als TreeSHAP, insbesondere für tiefe Ensembles.
Hardware-effiziente Implementierung: Die Methode ist in C++ für CPUs implementiert und in XGBoost für GPUs integriert. Sie nutzt Vektorisierung (4 Punkte auf der CPU, 32 auf der GPU), um signifikante Beschleunigungen gegenüber bestehenden Implementierungen zu erzielen.
Open-Source-Integration: Die Implementierung ist Open Source und in die XGBoost-Bibliothek integriert (ersetzt das TreeSHAP-Backend) und über Standard-API-Aufrufe (pred_contribs=True und pred_interactions=True) zugänglich.

Experimentelle Ergebnisse

Die Autoren bewerteten Quadrature-TreeSHAP an 12 XGBoost-Benchmark-Ensembles (Adult, CalHousing, CovType, Fashion-MNIST) in kleinen, großen und spärlichen Regimen.

Erste Ordnung (Shapley-Werte):
- CPU: 1,06× bis 10,59× schneller als TreeSHAP (Median 3,84×).
- GPU: 1,84× bis 6,95× schneller als GPUTreeSHAP.
Zweite Ordnung (Paarweise Interaktionen):
- CPU: 3,80× bis 58,11× schneller als TreeSHAP (Median 12,86×).
- GPU: Bis zu 6,65× schneller als GPUTreeSHAP (obwohl GPUTreeSHAP bei spezifischen Workloads mit geringer Tiefe wettbewerbsfähig blieb).
Interaktionen höherer Ordnung (Python-Benchmarks):
- Im Vergleich zu TreeSHAP-IQ bei Interaktionen dritter Ordnung war Quadrature-TreeSHAP 18,73× bis 26,49× schneller.
- Auf dem spärlichen CovType-Datensatz nahm der Speedup gegenüber TreeSHAP-IQ mit der Interaktionsordnung zu und erreichte bei Ordnung 6 1209,37×.
Numerische Stabilität:
- Beim Fashion-MNIST-spärlichen Benchmark mit zunehmender Baumbreite wurde TreeSHAP jenseits der Tiefe 32 instabil. Quadrature-TreeSHAP blieb stabil, wobei 6–8 Punkte eine hohe Genauigkeit erreichten.

Bedeutung

Die Arbeit behauptet, dass Quadrature-TreeSHAP eine numerisch stabile, hardware-effiziente und interaktionsbewusste Reformulierung von Path-Dependent SHAP bietet. Durch den Wechsel von symbolischer Polynomarithmetik zu Fixpunkt-Quadratur löst die Methode den Kompromiss zwischen Tiefenabhängigkeit und numerischer Stabilität. Sie ermöglicht die effiziente Berechnung von Interaktionen höherer Ordnung auf tiefen Bäumen, eine Aufgabe, die zuvor durch die exponentielle Komplexität oder Instabilität früherer Methoden behindert wurde. Die Integration in XGBoost gewährleistet einen unmittelbaren praktischen Nutzen für Benutzer der Bibliothek und des breiteren shap-Pakets.