Post on 12-Jan-2016
description
transcript
Sisteme de programeSisteme de programepentru timp realpentru timp real
Universitatea “Politehnica” din Bucuresti2007-2008
Adina Magda Floreahttp://turing.cs.pub.ro/sptr_08
si curs.cs.pub.ro
Curs Nr. 5
Reţele neurale• Retele perceptron
• Reţele backpropagation
2
1. Reţele Perceptron
• Rosenblatt [1962] – perceptron "clasic"
• Model actualizat de Minsky si Papert
• Intr. binare sau continue
• Exemple la intrari xs1,…xs
N, s=1,M
• Iesiri ys = +1/0 (se poate si +1/-1)
• ds – iesiri dorite (ds = ys ?) pt s = 1,M
3
x
x
x
w
w
w
y
1
2
N
1
2
N
Intrari
Iesire
...
x = 1
x
x
w
w
y
0
1
N
1
N
Iesire
...
Intrari
x
xA A
A
AA
AB
B
B
B
B
B
BB
2
1
(a) Reprezentare perceptron (b) Reprezentare perceptroncu intrare fictiva x0
(c) Regiunile de decizie ale unui perceptroncu doua intrari x , x1 2
dreapta de decizie
y = +1 clasa Ay = -1 clasa A
y f ( w x )h i ii 1
N
y f ( w x )h i i
i 0
N
• Perceptron = Unitate computationala cu valoare de prag care pentru intrari x1,..xn si ponderi w1…wn produce la iesire +1 dacai=1,N wixi si 0 (sau -1) in caz contrar
• Separa spatiul intrarilor in 2 zone: pct pt care rezultatul este 1 si pctpt care rezultatul este 0
trece prin origine
y f ( w x )h i ii 1
N
y f ( w x )h i ii 0
N
Exemplu: SAU logic, intrari 0/1, iesiri 0/1, f. treapta
x1 1
1x2 = 0
y
X1
X2
0.9
2
=1
Exemplu: perceptron cu 2 intrari reale, iesiri 0/1, f. treapta
Caracteristici
Ponderi: invatate sau calculate
Minsky si Papert [1969] au pus in evidenta limitarile modelului computational al perceptronilor
Functiile calculabile de perceptron – acele functii pentru care punctele cu valoarea functiei 1 (A) pot fi separate de punctele cu valoarea functiei 0 ( B) – liniar separabile
6
7
• Nu orice functie este calculabila de perceptron• De exemplu AND si OR pot fi calculate, dar nu XOR
x1=0 x2=0 w1x1+w2x2 = 0 => 0 < x1=1 x2=0 w1x1+w2x2 = w1 => w1 x1=0 x2=1 w1x1+w2x2 = w2 => w2 x1=1 x2=1 w1x1+w2x2 = w1+w2 => w1+w2 <
• Cate functii liniar separabile?n=2 14 din 16n=3 104 din 256n=4 1882 din 65536
• Calculul facut de perceptron poate fi vazut ca o separare liniara a spatiului de intrare dar si ca o cautare in spatiul ponderilor
• Perceptron cu n intrari – gaseste n+1 parametrii – reprezinta un punct in spatiul cu n+1 dimensiuni al ponderilor
• Alegem un punct in spatiul ponderilor => alegem o combinatie de ponderi si o separare liniara specifica in spatiul de intrare
• Fiecare punct in spatiul n+1 al ponderilor poate fi asociat cu un hiperplan in spatiul intrarilor de dimensiune n+1
• Dualitate intrari - ponderi
Functionare perceptron
2 etape ale functionarii
9
Algoritmul de invatare al perceptronului
1. Initializeaza ponderile wk si valoarea de deplasare cu valori aleatoare mici ([-0.1, +0.1]
2. Prezinta cele M exemple. Fie y(0) iesirea perceptronului la momentul de timp 0
3. daca toate exemplele sunt clasificate corect (ds=ys)
atunci STOP /* perceptronul a invatat */
4. Actualizeaza ponderile si valoarea de deplasare
pentru fiecare exemplu s=1,M repeta
4.1.Calculeaza iesirea perceptronului
ys(t) = f(k=0,N wk(t)xsk)
4.2.Corecteaza ponderi la momentul de timp t + 1
wk(t+1) = wk(t) + (ds – ys) xsk
(wk – delta rule)
5. repetea de la 3
sfarsit 10
Justificarea actualizarii ponderilor
• Functia de eroare – numar de clasificari incorecte obtinute cu un set de ponderi
Eroare = ½ i(di-yi)2
• Poate fi interpretata ca o functie de energieE(w) 0
• Dorim un minim global pentru E(w) =0• Metoda scaderii gradientului: pt a afla un minim
local se iau pasi proportionali cu negativul gradientului functiei in punctul curent
11
Justificarea actualizarii ponderilor - cont
• Actualizarea ponderilor se bazeaza pe metoda scaderii gradientului: schimbarea fiecarui wk cu o cantitate wk proportionala cu gradientul functiei de energie E (masura a erorii) pentru un anumit punct
• wk(t+1) = wk(t) + (ds – ys) xsk
wk= (ds – ys) xsk = s xs
k
• Eroare = ½ i(di-yi)2
12
Justificarea actualizarii ponderilor - cont
• Eroare = ½ i(di-yi)2
• Modificare eroare in fct de iesire Eroare/ yi= [1/2 i(di-yi)2]/ yi =
[1/2 (di-yi)2]/ yi = - (di-yi)• Modificare eroare in fct de ponderi Eroare/ wk= Eroare/ yi * yi / wk=
- (di-yi) * yi / wk= - (di-yi) * (k=0,N wkxk) / wk
= - (di-yi) *xk
Delta rule la perceptron
wk(t+1) = wk(t) + (ds – ys) xsk cu =1 13
Exemple de utilizare
• Detectarea laturilor unei imagini cu perceptroni• Edge detection – extragerea laturilor (presupus mai
inchise decat fondul)• Fiecare pixel comparat cu vecinii lui – daca este negru si
un vecin este alb atunci este clasificat ca facand parte din latura
• Vecinatati Moore• Operator de convolutie
14
-1 -1 -1-1 8 -1-1 -1 -1
-1 0 1-1 0 1 -1 0 1 latura verticala intre sup alba stg si neagra dr
Exemple de utilizare
• Recunoasterea caracterelor• Clasificarea unei litere cu t pixeli negrii = t-1 – clasifica T-uri cu 1 pixel gresit (distorsionat)
• Se poate ajusta pt a recunoaste figuri cu 2, 3 .. pixeli distorsionati
• Problema
15
Exemple de utilizare
• Cognitron• Exemplu de "quad-pyramid" – rezolutia este redusa cu
un factor de 4 de la plan la plan.• Fiecare pixel dintr-un plan superior este legat la 4 pixeli
din unul inferior
16
arhitectura piramidala
Exemple de utilizare
• Neocognitron
17
• Neocognitron• UC0. Planul de intrare este UC0,
transformat in 12 imagini US10 ,... US1
11 cu aceeasi rezolutie
• US1i. Operatorul de transformare de la
UC0 la US1i are intrari 3 x 3 pixeli din
UC0, si fiecare pixel din US1i are asociat
un astfel de operator.• In fiecare plan numai o anumita
caracteristica este recunoscuta: US11 –
toate laturile verticale din UC0, US12
numai diagonale, etc.• UC1
j Urmatorul nivel de prelucrare este format din planele UC1
j
• Fiecare pixel din UC1j se conecteaza la
un pixel din 1 sau 2 plane US1i
• Ponderile sunt de excitare si efectul acestui plan este sa suprapuna activarea imaginilor selectate din US1
i si sa le estompeze in acelasi timp, prin largirea sablonului.
• Acest lucru se realizeaza prin transformarea valorii fiecarui pixel in suma ponderata a valorii lui si a valorilor vecinilor.
18
• Neocognitron• US2
i Pe urmatorul nivel/plan de prelucrare fiecare pixel dintr-un plan US2
i se conecteaza la o unitate in aceeasi pozitie din imaginile UC1
j. Pe acest nivel se poate reduce rezolutia imaginilor, ca in arhitecturile piramidale.
• Se alterneaza astfel nivelurile US si UC pana ce UC4 clasifica in clase 0, . . . , 9
• Toleranta la deplasari si rotiri: UC estompeaza imaginea si US extrage caracteristici specifice.
19
2. Reţele backpropagation
• Perceptronii multi-nivel sau retele backpropagation
• Sunt retele neuronale cu activare directa care contin unul sau mai multe straturi de noduri intre nodurile de intrare si nodurile de iesire.
• Aceste straturi suplimentare reprezinta nivelele ascunse ale perceptronilor multinivel.
20
x x x0 2 A
Intrarix1
...
...
h0
y y2 C
y1 Iesiri
Strat ascuns
w1ij
w2ij
i=1,Aj=1,B
i=1,Bj=1,C
11
12
22
21
Perceptroni multi-nivel cu doua nivele si un strat ascuns
2.1 Caracteristici
2 etape ale functionarii
functii sigmoid
intrari binare sau reale in intervalul [0, 1] sau [-1, +1]
23
j 1iji=1
A
i 1jh = f ( w x - ), j = 1,B
y = f ( w h - ), j = 1,Cj 2iji=1
B
i 2 j
iesire =1
1+ e-suma intrari
Structuraperceptronmultinivel
Tipulregiuniide decizie
ProblemaSAUexclusiv
Jumatate deplan limitatde un hiperplan
1 NIVEL
2 NIVELERegiuniconvexeinchisesaudeschise
3 NIVELEArbitrar.Complexitateaeste limitatade numarulde noduri.
Clase curegiuniamestecate
Forma ceamai generalaa regiunii
B
B A
B
A
B
B
B
A
B
B
A
A
A
A
A
Tipurile regiunilorde decizie formatede un perceptronmultinivel
2.2 Functionare
Algoritmul de invatare al retelelor backpropagation este format din doi pasi principali:
(a) o parcurgere directa a retelei, de la intrari la iesiri, in care se activeaza reteaua si se determina valorile iesirilor
(b) o parcurgere inapoi a retelei, de la iesiri la intrari, in care iesirile calculate se compara cu iesirile din exemple si se determina o estimare a erorii; aceasta estimare a erorii este propagata inapoi si utilizata la actualizarea ponderilor.
epoca
25
2.2 Functionare - cont
Notatii algoritm
este factorul de scalare care reprezinta viteza de invatare
reprezinta valorile iesirilor din exemple, cate o secventa pentru fiecare exemplu
reprezinta estimarea erorilor la nivelul stratului de iesire
reprezinta estimarea erorilor la nivelul stratului ascuns.
26
d , j = 1,Cj
2 j, j = 1,C
1j, j = 1,B
Algoritmul de invatare backpropagation
1. Initializeaza ponderile si valorile de deplasare cu valori aleatoare mici in intervalul [-0.1, 0.1]
2. pentru fiecare exemplu executa2.1. Calculeaza iesirea retelei
2.2. Calculeaza erorile la nivelul stratului de iesire
27
w aleator(-0.1, 0.1) i = 0,A, j = 1,B1ij
w aleator(-0.1, 0.1) i = 0,B, j = 1,C2ij
B1,=j 1
h A
0=i
i1ij )xw(
j
f
C1,=j 1
y B
0=i
i2ij )hw(
j
f
2 j j j j jy (1- y )(d y ) j=1,C
Algoritmul de invatare backpropagation - cont
2.3. Calculeaza erorile la nivelul stratului ascuns
2.4. Modifica ponderile
3. repeta pasul 2 de cite ori se doreste
sfarsit
28
w (t +1) h + w (t) i = 0,B j = 1,C2ij 2 j i 2ij
B1,=jA 0,=i (t)w+ x 1)+(tw 1iji1j1ij
B1,=j w)h-(1h 2ij
C
1=i2ijj1j
Observatii
Generalizare la retele backpropagation cu mai mult de doua niveluri
Viteza de invatare
termen moment
29
0 1
w (t +1) h + [w (t) - w (t -1)] i = 0,B j = 1,C2ij 2 j i 2ij 2ij
w (t +1) h + [w (t) - w (t -1)] i = 0,A j = 1,B1ij 1j i 1ij 1ij
Observatii - cont
Actualizarea ponderilor se face to cf. metodei scaderii gradientului - functie de eroare care depinde de diferenta intre iesirea dorita si iesirea curenta a retelei pentru a scadea gradientul.
Un algoritm backpropagation poate ajunge sa calculeze un set de ponderi care nu rezolva problema
Fenomenul de overfitting Nr de ponderi care se invata / nr. de ponderi care
influenteaza o iesire particulara < nr. de exemple Impartirea exemplelor de invatare in doua multimi Optimal brain damage Tiling
30
2.3 Exemple retele backpropagation
SAU EXCLUSIV – intrari 0, 1, f. limitator
31
x11
1
= 0.5
1
1x2
= 1.5
y
-2
1
SI logic
x0
1 1
= 0 pt toti
1
0.5
x1
y0
-1
1
ymax y1
-1
0.5 0.5
0.5
32
- f1 functie de transfer treapta - f2(t) = t daca t 0-t daca t < 0
- f3(t) = t
Retea care selecteazamaximuma doua intrari reale
2.3 Exemple retele backpropagation - cont
Parabola: invata sa coreleze viteza initiala de lansare a unui proiectil si pozitia tintei cu unghiul corect de lansare
OCR: invata sa recunosca digiti
Vehicul: invata sa ghideze pozitia volanului unui vehicul in functie de pozitia de plecare a vehiculului si de pozitia destinatiei
Functie: invata o functie pe baza unei multimi de puncte
33