+ All Categories
Home > Documents > Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

Date post: 27-Jun-2015
Category:
Upload: enrollinfo
View: 484 times
Download: 3 times
Share this document with a friend
Description:
Inteligenta artificiala: Retele neuronale 2 Artificial Intelligence: Neural Networks 2
93
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
Transcript
Page 1: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 2: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 3: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 4: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 5: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 6: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 7: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

7

Margini mici

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 8: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

8

Margine mare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 9: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 10: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

10

Vectori suport

Vectori suport

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 11: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 12: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

12

Normalizarea

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 13: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 14: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

14

Marginea

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 15: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 16: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 17: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 18: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

Problema primară

18 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 19: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 20: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 21: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 22: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 23: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 24: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 25: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

25

Transformarea datelor

Clasele nu sunt liniar separabile

zk = (xk, xk2)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 26: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 27: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

27

Nuclee

Transformarea în trăsături (engl. “feature mapping”)

Nucleu (engl. “kernel”)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 28: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 29: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

29

Trucul nucleului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 30: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 31: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 32: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 33: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 34: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 35: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 36: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 37: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 38: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

38

Probleme neseparabile liniar

Problema de optimizare primară devine:

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 39: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 40: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 41: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 42: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 43: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 44: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 45: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 46: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 47: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 48: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 49: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 50: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 51: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 52: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 53: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 54: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

54

Învăţarea hebbiană

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 55: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 56: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 57: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 58: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 59: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 60: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 61: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 62: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 63: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

63

Cortexul uman

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 64: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 65: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 66: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 67: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 68: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 69: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 70: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 71: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 72: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

72

Vecinătăţi topologice

1D

2D

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 73: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

73

Exemple 2D Exemplu 2D

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 74: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

74

Exemplu 1D

Proiecţie 2D → 1D

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 75: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

75

Alte exemple

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 76: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 77: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 78: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 79: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 80: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 81: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 82: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

82

Partiţionarea cu algoritmul Kohonen

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 83: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 84: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 85: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

Exemplu

85 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 86: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

86

Exemple

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 87: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 88: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 89: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 90: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 91: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 92: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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

Page 93: Inteligenta artificiala: Retele neuronale 2. Invatarea nesupervizata

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


Recommended