Expertní systémy Neurčitost – Dempster-Shaferova teorie Jan Górecki Název prezentace Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Logolink_OP_VVV_hor_barva_cz •Neurčitost je charakteristickým rysem složitých systémů. Vlastní povaha reality způsobuje, že poznatky, které z ní získáváme, jsou neurčité či vágní. – Neurčitost (opakování) csvukrs –problémy s daty; např.: •chybějící nebo nedostupná data •nespolehlivá data (např. z důvodu chyb měření) •nepřesná nebo nekonzistentní reprezentace dat Příčiny neurčitosti (opakování) csvukrs –nejisté znalosti; např.: •znalost nemusí být platná ve všech případech •znalost může obsahovat vágní pojmy. – Příčiny neurčitosti (opakování) csvukrs •Dempster-Shaferova teorie byla vyvinuta ve snaze o překonání některých nedostatků pravděpodobnostního přístupu, jako např. reprezentace neznalosti (ignorance) a požadavku, že součet měr důvěry v událost a její negaci musí být roven 1. Dempster-Shaferova teorie csvukrs •Zatímco pravděpodobnost představuje stupeň, ve kterém je tvrzení považováno za pravdivé, míra domnění v DS teorii představuje podporu tomuto tvrzení. Růst pravděpodobnosti hypotézy redukuje pravděpodobnost komplementu, kdežto v DS teorii růst podpory hypotézy nezpůsobuje změnu podpory komplementu. – Dempster-Shaferova teorie csvukrs •DS teorie je obecnější než bayesovský přístup, jelikož důvěra ve tvrzení a důvěra v negaci tohoto tvrzení nemusí být v součtu rovna 1. – Dempster-Shaferova teorie csvukrs •Prostředí: úplný systém vzájemně disjunktních základních hypotéz . •X = {h1, h2, … , hn} – Základní přiřazení csvukrs •Základní přiřazení (basic probability assignment, mass probability function) je funkce definovaná na množině všech podmnožin množiny X a nabývající hodnot z intervalu á0, 1ñ, tj. •m: 2X ® á0, 1ñ, • která má tyto vlastnosti: • m(Æ) = 0, – Základní přiřazení csvukrs •Hodnota m(A) představuje míru důvěry, že platí právě hypotéza A, přičemž nevypovídá nic o míře důvěry ve složky množiny A. Nemusí tedy platit m(B) £ m(A) pro B Í A. •Řekneme, že A je fokální element, jestliže m(A) > 0. – Základní přiřazení csvukrs –Míra domnění (measure of belief) v platnost hypotézy A je definována jako součet základních přiřazení všech podmnožin množiny A: – – Míra domnění csvukrs •Na rozdíl od základního přiřazení tedy Bel(A) vyjadřuje míru domnění v hypotézu A nebo v jakoukoli z jejích podmnožin. •Platí: •Bel(A) + Bel(Ac) £ 1, kde Ac = X – A, •Bel(A) £ Bel(B) pro A Í B, •Bel(X) = 1. Míra domnění csvukrs •Míra věrohodnosti (measure of plausibility) : •Pl(A) = 1– Bel(Ac) • Hodnota Pl(A) vyjadřuje míru chyby při zamítnutí A. • Platí: •Bel(A) £ Pl(A) •Pl(A) + Pl(Ac) ³ 1, •Pl(A) £ Pl(B) pro A Í B. – Míra věrohodnosti csvukrs á áBel(A), Pl(A) ñ • •Tento interval vyjadřuje rozsah naší jistoty o hypotéze A. Rozdíl Pl(A) – Bel(A) se nazývá nejistota o hypotéze A nebo ignorance. – Interval domnění csvukrs Intervaly domnění – – – – – – –Základní přiřazení m1 a m2 mohou pocházet od různých expertů, případně m1 může být výchozí základní přiřazení a m2 základní přiřazení získané na základě nových skutečností. – Kombinace základních přiřazení csvukrs –Jestliže pozorujeme B, pak se základní přiřazení, domnění a věrohodnost A mění takto: – – pro A ¹ Æ; m(Æ|B) = 0 – – – – – Změna domnění csvukrs –Počítač nepracuje správně. Možné příčiny jsou závada napájení (zn), závada na hlavní desce (zd), závada operační paměti (zp) nebo závada grafické karty (zg). Definujte rámec domnění. – Příklad 1 csvukrs –Odpověď: Uvedené příčiny tvoří množinu vzájemně disjunktních základních (atomických) hypotéz. Rámec domnění tedy je množina Θ = {zn, zd, zp, zg}. – Příklad 1 csvukrs Příklad 1 Množina hypotéz (potenční množina 2Θ) csvukrs •V DS teorie je každá podmnožina hypotéz z 2Θ považována za specifickou hypotézu, viz předešlý obrázek. Nedostatek domnění k jednotlivým hypotézám se nahrazuje domněním k celé množině všech hypotéz 2Θ, což nazýváme stav nejistoty. Příklad csvukrs –Míra domnění ke specifické hypotéze se v DS teorii označuje reálným číslem z intervalu <0, 1>. Toto číslo indikuje také stupeň, se kterým jsme přesvědčeni, že důkazy (evidence) podporují hypotézu. V DS teorii se důkaz proti specifické hypotéze považuje za důkaz pro její negaci (například důkaz proti {zn} je považován za důkaz pro {zd, zp, zg} a podle toho bude přiřazen stupeň domnění). – Příklad csvukrs –Domníváme se, že závada na počítači je způsobena napájením nebo chybou na hlavní desce ({zn, zd}). Naše přesvědčení vyjádříme stupněm 0,6 (existují určité indicie této závady, které ohodnotíme stupněm 0,6). Neexistuje žádný důkaz pro podporu výběru mezi závadou na hlavní desce a závadou napájení. Jaká jsou základní přiřazení bba? – Příklad 2 csvukrs –Odpověď: m({zn, zd}) = 0,6, a m(Θ) = m({zn, zd, zp, zg}) = = 1 – 0,6 = 0,4. – Příklad 2 csvukrs –Test vyvrátil, že by porucha počítače byla způsobena závadou na napájení, a to stupněm 0,7. Jaká jsou bba? – – Příklad 3 csvukrs –Odpověď: Důkaz proti závadě na napájení se považuje za důkaz pro negaci (zn). Tedy m({zd, zp, zg}) = 0,7 a m(Θ) = 0,3. – Příklad 3 csvukrs –Jaká je velikost Bel({zn, zd, zg})? – Příklad 4 csvukrs –Odpověď: Bel({zn, zd, zg}) = m({zn, zd, zg}) + m({zn, zd}) + + m({zn, zg}) + m({zd, zg}) + m({zn}) + m({zd}) + m({zg}). – Příklad 4 csvukrs –m({zn}) = 0,6. Jaká je velikost Bel({zn}) ? – Příklad 5 csvukrs –Odpověď: Pro množinu s jediným prvkem platí, že Bel(A) = m(A), tedy Bel({zn}) = 0,6. – Příklad 5 csvukrs –Bel(A) odpovídá celkové velikosti domnění přiřazené podmnožině A. Znalost Bel(¬A) (domnění ke komplementu A) je také užitečná informace. Vedle funkce Bel(A) existují jiné funkce, které vyjadřují stejnou informaci, ale mají jinou interpretaci, například míra věrohodnosti (measure of plausibility, upper probability function) – Shrnutí csvukrs Děkuji za pozornost Některé snímky převzaty od: RNDr. Jiří Dvořák, CSc. dvorak@fme.vutbr.cz doc. Ing. Ladislav Beránek, CSc. beranek@ef.jcu.cz