LE RETI NEURALI:
MODELLI, ALGORITMI
E APPLICAZIONI
Giancarlo Mauri
Università di Milano - Bicocca
18/12/2015
1
1.1. Perché le reti neurali
LA POTENZA DEL CALCOLO ELETTRONICO…
 calcoli numerici complessi (anni per un uomo) in frazioni di secondo
 memorizzazione grandi quantità di dati
… E I SUOI LIMITI
 riconoscimento di persone, oggetti, suoni (anche in presenza di rumore)
 riconoscimento del parlato e comprensione del linguaggio naturale
 apprendimento, classificazione, generalizzazione
 visione e controllo del movimento
 adattamento a nuove situazioni
 soluzione di problemi complessi in modo esaustivo (ottimizzazione
combinatoria)
18/12/2015
2
1.1. Perché le reti neurali
 Perché il cervello risulta superiore al computer per certe
categorie di problemi?
 I meccanismi operanti nel cervello possono essere imitati
per produrre macchine più efficienti ?
18/12/2015
3
1.1. Perché le reti neurali
La differenza non sta nelle componenti:
Cellule nervose:
Circuiti logici elettronici:
tempo risposta ordine msec
tempo risposta ordine nsec
ma nella "architettura"
18/12/2015
4
1.1. Perché le reti neurali
IL CERVELLO COME CALCOLATORE
 L'elaborazione è frutto di un processo altamente parallelo
 La potenza di calcolo deriva dalla cooperazione di molti processori semplici e
fortemente interconnessi:
1010 - 1011 neuroni
105 connessioni/ neurone
 Le connessioni si modificano con l'apprendimento
 L'informazione non é localizzata, ma distribuita globalmente nella rete di
processori
 L'intelligenza deriva dalla interazione tra i neuroni, non é prerogativa di un
singolo neurone
 Ha una notevole tolleranza ai guasti
18/12/2015
5
1.2. Un po' di storia
INTERESSE PER IL NEURAL COMPUTING
1943
McCulloch
Pitts
Wiener
Craik
18/12/2015
1950
Wiener
Shannon
Von Neuman
Ashby
Hebb
Turing
1960
Rosenblatt
Minsky
Papert
1970
Arbib
Kohonen
1984
PdP Group
Hopfield
…………
6
1.2. Un po' di storia
I PIONIERI (Anni '40)
1943 : McCulloch e Pitts
"A Logical calculus of Ideas Immanent in Nervous Activity"
Primo modello formale di funzionamento di una rete nervosa, descritta come un circuito i
cui componenti sono porte logiche costruite a partire dalle funzioni booleane elementari:
OR, AND, NOT.
1949 : Wiener
introduce la visione del sistema nervoso come un sistema per l'elaborazione delle
informazioni
1949 : D.O. Hebb
"The organization of behavior"
ipotizza che alla base del meccanismo di apprendimento vi sia una modifica
dell'efficacia sinaptica tra coppie di neuroni, atraverso il rafforzamento di
connessioni spesso attive.
La regola di apprendimento di Hebb è ancora alla base di molti modelli
18/12/2015
7
1.2. Un po' di storia
LA PRIMA ETA’ DELL’ORO ('50–'60)
Fine anni '40: von Neumann sviluppa la teoria degli automi
"ramo seriale" che darà origine alle architetture "alla von Neumann"
"ramo parallelo" che produrrà gli automi cellulari e le reti neuronali
1960: B. Widrow, M. Hoff
"Adaptive switching circuits"
Uno dei primi neurocomputer, con regola di apprendimento di Widrow–Hoff, capace
di riconoscere semplici pattern.
La differenza tra l'uscita del circuito e l'uscita desiderata modifica per
controreazione le resistenze nel circuito per ottenere uscite più corrette.
1962: F. Rosenblatt
"The principles of neurodynamics"
Primo modello di neurone formale in grado di apprendere da esempi (percettrone).
Esperimenti su computer.
18/12/2015
8
1.2. Un po' di storia
GLI ANNI DELLA CRISI ('70)
1969: M. Minsky, S. Papert
"Perceptrons: an introduction to computational geometry"
Analisi approfondita dei percettroni.
Dimostrazione della inadeguatezza a risolvere molti problemi.
Il campo delle reti neurali fu abbandonato
(anche per l'indisponibilità di tecnologie adeguate)
salvo poche eccezioni
(Stephen Grossberg, Teuvo Kohonen, James Anderson, Gail Carpenter)
Sviluppo di
calcolatori basati sulla architettura sequenziale di von Neuman
Intelligenza artificiale
18/12/2015
9
1.2. Un po' di storia
GLI ANNI DELLA RIPRESA ('80–'90)

Riesame della critica di Minsky e Papert, che risulta valida solo per reti molto semplici

Introduzione dell'algoritmo di back propagation
John Hopfield
Analogie stimolanti con altri sistemi fisici
D. Rumelhart, J. McClelland, G. Hinton, T. Sejnowski
Descrizione dell'apprendimento delle reti in termini di meccanica statistica: Macchina
di Boltzmann

Sviluppo di algoritmi ed architetture ad alto parallelismo

Sviluppo di nuove tecnologie: VLSI, Circuiti ottici
18/12/2015
10
1.3. Campi applicativi
 Elaborazione di segnali
 Controllo
 Riconoscimento di schemi grafici
 Elaborazione di immagini
 Medicina
 Riconoscimento e produzione del parlato
 Finanza
18/12/2015
11
1.4. Connessionismo e intelligenza artificiale
Intelligenza
artificiale
Connessionismo

Mente ≠ cervello

Mente  cervello

Deduzione

Induzione

Simbolico

Analogico / subsimbolico

Sequenziale

Parallelo

Programmazione

Apprendimento

Istruzioni imperative

Adattività

Indirizzi espliciti

Memoria associativa

No generalizzazione

Generalizzazione
18/12/2015
12
2.1. Il neurone biologico
Stati possibili:
eccitazione
invia segnali ai neuroni connessi attraverso le sinapsi
inibizione
non invia segnali
Transizione di stato:
dipende dall'entità complessiva dei segnali eccitatori e inibitori ricevuti
18/12/2015
13
2.2. Neuroni formali
GLI ELEMENTI ESSENZIALI:
 Stato
 Funzione di transizione
 Funzione di uscita
 Modalità di transizione
UN ESEMPIO:
il neurone binario a soglia (McCulloch, Pitts 1943)
<n, C, W, >
nome
18/12/2015
canali
input
vettore
pesi
soglia
14
2.2. Neuroni formali
• Stati:
{0,1}
• Funzione di transizione:
s(t+1) = 1
• Funzione di uscita:
coincide con lo stato
• Modalità di transizione:
deterministica
c1
c2
cn
18/12/2015
o
{-1,1}
sse
wisi(t) ≥ 
w1
w2

wn
15
2.2. Neuroni formali
Funzioni di trasferimento
A gradino
f(x) = 1 se x > 
0 altrimenti
Output
Input
Lineare
Output
Input
18/12/2015
16
2.2. Neuroni formali
Mista
Output
Input
Sigmoide
f(x) =
1 –1
1+e–x
Output
Input
18/12/2015
17
2.3. Reti neurali artificiali
w21
1
2
3
5
4
f(x) 
18/12/2015
1
1

x
1 e
18
2.3. Reti neurali artificiali
CARATTERISTICHE STRUTTURALI:
Grande numero di unità
Operazioni elementari
Alto livello di interconnessione



CARATTERISTICHE DINAMICHE :
Cambiamento di stato in funzione dello stato dei neuroni collegati
(input)

Funzione di uscita per ogni unità

Modifica delle schema di connessione per apprendimento

FORMALMENTE:
| w ij |
matrice dei pesi
| i |
vettore delle soglie
n
n i (t)   w ij  x j (t)   i
input netto a i in t
x i (t  1)  g(n i (t))
funzione di trasferimento
j1
18/12/2015
19
2.3. Reti neurali artificiali
ELEMENTI CARATTERIZZANTI:
 tipo di unità
 topologia (direzione delle connessioni, numero di strati …)
 modalità di attivazione:

seriale ciclica

seriale probabilistica

parallela

mista
 modalità di addestramento
18/12/2015
20
2.3. Reti neurali artificiali
CLASSI PRINCIPALI:
 Percettrone (Rosenblatt)
 Adaline(Widrow e Hoff)
 Mappe di caratteristiche autoorganizzanti (Kohonen)
 Reti di Hopfield
 Reti basate sulla teoria della risonanza adattiva (Carpenter)
 Percettrone a più strati (Rumelhart e Williams)
 Macchina di Boltzmann (Hinton)
 Memoria associativa bidirezionale (Kosko)
 Rete a contropropagazione (Hecht–Nielsen)
18/12/2015
21
3.1. Il percettrone
Compito: riconoscimento di forme
I percettroni sono reti semplificate, progettate per permettere lo studio di relazioni tra
l'organizzazione di una rete nervosa, l'organizzazione del suo ambiente e le prestazioni "psicologiche"
di cui è capace.
I percettroni potrebbero realmente corrispondere a parti di reti e sistemi biologici più estesi;
in questo caso, i risultati ottenuti sarebbero direttamente applicabili. Più verosimilmente, essi
rappresentano una semplificazione estrema del sistema nervoso centrale, in cui alcune proprietà
sono esagerate ed altre soppresse. In questo caso, perturbazioni e raffinamenti successivi del sistema
possono dare una approssimazione migliore.
Rosenblatt, 1962
18/12/2015
22
3.1. Il percettrone

Struttura:
t
SOGLIA
S
NODO DI OUTPUT
w
k
w
1
wn
••••
••••
x
1
PESI
x
k
NODI DI INPUT
x
n
 Regola di transizione:
n
se
 wk xk  t  0
k 1
allora S = 1
altrimenti S = 0
18/12/2015
23
3.2. Apprendimento nel percettrone

I pesi vengono fissati a caso e poi modificati

L'apprendimento è guidato da un insegnante

La procedura
 Obiettivo è classificare vettori di input in due classi, A e B.
 Si sottomette una sequenza infinita {xk} di vettori tale che ve ne siano un numero
infinito sia di A che di B
 Per ogni xk la rete calcola la risposta
 Se la risposta è errata, si modificano i pesi, incrementando i pesi delle unità di input
attive se si è risposto 0 anzichè 1, decrementandole nel caso duale:
w' = w ± x
18/12/2015
24
3.2. Apprendimento nel percettrone

Teorema di convergenza:
Comunque si scelgano i pesi iniziali, se le classi A e B sono discriminabili, la procedura di
apprendimento termina dopo un numero finito di passi.

Teorema di Minsky e Papert:
La classe delle forme discriminabili da un percettrone semplice
linearmente separabili.
18/12/2015
è limitata alle forme
25
3.3. Il teorema di convergenza del percettrone
Input
Input esteso
Pesi
x = (x1, …, xd)
x = (x1, …,xd, 1)
w = (w1, …,wd, -)
Teorema
Se l'insieme degli input estesi è partito in due classi linearmente
separabili A, B allora é possibile trovare un vettore di pesi w tale che:
18/12/2015
wy ≥ 0
se yA
wy < 0
se yB
26
3.3. Il teorema di convergenza del percettrone
Costruzione
1. Si parte con w arbitrario
2. Si classifica un input y:
risposta corretta: w' := w
risposta errata: w' := w+y se yA
w' := w–y se yB
3. Si prova un nuovo input
18/12/2015
27
3.3. Il teorema di convergenza del percettrone
Correttezza
Sia yA e wy < 0
Poiché yy ≥ 0 vale w'y = (w+y)y = wy + yy > wy
Quindi w' classifica y in modo "più corretto" rispetto a w.
Ma altri input possono essere classificati "meno correttamente".
18/12/2015
28
3.3. Il teorema di convergenza del percettrone
Convergenza
Si consideri A'  A  B'

B'  - y | y  B
Cerchiamo
v tale che v  y ≥ 0
yA'
{yi}iN
sequenza di addestramento
 yiA’
 yB'

{wi}iN
occorre infinite volte
sequenza dei pesi
 w0 = 0

wk+1= wk
scelta arbitraria
se wk  yk ≥ 0
wk + yk altrimenti
18/12/2015
29
3.3. Il teorema di convergenza del percettrone
 {vi}iN
sequenza dei pesi modificati
{ti}iN
sottosequenza di training corrispondente
w0 ≠ w1 = w2 = w3 ≠ w4 = w5 = w6 ≠ w7 ≠ w8 ……..

v0
v1
v2
v3
t0
t1
t2
t3
j
vj tj < 0
vj+1 = vj + tj = vj-1 + tj-1 + tj = …… =

TESI: la sequenza
18/12/2015
{vi} è finita
30
Il teorema di convergenza del percettrone

DIMOSTRAZIONE

Sia w una qualsiasi soluzione
 y  A'
y•w≥0

Si ponga  = min (y • w | y  A')
 j 
 vj+1 • w =   t k 
•w≥j•
k 1 


18/12/2015
(vj+1 • w)2 ≤ | vj+1|2 • |w|2
| vj+1|2 ≥
(esiste per ipotesi)!
j2   2
|w|
2
( )
() + ( )
(Cauchy-Schwarz)
(  )
31
Il teorema di convergenza del percettrone
 Si ponga


M = max {|y|2 | y  A'}
|vj+1|2 = |vj +tj|2 = | vj|2 + 2 vj • tj + |tj|2 ≤ | vj|2 + |tj|2
|2
|vj+1 ≤
j

| tj|2 ≤ j • M
(vj • tj < 0)
()
k 1
j2  2 ≤ | v |2 ≤ j M = g(j)
j+1
f(j) =
2
|w|
(  ) + ()
lineare in j
quadratico in j
18/12/2015
32
Il teorema di convergenza del percettrone
f
g
j
j
M | W |2

2

Dopo al massimo  modificazioni di peso, il percettrone classifica correttamente ogni input.
18/12/2015
33
Il teorema di convergenza del percettrone
Ma:
•  dipende dalla soluzione W
•  non è il reale numero di stadi
LIMITAZIONI DEL PRECETTRONE
Minsky – Papert theory
18/12/2015
34
Un esempio
OR ESCLUSIVO (addizione binaria):
I punti a valore 1 non sono linearmente separabili da quelli a valore 0
01 = 1
00 = 0
Ipotesi: Esiste un neurone binario a soglia
x
y
11 = 0
10 = 1

xy
        
tale che xy = 1 se e solo se x + y ≥.
Essendo  simmetrica, vale anche xy = 1 sse y + x ≥.
Sommando e dividendo per 2 si ottiene:
xy = 1 sse tx + ty = t(x+y)≥
ove t = (+ )/2. Posto ora x+y = s, abbiamo:
xy = 1 sse ts –≥ 0.
Dallo studio del polinomio di primo grado in s y = ts – si ottiene:
Per s = 0, ts – < 0
(00 = 0)
Per s = 1, ts – ≥ 0
(01 = 1 = 10)
Per s = 2, ts – < 0
(11 =0)
Questa é una contraddizione, poiché una retta non può salire e poi scendere
18/12/2015
35
Il percettrone generalizzato

Strati intermedi tra input e output

Connessioni da strati di livello basso a strati di livello alto; nessuna
connessione all'interno di uno stesso strato

Stato di un neurone: x

Funzione di attivazione: x k  P(
sigmoidale.

w
jk x j )
con P(x) funzione
j
Per ogni configurazione x del primo strato (ingresso), la rete calcola una
configurazione y dell'ultimo strato (uscita)
18/12/2015
36
Il percettrone generalizzato

Obiettivo è che, fissata una mappa f tra configurazioni di ingresso e di
uscita, sulla base di una sequenza di stimoli (xk), la rete cambi i pesi delle
connessioni in modo che, dopo un numero finito s di passi di apprendimento,
l'uscita (yk) coincida con f(xk) per ogni k>s, almeno approssimativamente.

Criterio di modifica: minimizzare un "criterio di discrepanza" tra risposta
della rete e risposta desiderata

Teorema (Irie-Miyake, 1988): Un solo strato nascosto è sufficiente per
permettere di calcolare qualsiasi funzione da un insieme finito a {0,1}
18/12/2015
37
Reti multistrato
Pattern di input
Strato 1
Input
Strato 2
Nascosto
Strato L-1
Nascosto
Strato L
Output
18/12/2015
Pattern di output
38
Reti multistrato
REGOLA DELTA E CALO GRADIENTE
●
Strategie di apprendimento:
ridurre una funzione appropriata della differenza tra il reale output y
sull'input x e l'output desiderato t
1
   i t i  y i 2
2
●
Tecnica di riduzione:
calo gradiente (versus pesi di connessione)
E
w
18/12/2015
39
Un esempio
.5
+1
+1
–2
1.5
+1
+1
Una rete per l'or esclusivo con una unità nascosta
18/12/2015
40
Retropropagazione dell'errore
L'algoritmo (senza unità nascoste)
x
w
yj = • wij xi
h
y
Žyj
Žiw ijxj
ŽE ŽE Žyj
=

= –(tj–yj)
= –j
= –jxi
Žw ij Žyj Žw ij
Žw ij
Žw ij
I pesi sono modificati proporzionalmente a questa derivata (regola delta):
w ij = jxi
La convergenza a un minimo globale é garantita per funzioni di attivazione lineari senza
unità nascoste e per dati consistenti
18/12/2015
41
Retropropagazione dell'errore
Assunzioni

Neuroni u1, u2, …, un:
•
unità di input
•
unità nascoste
•
unità di output

Pesi reali wij

Stati di attivazione sj

Input netto

Funzione di attivazione
nj 
w s
ij i
i
semilineare differenziabile non decrescente:
sj(t+1) = fj(nj(t))
Es. : Funzione logistica
sj 
18/12/2015
1
1  e ni
42
Retropropagazione dell'errore
 Sia x input, y output atteso, t output effettivo.
 Consideriamo la norma quadratica

1
2
 (t
j
 y j )2
j
 Cerchiamo una regola di modifica dei pesi tale che:
w ij = – 
ŽE
Žw ij
con tasso di apprendimento. Poiché:
ŽE ŽE Žnj
ŽE
=

=
 s j = (def) –j s j
Žwij Žnj Žwij
Žnj
dobbiamo determinare
j = –
18/12/2015
ŽE
Žnj
43
Retropropagazione dell'errore
 Passo 1 – Input
Il neurone di input j é posto nello stato xj
 Passo 2 – Propagazione
Per ogni neurone interno o di output j si calcola lo stato
sj = fj(nj)
 Passo 3 – Confronto
Per ogni neurone di output j, noto l'output atteso, si calcola:
j = f 'j(nj)(tj – y j)
 Passo 4 – Retropropagazione dell'errore
Per ogni neurone nascosto j, si calcola:
j = f 'j(nj)(• wjh h)
h
 Passo 5 – Aggiornamento dei pesi
wij := w ij +  isj
18/12/2015
44
Retropropagazione dell'errore
Limiti
 mancanza di teoremi generali di convergenza
 può portare in minimi locali di E
 difficoltà per la scelta dei parametri
 scarsa capacità di generalizzazione, anche nel caso di buona minimizzazione di E
Possibili modifiche migliorative
 Tasso di apprendimento adattivo:  = g(gradiente di E)
 Termine di momento wij (t+1) = i sj + wij (t)
 Range degli stati da –1 a 1
 Deviazioni dalla discesa più ripida
 Variazioni nell'architettura (numero di strati nascosti)
 Inserimento di connessioni all'indietro
18/12/2015
45
Retropropagazione dell'errore
Il tasso di apprendimento

grande, rischio di comportamento oscillatorio

piccolo, apprendimento lento
Strategie di identificazione della architettura ottimale

Rete grande apprende facilmente, ma generalizza male


Rete piccola apprende con difficoltà, ma generalizza bene


A partire da una rete grande tolgo neuroni nascosti, se valuto che può continuare
ad apprendere anche con meno neuroni
A partire da una rete piccola aggiungo neuroni nascosti, se la discesa della
funzione E é troppo lenta o bloccata
A partire da una ipotesi iniziale di rete, aumento o diminuisco i nodi nascosti, secondo
criteri misti
18/12/2015
46
Retropropagazione dell'errore
Inserimento di connessioni all'indietro
in presenza di connessioni con ritardo q l'input netto é:

n j t  
Q
  w  s t  q
q
ij
j
j
q 1
la funzione E é calcolata pesando l'errore nel tempo:

T
E = 1 • • jt (sj – tj 2
2 j t=1
nel calcolo delle derivate occorre aggiungere variabili ausiliarie

Il ruolo dell'integrazione

la rete può integrarsi con moduli tradizionali, sfruttando tutte le informazioni
simboliche e le sinergie che vi possono essere
18/12/2015
47
Come lavorare con la retropropagazione
B.P. al lavoro
Come evitare i minimi locali?
Quanto è lungo il tempo di apprendimento?
Come scegliere ?
Nessuna risposta teoretica, solo risultati di simulazione
18/12/2015
48
Come lavorare con la retropropagazione
Esempio: Funzione Logistica
oj 
o j
n j

1
1 e
e
nj 
n j
ij i
 j
i
n j
(1  e
w o
n j 2

)
1
1 e
n j

1
  1 
n
1 e j


  o j (1  o j )


δ j  (t j  o j )  o j  (1  o j )
δ j  o j (1  o j ) 
δ w
k
jk
unità output
unità nascosta
k
Il ruolo dell'integrazione
18/12/2015

Troppo grande: oscillazione

Troppo piccolo: apprendimento lento
49
Il problema XOR
Soluzione 1
y
6.3
-4.2
-4.2
-9.4
x3
2.2
x1
18/12/2015
-6.4
-6.4
x2
50
Il problema XOR
Logistic function
 = 0.5
558 cicli
Output
≤ 0.1 per 0
≥ 0.9 per 1
x1  x 2  1
x3 
x1  x 2  0
x3 
x1  1
x3 
18/12/2015
x2  0
1
1 e
10.6
1
1  e  2.2
1
1  e 4.2
~0
y
~1
y
~0
y
1
1 e
2.1
1
1 e
3.1
1
1 e
 2.1
~0
~0
~1
51
Il problema XOR
Soluzione 2
-.8
5.3
-4.5
2.0
-.1
-2.0
8.8
4.3
9.2
Minimo locale!!!!
Output 0.5 per input 11 e 01
6.587 presentazioni, =0.25
18/12/2015
52
Il problema XOR
APPRENDIMENTO NEL PRECETTRONE GEN.
0
1
1
1
1
1
0
1
1
1
INPUT
1
1
0
1
1
1
1
1
0
1
1

1

1 0
1

0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0

0

0 1
0

1
OUTPUT INIZ.
OUTPUT DOPO 250 CICLI
(1 CICLO)
( = .1)
0 1 1 1 1
.50
.96
1 0 1 1 1
.48
.97
1 1 0 1 1
.46
.97
1 1 1 0 1
.48
.97
1 1 1 1 0
.46
.97
1 0 0 0 0
.51
.02
0 1 0 0 0
0 0 1 0 0
.39
.48
.03
.03
0 0 0 1 0
.47
.02
0 0 0 0 1
.46
.02
18/12/2015
53
Il problema XOR
-.4
-.9
-1.4
-.8
-2.9
-6.9
-1.4
-.7
0
1
1
0
1
1
1
0
0
1
-.4
0
0
1
1
0
-2.4
0
1
0
0
1
-1.7
-1.8
0
-1.4
-3.3
-2.0
-1.6
-2.2
-.8
-1.1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
1
0
1
-2.3
-1.5
-.1
0
0
0
1
1
-1.2
0
1
1
0
0
Difficoltà di classificazione
18/12/2015
54
Il problema XOR
N.B.
Non c'è una soluzione corretta a cui convergere, perché
la soluzione cambia al variare dell'ambiente!
Necessità di feedback dall'ambiente, per un
adattamento continuo.
18/12/2015
55
Le reti di Hopfield
 n neuroni binari a soglia
ui
 connessione completa con pesi simmetrici
Tij
 evoluzione della rete verso uno stato stabile, a partireda uno stato iniziale assegnato
 aggiornamento sequenziale casuale con equidistribuzione di probabilità
Teorema: La rete converge a uno stato stabile, che é minimo globale o locale della funzione
energia:
E = –1 • • Tijui uj
2 j i °j
Dimostrazione:
E decresce o resta invariata ad ogni aggiornamento. Se si aggiorna ui a u'i si ha la
variazione di energia:
E = E' – E = –1 ui • Tijuj
2
i °j
Se
ui =0 e u'i =1 allora ui =1 e
Se
ui =1 e u'i =0 allora ui =–1 e
18/12/2015
• Ti juj•0, e quindi Ei Š0
j
• Ti juj<0, e quindi Ei <0
j
56
Le reti di Hopfield
In altre parole, si cambia stato solo se ciò comporta una diminuzione di energia.
Stati stabili sono gli stati di minima energia, in cui E non é abbassata da modifiche di nessuna
delle variabili ui
B
A
COMPUTAZIONE:
C
Stati di minimo
 Si bloccano i valori di alcune unità (input)
 Si lascia evolvere la rete fino all'equilibrio
 Si leggono e interpretano i valori di alcune unità (output)
18/12/2015
Il meccanismo probabilistico e l'esistenza di più minimi locali
possono portare a risultati diversi in
57
Macchina di Boltzmann

Rete di neuroni binari che usa la tecnica dell'annealing simulato per modificare le connessioni interne

Funzione obiettivo (bilineare):
V=
n
n
i,j=1
i=1
• si wij sj + •i si

Matrice di connessione simmetrica

No auto connessioni

Aggiornamento neuroni casuale
=
n
•si ni
(si  {0,1})
i=1
1
1casuale governata
 Funzione di attivazione sigmoidale
dallaa seguente
probabilità di transizione da s a s'
se s contiguo
s'
N 1+e-(V(s) -V(s'))
ps,s' =
1-
•
ps,s"
se s = s'
s" contiguo a s
0
altrimenti
ove s é contiguo a s' sse la loro distanza di Hamming é 1
18/12/2015
58
Macchina di Boltzmann

processo stocastico che, all'equilibrio, concentra la probabilità nella regione critica M per V, in base
alla legge di distribuzione
p(s) = e-V(s)
Z
ove Z é una costante di normalizzazione
Procedure: MACCHINA DI BOLTZMANN
External function: stopping_rule
BEGIN
prendi una configurazione iniziale s  {0,1}
REPEAT
calcola V = V(s)
prendi uniformemente un i in {1,2,...,n}
(scelta di un vettore
prossimo)
calcola V' = V(s)
IF exp(–b(V–V')) > random [0,1) THEN flip si
UNTIL stopping_rule é verificata
END
18/12/2015
59
Apprendimento nelle B.M.
Si impara una buona approssimazione della distribuzione di probabilità
condizionale sull'insieme di coppie (input, output)
1.
Fase positiva
 Blocco unità di input e di output
 Evoluzione verso l'equilibrio termico
 Incremento del peso tra unità contemporaneamente attive
2.
(Hebb)
Fase negativa
 Blocco unità di input
 Evoluzione verso l'equilibrio termico
 Decremento del peso tra unità contemporaneamente attive
Elimina il rischio di saturazione dei pesi sinaptici
18/12/2015
60
Reti neurali e apprendimento
Il "programma" di una rete neurale è rappresentato dai pesi
sinaptici
 E' impossibile "programmare" direttamente reti complesse per
svolgere un certo compito
D.O. Hebb, 1949:
Apprendimento = modifica pesi sinaptici
Se due neuroni connessi sono per più volte di seguito
contemporaneamente attivi, il peso della sinapsi aumenta
La regola di Hebb è una regola non formalizzata. Inoltre i pesi
vengono solo aumentati
Una possibile formalizzazione (Sutton, 1981)
wi(t+1) = wi(t) + xi(t)y(t)
18/12/2015
61
Reti neurali e apprendimento
Apprendimento:
capacità della rete ad autoorganizzarsi in una topologia che esibisce
le caratteristiche desiderate
(cambiamento nel comportamento che deriva dall'attività, dall'addestramento o
dall'osservazione)
Principali metodi di apprendimento:
1. Apprendimento con supervisione
noti ingresso e uscita corrispondente
i pesi sono modificati per produrre l'uscita migliore
2. Apprendimento rinforzato
non è data l'uscita corretta
viene detto se l'uscita prodotta é buona o cattiva
3. Apprendimento senza supervisione
La rete sviluppa le proprie regole di classificazione mediante l'estrazione di
informazioni dagli esempi ricevuti
18/12/2015
62
Apprendimento da esempi
Input: una sequenza di coppie (argomento, valore) da una funzione f
Output: un programma (o una rete neurale) che computa la funzione
Approcci
 Apprendimento induttivo (Solomonov, Goodman, Blum) [Risultati
asintotici]
 Apprendimento computazionale (Valiant, Blumer, Natarajan) [ Risultati
probabilistici]
 Apprendimento con reti neurali (Hinton, Kohonen, Seinowskj)
18/12/2015
63
Apprendere come ?
Il compito
 Data una funzione (ignota) f: X Y
 Estrarre un campione {(x1,f(x1)), … ,(xn,f(xn))} e sottoporlo a una rete neurale
 Cercare la rete neurale che simula f
La strategia di apprendimento
Minimizzare una opportuna funzione della differenza E tra il comportamento effettivo
della rete e quello che si accorderebbe col campione
Le tecniche di minimizzazione
Discesa lungo il gradiente (rispetto ai pesi)
La valutazione dell'apprendimento
Per generalizzazione della funzione appresa a nuovi esempi mai visti dalla rete
18/12/2015
64
Apprendere come ?
generatore dei
parametri iniziali
della rete
W
+
W
W'
generatore di
esempi
x
RETE
NEURALE
y
modulo di
calcolo del
gradiente
z
modulo di
confronto
18/12/2015
65
Alcune applicazioni
Filtri adattivi per telecomunicazioni
1959
B. Widrow
ADALINE
Valutazione rischi per mutui e prestiti
Nestor
Mortgage Risk Evaluator
Training su qualche migliaio di casi
Individua pattern di dati associati a forte rischio
Può essere configurato come prudente o ottimista
Confronto con esperto umano promettente
Individuazione di esplosivi
SAIC
SNOOPE
Riconosce il pattern di emissioni gamma di esplosivi
Reagisce a poco più di un kg di esplosivo
Installato al JFK di NY – Costo: 1.1 M$
Prevista l'installazione in altri grandi aeroporti
18/12/2015
66
Alcune applicazioni
Monitoraggio di processo
GTE
Produzione lampadine
Confronta dati da sensori con gli standard
(variaz. di temperatura, pressione, sostanze chimiche)
Determina condizioni di produzione ottimali
Vantaggi su tecniche statistiche (regressione lineare):
raccolta dati incrementale, meno memoria
Riconoscimento parlato
Intel
Accuratezza 99% su un centinaio di parole da un solo speaker
Usato per registrare relazioni di ispettori
Individuazione prodotti difettosi
Siemens
Impianti condizionamento per auto rumorosi
Accuratezza 90%
18/12/2015
67
Prototipi e ricerca
Classificazione segnali sonar
Bendix Aerospace
Distingue mine da rocce o altri oggetti sul fondo marino
Accuratezza 99.8% su dati training, 90% su nuovi dati
Riconoscimento sequenze DNA
Riconoscimento scrittura manuale (indirizzi)
Ottimizzazione prenotazioni e tariffe aeree
Lettura assegni
Analisi dati clinici (ECG, EEG)
18/12/2015
68
Prototipi e ricerca
Movimento di un braccio flessibile
m
r
w(r,t)
t
18/12/2015
69
Prototipi e ricerca
Controllo degli angoli di un satellite geostazionario
18/12/2015
70