Appunti di Fundamentals Of Machine Learnings

Fundamentals of Machine Learning 2022-2023

Indice

1 Introduzione 2

2 Preliminari matematici 9

2.1 Algebra lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Probabilità e statistica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Modelli lineari per la regressione 22

3.1 Geometric Curve Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2 Maximum Likelihood Estimation e Least Squares . . . . . . . . . . . . . . 23

3.3 Regressione lineare Bayesiana . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1 Decomposizione bias-varianza . . . . . . . . . . . . . . . . . . . . 31

3.3.2 Regressione lineare Bayesiana . . . . . . . . . . . . . . . . . . . . 34

4 Modelli lineari per la classificazione 39

4.1 Funzioni discriminanti lineari . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.1 Due classi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.2 Multiclasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.3 Least Squares per la classificazione . . . . . . . . . . . . . . . . . 42

4.1.4 Discriminante lineare di Fisher . . . . . . . . . . . . . . . . . . . 44

4.2 Modelli generativi probabilistici . . . . . . . . . . . . . . . . . . . . . . 47

4.2.1 Modelli generativi con input continui . . . . . . . . . . . . . . . . 48

4.3 Modelli discriminativi probabilistici . . . . . . . . . . . . . . . . . . . . 50

4.3.1 Regressione logistica . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.2 Regressione logistica Bayesiana . . . . . . . . . . . . . . . . . . . 53

5 Kernel machines 55

5.1 Maximum Margin Classifiers . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2 Soft Margin Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.3 SVM per problemi non lineari . . . . . . . . . . . . . . . . . . . . . . . . 62

5.3.1 Modo alternativo di ottenere la SVM primale . . . . . . . . . . . 63

5.3.2 Sguardo più approfondito alla forma duale della SVM . . . . . . . 64

5.3.3 Kernel trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.4 SVM nella pratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6 Modelli non parametrici 70

6.1 Tecniche di valutazione del classificatore . . . . . . . . . . . . . . . . . . 70

6.2 Istogrammi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3 Kernel Density Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.3.1 Nadaraya-Watson (o Kernel Regression) . . . . . . . . . . . . . . 77

ii Indice 1

6.4 K-Nearest Neighbors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.4.1 K-Nearest Neighbors Classification . . . . . . . . . . . . . . . . . 78

7 Unsupervised learning 80

7.1 K-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7.2 Gaussian Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.3 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . 89

7.3.1 Formulazione della massima varianza . . . . . . . . . . . . . . . . 91

7.3.2 Formulazione del minimo errore . . . . . . . . . . . . . . . . . . . 92

7.3.3 Applicazioni della PCA . . . . . . . . . . . . . . . . . . . . . . . 94

8 Ensemble models 98

8.1 Committees e Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

8.2 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

8.3 Tree Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

8.4 Conditional Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . 105

9 Deep learning 108

9.1 Connectionism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9.2 Fondamenti del Deep Learning . . . . . . . . . . . . . . . . . . . . . . . 117

9.2.1 Convolutional Neural Networks . . . . . . . . . . . . . . . . . . . 143

Capitolo 1 Introduzione

Machine learning

Il Machine Learning (o apprendimento automatico) è una branca dell’Intelligenza Artificiale (IA) che mira a dotare le macchine della capacità di apprendere informazioni dai dati in maniera autonoma.

Il Machine Learning può essere approssimativamente suddiviso in due macro categorie di approcci di apprendimento:

• Supervised Learning (apprendimento supervisionato), si riferisce ad una classe di approcci di apprendimento che mirano ad imparare a prevedere gli output a partire da informazioni in input fornite da un dataset costituito da coppie di input e di output. In altre parole, al modello vengono forniti degli esempi in input ed i rispettivi output desiderati con l’obiettivo di definire una regola generale che associ l’input all’output corretto.
• Unsupervised Learning (apprendimento non supervisionato), si riferisce ad una classe di approcci di apprendimento che cercano di imparare a prevedere gli output a partire da dati in input non etichettati, ovvero dati le cui classi non sono note a priori ma devono essere apprese automaticamente. Tale tecnica di apprendimento consiste quindi nel riclassificare ed organizzare i dati in input sulla base di caratteristiche comuni per cercare di effettuare previsioni sui successivi input. In altre parole, il modello ha lo scopo di trovare una struttura negli input forniti, senza che questi siano etichettati in alcun modo.

