Expertní systémy
T5: metody inference
Metody odvozování matematická východiska: logika, Prolog psychologická východiska: rámce biologická východiska: konekcionismus, neuronové sítě statistická východiska: kauzální (bayesovské) sítě ekonomická východiska: racionální agenti (teorie užitku)
P. Berka, 2012
1/21
Expertní systémy
T5: metody inference
Metody odvozování „klasické“ logické defaulty nemonotónní generování a testování analogie
P. Berka, 2012
2/21
Expertní systémy
T5: metody inference
Základní logické metody inference A 0 0 1 1
B 0 1 0 1
A
B 1 1 0 1
Dedukce: logické usuzování při kterém musí závěr plynout z pravidla a předpokladů A A B
B
(modus ponens)
Abdukce: usuzování z pravidla a pravdivého závěru na předpoklady, které mohly tento závěr způsobit (lze použít pro vysvětlení) Indukce: zobecnění speciálních případů (strojové učení) P. Berka, 2012
3/21
Expertní systémy
T5: metody inference
Defaultní metody pokud nejsou k dispozici speciální znalosti, uvažuje se na základě obecných znalostí, tedy např. Jestliže (x) platí a (x) může být
konsistentně předpokládáno, pak odvoď (x)
Odvozovací pravidlo (Reiter, 1980)
(x); (x) (x) Operátor modální logiky (McDermott, Doyle, 1980)
( x) (x)
M (x)
(x)
Defaultové logiky definují pojem rozšíření (extenze) teorie s defaulty jako analogii k pojmu logického uzávěru (množiny logických důsledků).
NEST modeluje defaulty typu ; (x)/ (x) P. Berka, 2012
4/21
Expertní systémy
T5: metody inference
Nemonotonní usuzování předcházející znalosti se mohou revidovat na základě nových poznatků Klasická logická inference - odvozování důsledků plynoucích z formulí v prostředí, které je statické: 1. 2. 3. 4.
X Cn(X) X Y Cn(X) Cn(Y) Cn(Cn(X)) = Cn(X) Cn(X) = U Cn(Y), kde Y jsou konečné podmnožiny množiny X
kde Cn(X) je množina všech důsledků množiny formulí X
Pro nemonotonní usuzování neplatí axiom 2, tedy přidáme-li k X další formuli, přestanou platit původní závěry. Lze použít pro vyjádření neurčitosti typu výjimka z obecného pravidla: všichni ptáci létají tučňák nelétá
P. Berka, 2012
5/21
Expertní systémy
T5: metody inference
Generování a testování opakovaně se generuje možné řešení V daném okamžiku běhu systému mohou být splněny podmínky více pravidel, přičemž levé strany každého z nich mohou být nasyceny (v pracovní paměti existuje objekt, který vyhovuje podmínkám pravidla) více způsoby. Dvojice skládající se z pravidla a jeho nasycení se nazývá instance.
Základní odvozovací cyklus: porovnání (match) - vytvoření rozhodovací množiny, která obsahuje všechna v dané chvíli aplikovatelná pravidla, rozhodnutí sporu (conflict resolution) - výběr právě jedné instance (a tedy právě jednoho pravidla) z rozhodovací množiny, úkon (act) - provedení akcí pravé strany vybrané instance; tyto akce typicky vytvářejí, modifikují a ruší objekty v pracovní paměti.
P. Berka, 2012
6/21
Expertní systémy
T5: metody inference
Diagnostická úloha
kde vzít počáteční hypotézu, jak zvolit vyšetření, které má prověřit zkoumanou hypotézu, co způsobí změnu hypotézy, jak zjistit, že vyšetřování skončilo. P. Berka, 2012
7/21
Expertní systémy
T5: metody inference
Inference v diagnostických systémech Prohledávání báze znalostí: výběr relevantních znalostí v dané fázi konzultace exhaustivní - nalezení všech znalostí umožňujících odvodit daný závěr; typické pro kompozicionální systémy pracující s neurčitostí neexhaustivní- nalezení prvního pravidla, které umožní odvodit závěr; typické pro systémy bez neurčitosti
Aplikace pravidel: aplikace jednoho pravidla vychází z dedukce exhaustivní - skládání dílčích příspěvků všech pravidel vedoucích k témuž závěru; typické pro kompozicionální systémy pracující s neurčitostí neexhaustivní - aplikace prvního pravidla, které umožní odvodit závěr; typické pro systémy bez neurčitosti –„skládání“ pravidel má podobu disjunkce
Práce s neurčitostí: odvozování závěrů z neurčitých informací a znalostí P. Berka, 2012
8/21
Expertní systémy
T5: metody inference
Prohledávání báze znalostí (1) Zpětné řetězení (backward chaining): vycházíme z cílů, které chceme odvodit a pokoušíme se nalézt vhodná pravidla
(lze použít pouze v diagnostických systémech) P. Berka, 2012
9/21
Expertní systémy
T5: metody inference
Prohledávání báze znalostí (2) Přímé řetězení (forward chaining): vycházíme z faktů, která jsou splněna a pokoušíme se nalézt aplikovatelná pravidla
(jediný způsob pro generativní systémy, lze ale využít i v diagnostických systémech) P. Berka, 2012
10/21
Expertní systémy
T5: metody inference
Zpětné nebo přímé řetězení? Dle typu úlohy:
Generativní – lze jen přímé Diagnostické – lze obojí
Dle dostupných dat:
jestliže zatím nemáme k dispozici žádná fakta a zajímá nás, zda je plněn některý z cílů (vlastně se ptáme, co potřebujeme vědět pro odvození cíle), je vhodnější zpětné řetězení, jestliže známe všechna fakta a zajímá nás, co všechno lze z těchto faktů odvodit, je vhodnější přímé řetězení.
Dle struktury báze znalostí:
pro hlubokou bázi, která má méně cílů, je vhodnější zpětné řetězení, pro plochou bázi, která má více cílů, je vhodnější přímé řetězení.
P. Berka, 2012
11/21
Expertní systémy
T5: metody inference
Aplikace pravidel Aplikace jednoho pravidla vychází z dedukce (na základě platnosti předpokladu lze odvodit platnost závěru). Pokud není předpoklad pravidla splněn, pravidlo se nebude aplikovat, protože platí-li pravidlo a neplatí-li předpoklad, nelze nic říci o platnosti závěru. IF bledost THEN tbc not(bledost) ???
Aby se naše báze znalostí chovala „rozumněji“, musíme doplnit pravidla, která pokryjí situace, kdy původní předpoklady neplatí: IF not(bledost) THEN not(tbc) Lze přitom postupovat dle deMorganových vztahů: (A B) = A B (A B) = A B P. Berka, 2012
12/21
Expertní systémy
T5: metody inference
Prolog a odvozování Logický program: Konečná posloupnost faktů A a podmíněných příkazů
B :- A1,A2,...,An.
Na vlastnosti relací definovaných programem se dotazuji pomocí cílových klauzulí ?- C1,C2,...,Cn.
Tedy: Ptáme se, zda existují hodnoty, pro které je splněna konjunkce cílů C1,C2,...,Cn unifikace rezoluce hledání alternativ
P. Berka, 2012
13/21
Expertní systémy
T5: metody inference
Strategie Prologu: Prohledávání do hloubky a mechanismus navracení (backtracking). ?- C1,...,Cn. Vypočet začíná pokusem splnit cíl C1. V případě, že se podařilo tento cíl splnit (např. nalezením prvního vyhovujícího faktu v databázi), systém pokračuje cílem C2. Ten se opět pokouší splnit (hledáním klauzulí jejichž hlava odpovídá cíli C2 nebo hledáním faktů v databázi). Pokud se cíl C2 nepodařilo splnit, program se navrací k cíli C1 a pokouší se ho splnit jiným způsobem (např. nalezením jiného vyhovujícího faktu v databázi) tak, aby se eventuelně podařilo splnit i cíl C2. Podařilo-li se splnit cíl C2, pokračuje se cílem C3, atd.
Negace jako neúspěch: pravda je jen to, co je v databázi (předpoklad uzavřenosti světa).
P. Berka, 2012
14/21
Expertní systémy
T5: metody inference
Prolog jako inferenční mechanismus: zpětné řetězení bez neurčitosti (tedy nekompozicionální)
Tedy Prolog vhodný pro diagnostické expertní systémy savec(X) :- dava_mleko(X). savec(X) :- ma_srst(X). dravec(X) :- savec(X),zere_maso(X). kocka(X) :- dravec(X),mnouka(X). pes(X) :- dravec(X),steka(X). pes(X) :- dravec(X),chodi_na_voditku(X).
ma_srst(bobek). ma_srst(sultan). ma_srst(tyrl). zere_maso(mici). zere_maso(sultan). zere_maso(tyrl). mnouka(mici). dava_mleko(stracena). steka(sultan). chodi_na_voditku(tyrl). P. Berka, 2012
15/21
Expertní systémy
T5: metody inference
Odvozování v systému NEST (1) Prohledávání báze: režim dialog - klasické zpětné řetězení režim dotazník - pracuje se pouze s předem zadanými fakty (simulace přímého řetězení) režim dialog s dotazníkem - možnost předem zodpovědět některé dotazy, pak následuje zpětné řetězení
Výběr relevantních znalostí v dané fázi konzultace: exhaustivní v rámci apriorních a kompozicionálních pravidel
neexhaustivní v rámci logických pravidel
Aplikace pravidel (modus ponens):
kompozicionální v rámci apriorních a kompozicionálních pravidel nekompozicionální v rámci logických pravidel
P. Berka, 2012
16/21
Expertní systémy
T5: metody inference
Odvozování v systému NEST (2) V síti pravidel se odvozuje všemi dostupnými směry.
Práce s neurčitostí: (příště)
Vyhodnocení integritních omezení: Po skončení konzultace se zjišťuje, zda jsou porušeny logické implikace. Ant
Suc (stupeň)
Míra porušení je definována jako
IMPL(a,s) = max(0, min(1, a-s)) pro a > 0 (Integritní omezení je porušeno pokud Ant je splněn více než Suc)
P. Berka, 2012
17/21
Expertní systémy
T5: metody inference
Další prostředky odvozování v expertních systémech Agenda je seznam (obvykle zásobník, tedy struktura LIFO) úkolů, které se mají provést. Vytváří se jako vedlejší produkt řešení úlohy. Princip vyřizování agendy umožňuje efektivní zaostřování pozornosti.
Tabule (blackboard) je speciální datová a řídící struktura, která umožňuje předávat informace mezi jednotlivými částmi systému. Zpočátku tabule představovala pouze sdílenou datovou strukturu. Později byla architektura tabule rozšířena i o řídící strukturu, která umožňuje výměnu řídících informací nebo se podílí na řízení celého systému. Dnes se tabule používá v systémech distribuované umělé inteligence.
P. Berka, 2012
18/21
Expertní systémy
T5: metody inference
Usuzování založené na analogii odvození závěru na základě podobnosti s jinou situací (používá se v rámci tzv. případového usuzování (Case-Based Reasoning, CBR) Pro měření podobnosti (vzdálenosti) se používá metrika: 1. x1,x2 X; d(x1,x2) 0 2. d(x1,x2) = 0
x1 = x2
3. d(x1,x2) = d(x2,x1) 4. x1,x2,x3
X; d(x1,x2) + d(x2,x3)
d(x1,x3)
např: Eukleidovská metrika 2
m
d x1 , x2
x1 j
x2 j
j 1
„překrytí“ m
d x1 , x2
x1 j , x2 j , kde j 1
P. Berka, 2012
x1 j , x2 j
0 pro x1 j 1 pro x1 j
x2 j x2 j 19/21
Expertní systémy
T5: metody inference
Případové usuzování (Case-Based Reasoning, CBR) alternativa k usuzování založeném na pravidlech
Inferenční cyklus (Watson, Marir, 1994)
retrive (najdi nejpodobnější případy) reuse (použij navržené řešení) revise (případně reviduj navržené řešení) retain (uchovej nové řešení v bázi případů)
P. Berka, 2012
20/21
Expertní systémy
T5: metody inference
Vysvětlování Důvody pro vysvětlování v expertním systému: uživatel získá jistotu, že způsob usuzování systému je v zásadě v pořádku a že nabízená řešení jsou akceptovatelná, tvůrce aplikace se může přesvědčit, že implementované znalosti (a jejich využívání) odpovídá představám experta.
U diagnostických expertních systémů typicky nacházíme vysvětlení: Why - proč systém klade svůj dotaz, How - jak dospěl systém ke svým závěrům, What if - jak by systém reagoval na změnu některé odpovědi.
P. Berka, 2012
21/21
