TUTORIAL DATA SCIENCE

Combinazioni di Decision Tree con bagging, random forest e alberi potenziati

Scritto da
Gianluca

TUTORIAL

In un precedente articolo è stato introdotto l’albero decisionale (DT) come metodo di apprendimento supervisionato. Nell’articolo abbiamo definito che la vera potenzialità dei Decision Tree è la loro capacità di funzionare estremamente bene come predittori quando usati in un insieme statistico (statistical ensemble).

In questo articolo descriviamo come la combinazione di più DT in un insieme statistico migliora notevolmente le prestazioni predittive sul modello combinato. Queste tecniche non si limitano ai DT, ma possono efficacemente applicate a molti modelli di machine learning, sia di regressione che di classificazione. Tuttavia, i DT forniscono una configurazione “naturale” per descrivere i metodi d’insieme e sono spesso comunemente associati tra loro.

Dopo aver descritto la teoria di questi metodi d’insieme, vediamo come implementarli in Python usando la libreria Scikit-Learn applicata ai dati finanziari. Negli articoli successivi descriviamo come applicare tali metodi d’insieme all’interno di reali strategie di trading, utilizzando il framework DataTrader.

Se non si ha familiarità con gli alberi decisionali, è opportuno leggere l’articolo introduttivo prima di approfondire i metodi dell’insieme.

Prima di approfondire le tecniche dell’insieme di bootstrap aggegration (bagging), random forest e boosting è necessario introdurre una tecnica della statistica frequentista nota come bootstrap, che consente a queste tecniche di funzionare.

Il Bootstrap

Il Bootstrapping [1] è una tecnica di ricampionamento statistico che prevede il campionamento casuale di un set di dati tramite sostituzione. Viene spesso utilizzato come strumento per quantificare l’incertezza associata a un modello di machine learning.

Nella finanza quantitativa il bootstrapping è estremamente utile perchè consente di generare nuovi campioni da una popolazione senza dover andare a raccogliere ulteriori “dati di addestramento”. Nelle applicazioni di finanza quantitativa è spesso impossibile generare più dati a partire dai prezzi di asset finanziari dato che esiste solo una “storia” da cui campionare.

L’obiettivo è produrre molti set di training separati tramite il campionamento ripetuto dei dati con la sostituzione del training set originale. Questi sono quindi utilizzati per consentire ai metodi “meta-learner” o “ensemble” di ridurre la varianza delle loro previsioni, migliorando notevolmente le loro prestazioni predittive.

Due delle seguenti tecniche d’insieme, il bagging e le foreste casuali, fanno un uso massiccio di tecniche di bootstrapping.

Aggregazione bootstrap (Bagging)

Come descritto nell’articolo sulla teoria degli Decition Tree, uno dei principali svantaggi dei DT è l’elevata varianza delle stime effettuate (high-variance estimator). Ne consegue che l’aggiunta di un piccolo numero di osservazioni di addestramento extra può alterare drasticamente le prestazioni di previsione di un decision tree, nonostante i dati di addestramento non subiscono variazioni significative.

Al contrario un low-variance estimator, come la regressione lineare, non è estremamente sensibile all’aggiunta di punti extra, almeno quelli che sono relativamente vicini ai punti rimanenti.

Un modo per mitigare questo problema consiste nell’utilizzare un concetto noto come aggregazione bootstrap o bagging. L’idea è di combinare più modelli di learning (come i DT), ognuno addestrato su diversi campioni di bootstrap e calcolare la media delle loro previsioni al fine di ridurre la varianza complessiva di queste previsioni.

Come sottolineato da James et al (2013) [2], date N osservazioni indipendenti e identicamente distribuite (iid) \(Z_1, \ldots, Z_N\), ciascuno con una varianza di \(\sigma^2\) allora la varianza della media delle osservazioni, \(\bar{Z}\) è data da \(\sigma^2 / N\), cioè, se si prende la media di queste osservazioni, la varianza viene ridotta di un fattore uguale al numero di osservazioni. Questo dimostra che l’approccio di bagging è corretto.

