Machine Learning - Appunti

Machine learning

Storia

1940-1974 - Nascita e anni d'oro

Primi calcolatori

Teoria della computazione (Turing) e dell'informazione (Shannon)

Nascita del concetto di neurone artificiale (McCullok e Pitts, 1943)

1974-1980 - Primo inverno

Scarsi risultati (poca capacità computazionale ed esplosione combinatoria non trattabile)

Riduzione degli investimenti

1980-1987 - Nuova primavera

Nuovo algoritmo di backpropagation

Finanziamento del governo giapponese per i calcolatori di "quinta generazione"

1987-1993 - Secondo inverno

Flop della quinta generazione

Le reti neurali non scalano a problemi complessi

1993-2011 - Tempi moderni

Hardware più potenti

Classificatori più robusti (SVM, Random Forest...)

Deep Blue batte Kasparov

Successi dell'IA in varie discipline

2011-Oggi - Deep learning

Utilizzo massiccio delle Convolutional Neural Networks (Yan LeCun 1989)

Il deep learning raggiunge e supera lo stato dell'arte in molte applicazioni

I big dell'ICT investono nell'intelligenza artificiale

Fondamenti

Pattern

• Esempio, campione, modello, entità definita a cui può essere assegnato un nome
• Numerici: Associati a caratteristiche misurabili; rappresentabili come vettore di numeri in uno spazio multidimensionale
• Categorici: Associati a caratteristiche qualitative
• Sequenze: Pattern sequenziale con relazioni spazio-temporali: video, audio...

Problemi di learning

• Classificazione: Assegnare una classe a un pattern (binaria o multi-classe). Il concetto di classe dipende dall'applicazione.
• Regressione: Assegnare un valore (continuo) a un pattern.
• Clustering: Individuare gruppi (cluster) di pattern con caratteristiche simili.
• Riduzione di dimensionalità: Ridurre il numero di dimensioni dei pattern in input.
• Apprendimento di un mapping da a con (L'obiettivo è rendere trattabili problemi con dimensionalità molto elevata senza perdere informazioni).
• Representation Learning: Apprendere le feature più importanti dei dati in input.

Apprendimento

• Supervisionato: Il training set è etichettato.
• Non supervisionato: Il training set è non etichettato.
• Semi-supervisionato: Il training set è etichettato parzialmente. (Analisi della distribuzione dei dati non etichettati).

Batch: L'addestramento è effettuato una sola volta su un training set dato.

Incrementale: Sono possibili ulteriori fasi di addestramento (rischio di catastrofic forgetting: la rete dimentica ciò che ha appreso in precedenza).

Naturale: Addestramento continuo (per tutta la vita). Coesistono approccio supervisionato e non supervisionato.

Parametri e funzione obiettivo

• Set di parametri: valore ottimo dei parametri
• L'apprendimento consiste nel determinare.
• Dato un training set Train, la funzione obiettivo può indicare:
  • L'ottimalità della soluzione (da massimizzare)
  • L'errore o perdita (loss-function da minimizzare)
• La funzione può essere ottimizzata in maniera:
  • Esplicita: calcolata dalla definizione matematica (calcolo dei parametri per gradiente=0)
  • Implicita: utilizzando metodi euristici

Iperparametri

Parametri che descrivono il modello di apprendimento. Spesso vanno modificati per raggiungere le prestazioni migliori. È buona norma automatizzare l'ottimizzazione degli iperparametri.

Valutazione delle prestazioni

Classificazione:

• L'accuratezza calcolata in questo modo potrebbe essere poco indicativa nel caso di un problema binario in cui una classe è molto rara: un classificatore che non la predice mai avrebbe un'accuratezza vicina al 100%...
• Un altro modo di valutare le prestazioni di un classificatore è la matrice di confusione: una matrice che ha sulle righe le classi true e sulle colonne le classi predicted; ogni entry (r,c) indica la percentuale di casi in cui il sistema ha predetto c un pattern di classe r.

Regressione: Indica la radice della media dei quadrati degli errori (calcolati come scostamenti tra valore vero e valore predetto).

Problemi Open Set e Closed Set

• Closed Set: Tutti i pattern considerati appartengono a una classe.
• Open Set: Alcuni pattern possono non appartenere a nessuna classe, 2 soluzioni:
  • Aggiungere una classe fittizia
  • Si consente al sistema di non classificare il pattern definendo una soglia minima di 'somiglianza'.

False Positive e False Negative

Dato un classificatore binario si ha che i pattern da classificare sono TotPattern = Positivi (P) + Negativi (N); il risultato della classificazione può essere:

• True Positive (TP): Un pattern positivo è stato assegnato ai positivi
• True Negative (TN): Un pattern negativo è stato assegnato ai negativi
• False Positive (FP): Un pattern negativo è stato assegnato ai positivi errore di tipo I o False
• False Negative (FN): Un pattern positivo è stato assegnato ai negativi errore di tipo II o Miss

È possibile calcolare le frequenze dei risultati in questo modo:

• 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 Characteristic)

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 stati indicati come tali?)

Tipicamente anche precision e recall dipendono dalla soglia.

Object Detection: AP e mAP

• AP (Average Precision): AUC calcolata sul grafico Recall/Precision per oggetti di una singola classe su tutto il database
• mAP (medium Average Precision): media delle AP su tutte le classi

Training, Validation, Test

Training: Insieme di pattern di addestramento per trovare

Validation: Insieme di pattern su cui tarare gli iperparametri.

Test: Insieme di pattern su cui valutare le prestazioni.

Esistono vari modi per separare i pattern in questi 3 set, per esempio dati 12000 pattern:

• Set disgiunti: 10000 training, 1000 validation e 1000 test
• K-fold Cross-Validation: 2000 Test, K=5 fold (partizioni) da 2000 pattern. Si esegue K volte il training scegliendo uno dei fold come validation e gli altri K-1 come training. La prestazione finale è la media/mediana delle K prestazioni su test.
• *Leave-one-out: Caso estremo di cross-validation in cui i fold hanno dimensione 1 (utile se si hanno pochi pattern).

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, ottimizzazione non efficace, iperparametri sbagliati.

Il loss decresce ma l'accuratezza non aumenta: loss function errata.

L'accuratezza non si avvicina al 100%: i gradi di libertà del sistema non sono sufficienti per gestire la complessità del problema.

Generalizzazione e Overfitting

Generalizzazione: Capacità di 'trasferire' sul 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.

I gradi di libertà influenzano la regolarità della soluzione (decision-boundary), che viene per questo spesso controllata aggiungendo un fattore regolarizzante che penalizza soluzioni irregolari (e.g. per le reti neurali che favorisce soluzioni senza pesi troppo elevati; oppure i casi in cui solo una parte dei pesi sono diversi da 0).

Classificazione

Approccio Bayesiano

Se tutte le distribuzioni delle classi sono note, l'approccio Bayesiano costituisce la soluzione ottima.

• Insieme di s classi
• Spazio di pattern d-dimensionali
• Probabilità a 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 dato x, ovvero 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 certezza 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 o 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 Kolmogorov-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 & egra)