Kontrola správnosti - validácia
expertných systémov

Jozef Végh

Peter Veres

Abstrakt

Jeden pohľad na expertné systémy tvrdí, že v podstate táto metodológia je jednoduchou alternatívou tradičného programovania. Jeden prístup navrhuje analogický postup na kontrolu správnosti expertných systémov ako sa používa v tradičnom programovaní. Napriek tomu, že tento prístup je veľmi obmedzený, je pravda, že existujú všeobecne platné pravidlá, ktoré sú aplikovateľné, tak na kontrolu správnosti tradičného spôsobu programovania, ako aj bázy znalostí. Sú to teórie štruktúrovaného programovania, ktoré sa týkajú organizácie, logiky a jednoznačnosti výrazov, či už sú to procedurálne výrazy alebo heuristické pravidlá. Tieto pravidlá slúžia na priame alebo nepriame určenie konzistencie a úplnosti v rámci bázy znalostí.

Mnohé diskusie o kontrole správnosti expertných systémov predstavovali príliš úzke chápanie tejto problematiky, bez globálneho pohľadu. V širšom ponímaní kontrola správnosti expertných systémov musí určiť nasledujúce tri oblasti:

• Fáza prvá: Opodstatnenosť použitia expertného systému
• Fáza druhá: Kontrola konzistentnosti a úplnosti bázy znalostí expertného systému
• Fáza tretia: Overenie celkovej výkonnosti expertného systému

Klúčové slová:
testovanie, opodstatnenosť, konzistentnosť, úplnosť bázy znalostí, identické, konfliktné, obsiahnuté pravidlá, cirkularita, nadbytočnosť, úplnosť, nedosiahnutelnosť, nereferencovatelnosť, neprípustnosť, neurčitosť, výkonnosť ES

Abstract in English

Väčšina ľudí sa nezamyslí nad tým, či použitie daného nástroja je rozumné, praktické a efektívne. V našom prípade, ak niekto sa zaoberá vývojom expertných systémov, automaticky chce daný problém riešiť využitím expertných systémov. Neuvažuje nad použitím iných alternatívnych techník, ktoré môžu v mnohých prípadoch rozumnejšie, praktickejšie a efektívnejšie. Takýto expertný systém , ktorý je vytvorený za každú cenu určite bude schopný dávať odpovede, avšak nikto nezaručí do akej miery možno dôverovať jeho výsledkom. Pri takomto zamýšľaní sa automaticky kladú nasledovné otázky:

• Aké druhy testov treba použiť na overenie správnosti?
• Akým spôsobom sa majú tieto testy vykonať?
• Akým spôsobom by sa mali posudzovať výsledky testov?

Predtým ako sa rozhodnete vyvíjať (kúpiť) takýto systém mali by ste si položiť nasledovných päť otázok:

1. Zaoberá sa programový balík s problémom, ktorý je pre Vás významný a ktorého riešenie (alebo rozšírené riešenie alebo rýchlejšie riešenie) Vám prináša významný úžitok? - Položiť si túto otázku je veľmi racionálne, keďže nie je logické míňať obrovské sumy na riešenie problému, ktorý nie je naozaj dôležitý.
2. Máte niekoho vo vašej organizácii (alebo dostupného externého pracovníka), ktorý má znalosti v oblasti expertných systémov a rozhodovacej analýzy, a ktorý môže poskytnúť objektívne zhodnotenie programového balíku? Ak nie, potom je potrebná zvláštna opatrnosť. Ak áno, potom nasledujúce otázky sa majú byť zodpovedané v spolupráci s ním.
3. Je daný problém, ktorý sa dá ale by mal by byť riešený pomocou expertného systému? Existujú nejaké alternatívne metódy riešenia, ktoré sú vhodnejšie, časovo a finančne menej náročné a potrebujú menej prípravy?
4. Venovali sa tejto problematike aj iní? Ak áno, môžu byť ich výsledky využiteľné?
5. Je jediným významným rozdielom medzi týmto balíkom a ostatnými (ktoré vykonávajú v podstate tú istú úlohu) iba oblasť grafického výzoru aplikácie? Ak áno, potom sú tieto úpravy naozaj dôležité?

Ďalej by ste sa mali spýtať potencionálnych vývojárov alebo dodávateľov balíku nasledujúce otázky:

1. Majú konkrétne všeobecné skúsenosti v oblasti rozhodovacej analýzy a poznajú iné alternatívne prístupy, ktoré sú bežne používané v tejto oblasti?
2. Vedia jednoducho vysvetliť podstatu expertných systémov a ich hmatateľné úžitky (v porovnaní s alternatívnymi prístupmi?
3. Môžu poskytnúť racionálne vysvetlenie prečo dávajú prednosť expertným systémom pred inými alternatívnymi metódami?
4. Či sa už stretli s podobnými prieskumami alebo pokusmi v literatúre? Ak nie, prečo? Ak, áno, aké boli výsledky?
5. Nakoniec, môžu poskytnúť podrobný odhad týkajúci sa nasledovných oblastí:
• očakávané prínosy využívania programového balíku
• očakávané výdavky vývoja a implementácie
• špeciálne požiadavky (napr. nákup LISP zariadenia)
• požiadavka na vyškolenie personálu (výdavky a trvanie takéhoto školenia)
• čas potrebný na vývoj systému a jeho zavedenie do prevádzky

Potom čo sme si už potvrdili, že použitie expertného systému je naozaj opodstatnené a keď sme si vytvorili časť bázy znalostí, t.j. prototyp expertného systému, môžeme pristúpiť k druhej fáze. Konkrétne sa sústredíme na systematické preskúmanie logiky a integrity bázy znalostí.

Niektoré existujúce shell-y expertných systémov zahŕňajú prostriedky na čiastočnú kontrolu znalostí pri vývoji systému. Toto je typicky riešené v editori rámci znalostí a v používateľskom rozhraní shell-u. Napríklad shell EXSYS kontroluje každé pravidlo pri zadávaní na možný výskyt konfliktov medzi zadaným a už existujúcimi pravidlami v báze znalostí. Veľa shell-ov má zabudovaný prostriedok na kontrolu syntax-e, napr. na preskúšanie každého zadaného pravidla pre pravopisné chyby a neošetrené zátvorky. Avšak veľká časť existujúcich shell-ov neposkytuje skutočne vyčerpávajúci a dôkladný prostriedok na validáciu množiny pravidiel.

V polovici osemdesiatych rokoch Nguyen, Perkins, Laffey a Pecora (1985,1987) ohlásili vývoj oveľa lepšieho programu CHECK. CHECK pracuje s bázami znalostí, ktoré obsahujú ak dopredné a spätné zreťazenie, konkrétne s LES (Lockheed Expert System), ktorý je programovým balíkom na vývoj expertných systémov. Tento systém sa zaoberá problémami nekonzistentnosti a úplnosti pravidiel.

Predpokladá sa, že pravidlá sú zoskupené podľa subjektu. V prípade spätného alebo cieľom riadeného odvodzovaniab môže byť množina pravidiel pre každý cieľ nezávisle kontrolovaná. Táto podmienka však nie prísna, ale určite zjednoduší kontrolu pravidiel. Kontrola pravidiel je ešte jednoduchšia ak v predpoklade pravidla sa objavujú iba konjunktívne klauzuly a ak v dôsledku pravidla sa objaví iba jednoduchá klauzula.

V podstate existuje päť druhov nekonzistencií, ktoré môžu byť identifikované:

1. Identické pravidlá
2. Konfliktné pravidlá
3. Obsiahnuté pravidlá
4. Nadbytočné podmienky
5. Cirkularita v reťazi inferencie

{ P(k)} je množina predpokladov pre pravidlo k

{ C(k)} je množina dôsledkov pre pravidlo k

p(k) je jeden predpoklad z množiny { P(k)}

c(k) je jeden dôsledok z množiny { C(k)}

{ S} ={ T} znamená, že množina S sa rovná množine T

Pravidlo 1:

    If A = X And B = Y

    Then C = Z

Pravidlo 2:

    if B = Y and A = X

    Then C = Z And D = W

Definícia: pravidlo r je nadbytočné s ohľadom na pravidlo s ak

        { P(r)} = { P(s)}

        a { C(r)} je podmnožinou { C(s)}

Pravidlo 1:

        If A = X And B = Y

        Then C = Z

Pravidlo 2:

        If A = X And B = Y

        Then C = W

Definícia: pravidlo r je v konflikte s pravidlom s ak

        { P(r)} = { P(s)}

        a { C(r)} je v rozpore s { C(s)}

Pravidlo 1:

        If červené vyrážky And má teplotu

        Then pacient je alergický na liek A

Pravidlo 2:

        If červené vyrážky And má teplotu

        Then pacient je alergický na liek B

To znamená, že obidva lieky môžu vyvolať rovnaké symptómy u pacienta. Takýto výsledok najpravdepodobnejšie znamená, že sme nezadali dostatočný počet symptómov na rozlíšenie dvoch typov alergických reakcií. Avšak môže sa stať, že pacient je alergický na obidva lieky. A tak by bolo vhodné použiť viacero hodnôt pre vyjadrenie dôsledku. Znalostní inžinieri musia určiť prípad, ktorý je pravdepodobnejší a v prípade potreby podľa toho upraviť bázu znalostí.

Jedno pravidlo je obsiahnuté v druhom pravidle, ak obidve pravidlá majú rovnaké dôsledky, ale prvý obsahuje dodatočné (nepotrebné) predpoklady. V nasledujúcom prípade pravidlo 1 je obsiahnuté v pravidle 2.

Pravidlo 1:

        If A = X And B = Y

        Then C = Z

Pravidlo 2:

        If A = X

        Then C = Z

Definícia: pravidlo r je podradené pravidlu s ak

        { C(r)} = { C(s)}

        a { P(s)} je podmnožinou { P(r)}

potom pravidlo r sa odstráni z bázy znalostí.

Pravidlo 1:

        If A = X And B = Y

        Then C = Z

Pravidlo 2:

        If A = X And B = NOT Y

        Then C = Z

Definícia: pravidlo r a s majú nadbytočný predpoklad v klauzule if ak:

        { C(r)} = { C(s)}

        a niektorý p(r) je v konflikte s p(s)

a ostatné predpoklady sú ekvivalentné.

Množina pravidiel je v cirkularite, ak zreťazenie týchto pravidiel vedie k slučke alebo cyklu. Uvažujme príklad nasledujúcich troch pravidiel. V týchto pravidlách predpokladajme nasledovný cieľ: decision. Takže, použitím spätného zreťazenia, najskôr použijeme pravidlo 2, jediné pravidlo obsahujúce decision v dôsledku. Prvý predpoklad pravidla 2 sa nachádza v dôsledku pravidla 1. Takže zreťazíme teraz pravidlo 2 s pravidlom 1. Predpoklad pravidla 1 sa nachádza v dôsledku pravidla 3, pokračujeme použitím pravidla 3. V pravidle 3 je uvedený predpoklad decision = yes. Decision sa zase vyskytuje v dôsledku pravidla 2 - koniec prvého cyklu.

Pravidlo 1 (R1):

        If A = X

        Then B = Y

Pravidlo 2 (R2):

        If B = Y And C = Z

        Then decision = yes

Pravidlo 3 (R3):

        If decision = yes

        Then A = X

Kroky na vytvorenie grafu závislosti pravidiel:

2. Prepoj hranou dva uzly, ak

- jeden alebo viacej predpokladov v jednom pravidle sa nachádza v jednom alebo viacerých dôsledkoch iného pravidla (hrana je orientovaná z prvého do druhého pravidla)

Existuje päť typov úplnosti v báze znalostí:

1. Nereferencované hodnoty atribútov
2. Neprípustné hodnoty atribútov
3. Nedosiahnuteľné okamžité dôsledky
4. Nedosiahnuteľné konečné dôsledky (cieľ)
5. Nedosiahnuteľné predpoklady

R1:

        If úroková sadzba je vysoká

        Then investuj do cenných papierov

R2:

        If úroková sadzba je nízka

        Then investuj do zásob

Z tohto dôvodu by mal byť validačný systém schopný signalizovať znalostnému inžinierovi, ak sa nejaká hodnota atribútu neobjaví v žiadnej podmienke množiny pravidiel. Táto kontrola môže byť dosiahnutá použitím matice, v ktorej riadky znamenajú hodnoty atribútu a stĺpce znamenajú podmienky v pravidlách. Hviezdičkou (*) označíme priesečník každého stĺpca a riadku, ak podmienka v stĺpci obsahuje hodnotu atribútu v riadku. Ak celý riadok v takejto matici je prázdny, to znamená, že zodpovedajúca hodnota atribútu nie je referencovaná. To znamená, že chýba buď pravidlo, alebo podmienka, alebo hodnota atribútu má byť odstránená z množiny prípustných hodnôt atribútu.

Pravidlo:

        If úroková sadzba je veľmi vysoká

        Or inflácia je V

        Then investuj do zlatých zásob

Hodnoty veľmi vysoká pre úrokovú sadzbu a V pre infláciu, nie sú zahrnuté v množine prípustných hodnôt atribútov. Pravidlo musí byť opravené. Takéto neprípustné hodnoty môžu byť odhalené porovnaním všetkých prípustných hodnôt atribútu s hodnotami uvedenými v pravidlách. Ak neexistuje zhoda, potom nastal prípad neprípustnej hodnoty atribútu.

Pravidlo:

        If A = X

        Then R = W

Cieľ je označený ako nedosiahnuteľný (nesplniteľný) ak:

• Neexistuje dotaz pre podmienku cieľa
• A podmienka nemôže byť odvodená z akéhokoľvek iného pravidla (t.j. nenachádza sa v dôsledku žiadneho iného pravidla)

R1:

        If A = U

        Then C = W

R2:

        If C = W

        Then D = X

R3:

        If E = Q

        Then goal = yes

Predpoklad (podmienka) pravidla je nedosiahnuteľný ak:

• Neexistuje dotaz pre predpoklad

• A podmienka nemôže byť odvodená z akéhokoľvek iného pravidla (t.j. nenachádza sa v dôsledku žiadneho iného pravidla)

Pozri pravidlo 3 predchádzajúceho príkladu.

R1:

        If A = X

        Then B = Y

R2:

        If C = W

        Then A = X

R3:

        If E = Q

        Then goal = yes

Matica závislostí pravidiel je nasledovná:

Stĺpce matice určujú dôsledky pravidiel, kým riadky matice určujú podmienky pravidiel.

• Hviezdičkou (*) označíme taký priesečník, ktorého podmienka určená riadkom sa nachádza v dôsledku určeným stĺpcom.
• Krížikom (#) označíme taký priesečník, ktorého dôsledok určený stĺpcom sa nachádza v podmienke určenou príslušným riadkom.
• Hviezdička (*) sa zapíše do stĺpca označeného "Dotaz", ak podmienka pre určený riadok má priradený nejaký dotaz (interakcia s používateľom)
• Písmeno "G" sa má zapísať do takého priesečníka pravidiel, ktorého pravidlo obsahuje cieľ vo svojom dôsledku.

Pravidlá pre určenie úplnosti sú takéto:

• Ak nie je hviezdička (*) v nejakom riadku, potom určená podmienka je nedosiahnuteľná.

Po použití týchto pravidiel, z uvedenej tabuľky môžeme vyvodiť nasledovné:

• Podmienka pravidla 3 je nedosiahnuteľná
• Okamžitý dôsledok pravidla 1 je nedosiahnuteľný
• Cieľ je nedosiahnuteľný

Množina dopredne zreťazených pravidiel, alebo pravidiel riadených údajmi môže byť kontrolovaná podobným spôsobom ako je popísané pri spätnom zreťazení. Jediný rozdiel je v kontrole nedosiahnuteľných okamžitých dôsledkov, nedosiahnuteľných konečných dôsledkov (cieľ), nedosiahnuteľných predpokladoch a cirkularít v reťazi inferencie. V množine dopredne zreťazených pravidiel detekcia týchto štyroch prípadov je neaplikovateľná. Napríklad v pravidlách uvedených v predchádzajúcom príklade je dôsledok pravidla 1 nedosiahnuteľný iba pri použití spätného zreťazenia. Pri použití druhého spôsobu sa môže stať, že hodnota podmienky pravidla 1 (atribút A) je súčasťou dát, teda dôsledok je možné odvodiť.

Faktory dôveryhodnosti slúžia na skomplikovanie procesu validácie expertných systémov. Program CHECK od Nguyen a spol., pracuje s faktormi dôveryhodnosti vo formáte známeho z MYCIN-u.

Mechanizmus určenia identických pravidiel je totožný s už uvedením bez uvažovania neurčitosti. Identické pravidlá, ktoré ostávajú v báze znalostí môžu spôsobiť vážne problémy ak sú použité faktory dôveryhodnosti, z dôvodu že ktorékoľvek pravidlo môže byť použité, čo spôsobuje viacnásobné chybné spočítanie tej istej informácie, ktorá potom chybne zvyšuje konečnú váhu danú všetkými asociovanými dôsledkami.

Pravidlo 1:

        If A = X And B = Y

        Then C = Z (cf = 0.7)

Pravidlo 2:

        If A = X

        Then C = Z (cf = 0.6)

Pravidlo 1:

        If A = X (cf11)

       And B = Y (cf12)

        Then C = Z (cf1)

Pravidlo 2:

        If A = X (cf11)

        And B = NOT Y (cf21)

        Then C = Z (cf2)

Pravidlo 1:

        If A = X (cf11=0.3)

        Then D = W (cf1 = 0.6)

Pravidlo 2:

        If D = W (cf21)

        Then R = Z (cf2)

Ak chceme potvrdiť cieľ R = Z, musíme najprv potvrdiť podmienku D=W v 2. pravidle. D=W sa nachádza v dôsledku 1. pravidla, preto použijeme toto pravidlo. Ak atribút A je zadaný používateľom potom faktor dôveryhodnosti pre pravidlo 1 = 0.6 * 0.3 = 0.18. Ak prahová hodnota je 0.2, potom sme neuspeli pri odvodzovaní.

R1:

        If A = X

        Then B = Y (cf)

R2:7

        If B = Y

        Then goal = yes (cf)

Fáza tretia: Overenie celkovej výkonnosti expertného systému

Primárne kroky pri overení sú nasledovné:

• Aká je presná určená úloha expertného systému ?
• Aké špecifické kritériá by mali byť použité na vyhodnotenie dôsledkov dosiahnutých expertným systémom ?
• Ako by mali byť tieto kritériá pozbierané ?
• Na akom princípe by mali byť výsledné kritériá vyhodnotené ?

Úloha expertného systému by mala byť samozrejme určený už predtým ako sme sa ho odhodlali vyvíjať. Expertný systém poskytuje expertovi rady na nejakom špecifikom poli nasadenia systému. Úlohou je zdokumentovať presné ciele a požiadavky na daný systém.

Ak úloha expertného systému je už zdokumentovaná, potom určenie kritérií, ktorými sa daný expertný systém bude posudzovať je značne ľahšou úlohou. Zavedie expertného systému má vplyv na nasledujúce oblastia: produktivita, organizácia a personál. Tieto dopady do týchto oblastí sa dajú ďalej deliť takto:

• Vplyv na produktivitu
• Presnosť riešenia
• Zlepšenie voči už existujúcim prístupom
• Výpočtové hľadisko (doba výpočtu, požiadavky na uloženie údajov)
• Ľahké zaobchádzanie so systémom, update a revízie
• Jednoznačnosť výstupov
• Vhodnosť výberu softwaru/hardwaru
• Vplyv na organizáciu
• Výdavky na software a hardware
• Znižovanie nákladov
• Potenciálny profit
• Reorganizácia a požiadavky na personál
• Vplyv na personál
• Morálny
• Požiadavky na vzdelanie
• Rozšírenie/zúženie pracovných možností

Jedným spôsobom zberu údajov je získať údaje z minulého obdobia v organizácii. S týmito údajmi sa potom testuje expertný systém. Kontroluje sa správnosť výsledkov. Druhou alternatívou je testovanie s množinou skúšobných prípadov (pripraví ich expert, ktorý navrhol aj bázu znalostí). Treťou alternatívou je spustenie paralelne existujúceho systému a expertného systému a porovnanie ich výsledkov.

Typické, ale zďaleka nie perfektné vyhodnotenie výkonnosti systému je použitie metodiky zvanej cost-benefit (zefektívnenie nákladov). Podmienka takejto metodiky je ten, že je nutné nejakým spôsobom skombinovať rôzne mierky (kritériá) výkonnosti do jednej jednotky merania výkonnosti.

Zápory takéhoto prístupu sú:

1. Tento základný predpoklad je beznádejne idealistický (t.j. že sa nájde spoločná jednotka merania výkonnosti)

2. Viacero mierok výkonnosti sa nedá spolu skombinovať (napríklad ohodnotenie ľudského života v dolároch)

3. Kombinácia množstva rôznych mierok, z ktorých každá je zaťažená nejakou chybou, spôsobí agregáciu chýb vo výslednej agregovanej mierke.

Bibliografia

Ignizio. An Introduction To Expert System - Chapter 8 - Validation.

Znalostné systémy
Zimný semester 1998/99