Gradient Descent cosa è e come funziona

AI, APPUNTI, INTELLIGENZA ARTIFICIALE Marzo 14, 2020

14-03-2020

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 $\sum$ 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:

$\inline x_{j}^{(i)} =$ valore della caratteristica j-esima nel i-esimo campione di training

$\inline x^{(i)} =$ 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ì:

$h_{\theta }(x)=\theta_{0} + \theta_{1}x_{1}+\theta_{2}x_{2}+\theta_{3}x_{3} + ... + \theta_{n}x_{n}$

Giusto per capire con un esempio, $\theta_{o}$ potrebbe essere il valore minimo di un immobile, $\theta_{1}$ il prezzo per metro quadro di un immobile, $\theta_{2}$ il prezzo per numero di servizi e così via dicendo… di conseguenza $x_{1}$ corrisponderà al numero di metri quadri, $x_{2}$ al numero dei servizi…

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

$h_{\theta}(x) = \begin{bmatrix} \theta_{0} & \theta_{1} & \cdots & \theta_{n} \end{bmatrix} \begin{bmatrix} x_{0}\\ x_{1}\\ \cdots\\ x_{n} \end{bmatrix} = \theta^{T}x$

ma per avere dal prodotto di cui sopra lo stesso risultato della funzione ipotesi si assume che $x_{0}=1$ 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 $J(\theta_{0},\theta_{1})$ . In tal caso il metodo iterativo del gradient descent lavorerà nel seguente modo:

– Inizializzazione di valori arbitrari di $\theta_{o}$ e $\theta_{1}$

– Calcolo dei nuovi valori di $\theta_{o}$ e $\theta_{1}$ che riducono $J(\theta_{0},\theta_{1})$

– Fermarsi quando si è raggiunto il minimo.

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

${\begin{aligned}&k=0\\&{\text{while }}\nabla f(\mathbf {x} _{k})\neq 0\\&\qquad {\text{calcolare la direzione di discesa }}\mathbf {p} _{k}:=-\nabla f(\mathbf {x} _{k})\\&\qquad {\text{calcolare il passo di discesa }}\alpha _{k}\\&\qquad \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad k=k+1\\&{\hbox{end}}.\end{aligned}}$

Vediamo cosa significa da un punto di vista matematico formale:

Ripetere fin quando i valori non raggiungono il minimo:

{ $\theta_{0} := \theta_{0} - \alpha\*\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}* (x^{(i)})-y^{(i)} )*x_{0}^{(i)}$

$\theta_{1} := \theta_{1} - \alpha\*\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}* (x^{(i)})-y^{(i)} )*x_{1}^{(i)}$

$\theta_{2} := \theta_{2} - \alpha\*\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}* (x^{(i)})-y^{(i)} )*x_{2}^{(i)}$

…

}

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:

$-1 \leq x_{(i)} \leq 1$

oppure tra -0.5 e 0.5

$-0.5 \leq x_{(i)} \leq 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:

$x_{(i)}:=\frac{x_{(i)} - \mu _{i} }{s_{i}}$

dove $\mu _{i}$ è la media dei valori idi ingresso ed $s_{i}$ è 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 $\alpha$ ( o learning rate). Per capire il valore coretto da scegliere per $\alpha$ 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 α.

Se vuoi farmi qualche richiesta o contattarmi per un aiuto riempi il seguente form

Comments

discesa del gradiente gradient descent