INFORMATICA 4/1979 OSNOVNI KONCEPTI IN STRUKTURA EKSPERTNIH SISTEMOV M. GAMS N. LAVRAC I. BRATKO* UOK: 519.1 : 681.3 INSTITUT JOŽEF ŠTEFAN, LJUBLJANA * FAKULTETA ZA ELEKTROTEHNIKO, LJUBLJANA V referatu podajano pregled podroBja ekspertnih sfstemov. ki so eno najpomembnejših pod- roen umetne inteligence in ki v zadnjih letih doHivljajo velik kvalitativen in kvantitativen napredek. Referat opisuje osnovne metodoloSke koncepte, strukturoi delovanje in znaBilnosti ekspertnih sistemov. Podaja tudi pregled obstojeBih sistemov z oceno njihovega delovanja in Situacija dolotia pogoje (de katerimi je treba izvesti a lahko trditev ali pa proced datkovno bazo ali npr. usme nizme sistema na aktiviranj znanja. Ekspertni sistemi produkcijske sisteme, to so imajo znanje predstavljeno Oglejmo si enostave oljskega sistema na modelu itevanje temperature med 18 Celzija. eraov temelj i ec if iBn ih zd ja. To znanje je raz- le. Vsak modul vse- n kos znanja o spe- istemov deluje takoi e, da bi ugotovil, i situac i j i v podat- katerega iskalni podatkih, se izvrSi tega modula. Sistemi, ni se imenujejo h sistemih je na j - bI i k i pravi I za enemu modulu). ko akcija finira vzorec)? pod kc i jo. Akcija je ura, ki spremeni po­ ri kontrolne meha- e dolofienega dela pogosto uporabljajo sistemi, ki v obli k i pravi I . n primer produk- termostata za vzdr- in 20 stopinjami • ^ 12 tQQperatura>ia in teciperatura<20 ===> miruj, tBwperatura<10 ===> pok IiCi-popraviloS . vkljutii elektriBno_gret je. te(aperatura<18 in stan je_pee i=ugasn jen ===> priagi pet). , t(?npQrotura>20 in st an je_peB i=pr iiigan ===> ugasni peU. To produkcijski sistem je sest (ftirih pravil. Vsaka lova stran (pogoj doloCo vzorec vnaprej izbranih spreaen SistGCi poiSee pravilot katerega pogoji polnjoni glede na podatkovno išazo. To S5Q sproS i in izvrši se zaporedje akcij definira desna stran pravita. . V tam preprostem primeru termo soo si ogledali samo vloiieno znanjei n tudi njegovo dejansko uporabo. Ta last oraogoea "top-down" pristop in uBinkovi turironje sistema. Pravila v produkcijskih sistem izvajajo v ciklih "razpoznaj-ukrepaj" sliko 1.). No oliki 1 vidimoi kako se izvrSi en oi- kol "razpoznaj-ukrepaj" produkcijskih sistemov. iRtorpreter najprej preglodujei katera pravila isaed množice produkcijskih pravil ustrezajo da- nio podatkom iz podatkovne baze. V naSem primeru pridejo v podtev tri pravila in ta pravila pred­ stavljajo ti. konfliktno situacijo. Kot reSitev koBfliktno situacije se lahko proži veOi obiCajno po oarao GBo pravilo iz konfiiktne množice.' podatkovna bazai C3 Ct C3 avljen iz ) pravila 1 j ivk. so iz- pravilo t ki ga istata le pa nos t "to"struk- ih sB (glej (2) P8 omogoKojo enostavno spreminjanje in doda­ janja pravil« pri tom lahko pravila dodajamo postopoma! (3) grobo gledanoi produkcijska pravila funkcio­ nalno ustrezajo iDodelu ČloveSkcga dolgoroSno- ga spominoi dinamični del podatkov v podat­ kovni bazi pa (JlovekovGfiiu kratkoroBnerau spo- ainu. ' Zanimiva jo ugotovitevg da sistem z doda- joBjeia Bovih pravil obiiiajno pridobi no kvalilotii SQ pa pravila postopoma izločamo is sistemat po dobirao model okrnj enega SloveSkega razmiSljanj o. Pri gradnj i eksper usaerjene v tiimbolj kvalit na specifiBnom problemskem izbrane metode bolj ali ma Izbrano problemsko podro&j Bajobetavnej5i in se pojav nih aplikacij ekspertnih s Prednosti pri uporabi PS s (1) enostavno dodajanje in (2) znanje v obliki pravil topno vsakemu delu pro ' motf sistema! (3) specialni primeri kot trolna struktura onogo ustreznemu problemskem (4) PS' so najmoSnejSe orod znanja na podrotfjihf k v velikera Številu med tlvno neodvisnih pravi (3) PŠ omogoCajo "intelige uporabnikomi saj omogo sklepov« pojasnjevanje Pri tem imajo nekatera mentan drugod pa znaj vasti pravila v naravn tnih sistemov so ciisli etno delovanje sistema podroBju« zato so nj strogo vezane na e. Kljub temu so PS Ijajo v vefiini uspafi- istemov. o predvsem) spreminjanje pravil! je naBeloma vedno dos- raiaa in s tem raste npr. hierarhična kon- Cajo prilagoditev PS u podrofiju! je za predstavitev jer ja znanje zajeto seboj vetiinoma rela- II ntno" komunikacijo z Bajo razlago svojih posameznih pravil itd. pravila priložen ko- o programi sami pro- i jezik. »rodukciiska pravila CiaC2==>Al » C3==>A2 CiaC3=' = >A3 C5==>A3 primerjava množica konfIiktnih pravil reSitev izbrano C3«»=>A2 konf I ikta pravi lo CtaC3==>A3 ooa=o===> C3==>A2 => = C5==>A3 => A2 se i zvrSi RAZPOZNAI^JE ftKCIJA SIika 1» Cikel "razpoznaj-ukrepaj" produkoijskih'sistemov. Produkcijski sistemi so praviloma seve­ da Qnogo kompleksnejši. Nafitejmo le nekaj naj­ bolj pogostih karakteristik! (a) Podatki lahko izpolnjujejo pogoje veB pra­ vil - ta pravila potem tekmujejo za izvajanje. <, (b) Pravilom lahko pridamo faktorje zanes­ ljivosti) tj. Števila na intervalu C-lil3i ki izroSajoi v kolikšni meri zaupamo danemu pravi­ lu. (Vzemimo primer neformalno napisanega pra­ vila iz medicinskega ekspertnega sistema MVCIlMi "Graanegativna paliBasta bakterija v krvi je zolo verjetno (0.8) E.COLl.") (0) Pravila se lahko pri Izvajanju veSejo v bolj sli manj komplicirane strukture (verige), (d) Vr^riženje pravil lahko spremlja metoda za dolofianje faktorjev zanesljivosti verige iz faktorjev zanesljivosti posameznih jiravi• ^ . - "Produlici jski'sistemi so naSli dvoje us- poBnih podroBij uporabe (Davisi77)s za modeli- ronjo SloveSkega mišljenja (PSGiPAS2iVIS..) in v o.kspertnih sistemih (MYCIN)DENDRALiM0L6EN...). Prve uporabe PS za modeliranje BloveS- ttQ(iia oiSljenja so bile raziskave na podroBju Schs in kriptografskih problemov (Simon in Noooll). Po IMeuGllu in Simonu so PS primerni pred- vsGiD zaradi • (1) PS Sio ravno tako splošni kot Turingov stroj in omogoBajo gradnje modelov z raznovrstnimi moiiniostmi procesiranja informaciji Kljub razlikam vsi omenjeni sistemi dajo pod pojem "produkcijski sistemi". spa- fJekateri strokovnjaki kot Neuell (72) glodajo na PS ne samo l v doloBeni meri potr­ juje zgornja razmišljanja. Prav tako je dejst­ vo da je metodologija PS zalo uBInkovito. Ven­ dar ni povsem jasnoi ali uBInkovitosl PS ros iz­ vira iz podobnosti s BlovoSkim rozmiSljanjom in ali bi morali biti zaradi tega tudi inteligen­ tni raBunalniSkI programi podobno grajeni. IzkuSnje kažejo) da je moB ljudi pred­ vsem v specializaciji) v izku3njah In znonju z doloBenega podroBja. Tako je raalo verjetno da bi bil Šahovski velemojster hkrati vrhunski ma- temat.ik ali kemik. "Ekspert" je strokovnjak s 13 specialnim znanjem o svojem podroBjui s special­ nimi, metodami in hevristIkami. Odtod izvira ime "ekspertni si^stemi". -^ ' 3. STRUKTURA IN DELOVANJE EKSPERTNIH SISTEMOV I jeni i (knowle panja ( sistemo vse inf objekt i oz. kda nizmi s znanja bolj sp odvisni V sploSneni so ekspertni sistemi sestav- z baze znania o problemskem podroBju dge base) in ustrezniin mehan izmov sk le- . inferenoe engine). Strukturo ekspertnih v prikazuje slika 2. Baza znanja vsebuje ormaoije o objektih in relacijah med problemskega podrotjja ter navodilai kako j uporabiti posamezne dele znanja, hteha- klepanja pa so algoritmi za uporabo tega pri reSevanju problemov in temeljijo na loSnih in od problemskega podrotfja manj h mehanizmih. I I I baza I I mehanizmi I I I znanja I I sklepanja I I I I I I I ekspertni sistem I __. Slika 2: Osnovna struktura ekspertnih sistemov Znanje v bazi znanja je predstavljeno takoi da omogoBimo uporabniku enostavno vnaSa- njei spreminjanje in dopolnjevanje znanjai r^tzumevanje terrazlago znanja in izpeljanih sklepov (rezultatov). Pogosto vsebuje vse to znanje poseben komun ikaciiski moduli ki amogoSa uporabniku inteligentno interakcijo s ; sistemom v skoraj naravnem jeziku. Delovanje takega sistema .prikazuje slika 3. I strokovnjak I prenos '|' razlaga prenos 'P znanja y I komun i kac i j sk i I I modul I / \ I baza I I znanja !•<- I mehanizmi I -^1 sklepanja I ekspertni sistem Stika 31 Prikaz delovanja ekspertnih sistemov na osnovn sliko 2) in delov E osnovna m nizmi skl ( je sestav ( znanie o i nformao i med temi sistemi t informao i O v danem o procesu s medtem ko v ti. "sp pravi loma modulov nadal j 0 struk ter raz ,n je . kspertn odulai epan j a. a) Baza 1 j ena i al) Zna problem je o ob ob j ekt i udi ti. je o up el speo iperac i j k lepanj je pre edem" s razb i t nji obravnavi se bomo omejili turo ekspertnih sistemov (glej loSfili njihove sasiavne dele e sisteme sestavljata dva (a) baza znanja in (b) meha- znan z (a-1 als. v ski d jekt i i VBa meta la o ) zna sebuj omen 1 h dom sih v -znan orabi tega i f itfnega z skem ciklu ai tvori t ostali del tanju. Spe o v mnoJIlco vzo probl nja i e sex . Tvo ene i sebuj i e I k speč nanj a sist i. "a emsk n (a speč oif ie njo n o e jo i ga if ie • ki ema kt iv if ie no z rBno i domeni 2) podatkov, Ma ga relao1 j ah ekspertn i tvori jo nega znanja. mora biti na voljo v no znanje") nega znanja nan je je voden ih UBinkovit temov je v veliki tega znanja. Znan oblik i modelov> s Izredno zanimiv znanj a v obl ik i E: stroge forAializac Beprav je ie dolofiena veein ustreznih hevrist sistem Se dodatno kovitost delovanj dodatno doloBai k l razbijanje doloBene konfiguracija konfiguracije (razpad atomov povezav podgrafa) (podgraf) DENDRAL deluje v cikllhi sestavljenih iz faz "planiraj In gener1ra j"-"testiraj". Vsako od teh faz izvaja poseben modul. Modul "generi- raj" (CONGEN) je kombinatoriBni algoritem za ge- neriranje vseh topoloSko dovoljenih struktur. Modul "planiraj" (PLANNER) omejuje generiranje struktur glede na podane omejitve. Modul "testi­ raj" (MSPRUNE In MSRANK) nekatere izmed zgene- riranih struktur zavrilei ostale moSne strukture pa razvrsti (oooni) glede na znanje v sistemu. ' . DENDRALova kvaliteta je na ravni najbolj­ ših, strokovnjakov za snovi I za katere ima vlože­ no Se specialno znanje. Za iskanje strukture brez merjenja z instrumenti pa je DENDRAL (oz. CONGEN) bistveno boljSi od Človeka. DENORAL je v ZDA dostopen preko raUunalniSke mreže TVMNET. MYCIN Tudi HVCIN je plod dolgoletnega dela • ntrokovnjakovi ki se je zaHelo leta 1972 v Stanfordu (ShortI iffei76). MVCINova naloga jei da v interaktivni komunikaciji z uporabnikom (zdravnikom specia­ listom) postavi diagnozo povzroBi te I j a infek­ cije krvi in meningitisa in svetuje najboljfio terapijo (doziranje zdravil). Komunikacija poteka v omejeni angleSSini in s standardnimi ukazi. MVCIN vsebuje strokovno zdravniško zna­ nje v obliki produkcijskih pravil kot je npr. ffE! 1) BARVANJE ORGANIZMA JE GRAMNEGATIVNOi IN 2) OBLIKA ORGANIZMA JE PALIflASTAi IN 3) AEROBNOST ORGANIZMA JE AEROBNA POtEM: OBSTAJA VELIKA VERJETNOST (O.B) DA SPADA ORGANIZEM V RAZRED ENTEROBACTERIACEAE. Podatki v podatkovni bazi so Ketvorke oblike) (lastnost objekt vrednost faktor-zaneslj ivosti) Primeri (IDENTITETA ORGANIZEM-1 E.COLI 0.8) EMVCIN je nostal kot MVCINov modul. EHVCIN je ekspertni sistem za gradnjo ekspertnih sistemov. Njegovo delovanje temelji na spoznanju) da je mogoKe z uporabo istega mo­ dula "mehanizmi sklepanja" z zamenjavo baze znanja dobiti nov ekspertni sistem za podobna problemska podrobja. Z uporabo EMVCINa so zgradi­ li veB sistemov! PUFF - program za ugotavljan­ je dihalnih obolenj z merjenjem izdihane sapei HEADHED - program za psihofarmacijsko podroBjes SACOM - program za ugotavljanje najboljših metod za testiranje materialovi itd. PROSPECTOR je ekspertni sistem za odkri­ vanje nahajaliSt! rud in nafte. Znanje v sistemu je podano v obliki pravil« ki so povezana v se­ mantično mrežo. V tipitfni aplikaciji da PROSPECTOR kot rezultat geografsko kartoi na ka­ teri so oznaGene verjetnosti nahajaliSB doloUene rude. Omenimo Se sisteme M0L6EN (svetuje gene- tikoiiii kakSni poskusi pri raziskavah DNA so naj­ bolj obetavni)! AM (poskuSa odkriti nove zanimi­ ve matematiffne koncepte)) MACSVMA (reSuje neka­ tere matematitjne probleme kot so reSevanje dife­ rencialnih enaijbi simboliBno integriranje? itd.)) EL (sistem za diagnostiko električnih vezij)) AGE (sistem z bazo znanja za gradnjo sistemov z bazo znanja)« SU/X (sistem za razpoznavanje identitete objektov v prostoru)) itd. 5. OCENA DELOVANJA EKSPERTNIH SISTEMOV MVCIN deluje po principu "generiraj in testiraj". Sistem iSBe povzročitelja bolezni tako« da primerja iskani organizem z vsemi zna­ nimi organizmi' iz podatkovne baze« pri fiemer MVCIN vsakitf razvije and/or drevo. Produkcijska pravila se torej v tem postopku veSejo v vzvratni sraer i . identiteta povzroB i t.e t j a bolezni (ime bakterije) znatfiIna lastnost tega organizma lastnosti« iz katerih lahko sklepamo na zgornje znaBi t nost i MVCIN preiskuje and/or drevo najprej v globino ("depth- first searoh")« zato za marsi­ kateri organizem že kmalu ugotovi« da ne ustreza« in drevesa ni treba razvijati do konca. MVCIN na svojem podroBju dosega in pre­ sega najboljše zdravnike-specialiste. Ugotovili SO) da zdravniki najveflkrat predpisujejo anti­ biotike preširokega spektra in premalo pazijo na negativne medsebojne vplive zdravil) Besar MVCIN ne dela. Kljub izredni kvaliteti pa MVCIN ni praktiBno v rabi) zlasti zatO) ker zahteva velik raBunatnik in ker je težko sprejemljiv tako bolnikom kot zdravnikom. DENDRAL in MVCIN sta podroCja ekspertnih sistemov« robneje opisali. Navedimo le tfilnejSe primere ekspertnih s META-DENDRAL je nasia Sistem skuSa odkriti nova pra kul v masnem spektrometru, Pr na osnovi primerov spektrov i! Pri kreiranju pravil uporabni sodeluje. T^IR^StAS je popoln jevanj C MVCINa. Sistem dodajanje in spreminjanja pra protislovnosti pravili zfl isk jo napak in pomankI j ivosti v jo nodgradnja nad obiBojnimi klasiBn i deli s zato smo ju pod- Se nekatere zna- istemov. I kot del DENDRALa. vila o razpadu mole- avila SQ kreirajo i e znan ih molekul. k interaktivno nastal pri iz- skrbi za enostavno vili za preverjanj e anjo in odpravljan- praviUh. TEIRESIAB okspartnimi sistemi. Omenili smo žei da je pri gradnji eksper­ tnih sistemov vse podrejeno flimtaoljSira rezultaton in s tem problemski domeni. To pa ne pomenit da metoda ni vaSnai ampak da izbiramo take metoda« od katerih priBakujemo najboljSe rezultate. Prav tako to ne pomenil da so ekspertni sistemi Bista aplikacija teoretiBnih dosevkov) tj. prenos teo­ rije v prakso. Ne - ekspertni sistemi so velik doseifek umetne inteligence in so eno od najbolj ovetotfih podroBij znanosti. (a) Ocena ekspertnih sistemov z znanstvenega staliSBas zof s I ige eksp veSk inte b i t j je e gram da I inte mo n do p v ce znan N ko vp ntni? ertn i ih st I igen a al i ksper in k ahko I igen aredi repr i loti ja. ajpre raSan " Odg sist rokov t en p napr tn i s ot ta do po tno o ti) Banj a zamen J mor je: " ovor emi d n j ako r i sto ave istem k vsa tanko perac Poleg I da j amo amo o Ali s je za osega v na p od Pri t prav j teo st i r i jo ( tega lahko s pre dgov o ek goto jo r podr kate em n zapr ret i az lo tega so poj dsta or i t i spertn vo "Oa aven n o6 j i h.) regako as ne av raB fino pr ilimo v pr i e znanst em int v i t v i j nama i s is ". Na a jbol ki z ti na sme m unaln edv i d sako lovek ven i k e I ige o in loe f ilo- tem i i nte- jboljSi jSih eio- ahtBvajo m znanega ot i t i I da iSki pro- Ijiv« tj. nav idoz u ne more- i priSli nce ckoraj uporabo NajmoSnejSe orodje ekspertnih sisteaovi produkcijske sisteme« so zelo uspeSno uporabili za modeliranje BloveSkega razmišljanja. Tako so na oJfjih podroBjih doslej najuspefineje posnemali tfloveSko obaSanje z vsemi najpomembnejšimi last­ nostmi kot so uBenje« pozabljanje« sklepanjo« ,. razv je d mora glob Beme me I mal i port samo nih ozko npr. o di Eksp oju umet okonBno jo razis a I ne pri r bi Se ki bi na B tovoflk n,i Biflto metodoi metod iz povozon robotsk namik i 1 e r t n i ne i n oprav koval ne ipe I ahko i zre i (bo mi so t omv brati 0 s p 1 eks ccnzo sist t el ig il- t 0 i um Blov pisa dno h 1 jSi) poka QB da tist roblo por In rjih emi ence zmot et ne eSke I i i i tri naB zali mor e sp msk i i si in m so ve (Al) n im p inte go ra nt e I i h raB in ra I da amo p ec ial m pro stem Gtodo I iko p . Njih repr i B Iigeno zm iSl j gentne unaln i zmiSl j no gro oleg b ne met fltorom vsubov zc uB rispevali k ov razvoj anjemi da e odkri t i anj a« a jSe progra- kih pocno- anja. Eks- za ono olj sploff- ode« ki co . Tako moro otI znanj o i nkovi to :16 rokovanje ž njimi. Tudi sistemii ki imajo veliko skupnih lastnosti (npr. MYCIN in DENDRAL oba uporabljata produkcijska pravila) se obiBajno . 'v konkretni izvedbi mobno razlikujejo. Velik korak naprej je bila ugotovitevi d^ ," lahko uporabimo iste mehanizme sklepanja na po­ dobnih problemih s temi da zamenjamo bazo znanja o problemski domeni. nimi dodatki in izboljBavami dajali vedno boljBe rezultate in da bodo v uporabi vsaj Se nekaj deset let. Pri izgradnj i praviloma sodelovalo. ;v najbolj, znanih svet gence. Izdelava takih nekaj deset Blovek-le je gradnja kvalitetni zahtevno delo. Se nek obeta dober skok napr takrat se veliko znan podroliju. To nam doka odkritja (npr. telefo ekspertni sistemi tak zahtevnejših sistemov je veB najboljših strokovnjakov ovnih o etri h umetne i nteI i- . sistemov je vzela nekaj ali t dela. Vse to nam pove< da h ekspertnih sistemov izredno ajs. pogosto se v znanosti ej na dolotienem podroSju in stvenikov loti dela na tem zujejo Številna istoBasna ni itd.). Zdi sei da so tudi o podroCje. Delo na podroBju ekspertnih sistemov je prispevalo k umetmi inteligenci kot znanosti vsaj naslednje! 1. Izdelavo metod za uspeSno predstavi- ,tev in uporabo znanja in s tem tudi za hitrejSo Izdelavo novih ekspertnih sistemov, ' ' Za izdel a^vo . ekspertnega sistema DENDRAL je bilo potrebnih okoli 50-60 filovek-leti za MYC1N 20-30. Ti sistemi so kot pionirski dosevki odprli pot nadaljnemu razvoju. Danes nastajajo manjSi sistemi v nekaj Blovek-mesecih. To pohit- ritev vsaj za faktor 10 so dosegli predvsem z uporabo sploSnejSihi od problemskega prostora s.kora j. neodvisn ih mehanizmov sklepanjai ki omo- goBajo hitro vlaganje specifiBnega problemskega znanja. Lep primer je sistem EMVCINi ekspertni sistem za gradnjo ekspertnih sistemov. Poleg tega so pri.gradnji ekspertnih sistemov razvili mnoifico novih metod za predstavitev in uporabo znanja. Te metode omogofiajo gradnjo modularnih programov » ki jih je enostavno spreminjatii jim dodajati novo znanjei graditi uBeBe se sisteme« itd.. Največkrat pri tem ni Slo za iznajdbo novih metodi ampak za izvirne izboljSave prej ,veBinoma teoretiBnih metod. Ni dovolji da pozna­ mo metodoi dostikrat je pomembnejša konkretna izvedba metodei njena praktiBna uporaba? tako je Se zlasti na podrofiju umetne inteligence. 2. Iz nje z u Pri i i tudi z upora za upo no taki • - sis to lahk jo moin - nj« I iz iran j i v in delavo metod za inteligentno komu- . porabnikom v skoraj naravnem jeziku. zgradnji ekspertnih sistemov so metode za inteligentno komunici- bnikomi saj bi bil sicer celoten rabnika nerazumljiv. Zato imajo sistemi naslednje lastnosti: temi znajo popravljati Brkovne na- o delajo predvsem zatoi ker pred- e odgovore)i hov slovar besed je vezan na ozko o podroBje in je kot tak uporabniku zadosten kljub manjSemu Številu . .n to ira .razvi I ran je sistem obiBaj 'pake ( videva speč i a razumi besed« - sistemi so sposobni pojasnjevati svoje odloBitvei - sistemi znajo odgovarjati na vpraBanja' em delovanju) o vloifenem zanju« itd. v naravnem j ez iku.