1 09/09/2014 LE RETI NEURALI: MODELLI, ALGORITMI E APPLICAZIONI Giancarlo Mauri Università di...

111/04/23

LE RETI NEURALI:LE RETI NEURALI:

MODELLI, ALGORITMIMODELLI, ALGORITMI

E APPLICAZIONIE APPLICAZIONI

Giancarlo Mauri

Università di Milano - Bicocca

211/04/23

1.1. Perché le 1.1. Perché le reti neuralireti neurali

… 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)

… 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)

LA POTENZA DEL CALCOLO ELETTRONICO…

calcoli numerici complessi (anni per un uomo) in frazioni di secondo

memorizzazione grandi quantità di dati

LA POTENZA DEL CALCOLO ELETTRONICO…

calcoli numerici complessi (anni per un uomo) in frazioni di secondo

memorizzazione grandi quantità di dati

311/04/23


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 ?

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 ?

411/04/23


La differenza non sta nelle componenti:

Cellule nervose: tempo risposta ordine msec

Circuiti logici elettronici: tempo risposta ordine nsec

ma nella "architettura"

511/04/23


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

611/04/23

1.2. Un po' di 1.2. Un po' di storiastoria

1943 1950 1960 1970 1984McCullochPittsWienerCraik

WienerShannonVon NeumanAshbyHebbTuring

RosenblattMinskyPapert

ArbibKohonen

PdP GroupHopfield…………

INTERESSE PER IL NEURAL COMPUTING

711/04/23


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.

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.

I PIONIERI (Anni '40)

1949 : Wiener

introduce la visione del sistema nervoso come un sistema per l'elaborazione delle informazioni

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

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

811/04/23


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

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

LA PRIMA ETA’ DELL’ORO ('50–'60)

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.

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.

1962: F. Rosenblatt

"The principles of neurodynamics"

Primo modello di neurone formale in grado di apprendere da esempi (percettrone).

Esperimenti su computer.

911/04/23


GLI ANNI DELLA CRISI ('70)

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)

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

Sviluppo di

calcolatori basati sulla architettura sequenziale di von Neuman

Intelligenza artificiale

1969: M. Minsky, S. Papert

"Perceptrons: an introduction to computational geometry"

Analisi approfondita dei percettroni.

Dimostrazione della inadeguatezza a risolvere molti problemi.

1969: M. Minsky, S. Papert

"Perceptrons: an introduction to computational geometry"

Analisi approfondita dei percettroni.

Dimostrazione della inadeguatezza a risolvere molti problemi.

1011/04/23


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

Riesame della critica di Minsky e Papert, che risulta valida solo per reti molto semplici

Introduzione dell'algoritmo di back propagation

D. Rumelhart, J. McClelland, G. Hinton, T. Sejnowski

Descrizione dell'apprendimento delle reti in termini di meccanica statistica: Macchina di Boltzmann

D. Rumelhart, J. McClelland, G. Hinton, T. Sejnowski

Descrizione dell'apprendimento delle reti in termini di meccanica statistica: Macchina di Boltzmann

John Hopfield

Analogie stimolanti con altri sistemi fisici

John Hopfield

Analogie stimolanti con altri sistemi fisici

Sviluppo di algoritmi ed architetture ad alto parallelismo

Sviluppo di nuove tecnologie: VLSI, Circuiti ottici

Sviluppo di algoritmi ed architetture ad alto parallelismo

Sviluppo di nuove tecnologie: VLSI, Circuiti ottici

1111/04/23

1.3. Campi 1.3. Campi applicativiapplicativi

Elaborazione di segnali

Controllo

Riconoscimento di schemi grafici

Elaborazione di immagini

Medicina

Riconoscimento e produzione del parlato

Finanza

1211/04/23

1.4. Connessionismo e 1.4. Connessionismo e intelligenza artificialeintelligenza artificiale

Intelligenzaartificiale

Intelligenzaartificiale

ConnessionismoConnessionismo

Mente ≠ cervello

Deduzione

Simbolico

Sequenziale

Programmazione

Istruzioni imperative

Indirizzi espliciti

No generalizzazione

Mente cervello

Induzione

Analogico / subsimbolico

Parallelo

Apprendimento

Adattività

Memoria associativa

Generalizzazione

1311/04/23

2.1. Il neurone 2.1. Il neurone biologicobiologico

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

1411/04/23

2.2. Neuroni 2.2. Neuroni formaliformali

GLI ELEMENTI ESSENZIALI:

Stato

Funzione di transizione

Funzione di uscita

Modalità di transizione

UN ESEMPIO: il neurone binario a soglianeurone binario a soglia (McCulloch, Pitts 1943)

<n, C, W, >

nome canali vettore soglia input pesi

1511/04/23


• Stati: {0,1} o {-1,1}

• Funzione di transizione: s(t+1) = 1 sse wisi(t)

≥ • Funzione di uscita: coincide con lo stato

• Modalità di transizione: deterministica

wn

w2

w1

cn

c2

c1

1611/04/23


A gradino

Output

Input

Output

Input

Lineare

f(x) = 1 se x > 0 altrimenti

Funzioni di trasferimentoFunzioni di trasferimento

1711/04/23


f(x) = 11+e–x

– 1

Output

Input

Mista

Output

Input

Sigmoide

1811/04/23

2.3. Reti neurali 2.3. Reti neurali artificialiartificiali

f(x) =1

1+ −xe−1

4

3

1 2

5

21w

1911/04/23


ni (t)= wij ⋅xj(t)−ϑ ij=1

n∑

|w| ij

|ϑ i |

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:

xi (t+1)=g(ni(t))

matrice dei pesi

vettore delle soglie

input netto a i in t

funzione di trasferimento

2011/04/23


ELEMENTI CARATTERIZZANTI:

tipo di unità

topologia (direzione delle connessioni, numero di strati …)

modalità di attivazione:

seriale ciclica

seriale probabilistica

parallela

mista

modalità di addestramento

2111/04/23


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)

