inteligenta artificiala: retele neuronale 2. invatarea nesupervizata

Click here to load reader

Post on 27-Jun-2015

464 views

Category:

Documents

3 download

Embed Size (px)

DESCRIPTION

Inteligenta artificiala: Retele neuronale 2 Artificial Intelligence: Neural Networks 2

TRANSCRIPT

Inteligen artificial 12. Reele neuronale (II). nvarea nesupervizat Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 Reele neuronale (II). nvarea nesupervizat 1. Maini cu vectori suport 2. Reele cu auto-organizare 2.1. nvarea hebbian 2.2. Algoritmul Kohonen 3. Partiionarea datelor 4. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm3 Reele neuronale (II). nvarea nesupervizat 1. Maini cu vectori suport 2. Reele cu auto-organizare 2.1. nvarea hebbian 2.2. Algoritmul Kohonen 3. Partiionarea datelor 4. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm4 Maini cu vectori suport engl. Support Vector Machines, SVM Boser, Guyon & Vapnik (1992) Vapnik (1995) Devenite populare datorit succesului n recunoaterea cifrelor scrise de mn Eroare de 1,1% pe mulimea de test Fundament teoretic solid Performane experimentale foarte bune Mainile cu vectori suport reprezint una dintre cele mai bune metode de nvare din prezent Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 Limitele suprafeelor dedecizie S considerm o problem de clasificare liniar separabil cu 2 clase Exist multe limite posibile Algoritmul de nvare al perceptronului poate gsi astfel de limite Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 Limitele suprafeelor dedecizie Pot exista mai multe limite de separaie Care este cea mai bun? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Margini mici Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 Margine mare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm9 Limite de decizie cumargini mari Limita de decizie trebuie s fie ct mai departe de datele din ambele clase Trebuie s maximizmmarginea m h = 1 h = 1 h(x) = g(wTx + b) 1, dac z 0 1, dac z < 0 g(z) = Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 Vectori suport Vectori suport Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm11 Normalizarea h(x) = g(wTx + b); g(z) este 1 sau 1 Doar semnul lui (wTx + b) conteaz,nu i valoarea Putem normaliza ecuaiile (constrngerile) astfel ca n limitele care trec prin vectorii suport ai celor dou clase, wTx + b s fie 1, respectiv 1 Pentru toate punctele celor dou clase wTxi + b 1 dac yi = 1 wTxi + b 1 dac yi = 1 de exemplu: w1 x1 + w2 x2 + b yi este clasa instanei i Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm12 Normalizarea Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm13 Marginea Marginea m este proiecia distanei dintre doi vectori suport x1 i x2 pe direcia vectorului w Valoarea lui m se poate obine de exemplu scznd ecuaiile lui x1 i x2 w x1 + b = 1 w x2 + b = 1 w (x2 x1) = 2 m = w / w (x2 x1) = 2 / w Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Marginea Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Determinarea marginii Trebuie determinai w i b astfel nct marginea m = 2 / w s fie maximpentru toate instanele { xi , yi } Respectnd constrngerile: wTxi + b 1 dac yi = 1 wTxi + b 1 dac yi = 1 Adic: yi (wTxi + b) 1 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm16 Determinarea marginii O formulare mai bun a problemei de optimizare: Minimizarea lui w2, respectnd aceleai constrngeri Problem de optimizare cuadratic Se poate rezolva cu metode tipice de optimizare,de exemplu cu un algoritm evolutiv Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm17 Determinarea marginii Dar... SVM este n general utilizat pentru clasificarea unor date cu foarte multe dimensiuni De exemplu, n clasificarea textelor sau deteciaspam-ului, frecvenele de apariie ale cuvintelorsunt atributele Posibil mii de atribute Teoretic, w poate fi infinit dimensional Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmProblema primar 18 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Dualitatea Lagrange Rezolvarea problemei de optimizare anterioare (problema primar) este echivalent cu rezolvarea problemei duale LagrangianMultiplicatori lagrangieni Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 Condiiile Karush-Kuhn-Tucker Exist w*, * i * (soluiile problemei primare, respectiv duale), astfel nct: Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmFormularea problemei duale Aplicm condiiile Karush-Kuhn-Tucker (diferenialele n raport cu w i b s fie 0) : 21 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmFormularea problemei duale nlocuind aceste relaii n formula de mai sus,vom avea: 22 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Problema dual Se determin i i apoi se pot calcula w i b Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Avantaj Prin rezolvarea problemei duale se determin i 0 De fapt, toi i sunt 0 cu excepia multiplicatorilor corespunztori vectorilor suport Numrul vectorilor suport este mult mai mic dect numrul instanelor: nvs 0, d, r Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm32 Interpretare Intuitiv, un nucleu poate fi interpretat ca o msur a similaritii dintre cele 2 argumente Nucleul liniar(produsul scalar) Nucleul RBF Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm33 Exemplu Clasificarea proteinelor: iruri de aminoacizi codificai prin caractere Fie (x) o funcie care numr apariiile fiecrei secvene de lungime k n irul x (x) este un vector cu 20k dimensiuni 20 de aminoacizi standard Pentru subiruri mici de 5 caractere, vom avea3 milioane de dimensiuni Totui, nucleul poate implementa un algoritm eficient de string matching Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm34 Nuclee valide Folosind doar nucleul, nu mai este nevoie s calculm funcia Nucleul ar putea avea orice form Trebuie s respecte ns condiia: K(x,z) = (x)T (x) chiar dac nu cunoatem sau nu ne intereseaz forma lui Fie matricea nucleului K o matrice n care elementele Kij = K(x(i), x(j)) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm35 Teorema lui Mercer Condiia necesar i suficient pentru ca un nucleu real s fie valid este ca matricea nucleului s fie simetric i pozitiv semidefinit Kij = Kji zT K z 0, z Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm36 Cazurile neseparabile liniar n unele cazuri, datele nu sunt separabile liniar nici dup transformrile prezentate anterior Sau datele prezint valori extreme (engl. outliers) care influeneaz marginea optim Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm37 Probleme neseparabile liniar Putem permite existena unor erori i n clasificare Hiperplanul are acum o margine flexibil (engl. soft margin) i se numesc variabile de decalaj (engl. slack variables) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm38 Probleme neseparabile liniar Problema de optimizare primar devine: Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm39 Parametrul C Parametrul de cost C este o msur a erorii admise n clasificare C controleaz compromisul dintre a permite erori pe mulimea de antrenare i a fora margini stricte Creterea valorii lui C mrete costul clasificrii greite a instanelor i determin crearea unui model mai precis dar care poate s nu generalizeze bine Valoarea lui C trebuie aleas de utilizator i depinde de problem De multe ori se alege prin ncercri repetate, de exemplu: 105, 103, 0,1, 1, 10, 100, 103, 105 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm40 Problema dual Oarecum surprinztor, termenii i nu apar n problema dual Conteaz numai parametrul C care limiteaz multiplicatorii i Pentru instanele neclasificabile, multiplicatorii ar crete foarte mult i ar determina i apariia unor vectori suport suplimentari (cu i > 0) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmAlgoritmul SMO Sequential Minimal Optimization (Platt, 1999) Scopul su este rezolvarea problemei duale de optimizare (determinarea i) Este rapid i deci foarte potrivit pentru optimizarea problemelor de dimensiuni mari cu care lucreaz de obicei SVM Biblioteci pentru SVM SVM-light LibSVM 41 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmIdeea de baz a SMO Optimizarea este asemntoare metodei hill climbing Se ajusteaz succesiv cte 2 multiplicatori i 42 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm43 Exemplu S presupunem c avem 5 instane unidimensionale x1=1, x2=2, x3=4, x4=5, x5=6, cu 1, 2, 6 din clasa 1 i 4, 5 din clasa 2 y1=1, y2=1, y3=1, y4=1, y5=1 Folosim nucleul polinomial de grad 2 K(x, z) = (x z + 1)2 Setm C = 100 Mai nti determinm ai (i = 1, , 5) prin i constrngerile: Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm44 Exemplu Rezolvnd problema de optimizare, obinem: a1 = 0, a2 = 2.5, a3 = 0, a4 = 7.333, a5 = 4.833 Constrngerile sunt satisfcute Vectorii suport sunt: {x2 = 2, x4 = 5, x5 = 6} Funcia discriminant este: b se determin prin rezolvarea f(2)=1 sau f(5)=1 sau f(6)=1, deoarece x2 i x5 sunt pe liniaiar x4 este pe linia Toate trei dau b=9 Florin Leon, Inteligenta ar