Znalosti a jejich reprezentace, základní postupy, výroková logika. Katedra kybernetiky, FEL, ČVUT v Praze

Znalosti a jejich reprezentace, z´ akladn´ı postupy, v´ yrokov´ a logika Jiˇr´ı Kl´ ema Katedra kybernetiky, ˇ FEL, CVUT v Praze

http://cw.felk.cvut.cz/doku.php/courses/a7b33sui/start

pCel´ aˇ c´ısla – motivaˇ cn´ı pˇr´ıklad 1 :: Srovnejme dvˇe odliˇsné reprezentace ˇc´ısel – arabskou a ˇr´ımskou:

Délka zápisu − 1000 vs. M, 1997 vs. MCMXCVII, 100000 vs. MMMM...M, − pr˚ umˇerná délka (PD) zápisu, − doplnˇená o odhad redundance (R), protoˇze jeden kód pracuje s 10 symboly a druhý pouze se 7 ˇ ımská Soustava Arabská R´ Interval PD[znak˚ u] R[%] PD[znak˚ u] R[%] 1..1000 2.89 0.3 6 11.5 1..3000 3.63 2.6 7 5.5

Sloˇzitost aritmetických operac´ı, pˇr. sˇc´ıtán´ı a dˇelen´ı − arabská ˇc´ısla jsou poziˇcn´ı (operace pod sebou), existuje symbol pro 0, − u ˇr´ımských ˇc´ısel je aritmetika obt´ıˇznˇejˇs´ı (problémy s notac´ı IV → IIII, nutnost expanze L → XXXXX, apod.).

:: Závˇer: reprezentace významnˇe spoluurˇcuje zp˚ usob, efektivitu a srozumitelnost nakládán´ı s ˇc´ısly.

http://cw.felk.cvut.cz

pWumpus˚ uv svˇ et – motivaˇ cn´ı pˇr´ıklad 2

:: Hunt the Wumpus byla jednou z prvn´ıch poˇc´ıtaˇcových her. Wumpus je záhadnou pˇr´ıˇserou ˇc´ıhaj´ıc´ı v systému jeskyn´ı. Definice prostˇred´ı je:

Hodnocen´ı: zlato +1000, smrt -1000 (wumpus i ˇsachta), -1 za krok, -10 za pouˇzit´ı ˇs´ıpu Prostˇred´ı: jeskynˇe soused´ıc´ı s wumpusem smrd´ı, jeskynˇe vedle ˇsachty jsou vˇetrné, jeskynˇe se zlatem se tˇrpyt´ı, Senzory: náraz (pro krok do vnˇejˇs´ı zdi), zápach, vánek a tˇrpyt (pouze lokálnˇe v dané jeskyni), výkˇrik (slyˇsitelný kdekoli v bludiˇsti), Akce: otoˇc se vlevo, otoˇc se vpravo, jdi vpˇred, uchop (sebere zlato, hráˇc mus´ı být v jeskyni se zlatem), poloˇz (zlato), vystˇrel (ˇs´ıp zabije wumpuse pokud hráˇc stoj´ı ˇcelem k nˇemu – hráˇc má jediný ˇs´ıp).

c

Russel, Norvig: Artificial Intelligence: A Modern Approach.

:: C´ılem je volit akce tak, aby maximalizovaly bodový zisk hráˇce. Ten zaˇc´ıná i konˇc´ı na poli [1,1].


pWumpus˚ uv svˇ et – intencion´ aln´ı a reaktivn´ı agent :: Charakteristika u´lohy:

deterministická (výstupy jsou pˇresnˇe dány), statická (wumpus ani ˇsachty se nepohybuj´ı), sekvenˇcnˇe-diskrétn´ı (jednotkou je krok), prostˇred´ı nen´ı plnˇe pozorovatelné (lokáln´ı senzory), uvaˇzujme prostˇred´ı 4x4 s jediným wumpusem i pokladem a pst´ı ˇsachty v kaˇzdém poli 0.2 (startovac´ı pole je vˇzdy prázdné).

ˇ :: Sance intencionáln´ıho∗ (IA) a reaktivn´ıho∗∗ agenta (RA):

vˇetˇsina zadán´ı je neˇreˇsitelná (zlato je v ˇsachtˇe, je ˇsachtami obkl´ıˇceno, agent se nem˚ uˇze bezpeˇcnˇe pohnout apod.), IA ve 30% pˇr´ıpad˚ u najde bezpeˇcnˇe zlato a donese je zpˇet na start, ve zbytku pˇr´ıpad˚ u mus´ı riskovat nebo se vrátit bez zlata, RA bezpeˇcnˇe uspˇeje pouze ve 20% pˇr´ıpad˚ u, provede mnohem v´ıce akc´ı.

:: Závˇer: vnitˇrn´ı reprezentace svˇeta a schopnost základn´ı inference jsou nutnými podm´ınkami ˇ sen´ı IA viz. dále. u´spˇeˇsného agenta/hráˇce. Reˇ ∗

