Technische Samenvatting: Clustered Random Forests met Gecorreleerde Data

Probleemstelling

Real-world datasets vertonen vaak geclusterde structuren die voortkomen uit herhaalde metingen, longitudinale studies of geografische groeperingen. In dergelijke settings zijn observaties binnen een cluster vaak gecorreleerd, wat de aanname van onafhankelijke en identiek verdeelde (i.i.d.) waarnemingen schendt die standaard is voor veel machine learning-algoritmen. Hoewel parametrische mixed-effects modellen deze correlaties kunnen verklaren, vertrouwen zij op specifieke parametrische aannames met betrekking tot de gemiddelde en covariantiestructuren; misspecificatie van deze structuren kan leiden tot aanzienlijke bias en inconsistente schattingen.

Bestaande non-parametrische benaderingen, zoals Random Forests (RF), negeren intra-clustercorrelaties doorgaans of proberen deze te modelleren via rigide parametrische covariantiestructuren (bijv. REEM-trees, Mixed Effects Random Forests). Deze bestaande methoden lijden vaak aan computationele onhandelbaarheid (kubische complexiteit) of falen in het garanderen van variantiereductie ten opzien van standaard RF's. Bovendien bestaat er een kritieke kloof in het begrip van hoe optimale schatting en inferentie zich gedragen onder covariaat-distributieverschuiving (covariate distribution shift) wanneer data gecorreleerd zijn. Standaard methoden die geoptimaliseerd zijn voor de trainingsdistributie kunnen willekeurig slecht presteren wanneer de testdistributie verschuift, een fenomeen dat minder bestudeerd is in settings met gecorreleerde data vergeleken met onafhankelijke data.

Methodologie: Clustered Random Forests (CRF)

De auteurs stellen Clustered Random Forests (CRF) voor, een non-parametrische uitbreiding van het Random Forest-algoritme die specifiek is ontworpen voor geclusterde data. De kerninnovatie ligt in het modificeren van het blad-gebaseerde voorspellingsmechanisme van de constituerende beslissingsbomen.

Algoritmisch Kader

