6 Reprezentace a zpracování neurčitosti Většina našich znalostí o reálném světě je zatížena (ve větší či menší míře) neurčitostí. Na druhou stranu, schopnost rozhodovat se i v situacích, kdy nejsou všechny informace dostupné, je běžnou vlastností lidského rozumu. Vezměme si následující čtyři tvrzení: 1. Žadatel o úvěr má měsíční příjem 20 500 korun, 2. Žadatel o úvěr má vysoký měsíční příjem, 3. Žadatel o úvěr má měsíční příjem asi 20 000 korun, 4. Žadatel o úvěr má asi vysoký měsíční příjem. První tvrzení žádnou neurčitost neobsahuje. Tvrzení číslo dvě používá vágní pojem „vysoký příjem“; není přesně specifikováno, jaké částky už jsou „vysoké“ a jaké ještě „nízké“ – navíc pojem vysoký příjem může být různými lidmi chápán různě. Ve třetím tvrzení se objevuje nejistota; neznáme přesnou výši příjmu – víme jen, že je „okolo“ 20000. Ve čtvrtém tvrzení se pak objevuje jak vágnost, tak nejistota. Zpočátku byla problematika neurčitosti umělou inteligencí přehlížena, výzkum se zaměřoval především na symbolické manipulace. Své explicitní vyjádření našla neurčitost až v polovině 70. let v souvislosti s expertními systémy. Vedle ad hoc přístupů, navržených pro práci s neurčitostí v konkrétních expertních systémech (např. MYCIN nebo PROSPECTOR) se vychází i z propracovaných teorií. Historicky první je teorie pravděpodobnosti, jejíž základy spadají do sedmnáctého století. Pravděpodobnostní přístup bychom mohli použít pro vyjádření nejistoty. V současnosti je tato teorie nejpropracovanější a existuje celá řada jejích aplikací v oblasti umělé inteligence. Za všechny zmiňme bayesovské sítě umožňující reprezentovat znalosti o částečně nezávislých evidencích a tyto znalosti použít při usuzování. Z dalších teorií našly své uplatnění v umělé inteligenci teorie možnosti (possibility theory) a teorie fuzzy množin (a fuzzy logiky). Zatímco axiomy teorie možnosti jsou velice podobné axiomům teorie pravděpodobnosti, teorie ale umožňuje vyjadřovat vágnost přirozeného jazyka, fuzzy množiny (rovněž nabízející formalismus pro vyjádření vágnosti) vycházejí ze zcela odlišných základů. Podrobněji je této problematika zpracována např. v [Mařík a kol., 1997] nebo [Giarratano, Riley, 1993]. Důraz na zpracování neurčitosti dostal v posledních letech v kontextu umělé inteligence nový impuls v oblasti nazývané soft computing. Soft computing je termín souhrnně označující metody, které umožňují rychle nalézat řešení (byť ne zcela optimální) vágně a neúplně popsaných problémů [Zadeh, 1994]. Do oblasti soft computing bývají z metod umělé inteligence řazeny fuzzy logika, neuronové sítě a genetické algoritmy. Patří sem ale i pravděpodobnostní metody nebo teorie chaosu. Podstatné je, že tyto metody se nepoužívají izolovaně ale ve vzájemné kombinaci; nalezneme tak například celou řadu neuro-fuzzy nebo fuzzy-genetických systémů. Do oblasti soft computing se přesouvá i práce s neurčitostí z expertních a znalostních systémů.
1
6.1 Způsoby vyjádření neurčitosti 6.1.1 Vágnost 6.1.1.1 Fuzzy množiny Fuzzy množiny představují zobecnění klasických množin (nazývaných pak crisp). Def: Crisp množina A je definována pomocí charakteristické funkce ϕA: U → {0,1} takové, že 0, právě když ∀x ∈ U ; ϕ A ( x) = 1, právě když
x∉ A x∈ A
Def: Fuzzy množina A je definována pomocí charakteristické funkce (též nazývané funkce příslušnosti) µA: U → [0,1] tak, že každému prvku x je přiřazena hodnota z intervalu [0,1]. Pro fuzzy množiny obsahující konečný počet prvků se používá zápis A = {(x, µA(x)}
Obr. 1 Crisp resp. fuzzy množina zvýšená teplota
Hlavní rozdíl mezi oběma typy množin je patrný z obr. 1. Zatímco u crisp množiny A, A ⊆ U můžeme o každém prvku x z univerza U říci, že do množiny A jistě patří nebo jistě nepatří (viz charakteristická funkce vlevo), v případě fuzzy množiny může x prvek do množiny A patřit „jen do jisté míry“ (viz funkce příslušnosti vpravo). S využitím funkce příslušnosti jsou definovány všechny množinové operace: •
kardinalita (počet prvků) fuzzy množiny A
•
doplněk fuzzy množiny A
| A | = ∑ µ A ( x) x∈U
µU \ A ( x) = 1 − µ A ( x) •
průnik fuzzy množin A a B
µ A∩ B ( x) = min(µ A ( x), µ B ( x))
2
•
sjednocení fuzzy množin A a B µ A∪ B ( x) = max(µ A ( x), µ B ( x))
•
A fuzzy podmnožina B A ⊆ B právě když ∀x; µA(x) < µB(x)
Obr. 2 Fuzzy množinové operace
Kromě těchto klasických operací lze pro fuzzy množiny definovat: •
α-řez fuzzy množiny A [µ]α = {x; µA(x) > α}
•
nosič (support) fuzzy množiny A supp(A) = {x; µA(x) > 0}
•
jádro (kernel) fuzzy množiny A ker(A) = {x; µA(x) = 1}
Neboli podpora A jsou ty prvky univerza, které do množiny A “alespoň trochu” patří a jádro jsou ty prvky univerza, které do A jistě patří, a α-řez jsou ty prvky univerza, jejíchž míra příslušnosti k A je větší nebo rovna α.
1 α
0 jádro α řez nosič Obr. 3 Jádro, nosič a alfa řez
Často se v souvislosti s fuzzy množinami mluví o počítání se slovy. Mají se tím na mysli tzv. lingvistické proměnné (např. velký, malý apod.), vyjádřené pomocí fuzzy intervalů.
3
Obr. 4 Linguistické proměnné
6.1.1.2 Fuzzy relace Fuzzy relace jsou definovány na kartézském součinu (crisp) množin: R: X × Y → [0, 1], X = {x}, Y = {y}. Hodnota µR(x,y) odpovídá stupni relace mezi x∈ X a y ∈ Y . Příklad zvířata: Podobnost mezi zvířaty X = {kůň, osel}, Y = {mula, kráva} může být definována následující tabulkou: Y = {mula X = {kůň osel}
kráva}
0.8
0.4
0.9
0.2
Def: Kompozice relace pro crisp relaci R: X × Y → {0, 1} a crisp množinu M ⊆ X je definována jako M ° R = {y ∈ Y; ∃x∈ M ∧ (x , y) ∈ R} Def: Kompozice relace pro fuzzy relaci R: X × Y → [0, 1] a fuzzy množinu M ⊆ X je definována jako M ° R = {(y, µM°R(y)}, kde µM°R(y) = max min (µM(x), µR(x,y)) Příklad zvířata pokračování: Je-li M = {(kůň, 0.7)}, pak M ° R = {(mula, 0.7),(kráva, 0.4)} Analogicky, tedy s využitím max-min kompozice můžeme „skládat“ relace.
4
Def: Pro dvě fuzzy relace R: X × Y → [0, 1] a S: Y × Z → [0, 1] je R ° S fuzzy relace X × Z → [0, 1] taková, že µR°S(x,z) = maxy min (µR(x,y), µS(y,z)) Relaci mezi linguistickými proměnnými (tj. mezi fuzzy množinami) můžeme chápat jako fuzzy podmíněný příkaz if X is A then
Y is B
kde A je fuzzy množina na X a B je fuzzy množina na Y (např. IF BMI vysoké THEN krevní tlak vysoký). 6.1.2 Nejistota 6.1.2.1 Hrubé množiny Hrubé množiny (rough sets) představují jakési aproximace klasických (crisp) množin. Def: Nechť pro universum U existuje jeho rozklad tvořený množinami Bi. (množiny tvořící rozklad jsou navzájem disjunktní a jejich sjednocení tvoří celou množinu U. Pak pro každou množinu A; A ⊆ U definujme dolní aproximaci AL jako AL = ∪{ Bi; Bi ⊆ A}, horní aproximaci AU jako AU = ∪{ Bi; Bi ∩ A ≠ ∅}, a hranici AUL jako AUL = AU – AL.
Obr. 5 Hrubé množiny
5
Základní myšlenku hrubých množin ilustruje Obr. 5. Pro množinu A (na obrázku žlutě) a množiny Bi tvořené jednotlivými obdélníky je její dolní aproximace znázorněna zeleně a hranice znázorněna modře. Horní aproximace je pak vše, co je barevné. 6.1.2.2 Vícehodnotové logiky Klasická dvouhodnotová logika pracuje se dvěma pravdivostními hodnotami TRUE a FALSE (často značené 1 a 0). U vícehodnotových logik je pravdivostních hodnot více. Nejjednodušší vícehodnotovou logikou je tříhodnotová logika. K hodnotám 1 a 0 se zde přidává hodnota X, která má význam UNKNOWN (ve smyslu „tvrzení může být TRUE nebo FALSE“). Tomu odpovídá i příslušné rozšíření definic jednotlivých logických spojek: 1. nezáleží-li na neznámé hodnotě, pravdivostní hodnota logické spojky je příslušná standardní hodnota, 2. záleží-li na neznámé hodnotě, je pravdivostní hodnota logické spojky X.
Obr. 6 Negace a konjunkce v trojhodnotové logice
Obr. 7 Disjunkce a implikace v trojhodnotové logice
„Pravé“ vícehodnotové logiky pracují s pravdivostními hodnotami z celého intervalu [0, 1]. Často se v této souvislosti mluví o fuzzy logice, i když ne každá vícehodnotová logika je inspirována fuzzy teorií. Def: Funkce : [0, 1] × [0, 1] → [0, 1] se nazývá t-norma, právě když: 1. (a, 1) = a 2. (a, b) = (b, a) 3. (a, (b,c)) = ( (a, b), c) 4. pro b < c (a, b) < (a, c) (lze dokázat, že (a, 0) = 0)
6
Příklady t-norem: •
Gődelova
min (a, b) = min(a, b)
•
součinová
prod (a, b) = a · b
•
Lukasiewiczova
Luk (a, b) = max(0, a + b – 1)
Def: Funkce ⊥: [0, 1] × [0, 1] → [0, 1] se nazývá t-konorma, právě když: 1. ⊥ (a, 0) = a 2. ⊥ (a, b) = ⊥(b, a) 3. ⊥ (a, ⊥ (b,c)) = ⊥ (⊥ (a, b), c) 4. pro b < c
⊥ (a, b) < ⊥ (a, c)
(lze dokázat, že ⊥ (a, 1) = 1) Příklady t-konorem: •
Gődelova
⊥min (a, b) = max(a, b)
•
součinová
⊥prod (a, b) = a + b - a · b
•
Lukasiewiczova
⊥Luk (a, b) = min(1, a + b)
Vztah mezi t-normou a t-konormou je definován následující rovností: ⊥ (a, b) = 1 - (1 - a, 1 - b) Def: Nechť a, b ∈ [0, 1] jsou pravdivostní hodnoty dvou fuzzy tvrzení. Logické spojky ve fuzzy logice jsou pak definovány následujícím způsobem: 1. negace ¬a pro a < b
¬b < ¬a
¬¬a = a uvedeným požadavkům vyhovuje standardní negace ¬ a = 1 - a 2. konjunkce a ∧ b = (a, b) 3. disjunkce a ∨ b = ⊥(a, b) 4. implikace a ⇒ b je definována jako tzv. reziduum t-normy, tedy tak, že a ⇒ b = max(c, (a, c) < b) Věta: Nechť fuzzy implikace je definována jako reziduum t-normy. Pak
7
1. pro a < b je a ⇒ b = 1 (neboť (a, 1) = a < b ) 2. pro a > b je •
Gődelova implikace
a⇒b = b
•
součinová implikace
a ⇒ b = b/a
•
Lukasiewiczova implikace
a⇒b = 1– a + b
6.1.2.3 Pravděpodobnost Teorie pravděpodobnosti představuje klasický způsob jak pracovat s neurčitostí. Připomeňme zde některé základní pojmy (dle Jiroušek). Def: Nechť X je konečná množina, Pt(X) je potenční množina (množina všech podmnožin). Pravděpodobnostní distribuce P je takové zobrazení P: Pt(X) → [0, 1] že, •
P(X) = 1
•
P(∅) = 0
•
pro A, B ⊆ Pt(X) takové, že A ∩ B = ∅ platí P(A ∪ B) = P(A) + P(B)
Def: Podmíněná pravděpodobnost jevu A při jevu B je definována jako P( A | B ) =
P ( A ∩ B) P( B)
Věta: Je-li P(A) > 0 a P(B) > 0, potom
P( A | B) =
P( B | A) P ( A) P( B)
Výše uvedený vztah se nazývá Bayesův vzorec. Def: Jevy A a B jsou nezávislé právě když
P(A ∩ B) = P(A) P(B) Def: Jevy A a B jsou podmíněně nezávislé při jevu C právě když
P(A ∩ B|C ) = P(A|C) P(B|C)
8
Podívejme se nyní na situaci, kdy množina X je kartézský součin hodnot, které mohou nabývat náhodné veličiny X1, X2,…, Xn. Potom pravděpodobnostní rozložení P definované na X1 × X2 ×… × Xn budeme též nazývat pravděpodobnostní distribuce náhodných veličin X1, X2,…, Xn. Místo P(X1=x1, X2=x2, …) budeme pro jednoduchost psát P(x1, x2, …). Def: Uvažujme dvě náhodné veličiny X1, X2 a nějakou jejich sdruženou pravděpodobnostní distribuci P(X1, X2). Marginální pravděpodobnostní distribuce veličiny X1 je dána vztahem
PX 1 ( x1 ) =
∑ P( x , x 1
2
)
x2 ∈ X 2
Def: Uvažujme dvě náhodné veličiny X1, X2 a nějakou jejich sdruženou pravděpodobnostní distribuci P(X1, X2). Veličiny X1, X2 jsou nezávislé, právě když P( x1 , x 2 ) = P( x1 ) P( x 2 ) Def: Uvažujme tři náhodné veličiny X1, X2, X3. Veličiny X1, X2 jsou podmíněně nezávislé při veličině X3, právě když
P( x1 , x 2 x3 ) = P( x1 x3 ) P( x 2 x3 ) 6.1.2.4 Možnost
Základy teorie možnosti (possibility theory) formuloval v roce 1978 L.A: Zadeh jako nástroj umožňující usuzovat na základě nepřesné či vágní znalosti a brát přitom do úvahy neurčitost těchto znalostí. Formálně vzato tato teorie představuje alternativu k teorii pravděpodobnosti. Uvidíme tedy podobné definice jako v předcházející podkapitole. Def: Nechť X je konečná množina, Pt(X) je potenční množina (množina všech podmnožin). Possibilistická distribuce Π je takové zobrazení Π: Pt(X) → [0, 1]
že, •
Π (X) = 1
•
Π (∅) = 0
•
pro A, B ⊆ Pt(X) takové, že A ∩ B = ∅ platí Π (A ∪ B) = max (Π (A), Π (B))
Věta: Nechť A, B ⊆ Pt(X). Potom Π (A ∪ B) = max (Π (A), Π (B))
(Zatímco definice pravděpodobnostní distribuce požaduje, aby množiny A a B byly disjunktní, to že možnost sjednocení odpovídá maximální možnosti jednotlivých členů platí pro jakékoliv množiny A a B.) Věta: Nechť A, B ⊆ Pt(X). Potom Π (A ∩ B) ≤ min (Π (A), Π (B))
9
Def: Uvažujme dvě náhodné veličiny X1, X2 a nějakou jejich sdruženou pravděpodobnostní distribuci P(X1, X2). Marginální possibilistická distribuce veličiny X1 je dána vztahem Π X1 ( x1 ) = max Π ( x1 , x 2 ) x2 ∈X 2
Def: Uvažujme dvě náhodné veličiny X1, X2 a nějakou jejich sdruženou possibilistickou distribuci Π(X1, X2). Veličiny X1, X2 jsou nezávislé, právě když
Π ( x1 , x 2 ) = Π ( x1 ) ⊗ Π ( x 2 ) Def: Uvažujme tři náhodné veličiny X1, X2, X3. Veličiny X1, X2 jsou podmíněně nezávislé při veličině X3, právě když
Π ( x1 , x 2 x3 ) = Π ( x1 x3 ) ⊗ Π ( x 2 x3 ) Ve výše uvedených definicích značí symbol ⊗ t-normu, kterou jsme poznali v souvislosti s fuzzy množinami. Operace ⊗ tedy může (ale nemusí) být klasické násobení, tak jak je tomu v případě pravděpodobnosti. Dalším (a ještě významnějším) rozdílem je to, že požadujeme aby součet pravděpodobností všech prvků množiny X byl 1, zatímco u možnosti požadujeme, aby nějaký prvek množiny X byl jistě možný. Možnost tedy klade méně omezujících podmínek na formulování expertem, než pravděpodobnost.
6.2 Usuzování s využitím neurčitosti 6.2.1 Fuzzy inference Odvozovací pravidlo
R: if X is A then Y is B X is A ’ Y is B’ kde A a A’ nemusí být stejné, využívá tzv. kompozicionální pravidlo inference µB’(y) = maxx min (µA‘(x), µR(x,y))
6.2.1.1 Mamdaniho model
Takzvaný Mamdaniho model je jazykový model pracující s fuzzy podmíněnými příkazy typu Ri:
if X is Ai then Y is Bi
kde Ai(x) a Bi(y) jsou fuzzy množiny. Stupeň pravdivosti případné konjunkce v předpokladu se vyhodnotí jako minimum.
10
Fuzzy podmíněného příkazu (pravidlo) chápeme jako fuzzy relaci, kde µR(x,y) = ( µA(x), µB(y)) kde jako t-norma se nejčastěji používá minimum. Výstup y’ fuzzy systému spočítáme ze vstupu x‘ a relace R jako max min (obecněji ⊥ ) kompozici y‘ = x‘ ° R tedy µB(y‘) = maxx min (µA(x‘), µR(x,y)) Příklad:
Jsou dány crisp množiny X = {1, 2, 3}, Y = {1, 2, 3, 4}, fuzzy množina Xlow = {(1, 1), (2, 0.7), (3, 0.3)} a fuzzy množina Yhigh = {(1, 0.2), (2, 0.5), (3, 0.8), (4, 1)}. Pravidlo if X is low then Y is high lze vyjádřit relací 1 R: low ° high =
2
3
4
1
0.2 0.5 0.8
1
2
0.2 0.5 0.7 0.7
3
0.2 0.3 0.3 0.3
Je-li nyní fuzzy množina Xmedium = {(1, 0.5), (2, 1), (3, 0.5)}, potom y* = medium ° R = {(1, 0.2), (2, 0.5), (3, 0.7), (4, 0.7)}
Příklad: balancování tyče
Balancování tyče na vozíku (neboli převrácené kyvadlo – viz Obr. 8) je klasická úloha fuzzy regulace, jejíž popis je převzat z (Nauck, Klawonn, Kruse). Cílem je udržet tyč ve svislé poloze pomocí síly F, která je závislá na úhlu Θ mezi kyvadlem a svislou osou, a na úhlové rychlosti Θ’ = d Θ/ dt. Uvažujme rozsah velikostí úhlu Θ od –90o do 90o, rozsah hodnot úhlové rychlosti od –45os-1 do 45os-1 a rozsah hodnot síly F od –10N do 10N. Přiřaďme každé z těchto veličin fuzzy intervaly „velký záporný“ (vz), „střední záporný“ (sz), „malý záporný“ (mz), „asi nula“ (an), „malý kladný“ (mk), střední kladný“ (sk) a „velký kladný“ (vk) způsobem analogickým Obr. 4 . Pravidla použitá pro řešení této úlohy mají podobu: Ri: if Θ is Ai and Θ’ is Bi then F is Ci Celkem se použije 19 pravidel, souhrnně ukázaných v Tab. 1. Tedy pravidlo je např. if Θ is “malý záporný” and Θ’ is „velký záporný“ then F is “malý kladný”
11
Při odvozování se nejprve určí stupeň pravdivosti předpokladu každého pravidla (jako minimum stupňů pravdivosti jednotlivých linguistických proměnných v předpokladu). Pak se pro každé pravidlo určí hodnota závěru (jako minimum stupně pravdivosti předpokladu a linguistické proměnné v závěru). Nakonec se získá výstupní hodnota jako maximum ze závěrů počítaných pro jednotlivá pravidla. Schematicky je celý postup znázorněn na Obr. 9. (Analytické řečení celé úlohy vede na soustavu nelineárních diferenciálních rovnic)
Obr. 8 Přvrácené kyvadlo
Θ vz
sz
vz
mz
an
mk
vk
sk
vk
sk
vk
sk
sz Θ’
mk
mz
sz
mz
mk
an
vz
mz
an
mk
mk
mz
mk
sk
sz
vk
vz
sz
mz
Tab. 1 Fuzzy pravidla pro kyvadlo
12
sk
Obr. 9 Fuzzy inference (Nauck, Klawonn, Kruse)
V případě fuzzy regulace musíme tento odvozovací postup ještě doplnit o fuzzyfikaci vstupů a defuzzyfikaci výstupu. Při fuzzyfikaci se konkrétní číselná hodnota převádí na fuzzy množinu (fuzzy interval), při defuzzyfikaci se výsledek odvozování na základě fuzzy inference (fuzzy množina) převádí na konkrétní číselnou hodnotu. Obecné schéma fuzzy regulace (podle kterého pracují různé spotřebiče typu fuzzy pračka, fuzzy mikrovlnná trouba apod.) je na Obr. 10. Pro defuzzyfikaci výstupu y se nabízí několik možností. Numerické výstupní veličině se přiřadí hodnota odpovídající •
těžišti odvozené fuzzy množiny
•
středu maxima odvozené fuzzy množiny
•
váženému průměru odvozené fuzzy množiny
Obr. 10 Fuzzy regulace
13
6.2.1.2 Takagiho – Sugenův model
Takzvaný Takagiho - Sugenův model je jazykový model pracující s fuzzy podmíněnými příkazy typu Ri: if X is Ai then y = fi(x) kde f(x) je obvykle lineární funkcí x, tedy f(x) = aTx + b. Začátek výpočtu (fuzzyfikace, inference) je stejný jako u Mamdaniho modelu. Výstupní hodnota y se ale spočítá jako y=
∑ akt ⋅ f (x) ∑ akt i
i
i
i
i
kde akti je stupeň pravdivosti předpokladu i-tého pravidla. Stupeň pravdivosti případné konjunkce v předpokladu se opět vyhodnotí jako minimum. 6.2.1.3 Dedukce ve vícehodnotové logice
Jinou variantou fuzzy odvozování je odvozování ve vícehodnotové (fuzzy) logice. Zde vycházíme z klasického dedukčního pravidla ϕ ⇒ ψ ϕ ψ Ze stupně a pravdivosti formule ϕ ⇒ ψ stupně b pravdivosti formule ϕ pak počítáme stupeň pravdivosti formule ψ. Použijeme-li Lukasiewiczovu logiku, která má vlastnost úplnosti (logické vyplývání v sémantickém smyslu odpovídá dokazatelnosti chápané syntakticky), stupeň pravdivosti formule ψ spočítáme jako Luk (a, b) = max(0, a + b – 1).
6.2.2 Pravděpodobnostní inference
Základním pojmem tohoto přístupu, známého především ze systému PROSPECTOR [Duda, Gasching, 1979], je pojem šance. Ta je pro libovolný výrok A definována jako podíl počtu jevů příznivých A a jevů nepříznivých A: O ( A) =
P( A) P( A) = P( A ) 1 − P( A)
Práce s neurčitostí vychází z Bayesovy věty, známé z teorie pravděpodobnosti: P( H | E ) =
14
P( E | H ) ⋅ P( H ) , P( E )
kde P(H|E) je podmíněná, nebo aposteriorní pravděpodobnost hypotézy H, víme-li, že evidence E jistě platí, a P(H) je apriorní pravděpodobnost hypotézy H. Podobně můžeme definovat aposteriorní pravděpodobnost negace hypotézy H, víme-li, že evidence E jistě platí jako P( H | E ) =
P( E | H ) ⋅ P( H ) P( E )
Vydělíme-li výše uvedené rovnice, dostaneme P( H | E ) P( E | H ) P( H ) , = ⋅ P( H | E ) P( E | H ) P( H ) což můžeme, s využitím pojmu šance vyjádřit jako O( H | E ) =
P( E | H ) ⋅ O( H ) . P( E | H )
Definujeme-li výrazem L=
P( E | H ) P( E | H )
míru postačitelnosti, dostáváme pro aposteriorní šanci hypotézy H výraz O ( H | E ) = L ⋅ O( H )
Míra postačitelnosti L je kvantitativní ocenění pravidla a zadává ji expert. Velká hodnota (L>>1) říká, že evidence E je postačující k dokázání hypotézy H, protože z indiferentní apriorní šance O(H) „udělá“ velkou aposteriorní šanci O(H|E). Obdobným způsobem můžeme definovat míru nezbytnosti L=
P( E | H ) P( E | H )
a aposteriorní šanci hypotézy H jako O ( H | E ) = L ⋅ O( H ) . Bayesova věta dává návod jak stanovit vliv jedné evidence na uvažovanou hypotézu. Jak ale postupovat, pokud je evidencí více? Tedy, jak stanovit aposteriorní pravděpodobnost P(H|E1,…, EK)? Jsou v zásadě dvě možnosti, jak postupovat: 1. Naivní bayesovský přístup vychází z předpokladu, že jednotlivé evidence E1,…,EK jsou podmíněně nezávislé při platnosti hypotézy H [Duda, Hart, 1973]. Tento zjednodušující předpoklad umožňuje spočítat aposteriorní pravděpodobnost hypotézy při platnosti všech evidencí
15
P(H|E1,…,EK) =
P(E1,…,EK |H) × P(H) P(E1,…,EK)
vyjádřeno jako šance dostáváme O( H | E1 … E n ) = L1 … Ln ⋅ O( H ) O ( H | E 1 … E n ) = L1 … L n ⋅ O( H ) 2. Bayesovské sítě (též nazývané pravděpodobnostní sítě) umožňují reprezentovat znalosti o částečně nezávislých evidencích a tyto znalosti použít při usuzování. Bayesovská síť je acyklický orientovaný graf zachycující pomocí hran pravděpodobnostní závislosti mezi náhodnými veličinami. Ke každému uzlu u (náhodné veličině) je přiřazena pravděpodobnostní distribuce tvaru P(u|rodiče(u)), kde rodiče(u) jsou uzly, ze kterých vycházejí hrany do uzlu u. To umožňuje spočítat sdruženou pravděpodobnostní distribuci celé sítě jako n P(u1,….,un) =
∏ P(ui|rodiče(ui)) i=1
Má-li tedy bayesovská síť podobu uvedenou na Obr. 11 , bude mít sdružená distribuce tvar P(Z,K,D,M) = P(Z) P(K|Z) P(D|Z) P(M|K,D)
Obr. 11 Příklad bayesovské sítě
6.2.3 Possibilistická inference
Odvozování založené na teorii možnosti je analogické s odvozováním založeným na teorii pravděpodobnosti. Zhruba se dá říci, že sčítání je nahrazeno hledáním maxima a násobení je nahrazeno použitím nějaké t-normy (například násobením). Podobně jako bayesovskou síť lze definovat posibilistickou síť jako acyklický orientovaný graf zachycující pomocí hran posibilistické závislosti mezi náhodnými veličinami. Každému uzlu můžeme
16
přiřadit podmíněnou posibilistickou distribuci Π(u|rodiče(u)). Sdruženou posibilistickou distribuci celé sítě pak definujeme jako
n Π (u1,….,un) =
∏ Π (ui|rodiče(ui)) i=1
Bude-li tedy mít posibilistická síť stejnou podobu jako bayesovská síť uvedená na Obr. 11, bude sdružená posibilistická distribuce dána výrazem Π (Z,K,D,M) = Π(Z) Π(K|Z) Π(D|Z) Π(M|K,D)
6.2.4 Nemonotonní usuzování
Všechny doposud zmíněné způsoby práce s neurčitostí vycházejí z toho, že neurčitost je vyjádřena pomocí číselné hodnoty. Zajímavou alternativu nabízí logika, konkrétněji tzv. nemonotónní usuzování. Klasickou logickou inferenci můžeme chápat jako odvozování důsledků plynoucích y formulí v prostředí, které je statické. Označíme-li Cn(X) množinu všech důsledků množiny formulí X, pak 1. X ⊆ Cn(X) 2. X ⊆ Y ⇒ Cn(X) ⊆ Cn(Y) 3. Cn(Cn(X)) = Cn(X) Nemonotonní usuzování je takový způsob inference, kdy dříve učiněný závěr může být zpochybněn ve světle nové informace – neplatí tedy podmínka č. 2. Klasickým příkladem je formule „každý pták létá“. Závěr, který můžeme učinit na základě této formule o leteckých schopnostech libovolného ptáka ale bude zpochybněn, přidáme-li dodatečnou formuli (znalost), že tučňák nelétá.
6.2.5 Kompozicionální vs. nekompozicionální přístup
Výše uvedené přístupy buď skládají dílčí příspěvky k celkové neurčitosti = jsou tedy kompozicionální (pravděpodobnostní, possibilistická inference, fuzzy inference), nebo hledají jeden způsob odvození závěru (tříhodnotová logika, nemonotónní usuzování).
17
Cvičení: 1) Příklad: Jsou dány množiny X = {1, 2}, Y = {1, 2, 3} a fuzzy relace R: X × Y Y 1 R: X
2
3
1
0.3 0.8
1
2
0.9 0.7 0.4
Pro A = {(1, 0.5), }2, 0.7)} spočítejte kompozici
A ° R.
2) Příklad: Jsou dány tři crisp množiny X = {1, 2}, Y = {1, 2, 3}, Z = {1, 2, 3, 4}, a dvě fuzzy relace R: X × Y a S: Y × Z Y 1 R: X
Z 2
3
1
1
0.3 0.8
1
2
0.9 0.7 0.4
S: Y
2
3
4
1
0.7 0.6 0.4 0.1
2
0.4
3
0.5
1
0.7 0.2
0.9 0.6 0.8
Spočítejte kompzozici R ° S
3) Příklad: Na základě definice t-normy dokažte, že (a, 0) = 0
4) Příklad: Na základě definice t-konormy dokažte, že ⊥(a, 1) = 1
5) Příklad: Prověřte, že Lukasiewiczovo dedukční pravidlo uvedené v 6.2.1.3 vychází z Lukasiewiczovy implikace.
18
Literatura: 1. Duda R.O., Gasching J.E.: Model Design in the Prospector Konsultant System for Mineral Exploration. in: Michie,D. (ed.), Expert Systems in the Micro Electronic Age, Edinburgh University Press, UK, 1979. 2. Giarratano J., Riley G.: Expert Systems. Principles and Programming. PWS Publishing Co. 1993. 3. Konar A.: Computational Inteligence. Springer, 2005 4. Mařík V., Štěpánková O., Katanský J a kol. Umělá inteligence II. Academia, 1997. 5. Nauk D., Klawonn F., Kruse R.: Foundations of Neuro-fuzzy systems. John Wiley, 1997
19
