Discesa del gradiente

Da Wikipedia, l'enciclopedia libera.
Illustrazione grafica del metodo per trovare il minimo su una superficie

La discesa del gradiente è una tecnica di ottimizzazione di tipo locale. Data una funzione matematica multidimensionale, la discesa del gradiente consente di trovare un minimo locale di questa funzione.

La tecnica consiste nel valutare, inizialmente in un punto scelto a caso nello spazio multidimensionale (primo punto), sia la funzione stessa sia il suo gradiente. Il gradiente, essendo una direzione di discesa indica la direzione in cui la funzione tende a un minimo. Si sceglie poi un altro punto (secondo punto) nella direzione indicata dal gradiente. Se la funzione al secondo punto ha un valore inferiore al valore calcolato al primo punto, la discesa può continuare, seguendo adesso però il gradiente calcolato al secondo punto, che potrebbe essere molto diverso dal gradiente calcolato al primo punto.

Per esempio, data una funzione di molte variabili y = f(x_1, x_2, \ldots x_n), si possono scegliere a caso valori per le x_1, x_2, \ldots, x_n nello spazio di interesse, dando un risultato iniziale y_0. Il gradiente si calcola perturbando ciascuno dei valori iniziali delle x_1, x_2, \ldots, x_n, cioè ricalcolando il valore della funzione f a posizioni in cui al valore iniziale di ciascun x_i si somma o si sottrae un valore minimo (epsilon). La differenza fra il valore originale e il valore perturbato è la derivata discreta in ciascuna dimensione. La stima del gradiente in ciascuna dimensione è proporzionale a questa derivata discreta.

Per continuare il nostro esempio, se la funzione fosse f(x_1, x_2, x_3) = x_1^2 - x_2 + x_3 e i punti iniziali fossero x_1 = 1, x_2 = 2, x_3 = 3 allora:

f(1, 2, 3) = 2,

f(1.1, 2, 3) = 2.21, f(1, 2.1, 3) = 1.9, f(1, 2, 3.1) = 2.1, f(1, 2, 2.9) = 1.9.

Si vede che per trovare un minimo di questa funzione conviene diminuire i valori di x_1 e x_3, e aumentare il valore di x_2. Si vede anche che diminuire il valore di x_1 minimizza la funzione circa due volte più velocemente che diminuire il valore di x_3 o aumentare il valore di x_2, quindi, volendo un cambiamento totale di circa \delta, si utilizzerá una formula tipo x_1' = x_1 - \frac{\delta}{2}, x_2' = x_2 + \frac{\delta}{4}, x_3' = x_3 - \frac{\delta}{4}.

