Riassunto esame Fundamentals of machine learning, Prof. Seidenari Lorenzo, libro consigliato Recognition and Machine Learning, Bishop, Christopher M. Pattern

Introduction

Esame

Concordare assieme al Prof. un certo numero di articoli (2-3), studiare i metodi a fondo in dettaglio e reimplementare alcune delle tecniche esposte negli articoli e ottenere risultati sperimentali da queste reimplementazioni.

Outline corso Machine Learning versione da 9 CFU

• Modelli lineari generalizzati (Generalized Linear Models - GLM): loss functions, spazi di funzione, regolarizzatori, LM statistics, condizioni sulla risoluzione di problemi.
• Supervised learning: classificazione, regressione, structured output.
• Classificatori lineari: support vector machines (kernels).
• Teoria computazionale e dell’apprendimento.
• Bagging e boosting (combinazione di classificatori diversi).
• Unsupervised learning: stima della densità, clustering, manifold learning (dimensionality reduction), LM con dati mancanti, modelli generativi.
• Deep learning: basic notions, neural networks, addestramento, architetture, problematiche.
• Learning sequences, recurrent networks, testi, grafi.
• Ottimizzazione degli iperparametri.
• Meta learning.
• Adversarial learning.

Scenario

Scenario: ()

ML = cercare una sintetizzazione (un’approssimazione) di una funzione che risolve un dato problema per un input . Di base la differenza tra la formulazione standard dei problemi e il ML è che i problemi da affrontare con ML non hanno una funzione definita, ma appunto cerchiamo una sua approssimazione. Nel caso standard, e.g. trovare uno shortest path, la funzione è ben definita.

Apprendimento supervisionato

Scenario

I dati sono suddivisi in due componenti:

• → - Input (covariate) input space.
• → - Output (risposte) output space.

e.g. sentiment analysis (capire da un testo/linguaggio naturale se quel testo è di stampo positivo o negativo) è un insieme di documenti testuali (sequenza di caratteri ASCII) = {0, 1}

Condizione fondamentale: noi siamo in grado di raccogliere dei dati che arrivano in questa forma: () () → = {( , ) | = 1.. } (training) dataset supervisionato

dove () () ∈ ∈ {0, 1}() () ()

( , ) e la coppia è chiamato data point o example in cui ogni oggetto ha associato() ad esso una sua label . ∈ Φ

È un dataset appartenente all’insieme dei dataset e si ha che un algoritmo di Φ learning supervisionato è una funzione che mappa ogni possibile dataset in uno spazio di funzioni : : Φ → : → , ∈ Quella in particolare usata qui è()

Si ha in questo esempio che è una distribuzione di probabilità da cui viene estratto ogni() : () ∼ ()() () ()

Questo viene fatto passare attraverso un supervisore che associa ad una label() che classifica quella data . Si ha quindi che la label ha una distribuzione di probabilità che() dipende direttamente da : () ∼ ( = | = )

Si ha però spesso che la label corretta da associare a non è ovvia, in quanto le distribuzioni di probabilità (), (|) (, ) sono fissate ma sconosciute. (, )

Idealmente, avendo a disposizione nota potremmo creare una funzione tale che: : → | () = [( = |)]

In questo caso viene definito come classificatore ottimo. Si ha ovviamente che non è ottenibile.

L’obiettivo è quindi di cercare una funzione: : → che si comporti bene nella classificazione di dati nuovi e non ancora osservati. Tutto questo (, ) però si basa sul fatto che la distribuzione sia fissata, altrimenti se essa cambiasse nel tempo arriverebbe presto a diventare inutile. Idealmente dovrebbe minimizzare il valore atteso 1 1{() ≠ } = ∫ 1{() ≠ }(, ) = ∑ 1{() ≠ }||, (,)∈

dove è il test set, ovvero dati nuovi non osservati. Lo scopo quindi è la creazione di una () ≠ funzione che minimizza il valore atteso dei casi in cui : 1{() ≠ }∈ΩΩ

dove è definito come spazio delle ipotesi.

L’apprendimento supervisionato è infine un problema di ottimizzazione dove la funzione obiettivo non è osservata e ciò significa che minimizzare in modo ottimo non è possibile.

Descritto così quindi il problema dell’apprendimento supervisionato è malposto. In generale si semplifica il problema assumendo che i dati a disposizione (quelli precedenti) siano un buon esempio dei dati futuri: () (){ ( ) }1 → ∑ 1 ≠ può diventare NP-completo∈Ω =1 1

dove in generale al posto della funzione indicatrice che conta i numeri di errore di previsione, utilizzeremo le loss functions. () ()( , ) (, )

In particolare osserviamo che le coppie sono state campionate da in modo indipendente e identicamente distribuite (IID), ciò significa che i punti sono campionati sempre dalla stessa distribuzione e che il punto non influenza in alcun modo il ≠ campionamento del punto con . Formalmente si ha per l’indipendenza: () ()( )() = ∏ ,

