💻 computer science

Ternary Decision Trees with Locally-Adaptive Uncertainty Zones

Dit artikel introduceert ternaire beslisbomen die standaard CART verbeteren door lokaal-adaptieve onzekerheidszones toe te voegen bij splitsingsknopen, waarbij voor ambiguïteit een gewogen mengsel van voorspellingen van de kinderen wordt gebruikt, en toont aan dat deze aanpak de beslisnauwkeurigheid aanzienlijk verbetert over diverse datasets terwijl het bruikbare onzekerheidsvlaggen biedt zonder externe hyperparameters te vereisen.

Oorspronkelijke auteurs: William Smits

Gepubliceerd 2026-05-22

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: William Smits

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een rechter bent die een rechtszaak leidt. In een standaardbeslissingsboom (het soort dat computers meestal gebruiken), wordt elke zaak gedwongen in één van twee dozen: Schuldig of Niet Schuldig.

De rechter neemt deze beslissing op basis van één harde lijn. Bijvoorbeeld: "Als de snelheid hoger is dan 60 mijl per uur, ben je schuldig."

Als je 61 mijl per uur reed, ben je schuldig.
Als je 100 mijl per uur reed, ben je ook schuldig.

Voor de standaardrechter voelen deze twee zaken precies hetzelfde aan. Maar in werkelijkheid zit de persoon die 61 mijl per uur reed precies op de rand van de wet. Misschien was de snelheidsmeter ietsje verkeerd afgesteld, of waren de wegomstandigheden lastig. De persoon die 100 mijl per uur reed, is daarentegen duidelijk en met zekerheid schuldig. Standaardbeslissingsbomen behandelen beide met hetzelfde niveau van zekerheid, wat riskant kan zijn.

Het Nieuwe Idee: De Rechter van de "Grijze Zone"

Dit artikel introduceert een nieuw type rechter genaamd een Ternaire Beslissingsboom. In plaats van slechts twee dozen, heeft deze rechter een derde optie: een "Grijze Zone" (of een "Onzekerheidszone").

Zo werkt het:

De Duidelijke Zaken: Als je 100 mijl per uur rijdt, zegt de rechter: "Schuldig!" (Zeker). Als je 40 mijl per uur rijdt, zegt de rechter: "Niet Schuldig!" (Zeker).
De Grijze Zone: Als je 61 mijl per uur rijdt (net iets boven de limiet), dwingt de rechter geen enkel vonnis af. In plaats daarvan zegt hij: "Onbeslist."

Wanneer een zaak in de "Onbesliste" zone terechtkomt, gooit de rechter de zaak niet weg. Hij geeft je nog steeds een voorspelling, maar die is gecombineerd. Stel je voor dat de rechter twee andere experts vraagt om hun mening te geven (een die neigt naar "Schuldig" en een die neigt naar "Niet Schuldig"). Ze mengen hun meningen om je een definitief antwoord te geven, maar ze plakken ook een groot sticker op je dossier met de tekst: "Voorzorg: Dit was een krappe zaak."

Hoe weet de Rechter waar hij de Grijze Lijn moet trekken?

Het lastige deel is beslissen hoe breed deze "Grijze Zone" moet zijn. Moet hij 1 mijl per uur breed zijn? 5 mijl breed?

Eerdere methoden vereisten dat de rechter een handleiding of een sensor had die hem precies vertelde hoeveel fout er in de snelheidsmeter zat. Maar dit artikel zegt: "We hebben geen extra gereedschap nodig. We kunnen het uitzoeken door alleen te kijken naar het bewijsmateriaal dat al in de kamer aanwezig is."

De auteurs hebben vijf verschillende manieren bedacht waarop de rechter de grootte van deze Grijze Zone kan berekenen met uitsluitend de gegevens van de huidige zaak:

