Verslag FWO postdoctoraal mandaat 2006

1. Inleiding

Kort samengevat is de doelstelling van dit project het bruikbaarder maken van technieken uit het domein van Inductief Logisch Programmeren in de praktijk, vooral voor toepassingen in bio-medische domeinen. Het project omvat twee luiken. Het eerste vertrekt vanuit de data mining en meer bepaald het domein van Inductief Logisch Programmeren. Het is de bedoeling betere data-mining technieken te ontwikkelen die de moeilijkheden uit bio-informatica applicaties beter aankunnen. Het tweede luik vertrekt vanuit de toepassingen zelf, van waarin dan geprobeerd wordt om met behulp van data mining technieken bij te dragen tot die applicatie-domeinen zelf.

2. Data mining onderzoek

2.1. Efficiënte methoden voor 'gemakkelijke' klassen grafen

In een studieverblijf in Bonn (Tamas Horvath, Fraunhofer Institüt, November 2005) werd gewerkt rond 'gemakkelijke' klassen van grafen voor data mining. De huidige technieken in het gebied van Inductief Logisch programmeren en Graph Mining veronderstellen meestal data voorgesteld met (algemene) grafen, waardoor de computationele kost zowel in theorie (worst case) als in de praktijk exponentieel stijgt met de grootte van de grafen. In de praktijk echter, kan men vaststellen dat veel data kan voorgesteld worden met gemakkelijker klassen grafen. We onderzochten de NCI-databank (een grote, populaire databank met 250251 molecules) en merkten op [4, 5, 6] dat 94.5% van de molecules outer- planair zijn (d.w.z. men kan ze in een vlak tekenen zonder snijdende bogen en zodat alle knopen de buitenzijde raken). We definiëren een nieuwe subgraaf matching operator gemotiveerd op scheikundige toepassingen (ringen en lineaire fragmenten gedragen zich verschillend) en tonen aan dat we alle frequente outerplanaire patronen kunnen vinden in incrementeel polynomiale tijd. Naast de resultaten [4] werd ook een prototype implementatie voorgesteld op de prestigieuze ACM SIGKDD conferentie [11].

In een verdere uitbreiding [8] merken we op dat gelijkaardige assymptotische eigenschappen kunnen bewezen worden voor subgraaf homomorphisme en dat men ook alle universeel gequantificeerde associatieregels met confidence groter dan een gegeven threshold in polynoomtijd kan afleiden uit een gevonden verzameling frequente outerplanaire patronen.

Er is gepland om in verder onderzoek deze resultaten nog verder uit te breiden zodat ook alle niet-outerplanaire frequente subgrafen van de NCI-databank efficient kunnen gevonden worden en de methode ook toepasbaar wordt op andere biologisch relevante structuren (bv. proteines). In een recent bezoek van T. Horvath aan Leuven werd bv. gewerkt aan een benadering waarbij we grafen met beperkte treewidth beschouwen (onder verschillende matching operatoren zoals subgraaf iso-, homo- en homeo-morphisme).

2.2. Afstandsgebaseerd leren

Er werd samengewerkt met Luc De Raedt rond het uitbreiden van eerder werk naar een algemeen framework voor afstandsfunkties op ruimten waarin een partiële orde is gedefinieerd, Op strings, atomen, bomen, grafen, . . . bijvoorbeeld kan men een "is meer algemeen dan" (of "is subgrafe van") relatie definieren waaruit dan op natuurlijke wijze een afstandsfunctie ontstaat door te meten hoe sterk twee elementen verschillen van hun minst algemene veralgemening.

Als een verdere toepassing op het werk besproken in Sectie 2.1 werd de laatste maanden ook gewerkt aan een afstandmaat voor outerplanaire grafen. De voorgestelde afstand is een specialisatie van een eerder (in doctoraatsthesis) voorgestelde algemene afstandsfunctie. Echter, door de gunstige complexiteitseigenschappen zal deze afstandsfunctie veel bruikbaarder zijn in de praktijk.

3. Bio-medisch onderzoek

3.1. Intensieve geneeskunde

In 2004 werd een samenwerkingsproject gestart met de afdeling intensieve geneeskunde van het UZ Leuven. In een eerste faze werd een studie gedaan op een beperkte databank met dagelijkse gegevens van patiënten van voorbije jaren. De resultaten hiervan [7, 9] zijn veelbelovend: we voorspelden verschillende factoren (overleven van de patient, nierfalen, SIRS, SIRS-shock, . . . ), met een aanvaardbaar resultaat (soms even goed en soms iets langer van tevoren als artsen) ondanks het feit dat onze systemen over een beperktere hoeveelheid data beschikten als de experts. Ondertussen is de tweede faze van het project gestart met de installatie van een PDMS-systeem in het ziekenhuis. We beschikken nu over meer informatie (monitoring van parameters elke 3 minuten en een meer systematische opslag van de patient-gegevens) wat hopelijk de kwaliteit van onze resultaten kan verbeteren. In eerste instantie wordt nu gepoogd om een maximum aan informatie te halen uit de aanwezige hoge resultie tijdsreeksen [3].

3.2. HIV onderzoek

In een samenwerkingsproject met o.a. het Rega-Instituut (KULeuven) en Tulio Deoliveira (Oxford, UK) wordt onderzoek gedaan naar HIV. Een probleem dat regelmatig opduikt is dat sommige methoden (bv. phylogenetische bomen) proberen de evolutie van een populatie te verklaren terwijl andere (bv. onze en andere data mining experimenten in het verleden) associaties tussen mu- taties (bv. bij resistentie-ontwikkeling) ontdekken, maar geen enkele methode een theorie genereert die beide soorten fenomenen tegelijk verklaart. Daarom wordt recentelijk gewerkt rond een systeem dat m.b.v. een EM-algoritme een Bayesiaans model bouwt dat tegelijk de effekten van externe evolutionaire druk (medicatie) en evolutie kan omvatten. Dit werk is ook gedeeltelijk geïnspireerd door [10] (zie Sectie 4).

