Voorwoord. Maar nu eerst Latex leren

Voorwoord We schrijven 17 juni 2006, na bijna een jaar proberen er iets van te maken is de meet in zicht. Het is niet altijd even makkelijk geweest, vaak te weinig concentratie, niet voldoende druk om hard door te werken op sommige momenten... waarschijnlijk de belangrijkste redenen dat deze tekst nu pas volledig wordt in elkaar gestoken. De krabbels op losse papieren worden verzameld, de kladblok files op de verschillende computers bij elkaar gesprokkeld om er 1 groot afrondend geheel uit te fabriceren. Uiteraard met de nodige code, tests en resultaten zou dit moeten leiden tot een thesis die voldoet aan de eisen en zo af te studeren als Licenciaat Informatica. Het is mooi geweest, de jaren als student, het ene jaar al succesvoller dan het andere, maar de eindstreep ,of de meet zoals ik ze al noemde, is ,nog steeds, in zicht Nog een laatste inspanning en dan, hopelijk, het ”echte ”leven in... Alea iacta est en ook morituri te salutant en hopelijk daarna: Veni,Vidi,Vici, want wij informatici zijn de dappersten van allemaal.... Maar

nu

eerst

Latex

Thesis geschreven door Samuel Dom voor het behalen van het diploma: Licenciaat in de Informatica. Aan de K.U. Leuven, 2005-2006.

1

leren.

Inhoudsopgave Voorwoord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1 Inleiding 1.1 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doel van de thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Overzicht van de hoofdstukken . . . . . . . . . . . . . . . . . . . . . .

4 4 4 5

2 Beslisbomen 2.1 Geschiedenis . . . . . . . . . . . . 2.2 Terminologie . . . . . . . . . . . . 2.3 Optimaliseren van bomen . . . . . 2.3.1 Stop Criterium en pruning 2.3.2 Split-criteria . . . . . . . . 2.4 Algoritmes . . . . . . . . . . . . . 2.4.1 ID3 . . . . . . . . . . . . . 2.4.2 C4.5 . . . . . . . . . . . . . 2.4.3 CART . . . . . . . . . . . . 2.5 Overzicht . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

7 7 8 10 10 11 13 13 14 15 15

3 Lookahead 3.1 Wat en waarom? . . . . . . . . . . . . . 3.2 Pathologie . . . . . . . . . . . . . . . . . 3.3 Fuzzy TDIDT en Lookahead . . . . . . 3.4 Skewing . . . . . . . . . . . . . . . . . . 3.5 Algoritmes . . . . . . . . . . . . . . . . 3.5.1 ID3-k . . . . . . . . . . . . . . . 3.5.2 Lookahead met stochastische ID3 3.6 Besluit Lookahead . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

16 16 18 19 19 22 22 22 23

. . . .

24 24 24 25 26

4 Achteruitkijken: een voorstel 4.1 Algoritme 1: gulzig algoritme 4.2 Algoritme 2 . . . . . . . . . . 4.3 Algoritme 3 . . . . . . . . . . 4.4 Algoritme 4:Lookahead . . . .

. . . .

. . . .

. . . .

. . . . . . . . . .

. . . .

2

. . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 ILP, ACE en Tilde 5.1 ILP . . . . . . . . . . . . . . . 5.2 Logische beslisbomen en Tilde . 5.2.1 Logische beslisbomen . 5.2.2 Tilde . . . . . . . . . . . 5.2.3 Lookahead in Tilde. . . 5.3 ACE . . . . . . . . . . . . . . .

. . . . . .

27 27 28 28 29 29 30

6 MIP 6.1 Wat zijn Multi Instantie Problemen? . . . . . . . . . . . . . . . . . . . . . . . 6.2 MIP en Tilde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 32

7 Studie originele code van Tilde 7.1 Tdidt.gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 cprefine.gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 flocks.gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34 34 35 36

8 Uitbreidingen van de code 8.1 tdidt.gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 flocks.gen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 38

9 Datasets 9.1 Mutagenesis 9.2 Diterpenes . 9.3 Musk . . . . 9.4 PTE . . . . 9.5 Bongard . .

39 39 39 40 40 40

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

10 Tests

41

11 Resultaten en conclusies 11.1 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Snelheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Grootte van de boom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42 42 43 44

12 Besluit Dank- en Nawoord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Referenties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46 47 48

3

Hoofdstuk 1

Inleiding 1.1

Machine Learning

Sinds de dageraad van de het computertijdperk zijn we al op zoek naar een antwoord op de vraag of machines intelligentie kunnen vertonen. Door de jaren heen werd uitvoerig onderzoek gedaan naar artifici¨ele intelligentie. Een grote domein binnen de A.I. is dat van machine learning. Hier wordt onderzocht of machines kunnen leren, of ze zelf door ervaring nieuwe dingen kunnen ontdekken. Dit met behulp van een uitgebreid gamma aan uiteenlopende algoritmes en technieken. Machine learning heeft een groot aantal toepassingen die we onder ander terugvinden bij zoekmachines, medische diagnose,beursanalyes,spraakherkenning, computer vision, etc...

1.2

Doel van de thesis

Context Een belangrijke taak in het domein van machine learning is het voorspellen van de klasse van voorbeelden in een dataset. Bouwen van beslissingsbomen is hiervoor een populaire methode. Er bestaan enorm veel algoritmes en varianten op algoritmen voor het bouwen van deze beslisbomen, in hoodstuk 2 geven we een overzicht met de belangrijkste algoritmen,hun voordelen,nadelen en specificaties. De meest gekende en gebruikte algoritmes zijn de zogenaamde greedy of gulzige algoritmes. Hierbij wordt een boom gebouwd knoop voor knoop en wordt voor elke knoop op zich de beste beslissing gemaakt. De tijd nodig voor deze werkwijze is relatief kort. Tilde is bijvoorbeeld zulk een algoritme om een beslissingsboom te leren, uit een relationele databank.Tilde is ge¨ımplementeerd in het ACE data mining systeem. Dit is het systeem waarin we voor de thesis gaan werken. In hoofdstuk 5 bekijken we dit systeem samen met de specificaties van Tilde. Een eerste bekende techniek voor het verbeteren van de performantie van gulzige algoritmen zoals Tilde is het vooruitkijken in een boom of lookahead. Hierbij gaan we in een knoop van de boom voor de keuze van een test proberen te schatten wat het effect van deze keuze is op knopen lager in de boom. Aan de hand van die schattingen gaan we dan de beste test kiezen. Er zijn al een redelijk aantal uitwerkingen en bevindingen over deze methode voorhanden en we zullen hier dan ook nog uitgebreid op terug komen op het einde van hoofdstuk 3. 4

Een andere techniek, die het uitproberen waard is, is achteruitkijken. Dit houdt in dat we eerst een test kiezen voor een knoop K. Daarna kijken we of die nog geoptimaliseerd kan worden. Deze optimalisatie gebeurt door het naar boven verschuiven van de test in zijn linkerkind indien de samengevoegde test van ouder en kind betere resultaten zou geven dan die van de ouder alleen. We kijken dus achteruit in de boom naar de ouderknoop K bij het bouwen van het linkerkind. Deze aanpak heeft een lagere tijdscomplexiteit dan lookahead. Het doel is nu na te gaan of deze methode een potentieel gulden middenweg kan zijn tussen gewone gulzige algoritmes en de vaak tijds-intensieve lookahead-algoritmes. Hiertoe stellen we enkele algoritmen voor om achteruit te kijken in hoofdstuk 4. Deze gaan we dan implementeren in ACE(Hoofdstuk 8) en testen op een aantal datasets(Hoofdstuk 9). Met deze achteruitkijk-techniek zouden we Tilde bovendien kunnen gebruiken voor multiinstance problemen. De bestaande Tilde kan hiervoor niet optimaal gebruikt worden. Dit wordt verduidelijkt in hoofdstuk 6.

Doel Om het voorgaande samen te vatten: het doel van de thesis is het uitwerken en implementeren van een achteruitkijk -techniek in Tilde en het vergelijken van deze techniek met vooruitkijken. Ook dient de toepassing van deze techniek in het multi-instance domein onderzocht te worden.

1.2.1

Overzicht van de hoofdstukken

• Hoofdstuk 2 geeft een inleiding op beslisbomen, enkele veelgebruikte algoritmes en technieken. Tevens wordt een blik geworpen op lookahead,vooruitkijken in een boom. Wat is lookahead juist en we geven enkele bevindingen uit eerder onderzoek. • Hoofdstuk3, we stellen enkele algoritmes voor die we in deze thesis gaan onderzoeken en situeren ze tussen de bestaande gulzige algoritmes enerzijds en lookahead-algoritmes anderzijds. • Hoofdstuk 4 bespreekt bondig het systeem waarin we de algoritmes gaan implementeren en testen. • Hoofdstuk 5 werpt een licht op het begrip multi − instantieproblemen en duidt aan waarin het huidige systeem te kort schiet om deze problemen op te lossen en wat het doel van de thesis hier is. • Hoofdstuk 6 overloopt de modules van het systeem die intressant zijn voor deze thesis en licht kort de werking toe. • Hoofdstuk 7 , de eigen aanpassingen aan de code worden bekeken en besproken

5

• Hoofdstuk 8 vertelt over de testen die we uitvoeren, welke datasets we gebruiken en bespreekt de resultaten en bevindingen. De experimentele fase bestaat uit 2 delen: – vergelijken van de predictieve performantie en grootte van bomen bij Tilde met vooruitkijken en met achteruitkijken op een aantal benchmark datasets. – het uitproberen van de nieuwe techniek op een aantal multi-instance benchmark datasets en de resultaten vergelijken met die van andere multi-instance systemen • Hoofdstuk 9 vormt een besluit.

6

Hoofdstuk 2

Beslisbomen Zoals we in de inleiding zagen is een van de meest gebruikte machine learning technieken de beslissingsboom. Beslisbomen worden gebruikt voor het benaderen van een functie met discrete waarden. We geven in het eerste deek van dit hoofdstuk een korte inleiding op beslissingsbomen, hun geschiedenis, gebruik, terminologie, etc.. Dan bekijken we de belangrijkste en meest invloedrijke algoritmen van het domein.

2.1

Geschiedenis