2211/04/23

3.1. Il 3.1. Il percettronepercettroneCompito: 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

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

2311/04/23

3.1. Il 3.1. Il percettronepercettrone

Regola di transizione:

se

Struttura:

w1

nx

S

NODI DI INPUT

NODO DI OUTPUT

PESI

SOGLIA

wk wn

kx1

x

• • • •• • • •

01

≥−=

kk

n

kxw allora S = 1

altrimenti S = 0

2411/04/23

3.2. 3.2. Apprendimento nel Apprendimento nel percettronepercettrone

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

2511/04/23

3.2. 3.2. Apprendimento nel Apprendimento nel percettronepercettrone

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 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 è limitata alle forme linearmente separabili.

Teorema di Minsky e Papert:

La classe delle forme discriminabili da un percettrone semplice è limitata alle forme linearmente separabili.

2611/04/23

3.3. 3.3. Il teorema di convergenza Il teorema di convergenza del del percettronepercettrone

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:

wy ≥ 0 se yA

wy < 0 se yB

Input x = (x1, …, xd)Input esteso x = (x1, …,xd, 1)Pesi w = (w1, …,wd, -)

2711/04/23


Costruzione

1. Si parte con w arbitrario

2. Si classifica un input y:

risposta corretta: w' := w

risposta errata: w' := w+y se yA

w' := w–y se yB

3. Si prova un nuovo input

2811/04/23


Correttezza

Sia yA e wy < 0

Poiché yy ≥ 0 vale w'y = (w+y)y = wy + yy > wy

Quindi w' classifica y in modo "più corretto"

rispetto a w.

Ma altri input possono essere classificati "meno

correttamente".

2911/04/23


Convergenza

Si consideri

{ }By|y-B' B'AA' ∈== U

Cerchiamo v tale che v y ≥ 0 yA'

{yi}iN sequenza di addestramento

yiA’ yB' occorre infinite volte{wi}iN sequenza dei pesi

w0 = 0 scelta

arbitraria

wk+1= wk se wk yk ≥ 0

wk + yk altrimenti

3011/04/23


{vi}iN sequenza dei pesi modificati

{ti}iN sottosequenza di training corrispondente

w0 ≠ w1 = w2 = w3 ≠ w4 = w5 = w6 ≠ w7 ≠ w8 ……..

v0 v1

v2 v3

t0 t1

t2 t3 vj tj < 0 j

vj+1 = vj + tj = vj-1 + tj-1 + tj = …… =

TESI: la sequenza {vi} è finita

3111/04/23

Il teorema di convergenza del Il teorema di convergenza del percettronepercettrone

DIMOSTRAZIONE

Sia w una qualsiasi soluzione (esiste per ipotesi)!

y • w ≥ 0 y A'

