L 22 GGrraaddiieennttii ee mmeettooddii ddii oottttiimmiizzzzaazziioonnee

2

2

G

G

r

r

a

a

d

d

i

i

e

e

n

n

t

t

i

i

e

e

m

m

e

e

t

t

o

o

d

d

i

i

d

d

i

i

o

o

t

t

t

t

i

i

m

m

i

i

z

z

z

z

a

a

z

z

i

i

o

o

n

n

e

e

2.1 Nozioni di base

a maggior parte dei criteri di recupero delle componenti indipendenti (come vedremo) si basano sulla minimizzazione di una

funzione costo in modo da ottimizzare determinate caratteristiche statistiche

dei segnali che si è interessati a valutare.

L

In generale se w è un vettore colonna tale per cui w = (w1,…,wm) e se g =

g(w

T

1,…,wm) = g(w) è una generica funzione scalare differenziabile di m

variabili, allora si definisce gradiente vettoriale l’espressione:

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ∂ ∂ ∂ ∂ = ∂ ∂ m w g w g g . . . 1 w (2.1)

Un’altra notazione comunemente usata è ∇g oppure ∇ _wg.

Questo concetto può essere generalizzato al caso di una funzione vettoriale

g(w)= (2.2) ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ) g . . . ) g n w w ( ( 1

i cui singoli elementi gi (w) sono a loro volta funzioni di w. In questo

caso si parla di Jacobiano (Ĵg) che in notazione matriciale assume la forma

di: ⎟⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ = ∂ ∂ m n m n w g w g w g w g g . . . . . . . . . . . . . . . 1 1 1 1 w (2.3)

in cui la i-esima colonna del Jacobiano rappresenta il gradiente vettoriale di gi(w) rispetto a w stesso.

Data ora una funzione scalare g e una matrice W = (wij) di dimensione m

n, in analogia a quanto detto sopra si può definire una

×

g = g(W) = g(w11,…,wij,…w ) (2.4) mn

W ∂ ∂g = ⎟⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ mn m n w g w g w g w g . . . . . . . . . . . . . . . 1 1 11 (2.5)

Quindi il gradiente matriciale è una matrice delle stesse dimensioni di W e il cui ij-esimo elemento è la derivata parziale di g rispetto a wij.

2.2 La discesa del gradiente

La tecnica di ottimizzazione della discesa del gradiente si basa sulla minimizzazione di una funzione costo J(W) rispetto alla matrice parametro

W o possibilmente rispetto a una delle sue colonne w. In molti casi

vengono usate delle costrizioni (come ad esempio si impone che la norma del vettore soluzione sia limitata) per restringere il numero di possibili soluzioni o meglio per evitare soluzioni spurie.

Considerando per semplicità il caso in cui la soluzione sia un vettore w, lo scopo è quello di minimizzare la funzione costo iterativamente e a partire da alcune condizioni iniziali w(0) in modo tale da ottenere proprio w. Per fare questo si calcola il gradiente di J(W) e, allontanandosi dalla condizione iniziale ci si muove nella direzione negativa del gradiente ripetendo la stessa procedura per ogni punto. Naturalmente i vari punti in cui si applica il gradiente sono distanziati di un opportuno passo la cui scelta è cruciale sia per la convergenza sia per l’accuratezza della soluzione.

Traducendo le parole in formule la regola di apprendimento che si ottiene può essere espressa come:

w(t) = w(t-1) – α(t) (t-1) ) w w w w = ∂ ∂ ( ) ( J (2.6)

Il parametro α(t) tiene conto della lunghezza del passo nella direzione del gradiente negativo e per questo è anche chiamato velocità di apprendimento.

L’iterazione (2.6) viene ripetuta fino a che la distanza euclidea tra due soluzioni consecutive risulta minore di una voluta tolleranza ε e cioè fino a che ε ≤ − − ( 1) ) (t w t w (2.7)

L’equazione (2.6) può essere riscritta in notazione più snella definendo

1) -(t -(t) w w w = ∆ _(2.8)

per cui la (2.6) diventa

w w w ∂ ∂ = ∆ - α(t) J( ) (2.9)

Va notato per completezza che la velocità di apprendimento non sempre è tempo dipendente, bensì può semplicemente essere un opportuno coefficiente scalare.

Per visualizzare il concetto si può equiparare il grafico tridimensionale di J(W) ad un terreno montuoso e intuitivamente capire che la (2.9) agisce in modo tale da muoversi sempre nella direzione della più ripida discesa. Ciò evidenzia quale è lo svantaggio nell’usare questa tecnica: a meno che la funzione costo sia “levigata”, la discesa del gradiente può condurre ad un minimo locale di J(W) (“una valle intermedia tra due rilievi montuosi”) senza avere più la possibilità di muoversi da lì. E’ evidente che la soluzione trovata in tale caso non è ottimale, in quanto ciò che si è trovato rappresenta un minimo locale e che il ruolo delle condizioni iniziali nell’evitare il verificarsi di tali inconvenienti è fondamentale.

Come esempio consideriamo il caso indicato in figura 1.1 che mostra il grafico a contorni di una possibile funzione costo con la presenza di più minimi. Con la scelta del punto iniziale evidenziato dalla freccia del vettore gradiente, è chiaro che l’algoritmo convergerà sul minimo locale più vicino e non sul minimo assoluto cercato.

Fig.1.1 Grafico del contorno di una funzione costo J(W) con un minimo locale

Indicando con x il vettore delle osservazioni (i segnali che possiamo misurare) abbiamo la possibilità di esprimere la funzione costo come

J(w) = E{g(w,x)} (2.10) dove g è una funzione integrabile ed E indica l’aspettazione statistica, dipendente dalla densità di probabilità f(x) del vettore osservazioni secondo la nota relazione E{ g(w,x)} =

∫ ∫

Utilizzando questa forma della funzione costo la regola di apprendimento del gradiente diventa

w(t) = w(t-1) - α(t)

w ∂

∂

E{g(w, x(t)) } w=w(t−1) (2.12)

Questo tipo di algoritmo, in cui viene usato per ogni iterazione l’intero set di dati a disposizione, viene chiamato apprendimento batch .

Tuttavia questo tipo di approccio risulta scomodo in quanto ad ogni iterazione bisogna valutare l’aspettazione di un’ appropriata funzione g e ciò risulta tanto più problematico quanto più nuove osservazioni si presentano nel corso dell’ iterazione.

Può essere vantaggioso quindi utilizzare algoritmi così detti on-line, in cui ad ogni iterazione vengono considerati solamente gli ultimi (in senso temporale) campioni del segnale x(t).

In questo contesto l’aspettazione presente nella regola di apprendimento (2.12) viene eliminata ottenendo la relazione

w(t) = w(t-1) - α(t)

w ∂

∂

g(w, x) w=w(t−1) (2.13) Ciò porta a una maggiore fluttuazione di questo algoritmo rispetto a quello batch, ma la direzione verso cui evolve resta ancora quella della discesa del gradiente.

Questo tipo di tecnica risulta lenta nel convergere alla soluzione ma ha un basso costo computazionale rispetto ad altre tecniche come la discesa del gradiente.

2.4 Il gradiente naturale

Il metodo del gradiente naturale è una tecnica particolarmente utile per risolvere iterativamente problemi di stima. Nella sua forma più semplice questo metodo non è altro che una derivazione della più generale tecnica della discesa del gradiente.

In quest’ultima, come visto, si cerca di minimizzare iterativamente una funzione costo J(w) (dove w è un generico vettore di m elementi) iniziando da alcuni punti di partenza w(0). Questi ultimi sono scelti accuratamente allo scopo di far convergere l’algoritmo alla soluzione cercata nella maniera più veloce possibile.

Con l’uso del gradiente naturale tuttavia la minimizzazione di J(w) non è effettuata in uno spazio euclideo bensì in uno spazio parametrico di Riemann [5].

2.4.1 Lo spazio di Riemann

Sia S = {

w

J(

w

w

w

w

w

∑

dove dw sono le componenti di di

w

Diversamente quando il sistema di coordinate non è ortonormale la distanza quadratica viene espressa nella forma

j i j i ij dwdw g d =

∑

La matrice G = (gij), di dimensione n × n, è chiamata tensore di Riemann

e dipende in generale da w. Nel caso di spazio Euclideo ortonormale tale matrice si riduce a g (w) = δ = (2.16) ij ij ⎩ ⎨ ⎧ 0 1 j i j i ≠ =

Quando S è uno spazio multi-curvato non c’è possibilità di definire coordinate ortonormali, perciò la distanza d

w

In tale tipo di spazio la direzione della più ripida discesa della funzione costo J(w) è definita in base al vettore dw che minimizza J(w+dw) sotto la condizione

2 w

d = ε (2.17) 2

Dove ε è una costante piccola a sufficienza e dw è di lunghezza fissata. In forma matematica si ha il seguente teorema [6]:

Teorema. La direzione della più ripida discesa di J(w) in uno spazio

Riemmaniano è data da

-_∇J w)₌-G-1(w)_∇J(w) (2.18)

(

Dove G è l’inversa della matrice G = (g−1

ij) e ∇J è il gradiente

convenzionale espresso come già visto nella forma

J ∇ = ( _J T w J w₁ (w),...,∂ _n (w)) ∂ ∂ ∂ (2.19)

Approfondimento. Denotando con

dw = εa (2.20)

J(w + dw) = J(w) + ε J(w)·a (2.21) ∇ sotto la limitazione 2 a =

∑

Utilizzando il metodo dei moltiplicatori di Lagrange [7] abbiamo

{

}

o eqivalentemente dopo semplici calcoli

) ( 2 1 w G a₌ -1_∇J λ . (2.25) Ora indichiamo ) ( ) (w G- J w J = ∇ ∇ 1 (2.26)

come il gradiente naturale di J nello spazio di Riemman, così che

J ∇

Naturalmente è facile constatare che nel caso di spazio euclideo e coordinate ortonormali J J =∇ ∇ . (2.27) Tutto ciò suggerisce un utile algoritmo di discesa del gradiente naturale nella forma: ) ( 1 t t t t w J w w ₊ = −η∇ (2.28)