Zbirka nalog za predmet Osnove umetne inteligence Jure ˇ Zabkar Martin Moˇ zina 2017 Univerza v Ljubljani Fakulteta za raˇ cunalniˇ stvo in informatiko Kataloˇ zni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjiˇ znici v Ljubljani COBISS.SI-ID=290478080 ISBN 978-961-6209-91-5 (pdf) Copyright c 2017 Zaloˇ zba UL FRI. All rights reserved. Elektronska izdaja knjige je na voljo na URL: https://ailab.si/oui-zbirka-nalog.pdf Recenzenta: akad. prof. dr. Ivan Bratko, prof. dr. Marko Robnik ˇ Sikonja Zaloˇ znik: Zaloˇ zba UL FRI, Ljubljana Izdajatelj: UL Fakulteta za raˇ cunalniˇ stvo in informatiko, Ljubljana Urednik: prof. dr. Franc Solina Kazalo 1 Preiskovanje 7 1.1 Osnovni algoritmi preiskovanja . . . . . . . . . . . . . . . . . 8 1.2 A* in IDA* . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Prostor stanj malo druga ce . . . . . . . . . . . . . . . . . . . 14 1.4 Neskon cno dvoji sko drevo . . . . . . . . . . . . . . . . . . . . 16 1.5 Teoreti cna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 AND-OR graf . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.7 AND-OR graf z netrivialno hevristiko . . . . . . . . . . . . . 21 2 Planiranje 23 2.1 STRIPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Raz sirjen svet kock . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3 Falcon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Strojno u cenje 43 3.1 Dva atributa in razred . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Mi sma s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3 Mi sma s z razmerjem inf. prispevka . . . . . . . . . . . . . . . 51 3.4 Mi sma s z Gini indeksom . . . . . . . . . . . . . . . . . . . . . 55 3.5 Ocenjevanje verjetnosti . . . . . . . . . . . . . . . . . . . . . . 59 3.6 Rezanje: metoda zmanj sevanja napake . . . . . . . . . . . . . 60 3.7 Rezanje: MEP . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.8 Naivni Bayesov klasikator . . . . . . . . . . . . . . . . . . . 67 3.9 Loto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.10 Nakup ra cunalnika . . . . . . . . . . . . . . . . . . . . . . . . 71 4 Bayesove mre ze 75 4.1 Prva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Izrazi pogojne verjetnosti . . . . . . . . . . . . . . . . . . . . 78 4.3 d-lo cevanje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.4 Pre(za)pletena BM . . . . . . . . . . . . . . . . . . . . . . . . 82 4.5 Zadnja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3 4 KAZALO Predgovor Pri cujo ca zbirka nalog je pripomo cek za predmet Osnove umetne inteli- gence, ki se predava v 3. letniku univerzitetnega studija na Fakulteti za ra cunalni stvo in informatiko, Univerza v Ljubljani. Razdeljena je na stiri sklope: Preiskovanje (Jure Zabkar), Planiranje (Martin Mo zina), Strojno u cenje (Jure Zabkar) in Bayesove mre ze (Jure Zabkar). Skripta se navezuje na knjigo akad. prof. dr. Ivana Bratka, Prolog Programming for Articial Intelligence, 4. izdaja, Addison-Wesley, 2012. Hvale zna sva studentom, ki so zbirko med njenim nastajanjem upora- bljali in opozarjali na nejasnosti in pomanjkljivosti. Recenzirala sta jo akad. prof. dr. Ivan Bratko in prof. dr. Marko Robnik Sikonja, za kar sva jima iskreno hvale zna. Ljubljana, 1.6.2017 Jure Zabkar, Martin Mo zina 5 6 KAZALO Poglavje 1 Preiskovanje 7 8 POGLAVJE 1. PREISKOVANJE 1.1 Osnovni algoritmi preiskovanja Prostor stanj in hevristi cna funkcija h sta podana na sliki 1.1. Pri re sevanju upo stevajte vrstni red pri generiranju vozli s c; generirajo se po abecednem vrstnem redu. Ciljni vozli s ci sta obkro zeni. Vozli s ce s je za cetno vozli s ce. Slika 1.1 Simulirajte preiskovanje grafa z naslednjimi postopki: a) Iskanje v globino (iterativno in rekurzivno). b) Iskanje v sirino. c) Iterativno poglabljanje. d) A*. Med enakovrednimi kandidati razvijte najprej tistega, ki je bil prej generiran. e) IDA*. 1.1. OSNOVNI ALGORITMI PREISKOVANJA 9 Re sitev: a) Iskanje v globino (iterativno): Raz. Gen. Vrsta ; s s s a;b;c a;b;c a d;e d;e;b;c d i;j i;j;e;b;c i = j;e;b;c j = e;b;c e f;h;k f;h;k;b;c f g;h;i g;h;i;h;k;b;c g Iskanje v globino (rekurzivno): Generirano vozli s ce takoj razvijemo. Vrstni red razvijanja: s;a;d;i (nima naslednikov, zato sestopimo na d), j (sestopimo na a), e;f;g. Re sitev: s!a!e!f!g; cena: 8. b) Iskanje v sirino: Raz. Gen. Vrsta ; s s s a;b;c a;b;c a d;e b;c;d;e b f;h c;d;e;f;h c b;f;g d;e;f;h;b;f;g d i;j e;f;h;b;f;g;i;j e f;h;k f;h;b;f;g;i;j;f;h;k f g;h;i h;b;f;g;i;j;f;h;k;g;h;i h = b;f;g;i;j;f;h;k;g;h;i b f;h f;g;i;j;f;h;k;g;h;i;f;h f g;h;i g;i;j;f;h;k;g;h;i;f;h;g;h;i g Re sitev: s!c!g; cena: 9. 10 POGLAVJE 1. PREISKOVANJE c) Iterativno poglabljanje. Raz. Gen. Vrsta ; s s s = ; s s s a;b;c a;b;c a = b;c b = c c = ; s s s a;b;c a;b;c a d;e d;e;b;c d = e;b;c e = b;c b f;h f;h;c f = h;c h = c c b;f;g b;f;g b = f;g f = g g Re sitev: s!c!g; cena: 9. d) A*. Med enakovrednimi kandidati razvijte najprej tistega, ki je bil prej generiran. Raz. Gen. Vrsta ; s s(0 + 7) s a;b;c b(2 + 5);c(3 + 4);a(3 + 5) b f;h h(3 + 2);f(5 + 1);c(3 + 4);a(3 + 5) h = f(5 + 1);c(3 + 4);a(3 + 5) f g;h;i c(3 + 4);g(7 + 0);a(3 + 5);h(7 + 2);i(8 + 3) c b;f;g g(7 + 0);a(3 + 5);h(7 + 2);f(8 + 1);g(9 + 0);i(8 + 3);b(8 + 5) g(7 + 0) Re sitev: s!b!f!g; cena: 7. 1.1. OSNOVNI ALGORITMI PREISKOVANJA 11 e) IDA* F Raz. Gen. Vrsta 0 ; s s(0 + 7) 7 ; s s(0 + 7) s a;b;c a(3 + 5);b(2 + 5);c(3 + 4) b f;h f(5 + 1);h(3 + 2);c(3 + 4) f g;h;i g(7 + 0);h(7 + 2);i(8 + 3);h(3 + 2);c(3 + 4) g(7 + 0) Re sitev: s!b!f!g; cena: 7. V tabeli so pod crtana tista generirana vozli s ca, katerih ocena presega trenutno mejoF . Takih vozli s c seveda ne smemo razvijati; z njihovimi ocenami si pomagamo pri dolo canju nove vrednosti F . 12 POGLAVJE 1. PREISKOVANJE 1.2 A* in IDA* Izvajajte A* in IDA* na grafu na sliki 1.2. Pri re sevanju upo stevajte vrstni red pri generiranju vozli s c; generirajo se po abecednem vrstnem redu. Med enakovrednimi kandidati razvijte najprej tistega, ki je bil prej generiran. Hevristi cne ocene so podane v kvadratkih ob pripadajo cih vozli s cih. s 6 a 5 b 9 c 4 3 3 2 d 10 e 2 f 10 g 0 h 1 i 12 2 4 2 8 5 2 6 1 j 12 k 0 l 0 2 2 3 Slika 1.2 Re sitev: Simulacija A* Raz. Gen. Vrsta ; s s(0 + 6) s a;b;c c(2 + 4);a(3 + 5);b(3 + 9) c h;i a(3 + 5);h(7 + 1);b(3 + 9);i(4 + 12) a d;e h(7 + 1);e(7 + 2);b(3 + 9);d(5 + 10);i(4 + 12) h l e(7 + 2);l(10 + 0);b(3 + 9);d(5 + 10);i(4 + 12) e h;j;k h(8 + 1);k(9 + 0);l(10 + 0);b(3 + 9);d(5 + 10); i(4 + 12);j(9 + 12) h l k(9 + 0);l(10 + 0);b(3 + 9);d(5 + 10);i(4 + 12);j(9 + 12) k Re sitev: s!a!e!k; cena: 9. 1.2. A* IN IDA* 13 Simulacija IDA* F Raz. Gen. Vrsta 0 ; s s(0 + 6) 6 ; s s(0 + 6) s a;b;c a(3 + 5);b(3 + 9);c(2 + 4) c h;i h(7 + 1);i(4 + 12) 8 ; s s(0 + 6) s a;b;c a(3 + 5);b(3 + 9);c(2 + 4) a d;e d(5 + 10);e(7 + 2);c(2 + 4) c h;i h(7 + 1);i(4 + 12) h l l(10 + 0) 9 ; s s(0 + 6) s a;b;c a(3 + 5);b(3 + 9);c(2 + 4) a d;e d(5 + 10);e(7 + 2);c(2 + 4) e j;k j(9 + 12);k(9 + 0);e(7 + 2);c(2 + 4) k Re sitev: s!a!e!k; cena: 9. 14 POGLAVJE 1. PREISKOVANJE 1.3 Prostor stanj malo druga ce Prostor stanj je podan z naslednjim programom: s(a;b): s(a;c): s(b;d): s(b;e): s(c;f): s(c;g): s(d;h): s(e;i): s(f;j): goal(h): goal(i): goal(j): f(a; 2): f(b; 8): f(c; 5): f(d; 9): f(e; 7): f(f; 10): f(g; 12): f(h; 4): f(i; 10): f(j; 6): Predikat s(n;n 0 ) pomeni, da je vozli s ce n 0 naslednik vozli s ca n, predikat f(n;v) pa podaja vrednost ocenitvene funkcije f za vozli s ce n. Cene vseh povezav so enake 0. Naj bo a za cetno vozli s ce preiskovanja. a) Kako se spreminja meja med izvajanjem IDA* za ta graf? b) Katero re sitveno pot vrne IDA*? c) V kak snem vrstnem redu IDA* razvija vozli s ca (vklju cite tudi ponovno razvita vozli s ca)? d) Kaj pomeni, da preiskovalni algoritem spo stuje prioritetno zaporedje ? Ali ga IDA* v zgornjem primeru spo stuje? Re sitev: Izvajanje IDA*: F Raz. Gen. Vrsta 0 ; a a(2) 2 / a a(2) a b;c b(8);c(5) 5 / a a(2) a b;c b(8);c(5) c f;g f(10);g(12) 8 / a a(2) a b;c b(8);c(5) b d;e d(9);e(7);c(5) e i i(10);c(5) c f;g f(10);g(12) 9 / a a(2) a b;c b(8);c(5) b d;e d(9);e(7);c(5) d h h(4);e(7);c(5) h 1.3. PROSTOR STANJ MALO DRUGA CE 15 a) Spreminjanje meje F : 0; 2; 5; 8; 9 b) Re sitvena pot: a!b!d!h c) Vrstni red razvijanja vozli s c: a;a;c;a;b;e;c;a;b;d;h d) Algoritem spo stuje prioritetno zaporedje, ce razvija vozli s ca po nara s cajo ci vrednosti ocenitvene funkcijef. IDA* v zgornjem primeru ne spo stuje prioritetnega zaporedja, ker vozli s ce d razvije pred h, ceprav ima h manj so vrednost ocenitvene funkcije kot d. 16 POGLAVJE 1. PREISKOVANJE 1.4 Neskon cno dvoji sko drevo Prostor stanj je neskon cno dvoji sko drevo, kjer so cene vseh povezav enake 1. Hevristi cno funkcijo h(n), kjer je n vozli s ce, deniramo takole: h(n) = 2d(n); kjer je d(n) globina vozli s ca n v drevesu (koren drevesa ima globino 0). Za cetno vozli s ce preiskovanja je koren drevesa, ciljna vozli s ca pa so na globini 5. Preiskujemo z algoritmom IDA*. a) Kako se spreminja meja med izvajanjem IDA*? b) Kolik sna je cena re sitvene poti? c) Izra cunajte koliko najmanj in koliko najve c vozli s c generira IDA*, pre- den najde re sitev. Upo stevajte tudi morebitna ponovno generirana vozli s ca. Re sitev: a) Vedno za cnemo z mejo F = 0. V korenu jef = 0, za njegova naslednika na globini 1 pa velja f = 1 + 2 1 = 3, zato je naslednja meja F = 3. Ugotovimo, da meja raste z globino: sinovi vozli s c na globini 1 imajo f = 2 + 2 2 = 6 itn. Meja F se torej spreminja takole 0; 3; 6; 9; 12; 15. b) Cena re sitve je vsota cen poti: 1 + 1 + 1 + 1 + 1 = 5 c) V prvi iteraciji generiramo koren in njegova naslednika, se pravi 2 0 + 2 1 = 3 vozli s ca. V drugi iteraciji generiramo vsa vozli s ca iz prve iteracije in vse 2 2 = 4 njihove naslednike: 2 0 + 2 1 + 2 2 = 7. V tre- tji iteraciji ponovno generiramo vse iz prvih dveh iteracij in 2 3 = 8 njihovih naslednikov: 2 0 + 2 1 + 2 2 + 2 3 = 15. V i-ti iteraciji tako generiramo P d i=0 2 i vozli s c. Sele v peti iteraciji generiramo morebi- tna kon cna vozli s ca na globini 5 (pazite, za celi smo z globino 0, zato se stevilo iteracij in globina ne ujemata). Do zdaj smo torej gene- rirali 3 + 7 + 15 + 31 + 63 = 119 vozli s c. V najbolj sem primeru moramo generirati se 6 novih - to je skrajno leva veja drevesa, ob predpostavki, da IDA* izvajamo rekurzivno (generirano vozli s ce ta- koj razvijemo) in da je skrajno levo vozli s ce na globini 5 kon cno. Ni nam potrebno generirati njegovih naslednikov, saj ob razvijanju najprej preverimo, ce je kon cno in naslednike generiramo samo, ce ugotovimo, da ni. Generiramo torej najmanj 119 + 6 = 125 vo- zli s c. Iterativna implementacija IDA* potrebuje nekoliko ve c gene- riranih vozli s c, namesto 6 jih moramo pri steti 11: 119 + 11 = 130. Najve c vozli s c generiramo takrat, ko je kon cno vozli s ce skrajno desno 1.4. NESKON CNO DVOJI SKO DREVO 17 na globini 5. V tem primeru generiramo skoraj vsa vozli s ca na glo- bini 6, razen seveda zadnjih dveh, ki sta naslednika kon cnega vozli s ca: 119 + 2 0 + 2 1 + 2 2 + 2 3 + 2 4 + 2 5 + 2 6 2 = 119 + 127 2 = 244. 18 POGLAVJE 1. PREISKOVANJE 1.5 Teoreti cna Naj bos za cetno vozli s ce in f ocenitvena funkcija oblikef(n) =g(n)+h(n), kjer je g cena optimalne poti od s do n, h pa hevristi cna ocena. a) Kdaj je ocenitvena funkcija f monotona? Navedite preprost primer, kjer f ni monotona. Predlagajte optimisti cno hevristiko za problem preiskovanja grafa slovenskih cest, ki dobro usmerja preiskovanje? Po- dajte primer optimisti cne hevristike, ki slabo usmerja preiskovanje. b) Ali iz monotonosti sledi dejstvo, da hevristika h zado s ca izreku o po- polnosti? c) Ali velja: ce h zado s ca izreku o popolnosti, je f monotona? d) Ali A* razvija generirana vozli s ca v prioritetnem vrstnem redu, ce f ni monotona? Kaj pa IDA*? Re sitev: a) Funkcija f je monotona, ce za vsak par vozli s c n;n 0 velja: s(n;n 0 )) f(n) f(n 0 ). Pri tem predikat s(n;n 0 ) pomeni, da je n 0 naslednik vo- zli s ca n. Primer je na sliki 1.3a. Zra cna razdalja med kraji je primer optimisti cne hevristike za cestno omre zje, ki dobro usmerja preiskova- nje. Hevristika h(n) = 0 za vsak n, je tudi optimisti cna, vendar slabo usmerja preiskovanje. b) Ne, iz monotonosti ne sledi, da hevristika zado s ca izreku o popolnosti. Primer je graf na sliki 1.3b. c) Ne. Hevristika h je lahko optimisti cna (torej zado s ca izreku o popol- nosti), f pa ni monotona (slika 1.3a). d) A* razvija generirana vozli s ca v prioritetnem vrstnem redu ne glede na monotonost f, pri IDA* pa je monotonost pogoj za razvijanje v prioritetnem vrstnem redu. s 7 a 2 b 0 4 4 (a) f ni monotona: f(s) = 7, f(a) = 6 in f(b) = 8. h je optimisti cna. s 5 a 5 b 7 3 1 (b) f je monotona (f(s) = 5, f(a) = 8 in f(b) = 8), h ni optimisti cna. Slika 1.3 1.6. AND-OR GRAF 19 1.6 AND-OR graf Dan je AND-OR graf (slika spodaj). Naj bodo hevristi cne ocene vozli s c enake 0, t.j. h(N) = 0 za vsak N. Naj bo s za cetno vozli s ce. Naslednike generiramo po abecednem redu, v AND vozli s cu pa vedno razvijemo vse naslednike. Simuliraj algoritem AO*. s a b 2 5 c d e 1 1 1 f g 1 3 h i j k l 2 8 7 1 4 3 6 5 Re sitev: s 0 s 2 a 2 b 5 2 5 s 5 a 5 b 5 2 5 c 1 d 1 e 1 1 1 1 s 5 a 8 b 5 2 5 c 3 d 1 e 2 1 1 1 h 2 i 8 i 7 j 1 2 8 7 1 Slika 1.4: Najprej generiramo s, ki ima oceno F (s) = 0, in ga razvijemo. Popravimo oceno F (s) = 0 + minfF (a) = 2;F (b) = 5g = 2. Nadaljujemo z razvijanjem vozli s ca a, ki ima manj so oceno F . Generiramo vozli s ca c, d in e ter popravimo oceni za a ins: F (a) = 5 inF (s) = 5. Ker F (a) ne presega F (b), nadaljujemo z razvijanjem v istem poddrevesu, torej razvijemo c, d in e ter popravimo njihove ocene: F (c) = 1 + minfF (h) = 2;F (i) = 8g = 3, d je kon cno vozli s ce ( F (d) = 1), F (e) = 1 + minfF (i) = 7;F (j) = 1g = 2. Popravimo se oceno vozli s ca a, F (a) = 2 + (3 + 1 + 2) = 8 in vozli s ca s, F (s) = 0 + minfF (a) = 8;F (b) = 5g = 5. 20 POGLAVJE 1. PREISKOVANJE s 8 a 8 b 9 2 5 c 3 d 1 e 2 1 1 1 f 1 g 3 1 3 h 2 i 8 i 7 j 1 2 8 7 1 (a) s 9 a 14 b 9 2 5 c 9 d 1 e 2 1 1 1 f 1 g 3 1 3 h ∞ i 8 i 7 j 1 2 8 7 1 (b) Slika 1.5: Nadaljujemo v poddrevesu s korenom b: razvijemo b, pri cemer generiramo f in g. Ocena b se pri tem spremeni: F (b) = 5 + (1 + 3) = 9. (slika 1.5a). Zato se vrnemo v levo poddrevo a, kjer zdaj lahko razvijemo vozli s ce h, ki ni niti kon cno niti nima naslednikov, zato je F (h) =1. Zaradi tega se spremeni ocena vozli s ca c;F (c) = 9. Popravijo se tudi ocene F (a) = 14 in F (s) = 9 (slika 1.5b). s 14 a 14 b 17 2 5 c 9 d 1 e 2 1 1 1 f 4 g 8 1 3 h ∞ i 8 i 7 j 1 j 4 k 3 k 6 l 5 2 8 7 1 4 3 6 5 (a) s 14 a 14 2 c 9 d 1 e 2 1 1 1 i 8 j 1 8 1 (b) Slika 1.6: Nadaljujemo v poddrevesu s korenom v b in razvijemof ing, kjer je F (f) = 4 in F (g) = 8. Popravimo F (b) = 17 in F (s) = 14. Ponovno gremo v poddrevo s korenom v a, kjer razvijemo i, pri cemer ugotovimo, da je i kon cno, ocene vozli s c pa ostanejo iste. Zato nadaljujemo z razvijanjem j (ima ni zjo oceno kot i) in prav tako ugotovimo, da je kon cno. S tem smo kon cali. Re sitveno drevo je prikazano na sliki 1.6b. Cena re sitve je vsota cen vseh povezav v re sitvenem drevesu in je kar enaka oceni v korenu, F (s) = 14. 1.7. AND-OR GRAF Z NETRIVIALNO HEVRISTIKO 21 1.7 AND-OR graf z netrivialno hevristiko Za AND-OR graf iz prej snje naloge podamo se hevristi cno funkcijo. Simu- liraj algoritem AO*. N s a b c d e f g h i j k l h(N) 10 14 13 2 0 1 4 5 5 0 0 0 7 Re sitev: s 10 s 16 a 16 b 18 2 5 s 8 a 8 b 18 2 5 c 3 d 1 e 2 1 1 1 s 13 a 13 b 18 2 5 c 8 d 1 e 2 1 1 1 h 7 i 8 i 7 j 1 2 8 7 1 Slika 1.7: Najprej generiramo s, ki ima oceno F (s) = 0 + 10 = 10, in ga razvijemo. Vozli s ci a in b sta lista, zato sta njuni hevristi cni oceni enaki H(a) = h(a) in H(b) = h(b), njuni F oceni pa: F (a) = 2 + 14 = 16 in F (b) = 5 + 13 = 18. Popravimo oceno F (s) = 0 + minfF (a) = 16;F (b) = 18g = 16. Nadaljujemo z razvijanjem a in generiramo c, d in e z F ocenami F (c) = 3, F (d) = 1 in F (e) = 2. Popravimo se F (a) = 8 in F (s) = 8. Se vedno je F (a) < F (b), zato nadaljujemo z razvijanjem c, d in e. Ustrezno popravimo ocene od listov navzgor: F (c) = 8, F (d) = 1 (ugotovimo, da je d kon cno vozli s ce), F (e) = 2, F (a) = 2 + 8 + 1 + 2 = 13 in F (s) = 13. 22 POGLAVJE 1. PREISKOVANJE s 14 a 14 b 18 2 5 c 9 d 1 e 2 1 1 1 h ∞ i 8 i 7 j 1 2 8 7 1 Slika 1.8: Se vedno ostajamo v levem poddrevesu. Razvijemo najprej h, ugotovimo, da nima sinov niti ni kon cno, zato dobi oceno 1 (go- tovo ne vodi do re sitve). Takoj popravimo ocene njegovih prednikov: F (c) = 1 + minfF (h);F (i)g = 9, F (a) = 14 in F (s) = 14. Vztrajamo v istem poddrevesu, kjer je naslednji kandidat za razvijanje i. Ugotovimo, da je i kon cno vozli s ce, ocene pa se ne spremenijo, zato nadaljujemo z raz- vijanjem j, ki je spet kon cno. Ugotovimo, da obstaja poddrevo, katerega listi so vsi kon cna vozli s ca, zato kon camo. Re sitev je isto drevo kot prej, le pot do re sitve je bila kraj sa, ker je preiskovanje usmerjala dobra hevri- sti cna funkcija. Tudi cena re sitve je ista, saj cen povezav nismo spreminjali, hevristi cne ocene pa na ceno re sitve ne vplivajo. Poglavje 2 Planiranje 23 24 POGLAVJE 2. PLANIRANJE 2.1 STRIPS Imamo 3 kocke (a;b;c) in 4 mo zne pozicije (1,2,3,4), kot ka ze slika 2.1. Robot, ki premika kocke, ima na voljo le operacijo move. S to akcijo lahko prime kocko na vrhu in jo premakne ter odlo zi na drugi kocki ali na ozna ceni pozici na tleh. Stanja in akcijo opi semo z relacijama clear in on. a) V STRIPS jeziku opi site za cetno stanje s slike in akcijo move. b) V STRIPS jeziku opi site cilj planiranja. Zelimo sestaviti stolp, kjer je c spodaj, b na sredini in a na vrhu. c) Na kratko opi site osnovne korake pri planiranju s sredstvi in cilji. d) Simulirajte postopek planiranja. Uporabite preiskovanje v globino. Kaj je problem preiskovanja v globino? e) Uporabite iterativno poglablanje. Pri klasi cnem preiskovanju itera- tivno poglablanje zagotavlja optimalno re sitev. Kaj pa tu? f) Kaj je osnovni princip regresiranja ciljev. Napi site formulo. g) Simulirajte planiranje z regresijo ciljev. Uporabite iterativno pogla- blanje; za cnite z globino D = 3. Re sitev: Pri prvi nalogi bodo odgovori precej bolj podrobni, kot pri na- logah, ki sledijo. Ceprav razumevanje nekaterih re sitev zahteva malo ve c truda, lahko le na ta na cin podrobno prika zemo delovanje algoritmov plani- ranja. Naloga a: opis akcije move Stanje na sliki 2.1 opi semo z relacijama clear in on: state = [clear(2);clear(4);clear(b);clear(c);on(a; 1);on(c;a);on(b; 3)]: Slika 2.1: Za cetno stanje v svetu kock 2.1. STRIPS 25 Za imena relacij bomo, zaradi konsistentnosti z opisi v knjigi, uporabljali angle ske izraze. Z relacijo clear ozna cimo prost objekt, on pa pomeni, da prvi objekt stoji na drugem. Preostane nam se opis akcije move. Akcija ima 3 argumente: move(X;From;To); kjer X ozna cuje kocko, ki jo bomo premaknili, From in To sta za cetni in kon cni polo zaj. Akcije bomo opisali s stirimi atributi: conditions; pogoji, ki morajo veljati v trenutnem stanju, da je akcija izve- dljiva, adds; relacije, ki jih akcija doda v stanje (temu pravimo tudi pozitivni u cinki akcije), dels; relacije, ki jih akcija izbri se iz stanja (negativni u cinki), constraints; omejitve pri dolo canju vrednosti spremenljivk, s katerimi lahko ob cutno zmanj samo prostor preiskovanja. Omejitve (constraints) in pogoji (conditions) imajo na prvi pogled enako vlogo. Obi cajno v pogoje pi semo relacije, ki jih v nadaljevanju lahko dose zemo, npr. on(b; 2). V omejitvah pa so ksni pogoji, npr. \ a je kocka", in pogoji, ki prepre cujejo nesmiselne akcije, npr. premik kocke na samo sebe. Akcijo move lahko izvedemo pri naslednjih pogojih: conditions(move(X;From;To)) = [clear(X);clear(To);on(X;From)]: Kocka X mora biti prosta (sicer je ne moremo prijeti), To mora biti prost, da lahko kocko postavimo tja in X mora biti na From. Izvedba akcije v trenutnem stanju doda relacije: adds(move(X;From;To)) = [clear(From);on(X;To)]: Objekt From se po akciji sprosti in X je na mestu To. Negativni u cinki akcije so: clear(To) in on(X;From): dels(move(X;From;To)) = [clear(To);on(X;From)]: Omejitve: constraints(move(X;From;To)) = [X6=From;X6=To;To6= From;block(X)]: Omejitev X 6= To prepre cuje, da bi kocko X premaknili na samo sebe, To6= From pa prepre cuje, da bi kocko premaknili nazaj na isto mesto. Z block(X) zahtevamo, da je X kocka (sicer bi algoritem lahko posku sal premikati tudi polja 1,2,3,4). 26 POGLAVJE 2. PLANIRANJE Naloga b: opis cilja Stolp, kjer je c spodaj in a na vrhu: goals = [on(a;b);on(b;c)]: Naloga c: princip sredstev in ciljev Osnovni princip planiranja je sredstva-cilji (angl. means-ends), kjer izbiramo sredstva (akcije), ki najbolj verjetno vodijo k zadanemu cilju. Postopek ima stiri korake: 1. Izberi se nere sen cilj v goals. Cilje izbiramo po vrsti, kot so napisani. 2. Izberi akcijo, ki ta cilj doda v stanje. Vse akcije, ki dodajo izbran cilj v stanje, predstavljajo mo znosti za nadaljevanje. Za potrebe preisko- vanja akcije uredimo glede na stevilo nere senih predpogojev. 3. Omogo ci izbrano akcijo tako, da obravnava s njene predpogoje kot nove cilje. 4. Izvedi akcijo, ki doda izbran cilj v trenutno stanje. 5. Ce obstajajo nere seni cilji, se vrni na korak 1. Za preiskovanje lahko uporabimo poljuben algoritem; v globino, itera- tivno poglabljanje, A*, itd. Naloga d: preiskovanje v globino V na si domeni sveta kock bi postopek potekal takole: 1. Izberemo cilj on(a;b). 2. Za cilj poi s cemo akcijo, ki ga vzpostavi. To informacijo vsebuje mno zica adds. Akcija, ki doda relacijo on(a;b) je: move(a;From;b). Pred- pogoji zanjo so: conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Zaradi nedolo cene vrednosti From imamo 5 mo znih akcij: move(a; 1;b), move(a; 2;b), move(a; 3;b), move(a; 4;b) in move(a;c;b). Zaradi omejitev a in b nista dovoljeni vrednosti spremenljivke From. Najprej poskusimo s From = 1, ker sta potem dva predpogoja ze izpolnjena v za cetnem stanju. 3. Predpogoji [clear(a);clear(b);on(a; 1)] postanejo trenutni cilji in re- kurzivno kli cemo program za planiranje (zato znak ’ pri oznaki koraka). 1’. Izberemo cilj clear(a). 2’. Akcija: move(X;a;To). Torej, nekaj moramo premakniti iz a in postaviti drugam, da bo a prost. Predpogoji za to akcijo so: conditions(move(X;a;To)) =fclear(X);clear(To);on(X;a)g: 2.1. STRIPS 27 Vrednosti za X in To, izpolnjene ze v za cetnem stanju, so X =c in To = 2. 3’. Korak ni potreben, vsi pogoji so izpolnjeni v trenutnem stanju. 4’. Izvedemo akcijo 1:move(c;a; 2) in dobimo novo stanje tako, da iz stanja initial state izbri semo vse iz dels: clear(2);on(c;a) in dodamo vse iz adds: clear(a);on(c; 2). Novo stanje je state = [clear(4);clear(a);clear(b);clear(c);on(a; 1);on(c; 2);on(b; 3)]: 5’. Vsi cilji (predpogoji) so izpolnjeni, zaklju cimo. 3. Zdaj so izpolnjeni vsi predpogoji za akcijo move(a; 1;b). 4. Izvedemo akcijo: 2:move(a; 1;b) in dobimo stanje: state = [clear(1);clear(4);clear(a);clear(c);on(a;b);on(c; 2);on(b; 3)]: 5. Cilj on(b;c) se ni izpolnjen. Vrnemo se na korak 1. 1. Izpolnili smo prvi cilj on(a;b) in se lotimo drugega, on(b;c). 2. Ta cilj dose zemo z akcijo move(b;From;c), ki ima predpogoje: conditions(move(b;From;c)) = [clear(b);clear(c);on(b;From)]: Izberemo From = 3. 3. Re sujemo predpogoje [ clear(b);clear(c);on(b; 3)]: 1’. Izberemo cilj clear(b). 2’. Akcija: move(X;b;To) in njeni predpogoji so conditions(move(X;b;To)) = [clear(X);clear(To);on(X;b)]: Ze izpolnjene vrednosti za X in To so X =a in To = 1. 3’. Vsi pogoji so izpolnjeni. 4’. Izvedemo akcijo: 3:move(a;b; 1) in dobimo stanje state = [clear(4);clear(a);clear(b);clear(c);on(a; 1);on(c; 2);on(b; 3)]: 5’. Vsi cilji so izpolnjeni, zaklju cimo. 3 in 4. Predpogoji so izpolnjeni in izvedemo cetrto akcijo, s katero dose zemo on(b;c): 4:move(b; 3;c) in dobimo stanje state =fclear(3);clear(4);clear(a);clear(b);on(a; 1);on(c; 2);on(b;c)g: 28 POGLAVJE 2. PLANIRANJE 5. Med re sevanjem on(b;c) smo podrli ciljon(a;b) in ga moramo ponovno re sevati. Vrnemo se na korak 1. 1. Cilj: on(a;b) 2. Akcija: move(a;From;b) izpolni ta cilj in, ker predpogoji zanjo pri From = 1 v danem stanju veljajo, jo lahko (4. korak) izvedemo: 5:move(a; 1;b) Kon cno stanje je: state = [clear(1);clear(3);clear(4);clear(a);on(a;b);on(c; 2);on(b;c)]: 5. Vsi cilji so dose zeni, kon camo postopek. S planiranjem smo na sli re sitev: 1. move(c;a; 2); 2. move(a; 1;b); 3. move(a;b; 1); 4. move(b; 3;c); 5. move(a; 1;b): Re sitev ni optimalna, saj je problem re sljiv v le treh potezah. V nadalje- vanju si bomo pogledali, kako lahko najdemo kraj se re sitve z a) uporabo interativnega poglabljanja in b) regresijo ciljev. Naloga e: preiskovanje z iterativnim poglabljanjem Pri iterativnem poglabljanjem bomo postopoma pove cevali dol zino D dovo- ljenega plana. Zaradi preglednosti bomo v simulaciji nekaj korakov izpustili. Imamo isti cilj: goals = [on(a;b);on(b;c)] v na si za cetni poziciji: initial state = [clear(2);clear(4);clear(b);clear(c);on(a; 1);on(c;a);on(b; 3)]: D = 1 (najve cja dol zina plana je 1) 2.1. STRIPS 29 (d=0) Re sujemo cilje on(a;b);on(b;c). Izberemo cilj on(a;b). Akcija, ki doda on(a;b) je move(a;From;b). Pred- pogoji so: conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Kerclear(a) v za cetnem stanju ni resni cen, potrebujemo se eno akcijo. Cilja torej ne moremo re siti samo z eno akcijo. Izberemo cilj on(b;c). Akcija: move(b;From;c), predpogoji so: conditions(move(b;From;c)) = [clear(b);clear(c);on(b;From)]: Mo zne vrednosti za From so: 3; 1; 2; 4;a. Pri vrednosti From = 3 lahko izvedemo akcijomove(b; 3;c) in dose zemo on(b;c). V tem stanju se vedno ni dose zen on(a;b), torej to ni re sitev. Vse druge vrednosti za From prav tako zahtevajo dodatne akcije za uresni citev predpogojev in jih zaradi omejitve D = 1 ne moremo izpolniti. Pri D = 1 torej ne moremo najti re sitve. D = 2 (d=0) Re sujemo cilje on(a;b);on(b;c). Akcija: move(a;From;b), predpogoji so conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Mo zne vrednosti za From so: 1; 2; 3; 4;c. Nastavimo From = 1, re siti moramo: [clear(a);clear(b);on(a; 1)]: (d=1) Re sujemo cilje [clear(a);clear(b);on(a; 1)] Zdaj smo na globini 1 in lahko uporabimo le se eno akcijo, saj bomo v vsakem primeru izvedlimove(a; 1;b). Izberemo ciljclear(a), akcija: move(X;a;To). Predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; kjer so mo zne vrednosti za X in To: (c; 2); (c; 4); (c;b); (c; 1); (c; 3); (b; 2); (b; 4); (b;c); (b; 1); (b; 3): Prvi trije nabori (c; 2); (c; 4); (c;b) izpolnjujejo vse pogoje in so zato na za cetku, ( c; 1); (c; 3) izpolnjujeta le dva pogoja, itd. IzberimoX =c inTo = 2. Zdaj lahko izvedemo prvo akcijo 1:move(c;a; 2) in takoj nato se akcijo 2 :move(a; 1;b) iz prej snjega koraka. Dobimo stanje: 30 POGLAVJE 2. PLANIRANJE state = [clear(1);clear(4);clear(a);clear(c);on(a;b);on(c; 2);on(b; 3)]: V tem stanju ni izpolnjen cilj on(b;c) in ker smo naredili ze dva koraka, se vrnemo in poskusimo drugo pot. Postopek bi nadaljevali z naslednjim naborom vrednosti za X in To. Hitro opazimo, da z uporabo zgoraj na stetih vrednosti ne bi na sli re sitve in se moramo vrniti na globino d=0. (d=0) Re sujemo cilje on(a;b);on(b;c), nadaljevanje. V mno zici ciljev [ clear(a);clear(b);on(a; 1)] smo posku sali re siti clear(a), a nam ni uspelo priti do re sitve. Preostala dva cilja sta ze izpolnjena, zato jih nima smisla re sevati. Poskusimo naslednjo nastavitev za From; From = 2. Nov nabor ciljev je: [clear(a);clear(b);on(a; 2)]: Najprej bi poskusili se enkrat re siti clear(a) z istim rezultatom kot zgo- raj. Potem bi posku sali re sevati on(a; 2), a brez uspeha, saj za premik kocke a na drugo mesto potrebujemo clear(a). Enako se zgodi pri ostalih vredno- stih From. Ne preostane nam drugega, kot da izberemo cilj: on(b;c). Akcija je: move(b;From;c), predpogoji pa: conditions(move(b;From;c)) = [clear(b);clear(c);on(b;From)]: Mo zne vrednosti za From so: 3; 1; 2; 4;a. Nastavimo From = 3 in dobimo mno zico ciljev: [clear(b);clear(c);on(b; 3)]: Vsi cilji so izpolnjeni, torej so izpolnjeni predpogoji za 1:move(b; 3;c). Algoritem bi zdaj izra cunal novo stanje in potem nadaljeval z re sevanjem on(a;b). Ugotovil bi, da cilj ni re sljiv z eno akcijo. Nato bi se vrnil in posku sal s From = 1, kar pomeni, da bi najprej premaknil kocko b na polje 1 in jo potem dal na c. Spet se ne bi iz slo. To bi ponavljal se s preostalimi vrednostmi za From in vendar neuspel. S tem bi se zaklju cilo preiskovanje pri D = 2. D = 3 Vemo, da je problem re sljiv s tremi premiki. Torej bi re sitev morali najti pri D = 3. Pa jo res? 2.1. STRIPS 31 (d=0) Re sujemo cilje on(a;b);on(b;c): Izberemo cilj on(a;b), akcija: move(a;From;b), predpogoji so conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Mo zne vrednosti za From so: 1; 2; 3; 4;c. Nastavimo From = 1 in dobimo novo mno zico ciljev: [clear(a);clear(b);on(a; 1)]: (d=1) Re sujemo cilje [clear(a);clear(b);on(a;1)]: Izberemo cilj clear(a), akcija: move(X;a;To). Predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; kjer so mo zne vrednosti za X in To: (c; 2); (c; 4); (c;b);:::. Izvedemo akciji 1:move(c;a; 2) in 2:move(a; 1;b), kot pri D = 2. Zdaj ostane se re sevanje on(b;c). O citno on(b;c) ne dose zemo z eno akcijo, zato postopka ne bomo nada- ljevali. Vpra sanje je, ali je mo zno dose ci re sitev po drugi poti; npr. ce bi v koraku A spremenili vrednostFrom? Izka ze se da ne, saj algoritem posku sa najprej dose ci on(a;b), a pri tem ne uspe, saj bi moral najprej poskrbeti za on(b;c). (d=0) Re sujemo cilje on(a;b);on(b;c); nadaljevanje. Izberemoon(b;c), akcija: move(b;From;c) in nastavimoFrom = 3, kot pri D = 2. Dobimo cilje: [clear(b);clear(c);on(b; 3)]: Vsi cilji so izpolnjeni, izvedemo akcijo 1:move(b; 3;c). Spet hitro vidimo, da ne bomo uspeli z dvema akcijama, saj potrebujemo dva koraka za dosego clear(a), ki je predpogoj za akcijo, ki bi dosegla on(a;b). D = 4 (d=0) Re sujemo cilje on(a;b);on(b;c): Izberemo cilj on(a;b). Akcija: move(a;From;b), predpogoji so conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Mo zne vrednosti za From so: 1; 2; 3; 4;c. Nastavimo From = 1 in dobimo cilje: [clear(a);clear(b);on(a; 1)]: 32 POGLAVJE 2. PLANIRANJE (d=1) Re sujemo cilje [clear(a);clear(b);on(a;1)]: Izberemo cilj clear(a). Akcija: move(X;a;To). Predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; vrednosti za X in To so: (c; 2); (c; 4); (c;b); (c; 1); (c; 3); (b; 2); (b; 4); (b;c); (b; 1); (b; 3): Pri izbranih vrednostih (c; 2) lahko izvedemo akcijimove(c;a; 2) inmove(a; 1;b) in dose zemo stanje: state = [clear(1);clear(4);clear(a);clear(c);on(a;b);on(c; 2);on(b; 3)]: Ostane se re sevanje on(b;c). S preostalima dvema akcijama nam to ne uspe, saj moramo najprej umakniti a iz b, potem premakniti b na c in se enkrat a na b. Vrnimo se in poskusimo z drugimi vrednostmi za X in To. Pri (c; 4),(c;b),(c; 1),(c; 3),(b; 2) in (b; 4) naletimo na podoben problem. Sele pri X =b in To =c najdemo re sitev. Na sa akcija je torej move(b;a;c), predpogoji so: conditions(move(b;a;c)) = [clear(b);clear(c);on(b;a)]; (d=2) Re sujemo cilje [clear(b);clear(c);on(b;a)]: Izberemo on(b;a), akcija: move(b;From;a), predpogoji: conditions(move(b;From;a)) = [clear(b);clear(a);on(b;From)]; Poskusimo s From = 3, predpogoji za akcijo move(b; 3;a) so: [clear(b);clear(a);on(b; 3)]: (d=3) Re sujemo cilje [clear(b);clear(a);on(b;3)]: Izberemo clear(a). Akcija: move(X;a;To). Predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; vrednosti za X in To so: (c; 2); (c; 4); (c;b); (c; 1); (c; 3); (b; 2); (b; 4); (b;c); (b; 1); (b; 3): Tokrat re sitev najdemo ze kar pri prvem naboru vrednosti ( c; 2). Zdaj lahko izvedemo 1:move(c;a; 2) in dobimo novo stanje: state = [clear(4);clear(a);clear(b);clear(c);on(a; 1);on(b; 3);on(c; 2)]: 2.1. STRIPS 33 (d=2) Re sujemo cilje [clear(b);clear(c);on(b;a)]; nadaljevanje. Predpogoji [clear(b);clear(a);on(b; 3)] so izpolnjeni, lahko izvedemo akcijo 2:move(b; 3;a): Novo stanje: state = [clear(3);clear(4);clear(b);clear(c);on(a; 1);on(b;a);on(c; 2)]: (d=1) Re sujemo cilje [clear(a);clear(b);on(a;1)]; nadaljevanje. Izpolnjeni predpogoji [clear(b);clear(c);on(b;a)], izvedemo akcijo: 3:move(b;a;c) Novo stanje: state = [clear(3);clear(4);clear(a);clear(b);on(a; 1);on(b;c);on(c; 2)]: (d=0) Re sujemo cilje on(a;b);on(b;c): Izpolnjeni predpogoji [clear(a);clear(b);on(a; 1)], izvedemo akcijo: 3:move(a; 1;b) Novo stanje: state = [clear(1);clear(3);clear(4);clear(a);on(a;b);on(b;c);on(c; 2)]: Oba cilja sta dose zena, zaklju cimo postopek! Na sli smo re sitev: 1. move(c;a; 2); 2. move(b; 3;a); 3. move(b;a;c); 4. move(a; 1;b): Ta naloga ka ze, da je planiranje zelo povezano s preiskovanjem. Mnogo- krat se namre c zgodi, da prva izbrana akcija, ki cilj uresni ci, ni primerna. V koraku z d = 1 smo sele v sedmem poskusu z akcijo move(b;a;c) pri sli do cilja. 34 POGLAVJE 2. PLANIRANJE Naloga f: planiranje z regresijo ciljev Pri metodi sredstva-cilji se posamezni cilji re sujejo lokalno, kar mnogokrat onemogo ca poiskati najkraj so re sitev. To imenujemo Sussmanova anoma- lija. Regresiranje ciljev se problema loti globalno in posku sa dose ci vse cilje naenkrat. S tem omogo ca iskanje optimalnih planov. Postopek za cnemo tako, da iz mno zice ciljev izberemo cilj in ustrezno akcijo, s katero bi ta cilj dosegli. V naslednjem koraku se vpra samo, kaj vse bi moralo veljati, da bi bili po izvedeni izbrani akciji dose zeni vsi cilji (ne samo izbrani). Odgovor na to vpra sanje je v regresiji ciljev, ki iz prej snjih ciljev, pogojev za akcijo in u cinkov akcije izra cuna nove cilje. Od tu naprej nas zanimajo le ti novi cilji, saj ce jih uresni cimo, bomo na koncu z izbrano akcijo re sili vse za cetne cilje. Postopek se rekurzivno ponavlja dokler ne dobimo mno zice ciljev, ki so izpolnjeni ze v za cetni poziciji. Algoritem (na nivoju i; na za cetku so cilji goals(0) enaki kon cnim ciljem): 1. Ce so vsi cilji v goals(i) resni cni v za cetnem stanju, kon camo in vse akcije izvedemo v obratnem vrstnem redu. Cegoals(i) ni mo zno dose ci (nemogo ci cilji ali ni primerne akcije), se vrnemo v prostoru stanj in posku samo najti re sitev po drugi poti. 2. Ce cilji goals(i) se niso uresni ceni in so izvedljivi, izberemo cilj iz goals(i) in akcijo A, ki doda ta cilj in regresiramo cilje po naslednji formuli: goals(i + 1) =goals(i)[conditions(A)nadds(A) Pri tem moramo paziti, da A ne izbri se trenutnega cilja (v del(A) ni cilja iz goals(i), oz. presek del(A) in goals(i) je prazna mno zica). Naloga g: simuliranje algoritma z regresiranjem ciljev Za zagotavljanje najkraj se re sitve uporabimo iterativno poglabljanje. Za cnemo pri D = 3, globini D = 1 in D = 2 zaradi preglednosti izpustimo. goals(0)=[on(a;b);on(b;c)] Ali so cilji on(a;b);on(b;c) izpolnjeni v za cetni poziciji? Ne. Izberemo cilj: on(a;b). Akcija: move(a;From;b); predpogoji so: conditions(move(a;From;b)) = [clear(a);clear(b);on(a;From)]: Mo zne vrednosti za From so: 1; 2; 3; 4;c. Nastavimo From = 1. adds(move(a; 1;b)) = [clear(1);on(a;b)] dels(move(a; 1;b)) = [clear(b);on(a; 1)] 2.1. STRIPS 35 Akcijo lahko izvedemo, ker dels ne vsebuje cilja iz goals(0): Regresija ciljev: goals(1) =goals(0)[conditions(move(a; 1;b))nadds(move(a; 1;b)) = = [on(a;b);on(b;c)][ [clear(a);clear(b);on(a; 1)]n [clear(1);on(a;b)] = = [clear(a);clear(b);on(a; 1);on(b;c)]: Regresirane cilje interpretiramo takole: ce lahko pridemo v stanje, kjer veljagoals(1), bomo z akcijomove(a; 1;b) pri sli v stanje, kjer velja goals(0). Postopek nadaljujemo, dokler goals(i) niso izpolnjeni v za cetnem stanju. goals(1)=[clear(a);clear(b);on(a;1);on(b;c)] Ali so novi cilji goals(1) izpolnjeni v za cetni poziciji? Ne. Izberemo cilj: clear(a) izgoals(1) (po vrsti) in izberemo akcijomove(X;a;To). Predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; mo zne vrednosti za X in To so: (c; 2),(c; 4), (c;b), (c; 1), itd. Izberemo X =c, To = 2. adds(move(c;a; 2)) = [clear(a);on(c; 2)] dels(move(c;a; 2)) = [clear(2);on(c;a)] Akcijo lahko izvedemo, kerclear(2) inon(c;a) nista v trenutni mno zici ciljev goals(1): Regresija ciljev: goals(2) =goals(1)[conditions(move(c;a; 2))nadds(move(c;a; 2)) = = [clear(a);clear(b);on(a; 1);on(b;c)][ [clear(c);clear(2);on(c;a)]n [clear(a);on(c; 2)] = = [clear(c);clear(2);on(c;a);clear(b);on(a; 1);on(b;c)]: Tu ne moremo nadaljevati, saj cilj ni izvedljiv! Hkrati ni mo zno dose ci ciljev on(b;c) in clear(c): Zdaj lahko poskusimo z drugimi vrednostmi spremenljivk X in To, ven- dar ne bi na sli re sitve v treh ali manj korakih. Vrnemo se korak nazaj; izbrati moramo nov cilj. Cilja clear(b) in on(a; 1) v goals(1) sta v za cetnem stanju ze resni cna, izberemo cilj: on(b;c). Akcija move(b;From;c), predpogoji: conditions(move(b;From;c)) = [clear(b);clear(c);on(b;From)]: Mo zne vrednosti za From so: 3; 1; 2; 4;a. Nastavimo From = 3: adds(move(b; 3;c)) = [clear(3);on(b;c)] dels(move(b; 3;c)) = [clear(c);on(b; 3)] 36 POGLAVJE 2. PLANIRANJE V dels ni relacije, ki bi bila tudi v trenutnih ciljih, torej lahko izvedemo akcijo. Regresija ciljev: goals(2) =goals(1)[conditions(move(b; 3;c))nadds(move(b; 3;c)) = = [clear(a);clear(b);on(a; 1);on(b;c)][ [clear(b);clear(c);on(b; 3)]n [clear(3);on(b;c)] = = [clear(a);clear(b);clear(c);on(a; 1);on(b; 3)]: goals(2)=[clear(a);clear(b);clear(c);on(a;1);on(b;3)] Ali so ciljigoals(2) resni cni v za cetnem stanju? Ne. Izberemo cilj: clear(a), izberemo akcijo move(X;a;To), njeni predpogoji so: conditions(move(X;a;To)) = [clear(X);clear(To);on(X;a)]; vrednosti za X in To so: (c; 2); (c; 4); (c;b);:::. Nastavimo vrednosti X =c, To = 2. adds(move(c;a; 2)) = [clear(a);on(c; 2)] dels(move(c;a; 2)) = [clear(2);on(c;a)] Med cilji v goals(2) in dels(move(c;a; 2)) ni konikta . Regresija ciljev: goals(3) =goals(2)[conditions(move(c;a; 2))nadds(move(c;a; 2)) = = [clear(a);clear(b);clear(c);on(a; 1);on(b; 3)][ [clear(c);clear(2);on(c;a)]n [clear(a);on(c; 2)] = = [clear(b);clear(c);on(a; 1);on(b; 3);clear(2);on(c;a)]: goals(3)=[clear(b);clear(c);on(a;1);on(b;3);clear(2);on(c;a)] Opazimo, da so ti cilji resni cni v za cetnem stanju. Zdaj le se izvedemo akcije v obratnem vrstnem redu. Re sitev je: 1. move(c;a; 2) 2. move(b; 3;c) 3. move(a; 1;b) 2.2. RAZ SIRJEN SVET KOCK 37 2.2 Raz sirjen svet kock V tej nalogi bomo svet kock iz prej snje naloge raz sirili z dodatnimi akcijami. a) Predpostavimo, da lahko robot porine celoten stolp levo ali desno. Pri tem mora imeti prosto ustrezno polje (levo oz. desno), kamor premika stolp. Opi site akciji pushLeft in pushRight, ki predstavljata levi in desni premik. b) Imejmo spretnega robota, ki zna zagrabiti dve zgornji kocki na istem stolpcu in ju zamenjati. Denirajte akcijo swap(X;Y;From), ki kocki zamenja. c) Robot lahko prime dve kocki in ju odnese na drugo polje. Denirajte akcijo move2(X;Y;From;To). d) Kako bi posodobljen robot z novimi akcijami re seval problem opisan na za cetku tega poglavja? Napi site vse mo zne akcije, s katerimi bi posku sal pri prvem cilju on(a;b)? Kak sni so pogoji za izbrane akcije? Dolo cite smiselne vrednosti spremenljik, ki naj jih algoritem najprej poskusi. Uporabljajte planiranje brez regresije ciljev. e) Poi s ci mno zico regresiranih ciljev rgoals skozi akcije move(a; 1;b), swap(b;a; 1) inmove2(c;a; 3;b), za cetni cilji so goals = [on(a;b);on(b;c)]. Re sujemo cilj on(a;b). Ali lahko akcije izvedemo? Re sitev: Naloga a: premikanje levo in desno Akcija: pushLeft(X;From;To) conditions = [on(X;From);clear(To)] adds = [on(X;To);clear(From)] dels = [on(X;From);clear(To)] constraints = [notblock(To);notblock(From);From =To + 1;From> 1] Akcija: pushRight(X;From;To) conditions = [on(X;From);clear(To)] adds = [on(X;To);clear(From)] dels = [on(X;From);clear(To)] constraints = [notblock(To);notblock(From);From =To 1;From< 4] Naloga b: zamenjava dveh kock Akcija: swap(X;Y;From) conditions = [on(X;Y );clear(X);on(Y;From)] 38 POGLAVJE 2. PLANIRANJE adds = [on(Y;X);clear(Y );on(X;From)] dels = [on(X;Y );clear(X);on(Y;From)] constraints = [block(X);block(Y )] Naloga c: premikanje dveh kock Akcija: move2(X;Y;From;To) conditions = [on(X;Y );clear(X);clear(To);on(Y;From)] adds = [clear(From);on(Y;To)] dels = [clear(To);on(Y;From)] constraints = [X6=Y;X6=From;Y 6=From;X6=To;Y 6=To;To6= From;block(X);block(Y )] Naloga d: planiranje Posku sal bi z vsemi akcijami, ki dodajo relacijo on(a;b). To so akcije move, swap inmove2. AkcijipushLeft inpushRight nista primerni, ceprav imata med svojimi pozitivnimi u cinki on(X;To), saj drugi argument ne sme biti kocka. Akcija move(a;From;b), pogoji za akcijo so: [clear(a);clear(b);on(a;From)] Algoritem bi najprej poskusil s From = 1, saj je a v za cetni poziciji na mestu 1. Akcija swap(b;a), pogoji so: [on(b;a);clear(b)]: Akcijamove2(X;b;From;a), pogoji: [on(X;b);clear(X);clear(a);on(b;From)]: Najprej bi izbral vrednosti (X = c;From = 3). From = 3 bi izbral, ker je b na za cetku na 3, c, ker je edina preostala kocka (X ne more biti ne a in ne b). Naloga e: planiranje z regresijo ciljev 1. move(a; 1;b) rgoals = [clear(a);clear(b);on(a; 1);on(b;c)] Ce dose zemo rgoals, bomo z akcijo move(a; 1;b) dosegli goals. 2. swap(b;a; 1) rgoals = [on(b;a);on(a; 1);clear(b);on(b;c)] Akcije ne bomo mogli izvesti, saj so cilji neizvedljivi! Kocka b ne more biti hkrati na a in c. 3. move2(c;a; 3;b) rgoals = [on(c;a);clear(c);clear(b);on(a; 3);on(b;c)] 2.3. FALCON 39 2.3 Falcon Falcon je vladno letalo 1 , ki se ne uporablja prav dosti. Na s cilj bo narediti na crt leta, da bi s cim manj leti prepeljali slovenske ministre po evropskih dr zavah. Na letalu je hkrati lahko poljubno stevilo ministrov, a so ministri v casih skregani in takrat no cejo leteti skupaj. Skregana ministra ne smeta biti hkrati na letalu. a) Opis akcij: V domeni imamo tri mo zne akcije: fly (premakne Falcona iz ene dr zave v drugo), embark (vkrcanje ministra) indisembark (izkr- canje ministra). Opi site vse akcije z jezikom STRIPS. Na voljo imate relacije incountry(Where;X), ki ozna cuje, da je X v dr zavi Where, country(Where) vrne True, ce je X dr zava, minister(X), ce je X mi- nister, dislikes(X;Y ) je True, ce se ministra X in Y ne marata, in onplane(X) ozna cuje, da je minister X na letalu. b) Planiranje Falcona: Imejmo za cetno stanje: fincountry(france;m1);incountry(slovenia;falcon)g in ciljegoals = [incountry(slovenia;m1);incountry(slovenia;falcon)]. Re site pro- blem s planiranjem po principu sredstva-cilji in pri tem uporabite regresiranje ciljev. Poskusite nalogo re siti s s citenjem ciljev in brez. S citenje ciljev ( angl. protecting goals) je prepre cevanje algoritmu pla- niranja, da bi \poru sil" ze dose zene cilje. c) Naj bo za cetno stanje [incountry(slovenia;m1);incountry(slovenia;falcon); onplane(m2);onplane(m3);dislikes(m2;m1)] in cilj je onplane(m1). Zakaj s planiranjem ne moremo dose ci cilja? Kako bi problem odpra- vili? Re sitev: Naloga a: opis akcij Akcija: fly(From;To) conditions = [incountry(From;falcon)] adds = [incountry(To;falcon)] dels = [incountry(From;falcon)] constraints = [country(From);country(To)] Akcija: embark(Where;Who) conditions = [incountry(Where;falcon);incountry(Where;Who)] adds = [onplane(Who)] dels = [incountry(Where;Who)] 1 V casu pisanja te skripte je slovenska vlada vsekakor se imela to letalo. 40 POGLAVJE 2. PLANIRANJE constraints = [land(Where);minister(Who);notdislikes(Who;X);onplane(X)] Akcija: disembark(Where;Who) conditions = [incountry(Where;falcon);onplane(Who)] adds = [incountry(Where;Who)] dels = [onplane(Who)] constraints = [land(Where);minister(Who)] Dodatno vpra sanje: ali bi znali to predstavitev posplo siti za ve c vladnih letal? Naloga b: planiranje poletov s Falconom S s citenjem ciljev. Izberimo cilj: incountry(slovenia;m1). To relacijo doda le akcija disembark(slovenia;m1), ki ima predpogoje: conditions(disembark(slovenia;m1)) = [incountry(slovenia;falcon);onplane(m1)] Regresirani cilji so [incountry(slovenia;falcon);onplane(m1)]: Izberemo ciljonplane(m1), ki se ni izpolnjen. Akcija embark(Where;m1) s predpogoji conditions(embark(Where;m1)) = [incountry(Where;falcon);incountry(Where;m1)] Za Where bi bilo tu najbolje vzeti france, saj se minister m1 tam nahaja. Problem je, da potem dobimo neizvedljive regresirane cilje [incountry(france;falcon);incountry(france;m1);incountry(france;falcon). Letalo ne more biti hkrati na dveh mestih. Alternativna mo znost je, da izberemo cilj incountry(slovenia;falcon), vendar to s s citenjem ciljev ni mo zno. S s citenjem ciljev ne najdemo re sitve. Brez s citenja ciljev. Izberemo cilj incountry(slovenia;falcon) in ak- cijo: fly(From;slovenia) s predpogoji: conditions(fly(From;slovenia)) = [incountry(From;falcon)] From je lahko katerakoli dr zava, re sitev bomo na sli pri From =france. Regresirani cilji so [incountry(france;falcon);onplane(m1)] Izberemo ciljonplane(m1). Akcijaembark(Where;m1), kjer jeWhere = france. Novi regresirani cilji so [incountry(france;falcon);incountry(france;m1)]. Preostane nam le se cilj incountry(france;falcon). Akcija: fly(From;france). Pri vrednosti From = slovenia lahko akcijo izvedemo v za cetnem stanju. Rezultat planiranja je: fly(slovenia;france), embark(france;m1), fly(france;slovenia), disembark(slovenia;m1). 2.3. FALCON 41 Naloga c Cilj onplane(m1). Akcija: embark(slovenia;m1) conditions = [incountry(slovenia;falcon);incountry(slovenia;m1)] Pogoji so izpolnjeni, a akcije ne moremo izvesti zaradi omejitev notdislikes(Who;X);onplane(X). Omejitev bi morali zapisati kot pogoj. Potem bi pogoji ne bili izpol- njeni in algoritem planiranja bi jih poskusil izpolniti. Opis akcije embark spremenimo v: Akcija: embark(Where;Who) conditions = [incountry(Where;falcon);incountry(Where;Who); dislikes(Who;X);notonplane(X)] adds = [onplane(Who)] dels = [incountry(Where;Who)] constraints = [land(Where);minister(Who)] 42 POGLAVJE 2. PLANIRANJE Poglavje 3 Strojno u cenje 43 44 POGLAVJE 3. STROJNO U CENJE 3.1 Dva atributa in razred Dana je tabela u cnih primerov z dvoji skima atributoma A inB in dvoji skim razredom R. A B R 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 a) Brez ra cunanja dolo ci informacijski prispevek in razmerje inf. pri- spevka atributa A. Odgovor utemelji. b) Oceni ali sta inf. prispevek in razmerje inf. prispevka atributaB ve cja, manj sa ali enaka kot pri atributu A. c) Izra cunaj klasikacijsko napako drevesa, ki je ekvivalentno pravilu: IF B = 1 THEN R = 1 ELSE R = 0. Uporabi Laplaceovo oceno verjetnosti. d) Iz atributovA inB naredimo nov atributAB, ki ga deniramo takole: AB = 1, kadar jeA =B = 1, sicer jeAB = 0. S pomo cjo tega atributa si kot drevo lahko predstavljamo naslednje pravilo: IF A = 1^B = 1 THEN R = 1 ELSE R = 0. Ocenite njegovo klasikacijsko to cnost z uporabo m-ocene. Naj bo m = 5, apriorne verjetnosti pa izra cunajte z relativno frekvenco na celotni u cni mno zici. 3.1. DVA ATRIBUTA IN RAZRED 45 Re sitev: a) Porazdelitev obeh razredov, R = 0 in R = 1 je pri A = 0 in A = 1 enaka: A = 0: [3; 3] A = 1: [3; 3] Informacijski prispevek atributa A je torej 0, iz tega pa sledi, da je tudi razmerje inf. prispevka A enako 0. b) Ker je inf. prispevek A enak 0, ima B lahko le ve cji ali enak, gotovo pa ne manj si inf. prispevek. Pogledamo porazdelitve razreda pri obeh vrednostih atributa B: B = 0: [5; 1] B = 1: [1; 5] Iz neenakomerne porazdelitve vidimo, da inf. prispevek B gotovo ni 0, iz cesar sledi, da ima B ve cji inf. prispevek kot A in posledi cno tudi ve cje razmerje inf. prispevka. c) Napaka pravila IF B = 1 THEN R = 1 ELSE R = 0 je: e = 1 (P (B = 1)P Laplace (R = 1jB = 1)+P (B = 0)P Laplace (R = 0jB = 0)): P (B = 1) = 6 12 = 1 2 , P Laplace (R = 1jB = 1) = 5+1 6+2 (imamo 6 primerov z B = 1, od tega jih ima 5 R = 1) P (B = 0) = 6 12 = 1 2 , P Laplace (R = 0jB = 0) = 5+1 6+2 (imamo 6 primerov z B = 0, od tega jih ima 5 R = 0) Napaka je: e = 1 ( 1 2 6 8 + 1 2 6 8 ) = 1 4 = 0:25: d) To cnost izra cunamo kot ute zeno vsoto verjetnosti napovedanega ra- zreda v posameznem listu drevesa: t = P (A = 1^B = 1)P (R = 1jA = 1^B = 1) + +(1 P (A = 1^B = 1))P (R = 0j:(A = 1^B = 1)) P (A = 1^B = 1) = 3 12 = 1 4 P (R = 1jA = 1^B = 1) = 3+5 6=12 3+5 = 0:74 P (R = 0j:(A = 1^B = 1)) = 6+5 6=12 9+5 = 6+5=2 14 = 0:607 t = 0:25 0:74 + 0:75 0:607 = 0:64 46 POGLAVJE 3. STROJNO U CENJE 3.2 Mi sma s Kot vemo, pri Mi sma su ze od nekdaj pe cejo kruh mi si. V casih je bilo eno- stavno: crne mi si so pekle crn kruh, bele belega, sive polbelega in rumene koruznega. Kriza tudi Mi sevu ni prizanesla. Polbeli in koruzni kruh so za casno prenehali pe ci, sive in rumene mi si pa je Mi sma s skrivnostno pre- razporedil na beli in crni kruh. S pomo cjo spodnje tabele ugotovi, kako se je odlo cal. Zgradi odlo citveno drevo z uporabo informacijskega prispevka (angl. Information Gain). BARVA REP KLOBUK KRUH crna kratek nima crn crna kratek nima crn crna kratek nima crn crna kratek nima crn siva dolg ima crn siva dolg nima crn rumena dolg nima crn rumena dolg nima crn siva dolg ima crn siva dolg nima crn rumena dolg ima bel rumena kratek ima bel crna dolg ima bel siva kratek nima bel bela dolg ima bel bela dolg nima bel bela dolg ima bel bela kratek ima bel bela kratek ima bel bela kratek ima bel Re sitev: Entropija razreda je: H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 1bit ; kar sicer lahko izra cunamo tudi na pamet, saj je razred enakomerno poraz- deljen. V koren drevesa bomo postavili tisti atribut, ki najbolj zmanj sa ne- dolo cenost H. Za vsak atribut izra cunamo zmanj sano entropijo: IG(X) =H(KRUH) H res (X): H res (X) je preostala nedolo cenost, ce podatke razdelimo glede na atribut X. Izra cunamo jo kot ute zeno vsoto entropij posameznih vrednosti atributa X: 3.2. MI SMA S 47 H res (X) = P v p(v)H(v), kjer je: H(v) = P r p(rjX = v) log 2 p(rjX = v) prek vseh razredov r. Imamo 5 crnih, 4 rumene, 6 belih in 5 sivih mi si, torej: H res (BARVA) = 5 20 H( crna) + 4 20 H(rumena) + 6 20 H(bela) + 5 20 H(siva) H( crna) = 1 5 log 2 1 5 4 5 log 2 4 5 = 0:722 H(rumena) = 2 4 log 2 2 4 2 4 log 2 2 4 = 1 H(bela) = 6 6 log 2 6 6 0 6 log 2 0 6 = 0 H(siva) = 1 5 log 2 1 5 4 5 log 2 4 5 = 0:722 H res (BARVA) = 0:561 in IG(BARVA) =H(KRUH) H res (BARVA) = 1 0:561 = 0:439. Podobno izra cunamo IG(REP) in IG(KLOBUK): H res (REP) = 11 20 H(dolg) + 9 20 H(kratek) H(dolg) = 5 11 log 2 5 11 6 11 log 2 6 11 = 0:994 H(kratek) = 5 9 log 2 5 9 4 9 log 2 4 9 = 0:991 H res (REP) = 0:993 in IG(REP) =H(KRUH) H res (REP) = 1 0:993 = 0:007. H res (KLOBUK) = 10 20 H(ima) + 10 20 H(nima) H(ima) = 8 10 log 2 8 10 2 10 log 2 2 10 = 0:722 H(nima) = 2 10 log 2 2 10 8 10 log 2 8 10 = 0:722 H res (KLOBUK) = 0:722 in IG(KLOBUK) =H(KRUH) H res (KLOBUK) = 1 0:722 = 0:278. Najve cji informacijski prispevek (IG) ima BARVA, zato ta atribut izbe- remo za koren drevesa, ki ga gradimo. Trenutno drevo je globine 1 in ima eno notranje vozli s ce (BARVA) in stiri liste, v katerih se nahajajo u cni primeri z ustreznimi vrednostmi atributa BARVA. Postopek ra cunanja informacij- skih prispevkov in izbire atributa ponovimo v vsakem od listov. Pri tem upo stevamo samo u cne primere v vsakem listu. Ker smo barvo ze dolo cili, bomo izbirali samo med atributoma REP in KLOBUK. Za vsako barvo si naredimo ustrezno tabelo primerov in izra cunajmo informacijska prispevka preostalih atributov: 48 POGLAVJE 3. STROJNO U CENJE BARVA = crna: BARVA REP KLOBUK KRUH crna kratek nima crn crna kratek nima crn crna kratek nima crn crna kratek nima crn crna dolg ima bel Porazdelitev razreda je 4 : 1 (4 crne mi si pe cejo crn kruh, 1 pa belega). Entropija razreda je: H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 4 5 log 2 4 5 1 5 log 2 1 5 = 0:722bit Informacijska prispevka atributov REP in KLOBUK za crne mi si sta: H res (REP) = 1 5 H(dolg) + 4 5 H(kratek) H(dolg) = 1 1 log 2 1 1 0 1 log 2 0 1 = 0 H(kratek) = 0 4 log 2 0 4 4 4 log 2 4 4 = 0 H res (REP) = 0 in IG(REP) =H(KRUH) H res (REP) = 0:722 0 = 0:722. Ker je porazdelitev vrednosti pri obeh atributih enaka, je ra cun za KLO- BUK isti: IG(KLOBUK) = H(KRUH) H res (KLOBUK) = 0:722 0 = 0:722. Atributa REP in KLOBUK sta torej enakovredna in vseeno je, katerega izberemo za koren tega poddrevesa. To bi pravzaprav lahko ugotovili ze brez ra cunanja, ker sta atributa prakti cno identi cna. BARVA = rumena: BARVA REP KLOBUK KRUH rumena dolg nima crn rumena dolg nima crn rumena dolg ima bel rumena kratek ima bel Tudi pri rumenih mi sih zadostuje ze metoda ostrega pogleda: rumene mi si s klobukom pe cejo bel kruh, tiste brez pa crnega. Glede na rep o citno ne moremo natan cno dolo citi vrste kruha. Opa zeno potrdimo z ra cunanjem: Porazdelitev razreda je 2 : 2 { tega se ne bomo ra cunali, vemo ze, da je njegova entropija 1bit. H res (REP) = 3 4 H(dolg) + 1 4 H(kratek) 3.2. MI SMA S 49 H(dolg) = 1 3 log 2 1 3 2 3 log 2 2 3 = 0:918 H(kratek) = 1 1 log 2 1 1 0 1 log 2 0 1 = 0 H res (REP) = 0:689 in IG(REP) =H(KRUH) H res (REP) = 1 0:689 = 0:311. H res (KLOBUK) = 2 4 H(ima) + 2 4 H(nima) H(ima) = 2 2 log 2 2 2 0 2 log 2 0 2 = 0 H(nima) = 0 2 log 2 0 2 2 2 log 2 2 2 = 0 H res (KLOBUK) = 0 in IG(KLOBUK) =H(KRUH) H res (REP) = 1 0 = 1. BARVA = bela: BARVA REP KLOBUK KRUH bela dolg ima bel bela dolg nima bel bela dolg ima bel bela kratek ima bel bela kratek ima bel bela kratek ima bel Bele mi si o citno pe cejo samo bel kruh. Iz tega sklepamo, da je entropija oz. nedolo cenost enaka 0. Z drugimi besedami, nesmiselno bi bilo nadalje vejiti to vozli s ce drevesa. Na se sklepanje potrdi tudi ra cun: H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 6 6 log 2 6 6 0 6 log 2 0 6 = 0bit: BARVA = siva: BARVA REP KLOBUK KRUH siva dolg ima crn siva dolg nima crn siva dolg ima crn siva dolg nima crn siva kratek nima bel Ostale so se sive mi si. Nedolo cenost pri njih je H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 4 5 log 2 4 5 1 5 log 2 1 5 = 0:722bit. H res (REP) = 4 5 H(dolg) + 1 5 H(kratek) H(dolg) = 0 4 log 2 0 4 4 4 log 2 4 4 = 0 50 POGLAVJE 3. STROJNO U CENJE H(kratek) = 1 1 log 2 1 1 0 1 log 2 0 1 = 0 H res (REP) = 0 in IG(REP) =H(KRUH) H res (REP) = 0:722 0 = 0:722. H res (KLOBUK) = 2 5 H(ima) + 3 5 H(nima) H(ima) = 2 2 log 2 2 2 0 2 log 2 0 2 = 0 H(nima) = 1 3 log 2 1 3 2 3 log 2 2 3 = 0:918 H res (KLOBUK) = 0:551 in IG(KLOBUK) =H(KRUH) H res (KLOBUK) = 0:722 0:551 = 0:171. Atribut REP ima vi sji informacijski prispevek, zato ga damo v koren poddrevesa. V naslednjem koraku spet razdelimo mno zico u cnih primerov glede na trenutno drevo(slika 3.1). Ugotovimo, da so listi tega drevesa cisti in da nadaljna vejitev drevesa ni smiselna. Zato je drevo na sliki 3.1 ze kon cno drevo. Se enkrat poudarimo, da sta REP in KLOBUK pri crnih mi sih enakovredna in da je pravilno tudi drevo, ki ima v korenu poddrevesa pri crnih mi sih atribut REP. Slika 3.1: Mi sma s info gain in gini 3.3. MI SMA S Z RAZMERJEM INF. PRISPEVKA 51 3.3 Mi sma s z razmerjem inf. prispevka Zgradite odlo citveno drevo za 2. nalogo z uporabo razmerja informacijskega prispevka (angl. Information Gain Ratio). Re sitev: Ve cino dela za izra cun razmerja informacijskega prispevka smo opravili ze zgoraj. Izra cunati moramo le se entropije atributov, s katerimi bomo delili njihove informacijske prispevke. Entropija atributa X je H(X) = P v p(X =v) log 2 p(X =v), kjer je v vrednost atributa X. H(BARVA) = p(BARVA = crna) log 2 p(BARVA = crna) p(BARVA = rumena) log 2 p(BARVA = rumena) p(BARVA = bela) log 2 p(BARVA = bela) p(BARVA = siva) log 2 p(BARVA = siva) = = 5 20 log 2 5 20 4 20 log 2 4 20 6 20 log 2 6 20 5 20 log 2 5 20 = 1:985bit H(REP) = p(REP = dolg) log 2 p(REP = dolg) p(REP = kratek) log 2 p(REP = kratek) = 11 20 log 2 11 20 9 20 log 2 9 20 = 0:993bit H(KLOBUK) = p(KLOBUK = ima) log 2 p(KLOBUK = ima) p(KLOBUK = nima) log 2 p(KLOBUK = nima) = 10 20 log 2 10 20 10 20 log 2 10 20 = 1bit Razmerje informacijskega prispevka atributa X, IGR(X), je IGR(X) =IG(X)=H(X): Na celotni mno zici podatkov je: IGR(BARVA) =IG(BARVA)=H(BARVA) = 0:439=1:985 = 0:221 IGR(REP) =IG(REP)=H(REP) = 0:007=0:993 = 0:007 IGR(KLOBUK) =IG(KLOBUK)=H(KLOBUK) = 0:278=1 = 0:278 Glede na IGR je za koren najbolj primeren atribut KLOBUK. V nada- ljevanju postopamo kot prej. Za cetno mno zico podatkov razdelimo glede na vrednosti atributa KLOBUK. Tako za KLOBUK=ima kot za KLO- BUK=nima moramo izra cunati informacijska prispevka atributov BARVA in REP. 52 POGLAVJE 3. STROJNO U CENJE KLOBUK = ima: BARVA REP KLOBUK KRUH siva dolg ima crn siva dolg ima crn rumena dolg ima bel rumena kratek ima bel crna dolg ima bel bela dolg ima bel bela dolg ima bel bela kratek ima bel bela kratek ima bel bela kratek ima bel H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 8 10 log 2 8 10 2 10 log 2 2 10 = 0:722bit. H res (BARVA) = 1 10 H( crna) + 2 10 H(rumena) + 5 10 H(bela) + 2 10 H(siva) H( crna) = 1 1 log 2 1 1 0 1 log 2 0 1 = 0 H(rumena) = 2 2 log 2 2 2 0 2 log 2 0 2 = 0 H(bela) = 5 5 log 2 5 5 0 5 log 2 0 5 = 0 H(siva) = 0 2 log 2 0 2 2 2 log 2 2 2 = 0 H res (BARVA) = 0 in IG(BARVA) =H(KRUH) H res (BARVA) = 0:722 0 = 0:722. H(BARVA) = 2 10 log 2 2 10 2 10 log 2 2 10 1 10 log 2 1 10 5 10 log 2 5 10 = 1:761bit IGR(BARVA) =IG(BARVA)=H(BARVA) = 0:722=1:761 = 0:410 H res (REP) = 6 10 H(dolg) + 4 10 H(kratek) H(dolg) = 4 6 log 2 4 6 2 6 log 2 2 6 = 0:918 H(kratek) = 4 4 log 2 4 4 0 4 log 2 0 4 = 0 H res (REP) = 0:551 in IG(REP) =H(KRUH) H res (REP) = 0:722 0:551 = 0:171. H(REP) = 6 10 log 2 6 10 4 10 log 2 4 10 = 0:971bit IGR(REP) =IG(REP)=H(REP) = 0:171=0:971 = 0:176 Izra cun poka ze, da je po kriteriju razmerja informacijskega prispevka BARVA bolj si atribut, zato ga damo v koren poddrevesa. 3.3. MI SMA S Z RAZMERJEM INF. PRISPEVKA 53 KLOBUK=nima: BARVA REP KLOBUK KRUH crna kratek nima crn crna kratek nima crn crna kratek nima crn crna kratek nima crn siva dolg nima crn rumena dolg nima crn rumena dolg nima crn siva dolg nima crn siva kratek nima bel bela dolg nima bel H(KRUH) = p(bel) log 2 (bel) p( crn) log 2 ( crn) = 2 10 log 2 2 10 8 10 log 2 8 10 = 0:722bit. H res (BARVA) = 4 10 H( crna) + 2 10 H(rumena) + 1 10 H(bela) + 3 10 H(siva) H( crna) = 0 4 log 2 0 4 4 4 log 2 4 4 = 0 H(rumena) = 0 2 log 2 0 2 2 2 log 2 2 2 = 0 H(bela) = 1 1 log 2 1 1 0 1 log 2 0 1 = 0 H(siva) = 1 3 log 2 1 3 2 3 log 2 2 3 = 0:918 H res (BARVA) = 0:276 in IG(BARVA) =H(KRUH) H res (BARVA) = 0:722 0:276 = 0:446. H(BARVA) = 4 10 log 2 4 10 3 10 log 2 3 10 2 10 log 2 2 10 1 10 log 2 1 10 = 1:846bit IGR(BARVA) =IG(BARVA)=H(BARVA) = 0:446=1:846 = 0:242 H res (REP) = 5 10 H(dolg) + 5 10 H(kratek) H(dolg) = 1 5 log 2 1 5 4 5 log 2 4 5 = 0:722 H(kratek) = 1 5 log 2 1 5 4 5 log 2 4 5 = 0:722 H res (REP) = 0:722 in IG(REP) =H(KRUH) H res (REP) = 0:722 0:722 = 0. H(REP) = 5 10 log 2 5 10 5 10 log 2 5 10 = 1bit IGR(REP) =IG(REP)=H(REP) = 0=1 = 0 Atribut BARVA je spet bolje ocenjen od atributa REP, vendar sive mi si brez klobuka se vedno pe cejo razli cen kruh, zato gradnja na sega drevesa se ni kon cana. Ker pa smo drevo vejili ze po dveh atributih, nam ostane samo se eden, REP. Zato ra cunanje ni potrebno. Vidimo, da siva mi s brez klobuka in 54 POGLAVJE 3. STROJNO U CENJE s kratkim repom pe ce bel kruh, oni dve z dolgim repom pa crnega. Kon cno drevo za na s primer je na sliki 3.2. Prav lahko bi se zgodilo, da bi v listih ne dobili cistih porazdelitev { ce zmanjka atributov za nadaljne vejitve, se gradnja drevesa ne glede na to ustavi. Slika 3.2: Mi sma s gain ratio Drevesi 3.1 in 3.2 sta razli cni zato, ker informacijski prispevek in raz- merje informacijskega prispevka razli cno rangirata atribute. Razlog za to je, da informacijski prispevek daje prednost ve cvrednostnim atributom, torej atributu BARVA pred atributom REP. 3.4. MI SMA S Z GINI INDEKSOM 55 3.4 Mi sma s z Gini indeksom Re site 2. nalogo se z uporabo Gini indeksa. Re sitev: Gini razreda je: Gini(KRUH) = 1 p(bel) 2 p( crn) 2 = 1 0:5 2 0:5 2 = 0:5. V koren drevesa bomo postavili tisti atribut, ki najbolj zmanj sa Gini razreda. Za vsak atribut izra cunamo njegov Gini prispevek: Gini(BARVA) =Gini(KRUH) Gini res (BARVA) Ce podatke razdelimo glede na atributX, jeGini res (X) = P v2X p(v)Gini(v), kjer je: Gini(v) = 1 P r p(rjX =v) 2 prek vseh razredov r. Imamo 5 crnih, 4 rumene, 6 belih in 5 sivih mi si, torej: Gini res (BARVA) = 5 20 Gini( crna)+ 4 20 Gini(rumena)+ 6 20 Gini(bela)+ 5 20 Gini(siva) Gini( crna) = 1 ( 1 5 ) 2 ( 4 5 ) 2 = 0:320 Gini(rumena) = 1 ( 2 4 ) 2 ( 2 4 ) 2 = 0:5 Gini(bela) = 1 ( 6 6 ) 2 ( 0 6 ) 2 = 0 Gini(siva) = 1 ( 1 5 ) 2 ( 4 5 ) 2 = 0:320 Gini res (BARVA) = 0:260 in GiniGain(BARVA) = Gini(KRUH) Gini res (BARVA) = 0:5 0:260 = 0:240. Gini res (REP) = 11 20 Gini(dolg) + 9 20 Gini(kratek) Gini(dolg) = 1 ( 5 11 ) 2 ( 6 11 ) 2 = 0:496 Gini(kratek) = 1 ( 5 9 ) 2 ( 4 9 ) 2 = 0:494 Gini res (REP) = 0:495 in GiniGain(REP) =Gini(KRUH) Gini res (REP) = 0:5 0:495 = 0:005. Gini res (KLOBUK) = 10 20 Gini(ima) + 10 20 Gini(nima) Gini(ima) = 1 ( 8 10 ) 2 ( 2 10 ) 2 = 0:320 Gini(nima) = 1 ( 2 10 ) 2 ( 8 10 ) 2 = 0:320 Gini res (KLOBUK) = 0:320 in GiniGain(KLOBUK) =Gini(KRUH) Gini res (KLOBUK) = 0:5 0:320 = 0:180. Najve cji Gini prispevek ima BARVA, zato jo damo v koren drevesa. Kot v prej snjih dveh nalogah postopek ponovimo na listih trenutnega drevesa. 56 POGLAVJE 3. STROJNO U CENJE BARVA = crna: BARVA REP KLOBUK KRUH crna kratek nima crn crna kratek nima crn crna kratek nima crn crna kratek nima crn crna dolg ima bel Gini(KRUH) = 1 (p(bel)) 2 (p( crn)) 2 = 1 ( 1 5 ) 2 ( 4 5 ) 2 = 0:320 Gini res (REP) = 1 5 Gini(dolg) + 4 5 Gini(kratek) Gini(dolg) = 1 ( 1 1 ) 2 ( 0 1 ) 2 = 0 Gini(kratek) = 1 ( 0 4 ) 2 ( 4 4 ) 2 = 0 Gini res (REP) = 0 in GiniGain(REP) =Gini(KRUH) Gini res (REP) = 0:320 0 = 0:320. Ker je porazdelitev vrednosti pri obeh atributih enaka, je ra cun za KLO- BUK isti: GiniGain(KLOBUK) = Gini(KRUH) Gini res (KLOBUK) = 0:320 0 = 0:320. Za atributa REP in KLOBUK velja enako kot prej { vseeno je, katerega izberemo za koren tega poddrevesa. BARVA = rumena: BARVA REP KLOBUK KRUH rumena dolg nima crn rumena dolg nima crn rumena dolg ima bel rumena kratek ima bel Gini(KRUH) = 1 (p(bel)) 2 (p( crn)) 2 = 1 ( 2 4 ) 2 ( 2 4 ) 2 = 0:5 Gini res (REP) = 3 4 Gini(dolg) + 1 4 Gini(kratek) Gini(dolg) = 1 ( 1 3 ) 2 ( 2 3 ) 2 = 0:444 Gini(kratek) = 1 ( 1 1 ) 2 ( 0 1 ) 2 = 0 Gini res (REP) = 0:333 in GiniGain(REP) =Gini(KRUH) Gini res (REP) = 0:5 0:333 = 0:167. 3.4. MI SMA S Z GINI INDEKSOM 57 Gini res (KLOBUK) = 2 4 Gini(ima) + 2 4 Gini(nima) Gini(ima) = 1 ( 2 2 ) 2 ( 0 2 ) 2 = 0 Gini(nima) = 1 ( 0 2 ) 2 ( 2 2 ) 2 = 0 Gini res (KLOBUK) = 0 in GiniGain(KLOBUK) =Gini(KRUH) Gini res (KLOBUK) = 0:5 0 = 0:5. BARVA = bela: BARVA REP KLOBUK KRUH bela dolg ima bel bela dolg nima bel bela dolg ima bel bela kratek ima bel bela kratek ima bel bela kratek ima bel Sklepamo tako kot v nalogi 3.2. BARVA = siva: BARVA REP KLOBUK KRUH siva dolg ima crn siva dolg nima crn siva dolg ima crn siva dolg nima crn siva kratek nima bel Gini(KRUH) = 1 p(bel) 2 p( crn) 2 = 1 ( 1 5 ) 2 ( 4 5 ) 2 = 0:320 Gini res (REP) = 4 5 Gini(dolg) + 1 5 Gini(kratek) Gini(dolg) = 1 ( 0 4 ) 2 ( 4 4 ) 2 = 0 Gini(kratek) = 1 ( 1 1 ) 2 ( 0 1 ) 2 = 0 Gini res (REP) = 0 in GiniGain(REP) =Gini(KRUH) Gini res (REP) = 0:320 0 = 0:320. Gini res (KLOBUK) = 2 5 Gini(ima) + 3 5 Gini(nima) Gini(ima) = 1 ( 2 2 ) 2 ( 0 2 ) 2 = 0 Gini(nima) = 1 ( 1 3 ) 2 ( 2 3 ) 2 = 0:444 Gini res (KLOBUK) = 0:267 in 58 POGLAVJE 3. STROJNO U CENJE GiniGain(KLOBUK) =Gini(KRUH) Gini res (KLOBUK) = 0:053. Atribut REP ima vi sji gini prispevek, zato ga damo v koren poddrevesa. Tako kot v nalogi 3.2 tudi na tem mestu kon camo gradnjo drevesa in drevo je natan cno tako kot tisto, ki smo ga dobili z informacijskim prispev- kom (slika 3.1). Ugotovimo, da sta gini in informacijski prispevek enako razvrstila atribute po pomembnosti. 3.5. OCENJEVANJE VERJETNOSTI 59 3.5 Ocenjevanje verjetnosti Dano je odlo citveno drevo s seznami razredov tistih primerov, ki padejo v ustrezni list. L 1 = [x;x;x;y;z], L 2 = [x;y;y;y;y], L 3 = [y;y;z;z;z;z], L 4 = [w;w;w;w]. a) Oceni klasikacijske to cnosti v listih L 1 ;:::;L 4 z uporabo Laplaceove ocene verjetnosti. b) Oceni to cnost celotnega drevesa z Laplaceovo oceno verjetnosti. c) Oceni to cnost v listu L 2 z uporabo m-ocene, pri cemer naj bo m=7, apriorne verjetnosti razredov pa naj bodo: p 0 (x) = 0:1, p 0 (y) = 0:05, p 0 (z) = 0:8 in p 0 (w) = 0:05. Opomba: Klasikacijska to cnost je verjetnost, da bo model pravilno kla- siciral naklju cni testni primer. Klasikacijska napaka je verjetnost napa cne klasikacijske. Re sitev: a) Iz podatkov razberemo, da je stevilo razredov, k = 4. Stevilo primerov ve cinskega razreda n in stevilo vseh primerov v listu N ugotovimo za vsak list posebej. Ocene to cnosti so torej: t(L 1 ) = (3 + 1)=(5 + 4) = 4=9, t(L 2 ) = (4 + 1)=(5 + 4) = 5=9, t(L 3 ) = (4 + 1)=(6 + 4) = 5=10, t(L 4 ) = (4 + 1)=(4 + 4) = 5=8. b) Ocena to cnosti celotnega drevesa, t(A), je ute zena vsota to cnosti v listih. Ute zimo jo z dele zem primerov, ki padejo v posamezni list: t(A) = 5 20 t(L 1 ) + 5 20 t(L 2 ) + 6 20 t(L 3 ) + 4 20 t(L 4 ) = 0:525. c) Za vsak razred moramo izra cunati oceno verjetnosti, ter nato klasi- cirati v najbolj verjeten razred. razred x: 1+p 0 (x) 7 5+7 = 0:14 razred y: 4+p 0 (y) 7 5+7 = 0:36 razred z: 0+p 0 (z) 7 5+7 = 0:47 razred w: 0+p 0 (w) 7 5+7 = 0:03 Klasiciramo torej v razred z. Razlog je zelo visoka apriorna verjetnost tega razreda. 60 POGLAVJE 3. STROJNO U CENJE 3.6 Rezanje: metoda zmanj sevanja napake Dano je klasikacijsko drevo in rezalna tabela. Z rezanjem po metodi zmanj sevanja napake pore zi dano drevo. A B C R 0 0 1 0 0 1 + 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 + 1 1 1 + 1 1 0 + 1 0 1 + 1 0 1 + 1 0 0 + 1 0 1 1 0 0 1 0 0 1 0 0 Re sitev: Rezanje klasikacijskih dreves po metodi zmanj sevanja napake ( angl. Reduced Error Prunning) poteka od spodaj navzgor, t.j. od listov drevesa proti njegovemu korenu. Poleg drevesa postopek zahteva se rezalno tabelo podatkov. Pri gradnji drevesa se ti podatki ne upo stevajo, uporabljajo se samo pri rezanju. Z rezanjem za cnemo v vozli s cih tik nad listi. V vsakem vozli s cu v izra cunamo t.i. dobitek rezanja, G(v), ki je deniran kot razlika med stevilom napa cno klasiciranih primerov v poddrevesu T s korenom v v in stevilom napa cnih klasikacij pri v, ce bi drevo tam porezali: 3.6. REZANJE: METODA ZMANJ SEVANJA NAPAKE 61 G(v) = #napak T #napak v : Re zemo takrat, ko je G(v) 0, torej ce je napaka poddrevesa ve cja od napake v vozli s cu v ali ce sta napaki enaki, saj imamo ob enaki napaki raje manj se drevo. Koristno je najprej vsakemu vozli s cu drevesa pripisati porazdelitev ra- zreda iz rezalne tabele (glej levo drevo na sliki 3.3). V oglatih oklepajih je najprej navedeno stevilo primerov z razredom +, nato pa stevilo prime- rov z razredom . Sprotno pre stevanje primerov hitro privede do napak. S pomo cjo zgornje formule in izpisanih porazdelitev pa zlahka izra cunamo dobitke rezanja za vsako vozli s ce. Za cnimo pri vozli s cu z atributom ( C; [3; 4]; ). V tem vozli s cu je torej 7 primerov, od tega 3 z razredom + in 4 z razredom . Drevo v tem vozli s cu klasicira v razred . Poudarimo, da to ni vezano na porazdelitev primerov iz rezalne tabele, ampak je lastnost drevesa, ki je posledica porazdelitve v u cnih podatkih, ki jih naloga ne navaja. Stevilo napak v tem vozli s cu, #napak v , je 3, saj drevo napa cno klasicira vse 3 primere z razredom +. Stevilo napak v poddrevesu tega vozli s ca je: #napak T = 2 + 3 = 5, 2 napaki v levem listu in 3 v desnem. Dobitek G(v) = 5 3 = 2, torej je dobro drevo porezati tako, da vozli s ce ( C; [3; 4]; ) postane list. Naslednji kandidat za rezanje, po drevesu navzgor, je vozli s ce ( B; [5; 4]; +): #napak v = 4 #napak T = 0 + 3 = 3 G(v) = 3 4 = 1 V tem vozli s cu je bolje pustiti drevo tako kot je, kot ga porezati. Nadaljujmo v vozli s cu ( B; [2; 5]; +): #napak v = 5 #napak T = 4 + 2 = 6 G(v) = 6 5 = 1 Drevo tu pore zemo in ( B; [2; 5]; +) postane list. Nadaljujemo v (C; [2; 7]; ): #napak v = 2 #napak T = 5 + 0 = 5 G(v) = 5 2 = 3 Drevo pore zemo in ( C; [2; 7]; ) postane list. Kon cno drevo je na sliki 3.3 desno. 62 POGLAVJE 3. STROJNO U CENJE Slika 3.3: Pomo zno drevo (levo) in re sitev (desno). 3.7. REZANJE: MEP 63 3.7 Rezanje: MEP Pore zite drevo na sliki 3.4 s postopkom MEP z uporabo Laplaceove ocene. V oglatih oklepajih je navedeno stevilo primerov obeh razredov, npr. vozli s ce b vsebuje 10 primerov prvega in 16 primerov drugega razreda. V vozli s cu b je ve cinski drugi razred. a [15,21] b [10,16] c [5,5] d [7,13] e [3,3] [5,7] [2,6] g [1,2] h [2,1] [1,1] [0,1] [1,0] [1,1] f [2,4] [3,1] [2,3] [0,1] Slika 3.4 Re sitev: V vsakem notranjem vozli s cu v (govoriti o rezanju v listih ni smiselno) primerjamo stati cno napako e in vzvratno napako E. Stati cna napaka e(v) je napaka drevesa v primeru, ce v postane list (torej, ce bi drevo porezali tik pod vozli s cem v). Vzvratna napakaE(v) je napaka, ce drevesa ne pore zemo. Kdaj naj torej drevo pore zemo pod v? Napako ho cemo minimizirati, torej ga pore zemo takrat, ko je stati cna napaka manj sa ali enaka od vzvratne napake. Zakaj tudi, ce je enaka? Z vidika to cnosti je vseeno ali drevo tu pore zemo ali ne, ker pa je manj si model ponavadi tudi bolj razumljiv, ga pore zemo. Ponovimo najprej formulo za izra cun Laplaceove ocene verjetnosti, p = n + 1 N +k ; kjer je: n stevilo primerov ve cinskega razreda v vozli s cu N stevilo vseh primerov v vozli s cu k stevilo razredov V na sem primeru je k = 2. 64 POGLAVJE 3. STROJNO U CENJE Vozli s ce d: Ker ra cunamo napako, moramo ocenjeno verjetnost od steti od 1 (glej nalogo 3). Stati cna napaka v vozli s cu d je e(d) = 1 n+1 N+2 = 1 13+1 20+2 = 8=22 = 0:363. Za izra cun vzvratne napake potrebujemo napako v levem in desnem listu d, ki ju bomo ozna cili kar z d L in d D . e(d L ) = 1 7+1 12+2 = 6=14 = 0:428 e(d D ) = 1 6+1 8+2 = 3=10 = 0:3 Vzvratna napaka je ute zena vsota napak v obeh vozli s cih. Ute zimo ju z dele zem primerov, ki pripadajo vsakemu listu. V levi list vozli s ca d gre 12 od 20 primerov izd, v desnega pa preostalih 8: E(d) = 12 20 0:428+ 8 20 0:3 = 0:376 Izra cunali smo, da je stati cna napaka e(d) manj sa od vzvratne napake E(d), torej je bolj se, da drevo pore zemo pod d. Podobno izra cunamo obe napaki za ostala vozli s ca, pri cemer je po- membno, da gremo po drevesu od spodaj navzgor: Vozli s ce g: e(g) = 1 2+1 3+2 = 2=5 = 0:4 e(g L ) = 1 1+1 2+2 = 0:5 e(g D ) = 1 1+1 1+2 = 1=3 = 0:333 E(g) = 2 3 0:5 + 1 3 0:333 = 0:444 e(g) E(g), torej re zemo pod g. Vozli s ce h: e(h) = 1 2+1 3+2 = 2=5 = 0:4 e(h L ) = 1 1+1 1+2 = 1=3 = 0:333 e(h D ) = 1 1+1 2+2 = 0:5 E(h) = 1 3 0:333 + 2 3 0:5 = 0:444 e(h) E(h), torej re zemo pod h. Vozli s ce e: e(e) = 1 3+1 6+2 = 0:5 e(e L ) =e(g) = 0:4 3.7. REZANJE: MEP 65 e(e D ) =e(h) = 0:4 E(e) = 1 2 0:4 + 1 2 0:4 = 0:4 e(e)>E(e), torej NE re zemo pod e. Vozli s ce f: e(f) = 1 4+1 6+2 = 3=8 = 0:375 e(f L ) = 1 3+1 5+2 = 3=7 = 0:429 e(f D ) = 1 1+1 1+2 = 1=3 = 0:333 E(f) = 5 6 0:429 + 1 6 0:333 = 0:412 e(f) E(f), torej re zemo pod f. Vozli s ce c: e(c) = 1 5+1 10+2 = 0:5 e(c L ) =e(f) = 0:375 e(c D ) = 1 3+1 4+2 = 1=3 = 0:333 E(c) = 6 10 0:375 + 4 10 0:333 = 0:358 e(c)>E(c), torej NE re zemo pod c. Vozli s ce b: e(b) = 1 16+1 26+2 = 0:393 e(b L ) = e(d) = 0:363 (ker smo pri d porezali, vzamemo tu stati cno na- pako vozli s ca d) e(b D ) = E(e) = 0:4 (pri e nismo rezali, zato vzamemo tu vzvratno na- pako) E(b) = 20 26 0:363 + 6 26 0:4 = 0:371 66 POGLAVJE 3. STROJNO U CENJE e(b)>E(b), torej NE re zemo pod b. Vozli s ce a: e(a) = 1 21+1 36+2 = 0:421 e(a L ) = E(b) = 0:371 (ker pri b nismo rezali, vzamemo tu vzvratno na- pako vozli s ca b) e(a D ) =E(c) = 0:358 (vzamemo vzvratno napako pric, ker podc nismo rezali) E(a) = 26 36 0:371 + 10 36 0:358 = 0:367 e(a)>E(a), torej NE re zemo pod a. 3.8. NAIVNI BAYESOV KLASIFIKATOR 67 3.8 Naivni Bayesov klasikator Dani so naslednji u cni podatki: X Y Z R 0 1 a 0 0 1 a 0 1 0 b 0 1 0 b 0 2 1 b 0 1 1 b 1 1 1 b 1 1 0 b 1 2 0 a 1 2 1 a 1 Klasicirajte naslednje primere z naivnim Bayesom. Verjetnosti ra cunajte z relativno frekvenco. X = 1;Y = 1;Z =a X = 0;Y = 0;Z =? X = 2;Y = 0;Z =b Re sitev: Z naivnim Bayesom klasiciramo tako, da za vsak razred c izra cunamo produkt pogojnih verjetnosti danih vrednosti atributov in vse skupaj po- mno zimo z verjetnostjo razreda. Na koncu klasiciramo v tisti razred, kjer ima zgornji produkt najve cjo vrednost: R = argmax c2R P (c) n Y i=1 P (A i jc) X = 1;Y = 1;Z =a c = 0 c = 1 P (c) 1/2 1/2 P (X = 1jc) 2/5 3/5 P (Y = 1jc) 3/5 3/5 P (Z =ajc) 2/5 2/5 Q 6/125 9/125 Primer (X = 1;Y = 1;Z = a) klasiciramo v razred c = 1. Opo- zorimo, da izra cunana vrednost R ni verjetnost P (c = 1jX = 1;Y = 1;Z =a) - to verjetnost lahko izra cunamo takole: P (c = 1jX = 1;Y = 1;Z =a) = 9=125 6=125 + 9=125 = 0:6 68 POGLAVJE 3. STROJNO U CENJE X = 0;Y = 0;Z =? c = 0 c = 1 P (c) 1/2 1/2 P (X = 0jc) 2/5 0 P (Y = 0jc) 2/5 2/5 P (Z =?jc) / / Q 2/25 0 Primer (X = 0;Y = 0;Z =?) klasiciramo v razred c = 0. Ker vre- dnost atributaZ ni podana, tega atributa pri ra cunanju ne upo stevamo. X = 2;Y = 0;Z =b c = 0 c = 1 P (c) 1/2 1/2 P (X = 2jc) 1/5 2/5 P (Y = 0jc) 2/5 2/5 P (Z =bjc) 3/5 3/5 Q 3/125 6/125 Primer (X = 2;Y = 0;Z =b) klasiciramo v razred c = 1. V tej nalogi smo pogojne verjetnosti ra cunali z relativno frekvenco, lahko pa bi uporabili Laplaceovo oceno verjetnosti ali m-oceno. 3.9. LOTO 69 3.9 Loto Po novoletnem zrebanju lota v Sre cnem dolu nad Radovno so v loteriji s pomo cjo svojih zvestih gledalcev naredili statistiko, da bi ugotovili, ce so bili zadetki predvidljivi. V kratki anketi so gledalce vpra sali, ce so sre cko kupili ali jim je bila podarjena (oz. so jo kupili in jo podarili), vpra sali so jih po barvi las in pa ce so spremljali zrebanje v neposrednem prenosu po televiziji. Odgovore povzema naslednja tabela: DOBITEK KUPIL SRE CKO BARVA LAS TV P DA NE SVETLA TEMNA RDE CA DA NE DA 3 777 650 50 80 779 1 780 NE 218 2 5 195 20 1 219 220 221 779 655 245 100 780 220 1000 S pomo cjo naivnega Bayesovega klasikatorja ugotovite ali so bili med sre cnimi dobitniki tudi: a) Temnolasi sre cnodol can, ki ni kupil sre cke, a je gledal zrebanje. b) Blondinka, ki je kupila sre cko in ni gledala zrebanja. c) Rde celaska, ki ni kupila sre cke in ni gledala zrebanja. Pogojne verjetnosti ocenjujte z m-oceno (m = 5), apriorne pa z relativno frekvenco. Re sitev: 1 a) P(DOBITEKj (NE, T, DA)) DOBITEK = DA DOBITEK = NE apriorna P (DA) = 780=1000 = 0:78 P (NE) = 220=1000 = 0:22 KUPIL SRE CKO P (NEjDA) = 777+m779=1000 780+m = 0:994 P (NEjNE) = 2+m779=1000 220+m = 0:022 BARVA LAS P (TjDA) = 50+m245=1000 780+m = 0:065 P (TjNE) = 195+m245=1000 220+m = 0:871 TV P (DAjDA) = 779+m780=1000 780+m = 0:996 P (DAjNE) = 1+m780=1000 220+m = 0:018 Q 0:78 0:994 0:065 0:996 = 0:05 0:22 0:022 0:871 0:018 = 7:6 10 5 P(DAj (NE, T, DA)) > P(NEj (NE, T, DA)) Temnolasi sre cnodol can, ki ni kupil sre cke, a je gledal zrebanje je bil bolj verjetno med sre cnimi dobitniki kot ne. 1 Zaradi utesnjenosti v tabelah kraj samo imena in vrednosti atributov. 70 POGLAVJE 3. STROJNO U CENJE b) P(DOBITEKj (DA, B, NE)) DOBITEK = DA DOBITEK = NE apriorna P (DA) = 780=1000 = 0:78 P (NE) = 220=1000 = 0:22 KUPIL SRE CKO P (DAjDA) = 3+m221=1000 780+m = 0:005 P (DAjNE) = 218+m221=1000 220+m = 0:973 BARVA LAS P (SjDA) = 650+m655=1000 780+m = 0:832 P (SjNE) = 5+m655=1000 220+m = 0:036 TV P (NEjDA) = 1+m220=1000 780+m = 0:003 P (NEjNE) = 219+m220=1000 220+m = 0:978 Q 0:78 0:005 0:832 0:003 = 9:7 10 6 0:22 0:022 0:871 0:018 = 0:008 P(DAj (DA, B, NE)) < P(NEj (DA, B, NE)) Svetlolaska, ki je kupila sre cko in ni gledala zrebanja najverjetneje ni bila med dobitniki. c) P(DOBITEKj (NE, R, NE)) DOBITEK = DA DOBITEK = NE apriorna P (DA) = 780=1000 = 0:78 P (NE) = 220=1000 = 0:22 KUPIL SRE CKO P (NEjDA) = 777+m779=1000 780+m = 0:994 P (NEjNE) = 2+m779=1000 220+m = 0:022 BARVA LAS P (RjDA) = 80+m100=1000 780+m = 0:102 P (RjNE) = 20+m100=1000 220+m = 0:089 TV P (NEjDA) = 1+m220=1000 780+m = 0:003 P (NEjNE) = 219+m220=1000 220+m = 0:978 Q 0:78 0:994 0:102 0:003 = 2:4 10 4 0:22 0:022 0:089 0:978 = 4:2 10 4 P(DAj (NE, R, NE)) < P(NEj (NE, R, NE)) Rde celaska, ki ni kupila sre cke in ni gledala zrebanja najverjetneje ni bila med dobitniki. 3.10. NAKUP RA CUNALNIKA 71 3.10 Nakup ra cunalnika Tr zni analitik ra cunalni skega podjetja raziskuje trg ra cunalnikov. Anali- zirati zeli dejavnike, ki vplivajo na odlo citev potro snikov za nakup bodisi ra cunalnika PC ali MAC. Izlu s cil je naslednje dejavnike: Navada. V spletni anketi je bilo od 1000 vpra sanih 600 takih, ki so tra- dicionalno uporabljali PC; od teh se je 100 odlo cilo, da bo njihov nov ra cunalnik MAC. Skupaj so sodelujo ci v anketi kupili 470 ra cunalnikov MAC. Trg Raziskava svetovnega trga je pokazala, da evropejci ve cinoma ku- pujemo ra cunalnike PC (71 ; 5%), verjetnost, da je kupec iz EU pa je 35%. Ve c kupcev prihaja iz ZDA (40%), kjer pa prevladujejo ra cunalniki MAC (95%); preostanek je azijski trg, kjer je razmerje PC:MAC = 1,5:1. V svetovnem merilu je dele z ra cunalnikov MAC 58%. Izobrazba Od tistih, ki so se pri novem ra cunalniku odlo cili za PC, je studiralo 78% vpra sanih, od tistih, ki so se odlo cili za MAC pa 91%. Sestavi naivni Bayesov nomogram za zgornje podatke in ga komentiraj. Kateri dejavniki so bolj, kateri manj pomembni? Kaj najbolj pripomore k odlo citvi za MAC in kaj k odlo citvi za PC? Re sitev: Izberimo za ciljni razred C T = PC. Za vsak atribut A2fNavada, Trg, Izobrazbag potrebujemo pogojne verjetnosti posameznih vrednosti pri danem razredu C2fPC, MACg, da dobimo velikost vpliva x A=v na nomogramski osi atri- buta: ln P (A =vjC) P (A =vjC) Navada Iz podatkov razberemo: nov = PC nov = MAC P navada = PC 100 600 navada = MAC P 470 1000 72 POGLAVJE 3. STROJNO U CENJE Tabelo dopolnemo: nov = PC nov = MAC P navada = PC 500 100 600 navada = MAC 30 370 400 P 530 470 1000 Iz tabele preberemo potrebne pogojne verjetnosti in izra cunamo vre- dnosti x Navada=PC = ln P (Navada=PCjPC) P (Navada=PCjMAC) = ln 500=530 100=470 = ln(0:943=0:213) = 1:487 x Navada=MAC = ln P (Navada=MACjPC) P (Navada=MACjMAC) = ln 30=530 370=470 = ln(0:057=0:787) = 2:625 Trg Iz podatkov razberemo: P (PCjEU) = 0:715 P (EU) = 0:35 P (ZDA) = 0:4 P (MACjZDA) = 0:95 P (PCjAZIJA) = 1:5=(1 + 1:5) = 0:6 P (MACjAZIJA) = 1=(1 + 1:5) = 0:4 P (MAC) = 0:58 Iz teh podatkov izra cunamo: P (PC) = 1 P (MAC) = 1 0:58 = 0:42 P (EUjPC) =P (PCjEU) P (EU)=P (PC) = 0:715 0:35=0:42 = 0:596 P (MACjEU) = 1 P (PCjEU) = 0:285 P (EUjMAC) =P (MACjEU)P (EU)=P (MAC) = 0:285 0:35=0:58 = 0:172 P (PCjZDA) = 1 P (MACjZDA) = 0:05 3.10. NAKUP RA CUNALNIKA 73 P (ZDAjPC) =P (PCjZDA) P (ZDA)=P (PC) = 0:05 0:4=0:42 = 0:048 P (ZDAjMAC) =P (MACjZDA)P (ZDA)=P (MAC) = 0:95 0:4=0:58 = 0:655 P (AZIJA) = 1 (P (EU) +P (ZDA) = 0:25 P (AZIJAjPC) =P (PCjAZIJA)P (AZIJA)=P (PC) = 0:6 0:25=0:42 = 0:357 P (AZIJAjMAC) =P (MACjAZIJA)P (AZIJA)=P (MAC) = 0:4 0:25=0:58 = 0:172 Vrednosti na nomogramski osi so: x Trg=EU = ln(0:596=0:172) = 1:243 x Trg=ZDA = ln(0:048=0:655) = 2:613 x Trg=AZIJA = ln(0:357=0:172) = 0:73 Izobrazba Iz podatkov razberemo: P ( STUDIRALjPC) = 0:78 P ( STUDIRALjMAC) = 0:91 Izra cunati moramo se: P (NI STUDIRALjPC) = 1 0:78 = 0:22 P (NI STUDIRALjMAC) = 1 0:91 = 0:09 Vrednosti na nomogramski osi sta: x Izobrazba= STUDIRAL = ln(0:78=0:91) = 0:154 x Izobrazba=NI STUDIRAL = ln(0:22=0:09) = 0:894 NAVADA MAC PC TRG ZDA AZIJA EU IZOBRAZBA ˇ STUDIRAL NI ˇ STUDIRAL 74 POGLAVJE 3. STROJNO U CENJE Poglavje 4 Bayesove mre ze 75 76 POGLAVJE 4. BAYESOVE MRE ZE 4.1 Prva Dan je usmerjen graf: a b c d e f g h i a) Katere verjetnosti morajo biti podane ob grafu, da bo dobro denirana Bayesova mre za? b) Kak sen je pomen mno zice vozli s c, ki d lo cuje dani vozli s ci? c) Brez ra cunanja oceni, katera verjetnost je ve cja in utemelji svojo odlo citev: p(cje) ali p(cjde)? p(cje) ali p(cjeg)? p(cje) ali p(cjdef)? Pri tem predpostavite, da je a pozitiven vzrok za c (p(cja)>p(cj:a)) in b pozitiven vzrok za d (p(djb)>p(dj:b)). 4.1. PRVA 77 Re sitev: a) Ob vsakem vozli s cu mora biti podana njegova verjetnost pri danih star sih: p(a) p(b) p(cja);p(cj:a) p(djb);p(dj:b) p(ejcd);p(ejc:d);p(ej:cd);p(ej:c:d) p(fjd);p(fj:d) p(gje);p(gj:e) p(hjg);p(hj:g) p(ijg);p(ij:g) b) Naj mno zica S d lo cuje vozli s ci v 1 in v 2 . Potem sta v 1 in v 2 pogojno neodvisna pri dani mno zici S: p(v 1 ;v 2 jS) =p(v 1 jS) p(v 2 jS): c) p(cje) > p(cjde). Ker je c vzrok za e, se pri danem e pove ca verjetnost za c. Ce je dan tudi d, ki je alternativni vzrok za c pa se verjetnost zac zni za. Ce imate glavobol (e), je bolj verjetno, da imate virus prehlada (c), kot da ga nimate. Ce pa imate glavobol in dokazan meningitis (d), je verjetnost za prehlad manj sa, saj je meningitis alternativni vzrok za glavobol. p(cje) =p(cjeg). Ce poznamo e, potem prisotnost g ne vpliva na verjetnost c. p(cje)>p(cjdef). p(cjdef) =p(cjde), kar pa se prevede na zgor- nji primer. 78 POGLAVJE 4. BAYESOVE MRE ZE 4.2 Izrazi pogojne verjetnosti Za Bayesovo mre zo iz naloge 1 izrazi s podanimi verjetnostmi: a) p(c) b) p(gjc;d) c) p(gjc;i) d) p(dje;f) Re sitev: Pri ra cunanju v Bayesovih mre zah si pomagamo z naslednjimi pravili: 1. Verjetnost gotovega dogodka: p(XjA 1 ;:::;X;:::;A n ) = 1 2. Verjetnost nemogo cega dogodka: p(XjA 1 ;:::;:X;:::;A n ) = 0 3. Verjetnost konjunkcije: p(A^BjC) =p(AjC)p(BjA^C) 4. Verjetnost negacije: p(:XjC) = 1 p(XjC) 5. Bayesovo formula ( ce je Y naslednik odX in jeY vsebovan v pogojnem delu): p(XjY^C) =p(XjC) p(YjX^C) p(YjC) 6. Ce pogojni del ne vsebuje naslednika od X: a) ce X nima star sev, je p(XjC) =p(X), pri cemer je p(X) podan. b) ce ima X star se, je: p(XjC) = X S2P X p(XjS)p(SjC); kjer jeP X mno zica vseh mo znih stanj star sev od X. a) p(c) =p(a)p(cja) +p(:a)p(cj:a) b) p(gjc;d) 6b =p(gje)p(ejc;d) +p(gj:e)p(:ejc;d) p(ejc;d) je podana, p(:ejc;d) 4 = 1 p(ejc;d). 4.2. IZRAZI POGOJNE VERJETNOSTI 79 c) p(gjc;i) 5 =p(gjc) p(ijg;c) p(ijc) p(gjc) 6b =p(gje)p(ejc) +p(gj:e)p(:ejc) p(ejc) 6b = p(ejc;d)p(c;djc) + p(ejc;:d)p(c;:djc) + p(ej:c;d)p(:c;djc) + p(ej:c;:d)p(:c;:djc) Izrazimo se manjkajo ce faktorje: p(c;djc) 3 = p(cjc)p(djc) 1 =p(djc) = 6b = p(djb)p(bjc) +p(dj:b)p(:bjc) = 6a = p(djb)p(b) +p(dj:b)p(:b) p(c;:djc) 3 = p(cjc)p(:djc) 1;6b;6a = p(:djb)p(b) +p(:dj:b)p(:b) p(:c;djc) 3 = p(:cjc)p(djc;:c) 2 = 0 p(:c;:djc) 3 = p(:cjc)p(:dj:c) 2 = 0 (4.1) Poznamo torej vse, kar potrebujemo za izra cun p(ejc), po 4. pravilu pa znamo izra cunati tudi p(:ejc); p(gjc) smo tako izrazili samo z znanimi verjetnostmi. Nadaljujmo s p(ijg;c): p(ijg;c) 6b =p(ijg)p(gjg;c) +p(ij:g)p(:gjg;c) 1;2 = p(ijg): Verjetnost p(ijg) je dana; izraziti moramo le se p(ijc): p(ijc) 6b =p(ijg)p(gjc) +p(ij:g)p(:gjc): Ze zgoraj smo izra cunali p(gjc) in p(:gjc) = 1 p(gjc), ostalo pa je podano. d) p(dje;f) 5 =p(djf) p(ejd;f) p(ejf) p(djf) 5 =p(d) p(fjd) p(f) p(d) 6b =p(djb)p(b) +p(dj:b)p(:b) p(f) 6b =p(fjd)p(d) +p(fj:d)p(:d) 80 POGLAVJE 4. BAYESOVE MRE ZE p(ejd;f) 6b = p(ejc;d)p(c;djd;f) + p(ejc;:d)p(c;:djd;f) + p(ej:c;d)p(:c;djd;f) + p(ej:c;:d)p(:c;:djd;f) = 3 = p(ejc;d)p(cjd;f) +p(ej:c;d)p(:cjd;f) p(cjd;f) 6b = p(cja)p(ajd;f) +p(cj:a)p(:ajd;f) = 6a = p(cja)p(a) +p(cj:a)p(:a) 4.3. D-LO CEVANJE 81 4.3 d-lo cevanje Za Bayesovo mre zo iz naloge 1 zapi si vse mno zice, ki d lo cujejo naslednje pare vozli s c: a) c in d, b) b in f, c) b in i, d) h in i. Re sitev: Mno zica B d lo cuje V i in V j , ce blokira vse poti med V i in V j .Mno zica B blokira pot med V i in V j , ce obstaja tako vozli s ce V b na poti, ki blokira to pot. V b blokira pot, ce velja eden od pogojev: 1. V b 2 B je divergentno vozli s ce oz. skupni vzrok ( V b je v B in obe povezavi na poti ka zeta iz V b ), 2. V b 2 B je zaporedno vozli s ce ( V b je v B in ena povezava na poti ka ze v V b in ena iz V b ), 3. V b = 2 B je konvergentno vozli s ce oz. skupna posledica (obe povezavi na poti ka zeta v V b ) in niti V b niti noben njegov naslednik ni v B. a) Iz pogoja 3 sledi, da c in d d lo cujejo vse mno zice, ki ne vsebujejo vozli s c e, g, h in i: fg,fag,fbg,ffg,fa;bg,fa;fg,fb;fg,fa;b;fg b) Na poti med b in f je samo d, ki je zaporedno vozli s ce. Najmanj sa mno zica, ki d lo cuje b in f jefdg. Re sitev pa je tudi vsaka mno zica, ki vsebuje vozli s ce d, npr.fd;ag;fd;g;hg (ker je takih mno zic veliko, tu ne navajamo vseh). c) Najmanj se mno zice, ki d lo cujejo b ini so:fdg;feg;fgg. Vsako od teh vozli s c namre c blokira pot od b do i. Tudi vsaka mno zica, ki vsebuje najmanj eno od vozli s c d;e;g, d lo cuje b in i. d) Vozli s ce g blokira pot med h in i, ker je njun skupni vzrok. Zato vse mno zice, ki vsebujejo g d lo cujejo h in i. 82 POGLAVJE 4. BAYESOVE MRE ZE 4.4 Pre(za)pletena BM Dana je struktura Bayesove mre ze: a b c d e a) Brez ra cunanja oceni, katera verjetnost je ve cja: p(aje) ali p(aje;b). Predpostavi, da velja: p(eja)>p(ej:a) in p(ejb)>p(ej:b). b) Izrazi pogojno verjetnost p(djc) z verjetnostmi, ki morajo biti podane za zgornjo strukturo mre ze. c) Zapi si vse mno zice, ki d lo cujejo c in b. Re sitev: a) Tako oceno lahko podamo samo pri predpostavki, da povezave med vozli s ci pomenijo pozitiven vzrok. V na sem primeru mora torej ve- ljati: p(eja) > p(a) in p(ejb) > p(b). Ob tej predpostavki je p(aje) > p(aje;b), ker je b alternativni vzrok za e, zato zmanj sa verjetnost a-ju. b) Podane morajo biti naslednje verjetnosti: p(a);p(b), p(cja);p(cj:a); p(dja;b);p(dja;:b);p(dj:a;b);p(dj:a;:b) p(eja;b;d);p(eja;b;:d);p(eja;:b;d);p(eja;:b;:d) p(ej:a;b;d);p(ej:a;b;:d);p(ej:a;:b;d);p(ej:a;:b;:d) p(djc) = p(dja;b)p(a;bjc) + p(dja;:b)p(a;:bjc) + p(dj:a;b)p(:a;bjc) + p(dj:a;:b)p(:a;:bjc) p(a;bjc) = p(ajc)p(bja;c) = = p(a) p(cja) p(c) p(bja;c) p(c) = p(cja)p(a) +p(cj:a)p(:a) p(bja;c) = p(b) 4.4. PRE(ZA)PLETENA BM 83 Zaradi neodvisnosti b in c bi lahko sklepali tudi takole: p(a;bjc) =p(ajc)p(bjc) =p(ajc)p(b): p(a;:bjc) = p(ajc)p(:bja;c) = = p(a) p(cja) p(c) p(:bja;c) = p(:bja;c) = p(:b) = 1 p(b) p(:a;bjc) = p(:ajc)p(bja;c) = = p(:a) p(cj:a) p(c) p(bja;c) p(:a;:bjc) = p(:ajc)p(:bja;c) = = p(:a) p(cj:a) p(c) p(:bja;c) c) Od c do b vodijo 4 neusmerjene poti. Za vsako od njih bomo poiskali mno zice, ki jih blokirajo. 1. c a d b: a je divergentno vozli s ce, torej fag in vsaka mno zica, ki vsebuje a blokira to pot. Torej tudi: fa;dg;fa;eg;fa;d;eg. Vozli s ce d je konvergentno, iz cesar sledi, da vse mno zice, ki ne vsebujejo d in njegovih naslednikov (e), blokirajo to pot: fg in fag, ki pa jo imamo ze zgoraj. 2. c a e b: Po istem premisleku kot zgoraj, namesto vozli s ca d imamo zdaj na poti e, ki pa je tako kot d konvergentno: fag;fg;fa;dg;fa;eg;fa;d;eg. 3. c a d e b: Vozli s ce a blokira pot in podobno kot prej,fag in vsaka mno zica, ki vsebuje a, blokira to pot. Vozli s ce d na tej poti je zaporedno, torej tudifdg in vsaka mno zica, ki vsebuje d, blokira to pot. Ker jee konvergentno, tudifg blokira to pot. Vse mno zice, ki jih dobimo na tej poti so: fg;fag;fdg;fa;dg;fa;eg;fd;eg;fa;d;eg. 4. c a e d b: Premislek in re sitev sta taka, kot za pot c a d e b. Povzemimo: vozli s ci c in b d-lo cujejo: fg;fag;fa;dg;fa;eg;fa;d;eg. 84 POGLAVJE 4. BAYESOVE MRE ZE 4.5 Zadnja Podane so naslednje strukture Bayesovih mre z S1, S2 in S3: S1: a b c d S2: a b c d S3: a b c d a) Koliko podatkov prihrani posamezna struktura v primerjavi s tem, ko Bayesova mre za sploh ni podana? b) Ali je mo zno podatke o verjetnostih za strukturo S1 prevesti v po- datke za S2 tako, da bosta obe Bayesovi mre zi denirali enako skupno verjetnostno porazdelitev vseh spremenljivk? Utemelji podgovor. c) Zapi si vse mno zice, ki d-lo cujejo a in b za vsako od podanih mre z. Re sitev: a) Ce mre za ni podana potrebujemo 2 4 1 = 15 podatkov o (pogojnih) verjetnostih. Pri S1 potrebujemo samo naslednje podatke: p(a);p(bja);p(bj:a);p(cjb);p(cj:b);p(djc);p(dj:c); kar nam prihrani 15-7=8 podatkov. Po podobnem premisleku za S2 potrebujemo 8 podatkov, torej jih prihranimo 7. Pri S3 ne prihranimo ni cesar. b) Ne, ker v S1 je b odvisen od a, medtem ko sta v S2 neodvisna (velja p(a;b) =p(a)p(b)). c) S1: Ne obstaja mno zica, ki bi d-lo cevala a in b. S2: Take so vse mno zice, ki ne vsebujejo c in d:fg S3: Imamo 5 poti, ki jih moramo pregledati: za poti a c b in a d b je re sitev enaka zgornji. Za poti a c d b,a d c b je c zaporedno, d pa konvergentno vozli s ce. Ker je c zaporedno, mno zici fcg;fc;dg blokirata obe poti. Prav tako ju blokiratafcg infg, ker je d konvergentno. Preostane nam se najkraj sa pot, a b, ki pa je ni mo zno d-lo citi. Ker ne obstaja mno zica, ki bi blokirala vse na stete poti, zaklju cimo, da a inb ni mo zno d-lo citi.