PROGETTO E TRAINING
DI MLP
PT-1
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 nascosto
infine
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
CONTROLLO DEL LEARNING
PT-2
• Pesi iniziali
• Tasso di learning
• Algoritmo di ricerca dell’ottimo
È inoltre cruciale la qualità e
quantità dei dati di training
• Criterio d’arresto
• Pesi iniziali - Non vi sono molti lavori in letteratura
Regola pratica: pesi random; occorre fare più run
• Tasso di learning: annealing
Es:
-  (n  1)   (n)  
 costante
-  ( n )  0
1
0 ,n0
n
n0
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
LA SCELTA DI UN LEARNING RATE UGUALE PER TUTTI I NODI È DETTATA
DALLA SEMPLICITÀ IMPLEMENTATIVA
PT-3
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 wij  ij
REGOLA DI ADATTAMENTO
DELTA-BAR-DELTA
se S ij(n  1) Dij (n)  0
k


ij ( n  1)   bij (n) se S ij(n  1) Dij (n)  0

altrimenti
0

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
COMPETIZIONE DEI NEURONI NON LINEARI
PT-4
Le non linearità agiscono come meccanismi di competizione che permettono ai diversi
neuroni di specializzarsi in differenti aree dello spazio degli ingressi


wij  f ' (neti )   k wki  y j
k

Derivata della
non linearità
Somma degli errori
pesati provenienti dallo
strato successivo
 i Errore locale
Attività
locale
Differenti neuroni nascosti
con diversi punti di
funzionamento (valore di net)
producono un aggiornamento
dei pesi molto diverso
PROCEDURE DI RICERCA
PT-5
• Ricerca locale
- Metodi del gradiente: estrema semplicità
minimi locali
divergenza
- Metodi del II°ordine: maggior potenza
• Ricerca globale
- Simulated Annealing
- Algoritmi Genetici
- Tabu Search
minimi locali
divergenza
maggior costo computazionale
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
wij  J (wij )
SIA LMS CHE EBP USANO UNA STIMA DEL GRADIENTE
wij (n)   i (n) y j (n)
SI PUÒ MIGLIORARE QUESTA ESPRESSIONE PER ADEGUARSI
A SUPERFICI DI PRESTAZIONE NON CONVESSE
SUPERFICI DI PRESTAZIONE
Espansione in Serie di Taylor
SP-1
Sia F(x) una funzione analitica tale che esistano tutte le sue derivate:
Essa puo’ essere rappresentata dalla sua espansione in serie di Taylor
nell’intorno di un punto x*
F  x  = F  x  +
d
F x 
dx
x = x
 x – x 
2
1 d
+ --F x
2 d x2
2
 x – x  + 
x = x
n
1 d
+ ----F x
n! d x n
n
 x – x  + 
x = x
Possiamo approssimare la F(x) troncando la serie ad un numero
finito di termini
Esempio
–x
F x  = e
Serie di Taylor di F(x) nell’intorno di x* = 0 :
F x  = e
–x
–0
= e
–0
1 –0
2 1 –0
3
– e  x – 0  + ---e  x – 0  – -- e  x – 0  + 
2
6
1 2 1 3
F  x  = 1 – x + -- x – --- x + 
2
6
Approssimazioni della serie di Taylor :
F x   F0 x  = 1
F x  F1 x = 1 – x
1 2
F  x   F 2  x  = 1 – x + --- x
2
SP-2
SP-3
Grafico delle Approssimazioni
6
5
4
F2  x 
3
2
1
F1  x 
F0  x 
0
-2
-1
0
1
2
SP-4
Le tre approssimazioni sono accurate se x e’ vicino a x*
Se x si allontana da x* l’approssimazione migliora all’aumentare
del numero di termini. Infatti i termini sono moltiplicati per
potenze crescenti di (x-x*) e man mano che x si avvicina a x*
questi termini diventano geometricamente piu’ piccoli
SP-5
Caso Vettoriale
F x = F x1 x 2   x n


F  x  = F  x  +
Fx 
Fx
 x 1 – x 1  +
 x 2 – x 2 


 x1
 x2
x=x
x=x
2
2
1 



++
F x
x
–
x
+
-F
x
–
x
x






n
n
1
1
2  x2
 xn
x = x
x = x
1
2
1 
+ --Fx
 x 1 – x 1   x 2 – x 2  + 

2  x 1 x 2
x=x
SP-6
Forma Matriciale
F  x  = F  x  +  F  x 
T
x
= x
 x – x 