Si ponga = min (y • w | y A')( )

vj+1 • w = • w ≥ j • () + ( )

(vj+1 • w)2 ≤ | vj+1|2 • |w|2 (Cauchy-Schwarz)

| vj+1|2 ≥ ( )

ktk=1

j∑

⎛

⎝ ⎜

⎞

⎠ ⎟

2

22

|w|

j ⋅

3211/04/23


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 (vj • tj < 0)

|vj+1|2 ≤ | tj|2 ≤ j • M ()

∑=

j

1k

j2α2

|w|2≤ | vj+1|2 ≤ j M = g(j) ( ) + ()

f(j) =

quadratico in j

lineare in j

3311/04/23


fg

j

β

=•

≤2

2|W|Mj

Dopo al massimo β modificazioni di peso, il percettrone classifica correttamente ogni input.

3411/04/23


Ma:

• β dipende dalla soluzione W

• β non è il reale numero di stadi

LIMITAZIONI DEL PRECETTRONE

Minsky – Papert theory

3511/04/23

Un Un esempioesempioOR ESCLUSIVO (addizione binaria):

I punti a valore 1 non sono linearmente separabili da quelli a valore 0

Ipotesi: Esiste un neurone binario a soglia

tale che xy = 1 se e solo se x + βy ≥ . Essendo simmetrica, vale anche xy = 1 sse y + βx ≥ . Sommando e dividendo per 2 si ottiene: xy = 1 sse tx + ty = t(x+y)≥ ove t = (+ β)/2. Posto ora x+y = s, abbiamo: xy = 1 sse ts – ≥ 0.Dallo studio del polinomio di primo grado in s y = ts – si ottiene:

Per s = 0, ts – < 0 (00 = 0)Per s = 1, ts – ≥ 0 (01 = 1 = 10)Per s = 2, ts – < 0 (11 =0)

Questa é una contraddizione, poiché una retta non può salire e poi scendere

0⊕1 = 1

0⊕0 = 01⊕0 = 1

1⊕1 = 0

xy

x⊕y

β

3611/04/23

Il percettrone Il percettrone generalizzatogeneralizzato

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: x01

Funzione di attivazione:

con P(x) funzione sigmoidale.

Per ogni configurazione x del primo strato (ingresso),

la rete calcola una configurazione y dell'ultimo strato

(uscita)

∑=j

jjkk )xwP(x

3711/04/23

Il percettrone Il percettrone generalizzatogeneralizzato

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}

3811/04/23

Reti Reti multistratomultistrato

Strato 1Input

Pattern di output

Pattern di input

Strato 2Nascosto

Strato L-1Nascosto

Strato LOutput

3911/04/23

Reti Reti multistratomultistrato

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

( )22

1iii yt −Σ=Ε

● Tecnica di riduzione:

calo gradiente (versus pesi di connessione)

E

w

4011/04/23

Un Un esempioesempio

Una rete per l'or esclusivo con una unità nascosta

.5

1.5

+1 –2 +1

+1+1

4111/04/23

Retropropagazione Retropropagazione dell'erroredell'errore

L'algoritmo (senza unità nascoste)

I pesi sono modificati proporzionalmente a questa derivata (regola delta):I pesi sono modificati proporzionalmente a questa derivata (regola delta):

La convergenza a un minimo globale é garantita per funzioni di attivazione lineari senza unità nascoste e per dati consistentiLa convergenza a un minimo globale é garantita per funzioni di attivazione lineari senza unità nascoste e per dati consistenti

x

w

y

∂E∂wij

= ∂E∂yj

⋅∂yj

∂wij = –(tj–yj)⋅

∂yj

∂wij = –δj⋅

∂iwijxj

∂wij = –δj⋅xi

yj = wij∑h

xi

Δwij = η⋅δj⋅xi

4211/04/23


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 semilineare differenziabile non decrescente:

sj(t+1) = fj(nj(t))Es. : Funzione logistica

∑=i

iijj swn

inje1

1s −+

=

4311/04/23


Sia x input, y output atteso, t output effettivo.

Consideriamo la norma quadratica

Cerchiamo una regola di modifica dei pesi tale che:

con tasso di apprendimento. Poiché:

dobbiamo determinare

∑ −=Εj

2jj )y(t

2

1

Δw ij = – η ∂E

∂w ij

∂E∂wij

= ∂E∂nj

⋅ ∂nj

∂wij = ∂E

∂nj ⋅ sj = (def) –δj⋅ sj

δj = – ∂E∂nj

4411/04/23

Retropropagazione Retropropagazione dell'erroredell'errore Passo 1 – Input

Il neurone di input j é posto nello stato xj

Passo 3 – ConfrontoPer ogni neurone di output j, noto l'output atteso, si calcola:

Passo 4 – Retropropagazione dell'errorePer ogni neurone nascosto j, si calcola:

Passo 5 – Aggiornamento dei pesi

sj = fj(nj)

δj = fj'(nj)(tj – yj)

wij := w ij + δ isj

Passo 2 – Propagazione Per ogni neurone interno o di output

j si calcola lo stato

δj = fj' (nj)( wjh∑

hδh)

4511/04/23


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

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

Limiti

Possibili modifiche migliorative

Tasso di apprendimento adattivo: = g(gradiente di E)

Termine di momento

Range degli stati da –1 a 1

Deviazioni dalla discesa più ripida

Variazioni nell'architettura (numero di strati nascosti)

Inserimento di connessioni all'indietro

Tasso di apprendimento adattivo: = g(gradiente di E)

Termine di momento

Range degli stati da –1 a 1

Deviazioni dalla discesa più ripida

Variazioni nell'architettura (numero di strati nascosti)


Δwij(t+1) = ηδisj + αΔwij(t)

4611/04/23


Il tasso di apprendimento

grande, rischio di comportamento oscillatorio

piccolo, apprendimento lento

grande, rischio di comportamento oscillatorio

piccolo, apprendimento lento

Strategie di identificazione della architettura ottimale

Rete grande apprende facilmente, ma generalizza male

A partire da una rete grande tolgo neuroni nascosti, se valuto che può continuare ad apprendere anche con meno neuroni

Rete piccola apprende con difficoltà, ma generalizza bene

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

Rete grande apprende facilmente, ma generalizza male

A partire da una rete grande tolgo neuroni nascosti, se valuto che può continuare ad apprendere anche con meno neuroni

Rete piccola apprende con difficoltà, ma generalizza bene

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

4711/04/23

RetropropagazioneRetropropagazione dell'erroredell'errore

Il ruolo dell'integrazione

in presenza di connessioni con ritardo q l'input netto é:

la funzione E é calcolata pesando l'errore nel tempo:

nel calcolo delle derivate occorre aggiungere variabili ausiliarie

in presenza di connessioni con ritardo q l'input netto é:

la funzione E é calcolata pesando l'errore nel tempo:

nel calcolo delle derivate occorre aggiungere variabili ausiliarie


la rete può integrarsi con moduli tradizionali, sfruttando tutte le informazioni simboliche e le sinergie che vi possono essere

la rete può integrarsi con moduli tradizionali, sfruttando tutte le informazioni simboliche e le sinergie che vi possono essere

( ) ( ) ( )∑∑=

−=Q

1qj

qij

jj qtswtn

E = 12

σjt(sj – tj 2∑t=1

T∑j

4811/04/23

Come lavorare con la Come lavorare con la retropropagazioneretropropagazione

B.P. al lavoro

Come evitare i minimi locali?

Quanto è lungo il tempo di apprendimento?

Come scegliere ?

Nessuna risposta teoretica, solo risultati di simulazione

Come evitare i minimi locali?

Quanto è lungo il tempo di apprendimento?

Come scegliere ?

Nessuna risposta teoretica, solo risultati di simulazione

4911/04/23

Come lavorare con la Come lavorare con la retropropagazioneretropropagazione

Esempio: Funzione Logistica

jnje1

1o −+

= ∑ +=i

jiijj own ϑ

)o(1oe1

11

e1

1

)e(1

e

n

ojjnn2n

n

j

j

jjj

j

−=⎟⎟⎠

⎞⎜⎜⎝

⎛

+−⋅

+=

+=

∂

∂−−−

−

)o(1o)o(tä jjjjj −⋅⋅−=

∑⋅−=k

jkkjjj wä)o(1oä

unità output

unità nascosta

Il ruolo dell'integrazione

Troppo grande: oscillazione

Troppo piccolo: apprendimento lento

Troppo grande: oscillazione

Troppo piccolo: apprendimento lento

5011/04/23

Il problema Il problema XORXOR

Soluzione 1

y

x2x1

x3 2.2-

6.4-6.4

-4.2-9.4

-4.2

6.3

5111/04/23


Logistic function

= 0.5

558 cicli

Output ≤ 0.1 per 0 ≥ 0.9 per 1

4.23

2.23

10.63

e1

1x

e1

1x

e1

1x

+=

+=

+=

−

~ 0

~ 0

~ 1

2.1

3.1

2.1

e1

1y

e1

1y

e1

1y

−+=

+=

+= ~ 0

~ 0

~ 10x1x

0xx

1xx

21

21

21

==

==

==

5211/04/23


Soluzione 2

Minimo locale!!!!

Output 0.5 per input 11 e 01

6.587 presentazioni, =0.25

-.8

-.1 2.0

5.3 -4.5

-2.0

4.3 9.2

8.8

5311/04/23


APPRENDIMENTO NEL PRECETTRONE GEN.

0

01111

10111

11011

11101

11110

⎪⎪⎪

⎭

⎪⎪⎪

⎬

⎫

1

10000

01000

00100

00010

00001

⎪⎪⎪

⎭

⎪⎪⎪

⎬

⎫

INPUT OUTPUT INIZ. OUTPUT DOPO 250 CICLI

(1 CICLO) ( = .1)

10000

01000

00100

00010

00001

01111

10111

11011

11101

11110

46.

47.

48.

39.

51.

46.

48.

46.

48.

50.

02.

02.

03.

03.

02.

97.

97.

97.

97.

96.

5411/04/23


-.8

-2.9

-1.4

-.7-.4

-2.4-1.7

-1.4

-1.1

0

-.9-.4 -6.9 -3.3

-1.8

-1.4 -.8-2.2

-.1-1.5

-1.6

-1.2

-2.3-2.0

01011

00100

00101

11011

10010

01100

01001

10100

10110

00111

Difficoltà di classificazione

5511/04/23


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.

5611/04/23

Le reti di Le reti di HopfieldHopfield

n neuroni binari a soglia ui

connessione completa con pesi simmetrici Tij

evoluzione della rete verso uno stato stabile, a partire da 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:

Teorema: La rete converge a uno stato stabile, che é minimo globale o locale della funzione energia:

Dimostrazione:

E decresce o resta invariata ad ogni aggiornamento. Se si aggiorna ui a u'i si ha la variazione di energia:

Se

Se

Dimostrazione:

E decresce o resta invariata ad ogni aggiornamento. Se si aggiorna ui a u'i si ha la variazione di energia:

Se

Se

E = –12

Tij∑i≠j

uiuj∑j

ΔE = E' – E = –12

Δui Tij∑i≠j

uj

ui=0 e ui' =1 allora Δui=1 e Ti juj∑

j

≥0, e quindi ΔEi≤0

ui=1 e ui' =0 allora Δui=–1 e Ti juj∑

j

<0, e quindi ΔEi<0

5711/04/23

Le reti di Le reti di HopfieldHopfield

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

COMPUTAZIONE:

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)

Il meccanismo probabilistico e l'esistenza di più minimi locali possono portare a risultati diversi in diverse esecuzioni.

A

B

C

Stati di minimo

5811/04/23

Macchina di Macchina di BoltzmannBoltzmann

Rete di neuroni binari che usa la tecnica dell'annealing simulato per modificare le connessioni interne

Funzione obiettivo (bilineare):

Matrice di connessione simmetrica

No auto connessioni

Aggiornamento neuroni casuale

Funzione di attivazione sigmoidale casuale governata dalla seguente probabilità di transizione da s a s'

ove s é contiguo a s' sse la loro distanza di Hamming é 1

V = n∑

i,j=1

siwijsj + n∑i=1

isi = n∑i=1

sini (si∈{0,1})

5911/04/23

Macchina di Macchina di BoltzmannBoltzmann processo stocastico che, all'equilibrio, concentra la probabilità nella

regione critica M per V, in base alla legge di distribuzione

ove é una costante di normalizzazione

Procedure: MACCHINA DI BOLTZMANNExternal function: stopping_ruleBEGIN

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 siUNTIL stopping_rule é verificata

END

pβ(s) = e-βV(s)

Zβ

Zβ

6011/04/23

Apprendimento nelle Apprendimento nelle B.M.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 (Hebb)

2. 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

6111/04/23

Reti neurali e Reti neurali e apprendimentoapprendimento

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)

6211/04/23