1. Clustered Decision Trees (CDT): In plaats van Ordinary Least Squares (OLS) te gebruiken om het gemiddelde binnen een blad te schatten (zoals in standaard RF's), maken CRFs gebruik van Weighted Least Squares (WLS).
   • De voorspelling in een blad is een gewogen gemiddelde van observaties, waarbij de gewichten worden afgeleid van een cluster-gewichtsmatrix $W_i(\rho)$.
   • Deze gewichten zijn ontworpen om intra-clustercorrelaties te verklaren. De auteurs richten zich op parametrische klassen van gewichten, specifiek equicorrelatie (exchangeable) en AR(1) structuren, die een computationeel efficiënte fitting mogelijk maken.
2. Gewichtsschatting:
   • In tegen tegenstelling tot likelihood-gebaseerde methoden (bijv. REEM, MERF) die covariantieparameters schatten via maximum likelihood op residuen, schat CRF de gewichtsparameter $\rho$ door de Mean Squared Prediction Error (MSPE) te minimaliseren onder een specifieke doel-covariaatdistributie $Q$.
   • Dit stelt het algoritme in staat om zich aan te passen aan covariaatverschuiving. De optimale gewichtsparameter $\rho^*$ is een functie van de doeldistributie $Q$.
   • De schatting maakt gebruik van een "covariance model-free" ethos, waarbij $\rho$ wordt geschat door het minimaliseren van een empirische estimator van de geïntegreerde variantie over de doeldistributie $Q$, in plaats van een specifieke generatieve foutenmodellen aan te nemen.
3. Honesty en Subsampling:
   • Het algoritme dwingt de honesty eigenschap af (Wager en Athey, 2018): de data die worden gebruikt voor het bepalen van splitsingen, het schatten van gewichten en het doen van voorspellingen zijn strikt gescheiden.
   • Het maakt gebruik van een "bootstrap of little bags" subsampling-strategie om het bos te construeren en variantie te schatten, wat de constructie van geldige betrouwbaarheidsintervallen mogelijk maakt.

Computationele Efficiëntie

Een aanzienlijke technische prestatie is de ontwikkeling van algoritmen die CRFs in ongeveer lineaire tijd laten fitten ten opzichte van het aantal observaties. Door gebruik te maken van de structuur van equicorrelante en AR(1) gewichtsmatrices, maken de auteurs gebruik van conjugate gradient descent om de WLS-problemen op te lossen, waardoor de kubische $O(M^3)$ complexiteit die gepaard gaat met het inverteren van dichte matrices in bestaande mixed-effects forest methoden wordt vermeden.

Belangrijke Theoretische Bijdragen

1. Asymptotische Snelheden en Minimax Optimaliteit

De auteurs leiden asymptotische bovengrenzen af voor de algemene $Q$-covariaatverschoven MSPE. Zij demonstreren dat er splitsingsregels en subsampling-regimes bestaan binnen het CRF-kader die minimax optimale snelheden bereiken voor pointwise schatting van Lipschitz-gemiddelde functies. Deze snelheden komen overeen met die van standaard random forests voor i.i.d. data, ondanks de toegevoegde complexiteit van correlatie.

2. Covariaatverschuiving en Optimale Gewichten

Een centrale theoretische bevinding is dat de optimale gewichtsparameter $\rho$ voor gecorreleerde data niet invariant is aan covariaatverschuivingen.

• Theorem 2 stelt vast dat de optimale gewichten voor een doeldistributie $Q$ willekeurig kunnen verschillen van de gewichten die optimaal zijn voor de trainingsdistributie.
• Bijgevolg kunnen methoden die gewichten schatten op basis van enkel de trainingsdistributie (bijv. via kruisvalidatie of likelihood-maximalisatie op trainingsresiduen) willekeurig suboptimaal zijn onder covariaatverschuiving, en zelfs slechter presteren dan zelfs standaard ongegewogen Random Forests.
• Dit contrasteert met onafhankelijke data-settings waar herwegting-schema's (zoals importance weighting) goed begrepen zijn; in gecorreleerde settings is de optimale herwegtingsstrategie intrinsiek verbonden met de doeldistributie $Q$.

3. Inferentie en Asymptotische Normaliteit

Het artikel bewijst dat variantie-dominante CRFs asymptotisch Gaussisch zijn (pointwise en uniform over een klasse van distributies). Dit resultaat houdt stand onder specifieke subsampling-snelheden die ervoor zorgen dat variantie dominant is over bias. Deze theoretische garantie maakt de constructie van asymptotisch geldige betrouwbaarheidsintervallen mogelijk voor de conditionele gemiddelde functie, met breedtes die sneller convergeren dan standaard RF's dankzij de variantiereductie die wordt bereikt door correlaties te verklaren.

Empirische Resultaten

De auteurs valideren hun theoretische bevindingen via simulaties en een real-world toepassing:

1. Covariaatverschuiving Simulatie: In een setting met equicorrelante data presteerden CRFs die geoptimaliseerd zijn voor een verschoven testdistributie ($Q = \text{Unif}[1, 2]$) significant beter dan standaard RF's, trainingsfout-geoptimaliseerde forests (TRAIN), en likelihood-gebaseerde forests (REEM). Opvallend genoeg presteerden TRAIN en REEM forests zelfs slechter dan standaard RF's onder de verschuiving, wat de theoretische risico's bevestigt van het negeren van distributieverschuivingen bij gewichtsschatting.
2. Inferentie Simulatie: In settings met AR(2) gecorreleerde fouten bereikten CRFs smallere betrouwbaarheidsintervallen (gereduceerde breedte) terwijl ze een nominale dekking (95%) behielden vergeleken met standaard RF's. Dit resulteerde in een lagere mean squared error voor de punt-schattingen.
3. Real-World Applicatie (HIV CD4 Counts): Bij het analyseren van CD4-celgetallen van HIV-seroconverters boden CRFs gepersonaliseerde voorspellingen met een reductie van 20–40% in de geschatte variantie vergeleken met standaard RF's, wat de praktische bruikbaarheid in medische voorspellings-taken met herhaalde metingen aantoont.

Betekenis en Claims

Het artikel claimt een praktische en theoretisch gefundeerde uitbreiding te bieden van Random Forests naar geclusterde data die:

• Correlatie Benut: De voorspellingsnauwkeurigheid en de precisie van inferentie verbetert door expliciet intra-cluster afhankelijkheid te modelleren zonder te vertrouven op rigide parametrische gemiddelde modellen.
• Covariaatverschuiving Aanpakt: Identificeert en lost een kritiek gebrek in bestaande gecorreleerde-data methoden op: het falen om gewichten aan te passen aan de doel-covariaatdistributie. De auteurs stellen dat optimale non-parametrische schatting onder covariaatverschuiving voor gecorreleerde data een door de gebruiker gespecificeerde doeldistributie vereist om de gewichten te bepalen.
• Schaalbaarheid Garandeert: Overkomt de computationele barrières van eerdere mixed-effects forest methoden door een oplossing te bieden met een lineaire tijdscomplexiteit die vergelijkbaar is met standaard Random Forests.
• Geldige Inferentie Mogelijk Maakt: Biedt de eerste asymptotische theorie voor variantie-dominante geclusterde forests die de constructie van nauwe, geldige betrouwbaarheidsintervallen ondersteunt.

De auteurs positioneren hun werk als een brug tussen de flexibiliteit van non-parametrische machine learning en de rigoureuze behandeling van afhankelijkheidsstructuren, en bieden een nieuw perspectief op het probleem van covariaatverschuiving in de context van gecorreleerde data.