Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Dit artikel introduceert een theoretisch raamwerk voor het ontleden van observatieve multipliciteit in beslisbomen in 'leaf regret' en 'structurele regret', waarbij wordt aangetoond dat structurele instabiliteit de dominante bron van variatie is en dat deze maatstaven de modelveiligheid kunnen verbeteren door selectief voorspellen.

De kern

Titel: Waarom Twee Boekhouders Met Dezelfde Getallen Tot Verschillende Conclusies Kunnen Kommen

Stel je voor dat je een grote groep mensen moet beoordelen op hun kredietwaardigheid. Je gebruikt een slim computerprogramma (een "beslissingsboom") om te voorspellen wie een lening krijgt en wie niet. Je denkt: "Oké, de computer is slim, het antwoord is objectief."

Maar wat als ik je zeg dat als je dezelfde data net even anders zou verzamelen – bijvoorbeeld door een paar willekeurige klanten een dag later te interviewen – de computer een heel ander antwoord zou geven voor dezelfde persoon?

Dat is het probleem waar dit onderzoek over gaat. Het heet voorspellende multipliciteit: er zijn veel verschillende modellen die allemaal even goed werken, maar die voor jou als individu een totaal ander advies geven.

De auteurs van dit paper, Mustafa Cavus en zijn team, hebben een manier bedacht om te begrijpen waarom die verschillen ontstaan. Ze splitsen de verwarring op in twee soorten "spijt" (in het Engels: regret). Laten we het uitleggen met een simpele analogie.

De Twee Soorten "Spit" (Regret)

Stel je voor dat je een boom hebt die mensen in groepjes verdeelt (bijvoorbeeld: "Mensen met een hoog inkomen" vs. "Mensen met een laag inkomen"). Binnen die groepjes maakt de computer een voorspelling.

De auteurs zeggen dat de onzekerheid in de voorspelling uit twee bronnen komt:

1. Blad-Spijt (Leaf Regret): De "Ruis" in de Groep

Stel je voor dat je in een groepje van 10 mensen zit die allemaal "hoog inkomen" hebben. De computer kijkt naar deze 10 mensen en zegt: "9 van de 10 hebben een goede creditcard, dus jij ook."
Maar wat als je die 10 mensen had gewisseld met 10 andere mensen uit dezelfde groep? Misschien hadden er dan 8 goede creditcards en 2 slechte gehad. De voorspelling zou dan iets anders zijn.

• De Analogie: Dit is als het meten van de temperatuur met een onnauwkeurige thermometer. Als je 10 keer meet, krijg je 10 verschillende getallen. De groep zelf is stabiel, maar de meting binnen die groep is een beetje wazig door toeval.
• In het kort: Dit is de onzekerheid die ontstaat omdat je niet alle mensen in de wereld kent, maar slechts een steekproef. Het is "ruis" binnen een vast groepje.

2. Structuur-Spijt (Structural Regret): De "Willekeur" van de Groepindeling

Nu komt het spannende deel. Wat als de computer de hele boom anders opbouwt?
Stel je voor dat de computer besluit: "Nee, we verdelen mensen niet op inkomen, maar op hun leeftijd." Of misschien maakt hij een heel andere scheidslijn: "Mensen met een inkomen boven 3000 euro" in plaats van "boven 2500 euro".

Door deze kleine verandering in de indeling van de groepen, belandt jij plotseling in een heel ander groepje met een heel ander advies.

• De Analogie: Dit is alsof je een grote taart in stukken snijdt. Als je de taart net iets anders snijdt (een andere hoek, een andere dikte), beland jij plotseling in een ander stukje taart. Het stukje taart zelf is misschien perfect, maar het feit dat je in een ander stukje zit, verandert je ervaring volledig.
• In het kort: Dit is de onzekerheid die ontstaat omdat de computer zelf niet weet hoe hij de wereld het beste moet verdelen. Het is de instabiliteit van de kaart zelf, niet van de punten op de kaart.

Wat Vonden Ze?

De onderzoekers hebben dit getest op echte data (zoals kredietgegevens uit Taiwan, Duitsland en Polen). Hun belangrijkste ontdekkingen zijn:

1. De Indeling is de Boosdoener: Ze ontdekten dat de meeste verwarring (meer dan 15 keer zoveel!) komt door Structuur-Spijt. De manier waarop de computer de groepen indeelt, is veel onstabiel dan de ruis binnen die groepen.
   • Dagelijkse taal: Het probleem is niet dat de thermometer onnauwkeurig is, maar dat de kaart waarop we de gebieden afbakenen, steeds een beetje verschuift.
2. Het Werkt als een Veiligheidsnet: Ze bedachten een slimme truc. Als de computer merkt dat een voorspelling heel gevoelig is voor deze "willekeurige indeling" (hoge structuur-spijt), kan hij zeggen: "Ik durf dit niet te zeggen."
   • In plaats van een gok te doen, zegt de computer: "Ik weet het niet zeker, laat een mens dit controleren."
   • Door dit te doen, konden ze in sommige gevallen het succespercentage (recall) van goede voorspellingen van 92% naar 100% brengen. Ze lieten alleen de "veilige" voorspellingen door en stopten de twijfelachtige gevallen bij mensen.

Waarom is Dit Belangrijk?

In belangrijke situaties – zoals het geven van een hypotheek, het diagnosticeren van een ziekte of het beoordelen van een straf – is het niet genoeg om te zeggen: "Gemiddeld werkt het goed."

Als een computer voor jou "ja" zegt en voor je buurman "nee", terwijl jullie bijna hetzelfde zijn, is dat gevaarlijk. Dit onderzoek geeft ons een manier om te zien:

• Is het probleem dat we te weinig data hebben? (Blad-spijt)
• Of is het probleem dat het algoritme zelf te wispelturig is? (Structuur-spijt)

En het beste nieuws: als we weten dat het algoritme wispelturig is, kunnen we het systeem "eerlijk" maken. We kunnen het systeem leren om te zeggen: "Ik twijfel, vraag een mens." Dat maakt beslissingen veiliger en eerlijker voor iedereen.

Samenvattend:
De auteurs hebben een meetlat bedacht om te zien waarom computers soms wisselende antwoorden geven. Ze ontdekten dat de grootste oorzaak niet de data zelf is, maar de manier waarop de computer de wereld indeelt. Door dit te meten, kunnen we slimme systemen veiliger maken door ze te laten twijelen waar het nodig is, in plaats van ze blindelings te laten gokken.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret" in het Nederlands.

Titel: Ontleding van Observationele Multipliciteit in Beslissingsbomen: Leaf- en Structurele Regret

1. Het Probleem: Observationele Multipliciteit

In hoog-risico domeinen zoals krediet scoring, gezondheidszorg en juridische risicobeoordeling is het niet alleen belangrijk dat machine learning-modellen een hoge algehele nauwkeurigheid hebben, maar ook dat individuele voorspellingen betrouwbaar en rechtvaardig zijn. Een groeiend probleem is predictieve multipliciteit: het bestaan van meerdere modellen met bijna identieke prestaties die echter tegenstrijdige voorspellingen geven voor dezelfde individuen.

Een fundamentele bron hiervan is observationele multipliciteit. Dit fenomeen ontstaat door de stochastische aard van het verzamelen van labels. De waargenomen trainingslabels zijn slechts één realisatie van onderliggende grond-waarheid waarschijnlijkheden. Als men een andere, even waarschijnlijke set labels uit dezelfde verdeling zou trekken, zou dit leiden tot een ander getraind model.

Hoewel dit concept theoretisch voor logistieke regressie is onderzocht, blijft het voor niet-gladde, op partities gebaseerde modellen (zoals beslissingsbomen) onderbelicht. Beslissingsbomen zijn berucht om hun gevoeligheid voor kleine data-perturbaties. Het artikel stelt dat er twee verschillende bronnen van onzekerheid zijn die vaak door elkaar worden gehaald:

1. Aleatorische onzekerheid: Ruis binnen een vaste leaf (door eindige steekproefgrootte).
2. Epistemische onzekerheid: Instabiliteit van de boomstructuur zelf (door variatie in de gekozen splitsingen).

2. Methodologie: Decompositie van Regret

De auteurs introduceren een formeel raamwerk om de totale observationele multipliciteit te ontleden in twee complementaire componenten: Leaf Regret en Structural Regret.

• Leaf Regret ($R_{leaf}$):

  • Definitie: De conditionele variantie van de waarschijnlijkheidsschatting binnen een vaste leaf, gegeven een specifieke boomstructuur.
  • Oorzaak: Variabiliteit door stochastische realisaties van labels binnen een vaste partitiecel.
  • Formule: $R_{leaf}^L = \text{Var}(\hat{p}_L | L) = \frac{p^*_L(1-p^*_L)}{n_L}$, waarbij $n_L$ het aantal observaties in de leaf is.
  • Eigenschappen: Dit is een goed gedefinieerde statistische grootheid met een gesloten vorm. Het neemt af naarmate de leaf-grootte ($n_L$) toeneemt (concentratie-ongelijkheden worden bewezen).