Se la funzione al secondo punto dovesse avere un valore maggiore o uguale a quello calcolato al primo punto, o si è trovato un minimo locale per la funzione, oppure la distanza fra il primo e il secondo punto (per esempio il valore di \delta dell'esempio precedente) è eccessiva per questa funzione (quanto meno in questa zona dello spazio multidimensionale). I due casi si possono distinguere valutando la funzione in vari punti intermedi, perché nel caso del minimo locale i valori saranno simili, e altrimenti potranno essere molto diversi. Se non si è raggiunto un minimo locale, la ricerca può ricomiciare dal primo punto, magari usando una distanza minore.

La discesa di gradiente d'errore trova solo minimi locali di funzione. Può però anche esser utilizzata nella ricerca di un minimo globale, scegliendo a caso un nuovo punto iniziale una volta che si sia trovato un minimo locale, e ripetendo l'operazione moltissime volte. Se il numero di minimi della funzione è limitato e il numero di tentativi molto elevato, ci sono buone probabilità che prima o poi il minimo globale sarà identificato.

Soluzione iterativa di sistemi lineari[modifica | modifica sorgente]

Il metodo della discesa del gradiente può essere utilizzato anche per risolvere sistemi lineari, del tipo:

 A \mathbf x= \mathbf b

con A matrice quadrata simmetrica e definita positiva, eseguendo k iterazioni.

Ciò vale perché il minimo della forma quadratica Q:

 Q(x) = \frac{1}{2} \mathbf x^T A \mathbf x - \mathbf b^T \mathbf x

si trova nel punto in cui il cui gradiente (∇Q) è nullo, in quanto punto stazionario:

 \nabla Q = A \mathbf x - \mathbf b = 0

Perciò, definito x0 un vettore di partenza qualunque e x1 come:

\mathbf x_1 = \mathbf x_0 + \alpha \mathbf r_0 \qquad \alpha \in \mathbb{R}

ovvero come una perturbazione di x0 della quantità prodotto tra lo scalare α e il vettore residuo (r),[1] vediamo che l'opposto del gradiente di Q è uguale al residuo:

-\nabla Q = \mathbf b - A \mathbf x_k = \mathbf r_k

Ragionando graficamente su una superficie curva bidimensionale possiamo dunque immaginare che, una volta scelto di partenza un punto qualsiasi x0, seguendo la pendenza negativa (-∇Q) cerchiamo di avvicinarci al punto di minimo con passi del valore dei vettori αr, con α valore variabile a seconda dell'iterazione (utilizzando perciò un α dinamico = f(k), per migliorare la velocità di convergenza; altrimenti si può scegliere un α statico costante, sufficientemente piccolo).

Procedendo con sostituzione, passaggi algebrici e utilizzando proprietà delle matrici arriviamo a dire che:

 Q( \mathbf x_1 ) = \frac{1}{2} \alpha_0^2 \mathbf r_0^T A \mathbf r_0 - \alpha_0 \mathbf r_0^T \mathbf r_0

che, derivata su α:

 \frac{\partial Q( \mathbf x_1 )}{\partial \alpha_0} = \alpha_0 \mathbf r_0^T A \mathbf r_0 - \mathbf r_0^T \mathbf r_0

quindi α al passo k vale:

 \alpha_0 = \frac{\mathbf r_0^T \mathbf r_0}{\mathbf r_0^T A \mathbf r_0}

A questo punto è sufficiente iterare con  \mathbf x_{1,2,...,k}

Applicazione alle reti neurali artificiali[modifica | modifica sorgente]

La discesa sul gradiente d'errore è una caratteristica che descrive le prestazioni di una delle più semplici regole di apprendimento delle reti neurali: la regola delta.

La regola, una delle più classiche dell'apprendimento supervisionato, può essere applicata a reti neurali di tipo "in avanti" (cioè con propagazione unidirezionale dei segnali, in inglese feedforward) e permette di calcolare la differenza tra i valori di output che la rete ottiene e quelli che invece dovrebbe apprendere. La regola deve essere applicata a reti che usano unità di output ad attivazione continua e differenziabile e può essere definita precursore dell'algoritmo di retroazione (o in inglese: backpropagation), "cavallo di battaglia" dell'approccio connessionista.

Data una rete "in avanti" con le proprietà sopra descritte, il nostro compito è di minimizzare la differenza tra i valori di attivazione delle unità di output y dalla rete, ottenuti mediante la sommatoria dei segnali provenienti dalle unità di input (vettori di ingresso x) moltiplicati per l'efficacia delle connessioni provenienti dalle unità presinaptiche (vettori di pesi sinaptici w), e la risposta desiderata (vettori di pesi ideali t).

Le prestazioni della rete possono essere descritte da una funzione di costo (la funzione utilizza lo scarto quadratico medio tra y e t per ciascuna unità della rete sommato per tutte le unità di output e per tutti i pattern d'apprendimento) che desideriamo ridurre. La sua variazione dipende dalla modifica dell'efficacia dei pesi sinaptici che permettono alla rete di giungere all'apprendimento degli esempi presentati nella fase di addestramento. Il gradiente rappresenta la direzione di massima crescita della funzione e dipende dal valore delle connessioni w. Il nostro intento è ridurre al minimo lo scarto quadratico medio tra y e t modificando i pesi in direzione opposta al gradiente eseguendo una discesa del gradiente. Possiamo immaginare la funzione d'errore come una superficie n dimensionale, dove le n-dimensioni sono il numero di pesi sinaptici w, e il gradiente è la tangente alla superficie definito da un vettore di derivate parziali della funzione rispetto a ciascun peso sinaptico w.

Note[modifica | modifica sorgente]

  1. ^ Il residuo al passo k è la differenza tra la soluzione esatta e la soluzione ottenuta, ovvero:
    \mathbf r_k = \mathbf b - A \mathbf x_k

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica