03-Perceptron

5/10/2018 03-Perceptron - slidepdf.com

http://slidepdf.com/reader/full/03-perceptron 1/10

1

3. Perceptronul

3.1 Perceptronul şi procesarea paralelăUnităţile McCulloch–Pitts sunt elementele constructive ale unor reţele care pot calcula orice funcţie logică sau care pot simula orice automat finit. O

caracteristică a unor astfel de reţele este că acestea trebuie completspecificate înainte de a fi utilizate şi nu există parametri care să poată fiajustaţi după ce reţelele au fost proiectate, în scopul de a trata problemediverse. Învăţarea şi adaptarea pot fi implementate doar prin modificareamodelului de conectivitate şi ale valorilor pragurilor. În continuare vor fitratate reţelele ponderate pentru flexibilitatea pe care o au relativ la ajustarea parametrilor numerici în scopul tratării unor probleme de mai marediversitate.

3.1.1. Perceptronul ca element cu prag ponderatModelul introdus în 1958 de Frank Rosenblatt, aşa-numitul perceptron

clasic, a fost ulterior investigat de Minsky şi Papert, rezultatul fiind actualul perceptron. Perceptronul clasic este o reţea pentru tratarea unor probleme derecunoaştere a caracterelor şi este schematic ilustrat în fig. 1. O suprafaţă de proiecţie, retina, transmite valori binare către un strat de elemente de calculîn aria de proiec ţ ie. Conexiunile de la retină la aceste elemente suntdeterministe şi fixe, neadaptive. Conexiunile de la al doilea strat cătreunităţile ce formează stratul numit arie de asociere şi de la acest strat către altreilea care furnizează r ăspunsurile, sunt selectate stocastic. Sistemul trebuieantrenat pentru a recunoaşte anumite modele din regiunea de conexiuni caresă conducă la anumite valori de ieşire al unităţilor de pe ultimul strat,misiunea algoritmului de învăţare fiind determinarea unor ponderi adecvate

ale conexiunilor. Diferenţa între o reţea de unităţi McCulloch–Pitts şi perceptronul clasic constă în existenţa ponderilor.

conexiuni

locale

conexiuni

aleatoare

arie de proiectie arie de asociere

retina

raspunsuri

Fig. 1. Perceptronul clasic



2

În modelul Minsky–Papert retina este o arie de pixeli cu valori binare pe caremodelul este proiectat. Unii pixeli din retină sunt conectaţi la elemente logicenumite predicate care calculează un singur bit ca r ăspuns la valorile pixelilor asociaţi, iar acest predicat poate avea o complexitate computaţională destulde mare. Fiecare predicat este restricţionat, de exemplu, de numărul de pixeli

din retină ce pot fi examinaţi simultan sau de distanţa maximă între aceşti pixeli. Predicatele transmit valorile binare către un element cu prag ponderatca în fig. 2.

θ

P1 w1

P3

w3P2

w2

P4

w4

Fig. 2. Predicate şi ponderi asociate unui perceptron

Desigur, ar trebui date r ăspunsuri referitoare la modele pot fi recunoscutefolosind un singur element la ieşirea reţelei şi la limitele de lucru în paralel însituaţia în care un predicat poate examina un număr limitat de pixeli din toatăretina.Restricţiile asupra unui predicat constau faptul că el produce doar o valoare binar ă şi câmpul de pixeli examinaţi nu acoper ă toată retina. Dacă predicatelesunt n P P ,...,1 iar ponderile conexiunilor la elementul cu prag sunt respectiv

nww ,...,1 , atunci sistemul emite “1” doar atunci când θ ≥∑ = i

n

i i P w1

, unde

θ este pragul unităţii de ieşire. Acest model de perceptron este o variantăsimplificată a perceptronului clasic.

