Exact Functional ANOVA Decomposition for Categorical Inputs Models

Dit paper introduceert een exacte, gesloten-devormige Functional ANOVA-decompositie voor categorische invoer die afhankelijkheden tussen variabelen volledig in aanmerking neemt en een natuurlijke generalisatie van SHAP-waarden biedt.

De kern

Stel je voor dat je een heel ingewikkeld recept hebt voor een taart, maar je weet niet precies welke ingrediënten (meel, suiker, eieren) of welke combinaties daarvan (meel + suiker) de taart zo lekker maken. In de wereld van kunstmatige intelligentie (AI) is dit precies het probleem: we hebben een "zwarte doos" die een voorspelling doet, maar we weten niet waarom.

Deze paper introduceert een nieuwe, slimme manier om die zwarte doos open te maken, specifiek voor data die bestaat uit categorieën (zoals "rood, blauw, groen" of "ja, nee, misschien") en waarbij die categorieën vaak met elkaar verbonden zijn.

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

1. Het Probleem: De Verwarde Orkestleider

Stel je een groot orkest voor (het AI-model). Elk muzikant is een variabele in je data.

• Onafhankelijke muzikanten: Als elke muzikant zijn eigen partituur speelt zonder naar de anderen te luisteren, is het makkelijk om te zeggen wie wat doet. Dit is wat oude methoden deden.
• Afhankelijke muzikanten: Maar in de echte wereld spelen muzikanten vaak samen. Als de trompettist hard speelt, moet de drummer misschien zachter spelen. Als je de trompet weglaat, klinkt het drumgedeelte ineens anders.

Vroeger was het heel moeilijk om te weten wie wat deed als de muzikanten zo met elkaar verweven waren. De oude methoden moesten "gokken" of duizenden keer proberen (rekenen) om een benadering te krijgen. Dat duurde lang en was niet 100% nauwkeurig.

2. De Oplossing: De "Perfecte Splitsing"

De auteurs van dit paper hebben een nieuwe formule bedacht die dit probleem exact oplost voor categorische data.

Ze gebruiken een wiskundige truc die lijkt op het ontleden van een complexe muziekstuk in losse noten en akkoorden.

• De "Main Effects" (Hoofd-effecten): Dit is wat elke muzikant alleen doet. (Bijvoorbeeld: "De trompet maakt het geluid 10% luider").
• De "Interactions" (Interacties): Dit is wat gebeurt als ze samen spelen. (Bijvoorbeeld: "Als de trompet en de fluit tegelijk spelen, wordt het geluid 20% zachter").

Het mooie aan hun methode is dat ze een formule hebben die dit direct uitrekent, zonder te hoeven gokken of te simuleren. Het is alsof ze een magische bril hebben die direct ziet welke muzikant welke noot speelt, zelfs als ze allemaal door elkaar heen spelen.

3. De "Gaten" in het Net (Het Sparsite-Principe)

Een groot probleem bij grote datasets is dat er vaak "gaten" zijn. Niet elke mogelijke combinatie van ingrediënten komt voor.

• Voorbeeld: In een dataset over huizen komen misschien nooit huizen voor met "rode muren" én "blauwe dakpannen" én "een zwembad". Die combinatie bestaat simpelweg niet in de data.

Oude methoden raakten hierdoor in de war of moesten enorme hoeveelheden rekenkracht gebruiken om die lege gaten op te vullen.
Deze nieuwe methode kijkt alleen naar de werkelijke combinaties die er zijn. Ze bouwen een "ladder" van uitleg die precies past op de data die je hebt, zonder zich druk te maken over de combinaties die nooit bestaan. Het is alsof je een traptrede bouwt die precies past op de helling van je tuin, in plaats van een rechte ladder te forceren die overal gaten heeft.

4. Waarom is dit geweldig? (De Voordelen)

• Snelheid: Omdat ze een directe formule hebben, is het rekenen veel sneller dan de oude methoden. Ze noemen het "computationally very efficient".
• Nauwkeurigheid: Het is geen schatting meer; het is de exacte waarheid voor die specifieke data.
• Vertrouwen: Het helpt ons te begrijpen waarom een AI een bepaalde beslissing neemt. Bijvoorbeeld: "Waarom werd deze sollicitant afgewezen?" Het antwoord is niet "omdat de AI het zo wilde", maar "omdat de combinatie van 'lage ervaring' en 'geen diploma' de kans op aannemen drastisch verlaagde".

