Inteligenta artificiala: masini cu vectori suport 9786066871556 [PDF]

Zitiervorschau

Cuprins Capitolul 1. Reţele neuronale cu un singur strat 1.1. Neuronii biologici .........................................................................................7 1.2. Perceptronul ................................................................................................ 12 1.2.1. Neuronul McCulloch-Pitts .......................................................... 12 1.2.2. Perceptronul originar al lui Rosenblatt ............................... .13 1.2.3. Perceptronul standard ................................................................ 14 1.2.4. Regula de învăţare a perceptronului ..................................... 19 1.3. Adaline. Regula delta ................................................................................ 30 Capitolul 2. Noţiuni de teoria învăţării 2.1. Probleme de filosofia învăţării ............................................................. 35 2.2. Învăţarea probabil aproximativ corectă ........................................... 37 2.3. Dimensiunea Vapnik-Chervonenkis ................................................... 48 2.4. Riscul empiric şi riscul structural ........................................................ 58 Capitolul 3. Probleme separabile liniar 3.1. Introducere .................................................................................................. 63 3.2. Hiperplane de separare liniare. Marginea dintre clase ............... 63 3.3. Problema de optimizare .......................................................................... 73 3.4. Minimizarea riscului structural de către maşinile cu vectori suport.. 74

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange 4.1. Problema primară ..................................................................................... 77 4.2. Problema duală ........................................................................................... 83 4.3. Perspectiva geometică ............................................................................. 88 4.4. Formalizarea problemei de optimizare ............................................ 94 4.5. Particularizarea pentru maşinile cu vectori suport ..................... 96 Capitolul 5. Nuclee 5.1. Transformarea în trăsături ................................................................. 107 5.2. Teorema lui Mercer................................................................................ 111 5.3. Tipuri de nuclee ....................................................................................... 112 5.3.1. Nucleul polinomial ..................................................................... 112 5.3.2. Nucleul gaussian ......................................................................... 116 5.3.2. Nucleul sigmoid .......................................................................... 118 Capitolul 6. Probleme neseparabile liniar 6.1. Margini flexibile....................................................................................... 121 6.2. Exemple ...................................................................................................... 124 Capitolul 7. Algoritmul SMO 7.1. Optimizarea diferenţială a unei funcţii........................................... 133 7.2. Rezolvarea problemei duale pentru maşini cu vectori suport .. 136 7.3. Optimizarea comună a unei perechi de multiplicatori ............. 138 7.4. Determinarea multiplicatorilor pentru optimizare ................... 142 7.5. Determinarea pragului ......................................................................... 144 7.6. Pseudocodul algoritmului SMO ......................................................... 146 7.7. Exemplu de aplicare .............................................................................. 150

4 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii 8.1. Probleme de regresie ............................................................................ 157 8.2. Probleme de clasificare cu clase multiple ..................................... 160 8.2.1. Abordarea „una versus toate” ............................................... 160 8.2.2. Abordarea „toate versus toate” ............................................. 161 8.3. Exemple ...................................................................................................... 162 8.3.1. Abordarea „una versus toate” ............................................... 164 8.3.2. Abordarea „toate versus toate”............................................. 166 8.4. Concluzii ..................................................................................................... 168 Referinţe .................................................................................................................... 171

5 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1

Reţele neuronale cu un singur strat 1.1. Neuronii biologici Neuronii sunt componentele fundamentale ale sistemului nervos, a cărui complexitate este extraordinară. Creierul uman are în medie 86 de miliarde de neuroni (Herculano-Houzel, 2009). În figura 1.1 (Monoyios, 2011) se poate vedea fotografia unui neuron real. Numele vine din limba greacă, νευρών însemnând tendon, adică un fascicul subțire şi rezistent cu ajutorul căruia se fixează mușchii pe oase. S-a considerat că nervii au aspectul unor tendoane. Neuronii mai sunt numiţi uneori şi celule nervoase, deşi mulţi neuroni nu formează nervi iar nervii includ şi alte celule decât neuroni. Diametrul unui neuron este de 4-100 microni iar greutatea sa nu depăşeşte 10-6 grame (Groves & Rebec, 1988; Chudler, 2014). Simplificând puţin lucrurile, un neuron este alcătuit din corpul celular, dendrite (din gr. δένδρον, copac), terminaţii cu aspect arborescent care primesc impulsuri de la alţi neuroni şi un axon (din gr. ἄξων, axă), care trimite impulsuri electrice către alţi neuroni, după cum se poate vedea în figura 1.2 (adaptată după Droual, 2011). Neuronii sunt conectaţi prin sinapse (din gr. σύν, cu, împreună şi ἅπτω, a prinde, a fixa cu derivatul ἅψᾱ, legătură). În scoarţa cerebrală există 150 de trilioane de sinapse (Pakkenberg & Gundersen, 1997; Pakkenberg et al., 2003; Chudler, 2014). Un neuron se conectează cu alţi 1000-10000 de neuroni, în medie 7000.

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Figura 1.1. Neuron biologic real

Dendrite Corp celular Nucleu

Butoni terminali Direcţia semnalului

Con de emergenţă Axon Neuron presinaptic Sinapsă Dendrite

Buton terminal

Neuron postsinaptic

Neurotransmiţători Butoni terminali Axon

Figura 1.2. Structura neuronilor. Sinapsă chimică

8 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

Atât în interiorul cât şi în exteriorul celulelor neuronale se găsesc ioni pozitivi şi negativi. Schimbările de concentraţie ale acestora determină apariţia unor curenţi electrici sau impulsuri nervoase. Transmiterea de la un neuron la altul a acestor impulsuri se face prin intermediul sinapselor, unidirecţional de la axoni la dendrite (deşi există şi alte combinaţii posibile). De fapt, neuronii nu se ating direct, există o regiune foarte îngustă, de aproximativ 20 nm între membranele pre- şi postsinaptice, numită fantă sinaptică. Transferul impulsurilor se realizează prin intermediul unor substanţe chimice şi nu prin curenţi electrici. Acesta este cel mai des întâlnit tip de sinapsă, numit sinapsă chimică. Atunci când impulsul electric ajunge într-un buton terminal al axonului presinaptic, acesta atrage ioni pozitivi de calciu care determină „vărsarea” în fanta sinaptică a unor neurotransmiţători. Aceştia activează unii receptori în partea postsinaptică şi determină depolarizarea neuronului postsinaptic, adică potenţialul membranei devine pozitiv deoarece în celulă intră ioni pozitivi de sodiu. Dacă depolarizarea atinge un anumit nivel, în celulă se propagă un impuls nervos. Unii neurotransmiţători, dimpotrivă, fac ca neuronul postsinaptic să se hiperpolarizeze, adică potenţialul membranei să devină negativ. Ionii negativi de clor intră în celulă iar ionii pozitivi de potasiu ies din celulă. Acest fapt împiedică generarea unui impuls electric. În primul caz, potenţialul sinaptic este excitator; în al doilea caz, este inhibitor. În scurt timp după eliberarea în fanta sinaptică, neurotransmiţătorii sunt dizolvaţi de enzime sau reabsorbiţi în butonii presinaptici, iar concentraţia de ioni revine la valoarea iniţială. Imediat după generarea unui impuls urmează o aşa numită perioadă refractară, în care neuronul „se

9 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

încarcă” şi nu se mai poate activa din nou. Abia apoi neuronul revine în starea de repaus şi poate genera un nou impuls. Neuronii au un prag de depolarizare. Dacă potenţialul creat este mai mic decât acest prag, neuronul postsinaptic nu se activează. Potenţialul creat de o sinapsă excitatoare este mult mai mic decât pragul de depolarizare, prin urmare un impuls poate fi generat doar prin efectul combinat al mai multor sinapse. Dintre miile de terminaţii sinaptice care sunt conectate la un neuron, câteva sute sunt active simultan sau la intervale de timp suficient de apropiate ca efectele lor să se poată însuma. Potenţialul membranar al neuronului postsinaptic este în fiecare moment rezultanta activităţii tuturor sinapselor active în acel moment. În figura 1.2 se poate observa formaţiunea denumită con de emergenţă al axonului. Acesta este ultimul loc din corpul celular unde potenţialele din intrările sinaptice se sumează înainte de a fi transmise axonului. Neuronul respectă principiul totul sau nimic. Dacă depolarizarea nu este suficient de puternică pentru a depăşi pragul, canalele de ioni nu se deschid. Dacă depolarizarea depăşeşte pragul, canalele se deschid şi se generează un impuls electric. Acesta este întotdeuna la fel de mare, de exemplu 40 mV, fără valori intermediare. Intensitatea unui stimul este dată de frecvenţa impulsurilor. Unui stimul mai puternic îi corespunde o frecvenţă mai mare. De exemplu, un stimul de durere puternică poate avea o frecvenţă de până la 800 Hz (Malmivuo & Plonsey, 1995; Freudenrich, 2007; Mastin, 2010; Ribrault, Sekimoto & Triller, 2011; Tamarkin, 2011; Gregory, 2014). Acest principiu poate fi descris prin analogie cu aprinderea unui fitil, care necesită o anumită temperatură. Sub aceasta, fitilul nu se aprinde. Însă

10 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

un chibrit cu o temperatură mai mare decât pragul nu face fitilul să ardă mai repede, odată ce s-a aprins (Byrne, 2014). În figura 1.3 (după Wikimedia Commons, 2014a) se prezintă un impuls tipic, unde se pot vedea şi valorile curenţilor propriu-zişi şi ale pragului.

e rizar

Prag

la Repo

Depo lariza re

Tensiune (mV)

Impuls

Iniţieri eşuate

Stare de repaus Perioadă refractară

Timp (ms)

Figura 1.3. Impuls neuronal tipic

Un alt principiu biologic pe care se bazează o modalitate adaptivă de învăţare numită învăţare hebbiană (Hebb, 1949) este acela că dacă un neuron activează în mod repetat alt neuron, apar modificări fizice care cresc eficienţa acestei interacţiuni. Pe scurt, „neuronii care se activează împreună se cablează împreună” (engl. “neurons that fire together wire together”, Shatz, 1992; Doidge, 2007). Cu alte cuvinte, conexiunea dintre neuronii respectivi se întăreşte iar impulsurile se transmit mai uşor. De aceea, dacă repetăm de suficient de multe ori o acţiune, ajungem să o realizăm în mod automat (Ware, 2013).

11 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

1.2. Perceptronul 1.2.1. Neuronul McCulloch-Pitts

Primul model matematic al unui neuron a fost propus de McCulloch şi Pitts (1943; 1947). Modelul este prezentat în figura 1.4 (Ngom, 2010).

Figura 1.4. Neuronul McCulloch-Pitts

Ieşirea este binară: neuronul este activat (1) sau nu (0), ceea ce îl face echivalent cu o propoziţie logică, care poate fi adevărată sau falsă. Intrările sunt excitatoare (ai) sau inhibitoare (bj). Aceste intrări sunt sumate direct şi neuronul se activează dacă suma depăşeşte un prag fix. De asemenea, neuronul se activează doar dacă nu există intrări inhibitoare. Funcţia de activare este următoarea:

(1.1)

12 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

Orice problemă care poate fi reprezentată sub forma unei funcţii logice poate fi modelată de o reţea de neuroni McCulloch-Pitts deoarece orice funcţie booleană poate fi implementată folosind doar operaţiile SAU, ŞI şi NEGAŢIE. În figura 1.5 (după Ngom, 2010) sunt prezentate aceste funcţii logice elementare.

Figura 1.5. Funcţii logice elementare implementate ca neuroni McCulloch-Pitts

Dificultatea principală a modelului constă în faptul că îi lipseşte capacitatea de învăţare; pragurile sunt determinate analitic. Pentru funcţii complexe, dimensiunea reţelei corespunzătoare este mare.

1.2.2. Perceptronul originar al lui Rosenblatt

Problema cea mai importantă pe care a încercat să o rezolve Rosenblatt (1957; 1958) este posibilitatea de a învăţa, o calitate esenţială a reţelelor neuronale biologice. Sistemul propus de el modela sistemul vizual uman, de aceea s-a numit perceptron (figura 1.6). Dintr-o imagine raster, valorile pixelilor treceau prin nişte conexiuni cu valori aleatorii, rezultând 13 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

nişte trăsături sintetice ale imaginii. Aceste trăsături erau conectate la ieşire, prin modelul standard pe care îl vom discuta în secţiunea următoare. Antrenând perceptronul cu o mulţime de imagini şi ieşirile corespunzătoare, sistemul putea învăţa să clasifice imaginile (Kröse & van der Smagt, 1996; Champandard, 2003).

Figura 1.6. Perceptronul originar al lui Rosenblatt

Problema principală a acestui model este că nu s-a reuşit găsirea unei modalităţi de determinare a parametrilor conexiunilor dintre imagine (echivalentul în model al retinei) şi stratul intermediar corespunzător trăsăturilor, ci doar dintre acesta şi ieşire. Este ceea ce vom prezenta în continuare.

1.2.3. Perceptronul standard

Perceptronul este un neuron cu mai multe intrări xi, fiecare conexiune de intrare având o valoare numită pondere wi (engl. “weight”),

14 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

care este o măsură a importanţei acelei intrări, un prag θ şi o funcţie de activare semn sau treaptă. Structura sa generală este prezentată în figura 1.7.

x1 w1 x2

w2

y

Σwixi - θ

wn xn

Figura 1.7. Structura generală a perceptronului

Se poate vedea analogia cu modul de funcţionare al unui neuron biologic, în care semnalele de intrare sunt sumate iar neuronul generează un semnal doar dacă suma depăşeşte pragul. Ieşirea perceptronului este dată de următoarea ecuaţie:

,

(1.2)

unde F este funcţia semn:

(1.3)

sau funcţia treaptă:

15 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

.

(1.4)

Scopul perceptronului este rezolvarea problemelor de clasificare binară. Se dă o mulţime de vectori de antrenare, care conţin valori pentru cele n intrări şi valoarea ieşirii dorite. Se doreşte determinarea ponderilor şi pragului astfel încât modelul să clasifice corect toţi vectorii de antrenare într-una din cele 2 clase, adică ieşirea perceptronului pentru un vector de intrare să fie egală cu ieşirea dorită. Pentru a înţelege semnificaţia parametrilor, să considerăm un perceptron cu o singură intrare. În ecuaţiile 1.3 sau 1.4, se vede că dacă a este pozitiv vectorul va fi atribuit unei clase iar dacă este negativ, vectorul va fi atribuit celeilalte clase. Prin urmare, separarea celor 2 clase este dată de o linie, care în cazul unidimensional are ecuaţia:

.

(1.5)

Exemplu

Să considerăm următoarea situaţie:

,

reprezentată în figura 1.8a. Pentru x < 2, răspunsul va fi clasa –1/0 iar pentru x >= 2, răspunsul perceptronului va fi clasa 1.

16 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

Mai întâi să vedem ce se întâmplă când pragul rămâne constant şi se modifică ponderea. Fie următoarea situaţie, în care ponderea s-a schimbat de la 0,5 la 2: . Comparând figurile 1.8a şi 1.8b, se vede că panta diferă. Prin urmare, ponderea exprimă panta dreptei. În figura 1.8b, se vede cum punctul de intersecţie cu ordonata a rămas –1, valoare dată de prag, însă datorită schimbării ponderii, punctul de separare s-a schimbat din 2 în 0,5.

Figura 1.8. Reprezentări geometrice ale unor decizii unidimensionale

Acum să considerăm din nou prima situaţie, menţinând ponderea la valoarea 0,5, dar modificând pragul de la 1 la –1: . Comparând figurile 1.8a şi 1.8c, se vede că pragul a translat dreapta în sus, panta rămânând aceeaşi. Punctul de separare s-a mutat în –2.

17 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

În general, pentru cazul unidimensional, punctul de separare este, conform ecuaţiei 1.5:

.

(1.6)

În continuare, să considerăm un perceptron cu 2 intrări. Separarea celor 2 clase este dată de o dreaptă cu ecuaţia:

(1.7)

care poate fi rescrisă astfel:

.

(1.8)

Ecuaţia este reprezentată în figura 1.9 (după Kröse & van der Smagt, 1996).

Figura 1.9. Reprezentarea geometrică a deciziei bidimensionale

Pentru cazul bidimensional considerat, se observă că panta dreptei de separare este dată de valoarea ponderilor. Dreapta de separare este 18 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

întotdeauna perpendiculară pe dreapta definită de origine şi de punctul (w1, w2). Pragul marchează deplasarea dreptei de separare faţă de origine. În general, distanţa de la un punct la o dreaptă este :

(1.9)

iar în cazul nostru distanţa de la origine la dreapta de separare este:

.

(1.10)

O observaţie importantă pe baza figurilor 1.8 şi 1.9 este că perceptronul poate învăţa să separe doar clase ale căror instanţe nu sunt intercalate, numite separabile liniar. În cazul bidimensional, avem o dreaptă care împarte planul în două. De o parte a dreptei se află o clasă iar de cealaltă parte se află cealaltă clasă. Dacă am fi avut 3 intrări, ar fi existat o suprafaţă de separare care ar fi împărţit spaţiul în 2 regiuni. În cazul general n-dimensional, perceptronul defineşte un hiperplan de separare.

1.2.4. Regula de învăţare a perceptronului

În ecuaţia 1.2 apar atât ponderile cât şi pragul. De fapt, aceşti parametri pot fi trataţi unitar, deoarece intrarea totală a neuronului reprezintă până la urmă o sumă. De aceea, pentru a simplifica modelul de calcul, se consideră că pragul defineşte încă o intrare a neuronului:

19 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

.

(1.11)

Considerând această intrare suplimentară ca fiind 1 în loc de –1, pragul va fi valoarea negată a ponderii conexiunii respective. În acest mod, algoritmul de învăţare are ca scop doar determinarea unor ponderi. Arhitectura perceptronului după aceste transformări este prezentată în figura 1.10.

x1 w1 x2

w2

wn

y

Σwixi

-θ

xn 1

Figura 1.10. Perceptronul. Pragul poate fi considerat ponderea unei conexiuni suplimentare

Astfel, ieşirea este:

.

(1.12)

Pentru a descrie regula de învăţare a perceptronului, vom utiliza următoarele notaţii. Fie x = (x1, …, xn) un vector de intrare. Mulţimea de 20 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

antrenare conţine N astfel de vectori. Pentru vectorul x, y este ieşirea calculată de perceptron iar yd este ieşirea dorită (corectă, cunoscută). Fie w = (w1, …, wn, wn+1) vectorul de ponderi. Conform celor discutate anterior, wn+1 = – θ. Învăţarea are loc prin modificarea valorilor ponderilor pentru a reduce diferenţa dintre ieşirile reale şi ieşirile dorite, pentru toate datele de antrenare. Instanţele de antrenare se prezintă la intrarea reţelei succesiv, calculându-se ieşirea reţelei şi eroarea. Pe baza erorii se ajustează ponderile. Prezentarea instanţelor se face iterativ, până se termină toată mulţimea de antrenare. Prezentarea tuturor instanţelor reprezintă o epocă de antrenare. Apoi, dacă mai există erori, procesul poate reîncepe cu o nouă epocă şi continuă până când ieşirea perceptronului este egală cu ieşirea dorită pentru toate instanţele de antrenare. Dacă după prezentarea instanţei i ieşirea reală este yi iar ieşirea dorită este ydi, atunci eroarea este: .

(1.13)

Dacă eroarea este pozitivă, trebuie să creştem ieşirea perceptronului yi. Dacă eroarea este negativă, trebuie să micşorăm ieşirea yi.

Exemplu

Să considerăm problema de clasificare bidimensională definită de mulţimea de antrenare din tabelul 1.1, care ne va ajuta să înţelegem algoritmul de antrenare.

21 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Tabelul 1.1. Mulţime de antrenare Intrări Ieşire dorită 11 1 1 –1 0

Vom folosi pentru perceptron funcţia treaptă, însă dacă problema era definită cu valori ale clasei de –1 în loc de 0, se putea folosi funcţia semn fără alte modificări. De asemenea, pentru a simplifica şi mai mult lucrurile, vom ignora pragul. În această situaţie, găsirea perechii de ponderi se rezumă la a găsi orientarea potrivită a unei drepte care se poate roti în jurul originii. Dacă vectorul de ponderi este w = (–0,2, 0,1), ieşirile perceptronului pentru cei doi vectori vor fi:

Primul vector nu este clasificat corect: y1 = 0 însă yd1 = 1. Eroarea este e = 1. Situaţia este reprezentată în figura 1.11.

1.5

1

0.5

0

-0.5

-1

-1.5 -1.5

-1

-0.5

0

0.5

1

1.5

Figura 1.11. Procesul de învăţare: ajustarea ponderilor (cazul 1) 22 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

Se vede că ambele puncte sunt sub dreapta de separare. Ecuaţia dreptei este:

(1.14)

echivalent cu:

,

(1.15)

deci panta dreptei este –w1 / w2. Am dori să scădem panta dreptei, astfel încât să treacă printre cele două puncte. Întrucât eroarea apare la primul vector, cel de sus, trebuie modificat w1. Prin urmare, trebuie mărit w1, de exemplu la valoarea w1 = –0,05, rezultând situaţia din figura 1.12.

1.5

1

0.5

0

-0.5

-1

-1.5 -1.5

-1

-0.5

0

0.5

1

1.5

Figura 1.12. Procesul de învăţare: ajustarea ponderilor (cazul 2)

Acum ieşirile perceptronului vor fi:

23 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

care sunt răspunsurile corecte. Analog, dacă vectorul de ponderi este w = (0,2, 0,1), ieşirile perceptronului pentru cei doi vectori vor fi:

adică dreapta trece pe dedesubtul vectorului al doilea. Eroarea acestuia este . În acest caz, panta –w1 / w2 trebuie crescută şi în consecinţă trebuie mărit w2, să spunem până la w2 = 0,4. Ieşirile perceptronului vor fi:

şi corespund răspunsurilor corecte. Să sintetizăm rezultatele. În primul caz, e1 > 0, x1 > 0 şi diferenţa cu care am actualizat ponderea,

. În al doilea caz, e2 < 0, x2 < 0 şi

. Acum să considerăm exemplul rotit cu 180° în jurul originii, definind problema următoare din tabelul 1.2, cu vectorul de ponderi w = (0,2, –0,1), după cum se poate vedea în figura 1.13.

24 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 1. Reţele neuronale cu un singur strat

Tabelul 1.2. Mulţime de antrenare Intrări Ieşire dorită –1 1 0 –1 –1 1 1.5

1

0.5

0

-0.5

-1

-1.5 -1.5

-1

-0.5

0

0.5

1

1.5

Figura 1.13. Procesul de învăţare: ajustarea ponderilor (cazul 3)

Ieşirile perceptronului pentru cei doi vectori vor fi:

Vectorul 2 are eroarea e2 = 1 – 0 > 0. Acum am dori să scădem panta dreptei –w1 / w2, astfel încât cele două puncte să fie separate, modificând w2. Ponderea w2 trebuie să scadă. Pentru w2 = –0,3, vom avea:

ceea ce reprezintă o clasificare corectă.

25 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

În această situaţie avem e2 > 0, x2 < 0 şi

.

La fel putem găsi o configuraţie în care e < 0, x > 0 şi

.

Întrucât dorim să determinăm modul în care se schimbă ponderile, vom sumariza cele 4 cazuri în tabelul 1.3.

Tabelul 1.3. Schimbarea ponderilor în funcţie de semnele erorii şi intrării

e >0 0 0 0 >0 0, spunem că respectiva constrângere este activă. Să vedem ce s-ar întâmpla dacă am folosi o altă constrângere:

87 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Atunci langrangianul ar fi:

Calculele se efectuează în mod analog:

Acum nu se mai respectă condiţia α ≥ 0. Considerând α = 0, obţinem x = –0,5 pentru care f(x) = –0,25, la fel ca atunci când lipseşte constrângerea. În acest caz, constrângerea este inactivă. Prin urmare, constrângerile inactive nu au niciun rol iar constrângerile active sunt echivalente cu nişte egalităţi.

4.3. Perspectiva geometică Dincolo de abordarea analitică, este interesantă şi perspectiva geometică asupra acestei metode de optimizare. Întrucât lucrăm cu o funcţie de forma f + α · g, putem reprezenta grafic punctele într-un nou sistem de coordonate, în care abscisa este g iar ordonata este f. Practic, pentru fiecare

88 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

valoare x dintr-un domeniu de interes, reprezentăm în noul grafic un punct (De Doná, 2004; Vasconcelos, 2009). În cazul constrângerii active din exemplul precedent, adică:

,

vom avea situaţia din figura 4.9.

4

3.5

3

2.5

2

1.5

1

0.5

0

-0.5

-1

-3

-2

-1

0

1

2

3

Figura 4.9. Reprezentarea în sistemul de coordonate (g, f) a situaţiei unei constrângeri active

Pe lângă regiunea delimitată de funcţie se trasează linii tangente care o intersectează în zona g ≤ 0. Punctul maxim de intersecţie de pe axa g = 0 este soluţia iar panta este –α. La noi α = 1, ceea ce este echivalent cu o pantă de –45º. Când constrângerea este activă, α > 0 iar intersecţia cu

89 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

funcţia are loc în punctul în care abscisa este 0. Valoarea de pe ordonată reprezintă minimul funcţiei, în acest caz 0. Este doar o coincidenţă că intersecţia apare în punctul (0, 0). Putem considera o altă problemă, doar puţin diferită:

Procedând ca în secţiunea 4.3, determinăm α = 7/2, xmin = –3/2 şi f(xmin) = 5/2. Reprezentarea în sistemul de coordonate (g, f) este cea din figura 4.10.

4

3.5

3

2.5

2

1.5

1

0.5

0

-0.5

-1

-3

-2

-1

0

1

2

3

Figura 4.10. Reprezentarea în sistemul de coordonate (g, f) a unei alte probleme cu o constrângere activă

90 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange 4

3.5

3

2.5

2

1.5

1

0.5

0

-0.5

-1

-3

-2

-1

0

1

2

3

Figura 4.11. Reprezentarea în sistemul de coordonate (g, f) a situaţiei unei constrângeri inactive

f panta = −α x

B

A

(g(x), f(x))

g C ϕ(α)

Figura 4.12. Reprezentarea cazului general pentru o constrângere activă

91 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Aici panta este de aproximativ –74º. Se poate observa că valoarea de pe ordonată corespunzătoare intersecţiei cu tangenta este 2,5, adică exact minimul funcţiei. Să considerăm şi cazul unei constrângeri inactive:

.

Acum α = 0 iar intersecţia cu funcţia are loc într-un punct în care abscisa este strict negativă, după cum se poate vedea în figura 4.11. În general, cazul unei constrângeri active este cel din figura 4.12. Ne interesează semiplanul în care g ≤ 0. Dacă există mai multe constrângeri, reprezentarea devine multidimensională. O dreaptă tangentă la funcţia reprezentată în planul (g, f), cu panta –α, intersectează axa f în punctul . Scopul este determinarea pantei (de fapt a multiplicatorului lagrangian) astfel încât

să fie maxim. În figura 4.12, α poate scădea

astfel încât punctul de intersecţie cu ordonata să crească de la valoarea din punctul C la valoarea din punctul A. Intersecţia are loc în g = 0. Minimul funcţiei f în problema iniţială corespunde valorii de pe ordonată a punctului A. Cazul general pentru o constrângere inactivă este ilustrat în figura 4.13. Aici se poate scădea α astfel încât să se ajungă de la dreapta BC la dreapta AD. Teoretic, α ar putea scădea în continuare, deoarece se poate identifica o dreaptă tangentă la funcţia reprezentată a cărei intersecţie cu axa f să fie mai sus de punctul D. Însă trebuie să respectăm condiţia α ≥ 0. Prin urmare, nu putem să scădem mai mult valoarea lui α. Rezultatul este α = 0 iar intersecţia are loc acum într-un punct unde g < 0. Şi aici, minimul funcţiei f în problema iniţială corespunde valorii de pe ordonată a punctului A. 92 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

f x

B (g(x), f(x)) α =0 A

D g

C

Figura 4.13. Reprezentarea cazului general pentru o constrângere inactivă

f

A

Diferenţa de dualitate

B

g

Figura 4.14. Diferenţa de dualitate pentru o funcţie neconvexă

93 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Din ambele cazuri se poate observa că întotdeauna ori α este 0, ori g este 0, deci se respectă relaţia: α · g = 0. Atunci când funcţia nu este convexă, putem avea situaţia din figura 4.14. Punctul A corespunde soluţiei problemei primare iar B corespunde soluţiei problemei duale, utilizând aceeaşi metodă a dreptei tangente. Din cauza concavităţii, există aici o diferenţă între valorile lui f în cele două puncte, numită diferenţă de dualitate (engl. “duality gap”). În această situaţie, deşi problema duală are o soluţie, aceasta nu este o soluţie corectă şi pentru problema primară.

4.4. Formalizarea problemei de optimizare În această secţiune vom da o descriere completă şi formală a paşilor de rezolvare ai problemei de optimizare. În cazul general avem funcţia obiectiv f, o mulţime de constrângeri de inegalitate gi şi o mulţime de constrângeri de egalitate hj. Problema primară este: ,

(4.9)

astfel încât: (4.10) .

(4.11)

Se defineşte lagrangianul:

94 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

,

(4.12)

unde αi şi βj sunt multiplicatorii lagrangieni. Problema duală este:

(4.13) unde: (4.14) astfel încât: .

(4.15)

Când nu există diferenţa de dualitate:

.

(4.16)

Pe lângă constrângerile 4.10, 4.11 şi 4.15, trebuie îndeplinite şi o serie de condiţii necesare, numite condiţiile Karush-Kuhn-Tucker:

(4.17)

.

(4.18)

95 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Ecuaţia 4.17 generează n ecuaţii, câte una pentru fiecare dimensiune a problemei. Astfel se determină multiplicatorii lagrangieni αi şi βj. Valoarea unui multiplicator lagrangian corespunzătoare soluţiei problemei este egală cu rata modificării valorii maxime a funcţiei obiectiv f atunci când constrângerea aferentă este relaxată. Această interpretare este de multe ori folosită în context economic, unde funcţia de optimizat reprezintă profitul iar constrângerile se aplică resurselor utilizate. Astfel, valoarea unui multiplicator

lagrangian

semnifică

creşterea

constrângere ar fi relaxată puţin, de exemplu

profitului

dacă

acea

în loc de

, cu

ε > 0 (Osborne, 2003).

4.5. Particularizarea pentru maşinile cu vectori suport După cum am văzut în capitolul 3, pentru maşinile cu vectori suport nu avem egalităţi, ci doar inegalităţi. Prin urmare lagrangianul are forma următoare:

(4.19)

iar constrângerile şi condiţiile sunt:

(4.20) (4.21)

96 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

(4.22)

(4.23) Pentru SVM, w* este soluţia problemei primare şi * este soluţia problemei duale. Problema primară este următoarea (ecuaţia 3.11):

(4.24) astfel încât (ecuaţia 3.12):

.

(4.25)

Pentru a respecta notaţia introdusă în acest capitol, constrângerile anterioare pot fi scrise astfel:

.

(4.26)

Introducem ecuaţiile 4.24 şi 4.26 în expresia lagrangianului:

(4.27)

În continuare, se rezolvă ecuaţiile date de condiţiile Karush-KuhnTucker, pentru a găsi minimul lui L:

97 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

(4.28)

.

(4.29)

Înlocuind aceste rezultate în expresia problemei duale, vom obţine următoarea formulare pentru o maşină cu vectori suport liniară:

(4.30)

respectând constrângerile:

(4.31) .

(4.32)

Conform condiţiei:

(4.33)

rezultă că αi > 0 doar pentru vectorii suport, care corespund constrângerilor active (unde g = 0), şi αi = 0 pentru celelalte instanţe, unde constrângerile sunt inactive (g ≠ 0). Avantajul rezolvării problemei duale este că numărul vectorilor Nvs suport este mult mai mic decât numărul instanţelor de antrenare N:

98 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

.

(4.34)

De exemplu, în experimentele făcute de Vapnik (1995) privind recunoaşterea cifrelor scrise de mână, s-a constat că numărul vectorilor suport era de 3-5% din numărul instanţelor de antrenare. În acest capitol nu ne vom opri asupra modalităţii concrete de rezolvare a problemei duale. Există pachete software specializate în acest sens şi algoritmi dedicaţi rezolvării problemei pentru maşinile cu vectori suport. Vom prezenta un astfel de algoritm mai târziu, în capitolul 7. După rezolvarea problemei şi găsirea multiplicatorilor αi, parametrii problemei primare vor fi determinaţi astfel:

(4.35)

,

(4.36)

unde S este mulţimea vectorilor suport iar |S | este numărul lor. Pentru o problemă cu clase liniar separabile, există formule mai simple pentru calcularea valorii lui b. De exemplu, este suficientă verificarea ecuaţiei hiperplanului care trece printr-un vector suport, ca în exemplul următor. Ecuaţia 4.36 este însă utilă în cazul general, atunci când clasele nu sunt liniar separabile, când se permit erori de clasificare sau când se aplică funcţii pentru transformarea datelor, după cum vom vedea în capitolele următoare. Ecuaţia hiperplanului de separare,

, se poate rescrie

sub forma: 99 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

. (4.36)

Exemplu

Pentru a înţelege mai bine modalitatea de calcul, să considerăm mai întâi o problemă unidimensională cu 3 instanţe de antrenare, prezentată în figura 4.15.

1

0.5

0

-0.5

-1

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Figura 4.15. Problemă de clasificare unidimensională

Particularizând ecuaţia 4.30, problema de optimizare este:

(4.37) cu constrângerile: αi ≥ 0

(4.38) .

(4.39)

100 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

Rezolvarea problemei se poate face de exemplu în Microsoft Excel cu instrumentul Solver. Valorile celor 3 multiplicatori αi corespund celulelor A, B şi C. În celula A introducem expresia care va trebui maximizată (ecuaţia 4.37), după cum se arată în figura 4.16.

Figura 4.16. Expresia de maximizat

În celula A introducem expresia 4.39, ca în figura 4.17.

Figura 4.17. Suma multiplicatorilor

101 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

În fereastra instrumentului Solver, se introduc constrângerile ca multiplicatorii din celulele A:C să fie nenegative şi suma din A să fie 0. Se setează funcţia obiectiv de maximizat ca fiind expresia din celula A, după cum se indică în figura 4.18.

Figura 4.18. Setarea funcţiei obiectiv şi a constrângerilor

Figura 4.19. Rezultatele

102 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

După rezolvare, rezultatele vor fi afişate în celulele A:C, ca în figura 4.19. Prin urmare: α1 = α2 = 0,5 şi α3 = 0. După determinarea multiplicatorilor, putem calcula vectorul w, conform ecuaţiei 4.35:

Apoi obţinem valoarea pragului pe baza ecuaţiilor dreptelor care trec prin vectorii suport, la noi acestea fiind instanţele 1 şi 2. Rezultatele sunt identice, având în vedere că b este unic: în instanţa 1:

,

în instanţa 3:

.

Prin urmare, suprafaţa de separare este dreapta

adică

x = 2, aflată la distanţe egale de vectorii suport (instanţa 1 şi instanţa 2). În continuare, vom rezolva o problemă bidimensională puţin mai complexă, ilustrată în figura 3.1 şi repetată aici pentru comoditate. Mulţimea de antrenare este prezentată în tabelul 4.1.

Tabelul 4.1. Instanţele de antrenare ale problemei bidimensionale x1 x2 Clasa 1 1 –1 1 3 –1 2 2 –1 3 1 –1 4 4 1 4 5 1 5 5 1 103 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport 7

6

5

4

3

2

1

0

0

1

2

3

4

5

6

7

Figura 4.20. Problemă de clasificare bidimensională

Expresia care trebuie maximizată este următoarea (varianta nesimplificată de mai jos a fost generată printr-un program):

             – 0.5 ∙ 2 ∙  ∙   4 ∙  ∙   4 ∙  ∙   4 ∙  ∙  – 8 ∙  ∙  – 9 ∙  ∙  – 10 ∙  ∙   4 ∙  ∙   10 ∙  ∙   8 ∙  ∙   6 ∙  ∙  – 16 ∙  ∙  – 19 ∙  ∙  – 20 ∙  ∙   4 ∙  ∙   8 ∙  ∙   8 ∙  ∙   8 ∙  ∙  – 16 ∙  ∙  – 18 ∙  ∙  – 20 ∙  ∙   4 ∙  ∙   6 ∙  ∙   8 ∙  ∙   10 ∙  ∙  – 16 ∙  ∙  – 17 ∙  ∙  – 20 ∙  ∙  – 8 ∙  ∙  – 16 ∙  ∙  – 16 ∙  ∙  – 16 ∙  ∙   32 ∙  ∙   36 ∙  ∙   40 ∙  ∙  – 9 ∙  ∙  – 19 ∙  ∙  – 18 ∙  ∙  – 17 ∙  ∙   36 ∙  ∙   41 ∙  ∙   45 ∙  ∙  – 10 ∙  ∙  – 20 ∙  ∙  – 20 ∙  ∙  – 20 ∙  ∙   40 ∙  ∙   45 ∙  ∙   50 ∙  ∙  "

104 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 4. Dualitatea Lagrange

Celelalte constrângeri sunt:

şi condiţia ca multiplicatorii să aibă valori nenegative: αi ≥ 0. Şi această problemă poate fi rezolvată în Microsoft Excel. Multiplicatorii lagrangieni ai instanţelor sunt prezentaţi în tabelul 4.2.

Tabelul 4.2. Multiplicatorii lagrangieni ai instanţelor x1 x2 Clasa α 1 1 –1 0 1 3 –1 0,0584 2 2 –1 0,1332 3 1 –1 0,0584 4 4 1 0,25 4 5 1 0 5 5 1 0

Pe baza acestora se calculează apoi w = (0,5, 0,5) şi b = –3. Dreapta de separare are următoarea ecuaţie:

sau echivalent:

Rezultatul este prezentat în figura 4.21.

105 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport 7

6

5

4

3

2

1

0

0

1

2

3

4

5

6

7

Figura 4.21. Dreapta de separare şi vectorii suport

În faza de predicţie, noile instanţe vor fi clasificate conform ecuaţiei 3.3:

. De exemplu:

(prin convenţia din ecuaţia 3.4)

Pentru unele probleme pot exista foarte mulţi vectori suport, iar în acest caz programele generale de optimizare pot fi mai puţin eficiente. De aceea, pentru SVM se folosesc în general algoritmi speciali de optimizare, precum algoritmul de optimizare secvenţială minimală (engl. “Sequential Minimal Optimization”, SMO), descris în capitolul 7.

106 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5

Nuclee 5.1. Transformarea în trăsături Există multe situaţii în care datele nu sunt separabile liniar pentru a folosi direct metodele de calcul prezentate până acum. De exemplu, să considerăm

problema

unidimensională

din

figura

5.1.

Instanţele

corespunzătoare punctelor 1 şi 6 aparţin unei clase, iar instanţele corespunzătoare punctelor 3 şi 4 aparţin celeilalte clase.

1 0.5

0 -0.5

-1 0

1

2

3

4

5

6

7

Figura 5.1. Instanţe în spaţiul atributelor

O idee ingenioasă, pentru a putea aplica totuşi separarea liniară, este transformarea datelor din spaţiul iniţial al problemei, numit spaţiul atributelor, într-un spațiu cu (mult) mai multe dimensiuni, numit spaţiul trăsăturilor, în care clasele devin separabile liniar. Transformarea se face cu ajutorul unei funcţii care realizează transformarea în trăsături (engl. “feature mapping”), după cum se poate vedea în figura 5.2 (adaptată după Wikimedia Commons, 2014c).

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport φ

φ(x) x φ(o)

x

φ(x)

o o

φ(x)

o

φ(o)

o φ(x) φ(o) x

φ(o)

x

spaţiul atributelor

spaţiul trăsăturilor

Figura 5.2. Transformarea în trăsături

De exemplu, să considerăm problema de mai sus şi o funcţie , care transformă spaţiul unidimensional din figura 5.1 în spaţiul bidimensional din figura 5.3.

40

35

30

25

20

15

10

5

0 1

2

3

4

5

6

7

Figura 5.3. Instanţe în spaţiul trăsăturilor

108 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

Acum instanţele din spaţiul bidimensional sunt punctele (1, 1), (3, 9), (4, 16) şi (6, 36) care pot fi separate de o dreaptă. Din ecuaţiile 3.1 şi 4.35, înlocuind x cu φ(x), vom obţine următoarea expresie pentru ecuaţia hiperplanului de separare:

.

(5.1)

Se observă că toate calculele ce privesc instanţele se fac în perechi, intrând în produse scalare ale funcţiilor de transformare în trăsături. Numim acest produs scalar nucleu (engl. “kernel”):

.

(5.2)

În acest caz, ecuaţia 5.1 devine:

.

Exemplu

Fie nucleul:

.

109 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

(5.3)

Inteligenţă artificială: maşini cu vectori suport

Dacă avem o problemă bidimensională, cu

, atunci:

unde funcţia φ(x) transformă vectorul bidimensional x într-un vector cu 4 dimensiuni:

.

De exemplu, dacă x = (2, 3), atunci . Se poate verifica faptul că dacă z = (4, –5), atunci

şi .

Însă folosind direct nucleul, calculele sunt mult mai simple:

.

110 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

5.2. Teorema lui Mercer Nu orice funcţie cu 2 argumente vectoriale este un nucleu valid. O astfel de funcţie trebuie să satisfacă în general ecuaţia 5.2. În cele ce urmează (Ng, 2007), vom prezenta condiţiile pe care trebuie să le îndeplinească o funcţie K pentru a fi un nucleu valid, adică pentru a avea garanţia că există o transformare φ (a cărei expresie putem să nu o cunoaştem explicit), astfel încât să se respecte ecuaţia 5.2. Fie o mulţime de N instanţe xi (nu neapărat instanţele din mulţimea de antrenare) şi o matrice K ale cărei elemente sunt:

.

Matricea K se numeşte matricea nucleului. Dacă funcţia K este un nucleu valid, atunci:

(5.4)

Prin urmare, matricea K trebuie să fie simetrică. În al doilea rând, notând cu φk(x) valoarea coordonatei k a vectorului φ(x), pentru orice vector z vom avea:

.

ceea ce înseamnă că matricea K este pozitiv semidefinită.

111 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

(5.5)

Inteligenţă artificială: maşini cu vectori suport

S-a demonstrat că aceste două condiţii sunt nu numai necesare, ci şi suficiente pentru valididatea nucleului K. Aceasta este teorema lui Mercer (Mercer, 1909; Hazewinkel, 2001): O funcţie

este un nucleu valid dacă şi numai dacă

oricare ar fi mulţimea

cu

matricea nucleului

corespunzătoare lui K este simetrică şi pozitiv semidefinită.

5.3. Tipuri de nuclee Există mai multe clase de funcţii care pot servi drept nuclee pentru transformarea datelor. Nucleele folosite în mod uzual pentru maşinile cu vectori suport sunt:

•

nucleul liniar:

;

•

nucleul polinomial:

•

nucleul gaussian sau cu funcţii de bază radială (engl. “radial basis

;

functions”, RBF): •

;

nucleul sigmoid:

.

5.3.1. Nucleul polinomial

În expresia

, parametrii utilizaţi sunt:

γ > 0, r şi, foarte important, numărul (în general) întreg d, care indică gradul polinomului. De multe ori, se folosesc valorile γ = 1, r = 1 şi d = 2 sau 3. Un nucleu nu este echivalent cu o singură transformare φ, ci cu o întreagă familie de transformări. Nici măcar dimensionalitatea spaţiului trăsăturilor nu este fixă. De exemplu, am văzut mai sus că pentru o 112 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

problemă bidimensională, cu x = (x1, x2), nucleul K(x, z) = (x · z)2 poate fi definit de funcţia

, care transformă

spaţiul atributelor într-un spaţiu cu 4 dimensiuni. Însă există şi:

care transformă spaţiul bidimensional al atributelor într-un spaţiu cu 3 dimensiuni. Un nucleu polinomial de forma:

poate fi echivalent cu utilizarea atât a funcţiei:

cu 6 dimensiuni, cât şi a funcţiei:

cu 9 dimensiuni. Când se aleg diferite nuclee care satisfac teorema lui Mercer, chiar apropiate din punct de vedere al parametrilor, pot exista salturi mari în dimensionalitatea spaţiului trăsăturilor. Pentru acelaşi nucleu dar cu o problemă tridimensională, adică x = (x1, x2, x3), vom avea o transformare într-un spaţiu cu 13 dimensiuni: 113 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

În general, gradul polinomului d este un număr întreg pozitiv, însă au fost încercate şi valori fracţionare (Rossius et al., 1998) pentru un control mai fin al numărului de dimensiuni în care sunt proiectate instanţele problemei. Nucleul polinomial este des utilizat pentru probleme de prelucrare a limbajului natural. În general se foloseşte gradul 2, deoarece grade mai mari tind să provoace fenomenul de supra-potrivire (Chang et al, 2010; Lin, 2012).

Exemplu

Pentru problema din figura 5.1, multiplicatorii lagrangieni ai instanţelor sunt cei din tabelul 5.1, obţinuţi cu aceeaşi metodă de calcul, prezentată în capitolul 4, dar înlocuind în ecuaţia 4.30 produsul scalar cu nucleul

. Folosim nucleul

.

Tabelul 5.1. Multiplicatorii lagrangieni ai instanţelor xi Clasa (yi) 1 –1 3 1 4 1 6 –1

αi 1,0461 1,2304 0,1862 0,3706

Funcţia discriminant este:

114 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

Înlocuind valorile din tabelul 5.1, se obţine funcţia:

Valoarea parametrului b se poate calula rezolvând oricare din ecuaţiile f(xi) = yi pentru vectorii suport, adică: f(1) = –1, f(3) = 1 etc. Rezultatul este b = –3. Prin urmare, funcţia discriminant este următoarea funcţie cuadratică, capabilă să separe datele unidimensionale:

şi al cărei grafic este ilustrat în figura 5.4. Rădăcinile funcţiei sunt: z = 1,697 şi z = 5,303.

Figura 5.4. Graficul funcţiei discriminant

Suprafaţa de decizie în spaţiul iniţial unidimensional este prezentată în figura 5.5.

115 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport 1

0.5

0

-0.5

-1 0

1

2

3

4

5

6

7

Figura 5.5. Suprafaţa de decizie în spaţiul atributelor

5.3.2. Nucleul gaussian

, avem doar parametrul γ > 0, care

În expresia are semnificaţia 1 / 2σ2.

Figura 5.6 (Berwick, 2003) ilustrează suprafaţa de decizie a unei probleme de clasificare în care se utilizează nucleul gaussian.

Figura 5.6. Suprafaţă de decizie pentru nucleul gaussian

Privind aspectul acestei funcţii, în care valoarea nucleului este mare (1 dacă γ = 1) când argumentele sunt apropiate şi tinde la 0 când distanţa dintre ele este mare, putem înţelege nucleul ca o măsură a similarităţii dintre

116 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

cele două argumente. Şi produsul scalar din nucleul polinomial are aceeaşi semnificaţie. Folosind această interpretare, se pot găsi funcţii nucleu pentru probleme cu formulări diferite de cele ale clasificării clasice. De exemplu, fie problema clasificării proteinelor: o proteină este reprezentată de un şir de caractere, care semnifică aminoacizi. Scopul este clasificarea proteinelor, adică a acestor şiruri de caractere în familii şi super-familii definite de relaţiile dintre structură şi funcţionalitate. Să presupunem că φ(x) reprezintă numărul de apariţii al fiecărui subşir de lungime k în şirul x. Pentru 20 de aminoacizi standard, problema presupune lucrul într-un spaţiu cu 20k dimensiuni, care nu este fezabil nici pentru valori relativi mici ale lui k. Însă, folosind algoritmi de potrivire a şirurilor (engl. “string matching”), se poate calcula eficient nucleul

, astfel încât se va lucra

implicit în spaţiul cu 20k dimensiuni, fără însă a calcula vectorii trăsăturilor în acest spaţiu (Leslie, 2004; Ng, 2007). Este de asemenea important de precizat că nucleul gaussian proiectează spaţiul atributelor într-un spaţiu infinit dimensional. Vom da în continuare un exemplu intuitiv asupra modului în care se poate demonstra acest rezultat (Iyer & Ghose, 2013). Să considerăm cazul unei probleme bidimensionale, n = 2. Presupunând că γ = 1, putem exprima ecuaţia nucleului gaussian astfel:

Descompunând această expresie în serie Taylor, conform regulii:

117 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

vom obţine:

.

Se poate observa că numărătorul argumentului sumei este un nucleu polinomial de ordin n. Nucleul gaussian este deci o combinaţie a tuturor nucleelor polinomiale de grad n ≥ 0. De vreme ce un nucleu polinomial de ordin n transformă datele într-un spaţiu cu mai mult de n dimensiuni, putem spune că nucleul gaussian transformă spaţiul atributelor într-un spaţiu al trăsăturilor infinit dimensional. Chiar dacă vectorii corespunzători φ(x) sunt infiniţi, acest lucru nu înseamnă că similaritatea între 2 vectori nu se poate calcula. Produsul lor scalar este o sumă care converge la un număr real şi acest număr este de fapt valoarea nucleului gaussian. Acest tip de nucleu este foarte popular pentru problemele de clasificare.

5.3.3. Nucleul sigmoid

Nucelul sigmoid este asemănător funcţiei de activare tipice a unui neuron de tip perceptron. Acesta însă nu este întotdeauna un nucleu valid conform teoremei lui Mercer, deoarece există valori ale parametrilor pentru care matricea nucleului nu este pozitiv semidefinită (Lin & Lin, 2003; Hinton, 2008).

118 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 5. Nuclee

Un nucleu sigmoid alternativ care respectă teorema lui Mercer şi care are o formă similară cu nucleul sigmoid standard a fost propus recent (Carrington, Fieguth & Chen, 2014):

,

unde a este un parametru de deplasare orizontală iar b este un parametru de scalare orizontală.

119 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6

Probleme neseparabile liniar 6.1. Margini flexibile În unele cazuri, datele nu devin separabile liniar nici după transformarea într-un spaţiu cu mai multe dimensiuni. În alte situaţii, datele prezintă valori extreme (engl. “outliers”) care influenţează marginea optimă. De exemplu, în figura 6.1 prezenţa unor valori extreme scade mărimea marginii dintre cele două clase.

Figura 6.1. Prezenţa unor valori extreme afectează calitatea modelului

Soluţia este de a permite existenţa unor erori ξi în clasificare, după cum se poate vedea în figura 6.2. ξi se numesc variabile de decalaj (engl. “slack variables”). Se spune că hiperplanul de separare are acum o margine flexibilă (engl. “soft margin”).

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport 7

6

w 5

4

3

ξ1

ξ2

2

(w · x) + b = 1 1

(w · x) + b = 0 (w · x) + b = -1

0 0

1

2

3

4

5

6

7

Figura 6.2. Variabile de decalaj şi margine flexibilă

Problema de optimizare devine:

(6.1)

astfel încât: (6.2) ξi ≥ 0

(6.3)

cu i = 1..N. Parametrul de cost C este o măsură a erorii admise în clasificare. El controlează compromisul dintre a permite erori pe mulţimea de antrenare şi a forţa margini stricte. Creşterea valorii lui C măreşte costul clasificării greşite a instanţelor şi determină crearea unui model mai precis dar care poate să nu generalizeze bine. O valoare foarte mare pentru C este

122 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6. Probleme neseparabile liniar

echivalentă cu folosirea unui hiperplan cu margine inflexibilă, ca în capitolele anterioare. Parametrul C trebuie ales de utilizator şi depinde de problemă. De obicei, acesta se alege prin încercări repetate, unii autori propunând secvenţe exponenţiale, precum: 10–5, 10–3, 0,1, 1, 10, 100, 103, 105. De asemenea, se pot încerca mai multe combinaţii de perechi de valori pentru parametri (Hsu, Chang & Lin, 2010), de exemplu, dacă se foloseşte nucleul gaussian, perechi (C, γ). La fel cum s-a procedat şi în capitolul 4, se formează lagrangianul (Huson, 2007):

(6.4)

şi apoi se pun condiţiile ca derivatele sale parţiale în raport cu argumentele să fie 0. Se obţine astfel problema duală:

(6.5)

astfel încât: 0 ≤ αi ≤ C, i = 1..N.

(6.6)

Celelalte constrângeri sunt la fel ca în situaţia marginii inflexibile:

123 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

(6.7) (6.8)

Oarecum surprinzător, termenii ξi nu apar în problema duală. Contează numai parametrul C care limitează multiplicatorii αi. Pentru instanţele neclasificabile, multiplicatorii ar creşte foarte mult şi ar determina şi apariţia unor vectori suport suplimentari, cu αi > 0.

6.2. Exemple Să considerăm mai întâi tot o problemă unidimensională (figura 6.3), pentru care vom aplica o maşină cu vectori suport liniară. Este clar că nu se pot separa cele două clase.

1 0.5 0 -0.5 -1 0

1

2

3

4

5

6

7

8

9

Figura 6.3. Problemă neseparabilă liniar unidimensională

Fără C, toate instanţele au valori mari pentru multiplicatorii αi, după cum se vede în tabelul 6.1. De asemenea, se poate observa cum scăderea valorii lui C limitează şi valorile multiplicatorilor αi.

124 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6. Probleme neseparabile liniar

Tabelul 6.1. Multiplicatorii lagrangieni ai instanţelor xi Clasa (yi) αi (fără C) αi (C = 10) αi (C = 1) 1 –1 417,428 1,629 0 2 –1 38.564,744 2,516 0,221 3 1 103.756,765 7,933 1 4 –1 76.934,555 3,798 1 6 1 11.249,539 0,001 0,221 7 1 762,259 0,0017 0 8 1 148,164 0,0079 0

A doua problemă, din figura 6.4, este tot unidemensională. Clasele sunt separabile liniar, dar instanţa din punctul 10 ar putea fi o valoare afectată de zgomot sau o valoare extremă. Decizia pe care trebuie să o ia utilizatorul este dacă permite o eroare la această instanţă pentru a avea o margine mare de separare între 4 şi 12 (introducând parametrul C, pentru o formulare cu margine flexibilă), sau dacă doreşte o clasificare precisă, cu o margine mai mică, între 10 şi 12 (fără C, cu formularea exactă a problemei de optimizare).

1 0 -1 0

2

4

6

8

10

12

14

16

Figura 6.4. Problemă cu o valoare extremă

Tabelul 6.2 prezintă multiplicatorii lagrangieni ai instanţelor, pentru diferite valori ale lui C.

125 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Tabelul 6.2. Multiplicatorii lagrangieni ai instanţelor xi Clasa (yi) αi (fără C) αi (C = 0,01) αi (C = 0,001) 1 –1 0 0 0 2 –1 0 0 0,001 3 –1 0 0,0065 0,001 4 –1 0 0,01 0,001 10 –1 0,5 0,01 0,001 12 1 0,5 0,01 0,001 13 1 0 0,01 0,001 14 1 0 0,0065 0,001 15 1 0 0 0,001

Fără C se reuşeşte clasificarea perfectă, cu punctul de separare 11. Cu un C mai mic, se permit erori şi apar mai mulţi vectori suport. Pentru C = 0,01, punctul de separare este 9,32, iar pentru C = 0,001, are valoarea 9,11, deci se mută spre stânga, depăşind instanţa problematică 10. Să considerăm acum un exemplu bidimensional neseparabil liniar, ilustrat în figura 6.5 (Zisserman, 2014).

Figura 6.5. Problemă neseparabilă liniar bidimensională

126 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6. Probleme neseparabile liniar

Suprafeţele de decizie, folosind nucleul gaussian

,

pentru diferite valori ale lui γ şi C, sunt prezentate în figurile 6.6 – 6.10 (Zisserman, 2014).

Figura 6.6. Suprafaţa de decizie pentru γ = 1/2 şi C = ∞

Figura 6.7. Suprafaţa de decizie pentru γ = 1/2 şi C = 100

127 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Figura 6.8. Suprafaţa de decizie pentru γ = 1/2 şi C = 10

Figura 6.9. Suprafaţa de decizie pentru γ = 8 şi C = ∞

În final, vom rezolva un exemplu mai complex (adaptat după Quinlan, 1986 de Leon, 2012), în care trebuie să se determine în funcţie de condiţiile meteorologice dacă se poate juca sau nu golf. Instanţele problemei sunt prezentate în tabelul 6.3.

128 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6. Probleme neseparabile liniar

Figura 6.10. Suprafaţa de decizie pentru γ = 50 şi C = ∞

Tabelul 6.3. Problemă de clasificare cu atribute mixte Nr. instanţă Starea vremii Temperatură Umiditate Vânt Joc 1 Soare 29,4 85 Absent Nu 2 Soare 26,7 90 Prezent Nu 3 Înnorat 28,3 86 Absent Da 4 Ploaie 21,1 96 Absent Da 5 Ploaie 20,0 80 Absent Da 6 Ploaie 18,3 70 Prezent Nu 7 Înnorat 17,8 65 Prezent Da 8 Soare 22,2 95 Absent Nu 9 Soare 20,6 70 Absent Da 10 Ploaie 23,9 80 Absent Da 11 Soare 23,9 70 Prezent Da 12 Înnorat 22,2 90 Prezent Da 13 Înnorat 27,2 75 Absent Da 14 Ploaie 21,7 91 Prezent Nu

Întrucât atributele Temperatură și Umiditate sunt numerice, acestea se normalizează în întervalul [0, 1]. Vânt este un atribut binar, deci valorile lui se pot înlocui cu valori de 0 şi 1. Starea vremii are mai multe valori simbolice. Acestea pot fi tratate ca valori ordinale, transformându-se în

129 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

valorile { 0, 0,5, 1 }, ca în tabelul 6.4, sau pot fi tratate ca valori nominale distincte, şi în acest caz vom avea o intrare separată binară pentru fiecare valoare a atributului. Cu 3 valori distincte, vom avea 3 intrări (notate SV-S pentru Starea vremii = Soare, SV-Î pentru Starea vremii = Înnorat şi SV-P pentru Starea vremii = Ploaie), în care, pentru o anumită valoare a atributului, intrarea corespunzătoare va fi 1 iar celelalte două vor fi 0, după cum se poate vedea în tabelul 6.5.

Tabelul 6.4. Problemă de clasificare cu atribute exclusiv numerice Nr. instanţă Starea vremii Temperatură Umiditate Vânt Joc 1 1 1,000 0,645 0 –1 2 1 0,767 0,806 1 –1 3 0,5 0,905 0,677 0 1 4 0 0,284 1,000 0 1 5 0 0,190 0,484 0 1 6 0 0,043 0,161 1 –1 7 0,5 0,000 0,000 1 1 8 1 0,379 0,968 0 –1 9 1 0,241 0,161 0 1 10 0 0,526 0,484 0 1 11 1 0,526 0,161 1 1 12 0,5 0,379 0,806 1 1 13 0,5 0,810 0,323 0 1 14 0 0,336 0,839 1 –1

În cele ce urmează, vom utiliza mulţimea de date din tabelul 6.4 şi nucleul gaussian

. Multiplicatorii şi valorile funcţiei

discriminant sunt prezentate în tabelul 6.6, în condiţiile în care b = 0,699.

130 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 6. Probleme neseparabile liniar

Tabelul 6.5. Transformarea unui atribut simbolic nominal Nr. instanţă SV-S SV-Î SV-P Temperatură Umiditate Vânt Joc 1 1 0 0 1,000 0,645 0 –1 2 1 0 0 0,767 0,806 1 –1 3 0 1 0 0,905 0,677 0 1 4 0 0 1 0,284 1,000 0 1 5 0 0 1 0,190 0,484 0 1 6 0 0 1 0,043 0,161 1 –1 7 0 1 0 0,000 0,000 1 1 8 1 0 0 0,379 0,968 0 –1 9 1 0 0 0,241 0,161 0 1 10 0 0 1 0,526 0,484 0 1 11 1 0 0 0,526 0,161 1 1 12 0 1 0 0,379 0,806 1 1 13 0 1 0 0,810 0,323 0 1 14 0 0 1 0,336 0,839 1 –1

Tabelul 6.6. Rezultatele modelului SVM Nr. instanţă 1 2 3 4 5 6 7 8 9 10 11 12 13 14

α 2,028 5,486 3,325 1,578 0 1,696 0 2,691 1,721 0 1,460 9,684 0 6,594

(w · x) + b –1 –1 1 1 1,040 –1 1 –1 1 1,392 1 1 1,402 –1

fd(x) –1 –1 1 1 1 –1 1 –1 1 1 1 1 1 –1

Joc –1 –1 1 1 1 –1 1 –1 1 1 1 1 1 –1

131 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7

Algoritmul SMO 7.1. Optimizarea diferenţială a unei funcţii În cazul general al unei funcţii de n variabile, f(x1, ..., xn), o modalitate de maximizare este de a considera pe rând fiecare variabilă şi de a-i găsi acesteia valoarea care maximizează funcţia, în condiţiile în care celelalte variabile rămân cu valori fixe (după Terashima, 2012). De exemplu, fie

, reprezentată

din două perspective diferite în figurile 7.1 şi 7.2.

Figura 7.1. Graficul funcţiei
 ,        2 

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Figura 7.2. Proiecţie bidimensională a graficul funcţiei
 ,        2 

Să presupunem că începem procesul de optimizare din punctul (5, 5), unde f(5, 5) = 5 + 5 + 25 – 50 – 25 = –40. Realizăm mai întâi optimizarea după x1, considerând fix pe x2:

care are un maxim în punctul în care derivata expresiei din paranteză în raport cu x1 este 0: .

Din noul punct (0,67 , 5), realizăm optimizarea după x2, considerând fix pe x1:

134 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

care are un maxim în punctul în care derivata expresiei din paranteză în raport cu x2 este 0: .

Repetând procesul vom obţine succesiv:

Se vede că x1 şi x2 converg la valorile care maximizează funcţia: f(0,43 , 0,71) = 0,57. Din punct de vedere grafic, procesul se desfăşoară ca în figura 7.3.

Figura 7.3. Procesul de optimizare diferenţială iterativă

135 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

7.2. Rezolvarea problemei duale pentru maşini cu vectori suport După cum am văzut în capitolele anterioare, problema de optimizare pentru o maşină cu vectori suport presupune maximizarea funcţiei ΘD(α):

(7.1)

astfel încât:

0 ≤ αi ≤ C, i = 1..N

(7.2) (7.3) .

(7.4)

Rezolvând problema de determinare a multiplicatorilor optimi, sunt satisfăcute următoarele condiţii de optimalitate:

(7.5)

Având în vedere ecuaţia 7.3, nu putem optimiza funcţia din ecuaţia 7.1 cu o singură variabilă, ca în secţiunea 7.1. Pentru a păstra suma constantă, trebuie să modificăm cel puţin 2 multiplicatori α simultan.

136 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

Pentru a rezolva această problemă de optimizare au fost propuse mai multe metode. De exemplu, metoda partiţionării (engl. “chunking”, Vapnik, 1982) se bazează pe faptul că înlăturarea instanţelor de antrenare cu multiplicatori nuli nu modifică soluţia. Ideea de bază este împărţirea problemei de optimizare în subprobleme mai mici, pentru a identifica multiplicatorii nenuli. O subproblemă conţine multiplicatorii nenuli găsiţi prin rezolvarea subproblemei precedente la care se adaugă instanţele care violează cel mai mult condiţiile 7.5. În ultimul pas, se rezolvă problema completă, în care s-au determinat toţi multiplicatorii nenuli. O altă metodă este cea a decompoziţiei (Osuna, Freund & Girosi, 1997b), cu acelaşi principiu de împărţire în subprobleme mai mici, însă de dimensiune fixă, ceea ce permite rezolvarea unor probleme cu mulţimi de antrenare foarte mari. Algoritmul de optimizare secvenţială minimală (engl. “Sequential Minimal Optimization”, SMO), propus de Platt (1998), descompune şi el problema de programare cuadratică în subprobleme de dimensiune fixă, rezolvând însă de fiecare dată problema de optimizare de dimensiune minimă, adică o problemă cu doar 2 multiplicatori. În mod repetat, SMO alege 2 multiplicatori pentru a fi optimizaţi împreună, până când este rezolvată problema globală. Din punct de vedere practic, procedura se repetă până la satisfacerea unui criteriu de convergenţă, adică aproximarea corectă a mulţimii de antrenare cu o eroare maximă permisă ε, de exemplu ε = 10–3 (Terashima, 2012). Considerând multiplicatorii αi şi αj , pe baza ecuaţiei 7.3 putem scrie:

(7.6) 137 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

unde

, după cum clasele corespunzătoare instanţelor celor

2 multiplicatori sunt diferite sau egale, respectiv. Prin

urmare, putem

optimiza la un moment

dat

funcţia

doar după multiplicatorul αi , menţinând ceilalţi multiplicatori constanţi. Algoritmul SMO are trei componente principale (Platt, 1998; Ramirez-Padron, 2007):

•

o metodă analitică de optimizare a celor doi multiplicatori aleşi;

•

o euristică pentru alegerea multiplicatorilor care vor fi optimizaţi împreună la un moment dat;

•

o metodă pentru calcularea pragului b.

7.3. Optimizarea comună a unei perechi de multiplicatori Pentru a uşura înţelegerea, vom nota, ca şi Platt, primul multiplicator ales cu α1 şi pe cel de-al doilea cu α2. De asemenea, notăm cu valorile „vechi” dinaintea procesului de optimizare şi cu

şi

şi valorile

„noi”, optimizate. Ştim că suma

trebuie să rămână constantă după

optimizarea lui α1 şi α2. Această condiţie poate fi scrisă astfel: (7.7)

unde s = y1y2.

138 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

Ecuaţiile 7.7 şi 7.2 impun ca valorile actualizate ale multiplicatorilor să rămână pe un segment de dreaptă precum cele din figura 7.4 (Platt, 1999a).

Figura 7.4. Restricţiile de la actualizarea unei perechi de multiplicatori

Paşii urmaţi sunt următorii:

•

rezolvarea problemei de optimizare în α2 respectând relaţia ;

•

readucerea, dacă este cazul, a valorii noi a lui α2 într-un interval acceptabil [L, H] astfel încât în final

•

;

calcularea noii valori pentru α1.

Folosind ecuaţia 7.7, dacă y1 ≠ y2, α2 trebuie să se încadreze în următoarele limite:

(7.8) .

Dacă y1 = y2, aceste limite vor fi:

139 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

(7.9)

Inteligenţă artificială: maşini cu vectori suport

(7.10) .

(7.11)

Platt propune o expresie generală pentru L şi H, evitând testul după valorile claselor, y1 şi y2:

(7.12)

.

(7.13)

În continuare, funcţia de maximizat se consideră a fi

,

ceilalţi multiplicatori fiind trataţi ca nişte constante. Substituind α1 cu o funcţie de α2, vom avea de optimizat

, rezolvând:

.

Nu vom include aici expresia lui

(7.14)

, deoarece este destul de

complexă şi considerăm că aceste calcule matematice nu sunt esenţiale pentru înţelegerea algoritmului. Este suficient să menţionăm că

este

o funcţie cuadratică în α2: ,

unde

(7.15)

. Prin urmare, este uşor de optimizat.

140 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

Derivata a doua a unei funcţii f poate fi folosită pentru a vedea dacă un punct este minim sau maxim local. Astfel:

•

dacă f''(x) < 0, x este un punct de maxim local;

•

dacă f''(x) > 0, x este un punct de minim local;

•

dacă f''(x) = 0, testul este neconcludent; x poate fi un punct de inflexiune.

În cazul nostru, dacă există un maxim, vom avea:

(7.16)

iar valoarea optimă a lui α2 va fi:

,

(7.17)

este eroarea curentă pentru instanţa de antrenare i.

unde

indică funcţia de decizie cu mulţimea veche de multiplicatori lagrangieni. După calcularea valorii optime a lui α2, aceasta este adusă în intervalul

pentru a respecta condiţiile de limită:

(7.18)

Apoi este calculată noua valoare a lui α1:

141 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

.

(7.19)

În cazul în care avem mai multe instanţe de antrenare duplicat, este posibil ca η să fie 0. Pot exista două situaţii:

•

, atunci ΘD(α2) este o linie iar

Dacă

fi ori 0 ori C, valoarea care maximizează ΘD.

va

se obţine tot din

ecuaţia 7.19; •

, atunci ΘD este o constantă, nu se

Dacă

mai pot face progrese în optimizarea multiplicatorilor curenţi şi trebuie găsită o altă pereche.

7.4.

Determinarea

multiplicatorilor

pentru

optimizare Principala problemă a algoritmului SMO este alegerea unei perechi potrivite de multiplicatori în fiecare iteraţie. În acest scop, se utilizează câteva euristici (Platt, 1999a; Platt, 1999b; Ramirez-Padron, 2007). Algoritmul are două bucle de căutare. În bucla exterioară se caută un multiplicator care nu respectă condiţiile 7.5, cu o anumită eroare admisibilă ε. Prima dată bucla exterioară iterează după toate instanţele de antrenare. După prima iteraţie, bucla exterioară alternează căutarea după o singură trecere prin toate instanţele de antrenare şi iteraţii multiple după instanţele cu multiplicatori care nu sunt nici 0 şi C, adică

. În

timpul execuţiei algoritmului, multiplicatorii care au valori limită, probabil şi le vor păstra, iar ceilalţi şi le vor schimba în decursul optimizărilor.

142 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

Algoritmul se termină când toate instanţele de antrenare respectă condiţiile 7.5 cu eroarea admisibilă ε. De fiecare dată când bucla exterioară determină un prim multiplicator, bucla inferioară iterează după restul multiplicatorilor pentru a-l găsi pe cel de-al doilea. Este ales acela ca maximizează pasul de actualizare din ecuaţia 7.17. Evaluările funcţiei nucleu K sunt consumatoare de timp, aşa încât SMO aproximează pasul prin valoarea absolută a numărătorului: |E1 – E2 |. Algoritmul păstrează o valoare de rezervă (engl. “cached”) a erorii pentru fiecare instanţă al cărei multiplicator nu are o valoare limită şi apoi alege o eroare care maximizează în mod aproximativ mărimea pasului. Dacă E1 este pozitivă, algoritmul alege o instanţă cu eroarea E2 minimă. Dacă E1 este negativă, algoritmul alege o instanţă cu eroarea E2 maximă. În anumite situaţii, de exemplu când ambele instanţe au acelaşi vector de antrenare (x1 = x2), folosirea metodei de mai sus nu conduce la progresul algoritmului, adică la un pas nenul în ecuaţia 7.17. În aceste cazuri, SMO utilizează o ierarhie de euristici pentru alegerea celui de-al doilea multiplicator:

•

Dacă euristica de mai sus nu conduce la progres, algoritmul iterează după multiplicatorii care nu au valori limită, care pot determina un pas nenul;

•

Dacă nu se găsesc astfel de multiplicatori, algoritmul iterează după toate instanţele de antrenare, căutând una care să conducă la progres.

143 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

În ambele situaţii, căutarea multiplicatorilor porneşte din poziţii aleatorii, pentru a nu da importanţă mai mare instanţelor de la începutul mulţimii de antrenare. Dacă nicio instanţă nu poate conduce la progres, se alege un nou prim multiplicator şi procedura se reia cu acesta.

7.5. Determinarea pragului Determinarea multiplicatorilor

permite calcularea lui w, dar nu şi

a pragului b. Acesta trebuie calculat separat iar SMO îi recalculează valoarea după fiecare pas, pentru ca instanţele de antrenare să satisfacă toate condiţiile 7.5. Platt utilizează o mică modificare a ecuaţiei suprafeţei de separare, cu –b în loc de b. Din punct de vedere practic, nu are nicio importanţă cum considerăm semnul lui b. În continuare vom urma însă formularea lui Platt. Când

nu are valori limită, următoarea formulă forţează ieşirea

SVM să fie y1 pentru intrarea x1: . (7.20)

Analog, când

nu are valori limită, următoarea formulă forţează

ieşirea SVM să fie y2 pentru intrarea x2: . (7.21)

Mai concis, formulele 7.20 şi 7.21 pot fi scrise astfel:

144 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO

. (7.22)

Primii doi termeni de după Ei actualizează ieşirea reală a modelului fd cu noile valori ale lui α1 şi α2. Ultimul termen îndepărtează pragul vechi din funcţia de decizie. Astfel, ecuaţia 7.22 este adevărată când multiplicatorii lagrangieni nu au valori limită. În acest caz, pragurile

şi

au valori egale şi aceasta devine noua valoare a lui b. Dacă multiplicatorii au valori limită şi L ≠ H, toate valorile din intervalul

sunt praguri care conduc la respectarea condiţiilor 7.5. În

acest caz, se alege valoarea:

.

(7.23)

Utilizarea ecuaţiilor 7.20 şi 7.21 are avantajul rapidităţii calculelor, deoarece erorile pot fi memorate pentru toate instanţele ai căror multiplicatori nu sunt nici 0 nici C. Când un multiplicator care nu are o valoare limită este implicat într-o optimizare, valoarea de rezervă a erorii sale devine 0. Pentru ceilalţi multiplicatori fără valori limită, care nu sunt implicaţi într-o optimizare, erorile sunt actualizate astfel:

.(7.24)

Pentru multiplicatorii cu valori extreme (0 sau C), algoritmul va evalua eroarea calculând funcţia de decizie determinată de multiplicatorii curenţi. Avantajul principal al algoritmului SMO este consumul relativ scăzut de resurse. Spaţiul necesar este liniar în numărul de instanţe de 145 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

antrenare. Complexitatea de timp este O(k · n) unde n este numărul de instanţe de antrenare iar k este numărul mediu de candidaţi ai vectorilor suport în timpul iteraţiilor. De fapt, complexitatea de timp este în general între O(n) şi O(n2) (Ramirez-Padron, 2007). În ultimii ani, au apărut numeroşi algoritmi derivaţi din SMO care încearcă să-i crească viteza de convergenţă sau să adapteze algoritmul pentru alte probleme precum regresia sau diferite variante ale problemelor de clasificare (Shevade et al., 2000; Keerthi et al., 2001; Shao, Wu & Liao, 2013; Huanga, Shib & Suykensa, 2014). De asemenea, există şi abordări mai simple şi mai rapide, dar aproximative, pentru rezolvarea problemei de optimizare, atât în forma primară cât şi duală, precum metoda gradientului descendent stohastic (Cristianini, 2001; Zhang, 2004; Bottou, 2012).

7.6. Pseudocodul algoritmului SMO Pseudocodul algoritmului SMO (Platt, 1999a; Ramirez-Padron, 2007) este prezentat în cele ce urmează.

