RETELE NEURALE
3.1 PRINCIPII GENERALE
Scopul recunoasterii formelor este de a clasifica o multime de obiecte, procese sau evenimente de orice natura, pe baza unor caracteristici obtinute prin masuratori indirecte. Numarul de clase de forme este in functie de aplicatia particulara.
Metodele de recunoastere a formelor pot fi clasificate in doua mari categorii:
-metode decizionale;
-metode sintactice.
Metodele decizionale se bazeaza pe un set de masuratori selectate din formele de intrare, numite caracteristici.
Metodele sintactice de recunoastere a formelor tin cont si de informatia structurala care caracterizeaza fiecare forma. Ca urmare procesul de recunoastere nu se limiteaza doar la clasificarea formei respective, ci include metode capabile sa descrie acele aspecte ale formelor care le fac sa nu poata fi atribuite altor clase. O forma complexa este descrisa printr-un ansamblu ierarhizat de subforme cu un numar din ce in ce mai redus de caracteristici.
In ultimul timp au fost realizate sisteme evoluate reprezentind dezvoltarea de modele organizate dupa principiul sistemului nervos uman si care tind sa aibe performante comparabile cu acestea. Aceste modele sint alcatuite din elemente de calcul neliniare, lucrind in paralel, interconectate astfel sa formeze retele asemanatoare cu cele umane, primind astfel denumirea de retele neuronale.
Desi elementele de prelucrare, "neuronii", pot efectua numai operatii simple, performantele deosebite ale retelei se bazeaza pe gradul mare de interconectare ale acestora. Realizarea unor asemenea modele are la baza dezvoltarea de noi algoritmi si tehnici de implementare VLSI, dar functionarea acestora poate fi simulata si pe calculatoare conventionale, in care elementele de prelucrare si schemele de interconectare sint reprezentate in software prin adrese de memorie, rutine de prelucrare si tabele dictionar.
In problema recunoasterii de forme exista trei faze distincte:
-achizitia de date analogice si conversia in date digitizate;
-extragerea de caracteristici din datele achizitionate;
-clasificarea datelor prin aceste caracteristici.
3.2 METODE DECIZIONALE
Fiecare forma trebuie considerata ca reprezentind o variabila in spatiul n-dimensional, in care fiecare caracteristica este asignata la o dimensiune. Astfel o forma x apare ca un punct in spatiul de forme:
│ x1 │
│ x2 │
x = │ : │
│ xn │
Dupa ce caracteristicile au fost extrase din obiectele fizice, vectorii de forma trebuie plasati in spatiul formelor, atribuindu-se claselor distincte prin intermediul unui clasificator.
Este necesar sa se 313f519d determine o functie care separa doua clase, sau o serie de functii care separa trei sau mai multe clase. Asemenea functii se numesc functii de decizie.
In cazul bidimensional aceste functii sint liniare si se reprezinta sub forma:
x1-mx2-b=0 sau w1x1+w2x2+w3=0
unde w1=1, w2=-m, w3=-b.
In cazul n-dimensional, functiile de decizie sint hiperplanuri de forma:
d(x)=w1x1+w2x2+...+wnxn+wn+1=0
Aceasta ecuatie poate fi scrisa vectorial sub forma:
d(x) = w'x = 0
Pentru cazul a doua clase, polaritatea lui d(x) determina carei clase apartine o forma data x. Pentru clasificare multicategoriala sint necesare mai multe functii de decizie.
Clasificatorii multicategoriali pot fi de trei tipuri : I, II si III (figura 3.2.1).
Un clasificator multicategorial de tip I considera o clasa oi si toate celelalte clase ca formind o a doua clasa, pentru care se utilizeaza o functie de decizie di. Pentru n clase vor exista astfel n functii de decizie. O forma data xεoi daca si numai daca di(x)>0 si dj(x)<0 pentru i╪j.
Clasificatorul de tip II consta in separarea de perechi care necesita functii de decizie ce separa doua clase la un moment dat. Separarea claselor oi si oj necesita o functie de decizie dij(x)=0. Forma xεoi daca si numai daca dij(x)>0.
Clasificatorul de tip III este un caz special al tipului II, modificat astfel incit orice punct din spatiul formelor este asignat la o clasa data. In clasificatorii anteriori orice punct din triunghiul format de cele trei linii nu poate fi clasificat. Eliminarea acestei regiuni de nedeterminare se realizeaza prin functia de decizie di(x)-dj(x)=0 unde di si dj sint fuctii de decizie ale clasificatorului de tip I. Criteriul de asignare a unei forme x la clasa oi este di(x)-dj(x)>0 pentru orice j╪i.
In spatiul formelor, utilizind o functie de decizie n-dimensionala (hiperplan) se poate realiza clasificarea formelor in doua clase. Este necesar sa se 313f519d determine punctele reprezentind valorile tipice ale fiecarei clase (centrii grupului), prin medierea valorilor punctelor dintr-un grup:
N
z = 1/N Σ xi
i=1
Figura 3.2.1. Clasificatorii mlticategoriali de tip I, tip II si tip III.
Ca o masura a similaritatii unui punct fata de centrul grupului este distanta euclidiana, aceasta abordare a procesului de clasificare fiind cunoscuta sub numele de clasificare dupa distanta minima. Astfel distanta unei forme date x fata de centrul z se calculeaza cu relatia:
n
D = ║x-z║ = ( Σ(xi-zi)2 )1/2
i=1
Din aceasta categorie de metode de clasificare nesupervizata fac parte o serie de algoritmi cum sint: algoritmul de prag, algoritmul de distanta maxmin, algoritmul de grupare general.
Algoritmul de prag considera primul vector de forma x1 ca fiind primul centru de grup z1. Apoi pentru fiecare forma noua se calculeaza distantele fata de toti centrii de grup, care daca sint mai mari decit o valoare de prag, aceasta este asignata ca centru de grup pentru o noua clasa.
Algoritmul de prag.
citeste x1
*asigneaza x1 ca centru de grup z1
┌pentru i=2,N executa
│ citeste xi
│ *calculeaza distantele Dk fata de toti centrii de grup
│ ┌daca Dk<T atunci
│ │ *asigneaza xi la clasa ok
│ │altfel
│ │ *creeaza un nou centru de grup zj=xi
│ └n
│stop
└n
Deoarece rezultatele algoritmului sint afectate de ordinea introducerii vectorilor de forma este necesar ca la inceput sa fie furnizati acei vectori care reprezinta cu aproximatie centrii de grup. De asemenea valoarea de prag influenteaza rezolutia clasificarii: daca se alege o valoare prea mare atunci este posibil ca doua clase distincte sa fie grupate intr-una singura.
Algoritmul de distanta maxmin este o imbunatatire a celui precedent si utilizeaza distanta euclidiana. Initial se alege un vector de forma asignat ca centru de grup z1 iar punctul cel mai indepartat de acesta este asignat ca al doilea centru z2. Restul punctelor sint clasificate in cele doua clase utilizind un clasificator de distanta minima. In continuare, din fiecare clasa cel mai indepartat punct de centru este asignat ca centru de grup nou daca distanta sa fata de centru este mai mare decit distanta medie a celorlalte puncte din grup fata de centru. Procedura este repetata ori de cite ori apare un centru nou. Algoritmul se opreste cind numarul de centre nu se modifica.
Algoritmul distanta maxmin.
citeste x1
*asigneaza x1 ca centru de grup z1
┌repeta
│ atribuie CLAS adev
│ ┌pentru i=2,N executa
│ │ *calculeaza toate distantele Dk pentru xi
│ │ *asigneaza xi la clasa cu Dk minim
│ └n
│ ┌pentru k=1,M executa
│ │ *calculeaza distanta medie Dmk
│ │ *selecteaza xi cu Dk maxim
│ │ ┌daca Dk>Dmk/2 atunci
│ │ │ *asigneaza xi nou centru de grup
│ │ │ atribuie CLAS fals
│ └n └n
│pina CLAS
└n
stop
Si in cazul acestui algoritm alegerea primului centru de grup influenteaza clasificarea care urmeaza. De asemenea, selectarea punctului cel mai indepartat poate introduce erori, caci acesta poate fi afectat de zgomot.
Algoritmii prezentati in paragraful precedent sint algoritmi nesupervizati, deoarece clasele unui set dat de forme sint determinate chiar de algoritm. O alta abordare consta in utilizarea unui algoritm caruia sa i se furnizeze un set de vectori de forma cunoscuti, ce vor fi clasificati intr-un mod convenabil, iar apoi sa se utilizeze algoritmul pentru clasificarea unor vectori necunoscuti.
In aceasta idee, algoritmul perceptron, determina vectorul de pondere w pentru N functii de decizie, care clasifica corect N vectori de incercare cunoscuti, in doua clase o1 si o2. Astfel pentru un vector xi:
xi w > 0 => xi ε o1
xi w < 0 => xi ε o2
Setul de forme de incercare poate fi reprezentat sub forma unei matrici X, in care vectorii de forma pentru care xiw<0, au fost multiplicati cu -1. Scopul algoritmului este sa gaseasca un vector pondere w care satisface conditia Xw>0.
Algoritmul perceptron.
*initializeaza w
┌repeta
│ atribuie READY adev
│ ┌pentru i=1,N executa
│ │ atribuie d(xi) xi w
│ │ ┌daca d(xi)<0 atunci
│ │ │ *modifica w
│ │ │ atribuie READY fals
│ └n └n
│pina READY
└n
stop
Cind algoritmul gaseste pentru un vector x, d(x)>0, vectorul pondere w nu este modificat, trecindu-se la vectorul urmator. Daca insa d(x)<0 atunci w va fi corectat utilizind un coeficient pozitiv de corectie c. La iteratia k+1:
┌ w(k) daca w(k)x>0
w(k+1) =│
└ w(k)+cx daca w(k)x
La urmatoarea iteratie w va fi mai aproape de valoarea corecta, chiar daca d(x) 0, pentru ca:
d(x) = w(k+1)x = (w(k)+cx)x = w(k)x+cxx
Acest nou d(x) este mai mare decit cel precedent, care este egal cu primul termen w(k)x. Al doilea termen este pozitiv pentru c>0, deci algoritmul va converge.
RETELE NEURONALE
O retea neuronala se poate descrie prin patru parametrii de baza:
-elementele de prelucrare ("neuronii");
-schema de interconectare intre elemente;
-legea de invatare;
-domeniul aplicatiei.
Elementele de prelucrare utilizate in retele neuronale sint neliniare, de obicei analogice si pot realiza o suma ponderata pentru cele N intrari, trecind rezultatul printr-o functie neliniara, cum sint functia treapta, functia rampa sau functia sigmoidala.
Daca x0,x1,...,xN-1 sint intrarile intr-un element de prelucrare, iar w0,w1,...,wN-1 sint ponderile corespunzatoare, atunci iesirea generata este data de relatia:
N-1
y = f(Σwi*xi-Θ)
i=0
unde f este functia ce caracterizeaza neliniaritatea atasata elementului de prelucrare, iar Θ este o valoare de prag (figura 3.4.1). Elementele de prelucrare sint puternic interconectate formind retele dupa modelul sistemului nervos uman. Un avantaj deosebit fata de sistemele de calcul conventionale il reprezinta ca defectarea citorva elemente de prelucrare sau conexiuni nu degradeaza in mod semnificativ performantele retelei.
Invatarea sau adaptarea reprezinta o caracteristica de baza a retelelor neuronale. Aceasta operatie are loc prin preluarea repetitiva de intrari apartinind unor clase cunoscute. Caracteristicile acestora sint memorate sub forma de valori, ce sint utilizate apoi ca ponderi pentru intrarile urmatoare necunoscute. De asemenea, majoritatea algoritmilor pot modifica ponderile asociate conexiunilor dintre noduri, pe baza rezultatelor obtinute, in vederea cresterii performantelor.
Figura 3.4.1. Element de prelucrare.
Exista diferite tipuri de paradigme, unele cu utilizari practice in recunoasterea de forme. Modul de operare a unei retele neuronale pentru clasificarea de forme este prezentat in figura 3.4.2. Valorile de intrare sint trimise in paralel catre primul segment, prin intermediul a N intrari de conexiune. Aceste valori pot fi situate pe unul din doua nivele (+1 si -1) pentru imagini binare, sau pot apartine unei multimi mai largi de valori pentru imagini cu mai multe nivele de gri. Primul segment calculeaza scorurile de coincidenta si furnizeaza in paralel aceste scoruri prin M linii corespunzatoare celor M clase. Al doilea segment are M iesiri, notate y0,y1,...,yM-1, corespunzatoare celor M clase. Acest segment selecteaza valoarea maxima de la intrare si o intensifica, activind iesirea clasei careia ii corespunde forma de la intrare, toate celelalte iesiri raminind inactive. In cazul unor retele, iesirile furnizate, daca sint corecte, sint trimise catre primul segment pentru adaptarea ponderilor pe baza unui algoritm de invatare, in vederea imbunatatirii performantelor.
Figura 3.4.2. Clasificarea de forme utilizand o retea neuronala.
O retea neuronala, cum este cea din figura 3.4.2, poate executa trei tipuri de prelucrari:
-identificarea clasei din care face parte o forma de intrare afectata de zgomot;
-utilizarea ca memorie adresabila dupa continut (memorie asociativa), in care se furnizeaza ca intrare o forma reprezentind o anumita cheie si se genereaza la iesire informatia atasata (aplicabilitate in sistemele de regasire a informatiei cind se cunoaste numai o parte din aceasta);
-cuantizarea de vectori, aplicatie in care N elemente de intrare sint repartizate in M clase (aplicabilitate in sisteme de transmisie de informatie, in care cantitatea de informatie este comprimata fara sa se piarda detalii semnificative).
Retelele neuronale se pot clasifica dupa un prim criteriu reprezentat prin numarul de valori de intrare. Un alt criteriu il reprezinta modul de realizare al operatiei de invatare, retelele clasificindu-se in retele supervizate si nesupervizate. Citeva retele neuronale clasice sint prezentate in tabelul urmator:
│ intrari binare │ intrari valori continue
supervizate │ Hopfield │ Perceptron
│ Hamming │ Perceptron multinivel
nesupervizate │Carpenter/Grossberg│ Kohonen
Structura unei retele Hopfield este prezentata in figura 3.4.3. Este utilizata pentru prelucrarea de imagini binare, de exemplu recunoasterea de caractere scrise.
m m . . . mN-2 mN-1
x0 x1 . . . xN-2 xN-1
Figura 3.4.3. Reteaua neuronala de tip Hopfield.
Reteaua contine un set de N elemente de prelucrare, ce implementeaza o functie de tip treapta. Intrarile si iesirile pot lua una din valorile +1 si -1. Iesirea fiecarui nod este conectata la toate celelalte noduri prin intermediul unor ponderi notate ti,j cu i,j=0,1,...,N-1.
Algoritmul de functionare al unei retele Hopfield se desfasoara conform urmatorilor pasi:
1) Asignarea ponderilor conexiunilor:
N-1
ti,j = Σ xi(s)xj(s) pentru i╪j
s=0
ti,j = 0 pentru i=j, 0 i,j M-1
2) Initializarea nodurilor cu forma de intrare necunoscuta:
μi = xi 0 i N-1
3) Iteratie pina la convergenta:
N-1
μi(t+1) = f(Σ ti,jμi(t)) 0 i M-1
i=0
unde:
ti,j : ponderea conexiunii intre nodul i si nodul j;
xi(s) : poate lua una din valorile +1 si -1 si reprezinta componenta i a exemplarului apartinind clasei s;
μi(t) : poate lua una din valorile +1 si -1 si reprezinta valoarea iesirii nodului i la momentul de timp t;
xi : poate lua una din valorile +1 si -1 si reprezinta componenta i a exemplarului necunoscut de la intrarea retelei;
f : reprezinta functia de neliniaritate de tip treapta.
Pasul trei al algoritmului se repeta pina cind iesirile nodurilor ramin neschimbate la o noua iteratie. Iesirile nodurilor reprezinta in acest moment exemplarul de forma de care este cea mai apropiata intrarea necunoscuta. Hopfield a aratat ca aceasta retea converge atunci cind ponderile sint simetrice (ti,j=tj,i), iar starile nodurilor sint actualizate asincron utilizind ecuatiile algoritmului.
Reteaua Hopfield prezinta citeva avantaje majore:
-numarul de forme care pot fi memorate si apelate este limitat. Daca acest numar este prea mare reteaua poate converge catre o forma falsa, diferita de toate celelalte memorate.
-numarul de clase este mentinut sub 0.15*N (N fiind numarul de noduri). Astfel, o retea pentru 10 clase, necesita 70 de noduri si aproximativ 5000 de conexiuni).
-un exemplar de forma poate fi instabil daca prezinta mai multi biti in comun cu un alt exemplar (fiind aplicat la intrarea retelei la momentul zero, reteaua converge catre un alt exemplar).
In numeroase aplicatii, de exemplu transmiterea la distanta a imaginilor digitale, apar erori cu o anumita probabilitate, constind in complementarea unor biti. Pentru determinarea clasei din care face parte un exemplar oarecare, se calculeaza distanta Hamming fata de toate clasele, selectindu-se clasa avind distanta minima. Distanta Hamming este numarul de biti prin care difera un exemplar de cel reprezentativ al clasei. O retea neuronala care implementeaza acest concept este prezentata in figura 3.4.4 si poarta numele de retea Hamming.
Algoritmul de functionare al retelei Hamming consta din urmatorii pasi:
1) Initializarea ponderilor conexiunilor si valorilor de prag:
1.a) in subreteaua inferioara:
wi,j = xi(j)/2
Θj = N/2 0 i N-1, 0 j M-1
1.b) in subreteaua superioara:
tk,l = 1 pentru k=l
tk,l = ε pentru k╪l, ε<1/M
0 k,l M-1
2) Initializarea nodurilor cu forma de intrare necunoscuta:
N-1
μj(0) = f(Σ wi,jxi-Θ) 0 j M-1
i=0
3) Iteratie pina la convergenta:
μj(t+1) = f(μj(t)-εΣ μk(t)) 0<j,k<M-1
k╪j
unde:
wi,j : ponderea conexiunii intre intrarea i si nodul j din reteaua inferioara;
Θj : valoarea de prag a nodului j din subreteaua inferioara;
tk,j : ponderea conexiunii de la nodul k la nodul j din subreteaua inferioara (in aceasta subretea toate valorile de prag sint zero);
xi(j) : elementul i al exemplarului reprezentativ al clasei j;
μj(t) : iesirea nodului j din subreteaua superioara la momentul de timp t;
xi : elementul i al exemplarului necunoscut furnizat la momentul initial la intrarea retelei;
f : functia de neliniaritate de tip rampa (se poate presupune ca valoarea maxima ce se poate furniza nu produce saturarea valorii functiei).
m m . . . mN-2 mN-1 subretea
superioara
Figura 3.4.4. Reteaua neuronala de tip Hamming.
Iteratia de la pasul 3 al algoritmului se continua pina cind iesirea unui singur nod al subretelei superioare este pozitiva, toate celelalte fiind zero. In acest moment procesul de clasificare s-a incheiat, exemplarul de la intrare apartinind clasei cu iesirea pozitiva. Se poate demonstra ca reteaua Hamming va converge intotdeauna daca ε<1/M.
Reteaua Hamming prezinta o serie de avantaje fata de reteaua Hopfield:
-implementeaza clasificatorul de distanta minima, in aplicatii unde erorile de bit sint aleatoare si independente, in care reteaua Hopfield obtine performante mai scazute sau cel mut egale;
-necesita mult mai putine conexiuni. De exemplu o retea Hamming cu 100 de intrari si 10 clase necesita numai 1100 de conexiuni, in timp ce o retea Hopfield aproape 10000. Aceasta diferenta se mareste o data cu cresterea numarului de intrari, deoarece la reteaua Hamming numarul de conexiuni este direct proportional cu numarul de intrari, in timp ce la reteaua Hopfield este proportional cu patratul numarului de intari.
Reteaua Carpenter/Grossberg este utilizata pentru obtinerea de clase, operatia de invatare executindu-se fara supervizare. Algoritmul implementat selecteaza un prim element pe care il asigneaza ca element reprezentativ al primei clase. Urmatorul element este adaugat la prima clasa daca distanta fata de exemplarul reprezentativ este mai mica decit o anumita valoare de prag. Altfel este asignat ca exemplar reprezentativ pentru o noua clasa. Acest proces este repetat pentru toate intrarile urmatoare. Astfel numarul de clase creste in timp si depinde de o serie de factori cum sint valoarea de prag, tipul de distanta folosita, ordinea elementelor.
Organizarea unei retele Carpenter/Grossberg este reprezentata in figura 3.4.5, in care sint reprezentate nodurile pentru trei intrari si doua iesiri. Structura este asemanatoare cu cea a retelei Hamming. Scorurile de coincidenta sint calculate utilizind conexiunile directe, iar selectarea valorii maxime se realizeaza prin inhibitie laterala intre nodurile de iesire. Diferenta fata de o retea Hamming consta in conexiunile de reactie de la nodurile de iesire la nodurile de intrare.
Algoritmul de functionare al retelei Carpenter/Grossberg este prezentat in continuare:
1) Initializari:
ti,j(0) = 1
bi,j(0) = 1/(1+N) 0 i N-1, 0 j M-1
seteaza δ 0
2) Se aplica un nou element la intarea retelei;
3) Se calculeaza scorurile de coincidenta:
N-1
μj = Σ bi,j(t)xi 0 j M-1
i=0
4) Se selecteaza exemplarul cu scor maxim:
μj* = max
j
5) Test de vigilenta:
N-1
║X║ = Σ xi
i=0
N-1
║T X║= Σ ti,j*xi
i=0
Daca ║T X║/║X║>δ atunci treci la pas 7
altfel treci la pas 6.
6) Dezactiveaza nodul cu scor maxim (setat la zero, neparticipind in continuare la operatia de maximizare de la pasul 4). Se trece la pas 3.
7) Adapteaza exemplarul cu scor maxim:
ti,j*(t+1) = ti,j*(t)xi
N-1
bi,j*(t+1) = (ti,j*(t)xi)/(0.5+Σti,j*(t)xi)
i=0
8) Activeaza toate nodurile dezactivate la pasul 6. Se trece la pasul 2.
In cadrul descrierii algoritmului au fost utilizate urmatoarele notatii:
ti,j(t): ponderea conexiunii inapoi intre nodul de intrare i si nodul de iesire j, la momentul t;
bi,j(t) : ponderea conexiunii inainte intre nodul de intrare i si nodul de iesire j, la momentul t (aceste ponderi definesc exemplarul specificat la nodul de iesire j);
δ : pragul de vigilenta, care indica cit trebuie sa fie de aproape o intrare de un exemplar memorat pentru a coincide;
μj : iesirea nodului de iesire j;
xi : elementul i al intrarii (care poate fi zero sau 1).
y0 y1
x0 x1 x2
Figura 3.4.5. Reteaua neuronala de tip Carpenter/Grossberg.
Algoritmul incepe cu initializarea ponderilor conexiunilor intre noduri si cu setarea valorii pragului de vigilenta, cuprinsa intre 0.0 si 1.0, determinind cit de aproape trebuie sa fie un exemplar de intrare memorat pentru a fi considerat ca facind parte din aceeasi clasa. O valoare invecinata de 1.0 necesita o apropiere strinsa intre cele doua exemplare.
In continuare la intrarea retelei se furnizeaza in mod secvential, intrari ce urmeaza sa fie clasificate. O intrare urmeaza sa fie comparata cu toate exemplarele memorate si se calculeaza scorurile de coincidenta, selectindu-se clasa cu scorul maxim. Exemplarul reprezentativ al clasei cu scor maxim, este comparat cu intrarea, calculind raportul intre produsul scalar al exemplarului de la intrare si al exemplarului clasei (numarul de biti 1 in comun), impartit la numarul de biti 1 din exemplarul de la intrare. Daca acest raport este mai mare decit pragul de vigilenta, atunci intrarea este considerata similara cu exemplarul avind cea mai buna coincidenta, acesta fiind apoi actualizat, realizind o operatie logica AND intre bitii sai si cei ai exemplarului de la intrare. Daca raportul este mai mic decit valoarea de prag, atunci intrarea este considerata diferita de toate exemplarele si este considerata ca reprezentind o noua clasa. Fiecare nou exemplar adaugat necesita un nod si 2N conexiuni pentru a se calcula scorurile de coincidenta
|