Di base un algoritmo di apprendimento prende come input un dataset e una classe di Ω funzioni e restituisce una funzione che minimizza l’errore. I diversi algoritmi di apprendimento si contraddistinguono per quale funzione obiettivo minimizzano, per quale sentimento usano verso il risultato di questa ottimizzazione e infine su quale spazio di funzioni gli viene dato come input.

Regressione lineare

Sinonimo di apprendimento supervisionato con targets continui. Ciò significa che per ogni unità statistica abbiamo che la risposta è identificata da() ∈ mentre per quanto riguarda gli input si ha () ∈

con pari alla dimensione del vettore delle features.

Vogliamo quindi una funzione che mappa input in output in questo modo: : → in particolare vogliamo che sia lineare, ovvero vogliamo che: (, ) = in cui è un vettore di parametri. →

La soluzione di questo problema sarà in forma chiusa nell’ambito degli apprendimenti è uno dei pochi metodi che ha soluzione in forma chiusa. Inoltre questo modello è interpretabile e estendibile al caso non lineare.

A volte usa scrivere il modello in questo modo: (, ) = +

Ovviamente la natura delle variabili contenute in dipende dal campo di applicazione preciso. →

NB: gli attributi categorici vanno trattati in modo diverso dalle variabili booleane e reali pre-processing è richiesto, creando delle dummy variables booleane. Nelle neural networks addirittura ogni alternativa di una variabile categorica li rappresento ciascuno con un vettore.

Il dataset è composto da una collezione di coppie: () (){( ) } = , , = 1.. (, )

con la famiglia di funzioni: { }Ω = : → | () =

L’obiettivo è quindi di trovare (, ())∈Ω dove è una funzione di loss. (, ())

Il termine viene denominato rischio, ovvero una metrica che definisce quanto buona sia una certa funzione .

Notare che così esposto l’obiettivo è impossibile. Ciò che è possibile fare è trasformare l’obiettivo sopra in: () ()( ( ))1 (, ()) = ∑ , ∈Ω =1 ovvero trovare la funzione che minimizza l’errore sulla base dei dati del dataset . () ()( ( ) )1 ∑ , []

Infatti la quantità viene definita rischio empirico e denotato con . =1

La funzione di loss può essere esplicitata con: 21 →(, ()) = ( − () ) square loss2 che talvolta viene usata per facilità di calcolo in quanto la sua forma analitica è semplice.

Questa funzione di loss però genera problemi nel caso di outliers, in quanto il quadrato rende la differenza tra il valore atteso e il valore osservato ancora più grande.

Per rimediare a questo problema si può usare: →(, ()) = {0, | − ()| − ε} ε -insensitive loss

Ciò fa sì che nel caso di outliers si paghi comunque una quantità lineare, e nel caso di errori piccoli si paga 0.

Vi è anche una terza versione: { }21 1 →(, ()) = ( − ()) | − () | < 1 | − ()| − ℎ loss2 2 robusta

che viene chiamata robusta proprio per la sua resistenza agli outliers. Vicino a zero è uguale alla quadratica, lontana è uguale alla insensitive.

Metodo dei minimi quadrati

Abbreviato in OLS. L’idea è di avere una design matrix o matrice del disegno: × ∈()

in cui ogni riga contiene l’esempio i-esimo, o la i-esima unità statistica.

21 = | | − | |2 2

La condizione necessaria affinché sia possibile trovare l’argmin è che si annulli il gradiente: −1 ( ) ( − ) = 0 → = → = ( )→ = ()

Si ha quindi la necessità che sia invertibile () <

Significa quindi che è singolare se . Questo accade nel caso in cui una delle variabili di è combinazione lineare delle altre. Vi sono due casi in cui si ha() < :

• Correlazioni, ovvero attributi collineari o quasi collineari >>
• Alta dimensionalità di dati, ovvero

Per verificare preventivamente queste situazioni è possibile creare uno scatterplot in cui ogni variabile è contrapposta a ogni altra variabile, verificando eventuali dipendenze lineari o non lineari.

Proprietà dei minimi quadrati

Innanzitutto vanno fatte alcune assunzioni:

• I dati sono effettivamente stati generati da un modello lineare (con rumore additivo): = + ε
• Gli errori sono omoschedastici, ovvero la varianza degli errori è indipendente dall’unità statistica i-esima (è costante): ε ∼ ( 0, σ ) (|)
• Non è random, in quanto stiamo creando un modello di , ciò significa che è effettivamente data e nota. Non consideriamo quindi come una variabile aleatoria ma come una costante.

Date queste assunzioni si ha: −1 −1 −1 ( ) ( ) ( ) = = ( + ε) = + ε

