Inteligență artiﬁcială [607689]

Inteligență artiﬁcială
Versiunea 4 martie 2020
Lucian M. Sasu, Ph.D.

Cuprins
1 Introducere 5
1.1 Rețele neurale . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Bazele biologice . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Diferențe între RN artiﬁciale și naturale . . . . . . . . 9
1.1.3 Aplicabilitate . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Calcul evoluționist . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Bazele biologice . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Cromozomi . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3 Diferențe între cromozomii biologici și cei artiﬁciali . . 11
1.2.4 Aplicabilitate . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Sistemele fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Tipuri de învățare în inteligența computațională . . . . . . . 12
1.4.1 Învățarea supervizată . . . . . . . . . . . . . . . . . . 12
1.4.2 Învățarea prin întărire . . . . . . . . . . . . . . . . . . 13
1.4.3 Învățarea nesupervizată . . . . . . . . . . . . . . . . . 13
1.5 Auto-organizarea . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Regresia liniară 16
2.1 Exemplu și notații . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Funcția de cost . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Metoda de căutare după direcția gradientului . . . . . . . . . 22
2.4 Metoda algebrică . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Overﬁtting, underﬁtting, regularizare . . . . . . . . . . . . . . 27
2.5.1 Overﬁtting, underﬁtting . . . . . . . . . . . . . . . . . 27
2.5.2 Regularizare . . . . . . . . . . . . . . . . . . . . . . . 29
3 Regresia logistică 32
3.1 Încadrare, motivație . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Regresia logistică binară . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Setul de instruire . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Reprezentarea ipotezei . . . . . . . . . . . . . . . . . . 33
3.2.3 Suprafața de decizie a regresiei logistice . . . . . . . . 35
3.2.4 Funcția de cost . . . . . . . . . . . . . . . . . . . . . . 36
1

3.2.5 Algoritmul de instruire . . . . . . . . . . . . . . . . . . 38
3.2.6 Regularizare . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Regresia logistică multinomială . . . . . . . . . . . . . . . . . 40
3.3.1 Funcția softmax . . . . . . . . . . . . . . . . . . . . . 40
3.3.2 Reprezentarea ipotezei . . . . . . . . . . . . . . . . . . 41
3.3.3 Funcția de cost . . . . . . . . . . . . . . . . . . . . . . 42
3.3.4 Algoritmul de instruire . . . . . . . . . . . . . . . . . . 42
3.3.5 Regularizare . . . . . . . . . . . . . . . . . . . . . . . 43
4 Rețele neurale artiﬁciale – fundamente 44
4.1 Încadrarea domeniului . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Neuronul biologic . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Modele de neuroni artiﬁciali . . . . . . . . . . . . . . . . . . . 47
4.3.1 Modelul McCulloch–Pitts . . . . . . . . . . . . . . . . 47
4.3.2 Modelarea neuronului pentru sisteme neurale artiﬁciale 47
4.4 Modele de rețea neurală artiﬁcială . . . . . . . . . . . . . . . 49
4.4.1 Rețea cu propagare înainte . . . . . . . . . . . . . . . 49
4.4.2 Rețele cu conexiune inversă . . . . . . . . . . . . . . . 51
4.5 Învățarea ca problemă de aproximare . . . . . . . . . . . . . . 52
4.6 Reguli de învățare . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6.1 Regula de învățare Hebbiană . . . . . . . . . . . . . . 54
4.6.2 Regula de învățare a perceptronului . . . . . . . . . . 54
4.6.3 Regula de învățare delta . . . . . . . . . . . . . . . . . 55
4.6.4 Regula de învățare Widrow-Hoﬀ . . . . . . . . . . . . 55
4.6.5 Regula de învățare prin corelație . . . . . . . . . . . . 56
4.6.6 Regula “câștigătorul ia tot” . . . . . . . . . . . . . . . 56
5 Perceptronul liniar 57
5.1 Motivație, deﬁniții, notații . . . . . . . . . . . . . . . . . . . . 57
5.2 Perceptronul liniar . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3 Algoritmul de instruire a perceptronului . . . . . . . . . . . . 60
5.4 Convergența perceptronului . . . . . . . . . . . . . . . . . . . 63
5.5 Algoritmul lui Gallant . . . . . . . . . . . . . . . . . . . . . . 65
5.6 Comentarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Perceptroni multistrat 67
6.1 Motivație pentru rețele neurale multistrat . . . . . . . . . . . 67
6.2 Setul de instruire . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.3 Rețeaua neurală multistrat . . . . . . . . . . . . . . . . . . . 70
6.3.1 Arhitectură . . . . . . . . . . . . . . . . . . . . . . . . 70
6.3.2 Funcții de activare . . . . . . . . . . . . . . . . . . . . 72
6.4 Pasul de propagare înainte . . . . . . . . . . . . . . . . . . . . 75
6.5 Funcții de cost . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.6 Inițializarea ponderilor rețelei . . . . . . . . . . . . . . . . . . 78
2

6.7 Algoritmul backpropagation . . . . . . . . . . . . . . . . . . . 78
6.8 Justiﬁcarea matematică a algoritmului . . . . . . . . . . . . . 82
6.9 Utilizarea rețelei . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.10 Discuții . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7 Memorii asociative bidirecționale 83
7.1 Distanța Hamming . . . . . . . . . . . . . . . . . . . . . . . . 83
7.2 Asociatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.3 Memoria asociativă bidirecțională . . . . . . . . . . . . . . . . 85
7.4 Funcția de energie a MAB . . . . . . . . . . . . . . . . . . . . 88
7.5 Comentarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8 Rețele neurale cu funcții de activare radială 91
8.1 Teorema lui Cover . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 Funcții cu activare radială . . . . . . . . . . . . . . . . . . . . 93
8.3 Rețele cu funcții cu activare radială . . . . . . . . . . . . . . . 95
8.4 Clustering folosind algoritmul K-means . . . . . . . . . . . . . 97
8.5 Determinarea ponderilor pentru RBF . . . . . . . . . . . . . . 100
8.6 Algoritmul de instruire a rețelei RBF . . . . . . . . . . . . . . 100
9 Fuzzy ARTMAP 102
9.1 Învățarea incrementală . . . . . . . . . . . . . . . . . . . . . . 102
9.2 Proprietăți dezirabile ale sistemelor instruibile . . . . . . . . . 102
9.3 Dilema stabilitate–plasticitate . . . . . . . . . . . . . . . . . . 103
9.4 Fuzzy ARTMAP . . . . . . . . . . . . . . . . . . . . . . . . . 104
9.4.1 Arhitectura rețelei FAM . . . . . . . . . . . . . . . . . 105
9.4.2 Algoritmul de învățare pentru FAM . . . . . . . . . . 107
10 Calcul evoluționist 114
10.1 Taxonomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
10.2 Algoritmi genetici . . . . . . . . . . . . . . . . . . . . . . . . . 115
10.3 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . . . 118
10.4 Problema reprezentării datelor în algoritmii genetici . . . . . 121
10.4.1 Varianta cu penalizare . . . . . . . . . . . . . . . . . . 124
10.4.2 Varianta cu reparare . . . . . . . . . . . . . . . . . . . 124
10.4.3 Codiﬁcarea adecvată a indivizilor . . . . . . . . . . . . 125
10.5 Exemplu: problema orarului . . . . . . . . . . . . . . . . . . . 126
11 Mulțimi și logică fuzzy 128
11.1 Prezentare generală . . . . . . . . . . . . . . . . . . . . . . . . 128
11.2 Teoria mulțimilor fuzzy . . . . . . . . . . . . . . . . . . . . . 129
11.3 Operații cu mulțimi fuzzy . . . . . . . . . . . . . . . . . . . . 131
11.3.1 Egalitatea mulțimilor fuzzy . . . . . . . . . . . . . . . 132
11.3.2 Incluziunea mulțimilor fuzzy . . . . . . . . . . . . . . 132
3

11.3.3 Complementara unei mulțimi fuzzy . . . . . . . . . . . 132
11.3.4 Intersecția a două mulțimi fuzzy . . . . . . . . . . . . 133
11.3.5 Reuniunea a două mulțimi fuzzy . . . . . . . . . . . . 133
11.3.6 Operatori de compensare . . . . . . . . . . . . . . . . 134
11.4 Reguli fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
11.5 Măsuri ale gradului de nuanțare . . . . . . . . . . . . . . . . . 137
4

Capitolul 1
Introducere
Inteligența computațională (IC) este un domeniu care combină elemente
de învățare automată, adaptare, evoluție și logică fuzzy pentru a rezolva
probleme care, abordate tradițional, sunt diﬁcil sau imposibil de abordat.
Este o ramură a inteligenței artiﬁciale. Subdomeniile majore ale inteligenței
computaționale sunt:
•modele de învățare parametrică
•modele de învățare neparametrice, precum rețele neurale1artiﬁciale,
Support Vector Machines, modele probabiliste;
•mulțimi și logică fuzzy;
•calcul evoluționist;
•imunitate artiﬁcială;
•inteligența mușuroiului.
Fiecare din aceste subdomenii a evoluat rapid și s–au impus ca poten-
țiale metode de rezolvare efectivă a unor probleme complexe și presante,
pentru care abordările uzuale sunt nefructuase. De regulă, prototipizarea
unui sistem inspirat din inteligența computațională este rapidă, iar pentru
o problemă se pot folosi mai multe abordări: de exemplu, optimizarea se
poate face prin algoritmi genetici sau prin anumite familii de rețele neurale.
Metodele din inteligența computațională sunt frecvent inspirate din bi-
ologie: rețelele neurale au pornit de la modelul imaginat pentru neuronul
biologic, calculul evoluționist este bazat pe teoria evoluției și pe genetică.
Sistemele fuzzy sunt introduse pentru a permite manipularea impreciziei,
altfel decât prin teoria probabilităților.
Este o mare diferență între abordarea clasică, algoritmică a unei pro-
bleme și cea dată de IC. În primul caz este pusă la bătaie toată abilitatea
1Sau “neuronale”
5

celui care imaginează algoritmul pentru a rezolva problema; este un demers
anevoios, depinzând esențial de imaginația, puterea de abstractizare și ex-
periența persoanei în cauză; evident, este un proces creativ, la ora actuală
efectuat exclusiv de oameni. Totodată, de cele mai multe ori rezultatele
sunt exacte; de asemenea, se are în vedere permanent micșorarea complexi-
tății de calcul a problemei respective, dar în destule situații o soluție exactă
presupune un efort de calcul sau resurse de memorie prohibitive.
Abordarea IC este total diferită: pentru rețele neurale sau algoritmi ge-
netici, deﬁnitorie este capacitatea de adaptare automată sau auto-organizare
la condițiile problemei. Este modelul inspirat din natură, unde un sistem
biologic preia semnale din mediu și printr-un proces de învățare se adap-
tează, astfel încât să își îndeplinească scopul, sau pentru a obține o mai
bună integrare. Soluția la care se ajunge nu este neapărat optimă, dar este
un răspuns suﬁcient de bun pentru problema propusă. În implementarea
unui sistem din cadrul IC accentul cade mai mult pe abilitatea sistemului
rezultat de a se adapta, de a învăța, decât pe imaginația celui care îl con-
cepe. Abilitățile de 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 ﬁ folosiți pentru o clasă largă de funcții,
nedepinzând atât de mult precum cercetările operaționale de ipoteze care în
practică pot ﬁ prea restrictive.
O deﬁniție a “inteligenței” potrivită pentru contextul de IC este:
Deﬁniț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 proprietatate
a tuturor entităților ce trebuie să ia decizii și al căror comportament este
condus de scop.
Deﬁniția de mai sus a fost dată în 1995 de către David Fogel, scoțând în
evidență elementul esențial al comportamentului inteligent și în particular
al inteligenței computaționale: adaptarea.
Rețelele neurale artiﬁciale reprezintă grupuri interconectate de neuroni
artiﬁciali 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ății
creierului biologic, precum și ca modalitate propusă pentru a obține sisteme
artiﬁciale capabile să recunoască șabloane. Exemple de rețele neurale și
algoritmi de instruire se găsesc în [7], [8], [18].
Sistemele fuzzy sunt introduse pentru a putea gestiona imprecizia, no-
țiunile vagi (“înalt”, “acum”) și aproximarea. Sunt elemente des întâlnite în
modelarea de limbaj sau în situații de cunoaștere incompletă. Teoria mul-
țimilor 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ât
6

cele din logica clasică, sau altfel zis, a unor grade de adevăr diferite. Este
variantă de realizare a raționamentului aproximativ.
Calculul evoluționist se ocupă în special cu optimizarea și de probleme
de căutare, bazate pe mecanismele preluate din genetică și evoluționism. Se
pleacă de la ideea evoluției unei populații de indivizi, ﬁecare din ei ﬁind o
soluție potențială a problemei ce se vrea rezolvată. Domeniul include algo-
ritmii genetici, programarea evoluționistă, programarea genetică și strategii
de evoluție.
Sistemele rezultate prin inteligență computațională pot reprezenta hi-
bridizări ale celor de mai sus; de exemplu, există sisteme neuro-fuzzy, iar
ajustarea parametrilor pentru un sistem adaptiv se poate face prin algo-
ritmi genetici. 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 timpului, ajungând la
performanțe care astăzi nu sunt accesibile calculatoarelor electronice: de
exemplu, recunoașterea de imagini, speciﬁcă animalelor; sau interpretarea
ecoului reﬂectat 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 pentru
cele mai performante sisteme electronice actuale.
Studiile efectuate în ultimul secol au permis enunțarea unor prinicipii
asupra modului de funcționare a sistemelor neurale biologice; suntem însă
departe de a cunoaște toate detaliile funcționale și structurale. Chiar și
așa, prin implementarea modelelor obținute, rezultatele sunt mai mult decât
notabile.
Figura 1.1 ([6]) reprezintă cel mai comun tip de neuron natural. În
scoarța neurală există circa 86 de miliarde de neuroni interconectați, ﬁecare
putând avea până la 104conexiuni cu alți neuroni; modul de grupare a
acestora și interdependențele nu sunt pe deplin cunoscute.
Un neuron artiﬁcial are o structură asemănătoare, ﬁind un element de
procesare conectat cu alte elemente ce preia intrare de la niște neuroni și
produce o ieșire ce devine intrare pentru alți neuroni; legăturile neurale sunt
niște coeﬁcienți numerici, iar prin algoritmi de învățare se obține adaptarea
convenabilă a rețelei neurale. Adaptarea (sau învățarea) este aspectul esen-
țial al rețelelor neurale: plecând de la seturi de date, se detectează automat
șabloanele existente și se construiesc niste modele care pot ﬁ folosite mai
departe.
7

Figura 1.1: Neuron natural [6]
Figura 1.2: Neuron de tip Purkinje din cortexul cerebelar; sursa
http://en.wikipedia.org/wiki/Neuron.
8

1.1.2 Diferențe între RN artiﬁciale ș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ă excite
sau să inhibe un neuron cu care este conectat; în modelarea de RN artiﬁci-
ale, o pondere de legătură este ﬁe excitatoare, ﬁe inhibitoare, dar forma ei
este ﬁxată după ce s–a făcut învățarea.
O altă diferență (și punct de critică pentru rețelele neurale artiﬁciale)
este faptul că modelarea semnalului făcută sub formă de valori continue este
de negăsit în rețelele biologice; în RN biologice se folosesc de fapt trenuri de
impulsuri care sunt transmise către neuroni, apărând variație în frecvența
semnalului. Acest aspect a fost abordat 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 cicli de timp între 10 și 100 milisecunde;
implementările de RN artiﬁciale funcționează pe procesoare de câtiva giga-
hertzi, deci cu un ciclu de mai puțin de o nanosecundă. Chiar și așa, rețelele
neurale biologice sunt cu mult mai performante decât cele artiﬁciale.
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 para-
lelism masiv, ce e încă atins în modelel neurale actuale.
1.1.3 Aplicabilitate
•Clasiﬁcarea – pe baza unui set de date de forma (intrare – ieșire asoci-
ată) se construiește un sistem care detectează asocierile dintre datele
de intrare și etichetele ce le sunt asociate; etichetele – sau clasele –
sunt dintr-o mulțime discretă, ﬁnită. Clasiﬁcarea se folosește pentru
recunoașterea automată a formelor, recunoașterea vorbirii, diagnoză
medicală și altele.
•Estimarea de probabilitate condiționată – similar cu clasiﬁcarea, dar
se produce un sistem care estimează probabilitatea ca un obiect să
aparțină unei clase, date ﬁind trăsăturile de intrare; de exemplu, dat
ﬁind conținutul unui mesaj de email care este probabilitatea ca să ﬁe
mail legitim sau spam;
•Regresie – asemănător cu clasiﬁcarea, dar ieșirile nu sunt dintr-o mul-
țime discretă și ﬁnită, ci valori numerice continue;
•Memorie asociativă , sau memorie adresabilă prin conținut – se poate
regă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 unei căutări – dar apropiată de modul în care se face regăsirea
elementelor reținute de către o persoană.
9

•Grupare automată (clustering) – pe baza similarităților existente într–
un set de date, se detectează grupările de date; elementele dintr-un
grup sunt mai apropiate între ele decât de altele din alt grup;
•Detectara automată de trăsături – a acelor elemente care fac ca proce-
sul de recunoaștere a unui obiect să ﬁe mai bun decât dacă se folosesc
cunoștințe speciﬁce domeniului;
•Controlul sistemelor – folosite pentru cazul în care un proces trebuie să
ﬁe ghidat pentru a se încadra în parametri; utilitatea rețelelor neurale
provine din faptul că nu se presupune că există dependențe liniare
între acțiune și reacțiune.
1.2 Calcul evoluționist
Principalele paradigme2ale 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 nu
există hibridizări;
•strategiile de evoluție – similari cu algoritmii genetici, dar se folosește
recombinarea î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ă. Genetica
tratează ereditatea, adică transmiterea trăsăturilor de la părinți la urmași.
Astfel, adaptarea obținută în generațiile anterioare este preluată de către
urmași și continuată. Codiﬁcarea caracteristicilor este dată de cromozomi.
Noțiunile și mecanismele sunt preluate din teoria eredității întemeiată de
Gregor Mendel și teoria evoluționistă a lui Charles Darwin.
2“Paradigma este o construcție mentală larg acceptată, care oferă unei comunități
sau unei societăți pe perioada îndelungată o bază pentru crearea unei identități de sine (a
activității de cercetare de exemplu) și astfel pentru rezolvarea unor probleme sau sarcini.”,
conform Wikipedia.
10

1.2.2 Cromozomi
Cromozomiisuntstructuridininteriorulcelulelorcaremențininformația
genetică. În cazul oamenilor, sunt 46 de cromozomi, jumătate moșteniți de
la tată și jumătate de la mamă. Cromozomii sunt alcătuiți din gene, ﬁecare
ﬁind identiﬁcată prin locația pe care o ocupă și prin funcția asociată.
1.2.3 Diferențe între cromozomii biologici și cei artiﬁciali
Cromozomii artiﬁciali sunt reprezentări simpliﬁcate a celor biologici. În
timp ce neuronii biologici sunt secvențe de acizi nucleici, cromozomii artiﬁ-
ciali sunt șiruri de cifre binare.
Cromozomii biologici care deﬁnesc organismele vii variază în lungime,
chiar dacă de la un organism la altul din aceeași specie pentru un cromozom
speciﬁc lungimea este constantă. În algoritmii genetici, lungimea este ﬁxă.
La reproducerea indivizilor dintr-o populație naturală, jumătate din in-
formația genetică este preluată de la tată și jumătate de la mamă. În algo-
ritmii genetici, procentul de combinație poate să difere.
1.2.4 Aplicabilitate
Principala arie de aplicare este optimizarea, pentru situațiile în care că-
utarea soluției cere un timp îndelungat. Algoritmii genetici sunt folositi ca
o metodă euristică; problemele abordate sunt din cele mai diverse — op-
timizarea unui plan de lucru sau circuit, balansarea încărcării, optimizarea
ingredientelor, 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 preluate
din partea comportamentală umană. Este o modalitate de manipulare a in-
certitudinii, modelând imprecizia, caracterul vag, ambiguitatea. Este vorba
de un alt tip de incertitudine decât cel modelat prin intermediul variabilelor
aleatoare din cadrul teoriei probabilităților. Se folosește pentru modelarea
impreciziei lingvistice (“Maria e înaltă”, “Livrarea se face în aproximativ 3
ore”). Teoria mulțimilor fuzzy a fost dezvoltată de către Lotﬁ Zadeh înce-
pând cu 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
11

Toate variantele sunt evaluate și în funcție de rezultat se ajustează viteza
ventilatorului. Modelarea conceptelor de “very cold”, “normal” etc. se face
prin mulțimi vagi.
Pornind de la acest curent, s-au dezvoltat următoarele: fuzziﬁcare/de-
fuzziﬁcarea, sisteme de control fuzzy, jocuri fuzzy, matematică fuzzy, teoria
măsurii fuzzy, căutare fuzzy.
Teoria fuzzy este folosită intens în sisteme ce presupun control: camere
video, sisteme de frânare sau accelerare, sisteme de control al debitului și
presiunii etc. De asemenea, sistemele expert din domeniu medical, ﬁnanciar,
navigațional, diagnoza mecanica etc. se folosesc masiv de suportul pentru
imprecizie și ambiguitate.
1.4 Tipuri de învățare în inteligența computațio-
nală
Învățarea permite unui sistem să se adapteze la mediul în care operează;
pe baza semnalelor provenite din exterior, sistemul inteligent își modiﬁcă
parametrii pentru o îndeplinire cât mai bună a sarcinii propuse. Trebuie
fă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ă.
1.4.1 Învățarea supervizată
Se presupune că există un “profesor” care poate prezenta un set de date
de instruire având forma (intrare — ieșire asociată), relevant, care este pre-
luat de către sistem și învățat. Se folosește o funcție de eroare, care măsoară
cât de departe este răspunsul cerut față de cel furnizat de sistem; pe baza
erorii se desfășoară un proces de ajustare a valorilor din sistemul computa-
țional inteligent până când eroarea scade sub un anumit prag. Rezultatul
ﬁnal este obtinerea unui sistem ce poate să furnizeze o valoare de ieșire
adecvată pentru o 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ă.
12

Figura 1.3: Schema de lucru pentru învățare supervizată
1.4.2 Învățarea prin întărire
Învățarea prin întărire (eng: reinforcement learning) este similară cu
învățarea supervizată, numai că în loc de a se furniza ieșirea asociată unei
intrări, se pune la dispoziție o indicație care arată cât de bine a acționat
sistemul respectiv. Acesta este un sistem bazat pe critică sau aprobare, ﬁind
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ă ﬁe precizată sistemului!).
Rolul profesorului este luat de un critic, care precizează în ce măsură ieșirea
obținută se apropie de cea dorită. Pe termen lung, sistemul își va modiﬁca
propriul comportament astfel încât să se reducă criticile obținute.
Acest tip de învățare este plauzibil din punct de vedere biologic, deoarece
o ﬁință sau un agent artiﬁcial inteligent va încerca să își minimizeze starea
de disconfort prilejuită de comportament neadecvat. Rolul criticului este
dat aici de mediul înconjurător. Schema de lucru este dată în ﬁgura 1.4.
1.4.3 Învățarea nesupervizată
Spre deosebire de precedentele moduri de învățare, în acest caz nu se
primește niciun semnal de tip ieșire sau critică asociată. Sistemului capabil
de 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 analiza
asociererilor, gruparea pe baza de similaritate si estimarea de densitate de
probabilitate.
Schema de lucru este dată în ﬁgura 1.5. Acest tip de adaptare este pre-
zent în rețelele de tip clustering, analiza de asocieri, analiza componentelor
principale etc.
13

Figura 1.4: Schema de lucru pentru învățare prin întărire
Figura 1.5: Schema de lucru pentru învățare nesupervizată
14

1.5 Auto-organizarea
Auto-organizarea, alături de învățare, este un alt atribut important al
sistemelor 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 este
deﬁnită astfel:
Deﬁniția 2. Spunem că un sistem se auto-organizează dacă, după ce se
primesc intrarea și ieșirea unui fenomen necunoscut, sistemul se organizează
singur astfel încât să simuleze fenomenul necunoscut [5].
sau:
Deﬁniția 3. Sistemele cu auto-organizare se auto-organizează pentru a cla-
siﬁca percepțiile din mediu în percepții ce pot ﬁ recunoscute, sau șabloane
[5].
15

Capitolul 2
Regresia liniară
2.1 Exemplu și 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 inﬁnită de valori. Ca exemplu, să presupunem că vrem
să facem predicția costului unei proprietăți imobiliare, dată ﬁind suprafața
sa. 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ă aproximarea
prețului (număr real) pentru alte proprietăți de interes. O exempliﬁcare este
dată în ﬁgura 2.1.
Figura 2.1: Reprezentarea graﬁcă a datelor de vânzare a unor proprietăți
imobiliare. Pe abscisă este măsurată suprafața, pe ordonată este prețul [1].
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ă care să
16

aproximeze “cât mai bine”1norul de puncte reprezentat2. Eroarea pentru
cazul unui punct este inﬂuențată de diferența dintre valoarea actuală și cea
prezisă de model – aici modelul este o dreaptă. Se constată apoi care este
valoarea de pe dreaptă, corespunzătoare lui 1300 (ﬁgura 2.2). Estimarea
obținută este de circa 220000.
1300220
Figura 2.2: Aproximarea prețului pentru o suprafață de 1300 feet2.
Modelul de predicție ﬁgurat mai sus este un model liniar:
pret =a·suprafata +b
undeașibsunt coeﬁcienți reali ce vor ﬁ determinați; ase numește pantă
(eng: slope) iar btermen liber (eng: intercept). Desigur, se pot folosi forme
polinomiale de grad mai mare decât 1, sau modele local liniare, sau rețele
neurale etc. Alegerea celui mai bun model pentru un set de date cunoscut
este o problemă în sine. Preferarea unui model liniar se motivează prin aceea
că în practică se dovedește a ﬁ suﬁcient de bun pentru multe probleme, iar
modelele mai simple se recomandă a ﬁ încercate printre primele. În plus, un
model liniar este ușor de interpretat: creșterea valorii variabilei suprafata
cu o unitate duce la creșterea prețului total cu aunități monetare; valoarea
beste prețul de pornire.
Avem mai sus un exemplu de instruire supervizată: se pornește de la
un set de date cu perechi formate din valoare de intrare ( e.g.suprafața)
1O formulă pentru a măsura cât de bună e aproximarea rezultată se va da în secțiunea
2.2.
2Pentru cazul cu mai multe date de intrare se obține o varietate liniară – plan pentru
2 dimensiuni de intrare etc. – dar modul de determinare a ei este similar cu ceea ce se
prezintă pentru o singură variabilă.
17

și valoare de ieșire asociată ( e.g.costul suprafeței). Se cere determinarea
unui model care să ﬁe folosit pentru prezicerea (aproximarea) unor valori
de ieșire, date ﬁind valori de intrare furnizate; pentru exemplul considerat,
vrem să vedem care e costul estimat al unor suprafețe.
Formal, într–o problemă de regresie se dau:
•m– numărul de perechi de valori (sau cazuri, sau înregistrări) din
setul de instruire; pentru desenul din ﬁgura 2.1 este numărul de puncte
desenate;
•x(i)–mvectori de intrare, 1≤i≤m; un astfel de vector este compus
deregulădin ncomponentenumerice,numitetrăsături(eng: features):
x(i)=/parenleftBig
x(i)
1,x(i)
2,…,x(i)
n/parenrightBigt: suprafața, distanța la utilități etc. Trăsă-
turilex(i)
jse mai numesc și variabile predictive sau independente3;
•y(i),1≤i≤m– variabila de ieșire (sau de predicție, sau dependentă)
aferentă valorii x(i); în cazul exempliﬁcat este un număr real (prețul),
dar în general poate ﬁ un vector de valori reale.
Perecheaidin setul de antrenare este (x(i),y(i)),1≤i≤m. Întregul
set de antrenare se scrie ca:
S=/braceleftBig
(x(i),y(i))|1≤i≤m/bracerightBig
(2.1)
Setul de antrenare se speciﬁcă frecvent sub formă tabelară, precum în
tabelul 2.1.
Suprafața (picioare pătrate) Prețul (mii de dolari)
2100 450
1410 243
800 188
… …
Tabela 2.1: Set de date de instruire
Fluxul de lucru în învățarea automată4este dat în ﬁgura 2.3: se pornește
de la un set de instruire, se aplică un algoritm de învățare și se produce un
model. Din motive istorice acest model se mai numește și ipoteză și se no-
tează de regulă cu h. Algoritmul de instruire are ca scop determinarea unei
forme adecvate a modelului, de exemplu a unor valori potrivite a coeﬁcien-
ților funcției h.
3A nu se confunda cu noțiunea de independența liniară din algebră, sau cu indepen-
dența evenimentelor și a variabilelor aleatoare din teoria probabilităților.
4În limba engleză: machine learning = învățare automată.
18

Figura 2.3: Fluxul de lucru într-un proces de instruire automată.
Dupăceinstruireasetermină, modeluluirezultatisefurnizeazăointrare
(în exemplul nostru: suprafața) și modelul va calcula o valoare de ieșire
estimată (prețul). În notație formală avem ecuația 2.2:
ˆy=h(x) (2.2)
unde notația cu căciulă se folosește pentru a denota valori care sunt estimate
de un model oarecare.
Una din întrebările esențiale este: cum se reprezintă ipoteza h? Există
mai multe variante ce pot ﬁ utilizate. Mai sus am pornit cu presupunerea
că prețul crește liniar cu suprafața vândută, deci:
h(x) =hθ(x) =θ0+θ1·x (2.3)
unde indicele lui heste vectorul coloană = (θ0,θ1)t.
Acest model (ipoteză) se numește regresie liniară cu o variabilă, sau
regresie liniară univariată. Se poate ca pe lângă suprafață – singura valoare
de intrare considerată până acum – să se mai considere și alte variabile de
intrare: distanța de la proprietate la utilități, gradul de poluare a zonei
etc.; în acest caz, modelul ar ﬁ unul multivariat (mai multe valori de intrare
considerate). Coeﬁcienții θ0șiθ1din ecuația (2.3) se mai numesc parametri
ai modelului de predicție și se determină prin pasul de învățare.
Modelul (2.3) se mai poate scrie astfel:
hθ(x) =θ0·1 +θ1·x=θ0·x0+θ1·x1=t·x (2.4)
unde:x0= 1,×1=x, vectoruleste(θ0,θ1)t, vectorul xeste(x0,x1)t.
19

2.2 Funcția de cost
Există o inﬁnitate de moduri în care se poate trasa dreapta din ﬁgura
2.2; altfel zis, există o inﬁnitate de valori pentru coeﬁcienții din modelul dat
de ecuația (2.3).
Se pune problema: cum alegem cât mai bine acești coeﬁcienți? O vari-
antă naturală este determinarea acestora de așa manieră încât valorile pre-
zisede model,hθ(x(i)), să ﬁe cât mai apropiate de valorile cunoscutey(i),
pentru tot setul de antrenare Sdin (2.1). Pentru toate valorile din setul de
instruire, eroarea cumulată se poate măsura cu funcția de cost
J(θ0,θ1) =1
2mm/summationdisplay
i=1/parenleftBig
hθ(x(i))−y(i)/parenrightBig2(2.5)
deci trebuie să găsim acele valori ale coeﬁcienților θ(min)
0,θ(min)
1pentru care
se atinge minimul funcției de eroare:
/parenleftBig
θ(min)
0,θ(min)
1/parenrightBig
= arg min
(θ0,θ1)∈R2J(θ0,θ1) = arg min
(θ0,θ1)∈R21
2mm/summationdisplay
i=1/parenleftBig
hθ(x(i))−y(i)/parenrightBig2
(2.6)
Factorulmde la numitor apare pentru a calcula media erorii (altfel, eroa-
rea ar crește de ﬁecare dată când se adaugă în setul de instruire o pereche
(x(i),y(i))pentru care hθ(x(i))/negationslash=y(i), în timp ce media permite compara-
rea erorilor modelului peste seturi de dimensiuni diferite); numitorul 2se
utilizează din motive estetice pentru formulele de mai târziu. Oricum, fac-
torul 1/(2m)nu inﬂuențează valorile θ(min)
0șiθ(min)
1care realizează minimul
funcțieiJ.
Funcția de eroare Jse mai numește și funcție de cost a modelului5. Se
pot folosi și alte funcții de cost, de exemplu incluzând constrângeri impuse
valorilor parametrilor . Funcția de eroare pătratică este o alegere populară
pentru problemele de regresie, dar nu singura posibilă.
Merităsădiscutămcomportamentulfuncției Jpentrucazuriparticulare.
De exemplu, dacă θ0= 0, funcția de eroare J(0,θ1)este o funcție de gradul
2 depinzând de o singură variabilă ( θ1) și având minimul mai mare sau egal
cu zero. Pentru θ0,θ1oarecare forma funcției de eroare este dată în ﬁgura
2.4 [1].
O altă variantă de reprezentare graﬁcă a funcției de eroare este pe baza
curbelor de contur: reprezentarea este plană, având pe cele două axe res-
pectiv peθ0,θ1. Pentru o valoare oarecare a funcției de eroare se consideră
mulțimea tuturor perechilor de parametri θ0,θ1pentru care se obține ace-
easi valoare a erorii. Rezultatul este dat de o mulțime de curbe, precum
cele reprezentate în ﬁgura 2.5 [1]. Se poate arăta că aceste contururi sunt
eliptice.
5În limba engleză: loss function, error function, cost function.
20

Figura 2.4: Funcția de eroare pentru model liniar univariat, cu coeﬁcienți
θ0,θ1[1].
Figura 2.5: Curbe de contur pentru functia de eroare a unui model liniar
univariat [1].
21

