Expertní systémy Algebraická teorie neurčitosti 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 –vychází se systému SAK –práce s neurčitostí v systému SAK vychází z Hájkovy algebraické teorie –jsou tedy definovány kombinační funkce NEG, CONJ, CTR a GLOB –Systém SAK umožňuje volit uživateli mezi dvěma sémantikami inferenčního mechanismu (dvěma “sadami” kombinačních funkcí): 1.standardním 2.logickým Neurčitost v systému NEST csvukrs •- NEG(w) – váha negace výroku •- CONJ(w1,w2) - váha konjunkce výroků v •předpokladu pravidla •- CTR(a,w) - příspěvek váhy předpokladu k váze •závěru pravidla •- GLOB(w1,w2) - kombinování vah pravidel se •stejným závěrem Kombinační funkce v systému SAK csvukrs –NEST (Next Expert SysTem) je rozšířením SAK –Toto rozšíření zahrnuje: •doplnění kombinačních funkcí o výpočet váhy disjunkce, •doplnění neuronové sémantiky kombinačních funkcí, •přechod od bodových vah k intervalům. Neurčitost v systému NEST csvukrs –založen na PROSPECTORovském a MYCINovském přístupu Standardní mechanismus csvukrs –založen na úplné vícehodnotové logice; –základem přístupu ke konstrukci logického inferenčního mechanismu je chápání báze znalostí jako fuzzy axiomatické teorie, tj. teorie, v níž je každý axiom opatřen váhou značící stupeň jeho příslušnosti do fuzzy množiny axiomů teorie; –úkolem inferenčního mechanismu je pak určit, v jakém stupni z této teorie a z dalších předpokladů (odpovědí uživatele v konzultaci) logicky vyplývá každý cílový výrok; –díky úplnosti použité Lukasiewiczowy vícehodnotové (fuzzy) logiky je pak každý logický důsledek teorie odvoditelný důkazem, v němž se používají axiomy teorie a pravidla úsudku. – Logický mechanismus csvukrs Neuronový mechanismus csvukrs •• váha negace výroku •1. NEG(1) = -1, •2. NEG(-1) = 1, •3. NEG(0) = 0, •4. NEG(NEG(w)) = w, •5. w = 0 právě když NEG(w) = 0. Funkce NEG - požadavky csvukrs –Je-li w váha výroku A, pak – – – – – Funkce NEG sémantika funkce NEG(w) standardní —w logická —w neuronová —w csvukrs •Předpokládejme nezaměstnaného klienta žádajícího o půjčku. Tzn., že výrok klient má vysoký příjem by byl ohodnocen vahou -1. Do systému tedy vstupuje tento výrok • •klient má vysoký příjem (-1) • •Jak by se dala vyjádřit váha negace původního výroku, kterou lze formulovat např. jako klient nemá vysoký příjem ? Váha původního výroku je -1, tedy w = -1. Váha negace výroku se spočte pomocí funkce NEG jako • •NEG(w) = NEG(-1) = -(-1) = 1 • •Vypočtená váha výroku klient nemá vysoký příjem je tedy 1, což dobře koresponduje se skutečností, že se jedná o nezaměstnaného klienta. Funkce NEG - příklad csvukrs •• váha konjunkce výroků v předpokladu •1. CONJ(w1,w2) ≤ w1, •2. CONJ(w1,w2) ≤ w2. Funkce CONJ - požadavky csvukrs –Jsou-li w váha výroku A a v váha výroku B, pak – – – – – Funkce CONJ sémantika funkce CONJ(w,v) standardní min(w,v) logická min(w,v) neuronová min(w,v) csvukrs •Předpokládejme klienta, pro kterého platí dva následující výroky s danými vahami • •klient má vysoký příjem (-1) •klient má vysoké konto (1) • •Dále předpokládejme velmi přísnou banku, která klientovi půjčí jedině v tom případě, že klient má jak vysoký příjem, tak vysoké konto. Tento požadavek lze přeformulovat tak, že banka je ochotná půjčit pouze klientovi, který má vysoký příjem a zároveň má vysoké konto (má hodně peněz na účtu). Jak bychom tedy vypočetli váhu následujícího výroku? •klient má vysoký příjem a zároveň klient má vysoké konto •Stačí dosadit do funkce CONJ našeho klienta, tedy v = -1 a w = 1, tzn. •CONJ(-1; 1) = min(-1; 1) = -1 •Váha konjunkce dvou výše zmíněných výroků je tedy -1, tzn. do systému vstupuje (složený) výrok • •klient má vysoký příjem a zároveň •klient má vysoké konto (-1) Funkce CONJ – příklad 1 csvukrs •Předpokládejme dalšího klienta s •klient má vysoký příjem (0,4) •klient má vysoké konto (0,3) • •Vypočtená váha stejného výroku složeného pomocí a zároveň je 0.3. Takovýto klient by měl určitě vyšší šanci na zisk půjčky než první klient, přestože první klient má vyšší konto než tento. • Je důležité si uvědomit, že právě funkce min není použita k výpočtu váhy konjunkce dvou výroků náhodou. Vysoká váha konjunkce dvou výroků náhodou je možná jen v případě, kdy každý z těchto dvou výroků má vysokou váhu. Pokud je jedna z vah nízká, váha konjunkce je také nízká. Toto dobře koresponduje se zažitou představou, že dva výroky platí dohromady pouze v případě, kdy platí jak jeden, tak druhý výrok. • Funkce CONJ – příklad 2 csvukrs •• váha konjunkce výroků v předpokladu •1. DISJ(w1,w2) ≥ w1, •2. DISJ(w1,w2) ≥ w2. Funkce DISJ - požadavky csvukrs –Jsou-li w váha výroku A a v váha výroku B, pak – – – – – Funkce DISJ sémantika funkce DISJ(w,v) standardní max(w,v) logická max(w,v) neuronová max(w,v) csvukrs •Předpokládejme klienta, pro kterého platí dva následující výroky s danými vahami • •klient má vysoký příjem (-1) •klient má vysoké konto (1) • •Dále předpokládejme méně přísnou banku, které pro smluvení půjčky stačí, aby klient měl alespoň vysoký příjem bez nutnosti mít vysoké konto nebo alespoň vysoké konto bez nutnosti mít vysoký příjem (pokud by měl jak vysoký příjem tak vysoké konto, tak to samozřejmě bude stačit také). Tento požadavek lze přeformulovat tak, že banka je ochotná půjčit klientovi, který má buď vysoký příjem, nebo má vysoké konto (nebo samozřejmě obojí). Jak bychom tedy vypočetli váhu následujícího výroku? •klient má vysoký příjem nebo klient má vysoké konto •Stačí dosadit do funkce DISJ našeho klienta, tedy v = -1 a w = 1, tzn. • •DISJ(-1; 1) = max(-1; 1) = 1 • •Váha konjunkce výše zmíněných dvou výroků je tedy 1, tzn. do systému vstupuje (složený) výrok • •klient má vysoký příjem nebo klient má vysoké konto (1) Funkce DISJ – příklad 1 csvukrs •Předpokládejme dalšího klienta s • •klient má vysoký příjem (0,4) •klient má vysoké konto (0,3) • •Vypočtená váha výroku složeného pomocí nebo je 0.4. Takovýto klient by měl určitě nižší šanci na zisk půjčky než první klient, přestože první klient má nižší příjem než tento. •Je důležité si uvědomit, že právě funkce max není použita k výpočtu váhy disjunkce dvou výroků náhodou. Nízká váha disjunkce dvou výroků náhodou je možná jen v případě, kdy každý z těchto dvou výroků má nízkou váhu. Pokud je jedna z vah vysoká, váha disjunkce je také vysoká. To znamená, že disjunkce dvou výroků platní v případech, kdy alespoň jeden z těchto výroků je platný. •Tento a předchozí příklad ilustrují, jak lze pomocí logických spojek (a zároveň, nebo) modelovat např. „přísnost“ banky a jak odlišná volba logické spojky výrazně ovlivňuje výsledek výpočtu, popř. celý rozhodovací proces o smluvení půjčky - dvakrát dva stejní zákazníci, ale vždy zcela opačný výsledek. • Funkce DISJ – příklad 2 csvukrs •CTR(a,w): •• je-li a < 0, pak CTR(a,w) = 0, •• CTR(1,w) = w •• je-li 0 < a < 1, pak CTR je neklesající v a Funkce CTR - požadavky csvukrs –slouží pro určení příspěvku pravidla k váze závěru –pravidlo A —> S (w) přiřadí závěru S váhu w v případě, že A je splněno s jistotou (tak chápe váhu pravidla expert) – Funkce CTR csvukrs •Je-li a váha předpokladu A, pak se váha závěru mění: 1.pro a < 0 : CTR(a,w) = 0 2.pro 0 < a < 1 získáme následující podoby funkce CTR pro různé sémantiky inferenčního mechanismu: – – – – – Funkce CTR sémantika funkce CTR(a, w) standardní a*w logická sign(w)*max(0, a + |w| - 1) neuronová a*w (w nemusí být z [0,1]) a*w sign(w)*max(0, a + |w| - 1) csvukrs •Předpokládejme znovu nezaměstnaného klienta žádajícího o půjčku. Tzn., že výrok klient má vysoký příjem by byl ohodnocen vahou -1. Do systému tedy vstupuje tento výrok • •klient má vysoký příjem (-1) •Předpokládejme velmi jednoduchou bázi znalostí, která obsahuje pouze dvě pravidla •klient má vysoký příjem => půjčíme (1) •klient nemá vysoký příjem => půjčíme (-1) • •kde výrok půjčíme odpovídá situaci, kdy banka klientovi půjčku poskytne. Váhu tohoto výroku chceme odvodit z odpovědí pomocí pravidel. Zatím však o výroku půjčíme nevíme nic. Systém NEST v takovém případě přiřadí výroku neutrální váhu 0, tzn. není ani (trochu) platný ani (trochu) neplatný. •Jak upravíme váhu výroku půjčíme pro našeho klienta na základě jeho odpovědí a naši bázi znalostí? Nejdříve berme v úvahu pravidlo 1). Výrok klient má vysoký příjem má pro našeho klienta váhu -1, tzn. do funkce CTR dosadíme a = -1. Váha pravidla 1) je 1, tzn. w = 1. Tudíž •CTR(a, w) = CTR(-1, 1) = 0, •jelikož a < 0. Příspěvek pravidla 1) k neznámé váze výroku půjčíme je 0, tzn. můžeme ho ignorovat (zatím se spokojíme s tímto faktem bez dalšího vysvětlování a vše si vyjasníme u funkce GLOB), tudíž váha výroku půjčíme je stále 0. Na základě této váhy se nemůžeme ani přiklonit ani odklonit od smluvení půjčky. • Funkce CTR – příklad 1 csvukrs •Nyní vezměme v úvahu pravidlo 2). Výrok klient nemá vysoký příjem má pro našeho klienta váhu 1, což jsme vypočetli pomoci funkce NEG (viz výše), tzn. do funkce CTR dosadíme a = 1. Váha pravidla 2) je -1, tzn. w = -1. Tudíž • •CTR(a, w) = CTR(1, -1) = 1, • •jelikož a > 0. Příspěvek pravidla 2) k váze výroku půjčíme je 1, tudíž novou váhu výroku půjčíme stanovíme na 1. To můžeme provést díky tomu, že váha půjčíme byla doposud rovná 0 (pokud by nebyla rovná 0, použili bychom funkci GLOB, viz níže). Na základě této nové váhy se již můžeme silně odklonit od smluvení půjčky, což reálně odpovídá situaci, kdy nezaměstnaný člověk má je velmi malou šanci na získání půjčky. Funkce CTR – příklad 2 csvukrs •GLOB(w1, w2, …wn) = w1 ⊕ w2 ⊕ ... ⊕ wn •1. ⊕ je komutativní a asociativní, •2. 1 ⊕ w = w ⊕ 1 = 1, pro w ∈ (-1,1], •3. -1 ⊕ w = w ⊕ -1 = -1, pro w ∈ [-1,1), •4. 0 ⊕ w = w ⊕ 0 = w, pro w ∈ [-1,1], •5. w ⊕ -w = 0, pro w ∈ [-1,1], •6. pro libovolné w1, w2, w3 ∈ (-1,1), •jestliže w1 < w2, pak w1 ⊕ w3 ≤ w2 ⊕ w3. Funkce GLOB - požadavky csvukrs –slouží pro skládání příspěvků pravidel se stejným závěrem – –Pro pravidla •A1 —> S (wl) •A2 —> S (w2) •… •An —> S (wn) –která dávají (po aplikaci funkce CTR) příspěvky w1’, w2’, …, wn’ se výsledná váha závěru S odvodí těmito funkcemi: – – – – Funkce GLOB sémantika funkce GLOB(w1’, w2’, …, wn’) standardní GLOB1(w1’, w2’) = (w1’ + w2’) / (1 + w1’ * w2’) logická GLOB2(w1’, w2’, …, wn’) = min(Σwi>0wi ,1) + max(Σwi<0wi, -1) neuronová GLOB3(w1’, w2’, …, wn’) = max(-1, min(1, Σwiwi)) csvukrs Funkce GLOB - ilustrace GLOB1(w1’, w2’) = (w1’ + w2’) / (1 + w1’ * w2’) GLOB2(w1’, w2’, …, wn’) = min(Σwi>0wi ,1) + max(Σwi<0wi, -1) csvukrs •Opět předpokládejme jednoduchou bázi znalostí, která obsahuje čtyři pravidla • 1)klient má vysoký příjem => půjčíme (0,9) 2)klient nemá vysoký příjem => půjčíme (-0,9) 3)klient má vysoké konto => půjčíme (0,5) 4)klient nemá vysoké konto => půjčíme (-0,3) • •Všimněme si dvou pravidel 3) a 4). Váhy již nejsou nastaveny taky (absolutně) vysoce jako u pravidel 1) a 2). Takto lze modelovat situaci, kdy na některých výrocích záleží méně a na některých více. V tomto případě banka klade hlavní důraz na výšku příjmu klienta, zatímco výška konta klienta hraje při rozhodování o půjčce méně výraznou roli. Ilustrujme si to na následujících dvou klientech. • Funkce GLOB – příklad 1 csvukrs •První klient: •klient má vysoký příjem (1) •klient má vysoké konto (-1) •Nenulové příspěvky, jelikož a > 0 (viz funkce CTR), k váze výroku půjčíme plynou z pravidel 1) CTR(1; 0,9) = 0,9 a 4) CTR(NEG(-1), -0,3) = -0,3. Kolik je tedy váha výroku půjčíme? Tento výpočet lze provést pomocí funkce GLOB. Za předpokladu standardního inferenčního mechanismu by výpočet byl proveden následovně. Z pravidla 1) je v = 0,9 a z pravidla 2) je w = -0,3, tedy • •GLOB(v; w) = GLOB(0,9; -0,3) = (0,9 + (-0,3))/(1 + 0,9 * (-0,3)) = 0,82 • Funkce GLOB – příklad 2 csvukrs •Druhý klient: •klient má vysoký příjem (-1) •klient má vysoké konto (1) • •Nenulové příspěvky k váze výroku půjčíme plynou z pravidel 2) CTR(NEG(-1); -0,9) = -0,9 a 3) CTR(1, 0,5) = 0,5. Kolik je tedy váha výroku půjčíme? Tento výpočet lze provést opět pomocí funkce GLOB. Za předpokladu standardního inferenčního mechanismu by výpočet byl proveden následovně. Z pravidla 2) je v = -0,9 a z pravidla 2) je w = 0,5, tedy • •GLOB(v; w) = GLOB(-0,9; 0,5) = (-0,9 + 0,5))/(1 + (-0,9) * 0,5) = -0,73 • Funkce GLOB – příklad 3 csvukrs •U prvního klienta bychom se (jako banka) výrazně přiklonili k půjčce (s vahou 0,82), kdežto u druhého klienta bychom se výrazně (s vahou -0,72) od půjčky odklonili. Na tomto příkladu lze dobře vidět, jak lze modelovat odlišnou důležitost jednotlivých vlastností klienta při rozhodování. Zatímco váhy výroků našich dvou klientů jsou pouze navzájem „prohozeny“, 1 za -1 a naopak, rozhodnutí o půjčce, pokud by záviselo pouze na váze výroku půjčíme, se zcela zásadně liší. • Funkce GLOB – příklad 4 csvukrs –. Neurčitost informace/znalosti je chápána jako stupeň jistoty, že jde o „axiom“ –. Formule reprezentující bázi znalostí a vstupní informace se stupni jistoty z [0; 1] tak tvoří fuzzy axiomatickou teorii –. V úplné fuzzy logice je stupeň dokazatelnosti formule ve fuzzy axiomatické teorii roven stupni její pravdivosti v této teorii –. Inferenční mechanismus je pak dokazovací procedura, která určí stupně logického vyplývání všech cílových formulí z fuzzy teorie reprezentující bázi znalostí a vstupní informace –. Realizace logického inferenčního mechanismu je tedy založena na úplné Lukasiewiczově logice s tím, že každý výrok je reprezentován svou pozitivní verzí (pro kladnou váhu) a negativní verzí (pro zápornou váhu) –. Z pravdivostních funkcí logických spojek a z dedukčního pravidla modus ponens v Lukasiewiczově výrokové logice byly pak odvozeny kombinační funkce pro váhy na intervalu [-1; 1] – Zpracování neurčitosti v úplné fuzzy logice csvukrs Konzultace csvukrs Děkuji za pozornost Některé snímky převzaty od: prof. Ing. Petr Berka, CSc. berka@vse.cz