De eerste idee¨en omtrent deze tak gaan terug naar het werk van Hoveland en Hunt uit de jaren 50 van vorige eeuw. EPAM (Elementary Perceiver And Memorizer) van Feigenbaum was in 1961 het eerste syteem dat beslisbomen gebruikte, onder de naam van discriminatie-nets. Het werk dat echter voor de grote boost zorgde in de ontwikkeling van het domein dateert uit 1966: ”Experiments in Induction”door de psychologen E.B. Hunt, J. Marin en P.J. Stone. Hun CLS gebruikte ”heuristische lookahead om bomen te bouwen voor het modelleren van het leren van menselijke concepten.” In de jaren 70 werd de basis gelegd voor de populairste algoritmen uit het domein. We schrijven 1977 als Breiman en Friedman simultaan de basis leggen voor CART en in ’79 introduceerde Quinlan het idee om informatie-inhoud te gebruiken voor de keuze van splits in een boom uitgewerkt in een prototype van ID3. De eighties brachten in 1984 de eerste publieke versie van CART software, 2 jaar later,1986, komt Quinlan’s baanbrekende paper over ID3 uit, welk hij later zal updaten tot C4.5(1993). In navolging van dit laatste algoritme komen er meer optimalisaties op het vlak van pruning en andere heuristieken om overfitten van data tegen te gaan doorheen het laatste decennium.

7

2.2

Terminologie

In onderstaande tabel geven we eerst een korte beschrijving van termen die veel worden gebruikt in verband met beslissingsbomen. We geven dan een iets meer uitgebreide uitleg bij de tabel aangevuld met enkele figuren. Voorbeeld Sample,object, een eenheid van informatie Attribuut Een eigenschap of variabele in de testset, beschrijft de data Waarde De waarde van een attribuut voor een bepaald voorbeeld. Klasse Doel variabele, elk voorbeeld moet worden geklassificeerd in een klasse Knoop Interne knoop van een boom, bevat een test Blad eindknoop in een boom, heeft geen kinderen, heeft een klasse label Test voorwaarde in een knoop waarop de data wordt gesplitst Diepte Het level van een knoop, de afstand tot de wortel, met wortel heeft diepte 1. Een boom bestaat uit knopen en verbindingen, de takken, tussen deze knopen. Een boom heeft een wortel en vanuit de wortel bestaat er juist 1 pad naar elke knoop, er zijn dus geen lussen in een boom. Een knoop kan 1 of meerdere kinderen hebben, zoals we zien in figuur 1.1. Indien een knoop geen kinderen meer heeft noemen we het een blad. Zoals we in de figuur zien heeft elke knoop ook een diepte. Deze is bepalen aan de hand van de afstand van de knoop tot de wortel en is gelijk aan de lengte van het pad, waarbij elke tak even lang is. Dus als de wortel diepte 0 heeft dan hebben de kinderen van de wortel diepte 1, de kinderen daarvan hebben diepte 2 enzovoort....

Figuur 2.1: Terminologie Een beslisboom is een boom met in de knopen een test en in zijn bladeren een klasse. De tests zijn mutueel exclusief, er is maar 1 mogelijke tak die kan worden genomen vanuit een knoop naar 1 van de kinderen. Tevens zal een pad van de wortel naar een knoop een test niet meer dan 1 keer doorlopen,de tests zijn exhaustief. Zulk een test is een test op een attribuut. Het doel van een beslissingsboom kan verschillen maar we kunnen 3 grote klassen onderscheiden binnen de problemen die een beslisboom kan aanpakken: Regressie. Bomen bepalen voor een continue doelvariabele de afhankelijkheid van onderling onafhankelijke variabelen. Klassificatie. Objecten worden in een klasse ingedeeld aan de hand van een boom. De doel variabele is een discrete waarde. Data Beschrijving. Bomen kunnen gebruikt worden om een beschrijving te geven van objecten en zo kunnen we op een compacte manier data te bewaren 8

In deze tekst focussen we op bomen die we gebruiken om te klassificeren. We gaan dus een boom gebruiken om voorbeelden uit een dataset in te delen in een klasse. Hiertoe gaan we elk voorbeeld doorheen de boom leiden via een pad van de wortel uit naar een blad, het pad wordt bepaald door de tests in de knopen. We testen data in elke knoop die hij passeert op zijn pad op attributen van de voorbeelden door de test in de knoop en op die manier worden voorbeelden in klasse ingedeeld in een blad. Een boom kan binair zijn, waarbij elke knoop maar 2 kinderen heeft of hij kan meerdere kinderen hebben. Ook een individuele test kan binair zijn, zoals alle tests in een binaire boom, of kan meerdere mogelijke uitkomsten hebben. Het aantal kinderen van een knoop hangt dus af van de test. Er kunnen 2 of meer klassen zijn waartoe voorbeelden kunnen behoren. De attributen waarop getest wordt kunnen zowel numeriek als categoriek zijn. Als we een boom willen gebruiken om data in klassen te verdelen moeten we uiteraard eerst een boom bouwen. Een boom wordt gebouwd aan de hand van een set van trainingsvoorbeelden die aan een algoritme worden gegeven. Als een boom is gebouwd kan hij worden getest met andere voorbeelden en indien hij voldoet verder worden gebruikt. Iets specifieker beginnen we bij de wortel van de boom waarvoor we aan de hand van een split-criteria de beste test bepalen aan de hand van de gegeven data. We trainen de boom dus op door hem voorbeelden aan te reiken die liefst representatief zijn voor alle mogelijke data die later aan de boom kan worden gegeven om te klassificeren, dus de boom gaat ook niet eerder gezien data juist moeten kunnen klassificeren. In figuur 1.2 zien we schematisch de levensweg van een beslisboom.

Figuur 2.2: ’Levensweg’ van een beslisboom

We bekijken kort het voorbeeld van een beslisboom uit figuur 1.3. Het is een fictieve beslisboom om een dier in te delen in 1 van 6 klassen. De data zal dus uit een aantal dieren bestaan met eigenschappen of attributen zoals het aantal poten, het hebben van een staart of beharing. We zien dat elke knoop ofwel 2 kinderen heeft ofwel geen. Het is dus een binaire boom. We beginnen in de wortel met de test of een dier haar heeft, zoja gaan we verder naar het linkerkind anders naar het rechter. De test van het linkerkind vraagt of het voorbeeld veren heeft, zoja behoort het tot de klasse vogel, zo nee gaan we naar het rechterkind. Zo doorlopen we voor elk dier, elk voorbeeld, de boom van de wortel tot in een blad tot we de klasse kennen.

9

Figuur 2.3: Voorbeeld van een beslisboom

2.3

Optimaliseren van bomen

Een van de uitdagingen bij beslisboominductie is het bouwen van kleine en ondiepe bomen. Kleinere bomen verminderen de berkeningskost voor het klassificeren van testvoorbeelden enerzijds en wat belangrijker is; grotere bomen geven slechtere resultaten qua generalisatie van testvoorbeelden. Met dit doel zijn een aantal methodes met verschillende inslag over de jaren heen ontwikkeld. We kunnen deze verdelen groepen: spilt-criteria, ten tweede stop criteria plus snoeien (pruning) en als derde lookahead. Al deze methodes zijn er op gericht om betere bomen in het algemeen te verkrijgen.In wat volgt zal elk van deze methodes worden overlopen. Daarna bespreken we enkele specifieke algoritmen.

2.3.1

Stop Criterium en pruning

Overfitten kan een probleem vormen Als we een boom groeien met behulp van set trainings-voorbeelden kunnen problemen optreden indien de gegevens ruis bevatten of als de set te klein is om representatief te zijn voor de doelfunctie. We krijgen dan een boom met pure bladeren die een hypothese geeft zodat een andere hypothese bestaat die slechter presteert over de trainingsdata maar over verdeling van alle mogelijke voorbeelden beter is. Dit noemen we overfitten van de trainingsdata. Uit onderzoek blijkt dat door dit probleem de juistheid van een boom 10 tot 25% daalt. Het is dus belangrijk overfitten te vermijden. We onderscheiden 2 technieken om overfitten tegen te gaan; stop-criterium en pruning, waarbij de laatste de meest effici¨ente is.

10

Stop-criterium Een eerste methode is gebruik maken van een stop-citerium zodat de boom stopt met groeien voor hij gaat overfitten. We kunnen de groei van de boom stoppen in een bepaalde knoop als de waarde van het splitcriterium onder een bepaalde waarde gaat. Een ander criterium dat we kunnen gebruiken is een grens zetten op het aantal voorbeelden dat nog over blijft in een knoop, als het aantal onder de grens gaat stoppen we met splitten. Pruning We kunnen uiteraard de boom niet willekeurig gaan bijknippen en kleiner maken. Daarom moeten we ons eerst volgende vraag stellen: Wat is nu de ”beste”grootte van een boom? Zo klein mogelijk uiteraard, maar een boom met een enkele knoop gaat waarschijnlijk niet denderend presteren en aan de andere kant zoals gezegd een boom met pure bladeren ook niet. Dus waar ligt de grens? De meest gebruikte methode om deze grens te bepalen is kruisvalidatie. Hierbij wordt een deel van de data, vaak ’e’en derde, gebruikt als test of validatie set. Het andere deel wordt eerst gebruikt om de boom te bouwen. Daarna wordt met behulp van de testset de juistheid van de boom nagekeken. Het idee is dat uitzonderingen of foute data die in de trainingset voorkomen waarschijnlijk niet of minder gaan terugkomen in de testset. Bij het testen van algoritmes wordt de data zo vaak op meerdere manieren ”gevouwen”, waarbij dan telkens een willekeurig,verschillende derde van de data wordt genomen als testset. Nadeel is dat bij een kleine dataset, deze methode de data die wordt gebruikt nog vermindert en zo fouten nog meer gaat uitvergroten. We kunnen deze validatie-strategie gebruiken om voor knopen na te gaan of de boom zonder die knoop en bijhorende deelboom al dan niet slechter presteert. Indien de boom zonder de knoop niet slechter presteert wordt de knoop en zijn deelboom verwijdert. Zo worden alle knopen die de boom niet slechter maken verwijdert. Een andere manier van snoeien de boom gewoon bouwen en nadien omzetten in regels, indien dit de juistheid van de boom verhoogt wordt een regel verwijdert of gegeneraliseert. De overblijvende regels gaan we sorteren op hun geschatte juistheid en deze worden dan in volgorde gebruikt voor klassificatie.

2.3.2

Split-criteria

De centrale keuze bij het bouwen van bomen is welke attribuut we gaan gebruiken voor de test in een knoop. In het algemeen kunnen we zeggen dat het attribuut dat we kiezen voor de split de dataset moet verdelen op zulk een manier dat elke subset zoveel mogelijk objecten bevat van dezelfde klasse en zo weinig mogelijk van een andere klasse. We willen een zo puur mogelijke subset. In wat volgt worden een aantal criteria gebruikt voor het kiezen van attributen die worden gebruikt voor een split in een knoop om de dataset in subsets te verdelen. Men gebruikt soms meer dan 1 criteria om de resultaten te vergelijken, maar er is niet 1 criterium dat absoluut het beste is,we bekijken eerst enkele veel gebruikte criteria. Informatie Winst Deze statistische informatie-theoretische methode maakt gebruik van het begrip entropie. Entropie geeft weer hoe puur of onpuur een set van voorbeelden is voor een doelattribuut. Wanneer we nu met een split de data in subsets splitsen hebben we voor een set S dat de

