ZNALOSTNÍ SYSTÉMY Doc. Ing. Ludk Müller, Ph.D

©2002 Lud k Müller

Strana 0

ZÁPADO ESKÁ UNIVERZITA V PLZNI FAKULTA APLIKOVANÝCH V D

ZNALOSTNÍ SYSTÉMY Doc. Ing. Lud k Müller, Ph.D.

ZSY


Strana 1

ZSY

1 EXPERTNÍ SYSTÉM ES = po íta ový program, který simuluje usuzování lidského experta (schopnost ízení) BD

BD – báze dat BZ – báze znalostí IM – informa ní mechanismus (usuzovací)

BZ IM

Srovnání ES a lov ka experta ES okamžitá všude ↑ (kopie,…) konstantní konstantní ↑ ↑

%

Dostupnost v ase Dostupnost v míst Bezpe nost Smrtelnost Výkonnost Rychlost Cena 45 40 35 30 25 20 15 10 5 0 Shell

0

lov k + prom nlivá prom nlivá ↑↑

10

LISP

PROLOG

20 %

OPS

30

ostaní

40

ízení Návrh Diagnostika Instruktáž Interpretace Monitorování Plánování P edpovídání P edpisování Výb r Simulace

%


Strana 2

ZSY

70 60 50 40 30 20 10 0 PC

Work station

Mini

Main frame

1.1 K EMU ES JSOU? -

náhrada experta – lov ka pomoc expertovi – lov ku

1.2 KDE JSOU ES NASAZOVÁNY? 1. obrázky nasazení v oborech 2. p íklady: Drilling Advisor – Rádce ropných vrt – Elf Aquitaine of France Cooker Advisor – Rádce ve steriliza ním procesu potravin R1/XCON – Konfigurace po íta DEC Lending Advisor – finan nictví - úv ry

2 CHARAKTERISTIKY ES 2.1 STRUKTURA ES IM = ást ES, která srovnává fakta z PP (pracovní pam ) se znalostmi v BZ za ú elem nalezení záv ru ešeného problému

BZ

VM

VM – vysv tlovací mechanismus I - interface

PP

IM

I

BZ = ást ES, která obsahuje oborové znalosti PP = BD = ást ES, která obsahuje konkrétní fakta (data) o dané ešené úloze a to jak vložená uživatelem (databáze), tak odvozená IM b hem práce ES


Strana 3

ZSY

Znalost, informace, data, šum metaznalosti znalosti informace data šum Metaznalost = znalost o znalostech P íklad: M jme posloupnost 26 íslic • 13907665847932520051564315 … šum • když budeme v d t, že posloupnost obsahuje údaje, pak se jedná o data … data • p edpokládejme, že existuje p edpis, jak tato data p evést na informaci … informace Nap .: 1. rozd líme posloupnost na: 13 90 76 … 15 2. vynecháme každé íslo menší než 32: 90 76 65 … 43 3. nahra zbývající ísla ASCII znaky: ZLATO 438 + → stoupá cena • Máme-li znalost IF ZLATO levn jší než 500 a cena stoupá THEN nakupuj ZLATO pak informaci m žeme využít. znalost = p edpis, jak nakládat s informacemi

2.2 CHARAKTERISTIKY ES 1. separace znalostí od ízení ( BZ x IM) 2. obsahuje expertní znalosti (BZ) 3. úzká oblast expertýzy ne p íliš hluboká oblast expertýzy musí existovat lov k, který danou úlohu umí ešit 4. usuzování se symboly P íklad: IF osoba má hore ku THEN osoba dostane aspirin Data: Jan má hore ku Hore ka (Jan) Hore ka(x) → Dát(x, aspirin) x = Jan → Dát (Jan, aspirin) 5. heuristické usuzování P íklad: Lidé jsou v lét málokdy nachlazeni. Je-li podez ení, že pacient má rakovinu, nejd íve se podívám na rodinnou anamnézu. 6. nep esné usuzování zdroje nep esnosti: - neur itost dat BD (PP) - neur itost znalostí BZ - neur itost p i práci IM IM 7. ES d lá chyby Ad 6. P íklad: Pacient je na ARO (JIP). Chceme diagnostikovat jeho stav. • Nep esná data: Chybí výsledky laboratorního testu nebo EKG, nebo jsou zatíženy chybou. • Nep esné znalosti: Chybí-li výsledky z laboratorního testu nebo EKG a pacient má bolest na hrudi, pak se m že jednat o srde ní problém.


Strana 4

ZSY

Dovede-li lidský expert vy ešit úlohu p ibližn za 15 minut ⇔ složitost problematiky je vhodná pro nasazení ES. Složitost

rozklad Diagnostika poruchy automobilu

Elektronický systém

Baterie

Alternátor

Palivový systém

Karburátor

Pumpa

2.3 VÝVOJOVÉ FÁZE ES (x vývoj konven ního programu) KONVEN NÍ PROGRAMY Numerické hodnoty Algoritmus Informace a ízení pohromad T žké modifikovat P esná informace Povelový Interface Dává kone ný výsledek Optimální ešení

EXPERTNÍ SYSTÉMY Symboly Heuristika Znalosti odd lené od ízení Lehké modifikovat Neur itá informace P irozený dialog s vysv tlením Dává doporu ení s vysv tlením P ijatelné ešení


Strana 5

Odhad požadavky Získávání znalostí

znalosti

ZSY

Iterativní proces: - stavba prototypu - testování - modifikace ES vzniká jako vedlejší produkt porozum ní dané problematice.

Návrh struktura Testování vyhodnocení Dokumentace produkt Údržba

Fáze vývoje 1. Odhad Zkoumá se proveditelnost, oprávn nost nasazení Definuje se okruh problému Definují se zdroje znalostí ( lov k – expert, p íru ky, zprávy, …) 2. Získávání znalostí (Knowledge Acquisition) Jeden z hlavních problém p i tvorb ES - pro porozum ní problému - pro návrh ES Získávání znalostí = proces získávání, organizování a studování znalostí - sch zka s expertem - získání základní p edstavy o metod , kterou expert uplat uje 3. Návrh a) zvolit nejlepší zp sob reprezentace znalostí b) je definována základní struktura báze znalostí (BZ) a definována metoda práce se znalostmi (IM) [BZ + IM výb r SW] c) prototyp ES sloužící jako vstup do itera ního vývojového cyklu 4. Testování - spolupráce s expertem - spolupráce s uživatelem 5. Dokumentace - pro uživatele - pro vývojá e (tzv. znalostního inženýra): • slovník znalostí • procedury ešení • definice struktury ES a strategie IM (dekompozice na díl í BZ, každá s n jakým mechanismem inference, jak jsou díl í BZ ízeny, jak je ízen celek)


Strana 6

ZSY

6. Údržba - ES se neustále u í Všechny kroky 1 – 6 jsou provázány, nemusí být provád ny p esn podle uvedeného po adí

2.4 LIDÉ ZAPOJENI V PROJEKTU ES -

oborový (domain) expert znalostní inženýr uživatel

2.4.1 Oborový expert = osoba mající znalosti a dovednosti, která eší problém mnohem lépe než ostatní lidé - má expertní znalosti … hodnota experta = expert – neexpert - má dovednosti jak vy ešit problém - komunika ní schopnost, nap .: dekompilace znalostí

2.4.2 Znalostní inženýr = lov k provád jící znalostní inženýrství a je za n zodpov dný (psycholog, diplomat, výzkumník, programátor) - dovednosti um ní, nebo nezná p esný postup jak vyvinout ES - komunika ní schopnosti - schopnost naprogramovat ES pomocí vývojového SW schopnost vybrat vhodnou metodu reprezentace znalostí → vhodný SW: (systémy založené na pravidlech, systémy založené na rámcích)

2.4.3 Uživatel Uživatel by m l: - pomoci definovat specifikaci interface (interface znamená ≈ 1/2 rozpo tu projektu) - pomoci p i získávání znalostí (ze za átku více než expert) - pomoci p i vývoji software • definovat p ístup k systému • vstup informace (menu, databáze, data informa ního systému) • specifikovat vysv tlovací mechanismus • definovat formu výstupu (databáze,…) • specifikovat utility

2.5 VÝVOJ Konven ní programy - d raz na ešení - programátor pracuje sám - sekven ní vývoj

Expertní systémy - d raz na problém - týmová práce - iterativní vývoj


Strana 7

ZSY

Požadovaná kvalifikace: Domain Expert (oborový expert): - má expertní znalosti - má dovednosti jak ešit problém - je schopen p edat znalosti - je schopen v novat as - není nep átelský Knowledge Engineer (znalostní inženýr): - má dovednosti znalostního inženýrství - dobré dorozumívací schopnosti - umí p i adit problému vhodný software - umí programovat expertní systémy End - User (uživatel): - umí pomoci definovat specifikaci interface - umí pomoci p i získávání znalostí (knowledge acquisition) - umí pomoci p i vývoji software Hlavní odpov dnosti znalostního inženýra: - ohodnocení problému - rozhovor s expertem - identifikace koncepce expertem užívané - organizace znalostí - identifikace metody ešení problému expertem užívané - výb r software - „kódování“ znalostí do systému - testování systému - revize systému - integrace systému do pracovního prost edí - údržba systému

3 REPREZENTACE ZNALOSTÍ Znalost = abstraktní pojem p edstavující individuální porozum ní danému problému ≡ porozum ní oblasti p edm tu (Pro nás znalost ≡ oborová znalost - nap . ást oblasti medicíny - nap . infek ní nemoce) Obor = dob e vymezená oblast daného p edm tu Jak zachytit znalosti? Reprezentace znalostí = metoda užívaná k zakódování znalostí do báze znalostí ES Neexistuje jedna metoda, jak znalosti zakódovat.

3.1 TYPY ZNALOSTÍ Psychologové vymysleli n kolik teorií, jak lov k eší problémy a jak uchovává znalosti. Výzkumníci v UI p ebrali tyto výsledky a vyvinuli metody, jak je nejlépe reprezentovat v po íta i. Neexistuje jedna nejlepší teorie, jak znalosti uchovávat, ale je jich n kolik. Protože znalostní inženýr musí um t vybrat nejlepší z nich „šitou“ na daný problém, m l by znát všechny.


Strana 8

ZSY

Typy znalostí - procedurální – pravidla, strategie, agendy, procedury - deklarativní – pojmy, objekty, fakty - metaznalosti – znalosti o jiných typech znalostí a jak je užít - heuristické znalosti (m lké) – znalosti „vycucané z palce“ - strukturální znalosti (celkový model ES) – soubory pravidel, vztahy mezi pojmy, vztahy mezi objekty

3.2 TECHNIKY REPREZENTACE ZNALOSTÍ O - A - V triplet (O - V - H triplet) pravidla • sémantické sít • rámce • logika Každá má své výhody i nevýhody. • •

3.2.1 O - A - V (Object - Attribute - Value = Objekt - Vlastnost - Hodnota) Základním prvkem je fakt = forma deklarativní znalosti. V UI a ES se asto hovo í o výroku. Fakt = výrok = tvrzení, které m že být pravdivé nebo nepravdivé V pracovní pam ti je každému faktu p i azena hodnota TRUE nebo FALSE. O-A-V je komplexn jší pojem výroku, faktu. Fakt užijeme p i p i azení hodnoty vlastnosti objektu. P íklad: Fakt „mí má ervenou barvu“ vyjád íme pomocí O - A – V: O - mí A - barva mí barva ervená V - ervená

objekt

atribut

hodnota

Hodnota m že být • Boolean … true/false • numerická … íslo • textová … et zec Objekt ale m že mít n kolik vlastností: P íklad: Objekt s n kolika vlastnostmi:

mí

objekt

píchlý

true

barva

ervená

pr m r

1,2

atribut

hodnota


Strana 9

ZSY

3.2.1.1 jednohodnotový a vícehodnotový fakt P íklad: jednohodnotový fakt vyjád ený pomocí O-A-V:

barometr

tlak

roste

objekt

atribut

hodnota

Tlak m že nabývat práv jedné hodnoty z množiny tlak {roste, klesá, stojí}. P íklad: vícehodnotový fakt vyjád ený pomocí O-A-V:

lov k

dosažené vzd lání

objekt

atribut

-

VŠ SŠ ZŠ

hodnota

Dosažené vzd lání m že nabývat n kolika hodnot z množiny vzd lání (základní, st edoškolské, vysokoškolské, postgraduál) Oba - jednohodnotový i vícehodnotový fakt vyjád ený pomocí O-A-V mají tuto podstatnou vlastnost: pokud p i adíme hodnotu/hodnoty atributu, systém (program ES) automaticky p i adí této hodnot /t mto hodnotám hodnotu TRUE a všem ostatním hodnotám atributu hodnotu FALSE. 3.2.1.2 nep esné fakty Jistotu pravdivosti faktu vyjad ujeme pomocí initele jistoty (CF = Certainty Factor) hodnota CF: 0

-1.0 ur it neplatí

+1.0

nevíme

ur it platí

P íklad:

po así objekt

p edpov

atribut

déš

0,6

hodnota

CF

3.2.1.3 Fuzzy fakty lov k m že íci: „Osoba X je vysoká.“ Kolik to ale je cm? Fuzzy logika: Umož uje pracovat s metodami reprezentace nejednozna ného tvrzení i s metodami uvažování, které tato nejednozna ná tvrzení využívají. Používá pojmy fuzzy množiny: Klasická teorie množin každému prvku univerza p i adí bu prvek dané množiny (s absolutní ur itostí) anebo prvek jejího dopl ku (op t s absolutní ur itostí). Fuzzy (nez etelná) množina však nemá p esné hranice a proto nelze prvek univerzální množiny jednozna n p i adit bu k množin anebo k jejímu dopl ku. Pro každou fuzzy množinu je proto zavedena tzv. funkce p íslušnosti, která každému prvku univerza p i adí váhu naší d v ry (tzv. stupe p íslušnosti) v to, že tento prvek je prvkem dané fuzzy množiny.


Strana 10

ZSY

P íklad: nízký

normální

vysoký

nízký

normální

vysoký výška v cm

klasické množiny

fuzzy množiny

funkce p íslušnosti výška normální

1

výška vysoká

výška nízká

0 100

200

300

cm

3.2.2 Pravidla pravidlo = reprezentace znalostí udávající vztah mezi vstupní informací a výstupní informací, která se v p ípad , že vstupní informace je známá, stane také známou IF AND BZ if A AND then B OR … THEN if B AND then C (ELSE) … nepoužívat - pravidla jsou uložena v BZ uživatel

A B C

BD=PP

Co všechno m že pravidlo d lat - volání procedury - volání programu IF telefonovat THEN CALL program (jméno, telefonní íslo) Typy pravidel - vzájemný vztah - doporu ené - p íkaz - strategie - heuristika -

… IF baterie je špatná THEN auto nestartuje … IF auto nestartuje THEN použij taxi … IF auto nestartuje THEN zavolej taxi službu … IF máš použít taxi THEN zkontroluj, jestli máš peníze, cenu/km, taxametr

pravidla mohou pracovat s prom nnými … IF X je starší jak 65 let THEN d chod neur itá pravidla … IF inflace ↑ THEN tém jist úroková míra roste 0,8


-

Strana 11

ZSY

metapravidla = pravidlo o pravidlech IF auto nestartuje AND závada není v palivovém systému THEN použij pravidla o elektrickém systému BZ1

BZ2

el. systém

pal. systém

metapravidla

BZ

BZ

tabule

tabule = místo v PP (=BD), ve kterém si jednotlivé BZ vym ují informace