target = vectorul de ieşiri dorite point = matricea vectorilor de antrenare main { Se iniţializează elementele vectorului alpha cu 0 Se iniţializează pragul cu 0 –3 Se iniţializează epsilon cu o valoare mică, de exemplu 10 numChanged = 0 examineAll = true 146 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO while (numChanged > 0 or examineAll) { numChanged = 0 if (examineAll) { // iteraţie după toţi vectorii de antrenare loop i numChanged += ExamineExample(i) } else { // iteraţie după toţi vectorii de antrenare cu alpha diferiţi de 0 şi C loop i numChanged += ExamineExample(i) } if (examineAll) examineAll = false else if (numChanged == 0) examineAll = true } }

procedure ExamineExample(i2) { y2 = target[i2] alpha2 = multiplicatorul lagrangian pentru i2 // memorarea valorii de rezervă a erorii (error cache) E2 = (ieşirea curentă a SVM pentru instanţa de antrenare i2) – y2 // dacă alpha2 violează condiţiile de optimalitate, caută un alpha1 potrivit r2 = E2 * y2 if ((r2 < – epsilon && alpha2 < C) or (r2 > epsilon && alpha2 > 0)) { if ((numărul de elemente ale lui alpha diferite de 0 şi C) > 1) { i1 = alege un alt multiplicator care maximizează pasul

147 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport if (TakeStep(i1, i2)) return 1 } // iteraţie după toţi alpha diferiţi de 0 şi de C, începând cu un index aleatoriu loop i1 { if (TakeStep(i1, i2)) return 1 } // iteraţie după toţi alpha, începând cu un index aleatoriu loop i1 { if (TakeStep(i1, i2)) return 1 } } return 0 }

procedure TakeStep(i1, i2) // i1, i2 sunt indicii multiplicatorilor { if (i1 == i2) return false alpha1 = alpha[i1] // multiplicatorul lagrangian pentru i1 y1 = target[i1] // memorarea valorii de rezervă a erorii (error cache) E1 = (ieşirea curentă a SVM pentru instanţa de antrenare i1) – y1 s = y1 * y2 Se calculează L, H if (L == H) return false k11 = kernel(point[i1], point [i1]) k12 = kernel(point[i1], point [i2]) k22 = kernel(point[i2], point [i2])

148 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO eta = 2 * k12 – k11 – k22 alpha2 = alpha[i2] // multiplicatorul lagrangian pentru i2 y2 = target[i2] if (eta < 0) { a2 = alpha2 – y2 * (E1 – E2) / eta if (a2 < L) a2 = L else if (a2 > H) a2 = H } else { Lobj = ΘD pentru a2 = L Hobj = ΘD pentru a2 = H if (Lobj > Hobj + epsilon) a2 = L else if (Lobj < Hobj – epsilon) a2 = H else a2 = alpha2 } // gestionarea erorilor numerice –8 if (a2 < 10 ) a2 = 0 –8 else if (a2 > C – 10 ) a2 = C if (|a2 – alpha2| < epsilon * (a2 + alpha2 + epsilon)) return false // actualizarea primului multiplicator a1 = alpha1 + s * (alpha2 – a2) Se actualizează pragul pentru a reflecta schimbările multiplicatorilor

149 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport Se actualizează vectorul de ponderi pentru a reflecta schimbările din a1 şi a2, dacă modelul SVM este liniar Se actualizează valorile de rezervă ale erorilor folosind noii multiplicatori Se memorează a1 şi a2 în vectorul alpha: alpha[i1] = a1, alpha[i2] = a2 return true }

7.7. Exemplu de aplicare Să considerăm problema simplă din tabelul 7.1. Având în vedere complexitatea algoritmului SMO, chiar şi pentru această problemă se vor face numeroase prelucrări. Tabelul 7.1. Mulţimea de antrenare x y 1 –1 2 –1 4 1 5 1

În continuare, se prezintă modul de execuţie, pas cu pas, evidenţiind numele procedurilor din pseudocod împreună cu valorile argumentelor şi rezultatele calculelor. Pentru a urmări funcţionarea algoritmului, s-a folosit o variantă modificată a implementării lui Vuduc (1999).

Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 0, a2 = 0.000, E2 = 1.000, r2 = -1.000, alphaNonBounded = 0 Take step: i1=3 i2=0

150 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO a1=0.000 p1=5.000 y1=1 E1=-1.000 a2=0.000 p2=1.000 y2=-1 E2=1.000 L=0.000 H=10000.000 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.125 a2=0.125 a1=0.125 b1=1.500 b2=1.500 b=1.500 alpha-bound(1) = False Update error cache E[0]=0.000 E[1]=0.500 E[2]=-0.500 E[3]=0.000 Update alphas a1[3]=0.125 a2[0]=0.125 return 1 Examine example - return 1 i = 0, numChanged = 1 Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 1, a2 = 0.000, E2 = 0.500, r2 = -0.500, alphaNonBounded = 2 Find min error: imin=0 Emin=0.000e+000 Take step: i1=0 i2=1 a1=0.125 p1=1.000 y1=-1 E1=0.000 a2=0.000 p2=2.000 y2=-1 E2=0.500 L=0.000 H=0.125 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.125 a2=0.125 a1=0.000 b1=1.375 b2=1.750 b=1.750 alpha-bound(2) = False Update error cache

151 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport E[0]=-0.375 E[1]=0.000 E[2]=-1.250 E[3]=-0.875 Update alphas a1[0]=0.000 a2[1]=0.125 return 1 Examine example - return 1 i = 1, numChanged = 2 Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 2, a2 = 0.000, E2 = -1.250, r2 = -1.250, alphaNonBounded = 2 Find max error: imax=1 Emax=0.000e+000 Take step: i1=1 i2=2 a1=0.125 p1=2.000 y1=-1 E1=0.000 a2=0.000 p2=4.000 y2=1 E2=-1.250 L=0.000 H=9999.875 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.313 a2=0.313 a1=0.438 b1=3.000 b2=3.000 b=3.000 alpha-bound(1) = False Update error cache E[0]=-1.000 E[1]=0.000 E[2]=0.000 E[3]=1.000 Update alphas a1[1]=0.438 a2[2]=0.313 return 1 Examine example - return 1 i = 2, numChanged = 3

152 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 3, a2 = 0.125, E2 = 1.000, r2 = 1.000, alphaNonBounded = 3 Find min error: imin=1 Emin=0.000e+000 Take step: i1=1 i2=3 a1=0.438 p1=2.000 y1=-1 E1=0.000 a2=0.125 p2=5.000 y2=1 E2=1.000 L=0.000 H=9999.688 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.014 a2=0.014 a1=0.326 b1=2.333 b2=2.333 b=2.333 alpha-bound(1) = False Update error cache E[0]=-0.667 E[1]=0.000 E[2]=-0.667 E[3]=0.000 Update alphas a1[1]=0.326 a2[3]=0.014 return 1 Examine example - return 1 i = 3, numChanged = 4 Examine example Examine example - not in if - return 0 Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 2, a2 = 0.313, E2 = -0.667, r2 = -0.667, alphaNonBounded = 3 Find max error: imax=1 Emax=5.402e-008 Take step: i1=1 i2=2

153 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport a1=0.326 p1=2.000 y1=-1 E1=0.000 a2=0.313 p2=4.000 y2=1 E2=-0.667 L=0.000 H=9999.986 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.479 a2=0.479 a1=0.493 b1=3.000 b2=3.000 b=3.000 alpha-bound(1) = False Update error cache E[0]=-1.000 E[1]=-0.000 E[2]=-0.000 E[3]=1.000 Update alphas a1[1]=0.493 a2[2]=0.479 return 1 Examine example - return 1 Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 3, a2 = 0.014, E2 = 1.000, r2 = 1.000, alphaNonBounded = 3 Find min error: imin=2 Emin=-1.192e-007 Take step: i1=2 i2=3 a1=0.479 p1=4.000 y1=1 E1=-0.000 a2=0.014 p2=5.000 y2=1 E2=1.000 L=0.000 H=0.493 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.000 a2=0.000 a1=0.493 b1=2.944 b2=3.931 b=2.944 alpha-bound(1) = False Update error cache E[0]=-0.958

154 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 7. Algoritmul SMO E[1]=0.028 E[2]=0.000 E[3]=0.986 Update alphas a1[2]=0.493 a2[3]=0.000 return 1 Examine example - return 1 Examine example r2 < -epsilon && alpha2 < C2) || (r2 > epsilon && alpha2 > 0) i2 = 1, a2 = 0.493, E2 = 0.028, r2 = -0.028, alphaNonBounded = 2 Find min error: imin=2 Emin=1.118e-008 Take step: i1=2 i2=1 a1=0.493 p1=4.000 y1=1 E1=0.000 a2=0.493 p2=2.000 y2=-1 E2=0.028 L=0.000 H=10000.000 K=0.000 k11=0.000 k12=0.000 k22=0.000 eta=0.000 eta>0 a2=0.500 a2=0.500 a1=0.500 b1=3.000 b2=3.000 b=3.000 alpha-bound(1) = False Update error cache E[0]=-1.000 E[1]=0.000 E[2]=0.000 E[3]=1.000 Update alphas a1[2]=0.500 a2[1]=0.500 return 1 Examine example - return 1 Examine example Examine example - not in if - return 0

155 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport Examine example Examine example - not in if - return 0 Examine example Examine example - not in if - return 0 Examine example Examine example - not in if - return 0 i = 0, numChanged = 0 Examine example Examine example - not in if - return 0 i = 1, numChanged = 0 Examine example Examine example - not in if - return 0 i = 2, numChanged = 0 Examine example Examine example - not in if - return 0 i = 3, numChanged = 0

Rezultatele obţinute în final, prezentate în tabelul 7.2, sunt cele aşteptate, cu 2 vectori suport în instanţele 2 şi 4 şi un punct de separare în 3.

Tabelul 7.2. Rezultatele modelului SVM x α (w · x) + b fd(x) y 1 0 –2 –1 –1 2 –0,5 –1 –1 –1 4 0,5 1 1 1 5 0 2 1 1

156 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8

Extensii 8.1. Probleme de regresie Pentru o problemă de regresie, valoarea care trebuie învăţată nu mai este binară, ci reală. Această valoare trebuie aproximată cât mai bine de model, cu o eroare maximă admisă ε. De aceea, utilizarea SVM pentru regresie se mai numeşte ε-SVR (engl. “ε-Support Vector Regression”). Ideea de bază este determinarea funcţiei de decizie:

(8.1) astfel încât: .

(8.2)

Trebuie subliniat faptul că în expresia lui fdr lipseşte funcţia semn utilizată în ecuaţia 3.3 corespunzătoare funcţiei de decizie fd pentru maşinile cu vectori suport destinate clasificării. De asemenea, pentru a preveni supra-potrivirea, fdr trebuie să fie cât mai netedă. Figura 8.1 (Statnikov et al., 2009) ilustrează principiul metodei.

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Figura 8.1. Principiul metodei de regresie

Atunci când se permit erori mai mari, echivalentul marginii flexibile, doar punctele din exteriorul benzii ε sunt penalizate iar problema de optimizare este:

(8.3)

astfel încât: (8.4)

ξi ≥ 0.

(8.5)

cu i = 1..N. Această situaţie este reprezentată în figura 8.2 (Statnikov et al., 2009).

158 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

Figura 8.2. Margine flexibilă pentru regresie

În cazul neliniar, se va utiliza şi aici o funcţie de transformare φ(x), echivalentă cu aplicarea unui nucleu, ca în figura 8.3 (după Statnikov et al., 2009).

Figura 8.3. Utilizarea unui nucleu pentru o problemă de regresie

159 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

8.2. Probleme de clasificare cu clase multiple Multe probleme de clasificare nu sunt binare, ci implică mai multe valori pentru clasă. De exemplu, clasificarea florilor de iris sau stânjenel (Fisher, 1936) este un exemplu tipic de problemă cu o structură simplă dar nu foarte uşor de rezolvat. Mulţimea de date conţine 3 clase cu 50 de instanţe fiecare, iar fiecare clasă reprezintă un tip de iris: setosa, versicolor şi virginica. Clasa setosa este separabilă liniar de celelalte două, dar acestea la rândul lor nu sunt separabile liniar între ele. Există 4 atribute numerice: lungimea petalelor, lăţimea petalelor, lungimea sepalelor şi lăţimea sepalelor, toate exprimate în centimetri. Un alt exemplu este o problemă de clasificare a textelor, în care un document poate aparţine unui număr mare de clase, acestea reprezentând tematica (politică, economie, sport etc.) Metodele pe care le vom prezenta în continuare sunt generale şi pot fi aplicate pentru orice clasificator binar, nu doar pentru maşinile cu vectori suport. Există multe metode specifice SVM, mult mai complexe, pe care le vom aminti la finalul acestei secţiuni, însă este discutabil dacă aplicarea lor se justifică din punct de vedere practic.

8.2.1. Abordarea „una versus toate”

O metodă clasică de tratare a problemelor cu clase multiple este aşanumita una versus toate (engl. “one versus all”), care construieşte k modele, unde k este numărul de clase (Bottou et al., 1994; Hsu & Lin, 2002). Modelul i este antrenat cu toate instanţele din clasa i ca exemple pozitive (y = 1) şi toate instanţele din celelalte clase, ca exemple negative (y = –1). 160 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

După construirea celor k modele, rezultă k funcţii de decizie: . În final, o instanţă x este clasificată în clasa corespunzătoare modelului cu valoarea maximă a funcţiei de decizie:

.

(8.6)

Această metodă este potrivită şi pentru cazul în care clasele nu sunt mutual exclusive, adică o instanţă poate aparţine simultan mai multor clase (Statnikov et al., 2009). De exemplu, într-o problemă de clasificare a documentelor, un document poate aparţine atât clasei ştirilor politice, cât şi clasei corespunzătoare Italiei. Alt document poate aparţine clasei Italiei dar şi categoriei sport. Deoarece numărul de instanţe de antrenare din fiecare problemă este egal cu numărul total de instanţe N, metoda rezolvă k probleme de optimizare cuadratică cu N variabile.

8.2.2. Abordarea „toate versus toate”

O altă metodă foarte des folosită este cea denumită toate versus toate (engl. “all versus all”), care construieşte k · (k – 1) / 2 modele, fiecare fiind antrenat doar cu instanţele a 2 clase (Knerr, Personnaz & Dreyfus, 1990; Kreßel, 1999). Pentru a clasifica o instanţă x, se folosesc toţi aceşti clasificatori şi fiecare dă un vot asupra apartenenţei lui x la o anumită clasă: dacă

indică apartenenţa lui x la clasa i, atunci numărul

de voturi corespunzător clasei i este incrementat. În final, se alege clasa cu cele mai multe voturi. Dacă două clase au acelaşi număr de voturi, se poate alege în mod arbitrar prima clasă, în ordine lexicografică (Hsu & Lin, 2002). 161 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Această metodă presupune rezolvarea a k · (k – 1) / 2 probleme de optimizare cu 2N / k variabile, deoarece fiecare clasă are în medie N / k instanţe. În acest caz, antrenarea poate fi mai rapidă deoarece mulţimile de antrenare sunt mai mici decât în cazul metodei precedente (Manning, Raghavan & Schütze, 2008). Există multe metode de tratare a claselor multiple care încearcă să rezolve o singură problemă, de exemplu (Weston & Watkins, 1999; Platt, Cristianini & Shawe-Taylor, 2000; Crammer & Singer, 2001; Bordes et al., 2007; Lauer & Guermeur, 2011) ş.a., dar abordarea „toate versus toate” este probabil mai eficientă din punct de vedere practic.

8.3. Exemple În această secţiune, vom considera o variantă simplificată a problemei florilor de iris, cu 2 dimensiuni în loc de 4, dar cu aceeaşi natură: clasa setosa este separabilă liniar de celelalte două clase, iar la graniţa dintre clasele versicolor şi virginica există instanţe intercalate. Mulţimea de antrenare este prezentată în tabelul 8.1 iar reprezentarea grafică a problemei este realizată în figura 8.4. În toate experimentele de mai jos se foloseşte nucleul polinomial de gradul 2, deoarece clasele versicolor şi virginica nu sunt separabile liniar. Valoarea parametrului de cost este C = 10000.

162 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

Tabelul 8.1. Mulţimea de antrenare x1 1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

x2 0,1 0,2 0,2 0,3 0,6 1 1,6 1,6 1,7 1,8 1,4 1,5 1,5 1,6 2,5

Clasa setosa setosa setosa setosa setosa versicolor versicolor versicolor versicolor versicolor virginica virginica virginica virginica virginica

3

2.5

2

1.5

1

0.5

0 0

1

2

3

4

5

6

7

Figura 8.4. Versiune simplificată bidimensională a problemei florilor de iris

163 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

8.3.1. Abordarea „una versus toate” Pentru această abordare, trebuie să realizăm 3 modele: setosa vs. rest, versicolor vs. rest şi virginica vs. rest. În fiecare model, instanţelor clasei de referinţă le corespunde valoarea 1 pentru clasă, iar restului de instanţe, valoarea –1. Tabelele 8.2, 8.3, respectiv 8.4 prezintă rezultatele obţinute cu cele 3 modele pentru toate instanţele din mulţimea de antrenare, valorile calculate ale pragurilor fiind: –1,736, 47,796, respectiv 30,624. Tabelul 8.2. Modelul setosa vs. rest 1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

Instanţa y ∙ α ((w ∙ x) + b) 0,1 setosa 0 1,404 0,2 setosa 0 1,278 0,2 setosa 0 1,151 0,3 setosa 0 1,261 0,6 setosa 0,023 1,000 1 versicolor –0,023 –1,000 1,6 versicolor 0 –3,747 1,6 versicolor 0 –4,599 1,7 versicolor 0 –4,441 1,8 versicolor 0 –4,071 1,4 virginica 0 –5,618 1,5 virginica 0 –4,320 1,5 virginica 0 –4,538 1,6 virginica 0 –6,238 2,5 virginica 0 –7,661

164 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

Tabelul 8.3. Modelul versicolor vs. rest 1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

Instanţa y∙α ((w ∙ x) + b) 0,1 setosa 0 –27,580 0,2 setosa 0 –20,994 0,2 setosa 0 –20,500 0,3 setosa 0 –15,809 0,6 setosa –0,807 –0,998 1 versicolor 0 11,487 1,6 versicolor 0 12,000 1,6 versicolor 1214,394 1,007 1,7 versicolor 0 8,363 1,8 versicolor 0 16,656 1,4 virginica 0 –30,017 1,5 virginica –1110,934 –0,980 1,5 virginica 0 –4,215 1,6 virginica 0 –24,980 2,5 virginica –102,654 –0,935

Tabelul 8.4. Modelul virginica vs. rest 1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

Instanţa y∙α ((w ∙ x) + b) 0,1 setosa 0 –42,222 0,2 setosa 0 –46,911 0,2 setosa 0 –44,434 0,3 setosa 0 –53,001 0,6 setosa 0 –67,043 1 versicolor 0 –51,998 1,6 versicolor 0 –27,217 1,6 versicolor –1186,969 –1,006 1,7 versicolor 0 –16,310 1,8 versicolor 0 –36,061 1,4 virginica 0 59,539 1,5 virginica 1087,702 0,981 1,5 virginica 0 8,211 1,6 virginica 0 55,043 2,5 virginica 99,268 0,936

165 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Tabelul 8.5 prezintă rezultate obţinute prin combinarea celor 3 modele. Pe fiecare linie, valoarea maximă este marcată cu litere aldine. Coloana corespunzătoare indică clasa furnizată ca răspuns. Se vede că toate instanţele sunt clasificate corect. Tabelul 8.5. Rezultatele obţinute prin combinarea modelelor Instanţa 1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

0,1 0,2 0,2 0,3 0,6 1 1,6 1,6 1,7 1,8 1,4 1,5 1,5 1,6 2,5

setosa setosa setosa setosa setosa versicolor versicolor versicolor versicolor versicolor virginica virginica virginica virginica virginica

((w ∙ x) + b) ((w ∙ x) + b) ((w ∙ x) + b) setosa versicolor virginica 1,404 –27,580 –42,222 1,278 –20,994 –46,911 1,151 –20,500 –44,434 1,261 –15,809 –53,001 1,000 –0,998 –67,043 –1,000 11,487 –51,998 –3,747 12,000 –27,217 –4,599 1,007 –1,006 –4,441 8,363 –16,310 –4,071 16,656 –36,061 –5,618 –30,017 59,539 –4,320 –0,980 0,981 –4,538 –4,215 8,211 –6,238 –24,980 55,043 –7,661 –0,935 0,936

8.3.2. Abordarea „toate versus toate”

Pentru această abordare, trebuie să realizăm 3 modele: setosa vs. versicolor, setosa vs. virginica şi versicolor vs. virginica. În fiecare model, instanţelor primei clase le corespunde y = 1, iar instanţelor din a doua clasă, y = –1. Tabelele 8.6, 8.7, respectiv 8.8 prezintă rezultatele obţinute cu cele 3 modele doar pentru instanţele din perechile de clase considerate, valorile calculate ale pragurilor fiind acum: –1,736, –1,268, respectiv 30,624. 166 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

Tabelul 8.6. Modelul setosa vs. versicolor Instanţa y ∙ α ((w ∙ x) + b) 0,1 setosa 0 1,404 0,2 setosa 0 1,278 0,2 setosa 0 1,151 0,3 setosa 0 1,261 0,6 setosa 0,023 1,000 1 versicolor –0,023 –1,000 1,6 versicolor 0 –3,747 1,6 versicolor 0 –4,599 1,7 versicolor 0 –4,441 1,8 versicolor 0 –4,071

1,1 1,3 1,5 1,3 1,6 3,3 4,7 5,1 5 4,8

Tabelul 8.7. Modelul setosa vs. virginica 1,1 1,3 1,5 1,3 1,6 5,6 5 5,1 5,8 6,1

Instanţa y ∙ α ((w ∙ x) + b) 0,1 setosa 0 1,150 0,2 setosa 0 1,104 0,2 setosa 0 1,057 0,3 setosa 0 1,097 0,6 setosa 0,003 1,000 1,4 virginica 0 –1,488 1,5 virginica –0,003 –1,000 1,5 virginica 0 –1,082 1,6 virginica 0 –1,724 2,5 virginica 0 –2,270

Tabelul 8.8. Modelul versicolor vs. virginica 3,3 4,7 5,1 5 4,8 5,6 5 5,1 5,8 6,1

Instanţa y∙α ((w ∙ x) + b) 1 versicolor 0 51,998 1,6 versicolor 0 27,217 1,6 versicolor 1186,969 1,006 1,7 versicolor 0 16,310 1,8 versicolor 0 36,061 1,4 virginica 0 –59,539 1,5 virginica –1087,702 –0,981 1,5 virginica 0 –8,211 1,6 virginica 0 –55,043 2,5 virginica –99,268 –0,936

167 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Tabelul 8.9 prezintă un exemplu de combinare a rezultatelor oferite de modelele parţiale pentru instanţa cea mai mică din clasa versicolor (3,3 , 1). În modelul setosa vs. virginica, această instanţă este clasificată drept setosa, deoarece instanţa este foarte apropiată de dreapta de separare: ((w w · x) + b) = 0,252. Tabelul 8.9. Rezultatul obţinut prin combinarea modelelor pentru instanţa versicolor (3,3 , 1) Model Rezultat setosa vs. versicolor versicolor setosa vs. virginica setosa versicolor vs. virginica versicolor Vot majoritar versicolor

În consecinţă, instanţa este clasificată drept versicolor, deoarece are 2 voturi din 3 în acest sens.

8.4. Concluzii Maşinile cu vectori suport sunt foarte des utilizate pentru probleme de clasificare, regresie, dar şi pentru alte tipuri de probleme precum selectarea trăsăturilor (engl. “feature selection”) de exemplu (Brank et al., 2002; Alonso-Atienza et al., 2012) sau clasificări cu o singură clasă (engl. “one-class classification”), de exemplu (Manevitz & Yousef, 2001). Metoda se bazează pe o fundamentare matematică riguroasă, iar problema de optimizare a cărei rezolvare o presupune este cuadratică, deci fără optime locale. Transformând formularea primară în formularea duală, optimizarea nu mai depinde de dimensiunea spaţiului iniţial al problemei, ceea ce este foarte avantajos în cazul în care există multe atribute, de 168 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Capitolul 8. Extensii

exemplu la clasificarea textelor. Numărul de parametri care trebuie ales de utilizator este relativ mic. De asemenea, maşinile cu vectori suport demonstrează o capacitate foarte bună de generalizare. Pe de altă parte, alegerea tipului de nucleu, a valorilor parametrilor acestuia şi a parametrului de cost depinde mult de experienţa utilizatorului şi se face de multe ori prin încercare şi eroare. Proiectarea optimă a clasificatorilor cu clase multiple este încă o problemă deschisă. Din punct de vedere practic, timpul de calcul şi necesarul de memorie necesare sunt factori semnificativi, care trebuie luaţi în considerare mai ales pentru probleme de dimensiuni mari (Sullivan, 2008).

169 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe [1]

Aaronson, S. (2008a) Automata, Computability, and Complexity, MIT OpenCourseWare, Massachusetts Institute of Technology, lecture notes of “Probably approximately correct (PAC) learning”, http://ocw.mit.edu/courses/electrical-engineering-andcomputer-science/6-045j-automata-computability-andcomplexity-spring-2011/lecture-notes/MIT6_045JS11_lec19.pdf

[2]

Aaronson, S. (2008b) Automata, Computability, and Complexity, MIT OpenCourseWare, Massachusetts Institute of Technology, lecture notes of “More PAC learning”, http://ocw.mit.edu/ courses/electrical-engineering-and-computer-science/6-045jautomata-computability-and-complexity-spring-2011/lecturenotes/MIT6_045JS11_lec20.pdf

[3]

Alonso-Atienza, F., Rojo-Álvarez, J. L., Rosado-Muñoz, A., Vinagre, J. J., García-Alberola, A. & Camps-Valls, G. (2012) Feature selection using support vector machines and bootstrap methods for ventricular fibrillation detection, Expert Systems with Applications, vol. 39, pp. 1956-1967, http://www.uv.es/ gcamps/papers/science.pdf

[4]

Berwick, R. (2003) An Idiot’s guide to Support vector machines (SVMs), http://www.cs.ucf.edu/courses/cap6412/fall2009/papers/ Berwick2003.pdf

[5]

Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. K. (1989) Learnability and the Vapnik-Chervonenkis dimension,

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

Journal of the ACM, vol. 36, issue 4, pp. 929-965, doi: 10.1145/76359.76371 [6]

Bordes, A., Bottou, L., Gallinari, P. & Weston, J. (2007) Solving MultiClass

Support

Vector

Machines

with

LaRank,

http://www.machinelearning.org/proceedings/icml2007/papers/ 381.pdf [7]

Bottou,

L.

(2012)

Stochastic

Gradient

Descent

Tricks,

http://research.microsoft.com/pubs/192769/tricks-2012.pdf [8]

Bottou, L., Cortes, C., Denker, J., Drucker, H., Guyon, I., Jackel, L., LeCun, Y., Muller, U., Sackinger, E., Simard, P. & Vapnik, V. (1994) Comparison of classifier methods: A case study in handwriting

digit

recognition,

Proceedings

of

the

12th

International Conference on Pattern Recognition, pp. 77-78 [9]

Boyd, S. & Vandenberghe, L. (2004) Convex Optimization, Cambridge University Press

[10]

Brank, J., Grobelnik, M., Milić-Frayling, N. & Mladenić, C. (2002) Feature Selection Using Linear Support Vector Machines, Technical Report MSR-TR-2002-63, http://research.microsoft. com/pubs/69946/tr-2002-63.pdf

[11]

Burges, C. J. C. (1998) A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery, vol. 2, pp. 121-167, http://research.microsoft.com/pubs/67119/ svmtutorial.pdf

[12]

Byrne, J. H. (2014) Neuroscience Online, chapter “Introduction to Neurons and Neuronal Networks”, http://neuroscience.uth.tmc. edu/s1/introduction.html

[13]

Carrington, A., Fieguth, P. & Chen, H. H. (2014) A New Mercer Sigmoid Kernel for Clinical Data Classification, 36th Annual 172

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

International Conference of the IEEE Engineering in Medicine and

Biology

Society

(EMBC’14),

Chicago,

http://vip.uwaterloo.ca/files/publications/Carrington%20et%20al %20-%20A%20New%20 Mercer%20Sigmoid%20Kernel.pdf [14]

Champandard, A. J. (2003) AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors, New Riders Games,

chapter

“Perceptrons”,

http://flylib.com/books/en/

2.71.1.130/1/ [15]

Chang, Y. W., Hsieh, C. J., Chang, K. W., Ringgaard, M. & Lin, C. J. (2010) Training and testing low-degree polynomial data mappings via linear SVM, Journal of Machine Learning Research, vol. 11, pp. 1471-1490

[16]

Chudler,

E.

H.

(2014)

Brain

Facts

and

Figures,

https://faculty.washington.edu/chudler/facts.html [17]

Crammer, K. & Singer, Y. (2001) On the Algorithmic Implementation of Multi-class SVMs, Journal of Machine Learning Research, vol. 2, pp. 265-292

[18]

Cristianini, N. (2001) Support Vector and Kernel Machines, tutorial for the 18th International Conference on Machine Learning,

Berkshires,

Massachusetts,

http://www.support-

vector.net/icml-tutorial.pdf [19]

De Doná, J. (2004) Lagrangian Duality, http://www.eng. newcastle.edu.au/eecs/cdsc/books/cce/Slides/Duality.pdf

[20]

Doidge, N. (2007) The Brain That Changes Itself, Viking Press, United States

[21]

Droual, R. (2011) Nerve Cells and Electric Signaling, http://droualb.faculty.mjc.edu/Course%20Materials/Physiology%

173 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

20101/Chapter%20Notes/Fall%202011/chapter_7%20Fall%2020 11.htm [22]

Fisher, R. A. (1936) The use of multiple measurements in taxonomic problems, Annual Eugenics, vol. 7, part II, pp. 179188

[23]

Freudenrich, C. (2007) How Nerves Work, HowStuffWorks.com, http://health.howstuffworks.com/human-body/systems/nervoussystem/nerve5.htm/printable

[24]

Georgiou, G. M. (1997) Single-layer networks, in Fiesler, E. & Beale, R. (eds.), “Handbook of Neural Computation”, IOP Publishing Ltd and Oxford University Press

[25]

Gibbs, P. & Sugihara, H. (1997) What is Occam’s Razor?, http://math.ucr.edu/home/baez/physics/General/occam.html

[26]

Gregory, M. J. (2014) The Nervous System: Neurons, http://faculty.clintoncc.suny.edu/faculty/michael.gregory/files/ bio%20102/bio%20102%20lectures/nervous%20system/ neurons.htm

[27]

Groves, P. M. & Rebec, G. V. (1988) Introduction to Biological Psychology, 3rd edition, W. C. Brown Publishers, Dubuque, Iowa

[28]

Guestrin, C. (2005) PAC-learning, VC Dimension and Marginbased Bounds, http://www.cs.cmu.edu/~guestrin/Class/10701S05/slides/pac-vc.pdf

[29]

Gutierrez-Osuna,

R.

(2010)

Support

vector

machines,

http://research.cs.tamu.edu/prism/lectures/pr/pr_l21.pdf [30]

Hastie, T., Tibshirani, R. & Friedman, J. (2001) Elements of Statistical Learning: Data Mining, Inference and Prediction, Springer-Verlag, New York

174 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

[31]

Hazewinkel, M., ed. (2001) Mercer theorem, Encyclopedia of Mathematics, Springer

[32]

Hebb, D. O. (1949) The Organization of Behavior, Wiley & Sons, New York

[33]

Herculano-Houzel, S. (2009) The Human Brain in Numbers: A Linearly Scaled-up Primate Brain, Frontiers in Human Neuroscience, vol. 3, no. 31, doi: 10.3389/neuro.09.031.2009, http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2776484/

[34]

Hinton, G. (2008) Support Vector Machines, https://www.cs. toronto.edu/~hinton/csc2515/notes/lec10svm.ppt

[35]

Hsu, C. W. & Lin, C. J. (2002) A Comparison of Methods for Multiclass Support Vector Machines, IEEE Transactions on Neural

Networks,

vol.

13,

no.

2,

pp.

415-425,

http://cs.ecs.baylor.edu/~hamerly/courses/5325_11s/papers/svm/ hsu2001multiclass.pdf [36]

Hsu, C. W., Chang, C. C. & Lin, C. J. (2010) A Practical Guide to Support Vector Classification, http://www.csie.ntu.edu.tw/ ~cjlin/papers/guide/guide.pdf

[37]

Huanga, X., Shib, L. & Suykensa, J. A. K. (2014) Sequential minimal

optimization

Neurocomputing,

vol.

for

SVM

149,

part

with C,

pinball pp.

loss,

1596-1603,

doi:10.1016/j.neucom.2014.08.033 [38]

Hume, D. (1888) Hume’s Treatise of Human Nature, edited by L. A. Selby Bigge, Oxford, Clarendon Press, originally published 1739-40

[39]

Huson, D. (2007) SVMs and Kernel Functions, http://ab.inf.unituebingen.de/teaching/ss07/albi2/script/svm.pdf

175 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

[40]

Iyer, A. & Ghose, A. (2013) Why does the RBF (radial basis function)

kernel

map

into

infinite

dimensional

space?,

http://www.quora.com/Why-does-the-RBF-radial-basis-functionkernel-map-into-infinite-dimensional-space [41]

Kearns, M. & Vazirani, U. (1994) An Introduction to Computational Learning Theory, MIT Press, Cambridge, Massachusetts

[42]

Kecman, V. (2001) Learning and Soft Computing: Support Vector Machines, Neural Networks, and Fuzzy Logic Models, The MIT Press, Cambridge, Massachusetts

[43]

Keerthi, S. S., Shevade, S. K., Bhattacharyya, C. & Murthy, K. R. K. (2001) Improvements to Platt’s SMO Algorithm for SVM Classifier Design, Neural Computation, vol. 13, no. 3, pp. 637649, doi: 10.1162/089976601300014493

[44]

Klivans,

A.

The

(2005)

PAC

Learning

Model,

http://www.cs.utexas.edu/~klivans/f06lec2.pdf [45]

Knerr, S., Personnaz, L. & Dreyfus, G. (1990) Single-layer learning revisited: a stepwise procedure for building and training a neural network, in Fogelman, J. (ed.), „Neurocomputing: Algorithms, Architectures and Applications”, Springer-Verlag

[46]

Kreßel, U. (1999) Pairwise classification and support vector machines, in Schölkopf, B., Burges, C. J. C. & Smola, A. J. (eds.),

“Advances in Kernel Methods – Support Vector

Learning”, pp. 255-268, MIT Press, Cambridge, Massachusetts [47]

Kröse, B. & van der Smagt, P. (1996) An Introduction to Neural Networks, University of Amsterdam

176 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

[48]

Lauer, F. & Guermeur, Y. (2011) MSVMpack: a Multi-Class Support Vector Machine Package, Journal of Machine Learning Research, vol. 12, pp. 2269-2272

[49]

Leon, F. (2012) Inteligenţă artificială: raţionament probabilistic, tehnici de clasificare, Tehnopress, Iaşi

[50]

Leslie, C. (2004) String Kernels and Cluster Kernels for Protein Classification,

http://www.cs.columbia.edu/~cleslie/cs4761/

papers/string-kernel-slides.pdf [51]

Lin, C. J. (2012) Machine learning software: design and practical

use,

http://www.csie.ntu.edu.tw/~cjlin/talks/

mlss_kyoto.pdf [52]

Lin, H. T. & Lin, C. J. (2003) A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods, http://home.caltech.edu/~htlin/publication/doc/tanh.pdf

[53]

Malmivuo, J. & Plonsey, R. (1995) Bioelectromagnetism Principles and Applications of Bioelectric and Biomagnetic Fields, Oxford University Press, New York, chapter “Synapses, Receptor Cells, and Brain”, http://www.bem.fi/book/05/ 05.htm

[54]

Manevitz, L. M. & Yousef, M. (2001) One-Class SVMs for Document Classification, Journal of Machine Learning Research, vol.

2,

pp.

139-154,

http://www.jmlr.org/papers/volume2/

manevitz01a/manevitz01a.pdf [55]

Manning, C. D., Raghavan, P. & Schütze, H. (2008) Introduction to

Information

Retrieval,

Cambridge

University

Press,

http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html [56]

Mastin, L. (2010) Neurons & Synapses, http://www.humanmemory.net/brain_neurons.html

177 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

[57]

McCulloch, W. S. & Pitts, W. (1943) A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, vol. 5, pp. 115-133

[58]

Mercer, J. (1909) Functions of positive and negative type and their connection with the theory of integral equations, Philosophical Transactions of the Royal Society A, vol. 209, pp. 415-446, doi:10.1098/rsta.1909.0016

[59]

Minsky, M. L. & Papert, S. A. (1969) Perceptrons, MIT Press, Cambridge, Massachusetts

[60]

Monoyios, K. (2011) 5 Reasons Your Camera Won’t Steal My Job, Scientific American Blogs, http://blogs.scientificamerican. com/symbiartic/2011/07/12/5-reasons-your-camera-won%E2 %80%99t-steal-my-job/

[61]

Moore, A. W. (2001a) PAC-learning, http://www.autonlab.org/ tutorials/pac05.pdf

[62]

Moore, A. W. (2001b) VC-dimension for characterizing classifiers, http://www.autonlab.org/tutorials/vcdim08.pdf

[63]

Murphy, K. (2006) Learning theory, http://www.cs.ubc.ca/ ~murphyk/Teaching/CS340-Fall06/lectures/L4pac.pdf

[64]

Ng, A. (2007) Support Vector Machines, http://see.stanford.edu/ materials/aimlcs229/cs229-notes3.pdf

[65]

Ngom, A. (2010) The Perceptron, http://angom.myweb.cs. uwindsor.ca/teaching/cs574/le2.pdf

[66]

Nilsson, N. J. (1998) Introduction to Machine Learning, http://ai.stanford.edu/~nilsson/MLBOOK.pdf

[67]

Osborne, M. J. (2003) Optimization with an equality constraint: interpretation of Lagrange multiplier, https://www.economics. utoronto.ca/osborne/MathTutorial/ILMF.HTM 178

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

[68]

Osuna, E. E., Freund, R. & Girosi, F. (1997a) Support Vector Machines: Training and Applications, A. I. Memo No. 1602, C. B. C. L. Paper No. 144, MIT, Artificial Intelligence Laboratory, ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1602.pdf

[69]

Osuna, E. E., Freund, R. & Girosi, F. (1997b) Improved training algorithm for support vector machines, Proceedings of the IEEE Workshop on Neural Networks in Signal Processing, pp. 276-285

[70]

Pakkenberg, B. & Gundersen, H. J. G. (1997) Neocortical neuron number in humans: effect of sex and age, Journal of Comparative Neurology, vol. 384, pp. 312-320

[71]

Pakkenberg, B., Pelvig, D., Marner, L., Bundgaard, M. J., Gundersen, H. J. G., Nyengaard, J. R. & Regeur, L. (2003) Aging and the human neocortex, Experimental Gerontology, vol. 38, pp. 95-99

[72]

Pitts, W. & McCulloch, W. S. (1947) How we know universals: The perception of auditory and visual forms, Bulletin of Mathematical Biophysics, vol. 9, pp. 127-147

[73]

Platt, J. C. (1998) Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, Technical report

MSR-TR-98-14,

http://research.microsoft.com/pubs/

69644/tr-98-14.pdf [74]

Platt, J. C. (1999a) Fast training of Support Vector Machines using sequential minimal optimization, in Schölkopf, B., Burges, C. J. C. & Smola, A. J. (eds.), “Advances in Kernel Methods – Support Vector Learning”, pp. 185-208, MIT Press, Cambridge, Massachusetts,

http://research.microsoft.com/pubs/68391/smo-

book. pdf [75]

Platt, J. C. (1999b) Using Analytic QP and Sparseness to Speed Training of Support Vector Machines, in Kearns, S., Solla, S. A. 179

Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

& Cohn, D. A. (eds.), “Advances in Neural Information Processing Systems”, MIT Press, Cambridge, Massachusetts, http://research.microsoft.com/en-us/um/people/jplatt/smonips.pdf [76]

Platt, J. C., Cristianini, N. & Shawe-Taylor, J. (2000) Large Margin DAGs for Multiclass Classification, in Solla, S. A., Leen, T. K. & Müller, K. R. (eds.), “Advances in Neural Information Processing Systems”, pp. 547-553, MIT Press, Cambridge, Massachusetts,

http://research.microsoft.com/pubs/68541/

dagsvm.pdf [77]

Quine, W. V. O. (1960) Word and Object, MIT Press, Cambridge, Massachusetts

[78]

Quinlan, J. R. (1986) Induction of Decision Trees, Machine Learning, vol. 1, pp. 81-106

[79]

Ramirez-Padron, R. (2007) A Roadmap to SVM Sequential Minimal Optimization for Classification, http://nshorter.com/ ResearchPapers/MachineLearning/A_Roadmap_to_SVM_SMO. pdf

[80]

Ribrault, C., Sekimoto, K. & Triller, A. (2011) From the stochasticity of molecular processes to the variability of synaptic transmission, Nature Reviews Neuroscience, vol. 12, pp. 375387, doi:10.1038/nrn3025, http://www.nature.com/nrn/journal/ v12/n7/box/nrn3025_BX2.html

[81]

Rosenblatt, F. (1957) The Perceptron – a perceiving and recognizing automaton, Report 85-460-1, Cornell Aeronautical Laboratory

[82]

Rosenblatt, F. (1958) The perceptron: A probabilistic model for information storage and organization in the brain, Psychological

180 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

Review, vol 65, no. 6, pp. 386-408, http://dx.doi.org/10.1037/ h0042519 [83]

Rosenblatt, F. (1962) Principles of Neurodynamics, Spartan Books, Washington, DC

[84]

Rossius, R., Zenker, G., Ittner, A. & Dilger, W. (1998) A short note about the application of polynomial kernels with fractional degree in Support Vector Learning, Lecture Notes in Computer Science, vol. 1398, , pp 143-148

[85]

Russell, S. J. & Norvig, P. (2002) Artificial Intelligence: A Modern Approach, Prentice Hall, 2nd Edition

[86]

Schapire, R. E. (1990) The Strength of Weak Learnability, Machine

Learning,

vol.

5,

no.

2,

pp.

197-227,

doi:10.1007/bf00116037 [87]

Sewell, M. (2014) VC Dimension, http://www.svms.org/vcdimension/

[88]

Shao, X., Wu, K. & Liao, B. (2013) Single Directional SMO Algorithm for Least Squares Support Vector Machines, Computational Intelligence and Neuroscience, vol. 2013, Article ID 968438, 7 pages, http://dx.doi.org/10.1155/2013/968438

[89]

Shatz, C. (1992) The developing brain, Scientific American, vol. 267, no. 3, pp. 60-67

[90]

Shawe-Taylor, J. & Cristianini, N. (2000) Support Vector Machines and other kernel-based learning methods, Cambridge University Press

[91]

Shawe-Taylor, J., Anthony, M. & Biggs, N. L. (1993) Bounding sample size with the Vapnik-Chervonenkis dimension, Discrete Applied

Mathematics,

vol.

42,

issue

1,

pp.

65-73,

doi:10.1016/0166-218X(93)90179-R 181 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

[92]

Shevade, S. K., Keerthi, S. S., Bhattacharyya, C. & Murthy, K. R. K. (2000) Improvements to the SMO Algorithm for SVM Regression, IEEE Transactions on Neural Networks, vol. 11, no. 5, pp. 1188-1193

[93]

Statnikov, A., Hardin, D., Guyon, I. & Aliferis, C. F. (2009) A Gentle Introduction to Support Vector Machines in Biomedicine, AMIA 2009 San Francisco, http://www.nyuinformatics.org/files/ chibi/user-content/Final.pdf

[94]

Sullivan, J. (2008) Support Vector Machines, http://www.csc.kth. se/utbildning/kth/kurser/DD2427/bik08/LectureNotes/Lecture10. pdf

[95]

Tamarkin, D. A. (2011) Anatomy and Physiology, STCC Foundation Press, chapter “Synapses”, http://faculty.stcc.edu/ AandP/AP/AP1pages/nervssys/unit11/synapses.htm

[96]

Terashima,

S.

(2012)

Sequential

Minimal

Optimization,

http://web.cecs.pdx.edu/~landeckw/aml-spring-2012/slides/ smo-presentation.pdf [97]

Valiant, L. (1984) A theory of the learnable, Communications of the ACM, vol. 27, issue 11, pp. 1134-1142

[98]

Vapnik, V. & Chervonenkis A. (1968) On the uniform convergence of relative frequencies of

events to their

probabilities, Doklady Akademii Nauk, vol. 181, no. 4, URSS [99]

Vapnik, V. & Chervonenkis A. (1971) On the uniform convergence of relative frequencies of

events to their

probabilities, Theory of Probability and its Applications, vol. 16, no. 2, pp. 264-280 [100] Vapnik, V. (1982) Estimation of Dependences Based on Empirical Data, Springer-Verlag 182 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Referinţe

[101] Vapnik, V. (1995) The Nature of Statistical Learning Theory, Springer-Verlag, New York [102] Vasconcelos, N. (2009) The Karush-Kuhn-Tucker conditions and duality,

http://www.svcl.ucsd.edu/courses/ece271B-F09/

handouts/KKT.pdf [103] Vuduc, R. (1999) SMO implementation, http://www.cs.berkeley. edu/~richie/stat242b/project/src/smo/smo.c [104] Ware, D. (2013) Neurons that Fire Together Wire Together, http://www.dailyshoring.com/neurons-that-fire-together-wiretogether/ [105] Welling, M. (2005) Essentials of Convex Optimization, http://www.ics.uci.edu/~welling/classnotes/papers_class/ Convex-Opt.pdf [106] Weston, J. & Watkins, C. (1999) Support vector machines for multi-class pattern recognition, Proceedings of 7th European Symposium on Artificial Neural Networks (ESANN’99), pp. 219-224 [107] Widrow, B. & Hoff, M. E. (1960) Adaptive Switching Circuits, IRE WESCON Convention Record, vol. 4, pp. 96-104 [108] Widrow, B. (1960) An Adaptive “Adaline” Neuron Using Chemical

“Memistors”, Stanford Electronics

Laboratories

Technical Report 1553-2 [109] Wikimedia

Commons

(2014a)

Action

potential,

http://commons.wikimedia.org/wiki/File:Action_potential.svg [110] Wikimedia

Commons

(2014b)

Convex

Function,

http://commons.wikimedia.org/wiki/File:ConvexFunction.svg [111] Wikimedia

Commons

(2014c)

SVM

Polinomial,

http://commons.wikimedia.org/wiki/File:Svm_8_polinomial.JPG 183 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com

Inteligenţă artificială: maşini cu vectori suport

[112] Wortman Vaughan, J. (2011) Infinite Function Classes and VC Dimension, http://www.jennwv.com/courses/F11/lecture5.pdf [113] Zhang, T. (2004) Solving large scale linear prediction problems using stochastic gradient descent algorithms, Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, pp. 116-123, http://stat.rutgers.edu/home/tzhang/papers/ icml04-stograd.pdf [114] Zisserman, A. (2014) SVM dual, kernels and multiple classes, http://www.robots.ox.ac.uk/~az/lectures/ml/lect3.pdf

184 Florin Leon (2014). Inteligenţă artificială: maşini cu vectori suport Tehnopress, Iaşi, ISBN 978-606-687-155-6, http://florinleon.byethost24.com