11

entropie tov de doelfunctie, die n verschillende waarden kan aannemen ,gelijk is aan: Entropie(S) ≡

Pn

i=1 −pi log2 pi

Hierbij is pi de de verhouding waarin voorbeelden tot klasse i behoren in S De entropie van S zal 0 zijn als alle voorbeelden tot dezelfde klasse behoren. Hieruit kunnen we besluiten dat het attribuut dat we prefereren voor een split hetgene is dat de entropie van zijn subsets minimaliseert. Doorgaans gebruikt men niet puur de entropie zelf om dit te doen ,maar maakt men gebruik van Inf ormatie − winst om de effectiviteit van een attribuut voor het klassificeren te berekenen. We doen dit als volgt: W inst(A, S) = Entropie(S) −

|Sv | vwaarden(A) |S| Entropie(Sv )

P

Waarbij de laatste term gelijk is aan de gemiddelde entropie van elk van de subsets als we splitsen op attribuut A. Dit is de verwachte vermindering in entropie aan de hand van de kennis over het attribuut A. W inst(A, S) is dus de informatie over de doelfunctie vanuit de waarde van een ander attribuut. Split Informatie Inf ormatiewinst bevat echter de natuurlijke neiging om attributen te verkiezen met meer verschillende waarden boven anderen, daar subsets puurder zijn als er meer subsets zijn. Gevaar hierbij is dat wanneer attributen met enorm veel waarden eerst gaan gekozen worden er een goede kans bestaat voor overfitten van de trainingsdata. Daarom ontwikkelde Quinlan een alternatieve methode; winstratio. Deze bestraft attributen met teveel waarden door middel van split − inf ormatie, deze is gevoelig voor hoe breed en uniform een attribuut data opsplitst. SplitInf ormatie(S, A) ≡ −

|Si | |Si | i |S| log2 |S|

Pc

Dit is de entropie van S in verhouding tot de waarden van A in tegenstelling tot de entropie van het vorige criterium die in verhouding was tot het doelattribuut. We gebruiken nu deze entropie en W inst(A, S) en definieren: W instRatio(S, A) ≡

W inst(S,A) SplitInf ormatie(S,A)

Gevaar is dat wanneer een attribuut voor de meeste voorbeelden dezelfde waarde heeft, die subset bijna evengroot is als S zelf en bijgevolg W instRatio heel groot wordt. Daarom berekenen we eerst de W inst van elk attribuut en berekenen we dan de W instratio enkel voor de attributen die een W inst hebben boven een bepaalde grens. Gini-Index De Gini-index, voor het eerst beschreven door Corrado Gini in 1912, is een statistische methode die de ongelijkheid van een verdeling meet, gedefini¨eerd als de verhouding tussen de zogenaamde Lorenz-curve van de verdeling en de curve van de normaalverdeling. De meeste 12

bekende toepassing is het meten van de ongelijkheid van inkomen. De index is een getal tussen 1 en 0 met 0 de perfecte gelijkheid en 1 de totale ongelijkheid.

Figuur 2.4: Gini Index

Men kan de formule van de gini index ook gebruiken zonder referentie naar de LorenzCurve. Zoals ook in het domein van beslissingsbomen deze methode wordt gebruikt om de puurheid van een split te bepalen, bijvoorbeel het CART algoritme,waar we later kort op terugkomen, maakt er gebruik van. De gini-index schat de afstand tussen waarschijnlijkheids verdelingen van klassen. Gini(c) = 1 −

Pn

i=1 p

2

∗ i Met c de huidige knoop en pi de kans dat een element in knoop c tot klasse j behoort.

Deze zal 0 zijn als als er maar 1 klasse aanwezig is in een knoop. Als in een knoop de grootte van alle klassen gelijk is zal de gini-index maximaal zijn.

2.4 2.4.1

Algoritmes Iterative Dichotomiser 3

Door zijn gebruiksgemak en efficientie is ID3 een van de bekendste en meest gebruikte algoritmes in het domein van machine learning en specifieker ook heel populair bij het bouwen van beslisbomen. Het is gebaseerd op Occams Scheermes die simpelere theorie¨en en dus kleinere bomen verkiest boven grotere. De keuze van een attribuut voor de classificatietest gebeurt door middel van een statistische methode zoals informatie winst, waarbij attributen met hoge informatiewinst verkozen worden boven attributen met lage informatiewinst Elke keuze streeft dus naar een zo zuiver mogelijke splitsing van de dataset in subsets.

13

ID3-Algoritme • ID3 ( Voorbeelden, DoelAttribuut, Attributen) – Maak een wortel voor de boom – Als alle voorbeelden positief zijn, geef dan de boom met 1 knoop Wortel terug met label = +.

– Als alle voorbeelden negatief zijn, geef dan de boom met 1 knoop Wortel terug met label = -.

– Als er geen voorspellende attributen geet dan met 1 knoop Wortel terug met label = meest voorkomende waarde van het doel-attribuut in uit de voorbeeldenset

– Anders: Begin ∗ A = Het attribuut dat de voorbeelden het best klassificeert ∗ Beslisboom attribuut voor Wortel = A ∗ Voor elke moglijke waarde ν van A doe : · Voeg een nieuwe tak toe aande wortel voor de test A = vi . · Neem Voorbeelden(ν) de subset van de voorbeelden die waarde ν hebben voor A

· Als Voorbeelden(ν) leeg is voeg dan een blad toe aan de tak met als label de meest voorkomende doelwaarde in Voorbeelden

· Anders: Voeg de deelboom ID3 ( Voorbeelden(ν), DoelAttribuut, Attributen-{A}) toe aan de tak.

Enkele minpuntjes van ID3k • Het kan niet zo goed om met ruis en fouten in de data. • Deze methode stopt pas met trainen als er geen enkele uitzondering meer is in een blad en dus alle bladeren zuiver to 1 klasse behoren. Zo krijgen we bijzonder uitgebreide bomen met gevaar op overfitten van de data gebruikt voor de training.

2.4.2

C4.5

C4.5 is een uitbreiding op het standaard ID3- algoritme van Quinlan. Het maakt gebruik van na-snoeien van regels. Het omvat de volgende stappen: 1. Bouw gewoon de beslisboom uit de trainingset totdat deze data niet meer beter kan worden weergegeven door de boom, overfitten is dus toegelaten 2. De boom wordt omgezet in regels, elk pad van de wortel naar een blad is een regel. 3. We gaan elke regel bijwerken, snoeien, door voorwaarden die de juistheid van de boom op ongeziene voorbeelden verhoogt, aan de hand van een heuristiek. 4. Sorteer de regels op hun geschatte juistheid en gebruik ze in deze volgorde voor het klassificeren van voorbeelden. 14

C4.5 optimaliseert ID3 op volgende vlakken: Het vermijdt overfitten van trainingsdatadata Het kan continue attributen aan Kan omgaan met incomplete data en ruis Juistere en kleinere bomen worden gebouwd.

2.4.3

Classification And Regression Trees (CART)

CART construeert net zoals ID3(en dus C4.5) een boom door het splitsen van dataset in subsets. Belangrijk verschil is dat CART een binaire boom opbouwt waar bij ID3 een knoop in principe oneindig veel kinderen kan hebben.De splits zelf zijn in s e gelijk aan die van ID3. Bij het selecteren van een split wordt getracht de homogeniteit van de klassen van de resterende subsets te optimaliseren. Met andere woorden: CART probeert een split zo te kiezen dat de resterende subsets voorbeelden van e´e´n klasse bevatten. De bruikbaarheid van een split kan dus worden gedefinieerd als de mate van zuiverheid of onzuiverheid. Dus wordt bij het splitsen van de dataset geprobeerd de beste scheiding van de klassen te bereiken volgens een zuiverheids-criterium. Een boom wordt dan op de volgende manier gecreerd. Alle mogelijke kandidaat-splits worden bekeken om die split te vinden die de grootste afname bewerkstelligt met betrekking tot e´e´n of andere maatstaf van onzuiverheid. Het uitbreiden (opsplitsen) van een knoop stopt zodra er geen significante afname van deze maatstaf meer is. De klasse die dan aan deze knoop wordt toegewezen is de klasse die het meest voorkomt tussen de voorbeelden uit de subset.

2.5

Overzicht

We hebben nu een beknopte inhoud op beslisbomen gegeven. Als afsluiter zagen we enkele algoritmes. Deze algoritmen hadden alleen een heuristiek een split-criterium aan de hand waarvan ,bij het bouwen van de boom, een test wordt gekozen voor elke knoop waarop voorbeelden worden gesplitst. De criteria keken daarbij enkel naar het effect van de split in de knoop zelf. Het zijn lokaal optimale beslissingen. Er wordt niet gekeken naar het effect van deze beslissingen. Op deze manier wordt door telkens het lokaal optimale te nemen gehoopt globaal het optimale te bereiken. Dit laatste is uiteraard niet altijd het geval. Dit type van algoritmen noemen we greedy of gulzige algoritmen. We kijken nu in een volgend hoofdstuk naar een methode om verder te kijken dan lokaal optimale beslissingen.

15

Hoofdstuk 3

Lookahead 3.1

Wat is lookahead en waarom is het nodig?

We zagen in het vorige hoofdstuk dat de algoritmes die we tot nu toe hebben vernoemd hebben steeds lokaal optimale beslissingen maakten. Ook verbruikten ze een niet te kiezen relatief korte tijdsduur. Door deze begrenzing op de tijd en door het maken van de lokaal optimale beslissingen worden niet altijd globaal optimale bomen gebouwd. Dit zijn 2 beperkingen die we willen tegen gaan. Lookahead-gebaseerde algoritmes zijn hiervoor geschikt. We bekijken in dit hoofdstuk waar we lookahead moeten situeren en wat lookahead juist is. Dan bespreken we ook enkele papers met onderzoek naar lookahead algoritmes. We besluiten met een overzicht met de voor en nadelen.

