Gradient Descent cosa è e come funziona

Avevo avuto già modo di parlare dell’algoritmo chiamato gradient descent o  algoritmo di discesa del gradiente. In questo articolo cercherò di generalizzare il tema e di approfondire il concetto anche da un punto di vista matematico.

Iniziamo a dire, che, in via generale, l’algoritmo della discesa del gradiente ci consente di calcolare in modo interattivo il minimo di una generica funzione J().

In ambito machine Learning, l’algoritmo è molto conosciuto perché consente di calcolare il minimo della funzione di costo J, che nel caso  della regressione, significa trovare la giusta funzione di ipotesi h che si adatta meglio al sistema che si sta studiando.

In questo articolo  spiegherò, pertanto, come utilizzare  l’algoritmo della discesa del gradiente nell’ipotesi, generale,  in cui la funzione J che si vuole minimizzare è dipendente da n variabili.  Per questo motivo  darò per scontato che conosciate le diverse notazione matematiche quale la sommatoria e che abbiate in minima parte conoscenza delle operazioni tra  matrici.

Regressione lineare multivariata

La regressione lineare con più variabili è conosciuta anche con il nome di “regressione lineare multivariata”.

Prima di addentrarci nei problemi matematici vediamo qualche definizione/notazione:

valore della caratteristica j-esima nel i-esimo campione di training valore dell’ i-esimo campione di training m = numero di campioni n = numero di variabili in gioco ( caratteristiche )

La funzione  di ipotesi h per n variabili possiamo scriverla così:

Giusto per capire  con un esempio, potrebbe essere il valore minimo di un immobile,   il prezzo per metro quadro di un immobile,  il prezzo per numero di servizi e così via dicendo… di conseguenza corrisponderà al  numero di metri quadri, al numero dei servizi…

Usando la notazione matriciale la funzione di Ipotesi precedente potrà essere scritta nel seguente modo:

ma per avere dal prodotto di cui sopra  lo stesso risultato della funzione ipotesi si assume che sempre.

Prima di andare avanti con i formalismi, riprendo qualche concetto già spiegato in un altro articolo.

Supponiamo di voler minimizzare  la funzione di costo  in caso di regressione , ovvero l’errore quadratico  . In tal caso il metodo iterativo del gradient descent lavorerà nel seguente modo:

– Inizializzazione di valori arbitrari di e

– Calcolo dei nuovi valori di e che riducono

– Fermarsi quando si è raggiunto il minimo.

L’algoritmo che implementa il metodo del gradiente discendente può essere scritto così:

Vediamo cosa significa da un punto di vista matematico formale:

Ripetere fin quando i valori non raggiungono il minimo: { … }

 

Pe ottenere una convergenza veloce uno degli accorgimenti da tenere presente, è quello di usare dei vettori di ingresso  normalizzati. Per intenderci nel caso di un modello  di regressione  per il calcolo del prezzo di un immobile, i valori possono essere molto diversi se si considerano da esempio come parametri di ingresso e non confrontabili  : il numero di metri quadri, il numero di servizi, il numero di stanze;  per rendere omogenei questi valori e facilitare il calcolo del minimo si devono usare degli algoritmi di normalizzazione. La  normalizzazione dei vettori di ingresso, infatti,  consente di accelerare la discesa del gradiente in quanto i valori di input saranno tutti approssimativamente nello stesso intervallo, il che evita che   θ  vari rapidamente su certi intervalli e lentamente su altri a secondo della direzione della discesa, il che potrebbe innescare delle oscillazioni nella convergenza rendendo inefficiente il processo.

Il modo per evitare, questi problemi , è, pertanto, quello di modificare gli intervalli delle variabili di ingresso  in modo che siano tutte pressoché uguali. Idealmente le variabili dovrebbero essere tutte comprese tra -1 e d 1:

oppure tra -0.5 e 0.5

Le due tecniche a nostra disposizione sono il feature scaling e la mean normalization.

Il feature scaling si ottiene facendo la divisione dei valori di input per l’intervallo  (ovvero il valore massimo –  il valore minimo) della variabile di input, il risultato dei valori sarà sempre compreso tra -1 e 1.

La mean normalization  si ottiene  effettuando la sottrazione della media delle variabili di input al valore   di input.

Per ottenere i valori normalizzati possiamo implementare entrambe queste tecniche,  usando la seguente formula:

dove è la media dei valori idi ingresso ed è la deviazione standard ovvero: (max – min) dei valori di ingresso.

Quando si effettua un’operazione di minimizzazione della funzione di costo bisogna tenere in considerazione alcuni spetti che possono aiutare per ottenere buoni risultati.

Uno tra tutti è la scelta opportuna del valore di ( o learning rate). Per capire il valore coretto da scegliere per potreste tracciare su un grafico valori  assunti dalla funzione di costo  J (θ)  in funzione del  numero di iterazioni sull’asse x.

In tal modo sarà possibile osservare  l’andamento del gradiente per cui che se J (θ) tenderà ad aumentare, probabilmente sarà necessario ridurre il valore di α.