5. Een concreet Voorbeeld uit de Paper

De auteurs testten hun methode op een AI die foto's van cijfers moest herkennen (bijvoorbeeld het cijfer '3' versus '8').

• Ze keken naar de pixels (de kleine vierkantjes) op de foto.
• Met hun methode konden ze precies zien welke pixels belangrijk waren.
• Het resultaat: De pixels die leken op de bovenkant van een '3' (rechtsboven) waren rood gemarkeerd (belangrijk voor 'ja'). De pixels die de lus van een '8' maakten (links) waren blauw gemarkeerd (belangrijk voor 'nee').
• Dit gaf een heel duidelijk en logisch beeld van hoe de AI dacht, zelfs bij duizenden pixels tegelijk.

Samenvatting in één zin

Deze paper geeft ons een snelle, exacte en betrouwbare "vertaaltool" om te begrijpen hoe AI-modellen werken met categorische data, zelfs als die data complex en met elkaar verbonden is, zonder dat we hoeven te gokken of urenlang hoeven te rekenen.

Het is alsof we eindelijk een handleiding hebben die perfect uitlegt hoe een ingewikkeld horloge werkt, zonder dat we het horloge hoeven te slopen.

Technische samenvatting

Probleemstelling

Functionele ANOVA (Analysis of Variance) biedt een fundamenteel raamwerk voor modelinterpretatie door voorspellingen te ontbinden in hoofdeffecten en hogere-orde interacties. Voor onafhankelijke kenmerken is deze ontbinding goed gedefinieerd en sterk verbonden met SHAP-waarden. Echter, voor afhankelijke verdelingen ontbreekt een expliciete, gesloten-vorm uitdrukking. Practici zijn hierdoor vaak aangewezen op kostbare, op steekproeven gebaseerde benaderingen die niet altijd accuraat zijn.

Bestaande methoden hebben beperkingen:

• Booleaanse analyse (Fourier): Werkt alleen perfect voor onafhankelijke Bernoulli-variabelen met parameter 1/2 en faalt bij categorische data door kunstmatige interacties die ontstaan door one-hot encoding.
• Boom-gebaseerde methoden (bijv. TreeHFD): Beperkt tot ondiepe bomen en veronderstelt niet-lege bladeren, wat sparsiteit in de data niet goed aankan.
• Algemene benaderingen: Vaak computationally onhaalbaar voor hoge dimensies of vereisen zware sampling.

Het paper richt zich specifiek op categorische invoer, die vaak afhankelijk zijn en een niet-rechthoekige steun (support) hebben (d.w.z. niet alle mogelijke combinaties van categorieën komen voor in de data).

Methodologie

De auteurs introduceren een gesloten-vorm formule voor de Generalized Functional ANOVA die specifiek is ontworpen voor categorische domeinen, zonder aannames over onafhankelijkheid.

1. Wiskundige Basis:

   • Het probleem wordt geformuleerd in de Hilbertruimte $L^2(\nu)$, waarbij $\nu$ de telmaat is op het eindige steunpunt $X$ van de categorische variabelen.
   • De doelstelling is een ontbinding $f(X) = \sum_{A \subseteq [d]} f_A(X_A)$ te vinden die voldoet aan een hiërarchische orthogonaliteitsvoorwaarde: informatie toegevoegd door een set $A$ moet orthogonaal zijn aan alle informatie in zijn deelverzamelingen.

2. Uitgebreide Walsh-Hadamard Basis:

   • De kern van de methode is een uitbreiding van de klassieke Walsh-Hadamard basis (gebruikt in Booleaanse analyse) naar categorische variabelen met willekeurige kardinaliteit.
   • Ze definiëren een familie van functies $\phi_A^{(z)}(x)$ die fungeren als een "getekende inverse waarschijnlijkheid". Deze functies vormen een overcomplete verzameling die de hele ruimte $L^2$ opspant.

3. Lineair Stelsel en Gram-matrix:

   • De coëfficiënten van de ANOVA-ontbinding worden gevonden door een lineair stelsel op te lossen: $\Gamma \mathbf{c} = \boldsymbol{\mu}$.
   • Hierbij is $\Gamma$ een Gram-matrix van inproducten tussen de basisfuncties, en $\boldsymbol{\mu}$ een vector van inproducten met de doelfunctie $f$.
   • In het geval van volledige steun (alle combinaties mogelijk) is deze matrix inverteerbaar en is de oplossing uniek.

