Machine Learning and Deep Learning

Supervised Learning

mercoledì 9 ottobre 2019 12:05

Il Dataset è un set di record , che hanno una cardinalità e appartengono a uno spazio.

Ogni elemento del dataset ha attributi o features. L'elemento può essere decritto come un punto in

uno spazio -dimensionale o come un vettore fatto di componenti.

La Classe è la risposta al task che vogliamo risolvere

L'obiettivo del learning è di creare un modello che può predirre nuove classi di nuovi elementi.

Il processo di learning è composto da:

Training: imparare i parametri

- Testing: testare il modello su dati diversi dal training

-

Training Pipeline:

Comparo la classe con quella corretta, misuro l'errore e lo uso per migliorare il set di parametri.

Γ è un parametro non imparato.

Inference o Testing pipeline:

Nel test set non abbiamo le classi. Selezionamo i dati, li mettiamo nel model, usiamo i parametri che

abbiamo ottimizzato nel training e otteniamo la classe.

Learning: se dopo che ho presentato il training set al mio modello, ho imparato i parametri e la

performance è maggiore del random guessing, allora il mio sistema ha imparato qualcosa.

La distribuzione dei dati nel training deve essere uguale a quella del test.

Fundamental assumption i.i.d.: posso imparare qualcosa solo quando i dati di training e test vengono

dalla stessa distibuzione . Si dice che i campioni sono indipendentemente e indenticamente

Machine Learning and DL Pagina 1

dalla stessa distibuzione . Si dice che i campioni sono indipendentemente e indenticamente

distribuiti (i.i.d) dal training e testing.

Se alleno un face recognition algorithm in Cina e lo testo in Europa probabilmente il sistema non

funzionerà, questo perché le persone non sono i.i.d. L'errore misurato nel training sarà diverso da

quello del test (PAC theory).

Errore

Generalization error o Risk: è l'errore che un classificatore commette in fase di training e test. Mi dice

se il modello performa bene anche su dati mai visti.

È il valore atteso (la media in alcuni casi) di una indicator function, che mi dà 1 se predico la classe

giusta o 0 classe sbagliata. Quindi mi dice quante volte predico la classe sbagliata.

Non è proprio la media, ma è l'integrale della probabilità del campione per il valore.

Empirical risk: è fatto su un piccolo subset dei dati. È proprio la media empirica della mia funzione

errore su . Viene misurato sul test set.

Il primo è fatto su tutti gli elementi, mentre il secondo su un subset.

Quando testo un classificatore, misuro solo l'empirical risk perché il mio test set è un numero di

campioni definito.

Il generalization gap è la differenza dei due risk. Mi dice la differenza di performance tra il training e il

testing.

Se il nostro insieme dei campioni è i.i.d. per il dataset, allora l'errore nel training sarà uguale o

molto vicino all'errore nel testing.

Es. considero un dataset di 1000 elementi:

Risk: se scelgo i numeri in gruppi (1-100, 101-200, 201-300…), allora avrò un valor medio (AV) diverso

per ogni gruppo. i.i.d. AV=500.

Empirical risk: se invece prendo gruppi da 100 in modo casuale, allora tutti i valor medi

convergeranno in una gaussiana. In base a come scelgo i gruppi il centro della gaussiana avrà AV≈500.

Gli hyperparameters sono dei parametri che non possono essere imparati, non fanno parte

dell'optimization process. Per testare gli hyperparameters, dividiamo il dataset in un terzo set, detto

Validation set.

Metodi di Splitting

1) Train-Validation-Test (dataset grande):

Training: alleno i parametri della mia funzione in modo supervisionato

- Validation: provo diversi set di hyperparameters fin quando non ottengo l'accuracy che voglio

- Testing: testo il classificatore

- Machine Learning and DL Pagina 2

Set più grande

Gli split vanno fatti random per la i.i.d assumption e per non avere gli stessi set precedenti.

Gli split non vanno sovrapposti, perché nel test avremmo elementi del training che già sono corretti.

Anche del dataset devo fare lo shuffle, in modo da cambiare la distribuzione.

Alleniamo tanti modelli quanti sono i set di hyperparameters che vogliamo scegliere.

2) k-fold Crossvalidation:

Se il mio dataset è molto piccolo, potrei non avere un test set consistente.

Splitto uniformemente il set in k blocchi e ripeto training e set k volte, una per ogni blocco.

Uso un blocco per il test e i restanti k-1 per il training, ripeto questa procedura k volte.

Ottengo così k accuracies e la performance finale sarà la media delle k accuracies.

La quantità di labels (=classi, annotazioni, data) perse è minore rispetto al caso 1, perché perdo solo

quelle di un blocco che però riuserò negli step successivi.

Di solito vengono usate la 5-fold (figura) o la 10-fold crossvalidation.

In casi estremi (cioè dataset piccolissimo e voglio usare tutte le classi) si usa la 1-fold, in cui uso tutti

gli elementi del dataset per il training tranne uno per il test. Ripeto questa procedura volte.

Precision and Recall

Precision: numero di esempi positivi classificati correttamente diviso il numero totale di esempi

classificati positivi.

Se = 1, non ci sono falsi positivi FP=0, ma non significa che mi sta segnalando tutti gli eventi positivi

e potrei avere falsi negativi (es. se ho fuoco mi dice che ho fuoco, ma potrebbe non aver segnalato un

altro fuoco ).

Recall: numero di esempi positivi classificati correttamente diviso il numero totale di esempi

realmente positivi. Machine Learning and DL Pagina 3

realmente positivi.

Se = 1, non ci sono falsi negativi FN=0 e ricopro sicuramente tutti gli eventi positivi, ma potrei avere

falsi positivi. (es. dice sempre che ho fuoco anche quando non c'è fuoco ).

media armonica

F1-score:

Quando l'output non è un valore booleano, ma uno score, per ottenere una classe dobbiamo usare un

threshold. Variando il threshold cambiano sia che .

Otteniamo così una curva di correlazione tra precision e recall detta ROC Curve:

Recap

Se l'output è un numero o una classe, per misurare la performance vediamo quando la label e la

- classe predetta sono uguali e misuro l'accuracy di tutti i casi.

Se sono interessato ad un particolare evento e gli eventi non sono distibuiti uniformemente

- considero precision e recall.

Se l'output è uno score, metto un threshold e seleziono l'evento positivo, conto quanti ne sono

- e faccio precision e recall.

Statistical Output

Se l'output è una funzione densità di probabilità (pdf) posso:

1) Fare un threshold sulla probabilità e usare misure discrete. Ad esempio se il threshold è nello

score 0.5, se lo score è minore di 0.5 vado nella classe 0, se lo score è maggiore di 0.5 vado nella

classe 1.

2) Usare la distanza fra le distribuzioni pdf e :

Bhattacharrya coefficient:

- Misura di quanto le due distribuzioni tendono a sovrapporsi (overlap).

È max quando si sovrappongono, è min quando non si sovrappongono.

KL Divergence:

- Non è simmetrica, non posso scambiare e .

Misura la quantità di informazione persa quando uso per approssimare .

3) Cross Entropy.

Cross Entropy

Valuta il numero medio di bits per identificare un elemento codificato da una distribuzione , mentre

quella originale è . Sto approssimando con e sto campionando un elemento.

Voglio sapere di quanta informazione ho bisogno per scoprire che questi elementi vengono da .

Machine Learning and DL Pagina 4

Voglio sapere di quanta informazione ho bisogno per scoprire che questi elementi vengono da .

Kraft-McMillan: un valore può essere identificato da bits con probabilità .

Il valore atteso di rispetto a è:

La cross entropy può essere usata come misura del classification error.

Considero una distribuzione discreta con k possibili valori, dove k sono le classi da predire:

se appartiene alla classe . È un vettore con tutti 0 e un 1 dove è vera la condizione

- della classe.

è lo score predetto dal sistema alla classe i per l'elemento . È un vettore i cui elementi

- sommati danno 1. È l'output del classificatore.

Es:

Sommo 0.3 così come tutti i valori ottenuti con le altre classi e ottengo la cross entropy.

Binary Case:

In questo caso il threshold è nello score 0.5, perché se lo score è minore di 0.5 vado nella classe 0, se

lo score è maggiore di 0.5 vado nella classe 1.

Machine Learning and DL Pagina 5

Bayes Classification

mercoledì 9 ottobre 2019 12:05

Likelihood:

Fissata la classe , mi dice qual è la probabilità di avere il campione osservato in quella classe .

Prior probability :

Senza osservare , mi dice quanto probabile è .

Posso contare a priori i dati generici, ma non nel mio dataset.

Non prende in considerazione la mia conoscenza generale del problema.

Bayes rule:

Posterior probability:

Fisso il campione e voglio sapere la probabilità della classe .

Prendo la likelihood e la prior e applico la Bayes rule:

Strategie di Classificazione ,

Considero un dataset con con classi e un campione di test .

Ci sono sue strategie per risolvere un problema di classificazione:

Maximum Likelihood Classification:

- 1) Imparo da una likelihood per ogni classe

2) Valuto il campione per le likelihood

3) Calcolo la classe

Maximum Posterior Classification (metodo Bayesiano):

- 1) Imparo da una likelihood per ogni classe

2) Imparo da la prior per ogni classe, senza osservare niente

3) Applico la Bayes rule per ogni classe

4) Calcolo la classe

Differenze:

Nel primo caso uso una prior probability, che forza la likelihood a non abbassare la probabilità per le

classi improbabili.

La seconda è migliore perché prende in considerazione la mia conoscenza generale del problema.

Classificatore Bayes Optimal Classifier:

È un classificatore del tipo Max Posterior, che mi dà la predizione più probabile per un campione .

Usa la seguente classification function, che mappa un input in una classe :

Se misuriamo il valore atteso del massimo degli scores possibili, 1 meno questo valore mi da l'errore

minimo possibile, per questo è detto optimal:

Machine Learning and DL Pagina 6

Siamo in un caso ideale in cui il mio classificatore non commette errori, considero solo gli scores.

JOINT density estimation - Stima della probabilità composta

Il problema della density estimation è di valutare la probabilità di variabili random. Voglio stimare due

o più variabili che dipendono tra di loro, es. media e varianza di una gaussiana.

Dalla JOINT posso ottenere la probabilità condizionata e settare il mio classificatore.

Product rule of probability: e possono essere due vettori.

Posso fare una Joint Density Table con tutte le possibili combinazioni di e , prendo il mio dataset e

conto quante volte appartiene a .

Overfitting:

Il problema della Joint probability estimation è l'Overfitting: se una combinazione non appare mai nel

mio dataset, essa avrà probabilità 0. Il classificatore è troppo concentrato sul mio dataset ed è ristretto

ad un certo numero di casi (dataset troppo piccolo), quindi se non ho nel dataset una copia perfetta di

quello che voglio testare, esso non verrà classificato.

Si possono usare due approcci per la stima:

Parametric Maximum Likelihood density estimation (caso Continuo):

- Fisso una pdf parametrizzata da parametri che modificano la densità (es. la gaussiana è

parametrizzata da media e deviazione standard). Prendo il dataset, comincio con un set random

di parametri e valuto la funzione sul mio dataset, con l'obiettivo di massimizzare la likelihood di

tutto il dataset, cioè il prodotto della pdf per tutti gli elementi del dataset:

Devo stare attento perché se un solo elemento è 0, il prodotto sarà 0, per questo uso il

perché in questo modo ho una somma (log likelihood). Anche se ho delle pdf minori di 1,

moltiplicandole vanno a 0 lo stesso. Alla fine ottengo la probabilità di rispetto al dataset (es. se

ho una gaussiana la probabilità sarà sempre una gaussiana).

Non-parametric density estimation (caso Discreto):

- È un istogramma che conta il numero di valori che la variabile assume. Normalizzo i valori di

in modo che si sommino a 1, così ottengo la probabilità di data una classe o un set di classi.

In questo caso non prendo in considerazione la forma della distribuzione.

DIM , il

Dato un dataset di elementi e una distribuzione gaussiana 1D maximum likelihood

estimator mi dà il valore della media empirica e della varianza.

La log-likelihood sul dataset è: Machine Learning and DL Pagina 7

Per massimizzare la log-likelihood, faccio le derivate rispetto a e e le pongo uguali a :

Naive density estimator

Ritornando all'overfitting, esso può accadere con la Joint density estimator.

Se il dominio della Joint è molto grande, è molto difficile coprire tutti i possibili valori del dominio con

almeno un caso. In altre parole, una combinazione di valori può non essere presente nel mio dataset.

Es. se nel mio dataset non ho la combinazione {capelli rossi, occhi verdi, barba si}, quando vado

all'esterno potrei avere questa combinazione che però non verrà mai classificata dal mio modello.

