69 UPORABA PREDZNANJA INFORMATICA 4/91 V INDUKTIVNEM UČENJU Keywords: machine learning, inductive Nada Lavrač learning, background knowledge, inductive Istitut Jožef Stefan logic programmnig Večina uveljavljenih metod za avtomatsko zajemanje znanja temelji na avtomatskem učenju iz primerov in uporablja atributni jezik za predstavitev primerov in naučenih konceptov. Atributni jezik je zelo omejen, saj ne omogoča opisovanja kompleksnih strukturiranih objektov ter relacij med objekti. V zadnjem času gre vse več pozornosti sistemom za avtomatsko učenje, ki uporabljajo izraznejše jezike prvega reda za predstavitev naučenih konceptov. Ti jeziki omogočajo uporabo relacij, ki izražajo predznanje o učnih primerih in domeni sami. Induktivno avtomatsko učenje relacij imenujemo tudi induktivno logično programiranje. V članku opišemo različne načine uporabe predznanja v atributnem učenju in v učenju relacij. Opišemo tudi uporabo predznanja v sistemu induktivnega logičnega programiranja LINUS. Na kratko predstavimo dve aplikaciji tega sistema. THE USE OF BACKGROUND KNOWLEDGE IN INDUCTIVE CONCEPT LEARNING Inductive concept learning is most frequently used for automatic knowledge acquisition. Most of the successful inductive learning methods use a propositional attribute-value language for the representation of training examples and concepts. This language is limited and does not allow for representing complex structured objects and relations among objects. The goal of a new research area named Inductive Logic Programming (ILP) is to develop systems which can learn relational descriptions of concepts in a firstorder language of logic programs. A first-order language allows for describing relations which- express experts' background knowledge about training examples and the domain as a whole. The paper describes the ways of using background knowledge in inductive concept learning, both in learning attribute and relational descriptions. Furthermore, the ways of using background knowledge in the system LINUS is described. LINUS is an integrated inductive learning environment which can be used for learning attribute descriptions using background knowledge, as well as for inductive logic programming. Two applications of LINUS are briefly described: learning rules for early diagnosis of rheumatic diseases and learning illegal chess endgame positions. 1. Uvod V svojem razvoju je umetna inteligenca prišla do stopnje, ko so njene metode, tehnike in orodja postale splošno uporabne v raznovrstnih računalniških aplikacijah. Med njimi so najbolj znani, najuspešnejši in zato tudi komercialno najbolj zanimivi ekspertni sistemi (Jackson 1990), ki v izvrševanju nalog na ozkem problemskem področju dosegajo raven vrhunskih strokovnjakov - ekspertov. 'Inteligenca' ekspertnega sistema temelji na bazi znanja, specifični za konkretno problemsko področje. Proces izgradnje baze znanja je najtežavnejša faza v razvoju ekspertnega sistema in je znana pod imenom 'Feigen-baumovo ozko grlo'. Dolgotrajnost in težavnost konstrukcije baz znanja sta bila povod za številne 70 raziskave, katerih cilj je olajšati in pospešiti proces zajemanja znanja za ekspertne sisteme. Večina uveljavljenih metod za avtomatsko zajemanje znanja temelji na avtomatskem učenju iz primerov. V tem pristopu iz danih primerov ekspertnih odločitev z induktivnim sklepanjem izpeljemo splošna pravila. Tudi sam ekspert včasih najlaže posreduje svoje znanje s pomočjo dobro izbranih primerov. Večina praktično uporabnih sistemov za avtomatsko učenje, kot na primer ASISTENT (Cestnik, Kononenko in Bratko 1987), uporablja atributni jezik za predstavitev primerov in naučenih konceptov (opisov razredov). Pri teh sistemih so primeri predstavljeni z 7i-tericami vrednosti atributov ter ustreznim razredom, medtem ko so naučeni koncepti opisani z odločitvenimi drevesi ali z if-then pravili. Vse informacije o domeni so vsebovane v učnih primerih. Atributni jezik je zelo omejen, saj ne omogoča opisovanja kompleksnih strukturiranih objektov ter relacij med objekti. Zato obstaja vrsta nalog, ki jih z atributnim učenjem iz primerov ni mogoče rešiti. S problemom omejenosti opisnega jezika se lahko spopademo na več načinov: • Metode za konstruktivno učenje omogočajo, da sistem avtomatsko konstruira nove, sestavljene izraze. V interakciji s sistemom ekspert izbere in poimenuje tiste od predlaganih avtomatsko konstruiranih izrazov, ki bi jih bilo smiselno uporabiti v učenju opisov konceptov. • Nove izraze lahko na osnovi svojega znanja o problemski domeni predlaga ekspert. Ekspert lahko torej poda svoje predznanje (angl. background knowledge) kot funkcije vrednosti obstoječih atributov lahko pa poda tudi smiselne relacije med objekti problemskega prostora. • Moč atributnega jezika lahko povečamo tako, da izberemo izraznejši logični jezik prvega reda za predstavitev naučenih konceptov. V zadnjem času gre vse več pozornosti sistemom za avtomatsko učenje, ki uporabljajo izraznejše jezike prvega reda za predstavitev naučenih konceptov. Ti jeziki omogočajo uporabo relacij, ki izražajo predznanje o učnih primerih in domeni sami. Medtem ko je v atributnih jezikih naloga učenje opisa razredov iz učnih primerov, je v relacijskih jezikih naloga učenje logičnih definicij relacij iz primerov ter predznanja. V relacijskem učenju šo učni primeri opredeljena dejstva oz. n-terice vrednosti argumentov relacije, katere definicije se hočemo naučiti. Po analogiji z razredom je vsak učni primer označen z ©, če pripada, oz. z Q, če ne pripada dani relaciji. Predznanje je tudi izraženo v obliki relacij, ki so podane s pripadajočimi n-tericami, ali pa z logičnimi definicijami (programi) v programskem jeziku prolog. Ker so naučene definicije relacij tudi izražene kot logični programi, induktivno avtomatsko učenje relacij imenujemo tudi induktivno logično programiranje (Muggleton 1991). V članku upišemu različne načine uporabe predznanja v atributnem učenju in v učenju relacij. V drugem razdelku definiramo problem induktivnega učenja konceptov. S primeri predstavimo naloge atributnega učenja, atributnega učenja '/. upoštevanjem predznanja ter učenja relacij v induktivnem logičnem programiranju. V tretjem razdelku obravnavamo uporabo predznanja v sistemu induktivnega logičnega programiranja LINUS. Na kratko opišemo algoritem in dve ap-lika.ciji sistema LINUS: učenje medicinskih diagnostičnih pravil v revmatologiji ter učenje relacij v šahovski končnici. 2. Induktivno učenje konceptov Koncept C lahko definiramo kot podmnožico prostora objektov. Induktivno učenje konceptov pomeni metodo učenja iz primerov, ki omogoča razpoznavanje objektov v C. Učni primer za učenje koncepta C je par: (Objekt, Razred) kjer je Objekt izbrani opis objekta, Razred pa © ali 0, kar označuje, da Objekt pripada ali ne pripada konceptu C. Učni primer je pozitiven, če Objekt pripada konceptu C (Razred = ©) in je negativen primer ali protiprimer, če ne pripada C (Razred = 0). Namesto da bi dani objekt klasificirali v enega od dveh razredov © and 0, ga lahko klasificiramo v enega od več medsebojno izključujočih se razredov Cc, c — 1,..., A'. Problem induktivnega učenja konceptov lahko formalno definiramo takole (de Raedt 1991): 71 al a2 a3 . Razred Al A2 A3 A4 A5 Razred, primeri vi2 primer2 v2i v22 v23 primer3 ......... Ci C2 Tabela 1: Množica primerov, zapisana v obliki tabele. da balon da kvadrat kvadrat P da zastava da osmerokoinik osmerokoinik P da meč da krog osmerokoinik N da meč ne kvadrat osmerokoinik N ne meč ne osmerokoinik krog N ne zastava ne krog osmerokoinik N Podani so: • jezik za opis primerov Le • množica pozitivnih primerov p • množica negativnih primerov N • jezik za opis konceptov Lc • relacija pokritosti med Lc in Le • kriterij kvalitete definiran na nizih iz Lq Poišči: • opis koncepta C iz Lc, ki zadošča kriteriju kvalitete Kriterij kvalitete lahko zahteva, da je zgrajeni opis koncepta konsistenten in popoln glede na dano množico primerov. Opis koncepta je konsistenten, če ne pokriva nobenega negativnega primera. Opis je popoln, če pokriva vse pozitivne primere. Zahtevo po konsistenstnosti in popolnosti moramo omiliti, ko se učimo iz šumnili in nepopolnih podatkov. Tako lahko preprečimo, da bi sistem zgradil preveč specifične opise konceptov. Glede na izbor jezika za opis konceptov in primerov ločujemo dve glavni področji v induktivnem učenju: atributno učenje in učenje relacij. Tabela 2: Primeri prijaznih (P) in neprijaznih (N) robotov. if (A{ = Vi) A (Aj — Vj) A ... then Razred — Cc ki je konsistentno in popolno glede na dano množico primerov. Naučena if-then pravila opisujejo posamezne razrede. Sistemi pa se lahko naučijo tudi opisa vseh razredov v obliki odločitvenega drevesa, katerega listi označujejo posamezne razrede. Za ilustracijo učenja odločitvenih dreves izberimo primer iz sveta prijaznih in neprijaznih robotov (Wnek, Sarma, Wahab in Michalski 1990, Sutlič 1991). Opis robota je podan z naslednjimi atributi in njihovimi vrednostmi: Al - se smeji: da, ne A 2 - drži: balon, zastava, meč A 3 - ima kravato: da, ne Al) - oblika glave: krog, kvadrat, osmerokoinik A 5 - oblika telesa: krog, kvadrat, osmerokoinik 2.1 Induktivno učenje atributnih opisov konceptov V atributnem učenju so primeri predstavljeni z 7i-tericami vrednosti atributov ter z ustreznim razredom. Objekt lahko pripada enemu od N medsebojno izključujočih se razredov Cc. Množico primerov (Objekt, Razred) lahko predstavimo s tabelo 1. Naloga atributnega učenja je poiskati klasifikacijsko pravilo (hipotezo, opis koncepta) kot funkcijo vrednosti atributov, ki ga lahko uporabimo za napovedovanje razreda neznanega objekta. Naučeni opis koncepta ima lahko obliko if-then pravila: V tabeli 2 je podanih šest učnih primerov. Za vsako 5-terico vrednosti atributov je podan razred, ki določa, ali je robot prijazen ali ne. Naloga učenja je poiskati pravilo, ki opredeli, ali je robot prijazen ali ne. Za učenje odločitvenih dreves lahko uporabimo sistem ASISTENT (Cestnik, Kononenko in Bratko 1987). Naučeno odločitveno drevo je prikazano na sliki 1. Opišimo Quinlanov algoritem ID3 (Quinlan 1986), ki je osnova algoritma ASISTENT. Naj bo S množica učnih primerov, C\,...Cn pa odločitveni razredi. • če vsi primeri iz S spadajo v isti razred Cc • potem označi list drevesa s Cc • sicer 72 Slika 1: Odločitveno drevo, zgrajeno s sistemom ASISTENT iz šestih primerov robotov. • izberi 'najinformativnejši' atribut A z vrednostmi vi,.. ,,vn • razdeli učno množico Sv Si,..., Sn glede na vrednosti v\,...,vn • rekurzivno zgradi poddrevesa Ti,..., Tn za S\,..., Sn • zgradi odločitveno drevo T, kot je prikazano na sliki 2. Slika 2: Odločitveno drevo, ki ga zgradi ID3. Preiskovalna hevristika algoritma je določena z in-formativnostjo atributa, ki se izračuna na osnovi entropije učne množice E(S), ki izraža količino informacije, potrebne za klasifikacijo enega objekta: N E(S) = - ^Pc-logiVc C—1 kjer je pc apriorna verjetnost razreda Cc (izračunana z relativno frekvenco razreda Ccv S). Entropija učne množice po razbitju po vrednostih vi,...,vn atributa A je: E(S/A) = -±Pv.jrPf.lo92Pf V=1 c=l Pv Pv kjer je pv apriorna verjetnost, da ima A vrednost Vvi Pvc pa je apriorna verjetnost, da ima primer, ki spada v razred Cc, vrednost vv atributa A. Informativnost atributa 1(A) je mera, ki mini-mizira število testov, potrebnih za klasifikacijo novega objekta: 1(A) - E(S) - E(S/A). Najinformativnejši atribut je tisti, pri katerem doseže informativnost maksimum max 1(A), kar je ekvivalentno minimizaciji entropije min E(S/A). V sistemu ASISTENT je bil algoritem ID3 izboljšan na več načinov. Omogoča obravnavo manjkajočih podatkov, obravnavo numeričnih (zveznih) vrednosti atributov, obravnavo NULL listov, v katere ne spada noben učni primer, obravnavo SEARCH listov, v katere spadajo primeri iz več različnih razredov, binarizacijo atributov, ter obravnavo netočnih podatkov, tako da vpelje rezanje dreves; rezanje omogoča izgradnjo manjših drevesa, ki so lažje razumljiva in imajo večjo klasifikacijsko točnost. Drugi primeri sistemov, ki se učijo opisov konceptov v obliki odločitvenih dreves so npr. C4 (Quinlan et al. 1986) in CART (Breiman et al. 1984). Primeri sistemov, ki se učijo if-then pravil pa so AQ15 (Michalski et al. 1986), njegov predhodnik NEWGEM (Mozetič 1985), CN2 (Clark in Niblett 1989) ter GINESYS (Gams 1989). 2.2 Uporaba predznanja v atributnem učenju Kot smo omenili v uvodu, lahko sistem v naučenih pravilih upošteva nove izraze, ki mu jih na osnovi svojega znanja o problemski domeni predlaga ekspert. Pri odločanju in pri razlagi odločitev eksperti namreč uporabljajo svoje znanje o problemu. To znanje je mogoče izraziti kot funkcije vrednosti atributov (s katerimi so opisani učni primeri) ali pa z relacijami med atributi ali objekti problemskega področja. To ekspertovo znanje, imenovano predznanje (angl. background knowledge), lahko sistem koristno uporabi pri učenju kompleksnejših relacij. Predznanje lahko sistem uporabi kot pomožno znanje v atributnem učenju. V učenju relacij pa postane relacijsko predznanje bistvenega pomena za učenje. V atributnem učenju sistem upošteva predznanje tako, da za vsak nov (sestavljen) izraz, podan v predznanju, vpelje nov atribut. Če poda ekspert svoje znanje v funkcijski obliki, se za posamezni 73 .4/ A Ž A 3 A 4 A 5 A 6 Razred da balon da kvadrat. kvadrat da ]' da zastava da osmerokotnik osmerokotnik da P da meč da krog osmerokotnik ne N da meč ne kvadrat osmerokotnik ne N II C meč ne osmerokotnik krog ne /V n e zastava ne krog osmerokotnik ne N Tabela 3: Primeri prijaznih (P) in neprijaznih (N) robotov. V stolpcu /16 so podane vrednosti novega atributa oblika gluve = oblika telesa. Slika 3: Odločitveno drevo, zgrajeno s sistemom ASISTENT iz šestih primerov robotov z uporabo predznanja. učni primer vrednost novega atributa izračuna kot funkcija- vrednosti osnovnih atributov. Če pa je predznanje podano v obliki relacij, ima novo vpeljani atribut vrednost 'true, v kolikor vrednosti ustreznih atributov primera ustrezajo relaciji, sicer ima vrednost Jalte. V primeru iz sveta robotov vpeljimo en sestavljen izraz, s katerim testiramo relacijo enakosti: oblika glave = oblika telesa. S tem smo vpeljali nov atribut /16 z naborom vrednosti da (true/resnično) in ne (f al se/ni resnično). Množico učnih primerov, dopolnjeno z vrednostmi novega atributa .46, prikažemo v tabeli 3. V gradnji odločitvenega drevesa iz primerov podanih v tabeli 3 se novi atribut /16 izkaže kot najbolj inlormativen, zato se pojavi v korenu drevesa zgrajenega s sistemom ASISTENT. Ker vrednosti atributa /16 v celoti ločita med prijaznimi in neprijaznimi roboti, je to tudi edini atribut v zgrajenem drevesu. Drevo je podano na sliki 3. Iz primera je razvidno, da je lahko atribut, ki je zgrajen na osnovi predznanja, bolj informativen kot so osnovni atributi. Z uporabo predznanja lahko zgradimo kompaktnejše opise konceptov, ki imajo lahko večjo klasifikacijsko točnost. 2.3 Induktivno logično programiranje V učenju relacij učni primeri izražajo relacije med elementi problemskega prostora (objekti), podano pa je tudi dodatno problemsko znanje (predznanje) o učnih primerih in domeni sami. Medtem ko je v atributnih jezikih naloga učenje opisov konceptov (razredov) iz učnih primerov, je v relacijskih jezikih naloga učenje logičnih definicij relacij iz primerov in predznanja. Nalogo učenja relacij v jeziku prvega reda lahko formuliramo takole: Podani so: • jezik za opis primerov L£ • množica pozitivnih in negativnih primerov (dejstev © in Q) neznane relacije p • jezik za opis konceptov Lc, ki določa sintaktične omejitve za definicijo predikata p • jezik za opis predznanja Lb • predznanje - množica definicij pomožnih predikatov in funkcij r/., ki jih lahko uporabimo v definiciji predikata p • relacija pokritosti med Lc in LE glede na Ly • kriterij kvalitete definiran na* definicijah predikatov iz Lc Poišči: • definicijo ciljnega predikata p kot množico stavkov iz Lc, ki zadošča kriteriju kvalitete Množica pozitivnih (®) in negativnih (9) primerov je podana z opredeljenimi dejstvi (angl. ground facts), kar pomeni, da so podane vrednosti argumentov relacije, t.j., da v argumentih relacije ne nastopajo spremenljivke. Predznanje je podano z funkcijami in relacijami, ki vsebujejo informacijo o argumentih ciljne relacije p. Naloga učenja je poiskati definicijo relacije p v odvisnosti od relacij iz predznanja, ki bo ustrezala kriteriju kvalitete, npr. ki bo popolna in konsistentna glede na dana dejstva. Definicija je popolna, če razlaga (pokriva) vsa pozitivna dejstva, konsistentna pa, če ne pokriva nobenih negativnih dejstev. Naučena definicija predikata p sestoji iz množice stavkov oblike p{.Vi, A'2, • • •, Xk) <- Lu. . ,,Ln kjer je telo stavka koujunkcija litera.lov L, = v,-(Vi, y2,..., V,,,). 74 Ilustrirajmo zgornjo definicijo na preprostem problemu učenja družinskih relacij (Džeroski 1991). Naj bo ciljna relacija daughter in naj bo predznanje sestavljeno iz relacij female in parent. Za relacijo daughter so podani štirje učni primeri: dva pozitivna in dva negativna. daughter(maja,ana). © daughter(eva,tom). © daughter(tom,ana). 0 daughter(eva,ana). 0 Podano je naslednje predznanje: parent(ana,maja). female(ana). pareni(ana, torn). female(maja). parent(tom,eva). female(eva). parent(tom, ivo). Iz učnih primerov in predznanja se je mogoče naučiti definicije predikata daughter: daughter(X,Y) female(X),parent(Y,X). Naučene definicije relacij so podane s programskimi stavki v sintaksi programskega jezika prolog. Definicijo lahko v kompleksnejših primerili sestavlja več programskih stavkov (angl. program clauses). Množico stavkov z istim predikatom v glavi stavka imenujemo definicija predikata (angl. predicate definition). Definicija predikata tvori prologovo proceduro oziroma prologov logični program. Sistemi, ki se učijo logičnih programov, spadajo med sisteme induktivnega logičnega programiranja (ILP). Induktivno logično programiranje je mlado raziskovalno področje. V svetu so bile prve raziskave s tega področja opravljene leta 1981, ko je bil razvit sistem MIS (Model Inference System, Shapiro 1981), ki se zna učiti logičnih programov, temu pa so sledili sistemi MARVIN (Sammut in Banerji 1986), CIGOL (Muggleton in Buntine 1988), GOLEM (Muggleton in Feng 1990) in FOIL (Quinlan 1990). Področje je dobilo svoje ime šele leta 1990, prva delavnica (First International Workshop on Inductive Logic Programming) pa je bila marca 1991. Področje ILP je razvito tudi v Sloveniji. Razvita sta bila ILP sistema LINUS (Lavrač 1990) in mFOIL (Džeroski 1991), ki sta bila uporabljena v več domenah, znanih iz literature o avtomatskem učenju (Lavrač, Džeroski in Grobelnik 1991), za učenje medicinskih diagnostičnih pravil na področju revmatologije (Lavrač, Džeroski, Pirnat in Križman 1991), za učenje načrtovanja mrež končnih elementov (Džeroski in Dolšak 1991) ter za učenje iz šumnih podatkov (Lavrač in Džeroski 1991, Džeroski in Lavrač 1991a). Teoretično primerjavo sistemov LINUS in FOIL smo podali z grafi specializacije (Džeroski in Lavrač 1991b). ILP pristop je bil uporabljen tudi za učenje kvalitativnih modelov (Bratko, Muggleton in Varšek 1991). 3. Uporaba predznanja v integriranem okolju za avtomatsko učenje LINUS Sistem induktivnega logičnega programiranja LINUS (Lavrač 1990, Lavrač, Džeroski in Grobelnik 1991) temelji na ideji, da je možno transformi-rati problem učenja relacij v problem atributnega učenja z uporabo predznanja. Na ta način lahko uporabimo obstoječe atributne učne algoritme, npr. sistem ASISTENT, ki so že dosegli veliko stopnjo uporabnosti in znajo obravnavati nepopolne in šumne podatke. Sistem LINUS omogoča uporabo dodatnega problemskega znanja v učenju opisov konceptov (opisov posameznih razredov objektov) ali učenju logičnih definicij relacij med objekti problemskega prostora. V sistemu LINUS opišemo učne primere in naučena pravila v jeziku deduktivnih hierarhičnih baz podatkov (DHBP), t.j. v logičnem jeziku prega reda, ki je izraznejši od atributnih jezikov 0-tega reda, ki jih uporablja večina uveljavljenih sistemov za induktivno učenje. Izbor tega preprostega jezika prvega reda omogoča sistemu LINUS, da z uporabo atributnih učnih algoritmov učinkovito zgradi logične opise relacij. Stavki DHBP so omejena oblika programskih stavkov; prepovedani so rekurzivni stavki, spremenljivkam pa so pridružene ustrezne končne zaloge vrednosti (tipi). Dodatna omejitev LINUSu onemogoča uvajanje novih spremenljivk v telo stavka. Predznanje je pri LINUSu izraženo v formalizmu deduktivnih baz podatkov (DBP), ki dovoljuje rekurzivne definicije predikatov. Sistem LINUS vključuje tri atributne učne algoritme ASISTENT, NEWGEM in CN2. ASISTENT je predstavnik TDIDT (Top-Down Indue- 75 tion of Decision Trees) družine učnih algoritmov (Quinlan 1986). NEWGEM je član družine AQ algoritmov (npr. Michalski et al. 1986). CN2 združuje najboljše lastnosti ID3 in AQ algoritmov s tem, da dovoli uporabo statističnih metod, podobnih rezanju drevesa, in da generira if-then pravila. 3.1 Opis algoritma LINUS Program, ki omogoča vključitev sistema LINUS v okolje logičnega programiranja imenujemo DHBP vmesnik. Program je implementiran v prologu. Vmesnik pretvori pozitivna dejstva in negativna dejstva (negativna dejstva so podana ali pa jih generira DIIBP vmesnik) iz DHBP oblike v obliko 7i-teric vrednosti atributov, atributni učni algoritem se nauči opisa koncepta v atributnem jeziku, DHBP vmesnik pa pretvori te opise v obliko DHBP stavkov. Najpomembnejši del DHBP vmesnika je generiranje novih atributov za učenje. Z upoštevanjem zaloge vrednosti tipov argumentov ciljne relacije namreč preveri, katere so možne aplikacije pomožnih predikatov in funkcij iz predznanja ter le-te upošteva kot dodatne atribute, ki jih bo uporabil v učenju. Vsak učni primer dopolni z vrednostmi teh dodatnih atributov, to je z vrednostmi da (true) ali ne (false) za pomožne predikate, oziroma z vrednostmi izhodnih argumentov za pomožne funkcije. DHBP vmesnik torej implementira osnovno idejo uporabe predznanja v atributnem učenju, ki smo jo razložili v razdelku 2.2. Učenje z LINUSom poteka v naslednjih korakih: • pripravi množico pozitivnih in negativnih dejstev, • pretvori dejstva iz DHBP oblike v n-terice vrednosti atributov, • nauči se opisa koncepta z uporabo atributnega učnega algoritma, • pretvori naučena pravila iz oblike if-then pravil v obliko DHBP stavkov. Algoritem opišemo s preprostim primerom. Denimo, daje relacija r(a,b,c) podana z naslednjimi tremi dejstvi, označenimi z ©: r(al,61,61). r(al,62,62). r(a2,61,62). Podana je t,udi informacija o imenih in tipih spre- menljivk. Prvi argument relacije r ima ime a, njegov tip je tip.a, drugi in tretji argument 6 in c pa sta oba istega tipa tip^b. Vsakemu tipu je pridružena informacija o zalogi vrednosti spremenljivk: {al,a2} za tip .a in {61,62} za tipJb. Dodatno znanje o problemu je podano v obliki definicij pomožnih predikatov in funkcij. Uporabimo npr. binarni pomožni predikat p, definiran z naslednjimi dejstvi: p(al,bl). p(al, 62). p(a2,62). V splošnem so lahko pomožni predikati in funkcije definirani z množico rekurzivnih tipiziranih programskih stavkov (v formalizmu DBP). Argumenta predikata p sta tipa tip_a in tipJb. LINUS uporablja tudi vgrajeni pomožni predikat ena kost (-/2). Množica negativnih dejstev je lahko vnaprej podana, lahko pa jo sistem generira iz pozitivnih dejstev. V načinu, ki temelji na predpostavki zaprtega sveta (cwa), LINUS generira vse možne kombinacije vrednosti argumentov ciljne relacije. Vsa generirana dejstva, razen podanih pozitivnih dejstev, LINUS uporabi kot negativna dejstva in jih označi z 0: r(al, 61,62). r(al,62,61). r(a2,61,61). r(a2,62,6l). r(a2,62,62). V drugem koraku algoritem preveri vse možne aplikacije pomožnih predikatov in funkcij glede na tipe spremenljivk. V našem primeru so to p(a,b) in p(a,c), enakost pa lahko uporabi nad argumentoma istega tipa, torej b=c. Iz treh pozitivnih primerov relacije r LINUS generira naslednje šesterice oblike: (a, 6, c, (6 = c), p(a,6), p(a,c) ) (al, 61, 61, true, true, true ) (al, 62, 62, true, true, true ) (a2, 61, 62, false, false, true ) Na enak način LINUS generira šesterice tudi iz negativnih dejstev. 76 V tretjem koraku generirane n-terice pozitivnih in negativnih primerov uporabi za učenje s sistemi ASISTENT, NEVVGEM ali CN2. Generi-rani opis koncepta v obliki odločitvenega drevesa, VL1 pravila ali if-then pravil, se prepiše v prolo-govo obliko if-then pravil. V četrtem koraku algoritem pretvori if-then pravila iz prologove oblike v obliko DHBP stavkov. V našem preprostem primeru dobimo naslednji opis: r(A,B,C) «- A = al,B = C. r(A, B,C) «- C = 62, not p(A, B). V generiranih pravilih nastopata poleg literalov A=al in C=b2, ki jih je mogoče dobiti tudi z atributnim učenjem, tudi literala B=C in not p(A,B), ki sta dobljena z uporabo relacijskega predznanja. Z izborom atributov in predznanja, ki naj se uporabi za učenje, lahko torej sistem LINUS uporabimo na tri načine: • kot atributni učni algoritem, če sistemu povemo, kateri od argumentov ciljne relacije naj upošteva kot odločitveni razred ter če v celoti izključimo predznanje, • kot algoritem za atributno učenje, ki zna uporabljati predznanje, če sistemu povemo, kateri od argumentov ciljne relacije naj upošteva kot odločitveni razred ter če upoštevamo nove atribute, dobljene z uporabo predznanja, t kot algoritem za relacijsko učenje, če obravnavamo samo pozitivne in negativne primere relacije © in 6 ter se učimo samo na osnovi predznanja. 3.2 Uporaba predznanja v atributnem učenju opisov posameznih razredov v revmatologiji LINUS predstavlja razširitev atributnih algoritmov z možnostjo uporabe predznanja in ga lahko uporabimo za atributno učenje. Takemu načinu učenja pravimo učenje razredov (class learning mode, Lavrač, Džeroski in Grobelnik 1991). Sistem smo v tem načinu uporabili za učenje diagnostičnih pravil v revmatologiji. Eksperimenti so podrobno opisani v (Lavrač, Džeroski, Pirnat in Križman 1991). Na voljo smo imeli podatke o 462 pacientih Univerzitetnega kliničnega centra v Ljubljani. Pacienti so bili razvrščeni v 200 diagnoz, ki so bile grupirane v 8 razredov diagnoz: Al degenerativne bolezni hrbtenice (158 primerov), A2 degenerativne bolezni sklepov (128), BI vnetne bolezni hrbtenice (16), B234 druge vnetne bolezni (29), C zunajsklepni revmatizem (21), D metabolni revmatizem (24), E neznačilne revmatske težave (32) ter F nerevmatske bolezni (54). V eksperimentu smo upoštevali le anamnestične podatke, opisane z vrednostmi naslednjih 16 atributov: spol, starost, družinska anamneza, sedanje težave, sedanja bolezen, bolečine v sklepih, število bolečih sklepov, število oteklih sklepov, bolečine v hrbtenici, ostale bolečine, jutranja okorelost, koža, sluznice, oči, druge težave in terapija. LINUS smo uporabili za učenje opisov posameznih razredov diagnoz. 70 % podatkov smo uporabili za učenje, 30 % pa za testiranje klasifikacijske točnosti naučenih pravil. Eksperiment smo ponovili desetkrat, z naključno porazdelitvijo v učne in testne primere. V učenju smo upoštevali predznanje o značilnih skupinah simptomov. Identificirali smo 6 značilnih skupin simptomov, npr. karakteristične kombinacije simptomov prve skupine so naslednje: Bolečine v sklepih Jutranja okorelost bp artrotična artritična < 1 ura < 1 ura > 1 ura Karakteristične kombinacije v šesti skupini simptomov pa so podane v spodnji tabeli: Število oteklih sklepov Število bolečih sklepov 0 0 1 < št. sklepov < 10 0 1 < št. sklepov < 30 0 < št. sklepov < 30 Kot primer navedimo diagnostično pravilo za metabolni revmatizem: Razred = metabolni^revmatizem «— skupina6( St-oteklsklepov, St-boLsklepov, 'l= 30, Starost =< 40, Spol — moški. Razred = metabolni^revmatizem <— BoLv-hrbtenici = bp, 77 BoLv.sklepih — artriticne, Spol — moški. Razred = metabolni-revmatizem <— BoLvJirbtenici = bp, Starost =< 40, Sedanje.tezave > 11, Spol = rrCbski, skupina5( BoLv.sklepih, BoLvJirbtenici, St.boLsklepov, Vrednost), member( Vrednost, [ 'artriticne&bp&l—