Machine Learning & Deep Learning

T

w x+b

1+e

( )

T

w x+ b =0

log e

T +b=0

w x

La dimostrazione* completa è sul tablet.

Questa è proprio l'equazione lineare che rappresenta una generica Retta, o più

in generale un Iperpiano. Di fatto la Logistic Regression è un classificatore

lineare. In particolare, se il rapporto tra le due equazioni (dentro il logaritmo) è

> 1 allora apparteniamo alla classe 0, se invece < 1, siamo nella classe 1.

Applicando i logaritmi avremo che se il rapporto è > 0 siamo nella classe 0, se

< 0 siamo nella classe 1. In poche parole:

T

- Se, Allora apparteniamo alla classe 0;

+b >0

w x

T

- Se, Allora apparteniamo alla classe 1;

+b <0

w x

Proprio in linea con quanto visto nei classificatori bayesiani, l'equazione

T rappresenta la superficie di separazione tra l'appartenenza ad una

+b=0

w x

classe piuttosto che all'atra, in questo caso ne sono due.

La funzione di classificazione sarà identica, cioè cerca la classe c che

massimizza la posterior:

Sotto è rappresentata la funzione vera e propria, detta Funzione Logistica

(che non è sempre la stessa), o Sigmoide. Praticamente la Logistic

T

Regression calcola uno score con , che poi “passa” ad una

+b

w x

sigmoide, per trasformarlo in una probabilità. Infatti, sostituendo alle funzioni

T

sottostanti , otteniamo proprio la funzione vista all’inizio. In questo

+b

w x

modo i numeri in output sono tutti tra 0 e 1, quindi abbiamo una probabilità

disponibile in uscita.

Se estendiamo le funzioni a più di due classi, per ogni classe c abbiamo un

vettore w e b. Nella prima funzione, al denominatore abbiamo la somma di

tutti i numeratori. In entrambe le formule, la prima vale per una qualsiasi

classe c tranne l'ultima, mentre la seconda si riferisce all'ultima classe, che ha

una rappresentazione diversa (più semplice), perché conoscendo tutti gli altri

valori basta fare 1- quei valori (proprio come è stato fatto nel caso binario).

N.B.: Il vettore w è sempre grande quanto x.

Ogni Classificatore Lineare Discriminativo, in fase di learning costruisce un

boundary di demarcazione che sia “ottimo”, risolvendo un problema di

ottimizzazione, sulla base di una Funzione Obiettivo (F.O.). Questa è

tipicamente diversa per ogni classificatore discriminativo.

La Logistic Regression utilizza la Maximum Conditional Log-Likelihood. Ciò

vuol dire che il set dei parametri teta (in questo caso i pesi w e b), con i quali

poi si genera la demarcazione, viene imparato in modo tale da massimizzare la

conditional Log-Likelihood.

L'obiettivo è quindi trovare il set di parametri teta che massimizzano la

sommatoria in slide.

Parte 3.3- Logistic Regression learning

Questa parte cerca di spiegare bene, come avviene la fase di addestramento

della Logistic Regression. La situazione, infatti, è molto più complessa di

come è esposta sulle slides.

logistic regression,

Come già detto, la in fase di learning, vuole imparare il

T

miglior demarcatore (lineare), dato dall’equazione, . Ciò si traduce

+b=0

w x

T

effettivamente nel trovare i parametri e . Inoltre, sappiamo anche

b

w

come lo fa, ossia cercando di Massimizzare la Conditional Log-Likelihood:

( )

argma x L θ , D

θ

Con: { }

( )

 T ∀ ∈

θ= w , b c Y , set di parametri

{ }

( )

D= x , y , dataset , elementi del dataset di training

 i i

La maximum conditiona likelihood può essere espressa come l prodotto delle

x y

probabilità condizionate per ogni coppia di e nel nostro set di dati:

i i

|