Per risolvere questo problema di overfitting considero i tre attributi separatamente. Questo non sarà

buono come la JDE, ma ricopre meglio tutti i casi perché non ho bisogno di fare il prodotto cartesiano

tra gli attributi.

Questo è chiamato Naive density estimator e assume che tutte gli attributi random siano

indipendenti, quindi la Joint è semplicemente il prodotto delle singole probabilità:

Classificatore Naive Bayes

È un classificatore in cui la likelihood è il prodotto di tutte le singole likelihood fatte per ogni variabile:

Machine Learning and DL Pagina 8

La forma generale della funzione di classificazione è: Qui è presente anche la Prior

Dove i termini e sono le likelihood e derivano dalla Bayes rule:

Le seguenti funzioni sono dette marginal class conditional distributions:

Setup Classificatore Naive Bayes:

1) Fare la prior probability, cioè la sommatoria di quanti elementi appartengono a una classe fratto il

numero totale degli elementi del dataset:

2) Fare la conditional likelihood, cioè fare la likelihood data la classe. Devo decidere se farlo in Naive o

no e scelgo la distibuzione che voglio usare (gaussian, bernoulli, categorical, istogramma…).

Prendo gli elementi che appartengono a una classe specifica e faccio la maximum likelihood per la

classe.

Es: => likelihood => es. normal gaussian distr

=> prior, somma=1

Quando ho un nuovo campione da classificare, avrò:

Se è massimo in allora appartiene a , se è massimo in appartiene a e così via.

Non considero il denominatore della Bayes rule perché è comune a tutti e 3 ed è una costante di

normalizzazione.

Interpretazione geometrica dei classificatori

Se considero un vettore , esso è un punto in uno spazio -dimensionale.

In questo caso chiedo al classificatore di separare i punti dello spazio per stabilire a quale classe

appartiene il punto. Per fare ciò il classificatore deve disegnare un contorno di separazione per

separare le classi differenti, detto decision boundary.

Per un classificatore Naive Bayes, avente come likelihood una gaussiana, il decision boundary è:

Machine Learning and DL Pagina 9

Se considero solo due classi 0 e 1, il boundary (retta) sarà l'insieme dei punti in cui il classificatore mi

darà lo stesso score per classe 0 e classe 1 e la differenza degli scores sul boundary mi darà 0:

Il decision boundary è una funzione quadratica di :

Nel caso in cui ho più di 2 classi, devo considerare 2 classi alla volta e il boundary sarà piece-wise

quadratic (quadratico a due a due).

Trade-Offs

Velocità: learning e classification sono molto veloci.

- Storage: ho bisogno solo di memorizzare i parametri della funzione moltiplicati per le classi più lo

- stesso numero di prior probabilities.

Interpretabilità: guardando solo la likelihood posso dire quanto un attributo ha contribuito alla

- classificazione.

Accuracy: se PAC, il classificatore è minimo.

- Data: attenzione all'overfitting. Pdf funziona bene con molti dati.

- Machine Learning and DL Pagina 10

LDA (Linear Discriminant Analysis)

domenica 13 ottobre 2019 12:52

Un classificatore è detto Lineare LDA quando l'input e i parametri del classificatore sono lineari

insieme, ad esempio prod. scalare.

Da un punto di vista geometrico, si dice lineare quando il contorno del classificatore è lineare, ad

esempio l'equazione di una retta.

LDA è ancora un Bayes Optimal Classifier perché il setup è lo stesso: ho una likelihood per ogni classe,

applico la Bayes rule per ottenere la posterior…

L'unica ipotesi differente è che la funzione likelihood deve essere una gaussiana multi-dimensionale:

Σ

Dove è un vettore, è un vettore media e è la matrice di covarianza, ovvero una generalizzazione

della varianza nel caso multi-dimensionale.

Matrice di covarianza:

È una matrice quadrata semi-definita positiva , dove è il numero di features dell'elemento ,

con e .

Nel caso mono-dimensionale è la varianza:

Nel caso multi-dimensionale dobbiamo usare la forma quadratica (vettore per il suo trasposto) e la

matrice viene anche detta Shared Covariance: con e dimensione

dove

È detta covarianza perché misura al variare della classe1 quanto la classe2 cambia.

La funzione di classificazione per la LDA è: È come Bayes, ma qui non abbiamo bisogno

di features indipendenti

Come per Bayes, per ogni elemen