3.1.2. Limite computaţionale ale perceptronuluiPentru a explora proprietăţile perceptronului, vom presupune că numărul de predicate este fixat. Chiar dacă acestora le este alocată o putere de calculnelimitată, punctul critic îl reprezintă calculul paralel în singurul element cu prag. Astfel, fiecare procesor este obligat să coopereze prin producerea unuirezultat adecvat deciziei globale. Asupra limitelor câmpurilor receptive se pot

enunţa următoarele:- Perceptroni cu diametru limitat: câmpul receptiv al fiecărui perceptronare un diametru limitat.



3

- Perceptroni cu ordin limitat: numărul de puncte din fiecare câmp receptivnu poate depăşi o limită dată.

- Perceptroni stocastici: fiecare câmp receptiv constă dintr-un număr de puncte alese aleator.

Minsky şi Papert au demonstrat existenţa unor probleme care nu pot fi

rezolvate de un singur perceptron care acţionează ca o unitate de deciziefinală. Conectivitatea este un exemplu de problemă la care perceptronul nu poate r ăspunde.

Propoziţia 1. Un perceptron cu diametru limitat nu poate decide dacă o

figur ă geometrică este conexă . Demonstra ţ ie. Să presupunem că există un perceptron cu diametru limitatcapabil să decidă dacă o figur ă este conexă. Fie modelele A,B,C,D din fig.3(a), în care doar B şi C sunt conexe.

G1 G2G3

A B C D

(a)

(b)

Fig. 3. Modele şi câmpuri receptive ale predicatelor

Din faptul că diametrele câmpurilor receptive sunt limitate, figurile pot fideformate oblic pe orizontală, astfel încât nici un câmp să nu conţinăsimultan puncte din extremitatea stângă şi dreaptă a modelelor, ca în fig.3(b). Aceasta duce la o împăr ţire a predicatelor în trei grupuri. Primul grup

1G constă din predicatele ale căror câmpuri receptive conţin puncte din

partea stângă a figurii. În al doilea grup 2G de predicate, câmpul receptivacoper ă latura dreaptă a figurii. Predicatele r ămase formează al treilea grup

3G . Situaţia este ilustrată în figura 3(b). Toate predicatele sunt conectate la

un element cu prag prin muchii ponderate. Acest element decide dacă ofigur ă este conexă evaluând condiţia



4

.0321

321≥−++= ∑∑∑

∈∈∈

θ

G P

ii

G P

ii

G P

ii

iii

P w P w P wS

Dacă 0≥S atunci se decide că figura este conexă.Dacă este analizată figura A, care nu este conexă, atunci ar trebui să se obţină

0<S . Prin mutarea laturii din dreapta a dreptunghiului, figura A poate fi

transformată în figura B f ăr ă a afecta rezultatele predicatelor din 3G carenu sesizează diferenţa deoarece câmpurile lor receptive nu acoper ă marginilelaterale ale figurii aşa cum se poate vedea în figura 3(b). De asemenea, predicatele din 1G nu-şi modifică ieşirile pentru că în câmpurile lor receptive

nu s-a produs nici o schimbare. Predicatele din 2G modifică ieşirile lor cu

S 2∆ astfel încât, după deformarea lui A, avem

02 ≥∆+ S S

pentru că acum se recunoaşte figura conexă B. De aici obţinem că.2 S S −≥∆

Dacă figura A este transformată în C prin deplasarea laturii din dreapta a

dreptunghiului în jos, atunci predicatele din 2G şi din 3G nu-şi modifică

r ăspunsul, însă cele din 1G conduc la o modificare S 1∆ în S astfel încât

01 ≥∆+ S S

deoarece şi acum trebuie recunoscută o figur ă conexă C şi deci .1 S S −≥∆

Acum, dacă figura A este transformată în figura D prin deplasarea ambelor laturi ale dreptunghiului, predicatele din 1G nu pot distinge acest caz faţă de

cazul figurii C iar cele din 2G nu fac distincţia faţă de figura B. Desigur, în

