Post on 27-Jun-2015
description
transcript
Inteligenţă artificială
12. Reţele neuronale (II). Învăţarea nesupervizată Florin Leon
Universitatea Tehnică „Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare
http://florinleon.byethost24.com/curs_ia.htm
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
2
Reţele neuronale (II). Învăţarea nesupervizată
1. Maşini cu vectori suport
2. Reţele cu auto-organizare
2.1. Învăţarea hebbiană
2.2. Algoritmul Kohonen
3. Partiţionarea datelor
4. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
3
Reţele neuronale (II). Învăţarea nesupervizată
1. Maşini cu vectori suport
2. Reţele cu auto-organizare
2.1. Învăţarea hebbiană
2.2. Algoritmul Kohonen
3. Partiţionarea datelor
4. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
4
Maşini cu vectori suport
engl. “Support Vector Machines”, SVM
Boser, Guyon & Vapnik (1992)
Vapnik (1995)
Devenite populare datorită succesului în recunoaşterea cifrelor scrise de mână
Eroare de 1,1% pe mulţimea de test
Fundament teoretic solid
Performanţe experimentale foarte bune
Maşinile cu vectori suport reprezintă una dintre cele mai bune metode de învăţare din prezent
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
5
Limitele suprafeţelor de decizie
Să considerăm o problemă de clasificare liniar separabilă cu 2 clase
Există multe limite posibile
Algoritmul de învăţare al perceptronului poate găsi astfel de limite
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
6
Limitele suprafeţelor de decizie
Pot exista mai multe limite de separaţie
Care este cea mai bună?
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
7
Margini mici
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
8
Margine mare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
9
Limite de decizie cu margini mari
Limita de decizie trebuie să fie cât mai departe de datele din ambele clase
Trebuie să maximizăm marginea 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.htm
10
Vectori suport
Vectori suport
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
11
Normalizarea
h(x) = g(wTx + b); g(z) este –1 sau 1 Doar semnul lui (wTx + b) contează,
nu şi valoarea
Putem normaliza ecuaţiile (constrângerile) 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 instanţei i Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
12
Normalizarea
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
13
Marginea
Marginea m este proiecţia distanţei dintre doi vectori suport x1 şi x2 pe direcţia vectorului w
Valoarea lui m se poate obţine de exemplu scăzând ecuaţiile 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.htm
14
Marginea
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
15
Determinarea marginii
Trebuie determinaţi w şi b astfel încât marginea m = 2 / ‖w‖ să fie maximă pentru toate instanţele { xi , yi }
Respectând constrângerile: 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.htm
16
Determinarea marginii
O formulare mai bună a problemei de optimizare:
Minimizarea lui ½ ‖w‖2, respectând aceleaşi constrângeri
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.htm
17
Determinarea marginii
Dar...
SVM este în general utilizat pentru clasificarea unor date cu foarte multe dimensiuni
De exemplu, în clasificarea textelor sau detecţia spam-ului, frecvenţele de apariţie ale cuvintelor sunt atributele
Posibil mii de atribute
Teoretic, w poate fi infinit dimensional
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Problema primară
18 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
19
Dualitatea Lagrange
Rezolvarea problemei de optimizare anterioare (problema primară) este echivalentă cu rezolvarea problemei duale
Lagrangian Multiplicatori lagrangieni
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
20
Condiţiile Karush-Kuhn-Tucker
Există w*, α* şi β* (soluţiile problemei
primare, respectiv duale), astfel încât:
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Formularea problemei duale
Aplicăm condiţiile Karush-Kuhn-Tucker (diferenţialele
în raport cu w şi b să fie 0) :
21 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Formularea problemei duale
Înlocuind aceste relaţii în formula de mai sus, vom avea:
22 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
23
Problema duală
Se determină α i
şi apoi se pot calcula w şi b
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
24
Avantaj
Prin rezolvarea problemei duale se determină
α i ≥ 0
De fapt, toţi α i sunt 0 cu excepţia
multiplicatorilor corespunzători vectorilor suport
Numărul vectorilor suport este mult mai mic decât numărul instanţelor: nvs << n
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
25
Transformarea datelor
Clasele nu sunt liniar separabile
zk = (xk, xk2)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
26
Transformarea datelor
Clasele nu sunt liniar separabile
Clasele devin liniar separabile într-un spaţiu cu mai multe dimensiuni
Spaţiul atributelor
Spaţiul trăsăturilor (engl. “features”)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
27
Nuclee
Transformarea în trăsături (engl. “feature mapping”)
Nucleu (engl. “kernel”)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
28
Trucul nucleului
engl. “kernel trick”
Cantitatea necesară pentru clasificare este:
Folosind un nucleu: Calculele depind doar
de perechi (x1,x2)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
29
Trucul nucleului
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
30
Trucul nucleului
Deoarece calculele se fac doar în perechi, nu este nevoie să calculăm explicit trăsăturile instanţelor
Calcularea nucleului unei perechi de instanţe poate fi mult mai simplă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
31
Nuclee uzuale
Nucleul liniar
Nucleul polinomial
Nucleul RBF
Nucleul sigmoid
Parametri: γ > 0, d, r
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
32
Interpretare
Intuitiv, un nucleu poate fi interpretat ca o măsură a similarităţii dintre cele 2 argumente
Nucleul liniar (produsul scalar)
Nucleul RBF
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
33
Exemplu
Clasificarea proteinelor: şiruri de aminoacizi codificaţi prin caractere
Fie ϕ(x) o funcţie care numără apariţiile fiecărei
secvenţe de lungime k în şirul x
ϕ(x) este un vector cu 20k dimensiuni
20 de aminoacizi standard
Pentru subşiruri mici de 5 caractere, vom avea 3 milioane de dimensiuni
Totuşi, nucleul poate implementa un algoritm eficient de “string matching”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
34
Nuclee valide
Folosind doar nucleul, nu mai este nevoie să calculăm funcţia ϕ
Nucleul ar putea avea orice formă
Trebuie să respecte însă condiţia: K(x,z) = ϕ(x)T ϕ(x)
chiar dacă nu cunoaştem 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.htm
35
Teorema lui Mercer
Condiţia 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.htm
36
Cazurile neseparabile liniar
În unele cazuri, datele nu sunt separabile liniar nici după transformările prezentate anterior
Sau datele prezintă valori extreme (engl. “outliers”) care influenţează marginea optimă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
37
Probleme neseparabile liniar
Putem permite existenţa 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.htm
38
Probleme neseparabile liniar
Problema de optimizare primară devine:
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
39
Parametrul C
Parametrul de cost C este o măsură a erorii admise în clasificare
C 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
Valoarea lui C trebuie aleasă de utilizator şi depinde de problemă
De multe ori se alege prin încercări repetate, de exemplu: 10–5, 10–3, 0,1, 1, 10, 100, 103, 105
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
40
Problema duală
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)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Algoritmul SMO
Sequential Minimal Optimization (Platt, 1999)
Scopul său 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.htm
Ideea de bază a SMO
Optimizarea este asemănătoare metodei “hill climbing”
Se ajustează succesiv câte 2 multiplicatori αi
42 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
43
Exemplu
Să presupunem că avem 5 instanţe 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
Setăm C = 100
Mai întâi determinăm ai (i = 1, …, 5) prin
şi constrângerile:
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
44
Exemplu
Rezolvând problema de optimizare, obţinem:
a1 = 0, a2 = 2.5, a3 = 0, a4 = 7.333, a5 = 4.833
Constrângerile sunt satisfăcute
Vectorii suport sunt: {x2 = 2, x4 = 5, x5 = 6}
Funcţia discriminant este:
b se determină prin rezolvarea f(2)=1 sau f(5)=–1 sau f(6)=1, deoarece x2 şi x5 sunt pe linia iar x4 este pe linia
Toate trei dau b=9
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
45
Exemplu
Funcţia discriminant
1 2 4 5 6
clasa 2 clasa 1 clasa 1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
46
Clasificarea cu clase multiple
Maşinile cu vectori suport clasice permit rezolvarea problemelor binare (cu numai 2 clase)
Pentru a trata mai multe clase există mai multe metode, dintre care cele mai des folosite sunt:
Abordarea „una versus toate”
Abordarea „una versus una”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
47
Una versus toate
“one-versus-all” / “one-against-all”
Pentru k clase, se creează k modele
În modelul cu numărul i, SVM este antrenat cu instanţele din clasa i ca exemple pozitive şi toate celelalte instanţe (din celelalte clase) ca exemple negative
Pentru a clasifica o nouă instanţă, se apelează toate cele k modele şi se alege clasa cu funcţia de decizie maximă:
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
48
Una versus una
“one-versus-one” / “one-against-one”
Pentru k clase, se creează k ∙ (k – 1) / 2 modele corespunzătoare tuturor perechilor de clase
Pentru a clasifica o nouă instanţă, se apelează toate modelele şi fiecare model dă un vot pentru apartenenţa la o clasă
Se alege în final clasa care are cele mai multe voturi
Antrenarea poate fi mai rapidă pentru că mulţimile de antrenare sunt mai mici
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
49
Generalizarea
S-a demonstrat că probabilitatea de eroare aşteptată pentru mulţimea de test este mărginită:
E[x] = valoarea aşteptată pentru x
nvs = numărul de vectori suport
P(e) = probabilitatea erorii
l = dimensiunea mulţimii de antrenare
Capacitatea de generalizare creşte cu cât numărul de vectori suport este mai mic şi mulţimea de antrenare mai mare
Rezultatul este independent de numărul de atribute al instanţelor (de dimensiunea spaţiului problemei)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
50
Limitări
Principalele probleme care apar la lucrul cu SVM sunt legate de:
Stabilirea nucleului şi a parametrilor săi
Stabilirea parametrului de cost C
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
51
Reţele neuronale (II). Învăţarea nesupervizată
1. Maşini cu vectori suport
2. Reţele cu auto-organizare
2.1. Învăţarea hebbiană
2.2. Algoritmul Kohonen
3. Partiţionarea datelor
4. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
52
Învăţarea nesupervizată
Nu există nicio informaţie despre ieşirea dorită
Algoritmul trebuie să descopere singur relaţiile de interes din datele de intrare
Modele, regularităţi, corelaţii
Relaţiile descoperite se regăsesc în ieşire
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
53
Învăţarea hebbiană
Legea lui Hebb (1949)
Dacă 2 neuroni conectaţi sunt activaţi în acelaşi timp, ponderea conexiunii dintre ei creşte
Dacă 2 neuroni sunt activaţi în contratimp, ponderea conexiunii dintre ei scade
“Neurons that fire together, wire together”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
54
Învăţarea hebbiană
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Instabilitatea
55
Modelele liniare sunt des întâlnite la învăţarea hebbiană. În cazul unui neuron liniar, instabilitatea este mai uşor de pus în evidenţă
≥ 0
⇒ Ponderile vor creşte nelimitat
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Intrări multiple
56
Neuronul hebbian implementează o măsură de similaritate în spaţiul de intrare
O ieşire y mare înseamnă că intrarea curentă este similară cu vectorul de antrenare x care a creat ponderile
Reţeaua îşi aminteşte vectorul de antrenare, deci se comportă ca o memorie asociativă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Regula lui Oja
57
Este o normalizare a regulii hebbiene. Noua valoare a unei ponderi se împarte la norma vectorului de ponderi. Dacă o pondere creşte,
celelalte trebuie să scadă
Dacă rata de învăţare este mică, regula se poate aproxima astfel:
Regula este echivalentă cu învăţarea hebbiană cu activitate normalizată:
Normalizarea reprezintă introducerea unui factor de uitare proporţional cu pătratul ieşirii. Ponderile nu mai cresc nelimitat, dar reţeaua uită asocierile vechi. Dacă un vector de antrenare nu este prezentat frecvent, va fi uitat
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Regula lui Oja şi analiza componentelor principale
58
direcţia principală
direcţia secundară
întinderea maximă
întinderea minimă
Regula lui Oja determină un versor de ponderi w coliniar cu componenta principală a datelor de intrare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Reţea PCA
59
engl. “Principal Component Analysis”, PCA
Regula lui Sanger determină toate componentele principale, care converg succesiv:
Ponderile reprezintă cei M vectori de dimensiune D
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Avantaje PCA
Reducerea dimensionalităţii, compresia datelor
Prin selectarea proiecţiilor pe cele mai importante M dimensiuni, din cele D ale spaţiului de intrare, cu M ≤ D, se păstrează cele mai importante caracteristici ale datelor
60 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
61
Reţele neuronale (II). Învăţarea nesupervizată
1. Maşini cu vectori suport
2. Reţele cu auto-organizare
2.1. Învăţarea hebbiană
2.2. Algoritmul Kohonen
3. Partiţionarea datelor
4. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
62
Algoritmul Kohonen
engl. “Self-Organizing Map”, SOM
Harta / transformarea cu auto-organizare
Teuvo Kohonen, 1982
Algoritm de învăţare nesupervizată competitivă
Neuronii concurează pentru a fi activaţi
Învingătorul ia totul
Bazat pe ideea corespondenţelor dintre intrările senzoriale şi diferitele regiuni ale cortexului
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
63
Cortexul uman
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
64
Modelul Kohonen
spaţiul de intrare
n-D
spaţiul de ieşire
2D (sau 1D)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
65
Conexiunile laterale
Între neuroni există conexiuni laterale
Activarea unui neuron
provoacă inhibiţii sau excitaţii laterale altor neuroni, în funcţie de distanţa dintre aceştia Funcţia „pălărie mexicană”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
66
Învăţarea (I)
Neuronii sunt dispuşi într-o structură regulată: matrice (2D) sau vector (1D)
Ponderile fiecărui neuron sunt iniţializate aleatoriu
Ponderile au aceeaşi dimensionalitate ca datele de intrare
Fiecare neuron poate fi reprezentat ca un punct în spaţiul n-dimensional al intrărilor, în funcţie de valorile ponderilor sale
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
67
Învăţarea (II)
Pentru fiecare vector de intrare, se determină în spaţiul de intrare cel mai apropiat neuron (conform ponderilor acestuia)
distanţa euclidiană
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
68
Învăţarea (III)
Se determină vecinii neuronului câştigător în spaţiul de ieşire
funcţia „pălărie mexicană” simplificată
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
69
Învăţarea (IV)
Doar pentru aceşti neuroni (neuronul câştigător şi cei din vecinătatea sa), se actualizează ponderile
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
70
Efect
Ponderile neuronului (neuronilor) câştigători se deplasează puţin către vectorul de intrare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
71
Parametri
Rata de învăţare α are o valoare mică pozitivă (de exemplu 0,1 sau 0,5)
Mărimea vecinătăţii Λj
Alegerea statică: de exemplu 2
Alegerea dinamică: la început dimensiunea este jumătate sau o treime din dimensiunea stratului de ieşire (care poate fi de exemplu 10x10 sau 20x20) şi apoi scade treptat. De exemplu, după 10 epoci, dimensiunea scade cu 1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
72
Vecinătăţi topologice
1D
2D
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
73
Exemple 2D Exemplu 2D
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
74
Exemplu 1D
Proiecţie 2D → 1D
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
75
Alte exemple
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
76
Exemplu de vizualizare
Nivelul de trai în diferite ţări
Harta nu arată nivelurile propriu-zise, ci similaritatea lor: ţările cu nivel de trai asemănător au culori apropiate
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
77
Proprietăţi
Reducerea dimensionalităţii
Poate transforma un spaţiu n-dimensional într-un spaţiu 1D sau 2D
Păstrarea topologiei
Relaţiile de similaritate prezente între datele iniţiale sunt păstrate şi între datele rezultate după transformare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
78
Aplicaţii
Prelucrarea limbajului natural
Codificarea imaginilor
Analiza semnalelor biologice
Vizualizarea rezultatelor analizei datelor multidimensionale
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
79
Reţele neuronale (II). Învăţarea nesupervizată
1. Maşini cu vectori suport
2. Reţele cu auto-organizare
2.1. Învăţarea hebbiană
2.2. Algoritmul Kohonen
3. Partiţionarea datelor
4. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
80
Partiţionarea datelor
engl. “clustering”
partiţionare, grupare, clusterizare (pron. [clasterizáre])
Partiţionarea reprezintă gruparea (de obicei nesupervizată) a instanţelor astfel încât instanţele din acelaşi grup să fie mai asemănătoare între ele decât cu instanţele altor grupuri
Similaritatea presupune o măsură de distanţă; de obicei se foloseşte distanţa euclidiană iar similaritatea este o funcţie care variază invers cu distanţa
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
81
Partiţionarea cu algoritmul Kohonen
Se utilizează un singur neuron învingător
Se porneşte cu mai mulţi neuroni ale căror ponderi au valori mici, apropiate de 0
Pentru fiecare vector de intrare xi, se actualizează ponderile neuronului învingător
wr = wr + α (xi – wr)
La sfârşitul procesului, numai câţiva vectori de ponderi se dezvoltă iar aceştia indică centrele de greutate ale grupurilor (clusterelor) descoperite
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
82
Partiţionarea cu algoritmul Kohonen
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
83
Partiţionarea cu algoritmul k-medii
engl. “k-means” (Steinhaus, 1956; MacQueen, 1967)
k reprezintă numărul de grupuri
Este un parametru de intrare ales de utilizator
Algoritmul grupează mulţimea de instanţe numerice în k grupuri (clustere)
Rezultatul algoritmului este minimizarea sumei erorilor pătratice dintre centrele grupurilor şi instanţe
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
84
Algoritmul
Se iniţilizează aleatoriu cele k medii (centre) iniţiale
Se atribuie fiecărui centru instanţele cele mai apropiate de el
Se calculează centrul de greutate (media aritmetică) al (a) tuturor instanţelor atribuite unui centru şi se actualizează poziţia centrului grupului respectiv
Se repetă cei doi paşi până când nu se mai modifică poziţia
niciunui centru
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
Exemplu
85 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
86
Exemple
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
87
Segmentarea imaginilor
Imaginea din dreapta este rezultatul partiţionării cu 3 grupuri corespunzătoare nivelurilor de gri din imaginea din stânga
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
88
Probleme (I)
Grupurile vide
Abordarea 1. Centrele iniţiale se pot alege în nişte instanţe existente, astfel încât fiecare centru să aibă cel puţin o instanţă atribuită
Abordarea 2. Dacă iniţial există un centru de grup vid, se alege un alt centru în instanţa cea mai depărtată de toate celelalte centre
Valorile extreme (engl. “outliers”)
Pot influenţa rezultatele grupării
Înainte de partiţionare, în faza de pre-procesare a datelor, acestea se pot elimina
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
89
Probleme (II)
Viteza de căutare Pentru determinarea instanţelor celor mai apropiate de un
centru se pot utiliza metode precum kd-tree sau ball-tree
Convergenţa Algoritmul converge, dar găseşte de obicei un minim local al
funcţiei de eroare
Forma grupurilor Algoritmul dă rezultate bune dacă grupurile sunt convexe şi
mai ales de formă aproximativ sferică
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
90
Calitatea partiţionării
În funcţie de alegerea centrelor iniţiale, rezultatele finale pot diferi mult
O măsură a calităţii partiţionării este coeficientul de siluetă
Scopul este maximizarea similarităţii intra-grup şi minimizarea similarităţii inter-grup
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
91
Calcularea coeficientului
Pentru o instanţă, se calculează:
ai – distanţa medie faţă de instanţele din acelaşi grup
bi – distanţa minimă faţă de orice instanţă din orice alt grup
Coeficientul de siluetă al instanţei i este:
si = (bi – ai) / max(ai, bi)
si ∊ [–1, 1]
Partiţionarea este mai bună când si este mai mare, aproape de 1, adică ai << bi
Coeficientul de siluetă al unui cluster este media coeficienţilor instanţelor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
92
Exemplu
Sunt 10 grupuri în figură. Se observă că punctele mai apropiate de „graniţe” au valori mai mici ale coeficientului de siluetă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
93
Concluzii
Maşinile cu vectori suport sunt una dintre cele mai eficiente metode de clasificare la ora actuală
Învăţarea hebbiană modelează dinamica sinapselor din creierele biologice
Algoritmul Kohonen este inspirat tot din cercetările neurobiologice şi încorporează mecanisme de auto-organizare precum competiţia şi cooperarea
Algoritmul k-medii este unul dintre cei mai populari algoritmi de partiţionare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm