A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Dit paper introduceert ESENSC_rev2, een axiomatisch onderbouwde en polynomiale alternatieve methode voor SHAP die een gunstige afweging biedt tussen rekenkosten en nauwkeurigheid bij het verklaren van hoge-dimensionale voorspellingsmodellen.

De kern

Een snellere, slimmere manier om AI's gedrag te verklaren

Stel je voor dat je een zeer complexe, magische machine hebt die voorspellingen doet. Misschien zegt hij of een hypotheek wordt goedgekeurd, of een patiënt ziek is, of welke film je gaat leuk vinden. Maar deze machine is een "zwarte doos": je ziet de input (de gegevens), je ziet de output (het resultaat), maar je weet niet precies waarom hij tot die conclusie kwam.

In de wereld van kunstmatige intelligentie (AI) willen we graag weten welke "ingrediënten" (de kenmerken of features) het meest hebben bijgedragen aan het resultaat. Dit noemen we Feature Attribution.

Deze paper introduceert een nieuwe, snellere manier om dit te doen, als een alternatief voor de huidige standaardmethode, genaamd SHAP.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. Het probleem: De "Gouden Kooi" van SHAP

De huidige koning van het verklaren van AI is SHAP. Het werkt op basis van een wiskundig concept uit de speltheorie (coöperatieve speltheorie).

• De Analogie: Stel je voor dat je een team hebt van 100 mensen die samen een taak uitvoeren. SHAP probeert uit te rekenen hoeveel elke persoon precies heeft bijgedragen aan het eindresultaat. Om dit perfect te doen, moet SHAP kijken naar elke mogelijke combinatie van mensen die samen kunnen werken.
• Het probleem: Als je 10 mensen hebt, zijn er al duizenden combinaties. Als je 100 mensen hebt (wat vaak het geval is bij moderne AI met veel gegevens), zijn er meer combinaties dan er atomen in het heelal zijn.
• De realiteit: Het exacte berekenen van SHAP is zo zwaar dat het vaak onmogelijk is om het in redelijke tijd te doen. Mensen gebruiken daarom "schattingen" (benaderingen), maar die kunnen onnauwkeurig zijn of veel tijd kosten om te "tunen".

2. De oplossing: Een slimme shortcut (ESENSC_rev2)

De auteurs van dit paper zeggen: "Laten we niet proberen elke mogelijke combinatie te tellen. Laten we een slimme, snelle regel bedenken die bijna hetzelfde resultaat geeft, maar dan in een fractie van de tijd."

Ze kijken naar twee bestaande, snellere methoden uit de speltheorie:

1. Equal Surplus (ES): Iedereen krijgt eerst wat hij alleen heeft opgeleverd, en de rest van de winst wordt eerlijk verdeeld.
2. ENSC: Iedereen krijgt eerst wat hij heeft opgeleverd als hij alleen wegvalt uit het team, en de rest wordt eerlijk verdeeld.

De nieuwe methode (ESENSC_rev2) is een mix van deze twee. Maar er is een addertje onder het gras: de standaard mix geeft soms punten aan mensen (of kenmerken) die helemaal niets hebben bijgedragen. Dat is in een AI-context raar: als een kenmerk (bijvoorbeeld "de kleur van de auto") niets doet voor de voorspelling, moet de bijdrage 0 zijn, niet een klein beetje.

De auteurs hebben de formule dus een beetje aangepast (een "rev2" versie) zodat mensen die niets doen, echt 0 punten krijgen. Dit noemen ze de Null-player eigenschap.

3. Waarom is dit beter? (De vergelijking)

• Snelheid:
  • SHAP: Is als het proberen om elke mogelijke route door een stad te lopen om de kortste weg te vinden. Bij veel straten (kenmerken) duurt dit eeuwen.
  • ESENSC_rev2: Is als het gebruiken van een GPS die een slimme, directe route berekent. Het is polynomiale tijd, wat betekent dat het snel blijft, zelfs als je van 10 naar 1000 kenmerken gaat. Het schaalt perfect.
• Nauwkeurigheid:
  • De auteurs hebben getest met echte data (zoals huizenprijzen in Californië). Ze zagen dat hun nieuwe methode bijna exact hetzelfde resultaat geeft als de dure, trage SHAP-methode.
  • Het is veel nauwkeuriger dan andere snelle schattingen die mensen nu gebruiken.

4. Een ander probleem: De "Omdraaiing"

De paper bespreekt ook een andere groep methoden (Proportional Allocation). Deze proberen de winst te verdelen op basis van een verhouding.

