Statistical Learning - Classificazione (PDF)

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

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