• Structural Regret ($R_{struct}$):

  • Definitie: De variantie in voorspellingen veroorzaakt door de willekeur in de geleerde boomstructuur zelf.
  • Oorzaak: Instabiliteit in de selectie van splitsingen door variatie in de trainingsdata.
  • Analyse: Omdat de verdeling van boomstructuren complex is, wordt dit benaderd via Monte Carlo-simulaties (bootstrap-steekproeven) in plaats van een gesloten vorm.
  • Decompositie: De totale voorspellende variantie voor een input $x$ wordt ontbonden als:
    $$\text{Var}(\hat{p}(x)) = \mathbb{E}_T[R_{leaf}^{L(x;T)}] + R_{struct}(x)$$
    Waarbij de eerste term de verwachte leaf-regret is en de tweede term de structurele regret.

• Schatting:

  • Voor Leaf Regret wordt een plug-in schatter gebruikt die consistent is en waarvan de afwijking exponentieel klein wordt naarmate $n_L$ groeit.
  • Voor Structural Regret wordt een Monte Carlo-procedure voorgesteld waarbij $B$ bomen worden getraind op bootstrap-steekproeven om de variantie in voorspellingen te berekenen.

3. Belangrijkste Bijdragen

1. Conceptuele Decompositie: Het is de eerste studie die observationele multipliciteit in beslissingsbomen formeel splitst in "ruis binnen de structuur" (leaf) en "instabiliteit van de structuur" (structural).
2. Theoretische Garanties: De auteurs leveren wiskundige bewijzen voor de goed-gedefinieerdheid, consistentie en concentratie-eigenschappen van leaf regret.
3. Empirische Validatie: Het raamwerk wordt getest op diverse credit risk datasets, waarbij wordt aangetoond dat de som van de geschatte componenten de werkelijke variantie bijna perfect benadert.
4. Toepassing in Selectieve Voorspelling: Het gebruik van regret-maten als mechanisme voor "abstention" (het weigeren van een voorspelling) om de veiligheid van het model te verhogen.

4. Resultaten

De experimenten zijn uitgevoerd op diverse datasets (o.a. taiwan_credit, hmeq, german_credit).

• Validatie van Decompositie: Er is een bijna perfecte correlatie gevonden tussen de theoretisch berekende som van leaf- en structural regret en de empirisch waargenomen variantie (de punten liggen op de lijn $y=x$).
• Dominantie van Structurele Regret: De analyse toont aan dat structurele regret de primaire drijvende kracht is van observationele multipliciteit. In sommige datasets (zoals taiwan_credit) is de structurele component meer dan 15 keer groter dan de leaf regret. Dit betekent dat de onzekerheid voornamelijk voortkomt uit de instabiliteit van de partitiegrenzen, niet uit ruis binnen de leaf.
• Invloed van Leaf-grootte: Een toename van de minimale leaf-grootte ($n_L$) vermindert de leaf regret drastisch (in lijn met theorie), maar leidt tot een toename van de logistische loss (onderfitting), wat een afweging vereist.
• Selectieve Voorspelling (Safety):
  • Door individuen te rangschikken op basis van hun totale regret en de hoogste regret-voorspellingen te laten vallen (abstention), kan de recall voor de meest stabiele sub-populaties worden verhoogd van 92% naar 100%.
  • Dit mechanisme identificeert "willekeurige" gebieden waar het model eigenlijk "raadt" vanwege label-instabiliteit.
  • Structurele regret bleek een robuustere filter te zijn dan leaf regret voor het identificeren van moeilijke positieve gevallen.

5. Betekenis en Conclusie

Deze studie biedt een rigoureus raamwerk om de onzekerheid in beslissingsbomen te kwantificeren. De belangrijkste inzichten zijn:

• Prioritering van Stabiliteit: Omdat structurele regret de dominante bron van onzekerheid is, moeten mitigatiestrategieën zich richten op het stabiliseren van de boomstructuur (bijv. via sterkere regularisatie, pruning of ensemble-methoden) in plaats van alleen het vergroten van steekproefgroottes in leaves.
• Veiligheid en Interpretatie: Het onderscheid tussen lokale ruis en globale instabiliteit maakt het mogelijk om modellen "eerlijk" te maken. Als een voorspelling een hoge structurele regret heeft, kan het systeem dit signaleren aan menselijke operators voor handmatige review, in plaats van een arbitraire automatische beslissing te nemen.
• Toekomstige Richting: Het raamwerk is nu beperkt tot binaire classificatie met enkele bomen; uitbreiding naar multiclass en ensemble-methoden (zoals Random Forests) is een logische volgende stap.

Kortom, dit werk verlegt de focus van "hoe accuraat is het model gemiddeld?" naar "hoe stabiel is de voorspelling voor dit specifieke individu, en wat is de bron van de onzekerheid?", wat essentieel is voor de veilige implementatie van AI in hoog-risico omgevingen.