• Het probleem: Soms kan het gebeuren dat een kenmerk dat een negatieve invloed heeft, ineens een hoge positieve score krijgt, en andersom. Dit is als een chef-kok die zegt: "De peper die het gerecht verpestte, was eigenlijk de reden dat het zo lekker was!" Dat is verwarrend.
• De nieuwe methode van de auteurs voorkomt dit soort rare omkeringen, terwijl de andere snelle methoden er soms last van hebben.

5. De Wiskundige "Waarborg" (Axiomatiek)

Om zeker te weten dat hun methode niet zomaar een gok is, hebben de auteurs bewezen dat hun regel de enige regel is die voldoet aan een aantal logische eisen:

1. Efficiëntie: Alle punten worden verdeeld (niets gaat verloren).
2. Null-player: Wie niets doet, krijgt niets.
3. Rekenkracht: De methode gebruikt geen onmogelijke berekeningen.

Dit betekent dat hun methode niet alleen snel is, maar ook wiskundig solide en eerlijk.

Samenvatting voor de leek

Stel je voor dat je een groep vrienden hebt die samen een puzzel oplossen.

• SHAP vraagt: "Laten we kijken naar elke mogelijke groepje vrienden dat we kunnen vormen om te zien wie de puzzel het snelst oplost." Dit duurt te lang als de groep groot is.
• De nieuwe methode (ESENSC_rev2) zegt: "Laten we kijken naar wat elke vriend alleen kan, en wat hij doet als hij wegvalt, en dan nemen we het gemiddelde. Als iemand niets doet, krijgt hij 0."

Het resultaat? Je krijgt een verklaring die net zo goed is als de dure methode, maar die je in een seconde kunt berekenen, zelfs met duizenden variabelen. Het is een snellere, betrouwbaarder en wiskundig onderbouwde manier om te begrijpen wat AI's eigenlijk doen.

Technische samenvatting

Titel: Een Polynomiale Axiomatische Alternatief voor SHAP voor Feature Attribution

Auteurs: Kazuhiro Hiraki, Shinichi Ishihara, Takumi Kongo, Junnosuke Shino.

---

1. Het Probleem

In het veld van Explainable AI (XAI) is SHAP (SHapley Additive exPlanations) de meest gebruikte methode om modelvoorspellingen te decomponeren in bijdragen van individuele features. SHAP is gebaseerd op de Shapley-waarde uit de coöperatieve speltheorie. Hoewel SHAP theoretisch sterk is (het voldoet aan wenselijke eigenschappen zoals efficientie en de null-player eigenschap), heeft het een ernstig nadeel: de rekenkosten.

• De exacte berekening van de Shapley-waarde vereist het evalueren van $2^n$ coalities, wat exponentieel groeit met het aantal features ($n$).
• Bestaande benaderingsalgoritmen (zoals Kernel SHAP of Permutation SHAP) lossen dit op door te stochastisch te bemonsteren, maar deze methoden zijn vaak instabiel, vereisen het tunen van hyperparameters (zoals het aantal bemonsteringen) en garanderen niet dat ze alle theoretische eigenschappen van de Shapley-waarde behouden.
• Er is behoefte aan een methode die polynomiale tijd vereist (rekenbaar voor grote $n$), theoretisch onderbouwd is via axiomatische karakterisering, en nauwkeurig genoeg is om SHAP te benaderen.

2. Methodologie

De auteurs formuleren het probleem van feature attribution als een XAI-TU game (Transferable Utility game). In dit spel vertegenwoordigen de features de spelers.

A. Definitie van XAI-TU Games

Voor een observatie $\tau$ wordt een karakteristieke functie $v_\tau(S)$ gedefinieerd als de verwachte voorspelling van het model wanneer de features in $S$ bekend zijn en de rest uit de empirische verdeling wordt getrokken.

• Unieke kenmerken: In tegenstelling tot traditionele speltheorie, kunnen in XAI-games zowel positieve als negatieve coalitiewaarden voorkomen binnen hetzelfde spel. De totale surplus ($v(N) - v(\emptyset)$) kan positief of negatief zijn, en sommen van marginale bijdragen kunnen van teken verschillen met de totale surplus.

B. Ontwikkeling van Alternatieve Oplossingsconcepten

De auteurs onderzoeken twee klassen van oplossingen met lage rekenkosten: Equal Surplus (ES)-type en Proportional Allocation (PA)-type.

1. ES-type Oplossingen:

   • Ze bekijken de gemiddelde van Equal Surplus (ES) en Egalitarian Nonseparable Contribution (ENSC).
   • Probleem: De simpele mix van ES en ENSC schendt de null-player eigenschap (een feature zonder invloed krijgt toch een toewijzing).
   • Oplossing: Ze introduceren een gemodificeerde versie, $\psi_{ESENSC\_rev2}$. Deze regel verdeelt het resterende surplus alleen onder features die een niet-nul marginale bijdrage hebben. Dit garandeert dat null-players een toewijzing van 0 krijgen.

