Technische Samenvatting: Snelle benaderende schatting van conditionele Shapley-waarden met lineaire explainers

Probleemstelling

Het artikel behandelt de computationele flessenhals die gepaard gaat met het schatten van conditionele Shapley-waarden voor lineaire regressiemodellen wanneer covariaten afhankelijk zijn. Hoewel Shapley-waarden een speltheoretische uitsplitsing bieden van de bijdragen van kenmerken aan een specifieke voorspelling, vereist het conditioneel berekenen ervan de schatting van de verwachte modeloutput voor alle mogelijke subsets (coalities) van kenmerken.

Voor een model met $p$ predictoren zijn er $2^p$ mogelijke coalities. Bestaande methoden, zoals de Sequentiële en Iteratieve benaderingen in het shapr R-pakket, kampen met aanzienlijke uitdagingen:

1. Sequentiële schatting: Vereist het fitten van $2^p$ afzonderlijke regressiemodellen, wat computationeel onuitvoerbaar wordt naarms de $p$ toeneemt.
2. Iteratieve schatting: Samplet coalities totdat een convergentiecriterium wordt bereikt. Hoewel dit sneller is wanneer weinig coalities volstaan, kan het nog steeds een groot deel van alle $2^p$ coalities vereisen om convergentie te bereiken, wat leidt tot lange looptijden (uren) die vergelijkbaar zijn met de sequentiële methode in moeilijke gevallen.
3. Kenmerkafhankelijkheid: In tegenstelling tot marginale Shapley-waarden moeten conditionele waarden rekening houden met de afhankelijkheidsstructuur tussen covariaten, wat complexe berekeningen van conditionele verwachtingen noodzakelijk maakt.

De auteurs streven ernaar methoden te ontwikkelen die de coëfficiënten voor alle $2^p$ submodellen gelijktijdig en snel kunnen schatten, door gebruik te maken van de spaarzaamheid van de onderliggende wiskundige structuren.

Methodologie

De voorgestelde aanpak maakt gebruik van de theorie van Constrained Gaussian Markov Random Fields (GMRF) en spaarse matrixalgebra om de regressiecoëfficiënten voor alle submodellen gezamenlijk in plaats van sequentieel te schatten. De auteurs leiden drie verschillende algoritmen af:

1. De Diagonaal Correctie Methode (Benaderend)

Deze methode benadert de geconstraineerde regressie door de precisie-matrix ($Q = X^T X$) van het volledige model te modificeren.

• Mechanisme: Om een restrictie af te dwingen waarbij een specifieke coëfficiënt nul is (d.w.z. het kenmerk is uitgesloten van een submodel), wordt een grote scalaire waarde $\kappa$ toegevoegd aan het overeenkomstige diagonale element van de precisie-matrix.
• Theoretische basis: Gebaseerd op de Woodbury-matrixidentiteit; het toevoegen van $\kappa A^T A$ (waarbij $A$ een restrictiematrix is) aan $Q$ benadert de conditionele covariantie-matrix als $\kappa \to \infty$.
• Implementatie: Een gezamenlijke restrictiematrix $A$ wordt geconstrueerd voor alle $2^p$ modellen. De methode lost het lineaire stelsel $(Q_F + \kappa A^T A)^{-1}m$ op, waarbij $Q_F$ een blokdiagonaal matrix is die de precisie-matrix van het volledige model $2^p$ keer bevat.
• Afstemming: Vereist een afstemingsparameter $\kappa$, die wordt gesuggereerd te zijn $10^5$ keer de grootste eigenwaarde van de oorspronkelijke precisie-matrix.

2. De Projectie Methode (Benaderend)

Deze methode projecteert de parameterruimte om geconstreinserde parameters te verwijderen.

• Mechanisme: Een projectiematrix $Z = I - A^T A$ wordt toegepast op de precisie-matrix. Het geconstreinserde model wordt behandeld als een intrinsieke GMRF. Om numerieke stabiliteit (positief definitheid) te garanderen, wordt een kleine scalaire $\epsilon$ toegevoegd aan de diagonaal van de geprojecteerde precisie-matrix ($Z Q Z + \epsilon I$).
• Theoretische basis: Naarmate $\epsilon \to 0^+$, convergeert de oplossing naar de exacte geconstreinserde schattingen.
• Implementatie: Lost het stelsel $Z(Z Q_F Z + \epsilon I)^{-1} Z m$ op.
• Afstemming: Vereist een kleine afstemingsparameter $\epsilon$ (bijv. $10^{-5}$), gekozen om klein te zijn ten opzichte van de kleinste eigenwaarde van $Q$, maar groot genoeg voor een stabiele Cholesky-decompositie.

3. De Exacte Transformatie Methode (Exact)

Deze methode biedt een exacte oplossing zonder benaderingsfouten of afstemingsparameters.

• Mechanisme: In plaats van te werken in de volledige parameterruimte en coëfficiënten naar nul te dwingen, transformeert deze methode het probleem naar een lager-dimensionale ruimte die alleen de actieve parameters bevat.
• Implementatie: Een mapping-matrix $E$ wordt geconstrueerd om alleen de actieve parameters voor elk submodel te selecteren. Het stelsel wordt opgelost als $(E Q_F E^T)^{-1} E m$.
• Voordeel: Elimineert de noodzaak voor grote straftermen ($\kappa$) of kleine regularisatietermen ($\epsilon$), waardoor potentiële numerieke instabiliteit of benaderingsbias wordt vermeden.