T
1
+ ---  x – x  2F  x 
 x – x  + 

2
x=x

Fx
 xn
2
2
 x1
2
Fx

Fx
2
F
=
x
x
x
  
 2 1
2
2
2
2

Fx

x
x
 2 n


Fx  
Fx
x
x
x
x
 1 2
 1 n

2
 x2
Fx
2


Fx
Fx  
x
x
x
x
 n 1
 n 2
2



Fx
F  x  =  x 2



Fx
 x1
Hessiano

Gradiente

2
2
 xn
Fx
SP-7
Derivate Direzionali
Derivata prima (pendenza) di F(x) lungo l’asse xi :
F x  xi
(i-esimo elemento del gradiente)
Derivata seconda (curvatura) di F(x) lungo l’asse xi :
2
2
 Fx   x i
(elemento i,i dell’Hessiano)
Se vogliamo la derivata lungo una qualunque direzione p:
T
p
F  x 
----------------------Derivata prima (pendenza) di F(x) lungo il
p
vettore p:
T
Derivata seconda (curvatura) di F(x) lungo il vettore p:
p
2 F  x  p
-----------------------------2
p
SP-8
Esempio
2
2
F x  = x 1 + 2x 1 x2 + 2 x2
0.5
x =
0
 F  x
x = x
=
p =

F x 
 x1

F x 
 x2
=
1
–1
2x 1 + 2x 2
2x 1 + 4x 2
x = x
x = x
= 1
1
1
1
–
1
T
1
0
p
F  x 
----------------------- = ------------------------ = ------- = 0
p
2
1
–1
Si ottiene derivata nulla se la direzione p e’ ortogonale al gradiente
Si ha pendenza massima quando la direzione p e’ quella del gradiente
SP-9
Grafici
Derivate direzionali
2
20
15
1
1.4
10
1.3
x2
5
1.0
0
0.5
0
2
1
2
1
0
x2
0.0
-1
0
-1
-1
-2
-2
x1
-2
-2
-1
0
x1
1
2
Minimi
SP-10
Strong Minimum
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.
Global Minimum
Il punto x* e’ un unico global minimum di F(x) se
F(x*) < F(x* + x) per tutti i x  0.
Weak 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.
SP-11
Esempio Scalare
4
2 1
F  x  = 3x – 7x – --- x + 6
2
8
Strong Maximum
6
4
2
Strong Minimum
Global Minimum
0
-2
-1
0
1
2
SP-12
Esempio Vettoriale
4
Fx  =  x2 – x1 + 8x 1 x2 – x1 + x2 + 3
2
2
2
F x =  x 1 – 1.5x 1x2 + 2 x2x1
2
2
1.5
1
1
0.5
0
0
-0.5
-1
-1
-1.5
-2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
-2
-2
2
12
-1
0
1
2
8
6
8
4
4
2
0
2
0
2
1
2
1
0
0
-1
-1
-2
-2
1
2
1
0
0
-1
-1
-2
-2
Condizioni di Ottimalità del
Primo-Ordine
1
F  x  = F  x +  x  = F  x  +  F  x 
T
SP-13
 x + ---  x 2F  x 
x + 


2
x=x
x=x
T
 x = x – x
Per piccoli x:
Se x* e’ un minimo, questo implica:
T
F  x +  x   F  x  + F  x 
T
Se  Fx 
x
= x
T
x
 Fx 
T



x

0
F

x
–

x


F

x

–

F

x

allora

x=x
Poiche’ questo deve essere vero per ogni x,

x =x
= 0
x  0
x  F x
T
F  x 
Ma questo implicherebbe che x* non e’ un minimo. Quindi:
F x
x = x
x = x
x = x
x = 0
SP-14
Condizioni del Secondo-Ordine
Se la condizione del primo-ordine e’ soddisfatta (gradiente nullo), allora:
1 T
F x +  x  = F  x  + --  x 2 F  x
2
x
T
Un strong minimum esisterà in x* se x 2F x 

x=x
=
x
x + 
x  0 Per ogni x  0.
La matrice Hessiana deve essere definita positiva. Una matrice H e’ positiva definita se:
z T Hz  0
Per qualunque z  0.
Questa e’ una condizione sufficiente per l’ottimalità.
Una condizione necessaria e’ che la matrice Hessiana sia semidefinita positiva. Una
matrice H e’ semidefinita positiva se:
zT Hz  0
Per qualunque z.
SP-15
Esempio
2
2
F x  = x 1 + 2x 1 x 2 + 2x 2 + x 1
 F  x =
