sisteme computationale inteligente

104
Sisteme computaţionale inteligente Versiunea 33 Ph.D. Lucian Sasu 4 martie 2015

Upload: maria

Post on 22-Dec-2015

67 views

Category:

Documents


8 download

DESCRIPTION

SCI

TRANSCRIPT

Page 1: Sisteme Computationale Inteligente

Sisteme computaţionale inteligente

Versiunea 33

Ph.D. Lucian Sasu

4 martie 2015

Page 2: Sisteme Computationale Inteligente

Cuprins

1 Introducere 41.1 Reţele neurale . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 Bazele biologice . . . . . . . . . . . . . . . . . . . . . . 61.1.2 Diferenţe între RN artificiale şi naturale . . . . . . . . 81.1.3 Aplicabilitate . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Calcul evoluţionist . . . . . . . . . . . . . . . . . . . . . . . . 91.2.1 Bazele biologice . . . . . . . . . . . . . . . . . . . . . . 91.2.2 Cromozomi . . . . . . . . . . . . . . . . . . . . . . . . 101.2.3 Diferenţe între cromozomii biologici şi cei artificiali . . 101.2.4 Aplicabilitate . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Sistemele fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4 Tipuri de învăţare în inteligenţa computaţională . . . . . . . . 11

1.4.1 Învăţarea supervizată . . . . . . . . . . . . . . . . . . . 121.4.2 Învăţarea prin întărire . . . . . . . . . . . . . . . . . . 121.4.3 Învăţarea nesupervizată . . . . . . . . . . . . . . . . . 13

1.5 Auto-organizarea . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Regresia liniară 152.1 Exemplu, notaţii . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Funcţia de cost . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Metoda de căutare după gradient . . . . . . . . . . . . . . . . 202.4 Metoda algebrică pentru minimizarea funcţiei de eroare . . . . 21

3 Reţele neurale artificiale - fundamente 253.1 Încadrarea domeniului . . . . . . . . . . . . . . . . . . . . . . 253.2 Neuronul biologic . . . . . . . . . . . . . . . . . . . . . . . . . 273.3 Modele de neuroni artificiali . . . . . . . . . . . . . . . . . . . 28

3.3.1 Modelul McCulloch–Pitts . . . . . . . . . . . . . . . . 283.3.2 Modelarea neuronului pentru sisteme neurale artificiale 29

3.4 Modele de reţea neurală artificială . . . . . . . . . . . . . . . . 313.4.1 Reţea cu propagare înainte . . . . . . . . . . . . . . . . 31

1

Page 3: Sisteme Computationale Inteligente

3.4.2 Reţele cu conexiune inversă . . . . . . . . . . . . . . . 323.5 Învăţarea ca problemă de aproximare . . . . . . . . . . . . . . 343.6 Reguli de învăţare . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.6.1 Regula de învăţare Hebbiană . . . . . . . . . . . . . . . 363.6.2 Regula de învăţare a perceptronului . . . . . . . . . . . 373.6.3 Regula de învăţare delta . . . . . . . . . . . . . . . . . 373.6.4 Regula de învăţare Widrow-Hoff . . . . . . . . . . . . . 383.6.5 Regula de învăţare prin corelaţie . . . . . . . . . . . . 383.6.6 Regula “câştigătorul ia tot” . . . . . . . . . . . . . . . 38

4 Perceptroni monostrat 40

5 Perceptroni multistrat 41

6 Memorii asociative bidirecţionale 426.1 Distanţa Hamming . . . . . . . . . . . . . . . . . . . . . . . . 426.2 Asociatori liniari . . . . . . . . . . . . . . . . . . . . . . . . . 436.3 Memoria asociativă bidirecţională . . . . . . . . . . . . . . . . 446.4 Funcţia de energie a MAB . . . . . . . . . . . . . . . . . . . . 476.5 Capacitatea de memorie . . . . . . . . . . . . . . . . . . . . . 48

7 Fuzzy ARTMAP 497.1 Învăţarea incrementală . . . . . . . . . . . . . . . . . . . . . . 497.2 Proprietăţi dezirabile ale sistemelor instruibile . . . . . . . . . 497.3 Dilema stabilitate-plasticitate . . . . . . . . . . . . . . . . . . 507.4 Fuzzy ARTMAP . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.4.1 Structura reţelei FAM . . . . . . . . . . . . . . . . . . 527.4.2 Algoritmul de învăţare pentru FAM . . . . . . . . . . . 54

8 Reţele neurale cu funcţii de activare radială 618.1 Teorema lui Cover pentru separabilitate . . . . . . . . . . . . 618.2 Funcţii cu activare radială . . . . . . . . . . . . . . . . . . . . 628.3 Reţele cu funcţii cu activare radială . . . . . . . . . . . . . . . 658.4 Clustering folosind algoritmul K-means . . . . . . . . . . . . . 678.5 Determinarea ponderilor . . . . . . . . . . . . . . . . . . . . . 708.6 Algoritmul de instruire a reţelei RBF . . . . . . . . . . . . . . 70

9 Reţele neurale cu auto-organizare 72

2

Page 4: Sisteme Computationale Inteligente

10 Calcul evoluţionist 7310.1 Clasificare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7310.2 Algoritmi genetici . . . . . . . . . . . . . . . . . . . . . . . . . 7410.3 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . . . . 7710.4 Problema reprezentării datelor în algoritmii genetici . . . . . . 80

10.4.1 Varianta cu penalizare . . . . . . . . . . . . . . . . . . 8310.4.2 Varianta cu reparare . . . . . . . . . . . . . . . . . . . 8310.4.3 Codificarea adecvată a indivizilor . . . . . . . . . . . . 84

10.5 Exemplu: problema orarului . . . . . . . . . . . . . . . . . . . 85

11 Sisteme fuzzy 8811.1 Prezentare generală . . . . . . . . . . . . . . . . . . . . . . . . 8811.2 Teoria mulţimilor fuzzy . . . . . . . . . . . . . . . . . . . . . . 8911.3 Operaţii cu mulţimi fuzzy . . . . . . . . . . . . . . . . . . . . 91

11.3.1 Egalitatea mulţimilor fuzzy . . . . . . . . . . . . . . . 9211.3.2 Incluziunea mulţimilor fuzzy . . . . . . . . . . . . . . . 9211.3.3 Complementara unei mulţimi fuzzy . . . . . . . . . . . 9311.3.4 Intersecţia a două mulţimi fuzzy . . . . . . . . . . . . . 9311.3.5 Reuniunea a două mulţimi fuzzy . . . . . . . . . . . . . 9411.3.6 Operatori de compensare . . . . . . . . . . . . . . . . . 94

11.4 Reguli fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9511.5 Măsuri ale gradului de nuanţare . . . . . . . . . . . . . . . . . 98

12 Reţele neuro-fuzzy 101

3

Page 5: Sisteme Computationale Inteligente

Capitolul 1

Introducere

Inteligenţa computaţională (IC) este un domeniu care combină elementede învăţare automată, adaptare, evoluţie şi logică fuzzy pentru a rezolvaprobleme care, abordate tradiţional, sunt dificil sau imposibil de abordat.Este o ramură a inteligenţei artificiale. Subdomeniile majore ale inteligenţeicomputaţionale sunt:

• reţele neurale artificiale1;

• sisteme fuzzy

• calcul evoluţionist

• sisteme imune artificiale

• inteligenţa muşuroiului

Fiecare din aceste subdomenii a evoluat rapid şi s–au impus ca potenţialemetode de rezolvare efectivă a unor probleme complexe şi presante, pen-tru care abordările uzuale sunt nefructuase. De regulă, prototipizarea unuisistem inspirat din inteligenţa computaţională este rapidă, iar pentru o pro-blemă se pot folosi mai multe abordări: de exemplu, optimizarea se poateface prin algoritmi genetici sau prin anumite familii de reţele neurale.

Metodele din inteligenţa computaţională (IC) sunt preponderent inspi-rate din biologie: reţelele neurale au pornit de la modelul imaginat pentruneuronul biologic, calculul evoluţionist este bazat pe teoria evoluţiei enun-ţată de Charles Darwin. Sistemele fuzzy sunt introduse pentru a permitemanipularea incertitudinii, altfel decât prin teoria probabilităţilor.

1Sau “neuronale”.

4

Page 6: Sisteme Computationale Inteligente

Este o mare diferenţă între abordarea clasică, algoritmică a unei problemeşi cea dată de IC. În primul caz este pusă la bătaie toată abilitatea celui careimaginează algoritmul pentru a rezolva problema; este un demers anevo-ios, depinzând esenţial de imaginaţia, puterea de abstractizare şi experienţapersoanei în cauză; evident, este un proces creativ, la ora actuală efectuatexclusiv de oameni. Totodată, de cele mai multe ori rezultatele sunt exacte;de asemenea, se are în vedere permanent mişorarea complexităţii de calcula problemei respective, dar în destule situaţii o soluţie exactă presupune unefort de calcul sau resurse de memorie prohibitive.

Abordarea IC este total diferită: pentru reţele neurale sau algoritmi ge-netici, definitorie este capacitatea de adaptare automată sau auto-organizarela condiţiile problemei. Este modelul inspirat din natură, unde un sistem bi-ologic preia semnale din mediu şi printr-un proces de învăţare se adaptează,astfel încât să îşi îndeplinească scopul, sau pentru a obţine o mai bună inte-grare. Soluţia la care se ajunge nu este neapărat optimă, dar este un răspunssuficient de bun pentru problema propusă. În implementarea unui sistemdin cadrul IC accentul cade mai mult pe abilitatea sistemului rezultat de ase adapta, de a învăţa, decât pe imaginaţia celui care îl concepe. Abilităţilede programare pentru implementarea sau personalizarea sistemului sunt însăesenţiale.

Sistemele propuse în cadrul IC sunt cu un mare grad de aplicabilitate.De exemplu, algoritmii genetici pot fi folosiţi pentru o clasă largă de funcţii,nedepinzând atât de mult precum cercetările operaţionale de ipoteze (ce potfi prea restrictive).

O definiţie a “inteligenţei” potrivită pentru contextul de IC este:

Definiţia 1 Inteligenţa este abilitatea unui sistem de a–şi adapta compor-tamentul pentru a–şi îndeplini scopurile în mediul său. Este o proprietatatea tuturor entităţilor ce trebuie să ia decizii şi al căror comportament estecondus de scop.

Definiţia de mai sus a fost dată în 1995 de către David Fogel, scoţând înevidenţă elementul esenţial al comportamentului inteligent şi în particular alinteligenţei computaţionale: adaptarea.

Reţelele neurale artificiale reprezintă grupuri interconectate de neuroniartificiali care au abilitatea de a învăţa din şi a se adapta la mediul lor, con-struind un model al lumii. Ele au apărut ca răspuns la modelarea activităţiicreierului biologic, precum şi ca răspuns al dorinţei de a obţine sisteme artifi-ciale capabile să recunoască şabloane. Exemple de reţele neurale şi algoritmide instruire se găsesc în [4], [5], [13].

Sistemele fuzzy sunt introduse pentru a putea gestiona imprecizia, no-ţiunile vagi (“înalt”, “acum”) şi aproximarea. Sunt elemente des întâlnite în

5

Page 7: Sisteme Computationale Inteligente

modelarea de limbaj sau în situaţii de cunoaştere incompletă. Teoria mulţi-milor fuzzy permite ca un element să aibă un anumit grad de apartenenţă(număr între 0 şi 1) la o mulţime, spre deosebire de teoria clasică a mulţi-milor. Logica fuzzy permite considerarea mai multor valori de adevăr decâtcele din logica clasică, sau altfel zis, a unor grade de adevăr diferite. Estevariantă de realizare a raţionamentului aproximativ.

Calculul evoluţionist se ocupă în special cu optimizarea şi de problemede căutare, bazate pe mecanismele preluate din genetică şi evoluţionism. Sepleacă de la ideea evoluţiei unei populaţii de indivizi, fiecare din ei fiind osoluţie potenţială a problemei ce se vrea rezolvată. Domeniul include algo-ritmii genetici, programarea evoluţionistă, programarea genetică şi strategiide evoluţie.

Sistemele rezultate prin inteligenţă computaţională pot reprezenta hi-bridizări ale celor de mai sus; de exemplu, există sisteme neuro-fuzzy, iarajustarea parametrilor pentru un sistem adaptiv se poate face prin algoritmigenetici. Alegerea uneltei potrivite pentru problema în cauză este o problemădeloc simplă, deoarece de regulă se pot folosi mai multe abordări.

1.1 Reţele neurale

1.1.1 Bazele biologice

Reţeaua neurală biologică a evoluat de-a lungul câtorva milenii, ajungândla performanţe care astăzi nu sunt accesibile calculatoarelor electronice: deexemplu, recunoaşterea de imagini, specifică animalelor; sau interpretareaecoului reflectat de către obstacole sau insecte, în cazul liliecilor - chiar dacăau creierul foarte mic, procesarea în cazul lor se face mai rapid decât pentrucele mai performante sisteme electronice actuale.

Studiile efectuate în ultimul secol au permis enunţarea unor prinicipiiasupra modului de funcţionare a sistemelor neurale biologice; suntem însădeparte de a cunoaşte toate detaliile funcţionale şi structurale. Chiar şiaşa, prin implementarea modelelor obţinute, rezultatele sunt mai mult decâtnotabile.

Figura 1.1 ([3]) reprezintă cel mai comun tip de neuron artificial. Înscoarţa neurală există un număr de 1010 neuroni interconectaţi, fiecare pu-tand avea pana la 104 conexiuni cu alţi neuroni; modul de grupare a acestoraşi interdependenţele nu sunt pe deplin cunoscute.

//TODO: referita de http://www.quora.com/What-would-you-add-to-current-Artificial-Neural-Network-to-resemble-more-of-Biological-Neural-Network +comentariu

6

Page 8: Sisteme Computationale Inteligente

Figura 1.1: Neuron natural [3]

Figura 1.2: Neuron de tip Purkinje din cortexul cerebelar,http://en.wikipedia.org/wiki/Neuron.

7

Page 9: Sisteme Computationale Inteligente

Un neuron artificial are o structură asemănătoare, adică reprezintă unelement de procesare conectat cu alte elemente, preia intrare de la nişte neu-roni şi ieşirea produsă este intrare pentru alţi neuroni, legăturile neurale suntnişte ponderi numerice, apare adaptarea reţelei neurale la mediu. Adapta-rea (sau învăţarea) este aspectul esenţial al reţelelor neurale: plecând de laseturi de date, se detectează automat şabloanele existente şi se construiescniste modele care pot fi folosite mai departe.

1.1.2 Diferenţe între RN artificiale şi naturale

În mod cert însă, există diferenţe: nu sunt modelate toate tipurile cunos-cute de neuroni; apoi, o lege biologică spune că un neuron poate să excitesau să inhibe un neuron cu care este conectat; în modelarea de RN artificiale,o pondere de legătură este fie excitatoare, fie inhibitoare, dar forma ei estefixată după ce s–a făcut învăţarea.

O altă diferenţă (şi punct de critică) este faptul că modelarea semnaluluifăcută sub formă de valori continue este de negăsit în reţelele biologice; înRN biologice se folosesc de fapt trenuri de impulsuri care sunt transmisecătre neuroni, apărând variaţie în frecvenţa semnalului. Acest aspect a fostabordat relativ târziu, în cadrul reţelelor neurale cu pulsuri.

Viteza reţelelor neurale este iarăşi un loc în care apar diferenţe. Se es-timează că neuronii naturali au o cicli de timp între 10 şi 100 milisecunde;implementările de RN artificiale funcţionează pe procesoare de câtiva gi-gahertzi, deci mai puţin de o nanosecundă. Chiar şi aşa, reţelele neuralebiologice sunt cu mult mai performante decât cele artificiale.

Altă diferenţă este că neuronii naturali sunt grupaţi în cantităţi mari,uneori de sute de milioane de unităţi. Se ajunge astfel la un grad de parale-lism masiv, ce nu poate fi atins în simulările artificiale.

1.1.3 Aplicabilitate

• Clasificarea - pe baza unui set de date de forma (intrare - ieşire asoci-ată) se construieşte un sistem care detectează asocierile dintre datelede intrare şi etichetele ce le sunt asociate; etichetele - sau clasele -sunt dintr-o mulţime discretă, finită. Clasificarea se foloseşte pentrurecunoaşterea automată a formelor, recunoaşterea vorbirii, diagnozămedicala şi altele.

• Regresie - asemănător cu clasificarea, dar ieşirile nu sunt dintr-o mul-ţime discretă şi finită, ci valori numerice continue;

8

Page 10: Sisteme Computationale Inteligente

• Memorie asociativă, sau memorie adresabilă prin conţinut - se poateregăsi o dată pe baza unei părţi a ei. Este un mecanism diferit de modulîn care calculatoarele regăsesc informaţia - pe baza adreselor sau a uneicăutări - dar apropiată de modul în care se face regăsirea elementelorreţinute de către o persoană.

• Grupare - pe baza similarităţilor existente într–un set de date, se de-tectează grupările de date; elementele dintr-un grup sunt mai apropiateîntre ele decât de altele din alt grup;

• Controlul sistemelor - folosite pentru cazul în care un proces trebuie săfie ghidat pentru a se încadra în parametri; utilitatea reţelelor neuraleprovine din faptul că nu se presupune că există dependenţe liniare întreacţiune şi reacţiune.

1.2 Calcul evoluţionist

Principalele paradigme2 ale calculului evoluţionist sunt:

• algoritmii genetici - evoluţia unei populaţii de indivizi (cromozomi),folosind selecţia, încrucişarea şi mutaţia;

• programarea evoluţionistă - similar cu precedenta, dar fără a folosiîncrucişarea; este văzută ca evoluţia de specii diferite, între care nuexistă hibridizări;

• strategiile de evoluţie - similari cu algoritmii genetici, dar se foloseşterecombinarea în loc de încrucişare şi deseori alte metode de mutaţie

• programarea genetică - metode evolutive aplicate programelor de cal-culator.

1.2.1 Bazele biologice

Domeniile de inspiraţie sunt genetica şi teoria evoluţionistă. Geneticaexplică ereditatea, adică transmiterea caracterelor de la părinţi la urmaşi.Astfel, adaptarea obţinută în generaţiile anterioare este preluată de cătreurmaşi şi continuată. Codificarea caracteristicilor este dată de cromozomi.

2“Paradigma este o construcţie mentală larg acceptată, care oferă unei comunităţi sauunei societăţi pe perioada îndelungată o bază pentru crearea unei identităţi de sine (aactivităţii de cercetare de exemplu) şi astfel pentru rezolvarea unor probleme sau sarcini.”,conform Wikipedia.

9

Page 11: Sisteme Computationale Inteligente

Noţiunile şi mecanismele sunt preluate din teoria eredităţii întemeiată deGregor Mendel şi teoria evoluţionistă a lui Charles Darwin.

1.2.2 Cromozomi

Cromozomii sunt structuri din interiorul celulelor care menţin informaţiagenetică. În cazul oamenilor, sunt 46 de cromozomi, jumătate moşteniţi dela tată şi jumătate de la mamă. Cromozomii sunt alcătuiţi din gene, fiecarefiind identificată prin locaţia pe care o ocupă şi prin funcţia asociată.

1.2.3 Diferenţe între cromozomii biologici şi cei artifici-ali

Cromozomii artificiali sunt reprezentări simplificate a celor biologici. Întimp ce neuronii biologici sunt secvenţe de acizi nucleici, cromozomii artifi-ciali sunt şiruri de cifre binare.

Cromozomii biologici care definesc organismele vii variază în lungime,chiar dacă de la un organism la altul din aceeaşi specie pentru un cromozomspecific lungimea este constantă. În algoritmii genetici, lungimea este fixă.

La reproducerea indivizilor dintr-o populaţie naturală, jumătate din infor-maţia genetică este preluată de la tată şi jumătate de la mamă. În algoritmiigenetici, procentul de combinaţie poate să difere.

1.2.4 Aplicabilitate

Principala arie de aplicare eeste optimizarea, pentru situaţiile în care că-utarea soluţiei cere un timp îndelungat. Algoritmii genetici sunt folositi cao metodă euristică; problemele abordate sunt din cele mai diverse — op-timizarea unui plan de lucru sau circuit, balansarea încărcării, optimizareaingredientelor, design automat, încărcarea containerelor, optimizarea struc-turilor moleculare, testarea mutaţiilor, optimizarea sistemelor de compresie,selectarea modelelor optime, găsirea defectelor hardware etc.

1.3 Sistemele fuzzy

Sistemele fuzzy şi logica fuzzy nu sunt de inspiraţie biologică, ci preluatedin partea comportamentală umană. Este o modalitate de manipulare aincertitudinii, modelând imprecizia, caracterul vag, ambiguitatea. Este vorbade un alt tip de incertitudine decât cel modelat prin intermediul variabileloraleatoare din cadrul teoriei probabilităţilor. Se foloseşte pentru modelarea

10

Page 12: Sisteme Computationale Inteligente

impreciziei lingvistice (“Maria e înaltă”, “Livrarea se face în aproximativ 3ore”). Teoria mulţimilor fuzzy a fost dezvoltată de către Lotfi Zadeh începândcu anul 1965.

Un exemplu de raţionament fuzzy este:

IF temperature IS very cold THEN stop fan

IF temperature IS cold THEN turn down fan

IF temperature IS normal THEN maintain level

IF temperature IS hot THEN speed up fan

Toate variantele sunt evaluate şi în funcţie de rezultat se ajustează vitezaventilatorului. Modelarea conceptelor de “very cold”, “normal” etc se faceprin mulţimi vagi.

Pornind de la acest curent, s-au dezvoltat următoarele: fuzzificare/de-fuzzificarea, sisteme de control fuzzy, jocuri fuzzy, matematică fuzzy, teoriamăsurii fuzzy, căutare fuzzy.

Teoria fuzzy este folosită intens în sisteme ce presupun control: camerevideo, sisteme de frânare sau accelerare, sisteme de control al debitului şipresiunii etc. De asemenea, sistemele expert din domeniu medical, financiar,navigaţional, diagnoza mecanica etc se folosesc masiv de suportul pentruimprecizie şi ambiguitate.

1.4 Tipuri de învăţare în inteligenţa computa-ţională

Învăţarea permite unui sistem să se adapteze la mediul în care operează;pe baza semnalelor provenite din exterior, sistemul inteligent îşi modificăparametrii pentru o îndeplinire cât mai bună a sarcinii propuse. Trebuiefăcută distincţia între “învăţare” şi “memorare cu regăsire exactă” – aceastădin urmă problemă este rezolvată de structuri şi baze de date.

Există trei tipuri principale de învăţare:

1. supervizată

2. nesupervizată

3. prin întărire

La acestea se adaugă şi învăţarea semi–supervizată.

11

Page 13: Sisteme Computationale Inteligente

1.4.1 Învăţarea supervizată