2.3 Metoda de căutare după direcția gradientului
În această secțiune se va prezenta o metodă iterativă6pentru minimiza-
rea funcției de eroare J. Ideea este simplă:
•se pornește cu valori θ0,θ1inițiale, setate aleator sau chiar 0;
•se modiﬁcă în mod iterativ valorile curente ale parametrilor θ0,θ1de
așa manieră încât Jsă scadă.
Ultimul punct se concretizează astfel: valorile curente ale parametrilor
θ0,θ1se modiﬁcă conform
θ0=θ0−α·∂J
∂θ0(θ0,θ1) (2.7)
θ1=θ1−α·∂J
∂θ1(θ0,θ1) (2.8)
și atribuirile se operează în mod simultan pentru θ0,θ1.
Această simultaneitate e cerută din cauză că la calculele (2.7–2.9) tre-
buie să ne asigurăm că aceiași θ0,θ1sunt folosiți pentru evaluarea ambelor
derivate parțiale. Simultaneitatea se obține astfel: se calculează expresiile
din membrii drepți ai ecuațiilor (2.7) și ( 2.8) și se asignează unor variabile
temporare θ(nou)
0și respectiv θ(nou)
1; doar după ce ambele variabile tem-
porare sunt calculate, valorile lor se atribuie corespunzător: θ0=θ(nou)
0și
θ1=θ(nou)
1.
Aceleași formule se scriu în mod vectorial ca:
/parenleftBigg
θ0
θ1/parenrightBigg
=/parenleftBigg
θ0
θ1/parenrightBigg
−α·/parenleftBigg∂J
∂θ0(θ0,θ1)
∂J
∂θ1(θ0,θ1)/parenrightBigg
(2.9)
Dacă folosim notația nabla pentru vectorul de derivate parțiale (vectorul de
gradienți)7:
∇J=/parenleftBigg∂J
∂θ0∂J
∂θ1/parenrightBigg
(2.10)
atunci mai putem scrie formula de modiﬁcare a ponderilor ca:
=−α·∇J(θ0,θ1) (2.11)
În limbajele si bibliotecile care permit calcul matricial implementarea
este imediată, iar condiția de atribuire simultană este respectată automat.
6Eng: gradient descent.
7Vectorul de derivate parțiale este un vector de funcții; acestea se vor evalua pentru
valorileθ0,θ1
22

Coeﬁcientul α>0se numește rată de învățare; poate ﬁ o constantă sau
o cantitate care variază de–a lungul iterațiilor. Alegerea lui αeste crucială:
dacă valoarea lui e prea mică, atunci algoritmul va face foarte multe iterații
până se va opri, deci am avea un cost computațional mare. Dacă e prea
mare, procesul poate să rateze minimul sau chiar să diveargă (valoarea lui
Jsă crească mereu sau periodic). Dacă se constată acest al doilea fenomen,
valoarea lui αtrebuie scăzută. Odată ce o valoare potrivită pentru αeste
găsită, nu e neapărat nevoie ca aceasta să ﬁe modiﬁcată.
Metoda se poate folosi pentru reducerea valorilor unei funcții de oricâte
variabile. Menționăm că în general se poate ajunge într-un minim local al
funcției căreia i se aplică.
Algoritmul de căutare după direcția gradientului are forma (considerăm
că valorileθ0șiθ1sunt inițializate înainte de execuția ciclului):
repeta{
θj:=θj−α∂
∂θjJ(θ0,θ1)simultan pentru j= 0,1(2.12)
} pana la convergenta
Criteriul de convergență poate ﬁ: de la o iterație la alta valoarea lui Jnu
mai scade semniﬁcativ, sau se atinge un număr maxim de iterații permise.
Putem explicita derivatele parțiale pentru forma funcției de eroare con-
siderate și atunci (2.12) devine:
θj:=θj−α·1
mm/summationdisplay
i=1/bracketleftBig/parenleftBig
hθ(x(i))−y(i)/parenrightBig
·x(i)
j/bracketrightBig
simultan pentru j= 0,1
(2.13)
Deoarece gradientul unei funcții în extremele funcției este vectorul zero,
rezultă că valoarea parametrilor nu se va mai modiﬁca, odată ce s–a atins
o valoare de minim – global sau local – a lui J.
Următoarele sugestii ar trebui să ﬁe luate în considerare:
•valorile trăsăturilor de intrare să ﬁe în scale similare; se recomandă
deci a se face în prealabil o scalare a datelor la un interval convenabil
ales,e.g.[0,1]; ca efect se obține de regulă un număr mult mai mic de
iterații până la convergența algoritmului;
•se vor urmări valorile lui J; dacă ele au nu o tendință descrescătoare
(funcțiaJcreștesauarescăderiurmatedecreșteri)atuncisevaîncerca
o valoare mai mică pentru rata de învățare α;
•dacă valoarea funcției Jscade foarte lent se poate mări valoarea lui α.
Pe scurt, valoarea optimă a lui αdepinde de setul de date peste care se
calculează funcției de eroare J.αeste un hiperparametru care inﬂuențează
succesul și viteza învățării.
23

Cazulîncaredateledeintraresuntmultivariate: x(i)=/parenleftBig
x(i)
1,x(i)
2,…,x(i)
n/parenrightBigt
se tratează prin metoda de căutare după direcția gradientului, prin modiﬁ-
cări imediate:
1. modelul de predicție devine h(x) =θ0+θ1·x1+…θn·xn=t·x,
x= (x0= 1,×1,…,xn)t,= (θ0,θ1,…,θn)t;
2. funcția de eroare Jse scrie ca:
J() =1
2mm/summationdisplay
i=1(h(xi)−yi)2(2.14)
exact forma din ecuația (2.5);
3. ecuația (2.12) din algoritmul de căutare se rescrie ca:
θj:=θj−α∂
∂θjJ()simultan pentru j= 0,1,…,n (2.15)
Se poate veriﬁca ușor că valoarea J()din ecuația (2.14) se calculează
folosind produse de matrice:
J() =1
2m(X−y)t·(X−y) (2.16)
iar actualizările de ponderi θjdin ecuația (2.15) se pot scrie pentru vectorul
ca:
=−α
mXt(X−y) (2.17)
unde y= (y(1),…,y(m))teste vectorul de valori de ieșire. Formulele (2.16)
și (2.17) sunt utile pentru mediile în care se pot folosi biblioteci performante
de algebră liniară.
2.4 Metoda algebrică
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 problema exempliﬁcată anterior, dorim
să facem estimarea valorii unei proprietăți imobiliare considerând pe lângă
suprafață și distanța la utilități, gradul de poluare a zonei etc. Pentru
început, se va nota cu Xmatricea datelor de intrare:
X=
x(1)
1x(1)
2… x(1)
n
x(2)
1x(2)
2… x(2)
n
…………
x(m)
1x(m)
2… x(m)
n
(2.18)
24

unde linia x(i)conține valorile predictive asociate celui de al i–lea caz din
setul de instruire, iar vectorul coloană de indice 1≤j≤ncorespunde
unei trăsături predictive, de exemplu pentru problema noastră: distanța
la utilități. Valorile de ieșire corespunzătoare sunt de asemenea stocate
matricial, folosind un vector coloană:
y=
y(1)
y(2)
…
y(m)
(2.19)
Modelul de predicție liniar multivariat are forma:
hθ(x) =θ0+θ1·x1+θ2·x2+···+θn·xn (2.20)
unde
x= (x1,…,xn)t(2.21)
Dacă se deﬁnește termenul x0= 1, atunci modelul multivariat se rescrie ca:
hθ(x) =n/summationdisplay
j=0θj·xj (2.22)
Vectorul de intrare xeste8x= (x0,…,xn)t, vectorul de parametri e =
(θ0,…,θn)t, ambii sunt din Rn+1iar suma din ecuația (2.22) se poate scrie
sub forma unui produs scalar de vectori:
hθ(x) =t·x (2.23)
cux= (1,×1,…xn)t. Putem extinde matricea de date Xdin ecuația (2.18)
ca având o coloană plină cu valoarea 1 adăugată drept primă coloană; tot
pentru simplitatea notațiilor, vom folosi și în continuare litera Xpentru
această matrice, numită matrice de design:
X=
1x(1)
1x(1)
2… x(1)
n
1x(2)
1x(2)
2… x(2)
n
…………
1x(m)
1x(m)
2… x(m)
n
(2.24)
Vom folosi următoarele relații cunoscute din algebra liniară:
•(A+B)t=At+Bt;
•(A1·A2…Ap)t=At
p·At
p−1…At
1;
8Pentru simplitate, vom folosi tot notația xpentru acest vector.
25

•dacăaeste un număr real, atunci el poate ﬁ interpretat ca o matrice
de o linie și o coloană și din acest motiv at=a.
•conform lucrării [21] ecuația (81) din secțiunea 2.4.2, pagina 11:
∂θtBθ
∂θ= (B+Bt)·θ
pentru B(obligatoriu) matrice pătratică.
FuncțiaJse rescrie matricial astfel:
J() =1
2mm/summationdisplay
j=1/parenleftBig
hθ(x(j))−y(j)/parenrightBig2
=1
2mm/summationdisplay
j=1/parenleftBig
Tx(j)−y(j)/parenrightBig2
=1
2m(X−y)t(X−y)
=1
2m/braceleftBig
(X)tX−(X)ty−yt(X) +yty/bracerightBig
=1
2m/braceleftBig
tXtX−2tXty+yty/bracerightBig(2.25)
Valorile căutate pentru sunt cele care produc minimul valorii lui J:
(min)= arg min
∈Rn+1J() (2.26)
Conform teoremei lui Fermat, o condiție necesară pentru ca (min)să
minimizeze pe Jeste ca vectorul derivatelor parțiale calculat în (min)să ﬁe
vectorul nul:
∇J/parenleftBig
(min)/parenrightBig
=0 (2.27)
unde 0este vectorul coloană format din n+ 1elemente zero.
Pentru funcția de eroare pătratică J, având în vedere că e și convexă, din
ecuația (2.5), condiția necesară de extrem dată de (2.27) este și suﬁcientă
pentru a garanta că se ajunge în unicul minim al lui J. Avem:
∇J/parenleftBig
(min)/parenrightBig
=1
2m/parenleftBig
2XtX(min)−2Xty/parenrightBig
(2.28)
Impunând condiția (2.27) obținem:
XtX(min)=Xty (2.29)
numite și “ecuațiile normale”. Mai departe, dacă matricea XtXeste nesin-
gulară, vectorul de parametri (min)se determină ca
(min)=/parenleftBig
XtX/parenrightBig−1Xt·y (2.30)
Precizări:
26

1. Expresia/parenleftbigXtX/parenrightbig−1Xtsemainumeșteșipseudo–inversaMoore–Penrose
și se notează cu X+; pentru o matrice inversabilă inversa și pseudo–
inversa ei coincid; pentru calculul pseudoinversei unei matrice Ase
poate folosi în Octave și Matlab funcția pinv, iar în Python funcția
numpy.linalg.pinv ;
2. Când se folosește metoda ecuațiilor normale, nu este necesar să se
facă scalarea trăsăturilor de intrare, precum se recomandă la metoda
iterativă.
Una din problemele care trebuie discutate este: cum se procedează când
matricea XtXeste singulară? Acest lucru se datorează de regulă uneia din
situațiile de mai jos:
•există trăsături de intrare redundante, de exemplu două coloane ale lui
Xsunt liniar dependente; în acest caz avem în mod clar o redundanță
informațională și putem elimina oricare din aceste două coloane; mai
general, una din coloane poate ﬁ combinație liniară a altor coloane și
dacă se știe care e, se poate elimina;
•se folosesc prea multe trăsături față de numărul de cazuri din setul de
instruire (m≤n); în acest caz se poate renunța la câteva trăsături,
adică se elimină coloane din X, sau se folosește regularizarea – a se
vedea secțiunea 2.5.
Ordinea de mai sus este cea sugerată pentru acționare: se elimină din
coloanele redundante, apoi dacă încă e nevoie, se folosește regularizarea.
Dat ﬁind faptul că avem două metode de determinare a lui (min), se
pune problema pe care din ele să o preferăm. Iată câteva comparații:
1. În timp ce pentru metoda gradient descent trebuie ca rata de învățare
să ﬁe aleasă cu grijă, pentru varianta algebrică așa ceva nu e necesar,
neavând de fapt rată de învățare;
2. În timp ce pentru metoda de calcul bazată pe gradient descent sunt
necesare mai multe iterații, metoda algebrică necesită un singur pas;
3. Metoda bazată pe gradient descent funcționează bine chiar și pentru
valori mari ale lui mșin; pentru valori msaunmari, calculul pseudo-
inversei poate ﬁ prohibitiv din punct de vedere al memoriei și timpului
de calcul necesar.
2.5 Overﬁtting, underﬁtting, regularizare
2.5.1 Overﬁtting, underﬁtting
Pentru problema estimării prețului unei proprietăți, să presupunem că
există 5 perechi de valori în setul de instruire, o pereche ﬁind constituită din
27

variabila predictivă suprafata și variabila de ieșire pret. Să considerăm 3
modele de predicție:
1. polinom de gradul întâi: prețul estimat este de forma:
pret =θ0+θ1x (2.31)
2. polinom de gradul al doilea:
pret =θ0+θ1x+θ2×2(2.32)
3. polinom de gradul 4:
pret =θ0+θ1x+θ2×2+θ3×3+θ4×4(2.33)
undepentruﬁecarecaz xestesuprafața; spunemcăamintrodusnoitrăsături
pe baza celor existente, corespunzătoare mai sus cantităților x2,x3,x4.
Primul model este cel liniar discutat până acum, iar celelalte două sunt
modele polonomiale (de grad 2, respectiv 4). Ca și mai înainte, se pune
problema determinării coeﬁcienților θ0,θ1,….
Graﬁcele celor trei forme polinomiale sunt date în ﬁgura 2.6 [1]. Putem
considera cantitățile x,x2,x3,x4ca ﬁind variabile de intrare pe baza cărora
se realizează predicția; faptul că ele provin de la același x(suprafața) este o
chestiune secundară.
Figura 2.6: Trei polinoame pentru aproximarea prețului pornind de la su-
prafață, notată x[1].
Intuitiv, polinomul de gradul întâi nu reușeste să facă o aproximare prea
bună a evoluției prețului față de suprafață. Spunem că modelul dat de
primul polinom suferă de “underﬁtting”9, puterea lui de reprezentare ﬁind
prea slabă pentru problema în cauză. Se mai spune despre un asemenea
model că are “high bias”10, deoarece face o presupunere mult prea simplistă
pentru problema tratată.
Pentru polinomul de grad 4, dacă nu se găsesc două prețuri pe aceeași
verticală (adică nu avem două suprafețe egale vândute cu prețuri diferite),
9Aproximativ, în limba română: incapacitate de reprezentare
10Inclinare prea pronunțată spre un model nepotrivit.
28

se pot determina coeﬁcienții θ0,…,θ 4astfel încât curba să treacă prin toate
cele 5 puncte (interpolare polinomială). Remarcăm însă forma nemonotonă,
cu variații mari a predicției, ﬁind cazuri în care valoarea estimată scade în
raport cu suprafața. Intuitiv, modelul suferă de “overﬁtting”11, ﬁind prea
ﬁdel construit pe datele din setul de instruire; dacă aceste date conțin zgo-
mot, atunci modelul va învăța perfect zgomotul din setul de date. Deși
reprezentarea pe datele de instruire este perfectă, polinomul de gradul 4
dând chiar prețurile cunoscute, în rest nu face o predicție prea credibilă (re-
marcăm scăderea prețului intre al treilea și al patrulea punct din graﬁc). Se
mai spune că modelul are varianță (variabililtate) mare12, datorită faptului
că e prea complex pentru problema tratată.
Polinomul de gradul 2 prezintă cea mai credibilă (în sens intuitiv) formă,
chiar dacă nu reprezintă exact cele 5 perechi de valori din setul de instruire.
Este un compromis între capacitatea de a reproduce setul de instruire și
capacitatea de generalizare, aceasta din urmă ﬁind abilitatea de a prezice
valori de ieșire pentru cazuri care nu fac parte din setul de date de instruire.
Pe scurt, un model care suferă de “underﬁtting” este incapabil de a re-
prezenta de antrenare, cât și de a face estimări pentru alte valori. Un model
care suferă de “overﬁtting” poate reprezenta foarte precis datele din setul
de instruire, dar nu reușește să facă estimări prea bune în afara lui; în acest
ultim caz spunem că nu generalizează bine, generalizarea ﬁind capacitatea
unui model de a estima cât mai aporape de adevăr în afara cazurilor cu care
a fost instruit.
Exempliﬁcarea s–a făcut plecând de la o variabilă predictivă xreprezen-
tând suprafața, care produce alte valori de predicție: x2,x3,x4. Mai gene-
ral, putem să presupunem că avem trăsături de intrare deﬁnite în domeniul
problemei; în cazul nostru, poate ﬁ distanța dintre suprafața respectivă și
utilități, gradul de poluare al zonei etc. Trebuie însă să ﬁm capabili să
detectăm cazurile de overﬁtting și underﬁtting și să le tratăm.
O modalitate de evitare a overﬁtting–ului este reducerea numărului de
trăsături: pentru problema noastră se evită folosirea variabilelor x3,x4. O
altă variantă este alegerea judicioasă a modelului de predicție. Cea de a
treia opțiune este regularizarea: se păstrează variabilele predictive, dar se
impun constrângeri asupra parametrilor modelului — în cazul nostru asupra
coeﬁcienților θi.
2.5.2 Regularizare
Să considerăm că predicția se formează pe baza funcției polinomiale
hθ(x) =θ0+θ1x+θ2×2+θ3×3+θ4×4(2.34)
11Supraspecializare
12Engl: high variance.
29

Intuitiv, vrem ca în funcția de eroare să includem o constrângere asupra
coeﬁcienților θ3,θ4; ei se înmulțesc cu cantitățile x3, respectivx4care deter-
mină o variație rapidă a funcției h; altfel zis, o modiﬁcare mică a cantității x
duce la o modiﬁcări majore ale lui hθ(x). Constrângerea pe care o impunem
este deci ca valorile absolute ale lui θ3șiθ4să ﬁe cât mai apropiate de zero.
Pentru aceasta, vom include în expresia funcției de eroare J(·)și pătra-
tele luiθ3șiθ4:
J() =/braceleftBigg
1
2mm/summationdisplay
i=1/parenleftBig
hθ(x(i))−y(i)/parenrightBig2/bracerightBigg
+ 100·θ2
3+ 100·θ2
4(2.35)
Minimizarea lui Jdin ec. (2.35) va urmări simultan micșorarea diferenței
dintre valorile estimate de model și cele reale, dar și reducerea valorilor
absolute ale lui θ3,θ4. Exemplul de mai sus este gândit pentru a aduce
funcția polinomială de grad patru la una mai apropiată de gradul al doilea,
pentru care agreăm ideea că generalizează mai bine.
În general, nu știm care dintre coeﬁcienții care se înmulțesc cu puteri
ale luixar trebui să aibă valori absolute mici. Intuitiv, ne dăm seama că
valoarea lui θ0nu ar ﬁ necesar a ﬁ supusă unei constrângeri (nu se înmulțeste
cu nicio variabilă predictivă); vom impune deci constrângeri doar asupra
luiθ1,θ2,…– să aibă valori absolute mici. Scopul ﬁnal este de a evita
overﬁtting–ul. Principiul se aplică și dacă se pleacă de la variabile de intrare
independente, nu neapărat suprafata,suprafata2,…. Ca atare, ec. (2.35)
se rescrie mai general ca:
J() =1
2m/bracketleftBiggm/summationdisplay
i=1/parenleftBig
hθ(x(i))−y(i)/parenrightBig2/bracketrightBigg
+λn/summationdisplay
j=1θ2
j (2.36)
undeλ>0. Cu câtλe mai mare, cu atât constrângerea impusă coeﬁcien-
țilorθ1,…,θne mai pronunțată. La extrem, dacă λ→∞atunci se ajunge
lahθ(x) =θ0, ceea ce aproape sigur înseamnă underﬁtting (model de apro-
ximare prea simplist): funcția de estimare returnează mereu θ0, indiferent
de intrare.
Algoritmul de căutare după direcția gradientului devine (considerăm că
avem coeﬁcienții θ0,…,θninițializați aleator):
repeta{
θ0:=θ0−α/bracketleftBigg
1
mm/summationdisplay
i=1/parenleftBig
hθ(x(i))−y(i)/parenrightBig
·x(i)
0/bracketrightBigg
θj:=θj−α/bracketleftBigg
1
mm/summationdisplay
i=1/parenleftBig
h(x(i))−y(i)/parenrightBig
·x(i)
i+λ·θj/bracketrightBigg
, j= 1,…,n
} pana la convergenta
30

unde atribuirile se efectuează în mod simultan.
Pentru metoda algebrică se poate arăta că regularizarea produce urmă-
toarea valoare pentru :
=
XtX+λ·
0 0 0… 0
0 1 0… 0
0 0 1… 0
……………
0 0 0… 1

/bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipupright
(n+1)×(n+1)
−1
·Xy (2.37)
unde matricea care se înmulțește cu λse obține din matricea unitate de
ordinuln+ 1, modiﬁcând primul element în 0.
31

Capitolul 3
Regresia logistică
3.1 Încadrare, motivație
Regresia logistică este folosită pentru estimare de probabilitate condi-
ționată și clasiﬁcare. Inițial dezvoltată pentru lucrul cu două clase, a fost
extinsă pentru a discrimina între oricâte clase — regresia logistică multino-
mială.
Ca mod de instruire se folosește învățarea supervizată. Intrările sunt
vectori numerici, iar clasele sunt ﬁe două (pentru regresia logistică), ﬁe mai
multe (pentru regresia logistică multinomială).
Exemple de probleme de clasiﬁcare cu două clase, tratate de regresia
logistică, sunt:
•clasiﬁcarea unui email ca ﬁind de tip spam sau nonspam, dându–se
conținutul lui, subiectul emailului, faptul că expeditorul face sau nu
parte din lista de contacte etc.
•clasiﬁcarea unei tumori ca ﬁind benignă sau malignă, date ﬁind rezul-
tatele unor analize;
•clasiﬁcarea unui fruct dintr–o imagine ca ﬁind măr sau pară.
Exemple de probleme pentru care există mai mult de două clase sunt:
•clasiﬁcarea unui email ca ﬁind de tip: știri, muncă, prieteni, anunțuri,
spam etc.;
•clasiﬁcarea unui fruct dintr–o imagine ca ﬁind măr, pară, banană,
cireașă etc.
De fapt, modelul dat de regresia logistică (ﬁe ea simplă sau multinomi-
ală) construiește o estimare a probabilității condiționate, dată ﬁind intrarea
curentă (conținut email, imagine cu fructe etc.); mai precis, se determină
32

care este probabilitatea ca obiectul descris de vectorul de intrare speciﬁcat
să ﬁe dintr-o clasă sau alta; matematic, se scrie
P(clasai|intrare ) (3.1)
Faptul că se estimează probabilități, adică valori continue din [0,1]justi-
ﬁcă cuvântul “regresie” din denumirile metodelor. Clasiﬁcarea se face prin
determinarea acelei claseipentru care probabilitatea din ecuația (3.1) este
maximă.
3.2 Regresia logistică binară
3.2.1 Setul de instruire
În cazul regresiei logistice binare se urmărește discriminarea între două
clase. Clasele sunt convenabil date ca ﬁind “0” (clasa negativă) și respectiv
“1” (clasa pozitivă). Setul de instruire este de forma:
S=/braceleftBig
(x(j),y(j))|1≤j≤m/bracerightBig
(3.2)
unde x(j)=/parenleftBig
x(j)
0,x(j)
1,…,x(j)
n/parenrightBigt∈Rn+1,yj∈{0,1}(ca și până acum,
simbolultreprezintă transpunerea unui vector sau a unei matrice). Vom
considera că x(j)
0= 1pentru orice j.
3.2.2 Reprezentarea ipotezei
Pentru regresia logistică modelul de predicție trebuie să producă o va-
loare reprezentând probabilitatea condiționată (3.1). Vom folosi în acest
scop o funcție h(·)cu proprietatea 0≤h(x)≤1:
P(y= 1|x;) =h(x) =1
1 + exp(−t·x)(3.3)
unde= (θ0,θ1,…,θn)t∈Rn+1esteunvectorde n+1coeﬁcienți(ponderi)
cevorﬁdeterminațiprinprocesuldeînvățare. Probabilitateadin(3.3)esteo
probabilitate condiționată de intrarea curentă – în cazul nostru: vectorul x–
și parametrizată de . Se exprimă prin P(y= 1|x;)gradul de încredere că
xface parte din clasa 1, dar modelul este totodată inﬂuențat de parametrul
.
Funcția care stă la baza deﬁnirii modelului heste:
σ:R→(0,1), σ(z) =1
1 + exp(−z)(3.4)
și numită sigmoida logistică, sau funcția logistică, reprezentată graﬁc în ﬁ-
gura3.1. Dupăcumseremarcă, codomeniulfuncțieilogisticeeste (0,1), deci
33

compatibil cu valorile admisibile pentru funcție de probabilitate; extremele
0 și 1 nu se ating, însă. Avem că funcția σeste derivabilă, monoton (strict)
crescătoare, limz→−∞σ(z) = 0,limz→∞σ(z) = 1. Denumirea de “sigmoidă”
este dată de alura graﬁcului, amintind de litera S.
−10.0 −7.5 −5.0 −2.5 0.0 2 .5 5 .0 7 .5 10 .0
z0.00.20.40.60.81.0σ(z) =1
1+exp( −z)
Figura 3.1: Graﬁcul sigmoidei logistice deﬁnită în ecuația 3.4
Probabilitatea evenimentului contrar P(y= 0|x;)este complementul
față de 1 al evenimentului y= 1dat ﬁind vectorul x, adică:
P(y= 0|x;) = 1−P(y= 1|x;) =exp(−t·x)
1 + exp(−t·x)(3.5)
Dorim să determinăm ponderile (coeﬁcienții) din vectorul astfel încât
pentru acei vectori x(i)pentru care eticheta asociată este 1 să avem P(y=
1|x;)să ﬁe cât mai aproape de 1, iar pentru x(i)cu eticheta asociată 0 să
avemP(y= 1|x;)să ﬁe cât mai aproape de 0 – echivalent cu P(y= 0|x;)
să ﬁe cât mai apropiată de 1. Ponderile din vectorul vor ﬁ determinate
prin învățare automată.
După învățare, modelul probabilist dat de (3.3) este mai departe folosit
pentru a face clasiﬁcare, astfel: dacă pentru un vector de intrare xavem că:
P(y= 1|x;)≥P(y= 0|x;) (3.6)
34

atunci se estimează că obiectul descris de vectorul xeste din clasa 1 (pozi-
tivă), altfel din clasa 0 (negativă).
3.2.3 Suprafața de decizie a regresiei logistice
În poﬁda caracterului neliniar al funcției ce deﬁnește modelul – conform
ecuației (3.3) – se arată ușor că suprafața care desparte regiunea xde clasă
pozitivă și cea de clasă negativă este o varietate liniară1.
Inegalitatea (3.6) se scrie echivalent:
P(y= 1|x;)≥P(y= 0|x;)⇐⇒1
1+exp(−t·x)≥exp(−t·x)
1+exp(−t·x)
⇐⇒ 1≥exp(−t·x)
(logaritmând)⇐⇒ 0≥−t·x
⇐⇒t·x≥0
(3.7)
Am obținut deci că dacă xare proprietatea că t·x≥0atunci xeste
clasiﬁcat ca ﬁind de clasă 1, altfel este de clasă 0. Separarea dintre cele
două clase se face de către varietatea liniară t·x= 0: dacă xe în partea
pozitivă a varietății liniare t·x= 0sau chiar pe această varietate, atunci
e de clasă 1, altfel e de clasă 0.
Unii autori consideră că dacă avem o intrare xpentru care P(y=
1|x;) =P(y= 0|x;) = 0.5, atunci modelul nu poate să facă o clasiﬁ-
care a intrării: este tot arât de probabil să ﬁe de clasă pozitivă pe cât e
de probabil să ﬁe de clasă negativă. În inecuația (3.7) am considerat – în
mod mai degrabă arbitrar – că situația cu egalitate să ﬁe tratată ca un caz
pozitiv.
Tot legat de acest subiect, unii preferă să facă o clasiﬁcare de clasă
c∈{0,1}nu doar dacă P(y=c|x;)≥0.5, ci să ia un prag mai sigur, de
exempluP(y=c|x;)≥0.8(sau chiar un prag mai mare); dacă valoarea
P(y= 1|x;)este între 0.2 și 0.8, se decide că modelul de clasiﬁcare nu e
suﬁcient de sigur pe rezultat și refuză să se dea un verdict pentru clasă.
Dacă se permite ca în componența vectorului xsă intre și forme pă-
tratice, cubice etc. ale trăsăturilor originare, atunci suprafața de decizie
poate ﬁ mai complicată. De exemplu, să considerăm că vectorul de in-
trare xestex= (x0= 1,×1,x2,x2
1,×2
2,x1x2)t; rezultă că∈R6; avem
căt·x=θ0+θ1×1+θ2×2+θ3×2
1+θ4×2
2+θ5x1x2. Pentru valorile2
θ0=−4,θ1=θ2=θ5= 0,θ3=θ4= 1se obține ecuația suprafeței de
deciziex2
1+x2
2= 4, reprezentând un cerc; în funcție de poziția față de cerc
(înăuntrul sau în afara lui), obiectul de coordonate (x1,x2)teste estimat ca
ﬁind de o clasă sau de cealaltă.
1Prin abuz se folosește și denumirea “hiperplan”; în timp ce un hiperplan obligatoriu
trebuie să treacă prin origine, varietatea liniară este o formă liniară fără această constrân-
gere.
2În mod normal, valorile lui se determină prin proces de instruire.
35

3.2.4 Funcția de cost
Funcția care ne permite să estimăm cât de bun este un vector de ponderi
șicareedeasemeneautilizatăpentruajustareaacestorponderiînprocesul
de instruire este notată tradițional cu J(·),J:Rn+1→R+, argumentul ei
ﬁind vectorul de ponderi . Valoarea se va calcula peste setul de instruire
Sdin ecuația (3.2).
O variantă este dată de utilizarea aceleiași funcții de eroare din capi-
tolul de regresie liniară, ecuația (2.25) pagina 26. Se arată însă că pentru
problema estimării de probabilitate condiționată, dată ﬁind forma funcției
(modelului) hdin ecuația (3.3), funcția de eroare nu mai este convexă și în
acest caz o căutare bazată pe gradient se poate opri într–un minim local —
ﬁgura 3.2.
0 2 4 6 8 10 12 14
x51015202530f(x) = 15 + sin( x)·x+1
x2+3
minim local minim global
Figura 3.2: Minim global și minim local pentru funcția f: [0,15]→R,
f(x) = 15 + sin( x)·x+1
x2+3
Vom deﬁni Jde așa manieră încât să ﬁe convexă:
J() =1
mm/summationdisplay
j=1Cost (h(x(j)),y(j)) (3.8)
undeCost (h(x(j)),y(j))vrem să veriﬁce următoarele condiții:
36

1. (condiția de apropiere) dacă h(x)șiysunt valori apropiate, atunci
valoarea lui Cost (h(x),y)trebuie să ﬁe apropiată de 0, și reciproc;
2. (condiția de depărtare) dacă h(x)șiysunt valori îndepărtate, atunci
valoarea lui Cost (h(x),y)trebuie să ﬁe mare, și reciproc;
DeﬁnimCost (·,·)astfel:
Cost (h(x),y) =/braceleftBigg
−lnh(x) dacăy= 1
−ln(1−h(x))dacăy= 0(3.9)
logaritmii ﬁind în baza e.
Cele două ramuri ale funcției Costsunt reprezentate în ﬁgura 3.3. Drep-
telex= 0și respectiv x= 1sunt asimptote verticale pentru cele două
ramuri ale lui Cost.
0.0 0 .2 0 .4 0 .6 0 .8 1 .0
hθ(x)01234567 −log(hθ(x))
−log(1−hθ(x))
Figura 3.3: Cele două ramuri ale funcției Costdin ecuația (3.9)
Rescriem funcția Costsub forma:
Cost (h(x),y) =−y·lnh(x)−(1−y)·ln(1−h(x)) (3.10)
Să veriﬁcăm că se îndeplinesc cele două condiții cerute mai sus. Pentru
condiția de apropiere, vrem să veriﬁcăm că:
Cost (h(x),y)≈0⇔h(x)≈y (3.11)
37

Pentru cazul y= 1, (3.11) devine:
Cost (h(x),y)≈0⇔− lnh(x)≈0⇔h(x)≈1 =y⇔h(x)≈y
Pentru cazul y= 0, (3.11) devine:
Cost (h(x),y)≈0⇔− ln(1−h(x))≈0⇔h(x)≈0 =y⇔h(x)≈y
deciprimacondiție,legatădevaloareaapropiatedezeroacantității Cost (h(x),y)
este îndeplinită de deﬁniția funcției Costdin ecuația (3.10).
Pentru condiția de depărtare, dacă Cost (h(x),y) =M/greatermuch0, atunci
obținem echivalent h(x) = exp(−M)(pentruy= 1) respectiv h(x) =
1−exp(−M)(pentruy= 0);yeste unul din capetele intervalului [0,1],
iar dacăMeste o valoare din ce în ce mai mare, atunci h(x)se îndreaptă
spre celălalt capăt al intervalului unitate. Rezultă deci că și această a doua
condiție este îndeplinită de deﬁniția din formula (3.10), pentru valori yși
h(x)îndepărtate.
În plus, deoarece ﬁecare din cele două ramuri ale funției de cost din (3.9)
sunt convexe, rezultă că de fapt funcția Costeste convexă, deci funcția J,
ca sumă a unui număr ﬁnit de funcții convexe, este ea însăși convexă. Ca
atare, orice punct de minim al lui Jeste garantat și minim global; acest
lucru este deosebit de util și justiﬁcă forma aparte a funcției de cost din
(3.9).
Funcția de eroare Jse rescrie astfel:
J() =−1
mm/summationdisplay
j=1/bracketleftBig
y(j)·lnh/parenleftBig
x(j)/parenrightBig
+/parenleftBig
1−y(j)/parenrightBig
·ln/parenleftBig
1−h(x(j))/parenrightBig/bracketrightBig
(3.12)
și acestă formă se numește cross–entropy.
3.2.5 Algoritmul de instruire
Setul de antrenare Seste utilizat pentru a deduce valori adecvate ale
lui, astfel încât predicțiile date de model pentru valorile de intrare x(j)
să ﬁe cât mai apropiate de valoarea actuală a etichetelor corespunzătoare
y(j). Datorită proprietăților funcției Costdin ecuația ( 3.9) și a faptului că
Jeste valoarea medie a funcției Costpeste setul de instruire, deducem că
minimizând valoarea lui J, obținem (în medie) valori h(x(j))apropiate de
y(j).
Pentru determinarea lui (min)= arg min
J()se folosește algoritmul
de căutare după direcția gradientului: se pornește cu valori aleator setate
componentelorvectorului3șisemodiﬁcăînmoditerativ, scăzândlaﬁecare
pas valoarea gradientului înmulțită cu un coeﬁcient pozitiv mic (rata de
învățare).
Formal, algoritmul are forma:
3Se poate seta chiar ca să ﬁe vectorul nul.
38