Reti neurali e Reti neurali e apprendimentoapprendimentoApprendimento:

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 corrispondentei pesi sono modificati per produrre l'uscita migliore

1. Apprendimento con supervisionenoti ingresso e uscita corrispondentei pesi sono modificati per produrre l'uscita migliore

2. Apprendimento rinforzatonon è data l'uscita correttaviene detto se l'uscita prodotta é buona o cattiva

2. Apprendimento rinforzatonon è data l'uscita correttaviene detto se l'uscita prodotta é buona o cattiva

3. Apprendimento senza supervisioneLa rete sviluppa le proprie regole di classificazione mediante l'estrazione di informazioni dagli esempi ricevuti

3. Apprendimento senza supervisioneLa rete sviluppa le proprie regole di classificazione mediante l'estrazione di informazioni dagli esempi ricevuti

6311/04/23

Apprendimento da Apprendimento da esempiesempi

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)

Approcci

Apprendimento induttivo (Solomonov, Goodman, Blum) [Risultati asintotici]

Apprendimento computazionale (Valiant, Blumer, Natarajan) [ Risultati probabilistici]

Apprendimento con reti neurali (Hinton, Kohonen, Seinowskj)

6411/04/23

Apprendere Apprendere come ?come ?

Data una funzione (ignota) f: X Y Estrarre un campione e

sottoporlo a una rete neurale Cercare la rete neurale che simula f

Data una funzione (ignota) f: X Y Estrarre un campione e

sottoporlo a una rete neurale Cercare la rete neurale che simula f

Il compito

La strategia di apprendimento

Minimizzare una opportuna funzione della differenza E tra il comportamento effettivo della rete e quello che si accorderebbe col campione

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)Discesa lungo il gradiente (rispetto ai pesi)

La valutazione dell'apprendimento

Per generalizzazione della funzione appresa a nuovi esempi mai visti dalla retePer generalizzazione della funzione appresa a nuovi esempi mai visti dalla rete

{(x1,f(x1)), … ,(xn,f(xn))}

6511/04/23

Apprendere Apprendere come ?come ?

generatore dei parametri iniziali

della rete

generatore diesempi

RETENEURALE

+

modulo di confronto

modulo di calcolo delgradiente

x

y z

W

W'ΔW

6611/04/23

Alcune Alcune applicazioniapplicazioni

Filtri adattivi per telecomunicazioni1959 B. Widrow ADALINE

Valutazione rischi per mutui e prestitiNestor Mortgage Risk EvaluatorTraining su qualche migliaio di casiIndividua pattern di dati associati a forte rischioPuò essere configurato come prudente o ottimistaConfronto con esperto umano promettente

Individuazione di esplosiviSAIC SNOOPERiconosce il pattern di emissioni gamma di esplosiviReagisce a poco più di un kg di esplosivoInstallato al JFK di NY – Costo: 1.1 M$Prevista l'installazione in altri grandi aeroporti

6711/04/23

Alcune Alcune applicazioniapplicazioniMonitoraggio di processo

GTE Produzione lampadineConfronta dati da sensori con gli standard(variaz. di temperatura, pressione, sostanze chimiche)Determina condizioni di produzione ottimaliVantaggi su tecniche statistiche (regressione lineare):raccolta dati incrementale, meno memoria

Riconoscimento parlatoIntelAccuratezza 99% su un centinaio di parole da un solo

speakerUsato per registrare relazioni di ispettori

Individuazione prodotti difettosiSiemensImpianti condizionamento per auto rumorosiAccuratezza 90%

6811/04/23

Prototipi e Prototipi e ricercaricerca

Classificazione segnali sonarBendix AerospaceDistingue mine da rocce o altri oggetti sul fondo marinoAccuratezza 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)

6911/04/23

Prototipi e Prototipi e ricercaricercaMovimento di un braccio flessibile

m

r

ϑ(τ)

w(r,t)

7011/04/23

Prototipi e Prototipi e ricercaricercaControllo degli angoli di un satellite geostazionario

Y

Z

X

yaw

roll

pitch

Inertial frame

Absolute frame

Satellite frame

1 09/09/2014 LE RETI NEURALI: MODELLI, ALGORITMI E APPLICAZIONI Giancarlo Mauri Università di...

Documents

Transcript of 1 09/09/2014 LE RETI NEURALI: MODELLI, ALGORITMI E APPLICAZIONI Giancarlo Mauri Università di...