3.2.3 Sémantické sít sémantická sí = reprezentace znalostí vyjád ená formou grafu, kde vrcholy grafu ur ují objekty, vlastnosti, hodnoty a hrany ur ují vztahy mezi nimi individuální vrchol

k ídla

obecný vrchol

vzduch

MÁ DÝCHÁ

Pepí ek

JE

kanárek

JE JE

CESTUJE

létá

zví e

CESTUJE

CESTUJE

létá chodí plave

létá

tu ák nemusí se psát eší vazba JE

pták

JE

CESTUJE

plave

ošet ení výjimek


Strana 12

ZSY

3.2.4 Rámce Rámec = datová struktura, která zahrnuje stereotypní znalosti o daném objektu nebo pojmu Rámec t ídy

Individuální rámce = instance

jméno

Pták

jméno

t ída

zví e

t ída

pták

potrava

ervi

potrava

ervi

barva

—

barva

N k ídel

2

N k ídel

d di nost

Pepí ek

žlutá

létá

ANO

létá

NE

hlad

—

hlad

—

aktivita

—

aktivita

—

žije

• … jsou prázdné sloty p i tvorb (vytvo ení)

rámce jsou inicializovány

•

1

… hlad … aktivita

klec

zm na oproti rámci t ídy

dopl ující informace

metody (procedury)

Metoda_Hlad( ) … íká, co má pták d lat, když má hlad Metoda_Aktivita( ) … íká, co pták d lá Faseta = vlastnost rámce, která: 1. m že definovat obor hodnot pro každý datový typ ( et zec, íslo, boolean,...), nap .: N k ídel íslo 0≤N≤2 2. pom že zjistit hodnotu slotu, je-li neznámá - faseta IF_NEEDED pom že íci, co d lat, když se hodnota slotu zm ní - faseta IF_CHANGED P íklad: Faseta IF_NEEDED V rámci Pepík (tj. individuální rámec) nap . nemáme k dispozici hodnotu slotu létá (neznáme ji): létá: — (prázdný slot) Chceme tuto hodnotu ur it. Voláme fasetu IF_NEEDED. Faseta volá metodu: IF N k ídel = 2 THEN létá := ANO ELSE létá := NE


Strana 13

V Shellu se zapisuje: IF Pepík : N_k ídel = 2 THEN Pepík : létá := ANO ELSE Pepík : létá := NE

ZSY

lépe:

IF Self : N_k ídel = 2 THEN Self : létá := ANO ELSE Self : létá := NE

Faseta IF_CHANGED V rámci Pepík se zm ní hodnota slotu hlad z NE na ANO. Co se stane dál? Vyvolá se faseta IF_CHANGED. Faseta volá metodu: IF Self : Hlad = TRUE THEN Self : Aktivita = „jí“ + Self : Potrava Pak se objeví ve slotu Aktivita : aktivita jí ervy

3.2.5 Logika predikátový po et P íklad: Každý, kdo má rád pivo a pije pivo, má rád hospodu. rád (X, pivo) pije (X, pivo)

∀X: rád (X, pivo) ∧ pije (X, pivo) → rád (X, hospoda)

4 INFEREN NÍ MECHANISMUS 4.1 UVAŽOVÁNÍ LOV KA Uvažování = proces práce se znalostmi, p íchozími i vyvozenými fakty a strategiemi ešení, který se snaží dosp t k záv ru (fakt = tvrzení výrok = tvrzení TRUE, FALSE axiom = TRUE výrok)

4.1.1 Dedukce axiom (fakt): stojím v dešti (A) implikace (pravidlo): každý, kdo stojí v dešti, zmokne záv r (nový fakt): zmoknu (B) Pravidlo modus ponens: Když platí A a platí A→ B, pak platí B.

4.1.2 Indukce Platí n co pro x1, x2, …, xn zobecníme, že platí pro ∀xi, pak platí i pro xn+1, …

4.1.3

Abdukce

Když platí B a platí A → B, pak platí A. Vím, že zmoknu. Abdukcí usoudím, že: stojím v dešti.


Strana 14

ZSY

4.1.4 Analogie lov k vytvá í model na základ zkušenosti. Tento model pak používá k tomu, aby porozum l situaci nebo objektu. Na základ analogie pak mezi dv ma situacemi i objekty lov k hledá stejné rysy nebo naopak odlišnosti. TYGR LEV barva: ervená s pruhy žije kde: Indie, Asie,… jí co: maso po et nohou: 4 pat í do: šelma

4.1.5 Heuristika Selský rozum opírající se spíše o dobrý úsudek (mín ní) než o exaktní logiku m že velmi efektivn ešit problém. Nap .: „Volný emen v tráku v tšinou zp sobí podivný hluk.“ Tuto znalost si m že vytvo it mechanik v autoservisu. Je to znalost heuristická, vycucaná z prstu. Užijeme-li heuristické znalosti k ízení hledání v BZ, nazýváme toto hledání heuristickým hledáním nebo nejlepší – první hledání (best-first search). Heuristické hledání nezaru uje ešení, jen garantuje, že hledání se bude ubírat „rozumným“ sm rem. Používá se tam, kde chceme rychlé ešení.

4.1.6 Nemonotónní usuzování Jsou-li sbírané fakty (tvrzení) statické (nem nné), jedná se o monotónní usuzování. U

jeden možný záv r

množina možných záv r

Stupe vysv tlení: je tím v tší, ím menší je množina možných záv r . P íklad:

zarostlost

výška

ešení:

výzbroj

zarostlost

= RUMCAJS

t=1 : vysoký stupe vysv tlení

výška t=2 : zarostlý

t=3 :má bambitku monotónní pr b h

t


Strana 15

ZSY

Není-li fakt statický v pr b hu usuzování (m že docházet k jeho zm nám) m že snížit má nemonotónní pr b h nemonotónní usuzování

stupe vysv tlení se

stupe vysv tlení

t

P íklad: IF vítr fouká THEN kolébka se houpá Fakta: t = 1: vítr fouká kolébka se houpá … t = 2: je vich ice kolébka se houpá … t = 3: vich ice skon í kolébka se nehoupá

…

lov k uvažuje nemonotónn . Systém, který je schopen nemonotónního usuzování, se nazývá nemonotónní systém – p íkladem je tzv. truth-maintenance system - viz. skripta [Kepka]

4.1.7 Generování a testování 4.1.8 Default usuzování -

nezná-li se p edpoklad, bere se default hodnota (d di nost)

4.1.9 Intuice

4.2 INFERENCE = proces práce ES se znalostmi, vstupními a vyvozenými fakty používající definované strategie ešení, které vede k vyvození záv ru / záv r = proces užívaný ES k vyvození nové informace z informace známé báze znalostí (BZ) – dlouhodobá pam BZ

báze dat (BD) – krátkodobá pam

BD

IM

Otázky: 1. Jak prohledávat BZ? 2. Jaké otázky klást uživateli? 3. Jaké pravidlo vybrat? 4. Jak vyvozená (nová) informace ovlivní prohledávání BZ? V ES založených na pravidlech se eší D (dop edné et zení) a Z (zp tné et zení) P vod postupu v logice – logickém uvažování

4.2.1 Pravidlo modus ponens [A ∧ (A

B)]

B


Strana 16

ZSY

P íklad: R1: IF (pacientova t > 38°C) E1 THEN (pacient má hore ku) E2 R2: IF (pacient má hore ku) E2 THEN (vezme si 2 prášky léku) E3 Platí nyní: (t > 38°C). Pak máme: E1; E1 → E2; E2 → E3 t = 1: E1; E1 → E2; E2 → E3 t = 2: E1; E2; E1 → E2; E2 → E3 t = 3: E1; E2; E3; E1 → E2; E2 → E3

4.2.2 Rezoluce Chceme-li odvodit (dokázat) hypotézu, je lépe použít rezoluce (nežli modus ponens) (A ∨ B) ∧ (¬B ∨ C) A ∨ C P íklad: Cílem je dokázat, že E3 je pravda, mám E1; E1 → E2; E2 → E3 ešení: 1. p ipíši ¬E3 E1; ¬E3; E1 → E2; E2 → E3 2. • ¬E1 ∨ E2 • ¬E2 ∨ E3 • E1 • ¬E3 t = 1: • ¬E1 ∨ E2 • ¬E2 ∨ E3 ¬E2 ∨ ø • E1 • ¬E3 ∨ ø t = 2: • ¬E1 ∨ E2 • ¬E2 ∨ ø • E1 • ¬E3 t = 3: • ¬E1 ∨ ø • ¬E2 • E1 ∨ ø • ¬E3

¬E1 ∨ ø

ø∨ø=ø

platí E3 (d kaz sporem)

↑ rezolventa

4.2.3 Nerezoluce Na rozdíl od rezoluce si pamatuje, co je p edpokladem a co záv rem.

4.3 DOP EDNÉ ET ZENÍ (D ) Nejd íve se seberou všechna data od uživatele (všechny informace), pak se usuzuje na záv r. Nap . léka sbírá informace o symptomech nemoci od pacienta. Dop ednému et zení se proto íká hledání ízené daty. D vychází z pravidla modus ponens. D = dop edné et zení = inferen ní strategie, která za íná množinou známých fakt , odvozuje nová fakta použitím pravidel, jejichž p edpoklady odpovídají známým fakt m, a pokra uje v tomto procesu, dokud není odvozený cílový stav nebo již neexistují pravidla, která mají p edpoklad vyhovující fakt m.


Strana 17

ZSY

4.3.1 Proces D probíhá takto: Inicializace: žádné pravidlo není aktivní ani nebylo aktivní (tj. flag aktivity je shozen u každého pravidla) 1. Informace od uživatele se zapíše do PP (pracovní pam ti). 2. Prohledá se BZ, a to od za átku, a najde (najdou) se první (všechna) pravidlo (a), jehož (jejichž) *p edpoklad (y) vyhovuje (í) fakt m v PP a jež (jenž) nebylo (a) dosud aktivní (tj. flag aktivity je shozen). Pokud se pravidlo nenajde, jde se na krok 4. Vybere se jedno pravidlo podle zvolení rozhodovací strategie. 3. Pravidlo se aktivuje, tj. jeho záv r se p idá do PP a ozna í se, že bylo aktivováno (tj. flag aktivity nahozen) 4. Pravidlo se p i prohledávání BZ nenajde proces kon í (IF E1 AND E2) OR E3

THEN C

*celkový p edpoklad


Strana 18

ZSY

Dop edné et zení: sb r dat data → PP

Nalezení 1 (všech) pravidla (pravidel), jehož (jejichž) *p edpoklad (y) je (jsou) v PP a jež (jenž) nebylo (a) dosud aktivní

STOP

nalezeno pravidlo (alespo jedno pravidlo)

-

+ Vybereme pravidlo ze všech nalezených podle strategie

*viz. p edchozí *

Aktivace pravidla záv r → PP nahozen flag aktivity

4.3.2 P íklad na Z a D Diagnóza streptokokové nákazy v krku Pravidla v BZ: Pr1 IF bolení v krku AND o ekáváme bakteriální infekci THEN streptokoková nákaza …… je (goal) cíl 1 Pr2 IF t > 38°C THEN pacient má hore ku Pr3 IF pacient nemocen ≥ 2 m síce AND pacient má hore ku THEN o ekáváme bakteriální infekci Pacient má tyto údaje: t = 38,5°C t > 38°C nemocen 2 m síce pacientova nemoc ≥ 2 m síce bolení v krku

nalezen cíl

+

STOP


Legenda:

Strana 19

P1 … díl í p edpoklad

ZSY

Pr1 … díl í pravidlo

CYKLUS 1 Pr1, P1 (pravidlo, p edpoklad) (bolení v krku)

+

Pr1, P2 (o ekáváme bakteriální infekci) •Pr2, P1 (t > 38 °C) aktivace Pr2 (pacient má hore ku) Konec cyklu

−

t > 38°C nemoc ≥ 2 m síce bolení v krku

—’’ — +

—’’ —

pacient má hore ku

záv r do PP

CYKLUS 2 Pr1, P1

+

—’’ — —’’ —

Pr1, P2 P1 nemohu aktivovat

−

—’’ — —’’ —

Pr3, P1 (nemoc ≥ 2 m síce)

+

—’’ — —’’ — +—’’ —

•Pr3, P2 (pacient má hore ku) aktivace Pr3: (o ekáváme bakteriální infekci) Konec cyklu CYKLUS 3 Pr1, P1

o ek.bakter. infekci

+

—’’ — —’’ — —’’ — +

•Pr1, P2 aktivace Pr1: (streptokoková nákaza) Konec cyklu

—’’ —

záv r do PP

záv r do PP

CYKLUS 4 neexistuje žádné vhodné pravidlo

STOP

—’’ — —’’ — —’’ —

streptokok. nákaza

PP


Strana 20

ZSY

Dop edné et zení vyvozuje ze vstupních dat cokoliv (hlednání ízené daty) – i když je to zbyte né. Vylepšení D spo ívá v testování PP po každé její zm n , zda neobsahuje žádaný cíl. Obsahuje-li jej, proces kon í. P íklad: V BZ budeme mít navíc tato pravidla: 1. IF pacient má hore ku THEN nep jde do kina 2. IF nep jde do kina THEN p jde na seminá cíl 4 Po adí pravidel v BZ: 1, 2, 3, 4, 5 dopadne to stejn v p ípad , že použijeme „vylepšení“ Po adí pravidel v BZ: 1, 5, 4, 3, 2 nedopadne to stejn , p ibudou 2 cykly (i když aktivace 2, 4, 5, 3, 1, ø použijeme „vylepšení“) Z p íkladu plyne, že záleží na po adí pravidel v BZ. P i špatném uspo ádání pravidel: 1. v každém cyklu m že být prohledáno velké množství pravidel 2. mohu odvozovat zbyte né cíle (záv ry) (i p i „vylepšení“) Po adí pravidel udává, jaká je efektivita procesu D .

4.3.3

ešení konflikt

P íklad: V BZ budou navíc tato pravidla: 3. IF pacient má hore ku THEN zajde do lékárny 4. IF pacient má hore ku THEN zajde Je-li po adí pravidel 1, 2, 3, 4, 5, 6, 7 Je-li po adí pravidel 1, 5, 4, 3, 2, 6, 7 Je-li po adí pravidel … jiné …

cíl 2 cíl 3 ? cíl : cíl 1 cíl 4 cíl 2, nebo 3

Z uvedeného p íkladu vyplývá, že v ur ité fázi mohu aktivovat více pravidel, nebo mají spln né p edpoklady, a záv ry t chto pravidel mohou být v konfliktu. Standardní postup je vybrat 1. pravidlo, ale pak je výsledek závislý na po adí pravidel ešení konflikt = strategie ur ující N-best pravidel v p ípad , že více jak jedno pravidlo m že být aktivní Typy strategií: 1. vybrat 1. pravidlo podle po adí 2. podle priority (každé pravidlo má p i azenou prioritu) 3. podle specifi nosti pravidel IF A IF A IF C PP: THEN Z3 A AND B THEN Z2 THEN Z1 B nejvíce specifické C 4. podle erstvosti p edpoklad v PP nej erstv jší 5. neuvažovat již aktivovaná pravidla 6. výb r více pravidel, záv ry do odd lených PP a úlohu eším paraleln Pomocí strategií realizujeme ešení konflikt , realizujeme heuristické hledání v inferen ní síti (AND/OR stromech)


Strana 21

ZSY

4.3.4 D jako t íkrokový proces D 1. 2. 3.

je t íkrokový proces: rozpoznej (∀ ∀ pravidla, jejichž p edpoklady vyhovují údaj m v PP) rozhodni (výb r jednoho pravidla – podle strategie) prove (aktivace pravidla, záv r do PP)

4.4 ZP TNÉ ET ZENÍ (Z ) Použiji v p ípad , že se snažím ov it hypotézu (hypotézy) … cíl = hypotéza (platí i neplatí ?)

= hledání ízené cílem, používá princip rezoluce Z

= inferen ní strategie, která se snaží dokázat hypotézu (cíl) sbíráním fakt (informací), které podporují dokazovanou hypotézu

4.4.1 Postup p i Z 1. Za neme d kazem cíle: → podíváme se, zda cíl již není dokázán v PP (m že ho dokázat i jiná BZ) - když je dokázán, jdeme na dokazování dalšího cíle, neexistuje-li další cíl, pak kon íme 2. hledáme pravidla (v BZ) taková, že jejich záv r je totožný s dokazovaným cílem (tzv. cílová pravidla) 3. najdou-li se taková pravidla, podíváme se na jejich p edpoklad, zdali je v PP 3.1 p edpoklad je v PP - pravidla aktivujeme, jejich záv ry jdou do PP a jdeme na krok 1 3.2 p edpoklad není v PP - p edpoklad prohlásíme za nový cíl (podcíl) a jdeme na krok 1 4. nenajdou-li se pravidla (v BZ) – z kroku 2 taková, že jejich záv r je totožný s dokazovaným cílem (podcílem): cíl = záv r = primitivum = tvrzení, které není podporované žádným pravidlem (v BZ) - systém se zeptá na „záv r“ (= primitivum) uživatele Uživatel odpoví: - primitivum platí : aktivuji pravidlo dáme primitivum do PP: jdeme na krok 1 (budeme dokazovat další cíl) primitivum - primitivum neplatí: cíl nedokázán („negace primitiva“ → PP), jdeme na krok 1 (budeme dokazovat další cíl)


Strana 22

ZSY

Z START

STOP

mám dokázat ješt další neotestované cíle?

-

výb r dalšího neotestovaného cíle 1 je cíl dokázán?

2 ∃ v BZ pravidla, jejichž záv r je cílem?

cíl se stává primitivem dotaz uživateli

odpov (odpov

3 jsou ∀ (díl í) p edpoklady pravidla spln ny (jsou v PP)?

3.2

+) → cíl otestován

aktivace pravidla záv r → PP 3.1

∀ p edpoklad (díl í) se stává novým cílem

→ PP

cíl otestován


Strana 23

P íklad: na Z z odst. 4.3.2 Diagnóza streptokokové nákazy v krku (zadání viz odst. 4.3.2) 0. cíl := streptokoková nákaza (Pr1, Z1) (pravidlo, záv r) 1. (Pr1, Z1) není v PP najdu v BZ Pr1 dokazuji: (Pr1, P1) – bolení v krku ? není v PP nový cíl := (Pr1, P1) 2. (Pr1, P1) není v PP najdu v BZ ø (1, 2) cíl = primitivum dotaz uživateli uživatel odpoví: bolení v krku (4) 3. cíl := streptokoková nákaza (Pr1, Z1) (Pr1, Z1) není v PP najdu v BZ Pr1 (1,2) dokazuji: (Pr1, P1) → bolení v krku ? (3) (Pr1, P1) – bolení v krku je v PP 4. (Pr1, P2) není v PP (3) nový cíl := (Pr1, P2) – o ekáváme bakteriální infekci (1) 5. (Pr1, P2) není v PP najdu v BZ Pr3 (2) dokazuji: (Pr3, P1) – nemoc ≥ 2 m síce? (3) (Pr3, P1) není v PP (3) nový cíl := (Pr3, P1) – nemoc ≥ 2 m síce 6. (Pr3, P1) není v PP najdu v BZ ø (1, 2) cíl = primitivem dotaz uživateli uživatel odpoví: nemoc ≥ 2 m síce (4) 7. cíl := (Pr1, P2) – o ekáváme bakteriální infekci (Pr1, P2) není v PP najdu v BZ Pr3 (1, 2) dokazuji: (Pr3, P1) nemoc ≥ 2 m síce (Pr3, P1) nemoc ≥ 2 m síce je v PP (3) 8. (Pr3, P2) – pacient má hore ku – není v PP (3) nový cíl := (Pr3, P2) – pacient má hore ku 9. (Pr3, P2) není v PP najdu v BZ Pr2 (1,2) Dokazuji: (Pr2, P1) – t > 38°C (3) (Pr2, P1) není v PP nový cíl := (Pr2, P1) – t > 38°C 10. (Pr2, P1) není v PP najdu v BZ ø (1,2) cíl = primitivum dotaz uživateli uživatel odpoví: t > 38°C (4) 11. cíl := (Pr3, P2) – pacient má hore ku (Pr3, P2) není v PP najdu v BZ Pr2 (1,2) Dokazuji (Pr2, P1) – t > 38°C (3) (Pr2, P1) je v PP aktivace Pr2 (3.1) 12. cíl := o ekáváme bakteriální infekci – (Pr1,P2) (Pr1, P2) není v PP najdu v BZ Pr3 (1,2) (Pr3, P1) – pacient nemocen ≥ 2 m síce – je v PP, (Pr3, P2) – pacient má hore ku je v PP (3) aktivace Pr3 13. cíl := streptokoková nákaza (Pr1, Z1) (Pr1, Z1) není v PP najdu v BZ Pr1 (1,2) dokazuji (Pr1, P1) – bolení v krku, (Pr1, P2) – o ekáváme bakteriální infekci – jsou v PP (3) aktivace Pr1 14. Další cíl neexistuje STOP

ZSY

PP

bolení v krku

bolení v krku

—’’ —

nemoc ≥ 2 m síce

—’’ —

nemoc ≥ 2 m síce

—’’ —

t > 38 °C

—’’ —

t > 38 °C

—’’ —

pacient má hore ku

—’’ —

o ekáváme bakt.infekci

—’’ —

streptokoková nákaza


Strana 24

BACKWARD – postupuje do hloubky ?

ZSY

FORWARD – postupuje do ší ky

?

p íklad vhodný pro Z

? = cíl

?

?

?

?

p íklad vhodný pro D

= list = data od uživatele

P íklad: P1: IF existují známky infekce v krku AND organismus je streptokok THEN streptokoková nákaza v krku ? P2: IF krk je ervený THEN existují známky infekce v krku P3: IF organismus je grampozitivní AND tvar je kok AND organismus je et zovitý THEN organismus je streptokok Cíl 1: streptokoková nákaza v krku Pacient: - krk je ervený - organismus je grampozitivní - tvar je kok - organismus je et zovitý

4.4.2 Agenda cíl agenda cíl = ada cíl zpracovávaná v ur itém po adí 1. nejjednodušší je seznam cíl 1. cíl A 2. cíl B … 2. Hierarchický seznam (výhodou je umožn ní áste ného ešení) P íklad: - + 1. zví e je pták + konec 1.1 zví e je drozd 1.2 zví e je p nkava 2. zví e je savec - + 2.1 zví e je k 2.2 zví e je kráva 3. zví e je plaz …… 3. Strategie (dynamický seznam) Po spln ní každého jednotlivého cíle se definuje, co se má d lat dál (nap . STOP, p ejít na jiný cíl, atd.) P íklad: + STOP 1. kup televizor → + 2. kup rádio → STOP 3. kup vysava → STOP


Strana 25

ZSY

4.4.3 Po adí cíl dané uživatelem P íklad: 10 modul 1. diagnostika 1. modul 2. — | | — 2. — | | —

3. — | | —

3. — | | —

… 10. — | | — 1

- OK?

10. — | | —

2

3

4

5

6

7

8

9

10

4.4.4 Po adí cíl dané pravidly P íklad: 1. cíl = zesilova 2. cíl = chladi

agenda ≡

IF P>10W THEN jdi na 2.cíl

metapravidlo - množina pravidel z BZ odvozující 1. cíl cíl metapravidla m žeme p idat do seznamu cíl vyšet ujeme nejprve cíle metapravidel

4.5 VÝHODY A NEVÝHODY D A Z 4.5.1 D - výhody 1. výhodné p i sb ru informace s následným vyhodnocováním 2. z malého množství vstupních informací odvozuje velké množství nových fakt IF prší THEN tráva je mokrá IF tráva je mokrá THEN nesekat IF tráva je mokrá THEN nehrát fotbal IF prší THEN deštník 3. výhodné v úlohách plánování

4.5.2 D - nevýhody 1. nepozná d ležitost vstupních informací - vyvozuje úpln všechno m že klást otázky v nelogickém sledu 3. v p ípadech, kde existuje málo hypotéz, které se mají zodpov d t, existuje velké množství vstupních dat 2.

4.5.3 Z – výhody 1. 2. 3. 4.

existuje málo hypotéz otázky klade v logickém sledu hledá jen to, co je pot ebné pro spln ní cíle výhodné v diagnostice

4.5.4 Z – nevýhody 1. postupuje slep od cíle (ko ene) dol 2. když existuje velké množství hypotéz a málo vstupních dat

4.6 VÝB R MEZI D A Z 1. Jak úlohu eší expert (nap . málo hypotéz 2. Jak je inference ešena jinde 3. Nic se ned je, i když se spleteme

Z )


Strana 26

ZSY

4.7 KOMBINACE D A Z - 2 zp soby 1. separované moduly D

Z

D

metapravidla

D

Z

D

tabule

2. Z s démony démon = démonické pravidlo = pravidlo, které se aktivuje kdykoliv, když jsou spln ny jeho p edpoklady P íklad: Diagnostika tlakové nádoby → Z 1. BZ obsahuje pravidla, která jsou využívána Z 2. Do BZ p idáme tzv. démonická pravidla (_D) 1D: IF tlak > 1000 THEN stav ohrožení 2D: IF stav ohrožení THEN poplach 3D: IF poplach THEN siréna, telefon, evakuace 3. Proces ES po spušt ní: Jakmile dojde k události „tlak > 1000“, aktivuje se pravidlo 1D nová událost „stav ohrožení“ aktivuje se 2D atd. (1D až 3D jsou et zeny D ) - práce v reálném ase ízení událostmi


Strana 27

ZSY

4.8 HLEDÁNÍ VE STAVOVÉM PROSTORU stavový prostor = strom nebo graf, kde uzly = stavy úlohy, hrany = vztahy (p edpisy p echodu) mezi uzly V ES založených na pravidlech jsou uzly = p edpoklady nebo záv ry pravidel a hrany = pravidla. IM (inferen ní mechanismus) íká, jak procházet graf (stavový prostor), abychom co nejrychleji (a nejlépe) dosp li k cíli (cílovému uzlu, cílové hypotéze). P íklad: Servírovat bílé i ervené? 1 6 1. IF objednáno maso P1 THEN ervené víno Z1 2. IF objednána ryba P2 Z1 Z2 THEN bílé víno Z2 3. IF mají rybu P3 11 6 2 77 P4 AND máme dost pen z na rybu 3 THEN objednáme rybu Z3 4. IF mají maso P5 P9 P1,Z4 P2,Z3 P6 AND máme dost pen z na maso 4 5 ANO 3 8 THEN objednáme maso Z4 4 79 AND AND P7 5. IF máme ≥ 300 K THEN máme dost pen z na maso Z5 P5 P6,Z5 P3 P4,Z6 6. IF máme ≥ 150 K P8 ANO ANO THEN máme dost pen z na rybu Z6 1 5 7. IF skute n chceme bílé víno P9 THEN bílé víno Z2 2 P7 P8 ANO N Z … prohledávání do hloubky NE ( AN E O) D … prohledávání do ší ky Inferen ní sí (speciální AND/OR stromy) (ukázka sleposti Z ⇔ 11 krok ) pozn: Pro demonstraci je BZ procházena až do konce!

4.8.1 Prohledávání stavového prostoru do hloubky Viz. • v p edchozím p íkladu, používá ho Z (od cíle k uzl m = primitiv m) prohledávání stavového prostoru do hloubky = technika hledání, která prohledává stavový prostor tak, že prohledává d íve vždy uzly s v tší i stejnou hloubkou, než je hloubka uzl ostatních hloubka uzlu = po et hran cesty vedoucí od ko ene k uzlu 1 cíl Výhody: 1. zaru uje ešení – v p ípad kone ného po tu stav 2. rychlé v p ípadech, kdy je výhodné použít Z 3. zaost ené na cíl 4. interakce s uživatelem v logickém sledu Nevýhody: 1. slepé 2. nevhodné pro rozsáhlý stavový prostor 3. nevhodné v p ípadech, kdy je výhodné použít D vstupní informace


Strana 28

ZSY

4.8.2 Prohledávání stavového prostoru do ší ky Viz • v p edchozím p íkladu, používá ho D prohledávání stavového prostoru do ší ky = technika hledání, která prohledává stavový prostor tak, že prohledává d íve vždy uzly s menší i stejnou hloubkou než je hloubka uzl ostatních 1 2 3 4 5 6 7 ...cíle 1-7 Výhody: 1. zaru uje ešení 2. rychlé v p ípadech, kdy je výhodné použít D („m lké“ ešení) 3. najde minimální cestu, pot ebujeme-li ji (platí pouze tehdy, když cena cesty je rovna po tu hran!!) Nevýhody: 1. slepé 2. nevhodné pro rozsáhlý stavový prostor 3. nevhodné v p ípadech, kdy je výhodné použít Z vstupní informace 4. ↓ interakce s uživatelem

4.8.3 Prohledávání stavového prostoru heuristickým prohledáváním heuristické prohledávání = první nejlepší prohledávání = technika hledání, která užívá znalostí o problému k vedení hledání V ES se používá heuristik k: 1. po adí cíl 2. po adí p edpoklad pravidel 3. definování metapravidel 4. stanovení priorit pravidel 5. stanovení CF (= certainty factor = initel jistoty) pravidel Výhody: 1. není slepé 2. rychlejší Nevýhody: - nemusí nalézt ešení (p estože ešení existuje)

4.9 MONOTÓNNÍ A / NEBO NEMONOTÓNNÍ INFERENCE 4.9.1 Monotónní monotónní uvažování = metoda uvažování, která p edpokládá, že jakmile nastal n jaký fakt, nem že být b hem úlohy již zm n n P íklad: IF T1 je špatný THEN nahra T1 novým (T1 je po ád špatný)

4.9.2 Nemonotónní nemonotónní uvažování = metoda uvažování, která povoluje zm ny ve faktech a tím i všech záv r z fakt doposud vyplynulých P íklad: IF prší THEN vem si deštník (pak p estane pršet)

4.9.3 Monotónní a nemonotónní P íklad: IF vypína zapnut THEN sv tlo svítí


Strana 29

ZSY

IF sv tlo svítí THEN film zni en (vypína zapnu a pak vypnu) (nemonotónní s nevratnými fakty)

5 ROZHODOVACÍ STROMY, AND/OR STROMY A PRAVIDLA Z

L1 U1

U2

OR

AND

U3

U3 ∨ L2 L3 ∧ L4

U1 U2

U1 ∧ U2

Z

U3 L2

L3

L4

L1

L1

Z+

L2

L4 L3

L2

ZL4

16 = 24 L1

Z-

+

L2

−

Z-

• •

záleží na po adí L1, L2, L3, L4 ↑ více strom L2

L1

+ −

+

T

−

T L2

+ −

T Z-

T :

Z+

L4

Z-

L3 L2 L4 −

Z-


IF L1AND L2THEN Z-

IF L1+ AND L2+ THEN T

Strana 30

IF L1+ AND L2THEN T

