Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

Technische Samenvatting: Kwantificering van Gevoeligheid voor Boom-Ensembles

Probleemstelling
Beslissingsboom-ensembles (DTE's), zoals XGBoost en Random Forests, worden veel gebruikt in veiligheidskritieke domeinen, maar vormen uitdagingen voor formele verificatie. Hoewel bestaand werk de existentie van gevoeligheid heeft aangepakt (het vinden van één enkel "gevoelig paar" van invoeren die alleen verschillen in beschermde kenmerken maar verschillende uitkomsten opleveren), betoogt dit artikel dat binaire existentiecontroles ontoereikend zijn voor een kwantitatief begrip van modelfairheid. Het kernprobleem dat wordt aangepakt, is de kwantificering van gevoeligheid: het bepalen van het volume of het aantal invoergebieden in een DTE waar kleine verstoringen in gevoelige kenmerken leiden tot verkeerde classificatie of aanzienlijke veranderingen in de uitkomst. Dit probleem verschilt van lokale robuustheid (het controleren van een omgeving van een specifieke invoer) en is computationeel moeilijker, omdat het valt in de #P-hard complexiteitsklasse, aangezien het vereist dat de hele invoerruimte wordt doorzocht om vervullende toewijzingen te tellen in plaats van er slechts één te vinden.

Methodologie
De auteurs stellen XCount voor, een nieuw algoritmisch raamwerk dat kenniscompilatie, compositieve decompositie en benaderende modeltelling combineert om het aantal gevoelige gebieden te schatten met formele garanties.

1. Discretisatie en Symbolische Encodering:
   De continue invoerruimte wordt gediscretiseerd op basis van de bewaakpredicaten (kenmerk-drempelparen) van de DTE. Dit brengt de invoerruimte in kaart naar een eindige verzameling Booleaanse vectoren. Het gedrag van het model wordt gecodeerd met behulp van Algebraïsche Beslissingsdiagrammen (ADD's), een kwantitatieve uitbreiding van Binair Beslissingsdiagrammen (BDD's). ADD's maken een efficiënte representatie mogelijk van de additieve structuur van het ensemble ($T(x) = \sum T_i(x)$).

2. Compositieve Decompositie:
   Het direct compileren van een grote DTE naar een monoliet ADD is geheugenintensief en vaak onuitvoerbaar. Om dit te overwinnen, hanteert het algoritme een verdeel-en-heers-strategie:

   • Het probleem wordt opgesplitst in deelproblemen op basis van paren bitmaskers (toewijzingen aan gevoelige kenmerken) die maximaal $d$ bits van elkaar verschillen (Hamming-afstand).
   • Voor elk paar worden de gevoelige kenmerken vastgezet en worden de beslissingsbomen "gesnoeid" om onbereikbare takken te verwijderen, wat resulteert in kleinere, hanteerbare deelproblemen.
   • Elk deelprobleem berekent het verschil in uitkomsten tussen de twee vastgezette toewijzingen.

3. Benaderende Telling met PAC-Garanties:
   In plaats van exacte telling uit te voeren op de unie van alle oplossingen van de deelproblemen (wat de complexiteit van overlappende verzamelingen opnieuw zou introduceren), passen de auteurs een techniek uit de database-theorie toe voor het benaderen van het volume van een unie van verzamelingen in een streaming-model.

   • Het algoritme steekt vervullende toewijzingen uit de deelproblemen (weergegeven als BDD's) met behulp van een probabilistische aanpak.
   • Het onderhoudt een set steekproeven en past de steekproefkans dynamisch aan om ervoor te zorgen dat de uiteindelijke schatting $\hat{C}$ voldoet aan Probably Approximately Correct (PAC) garanties: $Pr[(1-\epsilon)C \leq \hat{C} \leq (1+\epsilon)C] \geq 1-\delta$.

Belangrijkste Bijdragen

1. Kwantitatieve Formulering: Het artikel definieert een gediscretiseerde, kwantitatieve notie van gevoeligheid die het aantal invoergebieden telt dat een gevoelig paar toestaat, en gaat verder dan eenvoudige existentiecontroles.
2. Compositief Algoritme: Het introduceert een splitsings- en samenvoegstrategie die het globale tellingsprobleem decomposeert in paralleliseerbare deelproblemen, waarmee de schaalbaarheidsproblemen van monoliete ADD-compilatie worden aangepakt.
3. Theoretische Sluitendheid: De methode biedt sterke theoretische garanties, waarbij wordt gewaarborgd dat de benaderde telling binnen een door de gebruiker gedefinieerde foutmarge ($\epsilon$) ligt met een gespecificeerd betrouwbaarheidsniveau ($1-\delta$).
4. Implementatie en Validatie: De auteurs hebben de tool XCount geïmplementeerd en gevalideerd tegen state-of-the-art exacte modeltellers (Ganak) en benaderende tellers (ApproxMC), evenals een monoliete ADD-baseline.

Experimentele Resultaten
De auteurs hebben XCount geëvalueerd op 3.194 benchmarkinstanties afgeleid van 10 real-world datasets (bijvoorbeeld Adult, Diabetes, Higgs) met variërende ensemblegroottes (10–100 bomen) en dieptes (3–6).

• Prestaties: XCount presteerde aanzienlijk beter dan alle baselines. Het loste 1.552 instanties op, vergeleken met 721 voor Ganak en 579 voor ApproxMC. Het behaalde een Gestrafte Gemiddelde Runtime (PAR2) van 1.937 seconden, wat een verbetering van 33% vertegenwoordigt ten opzichte van de volgende beste aanpak en een verbetering van 43% ten opzichte van de ADD-baseline.
• Nauwkeurigheid: Voor instanties waar exacte tellingen beschikbaar waren, behield XCount hoge fideliteit, waarbij 99% van de schattingen binnen de voorgeschreven foutmarge van 10% viel ($\epsilon=0.1$).
• Schaalbaarheid: De tool toonde superieure schaalbaarheid met toenemende ensemblegrootte en diepte, terwijl de monoliete ADD-aanpak faalde om te schalen buiten kleine instanties.

Betekenis en Toepassingen
Het artikel beweert dat XCount een schaalbare, sluitende en complete methode biedt voor het kwantificeren van gevoeligheid in DTE's, een taak die eerder als onuitvoerbaar werd beschouwd voor grote modellen.

• Validatie van Regularisatie: Als specifieke toepassing hebben de auteurs XCount gebruikt om de effectiviteit van L1-regularisatie te valideren. Zij toonden aan dat het verhogen van de regularisatieparameter $\alpha$ correleert met een afname van het aantal gevoelige gebieden, wat suggereert dat het tellen van gevoeligheid kan dienen als een maatstaf voor het beoordelen van modeloverfitting en generalisatie zonder toegang tot interne trainingsparameters.
• Fairness en Veiligheid: Door het "volume" van onrechtvaardigheid te kwantificeren, biedt de aanpak een genuanceerdere maatstaf voor individuele fairheid en causale discriminatie dan binaire verificatie, waardoor praktici modellen kunnen afstemmen om specifieke regelgevende drempels te halen (bijvoorbeeld het garanderen dat gevoeligheid onder de 1% van de invoerruimte blijft).

De auteurs concluderen dat, hoewel hun werk zich richt op DTE's, de compositieve en probabilistische technieken generaliseerbaar zijn, en dat toekomstig werk zal onderzoeken hoe deze gevoeligheidstellingen kunnen worden toegepast om modellen te rangschikken en de aanpak uit te breiden naar andere klassen van machine learning-modellen.