invatare automata

Invatare automata

Universitatea Politehnica BucurestiAnul universitar 2008-2009

Adina Magda Floreahttp://turing.cs.pub.ro/inva_09 si

curs.cs.pub.ro

Curs nr. 3

Continut curs Invatarea inductiva ca problema de

cautare Reprezentarea ipotezelor Reprezentarea spatiului versiunilor Algoritmul de eliminare a candidatilor Invatarea conceptelor disjunctive

2

1. Problema de invatare

Invatarea descrierilor de concepte pe baza exemplelor pozitive (ex+) si negative (ex-) de invatare.

Invatarea supervizata a descrierii unui concept pe baza exemplelor prin sintetizarea unei functii booleene care clasifica cu +1 (true) instantele care apartin conceptului si cu -1 (false) instantele care nu apartin conceptului.

3

T = {x1, x2, …, xn} – multime de invatare

4

v1

v2

.

.vm

hx =

h H

h(x)

c(x) = ?

Se cunosc c(x1), … c(xi),..., c(xn) (exemple pozitive sau ex+ daca c este ne-negata sau exemple negative sau ex- daca c este negata)

Trebuie sa gasim ipoteza hH (H este multimea tuturor ipotezelor) a.i.

h(xi) = c(xi), i=1,n h(xi) = c(xi), i

2. Spatiul versiunilor Invatarea in spatiul versiunilor a fost propusa pentru

prima oara de Mitchell (1982) Invatarea inductiva - o cautare in spatiul conceptelor

(ipoteza h de invatat este de fapt descrierea conceptului care se invata).

Algoritmul de invatare in spatiul versiunilor sau algoritmul de eliminare a candidatilor.

Caracteistici: Invatare incrementala – prelucreaza cate un

exemplu pe rand, modificand ipoteza sau multimea de ipoteze curente

Strategia decizilor amanate (least commitment) – ia o decizie de modificare numai cand este fortat sa o faca

5

3. Reprezentarea ipotezelor

Reprezentarea uzuala pentru aceasta metoda este bazata pe logica cu predicate

Obiectele din universul problemei sunt caracterizate de o serie de atribute (la fel ca in ID3)

Ipoteza h de invatat este reprezentata ca o multime de expresii logice.

Descrierea exemplelor si clasificarea acestora sunt de asemenea expresii logice.

6

Reprezentarea ipotezelor

O ipoteza h este consistenta cu exemplele de invatare daca ipoteza recunoaste corect instantele pozitive ca apartinand clasei iar pe cele negative ca nefacand parte din clasa.

Consistent(h,T) = ( <xi, c(xi)> T) h(xi) = c(xi)

O ipoteza poate sa nu fie consistenta cu exemplele: un exemplu poate fi exemplu fals negativ pentru h (h

clasifica exemplul ca negativ dar exemplul este pozitiv) un exemplu poate fi exemplu fals pozitiv pentru h (h

clasifica exemplu ca pozitiv dar exemplul este de fapt negativ).

7


Spatiul versiunilor VSH,T corespunzator multimii de ipoteze H si multimii de exemple T este submultimea de ipoteze din H care sunt consistente cu toate exemplele de invatare din T.

VSH,T = { hH | Consistent(h,T)}

8

9

Exemplu: Invatarea conceptului"Ce zi este buna pentru sport?" din exemple.

Nr ex Cer Temperatura Umiditate Vant Apa Evolutie Zi buna?

1 soare tmedie normala puternic calda lafel DA (+)

2 soare tmedie mare puternic calda lafel DA (+)

3 ploaie tmica mare puternic calda schimba NU (-)

4 soare tmedie mare puternic rece schimba DA (+)

Reprezentarea unei ipoteze posibile

h1(x) = Cer(x,soare) Temp(x,tmedie) Umid(x,normala) Vant(x, puternic) Apa(x, calda) Evolutie (x, lafel)

Reprezentarea unei ipoteze posibileh1(x) = Cer(x,soare) Temp(x, tmedie) Umid(x,normala) Vant(x, puternic)

Apa(x, calda) Evolutie (x, lafel)

Reprezentare simplificatah1 = <soare, tmedie, normala, puternic, calda, lafel>

O ipoteza mai generalah2 = <soare, tmedie, _, _, _, lafel>

spune de fapth2(x) = Cer(x,soare) Temp(x, tmedie) Umid(x,y) Vant(x, z) Apa(x, u) Evolutie (x, lafel)


10

Cate ipoteze se pot forma? Daca sunt n atribute, fiecare avand m valori

atunci

|H| = mn

Presupunem ca una din aceste ipoteze va fi c(x), descrierea conceptului

4. Spatiul ipotezelor

11

Ipoteza de invatare inductiva

Ipoteza de invatare inductiva = orice ipoteza care aproximeaza functia c(x) pentru un numar suficient de mare de exemple din T va aproxima functia c suficient de bine si pentru instante necunoscute.

Invatarea conceptelor poate fi vazuta ca o cautare in spatiul H

In H se poate defini o relatie de ordine partiala "general-specific"

12

5. Generalizare si specializare O ipoteza h2(x) este o generalizarea a unei ipoteze h1(x)

dacaxT h1(x) h2(x)

Se spune ca h2 este "mai generala" (are un grad de generalitate mai mare) decat h1 sau ca h2 acopera h1

Se noteaza h2 h1

Exempluh1(x) = Cer(x,soare) Temp(x, tmedie) Umid(x,normala) Vant(x,

puternic) Apa(x, calda) Evolutie (x, lafel)

h2(x) = Cer(x,soare) Temp(x, tmedie) Umid(x,y) Vant(x, z) Apa(x, u) Evolutie (x, lafel)

xT h1(x) h2(x)

13

Generalizare si specializare

O ipoteza h2(x) este o specializare a unei ipoteze h1(x) daca

xT h2(x) h1(x) Se spune ca h2 este "mai specifica" (are un grad

de specializare mai mare) decat h1 sau ca h1 acopera h2

Se noteaza h2 h1

14

Operatori de generalizare si specializare

Inlocuirea const cu varcolor(ball, red) color(X, red)

Eliminarea unor literali din conjunctiishape(X, round) size(X, small) color(X, red)shape(X, round) color(X, red)

Adaugarea unei disjunctiishape(X, round) size(X, small) color(X, red)shape(X, round) size(X, small) (color(X, red)

color(X, blue)) Inlocuirea unei proprietati cu parintele din ierarhieis-a(tom, cat) is-a(tom, animal)

15

x1 = <soare, tmedie, normala, puternic, calda, lafel> + x2 = <soare, tmedie, mare, puternic, calda, lafel> + x3 = <ploaie, tmica, mare, puternic, calda, schimba> - x4 = <soare, tmedie, mare, puternic, rece, schimba> +

16

h0 = <, , , , , > h1 = < soare, tmedie, normala, puternic, calda, lafel> h2 = < soare, tmedie, _, puternic, calda, lafel> h3 = < soare, tmedie, _, puternic, calda, lafel> h4 = < soare, tmedie, _, puternic, _, _>

Reprezentarea spatiului versiunilor

Algoritmul de invatare trebuie sa construiasca si sa mentina VSH,T - multimea de ipoteze care sunt toate consistente cu exemplele de invatare

Cum se poate reprezenta aceasta multime care poate fi foarte mare sau chiar infinita?

Multimea H este partial ordonata prin relatiile general – specific

Reprezentarea lui H se face prin mentinerea a 2 multimi frontiera = set de ipoteze care reprezinta limitele lui H: G si S

17

Reprezentarea spatiului versiunilor

G VSH,T – multimea de ipoteze maxim generale G – ipotezele care acopera toate exemplele pozitive

dar nu includ nici un exemplu negativ (daca s-ar generaliza mai mult ar include cel putin un ex-)

S VSH,T - multimea de ipoteze maxim specifice S - ipotezele care acopera toate exemplele pozitive si

nu exclud nici un exemplu pozitiv (daca s-ar specializa mai mult ar exclude cel putin un ex+)

Fiecare element din spatiul versiunilor se afla intre aceste doua limite

VSH,T = { h H | (sS) (gG) (g h s)}

18

Algoritmul de eliminare a candidatilor 1. G ipotezele maxim generale din H2. S ipotezele maxim specifice din H3. pentru fiecare exemplu de invatare dT repeta

3.1 daca d este ex+ atunci3.1.1 elimina din G toate ipotezele inconsistente cu d3.1.2 pentru fiecare ipoteza sS care nu este consistenta

cu d executa- elimina s din S- adauga la S toate generalizarile minimale h ale

lui s care indeplinesc conditiile:- h este consistenta cu d- exista cel putin un membru gG a.i.

g h- Elimina din S orice ipoteza care este mai

generala decat alte ipoteze din S

19

AEC - cont 3.2 daca d este ex- atunci

3.2.1 elimina din S toate ipotezele inconsistente cu d3.2.2 pentru fiecare ipoteza gG care nu este consistenta

cu d executa- elimina g din G- adauga la G toate specializarile minimale h ale lui

g care indeplinesc conditiile:- h este consistenta cu d- exista cel putin un membru din sS a.i.

h s- Elimina din G orice ipoteza care este mai putin

generala decat alte ipoteze din Gsfarsit

20

Ce se intampla la sfarsit?

S si G contin un unic element - o aceeasi ipoteza – clasificare corecta

S sau G sunt vide – nu se poate clasifica S si/sau G contin mai multe elemente

(ipoteze) – clasificare partiala

21

Exemplu G0= <_, _, _, _, _, _>

S0= <, , , , , >

1. <soare, tmedie, normala, puternic, calda, lafel> +

G0=G1= <_, _, _, _, _, _>

S1= <soare, tmedie, normala, puternic, calda, lafel>

S0= <, , , , , >

2. <soare, tmedie, mare, puternic, calda, lafel> +

G0=G1=G2 <_, _, _, _, _, _>

S2= <soare, tmedie, _, puternic, calda , lafel>

S1= <soare, tmedie, normala, puternic, calda , lafel>

S0= <, , , , , >22

3. <ploaie, tmica, mare, puternic, calda, schimba> -

G0=G1=G2 <_, _, _, _, _, _>

G3={<soare, _, _, _, _, _>,<_,tmedie, _, _, _, _><_, _, _, _,_,lafel>}

S2=S3= <soare, tmedie, _, puternic, calda, lafel>


S0= <, , , , , >

4. <soare, tmedie, mare, puternic, rece, schimba> +

G0=G1=G2 <_, _, _, _, _, _>

G3={<soare, _, _, _, _, _>,<_,tmedie, _, _, _, _><_, _, _, _,_,lafel>}

G4={<soare, _, _, _, _, _>,<_,tmedie, _, _, _, _>}

S4= <soare, tmedie, _, puternic, _,_>

S2=S3= <soare, tmedie, _, puternic, calda, lafel>


S0= <, , , , , > 23

I1 <soare, tmedie, normala, puternic, rece, shimba>

I2 <ploaie, tmica, normala, slab, calda, lafel>

I3 <soare, tmedie, normala, slab, calda, lafel>

I4 <soare, tmica, normala, puternic, calda, lafel>

24

S: <soare, tmedie, _, puternic, _,_>

G: {<soare, _, _, _, _, _>,<_,tmedie, _, _, _, _>}

<soare, _, _, puternic, _,_> <soare, tmare, _, _, _,_><_,tmare, _, puternic, _,_>

I1 – pozitiv (toate ipotezele il clasifica +)

I2 - negativ

I3 – nu se stie (jumatate +, jumatate -)

I4 – 4 ipoteze -, 2 ipoteze +, deci negativ

Clasificare partiala

25

Exemplu: Invatarea conceptului"obiectul din imagine" din exemple.

Nr ex Dimensiune Culoare Tip Ob?

1 mica rosie minge DA (+)

2 mica albastra minge NU (-)

3 mare rosie minge DA (+)

4 mare rosie caramida NU (-)

Ce concept se invata?S=? G=?

6. Limitari ale metodei

Zgomot in clasificare sau in atribute – esueaza (S= sau G= )

Pt anumite ipoteze numarul de elemente din S sau G poate creste exponential cu numarul de atribute

26

7. Aplicatii

Meta-dendral Lex Aplicatii mai noi: combine SV cu alte

abordari

27

Aplicatii

Gasirea fragmentelor de molecule Fragmentele de molecule sunt secvente de

atomi conectati liniar Sunt utilizate in determinarea SAR

(Structure-Activity Relationships) – modele statistice care leaga structura chimica de activitatea biologica

Fragmentele de molecule = sabloane

28

Aplicatii Fiind data o baza de date r, un limbaj de descriere

a sabloanelor L si o restrictie q, sa se gaseasca o teorie bazata pe r si L a.i.

Th(L,r,q) = {L | q(r, ) = true} Algoritm de generare a saboanelor care satisfac

diferite restrictii peste sabloane: relatii intre sabloane frecventa maxima de aparitie a sabloanelor in datele de

test Sabloane de interes cu grad de specificitate mai

mare sau mai mic decat cel al unui sablon dat

29

8. Invatarea conceptelor disjunctive

Generalizare si specializare

Exemple de invatare1. (galben piram lucios mare +)

2. (bleu sfera lucios mic +)

3. (galben piram mat mic +)

4. (verde sfera mat mare +)

5. (galben cub lucios mare +)

6. (bleu cub lucios mic -)

7. (bleu piram lucios mare -)

30

nume concept: NUMEparte pozitiva

cluster: descriere: (galben piram lucios mare) ex: 1

parte negativaex:

nume concept: NUMEparte pozitiva

cluster: descriere: ( _ _ lucios _) ex: 1, 2

parte negativaex:

31

1. (galben piram lucios mare +)







Invatarea conceptelor disjunctive


nume concept: NUME

parte pozitiva

cluster: descriere: ( _ _ _ _)

ex: 1, 2, 3, 4, 5

parte negativa

ex: 6, 7

32

suprageneralizare









nume concept: NUME

parte pozitiva

cluster: descriere: (galben piram lucios mare)

ex: 1

cluster: descriere: ( bleu sfera lucios mic)

ex: 2

parte negativa

ex: 6, 7

33









nume concept: NUME

parte pozitiva

cluster: descriere: ( galben piram _ _)

ex: 1, 3

cluster: descriere: ( _ sfera _ _)

ex: 2, 4

parte negativa

ex: 6, 7

34









nume concept: NUME

parte pozitiva

cluster: descriere: ( galben _ _ _)

ex: 1, 3, 5

cluster: descriere: ( _ sfera _ _)

ex: 2, 4

parte negativa

ex: 6, 7

35








A daca galben sau sfera

Invatare conceptelor disjunctive prin grupare (clusterizare)

1. Fie S setul de exemple

2. Creaza PP si PN

3. Adauga toate ex- din S la PN (*comentariu) si elimina ex- din S

4. Creaza un cluster in PP si adauga primul ex+

5. S = S – ex+

6. pentru fiecare ex+ din S, ei repeta

6.1 pentru fiecare cluster Ci repeta

- Creaza descriere ei + Ci

- daca descriere nu acopera nici un ex-

atunci adauga ei la Ci

6.2 daca ei nu a fost adaugat la nici un cluster

atunci creaza un nou cluster cu ei

sfarsit

36

invatare automata

Documents