FormularioMachine Learning: definizioni, teoremi e formule delle note, in ordine di capitolo

In questa pagina 8

1. Introduzione e dati

Introduzione al machine learning

Definizione (machine learning). Il machine learning è l'insieme dei metodi con cui un programma ricava dai dati la regola che collega ingressi e uscite, invece di riceverla scritta da un programmatore.

Esempio. Per riconoscere lo spam si potrebbe scrivere a mano la regola «se compare la parola premio allora è spam» (approccio basato su regole) oppure mostrare al modello migliaia di messaggi già etichettati e lasciare che sia lui a trovare quali parole e combinazioni contano (approccio guidato dai dati, cioè ML). Oggi quasi tutte le tecnologie di AI importanti sono di questo secondo tipo.

Definizione (apprendimento supervisionato). Setup: osservazione dell'ambiente. Dati: coppie $(x,y)$ , cioè un ingresso $x$ e l'uscita desiderata $y$ (l'etichetta, label). Compito: imparare una funzione che dagli ingressi $x$ produca le uscite $y$ .

Esempio. $x$ = metri quadri di un appartamento, $y$ = prezzo. I dati sono coppie (metri quadri, prezzo) di appartamenti venduti; il compito è prevedere il prezzo di un appartamento nuovo.

Definizione (apprendimento non supervisionato). Dati: solo gli ingressi $x$ , senza etichette. Compito: imparare strutture (pattern) nei dati di ingresso, per esempio gruppi di osservazioni simili.

Esempio. Si hanno gli acquisti di 10 000 clienti, senza alcuna etichetta. Un algoritmo di clustering (Clustering e k-means) può dividerli in gruppi con abitudini simili, senza che nessuno abbia detto quali gruppi esistano.

Definizione (apprendimento per rinforzo). Setup: interazione con l'ambiente. Dati: triplette (stato, azione, ricompensa). Compito: imparare una politica (policy) che massimizzi la ricompensa totale.

Esempio. Un robot che impara a camminare: lo stato è la posizione dei suoi giunti, l'azione è il movimento, la ricompensa è la distanza percorsa senza cadere. Il rinforzo non si approfondisce in questo corso.

Formula (regressione lineare con una variabile). $\hat y = b + w\,x$ , con $w$ pendenza e $b$ valore in $x=0$ .

Esempio. Con $b=50\,000$ € e $w=2\,000$ € al metro quadro, un appartamento di $80\ \text{m}^2$ ha predizione $\hat y = 50\,000 + 2\,000\cdot 80 = 210\,000$ €.

Statistica per il machine learning

Definizione (matrice di progetto o design matrix). I dati tabulari si organizzano in una matrice $X$ con $n$ righe e $p$ colonne:

ogni riga è un'osservazione (o campione, sample): una volta in cui il fenomeno da descrivere compare nei dati storici, quindi $n$ è il numero di osservazioni;

ogni colonna è un attributo (o variabile, o feature): una grandezza potenzialmente legata al fenomeno, quindi $p$ è il numero di variabili.

Esempio. Per prevedere il prezzo delle case, ogni riga è una casa venduta e le colonne sono metri quadri, numero di stanze, anno di costruzione: con 1 000 case e 3 attributi, $X$ ha $n=1000$ righe e $p=3$ colonne.

Definizione (momento di ordine $k$ ). Per una variabile aleatoria $X$ il momento di ordine $k$ è $E[X^k]$ (valore atteso: Valore atteso; momenti e varianza: Varianza e momenti): $\mu_k=\int_{-\infty}^{+\infty}x^k f(x)\,dx\ \ \text{(continua)},\qquad \mu_k=\sum_x x^k\,P(X=x)\ \ \text{(discreta)}.$

Formula (indicatori teorici).

Media: $E[X]=\mu$ (tendenza centrale).

Varianza: $\operatorname{Var}(X)=E[(X-\mu)^2]=\sigma^2$ (dispersione).

Asimmetria (skewness): $\operatorname{Skew}(X)=E[(X-\mu)^3]/\sigma^3$ .

Curtosi (kurtosis): $\operatorname{Kurt}(X)=E[(X-\mu)^4]/\sigma^4$ .

Formula (momenti campionari). Con $X_1,\dots,X_n$ i valori osservati: $\hat\mu_k=\frac1n\sum_{i=1}^nX_i^k,\qquad \mu=\frac{1}{n}\sum_i X_i,\qquad \sigma^2=\frac{1}{n}\sum_i(X_i-\mu)^2,$ $\operatorname{Skew}=\frac{\sum_i(X_i-\mu)^3}{n\,\sigma^3},\qquad \operatorname{Kurt}=\frac{\sum_i(X_i-\mu)^4}{n\,\sigma^4}.$

Esempio. $X=[10,15,20,25,30,35,40,45,50,55]$ , $n=10$ . Media: $\mu=325/10=32{,}5$ . Scarti dalla media: $-22{,}5,\,-17{,}5,\,\dots,\,22{,}5$ .

Definizione (quartili). Dividono i dati ordinati in quattro parti con lo stesso numero di osservazioni:

$Q_1$ (25%): valore sotto cui cade il 25% dei dati;

$Q_2$ (50%): la mediana, che divide i dati in due metà;

$Q_3$ (75%): valore sotto cui cade il 75% dei dati;

scarto interquartile $\mathrm{IQR}=Q_3-Q_1$ : ampiezza dell'intervallo che contiene il 50% centrale dei dati.

Esempio. Con $n=11$ dati $X=[5,10,\dots,55]$ : $Q_1=15$ , $Q_2=30$ , $Q_3=45$ , $\mathrm{IQR}=45-15=30$ .

Definizione (moda). Il valore che compare più spesso nei dati. È importante per le variabili categoriche, per le quali media e mediana non hanno senso.

Esempio. $X=[1,2,2,3,4,7,9,10,10,10,12]$ : media $=70/11\approx6{,}36$ , mediana $=7$ , moda $=10$ .

Formula (z-score). $z=\dfrac{x-\mu}{\sigma}$ , con $\mu$ e $\sigma$ media e deviazione standard della variabile (la stessa standardizzazione delle variabili gaussiane: Distribuzione gaussiana (normale)).

Esempio (dalle slide). $X=[10,12,14,16,18]$ : $\mu=14$ , $\sigma=3{,}162$ (con divisore $n-1$ , come fa pandas); gli z-score sono $-1{,}265,\ -0{,}632,\ 0,\ 0{,}632,\ 1{,}265$ . Con il divisore $n$ si avrebbe $\sigma=2{,}828$ e valori $-1{,}414,\dots,1{,}414$ : le slide usano $n-1$ .

Grafico interattivo: Normale standard e distribuzione più appuntita con la stessa media e varianza: la seconda ha curtosi maggiore di 3 (code più pesanti e picco più alto)

Correlazione e visualizzazione dei dati

Definizione (correlazione). Misura statistica del grado con cui due variabili si muovono una rispetto all'altra: ne quantifica forza e direzione. I suoi valori stanno tra $-1$ e $1$ :

$+1$ : correlazione positiva perfetta (se una variabile cresce, l'altra cresce in proporzione);

$0$ : nessuna correlazione (nessuna relazione, almeno lineare);

$-1$ : correlazione negativa perfetta (se una cresce, l'altra decresce in proporzione).

Formula (coefficiente di correlazione di Pearson). Per due variabili $X,Y$ osservate su $n$ campioni, con medie $\bar X,\bar Y$ : $r=\frac{\sum_{i=1}^n (X_i-\bar X)(Y_i-\bar Y)}{\sqrt{\sum_{i=1}^n (X_i-\bar X)^2}\ \cdot\ \sqrt{\sum_{i=1}^n (Y_i-\bar Y)^2}}.$ Il numeratore rappresenta la covarianza (a meno del fattore $1/n$ ) tra $X$ e $Y$ (Covarianza e coefficiente di correlazione); il denominatore è il prodotto delle deviazioni standard (a meno degli stessi fattori). Misura la relazione lineare.

Esempio. $X=[1,0,2]$ , $Y=[2,-1,5]$ . Medie: $\bar X=1$ , $\bar Y=2$ . Scarti: $X_i-\bar X=[0,-1,1]$ , $Y_i-\bar Y=[0,-3,3]$ . Numeratore: $0\cdot0+(-1)(-3)+1\cdot3=6$ . Somme dei quadrati: $0+1+1=2$ e $0+9+9=18$ . Allora $r=\dfrac{6}{\sqrt2\,\sqrt{18}}=\dfrac{6}{\sqrt{36}}=1$ .

Grafico interattivo: X = [0, 1, 2, 5] e Y = [4, 1, 3, 0]: i quattro punti e la retta dei minimi quadrati y = 3,29 − 0,64 x, con r ≈ −0,76 (relazione decrescente, non perfetta)

Analisi delle componenti principali (PCA)

Definizione (autovalore di una componente). $\lambda_k=\dfrac{SS(\text{distances per PC}_k)}{n-1}$ , cioè la varianza dei dati proiettati sulla componente $k$ . La radice quadrata di $SS(\text{distances})$ si chiama valore singolare. In forma matriciale $\lambda_k$ è l'autovalore della matrice di covarianza.

Formula (varianza spiegata). $\text{frazione spiegata dalla PC}_k=\dfrac{\lambda_k}{\sum_{j=1}^p\lambda_j}.$ La frazione cumulata fino alla componente $k$ si calcola sommando.

Esempio (dati dei topi, due geni). La matrice di covarianza dei dati è $S=\begin{pmatrix}18{,}97&6{,}49\\6{,}49&3{,}13\end{pmatrix}$ . Gli autovalori sono le radici di $\lambda^2-\operatorname{tr}(S)\lambda+\det S=0$ , cioè $\lambda^2-22{,}09\lambda+17{,}23=0$ , e valgono $\lambda_1=21{,}28$ e $\lambda_2=0{,}81$ . PC1 spiega $21{,}28/22{,}09\approx96{,}3\%$ della varianza, PC2 il $3{,}7\%$ . L'autovettore di $\lambda_1$ risolve $(18{,}97-21{,}28)v_1+6{,}49\,v_2=0$ , cioè $v_2=0{,}357\,v_1$ : normalizzato dà $(0{,}942;\,0{,}336)$ .

Grafico interattivo: Dati dei topi (geni 1 e 2) centrati: PC1 (rossa) è la retta che passa più vicino ai punti e lungo cui la varianza è massima (96 % del totale), PC2 (tratteggiata) è perpendicolare

Teorema (perché gli autovettori). Tra tutti i vettori unitari $u$ ( $u^Tu=1$ ), la varianza dei dati proiettati $Z=X_cu$ è $\operatorname{Var}(Z)=u^TSu$ , ed è massima quando $u$ è l'autovettore di $S$ con autovalore più grande; il massimo vale $\lambda_1$ .

Esempio. Per $S=\begin{pmatrix}2&0\\0&1\end{pmatrix}$ e $u=(\cos\theta,\sin\theta)$ : $u^TSu=2\cos^2\theta+\sin^2\theta=1+\cos^2\theta$ , massimo $2=\lambda_1$ per $\theta=0$ (l'autovettore $(1,0)$ ).

2. Regressione

Regressione lineare

Definizione (compito supervisionato). Si dispone di dati storici $(x^{(i)},y^{(i)})$ con $i=1,\dots,n$ : $x$ è l'ingresso (input, il vettore delle feature $x=[x_1,\dots,x_p]$ ) e $y$ l'uscita (output, la risposta da prevedere). L'obiettivo è imparare una funzione $F(x)$ che, ricevendo un $x$ nuovo, fornisca una stima di $y$ .

Formula (modello lineare). $F_\beta(x)=\beta_0+\beta_1x_1+\beta_2x_2+\dots+\beta_px_p$ . I numeri $\beta_0,\dots,\beta_p$ sono i parametri (o coefficienti); $\beta_0$ è l'intercetta, il coefficiente della costante.

Esempio (dalle slide). Prezzo (in USD) $=150\,000+10\,000\cdot[\text{n. bagni}]+\dots-1\,000\cdot[\text{età della casa}]$ : ogni bagno in più aumenta la stima di $10\,000$ USD e ogni anno di età la riduce di $1\,000$ USD, a parità delle altre variabili. Il coefficiente $\beta_j$ dice di quanto cambia la stima per un'unità in più della feature $x_j$ , tenendo ferme le altre.

Formula (MSE e RMSE). $\mathrm{MSE}=\frac1n\sum_{i=1}^n\big[y^{(i)}-F_\beta(x^{(i)})\big]^2,\qquad \mathrm{RMSE}=\sqrt{\mathrm{MSE}}.$ $\mathrm{MSE}$ è l'errore quadratico medio (mean squared error); la radice $\mathrm{RMSE}$ ha la stessa unità di $y$ ed è di più facile lettura.

Esempio. Previsioni $[2{,}3;\,3{,}1;\,3{,}9;\,4{,}7]$ per valori veri $[2;\,3;\,5;\,4]$ : errori $[-0{,}3;\,-0{,}1;\,1{,}1;\,-0{,}7]$ , quadrati $[0{,}09;\,0{,}01;\,1{,}21;\,0{,}49]$ con somma $1{,}8$ , $\mathrm{MSE}=1{,}8/4=0{,}45$ , $\mathrm{RMSE}=\sqrt{0{,}45}\approx0{,}671$ .

Proprietà (convessità). Nei modelli di regressione lineare la funzione di costo è convessa nello spazio dei parametri: il segmento che unisce due punti qualunque del grafico non sta mai sotto il grafico. Quindi non ci sono minimi locali spuri: c'è un unico insieme di parametri ottimi, indicato con $\hat\beta$ .

Grafico interattivo: MSE in funzione della pendenza β₁ (con β₀ = 1,5 fisso) per i quattro punti (1;2), (2;3), (3;5), (4;4): è una parabola convessa con minimo 0,45 in β₁ = 0,8

Teorema (soluzione dei minimi quadrati ordinari). Se $X^TX$ è invertibile, $\hat\beta=(X^TX)^{-1}X^Ty.$

Esempio completo. Dati $x=[1,2,3,4]$ , $y=[2,3,5,4]$ . La matrice con la colonna di uni è $X=\begin{bmatrix}1&1\\1&2\\1&3\\1&4\end{bmatrix}$ . Allora $X^TX=\begin{bmatrix}4&10\\10&30\end{bmatrix},\qquad X^Ty=\begin{bmatrix}2+3+5+4\\ 2+6+15+16\end{bmatrix}=\begin{bmatrix}14\\39\end{bmatrix}.$ Il determinante è $4\cdot30-10\cdot10=20$ e l'inversa è $\frac1{20}\begin{bmatrix}30&-10\\-10&4\end{bmatrix}$ . Perciò $\hat\beta=\frac1{20}\begin{bmatrix}30\cdot14-10\cdot39\\-10\cdot14+4\cdot39\end{bmatrix}=\frac1{20}\begin{bmatrix}30\\16\end{bmatrix}=\begin{bmatrix}1{,}5\\0{,}8\end{bmatrix}.$ La retta è $\hat y=1{,}5+0{,}8x$ , con previsioni $2{,}3;\ 3{,}1;\ 3{,}9;\ 4{,}7$ ( $\mathrm{MSE}=0{,}45$ come sopra).

Grafico interattivo: I quattro punti e la retta dei minimi quadrati ŷ = 1,5 + 0,8 x: i segmenti sono i residui (−0,3; −0,1; +1,1; −0,7), la cui somma dei quadrati 1,8 è la minima possibile

Formula (coefficiente di determinazione). $R^2=1-\frac{SS_{res}}{SS_{tot}},\qquad SS_{res}=\sum_i(y_i-\hat y_i)^2,\qquad SS_{tot}=\sum_i(y_i-\bar y)^2.$ $SS_{res}$ (somma dei quadrati dei residui) misura l'errore del modello; $SS_{tot}$ misura la variabilità totale di $y$ rispetto alla media, cioè l'errore di un «modello» che prevede sempre $\bar y$ .

Esempio. Per $y=[2,3,5,4]$ : $SS_{tot}=(-1{,}5)^2+(-0{,}5)^2+1{,}5^2+0{,}5^2=5$ e $SS_{res}=1{,}8$ , quindi $R^2=1-1{,}8/5=0{,}64$ : la retta spiega il $64\%$ della variabilità di $y$ .

Overfitting, ridge regression e cross-validation

Definizione (K-fold cross-validation). Si mescolano i dati e si dividono in $k$ parti (fold) di uguale dimensione. Per $i=1,\dots,k$ : si usa il fold $i$ come insieme di valutazione e i restanti $k-1$ per addestrare il modello; si calcola la metrica (per esempio l'MSE) $\mathrm{MSE}_i$ sul fold $i$ . La stima finale è la media $\overline{\mathrm{MSE}}=\frac1k\sum_{i=1}^k\mathrm{MSE}_i$ .

Esempio. Con $n=20$ dati e $k=5$ si formano 5 fold da 4 dati (dati 1-4, 5-8, 9-12, 13-16, 17-20 dopo il mescolamento): a ogni giro si addestra su 16 dati e si valuta su 4. Per il polinomio quadratico dell'esempio del laboratorio gli MSE dei 5 fold sono $0{,}0106;\ 0{,}0219;\ 0{,}0204;\ 0{,}0194;\ 0{,}0243$ e la media vale $\frac{0{,}0106+0{,}0219+0{,}0204+0{,}0194+0{,}0243}{5}=\frac{0{,}0966}{5}=0{,}0193$ .

Definizione (MCCV). Si ripete $k$ volte: divisione casuale del dataset in training e test, con una frazione fissata $q$ di dati nel test; addestramento; calcolo di $\mathrm{MSE}_i$ . Si media: $\frac1k\sum_i\mathrm{MSE}_i$ . Le scelte di progetto sono due: il numero di ripetizioni $k$ e la quota di test $q$ .

Definizione (bias). L'incapacità di un metodo di cogliere la vera relazione tra ingresso e uscita. Un modello troppo semplice (la retta quando i dati seguono una parabola) ha bias alto e non la catturerà mai, per quanti dati si abbiano.

Definizione (varianza). La sensibilità del modello ai dati di addestramento: se, cambiando il campione di training, le previsioni cambiano molto, la varianza è alta. Un modello molto flessibile (polinomio con 20 coefficienti) ha bias basso sul training ma varianza alta.

Teorema (decomposizione bias-varianza). Sia $y=f(x)+\varepsilon$ con rumore $E[\varepsilon]=0$ , $\operatorname{Var}(\varepsilon)=\sigma^2$ , indipendente dal training. Per un punto fissato $x$ e un modello $\hat f$ addestrato su un campione casuale: $E\big[(y-\hat f(x))^2\big]=\underbrace{\big(f(x)-E[\hat f(x)]\big)^2}_{\text{bias}^2}+\underbrace{E\big[(\hat f(x)-E[\hat f(x)])^2\big]}_{\text{varianza}}+\sigma^2.$

Esempio. Se per un punto $f=3$ , la media delle previsioni su molti campioni è $E\hat f=2{,}5$ con varianza $0{,}04$ e $\sigma^2=0{,}01$ , l'errore quadratico atteso è $(3-2{,}5)^2+0{,}04+0{,}01=0{,}25+0{,}04+0{,}01=0{,}30$ .

Grafico interattivo: Andamento qualitativo al crescere della complessità del modello: l'errore sul training scende sempre, quello su dati nuovi scende e poi risale (overfitting); il minimo (circa a 6) è il buon compromesso tra bias e varianza

Definizione (regolarizzazione). Tecnica per prevenire l'overfitting aggiungendo alla funzione di costo un termine di penalità sulla complessità del modello: si minimizza $J=\sum_{i=1}^n\big[y_i-\hat y_i\big]^2+\gamma\,R,$ dove $R$ misura la complessità e $\gamma\ge0$ è il parametro di regolarizzazione, un iperparametro (un valore che si sceglie prima dell'addestramento e che non è appreso dai dati). Se $\gamma=0$ non c'è regolarizzazione; per $\gamma$ grande conta quasi solo la penalità.

Definizione (ridge regression, penalità $L_2$ ). Con $R=\sum_{j=1}^p\beta_j^2$ (somma dei quadrati dei coefficienti, senza $\beta_0$ ) si minimizza $J(\beta)=\sum_{i=1}^n\big(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij}\big)^2+\lambda\sum_{j=1}^p\beta_j^2 .$

Formula (ridge regression). $\hat\beta_{\text{ridge}}=(X^TX+\lambda\tilde I)^{-1}X^Ty$ . Per $\lambda=0$ coincide con l'OLS; al crescere di $\lambda$ i coefficienti si riducono (shrinkage) verso zero.

Esempio (una sola feature). Dati $x=[-1{,}5;-0{,}5;0{,}5;1{,}5]$ (centrata) e $y_c=[-1{,}5;-0{,}5;1{,}5;0{,}5]$ ( $y=[2,3,5,4]$ meno la media $3{,}5$ ): $X^TX=2{,}25+0{,}25+0{,}25+2{,}25=5$ e $X^Ty_c=2{,}25+0{,}25+0{,}75+0{,}75=4$ . Con $\lambda=0$ : $\hat\beta=4/5=0{,}8$ (l'OLS). Con $\lambda=1$ : $4/(5+1)=0{,}667$ ; con $\lambda=5$ : $4/10=0{,}4$ ; con $\lambda=20$ : $4/25=0{,}16$ ; per $\lambda\to\infty$ : $\hat\beta\to0$ . Il trace plot (coefficienti in funzione di $\lambda$ ) mostra questa discesa.

Grafico interattivo: Trace plot nel caso di una feature: il coefficiente ridge 4/(5+λ) parte dal valore OLS 0,8 per λ = 0 e tende a 0 al crescere di λ (shrinkage)

LASSO e discesa del gradiente

Definizione (LASSO). Least Absolute Shrinkage and Selection Operator: penalità $L_1$ , somma dei valori assoluti dei coefficienti, $J(\beta)=\sum_{i=1}^n\Big(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij}\Big)^2+\lambda\sum_{j=1}^p|\beta_j|,$ con $\beta_0$ non penalizzato (come nella ridge) e feature standardizzate (Statistica per il machine learning). In forma matriciale, con $X$ comprensiva della colonna di uni: $J(\beta)=\lVert y-X\beta\rVert^2+\lambda\sum_{j\ge1}|\beta_j|$ .

Esempio. Con $\beta=(\beta_0,\beta_1,\beta_2)=(3;\,2;\,-0{,}5)$ e $\lambda=4$ la penalità vale $4\,(|2|+|-0{,}5|)=4\cdot2{,}5=10$ , mentre la ridge con lo stesso $\lambda$ varrebbe $4\,(4+0{,}25)=17$ (il valore assoluto penalizza di più i coefficienti piccoli, il quadrato quelli grandi).

Formula (discesa del gradiente, gradient descent). Partendo da un $W$ iniziale, si ripete $W\leftarrow W-\eta\,\nabla J(W),$ dove $\eta>0$ è il passo (learning rate), fino a convergenza (per esempio finché $\lVert W_{\text{nuovo}}-W\rVert<\text{tol}$ o dopo un numero massimo di iterazioni).

Esempio in una variabile. $J(w)=w^2$ ha gradiente $2w$ e minimo in $w=0$ . L'aggiornamento è $w\leftarrow w-\eta\cdot2w=(1-2\eta)w$ . Partendo da $w_0=4$ :

Grafico interattivo: Discesa del gradiente su J(w) = w² partendo da w = 4: con η = 0,1 si scende lentamente verso il minimo, con η = 1,1 i passi saltano da un lato all'altro della parabola e si allontanano

Formula (subgradiente del LASSO). $\nabla_\beta J=2X^T(X\beta-y)+\lambda\begin{bmatrix}0\\ \operatorname{sign}(\beta_1)\\ \vdots\\ \operatorname{sign}(\beta_p)\end{bmatrix},$ con $0$ al posto di $\operatorname{sign}(\beta_0)$ perché l'intercetta non si penalizza.

Esempio. Con $\lambda=1$ , $\beta=(0{,}5;\ -2;\ 0)$ e componente dell'errore $2X^T(X\beta-y)=(1;\ 3;\ -4)$ : il subgradiente è $(1+0;\ 3+1\cdot(-1);\ -4+1\cdot0)=(1;\ 2;\ -4)$ .

3. Classificazione

Classificazione e k-nearest neighbors

Definizione (classificazione). Problema supervisionato in cui l'uscita $y$ è una variabile categorica: ogni osservazione appartiene a una di $C$ classi. Se $C=2$ la classificazione è binaria (per esempio spam o non spam); se $C>2$ è multiclasse (per esempio $C=3$ per le specie di iris: setosa, versicolor, virginica).

Esempio. Iris: ingressi $x$ = lunghezza e larghezza di sepali e petali; uscita $y\in\{\text{setosa},\text{versicolor},\text{virginica}\}$ . Un caso estremo è Shazam: riconoscere una canzone da 3-4 secondi di audio, con $C\approx10^8$ classi; la soluzione è diventata possibile grazie a un forte lavoro di feature engineering (un'«impronta digitale» $x$ del segnale).

Definizione (k-NN). «Una nuova osservazione viene assegnata alla classe più frequente tra i suoi $k$ vicini più prossimi nel training.» Algoritmo:

si sceglie il numero di vicini $k$ ;

si calcola la distanza tra il nuovo punto e tutti i punti del training (di solito la distanza euclidea);

si selezionano i $k$ punti più vicini;

si predice: per la classificazione la classe più frequente tra i $k$ (voto di maggioranza); per la regressione la media (o la media pesata) dei valori $y$ dei $k$ vicini.

Esempio. Si abbiano 8 punti nel piano: classe R in $(0{,}5;\,0)$ , $(0;\,0{,}8)$ , $(3;\,3)$ , $(-3;\,2)$ ; classe B in $(-1;\,0)$ , $(0;\,-1{,}2)$ , $(1{,}3;\,0)$ , $(-2;\,-3)$ . Il nuovo punto è $q=(0,0)$ . Le distanze euclidee dai primi cinque punti più vicini sono: $(0{,}5;0)\to0{,}5$ (R), $(0;0{,}8)\to0{,}8$ (R), $(-1;0)\to1$ (B), $(0;-1{,}2)\to1{,}2$ (B), $(1{,}3;0)\to1{,}3$ (B). Quindi: con $k=1$ il vicino è R e $q$ è R; con $k=3$ i vicini sono R, R, B e vince R (2 voti contro 1); con $k=5$ sono R, R, B, B, B e vince B (3 contro 2). Il risultato dipende da $k$ .

Grafico interattivo: Esempio con q = (0, 0): i cerchi tratteggiati contengono i 3 e i 5 vicini più prossimi. Con k = 1 e k = 3 vince la classe rossa (R), con k = 5 la classe blu (B)

Definizione (curse of dimensionality). L'insieme dei problemi che compaiono in spazi con molte dimensioni: aumentando il numero di feature i dati si comportano in modo inatteso e molti metodi diventano meno efficienti.

Regressione logistica e softmax

Definizione (funzione logistica o sigmoide). $\displaystyle\sigma(z)=\frac1{1+e^{-z}}$ (esponenziale: Esponenziale e logaritmo). Ha valori in $(0,1)$ , è crescente, vale $0{,}5$ in $z=0$ , tende a $0$ per $z\to-\infty$ e a $1$ per $z\to+\infty$ .

Esempio (dalle slide). $\sigma(-10)=4{,}5\cdot10^{-5}\approx0$ ; $\sigma(0)=0{,}5$ ; $\sigma(5)=0{,}9933\approx0{,}99$ . Inoltre $\sigma(2)=0{,}881$ e $\sigma(-2)=0{,}119=1-\sigma(2)$ : vale la simmetria $\sigma(-z)=1-\sigma(z)$ .

Grafico interattivo: Sigmoide σ(z) = 1/(1 + e^(−z)): trasforma qualunque numero reale in un valore in (0, 1); σ(0) = 0,5 è la soglia di decisione, σ(5) = 0,99

Definizione (regressione logistica). Si prende la combinazione lineare delle feature $x^T\beta=\beta_0+\beta_1x_1+\dots+\beta_px_p$ (come nella Regressione lineare, con la colonna di uni) e la si trasforma con la sigmoide: $\hat y_i=\sigma(x_i^T\beta)=\frac1{1+e^{-x_i^T\beta}},\qquad P(y_i=1\mid x_i)=\sigma(x_i^T\beta),\quad P(y_i=0\mid x_i)=1-\sigma(x_i^T\beta).$ La classe predetta è $1$ se $\sigma(x_i^T\beta)\ge0{,}5$ , altrimenti $0$ .

Esempio. Se $\beta=(-3;\,1;\,1)$ e $x=(2;\,2)$ : $z=-3+2+2=1$ , $\hat y=\sigma(1)=0{,}731$ : classe $1$ con probabilità $73\%$ . Per $x=(0;\,1)$ : $z=-2$ , $\hat y=0{,}119$ , classe $0$ .

Grafico interattivo: Con β = (−3; 1; 1) il bordo di decisione è la retta x₁ + x₂ = 3 (probabilità 0,5); le rette parallele x₁ + x₂ = 3 ± 2,2 sono le curve di probabilità 0,9 e 0,1: la probabilità varia solo nella direzione perpendicolare al bordo

Definizione (log-verosimiglianza negativa o cross-entropia binaria). $\mathcal L(\beta)=-\sum_{i=1}^n\Big[y_i\log\sigma(x_i^T\beta)+(1-y_i)\log\big(1-\sigma(x_i^T\beta)\big)\Big].$ Spesso si usa la media $\frac1n\mathcal L$ .

Esempio. Per $y=1$ e $\hat y=0{,}9$ : costo $-\ln0{,}9=0{,}105$ ; per $\hat y=0{,}1$ : $-\ln0{,}1=2{,}303$ ; per $\hat y=0{,}5$ (modello indeciso): $\ln2=0{,}693$ . Con $\beta=0$ tutte le previsioni valgono $0{,}5$ e la media della perdita è $\ln2=0{,}693$ qualunque siano i dati.

Grafico interattivo: Costo per un esempio con y = 1 in funzione di z = xᵀβ: l'errore quadratico (1 − σ(z))² si appiattisce a sinistra (gradiente quasi nullo anche se l'errore è massimo), la log-verosimiglianza −log σ(z) = log(1 + e^(−z)) cresce linearmente per z molto negativo e fornisce sempre un gradiente utile

Formula (gradiente della log-verosimiglianza negativa). $\nabla_\beta\mathcal L=X^T(\hat y-y),\qquad\text{oppure, con la media,}\quad\nabla_\beta\Big(\tfrac1n\mathcal L\Big)=\frac{X^T(\hat y-y)}{n}.$ Qui $X$ include la colonna di uni, $\hat y=\sigma(X\beta)$ e $y$ sono vettori $n\times1$ .

Esempio completo. Dati $x=[1,2,3,4,5,6]$ , $y=[0,0,1,0,1,1]$ , $X=\begin{bmatrix}1&1\\\vdots&\vdots\\1&6\end{bmatrix}$ . Partendo da $\beta=(0,0)$ tutte le previsioni sono $0{,}5$ e l'errore $\hat y-y=[0{,}5;0{,}5;-0{,}5;0{,}5;-0{,}5;-0{,}5]$ . Gradiente: la prima componente è $\frac16(0{,}5+0{,}5-0{,}5+0{,}5-0{,}5-0{,}5)=0$ ; la seconda è $\frac16(0{,}5\cdot1+0{,}5\cdot2-0{,}5\cdot3+0{,}5\cdot4-0{,}5\cdot5-0{,}5\cdot6)=\frac16(-3{,}5)=-0{,}583$ . Con $\eta=0{,}1$ : $\beta=(0;\ 0{,}0583)$ . Le previsioni diventano $\sigma(0{,}0583x)=0{,}515;\,0{,}529;\,\dots;\,0{,}587$ ; secondo gradiente $(0{,}0507;\,-0{,}364)$ , quindi $\beta=(-0{,}0051;\ 0{,}0947)$ ; terzo passo $\beta=(-0{,}0131;\ 0{,}1182)$ . A convergenza (verificata con il metodo di Newton e con scikit-learn senza penalità) $\beta\approx(-4{,}249;\ 1{,}214)$ , con perdita media $0{,}413$ (era $0{,}693$ ): il bordo $-4{,}249+1{,}214x=0$ cade in $x=3{,}5$ e le probabilità previste sono $0{,}046;\ 0{,}139;\ 0{,}353;\ 0{,}647;\ 0{,}861;\ 0{,}954$ .

Grafico interattivo: Sei dati (y = 0 per x = 1, 2, 4 e y = 1 per x = 3, 5, 6) e curva logistica σ(−4,249 + 1,214 x): supera 0,5 in x = 3,5, il bordo di decisione

Metriche di classificazione

Definizione (matrice di confusione). Tabella che incrocia la classe vera (actual, righe) con la classe prevista (predicted, colonne). Ogni cella conta quante osservazioni hanno quella combinazione; la diagonale contiene le previsioni corrette.

Esempio. Con etichette vere $[1,1,1,1,0,0,0,1,1,1]$ e previste $[1,1,1,1,0,0,1,0,0,0]$ : TP $=4$ (le prime quattro), TN $=2$ (posizioni 5 e 6), FP $=1$ (posizione 7: vero $0$ , previsto $1$ ), FN $=3$ (posizioni 8, 9, 10: vero $1$ , previsto $0$ ).

Formula (accuracy, specificità, precision, recall). $\text{accuracy}=\frac{TP+TN}{TP+TN+FP+FN},\qquad\text{specificità}=\frac{TN}{TN+FP},$ $\text{precision}=\frac{TP}{TP+FP},\qquad\text{recall (sensibilità, TPR)}=\frac{TP}{TP+FN}.$

Esempio (stessi dati). Accuracy $=\frac{4+2}{10}=0{,}6$ ; specificità $=\frac{2}{2+1}=0{,}667$ ; precision $=\frac{4}{4+1}=0{,}8$ ; recall $=\frac{4}{4+3}=0{,}571$ . Il modello è quindi affidabile quando dice «positivo» ( $0{,}8$ ) ma trova solo il $57\%$ dei positivi.

Definizione (curva ROC). Per ogni soglia $t$ (si predice positivo se punteggio $\ge t$ ) si calcolano il tasso di veri positivi $\text{TPR}=\frac{TP}{TP+FN}$ (la recall) e il tasso di falsi positivi $\text{FPR}=\frac{FP}{FP+TN}=1-\text{specificità}$ ; la curva ROC (receiver operating characteristic) riporta TPR contro FPR. L'area sotto la curva si chiama AUC: $1$ per un classificatore perfetto, $0{,}5$ per uno casuale (la diagonale). Un buon classificatore ha la curva vicina all'angolo in alto a sinistra.

Esempio. Etichette $y=[0,0,1,1]$ e punteggi $[0{,}1;\,0{,}4;\,0{,}35;\,0{,}8]$ . Soglia $0{,}8$ : previsti positivi solo il punteggio $0{,}8$ (vero positivo): TPR $=1/2$ , FPR $=0$ , punto $(0;\,0{,}5)$ . Soglia $0{,}4$ : positivi i punteggi $0{,}8$ e $0{,}4$ (quest'ultimo è un negativo): TP $=1$ , FP $=1$ , punto $(0{,}5;\,0{,}5)$ . Soglia $0{,}35$ : TP $=2$ , FP $=1$ , punto $(0{,}5;\,1)$ . Soglia $0{,}1$ : tutti positivi, punto $(1;\,1)$ . Area per rettangoli: $0{,}5\cdot0{,}5$ (tra $\text{FPR}=0$ e $0{,}5$ a quota $0{,}5$ ) $+\ 0{,}5\cdot1$ (tra $0{,}5$ e $1$ a quota $1$ ) $=0{,}25+0{,}5=0{,}75$ . Lo stesso valore si ottiene contando le coppie (positivo, negativo) in cui il positivo ha punteggio più alto: $3$ su $4$ $\Rightarrow0{,}75$ : l'AUC è la probabilità che un positivo preso a caso abbia un punteggio maggiore di un negativo preso a caso.

Grafico interattivo: Curva ROC dell'esempio (punteggi 0,1; 0,4; 0,35; 0,8 con classi 0, 0, 1, 1): passa per (0; 0,5), (0,5; 0,5), (0,5; 1); l'area è 0,75. La diagonale è il classificatore casuale (AUC = 0,5)

Halfspace e Perceptron

Definizione (halfspace). La classe di funzioni $h_{w,b}(x)=\operatorname{sign}\big(w^Tx+b\big),\qquad w\in\mathbb R^p,\ b\in\mathbb R,$ con $\operatorname{sign}(z)=+1$ per $z>0$ e $-1$ per $z<0$ (per $z=0$ si sceglie una convenzione, per esempio $+1$ ). Il vettore dei pesi $w$ e il bias $b$ sono i parametri.

Esempio. In $\mathbb R^2$ con $w=(1,1)$ e $b=-3$ : $h(x)=\operatorname{sign}(x_1+x_2-3)$ . Il punto $(2,3)$ dà $2+3-3=2>0\Rightarrow+1$ ; il punto $(0,1)$ dà $-2<0\Rightarrow-1$ .

Definizione (separabilità lineare). Un insieme di esempi $(x_i,y_i)$ è linearmente separabile se esistono $w,b$ con $y_i(w^Tx_i+b)>0$ per ogni $i$ , cioè se un halfspace li classifica tutti correttamente. Il margine di un tale piano è la distanza minima dei punti dal piano.

Definizione (algoritmo del Perceptron). Dati $(x_i,y_i)$ con $y_i\in\{-1,+1\}$ e $x_i$ aumentati con la costante $1$ :

si inizializza $w=0$ ;

si scorrono gli esempi; per un esempio sbagliato, cioè con $y_i\,w^Tx_i\le0$ , si aggiorna $w\leftarrow w+y_i\,x_i;$

si ripete finché in un'intera passata non ci sono errori.

Esempio completo (verificato). Dati $x_0=(2,3)$ con $y=+1$ , $x_1=(3,1)$ con $+1$ , $x_2=(0,1)$ con $-1$ , $x_3=(1,-1)$ con $-1$ ; con la costante $\tilde x=(x_1,x_2,1)$ e $w=(0,0,0)$ :

Grafico interattivo: Esempio del Perceptron: i punti positivi (rossi) e negativi (blu) e l'iperpiano finale x₁ + x₂ = 3, ottenuto con w = (1, 1) e b = −3; il vettore w (freccia) è perpendicolare alla retta e punta verso il semispazio positivo

Teorema (convergenza del Perceptron, Novikoff). Siano $\lVert x_i\rVert\le R$ per ogni $i$ , e sia $w^\ast$ con $\lVert w^\ast\rVert=1$ tale che $y_i\,w^{\ast T}x_i\ge\gamma>0$ per ogni $i$ (esiste un iperpiano con margine $\gamma$ ). Allora il Perceptron commette al più $(R/\gamma)^2$ errori (aggiornamenti) prima di classificare correttamente tutti gli esempi.

Esempio. Nell'esempio precedente $w^\ast=(1,1,-3)/\sqrt{11}$ ha margini $y_iw^{\ast T}\tilde x_i=[2,1,2,3]/\sqrt{11}$ , quindi $\gamma=1/\sqrt{11}=0{,}302$ ; il vettore aumentato più lungo è $(2,3,1)$ con $R=\sqrt{14}=3{,}74$ . Il teorema garantisce $t\le R^2/\gamma^2=14\cdot11=154$ errori; ne sono occorsi $5$ (il limite è largo ma vale per ogni ordine degli esempi).

4. Alberi e metodi ensemble

Alberi di decisione

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).

Definizione (entropia). (Logaritmo in base 2: 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.

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

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à).

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.

Grafico interattivo: Misure di impurità per due classi in funzione della proporzione p di una classe: entropia (normalizzata a 1 in p = 0,5), indice di Gini 2p(1 − p) e errore di classificazione min(p, 1 − p). Tutte valgono 0 per un nodo puro e sono massime per p = 0,5

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 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.

Esempio. $x=[1,2,3,4,5,6]$ , $y=[1,2,3,10,11,12]$ : varianza del genitore $20{,}92$ . 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.

Metodi ensemble - bagging, random forest e boosting

Definizione (bagging, bootstrap aggregating). Per costruire una foresta di $T$ alberi: per ciascun albero si estrae dal training di $n$ campioni un campione bootstrap, cioè $n$ campioni con rimpiazzo (ogni estratto è rimesso nell'urna prima della successiva); si addestra un albero su ciascun campione; per classificare si fa il voto di maggioranza (la moda), per la regressione la media.

Esempio di voto. Con $T=4$ alberi che predicono $[2,2,1,2]$ per un campione: classe $2$ con $3$ voti su $4$ , «confidenza» $0{,}75$ (la frazione di voti per la classe vincente). Nel laboratorio (dataset wine, $T=4$ alberi di profondità 2) l'accuracy sul test è $0{,}919$ e gli errori hanno confidenza $0{,}75$ o $0{,}5$ .

Definizione (random forest). Bagging in più: a ogni split di ogni albero, invece di valutare tutte le feature se ne estrae a caso un sottoinsieme (tipicamente $\sqrt p$ , con $p$ feature) e si sceglie lo split migliore solo tra queste (feature bagging).

Esempio (laboratorio, wine, feature bagging, $T=10$ ). Accuracy sul test $0{,}973$ con profondità 2 e 4 e $1{,}0$ con profondità 10; un solo albero di profondità 2-3 dava $0{,}946$ - $0{,}973$ .

Definizione (importanza di una feature). La misura di quanto una feature è utile alle previsioni, basata su quanto riduce l'impurità quando è usata per dividere. È un approccio «globale» di intelligenza artificiale spiegabile (Explainable AI (XAI)): dà informazioni sull'intero modello.

Esempio (iris, albero di profondità 3). Nodi: radice (150 campioni) con la larghezza del petalo: $\frac{150}{150}\cdot0{,}3333=0{,}3333$ ; nodo «larghezza $>0{,}8$ » (100 campioni, di nuovo larghezza): $\frac{100}{150}\cdot0{,}3897=0{,}2598$ ; due nodi con la lunghezza del petalo: $\frac{54}{150}\cdot0{,}0824=0{,}0297$ e $\frac{46}{150}\cdot0{,}0135=0{,}0042$ . Importanza grezza: larghezza $0{,}3333+0{,}2598=0{,}5931$ , lunghezza $0{,}0297+0{,}0042=0{,}0339$ ; normalizzando (divisione per la somma $0{,}6270$ ): $0{,}946$ e $0{,}054$ (coincide con feature_importances_ di scikit-learn). Sul dataset wine le feature più importanti sono proline, intensità del colore e flavonoidi.

Definizione (boosting). Si costruisce un modello forte (strong learner) combinando in sequenza molti modelli deboli (alberi con pochi split); ciascun nuovo modello cerca di correggere gli errori dei precedenti. La combinazione è una somma pesata.

Formula (gradient boosting). $F_0=\bar y$ , $\ r_i=y_i-F_{m}(x_i)$ , $\ F_{m+1}(x)=F_m(x)+\eta\,h_m(x)$ . Predizione finale: $F_M(x)=F_0+\eta\sum_mh_m(x)$ .

Esempio (dalle slide). Pesi osservati $y=[88,76,56,73,77,57]$ (altezza, colore preferito, genere come feature). Predizione iniziale: la media $71{,}2$ (esattamente $71{,}17$ ). Residui: $[16{,}8;\ 4{,}8;\ -15{,}2;\ 1{,}8;\ 5{,}8;\ -14{,}2]$ . Primo albero con 4 foglie: $\{-14{,}2,-15{,}2\}\to-14{,}7$ (media), $\{4{,}8\}\to4{,}8$ , $\{1{,}8,5{,}8\}\to3{,}8$ , $\{16{,}8\}\to16{,}8$ . Con $\eta=0{,}1$ la prima osservazione passa da $71{,}2$ a $71{,}2+0{,}1\cdot16{,}8=72{,}88$ e il nuovo residuo è $88-72{,}88=15{,}12$ (prima $16{,}8$ : ha fatto un «piccolo passo» nella direzione giusta). Residui dopo il primo albero: $[15{,}1;\ 4{,}3;\ -13{,}7;\ 1{,}4;\ 5{,}4;\ -12{,}7]$ . Secondo albero: foglie $-13{,}2$ , $4{,}3$ , $3{,}4$ , $15{,}1$ ; residui dopo il secondo: $[13{,}6;\ 3{,}9;\ -12{,}4;\ 1{,}1;\ 5{,}1;\ -11{,}4]$ . Ad ogni albero i residui si riducono (l'errore quadratico medio sul training passa da $129$ a circa $105$ e $85$ ).

Formula (similarity score, gain, output). Con $\lambda$ parametro di regolarizzazione: $\text{Similarity}=\frac{\big(\sum\text{residui}\big)^2}{N_{\text{residui}}+\lambda},\qquad \text{Gain}=\text{Sim}_{\text{sx}}+\text{Sim}_{\text{dx}}-\text{Sim}_{\text{genitore}},\qquad \text{Output}=\frac{\sum\text{residui}}{N_{\text{residui}}+\lambda}.$ Attenzione: nell'output la somma non è al quadrato.

Esempio (dalle slide). Dosaggi $[10,20,25,35]$ mg, efficacia $[-10,7,8,-7]$ , predizione iniziale $0{,}5$ : residui $[-10{,}5;\ 6{,}5;\ 7{,}5;\ -7{,}5]$ , con $\lambda=0$ . Radice: somma $=-4$ , similarità $\frac{(-4)^2}{4}=4$ . Soglia «dosaggio $<15$ »: sinistra $\{-10{,}5\}$ : $\frac{110{,}25}{1}=110{,}25$ ; destra $\{6{,}5;\ 7{,}5;\ -7{,}5\}$ (somma $6{,}5$ ): $\frac{42{,}25}{3}=14{,}08$ ; gain $=110{,}25+14{,}08-4=\mathbf{120{,}33}$ . Soglia « $<22{,}5$ »: sinistra $\{-10{,}5;\ 6{,}5\}$ (somma $-4$ ): $\frac{16}{2}=8$ ; destra $\{7{,}5;\ -7{,}5\}$ (somma 0): $0$ ; gain $=8+0-4=4$ . Soglia « $<30$ »: sinistra (somma $3{,}5$ ): $\frac{12{,}25}{3}=4{,}08$ ; destra $\{-7{,}5\}$ : $56{,}25$ ; gain $=4{,}08+56{,}25-4=56{,}33$ . Si sceglie «dosaggio $<15$ ». Il ramo destro $\{6{,}5;7{,}5;-7{,}5\}$ si divide ancora con « $<30$ »: sinistra $\{6{,}5;7{,}5\}$ (somma 14): $\frac{196}2=98$ ; destra $\{-7{,}5\}$ : $56{,}25$ ; gain $=98+56{,}25-14{,}08=140{,}17$ (profondità massima 2 nell'esempio; in pratica 6).

5. Apprendimento non supervisionato

Anomaly detection

Definizione (anomalia o outlier). «Un outlier è un'osservazione che si discosta così tanto dalle altre da destare il sospetto di essere stata generata da un meccanismo diverso» (Hawkins, 1980). In un dataset, per definizione, gli outlier dovrebbero essere pochi.

Esempio. Un sensore di temperatura che segna $2000$ gradi invece di $200$ per un guasto del sensore.

Definizione (statistica $T^2$ di Hotelling). Per $p$ variabili, con media campionaria $\bar x$ e matrice di covarianza $S=\frac1{n-1}\sum_i(x_i-\bar x)(x_i-\bar x)^T$ : $T^2(x)=(x-\bar x)^T\,S^{-1}\,(x-\bar x).$ È uno z-score multivariato: misura quanto un'osservazione è lontana dalla media tenendo conto delle correlazioni. Un punto è un outlier multivariato se $T^2>\mathrm{UCL}$ .

Esempio. Quantili: per $p=1$ e $\alpha=0{,}05$ , $\chi^2=3{,}841$ (uguale a $1{,}96^2$ ); per $p=2$ : $5{,}991$ ( $\alpha=0{,}05$ ) e $9{,}210$ ( $\alpha=0{,}01$ ); per $p=3$ : $7{,}815$ . Caso univariato: con media $\bar x$ e varianza $s^2$ la statistica è $(x-\bar x)^2/s^2$ : nel laboratorio, per $100$ valori da $N(0,1)$ il punto $x=5$ ha $T^2\approx24$ , ben oltre $3{,}841$ : anomalo.

Grafico interattivo: Con correlazione 0,8 e varianze 1, la regione «normale» T² ≤ 5,99 (α = 0,05) è un'ellisse allungata lungo la diagonale: il punto (1, −1) è fuori (T² = 10) anche se ogni coordinata è entro 1σ; il punto (2, 2) è dentro (T² = 4,4) anche se ogni coordinata è a 2σ

Clustering e k-means

Definizione (k-means). Se si conoscessero i centroidi (i centri) di $K$ gruppi, basterebbe assegnare ogni punto al centroide più vicino. L'algoritmo li trova insieme alle assegnazioni:

Scegliere $K$ (iperparametro): il numero di cluster.

Inizializzare i centroidi: si scelgono a caso $K$ dei punti dati come centri iniziali.

Assegnare ogni punto al centroide più vicino (distanza euclidea o altra).

Aggiornare ogni centroide alla media dei punti assegnati al suo cluster.

Ripetere 3-4 fino a convergenza (i centroidi non cambiano più, o cambiano meno di una tolleranza, o si è raggiunto il numero massimo di iterazioni).

Definizione (clustering gerarchico). Costruisce un albero di cluster, il dendrogramma, in due modi:

agglomerativo (bottom-up): ogni punto parte come cluster a sé e si fondono cluster passo dopo passo;

divisivo (top-down): si parte da un unico cluster che contiene tutto e lo si divide passo dopo passo.

Esempio svolto (average e single linkage). Sei punti $P_0=(1,2)$ , $P_1=(5,8)$ , $P_2=(1,1)$ , $P_3=(2,3)$ , $P_4=(1{,}5;1{,}8)$ , $P_5=(5;6{,}5)$ e distanza euclidea. Ordine delle fusioni con average linkage (distanza di fusione tra parentesi): $\{P_0,P_4\}$ $(0{,}539)$ ; poi $\{P_0,P_4\}$ con $P_2$ $(0{,}972)$ ; $\{P_1,P_5\}$ $(1{,}50)$ ; $\{P_0,P_4,P_2\}$ con $P_3$ $(1{,}65)$ ; infine i due gruppi $\{P_0,P_2,P_3,P_4\}$ e $\{P_1,P_5\}$ $(6{,}44)$ . Con single linkage le distanze sono $0{,}539;\ 0{,}943;\ 1{,}30;\ 1{,}50;\ 4{,}61$ : stessi gruppi, altezze diverse. Il salto grande nell'ultima fusione indica che due cluster sono la scelta naturale.

6. Support vector machines

Support vector machines e metodi kernel

Definizione (margine). Il margine è la distanza tra il bordo di decisione e le osservazioni di ciascuna classe più vicine ad esso. Il classificatore a margine massimo (maximal margin classifier) è il classificatore lineare che sceglie l'iperpiano per cui questa distanza è la più grande possibile.

Formula (distanza di un punto dall'iperpiano). $d(x_0)=\frac{|w\cdot x_0+b|}{\|w\|}.$

Esempio. Piano $x_1+x_2-4=0$ , quindi $w=(1,1)$ , $b=-4$ , $\|w\|=\sqrt2$ . Il punto $(3,3)$ dista $|3+3-4|/\sqrt2=2/\sqrt2=\sqrt2\approx1{,}41$ .

Formula (larghezza del margine). Con la normalizzazione precedente, la distanza dal piano centrale a ciascun piano parallelo è $1/\|w\|$ e il margine totale è $\text{larghezza}=\frac{2}{\|w\|}.$

Esempio. Con $w=(0{,}5;0{,}5)$ si ha $\|w\|=0{,}5\sqrt2\approx0{,}707$ , quindi un margine di $1/0{,}707\approx1{,}41$ per lato e $2{,}83$ in totale.

Formula (SVM a margine rigido, hard margin). $\min_{w,b}\ \frac12\|w\|^2\qquad\text{soggetto a}\quad y_i(w\cdot x_i+b)\ge1,\ \ i=1,\dots,n.$

Formula (forma duale). $\max_{\alpha\ge0}\ \sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,(x_i\cdot x_j)\qquad\text{con}\quad\sum_i\alpha_iy_i=0.$ Il classificatore è $\hat y(x)=\operatorname{sign}\!\Big(\sum_i\alpha_iy_i\,(x_i\cdot x)+b\Big)$ , perché $w\cdot x=\sum_i\alpha_iy_i\,(x_i\cdot x)$ .

Esempio. Nell'esempio i vettori di supporto sono due, con $\alpha_1=\alpha_2=\alpha$ per $\sum\alpha_iy_i=0$ . Da $w=\alpha\,(3,3)-\alpha\,(1,1)=\alpha\,(2,2)=(0{,}5;0{,}5)$ si ricava $\alpha=0{,}25$ ; gli altri quattro punti hanno $\alpha=0$ . Si controlla che il valore del duale $\sum\alpha_i-\frac12\sum\alpha_i\alpha_jy_iy_jx_i\cdot x_j=0{,}5-\frac12\cdot0{,}25^2\cdot(2+18-2\cdot6)=0{,}5-0{,}25=0{,}25$ coincide con il valore del primale $\frac12\|w\|^2=0{,}25$ .

Formula (SVM a margine morbido). $\min_{w,b,\xi}\ \frac12\|w\|^2+C\sum_{i=1}^n\xi_i\qquad\text{soggetto a}\quad y_i(w\cdot x_i+b)\ge1-\xi_i,\ \ \xi_i\ge0.$

Esempio. Con $w=(0{,}5;0{,}5)$ , $b=-2$ e un punto di classe $+1$ in $(2{,}5;2)$ : $m=0{,}5\cdot4{,}5-2=0{,}25$ , quindi $\xi=0{,}75$ (dentro il margine, ma dal lato corretto). Un punto di classe $+1$ in $(3;0{,}5)$ ha $m=0{,}5\cdot3{,}5-2=-0{,}25$ e $\xi=1{,}25$ : mal classificato.

Grafico interattivo: Margine morbido: lo stesso piano con due punti di classe +1 che violano il margine. (2,5; 2) è dentro il margine (ξ = 0,75), (3; 0,5) è dal lato sbagliato (ξ = 1,25)

Definizione (kernel). Una funzione $K(x,x')$ è un kernel se vale $K(x,x')=\langle\phi(x),\phi(x')\rangle$ per una certa mappa $\phi$ . Misura la «somiglianza» di $x$ e $x'$ : grande per punti simili, piccola per punti dissimili. Una SVM (Support Vector Machine) è un SVC in cui $x_i\cdot x_j$ è sostituito dal kernel: $\hat y(x)=\operatorname{sign}\Big(\sum_i\alpha_iy_i\,K(x_i,x)+b\Big).$

Esempio (kernel polinomiale di grado 2). Con $\phi$ del paragrafo precedente si dimostra $\langle\phi(x),\phi(z)\rangle=(x\cdot z+1)^2$ : si espande il quadrato, $(x_1z_1+x_2z_2+1)^2=x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2+2x_1z_1+2x_2z_2+1$ , e si osserva che i sei addendi sono i prodotti delle sei componenti corrispondenti di $\phi(x)$ e $\phi(z)$ (per esempio $\sqrt2x_1x_2\cdot\sqrt2z_1z_2=2x_1x_2z_1z_2$ ); da qui il fattore $\sqrt2$ nella mappa. Numericamente, per $x=(1,2)$ , $z=(3,1)$ : $\phi(x)=[1,4,2\sqrt2,\sqrt2,2\sqrt2,1]$ , $\phi(z)=[9,1,3\sqrt2,3\sqrt2,\sqrt2,1]$ e $\langle\phi(x),\phi(z)\rangle=9+4+12+6+4+1=36$ . Con il kernel: $x\cdot z=3+2=5$ e $(5+1)^2=36$ . Stesso risultato con un solo prodotto scalare in $\mathbb R^2$ invece di uno in $\mathbb R^6$ .

Formula (SVR). $\min_{w,b,\xi,\xi^*}\ \frac12\|w\|^2+C\sum_i(\xi_i+\xi_i^*)\quad\text{con}\quad y_i-w\cdot x_i-b\le\varepsilon+\xi_i,\ \ w\cdot x_i+b-y_i\le\varepsilon+\xi_i^*,\ \ \xi_i,\xi_i^*\ge0.$

7. Reti neurali e deep learning

Reti neurali - neuroni e funzioni di attivazione

Definizione (neurone artificiale). Dato un vettore di ingressi $x=[x_1,\dots,x_m]^\top$ , pesi $w=[w_1,\dots,w_m]^\top$ , bias $w_0$ e una funzione di attivazione $g$ (non lineare) il neurone calcola $\hat y=g\big(w_0+x^\top w\big),\qquad z=w_0+x^\top w\ \text{ (pre-attivazione)},\ \ a=g(z)\ \text{ (attivazione)}.$

Esempio. $x=(2,1)$ , $w=(1,-0{,}5)$ , $w_0=-0{,}2$ , $g=\sigma$ : $z=2-0{,}5-0{,}2=1{,}3$ e $\hat y=\sigma(1{,}3)=1/(1+e^{-1{,}3})\approx0{,}786$ .

Formula (attivazioni principali). Le quattro funzioni usate negli strati nascosti, con la derivata (serve alla backpropagation):

Esempio. $\sigma(0)=0{,}5$ , $\sigma(2)=0{,}881$ , $\sigma(-2)=0{,}119$ ; $\sigma'(0)=0{,}25$ (massimo), $\sigma'(5)=0{,}0066$ . $\tanh(1)=0{,}762$ e $\tanh'(1)=1-0{,}762^2=0{,}42$ .

Grafico interattivo: Funzioni di attivazione: sigmoide e tanh saturano, ReLU e Leaky ReLU (α = 0,1) no

Formula (forma matriciale). Con $a^{(0)}=x$ e, per ogni strato $k=1,\dots,L$ , $z^{(k)}=W^{(k)}a^{(k-1)}+b^{(k)},\qquad a^{(k)}=g^{(k)}\big(z^{(k)}\big),\qquad \hat y=a^{(L)}.$ $W^{(k)}$ ha dimensione $d_k\times d_{k-1}$ , $b^{(k)}$ ha $d_k$ componenti.

Teorema (approssimazione universale). Una rete con un solo strato nascosto (sufficientemente largo) e attivazione non lineare può approssimare qualsiasi funzione continua su un insieme compatto con precisione arbitraria.

Formula (softmax). Trasforma i punteggi grezzi (logits) $z_1,\dots,z_K$ in probabilità: $\operatorname{softmax}(z)_i=\frac{e^{z_i}}{\sum_{j=1}^Ke^{z_j}}.$ Ogni uscita sta in $(0,1)$ e la somma è $1$ (il numeratore è positivo ed è una parte del denominatore, che è la somma di tutti i numeratori). Si usa l'esponenziale (Esponenziale e logaritmo) perché è positivo, monotono (ordine dei punteggi conservato) e derivabile. Si veda Regressione logistica e softmax.

Esempio. $z=(2,1,0)$ : gli esponenziali sono $7{,}389;\ 2{,}718;\ 1$ , somma $11{,}107$ , quindi probabilità $(0{,}665;\ 0{,}245;\ 0{,}090)$ .

Formula (cross-entropy). Con $y_i$ la distribuzione vera (one-hot) e $p_i$ quella predetta, la perdita di un campione è $-\sum_iy_i\log p_i$ ; nel caso binario $-[\,y\log p+(1-y)\log(1-p)\,]$ . Penalizza molto una previsione sbagliata con alta confidenza. Su un campione di classe vera $2$ con probabilità predetta $0{,}245$ la perdita è $-\log0{,}245=1{,}41$ .

Addestramento delle reti neurali - backpropagation e ottimizzatori

Definizione (loss e loss empirica). La loss $\mathcal L(f(x^{(i)};W),y^{(i)})$ è il costo associato alla previsione $f(x^{(i)};W)$ quando il valore vero è $y^{(i)}$ . La loss empirica (detta anche funzione obiettivo, funzione di costo, rischio empirico) è la media sul dataset: $J(W)=\frac1n\sum_{i=1}^{n}\mathcal L\big(f(x^{(i)};W),\,y^{(i)}\big).$

Esempio. Tre campioni con probabilità predette $f=(0{,}1;\ 0{,}8;\ 0{,}6)$ ed etichette $y=(1,0,1)$ : le perdite individuali sono $-\log0{,}1=2{,}303$ , $-\log(1-0{,}8)=1{,}609$ , $-\log0{,}6=0{,}511$ e la loss empirica vale $(2{,}303+1{,}609+0{,}511)/3=1{,}474$ . Il primo campione, classificato male con alta confidenza, pesa da solo metà della perdita.

Formula (discesa del gradiente).

Inizializza i pesi a caso, $W\sim\mathcal N(0,\sigma^2)$ .

Ripeti fino a convergenza: calcola $\dfrac{\partial J(W)}{\partial W}$ e aggiorna $W\leftarrow W-\eta\,\dfrac{\partial J(W)}{\partial W}$ .

Restituisci $W$ .

Esempio (una sola variabile). $J(w)=(w-3)^2$ , derivata $2(w-3)$ , partenza $w_0=0$ , $\eta=0{,}1$ . Ogni passo è $w\leftarrow w-0{,}1\cdot2(w-3)=0{,}8\,w+0{,}6$ : $0\to0{,}6\to1{,}08\to1{,}464\to1{,}771\to2{,}017\to\dots$ , che tende a $3$ con $J$ che scende $9\to5{,}76\to3{,}69\to2{,}36\to1{,}51\to0{,}97$ . Con $\eta=1{,}1$ invece il passo è $w\leftarrow w-2{,}2(w-3)=-1{,}2w+6{,}6$ : $0\to6{,}6\to-1{,}32\to8{,}18\to-3{,}22\dots$ oscilla e diverge. Un $\eta$ troppo piccolo è lentissimo, troppo grande diverge: è l'iperparametro più importante.

Grafico interattivo: Learning rate troppo piccolo (η = 0,01): partendo da w = 0 i passi sono minuscoli (w = 0, 0,06, 0,119, 0,177)

Formula (mini-batch). $\dfrac{\partial J(W)}{\partial W}\approx\dfrac1B\sum_{k=1}^{B}\dfrac{\partial J_k(W)}{\partial W},\qquad W\leftarrow W-\eta\,\dfrac{\partial J(W)}{\partial W}.$

Esempio. MNIST: $60\,000$ immagini, $B=32$ : $1\,875$ iterazioni per epoca. Con validation_split=0.1 il training scende a $54\,000$ e Keras mostra $1\,688$ iterazioni ( $\lceil54\,000/32\rceil$ ).

Teorema (regola della catena). Se $y=f(u)$ e $u=g(x)$ allora $\dfrac{dy}{dx}=\dfrac{df}{du}\cdot\dfrac{du}{dx}$ (Regole di derivazione). Con più variabili intermedie $y=f(u_1,\dots,u_k)$ e $u_i=u_i(x)$ si sommano i contributi di ciascun percorso: $\dfrac{dy}{dx}=\sum_i\dfrac{\partial f}{\partial u_i}\dfrac{du_i}{dx}$ (Regola della catena in più variabili, Matrice jacobiana e derivata delle funzioni composte).

Formula (backpropagation). Con $z^{(l)}=W^{(l)}a^{(l-1)}+b^{(l)}$ e $a^{(l)}=g(z^{(l)})$ : $\delta^{(L)}=\frac{\partial J}{\partial a^{(L)}}\odot g'\big(z^{(L)}\big),\qquad \delta^{(l)}=\Big(W^{(l+1)\top}\delta^{(l+1)}\Big)\odot g'\big(z^{(l)}\big),$ $\frac{\partial J}{\partial W^{(l)}}=\delta^{(l)}\,a^{(l-1)\top},\qquad \frac{\partial J}{\partial b^{(l)}}=\delta^{(l)}.$ ( $\odot$ = prodotto componente per componente.)

Formula (inizializzazioni).

Glorot / Xavier (per tanh e sigmoide): $\operatorname{Var}(W)=\dfrac2{n_{in}+n_{out}}$ (media tra la condizione in avanti $1/n_{in}$ e quella all'indietro $1/n_{out}$ ).

He (per ReLU): $\operatorname{Var}(W)=\dfrac2{n_{in}}$ . La ReLU azzera metà degli ingressi, dimezzando la varianza: si raddoppia per compensare.

Esempio. Strato $784\to512$ : Xavier dà deviazione standard $\sqrt{2/(784+512)}=0{,}039$ ; per uno strato ReLU $512\to512$ He dà $\sqrt{2/512}=0{,}0625$ . Keras usa Glorot uniforme di default; con ReLU conviene kernel_initializer="he_normal".

Formula (batch normalization). $\mu_{\mathcal B}=\frac1m\sum_ix_i,\qquad\sigma^2_{\mathcal B}=\frac1m\sum_i(x_i-\mu_{\mathcal B})^2,\qquad\hat x_i=\frac{x_i-\mu_{\mathcal B}}{\sqrt{\sigma^2_{\mathcal B}+\varepsilon}},\qquad y_i=\gamma\hat x_i+\beta.$ $\gamma$ (scala) e $\beta$ (traslazione) sono parametri appresi per ogni strato; $\varepsilon$ evita la divisione per zero.

Esempio. Batch $\{2,4,6,8\}$ : $\mu=5$ , $\sigma^2=5$ , quindi $\hat x=(-1{,}342;\ -0{,}447;\ 0{,}447;\ 1{,}342)$ . Con $\gamma=2$ , $\beta=1$ : $y=(-1{,}683;\ 0{,}106;\ 1{,}894;\ 3{,}683)$ . Al momento dell'inferenza media e varianza del batch non esistono: si usano medie mobili calcolate durante l'addestramento (Keras lo fa da solo).

Regolarizzazione delle reti neurali

Formula (regolarizzazione $\ell_2$ e $\ell_1$ ). Con $\lambda\ge0$ forza della penalità: $J_{\ell_2}(W)=J(W)+\lambda\sum_k w_k^2,\qquad J_{\ell_1}(W)=J(W)+\lambda\sum_k|w_k|.$

Esempio. $w=2$ , $\nabla J=0$ (solo penalità), $\eta=0{,}1$ , $\lambda=0{,}01$ . Con $\ell_2$ : $w\leftarrow(1-0{,}002)\cdot2=1{,}996$ per passo. Con $\ell_1$ : $w\leftarrow2-0{,}1\cdot0{,}01=1{,}999$ per passo, ma lo stesso passo vale per $w=0{,}001$ , che quindi in pochi passi arriva a $0$ .

Grafico interattivo: Le due penalità su un singolo peso: w² (ℓ2) è piatta vicino a 0 e ripida lontano, |w| (ℓ1) ha pendenza costante e un angolo in 0

Definizione (early stopping). Si monitora una metrica di validazione (monitor, tipicamente val_loss). Se non migliora per patience epoche consecutive l'addestramento si interrompe; con restore_best_weights=True si ripristinano i pesi dell'epoca migliore.

Definizione (dropout). Durante l'addestramento, a ogni passo e per ogni neurone di uno strato, con probabilità $p$ (la rate) l'uscita viene posta a $0$ . Gli altri neuroni sono riscalati per $1/(1-p)$ . In inferenza il dropout è spento e si usano tutti i neuroni.

Esempio. Attivazioni $a=(0{,}8;\ 1{,}2;\ 0{,}5;\ 2{,}0)$ , $p=0{,}5$ , maschera estratta $(1,0,1,0)$ : l'uscita in training è $(0{,}8;\ 0;\ 0{,}5;\ 0)/0{,}5=(1{,}6;\ 0;\ 1{,}0;\ 0)$ . La riscalatura fa sì che il valore atteso (Valore atteso) di ogni attivazione sia lo stesso con e senza dropout (la maschera vale $1$ con probabilità $1-p$ e $0$ con probabilità $p$ ): $E=(1-p)\cdot\frac{a}{1-p}+p\cdot0=a$ . Per questo in inferenza non serve correggere nulla (versione «inverted dropout» usata da Keras e PyTorch).

Reti neurali convolutive (CNN)

Definizione (convoluzione 2D discreta). Dati un'immagine $x$ e un filtro $h$ , $y[n,m]=\sum_j\sum_ix[i,j]\;h[n-i,\,m-j].$ Si moltiplicano elemento per elemento l'immagine e il filtro posizionato in $(n,m)$ e si sommano i risultati (una combinazione lineare locale).

Formula (dimensione dell'uscita). Con ingresso di lato $W$ , filtro di lato $K$ , padding $P$ , stride $S$ : $O=\Big\lfloor\frac{W-K+2P}{S}\Big\rfloor+1.$

Esempio. $W=28$ , $K=3$ , $P=0$ , $S=1$ : $O=25+1=26$ . Con $P=1$ : $O=(28-3+2)/1+1=28$ (padding «same»: la dimensione si conserva). AlexNet: ingresso $227$ , filtro $11$ , stride $4$ : $O=(227-11)/4+1=55$ .

Formula (parametri di uno strato convolutivo). Con $C_{in}$ canali in ingresso e $C_{out}$ filtri $K\times K$ : $K^2\,C_{in}\,C_{out}+C_{out}.$ Ogni filtro ha $K\cdot K\cdot C_{in}$ pesi (si estende in profondità a tutti i canali) più un bias.

Autoencoder

Definizione (autoencoder). Un autoencoder è una rete deterministica addestrata con la backpropagation (Addestramento delle reti neurali - backpropagation e ottimizzatori) in cui l'uscita deve coincidere con l'ingresso. Per non imparare l'identità, il segnale passa per un collo di bottiglia (bottleneck, codice) di dimensione limitata.

L'encoder $e$ mappa $x$ in una rappresentazione a bassa dimensione $z=e(x)$ (il vettore latente);

il decoder $d$ ricostruisce $\hat x=d(z)$ a partire da $z$ .

Formula (loss di ricostruzione). $\text{loss}=\|x-\hat x\|^2=\|x-d(z)\|^2=\|x-d(e(x))\|^2,$ mediata sul training set; $\|v\|^2=\sum_kv_k^2$ è l'errore quadratico (Prodotto scalare, norma e angoli). Se l'ingresso è binario o in $[0,1]$ si usa spesso la cross-entropy binaria per pixel.

Esempio (conteggio dei parametri). Autoencoder denso $784\to128\to32\to128\to784$ con ReLU (e sigmoide in uscita): $784\cdot128+128=100\,480$ ; $128\cdot32+32=4\,128$ ; $32\cdot128+128=4\,224$ ; $128\cdot784+784=101\,136$ ; in tutto $209\,968$ parametri. Il codice ha $32$ numeri per rappresentare $784$ pixel: compressione di $784/32=24{,}5$ volte.

Formula (regola di decisione). Con $\text{MSE}(x,x')=\frac1p\sum_k(x_k-x'_k)^2$ e una soglia $\theta$ : normale se $\text{MSE}\le\theta$ , anomalo se $\text{MSE}>\theta$ .

Esempio. Errori di ricostruzione sul training: media $0{,}015$ , deviazione standard $0{,}004$ , quindi $\theta=0{,}015+3\cdot0{,}004=0{,}027$ . Cinque nuovi campioni hanno errori $0{,}010;\ 0{,}022;\ 0{,}015;\ 0{,}200;\ 0{,}031$ : sono anomali il quarto ( $0{,}200>0{,}027$ ) e il quinto ( $0{,}031>0{,}027$ ).

Grafico interattivo: Densità schematiche dell'errore di ricostruzione: i dati normali stanno sotto la soglia θ = 0,027, le anomalie sopra

Formula (loss del VAE). $\text{loss}=\|x-d(z)\|^2+KL\big[\mathcal N(\mu_x,\sigma_x)\,\big\|\,\mathcal N(0,I)\big],\qquad z\sim\mathcal N(\mu_x,\sigma_x).$ Il primo termine è l'errore di ricostruzione; il secondo è la divergenza di Kullback-Leibler tra la distribuzione stimata e quella standard. Spesso il primo termine è moltiplicato per una costante $C$ che ne regola il peso.

Definizione (divergenza KL). Per due densità $P$ e $Q$ , $D_{KL}(P\,\|\,Q)=\int P(x)\log\frac{P(x)}{Q(x)}\,dx=E_P\Big[\log\frac P Q\Big]\ \ge0,$ e vale $0$ se e solo se $P=Q$ (disuguaglianza di Jensen, Disuguaglianze di Markov, Chebyshev e Jensen). Misura quanto $P$ è diversa da $Q$ (non è simmetrica).

Esempio. $\mu=(1,0)$ , $\sigma=(1;0{,}5)$ : componente $1$ : $\frac12(1+1-1-0)=0{,}5$ ; componente $2$ : $\frac12(0+0{,}25-1-\ln0{,}25)=\frac12(-0{,}75+1{,}386)=0{,}318$ . $KL=0{,}818$ .

Grafico interattivo: KL(N(μ,σ²) ‖ N(0,1)) al variare di σ con μ = 0: minimo 0 in σ = 1; con μ ≠ 0 si aggiunge μ²/2

Formula (reparametrization trick). $z=\mu_x+\sigma_x\odot\zeta,\qquad\zeta\sim\mathcal N(0,I)$ (nelle slide $z=h(x)\zeta+g(x)$ con $g(x)=\mu_x$ e $h(x)=\sigma_x$ prodotti dall'encoder).

Esempio. $\mu=0{,}5$ , $\sigma=2$ , $\zeta=-0{,}3$ estratto: $z=0{,}5+2\cdot(-0{,}3)=-0{,}1$ .

Cenni a reinforcement learning e reti per sequenze

Definizione (reinforcement learning, RL). Area del ML e paradigma di apprendimento che si occupa di imparare a controllare un sistema (con molti elementi sconosciuti) interagendo con esso, per massimizzare una misura numerica di prestazione. I dati si raccolgono durante l'interazione con l'ambiente.

Esempio (dal film «Ricomincio da capo»). Phil, intrappolato in un ciclo temporale, è l'agente; le azioni sono comportarsi in vari modi (gentile, divertente...) a partire da stati diversi (al ristorante, al parco); l'ambiente è la città con i suoi abitanti; iterando raccoglie dati e impara come massimizzare la ricompensa (far innamorare Rita).

Formula (obiettivo del RL). Si cerca la politica ottima $\pi^*=\arg\max_\pi\,E[G]$ . A differenza del ML supervisionato, dove si minimizza una loss, qui si massimizza il ritorno.

8. Fairness ed explainability

Fairness nel machine learning

Definizione (fairness). Nell'AI/ML, assenza di bias, discriminazione o favoritismo nei confronti di individui o gruppi nei risultati, nelle decisioni e nei processi del sistema. Le decisioni non devono produrre esiti ingiusti o pregiudizievoli in base ad attributi sensibili come razza, genere, età, religione, stato socioeconomico.

Definizione (attributi sensibili o protetti). Caratteristiche degli individui sulle quali, per legge o per etica, il trattamento ingiusto va evitato (razza, etnia, genere, età, disabilità, religione, orientamento sessuale, nazionalità, stato civile, background socioeconomico). Sono «sensibili» perché storicamente alla base di disuguaglianze.

Definizione (fairness through unawareness). Un algoritmo è giusto se gli attributi protetti non sono usati esplicitamente nel processo decisionale: $\hat Y=f(X)$ con $A\notin X$ . È apprezzata dai giuristi (il GDPR vieta di trattare categorie particolari di dati, salvo eccezioni): un sistema non può discriminare in base a un attributo che non vede.

Definizione (variabile proxy). Una variabile che non è sensibile ma è fortemente correlata a un attributo sensibile. Anche senza race, il modello può ricostruirla dal proxy e discriminare lo stesso.

Formula (Demographic Parity, parità demografica). Usata dove un esito positivo è desiderabile per tutti (selezione del personale, prestiti): la previsione dovrebbe essere indipendente dall'attributo sensibile, cioè la probabilità di un esito positivo uguale nei gruppi. $DP=P(\hat Y=1\mid A=a)-P(\hat Y=1\mid A=d),\qquad\text{ideale }DP=0.$

Formula (Equality of Opportunity, pari opportunità). Usata quando l'esito deve poter dipendere dal gruppo (in medicina la frequenza di certe patologie dipende da sesso o etnia): non si chiede lo stesso tasso di esiti positivi ma lo stesso tasso di veri positivi (TPR, Metriche di classificazione), cioè la stessa probabilità di essere riconosciuto positivo tra chi lo è davvero. $EO=P(\hat Y=1\mid A=a,Y=1)-P(\hat Y=1\mid A=d,Y=1),\qquad\text{ideale }EO=0.$

Esempio. Gruppo $a$ : $100$ persone, $50$ con $Y=1$ , previsione positiva per $60$ (di cui $45$ con $Y=1$ ). Gruppo $d$ : $100$ persone, $40$ con $Y=1$ , previsione positiva per $30$ (di cui $24$ con $Y=1$ ). Allora $P(\hat Y=1|a)=60/100=0{,}60$ e $P(\hat Y=1|d)=30/100=0{,}30$ : $DP=0{,}30$ . I TPR sono $45/50=0{,}90$ e $24/40=0{,}60$ : $EO=0{,}30$ . Il gruppo $d$ è penalizzato sia nella quota di accettati sia nella probabilità di essere riconosciuto quando merita.

Explainable AI (XAI)

Definizione (interpretabilità). La scienza (o arte) di produrre descrizioni di un modello abbastanza semplici da essere comprese da un essere umano.

Definizione (spiegabilità). Interpretabilità più completezza: una spiegazione è completa quando permette di anticipare la previsione del modello.

Formula (Gini e Information Gain). Per un nodo con classi di probabilità $p_1,\dots,p_c$ : $Gini=1-\sum_ip_i^2$ ; entropia $-\sum_ip_i\log_2p_i$ . Lo split in due figli ha $Gini_{split}=\frac{n_{left}}{n}Gini(left)+\frac{n_{right}}{n}Gini(right)$ . La riduzione di impurità (Mean Decrease in Impurity, MDI) di uno split è $\Delta Gini=Gini(parent)-\Big(\frac{n_{left}}{n_p}Gini(left)+\frac{n_{right}}{n_p}Gini(right)\Big).$

Esempio. Nodo con $10$ campioni, $6$ di classe A e $4$ di B: $Gini=1-0{,}6^2-0{,}4^2=0{,}48$ . Uno split manda $5$ campioni (tutti A) a sinistra, impurità $0$ , e $5$ (1 A e 4 B) a destra, $Gini=1-0{,}2^2-0{,}8^2=0{,}32$ . Pesata: $\frac5{10}\cdot0+\frac5{10}\cdot0{,}32=0{,}16$ e $\Delta Gini=0{,}48-0{,}16=0{,}32$ .

Grafico interattivo: Impurità di un nodo a due classi in funzione della frazione p di una classe: massima in p = 1/2 (nodo più misto), zero per nodi puri

Formula (importanza MDI, Gini importance). L'importanza di una feature è la somma delle riduzioni di impurità di tutti i nodi in cui essa è usata per lo split, pesate per la quota di campioni del nodo: $\text{Imp}(f)=\sum_{\text{nodi che usano }f}\frac{n_p}{n_{TOT}}\,\Delta Gini,\qquad\text{normalizzata: }\frac{\text{Imp}(f)}{\sum_g\text{Imp}(g)}.$

Definizione (permutation importance). Metodo post-hoc, agnostico, globale. Si valuta il modello (errore su un insieme di dati); poi si mescola a caso una feature su tutti i punti, rompendo il suo legame con il target, e si rivaluta. L'importanza è l'aumento dell'errore.

Esempio (slide). Cinque dati con $x_1=(3{,}4;\ 2{,}7;\ 3{,}5;\ 1{,}5;\ 1{,}8)$ , $x_2=(7{,}5;\ 7{,}7;\ 6{,}9;\ 6{,}3;\ 6{,}4)$ , etichette vere $(0,1,1,0,1)$ , predizioni originali $(1,1,1,0,1)$ : un errore su cinque, errore $20\%$ . Dopo aver mescolato $x_1$ le predizioni sono $(1,1,0,0,1)$ : differiscono dalle etichette in posizione $1$ e $3$ , errore $40\%$ . Dopo aver mescolato $x_2$ sono $(1,0,1,1,0)$ : sbagliate in posizione $1,2,4,5$ , errore $80\%$ . Importanza $x_1=40\%-20\%=20$ punti, $x_2=80\%-20\%=60$ punti: $x_2$ conta molto di più.

Definizione (PDP, grafico di dipendenza parziale). Effetto marginale medio di un sottoinsieme $S$ di feature (di solito una o due) sulla previsione, ottenuto marginalizzando le altre feature $C$ : $\hat f_S(x_S)=E_{x_C}\big[\hat f(x_S,x_C)\big]\approx\frac1n\sum_{i=1}^n\hat f\big(x_S,\,x_C^{(i)}\big).$ Il PDP è la media delle curve ICE (valore atteso come media sui dati, Valore atteso).

Esempio. $f(x_1,x_2)=x_1+x_1x_2=x_1(1+x_2)$ e tre dati con $x_2=0,1,2$ . Per un valore $x_1$ fissato le tre ICE valgono $x_1,\ 2x_1,\ 3x_1$ e il PDP $=\frac13(x_1+2x_1+3x_1)=2x_1$ : la media nasconde che per un campione la pendenza è $1$ e per un altro $3$ . Il PDP si legge per capire se il legame è lineare, monotono o più complesso; con due feature si disegna una mappa di contorno (laboratorio: età e frequenza cardiaca massima).

Grafico interattivo: ICE e PDP per il modello f = x1 + x1·x2 con x2 ∈ {0,1,2}: le tre curve ICE (pendenze 1, 2, 3) hanno medie diverse, il PDP (pendenza 2) le riassume e nasconde l'eterogeneità

Definizione (LIME, Local Interpretable Model-agnostic Explanations). Spiega una singola previsione con un modello semplice che approssima il black-box vicino a quel punto.

Definizione (valore di Shapley, SHAP). Dalla teoria dei giochi cooperativi: la previsione è un «pagamento» da distribuire tra le feature («giocatrici»). Il valore di Shapley $\varphi_i$ della feature $i$ è la media del suo contributo marginale su tutti gli ordini in cui le feature possono essere aggiunte: $\varphi_i=\sum_{S\subseteq F\setminus\{i\}}\frac{|S|!\,(|F|-|S|-1)!}{|F|!}\Big[v(S\cup\{i\})-v(S)\Big],$ con $v(S)$ la previsione quando solo le feature in $S$ hanno il valore osservato e le altre un valore di riferimento (la media sul dataset di sfondo).

Esempio. $f(x)=2x_1+x_1x_2+x_3$ , riferimento $(0,0,0)$ , istanza $x=(1,2,3)$ , $f(x)=2+2+3=7$ . Valori di $v$ : $v(\emptyset)=0$ , $v(1)=2$ , $v(2)=0$ , $v(3)=3$ , $v(12)=2+2=4$ , $v(13)=5$ , $v(23)=3$ , $v(123)=7$ . Per $x_1$ : $\frac13(2-0)+\frac16(4-0)+\frac16(5-3)+\frac13(7-3)=\frac23+\frac23+\frac13+\frac43=3$ . Per $x_2$ : $\frac13(0)+\frac16(4-2)+\frac16(3-3)+\frac13(7-5)=\frac13+\frac23=1$ . Per $x_3$ : $3$ . Somma $3+1+3=7=f(x)-f(0)$ . Si noti che il prodotto $x_1x_2=2$ è diviso a metà tra $x_1$ e $x_2$ (ma $x_2$ ottiene solo $1$ perché da solo non vale nulla, $v(2)=0$ ).