De "Vlakke Top" Methode (Kwaliteitsplateau): Als het bewijsmateriaal bijna even goed is voor verschillende snelheidslimieten, weet de rechter dat de lijn vaag is en maakt hij de Grijze Zone breder.
De "Overvolle Kamer" Methode (Klasse-overlapping): Als de "Schuldige" mensen en de "Niet Schuldige" mensen allemaal direct naast elkaar in de rechtszaal staan, weet de rechter dat het een rommelig gebied is en verbreedt hij de Grijze Zone.
De "Zekerheidsscore" Methode (Gain Ratio): Als de splitsing in de gegevens zeer zwak is (het bewijsmateriaal is verwarrend), verbreedt de rechter de Grijze Zone.
De "Terugspelen" Methode (Node Bootstrap): De rechter stelt zich voor dat hij het proces 10 of 20 keer opnieuw afspeelt met lichtjes verschillende groepen getuigen. Als het vonnis elke keer verandert, weet de rechter dat de lijn onstabiel is en maakt hij de Grijze Zone groter.
De "Dichtstbijzijnde Buur" Methode (Marge): De rechter kijkt naar de twee mensen die het dichtst bij de lijn staan aan tegenovergestelde kanten. Als ze direct naast elkaar staan, is de Grijze Zone miniem. Als er een groot gat tussen hen is, is de Grijze Zone groter.

Wat Vonden Ze?

De auteurs hebben deze nieuwe "Grijze Zone"-rechter getest op 72 verschillende real-world datasets (zoals medische dossiers, financiële gegevens en synthetische puzzels).

Het Resultaat: De nieuwe rechters waren veel beter in het tonen van zekerheid wanneer ze gelijk hadden. Door de "krappe zaken" (de Grijze Zone-zaken) te markeren en ze anders te behandelen, werd het systeem nauwkeuriger op de zaken die het wel besliste.
De Winnaar: Eén methode, genaamd "Marge" (de "Dichtstbijzijnde Buur"-methode), was de beste allrounder. Het had geen extra instellingen nodig, was snel en werkte uitstekend. Het markeerde ongeveer 17% van de zaken als "krappe zaken", maar de resterende 83% werden beslist met veel hogere nauwkeurigheid dan standaardbomen.
Medisch Voorbeeld: Op een dataset over mammografieën (borstkankerscreening) markeerde de nieuwe methode ongeveer 11% van de zaken als "krappe zaken". Voor deze specifieke zaken suggereerde het systeem een tweede blik. Dit stelde het systeem in staat om nauwkeuriger te zijn op de duidelijke zaken, terwijl het de aandacht vestigde op diegenen die extra aandacht nodig hadden.

De Conclusie

Standaardbeslissingsbomen zijn als een stijve schakelaar: Aan of Uit.
Dit artikel introduceert een dimmer. Het stelt de computer in staat om te zeggen: "Ik ben vrij zeker, maar ik ben niet 100% zeker", voor de lastige zaken.

Door deze "krappe zaken" automatisch te identificeren met uitsluitend de beschikbare gegevens, kan het systeem downstream-toepassingen (zoals een arts of een kredietbeoordelaar) waarschuwen om extra aandacht te besteden aan die specifieke zaken, in plaats van blindelings te vertrouwen op een zeker klinkende maar potentieel wankel voorspelling.

Technische Samenvatting: Ternaire Beslissingsbomen met Lokaal-Adaptieve Onzekerheidszones

Probleemstelling

Standaard beslissingsbomen, met name die gebaseerd op het CART-algoritme, partitioneren de kenmerkruimte met harde binaire drempels. Dit mechanisme wijst identiek vertrouwen toe aan instanties, ongeacht hun nabijheid tot de beslissingsgrens. Bijgevolg wordt een instantie die ver verwijderd is van de optimale drempel $\theta$ met dezelfde zekerheid behandeld als een instantie die direct daarop ligt. Deze "harde toewijzing" creëert een bekende zwakte: het overdrijft de zekerheid voor instanties nabij grenzen waar de geleerde splitsing het minst betrouwbaar is, en faalt om doorstroomtoepassingen te signaleren dat een voorspelling mogelijk dubbelzinnig is.

Bestaande benaderingen om onzekerheid aan te pakken, vertrouwen vaak op externe ruispecificaties (bijv. bekende sensorfouten) of globale drempels afgeleid van datasetstatistieken. Deze methoden passen zich niet lokaal aan aan de specifieke splitsingskwaliteit of dataverdeling bij elke knoop. Bovendien ontbreekt het bij benaderingen zoals vage beslissingsbomen of zachte beslissingsbomen vaak aan een expliciete, interpreteerbare onzekerheidszone die is afgeleid van lokale splitsingsstatistieken.

Methodologie