Tuttavia, nella finanza quantitativa si ha quasi sempre ha disposizione un solo set di dati di “training”, quindi è difficile, se non impossibile, creare più set di training indipendenti e separati. In questi casi è necessario applicare il bootstrap in modo da generare molti diversi set di training, a partire da un set più grande.

Dal lavoro di James et al (2013) [2] e dall’articolo Random Forest su Wikipedia [3], se creiamo \(B\) campioni bootstrap separati del set di addestramento, con diversi stimatori di modelli \(\hat{f}^b ({\bf x})\), allora la media dei campioni forma una modello di stima a bassa varianza, \(\hat{f}_{\text{avg}}\):

\(\begin{eqnarray}\hat{f}_{\text{avg}} ({\bf x}) = \frac{1}{B} \sum^{B}_{b=1} \hat{f}^b ({\bf x})\end{eqnarray}\)

Questa procedura è nota come bagging [4]. È applicabile ai DT perché quest’ultimi sono ‘high-variance estimators’ e quindi il bagging è uno strumento per ridurre sensibilmente la varianza.

L’esecuzione del bagging per i DT è semplice. Centinaia o migliaia di alberi molto profondi (non potati) vengono creati attraverso \(B\) campioni bootstrap dei dati di addestramento. Sono combinati con le modalità descritte in precedenza e riducono significativamente la varianza complessiva.

Il bagging ha il principale vantaggio di non poter sovradimensionare il modello solamente aumentando il numero di campioni bootstrap \(B\). Questo è valido anche per le Random Forest, ma non per gli alberi potenziati.

Sfortunatamente questo guadagno nell’accuratezza della previsione produce una significativa riduzione dell’interpretabilità del modello. Tuttavia, nella ricerca quantitativa, l’interpretabilità è spesso meno importante rispetto all’accuratezza della previsione grezza. Quindi questo non è uno svantaggio troppo significativo per le applicazioni di trading algoritmico.

Da notare che esistono metodi statistici specifici per dedurre variabili importanti nel bagging, ma esulano dallo scopo di questo articolo.

Random Forest

Le foreste casuali [5] sono molto simili alla procedura di bagging ad eccezione dell’uso di una tecnica chiamata feature bagging, che ha il vantaggio di diminuire significativamente la correlazione tra ogni DT e quindi aumentare, in media, la sua accuratezza predittiva.

Il bagging delle feature consiste nel selezionare casualmente un sottoinsieme delle feature a p-dimensioni delle caratteristiche, per ogni divisione nella crescita dei singoli DT. Questo può sembrare controintuitivo, dopotutto si desidera inizialmente includere il maggior numero possibile di feature per ottenere quante più informazioni possibili per il modello. Tuttavia ha lo scopo di evitare deliberatamente (in media) feature predittive molto forti che causano divisioni molto simili negli alberi (e quindi aumentano la correlazione).

Cioè, se una particolare feature è efficace nel prevedere il valore della risposta, verrà selezionata per molti alberi. In questo caso una procedura di bagging standard può essere abbastanza correlata. Le foreste casuali evitano questo scenario, scartando deliberatamente queste forti feature nell’addestramento di molti alberi.

Se tutti i valori p sono scelti nella divisione degli alberi in un insieme di foreste casuali, questo corrisponde semplicemente all’insieme (ensemble) standard. Una regola pratica per le foreste casuali è usare \(\sqrt{p}\) feature, opportunamente arrotondate, ad ogni divisione.

Di seguito descriviamo il codice Python per verificare come confrontare le prestazioni delle foreste casuali e del bagging, all’aumentare del numero di DT utilizzati come stimatori di base.

Boosting

Un altro metodo d’insieme molto usato nel machine learning è noto come potenziamento degli alberi. Il boosting differisce dal bagging perchè non implica il campionamento bootstrap. Nel boosting i modelli vengono generati in modo sequenziale e iterativo, cioè è necessario disporre di informazioni sul modello \(i\) prima dell’esecuzione dell’iterazione \(i+1\).