acest caz predicatele din 3G nu-şi schimbă ieşirile, aşa că

S S S S 212 −≥∆+∆=∆

şi din aceasta rezultă că0>−≥∆+ S S S

adică sistemul r ăspunde ca şi cum D ar fi conex, ceea ce este în contradicţiecu faptul că D nu este conex. Argumentaţia de mai sus este prezentată sinteticîn diagrama din fig. 4. Semnificaţia acestui rezultat este că proprietatea deconectivitate este una globală care nu poate fi decisă local.



5

Aneconexa

(S<0)

∆2S

∆

1S

Bconexa

(S+ 2S>=0)∆

∆ ∆ ∆S= 2S+ 1S

Cconexa

S+ 1S>=0∆

Dneconex

S+ S>=-S>0∆

Fig. 4. Diagrama transformărilor pentru proprietatea de conectivitate.

3.2. Perceptronul şi interpretarea geometricăReţelele cu unităţi McCulloch–Pitts pot implementa funcţii booleenearbitrare. Reţelele ponderate pot asigura acelaşi lucru folosind un număr mic

de por ţi cu prag. În continuare, perceptronul este considerat ca o unitate cu prag izolată care calculează rezultatul f ăr ă întârzieri.

Definiţia 1. Un perceptron simplu este o unitate de calcul cu pragul θ care

prime şte n intr ă ri reale n x x ,...,1 de-a lungul muchiilor cu ponderile respectiv

nww ,...,1 şi care emite 1 dacă ∑ =≥

n

i i xw1 1 θ şi 0 în caz contrar.

Intr ările perceptronului simplu pot fi furnizate de alţi perceptroni sau alteelemente de calcul. Un perceptron separ ă spaţiul intr ărilor în două subspaţii.Pentru punctele dintr-un subspaţiu, rezultatul emis este 0 şi pentru punctele

celuilalt este 1. Prin ajustarea ponderilor şi a pragului se obţine orice separaredorită de tipul menţionat mai înainte.Adesea este preferabil să se considere perceptroni cu prag nul, acestacorespunzând cazului în care planul separator trece prin origine. Pentru aevita această limitare, se adaugă perceptronului o nouă intrare prin care se primeşte valoarea 1 iar muchia care conectează această intrare cu unitatea areca pondere valoarea dorită a pragului, ca in figura 5.

w1 x1

n xn

w

.

.

.

θ

w11

n

nw

.

.

.

−θ1

0

Fig. 5. Tratarea pragului ca o pondere şi o intrare constantă



6

Această pondere suplimentar ă împreună cu intrarea constantă se numeşteînclinaţie (bias). În contextul acestei transformări, vectorul de intrare iniţial( n x x ,...,1 ) se transformă în vectorul de intrare extins ( 1,,...,1 n x x ), iar vectorul

ponderilor în vectorul extins al ponderilor ( 11 ,,...,+nn www ) , cu θ −=

+1nw .

3.2.1. Problema XOR Pentru a avea o idee asupra posibilităţilor unui perceptron izolat, săconsider ăm funcţii booleene de 2 variabile. Cele 16 funcţii de două variabilesunt definite în tab. 1.

Tab. 1. Funcţiile booleene de două variabilex1 x2 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 f 13 f 14 f 15

0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 10 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 11 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 11 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Din interpretarea geometrică anterioar ă, funcţiile booleene f calculabile de

