AXIL: Exact Instance Attribution for Gradient Boosting

Dit paper introduceert AXIL, een exacte en efficiënte methode voor het toewijzen van voorspellingen aan trainingsinstanities bij gradient boosting-modellen met een vaste boomstructuur, die zowel in nauwkeurigheid als snelheid presteert boven bestaande methoden.

De kern

Titel: AXIL: De "Wie heeft dit gedaan?"-detector voor slimme computers

Stel je voor dat je een zeer slimme voorspeller hebt gebouwd, bijvoorbeeld een computer die kan voorspellen hoe duur een huis zal zijn op basis van eerdere verkoopdata. Als de computer zegt: "Dit huis kost 500.000 euro," is de volgende logische vraag: "Waarom?"

Meestal kijken we naar de kenmerken van het huis: "Het heeft drie slaapkamers, dus dat is duur." Maar dit artikel introduceert een nieuwe manier van kijken. Het vraagt niet naar de kenmerken, maar naar de geschiedenis: "Welke specifieke huizen uit de oude database hebben deze voorspelling eigenlijk veroorzaakt?"

De auteurs noemen hun nieuwe methode AXIL. Laten we dit uitleggen met een paar simpele analogieën.

1. Het probleem: Een recept dat te complex is

Stel je voor dat je een gigantisch recept hebt voor een soep (het computermodel). Dit recept is gemaakt door duizenden kleine koks (de "bomen" in het model) die één voor één een lepel zout of peper hebben toegevoegd.
Als je nu vraagt: "Waarom is deze soep zo zout?", kun je niet gewoon zeggen: "Omdat er peper in zat." Je moet weten: "Welke specifieke kok heeft precies hoeveel peper toegevoegd, en welke andere koks hebben dat gecompenseerd?"

Bij de meeste bestaande methoden proberen ze dit te schatten. Ze zeggen: "Ik denk dat kok nummer 45 wel een grote rol heeft gespeeld." Maar dat is vaak maar een gokje.

2. De oplossing: AXIL is de perfecte rekenmachine

AXIL is anders. De auteurs hebben ontdekt dat voor een bepaald type computermodel (genaamd Gradient Boosting, heel populair voor tabellen met cijfers), je de voorspelling exact kunt schrijven als een som van alle oude data.

Het is alsof je zegt:
"De prijs van dit huis is 500.000 euro, omdat:

• Huis A uit 2010 10% heeft bijgedragen,
• Huis B uit 2015 5% heeft bijgedragen,
• Huis C uit 2020 eigenlijk 2% heeft afgetrokken (want het was goedkoper),
• en zo verder voor elk huis in de database."

AXIL berekent deze percentages exact. Geen schattingen, geen gokken. Het is wiskundisch bewezen dat dit zo werkt.

3. Het grote probleem: De "Grote Lijst"

Er is een klein maar groot probleem. Als je 1 miljoen oude huizen in je database hebt, moet je voor één nieuwe voorspelling 1 miljoen percentages berekenen.
Stel je voor dat je een gigantisch boek moet schrijven waarin je voor elke nieuwe vraag een lijst maakt van 1 miljoen namen. Als je dat voor elke vraag doet, duurt het eeuwen en heb je een computer nodig zo groot als een stad.

4. De magische truc: De "Terugwaartse Toverstaf"

Hier komt de echte genialiteit van dit artikel. De auteurs hebben een slimme truc bedacht, een soort "Terugwaartse Toverstaf".

In plaats van dat hele enorme boek (de lijst van 1 miljoen namen) eerst te schrijven en op te slaan, laten ze de toverstaf direct naar het antwoord springen.

• Oude manier: Schrijf eerst de hele lijst, zoek dan de regels op. (Duurt lang, kost veel geheugen).
• AXIL-methode: Vraag direct: "Wie is de belangrijkste kok voor deze ene soep?" De toverstaf berekent direct alleen die specifieke lijst, zonder ooit de hele grote lijst te hoeven schrijven.

Dit maakt het mogelijk om dit zelfs te doen op computers met miljoenen data-punten, en het gaat razendsnel.

5. Waarom is dit belangrijk? (De proef op de som)

De auteurs hebben dit getest tegen andere methoden.