Il potenziamento è stato introdotto da Kearns e Valiant (1989) [6], come risposta alla possibilità di combinare, in qualche modo, una selezione di modelli di machine learning deboli per produrre un unico più forte modello di machine learning. Debole, in questo caso, significa un modello che è solo leggermente migliore della probabilità casuale di prevedere una risposta. Di conseguenza, un modello forte è invece ben correlato alla vera risposta.

Questo ha motivato il concetto di potenziamento. L’idea è di addestrare in modo iterativo modelli deboli di machine learning su un set di dati continuamente aggiornato e quindi unire insieme i modelli deboli per produrre un modello finale e forte. Questo è diverso dal bagging, che semplicemente calcola la media dei modelli su campioni bootstrap separati.

L’algoritmo di base per il potenziamento, descritto a lungo in James et al (2013) [2] e Hastie et al (2009) [7] , è riportato di seguito:

Impostare l’estimatore iniziale a zero, cioè \(\hat{f}({\bf x}) = 0\). Impostare inoltre i residui sulle risposte correnti, \(r_i = y_i\), per tutti gli elementi del training set.
Impostare il numero di alberi potenziati, \(B\) ed effettuare il seguente ciclo per \(b=1,\ldots,B\):
- Addestrare un albero \(\hat{f}^b\) con k divisioni dei dati di allenamento \((x_i, r_i)[/late], per ogni i.
- Aggiungere una versione in scala di questo albero all’estimatore finale: \(\)\hat{f} ({\bf x}) \leftarrow \hat{f} ({\bf x}) + \lambda \hat{f}^b ({\bf x})\)
- Aggiornare i residui per tenere conto del nuovo modello: \(r_i \leftarrow r_i – \lambda \hat{f}^b (x_i)\)
Impostare il modello finale potenziato in modo che sia la somma dei singoli modelli studenti deboli: \(\hat{f}({\bf x}) = \sum_{b=1}^B \lambda \hat{f}^b ({\bf x})\)

Si noti che ogni albero successivo viene adattato ai residui dei dati. Quindi ogni iterazione successiva sta lentamente migliorando il modello forte complessivo migliorando le sue prestazioni nelle regioni con scarse prestazioni dello spazio delle feature.

Da sottolineare che questa procedura dipende fortemente dall’ordine in cui vengono addestrati gli alberi. Si dice che questo processo “impara lentamente”. Tali procedure di apprendimento lento tendono a produrre modelli di machine learning con buone prestazioni. Questo è il motivo per cui gli algoritmi di ensemble che coinvolgono modelli di machine learning potenziati tendono a vincere molte delle competizioni di Kaggle.

Ci sono tre iperparametri per l’algoritmo di potenziamento che abbiamo appena descritto. Vale a dire, la profondità dell’albero \(k\), il numero di alberi potenziati \(B\) e il tasso di contrazione \(\lambda\). Alcuni di questi parametri possono essere impostati mediante convalida incrociata.

Uno degli svantaggi computazionali del boosting è che si tratta di un metodo iterativo sequenziale. Ciò significa che non può essere facilmente parallelizzato, a differenza del bagging, che è parallelizzabile direttamente.

Esistono molti algoritmi di potenziamento, inclusi AdaBoost, xgboost e LogitBoost. Prima che l’uso delle reti neurali profonde convoluzionali diventasse prevalente, gli alberi potenziati erano spesso (e sono tuttora!) alcuni dei migliori strumenti di classificazione “out of the box” esistenti.

Nel prossimo paragrafo descriviamo come il boosting si confronta con il bagging, almeno per il caso del Decision Tree.

Implementazione con Python Scikit-Learn

In questo paragrafo applichiamo i tre metodi d’insieme, descritti in precedenza, per prevedere i rendimenti giornalieri per le azioni Amazon, utilizzando i tre giorni precedenti dei dati sui rendimenti.