1. Setează componentele lui la valori inițiale aleatoare;
2. Iterații:
repeta{
θi:=θi−α·∂J
∂θi()simultan pentru i= 0,1,…,n
} pana la convergenta
undeα>0este rata de învățare. Condiția de convergență este la fel ca la
regresia liniară.
Explicitând derivatele parțiale ale lui Jobținem:
repeta{
θi:=θi−α1
mm/summationdisplay
j=1/parenleftBig
hθ(x(j))−y(j)/parenrightBig
·x(j)
isimultan pentru i= 0,…,n
} pana la convergenta
Se observă că modiﬁcarea ponderilor θ0,…,θnare aceeași formă ca la
regresia liniară. Singura diferență este forma funcției h.
3.2.6 Regularizare
Dacă se permite ca valorile parametrilor4θ1,…,θnsă ﬁe lăsate necon-
strânse, atunci valorile lor absolute pot crește și inﬂuența negativ perfor-
manțadegeneralizareamodelului: pentruvariațiimicialedatelordeintrare
vom avea variații mari ale valorilor funcției model; mai mult, dacă luăm în
considerare trăsături de intrare de forma xi·xj,xi·xj·xketc. modelul poate
ajunge să aproximeze foarte bine perechile din setul de instruire, dar fără a
avea o performanță bună pe datele din set de testare5. Ca atare, se preferă
impunerea unor constrângeri parametrilor θ1,…,θnastfel încât aceștia să
ﬁe cât mai mici în valoare absolută.
Pentru regularizare se modiﬁcă forma funcției de eroare astfel:
J() =−1
mm/summationdisplay
j=1/bracketleftBig
y(j)·lnh(x(j)) + (1−y(j))·ln(1−h(x(j)))/bracketrightBig
+λ
2mn/summationdisplay
i=1θ2
i
(3.13)
Modiﬁcarea adusă algoritmului de instruire este simplă: mai trebuie inclusă
și derivata parțială a lui θ2
iîn raport cu θi:
4Se remarcă lipsa termenului liber θ0; el nu este regularizat.
5Alfel zis: creștem numărul de trăsături din setul de antrenare, dar numărul de exem-
plare din acest set rămâne același: m.
39

repeta{
θ0:=θ0−α1
mm/summationdisplay
j=1(hθ(x(j))−y(j))·x(j)
0
θi:=θi−α
1
mm/summationdisplay
j=1/parenleftBig
hθ(x(j))−y(j)/parenrightBig
·x(j)
i+λ
mθi

} pana la convergenta
unde atribuirile se fac simultan pentru inidicii 0, 1, …, nai componentelor
vectorului.
3.3 Regresia logistică multinomială
Pentru cazul în care se cere discriminarea pentru kclase,k>2, regresia
logistică se extinde să construiască kfuncții (modele) simultan6:
h(x) =
P(y= 1|x;)
P(y= 2|x;)
…
P(y=k|x;)
(3.14)
Setul de instruire suferă modiﬁcări doar pentru valorile lui y(i), care
acum pot ﬁ din mulțimea {1,…,k}.
3.3.1 Funcția softmax
În cazul rergresiei logisitce cu două clase s–a folosit funcția sigmoidă lo-
gistică, producându–e valori de ieșire ce pot ﬁ folosite direct ca probabilități
condiționate. Pentru mai mult de două clase, estimarea de probabilitate
condiționată se face cu funcția softmax, care transformă un vector oarecare
deknumere într-un vector de kvalori din intervalul (0,1)și care însumate
dau 1.
Pornind de la vectorul z= (z1,…,zk)t∈Rk, el e transformat de funcția
softmax astfel:
softmax (z) = (softmax (z; 1),…,softmax (z;k))t(3.15)
undesoftmax (z;l)este:
softmax (z;l) =exp(zl)
k/summationtext
i=1exp(zi)(3.16)
6Pentru doua două clase era suﬁcientă construirea unei singure funcții. Pentru k > 2
clasearﬁsuﬁcienteconstruireaa k−1funcții, darpentrucomoditatesepreferăconstruirea
akfuncții, oricare din ele ﬁind acceptată ca redundantă.
40

pentru 1≤l≤k. Se veriﬁcă ușor că softmax (z;l)∈(0,1)pentru orice l,
1≤l≤kși/summationtextk
l=1softmax (z;l) = 1. Vom folosim funcția softmax pentru
producerea de estimări de probabilități condiționate de intrarea curentă x.
La implementare se poate întâmpla ca valoarea funcției exponențiale să
depășească posibilitățile de reprezentare numerică, pentru valori zlmari.
Un truc de calcul frecvent aplicat în practică este următorul: în loc de a se
calcula funcția softmax precum în ecuația (3.16), se calculează prima dată
valoareamaximădin (z1,…,zl), ﬁeeaM, apoisecalculeazăsoftmaxpentru
vectorul de valori z/prime= (z1−M,…,zl−M). Avem că:
softmax (z/prime,l) =exp(zl−M)
k/summationtext
i=1exp(zi−M)=exp(zl)/exp(M)
k/summationtext
i=1[exp(zi)/exp(M)]=
=exp(zl)
k/summationtext
i=1exp(zi)=softmax (z;l) (3.17)
3.3.2 Reprezentarea ipotezei
Modelul care conține toate cele kmodele, câte unul pentru ﬁecare clasă,
ia forma:
h(x) =
P(y= 1|x;)
P(y= 2|x;)
…
P(y=k|x;)
=1
k/summationtext
l=1exp/parenleftbigt
l·x/parenrightbig
exp/parenleftbigt
1·x/parenrightbig
exp/parenleftbigt
2·x/parenrightbig
…
exp/parenleftbigt
k·x/parenrightbig
(3.18)
Modelul pentru clasa lare asociat propriul vector de ponderi l; aceștia
vor ﬁ determinați prin învățare. Impreună, vectorii ldeﬁnesc matricea
– ce apare ca indice al funcției hdin ecuația (3.18) – prin stivuirea pe
orizontală a transpuselor lor:
=
t
1
t
2
…
t
k
(3.19)
deci matricea e de forma k×(n+ 1).
Pe clase, probabilitatea ca un vector xsă ﬁe de clasă l(1≤l≤k)este:
P(y=l|x;) =exp/parenleftbigt
l·x/parenrightbig
/summationtextk
i=1exp (t
i·x)(3.20)
41

Numitorul ultimului termen din ecuația (3.18) are rolul de a face ca toate
probabilitățile condiționate să se însumeze la 1:
k/summationdisplay
l=1P(y=l|x;) = 1 (3.21)
Pentruclasiﬁcareaunuivector xdatlaintrare,secalculează P(y=l|x;)
pentru toți lîntre 1 șikși se alege acel l(max)care realizează probabilitatea
maximă:
l(max)= arg max
1≤l≤kP(y=l|x;) (3.22)
Predicția făcută de model este că xaparține clasei l(max).
Instruirea vizează determinarea acelei matrice pentru care modelul
învață să recunoască cât mai bine datele din setul de instruire (eventual
adăugându–se și factor de regularizare). Mai clar, dacă un obiect x(j)dinS
este de clasă y(j)=l, atunci vrem ca valoarea P(y=l|x;)să ﬁe cât mai
aproape de 1.
3.3.3 Funcția de cost
Ca și în cazul funcției de eroare pentru regresia logistică, se va cuantiﬁca
în ce măsură diferă clasa actuală a unei intrări de predicția dată de modelul
h. Introducemfuncțiaindicator I(·)carepentruovaloarelogicăreturnează
1 dacă argmentul este adevărat și 0 altfel:
I(valoare_logica ) =/braceleftBigg
1dacăvaloare_logica =adevarat
0dacăvaloare_logica =fals(3.23)
Funcția de eroare pentru regresia logistică multinomială se deﬁnește ca:
J() =−1
m
m/summationdisplay
j=1k/summationdisplay
l=1I/parenleftBig
y(j)=l/parenrightBig
·lnexp/parenleftBig
t
lx(j)/parenrightBig
/summationtextk
i=1exp/parenleftbigt
ix(j)/parenrightbig
 (3.24)
3.3.4 Algoritmul de instruire
Determinarea lui (min)= arg min
∈Rn+1J()se face prin căutarea după
direcția gradientului. Formula gradientului este:
∂J
∂l() =−1
mm/summationdisplay
j=1/bracketleftBig
x(j)/parenleftBig
I(y(j)=l)−P(y(j)=l|x(j);)/parenrightBig/bracketrightBig
,1≤l≤k
(3.25)
unde∂J
∂l()este un vector. Modiﬁcarea vectorului leste:
l:=l−α·∂J
∂l() (3.26)
42

pentru toți 1≤l≤k. Modiﬁcarea se face iterativ, până când matricea se
stabilizează sau se atinge un număr maxim de iterații.
Spre deosebire de regresia liniară, nu există o variantă algebrică de de-
terminare a valorilor din matricea .
3.3.5 Regularizare
Înpracticăsepreferăpenalizareavalorilorabsolutemarialeparametrilor
θli(1≤l≤k,1≤i≤n); nu se penalizează ponderile de termeni liberi θl0
(1≤l≤k). Se adaugă penalizări pentru pătratele valorilor ponderilor θliși
funcția de eroare se modiﬁcă astfel:
J() =−1
m
m/summationdisplay
j=1k/summationdisplay
l=1I(y(j)=l)·lnexp/parenleftBig
t
lx(j)/parenrightBig
/summationtextk
i=1exp/parenleftbigt
ix(j)/parenrightbig
+λ
2mk/summationdisplay
l=1n/summationdisplay
i=1θ2
li
(3.27)
Coeﬁcientul λeste un hiperparametru care arată cât de mult contează re-
gularizarea în cadrul funcției de eroare; evident, pentru λ= 0nu avem
regularizare, iar dacă λse alege foarte mare, atunci funcția de eroare cross–
entropy este neglijată în favoarea micșorării valorii coeﬁcienților θli, fără a
da vreo importanță prea mare dicrepanțelor de clasiﬁcare. Evident, trebuie
realizat un echilibru îintre aceste două extreme.
Formula gradientului folosit în căutarea de tip gradient descent este:
∂J
∂l() =−1
mm/summationdisplay
j=1/bracketleftBig
x(j)/parenleftBig
I(y(j)=l)−P(y(j)=l|x(j);)/parenrightBig/bracketrightBig
+λ
ml(3.28)
Valoareahiperparametrului λsedeterminăprinîncercărirepetate, cross-
validation, căutare aleatoare, optimizare bayesiană, algoritmi genetici sau
alte euristici de căutare.
43

Capitolul 4
Rețele neurale artiﬁciale –
fundamente
4.1 Încadrarea domeniului
Studiul rețelelor neurale artiﬁciale este motivat de observația că un sis-
tembiologicestemaiperformantdecâtcalculatoareleșiprogrameleexistente
la ora actuală într-o serie de sarcini precum recunoașterea de imagini, regă-
sirea informației, înțelegerea vorbirii. Acest lucru se întâmplă cu toate că
neuronii biologici operează mult mai lent decât procesoarele actuale. Stu-
diul rețelelor neurale artiﬁciale are ca scop producerea unor sisteme care să
obțină rezolvări pentru probleme de tipul celor de mai sus, dar și altele de
natură sintetică, pe baza experienței acumulate din mediu.
Deﬁniția următoare ([18]) ia în considerare abilitatea de adaptare pe
baza experienței:
Deﬁniția 4. Sistemele neurale artiﬁciale, sau rețelele neurale sunt sisteme
celulare ﬁzice 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ă artiﬁcială
modelează felul în care creierul biologic procesează semnalele. Modelele de
rețele neurale artiﬁciale sunt structurate ca niște grafuri ale căror noduri
sunt neuroni artiﬁciali, iar legăturile dintre noduri au ponderi1- valori nu-
merice-ajustabileprintr-unprocesdeînvățare. Deﬁnițiadin[7]sumarizează
acest fapt:
Deﬁniția 5. O rețea neurală este un sistem de procesare masiv paralel-
distribuit constând din unități de procesare simple, care au predispoziție
naturală pentru stocarea cunoștințelor experimentale și utilizarea lor. Este
asemănătoare creierului în două aspecte:
1În limba engleză: weights.
44

1. Cunoașterea este achiziționată de către rețea din mediu printr–un pro-
ces de învățare;
2. Ponderile legăturilor dintre neuroni, cunoscute ca ponderi sinaptice
sunt folosite pentru a reține cunoașterea dobândită.
Procedura prin care se obține adaptarea ponderilor din cadrul rețelei se
numețealgoritm de învățare . Mai menționăm că învățarea poate duce la
modiﬁcarea numărului de noduri din rețea (a se vedea de exemplu Fuzzy
ARTMAP, capitolul 9), ceea ce în cadrul rețelelor neurale biologice are ca și
corespondent 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: neurocalcu-
latoare, rețele conecționiste, sisteme adaptive stratiﬁcate, rețele cu auto-
organizare, sisteme neuromorﬁce etc.
Există multe moduri în care pot ﬁ privite aceste rețele neurale de către
diferite categorii profesionale:
•oamenii de știință din domeniul neurobiologiei sunt interesați de mo-
dul în care rețelele neurale artiﬁciale conﬁrmă rezultatele sau modelele
cunoscute pentru sisteme biologice; facem precizarea că transferul de
cunoștințenuestedoardinsprebiologiespredomeniulrețelelorneurale
artiﬁciale, ci și invers: modele teoretice sunt conﬁrmate de descoperi-
rile biologice2;
•ﬁzicienii văd analogii între rețelele neurale și sistemele dinamice neli-
niare pe care le studiază;
•matematicienii sunt interesați de potențialul de modelare matematică
pentru sisteme complexe;
•ingineriidindomeniulelectriclefolosescpentruprocesareadesemnale;
•informaticienii sunt interesați de oportunitățile care apar in zonele de
inteligență artiﬁcială, teorie computațională, modelare și simulare etc.
Beneﬁciile aduse de rețele neurale artiﬁciale sunt:
1. neliniaritatea: un neuron artiﬁcial poate avea comportament liniar sau
nu; caracteristica neliniară este importantă pentru cazul în care me-
canismul care generează semnalul este neliniar – de exemplu semnalul
de vorbire;
2Vezi de exemplu “Reinforcement learning through modulation of spike-timing-
dependent synaptic plasticity”, A mechanism predicted theoretically by a Coneural scien-
tist has been found experimentally in the brain.
45

2. detectarea de asocieri între intrări și ieșiri: este cazul învățării su-
pervizate, în care antrenarea se face pe baza unor perechi de semnale,
corespunzătoare intrărilor și respectiv ieșirilor asociate. Se poate pleca
delaunmodelcarenuarecunoștințeaprioridespredomeniușipebaza
datelor se învață asocierea.
3. adaptabilitate: rețelele neurale au capacitatea naturală de a–și adapta
ponderile în funcție de semnalele provenite din mediu; mediul poate să
ﬁe nestaționar, adică să sufere modiﬁcări în ceea ce privește distribuția
semnalelor sau a asocierilor;
4. rezistența la zgomot: o rețea neurală poate să accepte date care au
imprecizie sau sunt afectate de zgomot; sunt raportate multe situații
în care adăugarea de zgomot la datele de antrenare îmbunătățește
calitatea învățării.
4.2 Neuronul biologic
Este utilă o scurtă incursiune în biologie, pentru a înțelege modelarea ce
se face pentru un neuron artiﬁcial.
Neuronul biologic este o celulă nervoasă elementară, elementul construc-
tiv de bază pentru rețeaua neurală biologică. Neuronul are trei părți prin-
cipale: corpul celulei, numit și soma,axonulșidendritele . O schemă a unui
neuron a fost dată în ﬁgura 1.1. Dendritele formează o arborescență prin
care sunt primite impulsuri de la alți neuroni. Axonul este un ﬁr conduc-
tor lung, cu un capăt în corpul celulei iar cu celălalt ramiﬁcat, prin care
se trimite semnal către dendritele altor axoni. Contactul dintre un axon
și o dendrită se cheamă 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 de
către dendrite. Răspunsul acesta este generat dacă potențialul membranei
depășeste un anumit prag de activare. Impulsurile care vin prin membrană
suntexcitatoare dacă ele favorizează formarea semnalului de ieșire din ne-
uron șiinhibitoare dacă inhibă răspunsul. Se face o agregare a semnalelor
primite de celulă de-a lungul unei perioade de sumare latentă, luându-se în
considerare și apropierea în timp a semnalor excitatoare primite; nu se cere
o sincronizare a semnalelor, iar valoarea de ieșire este de regulă văzută ca
una binară: 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ătre alți neuroni; dacă este mai mic, atunci nu se declanșează semnal
în axon.
După emiterea semnalului prin axon există o perioadă refractară, în care
neuronul numaiiaîn considerareniciunsemnalsosit, indiferentdegradulde
intensitate. Dupăscurgereaacesteiperioade, neuronulestegatasăproceseze
46

noisemnale. Perioadarefractarănuareneapărataceeașiduratăpentrutoate
celulele. Timpul necesar acestui ciclu este de ordinul milisecundelor.
Facem precizarea că prezentarea făcută este o variantă simpliﬁcată; con-
siderareașimodelareaunordetaliiducelarețeleneuraleartiﬁcialedediferite
tipuri (generații).
4.3 Modele de neuroni artiﬁciali
4.3.1 Modelul McCulloch–Pitts
Reprezintă prima deﬁniție formală a unui neuron artiﬁcial, ce pleacă
de la descrierea a neuronului biologic. Modelul a fost formulat în 1943 de
neurobiologul si ciberneticianul Warren McCulloch și respectiv logicianul
Walter Pitts. Modelul este arătat în ﬁgura 4.1. Intrările xisunt 0 sau 1,
i=1,n, ponderile wi∈{− 1,1},Teste pragul neuronului iar ieșirea ose
calculează ca:
ok+1=

1dacăn/summationtext
i=1wixk
i≥T
0altfel=I(wt·x≥T) (4.1)
undeI()estefuncțiaindicator, w= (w1,w2,…,wn)tșix= (x1,x2,…,xn)t
sunt respectiv vectorul de ponderi și de valori de intrare, iar indicele superior
kestemomentuldetimp, k= 0,1,…. Ponderile wi= 1reprezintăsinapsele
excitatoare, cele cu valoare -1 sunt inhibitoare. Cu toate că modelul este
simplu, el poate ﬁ folosit pentru implementarea operațiilor logice not,and
șior, dacă ponderile și pragul sunt setate corespunzător.
x1
x2
xnw1
w2
wnT o
Figura 4.1: Modelul McCulloch-Pitts pentru neuron artiﬁcial.
4.3.2 Modelarea neuronului pentru sisteme neurale artiﬁci-
ale
Modelul McCulloch-Pitts este o viziune simpliﬁcată: permite doar in-
trări, ieșiri și ponderi binare, operează în timp discret, presupune sincroni-
zarea intrărilor (toate intrările trebuie să sosească în același timp), ponderile
47

și pragul sunt ﬁxe. Ca atare, se propune modelul dat în ﬁgura 4.2 cu urmă-
toarele precizări:
1. ﬂuxul semnalului de intrare xieste unidirecțional
2. valoarea de ieșire a neuronului este:
o=f(wt·x) =f/parenleftBiggn/summationdisplay
i=1wixi/parenrightBigg
(4.2)
unde wșixau fost dați mai sus.
3. valoareaprodusuluiscalar wt·xsenoteazăcu netșisenumeștevaloare
de activare a neuronului;
4. funcțiafse numește funcție de activare ; poate avea diferite forme.
x1
x2
xnw1
w2
wntf(w x) o
Figura 4.2: Model general de neuron
Se remarcă lipsa pragului Tdin ecuațiile de mai sus; de fapt, se poate
considera că neuronul are doar n−1intrări sinaptice iar valoarea a n-a este
xn=−1permanent, având ponderea asociată wn=T. Funcțiile de activare
f(·)larg folosite sunt
f1(net) =2
1 +e−λ·net−1,λ> 0 (4.3)
cu graﬁcul dat în ﬁgura 4.3 și
f2(net) =sgn(net) =/braceleftBigg
+1,dacănet> 0
−1,dacănet< 0(4.4)
Se observă că λ/4 =f/prime
1(0), deciλeste proporțională cu panta tangentei
la graﬁcul lui f1în origine. Pentru λ→∞f1tinde către f2. Datorită alurii
funcțieif1, amintind de forma literei S, ea se mai numește și sigmoidă. Se
mai poate folosi 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(4.5)
48

Figura 4.3: Funcția sigmoidă dată de ecuația 4.3 pentru λﬁxat.
Deoarece funcțiile date iau valori între -1 și +1 se mai numesc bipolare,
iar aspectul continuu sau discontinuu le dă denumirea de bipolară continuă
și respectiv bipolară discretă . Funcția bipolară poate ﬁ redusă la formă
unipolară, mărginită de 0 și 1:
f4(net) =σλ(net) =1
1 +e−λ·net,λ> 0 (4.6)
(sigmoida logistică) și
f5(net) =/braceleftBigg
+1,dacănet> 0
0,dacănet< 0(4.7)
Drept funcție de activare se poate folosi de fapt orice funcție care este mo-
noton nedescrescătoare, mărginită și preferabil derivabilă3. Proprietatea de
derivabilitate asigură mai multă ﬂexibilitate procesului de instruire, motiv
pentru care funcțiile de activare continue sunt cele folosite.
Ieșirile pot ﬁ binare sau continue, bipolare sau unipolare. Pentru m
neuroni, mulțimea valorilor de ieșire este:
•(−1,1)mpentru funcție de activare bipolară continuă
•(0,1)mpentru funcție de activare unipolară continuă
•{−1,1}mpentru funcție de activare bipolară discretă
•{0,1}mpentru funcție de activare unipolară discretă
4.4 Modele de rețea neurală artiﬁcială
4.4.1 Rețea cu propagare înainte
Vomconsideraoarhitecturăderețeacupropagareînainte4cunintrăriși
mneuroni de ieșire, precum în ﬁgura 4.4. Intrările și ieșirile sunt respectiv:
x= (x1,x2,…,xn)t
o= (o1,o2,…,om)t (4.8)
3Pentru cazul funcțiilor nederivabile se poate folosi metoda subgradientului:
http://www.stanford.edu/class/ee392o/subgrad_method.pdf.
4În original: feedforward network.
49

Dacă considerăm vectorul de ponderi wicare leagă neuronul de ieșire icu
o1w11
wm1
xnw22o2
omx1
x2w21 w12
wm2
w1nw2n
wmn
Figura 4.4: Model de rețea neurală artiﬁcială
toate intrarile, wi= (wi1,wi2,…,win)t, atunci valoarea de activare pentru
neuronulieste
neti=wt
ix=n/summationdisplay
j=1wijxj,1≤i≤m (4.9)
Valoarea de ieșire oipentru ﬁecare neuron este oi=f(neti) =f(wt
ix).
Putem nota cu Wmatricea ponderilor dintre neuroni:
W=
w11w12···w1n
w21w22···w2n
…………
wm1wm2···wmn
(4.10)
și introducem operatorul matricial Γ(·)deﬁnit ca
Γ
net1
net2
…
netm
=
f(net1)
f(net2)
…
f(netm)
(4.11)
ceea ce ne permite să scriem ieșirea rețelei ca ﬁind:
o= Γ(W·x) (4.12)
50

Valorile de intrare xși cele de ieșire ose numesc pattern-uri de intrare
și respectiv de ieșire. Rețeaua acționează instantaneu, adică de îndată ce
intrarea este furnizată, rețeaua dă și valoarea de ieșire asociată. Dacă se
consideră momentul de timp t, atunci putem rescrie 4.12 ca:
o(t) = Γ( W·x(t)) (4.13)
4.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
conexiune inversă”5; o reprezentare este dată în ﬁgura 4.5. În felul acesta,
ieșirile controlează 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)) (4.14)
w11
wm1
w221∆o (t+ )x (0)1
x (0)
x (0)∆∆
∆w21 w12
wm2
w1nw2n
wmn2o (t+ )
no (t+ )∆
∆2
n
Figura 4.5: Rețea cu conexiune inversă.
Intrarea xeste necesară doar la început ( t= 0), după care sistemul
se auto-întreține. Dacă considerăm timpul ca valoare discretă și urmărim
5În limba engleză: feedback network.
51

sistemul la momentele 0, ∆,2∆, …,k∆, …atunci sistemul se numește
discret. Putem lua convenabil ∆ = 1și atunci avem:
ok+1= Γ(Wok),k= 1,2,… (4.15)
sau
ok+1= Γ/parenleftBig
WΓ/parenleftBig
···Γ(Wx0)···/parenrightBig/parenrightBig
(4.16)
Șirul de valori o1,o2, …reprezintă stările succesive ale rețelei, care în acest
caz este văzut ca un sistem dinamic. Este posibil ca de la un moment dat
ok=ok+1=…, adică oksă ﬁe un atractor, iar rețeaua se stabilizează. Mai
general, un atractor poate să ﬁe o mulțime ﬁnită de valori. Un exemplu de
astfel de rețea neurală este memoria asociativă bidirecțională.
4.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 unei
funcțiih(·)printr-o funcție H(w,·)unde w= (w1,w2,…wm)tiar argu-
mentul notat “·” este un vector x= (x1,x2,…,xn)t. Problema este de a
găsi vectorul wcare dă cea mai bună aproximare pentru un set de antrenare
{(x1,h(x1)),…, (xp,h(xp))}. Primul pas este alegerea funcției aproximante
H(·,·), apoi un proces de învățare este folosit pentru a determina o valoare
bună pentru vectorul w. Altfel zis, se caută un vector w∗pentru care
w∗= arg minwp/summationdisplay
k=1ρ/parenleftBig
H(w,xk),h(xk)/parenrightBig
(4.17)
undeρeste o funcție distanță care măsoară calitatea aproximării. Învățarea
este procesul de găsire a unui bun aproximant.
Deși formularea este simplă, există două diﬁcultăți în rezolvarea generală
a acestei probleme de aproximare:
1. o valoare potrivită pentru mpoate ﬁ greu de determinat; atunci când
aproximarea se face prin rețele neurale de tip feedforward cu un strat
ascuns (vezi curs 6), valoarea lui meste numărul de neuroni din stratul
ascuns;
2. determinarea efectivă a lui w∗cunoaște rezolvări pentru câteva clase
de funcțiiHșiρ– a se vedea teoria cercetărilor operaționale – dar
o metodă eﬁcientă pentru toate cazurile nu este cunoscută6; putem
vorbi de probleme de programare liniară sau de programare pătratică,
dar sunt multe alte situații care nu au o rezolvare teoretică cunoscută.
O abordare este folosirea unor metode de căutare euristică – metodele
“hill-climbing”, “simulated annealing”, algoritmi genetici, dar aceștia
nu garantează obținerea minimului absolut.
6Asevedeahttp://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization.
52

4.6 Reguli de învățare
În această secțiune vom privi neuronul artiﬁcial ca pe o entitate adap-
tivă, pentru care ponderile se pot modiﬁca pe baza unui proces de învățare.
Ponderile se modiﬁcă în funcție de:
•valoarea actuală a ponderilor, wsauW;
•semnalul de intrare x;
•ieșirea rezultată o;
•(opțional) ieșirea furnizată de un “profesor”, în cazul învățării super-
vizate, numită și ieșirea dorită, d.
Putem presupune că intrarea xnare valoarea ﬁxă −1, pentru a permite
includerea parametrului prag. Putem considera că sunt nneuroni de intrare
șimde ieșire, iar vectorul ponderilor care leagă al i-lea neuron de ieșire de
toți neuronii de intrare este wi= (wi1,wi2,…,win)t.
Regula de învățare generală este că ponderile wivariază proporțional cu
produsul dintre intrarea xși semnalul de învățare r.reste o funcție care ia
în considerare trei din valorile date mai sus, deci
r=r(wi,x,di) (4.18)
undedieste eventuala valoare de ieșire ce corespunde neuronului de ieșire i.
Mai precis, avem
∆wi(t) =α·r(wi(t),x(t),di(t))·x(t) (4.19)
undec > 0este rata de învățare. Expresia (4.19) dă modul în care se
modiﬁcă ponderile de la un moment de timp la următorul:
wi(t+ 1) = wi(t) +α·r(wi(t),x(t),di(t))·x(t) (4.20)
Pentru cazul discret se folosește scrierea:
wk+1
i=wk
i+α·r(wk
i,xk,dk
i)·xk,k= 0,1,… (4.21)
iar pentru cazul continuu se scrie ecuația diferențială
dwi(t)
dt=α·r(wi(t),x(t),di(t))x(t) (4.22)
Pe baza formei funcției ravem variantele de învățare menționate mai
jos.
53

4.6.1 Regula de învățare Hebbiană
Este o regulă de învățare nesupervizată formulată de Donald Hebb în
1949 astfel:
When an axon of cell A is near enough to excite a cell B and
repeatedly or persistently takes part in ﬁring it, some growth
process or metabolic change takes place in one or both cells such
that A’s eﬃciency, as one of the cells ﬁring B, is increased.
Matematic, se scrie:
r=f(wt
ix) (4.23)
deci modiﬁcarea ponderilor devine
∆wi=αf(wt
ix)x (4.24)
ceea ce pe componente se scrie
∆wij=αf(wt
ix)xj (4.25)
sau în funcție de ieșirea neuronului i
∆wij=αoixj (4.26)
Ponderile sunt inițializate cu valori aleatoare mici, în jurul lui 0. Conform
formulelor date, putem avea o creștere a ponderii wijdacă produsul oixj
este pozitiv și o scădere în caz contrar. Se arată ușor că intrările prezentate
frecvent au o inﬂuență mai mare asupra ponderilor și vor produce o valoare
de ieșire mare.
Regula trebuie înțeleasă ca un principiu, existând la ora actuală varia-
țiuni pe această temă.
Exemplu numeric: [18] pag 61.
4.6.2 Regula de învățare a perceptronului
Estefolosităpentruînvățaresupervizată; regulaafostformulatădecătre
Rosenblatt în 1958. Semnalul de învățare este diferența între valoarea dorită
și cea obținută:
r=di−oi (4.27)
undeoi=sgn(wt
ix), iardieste răspunsul dorit, furnizat de “profesor”.
Modiﬁcarea ponderilor este deci
∆wi=α/parenleftBig
di−sgn(wt
ix)/parenrightBig
x (4.28)
Formula se aplică pentru cazul în care ieșirile sunt bipolare binare. Modi-
ﬁcarea în ponderi apare doar dacă ieșirea furnizată de neuronul de ieșire i
54

diferă de valoarea dorită — cunoscută aprioric. Explicitând, se poate vedea
că modiﬁcarea de pondere în cazul neconcordanței ieșirii cu valoarea dorită
este
∆wi=±2αx (4.29)
Ponderile pot ﬁ inițializate cu orice valoare.
Exemplu: [18] pag 65.
4.6.3 Regula de învățare delta
Prezenta regulă se folosește pentru cazul învățării supervizate cu funcție
de 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(wt
ix))f/prime(wt
ix) (4.30)
Motivația prezenței derivatei în formulă este dată de minimizarea erorii pă-
tratice:
E=1
2(di−oi)2=1
2/parenleftBig
di−f(wt
ix)/parenrightBig2(4.31)
Tehnica de reducere a valorii funcției constă în mișcarea în sens opus gra-
dientului∇E
∇E=−(di−oi)f/prime(wt
ix)x (4.32)
Componentele gradientului sunt
∂E
∂wij=−(di−oi)f/prime(wt
ix)xj,∀j=1,n (4.33)
Modiﬁcarea ponderilor se face astfel:
∆wi=−α∇E (4.34)
undeηeste o constantă pozitivă. O altă scriere este:
∆wi=α(di−oi)f/prime(neti)x (4.35)
Regula poate ﬁ generalizată pentru rețele cu mai multe straturi.
Exemplu: [18] pag 68.
4.6.4 Regula de învățare Widrow-Hoﬀ
A fost enunțată în 1962 și se aplică pentru învățarea supervizată. Regula
foloseș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−wt
ix (4.36)
55

deci ajustarea de ponderi se face cu
∆wi=α(di−wt
ix)x (4.37)
Regula Widrow-Hoﬀ este o formă particulară a regulii delta și mai este
cunoscută sub numele de regula celor mai mici pătrate7. Ponderile sunt
inițializate cu orice valori.
4.6.5 Regula de învățare prin corelație
Se obține prin considerarea lui r=di. Ponderile se modiﬁcă cu valoarea
∆wi=αdix (4.38)
Ponderile sunt inițializate cu zero.
4.6.6 Regula “câștigătorul ia tot”
Regula “winner-takes-all” este un exemplu de învățare competitivă și e
folosită pentru învățarea în mod nesupervizat a proprietăților statistice ale
datelor. Învățarea se bazează pe premisa că din toți neuronii de ieșire unul
(ﬁeeldeindice k)dărăspunsulmaximpentruointrare x. Pondereaaferentă
acestui vector va ﬁ modiﬁcată astfel:
∆wi=α(x−wi) (4.39)
undeα > 0este o valoare mică, de regulă descrescătoare pe măsură ce
procesul de învățare continuă. Indicele ieste ales deci
i= arg max
k/parenleftBig
wt
kx/parenrightBig
(4.40)
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:/bardblwi/bardbl=const,∀i.
7Least Mean Square (LMS).
56

