Lezione 5
Reti Neurali
Mercoledì, 10 Novembre 2004
Giuseppe Manco
References:
Chapter 4, Mitchell
Chapter 1-2,4, Haykin
Chapter 1-4, Bishop
Reti Neurali
Outline
•
Perceptron Learning
– Unità neurale
– Gradiente Discendente
•
Reti Multi-Layer
– Funzioni nonlineari
– Reti di funzioni nonlineari
•
Backpropagation dell’errore
– L’algoritmo backpropagation
– problematiche
• Ottimi locali
• Overfitting
Reti Neurali
Modelli Connezionisti
•
Il cervello umano
– Tempo di switch di un neurone: ~ 0.001 (10-3) secondi
– Numero di neuroni: ~10-100 miliardi (1010 – 1011)
– connessioni per neurone: ~10-100.000 (104 – 105)
– Tempo di classificazione: ~0.1 secondi
•
Reti Neurali artificiali
– “… a system composed of many simple processing elements operating in parallel
whose function is determined by network structure, connection strengths, and
the processing performed at computing elements or nodes.” - DARPA (1988)
•
Proprietà
– Molti neuroni
– Molte interconnessioni pesate
– Computazione distribuita
– I pesi si costituiscono automaticamente
Reti Neurali
Reti Neurali
•
Input: dati numerici di alta dimensionalità
– Esempio: input da sensori
– Rumore
•
Output: nominale/Numerico/vettoriale
– Funzione di forma ignota
•
Risultato: leggibilità meno importante delle performances
– Performance misurata in termini di accuratezza
– Leggibilità: capacità di spiegare l’inferenza
•
Esempi
– Classificazione di immagini
– Predizione finanziaria
Reti Neurali
Rete neurale
– http://www.cs.cmu.edu/afs/cs/project/alv/member/www/projects/ALVINN.html
Reti Neurali
Riconoscimento di caratteri
(Progetto scorso anno)
•Dimensionalità
Reti Neurali
Le regioni di decisione
x2
+
+
-
+
x1
-
•
Dato x, vogliamo trovare h(x) consistente con c(x)
– h(x) può essere approssimata con una funzione lineare y
– y = 1: h(x) = +
– y = 0: h(x) = -
 
y  f ( x ; w)
– Qual è una possibile istanziazione di y?
– generalizzazione?
Reti Neurali
Il Perceptron
x1
w1
x2
w2
xn
wn
x0 = 1
w0

n

1 se  w i x i  0
n
ox1 , x 2 , x n   
i 0
wi xi
- 1 altrimenti


i 0
 

  1 se w  x  0
ox   sgn x, w   
- 1 altrimenti
•
Perceptron: modello neuronale singolo
– Input definito come una combinazione lineare
net 
n
w x
i
i 0
i
– Output: funzione di attivazione basata su una soglia sull’input (threshold  = w0)
Reti Neurali
Le regioni di decisione
x2
+
x2
+
-
+
+
-
x1
-
x1
-
+
-
Esempio A
•
Esempio B
Il perceptron può rappresentare alcune funzioni
– Emulazione di porte logiche
– ESERCIZIO: Quali pesi rappresentano g(x1, x2) = AND(x1, x2)?
NOT(x)?
•
Alcune funzioni non sono rappresentabili
– Non linearmente separabili
Reti Neurali
OR(x1, x2)?
Perceptron Learning
•
Regola di learning del Perceptron (Rosenblatt, 1959)
– Idea: un target può aggiornare I pesi in modo tale da produrre l’output desiderato
w i  w i  Δw i
Δw i   (t  o)xi
– dove t = c(x) è il valore di output atteso, o è il valore di output calcolato
–  è il tasso di learning
Reti Neurali
Algoritmo Perceptron learning
•
Algorithm Train-Perceptron (D  {<x, t(x)  c(x)>})
– inizializza tutti I pesi wi a valori random
– WHILE non tutti i valori sono predetti correttamente DO
FOR EACH istanza x  D
Calcola l’output o(x)
FOR i = 1 to n
wi  wi + (t - o)xi
Reti Neurali
Convergenza dell’algoritmo
•
Teorema di convergenza
– Se esiste un insieme di pesi consistente con i dati (cioè: I dati sono linearmente
separabili), l’algoritmo converge
– Complessità computazionale
– Regioni non linearmente separabili
– Se le regioni non sono linearmente separabili, l’algorimo entra in un loop infinito
– Cicla sugli stessi pesi
Reti Neurali
Gradiente Discendente:
Idea
•
Unità lineari
– Consideriamo l’unità più semplice:


ox   net x  
n
w x
i
i
i 0
– Obiettivo: trovare il “migliore adattamento” a D
•
Algoritmo di approssimazione
– Minimizzare l’errore sul training set D
– Funzione dell’errore: Somma dei quadrati (SSE)

 1
t x   ox 2
E w   errorD w  
2 xD

•
Come si minimizza?
– Ottimizzazione semplice
– Ci muoviamo in direzione del più ripido gradiente nello spazio pesi-errore
Reti Neurali
Idea di fondo
•
Vogliamo trovare una sequenza di pesi w(1), w(2), …, w(t) tali che


