Reprezentace znalost´ı
Vladim´ır Maˇr´ık Katedra kybernetiky, ˇ CVUT v Praze
http://cyber.felk.cvut.cz/
pReprezentace znalost´ı
V pamˇeti poˇc´ıtaˇce
poˇzadavky na modularitu (M) × asociativnost (A)
ˇ ri z´akladn´ı formalizmy: Ctyˇ A) Produkˇcn´ı syst´emy (M) B) Logika (predik´atov´a 1.ˇr´adu) (M) C) S´emanitck´e s´ıtˇe (A) D) R´amce a sc´en´aˇre (A)
ˇ Katedra kyberentiky, CVUT v Praze
pA) Produkˇ cn´ı syst´ emy
Soubor produkˇ cn´ıch pravidel typu situace → akce − situaˇcn´ı ˇc´ast pravidla popisuje podm´ınku, za n´ıˇz m˚ uˇze b´yt pravidlo pouˇzito
B´ aze dat (pracovn´ı pamˇ eˇt): − obsahuje jak poˇc´ateˇcn´ı data, tak i data odvozen´a − popisuje okamˇzit´y stav ˇreˇsen´e u´lohy
Inferenˇ cn´ı stroj − porovn´av´a data v pracovn´ı pamˇeti s podm´ınkov´ymi ˇc´astmi produkˇcn´ıch pravidel − vyb´ır´a pravidla vhodn´a k vykon´an´ı (nutnost ˇreˇsen´ı konfliktu) − prov´ad´ı pˇr´ısluˇsnou akci
ˇ Katedra kyberentiky, CVUT v Praze
ˇ pCinnost produkˇ cn´ıho syst´ emu
Prob´ıh´a obvykle v cyklu rozpozn´an´ı situace → vykon´an´ı akce“ ” Maj´ı-li pravidla parametry, pˇriˇrad´ı se jim konkr´etn´ı hodnoty → instance pravidel Ze souboru aplikovateln´ych instanc´ı pravidel je v kaˇzd´em kroku vybr´ano jedin´e ˇreˇsen´ı (ˇreˇsen´ı konfliktu) a provede jeho akˇcn´ı ˇc´ast
Vykon´an´ım pravidla se modifikuje obsah pracovn´ı pamˇeti
Cyklus zaˇc´ın´a znovu
POZOR! Souvislosti: 1. Produkˇcn´ı syst´em jako formalismus prohled´av´an´ı stavov´eho prostoru (dopˇredn´e i zpˇetn´e ˇretˇezen´ı) 2. Analogie s ˇcinnost´ı mozku: Soubor produkˇcn´ıch pravidel . . . . . . . . . . . . dlouhodob´a pamˇeˇt Pracovn´ı pamˇeˇt . . . . . . . . . . . . . . . . . . . . . . . . kr´atkodob´a operativn´ı pamˇeˇt Inferenˇcn´ı stroj . . . . . . . . . . . . . . . . . . . . . . . . . kognitivn´ı procesor lidsk´eho mozku
ˇ Katedra kyberentiky, CVUT v Praze
ˇ pCinnost produkˇ cn´ıho syst´ emu
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´ı)
Preference novˇejˇs´ıch dat, uˇzit´ych k aktivaci pravidla
Vlastnosti produkˇ cn´ıch syst´ em˚ u:
Omezen´a moˇznost interakce mezi pravidly
Omezen´ı kladen´a na tvar pravidel
Pravidla pˇredstavuj´ı element´arn´ı akce → moˇznost vysvˇetlov´an´ı
Modularita
ˇ Katedra kyberentiky, CVUT v Praze
pB) Logika (predik´ atov´ a 1.ˇr´ adu)
op´ır´a se o mnoˇzinu konstant, promˇenn´ych, funkˇcn´ıch symbol˚ u, predik´atov´ych symbol˚ u a kvantifik´ator˚ u funkˇcn´ı a predik´atov´e symboly maj´ı tzv. ˇ cetnost (poˇcet argument˚ u)
Z´ akladn´ı pojmy
Dvojargumentov´e predik´aty ISA ( Kol´ın“, A320). ” ISA ( Paris“, B777). ” M´a-tvar (bal´on, elipsovit´y). AKO (B777, tryskov´e letadlo).
Reprezentuj´ı fakta
ˇ Katedra kyberentiky, CVUT v Praze
pB) Logika (predik´ atov´ a 1.ˇr´ adu)
Predik´atov´e v´yrazy y Barva (ˇcerven´a) – jednoargumentov´ Otec (Martin, Zuzana) – dvojargumentov´ y Matka (Anna, Zuzana) – dvojargumentov´ y Rodiˇce (Martin, Anna, Zuzana) – trojargumentov´ y
Nab´yvaj´ı hodnot pravda“ (T) ˇci nepravda“ (F) ” ” Formule/klauzule Procedur´alnˇe: p1 ∧ p2 ∧ . . . ∧ pn ⇒ p(v Prologu p :- p1, p2, . . . , pn) Deklarativnˇe: p1 ∨ p2 ∨ . . . pn ∨ p
ˇ Katedra kyberentiky, CVUT v Praze
pB) Logika (predik´ atov´ a 1.ˇr´ adu) Pˇr´ıklad: Fakta: (1) Rodiˇc (Anna, Marie). (2) Rodiˇc (Anna, Zuzana). (3) Rodiˇc (Marie, Robert). (4) Rodiˇc (Zuzana, Jan). Pravidla: (5) Rodiˇc (X,Y) :- Otec (X,Y) (6) Rodiˇc (X,Y) :- Matka (X,Y) (7) Prarodiˇc (X,Y) :- Rodiˇc (X,Z), Rodiˇc (Z,Y) (8) Pˇredek (X,Y) :- Rodiˇc (X,Y) (9) Pˇredek (X,Y) :- Pˇredek (X,Z), Pˇredek (Z,Y) Chceme dok´ azat (c´ıl): :- Pˇredek (Anna, Jan)
ˇ Katedra kyberentiky, CVUT v Praze
pB) Logika (predik´ atov´ a 1.ˇr´ adu) Postup ˇreˇsen´ı: (1) X. . .Anna, Y. . .Jan Podc´ıl: Rodiˇc (Anna, Jan) – nen´ı splnˇen (2) podc´ıle: Pˇredek (Anna, Z), pˇredek (Z, Jan) (3) Zkoum´ame podc´ıl Pˇredek (Anna, Z), platn´e moˇznosti: Rodiˇc (Anna, Marie), Rodiˇc (Anna, Zuzana) (4) Zkoum´ame, zda pˇri Z=Marie m˚ uˇze platit Pˇredek (Z, Jan) → zjiˇstˇeno, ˇze neplat´ı Rodiˇc (Z, Jan) . . . nast´av´a bactracking (5) Zkoum´ame, zda pˇri Z=Zuzana m˚ uˇze platit Pˇredek (Z, Jan), zjiˇsˇtujeme, ˇze Rodiˇc (Zuzana, Jan) plat´ı, a tedy s uˇzit´ım pravidla (8) plat´ı: Pˇredek (Zuzana, Jan) (6) Obdobnˇe z Rodiˇc (Anna, Zuzana) plyne platnost Pˇredek (Anna, Zuzana) (7) S uˇzit´ım pravidla (9) pak dok´aˇzeme: Pˇredek (Anna, Jan)
ˇ Katedra kyberentiky, CVUT v Praze
pB) Logika (predik´ atov´ a 1.ˇr´ adu) POZOR! Souvislosti: 1. Pravidla JPL 1. ˇr´adu – speci´aln´ı tvar produkˇcn´ıch pravidel Fakta – data v pracovn´ı pamˇeti Inferenˇcn´ı stroj – realizuje strategii (prohled´av´an´ı stavov´eho prostoru) JPL 1. ˇr´adu = speci´aln´ı pˇr´ıpad produkˇcn´ıho syst´emu 2. A jeˇstˇe nˇeco nav´ıc: Data i pravidla mohou m´ıt stejn´y form´at – liˇs´ı se jen interpretac´ı (deklarativn´ı u dat, procedur´aln´ı u pravidel) 3. Jazyk PROLOG: Obsahuje syst´em automatizovan´ eho dokazov´ an´ı platnosti/neplatnosti formule v dan´em syst´emu axiom˚ u (teorii) – m´a zabudovanou jednoduchou strategii inferenˇcn´ıho stroje, op´ır´a se o systematickou transformaci formul´ı do standardn´ıho tvaru (napˇr. skolemizac´ı se zbav´ıme obecn´ych kvantifik´ator˚ u) a o tzv. rezoluˇ cn´ı princip (d˚ ukaz neplatnosti negace je postaˇcuj´ıc´ı v u´pln´em logick´em syst´emu)
ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
p˚ uvodnˇe mˇely reprezentovat pamˇeˇt ˇclovˇeka a podporovat porozumˇen´ı pˇrirozen´emu jazyku (Quillian, 1968) grafick´a reprezentace: − orientovan´y oznaˇcen´y graf ∗ uzly – entity (objekty, koncepty, situace) ∗ hrany – relace
ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
Obr. 1
ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
nejbˇeˇznˇeji uˇz´ıvan´e relace: − ISA – instance tˇr´ıdy − AKO – podtˇr´ıda (uˇz´ıv´a se mezi dvˇema generick´ymi uzly)
ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
Obr. 2 ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
POZOR: tˇr´ıda × mnoˇzina Nadtˇr´ıda ↓ Tˇr´ıda ↓ Podtˇr´ıda
Objekty jedn´e tˇr´ıdy maj´ı alespoˇn jeden spoleˇcn´y atribut (znak). Kaˇzd´y atribut m´a hodnotu, kombinace atributu a hodnoty je vlastnost. ˇ EN ˇ ´I Velmi d˚ uleˇzit´a vlastnost: DED Vˇsichni ˇclenov´e tˇr´ıdy dˇed´ı vˇsechny vlastnosti sv´ych nadtˇr´ıd → nen´ı tˇreba tyto charakteristiky opakovat V´ yjimky z procesu dˇ edˇ en´ı se ˇreˇs´ı uveden´ım v´yjimeˇcn´e vlastnosti na niˇzˇs´ı u´rovni (ta m´a preferenci) - viz tvar bal´onu a tvar bal´onu pro d´alkov´e lety (obr. 2) Taxonomick´ e struktury: ˇcistˇe hierarchick´e s´emantick´e s´ıtˇe umoˇznˇuj´ıc´ı kategorizaci jev˚ u, koncept˚ u, situac´ı atd.
ˇ Katedra kyberentiky, CVUT v Praze
pC) S´ emantick´ e s´ıtˇ e
POZOR! Souvislosti: mezi s´emantick´ymi s´ıtˇemi a JPL 1. ˇr´adu a JPL 1. ˇr´adu: :: kaˇzdou hranu s´emantick´e s´ıtˇe moˇzno ch´apat jako instanci dvojargumentov´eho predik´atu :: trojargumetov´e predik´aty nelze pˇr´ımo reprezentovat s.s., napˇred nutno dekomponovat na dvojargumentov´e predik´aty :: v oblasti s.s. existuje jedin´y typ inference – dˇedˇen´ı :: celkovˇe je s.s. podstatnˇe v´ yrazovˇ e chudˇs´ı neˇ z JPL 1. ˇr´ adu – ale vhodn´a pro praktick´e uˇzit´ı d´ıky jasn´e asociativitˇ e mezi prvky
ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre
n´astroje pro reprezentaci stereotypn´ıch situac´ı (Minsky, 1975)
pˇrirozen´a sekvence r´amc˚ u – sc´ en´ aˇr (Schenk, 1977) (povinn´ e) Jm´ eno r´ amce: (povinn´ e) Ukazatel na nadˇrazen´ y r´ amec: Jm´eno poloˇzky 1: hodnota Jm´eno poloˇzky 2: hodnota
Jm´eno poloˇzky n: hodnota
Obr. 3 – struktura r´amce
ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre
Jm´eno: Osobn´ı automobil stˇredn´ı tˇr´ıdy Nadˇrazen´y r´amec: osobn´ı automobil Airbagy: 4 a v´ıce ABS: Ano Klimatizace: automatick´a
Obr. 4 – generick´y r´amec ˇ Jm´eno: Skoda Okt´avia Speci´al Nadˇrazen´y r´amec: os. aut. stˇredn´ı tˇr´ıdy Motor: ˇctyˇrdob´y benz´ınov´y Pˇrevodovka: manu´aln´ı Typ: sedan ˇctyˇrdveˇrov´y Sedadla: k˚ uˇze
Obr. 5 – generick´y r´amec niˇzˇs´ı u´rovnˇe ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre
Jm´eno: Moje okt´avka ˇ Nadˇrazen´y r´amec: Skoda Okt´avia Speci´al Barva: ˇcern´a SPZ: 1A6 2222 Barva k˚ uˇze: b´eˇzov´a Sedadla: k˚ uˇze Volant: sportovn´ı Taˇzn´e zaˇr´ızen´ı: Mikov
Obr. 6 – Instance r´amce
ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre
Obr. 7 – Sloˇzitˇejˇs´ı r´amcov´a struktura
ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre N´aplnˇe poloˇzek mohou b´yt t´eˇz:
pˇredpokl´adan´a hodnota“ ” {seznam moˇzn´ych hodnot}
ot´azky uˇzivateli
obr´azky
odkazy na jin´e r´amce
v´ypoˇcetn´ı algoritmy
...
ˇ Jm´eno: Skoda Okt´avia Speci´al Nadˇrazen´y r´amec: Stˇredn´ı tˇr´ıda Pˇrevodovka: {manu´al, automat} Mlhovky: ano“ ” Typ taˇzn´eho zaˇr´ızen´ı: viz r´amec M˚ uj voz´ık“ ” Spotˇreba ve mˇestˇe: spotˇreba standard viz r´amec spotˇreba“ × 1.3 ”
Obr. 8 – Sloˇzitˇejˇs´ı r´amec ˇ Katedra kyberentiky, CVUT v Praze
pD) R´ amce a sc´ en´ aˇre POZOR! Souvislosti:
kaˇzd´y (jednoduch´y) r´amec lze reprezentovat s´emantickou s´ıt´ı, napˇr. r´amec moje okt´avka“ je ” v jednoduch´e s´emantick´e s´ıti zachycen na obr. 9 lze pouˇz´ıvat princip dˇedˇen´ı, resp. v´yjimky z dˇedˇen´ı . . .
Obr. 9 ˇ Katedra kyberentiky, CVUT v Praze