Questo è un compito impegnativo, dato che i titoli liquidi come Amazon hanno un basso rapporto segnale-rumore. Inoltre tali dati sono anche correlati serialmente, cioè i campioni scelti non sono veramente indipendenti l’uno dall’altro, quindi si possono avere conseguenze spiacevoli per la validità statistica della procedura.

Negli articoli successivi eseguiamo una procedura più robusta tramite il meccanismo di convalida incrociata delle serie temporali implementato in Scikit-Learn. Per ora, usiamo una suddivisione standard di training-testing, dato che in questo articolo ci concentriamo sul confronto dell’errore tra i modelli e non sull’errore assoluto ottenuto su ciascuno.

Il risultato finale è un grafico dell’errore quadratico medio (MSE) di ciascun metodo (bagging, random forest e boosting) rispetto al numero di stimatori utilizzati nel campione. Vediamo chiaramente che il bagging e le foreste casuali non si adattano all’aumentare del numero di stimatori, mentre AdaBoost si adatta significativamente.

Come sempre, il primo passaggio è importare le necessarie librerie e le funzioni Python. Per questo script sono necessari molti moduli, la maggior parte dei quali si trova nella libreria Scikit-Learn. Inoltre dobbiamo importare i “soliti sospetti”, ovvero Matplotlib, NumPy, Pandas e Seaborn per l’analisi e il plotting dei dati. Inoltre abbiamo bisogno dei metodi d’insieme come BaggingRegressor, RandomForestRegressor e AdaBoostRegressor. Infine, importiamo la metrica mean_squared_error, lo strumento di convalida incrociata train_test_split, lo strumento di preprocessing e di DecisionTreeRegressor

				
					# ensemble_prediction.py

import datetime

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import yfinance as yf
import seaborn as sns
import sklearn
from sklearn.ensemble import (
    BaggingRegressor, RandomForestRegressor, AdaBoostRegressor
)
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import scale
from sklearn.tree import DecisionTreeRegressor

Prima di tutto dobbiamo usare Pandas per creare il DataFrame dei valori ritardati. Questo particolare pezzo di codice è stato ampiamente utilizzato in altri articoli sul sito, quindi non c’è bisogno di descriverlo nei dettagli. La funzione crea un DataFrame contenente i dati dei rendimenti ritardati di tre giorni per una specifica serie temporale di un asset disponibile su Yahoo Finance (oltre al volume degli scambi giornalieri):

				
					
def create_lagged_series(symbol, start_date, end_date, lags=3):
    """
    Crea un DataFrame panda che memorizza
    i rendimenti percentuali dell valore della chiusura
    rettificata di un assest scaricato da Yahoo Finance,
    insieme a una serie di rendimenti ritardati dei
    giorni di trading precedenti (il ritardo predefinito è 3 giorni).
    È incluso anche il volume degli scambi.
    """

    # Scaricare i dati storici da Yahoo Finance
    ts = yf.download(symbol, start=start_date, end=end_date)

    # Creazione di un DataFrame dei ritardi
    tslag = pd.DataFrame(index=ts.index)
    tslag["Today"] = ts["Adj Close"]
    tslag["Volume"] = ts["Volume"]

    # Creazione della serie dei ritardi dei
    # prezzi di chiusura dei giorni precedenti
    for i in range(0,lags):
        tslag["Lag%s" % str(i+1)] = ts["Adj Close"].shift(i+1)

    # Creazione del DataFrame dei rendimenti
    tsret = pd.DataFrame(index=tslag.index)
    tsret["Volume"] = tslag["Volume"]
    tsret["Today"] = tslag["Today"].pct_change()*100.0

    # Creazione delle colonne delle percentuali dei rendimenti ritardi
    for i in range(0,lags):
        tsret["Lag%s" % str(i+1)] = tslag[
            "Lag%s" % str(i+1)
        ].pct_change()*100.0
    tsret = tsret[tsret.index >= start_date]
    return tsret