Capitolul 5
Perceptronul liniar
5.1 Motivație, deﬁniții, notații
Scopul cursului este de a prezenta perceptronul liniar – cel mai simplu
tip de neuron, capabil să învețe să separe două mulțimi (clase) de puncte
care sunt liniar separabile.
Pentru perceptronul liniar se folosește instruire supervizată, modelul re-
zultat putând ﬁ folosit pentru clasiﬁcare.
Deﬁniția 6. (Clase liniar separabile) Mulțimile C1șiC2de puncte din
spațiul Rnse numesc liniar separabile dacă există o funcție y:Rn→Rde
forma:
y(x) =n/summationdisplay
i=1wi·xi+b (5.1)
astfel încât:/braceleftBigg
y(x)>0pentru x∈C1
y(x)<0pentru x∈C2(5.2)
În condițiile de mai sus, numim clasa C1clasă pozitivă, iar C2clasă
negativă.
Plecând de la un set de instruire format din mulțimile C1,C2despre care
seștiecăsuntliniarseparabile–darpentrucarefuncția y(·)nusecunoaște–
perceptronul liniar determină coeﬁcienții b,w 1,…,wnpentru care condițiile
din (5.2) sunt îndeplinite.
Ecuațiay(x) = 0, precum și mulțimile C1,C2pe careyle separă au
interpretări geometrice simple. Punctele x∈Rnpentru care y(x) = 0
formează o varietate liniară – notată cu S– de dimensiune n−1; dacăb= 0
atunciy(x) = 0este un hiperplan (subspațiu aﬁn de dimensiune n−1și
deci trecând prin origine); prin abuz de limbaj, în literatură se folosește tot
denumirea de hiperplan pentru suprafața y(x) = 0chiar dacăb/negationslash= 0.
Pentru cazul n= 2,w1>0,w2>0,b<0a se vedea reprezentarea din
ﬁgura 5.1.
57

0–
–
–
–
–
–
–
–-
–
––
–
– –
–-
––+
++
+
+++
++
++
+
+
++
++
+Figura 5.1: Mulțimi separabile liniar și suprafață de separare liniară y(x) =
w1x1 +w2x2+b,w1>0,w2>0,b<0. ClasaC1e clasă pozitivă, clasa C2
e clasă negativă
Suprafața liniară y(x) = 0separă planul în două submulțimi – în cazul
n= 2, în două semiplane. Oricum am alege un punct xdintr-o submulțime
oarecare, semnul lui y(x)este mereu același, iar la trecerea în cealaltă su-
bmulțime semnul se schimbă. Pentru n= 2vorbim de semiplan pozitiv și
semiplan negativ.
Distanța de la origine la suprafața Sse calculează ca:
d=|w0|
/bardblw/bardbl
unde w= (w1,…,wn)tiar/bardblw/bardbleste norma Euclidiană a vectorului w,
/bardblw/bardbl=/radicalBig
w2
1+…w2n. Dacă x1șix2sunt două puncte de pe varietatea
liniarăS, atunci:
y(x1) = 0⇔wt·x1+b= 0 (5.3)
y(x2) = 0⇔wt·x2+b= 0 (5.4)
Scăzând (5.3) din (5.4) obținem wt·(x1−x2) = 0, sau, echivalent, vectorul
weste perpendicular pe varietatea liniară y(x) = 0, a se vedea ﬁgura 5.2.
Distanța dintre un punct xși suprafațaSeste:
z=|y(x)|
/bardblw/bardbl(5.5)
Putem renota termenul liber bdin (5.1) cu w0, putem considera că vec-
torul xmai are o componentă x0= 1; dacă notăm tot cu wvectorul de
58

+
-Figura 5.2: Suprafața de decizie S, distanța de la origine la S, poziția
vectorului de ponderi wfață deS
ponderi extins w= (w0,w1,…,wn)tșix= (x0,x1,…,xn)tatunci funcția
de separare ydin (5.1) se rescrie ca:
y(x) =wt·x (5.6)
5.2 Perceptronul liniar
Setul de instruire este
S=/braceleftBig/parenleftBig
x(i),y(i)/parenrightBig
|x(i)∈Rn,y(i)∈{− 1,1},1≤i≤m/bracerightBig
(5.7)
y(i)este eticheta vectorului de intrare x(i). Putem partiționa vectorii de
intrare x(i)în submulțimile:
•C1- clasa pozitivă, acei x(i)∈Rnpentru care y(i)= +1,
•C2- clasa negativă, acei x(i)∈Rnpentru care y(i)=−1.
SetulSeste astfel dat încât mulțimile C1șiC2sunt liniar separabile –
aceasta ﬁind condiția în care perceptronul poate învăța să construiască o
suprafață de separare.
Reprezentarea unui perceptron este dată în ﬁgura 5.3.
Valoarea de activare a perceptronului este z=wt·x=/summationtextn
i=0wi·xi.
Valoarea de ieșire a perceptronului se calculează cu funcția de activare
“treaptă”:
f(z) =

1, dacăz>0
−1, dacăz<0
nedeﬁnit,altfel(5.8)
59

Figura 5.3: Reprezentarea unui perceptron
Valoarea produsă pentru ponderile wși intrarea xeste:
ˆy=f(wt·x) (5.9)
Dacă punctul xeste astfel încât wt·x>0, atuncif(wt·x) = 1și
spunem că perceptronul indică xca ﬁind de clasă pozitivă. Dacă wt·x<0,
atuncif(wt·x) =−1și spunem că perceptronul indică xca ﬁind de clasă
negativă. Valoarea funcției feste deliberat nedeﬁnită în 0: dacă wt·x= 0
atunci punctul xse aﬂă pe suprafața de separare și nu se poate spune despre
el că ar ﬁ de clasă pozitivă au negativă.
5.3 Algoritmul de instruire a perceptronului
Scopul algoritmului este ca, plecând de la setul de instruire Sdin ecuația
(5.7), să obținem ponderile w= (w0,w1,…,wn)astfel încât:
/braceleftBigg
pentru x(i)∈C1să avem wt·x(i)>0
pentru x(i)∈C2să avem wt·x(i)<0(5.10)
Se va arăta că dacă C1șiC2sunt liniar separabile, atunci algoritmul de
instruire poate să determine o funcție de separare yprecum în ecuația (5.6).
Instruireaporneștedelaponderialeatoarepentruvalorile w0,w1,…,wn;
acestea pot ﬁ luate chiar și 0. Notăm acest vector inițial cu w(1). Printr-un
proces iterativ vom obține vectorii de ponderi w(2),…,w(k),…. Vectorii
de ponderi se vor stabiliza la un moment dat: w(l) =w(l+ 1) =….
Pentru un vector de ponderi curente w(k), intrarea curentă x(i)și eti-
chetaasociată y(i),estimareaprodusădeperceptroneste ˆy(i),ˆy(i)=f/parenleftBig
w(k)t·x(i)/parenrightBig
.
Dacă pentru un w(k)avem ˆy(i)=y(i)pentru tot setul de instruire, atunci
perceptronul recunoaște corect clasele datelor din S. Altfel, este necesar să
se opereze modiﬁcări pentru vectorul de ponderi curent w(k), detaliile ﬁind
date în cele ce urmează.
Săconsiderămponderiledelamomentul k,w(k). Algoritmuldeinstruire
a perceptronului iterează peste setul de instruire. Dacă pentru o pereche
60

/parenleftBig
x(i),y(i)/parenrightBig
∈Savem că ˆy(i)=y(i), atunci pentru acest caz vectorul de
ponderi w(k)nu trebuie modiﬁcat: perceptronul clasiﬁcă corect intrarea
x(i). Dacă ˆy(i)/negationslash=y(i), atunci avem exact unul din următoarele două cazuri:
1.x(i)e de clasă pozitivă, dar e clasiﬁcat ca negativ: ˆy(i)=−1șiy(i)=
+1
2.x(i)edeclasăpozitivă,dareclasiﬁcatcapozitiv: ˆy(i)= +1șiy(i)=−1
Pentru cazul 1 avem că w(k)t·x<0dar ar trebui ca produsul să ﬁe
pozitiv. Trebuiedecimodiﬁcatvectorul w(k)astfelîncât, pentrunoulvector
w(k+1)valoarea produsului scalar cu xsă crească: w(k+1)t·x>w(k)t·x
, în speranța că asta va duce la f(w(k+ 1)t·x) = +1. Modiﬁcarea propusă
∆w(k)este:
∆w(k) =α·x(i)(5.11)
undeαeste un coeﬁcient strict pozitiv. Noul vector de ponderi va ﬁ:
w(k+ 1) = w(k) + ∆ w(k) =w(k) +α·x(i)(5.12)
Veriﬁcăm că vectorul w(k+ 1)duce la creșterea valorii de activare a per-
ceptronului. La momentele kși respectiv k+ 1, pentru vectorul de intrare
x(i)avem activările z(k) =w(k)t·x(i)șiz(k+ 1) = w(k+ 1)t·x(i).
Avem:
z(k+ 1) = w(k+ 1)t·x=/parenleftBig
w(k) +α·x(i)/parenrightBigt·x=
=w(k)t·x+α·/parenleftBig
x(i)/parenrightBigt·x(i)=z(k) +/vextenddouble/vextenddouble/vextenddoublex(i)/vextenddouble/vextenddouble/vextenddouble2≥z(k)(5.13)
cu inegalitate strictă pentru/vextenddouble/vextenddouble/vextenddoublex(i)/vextenddouble/vextenddouble/vextenddouble/negationslash= 0. Avem deci creșterea valorii de
activare a perceptronului, așa cum ne-am propus.
Pentru cazul 2, facem modiﬁcarea ponderilor astfel:
∆w(k) =−α·x(i)(5.14)
deci
w(k+ 1) = w(k) + ∆ w(k) =w(k)−α·x(i)(5.15)
cu aceeași condiție pentru α. Se veriﬁcă, similar ca în (5.13) că z(k+ 1)≤
z(k), cu inegalitate strictă pentru/vextenddouble/vextenddouble/vextenddoublex(i)/vextenddouble/vextenddouble/vextenddouble/negationslash= 0.
Avem deci că:
∆w(k) =

0, dacăy(i)= ˆy(i)
α·x(i),dacă ˆy(i)=−1șiy(i)= +1
−α·x(i),dacă ˆy(i)= +1șiy(i)=−1(5.16)
61

Putem scrie modiﬁcările din ecuațiile (5.11) și (5.14) uniﬁcat, astfel:
∆w(k) =α
2(y(i)−ˆy(i))·x(i)(5.17)
Dacă vrem să calculăm ∆w(k)doar pentru acele cazuri pentru care y(i)/negationslash=
ˆy(i)atunci:
∆w(k) =αy(i)x(i)(5.18)
E posibil ca o singură modiﬁcare a ponderilor să nu ﬁe suﬁcientă pentru
ca tot setul de instruire Ssă ﬁe clasiﬁcat corect. Dacă în decursul unei epoci
de instruire – epocă înseamnă parcurge în întregime a setului de instruire S
– apare măcar o modiﬁcare, se efectuează o nouă epocă. Procesul se încheie
când ponderile se stabilizează, deci setul de instruire Se învățat.
Algoritmul de instruire a perceptronului este:
1. Inițializează w(1)cu componente aleatoare sau cu vectorul nul; k= 1
2. Repetă:
(a)corectClasificat =adevarat
(b) pentru i= 1,m
i. calculează ˆy(i)=f/parenleftBig
w(k)t·x(i)/parenrightBig
ii. dacă ˆy(i)/negationslash=y(i)atunci:
A.corectClasificat =fals
B.w(k+ 1) = w(k) +αy(i)x(i)
C.k=k+ 1
3. Până când corectClasificat =adevarat
4. Vectorul w(k)este vectorul ﬁnal de ponderi pentru perceptron, iar k
este numărul total de setări ale vectorului de ponderi w.
Deși algoritmul modiﬁcă instantaneu ponderile pentru ﬁecare caz în care
ieșirea furnizată de perceptron nu coincide cu eticheta cunoscută, algoritmul
nu este incremental în sensul dat în secțiunea 9.1, având e regulă nevoie de
mai multe epoci de instruire.
Faptul că algoritmul se oprește după un număr ﬁnit de pași este demon-
strat în secțiunea 5.4. Notăm cu wvectorul de ponderi produs la terminarea
algoritmului, w=w(k).
După ce algoritmul de instruire se oprește, perceptronul este folosit pen-
tru a face clasiﬁcarea unui vector x∈Rn, astfel:
/braceleftBigg
dacăwt·x>0,atunci xe de clasă pozitivă
dacăwt·x<0,atunci xe de clasă negativă(5.19)
62

5.4 Convergența perceptronului
Vom demonstra că algoritmul de instruire a perceptronului se termină
în număr ﬁnit de pași, dacă setul de instruire este compus din două mulțimi
C1,C2liniar separabile.
Condițiadeliniarseparabilitatenepermitesăspunemcăexistăunvector
w∗∈Rn+1cu:
/braceleftBigg
pentru x(i)∈C1să avem wt
∗·x(i)>0
pentru x(i)∈C2să avem wt
∗·x(i)<0(5.20)
(a se revedea condițiile 5.10), sau, mai pe scurt,
y(i)·wt
∗·x(i)>0pentru orice i,1≤i≤m (5.21)
Putem presupune că vectorul w∗este de normă 1; în caz contrar se poate
face normarea lui, iar situațiile din (5.21) se mențin.
Întrucât numărul de elemente din setul de instruire este ﬁnit, putem găsi
γ >0astfel încât:
y(i)·wt
∗·x(i)>γpentru orice i,1≤i≤m (5.22)
de exemplu
γ=1
2·min
1≤i≤m/braceleftBig
y(i)·wt
∗·x(i)/bracerightBig
>0 (5.23)
Tot datorită faptului că mulțimea de instruire e ﬁnită, avem că există un
R> 0astfel încât/bardblx(i)/bardbl≤R: toți vectorii de intrare din setul de instruire
sunt cuprinși în interiorul unei sfere centrate în origine și de rază Rsuﬁcient
de mare.
Deși vectorul w∗nu este cunoscut (știm doar că există, pentru că C1și
C2sunt liniar separabile), cantitatea γe și ea necunoscută. Considerarea
acestor cantități e totuși utilă pentru demonstrarea convergenței algoritmu-
lui de instruire a perceptronului. O valoare a lui Rse poate găsi pe baza
datelor, de exemplu
R= max
1≤i≤m/braceleftBig
/bardblx(i)/bardbl/bracerightBig
(5.24)
Două presupuneri care simpliﬁcă partea de demonstrație pentru teorema
ce urmează sunt:
1.α= 1; valoarea lui αnu are de fapt importanță, atâta timp cât e mai
mare ca zero;
2. vectorul w(1)are toate elementele 0.
Teorema 1. (Teorema de convergență a perceptronului) Algoritmul de in-
struire a perceptronului efectuează cel mult R2/γ2modiﬁcări ale ponderilor,
după care returnează un hiperplan de separare.
63

Demonstrație. Pentruk≥1, ﬁe un x(i)clasiﬁcat greșit de perceptron, adică
f(w(k)tx(i))/negationslash=y(i), sau, echivalent:
f(w(k)tx(i))/negationslash=y(i)⇔y(i)·w(k)tx(i)<0 (5.25)
Pentru această situație de clasiﬁcare greșită a unui vector din setul de
instruire, algoritmul efectuează modiﬁcare a lui w(k).
Avem:
w(k+ 1)t·w∗= (w(k) +y(i)x(i))t·w∗ (5.26)
=w(k)t·w∗+y(i)(x(i))t·w∗ (5.27)
>w(k)t·w∗+γ (5.28)
Prin inducție matematică și ținând cont că w(1) = 0, se arată că:
w(k+ 1)t·w∗>kγ (5.29)
Folosim inegalitatea Cauchy-Schwartz ( |at·b|≤/bardbla/bardbl/bardblb/bardbl),a≤|a|∀a∈R
și obținem:
w(k+ 1)t·w∗≤|w(k+ 1)t·w∗|≤/bardblw(k+ 1)/bardbl·/bardblw∗/bardbl=/bardblw(k+ 1)/bardbl(5.30)
și din ultimele două inegalități avem:
/bardblw(k+ 1)/bardbl>kγ (5.31)
Pe de altă parte, avem că:
/bardblw(k+ 1)/bardbl2=/bardblw(k) +y(i)x(i)/bardbl (5.32)
=/bardblw(k)/bardbl2+/bardbly(i)x(i)/bardbl2+ 2w(k)t·x(i)·y(i)(5.33)
=/bardblw(k)/bardbl2+|y(i)|2·/bardblx(i)/bardbl2+ 2w(k)t·x(i)·y(i)(5.34)
≤ /bardblw(k)/bardbl2+/bardblx(i)/bardbl2(5.35)
≤ /bardblw(k)/bardbl2+R2(5.36)
Ținând cont că w(1) = 0, prin inducție matematică se arată că:
/bardblw(k+ 1)/bardbl2≤kR2(5.37)
unde trecerea de la (5.34) la (5.35) se face pe baza inegalității (5.25).
Din inecuațiile (5.31) și (5.37) rezultă că:
k2γ2</bardblw(k+ 1)/bardbl2≤kR2(5.38)
de undek<R2
γ2.
Am obținut deci că indicele kpentru care se fac modiﬁcare de ponderi
nu poate ﬁ oricât de mare, adică algoritmul se termină în timp ﬁnit. Finali-
zarea lui înseamnă totodată obținerea unui set de ponderi pentru forma de
separare liniară care să clasiﬁce corect cazurile din setul de instruire.
Comentariu: Deoarece valoarea lui γnu e cunoscută, rezultatul de mai
sus nu ne spune practic care e numărul efectiv de pași necesari. Totuși,
există o dovadă a faptului că algoritmul nu rulează la inﬁnit.
64

5.5 Algoritmul lui Gallant
Algoritmul lui Pocket – sau algoritmul “buzunarului“ – tratează cazul în
care setul de instruire nu este liniar separabil. Ideea algoritmului este de a
menține vectorul wde ponderi care face cele mai puține erori de clasiﬁcare
pentru date succesive. La ﬁnalul unei epoci se contorizează câte cazuri
din setul de instruire sunt corect clasiﬁcate de vectorul curent de ponderi.
Dacă numărul de clasiﬁcări corecte este mai mare decât pentru vectorul
menținut până până acum într-un “buzunar“ (la început: vectorul w(1)cu
număr de clasiﬁcări corecte cunoscute 0), atunci se actualizează conținutul
“buzunarului”: vectorul curent de ponderi și numărul de clasiﬁcări corecte.
Procesul se repetă de un număr de ori speciﬁcat. La ﬁnal se returnează
vectorul de ponderi din “buzunar“.
5.6 Comentarii
Spre deosebire de regresia logistică, perceptronul liniar nu produce o va-
loare care să exprime în ce măsură modelul consideră că un vector de intrare
aparține clasei pozitive, P(C1|x). Totuși, vine cu demonstrație matematică
pentru convergență, dacă un separator liniar desparte clasa pozitivă de cea
negativă.
La momentul apariției, perceptronul liniar a fost privit ca un motiv clar
pentru care problemele cele mai complexe sunt rezolvabile prin perceptroni.
CarteaPerceptrons1a lui Minsky si Papert, din 1969, arată însă că pecep-
tronul nu poate rezolva probleme care sunt neseparabile liniar, de exemplu
problema XOR. Conjectura lor că utilizarea de mai mulți perceptroni nu
poate să ducă la rezolvarea de probleme neseparabile liniar a devenit exrem
de populară, motiv pentru care cercetările în domeniul rețelelor neurale ar-
tiﬁciale au fost descurajate. Revenirea s–a produs în 1986, când Rumelhart,
Hinton și Williams2au propus o procedură de învățare pentru rețele cu mai
multe straturi de neuroni neliniari care permitea abordarea claselor nesepa-
rabile liniar.
Setul de instruire pentru problema XOR este următorul:
/braceleftBig
((0,0)t,0),((1,1)t,0),((1,0)t,1),((0,1)t,1)/bracerightBig
unde ﬁecare din cele 4 tuple contine o pereche de valori de intrare din {0,1}2
împreună cu eticheta de clasă asociată, 0 sau 1. Se poate demonstra algebric
că nu există un vector de 3 ponderi (w0,w1,w2)t∈R3pentru care:
sgn(w0·1 +w1·0 +w2·0) =sgn(w0·1 +w1·1 +w2·1) = 1 (5.39)
1Marvin Minsky și Seymour Papert, Perceptrons: an introduction to computational
geometry , , MIT Press, 1969.
2David E. Rumelhart, Geoﬀrey E. Hinton, Ronald J. Williams, Learning representa-
tions by back-propagating errors , Nature, volume 323, issue 6088, pp. 533-536, 1986.
65

iar
sgn(w0·1 +w1·0 +w2·1) =sgn(w0·1 +w1·1 +w2·0) =−1(5.40)
Pentru problema n–dimensională, clasa de ieșire pentru vectorul binar x∈
{0,1}neste 1 dacă numărul de componente 1 este impar, altfel 0. Se poate
arăta că și pentru cazul ndimensional problema nu e rezolvabilă printr–un
separator liniar.
66

Capitolul 6
Perceptroni multistrat
Rețeleleneuralemultistrat—sauperceptroniimultistrat,multilayerper-
ceptrons (MLPs) — sunt folosite pentru probleme de regresie, de clasiﬁcare
și de estimare de probabilități condiționate. Instruirea este supervizată.
Sunt cea mai populară variantă de rețele neurale artiﬁciale și fac parte din
clasa mai mare a rețelelor cu propagare înainte.
6.1 Motivație pentru rețele neurale multistrat
Conform celor din cursul precedent, un perceptron liniar este capabil să
găsească un hiperplan de separare pentru două mulțimi, dacă – și numai
dacă – ele sunt liniar separabile. Există însă exemple de probleme simple
care nu sunt liniar separabile — și deci nerezolvabile de către perceptron
liniar — dar care pot ﬁ totuși separate. În plus, dorim să rezolvăm și altfel
de probleme decât de clasiﬁcare binară: regresie (estimare de valoare de
ieșire de tip continuu), estimare de probabilitate condiționată, clasiﬁcare
între mai mult de două clase. Cursul de față conține modele bazate pe
neuroni neliniari în care se pot rezolva toate aceste tipuri de probleme.
Figura 6.1 conține cea mai celebră problemă care nu se poate rezolva de
către un clasiﬁcator liniar: problema XOR. Se consideră setul
S={((0,0),0),((0,1),1),((1,0),1),((1,1),0)}
unde ﬁecare din cele patru elemente este compus din pereche de intrare
(x,y)∈ {0,1}2și dintr–o etichetă de clasă binară. Se poate demonstra
algebric că într–adevăr nu se pot separa cele două clase printr–o dreaptă
(punctele de clasă 0 să ﬁe de o parte a dreptei, cele de clasa 1 de cealaltă
parte). Un alt exemplu este dat în ﬁgura 6.2 [7].
Intuim că un singur neuron e prea puțin pentru probleme complexe de
separare. Pe de altă parte, concatenarea mai multor neuroni cu funcție de
activare liniară este echivalentă cu produsul dintre înmulțirea unei secvențe
de matrice cu vectorul de intrare. Datorită faptului că înmulțirea de matrice
67

xy
11Figura 6.1: Problema XOR. Clasele sunt marcate cu forme și culori diferite.
Se poate demonstra că nu se poate trasa o dreaptă în plan care să aibă de
o parte a ei doar puncte din clasa “0” și de cealaltă parte doar puncte de
clasă “1”.
Figura 6.2: Două clase de puncte ce nu sunt separabile liniar [7].
este o operație distributivă și produce tot o matrice, operația este echiva-
lentă cu înmulțirea unei matrice cu vectorul de intrare. Obținem de aici că
succesiunea de neuroni cu funcție de activare liniară este echivalentă cu un
singur neuron cu funcție de activare liniară.
Vom folosi deci mai mulți neuroni, iar funcțiile lor de activare vor ﬁ
neliniare.
Tabelul 6.1 conține notațiile principale care se folosesc în acest curs.
6.2 Setul de instruire
Rețelele din acest capitol sunt pentru instruire de tip supervizat. Setul
de instruire este de forma:
S=/braceleftBig/parenleftBig
x(1),d(1)/parenrightBig
,/parenleftBig
x(2),d(2)/parenrightBig
,…,/parenleftBig
x(p),d(p)/parenrightBig/bracerightBig
(6.1)
unde x(i)∈Rniard(i)este, după caz:
•pentru o problemă de regresie: vector oarecare din Rm;
•pentruoproblemădeclasiﬁcaresauestimaredeprobabilitățipentru m
clase: vectori de forma (1,0,…, 0),(0,1,0,…, 0), …, (0,0,…, 0,1)
68

Noțiune sau notație Explicație
p numărul de perechi în setul de instruire
x(i)vector de intrare din setul de instruire,
x(i)=/parenleftBig
x(i)
1,…,x(i)
n/parenrightBigt,1≤i≤p
d(i)ieșirea asociată intrării x(i), din setul de instruire,
d(i)=/parenleftBig
d(i)
1,…,d(i)
m/parenrightBigt,1≤i≤p
L numărul de straturi din rețeaua neurală, inclusiv
straturile de intrare și de ieșire
nod neuron – dacă apare în stratul 2,3,…,L– sau
nod de intrare – dacă apare în primul strat
nl numărul de noduri din stratul l,1≤l≤L;
z(l)
i valoarea de activare a neuronului idin stratul l,
pentru 2≤l≤L,1≤i≤nl
z(l)vectorul conținând valorile de activare ale neuronilor
din stratul l,z(l)=/parenleftBig
z(l)
1,…,z(l)
nl/parenrightBigt,2≤l≤L
a(l)
i valoarea de ieșire a celui de al i–lea nod din stratul l,
pentru 1≤l≤L,1≤i≤nl
a(l)vectorul cu valorile de ieșire ale nodurilor din stratul l,
pentru 1≤l≤L,a(l)=/parenleftBig
a(l)
1,…,a(l)
nl/parenrightBigt
w(l)
ij ponderea legăturii între neuronul ide pe stratul l+ 1
și noduljde pe stratul l,1≤l≤L−1,
1≤i≤nl+1,1≤j≤nl
W(l)matricea de ponderi dintre stratul lși stratull+ 1,
1≤l≤L−1,W(l)
ij=w(l)
ij,1≤i≤nl+1,1≤j≤nl
W(l)
i liniaia matricei W(l),1≤l≤L−1,1≤i≤nl+1
b(l)
i ponderea de bias pentru neuronul idin stratul l+ 1,
1≤l≤L−1,1≤i≤nl+1
b(l)vectorul ponderilor de bias de la stratul llal+ 1,
b(l)=/parenleftBig
b(l)
1,…,b(l)
nl+1/parenrightBigt,1≤l≤L−1
f funcție de activare a neuronului
W secvența de matrice de ponderi (W1,W2,…,WL−1)
b secvența de vectori de ponderi de bias (b1,b2,…,bL−1)
J(W,b) eroare empirică pentru setul de instruire sau minibatch
J/parenleftBig
W,b;x(i),d(i)/parenrightBig
eroarea pentru perechea de vectori de instruire/parenleftBig
x(i),d(i)/parenrightBig
,
1≤i≤p
o(i)vector coloană de ieșire corespunzător intrării x(i),
calculat de rețea
lsemnalul de eroare pentru stratul l,2≤l≤L
⊙ produs Hadamard
Tabela 6.1: Notații folosite
69

cumvalori binare, din care doar cea de pe poziția aferentă clasei
curente este unu iar restul sunt zero1.
6.3 Rețeaua neurală multistrat
6.3.1 Arhitectură
Există mai multe modalități de dispunere a neuronilor; noi vom folosi
o arhitectură de tip multistrat, feedforward, numită perceptron multistrat
– chiar dacă neuronii folosiți nu sunt perceptroni, ci neuroni cu funcție de
activare neliniară. O rețea multistrat se compune din minim trei straturi:
•strat de intrare ce preia valorile de intrare; nu are rol computațional,
nu este format din neuroni2;
•măcar un strat ascuns, compus din neuroni;
•strat de ieșire, de asemenea compus din neuroni, produce estimări de
valori care sunt apoi comparate cu ieșirile dorite.
Un strat ascuns este unul care nu primește direct intrări și nu produce
valori de ieșire. Neuronii ascunși produc trăsături noi pe baza vectorilor de
intrare, trăsături care sunt mai apoi necesare rețelei neurale pentru produ-
cerea unei estimări. Este posibil ca o rețea să aibă mai mult de un neuron
în stratul de ieșire, așa cum se vede în ﬁgura 6.4.
Se consideră că instruirea e mai eﬁcientă dacă pe lângă valorile de intrare
și pe lângă valorile calculate de un strat de neuroni se mai furnizează o
valoare constantă, de regulă +1, înmulțită cu o pondere de bias3. Ponderile
dintre straturi precum și aceste ponderi de biassunt instruibile, adică se vor
modiﬁca prin procesul de învățare4.
O reprezentare de rețea neurală cu trei straturi și o ieșire este dată în
ﬁgura 6.3; o rețea cu 4 straturi și două ieșiri este reprezentată în ﬁgura 6.4.
Nu există o relație anume între numărul de straturi ascunse și numărul de
neuroni de intrare și ieșire.
Vom considera că avem L≥3straturi și în ﬁecare strat l(2≤l≤L)
un număr de nlneuroni. Stratul de intrare are n1=nnoduri, numărul
de neuroni din stratul de ieșire este nL=mdat de: numărul de clase
pentru care se face recunoașterea (la problemă de clasiﬁcare sau estimare
1Așa–numita codiﬁcare one–hot sau1-din-m.
2Motiv pentru care unii autori nu îl consideră un strat propriu–zis; frecvent se folo-
sește exprimarea că o rețea are “ k” straturi ascunse, cele de intrare și ieșire ﬁind oricum
existente. În cele ce urmează considerăm intrarea ca formând un strat.
3Unii autori consideră valoarea constantă -1; nu este esențial, deoarece ponderile sunt
instruibile și pot avea orice semn.
4O discuție asupra necesității considerării bias–ului este la
ftp://ftp.sas.com/pub/neural/FAQ2.html#A_bias
70

de probabilitate condiționată) respectiv numărul de ieșiri care se doresc a ﬁ
aproximate (la regresie).
Pentru oricare dintre ﬁguri:
•valorilex1,x2,x3suntcomponentelevectoruluideintrare x= (x1,x2,x3)t;
semaiconsiderăîncăointrarecuvaloareaconstantă+1, aferentă bias–
ului;
•valoareaa(l)
ieste ieșirea nodului idin stratul l,1≤l≤L,1≤i≤nl;
se remarcă în ﬁguri prezența valorilor constante +1 în toate straturile,
exceptând cel de ieșire. Pentru stratul de intrare, a(1)
i=xi;
•valoareahW,b(x)este ieșirea calculată de către rețea pentru vectorul
curent de intrare x;hW,b(x)∈Rpentru ﬁgura 6.3 și hW,b(x)∈R2
pentru ﬁgura 6.4.
Figura 6.3: Rețea MLP cu 3 straturi
Figura 6.4: Rețea MLP cu 4 straturi
Perechea (W,b)formează mulțimea ponderilor și a valorilor de bias din
în rețea. Folosim următoarele notații:
71

•ponderile dintre stratul de intrare și stratul ascuns sunt conținute în
matricea W(1):w(1)
ijeste ponderea legăturii dintre neuronul ial stra-
tului al doilea și nodul jdin stratul de intrare; se remarcă ordinea
indicilor, utilă mai departe pentru operațiile de algebră liniară ce vor
ﬁ folosite;
•în general, notăm cu w(l)
ijponderea legăturii dintre al i–lea neuron din
stratull+ 1și alj–lea nod (neuron sau nod de intrare) din stratul
precedentl(1≤l≤L−1);
•valoarea ponderii dintre intrarea constantă +1din stratul de intrare
și neuronul idin primul strat ascuns este stocată de b(1)
i,1≤i≤n2;
•în general, coeﬁcientul de bias provenind din stratul l(1≤l≤L−1)
și care afectează neuronul idin stratul l+ 1este notat cu b(l)
i,1≤i≤
nl+1.
În ce privește numărul de ponderi – atât cele din matricele W(l)cât și
ponderile de bias – avem, pentru 1≤l≤L−1:
•matricea W(l)de ponderi dintre stratul lși stratull+ 1arenl+1linii
șinlcoloane;
•vectorul coloană de coeﬁcienți bias b(l)conținenl+1valori, având
forma b(l)=/parenleftBig
b(l)
1,b(l)
2,…,b(l)
nl+1/parenrightBigt.
6.3.2 Funcții de activare
Fiecare neuron agregă valorile din nodurile din stratul anterior – inclu-
zând și termenul constant +1 multiplicat cu coeﬁcientul de bias. Neuronul
de indiceidin stratul l>1are valoarea de activare calculată ca:
z(l)
i=w(l−1)
i1·a(l−1)
1 +w(l−1)
i2·a(l−1)
2 +···+w(l−1)
i,nl−1·a(l−1)
nl−1+b(l−1)
i(6.2)
=W(l−1)
i·a(l−1)+b(l−1)
i,1≤i≤nl (6.3)
unde: W(l−1)
ieste liniaia matricei W(l−1),a(l−1)
ieste, după caz: valoarea
de ieșire a neuronului idin stratul l−1(dacăl−1>1)sau intrarea xidin
vectorul de intrare curent (dacă l−1 = 1). Notând cu z(l)vectorul coloană/parenleftBig
z(l)
1,z(l)
2,…,z(l)
nl/parenrightBigt, putem scrie matricial:
z(l)=W(l−1)·a(l−1)+b(l−1),2≤l≤L (6.4)
Pe baza valorii de activare z(l)
ia neuronului idin stratul lse calculează
ieșirea sa folosind funcția de activare f:
a(l)
i=f/parenleftBig
z(l)
i/parenrightBig
(6.5)
72

pentru 2≤l≤L,1≤i≤nl. Dacă folosim notația f/parenleftBig
(h1,h2,…,hk)t/parenrightBigdef=
(f(h1),f(h2),…,f (hk))t– adică se aplică funcția fpe ﬁecare valoare din
vectorul argument, sau facem vectorizarea funcției f– atunci putem scrie
mai compact ecuația (6.5) sub forma:
a(l)=f/parenleftBig
z(l)/parenrightBig
(6.6)
Funcțiaf(·)este necesară în pasul de propagare înainte; pentru pasul de
propagare înapoi a erorii este folosită derivata ei. Funcția de activare poate
avea formele5:
1.funcția logistică sigmoidă:
f=σ:R→(0,1),f(z) =σ(z) =1
1 + exp(−z)(6.7)
Derivata acestei funcții este:
f/prime(z) =σ/prime(z) =σ(z)(1−σ(z)) =f(z)·(1−f(z))(6.8)
2.funcția tangentă hiperbolică :
f= tanh : R→(−1,1),f(z) = tanh(z) =exp(z)−exp(−z)
exp(z) + exp(−z)(6.9)
a cărui derivată este:
f/prime(z) = tanh/prime(z) = 1−tanh2(z) = 1−f2(z)(6.10)
Se arată ușor că între cele două funcții de activare tanhșiσexistă
relația:
tanh(z) = 2·σ(2z)−1 (6.11)
Înpracticăfuncția tanhdărezultatemaibunedecâtsigmoidalogistică.
O explicație teoretică se găsește în [26]; demonstrații empirice sunt în
[4].
3.funcția liniară:
f(z) =a·z+b (6.12)
cu derivata f/prime(z) =a; frecvent se iau a= 1,b= 0. Este utilizată
dacă se dorește ca la ieșire valorile să ﬁe în afara intervalelor (0,1)și
(−1,1), cum se întâmplă la funcțiile de activare de mai sus.
5Dar alte funcții de activare mai pot ﬁ considerate, de exemplu combinații liniare de
polinoame Hermite.
73

4.funcția softmax:
softmax (z;c) =exp(zc)
m/summationtext
i=1exp(zi)(6.13)
undeceste indicele neuronului, iar meste numărul total de neuroni
din stratul său. Funcția softmax a mai fost folosită la regresia logistică
pentru cazul a mai mult de două clase; zeste vector cu valori de
activare, z= (z1,…,zm)t.
Funcția softmax este utilă pentru a transforma din valori oarecare în
distribuție de probabilitate: se arată ușor că 1>softmax (z;c)>0∀c
și/summationtextm
c=1softmax (z;c) = 1. De regulă, softmax se folosește pentru
stratul de ieșire și valorile furnizate se interpretează convenabil drept
probabilitateacaintrareacurentăsăﬁedeclasă c,1≤c≤m; clasiﬁca-
rea se face găsind acel indice 1≤c≤mpentru care softmax (z;c)este
maxim. Se utilizează în stratul de ieșire a rețelei neurale de clasiﬁcare
sau estimare de probabilitate.
Derivatele parțiale ale funcției softmax sunt:
∂softmax (z;i)
∂zj=/braceleftBigg
softmax (z;i)·(1−softmax (z;i))dacăi=j
−softmax (z;i)·softmax (z;j)dacăi/negationslash=j
(6.14)
5.funcția Rectiﬁed Linear Unit (ReLU):
f(z) = max(0,z) =/braceleftBigg
0dacăz≤0
zdacăz>0(6.15)
Reprezentarea graﬁcă e dată în ﬁgura 6.5.
Chiar dacă funcția este liniară pe porțiuni, ea este neliniară în ansam-
blu. Faptul că doar într–un punct nu e derivabilă nu deranjează în
practică.
6.funcția Parametric ReLU (PReLU) :
f(z) =/braceleftBigg
αzdacăz≤0
zdacăz>0(6.16)
undeα>0[28], reprezentând o ușoară generalizare a funcției ReLU.
Graﬁcul funcției pentru α= 0.1este dat în ﬁgura 6.6.
Pentruα= 0.01se obține un caz particular vehiculat în literatură,
Leaky ReLU.
74

−10.0 −7.5 −5.0 −2.5 0.0 2.5 5.0 7.5 10.0
x0246810ReLU(x)Figura 6.5: Graﬁcul funcției de activare ReLU
7.funcția Exponential Linear Units (ELU) are forma:
f(z) =/braceleftBigg
a(ez−1)zdacăz≤0
z dacăz>0(6.17)
Este admis ca funcția de activare să difere de la strat la strat sau de la
neuron la neuron.
6.4 Pasul de propagare înainte
Odată ce arhitectura rețelei e ﬁxată – numărul de straturi ascunse și
numărul de neuroni în ﬁecare strat precum și funcțiile de activare – se poate
trece la instruirea și apoi utilizarea ei. Pasul de propagare înainte preia un
vector de intrare x= (x1,…,xn)tși produce modiﬁcări în starea neuro-
nilor rețelei pornind de la intrare și acționând asupra succesiv straturilor
2,…,L−1, ceea ce dă și numele familiei din care face parte acest tip de re-
țea: “cupropagareînainte”, sau“feedforward”. Ieșiriledinultimulstratsunt
folosite pentru predicție – regresie, estimare de probabilitate condiționată
sau clasiﬁcare.
75

−10.0 −7.5 −5.0 −2.5 0.0 2.5 5.0 7.5 10.0
x0246810PReLU(x)Figura 6.6: Graﬁcul funcției de activare PReLU pentru α= 0.1
După cum s–a mai aﬁrmat, stratul de intrare nu are rol computațional;
valoare sa de ieșire este chiar vectorul de intrare xfurnizat rețelei:
a(1)=x (6.18)
Dacă se cunosc valorile de ieșire ale nodurilor din stratul lse pot calcula
valorile de activare ale neuronilor din stratul l+ 1și apoi valorile lor de
ieșire, astfel:
z(l)=W(l−1)·a(l−1)+b(l−1)(6.19)
a(l)=f(z(l)) (6.20)
pentrul= 1,2,…L−1, cuf(·)funcție de activare ce se aplică pe ﬁecare
componentă a vectorului. Vom nota cu ovectorul de mvalori de ieșire
produs de către rețea:
o=a(L)(6.21)
Se recomandă ca operațiile date mai sus să ﬁe implementate folosind
biblioteci optimizate de algebră liniară, ce permit înmulțirea eﬁcientă de
matrice și calcul vectorizat pe CPU sau GPU — Octave, Matlab, Numpy,
ND4J + Canova, Theano, Tensorﬂow etc.
76

6.5 Funcții de cost
Fiecare pereche din S,/parenleftBig
x(i),d(i)/parenrightBig
(1≤i≤p) va produce valoare de
eroare astfel: se furnizează vectorul x(i)ca intrare în rețea și se calculează un
vectordeieșire o(i), reprezentândestimareaprodusăderețeapentruintrarea
furnizată; se folosește o funcție de cost, sau de eroare, J/parenleftBig
W,b;x(i),d(i)/parenrightBig
care se dorește a ﬁ cu atât mai mică cu cât vectorul o(i)e mai apropiat de
d(i), și cu atât mai mare cu cât cei doi vectori sunt mai depărtați. În plus, se
mai consideră un factor de regularizare care împiedică ponderile să devină
prea mari în valoare absolută, caz asociat de regulă cu un comportament
instabil al rețelei: variații mici ale intrării duc la salturi mari în straturile
ascunse și la ieșire.
Forma generală a funcției de eroare este:
J(W,b) =
1
pp/summationdisplay
i=1eroare empirică pentru (x(i),d(i))/bracehtipdownleft/bracehtipupright/bracehtipupleft/bracehtipdownright
J/parenleftBig
W,b;x(i),d(i)/parenrightBig

/bracehtipupleft /bracehtipdownright/bracehtipdownleft /bracehtipupright
Eroarea empirică pe tot setul de antrenare+λ
2L−1/summationdisplay
l=1nl/summationdisplay
i=1nl+1/summationdisplay
j=1/parenleftBig
w(l)
ji/parenrightBig2
/bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipupright
Factor de regularizare
(6.22)
undeλ>0estecoeﬁcientulderegularizare. Ultimultermenesteregularizare
L2, osumădepătratedenormeFrobeniuspestematricele W(1),…,W(l−1):
nl/summationdisplay
i=1nl+1/summationdisplay
j=1/parenleftBig
w(l)
ji/parenrightBig2def=/vextenddouble/vextenddouble/vextenddoubleW(l)/vextenddouble/vextenddouble/vextenddouble2
F(6.23)
De regulă, bibliotecile pentru algebra liniară includ implementări eﬁciente
pentru calculul normei Frobenius. O subliniere importantă este că ponderile
de bias nu sunt supuse regularizării.
În cazul unei probleme de regresie, cea mai utilizată funcție de eroare
J(W,b;x(i),d(i))cemăsoarăcalitateauneipredicțiipentruperechea/parenleftBig
x(i),d(i)/parenrightBig
este eroarea L2pătratică:
J/parenleftBig
W,b;x(i),d(i)/parenrightBig
=1
2·/vextenddouble/vextenddouble/vextenddoubled(i)−o(i)/vextenddouble/vextenddouble/vextenddouble2(6.24)
unde/bardblv/bardbleste norma L2a vectorului v= (v1,…,vk)t:
/bardblv/bardbl=/radicaltp/radicalvertex/radicalvertex/radicalbtk/summationdisplay
i=1v2
i
În acest caz funcția de eroare pentru tot setul de instruire devine:
J(W,b) =/bracketleftBigg
1
2pp/summationdisplay
i=1/vextenddouble/vextenddouble/vextenddoubled(i)−o(i)/vextenddouble/vextenddouble/vextenddouble2/bracketrightBigg
+λ
2L−1/summationdisplay
l=1/vextenddouble/vextenddouble/vextenddoubleW(l)/vextenddouble/vextenddouble/vextenddouble2
F(6.25)
77

Pentru probleme de clasiﬁcare se preferă utilizare funcției de eroare
cross–entropy iar în stratul de ieșire funcția de activare să ﬁe softmax:
J(W,b;x(i),d(i)) =−m/summationdisplay
j=1/bracketleftBig
d(i)
jlno(i)
j+/parenleftBig
1−d(i)
j/parenrightBig
ln/parenleftBig
1−o(i)
j/parenrightBig/bracketrightBig
(6.26)
undepentruvectorul d(i)=/parenleftBig
d(1)
j,d(2)
j,…,d(m)
j/parenrightBig
sefoloseștecodiﬁcareaone–
hot. În acest fel, funcția totală de eroare J(W,b)calculată pentru setul de
instruire devine:
J(W,b) =

−1
pp/summationdisplay
i=1m/summationdisplay
j=1/bracketleftBig
d(i)
jlno(i)
j+/parenleftBig
1−d(i)
j/parenrightBig
ln/parenleftBig
1−o(i)
j/parenrightBig/bracketrightBig

+λ
2L−1/summationdisplay
l=1/vextenddouble/vextenddouble/vextenddoubleW(l)/vextenddouble/vextenddouble/vextenddouble2
F
(6.27)
6.6 Inițializarea ponderilor rețelei
Valorile inițiale ale ponderilor Wșibsunt setate aleator, în jurul lui
zero. Este necesar ca valorile ponderilor să nu ﬁe toate egale; dacă ar ﬁ toate
egale, ﬁecare neuron ar avea exact aceași valoare de intrare: ﬁecare neuron
e legat la exact aceleași intrări ca și ceilați din stratul său; mai departe,
dacă ponderile cu care se înmulțesc intrările sunt egale, atunci valoarea de
activare a ﬁecărui neuron de pe acel strat e aceeași (ponderea constantă
folosită se dă factor comun); argumentul se veriﬁcă începând cu propagarea
de la stratul de intrare. Am ajunge deci ca neuroni de pe același strat să
calculeze exact aceleași valori, ceea ce e inutil.
Strategii mai raﬁnate de ințializare sunt cele propuse de Glorot et al.
[27] și He et al.[28]. Pentru arhitecturile de tip deep learning se preferă
o preantrenare nesupervizată a ponderilor [26] sau preluarea unor ponderi
care au fost antrenate pentru un set de date (o problemă) similară cu cea
curentă – transfer de învățare6.
6.7 Algoritmul backpropagation
Se dorește modiﬁcarea atât a ponderilor din matricele W(l)cât și a
coeﬁcienților de bias b(l)astfel încât valoarea funcției de eroare J(W,b)să
scadă. Sevafolosidecăutaredupădirecțiagradientului7,încaremodiﬁcarea
unei ponderi w(l)
ijse efectuează astfel:
w(l)
ij=w(l)
ij−α∂J
∂w(l)
ij(W,b) (6.28)
6Eng: transfer learning
7Eng: gradient descent
78

Ponderile de bias b(l)
ijse modiﬁcă similar:
b(l)
i=b(l)
i−α∂J(W,b)
∂b(l)
i(W,b) (6.29)
unde pentru ambele ecuații de mai sus α>0este rata de învățare.
Avem trei variante de lucru pentru modiﬁcarea ponderilor:
1.varianta stochastic gradient descent: pentru ﬁecare pereche din
setul de instruire/parenleftBig
x(i),d(i)/parenrightBig
se calculează valoarea funcției de eroare
J/parenleftBig
W,b;x(i),d(i)/parenrightBig
, se calculează și se aplică modiﬁcările pentru pon-
derilew(l)
ijșib(l)
i; următoarea pereche de instruire folosește valorile de
ponderi modiﬁcate la acest pas;
2.varianta oﬀ–line saubatch: se calculează modiﬁcările de ponderi
w(l)
ijșib(l)
icare trebuie efectuate pentru ﬁecare pereche de vectori din
setul de instruire; la ﬁnal se calculează media tuturor acestor modiﬁ-
cări și se actualizează ﬁecare pondere w(l)
ijșib(l)
icu media corepunză-
toare. Algoritmul dat mai jos implementează această versiune.
3.varianta minibatch: se imparte setul de instruire in subseturi
disjuncte ( minibatches ) de exemplu, de câte 100 de perechi/parenleftBig
x(i),d(i)/parenrightBig
;
pentru ﬁecare minibatch se calculează media modiﬁcărilor datorate
valorilor din minibatch; se modiﬁcă ponderile/parenleftBig
x(i),d(i)/parenrightBig
cu media
pe minibatch, apoi se trece la următorul minibatch. Este o variantă
intermediară între stochastic gradient descent – modiﬁcarea se face
imediat după ﬁecare pereche din S– și cea batch – în care modiﬁcarea
ponderilor se face doar după ce se procesează tot setul S; în practică
este cea mai folosită strategie.
Întoatecazuriledemaisus: otrecerecompletăpestesetuldeinstruirese
numește epocă. Se execută mai multe epoci de instruire. Numărul epocilor
de instruire poate ﬁ:
•dat apriori, de exemplu 200;
•determinat prin urmărirea valorii funcției de eroare peste un set de
validare, un set disjunct față de setul de instruire S. Dacă se constată
că eroarea pe setul de validare începe să crească în timp ce eroarea pe
setuldeinstruirecontinuăsăscadă, atuncisedecideîncetareainstruirii
– a se vedea ﬁgura 6.7
Vom prezenta varianta de instruire batch, întrucât poate ﬁ ușor adaptată
la minibatch sau stochastic gradient descent. Trecerea de la ecuațiile (6.25)
și (6.27) la cazul în care se face antrenarea pe minibatch-uri este imediată:
79

Num rul de epociFunc
ia de eroare
Eroare
pe setul de antrenareEroare
pe setul de validare
Epoc la care instruirea
trebuie oprit Figura 6.7: Evoluția valorilor funcției de eroare pentru setul de antrenare,
respectiv cel de validare. Dacă se contină antrenarea, eroare pe setul de
antrenarescade, darpentrusetuldetestareîncepesăcreascădelaoanumită
epocă. Se recomandă oprirea instruirii dacă eroarea pe setul de validare
începe să crească.
însumarea de ptermeni din setul de instruire se substituie cu însumare peste
termenii care compun acel minibatch. Pentru stochastic gradient descent
avem numitorul p= 1.
Proﬁtânddefaptulcăfuncțiadeeroareesteosumădetermenișiderivata
unei sume de funcții este suma derivatelor, avem:
∂J
∂w(l)
ij(W,b) =
1
pp/summationdisplay
k=1∂J
∂w(l)
ij(W,b;x(k),d(k))
+λw(l)
ij (6.30)
respectiv pentru ponderile de bias
∂J
∂b(l)
i(W,b) =1
pp/summationdisplay
k=1∂
∂b(l)
iJ(W,b;x(k),d(k)) (6.31)
Formele matriceale ale (6.30) și (6.31) rezultă imediat și sunt explicitate
în algoritmul de instruire ce urmează.
Algoritmul backpropagation este cel care speciﬁcă ordinea de calculare
a derivatelor parțiale. Vom folosi în cele ce urmează funcția de eroare L2
pătratică conform ecuației (6.24); pentru funcția de eroare cross–entropy e
nevoie să se calculeze corespunzător formele derivatelor parțiale ale funcției
de eroare – a se vedea ﬁnalul acestei secțiuni.
Algoritmul funcționează astfel: pentru o pereche de instruire/parenleftBig
x(i),d(i)/parenrightBig
se face pasul de propagare înainte, și se obține vectorul de ieșire o(i); pentru
80

ﬁecare strat de neuroni l, începând de la ultimul, se calculează un termen
de eroare(l)care măsoară cât de mult e “responsabil” stratul l(mai precis:
ﬁecare neuron din strat) pentru discrepanța dintre ieșirea o(i)și valoarea
dorită d(i).
Înainte de detalia algoritmul de instruire a rețelei MLP, este nevoie să
introducem produsul Hadamard al două matrice; produsul se notează cu ⊙
și se aplică pentru două matrice care au același număr de linii și respectiv
același număr de coloane: dacă A= (aij)1≤i≤q,1≤j≤rșiB= (bij)1≤i≤q,1≤j≤r
sunt cele două matrice, atunci matricea produs Hadamard C=A⊙B=
(cij)1≤i≤q,1≤j≤rare elementele:
cij=aij·bij (6.32)
Algoritmul backpropagation detaliat – varianta batch – este:
1. Inițializeazăvalorile ∆W(l),∆b(l)cumatricenule,pentru l= 1,…,L−
1:
∆W(l)=0nl+1×nl (6.33)
∆b(l)=0nl+1,vector coloană (6.34)
2. Pentru ﬁecare pereche/parenleftBig
x(i),d(i)/parenrightBig
calculează corecția pentru ponderi
și ponderile de bias:
2.1. Efectuează pasul de propagare înainte, conform secțiunii 6.4, și
obține ieșirea estimată o(i)
2.2. Pentru stratul de ieșire calculează semnalul de eroare:
(L)=−/parenleftBig
d(i)−o(i)/parenrightBig
⊙f/prime/parenleftBig
z(L)/parenrightBig
(6.35)
unde am presupus că funcția f/primese vectorizează peste vectorul
z(L).
2.3. Pentru straturile l=L−1,…2se calculează semnalul de eroare:
(l)=/bracketleftbigg/parenleftBig
W(l)/parenrightBigt·(l+1)/bracketrightbigg
⊙f/prime/parenleftBig
z(l)/parenrightBig
(6.36)
2.4. Calculează derivatele parțiale dorite, pentru l= 1,…,L−1:
∂J
∂W(l)(W,b;x(i),d(i)) =(l+1)·/parenleftBig
a(l)/parenrightBigt(6.37)
respectiv pentru ponderile de bias:
∂J
∂b(l)(W,b;x(i),d(i)) =(l+1)(6.38)
81

2.5. Acumulează semnalul de corecție, pentru l= 1,…,L−1:
∆W(l)= ∆W(l)+∂J
∂W(l)(W,b;x(i),d(i)) (6.39)
∆b(l)= ∆b(l)+∂J
∂b(l)(W,b;x(i),d(i))(6.40)
3. După ce toate perechile din setul de instruire au fost considerate, mo-
diﬁcă valorile ponderilor și coeﬁcienții de bias, pentru l= 1,…L−1:
W(l)=W(l)−α/bracketleftbigg/parenleftbigg1
p∆W(l)/parenrightbigg
+λW(l)/bracketrightbigg
(6.41)
b(l)=b(l)−α/bracketleftbigg/parenleftbigg1
p∆b(l)/parenrightbigg/bracketrightbigg
(6.42)
4. Repetare: se repetă de la pasul 1 până când eroarea J(W,b)scade
sub un prag Emax.
Pentru cazul în care funcția de eroare este cross–entropy (6.27) în loc de
eroareaL2pătratică, se arată că pentru perechea (x(i),d(i)):
(L)=a(L)−d(i)(6.43)
substituind formula de calcul (6.35). Utilizarea funcției de eroare cross en-
tropy duce la o viteză mai mare de învățare pentru probleme de clasiﬁcare
decât dacă se folosește L2pătratică [4].
6.8 Justiﬁcarea matematică a algoritmului
TODO
6.9 Utilizarea rețelei
După ce se face antrenarea rețelei, ea se poate folosi pentru a face pre-
dicții pentru date din setul de testare T=/braceleftBig
x(j)|1≤j≤q/bracerightBig
. Fiecare vector
dinTeste trecut prin rețea, conform pasului de propagare înainte și se obțin
valori de ieșire estimate (predicții) o(1),…,o(q), toate din Rm.
Dacă valorile de ieșire sunt interpretate ca probabilități condiționate,
adică:
oi=P(clasai|x),1≤i≤m (6.44)
atunci clasiﬁcarea se face găsind acel indice ipentru care oie maxim. Pentru
clasiﬁcare se procedează la fel: indicele ipentru care se obține maximul
vectorului oeste indicele clasei prezise de rețeaua MLP.
6.10 Discuții
TODO
82

Capitolul 7
Memorii asociative
bidirecționale
Memoriile asociative bidirecționale (MAB) permit stocarea și regăsirea
datelor. Căutarea se face pe baza similarității care există între vectorul
furnizat ca intrare și ceea ce este stocat în rețea. Regăsirea se face pe baza
similarității între vectorul furnizat inițial și a unui vector stocat de rețea.
Se lucrează cu perechi de vectori asociați memorați de rețea; plecând de la
oricare dintre ele sau de la unul similar cu ele se dorește regăsirea celuilalt.
Datele memorate sunt reprezentate în ponderile rețelei.
Instruirea poate ﬁ atât supervizată, cât și nesupervizată. Spre deosebire
de modelele anterioare, MAB–urile nu se folosesc pentru regresie, clasiﬁcare
sau estimare de probabilitate condiționată. Este sunt utile pentru regăsirea
pe bază de conținut, reconstituire și corectare de date.
Întrucât memoria regăsește datele de instruire pe baza similarității, este
necesară o discuție despre distanțe și spațiul din care fac parte datele.
7.1 Distanța Hamming
Fiex= (x1,…,xn)tșiy= (y1,…,yn)tdoi vectori n-dimensionali din
spațiul Euclidian având restricțiile xi,yi∈{− 1,+1},i= 1,…,n. Cea mai
frecvent utilizată metrică, distanța Euclidiană, dintre cei doi vectori este:
dE(x,y) =/radicaltp/radicalvertex/radicalvertex/radicalbtn/summationdisplay
i=1(xi−yi)2 (7.1)
Având în vedere valorile pe care le pot lua componentele vectorilor xșiy,
avem că:
(xi−yi)2=/braceleftBigg
0 dacăxi=yi
(±2)2= 4dacăxi/negationslash=yi(7.2)
83

deci distanța Euclidiană este dE(x,y) =/radicalbig
4·diferente (x,y)unde prin
diferente (x,y)am notat numărul de componente din xșiycare diferă
pentru poziții de același indice. Pentru doi vectori xșiyca mai sus se deﬁ-
nește funcția de distanță Hamming dHca ﬁind tocmai numărul de diferențe
de pe pozițiile corespunzătoare:
dH(x,y) =n/summationdisplay
i=1I(xi/negationslash=yi) (7.3)
undeI(·)este funcția indicator (3.23) de la pagina 42.
Există deci relația:
dE(x,y) = 2/radicalBig
dH(x,y) (7.4)
Considerăm hipercubul n-dimensional centrat în origine cu latura de
lungime 2:
Hn=/braceleftBig
x= (x1,x2,…,xn)t∈Rn,xi∈{− 1,+1}/bracerightBig
={−1,+1}n(7.5)
Hnse mai numește și cub Hamming.
7.2 Asociatori
Considerăm mulțimea de pperechi de vectori de instruire:
S=/braceleftBig/parenleftBig
x(1),y(1)/parenrightBig
,…,/parenleftBig
x(p),y(p)/parenrightBig/bracerightBig
(7.6)
unde x(i)∈Rn,y(i)∈Rm,1≤i≤p. Există trei tipuri de memorii
asociative:
1.Memorii heteroasociative , implementând o funcție Φ :Rn→Rmcu
proprietatea că Φ/parenleftBig
x(i)/parenrightBig
=y(i),1≤i≤p. În plus, cerem ca dacă
un vector x∈Rneste cel mai apropiat de un exemplar x(i)dinS
(1≤i≤p), atunci Φ(x) = Φ/parenleftBig
x(i)/parenrightBig
=y(i). Apropierea se consideră în
sensul unei distanțe convenabil alese – motiv pentru care s-a discutat
în prima parte a cursului despre distanțe.
2.Memorii interpolative , implementând o funcție Φ :Rn→Rmastfel
încât Φ(x(i)) =y(i),1≤i≤p. În plus, dacă vectorul x∈Rneste
x=x(i)+dunde x(i)e cel mai apropiat de x, atunci ieșirea memoriei
este:
Φ(x) = Φ/parenleftBig
x(i)+d/parenrightBig
=y(i)+e,e∈Rm(7.7)
84

3.Memorie autoasociativă: dacăy(i)=x(i),1≤i≤p, atunci o memorie
autoasociativă trebuie să respecte proprietățile date de memoria hete-
roasociativă: Φ/parenleftBig
x(i)/parenrightBig
=x(i),1≤i≤pși dacă xeste cel mai apropiat
de un exemplar x(i), atunci Φ(x) = Φ/parenleftBig
x(i)/parenrightBig
=x(i).
Pentru cazul în care setul de vectori/braceleftBig
x(i)|1≤i≤p/bracerightBig
este ortonormat1
putem construi simplu un asociator interpolativ: Deﬁnim funcția Φca ﬁind:
Φ(x) =/parenleftBig
y(1)x(1)t+···+y(p)x(p)t/parenrightBig
x (7.8)
Avem că:
Φ(x(i)) =/parenleftBig
y(1)x(1)t+···+y(p)x(p)t/parenrightBig
x(i)=p/summationdisplay
j=1/parenleftBig/parenleftBig
y(j)x(j)t/parenrightBig
x(i)/parenrightBig
=
=p/summationdisplay
j=1/parenleftBig
y(j)/parenleftBig
x(j)tx(i)/parenrightBig/parenrightBig
=p/summationdisplay
j=1/parenleftBig
y(j)·I(i=j)/parenrightBig
=y(i).(7.9)
Dacă un argment x∈Rnare forma x=x(i)+d, atunci:
Φ(x) = Φ/parenleftBig
x(i)+d/parenrightBig
=y(i)+e (7.10)
unde
e=
p/summationdisplay
j=1y(j)x(j)t
·d (7.11)
7.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 sunt
interconectate. Elementele pot sau nu să aibă legături cu ele însele (bucle).
O reprezentare este dată în ﬁgura 7.1. Valorile xsunt din HniarydinHm.
Între noduri există legături cu diferite ponderi.
Spre deosebire de alte tipuri de rețele neurale, ponderile pot ﬁ determi-
nate dacă se cunoaște de dinainte setul de exemplare ce trebuie memorat.
Conexiunile sunt bidirecționale: putem furniza ca intrare o valoare în stratul
xiar ieșirea să ﬁe dată de stratul ysau invers.
Pentru construirea matricii ponderilor se poate folosi o idee similară cu
cea de la memoria interpolativă:
W=y(1)x(1)t+···+y(p)x(p)t. (7.12)
1Vectorii/braceleftbig
x(1),…,x(p)|1≤i≤p/bracerightbig
sunt ortonormați dacă x(i)t·x(j)=I(i=j),1≤
i,j≤p. Dintr-un set de vectori liniar independenți putem obține întotdeauna un sistem
de vectori ortonormați prin procedeul Gram-Schmidt de ortonormare. Pentru a reduce
din efectul erorilor de rotunjire, se poate folosi procedeul Gram-Schmidt modiﬁcat.
85

Figura 7.1: Arhitectura unei memorii asociative bidirecționale
Matricea W= (wij),1≤i≤m,1≤j≤ndă ponderile legăturilor de la
stratul xla stratul y. Matricea ponderilor în sens invers este Wt. Memoria
poate deveni autoasociativă prin stabilirea lui Wca ﬁind:
W=x(1)x(1)t+···+x(p)x(p)t(7.13)
Odată matricea de ponderi contruită, se poate utiliza MAB pentru regă-
sirea datelor stocate prin furnizarea unor date cheie, suﬁcient de apropiate
de cele din setul de instruire. Vom vedea că această intrare poate ﬁ 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 (x,y)celor două straturi de ne-
uroni;
2. se propagă informația de la stratul xla stratul yși se modiﬁcă valorile
din stratul y;
3. se propagă informația de la ylaxși se modiﬁcă valorile din stratul x;
4. se repetă pașii 2 și 3 până când nu mai apare nicio modiﬁcare în
nodurile celor două straturi.
86

Se poate ca datele să înceapă să se propage de la stratul yla stratul x.
Plimbarea informației în ambele sensuri dă natura bidirecțională a rețelei.
Când rețeaua se stabilizează, de regulă se regăsește în stratul xvaloarea x(i)
care este cea mai apropiată de xrelativ la distanța Hamming și valoarea
y(i)asociată cu x(i)— sau complementele acestora, a se vedea exemplele
următoare.
Procesarea care se face în momentul transmiterii informației de la stratul
xla stratul yeste dată de ecuația:
nety=W·x (7.14)
sau pe componente:
nety
i=n/summationdisplay
j=1wijxj,1≤i≤m (7.15)
unde netyeste vectorul de stare pentru stratul y. Pentru transmiterea în
sens invers are loc un proces asemănător:
netx=Wty (7.16)
sau pe componente:
netx
i=m/summationdisplay
j=1wji·yj,1≤i≤n (7.17)
Valoarea de ieșire a unui neuron depinde de intrări și de valoarea lui
curentă. Mai clar, valoarea de la momentul t+ 1pentru nodul yieste dată
de:
yi(t+ 1) =

+1,dacănety
i>0
yi(t),dacănety
i= 0
−1,dacănety
i<0(7.18)
Valorile de ieșire pentru stratul xse calculează similar.
Exemplu numeric: plecăm de la perechea de vectori
x(1)= (1,−1,−1,1,−1,1,1,−1,−1,1)t(7.19)
x(2)= (1,1,1,−1,−1,−1,1,1,−1,−1)t(7.20)
cu ieșirile corespunzătoare asociate
y(1)= (1,−1,−1,−1,−1,1)t(7.21)
y(2)= (1,1,1,1,−1,−1)t(7.22)
Matricea ponderilor este:
W=
2 0 0 0 −2 0 2 0 −2 0
0 2 2−2 0−2 0 2 0 −2
0 2 2−2 0−2 0 2 0 −2
0 2 2−2 0−2 0 2 0 −2
−2 0 0 0 2 0 −2 0 2 0
0−2−2 2 0 2 0 −2 0 2
(7.23)
87

Vom considera ca vector de intrare x= (−1,−1,−1,1,−1,1,1,−1,−1,1)t
cuvectorul yasociat (1,1,1,1,−1,−1)t. Remarcămcăvectorii xșiydaținu
sunt printre vectorii învățați. Vectorul de ieșire ypoate ﬁ dat ca un vector
binar bipolar cu componente aleatoare. Propagarea valorilor dinspre stratul
xcătre yduce la determinarea valorii nety= (4,−12,−12,−12,−4,12)t.
Noul vector din stratul yestey= (1,−1,−1,−1,−1,1)t. Propagând înapoi
către stratul xobținem x= (1,−1,−1,1,−1,1,1,−1,−1,1)t. Propagări
succesive într–un sens sau în celălalt nu duc la modiﬁcări ale valorilor din
straturile xsauy. Perechea de vectori la care se stabilizează rețeaua este
chiar perechea/parenleftBig
x(1),y(1)/parenrightBig
. S-a regăsit astfel o pereche de exemplare din
cele cu care s–a instruit rețeaua, chiar dacă s–a plecat de la valori care nu
se regăsesc printre cele învățate.
Să considerăm situația în care se pleacă de la valorile inițiale:
x= (−1,1,1,−1,1,1,1,−1,1,−1)t,y= (−1,1,−1,1,−1,−1)t
Propagând de la stratul xlay, 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țeaua
se stabilizează. Se observă că valorile stabile (x,y)sunt chiar (x(1)c,y(1)c)
unde aceste vectorul format cu valorile complementate ce compun pe a:
ac=−a. Aceasta este o proprietate a MAB: dacă memoria stochează
perechea (x,y), atunci stochează și perechea (xc,yc)și stabilizarea rețelei
se poate face pe o astfel de pereche de complemente.
7.4 Funcția de energie a MAB
În timpul propagării valorilor dinspre stratul xspreysau invers, valorile
din nodurile rețelei se modiﬁcă, ceea ce ne permite să vedem evoluția stării
acestora ca o funcție de timp. Vom asocia memoriei o funcție de energie a
căreivaloareestedependentădevalorile xșiydinnoduri; vremsăarătămcă
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/summationdisplay
i=1n/summationdisplay
j=1yiwijxj
Avem următoarea teoremă privitoare la comportamentul MAB pentru
funcția de energie:
Teorema 2. 1. Orice modiﬁcare a stării stratului xsauyîn timpul pro-
cesării din MAB duce la scăderea lui E;
2.Eeste mărginită inferior de Emin=−/summationtext
i,j|wij|;
88

3. Dacă valoarea lui Ese schimbă, atunci modiﬁcarea nu este arbitrar de
mică.
Demonstrație. Pentru cazul în care se face propagare dinspre stratul xcătre
stratuly, presupunem că se face o modiﬁcare pentru vectorul ype o singură
poziție, ﬁe ea l,1≤l≤m. Energia asociată intrării curente este:
E=−n/summationdisplay
j=1ylwljxj−m/summationdisplay
i=1,i/negationslash=ln/summationdisplay
j=1yiwijxj (7.24)
Dacă se face modiﬁcarea valorii ylînynou
l, noua valoare a energiei va ﬁ:
Enou=−n/summationdisplay
j=1ynou
lwljxj−m/summationdisplay
i=1,i/negationslash=ln/summationdisplay
j=1yiwijxj (7.25)
și deci variația energiei este:
∆E=Enou−E= (yl−ynou
l)n/summationdisplay
j=1wljxj= (yl−ynou
l)nety
l(7.26)
Avem posibilitățile:
1. dacăyl= +1, atunciynou
l=−1. Avemyl−ynou
l= 2>0; pe de
altă parte, dacă ynou
l=−1, asta se datorează lui nety
l<0(a se vedea
ecuația 7.18). Valoarea lui ∆Eeste produsul a doi termeni întregi
nenuli și de semn contrar și deci este o valoare întreagă strict mai
mică decât zero.
2. dacăyl=−1, atunciynou
l= +1și de aiciyl−ynou
l=−2<0. Pe
de altă parte, trecerea de la yl=−1laynou
l= +1se datorează lui
nety
l>0(ecuația 7.18) și din nou ∆Eeste produsul a două valori
întregi nenule și de semn contrar, ca atare de valoare întreagă strict
mai mică decât zero.
Situația în care mai mult de un termen din ynoueste modiﬁcat față de y
se tratează similar, cu observația că scăderea lui ∆Eeste și mai accentuată.
Similar se arată că modiﬁcarea stării unui neuron din stratul de intrare
de asemenea scade valoarea funcției de energie.
Pentru cea de a doua parte a teoremei avem:
−E(x,y) =m/summationdisplay
i=1n/summationdisplay
j=1yiwijxja≤|a|
≤/vextendsingle/vextendsingle/vextendsingle/vextendsingle/vextendsingle/vextendsinglem/summationdisplay
i=1n/summationdisplay
j=1yiwijxj/vextendsingle/vextendsingle/vextendsingle/vextendsingle/vextendsingle/vextendsingle|a+b|≤|a|+|b|
≤
|a+b|≤|a|+|b|
≤m/summationdisplay
i=1n/summationdisplay
j=1|yi|·|wij|·|xj||xj|=|yi|=1=m/summationdisplay
i=1n/summationdisplay
j=1|wij|.(7.27)
89