IF L1AND L2+ THEN T

IF T AND L3+ AND L4+ THEN Z+

ZSY

IF T AND L3+ AND L4THEN Z-

IF T AND L3THEN Z-

6 MYCIN (Shortlitte, E.H.: Computer - Based Medical Consultation, MYCIN, American Elserier, New York, 1976) meningitis, bakteriémie -

požadavek lidského experta úzce vymezená oblast neur itost – výsledky test nejsou ješt k dispozici, ale je t eba lé it v asnost diagnosy stanovení lé by (u léka e bylo: - špatné dávkování v 66% - špatná kombinace lék v 62%)

6.1 HLAVNÍ RYSY 6.1.1 Z , ≈ 500 pravidel, SW: INTERLISP: P íklad:

IF (AND (SAME CONTEXT GRAMNEG) (SAME CONTEXT MORPHROD) (SAME CONTEXT AIRAEROBIC)) THEN (CONCLUDE CONTEXT CLASS ENTEROBACTERIACEAE TALLY 0.8)

6.1.2 BZ a IM odd lené 6.1.3 Metapravidla IF absces v oblasti … AND ∃ pravidla stanovující grampozitivitu AND ∃ pravidla stanovující, zda-li se jedná o ele Enterobacteriaceae THEN p ednostn prohledej pravidla eledi Enterobacteriaceae

6.1.4 Neur itost initel jistoty CF ∈ -1, 1

6.1.5 Zapamatování si minulého sezení (konzultace) 6.1.6 P izp sobení uživateli: P íklad.: ES se táže, o jakou infekci se jedná? uživatel: Endurteritis ES: Myslíte Endarteritis?

6.1.7 Alternativní lé ba -

vyžádaná uživatelem (léka em)


Strana 31

ZSY

6.2 P ÍSTUP K EŠENÍ PROBLÉMU problém: - stanovení diagnózy - stanovení lé by 1. eší se stanovení diagnózy 1.1 ur ení infekce 1.2 ur ení druhu organismu 2. eší se stanovení lé by 3 požadavky: - pokrytí organism antibiotiky - co nejmenší po et antibiotik - bezpe nost lé by

6.2.1 Diagnóza 1. standardní posloupnost otázek 1. jméno? 2. v k? 3. ……… 2. Byly provedeny testy v laborato i? 3. (Testy provedeny výsledky známy ): - známá infekce (neptá se na symptomy nemoci) 4. (Testy nebyly): - ur ení infekce na základ symptom nemoci 5. Infekce známá, pak stanovení druhu organismu

CFV

organismus

Grampozitivní

tvar

aerobní CF1

6. Výsledek diagnózy: 1. organismus 1 … CF 1 2. organismus 2 … CF 2 ………

CF2

CF3

6.2.2 Lé ba -

seznam organism (A, B, C) seznam lék pro organismy (L1, L2, …) lé ba 1 2 3

A L1 L3 …

B L2 L1 …

C L1 L2 …

- Generace : L1 .............. p edpis 1 L1,L2 ........ p edpis 2 - Test – jestli eliminuje všechny organismy Dále se provede redukce lék : L1 t ída 1 L1⇔ L2 L2 t ída 1 … L3 t ída 2

plán

Generace

test


Strana 32

ZSY

výsledek redukce: L1 - test bezpe nosti lé by: ( +v k, pohlaví, alergie, …); ze všech p edpis vybere 1 lék Výsledek lé by 1. AMPICILIN dávkování 1 2. PENICILIN dávkování 2 Léka m že zm nit seznam doporu ených lék systém otestuje alternativu: 1. test pokrytí organism 2. indukce 3. test na bezpe nost

p edloží alternativu systém:

6.3 VYHODNOCENÍ 10 p ípad nemocných 9 „odborník “ – lidí + 1 ES MYCIN = 10 % adekvátnost lé by po et p ípad , ve kterých se nemoc nepokryla (lé bou) MYCIN 70 0 p ední odborník 70 0 Fak. nemocnice 1 50 1 Fak. nemocnice 2 50 1 vedoucí 50 1 Fak. nemocnice 4 50 0 Fak. nemocnice 3 40 0 Praktik 30 1 Fak. nemocnice 5 30 0 Student 10 3

6.4 P ÍKLAD PRÁCE MYCINU 1. ES: Jméno pacienta? 2. V k 3. Pohlaví 4. Rasa (b loch,…) 5. Byly nalezeny kultury pro testování v laborato i? 6. Z jakého místa byl sebrán vzorek? 7. V jakém ase vzorek po ízen? 8. Byl vzorek prozkoumán? 9. Našly se kultury? 10. Jste schopen z test obdržet informaci o infekci? 11. Jaká je infekce? - kdyby nebyly k dispozici laboratorní testy - neznala by se infekce - ES: Pacient trpí závrat mi? Bolí ho hlava? … 12. 13. 14. 15. 16.

infekce = _______ Zadej organismus 1: Je organismus ty inka nebo kok? Je organismus Grampozitivní? Aerobicita organismu? Je infekce zjišt na b hem hospitalizace?

SPEJBL 60 M b loch ANO esf as ANO ANO ANO Budartevitis

NEZNÁMÝ ANO fakultativní


Strana 33

Pro ? … NE 17. Jsou ješt jiné organismy, o kterých se chcete radit, p ítomny? ANO 18. Zadejte organismus 2: SALMONELLA (0,4) E. COL (0,3) ↓ ES: infekce 1 je endarteritis s bakteriemií Položka 1: E. COL 0,71 Položka 2: SALMONELLA 0,60 Položka 3: PNEUMONIA 0,25 ↓Otázky PRO 19. Má SPEJBL alergickou reakci na antibiotika? NE 20. Preferovaná lé ba je: Pro pokrytí položek 1,2,3: 1. AMPICILLIN 2,5g 2. CENTAMICIN 131mg po 10 dní Poznámka: Monitorovat koncentraci séra. … 21. Chcete vid t alternativní lé by: ANO AMP. 22. Jaký lék vypustit? 23. 2. lé ba je: - pro pokrytí položek 2,3 je …

6.5 E-MYCIN (EMPTY - MYCIN) BZ

IM

BD

E MYCIN BZ

PUFF (plicní nemoci)

7 P ÍKLADY ES ZALOŽENÝCH NA PRAVIDLECH (MYCIN)

7.1 VÝHODY ES ZALOŽENÝCH NA PRAVIDLECH 1. 2. 3. 4. 5. 6. 7. 8.

p irozenost vyjád ení znalostí p irozená separace znalostí a IM modularita znalostí snadná rozši itelnost (p idání, modifikace, ubrání pravidel) proporcionální r st inteligence užívá relevantních znalostí k problému snadná realizace vysv tlovacího mechanismu snadný test konzistence systému: IF A THEN B IF A THEN B’ 9. Neur itost – snadno:

ZSY


Strana 34

IF A THEN B CF 10. Práce s prom nnými 11. Metapravidla

7.2 NEVÝHODY ES ZALOŽENÝCH NA PRAVIDLECH 1. Vyžadují p esné srovnání ( ástí pravidel) A→B B→C 2. Nepr hledné vztahy mezi pravidly A→C B→D C→B ( grafická interpretace) 3. mohou být pomalé

7.3 P ÍKLAD DIAGNOSTICKÉHO SYSTÉMU V MEDICÍN (PODOBNÝ MYCINU) (Z ) 1. stanovení diagnózy (6.1) omezená na meningitis 2. stanovení lé by (viz. 6.2) 3. stanovení alternativní lé by (viz. 6.3) 1.cíl: infekce je meningitis INFEKCE MENINGITIS R1: IF léka ví, že se jedná o meningitis OR nemoc má rysy meningitis THEN infekce je meningitis AND DISPLAY infekce je meningitis ELSE DISPLAY není meningitis RYSY MENINGITIS R2: IF laboratorní testy ukazují na meningitis OR klinické vyšet ení ukazuje na meningitis THEN nemoc má rysy meningitis LABORATORNÍ TESTY R3: IF test proveden AND zjišt ny kultury mikroor. AND kultury jsou podobné meningitis THEN laboratorní testy ukazují na meningitis KULTURY JSOU PODOBNÉ MENINGITIS R4: IF organismus má tvar koku AND organismus je grampositivní THEN kultury jsou podobné meningitis KLINICKÉ P ÍZNAKY R5: IF pacient má persistentní bolení hlavy AND pacient má závrat AND pacient je letargický THEN klinické vyšet ení ukazuje na meningitis

ZSY


Strana 35

7.4 P ÍKLAD Z , TABULE (BLACKBOARD) Diagnostika automobilu

tabule

expert na elektr.

expert na paliva

{1.ES – šéf mechanik} $BLACK1.PRL … za lení soubor tabule - inicializace prom nných pro ∀ aktivaci díl ích ES (šéf, elektriká , palivá ) {INIT} REINIT AND AND … AND

v tabuli

cena_baterie cena_startéru cena_paliva

1250 1850 50

cena_default

…

- inicializace prom nných na za átku spušt ní programu INIT oblast_problému IS neznámá AND závada IS neznámá AND ešení IS neznámá AND po áte ní informace není k dispozici {Cíle} 1. Doporu ení šéfa IS 1.1. Cena_ur ena 1.1.1. Vypsat výsledky

elektrický systém palivový systém

{Ur ení závady} P1: EL. SYSTÉM IF problém je patrn v el. systému THEN Doporu ení šéfa IS el. systém AND Oblast problému IS el. systém AND DISPLAY AND CHAIN ELEKTRIKÁ p edá se ízení elektrickému systému P2: PAL. SYSTÉM analogicky k P1 … …CHAIN PALIVÁ P3: STARTÉR_neto í IF motor IS nenastartuje AND startér IS neto í THEN problém je patrn v el. systému

ZSY


Strana 36

P4: STARTÉR_to í IF motor IS nenastartuje AND startér IS to í AND motor se otá í IS pomalu THEN problém je patrn v el. systému P5: Motor_b ží špatn IF motor IS nastartuje AND motor b ží ne ist THEN problém je patrn v el. systému P6: Motor_se to í normáln IF motor IS nenastartuje AND motor se otá í IS normáln THEN problém je patrn v pal. systému P7: Zrychlení je špatné IF auto váhá p i zrychlení THEN problém je patrn v pal. systému {Ur ení ceny} P8: Cena paliva IF ešení IS p idat palivo THEN cena_opravy = cena_paliva AND cena_ur ena (cíl 1.1) P9: cena… IF ešení IS THEN cena_opravy = cena_ AND cena_ur ena P12: P13: IF ešení IS neznámé THEN cena_opravy = default AND cena_ur ena AND DISPLAY NENALEZENO EŠENÍ Výsledky_______ P14: IF cena_ur ena THEN vypsat výsledky (cíl 1.1.1) AND DISPLAY VÝSLEDKY … {2.ES na palivo} $BLACK1.PRL {cíle} 1. Ur ení závady v palivovém systému 1.1. P edat výsledky šéfovi P1: Není palivo IF motor IS nenastartuje AND startér IS to í AND paliv.ukazatel IS nehýbe se THEN Ur ení závady v pal. systému AND Závada IS není palivo AND ešení IS p idat palivo P2: karburátor … IF … AND … AND … P5: THEN Ur ení závady v pal. systému AND Závada IS AND ešení IS P6: IF CHAIN ŠÉF

ZSY

(p i startování)

Po adí P8-P13


Strana 37

ZSY

THEN p edat výsledky šéfovi Obdobn : {3.ES na el. systém} $BLACK1.PRL {cíle} 1. Ur ení závady v el. systému 1.1. P edat výsledky šéfovi P1: IF … AND … AND … THEN Ur ení závady v el. systému P5: AND Závada IS AND ešení IS P6: IF CHAIN ŠÉF THEN p edat výsledky šéfovi

8 METODY PRÁCE S NEUR ITOSTÍ V ES Druhy neur itosti 1. v datech od uživatele P(E|e) … e – víra uživatele v platnost E 2. v BZ (pravidlech) od experta IF E THEN C (CF = 0,8) 3. v nekompatibilit pravidel IF E1 IF E1 AND E2 THEN C THEN C IF E1 IF E1 THEN C CF1 THEN C CF2

E→C

Neexistuje jednotná teorie, jak pracovat s neur itostí v ES. Existuje tedy n kolik p ístup k tomuto problému. Každý z p ístup vede k obecn odlišným záv r m (nap . jiné „váhy“ záv r ). 4. Neur itost záv ru je ovlivn na p ístupem k práci s neur itostí, který je použit. Druhy p ístup 1. Bayes v p ístup a jeho modifikace (PROSPECTOR) 2. Teorie ur itosti (Certainty Theory) 3. Fuzzy logika 4. Dempster – Shaferova teorie

8.1 BAYES V P ÍSTUP K NEP ESNÉMU USUZOVÁNÍ 8.1.1 Opakování E→H P(E) … apriorní pravd podobnost jevu E P(H) … apriorní pravd podobnost jevu H P(H|E) … aposteriorní pravd podobnost záv ru (hypotézy) H P(E|H) … podmín ná pravd podobnost jevu E za podmínky, že nastal jev H

P( H | E ) =

P( E | H ) P( H ) P( E )


Strana 38

ZSY

P(H,E) = P(E,H) = P(E|H)P(H ) = P(H|E)P(E)

P( E ) =

P( E | H i ) P( H i ) = i

Hi =

H H

p( E , H i ) = P( E ) i

i=0 i =1

P( E ) = P( E | H ) P( H ) + P( E | H ) P( H ) P íklad: Pacient s bolestmi na hrudi: má: NS (nemocné srdce): EKG

+ (ano, má NS) - (ne nemá NS) + (ano, EKG je pozitivní) - (ne, EKG je negativní)

Za p edpokladu, že EKG je + (+EKG) se ptáme, zda pacient má skute n NS, tj. jaká je pravd podobnost P(+NS | +EKG) = ? P itom máme statisticky zjišt no, že: P(+NS) … apriorní pravd podobnost jevu, že pacient má nemocné srdce = 0,1 P(+EKG+NS) … podmín ná pravd podobnost jevu, že EKG je pozitivní u pacienta s NS = 0,9 P(-EKG-NS) … = 0,95 ešení:

P(+ EKG | + NS ) P(+ NS ) = P(+ EKG ) P (+ EKG | + NS ) P (+ NS ) = = P(+ EKG | + NS ) P(+ NS ) + P (+ EKG | − NS ) P(− NS ) P(+ EKG | + NS ) P(+ NS ) = P(+ EKG | + NS ) P(+ NS ) + [1 − P(− EKG | − NS )][1 − P(+ NS )] 0,9 ⋅ 0,1 2 = = 0,67 = 0,9 ⋅ 0,1 + [1 − 0,95]⋅ [1 − 0,1] 3

P(+ NS + EKG ) =

Odpov : 2/3 lidí s bolestmi na hrudi, kterým se nam ilo pozitivní EKG, má ve skute nosti nemocné srdce. (Tzn., že 1/3 lidí s bolestmi na hrudi a pozitivním EKG má srdce zdravé.)

8.1.2 Bayes v teorém v ES 8.1.2.1 Šance Šance 2/3 : 1/3 = 2 : 1 odpovídá tedy pravd podobnosti ≈ 0,67 ≈ 2/3. Šance, že má pacient nemocné srdce za p edpokladu, že EKG je pozitivní, je tedy 2. Šance jevu H - apriorní O(H) ↔ P(H) - aposteriorní O(H|E) (za podmínky E) ↔ P(H|E)


Strana 39

P( H ) P( H ) = P( H ) 1 − P( H )

