Learning Non Supervisionato

Learning Non Supervisionato
LEARNING NON SUPERVISIONATO
Non c’è insegnante 
Reti con Input e Output,
Nessun Feedback dall’ambiente
La Rete deve scoprire Da Sola
Caratteristiche, Regolarità, Correlazioni, etc.
nei dati di input. (AUTO-ORGANIZZAZIONE)
Durante il Learning i pesi variano
in accordo con una Regola Interna
specificata A Priori
LNS-1
Cosa possono individuare tali reti?
LNS-2
 FAMILIARITA’
Quando un nuovo input è simile ai pattern visti in passato
(ex: un output a valori continui)
 ANALISI DELLE COMPONENTI PRINCIPALI
estendendo il caso precedente a più unità porta ad una base
lungo cui misurare la somiglianza a esempi precedenti
 CLUSTERING
Un set di output a valori binari può indicare a quale
categoria appartiene un dato input
 CODIFICA
L’output può essere una versione codificata dell’input
 FEATURE MAPPING
Un output con una data struttura geometrica (ex: una
matrice) può mappare gli input in punti diversi della
struttura, realizzando una mappa topografica dell’input 
Input simili  Output vicini
Quando utilizzare le Reti NON Supervisionate:
LNS-3
 Quando il learning supervisionato non è possibile
 Quando il learning supervisionato è troppo lento
 In cascata ad una rete supervisionata
LEARNING HEBBIANO
LNS-4
1940: Donald Hebb, studiando la comunicazione tra neuroni, verificò
che l’eccitazione ripetuta di un neurone i da parte di un
neurone j portava all’abbassamento della soglia di eccitazione
del neurone i.
LA COMUNICAZIONE E’ FACILITATA
DALL’ECCITAZIONE RIPETUTA
xj
yi
wij
j
i
Estensione ai sistemi neurali artificiali:
Il peso della wij della connessione tra i neuroni i e j cresce al fluire
di un segnale da j a i:
wij    x j yi Regola di Hebb
1 Strato
D Input
1 Output Lineare
D
 x1 


x  
 xD 
x1
w1
w2
x2

T
i 1
Gli Input più frequenti
avranno, a lungo termine,
più influenza e
produrranno un output
maggiore.
S
y
xD
y   wi  xi  w  x  x  w  w  x  cos 
T
wD
LNS-5
x
y 
 x1 y 
 w      
w
 xD y 
w  x 1
x w  grande y
x w y = 0
L’ampiezza di y
misura la somiglianza
tra Input e Pesi
Durante il learning, i pesi sono esposti ai dati di Input e condensano
l’informazione in essi contenuta nel loro valore 
I PESI SONO LA MEMORIA A LUNGO TERMINE DELLA RETE
Per un singolo peso:

wnew  wold    xy  wold    x  wold x  wold 1    x 2

LNS-6
PROBLEMA: I pesi crescono senza limite ed il learning
non si ferma mai 
REGOLA DI OJA
(versione stabile)
 Vincolare la crescita dei pesi:
1. Rinormalizzazione dei pesi dopo l’aggiornamento:
wi '    wi
w'  1
oppure
2. Aggiungere un termine proporzionale a y2, nella formula di Hebb
wi    y  xi  y  wi  Regola di Oja
Hebb  correlazione
LNS-7
n     yn   xn     xn  xn 
Learning on-line  w
Learning batch
T
 wn 
 N

T
 w      xi   x i   w0    Rˆ x  w0
 i 1

 Ex1 x1 
Rˆ x  Rx   
 Ex D x1 


Ex1 x D  
 Matrice di autocorrelazione

 degli Input
Ex D x D 
Il learning Hebbiano aggiorna i pesi con una
stima della funzione di autocorrelazione
x1,, xN 
Es: D=2
V
Hebb  potenza
Set di dati
1
V
N
V  R  w
potenza in uscita
N
N
1
T
T
T
2
y i    w  x  x w  w Rx w

N
i 1
i 1
w
w1
LNS-8
2
1 N
T
Rx  R    xi   x i 
N i 1
definita positiva
V
T
V 
 w Rx  Rx w  2 Rx w
w
V  2Rw  w  Rw0
La regola di Hebb muove i pesi nella direzione del
gradiente, nel campo di potenza dei dati di Input
Divergenza (campo illimitato)
LNS-9
Legame Potenza - Varianza
Massima Potenza  Massima Varianza
Varianza - Informazione
Esempio:
Nube di punti 2-D
Spazio a dimensione minore
(Componente Principale)
E’ la direzione a maggiore varianza
Regola di Oja
wi   yxi  y wi 
Mantiene i pesi con norma unitaria
LNS-10
LNS-11
Dimostrazione:
wi n  1 
wi n    y n xn 
12

D
2
 wi n    y n xn  
 i 1

 wi n    y n xi n   y n wi n   O  2
per  piccolo
 
Posto:
x 'n (i )  xn (i )  y (n) wi (n)
wi (n  1)  wi (n)  y (n) x 'i (n)
Input effettivo
x  x1
Esempio:
x2 
w  w1
w2 
LNS-12
x2
x2
w
w0
x1
w 1
w
w0
x1
• I pesi partono da piccoli valori random e vengono
aggiornati secondo la regola di Oja:
w1   yx1  y w1 ;
w2   yx2  y w2 ;
w 1
L’output finale è la proiezione dell’input x nella direzione di w
È dovuto alla scelta di UNITA’ LINEARI
LNS-13
a) Input a media zero < x > = 0
Output a media zero < y > = 0
(qualunque sia la direzione di w)
MA la direzione di wOja fa sì che <| y |> sia massimo
b) Input a media diversa da zero
Output con media massima in corrispondenza di wOja
La direzione di wOja fa sì che <| y |> sia massimo
LNS-14
Significato di wOja
Rw   w
R funzione di autocorrelazione
 scalare reale
w è un autovettore di R e  l’autovalore massimo
x2
a asse principale
a  wOja
x1
LNS-15
Ricapitolando:
La regola di Oja converge ad un vettore peso che ha le
seguenti proprietà:
 w 1
 w ha la direzione dell’ autovettore di C con autovalore massimo
 w ha la direzione che massimizza la <y2>
y
2
 
 w x
T
2
 w x  x w  w Cw
T
T
T
La forma quadratica, per w fissato è massimizzata quando
w ha la direzione dell’autovettore massimo di C
Per dati con
x 0
 
max y 2  max( varianza )
LNS-16
ANALISI DELLE COMPONENTI PRINCIPALI (PCA)
La regola di Oja produce un vettore di pesi nella direzione in cui si
trova la maggiore informazione sui dati di input
COMPONENTE PRINCIPALE
Come trovare altre direzioni che tengono conto il più possibile della
varianza dei dati di Input?
x  D
Scopo  Trovare un sistema di coordinate
ORTONORMALE
M vettori tra
loro ortogonali
M D
M vettori di
lunghezza unitaria
che riduca la dimensione dei dati,
massimando l’informazione contenuta
Esempio
A
LNS-17
OB
SECONDA
COMPONENTE
PRINCIPALE
(A BASSA VARIANZA)
PCA
B
OA
PRIMA
COMPONENTE
PRINCIPALE
(AD ALTA VARIANZA)
O
La proiezione lungo OA consente di evidenziare i cluster
 La prima componente principale si prende lungo la
direzione a massima varianza;
 La seconda lungo la direzione a massima varianza del
sottospazio ortogonale alla prima;
 La terza lungo …
LNS-18
Procedura:
x  D
se
Sia C la matrice di covarianza di x : C  x  x
x 0
1
   
 0




 y  QT x
0
 
D 
con
  y y
T

CR

dove:
1  2    D
autovalori di C e
colonne di Q: autovettori corrispondenti
y  vettore delle componenti principali di x
x 0
T
matrice di autocorrelazione
LNS-19
Riassumendo:
Q


y  x q1
T
T
x q2


x q D  QT x
T
D
x  Q y   yi q j
j 1
Scartando le combinazioni a piccola varianza:
M
xˆ   y j q j  q1
j 1

 y1 
qM    
 yM 
MD
LNS-20
Algoritmi basati sulla risoluzione
di equazioni matriciali
PCA
Reti Neurali
w11
w21
w31
x1
x2

xD
RETI NEURALI PCA
S
y1
S
y2
w1D
Rete Lineare

w2D
S
wMD
x  D
y  M
D
yi   wij x j
j 1
yM
M D
i  1, M
i


wij   yi  x j   wkj yk 
k 1


i=1
w1j
xj
1
y1
I componente principale
w1 j   y1 x j  w1 j y1 
(regola di Oja)
x' j  x j
i=3
w3 j  
i=2
w2j
xj
LNS-21
Regola di Sanger
2
y2
II componente principale
w2 j   y2 x j  w1 j y1  w2 j y2  
  y2 x' j w2 j y2 