Intencion´ aln´ı agent pracuje s vnitˇrn´ım modelem svˇeta (tj. pamˇet´ı), vyuˇz´ıvá znalostn´ı bázi a inferenci.

∗

Reaktivn´ı agent nemá vnitˇrn´ı reprezentaci ani model svˇeta, ˇr´ıd´ı se pouze aktualn´ım stavem senzor˚ u.


pVe wumpusovˇ e svˇ etˇ e (1) :: Reaktivn´ı agent:

if Tˇrpyt=ano then Akce=uchop,

if Náraz=ano then Akce=rand(otoˇc se vpravo, otoˇc se vlevo),

if Zápach=ano or Vánek=ano then Akce=[otoˇc se vlevo, otoˇc se vlevo, jdi vpˇred, rand(otoˇc se vpravo, otoˇc se vlevo, jdi vpˇred)].

:: Pr˚ uchod svˇetem:

RA – vyhodnocen´ı 1

IA – inference 1







RA – krok 1

IA – krok 1








IA – inference 2







RA – krok 2

IA – kroky 2 a 3








IA – inference 3







RA – krok 3

IA – krok 4








IA – inference 4







RA – krok 4

IA – krok 5


pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3

:: Pokud vám ˇreknu, ˇze:

(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.

(S2) Pouze ptáci a savci jsou teplokrevn´ı.

(S3) Zuzana, m˚ uj pásovec, je teplokrevná a nemá peˇr´ı.

(S4) Kaˇzdý pták má peˇr´ı.

:: a zeptám se: (D) Klade Zuzana vejce?


pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3

:: Pokud vám ˇreknu, ˇze:

(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.

(S2) Pouze ptáci a savci jsou teplokrevn´ı.

(S3) Zuzana, m˚ uj pásovec, je teplokrevná a nemá peˇr´ı.

(S4) Kaˇzdý pták má peˇr´ı.

:: a zeptám se: (D) Klade Zuzana vejce? :: Inference v pˇrirozeném jazyce:

Zuzana nemá peˇr´ı a proto nen´ı pták.

Zuzana je teplokrevná a nen´ı pták, proto mus´ı být savec.

Zuzana je savec a pásovec, protoˇze nen´ı jeˇzura ani ptakopysk nem˚ uˇze klást vejce.

:: Jak realizovat strojovˇe? Reprezentace pomoc´ı ˇretˇezc˚ u je problematická z hlediska odvozován´ı nových tvrzen´ı ...


pIBM Watson – motivaˇ cn´ı pˇr´ıklad 4 :: Systém pro zodpov´ıdán´ı otázek kladených v pˇrirozeném jazyce

ve vˇedomostn´ı soutˇeˇzi Jeopardy (Riskuj) v roce 2011 porazil dva historicky nejúspˇeˇsnˇejˇs´ı lidi,

m´ısto otázek slovn´ı rébusy, soutˇeˇz´ıc´ı formuluje otázku definovanou pˇredloˇzeným textem,

integruje techniky zpracován´ı pˇrirozeného jazyka, vyhledáván´ı informac´ı, reprezentace znalost´ı a strojového uˇcen´ı.

:: Zˇrejmˇe obt´ıˇznˇejˇs´ı problém neˇz u DeepBlue (ˇsachový systém, také IBM)

ˇreˇsen´ı otázek v pˇrirozeném jazyce nen´ı ohraniˇcený problém.

:: Z pohledu reprezentace znalost´ı

heuristický pˇr´ıstup odliˇsný od “klasického” logického s formáln´ım dokazován´ım,

pokryt´ı a rychlost na u´kor pˇresnosti,

nejde ale o prosté statistické vyhledáván´ı informac´ı bez strukturované reprezentace (tomu chyb´ı pˇresnost uˇz pˇr´ıliˇs),

hybridn´ı pˇr´ıstup: nestrukturovaný text, ale i relace a strukturovaná a polo-strukturovaná znalost mj. ze sémantického webu.


pIBM Watson – motivaˇ cn´ı pˇr´ıklad 4

:: Pˇr´ıklady rébus˚ u a výsledných otázek

rébus literárn´ı postavy: Pokrývka hlavy toho, kdo oslovuje pˇr´ıtele slovem milý.

otázka: Co nos´ı na hlavˇe Sherlock Holmes?

rébus americká mˇesta: Má nejvˇetˇs´ı letiˇstˇe pojmenované po hrdinovi 2. svˇetové války, druhé nejvˇetˇs´ı po bitvˇe 2. svˇetové války. otázka: Co je Chicago? (O’Harovo a Midway)

:: Dovednosti nutné k ˇreˇsen´ı rébusu

shopnost rozloˇzit rébus na podúkoly, (americké mˇesto, hrdinové, bitvy, letiˇstˇe),

m´ıt vˇsechny informace k dispozici,

sloˇzit d´ılˇc´ı odpovˇedi a sestavit otázku.


pZnalosti :: Obecný a ˇcasto pouˇz´ıvaný pojem

epistemologie (teorie poznán´ı) versus znalostn´ı inˇzenýrstv´ı,

r˚ uzné u´rovnˇe abstrakce: data, informace, znalosti.

:: Zp˚ usoby chápán´ı znalosti

pro osobu - odbornost a dovednosti z´ıskané uˇcen´ım nebo ze zkuˇsenosti, − Petr v´ı, ˇze Tereza pˇrijde na sch˚ uzku. (vztah mezi osobou a popisným tvrzen´ım) − Petr vˇeˇr´ı, ˇze Tereza pˇrijde na sch˚ uzku. (existuj´ı r˚ uzné druhy vztah˚ u ...) − Petr um´ı hrát na piano. Petr zná Terezu. (explicitn´ı popisné tvrzen´ı chyb´ı)

pro obor - veˇskerá známá fakta a informace,

spolehlivé porozumˇen´ı vˇeci se schopnost´ı ji vhodnˇe pouˇz´ıvat.

:: Jaké kognitivn´ı schopnosti jsou obvykle tˇreba k z´ıskán´ı znalost´ı

vn´ımán´ı, uˇcen´ı, komunikace, asociace, uvaˇzován´ı.

:: Dále se pod´ıváme na souvisej´ıc´ı kl´ıˇcové pojmy: reprezentaci (bl´ıˇze) a usuzován´ı (ménˇe).


pReprezentace znalost´ı

:: Co to je? Jakou m˚ uˇze hrát roli?

náhraˇzka, umoˇznˇuje rozhodovat o následc´ıch uvaˇ zov´ an´ım bez prov´ adˇ en´ı skuteˇcných akc´ı − vnitˇrn´ı substituce vnˇejˇs´ıch objekt˚ u, u reálných objekt˚ u nutnˇe nedokonalá,

prostˇredek pro efektivn´ı výpoˇcetn´ı realizaci uvaˇzován´ı a myˇslen´ı

− mechanistický pohled – d˚ uraz na efektivitu inference jako výpoˇcetn´ıho procesu, odpovˇedˇ na otázku jakým zp˚ usobem bych mˇel uvaˇzovat o svˇetˇe − volba reprezentace spoluurˇcuje zp˚ usob myˇslen´ı, − nˇekteré inferenˇcn´ı postupy jsou snadné a jiné naopak,

prostˇredek lidského vyjádˇren´ı − jakou formou pˇredávat informace o svˇetˇe jiným lidem (nebo stroj˚ um).


pReprezentace znalost´ı – z´ akladn´ı sch´ ema

Jazyk pro reprezentaci znalost´ı mus´ı m´ıt jasnˇe danou syntaxi a s´ emantiku,

je nutné explicitnˇe znát význam vˇet jazyka v reálném svˇetˇe.


pJazyk pro reprezentaci znalost´ı – z´ akladn´ı vlastnosti

Pˇrirozenost − vˇety jazyka jsou intuitivnˇe srozumitelné, − srovnej pták(zuzana) a ydbk!op pro tvrzen´ı: Zuzana je pták.

Expresivita − poˇzadovanou ˇskálu objekt˚ u, jejich vlastnost´ı a vztah˚ u lze reprezentovat, − napˇr. výroková logika nen´ı dost expresivn´ı pro tvrzen´ı/problém: ∗ Kaˇzdý ˇclovˇek je smrtelný. Sokrates je ˇclovˇek. Je Sokrates smrtelný?

Vhodnost pro usuzován´ı − korektnost usuzován´ı – odvozené vˇety v reálném svˇetˇe vˇzdy plat´ı, − efektivita usuzován´ı – odvozen´ı s rozumnou ˇcasovou a pamˇeˇtovou sloˇzitost´ı, −u ´plnost usuzován´ı – lze odvodit vˇsechny vˇety, které vyplývaj´ı z aktuáln´ı báze znalost´ı, zpravidla v rozporu s poˇzadavky na efektivitu.

:: Pˇrirozený jazyk (ˇceˇstina) je pˇrirozený, expresivn´ı, ale zcela nevhodný pro automatické usuzován´ı. Mj. je nejednoznaˇcný (Prohnal si kul´ı hlavu.) a kontextovˇe závislý (Je to pˇekný párek.) :: Neexistuje univerzáln´ı jazyk, r˚ uzné jazyky jsou vhodné pro r˚ uzné problémy. Optimáln´ı je volba nejjednoduˇsˇs´ı dostateˇcnˇe expresivn´ı reprezentace pro daný problém.


pZnalosti – reprezentace a pouˇ zit´ı

Báze znalost´ı − mnoˇzina vˇet v jazyce pro reprezentaci znalost´ı, − data (znalosti) specifická pro daný problém, jak uˇzivatelská, tak i odvozená, − pracovn´ı pamˇeˇt – popisuje okamˇzitý stav ˇreˇseného problému.

Inferenˇcn´ı stroj − realizuje usuzován´ı – odvozován´ı nových znalost´ı, − problémovˇe nezávislý obsah (obecná odvozovac´ı pravidla, mechanismus ˇreˇsen´ı konflikt˚ u), − ˇr´ızen´ı báze znalost´ı.


pZnalostn´ı inˇ zen´ yrstv´ı

Vývoj a u´drˇzba znalostn´ıch systém˚ u − tj. poˇc´ıtaˇcových systém˚ u napodobuj´ıc´ıch lidské ˇreˇsen´ı problém˚ u zaloˇzených na znalostn´ı bázi a inferenˇcn´ım mechanismu.

Identifikace a konceptualizace problému − pˇrehled o pojmech a vztaz´ıch, − výsledkem je abstraktn´ı model – napˇr. ve formˇe znalostn´ı ontologie,

Formalizace znalost´ı a implementace systému − volba vhodné reprezentace znalost´ı a formalizace konceptuáln´ıho modelu, − datové typy, operaˇcn´ı systém, programové prostˇred´ı – ˇcasto standardn´ı,

Jak znalosti z´ıskat? − pˇrej´ımán´ı od expert˚ u × induktivn´ı odvozován´ı z dat, − data – ovˇeˇritelná elementárn´ı fakta, − znalosti – zobecnˇená tvrzen´ı, návody jak data interpretovat a vyuˇz´ıvat,

Testován´ı a u´drˇzba systému − konzultace výsledk˚ u s odborn´ıky – u´pravy a rozˇsiˇrován´ı báze i zmˇeny modelu, − aktualizace a opravy znalostn´ı báze – mj. problém konzistence.


pZnalostn´ı inˇ zen´ yrstv´ı vs klasick´ e programov´ an´ı

Jaká je analogie mezi obˇema typy ˇcinnost´ı? − lze je rozloˇzit na 4 odpov´ıdaj´ıc´ı si kroky

Programov´ an´ı Znalostn´ı inˇ zen´ yrstv´ı Volba jazyka reprezentace Volba programovac´ıho jazyka Tvorba báze znalost´ı Psan´ı programu Volba (implementace) inferenˇcn´ıho mechanismu Volba (implementace) pˇrekladaˇce Odvozován´ı nových znalost´ı Spuˇstˇen´ı programu

Znalostn´ı inˇzenýrstv´ı vyuˇz´ıvá deklarativn´ı (popisný, konstatuj´ıc´ı) pˇr´ıstup − je ménˇe explicitn´ı – pouze objekty a platnost vztah˚ u mezi nimi, − pouˇzit´ı i v databázových systémech nebo deklarativn´ım programován´ı (Prolog – viz dále).


pJazyky pro reprezentaci znalost´ı – pˇr´ıstupy

Logická schémata − deklarativn´ı znalostn´ı báze ve formˇe logických tvrzen´ı, − poté klasická logická inference pro konkrétn´ı fakta reprezentuj´ıc´ı problém, − nejˇcastˇejˇs´ım formalismem je predikátová logika 1. ˇrádu, nástrojem pak jazyk PROLOG.

Proceduráln´ı schémata − znalostn´ı báze ve formˇe instrukc´ı, − typickým pˇr´ıkladem jsou pravidlové produkˇcn´ı systémy – pravidla typu if ... then ...

S´ıˇtové modely − znalost je uchována ve formˇe grafu, − objekty ˇci pojmy jsou uzly, vztahy mezi nimi reprezentuj´ı hrany, − pˇr´ıkladem jsou sémantické s´ıtˇe.

Strukturované modely − rozˇs´ıˇren´ı s´ıˇtových model˚ u, uzly grafu mohou být komplexn´ımi strukturami, − pˇr´ıkladem jsou skripty, rámce a objekty.


pLogika

Formáln´ı jazyk s jasnˇe definovanými: − syntax´ı – jak se sestav´ı korektn´ı vˇeta, − sémantikou – co tato vˇeta znamená v reálném svˇetˇe, − axiomy a odvozovac´ımi pravidly – nástroje pro usuzován´ı.

:: Nejjednoduˇsˇs´ı je v´ yrokov´ a logika

Syntaxe – elementy jazyka − neprázdná mnoˇzina symbol˚ u, kaˇzdý symbol je atomickou výrokovou formul´ı, − logické spojky ⇒ a ¬, − pro zkrácen´ı zápisu ˇcasto doplnˇené o ∧, ∨ a ⇔ (napˇr. A ∨ B pro ¬ A ⇒ B), − závorky ().

Syntaxe – definice korektn´ıch výrokových formul´ı − kaˇzdá atomická výroková formule je téˇz výroková formule, − jsou-li A a B výrokové formule, pak i (¬ A) a (A ⇒ B) jsou výrokové formule, − nic jiného výrokové formule nejsou.


pV´ yrokov´ a logika

Sémantika – význam symbol˚ u, spojek a formul´ı − symboly reprezentuj´ı elementárn´ı výroky o svˇetˇe, napˇr. P pro “Petr má rád ˇcokoládu.”, − kaˇzdý výrok m˚ uˇze být budˇ pravdivý (True) nebo nepravdivý (False), − pˇriˇrazen´ı pravdivostn´ı hodnoty vˇsem symbol˚ um nazýváme interpretac´ı, − interpretaci nazveme modelem formule, pokud je formule pro danou interpretaci pravdivá, − kaˇzdé spojce odpov´ıdá pravdivostn´ı tabulka, ta vyjadˇruje pravdivost sloˇzené formule na základˇe pravdivosti formul´ı atomických.

Axiomy – základn´ı pravdivá tvrzen´ı, nedokazuj´ı se − (A1) A ⇒ (B ⇒ A), − (A2) (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)), − (A3) (¬ B ⇒ ¬ A) ⇒ (A ⇒ B).

Odvozovac´ı pravidlo – pro vytváˇren´ı odvozených formul´ı a dokazován´ı pravdivosti − základn´ım je Modus Ponens: A, A ⇒ B |= B, − základn´ımi pro rozˇs´ıˇrenou mnoˇzinu spojek: vylouˇcen´ı tˇret´ıho |= A ∨ ¬A, zaveden´ı konjunkce A, B |= A ∧ B, zaveden´ı disjunkce: A |= A ∨ B, eliminace disjunkce ¬A, A ∨ B |= B, atd.


pLogick´ y d˚ usledek a logick´ e usuzov´ an´ı

Logický d˚ usledek − α |= β – vˇeta β je logick´ ym d˚ usledkem vˇety α, − α |= β iff vˇsechny modely vˇety α jsou také modelem vˇety β,

Logické usuzován´ı (inference) − KB ì α – α je odvoditeln´ a z KB (báze znalost´ı je také vˇetou!) pomoc´ı procedury i, − korektnost – i je korektn´ı pokud: KB ì α ⇒ KB |= α, −u ´plnost – i je u´plná pokud: KB |= α ⇒ KB ì α,


pV´ yrokov´ a logika – pˇr´ıklad :: Na ostrovˇe poctivc˚ u a padouch˚ u lidé budˇ mluv´ı vˇzdy pravdu – poctivci – nebo vˇzdy lˇzou – padouˇsi. Potkáme A a ten prohlás´ı: “Já jsem padouch, ale B ne.” Urˇcete povahu A a B. Pouˇzijte výrokovou logiku.


pV´ yrokov´ a logika – pˇr´ıklad :: Na ostrovˇe poctivc˚ u a padouch˚ u lidé budˇ mluv´ı vˇzdy pravdu – poctivci – nebo vˇzdy lˇzou – padouˇsi. Potkáme A a ten prohlás´ı: “Já jsem padouch, ale B ne.” Urˇcete povahu A a B. Pouˇzijte výrokovou logiku.

Formalizace u´lohy: − atomické výroky – a: “A je padouch.” b: “B je padouch.”, − (F1) a ⇒ ¬(a ∧ ¬b), − (F2) ¬a ⇒ a ∧ ¬b,

ˇ sen´ı pravdivostn´ı tabulkou (model checking) Reˇ − hledáme model(y) splˇnuj´ıc´ı souˇcasnˇe (F1) i (F2). a F F T T

b F T F T

¬a ¬b (a ∧ ¬b) T T F T F F F T T F F F

F1 F F T T

F2 T T F T


pV´ yrokov´ a logika – pˇr´ıklad (pokr.)

Deduktivn´ı d˚ ukaz – pouˇzit´ı libovolných odvozovac´ıch pravidel − (F1) a ⇒ ¬(a ∧ ¬b), − (F2) ¬a ⇒ a ∧ ¬b, − (F3) ¬a ∨ ¬(a ∧ ¬b) (pˇrevod implikace v (F1)), − (F4) ¬ ¬a ∨ (a ∧ ¬b) (pˇrevod implikace v (F2)), − (F5) ¬a ∨ ¬a ∨ b (de Morgan˚ uv zákon v (F3)), − (F6) (a ∨ a) ∧ (a ∨ ¬b) (zákon dvoj´ı negace a distribuce v (F4)), − (F7) ¬a ∨ b (idempotence (F5)), − (F8) a ∧ (a ∨ ¬b) (idempotence (F6)), − (F9) a (absorbce (F8)), − (F10) a ∧ b (absorbce negace (F7) ∧ (F9)), − (F11) b (eliminace konjunkce (F10)).


pV´ yrokov´ a logika – pˇr´ıklad (pokr.)

Axiomatický d˚ ukaz – pouze axiomy a modus ponens (MP) − (F1) a ⇒ ¬(a ∧ ¬b), − (F2) ¬a ⇒ a ∧ ¬b, − (F3) a ⇒ ¬a ∨ b ⇔ a ⇒ (a ⇒ b) (F1 pouze s implikacemi), − (F4) ¬a ⇒ ¬¬(a ∧ ¬b) ⇔ ¬a ⇒ ¬(a ⇒ b) (F2 pouze s implikacemi), − (A1) A ⇒ (B ⇒ A), − (A2) (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)), − (A3) (¬ B ⇒ ¬ A) ⇒ (A ⇒ B), − (F5) (a ⇒ (a ⇒ b)) ⇒ ((a ⇒ a) ⇒ (a ⇒ b)) (dosazen´ı do (A2) A/a, B/a, C/b), − (F6) (a ⇒ a) ⇒ (a ⇒ b) (MP (F3), (F5)), − (F7) (a ⇒ b) (MP (F6), (a ⇒ a), platnost druh´ eho bez d˚ ukazu – zkuste doma!), − (F8) (¬a ⇒ ¬(a ⇒ b)) ⇒ ((a ⇒ b) ⇒ b) (dosazen´ı do (A3) A/(a ⇒ b), B/a), − (F9) (a ⇒ b) ⇒ a (MP (F4), (F8)), − (F10) a (MP (F7), (F9)), − (F11) b (MP (F7), (F10)).


