Discesa del gradiente
![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Gradient_descent.svg/350px-Gradient_descent.svg.png)
In ottimizzazione e analisi numerica, il metodo di discesa del gradiente (detto anche metodo del gradiente, oppure metodo della massima discesa, o anche della discesa più ripida; in inglese gradient descent o steepest descent) è una tecnica che consente di determinare i punti di massimo e minimo di una funzione di più variabili. In particolare, il metodo va alla ricerca di punti che soddisfano condizioni di ottimalità (condizioni necessarie, sufficienti, necessarie e sufficienti all'ottimo).
Il metodo fu sviluppato, e pubblicato nel 1847, dal matematico francese Augustin-Louis Cauchy nel tentativo di risolvere il problema della determinazione dell'orbita di un corpo celeste a partire dalle sue equazioni del moto[1].
Esempio
[modifica | modifica wikitesto]Si supponga di voler minimizzare la funzione e si scelga come soluzione iniziale il vettore . Allora
e, muovendosi in un intorno di :
Questi calcoli mostrano che, per individuare dei punti - vicini a - in corrispondenza dei quali la funzione assume un valore minore di , conviene spostarsi lungo direzioni che abbiano la prima e la terza componente più piccole o seconda componente più grande. Inoltre esistono delle direzioni preferenziali lungo le quali la funzione decresce più velocemente (ad esempio scegliere una coordinata più piccola è preferibile rispetto a far diminuire ).
La procedura può essere iterata partendo da un nuovo punto, ad esempio , fino a individuare un minimo per . L'esempio mostra che una procedura che aggiorni la soluzione in modo iterativo sulla base delle informazioni disponibili localmente può portare a individuare un punto di minimo per la funzione assegnata.
Metodo
[modifica | modifica wikitesto]Descrizione
[modifica | modifica wikitesto]Con riferimento al seguente problema di ottimizzazione non vincolata,
il metodo del gradiente è una tecnica iterativa per la risoluzione di problemi di ottimizzazione non vincolati in cui a ogni passo , supposto diverso da zero, si sceglie come direzione di ricerca quella corrispondente a , ovvero la direzione dell'anti-gradiente (si ricordi a tal proposito che ogni generico vettore , con , identifica una direzione).
In particolare, il nome di "steepest descent method" deriva proprio da questa scelta. Non è difficile dimostrare infatti che la direzione dell'anti-gradiente è la direzione che minimizza (massimizza in modulo) il valore della derivata della funzione nel punto rispetto a qualsiasi altra direzione a norma euclidea unitaria. Si noti soprattutto il riferimento alla particolare norma utilizzata. Una direzione è ottima per una particolare norma presa in considerazione.
Possiamo dunque affermare che ad ogni iterazione la direzione è soluzione al seguente problema (vincolato)
La dimostrazione è immediata.
L'importanza di tale scelta in realtà risiede in altro. Si noti infatti che ad ogni iterazione, si ha che (angolo ottuso tra i due vettori), questo garantisce che se si fa uso di tecniche di ricerca unidimensionali nella scelta del passo lungo la direzione dell'anti-gradiente, si riesce a dare all'algoritmo proprietà di convergenza globali.
Se l'algoritmo ne fa uso, allora ad ogni iterazione, lo stato di aggiornamento della successione di punti prodotta diventa
dove corrisponde alla lunghezza del passo di discesa.
Esempi di tecniche di ricerca unidimensionali sono quelli che soddisfano le condizioni di accettabilità di Wolfe (sufficiente riduzione, sufficiente spostamento)
Ancora una volta è lasciata al lettore la possibilità di dare una interpretazione geometrica alla seconda condizione, condizione di sufficiente spostamento.
Si osservi tuttavia che l'algoritmo non garantisce convergenza a punti di minimo globale; in realtà non assicura nemmeno che il punto così trovato sia un punto di minimo locale. Tuttavia, se aggiungiamo a ipotesi di convessità su tutto il suo dominio di definizione, allora non solo si ha convergenza ad un punto di minimo locale ma tale punto è anche un punto di minimo globale per la funzione (unico nel caso di stretta convessità).
Algoritmo
[modifica | modifica wikitesto]Lo schema generale per l'ottimizzazione di una funzione mediante metodo del gradiente è il seguente:
Analisi della convergenza
[modifica | modifica wikitesto]Una volta descritto il metodo, il prossimo passo è studiarne la rapidità di convergenza. In particolare diamo un risultato (facilmente dimostrabile) circa la rapidità di convergenza (Q-convergenza) della successione di punti al punto .
Di conseguenza la prima ipotesi che si fa nello studio della rapidità di convergenza del metodo è la validità del seguente limite
Se le ipotesi prima enunciate sono valide, ovvero l'algoritmo fa uso di tecniche di ricerca unidimensionale, ed in particolare si assicura l'unicità del punto stazionario per la funzione, il limite sopra indicato converge.
Supponiamo allora di voler minimizzare la seguente funzione quadratica strettamente convessa
con matrice simmetrica definita positiva, e si indichino il suo autovalore massimo e minimo rispettivamente con e .
Tramite semplici passaggi algebrici, si arriva a dimostrare che
dando al gradiente rapidità di convergenza Q-lineare.
Si noti come dipende dal rapporto tra il massimo ed il minimo autovalore della matrice. Questo spiega perché il metodo non funziona bene nel caso di matrici mal condizionate.
Soluzione di sistemi lineari
[modifica | modifica wikitesto]Un caso particolare di applicazione del metodo del gradiente consiste nella risoluzione di sistemi lineari. Si può usare il metodo ordinario o alcune varianti.
Metodo del gradiente
[modifica | modifica wikitesto]Si supponga di risolvere un sistema lineare della forma
dove è una matrice simmetrica e definita positiva. Per le proprietà di la soluzione di tale problema è equivalente alla procedura di minimizzazione della forma quadratica associata:
Infatti:
da cui
Per la funzione si ha che la direzione di massima discesa nel punto è:
coincidente con il residuo del sistema lineare. Dunque la direzione di discesa scelta a ogni iterazione è .
Inoltre vale la seguente relazione:
- [2] che permette di calcolare analiticamente il passo ottimale[3]. Infatti, imponendo la condizione di stazionarietà
si ricava
L'algoritmo del metodo del gradiente per la risoluzione di sistemi lineari è dunque
In aritmetica floating point la condizione del ciclo while può essere valutata verificando che la norma del residuo non sia più piccola di una tolleranza impostata dall'utente.
Varianti
[modifica | modifica wikitesto]Metodo del gradiente precondizionato
[modifica | modifica wikitesto]In molti casi è possibile accelerare la velocità di convergenza dell'algoritmo migliorando le proprietà di condizionamento della matrice . Si introduca a tal fine una matrice di precondizionamento simmetrica e definita positiva.
Lo schema risolutivo in questo caso diventa[3]:
Metodo del gradiente coniugato
[modifica | modifica wikitesto]Il metodo del gradiente coniugato costituisce una variante del metodo del gradiente in cui viene effettuata una scelta diversa, ma particolarmente conveniente nel caso di sistemi lineari simmetrici e definiti positivi, per le direzioni di discesa . Tale scelta garantisce la convergenza del metodo (in aritmetica esatta) in un numero di iterazioni pari al più alla dimensione del sistema da risolvere.
Analisi dell'errore
[modifica | modifica wikitesto]È possibile dimostrare che l'errore commesso alla -esima iterazione del metodo del gradiente soddisfa la seguente stima[3]:
dove
indica il numero di condizionamento in norma di e è la norma indotta da .
Nel caso precondizionato vale la stessa stima con
Esempio di implementazione
[modifica | modifica wikitesto]Si riporta un esempio di possibile implementazione del metodo del gradiente nella versione precondizionata compatibile con i linguaggi di programmazione Octave e MATLAB.
function [xk] = grad_prec(A, b, x0, nmax, toll)
xk = x0;
iter = 0;
while ((norm(rk) >= toll) && (iter < nmax))
rk = b - A * xk;
zk = P \ rk;
alphak = zk' * rk / ((A * zk)' * zk);
xk = xk + alphak * zk;
iter = iter + 1;
end
if iter == nmax
warning('Convergenza non raggiunta in nmax iterazioni!');
end
end
Approssimazione stocastica
[modifica | modifica wikitesto]Quando la funzione obiettivo è troppo costosa da calcolare ad ogni iterazione, ma può essere scomposta in una somma di molti addendi (ad esempio, la somma del costo calcolato su ogni singolo record in un dataset), il gradiente può essere approssimato stocasticamente restringendo la somma su un sottinsieme di addendi ad ogni iterazione, metodo noto come discesa stocastica del gradiente.
Applicazione alle reti neurali artificiali
[modifica | modifica wikitesto]La discesa del gradiente è ampiamente utilizzata in statistica e apprendimento automatico per l'addestramento tramite apprendimento supervisionato di modelli come reti neurali artificiali e modelli grafici. Il principio è noto come regola delta, e consiste nel valutare il modello su un input il cui corrispondente output esatto sia noto, e correggere ciascun parametro del modello in una quantità proporzionale (ma di segno opposto) rispetto al suo contributo all'errore sul risultato. L'algoritmo usato nelle reti neurali per implementare questo principio è noto come retropropagazione dell'errore, che consiste in un'applicazione della discesa del gradiente, essendo il contributo di ciascun parametro all'errore del modello dato dalla derivata parziale della funzione di perdita rispetto al parametro stesso.
La regola, classificabile fra i metodi per l'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 ed è l'elemento fondamentale dell'algoritmo di retropropagazione dell'errore (backpropagation), alla base dell'approccio connessionista.
Data una rete in avanti con le proprietà sopra descritte, l'obiettivo che ci si prefigge è minimizzare la diversità tra i valori di attivazione delle unità di output della rete (ottenuti sommando i segnali provenienti dalle diverse unità di input moltiplicati per l'efficacia, o pesi sinaptici delle connessioni in ingresso), e i valori della risposta desiderata. Tale diversità viene quantificata attraverso una funzione di perdita. La funzione obiettivo che si vuole minimizzare è il valore atteso della perdita (in pratica la perdita media sui dati).
Per applicare il metodo del gradiente, la funzione di perdita deve essere derivabile rispetto ai valori di output . Una scelta adatta a problemi di regressione è lo scarto quadratico medio tra e (valutato per tutte le unità di output e per tutti i pattern d'apprendimento); per problemi di classificazione si può utilizzare la divergenza di Kullback-Leibler o equivalentemente l'entropia incrociata.
Nella fase di addestramento, variando i pesi sinaptici (parametri del modello) si può aumentare o diminuire la funzione obiettivo; la prestazione della rete sarà funzione delle variabili , e sarà massima quando si raggiunge il minimo della funzione obiettivo, il che si ottiene applicando il metodo del gradiente e aggiornando iterativamente i valori dei pesi sinaptici.
Poiché nelle applicazioni pratiche le dimensioni dei modelli e dei relativi dataset usati nell'addestramento sono molto grandi, in pratica si fa generalmente uso della discesa stocastica del gradiente per l'addestramento delle reti neurali e di altri modelli statistici e di apprendimento automatico.
Note
[modifica | modifica wikitesto]- ^ (EN) Cauchy and the Gradient Method (PDF), su math.uni-bielefeld.de. URL consultato il 20 giugno 2016.
- ^ Si è sfruttata la proprietà , valida se è simmetrica.
- ^ a b c Quarteroni, Sacco, Saleri.
Bibliografia
[modifica | modifica wikitesto]- A. Quarteroni, R. Sacco e F. Saleri, Matematica numerica, 4ª ed., Milano, Springer Verlag, 13 marzo 2014, ISBN 978-88-470-5643-5.
- Dispensa di un corso di "Complementi di ricerca operativa" (PDF), su homes.di.unimi.it. URL consultato il 20 giugno 2016.
Voci correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file sulla discesa del gradiente
Collegamenti esterni
[modifica | modifica wikitesto]- Metodi di ottimizzazione (PDF), su dmsa.unipd.it. URL consultato il 20 giugno 2016.
- Problemi di ottimizzazione non vincolata (PDF), su dis.uniroma1.it. URL consultato il 20 giugno 2016 (archiviato dall'url originale il 22 dicembre 2016).
- (EN) The Steepest Descent Algorithm for Unconstrained Optimization and a Bisection Line-search Method (PDF), su ocw.mit.edu. URL consultato il 20 giugno 2016.