Alle drie de methoden maken gebruik van spaarse matrixalgebra (specifiek Cholesky-decompositie) om de gezamenlijke schatting van duizenden modellen efficiënt te verwerken. De gezamenlijke precisie-matrix is zeer spaarzaam omdat de modellen onafhankelijk zijn (blokdiagonaal structuur), en de off-diagonaal nulwaarden duiden op conditionele onafhankelijkheid.

Belangrijkste Bijdragen

1. Drie Nieuwe Algoritmen: Het artikel introduceert twee benaderende methoden (Diagonaal Correctie, Projectie) en één exacte methode (Exacte Transformatie) voor de gezamenlijke schatting van alle submodellen in lineaire regressie.
2. Convergentiebewijzen: De auteurs leveren wiskundige bewijzen die aantonen dat de benaderende methoden convergeren naar de ware conditionele schattingen naarmate hun respectieve afstemingsparameters ($\kappa \to \infty$ en $\epsilon \to 0^+$) worden aangepast.
3. Computationele Efficiëntie: Door gebruik te maken van spaarzaamheid en gezamenlijke schatting, reduceren de methoden de rekentijd van uren (typisch voor shapr) naar seconden of minuten, zelfs wanneer alle $2^p$ coalities worden geënumereerd.
4. Empirische Validatie: Uitgebreide numerieke studies vergelijken de nieuwe methoden met het shapr-pakket (zowel de Sequentiële als de Iteratieve versies) over drie datasets: Adult Income, een gesimuleerde Gaussische dataset en de WHO Life Expectancy dataset.

Resultaten

De numerieke casestudy's leveren de volgende bevindingen op:

• Nauwkeurigheid: De Shapley-waarde schattingen geproduceerd door de nieuwe methoden zijn vrijwel identiek aan de Sequentiële methode in shapr (gebruikt als grondwaarheid voor volledige enumeratie).
  • In de Adult dataset ($p=11$) was de mediane absolute fout (MedAE) tussen de nieuwe methoden en de Sequentiële methode van de orde $10^{-9}$.
  • In de Gesimuleerde dataset ($p=21$) was de MedAE van de orde $10^{-7}$ tot $10^{-5}$.
  • In de WHO dataset ($p=16$) was de MedAE van de orde $10^{-6}$.
• Snelheid:
  • Adult Dataset: De nieuwe methoden draalden in 2,5 tot 9 seconden, terwijl shapr (Sequentieel en Iteratief) 17 tot 19 minuten duurde.
  • Gesimuleerde Dataset: De nieuwe methoden namen 1,4 tot 2,5 minuten om alle $2^{21} \approx 2,1$ miljoen modellen te schatten. De shapr Iteratieve methode was sneller (6,48 seconden), maar schatte slechts 200 coalities, niet de volledige set.
  • WHO Dataset: De nieuwe methoden duurden 1,1 tot 1,2 minuten. De shapr Sequentiële methode duurde 131 minuten (2,2 uur), en de Iteratieve methode duurde 16 minuten (parallel) of 36 minuten (serieel).
• Schaalbaarheid: De methoden slaagden erin meer dan twee miljoen submodellen in de gesimuleerde studie binnen minuten te schatten. De primaire beperking die werd geïdentificeerd is geheugenbeperkingen (Vloek van de Dimensionaliteit) wanneer $p$ de ~21 overschrijdt op standaard hardware, hoewel de auteurs opmerken dat dit kan worden gemitigeerd met meer RAM of gespecialiseerde spaarse matrix-pakketten.

Betekenis en Claims

Het artikel claimt dat de voorgestelde methoden een substantiële verbetering bieden in de computationele efficiëntie voor de schatting van conditionele Shapley-waarden zonder in te boeten op nauwkeurigheid.

• Superioriteit in Volledige Enumeratie: Wanneer de shapr Iteratieve methode een groot deel van de coalities nodig heeft om te convergeren (zoals gezien in de Adult en WHO datasets), zijn de nieuwe methoden "substantieel sneller" terwijl ze "gelijke of betere nauwkeurigheid" behouden.
• Uitputtende Enumeratie: In tegen afwezigheid van de iteratieve aanpak die coalities samplet, bieden de nieuwe methoden een volledige enumeratie van alle $2^p$ submodellen, waardoor gegarandeerd wordt dat er geen informatie verloren gaat door variantie door sampling.
• Aanbeveling: De auteurs bevelen de Exacte Transformatie Methode aan voor praktisch gebruik. Hoewel alle drie de methoden vergelijkbare resultaten opleveren, heeft de Exacte methode geen afstemingsparameters, waardoor de noodzaak voor hyperparameterselectie en potentiële bronnen van benaderingsfouten wordt weggenomen.
• Toekomstig Potentieel: De auteurs suggereren dat de methodologie kan worden uitgebreid naar splines (bijv. uit het rms pakket) en dat parallellisatie (bijv. via OpenMP) de looptijden verder kan verkorten, hoewel de huidige implementatie afhankelijk is van seriële executie voor een eerlijke vergelijking met het geparallelliseerde shapr pakket.

Het artikel concludeert dat deze methoden de exacte berekening van conditionele Shapley-waarden voor lineaire modellen met gemengde covariatentypen haalbaar maken in scenario's waar dit voorheen computationeel onhaalbaar was.