pRezoluce

ˇcasto potˇrebujeme u ´pln´ y mechanismus odvozován´ı,

deduktivn´ı aplikace pravidel? − volba axiomu, odvozovac´ıho pravidla ˇci tvrzen´ı závis´ı na intuici, − d˚ ukaz se obt´ıˇznˇe automatizuje – snaha o u´plnost vede ke kombinatorické explozi.

model checking? − korektn´ı a u´plné, ale O(2n), kde n je poˇcet symbol˚ u.

rezoluce je korektn´ı a v kombinaci s u´plným prohledávac´ım algoritmem u´plná (úplnost popˇren´ım – daný výrok potvrd´ı ˇci popˇre, negeneruje výˇcet platných tvrzen´ı!), pˇr´ıˇciny “efektivity”: − u´plná normáln´ı konjunktivn´ı forma – minimalizuje poˇcet pouˇzitelných pravidel ∗ literál – atomická formule nebo jej´ı negace, klauzule – disjunkce literál˚ u, ∗ rezoluˇcn´ı pravidlo: A ∨ ψ, ¬A ∨ φ |= ψ ∨ φ, ∗ z dvojice klauzul´ı odvod´ı jejich rezolventu, A a ¬A jsou doplˇnkové literály. − d˚ ukaz sporem – lepˇs´ı ˇr´ızen´ı pr˚ uchodu prohl. prostorem, orientuje se na c´ıle ∗ T |= φ iff T ∪ {¬φ} |= , ∗ spor odpov´ıdá prázdné klauzuli, znaˇcen´ı .


