Technische Samenvatting: Partition Tree: Conditionele Densiteitsschatting over Algemene Uitkomstruimten

Probleemstelling

Beslissingsbomen worden breed gewaardeerd om hun interpreteerbaarheid en efficiëntie bij puntvoorspelling (classificatie en regressie). Het uitbreiden van boomgebaseerde methoden naar conditionele densiteitsschatting over algemene uitkomstruimten (die zowel continue als categorische variabelen gelijktijdig ondersteunen) blijft echter uitdagend. Bestaande benaderingen stuiten op specifieke beperkingen:

• Parametrische Aannames: Methoden zoals CADET maken gebruik van parametrische conditionele dichtheden in de bladknopen, wat mogelijk geen complexe, niet-Gaussische verdelingen kan vastleggen.
• Schaalbaarheid: Methoden zoals CDTree, die splitsen en bladvormige histogrammen gezamenlijk optimaliseren, kunnen rekenkundig veeleisend zijn, waardoor hun toepasbaarheid op grote datasets beperkt wordt.
• Gecombineerde Formulering: Er ontbreekt een verenigd kader dat classificatie en regressie behandelt als specifieke gevallen van conditionele densiteitsschatting, zonder parametrische beperkingen op de doelverdeling op te leggen.

Methodologie

1. Theoretisch Kader: Maattheoretische Formulering

De auteurs stellen Partition Tree voor, een kader dat gebaseerd is op maattheorie.

• Verdeling van de Gezamenlijke Ruimte: In tegenstelling tot traditionele bomen die alleen de covariatenruimte $X$ partitioneren, construeert Partition Tree een data-adaptieve verdeling $\pi_N$ van de gezamenlijke covariaten-uitkomstruimte $Z = X \times Y$.
• Stuksgewijs Constante Schatting: De conditionele dichtheid $f(y|x)$ wordt gemodelleerd als een stuksgewijs constante functie die op deze verdelingen is gedefinieerd.
• Radon-Nikodym-afgeleide: De methode definieert de conditionele dichtheid via de Radon-Nikodym-afgeleide met betrekking tot een productmaat $\nu = P_X \otimes \mu_Y$, waarbij $\mu_Y$ een referentiemaat is (telpmaat voor discrete uitkomsten, Lebesgue voor continue).
• Schatting: Voor een cel $A = A_X \times A_Y$ in de verdeling is de dichtheidsschatting:
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  waarbij $n_{XY}$ en $n_X$ empirische tellingen zijn. Deze formulering behandelt op natuurlijke wijze uitkomsten van gemengd type en laat classificatie en regressie ontstaan als speciale gevallen.

2. Boomconstructie-algoritme

De boom wordt gegroeid met een gierige, best-first-strategie die direct de conditionele negatieve log-waarschijnlijkheid minimaliseert.

• Doel: Het splitsingscriterium maximaliseert de empirische winst in log-verlies:
  $$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$
• Splitsingstypen:
  • Covariaten-splitsingen ($X$): Verfijnen de covariatenruimte (standaard boomsplitsingen).
  • Uitkomst-splitsingen ($Y$): Verfijnen de uitkomstbakken binnen een vaste covariatenregio. Dit stelt de boom in staat om adaptief histogrammen voor de uitkomstverdeling te construeren.
• Efficiëntie: Het algoritme maakt gebruik van efficiënte sorteer- en prefixsom-technieken om kandidaat-splitsingen te evalueren in $O(d_Z N \log N)$ tijd (of $O(d_Z N \log^2 N)$ voor gebalanceerde bomen), wat overeenkomt met de schaalbaarheid van standaard CART.
• Truncatie: Voor onbegrensde continue uitkomsten maakt de methode gebruik van een data-afhankelijke truncatie (min-max doos) om een eindige maat te garanderen, met theoretische garanties dat de truncatie asymptotisch alle waarschijnlijkheidsmassa vastlegt.

3. Partition Forest

Om stabiliteit en voorspellende prestaties te verbeteren, introduceren de auteurs Partition Forest, een ensemble-methode. Deze middelt de conditionele densiteitsschattingen van meerdere Partition Trees die zijn getraind op bootstrap-steekproeven (bagging), optioneel met willekeurige subsampling van kenmerken.

4. Theoretische Garanties

Het artikel stelt voldoende voorwaarden vast voor $L^1(\nu)$-consistentie van de schatter. Consistentie is gegarandeerd als de volgorde van verdelingen voldoet aan:

1. Het aantal cellen groeit sublineair ten opzichte van $N$.
2. De groeifunctie van de verdelingsfamilie voldoet aan specifieke VC-dimensie-begrenzingen.
3. De diameter van de cellen krimpt naar nul.
4. Het aantal onderscheiden covariatenprojecties groeit langzaam genoeg ten opzichte van $\sqrt{\log N / N}$.

Belangrijkste Bijdragen

1. Verenigd Kader: Een enkel, niet-parametrisch kader voor conditionele densiteitsschatting dat omgaat met continue, categorische en uitkomsten van gemengd type zonder parametrische aannames.
2. Directe Optimalisatie: Een boomconstructie-algoritme dat direct conditionele log-waarschijnlijkheid optimaliseert via een gierige best-first-zoekopdracht, waardoor de rekenkundige knelpunten van gezamenlijke split-histogramoptimalisatie uit eerdere werken worden vermeden.
3. Schaalbaarheid: Een implementatie met rekenkundige complexiteit die vergelijkbaar is met standaard CART, waardoor deze levensvatbaar is voor grote datasets.
4. Ensemble-extensie: De introductie van Partition Forest, die verbeterde probabilistische voorspelling ten opzichte van enkele bomen aantoont.
5. Theoretische Analyse: Rigoureuze consistentiebewijzen voor de voorgestelde schatter onder standaard complexiteits- en krimp-aannames.

Experimentele Resultaten

De auteurs hebben Partition Tree en Partition Forest geëvalueerd op een diverse reeks classificatie- en regressie-benchmarks, waarbij ze deze vergeleken met CART, Random Forests, CADET en CDTree.

• Classificatie:
  • Enkele Bomen: Partition Tree presteerde op de meerderheid van de datasets (8 van de 9) beter dan CART wat betreft log-waarschijnlijkheid.
  • Ensembles: Partition Forest behaalde een lagere log-waarschijnlijkheid dan Random Forests op de meeste datasets, wat superieure probabilistische kalibratie aantoont.
• Regressie:
  • Enkele Bomen: Partition Tree leverde concurrerende puntvoorspellingen en sterke probabilistische prestaties. Opmerkelijk is dat het de parametrische CADET op grotere datasets (bijv. Air, Power, California, Protein) overtrof, wat wijst op betere schaalbaarheid en aanpasbaarheid aan steekproefgrootte.
  • Ensembles: Partition Forest presteerde consistent beter dan Random Forests op de meerderheid van de regressie-benchmarks (8 van de 10) wat betreft log-waarschijnlijkheid.
• Robuustheid:
  • Ruis: De methode toonde robuustheid tegen zowel homoscedastische als heteroscedastische ruis, met prestatiedegradeerbaarheid vergelijkbaar met CDTree en betere stabiliteit dan CADET.
  • Redundante Kenmerken: Hoewel CDTree iets betere stabiliteit toonde tegen gecorreleerde kenmerkverdubbeling, leverde Partition Tree consistentere voorspellingen (lagere variantie) onder kenmerkcorruptie op vergeleken met CADET.
• Efficiëntie: Runtijdvergelijkingen op de Physicochemical Protein-dataset toonden aan dat Partition Tree ongeveer 5$\times$ sneller is dan CADET en 25$\times$ sneller dan CDTree bij $N=10.000$.

Betekenis en Beweringen

Het artikel beweert dat Partition Tree een schaalbaar, niet-parametrisch alternatief biedt voor bestaande probabilistische boommethoden. De primaire betekenis ligt in:

• Flexibiliteit: Het vermogen om complexe conditionele verdelingen over algemene uitkomstruimten te modelleren zonder een specifieke parametrische vorm (bijv. Gaussisch) aan te nemen.
• Interpreteerbaarheid: Het behoud van de intrinsieke interpreteerbaarheid van beslissingsbomen (via op winst gebaseerde kenmerkgewichten en visualisatie van stuksgewijs constante dichtheden) terwijl volledige probabilistische outputs worden geboden.
• Prestaties: Empirisch aantonen dat niet-parametrische, op dichtheid gebaseerde boom-ensembles zowel traditionele ensemble-methoden voor puntvoorspelling (Random Forests) als parametrische, op dichtheid gebaseerde bomen (CADET) kunnen overtreffen, met name naarmate de datasetgrootte toeneemt.

De auteurs positioneren Partition Tree als een natuurlijke kandidaat voor integratie in causal inference-pijplijnen en andere toepassingen die flexibele conditionele densiteitsschatting vereisen, terwijl ze erkennen dat toekomstig werk boostingskaders en op maat gemaakte snoeistrategieën kan verkennen.