Riepilogo Tecnico: Partition Tree: Stima della Densità Condizionata su Spazi di Risultato Generali

Enunciato del Problema

Gli alberi decisionali sono ampiamente apprezzati per la loro interpretabilità ed efficienza nella previsione puntuale (classificazione e regressione). Tuttavia, estendere i metodi basati su alberi alla stima della densità condizionata su spazi di risultato generali (supportando simultaneamente variabili continue e categoriali) rimane una sfida. Gli approcci esistenti presentano limitazioni specifiche:

• Assunzioni Parametriche: Metodi come CADET impiegano densità condizionate parametriche ai nodi foglia, che potrebbero non catturare distribuzioni complesse e non gaussiane.
• Scalabilità: Metodi come CDTree, che ottimizzano congiuntamente le suddivisioni e gli istogrammi a livello di foglia, possono essere computazionalmente onerosi, limitando la loro applicabilità a grandi dataset.
• Formulazione Unificata: Manca un quadro unificato che tratti la classificazione e la regressione come casi specifici di stima della densità condizionata senza imporre vincoli parametrici sulla distribuzione target.

Metodologia

1. Quadro Teorico: Formulazione Teorico-Misurabile

Gli autori propongono Partition Tree, un quadro fondato sulla teoria della misura.

• Partizionamento dello Spazio Congiunto: A differenza degli alberi tradizionali che partizionano solo lo spazio delle covariate $X$, Partition Tree costruisce una partizione adattiva ai dati $\pi_N$ dello spazio congiunto covariate-risultato $Z = X \times Y$.
• Stima a Costante a Pezzi: La densità condizionata $f(y|x)$ è modellata come una funzione a costante a pezzi definita su queste partizioni.
• Derivata di Radon–Nikodym: Il metodo definisce la densità condizionata tramite la derivata di Radon–Nikodym rispetto a una misura prodotto $\nu = P_X \otimes \mu_Y$, dove $\mu_Y$ è una misura di riferimento (misura di conteggio per risultati discreti, Lebesgue per continui).
• Stimatore: Per una cella $A = A_X \times A_Y$ nella partizione, la stima della densità è:
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  dove $n_{XY}$ e $n_X$ sono conteggi empirici. Questa formulazione gestisce naturalmente risultati di tipo misto e permette alla classificazione e alla regressione di emergere come casi speciali.

2. Algoritmo di Costruzione dell'Albero

L'albero viene generato utilizzando una strategia greedy, best-first che minimizza direttamente la log-verosimiglianza negativa condizionata.

• Obiettivo: Il criterio di suddivisione massimizza il guadagno empirico nella perdita logaritmica:
  $$\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)$$
• Tipi di Suddivisione:
  • Suddivisioni delle Covariate ($X$): Affinano lo spazio delle covariate (suddivisioni standard degli alberi).
  • Suddivisioni dei Risultati ($Y$): Affinano i bin dei risultati all'interno di una regione di covariate fissa. Ciò permette all'albero di costruire istogrammi adattivi per la distribuzione dei risultati.
• Efficienza: L'algoritmo utilizza tecniche di ordinamento efficiente e somme prefissate per valutare le suddivisioni candidate in $O(d_Z N \log N)$ tempo (o $O(d_Z N \log^2 N)$ per alberi bilanciati), corrispondendo alla scalabilità del CART standard.
• Troncamento: Per risultati continui illimitati, il metodo impiega un troncamento dipendente dai dati (scatola min-max) per garantire una misura finita, con garanzie teoriche che il troncamento catturi asintoticamente tutta la massa di probabilità.

3. Partition Forest

Per migliorare stabilità e prestazioni predittive, gli autori introducono Partition Forest, un metodo di ensemble. Media le stime della densità condizionata da più Partition Tree addestrati su campioni bootstrap (bagging), opzionalmente con sottocampionamento casuale delle caratteristiche.

4. Garanzie Teoriche

Il documento stabilisce condizioni sufficienti per la consistenza $L^1(\nu)$ dello stimatore. La consistenza è garantita se la sequenza di partizioni soddisfa:

1. Il numero di celle cresce in modo sublineare rispetto a $N$.
2. La funzione di crescita della famiglia di partizioni soddisfa specifici limiti di dimensione VC.
3. Il diametro delle celle si riduce a zero.
4. Il numero di proiezioni distinte delle covariate cresce abbastanza lentamente rispetto a $\sqrt{\log N / N}$.

Contributi Chiave

1. Quadro Unificato: Un singolo quadro non parametrico per la stima della densità condizionata che gestisce risultati continui, categoriali e di tipo misto senza assunzioni parametriche.
2. Ottimizzazione Diretta: Un algoritmo di costruzione dell'albero che ottimizza direttamente la perdita logaritmica condizionata tramite una ricerca greedy best-first, evitando i colli di bottiglia computazionali dell'ottimizzazione congiunta suddivisione-istogramma presenti nei lavori precedenti.
3. Scalabilità: Un'implementazione con complessità computazionale comparabile al CART standard, rendendola praticabile per grandi dataset.
4. Estensione Ensemble: L'introduzione di Partition Forest, che dimostra una migliore previsione probabilistica rispetto ai singoli alberi.
5. Analisi Teorica: Dimostrazioni rigorose di consistenza per lo stimatore proposto sotto ipotesi standard di complessità e contrazione.

Risultati Sperimentali

Gli autori hanno valutato Partition Tree e Partition Forest su un insieme diversificato di benchmark di classificazione e regressione, confrontandoli con CART, Random Forest, CADET e CDTree.

• Classificazione:
  • Singoli Alberi: Partition Tree ha superato CART nella maggior parte dei dataset (8 su 9) in termini di log-loss.
  • Ensemble: Partition Forest ha ottenuto una log-loss inferiore rispetto ai Random Forest nella maggior parte dei dataset, dimostrando una calibrazione probabilistica superiore.
• Regressione:
  • Singoli Alberi: Partition Tree ha fornito previsioni puntuali competitive e prestazioni probabilistiche solide. In particolare, ha superato il parametrico CADET su dataset più grandi (ad es. Air, Power, California, Protein), suggerendo una migliore scalabilità e adattabilità alla dimensione del campione.
  • Ensemble: Partition Forest ha costantemente superato i Random Forest nella maggior parte dei benchmark di regressione (8 su 10) per quanto riguarda la log-loss.
• Robustezza:
  • Rumore: Il metodo ha mostrato robustezza sia al rumore omoschedastico che eteroschedastico, con un degrado delle prestazioni comparabile a CDTree e una stabilità migliore rispetto a CADET.
  • Caratteristiche Ridondanti: Mentre CDTree ha mostrato una stabilità leggermente migliore contro la duplicazione di caratteristiche correlate, Partition Tree ha prodotto previsioni più coerenti (varianza inferiore) sotto corruzione delle caratteristiche rispetto a CADET.
• Efficienza: I confronti dei tempi di esecuzione sul dataset Physicochemical Protein hanno mostrato che Partition Tree è circa 5$\times$ più veloce di CADET e 25$\times$ più veloce di CDTree per $N=10,000$.

Significato e Affermazioni

Il documento afferma che Partition Tree offre un'alternativa non parametrica e scalabile ai metodi probabilistici basati su alberi esistenti. Il suo significato principale risiede in:

• Flessibilità: La capacità di modellare distribuzioni condizionate complesse su spazi di risultato generali senza assumere una forma parametrica specifica (ad es. Gaussiana).
• Interpretabilità: Mantenere l'interpretabilità intrinseca degli alberi decisionali (tramite importanza delle caratteristiche basata sul guadagno e visualizzazione della densità a costante a pezzi) fornendo al contempo output probabilistici completi.
• Prestazioni: Dimostrare empiricamente che ensemble di alberi basati su densità non parametriche possono superare sia gli ensemble tradizionali di previsione puntuale (Random Forest) sia gli alberi basati su densità parametriche (CADET), in particolare all'aumentare della dimensione del dataset.

Gli autori posizionano Partition Tree come un candidato naturale per l'integrazione in pipeline di inferenza causale e altre applicazioni che richiedono una stima flessibile della densità condizionata, riconoscendo che lavori futuri potrebbero esplorare framework di boosting e strategie di potatura personalizzate.