de undeE(x,y)≥−m/summationtext
i=1n/summationtext
j=1|wij|.
Parteaatreiaateoremeirezultădinceleobținuteîndemonstrațiaprimei
părți a teoremei: dacă a apare modiﬁcare în stările neuronilor, ∆Eeste un
număr întreg strict mai mic decât zero.
Punctele 2 și 3 ale teoremei arată că MAB se stabilizează într-un numıar
ﬁnit de pași. Primele două puncte arată că funcția Eeste de tip Lyapunov,
o clasă de funcții des folosite pentru studiul sistemelor dinamice.
Demonstrație practică: http://facstaﬀ.cbu.edu/ ∼pong/ai/bam/bamapplet.html .
7.5 Comentarii
MAB este un model în care ordinea de prezentare a vectorilor în setul
de instruireSdin ecuația (7.6) nu e relevantă: suma pe baza căreia se
creează matricea de ponderi W– a se vedea ecuația (7.12) – este o operație
comutativă. Altfel zis, MAB este un model order independent .
Totodată, MABesteunmodeldeînvățareîncarecreștereasaureducerea
setului de instruire S(uitarea) nu necesită reluarea instruirii pe întregul set
de instruire:
•la adăugarea unei noi perechi de vectori/parenleftBig
x(p+1),y(p+1)/parenrightBig
setului de
instruire, la matricea Wformată cu ptermeni se mai adună matricea
y(p+1)·x(p+1)t;
•dacă se dorește “uitarea” perechii/parenleftBig
x(i),y(i)/parenrightBig
, atunci din matricea W
se scade termenul y(i)·x(i)t.
Capacitatea de memorare a unei memorii asociative bidirecționale este
insuﬁcient studiată. După unii autori ea este min(m,n), alții estimează
însă că un prag superior pentru numărul de perechi de vectori care pot ﬁ
memorate ar ﬁ/radicalbig
min(m,n).
90

Capitolul 8
Rețele neurale cu funcții de
activare radială
Rețeleleneuralecufuncțiideactivareradialăsefolosescpentruprobleme
de clasiﬁcare, estimare de probabilitate condiționată și regresie. Instruirea
este nesupervizată (clustering) pentru determinarea centrilor neuronilor din
stratul ascuns și supervizată pentru învățarea ponderilor dintre stratul as-
cuns și cel de ieșire.
8.1 Teorema lui Cover
Pentru cazul vectorilor ce nu pot ﬁ separați liniar, perceptronul multis-
trat poate determina o funcție de separare, datorită caracterului de apro-
ximator universal. Există și o altă variantă de rezolva problema discernerii
între clase ce nu se pot separa liniar, folosind însă un separator liniar , ce
lucrează în doi pași:
1. mulțimea de instruire dată în spațiul originar este transformată într–
un alt spațiu, în care, în anumite condiții, liniar separabilitatea poate
apărea cu probabilitate mare; fundamentul matematic este dat de te-
orema lui Cover (vedeți mai jos);
2. prin utilizarea unui model de separare liniară (perceptron, SVM liniar,
regresie logistică) se separă clasele în cel de-al doilea spațiu.
Rezultatul se poate materializa printr–o rețea cu funcții de activare ra-
dială, formată din 3 straturi:
•stratuldeintrarealcătuitdinnodurideintrarecareconecteazărețeaua
la mediu;
•stratul de neuroni ascunși ce aplică transformări neliniare pe datele
din spațiul de intrare. Neuronii din acest strat sunt antrenați prin
instruire nesupervizată;
91

•stratul de ieșire produce o transformare liniară, iar ponderile dintre
stratul ascuns și stratul de ieșire sunt obținute prin instruire supervi-
zată. Acesta furnizează valoarea de ieșire pentru vectorul de intrare
curent.
Următoarea teoremă arată motivul pentru care se face o transformare a
datelor originare în alte date dintr-un spațiu cu mai multe dimensiuni decât
cel originar:
Teorema 3 (Cover, 1965) .Printr–o transformare neliniară a unui set de
date de intrare dintr-un spațiu Aîntr-un spațiu Bcu dimensiune mai mare,
crește probabilitatea de a obține clase liniar separabile, dacă Anu este dens
populat.
Rezultatul este util, deoarece pentru cazuri liniar separabile, un percep-
tron discret poate să obțină un hiperplan de separare în timp ﬁnit; se pot
folosi si alte modele de clasiﬁcatori liniari – regresie logistică, Support Vec-
tor Machines etc. Pentru a se obține o asemenea transformare, se pleacă de
la spațiulAndimensional în care se găsesc vectorii x1, …, xPși se ajunge
la un spațiu mdimensional ( m≥n) prin funcția:
x→(x) = (ϕ1(x),…,ϕm(x))t∈Rm(8.1)
undeϕi:Rn→R,i=1,msunt funcții neliniare; în rețeaua neurală funcția
ϕie calculată de neuronul idin 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)taparțin unei clase,
iar(0,1)tși(1,0)taparțin celeilalte clase. Se poate demonstra algebric că nu
existăodreaptăînplancaresăsepareceledouăclasedepuncte. Considerăm
funcțiileϕ1,ϕ2:R2→R
ϕ1(x) = exp (−/bardblx−t1/bardbl),t1= (1,1)t
ϕ2(x) = exp (−/bardblx−t2/bardbl),t2= (0,0)t
undex∈R2iar/bardbl·/bardbleste norma Euclidiană L2înR2. Pornind de la un vector
de intrare x∈R2se ajunge la un vector tot din R2dat de (ϕ1(x),ϕ2(x)).
Valorile rezultate pentru funcțiile ϕ1,2calculate în cele 4 puncte ale proble-
mei XOR sunt date în tabelul 8.1. Figura 8.1 dă reprezentarea punctelor
tranformate prin aplicarea celor două funcții. Se observă că problema devine
una liniar separabilă, folosind modiﬁcări neliniare ale datelor inițiale; mai
mult, nu a fost nevoie în acest caz să se mărească dimensiunea spațiului de
ieșire.
92

Vector de intrare ϕ1(xi)ϕ2(xi)
x1= (1,1)t10.1353
x2= (0,1)t0.3678 0.3678
x3= (0,0)t0.1353 1
x4= (1,0)t0.3678 0.3678
Tabela 8.1: Valorile funcțiilor ϕpentru punctele problemei XOR
/0/0/0/1/1/1
/0/0/0/1/1/1
/0/0/0/0/0/0
/1/1/1/1/1/1Regiune de decizie
(ϕ1(x4), ϕ2(x4))(ϕ1(x2), ϕ2(x2))(ϕ1(x3), ϕ2(x3))
(ϕ1(x1), ϕ2(x1))
8.2 Funcții cu activare radială
Teorema lui Cover aﬁrmă că pentru o problemă ce nu e liniar separabilă,
prin transformare adecvată cresc șansele de a se transforma într–una care e
liniar separabilă. Să considerăm o rețea neurală de tip feedforward cu un
strat de intrare cu nnoduri, un singur strat ascuns și un strat de ieșire cu un
singur nod1. Această rețea produce o funcție de la un spațiu n–dimensional
la unul unidimensional:
s:Rn→R (8.2)
Funcțiaspoate ﬁ văzută ca o hipersuprafață Γ⊂Rn+1; hipersuprafața Γ
este necunoscută și se determină pe baza setului de instruire.
Se lucrează în două etape: una de instruire și alta de generalizare. În
1În cele ce urmează în acest capitol, ieșirea unică este pentru simpliﬁcarea prezentării.
Pentru cazul în care ieșirea este din spațiul Rmsau dacă avem o problemă de clasiﬁcare
cumclase, stratul de ieșire va avea mneuroni.
93

etapa de instruire se folosește o procedură oarecare prin care se determină
hipersuprafața Γ, plecând de la setul de date de antrenare, adică se obține
funcțias. În etapa de generalizare se folosește un procedeu de interpolare
pentru a determina valori de ieșire corespunzătoare unor vectori din spațiul
de intrare Rn.
Problema de interpolare este:
Dându–se un set de instruire de pperechi
S=/braceleftBig/parenleftBig
x(i),y(i)/parenrightBig
|x(i)∈Rn,y(i)∈R,i=1,p/bracerightBig
se cere să se determine o funcție F:Rn→Rcare satisface proprietatea de
interpolare:
F/parenleftBig
x(i)/parenrightBig
=y(i), i=1,p (8.3)
Tehnica funcțiilor cu activare radială (Radial Basis Functions, RBF)
consideră că funcția F:Rn→Rare forma:
F(x) =p/summationdisplay
i=1wiϕi/parenleftBig/vextenddouble/vextenddouble/vextenddoublex−x(i)/vextenddouble/vextenddouble/vextenddouble/parenrightBig
(8.4)
undeϕisunt funcții neliniare reale, cunoscute ca funcții cu activare radială.
Punctele x(i)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
=
y(1)
y(2)
…
y(p)
(8.5)
unde
ϕij=ϕi/parenleftBig/vextenddouble/vextenddouble/vextenddoublex(j)−x(i)/vextenddouble/vextenddouble/vextenddouble/parenrightBig
, i,j =1,p (8.6)
Notămcu y=/parenleftBig
y(1),y(2),…,y(p)/parenrightBigt,w= (w1,w2,…,wp)t,={ϕij}i,j=1,p.
Numimmatricea matriceadeinterpolare. Sepoaterescrie(8.5)subforma:
·w=y (8.7)
Dacă matricea este nesingulară, atunci ponderile sunt w=−1y. Pentru
discuția asupra caracterului nesingular al matricei , considerăm teorema
lui Michelli:
Teorema 4 (Michelli, 1986) .Fie{xi}i=1,pun set de puncte distincte din
Rn. Atunci matricea de interpolare este inversabilă dacă funcțiile ϕiau
una din formele:
94

1. funcție multipătratică:
ϕi(ri) =/radicalBig
r2
i+c2, c> 0 (8.8)
2. funcție inversă de multipătratică:
ϕi(ri) =1/radicalBig
r2
i+c2, c> 0 (8.9)
3. funcție Gaussiană:
ϕi(ri) = exp/parenleftBigg
−r2
i
2σ2/parenrightBigg
, σ> 0 (8.10)
unde în toate cele trei cazuri rieste distanța Euclidiană dintre vectorii xși
x(i)— echivalent: norma diferenței dintre xșix(i),/vextenddouble/vextenddouble/vextenddoublex−x(i)/vextenddouble/vextenddouble/vextenddouble.
8.3 Rețele cu funcții cu activare radială
Orețeacufuncțiicuactivareradialăesteilustratăînﬁgura8.1; eaconstă
din trei straturi:
1.stratul de intrare , care constă din nnoduri, unde neste dimensiunea
spațiului de intrare.
2.stratul ascuns , care e format din același număr de neuroni ca numărul
de date din setul de antrenare, p; ﬁecare neuron i, i=1,pare funcție
cu activare radială ϕi/parenleftBig/vextenddouble/vextenddouble/vextenddoublex−x(i)/vextenddouble/vextenddouble/vextenddouble/parenrightBig
;
3.stratul de ieșire , care în cazul exempliﬁcat este format dintr-un singur
neuron. Stratul de ieșire poate avea în general mneuroni, pentru
problemele de clasiﬁcare sau estimare de probabilitate condiționată
pentrumclase, sau pentru probleme de regresie din RnînRm.
Pentru funcțiile ϕivom considera funcțiile Gaussiene:
ϕi/parenleftBig/vextenddouble/vextenddouble/vextenddoublex−x(i)/vextenddouble/vextenddouble/vextenddouble/parenrightBig
= exp/parenleftBigg
−1
2σ2
i/vextenddouble/vextenddouble/vextenddoublex−x(i)/vextenddouble/vextenddouble/vextenddouble2/parenrightBigg
, i=1,p (8.11)
undeσieste lățimea unei funcții Gaussiene centrate în x(i). De regulă tu-
turor Gaussienelor li se asigneaza aceeași lățime σ; diferența dintre funcții
este dată în acest caz de centrele x(i).
Din punct de vedere practic se evită folosirea tuturor datelor din setul de
instruire pentru crearea de funcții de activare de tip radial. Un motiv ar ﬁ
că setul/braceleftBig/parenleftBig
x(i),y(i)/parenrightBig
|i=1,p/bracerightBig
poate prezenta zgomot, de exemplu datorită
95

…x1
( · )
c e n t r u l x(1)
φ2(·)
centrul x x2w1
w2
wpy =F (x)
xnφp(·)
centrul xcentrul x
(2)
(p)(·)
centrul x1(1)φFigura 8.1: Structura unei rețele RBF, plecând de la funcția de interpolare
din ecuația 8.4.
erorilor de măsurare. Folosirea unui procedeu de interpolare plecând de la
un set de date cu zgomot duce la rezultate proaste. În plus, numărul de
noduri rezultat în rețeaua din ﬁgura 8.1 s-ar putea să ﬁe prohibitiv. Ca
atare, în practică numărul de noduri din stratul ascuns este mult redus.
FuncțiaFse transformă într-o funcție de aproximare de forma:
F(x) =k/summationdisplay
i=1wiϕi(/bardblx−ˆi/bardbl) (8.12)
unde dimensiunea vectorului de intrare xeste aceeași ca și cea de până
acum,k<piar punctele ˆinu sunt neapărat din setul de instruire – ele pot
proveni dintr–un proces de grupare automată (clustering). Interpretarea ca
rețea neurală este dată în ﬁgura 8.2.
Pentru determinarea celor kcentri ˆi,1≤i≤kale centrilor din stratul
ascuns se poate utiliza o metodă oarecare de grupare automată pe baza
similarităților (clustering), dar care să producă noțiunea de centroid2. Vom
2Excludem deci algoritmi de clustering precum DBSCAN sau OPTICS.
96

…x1
( · )
c e n t r u l x(1)
x2w1
w2
wky =F (x)
xncentrul xcentrul
(·)1
1
( · )
c e n t r u l x(1)centrul xcentrul
(·)2
2
( · )
c e n t r u l x(1)centrul xcentrul
(·)k
k^
^^Figura 8.2: Structura unei rețele RBF, folosind mai puține noduri decât în
ﬁgura 8.1. Centrii ˆi,i=1,kse obțin printr-un procedeu de clustering.
prezenta în cele ce urmează metoda K-means clustering.
8.4 Clustering folosind algoritmul K-means
Clustering-ul este o formă de învățare nesupervizată în care un set de
vectori este partiționat în grupuri. Se urmărește minimizarea unei funcții de
cost deﬁnită convenabil, care cuantiﬁcă disimilaritatea totală a vectorilor.
Clusterele ar trebui obținute de așa manieră încât vectorii similari să ﬁe
grupați în același cluster, iar doi vectori nesimilari să ﬁe dispuși în clustere
diferite.
Considerăm un set de ppuncte,/braceleftBig
x(i)/bracerightBig
i=1,pce urmează să ﬁe partiționat
înkclustere3,k <p. FieC(i)indicele de cluster de care aparține vectorul
x(i),i=1,p. Evident, 1≤C(i)≤k. Considerăm d/parenleftBig
x(i),x(j)/parenrightBig
o măsură a
deosebirii – a ne-similarității – dintre perechile de vectori x(i)șix(j). Pentru
3Cel mai frecvent, valoarea lui keste furnizată de utilizator.
97

clustering se cere minimizarea funcției:
J(C) =1
2k/summationdisplay
l=1/summationdisplay
i:C(i)=l/summationdisplay
j:C(j)=ld/parenleftBig
x(i),x(j)/parenrightBig
(8.13)
undeCeste partiția dată de cele kclustere:
C=/braceleftBig
{i|1≤i≤p,C(i) =l}|l=1,k/bracerightBig
În algoritmul K-means drept măsură de ne–similaritate se folosește pă-
tratul distanței Euclidiene:
d/parenleftBig
x(i),x(j)/parenrightBig
=/vextenddouble/vextenddouble/vextenddoublex(i)−x(j)/vextenddouble/vextenddouble/vextenddouble2(8.14)
În urma procesului de clustering vor rezulta kcentroizi – centri de clustere
– notați ˆl∈Rn,l=1,k.
Modiﬁcăm forma funcției de eroare Jastfel încât să se ia în considerare
distanțele dintre vectorii x(i)și centroizii ˆlai clusterelor de care aparțin:
J(C) =1
2k/summationdisplay
l=1/summationdisplay
i:C(i)=l/vextenddouble/vextenddouble/vextenddoublex(i)−ˆl/vextenddouble/vextenddouble/vextenddouble2(8.15)
Presupunând funcția Ccunoscută, cum anume se poziționează centroizii
astfel încât să se minimizeze J(C)? Algoritmul K-means determină niște
valori pentru ˆlprintr-un proces iterativ, astfel încât J(C)să scadă. Este
un algoritm euristic, nu garantează faptul că se ajunge la minimul global al
luiJ(C).
Algoritmul alege aleator kcentroizi inițiali ˆ(1)
l,l=1,k, inițializându–i
cu valori ﬁe din setul de instruire, sau setate la întâmplare cu valori din
spațiul de intrare, sau conform algoritmului K–means++, a se vedea mai
jos. Avem apoi o succesiune de iterații cu pașii:
•Pasul de asignare: Calculează pentru orice l,l= 1…k:
S(t)
l=/braceleftBig
x(i):/vextenddouble/vextenddouble/vextenddoublex(i)−ˆ(t)
l/vextenddouble/vextenddouble/vextenddouble≤/vextenddouble/vextenddouble/vextenddoublex(i)−ˆ(t)
j/vextenddouble/vextenddouble/vextenddouble,j=1,k,j/negationslash=l,i=1,p/bracerightBig
adică pentru ﬁecare punct x(i)se determină care este cel mai apropiat
centroid de care aparține; S(t)
leste mulțimea vectorilor din setul de
instruire ce sunt cel mai apropiate de centroidul ˆ(t)
l, la iterația t.
•Modiﬁcarea centroizilor:
ˆ(t+1)
l=1/vextendsingle/vextendsingle/vextendsingleS(t)
l/vextendsingle/vextendsingle/vextendsingle·/summationdisplay
x(i)∈S(t)
lx(i), l=1,k
unde/vextendsingle/vextendsingle/vextendsingleS(t)
l/vextendsingle/vextendsingle/vextendsingleeste numărul de elemente ale mulțimii S(t)
l.
98

Algoritmul K-means se oprește atunci când pasul de asignare nu mai
modiﬁcă mulțimile S(t)
l.
Nuexistăniciodemonstrațiecăalgoritmulconvergecătreminimulglobal
al funcțieiJ; ﬁind însă rapid în practică – adică necesitând puțini pași până
laoprire–sepoaterepornicualtevalorialecentroizilorinițiali ˆ(1)
l,l=1,k.
Situația (centroizii) pentru care J(C)are valoarea cea mai mică în aceste
încercări este reținută.
Se poate consideră că inițializarea centroizilor inițiali ˆ(1)
l,i=1,knu
ar trebui lăsată la voia întâmplării și că se poate îmbunătăți considerabil
performanța algoritmului printr–o alegere îngrijită a lor. Un caz nefavorabil
este dat în ﬁgura 8.4. Să considerăm un dreptunghi cu laturile de lungime
L/greatermuchl, având în cele patru vârfuri câte un punct x(i)∈R2,i=1,4. Dacă
considerăm k= 2și centroizii sunt aleși inițial la jumătatea laturilor de
lungime mai mare, atunci algoritmul se oprește după o iterație cu J(C) =
1
2·4/parenleftBig
L
2/parenrightBig2=L2
2(punctele x(1)șix(3)aparțin clusterului de centroid ˆ1, iar
celelalte două celui de al doilea cluster). Dacă alegerea punctelor se face
ca în ﬁgura 8.4, atunci se obține valoarea J(C) =l2
2– și se poate arăta că
aceasta este și valoarea minimă a lui J. Având în vedere că Lpoate ﬁ luat
oricât de mare 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.
/0/0/0/0
/1/1/1/1
/0/0/0/0/0/0
/1/1/1/1/1/1
/0/0/0/0
/1/1/1/1
/0/0/0/0
/1/1/1/1x2x1x3
x4
ˆµ2ˆµ1
Figura 8.3: Caz nefavorabil pentru K-means la alegerea centroizilor inițiali.
/0/0/0/0/0/0
/1/1/1/1/1/1
/0/0/0/0
/1/1/1/1/0/0/0/0/0/0
/1/1/1/1/1/1
/0/0/0/0
/1/1/1/1
x2x1x3
x4ˆµ2ˆµ1
Figura 8.4: Alegerea optimă a centroizilor inițiali.
Ca atare, s–a dezvoltat algoritmul K-means++ care are ca scop deter-
99

minarea unor centroizi inițiali aleși mai potrivit. Alegerea celor Kcentroizi
se face după următorii pași [19]:
1. Alege primul centroid aleator din setul de antrenare;
2. Pentruﬁecarepunctcenuafostîncăalesdreptcentroid x(i)calculează
D/parenleftBig
x(i)/parenrightBig
(1≤i≤p), distanța de la el pâ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 toți cei kcentroizi;
Se aplică apoi algoritmul K-means pentru centroizii astfel determinați.
Costul suplimentar indus de determinarea celor kcentroizi ca mai sus
este neglijabil față de efectele beneﬁce asupra rezultatului ﬁnal. Motivațiile
teoretice pentru K-means++ se găsesc în [19].
8.5 Determinarea ponderilor pentru RBF
Determinarea ponderilor legăturilor dintre stratul ascuns și cel de ieșire
este următorul pas. Problema este una de determinare a ponderilor pentru
o problemă de regresie liniară și se tratează cu tehnicile din secțiunile 2.3 și
2.4.
Pentru cazul în care problema este una de regresie în care vectorii de
ieșire sunt din Rm, ﬁecare neuron de ieșire își poate ajusta setul de ponderi
independent de ponderile celorlalte ieșiri; se aplică una din cele două metode
de mai sus.
8.6 Algoritmul de instruire a rețelei RBF
Sintetizăm pe baza expunerii de până acum procedura de instruire a
unei rețele RBF. Stratul de intrare este ﬁx, având numărul de noduri dat
de dimensiunea intrării. Stratul ascuns se obține rulând algoritm de clus-
tering (e.g.K-means precedat de K-means++) peste setul de antrenare
și rezultând kcentroizi ˆj,j=1,k. Acești centri de clustere devin centrii
unor funcții Gaussiene asignate nodurilor ascunse. Pentru ﬁecare astfel de
Gaussiană este asignată o aceeași lățime σ, calculată ca:
σ=dmax√
2·k(8.16)
undedmaxeste distanța maximă dintre perechile de centroizi. În stratul
de ieșire sunt tot atâtea noduri cât este dimensiunea spațiului de ieșire.
100

Ponderile legăturilor dintre stratul ascuns și stratul de ieșire se calculează
ca pentru o problemă de regresie liniară (metoda de căutare după gradient
din secțiunea 2.3 sau prin metoda pseudoinversei din secțiunea 2.4).
101

Capitolul 9
Fuzzy ARTMAP
Rețelele Fuzzy ARTMAP folosesc instruirea supervizată pentru a crea
clasiﬁcatoare, estimatoare de probabilitate condiționată și modele de regre-
sie.
Rețelele Fuzzy ARTMAP (FAM) au capacitatea de învățare incremen-
tală, posedă o mare parte din proprietățile dorite pentru sisteme instruibile
și rezolvă dilema stabilitate–plasticitate.
9.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 utilizate pentru a antrena sistemul până la mo-
mentul curent;
3. păstrează cunoștințele deprinse anterior;
4. se pot acomoda cu noi categorii care pot ﬁ introduse de noi date de
instruire.
9.2 Proprietăți dezirabile ale sistemelor instrui-
bile
Pentru un sistem instruibil următoarele proprietăți sunt văzute ca ﬁind
esențiale:
1. învățare rapidă;
2. învățare din noi date fără a ﬁ nevoie să se reantreneze cu datele par-
curse anterior – regăsită în învățarea incrementală;
102

3. rezolvarea de probleme neseparabile liniar – o varietate liniară nu este
întotdeauna o suprafață de separare bună;
4. în cazul unui clasiﬁcator: abilitate de a da nu doar clasa de aparte-
nență a unui vector de intrare, ci și plauzibilitatea acestei apartenențe;
sunt favorizați aici estimatorii de probabilitate condiționată de forma
P(clasa|intrare ); de exemplu, P(email =spam|continutemail );
5. pentru clasiﬁcatori: oferire de explicații asupra modului în care datele
sunt clasiﬁcate, de ce sunt clasiﬁcate într–un anume mod; prin această
trăsăturăseevitătratareaclasiﬁcatoruluicaocutieneagrăcenupoate
să explice modul de producere a deciziilor;
6. posibilitate de reglare automată a hiperparametrilor modelului; de
exemplu, pentru perceptronul multistrat hiperparametrii de interes
sunt rata de învățare, numărul de straturi ascunse, numărul neuroni-
lor din ﬁecare strat ascuns etc.;
7. aproximarea de funcții fără a cunoaște distribuția inițială a datelor;
rareori datele se supun unei distribuții clasice;
8. pentru clase care prezintă suprapuneri, să se creeze regiuni în spațiul
de intrare care să realizeze cea mai mică suprapunere; problema aso-
cierilor de tip un vector de intrare–la–mai multe clase trebuie tratată
explicit.
9.3 Dilema stabilitate–plasticitate
Un sistem instruibil ar trebui să aibă două proprietăți:
1.plasticitate – înseamnă adaptarea la mediul din care provin vectorii de
instruire. Altfel zis, plasticitatea este capacitatea de învățare.
2.stabilitate – se referă la păstrarea cunoștințelor învățate anterior.
Atunci când se prezintă noi intrări unei rețele neurale, cele vechi pot ﬁ
uitate. Ponderile rețelei trebuie să ﬁe suﬁcient de ﬂexibile pentru a învăța
noi cunoștințe (trăsătura de plasticitate), dar nu atât de mult încât să uite
ceea ce s–a învățat anterior (trăsătura de stabilitate). Acest conﬂict dintre
stabilitate și plasticitate se numește dilema stabilitate–plasticitate . Cele mai
multe dintre rețelele neurale existente sunt ﬁe stabile dar incapabile de a
învăța rapid noi vectori, ﬁe plastice dar instabile; de aceea, dilema mențio-
nată este una din problemele de interes în domeniul modelelor instruibile.
S-a formulat întrebarea: cum poate un sistem de învățare să ﬁe atât stabil
cât și plastic?
Dilema a fost abordată de Carpenter și Grossberg în [15]. Teoria rezo-
nanței adaptive (Adaptive Resonance Theory, ART) dezvoltată de cei doi
103

autori este unul din răspunsurile concrete date dilemei. De asemenea, siste-
mul prezintă abilitate de învățare incrementală și mare parte din proprietă-
țile dezirabile ale sistemelor instruibile.
9.4 Fuzzy ARTMAP
Familia Fuzzy ARTMAP de rețele neurale (FAM) este cunoscută ca una
din puținele care posedă capacitate de învățare incrementală, rezolvă dilema
stabilitate-plasticitate și are multe din proprietățile dorite pentru un sistem
instruibil.
Carpenter si Grossberg au fost interesați de obținerea de sisteme care se
pot organiza singure. Paradigma ART poate ﬁ descrisă ca un tip de gru-
pare incrementală a datelor, având posibilitatea de a învăța fără antrenare
supervizată și este de asemenea în acord cu modelele cognitive și de compor-
tament. Folosește învățare nesupervizată; rețeaua este capabilă să găsească
automat categoria asociată intrării curente sau să creeze una nouă atunci
când este nevoie: numărul de neuroni din rețea nu este ﬁxat aprioric.
Rețelele neurale Fuzzy ART sunt capabile să producă rapid o învățare
stabilă a unor categorii de semnale ca răspuns la secvențe arbitrare de in-
trări binare sau continue. Fuzzy ART încorporează operatori din teoria
mulțimilor fuzzy.
Sistemele de tip Fuzzy ARTMAP învață în mod autonom arbitrar de
mulți vectori, formând categorii de recunoaștere în funcție de succesul de
predicție. Acest sistem de învățare supervizată este construit dintr-o pere-
che de module ART capabile de auto-organizare și obținere de categorii de
recunoaștere stabile.
Succesul rețelelor bazate pe teoria rezonanței adaptive este dat de avan-
tajele pe care le au față de alte rețele multistrat dezvoltate anterior:
•permit crearea dinamică a nodurilor (neuronilor) fără distrugerea celor
existente;
•necesită mai puține cicluri de antrenare cerute, se pot folosi chiar cu
învățare incrementală, adică să treacă o singură dată peste setul de
instruire;
•are convergență garantată datorită utilizării unor ponderi mărginite și
monotone.
Fuzzy ARTMAP este utilizabil pentru probleme de clasiﬁcare, estimare
de probabilitate și regresie. S–a demonstrat că FAM este aproximator uni-
versal. Deoarece atât clasiﬁcarea cât și estimarea de probabilitate sunt ca-
zuri particulare ale regresiei, rezultă că FAM poate ﬁ utilizat în orice pro-
blemă ce presupune stabilirea de legături dintre două submulțimi din Rnși
respectiv din Rm.
104

Înﬁnal,maiprecizămcăFAMmaiareocalitate: reprezentareavectorilor
învățați prin categorii facilitează extragerea de reguli sub forma de reguli,
aspect esențial în domeniul extragerii de cunoștințe din date.
9.4.1 Arhitectura rețelei FAM
O rețea FAM constă într–o pereche de module ART notate ARTași
ARTb, conectate printr-un modul numit Mapﬁeld, notat Fab.ARTașiARTb
sunt folosite pentru codiﬁcarea vectorilor de intrare și respectiv de ieșire, iar
Mapﬁeld permite asocierea între intrări și ieșiri. Figura 9.1 conține compo-
nentele unei arhitecturi FAM.
Figura 9.1: Arhitectura Fuzzy ARTMAP
Modulul Fuzzy ARTaconține stratul de intrare Fa
1și stratul competitiv
Fa
2. Se adaugă de asemenea un strat de preprocesare Fa
0înaintea lui Fa
1.
Straturi echivalente apar în ARTb.
Vectorii de intrare inițiali1sunt dați sub forma:
a(i)=/parenleftBig
a(i)
1,…,a(i)
n/parenrightBig
, a(i)
j∈[0,1], j=1,n,i =1,p (9.1)
pﬁind numărul de vectori din setul de instruire.
În cazul în care datele inițiale nu sunt din intervalul [0,1], se poate aplica
1În acest capitol vectorii sunt văzuți ca matrice cu o linie.
105

o scalare globală:
a(i)
j→a(i)
j−MIN
MAX−MIN,j=1,n,i =1,p
pentru ﬁecare vector de intrare a(i)=/parenleftBig
a(i)
1,…,a(i)
n/parenrightBig
,1≤i≤p, undeMIN
șiMAXsunt valoarea minimă și respectiv maximă din vectorii de intrare:
MIN (MAX ) = min(max)/braceleftBig
a(i)
j/bracerightBig
, j=1,n,i =1,p
sau se poate lua un minorant (respectiv majorant) al valorilor de intrare.
Alternativ, ﬁecare din trăsături (coloane) poate ﬁ scalată independent de
celelalte. În urma aplicării oricărei din aceste scalări, vectorii din setul de
instruire vor avea valori în intervalul [0,1].
O tehnică de preprocesare numită codiﬁcare complementară este efectu-
ată în cele două module fuzzy ART de către stratul Fa
0, respectivFb
0pentru
a evita proliferarea nodurilor. S–a dovedit că fără codiﬁcarea complemen-
tară se vor produce numeroase categorii grupate lângă origine, fără a crea
altelecaresăleînlocuiască. Codiﬁcareacomplementarăesteutilizatăpentru
a obține vectori normalizați, adică vectori cu normă constantă:
|A|=const (9.2)
unde|·|este o funcție normă. În cazul de față |·|reprezintă norma L1:
pentru un vector z= (z1,…,zk)
|z|=L1(z) =k/summationdisplay
i=1|zi| (9.3)
Fiecare vector de intrare a= (a1,…,an)produce vectorul:
A= (a,ac) = (a,1−a) = (a1,…,an,1−a1,…, 1−an)(9.4)
a cărui normă este:
|A|=n/summationdisplay
i=1ai+n/summationdisplay
i=1(1−ai) =n=constant (9.5)
motiv pentru care spunem că vectorul Aeste normalizat.
PentruARTafolosim următoarele notații: Maeste numărul de noduri în
Fa
1șiNaeste numărul de noduri din Fa
2. Datorită pasului de preprocesare,
Ma= 2n. Fiecare nod Fa
2reprezintă un grup de intrări similare (numit
în alte contexte cluster); vom folosi termenul “categorie” pentru a ne referi
la un nodFa
2. Fiecare categorie Fa
2are propriul set de ponderi adaptive
stocate sub forma unui vector:
wa
j=/parenleftBig
wa
j,1,…,wa
j,Ma/parenrightBig
, j=1,Na. (9.6)
106