Nella funzione __main__ impostiamo i parametri. Innanzitutto definiamo un seme casuale per rendere il codice replicabile su altri ambienti di lavoro. Il parametro n_jobs controlla il numero dei core del processore da utilizzare per il bagging e per le foreste casuali. Il boosting non è parallelizzabile, quindi non fa uso di questo parametro. Il parametro n_estimators definisce il numero totale di stimatori da utilizzare nel grafico del MSE, mentre step_factor controlla la granularità del calcolo impostando i passi attraverso il numero di stimatori. In questo caso axis_step è uguale a 1000/10 = 100, cioè sono eseguiti 100 calcoli separati per ciascuno dei tre metodi di ensemble:

				
					    # Impostazione del seed random, numero di stimatori
    # and lo "step factor" usato per il grafico di MSE
    # per ogni metodo
    random_state = 42
    n_jobs = 1  # Fattore di parallelizazione per il bagging e random forests
    n_estimators = 1000
    step_factor = 10
    axis_step = int(n_estimators/step_factor)

Il codice seguente scarica dieci anni di prezzi AMZN e li converte in una serie dei rendimenti lagged utilizzando la funzione create_lagged_series. I valori mancanti vengono eliminati (una conseguenza della procedura di calcolo dei ritardi) e i dati vengono ridimensionati in modo che siano compresi tra -1 e +1 per facilitare il confronto. Quest’ultima procedura è comune nel machine learning e permette alle feature con grandi differenze nelle dimensioni assolute di essere paragonabili ai modelli:

				
					    # Scaricare 10 anni di storico di Amazon
start = datetime.datetime(2006, 1, 1)
end = datetime.datetime(2015, 12, 31)
amzn = create_lagged_series("AMZN", start, end, lags=3)
amzn.dropna(inplace=True)

# Uso dei ritardi dei primi 3 giorni dei prezzi close di AMZN
# e ridimensione dei dati ttra -1 e +1 per i confronti
X = amzn[["Lag1", "Lag2", "Lag3"]]
y = amzn["Today"]
X = scale(X)
y = scale(y)

I dati sono suddivisi in un set di addestramento e un set di test, con il 70% dei dati che formano i dati di addestramento e il restante 30% che formano il set di test. Da sottolineare che le serie temporali di dati finanziari hanno correlazione seriale, quindi questa procedura introduce alcuni errori dato che non teniamo di questa correlazione. Tuttavia, è trascurabile nel confronto tra i tre metodi d’insieme, scopo principale di questo articolo:

				
					    # Divisione in training-testing con il 70% dei dati per il 
    # training e il rimanente 30% dei dati per il testing
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.3, random_state=random_state
    )

Le seguenti matrici NumPy memorizzano il numero di stimatori a ogni step dell’asse, nonché l’effettivo MSE associato per ciascuno dei tre metodi dell’insieme. Sono tutti inizialmente azzerati e successivamente compilati:

				
					    # Inizializzazione degli array che conterrano il 
    # MSE per ogni metodo d'insieme
    estimators = np.zeros(axis_step)
    bagging_mse = np.zeros(axis_step)
    rf_mse = np.zeros(axis_step)
    boosting_mse = np.zeros(axis_step)

Il primo metodo di ensemble da utilizzare è la procedura di bagging. Il codice esegue un’iterazione sul numero totale di stimatori (in questo caso da 1 a 1000, con un passo di dimensione pari a 10), definisce il modello dell’insieme con il corretto modello di base (in questo caso un Decision Tree di regressione), lo adatta ai dati di addestramento e quindi calcola l’errore quadratico medio sui dati del test. Questo MSE viene quindi aggiunto all’array del bagging MSE:

				
					    # Stimare il Bagging MSE per l'intero numero di
    # stimatore, con un passo specifico ("step_factor")
    for i in range(0, axis_step):
        print("Bagging Estimator: %d of %d..." % (
            step_factor * (i + 1), n_estimators)
              )
        bagging = BaggingRegressor(
            DecisionTreeRegressor(),
            n_estimators=step_factor * (i + 1),
            n_jobs=n_jobs,
            random_state=random_state
        )
        bagging.fit(X_train, y_train)
        mse = mean_squared_error(y_test, bagging.predict(X_test))
        estimators[i] = step_factor * (i + 1)
        bagging_mse[i] = mse