We weten dus dat de geziene algoritmes een vaste en relatief beperkte hoeveelheid tijd nodig hebben om een boom te bouwen. Indien men wenst meer tijd te investeren om betere bomen te genereren is dit een optie waarvoor niet kan worden geopteerd. Daarom zijn andere methodes nodig die wel toelaten deze trade-off van tijd voor kwaliteit te maken. Een wijdverspreide manier om deze problematiek aan te pakken zijn de zogenaamde anytime algoritmes. Dit zijn algemeen algoritmes die toelaten om te kiezen hoeveel tijd we willen investeren in het bouwen van betere bomen. Een eerste soort van anytime algoritmes zijn de onderbreekbare methodes.Hierbij moet niet op voorhand vermeld zijn hoeveel recources worden toegekend maar kan elk moment het algoritme worden onderbroken en er moet ten allen tijde een bruikbaar antwoord kunnen gegeven worden. De tweede klasse is die van de contract-gebaseerde algoritmes waarbij op voorhand een soort contract wordt afgesloten tussen het algoritme en de gebruiker over hoeveel tijd we zouden willen investeren. Dit contract is een parameter die een indicatie geeft over hoeveel tijd het algoritme gaat mogen verbruiken, echter het gaat geen opgelegde vaste ree¨ele tijd vastleggen. Tot deze klasse rekenen we de lookahead-gebaseerde algoritmes Later zullen we enkele lookahead-algoritmes bekijken waarin het idee achter de contract-parameter duidelijker wordt. Maar met lookahead-gebaseerde algoritmen kunnen we het probleem van de trade-off dus tijd en kwaliteit oplossen. Een ander minpunt van gewone gulzige algoritmes is dat ze lokaal beslissingen maken en geen backtracking toelaten, bijgevolg heeft een slechte keuze bij 1 knoop onomkeerbare 16

gevolgen voor al de latere beslissingen. Men kan wel de bomen snoeien en op die manier de boom kleiner en beter maken maar dit is geen oplossing om minder goede beslissingen ongedaan te maken, logisch, gezien deze techniek bedoeld is om overfitten van de training data tegen te gaan. Ook dit probleem kan worden opgelost door gebruik te maken van lookahead. We weten nu waarom lookahead nuttig kan zijn, tijd om uit te leggen wat lookahead nu precies inhoudt. Stel we bouwen een boom en we zijn in een knoop en we willen een test bepalen voor deze knoop. In plaats van enkel het effect van de keuze van een attribuut op het niveau van de knoop zelf te bepalen gaan we ook verder kijken. We gaan vooruit kijken hoe de boom er zou uitzien als we een bepaalde keuze voor een test maken. We kijken eigenlijk naar knopen die later gevormd zullen worden op een dieper niveau en naar wat het effect is van de keuze in de huidige knoop. We kunnen zo bijvoorbeeld bij een keuze van een test een niveau dieper gaan kijken wat het effect is van de keuze op de performantie van de kinderen. We zien dit geillustreerd in figuur 3.1. Links zien we de situatie zonder lookahead, dus zoals we zagen bij de gulzige algoritmes uit het vorig hoofdstuk. We kiezen de beste test uit alle mogelijke n testen aan de hand van een lokaal optimale heuristiek. In het midden zien we lookahead tot op diepte 1, waarbij we gaan kijken wat het effect is van elke test een level lager. Het komt er op neer dat we alle mogelijke combinaties van n testen met de n−1 telkens overblijvende testen. De combinatie van de 2 testen die het beste resultaat geeft volgens de heuristiek wordt dan gezocht bvb(test 7, test 2) dan nemen we in dat geval test 7 als test om te splitsen in de knoop waarvoor we lookahead deden. In de meest rechtse strook zien we lookahead tot op diepte 2, voor elke test kijken we naar het effect tot op 2 levels later. Dit komt neer op de combinatie van alle n testen met alle n − 1 overblijvende testen die ook weer met alle overblijvenden n − 2 worden gecombineerd. De beste combinatie van 3 testen wordt weergezocht en de test in de knoop die voor de beste combinatie zorgt wordt gekozen als test voor de knoop. Zo kunnen we lookahead doen tot op diepte 3, diepte 4 etc tot op diepte n, waarbij we uiteindelijk uit alle mogelijke deelbomen de beste gaan halen. Volledige lookahead van uit de wortel geeft de optimale boom. Echter het doorzoeken van de volledige ruimte van alle mogelijke bomen kan erg tijdrovend worden en veel geheugen en rekenkracht vergen . Daarom wordt doorgaans gekozen voor lookahead tot op kleinere diepte uit te voeren om zo gemiddeld betere bomen te maken, naargelang we er meer tijd in steken.

17

Figuur 3.1: Lookahead

We bespreken kort enkele papers en bevindingen omtrent Lookahead om een dieper inzicht te krijgen in het nut en bruikbaarheid van Lookahead-gebaseerde algoritmes. Nadien bekijken we enkele praktisch uitgewerkte algoritmes.

3.2

Pathologie van Lookahead

Wanneer one-level lookahead wordt vergeleken met gewone greedy algoritmes zien we dat deze geen betere beslisbomen oplevert en soms zelfs minder goede resultaten geeft. De kwaliteitscriteria op basis waarvan de vergelijking wordt gemaak zijn accuraadheid, grootte en diepte. Het enige dat bij 1-level lookahead beter is, is de diepte van de boom. Dit is dan nog te wijten aan het slecht uitgebalanceerd zijn van de bomen die worden gebouwd door greedy algoritmes. Dit kan verholpen worden door de boom uit te balanceren door middel van rotaties. De grootte van de bomen bij lookahead is niet significant kleiner en wanneer we bij de greedy methodes gebruik maken vam pruning geeft dit zelfs kleinere en dus betere bomen

18

dan bij one-level-lookahead. Bij een aantal problemen is de accuraadheid bij lookahead zelfs minder goed. Dit is een pathologie, analoog aan spelbomen waarbij uitgebreider zoeken minder goede resultaten geeft.

3.3

Lookahead gebaseerde Fuzzy beslisboom-inductie

Fuzzy ID3 is een variant op ID3 voor continue data. Het maakt gebruik van een aanpassing van entropie en informatie winst. Net zoals ID3 bevoordeelt het attributen met veel waarden en dit wordt op analoge wijze als bij ID3 opgelost.We gaan hier niet in de op de details, maar het doel bij lookahead is het evalueren van de klassificeerbaarheid van voorbeelden die gesplits worden langs takken van een knoop. De vraag is hoe die evaluatie moet gebeuren. Meestal gebeurt dit aan de hand van een paramater identiek aan aan degene die de split evalueert. M.Dong en R.Kothari stellen voor de klassificeerbaarheid met een niet-parametrische methode uit te voeren. Deze wordt duidelijk door het visualiseren van variabelen waarbij het relief de doelvariabele is.We zien hieronder de verdeling van enkele voorbeelden in 2 dimensies, met als derde dimensie dus de klasse. De verdeling van de voorbeelden in de rechtse figuur toont

vlakke oppervlakten met samples van dezelfde klasse. Deze is beter om verder mee te gaan om de klassificeren.Hoe minder waarden afhankelijk zijn van de waarden van een andere klasse hoe vlakker het oppervlak en hoe geschikter om te klassificeren. Voor de verdere uitwerking hiervan wordt gebruik gemaakt van cooccurentie matrices.

3.4

Skewing, een alternatief voor lookahead.

Gulzig algoritmes zijn dus kortzichtig en lookahead is een goede manier om dit probleem op te lossen. Voor bepaakde functies, zoals de zogenaamde pariteitsfuncties (bvb. XOR) kan dit niet voldoende zijn indien lookahead niet diep genoeg gaat, hoewel een optimale boom kan worden verkregen door wel diep genoeg te gaan. Bijvoorbeeld x95 ⊕x96 ⊕x97 ⊕x98 ⊕x99 ⊕x100 kan door lookahead worden opgelost met een optimale boom op voorwaarde dat de lookahead gaat tot op diepte 6. Minder diepe lookahead geeft slechte resultaten. Een alternatief voor het rekenintensieve lookahead om deze probleemfuncties aan te pakken is skewing. We merken op dat de probleemfuncties geen probleem meer zouden geven indien de verdeling genoeg verschillend van de normaalverdeling zou zijn. Meestal hebben we maar 1 verdeling, we kunnen nu een tweede verdeling simuleren door middel van skewing (”scheef maken”) aan de hand van de eerste verdeling; waarbij de tweede significant verschillende frequenties heeft dan de originele.

19

Omdat we niet zomaar uit het niets nieuwe voorbeelden kunnen trekken moeten we het stellen met degene die we hebben. We veranderen de verdeling door gewichten toe te kennen aan deze voorbeelden. We geven eerst elk voorbeeld een gewicht van 1 en we gaan dan de gewichten herwegen. We nemen aan dat een variabele niet in elk voorbeeld dezelfde waarde aanneemt anders draagt de variabele niets bij en mag hij worden verwijdert. In het onderzoek werd uitgegaan van binaire variabelen, dus zowel waarden 1 en 0 worden dan aangenomen door een voorbeeld voor elke variabele. Vervolgens wordt voor elke variabele een waarde als favoriete setting gekozen. Voor elk voobeeld wordt dan voor elk attribuut waarvoor hij de favoriete setting heeft vermenigvuldigd met een skew-waarde s. Zo krijgt elke variabele een gewicht tussen 1 en sn . Het is zeer waarschijnlijk maar niet zeker dat we zo een compleet verschillende frequentie verdeling krijgen. Verder kunnen ook idiosyncrasies (individuele overgevoeligheid) uit de originele data worden uitvergroot. Deze problemen kunnen worden opgelost door meerdere verdelingen te genereren. Verschillende verdelingen hebben minder kans om dezelfde idiosyncrasies uit te vergroten. Daarom genereren we k verdelingen. Variabelen die geen deel uitmaken van de doelfuntie zullen een winst hebben die dicht bij 0 ligt in de meeste verdelingen. Een winst − drempel zorgt dat enkel de variabelen die in de meeste verdelingen duidelijk meer dan 0 − winst hebben worden beschouwd voor een split. We geven op de volgende pagina het skewing-algoritme voor de volledigheid. Het is niet belangrijk voor war volgt om dit te bekijken.

20

Algoritme Algorithm 1 Skewing Require: Matrix D met m datapunten over n boolse waarden, winstfractie G, aantalt trials T en skew 21 < s < 1 Ensure: Variabele xi voor een split, of −1 als er geen variabele met voldoende winst wordt gevonden 1: N ⇐ Entropie van de klasse variabele in D 2: v ⇐Variabele met de hoogste winst in D 3: g ⇐ winst van v in D 4: if g < G × N then 5: v ⇐ −1 6: end if 7: for i = 1 to n do 8: F (i) ⇐ 0 9: end for {begin skewing loop} 10: for t = 1 to T do 11: for i= 1 to n do 12: V (i) ⇐ Random gekozen waarde voor xi 13: end for 14: for e = 1 to m do 15: W (e) = 1 16: for e = 1 to n do 17: if t > 1 then 18: if D(e, i) = V (i) then 19: W (e) ⇐ W (e) × s 20: else 21: W (e) ⇐ W (e) × (1 − s) 22: end if 23: end if 24: end for 25: end for 26: N ⇐ Entropie van de klasse variabele in D onder W 27: for i=1 to n do 28: E ⇐ W inst van xi onder verdeling W 29: if E >= G × N then 30: F (i) ⇐ F (i) + 1 31: end if 32: end for 33: end for{einde skewing loop} 34: j ⇐ arg max F (i) 35: if F(j) > 0 then 36: return xj 37: else 38: return v 39: end if 21