Aceste ponderi formează memoria pe termen lung a sistemului. Inițial, toți
vectorii au valorile:
wa
ji= 1, j=1,Na, i=1,Ma (9.7)
Spunem că un nod din Fa
2estenecomis dacă nu a învățat încă nici un
vector de intrare, comisîn caz contrar. Modulul ARTaeste responabil
cu crearea grupărilor de vectori de intrare. În timpul etapei de învățare,
Naeste numărul de noduri (categorii) comise. Notații și aﬁrmații similare
se folosesc pentru ARTb, care primește vectori m-dimensionali. Pentru o
problemă de clasiﬁcare, adică o problemă pentru care numărul – total sau
inițial – de clase de ieșire este aprioric cunoscut, indexul de clasă este același
cu indexul de categorie din Fb
2și astfelARTbpoate ﬁ substituit de un vector
Nb−dimensional. Într-o astfel de codiﬁcare, valoarea lui Nbpoate să crească
– dacă noi clase de ieșire sunt adăugate la setul de instruire.
ModululMapﬁeldpermiteFAMsăcreezelegăturiîntreceledouămodule
ART, stabilind legături de tip mulți–la–unu între categorii din ARTași
ARTb. Numărul de noduri din Fabeste egal cu numărul de noduri din
Fb
2. Fiecare nod jdinFa
2este legat cu ﬁecare nod din Fb
2via un vector
de ponderi wab
j, unde wab
jeste aj–a linie dintr-o matrice wab(j=1,Na).
Toate ponderile din wabsunt inițializate cu 1:
wab
jk= 1, j=1,Na, k=1,Nb (9.8)
9.4.2 Algoritmul de învățare pentru FAM
În următorul algoritm, operatorul ∧este așa–numitul operator fuzzy
AND, care pentru doi vectori
p= (p1,…,pk),q= (q1,…,qk) (9.9)
cu0≤pi, qi≤1,i=1,keste deﬁnit ca:
(p∧q)i= min(pi,qi),i=1,k (9.10)
1. Se setează parametrul de factor de vigilență ρala o valoare egală cu
o valoare de bază prestabilită: ρa=ρa∈[0,1)și se consideră că
toate categoriile din Fa
2sunt neinhibate – adică ﬁecare nod participă
la căutarea unei categorii adecvate pentru vectorul de intrare curent;
2. Pentru ﬁecare vector de intrare preprocesat A, o funcție fuzzy este
folosită pentru a obține un răspuns de la ﬁecare categorie Fa
2:
Tj(A) =|A∧wa
j|
αa+|wa
j|, j =1,Na (9.11)
107

3. FieJindicele de nod neinhibat care dă cea mai mare valoare calculată
precum în (9.11):
J= arg max{Tj|1≤j≤Nași noduljnu este inhibat}(9.12)
4. Veriﬁcă condiția de rezonanță, i.e. dacă intrarea este suﬁcient de si-
milară cu prototipul câștigătorului:
|A∧wa
J|
|A|≥ρa (9.13)
Dacă condiția este îndeplinită, atunci mergi la pasul 5, altfel inhibă
nodulJastfel încât el nu va mai participa la competiția pentru vec-
torul curent. Dacă există noduri neinhibate, atunci mergi la pasul 3,
altfel recrutează o nouă categorie (creează un nou nod în Fa
2) pentru
a reprezenta vectorul de intrare și ﬁe Jindicele acestui nou nod.
5. Un proces similar se desfășoară și în ARTb. FieKindicele nodului
câștigător din ARTb. Vectorul de ieșire Nb-dimensional Fb
2este setat
la:
yb
k=I(k=K), k =1,Nb (9.14)
undeIeste funcția indicator (3.23) de la pagina 42.
În Mapﬁeld se formează vector de ieșire xab:
xab=yb∧wab
J (9.15)
6. Un test de veriﬁcare în Mapﬁeld controlează potrivirea dintre valoarea
prezisă xabși vectorul de ieșire atașat vectorului de instruire curent
yb:
|xab|
|yb|≥ρab (9.16)
undeρab∈[0,1]este un parametru de vigilență Mapﬁeld. Dacă testul
din ecuația (9.16) este trecut, atunci se face învățare ARTa,ARTbși
Mapﬁeld (pasul 7). Altfel, se inițiază o secvență de pași numită match
tracking (pasul 8).
7. În modulele fuzzy ART și în Mapﬁeld se efectuează învățare:
wa(new)
J=βa/parenleftBig
A∧wa(old)
J/parenrightBig
+ (1−βa)wa(old)
J(9.17)
(și analog în ARTb) și
wab
Jk=I(k=K) (9.18)
Se merge la pasul 9.
108

8. Faza de match tracking, în care se intră doar dacă inecuația (9.16) nu
e în deplinită: mărește ρa:
ρa=|A∧wa
J|
|A|+δ (9.19)
unde 0<δ < 1. Dacăρa>1atunci vectorul curent de instruire este
rejectat, altfel mergi la pasul 3.
9. Dacă mai sunt vectori în setul de învățare, mergi la pasul 1, altfel
STOP.
Urmează câteva comentarii privind pașii de mai sus:
1. La pasul 2, ﬁecare vector este preprocesat datorită straturilor Fa
0și
respectivFb
0.αa>0este un parametru de alegere. Pentru doi vectori
pșiq, raportul:
r=|p∧q|
|q|(9.20)
cu0≤r≤1dă gradul în care peste subset fuzzy al lui qși deci
pentru 0< αa/lessmuch1,Tj(A)din ecuația 9.11 măsoară gradul în care
Aeste o submulțime fuzzy a categoriei wa
j. Dacă se crește valoarea
luiαaatunci se va mări numărul de categorii, lucru nu întotdeauna
beneﬁc. Este deci sugerat ca să se mențină αala o valoare mică, de
exempluαa= 0.001; valori mai mici ale lui αanu duc la o diferență
semniﬁcativă.
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 indicele
minim.
3. Parametrul ρacalibrează încrederea minimă pe care ARTatrebuie 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ă.
Valori mici ρaduc la un grad mare de generalizare și un număr mai
mic de categorii ARTa.
4. Dacă inecuația (9.13) este îndeplinită, spunem că avem rezonanță în
ARTapentru vectorul de intrare curent. Datorită pasului de prepro-
cesare, conform (9.5), numitorul din (9.13) este exact dimensiunea
originară a vectorilor 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; în
acest din urmă caz indicele nodului câștigător Keste indicele de clasă
corespunzător intrării curente;
109

6. Când se intră în pasul 5, avem rezonanță atât în ARTacât și înARTb.
Vectorul xabdă activarea Mapﬁeld și se folosește atât când ambele
moduleFa
2șiFb
2sunt active, i.e.la faza de învățare, cât și când Fa
2
este activ și Fb
2e inactiv (faza de predicție). În faza de învățare xabare
forma din ecuația (9.15); în faza de predicție acest vector este calculat
ca:
xab=wab
J (9.21)
7. Atunci când ambele module Fa
2șiFb
2sunt active – lucru valabil la
instruirea rețelei, când se furnizează atât vectorul de intrare cât și cel
de ieșire – a J-a categorie câștigătoare din ARTava corespunde unui
vector de ponderi wab
Jdin Mapﬁeld care leagă nodul Fa
2cu categoria
Fb
2prezisă. În paralel, pentru modulul ARTbam obținut vectorul de
ieșire ybca în ecuația (9.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. Atunci când categoria Jeste necomisă avem:
wab
J= (1,1,…, 1) (9.22)
și deci xab=yb. Când doar modulul Fa
2este activ, matricea wab
dă valoarea prezisă: indicele categoriei din ARTbasociată cu intrarea
curentă este unica poziție kdin liniaja matricei wabpentru care
wab
jk= 1.
Ecuația (9.18) indică faptul că al J-lea nod din ARTaeste legat cu
categoria de ieșire K, iar legătura, odată făcută, nu se mai schimbă.
8. Pentruβa(Pasul 7), există două moduri de învățare:
(a)fast learning corespunde la a seta βa= 1atât pentru nodurile
comise cât și pentru cele necomise;
(b)fast-commit and slow-recode learning corespunde la a seta βa= 1
pentru nod necomis și βa<1pentru cele comise.
9. La faza de match tracking, datorită creșterii valorii lui ρaconform
ecuației (9.19), nodul Jnu va mai ﬁ în stare să câștige în competițiile
următoare pentru vectorul de intrare curent. Match tracking–ul va
declanșa o nouă căutare în ARTapentru a găsi un alt nod câștigător.
Se poate ca asta să ducă la crearea unui nou nod în ARTa. Căutarea
se repetă până când ρa>1, sau până când se găsește o categorie
adecvată în ARTa.
10. O valoare mare a lui δîn pasul 8 va crește numărul de categorii. Se
folosește de regulă o valoare mică δ= 0.001
110

11. Ordinea de prezentare a vectorilor din setul de instruire inﬂuențează
comportamentul rețelei, adică numărul și pozițiile categoriilor va di-
feri. Putem face antrenarea în paralel cu diferite permutări ale setului
de intrare, apoi se contorizează voturile pentru ﬁecare vector care tre-
buie clasiﬁcat.
Pasul de învățare este repetat până când nu mai este nicio eroare pentru
setul de învățare, sau până se atinge o eroare acceptabilă; dacă se vrea
învățare incrementală atunci se face o singură trecere pe setul de antrenare.
După învățare, FAM poate ﬁ utilizat pentru predicție. În această fază,
stratulFb
2este inactiv și Fa
2este activ. Conform ecuației (9.21), predicția
este făcută doar pe baza lui wab
J.
Există o interpretare geometrică interesantă a categoriilor ARTa: ﬁecare
categorie de intrare wa
jse reprezintă ca un hiper–dreptunghi Rj, deoarece
vectorul de ponderi poate ﬁ scris ca:
wa
j=/parenleftBig
uj,vc
j/parenrightBig
(9.23)
unde
vc
j=/parenleftBig
vc
j1,…,vc
jn/parenrightBig
(9.24)
(atât ucât și vaunelemente). Vectorul ujdeﬁnește un colț al hiper–
dreptunghiului Rjiarvjeste colț diagonal opus lui. Pentru n= 2, repre-
zentarea graﬁcă este dată în ﬁgura 9.2. Dimensiunea lui Rjeste deﬁnită
ca:
|Rj|=|vj−uj| (9.25)
O interpretare similară este valabilă și pentru modulul ARTb.
În modulul ARTa, atunci când se creează un nou nod în pasul 4, acesta
vaﬁdefaptvectoruldeintrarepreprocesatcurent: w(new)
J=A= (a,ac); cu
alte cuvinte, R(new)
jeste de fapt un punct reprezentând vectorul de intrare
preprocesat A. În timpul ﬁecărui pas de învățare fast-learning ( βa= 1),Rj
se expandează la Rj⊕a, hiper–dreptunghiul minim care conține Rjșia–
a se vedea ﬁgura 9.3; dacă punctul Aeste chiar în interiorul lui Rj, atunci
Rjnu se modiﬁcă. Colțurile lui Rj⊕asunt deﬁnite de a∧uJșia∨vJ,
unde operatorul∨este deﬁnit ca operatorul fuzzy OR:
(p∨q)i= max (pi,qi), i= 1…,n (9.26)
pentru pșiqvectori precum în ecuația (9.9).
Se poate arăta că:
|Rj|=n−|wj| (9.27)
iar hiper–dreptunghiul corespunzător unei categorii nu poate crește oricât
de mult:
|Rj|≤(1−ρa)n (9.28)
111

Figura 9.2: Fiecare vector pondere wa
jare o interpretare geometrică precum
un hiper–dreptunghi Rjcu colțurile deﬁnite de ujșivj
Figura 9.3: Expandarea de categorie în timpul fast learning: de la Rjla
hiper–dreptunghiul mai mare conținând Rjșia.
112

Proprietate similară este valabilă și pentru ARTb.
Aceste proprietăți sunt sumarizate de teorema:
Teorema 5. [20] Un sistem Fuzzy ART cu codiﬁcarea complementară, fast
learningși termen devigilență constantformeazăcategorii hiper–dreptunghiuri
care converg în limită la o secvență arbitrară de vectori analogici sau binari.
Hiper–dreptunghiurile cresc monoton în toate dimensiunile. Dimensiunea
|Rj|a unui hiper–dreptunghi este n−|wj|, unde wjeste vectorul pondere
corespunză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 exem-
plare din setul de antrenare este inﬁnit. Proprietăți similare au loc pentru
fast-learn, slow-recode, exceptând cazul în care este nevoie de prezentări re-
petate ale ﬁecărei intrări înainte de stabilizarea sistemului.
Sumarizând: FAM aplică o învățare bazată pe potrivire, conform căreia
vectorii sunt grupați în categorii pe baza unor măsuri de similaritate. Dacă
un vector din setul de instruire nu se potrivește suﬁcient de bine cu o cate-
gorie existentă, atunci se va crea una nouă pentru a o reprezenta. Datorită
acestui comportament, FAM nu încearcă să minimizeze o funcție de cost,
evitând problemele întâlnite în optimizarea funcțiilor. Strategia de învă-
țare prezentată este deci diferită de cea bazată pe minimizarea erorii, care
cere continuarea antrenării prin epoci suplimentare, dacă valoarea erorii este
inacceptabilă sau ponderile nu se stabilizează.
113

Capitolul 10
Calcul evoluționist
Calculul evoluționist este inspirat din teoria evoluției dezvoltate de că-
tre Charles Darwin și de genetică – știința eredității, având ca părinte pe
Gregor Mendel. Au în comun faptul că folosesc populații de elemente care
sunt folosite pentru căutarea soluției unei probleme, spre deosebire de alte
abordări care încercă îmbunătățirea printr-un proces iterativ a unei singure
valori.
10.1 Taxonomie
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 multe
rezultate sunt în domeniului algoritmilor genetici, dar la ora actuală există
hibridizări ale acestor 4 arii.
Cel care este creditat ca ﬁind pionierul domeniului algoritmilor genetici
este 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; de
asemenea, a dat teorema schemelor. El a fost cel care a stabilit operațiile
care trebuie să se aplice unei populații genetice – selecția, încrucișarea și
mutația.
Programarea evoluționistă (avându–l ca pionier pe Larry J. Fogel) fo-
losește ca operatori selecția celui mai potrivit individ și mutația, dar nu și
încrucișarea. În timp ce algoritmii genetici văd procesul evolutiv ca ﬁind
114

aplicat pe o populație de indivizi din aceeași specie , programarea evoluțio-
nistă vede evoluția ca aplicându–se unei populații de specii . Fiecare element
din populație este interpretat ca o specie întreagă.
StrategiiledeevoluțieaufostdezvoltatedeIngoRechenbergșiHans-Paul
Schwefel, care au experimentat diferite variante de mutație pentru rezolva-
rea unor probleme legate de optimizarea unor suprafețe aﬂate în contact cu
un ﬂuid. Mutațiile reprezentau perturbări ale unor stări, efectuând o cău-
tare în vecinătate. Multiplele variante de perturbare au construit un întreg
domeniu.
Programarea genetică (Richard Friedberg) a pornit cu coduri program
de lungime ﬁxă. Prin modiﬁcări efectuate în mod automat asupra acestor
programe se dorea obținerea unor variante de cod optimizate. Esențiale
sunt aici modul de reprezentare a acestor programe și funcțiile de măsurare
a calității codului.
De cele mai multe ori, pentru o abordare dintr-unul din cele patru do-
menii se urmează pașii:
1. Inițializează populația
2. Calculează performanța ﬁecă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 ﬁecărui pas. Pașii sunt bazați
pe alegeri de valori aleatoare, ceea ce dă de înțeles că rulări diferite pot duce
la valori diferite. Totodată algoritmii nu garantează descoperirea unei valori
optime. De cele mai multe ori, însă nu este nevoie să se cunoască exact
optimul, ci o valoare suﬁcient de bună. În practică, calculul evoluționist dă
rezultate bune într–un timp rezonabil.
În cele ce urmează vom prezenta algoritmii genetici.
10.2 Algoritmi genetici
Rolul mediului ca factor modelator în teoria evoluționistă este preluat în
algoritmii genetici de către o funcție scop (sau funcție obiectiv). Vom detalia
algoritmul pentru maximizarea unei funcții f: [a,b]→R∗
+. Indivizii care
alcătuiesc populația se numesc cromozomi (șiruri de biți) și sunt alcătuiți
dingene(biți).
Constrângerea ca funcția fsă ﬁe strict pozitivă poate ﬁ asigurată prin
adunarea unei cantități convenabile la funcția inițială, dacă are și porțiuni
115

negative, sauconsiderareafuncției g(x) = max(0,f(x)). Alegereadeamaxi-
miza funcția obiectiv este convenabilă. Dacă se dorește minimizarea funcție,
se poate ține cont de relația:
minxf(x) =−maxx[−f(x)] (10.1)
Se pornește cu o populație inițială, care este supusă apoi unei secvențe
de procese de tipul:
1. selecție: indivizii care sunt cei mai buni (considerând valoarea funcției
fce se vrea maximizată) sunt favorizați să apară de mai multe ori
într-o populație nouă față de indivizii mai puțin performanți;
2. încrucișare: arelocunschimbdegeneîntreperechidepărinți,formându-
se copii; aceștia se presupune că moștenesc și combină performanțele
părinților.
3. mutație: se efectuează niște modiﬁcări minore asupra materialului ge-
netic existent.
Pas 1. Crearea unei populații inițiale de cromozomi. Seconsiderămai
multe valori pentru variabila x∈[a,b]. Numărul acestor valori – nu-
mit dimensiunea populației – este dat ca parametrul al algoritmului,
n, dependent de problemă. Toate valorile sunt cuantiﬁcate prin cro-
mozomi care sunt șiruri de kbiți – un bit reprezintă în acest caz o
genă a cromozomului, kﬁind alt parametru de intrare.
Generarea celor ncromozomi se face aleator, prin setarea ﬁecărei gene
la valoarea 0 sau 1, la întâmplare. Se obține astfel o populație inițială
formată din cromozomii c1,…,cn.
Fiecare cromozom c(adică șir de kbiți) va produce un număr x(c)din
intervalul [a,b], astfel: dacă valoarea în baza 10 a cromozomului este
v(c)(0≤v(c)≤2k−1) atunci valoarea asociată din intervalul [a,b]
este:
x(c) =a+v(c)·b−a
2k−1∈/braceleftbigg
a,a+b−a
2k−1,a+ 2·b−a
2k−1,…,b/bracerightbigg
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+ 1se obține
pe baza populației de la generatia g. Operatorii sunt selecția, împere-
cherea (crossover, încrucișarea) și mutația.
Pas 2.1. Selecția. Pentru ﬁecare cromozom cidin populatie se cal-
culează funcția obiectiv yi=f(x(ci)),1≤i≤n. Apoi se însu-
mează valorile funcțiilor obiectiv obținute pentru ﬁecare cromo-
zom în parte:
S=n/summationdisplay
i=1yi
116

Pentru ﬁecare din cei ncromozomi se calculează probabilitatea
de selecție:
pi=yi
S,1≤i≤n
Pentru ﬁecare cromozom se calculează probabilitatea cumulativă
de selecție:
qj=j/summationdisplay
i=1pi,1≤j≤n
Remarcăm că se obține 0< p 1=q1< q 2<···< qn= 1. Cu
cât cromozomul cidetermină o valoare mai mare pentru funcția
f(i.e.cu cât valoarea f(x(ci))este mai mare), cu atât diferența
dintreqișiqi−1este mai mare.
Se selectează nnumere aleatoare uniform distribuite în (0,1].
Pentru ﬁecare număr, dacă el se găsește în intervalul (0,q1]atunci
cromozomul c1este ales și depus într-o populație nouă; dacă acest
număr se aﬂă în intervalul (qi,qi+1]atunci se alege cromozomul
ci+1. Remarcăm ca numărul de cromozomi prezenți în noua po-
pulație este tot n. Cu cât valoarea y=f(x(c))asociată unui
cromozom ceste mai mare, cu atât cresc șansele lui spre a ﬁ
selectat și depus în noua populație. Este foarte probabil ca un
astfel de cromozom valoros să apară de mai multe ori in popula-
ția nouă; de asemenea, este foarte probabil ca un cromozom cu o
valoare mică pentru funcția fsă nu apară deloc.
Pas 2.2. Încrucișarea (împerecherea, crossover) Pentru ﬁecare cro-
mozom care a rezultat la pasul anterior se alege o valoare alea-
toare, uniform distribuită în intervalul (0,1]. Dacă această va-
loare este mai mică decât un parametru pc(parametru al aplica-
ției,e.g.0.1), atunci cromozomul este ales pentru incrucișare. Se
procedează astfel încât să se obțină un număr par de cromozomi
(de exemplu se renunță la ultimul dacă numărul lor este impar).
Cromozomii aleși se încrucișează astfel: primul selectat cu al doi-
lea selectat, al 3-lea cu al 4-lea etc. Încrucișarea decurge astfel:
•se alege un număr aleator tintre 1 șik−1;
•se obțin 2 cromozomi copii astfel: primul va conține primele
tgene ale primului părinte și ultimele k−tgene ale celui
de–al doilea părinte; al doilea copil conține primele tgene ale
celui de–al doilea părinte și ultimele k−tgene ale primului
părinte;
•cei doi cromozomi copii îi vor înlocui în populație pe părinții
din care provin.
Pas 2.3. Mutația. Populației obținute i se aplică operator de mu-
tație, astfel: pentru ﬁecare genă a ﬁecărui cromozom se alege o
117

valoare aleatoare, uniform distribuită în (0,1]; dacă acest număr
este mai mic decât o probabilitate de mutație pm(parametru al
aplicației, e.g.pm= 0.01), atunci se modiﬁcă valoarea curentă a
genei 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 pro-
cesului este epuizat), se raportează valoarea celui mai bun cromozom din
ultima generație1.
Avantajul primar al algoritmilor genetici constă în schimbul de infor-
mație dintre indivizi realizat la etapa de încrucișare, adică schimbarea de
blocuri de date care au evoluat. O utilizare eﬁcientă a algoritmilor genetici
presupune crearea unor structuri de date pentru gene și a unor operatori
adecvați problemei 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ă ca un șir de caractere construit cu simbolurile “0”, “1” și “*”,
unde “*” poate ﬁ substituit cu orice bit; simbolul “*” poate apărea de ori-
câte ori, inclusiv niciodată. De exemplu, schema (∗0101)se potrivește cu
doi cromozomi3:(00101)și(10101). Dacă o schemă are lsimboluri “*”,
atunci ea poate să ﬁe reprezentată de 2lcromozomi, iar un cromozom de
lungimekpoate ﬁ descris de C0
k+C1
k+···+Ck
k= 2kscheme.
Pentru o schemă Sdeﬁnim ordinul ei (și îl notăm cu o(S)) numărul
de poziții pe care se aﬂă valorile 0 sau 1, adică numărul de poziții ﬁxate.
De exemplu, 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ății de supraviețuire a sa în cadrul mutațiilor.
Lungimea unei scheme S, notată cu δ(S), este distanța dintre prima
și ultima poziție ﬁxată. Pentru schema dată mai sus, δ(S) = 6−2 = 4
(sauδ(S) = 5−1 = 4, după cum indicierea începe de la 1 sau de la 0).
Noțiunea de lungime a unei scheme este utilă pentru calculul probabilității
de supraviețuire a unei scheme în cadrul operațiilor de încrucișare.
Pentru o populație de indivizi aﬂată la momentul tal evoluției, vom nota
cun(S,t)numărul de cromozomi din populație care reprezintă (se potrivesc
cu) schema S. De asemenea, vom considera valoarea medie a schemei din
populația de la un timp t, notată cu f(S,t)și deﬁnită ca suma valorilor
1În practică se preferă strategia elitistă: se returnează cel mai bun individ al tuturor
generațiilor.
2S-a stabilit “ecuația” Genetic Algorithms + Data Structures = Evolution Programs,
[17].
3În acest caz spunem că schema este reprezentată de cei doi cromozomi.
118

cromozomilor din populație care reprezintă schema Sîmpărțită la numărul
acestor cromozomi, n(S,t).
La pasul de selecție, un cromozom Aeste copiat în populația următoare
cu probabilitatea:
P(A) =f(A)/summationtext
cromozomcf(c)
unde însumarea se face după toți cromozomii cai populației curente. Rea-
mintind că neste numărul de cromozomi din populație, avem:
n(S,t+ 1) =n(S,t)·f(S,t)
1
n/summationtext
cromozomcf(c)
Cantitatea f(t) =/summationtext
cromozomcf(c)/neste chiar valoarea medie a populației
de la momentul t, deci avem:
n(S,t+ 1) =n(S,t)·f(S,t)
f(t)
Numărul de reprezentanți ai schemei Scare vor exista la momentul t+
1este dependent de valoarea schemei dată de cromozomii care există în
populația de la momentul t. De exemplu, o schemă Scare produce o valoare
relativ mare a lui f(S,t)față def(t)va impune creșterea numărului de
reprezentanți ai 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ă:
n(S,t) =n(S,0)(1 +ε)t,∀t∈{1,2,…}
adică pentru scheme care au valoare medie desupra valorii medii a populației
numărul de reprezentanți va crește exponențial în timp – respectiv dacă
valoarea schemei este sub medie, numărul de reprezentanți obținuti prin
selecție scade exponențial.
În ceea ce privește încrucișarea, să presupunem că cromozomul cu 7 gene
c= (1010100) este selectat pentru reproducere; există 27scheme care îl au
pecdrept reprezentant, de exemplu:
S1= (∗01∗∗∗∗ )
și
S2= (1∗∗∗∗ 0∗)
Să presupunem că în procesul de încrucișare tăietura se face după a patra
genă:
c= (1 0 1 0 |1 0 0)
S1= (∗0 1∗ | ∗ ∗ ∗ )
S2= (0∗ ∗ ∗ | ∗ 0∗)
119

Se observă că pentru exemplul considerat schema S1sigur se va regăsi într–
un descendent (deci schema supraviețuiește), deoarece valorile 0 și 1 se re-
găsesc pe pozițiile inițiale, în timp ce S2are șanse de a ﬁ distrusă4. Intuitiv,
este clar faptul că lungimea mică a schemei S1mărește șansa de supravie-
țuire, față de S2care poate ﬁ ușor “spartă” în cromozomii copii. Desigur,
contează poziția tăieturii.
Tăietura poate să apară uniform aleator (echiprobabil) în k−1poziții.
Probabilitatea de distrugere a unei scheme este:
Pd(S) =δ(S)
k−1
și evident probabilitatea evenimentului contrar, reprezentând supraviețuirea
schemei este
Ps(S) = 1−Pd(S) = 1−δ(S)
k−1
Conform strategiei de alegere a cromozomilor ce se supun împerecherii, pro-
babilitatea ca un cromozom să participe la încrucișare este pc, deci proba-
bilitatea de supraviețuire a unei scheme Seste:
Ps(S) = 1−pc·δ(S)
k−1
Se mai poate lua în considerare faptul că o schemă Spoate totuși să su-
praviețuiască, dacă cromozomii care se încrucișează au pe pozițiile ﬁxe ale
schemei chiar valorile din S. Așa ceva este posibil și trebuie considerat ca
mărind șansele de supraviețuire a unei scheme. Ca atare, șansa de supravie-
țuire este de fapt dată printr–o inegalitate:
Ps(S)≥1−pc·δ(S)
k−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:
n(S,t+ 1)≥n(S,t)·f(S,t)
f(t)·/bracketleftbigg
1−pc·δ(S)
k−1/bracketrightbigg
Mutația schimbă aleator biți din cromozom cu complementul lor. Este
clar că pentru ca o schemă să supraviețuiască, pozițiile sale ﬁxe nu trebuie
să ﬁe alese pentru mutație. Probabilitatea ca un bit oarecare să nu ﬁe mo-
diﬁcat este (1−pm). Alegerile biților care să sufere mutație sunt evenimente
independente, deci probabilitatea ca cei o(S)biți ﬁcși ai unei scheme să se
mențină (și deci ca întreaga schemă să se mențină) este:
Ps(S) = (1−pm)o(S)
4S2nu e distrusă, însă, dacă al doilea cromozom care participa la încrucișare vine cu
aceleași gene pe pozițiile ﬁxe din schemă.
120

Pentru căpm/lessmuch1, putem aproxima (1−pm)o(S)cu1−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:
n(S,t+ 1)≥n(S,t)·f(S,t)
f(t)·/bracketleftbigg
1−pc·δ(S)
k−1−pm·o(S)/bracketrightbigg
Se poate da acum enunțul teoremei schemelor, teorema fundamentală a al-
goritmilor genetici datorată lui Holland (1975):
Teorema 6 (Teoremaschemelor) .Schemele scurte, de ordin mic, cu valoare
peste medie cresc ca număr de reprezentanți în decursul generațiilor.
S–a formulat următoarea ipoteză:
Ipoteza blocurilor de construcție, [17]. Un algoritm genetic execută
un proces de căutare prin suprapunerea unor scheme scurte, de ordin mic
și de valoare mare, numite blocuri de construcție. Se poate arăta că pentru
o populație de ncromozomi, numărul de scheme efectiv procesate este în
ordinul lui n3, ceea ce dă caracter de paralelism implicit al algoritmilor
genetici: se procesează nu doar o singură schemă, ci mai multe.
10.4 Problema reprezentării datelor în algoritmii
genetici
Reprezentarea indivizilor ca șiruri de biți este nenaturală pentru multe
problemepractice. Săpresupunem, deexemplu,problemacomis-voiajorului:
ﬁind datenorașe și distanțele dintre ele, să se determine un tur al lor, astfel
încât ﬁecare oraș să ﬁe vizitat exact o singură dată, să se revină la orașul
de plecare iar costul total al drumului să ﬁe minim5. O soluție este dată ca
o permutare a mulțimii {1,…,n}.
Pentru cazul n= 20, dacă folosim reprezentarea binară, putem vedea că
cinci biți sunt suﬁcienți pentru a reprezenta orice număr de la 1 la 20, deci
ar trebui să folosim 20·5 = 100de biți pentru reprezentarea unei soluții po-
tențiale. Să presupunem că la un moment dat avem grupul de 5 biți 01101
reprezentând orașul cu numărul 13; prin aplicarea mutației este posibil să se
ajungă 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
elementelor din problemă sau a unor operatori care nu sunt adaptați co-
respunză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/similarequal1030, în timp ce mulțimea tuturor ciclurilor hamiltoniene este
– considerând primul oraș ca ﬁind ﬁxat si neconsiderând soluțiile simetrice
5Întermenidegrafuri: seceredeterminareaunuicicluHamiltoniandelungimeminimă.
121

de formaA→B→C→A≡A→C→B→A– mulțimea permutărilor
cu19!/2<1017elemente. În situația dată deducem că utilizarea unei
codiﬁcări binare conduce la un spațiu de căutare mărit artiﬁcial, existând
zone mari din spațiul binar care nu corespund unor soluții viabile.
Alte exemple de probleme aﬂate în aceeași situație pot ﬁ încă date; se
ajunge la concluzia că varianta naivă de reprezentare a valorilor și a ope-
ratorilor genetici nu se potrivește neapărat la orice problemă de căutare.
Modelarea unui individ și a operatorilor asociați trebuie să se facă ținând
cont de domeniu și de particularitățile problemei. Vor ﬁ exempliﬁcate codi-
ﬁcări adecvate pentru câteva probleme clasice.
O altă problemă care trebuie tratată este: cum procedăm când există
constrângeri? De exemplu, dacă vrem să maximizăm funcția:
f(x,y) =x2−y3+ 2·x·sin(y) (10.2)
cu condiția ca variabilele xșiysă satisfacă constrângerea:
1≤x3−cos(y) +y2≤5 (10.3)
cum încorporăm restricția în algoritmul genetic? Dacă folosim varianta cla-
sică de codiﬁcare a unui individ, împreună cu operatorii de încrucișare și de
mutație prezentați, cum asigurăm faptul că operatorii dați nu duc indivizii
în zone în care constrângerea (10.3) 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 satisfac
constrângerile;
3. implementarea unor operatori de încrucișare și de mutație care păs-
trează indivizii în condițiile impuse.
Pe marginea ﬁecăreia din cele trei variante există multiple versiuni:
•pentru penalizări, valoarea acestora poate ﬁ constantă, sau să varieze
cu gradul în care se încalcă constrângerile date; această ultimă va-
riantă poate ﬁ codiﬁcată sub forma unei funcții logaritmice, liniare,
pătratice etc. O formă extremă de penalizare este eliminarea indi-
vizilor care încalcă restricțiile, dar trebuie dat răspuns la întrebarea:
cu ce se umple locul lăsat gol prin eliminare? sau cumva se permite
populației de dimensiune variabilă? cei mai mulți autori aﬁrmă că
această eliminare este prea dură, în timp ce menținerea unor indivizi
penalizați oferă variabilitate populației – se pot produce descendenți
valizi, chiar și din cei care nu respectă constrângerile.
122

•pentru algoritmii de reparare – este posibil să se integreze cunoștințe
din domeniu în metodele de corecție; trebuie zis însă că elaborarea
unui algoritm de corecție poate uneori să ﬁe o problemă la fel de grea
ca și rezolvarea problemei de la care s–a plecat.
•pentru ultima variantă – este cunoscut deja că orice tip de date trebuie
să vină cu un set de operatori dedicați care să permită prelucrarea ti-
purilor; o codiﬁcare potrivită a problemei împreună operatorii asociați
trebuie 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 indivizi
care nu încalcă (prea mult, sau deloc) restricțiile;
Pentru ﬁecare 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 codiﬁcări de-
cât cea binară. Desigur, se poate folosi și o combinație a celor trei variante
de mai sus.
Pentru numeroase probleme practice s–a constatat experimental că re-
prezentarea adecvată a indivizilor, împreună cu deﬁnirea unor operatori par-
ticularizați și cele 3 metode de mai sus dau rezultate mai bune decât aplica-
reaad literam a algoritmului genetic peste o formă binarizată a problemei.
Vom exempliﬁca pentru problema discretă a rucsacului: se dă un rucsac
de capacitate C, un set de mobiecte având greutățile Gi>0și valorile
asociateVi>0,1≤i≤m. Un obiect poate ﬁ luat doar în întregime în
rucsac; problema este: care sunt obiectele care trebuie încărcate, astfel încât
greutatea totală să nu depășească Ciar valoarea cumulată să ﬁe maximă?
Problema este NP-completă, deci la ora actuală nu cunoaștem un algo-
ritm de complexitate polinomială care să o rezolve. Multe probleme pot ﬁ
reduse la aceasta, de aici interesul acordat.
O reprezentare naturală a unui individ – respectiv încărcare de rucsac
– este un vector xcu elementele xi,1≤i≤m,xi∈ {0,1}, valoarea
0 însemnând că obiectul nu este luat, iar 1 – că e adăugat în rucsac. Se
impune, evident, condiția de viabilitate a unui vector x:
m/summationdisplay
i=1xi·Gi≤C
iar funcția de maximizat – numită și proﬁt în acest caz – este:
P(x) =m/summationdisplay
i=1xi·Vi
123