• De test: Ze veranderden een klein beetje in de oude data (bijvoorbeeld: "Laten we doen alsof huis A in 2010 100 euro duurder was").
• Het resultaat: De andere methoden gaven vaak verkeerde antwoorden over wie er verantwoordelijk was. AXIL gaf exact het juiste antwoord. Het was alsof AXIL de enige was die de echte oorzaak van de verandering kon zien, terwijl de anderen in het donker tastten.

Daarnaast hebben ze getest of AXIL echt de "belangrijkste" data-punten vindt. Als je de data-punten die AXIL als belangrijk bestempelt verwijdert en het model opnieuw traint, verandert de voorspelling het meest. Dat betekent: AXIL weet echt wie de belangrijkste spelers zijn.

Samenvatting in één zin

AXIL is een nieuwe, supersnelle en exacte manier om te zeggen: "Jouw voorspelling is precies dit, omdat deze specifieke oude gegevens dit en dat hebben gedaan," zonder dat je duizenden uren hoeft te rekenen.

Het is alsof je eindelijk een spiegel hebt gekregen die je niet alleen laat zien wat er in de kamer is, maar ook wie precies heeft gezorgd voor elk object in de kamer.

Technische samenvatting

Probleemstelling

In het veld van Explainable AI (XAI) ligt de focus traditioneel op het verklaren van voorspellingen op basis van kenmerken (features), bijvoorbeeld met methoden zoals SHAP of LIME. Echter, de data-matrix is tweedimensionaal: naast kenmerken bestaan er ook instances (trainingsvoorbeelden). Een cruciale, maar vaak onbeantwoorde vraag is: welke specifieke trainingsvoorbeelden drijven een bepaalde voorspelling?

