Alberi di decisione

Gli alberi sono tra i metodi più efficaci per l'apprendimento supervisionato su dati tabellari di dimensione medio-piccola (meno di circa 10 000 campioni), e le idee alla base sono semplici. Qui si costruisce l'albero singolo; la combinazione di molti alberi (foreste, boosting) è in Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →. Gli esercizi sono Esercizio - Albero di decisione ID3 sul dataset del tennis, Esercizio - Albero di decisione con criteri di impurità e potatura sul dataset iris e Esercizio - ID3 con potatura e foresta casuale sul dataset Titanic.

L'idea: decisioni a una variabile alla volta

Un esempio di decisione medica: «età > 50? peso > 90 kg? fumatore?» da cui si stima il rischio di infarto. Il diagramma è probabilmente stato costruito da dati storici: è un problema supervisionato multivariato di classificazione, ma ogni decisione guarda una sola variabile per volta.

Definizione (albero di decisione). Struttura ad albero in cui

• ogni nodo interno rappresenta una regola basata su una feature (per esempio «umidità = alta» oppure «$x_3\le1{,}9$»);
• ogni ramo è l'esito della regola;
• ogni foglia è una predizione: tipicamente la classe più frequente tra i campioni che arrivano in quella foglia (in regressione, la media dei loro valori).

Per classificare un nuovo punto si parte dalla radice e si segue il ramo indicato dal valore delle sue feature, fino a una foglia.

L'obiettivo dell'addestramento è trovare le decisioni (coppie variabile-valore, o variabile-soglia) che dividono i dati in scenari in cui una classe diventa dominante o più facile da prevedere. Si procede in modo ricorsivo:

1. si parte dalla radice con tutti i dati;
2. si sceglie la variabile (e il valore) che «semplifica» di più il problema, cioè che rende più omogenee le classi nei figli;
3. si divide e si ripete su ciascun figlio, finché le classi sono separate o si raggiunge una profondità massima.

Serve una misura quantitativa di quanto sia «semplice» un nodo: le misure di impurità.

Entropia e guadagno d'informazione

Definizione (entropia). (Logaritmo in base 2: Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →.) Per un insieme $S$ di campioni con $c$ classi, di proporzioni $p_1,\dots,p_c$, $$H(S)=-\sum_{i=1}^cp_i\log_2p_i\qquad(\text{con }0\log_20=0).$$ $H=0$: l'insieme è puro (una sola classe); $H$ più alta: classi più mescolate, maggiore incertezza. Con due classi il massimo è $1$ per $p=\tfrac12$.