3.5

Lookahead gebaseerde algoritmes

We bekijken nu enkele specifieke vormen van een anytime contract-gebaseerd algoritmes volgens het look-ahead principe. Ze zijn gebaseerd op het van de wortel naar beneden induceren van de bomen trees waarbij een attribuut wordt gekozen om de dataset in subsets te verdelen om zo recursief een boom op te bouwen, net zoals bij de greedy algoritmes. Het is dus vooral de manier waarop een attribuut voor de split wordt gekozen die het verschil zal maken

3.5.1

ID3-k

We zagen hoe we de entropie kunnen berekenen om het beste attribuut te zoeken voor een split. We herschrijven de formule voor het berekenen het gemiddelde van de entropie van de subsets na een split aan de hand van attribuut a als volgt: Entropie − 1(E, a) =

|Ev | vwaarden(A) |E| Entropie(Ev )

P

Waarbij ”1”vertelt dat het effect van de split is bekekeb tot op diepte 1. We kunnen deze definitie uitbreiden voor diepte k. We krijgen ze een recursief algoritme dat de k − 1-entropie gaat minimaliseren voor elk kind. Waarbij k de parameter is die de contracttijd bepaalt voor de lookahead. Dit is de parameter die waar we in de inleiding van het hoofdstuk over vertelden, hij bepaalt hoe lang het algoritme gaat lopen zonder een specifieke tijd er op te zetten. De tijd tussen k en k + 1 lookahead neemt exponentieel toe bij stijgende k. Procedure 2 Entropie-k(E, A, a, k) 1: if k = 0 then 2: return I(PE (c1 ), . . . , PE (cn )) 3: V ⇐ domein(a) 4: end if 5: for all vi ∈ V do 6: Ei ⇐ {e ∈ E — a(e) = vi } 7: for all a0 ∈ A do 8: A0 ⇐ A − {a0 } 9: hi (a0 ) ⇐ Entropie − k(Ei , A0 , a0 , k − 1) 10: end for 11: end for P|V | |Ei | 0 12: return i=1 |E| mina0 ∈A (hi (a ))

3.5.2

Lookahead met stochastische ID3

Om de kost van een lookahead te verminderen kunnen we een minder diepe lookahead uit te voeren of door op elk niveau enkel die attributen te gebruiken die het meest belovend zijn. ID3 wordt dan gebruikt om te kijken welk de meest belovende attributen zijn. Voor een attribuut a splitsen we data in subsets en op elk van deze sets passen we ID3 toe,wat niet erg intensief is qua tijd en recources. We krijgen zo een aantal deelbomen waarvan we de gemiddele grote nemen als schatter voor de totale boom indien a zou worden gebruikt als splitter. Dit is uiteraard nog geen contract gebaseerd algoritme.Om dit probleem op te lossen 22

en om beter schattingen te krijgen gaan we Stochastisch ID3(SID3) gebruiken. Bij SID3 gaan de split random kiezen met een kans rechtevenredig tot zijn inf ormatiewinst, behalve als er variabelen zijn met entropie 0, dan word daar eentje uit gekozen.Verschillende runs van SID gaan dus andere attributen ”kiezen”voor de testen en dus andere bomen construeren.Lookahead met SID3 gaat dus voor elk kandidaat-attribuut de geschatte grootte van de deelbomen evalueren en de beste kiezen. Voor elke deelboom hebben we meerdere schattingen, allemaal bovengrenzen van de optimale boom. We onthouden dus alleen de laagste schatting voor van elk deelboom. Dit voor alle deelbomen voor een attribuut a. De contract-parameter vinden we in het aantal keer we een schatting gaan maken voor elke deelboom en de tijd zal lineair groeien ten opzichte van deze parameter. Procedure 3 LSID3-choose-Attribute(E, A, r) 1: if r = 0 then 2: return ID3-Choose-Attribute(E,A) 3: end if 4: for all a ∈ A do 5: for all vi ∈ domein(a) do 6: Ei ← {e ∈ E — a(e) = vi } 7: mini ← ∞ 8: Repeat r times 9: mini ← min(mini , SID3(Ei , A − {a})) 10: end for P|domein(a)| 11: totaala ← i=1 mini 12: end for 13: return a waarvoor totaala minimaal is.

3.6

Besluit Lookahead

De verschillende onderzoeken geven verschillende bevindingen, het ene onderzoek door Dong en Kothari met fuzzy beslisboom beweert dat lookahead betere bomen geeft waar Murthy en Salzberg juist een pathologie aantonen en aangeven dat lookahead zelfs minder goed zou presteren. Wat moeten we nu geloven? Als we beide papers bekijken zien we dat de onderzoekers opteren voor een lookahead tot op diepte 1. Dit kunnen we uiteraard niet erg exhaustief noemen,we kunnen zelfs niet echt van lookahead spreken, dus een algemeen besluit over lookahead op zich mogen en kunnen we er dan ook niet uit halen. Dit wordt ook aangehaald in de paper van Esmeir en Markovitch. Zij deden wel onderzoek met behulp van echte lookahead-algoritmes tot op grotere diepte en doorgaans gaven deze wel kleinere en ook juistere bomen dan algoritmes zonder vooruitkijken. Er werd geen gebruik gemaakt van snoeien, waardoor C4.5 wel kleinere bomen voortbrengt dan ID3-k en LSID, de juistheid van lookahead was niet minder dan die van C4.5. Voor sommige speciale problemen werkt lookahead niet optimaal, daarvoor werd skewing als alternatief bedacht. Maar algemeen denk ik dat we mogen besluiten dat voor een groot deel van de gekende problemen, lookahead gebaseerde algoritmes beter presteren op gebied van grootte en juistheid van de gebouwde bomen dan algoritmes zonder lookahead. Nadeel is dat deze lookahead soms heel tijdsintensief kan worden voor er duidelijk betere voorbeelden uitkomen. Het blijft een keuze die moet worden afgewogen. 23

Hoofdstuk 4

Achteruitkijken: een voorstel We hebben in hoofdstuk 2 enkele simpele gulzige algoritmes gezien en in hoofdstuk 3 kwamen lookahead-gebaseerde algoritmes aan bod. Ze hebben elk hun voor- en nadelen en het is een af te wegen keuze om al dan niet de ene of de andere te nemen. Enerzijds kort maar niet optimaal ,anderzijds tijdsintensief en beter en indien volledige lookahead wordt toegepast zelfs optimaal. Nu is er nog een andere techniek die we kunnen gebruiken om gulzige algoritmes te verbeteren, namelijk achteruit kijken, we stellen 2 algoritmes voor. Doorheen deze thesis zullen we deze ”algoritme2¨en ”algoritme3”noemen. Deze benaming komt van het feit dat ze een gulden middenweg zouden kunnen vormen tussen aan de ene kant gewone greedy algoritmes(1) en het rekenintensieve lookahead algoritme(4) aan de andere kant. We geven nu een beschijving en visualisatie van de algoritmes

4.1

Algoritme 1: gulzig algoritme

Dit zijn de algoritmes uit hoofdstuk 2 zoals ID3, C4.5 of CART die lokaal optimale beslissingen maken.

Figuur 4.1: Algoritme 1: gulzig algoritme

4.2

Algoritme 2

Eerst zoeken we in een knoop op de gewone manier de beste test, A. We splitsen dan de data aan de hand van deze set. We nemen nu het linkerkind en ook hier zoeken we de beste test, B. Vervolgens kijken we of de samengestelde test A,B een betere split zou uitvoeren dan 24

de originele test A, in de ouder-knoop. Als dat het geval is vervangen we test A door de samengestelde test A,B. Nu gaan we gewoon verder; we splitsen weer de data aan de hand van de test, zoeken de beste test in het linkerkind en weer kijken we of het betere zou zijn om deze naar boven te schuiven.

Figuur 4.2: Algoritme 2

4.3

Algoritme 3

Dit algoritme lijk sterk op algoritme 2. We kiezen weer eerst de beste test in de ouderknoop, A. Vervolgens splitsen we de data en bekijken we alle tests b1 , b2 , . . . , bn die we kunnen kiezen in het linkerkind om verder te splitsen. We bekijken nu alle mogelijke geconjugeerde test A, bi met 1 < i < n. We nemen de beste test uit deze geconjugeerde tests en kijken of deze beter presteert in de ouderknoop dan test A alleen. Indien dit het geval wordt test A vervangen door de beste geconjugeerde test A,bi en gaan we weer gewoon verder.

Figuur 4.3: Algoritme 3

25

4.4

Algoritme 4:Lookahead

Figuur 4.4: Algoritme 4: Lookahead gebaseerde methode

26

Hoofdstuk 5

ILP, ACE en Tilde 5.1

Inductief Logisch Programmeren

Doorgaans hebben we bij machine learning-taken, een set van data waaruit we een algemeen model gaan induceren. We kunnen dit veralgemenen naar het leren van meer algemene kennis uit gegeven kennis. Om deze kennis te kunnen voorstellen hebben we een goede voorstellingsmethode nodig zoals eerste orde logica (FOL). Data staat vaak beschreven in een enkele tabel waarbij elk voorbeeld bestaat uit 1 vector met vaste attributen en hun waarden. Soms is deze manier van data beschrijven niet voldoende,denken we maar aan Multi Instance Problemen. Ook hier hebben we een betere manier van representatie nodig die eerste orde logica kan voorzien. Een ander voordeel van eerste orde logica is de mogelijkheid om buiten de voorbeelden extra informatie mee te geven om van te leren, een stuk extra achtergrondkennis. Logica is dus een goede manier om algemeen kennis voor te stellen. Logische programma’s bestaan uit Horn clauses. Een voorbeeld wordt beschreven door een set van feiten, clauses, waarvan de grootte kan vari¨eren. De manier waarop eerste orde logica de feiten weergeeft kunnen we ook weergeven als een relationele databank.

Figuur 5.1: Voorbeeld uit Bongard dataset van hoe data wordt voorgesteld door eerste orde logica

De voordelen van FOL zijn, om op te sommen, de mogelijkheid om complexere data voor te stellen, extra achtergrondkennis kan worden meegegeven en we hebben een krachtigere taal

27

om hypotheses te formuleren. Inductief logisch programmeren gebruikt FOL en voorziet dus deze voordelen. Een veelgebruikte programmeertaal om dit te implementeren is Prolog. Redeneren in logica gebeurt echter meestal door middel van deductie waarbij uit algemene concepten meer specifieke concepten worden afgeleid. Deze manier van redeneren is uiteraard altijd correct. Nu willen we logica gebruiken voor inductie; de omgekeerde bewerking. De operatoren die veel worden gebruikt voor inductie zijn gebaseerd op theta-subsumptie. Een clause c1 theta-subsumed een andere clause c2 als er een variabele bestaat zodat hij een subset wordt van de andere: c1 ≤θ ⇔ ∃θ : c1 θ ⊆ c2 Dus is c2 een speciaal geval van c1 . De operator voor generalisatie is de least general generalisation (lgg).

