Decision Tree Learning on Product Spaces

Technische Samenvatting: Leren van Beslissingsbomen op Productruimtes

Probleemstelling
Leren van beslissingsbomen is een hoeksteen van machine learning, gewaardeerd om zijn interpreteerbaarheid en empirisch succes. De standaard praktische aanpak is de top-down greedy-heuristiek, die recursief knopen splitst op basis van de meest "invloedrijke" variabele (vaak gemeten via impureteitsreductie zoals entropie of Gini-index). Hoewel empirisch effectief, is het theoretisch inzicht in deze heuristiek beperkt. Eerdere rigoureuze garanties, zoals die van Blanc et al. (ITCS, 2020), waren beperkt tot de uniforme verdeling over de Boolese hyperkubus. Deze aanname faalt om real-world data te vangen, waarbij kenmerken vaak heterogene, niet-uniforme productverdelingen volgen. Bovendien stellen veel theoretische werken complexe, niet-greedy algoritmen voor (bijvoorbeeld bottom-up of brute-force zoekopdrachten) die afwijken van praktische implementaties, waardoor er een kloof ontstaat tussen theorie en praktijk.

Methodologie
De auteurs breiden de theoretische analyse van de top-down greedy-heuristiek uit naar willekeurige productverdelingen. De setting omvat het leren van een Boolese functie $f: \{0, 1\}^n \to \{\pm 1\}$ onder een productverdeling $\mu = \mu_1 \times \dots \times \mu_n$, waarbij elke bit met waarschijnlijkheid $p_i$ de waarde 1 heeft.

Het geanalyseerde kernalgoritme is BuildTopDownDT, een formalisering van de standaard greedy-aanpak:

1. Initialisatie: Start met een enkel blad.
2. Scoren: Op elk moment scoort men elk blad $l$ in de huidige boom. De score wordt gedefinieerd als de waarschijnlijkheidsmassa die het blad bereikt ($p_l$) vermenigvuldigd met de maximale invloed van een variabele op de subfunctie op dat blad ($\max_i \text{Inf}_i(f_l)$).
3. Splitsen: Selecteer het blad met de hoogste score en split dit op zijn meest invloedrijke variabele.
4. Beëindiging: Herhaal totdat de $f$-completing van de boom (toewijzen van het meerderheidslabel aan bladeren) een $\epsilon$-benadering van $f$ is.

Om dit te analyseren, introduceren de auteurs een potentieel functie genaamd de kosten van een kale boom (ongelabeld), gedefinieerd als de som van de totale invloed van de subfuncties op elk blad, gewogen met de waarschijnlijkheid om dat blad te bereiken. Zij stellen een relatie vast tussen deze kosten, de benaderingsfout en de structurele eigenschappen van de optimale boom (maximale diepte $D_{\text{opt}}$ en gemiddelde diepte $\Delta_{\text{opt}}$).

Belangrijkste Bijdragen

1. Generalisatie naar Productverdelingen: Het artikel biedt de eerste rigoureuze prestatiegaranties voor de top-down greedy-heuristiek onder willekeurige productverdelingen, waardoor de restrictieve aanname van een uniforme verdeling uit eerdere werken wordt verwijderd.
2. Verbeterde Groottegrenzen: Het belangrijkste theoretische resultaat (Stelling 1.1) stelt dat voor elke functie die berekenbaar is door een optimale boom van grootte $s$, maximale diepte $D_{\text{opt}}$ en gemiddelde diepte $\Delta_{\text{opt}}$, de greedy-heuristiek een $\epsilon$-benaderende boom construeert met een grootte van ten hoogste:
   $$\max \left( \left( \frac{e \cdot \Delta_{\text{opt}}}{\epsilon D_{\text{opt}}} \right)^{\Delta_{\text{opt}} D_{\text{opt}}}, e^{\Delta_{\text{opt}} D_{\text{opt}}} \right)$$
   • Gebalanceerd Regime: Voor volledige binaire bomen waar $D_{\text{opt}} = \Delta_{\text{opt}} = \log s$, vereenvoudigt de grens tot $s^{O(\log s \cdot \log(e/\epsilon))}$. Dit is een quasi-polynomiale grens die verbetert op de grens vastgesteld door Blanc et al. (2020) en geldt voor een strikt bredere klasse van verdelingen.
   • Pad-achtig Regime: Voor sterk ongebalanceerde bomen (bijvoorbeeld pad-bomen) kan $D_{\text{opt}}$ $O(n)$ zijn terwijl $\Delta_{\text{opt}}$ een kleine constante blijft. De gemengde afhankelijkheid van $\Delta_{\text{opt}}$ en $D_{\text{opt}}$ levert een grens op die exponentieel strakker is dan een grens die uitsluitend afhankelijk is van $D_{\text{opt}}$ (wat $e^{O(n^2)}$ zou zijn versus de afgeleide $e^{O(n)}$).
