Movatterモバイル変換

[0]ホーム
URL:

Vai al contenuto
WikipediaL'enciclopedia libera
Ricerca

Discesa del gradiente

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

Inottimizzazione eanalisi numerica, il metodo didiscesa del gradiente (detto anchemetodo del gradiente, oppuremetodo della massima discesa, o anchedella discesa più ripida; in inglesegradient descent osteepest descent) è una tecnica che consente di determinare i punti dimassimo 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, dalmatematicofranceseAugustin-Louis Cauchy nel tentativo di risolvere il problema della determinazione dell'orbita di uncorpo celeste a partire dalle sueequazioni del moto[1].

Esempio

[modifica |modifica wikitesto]

Si supponga di voler minimizzare la funzionef(x1,x2,x3)=x12−x2+x3{\displaystyle f(x_{1},x_{2},x_{3})=x_{1}^{2}-x_{2}+x_{3}} e si scelga come soluzione iniziale il vettorex0=[1,2,3]T{\displaystyle \mathbf {x} _{0}=[1,2,3]^{T}}. Allora

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

e, muovendosi in unintorno dix0{\displaystyle \mathbf {x} _{0}}:

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.{\displaystyle {\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 ax0{\displaystyle \mathbf {x} _{0}} - in corrispondenza dei quali la funzione assume un valore minore dif(x0){\displaystyle f(\mathbf {x} _{0})}, conviene spostarsi lungo direzioni che abbiano la prima e la terza componentex1,x3{\displaystyle x_{1},x_{3}} più piccole o seconda componentex2{\displaystyle x_{2}} più grande. Inoltre esistono delle direzionipreferenziali lungo le quali la funzionef{\displaystyle f} decresce più velocemente (per esempio scegliere una coordinatax1{\displaystyle x_{1}} più piccola è preferibile rispetto a far diminuirex3{\displaystyle x_{3}}).

La procedura può essere iterata partendo da un nuovo punto, ad esempiox1=[0.9,2,3]T{\displaystyle \mathbf {x} _{1}=[0.9,2,3]^{T}}, fino a individuare un minimo perf{\displaystyle f}. L'esempio mostra che una procedura che aggiorni la soluzione in modo iterativo sulla base delle informazioni disponibililocalmente 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 diottimizzazione non vincolata,

{minf(x)x∈Rn{\displaystyle {\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 passok{\displaystyle k}, supposto∇f(xk){\displaystyle \nabla f(x_{k})} diverso da zero, si sceglie come direzione di ricerca quella corrispondente adk=−∇f(xk){\displaystyle d_{k}=-\nabla f(x_{k})}, ovvero la direzione dell'anti-gradiente (si ricordi a tal proposito che ogni generico vettored∈Rn{\displaystyle d\in \mathbb {R} ^{n}}, cond≠0{\displaystyle d\neq {\textbf {0}}}, identifica unadirezione).

In particolare, il nome disteepest 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 funzionef{\displaystyle f} nel puntoxk{\displaystyle 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 a ogni iterazione la direzionedk=−∇f(xk){\displaystyle d_{k}=-\nabla f(x_{k})} è soluzione al seguente problema (vincolato)

{min∇f(xk)Tdk‖dk‖2=1{\displaystyle {\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 a ogni iterazione, si ha che∇f(xk)Tdk<0{\displaystyle \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 a ogni iterazione, lo stato di aggiornamento della successione di punti prodotta diventa

xk+1=xk−αk∇f(xk){\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}-\alpha _{k}\mathbf {\nabla } f(\mathbf {x} _{k})}

doveαk∈R+{\displaystyle \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(xk+akdk)≤f(xk)+γak∇f(xk)Tdk,γ∈(0,1/2){\displaystyle 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)}
∇f(xk+akdk)Tdk≤σ∇f(xk)Tdk,σ∈(γ,1){\displaystyle \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 af{\displaystyle f} ipotesi di convessità su tutto il suo dominio di definizione, allora non solo si ha convergenza a 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 funzionef(x){\displaystyle f(\mathbf {x} )} mediante metodo del gradiente è il seguente:

x0∈Rn,k=0while ∇f(xk)≠0calcolare la direzione di discesa dk:=−∇f(xk)calcolare il passo di discesa αkxk+1=xk+αkdkk=k+1end.{\displaystyle {\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

[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{xk}{\displaystyle \{x_{k}\}} al puntox¯:∇f(x¯)=0{\displaystyle {\overline {x}}:\nabla f({\overline {x}})=0}.

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

{xk}→x¯per  k→∞{\displaystyle \{x_{k}\}\to {\overline {x}}\quad {\text{per}}\ \ k\rightarrow \infty }

Se le ipotesi prima enunciate sono valide, ovvero l'algoritmo fa uso di tecniche di ricerca unidimensionale, e in particolare si assicura l'unicità delpunto stazionario per la funzione, il limite sopra indicato converge.

Supponiamo allora di voler minimizzare la seguente funzione quadratica strettamente convessa

f(x)=xTQx{\displaystyle f(x)=x^{T}Qx}

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

Tramite semplici passaggi algebrici, si arriva a dimostrare che

‖xk+1−x¯‖2≤(λMλm)1/2(λM−λmλM+λm)‖xk−x¯‖2{\displaystyle \|x_{k+1}-{\overline {x}}\|_{2}\leq {\biggl (}{\frac {\lambda _{M}}{\lambda _{m}}}{\Biggr )}^{1/2}{\Biggl (}{\frac {\lambda _{M}-\lambda _{m}}{\lambda _{M}+\lambda _{m}}}{\Biggr )}\|x_{k}-{\overline {x}}\|_{2}}

dando al gradiente rapidità di convergenza Q-lineare.

Si noti come dipende dal rapporto tra il massimo e 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 disistemi 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

Ax=b,{\displaystyle A\mathbf {x} =\mathbf {b} ,}

doveA{\displaystyle A} è unamatrice simmetrica edefinita positiva. Per le proprietà diA{\displaystyle A} la soluzione di tale problema è equivalente alla procedura diminimizzazione dellaforma quadratica associata:

Q(x)=12xTAx−xTb.{\displaystyle Q(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} .}

Infatti:

∇Q(x)=Ax−b{\displaystyle \nabla Q(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }

da cui

∇Q(x)=0⇔Ax=b.{\displaystyle \nabla Q(\mathbf {x} )=0\Leftrightarrow A\mathbf {x} =\mathbf {b} .}

Per la funzioneQ{\displaystyle Q} si ha che ladirezione di massima discesa nel puntoxk{\displaystyle \mathbf {x} _{k}} è:

−∇Q(xk)=b−Axk=:rk,{\displaystyle -\nabla Q(\mathbf {x} _{k})=\mathbf {b} -A\mathbf {x} _{k}=:\mathbf {r} _{k},}

coincidente con il residuork{\displaystyle \mathbf {r} _{k}} del sistema lineare. Dunque ladirezione di discesa scelta a ogni iterazione èpk=rk{\displaystyle \mathbf {p} _{k}=\mathbf {r} _{k}}.

Inoltre vale la seguente relazione:

Q~(αk):=Q(xk+αkpk)=12(pkTApk)αk2−pkT(b−Axk)⏟=rkαk+12xkTAxk−xkTb{\displaystyle {\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} }[2] che permette di calcolare analiticamente il passoαk{\displaystyle \alpha _{k}} ottimale[3]. Infatti, imponendo la condizione di stazionarietà
0=dQ~dαk(αk)=(pkTApk)αk−pkTrk{\displaystyle 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

αk=pkTrkpkTApk.{\displaystyle \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

k=0while rk≠0calcolare la direzione di discesa pk:=rk=b−Axkcalcolare il passo di discesa αk:=pkTrkpkTApkxk+1=xk+αkpkk=k+1end.{\displaystyle {\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 aritmeticafloating point la condizione delciclo while può essere valutata verificando che la norma del residuo‖rk‖{\displaystyle \|\mathbf {r} _{k}\|} 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à dicondizionamento della matriceA{\displaystyle A}. Si introduca a tal fine una matrice diprecondizionamentoP{\displaystyle P}simmetrica edefinita positiva.

Lo schema risolutivo in questo caso diventa[3]:

k=0while rk≠0calcolare la direzione di discesa pk:=rk=b−Axktrovare la soluzione zk del sistema Pzk=pkcalcolare il passo di discesa αk:=zkTrkzkTAzkxk+1=xk+αkzkk=k+1end.{\displaystyle {\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

[modifica |modifica wikitesto]
Lo stesso argomento in dettaglio:Metodo del gradiente coniugato.

Ilmetodo del gradiente coniugato costituisce una variante del metodo del gradiente in cui viene effettuata una scelta diversa, ma particolarmente conveniente nel caso di sistemi linearisimmetrici edefiniti positivi, per le direzioni di discesapk{\displaystyle \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

[modifica |modifica wikitesto]

È possibile dimostrare che l'errore commesso allak{\displaystyle k}-esima iterazione del metodo del gradiente soddisfa la seguente stima[3]:

‖ek‖A≤ck‖ek−1‖A,{\displaystyle \|\mathbf {e} _{k}\|_{A}\leq c^{k}\|\mathbf {e} _{k-1}\|_{A},}

dove

c=κ(A)−1κ(A)+1,{\displaystyle c={\frac {\kappa (A)-1}{\kappa (A)+1}},}

κ(A){\displaystyle \kappa (A)} indica il numero dicondizionamento innorma2{\displaystyle 2} diA{\displaystyle A} e‖x‖A:=xTAx{\displaystyle \|\mathbf {x} \|_{A}:=\mathbf {x} ^{T}A\mathbf {x} } è lanorma indotta daA{\displaystyle A}.

Nel caso precondizionato vale la stessa stima con

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

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

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;endifiter==nmaxwarning('Convergenza non raggiunta in nmax iterazioni!');endend

Approssimazione stocastica

[modifica |modifica wikitesto]
Lo stesso argomento in dettaglio:Discesa stocastica del gradiente.

Quando lafunzione obiettivo è troppo costosa da calcolare a ogni iterazione, ma può essere scomposta in una somma di molti addendi (per esempio, la somma del costo calcolato su ogni singolo record in undataset), il gradiente può essereapprossimato stocasticamente restringendo la somma su un sottoinsieme di addendi a ogni iterazione, metodo noto comediscesa stocastica del gradiente.

Applicazione alle reti neurali artificiali

[modifica |modifica wikitesto]

La discesa del gradiente è ampiamente utilizzata instatistica eapprendimento automatico per l'addestramento tramiteapprendimento supervisionato di modelli comereti neurali artificiali emodelli grafici. Il principio è noto comeregola 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 comeretropropagazione dell'errore, che consiste in un'applicazione della discesa del gradiente, essendo il contributo di ciascun parametro all'errore del modello dato dalladerivata 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 tipoin avanti (cioè con propagazione unidirezionale dei segnali, in inglesefeedforward) 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 diretropropagazione dell'errore (backpropagation), alla base dell'approccio connessionista.

Data una retein avanti con le proprietà sopra descritte, l'obiettivo che ci si prefigge è minimizzare la diversità tra i valori di attivazione delle unità di outputy{\displaystyle \mathbf {y} } della rete (ottenuti sommando i segnali provenienti dalle diverse unità di inputx{\displaystyle \mathbf {x} } moltiplicati per l'efficacia, opesi sinapticiw{\displaystyle \mathbf {w} } delle connessioni in ingresso), e i valorit{\displaystyle \mathbf {t} } della risposta desiderata. Tale diversità viene quantificata attraverso unafunzione di perdita. La funzione obiettivo che si vuole minimizzare è ilvalore atteso della perdita (in pratica la perditamedia sui dati).

Per applicare il metodo del gradiente, la funzione di perdita deve essere derivabile rispetto ai valori di outputy{\displaystyle \mathbf {y} }. Una scelta adatta a problemi diregressione è loscarto quadratico medio tray{\displaystyle \mathbf {y} } et{\displaystyle \mathbf {t} } (valutato per tutte le unità di output e per tutti i pattern d'apprendimento); per problemi diclassificazione si può utilizzare ladivergenza di Kullback-Leibler o equivalentemente l'entropia incrociata.

Nella fase di addestramento, variando i pesi sinapticiw{\displaystyle \mathbf {w} } (parametri del modello) si può aumentare o diminuire la funzione obiettivo; laprestazione della rete saràfunzione delle variabiliw{\displaystyle \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 relatividataset usati nell'addestramento sono molto grandi, in pratica si fa generalmente uso delladiscesa 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), sumath.uni-bielefeld.de.URL consultato il 20 giugno 2016(archiviato dall'url originale il 29 dicembre 2018).
  2. ^Si è sfruttata la proprietàAx⋅y=x⋅Ay{\displaystyle A\mathbf {x} \cdot \mathbf {y} =\mathbf {x} \cdot A\mathbf {y} }, valida seA{\displaystyle A} è simmetrica.
  3. ^abcQuarteroni, Sacco, Saleri.

Bibliografia

[modifica |modifica wikitesto]

Voci correlate

[modifica |modifica wikitesto]

Altri progetti

[modifica |modifica wikitesto]

Altri progetti

Collegamenti esterni

[modifica |modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Discesa_del_gradiente&oldid=145701353"
Categorie:
Categoria nascosta:
[8]ページ先頭
©2009-2025 Movatter.jp