2 x1 + 2x 2 + 1
2 x1 + 4x 2
2 F x  = 2 2
24
= 0
x = – 1
0.5
(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.
2 F  x –  I =
 = 0.76 5.24
2– 2
2 4–
2
=  – 6 + 4 =   – 0.76   – 5.24 
Entrambi gli autovalori sono positivi, quindi strong minimum.
Funzioni Quadratiche
1 xTAx d Tx
x
+
+c
F   = -2
(A simmetrica)
Gradiente e Hessiano:
Utili proprietà del gradiente:
T
T
 h x =  x h  = h
T Qx
Tx
x
Qx
Q
=
+
= 2 Qx (per Q simmetrica)

Gradiente di una funzione quadratica:
F  x  = Ax + d
Hessiano di una funzione Quadratica :
 2F  x  = A
SP-16
Forma quadratica
SP-17
1 xTHx d Tx
x
+
+c
F   = -2
Tutte le derivate di ordine superiore al secondo della F(x) sono
nulle. Quindi i primi tre termini della serie di Taylor forniscono
una rappresentazione esatta della funzione quadratica
Spesso la funzione costo utilizzata e’ quadratica. Quando non lo
fosse, spesso può essere approssimata con una funzione quadratica
in un intorno piccolo, specialmente vicino a un minimo.
Se ||x|| e’ piccolo, tutte le funzioni analitiche si comportano
come quadratiche in un piccolo intorno.
Autovalori e autovettori di H
SP-18
Consideriamo una funzione quadratica che ha un punto di stazionarietà nell’origine, e il cui valore sia zero.
1 xT Hx
x
F   = --2
Usiamo gli autovettori di H come nuova base e operiamo un cambiamento di base.
B = z 1 z 2  zn
Poiche’ H e’ simmetrica, i suoi autovettori sono ortogonali, e
l’inversa coinciderà con la trasposta.
B– 1 = BT
1 0  0

0 2  0


T
H' =  B HB  =
0 0  n
= 
H = BB T
Derivata seconda direzionale
SP-19
Possiamo utilizzare il concetto di derivata direzionale per spiegare il
significato fisico degli autovalori e autovettori di H e come essi determinano la forma della superficie di una funzione quadratica
La derivata seconda di F(x) lungo la direzione p e’:
T
T
p
p Hp
2 F  x  p
------------------------------ = --------------2
2
p
p
p = Bc
Dove c e’ la rappresentazione di p rispetto agli autovettori (nuova base):
n

2
i ci
p TH p c T B T  BB T  Bc c T c i = 1
------------2--- = ------------------------------------------- = ------------T T
T - = ------------------n
p
c B Bc
c c
2
 ci
i=1
SP-20
La derivata seconda secondo p e’ una media pesata degli autovalori
e quindi non può essere più grande del maggior autovalore o più
piccola del minor autovalore, quindi:
T
p Hp
 min  --------------  max
2
Se scegliamo
p = zmax
p
(cioe’ l’autovettore associato al massimo
autovalore)
T
T
c = B p = B z max =
0
1
0

Allora il vettore c e’:

0
0
0
Posizione
corrispondente
a max
SP-21
Autovettori (Massimo Autovalore)
Il valore unitario e’ in corrispondenza a max
poiche’ gli autovettori sono ortonormali. n
Sostituendo a p zmax
T
z max Hz max
 max
i=1
------------------------------=
------------------=
2
n
z max
Il massimo della derivata seconda si
ha in direzione dell’autovettore
corrispondente all’autovalore piu’
grande.
Gli autovalori rappresentano la curvatura
(derivate seconde) lungo gli autovettori
(gli assi principali).

2
i ci

i=1
2
ci
SP-22
Esempio: Circular Hollow
2
2
1 T
F x  = x 1 + x2 = ---x 2 0 x
2
0 2
2 F  x
= 20
02
1 = 2
z1 =
1
0
z2 = 0
2 = 2
1
(In realtà in questo caso qualunque coppia di vettori indipendenti possono essere autovettori)
Poiche’ gli autovalori sono uguali la curvatura deve essere la stessa
in tutte le direzioni e la funzione ha linee di contorno circolari
2
4
1
2
0
0
2
-1
1
2
1
0
0
-1
-1
-2
-2
-2
-2
-1
0
1
2
SP-23
Esempio: Elliptical Hollow
2
2
1 T
F x  = x 1 + x1 x2 + x2 = -- x 2 1 x
2
12
21
12
 2F  x  =
1 = 1
z1 =
1
–1
z2 = 1
2 = 3
1
(gli autovettori non sono univoci, essi possono essere moltiplicati per uno scalare)
In questo caso il massimo della curvatura e’ in direzione di z2
2
3
1
2
0
1
0
2
-1
1
2
1
0
0
-1
-1
-2
-2
-2
-2
-1
0
1
2
SP-24
Esempio: Autovalori di segno opposto
1 2 3
1 2
1 T
F  x  = – --- x 1 – --- x 1 x 2 – --- x 2 = --- x – 0.5 – 1.5 x
4
2
4
2
– 1.5 – 0.5
–0.5 – 1.5
–1.5 – 0.5
 2F  x  =
z1 = –1
1 = 1
2 = – 2
1
z2 = –1
–1
L’Hessiano e’ indefinito. Il punto di stazionarietà e’ una sella,
e’ un minimo lungo il primo autovettore e un massimo lungo
il secondo
2
4
1
0
0
-4
-8
2
-1
1
2
1
0
0
-1
-1
-2
-2
-2
-2
-1
0
1
2
SP-25
Esempio: Valle stazionaria
1 2
1 2
1 T
F x  = --- x 1 – x 1 x 2 + --- x 2 = --- x 1 – 1 x
2
2
2
–1 1
2 F x  =
1 –1
–1 1
z1 = –1
1 = 1
z2 = – 1
2 = 0
1
–1
Il secondo autovalore e’ nullo. Ci sarà una curvatura nulla lungo
il secondo autovettore.
2
3
1
2
0
1
0
2
-1
1
2
1
0
0
-1
-1
-2
-2
-2
-2
-1
0
1
2
OTTIMIZZAZIONE
DELLE PRESTAZIONI
Algoritmo di ottimizzazione di base
Trovare il minimo di una funzione obiettivo
Schema iterativo
xk + 1 = x k +  k p k
o
 x k =  xk + 1 – x k  =  p k
k
 kp k
xk +1
xk
pk - Direzione di ricerca
k - Learning Rate o Step size
Gli algoritmi che vedremo si distinguono per la scelta della
direzione di ricerca.
OP-1
Steepest Descent
OP-2
Scegliere il passo successivo in modo che la funzione decresca:
F x k + 1   F  xk 
Per piccoli cambiamenti nella x si puo’ approssimare F(x):
T x
x
x
x
x
g
=
+
+
F k + 1
F k  k   F k 
k k
dove
g k   F x 
x =xk
Se vogliamo che la funzione decresca:
g Tk  xk =  kg Tk p k  0
Possiamo massimizzare il decremento scegliendo:
pk = –gk
x k + 1 = xk –  k g k
OP-3
Esempio
2
2
x
=
+
2
+
2
F 
x1
x1 x 2
x 2 + x1
x 0 = 0.5
 = 0.1
0.5
F  x  =

F x 
 x1

F x 
 x2
=
2x 1 + 2x2 + 1
g 0 =  F x 
2x 1 + 4x 2
x 1 = x 0 –  g 0 = 0.5 – 0.1 3 = 0.2
0.5
3
0.2
x2 = x1 –  g1 = 0.2 – 0.1 1.8 = 0.02
0.2
1.2
0.08
x=
= 3
x0
3
Grafico
OP-4
Per valori bassi di  la traiettoria e’ sempre perpendicolare alle
linee di contorno
2
Se incrementassimo  per
es. a 0.035, la traiettoria
oscillerebbe. Al crescere di
 le oscillazioni aumentano
in ampiezza e l’algoritmo
diventa instabile.
1
0
-1
-2
-2
-1
0
1
2
Stabilizzazione del Learning Rate
(Quadratico)
OP-5
Non c’e’ un metodo sistematico per trovare  per qualunque tipo di
funzione. Per funzioni quadratiche si ha un limite superiore.
1 x THx d Tx
x
=
-+
+c
F 
2
F  x  = Hx + d
xk + 1 =  I –  H x k –  d
x k + 1 = xk –  gk = x k –   Hx k + d 
La stabilità e’ determinata dagli autovalori di questa matrice, che
devono avere ampiezza minore dell’unità
Poiche’:
 I –  H  z = z –  Hz = z –   z =  1 –    z
i
i
i
i
(i - autovalore di H)
i i
i
i
Autovalore di
[I - H].
Requisiti per la stabilità dell’algoritmo steepest descent:
 1 –    1
i
2
  ---i
2
--  ------max
OP-6
Esempio


0.851     = 5.24  z = 0.526  


=
0.764


z
=
 1
  2
 2

 1

– 0.526   

0.851  

A= 22
24
2
2
--  ------- = ---------- = 0.38
max
5.24
 = 0.37
 = 0.39
2
2
1
1
0
0
-1
-1
-2
-2
-1
0
1
2
-2
-2
-1
0
1
2
Minimizzazione lungo una linea
OP-7
Un altro approccio per scegliere il learning rate e’ quello di
minimizzare F rispetto a k a ciascuna iterazione cioe’: Scegliere
k per minimizzare:
F  x k +  k pk 
Si puo’ usare un metodo detto Line Search
Per funzioni quadratiche si puo’ trovare la soluzione analiticamente
T
T
p k +  k pk  2F  x 
pk
-----d----(F  xk +  k p k ) = F  x 
x = xk
x = xk
dk
T
T
 F  x x x pk
g
p
= k
k k
------------------------------------------ = – ------------------ k = – -----T 2
T
pk  F x 
p
p k Hkp k
x=x k
k
dove
Hk  2 F  x
x = xk
OP-8
Esempio
1 T
F  x = -- x 2 2 x + 1 0 x
2
24
F  x  =

F x 
 x1

F x 
 x2
=
2x 1 + 2x2 + 1
2x 1 + 4x 2
–3
33
–3
=
–
------------------------------ = 0.2
0
2 2 –3
–3 –3
2 4 –3
x 0 = 0.5
0.5
p 0 = –g 0 = –  F x 
x = x0
=
–3
–3
x1 = x0 –  0 g0 = 0.5 – 0.2 3 = – 0.1
0.5
3
– 0.1
OP-9
Grafico
Contour Plot
2
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.
x2
1
0
-1
-2
-2
-1
0
x1
1
2
T
d  x +  p  = d x
d x +  p 
x
F k
F k + 1 =  F  x = x
k k
k
k k
k + 1d k
dk
dk
= F  x 
T
T
x = xk + 1
pk = gk + 1 pk
Metodo di Newton
OP-10
E’ basato sulla serie di Taylor del secondo ordine
T
1 xT H x
x
x
x
x
g
x
F  k + 1  = F  k +  k   F  k  + k  k + -2-  k k k
Per trovare il punto di stazionarietà si prenda il gradiente di questa
approssimazione del secondo-ordine e si ponga uguale a zero:
gk + Hk  xk = 0
–1
 x k = – Hk g k
xk + 1 = xk – H–k 1 gk
OP-11
Esempio
2
2
F  x  = x1 + 2 x1 x 2 + 2x 2 + x1
x 0 = 0.5
0.5
F  x  =

F x 
 x1

F x 
 x2
=
2x 1 + 2x2 + 1
g 0 =  F x 
x=
= 3
x0
3
2x 1 + 4x 2
H= 22
24
x1 =
0.5
22
–
0.5
24
–1
3
=
3
0.5
1 – 0.5 3
–
=
0.5
– 0.5 0.5 3
Trova il minimo in un passo
0.5
1.5
–
=
0.5
0
–1
0.5
OP-12
Grafico
Se la funzione originaria e’ quadratica sarà minimizzata in un passo
2
1
0
-1
-2
-2
-1
0
1
2
OP-13
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
4
Fx  =  x2 – x1 + 8x 1 x2 – x1 + x2 + 3
Tale funzione ha tre punti di stazionarietà: due minimi e una sella
Punti di stazionarietà:
1
x =
– 0.42
0.42
2
x =
– 0.13
0.13
3
x =
0.55
– 0.55
OP-14
Esempio non-quadratico
Se partiamo dal punto iniziale
x 0 = 1.5
0
La prima iterazione non porta a convergenza.
Il metodo di Newton si intrappola nei minimi locali
F(x)
F2(x)
2
2
1
1
0
0
-1
-1
-2
-2
-1
0
1
2
-2
-2
-1
0
1
2
OP-15
Condizioni iniziali differenti
F(x)
2
2
2
1
1
1
0
0
0
-1
-1
-1
-2
-2
F2(x)
-1
0
1
2
-2
-2
-1
0
1
2
-2
-2
2
2
2
1
1
1
0
0
0
-1
-1
-1
-2
-2
-1
0
1
2
-2
-2
-1
0
1
2
-2
-2
-1
0
1
2
-1
0
1
2
Sommario
OP-16
•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
Metodo del gradiente coniugato
Funzione quadratica:
OP-17
1 x THx d Tx
x
-=
+
+c
F 
2
Un insieme di vettori {pk} e’ mutuamente coniugato rispetto a una
matrice Hessiana H definita positiva se e solo se:
p Tk Hp j = 0
kj
Esiste un numero infinito di insiemi mutuamente coniugati in
uno spazio n-dimensionale dato
Un possibile insieme di vettori coniugati sono gli autovettori di H.
zTk Hz j =  jz Tk z j = 0
kj
(Gli autovettori di matrici simmetriche sono ortogonali.)
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?
Per funzioni quadratiche
1 x THx d Tx
x
-=
+
+c
F 
2
F  x  = Hx + d
 2F  x  = H
La modifica nel gradiente all’iterazione k e’
g = g
k
k+1
– g =  Hx
k
k +1
+ d  – Hx + d  = H  x
k
k
dove
 x k =  xk + 1 – xk  =  p k
k
Le condizioni per la coniugazione possono essere riscritte:
p Tk Hp j = 0
Da
kj
a
T
T
T
p
Hp
x
Hp
g
=
=
k k
 k
 k pj = 0
j
j
k j
Questo non richiede la conoscenza della matrice Hessiana.
OP-18
OP-19
Costituzione delle direzioni coniugate
Le direzioni di ricerca saranno coniugate se sono ortogonali
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è:
Scegliere la direzione di ricerca iniziale come il negativo del gradiente.
p0 = –g0
Scegliere le successive direzioni in modo che siano coniugate.
p k = – gk +  k p k – 1
Per la scelta della scalare k vi sono differenti proposte
Scelte possibili
T
gk – 1 gk
 k = ---------T-------------------g k – 1 p k – 1
T
gkgk
k = -------------------------
Hestenes-Steifel
Fletcher-Reeves
g Tk – 1 gk – 1
T
g
g
k = ----------k----–--1------k---
g Tk – 1 gk – 1
Polak-Ribiere
OP-20
OP-21
Algoritmo del gradiente coniugato
1. La prima direzione di ricerca e’ il negativo del gradiente
p0 = –g0
2. Selezionare il learning rate per minimizzare lungo la linea.
T
x
p
 F  x = x k k
g Tk p k
------------------------------------------ = – ------------------ k = – -----T 2
T
pk  F x 
p
p k Hkp k
x=x k
(Per funzioni
quadratiche.)
k
3. Fare un passo xk=k pk
4. Selezionare la successiva direzione di ricerca usando:
pk = – gk + k pk – 1
5. Se l’algoritmo non va a convergenza, ritornare al passo 2.
Una funzione quadratica sarà minimizzata in n passi.
OP-22
Esempio
1 T
F  x = -- x 2 2 x + 1 0 x
2
24
F  x  =

F x 
 x1

F x 
 x2
=
2x 1 + 2x2 + 1
2x 1 + 4x 2
–3
33
–3
=
–
------------------------------ = 0.2
0
2 2 –3
–3 –3
2 4 –3
x 0 = 0.5
0.5
p 0 = –g 0 = –  F x 
x = x0
=
–3
–3
x1 = x0 –  0 g0 = 0.5 – 0.2 3 = – 0.1
0.5
3
– 0.1
OP-23
Esempio
g 1 =  F x 
1 =
x = x1
T
g1 g1
-----------gT0 g0
=
2 2 – 0.1 + 1 =
2 4 – 0.1
0
0.6
–0.6
0.6
0.6 – 0.6
– 0.6
0.72
= ----------------------------------------- = ---------- = 0.04
18
3
33
3
p 1 = – g1 + 1 p 0 =
– 0.6
–3
+ 0.04
=
0.6
–3
–0.72
0.48
– 0.72
0.6 – 0.6
0.48
–0.72
=
–
------------------------------------------ = – ------------- = 1.25
1
0.576
2 2 –0.72
–0.72 0.48
2 4 0.48
OP-24
Grafici
x2 = x1 +  1 p1 = – 0.1 + 1.25 – 0.72 = – 1
– 0.1
0.48
Gradiente coniugato
Steepest Descent
Contour Plot
2
1
1
x2
2
0
0
-1
-1
-2
-2
0.5
-1
0
1
2
-2
-2
-1
0
x1
1
2
VARIAZIONI
DEL
BACKPROPAGATION
Variazioni
VP-1
L’EBP e’ troppo lento per la maggior parte delle applicazioni.
• Modifiche euristiche
– Momentum
– Learning Rate variabile
• Ottimizzazione numerica standard
– Gradiente coniugato
– Metodo di Newton (Levenberg-Marquardt)
VP-2
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
Esempi di superfici di prestazione
VP-3
Risposta desiderata
Valori dei parametri
1
1
1
w 1 1 = 10 w 2 1 = 10
0.75
2
w 1 1 = 1
2
1
1
b1 = –5 b 2 = 5
w 1 2 = 1
2
b = –1
0.5
0.25
0
-2
-1
0
1
2
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.
Errore quadratico vs.
1
w 1,1 e
w
2
VP-4
1,1
15
10
10
w21,1
5
5
0
-5
0
0
-5
2
-5
-5
w
0
5
10
15
0
5
1,1
w11,1
5
10
10
15
15
w11,1
Gli altri parametri sono settati al loro valore ottimo. Il cerchio
blu indica il minimo errore pari a zero per w11,1 = 10 e w21,1=1
Errore quadratico vs.
1
w 1,1 e
1
b1
VP-5
15
2.5
5
2
1.5
b11
-5
1
0.5
-15
0
-10
20
0
10
10
-25
-10
0
10
20
30
w11,1
0
-10
20
-20
30
-30
b11
w11,1
Gli altri parametri sono settati al loro valore ottimo. Il cerchio
blu indica il minimo errore pari a zero per w11,1 = 0 e b11= -5
1
b 1e
Errore quadratico vs.
b
VP-6
1
2
10
1.4
5
0.7
2
b
0
1
0
-10
-5
-5
-10
-5
0
-10
-10
-5
0
5
10
b11
0
5
5
10
10
b21
b11
Gli altri parametri sono settati al loro valore ottimo. Il cerchio
blu indica il minimo errore in b11= -5 e b12= 5
Considerazioni
VP-7
•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-8
Esempio di convergenza
15
10
w21,1
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.
b
5
0
Traiettoria
intrappolamento
minimo locale.
a
-5
-5
0
5
w11,1
10
15
in
b:
un
Learning Rate troppo alto
15
10
w21,1
5
0
-5
-5
0
5
w11,1
10
15
VP-9
Commenti
VP-10
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.
MOMENTUM LEARNING
VP-12
Usa la memoria, cioè l’incremento passato del peso,
per accelerare e stabilizzare la convergenza
wij n  1  wij n     i n  y j n    wij n  wij n  1  : momentum
1
  0,5  0,9
• I pesi vengono modificati proporzionalmente a
quanto essi sono stati cambiati nell’ultima
iterazione
2,3,...
gradiente discendente
1
3
• 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
2
• Metodo robusto - Accelera l’apprendimento
gradiente discendente
con momentum
• Se ne consiglia l’uso per reti con non-linearità
VP-13
Momentum :Esempio
15
Con l’uso del momentum si
e’ potuto usare un learning
rate più alto mantenendo la
stabilità dell’algoritmo
10
w21,1
5
0
-5
-5
0
5
w11,1
 = 0.2
10
15
Learning Rate Variabile (VLBP)
VP-14
• Se l’errore quadratico (sull’intero training set) cresce più di
una certa percentuale fissata  da 1 a 5% dopo 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-15
Esempio
15
 = 1.05
10
 = 0.7
2
w
1,1
5
 = 4%
0
-5
-5
0
5
10
15
w11,1
1.5
60
1
40
0.5
20
0 0
10
102
Iteration Number
104
0 0
10
102
Iteration Number
104
Tecniche di ottimizzazione numerica
VP-16
Riformulazione 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 :
J w  w0   J0  w  w0  J0  1  w  w0  H0 w  w0   ...
2
dove:
J : gradiente
Hessiano  matrice delle derivate
H : seconde i cui elementi sono:
 2 J w
H ij w0  
wi w j
NOTA: l’hessiano non può essere calcolato con sole informazioni locali
Deriviamo J rispetto ai pesi:
J w  J 0  H0 w  w0   ...
Poiché la superficie di prestazione tende ad essere quadratica intorno al minimo,
normalmente possiamo fermarci solo al primo e al secondo termine dell’espressione
•Se usiamo solo il primo termine 
 metodi del primo ordine: metodi del gradiente
gradiente stimato come il suo valore in w 0
VP-17
•Se usiamo anche il secondo termine 
 metodi del secondo ordine: metodi di Newton
J w  J 0  H0 w  w0   ...
Uguagliando a zero l’espressione troncata:
w  w0  H01  J 0
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
METODI PSEUDO NEWTON
VP-19
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:
 wi n  
 wi n  
B) Generalmente questa regola è sostituita dalla:
 J n 
 2 J n 