4. Andere activiteiten en resultaten

Naast strikt project-gerelateerd onderzoek besteed ik tijd aan de dagelijkse begeleiding van en het samenwerken met een aantal doctoraatsstudenten binnen de onderzoeksgroep.

Er werd samengewerkt met Celine Vens rond het verfijnen van queries met aggregates in relationeel leren. Aggregaten zijn belangrijk in domeinen met numerieke informatie, zoals deze beschreven in Sectie 3.1. [?] beschrijft een methode om efficient geschikte queries te vinden in een (grote) zoekruimte door gebruik te maken van de onderlinge verbanden tussen verschillende queries die aggregaatscondities bevatten.
Er werd samengewerkt met Daan Fierens en Tom Croonenborghs rond het leren van de structuur van Logische Bayesiaanse Netwerken [10] en de toepassing daarvan in Relational Reinforcement Learning [1]. In de toekomst verwachten we dat LBN's in meerdere van onze bio-medische applicaties nuttig zullen zijn omwille van hun mogelijkheid om zowel probabilistische als relationele informatie voor te stellen.
Fabian Guiza is een doctoraatsstudent die werkt rond de applicatie in intensieve geneeskunde (Sectie 3.1).

Tenslotte waren er in 2006 kleinere samenwerkingen met Kurt Driessens ivm. het online reviseren van geleerde beslissingsbomen [2], Anneleen Van Assche [12] en Celine Vens [13].

5. Conclusie

In het derde jaar van het postdoctoraal mandaat werden meerdere aspecten van het project verder uitgewerkt. Er werden artikels gepubliceerd rond data mining specifieke, applicatie-specifieke en gemengde onderwerpen.

Globaal kunnen we stellen dat gedurende de voorbije drie jaar een nuttige bijdrage is geleverd aan alle punten genoemd in het eerste luik (data mining) van het project. Wat het tweede luik (toepassingen) betreft werden een aan- tal samenwerkingsverbanden opgezet met bio-medische onderzoeksgroepen die vorderingen hebben gemaakt door deze samenwerking. Recentelijk werden ook de eerste artikels over toepassingen gepubliceerd (Sectie 3.1).

References

[1] Tom Croonenborghs, Jan Ramon, Hendrik Blockeel, and Maurice Bruynooghe. Model-Assisted Approaches for Relational Reinforcement Learning: Some Challenges for the SRL Community. In Proceedings of the ICML-2006 Workshop on Open Problems in Statistical Relational Learning, pages 1-xx, Pittsburgh, PA, 2006.

[2] K. Driessens, J. Ramon, and T. Croonenborghs. Transfer learning for re- inforcement learning through goal and policy parametrization. In ICML Workshop on Structural Knowledge Transfer for Machine Learning (Online Proceedings), 2006.

[3] F. Guiza, J. Ramon, and H. Blockeel. Gaussian processes for predic- tion in intensive care. In Neil D. Lawrence, Anton Schwaighofer, and Joaquin Quinonero, editors, Proceedings of the Gaussian Processes in Prac- tice Workshop, Bletchley Park, U.K., June 2006.

[4] Tamas Horvath, Jan Ramon, and Stefan Wrobel. Frequent subgraph min- ing in outerplanar graphs. In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 197-206, Philadelphia, PA, August 2006.

[5] Tamas Horvath, Jan Ramon, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. In Workshop on Mining and Learning with Graphs (MLG 2006), Berlin, Germany, September 2006. Accepted.

[6] Tamas Horvath, Jan Ramon, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. In Proceedings of the Eighteenth Belgium- Netherlands Conference on Artificial Intelligence (BNAIC'06), Namur, Bel- gium, October 2006. To appear.

[7] J. Ramon, F. Guiza, D. Fierens, G. Meyfroidt, H. Blockeel, M. Bruynooghe, and G. Van Den Berghe. Mining data from intensive care patients. Ad- vanced Engineering Informatics, 2006. To appear.

[8] Jan Ramon. Efficient mining of frequent outerplanar graphs. In Proceedings of the 16th International Conference on Inductive Logic Programming - short papers, pages 170-172, 2006.

[9] Jan Ramon. Predicting evolution of critically ill patients. In Li Toa, Charles Perng, Haixun Wang, and Carlotta Domeniconi, editors, Proceedings of the KDD-workshop on Theory and Practice of Temporal Data Mining, pages 1-3, Philadelphia, PA, USA, 2006.

[10] Jan Ramon, Tom Croonenborghs, Daan Fierens, Hendrik Blockeel, and Maurice Bruynooghe. Generalizing ordering-search for learning directed probabilistic logical models. In Proceedings of the 16th International Conference on Inductive Logic Programming - short papers, pages 173-175, 2006.

[11] Jan Ramon, Tamas Horvath, Leander Schietgat, and Stefan Wrobel. FOG: Finding outerplanar graphs. In Gabor Melli, editor, Demo Session at SIGKDD 2006, Philadelphia, PA, August 2006.

[12] Anneleen Van Assche, Jan Ramon, and Hendrik Blockeel. Learning in- terpretable models from an ensemble in ILP. In Proceedings of the 16th International Conference on Inductive Logic Programming - short papers, pages 210-212, 2006.

[13] Celine Vens, Jan Ramon, and Hendrik Blockeel. Re-Mauve, a relational model tree learner. In Proceedings of the 16th International Conference on Inductive Logic Programming - short papers, pages 216-218, 2006