2. PA-type Oplossingen:

   • Ze analyseren proportionele regels. Een groot probleem hier is het order-reversal probleem: door het co-existeren van positieve en negatieve waarden, kan een feature met een hogere marginale bijdrage een lagere toewijzing krijgen dan een feature met een lagere bijdrage.
   • Ze stellen een aangepaste regel ($\psi_{PARPA}$) voor die probeert dit te voorkomen, maar experimenten tonen aan dat deze regels onstabiel blijven en grote afwijkingen van SHAP vertonen.

C. Axiomatische Karakterisering

De kern van de theoretische bijdrage is het bewijzen dat $\psi_{ESENSC\_rev2}$ uniek wordt bepaald door een specifieke set axioma's:

• Efficiency: De som van alle attributies is gelijk aan de totale voorspellingssurplus.
• Null-player eigenschap: Features zonder invloed krijgen 0.
• Restricted Differential Marginality: Een verzwakte versie van het klassieke axioma, die alleen geldt onder specifieke voorwaarden over welke features actief zijn.
• Intermediate Inessential Game: Een axiomatische eis die de toewijzing bepaalt in een specifiek "tussenliggend" scenario (gemiddelde van pessimistische en optimistische perspectieven).
• Reduction in Computational Complexity: De oplossing mag alleen afhankelijk zijn van coalities van grootte 0, 1, $n-1$ en $n$. Dit garandeert polynomiale complexiteit.

3. Belangrijkste Resultaten

De auteurs hebben uitgebreide experimenten uitgevoerd op tabulaire datasets (California Housing) met zowel XGBoost als Neuronale Netwerken, waarbij het aantal features werd opgevoerd tot 512.

• Rekenkosten:

  • Exact SHAP groeit exponentieel en wordt onuitvoerbaar bij $n > 16$.
  • De voorgestelde $\psi_{ESENSC\_rev2}$ schalen lineair met het aantal features.
  • De methode is aanzienlijk sneller dan bestaande benaderingsmethoden zoals Permutation SHAP en Kernel SHAP, en vereist geen tuning van hyperparameters.

• Nauwkeurigheid (Afwijking van Exact SHAP):

  • $\psi_{ESENSC\_rev2}$ benadert de exacte SHAP-waarden zeer nauwkeurig. De afwijking is vergelijkbaar met of zelfs beter dan Permutation SHAP en duidelijk kleiner dan Kernel SHAP.
  • PA-type regels (zoals $\psi_{PARPA}$) vertonen daarentegen grote en onstabiele afwijkingen, zelfs als ze zijn ontworpen om het order-reversal probleem te voorkomen. Dit suggereert dat proportionele regels fundamenteel minder geschikt zijn voor XAI-games met gemengde tekens.

• Theoretische Validatie:

  • De axiomatische karakterisering bevestigt dat $\psi_{ESENSC\_rev2}$ een wiskundig onderbouwde oplossing is die een evenwicht vindt tussen eerlijkheid (via axioma's) en rekenbaarheid.

4. Betekenis en Conclusie

Dit artikel biedt een theoretisch onderbouwd en computationeel efficiënt alternatief voor SHAP.

• Praktische Toepassing: Voor moderne XAI-pipelines met veel features (hoge dimensionaliteit) is exact SHAP vaak onmogelijk en zijn bestaande benaderingen traag of onnauwkeurig. De voorgestelde ESENSC_rev2-regel biedt een directe, parameter-vrije berekening die snel is en nauwkeurig genoeg blijft.
• Theoretische Bijdrage: Het is de eerste studie die een polynomiale feature-attributieregel axiomaatisch karakteriseert die SHAP benadert. Het toont aan dat men kan afzien van de sterke "symmetrie-gebaseerde" eisen van de Shapley-waarde (die leiden tot exponentiële complexiteit) ten gunste van een "restricted differential marginality" en een "reduction in computational complexity" axioma, zonder de kwaliteit van de uitleg significant te verliezen.
• Inzicht in XAI-games: Het onderzoek benadrukt dat XAI-games fundamenteel verschillen van traditionele coöperatieve spellen door de co-existentie van positieve en negatieve waarden, wat leidt tot specifieke valkuilen voor proportionele allocatieregels.

Kortom, de auteurs stellen dat $\psi_{ESENSC\_rev2}$ een praktische, theoretisch solide vervanger is voor SHAP in scenario's waar schaalbaarheid en reproduceerbaarheid cruciaal zijn.