Machine Learning - Appunti

L'accuratezza può essere calcolata come: Sistemi con soglia (DET e ROC)

Nei sistemi con soglia, i False Positive e False Negative sono legati alla soglia (t):

soglia elevata =

soglia ridotta =

Le due curve possono essere condensate in modo da 'nascondere' la soglia:

DET (Detection Error Tradeoff)

ROC (Receiver Operating Charateristic)

AUC - Area Under Curve

Dati due sistemi, il migliore è quello con la curva ROC 'più alta'. Se le curve si intersecano (quindi non c'è una curva sempre più alta di un'altra) è possibile fare un confronto utilizzando la prestazione media, calcolabile come integrale della curva ROC. Questo valore viene chiamato AUC.

Precision-Recall

Precision: quanto è accurato un sistema (ovvero, tra tutti i pattern che il sistema ha indicato come positivi, quanti effettivamente lo erano?)

Recall: quanto è selettivo un sistema (ovvero, tra tutti i pattern che erano effettivamente positivi, quanti)

sono pochi dati disponibili). In questo caso, si esegue il training K volte, lasciando fuori un solo pattern come validation, e si calcola la prestazione finale come la media/mediana delle K prestazioni su test.

Convergenza

Il primo obiettivo da perseguire nell'addestramento è la convergenza.

Si ha convergenza quando, all'aumentare delle iterazioni:

• Il loss ha andamento decrescente
• L'accuratezza ha andamento crescente

Se il loss non decresce, l'ottimizzazione non è efficace o gli iperparametri sono sbagliati.

Se il loss decresce ma l'accuratezza non aumenta, potrebbe essere dovuto a una loss function errata.

Se l'accuratezza non si avvicina al 100%, i gradi di libertà del sistema potrebbero non essere sufficienti per gestire la complessità del problema.

Generalizzazione e Overfitting

Generalizzazione: Capacità di 'trasferire' sull'Validation set l'accuratezza del Training set.

Si parla di Overfitting quando l'accuratezza sul Train è elevata ma non sul Valid. (Comune quando il Train è troppo piccolo oppure i gradi di libertà sono eccessivi)

È buona norma partire utilizzando un sistema con pochi gradi di libertà per poi eventualmente aumentarli.

priori di ovvero la probabilità che il prossimo pattern da classificare sia di classe densità di probabilità assoluta ovvero la densità di probabilità che il prossimo pattern da classificare sia x. densità di probabilità condizionale di x dato ovvero la densità di probabilità che il prossimo pattern sia x sotto l'ipotesi che la sua classe di appartenenza sia probabilità a posteriori di ovvero la probabilità che il prossimo pattern da classificare sia di classe dato che il pattern è x. L'approccio Bayesiano si basa sull'utilizzo del teorema di Bayes per calcolare le probabilità a posteriori.

posteriori di dato x ovveri la probabilità che avendo osservato il pattern x, la sua classe di appartenenza sia

Per il teorema di Bayes abbiamo che:

Classificatore di Bayes

Dato un pattern x e note le probabilità a priori e le densità di probabilità condizionali, si assegna x alla classe b per cui è massima la probabilità a posteriori

Con il classificatore di Bayes si ha in output, oltre alla classe di appartenenza di un certo pattern, anche un valore di confidenza. Se non si è interessati a questo valore può essere calcolato senza dividere per p(x)

Le probabilità condizionali non si conoscono in generale:

Approccio parametrico: si fanno ipotesi sulla forma delle distribuzioni; si utilizza quando si ha una ragionevole cretezza sulla distribuzione dei dati e il training set non è molto grande.

Approccio non parametrico: metodo Parzen Window, le densità si apprendono dai dati

Distribuzione Normale

Se la dimensionalità

è 1 (d=1)(valore medio) e (deviazione standard) possono essere ricavati dai dati per maximum likelihood. Se d>1 (assumiamo tutti vettori di tipo colonna), dove è il vettore medio (= ) e è la matrice di covarianza.: varianze degli ;sul grafico determinano l'allungamento sugli assi principali dell'ellisse: covarianze tra e ;e statisticamente indipendenti e correlati positivamente e correlati negativamente. Sul grafico determinano la rotazione dell'ellisse rispetto agli assi. La stima dei parametri per maximum likelihood è:oppure in forma estesa in forma estesa. Bayes Parametrico. Bisogna evitare di fare ipotesi azzardate sulla normalità delle densità di probabilità. Esistono dei metodi per valutare la rispondenza alla "normalità" delle distribuzioni (e.g test statistico basato su indice di Kolmokorov - Smirnov; modo empirico attraverso grafici). Se le distribuzioni risultano essere normali si può passare alla stima di.

