PROGETTO E TRAINING PROGETTO E TRAINING DI MLPDI MLP

Principali aspetti da considerare:

• efficienza e controllo del learning

• criterio d’errore

• topologia della rete

TOPOLOGIA

L’errore si attenua da uno strato all’altro

Si parte dal perceptron; se questo non risolve il problema

Si passa alla MLP con uno strato nascostoinfine

Si passa alla MLP con due strati nascosti

Poiché una MLP con 2 strati nascosti è un approssimatore universale raramente si dovranno usare reti con più di due strati nascosti

PT-1

CONTROLLO DEL LEARNING

• Pesi iniziali

• Tasso di learning

• Algoritmo di ricerca dell’ottimo

• Criterio d’arresto

È inoltre cruciale la qualità e quantità dei dati di training

• Pesi iniziali - Non vi sono molti lavori in letteratura

Regola pratica: pesi random; occorre fare più run

• Tasso di learning: annealing

Es:

-

-

)()1( nn costante

0

0

1)(

nn

n

00 ,n da determinare sperimentalmente

L’annealing migliora la convergenza ed evita l’intrappolamento nei minimi locali.

Regola empirica: incrementare dallo strato d’uscita all’ingresso di un fattore da 2 a 5 da strato a strato

PT-2

LA SCELTA DI UN LEARNING RATE UGUALE PER TUTTI I NODI È DETTATA DALLA SEMPLICITÀ IMPLEMENTATIVA

Teoricamente: va scelto in accordo con il valore dell’autovalore per la specifica direzione di ricerca

Praticamente: difficilmente realizzabile

Soluzione alternativa: adattamento dinamico per ciascun peso ijijw

REGOLA DI ADATTAMENTO DELTA-BAR-DELTA

0

)()1( nb

k

n ijij

0)()1( se nDnS ijij

0)()1( se nDnS ijij

altrimenti

Sij: media dei gradienti precedenti

Dij: gradiente corrente

Se Sij e Dij hanno lo stesso segno il loro prodotto è >0 e è incrementata di una costante

Se il prodotto è negativo c’è un’oscillazione dei pesi e deve essere decrementato

TUTTI QUESTI SCHEMI AUMENTANO I PARAMETRI LIBERI TUNING PIÙ DIFFICOLTOSO

PT-3

COMPETIZIONE DEI NEURONI NON LINEARI

Le non linearità agiscono come meccanismi di competizione che permettono ai diversi neuroni di specializzarsi in differenti aree dello spazio degli ingressi

jk

kikiij ywnetfw

)('

Somma degli errori pesati provenienti dallo strato successivo

Attività locale

Derivata della non linearità

i Errore locale

Differenti neuroni nascosti con diversi punti di funzionamento (valore di net) producono un aggiornamento dei pesi molto diverso

PT-4

PROCEDURE DI RICERCA

• Ricerca locale

estrema semplicità minimi locali divergenza

maggior potenza minimi locali divergenzamaggior costo computazionale• Ricerca globale

- Simulated Annealing

- Algoritmi Genetici

- Tabu Search

- Metodi del gradiente:

- Metodi del II°ordine:

Costosi in termini implementativi; costosi in termini di memoria richiesta; richiedono quantità non locali; minimo globale

LA TENDENZA È QUELLA DI UTILIZZARE TECNICHE CHE MIGLIORANO LE PRESTAZIONI DEL METODO DI BASE DEL GRADIENTE DISCENDENTE

)( ijij wJw SIA LMS CHE EBP USANO UNA STIMA DEL GRADIENTE

)()()( nynnw jiij SI PUÒ MIGLIORARE QUESTA ESPRESSIONE PER ADEGUARSI A SUPERFICI DI PRESTAZIONE NON CONVESSE

PT-5

SUPERFICI DI PRESTAZIONESUPERFICI DI PRESTAZIONE

Espansione in Serie di Taylor

F x F x xd

dF x

x x=x x– +=

12---

x2

2

d

dF x

x x=

x x– 2 + +

1n!-----

xn

n

d

dF x

x x=

x x– n + +

Sia F(x) una funzione analitica tale che esistano tutte le sue derivate:Essa puo’ essere rappresentata dalla sua espansione in serie di Taylornell’intorno di un punto x*

Possiamo approssimare la F(x) troncando la serie ad un numero finito di termini

SP-1

Esempio

F x ex–

e0–

e0–

x 0– 12---e

0–x 0– 2+–

16---e

0–x 0– 3– += =

F x ex–

=

F x 1 x–12---x

2 16---x

3– + +=

F x F0 x 1=

F x F1 x 1 x–=

F x F2 x 1 x–12---x

2+=

Approssimazioni della serie di Taylor :

Serie di Taylor di F(x) nell’intorno di x* = 0 :

SP-2

Grafico delle Approssimazioni

-2 -1 0 1 2

0

1

2

3

4

5

6

F0 x

F1 x

F2 x

SP-3

Le tre approssimazioni sono accurate se x e’ vicino a x*

Se x si allontana da x* l’approssimazione migliora all’aumentaredel numero di termini. Infatti i termini sono moltiplicati perpotenze crescenti di (x-x*) e man mano che x si avvicina a x*questi termini diventano geometricamente piu’ piccoli

SP-4

Caso VettorialeF x F x1 x 2 x n =

F x F x x1

F x x x=

x1 x1– x2

F x x x=

x2 x2– + +=

xn

F x x x=

xn xn– 12---

x12

2

F x

x x=x1 x1–

2+ + +

12---

x1 x2

2

F x x x=

x1 x1– x2 x2– + +

SP-5

Forma MatricialeF x F x F x

T

x x=x x– +=

12--- x x–

TF x

x x=x x– 2 + +

F x

x1

F x

x2

F x

xn

F x

= F x 2

x12

2

F x

x1 x2

2

F x x1 xn

2

F x

x2 x1

2

F x x2

2

2

F x

x2 xn

2

F x

xn x1

2

F x xn x2

2

F x xn

2

2

F x

=

Gradiente Hessiano

SP-6

Derivate DirezionaliF x xi

2F x x i

2

Derivata prima (pendenza) di F(x) lungo l’asse xi :

Derivata seconda (curvatura) di F(x) lungo l’asse xi :

(isimo elemento del gradiente)

(elemento i,i dell’Hessiano)

pTF x p

-----------------------Derivata prima (pendenza) di F(x) lungo il vettore p:

Derivata seconda (curvatura) di F(x) lungo il vettore p: pT

F x 2 p

p 2------------------------------

Se vogliamo la derivata lungo una qualunque direzione p:

SP-7

EsempioF x x 1

22x 1x

22 x2

2+ +=

x 0.5

0= p 1

1–=

F x x x=

x1

F x

x2

F x

x x=

2x1 2x2+

2x1 4x2+x x=

1

1= = =

pTF x p

-----------------------

1 1–1

1

11–

------------------------0

2------- 0= = =

Si ottiene derivata nulla se la direzione p e’ ortogonale al gradienteSi ha pendenza massima quando la direzione p e’ quella del gradiente

SP-8

Grafici

-2 -1 0 1 2-2

-1

0

1

2

-2

-1

0

1

2

-2

-1

0

1

20

5

10

15

20

x1

x1

x2

x2

1.4

1.3

0.5

0.0

1.0

Derivate direzionali

SP-9

Minimi

Il punto x* e’ un strong minimum di F(x) se esiste uno scalare >0, tale che F(x*) < F(x* + x) per tuttti i x tali che > ||x|| > 0.

Strong Minimum

Il punto x* e’ un unico global minimum di F(x) se F(x*) < F(x* + x) per tutti i x  0.

Global Minimum

Il punto x* e’ un weak minimum di F(x) se non e’ un strong minimum, e esiste uno scalare >0, tale che F(x*) F(x* + x) per tutti i x tali che > ||x|| > 0.

Weak Minimum

SP-10

Esempio Scalare

-2 -1 0 1 20

2

4

6

8

F x 3x4

7x2

–12---x– 6+=

Strong Minimum

Strong Maximum

Global Minimum

SP-11

Esempio Vettoriale

-2

-1

0

1

2

-2

-1

0

1

20

4

8

12

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

F x x2 x1– 48x 1x2 x1– x2 3+ + +=

-2 -1 0 1 2-2

-1

0

1

2

-2

-1

0

1

2

-2

-1

0

1

20

2

4

6

8

F x x 12

1.5x 1x2– 2 x22

+ x12

=

SP-12

Condizioni di Ottimalità del Primo-Ordine

F x F x x+ F x F x T

x x=x+= =

12---xT

F x x x=

x2 + +

x x x–=

F x x+ F x F x T

x x=x+

Per piccoli x:

F x T

x x=x 0

F x T

x x=x 0

Se x* e’ un minimo, questo implica:

F x x– F x F x T

x x=x – F x Se allora

Ma questo implicherebbe che x* non e’ un minimo. Quindi: F x T

x x=x 0=

Poiche’ questo deve essere vero per ogni x,

F x x x=

0=

SP-13

Condizioni del Secondo-Ordine

F x x+ F x 12---xT

F x x x=

x2 + +=

xTF x

x x=x2 0Un strong minimum esisterà in x* se Per ogni x 0.

La matrice Hessiana deve essere definita positiva. Una matrice H e’ positiva definita se:

zTH z 0

Una condizione necessaria e’ che la matrice Hessiana sia semidefinita positiva. Una matrice H e’ semidefinita positiva se:

zTH z 0

Se la condizione del primo-ordine e’ soddisfatta (gradiente nullo), allora:

Per qualunque z 0.

Per qualunque z.

Questa e’ una condizione sufficiente per l’ottimalità.

SP-14

EsempioF x x1

22x1x2 2x2

2x1+ + +=

F x 2 x1 2x 2 1+ +

2 x1 4x 2+0= = x 1–

0.5=

F x 2 2 2

2 4= (Non una funzione di x in questo caso.)

Se gli autovalori della matrice Hessiana sono tutti maggiori di zero,la matrice Hessiana e’ positiva definita.

F x 2 I– 2 – 2

2 4 –2

6– 4+ 0.76– 5.24– = = =

0.76 5.24= Entrambi gli autovalori sono positivi, quindi strong minimum.

SP-15

Funzioni Quadratiche1

F x 2---x TA x dTx c+ +=

hTx x

Th h= =

xT Qx Qx QT x+ 2Qx (per Q simmetrica) = =

F x A x d+=

F x 2 A=

Utili proprietà del gradiente:

Gradiente e Hessiano:

Gradiente di una funzione quadratica:

Hessiano di una funzione Quadratica :

(A simmetrica)

SP-16

1F x 2

---x TH x dTx c+ +=

Forma quadratica

Tutte le derivate di ordine superiore al secondo della F(x) sononulle. Quindi i primi tre termini della serie di Taylor fornisconouna rappresentazione esatta della funzione quadratica

Spesso la funzione costo utilizzata e’ quadratica. Quando non lofosse, spesso può essere approssimata con una funzione quadraticain un intorno piccolo, specialmente vicino a un minimo.

Se ||x|| e’ piccolo, tutte le funzioni analitiche si comportanocome quadratiche in un piccolo intorno.

SP-17

Autovalori e autovettori di H

F x 12--- xTH x=

Consideriamo una funzione quadratica che ha un punto di stazio-narietà nell’origine, e il cui valore sia zero.

B z1 z2 zn=

B 1– BT=

H' BTHB

1 0 0

0 2 0

0 0 n

= = =

Usiamo gli autovettori di H come nuova base e operiamo un cambia-mento di base.

Poiche’ H e’ simmetrica, i suoi autovettori sono ortogonali, e l’inversa coinciderà con la trasposta.

H BBT=

SP-18

Derivata seconda direzionale

pTF x 2 p

p 2------------------------------ pTHp

p 2---------------=

p Bc=

Dove c e’ la rappresentazione di p rispetto agli autovettori (nuova base):

cTBT BBT Bc

cTB

TBc

--------------------------------------------cTc

cTc

--------------

ici2

i 1=

n

ci2

i 1=

n

--------------------= = =

Possiamo utilizzare il concetto di derivata direzionale per spiegare ilsignificato fisico degli autovalori e autovettori di H e come essi de-terminano la forma della superficie di una funzione quadratica

La derivata seconda di F(x) lungo la direzione p e’:

p-------

pTH

p2------- -

SP-19

La derivata seconda secondo p e’ una media pesata degli autovalorie quindi non può essere più grande del maggior autovalore o piùpiccola del minor autovalore, quindi:

pTHpmin

p2--------------- max

Se scegliamo p zmax= (cioe’ l’autovettore associato al massimoautovalore)

Allora il vettore c e’:

c BTp BTzmax

0

0

0

10

0

= = = Posizione corrispondente a max

SP-20

Autovettori (Massimo Autovalore)maxIl valore unitario e’ in corrispondenza a

zmaxTHzmax

zmax2--------------------------------

ici2

i 1=

n

ci2

i 1=

n

--------------------= = max

poiche’ gli autovettori sono ortonormali.

Sostituendo a p zmax

Gli autovalori rappresentano la curvatura(derivate seconde) lungo gli autovettori(gli assi principali).

Il massimo della derivata seconda si ha in direzione dell’autovettore corrispondente all’autovalore piu’ grande.

SP-21

Esempio: Circular Hollow

-2

-1

0

1

2

-2

-1

0

1

20

2

4

-2 -1 0 1 2-2

-1

0

1

2

F x x 12

x22

+12---xT 2 0

0 2x= =

F x 2 2 0

0 2= 1 2= z1

1

0= 2 2= z2

0

1=

(In realtà in questo caso qualunque coppia di vettori indipendenti possono essere autovettori)

Poiche’ gli autovalori sono uguali la curvatura deve essere la stessain tutte le direzioni e la funzione ha linee di contorno circolari

SP-22

Esempio: Elliptical HollowF x x 1

2x1 x2 x2

2+ +

12---xT 2 1

1 2x= =

F x 2 2 1

1 2= 1 1= z1

1

1–= 2 3= z2

1

1=

-2 -1 0 1 2-2

-1

0

1

2

-2

-1

0

1

2

-2

-1

0

1

20

1

2

3

(gli autovettori non sono univoci, essi possono essere moltiplicati per uno scalare)

In questo caso il massimo della curvatura e’ in direzione di z2

SP-23

Esempio: Autovalori di segno opposto

-2

-1

0

1

2

-2

-1

0

1

2-8

-4

0

4

F x 14---x1

2–

32---x1x2–

14---x2

2–

12---xT 0.5– 1.5–

1.5– 0.5–x= =

F x 2 0.5– 1.5–

1.5– 0.5–= 1 1= z1

1–

1= 2 2–= z2

1–

1–=

-2 -1 0 1 2-2

-1

0

1

2

L’Hessiano e’ indefinito. Il punto di stazionarietà e’ una sella,e’ un minimo lungo il primo autovettore e un massimo lungoil secondo

SP-24

Esempio: Valle stazionaria

F x 12---x1

2x1x2–

12---x2

2+

12---xT 1 1–

1– 1x= =

F x 2 1 1–

1– 1= 1 1= z1

1–

1= z2

1–

1–=2 0=

-2 -1 0 1 2-2

-1

0

1

2

-2

-1

0

1

2

-2

-1

0

1

20

1

2

3

Il secondo autovalore e’ nullo. Ci sarà una curvatura nulla lungoil secondo autovettore.

SP-25

OTTIMIZZAZIONE OTTIMIZZAZIONE DELLE PRESTAZIONIDELLE PRESTAZIONI

Algoritmo di ottimizzazione di base

xk 1+ xk kpk+=

x k xk 1+ x k–

kpk

= =

pk - Direzione di ricerca k - Learning Rate o Step size

o

xk

x k 1+kpk

Schema iterativo

Trovare il minimo di una funzione obiettivo

Gli algoritmi che vedremo si distinguono per la scelta della direzione di ricerca.

OP-1

Steepest Descent

x xF k 1+ F k

Scegliere il passo successivo in modo che la funzione decresca:

F xk 1+ F x

kx k

+ F xk g

kT x k

+=

Per piccoli cambiamenti nella x si puo’ approssimare F(x):

gk F x x x k=

dove

gkT x k kgk

Tpk 0=

Se vogliamo che la funzione decresca:

pk g– k=

Possiamo massimizzare il decremento scegliendo:

xk 1+

xk

kg

k–=

OP-2

EsempioF x x1

2 2 x1x22x2

2 x1+ + +=

x00.5

0.5=

F x x1

F x

x2

F x

2x 1 2x2 1+ +

2x 1 4x 2+= = g0 F x

x x0=

3

3= =

0.1=

x1 x0 g0

– 0.5

0.50.1 3

3– 0.2

0.2= = =

x2 x1 g1

– 0.2

0.20.1 1.8

1.2– 0.02

0.08= = =

OP-3

Grafico

-2 -1 0 1 2-2

-1

0

1

2

Per valori bassi di la traiettoria e’ sempre perpendicolare allelinee di contorno

Se incrementassimo peres. a 0.035, la traiettoriaoscillerebbe. Al crescere di le oscillazioni aumentano in ampiezza e l’algoritmodiventa instabile.

OP-4

Stabilizzazione del Learning Rate (Quadratico)

1F x 2

---xTHx dTx c+ +=

F x Hx d+=

x k 1+ xk gk– x k Hx k d+ –= =

1 i

– 1 2i

---- 2max

------------

xk 1+

I H– xkd–=

La stabilità e’ determinata dagli autovalori di questa matrice, che devono avere ampiezza minore dell’unità

I H– zi

ziHz

i– z

i

iz

i– 1

i– z

i= = =

Autovalore di [I - H].

Requisiti per la stabilità dell’algoritmo steepest descent:

(i - autovalore di H)

Non c’e’ un metodo sistematico per trovare per qualunque tipo difunzione. Per funzioni quadratiche si ha un limite superiore.

Poiche’:

OP-5

EsempioA 2 2

2 4= 1 0.764= z1

0.851

0.526–=

2 5.24 z20.526

0.851=

=

2max

------------2

5.24---------- 0.38= =

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2 0.37= 0.39=

OP-6

Minimizzazione lungo una linea

x p+F k

k k

ddk

--------- F xk kpk+ ( ) F x T

x xk=pk kpk

T F x 2x xk=

pk+=

k

F x T

x x k=pk

pkT F x 2

x xk=pk

------------------------------------------------– g k

Tpk

pkTHkpk

--------------------–= =

Hk F x 2x xk=

dove

Per funzioni quadratiche si puo’ trovare la soluzione analiticamente

Si puo’ usare un metodo detto Line SearchLine Search

Un altro approccio per scegliere il learning rate e’ quello di minimizzare F rispetto a k a ciascuna iterazione cioe’: Scegliere

k per minimizzare:

OP-7

Esempio

F x 12---xT 2 2

2 4x 1 0 x+= x0

0.5

0.5=

F x x1 F x

x2 F x

2x1 2x2 1+ +

2x1 4x2+= = p0 g– 0 F x –

x x0=

3–3–

= = =

0

3 33–

3–

3– 3–2 2

2 4

3–

3–

--------------------------------------------– 0.2= = x1 x0 0g0– 0.5

0.50.2 3

3– 0.1–

0.1–= = =

OP-8

Grafico

I passi successivi sono ortogonali:Infatti, quando minimizziamo lungo una linea dobbiamo sempre fermarci in un punto tangente a una linea di contorno. Allora, poiche’ il gradiente e’ ortogonale alle linee di contorno, il successivo passo, che e’ lungo il gradiente negativo, sarà ortogonale al precedente percorso.

kd

d F xk k pk+

kd

d F xk 1+ F x T

x xk 1+= kd

d xk k pk+ = =

F x T

x xk 1+=pk gk 1+

Tpk= =

-2 -1 0 1 2-2

-1

0

1

2Contour Plot

x1

x2OP-9

Metodo di Newton

F xk 1+ F xk xk+ F xk g k

Tx k12---xk

T Hkx k+ +=

gk H k xk+ 0=

Per trovare il punto di stazionarietà si prenda il gradiente di questaapprossimazione del secondo-ordine e si ponga uguale a zero:

xk

Hk

1–– gk

=

xk 1+

xk

Hk

1– gk

–=

E’ basato sulla serie di Taylor del secondo ordine

OP-10

EsempioF x x1

22 x1x

22x 2

2x1+ + +=

x00.5

0.5=

F x x1 F x

x2 F x

2x1 2x2 1+ +

2x1 4x2+= =

g0 F x x x0=

3

3= =

H 2 2

2 4=

x10.5

0.5

2 2

2 4

1–3

3–

0.5

0.5

1 0.5–

0.5– 0.5

3

3–

0.5

0.5

1.5

0–

1–

0.5= = = =

Trova il minimo in un passo

OP-11

Grafico

-2 -1 0 1 2-2

-1

0

1

2

Se la funzione originaria e’ quadratica sarà minimizzata in un passo

OP-12

Metodo di Newton

Se la funzione originaria non e’ quadratica non si avrà, in generale, la convergenza in un passo. Inoltre non si ha la sicurezza neanche della convergenza poiché essa dipende sia dalla funzione sia dal punto iniziale.

Esempio non-quadratico

F x x2 x1– 4

8x 1x2 x1– x2 3+ + +=

Tale funzione ha tre punti di stazionarietà: due minimi e una sella

x1 0.42–

0.42= x

2 0.13–

0.13= x

3 0.55

0.55–=Punti di stazionarietà:

OP-13

Esempio non-quadratico

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2

F(x) F2(x)

Se partiamo dal punto iniziale x01.5

0=

La prima iterazione non porta a convergenza.Il metodo di Newton si intrappola nei minimi locali

OP-14

Condizioni iniziali differenti

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2

F(x)

F2(x)

-2 -1 0 1 2-2

-1

0

1

2

-2 -1 0 1 2-2

-1

0

1

2

OP-15

Sommario

•Sebbene generalmente abbia una convergenza più veloce dei metodi steepest descent, il metodo di Newton presenta un comportamento più complesso•Si può avere convergenza su un punto di stazionarietà che non e’ un minimo, o si può non avere convergenza. Si può avere un comportamento oscillatorio•Il metodo di Newton richiede il calcolo e l’immagazzinamento della matrice Hessiana e della sua inversa

Spesso il calcolo dell’Hessiano e’ impraticabile, specie per le reti neurali dove, nei casi pratici, gli elementi, cioè i pesi sinattici, possono essere dalle centinaia alle svariate migliaia.

Occorrerebbero metodi con terminazione quadratica ma che richiedessero solo derivate prime

OP-16

Metodo del gradiente coniugato1

F x 2--- xTH x dTx c+ +=

pkTHp

j0= k j

Un insieme di vettori {pk} e’ mutuamente coniugato rispetto a unamatrice Hessiana H definita positiva se e solo se:

Un possibile insieme di vettori coniugati sono gli autovettori di H.

zkT Hzj jzk

T zj0 k j= =

(Gli autovettori di matrici simmetriche sono ortogonali.)

Funzione quadratica:

Esiste un numero infinito di insiemi mutuamente coniugati in uno spazio n-dimensionale dato

Si puo’ mostrare che se effettuiamo una sequenza di ricerche lineari lungo qualunque set di direzioni coniugate {p1,..,pn}, il minimo esatto di qualunque funzione quadratica, con n parametri, si raggiunge in al più n ricerche.

Come costruire queste direzioni coniugate?

OP-17

Per funzioni quadratiche

F x Hx d+=

F x 2 H=

gk

gk 1+

gk

– Hxk 1+

d+ Hxk

d+ – H xk

= = =

xk xk 1+ xk–

kpk

= =

kp

k

T Hpj

xkT Hp

jg

kT p

j0= = = k j

La modifica nel gradiente all’iterazione k e’

dove

Le condizioni per la coniugazione possono essere riscritte:

Questo non richiede la conoscenza della matrice Hessiana.

1F x 2

--- xTH x dTx c+ +=

pkTHp

j0= k jDa

a

OP-18

Costituzione delle direzioni coniugate

p0 g0–=

pk gk–

kpk 1–

+=

Scegliere la direzione di ricerca iniziale come il negativo del gradiente.

Scegliere le successive direzioni in modo che siano coniugate.

Per la scelta della scalare k vi sono differenti proposte

Le direzioni di ricerca saranno coniugate se sono ortogonali Le direzioni di ricerca saranno coniugate se sono ortogonali alle modifiche del gradiente.alle modifiche del gradiente.

La prima direzione di ricerca e’ arbitraria. Una scelta molto comune e’ di iniziare la ricerca nella direzione della discesa più ripida, cioè:

OP-19

k

gk 1–T gk

g k 1–T

pk 1–

-----------------------------=

k

g kTg k

g k 1–T gk 1–

-------------------------=

k

g k 1–T gk

g k 1–T gk 1–

-------------------------=

Hestenes-Steifel

Fletcher-Reeves

Polak-Ribiere

Scelte possibili OP-20

Algoritmo del gradiente coniugato

p0 g0–=

pk gk– kpk 1–+=

F x T p

k x xk=k k k k

k x x k=

k

pT F x 2 p------------------------------------------------–

g kTpk

pTH p--------------------–= =

(Per funzioni quadratiche.)

1. La prima direzione di ricerca e’ il negativo del gradiente

2. Selezionare il learning rate per minimizzare lungo la linea.

4. Selezionare la successiva direzione di ricerca usando:

5. Se l’algoritmo non va a convergenza, ritornare al passo 2.

Una funzione quadratica sarà minimizzata in n passi.

3. Fare un passo xk=k pk

OP-21

Esempio

F x 12---xT 2 2

2 4x 1 0 x+= x0

0.5

0.5=

F x x1 F x

x2 F x

2x1 2x2 1+ +

2x1 4x2+= = p0 g– 0 F x –

x x0=

3–3–

= = =

0

3 33–

3–

3– 3–2 2

2 4

3–

3–

--------------------------------------------– 0.2= = x1 x0 0g0– 0.5

0.50.2 3

3– 0.1–

0.1–= = =

OP-22

Esempio

g1 F x x x1=

2 2

2 4

0.1–

0.1–

1

0+ 0.6

0.6–= = =

1

g1T g1

g0T g0

------------

0.6 0.6–0.60.6–

3 333

-----------------------------------------0.7218

---------- 0.04= = = =

p1 g1– 1p0+0.6–

0.60.04

3–

3–+

0.72–

0.48= = =

1

0.6 0.6–0.72–

0.48

0.72– 0.482 2

2 4

0.72–

0.48

---------------------------------------------------------------–0.72–

0.576-------------– 1.25= = =

OP-23

Grafici

-2 -1 0 1 2-2

-1

0

1

2Contour Plot

x1

x2

-2 -1 0 1 2-2

-1

0

1

2

Gradiente coniugato Steepest Descent

x2 x1

1 p1+ 0.1–

0.1–1.25 0.72–

0.48+ 1–

0.5= = =

OP-24

VARIAZIONIVARIAZIONIDELDEL

BACKPROPAGATIONBACKPROPAGATION

Variazioni

• Modifiche euristiche– Momentum

– Learning Rate variabile

• Ottimizzazione numerica standard– Gradiente coniugato

– Metodo di Newton (Levenberg-Marquardt)

L’EBP e’ troppo lento per la maggior parte delle applicazioni.

VP-1

Esempi di superfici di prestazione

Architettura di rete 1-2-1

Diamo alla rete un problema di cui conosciamo la soluzione: approssimare una funzione che non e’ altro che la risposta della

stessa rete per un assegnato set di valori dei pesi e dei bias

VP-2

Esempi di superfici di prestazione

-2 -1 0 1 20

0.25

0.5

0.75

1

w 1 11

10= w 2 11

10= b11

5–= b21

5=

w 1 12

1= w 1 22

1= b2

1–=

Valori dei parametriRisposta desiderata

Si vuole allenare la rete per approssimare la funzione in figura. L’approssimazione sarà esatta per il valore dei parametri su riportato. Sia noto il valore della funzione in un certo numero di punti di campionamento. La funzione costo sia il MSE calcolato in tali punti.

VP-3

Errore quadratico vs. w11,1 e w2

1,1

-5

0

5

10

15

-5

0

5

10

15

0

5

10

-5 0 5 10 15-5

0

5

10

15

w11,1w2

1,1

w11,1

w21,1

Gli altri parametri sono settati al loro valore ottimo. Il cerchio blu indica il minimo errore pari a zero per w1

1,1 = 10 e w21,1=1

VP-4

Errore quadratico vs. w11,1 e b1

1

w11,1

b11

-10

0

10

20

30 -30-20

-100

1020

0

0.5

1

1.5

2

2.5

b11w1

1,1-10 0 10 20 30

-25

-15

-5

5

15

Gli altri parametri sono settati al loro valore ottimo. Il cerchio blu indica il minimo errore pari a zero per w1

1,1 = 0 e b11= -5

VP-5

Errore quadratico vs. b11 e b1

2

-10

-5

0

5

10

-10

-5

0

5

10

0

0.7

1.4

-10 -5 0 5 10-10

-5

0

5

10

b11

b21

b21b1

1

Gli altri parametri sono settati al loro valore ottimo. Il cerchio blu indica il minimo errore in b1

1= -5 e b12= 5

VP-6

Considerazioni

•Vi sono delle simmetrie nelle MLP che fanno sì che lo zero sia un punto di stazionarietà della funzione obiettivo. E’ buona norma non settare il valore iniziale dei parametri a zero.•E’ buona norma non settare il valore iniziale dei parametri a valori troppo grandi. Questo perché la funzione costo tende ad avere regioni molto piatte lontano dal punto ottimo.•E’ buona norma settare il valore iniziale dei parametri a piccoli valori random.•E’ buona norma provare differenti scelte di valori iniziali per aumentare la probabilità di convergenza al minimo globale.

VP-7

Esempio di convergenza

-5 0 5 10 15-5

0

5

10

15

w11,1

w21,1

a

b

Traiettoria a: si ha convergenza al minimo globale ma la convergenza e’ lenta a causa del cambio di curvatura. Un valore alto del learning rate aumenterebbe la velocità di convergenza nelle regioni piatte, ma provocherebbe la instabilità dell’algoritmo quando si cada in una valle.

Traiettoria b: intrappolamento in un minimo locale.

VP-8

Learning Rate troppo alto

-5 0 5 10 15-5

0

5

10

15

w11,1

w21,1

VP-9

Commenti

Si e’ notato che quando l’algoritmo comincia a divergere la traiettoria di ricerca comincia a oscillare attraverso la stretta valle.Se si potesse filtrare la traiettoria mediando gli aggiornamenti dei parametri, questo potrebbe smorzare le oscillazioni e produrre oscillazioni stabili. Questo puo’ essere fatto con un filtro passa-basso.

VP-10

Usa la memoria, cioè l’incremento passato del peso, per accelerare e stabilizzare la convergenza

11 nwnwnynnwnw ijijjiijij momentum: 9,05,0

• I pesi vengono modificati proporzionalmente a quanto essi sono stati cambiati nell’ultima iterazione

• Se ci si trova in un minimo locale o in una zona piatta i pesi vengono ancora modificati, non a causa del gradiente (nullo) ma perché c’è una modifica dei pesi all’iterazione precedente

• Metodo robusto - Accelera l’apprendimento

• Se ne consiglia l’uso per reti con non-linearità

gradiente discendente

1

2,3,...

gradiente discendente con momentum

1

23

VP-12MOMENTUM LEARNINGMOMENTUM LEARNING

Momentum :Esempio

-5 0 5 10 15-5

0

5

10

15

w11,1

w21,1

0.2=

Con l’uso del momentum si e’ potuto usare un learning rate più alto mantenendo la stabilità dell’algoritmo

VP-13

Learning Rate Variabile (VLBP)• Se l’errore quadratico (sull’intero training set) cresce più di

una certa percentuale fissata daadopo un aggiornamento dei pesi, allora l’aggiornamento non viene fatto, il learning rate viene moltiplicato per un fattore (1>>0), e il coefficiente momentum e’ settato a zero.

• Se l’errore quadratico decresce dopo un aggiornamento dei pesi, allora l’aggiornamento viene accettato e il learning rate viene moltiplicato per un fattore >1. Se era stato precedentemente posto a zero, viene resettato al suo valore originale.

• Se l’errore quadratico cresce meno di , allora l’aggiornamento dei pesi viene accettato, ma il learning rate e il coefficiente momentum non vengono modificati.

VP-14

Esempio

-5 0 5 10 15-5

0

5

10

15

100 102 1040

0.5

1

1.5

Iteration Number100 102 1040

20

40

60

Iteration Number

w11,1

w21,1

1.05=

0.7=

4%=

VP-15

Tecniche di ottimizzazione numericaTecniche di ottimizzazione numericaRiformulazione con sole informazioni locali

Approssimazione della funzione costo J(w) nel punto operativo w 0 Sviluppo in serie di Taylor di J intorno a w 0 :

...21

0000000 wwHwwJwwJwwJ

dove: :J gradiente

:H Hessiano matrice delle derivate seconde i cui elementi sono:

ji

ij wwwJ

wH

2

0

NOTA: l’hessiano non può essere calcolato con sole informazioni locali

Deriviamo J rispetto ai pesi: ...000 wwHJwJ

Poiché la superficie di prestazione tende ad essere quadratica intorno al minimo, normalmente possiamo fermarci solo al primo e al secondo termine dell’espressione

VP-16

•Se usiamo solo il primo termine metodi del primo ordine: metodi del

gradiente gradiente stimato come il suo valore in w 0

•Se usiamo anche il secondo termine metodi del secondo ordine: metodi di

Newton ...000 wwHJwJ

Uguagliando a zero l’espressione troncata: 0

1

00 JHww

Vantaggi: se la funzione è quadratica si ottiene la convergenza nel minimo globale in un numero finito di passi (spesso 1 passo)

Svantaggi: massiccio uso di memoria e di tempo di calcolo per l’inversione di H0

Complessità: O( N3) N: numero dei pesi

Una rete neurale può avere migliaia di pesi l’hessiano milioni di termini

Soluzione

Metodi di approssimazione dell’hessiano:

•Metodi LINE SEARCH •Metodi PSEUDO-NEWTON

VP-17

METODI PSEUDO NEWTONMETODI PSEUDO NEWTON

IDEA BASE: fornire approssimazioni dell’hessiano ragionevoli e facili da calcolare

A) Considerare i soli termini diagonali di H si usa un algoritmo di Newton separatamente per ciascun peso:

2

2

i

i

wnJnJ

nw

B) Generalmente questa regola è sostituita dalla:

2

2

i

i

wnJ

nJnw

: Piccola costante che evita i problemi legati a curvature negative o a denominatori nulli

A) e B) danno approssimazioni poco accurate

APPROSSIMAZIONI PIU’ ACCURATE MA POCO COSTOSE:

–LEVEMBERG-MARQUARD (LM)–DAVIDSON - FLETCHER - POWELL (DFP)–BROYDEN - FLETCHER - GOLDFARB - SHANNO (BFGS)

VP-19

Metodo di Newton

wk 1+

wk

Hk

1– gk

–=

Hk J w 2w wk=

gk J w w wk=

Se la funzione costo e’ una somma di funzioni quadratiche:

J w ei2 w

i 1=

N

eT w e w = =

Allora il j-esimo elemento del gradiente e’:

J w jJ w wj

--------------- 2 eiw

eiw

wj

---------------

i 1=

N

= =

VP-27

Forma Matriciale

J w 2Tw e w=

Il gradiente puo’ essere scritto in forma matriciale:

dove e’ la matrice Jacobiana:

-- - ----

x

e1 w

1w---- - ----

e1 w w2

---------------- e1 w

nw----------------

e2 w

1w-------- --------

e2 w w2

---------------- e2 w

wn----------------

eN w

w1-----------------

eN w w2

----------------- eN w

wn-----------------

=

VP-28

Hessiano

2

J w 2 k j

2 J w wk wj

------------------ 2 ei w wk

--------------- ei w wj

--------------- eiw ei w

w k wj

------------------+

i 1=

N

= =

J w 2 2T w w 2S w +=

S w eiw ei

w 2

i 1=

N

=

L’elemento k,j della matrice Hessiana e’:

La matrice Hessiana puo’ allora essere scritta nella seguente forma:

dove

VP-29

Metodo Gauss-Newton

J w 2 2T w w

wk 1+ wk2T wk wk

1– 2T wk e wk –=

wk T wk wk 1–T wk e wk –=

Se assumiamo S(w) piccolo si approssima la matrice Hessiana come:

Il metodo di Newton diventa:

Sostituendo nella formula di aggiornamento dei pesiw

k 1+w

kH

k1– g

k–=

VP-30

Levenberg-Marquardt

TH’ =

G H’ I+=

Gauss-Newton approssima l’Hessiano come:

Questa matrice potrebbe essere singolare, ma puo’ essere resa invertibile nel seguente modo:

1 2 n z1 z2 zn

Gz i H’ I+ z i H’zi z i+ iz i z i

+ i

+ z i= = = =

Se gli autovalori e autovettori di H’ sono:

allora Autovalori di G

wk 1+ wk T wk wk k I+ 1– T wk e wk –=

G puo’ essere resa definita positiva incrementando sino a che i+>0

Questo porta all’algoritmo di Levenberg-Marquardt:

VP-31

Aggiustamento di k

Come k0, LM diventa Gauss-Newton.

wk 1+ wk JT wk J wk 1–JT wk e wk –=

Come k, LM diventa Steepest Descent con piccolo learning rate.

wk 1+ wk

1k-----JT wk

e wk – wk

12k--------- J w –=

Quindi, iniziare con k piccolo per usare Gauss-Newton e

accelerare la convergenza. Se un passo non porta a J(w) inferiore, ripetere lo step con k piu’ alto fino a che J(w) e’ decrementato.

J(w) deve comunque diminuire, poiche’ si compie uno step molto piccolo nella direzione steepest descent.

VP-32

Esempio di LMBP Step

-5 0 5 10 15-5

0

5

10

15

w11,1

w21,1

VP-35

Traiettoria del LMBP

-5 0 5 10 15-5

0

5

10

15

w11,1

w21,1

VP-36

CRITERI DI STOPCRITERI DI STOPNon esistono indicatori diretti che misurano se la rete ha imparato il compito che ci si prefigge