Lo stesso approccio viene eseguito per le random forest. Poiché le foreste casuali utilizzano implicitamente un albero di regressione come stimatore di base, non è necessario specificarlo nel costruttore dell’insieme:

				
					     # Stima del Random Forest MSE per l'intero numero di
    # stimatori, con un passo specifico ("step_factor")
    for i in range(0, axis_step):
        print("Random Forest Estimator: %d of %d..." % (
            step_factor * (i + 1), n_estimators)
              )
        rf = RandomForestRegressor(
            n_estimators=step_factor * (i + 1),
            n_jobs=n_jobs,
            random_state=random_state
        )
        rf.fit(X_train, y_train)
        mse = mean_squared_error(y_test, rf.predict(X_test))
        estimators[i] = step_factor * (i + 1)
        rf_mse[i] = mse

Allo stesso modo per l’algoritmo di boosting AdaBoost sebbene non è presente il parametro n_jobs perchè le tecniche di boosting non sono parallelizzabili. Il tasso di apprendimento, o fattore di contrazione, \lambda è stato impostato a 0,01. La regolazione di questo valore ha un grande impatto sull’assoluto MSE calcolato per ciascun stimatore totale:

				
					    # Stima del AdaBoost MSE per l'intero numero di
    # stimatori, con un passo specifico ("step_factor")
    for i in range(0, axis_step):
        print("Boosting Estimator: %d of %d..." % (
            step_factor * (i + 1), n_estimators)
              )
        boosting = AdaBoostRegressor(
            DecisionTreeRegressor(),
            n_estimators=step_factor * (i + 1),
            random_state=random_state,
            learning_rate=0.01
        )
        boosting.fit(X_train, y_train)
        mse = mean_squared_error(y_test, boosting.predict(X_test))
        estimators[i] = step_factor * (i + 1)
        boosting_mse[i] = mse

L’ultimo pezzo di codice grafica semplicemente questi array l’uno contro l’altro usando Matplotlib, ma con la combinazione di colori predefinita di Seaborn, che è visivamente più gradevole rispetto ai valori predefiniti di Matplotlib:

				
					    # Visualizzazione del grafico del MSE per il numero di stimatori
    plt.figure(figsize=(8, 8))
    plt.title('Bagging, Random Forest and Boosting comparison')
    plt.plot(estimators, bagging_mse, 'b-', color="black", label='Bagging')
    plt.plot(estimators, rf_mse, 'b-', color="blue", label='Random Forest')
    plt.plot(estimators, boosting_mse, 'b-', color="red", label='AdaBoost')
    plt.legend(loc='upper right')
    plt.xlabel('Estimators')
    plt.ylabel('Mean Squared Error')
    plt.show()

Il grafico risultante è riportato nella figura seguente. Da notare come l’aumento del numero di stimatori per i metodi basati sul bootstrap (bagging e foreste casuali) porta l’MSE a “sistemarsi” e diventare quasi identico tra di loro. Tuttavia, per l’algoritmo di potenziamento AdaBoost si può vedere che l’aumento del numero di stimatori oltre a circa 100, il metodo inizia ad aver un significativo overfit.

Quando si costruisce una strategia di trading basata su una procedura di boosting ensemble, questo fatto deve essere tenuto presente, altrimenti è probabile ottenere una significativa sottoperformance della strategia quando viene applicata a dati finanziari fuori campione.

In un articolo successivo utilizziamo i modelli di insieme per prevedere i rendimenti degli asset utilizzando DataTrader. Vediamo inoltre se è fattibile produrre una strategia solida che possa essere redditizia al di sopra dei costi di transazione a frequenza più elevata, necessari per eseguire questa strategia a mercato.