wi2
 J n 
 2 J n 

2
wi
 : 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)
Metodo di Newton
wk + 1 = wk – Hk– 1 gk
Hk  2 J w
w= w
gk  J w
w= w
k
k
Se la funzione costo e’ una somma di funzioni quadratiche:
N
J w =

2
e i w
T
= e w e w
i =1
Allora il j-esimo elemento del gradiente e’:
N
ei w
  J wj = --------------- = 2  ei w --------------wj
wj
i=1
 J w
VP-27
Forma Matriciale
Il gradiente puo’ essere scritto in forma matriciale:
T
 J w = 2  w e w
dove  e’ la matrice Jacobiana:
e 1  w e 1  w
e 1  w
---------------- ----------------  --------------w1
w2
wn


=

 x 
e 2  w e 2  w
e 2  w
-------------- - ----------------  ---------------w1
w2
wn
e N  w e N  w
e N  w
----------------- ----------------  ----------------w1
w2
wn
VP-28
VP-29
Hessiano
L’elemento k,j della matrice Hessiana e’:
  J w k j
2
N
w


J
= ------------------ = 2
wk w j
 ei w ei w
2

i w 
e
 --------w--k----- -------w----j---- + ei w -----w--k------w----j- 

i = 1
2
La matrice Hessiana puo’ allora essere scritta nella seguente forma:
2
T
 J w = 2 ww + 2 S w
dove
N
S w =
 ei w2e i w
i=1
Metodo Gauss-Newton
VP-30
Se assumiamo S(w) piccolo si approssima la matrice Hessiana come:
2
 J w  2 ww
T
Sostituendo nella formula di aggiornamento dei pesi
wk + 1 = wk – Hk– 1 gk
Il metodo di Newton diventa:
–1
wk + 1 = wk – 2T wk wk   2T wk e wk 
T
= wk –    wk   wk  
–1 T
  wk  e  wk 
Levenberg-Marquardt
Gauss-Newton approssima l’Hessiano come:
H’ = T
VP-31
Questa matrice potrebbe essere singolare, ma puo’ essere resa invertibile nel
seguente modo:
G = H’ + mI
Se gli autovalori e autovettori di H’ sono:
 1 2    n
 z1 z2   zn
allora
Autovalori di G
Gz i = H’ + mI z i = H’z i + mz i = iz i + mz i =  i + mz i
G puo’ essere resa definita positiva incrementando m sino a che i+m>0
Questo porta all’algoritmo di Levenberg-Marquardt:
wk + 1 = wk – T wk wk  + mk I – 1T wk e wk 
Aggiustamento di mk
VP-32
Come mk0, LM diventa Gauss-Newton.
–1
wk + 1 = wk –  JT wk J wk  J T wk  e wk 
Come mk, LM diventa Steepest Descent con piccolo learning rate.
wk + 1  wk – ---1--J T wk  e wk  = wk – -----1----  J w
mk
2 mk
Quindi, iniziare con mk piccolo per usare Gauss-Newton e
accelerare la convergenza. Se un passo non porta a J(w) inferiore,
ripetere lo step con mk 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.
Esempio di LMBP Step
15
10
w21,1
5
0
-5
-5
0
5
w11,1
10
15
VP-35
Traiettoria del LMBP
15
10
w21,1
5
0
-5
-5
0
5
w11,1
10
15
VP-36
CRITERI DI STOP
VP-37
Non 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 VALIDATION
stop in base all’errore sul test set
early stopping
errore
validation set
training set
iterazioni
VALIDATION SET: normalmente il 10%
del totale numero di training pattern
Svantaggi: si riduce il numero di esempi
utili per l’allenamento e questo può essere
un problema nelle applicazioni reali
DIMENSIONI DEL TRAINING SET
A)
(Haykin)
N W

N : # esempi
W : # pesi
 : errore accettabil e sul training set
B) regola empirica: N  10 W
accettando un’accuratezza di classificazione del 90%
QUALITA’ 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 PRUNING
VP-38
CRITERIO DI ERRORE
J    J n, k
k
n
VP-39
n : indice pattern
k : indice nodo output
J n,k  f dnk  ynk   f  nk 
Generalmente:
J n, k  dnk  ynk 
p
p intero
•Se p = 2  MSE  L2
•Se p = 1  metrica di Manhattan
•Se p = intero finito (norma p)  Lp
J nk
 dnk  ynk
ynk
p 1
•L: si considerano nulli tutti gli errori eccetto il più alto
•p = 0 : si usa semplicemente il segno dell’errore istantaneo
 sgn dnk  ynk 