Predik´ atov´ a logika, situaˇ cn´ı kalkulus, produkˇ cn´ı syst´ emy Jiˇr´ı Kl´ ema Katedra kybernetiky, ˇ FEL, CVUT v Praze
http://ida.felk.cvut.cz/moodle/
pLogika jako n´ astroj pro reprezentaci znalost´ı
Jak´e vhodn´e vlastnosti demonstrovala v´yrokov´a logika? − deklarativnost ∗ znalosti a usuzov´an´ı jsou pˇrirozenˇe oddˇeleny, ∗ procedur´aln´ı jazyky – postr´adaj´ı obecn´y mechanismus pro usuzov´an´ı. − moˇznost vyj´adˇrit ne´uplnou informaci ∗ pomoc´ı disjunkce (a negace), ∗ “Z´ıtra odpoledne p˚ ujdu do kina nebo budu sportovat.” ∗ nen´ı samozˇrejmost´ı (datab´aze, datov´e struktury). − je kompoziˇcn´ım a kontextovˇe nez´avisl´ym jazykem ∗ v´yznam vˇety je funkc´ı v´yznamu jejich ˇc´ast´ı, ∗ v´yznam A ∧ B m´a vztah k pravdivosti A a B, ∗ na rozd´ıl od pˇrirozen´eho jazyka: “Pak to vidˇela.”
http://ida.felk.cvut.cz/moodle/
pPredik´ atov´ a logika (PL)
V´yrokov´a logika m´a omezenou expresivitu − probl´emy se ˇsk´alov´an´ım ve wumpusovˇe svˇetˇe, nem´a siln´e mechanismy pro zobecnˇen´ı, − napˇr. rozmˇery bludiˇstˇe ∗ Vˇsechna pole soused´ıc´ı s wumpusem zap´achaj´ı. ∗ W1,2 ⇒ (S1,1 ∧ S2,2 ∧ S1,3), W2,1 ⇒ (S1,1 ∧ S2,2 ∧ S3,1) atd. − d´ale vztahy mezi objekty, ˇcas, − dˇr´ıve zm´ınˇen´y Aristotel˚ uv sylogismus o Sokratovi.
PL zav´ad´ı objekty a relace mezi nimi − inspiruje se v s´ıle pˇrirozen´eho jazyka, zachov´av´a ale jednoznaˇcnost.
PL 1.ˇr´ adu (first-order logic, FOL) − z´amˇern´e omezen´ı expresivity: ∗ relace samotn´e nelze povaˇzovat za objekty, ∗ nelze zapisovat tvrzen´ı o vˇsech relac´ıch, tj. napˇr. obecnˇe definovat tranzitivitu.
logiky vyˇsˇs´ıch ˇr´ad˚ u − vˇetˇs´ı expresivita, obt´ıˇznˇejˇs´ı teorie i efektivn´ı pouˇzit´ı.
http://ida.felk.cvut.cz/moodle/
pPredik´ atov´ a logika 1.ˇr´ adu – syntaxe
Syntaxe – elementy jazyka − konstanty odkazuj´ı na konkr´etn´ı objekty ∗ petr, pavel, skotsko, z´aklady-umˇel´e-inteligence (Prolog: zaˇc´ınaj´ı mal´ym p´ısmenem). − predik´ aty vyjadˇruj´ı vztahy mezi objekty ˇci jejich vlastnosti, ∗ muˇz(petr), otec(petr,pavel), ˇzije(petr,skotsko) (arita = poˇcet prvk˚ u relace). − funkce jako nepˇr´ım´e odkazy na objekt, ∗ otec(petr), ˇzije(petr) (jak je vidˇet, funkce lze nahradit predik´aty). − promˇ enn´ e odkazuj´ı na mnoˇziny objekt˚ u, ∗ X, Y, Z (Prolog: zaˇc´ınaj´ı velk´ym p´ısmenem). − kvantifik´ atory urˇcuj´ıc´ı interpretaci promˇenn´ych ∗ ∀ (pro vˇsechny) – pˇri jak´ekoli substituci objektu za promˇennou vˇeta plat´ı, ∗ ∃ (existuje) – lze nal´ezt objekt, kter´y pˇri substituci za promˇennou zajist´ı platnost vˇety, ∗ ∀ X ∃ Y uˇc´ı(X,Y) – kaˇzd´y pˇredmˇet m´a alespoˇn jednoho uˇcitele. − logick´ e spojky a z´avorky ∗ stejn´e jako ve v´yrokov´e logice.
V souvislosti se znaˇcen´ım konstant, funkc´ı a predik´at˚ u mluv´ıme o symbolech.
http://ida.felk.cvut.cz/moodle/
pPredik´ atov´ a logika 1.ˇr´ adu – syntaxe
Syntaxe – definice korektn´ıch v´yrokov´ych formul´ı − term je kaˇzd´a konstanta, promˇenn´a nebo funkce na nˇe aplikovan´a ∗ odkazuje na objekt, nic jin´eho termem nen´ı (tj. predik´aty nejsou termy). − dobˇre utvoˇrenou formul´ı (well-formed formula (WFF)) jsou ∗ atomick´ e formule p(t1, . . . , tn), kde p je predik´atov´y symbol a ti termy, ∗ formule ¬p a p ⇒ q, pokud p a q jsou WFF, ∗ formule ∀Xp, pokud X je promˇenn´a a p WFF.
Syntaxe pozn´amky − WFF m˚ uˇze obsahovat voln´e promˇenn´e (nev´azan´e kvantifik´atorem), ∗ to p˚ usob´ı probl´emy pˇri interpretaci WFF, vˇ eta je WFF pouze s v´azan´ymi promˇenn´ymi. − z hlediska definice jsou spojky ∨, ∧, ⇔ a kvantifik´ator ∃ odvozen´e.
http://ida.felk.cvut.cz/moodle/
pPredik´ atov´ a logika 1.ˇr´ adu – s´ emantika, interpretace
Jak urˇcovat platnost vˇet v PL 1.ˇr´adu? Je d´ana kontextem, ale ...
Ovˇeˇrov´an´ı pravdivosti pro vˇsechny modely? − pracujeme s velk´ymi nebo neomezen´ymi dom´enami (napˇr. re´aln´a ˇc´ısla), − v d˚ usledku m˚ uˇze existovat i neomezen´y poˇcet model˚ u.
Interpretace definuje: − kter´e objekty, predik´aty a fce odpov´ıdaj´ı pˇr´ısluˇsn´ym symbol˚ um a jejich v´yznam ˇ ∗ dom´ ena ∆ = {Jiˇr´ı Kl´ema, Filip Zelezn´ y, STM Y33ZUI, BK X33KUI}, ∗ interpretace konstant: lC : C → ∆, jirka odkazuje na Jiˇr´ıho Kl´emu, zui na pˇredmˇet STM Y33ZUI, atd. ∗ interpretace predik´at˚ u s aritou n: lP : P → P (∆n), uˇc´ı odkazuje na vztah mezi uˇcitelem a pˇredmˇetem, uˇc´ı/2 = {{jirka,zui},{filip,kui}}.
Je formule ∀X(p(X) ∨ q(X)) ⇒ (∀Xp(X) ∨ ∀Xq(X)) tautologi´ı? − pro vyvr´acen´ı staˇc´ı nal´ezt interpretaci v n´ıˇz formule neplat´ı, − napˇr. v interpretaci ∆={a,b}, pD = {a}, qD = {b}, − lev´a strana implikace plat´ı: X=a: p(a)∨q(a) = T ∨F = T , X=b: p(b)∨q(b) = F ∨T = T , − prav´a strana ne: X=b: p(b) = F , ∀Xp(X) = F podobnˇe pro X=a a ∀Xq(X) = F .
http://ida.felk.cvut.cz/moodle/
pInference v PL 1.ˇr´ adu – unifikace
Jak korektnˇe substituovat za voln´e promˇenn´e resp. termy pˇri srovn´av´an´ı v´yraz˚ u? − dotaz: Koho zn´a Jirka? − ?zna(jirka,X) – vraˇt vˇsechny korektn´ı substituce za volnou promˇennou vzhledem ke KB, − KB: Jirka zn´a Filipa. V´aclava zn´a kaˇzd´y. Kaˇzd´y zn´a svoji matku. Monika nˇekoho zn´a. − zna(jirka, f ilip), ∀Y zna(Y, vaclav), ∀Zzna(Z, matka(Z)), ∃W zna(monika, W ), − zna(jirka, f ilip), zna(Y, vaclav), zna(Z, matka(Z)), zna(monika, s1), − substituce: θ1 = {X|f ilip}, θ2 = {jirka|Y, X|vaclav}, θ3 = {jirka|Z, X|matka(jirka)}, − hled´ame co nejobecnˇ ejˇs´ı substituci, aby v´yrazy byly unifikovateln´e.
Substituce a unifikace nutn´a pro jakoukoli inferenci, viz. generalizovan´y modus ponens A, A ⇒ B p01, . . . , p0n, (p1 ∧ p2 ∧ · · · ∧ pn ⇒ q) → B Subst(θ, q) Subst(θ, p0i) = Subst(θ, pi) − Kdyˇz se dva lid´e znaj´ı, tak se zdrav´ı. → ∀XY (zna(X, Y ) ⇒ zdravi se(X, Y )) − aplikace MP na KB ` zdravi se(jirka, f ilip), zdravi se(Y, vaclav), zdravi se(U, matka(U )), zdravi se(monika, s1).
http://ida.felk.cvut.cz/moodle/
pInference v PL 1.ˇr´ adu – rezoluˇ cn´ı pravidlo
U rezoluce unifikace zejm´ena pˇri identifikaci doplˇnkov´ych liter´al˚ u ˇ zn´a kaˇzd´y z katedry. → ∀X(z katedry(X) ⇒ zna(X, vlada)), − Vl´adu − klauzule: ¬z katedry(X) ∨ zna(X, vlada) − klauzule viz. minul´y slajd: ¬zna(U, V ) ∨ zdravi se(U, V ), − substituce: θ = {V |vlada, X|U }, − rezolventa: ¬z katedry(U ) ∨ zdravi se(U, vlada).
http://ida.felk.cvut.cz/moodle/
pRezoluce v PL 1.ˇr´ adu – pˇrevod do CNF (1)
Obt´ıˇznˇejˇs´ı pˇrevod do CNF neˇz u v´yrokov´e logiky – promˇenn´e a kvantifik´atory ˇ ıman´e, kteˇr´ı znaj´ı Markuse, budˇ nen´avid´ı Caesara nebo si mysl´ı, ˇze kaˇzd´y kdo Pˇr: Vˇsichni R´ nˇekoho nen´avid´ı je bl´azen. ∀X (riman(X) ∧ zna(X, markus)) ⇒ (nenavidi(X, caesar) ∨ ∀Y ∃Z(nenavidi(Y, Z) ⇒ ma za blazna(X, Y ))) Obecn´e kroky pˇrevodu: 1. odstranˇen´ı implikac´ı ∀X ¬(riman(X) ∧ zna(X, markus))∨ (nenavidi(X, caesar) ∨ ∀Y ¬(∃Znenavidi(Y, Z)) ∨ ma za blazna(X, Y ))) 2. pˇresun negac´ı k atomick´ym formul´ım ∀X ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ∀Y ∀Z(¬nenavidi(Y, Z) ∨ ma za blazna(X, Y )) 3. skolemizace – eliminace existenˇcn´ıch kvantifik´ator˚ u, − zde ˇz´adn´y v´yskyt, ale: ∀X∃Y otec(Y, X) → ∀Xotec(s1(X), X) − s1 je v dan´em pˇr´ıpadˇe Skolemovou funkc´ı (kaˇzd´emu X pˇriˇrazuje otce)
http://ida.felk.cvut.cz/moodle/
pRezoluce v PL 1.ˇr´ adu – pˇrevod do CNF (2)
Obecn´e kroky pˇrevodu (pokr.): 5. oddˇelen´ı jmen promˇenn´ych − pro formule typu: ∀Xriman(X) ∨ ∀Xrek(X) → ∀Xriman(X) ∨ ∀Y rek(Y ) 6. pˇresun univerz´aln´ıch kvantifik´ator˚ u zcela vlevo – prenexn´ı tvar, ∀XY Z ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ¬nenavidi(Y, Z) ∨ ma za blazna(X, Y ) 7. pˇresun disjunkc´ı k liter´al˚ um − aplikace distributivn´ıch z´akon˚ u a ∨ (b ∧ c) → (a ∨ b) ∧ (a ∨ c) 8. eliminace univerz´aln´ıch kvantifik´ator˚ u – bezkvantifik´atorov´e j´adro. ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ¬nenavidi(Y, Z) ∨ ma za blazna(X, Y )
http://ida.felk.cvut.cz/moodle/
pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3
:: Pokud v´am ˇreknu, ˇze:
(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.
(S2) Pouze pt´aci a savci jsou teplokrevn´ı.
(S3) Zuzana, m˚ uj p´asovec, je teplokrevn´a a nem´a peˇr´ı.
(S4) Kaˇzd´y pt´ak m´a peˇr´ı.
:: a zept´am se: (D) Klade Zuzana vejce?
http://ida.felk.cvut.cz/moodle/
pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3
:: Pokud v´am ˇreknu, ˇze:
(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.
(S2) Pouze pt´aci a savci jsou teplokrevn´ı.
(S3) Zuzana, m˚ uj p´asovec, je teplokrevn´a a nem´a peˇr´ı.
(S4) Kaˇzd´y pt´ak m´a peˇr´ı.
:: a zept´am se: (D) Klade Zuzana vejce? :: Inference v pˇrirozen´em jazyce:
Zuzana nem´a peˇr´ı a proto nen´ı pt´ak.
Zuzana je teplokrevn´a a nen´ı pt´ak, proto mus´ı b´yt savec.
Zuzana je savec a p´asovec, protoˇze nen´ı jeˇzura ani ptakopysk nem˚ uˇze kl´ast vejce.
:: Jak realizovat strojovˇe? Reprezentace pomoc´ı ˇretˇezc˚ u je problematick´a z hlediska odvozov´an´ı nov´ych tvrzen´ı ...
http://ida.felk.cvut.cz/moodle/
pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (1) :: Pˇrepis do predik´atov´e logiky 1.ˇr´adu:
(S1) ∀X(savec(X) ∧ vejce(X) ⇒ jezura(X) ∨ ptakopysk(X))
(S2) ∀X(teplokrevny(X) ⇒ ptak(X) ∨ savec(X))
(S3) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)
(S4) ∀X(ptak(X) ⇒ peri(X))
(F) ∀X(pasovec(X) ⇒ ¬(ptakopysk(X) ∨ jezura(X)))
(D) vejce(zuzana)
http://ida.felk.cvut.cz/moodle/
pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (1) :: Pˇrepis do predik´atov´e logiky 1.ˇr´adu:
(S1) ∀X(savec(X) ∧ vejce(X) ⇒ jezura(X) ∨ ptakopysk(X))
(S2) ∀X(teplokrevny(X) ⇒ ptak(X) ∨ savec(X))
(S3) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)
(S4) ∀X(ptak(X) ⇒ peri(X))
(F) ∀X(pasovec(X) ⇒ ¬(ptakopysk(X) ∨ jezura(X)))
(D) vejce(zuzana)
:: Transformace do klauz´aln´ı formy:
(C1) ¬savec(X) ∨ ¬vejce(X) ∨ jezura(X) ∨ ptakopysk(X)
(C2) ¬teplokrevny(X) ∨ ptak(X) ∨ savec(X)
(C3,4,5) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)
(C6) ¬ptak(X) ∨ peri(X)
(C7,8) (¬pasovec(X) ∨ ¬ptakopysk(X)) ∧ (¬pasovec(X) ∨ ¬jezura(X))
(C9) vejce(zuzana)
http://ida.felk.cvut.cz/moodle/
pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (2) :: Strom rezoluˇcn´ıho zam´ıtnut´ı:
:: Tvrzen´ı, ˇze Zuzana klade vejce je ve sporu s teori´ı. Zuzana vejce neklade.
http://ida.felk.cvut.cz/moodle/
pPL ve wumpusovˇ e svˇ etˇ e
PL je dostateˇcnˇe expresivn´ı pro popis wumpusova svˇeta a inferenci v nˇem
reprezentace prostˇred´ı − sousednost jeskyn´ı ∀XY AB [sousedi([X, Y ], [A, B]) ⇔ [A, B] ∈ {[X + 1, Y ], [X − 1, Y ], [X, Y + 1], [X, Y − 1]}] − diagnostick´a pravidla – od pozorovateln´ych jev˚ u k jejich pˇr´ıˇcin´am – pro v´yskyt v´anku ∀S (vanek(S) ⇒ ∃R (sousedi(R, S) ∧ sachta(R))), ∀S (¬vanek(S) ⇒ ¬∃R (sousedi(R, S) ∧ sachta(R))), − kauz´aln´ı pravidla – vlastnosti prostˇred´ı generuj´ı vnˇejˇs´ı projevy – pro jeskynˇe ∀R (sachta(R) ⇒ ∀S (sousedi(R, S) ⇒ vanek(S))), ∀S [∀R sousedi(R, S) ⇒ ¬sachta(R)] ⇒ ¬vanek(S), − v´yˇse uveden´a diagnostick´a a kauz´aln´ı pravidla jsou ekvivalentn´ı z´apisu: ∀S (vanek(S) ⇔ ∃R (sousedi(R, S) ∧ sachta(R))) .
obt´ıˇznˇejˇs´ı je zachycen´ı vn´ım´an´ı, reflexe, modifikace prostˇred´ı − vn´ım´an´ı (T vyjadˇruje ˇcas, resp. ˇc´ıslo kroku) ∀T SB (senzory([S, B, trpyt], T ) ⇒ trpyt(T )) − reflexe ∀T (trpyt(T )) ⇒ nejlepsi akce(uchop, T ))
http://ida.felk.cvut.cz/moodle/
pSledov´ an´ı zmˇ en
fakta plat´ı v konkr´etn´ıch situac´ıch, sp´ıˇse neˇz vˇeˇcnˇe,
situaˇ cn´ı kalkul je jedn´ım ze zp˚ usob˚ u reprezentace zmˇen ve FOL, − predik´aty dˇel´ı na nemˇenn´e (rigid, eternal) a flexibiln´ı (fluents), − pˇrid´av´a situaˇcn´ı argument ke kaˇzd´emu predik´atu s moˇznou zmˇenou platnosti, − flexibiln´ı napˇr. drzi(zlato, nyni), term nyni oznaˇcuje situaci, − nemˇenn´y napˇr. sachta(R), sousedi(R, S) − situace jsou v´az´any result funkc´ı, − v´ysledkem result(a, s) je situace, do n´ıˇz dospˇejeme proveden´ım akce a v situaci s.
http://ida.felk.cvut.cz/moodle/
pPopis a pouˇ zit´ı akc´ı
“d˚ usledkov´y” axiom – popisuje zmˇeny, kter´e jsou v´ysledkem akce − ∀s seZlatem(s) → drzi(zlato, result(uchop, s))
axiom “r´amce” – popisuje, co akce nezmˇ enila − ∀s maSip(s) → maSip(result(uchop, s))
probl´ em r´ amce: jak elegantnˇe zvl´adnout fakta beze zmˇeny (a) reprezentaˇcn´ı – vyhni se axiom˚ um r´amce, pro F flexibiln´ıch predik´at˚ u a A akc´ı potˇrebujeme O(F A) axiom˚ u r´amce. (b) inferenˇcn´ı – vyhni se opakovan´emu pˇrepisov´an´ı k udrˇzen´ı informace o stavu,
kvalifikaˇ cn´ı probl´ em − vˇern´y popis re´aln´ych akc´ı vyˇzaduje nekoneˇcnou p´eˇci, − co kdyˇz zlato bude kluzk´e nebo pˇribit´e k zemi nebo . . . ?
probl´ em d˚ usledku − skuteˇcn´e akce maj´ı mnoho skryt´ych d˚ usledk˚ u, − s agentem se pˇresouv´a vˇse co drˇz´ı, se zlatem se pˇresouv´a i prach, rukavice se opotˇrebov´avaj´ı,
http://ida.felk.cvut.cz/moodle/
pPopis a pouˇ zit´ı akc´ı
axiomy “n´asledn´ych stav˚ u” ˇreˇs´ı reprezentaˇcn´ı probl´em r´amce,
kaˇzd´y axiom se dot´yk´a predik´atu (a nikoli akce samotn´e) P plat´ı po proveden´ı akce ⇔ [akce vedla ke splnˇen´ı P ∨ P jiˇz platilo a akce P nezneplatnila]
pro manipulaci se zlatem ∀a, s drzi(zlato, Result(a, s)) ⇔ [(a = uchop ∧ seZlatem(s)) ∨ (drzi(zlato, s) ∧ a 6= uvolni)]
dostaneme F axiom˚ u s celkov´ym poˇctem liter´al˚ u O(AE) (E je poˇcet efekt˚ u na akci).
http://ida.felk.cvut.cz/moodle/
pVytv´ aˇren´ı pl´ an˚ u
poˇc´ateˇcn´ı podm´ınky v b´azi znalost´ı − poloha(agent, [1, 1], s0), poloha(zlato, [1, 2], s0),
dotaz: − Zjisti(KB, ∃s drzi(zlato, s)), − tj., v jak´e situaci budu drˇzet zlato?
ˇ odpovˇed: − {s/result(uchop, result(jdi vpred, s0))}, − tj., jdi vpˇred a pot´e uchop zlato,
pˇredpoklady: − agent se zaj´ım´a pouze o pl´any zapoˇc´ınaj´ıc´ı v s0, − s0 je jedinou situac´ı popsanou v KB.
http://ida.felk.cvut.cz/moodle/
pVytv´ aˇren´ı pl´ an˚ u: lepˇs´ı zp˚ usob
vyj´adˇri pl´any jako posloupnosti akc´ı [a1, a2, . . . , an],
planResult(p, s) je v´ysledkem proveden´ı pl´anu p ve stavu s − projekˇcn´ı u´loha – jak´a je v´ysledn´a situace po aplikov´an´ı dan´e posloupnosti akc´ı? pozice(agent, [1, 1], s0) ∧ pozice(zlato, [1, 1], s0) ∧ ¬drzi(O, s0) pozice(zlato, [1, 1], result([jdi([1, 1], [1, 2]), uchop(zlato), jdi([1, 2], [1, 1])], s0)) − pl´anovac´ı u´loha – jak´a posloupnost akc´ı vede k dan´e situaci?
dotaz Zjisti(KB, ∃p drzi(zlato, planResult(p, s0))) − m´a ˇreˇsen´ı {p/[jdi vpred, uchop]},
definice planResult v r´amci result − ∀s planResult([ ], s) = s, − ∀a, p, s planResult([a|p], s) = planResult(p, result(a, s)),
viz pl´ anov´ an´ı prob´ıran´e dˇr´ıve − specializovan´e pl´anovac´ı syst´emy uspˇeˇsnˇejˇs´ı neˇz obecn´e usuzov´an´ı.
http://ida.felk.cvut.cz/moodle/
pKdy predik´ atov´ a logika nen´ı vhodn´ a?(1)
Pro nemonot´ onn´ı odvozov´an´ı → nemonot´onn´ı logiky, − monot´onnost PL – pˇrid´an´ım nov´eho tvrzen´ı nelze zruˇsit platnost tvrzen´ı dˇr´ıve odvozen´eho, − protipˇr´ıkladem je vhodnost pˇripuˇstˇen´ı obecn´ych tvrzen´ı a jejich v´yjimek: ∗ Kaˇzd´y pt´ak l´et´a. Tuˇcnˇ´aci jsou pt´aci. Quido je tuˇcnˇ´ak. ` Quido l´et´a. ∗ v´yjimka: Tuˇcnˇ´aci nel´etaj´ı. ` Quido nel´et´a. ∗ v PL jde o nekonzistentn´ı b´azi znalost´ı a lze z n´ı rezoluc´ı odvodit cokoli.
Pro pr´aci s ˇ casem → tempor´aln´ı mod´aln´ı logika, − lze i pˇr´ımo v PL ∗ zabit(caesar,brutus,-44), ∀ X Y T (zabit(X,Y,T) ∧ T
http://ida.felk.cvut.cz/moodle/
pKdy predik´ atov´ a logika nen´ı vhodn´ a?(2)
Vyj´adˇren´ı nejistoty → fuzzy logika, Dempster-Shaferova teorie, pravdˇepodobnost − pˇr´ıˇciny: omezen´a pozorovatelnost svˇeta, nedeterministick´e vztahy mezi objekty nebo v´ysledky akc´ı, zjednoduˇsen´ı kv˚ uli efektivitˇe, − pˇr´ıklad fuzzy pravidla: pokud je chladn´ e poˇ cas´ı a cena ropy je n´ızk´ a, pak je topen´ı zapnuto naplno, − lingvistick´ e promˇ enn´ e nab´yvaj´ı mnoˇziny hodnot, kaˇzd´a hodnota je fuzzy mnoˇ zinou.
Vyj´adˇren´ı pˇresvˇ edˇ cen´ı, v´ıry → podpˇr´ıpad nejistoty, mod´aln´ı logika − pˇr´ıklad 1: Alenka v´ı, ˇze je Bert´ık pˇresvˇedˇcen, ˇze Cyril lˇze. Alenka vˇeˇr´ı, ˇze Bert´ık je neomyln´y. Tedy: Alenka vˇeˇr´ı, ˇze Cyril lˇze. ˇ − pˇr´ıklad 2: A v´ı, ˇze V´aclav Klaus je V´aclav Klaus. V´aclav Klaus je prezidentem CR. ˇ ??? Plat´ı, ˇze: A v´ı, ˇze V´aclav Klaus je prezidentem CR
http://ida.felk.cvut.cz/moodle/
pProdukˇ cn´ı syst´ em
Soubor produkˇcn´ıch pravidel − pravidlo: situace ⇒ akce, obecn´a znalost, − situaˇcn´ı ˇc´ast pravidla popisuje podm´ınku, za n´ıˇz m˚ uˇze b´yt pravidlo pouˇzito − situace = konjunkce podm´ınek, − akce (pˇridej, odeber, zmˇenˇ) nebo jejich sekvence,
B´aze dat (pracovn´ı pamˇeˇt) − popisuje okamˇzit´y stav probl´emu, − obsahuje poˇc´ateˇcn´ı i odvozen´a data,
Inferenˇcn´ı stroj (interpret pravidel) − porovn´av´a b´azi dat se situacemi v pravidlech, − vyb´ır´a vhodn´a pravidla (ˇreˇs´ı konflikty), − prov´ad´ı jimi definovan´e akce - upravuje pamˇeˇt, − pˇr´ım´e (nebo zpˇetn´e) ˇretˇezen´ı - konˇc´ı nesplnˇen´ım ˇz´adn´e ze situac´ı.
http://ida.felk.cvut.cz/moodle/
ˇ pCinnost produkˇ cn´ıho syst´ emu
Prob´ıh´a obvykle v cyklu − rozpozn´an´ı situace ⇒ vykon´an´ı akce − souˇc´ast´ı jsou: instanciace promˇenn´ych pravidla, v´ybˇer jedin´eho pravidla, zmˇena obsahu pracovn´ı pamˇeti,
Strategie ˇreˇsen´ı konfliktu − preference pravidel s vˇetˇs´ım poˇctem podm´ınek na lev´e stranˇe, − z´akaz opakov´an´ı pravidla z pˇredchoz´ıho kroku (ochrana proti zacyklen´ı), − upˇrednostnˇen´ı novˇejˇs´ıch dat, uˇzit´ych k aktivaci pravidla,
Efektivita v re´aln´ych u´loh´ach? − nejv´ıce ˇcasu se obvykle spotˇrebuje na nalezen´ı podmnoˇziny instanc´ı pouˇziteln´ych pravidel, − to lze urychlit jej´ım zachov´an´ım i pro pˇr´ıˇst´ı kroky (mˇen´ı se mal´a ˇc´ast pracovn´ı pamˇei), − d´ale i kompilace pravidel do efektivnˇejˇs´ı reprezentace, nebo jejich struktury (stromy), − reference mezi pravidly a daty - testujeme pouze nadˇejn´a pravidla.
http://ida.felk.cvut.cz/moodle/
pProdukˇ cn´ı syst´ em pro wumpus˚ uv svˇ et % environment - example rule generate_stench(S) if agent(S) and wumpus(W) and call(adjacent(W,S)) then knows_stench(S).
% working memory gold((2,4)) and wumpus((1,3)) and pit((3,1)) and pit((3,3)) and pit((4,4)) and
% agent reasoning - example rule no_pit(N) if agent(A) and not knows_breeze(A) and call(adjacent(A,N)) then knows_no_pit(N)
knows_no_wumpus((1,1)) and knows_no_pit((1,1)) and knows_ok((1,1)) and agent((1,1))
http://ida.felk.cvut.cz/moodle/
pProdukˇ cn´ı syst´ emy - souvislosti
Formalismus prohled´av´an´ı stavov´eho prostoru, − stav je uloˇzen v pamˇeti, situace definuje stav (jejich mnoˇzinu), akce realizuje zmˇenu stavu, − pˇrirozen´y model lidsk´eho ˇreˇsen´ı probl´em˚ u,
Logick´e syst´emy reprezentace lze ch´apat i jako speci´aln´ı tvar produkˇcn´ıch syst´em˚ u − logick´a pravidla jsou speci´aln´ım pˇr´ıpadem produkˇcn´ıch pravidel, − pˇri omezen´ı na Hornovy klauzule lze usuzovat pˇr´ım´ym ˇretˇezen´ım,
Analogie s ˇcinnost´ı mozku − pravidla . . . dlouhodob´a pamˇeˇt, − b´aze dat . . . kr´atkodob´a operativn´ı pamˇeˇt, − inference . . . kognitivn´ı funkce,
Souvislost s procedur´aln´ım programem − tak´e vykon´av´a instrukce nad daty, − ale siln´a modularita - neuspoˇr´adan´a mnoˇzina pravidel vs posloupnost instrukc´ı, − interakce mezi pravidly je velmi omezen´a (pˇres obsah pamˇeti).
http://ida.felk.cvut.cz/moodle/
pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (1)
HTML reprezentace – lidsky srozumiteln´a ale nevhodn´a pro automatick´e zpracov´an´ı − vyhled´av´an´ı zaloˇzen´e na kl´ıˇcov´ych slovech m´a omezen´e moˇznosti ∗ nedostateˇcn´a u´plnost (recall) ˇci naopak pˇresnost (precision) ∗ citlivost na zmˇenu kl´ıˇcov´ych slov (napˇr. z´amˇena synonym) ∗ v´ysledkem vyhled´av´an´ı jsou jednotliv´e str´anky ˇci dokumenty – integrace je na ˇclovˇeku ∗ v d˚ usledku nejde o automatick´e z´ısk´av´an´ı informac´ı, ale zjiˇsˇtov´an´ı jejich um´ıstˇen´ı − podobn´a omezen´ı pˇri jin´ych ˇcast´ych u´konech ∗ u´drˇzba obsahu str´anek – zastar´av´an´ı, nekonzistence apod. ∗ z´ısk´av´an´ı znalost´ı – nelze dolov´an´ı dat jako u datab´az´ı (r˚ uznorodost, rozpt´ylenost) ∗ porovn´av´an´ı obsahu – porovnej vˇsechny v´yrobky dan´eho typu (ne ale v jednom katalogu, ale u r˚ uzn´ych prodejc˚ u, v r˚ uzn´ych zem´ıch, v r˚ uzn´ych mˇen´ach, apod.)
http://ida.felk.cvut.cz/moodle/
pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (2)
S´emantick´y web − je rozˇs´ıˇren´ım souˇcasn´eho webu – informace maj´ı pˇridˇelen dobˇre definovan´y v´yznam, − dovoluje vyˇsˇs´ı m´ıru automatizovan´eho (strojov´eho) zpracov´an´ı, − vyuˇzit´ı SW agent˚ u – autonomn´ıch a pˇredch´azej´ıc´ıch poˇzadavky uˇzivatele.
http://ida.felk.cvut.cz/moodle/
pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (3)
Pouˇzit´e prvky a technologie − konceptualizace dat na www ve formˇe ontologi´ı, − standardizovan´y popis www zdroj˚ u, − XML – z´apis strukturovan´ych metadat – dat o datech, − RDF (Resource Description Framework) – vyj´adˇren´ı vztah˚ u mezi metadatov´ymi prvky – syntaktick´y z´apis v XML, identifik´atory URI (Universal Resource Identifier) pro pojmenov´av´an´ı, − RDF Schema (Resource Description Framework) – jazyk pro popis ontologie – vyj´adˇren´ı s´emantiky popisovan´ych dat.
Antoniou, van Harmelen: A Semantic Web Primer, MIT Press, 2004
http://ida.felk.cvut.cz/moodle/
pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (4) – pˇr´ıklad
. Pˇrechod od HTML k ontologick´e konceptualizaci
http://ida.felk.cvut.cz/moodle/
pShrnut´ı
Je obt´ıˇznˇejˇs´ı tvoˇrit a spravovat znalost´ı o promˇenliv´em svˇetˇe.
http://ida.felk.cvut.cz/moodle/
pDoporuˇ cen´ e doplˇ nky – zdroje pˇredn´ aˇsky ˇ :: Cetba
Russel, Norvig: AI: A Modern Approach, Logical Agents, chapter 7 − reprezentace z pohledu inteligentn´ıho agenta, − dostupn´a v pdf – http://aima.cs.berkeley.edu/newchap07.pdf.
Maˇr´ık a kol. Umˇ el´ a inteligence 1 − kapitola Reprezentace znalost´ı: z´akladn´ı form´aty, logika, s´emantick´e s´ıtˇe, r´amce, ˇ sen´ı u´loh a dokazov´an´ı vˇet: predik´atov´a logika a d˚ − kapitola Reˇ ukazn´ı prostˇredky.
Maˇr´ık a kol. Umˇ el´ a inteligence 2 − kapitola Znalostn´ı inˇzen´yrstv´ı: praktick´a, znalostn´ı syst´emy v konkr´etn´ıch aplikac´ıch.
http://ida.felk.cvut.cz/moodle/