5.2

Logische beslisbomen en Tilde

Wat betreft ILP is het domein van de beslissingsbomen lang genegeerd geweest. De grootste reden waarom bomen niet veel worden gebruikt met ILP komt door het verschil tussen de voorstelling van ILP met behulp van clauses en de onderliggende structuur van beslisbomen. Het werk van Blockeel en De Raedt bracht hier verandering in. Ze introduceerden een voorstelling van logische beslisbomen conform die van het clause-gebaseerde inductief logisch programmeren. Verder ontwikkelden ze op basis van deze voorstelling een algoritme voor het bouwen van bomen. Het is gebaseerd op het aanpassen van heuristieken van C4.5 en gaat onder de naam Tilde. We bespreken kort het werk Blockeel en De Raedt in deze sectie.

5.2.1

Logische beslisbomen

De methode voorgesteld door Blockeel en De Raedt maakt gebruik van Prolog. Elk voorbeeld is een set van clauses gedefinie¨erd in Prolog. We hebben buiten de set van voorbeelden E ook extra achtergrondtheorie B en een set van klassen C. Het doel is het vinden van een hypothese bestaande uit welomlijnde clauses, zodat: ∀e ∈ E, H ∧ e ∧ B |= c en H ∧ e ∧ B niet |= c0 met c is de klasse van voorbeeld e en c0 ∈ C − {c} Definitie Logische Beslisboom Een logische beslisboom(LBB) is een binaire beslisboom waarbij elke test een conjunctie is van literals. Indien een variabele nieuw is in een knoop en dus niet voorkomt in hogere knopen, zal deze variabele niet voorkomen in de rechterdeelboom omdat de rechterdeelboom de voorbeeldenset zal bevatten die negatief zijn voor de test. Dit omdat nieuwe variabelen gekwantificeerd worden in de conjunctie en de rechterboom is net de deelboom relevant is voor wanneer de conjunctie niet slaagt voor de test en er dus geen ”X”voldoet aan de test, dus is het zinloos om later nog van die onbestaande ”X”te spreken. We gebruiken zulk een LBB nu voor de klassificatie van een voorbeeld, dit voorbeeld is nog steeds een Prolog-gegeven. Een test op het voorbeeld e komt overeen met kijken of de clause in de test slaagt met e ∧ B, met B de achtergrondkennis. Het voorbeeld begint in de wortel, de algemene query is ”waar”. Als e voldoet aan de test 28

in de knoop wordt het naar het linkerkind geschoven en wordt de nieuwe algemene query uitgebreid met de test van de knoop, indien de test niet slaagt gaat het voorbeeld naar het rechterkunt. Zo wordt het voorbeeld van de wortel naar beneden door de boom geleid tot het in een blad komt, het klasse-label van dit blad is dan de klasse waarin het voorbeeld wordt geklassificeerd. Logische bomen en logische programma’s Vervolgens gaan Blockeel en De Raedt een logische boom proberen te identificeren met een logisch programma. Hiertoe associ¨eren ze met elke knoop een eigen welomlijnde clause die een predicaat definieert zonder argumenten. Verder heeft ook elke knoop een Horn-vraag die gebruik kan maken van predicaten uit knopen hoger in de boom.

5.2.2

Tilde

Tilde is bijvoorbeeld zulk een algoritme om een beslissingsboom te leren uit een relationele databank. Een algoritme Het algoritme dat werd voorgesteld is gebaseerd op een simpel basis recursief TDIDT algoritme. Het is een aangepaste versie van C4.5,geschikt voor relationele data mining. De boom wordt van de wortel uit gebouwd, indien in een knoop,deelboom, de set van voorbeelden homogeen genoeg is wordt het een blad met klasse-label de meest voorkomende klasse van de voorbeelden. Als de homogeniciteit nog niet voldoende is wordt de data gespitst op de query die het beste is volgens de winstratio. De Horn-query van een knoop wordt als argument meegegeven en voor de linkerdeelboom telkens uitgebreidt met de test waarop wordt gesplitst. In het algemeen is het algoritme gebaseerd op C4.5, het heeft dezelfde heuristiek voor de tests, met name de winstratio. Hoewel alle splits binair zijn en er dus geen attributen zijn met meer mogelijke waarden waardoor deze worden bevoordeeld door inf ormatiewinst, blijkt dat winstratio alsnog beter presteert. Ook worden weer testen met een winst onder een bepaalde grens op voorhand gefilterd. Nog wordt net zoals in C4.5 de boom volledig gebouwd om nadien gesnoeid te worden. Het stop-criterium ,weer zoals dat van C4.5, zegt dat er gestopt wordt met splitsen als de set van voorbeelden in een knoop onder een bepaalde grootte gaat. Het overfitten dat zo onstaat wordt uiteraard opgevangen door het snoeien van de boom. Specificatie van de taal Implementatie: Tilde

5.2.3

Lookahead in Tilde.

In ILP kan het intressant zijn om een conjunctie toe te voegen in een knoop die niet meteen iets bijdraagt maar later in de boom wel handig kan zijn doordat ze leuke nieuwe variabelen introduceert. Om dit vast te stellen hebben we een vorm van lookahead nodig. Tilde gaat niet expliciet na gaan of er literals zijn waarvoor dit intressant kan zijn. Wel gaat lookahead in Tilde de gebruiker toelaten dit zelf te specifici¨eren. We kunnen dingen toevoegen van de vorm:

29

lookahead(hconjunctie1i, hconjunctie2i) Dit geeft aan dat wanneer een conjunctie die overeenkomt met conjunctie1 wordt toegevoegd als test aan de query moet meteen worden geprobeerd om alle instanties van conjunctie2 toe te voegen aan de test.

5.3

ACE

ACE is een data mining systeem dat een gemeenschappelijke interface voorziet voor een aantal algoritmes voor relationele data mining, dus voor het zoeken van patronen in relationee databanken met meerdere tabellen. Tilde is een van de algoritmes die ge¨ımplementeerd zijn, verder zijn onder andere volgende algoritmen in ACE terug te vinden Warmr een update van het Apriori algoritme voor relationele data-mining en ICL een versie van CN2. Voor een dataset waarop een algoritme uit het gamma van ACE willen toepassen hebben we een aantal invoer bestanden nodig. De bestanden worden in Prolog ge¨ımplementeerd. Om te beginnne zijn er uiteraard de voorbeelden die we gaan gebruiken voor training en testen van de boom. Deze vinden we terug in een .kb bestand, de ”knowledge base”, de kennis over de voorbeelden. Verder hebben we eventueel extra achtergrond kennis die we terugvinden in een .bg bestand. Als laatste invoerbestand hebben we een bestand met settings, waarin een aantal parameters kunnen worden bepaald. De taal die wordt gebruikt wordt bepaald door de operator die zorgt voor de verfijning. Deze is gespecifieerd door gebruik te maken van het rmode-predikaat: rmode(conj ) Wat wil zeggen dat een verfijning kan bestaan uit toevoegen van de conjunctie aan de query die moet worden verfijnt. Deze conjunctie kan soms maar een aantal keer worden toegelaten voor een verfijning, dit noteren we als: rmode(N: conj ) met N een natuurlijk getal of oneindig. Wanneer een literal wordt toegevoegd kan deze een aantal constanten bevatten als een van zijn argumenten. Opdat er men niet alle mogelijkheden tot vervelens toe zou moeten specifieren zijn er in ACE een aantal manieren zien waarop dit automatisch kan, deze zijn terug te vinden in de User Manual. We kunnen voor variabelen ook voorwaarden vastleggen indien ze op bepaalde plaatsen voorkomen constraint(conj, constr). Wanneer conjugatie conj wordt toegevoegd aan een clause moet aan de voorwaarde constr voldaan zijn. Verder kunnen we ook types specifi¨eren en lookahead specificaties meegeven, zoals die bij Tilde.

30

Hoofdstuk 6

Multi Instantie Problemen In vorig hoofdstuk maakten we kennis met ACE en Tilde, een algoritme voor het bouwen van beslisbomen. Tilde is een goed algoritme, echter door de specificaties van de taal en de omgeving is het niet optimaal voor het oplossen van Multi instantie problemen. We geven in dit hoofdstuk kort weer wat MIP juist zijn, waar het probleem met Tilde zich bevindt. Dan schetsen we wat we op dit gebied met de voorgestelde achteruikijk algoritmes zouden willen bereiken.

6.1

Wat zijn Multi Instantie Problemen?

We illustreren eerst met een voorbeeld uit het werk van Dietterich. Stel we werken in een conservatief bedrijf dat nog met sleutels en sloten werkt. Stel we hebben de deur van de voorraadkamer, met een slot waarvoor er meerdere sleutels bestaan. Elke werknemer van het bedrijf heeft een sleutelbos met sleutels. Bij sommigen past de sleutel van voorraadkamer ook nog op andere deuren, bij andere alleen op de voorraadkamerdeur. Een sleutelmaker wil nu een loper wil maken met de meest algemene vorm om de deur te openen. Elke werknemer levert daarom zijn sleutelbos in zonder te zeggen welk zijn sleutel voor de voorraadkamer is. De sleutelman krijgt ook geen permissie om de voorraadkamer te betreden en mag dus de sleutels niet uitproberen. Door een uitgebreide studie van de vorm van de sleutels zal hij zijn loper moeten maken. In wat voorging zagen we dat de data bestaat uit een aantal voorbeelden die al dan niet tot een klasse behoorden. Bij MIP hebben we een ander gegeven, de data bestaat uit groepen(cfr.sleutelbos) waarvan geweten is of het al dan niet een positieve instance bevat, van de afzonderklijke instanties is niet geweten of ze al dan niet positief zijn. De vraag van het probleem is nu het leren van een functie f zodat deze individuele instanties kan klassificeren en waar voor geldt dat wanneer een groep een positief voorbeeld bevat als en slechts als een van zijn instanties door f als positief is geklassificeerd. We spreken zo dus van positieve en negatieve groepen. Voorbeelden zijn positief als ze tot een positieve groep behoren, echte positieve voorbeelden zijn ook echt positief, valse positieve voorbeelden zijn negatief maar behoren tot een positieve groep. Alle voorbeelden in een negatieve groep zijn ook echt negatieve voorbeelden per definitie.

31

Figuur 6.1: Vendiagram van negatieve, echte positieve en valse positieve voorbeelden

6.2

MIP en Tilde

Volgens Blockeel en De Raedt[1998] is leren van een MIP een speciale vorm van ILP. Ze ontwikkelden een ILP-systeem, TILDE(zie hoofdstuk 3), dat beslisbomen bouwt.Het kan een bias gegeven worden aan de hand waarvan het dan multi instantie bomen kan leren. De bias die TILDE voorziet bevat niet alle multi-instance concepten en ook concepten die niet tot die van de multi-instance ruimte behoren, een voorbeeld:

In de tekening[Multi Instance Tree Learning, Blockeel et Al] zien we een propositie boom en een eerste orde boom. De eerste geeft A ∧ B ∨ C ∧ D weer. De eerste orde boom drukt dan weer volgende regel uit: (∃x ∈ B : a(x) ∧ b(x)) ∨ (∃x : a(x) ∧ c(x) ∧ d(x)) ∨ (∃ geen x ∈ B : a(x)∧∃x ∈ B : c(x)∧d(x)), wat buiten de ruimte van de multi-instantie concepten valt. Hierbij zijn a(x), b(x), c(x) en d(x) testen waarop de set van voorbeelden wordt gesplitst. De eerste test is a(X), indien een voorbeeld voldoet wordt hij naar de linkerdeelboom geschoven en daar op b(X) getest en zo gaat het voorbeeld verder de boom door naar beneden. Stel dat we nu een positief voorbeeld hebben dan zal deze in 1 van de 3 bladeren terechtgekomen met positief label en de geconjugeerde testen van de knopen die we doorlopen op het pad naar die bladeren zijn precies de regels weergegeven door voorgaande formule. Dit probleem kan worden aangepakt op een aantal manieren zoals een andere bias waarmee we een superset van multi-instantie concepten defini¨eren maar waardoor we wel het te leren probleem minder strenge voorwaarden opleggen. Of men kan de juiste set defini¨eren door de lookahead van TILDE te gebruiken en zo linaire bomen bouwen. Echter dit zijn beperkingen die we niet wensen op te leggen. We kijken nu even terug naar het voorbeeld en naar de regel die we eigenlijk willen representeren met een eerste orde boom: ∃x ∈ B : a(x) ∧ b(x) ∨ c(x) ∧ d(x)). De eerse orde boom die deze regel weergeeft is de volgende:

32

Om deze boom te verkrijgen moeten we meerdere tests in een knoop kunnen krijgen. Dit was het geval wanneer we zouden gaan achteruitkijken en knopen naar boven schuiven zoals in de voorgestelde algoritmes 2 en 3. We kunnen proberen om deze algoritmes toe te passen op data van multi-instance problemen. We gaan dan kijken of dit betere resultaten geeft en dat dus de juiste tests worden samengevoegd en de juiste bomen worden gebouws. Dit is een beetje ¨a shot in the dark”, maar in principe als de testen worden gekozen en samengevoegd zijn ze beter dan wanneer ze niet worden samengevoegd en kan de boom ook beter zijn. We komen hierop terug met resultaten in hoofdstuk 9.

33

Hoofdstuk 7

Studie originele code van Tilde Voor deze thesis is het niet intressant om alle modules te bekijken die voorhanden zijn. Er zullen slechts enkele ervan moeten worden aangepast en het is daarom ook niet nodig om alle mogelijke code te bekijken en te begrijpen. We geven een overzicht van de modules die van belang zijn, wat voor deze thesis nu juist van belang en een woordje uitleg bij de code zelf. Deze is achteraan te vinden in bijlage 1.

7.1

Tdidt.gen

Deze eerste module is meteen de intressantste en degene die we het meeste gaan gebruiken om de eigen algoritmes te implementeren. Het is de module die ervoor zorgt dat een logische beslisboom gebouwt wordt. De structuur van zulk een boom is gedefini¨eerd als: ldt(T ree, Inf o) met een knoop X gegeven als X = inode(test(T est, h(V alue)), Lef tBranch, RightBranch) of X = leaf () Inf o is elke soort extra informatie die nuttig is zou kunnen zijn V alue is de waarde van een bepaalde heuristiek voor de T est in de knoop. We gaan nu specifiek in de code kijken en deze overlopen. De methode refine node in de klasse tdidt wordt opgeroepen op een nieuwe instantie TIDIDT van tdidt door een methode met dezelfde naam buiten de klasse in het begin van de module. Deze gaat zorgen dat de boom gaat groeien. De parameters die worden gebruikt zijn : Distr: Een iterator over de gewogen set van voorbeelden in een knoop Language: de taal waarmee we gaan werken Node: De knoop zelf die we gaan maken, de eerste keer zal dit de wortel zijn; Root. Via de language-parameter kunnen we het Pack verkrijgen , deze bevat alle testen in de knoop. Refine nodes wordt opgeroepen met voor parameter Node, de waarde Root. De wortel wordt dus logischerwijs eerst gemaakt, anders zou het geen Top down-inductie zijn. De vorm van een node in ACE bevat het linker-en recherkind, dus we weten pas volledig wat node is als we deze kinderen hebben gebouwd. Deze worden recursief gebouwd met de methode refine nodes recursive(). Vanuit de wortel wordt dus de boom recursief opgebouwd. De functie refine nodes recursive heeft als parameters de distributie van voorbeelden, de node waar het 34

over gaat en het pack van mogelijke testen.De eerste keer is node dus gelijk aan de wortel. In de recursieve methode wordt eerst knoop verfijnt. Dit door de oproep van refine node(Distr, Node, Pack, LPack, LDistr, RPack, RDistr). Waarbij LPack,LDistr, RPack en RDistr respectievelijk de set van voorbeelden en het pack van tests zijn van het respectievelijke linker-en rechterkind. Indien de knoop die via node wordt doorgegeven, van de juist vorm is, wordt het linkerkind en het rechterkind met de juiste parameters verfijnd. In het andere geval is de knoop een blad en wordt er gewoon true teruggegeven. Hoe werkt de verfijn methode refine node nu juist? De invoer parameters zijn Distr, de voorbeelden en het pack van tests. Indien dit pack voldoet aan een stopcriterium wordt een blad gemaakt, anders gaan we verder met verfijnen. Er wordt een sample genomen van de voorbeelden. Het pack wordt gekopieerd naar de uitvoer-paramaters Lpack en Rpack, de packs van het linker-en rechterkind. Dan wordt het pack verfijnt en krijgen we een verfijnd pack, waaruit we de beste test gaan zoeken. Indien er geen beste test uit de bus komt, wordt de knoop een blad, anders gaan we verder en wordt het pack van het linkerkind uitgebreid met de gevonden beste test. De voorbeeldel worden gesplitst op de test in een set voor het linkerkind voor de voorbeelden die slagen voor de test, LDistr en een set van falende tests, RDistr, voor het rechterkind. Dan wordt de structuur van de knoop gemaakt en toegekend aan uitvoer-parameter Node. En gaan we verder met het recursief verfijnen van de kinderen.

7.2

cprefine.gen

De tweede module is minder intressant, maar wordt wel gebruikt om de twee modules die wel intressant zijn te ”verbinden”.Tdidt roep dus Pack.refine() op,voor het verfijnen van een pack, zodat we een verfijnt pack terugkrijgen. Deze gaat een iterator maken over het pack en daarop refine pack in de klasse refinable cpack in deze module. Daar wordt dan een refiner gemaakt van de klasse rmode refop die dan wordt verfijnt, dit vinden we terug in de derde module. terugkrijgen.

35

7.3

flocks.gen

De intressante methodes van deze module vinden we terug in de klasse rmode refop. Dit zijn degenen die voor de eigenlijke verfijning gaan zorgen. En verrassend genoeg hebben we dan ook om te beginnen een methode refine() die wordt toegepast op een pack. Van dit pack nemen we de rmodes. We kijken dan welke rmodes we kunnen gebruiken, dat wil zeggen degenen waarvoor de teller N, nog niet op 0 staat. Het predikaat rmode bevat een volgnummer en de rmode; de query. We gaan dan deze lijst van rmodes verfijnen door recursie op de lijst. We hebben de clause tot nu toe in de knoop,de query en een lijst met variabelen. Er wordt aan de hand hiervan een lijst van instantiaties van de vorm f (Clause, N ewQuery, N ewInstvars) gemaakt, met newquery de rmode waarbij ” + ” gebonden is aan een variabele. De lijst van instantiaties van de rmode die we zo krijgen gaan we weer verder verfijnen door recursie op de lijst. We gaan elke instantiatie van elke rmode nog verder verfijnen door de constanten te instanti¨eren. We krijgen zo weer een lijst van instantiaties die we wederom recursief gaan verfijnen. Het is nu dat de lookahead wordt toegepast, op elke instantiatie van constanten van elke instantiatie van elke rmode. Zo krijgen we een verfijnd pack van alle mogelijke testen in een knoop die we kunnen gebruiken om te splitsen en waaruit we de beste zullen moeten zoeken. In elke settingsfile van een dataset zullen we de maximale lookahead terugvinden, deze wordt hier opgevraagd. Dan gaan we weer recursief alle mogelijke lookaheads afgaan voor elke instantiatie van constanten en dit door deze lookahead als rmode te beschouwen en wederom de opeenvolging van recursies te doorlopen voor elke lookahead

We over lopen de verfijning van een knoop, deze gebeurt in volgende stappen: UIT DE CODE: 1. Een nieuwe querie/conjunctie wordt gekozen aan de hand van de heuristiek 2. De querie wordt ge¨ınstantieerd volgens de modes van variabelen 3. Lookahead wordt toegepast 4. Constanten worden gegenereeerd MAAR 1. Pack van de knoop gaat worden verfijnd 2. Alle rmodes die mogelijk zijn worden gebruikt voor uitbreiding van de Clause van de knoop. 3.Voor elke rmode gaan we variabelen instanti¨eren 4.Voor elke mogelijke instantiatie gaan we de constanten genereren. 5.Lookahead wordt toegepast. 6. Uit het verfijnd pack wordt een nieuwe querie/conjunctie wordt gekozen aan de hand van de heuristiek.

36

Hoofdstuk 8

Uitbreidingen van de code 8.1

tdidt.gen

Ik heb de 2 algoritmes die werden voorgesteld ge¨ımplementeerd. Deze houden in dat voor een knoop de beste test wordt gekozen zoals normaal. Vervolgens gaan we het linkerkind bekijken en daar de beste test voor zoeken volgens de beschreven algoritmes. We hebben dus een test A in de ouder knoop.Deze knoop heeft een query Q. Voor het linkerkind voegen we A toe aan de query. Dus in het linkerkind hebben we de query Q,A. We zoeken daar nu dus een beste test B ..... Indien deze beter is dan test A alleen vervangen we in de ouderknoop test A door de nieuwe geconjugeerde test. Dit testen we door de geconjugeerde test A,B te testen op de voorbeelden set van de ouderknoop.... NOG VERDER AFMAKEN–¿ZIE KLADBLOK

37

8.2

flocks.gen

