Discesa del gradiente

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
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 method o metodo di discesa più ripida) è 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 è 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]

Con riferimento al seguente problema di ottimizzazione non vincolata,

il metodo del gradiente è un metodo di risoluzione per problemi di ottimizzazione non vincolati , in cui ad ogni passo , supposto diverso da zero, sceglie come direzione di ricerca la direzione , 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 direzione 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 di Convergenza Metodo del Gradiente[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. Siamo

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

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]

Magnifying glass icon mgx2.svgLo 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

Approssimazione stocastica[modifica | modifica wikitesto]

Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: Discesa stocastica del gradiente.

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]

  1. ^ (EN) Cauchy and the Gradient Method (PDF), su math.uni-bielefeld.de. URL consultato il 20 giugno 2016.
  2. ^ Si è sfruttata la proprietà , valida se è simmetrica.
  3. ^ a b c Quarteroni, Sacco, Saleri.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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