( = =x

P Y y X

i i

∏ ¿¿

¿ D { }

∈

={c }

Ponendoci in un contesto di classificazione binaria, quindi ,

Y 0,1

possiamo scrivere

|

( =1

P Y X=x i

|

(

(1−P =1 )

Y X=x i

∏ (1− )

y y

¿ ( )= ¿¿ ∗¿ ¿

L θ , D i i

¿ D

Gli esponenti sono dovuti al fatto che, se siamo in una classificazione binaria,

uno dei due contributi si annulla ad ogni fase della produttoria (varrà 0).

Questa ultima formula rappresenta la Likelihood. Se si passa alla Log-

Likelihood avremo: |

(

( =1 )

y log ​ P Y X=x

i i

∑ |

( )= (

¿+(1− ) ( =1 =x )¿ ¿

L θ , D y log ​ 1−P Y X

i i

¿ D

Semplicemente applicando le proprietà dei logaritmi.

N.B.: Massimizzare la Likelihood coincide con il Minimizzare il negativo

della Cross-Entropy.

La dimostrazione* completa è sul tablet e parte direttamente dall’ultima

osservazione.

Com’è osservabile, la funzione di massimizzazione ottenuta, non può essere

risolta in modo analitico (omega compare in modo non lineare). Per farlo si

utilizzano metodi iterativi, che convergono ad una soluzione (approssimata)

dopo tot iterazioni. Il metodo che vedremo è quello del Gradient Descent.

Parte 3.4- Metodo del Gradient Descent

Come detto, il Metodo a Discesa del Gradiente è iterativo ed approssimato.

In particolare, si tratta di una procedura per trovare i minimi di una funzione. Si

θ

sceglie inizialmente un valore , successivamente si calcola la derivata della

j

θ θ

α

funzione rispetto a quel , la si moltiplica per un e lo si sottrae a quel

j j

. Continuiamo finchè non abbiamo un'approssimazione sufficientemente

=θ

θ

piccola, cioè finchè non raggiungiamo un , che tipicamente coincide

new old

con il raggiungere un punto dove si ha un cambio di concavità (cioè, un

minimo, dove la derivata è 0 per ogni teta). Un’osservazione non banale è che

il Gradient Descent arriva a convergenza non appena trova un minimo locale

(non globale, il primo che trova). Perciò, tipicamente è meglio avere una

funzione convessa, che ammetta un solo minimo, in modo tale da calcolare

sempre un minimo globale, non solo locale. Nella sostanza, scegliamo un set di

parametri a caso (iniziale) e lo aggiorniamo utilizzando questo metodo, fino a

convergenza (o quasi).

Tutto ciò può essere riassunto in questo modo:

α

Il parametro è anche detto Learning Rate. È un numero tra 0 e 1 che ci dice

"quanto ci stiamo fidando della pendenza data dal gradiente". Se è molto basso

freniamo molto, ci fidiamo poco. T

Nel nostro caso, il parametro da considerare è , pertanto avremo una

w

derivata del tipo:

Si tratta di calcolare la derivata della funzione obiettivo rispetto alla k-esima

componente del vettore w. L’espressione tra parentesi ci dice quanto è distante

il nostro score (rapporto exp) dalla label (yi). Ciò è poi moltiplicato per la

feature k-esima di xi. Fatto per ogni xi abbiamo un vettore di derivate parziali.

Andiamo a dimostrare quest’ultima affermazione partendo dall’ultima

espressione della funzione da massimizzare (nella penultima immagine):

La dimostrazione* completa è sul tablet. T

α

Questo risultato va poi moltiplicato per e va sottratto a . Si ottiene un

w 0

T , che sarà soggetto allo stesso trattamento, fino a convergenza. Lo stesso

w 1

va fatto per b.

Il Gradient Descent in generale dipende da tre componenti:

1. Set dei parametri iniziale scelto. È una caratteristica cruciale, poiché

possono esserci delle scelte “sfortunate” che risultano difficili da

interpretare. In particolare, è possibile scegliere un set di parametri che

creano indecisione sulla direzione giusta del gradiente, o perché ci portano

troppo lontani dal minimo, oppure in posizioni a bassa pendenza della curva.

2. Step di Update. In soldoni comporta quanti elementi del dataset inserire

nella sommatoria entro la Likelihood. Ciò comporta una maggiore o minore

precisione del gradiente. Ci sono tre possibili scelte in generale:

- Si sceglie in base ad un solo elemento (Stocastico). Questo

comporta un calcolo velocissimo e semplice del gradiente, ma è

probabile avere del rumore, poiché non è detto che la direzione dei

gradienti successivi vada verso il minimo (il gradiente non è affidabile).

Nella pratica, la sommatoria scompare e si prende una sola coppia

(x )

, y .

i i

- Si sceglie in base a tutto il dataset (Batch). Si prendono tutti gli

elementi del Dataset, si fa la media e si utilizza come gradiente da cui

partire. Qui non abbiamo un gradiente "rumoroso" ed inaffidabile, però,

ad ogni step, bisogna calcolare ogni volta il gradiente di tutto il dataset e,

siccome il gradient Descent impiega moltissime iter per convergere, è

una scelta molto inefficiente. Nella pratica, la formula è completa.

- Si sceglie in base a pezzi di dataset (Minibatch Stocastico).

Questa è la via di mezzo, cioè, si calcola il gradiente su un piccolo

sottoinsieme, si fa la media e si parte con l'algoritmo. In questo modo

bilanciamo lentezza ad affidabilità del gradiente. Nella pratica si avrà una

sommatoria parziale di coppie.

α

3. Learning Rate . Per quanto riguarda il primo, implica la possibile scelta di

un set “sfortunato” (con del rumore), cioè si sceglie una condizione di

partenza difficile da valutare, nel senso che è difficiel trovare il verso giusto

del minimo (Es. se il punto è troppo lontano oppure se la curva ha una

pendenza troppo bassa). Questa decisione può essere presa tipicamente in

tre modi diversi:

La metodologia della discesa del gradiente è molto utilizzata nella sua forma

base. Ad oggi esistono dei metodi di ottimizzazione per arrivare a convergenza

con una velocità relativamente alta.

Segue un breve sunto sulle caratteristiche generali della Logistic Regression.

Sezione 4- Support Vector Machine (SVM)

Parte 4.1- Introduzione

Come visto, i metodi discriminativi calcolano un Boundary in grado di separare

un insieme di punti da un altro, risolvendo un problema di ottimizzazione. Dal

momento che esistono tantissime rette con questo scopo, possono essere

implementati altrettanti problemi di ottimizzazione per il loro calcolo. Per

Logistic Regression

esempio, la individua la demarcazione scegliendo i

parametri tali da massimizzare la Likelihood, ma è solo una di tante possibilità.

Ebbene, il Support Vector Machine (SVM), è un altro classificatore

discriminativo e parte dal presupposto che la retta migliore sia