Questo articolo descriveun metodo di machine learning statistico noto come Decision Tree. Gli alberi decisionali (DT) sono una tecnica di apprendimento supervisionato che stima/predice i valori delle risposte tramite l’apprendimento di regole decisionali derivate dalle feature. Possono essere utilizzati sia in un contesto di regressione che di classificazione. Per questo motivo sono talvolta indicati anche come Classification And Regression Trees (CART).
I modelli DT/CART sono un esempio di una più generale area del machine learning nota come adaptive basis function models. Questi modelli apprendono le feature direttamente dai dati, anziché essere prespecificate, come in altrei approcci. Tuttavia, a differenza della regressione lineare, questi modelli non sono lineari nei parametri e quindi possiamo solamente calcolare una stima di massima verosimiglianza (MLE) localmente ottimale per i parametri [1] .
I modelli DT/CART funzionano suddividendo lo spazio delle caratteristiche in una serie di semplici regioni rettangolari, suddivise per assi paralleli . Per ottenere una previsione per una particolare osservazione, viene utilizzata la media o la modalità delle risposte delle osservazioni di addestramento , all’interno della partizione a cui appartiene la nuova osservazione.
L’utilizzo di un DT/CART ha il vantaggio principale di produrre, per costruzione, un set di regole decisionali interpretabili if-then-else, che sono simili ai diagrammi di flusso grafici. Mentre ha il principale svantaggio di non avere la stessa precisione di essere competitivo rispetto alle altre tecniche supervisionate come le support vector machines o deep neural networks in termini di precisione di previsione.
Tuttavia i DT/CART possono diventare estremamente competitivi se utilizzati in un metodo ensemble come con l’aggregazione bootstrap (“bagging” ), le random forest o il boosting.
Nella finanza quantitativa gli insiemi di modelli DT/CART vengono utilizzati nella previsione, sia per prezzi/direzioni futuri degli asset sia per la liquidità di determinati strumenti. Negli articoli futuri descriviamo strategie di trading basate su questi metodi.
Panoramica matematica
Considerando una specifica funzione di base adattiva probabilistica, il modello \(f({\bf x})\) è data da [1] :
\(\begin{eqnarray}f({\bf x}) = \mathbb{E}(y \mid {\bf x}) = \sum^{M}_{m=1} w_m \phi({\bf x}; {\bf v}_m)\end{eqnarray}\)
Dove \(w_m\) è la risposta media in una particolare regione, \(R_m\), e \({\bf v}_m\) descrive come ciascuna variabile viene divisa in corrispondenza di un determinato valore di soglia. Queste divisioni definiscono comei lo spazio delle feature \(R^p\) viene mappato in \(M\) diverse regioni di “iperblocco”.
Decision tree per la regressione
Consideriamo un esempio astratto del problema di regressione con due variabili caratteristiche (\(X_1\), \(X_2\)) e una risposta numerica \(y\). In questo modo possiamo facilmente visualizzare la natura del partizionamento effettuato dall’albero.
Nella seguente figura possiamo vedere un albero pre-addestrato per questo specifico esempio:
In che modo questo corrisponde a una partizione dello spazio delle feature? La figura seguente mostra un sottoinsieme di \(\mathbb{R}^2\) che contiene i dati del nostro esempio. Notiamo come il dominio viene partizionato utilizzando le divisioni parallele all’asse. Ovvero, ogni divisione del dominio è allineata con uno degli assi delle feature:
Il concetto di divisione in assi paralleli si generalizza direttamente per dimensioni maggiori di due. Per uno spazio di feature di dimensioni p, un sottoinsieme di \(\mathbb{R}^p\), lo spazio è suddiviso in M regioni, \(R_m\), ognuno dei quali è un iperblocco a p-dimensioni.
Dobbiamo ancora descrivere come tale albero venga “cresciuto” o “addestrato”. Il seguente paragrafo descrive l’algoritmo per eseguire questa operazione.
Creare un albero di regressione e fare previsioni
L’euristica di base per la creazione di un DT è la seguente:
- Date p feature, partizionare lo spazio delle feature a p-dimensioni (un sottoinsieme di \(\mathbb{R}^p\)) in M regioni reciprocamente distinte che coprono completamente il sottoinsieme dello spazio delle caratteristiche e non si sovrappongono. Queste regioni sono date da \(R_1,…,R_M\).
- Qualsiasi nuova osservazione che cade in una specifica partizione \(R_m\) ha una risposta stimata data dalla media di tutte le osservazioni di addestramento con la partizione, indicata con \(w_m\).
Tuttavia, questo processo in realtà non descrive come formare la partizione in modo algoritmico! Per questo abbiamo bisogno di usare una tecnica nota come Recursive Binary Splitting (RBS)[2].
Divisione binaria ricorsiva (Recursive Binary Splitting)
L’obiettivo di questo algoritmo è ridurre al minimo una qualche forma di criterio di errore. In questo caso particolare, desideriamo ridurre al minimo la somma residua dei quadrati (RSS), una misura di errore utilizzata anche nelle configurazioni di regressione lineare. L’RSS, nel caso di uno spazio di feature diviso in M partizioni è data da:
\(\begin{eqnarray}\text{RSS} = \sum^{M}_{m=1} \sum_{i \in R_m} ( y_i – \hat{y}_{R_m} )^2\end{eqnarray}\)
Per prima cosa sommiamo su tutte le partizioni dello spazio delle caratteristiche (la prima sommatoria) e quindi sommiamo su tutte le osservazioni di test (indicizzate da i) in una partizione particolare (la seconda sommatoria). Prendiamo quindi il quadrato della differenza tra la risposta \(y_i\) di una particolare osservazione e la risposta media \(\hat{y}_{R_m}\) delle osservazioni di addestramento all’interno della partizione.
Sfortunatamente considerare tutte le possibili partizioni dello spazio delle feature in M rettangoli è troppo costoso dal punto di vista computazionale (dato che è un problema NP-completo). E’ necessario quindi prevedere un approccio di ricerca meno oneroso dal punto di vista computazionale, ma più sofisticato. Il Recursive Binary Splitting (RBS) è utile a questo scopo.
Il RBS affronta il problema partendo dalla cima dell’albero e dividendolo in due rami, creando così una partizione in due spazi. Esegue più volte questa specifica suddivisione nella parte superiore dell’albero e sceglie la suddivisione delle feature che riduce al minimo l’RSS (attuale).
A questo punto l’albero crea un nuovo ramo in una determinata partizione ed esegue la stessa procedura, ovvero valuta l’RSS ad ogni split della partizione e sceglie la migliore.
Questo lo rende un algoritmo avido, nel senso che esegue la valutazione per ogni iterazione del ciclo, piuttosto che “guardare avanti” e continuare a ramificarsi prima di effettuare le valutazioni. È questa natura “avida” dell’algoritmo che lo rende computazionalmente fattibile e quindi nell’uso pratico [1], [2] .
In questa fase non abbiamo descritto quando effettivamente termina questa procedura. Ci sono alcuni criteri che possiamo prendere in considerazione, tra cui porre un limite alla profondità massima dell’albero, garantire esempi di addestramento sufficienti in ciascuna regione e/o garantire che le regioni siano sufficientemente omogenee in modo tale che l’albero sia relativamente “equilibrato”.
Tuttavia, come con tutti i metodi di machine learning supervisionato, dobbiamo essere costantemente consapevoli dell’overfitting. Questo motiva il concetto di “potatura” (pruning) dell’albero.
Potare l’albero
A causa del sempre presente rischio di overfitting e del compromesso bias-varianza, abbiamo bisogno di uno strumento per regolare il processo di divisione dell’albero in modo che possa generalizzare gli insiemi di test nel migliore dei modi.
Dato che è troppo costoso utilizzare la convalida incrociata direttamente su ogni possibile combinazione di sottoalbero durante la crescita (addestramento) dell’albero, dobbiamo prevedere un approccio alternativo che fornisca comunque un buon tasso di errore di test.
L’approccio classico consiste nel far crescere l’albero intero a una profondità prestabilita e quindi eseguire una procedura nota come “potatura”. Un approccio è chiamato cost-complexity pruning ed è descritto dettagliatamente in [2] e [3] . Si basa sull’introduzione di un ulteriore parametro di ottimizzazione, indicato con \(\alpha\), che bilancia la profondità dell’albero e la bontà di adattamento ai dati di allenamento. L’approccio utilizzato è simile alla tecnica LASSO sviluppata da Tibshirani.
Non descriviamo i dettagli della potatura degli alberi dato che usiamo la libreria Scikit-Learn per implementare questo approccio.
Alberi decisionali per la classificazione
Finora abbiamo descritto i Decision Tree applicati alla regressione, ma gli alberi decisionali funzionano ugualmente bene per la classificazione, da qui la “C” nei modelli CART!
L’unica differenza, come per tutti i regimi di classificazione, è la previsione di un valore categorico per la variabile di risposta, invece che un valore continuo. Per effettuare una previsione di una classe di categoria dobbiamo utilizzare la moda della regione di addestramento a cui appartiene un’osservazione, invece che la media. In altre parole, prendiamo il valore di classe più comune e lo assegniamo come risposta dell’osservazione.
Inoltre, dobbiamo considerare criteri alternativi per dividere gli alberi poiché il solito punteggio RSS non è applicabile nell’approccio categoriale. Prendiamo in considerazione re criteri alternativi, la “hit rate”, il Gini Index e il Cross-Entropy [1] , [2] , [3] .
Classificazione Error Rate/Hit Rate
Invece che verificare quanto una risposta numerica è lontana dal valore medio, come nella regressione, possiamo definire la “frequenza di successo” (hit rate) come la frazione di osservazioni di addestramento in una particolare regione che non appartengono alle classi più diffuse. Cioè, l’errore è dato da [1], [2]:
\(\begin{eqnarray}E = 1 – \text{argmax}_{c} (\hat{\pi}_{mc})\end{eqnarray}\)
Dove \(\hat{\pi}_{mc}\) rappresenta la frazione di dati di addestramento nella regione \(R_m\) che appartengono alla classe c.
Indice di Gini
Il Gini Index è una metrica di errore alternativa, progettata per mostrare quanto sia “pura” una regione. La “Purezza” in questo caso indica la quantità di dati di addestramento in una determinata regione che appartiene a una singola classe. Se una regione \(R_m\) contiene dati che provengono principalmente da una singola classe c allora il valore dell’indice Gini sarà piccolo:
\(\begin{eqnarray}G = \sum_{c=1}^C \hat{\pi}_{mc} (1 – \hat{\pi}_{mc})\end{eqnarray}\)
Entropia incrociata (o devianza)
Una terza alternativa, simile all’indice di Gini, è nota come Cross-Entropy o Deviance :
\(\begin{eqnarray}D = – \sum_{c=1}^C \hat{\pi}_{mc} \text{log} \hat{\pi}_{mc}\end{eqnarray}\)
Ciò motiva la domanda su quale metrica di errore utilizzare durante l’addestramento di un albero di classificazione. Al fine di massimizzare l’accuratezza della previsione, possiamo dire che l’Indice di Gini e la Devianza sono usati più spesso dell’Hit Rate. Non approfondiamo le motivazioni di questa scelta, ma una buona discussione può essere trovata nei libri forniti nel seguente paragrafo “Riferimenti”.
Nei prossimi articoli usiamo la libreria Scikit-Learn per eseguire attività di classificazione e valutare le misure di errore al fine di determinare l’efficacia delle nostre previsioni su dati invisibili.
Vantaggi e svantaggi degli alberi decisionali
Come tutti i metodi di machine learning, i modelli DT/CART presenta vantaggi e svantaggi rispetto ad altri modelli:Vantaggi
- I modelli DT/CART sono facili da interpretare, come regole “if-else”.
- I modelli possono gestire feature categoriali e continue nello stesso set di dati
- Il metodo di costruzione per i modelli DT/CART prevede che le variabili delle feature vengono selezionate automaticamente, invece di dover utilizzare la selezione di sottoinsiemi o simili
- I modelli sono in grado di scalare efficacemente su grandi set di dati
Svantaggi
- Prestazioni di previsione relative scarse rispetto ad altri modelli ML
- I modelli DT/CART soffrono di instabilità, cioè sono molto sensibili ai piccoli cambiamenti nello spazio delle feature. Nel linguaggio del compromesso bias-varianza, sono stimatori di varianza elevata.
Nota bibliografica
Una facile introduzione ai metodi basati sui Decision Tree può essere trovata in James et al (2013) [2], che copre le basi di entrambi i DT e degli associati metodi di ensemble. Un resoconto più rigoroso, presentato a livello di matematica/statistica in ritardo di laurea/laurea in matematica, può essere trovato in Hastie et al (2009) [3] . Murphy (2012) [1] descrive i modelli di funzione di base adattiva, di cui i modelli DT/CART sono un sottoinsieme. Il libro copre sia l’approccio frequentista che bayesiano a questi modelli. Per il professionista che lavora su dati del “mondo reale” (come i quants), Kuhn et al (2013) [4] è un testo molto interessante e ad un livello più semplice.
Riferimenti
- [1] Murphy, K.P. (2012) Machine Learning A Probabilistic Perspective, MIT Press
- [2] James, G., Witten, D., Hastie, T., Tibshirani, R. (2013) An Introduction to Statistical Learning, Springer
- [3] Hastie, T., Tibshirani, R., Friedman, J. (2009) The Elements of Statistical Learning, Springer
- [4] Kuhn, M., Johnson, K. (2013) Applied Predictive Modeling, Springer
