Expertn´ı syst´emy MYCIN, Prospector
Pseudodefinice [Expertn´ı syst´ emy, Feigenbaum a kol. 1988] Expertn´ı syst´emy jsou poˇc´ıtaˇcov´e programy, simuluj´ıc´ı rozhodovac´ı ˇcinnosti experta pˇri ˇreˇsen´ı sloˇzit´ych u ´loh a vyuˇz´ıvaj´ıc´ı vhodnˇe zak´ odovan´ych, explicitnˇe vyj´adˇren´ych speci´aln´ıch znalost´ı, pˇrevzat´ych od experta, s c´ılem dos´ahnout ve zvolen´e probl´emov´e oblasti kvality rozhodov´an´ı na u ´rovni experta.
Hlavn´ı rysy expertn´ıch syst´em˚ u Explicitnˇe reprezentovan´e znalosti, striktnˇe oddˇelen´e od ˇr´ıd´ıc´ıho mechanizmu nakl´ad´an´ı s nimi. Znalosti obsahuj´ı celou ˇsk´alu od nejobecnˇejˇs´ıch aˇz k u ´zce speci´aln´ım, od exaktn´ıch aˇz po osobn´ı heuristiky experta. Znalosti nemaj´ı statick´y charakter, n´ybrˇz se vyv´ıjej´ı a rozr˚ ustaj´ı. B´aze znalosti reprezentuje soubor pravidel, obecnou znalost. ˇ sit konkr´etn´ı pˇr´ıklad znamen´a dosadit data o dan´em Reˇ pˇr´ıpadu do obecnˇe formulovan´ych znalost´ı z b´aze znalost´ı. Mus´ı umˇet pracovat s nejist´ymi znalostmi (od experta) i nejistotˇe o b´azi dat (konkr´etn´ım pˇr´ıpadu). Mˇely by b´yt schopny vysvˇetlit a zd˚ uvodnit sv´e doporuˇcen´ı (i ot´azky). Reprezentace znalost´ı: modularita (logiky, pravidel) se hod´ı pro snadnou u ´drˇzbu, ale tˇeˇzko se v n´ı vyhled´avaj´ı vˇsechny informace relevantn´ı k jednomu pojmu. Z tohoto pohledu jsou lepˇs´ı
S´emantika pravidel
Definition (pravidlo E ⇒ H s vahou W ) Znalost je reprezentov´ana pomoc´ı pravidel E ⇒ H s vahou W , kde E a H reprezentuj´ı element´arn´ı tvrzen´ı. Kaˇzd´e pravidlo m´a pˇriˇrazenou svou v´ahu W - m´ıru, nakolik (jist´a, tj. 100%-n´ı) znalost E podporuje ˇci pop´ır´a platnost tvrzen´ı H. Potˇrebujeme zodpovˇedˇet n´asleduj´ıc´ı tˇri ot´azky. 1
Jak vyj´adˇrit neurˇcitost element´arn´ıho tvrzen´ı?
2
Jak se vyuˇz´ıv´a pravidla, pokud nen´ı splnˇen´ı pˇredpokladu jist´e?
3
Jak se urˇcuje m´ıra d˚ uvery z´avˇeru H v pˇr´ıpadˇe, ˇze existuje v´ıce pravidel se stejn´ym z´avˇerem?
R˚ uzn´e typy reprezentace nejistoty se v odpovˇedi na tyto ot´azky liˇs´ı.
MYCIN, EMYCIN
Pˇr´ır˚ ustek d˚ uvˇery (measure of belief) je definov´an jako MB(H, E ) =
P(H |E ) − P(H) 1 − P(H)
pˇr´ır˚ ustek ned˚ uvˇery (measure of disbelief) je definov´an jako MD(H, E ) =
P(H) − P(H |E ) P(H)
Pokud znalost E podporuje hypot´ezu H, tak se pravdˇepodobnost P(H) mus´ı touto znalost´ı zv´yˇsit, tj. P(H |E ) > P(H), tedy MB(H, E ) > 0, pokud E sniˇzuje d˚ uvˇeru v H, je P(H |E ) < P(H), a tedy MD(H, E ) > 0. Pro kaˇzd´e pravidlo vyˇzadujeme, aby nebyly ˇ obˇe m´ıry r˚ uzn´e od nuly z´aroveˇ n, tj. jednotliv´e pravidlo bud podporuje d˚ uvˇeru v hypot´ezu ˇci ned˚ uvˇeru v n´ı, ale ne oboj´ı z´aroveˇ n.
ˇ Cinitel jistoty (CF)
Na z´akladˇe MB a MD je definov´an ˇcinitel jistoty (certainty factor) CF (H, E ) = MB(H, E ) − MD(H, E ) kter´y nab´yv´a hodnotu od -1 do +1, je-li vˇetˇs´ı neˇz 0 je roven MB, jinak je v absolutn´ı hodnotˇe roven MD. V EMYCIN je ˇcinitel jistoty definov´an trochu jinak: CF =
MB − MD 1 − min(MB, MD)
coˇz umoˇzn´ı snaˇzˇs´ı skl´ad´an´ı pravidel.
Nejist´y pˇredpoklad pravidla
Ani pˇredpoklad pravidla E1 nemus´ıme zn´at s jistotou. Zav´ad´ıme m´ıru jistoty evidence E1 po pozorov´ an´ı E | : CF (E1 , E | ). Pravidlo E1 ⇒ H pak kombinujeme s touto m´ırou jistoty n´asledovnˇe: MB(H, E | ) = MB(H, E1 ) · max {0, CF (E1 , E | )} MD(H, E | ) = MD(H, E1 ) · max {0, CF (E1 , E | )}
Skl´ad´an´ı pravidel
Skl´ad´an´ı pravidel se stejnou hypot´ezou E1 ⇒ H, E2 ⇒ H je v MYCIN definov´ano n´asledovnˇe: MB(H, E1 &E2 ) = MB(H, E1 ) + MB(H, E2 ) − MB(H, E1 ) · MB(H, E2 ) MD(H, E1 &E2 ) = MD(H, E1 ) + MD(H, E2 ) − MD(H, E1 ) · MD(H, E2 ) a dopoˇc´ıtat CF V EMYCIN pˇr´ımo: CF (H, E1 &E2 ) = f (CF ((H, E1 ), CF (H, E2 )) ( x + y − xy pro xy ≥ 0 kde f (x , y ) = x+y jinak 1−min{abs(x),abs(y )}
Skl´ad´an´ı hypot´ez
Pro konjunkci ˇci disjunkci hypot´ez H1 &H2 MB(H1 &H2 , E ) = min{MB(H1 , E ), MB(H2 , E )} MD(H1 &H2 , E ) = max {MD(H1 , E ), MD(H2 , E )} MB(H1 ∨ H2 , E ) = max {MB(H1 , E ), MB(H2 , E )} MD(H1 ∨ H2 , E ) = min{MD(H1 , E ), MD(H2 , E )} Pˇr´ıklad.
PROSPECTOR
Pseudobayesovsk´y model P(H) P(E ) P(¬H) P(¬H |E ) = P(E |¬H) · P(E ) P(H |E ) = P(E |H) ·
Odtud P(H |E ) P(E |H) P(H) = · P(¬H |E ) P(E |¬H) P(¬H) O(H |E ) = L · O(H) O() odds - nadˇeje, pravdˇepodobnostn´ı ˇsance, O(H) apriorn´ı, O(H |E ) aposteriorn´ı L m´ıra postaˇcitelnosti
L=
P(E |H) P(E |¬H)
obdobnˇe m´ıra nutnosti P(¬E |H) b L= P(¬E |¬H) M´ıra nutnosti nelze dopoˇc´ıtat z m´ıry postaˇcitelnosti. Expert ˇLab zad´av´a bud L, nebo pravdˇepodobnosti P(H |E ), P(H |¬E ). Skl´ad´an´ı pravidel pak je trivi´aln´ı: O(H |E1 , E2 , ¬E3 , ¬E4 ) = L1 · L2 · b L3 · b L4 · O(H) Nejist´e pozorov´an´ı nen´ı tak trivi´aln´ı, protoˇze dojde k pˇreurˇcen´ı a je tˇreba aproximovat (my se t´ım zab´yvat nebudeme).
H´ajek 1985 - Abelovsk´e grupy
Pokud jsou k ˇreˇsen´ı u ´lohy k dispozici identick´e znalosti, pak je bez ohledu na pouˇzit´y inferenˇcn´ı mechanismus a na pouˇzitou kombinaˇcn´ı funkci, kter´a je operac´ı na uspoˇr´adan´e Abelovˇe grupˇe ⇒ v´ysledn´e uspoˇr´ad´an´ı c´ılov´ych hypot´ez identick´e. Uspoˇr´adan´a Abelovsk´a grupa Komutativnost Asociativnost Existence neutr´aln´ıho prvku Existence inverzn´ıho prvku Uspoˇr´ad´an´ı Minim´aln´ı a max. prvek + vlastnosti, jejich kombinace nen´ı def.
Success story: Pathfinder
Pathfinder je medic´ınsk´y diagnostick´y syst´em (lymph-node diseases). Mˇel ˇctyˇri verze: 1 pravidlov´ y syst´em zaloˇzen´y na logice, bez nejistoty. 2 zjednoduˇ sen´a Bayesovsk´a s´ıˇt (”naive bayes”) pro klasifikaci: jeden uzel pro klasifikovanou veliˇcinu, z n´ı vede hrana do kaˇzd´e pozorovateln´e veliˇciny, tj. pˇredpokl´ad´ame, ˇze pozorov´an´ı jsou nez´avisl´a. ˇ Castou pˇr´ıˇ cinou nespr´ avn´ e klasifikace bylo, ˇ ze expert pˇriˇradil pravdˇ epodobnost nula nepravdˇ epodobn´ emu, ale moˇ zn´ emu v´ ysledku. 3 zas naive bayes, ale dali si pozor na jevy s n´ ızkou pravdˇepodobnost´ı (´ uspˇeˇsnost 7.9 z 10) 4 modelovali i z´ avislosti mezi pozorov´an´ımi. (´ uspˇeˇsnost 8.9 z 10) - srovnateln´a s dobr´ym expertem.
Pravdˇepodobnostn´ı modely
budou pˇr´ıˇst´ı semestr nyn´ı (na tabuli) naive bayes klasifik´ator
Dempster Shapfer
Dempster-Shafer teorie M´am-li ˇctyˇri moˇzn´e hodnoty veliˇciny, pak mi pravdˇepodobnost neumoˇzn ˇuje reprezentovat znalost: na 50% to udˇelal A nebo B, ale nev´ım kter´y z nich, na 50% to udˇelal C. Pokud bychom to reprezentovali pravdˇepodobnost´ı a dostali informaci, ˇze to A neudˇelal, tak se zv´yˇs´ı pravdˇepodobnost viny C. V Dempster-Shapfer teorii vylouˇc´ıme A, tedy cel´ych 50% pˇrejde na B, a 50% z˚ ustane na C. Definition (z´akladn´ı pˇriˇrazen´ı) Mˇejme mnoˇzinu moˇzn´ych hodnot X. Definujeme z´akladn´ı pˇriˇrazen´ı m: P(X ) → [0, 1], kde m(∅) = 0 a ∑A⊂X m(A) = 1. Vˇsimˇete si, ˇze m definujeme na potenci X, nikoli na X samotn´e.
T´ımto z´akladn´ım pˇriˇrazen´ım je jednoznaˇcnˇe urˇcena m´ıra domˇ en´ı (belief) a plauzibilita (pˇripustitelnost), definovan´e: Bel(A) =
∑
m(B)
∑
m(B)
B ⊂A
Pl(A) =
B ∩A6=∅
tj. souˇcet pˇres vˇsechny B maj´ıc´ı s A nepr´azdn´y pr˚ unik. Bel sumarizuje, nakolik evidence ukazuje na A. Pl ˇr´ık´a, jak bychom vˇeˇrili A, kdyby vˇse nezn´am´e ukazovalo na A. pravdiv´a hodnota je nˇekde mezi.
Pˇr´ıklad
Uvaˇzujme univerzum U = {H, C , P } m({H}) = 0.3 m({H,C}) = 0.2 m({H,C,P}) = 0.5 Pak Bel({H}) = 0.3 Pl({H}) Bel({H,C}) = 0.5 Pl({H,C}) Bel({P}) = 0 Pl({P}) Bel({C}) = 0 Pl({C})
a z´akladn´ı pˇriˇrazen´ı
= = = =
1.0 1.0 0.5 0.7
Dempstrovo kombinaˇcn´ı pravidlo
Pro dvˇe dan´a z´akladn´ı pˇriˇrazen´ı m1 a m2 definujeme jejich kombinaci m1 + m2 (kter´a je tak´e z´akladn´ı pˇriˇrazen´ı) n´asledovnˇe: (m1 + m2 )(A) =
∑X ,Y ;X ∩Y =A m1 (X ) · m2 (Y ) 1 − ∑X ,Y ;X ∩Y =∅ m1 (X ) · m2 (Y )
Pˇr´ıklad
Pro univerzum U = {D, D 0 } a m1 ({D}) = 0.8; m1 ({D’}) = 0; m1 ({D,D’}) = 0.2; m2 ({D}) = 0.9; m2 ({D’}) = 0; m2 ({D,D’}) = 0.1; vytvoˇr´ıme tabulku: m2 0.9 {D} 0 {D’} 0.1 {D,D’} m1 0.8 {D} 0.72 {D} 0 {} 0.08 {D} 0 {D’} 0 {} 0 {} 0 {D’} 0.2 {D,D’} 0.18 {D} 0 {} 0.02 {D,D’} m1 + m2 ({D }) = 0.72 + 0.08 + 0.18 = 0.98 m1 + m2 ( { D 0 } ) = 0 m1 + m2 ({D, D 0 }) = 0.02
Probl´em s normalizac´ı
Counter Intuitive Behavior of Dempster Rule V n´asleduj´ıc´ım pˇr´ıkladu vede Dempstrovo pravidlo k neoˇcek´avan´emu v´ysledku. ˇ ˇ Reknˇ eme, ˇze dva doktoˇri vyˇsetˇrili stejn´eho pacienta, kter´y m´a bud meningitidu (M), concussion (C) nebo n´ador na mozku (tumor) (T). Tedy U = {M,C,T}. Doktoˇri se liˇs´ı v diagnoze: m1 ({M }) = 0.99; m1 ({T }) = 0.01; m2 ({C }) = 0.99; m2 ({T }) = 0.01; Shodnou se na mal´e pravdˇepodobnosti n´adoru T, ale neshodnou se v pravdˇepodobn´e pˇr´ıˇcinˇe. Kombinac´ı n´am vyjde, ˇze ... Jedna moˇznost, jak potlaˇcit takov´eto v´ysledky, je pˇriˇradit i pr´azdn´e mnoˇzinˇe nenulovou m´ıru, kter´a bude urˇcovat m´ıru neshody mezi