e .Le probabilità a priori possono essere estratte dal training set, oppure essere poste tutte uguali tra loro.

Approcci non parametrici

Non vengono fatte ipotesi sulle distribuzioni dei pattern e le densità di probabilità sono stimate dal training set. (Metodi molto complessi per dimensionalità alte)

Stima della densità

La probabilità che un pattern x cada all'interno di R è

Dati n pattern indipendenti la probabilità che k cadano nella regione R è:

Il cui valore medio è quindi

Assumendo R (con volume V) piccola e che quindi non vari significativamente in essa:

Parzen Window

La regione R è chiamata finestra (window) ed è un ipercubo d-dimensionale definito dalla funzione :

Dato un generico ipercubo centrato nel pattern x con lato ( ), il numero di pattern del training set che cadono all'interno dell'ipercubo è:

da cui possiamo ricavare

Se la finestra è piccola (V è piccolo) la stima

è rumorosa e statisticamente instabile. Se la finestra è grande (V è grande) la stima è più stabile ma piuttosto vaga. Per ottenere convergenza la dimensione della finestra va calcolata tenendo conto del numero di campioni. Soft Kernel Nella pratica spesso non viene utilizzata la funzione ipercubo vista in precedenza. Vengono piuttosto utilizzate kernel function più soft in cui ogni pattern contribuisce alla stima di densità in un intorno di x (in questo modo i decision boundaries sono più regolari o smoothed). Le kernel function devono comunque essere funzioni di densità (con integrale sullo spazio = 1). E' possibile utilizzare per esempio la multinormale (con e ). Classificatore Nearest Neighbor (NN) Data una metrica (dist) nello spazio, il classificatore Nearest Neighbor classifica un pattern x con la stessa classe dell'elemento x' più vicino (La regola nearest neighbor produce una tassellazione di voronoi). Invece di

derivare dai dati le probabilità a posteriori si suppone che se x è vicino a x' allora

Il principale problema di questo approccio è che un eventuale outlier potrebbe far etichettare i pattern vicini in maniera errata. Un modo più robusto per affrontare il problema è utilizzare il classificatore k-NN.

k-Nearest Neighbor k-NN

k-NN determina i k elementi più vicini al pattern x; ogni pattern 'vota' per la classe cui esso appartiene; x viene assegnato alla classe con più voti.

Si dimostra che con un training set infinito, all'aumentare di k, l'errore converge a quello Bayesiano.

k è un iperparametro solitamente < 10 (per evitare di allontanarsi troppo dal punto di interesse)

Confidenza di Classificazione

Per estrarre una confidenza probabilistica sull'appartenenza di un pattern x ad una classe è sufficiente dividere i voti di ogni classe per i voti totali con confidenze

Complessità computazionale

NN e

k-NN possono essere abbastanza onerosi in termini di risorse per training set molto grandi (memorizzare i pattern; calcolare le distanze da tutti gli altri pattern). Spesso è utile memorizzare i dati in strutture dati spaziali (e.g kd-tree) che consentono di individuare i vicini senza una scansione esaustiva. Prototipi di Classi Un altro modo per ridurre l'utilizzo di risorse è selezionare/derivare dai pattern dei prototipi, utilizzando solo questi ultimi per la classificazione. Tecniche di: - editing: si cancellano pattern dal training set, senza derivarne di nuovo - condensing: i prototipi non appartenevano al TS e sono stati derivati - i prototipi permettono di calcolare meno distanze e avere una maggiore robustezza in merito a outliers e rumore dei dati. Un prototipo può essere derivato per esempio come vettore medio di una classe nel TS. Possono anche essere ottenuti più prototipi per ogni classe (vector quantization e clustering) Metriche per NN, k-NN La metrica dig set, e poi vengono applicati anche al test set.