Het artikel introduceert Ternaire Beslissingsbomen, die standaard binaire splitsingen verrijken met een lokaal-adaptieve onzekerheidszone met halve breedte $\delta$ , gecentreerd rond de optimale drempel $\theta^*$ .

De Ternaire Evaluatie

Voor een kenmerk $x_f$ en drempel $\theta^*$ wordt de beslissingslogica gedefinieerd als:

Waar (Beslissend): $x_f > \theta^* + \delta$
Onwaar (Beslissend): $x_f \leq \theta^* - \delta$
Ondec (Grens-Onzeker): $\theta^* - \delta < x_f \leq \theta^* + \delta$

Instanties die in de Ondec-zone vallen, onthouden zich niet van voorspelling. In plaats daarvan ontvangen ze een voorspelling die is gevormd door een op afstand gewogen menging van de waarschijnlijkheidsoutput van beide kindsubbomen. Cruciaal worden deze instanties gemarkeerd als "grens-onzeker", waardoor downstreamsystemen ze anders kunnen behandelen (bijv. door te routeren voor menselijke beoordeling) zonder een klassevoorspelling in te houden.

Lokaal Berekenen van $\delta$

De kern technische bijdrage is het lokaal afleiden van $\delta$ bij elke knoop met behulp van statistieken die al zijn berekend tijdens de standaard CART-splitsing, zonder externe data of ruismodellen. Het artikel stelt vijf methoden voor en evalueert deze:

Kwaliteitsplateau ( $\delta_{QP}$ ): Meet de breedte van het "plateau" in de splitsingscriteriumcurve (bijv. Gini-winst) rond $\theta^*$ . Een breed plateau geeft aan dat de data de optimale splitslocatie niet precies beperkt.
Klasse-Overlap ( $\delta_{CO}$ ): Berekent de breedte van het gebied waar klasse-voorwaardelijke kenmerkverdelingen overlappen, gebaseerd op empirische percentielen.
Winst-Ratio ( $\delta_{GR}$ ): Schalen de kenmerkrange omgekeerd evenredig met de winstratio (Informatiewinst relatief tot splitsentropie). Lage winstratio's duiden op dubbelzinnige splitsingen, wat leidt tot een groter $\delta$ .
Knoop-Bootstrap ( $\delta_{NB}$ ): Meet de standaardafwijking van de optimale drempel $\theta^*$ over bootstrap-resamples van de trainingsdata van de knoop. Dit kwantificeert direct de drempelinstabiliteit.
Marge ( $\delta_{M}$ ): Geïnspireerd door Support Vector Machines, definieert dit $\delta$ als de afstand van $\theta^*$ tot het dichtstbijzijnde trainingsvoorbeeld van een andere klasse (het "support vector" bij die knoop). Als de splitsing perfect schoon is, gebruikt het de fysieke opening tussen aangrenzende datapunten.

Routeringsarchitecturen

Twee architecturen zijn geëvalueerd voor het doorgeven van onzekere instanties:

Probabilistische Routering: De boomstructuur blijft binair. Tijdens voorspelling worden instanties in de onzekerheidszone naar beide kinderen gerouteerd met gewichten die omgekeerd evenredig zijn met hun afstand tot de drempel, en worden de outputs gemengd.
Harde Middelste Tak: Er wordt een derde kindknoop toegevoegd aan de boomstructuur, uitsluitend getraind op instanties binnen de onzekerheidszone.
Experimentele resultaten gaven aan dat probabilistische routering over het algemeen beter presteerde dan de harde-middelbenadering, aangezien laatstgenoemde onzekere voorbeelden verwijdert uit de trainingssets van de linker- en rechtertakken, wat hun kwaliteit verslechtert.

Belangrijkste Bijdragen

Kader: Introductie van ternaire beslissingsbomen die een principieel, lokaal-adaptieve onzekerheidszone bieden voor elke splitsing.
Vijf Schattingmethoden: Afleiding van vijf distincte methoden om $\delta$ te berekenen met uitsluitend standaard CART-splitsingsstatistieken, waardoor externe ruismodellen overbodig worden.
Routeringsevaluatie: Comparatieve analyse van probabilistische versus harde-middelroutering, waarbij de superioriteit van probabilistische menging voor de meeste methoden wordt aangetoond.
Uitgebreide Empirische Evaluatie: Evaluatie over 72 OpenML-CC18 datasets, drie Breiman synthetische benchmarks (met bekende Bayes-fouten), en vier hoog-risico medische/financiële datasets.
Diagnostisch Kader: Introductie van de Ondecided/Bayes (U/B) ratio om te beoordelen hoe goed de flaggingsnelheid van een methode overeenkomt met de theoretisch onherleidbare fout van een dataset.