Voor Gradient Boosting Machines (GBM's), de dominante methode voor tabulaire data, ontbreekt er tot nu toe een methode die:

1. Exact is (geen benadering).
2. Specifiek is voor elke individuele voorspelling.
3. Schaalbaar is voor grote datasets (zonder het opstellen van een enorme $N \times N$ matrix).
4. Werkt voor zowel in-sample als out-of-sample voorspellingen.

Bestaande methoden zoals BoostIn, TREX en LeafInfluence zijn vaak benaderingen of vereisen herhaaldelijk hertrainen van het model, wat rekenkundig duur en onnauwkeurig kan zijn.

Methodologie: AXIL

De auteurs introduceren AXIL (Additive eXplanations with Instance Loadings), een methode die een exacte lineaire decompositie toepast op GBM's die zijn getraind met een kwadratische foutverliesfunctie (squared-error loss).

Kerninzicht:
Voor een gefit GBM met een vaste boomstructuur (de boomtopologie en bladeren zijn niet meer veranderlijk) kan elke voorspelling $\hat{y}_i$ worden geschreven als een lineaire combinatie van de trainingsdoelen $y$:
$$\hat{y}_i = \mathbf{k}_i \cdot \mathbf{y} = \sum_{j=1}^{N} k_{i,j} y_j$$
Hierbij is $\mathbf{k}_i$ een vector van gewichten (AXIL-gewichten) die uitsluitend wordt bepaald door de boomstructuur en de leerfactor ($\lambda$). De coëfficiënt $k_{i,j}$ geeft exact aan hoeveel de voorspelling $i$ verandert als trainingsdoel $y_j$ met één eenheid wordt verhoogd, mits de boomstructuur constant blijft.

Het Algorithmische Doorbraak: De Backward Operator
Het grootste obstakel is dat de volledige gewichtsmatrix $K$ (waarvan rij $i$ gelijk is aan $\mathbf{k}_i$) $N^2$ elementen heeft. Voor grote datasets (bijv. $N=1.000.000$) zou dit 8 TB aan geheugen vereisen, wat onpraktisch is.

De auteurs ontwikkelen een matrixvrije backward operator (Theorema 3) die een enkel AXIL-gewichtsvector $\mathbf{k}_i$ berekent zonder de matrix $K$ ooit expliciet te vormen:

• Principe: In plaats van de matrix te vermenigvuldigen, wordt een recursieve "terugwaartse" pass uitgevoerd door de gefitte bomen.
• Complexiteit: Het berekenen van de gewichten voor één voorspelling kost $O(TN)$ tijd, waarbij $T$ het aantal bomen is en $N$ het aantal trainingsinstances. Voor $S$ voorspellingen kost dit $O(TNS)$.
• Voordeel: Omdat $T$ en $S$ meestal veel kleiner zijn dan $N$, is de kost per voorspelling lineair in de datasetgrootte. Dit maakt exacte attributie haalbaar voor zeer grote datasets.
• Out-of-sample: De methode wordt uitgebreid naar nieuwe, onbekende instances (Theorema 4) door gebruik te maken van "cross-leaf" vectoren die aangeven in welk blad een nieuwe instance terechtkomt.

Belangrijkste Bijdragen

1. Exacte Decompositie: Bewijs dat gefitte GBM's (met L2-verlies) lineair zijn in de trainingsdoelen, wat leidt tot een unieke matrix $K$ van instance-gewichten.
2. Efficiënt Algoritme: Een matrixvrije backward operator die exacte attributies berekent in $O(TN)$ tijd, waardoor het toepasbaar is op datasets met miljoenen rijen.
3. Theoretische Grenzen: De auteurs definiëren waar deze exacte decompositie wel en niet werkt:
   • Werkt: Lineaire regressie, regressie-bomen, Random Forests, en GBM regressie (L2-verlies).
   • Werkt niet: GBM classificatie (vanwege de niet-lineaire log-odds initialisatie) en standaard neurale netwerken (vanwege niet-lineaire activaties en gewichtsupdates).
4. Verbinding met Jacobiaan: AXIL wordt gepositioneerd als het globale, constante speciale geval van de "target-response Jacobiaan" ($J$), die voor elke differentieerbare leerder een lokale, eerste-orde attributie biedt via impliciete differentiatie.

Resultaten

De methode is geëvalueerd op 20 regressiedatasets en vergeleken met de toonaangevende concurrenten: BoostIn, TREX en LeafInfluence.

1. Doelgevoeligheid (Target Sensitivity):

   • In een experiment waarbij trainingsdoelen werden verstoord, bleek AXIL perfect (correlatie $r=1.000$) de echte verandering in voorspellingen te voorspellen.
   • Concurrenten faalden hier: BoostIn had een correlatie van ~0.28 (meet gradient-bijdragen, niet doelgevoeligheid) en TREX ~0.67.

2. Betrouwbaarheid bij Hertraining (Faithfulness):

   • De auteurs gebruikten een protocol waarbij de meest invloedrijke trainingsinstances (volgens de attributiemethode) werden verwijderd en het model opnieuw werd getraind.
   • AXIL behaalde de hoogste "faithfulness score" (AURC) op 14 van de 20 datasets en deed het statistisch even goed op 4 andere.
   • AXIL identificeerde duidelijk de meest invloedrijke instances, vooral in datasets met sterke signalen (bijv. Titanic-dataset).

3. Snelheid:

   • AXIL is overal de snelste methode.
   • BoostIn is 4-10x trager.
   • TREX is 4-75x trager.
   • LeafInfluence is vaak >100x trager en onuitvoerbaar voor grote datasets.

Betekenis en Conclusie

AXIL biedt een fundamentele doorbraak in de interpretatie van GBM's. In plaats van te vertrouwen op benaderingen of dure hertrainingsprocedures, biedt AXIL exacte, ground-truth sensitiviteiten van een voorspelling ten opzichte van de trainingsdata.

• Praktische impact: Het maakt het mogelijk om te begrijpen welke specifieke data-punten een voorspelling beïnvloeden, wat essentieel is voor data-kwaliteitscontrole, bias-detectie en vertrouwen in modellen.
• Schaalbaarheid: Door de $O(TN)$ complexiteit is de methode direct toepasbaar op industriële datasets.
• Theoretische inzicht: Het paper verduidelijkt de wiskundige grenzen van lineaire decompositie in machine learning en plaatst exacte attributie binnen een breder raamwerk van impliciete differentiatie.

Kortom, AXIL transformeert GBM's van "zwarte dozen" naar modellen waarvan de afhankelijkheid van individuele trainingsvoorbeelden exact en efficiënt kan worden gekwantificeerd.