Discesa del gradiente

Illustrazione grafica del metodo per trovare il minimo su una superficie

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.

Esempio

Si supponga di voler minimizzare la funzione$f(x_{1},x_{2},x_{3})=x_{1}^{2}-x_{2}+x_{3}$ e si scelga come soluzione iniziale il vettore $\mathbf {x} _{0}=[1,2,3]^{T}$. Allora

$f(\mathbf {x} _{0})=2$

e, muovendosi in un intorno di $\mathbf {x} _{0}$:

${\begin{aligned}f(1.1,2,3)&=2.21,\\f(0.9,2,3)&=1.81,\\f(1,2.1,3)&=1.9,\\f(1,1.9,3)&=2.1,\\f(1,2,3.1)&=2.1,\\f(1,2,2.9)&=1.9.\end{aligned}}$

Questi calcoli mostrano che, per individuare dei punti - vicini a $\mathbf {x} _{0}$ - in corrispondenza dei quali la funzione assume un valore minore di $f(\mathbf {x} _{0})$, conviene spostarsi lungo direzioni che abbiano la prima e la terza componente $x_{1},x_{3}$ più piccole o seconda componente $x_{2}$ più grande. Inoltre esistono delle direzioni preferenziali lungo le quali la funzione $f$ decresce più velocemente (ad esempio scegliere una coordinata $x_{1}$ più piccola è preferibile rispetto a far diminuire $x_{3}$).

La procedura può essere iterata partendo da un nuovo punto, ad esempio $\mathbf {x} _{1}=[0.9,2,3]^{T}$, fino a individuare un minimo per $f$. 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

Descrizione

Con riferimento al seguente problema di ottimizzazione non vincolata,

${\begin{cases}\min f(x)\\x\in \mathbb {R} ^{n}\end{cases}}$

il metodo del gradiente è una tecnica iterativa per la risoluzione di problemi di ottimizzazione non vincolati in cui a ogni passo $k$, supposto $\nabla f(x_{k})$ diverso da zero, si sceglie come direzione di ricerca quella corrispondente a $d_{k}=-\nabla f(x_{k})$, ovvero la direzione dell'anti-gradiente (si ricordi a tal proposito che ogni generico vettore $d\in R^{n}$, con $d\neq 0$, 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 $f$ nel punto $x_{k}$ 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 $d_{k}=-\nabla f(x_{k})$ è soluzione al seguente problema (vincolato)

${\begin{cases}\min \nabla f(x_{k})^{T}d_{k}\\\|d_{k}\|_{2}=1\end{cases}}$

La dimostrazione è immediata.

L'importanza di tale scelta in realtà risiede in altro. Si noti infatti che ad ogni iterazione, si ha che $\nabla f(x_{k})^{T}d_{k}<0$ (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

$\mathbf {x} _{k+1}=\mathbf {x} _{k}-\alpha _{k}\mathbf {\nabla } f(x_{k})$

dove $\alpha _{k}\in \mathbb {R} ^{+}$ 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)

$f(x_{k}+a_{k}d_{k})\leq f(x_{k})+\gamma a_{k}\nabla f(x_{k})^{T}d_{k},\gamma \in (0,1/2)$

$\nabla f(x_{k}+a_{k}d_{k})^{T}d_{k}\leq \sigma \nabla f(x_{k})^{T}d_{k},\sigma \in (\gamma ,1)$

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 $f$ 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

Lo schema generale per l'ottimizzazione di una funzione $f(\mathbf {x} )$ mediante metodo del gradiente è il seguente:

${\begin{aligned}&x_{0}\in R^{n},k=0\\&{\text{while }}\nabla f(\mathbf {x} _{k})\neq 0\\&\qquad {\text{calcolare la direzione di discesa }}\mathbf {d} _{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 {d} _{k}\\&\qquad k=k+1\\&{\hbox{end}}.\end{aligned}}$

Analisi della convergenza

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 $\{x_{k}\}$ al punto $x_{p}:\nabla f(x_{p})=0$.

Di conseguenza la prima ipotesi che si fa nello studio della rapidità di convergenza del metodo è la validità del seguente limite

$\{x_{k}\}\rightarrow x_{p}(k\rightarrow \infty )$

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

$f(x)=x^{T}Qx$

con $Q$ matrice simmetrica definita positiva, e si indichino il suo autovalore massimo e minimo rispettivamente con $\lambda _{M}$ e $\lambda _{m}$.

Tramite semplici passaggi algebrici, si arriva a dimostrare che

$||x_{k+1}-x_{p}||_{2}\leq {\biggl (}{\frac {\lambda _{M}}{\lambda _{m}}}{\Biggr )}^{1/2}{\Biggl (}{\frac {\lambda _{M}-\lambda _{m}}{\lambda _{M}+\lambda _{m}}}{\Biggr )}||x_{k}-x_{p}||_{2}$

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

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

Si supponga di risolvere un sistema lineare della forma

$A\mathbf {x} =\mathbf {b} ,$

dove $A$ è una matrice simmetrica e definita positiva. Per le proprietà di $A$ la soluzione di tale problema è equivalente alla procedura di minimizzazione della forma quadratica associata:

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

Infatti:

$\nabla Q(\mathbf {x} )=A\mathbf {x} -\mathbf {b}$

da cui

$\nabla Q(\mathbf {x} )=0\Leftrightarrow A\mathbf {x} =\mathbf {b} .$

Per la funzione $Q$ si ha che la direzione di massima discesa nel punto $\mathbf {x} _{k}$ è:

$-\nabla Q(\mathbf {x} _{k})=\mathbf {b} -A\mathbf {x} _{k}=:\mathbf {r} _{k},$

coincidente con il residuo $\mathbf {r} _{k}$ del sistema lineare. Dunque la direzione di discesa scelta a ogni iterazione è $\mathbf {p} _{k}=\mathbf {r} _{k}$.

Inoltre vale la seguente relazione:

${\tilde {Q}}(\alpha _{k}):=Q(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})={\frac {1}{2}}(\mathbf {p} _{k}^{T}A\mathbf {p} _{k})\alpha _{k}^{2}-\mathbf {p} _{k}^{T}\underbrace {(\mathbf {b} -A\mathbf {x} _{k})} _{=\mathbf {r} _{k}}\alpha _{k}+{\frac {1}{2}}\mathbf {x} _{k}^{T}A\mathbf {x} _{k}-\mathbf {x} _{k}^{T}\mathbf {b}$ che permette di calcolare analiticamente il passo $\alpha _{k}$ ottimale. Infatti, imponendo la condizione di stazionarietà

$0={\frac {\mathrm {d} {\tilde {Q}}}{\mathrm {d} \alpha _{k}}}(\alpha _{k})=(\mathbf {p} _{k}^{T}A\mathbf {p} _{k})\alpha _{k}-\mathbf {p} _{k}^{T}\mathbf {r} _{k}$

si ricava

$\alpha _{k}={\frac {\mathbf {p} _{k}^{T}\mathbf {r} _{k}}{\mathbf {p} _{k}^{T}A\mathbf {p} _{k}}}.$

L'algoritmo del metodo del gradiente per la risoluzione di sistemi lineari è dunque

${\begin{aligned}&k=0\\&{\text{while }}\mathbf {r} _{k}\neq \mathbf {0} \\&\qquad {\text{calcolare la direzione di discesa }}\mathbf {p} _{k}:=\mathbf {r} _{k}=\mathbf {b} -A\mathbf {x} _{k}\\&\qquad {\text{calcolare il passo di discesa }}\alpha _{k}:={\frac {\mathbf {p} _{k}^{T}\mathbf {r} _{k}}{\mathbf {p} _{k}^{T}A\mathbf {p} _{k}}}\\&\qquad \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad k=k+1\\&{\hbox{end}}.\end{aligned}}$

In aritmetica floating point la condizione del ciclo while può essere valutata verificando che la norma del residuo $\|\mathbf {r} _{k}\|$ non sia più piccola di una tolleranza impostata dall'utente.

Varianti

Metodo del gradiente precondizionato

In molti casi è possibile accelerare la velocità di convergenza dell'algoritmo migliorando le proprietà di condizionamento della matrice $A$. Si introduca a tal fine una matrice di precondizionamento $P$ simmetrica e definita positiva.

Lo schema risolutivo in questo caso diventa:

${\begin{aligned}&k=0\\&{\text{while }}\mathbf {r} _{k}\neq \mathbf {0} \\&\qquad {\text{calcolare la direzione di discesa }}\mathbf {p} _{k}:=\mathbf {r} _{k}=\mathbf {b} -A\mathbf {x} _{k}\\&\qquad {\text{trovare la soluzione }}\mathbf {z} _{k}{\text{ del sistema }}P\mathbf {z} _{k}=\mathbf {p} _{k}\\&\qquad {\text{calcolare il passo di discesa }}\alpha _{k}:={\frac {\mathbf {z} _{k}^{T}\mathbf {r} _{k}}{\mathbf {z} _{k}^{T}A\mathbf {z} _{k}}}\\&\qquad \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {z} _{k}\\&\qquad k=k+1\\&{\hbox{end}}.\end{aligned}}$

Metodo del gradiente coniugato

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 $\mathbf {p} _{k}$. 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

È possibile dimostrare che l'errore commesso alla $k$-esima iterazione del metodo del gradiente soddisfa la seguente stima:

$\|\mathbf {e} _{k}\|_{A}\leq c^{k}\|\mathbf {e} _{k-1}\|_{A},$

dove

$c={\frac {\kappa (A)-1}{\kappa (A)+1}},$

$\kappa (A)$ indica il numero di condizionamento in norma $2$ di $A$ e $\|\mathbf {x} \|_{A}:=\mathbf {x} ^{T}A\mathbf {x}$ è la norma indotta da $A$.

Nel caso precondizionato vale la stessa stima con

$c={\frac {\kappa (P^{-1}A)-1}{\kappa (P^{-1}A)+1}}.$

Esempio di implementazione

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

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

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 $\mathbf {y}$ della rete (ottenuti sommando i segnali provenienti dalle diverse unità di input $\mathbf {x}$ moltiplicati per l'efficacia, o pesi sinaptici $\mathbf {w}$ delle connessioni in ingresso), e i valori $\mathbf {t}$ 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 $\mathbf {y}$. Una scelta adatta a problemi di regressione è lo scarto quadratico medio tra $\mathbf {y}$ e $\mathbf {t}$ (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 $\mathbf {w}$ (parametri del modello) si può aumentare o diminuire la funzione obiettivo; la prestazione della rete sarà funzione delle variabili $\mathbf {w}$, 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.

Bibliografia

• 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

• Ottimizzazione (matematica)
• Metodo del gradiente coniugato
• Metodo di Laplace

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla discesa del gradiente

Collegamenti esterni

• 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.