Uiteenzetting van het voorgestelde project in het Nederlands (max. 2 blz.).
Name applicant: Kristian Kersting Project Title: Statistisch Relationeel leren Statistisch Relationeel leren (SRL) is een nieuw onderzoeksgebied binnen machine learning dat leren en mining in relationele domeinen bestudeert, waar er missende observaties kunnen zijn, gedeeltelijk waargenomen observaties, en/of onduidelijke observaties. Deze integratie van relationele representaties gebaseerd op eerste orde logica, probabilistisch en statistisch redeneren, en machine learning wordt tegenwoordig steeds belangrijker: de hoeveelheid heterogene data die in het bedrijfsleven en de wetenschap verzameld wordt groeit explosief. Voorbeelden van toepassingsgebieden zijn bioinformatica, transportsystemen, communicatienetwerken, sociale netwerken, om enkele te noemen. Deze toepassingen bieden onzekere informatie over vari¨erende aantallen objecten en verbanden tussen deze objecten, de zogenaamde relationele domeinen. Technieken voor beschrijvende en voorspellende machine learning, voor het modelleren van dynamische omgevingen, en voor het nemen van complexe beslissingen binnen deze werelden, met name SRL technieken, zijn noodzakelijk en hebben daadwerkelijk het potentieel om de basis te vormen voor de nieuwe generatie kunstmatige intelligentie (KI) en machine learning (ML). Het belang en de populariteit van SRL blijkt uit een toenemend aantal aan SRL gerelateerde workshops (SRL02, SRL03, SRL04, MI-19, RRL04, RRL05, Dagstuhl seminar 05051, Dagstuhl seminar 0716), voordrachten op uitnodiging (IJCAI-01, ICML03, KDD03, ECML/PKDD04, BeNeLearn05, ILP04, ILP05, ECML/PKDD05), introducerende voordrachten op conferenties (ICML04, AAAI05, IDA05, ECML/PKDD05, IJCAI05), en internationale projecten (DARPA project over ‘Transfer Learning’; EU projects APrIL I and II “Applications of Probabilistic Inductive Logic Programming” gecoordineerd door Freiburg). De beginfase van SRL onderzoek (zie [3] voor een overzicht) werd gekarakteriseerd door de exploratie van verschillende manieren om statistische en relationele methoden te combineren. Meestal werden de logische concepten van objecten en hun relaties gecombineerd met een statistisch model, bijvoorbeeld een Bayesiaans netwerk of een Markov model. Vervolgens werden methoden ontwikkeld om deze SRL modellen uit data af te leiden. Beide fasen lijken nu langzaam voorbij te zijn: door toepassingen is er nu een goed practisch begrip van de verschillende SRL aanpakken. In dit project zal ik mij daarom concentreren op meer fundamentele vraagstukken. In het bijzonder stel ik voor om onderzoek te doen naar (WP1) afbeeldingen van SRL methoden op elkaar (WP2) complexiteit van steekproeven (WP3) equivalentieklassen van SRL modellen (WP4) de afweging tussen kansrekening en logica binnen SRL, en (WP5) effici¨ent redeneren binnen SRL en leren van SRL. WP1 Afbeeldingen: Er is op dit moment nog geen duidelijk en algemeen geaccepteerd begrip van de relatieve voordelen en beperkingen van SRL technieken. Dit project zal afbeeldingen tussen de verschillende SRL modellen onderzoeken. Afbeeldingen maken het op een natuurlijke wijze mogelijk om technieken tussen de verschillende SRL frameworks over te dragen. Alhoewel enkele afbeeldingen zijn voorgesteld, bijvoorbeeld [8, 10], is er nog geen algemeen framework. Het project zal een hierarchie tussen SRL aanpakken ontwikkelen die rekening houdt met de complexiteiten van de afbeeldingen en het type vraagstellingen dat een framework ondersteunt. Zulke complexiteitshierarchi¨en vormen het hart van de theoretische informatica. WP2 Steekproefcomplexiteit: De afname in rekentijd van statistisch relationeel leren door relationele abstractie is tot nu toe alleen empirisch bewezen. Dit project zal dit vraagstuk op een meer principi¨ele wijze benaderen en de steekproefcomplexiteiten van SRL modellen ontwikkelen: steekproefcomplexiteiten geven aan hoeveel trainingsvoorbeelden noodzakelijk zijn om resultaten van hoge kwaliteit te verkrijgen. Verder kunnen schattingen van de kwaliteit van een model, verkregen door steekproefcomplexiteit, worden gebruikt om nutteloze modellen snel te detecteren. WP3 Equivalentie Klassen: Vaak specificeren syntactisch verschillende SRL modellen dezelfde kansverdeling. Moderne SRL technieken voor het selecteren van modellen of het berekenen van gemiddelden van modellen houden geen rekening met equivalentieklassen van SRL modellen, met name klassen van SRL modellen die behoren bij een unieke kansverdeling. Hierdoor gebruiken deze algoritmen rekentijd die vermeden had kunnen worden als niet telkens dezelfde verdeling berekend zou worden. Het project zal notaties en equivalenties binnen SRL ontwikkelen. WP4 De Trade-Off tussen kansrekening en logica: Het eerste SRL onderzoek concentreerde vooral op zeer expressieve aanpakken. Deze expressiviteit veroorzaakt hoge computationele kosten voor het berekenen van modellen in deze talen. De juiste afweging tussen simpele/complexe statistische modelle en simpele/complexe logische talen is onbekend. Deze situatie lijkt op de bias-variantie tradeoff in computationele leertheorie: een model met veel graden van vrijheid kan slechte generalisatie-eigenschappen hebben voor voorbeelden die het model nog niet gezien heeft. Het combineren van statistische modellen met relationele representaties kan het aantal vrijheidsgraden nog verder verhogen. Ik zal de combinaties van statische en logische modellen onderzoeken op verschillende niveau’s van expressiviteit. Eerste resultaten [6] met het simpele Naıve Bayes model zijn hoopgevend. WP5 Efficient Redeneren: SRL aanpakken evalueren meestal een groot aantal queries op een verzameling van trainingsvoorbeelden. Deze queries lijken vaak zeer sterk op elkaar, zodat het onafhankelijk uitvoeren ervan tot overbodige berekeningen zou kunnen leiden. E´en veelbelovende aanpak is om technieken van de inductieve logische programmering toe te passen; de DTAI groep aan de K.U. Leuven is gekend om haar werk op dit gebied. Bijvoorbeeld, het opslaan in tabellen van queries [4] kan de snelheid van afleidingen significant verhogen. Het idee achter het opslaan in tabellen is als volgt. Tijdens de uitvoering van een query wordt elk doel S geregistreerd in een tabel; unieke antwoorden worden aan de tabel toegevoegd op het moment dat ze afgeleid zijn. Het gebruik van
tabellen voor het selecteren van modellen, in het bijzonder: het opslaan van informatie die gedeeld wordt tussen verschillende modellen is binnen SRL nog niet bestudeerd. Een onderdeel van deze studie vormen de query packs [2], die sterk gelijkende queries structureren, en transformaties van SRL modellen die verdelingen behouden. Het is aangetoond dat soortgelijke transformaties in het puur logische domein tot een significante versnelling kunnen leiden [9]. Als alternatief zal ik de relationele variant van AD-trees onderzoeken [7]. Een AD-tree is een effici¨ente datastructuur waarin informatie tijdelijk opgeslagen kan worden tijdens het leren van statische modellen. In het algemeen zijn interessante SRL modellen erg groot, zodat het veel tijd kost exacte afleidingen te verrichten; soms zelfs is de afleiding niet berekenbaar. Daarom zal het project ook kijken naar benaderende technieken. De relationele representatie van het domein zelf kan al tot nieuwe en betere benaderende afleidingsalgoritmen leiden. Ik zal onderzoek doen naar relationele abstractie, bijvoorbeeld door middel van logische beslissingsbomen [1], en ‘particle filters’ [5]. ‘Particle filters’ zijn gebaseerd op een Monte Carlo simulatie waarin de verdeling benaderd wordt door een verzameling deeltjes met bijbehorende gewichten. Het aantal deeltjes heeft directe invloed op de rekentijd. Relationele abstractie zal het aantal deeltjes verminderen aangezien deeltjes gedeeld worden door de toestanden die behoren bij dezelfde abstracte toestand. Het is mijn overtuiging dat het aanpakken van deze problemen uiteindelijk zal leiden tot een algemene theorie voor SRL. References [1] H. Blockeel and L. De Raedt. Top-down Induction of First-order Logical Decision Trees. Artificial Intelligence, 101(1–2):285–297, 1998. [2] H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H. Vandecasteele. Improving the Efficiency of Inductive Logic Programming Through the Use of Query Pack. Journal of Artificial Intelligence Research (JAIR), 16:135–166, 2002. [3] L. De Raedt and K. Kersting. Probabilistic Logic Learning. In ACM-SIGKDD Explorations, special issue on Multi-Relational Data Mining, S. Dzeroski and L. De Raedt, editors, Vol. 5(1), pp. 31-48, July 2003. [4] B. Demoen and K. F. Sagonas. CAT: The Copying Approach to Tabling. Journal of Functional and Logic Programming, 1999. Special Issue 2. [5] A. Doucet, N. de Freitas, and N. Gordon, editors. Sequential Monte Carlo in Practice. Springer, 2001. [6] N. Landwehr, K. Kersting, and L. De Raedt. nFOIL: Integrating Naıve Bayes and Foil. In M. Veloso and S. Kambhampati, editors, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), pages 795–800, Pittsburgh, Pennsylvania, USA, July 9–13 2005. AAAI. [7] A. W. Moore and M. S. Lee. Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets. Journal of Artificial Intelligence Research (JAIR), 8:67–91, 1998. [8] M. Richardson and P. Domingos. Markov Logic Networks. Machine Learning, 2006. (To appear). [9] V. Santos Costa, A. Srinivasan, R. Camacho, H. Blockeel, B. Demoen, G. Janssens, J. Struyf, H. Vandecasteele, and W. Van Laer. Query Transformations for Improving the Efficiency of ILP Systems. Journal of Machine Learning Research (JMLR), 4:465–491, 2003. [10] J. Vennekens, S. Verbaeten, and M. Bruynooghe. Logic Programs with Annotated Disjunctions. In B. Demoen and V. Lifschitz, editors, Proceedings of 20th International Conference on Logic Programming (ICLP-04), pages 431–445, Saint-Malo, France, September 6-10 2004.
Situeer dit onderzoek in het geheel van het onderzoek van uw onderzoekseenheid en geef de nationale en internationale co Geef samenwerkingsverbanden en de grotere projecten, programma's en internationale netwerken waarbinnen uw onderzo situeren is.
Het onderzoek rond statistical relational learning is belangrijk voor de DTAI groep. Het wordt o.a. onderzocht wordt in het kader van een FWO Project en is ook een thema binnen de GOA van de DTAI groep en het Europese APRIL II project, dat door Freiburg gecoordineerd wordt, en waarvan de andere partners zijn: Imperial College, Universita di Firenze, INRIA Rocquencourt en de Universiteit van Helsinki. Er bestaan ook uitstekende contacten rond dit onderwerp met de belangrijkste amerikaanse onderzoekers in dit domein. In een internationale context gezien, is het statistical relational learning een van de belangrijkste actuele onderwerpen binnen de kunstmatige intelligentie.
Uw wetenschappelijke publicaties met opgave van titel, auteurs en bibliografische gegevens ingedeeld als volgt : - boeken waarvan u auteur of co-auteur bent - publicaties in tijdschriften of boeken met leescomité. Zo deze tijdschriften een S.C.I. impactfactor hebben, gelieve deze ten indicatieve titel op te geven - publicaties in tijdschriften of boeken zonder leescomité - werken waarvan u wetenschappelijk uitgever bent - abstracts van lezingen - recensies - bijdragen in encyclopedieën, woordenboeken en vulgariserende publicaties - interne verslagen Indien nog niet werkelijk gepubliceerd : vermeld of het werk ter perse is, aangeboden ter publicatie of slechts in voorberei
(Deze publicaties dienen het FWO NIET toegestuurd te worden.)
Publicaties in tijdschriften of boeken met lescomite Tijdschriften: . . .
K. Kersting, L. De Raedt, T. Raiko. Logical Hidden Markov Models. Journal of Artificial Intelligence Research. 2006. Accepted. L. De Raedt, K. Kersting. Probabilistic Logic Learning. In SIGKDD Explorations - Newletter of the ACM Special Interest Group on Knowledge Discover and Data Mining, Special Issue on Multi-Relational Data Mining, S. Dzeroski and L. De Raedt, editors, Vol. 5(1), pp. 31-48, July 2003. S. Ganzert, J. Guttmann, K. Kersting, R. Kuhlen, C. Putensen, M. Sydow, S. Kramer. Analysis of Respiratory Pressure-Volume Curves in Intensive Care Medicine Using Inductive Machine Learning. Artificial Intelligence in Medicine, special issue on Medical Data Mining, K. Cios, J. Berman, W. Moore, editors, 26(1-2), pp. 69-86, Sept. 2002.
Proceedings van conferenties of workshops met programma comite en strenge selectie . . . . . . . . . . . . .
R. Triebel. K. Kersting. W. Burgard. Robust 3D Scan Point Classification using Associative Markov Networks.To appear in N. Papanikolopoulos, editor, IEEE International Conference on Robotics and Automation (ICRA-06), Walt Disney World Resort in Orlando, Florida, USA, May15-19, 2006. K. Kersting, T. Raiko. ’Say EM’ for Selecting Probabilistic Models for Logical Sequences. In F. Bacchus and T. Jaakkola, editors, Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI-05), Edinburgh, Scotland, July 26-29, 2005. N. Landwehr, K. Kersting, L. De Raedt. nFOIL: Integrating Naive Bayes and FOIL. In M. Veloso and S. Kambhampati, editors, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), pages 795-800, Pittsburgh, Pennsylvania, USA, July 9-13, 2005. L. De Raedt, K. Kersting, S. Torge. Towards Learning Stochastic Logic Programs from Proof-Banks. In M. Veloso and S. Kambhampati, editors, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), pages 752757, Pittsburgh, Pennsylvania, USA, July 9-13, 2005. L. De Raedt, K. Kersting. Probabilistic Inductive Logic Programming. In S. Ben-David, J. Case and A. Maruoka, editors, Proceedings of the 15th International Conference on Algorithmic Learning Theory (ALT-2004), pages 19-36, LNCS 3244, Padova, Italy, October 2-5, 2004. K. Kersting, U. Dick. Balios - The Engine for Bayesian Logic Programs. Demonstration paper in J.-F. Boulicaut, F. Esposito, F. Giannotti and D. Pedreschi, editors, Proceedings of the 8th European Conference on Principles and Practice of Knowledege Discovery in Databases (PKDD-2004), pages 549-551, LNCS vol. 3202, Springer, Pisa, Italy, September 20-25, 2004. K. Kersting, T. Gaertner. Fisher Kernels for Logical Sequences. In J.-F. Boulicaut, F. Esposito, F. Giannotti and D. Pedreschi, editors, Proceedings of the 15th European Conference on Machine Learning (ECML-2004), pages 205 - 216, LNCS vol. 3201, Springer, Pisa, Italy, September 20-25, 2004. K. Kersting, L. De Raedt. Logical Markov Decision Programs and the Convergence of Logical TD(lambda). In A. Srinivasan, R. King, and R.Camacho, editors, Proceedings of the Fourteenth International Conference on Inductive Logic Programming (ILP-2004), pages 180-197. Porto, Portugal, September 6-8, 2004. K. Kersting, M. Van Otterlo, L. De Raedt. Bellman goes Relational. In R. Greiner and D. Schuurmans, editors, Proceedings of the Twenty-First International Conference on Machine Learning (ICML-2004), pages 465 - 472. Banff, Alberta, Canada, July 48, 2004. J. Fischer, K. Kersting. Scaled CGEM: A Fast Accelerated EM. In N. Lavrac, D. Gamberger, H. Blockeel, and L. Todorovski, editors, Proceedings of the Fourteenth European Conference on Machine Learning (ECML-2003), pp. 133-144, LNCS vol. 2837, Springer, Cavtat, Croatia, September 22-26, 2003. K. Kersting, T. Raiko, S. Kramer, L. De Raedt. Towards Discovering Structural Signatures of Protein Folds based on Logical Hidden Markov Models. In R. B. Altman, A. K. Dunker, L. Hunter, T. A. Jung and T. E. Klein, editors, Proceedings of the Pacific Symposium on Biocomputing (PSB-2003), pp. 192-203, January 3-7 2003, Kauai, Hawaii, USA. K. Kersting, L. De Raedt. Towards Combining Inductive Logic Programming and Bayesian Networks. In C. Rouveirol, M. Sebag, editors, Proceedings of the Eleventh International Conference on Inductive Logic Programming (ILP-2001),pages 118-131, LNCS 2157, Springer, Strasbourg, France, September 2001. K. Kersting, L. De Raedt. Adaptive Bayesian Logic Programs. In C. Rouveirol, M. Sebag, editors, Proceedings of the Eleventh International Conference on Inductive Logic Programming (ILP-2001), pages 104 - 117, LNCS 2157, Springer, Strasbourg, France, September 2001.
Proceedings van conferenties met programma comite en zwakkere selectie . . . .
T. Guerel, K. Kersting. On the Trade-Off Between Iterative Classification and Collective Classification: First Experimental Results. In S. Nijssen, T. Meinl, and G. Karypis, editors, Working Notes of the Third International ECML/PKDD-Workshop on Mining Graphs, Trees and Sequences (MGTS-05), Porto, Portugal, October 7, 2005. M. Van Otterlo, K. Kersting. Challenges for Relational Reinforcement Learning. In the Working Notes of the ICML-2004 Workshop on Relational Reinforcement Learning. P. Tadepalli, R. Givan, K. Driessens, editors. Banff, Alberta, Canada, July 8, 2004. K. Kersting, M. Van Otterlo, L. De Raedt. Bellman goes Relational (Extended Abstract). L. Schomaker, N. Taatgen, R. Verbruggethe, editors, Proceedings of the Sixtheenth Belgian-Dutch Conference on Artificial Intelligence (BNAIC-04), Groning, The Netherlands, October 21-22, 2004. K. Kersting, T. Raiko, L. De Raedt. A Structural GEM for Learning Logical Hidden Markov Models. In S. Dzeroski, L. De Raedt,
. . . . . . . .
and S. Wrobel, editors, Working Notes of the Second KDD-Workshop on Multi-Relational Data Mining (MRDM-03), Washington, DC, USA, August 27, 2003. K. Kersting, L. De Raedt. Logical Markov Decision Programs. In L. Getoor and D. Jensen, editors, Working Notes of the IJCAI2003 Workshop on Learning Statistical Models from Relational Data (SRL-03), pp. 63-70, August 11, Acapulco, Mexico, 2003. K. Kersting. Representational power of probabilistic-logical models: From upgrading to downgrading. In L. Getoor and D. Jensen, editors, Working Notes of the IJCAI-2003 Workshop on Learning Statistical Models from Relational Data (SRL-03), pp. 6162, August 11, Acapulco, Mexico, 2003 K. Kersting, L. De Raedt, S. Kramer. Interpreting Bayesian Logic Programs. In L. Getoor and D. Jensen, editors, Proceedings of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data, Technical Report WS-00-06, AAAI Press, Austin/Texas, USA, 2000. K. Kersting, T. Gaertner. Fisher Kernels and Logical Sequences with an Application to Protein Fold. NIPS 2002 workshop on Machine Learning Techniques for Bioinformatics organized by C. Campbell, F. d’Alch-Buc, P. Long. December (Friday) 13, 2002, Vancouver, Canada. T. Raiko, K. Kersting, J. Karhunen, L. De Raedt. Bayesian Learning of Logical Hidden Markov Models. In Proceedings of the Finnish AI conference (STeP-2002), pp. 64-71, 15-17 December 2002, Oulu, Finland. K. Kersting, N. Landwehr. Scaled Conjugate Gradients for Maximum Likelihood: An Empirical Comparison with the EM Algorithm. In J. A. Gamez and A. Salmern, editors, Proceedings of the First European Workshop on Probabilistic Graphical Models (PGM-02), pp. 89-98, November 6-8, 2002, Cuenca, Spain. K. Kersting, T. Raiko, L. De Raedt. Logical Hidden Markov Models (Extended Abstract). In J. A. Gamez and A. Salmern, editors, Proceedings of the First European Workshop on Probabilistic Graphical Models (PGM-02), pp. 99-107, November 6-8, 2002, Cuenca, Spain. K. Kersting, L. De Raedt. Bayesian Logic Programs. In Proceedings of ”Informatiktage-2000”, Bad Schussenried, Germany, October 2000.
. Hoofstukken on boeken . .
K. Kersting, L. De Raedt. Bayesian Logic Programming: Theory and Tool. Chapter to appear in L. Getoor and B. Taskar, editors, An Introduction to Statistical Relational Learning, MIT Press. K. Kersting, N. Landwehr. Scaled Conjugate Gradients for Maximum Likelihood: An Empirical Comparison with the EM Algorithm. Chapter (pp. 235-254) in ”Advances in Bayesian Networks”, Series: Studies in Fuzziness and Soft Computing, Vol. 146, J. A. Gmez, S. Moral and A. Salmern, editors, Springer, 2004.
Publiciaties in tijdschriften of boeken zondern leesomite . . .
K. Kersting, L. De Raedt. Bayesian Logic Programs. (On invitation). In E. Leopold and M. Kirsten, editors, Proceedings of ”Treffen der GI-Fachgruppe 1.1.3 Maschinelles Lernen” (FGML-2000), GMD Report 114, Sankt Augustin, Germany, 2000. (not refereed) K. Kersting, L. De Raedt. Bayesian Logic Programs. In J. Cussens and A. Frisch, editors, Work-in-Progress Reports of the Tenth International Conference on Inductive Logic Programming (ILP-2000), London,U.K., 2000. (online Proceedings) K. Kersting, L. De Raedt. Bayesian Logic Programs. (On invitation). In F. Furukawa, S. Muggleton, D. Michie, and L. De Raedt, editors, Proceedings of the Seventeenth Machine Intelligence Workshop (MI-17), Bury St. Edmunds, Suffolk, U.K., 2000.
Interne verslagen . . .
K. Kersting, T. Raiko, S. Kramer, L. De Raedt. Towards Discovering Structural Signatures of Protein Folds based on Logical Hidden Markov Models. Technical Report No. 175, Institute for Computer Science, University of Freiburg, Germany, June 2002. K. Kersting, L. De Raedt. Basic Principles of Learning Bayesian Logic Programs. Technical Report No. 174, Institute for Computer Science, University of Freiburg, Germany, June 2002. K. Kersting, L. De Raedt. Bayesian Logic Programs. Technical Report No. 151, Institute for Computer Science, University of Freiburg, Germany, April 2001.
. Engelstalige pagina voor de referenten. Kan in het Nederlands worden ingevuld zo alle referenten deze taal beheersen. Name of the applicant Abstract of the research project in the frame of an application for a post doctoral fellowship of the Fund for Scientific Research – Flanders (Belgium)(FWO)(max. 2 pages). 1.aim – 2.objectives – 3.design and methodology
Name Applicant: Kristian Kersting Poject Title: Statistical Relational Learning Statistical relational learning (SRL) is a new subfield of machine learning that deals with learning and mining in relational domains where observations may be missing, partially observed, and/or noisy. This integration of relational and first order representations, probabilistic and statistical reasoning, and machine learning becomes nowadays more and more important: the amount of
heterogeneous data that is being collected in the business and scientific world is growing explosively. Example domains include bioinformatics, transportation systems, communication networks, social network analysis, among others. These domains provide uncertain information about variable numbers of objects and relations among these objects, so-called relational domains. Techniques for descriptive and predictive machine learning tasks, for modeling dynamic environments, and for making complex decisions within these worlds, i.e., SRL techniques are needed and have indeed the potential to lay the foundation for the next generation of artificial intelligence (AI) and machine learning (ML). The importance and popularity of SRL is witnessed by an increasing number of SRLrelated workshops (SRL02, SRL03, SRL04, MI-19, RRL04, RRL05, Dagstuhl seminar 05051 in 2005, and a forthcoming Dagstuhl seminar 0716 in 2007, which is co-chaired by the applicant), invited talks (IJCAI-01, ICML03, KDD03, ECML/PKDD04, BeNeLearn05, ILP04, ILP05, ECML/PKDD05) and tutorials (ICML04, AAAI05, IDA05, ECML/PKDD05, IJCAI05), and international projects (DARPA project on Transfer Learning; EU projects APrIL I and II “Applications of Probabilistic Inductive Logic Programming” coordinated by Freiburg). The initial phase of SRL research, see [3] for an overview, was characterized by the exploration of many different ways to combine statistical and relational models. Typically, the logical concepts of objects and relations among them were combined with some statistical model, say a Bayesian network or Markov model. Then, methods to induce these SRL models from data have been developed. Both phases seem to have tapered off: there is a good practical understanding of various SRL approaches through several applications. In this project, I will focus on fundamental issues of SRL. More precisely, I propose to address: (WP1) mappings among SRL approaches, (WP2) sample complexity results, (WP3) equivalence classes of SRL models, (WP4) probability-logic trade-off within SRL, (WP5) efficient reasoning within and learning of SRL. Work Part 1 (Mappings) No clear and generally accepted understanding of the relative advantages and limitations of different SRL techniques has yet emerged. The project will investigate mappings between different SRL models. Mappings naturally facilitate the transfer of techniques developed within different SRL frameworks. Although some mappings have been already proposed, see e.g. [8, 10], no general framework has been developed yet. The project will develop a hierarchy among the SRL approaches that takes the complexities of the mappings and the type of queries a framework supports into accounts. Such complexity-hierarchies lie at the heart of theoretical computer science. Work Part 2 (Sample Complexity) The speed up, i.e., the gain in running time of statistical learning through relational abstraction has been reported only empirically. The project will approach the issue in a more principled way and will develop sample complexities for SRL models: Sample complexities specify the number of training examples needed to get high quality models. Furthermore, sample complexity bounds on the quality of models can be used to detect useless models early in search. Work Part 3 (Equivalence Classes) Often, syntactically different SRL models still specify the same probability distribution. Stateof-the-art SRL techniques for model selection or model averaging do not take into account equivalence classes among SRL models, i.e., classes of SRL models associated with a unique probability distribution. In turn, they suffer from high computational costs due to estimating the same distribution again and again. The project will develop notations of equivalence within SRL. Work Part 4 (Probability - Logic Trade-Off) Most initial SRL research focused on highly expressive frameworks. High expressiveness burdens the learning process with high computational costs. The right trade-off between simple/complex statistical models and simple/complex logical languages is unknown. This is akin to the bias-variance trade-off in computational learning theory: a model with a high degree of freedom may have poor generalization capabilities to unseen examples. Combining statistical models with relational representations even increases the degrees of freedom. I will explore combinations of statistical and logical models at different levels of expressiveness. Initial results [6] indicate that already simple combinations are quite powerful. Work Part 5 (Efficient Reasoning) SRL approaches typically evaluate a large number of queries on the set of training examples. These queries are very similar so that executing them independently may involve a lot of redundant computation. The project will investigate how to reduce the running time by exploiting redundancy among queries and training examples. One promising approach is to employ (inductive) logic programming techniques, for which the DTAI group at K.U. Leuven is renowned. For instance, tabling [4] of queries can greatly speed up logical inference. The idea of tabling is as follows. During the execution of a query, each sub-goal S is registered in a table the first time it is called, and unique answers are added to the table as they are derived. Using tabling for model selection, i.e., storing redundant information across several similar models has not been considered within SRL. I will also explore query packs [2], which structure sets of similar queries, and distribution preserving transformations of statistical relational learning models. Such transformations considerably speed up the execution of queries for pure logic programs [9]. Alternatively, I will investigate relational variants of AD-trees [7]. AD-trees are an efficient data structure for caching redundant information during learning of statistical models. In general many SRL models of interest are large, which makes exact inference very slow, if not intractable. Therefore, the project will also resort to approximation techniques. Here, the relational representations of a domain itself can lead to novel and better approximate inference algorithm. I will investigate relational abstraction, e.g. through logical decision trees [1], within particle filters [5]. The basic idea of particle filters is a Monte Carlo simulation, in which the distribution of interest is approximated by a set of particles with associated weights. Thus, the number of particles directly affects the running time. Relational abstraction will reduce the number of particles as particles are shared by all states belonging to the same abstract state. It is my belief that addressing these issues will pave the way towards a general theory of SRL.
References [1] H. Blockeel and L. De Raedt. Top-down Induction of First-order Logical Decision Trees. Artificial Intelligence, 101(1–2):285–297, 1998. [2] H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H. Vandecasteele. Improving the Efficiency of Inductive Logic Programming Through the Use of Query Pack. Journal of Artificial Intelligence Research (JAIR), 16:135–166, 2002. [3] L. De Raedt and K. Kersting. Probabilistic Logic Learning. In ACM-SIGKDD Explorations, special issue on Multi-Relational Data Mining, S. Dzeroski and L. De Raedt, editors, Vol. 5(1), pp. 31-48, July 2003. [4] B. Demoen and K. F. Sagonas. CAT: The Copying Approach to Tabling. Journal of Functional and Logic Programming, 1999. Special Issue 2. [5] A. Doucet, N. de Freitas, and N. Gordon, editors. Sequential Monte Carlo in Practice. Springer, 2001. [6] N. Landwehr, K. Kersting, and L. De Raedt. nFOIL: Integrating Na¨ıve Bayes and Foil. In M. Veloso and S. Kambhampati, editors, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), pages 795–800, Pittsburgh, Pennsylvania, USA, July 9–13 2005. AAAI. [7] A. W. Moore and M. S. Lee. Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets. Journal of Artificial Intelligence Research (JAIR), 8:67–91, 1998. [8] M. Richardson and P. Domingos. Markov Logic Networks. Machine Learning, 2006. (To appear). [9] V. Santos Costa, A. Srinivasan, R. Camacho, H. Blockeel, B. Demoen, G. Janssens, J. Struyf, H. Vandecasteele, and W. Van Laer. Query Transformations for Improving the Efficiency of ILP Systems. Journal of Machine Learning Research (JMLR), 4:465–491, 2003. [10] J. Vennekens, S. Verbaeten, and M. Bruynooghe. Logic Programs with Annotated Disjunctions. In B. Demoen and V. Lifschitz, editors, Proceedings of 20th International Conference on Logic Programming (ICLP-04), pages 431–445, Saint-Malo, France, September 6-10 2004.
Vermeld voor iedere referent zijn drie beste publicaties die relevant zijn voor het onderzoeksproject.
Maurice Bruynooghe J. Struyf, J. Ramon, M. Bruynooghe, S. Verbaeten, and H. Blockeel: Compact Representation of Knowledge Bases in Inductive Logic Programming. Machine Learning Journal 57(3):305-333, 2004 L. De Raedt and M. Bruynooghe: A Theory of Clausal Discovery. In the Proceedings of the 13th International Joint Conference on Arificial Intelligence (IJCAI-93), pages 1058-1063, 1993. M. Bruynooghe: A Practical Framework for the Abstract Interpretation of Logic Programs. Journal of Logic Programming, 10(2):91124, 1991.
Yves Deville P. Hentenryck, L. Michelle, and Y. Deville,: Numerica. A Modeling Language for Global Optimization. The MIT Press, Cambridge, 1997. Y. Deville and K. Lau: Logic Program Synthesis. Journal of Logic Programming, 19,20: 321-350, 1994. P. Van Hentenryck, Y. Deville, C.-. Teng: A Generic Arc-Consistency Algorithm and its Specializations. Artificial Intelligence Journal 57(2-3): 291-321, 1992
Taisuke Sato H. Tamaki and T. Sato.: Unfold/fold Transformation of Logic Programs, In the Proceedings of the 2nd International Conference on Logic Programming (ICLP-84), pp.127-137, Uppsala, 1984. H. Tamaki and T. Sato: OLD Resolution with Tabulation, In Proceedings of the 3rd International Conference on Logic Programming (ICLP-86), pp. 84-98, London, GB, 1986 T. Sato and Y. Kameya. Parameter Learning of Logic Programs for Symbolic-statistical Modeling, Journal of Artificial Intelligence Research 15:291-454, 2001.
Gelieve aan de duiden (enkel voor biomedische wetenschappen) :
Mijn kandidatuur beoogt een NIH-FWO Postdoctoraal Onderzoeksmandaat. Mocht ik het NIH-FWO Postdoctoraal Onderzoeksmandaat niet ontvangen dan wens ik in aanmerking te komen voor een mandaat Postdoctoraal Onderzoeker FWO met een gewone mobiliteitstoelage voor één jaar voor dezelfde bestemming. Mocht ik het NIH-FWO mandaat niet ontvangen dan wens ik in aanmerking te komen voor een mandaat Postdoctoraal Onderzoeker FWO zonder een mobiliteitstoelage.
