DMS Pregled područja - Opis ILLM sistema

Opis ILLM sistema

DMS je mrežni sistem za indukciju pravila baziran na algoritmima ILLM sistema (Inductive Learning by Logic Minimization). ILLM je sistem za učenje pravila u obliku propozicija za rješavanje klasifikacijskih problema. Pravila koja se dobiju indukcijom ILLM sistemom su obično u obliku konjunkcija parova atributa-vrijednosti (CNF, DNF).

Osnovne razlike u odnosu na druge propozicijske sisteme, odnosno tehnike indukcije pravila sastoje se u slijedećem:

ILLM sistem odvojeno tretira proces generiranja parova atribute-vrijednost (u daljnjem tekstu koristit će se i naziv literali) i proces indukcije pravila;
Za proces selekcije literala ILLM koristi specijalan algoritam baziran na parovima pozitivnih i negativnih primjera (p/n parovi) Taj algoritam važan je zbog mogućnosti generiranja reduciranog skupa literala koji su relevantni za rješavanje konkretnog problema, prije samog procesa indukcije pravila;
Sam proces indukcije pravila baziran je na kriteriju minimiziranja duljine pravila;
Na osnovu skupa relevantnih literala moguće je odabrati minimalni skup literala dovoljan za generiranje pravila odredjene kvalitete. Ovaj algoritam baza je i za otkrivanje šuma u podacima, što je dodatna kvaliteta ILLM sistema.

Procedura odabira relevantnih literala

Većina tehnika indukcije pravila istovremeno rješava problem indukcije pravila i odabira značajnih literala. U tom procesu obično se koristi neka od metrika iz teorije informacija ("information gain"). Kod ILLM sistema proces odabira relevantnih literala prethodi procesu generiranja pravila. Odabrani skup literala dovoljan je za konstrukciju pravila koje u potpunosti pokriva sve primjere ciljane klase.

Proces odabira literala u ILLM sistemu baziran je na tzv. parovima pozitivnih i negativnih primjera (p/n parovi). Umjesto jedne tablice prekrivanja primjera, ILLM koristi dvije: P - tablicu pozitivnih primjera i N - tablicu negativnih primjera. Stupci ove tablice su svi potencijalno interesantni (generiranje ovih literala je objašnjeno kasnije u tekstu) literali koji su na raspolaganju za proces odabira. Elementi tablice (vrijednosti) poprimaju dvije vrijednosti, potvrdnu ("true") i negativnu ("false"), zavisno o tome da li pojedini literal za taj primjer poprima tu vrijednost ili ne.

P i N tablice se mogu reducirati ukoliko je zadovoljen neki od jednostavnih kriterija. Npr. stupac, odnosno literal može biti brisan iz tablice ukoliko postoji drugi literal koji pokriva iste primjere ili više primjera. Isto tako, red tablice (primjer) može biti brisan iz tablice, ukoliko ima iste vrijednosti u istim stupcima kao neki drugi primjer.

Ovo je osnovni princip odabira relevantnih literala u ILLM sistemu. Treba reći da je ova jednostavna procedura i osnova za proces otkrivanja 'posebnih' primjera ("outliers"), koji odskaču po svojim karakteristikama od ostalih primjera svoje klase.

Proces generiranja literala i njihovog odabira za proces indukcije pravila opisani su detaljnije u slijedećem poglavlju. Detalji procedure indukcije pravila dani su pri kraju. Ovaj koncept indukcije pravila nazvan 'konfirmacijskim pravilima ("confirmation rules") objašnjen je detaljnije u literaturi (Gamberger, 2000).

Literali u ILLM sistemu: proces generiranja i odabira

Razmotrimo najjednostavniji klasifikacijski problem s dvije klase, u kojem se skup primjera za učenje E sastoji od pozitivnih i negativnih primjera (E = P ∪ N) a primjeri e ∈ E su skupovi vrijednosti da-ne ("truth-values"), po svim literalima iz dostupnog skupa literala L. Neka je skup za učenje E definiran dakle kao tablica gdje redovi predstavljaju primjere iz skupa primjera a stupci predstavljaju pojedine literale. Element u tablici ima vrijednost da ukoliko primjer ima tu vrijednost literala, odnosno ne ukoliko primjer nema vrijednost literala.

Procedura generiranja literala u ILLM sistemu

Ukoliko skup primjera za učenje nije u formi, ta se transformacija automatski radi u fazi preprocesiranja podataka za ILLM sistem. Za svaki atribut A_i, vrijednosti v_ix (x = 1..kip) predstavljaju k_ip različitih vrijednosti tog atributa koje se pojavljuju u pozitivnim primjerima a w_iy (y = 1..k_in) neka su k_in različitih vrijednosti koje se pojavljuju u negativnim primjerima. Transformacija rezultira u skupu literala L:

Za diskretne (nominalne) atribute Ai, generirati će se literali tipa Ai=vix i Ai=wiy;
Za numeričke atribute Ai, generirat će se literali Ai ≤ (vix+wiy)/2 za sve susjedne parove vrijednosti literala(vix, wiy), te literali Ai > (vix+wiy)/2 za sve susjedne parove vrijednosti literala (wiy, vix);
Za atribute cjelobrojnog tipa (realne varijable) Ai, literali se generiraju kao da su Ai istovremeno i diskretnog odnosno numeričkog (realne vrijednosti) tipa, rezultirajući u literalima koji poprimaju četiri oblika: Ai ≤ (vix+wiy)/2, Ai > (vix+wiy)/2, Ai=vix, i Ai=wiy.

U definiciji literala za numeričke (realne atribute ili varijable) odnosno cjelobrojne atribute uvodi se pojam susjednog para vrijednosti. Ovaj pojam definiran je kao par neposrednih susjednih vrijednosti odredjenog atributa u skupu primjera i to tako da jedna od tih vrijednosti pripada pozitivnom primjeru, a druga negativnom, ili obrnuto. Ne postoji primjer iz datog skupa primjera čija vrijednost atributa se nalazi izmedju ovih dviju vrijednosti.

Tablice pokrivanja p/n parova primjera

Neka je skup primjera za učenje E predstavljen tablicom u kojoj stupci predstavljaju pozitivne i negativne literale skupa L, a redovi vrijednosti (da/ne) primjera iz skupa za učenje ei. Postoje dvije tablice, P - tablica pozitivnih primjera i N - tablica negativnih primjera. Da bi omogućili formalnu diskusiju o relevantnosti literala, i odabira literala za proces indikcije pravila, uvest ćemo slijedeće:

Definicija 1. p/n par je par primjera iz skupa za učenje za koji vrijedi p ∈ P i n ∈ N.

Definicija 2. Literal l ∈ L pokriva p/n par ako je vrijednost pozitivnog primjera p u stupcu da i negativnog primjera n, ne. Skup svih parova p/n pokrivenih literalom l označit ćemo sa E(l).

Definicija 3. Literal l pokriva literal l' ako vrijedi E(l') ⊆ E(l).

Da bi ilustrirali gornje definicije razmotrimo jednostavni problem s 5 primjera za učenje: 3 pozitivna primjera p1, p2 i p3, te dva negativna primjera n1 i n2, koji su opisani vrijednostima literala l i ∈ L. Tablica 1 sadrži P i N tablice našeg primjera skupa E, s nekoliko vrijednosti literala i primjera.

Tablica 1: Primjer P i N tablica: stupci su literali, a primjeri redovi. Elementi tablice poprimaju dvije vrijednosti da ili ne: da - ako je literal istinit za taj primjer, ili ne - ako literal nije istinit za taj primjer.

Značaj ("relevance") literala

Literal l2 u Tablici 1, značajan je za buduće formiranje pravila r jer je potvrdan za jedan pozitivni primjer, a negativan za dva negativna primjera. Literal l2 ustvari pokriva dva p/n para: E(l2) = {p2/n1, p2/n2}. Literal l8 nije pogodan za stvaranje pravila, jer ne pokriva nijedan p/n par: E(l8) = 0. Literal l4 izgleda manje značajan od l2, a više značajan od l8; on pokriva samo jedan p/n par: E(l4) = {p2/n1}. Literal l2 pokriva l4 i l8, a literal l4 pokriva l8, jer vrijedi E(l8) ⊆ E(l4) ⊆ E(l2). Na osnovu ovog razmatranja Tablica 1 daje nam slijedeće: što više p/n parova literal pokriva, to je on značajniji za indukciju pravila. To se može formalizirati kroz slijedeću definiciju.

Definicija 4a. Literal l' je beznačajan ako postoji literal l ∈ L koji pokriva l' (E(l') ⊆ E(l)). Drugim riječima, literal l' je beznačajan ako pokriva podskup p/n parova već pokrivenih nekim drugim literalom l ∈ L.

Pretpostavimo da je literarima pridružen 'trošak' (na primjer, 'trošak' može biti mjera kompleksnosti - što je kompleksniji literal, to je veći njegov 'trošak'). Označimo 'trošak' literala l ∈ L sa c(l). Definicija značaja literala se treba modificirati ukoliko postoji neka funkcija 'koštanja' vezana uz literale.

Definicija 4b. Literal l' je beznačajan, ako postoji literal l ∈ L, koji pokriva l' (E(l') ⊆ E(l)) a 'trošak' vezan uz korištenje l je niži od troška vezanog uz korištenje l' (c(l) ≤ c(l')).

Ovako objašnjen pojam značaja literala, osnova je za proceduru odabira relevantnih literala u ILLM sistemu, kao i za posebnu proceduru detekcije šuma. Detalji te procedure dani su u literaturi. Mi ćemo sada pretpostaviti da je skup relevantnih literala odabran, pa se može pristupiti procesu indukcije pravila, što je objašnjeno u nastavku.

Procedura indukcije pravila

Koristeći prethodno dan formalizam, te pretpostavljajući da smo odabrali skup relevantnih literala, prijeći ćemo na proceduru generiranja (indukcije) pravila. Algoritam za konstrukciju pravila prikazan je na Slici 1.

Slika 1: Algoritam za generiranje pravila ("confirmation rule subset")

Procedura koja je opisana pod točkom 3 u algoritmu CR ("Confirmation Rules"), je procedura pretraživanja kojom se maksimizira pokrivanje novog pravila koje se dodaje u skup CR. Ova procedura pretraživanja može biti različitih karakteristika, zavisno od kompleksnosti problema: 'iscrpna' ("exhaustive"), odnosno heuristička, ako je problem previše kompleksan. Treba primijetiti da je 'težina' pravila obrnuto proporcionalna zbroju 'težina' pokrivenih primjera.

Karakteristika je ovako stvorenih skupova pravila ("confirmation rule sets") da ona tipično ne pokrivaju sve pozitivne primjere, ali su zato 100% točna s obzirom na negativne primjere (odatle i ime "confirmation rules"). Kao posljedica korištenja adaptivnih težina primjera c(e) u algoritmu CR, pravila u skupu CR su medjusobno relativno nezavisna, jer je svako novo pravilo dodano u skup CR 'usmjereno' na pokrivanje primjera s manjom težinom, t.j. onih koji još nisu pokriveni, ili su pokriveni relativno malim brojem dotad generiranih pravila. Algoritam CR, s vrlo malim izmjenama je korišten kao podloga za 'online' indukciju pravila na poslužitelju (DMS).

Primjena ILLM sistema i DMS sistem za 'online' obradu podataka

Sistem za indukciju pravila ILLM namijenjen je za rješavanje klasifikacijskih problema (vidi stranicu posvećenu primjenama ILLM sistema). Njime se generiraju pravila tipično u obliku konjunkcija literala (CNF oblik). Uz korištenje posebnog algoritma za testiranje, generirana pravila mogu se koristiti kao 'online' sistem za detekciju ili klasifikaciju. S druge strane, 'čitljivost' pravila je vrlo dobra karakteristika za rješavanje problema obrade podataka koji su deskriptivnog tipa (COIL 2000 Challenge). Ovaj deskriptivni karakter pravila, dodatno je potenciran u DMS 'online' sistemu, gdje se pravila 'prevode' u jezik korisnika, odnosno skup jednostavnih tvrdnji.

Literatura o ILLM sistemu

D.Gamberger. (1995) A minimization approach to inductive learning. In Proc. of the 8th European Conference on Machine Learning, Springer, pp.151-160. ( .ps file 266kB).
D.Gamberger and N.Lavrac. (1997) Conditions for Occam's razor applicability and noise elimination. In Proc. of 9th European Conference on Machine Learning, Springer, pp. 108-123, ( .ps file 333kB).
N.Lavrac, D.Gamberger, and P.Turney. (1998) A relevancy filter for constructive induction. IEEE Intelligent Systems , Vol.13, pp.50-56.
D.Gamberger and N.Lavrac. (2000) Confirmation rule sets. In Proc. of 4th European Conference on Principles of Data Mining and Knowldge Discovery (PKDD 2000), pp. 34-43. ( .ps file 289kB).
D.Gamberger and N.Lavrac. (2001) Filtering noisy instances and outliers. In H.Liu and H.Motoda, editors, Instance Selection and Construction for Data Mining, Kluwer Academic Publishers.

.ps file