Discesa del gradiente

Da Wikipedia, l'enciclopedia libera.
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, metodo steepest descent o metodo di discesa più ripida) è una tecnica che consente di determinare i punti di massimo e minimo di una funzione di più variabili.

Il metodo è stato sviluppato - e pubblicato nel 1847 - dal matematico francese Augustin-Louis Cauchy nel tentativo di risolvere il problema di determinare l'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 assuma 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, ad esempio, rispetto a far diminuire ).

La procedura può essere iterata partendo da un nuovo punto, ad esempio , fino ad 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 ad individuare un punto di minimo per la funzione assegnata.

Descrizione del metodo[modifica | modifica wikitesto]

Si voglia risolvere il seguente problema di ottimizzazione non vincolata nello spazio -dimensionale

La tecnica di discesa secondo gradiente si basa sul fatto che, per una data funzione , la direzione di massima discesa in un assegnato punto corrisponde a quella determinata dall'opposto del suo gradiente in quel punto[2] . Questa scelta per la direzione di discesa garantisce che la soluzione tenda a un punto di minimo di . Il metodo del gradiente prevede dunque di partire da una soluzione iniziale scelta arbitrariamente e di procedere iterativamente aggiornandola come

dove corrisponde alla lunghezza del passo di discesa, la cui scelta diventa cruciale nel determinare la velocità con cui l'algoritmo convergerà alla soluzione richiesta.

Si parla di metodo stazionario nel caso in cui si scelga un passo costante per ogni , viceversa il metodo si definisce dinamico[3]. In quest'ultimo caso una scelta conveniente, ma computazionalmente più onerosa rispetto a un metodo stazionario, consiste nell'ottimizzare, una volta determinata la direzione di discesa , la funzione di una variabile in maniera analitica o in maniera approssimata[4]. Si noti che, a seconda della scelta del passo di discesa, l'algoritmo potrà convergere a uno qualsiasi dei minimi della funzione , sia esso locale o globale.

Algoritmo[modifica | modifica wikitesto]

Lo schema generale per l'ottimizzazione di una funzione mediante metodo del gradiente è il seguente:

Soluzione di sistemi lineari[modifica | modifica wikitesto]

Un caso particolare di applicazione del metodo del gradiente consiste nella risoluzione di sistemi lineari 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:

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.

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]

Exquisite-kfind.png Lo stesso argomento in dettaglio: 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 . 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 = 1;
    while ((norm(rk) >= toll) && (iter <= nmax))
        rk = b - A * xk;
        zk = P \ rk;
        alphak = zk' * rk / ((A * zk)' * zk);
        xk = xk + alphak * zk;
    end
    if iter == nmax
        warning('Convergenza non raggiunta in nmax iterazioni!');
    end
end

Applicazione alle reti neurali artificiali[modifica | modifica wikitesto]

Un esempio notevole di applicazione del metodo del gradiente è nell'ambito della valutazione delle prestazioni di una regola di apprendimento per reti neurali: la regola delta.

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 e può essere definita come un precursore dell'algoritmo di retroazione (backpropagation), alla base dell'approccio connessionista.

Data una rete in avanti con le proprietà sopra descritte, l'obiettivo che ci si prefigge è minimizzare la differenza 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, detti anche pesi ideali.

Le prestazioni della rete possono essere descritte in termini una funzione, che si vuole minimizzare, definita come scarto quadratico medio tra e (valutato per tutte le unità di output e per tutti i pattern d'apprendimento). 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; di conseguenza la prestazione della rete sarà funzione delle variabili , il cui minimo può essere individuato applicando il metodo del gradiente e aggiornando quindi iterativamente i valori dei pesi sinaptici .

Note[modifica | modifica wikitesto]

  1. ^ (EN) Cauchy and the Gradient Method (PDF), math.uni-bielefeld.de. URL consultato il 20 giugno 2016.
  2. ^ Complementi di ricerca operativa, sezione 2.4
  3. ^ a b c d Quarteroni, Sacco, Saleri
  4. ^ Complementi di ricerca operativa, sezione 6.1

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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