Se presupune că există un “profesor” care poate prezenta un set de date deinstruire având forma (intrare — ieşire asociată), relevant, care este preluatde către sistem şi învăţat. Se foloseşte o funcţie de eroare, care măsoară câtde departe este răspunsul cerut faţă de cel furnizat de sistem; pe baza eroriise desfăşoară un proces de ajustare a valorilor din sistemul computaţionalinteligent până când eroarea scade sub un anumit prag. Rezultatul final esteobtinerea unui sistem ce poate să furnizeze o valoare de ieşire adecvată pentruo anumită valoare de intrare ce nu este prezentă în setul de instruire.

Exemple de sisteme ce folosesc instruirea supervizată: perceptronul, per-ceptronul multistrat, Fuzzy ARTMAP, reţelele cu activare radială.

Figura 1.3: Schema de lucru pentru învăţare supervizată

1.4.2 Învăţarea prin întărire

Este similară cu învăţarea supervizată, numai că în loc de a se furnizaieşirea asociată unei intrări, se pune la dispoziţie o indicaţie care arată câtde bine a acţionat sistemul respectiv. Acesta este un sistem bazat pe cri-tică sau aprobare, fiind instruit în raport cu măsura în care ieşirea obţinutăde un sistem corespunde valorii dorite (dar fără ca această valoare dorităsă fie precizată sistemului!). Rolul profesorului este luat de un critic, careprecizează în ce măsură ieşirea obţinută se apropie de cea dorită. Pe termenlung, sistemul îşi va modifica propriul comportament astfel încât să se reducăcriticile obţinute.

12

Page 14: Sisteme Computationale Inteligente

Acest tip de învăţare este plauzibil din punct de vedere biologic, deoareceun animal va încerca să îşi minimizeze starea de disconfort prilejuită de com-portament neadecvat. Rolul criticului este dat aici de mediul înconjurător.Schema de lucru este dată în figura 1.4.

Figura 1.4: Schema de lucru pentru învăţare prin întărire

1.4.3 Învăţarea nesupervizată

Spre deosebire de precedentele moduri de învăţare, în acest caz nu seprimeşte niciun semnal de tip ieşire sau critică asociată. Sistemului capabilde grupare i se dau doar valori de intrare. El face o grupare automatăsau foloseşte o învăţare de tip competititiv. Aplicatiile clasice sunt analizaasociererilor, gruparea pe baza de similaritate si estimarea de densitate deprobabilitate.

Schema de lucru este dată în figura 1.5. Acest tip de adaptare este prezentîn reţelele de tip Self organizing feature maps sau Learning vector quantiza-tion.

13

Page 15: Sisteme Computationale Inteligente

Figura 1.5: Schema de lucru pentru învăţare nesupervizată

1.5 Auto-organizarea

Auto-organizarea, alături de învăţare, este un alt atribut important alsistemelor computaţionale inteligente. Este prezentă în sistemele naturale,de exemplu în creierul nou născuţilor, unde auto-organizarea se manifestăîn principal prin distrugerea legăturilor nefuncţionale. Auto-organizarea estedefinită astfel:

Definiţia 2 Spunem că un sistem se auto-organizează dacă, după ce se pri-mesc intrarea şi ieşirea unui fenomen necunoscut, sistemul se organizeazăsingur astfel încât să simuleze fenomenul necunoscut [2].

sau:

Definiţia 3 Sistemele cu auto-organizare se auto-organizează pentru a cla-sifica percepţiile din mediu în percepţii ce pot fi recunoscute, sau şabloane[2].

14

Page 16: Sisteme Computationale Inteligente

Capitolul 2

Regresia liniară

2.1 Exemplu, notaţii

Notă: expunerea din acest curs este făcută după [1].Regresia liniară este o metodă folosită pentru predicţia unei valori nume-

rice dintr-o mulţime infinită de posibilităţi. Ca exemplu, să presupunem căvrem să facem predicţia costului unei proprietăţi imobiliare, dată fiind su-prafaţa. Se cunosc date anterioare despre vânzarea unor astfel de proprietăţi.Pe baza acestor date vom construi o funcţie care să ne permită aproximareapreţului pentru alte suprafeţe de interes. O exemplificare este dată în figura2.1.

Figura 2.1: Reprezentarea datelor de vânzare a unor proprietăţi imobiliare.Pe abcisă este măsurată suprafaţa, pe ordonată este preţul [1].

15

Page 17: Sisteme Computationale Inteligente

Să presupunem că se doreşte estimarea valorii unei proprietăţi de supra-faţă 1300. Se poate proceda în felul următor: se trasează o dreaptă caresă aproximeze “cât mai bine”1 norul de puncte reprezentat2. Se constatăapoi care este valoarea de pe dreaptă, corespunzătoare lui 1300 (figura 2.2).Estimarea obţinută este de circa 220 mii USD.

1300

220

Figura 2.2: Aproximarea preţului pentru o suprafaţă de 1300 feet2.

Cu siguranţă se pot propune şi alte modele pentru predicţie. Cel discutataici este un model liniar:

pret = a · suprafata+ b

unde a şi b sunt coeficienţi reali ce pot fi determinaţi. Desigur, se pot folosiforme polinomiale de grad mai mare decât 1, sau modele liniare locale, saureţele neurale etc. Alegerea judicioasă a celui mai bun model pentru o pro-blema concretă este o problemă în sine. Folosirea unui model liniar se explicăprin faptul că e suficient de bun pentru o clasă largă de probleme abordate.

Avem mai sus un exemplu de instruire supervizată: se porneşte de laun set de date de forma valoare de intrare (suprafaţa) - valoare de ieşire(costul) şi se cere determinarea unui model care să fie folosit pentru prezicerea(aproximativă a) unor valori viitoare.

Formal, într–o problemă de regresie se dau:

1În sensul unei funcţii de eroare, vezi secţiunea 2.2.2Se arată în secţiunile următoare cum anume se construieşte dreapta, adică modul de

determinare a coeficienţilor ei. Pentru cazul cu mai multe date de intrare se obţine ovarietate liniară.

16

Page 18: Sisteme Computationale Inteligente

• m – numărul de date (cazuri, înregistrări) din setul de instruire; pentrudesenul din figura 2.1 este numărul de puncte roşii desenate;

• x(i) – variabilele (trăsăturile) de intrare, 1 ≤ i ≤ m; în exemplul dateste vorba de suprafaţă (un singur număr), dar în general pot fi maimulte trăsături, adică un vector de valori pentru fiecare caz. Li se maispune şi variabile predictive sau independente3;

• y(i) – variabila de ieşire (sau de predicţie, sau dependentă) este în cazulexemplificat un număr real (preţul), dar în general poate fi un vectorde valori. Ca mai sus, 1 ≤ i ≤ m.

O pereche din setul de antrenare se reprezintă prin (x(i),y(i)), 1 ≤ i ≤ m.Setul de antrenare se specifică frecvent sub formă tabelară, a se vedea

tabelul 2.1.

Suprafaţa Preţul (mii de dolari)2100 4501410 243800 188. . . . . .

Tabela 2.1: Set de date de instruire

Fluxul de lucru în învăţarea automată4 este dat în figura 2.3: se porneştede la un set de instruire, se aplică un algoritm de învăţare şi se produceun model. Din motive istorice acest model se mai numeşte şi ipoteză5 şi senotează de regulă cu h.

Acestui model i se furnizează o intrare (e.g. suprafaţa) şi modelul vacalcula o valoare de ieşire estimată (e.g. preţul). În notaţie formală avemecuaţia 2.1.

y = h(x) (2.1)

Una din întrebările esenţiale este: cum se reprezintă ipoteza h? Dupăcum am afirmat deja, există mai multe variante ce pot fi utilizate. Pentruexemplul de mai sus am pornit cu presupunerea că preţul creşte liniar cusuprafaţa în cauză, deci:

h(x) = hθ(x) = θ0 + θ1 · x (2.2)

3A nu se confunda cu noţiunea de independeţa liniară din algebră, sau independenţaevenimentelor sau a variabilelor aleatoare din teoria probabilităţilor.

4În limba engleză: învăţarea automată = machine learning.5În limba engleză: hypothesys.

17

Page 19: Sisteme Computationale Inteligente

Figura 2.3: Fluxul de lucru într-un proces de instruire automată.

unde θ = (θ0, θ1)t.

Acest model (ipoteză) se numeşte regresie liniară cu o variabilă, sau re-gresie liniară univariată. Se poate ca pe lângă suprafaţă – singura valoarede intrare considerată până acum – să se mai considere şi altele: distanţade la proprietate la cea mai apropiată autostradă, gradul de poluare a zoneietc.; în acest caz, modelul ar fi unul multivariat (mai multe valori de intrareconsiderate). Coeficienţii θ0 şi θ1 din ecuaţia 2.2 se mai numesc parametri aimodelului de predicţie.

2.2 Funcţia de cost

Există o infinitate de moduri în care se poate trasa dreapta din figura2.2; altfel zis, există o infinitate de modalităţi de alegere a coeficienţilor dinmodelul dat de ecuaţia 2.2.

Se pune problema: cum alegem aceşti coeficienţi? O variantă naturalăeste determinarea acestor coeficienţi de aşa manieră încât valorile prezisehθ(x

(i)) să fie cât mai apropiate de valorile cunoscute y(i), pentru tot setul deantrenare {(x(i), y(i))|1 ≤ i ≤ m}. Pentru toate valorile din setul de instruire,eroarea cumulată se poate măsura cu funcţia de cost

J(θ0, θ1) =1

2m

m∑

j=1

(

hθ(x(j))− y(j)

)2(2.3)

deci trebuie să găsim acele valori θ(min)0 , θ

(min)1 pentru care se atinge minimul

18

Page 20: Sisteme Computationale Inteligente

erorii cumulate:

θ(min)0 , θ

(min)1 = argmin

θ0,θ1J(θ0, θ1) = argmin

θ0,θ1

1

2m

m∑

j=1