pRezoluce – pˇr´ıklad (pokr.)

Rezoluˇcn´ı d˚ ukaz – nejprve pˇrevod do klauzáln´ı formy − (F1) a ⇒ ¬(a ∧ ¬b), − (F2) ¬a ⇒ a ∧ ¬b, − (K1) ¬a ∨ b (úprava (F1), viz. deduktivn´ı d˚ ukaz), − (K2,3) a ∧ (a ∨ ¬b) (úprava (F2), viz. deduktivn´ı d˚ ukaz).

Rezoluˇcn´ı d˚ ukaz – doplnˇen´ı o negaci dokazovaného tvrzen´ı − (D1) a ∧ b, − (¬D1) ≡ (K4) ¬a ∨ ¬b.

∗

Strom rezoluˇcn´ıho zam´ıtnut´ı ∗

Nelze rezolvovat K1 a K3. Proˇc?


pRezoluce – strategie prohled´ av´ an´ı, sloˇ zitost

Jak vyb´ırat klauzule, které maj´ı být rezolvovány? − ˇr´ızeno strategi´ı prohledáván´ı, − tvoˇr´ı derivaˇcn´ı graf (DG) – listy jsou klauzule, uzly jsou rezolventy, − strom rezoluˇcn´ıho zam´ıtnut´ı – podgraf DG jehoˇz koˇrenem je .

