Random Forest e l’Ensemble Learning

Come indica creativamente il nome dell’algoritmo, il Random Forest (Foresta Casuale) è un algoritmo di Ensemble learning¹, composto dunque non da un unico albero decisionale ma da tanti. La stima, in caso si tratti di una classificazione, sarà la classe più “votata” fra le stime dei singoli alberi decisionali (quindi la moda, Figura 3.6). Per problemi di regressione si tratterà della media dei singoli valori previsti dagli alberi. Pur essendo un algoritmo molto semplice si è rivelato essere uno degli strumenti più potenti e versatili utilizzato ad oggi dai data scientist.

1 Gli algoritmi di Ensemble sono algoritmi composti che prendono in considerazione le singole stime di ogni componente (solitamente algoritmi detti deboli) per creare una stima finale pesata.

88

Figura 3.6: Schema di struttura del Random Forest.

I metodi di Ensemble Learning hanno dimostrato più e più volte di funzionare meglio rispetto ai singoli algoritmi. Addirittura, ci sono prove che un algoritmo di Ensemble composto da molti stimatori “deboli” forniscono una stima più accurata del più potente degli stimatori “singoli”. L’intuizione che spiega il perché di questo fenomeno la si può delineare anche con il comportamento umano. Di fronte ad un problema spesso è utile prendere in considerazione l’opinione di più esperti contemporaneamente, invece che quella del singolo, per via dei vari punti di vista e le diverse esperienze e competenze. Questo si riflette in molte delle nostre organizzazioni odierne:

parlamenti, consigli di amministrazione, compagni dell’università organizzando una cena di classe, ecc. La Democrazia stessa, sistema di governo più diffuso oggi nel mondo¹, è guidata da questo concetto e la sua separazione dei poteri (fra legislativo, giudiziario ed esecutivo) teorizzata dal francese Montesquieu², ne riflette l’anima. Così come una persona è diversa dalle altre e riesce a notare aspetti che alle altre possono sfuggire,

1 [23]

2 [24] C.L. DE SECONDAT DE MONTESQUIEU, Lo spirito delle leggi, trad it. a cura di B. Boffito Serra, Milano, 1967, p. 207 e ss.

Categoria A Categoria B Categoria A Ensamble

Categoria A

Albero decisionale 1 Albero decisionale 2 Albero decisionale 3

89

un algoritmo costruito secondo criteri diversi da altri algoritmi può raccogliere aspetti che sfuggono ai secondi.

Le forme più famose ed utilizzate di Ensamble learning sono:

• Bagging¹: Si utilizza la stessa tipologia di algoritmo ma su diversi subset del training set creati con rimpiazzi (una istanza può finire più volte in più campioni). Solitamente il Random Forest utilizza questa logica riducendo fortemente la varianza nella previsione rispetto ad un singolo albero decisionale;

• Pasting: Esattamente come il Bagging ma senza il rimpiazzo;

• Stacking: Invece di utilizzare una predeterminata funzione, la media o la moda, come criterio decisionale per aggregare le singole

previsioni degli stimatori, lo Stacking utilizza a sua volta un algoritmo di apprendimento.

• Boosting: Si tratta di allenare gli algoritmi non parallelamente, come fatto per il Bagging e il Pasting, ma in modo sequenziale dando sempre più peso agli errori commessi dagli algoritmi “precedenti”. In questo modo si spera che l’algoritmo successivo corregga quello precedente andando a migliorare l’accuratezza complessiva della previsione. Infine, si sceglie la stima finale considerando le stime pesate dei singoli algoritmi secondo un determinato criterio. Esempi di questi algoritmi sono:

o AdaBoost (Adaptive Boost)² o Gradient Boosting ³

3.4.3.1 AdaBoost

Volendo capire l’idea alla base e per presentare l’AdaBoost senza entrare nel particolare di ogni sua variante, si elencano i seguenti passi logici:

0- Considerando un problema di classificazione binario con:

o N v_L, v_?… v vettori (istanze) in input;