10.4.1 Varianta cu penalizare
Pentru ﬁecare individ xse va considera valoarea sa val(x):
val(x) =m/summationdisplay
i=1xi·Vi−Pen(x)
undePen(·)este funcția de penalizare:
Pen(x)/braceleftBigg
= 0,dacăxeste viabil
>0,dacăxnu 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 ﬁ de exemplu de diferența
dintre/summationtextm
i=1xi·GișiC– atunci se poate folosi o funcție de tip logaritmic,
liniar, pătratic, exponențial etc. Efectele alegerii unei asemenea funcții au
fost analizate pe diferite situații; a se vedea [17] pentru rezultate experimen-
tale și interpretarea lor.
10.4.2 Varianta cu reparare
Putem folosi aici tot codiﬁcarea binară. Algoritmul de corectare este
simplu: dacăsetuldeobiectealesdepășeștecagreutatetotalăcapacitatea C,
atunci se scot obiecte până când greutatea celor rămase devine acceptabilă
(cel multG). Vom transforma deci vectorul xînx/prime= (x/prime
1,…,x/prime
m)astfel
încât/summationtextm
i=1x/prime
iGi≤C.
Algoritmul de reparare a unui individ este:
Listing 10.1: Repararea unui vector invalid
function reparare( x,G,C) returns a vector
begin
rucsac−supraincarcat := false
x/prime:=x
if/summationtextm
i=1x/prime
i·Gi>C
thenrucsac−supraincarcat := true
end if
whilerucsac−supraincarct = true
i:= selecteaza un obiect din rucsac (#)
scoate obiectul i din rucsac : x/prime
i:= 0
if/summationtextm
i=1x/prime
i·Gi≤C
thenrucsac−supraincarcat := false
end if
end while
return x/prime
end
124

În ce privește metoda de selectare a lui idin linia marcată cu (#), avem
variantele:
•(reparare aleatoare) valoarea ise 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 ra-
portulPi/Gicel mai mic.
10.4.3 Codiﬁcarea adecvată a indivizilor
Vom prezenta o strategie de codiﬁcare a indivizilor, diferită de cea binară
utilizată până acum, numită reprezentarea ordinală. Codiﬁcarea este larg
utilizată și în alte probleme care presupun manipularea unor secvențe de
valori, de exemplu în problema comis-voiajorului. Vectorul xeste cu cele m
componente în baza 10, ﬁecare element xiavând proprietatea că 1≤xi≤
m−i+ 1,∀i∈{1,…,m}. De exemplu, pentru vectorul x= (3,3,4,1,1,1)
asociat listei de obiecte L= (1,2,3,4,5,6), decodiﬁcarea se obține astfel: se
scoate elementul de indice x1= 3din listaL, adică obiectul 3 și îl adăugăm
în rucsac;Ldevine (1,2,4,5,6); apoi se scoate elementul de indice x2=
3(adică obiectul 4) din Lși îl adăugăm în rucsac, Ldevine (1,2,5,6);
se scoate elementul de indice x3= 4dinL, adică obiectul 6, Ldevine
(1,2,5)etc. Obținem astfel ordinea de depunere în rucsac: 3, 4, 6, 1, 2, 5.
Fiecare cromozom codiﬁcă astfel o ordine de adăugare a obiectelor în rucsac.
Adăugarea obiectului în rucsac se face numai dacă nu duce la depășirea
capacității C.
Se poate vedea că operație de încrucișare va duce întotdeauna la copii
valizi, adică pentru un copil z= (z1,…,zn)avem că 1≤zi≤n−i+1dacă
și părinții au aceeasi proprietate. Mutația este similară cu cea de la cazul
binar: o componentă aleasă pentru mutație, ﬁe ea xieste modiﬁcată cu o
valoare aleatoare uniform distribuită în mulțimea {1,…,n−i+ 1}diferită
dexi.
Listing 10.2: Utilizarea codiﬁcării ordinale
procedure decodificare ( x)
begin
construieste o lista Lde obiecte
greutateTotala := 0
profitTotal := 0
fori= 1,n
j :=xi
o :=Lj
sterge elementul al j−lea din lista L
ifgreutateTotala + Go≤C
then begin
125

greutateTotala := greutateTotala + Go
profitTotal := profitTotal + Po
end
end if
end for
end
ListaLse poate crea într–o ordine aleatoare, ca o permutare a mulțimii
{1,…,n}. Indivizii rezultați — adică cei care realizează populația inițială
— vor ﬁ deci generați aleatori.
Rezultate experimentale pentru cele trei variante de rezolvare sunt date
în [17]. Concluziile experimentelor însă nu pot ﬁ generalizate la orice pro-
blemă care vine cu impunere de restricții. Se exempliﬁcă însă că diferențele
de performanță pot ﬁ mari pentru aceste abordări.
10.5 Exemplu: problema orarului
Problema orarului este o altă situația practică care se abordează prin
intermediul algoritmilor genetici. Problema este NP-completă. Are diferite
enunțuri, vom prezenta varianta dată în [17].
Se dau următoarele:
•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}
Orarultrebuiesă respecte următoarele cerințe:
•există un număr predeﬁnit de ore pentru ﬁecare 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 ﬁecare clasă programată la o anumită oră trebuie să existe exact un
profesor
Mai avem și constrângeri care ar trebui respectate; acestea sunt legate
de:
•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;
126

•număr maxim de ore pe zi epntru elevi/profesori
Codiﬁcarea binară pentru această problemă, cu toate că este posibilă, poate
apărea drept nenaturală; mai mult decât atât, există riscul ca spațiul de
căutare să se mărească artiﬁcial, precum la problema comis voiajorului. Pu-
tem să codiﬁcăm un orar (un individ) ca ﬁind o matrice Ocumlinii șin
coloane, unde liniile corespund profesorilor iar coloanele – orelor disponibile.
Fiecare celulă este ﬁe liberă, ﬁe conține o clasă Ci,1≤i≤k.
Pentru reprezentarea dată, operatorii genetici ar putea ﬁ6:
•mutația de ordin k: se iau 2 secvențe adiacente formate din pelemente
și se interschimbă
•mutația de zile: se iau două zile și se interschimbă între ele
•încrucișare: seporneștedeladouăorarepărinte O1șiO2, seefectuează
tăietură pe orizontală sau pe verticală și se face interschimbarea de
porțiuni, întocmai ca la cromozomii binari
Este posibil ca să ﬁe nevoie să se intervină cu algoritmi de corecție după
aplicarea unor astfel de operatori. Din punct de vedere practic, abordarea
prin algoritmi genetici este conﬁrmată ca o metodă funcțională de către mai
mulți autori.
6Dar nimic nu ne împiedică să concepem alți operatori.
127

Capitolul 11
Mulțimi și logică fuzzy
11.1 Prezentare generală
Capitolul conține o introducere a logicii fuzzy și mulțimilor fuzzy1. Do-
meniilevizeazămodelareaincertitudiniidinlumeareală,raționamentulapro-
ximativ, imprecizia în exprimare. Majoritatea conceptelor folosite în lumea
reală sunt neclare, vagi, ambigue, dar cu toate aceste oamenii operează cu
ele foarte bine.
Termenul de “fuzzy” a fost introdus de către Lotﬁ A. Zadeh, profesor la
University of California at Berkley, în lucrarea sa “Fuzzy Sets” [16]. Mul-
țimile fuzzy – sau mulțimile nuanțate – se bazează pe conceptul de grad
de apartenență 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 asig-
nând grade de apartenență ﬁe 0, ﬁe 12. Într–o mulțime fuzzy, gradul de
apartenență se exprimă printr-o funcție cu valori în intervalul [0,1].
Alăturideteoriaprobabilităților, sistemelefuzzysuntfolositepentrumo-
delarea incertitudinii. Incertitudinea existentă în ceea ce privește rezultatul
aruncării unui zar este modelată prin variabile aleatoare – urmărindu-se de-
terminarea probabilităților asociate diferitelor valori, sau comportamentul
obținut prin repetarea experimentelor etc. Tipul de incertitudine pe care îl
abordează sistemele fuzzy este însă diferit. De exemplu, propoziția “Maria
este destul de înaltă” nu are o incertitudine de tip statistic în ea: nu este
vorba de evenimente aleatoare repetate sau condiționări probabiliste. Ca-
racterul 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
stare cunoscută și una posibil inﬂuențată de ea.
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ă deﬁnită pentru o submulțime Aa lui
X:
fA(x) =/braceleftbigg
1dacăx∈A
0dacăx∈X\A
128

Insistând pe direcția aceasta, putem aﬁrma 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,
atuncivaploua”realizămcăenunțulestevag, celpuțindincauzaurmătoare:
noțiunea de înnorat este vagă – rareori cerul este în totalitate acoperit de
nori; 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 ﬁ utilizabilă doar
pentru cazul în care cerul e complet acoperit de nori. Chiar și “ploaia” poate
ﬁ nuanțată – picură, plouă torențial etc.
Logica fuzzy este asociată deci cu incertitudinea nestatistică. Trăsătura
esențială a teoriei mulțimilor și a logicii fuzzy este manipularea riguroasă a
incertitudinii. Se pun la dispoziție modalități de deﬁnire, descriere și analiză
a caracteristicilor vagi.
11.2 Teoria mulțimilor fuzzy
În teoria clasică a mulțimilor, un element ﬁe face parte dintr-o mulțime,
ﬁe nu. În mulțimile fuzzy însă, apartenența la o mulțime se exprimă printr–
un grad de apartenență, pentru care valoarea este un număr cuprins între 0
și1. Putemvedeaaceastacaogeneralizareamulțimilorclasice: dacăunele-
ment aparț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, putem
spune 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 de
1.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.60 m sau mai
puțin nu mai poate ﬁ 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țime pentru elementele în discuție. Să considerăm tabelul 11.1 în care
pentru diferite exemple de înălțimi vom speciﬁca gradul de apartenență la
mulțimea considerată. Mulțimea oamenilor înalți este considerată din acest
moment o mulțime fuzzy (nuanțată).
Observăm că o mulțime fuzzy se poate speciﬁca prin perechi de elemente
de grad de apartenență/element. O notație mai compactă pentru tabelul
11.1 este:
Înalt ={1/2.10,0.8/2,0.6/1.90,0.4/1.80,0.2/1.70,0/1.60}
129

Persoană Înălțime Grad de apartenență
A 2.10 m 1
B 2 m 0.8
C 1.90 m 0.6
D 1.80 m 0.4
E 1.70 m 0.2
F1.60 m 0.0
Tabela11.1: Înălțimișigraduldeapartenențălamulțimeafuzzyaoamenilor
înalți.
Valorile extreme 0 și 1 se pot interpreta astfel: dacă µA(x) = 1atunci
spunem că xcu certitudine aparține lui A, dacăµA(x) = 0atuncixcu
certitudine nu aparține lui A.
O altă variantă este speciﬁcarea unei funcții de apartenență µA(x), unde
µAeste o funcție cu valori în intervalul [0,1],Aeste o mulțime fuzzy, x
este un element din universul discursului pentru care se stabilește gradul de
apartenență la mulțimea A. Astfel,µÎnalt(2.10 m ) = 1,µÎnalt(1.90 m ) = 0.6
etc.
Funcțiile de apartenență se pot reprezenta graﬁc, pe axa orizontală ﬁ-
ind valori al elementelor, iar pe verticală valoarea funcției de apartenență,
precum în ﬁgurile 11.1 sau 11.2.
Figura 11.1: Reprezentarea graﬁcă a funcției de apartenență pentru mulți-
mea “înalt”
Formele poligonale date în graﬁcele din ﬁgura 11.1 și 11.2 nu sunt singu-
rele care se pot folosi. Se poate de exemplu utiliza o funcție de tip Gaussian
pentru modelarea gradului de apartenență:
µCald(T) =e−(T−25)2
50
undeTeste 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 com-
portament bun; eventuala lor nederivabilitate nu este o problemă. Din ra-
țiuni evidente, spunem că funcția din ﬁgura 11.2 este triunghiulară.
130

Figura 11.2: Reprezentarea graﬁcă a funcției de apartenență pentru mulți-
mea “cald”
Î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.75 metri face parte
din mulțimea oamenilor înalți în măsura 0.33și totodată aparține mulțimii
oamenilor de înălțime medie în măsura 0.45 – a se vedea graﬁcele din ﬁgura
11.3. Remarcăm că noțiunile nu se exclud reciproc.
Figura 11.3: Valorile fuzzy “Mediu” și “Înalt” reprezentate pe același graﬁc
11.3 Operații cu mulțimi fuzzy
Raționamentul presupune operații logice; o mare parte din noțiunile și
operațiile din algebra booleană au fost preluate și adaptate la logica fuzzy.
Înainte de a deﬁni aceste operații, este cazul să enumerăm două parado-
xuri din logica binară:
1. (Paradoxulmincinosului,paradoxulcretanului)Opersoanăspune: “eu
mint”. Dacă presupunem că această propoziție este adevărată, atunci
înseamnă că spusele persoanei sunt false, deci de fapt ea nu minte,
3Valoarea exactă se aﬂă intersectând o dreaptă verticală care trece prin valoarea 1.75
de pe abscisă cu graﬁcul funcției de apartenență.
131

ceea ce e o contradicție cu presupunerea inițială. Dacă presupunem
că aﬁrmația persoanei este falsă, atunci înseamnă că dimpotrivă, per-
soana nu minte, deci din nou contradicție cu presupunerea noastră.
Oricare din cele două valori de adevăr am vrea să asociem aﬁrmației
“eu mint”, ajungem la o contradicție. Ori, cum doar una din valorile
Adevărat și Fals pot ﬁ asociate unei propoziții4, avem un paradox.
2. (Paradoxul bărbierului) Într–un sat există un bărbier care barbierește
pe toți bărbații care nu se bărbieresc singuri. Care este valoarea de
adevă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 din
cele două valori de adevăr nu pot ﬁ asociate propoziției, pentru că s–ar
ajunge la contradicție.
Aceste probleme sunt rezolvate de către logica fuzzy, putându–se da valori
de adevăr pentru propozițiile discutate. Intuitiv, pentru ambele aﬁrmații
am putea spune că ele sunt tot atât de adevărate pe cât sunt de false.
Vom trece acum la deﬁnirea operațiilor pentru mulțimi fuzzy. Deﬁniț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 aceleași
elemente. Pentru că o mulțime fuzzy înseamnă elemente cu grad de aparte-
nență la ea, spunem că două mulțimi fuzzy sunt egale dacă pentru domenii
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 Aeste o submulțime a mulțimii
Bdacă orice element din Ase găsește și în B. Pentru cazul mulțimilor
fuzzy, folosim următorul exemplu ca suport intuitiv pentru deﬁnirea inclu-
ziunii: mulțimea oamenilor foarte înalți este inclusă în mulțimea oamenilor
înalți. Evident, pentru un element xpentru care µfoarte înalt (x) =m, valoa-
rea asociată lui față de de mulțimea oamenilor înalți este cel puțin la fel de
mare:µînalt(x) =m+ε,ε≥0. Ca atare, spunem că mulțimea fuzzy Aeste
inclusă în mulțimea fuzzy Bdacă cele două mulțimi conțin aceleași elemente
șiµA(x)≤µB(x),∀x. Desigur, și alte deﬁniții sunt posibile.
11.3.3 Complementara unei mulțimi fuzzy
În teoria clasică a mulțimilor, complementul unei mulțimi Aeste mulți-
mea formată din toate elementele care nu aparțin lui A.
4Conform principiului terțului exclus, a treia variantă nu este posibilă.
132

Pentrudeﬁnițiarelativlamulțimifuzzy, pornimdelaunexemplu: consi-
derăm mulțimea oamenilor de înălțime medie, pentru care funcția de apar-
tenență este dată în ﬁgura 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.75 m,
evident că face parte din mulțimea oamenilor de înălțime medie; dacă are
1.90 m sau 1.80 m, atunci e evident că nu face parte din ea. Pentru o per-
soană pentru care gradul de apartenență la mulțimea oamenilor de înălțime
medie este, să spunem, 0.3, pare rezonabil să spunem că ea nu aparține
la această mulțime cu măsura 1−0.3 = 0.7. Putem deci deﬁni valoarea
de apartenență a complementului mulțimii ca ﬁind unu minus valoarea de
apartenență la mulțime. Desigur, și alte deﬁniții sunt posibile.
Deﬁniția dată contrazice principiul terțului exclus: in logica clasică se
spune că ceva ﬁe este A, ﬁe este non-A. Gradul de adevăr pentru aﬁrmațiile
discutate în cele două paradoxuri poate ﬁ luat 0.5, deci ﬁecare propoziție
are aceeaș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ă
din elementele comune celor care se intersectează.
Deﬁnirea pentru mulțimi fuzzy nu este unică; oricare ar ﬁ varianta folo-
sită, trebuie să se respecte următoarele:
1. operația să ﬁe 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 o
mulț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țimi
determină gradul de apartenență la intersecție. Varianta de operator de
intersecție dată de către Zadeh este:
µA∩B(x) = min{µA(x),µB(x)}
Se poate arăta ușor că dacă A⊂B, atunciA∩B=A, în sens fuzzy, ceea
ce este în concordanță cu ceea ce avem și în teoria clasică a mulțimilor.
Desigur, și alte deﬁniț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țime
formată din toate elementele care se regăsesc în ele. Pentru deﬁnirea relativ
la mulțimi fuzzy, se iau în considerare proprietăți similare cu cele de la
133

intersecție (doar la monotonie apare diferența), iar varianta dată de către
Zadeh este:
µA∪B(x) = max{µA(x),µB(x)}
Se pot da și alte deﬁniții pentru acest operator.
11.3.6 Operatori de compensare
În timp ce operațiile din cadrul teoriei clasice a mulțimilor sunt unic
deﬁnite, pentru mulțimile fuzzy există și alte posibilități de deﬁnire a lor
decât cele date mai sus. Operatorii de compensare tratează în special cazul
reuniunii și al interseției de mulțimi fuzzy. Intersecția este des întâlnită în
cadrul regulilor fuzzy.
Folosind deﬁniț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 atunci
D”, 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 ﬁnal este prea pronunțat. În
practică, deﬁniția intersecției dată de Zadeh nu e întotdeauna adecvată.
S–au deﬁnit mai mulți operatori de compensare. Ei formulează răspun-
suri la întrebarea: cât de mult poate să compenseze creșterea unor variabile
valorile mici ale altora? Vom prezenta două variante ale acestor operatori:
operatorul de medie și operatorul gama.
Prinoperatoruldemediesestabileștecăvaloareafuncțieideapartenență
este media valorilor individuale:
µX1∩X2∩···∩Xn(x) =n/summationtext
i=1µXi(x)
n
Operatorulgamaestemaicomplexșiparesăreprezintemaibineprocesul
de decizie umană decât deﬁnițiile lui Zadeh. El este deﬁnit ca:
µγ=/parenleftBiggn/productdisplay
i=1µi/parenrightBigg1−γ
·/parenleftBigg
1−n/productdisplay
i=1(1−µi)/parenrightBiggγ
unde 0≤γ≤1, iarneste 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șiA2și···șiAnatunciC
unde “A1șiA2și···șiAn” se numește antecedent sau premisă iar Ceste
consecvent sau consecință sau concluzie. De exemplu:
134

Dacă înălțimea bărbatului este mai mare de 1.80 m, atunci masa lui este
mai mare 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 datorate
lui Mamdani:
DacăX1esteA1și …șiXnesteAnatunciYesteB
și respectiv lui Takagi, Sugeno și Kang:
DacăX1esteA1și …șiXnesteAnatunciY=p0+p1X1+···+pnXn
undeXisunt variabile fuzzy de intrare, Aisunt mulțimi fuzzy peste varia-
bileleXi(1≤i≤n),Yeste o variabilă fuzzy de ieșire, Beste o mulțime
fuzzy deﬁnită peste valorile lui Yiarpjsunt coeﬁcienți reali ( 0≤j≤n).
Pentru probleme de clasiﬁcare există următoarea formă de regulă:
DacăX1esteA1și …șiXnesteAnatunciYface parte din clasa iîn
măsuraGCi.
Nuanțarea5estepasulprincaresecombinăvaloriledinantecedentulunei
reguli, folosind operațiile cu mulțimi fuzzy; pasul se aplică pentru ﬁecare
regulă în parte. Prin combinarea regulilor date la pas de denuanțare se
obține o ieșire care poate ﬁ folosită ca rezultat inferențial sau ca indicație
de control al unui sistem.
Exempliﬁcarea acestor reguli se face pentru cazul unei centrale de în-
călzire, 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 se folosesc noțiuni vagi (temperatură potrivită, variație mare, mărește
debitul etc.) ș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 ), modiﬁcarea de temperatură
interioară în ultimele 5 minute ( DeltaTempIn ); ca valoare de ieșire avem
ModificareDebit . Fiecare valoare de intrare concretă va avea un grad de
apartenență fuzzy la diferite mulțimi (de exemplu, pentru TempIn avem
apartenență la mulțimi precum rece,confortabil etc.
Pentru valoarea TempIn avem trei mulțimi fuzzy: rece,confortabil ,prea
cald. PentruTempExt avem mulțimile fuzzy foarte rece ,rece,cald,foarte
caldșiﬁerbinte. PentruDeltaTempIn deﬁnim mulțimile fuzzy: larg ne-
gativ,mic negativ ,aproximativ zero ,pozitiv mic ,larg pozitiv6, iar pentru
ModificareDebit avem seturile fuzzy scade mult ,scade puțin ,nu schimba ,
crește puțin ,crește mult .
Vom considera doar câteva reguli, suﬁciente pentru exempliﬁcarea nu-
anțării și denuanțării:
Regula 1: DacăTempIn esteconfortabilă șiDeltaTempIn esteaproxima-
tiv zero, atunciModificareDebit estenu schimba ;
5În original: fuzzyﬁcation.
6“Mic” și “larg” se referă la valorile absolute (modulul) cantităților măsurate.
135

Regula 2: DacăTempExt estereceșiDeltaTempIn estemic negativ ,
atunciModificareDebit estecrește puțin ;
Regula 3: DacăTempIn esteprea cald șiDeltaTempIn estelarg pozitivă ,
atunciModificareDebit estescade mult ;
Regula 4: DacăTempIn estereceșiDeltaTempIn esteaproximativ zero ,
atunciModificareDebit estecrește puțin .
PentruTempIn,mulțimea confortabil sedeﬁneșteca{0/15◦,1/21◦,0/27◦},
interpretată ca o funcție de apartenență de tip triunghiular. De exem-
plu, pentru 18◦și24◦gradele de apartenență sunt ambele 0.5. Pentru
receavem mulțimea fuzzy {1/10◦,1/16◦,0/21◦}, iarprea cald este mulți-
mea{0/21◦,1/27◦,1/33◦}.
PentruDeltaTempIn :
negativmic ={0/−4◦,1/−2◦,0/0◦}
aproapezero ={0/−2◦,1/0◦,0/+ 2◦}
largpozitiv ={0/2◦,1/4◦,1/6◦}
PentruTempExt ,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:
•pentruTempIn,µrece(20◦) = 0.25,µconfortabil (20◦) = 0.75,µpreacald (20◦) =
0;
•pentruDeltaTempIn ,µmicnegativ (−1.5◦) = 0.80,µaproximativzero (−1.5◦) =
0.20,µlargpozitiv (−1.5◦) = 0
•pentruTempExt ,µrece(11◦) = 0.90
Aplicăm aceste valori celor 4 reguli fuzzy de mai sus. Ținem cont de
faptul că antecedentele din reguli sunt exprimate cu conjuncție, corespun-
zătoare interseției de mulțimi, ceea ce în logica fuzzy se implementează prin
funcția min. Obținem:
Regula 1: 0.75∩0.20 = 0.20 =µnuschimba (ModificareDebit )
Regula 2: 0.90∩0.80 = 0.80 =µcresteputin (ModificareDebit )
Regula 3: 0∩0 = 0 =µscademult (ModificareDebit )
Regula 4: 0.25∩0.20 = 0.20 =µcresteputin (ModificareDebit )
136

Activarea acestor reguli se face în paralel. Observăm că pentru regula a
treia ieșirea este zero, deci ea nu se va aplica. Din regulile 2 și 4 avem două
valori pentru apartenența µcresteputin (ModificareDebit ); se va lua maximul
celor două valori, deci µcresteputin (ModificareDebit ) = 0.8.
Variația de debit este modelată la rândul ei fuzzy, așa cum se arată în
ﬁgura 11.4.
1
−3 −2 −1 0 2Scade putin Scade mult
1Nu schimba Creste putin Creste multµ
(m cubi/sec) variatie debit
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
problemă, adică se furnizează o valoare exprimată în metri cubi pe secundă
pentru debitul de gaz. Plecând de la graﬁcul anterior, se trasează conturul
mărginit de orizontalele y= 0.2- pentru nu schimba – șiy= 0.8- pentru
crește puțin . Se obține ﬁgura geometrică desenată cu linie continuă în ﬁgura
11.5, pentru care se determină centrul de greutate; verticala dusă prin acest
centru de greutate interesectează axa debitului la valoarea +0.76, aceasta
ﬁind indicația dată regulatorului de gaz: crește cu 0.76m3/s debitul de gaz.
Există mai multe metode care se pot folosi pentru denuanțare; a se vedea
[5] 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 de
nuanțată? Pentru o mulțime fuzzy discretă, se pot introduce câteva măsuri
care cuantiﬁcă gradul de nuanțare. Acestea au ca scop măsurarea gradu-
lui de incertitudine, care apare, de exemplu, în cazul exprimării vagi. În
continuare, prezentarea merge pe exemplele din [5].
Dacă considerăm mulțimea peștilor, atunci pentru diferite elemente de
mai jos avem gradele exprimate: µpești(biban ) = 1.0,µpești(peștisor auriu ) =
137

1
−3 −2 −1 0 2Scade putin Scade mult
1Nu schimba Creste putin Creste multµ
0.76
(m cubi/sec) variatie debitFigura 11.5: Procesul de denuanțare.
1.0,µpești(căluț de mare ) = 0.8,µpești(balenă ) = 0.0. Pentru mulțimea
fuzzyﬂori, gradul de apartenență ar putea ﬁ: µflori(trandaﬁr ) = 1.0,
µflori(pâine ) = 0.0,µflori(lemn câinesc ) = 0.5. Intuitiv, putem spune că
mulțimea de ﬂori exempliﬁcată este mai vagă decât mulțimea peștilor: în
ultimul caz, valorile de apartenență sunt mai apropiate de cele ale unei func-
ții de apartenență din cazul unei mulțimi clasice, 0 și 1.
Se preia din ﬁzică și din teoria informației noțiunea de entropie, care
măsoară gradul de dezorganizare a unui sistem. Spre deosebire de teoria
informației unde măsura entropiei este unic determinată7, în teoria mulți-
milor fuzzy sunt mai multe variante acceptate. Se pleacă de la o sumă de
proprietăți pe care ar trebui să le respecte o astfel de măsură entropică și se
introduc mai multe funcții care respectă o parte sau toate aceste proprietăți.
De exemplu, pentru o mulțime clasică, din care un element ﬁe face parte, ﬁe
nu, măsura gradului de nuanțare ar trebui să dea rezulatul 0 – i.e.o mul-
țime clasică nu este vagă. De asemenea, cu cât sunt mai multe valori pentru
care valoarea funcției de apartenență este 0.5 sau apropiată de aceasta, cu
atât mulțimea este mai vagă: un element care aparține cu măsura 0.5 la o
mulțime fuzzy 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 între
două mulțimi fuzzy: spunem că o mulțime S∗estemai ascuțită decât o altă
mulțime fuzzy S– ambele deﬁnite 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.5valoareaµS∗(x)poate ﬁ oricât.
Proprietățile de mai jos sunt punct de plecare pentru determinarea dife-
7Abstracție făcând de o constantă multiplicativă
138

ritelor funcții de măsurare a gradului de nuanțare.
caracterul exact: H(A) = 0dacă și numai dacă Aeste o mulțime clasică;
maximalitatea: H(A)este maximă dacă µA(x) = 0.5,∀xdin universul
discursului;
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ă de
DeLuca și Termini și care respectă toate cele 5 proprietăți de mai sus este:
HDT(A) =−Kn/summationdisplay
i=1(µilogµi+ (1−µi) log(1−µi))(11.1)
undeKeste un număr pozitiv oarecare. Varianta introdusă de Pal și Pal
este:
HPP(A) =Kn/summationdisplay
i=1/parenleftBig
µie1−µi+ (1−µi)eµi/parenrightBig
(11.2)
Se pot deﬁni și alte variante de măsurare a gradului de nuanțare a unei
mulțimi vagi.
139

Bibliograﬁe
[1]Stanford Machine Learning , curs online, Coursera, Andrew Ng
[2]Neural network design , 2nd edition, Martin T. Hagan, Howard
B. Demuth, Mark Hudson Beale, Orlado de Jesús, 2014,
http://hagan.okstate.edu/NNDesign.pdf
[3]Deep Learning , Ian Goodfellow, Yoshua Bengio, Aaron Courville, Mor-
gan Kaufmann, 2007, https://www.deeplearningbook.org
[4] MichaelA.Nielsen, Neural Networks and Deep Learning ,Determination
Press, 2015, http://neuralnetworksanddeeplearning.com
[5]Computational Intelligence. Concepts to Implementations , Russell C.
Eberhart, Yuhui Shi, Morgan Kaufmann, 2007
[6]Computational Intelligence. An Introduction , Andries P. Engelbrecht,
John Willeys and Sons, 2007
[7]Neural Networks and Learning Machines , ediția a treia, Simon Haykin,
Prentice Hall, 2008
[8]Inteligență computațională , Răzvan Andonie, Angel Cațaron, Universi-
tatea Transilvania din Brașov, online
[9]An Elementary Introduction to Statistical Learning Theory , Sanjeev
Kulkarni, Gilbert Harman, Willey, 2011
[10]A Brief Introduction to Neural Networks , David Kriesel, 2007,
http://www.dkriesel.com/en/science/neural_networks
[11]Self-Organized Formation of Topologically Correct Feature Maps , Teuvo
Kohonen, 1982, în Biological Cybernetics 43 (1), pp. 59–69
[12]Self-Organizing Maps , Kohonen, T., Springer Berlin Heidelberg, 2001
[13]Principiile inteligenței artiﬁciale , Dan Dumitrescu, Editura Albastră
[14]Algoritmi genetici și strategii evolutive – aplicații în inteligența artiﬁci-
ală, Dan Dumitrescu, Editura Albastră
140

[15]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
[16]Fuzzy Sets , Lotﬁ Zadeh, Information and Control, Vol. 8, 1965
[17]Genetic Algorithms + Data Structures = Evolution Programs , Zbigniew
Michalewicz, 1996, Ed. Springer-Verlag
[18]Introduction to artiﬁcial neural networks , Jacek M. Zurada, 1992, West
Publishing Company
[19]K-means++: the advantages of careful seeding , Arthur, D. and Vas-
silvitskii, S., Proceedings of the eighteenth annual ACM-SIAM sympo-
sium on Discrete algorithms, pp. 1027–1035
[20]Fuzzy ARTMAP: A Neural Network Architecture for Incremental Su-
pervised Learning of Analog Multidimensional Maps, , G. A. Carpenter
and S. Grossberg and N. Markuzon and J. H. Reynolds and D. B. Ro-
sen, IEEE Transactions on Neural Networks, 1992, vol. 3, no. 5, pp.
698–713
[21]The Matrix Cookbook , Kaare Brandt Petersen, Michael Syskind Peder-
sen, 2012, Technical University of Denmark
[22]Adaptive Subgradient Methods for Online Learning and Stochastic Op-
timization , John Duchi, Elad Hazan, Yoram Singer, Journal of Machine
Learning Research (12), pp. 2121–2159, 2011
[23]ADADELTA: An adaptive learning rate method , Matthew D. Zeiler,
arXiv:1212.5701, 2012
[24]Learning representations by back-propagating errors , David E. Rume-
lhart, Geoﬀrey E. Hinton, Ronald J. Williams, Nature 323 (6088), pp.
533–536, 1986
[25] Diederik P. Kingma, Jimmy Ba, Adam: A Method for Stochastic Opti-
mization , http://arxiv.org/abs/1412.6980, 2014
[26]Deep Learning , Ian Goodfellow, Yoshua Bengio, Aaron Courville, MIT
Press, 2016
[27] Xavier Glorot, Yoshua Bengio, Understanding the diﬃculty of training
deep feedforward neural networks , ProceedingsoftheInternationalCon-
ference on Artiﬁcial Intelligence and Statistics (AISTATS’10). Society
for Artiﬁcial Intelligence and Statistics, 2010
141

[28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun, Delving Deep
into Rectiﬁers: Surpassing Human-Level Performance on ImageNet
Classiﬁcation , Proceedings of the 2015 IEEE International Conference
on Computer Vision (ICCV), 2015
142

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: Inteligență artiﬁcială [607689] (ID: 607689)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

Inteligență artiﬁcială [607689]

Copyright Notice

PENTRU OBȚINEREA GRADULUI DIDACTIC I COORDONATOR ȘTIINȚIFIC: Lect.univ.dr. ADRIAN CURCAN PROPUNĂTOR: Înv. LUPU (CONEA) OLGUȚA DANIELA ȘCOALA… [307078]

INTRODUCERE ………………………….. ………………………….. ………………………….. ……2 CAPITOLUL I : COMERȚUL –… [624126]

Acordarea unui credit ipotecar unei persoane fizice [605884]

Aspecte privind imbunatatirea performantelor [619527]

CAPITOLUL 1.MOTIVAȚIA – IPOSTAZĂ A COMPORTAMENTULUI ÎN ORGANIZAȚII Angajații își vând timpul în schimbul salariului. Cei mai mulți dintre noi muncesc… [624794]

Pictura Bizantină În Locaşurile De Cult Din Nordul Moldovei [305982]

Copyright Notice

Similar Posts