(

hθ(x(j) − y(j)

)2(2.4)

Factorul m de la numitor apare pentru a calcula media erorii (altfel, eroa-rea ar creşte de fiecare dată când se adaugă în setul de instruire o pereche(x(i), y(i)) pentru care hθ(x

(i)) 6= y(i), în timp ce media reprezintă mai bineeroarea cumulată), iar numitorul 2 se utilizează pentru a uşura calculele ceurmează. Oricum, factorul 2m nu influenţează valorile parametrilor θ0, θ1.

Funcţia de eroare (sau “de cost”) J se mai numeşte şi funcţie de cost amodelului. Se pot folosi şi alte funcţii de cost, de exemplu incluzând relaţiiimpuse valorilor parametrilor θ. Funcţia de eroare pătratică (norma L2) esteo alegere populară pentru problemele de regresie, dar nu singura posibilă.

Pentru cazul în care θ0 = 0, se arată uşor că funcţia de eroare J(0, θ1) esteo funcţie de gradul 2, având minimul cel puţin zero. Pentru θ0, θ1 oarecareforma funcţiei de eroare este dată în figura 2.4 [1].

Figura 2.4: Funcţia de eroare pentru model liniar univariat, cu coeficienţioarecare [1].

O altă variantă de reprezentare grafică a funcţiei de eroare este pe bazacurbelor de contur: reprezentarea este plană, având pe cele două axe respectiv

19

Page 21: Sisteme Computationale Inteligente

pe θ0, θ1. Pentru o valoare oarecare a funcţiei de eroare se consideră mulţimeatuturor perechilor de parametri θ0, θ1 pentru care se obţine aceeasi valoare aerorii. Rezultatul este dat de o mulţime de curbe, precum cele reprezentateîn figura 2.5 [1]. Se poate arăta că aceste contururi sunt eliptice.

Figura 2.5: Curbe de contur pentru functia de eroare a unui model liniarunivariat [1].

2.3 Metoda de căutare după gradient

În această secţiune se va prezenta o metodă iterativă pentru minimizareafuncţiei de eroare J . Ideea este simplă:

• se porneşte cu valori θ0, θ1 iniţiale;

• se modifică în mod repetat valorile curente ale parametrilor de aşamanieră încât J să scadă.

Metoda se poate folosi pentru reducerea valorilor unei funcţii de oricâtevariabile. Menţinăm că se poate ajunge într-un minim local.

O variantă de modificare a valorilor curente a parametrilor este urmânddirecţia descendentă a derivatei lui J în punctul curent (θ0, θ1). Algoritmulare forma:

repeta{

θj := θj − α∂

∂θjJ(θ0, θ1), pentru j=0, 1 (2.5)

20

Page 22: Sisteme Computationale Inteligente

} pana la convergenta

Modificarea din interiorul ciclului trebuie să se facă simultan pentru toţiparametrii θj. Criteriul de convergenţă poate fi: de la o iteraţie la alta,valoarea lui J scade nesemnificativ.

Coeficientul α > 0 se numeşte rată de învăţare. Alegerea lui α estecrucială: dacă valoarea lui e prea mică, atunci algoritmul va face foartemulte iteraţii până se va opri (cost computaţional mare). Dacă e prea mare,procesul poate să rateze minimul sau chiar să diveargă (valoarea lui J săcrească mereu). Dacă se constată acest al doilea fenomen, valoarea lui αtrebuie scăzută. Odată ce o valoare potrivită pentru α este găsită, nu enevoie ca aceasta să fie modificată.

Menţionăm că pentru o funcţie oarecare procedura expusă poate duce laoprirea în minim local. Deoarece gradientul în extreme este nul, rezultă căvaloarea parametrilor θ nu se va mai modifica, odată ce s–a atins un minim.

Pentru trecerea la cazul multivariat, algoritmul dat mai sus se păstreazăcu modificarea domeniului de valori al lui j de la finalul ecuaţiei (2.5): 0 ≤j ≤ n.

Următoarele sugestii trebuie să fie luate în considerare:

• valorile trăsăturilor să fie în scale similare; dacă acest lucru nu se în-tâmplă, se poate face în prealabil o scalare a datelor la un intervalconvenabil ales, e.g. [0, 1]; ca efect se obţine un număr mult redus deiteraţii până la convergenţa algoritmului;

• se vor urmări valorile lui J ; dacă ele au nu o tendinţă descrescătoare(funcţia J creşte sau are scăderi urmate de creşteri bruşte) atunci seva încerca o valoare mai mică pentru rata de învăţare α;

• dacă valoarea funcţiei J scade foarte lent se poate mări valoarea lui α.

2.4 Metoda algebrică pentru minimizarea func-ţiei de eroare

Există o metodă care dă o soluţie pe baza unui calcul algebric.Vom discuta în cele ce urmează cazul unei funcţii liniare multivariate, cu

notaţii din algebra liniară. Pentru început, se va nota cu X matricea datelor

21

Page 23: Sisteme Computationale Inteligente

de intrare:

X =

x(1)1 x

(1)2 . . . x

(1)n

x(2)1 x

(2)2 . . . x

(2)n

......

. . ....

x(m)1 x

(m)2 . . . x

(m)n

(2.6)

unde x(i)j este a j-a componentă a celui de al i-lea vector din setul de instruire.

Valorile de ieşire corespunzătoare sunt de asemenea stocate matricial, folosindun vector coloană:

y =

y(1)

y(2)

...y(m)

(2.7)

Modelul liniar multivariat are forma:

hθ(x) = θ0 + θ1 · x1 + θ2 · x2 + · · ·+ θn · xn (2.8)

Dacă se defineşte termenul x0 = 1, atunci modelul multivariat se rescrie ca:

hθ(x) =n∑

j=0

θj · xj (2.9)

Vectorul de intrare x este x0 = (x0, . . . , xn)t, vectorul de parametri este

θ = (θ0, . . . , θn)t, ambii din ℜn+1 iar suma din ecuaţia (2.9) se poate scrie

sub forma unui produs scalar de vectori:

hθ(x) = θt · x (2.10)

cu x = (1, x1, . . . xn)t. Putem extinde matricea de date X din ecuaţia (2.6)

ca având o coloană plină cu valoarea 1 adăugată drept primă coloană:

X =

1 x(1)1 x

(1)2 . . . x

(1)n

1 x(2)1 x

(2)2 . . . x

(2)n

......

. . ....

1 x(m)1 x

(m)2 . . . x

(m)n

(2.11)

şi în continuare vom folosi tot notaţia X pentru această matrice.

22

Page 24: Sisteme Computationale Inteligente

Funcţia J se rescrie matricial astfel:

J(θ) =1

2m

m∑

i=1

(

hθ(x(i))− y(i)

)2

=1

2m

m∑

i=1

(

θTx(i) − y(i))2

=1

2m(Xθ − y)t (Xθ − y)

=1

2m

{

(Xθ)t Xθ − (Xθ)t y − yt (Xθ) + yty}

=1

2m

{

θtXtXθ − 2(Xθ)ty + yty}

(2.12)

Valorile căutate pentru componentele lui θ sunt cele care produc mini-mul valorii lui J . O condiţie necesară este ca pentru aceste valori, vectorulderivatelor parţiale să fie vectorul nul:

∂J

∂θj= 0, 0 ≤ j ≤ n (2.13)

sau într–o notaţie mai compactă [16]:

∂J

∂θ= 0 (2.14)

Pentru funcţia de eroare pătratică J din ecuaţia (2.3), condiţia necesarădată de (2.14) este şi suficientă pentru a ajunge în unicul minim al funcţieide eroare. Avem (vezi [16], secţiunea 2.4):

∂J

∂θ(θ) =

1

2m

(

2XtXθ − 2Xty)

(2.15)

Considerând condiţia (2.14) obţinem ecuaţiile normale:

XtXθ = Xty (2.16)

de unde vectorul de parametri θ se detemină ca

θ =(

XtX)−1

Xt · y (2.17)

Note:

1. Inversa lui XtX există dacă coloanele lui X sunt liniar independente;

23

Page 25: Sisteme Computationale Inteligente

2. Expresia (XtX)−1

Xt se mai numeşte şi pseudo–inversa Moore–Penrose;pentru o matrice inversabilă inversa şi pseudo–inversa ei coincid;

3. Când se foloseşte metoda ecuaţiilor normale nu este nevoie să se facăscalarea trăsăturilor de intrare, precum se sugerează la metoda itera-tivă.

24

Page 26: Sisteme Computationale Inteligente

Capitolul 3

Reţele neurale artificiale -

fundamente

3.1 Încadrarea domeniului

Studiul reţelelor neurale artificiale este motivat de observaţia că un sistembiologic este mai performant decât calculatoarele şi programele existente laora actuală într-o serie de sarcini precum recunoaşterea de imagini, regăsireainformaţiei, înţelegerea vorbirii. Acest lucru se întâmplă cu toate că neuroniibiologici operează mult mai lent decât procesoarele actuale. Studiul reţelelorneurale artificiale are ca scop producerea unor sisteme care să obţină rezolvăripentru probleme de tipul celor de mai sus, dar şi altele de natură sintetică,pe baza experienţei acumulate din mediu.

Definiţia următoare ([13]) ia în considerare abilitatea de adaptare pe bazaexperienţei:

Definiţia 4 Sistemele neurale artificiale, sau reţelele neurale sunt sistemecelulare fizice care pot achiziţiona, stoca şi utiliza cunoaşterea experimentală.

Natura neliniară, complexă şi cu grad mare de paralelism reprezintă di-ferenţe majore faţă de modelele de calcul actuale. O reţea neurală artificialămodelează felul în care creierul biologic procesează semnalele. Modelele dereţele neurale artificiale sunt structurate ca nişte grafuri ale căror noduri suntneuroni artificiali, iar legăturile dintre noduri au ponderi1 - valori numerice- ajustabile printr-un proces de învăţare. Definiţia din [4] sumarizează acestfapt:

Definiţia 5 O reţea neurală este un sistem de procesare masiv paralel-distribuitconstând din unităţi de procesare simple, care au predispoziţie naturală pen-

1În limba engleză: weights.

25

Page 27: Sisteme Computationale Inteligente

tru stocarea cunoştinţelor experimentale şi utilizarea lor. Este asemănătoarecreierului în două aspecte:

1. Cunoaşterea este achiziţionată de către reţea din mediu printr–un procesde învăţare;

2. Ponderile legăturilor dintre neuroni, cunoscute ca ponderi sinapticesunt folosite pentru a reţine cunoaşterea dobândită.

Procedura prin care se obţine adaptarea ponderilor din cadrul reţelei senumeţe algoritm de învăţare. Mai menţionăm că învăţarea poate duce lamodificarea numărului de noduri din reţea (a se vedea de exemplu FuzzyARTMAP, capitolul 7), ceea ce în cadrul reţelelor neurale biologice are ca şicorespondent faptul că unii neuroni mor (efectul de retezare din reţele neu-rale) şi alţi neuroni se pot alătura celor existenţi pentru a sprijini învăţarea.

Numele sub care mai sunt cunoscute aceste reţele sunt: neurocalculatoare,reţele conecţioniste, sisteme adaptive stratificate, reţele cu auto-organizare,sisteme neuromorfice etc.

Există multe moduri în care pot fi privite aceste reţele neurale de cătrediferite categorii profesionale:

• oamenii de ştiinţă din domeniul neurobiologiei sunt interesaţi de mo-dul în care reţelele neurale artificiale confirmă rezultatele sau modelelecunoscute pentru sisteme biologice; facem precizarea că transferul decunoştinţe nu este doar dinspre biologie spre domeniul artificial, ci şiinvers: modele teoretice sunt confirmate de descoperirile biologice2;

• fizicienii văd analogii între reţelele neurale şi sistemele dinamice nelini-are pe care le studiază;

• matematicienii sunt interesaţi de potenţialul de modelare matematicăpentru sisteme complexe;

• inginerii din domeniul electric le folosesc pentru procesarea de semnale;

• informaticienii sunt interesaţi de oportunităţile care apar in zonele deinteligenţă artificială, teorie computaţională, modelare şi simulare etc.

Beneficiile aduse de reţele neurale artificiale sunt:

2Vezi de exemplu “Reinforcement learning through mo-dulation of spike-timing-dependent synaptic plasticity”,A mechanism predicted theoretically by a Coneural scientist has been found experimentally in the brain.

26

Page 28: Sisteme Computationale Inteligente

1. neliniaritatea: un neuron artificial poate avea comportament liniar saunu; caracteristica neliniară este importantă pentru cazul în care meca-nismul care generează semnalul este neliniar - de exemplu semnalul devorbire;

2. detectarea de asocieri între intrări şi ieşiri: este cazul învăţării super-vizate, în care antrenarea se face pe baza unor perechi de semnale,corespunzătoare intrărilor şi respectiv ieşirilor asociate. Se poate plecade la un model care nu are cunoştinţe apriori despre domeniu şi pe bazadatelor se învaţă asocierea.

3. adaptabilitate: reţelele neurale au capacitatea naturală de a–şi adaptaponderile în funcţie de semnalele provenite din mediu; mediul poate săfie nestaţionar, adică să sufere modificări în ceea ce priveşte distribuţiasemnalelor sau a asocierilor;

4. rezistenţa la zgomot: o reţea neurală poate să accepte date care auimprecizie sau sunt afectate de zgomot; sunt raportate multe situa-ţii în care adăugarea de zgomot la datele de antrenare îmbunătăţeştecalitatea învăţării.

3.2 Neuronul biologic

Este utilă o scurtă incursiune în biologie, pentru a înţelege modelarea cese face pentru un neuron artificial.

Neuronul biologic este o celulă nervoasă elementară, elementul constructivde bază pentru reţeaua neurală biologică. Neuronul are trei părţi principale:corpul celulei, numit şi soma, axonul şi dendritele. O schemă a unui neurona fost dată în figura 1.1. Dendritele formează o arborescenţă prin care suntprimite impulsuri de la alţi neuroni. Axonul este un fir conductor lung,cu un capăt în corpul celulei iar cu celălalt ramificat, prin care se trimitesemnal către dendritele altor axoni. Contactul dintre un axon şi o dendrită secheamă sinapsă. Ca mediatori ai semnalului în sinapse se folosesc adrenalină,noradrenalină, acetilcolina, serotonina.

Neuronul este capabil să dea un răspuns pe baza intrărilor furnizate decătre dendrite. Răspunsul acesta este generat dacă potenţialul membraneidepăşeste un anumit prag de activare. Impulsurile care vin prin membranăsunt excitatoare dacă ele favorizează formarea semnalului de ieşire din ne-uron şi inhibitoare dacă inhibă răspunsul. Se face o agregare a semnalelorprimite de celulă de-a lungul unei perioade de sumare latentă, luându-se înconsiderare şi apropierea în timp a semnalor excitatoare primite; nu se cere

27

Page 29: Sisteme Computationale Inteligente

o sincronizare a semnalelor, iar valoarea de ieşire este de regulă văzut ca unabinară: dacă suma semnalelor primite este mai mare decât pragul de activare(nu contează cu cât mai mare) se trimite semnal mai departe prin axon, cătrealţi neuroni; dacă este mai mic, atunci nu se face trimitere.

După emiterea semnalului prin axon există o perioadă refractară, în careneuronul nu mai ia în considerare niciun semnal sosit, indiferent de gradul deintensitate. După scurgerea acestei perioade, neuronul este gata să procesezenoi semnale. Perioada refractară nu are neapărat aceeaşi durată pentru toatecelulele. Timpul necesar acestui ciclu este de ordinul milisecundelor.

Facem precizarea că prezentarea făcută este o variantă simplificată; con-siderarea unor detalii omise duce la reţele neurale artificiale de diferite tipuri(generaţii).

3.3 Modele de neuroni artificiali

3.3.1 Modelul McCulloch–Pitts

Reprezintă prima definiţie formală a unui neuron artificial, ce pleacă dela descrierea a neuronului biologic. Modelul a fost formulat în 1943 de neu-robiologul si ciberneticianul Warren McCulloch şi respectiv logicianul WalterPitts. Modelul este arătat în figura 3.1. Intrările xi sunt 0 sau 1, i = 1, n,ponderile wi ∈ {−1, 1}, T este pragul neuronului iar ieşirea o se calculeazăca:

ok+1 =

1 dacăn∑

i=1

wixki ≥ T

0 altfel(3.1)

unde indicele superior k este momentul de timp, k = 0, 1, . . . . Ponderilewi = 1 reprezintă sinapsele excitatoare, cele cu valoare -1 sunt inhibitoare.Cu toate că modelul este simplu, el poate fi folosit pentru implementareaoperaţiilor logice not, and şi or, dacă ponderile şi pragul sunt setate cores-punzător.

x1

x2

xn

w1

w2

wn

T o

Figura 3.1: Modelul McCulloch-Pitts pentru neuron artificial.

28

Page 30: Sisteme Computationale Inteligente

3.3.2 Modelarea neuronului pentru sisteme neurale ar-tificiale

Modelul McCulloch-Pitts este o viziune simplificată: permite doar intrări,ieşiri şi ponderi binare, operează în timp discret, presupune sincronizarea in-trărilor (toate intrările trebuie să sosească în acelaşi timp), ponderile şi pra-gul sunt fixe. Ca atare, se propune modelul dat în figura 3.2 cu următoareleprecizări:

1. fluxul semnalului de intrare xi este unidirecţional

2. valoarea de ieşire a neuronului este:

o = f(wt · x) (3.2)

adică

o = f

(

n∑

i=1

wixi

)

(3.3)

unde vectorul ponderilor w este

w =

w1

w2...wn

= (w1 w2 . . . wn)t

iar vectorul x al intrărilor este

x = (x1, x2, . . . , xn)t

3. valoarea produsului scalar wt ·x se notează cu net şi se numeşte valoarede activare a neuronului;

4. funcţia f se numeşte funcţie de activare; poate avea diferite forme.

Se remarcă lipsa pragului T din ecuaţiile de mai sus; de fapt, se poateconsidera că neuronul are doar n− 1 intrări sinaptice iar valoarea a n-a estexn = −1 permanent, având ponderea asociată wn = T . Funcţiile de activaref(·) larg folosite sunt

f1(net) =2

1 + e−λ·net− 1, λ > 0 (3.4)

cu graficul dat în figura 3.3 şi

f2(net) = sgn(net) =

{

+1, dacă net > 0−1, dacă net < 0

(3.5)

29

Page 31: Sisteme Computationale Inteligente

x1

x2

xn

w1

w2

wn

tf(w x) o

Figura 3.2: Model general de neuron

Figura 3.3: Funcţia sigmoidă dată de ecuaţia 3.4 pentru λ fixat.

Se observă că λ/2 = f ′1(0), deci λ este dublul pantei tangentei la graficul

lui f1 în origine. Pentru λ → ∞ f1 tinde către f2. Datorită alurii funcţieif1, amintind de forma literei S, ea se mai numeşte şi sigmoidă. Se mai poatefolosi drept funcţie de activare tangenta hiperbolică:

f3(x) = tanh(x) =sinh(x)

cosh(x)=

exp(x)−exp(−x)2

exp(x)+exp(−x)2

=exp(2x)− 1

exp(2x) + 1(3.6)

Deoarece funcţiile date iau valori între -1 şi +1 se mai numesc bipolare,iar aspectul (dis)continuu le dă denumirea de bipolară continuă şi respectivbipolară discretă. Funcţiile bipolare pot fi redusă la formă unipolară, avândminimul şi maximul egale cu 0, respectiv 1:

f4(net) =1

1 + e−λ·net, λ > 0 (3.7)

(sigmoida logistică) şi

f5(net) =

{

+1, dacă net > 00, dacă net < 0

(3.8)

Drept funcţie de activare se poate folosi de fapt orice funcţie care este mono-ton nedescrescătoare, mărginită şi preferabil derivabilă3. Aspectul continuu

3Pentru cazul funcţiilor nederivabile se poate folosi metoda subgradientului:http://www.stanford.edu/class/ee392o/subgrad_method.pdf.

30

Page 32: Sisteme Computationale Inteligente

asigură mai multă flexibilitate procesului de instruire, motiv pentru carefuncţiile de activare continue sunt cele folosite.

Ieşirile pot fi binare sau continue, bipolare sau unipolare. Pentru m neu-roni, mulţimea valorilor de ieşire este:

• (−1, 1)m pentru funcţie de activare bipolară continuă

• (0, 1)m pentru funcţie de activare unipolară continuă

• {−1, 1}m pentru funcţie de activare bipolară discretă

• {0, 1}m pentru funcţie de activare unipolară discretă

3.4 Modele de reţea neurală artificială

3.4.1 Reţea cu propagare înainte

Vom considera o arhitectură de reţea cu propagare înainte4 cu n intrări şim neuroni de ieşire, precum în figura 3.4. Intrările şi ieşirile sunt respectiv:

x = (x1, x2, . . . , xn)t

o = (o1, o2, . . . , om)t (3.9)

Dacă considerăm vectorul de ponderi wi care leagă neuronul de ieşire i cutoate intrarile, wi = (wi1, wi2, . . . , win)

t, atunci valoarea de activare pentruneuronul i este

neti = wtix =

n∑

j=1

wijxj, ∀i = 1,m (3.10)

Valoarea de ieşire oi pentru fiecare neuron este oi = f(neti) = f(wtix).

Putem nota cu W matricea ponderilor dintre neuroni:

W =

w11 w12 · · · w1n

w21 w22 · · · w2n...

.... . .

...wm1 wm2 · · · wmn

(3.11)

şi introducem operatorul matriceal Γ(·) definit ca

Γ(·) =

f(·)f(·)

...f(·)

m×1

(3.12)

4În original: feedforward network.

31

Page 33: Sisteme Computationale Inteligente

o1

w 11

w m1

xn

w 22 o2

om

x1

x2

w 21 w 12

w m2

w 1n w 2n

w mn

Figura 3.4: Model de reţea neurală artificială

ceea ce ne permite să scriem ieşirea reţelei ca fiind:

o = Γ(W · x) (3.13)

Valorile de intrare x şi cele de ieşire o se numesc pattern-uri de intrare şi res-pectiv de ieşire. Reţeaua acţionează instantaneu, adică de îndată ce intrareaeste furnizată, reţeaua dă şi valoarea de ieşire asociată. Dacă se considerămomentul de timp t, atunci putem rescrie 3.13 ca:

o(t) = Γ(W · x(t)) (3.14)

3.4.2 Reţele cu conexiune inversă

La reţeaua prezentată anterior putem adăuga nişte conexiuni care să facălegătura de la ieşiri la intrări. Reţeaua nou obţinută este denumită “cu cone-xiune inversă”5; o reprezentare este dată în figura 3.5. În felul acesta, ieşirilecontrolează intrările. Mai mult, valorile o(t) controlează valorile o(t+∆). ∆reprezintă aici perioada refractară a neuronului. Ieşirea este dată de ecuaţia:

o(t+∆) = Γ(Wo(t)) (3.15)

Intrarea x este necesară doar la început (t = 0), după care sistemulse auto-întreţine. Dacă considerăm timpul ca valoare discretă şi urmărim

5În limba engleză: feedback network.

32

Page 34: Sisteme Computationale Inteligente

w 11

w m1

w 22

1 ∆o (t+ )x (0)1

x (0)

x (0)

∆∆

w 21 w 12

w m2

w 1n w 2n

w mn

2o (t+ )

no (t+ )

2

n

Figura 3.5: Reţea cu conexiune inversă.

33

Page 35: Sisteme Computationale Inteligente

sistemul la momentele 0, ∆, 2∆, . . . , k∆, . . . atunci sistemul se numeştediscret. Putem lua convenabil ∆ = 1 şi atunci avem:

ok+1 = Γ(Wok), k = 1, 2, . . . (3.16)

sauok+1 = Γ

(

WΓ(

· · ·Γ(Wx0) · · ·))

(3.17)

Şirul de valori o1, o2, . . . reprezintă stările succesive ale reţelei, care în acestcaz este văzut ca un sistem dinamic. Este posibil ca de la un moment datok = ok+1 = . . . , adică ok să fie un atractor, iar reţeaua se stabilizează. Maigeneral, un atractor poate să fie o mulţime finită de valori. Un exemplu deastfel de reţea neurală este memoria asociativă bidirecţională.

3.5 Învăţarea ca problemă de aproximare

În urma procesului de învăţare nu putem obţine în toate cazurile repro-ducerea perfectă a ceea ce s–a învăţat. Se poate obţine o aproximare a uneifuncţii h(·) printr-o funcţie H(w, ·) unde w = (w1, w2, . . . wm)

t iar argumen-tul notat “·” este un vector x = (x1, x2, . . . , xn)

t. Problema este de a găsivectorul w care dă cea mai bună aproximare pentru un set de antrenare{x1, . . . ,xp}. Primul pas este alegerea funcţiei aproximante H(·, ·), apoi unproces de învăţare este folosit pentru a determina o valoare bună pentruvectorul w. Altfel zis, se caută un vector w∗ pentru care

p∑

k=1

ρ(

H(w∗,xk), h(xk))

≤ ρ(

H(w,xk), h(xk))

(3.18)

unde ρ este o funcţie distanţă care măsoară calitatea aproximării. Învăţareaeste procesul de găsire a unui bun aproximant.

Deşi formularea este simplă, există două dificultăţi în rezolvarea generalăa acestei probleme de aproximare:

1. o valoare potrivită pentru m poate fi greu de determinat; atunci cândaproximarea se face prin reţele neurale de tip feedforward cu un stratascuns (vezi curs 5), valoarea lui m este numărul de neuroni din stratulascuns;

2. determinarea efectivă a lui w∗ cunoaşte rezolvări pentru câteva cazuri– a se vedea teoria cercetărilor operaţionale – dar o metodă eficientăpentru toate cazurile nu este cunoscută6; putem vorbi de probleme de

6A se vedea http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization.

34

Page 36: Sisteme Computationale Inteligente

programare liniară sau de programare pătratică, dar sunt multe altesituaţii care nu au o rezolvare teoretică cunoscută. O abordare estefolosirea unor metode de căutare euristică – metodele “hill-climbing”,“simulated annealing”, algoritmi genetici, dar aceştia nu garantează ob-ţinerea minimului absolut.

3.6 Reguli de învăţare

În această secţiune vom privi neuronul artificial ca pe o entitate adap-tivă, pentru care ponderile se pot modifica pe baza unui proces de învăţare.Ponderile se modifică în funcţie de:

• valoarea actuală a ponderilor, w sau W;

• semnalul de intrare x;

• ieşirea rezultată o

• (opţional) ieşirea furnizată de un “profesor”, în cazul învăţării supervi-zate, numită şi ieşirea dorită, d

Putem presupune că intrarea xn are valoarea fixă −1, pentru a permite in-cluderea parametrului prag. Putem considera că sunt n neuroni de intrare şim de ieşire, iar vectorul ponderilor care leagă al i-lea neuron de ieşire de toţineuronii de intrare este wi = (wi1, wi2, . . . , win)

t.Regula de învăţare generală este că ponderile wi variază proporţional cu

produsul dintre intrarea x şi semnalul de învăţare r. r este o funcţie care iaîn considerare trei din valorile date mai sus, deci

r = r(wi,x, di) (3.19)

unde di este eventuala valoare de ieşire ce corespunde neuronului de ieşire i.Mai precis, avem

∆wi(t) = c · r(wi(t),x(t), di(t)) · x(t) (3.20)

unde c > 0 este rata de învăţare. Expresia (3.20) dă modul în care se modificăponderile de la un moment de timp la următorul:

wi(t+ 1) = wi(t) + c · r(wi(t),x(t), di(t)) · x(t) (3.21)

Pentru cazul discret se foloseşte scrierea:

wk+1i = wk

i + c · r(wki ,x

k, dki ) · xk, k = 0, 1, . . . (3.22)

35

Page 37: Sisteme Computationale Inteligente

iar pentru cazul continuu se scrie ecuaţia diferenţială

dwi(t)

dt= cr(wi(t),x(t), di(t))x(t) (3.23)

Pe baza formei funcţiei r avem variantele de învăţare menţionate mai jos.

3.6.1 Regula de învăţare Hebbiană

Este o regulă de învăţare nesupervizată formulată de Donald Hebb în1949 astfel:

When an axon of cell A is near enough to excite a cell B andrepeatedly or persistently takes part in firing it, some growthprocess or metabolic change takes place in one or both cells suchthat A’s efficiency, as one of the cells firing B, is increased.

Matematic, se scrie:r = f(wt

ix) (3.24)

deci modificarea ponderilor devine

∆wi = cf(wtix)x (3.25)

ceea ce pe componente se scrie

∆wij = cf(wtix)xj (3.26)

sau în funcţie de ieşirea neuronului i

∆wij = coixj (3.27)

Ponderile sunt iniţializate cu valori aleatoare mici, în jurul lui 0. Conformformulelor date, putem avea o creştere a ponderii wij dacă produsul oixj

este pozitiv şi o scădere în caz contrar. Se arată uşor că intrările prezentatefrecvent au o influenţă mai mare asupra ponderilor şi vor produce o valoarede ieşire mare.

Regula trebuie înţeleasă ca un principiu, existând la ora actuală variaţiunipe această temă.

Exemplu numeric: [13] pag 61.

36

Page 38: Sisteme Computationale Inteligente

3.6.2 Regula de învăţare a perceptronului

Este folosită pentru învăţare supervizată; regula a fost formulată de cătreRosenblatt în 1958. Semnalul de învăţare este diferenţa între valoarea dorităşi cea obţinută:

r = di − oi (3.28)

unde oi = sgn(wtix), iar di este răspunsul dorit, furnizat de “profesor”. Mo-

dificarea ponderilor este deci

∆wi = c(

di − sgn(wtix))

x (3.29)

Formula se aplică pentru cazul în care ieşirile sunt bipolare binare. Modi-ficarea în ponderi apare doar dacă ieşirea furnizată de neuronul de ieşire idiferă de valoarea dorită — cunoscută aprioric. Explicitând, se poate vedeacă modificarea de pondere în cazul neconcordanţei ieşirii cu valoarea dorităeste

∆wi = ±2cx (3.30)

Ponderile pot fi iniţializate cu orice valoare.Exemplu: [13] pag 65.

3.6.3 Regula de învăţare delta

Prezenta regulă se foloseşte pentru cazul învăţării supervizate cu funcţiede activare continuă; a fost introdusă de McClelland şi Rumelhart în 1986.Semnalul de învăţare se cheamă în acest context “delta” şi are forma:

r = (di − f(wtix))f

′(wtix) (3.31)

Motivaţia prezenţei derivatei în formulă este dată de minimizarea erorii pă-tratice:

E =1

2(di − oi)

2 =1

2

(

di − f(wtix))2

(3.32)

Tehnica de reducere a valorii funcţiei constă în mişcarea în sens opus gra-dientului ∇E

∇E = −(di − oi)f′(wt

ix)x (3.33)

Componentele gradientului sunt

∂E

∂wij

= −(di − oi)f′(wt

ix)xj, ∀j = 1, n (3.34)

Modificarea ponderilor se face astfel:

∆wi = −η∇E (3.35)

37

Page 39: Sisteme Computationale Inteligente

unde η este o constantă pozitivă. O altă scriere este:

∆wi = η(di − oi)f′(neti)x (3.36)

Regula poate fi generalizată pentru reţele cu mai multe straturi.Exemplu: [13] pag 68.

3.6.4 Regula de învăţare Widrow-Hoff

A fost enunţată în 1962 şi se aplică pentru învăţarea supervizată. Regulafoloseşte ca funcţie de activare funcţia identică f(x) = x şi minimizeazăpătratul diferenţei dintre ieşirea dorită di şi activarea neti:

r = di −wtix (3.37)

deci ajustarea de ponderi se face cu

∆wi = c(di −wtix)x (3.38)

Regula Widrow-Hoff este o formă particulară a regulii delta şi mai este cunos-cută sub numele de regula celor mai mici pătrate7. Ponderile sunt iniţializatecu orice valori.

3.6.5 Regula de învăţare prin corelaţie

Se obţine prin considerarea lui r = di. Ponderile se modifică cu valoarea

∆wi = cdix (3.39)

Ponderile sunt iniţializate cu zero.

3.6.6 Regula “câştigătorul ia tot”

Regula “winner-takes-all” este un exemplu de învăţare competitivă şi efolosită pentru învăţarea în mod nesupervizat a proprietăţilor statistice aledatelor. Învăţarea se bazează pe premisa că din toţi neuronii de ieşire unul(fie el de indice k) dă răspunsul maxim pentru o intrare x. Ponderea aferentăacestui vector va fi modificată astfel:

∆wk = α(x−wk) (3.40)

7Least Mean Square (LMS).

38

Page 40: Sisteme Computationale Inteligente

unde α > 0 este o valoare mică, de regulă descrescătoare pe măsură ceprocesul de învăţare continuă. Indicele k este ales deci

k = argmaxi

(

wtix)

(3.41)

După ajustare, ponderile tind să estimeze mai bine patternul de intrare.Ponderile sunt iniţializate cu valori aleatoare şi lungimile lor sunt apoi nor-malizate: ‖wi‖ = const, ∀i.

39

Page 41: Sisteme Computationale Inteligente

Capitolul 4

Perceptroni monostrat

[5], cap. 3

40

Page 42: Sisteme Computationale Inteligente

Capitolul 5

Perceptroni multistrat

[5], cap 4.

41

Page 43: Sisteme Computationale Inteligente

Capitolul 6

Memorii asociative bidirecţionale

Memoriile asociative permit stocarea şi regăsirea datelor. Căutarea seface pe baza similarităţii care există între pattern-ul furnizat ca intrare şiceea ce este stocat în reţea. Regăsirea se face pe baza similarităţii întrepattern–ul furnizat şi a unui pattern stocat de reţea. Se lucrează cu perechide pattern-uri asociate memorate de reţea; plecând de la oricare dintre elesau de la unul similar cu ele se doreşte regăsirea celuilalt. Datele memoratesunt reprezentate în întreaga reţea.

6.1 Distanţa Hamming

Fie x = (x1, . . . , xn)t şi y = (y1, . . . , yn)

t doi vectori n-dimensionali dinspaţiul Euclidian având restricţiile xi, yi ∈ {−1,+1}, i = 1, . . . , n. DistanţaEuclidiană dintre cei doi vectori este:

dE(x,y) =√

(x1 − y1)2 + · · ·+ (xn − yn)2 =

n∑

i=1

(xi − yi)2

Având în vedere valorile pe care le pot lua componentele vectorilor x şi y,avem că:

(xi − yi)2 =

{

0 dacă xi = yi(±2)2 = 4 dacă xi 6= yi

deci distanţa Euclidiană este dE(x,y) =√

4 · diferente(x, y) unde prindiferente(x, y) am notat numărul de componente din x şi y care diferă pen-tru poziţii de acelaşi indice. Pentru doi vectori x şi y ca mai sus se poatedefini funcţia de distanţă Hamming dH ca fiind tocmai numărul de diferenţe

42

Page 44: Sisteme Computationale Inteligente

de pe poziţiile corespunzătoare:

dH(x,y) =n∑

i=1

(1− δxi,yi)

unde δ este indicatorul lui Kronecker (simbolul Kronecker):

δa,b =

{

1, dacă a = b0, altfel

Există relaţia:dE(x,y) = 2

dH(x,y)

Considerăm hipercubul n-dimensional centrat în origine cu latura de lun-gime 21:

Hn ={

x = (x1, x2, . . . , xn)t ∈ Rn, xi ∈ {−1,+1}

}

= {−1,+1}n

Hn se mai numeşte şi cub Hamming.

6.2 Asociatori liniari

Considerăm mulţimea de perechi de pattern-uri {(x1,y1), . . . , (xk,yk)},unde xi ∈ Rn, yi ∈ Rm, i = 1, k. Există trei tipuri de memorii asociative:

1. Memorii heteroasociative: implementează o funcţie Φ : Rn → Rm cuproprietatea că Φ(xi) = yi, i = 1, k. În plus, cerem ca dacă un vectorx ∈ Rn este mai apropiat de un exemplar xi (1 ≤ i ≤ k) decât deceilalţi, atunci Φ(x) = Φ(xi) = yi. Apropierea se consideră în sensulunei distanţe convenabil alese.

2. Memorii interpolative: implementează o funcţie Φ : Rn → Rm astfelîncât Φ(xi) = yi, i = 1, k. În plus, dacă x ∈ Rn este x = xi+d, atunciieşirea memoriei este:

Φ(x) = Φ(xi + d) = yi + e, e ∈ Rm

3. Memorie autoasociativă: dacă yi = xi, i = 1, k, atunci o memorieautoasociativă trebuie să respecte proprietăţile date de memoria hete-roasociativă: Φ(xi) = xi i = 1, k şi dacă x este mai apropiat de xi

decât de oricare alt exemplar, atunci Φ(x) = Φ(xi) = xi.

1O variantă este considerarea vârfurilor ca având coordonatele 0 sau 1.

43

Page 45: Sisteme Computationale Inteligente

Pentru cazul în care setul de vectori {xi} este ortonormat2 putem construisimplu un asociator interpolativ. Vom defini funcţia Φ ca fiind:

Φ(x) =(

y1xt1 + · · ·+ ykx

tk

)

x (6.1)

Avem că:

Φ(xj) =(

y1xt1 + · · ·+ ykx

tk

)

xj =k∑

i=1

((

yixti

)

xj

)

=

k∑

i=1

(

yi

(

xtixj

))

=k∑

i=1

(yiδij) = yj (6.2)

Dacă un argment x are forma x = xi + d, atunci:

Φ(x) = Φ(xi + d) = yi + e

undee =

(

y1xt1 + · · ·+ ykx

tk

)

d

6.3 Memoria asociativă bidirecţională

O memorie asociativă bidirecţională (MAB) este o memorie heteroasoci-ativă constând în două straturi de elemente de procesare (noduri) care suntinterconectate. Elementele pot sau nu să aibă legături cu ele însele (bucle).O reprezentare este dată în figura 6.1. Valorile x sunt din Hn iar y din Hm.Între noduri există legături cu diferite ponderi. Spre deosebire de alte tipuride reţele neurale, ponderile pot fi determinate dacă se cunoaşte de dinaintesetul de exemplare ce trebuie memorat. Conexiunile sunt bidirecţionale: pu-tem furniza ca intrare o valoare în stratul x iar ieşirea să fie dată de stratuly sau invers.

Pentru construirea matricii ponderilor se poate folosi o idee similară cucea de la memoria interpolativă:

w = y1xt1 + · · ·+ ykx

tk,

matrice care dă ponderile legăturilor de la stratul x la stratul y. Matriceaponderilor în sens invers este wt. Memoria poate deveni autoasociativă prinstabilirea lui w ca fiind:

w = x1xt1 + · · ·+ xkx

tk

2Adică xti · xj = δij , i, j = 1, k, cu δ indicatorul lui Kronecker. Dintr-un set de

vectori liniar independenţi putem obţine întotdeauna un sistem de vectori ortonormaţiprin procedeul Gram-Schmidt de ortonormare. Pentru a reduce din efectul erorilor derotunjire, se poate folosi procedeul Gram-Schmidt modificat.

44

Page 46: Sisteme Computationale Inteligente

Figura 6.1: Arhitectura unei memorii asociative bidirecţionale

Odată matricea de ponderi contruită, se poate utiliza MAB pentru regă-sirea datelor stocate prin furnizarea unor date cheie. Vom vedea că aceastăintrare poate fi obţinută prin perturbarea unei valori din setul de instruire,iar MAB poate încă să determine cheia originară şi valoarea asociată ei.

Paşii de lucru sunt următorii:

1. se aplică perechea iniţială de vectori (x0,y0) celor două straturi deneuroni;

2. se propagă informaţia de la stratul x la stratul y şi se modifică valoriledin stratul y;

3. se propagă informaţia de la y la x şi se modifică valorile din stratul x;

4. se repetă paşii 2 şi 3 până când nu mai apare nicio modificare în noduri.

Se poate ca datele să înceapă să se propage de la stratul y la stratulx. Plimbarea datelor în ambele sensuri dă natura bidirecţională a reţelei.Când reţeaua se stabilizează, de regulă se regăseşte în stratul x valoarea xi

care este cea mai apropiată de x relativ la distanţa Hamming şi valoarea yi

asociată cu xi (sau complementele acestora, a se vedea exemplul considerat).Procesarea care se face în momentul transmiterii informaţiei de la stratul

x la stratul y este dată de ecuaţia:

nety = w · x

45

Page 47: Sisteme Computationale Inteligente

sau pe componente:

netyi =n∑

j=1

wijxj, i = 1,m

unde nety este vectorul de stare pentru stratul y. Pentru transmiterea însens invers are loc un proces asemănător:

netx = wty

sau pe componente:

netxi =m∑

j=1

wji · yj, i = 1, n

Valoarea pentru un nod depinde de intrări şi de valoarea lui curentă. Maiclar, valoarea de la momentul t+ 1 pentru nodul yi este dată de:

yi(t+ 1) =

1, dacă netyi > 0yi(t), dacă netyi = 0−1, dacă netyi < 0

(6.3)

Valorile de ieşire pentru stratul x se calculează similar.Exemplu: plecăm de la perechea de pattern-uri:

x1 = (1,−1,−1, 1,−1, 1, 1,−1,−1, 1)t,x2 = (1, 1, 1,−1,−1,−1, 1, 1,−1,−1)t

cu ieşirile corespunzătoare

y1 = (1,−1,−1,−1,−1, 1)t,y2 = (1, 1, 1, 1,−1,−1)t

Matricea ponderilor este:

w =

2 0 0 0 −2 0 2 0 −2 00 2 2 −2 0 −2 0 2 0 −20 2 2 −2 0 −2 0 2 0 −20 2 2 −2 0 −2 0 2 0 −2−2 0 0 0 2 0 −2 0 2 00 −2 −2 2 0 2 0 −2 0 2

Vom considera ca vector de intrare x0 = (−1,−1,−1, 1,−1, 1, 1,−1,−1, 1)t

cu vectorul y0 asociat (1, 1, 1, 1,−1,−1)t. Remarcăm că valorile x0şi y0 nusunt printre valorile învăţate. Valoarea de ieşire y0 poate fi dată ca un vectorbinar bipolar cun componente aleatoare. Propagarea valorilor dinspre stratulx către y duce la determinarea valorii nety = (4,−12,−12,−12,−4, 12)t.Noul vector din stratul y este y = (1,−1,−1,−1,−1, 1)t. Propagând înapoi

46

Page 48: Sisteme Computationale Inteligente

către stratul x obţinem x = (1,−1,−1, 1,−1, 1, 1,−1,−1, 1)t. Propagărisuccesive într–un sens sau în celălalt nu duc la modificări ale valorilor dinstraturile x sau y. Perechea (x,y) la care se stabilizează reţeaua este chiarperechea (x1,y1). S-a regăsit astfel o pereche de exemplare din cele cu cares–a instruit reţeaua, chiar dacă s–a plecat de la valori care nu se regăsescprintre cele învăţate.

Să considerăm situaţia în care se pleacă de valorile iniţiale:

x0 = (−1, 1, 1,−1, 1, 1, 1,−1, 1,−1)t,y0 = (−1, 1,−1, 1,−1,−1)t

Propagând de la stratul x la y, obţinem y = (−1, 1, 1, 1, 1,−1)t. Propagândîn direcţia inversă, obţinem x = (−1, 1, 1,−1, 1,−1,−1, 1, 1,−1)t şi reţeauase stabilizează. Se observă că valorile stabile (x,y) sunt chiar (xc

1,yc1) unde

ac este vectorul format cu valorile complementate ce compun pe a3. Aceastaeste o proprietate a MAB: dacă memoria stochează perechea (x,y), atuncistochează şi perechea (xc,yc) şi stabilizarea reţelei se poate face pe o astfelde pereche de complemente.

6.4 Funcţia de energie a MAB

În timpul propagării valorilor dinspre stratul x spre y sau invers, valoriledin nodurile reţelei se modifică, ceea ce ne permite să vedem evoluţia stăriiacestora ca o funcţie de timp. Vom asocia memoriei o funcţie de energie acărei valoare este dependentă de valorile x şi y din noduri; vrem să arătăm căfuncţia de energie converge la un punct limită pe durata propagării datelorîntre cele două straturi. Convergenţa se traduce prin stabilizarea reţelei.

Funcţia de energie considerată este:

E(x,y) = −ytwx = −m∑

i=1

n∑

j=1

yiwijxj

Avem următoarea teoremă privitoare la comportamentul MAB pentrufuncţia de energie:

Teorema 1 1. Orice modificare a stării stratului x sau y în timpul pro-cesării din MAB duce la scăderea lui E;

2. E este mărginită inferior de Emin = −∑i,j |wij|;

3. Dacă valoarea lui E se schimbă atunci modificarea nu este arbitrar demică.

3Aici “complementar” se defineşte ca “de semn opus”, deci ac = −a.

47

Page 49: Sisteme Computationale Inteligente

Presupunem că se face o modificare pentru vectorul y pe o singură poziţie,fie ea l. Energia asociată intrării curente este:

E = −n∑

j=1

ylwljxj −m∑

i=1,i 6=l

n∑

j=1

yiwijxj

Dacă se face modificarea valorii yl în ynoul , noua valoare a energiei va fi:

Enou = −n∑

j=1

ynoul wljxj −m∑

i=1,i 6=l

n∑

j=1

yiwijxj

şi deci variaţia energiei este:

∆E = Enou − E = (yl − ynoul )n∑

j=1

wljxj = (yl − ynoul )netyl

Avem posibilităţile:

1. dacă yl = +1, atunci ynoul = −1. Avem yl − ynoul = 2 > 0 dar dacăynoul < 0 asta se datorează lui netyl < 0 (a se vedea ecuaţia 6.3). Va-loarea lui ∆E este produsul a doi termeni de semn contrar şi deci arevaloare negativă.

2. dacă yl = −1, atunci ynoul = +1 şi de aici yl − ynoul = −2 < 0. Dartrecerea de la yl la ynoul presupune că netyl > 0 (ecuaţia 6.3) şi din nou∆E este produsul a două valori de semn contrar, ca atare de valoarenegativă.

Situaţia în care mai mult de un termen din ynou este modificat faţă de y

se tratează similar, cu observaţia că scăderea lui ∆E este şi mai accentuată.Pentru cea de a doua parte a teoremei avem în mod evident4:

−m∑

i=1

n∑

j=1

yiwijxj ≥ |m∑

i=1

n∑

j=1

yiwijxj| ≥m∑

i=1

n∑

j=1

|yi| · |wij| · |xj| =m∑

i=1

n∑

j=1

|wij|.

Partea a treia a teoremei este arătată în prima a demonstraţiei. �

Demonstraţie practică: http://facstaff.cbu.edu/∼pong/ai/bam/bamapplet.html

6.5 Capacitatea de memorie

Capacitatea de memorare a unei memorii asociative bidirecţionale estemin(m,n). După alţi autori, un prag superior pentru numărul de perechi depattern-uri care pot fi memorate ar fi

min(m,n).

4Reamintim că |a+ b| ≤ |a|+ |b| şi a ≤ |a|.

48

Page 50: Sisteme Computationale Inteligente

Capitolul 7

Fuzzy ARTMAP

7.1 Învăţarea incrementală

Învăţarea incrementală este o caracteristică asociată unor sisteme adap-tive care:

1. agregă cunoştinţe noi din date noi;

2. nu cer acces la datele originale, utilizate pentru a antrena sistemul pânăla acest moment;

3. păstrează cunoştinţele deprinse anterior;

4. se pot acomoda cu noi categorii care pot fi introduse de noi date deinstruire.

7.2 Proprietăţi dezirabile ale sistemelor instrui-bile

Pentru un sistem instruibil următoarele proprietăţi sunt văzute ca fiindesenţiale:

1. învăţare rapidă – cerinţă care se regăseşte şi în algoritmii de învăţareincrementală;

2. învăţare din noi date fără a fi nevoie să se reantreneze cu datele parcurseanterior – de asemenea regăsită în învăţarea incrementală;

3. rezolvarea de probleme neseparabile liniar – un hiperplan nu este în-totdeauna o suprafaţă de separare bună;

49

Page 51: Sisteme Computationale Inteligente

4. în cazul unui clasificator: abilitate de a da nu doar clasa de aparte-nenţă a unui pattern de intrare, ci şi plauzibilitatea acestei aparte-nenţe; sunt favorizaţi aici estimatorii de probabilitate Bayesiană deforma P (clasa|intrare); de exemplu, P (mail = spam|continut email);

5. oferire de explicaţii asupra modului în care datele sunt clasificate, dece sunt clasificate într–un anume mod; prin această trăsătură se evitătratarea clasificatorului ca o cutie neagră ce nu poate fi explicată camod de producere a deciziilor;

6. posibilitate de utilizare independentă de reglarea parametrilor; este omare lipsă a teoriei reţelelor neurale faptul că nu există sisteme deînvăţare autonomă;

7. aproximarea de funcţii fără a cunoaşte distribuţia iniţială a datelor; ra-reori datele se supun unei distribuţii clasice de tip normal, Bernoullian,Poissonian etc.;

8. pentru clase care prezintă suprapuneri, să se creeze regiuni în spaţiul deintrare care să realizeze cea mai mică suprapunere; problema asocierilorde tip un pattern de intrare-la-mai multe clase trebuie tratată explicit.

7.3 Dilema stabilitate-plasticitate

Un sistem instruibil ar trebui să aibă două proprietăţi:

1. plasticitate - înseamnă adaptarea la schimbarea mediului din care pro-vin pattern-urile de instruire. Altfel zis, plasticitatea este capacitateade învăţare.

2. stabilitate - se referă la păstrarea cunoştinţelor anterior învăţate

Atunci când se prezintă noi intrări unei reţele neurale, cele vechi pot fiuitate. Ponderile reţelei trebuie să fie suficient de flexibile pentru a învăţanoi cunoştinţe (trăsătura de plasticitate), dar nu atât de mult încât să uiteceea ce s–a învăţat anterior (trăsătura de stabilitate). Acest conflict dintrestabilitate şi plasticitate se numeşte dilema stabilitate–plasticitate. Cele maimulte dintre reţelele neurale existente sunt fie stabile dar incapabile de aînvăţa noi pattern–uri (de exemplu memoriile asociative bidirecţionale), fieplastice dar instabile; de aceea, dilema menţionată este una din problemelede interes în domeniul reţelelor neurale. S-a formulat întrebarea: cum poateun sistem de învăţare să fie atât stabil cât şi plastic?

50

Page 52: Sisteme Computationale Inteligente

Diferiţii algoritmi de învăţare existenţi în literatură se supun unuia saualtuia din criteriile de mai sus şi “cad” undeva între stabilitate şi plasticitate.Această dilemă a fost abordată de Carpenter şi Grossberg în [10]. Teoria re-zonanţei adaptive (Adaptive Resonance Theory, ART) dezvoltată de cei doiautori este unul din răspunsurile concrete date dilemei. De asemenea, siste-mul prezintă abilitate de învăţare incrementală şi mare parte din proprietăţiledezirabile ale sistemelor instruibile.

7.4 Fuzzy ARTMAP

Familia Fuzzy ARTMAP de reţele neurale (FAM) este cunoscută ca unadin puţinele care posedă capacitate de învăţare incrementală, rezolvă dilemastabilitate-plasticitate şi are proprietăţile dorite pentru un sistem instruibil.

Carpenter si Grossberg au fost interesaţi de obţinerea de sisteme care sepot organiza singure. Paradigma ART poate fi descrisă ca un tip de grupareincrementală a datelor, având posibilitatea de a învăţa fără antrenare super-vizată şi este de asemenea în acord cu modelele cognitive şi de comportament.Foloseşte învăţare nesupervizată; reţeaua este capabilă să găsească automatcategoria asociată intrării curente sau să creeze una nouă atunci când estenevoie: numărul de neuroni din reţea nu este fixat aprioric.

Reţelele neurale Fuzzy ART sunt capabile să producă rapid o învăţarestabilă a unor categorii de semnale ca răspuns la secvenţe arbitrare de intrăribinare sau continue. Fuzzy ART încorporează operatori din teoria mulţimilorfuzzy.

Sistemele de tip Fuzzy ARTMAP învaţă în mod autonom să clasificevectori arbitrar de mulţi, prezentaţi într–o ordine oarecare în categorii derecunoaştere create în funcţie de succesul de predicţie. Acest sistem de învă-ţare supervizată este construit dintr-o pereche de module ART capabile deauto-organizare şi obţinere de categorii de recunoaştere stabile.

Succesul reţelei bazate pe teoria rezonanţei adaptive este dat de avantajelepe care le are faţă de alte reţele multistrat dezvoltate anterior:

• permite crearea dinamică a nodurilor fără distrugerea nodurilor exis-tente;

• mai puţine cicluri de antrenare cerute, se poate folosi chiar cu învăţareincrementală;

• convergenţă garantată datorită utilizării unor ponderi mărginite şi mo-notone.

51

Page 53: Sisteme Computationale Inteligente

Fuzzy ARTMAP este utilizabil pentru probleme de clasificare, estimarede probabilitate şi regresie (aproximări de funcţii). S–a arătat relativ recentcă FAM este aproximator universal. Deoarece atât clasificarea cât şi esti-marea de probabilitate sunt cazuri particulare ale aproximărilor de funcţii,este evident acum că FAM poate fi utilizat în orice problemă ce presupunestabilirea de legături dintre două submulţimi din Rn şi respectiv din Rm.

În final, mai precizăm că FAM mai are o virtute: reprezentarea pattern–urilor prin categorii facilitează extragerea de reguli sub forma de relaţii, as-pect esenţial în domeniul extragerii de cunoştinţe (Knowledge Discovery in Data).

7.4.1 Structura reţelei FAM

O reţea FAM constă într–o pereche de module ART notate ARTa şi ARTb,conectate printr-un modul numit Mapfield, notat F ab. ARTa şi ARTb suntfolosite pentru codificarea pattern–urilor de intrare şi respectiv de ieşire, iarMapfield permite asocierea între intrări şi ieşiri. Figura 7.1 conţine principa-lele componente ale unei arhitecturi FAM.

Figura 7.1: Arhitectura Fuzzy ARTMAP

Modulul Fuzzy ARTa conţine stratul de intrare F a1 şi stratul competitiv

F a2 . Se adaugă de asemenea un strat de preprocesare F a

0 înaintea lui F a1 .

Straturi echivalente apar în ARTb.

52

Page 54: Sisteme Computationale Inteligente

Vectorii de intrare iniţiali sunt daţi sub forma:

a = (a1, . . . , an), ai ∈ [0, 1] i = 1 . . . n (7.1)

În cazul în care datele iniţiale nu sunt din intervalul [0, 1], se poate aplica otransformare bijectivă care să le aducă în acest interval:

api →api −MIN

MAX −MIN, i = 1, . . . n

pentru fiecare pattern de intrare ap = (ap1, . . . , apn), 1 ≤ p ≤ P , P fiind

numărul de pattern-uri din setul de instruire, iar MIN şi MAX sunt valoareaminimă şi respectiv maximă din pattern–urile de intrare:

MIN(MAX) = min(max) {api }, i = 1, . . . , n, p = 1, . . . P

sau se poate lua un majorant sau minorant al valorilor de intrare.O tehnică de preprocesare numită codificare complementară este efectu-

ată în cele două module fuzzy ART de către stratul F a0 , respectiv F b

0 pentrua evita proliferarea nodurilor. S–a dovedit geometric că fără codificarea com-plementară se vor produce numeroase categorii grupate lângă origine fără acrea altele care să le înlocuiască. Codificarea complementară este utilizatăpentru a obţine vectori normalizaţi, adică vectori cu normă constantă:

|A| = const (7.2)

unde | · | este funcţie normă. În cazul nostru | · | reprezintă norma L1: pentruun vector x = (x1, . . . , xk)

L1(x) = |x| =k∑

i=1

|xi| (7.3)

Fiecare vector de intrare a = (a1, . . . , an) produce vectorul normalizat:

A = (a, ac) = (a,1− a) = (a1, . . . , an, 1− a1, . . . , 1− an) (7.4)

a cărui normă este:

|A| =n∑

i=1

ai +n∑

i=1

(1− ai) = n = constant (7.5)

Pentru ARTa folosim următoarele notaţii: Ma este numărul de noduri înF a1 şi Na este numărul de noduri din F a

2 . Datorită pasului de preprocesare,Ma = 2n. Fiecare nod F a

2 reprezintă un grup de intrări similare (numit în

53

Page 55: Sisteme Computationale Inteligente

alte contexte cluster); vom folosi termenul “categorie” pentru a ne referi laun nod F a

2 . Fiecare categorie F a2 are propriul set de ponderi adaptive stocate

sub forma unui vector:

waj =

(

waj,1, . . . , w

aj,Ma

)

, j = 1, . . . Na. (7.6)

Aceste ponderi formează memoria pe termen lung a sistemului. Iniţial, toţivectorii au valorile:

waji = 1, j = 1, . . . Na, i = 1, . . .Ma (7.7)

Spunem că un nod din F a2 este necomis dacă nu a învăţat încă nici un pattern

de intrare, comis în caz contrar. Modulul ARTa este responabil cu creareagrupărilor de pattern-uri de intrare. În timpul etapei de învăţare, Na estenumărul de noduri (categorii) comise. Notaţii şi afirmaţii similare se folosescpentru ARTb, care primesc vectori m-dimensionali. Pentru o problemă declasificare, adică o problemă pentru care numărul total de clase de ieşire esteaprioric cunoscut, indexul de clasă este acelaşi cu indexul de categorie dinF b2 şi astfel ARTb poate fi substituit de un vector Nb−dimensional.

Modulul Mapfield permite FAM să creeze legături între cele două moduleART , stabilind legături de tip mulţi–la–unu între categorii din ARTa şi ARTb.Numărul de noduri din F ab este egal cu numărul de noduri din F b

2 . Fiecarenod j din F a

2 este legat cu fiecare nod din F b2 via un vector de ponderi wab

j ,unde wab

j este a j–a linie din matricea wab (j = 1, . . . , Na). Toate ponderiledin wab sunt iniţializate cu 1:

wabjk = 1, j = 1, . . . , Na, k = 1, . . . , Nb (7.8)

7.4.2 Algoritmul de învăţare pentru FAM

În următorul algoritm, operatorul ∧ este aşa numitul operator fuzzy ANDdefinit ca:

(p ∧ q)i = min(pi, qi), i = 1, . . . , k (7.9)

undep = (p1, . . . , pk) ,q = (q1, . . . , qk) (7.10)

1. Se setează parametrul de factor de vigilenţă ρa la o valoare egală cuo valoare de bază prestabilită: ρa = ρa ∈ [0, 1) şi se consideră cătoate categoriile din F a

2 sunt neinhibate – adică fiecare nod participăîn căutarea unei categorii adecvate pentru pattern-ul de intrare curent;

54

Page 56: Sisteme Computationale Inteligente

2. Pentru fiecare vector de intrare preprocesat A, o funcţie fuzzy estefolosită pentru a obţine un răspuns de la fiecare categorie F a

2 :

Tj(A) =|A ∧wa

j |αa + |wa

j |, j = 1, . . . , Na (7.11)

3. Fie J indicele de nod neinhibat care dă cea mai mare valoare calculatăprecum în (7.11), i.e.

J = arg maxj=1,...,Na

{Tj|j = 1, . . . , Na şi nodul j nu este inhibat} (7.12)

4. Verifică condiţia de rezonanţă, i.e. dacă intrarea este suficient de simi-lară cu prototipul câştigătorului:

|A ∧waJ |

|A| ≥ ρa (7.13)

Dacă condiţia este îndeplinită, atunci mergi la pasul 5, altfel inhibănodul J astfel încât el nu va mai participa la competiţia pentru pattern-ul curent. Dacă există noduri neinhibate, atunci mergi la pasul 3,altfel recrutează o nouă categorie (creează un nou nod în F a

2 ) pentru areprezenta vectorul de intrare şi fie J indicele acestui nou nod.

5. Un proces similar se desfăşoară şi în ARTb. Fie K indicele noduluicâştigător din ARTb. Vectorul de ieşire F b

2 este setat la:

ybk =

{

1, pentru k = K0, altfel

k = 1, . . . , Nb (7.14)

În Mapfield se formează vector de ieşire xab:

xab = yb ∧wabJ (7.15)

6. Un test de verificare în Mapfield controlează potrivirea dintre valoareaprezisă xab şi vectorul de ieşire ataşat pattern–ului de instruire curentyb:

|xab||yb| ≥ ρab (7.16)

unde ρab ∈ [0, 1] este un parametru de vigilenţă Mapfield. Dacă testuldin ecuaţia (7.16) este trecut, atunci se face învăţare ARTa, ARTb şiMapfield (pasul 7). Altfel, se iniţiază o secvenţă de paşi numită matchtracking (pasul 8).

55

Page 57: Sisteme Computationale Inteligente

7. În modulele fuzzy ART şi în Mapfield se efectuează învăţare:

wa(new)J = βa

(

A ∧wa(old)J

)

+ (1− βa)wa(old)J (7.17)

(şi analog în ARTb) şi

wabJk =

{

1, pentru k = K0, pentru k 6= K

(7.18)

Se merge la pasul 9.

8. Faza de match tracking: măreşte ρa:

ρa =|A ∧wa

J ||A| + δ (7.19)

unde 0 < δ < 1. Dacă ρa > 1 atunci pattern-ul curent este rejectat,altfel mergi la pasul 3.

9. Dacă mai sunt pattern–uri de învăţat, mergi la pasul 1, altfel STOP.

Urmează câteva comentarii privind paşii de mai sus:

1. La pasul 2, fiecare vector este preprocesat datorită straturilor F a0 şi

respectiv F b0 . αa > 0 este un parametru de alegere. Pentru doi vectori

p şi q, raportul:

r =|p ∧ q||q| (7.20)

cu 0 ≤ r ≤ 1 dă gradul în care q este subset fuzzy al lui p şi decipentru 0 < αa ≪ 1, Tj(A) măsoară gradul în care A este o submulţimefuzzy a categoriei wa

j . Dacă se creşte valoarea lui αa atunci se va mărinumărul de categorii, lucru nu întotdeauna benefic. Este deci sugeratca să se menţină valoarea αa la o valoare mică, de exemplu αa = 0.001;valori mai mici ale lui αa nu duc la o diferenţă semnificativă.

2. La pasul 3, dacă există mai multe categorii ale căror funcţie de ale-gere atinge maximul, vom considera pe acea categorie care are indiceleminim.

3. Parametrul ρa calibrează încrederea minimă pe care ARTa trebuie săo aibă vizavi de o categorie activată de o intrare pentru ca ARTa săaccepte această categorie, în loc de a căuta o categorie mai bună. Valorimici ρa duc la un grad mare de generalizare şi un număr mai mic decategorii ARTa.

56

Page 58: Sisteme Computationale Inteligente

4. Dacă inecuaţia (7.13) este îndeplinită, spunem că avem rezonanţă înARTa pentru pattern-ul de intrare curent. Datorită pasului de pre-procesare, conform (7.5), numitorul din (7.13) este exact dimensiuneaoriginală a pattern–urilor de intrare, n.

5. Aceiaşi paşi ca în 1 – 4 sunt efectuaţi în paralel pentru modulul ARTb,dacă nu cumva acesta este substituit cu un vector Nb−dimensional; înacest din urmă caz indicele nodului câştigător K este indicele de clasăcorespunzător intrării curente;

6. Când se intră în pasul 5, avem rezonanţă atât în ARTa cât şi în ARTb.Vectorul xab dă activarea Mapfield şi se foloseşte atât când ambelemodule F a

2 şi F b2 sunt active, i.e. la faza de învăţare, cât şi când F a

2

este activ şi F b2 e inactiv (faza de predicţie). În faza de învăţare xab are

forma din ecuaţia (7.15); în faza de predicţie acest vector este calculatca:

xab = wabJ (7.21)

7. Atunci când ambele module F a2 şi F b

2 sunt active, a J-a categorie câşti-gătoare din ARTa va corespunde unui vector de ponderi wab

J din Ma-pfield care leagă nodul F a

2 cu categoria F b2 prezisă. În paralel, pentru

modulul ARTb am obţinut vectorul de ieşire yb ca în ecuaţia (7.14).Operaţia fuzzy AND ne asigură că xab nu e plin cu valoarea zero dacăşi numai dacă valoarea de ieşire prezisă şi cea actuală coincid. Atuncicând categoria J este necomisă avem:

wabJ = (1, 1, . . . , 1) (7.22)

şi deci xab = yb. Când doar modulul F a2 este activ, matricea wab

dă valoarea prezisă: indecel categoriei din ARTb asociată cu intrareacurentă este unica poziţie k din linia j a matricei wab pentru carewab

jk = 1.

Ecuaţia (7.18) indică faptul că al J-lea nod din ARTa este legat cucategoria de ieşire K, iar asociaţia este permanentă.

8. Pentru βa (Pasul 7), există două moduri de învăţare:

(a) fast learning corespunde la a seta βa = 1 atât pentru nodurilecomise cât şi pentru cele necomise;

(b) fast-commit and slow-recode learning corespunde la a seta βa = 1pentru nod necomis şi βa < 1 pentru cele comise.

57

Page 59: Sisteme Computationale Inteligente

9. La faza de match tracking, datorită creşterii valorii lui ρa conform ecu-aţiei (7.19), nodul J nu va mai fi în stare să câştige în competiţiileurmătoare pentru patternul de intrare curent. Match tracking–ul vadeclanşa o nouă căutare în ARTa pentru a găsi un alt nod câştigător.Se poate ca asta să ducă la crearea unui nou nod în ARTa. Căutarea serepetă până când ρa > 1, sau până când se găseşte o categorie adecvatăîn ARTa.

10. Creşterea valorii δ în pasul 8 va creşte de asemenea şi numărul decategorii. Se foloseşte de regulă o valoare mică δ = 0.001

11. Ordinea de prezentare a patternurilor de instruire influenţează com-portamentul reţelei, adică numărul şi poziţiile categoriilor va diferi.Putem face antrenarea în paralel cu diferite permutări ale setului deintrare, apoi se contorizează voturile pentru fiecare pattern care trebuieclasificat.

Pasul de învăţare este repetat până când nu mai este nicio eroare pentrusetul de învăţare, sau până se atinge o eroare acceptabilă; dacă se vrea în-văştare incrementală atunci se face o singură trecere pe setul de antrenare.După învăţare, FAM poate fi utilizat pentru predicţie. În această fază, stra-tul F b

2 este inactiv şi F a2 este activ. Conform ecuaţiei (7.21), predicţia este

făcută doar pe baza lui wabJ .

Există o interpretare geometrică interesantă a categoriilor ARTa: fiecarecategorie j se reprezintă ca un hiperdreptunghi Rj, deoarece vectorul deponderi poate fi scris:

wj =(

uj ,vcj

)

(7.23)

undevcj =

(

vcj1, . . . , vcjn

)

(7.24)

(atât u cât şi v au acelaşi număr de elemente ca şi vectorii de intrare, adicăn). Vectorul uj defineşte un colţ al dreptunghiului Rj iar vj este alt colţ allui. Pentru n = 2, reprezentarea grafică este dată în figura 7.2. Dimensiunealui Rj este definită ca:

|Rj| = |vj − uj| (7.25)

Într–un system Fuzzy ART cu fast–commit, w(new)J = A = (a, ac) atunci

când J este un nod necomis, deci R(new)j este de fapt un punct reprezentând

pattern-ul de intrare preprocesat A. În timpul fiecărui pas de învăţare fast-learning, Rj se expandează la Rj ⊕ a, dreptunghiul minim care conţine Rj

şi a – vezi figura 7.3. Colţurile lui Rj ⊕ a sunt definite de a ∧ uJ şi a ∨ vJ ,

58

Page 60: Sisteme Computationale Inteligente

unde operatorul ∨ este definit ca operatorul fuzzy OR:

(p ∨ q)i = max (pi, qi) , i = 1 . . . , n (7.26)

pentru p şi q ca în ecuaţia (7.10).

Figura 7.2: Fiecare vector pondere wj are o interepretare geometrică precumun (hiper)dreptunghi Rj cu colţurile definite de uj şi vj

Figura 7.3: Expandarea de categorie în timpul fast learning: de la Rj ladreptunghiul mai mare conţinând Rj şi a.

Se poate arăta că:|Rj| = n− |wj| (7.27)

iar hiperdreptunghiul corespunzător unei categorii nu poate creşte oricât demult:

|Rj| ≤ (1− ρ)n (7.28)

Aceste proprietăţi sunt sumarizate de teorema:

59

Page 61: Sisteme Computationale Inteligente

Teorema 2 [15] Un sistem Fuzzy ART cu codificarea complementară, fastlearning şi termen de vigilenţă constant formează categorii hiperdreptunghiuricare converg în limită la o secvenţă arbitrară de vectori analogici sau binari.Hiperdreptunghiurile cresc monoton în toate dimensiunile. Dimensiunea |Rj|a unui hiperdreptunghi este n−|wj|, unde wj este vectorul pondere corespun-zător. Dimensiunea |Rj| este mărginită superior de n(1−ρ). Dacă 0 ≤ ρ < 1,numărul de categorii este mărginit, chiar dacă numărul de exemplare din se-tul de antrenare este infinit. Proprietăţi similare au loc pentru fast-learn,slow-recode, exceptând cazul în care este nevoie de prezentări repetate alefiecărei intrări înainte de stabilizarea sistemului.

Ca o remarcă generală, FAM aplică o învăţare bazată pe potrivire, con-form căreia pattern–urile sunt grupate în categorii pe baza unor măsuri desimilaritate. Dacă un pattern nu se potriveşte suficient de bine cu o categorieexistentă, atunci se va crea una nouă pentru a o reprezenta. Datorită acestuicomportament, FAM nu încearcă să minimizeze o funcţie de cost, evitândproblemele întâlnite în optimizarea funcţiilor. Această strategie de învăţareeste opusă celei bazate pe minimizarea erorii, care cer de regulă reantrenareadacă valoarea erorii este inacceptabilă sau dacă nişte pattern–uri prea diferitede cele învăţate anterior sunt prezentate reţelei.

60

Page 62: Sisteme Computationale Inteligente

Capitolul 8

Reţele neurale cu funcţii de

activare radială

8.1 Teorema lui Cover pentru separabilitate

Pentru cazul pattern-urilor neliniar separabile, perceptronul multistratpoate determina o funcţie de separare, datorită caracterului de aproximatoruniversal. Există şi o altă variantă de rezolva problema discernerii între claseneliniar separabile, folosind însă un separator liniar, bazată pe doi paşi:

1. setul dat iniţial cu pattern-uri din spaţiul originar este transformatîntr–un alt set în alt spaţiu, pentru care, în anumite condiţii, liniarseparabilitatea poate apărea cu probabilitate mare; fundamentul ma-tematic este dat de teorema lui Cover;

2. prin utilizarea metodei celor mai mici pătrate, se determină ponderi cepermit disocierea între clase.

Rezultatul este o reţea cu funcţii de activare radială, formată din 3 stra-turi:

• stratul de intrare alcătuit din unităţi senzoriale care conectează reţeauala mediu;

• stratul de neuroni ascunşi ce aplică transformări neliniare pe datele dinspaţiul de intrare. Neuronii din acest strat sunt antrenaţi prin instruirenesupervizată;

• stratul de ieşire este liniar, cu ponderi antrenate printr-o instruire su-pervizată. Acesta furnizează valoarea de ieşire pentru pattern-ul deintrare curent.

61

Page 63: Sisteme Computationale Inteligente

În marea majoritate a cazurilor se consideră ca funcţii de transformarefuncţii de tip Gaussian.

Următoarea teoremă arată motivul pentru care se face o transformare adatelor originare în alte date dintr-un spaţiu cu mai multe dimensiuni decâtcel originar:

Teorema 3 (Cover, 1965) O problemă de clasificare de pattern-uri trans-formate în mod neliniar într-un spaţiu cu mai multe dimeniuni este maiprobabil să devină liniar separabilă decât în spaţiul originar A, cu condiţia caA să nu fie dens populat.

Rezultatul este util, deoarece pentru cazuri liniar separabile, un perceptrondiscret poate să obţină un hiperplan de separare în timp finit. Pentru a seobţine o asemenea transformare, se pleacă de la un spaţiu A n dimensionalîn care se găsesc vectorii x1, . . . , xP şi se ajunge la un spaţiu m dimensional(m ≥ n) prin funcţia:

xφ→ φ(x) = (ϕ1(x), . . . , ϕm(x))

t (8.1)

unde ϕi(·), i = 1,m sunt funcţii reale neliniare; în reţeaua neurală funcţia ϕi

e calculată de neuronul i din stratul ascuns.Exemplu: considerăm problema XOR, în care 4 puncte sunt asignate la

două clase, astfel: punctele de coordonate (0, 0)t şi (1, 1)t aparţin unei clase,iar (0, 1)t şi (1, 0)t aparţin celeilalte clase. Nu se poate determina o dreaptăîn plan care să aibă de o parte a ei prima pereche de puncte şi de cealaltă adoua pereche. Folosim funcţiile ϕ1, ϕ2 : R2 → R:

ϕ1(x) = exp (−‖x− t1‖) , t1 = (1, 1)t

ϕ2(x) = exp (−‖x− t2‖) , t2 = (0, 0)t

unde x ∈ R2 iar ‖ · ‖ este norma Euclidiană L2. Pornind de la un pattern

de intrare x ∈ R2 se ajunge la un vector tot din R

2 dat de (ϕ1(x), ϕ2(x)).Valorile rezultate pentru funcţiile ϕ1,2 calculate în cele 4 puncte ale problemeiXOR sunt date în tabelul 8.1. Figura 8.1 dă reprezentarea punctelor tranfor-mate prin aplicarea celor două funcţii. Se observă că problema se tranformăîntr–una liniar separabilă, folosind modificări neliniare ale datelor iniţiale;mai mult, nu a fost nevoie în acest caz să se mărească dimensiunea spaţiuluide ieşire.

8.2 Funcţii cu activare radială

Teorema lui Cover afirmă că pentru o problemă ce nu e liniar separabilă,prin transformări adecvate cresc şansele de a se transforma într–una care e

62

Page 64: Sisteme Computationale Inteligente

Pattern de intrare ϕ1(xi) ϕ2(xi)x1 = (1, 1)t 1 0.1353x2 = (0, 1)t 0.3678 0.3678x3 = (0, 0)t 0.1353 1x4 = (1, 0)t 0.3678 0.3678

Tabela 8.1: Valorile funcţiilor ϕ pentru punctele problemei XOR

������

������

������������

Regiune de decizie

(ϕ1(x4), ϕ2(x4))

(ϕ1(x2), ϕ2(x2))

(ϕ1(x3), ϕ2(x3))

(ϕ1(x1), ϕ2(x1))

liniar separabilă. Să considerăm o reţea neurală de tip feedforward cu unstrat de intrare cu n noduri, un singur strat ascuns şi un strat de ieşire cu unsingur nod1. Această reţea produce o funcţie de la un spaţiu n–dimensionalla unul unidimensional:

s : Rn → R (8.2)

Funcţia s poate fi văzută ca o hipersuprafaţă Γ ⊂ Rn+1; hipersuprafaţa Γ

este necunoscută şi se determină pe baza setului de instruire. Există douăfaze care apar: una de instruire şi alta de generalizare. În etapa de instru-ire se foloseşte o procedură oarecare prin care se determină hipersuprafaţaΓ, plecând de la setul de date de antrenare. În etapa de generalizare se

1Ieşirea unică este pentru simplificarea prezentării. Pentru cazul în care ieşirea estedin spaţiul Rm sau avem o problemă de clasificare cu m clase stratul de ieşire va avea m

neuroni.

63

Page 65: Sisteme Computationale Inteligente

foloseşte o interpolare – vezi mai jos – pentru a determina valori de ieşirecorespunzătoare unor puncte din spaţiul de intrare Rn.

Problema de interpolare poate fi enunţată precum:Dându–se un set de P puncte diferite {xi ∈ R

n|i = 1, P} şi un set cores-punzător de P numere reale {di ∈ R|i = 1, P}, să se determine o funcţieF : Rn → R care satisface proprietatea de interpolare:

F (xi) = di, i = 1, P (8.3)

Tehnica funcţiilor cu activare radială (Radial Basis Functions, RBF) con-sideră că funcţia F are forma:

F (x) =P∑

i=1

wiϕi(‖x− xi‖) (8.4)

unde ϕi sunt funcţii neliniare reale, cunoscute ca funcţii cu activare radială.Punctele xi sunt “centrele” (parametri ai) funcţiilor RBF.

Impunând condiţia (8.3) asupra formei (8.4), avem următorul sistem liniarîn care necunoscutele sunt wi, i = 1, P :

ϕ11 ϕ12 · · · ϕ1P

ϕ21 ϕ22 · · · ϕ2P...

......

...ϕP1 ϕP2 · · · ϕPP

·

w1

w2...

wP

=

d1d2...dP

(8.5)

undeϕij = ϕi(‖xj − xi‖), i, j = 1, P (8.6)

Notăm cu d = (d1, d2, . . . , dP )t, w = (w1, w2, . . . , wP )

t, Φ = {ϕij}i,j=1,P .Numim matricea Φ matricea de interpolare. Se poate rescrie (8.5) sub forma:

Φ ·w = d (8.7)

Dacă matricea Φ este nesingulară, atunci ponderile sunt w = Φ−1d. Pentrudiscuţia asupra inversabilităţii lui Φ, considerăm teorema lui Michelli:

Teorema 4 (Michelli, 1986) Fie {xi}i=1,P un set de puncte distincte dinR

n. Atunci matricea de interpolare Φ este inversabilă dacă funcţiile ϕi auuna din formele:

1. funcţie multipătratică:

ϕi(ri) =√

r2i + c2, c > 0 (8.8)

64

Page 66: Sisteme Computationale Inteligente

2. funcţie inversă de multipătratică:

ϕi(ri) =1

r2i + c2, c > 0 (8.9)

3. funcţie Gaussiană:

ϕi(ri) = exp

(

− r2i2σ2

)

, σ > 0 (8.10)

unde ri este norma diferenţei vectorilor x şi xi (distanţa indusă de normă:d(x,xi) = ‖x− xi‖).

8.3 Reţele cu funcţii cu activare radială

O reţea cu funcţii cu activare radială este ilustrată în figura 8.1; ea constădin trei straturi:

1. stratul de intrare, care constă din n noduri sursă, unde n este dimen-siunea patternului de intrare x.

2. stratul ascuns, care e format din acelaşi număr de neuroni ca numărulde date din setul de antrenare, P ; fiecare neuron j, j = 1, P are funcţiecu activare radială ϕj(‖x− xj‖);

3. stratul de ieşire, care în cazul exemplificat este format dintr-un singurneuron. Acest strat poate însă avea oricâţi neuroni.

Pentru funcţiile ϕj vom considera funcţiile Gaussiene:

ϕj(‖x− xj‖) = exp

(

− 1

2σ2j

‖x− xj‖2)

, j = 1, P (8.11)

unde σj este lăţimea unei funcţii Gaussiene centrate în xj. De regulă tuturorGaussienelor li se asigneaza aceeaşi lăţime σ; diferenţa dintre funcţii estedată în acest caz de centrele xj.

Din punct de vedere practic se evită folosirea tuturor datelor din setulde instruire pentru crearea de funcţii de activare radială. Un motiv ar fică setul {xi, di} este în lumea reală cu zgomot, frecvent datorate erorilorde măsurare. Folosirea unui procedeu de interpolare plecând de la un setde date cu zgomot duce la rezultate proaste; în plus, numărul de nodurirezultat în reţeaua din figura 8.1 s-ar putea sa fie prohibitiv. Ca atare, în

65

Page 67: Sisteme Computationale Inteligente

...

x1

ϕ1(·)centrul x1

ϕ2(·)centrul x2

x2

w1

w2

wN

Σy = F (x)

xn

ϕP (·)centrul xP

Figura 8.1: Structura unei reţele RBF, plecând de la funcţia de interpolaredin ecuaţia 8.4.

practică numărul de noduri din stratul ascuns este mult redus. Funcţia F setransformă într-o funcţie de aproximare de forma:

F (x) =K∑

j=1

wjϕj(‖x− xj‖) (8.12)

unde dimensiunea vectorului de intrare x este aceeaşi ca şi cea de până acum,K < P iar punctele xj nu sunt neapărat din setul de instruire (ele pot provenidintr–un proces de grupare – clustering, de exemplu). Interpretarea ca reţeaneurală este dată în figura 8.2.

Pentru determinarea celor K valori vectoriale ale centrilor din stratulascuns se poate utiliza o metodă oarecare de clustering2. Vom prezenta încele ce urmează metoda k-means pentru clustering.

2Clustering: grupare.

66

Page 68: Sisteme Computationale Inteligente

...

x1

ϕ1(·)centrul x1

ϕ2(·)centrul x2

x2

ϕK(·)centrul xK

w1

w2

wK

Σy = F (x)

xn

Figura 8.2: Structura unei reţele RBF, folosind mai puţine noduri decât înfigura 8.1. Centrii xi, i = 1, K se obţin printr-un procedeu de clustering.

8.4 Clustering folosind algoritmul K-means

Clustering-ul este o formă de învăţare nesupervizată în care un set de ob-servaţii este partiţionat în grupuri de pattern-uri. Se urmăreşte ca o măsurăa similarităţii dintre perechi de observaţii ce aparţin aceluiaşi cluster să mi-nimizeze o anumită funcţie de cost. Pattern-urile care aparţin unui anumitgrup sunt similare între ele şi nesimilare cu pattern-urile din alt grup.

Considerăm un set de P puncte, {xi}i=1,P ce urmează să fie partiţionatîn K clustere3, K < P . Considerăm relaţia:

C(i) = clasa asignată pattern-ului xi, i = 1, P (8.13)

unde 1 ≤ C(i) ≤ K. Notăm cu d(xi,xj) o măsură a deosebirii dintre perechile

3Cel mai frecvent, valoarea lui K este furnizată de utilizator.

67

Page 69: Sisteme Computationale Inteligente

de vectori xi şi xj. Pentru clustering se cere minimizarea funcţiei:

J(C) =1

2

K∑

k=1

C(i)=k

C(j)=k

d(xi,xj) (8.14)

În algoritmul k-means drept măsură de similaritate se foloseşte pătratuldistanţei Euclidiene

d(xi,xj) = ‖xi − xj‖2 (8.15)

În urma procesului de clustering vor rezulta K centroizi – centri de clustere– notaţi µ̂k, k = 1, K.

Funcţia care se minimizează pentru realizarea procesului de clustering semodifică luând în considerare aceşti centroizi:

J(C) =1

2

K∑

k=1

C(i)=j

‖xi − µ̂j‖2 (8.16)

Presupunând funcţia C cunoscută, cum anume se poziţionează centroiziiastfel încât să se minimizeze J(C)? Algoritmul K-means determină niştevalori pentru µ̂j printr-un proces iterativ, astfel încât J(C) să scadă. Esteun algoritm euristic, nu garantează faptul că se ajunge la minimul global allui J(C). Algoritmul alege aleator K centroizi µ̂(1)

i , i = 1, K, valori fie dinsetul de instruire, fie setate la întâmplare la valori din spaţiul de intrare.Avem apoi o succesiune de iteraţii cu paşii:

• Pasul de asignare: Calculează:

S(t)k = {xi : ‖xi−µ̂

(t)k ‖ ≤ ‖xi−µ̂

(t)j ‖, ∀j = 1, K, j 6= k, i = 1, P}, k = 1, K

(8.17)adică pentru fiecare punct xi se determină care este cel mai apropiatcentroid de care aparţine; S(t)

k este mulţimea pattern–urilor din setulde instruire ce sunt cel mai apropiate de centroidul µ̂(t)

k , la iteraţia t.

• Modificarea centroizilor:

µ̂(t+1)k =

1

|S(t)k |

xi∈S(t)k

xi, k = 1, K (8.18)

unde |S(t)k | este numărul de elemente ale mulţimii S(t)

k .

68

Page 70: Sisteme Computationale Inteligente

Algoritmul K-means se opreşte atunci când pasul de asignare nu maimodifică mulţimile S

(t)k .

Nu există nicio demonstraţie că algoritmul converge către optimul global;fiind însă rapid în practică – adică necesitând puţini paşi până la oprire – sepoate reporni cu alte valori ale centroizilor iniţiali µ̂(1)

k , k = 1, K. Situaţiaîn care J(C) are valoarea cea mai mică în aceste încercări este reţinută.

Se consideră însă că iniţializarea centroizilor iniţiali µ̂(1)k , i = 1, K nu

ar trebui lăsată la voia întâmplării şi că se poate îmbunătăţi considerabilperformanţa algoritmului printr–o alegere îngrijită a lor. Un caz nefavorabileste dat în figura 8.4. Să considerăm un dreptunghi cu laturile de lungimeL ≫ l, având în cele patru vârfuri câte un punct xi ∈ R

2, i = 1, 4. Dacăconsiderăm K = 2 şi centroizii sunt aleşi iniţial la jumătatea laturilor delungime mai mare, atunci algoritmul se opreşte după o iteraţie cu J(C) =12· 4(

L2

)2= 1

2L2 (punctele x1 şi x3 aparţin clusterului de centroid µ̂

(1)i , iar

celelalte două celui de al doilea cluster). Dacă alegerea punctelor se face caîn figura 8.4, atunci se obţine valoarea optimă J(C) = 1

2l2 (centroizii fiind

de această dată pe verticală). Având în vedere că L poate fi luat oricât demare faţă de l, rezultă că o alegere neinspirată a centroizilor poate să ducăla o valoare oricât de depărtată faţă de optim pentru funcţia J .

��������

������������

��������

��������

x2

x1x3

x4

µ̂2

µ̂1

Figura 8.3: Caz nefavorabil pentru K-means la alegerea centroizilor iniţiali.

������������

��������

������������

��������

x2

x1x3

x4

µ̂2µ̂1

Figura 8.4: Alegerea optimă a centroizilor iniţiali.

69

Page 71: Sisteme Computationale Inteligente

Ca atare, s–a dezvoltat algoritmul K-means++ care are ca scop determi-narea unor centroizi iniţiali aleşi mai potrivit. Alegerea celor K centroizi seface după următorii paşi [14]:

1. Alege primul centroid aleator din setul de antrenare;

2. Pentru fiecare punct xi calculează D(xi) (1 ≤ i ≤ N), distanţa de la elpână la cel mai apropiat din centroizii determinaţi până la pasul curent;

3. Alege aleator un nou punct din setul de antrenare, folosind o probabi-litate de alegere o funcţie crescătoare cu distanţa dată de D;

4. Repetă paşii 2 şi 3 până când s–au ales K centroizi;

5. Aplică algoritmul K-means pentru centroizii astfel determinaţi.

Costul suplimentar indus de determinarea celor K centroizi ca mai suseste neglijabil faţă de efectele benefice asupra rezultatului final. Rezultateteoretice asupra comportamentului lui K-means++ se găsesc în [14].

8.5 Determinarea ponderilor

Determinarea ponderilor legăturilor dintre stratul ascuns şi cel de ieşireeste următorul pas. Problema este una de determinare a ponderilor pentruo problemă de regresie liniară şi se tratează cu tehnicile din secţiunile 2.3 şi2.4.

Pentru cazul în care problema este una de regresie în care pattern–urilede ieşire sunt din Rm, fiecare neuron de ieşire îşi poate ajusta setul de ponderiindependent de ponderile celorlalte ieşiri; se aplică una din cele două metodede mai sus.

8.6 Algoritmul de instruire a reţelei RBF

Sintetizăm pe baza expunerii de până acum procedura de instruire a uneireţele RBF. Stratul de intrare este fix, având numărul de noduri dat de di-mensiunea intrării. Stratul ascuns se obţine rulând algoritm de clustering(e.g. K-means precedat de K-means++) peste setul de antrenare şi rezul-tând K centroizi µ̂j , j = 1, K. Aceşti centri de clustere devin centrii unorfuncţii Gaussiene asignate nodurilor ascunse. Pentru fiecare astfel de Gaus-siană este asignată o aceeaşi lăţime σ, calculată ca:

σ =dmax√2K

(8.19)

70

Page 72: Sisteme Computationale Inteligente

unde dmax este distanţa maximă dintre centroizi. În stratul de ieşire sunt totatâtea noduri cât este dimensiunea spaţiului de ieşire. Ponderile legăturilordintre stratul ascuns şi stratul de ieşire se calculeaza pe baza algoritmuluiRLS.

71

Page 73: Sisteme Computationale Inteligente

Capitolul 9

Reţele neurale cu auto-organizare

[5], cap 7.

72

Page 74: Sisteme Computationale Inteligente

Capitolul 10

Calcul evoluţionist

Calculul evoluţionist este inspirat din teoria evoluţiei dezvoltate de cătreCharles Darwin şi de genetică – ştiinţa eredităţii. Au în comun faptul căfolosesc populaţii de elemente care sunt folosite pentru căutarea soluţiei uneiprobleme, spre deosebire de alte abordări care încercă îmbunătăţirea printr-un proces iterativ a unei singure valori.

10.1 Clasificare

Calculul evoluţionist se împarte în:

1. algoritmi genetici

2. programare evoluţionistă

3. strategii de evoluţie

4. programare genetică

Domeniile enumerate au concepte comune; dintre toate, cele mai multerezultate sunt dedicate domeniului algoritmilor genetici, dar la ora actualăexistă hibridizări ale acestor 4 domenii.

Cel care este creditat ca fiind pionierul domeniului algoritmilor geneticieste John T. Holland de la Universitatea din Michigan. El a introdus con-ceptul de populaţie de indivizi care participă la căutarea unei soluţii; deasemenea, a dat teorema schemelor. El a fost cel care a stabilit operaţi-ile care trebuie să se aplice unei populaţii genetice - selecţia, încrucişarea şimutaţia.

Programarea evoluţionistă (avându–l ca pionier pe Larry J. Fogel) folo-seşte ca operatori selecţia celui mai potrivit individ şi mutaţia, dar nu şi

73

Page 75: Sisteme Computationale Inteligente

încrucişarea. În timp ce algoritmii genetici văd procesul evolutiv ca fiindaplicat pe o populaţie de indivizi, programarea evoluţionistă vede evoluţiaca aplicându–se unei populaţii de specii. Fiecare element din populaţie esteinterpretat ca o specie întreagă.

Strategiile de evoluţie au fost dezvoltate de Ingo Rechenberg şi Hans-PaulSchwefel, care au experimentat diferite variante de mutaţie pentru rezolvareaunor probleme legate de optimizarea unor suprafeţe aflate în contact cu unfluid. Mutaţiile reprezentau perturbări ale unor stări, efectuând o căutare învecinătate. Multiplele variante de perturbare au construit un întreg domeniu.

Programarea genetică (Richard Friedberg) a pornit cu coduri programde lungime fixă. Prin modificări efectuate în mod automat asupra acestorprograme se dorea obţinerea unor variante optimizate. Esenţiale sunt aicimodul de reprezentare a acestor programe şi funcţiile de măsurare a calităţiicodului.

De cele mai multe ori, pentru o abordare dintr-unul din cele patru domeniise urmează paşii:

1. Iniţializează populaţia

2. Calculează performanţa fiecărui element din populaţie

3. Aplică un pas de selecţie

4. Aplică operaţii precum încrucişarea sau mutaţia

5. Reia de la pasul 2 până când se îndeplineşte o anumită condiţie.

Diferenţa între domenii constă în detaliile fiecărui pas. Paşii sunt bazaţipe alegeri de valori aleatoare, ceea ce dă de înţeles că rulări diferite pot ducela valori diferite. Totodată algoritmii nu garantează descoperirea unei valorioptime. De cele mai multe ori, însă nu este nevoie să se cunoască exactoptimul, ci o valoare suficient de bună. În practică, calculul evoluţionist dărezultate bune într–un timp rezonabil.

În cele ce urmează vom prezenta partea de algoritmi genetici.

10.2 Algoritmi genetici

Rolul mediului care apare ca factor modelator în teoria evoluţionistă estepreluat de către o funcţie scop. Vom detalia algoritmul pentru maximizareaunei funcţii f : [a, b] → R∗

+. Indivizii care alcătuiesc populaţia se numesccromozomi şi sunt alcătuiţi din gene.

Se porneşte cu o populaţie iniţială, care este supusă apoi unui şir deprocese de tipul:

74

Page 76: Sisteme Computationale Inteligente

1. selecţie: indivizii care sunt cei mai adecvaţi (faţă de valoarea funcţieice se vrea optimizată) sunt favorizaţi să apară de mai multe ori într-opopulaţie nouă faţă de indivizii mai puţin performanţi;

2. încrucişare: are loc un schimb de gene între perechi de părinţi, formându-se copii; aceştia se presupune că moştenesc şi combină performanţelepărinţilor.

3. mutaţie: se efectuează nişte modificări minore asupra materialului ge-netic existent.

Pas 1. Crearea unei populaţii iniţiale de cromozomi. Se consideră maimulte valori pentru variabila x ∈ [a, b]. Numărul acestor valori – numitdimendimensiunea populaţiei – este dat ca parametrul al algoritmului,n, dependent de problemă. Toate valorile sunt cuantificate prin cromo-zomi care sunt şiruri de k biţi – un bit reprezintă în acest caz o genă acromozomului, k fiind alt parametru de intrare.

Generarea celor n cromozomi se face aleator, prin setarea fiecărei genela valoarea 0 sau 1, la întâmplare. Se obţine astfel o populaţie iniţialăformată din cromozomii c1, . . . , cn.

Fiecare cromozom c (adica sir de k biţi) va produce un numar x(c) dinintervalul [a, b], astfel: dacă valoarea în baza 10 a cromozomului estev(c), 0 ≤ v(c) ≤ 2k − 1, atunci valoarea asociată din intervalul [a, b]este:

x(c) = a+ v(c) · b− a

2k − 1∈ [a, b].

Pas 2. Evoluţia populaţiei. În acest pas se obţin generaţii succesive ple-când de la populaţia iniţială; populaţia de la generaţia g + 1 se obţinepe baza populaţiei de la generatia g. Operatorii sunt selecţia, împere-cherea (crosssover, încrucişarea) şi mutaţia.

Pas 2.1. Selecţia. Pentru fiecare cromozom ci din populatie se calcu-lează funcţia obiectiv yi = f(x(ci)), 1 ≤ i ≤ n. Apoi se însumeazăvalorile funcţiilor obiectiv obţinute pentru fiecare cromozom înparte:

S =n∑

i=1

yi

Pentru fiecare din cei n cromozomi se calculează probabilitatea deselecţie:

pi =yiS, 1 ≤ i ≤ n

75

Page 77: Sisteme Computationale Inteligente

Pentru fiecare cromozom se calculează probabilitatea cumulativăde selecţie:

qj =

j∑

i=1

pi, 1 ≤ j ≤ n

Remarcăm că se obţine 0 < q1 < q2 < · · · < qn = 1. Cu câtcromozomul ci determină o valoare mai mare pentru funcţia f ,adică cu cât valoarea f(x(ci)) este mai mare, cu atât diferenţadintre qi şi qi−1 este mai mare.Se selectează n numere aleatoare uniform distribuite în (0, 1]. Pen-tru fiecare număr, dacă el se găseşte în intervalul (0, q1] atuncicromozomul c1 este ales şi depus într-o populaţie nouă; dacă acestnumăr se află în intervalul (qi, qi+1] atunci se alege cromozomulci+1. Remarcăm ca numărul de cromozomi prezenţi în noua po-pulaţie este tot n. Cu cât valoarea asociată unui cromozom estemai mare, cu atât cresc şansele lui spre a fi selectat şi depus înnoua populaţie. Este foarte probabil ca un astfel de cromozomvaloros să apară de mai multe ori in populaţia nouă; de asemenea,este foarte probabil ca un cromozom cu o valoare mică pentrufuncţia f să nu apară deloc.

Pas 2.2. Încrucişarea. (împerecherea, crossover) Pentru fiecare cro-mozom care a rezultat la pasul anterior se alege o valoare alea-toare, uniform distribuită în intervalul (0, 1]. Dacă această valoareeste mai mică decât un parametru pc (parametru al aplicaţiei, e.g.0.1), atunci cromozomul este ales pentru incrucişare. Se proce-dează astfel încât să se obţină un număr par de cromozomi (deexemplu se renunţă la ultimul dacă numărul lor este impar).Cromozomii aleşi se încrucisează astfel: primul selectat cu al doileaselectat, al 3-lea cu al 4-lea etc. Încrucişarea decurge astfel:

• se alege un număr aleator t intre 1 şi k − 1;• se obţin 2 cromozomi copii astfel: primul va conţine primele t

gene ale primului părinte şi ultimele k− t gene ale celui de–aldoilea părinte; al doilea copil conţine primele t gene ale celuide–al doilea părinte şi ultimele k− t gene ale primului părinte

• cei doi cromozomi copii îi vor înlocui în populaţie pe părinţi

Pas 2.3. Mutaţia. Populaţiei obţinute i se aplică operator de mu-taţie, astfel: pentru fiecare genă a fiecărui cromozom se alege ovaloare aleatoare, uniform distribuită în (0, 1]; dacă acest număreste mai mic decât o probabilitate de mutaţie pm (parametru al

76

Page 78: Sisteme Computationale Inteligente

aplicaţiei, e.g. pm = 0.01), atunci se modifică valoarea curentă agenei cu complementul său faţă de 1.

Populaţia obtinută în pasul 2 reia ciclul de evoluţie. După ce se executăcâteva astfel de evoluţii (sau număr de generaţii, sau un timp alocat procesu-lui este epuizat), se raportează valoarea celui mai bun cromozom din ultimageneraţie1.

Avantajul primar al algoritmilor genetici constă în schimbul de informaţiedintre indivizi realizat la etapa de încrucişare, adică schimbarea de blocuride date care au evoluat. O utilizare eficientă a algoritmilor genetici presu-pune crearea unor structuri de date pentru gene şi a unor operatori adecvaţiproblemei ce trebuie rezolvată2 – a se vedea secţiunea 10.4.

10.3 Fundamente teoretice

Studiul comportamentului algoritmilor genetici se face pe baza unor scheme(sau şabloane) care descriu colecţii de cromozomi. O schemă se reprezintăun şir de caractere construit cu simbolurile “0”, “1” şi “*”, unde “*” poatefi substituit cu orice bit. De exemplu, schema (∗0101) se potriveşte cu doicromozomi: (00101) şi (10101)3. Dacă o schemă are k simboluri “*”, atunciea poate să fie reprezentată de 2k cromozomi, iar un cromozom de lungimem poate fi descris de C0

m + C1m + · · ·+ Cm

m = 2m scheme.Pentru o schemă S definim ordinul ei (şi îl notăm cu o(S)) numărul de

poziţii pe care se află valorile 0 sau 1, adică numărul de poziţii fixate. Deexemplu, pentru schema S = (∗ 0 ∗ 1 1 0), o(S) = 4. Ordinul unei scheme dăgradul de specializare a ei şi este utilă mai departe în calcularea probabilităţiide supravieţuire a sa în cadrul mutaţiilor.

Lungimea unei scheme S, notată cu δ(S), este distanţa dintre prima şiultima poziţie fixată. Pentru schema dată mai sus, δ(S) = 6 − 2 = 4.Noţiunea de lungime a unei scheme este utilă pentru calculul probabilităţiide supravieţuire a unei scheme în cadrul operaţiilor de încrucişare.

Pentru o populaţie de indivizi aflată la momentul t al evoluţiei, vomnota cu ξ(S, t) numărul de cromozomi din populaţie care respectă schema S.De asemenea, vom considera valoarea medie a schemei din populaţia de laun timp t, notată cu f(S, t) şi definită ca suma valorilor cromozomilor din

1Sau se foloseşte strategia elitistă: se returnează cel mai bun individ al tuturor gene-raţiilor.

2S-a stabilit “ecuaţia” Genetic Algorithms + Data Structures = Evolution Programs,[12].

3În acest caz spunem că schema este reprezentată de cei doi cromozomi.

77

Page 79: Sisteme Computationale Inteligente

populaţie care satisfac schema S împărţită la numărul acestor cromozomi,ξ(S, t).

La pasul de selecţie, un cromozom A este copiat în populaţia următoarecu probabilitatea:

P (A) =f(A)∑

cromozom c

f(c)

unde însumarea se face după toţi cromozomii c ai populaţie curente. Dacăconsiderăm n ca fiind numărul de cromozomi din populaţie, atunci avem:

ξ(S, t+ 1) = ξ(S, t) · n · f(S, t)∑

cromozom c

f(c)

Cantitatea f(t) =∑

cromozom c f(c)/n este chiar valoarea medie a populaţieide la momentul t, deci avem:

ξ(S, t+ 1) = ξ(S, t) · f(S, t)f(t)

Numărul de reprezentanţi ai schemei S care vor exista la momentul t+1 estedependent de valoarea schemei dată de cromozomii care există în populaţiade la momentul t. De exemplu, o schemă S care produce o valoare relativmare a lui f(S, t) faţă de f(t) va impune creşterea numărului de reprezentanţiai săi. Dacă presupunem de exemplu că f(S, t) = f(t)+ε ·f(t) = f(t)(1+ε),∀t > 0 (unde ε > 0) atunci se poate arăta prin inducţie că:

ξ(S, t) = ξ(S, 0)(1 + ε)t, ∀t ∈ {1, 2, . . . }adică pentru scheme care au valoare medie desupra valorii medii a popu-laţiei numărul de reprezentanţi va creşte exponenţial cu timpul – respectivdacă valoarea schemei este sub medie, numărul de reprezentanţi obţinuti prinselecţie scade exponenţial.

În ceea ce priveşte încrucişarea, să presupunem că cromozomul c = (1010100)este selectat pentru reproducere; există 27 scheme care îl au pe c drept re-prezentant, de exemplu:

S1 = (∗01 ∗ ∗ ∗ ∗)şi

S2 = (1 ∗ ∗ ∗ ∗0∗)Să presupunem că în procesul de încrucişare tăietura se face după a patragenă:

c = (1 0 1 0 | 1 0 0)S1 = (∗ 0 1 ∗ | ∗ ∗ ∗)S2 = (0 ∗ ∗ ∗ | ∗ 0 ∗)

78

Page 80: Sisteme Computationale Inteligente

Se observă că pentru exemplul considerat schema S1 sigur se va regăsi într–undescendent (supravieţuieşte), deoarece valorile 0 şi 1 se regăsesc pe poziţiileiniţiale, în timp ce S2 are sanse de a fi distrusă. Intuitiv, este clar faptulcă lungimea mică a schemei S1 măreşte şansa de supravieţuire, faţă de S2

care poate fi uşor “spart” în cromozomii copii. Desigur, poziţia tăieturii esteimportantă.

Tăietura poate să apară uniform aleator în m− 1 poziţii. Probabilitateade distrugere a unei scheme este:

Pd(S) =δ(S)

m− 1

şi evident probabilitatea evenimentului contrar, reprezentând supravieţuireaeste

Ps(S) = 1− Pd(S) = 1− δ(S)

m− 1

Conform strategiei de alegere a cromozomilor ce se supun împerecherii, pro-babilitatea ca un cromozom să participe la încrucişare este pc, deci probabi-litatea de supravieţuire a unei scheme S este:

Ps(S) = 1− pc ·δ(S)

m− 1

Se mai poate lua în considerare faptul că o schemă S poate totuşi să su-pravieţuiască, dacă cromozomii care se încrucişează au pe poziţiile fixe aleschemei chiar valorile din S. Aşa ceva este posibil, chiar dacă puţin probabil.Ca atare, şansa de supravieţuire este exprimată printr–o inegalitate:

Ps(S) ≥ 1− pc ·δ(S)

m− 1

deci schemele de lungime mică au şanse crescute de supravieţuire.Combinând rezultatele obţinute pentru partea de selecţie şi încrucişare,

obţinem:

ξ(S, t+ 1) ≥ ξ(S, t) · f(S, t)f(t)

·[

1− pc ·δ(S)

m− 1

]

Mutaţia schimbă aleator biţi din cromozom cu complementul lor. Esteclar că pentru ca o schemă să supravieţuiască, poziţiile sale fixe nu trebuiesă fie alese pentru mutaţie. Probabilitatea ca un singur bit să nu fie modi-ficat este (1 − pm). Alegerile biţilor care să sufere mutaţie sunt evenimenteindependente, deci probabilitatea ca cei o(S) biţi ficşi ai unei scheme să semenţină (şi deci ca întreaga schema să se menţină) este:

Ps(S) = (1− pm)o(S)

79

Page 81: Sisteme Computationale Inteligente

Pentru că pm ≪ 1, putem aproxima (1− pm)o(S) cu 1− pmo(S). Am obţinut

că schemele cu ordinul mic au şanse crescute de supravieţuire.Efectul combinat al operaţiilor de selecţie, încrucişare, mutaţie este deci:

ξ(S, t+ 1) ≥ ξ(S, t) · f(S, t)f(t)

·[

1− pc ·δ(S)

m− 1− o(S) · pm

]

Se poate da acum enunţul teoremei schemelor, teorema fundamentală a al-goritmilor genetici datorată lui Holland (1975):

Teorema 5 (Teorema schemelor) Schemele scurte, de ordin mic, cu va-loare peste medie cresc ca număr de reprezentanţi în decursul generaţiilor.

S–a formulat următoarea ipoteză:Ipoteza blocurilor de construcţie, [12]. Un algoritm genetic execută unproces de căutare prin suprapunerea unor scheme scurte, de ordin mic şi devaloare mare, numită blocuri de construcţie. Se poate arăta că pentru o po-pulaţie de n cromozomi, numărul de scheme efectiv procesate este în ordinullui n3, ceea ce dă caracter de paralelism implicit al algoritmilor genetici: seprocesează nu doar o singură schemă, ci mai multe.

10.4 Problema reprezentării datelor în algorit-mii genetici

Reprezentarea indivizilor ca şiruri de biţi este nenaturală pentru multeprobleme practice. Să presupunem, de exemplu, problema comis-voiajorului:fiind date n oraşe şi distanţele dintre ele, să se determine un tur al lor, astfelîncât fiecare oraş să fie vizitat exact o singură dată, să se revină la oraşul deplecare iar costul total al drumului să fie minim4. O soluţie este dată ca opermutare a mulţimii {1, . . . , n}.

Pentru cazul n = 20, dacă folosim reprezentarea binară, putem vedea căcinci biţi sunt suficienţi pentru a reprezenta orice număr de la 1 la 20, deciar trebui să folosim 20 · 5 = 100 de biţi pentru reprezentarea unei soluţiipotenţiale. Să presupunem că la un moment dat avem grupul de 5 biţi 01101reprezentând oraşul cu numărul 13; prin aplicarea mutaţiei este posibil să seajungă la valoarea binară 11101, adică în zecimal 29, un oraş care nu există.S-ar obţine deci o valoare invalidă datorată unei reprezentări neadecvate a

4În termeni de grafuri: se cere deeterminarea unui ciclu Hamiltonian de lungime mi-nimă.

80

Page 82: Sisteme Computationale Inteligente

elementelor din problemă sau a unor operatori care nu sunt adaptaţi cores-punzător. La fel de bine, se poate ca prin mutaţie sau încrucişare să se obţinăvalori de oraşe repetate, deci un ciclu prematur.

Pentru cei 100 de biţi asociaţi problemei, spaţiul de căutare realizat este2100 ≃ 1030, în timp ce mulţimea tuturor ciclurilor hamiltoniene este – con-siderând primul oraş ca fiind fixat si neconsiderând soluţiile simetrice deforma A → B → C → A ≡ A → C → B → A – mulţimea permutărilor cu19!/2 ≈ 1017 elemente. În situaţia dată deducem că utilizarea unei codificăribinare conduce la un spaţiu de căutare mărit artificial, existând zone maridin spaţiul binar care nu corespund unor soluţii viabile.

Alte exemple de probleme aflate în aceeaşi situaţie pot fi încă date; seajunge la concluzia că varianta naivă de reprezentare a valorilor şi a opera-torilor genetici nu se potriveşte neapărat la orice problemă de căutare. Mo-delarea unui individ şi a operatorilor asociaţi trebuie să se facă ţinând contde domeniu şi de particularităţile problemei. Vor fi exemplificate codificăriadecvate pentru câteva probleme clasice.

O altă întrebare care se naşte este: cum procedăm când există constrân-geri? De exemplu, dacă vrem să maximizăm funcţia:

f(x, y) = x2 − y3 + 2 · x · sin(y)

cu condiţia ca variabilele x şi y să satisfacă:

1 ≤ x3 − cos(y) + y2 ≤ 5

cum încorporăm restricţia în algoritmul genetic? Dacă folosim varianta cla-sică de codificare a unui individ, împreună cu operatorii de încrucişare şi demutaţie prezentaţi, cum asigurăm faptul că operatorii daţi nu duc indiviziiîn zone în care restricţia nu este îndeplinită?

Pentru această din urmă problemă s–au dat următoarele variante:

1. impunerea de penalizări pentru indivizii care încalcă constrângerile;

2. implementarea unei metode de “reparare” a indivizilor care nu satisfacconstrângerile;

3. implementarea unor operatori de încrucişare şi de mutaţie care păs-trează indivizii în condiţiile impuse.

Pe marginea fiecăreia din cele trei variante există multiple versiuni:

• pentru penalizări, valoarea acestora poate fi constantă, sau să variezecu gradul în care se încalcă constrângerile date; această ultimă variantă

81

Page 83: Sisteme Computationale Inteligente

poate fi codificată sub forma unei funcţii logaritmice, liniare, pătraticeetc. O formă extremă de penalizare este eliminarea indivizilor careîncalcă restricţiile, dar trebuie dat răspuns la întrebarea: cu ce se umplelocul lăsat gol prin eliminare? sau se permite populaţie de dimensiunevariabilă? cei mai mulţi autori afirmă că această eliminare este preadură, în timp ce menţinerea unor indivizi penalizaţi oferă variabilitatepopulaţiei – se pot produce descendenţi valizi, chiar şi din cei care nurespectă constrângerile.

• pentru algoritmii de reparare – este posibil să se integreze cunoştinţedin domeniu în metodele de corecţie; trebuie zis însă că imaginareaunui algoritm de corecţie poate uneori să fie o problemă la fel de greaca şi rezolvarea problemei de la care s–a plecat.

• pentru ultima variantă – este cunoscut deja că orice tip de date trebuiesă vină cu un set de operatori dedicaţi care să permită prelucrareatipurilor; o codificare potrivită problemei împreună operatorii asociaţitrebuie să favorizeze (ideal: să garanteze) generarea de indivizi valizi.Aici se intervine cu cunoştinţe despre problema care trebuie rezolvată,cunoştinţe care, prin implementare, favorizează obţinerea de indivizicare nu încalcă (prea mult, sau deloc) restricţiile;

Pentru fiecare din abordări s–au studiat variante şi comportamente; stu-diul s–a făcut în mare măsură empiric, pe probleme concrete; la ora actuală,un rezultat precum teorema schemei este inexistent pentru alte codificări de-cât cea binară. Desigur, se poate folosi şi o combinaţie a celor trei variantede mai sus.

Pentru numeroase probleme practice s–a constatat experimental că repre-zentarea adecvată a indivizilor, împreună cu definirea unor operatori adecvaţişi cele 3 metode de mai sus dau rezultate mai bune decât aplicarea ad literama algoritmului genetic peste o formă binarizată a problemei.

Vom exemplifica pentru problema discretă a rucsacului: se dă un rucsacde capacitate C, un set de n obiecte având greutăţile Gi > 0 şi valorileasociate Vi > 0, 1 ≤ i ≤ n. Un obiect poate fi luat doar în întregime înrucsac; problema este: care sunt obiectele care trebuie încărcate, astfel încâtgreutatea totală să nu depăşească C iar valoarea cumulată să fie maximă?

Problema este NP-completă, deci la ora actuală nu cunoaştem un algoritmde complexitate polinomială care să o rezolve. Totodată, menţionăm că multeprobleme pot fi reduse la aceasta, de aici interesul acordat.

O reprezentare naturală a unui individ – respectiv încărcare de rucsac– este un vector x cu elementele xi, 1 ≤ i ≤ n, xi ∈ {0, 1}, valoarea 0

82

Page 84: Sisteme Computationale Inteligente

însemnând că obiectul nu este luat, iar 1 - că e adăugat în rucsac. Se impune,evident, condiţia:

n∑

i=1

xi ·Gi ≤ C

iar funcţia de maximizat – numită şi profit în acest caz – este:

P (x) =n∑

i=1

xi · Vi

10.4.1 Varianta cu penalizare

Pentru fiecare individ x se va considera valoarea sa val(x):

val(x) =n∑

i=1

xi · Vi − Pen(x)

unde Pen(·) este funcţia de penalizare:

Pen(x)

{

= 0, dacă x este viabil> 0, dacă x nu este viabil

Dacă valoarea funcţiei de penalizare depinde de gradul în care se face în-călcarea restricţiilor – gradul de încălcare poate fi de exemplu de diferenţadintre

∑n

i=1 xi ·Gi şi C – atunci se poate folosi o funcţie de tip logaritmic, li-niar, pătratic, exponenţial etc. Efectele alegerii unei asemenea funcţii au fostanalizate pe diferite situaţii; a se vedea [12] pentru rezultate experimentaleşi interpretarea lor.

10.4.2 Varianta cu reparare

Putem folosi aici tot codificarea binară. Algoritmul de corectare estesimplu: dacă setul de obiecte ales depăşeşte ca greutate totală capacitateaC, atunci se scot obiecte până când greutatea celor rămase devine acceptabilă(cel mult G). Vom transforma deci vectorul x în x′ = (x′

1, . . . , x′n) astfel încât

∑n

i=1 x′iGi ≤ C. Valoarea profitului P (x) se va calcula în urma corecţiei ca:

P (x) =n∑

i=1

x′i · Vi

Algoritmul de reparare al unui individ este:

83

Page 85: Sisteme Computationale Inteligente

Listing 10.1: Repararea unui vector invalid

function r epara r e (x , G , C ) r e tu rn s a vec to rbeginrucsac−sup ra inca r ca t := fa l sex′ := x

i f∑n

i=1 xi ·Gi > Cthen rucsac−sup ra inca r ca t := true

end i fwhile rucsac−sup ra inca r ca t = true

i := s e l e c t e a z a un ob i e c t din rucsac (#)scoa t e ob i e c t u l i din rucsac : x′

i := 0i f

∑n

i=1 x′i ·Gi ≤ C

then rucsac−sup ra inca r ca t := fa l seend i f

end whiler e turn x′

end

În ce priveşte metoda de selectare a lui i din linia marcată cu (#), avemvariantele:

• (reparare aleatoare) valoarea i se alege aleator din setul indicilor obiec-telor care se găsesc în rucsac;

• (reparare greedy) se alege obiectul cel mai uşor, sau cel care are raportulPi/Gi cel mai mic.

10.4.3 Codificarea adecvată a indivizilor

Vom prezenta o strategie de codificare a indivizilor diferită de cea binarăutilizată până acum, numită reprezentarea ordinală. Codificarea este largutilizată şi în alte probleme care presupun manipularea unor secvenţe devalori, de exemplu în problema comis-voiajorului. Vectorul x este cu compo-nente în baza 10, fiecare element xi având proprietatea că 1 ≤ xi ≤ n− i+1,∀i ∈ {1, . . . , n}. De exemplu, pentru vectorul x = (4, 3, 4, 1, 1, 1) asociat listede obiecte L = (1, 2, 3, 4, 5, 6) decodificarea se obţine astfel: se scoate elemen-tul de indice x1 = 4 din lista L, adică obiectul 4 şi îl adăugăm în rucsac; Ldevine (1, 2, 3, 5, 6); apoi se scoate elementul de indice x2 = 3 (adică obiectul3) din L şi îl adăugăm în rucsac, L devine (1, 2, 5, 6); se scoate elementul deindice x3 = 4 din L, adică obiectul 6, L devine (1, 2, 5) etc. Obţinem astfelordinea de depunere în rucsac: 4, 3, 6, 1, 2, 5. Fiecare cromozom codifică

84

Page 86: Sisteme Computationale Inteligente

astfel o ordine de adăugare a obiectelor în rucsac. Adăugarea se face numaidacă nu duce la depăşirea capacităţii rucsacului.

Se poate vedea că operaţie de încrucişare va duce întotdeauna la copiivalizi, adică petru un copil z = (z1, . . . , zn) avem că 1 ≤ zi ≤ n− i+ 1 dacăşi părinţii au aceeasi proprietate. Mutaţia este similară cu cea de la cazulbinar: o componentă aleasă pentru mutaţie, fie ea xi este modificată cu ovaloare aleatoare uniform distribuită în mulţimea {1, . . . , n− i + 1} diferităde xi.

Listing 10.2: Utilizarea codificării ordinale

procedure d e c o d i f i c a r e (x)begin

c o n s t r u i e s t e o l i s t a L de ob i e c t egreutateTota la := 0p r o f i tTo t a l := 0for i = 1, nj := xi

o := Lj

s t e r g e e lementul a l j −l e a din l i s t a Li f greutateTota la + Go ≤ Cthen begin

greutateTota la := greutateTota la + Go

p r o f i tTo t a l := p r o f i tTo t a l + Po

endend i f

end forend

Lista L se poate crea într–o ordine aleatoare, ca o permutare a mulţimii{1, . . . , n}.

Rezultate experimentale pentru cele trei variante de rezolvare sunt date în[12]. Concluziile experimentelor însă nu pot fi generalizate la orice problemăcare vine cu impunere de restricţii. Se exemplifică însă că diferenţele deperformanţă pot fi mari pentru aceste abordări.

10.5 Exemplu: problema orarului

Problema orarului este o altă situaţia practică care se abordează prinintermediul algoritmilor genetici. Problema este NP-completă. Are diferiteenunţuri, vom prezenta varianta dată în [12].

Se dau următoarele:

85

Page 87: Sisteme Computationale Inteligente

• o mulţime de profesori {T1, . . . , Tm}

• o listă de intervale de timp (ore) {H1, . . . , Hn}

• o listă de săli de clasă {C1, . . . , Ck}

Orarul trebuie să respecte următoarele cerinţe:

• există un număr predefinit de ore pentru fiecare profesor şi clasă;

• la un moment dat, la o clasă predă un singur profesor;

• un profesor nu poate preda la mai multe clase simultan;

• la fiecare clasă programată la o anumită oră trebuie să existe exact unprofesor

Mai avem şi constrângeri care ar trebui respectate; acestea sunt legatede:

• nicio “fereastră” în orarul elevilor, cât mai puţine în cel al profesorilor;

• preferinţe exprimate de profesori sau elevi: ore doar într–o anumităparte a zilei sau săptămânii;

• împărţire cât mai echilibrată a orelor;

• număr maxim de ore pe zi epntru elevi/profesori

Codificarea binară pentru această problemă, cu toate că este posibilă, poateapărea drept nenaturală; mai mult decât atât, există riscul ca spaţiul de cău-tare să se mărească artificial, precum la problema comis voiajorului. Putemsă codificăm un orar (un individ) ca fiind o matrice O cu m linii şi n coloane,unde liniile corespund profesorilor iar coloanele – orelor disponibile. Fiecarecelulă este fie liberă, fie conţine o clasă Ci, 1 ≤ i ≤ k.

Pentru reprezentarea dată, operatorii genetici ar putea fi5:

• mutaţia de ordin k: se iau 2 secvenţe adiacente formate din p elementeşi se interschimbă

• mutaţia de zile: se iau două zile şi se interschimbă între ele

• încrucişare: se porneşte de la două orare părinte O1 şi O2, se efectueazătăietură pe orizontală sau pe verticală şi se face interschimbarea deporţiuni, întocmai ca la cromozomii binari

5Dar nimic nu ne împiedică să concepem alţi operatori.

86

Page 88: Sisteme Computationale Inteligente

Este posibil ca să fie nevoie să se intervină cu algoritmi de corecţie dupăaplicarea unor astfel de operatori. Din punct de vedere practic, abordareaprin algoritmi genetici este confirmată ca o metodă funcţională de către maimulţi autori.

87

Page 89: Sisteme Computationale Inteligente

Capitolul 11

Sisteme fuzzy

11.1 Prezentare generală

Capitolul conţine o introducere a logicii fuzzy şi mulţimilor fuzzy1. Dome-niile sunt legate de modelarea incertitudinii din lumea reală, de raţionamentulaproximativ, de imprecizia în exprimare. Majoritatea conceptelor folosite înlumea reală sunt neclare, vagi, ambigue, dar cu toate aceste oamenii opereazăcu ele foarte bine.

Termenul de “fuzzy” a fost introdus de către Lotfi A. Zadeh, profesor laUniversity of California at Berkley, în lucrarea sa “Fuzzy Sets” [11]. Mulţimilefuzzy – sau mulţimile nuanţate – se bazează pe conceptul de grad de aparte-nenţă a unui element la o mulţime; acest grad este un număr din intervalul[0, 1], spre deosebire de mulţimile clasice care sunt văzute ca asignând gradede apartenenţă fie 0, fie 12. Într–o mulţime fuzzy, gradul de apartenenţă seexprimă printr-o funcţie cu valori în intervalul [0, 1].

Alături de teoria probabilităţilor, sistemele fuzzy sunt folosite pentru mo-delarea incertitudinii. Incertitudinea existentă în ceea ce priveşte rezultatularuncării unui zar este modelată prin variabile aleatoare - umrărindu-se de-terminarea probabilităţilor asociate diferitelor valori, sau comportamentulobţinut prin repetarea experimentelor etc. Tipul de incertitudine pe care îlabordează sistemele fuzzy este însă diferit. De exemplu, propoziţia “Mariaeste destul de înaltă” nu are o incertitudine de tip statistic în ea: nu estevorba de evenimente aleatoare repetate sau condiţionări probabiliste. Carac-

1Fuzzy: vag, neclar; în acest context este tradus în limba română şi ca “nuanţat”.2Se poate face o paralelă cu funcţia caracteristică definită pentru o submulţime A a lui

X:

fA(x) =

{

1 dacă x ∈ A

0 dacă x ∈ X \A

88

Page 90: Sisteme Computationale Inteligente

terul vag al unui sistem este o caracteristică intrinsecă a sa; ea nu este datăîn vreun fel de observaţii repetate sau încrederea în legătura dintre o starecunoscută şi una posibil influenţată de ea.

Insistând pe direcţia aceasta, putem afirma că modul în care se enunţăregulile de producţie bazate pe logica tradiţională:

Daca A atunci B

este aplicabil doar pentru cazul în care caracterul vag lipseşte cu desăvârşire,de exemplu în matematică. Totuşi, considerând regula: “Dacă e înnorat,atunci va ploua” realizăm că enunţul este vag, cel puţin din cauza următoare:noţiunea de înnorat este vagă – rareori cerul este în totalitate acoperit denori; vorbim de “parţial înnorat” sau “un pic înnorat” sau “foarte înnorat”şi niciunul din aceşti termeni nu are o caracterizare clară; dacă nu luămîn considerare aceste nuanţe, atunci regula anterioară ar fi utilizabilă doarpentru cazul în care cerul e complet acoperit de nori. Chiar şi “ploaia” poatefi nuanţată – picură, plouă torenţial etc.

Logica fuzzy este asociată deci cu incertitudinea nestatistică. Trăsăturaesenţială a teoriei mulţimilor şi a logicii fuzzy este manipularea riguroasă aincertitudinii. Se pun la dispoziţie modalităţi de definire, descriere şi analizăa caracteristicilor vagi.

11.2 Teoria mulţimilor fuzzy

În teoria clasică a mulţimilor, un element fie face parte dintr-o mulţime, fienu. În mulţimile fuzzy însă, apartenenţa la o mulţime se exprimă printr–ungrad de apartenenţă, pentru care valoarea este un număr cuprins între 0 şi 1.Putem vedea aceasta ca o generalizare a mulţimilor clasice: dacă un elementaparţine unei mulţimi clasice, atunci valoarea funcţiei de apartenenţă este 1,altfel 0 - de fapt, funcţia caracteristică a unei mulţimi.

Să considerăm de exemplu mulţimea oamenilor înalţi. Evident, putemspune că o persoană care are înălţimea de 2.10 metri face parte din aceastămulţime. La fel se poate spune şi despre un om cu înălţimea de 2 m sau de1.90 m; putem nuanţa aici faptele, spunând că ultimele două persoane aparţinîntr-o măsură mai mică acestei mulţimi. O persoană de 1.80 m sau mai puţinnu mai poate fi considerată ca făcând parte din mulţimea oamenilor înalţi.Soluţia schiţată aici este asignarea unor grade de apartenenţă la o mulţimepentru elementele în discuţie. Să considerăm tabelul 11.1 în care pentrudiferite exemple de înălţimi vom specifica gradul de apartenenţă la mulţimeaconsiderată. Mulţimea oamenilor înalţi este considerată din acest moment omulţime fuzzy (nuanţată).

89

Page 91: Sisteme Computationale Inteligente

Persoană Înălţime Grad de apartenenţăA 2.10 m 1B 2 m 0.8C 1.90 m 0.4D 1.80 m 0E 1.70 m 0

Tabela 11.1: Înălţimi şi gradul de apartenenţă la mulţimea fuzzy a oamenilorînalţi.

Observăm că o mulţime fuzzy se poate specifica prin perechi de elementede grad de apartenenţă/element. O notaţie mai compactă pentru tabelul11.1 este:

Înalt = {1.0/2.10, 0.8/2, 0.4/1.90, 0/1.80, 0/1.70}

Valorile extreme 0 şi 1 se pot interpreta astfel: dacă µA(x) = 1 atunci spunemcă x cu certitudine aparţine lui A, dacă µA(x) = 0 atunci x cu certitudinenu aparţine lui A.

O altă variantă este specificarea unei funcţii de apartenenţă µA(x), undeµA este o funcţie cu valori în intervalul [0, 1], A este o mulţime fuzzy, xeste un element din universul discursului pentru care se stabileşte gradul deapartenenţă la mulţimea A. Astfel, µÎnalt(2.10 m) = 1, µÎnalt(1.90 m) = 0.4etc.

Funcţiile de apartenenţă se pot reprezenta grafic, pe axa orizontală fiindvalori al elementelor, iar pe verticală valoarea funcţiei de apartenenţă, precumîn figurile 11.1 sau 11.2.

Figura 11.1: Reprezentarea grafică a funcţiei de apartenenţă pentru mulţimea“înalt”

Formele poligonale date în graficele din figura 11.1 şi 11.2 nu sunt singu-rele care se pot folosi. Se poate de exemplu utiliza o funcţie de tip Gaussian

90

Page 92: Sisteme Computationale Inteligente

Figura 11.2: Reprezentarea grafică a funcţiei de apartenenţă pentru mulţimea“cald”

pentru modelarea gradului de apartenenţă:

µCald(T ) = e−(T−25◦)2

50

unde T este temperatura exprimată în grade Celsius. Totuşi, funcţiile for-mate cu porţiuni liniare sunt mai uşor de calculat şi în practică au un compor-tament bun; eventuala lor nederivabilitate nu este o problemă. Din raţiunievidente, spunem că funcţia din figura 11.2 este triunghiulară.

În sistemele fuzzy un element poate să aparţină la două mulţimi fuzzy,simultan. De exemplu, o persoană cu înălţimea de 1.83 metri face partedin mulţimea oamenilor înalţi în măsura 0.13 şi totodată aparţine mulţimiioamenilor de înălţime medie în măsura 0.8 - a se vedea graficele din figura11.3. Remarcăm că noţiunile nu se exclud reciproc.

Figura 11.3: Valorile fuzzy “mediu” şi “înalt” reprezentate simultan

11.3 Operaţii cu mulţimi fuzzy

Raţionamentul presupune operaţii logice; o mare parte din noţiunile şioperaţiile din algebra booleană au fost preluate şi adaptate la logica fuzzy.

3Valoarea exactă se află intersectând o dreaptă verticală care trece prin valoarea 1.83de pe abcisă cu graficul funcţiei de apartenenţă.

91

Page 93: Sisteme Computationale Inteligente

Înainte de a defini aceste operaţii, este cazul să enumerăm două parado-xuri din logica binară:

1. (Paradoxul mincinosului, paradoxul cretanului) O persoană spune: “eumint”. Dacă presupunem că această propoziţie este adevărată, atunciînseamnă că spusele persoanei sunt false, deci de fapt ea nu minte,ceea ce e o contradicţie cu presupunerea iniţială. Dacă presupunem căafirmaţia persoanei este falsă, atunci înseamnă că dimpotrivă, persoananu minte, deci din nou contradicţie cu presupunerea noastră. Oricaredin cele două valori de adevăr am vrea să asociem afirmaţiei “eu mint”,ajungem la o contradicţie. Ori, cum doar una din valorile Adevărat şiFals pot fi asociate unei propoziţii4, avem un paradox.

2. (Paradoxul bărbierului) Într–un sat există un bărbier care barbiereştepe toţi bărbaţii care nu se bărbieresc singuri. Care este valoarea deadevăr a propoziţiei “Bărbierul se bărbiereşte singur”? Printr-un pro-cedeu asemănător cu cel anterior, se ajunge la concluzia că niciuna dincele două valori de adevăr nu pot fi asociate propoziţiei, pentru că s–arajunge la contradicţie.

Aceste probleme sunt rezolvate de către logica fuzzy, putându–se da valoride adevăr pentru propoziţiile discutate. Intuitiv, pentru ambele afirmaţii amputea spune că ele sunt tot atât de adevărate pe cât sunt de false.

Vom trece acum la definirea operaţiilor pentru mulţimi fuzzy. Definiţiileîi aparţin lui Zadeh.

11.3.1 Egalitatea mulţimilor fuzzy

În teoria clasică a mulţimilor, două mulţimi sunt egale dacă au exactaceleaşi elemente. Pentru că o mulţime fuzzy înseamnă elemente cu grad deapartenenţă la ea, spunem că două mulţimi fuzzy sunt egale dacă pentru do-menii de valori identice au exact aceleaşi valori ale funcţiilor de apartenenţă.

11.3.2 Incluziunea mulţimilor fuzzy

În teoria clasică a mulţimilor, o mulţime A este o submulţime a mulţi-mii B dacă orice element din A se găseşte şi în B. Pentru cazul mulţimilorfuzzy, folosim următorul exemplu ca suport intuitiv pentru definirea inclu-ziunii: mulţimea oamenilor foarte înalţi este inclusă în mulţimea oamenilorînalţi. Evident, pentru un element x pentru care µfoarte înalt(x) = m, valoa-rea asociată lui faţă de de mulţimea oamenilor înalţi este chiar mai mare:

4Conform principiului terţului exclus, a treia variantă nu este posibilă.

92

Page 94: Sisteme Computationale Inteligente

µînalt(x) = m + ε, ε > 0. Ca atare, spunem că mulţimea fuzzy A este in-clusă în mulţimea fuzzy B dacă cele două mulţimi conţin aceleaşi elementeşi µA(x) ≤ µB(x), ∀x. Desigur, şi alte definiţii sunt posibile.

11.3.3 Complementara unei mulţimi fuzzy

În teoria clasică a mulţimilor, complementul unei mulţimi A este mulţi-mea formată din toate elementele care nu aparţin lui A.

Pentru definiţia relativ la mulţimi fuzzy, pornim de la un exemplu: consi-derăm mulţimea oamenilor de înălţime medie, pentru care funcţia de aparte-nenţă este dată în figura 11.3. Se pune problema: când spunem că o persoanănu este de înălţime medie? Dacă persoana are înălţimea 1.80 m, evident căface parte din mulţimea oamenilor de înălţime medie; dacă are 1.90 m sau1.70 m, atunci e evident că nu face parte din ea. Pentru o persoană pentrucare gradul de apartenenţă la mulţimea oamenilor de înălţime medie este, săspunem, 0.7, pare rezonabil să spunem că ea nu aparţine la această mulţimecu măsura 1− 0.7 = 0.3. Putem deci defini valoarea de apartenenţă a com-plementului mulţimii ca fiind unu minus valoarea de apartenenţă la mulţime.Desigur, şi alte definiţii sunt posibile.

Definiţia dată contrazice principiul terţului exclus: in logica clasică sespune că ceva fie este A, fie este non-A. Gradul de adevăr pentru afirmaţiilediscutate în cele două paradoxuri poate fi luat 0.5, deci fiecare propoziţie areaceeaşi valoare de adevăr ca şi contrara ei.

11.3.4 Intersecţia a două mulţimi fuzzy

În varianta clasică, intersecţia a două mulţimi este o mulţime formată dinelementele comune celor care se intersectează.

Definirea pentru mulţimi fuzzy nu este unică; oricare ar fi varianta folo-sită, trebuie să se respecte următoarele:

1. operaţia să fie comutativă: µA∩B(x) = µB∩A(x)

2. de asemenea, să avem asociativitate: µ(A∩B)∩C(x) = µA∩(B∩C)(x)

3. monotonie: dacă valoarea funcţiei de apartenenţă a unui element la omulţime scade, atunci valoarea funcţiei de apartenenţă pentru mulţi-mea respectivă intersectată cu o alta nu trebuie să crească.

În practică, cel mai mic grad de apartenenţă relativ la cele două mulţimidetermină gradul de apartenenţă la intersecţie. Varianta de operator deintersecţie dată de către Zadeh este:

µA∩B(x) = min {µA(x), µB(x)}

93

Page 95: Sisteme Computationale Inteligente

Se poate arăta uşor că dacă A ⊂ B, atunci A∩B = A, în sens fuzzy, ceea ceeste în concordanţă cu ceea ce avem şi în teoria clasică a mulţimilor. Desigur,şi alte definiţii sunt posibile pentru acest operator.

11.3.5 Reuniunea a două mulţimi fuzzy

În teoria clasică a mulţimilor, reuniunea a două mulţimi este o mulţimeformată din toate elementele care se regăsesc în ele. Pentru definirea relativla mulţimi fuzzy, se iau în considerare proprietăţi similare cu cele de la inter-secţie (doar la monotonie apare diferenţa), iar varianta dată de către Zadeheste:

µA∪B(x) = max {µA(x), µB(x)}Se pot da şi alte definiţii pentru acest operator.

11.3.6 Operatori de compensare

În timp ce operaţiile din cadrul teoriei clasice a mulţimilor sunt unicdefinite, pentru mulţimile fuzzy există şi alte posibilităţi de definire a lordecât cele date mai sus. Operatorii de compensare tratează în special cazulreuniunii şi al interseţiei de mulţimi fuzzy. Intersecţia este des întâlnită încadrul regulilor fuzzy.

Folosind definiţia intersecţiei dată de Zadeh, valoare funcţiei de aparte-nenţă pentru intersecţia a 2 mulţimi fuzzy este controlată de cea mai micădin valorile existente. De exemplu, pentru regula “dacă A şi B şi C atunciD”, dacă valorile de apartenenţă ale lui A, B şi C sunt respectiv 0.2. 0.8,0.9, efectul pe care îl are A asupra rezultatului final este prea pronunţat. Înpractică, definiţia intersecţiei dată de Zadeh nu e întotdeauna adecvată.

S–au definit mai mulţi operatori de compensare. Ei formulează răspun-suri la întrebarea: cât de mult poate să compenseze creşterea unor variabilevalorile mici ale altora? Vom prezenta două variante ale acestor operatori:operatorul de medie şi operatorul gama.

Prin operatorul de medie se stabileşte că valoarea funcţiei de apartenenţăeste media valorilor individuale:

µX1∩X2∩···∩Xn(x) =

n∑

i=1

µXi(x)

nOperatorul gama este mai complex şi pare să reprezinte mai bine procesul

de decizie umană decât definiţiile lui Zadeh. El este definit ca:

µγ =

(

n∏

i=1

µi

)1−γ

·(

1−n∏

i=1

(1− µi)

94

Page 96: Sisteme Computationale Inteligente

unde 0 ≤ γ ≤ 1, iar n este numărul de valori fuzzy implicate în intersecţie.În practică, cel mai frecvent valorile lui γ sunt între 0.2 şi 0.4.

11.4 Reguli fuzzy

Regulile clasice au forma următoare:

Dacă A1 şi A2 şi · · · şi An atunci C

unde “A1 şi A2 şi · · · şi An” se numeşte antecedent sau premisă iar C esteconsecvent sau consecinţă sau concluzie. De exemplu:Dacă înălţimea bărbatului este mai mare de 1.80 m, atunci masa lui este maimare de 50 kg.

Regulile fuzzy păstrează această formă generală, dar pot să apară dife-renţe pe partea de consecvent. Cele două variante des folosite sunt datoratelui Mamdani:Dacă X1 este A1 şi . . . şi Xn este An atunci Y este Bşi respectiv lui Takagi, Sugeno şi Kang:Dacă X1 este A1 şi . . . şi Xn este An atunci Y = p0 + p1X1 + · · ·+ pnXn

unde Xi sunt variabile fuzzy de intrare, Ai sunt mulţimi fuzzy peste variabi-lele Xi (1 ≤ i ≤ n), Y este o variabilă fuzzy de ieşire, B este o mulţime fuzzydefinită peste valorile lui Y iar pj sunt coeficienţi reali (0 ≤ j ≤ n).

Pentru probleme de clasificare există următoarea formă de regulă:Dacă X1 este A1 şi . . . şi Xn este An atunci Y face parte din clasa i în măsuraGCi.

Nuanţarea5 este pasul prin care se combină valorile din antecedentul uneireguli, folosind operaţiile cu mulţimi fuzzy; pasul se aplică pentru fiecareregulă în parte. Prin combinarea regulilor date la pas de denuanţare seobţine o ieşire care poate fi folosită ca rezultat inferenţial sau ca indicaţie decontrol al unui sistem.

Exemplificarea acestor reguli se face pentru cazul unei centrale de încăl-zire, pentru care sunt date nişte reguli privind reglarea debitului de gaz astfelîncât să se obţină o temperatură potrivită. Se pleacă de la reguli în care sefolosesc noţiuni vagi (temperatură potrivită, variaţie mare, măreşte debituletc) şi se obţine o indicaţie pentru regulatorul de gaz.

Vom considera că avem valori de intrare precum temperatura interioară(notată TempIn), cea exterioară (TempExt), modificarea de temperaturăinterioară în ultimele 5 minute (DeltaTempIn); ca valoare de ieşire avemModificareDebit. Fiecare valoare de intrare concretă va avea un grad de

5În original: fuzzyfication.

95

Page 97: Sisteme Computationale Inteligente

apartenenţă fuzzy la diferite mulţimi (de exemplu, pentru TempIn avemapartenenţă la mulţimi precum foarte cald, foarte frig etc.

Pentru valoarea TempIn avem trei mulţimi fuzzy: rece, confortabil, preacald. Pentru TempExt avem mulţimile fuzzy foarte rece, rece, cald, foartecald şi fierbinte. Pentru DeltaTempIn definim mulţimile fuzzy: larg ne-gativ, mic negativ, aproximativ zero, pozitiv mic, pozitiv mare, iar pentruModificareDebit avem seturile fuzzy scade mult, scade puţin, nu schimba,creşte puţin, creşte mult.

Vom considera doar câteva reguli, suficiente pentru exemplificarea nuan-ţării şi denuanţării:

Regula 1: Dacă TempIn este confortabilă şi DeltaTempIn este aproximativzero, atunci ModificareDebit este nu schimba;

Regula 2: Dacă TempExt este rece şi DeltaTempIn este mic negativ, atunciModificareDebit este creşte puţin;

Regula 3: Dacă TempIn este prea cald şi DeltaTempIn este larg pozitivă,atunci ModificareDebit este scade mult ;

Regula 4: Dacă TempIn este rece şi DeltaTempIn este aproximativ zero,atunci ModificareDebit este creşte puţin.

Pentru TempIn, mulţimea confortabil se defineşte ca {0/15◦, 1/21◦, 0/27◦},interpretată ca o funcţie de apartenenţă de tip triunghiular. De exemplu,pentru 18◦ şi 24◦ gradul de apartenenţă este 0.5. Pentru rece avem mulţimeafuzzy {1/10◦, 1/16◦, 0/21◦}, iar prea cald este mulţimea {0/21◦, 1/27◦, 1/33◦}.

Pentru DeltaTempIn:

negativ mic = {0/− 4◦, 1/− 2◦, 0/0◦}aproape zero = {0/− 2◦, 1/0◦, 0/+ 2◦}larg pozitiv = {0/2◦, 1/4◦, 1/6◦}

Pentru TempExt, rece={0/− 1◦, 1/10◦, 0/21◦}.Să presupunem că temperatura interioară este de 20◦, diferenţa de tem-

peratură din ultimele 5 minute este −1.5◦ iar temperatura exterioară este de11◦.

Conform mulţimilor fuzzy date anterior, avem:

• pentru TempIn, µrece(20◦) = 0.25, µconfortabil(20

◦) = 0.75, µprea cald(20◦) =

0;

• pentru DeltaTempIn, µmic negativ(−1.5◦) = 0.80, µaproximativ zero(−1.5◦) =0.20, µlarg pozitiv(−1.5◦) = 0

96

Page 98: Sisteme Computationale Inteligente

• pentru TempExt, µrece(11◦) = 0.90

Aplicăm aceste valori celor 4 reguli fuzzy de mai sus. Ţinem cont de faptulcă antecedentele din reguli sunt exprimate cu conjuncţie, corespunzătoareinterseţiei de mulţimi, ceea ce în logica fuzzy se implementează prin funcţiamin. Obţinem:

Regula 1: 0.75 ∩ 0.20 = 0.20 = µnu schimba(ModificareDebit)

Regula 2: 0.90 ∩ 0.80 = 0.80 = µcreste putin(ModificareDebit)

Regula 3: 0 ∩ 0 = 0 = µscade mult(ModificareDebit)

Regula 4: 0.25 ∩ 0.20 = 0.20 = µcreste putin(ModificareDebit)

Activarea acestor reguli se face în paralel. Observăm că pentru regula atreia ieşirea este zero, deci ea nu se va aplica. Din regulile 2 şi 4 avem douăvalori pentru apartenenţa µcreste putin(ModificareDebit); se va lua maximulcelor două valori, deci µcreste putin(ModificareDebit) = 0.8.

Variaţia de debit este modelată la rândul ei fuzzy, aşa cum se arată înfigura 11.4.

1

−3 −2 −1 0 2

Scade putinScade mult

1

Nu schimba Creste putin Creste mult

debit

µ

(m cubi/sec)

Figura 11.4: Mulţimi fuzzy pentru debitul de gaz

Denuanţarea este operaţia prin care se obţine un răspuns concret la pro-blemă, adică se furnizează o valoare exprimată în metri cubi pe secundăpentru debitul de gaz. Plecând de la graficul anterior, se trasează conturulmărginit de orizontalele y = 0.2 - pentru nu schimba - şi y = 0.8 - pentru

97

Page 99: Sisteme Computationale Inteligente

creşte puţin. Se obţine figura geometrică desenată cu linie continuă în figura11.5, pentru care se determină centrul de greutate; verticala dusă prin acestcentru de greutate interesectează axa debitului la valoarea +0.76, aceastafiind indicaţia dată regulatorului de gaz: creşte cu 0.76 m3/s debitul de gaz.

1

−3 −2 −1 0 2

Scade putinScade mult

1

Nu schimba Creste putin Creste mult

debit

µ

(m cubi/sec)0.76

Figura 11.5: Procesul de denuanţare.

Există mai multe metode care se pot folosi pentru denuanţare; a se vedea[2] pentru detalii.

11.5 Măsuri ale gradului de nuanţare

În cazul unei mulţimi fuzzy se poate pune întrebarea: cât este ea denuanţată? Pentru o mulţime fuzzy discretă, se pot introduce câteva măsuricare cuantifică gradul de nuanţare. Acestea au ca scop măsurarea gradului deincertitudine, care apare, de exemplu, în cazul exprimării vagi. În continuare,prezentarea merge pe exemplele din [2].

Dacă considerăm mulţimea peştilor, atunci pentru diferite elemente demai jos avem gradele exprimate: µpeşti(biban) = 1.0, µpeşti(peştisor auriu) =1.0, µpeşti(căluţ de mare) = 0.8, µpeşti(balenă) = 0.0. Pentru mulţimea fuzzyflori, gradul de apartenenţă ar putea fi: µflori(trandafir) = 1.0, µflori(pâine) =0.0, µflori(lemn câinesc) = 0.5. Intuitiv, putem spune că mulţimea de floriexemplificată este mai vagă decât mulţimea peştilor: în ultimul caz, valorilede apartenenţă sunt mai apropiate de cele ale unei funcţii de apartenenţă dincazul unei mulţimi clasice, 0 şi 1.

98

Page 100: Sisteme Computationale Inteligente

Se preia din fizică şi din teoria informaţiei noţiunea de entropie, caremăsoară gradul de dezorganizare a unui sistem. Spre deosebire de teoriainformaţiei unde măsura entropiei este unic determinată6, în teoria mulţi-milor fuzzy sunt mai multe variante acceptate. Se pleacă de la o sumă deproprietăţi pe care ar trebui să le respecte o astfel de măsură entropică şi seintroduc mai multe funcţii care respectă o parte sau toate aceste proprietăţi.De exemplu, pentru o mulţime clasică, din care un element fie face parte, fienu, măsura gradului de nuanţare ar trebui să dea rezulatul 0 - i.e. o mulţimeclasică nu este vagă. De asemenea, cu cât sunt mai multe valori pentru carevaloarea funcţiei de apartenenţă este 0.5 sau apropiată de aceasta, cu atâtmulţimea este mai vagă: un element care aparţine cu măsura 0.5 la o mulţimefuzzy face şi nu face parte din mulţimea dată în aceeaşi măsură.

Înainte de a da diferite variante de măsurare a gradului de nuanţare,se introduce noţiunea de “mulţime mai ascuţită”, ce exprimă relaţia întredouă mulţimi fuzzy: spunem că o mulţime S∗ este mai ascuţită decât o altămulţime fuzzy S – ambele definite peste acelaşi univers al discursului – dacăµS∗(x) ≤ µS(x) pentru cazul în care µS(x) < 0.5 şi µS∗(x) ≥ µS(x) dacăµS(x) > 0.5; pentru µS(x) = 0.5 valoarea µS∗(x) poate fi oricât.

Proprietăţile de mai jos sunt punct de plecare pentru determinarea dife-ritelor funcţii de măsurare a gradului de nuanţare.

caracterul exact: H(A) = 0 dacă şi numai dacă A este o mulţime clasică;

maximalitatea: H(A) este maximă dacă µA(x) = 0.5, ∀x din universuldiscursului;

ascuţirea: H(A) ≥ H(A∗) dacă A∗ este mai ascuţită decăt A;

simetria: H(A) = H(A);

principiul includerii şi excluderii: H(A∪B) = H(A)+H(B)−H(A∩B)

O variantă de funcţie de măsurare a gradului de nuanţare, introdusă deDeLuca şi Termini şi care respectă toate cele 5 proprietăţi de mai sus este:

HDT (A) = −K

n∑

i=1

(µi log µi + (1− µi) log(1− µi)) (11.1)

unde K este un număr pozitiv oarecare. Varianta introdusă de Pal şi Paleste:

HPP (A) = Kn∑

i=1

(

µie1−µi + (1− µi)e

µi

)

(11.2)

6Abstracţie făcând de o constantă multiplicativă

99

Page 101: Sisteme Computationale Inteligente

Desigur, utilizatorul poate să definească alte variante de măsurare a graduluide nuanţare a unei mulţimi vagi.

100

Page 102: Sisteme Computationale Inteligente

Capitolul 12

Reţele neuro-fuzzy

[5], secţiunea 9.2.

101

Page 103: Sisteme Computationale Inteligente

Bibliografie

[1] Stanford Machine Learning, curs online, Coursera, Andrew Ng

[2] Computational Intelligence. Concepts to Implementations,Russell C. Eberhart and Yuhui Shi, Morgan Kaufmann, 2007

[3] Computational Intelligence. An Introduction, Andries P. Engel-brecht, John Willeys and Sons, 2007

[4] Neural Networks and Learning Machines, ediţia a treia, SimonHaykin, Prentice Hall, 2008.

[5] Inteligenţă computaţională, Răzvan Andonie, An-gel Caţaron, Universitatea Transilvania din Braşov,http://www.cwu.edu/~andonie/Cursul%20de%20IA%20Brasov.pdf

[6] An Elementary Introduction to Statistical Learning Theory,Sanjeev Kulkarni, Gilbert Harman, Willey, 2011

[7] A Brief Introduction to Neural Networks, David Kriesel, 2007,liberă la download

[8] Principiile inteligenţei artificiale, Dan Dumitrescu, Editura Albas-tră

[9] Algoritmi genetici şi strategii evolutive - aplicaţii în inteligenţaartificială, Dan Dumitrescu, Editura Albastră

[10] The ART of Adaptive Pattern Recognition by a Self-Organizing Neural Network, G. A. Carpenter and S. Grossberg,IEEE Computer, Vol. 21, No. 3, 1988

[11] Fuzzy Sets, Lotfi Zadeh, Information and Control, Vol. 8, 1965

[12] Genetic Algorithms + Data Structures = Evolution Programs,Zbigniew Michalewicz, 1996, Ed. Springer-Verlag

102

Page 104: Sisteme Computationale Inteligente

[13] Introduction to artificial neural networks, Jacek M. Zurada, 1992,West Publishing Company

[14] K-means++: the advantages of careful seeding, Arthur, D. andVassilvitskii, S., Proceedings of the eighteenth annual ACM-SIAM sym-posium on Discrete algorithms, pp. 1027–1035.

[15] Fuzzy ARTMAP: A Neural Network Architecture for In-cremental Supervised Learning of Analog MultidimensionalMaps,, G. A. Carpenter and S. Grossberg and N. Markuzon and J.H. Reynolds and D. B. Rosen, IEEE Transactions on Neural Networks,1992, vol. 3, no. 5, pp. 698–713.

[16] The Matrix Cookbook, Kaare Brandt Petersen, Michael Syskind Pe-dersen, 2012, Technical University of Denmark

103