Ew(t  1)  E w(t)
•
Metodo:


w(t  1)  w(t) - E
•
Giustificazione:
– Sviluppo in serie di Taylor al primo ordine



 
E w   E w(t)   T E w(t) w - w(t) 
– Sostituendo,





T
E w(t  1)  E w(t)    E w(t) w(t  1) - w(t) 
2


 E w(t)    T E w(t) 
– Quando  è positivo, il secondo addendo è sempre negativo
Reti Neurali
Gradiente discendente: delta rule
•
Il gradiente
  E E
E 
E w   
,
,,

w n 
 w 0 w1
•
Regola di learning


Δw  E w 
E
Δw i  
w i
E


w i w i

1
2
1
2

 

t x   ox 2 
2 xD  w i

1
2






t
x

o
x




x D

 


























2
t
x

o
x
t
x

o
x

t
x

o
x
t
x

w
 x 


 

w

w
x D 
i
i
 xD 

E
  t  x   o x  x i 
w i xD
Reti Neurali
Algoritmo del Gradiente Discendente
•
Algorithm Gradient-Descent (D, r)
– Ogni istanza ha la forma <x, t(x)>, dove x è il vettore di input e t(x) è il valore di
output. r è il tasso di learning (ad esempio, 0.05)
– Inizializza i pesi wi a valori random
– WHILE la condizione di terminazione non è soddisfatta, DO
Inizializza ogni wi a 0
FOR each <x, t(x)> in D, DO
Calcola o(x)
FOR each wi, DO
wi  wi + r(t - o)xi
FOR each wi, DO
wi  wi + wi
– RETURN w
Reti Neurali
Delta e Perceptron Rules
x2
+
x2
+
x2
+
-
+
+
-
x1
-
x1
-
+
-
Esempio A
•
+ +
+
- +
+
+
-+ + - - -x1
+
+
+
- +
-
Esempio B
Esempio C
Concetti Linearmente Separabili: classificazione ottimale
– esempio A: Convergenza
•
Concetti Non-LS: approssimazione
– esempio B: non LS; la delta rule converge, ma non è ottimale
– esempio C: non LS; buona generalizzazione
•
Vettore w = somma dei x  D misclassificati
– Perceptron: minimizza w
– Delta Rule: minimizza errore  distanca dal separatore
Reti Neurali
Sommario: Perceptron Learning
• Funzione di base:
y sgn( a)
n
a  wi xi  w0
i 1
 1 se z  0
sgn( z )
 1 se z  0
– Classificazione binaria
– Separabilità lineare
• Due estensioini:
– K classi
– Relazioni nonlineari
Reti Neurali
Estensioni
• K classi
yk g (ak )
n
ak  wki xi  wk 0
i 1
a  Wx  w 0
• Relazioni nonlineari
yk g (ak )
n
ak  wki ( xi )  wk 0
i 1
a  Wφ(x)  w 0
Reti Neurali
Reti Multi-Layer
•
Unità nonlineari
Output Layer
o1
– Funzione d’attivazione (originaria): sgn (w  x)
– Attivazione nonlinare: generalizzazione di sgn
•
Reti Multi-Layer
Hidden Layer h1
o2
h2
h3
h4
u 11
Input Layer
– Multi-Layer Perceptrons (MLPs)
x1
x2
x3
– Una rete multi-layer feedforward è composta da uno strato di input, uno strato
intermedio (nascosto) e uno strato di output
– Gli strati di output è intermedi sono perceptrons (unità nonlineari)
•
MLPs in teoria
– Le reti (di 2 or o più strati) possono rappresentare qualsiasi funzione
•
MLPs in pratica
– Trovare la topologia “giusta” è difficoltoso
– La fase di training è molto dispendiosa
Reti Neurali
v42
Funzioni di attivazione nonlineari
x1
w1
x2
w2
xn
x0 = 1
wn
w0

 
ox   σx  w   σnet 

 
net   w i x i  w  x
n
i 0
•
Funzione sigmoidale
– Funzione di attivazione a threshold: sgn (w  x)
– Funzione nonlineare: generalizzazione di sgn
–  è la funzione sigmoidale
σnet  
– utile per ottenere l’update dal gradiente per
1
1  e net
• Una unità
• Reti Multi-layer
•
Funzione iperbolica
Reti Neurali
sinhnet  e net  e net
σnet  
 net
coshnet  e  e net
Reti Feed-Forward
W
y k  g ( ak )
V
1
g (a) 
1  e a
m
ak   vkj z j  vk 0
j 1
z j  g (b j )
n
b j   w ji xi  wk 0
i 1
Reti Neurali
z
x
y
Addestramento di FFNNs: Backpropagation
• Obiettivo: minimizzazione
dell’errore
1 c
c
1
2
E   (t k  yk ) 2   ek
2 k 1
2 k 1


• Utilizzando E[w ]   E , E ,..., E 
wu 
 w1 w2