Een eerste aanpassing is een poging tot het invoeren van een uitgebreidere lookahead in Tilde. Hiertoe gaan we voor elke rmode die wordt verfijnt met instantiaties en constanten lookahead uitvoeren. Maar in plaats van gebruik te maken van de lookahead predikaten in de achtergrondkennis, gebruiken we alle rmodes voor mogelijke lookahead. NOG VERDER AFMAKEN–¿ZIE KLADBLOK

38

Hoofdstuk 9

Datasets 9.1

Mutagenesis

Mutagenesis is een veelgebruikte ILP benchmark-dataset. Het probleem hier bestaat er in om de mutuganiciteit te bepalen van aromatische en heteroaromatische componenten.De data beschrijft moleculen die in 2 klassen vallen, mutageen en niet − mutageen, waarbij informatie over de atomen en hun bindingen gegeven is. De originele dataset uit de paper van Debnath et al. bevat 2 subsets: 188 componenten bruikbaar voor linaire regressie en 42 componenten die daar niet geschikt voor waren.In totaal 230 voorbeelden die de Muta dataset vormen. De subset van 188 staat bekend als de ”regression friendly”versie van de Muta dataset. Er werden 4 levels van achtergrondkennis voorgesteld door [Srinivasan et al,1995]. Background 1: Atomen van de molecule zijn gegeven en de bindingen er tussen. Voor elke binding is het type gegeven alsook het element en het type van elk atoom. Background 2: Achtergrond 1 uitgebreid met tests op continue attributen zijn toegelaten Background 3: 2 extra attributen zijn toegevoegd die de molecule in zijn geheel beschrijven Background 4: Expliciete informatie over complexe structuren is toegevoegd. We zien dus dat 1 ⊂ 2 ⊂ 3 ⊂ 4

9.2

Diterpenes

Het doel is het type van diterpenoide samengestelde skeletten identificeren gegeven hun 13 CNMR-spectrum. Het probleem houdt het direct vergelijken van sets in. Normaal wordt dit manueel gedaan door menselijke experts. De data set bevat 1503 voorbeelden met een gekende structuur opgeslagen in 3 relaties: atomen die aangeven uit welke atoomtype de samenstelling bestaat,bindingen die weergeven welke en hoe atomen zijn gebonden en de gemeten spectra. Voor elk van de 20 carbon-atomen in een skelet bevat de info over de spectra de frequentie, atoomnummers en multipliciteit. Er zijn 23 klassen waarin de samenstellingen kunnen vallen.

39

9.3

Musk

De Musk dataset werd door Dietterich bestudeerd in verband met multi instance problemen.We gebruiken versie 1 van de data, met 47 musk moleculen en 45 niet-musk moleculen. Elk voorbeeld is een molecule en beschreven door een set tupels.Elke tupel heeft 166 features.De moleculen moeten worden geklassificieerd in musk of niet-musk. molecule heeft meerdere samenstellingen Het probleem bestaat er in welke samenstellingen van de muskmolecule de musk-activiteit veroorzaken. Een molecule is musk als 1 van zijn samenstellingen musk is. We weten echter enkel dat een molecule al dan niet musk is en niet welke van zijn samenstellingen daar voor zorgt. Dit is dus een typisch MIP.

Figuur 9.1: Enkele musk moleculen

9.4

The predictive toxicology evaluation challenge

Het voorkomen van kankers die door de omgeving worden veroorzaakt is van groot belang en noodzaakt begrip van de mechanismen van chemische carcinogenesis. Vanuit het onderzoek door het NIEHS is een grote database ontstaan van samenstellingen geklassificeerd als al dan niet carcinogeen. Het PTE-project van NIEHS geeft de mogelijkheid tot vergelijken van carcinogeniciteit voorspellingen op eerder ongeteste chemicali¨en. Dit leidde tot de PTEuitdagingen. Deze maken gebruik van de NTP database die bestaat uit 330 chemicali¨en waarvan 182 carcinogeen en 148 niet-carcinogeen.

9.5

Bongard

De Bongard dataset [Bongard,1970] bevat de beschrijvingen van artifici¨ele afbeeldingen. De taak is het ontdekken van patronen in de afbeeldingen. Elk beeld bestaat uit meerdere figuren die in elkaar kunnen vervat zijn.

40

Hoofdstuk 10

Tests We hebben nu een aantal algoritmes en datasets. Logische volgend stap is het testen van de algoritmes op de datasets. We gaan voor elke dataset volgende tests draaien: • Een test met het originele Tilde algoritme zonder meer. • Tilde met de originele lookahead aan de hand van de gegeven lookahead()-predikaten, tot op diepte 2 indien haalbaar gegeven de rekenkracht van de gebruikte PC. • Tilde uitgebreid met het eigen algoritme 2 • Tilde uitgebreid met het eigen algoritme 3 • Tilde met de nieuwe lookahead aan de hand van de rmode()-predikaten, eveneens tot op diepte 2 indien haalbaar gegeven de rekenkracht van de gebruikte PC. • Een combinatie van algoritme 2 met de nieuwe lookahead • Een combinatie van algoritme 3 met de nieuwe lookahead Volgens de aanbevelingen van Bouckaert[2003] draaien we voor elke test 10 keer een 10-vouwdige kruisvalidatie. We nemen van deze 10 tests dan het gemiddelde en noteren dan voor elk algoritme de snelheid, juistheid en grootte van de gebouwde boom. De grootte meten we zowel aan de hand van het aantal nodes als aan de hand van het aantal literals. De resultaten die we alzo bekomen gaan we dan vergelijken met elkaar en met resultaten van andere algoritmes. Voor de MIP-dataset vergelijken we uiteraard specifiek met andere algoritmes die voor MIP ontwikkeld zijn, om een idee te krijgen of de eventuele geconjugeerde tests die worden gemaakt door algoritme 2 en 3 de boom verbeteren voor deze problemen en zo een indicatie geven dat de geconjugeerde tests de juiste zouden zijn om Tilde beter met MIP te laten werken en zo de problemen die we daaromtrent hebben beschreven zouden kunnen counteren.

41

Hoofdstuk 11

Resultaten en conclusies 11.1

Accuracy

Figuur 11.1: Voorlopige jpeg van de resultaten

42

11.2

Snelheid

Figuur 11.2: Voorlopige jpeg van de resultaten

43

11.3

Grootte van de boom

Figuur 11.3: Voorlopige jpeg van de resultaten

44

Figuur 11.4: Voorlopige jpeg van de resultaten

45

Hoofdstuk 12

Besluit

46

Dank- en Nawoord Normaal heb ik altijd wel iets te zeggen, leuke zinsnedes klaar of flauwe grapjes om er tussen te houden, maar hier ga ik proberen het kort te houden en ”to the point ”vooral. Het is een lang jaar geweest, vooral met deze thesis. Veel vallen, veel opstaan, veel blauwe plekken. Maar we zijn er geraakt.(Uit)eindelijk. Alleen had ik het nooit klaar gekregen. Zonder de steun, hulp, motivatie en soms boosheid van anderen stond ik nu waarschijnlijk nog waar ik in september stond. De eerste persoon die ik zou willen bedanken, alleen al omwille van het vele geduld en het feit dat ik ook al liet ik soms een tijd niets horen, ze toch nooit heeft opgegeven mij zover te krijgen, is mijn begeleidster, Celin Vens. Ook voor de soms essenti¨ele hulp ben ik haar dankbaar, als er echt iemand is zonder wie het niet gelukt zou zijn, moet men niet verder zoeken. Verder zijn er uiteraard mijn ouders die me al die jaren aan de Univ hebben gesteund, samen met Tine die al evenveel achter me stond. Dan is er mijn Liesje, die altijd mijn humeur als het weer is niet lukte tolereerde, da vele nachtelijke uren mee opbleef of er gewoon was als het nodig was, zonder er iets voor terug te vragen Ook zijn er de vrienden die door te plagen dat de thesis nooit zou afgeraken, extra motivatie om het toch te doen gaven. Claes,Jochen en Tom: cheers en laat de Westvleteren maar komen!! Als laatste, maar daarom niet minder belangrijk, zijn er al de proffen die door de jaren heen hun best hebben gedaan om mij iets bij te brengen.

Figuur 12.1: Een zoekboom, anders.

47

Referenties Hoofdstuk 1 [Akobir Shahidi BaseGroup Labs.] Decision trees: general principles of operation. http://basegroup.biz/trees/description.en.htm [D.Page and S. Ray] Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction (2003) [J. Ross Quinlan] C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993. [S.Murthy] Automatic construction of decision trees from data: A Multi-disciplinary survey. 1997. [W. Buntine] A theory of classification rules. 1992. [D. Mitchie et.alMachine Learning, Neural and Statistical Classification.1994. [K. Shennon] Works On The Information Theory And Cybernetics. 1963. [S.A. Ivazyan, V.S. Mkhitaryan] Applied Statistics And Basics Of Econometric Theory. 1998. http://www.run.montefiore.ulg.ac.be/ francois/software/jaDTi/example/files/zooDT.png http://www.kurzweilai.net/articles/images/aimchapter407.jpg [Saher Esmeir, Shaul Markovitch ]Lookahead-based Algorithms for Anytime Induction of Decision Trees,2004 [Wikipedia] : http : //en.wikipedia.org/wiki/Ginic oef f icient

Hoofdstuk 2 Hoofdstuk 3 [H.Blockeel , L.Deraedt] Top-Down inductie van logische beslisbomen.,1997 [Cholwich Nattee, Sukree Sinthupinyo, Masayuki Numao,Takashi Okada],Inductive Logic Programming for Structure-Activity Relationship Studies on Large Scale Data [H. Blockeel] Cursus Machine Learning 2003-2004, Hoofdstuk 13:ILP

Hoofdstuk 4 [Thomas G. Dietterich,Richard H.Lathrop and Tomas Lozano-Perez] Solving the Multiple-Instance Problem with Axis-Parallel Rectangles (1997) [H.Blockeel, D Page, A. Srinivasan] Multi-instance Tree Learning

Hoofdstuk 6

48

Hoofdstuk 8 [Daan Fierens, Jan Ramon, Hendrik Blockeel, Maurice Bruynooghe] A Comparison of Approaches for Learning Probability Trees, 2005 Predicting Mutagenicity: http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/mutagenesis.html [A. Srinivasan,S.H. Muggleton,R.D. King, M.J.E Sternberg] The Predictive Toxicology Evaluation Challenge [Celine Vens, Anneleen Van Assche, Hendrik Blockeel, and Saso Dzeroski]First Order Random Forests with Complex Aggregates [Sasi O Dzi Eroski, S.Schulze-Kreme, K.R. Heidtke,K.Siems,D. Wettscherech en H. Blockeel] Diterpene structure elucidation from 13 C − N M R spectra with inductive logic programming. [Arno Jan Knobbe] Proefschrift over Multi-Relational Data Mining,2004 The Predictive Toxicology Evaluation Challenge : http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/PTE/

Hoofdstuk 9

49