4. Omgaan met Sparsiteit (Rang-reductie):

   • In de praktijk is de steun $X$ vaak een klein deel van het volledige hyperrooster (sparsiteit). De auteurs tonen aan dat er een deelverzameling van de basis bestaat die precies de dimensie van de effectieve steun ($r$) heeft.
   • Ze gebruiken een gretige algoritme (Algorithm 1) om een lineair onafhankelijke basis te selecteren die de data opspant.
   • Voor zeer grote datasets wordt een laag-rang benadering gebruikt: het proces wordt gestopt zodra een bepaald budget ($r_{low}$) is bereikt. Dit biedt een afweging tussen nauwkeurigheid en interpretatie, waarbij vaak al de belangrijkste hoofdeffecten en lage-orde interacties worden gevangen.

Belangrijkste Bijdragen

• Exacte Gesloten-Vorm Ontbinding: Voor het eerst wordt een exacte, analytische oplossing gepresenteerd voor Functional ANOVA op categorische data met willekeurige afhankelijkheidsstructuren en spare steunpunten.
• Generalisatie van SHAP: Het framework levert een natuurlijke generalisatie van SHAP-waarden voor categorische data. Onder onafhankelijkheid herwint het exact de klassieke SHAP-waarden; onder afhankelijkheid biedt het een theoretisch onderbouwde alternatief voor benaderingsmethoden.
• Computational Efficiency: De methode is uiterst efficiënt. Zodra de decompositie is berekend (een eenmalige globale kosten), kunnen verklaringen voor onbeperkt aantal steekproeven direct worden gegenereerd.
• Omgaan met Niet-Rechthoekige Support: De methode werkt correct zelfs als de data niet alle mogelijke combinaties bevat (bijv. door logische onmogelijkheden of zeldzame gebeurtenissen).

Resultaten

De auteurs testen hun methode op diverse synthetische en echte datasets:

1. Synthetisch Geval: Met perfect gecorreleerde variabelen ($X_3 = X_2$) en constante variabelen, toont de methode aan dat irrelevante variabelen automatisch worden genegeerd en de decompositie correct wordt beperkt tot de vrije variabelen.
2. Onafhankelijke Datasets (CAR EVALUATION, NURSERY): In gevallen waar kenmerken onafhankelijk zijn, komen de berekende waarden exact overeen met de theoretische SHAP-waarden, maar worden ze veel sneller berekend (0,5s vs 54s voor KernelSHAP).
3. MUSHROOMS Dataset: Een hoogdimensionale, spars dataset. De decompositie toont aan dat hoofdeffecten voldoende zijn om het signaal bijna perfect te reconstrueren ($R^2 \approx 1$). De methode identificeert correct bekende belangrijke kenmerken zoals 'geur' (odor).
4. Hoogdimensionale Spars Datasets (POKER, CONNECT-4, DOTA2):
   • De methode presteert goed in regimes waar $r \ll |E|$ (weinig samples vergeleken met het theoretische volume).
   • Zelfs met een beperkte rang (bijv. alleen hoofdeffecten), worden dominante interacties binnen seconden geïsoleerd.
   • Op de Binarized MNIST dataset (60.000 samples, 784 features) kon de methode binnen 15 minuten een hoge-rang benadering berekenen met een $R^2$ van 0,86, wat visueel interpreteerbare attributies opleverde die consistent waren met de vorm van de cijfers.

Betekenis en Conclusie

Dit werk vormt een paradigmaverschuiving in de interpretatie van zwarte doos-modellen met categorische invoer.

• Theoretisch: Het lost een langdurig probleem op door een exacte ontbinding te bieden zonder aannames over onafhankelijkheid.
• Praktisch: Het biedt een schaalbare oplossing voor tabulaire data, die vaak categorisch en afhankelijk is. Het elimineert de noodzaak voor kostbare Monte-Carlo sampling voor SHAP-berekeningen in deze context.
• Toekomst: Hoewel de huidige implementatie een gretige strategie gebruikt, toont het paper aan dat domeinkennis (zoals ruimtelijke structuur in beelddata) de efficiëntie verder kan optimaliseren. De auteurs zien potentieel om deze exacte decompositie later uit te breiden naar continue domeinen.

Kortom, de paper levert een robuust, wiskundig onderbouwd en computatieel haalbaar raamwerk voor het begrijpen van complexe interacties in categorische data, wat bijdraagt aan betrouwbaarder en transparanter machine learning.