Improving Random Forests by Smoothing

Technische Samenvatting: Verbetering van Random Forests door Gladdening

Probleemstelling
Random forest-regressie is een robuuste niet-parametrische methode die zich aanpast aan lokale data-eigenschappen via datagedreven partitionering. Echter, zijn voorspellingen zijn inherent stuksgewijs constant, wat leidt tot discontinuïteiten op de grenzen van de partitionen. Dit gebrek aan gladheid is vooral problematisch in regimes met weinig data, waar het onvermogen om informatie over de invoerruimte te delen kan leiden tot suboptimale prestaties. Hoewel er klassieke gladmakende methoden (bijv. kernel-schatters) en soft-tree-varianten bestaan, worstelen deze vaak met schaalbaarheid in hoge dimensies, verhoogde computationele complexiteit of een verlies van de efficiënte boomgroei-algoritmen die random forests aantrekkelijk maken. De kernuitdaging is om gladheid en differentieerbaarheid in te voeren in random forest-voorspellingen zonder hun ruimtelijke aanpasbaarheid of computationele efficiëntie te offeren.

Methodologie
De auteurs stellen een post-learning, kernel-gebaseerd gladmakend mechanisme voor dat werkt op de output van een getrainde random forest in plaats van het boomconstructieproces zelf te wijzigen.

1. Probabilistische Gladdening: De methode definieert een gegladde voorspelling $\tilde{f}(x_0)$ als de verwachting van de oorspronkelijke stuksgewijs constante voorspellingsfunctie $f(z)$ over een latente variabele $z$ die verdeeld is volgens een probabilistische kernel $k(\cdot | x_0, \lambda)$. Wiskundig: $\tilde{f}(x_0) = \mathbb{E}_{z \sim k}[f(z)]$.
2. Implementatie voor Stuksgewijs Constante Functies: Voor beslissingsbomen en -bossen, waarbij het domein is opgesplitst in as-parallelle hyper-rechthoeken, vereenvoudigt deze verwachting tot een gewogen som van de constante waarden in elk gebied. De gewichten zijn de kansen dat de latente variabele in elk gebied valt, efficiënt berekend met behulp van de cumulatieve verdelingsfuncties (CDF's) van de gekozen kernel.
3. Kernselectie: De auteurs maken gebruik van productkernels, specifiek de Gaussische en de hyperbolische secans (Hypsec) verdelingen. Deze worden gekozen om ervoor te zorgen dat de resulterende voorspellingsfunctie overal differentieerbaar is. De hyperbolische secans staat bekend om zijn exponentiële staartafname, die het asymptotische gedrag nabootst van de Laplace-verdeling die is afgeleid uit de theoretische analyse van variabiliteit in boom-splitpunten.
4. Theoretische Rechtvaardiging: Het artikel toont aan dat dit gladmakende procedé kan worden geïnterpreteerd als het vastleggen van de variabiliteit of onzekerheid in boom-snijpunten onder resampling van de trainingsinvoer. Specifiek volgt de limietverdeling van een schatting van het breekpunt van een boom onder resampling een Laplace-verdeling; de voorgestelde gladdening bootst dit na door de voorspelling te convolueren met een kernel die deze variabiliteit benadert.
5. Toepassing op Ensembles: Omdat random forests additieve ensembles zijn, kan de gladmakende operator (die lineair is) worden toegepast op individuele bomen en vervolgens worden gemiddeld, waardoor de computationele onuitvoerbaarheid van het gladmaken van de exponentieel complexe regiostructuur van het volledige ensemble wordt vermeden.
6. Modelselectie: De gladmakende parameters (schaal $\lambda$) en affiene herkalibratieparameters ($\beta_0, \beta_1$) worden geselecteerd door de Out-of-Bag (OOB) fout te minimaliseren. De auteurs maken gebruik van gradient-based optimalisatie (bijv. L-BFGS, AdamW) om om te gaan met de niet-convexe aard van het OOB-foutlandschap.

Belangrijkste Bijdragen

• Post-Learning Gladdening Framework: Introduceert een algemene, probabilistische aanpak om elke geleerde stuksgewijs constante functie uit te rusten met willekeurige gladheid, terwijl de ruimtelijke aanpasbaarheid van het oorspronkelijke model behouden blijft.
• Theoretische Interpretatie: Biedt een theoretisch verband tussen kernel-gladdening en de onzekerheid van boom-splitpunten onder data-resampling, wat het gebruik van specifieke kernel-vormen rechtvaardigt.
• Efficiënte Implementatie: Toont aan dat gladdening efficiënt kan worden toegepast op random forests door gebruik te maken van de lineariteit van het ensemble, waardoor de complexiteit wordt gereduceerd van exponentieel (in termen van regio's) naar lineair (in termen van individuele boomregio's).
• Empirische Validatie: Laat zien dat een gegladde random forest met een klein aantal bomen (bijv. 10) standaard random forests met aanzienlijk grotere ensembles (tot 100 bomen) en Gaussian Process-regressie kan overtreffen op diverse datasets.

Experimentele Resultaten
De aanpak werd geëvalueerd op 10 UCI-datasets met trainingsgroottes variërend van 50 tot 500 observaties.

• Prestaties: De voorgestelde "Ensemble of Smoothed Trees with Per-Dimension parameters" (EST-PD) met gebruik van Gaussische of hyperbolische secans-kernels presteerde consistent beter dan de baseline random forest (10 bomen) in 93–94% van de gevallen.
• Vergelijking met Baselines: EST-PD-varianten presteerden beter dan standaard random forests met 20, 50 en 100 bomen in respectievelijk 81%, 69% en 64% van de gevallen. Ze presteerden ook aanzienlijk beter dan Gaussian Process-regressie (winnen in 88% van de gevallen).
• Statistische Significantie: Niet-parametrische statistische tests (Friedman en Nemenyi) bevestigden dat de gegladde varianten een statistisch superieure equivalentiegroep vormen in vergelijking met standaard random forests en Gaussian processes.
• Regime met weinig data: De methode toonde bijzondere sterkte in datagebrekkige settings (bijv. $n=50$), waar het significante procentuele verbeteringen in de Mean Squared Error (MSE) behaalde ten opzichte van standaard baselines.
• Kernkeuze: De Gaussische en hyperbolische secans-kernels leverden opmerkelijk vergelijkbare prestatieprofielen op, wat suggereert dat de keuze van de kernel een minimaal praktisch effect heeft op de effectiviteit.

Betekenis en Claims
Het artikel beweert dat post-hoc gladdening een computationeel hanteerbare manier biedt om de voorspellende nauwkeurigheid van random forests te verbeteren, vooral wanneer data beperkt is. Door de aanpasbaarheid van boom-gebaseerde methoden te combineren met de gladheidsaannames van kernel-methoden, adresseert de aanpak het discontinuïteitsprobleem dat inherent is aan standaard bossen zonder de complexe aanpassingsprocedures van soft-trees te vereisen. De auteurs merken op dat hoewel het framework zich richt op regressie (schatting van de conditionele gemiddelde), het concept zich potentieel kan uitbreiden naar onzekerheidskwantificatie (conditionele variantie) en classificatietaken, hoewel deze onderwerpen voor toekomstig onderzoek blijven. Het werk benadrukt ook dat hoewel de methode theoretisch uitbreidbaar is naar gradient boosting, de sequentiële aard van het boosten van bomen uitdagingen presenteert voor de hier gebruikte globale kalibratie-aanpak.