1 Breiman, L. Bagging Predictors. Machine Learning 24, 123–140 (1996).

2 [25] Yoav Freund and Robert E. Schapire. “A decision-theoretic generalization of on-line learning and an application to boosting”. Journal of Computer and System Sciences, 55(1):119–139, August 1997;

3 [26] Jerome H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine, Aprile 2001

90

1- Si inizializza assegnando il peso di default Æ =_c^L ∀8 2- Per m= 1,…,M:

2.1- Si allena il classificatore x (v) sul training set minimizzando la funzione di errore:

º = " Æ 9(x (v ) ≠ )

c L

(3.56)

Ž 8 9(x (v ) ≠ ) g1 % x (v ) ≠0 % x (v ) = 2.2- Si calcolano le quantità:

È =∑^c _LÆ 9(x (v ) ≠ )

∑^c _LÆ (3.57)

G = ln Ê1 − È

È Ë (3.58)

Con È l’errore nella misurazione dello stimatore m, G il peso che si darà alla stima dello stimatore m.

2.3- Si aggiornano I pesi delle istanze:

Æ ^L = Æ v5[G 9(x (v ) ≠ )] (3.59) 3- Si esegue la stima finale YM:

Ì_•(v) = %6V8 ¨" G x (v)

• L

© (3.60)

Secondo questa logica quindi, allenato un primo stimatore, si evince quelle che sono le istanze per le quali la sua previsione non è stata corretta.

Queste istanze vedranno un aumento del loro peso wn (boosting appunto) e saranno così considerate maggiormente dal successivo stimatore grazie allo step di aggiornamento 2.3. Infine, nella stima finale, si darà una maggior considerazione ai classificatori con un errore di previsione È inferiore.

91 3.4.3.2 Gradient Boosting

Questo algoritmo si basa più sulla “discesa del gradiente”, ovvero data una determinata funzione di costo (solitamente si utilizza l’errore quadratico medio per i problemi di regressione e la perdita logaritmica per problemi di classificazione), si cerca di minimizzare gli errori commessi allenando in sequenza stimatori deboli (solitamente degli alberi decisionali):

0- Considerando:

o v = v_L, … , v il vettore degli input (istanze);

o “ = 1, … , Ä stimatori in sequenza;

o $(v, 0) = ∑^• _~Q ℎ(v, G ) la funzione di previsione con parametri 0 = {Q , G } che prende in input il vettore v per stimare la variabile target x = x_L, … , x ;

o ℎ(v, G ) una funzione di v avente come parametri G = G_L, … , G_•

o .(x , Í) la funzione di costo con Í il “tasso di apprendimento”

, con il quale si correggono gli errori di stima;

1- Si inizializza con $_~(v) = V “68_Î∑ .(x , Í)^c_KL 2- Per m=1,…,M:

2.1- Si calcola il gradiente come:

xÏ = − Ð .(x , $(v ))

$(v ) Ñ (3.61)

2.2- Si allena il modello:

G = arg “68_Ó,Ô"[xÏ − Qℎ(v , G )]^?

c

L (3.62)

2.3- Se sceglie il grado di apprendimento:

Í = arg “68_Î" .(x , $ _KL(v ) + Íℎ(v , G)

c KL

) (3.63)

2.4- Si aggiornano le stime rispetto al modello precedente:

$ (v) = $ _KL(v) + Í ℎ(v, G ) (3.64) 3- Fine dell’algoritmo.

92

3.4.3.3 Vantaggi e Svantaggi del Random Forest Tra i vantaggi si hanno:

• Comporta tutti i vantaggi del Decision Tree ma, rispetto a questo, riduce inoltre il rischio di overfitting, riduce la varianza e spesso viene migliorata di molto l’accuratezza;

• Versatilità, infatti è molto performante sia su problemi di classificazione che di regressione;

Svantaggi:

• Richiede maggiori tempi di calcolo rispetto al singolo Decision Tree;

• La complessità dell’interpretazione dei risultati aumenta notevolmente dal momento che si considerano tanti singoli Decision Tree e vengono combinati i singoli risultati.