´ e strategie Upln´ − prohledáván´ı do ˇs´ıˇrky ∗ nejprve vˇsechny rezolventy 1. ˇrádu (1 aplikace rezoluˇcn´ıho pravidla na výchoz´ı mnoˇzinu klauzul´ı), poté vˇsechny rezolventy 2. ˇrádu (alespoˇn 1 rodiˇc je 1. ˇrádu), atd., ∗ prázdná klauzule nalezena na nejniˇzˇs´ı moˇzné hladinˇe, moˇzná kombinatorická exploze, − podp˚ urná mnoˇzina ∗ teorie je bezesporná – spor m˚ uˇze vzniknout pouze z negace dokazovaného tvrzen´ı, ∗ pouze rezolventy maj´ıc´ı alespoˇn za 1 pˇredka (rodiˇce, prarodiˇce, . . . ) dokazované tvrzen´ı, ∗ poˇcet rezolvent kaˇzdého ˇrádu roste pomaleji. − lineárn´ı ∗ posledn´ı generovaná rezolventa je nejbliˇzˇs´ım rodiˇcem, ∗ opˇet omezuje poˇcet rezolvent.


pRezoluce – strategie prohled´ av´ an´ı, sloˇ zitost

Neúplné strategie − jednotková – alespoˇn jeden z rodiˇc˚ u je klauzule s jediným literálem, − vstupn´ı – alespoˇn jeden z rodiˇc˚ u je klauzule z výchoz´ı mnoˇziny, − filtraˇcn´ı – vstupn´ı strategie s pˇr´ıbuznost´ı – lze rezolvovat i klauzuli s jej´ım pˇredkem, − kombinované – napˇr. lineárnˇe-vstupn´ı, u´plnost pouze pro Hornovy klauzule (viz. dále).

