Home » Intelligenza Artificiale » 📋 URL
Il pruning, bagging e random forest sono tre diverse tecniche per evitare che avvenga overfitting nella creazione di alberi decisionali. Analizziamoli separatamente:
Pruning
Utilizziamo la tecnica del pruning per capire quali sono i nodi più significativi nella risoluzione del problema. Definiremo quindi delle quantità che ci permetteranno di confrontare il nostro problema con la tabella chi-quadro \left(\chi^2\right), tramite cui possiamo controllare quanto significativo un certo attributo risulta essere rispetto agli attributi totali. Procediamo con quello che chiameremo significance test.
Chiamiamo \hat{p_k} e \hat{n_k} il numero di esempi positivi e negativi di un problema, per i diversi valori di k li definiamo come
\hat{p_k}=p\cdot\frac{p_k+n_k}{p+n}\qquad\hat{n_k}=n\cdot\frac{p_k+n_k}{p+n}Utilizzando tali quantità possiamo definire
\Delta=\sum_{k}\left(\dfrac{\left(p_k-\hat{p_k}\right)^2}{\hat{p_k}}+\dfrac{\left(n_k-\hat{n_k}\right)^2}{\hat{n_k}}\right)La quantità \Delta dovremo confrontarla con il valore standard \Delta^* che può essere ottenuto tramite la tabella \chi^2 nella riga \ell=k-1 e, generalmente, controlleremo nella colonna 0.05, ovvero quella che ci permette di essere sicuri al 95\% che il valore considerato sia effettivamente significativo.
Esercizio (non controllato): Trovare il valore \Delta^*per l’attributo \texttt{Type}, e confrontarlo con il suo valore \Delta per capire se è un attributo significativo
Soluzione
Definiamo dapprima i valori \hat{p_k} e \hat{n_k} considerando che p+n=N rappresenta il numero totale di esempi che stiamo considerando, dunque 12, mentre si ha \Delta=0
Esercizio (dalle slide): Trovare il valore \Delta^*per l’attributo \texttt{Hungry}, e confrontarlo con il suo valore \Delta per capire se è un attributo significativo
Soluzione
Per l’attributo \texttt{Hungry} avremo p=2 e n=4, mentre nel caso in cui la risposta sia \texttt{No} si hanno
\hat{p_{k1}}=2\cdot\frac{0+2}{2+4}=\frac{4}{6}=\frac{2}{3}\qquad \hat{n_{k1}}=4\cdot\frac{0+2}{2+4}=\frac{8}{6}=\frac{4}{3}Nel caso invece in cui la risposta sia \texttt{Yes} si hanno i valori
\hat{p_{k2}}=2\cdot\frac{2+2}{2+4}=\frac{4}{3}\qquad \hat{n_{k2}}=4\cdot\frac{2+2}{2+4}=\frac{16}{6}=\frac{8}{3}Possiamo ora calcolare \Delta tramite
\begin{aligned}\Delta&=\underbrace{\dfrac{\left(0-\dfrac{2}{3}\right)^2}{\dfrac{2}{3}}+\dfrac{\left(2-\dfrac{4}{3}\right)^2}{\dfrac{4}{3}}}_{\displaystyle \text{per } k_1}+\underbrace{\dfrac{\left(2-\dfrac{4}{3}\right)^2}{\dfrac{4}{3}}+\dfrac{\left(2-\dfrac{8}{3}\right)}{\dfrac{8}{3}}}_{\displaystyle\text{per }k_2}\\[10pt]&=1.5\end{aligned}Poiché abbiamo k=2 avremo \ell=k-1=1 dovremo guardare il valore di \Delta^* nella prima riga della tabella chi-quadro
Poiché \Delta^*<\Delta possiamo applicare il pruning all’attributo \texttt{Hungry}.
Bagging
Il bagging è una tecnica utilizzata per generare K distinti insiemi di allenamento da quello originale, scegliendo per ognuno di essi N esempi su cui allenare l’algoritmo di decision tree (che utilizzerà gli stessi attributi nella definizione dei nodi dell’albero), cercando in questo modo di limitare l’overfitting. Omettendo volutamente alcuni degli esempi stiamo infatti forzando l’algoritmo a imparare dei “dati un po’ sbagliati”, che proveremo a generalizzare nel seguente modo: dopo aver eseguito l’algoritmo di decision tree sui vari insiemi si aggregano le predizioni fatte dai K modelli diversi in una unica, prendendo il risultato dell’aggregazione come l’effettiva predizione sull’insieme originale.
Nota bene: aggregare le previsioni puo essere fatto in maniera diversa in base al problema che si sta trattando. Il lato negativo di questa tecnica consiste nella creazione dei K alberi che hanno delle caratteristiche molto correlate, cosa che non ci porta necessariamente ad esplorare tutte le possibili opzioni.
Random Forest
Per ovviare al problema delle caratteristiche correlate emerso dall’utilizzo del pruning, la tecnica della random forest sceglie casualmente anche l’attributo sul quale eseguire l’algoritmo di decision tree, calcolando per ognuno di essi l’information gain (vedere la pagina sugli alberi decisionali) tenendo di volta in volta soltanto quelli che hanno l’information gain maggiore.
In poche parole
✅ Il pruning, il bagging e la random forest sono tecniche utilizzate per evitare l’overfitting negli alberi decisionali. Il pruning identifica gli attributi significativi tramite un test di significatività. Il bagging crea insiemi di addestramento diversi e aggrega le previsioni dei modelli (creando degli alberi che presentano sempre gli stessi attributi nei nodi). La random forest è come il bagging, però seleziona casualmente gli attributi e evita la correlazione tra gli alberi. Queste tecniche migliorano la generalizzazione degli alberi decisionali.