apriorní šance:

O( H ) =

aposteriorní šance:

O( H | E ) =

O ∈ 0, ∞ )

ZSY

P( H | E ) P( H | E ) = P( H | E ) 1 − P ( H | E )

V ta: P( H ) =

O( H ) 1 + O( H )

P 1 = 1 − P 1 / P −1 1 1 = −1 O P 1 O P= = 1+1/ O 1+ O

D kaz: O =

P íklad: Spo ítejte apriorní a aposteriorní šanci k P(+NS) a P(+NS|+EKG). 1 O(+NS) = 9 2 O(+NS|+EKG) = =2 1 8.1.2.2 Míra posta itelnosti a míra nezbytnosti Míra posta itelnosti (likelihood of sufficiency) LS: O( H | E ) = LS ⋅ O ( H ) Míra nezbytnosti (likelihood of neccesity) LN: O( H | E ) = LN ⋅ O( H )

LS =

O( H | E ) O( H )

LN =

O( H | E ) O( H )

Když E → H s velkou pravd podobností, pak LS↑ (LS → ∞) Když E → H s malou pravd podobností, pak LN↓ (LN →0) Tj. je-li LS↑∞, je O(H|E) ↑ bez ohledu na O(H), E je tedy posta itelné pro H je-li LN↓0, je O(H| E ) ↓ bez ohledu na O(H), sta í tedy, aby platilo E , a pak H neplatí. Aby tedy H mohla platit, musí platit (E) => musí platit E. E je tedy nezbytné pro to, aby H mohla platit.


Strana 40

ZSY

V ta:

LS =

P( E | H ) P( E | H )

LN =

P( E | H ) P( E | H )

D kaz:

P( H | E ) O( H | E ) P( H | E ) P( H | E ) P( H ) P ( E | H ) P ( H ) P( H ) P ( E ) P( E | H ) LS = = = = = P( H ) O( H ) P( H ) P( H | E ) P( E ) P( H ) P( E | H ) P( H ) P( E | H ) P( H ) LN … obdobn zám nou E za E Tabulka: E→H

O( H | E ) = LS ⋅ O ( H )

O( H | E ) = LN ⋅ O( H )

! zapamatuj si !

LS 0 1 ∞

LN ∞ E je posta itelné pro H E je nezbytné pro H E ani E nemá žádný vliv na H 1 E ani E nemá žádný vliv na H E je posta itelné pro H 0 E je nezbytné pro H

Platí: LS > 1 ⇔ LN < 1 LS = 1 ⇔ LN = 1 LS < 1 ⇔ LN > 1 Nebo platí:

LN =

1 − LS ⋅ P( E | H ) 1 − P( E | H )

D kaz plyne z p edchozí v ty Toto však platí jen teoreticky. Praktickým požadavkem totiž je, že expert ke každému pravidlu zadává též LS i LN a apriorní pravd podobnosti, které ale nemusí spl ovat uvedený vztah (nap . zadá-li LN = 2, LS = 1).

8.1.3 Použití Bayesova teorému v PROSPECTORu V inferen ní síti jsou ke každému p echodu z uzlu do uzlu (tj. ke každému pravidlu) p i azeny vztahy pro výpo et pravd podobnosti faktu odpovídajícího uzlu, do kterého se p ejde. P itom se použije pravd podobnost faktu odpovídajícího výchozího uzlu. E H e

e e P( H | e) = ? = f [P( H | E ), P( H | E ), P( E | e)] = vstup do vztahu, vyplývá bu z p edchozího pravidla anebo je musí být dáno ke zadáno uživatelem (v p ípad listu), každému pravidlu již p i pak e p edstavuje uživatelovu indicii konstrukci BZ expertem (víru v to, že platí E)


Strana 41

ZSY

(8.1.1): P( H | e) = P ( H | E , e) P ( E | e) + P( H | E , e) P( E | e)

.

= P ( H | E ) P ( E | e) + P ( H | E ) P ( E | e) 1. aproximace expert p edchozí expert p edchozí PROSPECTORu pravidlo i uživatel

pravidlo i uživatel

V inferen ní síti pak dochází k postupné propagaci

E e

?

H

H

E

E

?

?

H

P ( H | e) = f ( P ( E | e) ) P ( Hˆ | e) = fˆ ( P( Eˆ | e)) = ˆ ˆ ˆ P ( Hˆ | e) = fˆ ( P( Eˆ | e)) =

fˆ ( f (P( E | e) )) ˆ ˆ fˆ fˆ P( Eˆ | e) = fˆ fˆ( f (P( E | e) ))

((

… Protože je pro experta obtížné ur it P( H | E ) a P( H | E ) pro všechny p ípady E, tj. Obecné rozd lení: P(H|E) P(H|E)

)) (

E E Speciáln pro jev E nabývající pouze 2 hodnot (hod korunou) by m l expert zadat 2 ísla P ( H | E ) a

P( H | E ) . Expert ale zadává místo P ( H | E ) a P( H | E ) LS a LN (a protože ty nesta í na ur ení P( H | E ) a P( H | E ) (je pot eba znalosti P(H)), též zadává P(E) a P(H)). (P(E) z d vodu z et zení pravidel) Ur ení P ( H | E ) a P( H | E ) z LS, LN pak provedeme následovn : V ta:

P( H | E ) = Pak: P( H | E ) = P( H | E ) =

O( H | E ) 1 + O( H | E )

LS ⋅ O( H ) LS ⋅ P( H ) /[1 − P( H )] = 1 + LS ⋅ O ( H ) 1 + LS ⋅ P( H ) /[1 − P( H )]

LN ⋅ O( H ) LN ⋅ P( H ) / [1 − P( H )] = 1 + LN ⋅ O ( H ) 1 + LN ⋅ P( H ) /[1 − P( H )]

O ( H | E ) = LS ⋅ O ( H )

O ( H | E ) = LN ⋅ O( H )

ˆ ) dalšího Zadávání P(E) pak plyne z faktu, že vlivem et zení zadáním P(H) zárove zadáváme P(E pravidla, atd. Problém je, že nahrazujeme P(H|E) → LS, LN a ty jsou navzájem obecn nekonzistentní (⇐ expert zadává nap . LS = 1, LN < 1) Pro p ípad P(H|E) na LS, LN a obrácen pot ebujeme ješt znát P(H), P(E) – zadává expert Expert zadává: P(H), P(E), LS, LN 3 body na p ímce f(H|e) = f(P(E|e)) f obecn není p ímka Proto upravíme rovnici 8.1.1: P(H|e) 1 P(H)

[P(E);P(H)]

[1;P(H|E)] ←plyne z 1.aproximace prospectoru

[0;P(H|E )] 0

P(E)

1 P(E|e)

)


Strana 42

… 2. aproximace PROSPECTORu pramenící z p eur enosti údaj o neur itosti zadávaných expertem

8.1.1 → 8.1.2: (8.1.2): Pro P( E | e) ∈ 0; P( E )

rovnice propagace e

E

H

=x

P ( E | e) [P( H ) − P( H | E )] P ( H | e) = P ( H | E ) + P ( E ) y =a =b

H

Pro

P( E | e) ∈ P( E );1

=x-x0

P ( H | e) = P ( H ) +

P ( E | e) − P ( E ) [P( H | E ) − P( H )] 1 − P( E ) expert

y

=a

=b

1. heuristika PROSPECTORu: (8.1.3): Pravidla s logicky vázanými p edpoklady: H IF E1 AND E2 … THEN H IF E1 OR E2 … THEN H E1

E2

e

P ( E | e) =

min AND {P( Ei | e)} pro max OR

2. heuristika PROSPECTORu: (8.1.4): Kombinace pravidel O(H|e1, e2, …,en) ↔ P(H|e1, e2, …,en) H e1

e2

O ( H | e1 , e2 ,..., en ) =

∏ LE i =1

i

O( H ) , kde LEi =

O( H | ei ) je efektivní pom r O( H )

O( H | ei ) P (ei | H ) = O( H ) P(ei | H )

LEi = D kaz:

P( H |e i ) P( H |ei ) P( H ) O( H ) = P( H ) P( H |e i ) P( H ) P(ei ) P( H ,e i ) P( H ) P (e i | H ) LE i = : = = P( H |ei ) P( H ) P(ei ) P( H ) P( H ,e i ) P(ei | H )

H O( H |e i ) =

E e

n

P(E|e)

(8.1.5): Míra ur itosti: Pro P ( E | e) > P ( E ) : slouží k zadávání P(E|e) od P ( E | e) − P ( E ) uživatele (pro uživatele) C ( E | e) = 5 1 − P( E ) v p ijatelné form Pro P ( E | e) ≤ P ( E ) :

C ( E | e) = 5

P ( E | e) − P ( E ) P( E )

ZSY


Strana 43

C(E|e) 5 0 -5

P(E) 1 P(E|e) Místo P(E|e) se udává C(E|e) ∈ -5, 5 P(E|e) = ? f(C(E|e)) (8.1.6): Pro C(E|e) > 0 : 1 P( E | e) = C ( E | e) (1 − P( E ) ) + P( E ) 5 Pro C(E|e) ≤ 0 : 1 P ( E | e) = C ( E | e) P ( E ) + P ( E ) 5 0

ecelk = e1 ∧ e2 ∧

∧ en

Pro P(H|ecelk) > P(H) : P( H | ecelk ) − P( H ) C ( H | ecelk ) = 5 1 − P( H ) Pro P(H|ecelk) ≤ P(H) : P( H | ecelk ) − P( H ) C ( H | ecelk ) = 5 P( H ) C(H|ecelk) 5 0 -5

0

P(E)=P(H)

1 P(H|ecelk) O( H | ecelk ) O ( H | e1 , e2 ,..., en ) P( H | ecelk ) = = 1 + O ( H | ecelk ) 1 + O( H | e1 , e2 ,..., en )

P(H)

ZSY


Strana 44

ZSY

P íklad:

P(Ei) = 0.1, pro ∀i P(H1) = 0.1

H1 nekup OR E2 vysoká cena

E1 špatný stav

AND

1

E3 najeto >150000km

E4 jezdilo ve m st

5

5 LS6 LN6 [1000 , 0.001]

ešení: (Z ): H 1, C(H 1 | ecelkové )

E5 špatná karoserie

E6 poma kaná

E7 rezavá

4

-1

LS7 LN7 [ 100 , 1 ]

ecelkové = {e1 , e2 } = {e3 , e4 , e5 , e2 } = {e3 , e4 , e6 , e7 , e2 , } Co jsou to ei ? , i = 1,2,

,7

C ( Ei | ei ) …míra ur itosti tvrzení Ei , za p edpokladu, že platí indicie ei Nap :

C ( E 2 | e2 ) = 1 , protože nap . auto stojí 105 000,- K

a je to Peugeot 205

E 2 =↑ cena

e2

1.

E1 OR E2 → H1, LS1 = ∞, LN1 = 0 LS 2 = ∞, LN 2 = 0 P(H1) H1

LS1,LN1 P(E1)

OR

E1

LS2,LN2 P(E2) e1

E2

(1) C ( H 1 | e1 , e2 ) = ? (2) H1 propagace OR Ek

e2 P( H 1 | e1 , e2 ) = ? dle 8.1.5

↑ P ( H 1)

P( H 1 | e1 , e2 ) = f (P( E1 | e1 ), P( E 2 | e2 ),

(

)

dle 8.1.2 = f P( Ek | ek ), P( H 1), P( Ek ), P( H 1 | Ek ), P( H1 | Ek ) dle 8.1.3 P( Ek | ek ) = max(P ( E1 | e1 ), P ( E 2 | e2 ) ) (3)

(4) P ( H1 | Ek ) =

k ∈ {1,2}

O ( H 1 | Ek ) LS k ⋅ O ( H1 ) = 1 + O ( H1 | Ek ) 1 + LS k ⋅ O( H1 )

)


Strana 45

P( H1 ) 1 − P( H1 ) = P ( H1 ) 1 + LS k ⋅ 1 − P( H1 ) LS k ⋅

ZSY

k ∈ {1,2}

P( H1 ) 1 − P ( H1 ) (5) P ( H1 | Ek ) = P ( H1 ) 1 + LN k ⋅ 1 − P( H1 ) LN k ⋅

k ∈ {1,2}

P( E1 | e1 ) = ?

P( E 2 | e2 ) = ?

E2

P(E1) E1

LS3, LN3

AND

LS5, LN5

LS4 LN 4 P(E3) E3

P(E4) E4

e3

P(E5) E5 e5

e4

2. E3 AND E4 AND E5 → E1, LS3 = ∞, LN 3 = 0 LS 4 = ∞, LN 4 = 0 LS5 = ∞, LN 5 = 0

(6)

P( E1 | e1 ) = f (P( E 3 | e3 ), P( E 4 | e4 ), P( E 5 | e5 )

(

)

dle 8.1.2 = f P( Em | em ), P( E1), P( Em ), P( E1 | Em ), P( E1 | Em )

E1 propagace AND

)

m ∈ {3,4,5}

Em

dle 8.1.3 (7) P( Em | em ) = min (P( E 3 | e3 ), P( E 4 | e4 ), P( E 5 | e5 ) )

P( E1) 1 − P( E1) (8) P( E1 | Em ) = P( E1) 1 + LS m 1 − P( E1) LS m ⋅

P( E1) 1 − P( E1) (9) P ( E1 | Em ) = P ( E1) 1 + LN m 1 − P ( E1) LN m ⋅

P( E 3 | e3 ) = ?

P( E 4 | e4 ) = ?

E3

E4

(zadá uživatel)

P( E 5 | e5 ) = ? E5

E6

E7


Strana 46

E6 → E5, LS 6 = 1000 , LN 6 = 0,001 E7 → E5, LS 7 = 100 , LN 7 = 1 (10) P( E 5 | e5 ) = f (P( E 5 | e6 ), P( E 5 | e7 ),

ZSY

3.

)

e6 , e7

Rov. 8.1.4. (komb. pravidel) používá O, ne P

=

O( E 5 | e6 , e7 ) , kde 1 + O ( E 5 | e6 , e7 )

dle 8.1.4 (11) O( E 5 | e6 , e7 ) =

O ( E 5 | e6 ) =

O ( E 5 | e6 ) O ( E 5 | e7 ) ⋅ ⋅ O( E 5) , kde O( E 5) O ( E 5)

P( E 5 | e6 ) P( E 5) P( E 5 | e7 ) , O( E 5) = , O( E 5 | e7 ) = 1 − P( E 5 | e6 ) 1 − P( E 5) 1 − P( E 5 | e7 )

E5 kombinace!

E6

P(E5 P(E5,ee66)

E5(6)

E5(7) P(E5,ee77) P(E5

8.1.2

8.1.2 propagace E6

E7

E7 E5

Nelze u kombinace (jde jen u OR, AND)

(

El,l∈(6,7)

(12) P( E 5 | e6 ) = f P( E 6 | e6 ), P( E 5), P( E 6), P( E 5 | E 6), P( E 5 | E 6) Dle 8.1.2

)

LS 6 ⋅ P( E 5) 1 − P( E 5) (13) P ( E 5 | E 6) = LS ⋅ P( E 5) 1+ 6 1 − P( E 5)

E5 propagace

LN 7 ⋅ P ( E 5) 1 − P( E 5) (14) P ( E 5 | E 6) = LN 7 ⋅ P( E 5) 1+ 1 − P ( E 5)

E6

P( E 6 | e6 ) = ? E6 (15) P( E 5 | e7 ) = f P ( E 7 | e7 ), P( E 5), P( E 7), P( E 5 | E 7), P ( E 5 | E 7)

(

Dle 8.1.2

E5 propagace E7

LS 7 ⋅ P( E 5) 1 − P ( E 5) (16) P ( E 5 | E 7) = LS ⋅ P( E 5) 1+ 7 1 − P( E 5) LN 7 ⋅ P( E 5) 1 − P ( E 5) (17) P ( E 5 | E 7) = LN 7 ⋅ P ( E 5) 1+ 1 − P( E 5)

)


Strana 47

ZSY

P( E 7 | e7 ) = ? E7

Zbývá ur it: P( E 2 | e2 ) , P( E 3 | e3 ) , P( E 4 | e4 ) , P( E 6 | e6 ) , P( E 7 | e7 ) Dle 8.1.6 C ( E 2 | e2 ) , C ( E 3 | e3 ) , C ( E 4 | e4 ) , C ( E 6 | e6 ) , C ( E 7 | e7 ) P(E 2) P(E 3) P(E 4) P(E 6) P(E 7) Numerický výpo et: (Od list ke ko enu)

P( E 2 | e2 ) = C ( E 2 | e2 ) ⋅ C(Ei|ei)>0

C(E7|e7)<0

1

1 (1 − P( E 2) ) + P( E 2) = 0,28 5 0,9 0,1

P( E 3 | e3 ) =

5

0,9

0,1

=

1

P( E 4 | e4 ) =

5

0,9

0,1

=

1

P ( E 6 | e6 ) =

4

0,9

0,1

= 0,82

P( E 7 | e7 ) = C ( E 7 | e7 ) −1

⋅

1 (P ( E 7 ) ) 5 0,1

+ P( E 7) = 0,08 0,1

(18) P( E 5 | E7 ) nepo ítám, nebo P( E 7 | e7 ) < P( E7 ) nepot ebuji LS7 0,08 0,1 0,1 1⋅ 0,9 (17) P( E 5 | E 7) = = 0,1 0,1 1 + 1⋅ E5 0,9 8.1.2: P ( E 7 | e7 ) (15) P( E 5 | e7 ) = P( E 5 | E 7) + ⋅ P( E 5) − P ( E 5 | E 7) = 0,1 P ( E 7) 0 E7 0,1 1000 ⋅ 1000 0,9 (13) P( E 5 | E 6) = = = 0,9911 0,1 1009 1 + 1000 ⋅ 0,9

(

)

(14) P( E 5 | E 6) nepo ítám, nebo P( E 6 | e6 ) > P ( E 6)

E5

nepot ebuji LN6

8.1.2: P( E 6 | e6 ) − P ( E 6) 0,82 − 0,1 (12) P( E 5 | e6 ) = P ( E 5) + ⋅ (P( E 5 | E 6) − P( E 5) ) = 0,1 + ⋅ (0,9911 − 0,1) 1 − P ( E 6) 1 − 0,1

= 0,8129

E6

0,8129 0,1 1 − 0,1 ⋅ ⋅ = 4,3447 1 − 0,8129 1 − 0,1 0,1 4,3447 (10) P( E 5 | e5 ) = = 0,8129 1 + 4,3447 (7) min( P ( E 3 | e3 ), P( E 4 | e4 ), P ( E 5 | e5 )) = 0,8129 = P( Em | em ) (11) O ( E 5 | e6 , e7 ) =

E5

E6

↓ m=5

E7


Strana 48

P( E1 | E 5) = (8) P( E1 | E 5) =

"∞" LS = =1 1 + LS ∞

ZSY

(zde totiž LS → )

0 = 0 , ale nemusíme po ítat, P ( E 5 | e5 ) > P ( E 5) 1+ 0

(6) P( E1 | e1 ) = P ( E 5 | e5 ) = 0,8129 U deterministických pravidel se stejnou apriorní pravd podobností se „p enese“ aposteriorní pravd podobnost p edpokladu do záv ru. E1

(3) max(P ( E1 | e1 ), P ( E 2 | e2 ) ) = P ( E1 | e1 ) = 0,8129

k =1

(5) P( H 1 | E1) = 0 (4) P ( H 1 | E1) = 1 (2) P( H 1 | e1 , e2 ) = P( E k | ek ) = P ( E1 | e1 ) = 0,8127 U deterministických pravidel se stejnou apriorní pravd podobností se pravd podobnost p edpokladu „p enese“ do záv ru. P ( E1 | e1 ) − P ( E1) 0,8127 − 0,1 H1 (1) C ( H 1 | e1, e2) = 5 ⋅ = 5⋅ = 3,96 1 − P ( E1) 0,9 OR

P ( E1 | e1 ) > P ( E1) E1 E2 Odpov : Nekup (auto) s mírou ur itosti 3,96 ≈ 4.

Ušet it po ítání lze nejen u deterministických pravidel se stejnou apriorní pravd podobností p edpokladu a záv ru, ale dále též i: Jsou-li apriorní pravd podobnosti díl ích p edpoklad pravidla s logickými spojkami stejné, lze minimalizovat (maximalizovat) místo P(Ei|ei) C(Ei|ei) a naopak. p íklad r zných P ( E1) P ( E 2) , kdy tvrzení neplatí

C ( E1 | e) > C ( E 2 | e) ∧ P ( E1 | e) < P ( E 2 | e)

8.1.4 Zhodnocení Bayesova p ístupu Nevýhody: 1. Musí se znát p edem apriorní pravd podobnosti P(Ei) (musí zadat expert) 2. Musí platit P( H | E ) + P( H | E ) = 1 3. P edpokládá se nezávislost p edpoklad v pravidle tvaru: IF E1 AND E2 AND E3 THEN H Proto je t eba snažit se o co nejmenší po et AND v pravidle. 4. Když uživatel zadá P(E|e) musí se p epo ítat sí O(E|e) výpo etní náro nost


Strana 49

8.2 TEORIE UR ITOSTI (MYCIN, EMYCIN) MB … míra d v ry – relativní p ír stek pravd podobnosti H uplatn ním pravidla MD … míra ned v ry – relativní úbytek pravd podobnosti H CF … initel jistoty, faktor jistoty ∈ -1; +1 = CF

8.2.1 =1 MB(H, E ) =

=

P(H) = 1

P(H | E) − P(H) 1 − P(H)

=0

P(H | E) ≤ P(H)

=1 MD(H, E) =

=

P(H | E) > P(H)

P( H ) = 0

P(H) − P(H | E) P(H)

=0

P( H | E ) < P( H ) P( H | E ) ≥ P( H )

CF(H, E) = MB(H, E) − MD(H, E) ↑ MYCIN

CF ( H , E ) =

MB( H , E ) − MD( H , E ) 1 − min( MB, MD)

↑ EMYCIN

P íklady: A. E zcela podporuje H (E je posta itelné pro H): P(H|E) = 1 P(H | E) = 1 MB(H,E) = 1, MD(H,E) = 0, CF(H,E) = 1 B. E zcela vyvrací H (E je posta itelné pro H ); P( H | E) = 1

P(H | E) = 1 , tj. P(H|E) = 0

MB(H,E) = 0, MD(H,E) = 1, CF(H,E) = -1

C. E nijak neovliv uje H; P(H) ∈(0,1) : P(H|E) = P(H) P(H|E) = P(H) MB(H,E) = 0, MD(H,E) = 0, CF(H,E) = 0 D. E podporuje H; P(H) < P(H|E) < 1 P(H) < P(H|E) < 1

MB =

P(H | E) − P(H) ; MD(H,E) = 0, CF(H,E) = MB(H,E) 1 − P(H)

E. E vyvrací H; 0 < P(H|E) < P(H) 0 < P(H|E) < P(H)

MB(H,E) = 0; MD =

P(H) − P(H | E) , CF(H,E) = - MD(H,E) P(H)

ZSY


Strana 50

ZSY

F. Více Ei podporuje a jedna Ej vyvrací H E1, E2, …, En, n↑ MB(H, E1, E2, …, En) → 0,9999 MD(H, En+1) = 0,8 (nap .) dle MYCIN CF = MB – MD = 0,1999 p estože podporujících Ei >> vyvracejících Ei dle EMYCIN CF = 0,995

Pravd podobnost pro a proti V pravd podobnosti P platí P(H | E) + P(H | E) = 1 . Jak je tomu u CF? MYCIN CF(H, E) = MB(H, E) − MD(H, E) P(H) − P(H | E) , je-li P(H | E) < P(H ) CF(H, E) = 0 − P(H)

⇔ 1-P(H|E) < 1-P(H) ⇔ P(H|E) > P(H)

CF(H, E) = MB(H, E) − MD(H, E) P(H | E) − P(H) , je-li P(H|E) > P(H) CF(H, E) = 1 − P(H) − 1 + P(H) + 1 − P(H | E) + P(H | E) − P(H) CF(H, E) + CF(H, E) = =0 1 − P(H) CF(H, E) = −CF(H, E) Je-li P(H | E) ≥ P( H )

analogicky

Tedy CF(H, E) = −CF(H, E) (vždy) Podmín ný initel jistoty CF(H,E):

P íklad: P(H1) = 0,7 > P(H2) = 0,2 P(H1|E) = 0,9 > P(H2|E) = 0,8

CF ( H 1 , E ) =

0,9 − 0,7 0,2 2 = = = 1 − 0,7 0,3 3

CF ( H 2 , E ) =

= 0,666 < (není to jako u pravd podobnosti)

0,8 − 0,2 0,6 3 = = 1 − 0,2 0,8 4

= 0,750

8.2.2 Propagace e→E→H

CF(H,e) = CF(H,E).CF(E,e)

8.2.3 Logické spojky CF(H,E1 AND E2) = min(CF(H,E1),CF(H,E2)) OR max CF(H, E) = −CF(H, E) / heuristika – neplatí p esn z def. CF

8.2.4 Kombinace pravidel CFCOMBINE (CF1 , CF2 ) =

= CF1 + CF2 − CF1.CF2 CF1 + CF2 = 1 − min( CF1 , CF2 ) = CF1 + CF2 + CF1.CF2

CF1 > 0, CF2 > 0 CF1.CF2 < 0 CF1 < 0, CF2 < 0


Strana 51

ZSY

Platí komutativnost, tj. (CFCOMBINE(CF1,CF2) = CFCOMBINE(CF2,CF1)) Vztahy 8.2.2, 8.2.3, 8.2.4 platí pro CF definovaný pro EMYCIN.

P íklad:

H

1 0,7

E1 AND

0,2 0 ….prakticky nesmyslné, aby to expert takto zadal – tj.0 E2

E6

0.5

-0.4

Uživatel CFi =

e2 e6 E3

ešení: uživatel:

E4

E5

0.5

0.6

0.3

e3

e4

e5

CF(E3,e3) = 0,5 CF(E4,e4) = 0,6 CF(E5,e5) = 0,3 CF(E2,e2) = 0,5 CF(E6,e6) = -0,4

expert: CF(E1, E3, E4, E5) = 0,7 CF(H,E1) = 1 CF(H,E2) = 0,2 CF(H,E6) = 0

CF(H,e3, e4, e5, e2, e6) = ? →CF(H,e3, e4, e5, e2, e6) = CFCOMBNIE(CF(H, e3, e4, e5), CF(H,e2), CF(H,e6)) CF(H,e3, e4, e5) = CF(H,E1) CF(E1, e3, e4, e5) ↑ propagace ↓ propagace 8.2.2 CF(E1, e3, e4, e5) = CF(E1, E3, E4, E5) CF(E3, E4, E5, e3, e4, e5) logicky v.p. 8.2.3 → = CF(E1, E3, E4, E5) min{CF(E3,e3), CF(E4,e4), CF(E5,e5)} = 0,7 * 0,3 = 0,21 CF(H,e3, e4, e5) = 1*0,21 = 0,21 CF(H,e2) = CF(H,E2)* CF(E2,e2) = 0,2*0,5 = 0,1 ↑↓ propagace CF(H,e6) = CF(H,E6)* CF(E6,e2) = 0*(-0,4 ) = 0 (-0,4 nemá smysl zadávat) → CFCOMBINE(A,B,C) = CFCOMBINE (CFCOMBINE(A,B),C): CFCOMBINE(A,B)= CFCOMBINE(0.21,0.1)=0,289; CFCOMBINE(0.289,0)=0,289 CF(H,e3, e4, e5, e2, e6) = 0,289

Poznámky k teorii ur itosti 1. Více ei podporujících H; nap . bude pršet CFCOMBINE(CF1,CF2) = 0,8 + 0,8 – 0,8*0,8 = 0,96 CF1 = 0,8; CF2 = 0,8 CFCOMBINE(CF1,CF2,…,CFN) → 1 (N→∞) 1 je proti: CFN+1 = -0,8, pak CFCOMBINE(CF1,CF2,…,CFN) = (1-0,8)/(1-0,8) → 1 (proto je tu min) 2. Heuristické hledání Nap íklad: R1: IF A R2: IF D AND B THEN C2 THEN C1 CF = 0,7 CF = 0,8 Prioritu má pravidlo s vyšším CF , tj. R1 Kdyby CF(C1)< CF(C2), pak m žeme brát R2


3. 4.

5. 6. 7.

Strana 52

ZSY

ízené hledání pomocí CF Nap . IF CF (Problém je v elektrickém systému) < 0,5 THEN GOAL = Problém je v palivovém systému Pro ezávání p i hledání Nap .: pravidla s |CF(H|e)| < 0,2 nejsou dále uvažována ↑ obecn threshold MYCIN - uvažuje 0,2 problém p i pro ezávání (MYCIN má V p ípad hlubokého et zení CF(H,e) klesá s hloubkou ale malou hloubku) Problém, kdy jednu hypotézu vyvozuje mnoho p edpoklad . Nap . všichni v í, že bude pršet s 0,8 CF, ale systém uvažuje hodnotu CFCOMBINE = 1 vyhn me se použití mnoha pravidel vyvozujících tu samou hypotézu Problém pravidel s konjugovanými p edpoklady P íklad: IF Obloha je zatažená AND Vítr sílí AND Teplota klesá THEN Bude pršet CF 0,9

CF (Obloha je zatažená) = 1 CF(Vítr sílí) = 1 ? CF(Teplota klesá) = 0,1 CF(Bude pršet) = ? = 0,09 Záv r: Houby vím o tom, jestli bude pršet i nikoliv. Lépe: R1: IF Obloha je zatažená THEN Bude pršet CF 0,7 R2: IF Vítr sílí THEN Bude pršet CF 0,6 R3: IF Teplota klesá THEN Bude pršet CF 0,6 CF(Bude pršet) = ? CF1=1*0,7=0,7 CF2=1*0,6=0,6 CF3=0,1*0,6=0,06 CFCOMBINE(CF1 ,CF2)= 0,7 + 0,6 – 0,7 * 0,6 = 0,88 = CF12 CFCOMBINE(CF12 ,CF3)= 0,88 + 0,06 – 0,88 * 0,06 = 0,89 = CF ↑to je lepší, ale problém 6. z stává


Strana 53

ZSY

8.3 FUZZY LOGIKA V klasické teorii množin se zavádí tzv. charakteristická funkce: A

(x) =

1 0

jestliže jestliže

x∈A x∉A

Jedná se o zobrazení univerza X do množiny {0,1}: µA(x): X → {0,1}. Prvek tedy do množiny pat í nebo nepat í. V teorii fuzzy množin m že oproti tomu prvek do množiny pat it áste n . Stupe p íslušnosti prvku do fuzzy množiny je vyjad ován pomocí zobecn né charakteristické funkce nazývané funkce p íslušnosti. µA(x): X → 0,1 (do intervalu!) Stupe p íslušnosti prvku v množin se tedy pohybuje v rozmezí 0 ≤ µA ≤ 1, kde 0 znamená úplnou nep íslušnost a 1 úplnou p íslušnost prvku do fuzzy množiny A. Nap .: V klasické teorii množin m jme množinu vysokých lidí V a její dopln k malých lidí M = V =U-V U V M

300

H

0

cm

H… hodnota výšky v cm, d lící populaci na množiny V a M, nap . 165 cm. Je-li n kdo vysoký 163 cm, pat í do množiny malých; je-li vysoký 166cm, pat í do množiny vysokých. V M Fuzzy množiny V, M

300

N

0

cm

1

0 300 -

0 funkce p íslušnosti (subjektivní hodnocení) výšky do fuzzy množiny vysoký µV(x) funkce p íslušnosti výšky do fuzzy množiny malý µM(x)


Strana 54

ZSY

Poznámka: V teorii se asto používá tzv. S-funkce ( Π fce) S(x, α, β, γ) = 0 …x≤α

1 x −α = 2 β −α = 1−

2

…α≤x≤β 2

1 x −γ 2 γ −β

…β≤ x≤γ

S

…x≥γ

=1

Π analogicky Fuzzy logika := odv tví logiky, které užívá stupn p íslušnosti do množiny <0,1> místo striktní ANO/NE p íslušnosti Lingvistická prom nná := pojem užívaný v našem p irozeném jazyce k popisu v cí (objekt a jejich vlastností), které mají vágní (rozptýlené, neur ité) hodnoty Fuzzy množina := množina charakterizovaná funkcí p íslušnosti µA(x), která p i azuje každému prvku X (z univerza) hodnotu z intervalu <0,1>. (Stupe p íslušnosti) Reprezentace fuzzy množin

= Jak vyjád it funkci p íslušnosti µA(x): pomocí S-funkce nebo v p ípad diskrétního souboru prvk pomocí kone né množiny prvk , kde každému prvku p i adíme hodnotu funkce p íslušnosti fuzzy množiny A = (a1, a2,…,an), kde ai = µA(xi). Píšeme pro p ehlednost ve tvaru: A = (a1/x1, a2/x2,…,an/xn) !takto nap .: vysoký = (0/160; 0,2/175; 0,5/185; 0,9/190; 1/200) Prvky fuzzy množiny, pro které platí µA(x) > 0, tvo í tzv. podporu (support) fuzzy množiny. α- ez = množina, jejíž prvky mají µ > α (α je zvolená konstanta). Kone ná fuzzy podmnožina o N prvcích je obvykle reprezentována jako sjednocení fuzzy množin o jednom prvku µi/xi:

A=

N i =1

i /x i =

N i =1

i

/x i

Pro spojitou funkci: A =

A

(x i )/x i

x

Operátory: • koncentrace (hodn ) = CON(A): •

•

roztažení (trochu) = DIL(A):

CON(A)

DIL(A)

intenzifikace (vskutku) = INT(A):

(X) = [

(X) =

INT(A)

[

A

(X) =

(x)]

2

A

(x)]

2[

0≤

A (x) ]

2

1 − 2[1 −

(x)]

2

A

•

mohutnost (hodn hodn ) = POW(A): µ POW ( A) ( X ) = [µ A ( x) ]

•

normalizace = NORM(A):

n

NORM(A)

(X) =

A

(x)/max{

A

(y)/y ∈ X }

1 ≤ 2

A

(x) ≤

A

1 2

(x) ≤ 1


•

Strana 55

ZSY

pr nik: A ∩ B: pro ∀x ∈ X

µA

B

= min{µ A ( x ), µ B ( x)} = µ A ( x) ∧ µ B ( x) = µ A ( x) ∩ µ B ( x)

nap .:

•

sjednocení: A ∪ B: pro ∀x ∈ X A∪B

• • •

vysoký = (0/160; 0,2/175; 0,5/185; 0,9/190; 1/200) nízký = (1/160; 0,5/175; 0,2/185; 0,1/190; 0/200) µ vysoký ∧ nízký (x) = (0/160; 0,2/175; 0,2/185; 0,1/190; 0/200)

= max{

A

(x),

=

A

(x) ∨

B

=

A

(x) ∪

B

B

(x)}

(x) (x)

dopln k A‘: µA‘(x) = 1 – µA(x) rovnost: A = B: µA(x) = µB(x) pro ∀x ∈ X inkluze: A ⊆ B: µA(x) ≤ µB(x) pro ∀x ∈ X A ⊂ B: µA(x) ≤ µB(x) a zárove alespo pro jedno x: µA(x) < µB(x)

Pro fuzzy množiny platí komutativnost, asociativnost; neplatí zákon protikladu a vylou ení t etího – tedy m že platit: A ∪ A‘ ≠ U A ∧ A‘ ≠ Ø

Odvození P 1: A: vysoký B: ne hodn vysoký: µB(x) = 1 – (µA(x))2 P 2: A: vysoký B: nízký C: ne velmi vysoký a ne velmi nízký: µC(x) = [1 – (µA(x))2] ∧ [1 – (µB(x))2] Fuzzy inference

Fuzzy výrok:

↓vysoká X je A, kde A je fuzzy množina, X univerzum ↑rychlost ↓nízký Y je B, kde B je fuzzy množina, Y univerzum ↑tlak

fuzzy pravidlo: IF X je A THEN Y je B Expertní systém uchovává pravidla: IF A THEN B jako asociaci (A,B) v matici M M zobrazuje fuzzy množinu A do fuzzy množiny B Nap .: IF výška je vysoká THEN váha je t žká A B X výška A – fuzzy množina vysoká výška Y váha B – fuzzy množina t žká váha A = (a1/x1, a2/x2, …, an/xn) B = (b1/y1, b2/y2, …, bm/ym) M =: A M = B


Strana 56

ZSY

Úkolem je ur it M z A a B. Budeme-li M znát, budeme um t ur it B+ z A+∩ M.

a 1 → b1 Obecn : M: a 2 → b1 .........

a 1 → b 2 ......... ............ ........... .........

Vzniklo n kolik operátor → 2 nejpoužívan jší jsou Max-min a Max-product inference.

Max-min inference: • M : mij := min (ai,bj)

pak B + : bj+ = max(1 ≤ i ≤ n) {min(ai+, mij)} operátor A +

Max-product inference: • M : mij := ai•bj

M

P íklad: IF teplota je normální THEN rychlost je st ední (A… teplota normální, B… rychlost st ední) A: (0/100; 0,5/125; 1/150; 0,5/175; 0/200) B: (0/10; 0,6/20; 1/30; 0,6/40; 0/50) IF A THEN B

M = mij = min (ai,bj)

min(0;0) min(0,5;0) = min(1;0) ...... ...... 0 0 0 0 0,5 0,5 = 0 0,6 1 0 0,5 0,5 0 0 0

min(0;0,6) min(0;1) min(0;0,6) min(0;0) min(0,5;0,6) min(0,5;1) min(0,5;0,6) min(0,5;0) ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... 0 0 0,5 0 0,6 0 0,5 0 0 0

Máme-li nyní A + = (0/100; 0,5/125; 0/150; 0/175; 0/200) Pak B + = bj+ = max{min(ai+, mij)} 1≤i≤n b1+ = max[min(0;0), min(0,5;0), min (0;0), min(0,0), min(0;0)] b2+ = max[min(0;0), min(0,5;0,5), min (0;0,6), min(0;0,5), min(0;0)] … B + = (0/10, 0,5/20, 0,5/30, 0,5/40; 0/50) odpov : V p ípad , že A + =(0/100; 0,5/125; 0/150; 0/175; 0/200) , je B+ = (0/10, 0,5/20, 0,5/30, 0,5/40; 0/50) V reálných situacích hodnota A+ je tvo ena jedním íslem (nap . zm ení t = 135°C = xSINGLE) Pro tento p ípad platí: B + = µ A ( x SINGLE ) ∧ µ B ( y ) ∀y: µ B + ( y ) = min( µ A+ ( xSINGLE ), µ B ( y )) +


Strana 57

ZSY

P íklad: µ A = 0,5 +

A = [min(0,5;0), min(0,5;0,6), min (0,5;1), min(0,5;0,6), min(0,5;0)] = (0; 0,5; 0,5; 0,5; 0) +

→

A

B B+

M = mij = …

+

A

Max product single value

∀y: µ B + ( y ) = ( µ A+ ( xSINGLE ) • µ B ( y ))

B+=µA+(xSINGLE) • µB(y)

A

B

B+

A+

N kolik p edpoklad v pravidle: IF A AND B THEN C M=? ešení: A MAC = C B A + MAC = C A

MBC = C (místo M uvažujeme MAC a MBC)

+

B

+

MBC = C B

+

Pak p i zadaném A , B + odvodíme C + : A+ ∧ B+ → C+ +

C + = [ A + MAC ] ∧ [ B + MBC ] = C A ∧ C B + +

A+∧B+→C+

IF A OR B THEN C ešení: - p i zadaném A + , B + získáme C + : A+ ∨ B+ → C+ C + = [ A + MAC ] ∨ [ B + MBC ] = C A ∨ C B +

+

A+∨B+→C+

Zjednodušení pro SINGLE VALUE A + , B + :

∧ ∧ ∧ min ∧ ( µA+ (xSINGLE) µC µB+ (xSINGLE) µC = µA+ ( xSINGLE), µB+ ( xSINGLE)) µC • ∨ • max •

min min min min min (a, c ), (b, c ) = (a, b ), c max • • • max

∧ pro A B+ ∨ +

Max−min → C+ Max−product


Strana 58

ZSY

N kolik pravidel: IF A1 THEN B1 IF A2 THEN B2 M1, M2, …, MN IF … … IF AN THEN BN

Pak p i zadaných A1+ , A2+ , …, AN+ 1. ur íme: B1+ , B2+ , …, B N+ 2.

B + = B1+ ∪ B2+ ∪…∪ B N+ = max( B1+ , B2+ , …, B N+ )

Defuzzyfikace Výsledkem je fuzzy množina nap .: normální rychlost = (a1/x1, a2/x2, …, an/xn). My ale chceme v d t, jaká je rychlost, tj. íslo. Procesu ur ení ísla z vektoru reprezentujícího fuzzy množinu, se íké defuzzyfikace. Nejvíce populární metodou je metoda fuzzy centroidu: N

x=

j =1 N

x j µ A (x j )

j =1

µ A (x j )

Architektura systému s fuzzy pravidly:

A+

A1 → B1

B1+

A2 → B2

B2+

Σ

B+

defuzzyfikace

X výsledek íslo

AN→ BN

BN+

Takovýchto blok m že být více s delšími v tvemi pravidel.


Strana 59

P íklad: IF teplota je normální OR tlak je nízký THEN rychlost je st ední

t

ZSY

IF teplota je normální AND tlak je normální THEN rychlost je nízká p

v Max(T,P)

IF t = normální OR p = ↓ THEN v = st ední

norm.

nízký

st ední

tení

IF t = normální AND p = normální THEN v = ↓

norm.

Max-Min inference

norm.

nam it

nízká

P

v = t žišt

t

p

v Max(T,P)

IF t = normální OR p = ↓ THEN v = st ední

norm.

nízký

st ední

tení

Max-product inference Min(T,P)

IF t = normální AND p = normální THEN v = ↓

norm.

norm.

nízká

v = t žišt


Strana 60

ZSY

8.4 DEMPSTER – SHAFEROVA TEORIE Dempster – Shaferova teorie je založena na myšlence modelování neur itosti místo jedním íslem ur itým intervalem „pravd podobnosti“. Celá teorie je vybudována na velmi dobrém teoretickém základ a bylo prokázáno, že faktory jistoty jsou speciálním p ípadem Dempster – Shaferovy teorie. Uvažujme množinu Θ vzájemn nezávislých prvk . Nap .: Θ = {dopravní letadlo, bombardér, stíha ka} Θ = { ervená, zelená, modrá, oranžová, žlutá} Θ = {Θ1, Θ2,…, ΘN} Odpov na otázku: „Jaká jsou vojenská letadla?“ potom reprezentuje podmnožina Θ: {Θ2, Θ3} = {bombarder, stíha ka}={B,S} Obdobn na otázku: „Jaká jsou civilní letadla?“ získáme odpov : {Θ1} = {dopravní letadla}={D} Každá podmnožina množiny Θ tedy p edstavuje možnou odpov na n jakou otázku z oblasti, o kterou se zajímáme. Za p edpokladu, že prvky množiny Θ jsou nezávislé a množina Θ „pokrývá oblast“ našeho zájmu, potom na otázku z p íslušné oblasti existuje pouze jedna správná odpov . Množina Θ o celkem N prvcích má celkem 2N podmnožin, které odpovídají všem možným odpov dím. Množinu všech podmnožin množiny Θ ozna me P(Θ), což je tzv. poten ní množina. V Dempster – Shaferov teorii se s mírou d v ry pracuje analogicky jako s hmotností fyzikálního objektu. Nenulová váha je p i azována pouze t m prvk m v množin P(Θ), kterým je vyjad ována d v ra. Jakákoliv jiná d v ra, která není p i azena ur itému prvku z P(Θ), je vzhledem k tomuto prvku neutrální, tzn. že se nepovažuje za ned v ru. Uvažujme nap íklad, že vojenské za ízení na identifikaci p átelského i nep átelského letadla (IPN) vyšle k blížícímu se letounu radiovou zprávu. V p ípad , že se jedná o p átelský letoun, m l by tento letoun sd lit sv j identifika ní kód. Letoun, který neodpoví, je považován za nep átelský bombardér i stíha ku. Problém je však v tom, že se m že jednat i o p átelský letoun, který p esto nemusí odpov d t. D vodem m že být nap . chybné (poškozené) p ijímací za ízení, porucha ve vyslání signálu IPN aj. P edpokládejme nap íklad, že jestliže IPN nezíská od blížícího se letounu identifika ní kód, pak se s d v rou 0,7 jedná o nep átelský bombardér i stíha ku. Podmnožin {B, S} = {bombardér, stíha ka} množiny Θ je tedy p i azena váha: m1({B, S}) = 0,7 Zbytek d v ry je ponechán v množin Θ, jako neutrální d v ra, tj. m1(Θ) = 1 - 0,7 = 0,3 Hlavní rozdíl mezi Dempster – Shaferovou teorií a teorií pravd podobnsoti je v tom, že zatímco v teorii pravd podobnosti by platilo: P(nep ítel) = 0,7 P(p ítel) = 0,3; tak v Dempster – Shaferov teorii platí, že cíl je nep átelský minimáln s d v rou 0,7 a zbývající d v ra 0,3 je v ur itém nám dosud neznámém pom ru rozd lena mezi dodate nou d v ru (že se jedná o nep ítele) a v ned v ru.


Strana 61

ZSY

Takto zavedená váha má mnohem v tší volnost než pravd podobnost, jak je patrné z tabulky: Dempster – Shaferova teorie m(Θ) nemusí být rovno 1 je-li X ⊆ Y, nemusí být m(X) ≤ m(Y) nevyžaduje vztah mezi m(X) a m(X‘)

Teorie pravd podobnosti Σi P i = 1 P(X) ≤ P(Y) P(X) + P(X‘) = 1

Každá váha m že být formáln vyjád ena jako funkce, která zobrazuje každý prvek z P(Θ) do intervalu 0,1 : m: P(Θ) → 0,1 . P itom se dále definuje m(∅) = 0 a sou asn se vyžaduje, aby sou et všech vah p i azených všem možným podmnožinám množiny Θ, tj. sou et všech vah prvk množiny P(Θ) byl roven jedné: (1.11) m1 ( X ) =1. X ∈P ( Θ )

V našem p ípad skute n platí: m1 ( X ) = m({B,S}) + m(Θ) = 0,7 + 0,3 = 1. X ∈P ( Θ )

P edpokládejme nyní, že n jaké druhé za ízení pracující na odlišném principu identifikuje cíl jako nep átelský bombardér s vahou 0,9, tj. m2({B}) = 0,9 a m2(Θ)= 0,1 Tyto váhy mohou být kombinovány s p edchozími vahami: m1({B,S}) = 0,7 a m1(Θ)= 0,3 pomocí Dempsterova pravidla ve tvaru: mv(Z) = m1 ⊕ m2(Z) = m1 ( X )m2 (Y ) ,

(1.12)

X ∩Y = Z

kde sou et probíhá p es všechny prvky (množiny), jejichž pr nikem je Z. P i využití tohoto pravidla se p edpokládá, že kombinované d kazy (poznatky) jsou vzájemn nezávislé. Aplikací Dempsterova pravidla v našem p ípad obdržíme: mv({B}) = m1 ⊕ m2({B}) = m1({B,S}) m2({B}) + m1(Θ)m2({B}) = = 0,7*0,9 + 0,3*0,9 = 0,63 + 0,27 = 0,9 bombardér mv({B,S}) = m1 ⊕ m2({B,S}) = m1({B,S})m2({Θ}) = = 0,7*0,1 = 0,07 bombardér nebo stíha ka mv({Θ}) = m1 ⊕ m2(Θ) = m1(Θ) m2(Θ) = 0,3*0,1 = 0,03 zbývající d v ra a ned v ra mv({B}) reprezentuje výslednou váhu (míru d v ry), že cílem je práv nep átelský bombardér a nic jiného. Avšak váhy mv({B,S}) a mv({Θ}) obsahují ješt další informaci. Protože množiny {B,S} a Θ zahrnují také bombardér, m že ur itá ást jim odpovídajících vah ješt také p isp t ke zvýšení d v ry v bombardér, nejvíce však o 0,1 nebo sou et: mv({B,S}) + mv({Θ}) = 0,07 + 0,03 = 0,1. Míra d v ry v bombardér leží tedy v rozmezí od 0,9 do 1, tj. od minimální d v ry až po maximální p ijatelnou d v ru. Ozna me minimální jistou d v ru Bel a maximální ješt možnou d v ru Pls. Z ejm 0 ≤ Bel ≤ Pls ≤ 1.


Strana 62

Interpretace n kterých interval

ZSY

Bel, Pls je uvedena v tabulce:

Bel, Pls 1, 1 0, 0 0, 1 Bel, 1 , 0 < Bel < 1 0, Pls , 0 ≤ Pls < 1 Bel, Pls , 0 < Bel ≤ Pls < 1

Význam Absolutní pravdivost Absolutní nepravdivost Absolutní nejistota Tendence – podpora Tendence – odmítnutí Podpora i odmítnutí

Minimální jistá d v ra i podpora Bel je celková d v ra v množinu a její podmnožiny a je ur ena jako sou et vah p i azených této množin a jejím podmnožinám: (1.13) Bel(X) = m(Y) . Y⊆X

V našem p ípad je hodnota minimální jisté d v ry (podpory) Bel pro množinu {B,S} získaná na základ poznatku získaného od IPN: Bel1 ({B,S}) = m1({B,S}) + m1({B}) + m1({S}) = 0,7 + 0 + 0 = 0,7. Mezi hodnotou minimální jisté d v ry Bel a vahou je rozdíl v tom, že váha reprezentuje d v ru p i azenou práv množin a nikoliv i jejím podmnožinám. Platí mezi nimi následující vztah:

m(X) =

(−1)

X −Y

Bel(Y) ,

Y⊆X

kde X-Y udává kardinalitu, tj. po et prvk v množin X – Y. Protože je hodnota Bel ur ena pomocí vah vztahem (1.13), m že být i kombinace dvou podpor pro bombardér (funkcí d v ry) vyjád ena s pomocí vztahu (1.13): 1.13

1.1 3

0,7 * 0,9 + 0,3 * 0,9

Bel1 ⊕ Bel2 ({B}) = Belv({B}) = mv({B}) + mv({∅}) = m1⊕ m2({B}) + m1 ⊕ m2(Θ) = 0,90 + 0 = 0,90 nebo váha prázdné množiny je (definována) rovna nule. Celková podpora pro podmnožinu (bombardér, stíha ka) má již více podmnožin než v p edchozím p ípad a 1.13

1.13

Bel1 ⊕ Bel2 ({B,S}) = Belv({B,S})=: mv({B,S}) + mv({B}) + mv({S}) + mv({∅}) = 1.12

m1 ⊕ m2({B,S}) + m1 ⊕ m2(B) + m1 ⊕ m2({S}) = 0,07 + 0,90 + 0 = 0,97

(1.14)

Celková podpora pro celou množinu Θ Θ = {dopravní letadlo, stíha ka, bombardér} = {D,S,B} je ur ena výpo tem: Bel1 ⊕ Bel2 (Θ) = Belv({Θ}) = mv({Θ}) + mv({B,S}) + mv({B}) = m1 ⊕ m2(Θ) + m1 ⊕ m2({B,S}) + m1 ⊕ m2(B) = 0,03 + 0,07 + 0,90 =1 Množina Θ sice obsahuje podmnožiny {}, {D,B}, {D}, {D,S}, {S}, ale ty však mají nulovou váhu. Podmnožina Bel{Θ} = 1 je spln na v každém p ípad , tj. sou et všech vah p i azených množin Θ a všem jejím podmnožinám musí být vždy podle (1.11) roven jedné.


Strana 63

ZSY

Interval míry d v ry pro množinu Q ozna me EI(Q) = Bel, Pls Tento interval lze také vyjád it: EI(Q) = Bel(Q), 1- Bel(Q‘) . Je-li v našem p íklad Q = {B}, potom Q’ = {D,S} a Bel ({D,S}) = m1 ⊕ m2({D,S}) + m1 ⊕ m2({D}) + m1 ⊕ m2 ({S}) = 0 + 0 + 0 = 0 a skute n platí EI ({B})= 0,9; 1-0 = 0,9; 1 . Obdobn pro Q = {B,S} je Q‘ = {D} a potom z ejm : Bel({D}) = 0 Bel({B,S}) = 0,97 a tedy EI({B,S}) = 0,97; 1-0 = 0,97; 1 EI({D}) = 0; 0,03 . P ípustnost Pls(X) tudíž p edstavuje míru, do které zjišt né poznatky nesta í k odmítnutí X. m(Y ') . Z ejm : Pls(X) = 1 – Bel(X‘) = 1 − Y' ⊆X '

Pokra ujeme nyní dále v našem p íkladu a p edpokládejme, že t etí za ízení poskytne s p edchozími výsledky konfliktní poznatek, že se jedná o dopravní letadlo s mírou d v ry 0,95, tj.: m3({D}) = 0,95 a m3(Θ) = 0,05 Snadno odvodíme, že: m1 ⊕ m2 ⊕ m3({D}) = 0,0285 m1 ⊕ m2 ⊕ m3({B}) = 0,045 m1 ⊕ m2 ⊕ m3({B,S}) = 0,0035 m1 ⊕ m2 ⊕ m3(Θ) = 0,0015 m1 ⊕ m2 ⊕ m3(∅ ) = 0 (podle definice) Ostatní váhy pro zbývající podmnožiny jsou nulové. V tomto p ípad však zjistíme, že sou et vah je menší než jedna, nebo : m1 ⊕ m2 ⊕ m3(X) = 0,0285 + 0,045 + 0,0035 + 0,0015 = 0,0785. X ∈P ( Θ )

ešení tohoto problému je založeno na normalizaci prvk s nenulovou vahou, a to vyd lením každé váhy rozdílem 1 – K, kde K je definováno pro libovolné množiny X a Y vztahem: K= mi ( X )m j (Y ) i≠j X ∩Y = prázdná mn.

V našem p ípad (uvedeny jsou pouze kombinace dávající nenulový p ísp vek): K = m1 ⊕ m2 ({B})m3({D}) + m1 ⊕ m2 ({B,S})m3({D}) = = 0,9 * 0,95 + 0,07 * 0,95 = 0,9215 1 – K = 1 – 0,9215 = 0,0785 Po vyd lení získáme tyto normalizované hodnoty: m1 ⊕ m2 ⊕ m3({D}) = 0,363 m1 ⊕ m2 ⊕ m3({B}) = 0,573 m1 ⊕ m2 ⊕ m3({B,S}) = 0,045 m1 ⊕ m2 ⊕ m3(Θ) = 0,019


Strana 64

ZSY

Jeden d kaz ve prosp ch {D} = {dopravní letadlo} zna n zm nil d v ru v {B} = {bombardér}, jak se o ekávalo. Z ejm : Bel({B}‘) = Bel({D,S}) = m1 ⊕ m2 ⊕ m3({D,S}) + m1 ⊕ m2 ⊕ m3({D}) + m1 ⊕ m2 ⊕ m3({S}) = = 0 + 0,363 + 0 = 0,363 a interval míry d v ry pro bombardér EI({B}) = Bel({B}); 1 - Bel({B}‘) = 0,573; 0,637 . Díky t etímu poznatku, konfliktnímu s p edchozími, se podstatn bombardéru (jistá i maximáln možná d v ra).

snížila podpora i p ijatelnost

Obecná forma Dempsterova pravidla má tedy tvar:

m1 ⊕ m2 ( Z ) = kde

K=

X ∩Y = Z

m1 ( X )m 2 ( X ) 1− K

,

(1.15)

m ( X )m2 (Y ) .

1 X ∩Y = prázdná mn .

Hodnota K p itom nazna uje množství konfliktu v d kazu. Zatímco K = 0 odpovídá úplné kompatibilit ; K = 1 odpovídá úplnému rozporu. Ur itým problémem Dempster-Shaferovy teorie je normalizace, která m že vést až k výsledk m, které mohou být v rozporu s naším o ekáváním. P í ina tkví v tom, že normalizací je ignorována d v ra, že uvažovaný objekt v bec neexistuje.

P íklad: P edpokládejme dva léka e A a B, kte í mají následující d v ru v pacientovu nemoc: mA {zápal mozkových blan} = 0,99 mA {mozkový otok} = 0,01 mB {ot es mozku} = 0,99 mB {mozkový otok} = 0,01 Oba dva léka i sice p isuzují vhodn extrémn nízkou šanci 0,01 mozkovému otoku, ale zna n se liší v názoru na hlavní podstatu problému. Aplikací Dempsterova pravidla však dosp jeme k d v e v mozkový otok. Podle (1.15) totiž:

m1 ⊕ m2 ( Z ) =

0,01 * 0,01 =1 1 − (0,99 * 0,99 + 0,99 * 0,01 + 0,01 * 0,99)

(1.16)

(Z … mozkový otok) Tento výsledek odporuje naší intuici a navíc v bec nezávisí na ostatních vahách pro zápal mozkových blan i ot es mozku.


Strana 65

ZSY

9 INDUK NÍ SYSTÉMY Induk ní znalostní systém = systém, který z množiny p íklad (trénovacích dat) vyvodí množinu znalostí o datech Induk ní systém s pravidly = systém, který z množiny p íklad (trénovacích dat) vyvodí množinu pravidel platných pro data

P íklad: Jaký dárek? Peníze/fakta hodn hodn málo málo

V k / fakta dosp lý dít dosp lý dít

Dárek/Výsledek auto po íta topinkova kalkula ka

hodn

v k dosp lý

a

IF máme hodn pen z AND dárek je pro dosp lého THEN kupujeme auto ………

P íklad: P edpov teplota + – + + * + 0

po así vítr Z * V * * J S

obloha zataženo

barometr

výsledek déš

zataženo zataženo polojasno jasno jasno polojasno

→

sníh slunce slunce slunce déš sníh

→ → → teplota

vítr

obloha

výsledek

peníze

málo

v k dít

dosp lý

p

t

dít

k


Strana 66

ZSY

barometr

déš

obloha jasno

polojasno

slunce

teplota

slunce

No Data

slunce zataženo

sníh

sníh

Problém odvození množiny pravidel je p eveden na problém konstrukce rozhodovacího stromu (tj. chceme, aby rozhodovací strom m l co nejmenší v tvení malá množina pravidel)

CLS algoritmus C … množina p íklad Wi…t ídy výsledk 1. Když všechny p íklady jsou ze t ídy Wi, pak vytvo íme uzel Wi a konec. Jinak vybereme (užitím heuristiky) faktor Fj (vítr) s hodnotami Hj1, Hj2, …, HjNj a vytvo íme uzel s Fj. (tzv. hodnotící funkce) 2. Rozd líme množinu p íklad C do podt íd Cj1, Cj2, …, CjNj podle Fj a jeho hodnot. 3. Aplikujeme algoritmus rekurzivn na každou Cjk.

ID3 algoritmus 1. 2. 3. 4.

Vybereme náhodn podmnožinu z C (tzv. okno) Aplikuje CLS algoritmus Projde všechny p íklady z {C – (okno)} a najde výjimky Když existují výjimky, pak vybere n které z nich a p idá je do okna a jde na krok 2. Jinak konec a strom je hotov.

Hodnotící funkce m že mít tvar nap . entropie:

H=−

N i =1

p i log 2 p i

N … po et výsledných t íd Wi (nap . výsledek: déš , sníh, slunce; faktor: barometr)


Strana 67

ZSY

P íklad: P1 = P(výsledek = déš barometr )=1 )=0 P2 = P(výsledek = sníh barometr P3 = P(výsledek = slunce barometr )=0 H = -1*0 – 0*log0 – 0*log0 = 0 H … spo ítám i pro barometr H … spo ítám i pro barometr

H v = H výsledné =

n

H i P(barometr i)

i∈{

,

,

}

n … po et r zných hodnot faktoru

n=3, { , , } Spo ítám Hv i pro vítr, teplotu, oblohu a vyberu faktor, pro který Hv nabývá nejmenší hodnoty. 1.barometr (

,

,

N=3, {déš , sníh, slunce}

)

1.1 )=1 P1=P(déš P2=P(sníh )=0 P3=P(slunce )=0 H = 1*0 + 0*0 + 0*0 = 0 1.2 P1=P(déš )=0 )=0 P2=P(sníh )=1 P3=P(slunce H = 0 1.3 P1=P(déš )=0 ) = 1/2 P2=P(sníh P3=P(slunce ) = 1/2 H = 0 + (-log 2 (1/2)) = log 2 2 = 1 Hbarometr= H

* P(

) + H * P(

2.obloha (zat., pol., jasno) 2.1 P1=P(déš zat.) = 1/3 P2=P(sníh zat.) = 1/3 P3=P(slunce zat.) = 1/3 H zat.= log 2 3 = 1,58 2.2 P1=P(déš pol.) = 0 P2=P(sníh pol.) = 1/2 P3=P(slunce pol.) = 1/2 H pol.= log 2 2 = 1

) + H * P(

)=1*

4 4 = 7 7


Strana 68

2.3 P1=P(déš jasno) = 1/2 P2=P(sníh jasno) = 0 P3=P(slunce jasno) = 1/2 H jasno = 1 Hobloha = 1,58 *

3 2 2 4 +1* + 1* = 1,25 > 7 7 7 7

ZSY

ZNALOSTNÍ SYSTÉMY Doc. Ing. Ludk Müller, Ph.D

Recommend Documents