u  c m  m n
• Dobbiamo calcolare
Reti Neurali
E
wh
Backpropagation (2)
• Per un peso di output,
E E e j y j a j




v ji e j y j a j v ji
• otteniamo:
E
 ej
e j
a j
e j
a j
y j
 1
Reti Neurali
y j
v ji
 g (a j )  g (a j )(1  g (a j ))
 zi
Backpropagation (3)
E
  j zi
v ji
• riassumendo:
 j  e j g (a j )
• Regola di aggiustamento:
v ji   j zi
Reti Neurali
Backpropagation (4)
• Su un peso interno,
• otteniamo:
ek
  g ( ak )
ak
ak
 vkj
z j
Reti Neurali
E
E z j b j



w ji z j b j w ji
c
c
ek
ek ak
E
  ek
  ek

z j k 1 z j k 1 ak z j
z j
b j
b j
w ji
 g (b j )  g (b j )(1  g (b j ))
 xi
Backpropagation (5)
• riassumendo:
E
  j xi
w ji
c
 j  g (b j )  k vkj
k 1
• Regola di aggiustamento:
w ji   j xi
Reti Neurali
Algoritmo Backpropagation
•
Idea: Riportiamo l’effetto dell’errore ai layers successivi
•
Algorithm Train-by-Backprop (D, r)
– Ogni istanza ha la forma <x, t(x)>, dove x è il vettore di input e t(x) è il valore di
output. r è il tasso di learning (ad esempio, 0.05)
– Inizializza tutti i wi a valori random
– UNTIL la condizione di terminazione non è ottenuta, DO
FOR EACH <x, t(x)> in D, DO
calcola o(x) = (net(x))
FOR EACH unità k di output, DO
 j  e j g (a j )
FOR EACH unità j interna, DO
c
 j  g (b j )  k vkj
k 1
Aggiorna ogni w = wi,j (a = xj) o w = vj,k (a = zk)
Output Layer
Hidden Layer h1
– RETURN w, v
Reti Neurali
o2
h2
h3
Input Layer
x1
x2
v42
h4
w 11
wstart-layer, end-layer  wstart-layer, end-layer +  wstart-layer, end-layer
wstart-layer, end-layer  end-layer aend-layer
o1
x3
Proprietà
•
Gradiente Discendente
– Trova un ottimo locale
•
Backprop in pratica
– Tipicamente, si tende ad includere il momento 
Δw start - layer, end - layer n    δend - layer aend - layer  αΔw start - layer, end - layer n  1
– Quanto generalizza su altri esempi?
– La fase di training è molto lenta: migliaia di iterazioni (epoche)
– Inferenza (applicazione della rete) estremamente veloce
Reti Neurali
Potere di rappresentazione
x1
x2
x1
x2
x1
Reti Neurali
x2
Potere di rappresentazione
•
Representational (i.e., Expressive) Power
– 2-layer feedforward ANN
• Funzioni booleane
• Ogni funzione continua limitata
– 3-layer feedforward ANN: Qualsiasi funzione
•
Inductive Bias
– Spazio delle ipotesi continuo
– Spazio euclideo n-dimensionale (spazio dei pesi)
– Preference bias: “interpolazione” tra gli esempi positivi
– Non ancora compreso a fondo
Reti Neurali
Learning Hidden Layer Representations
•
Unità interne e Feature Extraction
– I valori interni rappresentano le proprietà essenziali dell’input
•
esempio
Input
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
Hidden Values
0
0
0
0
0
1
0
0
Reti Neurali
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1








0.89
0.04
0.08
0.01
0.11
0.88
0.01
0.97
0.27
0.99
0.97
0.71
0.03
0.05
0.02
0.22
0.99
0.99
0.80
0.01
0.98
0.60
0.94
0.01
Output








1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
Evoluzione dell’errore e dei nodi interni
errorD(ok)
zj(01000000), 1  j  3
Reti Neurali
Evoluzione dei pesi
ui1, 1  i  8
– w0 converge a 0
– Cambiamneti dopo le prime 1000 epoche
Reti Neurali
Overfitting
•
Overfitting
– h’peggio di h su Dtrain, meglio su Dtest
•
Overtraining
– Overfitting dovuto a troppe iterazioni
Reti Neurali
Overfitting
•
Altre possibili cause
–
Il numero di nodi interni è fissato
–
Troppo pochi (“underfitting”)
–
•
•
La rete non riesce a riassumere
•
Analogia: sistemi di equazioni non
determinati (troppe variabili rispetto
alle equazioni)
Troppi
•
La rete non generalizza
•
analogia: approssimare una parabola
con un polinomio di grado >> 2
Approcci
–
Prevenzione: selezione degli attributi
–
aggiramento
–
•
Hold out o k-fold cross-validation
•
Weight decay: decrementiamo ogni
peso di un certo fattore ad ogni epoca
recovery: aggiunta o cancellazione di unità
interne
Reti Neurali
Progetto:
Reti per il riconoscimento facciale
sinistra fronte
destra
su
30 x 32 Inputs
Reti Neurali