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
Reprezentarea ipotezelor
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)
Reprezentarea ipotezelor
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>
S1= <soare, tmedie, normala, 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>
S1= <soare, tmedie, normala, 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 +)
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 -)
Invatarea conceptelor disjunctive
Invatarea conceptelor disjunctive
nume concept: NUME
parte pozitiva
cluster: descriere: ( _ _ _ _)
ex: 1, 2, 3, 4, 5
parte negativa
ex: 6, 7
32
suprageneralizare
1. (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 -)
Invatarea conceptelor disjunctive
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
1. (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 -)
Invatarea conceptelor disjunctive
nume concept: NUME
parte pozitiva
cluster: descriere: ( galben piram _ _)
ex: 1, 3
cluster: descriere: ( _ sfera _ _)
ex: 2, 4
parte negativa
ex: 6, 7
34
1. (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 -)
Invatarea conceptelor disjunctive
nume concept: NUME
parte pozitiva
cluster: descriere: ( galben _ _ _)
ex: 1, 3, 5
cluster: descriere: ( _ sfera _ _)
ex: 2, 4
parte negativa
ex: 6, 7
35
1. (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 -)
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