Definizione (guadagno d'informazione). Dividere $S$ secondo i valori $v$ dell'attributo $A$ in sottoinsiemi $S_v$ riduce l'entropia di $$IG(S,A)=H(S)-\sum_{v\in\text{Valori}(A)}\frac{|S_v|}{|S|}\,H(S_v).$$ $IG$ alto: la divisione riduce molto l'incertezza (buona scelta); $IG$ basso: l'attributo non aiuta a separare le classi.

Il secondo termine è la media delle entropie dei figli pesata dalla frazione di campioni di ciascun figlio.

Da dove viene l'entropia (passaggi). Si vuole un numero che misuri la «sorpresa» nel vedere la classe di un campione.

1. Un evento di probabilità $p$ è tanto più sorprendente quanto più è raro, e la sorpresa di due eventi indipendenti si somma mentre le loro probabilità si moltiplicano (la probabilità di eventi indipendenti si moltiplica: Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →). L'unica funzione di $p$ che trasforma un prodotto in una somma è il logaritmo: la sorpresa è $-\log_2 p$ (proprietà $\log(ab)=\log a+\log b$: Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →). Il segno meno la rende $\ge0$ perché $\log_2p\le0$ quando $0<p\le1$; l'evento certo ($p=1$) ha sorpresa $0$, quello con $p=\tfrac12$ ha sorpresa $1$ bit.
2. L'entropia è la sorpresa media sulle classi, cioè il valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → della sorpresa: ogni classe $i$ capita con probabilità $p_i$ e porta sorpresa $-\log_2p_i$, quindi $H=\sum_ip_i\,(-\log_2p_i)$. È la formula sopra.
3. Il logaritmo in base 2 si calcola con il cambio di base $\log_2x=\ln x/\ln2$: per esempio $\log_2\tfrac9{14}=\ln(0{,}6429)/\ln2=-0{,}4418/0{,}6931=-0{,}637$.

Perché il massimo con due classi è in $p=\tfrac12$. Con due classi $H(p)=-p\log_2p-(1-p)\log_2(1-p)$. Si deriva (Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →; $(\log_2p)'=\frac1{p\ln2}$): $H'(p)=-\log_2p-\frac1{\ln2}+\log_2(1-p)+\frac1{\ln2}=\log_2\frac{1-p}{p}$. È $0$ quando $\frac{1-p}{p}=1$, cioè $p=\tfrac12$, positiva a sinistra e negativa a destra (Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →). La derivata seconda $H''(p)=-\frac1{\ln2}\cdot\frac1{p(1-p)}<0$ conferma che $H$ è concava (Funzioni convesse, concave e punti di flessof è convessa se ogni corda sta sopra il grafico (concava se sta sotto). Una funzione convessa è continua e ha derivate destra e sinistra in ogni punto interno. Per f derivabile: convessa ⇔ grafico sopra ogni tangente ⇔ f' crescente ⇔ (se esiste) f'' ≥ 0. f'' > 0 ⇒ strettamente convessa, non viceversa (x⁴). Flesso: punto in cui f passa da convessa a concava; lì, se esiste, f''(x0) = 0, ma non basta (x⁴ in 0).Funzioni convesse, concave e punti di flesso →), quindi quel punto è un massimo, con $H(\tfrac12)=1$. Per $c$ classi equiprobabili $H=\log_2c$.

Esempio (dataset del tennis, Mitchell 1997). Dati di 14 giorni per prevedere se l'amico gioca a tennis:

(Le slide indicano $n=15$ ma le righe sono 14.) Ci sono $9$ «Yes» e $5$ «No»: $H(S)=-\tfrac9{14}\log_2\tfrac9{14}-\tfrac5{14}\log_2\tfrac5{14}=0{,}643\cdot0{,}637+0{,}357\cdot1{,}485=0{,}410+0{,}530=0{,}940$.

Passi del calcolo: $\tfrac9{14}=0{,}643$ e $\tfrac5{14}=0{,}357$; $-\log_2\tfrac9{14}=0{,}637$ e $-\log_2\tfrac5{14}=1{,}485$ (la classe rara è più «sorprendente»); media pesata $0{,}643\cdot0{,}637=0{,}410$ più $0{,}357\cdot1{,}485=0{,}530$, in totale $0{,}940$. Un'entropia di $0{,}940$ su un massimo di $1$ dice che il nodo è quasi del tutto misto.

Passo 1: scelta della radice. Per ogni attributo si calcola l'entropia di ciascun sottoinsieme. Un esempio completo: Sunny ha $2$ Yes e $3$ No su $5$, quindi $p=\tfrac25=0{,}4$ e $1-p=0{,}6$, e $H=-0{,}4\log_2 0{,}4-0{,}6\log_20{,}6=0{,}4\cdot1{,}322+0{,}6\cdot0{,}737=0{,}529+0{,}442=0{,}971$. Gli altri valori sotto si ottengono allo stesso modo: $H(\tfrac46,\tfrac26)=0{,}918$, $H(\tfrac34,\tfrac14)=0{,}811$, $H(\tfrac37,\tfrac47)=0{,}985$, $H(\tfrac67,\tfrac17)=0{,}592$.

• Outlook: Sunny (5: 2 Yes, 3 No) $H=0{,}971$; Overcast (4: 4 Yes) $H=0$; Rain (5: 3 Yes, 2 No) $H=0{,}971$. $IG=0{,}940-\big(\tfrac5{14}0{,}971+\tfrac4{14}0+\tfrac5{14}0{,}971\big)=0{,}940-0{,}693=\mathbf{0{,}247}$.
• Temperature: Hot (4: 2/2) $H=1$; Mild (6: 4/2) $H=0{,}918$; Cool (4: 3/1) $H=0{,}811$. $IG=0{,}940-(\tfrac4{14}1+\tfrac6{14}0{,}918+\tfrac4{14}0{,}811)=0{,}940-0{,}911=0{,}029$.
• Humidity: High (7: 3 Yes, 4 No) $H=0{,}985$; Normal (7: 6/1) $H=0{,}592$. $IG=0{,}940-(0{,}5\cdot0{,}985+0{,}5\cdot0{,}592)=0{,}940-0{,}788=0{,}152$.
• Wind: Weak (8: 6/2) $H=0{,}811$; Strong (6: 3/3) $H=1$. $IG=0{,}940-(\tfrac8{14}0{,}811+\tfrac6{14}1)=0{,}940-0{,}892=0{,}048$.

Il guadagno massimo è quello di Outlook ($0{,}247$): è la radice. Il ramo Overcast è già puro (sempre Yes): foglia «Yes».

Passo 2: rami Sunny e Rain.

• Sunny (5 campioni: 2 Yes, 3 No, $H=0{,}971$): lo split su Humidity dà High $\to$ 3 No ($H=0$) e Normal $\to$ 2 Yes ($H=0$): $IG=0{,}971$, il massimo possibile (Temperature darebbe $0{,}571$, Wind $0{,}020$).
• Rain (5 campioni: 3 Yes, 2 No): lo split su Wind dà Weak $\to$ 3 Yes e Strong $\to$ 2 No: $IG=0{,}971$.

Outlook?
├── Sunny    -> Humidity?
│               ├── High   -> No
│               └── Normal -> Yes
├── Overcast -> Yes
└── Rain     -> Wind?
                ├── Weak   -> Yes
                └── Strong -> No

L'albero classifica correttamente tutti i 14 campioni di training. Le regole sono immediatamente leggibili («se è soleggiato e l'umidità è normale, gioca»).

L'indice di Gini e l'algoritmo CART

Definizione (indice di Gini o impurità di Gini). $\displaystyle\operatorname{Gini}(S)=1-\sum_{i=1}^cp_i^2.$ Vale $0$ per un insieme puro, e il massimo $1-\tfrac1c$ per classi equiprobabili. Per una divisione in sinistra/destra: $$\operatorname{Gini}_{\text{split}}=\frac{n_{\text{sx}}}{n}\operatorname{Gini}(\text{sx})+\frac{n_{\text{dx}}}{n}\operatorname{Gini}(\text{dx}).$$ Si sceglie la divisione con $\operatorname{Gini}_{\text{split}}$ minimo (cioè con la massima riduzione di impurità).

Che cosa misura il Gini. È la probabilità di sbagliare se si estrae a caso un campione e gli si assegna una classe estratta a caso con le stesse proporzioni. Le due estrazioni sono indipendenti, quindi la probabilità che abbiano la stessa classe $i$ è $p_i\cdot p_i=p_i^2$ (Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →); le classi sono eventi incompatibili, e per l'additività (Misura di probabilità e sue proprietàUna misura di probabilità è una funzione P: F → [0,1] con P(Ω) = 1 e σ-additiva; ne seguono P(Aᶜ) = 1 − P(A), P(∅) = 0, monotonia, P(A ∪ B) = P(A) + P(B) − P(A ∩ B) e la formula di inclusione-esclusione.Misura di probabilità e sue proprietà →) la probabilità che le due classi coincidano è $\sum_ip_i^2$. Il Gini $1-\sum p_i^2$ è la probabilità del complementare: che le due classi differiscano. Per due classi $1-p^2-(1-p)^2=2p(1-p)$, con massimo $\tfrac12$ in $p=\tfrac12$. Con $c$ classi equiprobabili $p_i=\tfrac1c$: $1-c\cdot\tfrac1{c^2}=1-\tfrac1c$. Rispetto all'entropia non serve calcolare logaritmi.

Esempio. Sul tennis, $\operatorname{Gini}(S)=1-(\tfrac9{14})^2-(\tfrac5{14})^2=1-0{,}413-0{,}128=0{,}459$. Split su Outlook: Sunny $1-(0{,}4)^2-(0{,}6)^2=0{,}48$, Overcast $0$, Rain $0{,}48$, quindi $\operatorname{Gini}_{\text{split}}=\tfrac5{14}0{,}48+0+\tfrac5{14}0{,}48=0{,}343$ (riduzione $0{,}116$); Humidity: $0{,}367$; Wind: $0{,}429$; Temperature: $0{,}440$. Anche con Gini la scelta migliore è Outlook. I passaggi di Humidity: High ($3$ Yes, $4$ No su $7$) $\operatorname{Gini}=1-(\tfrac37)^2-(\tfrac47)^2=1-\tfrac9{49}-\tfrac{16}{49}=\tfrac{24}{49}=0{,}490$; Normal ($6$ Yes, $1$ No) $1-\tfrac{36}{49}-\tfrac1{49}=\tfrac{12}{49}=0{,}245$; media pesata $\tfrac7{14}\cdot0{,}490+\tfrac7{14}\cdot0{,}245=0{,}367$. Wind: Weak ($6/2$) $1-0{,}5625-0{,}0625=0{,}375$, Strong ($3/3$) $0{,}5$, quindi $\tfrac8{14}0{,}375+\tfrac6{14}0{,}5=0{,}214+0{,}214=0{,}429$.

Le due curve sono molto simili, come quella dell'errore di classificazione $1-\max_ip_i$ (per due classi, in funzione di $p$):

(Il Gini ha massimo $0{,}5$ per due classi.)

CART (Classification And Regression Trees) costruisce alberi binari con un algoritmo ricorsivo:

CART(dati):
    se tutti gli esempi hanno la stessa classe  ->  foglia con quella classe
    miglior_divisione = attributo e valore con il Gini_split minimo
    se nessuna divisione migliora il Gini        ->  foglia con la classe maggioritaria
    sx, dx = dividi i dati con la miglior_divisione
    nodo con: la condizione, CART(sx), CART(dx)

Variabili numeriche

Per una feature numerica (per esempio la lunghezza del petalo) CART considera divisioni binarie $x\le t$ e prova molte soglie $t$ (di solito i punti medi tra valori consecutivi dei dati ordinati), scegliendo quella che minimizza l'impurità. Per le variabili categoriche si divide in «uguale a un valore» / «diverso».

Esempio. $x=[1,2,3,4,5,6]$ con etichette $[A,A,B,A,B,B]$. Per le soglie $t=1{,}5;\ 2{,}5;\ 3{,}5;\ 4{,}5;\ 5{,}5$ il Gini ponderato vale $0{,}400;\ 0{,}250;\ 0{,}444;\ 0{,}250;\ 0{,}400$. Per $t=2{,}5$: sinistra $\{A,A\}$ (Gini $0$), destra $\{B,A,B,B\}$ (Gini $1-(0{,}25)^2-(0{,}75)^2=0{,}375$): $\tfrac26\cdot0+\tfrac46\cdot0{,}375=0{,}25$. Le soglie $2{,}5$ e $4{,}5$ sono alla pari (ex aequo): si sceglie la prima trovata.

Esempio (dataset iris con CART, profondità 3). Radice: petalo $\le0{,}8$ cm (o, equivalentemente, lunghezza del petalo $\le1{,}9$) isola le 50 setosa. Poi larghezza $\le1{,}75$ e lunghezza $\le4{,}95$ o $\le4{,}85$. Accuracy sul training $0{,}973$ con profondità 3 ($0{,}667$ con profondità 1, $0{,}960$ con 2, $0{,}993$ con 4, $1{,}0$ con 5).

Alberi di regressione

Con un target continuo cambiano il criterio di divisione e l'uscita delle foglie.

Formula (criteri per la regressione). Per una divisione in sinistra/destra con $n_L,n_R$ campioni ($n=n_L+n_R$): $$\mathrm{MSE}_{\text{split}}=\frac{n_L}{n}\mathrm{MSE}_L+\frac{n_R}{n}\mathrm{MSE}_R,\qquad\text{riduzione di varianza}=\operatorname{Var}(\text{genitore})-\Big(\frac{n_L}{n}\operatorname{Var}_L+\frac{n_R}{n}\operatorname{Var}_R\Big),$$ con $\operatorname{Var}(y)=\frac1n\sum(y_i-\bar y)^2$ (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →). Poiché in ogni nodo la previsione è la media (e quindi l'MSE del nodo è la sua varianza), massimizzare la riduzione di varianza equivale a minimizzare l'MSE. Ogni foglia restituisce la media del target dei suoi campioni.

Perché la foglia restituisce la media (passaggi). Una foglia ha una sola previsione $c$ per tutti i suoi campioni $y_1,\dots,y_m$ e si vuole la $c$ che minimizza l'errore quadratico $E(c)=\sum_i(y_i-c)^2$. È una parabola in $c$: $E'(c)=-2\sum_i(y_i-c)=-2\big(\sum_iy_i-mc\big)$, che si annulla in $c=\frac1m\sum_iy_i=\bar y$ (Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →); $E''(c)=2m>0$, quindi è un minimo. Con $c=\bar y$ l'errore medio è $\frac1m\sum(y_i-\bar y)^2$, cioè proprio la varianza del nodo (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →): per questo MSE del nodo e varianza coincidono.

Esempio. $x=[1,2,3,4,5,6]$, $y=[1,2,3,10,11,12]$: varianza del genitore $20{,}92$ (media $\tfrac{39}6=6{,}5$, scarti quadratici $30{,}25;\,20{,}25;\,12{,}25;\,12{,}25;\,20{,}25;\,30{,}25$, somma $125{,}5$, divisa per $6$). Per $t=2{,}5$: sinistra $[1,2]$ (varianza $0{,}25$), destra $[3,10,11,12]$ (media $9$, varianza $\tfrac{36+1+4+9}4=12{,}5$): MSE ponderato $\tfrac26\cdot0{,}25+\tfrac46\cdot12{,}5=0{,}083+8{,}333=8{,}42$. Ripetendo per tutte le soglie si ottiene $14{,}87;\ 8{,}42;\ \mathbf{0{,}67};\ 8{,}42;\ 14{,}87$ per $t=1{,}5;\ 2{,}5;\ 3{,}5;\ 4{,}5;\ 5{,}5$: la migliore è $t=3{,}5$ (sinistra $[1,2,3]$ con media $2$ e varianza $\tfrac23$; destra $[10,11,12]$ con media $11$ e varianza $\tfrac23$), con riduzione di varianza $20{,}92-0{,}67=20{,}25$. Le predizioni sono $2$ per $x\le3{,}5$ e $11$ per $x>3{,}5$: una funzione costante a tratti.

ID3 e altre varianti

ID3 (Iterative Dichotomiser 3) è l'algoritmo originale per feature categoriche, alternativo a CART:

• a ogni nodo si calcola l'entropia di split (o il guadagno) per ogni feature non ancora usata nel ramo e si sceglie la migliore;
• si divide in tutti i valori della feature, creando tanti figli quanti sono i valori (anche più di due, o uno solo);
• una feature usata non è riutilizzata nei discendenti;
• si fermano la crescita (foglia): nessun campione nel nodo $\to$ si predice la classe maggioritaria del genitore; tutti i campioni della stessa classe $\to$ quella classe; nessuna feature rimasta con classi miste $\to$ classe maggioritaria (e, opzionale, profondità massima).

Per le feature continue si può: usare la soglia binaria come in CART (scegliere la miglior $x\le t$), oppure quantizzare le variabili in intervalli e trattarle come categoriche (pre-elaborazione), oppure fare uno split multiplo con i punti medi tra valori consecutivi. Nelle prove di laboratorio sul Titanic la soglia ($0{,}825$ di accuracy su test) e la quantizzazione ($0{,}790$) sono confrontabili.

Overfitting e potatura

Un albero lasciato crescere fino a foglie pure separa perfettamente il training ma si adatta al rumore: varianza alta (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →), scarsa generalizzazione (lo stesso fenomeno di Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →). Al crescere della profondità l'accuracy sul training sale sempre (nell'iris da $0{,}667$ a $1{,}0$); su dati nuovi sale e poi scende. Due rimedi:

Pre-potatura (profondità massima). Si ferma la crescita a una profondità $d_{\max}$ anche se altre divisioni migliorerebbero l'adattamento (early stopping). Pro: veloce e facile da controllare; evita l'overfitting con pochi dati. Contro: può perdere divisioni utili subito oltre il limite e non guarda quanto siano significative. Nel laboratorio sul dataset wine l'accuracy su test passa da $0{,}730$ (profondità 1) a $0{,}946$ (2) e $0{,}973$ (3).

Post-potatura a costo-complessità (minimal cost-complexity pruning, di CART). Si lascia crescere l'albero completo e poi si tolgono i rami che non migliorano la generalizzazione. Si cercano i sottoalberi che bilanciano l'errore e la semplicità: $$R_\alpha(T)=R(T)+\alpha\,|T|,$$ con $R(T)$ l'errore (impurità di Gini o tasso di errata classificazione) dell'albero $T$, $|T|$ il numero di foglie e $\alpha\ge0$ il parametro di potatura (più alto = più potatura). Per ogni nodo interno $t$ si calcola il $\alpha$ al quale conviene sostituire il suo sottoalbero $T_t$ con una foglia: $$\alpha_{\text{eff}}(t)=\frac{R(t)-R(T_t)}{|T_t|-1},\qquad R(t)=\frac{n_t}{N}\,\operatorname{Gini}(t),\quad R(T_t)=\sum_{\text{foglie di }T_t}R(\ell).$$ Il numeratore è la riduzione di errore che quel sottoalbero apporta, il denominatore il numero di foglie «aggiunte». Si pota per primo il nodo con $\alpha_{\text{eff}}$ minimo (il «filo più debole»: aggiunge poco per foglia), si ricalcolano gli $\alpha_{\text{eff}}$ e si ripete; ciò dà una successione di alberi sempre più piccoli, tra cui si sceglie con una validazione. Pro: flessibile, di solito generalizza meglio del limite rigido; contro: più lenta (valuta sottoalberi) e richiede un'accurata scelta di $\alpha$.

Esempio (iris, albero di profondità 3, 150 campioni). I quattro nodi interni sono: (a) il nodo «larghezza $>1{,}75$» (46 campioni: 1 versicolor e 45 virginica) con due foglie $[0,1,2]$ e $[0,0,43]$: $R(t)=\tfrac{46}{150}\,\operatorname{Gini}=0{,}0130$, $R(T_t)=0{,}0089$, 2 foglie $\Rightarrow\alpha_{\text{eff}}=(0{,}0130-0{,}0089)/(2-1)=0{,}0042$; (b) il nodo «larghezza $\le1{,}75$» (54 campioni) con le foglie $[0,47,1]$ e $[0,2,4]$: $0{,}0297$; (c) il nodo «larghezza $>0{,}8$» (100 campioni, 4 foglie): $0{,}0979$; (d) la radice (5 foglie): $0{,}1567$. Il calcolo di (a) per intero: Gini del nodo $=1-(\tfrac1{46})^2-(\tfrac{45}{46})^2=0{,}0425$, quindi $R(t)=\tfrac{46}{150}\cdot0{,}0425=0{,}0130$ (il peso $\tfrac{46}{150}$ misura quanta parte del training passa dal nodo); le foglie sono $[0,1,2]$ (3 campioni, Gini $1-\tfrac19-\tfrac49=\tfrac49$, $R=\tfrac3{150}\cdot\tfrac49=0{,}0089$) e $[0,0,43]$ (pura, $R=0$), quindi $R(T_t)=0{,}0089$; con $2$ foglie $\alpha_{\text{eff}}=\frac{0{,}0130-0{,}0089}{2-1}=0{,}0042$. Si pota per primo il nodo (a), con $\alpha_{\text{eff}}$ minimo ($0{,}0042$), poi si ricalcolano gli altri. (Nel notebook di laboratorio i valori $0{,}0042$, $0{,}0297$, $0{,}0979$ sono gli stessi; per la radice compare $0{,}1045$ perché il loro albero divide anche il nodo puro delle setosa e ha 7 foglie: $(0{,}6667-0{,}0397)/(7-1)=0{,}1045$.)

Vantaggi e svantaggi

• Pro: facilmente interpretabili (regole leggibili); non richiedono normalizzazione dei dati (le soglie su una variabile non dipendono dalla scala); classificazione quasi immediata; la parte costosa (l'addestramento) si fa una volta, offline; trattano classi multiple e variabili miste.
• Contro: sono classificatori ad alta varianza: piccole modifiche nei dati cambiano molto l'albero, quindi sono soggetti a overfitting e spesso generalizzano male.

La soluzione è considerare molti alberi diversi e combinarli: una foresta (Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →). L'importanza delle feature, calcolata dalla riduzione di impurità, è trattata anch'essa lì.

Codice

from sklearn.tree import DecisionTreeClassifier, export_text
tree = DecisionTreeClassifier(criterion="gini", max_depth=3, ccp_alpha=0.0, random_state=0)
tree.fit(X_train, y_train)
print(export_text(tree, feature_names=names))      # regole dell'albero
alphas = tree.cost_complexity_pruning_path(X_train, y_train).ccp_alphas   # alpha di potatura

L'implementazione da zero nei laboratori usa classi con impurity() e split_impurity() e un nodo con (feature, soglia, predizione); nodi indicizzati come $2i+1$ e $2i+2$ (la stessa numerazione per livelli con cui si memorizza un heapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap → in un array: i figli del nodo $i$ stanno a $2i+1$ e $2i+2$, senza puntatori).

Costi (con gli strumenti di Dati e Algoritmi). Un albero di decisione è un albero binarioAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari → (in CART) e predire significa percorrere un cammino dalla radice a una foglia (Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →): il costo è $O(h)$, con $h$ l'altezza, che è al più la profondità massima scelta. Non dipende da $n$, a differenza del k-NN (Classificazione e k-nearest neighborsNella classificazione l'uscita $y$ è una categoria (con $C$ classi; $C=2$ è il caso binario). Il classificatore più semplice è il k-nearest neighbors: una nuova osservazione prende la classe più frequente (voto di maggioranza) tra i suoi $k$ vicini più prossimi nel training, con distanza euclidea $\sqrt{\sum(A_i-B_i)^2}$ o di Manhattan $\sum|A_i-B_i|$ (per la regressione si fa la media dei vicini). $k$ è un iperparametro: $k$ piccolo dà bordi frastagliati e overfitting, $k$ grande underfitting. È un metodo basato su istanze e «pigro» (nessun addestramento, costo alla predizione), sensibile a scala e feature irrilevanti e alla maledizione della dimensionalità; gli ingressi categorici si codificano con one-hot. Approfondimento: non nel programma di Telecomunicazioni.Classificazione e k-nearest neighbors →). Per addestrare, a ogni livello si guardano al più tutti gli $n$ campioni; per ogni feature numerica si ordinano i valori ($O(n\log n)$, Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →) e si calcola l'impurità di ogni soglia con somme cumulate; con $p$ feature e profondità $h$ il costo è $O(h\,p\,n\log n)$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →). Un albero perfettamente bilanciato con $h$ livelli ha fino a $2^h$ foglie, perciò con $h=3$ al più $8$ regioni. Nota: nel codice del laboratorio il criterio «minimizza» (Gini, entropia) o «massimizza» (guadagno d'informazione).

Errori tipici

• Dimenticare che il guadagno d'informazione si massimizza mentre Gini e entropia dei figli si minimizzano.
• Calcolare la media delle entropie dei figli senza pesare per la dimensione dei sottoinsiemi.
• Scegliere la profondità guardando l'accuracy sul training (sale sempre).
• Pensare che serva standardizzare le feature: per gli alberi non serve.
• Usare un albero molto profondo sperando in una buona generalizzazione: varianza alta.