1) Stop in base all’errore su training

2) Stop in base al decremento del MSE da un’iterazione all’altra

OVERFITTING

3) EARLY STOPPING o CROSS VALIDATIONstop in base all’errore sul test set

early stopping

validation set

training set

iterazioni

erro

re

VALIDATION SET: normalmente il 10% del totale numero di training patternSvantaggi: si riduce il numero di esempi utili per l’allenamento e questo può essere un problema nelle applicazioni reali

VP-37

DIMENSIONI DEL TRAINING SETDIMENSIONI DEL TRAINING SET

A)

settrainingsuleaccettabilerrore:pesi#:esempi #:

WN

WN

(Haykin)

B) regola empirica: N 10 Waccettando un’accuratezza di classificazione del 90%

QUALITA’ DEL TRAINING SETQUALITA’ DEL TRAINING SET

• COPERTURA DELLO SPAZIO DEGLI INGRESSI

• Tecniche di estrazione di feature per ridurre le dimensioni dello spazio degli ingressi

• Si riducono le dimensioni della rete

ALTERNATIVA: TECNICHE DI PRUNINGTECNICHE DI PRUNING

VP-38

CRITERIO DI ERRORECRITERIO DI ERRORE

outputnodoindice:patternindice:

, knJJ

k nkn

nknknkkn fydfJ ,

Generalmente: p

nknkkn ydJ , p intero

•Se p = 2 MSE L2

•Se p = 1 metrica di Manhattan

•Se p = intero finito (norma p) Lp nknk

p

nknknk

nk ydydyJ

sgn1

•L: si considerano nulli tutti gli errori eccetto il più alto

•p = 0 : si usa semplicemente il segno dell’errore istantaneo

VP-39