Omezován´ı mnoˇziny rezolvent − odstranˇen´ı tautologi´ı (P ∨¬ P), − odstranˇen´ı specializac´ı (d˚ usledk˚ u) existuj´ıc´ı klauzule (P, P ∨¬ Q), − testován´ı pravdivosti literál˚ u (zejména v predikátové logice: vˇetˇs´ı(3,4)).

Sloˇzitost rezoluce − aˇckoli patˇr´ı do tˇr´ıdy exponenciáln´ıch algoritm˚ u, je v ˇradˇe pˇr´ıpad˚ u ”mnohem efektivnˇejˇs´ı” neˇz model checking, − efektivnˇe ˇreˇsit jdou zejména u´lohy s malým a velkým pomˇerem mezi klauzulemi a symboly, − alternativou pro výrokovou logiku je Davis-Putnam˚ uv algoritmus pro testován´ı splnitelnosti logické formule v CNF.


pPˇr´ım´ e a zpˇ etn´ e ˇretˇ ezen´ı

Omezen´ı na Hornovy klauzule s nejvýˇse jedn´ım pozitivn´ım literálem − (P ∨ ¬Q ∨ ¬R) ⇔ (Q ∧ R) ⇒ P , nelze zapsat napˇr. (¬P ∨ Q ∨ R) ⇔ P ⇒ (Q ∨ R), − tj. pouze jednoduchá fakta a implikace s jediným d˚ usledkem.