Resultaten

Brede Validiteit (OpenML-CC18)

Over 72 datasets heen presteerden alle vijf methoden met probabilistische routering significant beter dan de standaard CART-baseline op Beslissende Nauwkeurigheid (nauwkeurigheid beperkt tot niet-onzekere instanties) met $p \leq 0.001$ .

Marge-methode: Bereikte de beste efficiëntie (nauwkeurigheidswinst per eenheid flaggingsnelheid, $\eta = 0.104$ ). Het won op 42 van de 72 datasets, markeerde slechts 16,7% van de instanties als onzeker, en vereiste geen extra hyperparameters.
Klasse-Overlap & Winst-Ratio: Bereikten hoge beslissende nauwkeurigheid maar markeerden een groot deel van de instanties (respectievelijk 71% en 58%), wat resulteerde in lagere efficiëntie.
Knoop-Bootstrap: Presteerde goed maar was computatiekostenintensief en werd uitgesloten van datasets met $N > 20.000$ .

Theoretische Analyse (Breiman Benchmarks)

Op synthetische datasets met bekende Bayes-fouten:

Marge: Toonde zelfkalibrerend gedrag op geometrisch schone data, waarbij zeer weinig instanties als onzeker werden gemarkeerd (U/B-ratio's < 0,5), en zich effectief gedroeg als CART wanneer de grens duidelijk is.
Knoop-Bootstrap & Kwaliteitsplateau: Toonden proportionele kalibratie, waarbij meer instanties werden gemarkeerd op moeilijkere datasets (hogere Bayes-fout), hoewel alle methoden meer markeerden dan de theoretische Bayes-fout (U/B > 1).
Kalibratiekloof: Geen enkele methode bereikte een U/B-ratio van 1,0, wat aangeeft dat lokale drempelonzeekerheid niet direct overeenkomt met de globale Bayes-fout.

Domein-toepassingen

Mammografie: Knoop-Bootstrap markeerde 10,8% van de gevallen als onzeker terwijl de beslissende nauwkeurigheid met 0,71% verbeterde ten opzichte van CART. Dit is waardevol voor het identificeren van gevallen die secundaire beoordeling nodig hebben.
Diabetes: Knoop-Bootstrap behaalde een +9,8% nauwkeurigheidswinst maar markeerde 63,4% van de patiënten, wat een afweging suggereert tussen nauwkeurigheid en flaggingsnelheid. De Marge-methode bood een meer conservatief, praktisch bedieningspunt (+0,4% winst, 9,5% flagging).
Beperkingen: Op de kleine Cleveland-hartziekte-dataset ( $N=303$ ) presteerde Knoop-Bootstrap slechter vanwege onbetrouwbare variantieschattingen. Op de Duitse kredietdataset presteerde de Marge-methode slechter dan de baseline, wat beperkingen suggereert met complexe economische kenmerkinteracties.

Betekenis en Claims

Het artikel claimt de ternaire boom te vestigen als een principieel primitief voor onzekerheidsbewuste classificatie. De betekenis ligt in:

Praktische Nut: Het bieden van een mechanisme om grens-onzekere voorspellingen te flaggen zonder zich te onthouden, waardoor downstreamsystemen (bijv. medische screening, kredietonderhandeling) verschillende behandelingsstrategieën kunnen toepassen.
Berekenbare Haalbaarheid: Het afleiden van onzekerheidszones uit bestaande splitsingsstatistieken zonder externe data of complexe hertraining te vereisen.
Theoretische Grondslag: Het bieden van een kader waarin het "Ondec"-verdict een kwalificatie is op de voorspellingszekerheid in plaats van een afwijzing van de voorspelling zelf.

De auteurs merken bescheiden op dat hoewel de methoden de beslissende nauwkeurigheid verbeteren, ze de flaggingsnelheid nog niet perfect kalibreren op de theoretische Bayes-fout, en identificeren deze kalibratie als een concreet open probleem voor toekomstig werk.