un perceptron izolat sunt acelea pentru care punctele din { })0(1− f sunt

separate printr-o dreaptă de cele din { }).1(1− f Funcţiile 6 f şi 9 f (respectiv,

funcţia XOR şi cea de echivalenţă EQU) nu pot fi calculate de un perceptron izolat aşa cum este ilustrat în fig.(a)-(b). Funcţiile OR şi AND potfi calculate cu un perceptron izolat (fig. 6(c)-(d)).

11

0 1

OR

1

0

AND

0

0

01

0 1

(a) (b) (c) (d)

XOR

1

1

EQU

0

0

Fig. 6. Atributul de neseparabilitate/separabilitate pentru spaţiul intr ărilor.O demonstraţia a faptului că funcţia de echivalenţă nu poate fi calculată de unsingur perceptron este următoarea.

01 = x 02 = x 02211 =+ xw xw ⇒ θ ≥0

11 = x 02 = x 12211 w xw xw =+ ⇒ θ <1w

01 = x 12 = x 22211 w xw xw =+ ⇒ θ <2w

11 = x 12 = x 212211 ww xw xw +=+ ⇒ θ ≥+ 21 ww .



7

Conform primei condiţii, θ este negativ. Din inegalitatea a doua şi a treiarezultă θ 221 <+ ww în timp ce ultima dă θ ≥+ 21 ww . Contradicţiaobţinută arată că funcţia de echivalenţă nu este calculabilă de un perceptron.

3.2.2. Separabilitate liniară

Conceptul de separabilitate a fost ilustrat pentru funcţiile booleene de douăvariabile.Definiţia 2. Două mul ţ imi A şi n R B ⊂ se numesc separabile liniar dacă

exist ă 111 ),...,( +

+∈

n

n Rww astfel încât

,1∑ = +

≥n

i inii w xw )(∀ A x x n ∈),....,( 1

şi

,1∑ = +

<n

i inii w xw )(∀ B x x n ∈),....,( 1

3.2.3. Dualitatea între spaţiul intrărilor şi al ponderilor

Când se caută valori adecvate pentru cele n ponderi ale unui perceptron,spaţiul de căutare este n R . Dacă consider ăm un perceptron cu n intr ări,atunci este necesar să determinăm 1+n parametri corespunzători celor n

ponderi şi înclinaţiei. Aceste 1+n valori reprezintă un punct în 1+n R privit caspaţiu al ponderilor. Atunci când alegem un punct în spaţiul ponderilor sealege de fapt o combinaţie de valori ale ponderilor şi o separare liniar ă aspaţiului intr ărilor. Aşadar, unui punct din spaţiul ponderilor 1+n R îicorespunde un hiperplan în spaţiul extins al intr ărilor 1+n R ca în fig. 7. Dacă ponderile alese sunt ,1w ,2w 3w atunci ecuaţia hiperplanului este

.0332211 =++ xw xw xw

Invers, dacă dorim ca punctul ),,( 321 x x x să fie plasat în subspaţiul pozitivdefinit de un plan, atunci trebuie să determinăm ponderile ,1w ,2w 3w astfel

încât.0332211 ≥++ xw xw xw

Această inegalitate induce o separare liniar ă a spaţiului ponderilor 1+n R şi punctul ),,( 321 x x x defineşte planul de secţionare care are ecuaţia

0332211 =++ xw xw xw ,),,( 3321 Rwww ∈

pentru ),,( 321 x x x fixat. Aşadar, un punct ),,( 321 x x x din spaţiul extins al

intr ărilor conduc la un hiperplan în spaţiul extins al ponderilor (v. figura 7).

Deci puncte dintr-un spaţiu sunt aplicate în plane din celălalt spaţiu. Aceastadefineşte o relaţie de dualitate.



8

Fig. 7. Dualitatea spaţiului intr ărilor şi al ponderilor

3.2.4. Funcţia de eroare în spaţiul ponderilorDate două mulţimi ce trebuie separate de un perceptron, un algoritm deînvăţare trebuie să determine valori adecvate ale ponderilor şi pragului. Mai precis, fie A şi B două mulţimi în spaţiul intr ărilor n R ce trebuie separateastfel încât perceptronul calculează o funcţie binar ă w f cu

,1)( = x f w A x ∈∀)(

,0)( = x f w .)( B x ∈∀

Funcţia binar ă w f depinde de ponderi şi de prag. Func ţ ia de eroare este

numărul de clasificări false obţinute prin folosirea vectorului extins de ponderi w şi este definită ca:

∑∑ ∈∈+−=

B x w A x w x f x f w E ).())(1()(

Algoritmul de învăţare a perceptronului are ca scop minimizarea acesteifunţii, valoarea minimă posibilă pentru E fiind zero.

3.2.5. Curbe de decizie generalePerceptronul ia o decizie pe baza separ ării liniare a spaţiului intr ărilor.Separ ări mai generale ale spaţiului intr ărilor permit tratarea unor problemenerezolvabile cu un singur perceptron. În fig. 8 este ilustrată separareaneliniar ă a spaţiului intr ărilor pentru funcţia XOR. Funcţiile folosite pentru adiscrimina între regiuni ale spaţiului intr ărilor se numesc curbe de decizie.Aceste curbe pot fi date de polinoame sau curbe spline. Astfel, înrecunoaşterea statistică a caracterelor se presupune că modelele ce trebuie

recunoscute sunt grupate în clustere în spaţiul de intrare. Aceste clustere potfi izolate între ele prin combinaţii de curbe de decizie. Alternativ, se potcombina perceptroni pentru a izola o regiune convexă a spaţiului.



9

0

0 1

1

Fig.8. Curbă de decizieÎn general, este necesar să se discrimineze între diverse regiuni ale spaţiului.Sarcina unei RNA este să identifice aceste regiuni şi apoi să le asociezer ăspunsuri adecvate. Problema principală este să se ştie dacă parametriicorespunzători acestor regiuni de decizie pot fi determinaţi printr-un algoritmde învăţare.

3.3. Aplicaţie - detecţia muchiilor în imaginiFie o imagine dată sub forma unei matrice de pixeli. Fiecărui pixel i seasociază un număr întreg pozitiv reprezentând nivelul de gri (sau al uneianumite culori) corespunzător. Pentru detecţia muchiilor, intensitatea fiecărui pixel este comparată cu cea a vecinilor aflat la o distanţă specificată şi încazul în care există o diferenţă remarcabilă se decide că pixelul curentapar ţine unei muchii. Să presupunem că fiecare pixel este conectat la un perceptron care primeşte intr ări şi de la vecinii pixelului. În figura 9(a) este precizat modelul de vecinătate care defineşte câmpul receptiv iar ponderileasociate intr ărilor respective sunt date în fig. 9(b). Intrarea ce pleacă din pixelul central este ponderată cu 8 iar celelalte cu –1.

Fig.9. Câmpul receptiv şi ponderile detectorului de muchii

Cu această fereastr ă se scanează toţi pixelii din imagine (fig. 10) acţionânddiferit pentru pixelii situaţi pe frontiera acesteia. Dacă ija este intensitatea

pixelului ),( ji atunci pentru pixelul ),( ji se calculează predicatul

∑∑= =

+−+−≥

2

0

2

01,1 5.0

h k

hk k jhi wa .

hk w 0 1 2

(i-1,j-1) (i-1,j) (i-1,j+1) 0 -1 -1 -1(i,j-1) (i,j) (i,j+1) 1 -1 8 -1

(i+1,j-1) (I+1,j) (i+1,j+1) 2 -1 -1 -1(a) (b)



10

Dacă rezultatul este 1 atunci pixelul ),( ji apar ţine unei muchii.

0.5

Fig. 10. Conectare la o fereastr ă de pixeli

Exercitiu.Să se demonstreze că dacă două mulţimi A şi n R B ⊂ sunt separabile liniar

atunci există 11 1( ,..., ) n

nw w Q ++ ∈ astfel încât ,

1∑ = +≥

n

i inii w xw )(∀

A x x n ∈),....,( 1 şi ,1∑ = +

<n

i inii w xw )(∀ B x x n ∈),....,( 1 , unde Q este

mulţimea numerelor raţionale.

03-Perceptron

Documents

Transcript of 03-Perceptron