Odmˇenou je odvozován´ı v O(n), kde n je velikost báze znalost´ı (poˇcet klauzul´ı) − odvozovat lze pˇr´ımým ˇci zpˇetným ˇretˇezen´ım, oba postupy jsou korektn´ı a u´plné, − hlavnˇe sloˇzitost zpˇetného ˇretˇezen´ı je ˇcasto sublineárn´ı.

Pˇr´ımé ˇretˇezen´ı − udrˇzujeme agendu platných (a dosud nepouˇzitých) symbol˚ u, − u kaˇzdé implikace poˇc´ıtadlo nesplnˇených pˇredpoklad˚ u, − vybereme symbol z agendy, sn´ıˇz´ıme poˇc´ıtadla u pˇr´ısluˇsných implikac´ı, − pokud 0, rozˇs´ıˇr´ıme agendu o d˚ usledek implikace, − konˇc´ı vyˇcerpán´ım agendy nebo odvozen´ım dokazovaného tvrzen´ı, − ˇr´ızeno daty – postupuje od platných fakt˚ u ke splnˇen´ı c´ıle nebo vyˇcerpán´ı moˇzných operac´ı.

Zpˇetné ˇretˇezen´ı − najde pˇredpoklady platnosti dokazovaného tvrzen´ı a ty se postupnˇe snaˇz´ı ovˇeˇrit, − ˇr´ızeno c´ıli – postupuje od dokazovaného tvrzen´ı k jeho pˇredpoklad˚ um.


pPˇr´ım´ e a zpˇ etn´ e ˇretˇ ezen´ı – pˇr´ıklad :: dotaz: Q?

Báze znalost´ı a AND-OR graf


pV´ yrokov´ a logika ve wumpusovˇ e svˇ etˇ e

Zjednoduˇsený pˇr´ıklad − pouze ˇsachty, omezený poˇcet pozic, − KB vycház´ı z pozorován´ı svˇeta v pol´ıch [1,1] a [2,1] ∗ ¬B1,1 – bez vánku v poli [1,1], B2,1 – vánek v [2,1], ¬P1,1 – v [1,1] nen´ı ˇsachta, − KB obsahuje lokáln´ı odvozovac´ı pravidla ∗ B1,1 ⇔ (P1,2 ∨ P2,1), B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1), − c´ılem je zjistit výskyt ˇsachet v pol´ıch [1,2], [2,2] a [3,1].

Fragment svˇeta - 3 pole - 8 model˚ u

Praktická demonstrace usuzován´ı − model checking – vˇeta mus´ı m´ıt vˇsechny modely, které jsou modelem KB, − rezoluce – d˚ ukaz sporem.


pModel checking ve wumpusovˇ e svˇ etˇ e

α2 ≡ ¬P2,2, M(KB) * M(α2) ⇒KB 2 α2

α1 ≡ ¬P1,2, M(KB) ⊆ M(α1) ⇒ KB |= α1


pModel checking ve wumpusovˇ e svˇ etˇ e

α2 ≡ ¬P2,2, M(KB) * M(α2) ⇒KB 2 α2

α1 ≡ ¬P1,2, M(KB) ⊆ M(α1) ⇒ KB |= α1

B1,1 B2,1 P1,1 P1,2 P2,1 P2,2 P3,1 F F F F F F F ... ... ... ... ... ... ... F T F F F F T F T F F F T F F T F F F T T ... ... ... ... ... ... ... T T T T T T T

KB F ... T T T ... F

α1 T ... T T T ... F

α2 T ... T F F ... F


pRezoluce ve wumpusovˇ e svˇ etˇ e

Pˇrevod do klauzáln´ı formy − (F1-5) ¬B1,1, B1,2, ¬P1,1, B1,1 ⇔ (P1,2 ∨ P2,1), B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1), − (K1-3) ¬B1,1, B1,2, ¬P1,1, − (K5-7) ¬B1,1 ∨ P1,2 ∨ P2,1, ¬P1,2 ∨ B1,1, ¬P2,1 ∨ B1,1 (úpravou (F4)), − (K8-11) ¬B2,1 ∨ P1,1 ∨ P2,2 ∨ P3,1, ¬P1,1 ∨ B2,1, ¬P2,2 ∨ B2,1, ¬P3,1 ∨ B2,1 (úpravou (F5)).

Stromy rezoluˇcn´ıho zam´ıtnut´ı pro D1 ≡ ¬P1,2 a D2 ≡ ¬P2,2


pIntencion´ aln´ı agent ve wumpusovˇ e svˇ etˇ e function PL-wumpus-agent(senzory=[zápach,vánek,tˇrpyt]) returns akce if zápach then Vloˇz(KB,Sx,y ) else Vloˇz(KB,¬Sx,y ) % aktualizace KB if vánek then Vloˇz(KB,Bx,y ) else Vloˇz(KB,¬Bx,y ) % x,y urˇcuj´ı aktuáln´ı polohu if tˇrpyt then akce ← uchop else if plán <> {} then akce ← Vyber(plán) % plán je zásobn´ıkem neuskuteˇcnˇených akc´ı else repeat % hledej bezpeˇcné sousedn´ı pole Sousedn´ı-pole(x,y,i,j) % nejprve nenavˇst´ıvená, posléze navˇst´ıvená pole until Zjisti(¬Pi,j ∧ ¬Wi,j ) = True plán ← Vytvoˇr-plán(x,y,orientace,i,j) % posloupnost akc´ı k dosaˇzen´ı pole i,j akce ← Vyber(plán) % provedˇ prvn´ı akci z plánu Uprav(orientace, pozice (souˇradnice x,y),navˇst´ıvená pole, akce) % procedurálnˇe, mimo KB return akce


pShrnut´ı

Základn´ı východiska této pˇrednáˇsky − znalost lze reprezentovat ve formˇe r˚ uzných symbol˚ u ∗ symboly – obecné a potenciálnˇe sloˇzité datové struktury, ∗ objekty, koncepty, fakta, pravidla, strategie, − inteligentn´ıho chován´ı lze dosáhnout manipulac´ı se symboly, − jde o pˇredpoklady symbolické (tradiˇcn´ı) UI ∗ alternativou je konekcionismus – neuronové s´ıtˇe.

Inteligentn´ı systém pak vyˇzaduje − form´ aln´ı jazyk pro reprezentaci znalost´ı, − schopnost odvozovat nové znalosti/závˇery.

Neexistuje univerzáln´ı jazyk ani inferenˇcn´ı postup pouˇzitelný pro vˇsechny problémy.

Logika je velmi obecnou formáln´ı reprezentac´ı schopnou inference − rezoluce je postupem, který umoˇznˇuje korektn´ı a u´plné logické usuzován´ı.


pShrnut´ı

Výroková logika je jednoduchým jazykem − zaloˇzeným na výrokových symbolech a logických spojkách, − umoˇznˇuje pˇrehledné a rozumnˇe efektivn´ı ˇreˇsen´ı ˇrady problém˚ u, − pro jiné problémy nen´ı pouˇzitelná z d˚ uvodu ∗ efektivity zápisu – viz. prostorové vazby ve wumpusovˇe svˇetˇe NxN, ∗ koneˇcnosti mnoˇziny výrokových symbol˚ u – nemoˇznost zvládnout neohraniˇcené problémy, ∗ nedostateˇcné expresivity – viz. smrtelný Sokrates.

Pˇr´ıˇstˇe: predikátová logika a dalˇs´ı formy reprezentace.


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á v pdf – http://aima.cs.berkeley.edu/newchap07.pdf.

Maˇr´ık a kol. Umˇ el´ a inteligence 1 − kapitola Reprezentace znalost´ı: základn´ı formáty, logika, sémantické s´ıtˇe, rámce, ˇ sen´ı u´loh a dokazován´ı vˇet: predikátová logika a d˚ − kapitola Reˇ ukazn´ı prostˇredky.

Maˇr´ık a kol. Umˇ el´ a inteligence 2 − kapitola Znalostn´ı inˇzenýrstv´ı: praktická, znalostn´ı systémy v konkrétn´ıch aplikac´ıch.

Brachman, Levesque: Knowledge Representation and Reasoning − kniha, The Morgan Kaufmann Series in Artificial Intelligence.


Znalosti a jejich reprezentace, základní postupy, výroková logika. Katedra kybernetiky, FEL, ČVUT v Praze

Recommend Documents