3. Parameterloze Praktische Implementatie: De auteurs presenteren Algoritme 2, een praktische implementatie van de heuristiek die volledig parameterloos is. In tegenstelling tot eerdere theoretische analyses die kennis veronderstellen van de grootte ($s$) of diepte van de optimale boom, vertrouwt dit algoritme op schattingen van scores en fouten gebaseerd op steekproeven. Het verhoogt adaptief de steekproefgroottes om statistisch vertrouwen te behouden zonder voorafgaande kennis van de complexiteit van de doelfunctie.
4. Robuustheid tegen Schatting: Theoretische garanties blijken te gelden zelfs wanneer het algoritme een blad selecteert met een score die slechts een constante fractie (bijvoorbeeld $1/4$) is van de maximaal mogelijke score, waarmee het de ruis inherent aan schattingen op basis van steekproeven opvangt.

Resultaten

• Theoretisch: Het artikel bewijst dat de greedy-heuristiek quasi-polynomiale groottegrenzen bereikt in het gebalanceerde regime en aanzienlijk betere grenzen in ongebalanceerde regimes vergeleken met grenzen die uitsluitend afhankelijk zijn van de maximale diepte. De analyse steunt op nieuwe lemma's die de kosten van de boom relateren aan de fout en lagere grenzen vaststellen voor de score van het geselecteerde blad in termen van de huidige fout en boomdiepte.
• Empirisch: De auteurs bieden een empirische evaluatie van hun parameterloze algoritme (Algoritme 2) op zowel gebalanceerde als ongebalanceerde doelen voor beslissingsbomen onder variërende productverdelingen (uniform, matige bias, zware bias). De resultaten bevestigen dat de herstelde boomgroottes dicht bij de grondwaarheid-doelen blijven en ruim binnen de theoretische grenzen vallen, waarbij de steekproefcomplexiteit polynomiaal groeit in de dimensie en $1/\epsilon$.

Betekenis en Claims
Het artikel claimt de kloof te dichten tussen de theoretische analyse van leren van beslissingsbomen en de praktische toepassing daarvan. Door de klassieke, eenvoudige greedy-heuristiek (gebruikt in ID3, C4.5, CART) te analyseren in plaats van complexe, niet-greedy varianten, bieden de auteurs een rigoureuze rechtvaardiging voor de sterke empirische prestaties van deze wijdverspreide algoritmen.

De betekenis ligt in:

• Realisme: Voorbijgaan aan de uniforme verdeling naar willekeurige productverdelingen, die real-world data beter modelleren.
• Praktijkgerichtheid: Het bieden van een parameterloos algoritme dat geen voorafgaande kennis vereist van de grootte of diepte van de optimale boom, waardoor de theoretische garanties direct toepasbaar zijn op real-world scenario's.
• Strakheid: Het aantonen dat de gemengde afhankelijkheid van gemiddelde en maximale diepte strikt strakkere grenzen oplevert voor ongebalanceerde bomen, een veelvoorkomende structuur in beslissingsbomen.

De auteurs erkennen beperkingen, met name dat hun analyse zich richt op niet-gepruneerde bomen (aangezien rigoureuze analyse van pruning schaars is) en dat het huidige bewijs rust op discrete productruimtes. Zij identificeren het uitbreiden van de analyse naar continue kenmerken en splitsingen op basis van drempelwaarden als een toekomstige richting. Zij merken ook op dat, hoewel hun grens quasi-polynomiaal is, super-polynomiale ondergrenzen bestaan voor het leren van beslissingsbomen, wat suggereert dat enige afhankelijkheid van de optimale grootte $s$ onvermijdelijk is.