N.B: in realtà esiste uno spettro più ampio di tecniche di apprendimento, come weakly-supervised, semi-supervised, self-supervised, ecc…

Idealmente, con il Machine Learning vogliamo apprendere a partire da dati di addestramento, detti training data, per fare inferenza (inferences) su nuovi dati. In questo modo potremo modellare problemi di apprendimento, valutare le prestazioni dei sistemi di apprendimento e quantificare la fiducia (belief) nelle soluzioni ottenute.

Le componenti matematiche principali di un problema di Machine Learning sono:

• Uno spazio di input (input space) X (∈ Rm), ovvero lo spazio dei dati in ingresso, ed uno spazio di output (output space) Y (∈ Rn), ovvero lo spazio dei dati in uscita.
• Un’ipotesi generativa (generative assumption) di una funzione X → Y: h (spesso considereremo una funzione lineare che rappresenta la y = h(x) + ε funzione utilizzata dal modello per prevedere gli output). Tale ipotesi rappresenta la funzione che descrive al meglio l’obiettivo dell’apprendimento.

2 3

• Una densità di probabilità congiunta (joint probability density) sconosciuta su X ed Y. p(x, y)
• Uno spazio di ipotesi (hypothesis space) H di funzioni da X in Y, rappresenta l’insieme di tutte le possibili ipotesi legali del problema. Da tale insieme l’algoritmo di apprendimento determinerà la funzione (solo una) che descrive al meglio il modello.
• Una funzione loss (loss function) L Y × Y → R, rappresenta una funzione che mappa un evento (ovvero un insieme di risultati al quale viene assegnata una certa probabilità che accada) su un numero reale che rappresenta il costo associato a tale evento. La funzione loss quindi permette di misurare il grado di accuratezza del modello associato.

N.B: un problema di ottimizzazione cerca di minimizzare tale funzione loss.

Assumendo l’ipotesi dell’apprendimento l’obiettivo (learning objective) sarà:

∈ H, h Z∗ L(h(x), = arg min [L(h(x), = arg min h y)] y)p(x, y)dxdy Ep h∈H h∈H

Dovremo quindi studiare p che risulta essere sconosciuto. Non avendo informazioni su p dobbiamo ricorrere al campionamento, cioè campioneremo le coppie ∈ X × Y, (x ), yi i per (dove rappresenta la dimensione del dataset). In questo modo ∈ {1, } i ..., N N avremo che (ovvero consideriamo il campione simile alla densità di ∼(x ), y p(x, y)i i probabilità congiunta) e quindi possiamo approssimare l’obiettivo con la loss empirica attesa (empirical expected loss), ovvero:

N1 Z∗ XL(h(x), ≍ L(h(x = arg min arg min ), )h y)p(x, y)dxdy yi i Nh∈H h∈H i=1

Dovremo inoltre fare assunzioni su L, H, X Y, sulla minimizzazione e sugli spazi ed.

Esempio di regressione lineare

ES (problema di regressione lineare):

Consideriamo un esempio in cui i dati sono distribuiti come di seguito.

Idealmente y = f(x) + ε (dove ε rappresenta il Gaussian noise).

4 Capitolo 1. Introduzione

Il nostro obiettivo è quello di utilizzare questo dataset di addestramento (training set) per effettuare delle previsioni, cioè per prevedere l’obiettivo (detto target) ŷ = f(x̂) per un nuovo dato x̂.

In questo modo stiamo implicitamente cercando di capire quale sia la funzione sottostante f.

N.B: l’apprendimento dovrebbe risultare indipendente da ε.

Esempio di discriminazione delle sorgenti

ES:

A volte vorremo capire come i dati vengono generati da N sorgenti, con l’obiettivo di discriminare le sorgenti l’una dall’altra (attribuendo delle classi ad ogni sorgente simile).

L’idea generale è quella di trovare un iperpiano di separazione (separating hyperplane) che separa una classe dall’altra.

Uno degli obiettivi di questo problema di discriminazione (discrimination problem) risulta essere quella di individuare quale sia il migliore piano di separazione tra le classi, poiché potrebbero esistere più iperpiani contemporaneamente.

5

N.B: quando stimiamo i parametri di un modello (processo di inferenza (inference)) è necessario applicare tutte le informazioni a nostra disposizione. In particolare dobbiamo fare attenzione a quantificare ogni volta che è possibile la nostra credenza (belief).

Esempio di regressione con variabile target

ES:

Tornando al problema di regressione, osserviamo una variabile di input x a valori reali e vogliamo prevedere una variabile target t a valori reali. A scopo dimostrativo consideriamo un esempio in cui i dati sono generati sinteticamente secondo y = f(x|w~) + ε (dove y rappresenta l’output del modello, x rappresenta il dato in input e w~ rappresenta un vettore di parametri del modello).

Quindi ci viene fornito un training set di coppie (x, y) campionate da p(x, y) con l’obiettivo di imparare una funzione sottostante f che ha generato tali dati.

In questo modo, per un nuovo dato x̂ non ancora visto in precedenza possiamo utilizzare la funzione imparata f(x̂|w~∗) per predire il target ŷ.

6 Capitolo 1. Introduzione

Figura 1.1: Grafico di un dataset di addestramento di punti N = 10, rappresentati da cerchi blu, ognuno dei quali è costituito da un’osservazione della variabile d’ingresso x e della corrispondente variabile target t.

La curva verde mostra la funzione sin(2x) utilizzata per generare i dati.

Il nostro obiettivo è quello di prevedere il valore di t̂ per un nuovo valore di input x̂, senza conoscere la curva verde.

Modelliamo questo problema come un adattamento di una curva (curve fitting), per esempio utilizzando un modello modello polinomiale:

M M j2 X | = + + + + = y(x w)~ w w x w x ... w x w x M j0 1 2 j=0

Notiamo che, anche se y(x|w~) è una funzione non lineare di x, risulta comunque essere una funzione lineare nei coefficienti w~ (ovvero i parametri del modello).

Quindi, per apprendimento si intende la stima dei migliori parametri w~ a partire dal dataset D {(x | }. = ) = 1,, y i ..., Ni i

Per fare ciò possiamo iniziare pensando di misurare l’errore della funzione stimata in termini dei data osservati, ovvero:

1 2 XL( | D) {y(x, −=w~ w)~ t}2 (x,t)∈D

7

Figura 1.2: Funzione di errore corrispondente a metà della somma dei quadrati degli spostamenti (indicati dalle barre verdi verticali) di ciascun input dalla funzione y(x, w).

Tale funzione risulta essere quadratica in w~ e di conseguenza le sue derivate "#! ∂L ∂L ∂L sono lineari. Inoltre ha un ∇ L( | D) L( | D)=w~ , , ..., w~w~ ∂w ∂w ∂w M0 1 unico minimizzatore w~∗.

N.B: c’è un iperparametro del modello che abbiamo dimenticato, ovvero l’ordine del polinomio M.

8 Capitolo 1. Introduzione

Più tale iperparametro cresce, più la nostra funzione si adatterà ai dati.

Notiamo che:

• Se tale iperparametro risulta essere troppo piccolo (ad esempio M = 0 oppure M = 1), allora la funzione di apprendimento non riesce a modellare i dati di addestramento e di conseguenza non può generare nuovi dati in maniera corretta (tale problema è detto underfitting).
• Se tale iperparametro risulta essere troppo elevato (M = 9), allora la funzione di apprendimento sarà troppo vincolata ai dati di addestramento (avremo appreso anche i rumori del modello) e quindi non risulta essere una buona predittrice (tale problema è detto overfitting).

Per capire l’underfitting e l’overfitting possiamo utilizzare la radice quadratica media (Root Mean Square), in cui la divisione per q w~∗ |D) 2L( = E N RMS N ci permette di confrontare in modo paritario dataset di dimensioni diverse e la radice quadrata garantisce che l’E RMS sia misurato sulla stessa scala della variabile target t.

Figura 1.3: Grafici dell’errore quadratico medio valutato su un training dataset e su un testing dataset indipendente per vari valori di M.

Dalla figura si nota che piccoli valori di M danno valori relativamente grandi di errore nel testing dataset (questo perché i polinomi corrispondenti non sono in grado di catturare le oscillazioni della funzione sin(2πx)), mentre valori di M compresi nell’intervallo 3 ≤ M ≤ 8 danno valori piccoli di errore per il testing dataset e forniscono rappresentazioni ragionevoli della funzione generatrice sin(2x). Per M = 9 l’errore del training dataset si azzera, perché questo polinomio contiene 10 gradi di libertà corrispondenti ai coefficienti w0, ..., w9 e quindi può essere regolata esattamente sui dati dell’insieme di addestramento. Tuttavia, l’errore del testing dataset diventa molto grande.

Il problema rimanente è quello della selezione del modello più adatto (elemento fondamentale del Machine Learning).

Capitolo 2 Preliminari matematici

L’algebra lineare risulta essere un argomento centrale del Machine Learning poiché ci permette di trattare i dati con un’alta dimensionalità. Questo ci consentirà di modellare gli input agli algoritmi di Machine Learning come punti in spazi ad alta dimensionalità e successivamente modellare le trasformazioni funzionali di questi input in spazi di features. Infine ci consentirà di modellare le trasformazioni successive che portano agli output.

La probabilità e la statistica risultano essere argomenti meno centrali per il Machine Learning rispetto all’algebra lineare. A volte si vuole poter dare un’interpretazione probabilistica ad un modello. Tuttavia la maggior parte dei modelli di Deep Learning (particolari modelli di Machine Learning) sono definiti come pure trasformazioni degli input in output. Perciò, la statistica e la probabilità risulteranno essere strumenti molto utili per analizzare i risultati.

Per molti problemi vorremo che i nostri modelli producano una distribuzione di probabilità sui possibili risultati. Ad esempio, un semplice problema di classificazione risulta essere quello di classificare la cifra raffigurata in un’immagine data in input al modello.

Per altri problemi, invece, vorremo poter qualificare gli output del modello. Ad esempio, in molti problemi di regressione in cui gli output di alcuni punti potrebbero risultare più certi di altri output.

9

10 Capitolo 2. Preliminari matematici

Molti problemi di apprendimento sono formulati come problemi di ottimizzazione in variabili multiple e quindi in questi casi apprendere significa stimare questi problemi minimizzando qualche funzione obiettivo.

2.1 Algebra lineare

Un vettore è un oggetto matematico che ha sia una grandezza che una direzione.

I vettori descrivono rette, piani ed iperpiani nello spazio permettendo di eseguire calcoli in spazi multidimensionali.

Adottiamo la seguente notazione per specificare un vettore di dimensione n:

  v0 v   1 h i .. T n   ∈ v v . . . v = = (~v )~v ~v R. n0 1       vn

Definizioni (operazioni fondamentali sui vettori):

• Somma tra vettori: dati due vettori ~u e ~v (con ~u, ~v ∈ Rn), allora w~ = ~u + ~v (dove definiamo wi = ui + vi).
• Moltiplicazione scalare: dato un vettore ~v ∈ Rn, allora per ogni c ∈ R w~ = c~v (dove definiamo wi = cvi).
• Prodotto scalare (o dot): dati due vettori ~u e ~v (con ~u, ~v ∈ Rn), definiamo il prodotto scalare tra ~u e ~v come: n X · = ~u ~v u vi i i=1

2.1. Algebra lineare 11

N.B: il prodotto scalare tra due vettori è relativo alle direzioni e alle grandezze dei due vettori.

N.B: possiamo facilmente trovare il coseno tra due qualsiasi vettori ~u e ~v considerando l’angolo compreso tra qu