x' j  x j  w1 j y1  proiezione in uno
spazio ortogonale alla I componente
LNS-22
N.B. I pesi relativi alla II CP convergeranno solo dopo la
convergenza dei pesi della I CP, e così via …
PCA è il miglior “feature extractor” LINEARE
1
COMPRESSIONE DATI
Non esiste un sistema lineare che fornisca migliori caratteristiche per
la ricostruzione  applicazione PCA per la compressione dei dati
x
T
W
al trasmettitore:
compressione proiezione
y
R
~
x
W-1
al ricevitore:
decompressione
LNS-23
2
CLASSIFICAZIONE
x2
1
2 CLASSI
2
x1
Direzione principale
x1  ricostruzione
x2  classificazione
Reti Competitive e di Kohonen
CK-1
LEARNING NON SUPERVISIONATO COMPETITIVO
Solo un’unità è attiva (vincitore)
Scopo: clusterizzare i dati in ingresso
Codifica
Compressione
Elaborazione di immagini
Ottimizzazione combinatoria
Un Output per ogni categoria
Non sono robuste
Non possono rappresentare una conoscenza gerarchica
y1
•Feature Mapping (Kohonen)
y2
x1 x2 x 3 x 4
CK-2
SEMPLICE LEARNING COMPETITIVO
y1
x = [x1 , . . . , xN]
(0 , 1)
y = [y1 , . . . , yN]
(0 , 1)
hi   wij  x j  wi  x
yM
...
...
j
wi  w11  w1N 
i* : wi *  x  w  x
T
T
x1 x2 x3
VINCITORE
xN
x
yi *  1
wi  1 
wi
wi*  x  wi  x
wi • x
IL VINCITORE E’ L’UNITA’ PIU’ VICINA ALL’INPUT
CK-3
IL LEARNING
w(t = 0) = random
x
wi* j   x j  wi* j 
 yi*  1

 yi  0 i  i *
wi new
x-wi
01
 (x-wi)
wi
wi j    yi x j  wi j  REGOLA
INSTAR
 Sposta wi* verso x p
 Fa sì che l’unità i* abbia maggiore probabilità di vincere in
futuro per un Input simile a x
CK-4
Esempio di CLUSTERING

x p  x1p
x2p
x3p

P = 1, … , N
numero di esempi
p1
p2
wi  wi1
wi
Input continui
Input binari
wi 2
wi 3 
;
w 1
i
Stato iniziale
Stato finale
vettori prototipo - individuano dei punti nello spazio
Tassellazione di Voronoi
CK-5
1 solo strato  partizioni convesse dello spazio degli input
N° di cluster da fissare a priori
troppi cluster  cluster morti
input simili in cluster diversi
pochi cluster  ogni unità rappresenta + di un cluster
Problema delle unità morte
COSCIENZA
hi
bi*  bi

hi  bi
CK-6
COMPETIZIONE SOFT
 Anche i neuroni vicini al vincitore possono essere attivi
(bolla di attività)
 Connessioni laterali funzione della distanza dal vincitore
wij
+
-
+
i-j
distribuzione
a cappello
messicano
-
 E’ possibile un mappaggio topologico dallo spazio
degli ingressi a quello delle uscite
CK-7
y1
yM
+
...
+
-
x2
x1
y1
y2
x1 x2
CK-8
RETI DI KOHONEN
-Cappello messicano SENZA connessioni laterali
-Le relazioni di vicinato compaiono nel learning
-Output organizzato secondo una griglia
2 vicini
1- D
1
1
2-D
0
1
Input
2-D
0
1
Rete
1-D
ALGORITMO DI LEARNING
i*
wi*  x  wi  x
i,i * 
y1
vincitore
x 1 x2
wij  i, i *x j  wij 
1
CK-9
y2
xD
x wi - x
i  i*
f  ri  ri* 
…
wi
i  i*
wi • x
:
funzione di vicinato
Rete di Kohonen
Rete elastica
i, i *  e
 ri  ri*
2
2s
CK-10
2
wij  i, i * x j  wij 
 (n)
s (n)


n 

s n   s 0 1 

 N0 

 n    1  n 
0


 N0  K 
Vi(0)
Vi(t1)
Vi(t2)


n
s  

3
2


10

10

Scelta sperimentale del numero di neuroni
Conservazione della DENSITA’ dei dati di Input
CK-11
Esempi
CK-12
Applicazioni:




Controllo di motori
Riconoscimento del parlato
Ottimizzazione combinatoria
Quantizzazione vettoriale (LBG algorithm)
Kohonen è un algoritmo ottimale per la
quantizzazione vettoriale
LVQ Learning Vector Quantization
wi* j
  x j  wi* j 

  x j  wi* j 
classe corretta
classe sbagliata