UL/FRI/VSP-RI/MUI/Izpiti/2006-09-04

Rezultati pisnega izpita na: http://ai.fri.uni-lj.si/dorian/mui/lmuirez.htm

Ustni izpit: 7.09 ob 11h v pisarni prof. Kononenka.

1. naloga (20%)

Naj bosta prostor stanj ter hevristična funkcija h podana s spodnjim programom.

s(a, b, 7). s(a, c, 2).
s(b, c, 3). s(b, d, 2).
s(c, d, 3). s(c, e, 7).
s(d, b, 1). s(d, e, 4).

h(a, 0). h(b, 0). h(c, 6).
h(d, 2). h(e, 0).

goal(e).

a) Katero rešitveno pot najde algoritem A* in v kakšnem zaporedju razvija vozlišča? Napiši zaporedje razvitih vozlišč, rešitveno pot in ceno rešitvene poti!

b) Ali hevristična funkcija v tej nalogi izpolnjuje pogoj o popolnosti? Odgovor utemelji!

c) Koliko vozlišč obišče algoritem iterativno poglabljanje preden najde prvi rešitev? Napiši koliko vozlišč obišče algoritem na vsakem nivoju!

2. naloga (35%)

Pri učenju razreda z vrednostmi A, B in C iz 15 primerov smo se naučili odločitvenega drevesa s korenom in tremi listi. V korenu drevesa je atribut, ki ima tri možne vrednosti. Porazdelitev primerov po razredih v listih drevesa je:

List 1: 6xA, 0xB, 2xC
List 2: 1xA, 1xB, 2xC
List 3: 1xA, 0xB, 2xC

a) Izračunaj informacijski pridobitek atributa v korenu drevesa!

b) Oceni klasifikacijsko točnost tega drevesa z uporabo Laplacove ocene!

c) Oceni klasifikacijsko točnost tega drevesa z uporabo m-ocene, pri čemer določimo apriorne verjetnosti z relativno frekvenco na celotni množici primerov in vzamemo m=2.

d) Kdaj oziroma pri kateri metodi za ocenjevanje verjetnosti je mogoče da v Listu 2 (presenteljivo) klasificiramo v razred A in ne v večinski razred C. Določi pogoj ki mora veljati za parameter ustrezne ocene verjetnosti da drevo klasificira v razred A!

3. naloga (20%)

S spodnjimi pravili je podana baza znanja preprostega ekspertnega sistema:

rule1:: if b and c then a
rule2:: if d then b
rule3:: if e then b
rule4:: if f then b
rule5:: if h and g then c

fact(e).                    % e is known as a fact
fact(f). fact(g). fact(h).
askable(d).                 % E.S. is permitted to ask the user if d is true

a) Nariši and/or graf ki ustreza podanim pravilom!

b) Denimo da je ekspertni sistem na uporabnikovo vprašanje "Is it true: a?" odgovoril z "yes", ne da bi pri tem vprašal uporabnika o resničnosti d. Nariši vsa možna rešitvena drevesa, po katerih bi lahko ekspertni sistem dokazal da je a resnično.

c) Denimo da ekspertni sistem, po uporabnikovem vprašanju "Is it true: a?", vpraša uporabnika o resničnosti d ("Is it true: d?"), uporabnik pa vpraša zakaj ekspertni sistem potrebuje ta podatek ("why?"). Napiši odgovor, ki bi ga dal ekspertni sistem na to vprašanje!

4. naloga (25%)

a) Kdaj rečemo da algoritem hevrističnega iskanja (napr. A* ali IDA*) razvija vozlišča v prioritetnem vrstnem redu?

b) Kdaj rečemo, da je ocenitvena funkcija f monotona? Podaj enostaven primer, ko funkcija f ni monotona!

c) Večina algoritmov za učenje odločitveni dreves pri izbiri najboljšega atributa, ki ga da v koren poddrevesa minimizira neko mero nečistoče. Ali je rezultat takega pristopa vedno odločitveno drevo, ki ima na učni množici manjšo napako od vseh ostalih dreves z enakim številom listov? Odgovor utemelji!

d) Denimo da želiš, v sodelovanju z ekspertom z nekega področja (napr. zdravnikom), poiskati pravilo ki pojasnjuje njegove odločitve (napr. diagnoze). Uporabiti želiš strojno učenje iz dovolj velikega števila primerov, ki jih pripravi ekspert. Denimo, da uporabiš odločitvena drevesa in dobiš s križnim preverjanjem zelo slabe rezultate. Napiši vsaj 3 možne razlage za slabe rezulate! Za vsako razlago na kratko predlagaj/opiši rešitve, ki bi lahko vodile do "boljših" pravil!