Machine Learning and Deep Learning

Gradient Descent

Voglio imparare i parametri in modo da massimizzare la likelihood o minimizzare la negative binary cross entropy. Per fare questo ho bisogno di usare il gradient descent.

Il Gradient Descent è un metodo iterativo che migliora i parametri attraverso il gradiente. Siccome abbiamo un input e output multi-dimensionali, dobbiamo calcolare il Jacobiano, cioè il vettore (matrice in generale) delle derivate parziali.

Nel caso generale abbiamo un vettore di parametri per ogni funzione, quindi una matrice. Nel caso binario è la derivata della Loss function rispetto ai parametri uno alla volta.

Considero solo funzioni convesse, il Gradient Descent è un algoritmo di ottimizzazione iterativo usato per trovare il minimo di una funzione in un numero finito di step (la funzione ha un'unica soluzione).

L'idea

Ci sono tre strategie per applicare il gradient descent in un problema di classificazione:

1. Batch Gradient Descent: ad ogni step valuto la mia funzione per tutti i punti del dataset.
   • Passo nel dataset, faccio il gradiente per tutti i punti, faccio la media della direzione del gradiente e la uso per cambiare i parametri.
2. Minibatch Gradient Descent: se non voglio andare su tutto il dataset, ma solo su una parte,
   • scelgo punti e ad ogni step considero un gruppo random di punti.
3. Stochastic Gradient Descent: caso estremo, considero un singolo elemento.
   • Prendo un punto, faccio il gradiente e applico l'update ad ogni step.

La versione Batch ha come pro che ho un confronto di tutto il dataset e vado contro la "sfiga" di trovare pochi punti che puntano al minimo, infatti la maggior parte dei punti punterà verso il minimo e avrò un classificatore più robusto. Con lo Stochastic potrei essere sfortunato e trovare un punto che ha un

gradiente nella direzione sbagliata. Esistono ottimizzatori avanzati che permettono di cambiare durante il training.

Trade-Offs

• Velocità: la LR è più veloce di NB e LDA, ma il training time della LR è più alto delle altre.
• Storage: il numero dei parametri dipende dal numero delle classi e dalla dimensione dell'input. Ho bisogno di memorizzare parametri. È più basso di LDA, perché LDA ha bisogno di memorizzare la covariance matrix.
• Interpretabilità: molto interpretabile, perché ho un prodotto lineare tra parametri e input, guardo i parametri e le componenti del vettore dei parametri, quelle con score più alto sono collegate con le features che sono più importanti per il mio problema.
• Accuracy: se il numero di features aumenta, l'accuracy della LR è migliore della LDA, perché la gaussiana multivariata quando il numero di features aumenta molto è difficile da computare.

Il fatto della covariance matrix e poi la distribuzione potrebbe non essere più gaussiana. Con pochi dati si comporta peggio della KNN e non-linear decision boundaries. Machine Learning and DL Pagina 19

SVM (Support-Vector Machines)

mercoledì 9 ottobre 2019 10:34

Support Vector Machines è un classificatore discriminativo lineare, perché la relazione fra i parametri el'input vector è lineare, infatti è un prodotto scalare. In seguito vedremo che può essere generalizzato al caso non lineare usando il Kernel trick.

Consideriamo un classificatore lineare, ad esempio una retta:

Se sostituiamo i valori nell'equazione mettendo dei numeri, possiamo sapere se il punto si trova sopra, sotto o sulla linea:

Vogliamo sapere se c'è solo una retta che è quella ottima o se esistono diverse rette che mi classificano i punti in perfetto modo. In realtà ce ne sono diverse che mi classificano i punti in modo ottimale.

Con la SVM

Voglio trovare tra le rette, quella che mi massimizza la distanza tra i punti e la retta.

La retta ottima è quella che ha la maggiore distanza dal punto più vicino.

La distanza di un punto dalla retta in forma vettoriale è:

Voglio trovare la retta che mi massimizza

In particolare, sono interessato ai punti molto vicini alla retta e non a cambiare l'inclinazione (slope) della retta, attraverso parametri.

Quindi voglio risolvere due problemi:

1. Classificare tutti i punti nel modo corretto.
2. Massimizzare la distanza dei punti più vicini alla retta.

Considero un dataset e due classi.

Detto il margine, cioè il doppio della distanza, vogliamo che l'equazione della retta sia maggiore o uguale alla metà del margine, ovvero che il punto si trovi almeno a distanza dalla retta.

Se allora

Se allora

Posso mettere le due equazioni insieme in questo modo:

Non conosco , ma mi interessa solo massimizzarlo.

Per tutti i punti

La seconda viene detta Quadratic Programming Problem, cioè voglio minimizzare la quantità della prima riga soggetta alle condizioni (constraint) della seconda riga, una per ogni elemento.

Constrained Optimization Problem

Il Constrained Optimization Problem consiste nell'avere un problema di minimizzazione, soggetto a constraints (vincoli) positivi. Nella forma generale:

Machine Learning and DL Pagina 21

Nel caso della SVM:

La Lagrangiana è la funzione originale meno la somma degli per i constraints, con l'ipotesi che gli devono essere maggiori o uguali di 0:

Possiamo

1. Se per x abbiamo che f'(x) = 0, allora x si dice che il constraint è inattivo. La soluzione sarà un tale che f(x) = 0.
2. Se per x abbiamo che f'(x) ≠ 0, allora x si dice che il constraint è attivo. La soluzione sarà un tale che f(x) = 0.

Derivata della Lagrangiana uguale a 0
Queste condizioni sono necessarie per l'esistenza di un'unica soluzione, ma non sono sufficienti.

cioè può esserci una soluzione, ma non sono sicuro che questa sia quella ottimale. Se almeno una condizione non è verificata, allora non può esserci una soluzione. Queste condizioni diventano sufficienti solo nel caso in cui i constraint sono funzioni affini cioè lineari (affine functions, es. retta, piano...). Nel nostro caso i constraint sono sempre funzioni affini perché sono dei prodotti scalari tra i parametri e . Quindi nel caso in cui sono funzioni affini, è convessa ed e sono continuously differentiable (esiste la derivata prima ed è continua), allora esiste un'unica soluzione che soddisfa le KKT, che diventano necessarie e sufficienti.

Linear SVM Separable Case

Considerando il Constrained Optimization Problem per l'SVM abbiamo:

Con un dataset di elementi, la Lagrangiana e le condizioni diventano:

Machine Learning and DL Pagina 22

Se faccio le derivate di rispetto a e e le pongo uguali a 0 (prima condizione KKT), considerando,