Si ha quindi che, dato che gli errori sono normali, una trasformazione affine di una normale fa sì che anche risulti normale: ( )−1 2( ) ∼ , σ

L’unica variabilità in questo contesto è il rumore casuale aggiuntivo. Ciò significa che l’incertezza sul modello deriva dalla variabilità degli errori. Si ha però come vantaggio che: [ ] =

e che quindi OLS sono un metodo unbiased, ovvero non distorto. Attenzione: se uno stimatore è unbiased non significa per forza che commetta sempre errori piccoli.

Si può anche verificare se una certa variabile è significativa per la definizione della risposta tramite un test di ipotesi:

• Concretizzare un’ipotesi nulla.
• Formulare la statistica relativa all’ipotesi nulla.
• Verificare se la statistica calcolata risulta essere su una delle due code della gaussiana.
• Nel caso in cui si trovi lì non possiamo rifiutare l’ipotesi nulla, altrimenti rifiutiamo.

Varianza negli OLS

Prendiamo un qualunque stimatore lineare di : = e ipotizzo che il suo valore atteso sia effettivamente uguale a : [ ] =

Ciò significa che oltre ad essere lineare è anche unbiased. In queste condizioni definendo la matrice −1 ( )∆= − possiamo ricavare come −1 −1 −1⎡⎢ ⎤⎥ ⎡⎢ ⎤⎥ ⎡⎢ ⎤⎥ ( ) ( ) ( ) = + ∆ = + ∆ ( + ε ) = + ∆ + + ∆ ε⎣ ⎦ ⎣ ⎦ ⎣ ⎦

−1⎡⎢ ⎤⎥ ( ) + ∆ sappiamo però che che non è random perché è fissato. ⎣ ⎦

Si ha quindi che: [ ] = + ∆

dove l’unica possibilità è che ∆ = 0 ⇒ ∆ = 0

Quindi la varianza di : −1 −1⎡⎢ ⎤⎥⎡⎢ ⎤⎥ 2 2 ( ) ( ) ( ) = ( ) = × () × = σ = σ + ∆ + ∆ =⎣ ⎦⎣ ⎦2 ( )= + σ ∆∆

Si ha quindi che la varianza di un qualunque altro stimatore lineare unbiased è data dalla 2 σ ∆∆ varianza degli stimatori dei minimi quadrati più una quantità positiva . Ciò significa che OLS è lo stimatore lineare unbiased a varianza minima.

Questo passo si traduce nel teorema di Gauss-Markov: ( ) ≤ ( )

Può venire in mente che OLS sia il miglior algoritmo possibile da poter applicare nell’ambito del learning. (migliore = ottica di errore di predizione più piccolo)

È vero? NO.

Regolarizzazione

Decomposizione bias/varianza dell’errore: avendo una funzione di predizione () = = vogliamo prendere un altro possibile predittore tale che =

Qui è funzione del dataset, in quanto definisce . Entrambe sono variabili aleatorie.

Assumiamo sempre che i dati siano generati random con rumore gaussiano additivo.

Allora l’errore sarebbe: 2 = ( − )

dove non è random.

Posso quindi fare: 2 2 2 2( − ) = ( − ( ) + ( ) − ) =... = ( − ( ) ) + ( ( ) − ) + 2( − ( ) )( ( ) − )

dove ( − ( ) ) = 0 in quanto abbiamo dimostrato che se è costruita con essa è unbiased.

Ciò che rimane quindi è 2 2⎡⎣ ⎤⎦ = ( − ( ) ) + ( ( ) − )

in cui: 2⎡⎣ ⎤⎦ ( − ( ) ) = ( ) - 2( ( ) − ) = -

Questo passaggio è concretizzato dal fatto che un modello può essere troppo semplice e non riuscire in modo efficiente a fittare il modello, ma contemporaneamente troppo complesso e overfittare troppo il dataset.

Esercizio: Bishop

Avendo delle campionate da: ∼ () + ( 0, ε )

dove ∼ (0, 2π)

Per poter fittare una retta su un seno: 25 → ϕ() ∈ , ϕ () = 1−1|| ||−γ − 2π→ ϕ () = = 2.. 25 ϕ ()

È come se stessi prendendo per ogni intervallo una gaussiana centrata in la cui 2π1 ampiezza è regolata da . γ

Il modello a questo punto è concretizzato da: ( ) = ϕ()

La regolarizzazione punta a far diventare un problema mal posto in un problema ben posto. =

Se non ha rango pieno, allora non è invertibile e il problema dei minimi quadrati è mal posto. Si ha quindi che gli esempi forniti dal dataset non sono sufficienti per fornire una soluzione unica e fissarla.

Se invece ha quasi rango pieno, il che significa che gli autovalori più piccoli sono troppo vicini a 0, allora la soluzione non è stabile, in quanto i