Statistical Learning PDF - September 2024 - January 2025

Statistical Learning Enrico Daniele September 2024 - January 2025 Indice 1 La Classificazione 5 1.1 Concetti Introduttivi.....

Statistical Learning Enrico Daniele September 2024 - January 2025 Indice 1 La Classificazione 5 1.1 Concetti Introduttivi........................ 5 1.2 Il problema di Classificazione.................... 5 1.2.1 La variabile casuale Bernoulliana............. 7 Pull out what’s known.................... 7 Légge delle aspettative iterate................ 7 1.3 Classificatore ottimale di Bayes................... 7 1.3.1 Problema 2-class...................... 8 Dimostrazione........................ 8 Dimostrazione........................ 9 1.3.2 Problema multiclass.................... 9 1.4 Modello Bernoulliano-logistico Lineare............... 10 Assunzione 1......................... 11 Assunzione 2......................... 11 Odds............................. 11 Funzione logistca (o anti-logit/sigmoid)........... 11 Funzione soft-max...................... 11 Modelli con costante..................... 12 Assunzione 3......................... 12 1.5 Stima di β̂.............................. 12 1.6 Proprietà di β̂ ed Inferenza..................... 13 1.7 La linearità della Decision Boundary............... 14 1.8 Error rate in-sample......................... 15 1.9 Regressione logistica per i problemi multi-class.......... 15 1  1.9.1 Regressione Logistica One VS All............. 16 1.9.2 Modello Bernoulliano Generalizzato-Logistico (o Multi- nomial Logit)........................ 17 2 Geometria e probabilità nello spazio Multivariato 19 2.1 I concetti di Distanza e di Intorno.................. 19 2.2 Variabili Casuali Multivariate................... 21 2.2.1 Cosa sono le v. c. Multivariate?.............. 21 2.2.2 Momento primo, momento secondo e matrice VCV.... 21 Modello sferico: incorrelazione + omoschedasticità.... 23 Modello diagonale: incorrelazione + eteroschedasticità.. 23 Media campionaria (osservata)............... 23 Matrice di varianze-covarianze non distorta (osservata).. 24 2.3 Dispersione vs direzione....................... 24 2.4 Trasformazioni lineari di variabili casuali inRp......... 27 2.5 Variabile Casuale Normale Multivariata............. 28 2.5.1 Variabile Casuale Normale Multivariata Standard... 28 2.5.2 I density countours..................... 30 2.5.3 Distanza di Mahalanobis................. 30 3 Classificazione: LDA, QDA e kNN 33 3.1 Linear Discriminant Analysis - LDA................ 35 A. LDA:.......................... 35 Dimostrazione........................ 36 3.1.1 Linearità della Decision Boundary............ 36 3.1.2 Stima dei parametri.................... 36 3.2 Quadratic Discriminant Analysis - QDA............. 38 A. QDA:.......................... 38 Dimostrazione........................ 39 3.3 k-Nearest Neigbours (kNN)..................... 40 3.3.1 Classificatore kNN..................... 40 4 Metriche di Performance e Metodi di Thresholding 43 4.1 Alcune misure di performance................... 43 4.2 La curva ROC............................ 44 2 5 Validazione e Selezione del Modello 47 Descrizione locale vs globale................. 48 Parametri e iper-parametri................. 48 Le sorgenti di variazione................... 48 5.1 La questione dell’errore........................ 49 5.2 La Cross Validation......................... 51 Monte Carlo CV - MCCV.................. 53 k-folds CV - kFCV...................... 54 Trade-off nella scelta di k.................. 55 5.3 External Validation......................... 58 Caso 1 - Con EVS...................... 58 Caso 2 - Senza EVS..................... 58 6 Riduzione e Compressione dei dati 61 6.1 Principal Component Analysis - PCA................ 61 6.1.1 Costruzione delle PC.................... 62 6.1.2 Geometria delle PC.................... 65 6.1.3 Proprietà delle PC..................... 69 6.2 PCA................................. 70 7 Il Clustering 75 7.1 K-Means clustering......................... 75 7.1.1 L’iterazione di Lloyd.................... 76 7.1.2 La nozione di dissimilarità................ 78 7.1.3 K-Medoid......................... 80 7.2 Metodi gerarchici.......................... 82 I grafi............................ 82 Single Linkage (Nearest-Neighbour Linkage)....... 84 Complete Linkage...................... 84 Average Linkage....................... 85 7.3 Validazione e scelta di K...................... 86 3  1 La Classificazione 1.1 Concetti Introduttivi Lo Statistical Learning rappresenta la base statistica del Machine Learning. Il ML è una branca dell’Intelligenza Artificiale che raccoglie metodi sviluppati in diverse discipline (come la matematica e l’informatica) per costruire dai dati osservati dei meccanismi di azione, come previsioni e verifiche di ipotesi. Quando lavoriamo con i dati, possiamo distinguere due paradigmi principali: Par. predittivo, dove l’obiettivo è prevedere i casi non osservati sfruttando le relazioni tra le variabili nei dati osservati (tipico del ML); Par. esplicativo, dove l’obiettivo è comprendere le relazioni tra le variabili. Questi approcci si basano su due diverse fonti di conoscenza: Domain-independent Knowledge: strumenti pratici come programmazione, ottimizzazione, EDA (Exploratory Data Analysis), inferenza, ecc.; Domain-dependent Knowledge: conoscenza specifica e visione generale sul problema affrontato. 1.2 Il problema di Classificazione Nel problema di classificazione partiamo da una situazione dove abbiamo un certo numero di oggetti appartenenti a una classe nell’insieme Y. Nei problemi 2-class, queste sono convenzionalmente chiamate 0 e 1, o positivi (+1) e negativi (−1): sarà positiva la classe che è funzione del problema, come i pazienti che presentano una data malattia. Il problema di classificazione consiste nel prevedere, in base alle caratteristiche di un oggetto, la sua classe. Ergo, la quantità da prevedere è una variabile categoriale. In generale, osserviamo un vettore di variabili casuali, X = (X1 ,... , Xp )′ , e vogliamo costruire un classificatore, ossia una funzione Ŷ (·) che prende in input le features osservate e assegna l’oggetto a una certa classe Ŷ (X) ∈ Y. Noi vorremmo che un classificatore assegni le classi correttamente. Di solito si ha una funzione obiettivo da ottimizzare, come una Loss da minimizzare o un’Utilità da massimizzare. Qui vogliamo minimizzare una funzione di perdita. 5  Supponiamo di voler classificare gli individui in maschi e femmine, e di aver osservato una serie di features. Supponiamo di costruire il seguente classificatore: { M → se il nome finisce in ”o” Ŷ (X) := F → altrimenti Date le istanze {Ugo, Maria, Jasmine, Paolo, Gioele}, il classificatore ne classificherà correttamente 4 su 5. Per misurarne la qualità possiamo considerare la Loss 0/1: { 1 → se yi 6= Ŷ (xi ) L(yi , Ŷ (xi )) = I{yi 6= Ŷ (xi )} = 0 → altrimenti La Loss misura la perdita conseguita ogni volta che prendiamo l’istanza i e la as- segniamo a Ŷ (xi ). In altre parole, in base alle caratteristiche di i il classificatore fa una previsione, e la confronteremo con la vera etichetta. A che serve tutto ciò? La classificazione è un problema supervised e questa è solo la prima fase: useremo il classificatore addestrato nel train set per classificare le istanze fuori campione. La qualità di un classificatore dipende dalla distribuzione delle Loss, che a loro volta dipendono dall’incertezza che governa la Y e le X. Possiamo misurare la sua capacità previsiva con l’Expected Prediction Error, ossia il valore atteso della Loss. EP E := E[L(Y, Ŷ (X))] (1) Nel caso della Loss 0/1, L(·) è una v. c. dicotomica; quindi: EP E := E[I{Y 6= Ŷ (X)}] = P (Y 6= Ŷ (X)) (2) Nell’esempio, la Loss media attesa risulta: 1X 1X n n 0+0+0+0+1 L(yi , Ŷ (xi )) = I{yi 6= Ŷ (xi )} = = 0.2 (3) n i=1 n i=1 5 La Loss media, in questo caso, prende il nome di Misclassification Rate, ed è la proporzione di unità misclassificate. Sotto condizioni generali, possiamo determinare una ricetta per costruire un classificatore decente? Analizziamo l’ambiente tipo. Abbiamo: Una Popolazione di v. c., dove le Yi ∈ Y rappresentano le classi della popo- lazione con la loro distribuzione di probabilità; Un vettore di v. c. X (le features) per ogni istanza; Un classificatore Ŷ (X) che è funzione delle features e, quindi, è una v. c.; La Loss, che è la v. c. L(Y, Ŷ (X)). Poiché la Loss assume solo due valori, è una v. c. di Bernoulli. 6 1.2.1 La variabile casuale Bernoulliana La v. c. Bernoulliana Z può assumere solo due valori, fissati per convenzione nell’insieme {0, 1}, con 1 = successo. Se η = P (Z = 1) ⇒ P (Z = 0) = 1 − η. Da ciò si ha che E[Z] = P (Z = 1) = η. La successione ∑n {Z1 ,... , Zn } è un campione casuale con media campionaria Z = n1 i=1 Zi , e corrisponderà alla proporzione di successi. Esso è uno stimatore consistente per η, perché, per la légge dei grandi numeri, lim Z ≈ E[Z] = η. n→∞ Consideriamo una v. c. Reale X e fissiamo l’evento X ≥ 0. Inoltre, consid- eriamo P (X ≥ 0) = η. Si noti che, sotto queste condizioni, imponendole la funzione indicatrice, la si dicotomizza. Infatti, Z = I{X ≥ 0} ∼ Be(η) con: { 0 → se X < 0 Z := 1 → se X ≥ 0 Da ciò si ottiene che E[Z] = E[I{X ≥ 0}] = P (X ≥ 0) = η. Pull out what’s known. Date le v. c. X e Y , e una funzione g(·), allora: E[g(X)Y |X] = g(X)E[Y |X] (4) Légge delle aspettative iterate. Date le v. c. X e Y , allora: E[E[Y |X]] = E[Y ] (5) 1.3 Classificatore ottimale di Bayes C’è un classificatore ottimale che garantisca bassi livelli di rischio? Noi usiamo l’informazione contenuta in X per prevedere Ŷ (X) (facciamo un calcolo con- dizionato). Se formuliamo l’assegnazione sulla base dell’informazione fornita da X = x, il rischio atteso (o errore condizionato) è: E[L(Y, Ŷ (x))| X = x] (6) Si definisce Classificatore Ottimale di Bayes un classificatore Y ∗ (·) per cui la Loss condizionata in un dato punto x è la minore possibile; ossia: E[L(Y, Y ∗ (x))| X = x] ≤ E[L(Y, Ŷ (x))| X = x] ∀ x (7) 7 1.3.1 Problema 2-class Consideriamo il problema seguente: Y ∈ Y , con Y = {0, 1}; P (Y = 1|X) = η(X) e P (Y = 0|X) = 1 − η(X) note (posterior class probabilities - probabilità di appartenere a una classe date le features); Si dimostra che, conoscendo i posterior, si può costruire il Classificatore Bayesiano: { 0 → se η(X) < 12 Y ∗ (X) = 1 → se η(X) ≥ 1 2 Dimostrazione. Siccome la Loss assume due valori precisi, possiamo spezzarla in due componenti che rappresentano i due pezzi della decisione: L(Y, Ŷ ) = I{Y 6= Ŷ (X)} = I{Y = 1}I{Ŷ (X) = 0} + I{Y = 0}I{Ŷ (X) = 1} (8) Il classificatore è ottimale se minimizza l’errore condizionato per ogni valore di X: E[L(Y, Ŷ )|X] = E[I{Y = 1}I{Ŷ (X) = 0}|X] + E[I{Y = 0}I{Ŷ (X) = 1}|X] = = E[I{Y = 1}|X]I{Ŷ (X) = 0}] + E[I{Y = 0}|X]I{Ŷ (X) = 1}] = = P (Y = 1|X)I{Ŷ (X) = 0}] + P (Y = 0|X)I{Ŷ (X) = 1} = = η(X)I{Ŷ (X) = 0}] + [1 − η(X)]I{Ŷ (X) = 1} Si dimostra che il classificatore deve assegnare 0 se η(X) < 1 − η(X), ossia η(X) < 21 , altrimenti assegnerà 1. Ogni classificatore ha una superficie di separazione che divide geometricamente i positivi dai negativi. Tale linea è la decision boundary (frontiera di decisione), e, per p features, ne avrò p − 1. I punti con un colore diverso dalla loro regione, e, quindi, con una classe effettiva diversa dalla prevista, sono i punti misclassificati. 8  Perché questo è il miglior MCR possibile? Per la légge dei valori attesi iterati. Per costruzione, Y ∗ minimizza E[L(Y, Y ∗ (x))|X = x] ∀ x. Poiché ottimizza punto per punto localmente, ottimizzerà anche in generale. Come passiamo dal rischio condizionato locale a quello incondizionato globale (EPE)? Dobbiamo guardare alla nozione di error rate: E[L(Y, Ŷ (·))]. Poiché Y ∗ fornisce la migliore previsione per ogni punto x, allora produce globalmente l’error rate ottimale: E[L(Y, Y ∗ (X))], detto Bayes Error Rate. Si dimostra che il BER rispetto alla Loss 0/1 nel problema 2-class è dato da: E[min{η(X), 1 − η(X)}]. Dimostrazione. Per ottenere il BER dobbiamo ricavare E[L(Y, Y ∗ )]. Usando la légge del valore atteso iterato: E[L(·)] = E[E[L(·)|X]] (9) Calcoliamo innanzitutto E[L(Y, Y ∗ )|X]. Prima abbiamo ricavato: E[L(Y, Ŷ )|X] = η(X)I{Ŷ (X) = 0}] + [1 − η(X)]I{Ŷ (X) = 1} (10) Da cui otteniamo: E[L(Y, Y ∗ )|X] = η(X)I{Y ∗ (X) = 0}] + [1 − η(X)]I{Y ∗ (X) = 1} (11) Quando η(X) < 12 , Y ∗ = 0, quindi E[L(Y, Y ∗ )|X] = η(X); Quando η(X) ≥ 12 , Y ∗ = 1, quindi E[L(Y, Y ∗ )|X] = 1 − η(X). Possiamo concludere che il rischio condizionato di Y ∗ è min{η(X), 1 − η(X)}. Ora, poiché il rischio incondizionato è uguale al valore atteso del rischio condizion- ato, per la legge delle aspettative iterate: E[L(Y, Y ∗ (X))] = E[E[L(Y, Y ∗ (X))|X]] = E[min{η(X), 1 − η(X)}] (12) Dato l’input x, il rischio condizionato sarà: E[L(Y, Y ∗ (x))|X = x] = min{η(x), 1 − η(x)} (13) 1.3.2 Problema multiclass Analizziamo il problema seguente. Y ∈ Y , con Y = {Y1 ,... , YK }. Per brevità Y = {1,... , K}; Supponiamo di conoscere i posterior: P (Y = k|X) = ηk (X); Consideriamo la Loss 0/1 : L(Y, Ŷ (X)) = I{Y 6= Ŷ (X)}. 9 Il classificatore ottimale di Bayes è dato da Y ∗ (X) = argmax ηk (X), ossia k=1,..., K Y ∗ (x) = k se la P (Y = k|X = x) è massima sull’insieme di tutti i posterior calcolati in x. Supponiamo che Y = {A, B, C}, X = {1, 2, 3, 4} e che i posterior siano: x=1 x=2 x=3 x=4 ηA (x) = P (Y = A|X = x) 0.0000 0.0090 0.2531 0.7895 ηB (x) = P (Y = B|X = x) 0.3226 0.8442 0.7420 0.2105 ηC (x) = P (Y = C|X = x) 0.6774 0.1467 0.0049 0.0000 Si calcola facilmente che: x=1 x=2 x=3 x=4 Y ∗ (x) C B B A Si dimostra che, in corrispondenza del punto x, il rischio condizionato del classificatore Bayesiano è: E[L(Y, Y ∗ )|X = x] = 1 − max η(x) = 1 − max P (Y = k|X = x) (14) k k Da ciò ne consegue che il BER sotto la Loss 0/1 nel problema multiclass è dato da: E[L(Y, Y ∗ (X))] = 1 − E[max ηk (X)] = 1 − E[max P (Y = k|X)] (15) k k Come si costruisce il vero classificatore ottimale? Dovrei conoscere la distribuzione congiunta di X e Y (ossia i posterior). La determinazione dell’EPE è importante non solo per quantificare il livello di errore che ci dobbiamo aspettare, ma anche per scegliere tra metodi e algoritmi alternativi. Tuttavia, il calcolo analitico del ris- chio atteso è spesso impossibile, anche quando si conoscono i posterior. Ci sono due meta-modi per costruire un classificatore: 1. Osserviamo sul train set le Y e le X e stimiamo la distribuzione condizionata di Y |X (i posterior) attraverso vari metodi, come i modelli di regressione. A questo meta-modo corrispondono i classificatori LDA, QDA e kNN; 2. Costruiamo direttamente un modello di regressione che approssima η(X). A tale meta-modo corrispondono i classificatori di tipo logistico. 1.4 Modello Bernoulliano-logistico Lineare ′ ′ Tipicamente, in un problema 2-class, Xn = {(y1 , x1 ),... , (yn , xn )} è il nostro ′ dataset , dove yi ∈ {0, 1}, e xi contiene features numeriche. 10