Inductive Logic Programming

European Scientific Network

ILPNET

Description of the Nodes

May 1994

ILPNET is the Inductive Logic Programming European Scientific Network, financially supported by the CEC Action for Cooperation in Science and Technology with Central and Eastern European Countries (PECO 92), contract no. CIPA3510OCT920044. ILPNET is being financed for the duration of three years, starting on July 26, 1993. ILPNET gathers 19 leading European institutions involved in Inductive Logic Programming research.

Inductive Logic Programming (ILP) is a research area in the intersection of inductive machine learning and computational logic. The aim of the scientific network ILPNET is to stimulate the development, coordination, communication and exchange of results and personnel in European ILP research and to disseminate the research results to a wider European/world research community. In the scientific sense, the aim of ILPNET is to provide the infrastructure for the ongoing European research in ILP, most of which is currently performed within the ESPRIT III Basic Research Project No. 6020 Inductive Logic Programming. A particular aim of ILPNET is to build new communication and dissemination channels and to make them available to Central and Eastern European researchers interested in ILP.

ILPNET has the following objectives:

• support the existing and build new communication channels between ILPNET nodes,

• enable joint research activities by supporting short visits of researchers at other ILP-NET nodes,

• support organizing and attending specialized meetings and workshops,

• build a common database of ILP scientific publications, data and systems,

• promote the results of ILP research also outside ILPNET.

The management structure of ILPNET is the following:

• academic coordinator: Nada Lavrač, J. Stefan Institute, Ljubljana, Slovenia,

• management board: Project Managers of ILPNET nodes,

• academic secretary: Darko Zupanič, J. Stefan Institute, Ljubljana, Slovenia.

Contact:

Nada Lavrač, Darko Zupanič

Jožef Stefan Institute

Jamova 39, 61111 Ljubljana, Slovenia

phone +386 61 12 59 199, fax +386 61 12 58 058 and +386 61 219 385 Email: {Nada.Lavrac,Darko.Zupanic}@ijs.si

This booklet is intended to provide an overview of the current ILP research in Europe, by giving a compact description of each ILPNET node, including a list of researchers, main research areas, description of current research, list of recent publications and exact addresses of contact persons. The booklet contains the descriptions of the following nodes (ordered in the alphabetic order of the institution’s hometown):

1. Romanian Academy of Sciences (RA), Bucharest, Romania (G. Tecuci),

2. University of Dortmund (UDO), Dortmund, Germany (K. Morik),

3. Technical University Graz (TUG), Graz, Austria (M. Kubat),

4. Katholieke Universiteit Leuven (KUL), Heverlee, Belgium (L. De Raedt),

5. J. Stefan Institute and Faculty of Electrical Engineering and Computer Science (LAI), Ljubljana, Slovenia (N. Lavrač),

6. Faculty of Technical Sciences Maribor (TFM), Maribor, Slovenia (B. Dolšak),

7. Université Paris Sud (LRI), Orsay, France (C. Rouveirol),

8. Oxford University (OUCL), Oxford, United Kingdom (S. Muggleton),

9. University of Porto (LIACC), Porto, Portugal (P. Brazdil),

10. Czech Technical University (CTU), Czech Republic (O. Stenkova),

11. German National Research Center for Computer Science (GMD), Sankt Augustin, Germany (S. Wrobel),

12. Bulgarian Academy of Sciences (IINF), Sofia, Bulgaria (Z. Markov),

13. University of Stockholm (STO), Stockholm, Sweden (C.G. Jansson),

14. Universität Stuttgart (STU), Stuttgart, Germany (B. Tausend),

15. Hungarian Academy of Sciences (ARJ), Szeged, Hungary (T. Gyimóthy),

16. Tilburg University (ITK), Tilburg, the Netherlands (P. Flach),

17. Universita di Torino (TO), Torino, Italy (F. Bergadano),

18. Research Institute for Applied Knowledge-Processing (FAW), Ulm, Germany (R. Wirth),

19. Austrian Research Institute for Artificial Intelligence (ARIAI), Vienna, Austria (I. Mozetič)

This booklet was distributed by email to ILPNET partners and to approx. 250 subscribers of ILPNET Newsletter (ILP Newsletter, Volume 1, Number 2, 23rd May 1994). It is also accessible via World-Wide Web from the ILPNET titlepage at http://wwwai.ijs.si/ilpnet.html.

Nada Lavrač

Ljubljana, May 1994 Academic coordinator of ILPNET

Romanian Academy (RA)

Center for Machine Learning, Natural Language Processing and Conceptual Modeling Bucharest Romania

Researchers Gheorghe Tecuci, Dan Tufis, Stefan Trausan-Matu, Octav Popescu.

ILP Areas Multistrategy learning, Knowledge base revision, Autonomous agents, Integration of machine learning and knowledge acquisition.

Description of Research Over the past several years we have developed several learning methods and systems as, for instance, DISCIPLE, NeoDISCIPLE, and MTL-JT. DISCIPLE, which has been developed in cooperation with LRI of the University of Paris-South, is one of the first multistrategy learning systems [1, 2]. It learns general rules from a human expert by synergistically integrating inductive empirical learning, explanation-based learning and learning by analogy. DISCIPLE has been applied in several domains as, for instance, loudspeaker manufacturing, chemistry, and robotics. NeoDISCIPLE [3, 11] is a development of DISCIPLE which addresses the problem of extending and correcting an imperfect knowledge base. MTL-JT [4, 13] is a general framework for multistrategy-task adaptive learning which dynamically integrates the elementary inferences that are employed by single-strategy learning methods (such as deduction, analogy, abduction, generalization, specialization, abstraction, concretion, etc.), depending of the features of the learning task to be performed.

Current research consists in further developing the MTL-JT framework [13], developing a general methodology for knowledge base refinemet through plausible inference and multistrategy learning [7], and developing autonomous adaptive agents for adversarial planning [9].

Recent Publications

[1] G. Tecuci. DISCIPLE: A theory, methodology and system for learning expert knowledge. PhD Thesis, University of Paris-South, France, 1988.

[2] G. Tecuci, Y. Kodratoff. Apprenticeship learning in imperfect domain theories. In Y. Kodratoff, R. S. Michalski (eds.) Machine Learning: An Artificial Intelligence Approach, Vol. III. Morgan Kaufmann, 1990.

[3] G. Tecuci. Automating knowledge acquisition as extending, updating and improving a knowledge base. IEEE Transactions on Systems, Man and Cybernetics 22 (6), 1444– 1460, 1992.

[4] G. Tecuci. Plausible justification trees: A framework for the deep and dynamic integration of learning strategies. Machine Learning, 11 (2-3), 1993.

[5] R. S. Michalski, G. Tecuci. Multistrategy learning. In A. Kent, J. G. Williams (eds.) Encyclopedia of Microcomputers, Vol. 12. Marcel Dekker, Inc. of New York, 1993.

[6] R. S. Michalski, G. Tecuci (eds.). Proceedings of the Second International Workshop on Multistrategy Learning, Harpers Ferry, West Virginia, May 1993.

[7] G. Tecuci, D. Duff. Integrating multistrategy learning and knowledge acquisition for knowledge base refinement. Proceedings of the IJCAI-93 Workshop on Machine Learning and Knowledge Acquisition, Chambery, France, August 1993.

[8] G. Tecuci, S. Kedar, Y. Kodratoff (eds.). Proceedings of the IJCAI-93 Workshop on Machine Learning and Knowledge Acquisition: Common Issues, Contrasting Methods, and Integrated Approaches, Chambery, France, August 1993.

[9] M. R. Hieb, D. Hille, G. Tecuci. Designing a computer opponent for wargames: Integrating planning, knowledge acquisition and learning in WARGLES. Proceedings of the AAAI 1993 Fall Symposium Series, Raleigh, North Carolina, October 1993.

[10] G. Tecuci (guest editor). Informatica 17 (4), Special Issue on Multistrategy Learning. Slovenia, 1993.

[11] G. Tecuci, M. Hieb. Consistency-driven knowledge elicitation: Using a learningoriented knowledge representation that supports knowledge elicitation in NeoDISCI-PLE. Knowledge Acquisition Journal, December 1993.

[12] R. S. Michalski, G. Tecuci (eds.). Machine Learning: A Multistrategy Approach, Vol. IV. Morgan Kaufmann, San Mateo, 1994.

[13] G. Tecuci. An inference-based framework for multistrategy learning. In R. S. Michalski, G. Tecuci (eds.) Machine Learning: A Multistrategy Approach, Vol. IV. Morgan Kaufmann, San Mateo, 1994.

[14] G. Tecuci, S. Kedar, Y. Kodratoff (guest editors). Knowledge Acquisition Journal, Special Issue on the Integration of Machine Learning and Knowledge Acquisition, June 1994 (to appear).

Contact Person Gheorghe Tecuci Dan Tufis Center for Machine Learning, Natural Language Processing and Conceptual Modeling Calea Victoriei 125 Bucharest 1 Romania Phone: +1 703 993 1722 Fax: +1 703 993 3729 or +40 1 312 0209 E-mail: tecuci@cs.gmu.edu

University of Dortmund (UDO)

Department of Computer Science, LS VIII Dortmund Germany

Researchers Katharina Morik, Siegfried Bell, Steffo Weber, Anke Rieger, Volker Klingspor, Uschi Robers (student), Guido Lindner (student).

ILP Areas Multistrategy learning, ILP theory, Theory revision, Knowledge acquisition, Multi-valued logic.

Description of Research Topics such as learning in first order logic, integrating various learning tools (multistrategy learning) and formalizing inductive learning in order to get a clear view of where and how to apply which techniques have been a topic of research for Katharina Morik and her respective groups, long before these topics were internationally accepted and discussed. Building large software systems instead of just programming a technique is one of the strengths which in combination with the theoretical research offers new opportunities for machine learning applications.

In [7] we have shown how the main ILP settings proposed by Helft and Plotkin fit into one framework and how Foil’s behaviour [14] can be derived. This has been achieved by a prolegomenon to a three-valued logic. These ideas were elaborated in a recent paper [8] where we developed a notion of paraconsistent entailment as an alternative to Belnap’s four-valued logic of which some variants are used in ILP [9, 13]. It is an open question whether learning in ILP could be described in deductive manner to overcome the formal logical drawbacks of inductive reasoning.

Other research relates ILP to robotics. We have shown that an ILP system can be used to solve learning problems which arise in robot navigation [10]. Although it turned out that this is a very promising approach it is sometimes necessary to obtain short answer times; in [11] it is described how to modify the RDT learning procedure [9] for that reason. Since we consider cooperation and cross-fertilization as very important we relate our reasearch not only via theoretical terms to the state of the art, but also via empirical evaluation. A broad discussion and comparison of Mobal and Foil can found in [12].

Recent Publications

[1] K. Morik. Applications of Machine Learning, in Wetter (ed.) Current Developments in Knowledge Acquisition. Springer-Verlag, 1992.

[2] K. Morik, K. Causse, R. Boswell. A common knowledge representation integrating learning tools. In R. S. Michalski, G. Tecuci (eds.) Multistrategy Learning, Workshop Proceedings, Harper’s Ferry, 1991.

[3] K. Morik, J.-U. Kietz. Constructive induction of background knowledge. Proc. of the IJCAI-Workshop on Evaluating and Changing Representations in Machine Learning, Sydney, 1991.

[4] K. Morik. Balanced cooperative modeling. Machine Learning, 1993.

[5] K. Morik. Underlying assumptions in knowledge acquisition and machine learning. Knowledge Acquisition 3, 1991.

[6] S. Bell, S. Weber. On the close relationship between FOIL and the frameworks of Helft and Plotkin. Proceedins of the Third International Workshop on Inductive Logic Programming, Bled, 1993.

[7] S. Bell, S. Weber. A three-valued logic for ILP. Research Report LS-8 Nr.4, University of Dortmund, Dortmund, 1993.

[8] S. Bell, S. Weber. A note on paraconsistent inference in machine learning – Prelimanary report. University of Dortmund, Dortmund, 1994.

[9] K. Morik, S. Wrobel, J. Kietz, W. Emde. Knowledge Acquisition and Machine Learning. Academic Press, London, 1933.

[10] K. Morik, A. Rieger. Learning action-oriented perceptual features for robot navigation. LS-8 Report Nr. 3, University of Dortmund, Dortmund, 1993.

[11] V. Klingspor. GRDT: Enhancing models-based learning for its application in robot navigation. LS-8 Report Nr. 5, University of Dortmund, Dortmund, 1993.

[12] G. Lindner, U. Robers. Experimentelle Analyse zweier logik-basierter Lernverfahren. LS-8 Report Nr. 6, University of Dortmund, Dortmund, 1994.

[13] L. De Raedt. Interactive Theory Revision. Academic Press, London, 1992.∗

[14] J.R. Quinlan. Learning Logical Definitions From Relations. Machine Learning 5 (3), 1990.∗

Items marked with an asterisk are only mentioned for editorial convenience in this list. They are not by members of the group.

Contact Person Katharina Morik University of Dortmund Department of Computer Science, LS VIII Baroper Strasse 301 D-44221 Dortmund Germany Phone: +231 755 5101 Fax: +231 755 2047 E-mail: morik@kilo.informatik.uni-dortmund.de

Technical University Graz (TUG) Department of Medical Informatics

and Inst. of Theoretical Computer Science

Graz Austria

Researchers Wolfgang Maass, Miroslav Kubat, Peter Auer, Doris Flotzinger.

ILP Areas Computational learning theory, Inductive learning, Neural networks.

Description of Research The group concentrates primarily on the application of computational learning theory to the development of new learning algorithms, development of hybrid (symbolic and subsymbolic) learning systems and inductive logic programming.

Among major achievements, the contribution to the research of the complexity of inductive learning and to the theoretical foundations of neural networks should be mentioned [2, 3, 6, 8] as well as the solution of the computational complexity of function learning [7]. In the field of inductive learning, the group developed and co-developed the systems FAVORIT [4] and FLORA1-3 [1, 5] capable of learning under significant concept drift. Recently, the system TBNN initializing neural nets with an inductive-learning method has been developed and successfully tested in a medical domain [9].

Recent research interests include the study of the computational complexity of ILPoriented learning algorithms and the use of subsymbolic approaches for theory revision.

Recent Publications

[1] M. Kubat. Conceptual inductive learning—The case of unreliable teachers. Artificial Intelligence 52, 169–182, 1991.

[2] Z. Chen, W. Maass. On-line learning of rectangles. Proc. 5th Annual ACM Workshop on Computational Learning Theory, 16–28, 1992.

[3] Z. Chen, W. Maass. A solution to the credit assignmnet problem in the case of learning rectangles. Proc. 3rd Internat. Workshop on Analogical and Inductive Inference, Lecture Notes in Artificial Intelligence, Vol. 642, 26–34, Springer-Verlag, 1992.

[4] M. Kubat, I. Krizakova. Forgetting and ageing of knowledge in concept formation. Applied Artificial Intelligence 6, 193–204, 1992.

[5] G. Widmer, M. Kubat. Effective learning in dynamic environments by explicit context tracking. Proc. European Conference on Machine Learning, ECML ’93, 227–243, Vienna. Springer-Verlag, 1993.

[6] W. Maass, G. Turan. Lower bound methods and separation results for on-line learning models. Invited paper for a special issue of Machine Learning, 9, 107–145, 1992.

[7] P. Auer, P.M. Long, W. Maass, G.J. Woeginger. On the complexity of function learning. Proc. 5th Annual ACM Conference on Computational Learning Theory, 1993 (to appear).

[8] Z. Chen, W. Maass. On-line learning of rectangles and unions of rectangles. Invited paper for a special issue of Machine Learning (to appear).

[9] I. Ivanova, M. Kubat, G. Pfurtscheller. A decision-tree based neural net: Description and a case study. Proc. 11th International Conference on Machine Learning, 1994 (submitted).

Contact Person Miroslav Kubat Department of Medical Informatics Brockmanngasse 41 A-8010 Graz Austria Phone: (+43) 316 82 16 94 33 Fax: (+43) 316 81 29 64 E-mail: mirek@dpmi.tu-graz.ac.at Katholieke Universiteit Leuven (KUL) Department of Computing Science

Heverlee Belgium

Researchers Hilde Adé, Maurice Bruynooghe, Luc Dehaspe, Luc De Raedt, Gunther Sablon, Wim Van Laer.

ILP Areas Theory revision, Multiple predicate learning, Autonomous agents, Knowledge discovery in databases.

Description of Research The research of the Leuven’s Machine Learning Group is concentrated on Theory Revision and clausal discovery in deductive databases. In the past few years, the interactive theory revisor CLINT [2] has been developed. This system inductively and abductively learns simple logic programs from examples and background knowledge. CLINT is a user-friendly and opportunistic multi-strategy learner that integrates several interesting features: it generates its own examples, shifts its language bias, learns multiple related concepts at the same time, employs integrity constraints, has a sound theoretical behaviour (it identifies concepts and knowledge bases in the limit), invents new concepts by analogy to previously learned ones and is able to reason about the unknown and the inconsistent using a special multi-valued logic. CLINT was the first concept-learner to use integrity constraints, to shifts the bias of first order logic concept description languages and is certainly one of the most advanced integrated inductive learning systems. Recently the development of non-interactive theory revision system RUTH [1] was started. This system updates a given theory (logic program), as to make it consistent with a given set of integrity constraints. For this purpose, several techniques that were used in CLINT, are adapted for a non-interactive setting.

CLAUDIEN [6] is the first ILP system that discovers full clausal theories from databases. It also uses a different semantics for ILP, which puts several issues in ILP into a new perspective. The development of CLAUDIEN is a result of cross-fertilization between the work on computational logic (and deductive databases), and ILP, which Leuven is involved in.

Recent research interests of Leuven include also the integration of inductive machine learning principles with planning. Current research involves the development of a planning system for an autonomous agent, that uses the logical representation of the event calculus [11, 12].

Recent Publications

[1] H. Adé, L. De Raedt, M. Bruynooghe. Theory revision. Proceedings of the Third International Workshop on Inductive Logic Programming, 1993.

[2] L. De Raedt. Interactive Theory Revision: An Inductive Logic Programming Approach. Academic Press, 1992.

[3] L. De Raedt, M. Bruynooghe. Interactive concept-learning and constructive induction by analogy. Machine Learning, Vol. 8, 107–150, 1992.

[4] L. De Raedt, M. Bruynooghe. Belief updating from integrity constraints and queries. Artificial Intelligence 53, 291–307, 1992.

[5] L. De Raedt, N. Lavrač. The many faces of inductive logic programming (invited talk). In J. Komorowski, Z. Ras (eds.) Proceedings of the 7th International Symposium on Methodologies for Intelligent Systems, Lecture Notes in Artificial Intelligence, Vol. 689, Springer-Verlag, 1993.

[6] L. De Raedt, M. Bruynooghe. A theory of clausal discovery. Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1993.

[7] L. De Raedt. N. Lavrač, S. Džeroski. Multiple predicate learning. Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1993.

[8] L. De Raedt. Inductive logic programming and scientific discovery, 1994 (in press).

[9] L. De Raedt. A brief introduction to inductive logic programming (tutorial). Proceedings of the International Logic Programming Symposium, The MIT Press, Vancouver, Canada, 1993.

[10] S. Muggleton, L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 1994 (in press).

[11] G. Sablon, M. Bruynooghe. Using the event calculus to integrate planning and learning in an intelligent autonomous agent. Proceedings of the ECML ’93 Workshop on Integrated Learning Architectures, Vienna, 1993.

[12] G. Sablon, M. Bruynooghe. Using the event calculus to integrate planning and learning in an intelligent autonomous agent. Proceedings of the 2nd European Worskhop on Planning, Vadstena, Sweden, IOS Press, 1993.

Contact Persons Luc De Raedt Maurice Bruynooghe Department of Computing Science Celestijnenlaan 200 A B - 3001 Heverlee Belgium Phone: +32 16 20 10 15 Fax: +32 16 20 53 08 E-mail: {lucdr,maurice}@cs.kuleuven.ac.be

Ljubljana Artificial Intelligence Laboratories (LAI)

J. Stefan Institute and Faculty of Electrical Eng. and Computer Science Ljubljana Slovenia

Researchers Ivan Bratko, Bojan Cestnik, Sašo Džeroski, Aram Karalič, Igor Kononenko, Matevž Kovačič, Nada Lavrač, Dunja Mladenić.

ILP Areas Imperfect data, PAC-learnability, Declarative bias, Multiple predicate learning.

Description of Research The main aspects of LAI research in the area of ILP are the development of ILP algorithms and their application to real-world problems. Specific topics include handling imperfect data, handling numerical constraints, using statistical inference, heuristic, stochastic and genetic search techniques, declarative bias and learnability in ILP.

The problem of missing and imperfect data, including noise (random errors) has been thoroughly investigated [13, 5]. This problem is addressed also in a system for relational regression developed at LAI, as well as in the multiple predicate learning context [4]. A substantial body of LAI research in the area of noise handling is described in [13].

Most of ILP research has been devoted to the implementations of ILP systems, their experimental evaluation and application to real-world domains. Knowledge synthesis is one of the important aspects of ILP [1]. An early approach to ILP has been developed within the KARDIO project [3]. The ILP systems LINUS [12, 13], mFOIL [5] and MARKUS [10] have been developed. Stochastic and genetic approaches have also been investigated (systems sFOIL, MILP, GILP) with the goal to overcome locally optimal search used in state-of-the-art ILP systems [11, 15]. LAI research in ILP has already shown its potential for applications. LINUS is a tool for inductive learning from deductive databases [6] which can be used for knowledge discovery in databases and knowledge acquisition, e.g., acquisition of medical diagnostic rules in rheumatology [14]. ILP systems have been used to induce qualitative models [1]. mFOIL was applied to finite element mesh design and to learning of qualitative models from example qualitative behaviours [5]. Experiments with MARKUS have shown its potential for the construction and verification of logic programs [2], on discrete event simulation as well as the innovative design of electric circuits from first principles [1]. Recent work has constructed qualitative, as well as quantitative, models from example quantitative behaviour, by combining ILP and machine discovery techniques [7], implemented in the LAGRANGE and GOLDHORN systems.

LAI has contributed to the ILP theory by the study of PAC-learnability of constrained logic programs [9] and determinate logic programs [6].

Recent Publications

[1] I. Bratko. Applications of machine learning: Towards knowledge synthesis. New Generation Computing 11 (3–4), 343–360. Springer-Verlag.

[2] I. Bratko, M. Grobelnik. Inductive learning applied to program construction and verification. Proc. Artificial Intelligence from the Information Processing Perspective AIFIPP’92, Madrid, Spain, 1992.

[3] I. Bratko, I. Mozetič, N. Lavrač. KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems. The MIT Press. 1989.

[4] L. De Raedt, N. Lavrač, S. Džeroski. Multiple predicate learning. Proc. Thirteenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 1993.

[5] S. Džeroski. Handling imperfect data in inductive logic programming. Proc. Fourth Scandinavian Conference on Artificial Intelligence, SCAI-93, 111–125. IOS Press, Amsterdam, 1993.

[6] S. Džeroski, N. Lavrač. Inductive learning in deductive databases. IEEE Transactions on Knowledge and Data Engineering 5 (6), 939–949, 1993.

[7] S. Džeroski, L. Todorovski. Discovering dynamics. Proc. Tenth International Conference on Machine Learning, 97–103. Morgan Kaufmann, San Mateo, CA, 1993.

[8] S. Džeroski, S. Muggleton, S. Russell. PAC-learnability of determinate logic programs. Proc. Fifth ACM Workshop on Computational Learning Theory, 128–135. ACM Press, Baltimore, MD, 1992.

[9] S. Džeroski, S. Muggleton, S. Russell. Learnability of constrained logic programs. Proc. European Conference on Machine Learning. Springer-Verlag, Berlin, 1993.

[10] M. Grobelnik. MARKUS - an optimized Model Inference System. Proc. ECAI’92 Workshop on Logical Approaches to Machine Learning, Vienna, Austria, 1992.

[11] M. Kovačič, N. Lavrač, M. Grobelnik, D. Zupanič, D. Mladenič. Stochastic search in inductive logic programming. Proc. Tenth European Conference on Artificial Intelligence ECAI-92, 444–445, 1992.

[12] N. Lavrač, S. Džeroski. Weakening the language bias in LINUS. Journal on Experimental and Theoretical Artificial Intelligence 6, 95–119, 1993.

[13] N. Lavrač, S. Džeroski. Inductive Logic Programming: Techniques and Applications. Ellis Horwood, 1994.

[14] N. Lavrač, S. Džeroski, V. Pirnat, V. Križman. The use of background knowledge in learning medical diagnostic rules. Applied Artificial Intelligence 7, 273–293, 1993.

[15] U. Pompe. SFOIL: Stochastic approach to inductive logic programming. Proc. Second Slovenian Electrotechnical and Computer Conference, ERK’93, 1993.

Contact Person Nada Lavrač Jožef Stefan Institute Jamova 39 61000 Ljubljana Slovenia Phone: +38 61 1259199 Fax: +38 61 219385 or 1258058 E-mail: nada.lavrac@ijs.si Faculty of Technical Sciences Maribor (TFM)

Department of Mechanical Engineering Maribor Slovenia

Researchers Anton Jezernik, Bojan Dolšak.

ILP Area Applications of ILP to finite element mesh design.

Description of Research The research on ILP at TFM concentrates on the use of ILP methods to build a knowledge base for a finite element mesh design expert system [5], which is one out of three modules that we are proposing for an integrated ES for finite element methods (FEM) [6]. The first experiments have been done in 1990 at the Turing Institute in Glasgow by using the ILP algorithm GOLEM [1]. Respecting the results of the first experiments, a learning set has been slightly changed and extended. The knowledge base was inducted employing GOLEM again [2]. In cooperation with the AI group in Ljubljana a comparison between the results obtained by using three relation learning systems FOIL, GOLEM and LINUS has also been done [3].

The evaluation of the induced knowledge base has shown that the ILP application is an effective approach to solve the finite element mesh design problem. Yet, there are still some steps that have to be taken in order to improve the reliability and transparency of the rules in the knowledge base. Therefore we are planning to continue the research on this project in the directions described in [4]. The major problem in this stage is how to obtain enough appropriate FEM models to be added into the learning set. A wide action all over the Europe has been started recently [7].

Recent Publications

[1] B. Dolšak, S. Muggleton. The application of inductive logic programming to finite element mesh design. In S. Muggleton (ed.) Inductive Logic Programming, 451–472. Academic Press, London, 1992.

[2] B. Dolšak, A. Jezernik, I. Bratko. A knowledge base for finite element mesh design. Proc. International School for the Synthesis of Expert Knowledge, ISSEK Workshop, Bled, 1992.

[3] S. Džeroski, B. Dolšak. Comparison of ILP systems on the problem of finite element mesh design. Proc. International School for the Synthesis of Expert Knowledge, ISSEK Workshop, Bled, 1992.

[4] B. Dolšak, A. Jezernik. Expert system for finite element mesh design. Proc. International Conference Design to Manufacture in Modern Industry, 401–405. DMMI, Bled, 1993.

[5] B. Dolšak, A. Jezernik. A proposal for FEM expert system. Proc. Seventh World Congress on Finite Element Methods, 130–136. Monte Carlo, 1993.

[6] A. Jezernik, B. Dolšak. Expert systems for FEM. Proc. Seventh World Congress on Finite Element Methods, 150–153. Monte Carlo, 1993.

[7] B. Dolšak. Machine learning as a knowledge acquisition method for finite element mesh design. Finite Element News 6, 41–43. Robinson and Associates, Wimborne, Dorset, 1993.

Contact Person Bojan Dolšak Faculty of Technical Sciences Department of Mechanical Engineering Smetanova 17 62000 Maribor Slovenia Phone: +386 62 20091 Fax: +386 62 225451 or 225013 E-mail: dolsak@uni-mb.si Laboratoire de Recherche en Informatique (LRI)

Inference and Learning Group

Université Paris Sud Orsay France

Researchers Yves Kodratoff, Céline Rouveirol, Marta Franova, Claire Nédellec, Guillaume Leblanc.

ILP Areas Predicate invention, Declarative bias.

Description of Research The main research lines of LRI in the ESPRIT Basic Research Project 6020 “Inductive Logic Programming” are predicate invention and declarative bias.

The main focus in Predicate Invention is the study of the links and possible crossfertilization between ILP approaches to Predicate Invention and Program Synthesis methods that come from the Inductive Theorem Proving community. LRI’s system PRECOMAS [1, 2, 3, 4, 5] generates correct and computable definitions of predicates starting from specifications. It creates a new (recursive) predicate that characterizes the validity domain of the input specification. Other work in LRI in Predicate Invention and Program Synthesis is about the BMWk methodology, that discovers recursive relations among a set of terms. This methodology has been formalised in a term rewritting paradigm [12] and has been shown to exhibit some strong similarities and relevant improvements to related works in ILP.

In the field of Declarative Bias, LRI works on elicitation of learning biases both in knowledge intensive generalization [10] and in a subclass of empirical concept learners that follow a Generate and Test strategy. The most studied type of learning biases is the concept description language bias which statically restricts the set of learnable concepts. We focus in LRI on the study of search biases, (such as the adjustement of the generalisation/specialisation step), that directly influence learning performance such the number of examples needed for learning to converge, the learning speed, etc. [8, 9]. A prototype for a parameterisable learning system for the study of interaction between language and search biases is under developement.

Recent Publications

[1] M. Franova. A constructive proof for PRIME FACTORIZATION THEOREM: A result of putting it together in CONSTRUCTIVE MATCHING methodology. Rapport de Recherche No.780, L.R.I., Univ. de Paris-Sud, 1992.

[2] M. Franova, Y. Kodratoff. Predicate synthesis from formal specifications: Using mathematical induction for finding the preconditions of theorems. Rapport de Recherche No.781, L.R.I., Univ. de Paris-Sud, 1992.

[3] M. Franova, Y. Kodratoff. Simplifying implications in inductive theorem proving: Why and how? Rapport de Recherche No.788, L.R.I., Univ. de Paris-Sud, 1992.

[4] M. Franova, Y. Kodratoff, M. Gross.Constructive matching methodology: An extension and an application to a planning problem. Rapport de Recherche no. 838, L.R.I., Univ. de Paris-Sud, 1993.

[5] M. Franova, Y. Kodratoff, M. Gross. Constructive matching methodology: Formally creative or intelligent inductive theorem proving? In J. Komorowski, Z. W. Ras (eds.) Methodologies for Intelligent Systems - Proc. of ISMIS’93, Lecture Notes in Artificial Intelligence, Vol. 689, 476–485. Springer-Verlag, 1993.

[6] B. Duval. Abduction and induction for explanation based learning. Proc. Postconference Workshop on Abductive Reasoning of the International Conference on Logic Programming, Budapest, 1993.

[7] B. Duval. Relationships between machine learning and abductive reasoning. Proc. of European Working Session on Learning, EWSL-91, Lecture Notes in Computer Science, Vol. 482, 348–360. Springer-Verlag, 1991.

[8] C. Rouveirol, C. Nédellec. Biais pour les systemes incrementaux guides par les hypotheses. Actes des huitiemes Journees Francophones sur l’Apprentissage, 1993.

[9] C. Nédellec, C. Rouveirol. Hypothesis selection biases for incremental learning. Proceedings of the AAAI Spring Symposium Series workshop on Issues for Incremental Learning, 1993.

[10] C. Rouveirol, H. Ade, L. De Raedt. Bottom up Generalization in ILP. Proceedings of the IJCAI-93 workshop on ILP, 59–70, 1993.

[11] P. Flach. Predicate invention in inductive data engineering. Proc. European Conference on Machine Learning, Lecture Notes in Artificial Intelligence, Vol. 667. Springer-Verlag, 1993.

[12] G. Le Blanc. BMWk revisited – Generalization and Formalization of an algorithm for detecting recursive relations in term sequences. In F. Bergadano, L. De Raedt (eds.) Proc. Seventh European Conference on Machine Learning, ECML-94, Springer-Verlag, 1994.

Contact Person Céline Rouveirol Laboratoire de Recherche en Informatique (LRI) Inference and Learning Group Université Paris Sud Bât 490 F-91405 ORSAY Cédex France Email: celine@lri.fr Tel: +33 1 69416462 Fax: +33 1 69416586 Oxford University Computing Laboratory (OUCL)

Oxford

United Kingdom

Researchers Stephen Muggleton, David Page, Ashwin Srinivasan, Rui Camacho, Gary Powell.

ILP Areas Imperfect data, PAC-learnability, Predicate invention, Non-ground background knowledge, Numeric constraint handling, Applications in pilot training and drug design.

Description of Research The Oxford group, which transferred from the Turing Institute Glasgow in 1992, was the originator of the ILP systems CIGOL [1] and Golem [3]. CIGOL was ground-breaking in its introduction of the inverse resolution generalisation operators, V and W. However, CIGOL suffered from problems of inefficiency of search. To combat these problems the Golem system introduced a language restriction called ij-determinacy. This combination allowed a provably efficient implementation of Plotkin’s Relative Least General Generalisation. Since its inception, Golem has been successfully applied to a wide-range of application areas including Protein Secondary Structure prediction [7], Structure Activity prediction for drug design [8], automatic construction of qualitative models and satellite diagnosis. As such, it is the most widely field-tested ILP system. In addition, PAC-learning analysis of Golem’s ij-determinacy constraint [6] has shown that although non-determinate logic programs are unlearnable, the ij-determinate constraint allows PAC-learnability of a substantial class of logic programs.

A recent analysis of the shortcomings of ILP systems [11] was carried out on the basis of encountered difficulties in application of Golem. Shortcomings were noted in the following areas: 1) the use of ground atomic background in Golem and FOIL is overly restrictive in the following application areas: qualitative models, chess and natural language acquisition,

2) non-numerical data is badly handled in mesh and drugs domains, 3) the ij-determinacy constraint is too restrictive in qualitative modelling, chess and mesh domains, 4) search myopia is problematic for FOIL in program synthesis. All four of these problems have been addressed in a recent system called Progol [18]. The Progol system combines Inverse Resolution with top-down search through a refinement graph. Inverse Resolution is used with mode declarations to derive the most-specific clause within the mode language which entails a given example. Since inverse resolution is used, these mode-declarations do not require an ij-determinate restriction. The most specific clause is used to guide a refinementgraph search. Unlike the searches of Shapiro’s MIS and Quinlan’s FOIL, Progol carries out an A* search which is both highly efficient and has a provable guarantee of returning a solution having the maximum information compression in the search-space. To do so it performs an admissible A* search, guided by compression, over clauses which subsume the most specific clause. Progol deals with noisy data by using the compression measure to trade-off the description of errors against the hypothesis description length. Progol allows arbitrary Prolog programs as background knowledge and arbitrary definite clauses as examples. Despite this, in bench-tests the efficiency of Progol compares favourably with FOIL.

Progol handles numeric data and has been tested by Ashwin Srinivasan on a range of problems, including a new large database of carcinogenic compounds. Unlike previous drug datasets to which Golem was applied, the carcinogen dataset has highly non-determinate background knowledge in the form of a low-level bonds and atoms representation of the molecules. In the trial on carcinogens Progol was tested against FOIL. For this dataset Progol’s solution (which is optimally compact) has around 10 per cent higher accuracy on the test set than FOIL’s solution. Progol’s clauses are also much simpler. The runtime of Progol was 2 days, while the runtime of FOIL was 2 weeks.

Rui Camacho’s research is based on building control rules for aircraft navigation using Progol. Data is gathered from pilot execution of a simulated F-111. The output data is highly numeric and voluminous. The primary aim of the research is the construction of comprehensible models of pilot behaviour which can be used for “debugging” a particular pilot’s behaviour. According to aerospace companies questioned about this research topic, automatically constructed explicit pilot behaviour models will be invaluable in pilot training.

Gary Powell recently started his research at Oxford on the topic of modelling student learning in mathematics. His present plan is to use Progol to automatically conjecture Euclid’s theorems in plane geometry. This will proceed by a combination of experimentation and learning. The experimentation will involve projection of lines onto a 2D pixel array. Encoded background knowledge concerning such things as coincidence and parallelism will be used to make conjectures within the language used in Euclid’s axioms.

David Page’s research presently concentrates on analysis of learning self-recursive clauses. In addition, he is investigating extensions and applications of PAC-learning results for nonrecursive clauses. He is also studying a PAC-style formalisation of speed-up learning, using a first-order logic representation of control rules. His previous research, with Alan Frisch, provided the first results on PAC-learnability of logic programs [21, 22]. His work with Mike Frazier produced one of the few results for PAC-learning self-recursive clauses without additional queries [23].

Recent Publications

[1] S. Muggleton, W. Buntine. Machine invention of first order predicates by inverting resolution. Proceedings of the 5th International Conference on Machine Learning, 339– 351. Morgan Kaufmann, 1988.

[2] S. Muggleton. Inductive logic programming. New Generation Computing, 8 (4), 295– 317, 1991.

[3] S. Muggleton, C. Feng. Efficient induction of logic programs. Proceedings of the 1st conference on algorithmic learning theory. Ohmsha, Tokyo, Japan, 1990.

[4] S. Muggleton (ed.). Inductive Logic Programming. 550 pages. Academic Press, 1992.

[5] S. Muggleton, A. Srinivasan, M. Bain. Compression, significance and accuracy. Proceedings of the Ninth International Machine Learning Conference, 338–347. Morgan Kaufmann, 1992.

[6] S. Džeroski, S. Muggleton, S. Russell. PAC-learnability of Determinate Logic Programs. Proceedings of the International Conference on Learning Theory (COLT92). Morgan Kaufmann, 1992.

[7] S. Muggleton, R. King, M. Sternberg. Protein secondary structure prediction using logic-based machine learning. Protein Engineering 5 (7), 647–657, 1992.

[8] R. King, S. Muggleton, M. Sternberg, R. Lewis. Drug design by machine learning: The use of inductive logic programming to model the structure-activity relationships of trimethoprim analogues binding to dihydrofolate reductase. Proceedings of the National Academy of Sciences, 89 (23), 1992.

[9] S. Muggleton (ed.). Proceedings of the Third International Workshop on Inductive Logic Programming. Jozef Stefan Institute, Bled, Slovenia, 1993.

[10] S. Muggleton. Predicate Invention and Utility. Journal on Experimental and Theoretical Artificial Intelligence 6, 1993.

[11] S. Muggleton. Inductive logic programming: Derivations, successes and shortcomings. SIGART Bulletin 5 (1), 5–11. ACM Press, 1994.

[12] S. Muggleton (co-editor). Machine Intelligence 13. Oxford University Press, 1994 (to appear).

[13] S. Muggleton. Logic and learning: Turing’s legacy. Machine Intelligence 13. Oxford University Press, 1994 (to appear).

[14] S. Muggleton, L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 1994 (to appear).

[15] S. Muggleton. Inverting implication. Artificial Intelligence (to appear).

[16] S. Muggleton. Optimal layered learning: A PAC approach to incremental sampling. Theoretical Computer Science (submitted).

[17] M. Sternberg, R. King, R. Lewis, S. Muggleton. Applications of Machine Learning to Structural Molecular Biology. Philosophical Transactions of the Royal Society of London, Series B (to appear).

[18] S. Muggleton, A. Srinivasan. Mode-directed inverse resolution. In Machine Intelligence 14, Oxford University Press (to appear).

[19] S. Muggleton (co-editor). Machine Intelligence 14. Oxford University Press (to appear).

[20] A. Frisch, D. Page. Generalization with Taxonomic Information. Proc. Eighth Nat. Conf. on A.I. (AAAI-90), 755–761. Boston, MA, August, 1990.

[21] D. Page, A. Frisch. Generalizing Atoms in Constraint Logic. Proc. Second Int. Conf. on Principles of Knowledge Representation and Reasoning (KR-91), 429–440, 1991.

[22] D. Page, A. Frisch. Generalization and learnability: A study of constrained atoms. In S. Muggleton (ed.) Inductive Logic Programming, 29–61. Academic Press, 1992.

[23] M. Frazier, D. Page. Learnability in inductive logic programming: Some basic results and techniques. Proc. Eleventh Nat. Conf. on A.I. (AAAI-93), Washington, DC, July, 1993.

Contact Person Stephen Muggleton Oxford University Computing Laboratory Wolfson Building Parks Road Oxford OX1 3QD United Kingdom Phone: +44 865 273838 Fax: +44 865 273839 E-mail: steve@prg.oxford.ac.uk Laboratory of AI and Computer Science (LIACC)

University of Porto

Porto Portugal

Researchers Pavel Brazdil, Alípio Jorge, Luís Torgo, João Gama

ILP Areas Learning from algorithm sketches, Modular approaches to learning, Theory refinement, Multiple predicate learning, Learning in multi-agent environments, Learning from multiple sources, Evaluation of inductive methods.

Description of Research One of the main concerns of LIACC is how to turn ILP systems more practicable so that they could be of help when developing logic programs. In one line of work we have examined how we could adapt the ideas of structured programming to ILP [4]. Following the structured methodology, a complex task is split up into subtasks. Each subtask requires a specification of a particular predicate, or a group of predicates (= module), and generation of the required definition with the help of inductive methods. Our concerns are thus similar to those of in the area of multiple predicate learning (particularly intensional approaches).

In another line of work we have explored the possibility of giving the system some information about how the given problem could be solved. This information appears in the form of an algorithm sketch, which is an incomplete and somewhat vague representation of the computation, related to a particular example. In [1] we describe which sketches are admissible, give details of the learning algorithm. It employs a top-down covering method, but in addition exploits the information contained in the sketch. The implemented system is called SKIL1. We are planning to extend this system to multiple predicate (and modular) learning discussed earlier.

LIACC has been concerned with the problem that can arise in practice. Different subprograms may sometimes use a somewhat different predicate vocabulary. The composition of the final program requires then that all vocabulary differences get resolved. The method can itself emply induction, as is demonstrated in [6, 7]. The problem of different and/or incompatible vocabulary typically arise when subprograms get generated by different ILP systems (or agents). In this context the final program may consist of different parts, each generated by one particular system. In addition, we may need also certain interface theories which enable to relate the terms generated in different contexts.

Finally LIACC has also been concerned with evaluation of different learning algorithms. The aim is to obtain a system capable of examining a given dataset and giving a recommendation concerning the suitability of different learning methods. Although most of our previous effort was oriented towards evaluation of different classification algorithms [2], we are planning to extend this work to cater for ILP datasets/systems.

Recent Publications

[1] P. Brazdil, A. Jorge. Learning by refining algorithm sketches. Proc. European Conf. on Artificial Intelligence, ECAI-94, Amsterdam. J. Wiley, 1994.

[2] P. Brazdil, J. Gama, B. Henery. Characterizing the applicability of classification algorithms using meta-level learning. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[3] P. Brazdil, A. Jorge. Exploiting algorithm sketches in ILP. Proceedings of The Third International Workshop on Inductive Logic Programming, ILP’93, Jozef Stefan Institute, Ljubljana, Slovenia, 1993.

[4] P. Brazdil, A. Jorge. Modular approach to ILP: Learning from interactions between modules. Proceedings of the Workshop on Logical Approaches to Machine Learning, Vienna, Austria, 1992.

[5] P. Brazdil. Approaches to Inductive Logic Programming. In V. Marik, O. Stepankova, R. Trappl (eds.) Advanced Topics in AI, Lecture Notes in Artificial Intelligence, Vol. 617, 139–160, Springer-Verlag, 1992.

[6] P. Brazdil, S. Muggleton. Learning to relate terms in multiple agent environment. Proc. of European Working Session on Learning, EWSL-91, Lecture Notes in Computer Science, Vol. 482. Springer-Verlag, 1991.

[7] P. Brazdil. Learning in multi-agent environments. Proceedings of Second Workshop on Algorithmic Learning Theory. OHMSHA, 1991.

Contact Person Pavel Brazdil LIACC University of Porto Rua Campo Alegre, 823 4100 Porto Portugal Phone: +351 2 600 1672 Fax: +351 2 600 3654 E-mail: pbrazdil@ncc.up.pt Czech Technical University (CTU) Faculty of Electrical Engineering Department of Control Engineering

Prague

Czech Republic

Researchers Olga Stepankova, Vladimir Marik, Jiri Lazansky, Lubos Popelinsky, Jiri Hejsek.

ILP Areas Transformation of logic programs, Knowledge discovery in databases, Inductive identification of technical systems.

Description of Research Transformations [3] and synthesis of logic programs [1, 2] have been studied by the Czech LP community during the last decade. Only recently, we have realised that example guided folding and predicate invention fit well into the ILP framework. An ILP system for efficiency improving transformations of logic programs is currently under development.

Being very recent in the ILP comunity, the Czech ILP group is gathering first on-hand experience with available ILP systems. Special attention is devoted to those approaches which might prove useful for identification of technical systems (data-dependency discovery, induction of qualitative laws from exemples of behaviour). In order to support this goal, there are being reimplemented some modifications of known ILP algorithms, e.g. CLINT, grammar induction. The first results should be reported before July ’94. Possible interaction with database community is examined.

Recent Publications

[1] L. Popelinsky. Towards synthesis of nearly pure Prolog programs. Proceedings of LOP-STR’91, Manchester, 1991.

[2] L. Popelinsky. Interactive synthesis of logic programs. Proceedings of LOPSTR’93, 1993.

[3] O. Stepankova, P. Stepanek. Transformations of logic programs. Journal of Logic Programming 1, 305-318, 1984.

Contact Person Olga Stepankova Department of Control Engineering, FEL Technicka 2 166 27 Prague 6 Czech Republic Phone: +42 2 293107 Fax: +42 2 290159 E-mail: {step}@lab.felk.cvut.cz German National Research Center for Computer Science (GMD)

Artificial Intelligence Research Division (I3.KI)

Sankt Augustin Germany

Researchers Werner Emde, Jörg-Uwe Kietz, Edgar Sommer, Stefan Wrobel, Roman Englert, Markus Lübbe, Katharina Morik (consultant).

ILP Areas Concept formation, Conceptual clustering, Declarative bias, Knowledge acquisition, PAClearnability, Representation and inference, Theory restructuring, Theory revision.

Description of Research

The research of the Machine Learning group at GMD covers a broad range of topics from theory of ILP to applications of ILP. The group developed Mobal, a system for building, validating, and maintaining operational models of application domains [6]. It integrates a manual knowledge acquisition and inspection environment, a powerful inference engine, induction programs for automated knowledge acquisition, a concept formation tool [10] and a knowledge revision tool [9]. In the current release 3.0, Mobal can also be seen as an ILP toolbox, since the external tool facility allows foreign ILP induction algorithms to be coupled with Mobal and used within Mobal’s knowledge representation and inspection environment. The publicly available release^{1} of Mobal includes interfaces to Golem (developed at the ILPNet-node Oxford), Grdt (developed at the ILPNet-node Dortmund) and Foil (developed at Univ. of Sydney). The external tool concept has also been used to integrate GMD’s own algorithms Incy [7], Link [8] and Cola [1]. Mobal has been used to model various real-world domains.

Another system developed at GMD is Kluster. This system is capable of learning a concept structure in the framework of term subsumption formalisms [4]. The work on theoretical issues of ILP has lead to several proofs concerning the PAC-learnability of restricted classes of logic programs [3, 2, 5].

Current work in theory revision hinges on the identification and resolution of contradictions. Based on the notion of minimal base revision, means for controlling the choice among minimal revisions are being investigated. Future research will go in the direction of representation change and theory restructuring. We will investigate means of improving the structure of a theory, for instance to make it more coherent or more efficient. This work is to progress in two steps: in the first, means of performing user-specified transformations of a theory will be investigated, culminating in the implementation of methods for manual theory transformation. In the second step, criteria for automatic restructuring of first-order theories will be developed and implemented.

Recent Publications

[1] W. Emde. Inductive learning of characteristic concept descriptions from small sets of classified examples. In F. Bergadano, L. De Raedt (eds.) Proc. Seventh European Conference on Machine Learning, ECML-94. Springer-Verlag, 1994. Also as Arbeitspapiere der GMD No. 821.

1GMD grants a cost-free license to use Mobal for academic purposes. The system can be obtained from ftp.gmd.de, directory /GMD/mlt/Mobal.

[2] J.-U. Kietz. A comparative study of structural most specific generalizations used in machine learning. Proc. of 3th Inductive Logic Programming Workshop, ILP-93, 149– 164, 1993. Also as Arbeitspapiere der GMD No. 667.

[3] J.-U. Kietz. Some lower bounds for the computational complexity of inductive logic programming. Proc. Sixth European Conference on Machine Learning, ECML-93, 115– 123. Springer-Verlag, 1993. Also as Arbeitspapiere der GMD No. 718.

[4] J.-U. Kietz, K. Morik. A polynomial approach to the constructive induction of structural knowledge. Machine Learning 14, 193–217, 1994.

[5] J.-U. Kietz, S. Džeroski. Inductive logic programming and learability. SIGART Bulletin 5 (1), 22-32, 1994.

[6] K. Morik, S. Wrobel, J.-U. Kietz, W. Emde. Knowledge Acquisition and Machine Learning - Theory, Methods, and Applications. Academic Press, London, 1993.

[7] E. Sommer. Cooperation of data-driven and model-based methods for relational learning. In R.S. Michalski, G. Tecuci (eds.) Second International Workshop on Multistrategy Learning, Harpers Ferry, West Virginia, USA, 1993.

[8] E. Sommer. Learning relations without closing the world. In F. Bergadano, L. De Raedt (eds.) Proc. Seventh European Conference on Machine Learning, ECML-94. Springer-Verlag, 1994.

[9] S. Wrobel. On the proper definition of minimality in specialization and theory revision. Proc. Sixth European Conference on Machine Learning, ECML-93, 65–82. Springer-Verlag, 1993. Also as Arbeitspapiere der GMD No. 730.

[10] S. Wrobel. Concept formation during interactive theory revision. Machine Learning 14, 169–191, 1994.

Contact Person Stefan Wrobel GMD (German National Research Center for Computer Science) Artificial Intelligence Research Division (I3.KI) Schloss Birlinghoven D-53754 Sankt Augustin Germany Phone: ++49 (2241) 14-1 Fax: ++49 (2241) 14-2072 E-mail: stefan.wrobel@gmd.de Institute of Informatics, Bulgarian Academy of Sciences (IINF)

Artificial Intelligence Department

Sofia Bulgaria

Researchers Zdravko Markov, Genady Arge, Rositza Shkodrova.

ILP Areas Case-based learning, Multistrategy learning, Theory revision.

Description of Research The research on ILP of the AI department has begun a few years ago, when we were developing the Net-Clause Language (NCL) [1, 5]. NCL is a distributed logic programming language, based on data-driven computation and spreading activation. Besides the basic logic programming features of NCL, it provides a built-in mechanism for term generalization [3]. The latter have been used for implementing bottom-up (specific-to-general) inductive algorithms in relational domains [2, 4]. NCL integrates various computational mechanisms, such as standard Prolog, bottom-up execution of logic programs, spreading activation (marker passing) and some connectionist features, which makes it a powerful workbench for experimenting with various ILP algorithms. (NCL is available by anonymous ftp from the University of Georgia AI archive, ai.uga.edu, directory ai.misc.)

The current work is concentrated on approaches to combining inductive, deductive and case-based learning. The basic idea is to use a ground theory as a set of cases and applying a proper similarity measure to classify instances of the target predicate directly, without building a relational definition of the predicate. This is a kind of dynamic induction in a sense that it takes place basically during the process of classification of new instances. The approach also allows to derive clauses for the target predicate, which will serve as explanations of the classifications done by the system.

Recently, we have been developing a theory refinement system based on case-based reasoning [6]. The system uses pre-classified examples (cases) in order to correct and complete the knowledge base of a rule-based system. Each case is attached to a rule as exceptional, typical or non-typical instance, and further used for classification of new instances by using similarity measures. The approach is developed for the propositional case (attribute-value logic), however we are considering the possibilities to extended it to first order predicates.

Recent Publications

[1] Z. Markov, Ch. Dichev. The Net-Clause Language — A tool for data-driven inference. In J. van Eijck (ed.) Logics in AI, Proceedings of European Workshop JELIA’90, Lecture Notes in Computer Science, Vol. 478, 366–385, Springer-Verlag, 1991.

[2] Z. Markov. An approach to data-driven learning. Proceedings of the International Workshop on Fundamentals of Artificial Intelligence Research (FAIR’91), September 8–12, 1991, Smolenice, Czechoslovakia, Lecture Notes in Computer Science, Vol. 535, 127–140, Springer-Verlag, 1991.

[3] Z. Markov. An approach to concept learning based on term generalization. Proceedings of the 9th International Machine Learning Conference (ML92), 310–315, Aberdeen, Scotland, July 1–3, 1992.

[4] Z. Markov. Inductive inference in networks of relations. Proceedings of the Third International Workshop on Inductive Logic Programming (ILP’93), 256–277, Bled, Slovenia, April 1–3, 1993.

[5] Z. Markov, L. Sinapova. A framework for network modeling. Computers and Artificial Intelligence, Slovak Academic Press, Bratislava (to appear).

[6] G. Agre, Improving rule-based system by using its own problem solving experience. Technical Report, Institute of Informatics, Sofia, 1993.

Contact Person Zdravko Markov Institute of Informatics, Bulgarian Academy of Sciences Acad. G. Bonchev St. Block 29A 1113 Sofia Bulgaria Phone: +359 2 707586 Fax: +359 2 720166 Email: markov@iinf.bg

University of Stockholm (STO)

Department of Computer and Systems Sciences

Stockholm Sweden

Researchers Carl Gustaf Jansson, Henrik Bostrom, Peter Idestam-Almquist, Xiaohong Jin, Lars Asker, Bassam Michel El-Khouri, Fredrik Kilander, Harald Kjellin, Pierre Wijkman, Asa Rudstrom, Christer Samuelsson, Mats Danielsson.

ILP Areas Theory revision, Inverse resolution.

Description of Research The work of the Stockholm Machine Learning Group includes theorethical work emphasizing techniques based upon logic and statistics, realistic applications where learning mechanisms are inevitable, as well as studies of the cognitive relevance of learning mechanisms and their role in an interactive man/machine problemsolving process.

With respect to logical approaches to machine learning we are primarily interested in theory revision in the sense of modification of several related concepts (predicates) in order to make the theory fit new cases (clauses). Given an imperfect theory in Horn clause form, a system designer has the goal to enhance the theory from a logical as well as a performance perspective.

Imperfection from a logical point of view is basically due to incompleteness or inconsistency. By incompleteness is meant that a true theorem cannot be proved, and by inconsistency that a false theorem can be proved. As positive examples corresponds to true theorems, these can aid the revision of the theory to remedy incompleteness, basically by generalizing predicate definitions. As negative examples correspond to false theorems, these can aid the revision of the theory to remedy inconsistency, basically by specializing predicate definitions. Imperfection from a performance oriented point of view is basically due to the intractability of the theory or the non-optimality of the theory. One concrete example of our work is a novel approach to inverse resolution which combines top down and bottom up approaches [5, 6] and aiming at an inductively complete system.

Recent Publications

[1] H. Bostrom. Eliminating redundancy in explanation-based learning. Proceedings of the Ninth International Conference on Machine Learning. Morgan Kaufmann, 1992.

[2] H. Bostrom. Improving example-guided unfolding. Proceedings of the European Conference on Machine Learning. Morgan Kaufmann, 1993.

[3] H. Bostrom. Explanation-based generalization if multiple training examples. Proceedings of the Third International Workshop on Knowledge Compilation and Speedup Learning. Amherst MA, 1993.

[4] H. Bostrom. Explanation-based transformation of logic programs. PhD thesis, Department of Computer and Systems Sciences, Stockholm University and Royal Institute of Technology, 1993.

[5] P. Idestam-Almquist. Learning missing clauses by inverse resolution. Proceedings of the International Conference on Fifth Generation Computer Systems 1992. Ohmsha

Publishers, Tokyo, 1992.

[6] P. Idestam-Almquist. A method to integrate top down and bottom up induction for augmentation of incomplete theories. Proceedings of 1992 IEEE International Conference on Computer Systems and Software Engineering. IEEE Computer Society Press, Los Alamitos, California, 1992.

[7] P. Idestam-Almquist. Generalization of clauses. PhD thesis, Department of Computer and Systems Sciences, Stockholm University and Royal Institute of Technology, 1993.

[8] P. Idestam-Almquist. Generalization under implication by recursive anti-unification. Proceedings of the Tenth International Conference on Machine Learning. Morgan Kaufmann, 1993.

[9] P. Idestam-Almquist. Generalization under implication by using or-introduction. Proceedings of the European Conference on Machine Learning, ECML-93. Springer-Verlag, 1993.

[10] P. Idestam-Almquist. Generalization under implication: Expansion of clauses for indirect roots. Scandinavian Conference on Artificial Intelligence, SCAI-93. IOS Press, 1993.

[11] P. Idestam-Almquist. Recursive anti-unification. In S.Muggleton (ed.) Proceedings of the Third International Workshop on Inductive Logic Programming. J. Stefan Institute, Ljubljana, Slovenia, 1993.

Contact Person Carl Gustaf Jansson Department of Computer and Systems Sciences Kistagängen 16 S - 164 40 Stockholm Sweden Phone: +46 8 161605 Fax: +46 8 7039025 E-mail: calle@dsv.su.se Universität Stuttgart (STU)

Institut für Informatik Stuttgart Germany

Researchers Irene Stahl, Birgit Tausend.

ILP Areas Predicate Invention, Declarative bias.

Description of Research The research of the Stuttgart’s Machine Learning Group started with work on inverse resolution (IR) [13, 14] and analogical reasoning [1]. Both areas of research have been pursued further, the first with emphasis on the properties of IR-operators [2] and techniques to invent new predicates [15], the second leading to the idea of an abstract representation of the hypothesis space [9]. In [4, 5] concepts of both have been integrated in an efficient ILP system.

The two main foci of recent research in ILP at Stuttgart are predicate invention (PI) and frameworks for representing bias. PI is a method for recovering from an overly strong bias by extending the vocabulary of the hypothesis language. If the learning task fails in the given biased target language, new predicates might be introduced to shift the bias. A survey of approaches to PI is given in [6]. The work in Stuttgart concentrates on the exploration of decision criteria for PI and its usefulness as bias shift operation [7, 8]. Currently, methods for determining the structure and definition of the necessary new predicates are investigated and developed.

All these topics depend strongly on the language bias the new predicates shall weaken. The unifying framework for declaratively representing biases developed in Stuttgart [9, 11, 12] helps to investigate PI-methods for different language restrictions. Furthermore, this framework allows to describe generalisation and specialisation operators with respect to the bias, and to formulate bias shift operations [10]. The unifying representation facilitates the comparison of biases commonly used in ILP, and helps to classify systems according to the strength of their bias.

Recent Publications

[1] S. Bell, B. Tausend. Analogical reasoning for logic programming. Proceedings of the International Workshop on ILP, 1991.

[2] B. Jung. On inverting generality relations. Proceedings of the 3rd International Workshop on ILP, J. Stefan Institute, Technical Report IJS-DP-6707,1993.

[3] U. Knoll, G. Nakhaeizadeh, B. Tausend. Cost-sensitive pruning of decision trees. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[4] I. Stahl, B. Tausend, R. Wirth. General-to-specific learning of Horn clauses from positive examples. Proceedings of the CompEuro92, the Hague, the Netherlands, 1992.

[5] I. Stahl, B. Tausend, R. Wirth. Two methods for improving inductive logic programming systems. Proc. European Conf. on Machine Learning, ECML-93, Vienna. Springer-Verlag, 1993.

[6] I. Stahl. Predicate invention in ILP – An Overview. Proc. European Conf. on Machine Learning, ECML-93, Vienna. Springer-Verlag, 1993.

[7] I. Stahl. Properties of inductive logic programming in function-free Horn logic. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[8] I. Stahl. On the utility of predicate invention in inductive logic programming. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[9] B. Tausend. Using and adapting schemes for the induction of Horn clauses. Proc. of the ECAI Workshop Logical Approaches to Machine Learning, Vienna, 1992.

[10] B. Tausend. A unifying representation for language restrictions. Proceedings of the 3rd International Workshop on ILP, J. Stefan Institute, Technical Report IJS-DP-6707, 1993.

[11] B. Tausend. Biases and their effects in inductive logic programming. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[12] B. Tausend. Representing biases for inductive logic programming. Proc. European Conf. on Machine Learning, ECML-94, Catania. Springer-Verlag, 1994.

[13] R. Wirth. Learning by failure to prove. Proceedings of the Third European Working Session on Learning, 1988.

[14] R. Wirth. Completing logic programs by inverse resolution. Proceedings of the Fourth European Working Session on Learning, 1989.

[15] R. Wirth, P. O’Rorke. Constraints on predicate invention. In Proceedings of the 8th International Workshop on ML, Morgan Kaufmann, 1991.

Contact Persons Irene Stahl, Birgit Tausend Institut für Informatik Universität Stuttgart Breitwiesenstr. 20-22 D-70565 Stuttgart Germany Phone: +49-711-7816435 Fax: +49-711-7801045 E-mail: {stahl, tausend}@informatik.uni-stuttgart.de

Attila Jozsef Institute (ARJ)

Research Group on the Theory of Automata

Hungarian Academy of Sciences

Szeged Hungary

Researchers Zoltán Alexin, József Dombi, Tibor Gyimóthy, Tamás Horváth, György Turán.

ILP Areas ILP theory, Theory revision, Declarative bias.

Description of Research One part of the research done at ARJ concerns the PAC learnability for learning classes of logic programs. It is one of the basic results of computational learning theory that the Vapnik-Chervonenkis dimension of a concept class provides both a lower and an upper bound to its learnig complexity in the PAC model of Valiant. The lower bound is extended to the more powerful model where besides drawing random examples, the learner can also ask arbitrary Boolean queries and equivalence queries [6].

The second research topic concerns theory revision. An interactive debugging method IDT (Interactive Diagnosis and Testing) has been developed for logic programs [3]. The basic idea of the IDT method is that by using the test database prepared by the Category Partition Testing Method the number of user interactions can be reduced. Combining the IDT with program slicing a further improvment for bug-localization can be achived [5]. This approach applies well-known techniques of attribute grammars to analyze the directed data-flow within a program, thus making it possible to reorganize the search space of the debugging algorithm to concentrate on the suspect part of the program. This integrated method can be used in the testing, debugging and learning of logic programs [4].

Research at ARJ involves also the study of learning of attribute grammars. Attribute Grammars can be applied on several fields of Artificial Intelligence (e.g. syntactic pattern recognition [2], natural language processing [1]). There is a strong relationship between attribute grammars and logic programming. The possibilities to apply ILP learning methods to infer AG’s for AI applications is being investigated.

Recent Publications

[1] Z. Alexin, K. Fábricz, T. Gyimóthy, T. Horváth. Attribute grammar specification for natural language understnding interface. Proc. of Attribute Grammars and their Applications (WAGA), Paris, Lecture Notes in Computer Science, Vol. 461, Springer-Verlag, 1990.

[2] T. Gyimóthy, J. Tocki. Syntactic pattern recognition in the HLP/PAS systems. Acta Cybernetica 8 (1), 79–88, 1987.

[3] T. Horváth, T. Gyimóthy, Z. Alexin, F. Kocsis. Interactive diagnosis and testing of logic programs. Proc. of Symposium on Programming Languages and Software Tools, University of Tartu, Estonia, 1993.

[4] G. Kókai, Z. Alexin, F. Kocsis. IDT system and its application for learning Prolog programs. AIICSR’94, Bratislava, 1994 (submitted).

[5] J. Paakki, T. Gyimothy, T. Horvath. An integrated method for algorithmic debugging of logic programs (manuscript).

[6] Gy. Turán Lower bounds for PAC learning with queries. Proc. of the Workshop on Computational Learning Theory, 1993.

Contact Person Tibor Gyimóthy Research Group on the Theory of Automata Hungarian Academy of Science Aradi tèr 1 H-6720 Szeged Hungary Phone: +36 62 312 508 Fax: +36 62 312 508 E-mail: h42gyi@ella.hu Institute for Language Technology & Artificial Intelligence (ITK)

Tilburg University

Tilburg

the Netherlands

Researchers Peter Flach.

ILP Areas ILP theory, Induction of integrity constraints, Predicate invention.

Description of Research The work on ILP done at ITK concentrates on two main topics: a logical theory of inductive reasoning, and the discovery of regularities in data (weak induction). The first topic aims at providing a unifying framework for different kinds of induction, and at studying the relationships between them, and with other kinds of reasoning. The second topic is directed towards methods for inducing non-classification rules, such as integrity constraints. These two topics are closely related, since a unifying framework for weak induction and the classification-oriented notion of strong induction does not yet exist.

The logical theory of induction under development revolves around the notion of an inductive consequence relation. In [2] a number of useful properties of such a consequence relation is identified. In [5] a minimal set of properties of inductive consequence relations is identified. Consequently, strong and weak induction can be seen as special cases of this canonic type of induction. Current work aims at developing a model-theoretic account of inductive consequence relations.

The work on discovery of regularities in data started with a study of induction of attribute dependencies in relational databases [1]. In cooperation with the Jožef Stefan Institute the algorithm for inducing functional dependencies has been improved considerably [3]. Future work includes improving the multivalued dependency algorithm along the same lines. Building on this work, a prototype system called INDEX has been implemented, which restructures a knowledge base on the basis of induced attribute dependencies. Since the restructured knowledge base will contain predicates not present in the original knowledge base, this also resulted in a new approach to predicate invention through integrity constraints [4].

Recent Publications

[1] P. Flach. Inductive characterisation of database relations. In Z.W. Ras, M. Zemankova & M.L. Emrich (eds.) Proc. Methodologies for Intelligent Systems ISMIS’90, 371–378, North-Holland, Amsterdam, 1990. Full version appeared as ITK Research Report No. 23.

[2] P. Flach. A framework for Inductive Logic Programming. In S. Muggleton (ed.) Inductive Logic Programming, 193–211. Academic Press, London, 1992.

[3] I. Savnik, P. Flach. Bottom-up induction of functional dependencies from relations. In G. Piatetsky-Shapiro (ed.) Proc. AAAI’93 Workshop on Knowledge Discovery in Databases, 174–185, 1993.

[4] P. Flach. Predicate invention in inductive data engineering. In P. Brazdil (ed.) Proc.

European Conference on Machine Learning, ECML’93, Lecture Notes in Artificial Intelligence, Vol. 667, 83–94. Springer-Verlag, 1993.

[5] P. Flach. A model of inductive reasoning. In M. Masuch & L. Polos (eds.), Knowledge Representation and Reasoning under Uncertainty, Springer-Verlag, Berlin, 1994.

Contact Person Peter A. Flach Institute for Language Technology & Artificial Intelligence Tilburg University POBox 90153 5000 LE Tilburg the Netherlands Phone: +31 13 663119 Fax: +31 13 663069 E-mail: flach@kub.nl Universita‘ di Torino (TO) Dipartimento di informatica

Torino Italy

Researchers Francesco Bergadano, Daniele Gunetti, Gemma Cameirana, Umberto Trinchero, Stefano Brusotti, Nicola Olivetti.

ILP Areas ILP theory, Declarative bias, Theory revision.

Description of Research The research of the Torino’s ML group is concentrated on Declarative Bias, Theory revision and Theory. In the past few years, a lot of research was done on concept learning. More recently, attention has focused on the problem of declarative bias. A language based on clause sets has been developed, in order to specify in a simple and “logic programming oriented” way a bias for the ILP problem. This language has been used in the ILP learning system FILP [7], developed at the University of Torino. This system is able to learn logic programs from positive examples only, it can learn multiple predicates and does not need an extensionally complete set of examples of the target concept. Missing examples are queried to the user on the basis of those given initially. A similar approach has been also proposed for knowledge discovery in logic databases [1].

Another learning system, called TRACY, using clause sets as a language for specifying the bias, is under development at the University of Torino. TRACY is especially suitable for multiple predicate learning, theory revision and software engineering. It does not depend on the number and kind of given examples, and it is able to learn complete and consistent programs whenever they exist in the given hypothesis space. TRACY can start with an empty target theory or revise an existing one. The group in Torino is also working on the applications of ILP in software engineering, i.e. how using ILP techniques as an alternative approach to software development, testing, updating and reusing of logic programs [6, 2, 4]. The approach adopted in TRACY has also been used to show the difficulties of learning logic programs containing non declarative predicates [9].

More recent research is concerned with the formalization of the top-down approach to ILP in terms of inverse resolution as a deductive rule [8]. The research is showing that topdown methods can be seen as a special kind of theorem proving based on inverse resolution.

Recent Publications

[1] F. Bergadano. Inductive database relations. IEEE Trans. on Data and Knowledge Engineering 5 (6), 969–972, 1993.

[2] F. Bergadano. Test case generation by means of learning techniques. Proc. ACM SIGSOFT, Los Angeles, CA, 1993.

[3] F. Bergadano. The foundations of induction and machine learning. Minds and Machines 3, 31–51, 1993. Kluwer Academic Publishers.

[4] F. Bergadano, S. Brusotti, D. Gunetti, U. Trinchero. Inductive test case generation. Proc. Third Int. Workshop on Inductive Logic Programming, Bled, Slovenia, 1993.

[5] F. Bergadano, D. Gunetti. Functional inductive logic programming with queries to the user. In P. Brazdil (ed.) Proc. European Conference on Machine Learning, 323–328, Vienna, Austria, 1993. Springer-Verlag.

[6] F. Bergadano, D. Gunetti. Inductive synthesis of logic programs and inductive logic programming. Proc. Int. Workshop on Logic Program Synthesis and Transformation (LOPSTR-93), Leuven, Belgium, 1993. Springer-Verlag, Lecture Notes in Computer Science, Springer-Verlag.

[7] F. Bergadano, D. Gunetti. An interactive system to learn functional logic programs. Proc. 13th Int. Joint. Conf. on Artificial Intelligence, 1044–1049, Chambery, France, 1993. Morgan Kaufmann.

[8] F. Bergadano, D. Gunetti. Learning relations: Basing top-down methods on inverse resolution. In P. Torasso (ed.) Proc. Third Conf. of the Italian Association for Artificial Intelligence, 190–201, Torino, Italy, 1993. Springer-Verlag.

[9] F. Bergadano, D. Gunetti, U. Trinchero. The difficulties of learning logic programs with cut. Journal of Artificial Intelligence Research 1, 91–107, 1993. Morgan Kaufmann (to appear).

[10] A. Giordana, L. Saitta, F. Bergadano, F. Brancadori, D. Demarchi. ENIGMA: A system that learns diagnostic knowledge. IEEE Trans. on Knowledge and Data Engineering 5 (1), 15–28, 1993.

[11] L. Saitta, F. Bergadano. Pattern recognition and Valiant’s learning framework. IEEE Trans. on Pattern Analysis and Machine Intelligence, 15 (2), 145–154, 1993.

Contact Person Francesco Bergadano Dipartimento di Informatica Universita‘ di Torino Corso Svizzera 185 10149 - Torino Italy Phone: +39 11 7429216 Fax: +39 11 751603 E-mail: bergadan@di.unito.it Research Institute for Applied Knowledge-Processing (FAW)

Ulm Germany

Researchers Rüdiger Wirth.

ILP Areas Predicate invention, Applications of ILP.

Description of Research Research activities of FAW, mostly funded by research contracts from companies, cover a wide spectrum of applications of knowledge-based techniques to real world problems. The promotion of technology transfer from universities to companies is one of the most important tasks of FAW. One of the main problems addressed by most of the projects at FAW is how to provide knowledge in a form adequate for the problem at hand. Learning in various forms plays an important role in this task. In the context of ILP research FAW is investigating the integration of ILP techniques in knowledge-based systems solving to real world problems (e.g. [1]).

Rüdiger Wirth also contributes to the ESPRIT Basic Research Project 6020 “Inductive Logic Programming” as a consultant of the University of Stuttgart. His recent research activities include predicate invention [5], learning from positive examples only [3], and learning disjunctive definitions [2, 4].

Recent Publications

[1] M. Koegel. Aufbau einer Abstraktions-Hierarchie für strukturelle und funktionale Beschreibungen technischer Systeme (Constructing an abstraction hierarchy for structural and functional descriptions of technical devices), Diploma thesis, 1993 (in German).

[2] I. Stahl, B. Tausend, R. Wirth. Learning of disjunctive concepts via partitioning of the example set. Proc. Workshop on Logical Approaches to Machine Learning, European Conference on Artificial Intelligence, Vienna, 1992.

[3] I. Stahl, B. Tausend, R. Wirth. General-to-specific learning of Horn clauses from positive examples only. Proc. of IEEE 92 International Conference on Computer Systems and Software Engineering. the Hague, the Netherlands, 1992.

[4] I. Stahl, B. Tausend, R. Wirth. Two methods for improving inductive logic programming systems. Proc. European Conference on Machine Learning ECML-93, Vienna, Lecture Notes in Artificial Intelligence, Vol. 667. Springer-Verlag, 1993.

[5] R. Wirth, P. O’Rorke. Constraints for predicate invention. In S. Muggleton (ed.) Inductive Logic Programming. Academic Press, 1992.

Contact Person Rüdiger Wirth FAW Ulm P.O. Box 2060 D-89010 Ulm Germany Phone: +49 731 501 468 Fax: +49 731 501 999 E-mail: wirth@uni-ulm.de Austrian Research Institute for Artificial Intelligence (ARIAI)

Vienna Austria

Researchers Johannes Fürnkranz, Yousri El Fattah, Igor Mozetič, Bernhard Pfahringer, Gerhard Widmer.

ILP Areas Imperfect data, Multistrategy learning, Constructive induction.

Description of Research Our early ILP development is QuMAS, a system for semi-automatic construction and refinement of qualitative models [10]. The approach is based on a LP representation of a model at several levels of abstraction [9]. QuMAS integrates inductive learning from examples, location of incorrect and incomplete hypotheses in the model, and their incremental modification. We also defined a set of abstraction operators which map a complex, detailed model into a simpler, abstract one [11]. The algorithm which automatically abstracts a detailed model uses partial evaluation and term rewriting. In other pertinent work on modelling and diagnosis, explanation-based learning was used to improve the efficiency of diagnostic processes [6, 7, 8].

Another line of research related to ILP is concerned with knowledge-based relational learning algorithms. In [13], an incremental relational learner was presented that uses background knowledge to guide the induction process. Our current work in this area focuses on extending learning algorithms to be capable of using qualitative background knowledge [14] and on the integration of various relational learning algorithms (e.g., ML-Smart, Foil) with numeric, quantitative prediction methods [15, 16]. An application of special interest is the use of machine learning methods for music theory, e.g., [17].

In our research on constructive induction, we exploited the Minimum Description Length (MDL) principle as a powerful control heuristic [12]. The current version of the algorithm is based on a propositional version of Foil. We plan to adapt the general MDL approach to constructive induction in first-order logic.

Current research centrally located in the ILP area concentrates on pruning, a topic of a forthcoming Ph.D. thesis [5]. Pre-pruning has been common in the form of stopping criteria as used in Foil and mFoil. We have developed Fossil [1, 2], a new relational learning algorithm with a simple, but useful Cutoff stopping criterion. Post-pruning in the form of Reduced Error Pruning has proven a powerful, but inefficient method for noise handling with large example sets [4]. We have proposed several approaches that avoid some or all of the problems with pruning by combining [3] or integrating [4] pre- and post-pruning. Further research along these lines will include a direct comparison of the above algorithms along with a possible improvement of the latter method which currently is still subject to over-generalization in some domains.

Recent Publications

[1] J. Fürnkranz. Avoiding noise fitting in a Foil-like learning algorithm. Proc. IJCAI-93 Workshop on Inductive Logic Programming, Chambery, France, 1993.

[2] J. Fürnkranz. Fossil: A robust relational learner. Proc. 11th European Conf. on Machine Learning, ECML-94, 122–137, Catania. Springer-Verlag, 1994.

[3] J. Fürnkranz. Top-down pruning in relational learning. Proc. European Conf. on Artificial Intelligence, ECAI-94, Amsterdam. John Wiley & Sons, 1994.

[4] J. Fürnkranz, G. Widmer. Incremental reduced error pruning. Proc. 11th Intl. Conf. on Machine Learning, ML-94, Rutgers University, NJ, 1994.

[5] J. Fürnkranz. Pruning in inductive logic programming. Ph.D. Thesis, Univ. of Vienna, Austria (in preparation).

[6] Y. El Fattah, P. O’Rourke. Learning multiple fault diagnosis. Proc. 7th IEEE Conf. on AI Applications, 235–239. Los Alamitos, CA, 1991.

[7] Y. El Fattah, P. O’Rourke. Learning approximate diagnosis. Proc. 8th IEEE Conf. on AI Applications, 150–156, Los Alamitos, CA, 1992.

[8] Y. El Fattah, P. O’Rourke. Explanation-based learning for diagnosis. Machine Learning 13 (1), 35–70, 1993.

[9] I. Mozetič. The role of abstractions in learning qualitative models. Proc. 4th Intl. Workshop on Machine Learning, 242–255. Morgan Kaufmann, 1987.

[10] I. Mozetič. Learning of qualitative models. In Progress in Machine Learning, Proc. EWSL-87, 201–217, Sigma Press, Wilmslow, 1987.

[11] I. Mozetič, C. Holzbaur. Extending explanation-based generalization with abstraction operators. Proc. European Working Session on Learning, EWSL-91, 282–297. Springer-Verlag, 1991.

[12] B. Pfahringer. Controlling constructive induction in CiPF: An MDL approach. Proc. European Conf. on Machine Learning, ECML-94, 242–256, Catania. Springer-Verlag, 1994.

[13] G. Widmer. An incremental version of Bergadano & Giordana’s integrated learning strategy. Proc. European Working Session on Learning, EWSL-89. Pitman, London, 1989.

[14] G. Widmer. Learning with a qualitative domain theory by means of plausible explanations. In R. S. Michalski and G. Tecuci (eds.) Machine Learning: A Multistrategy Approach, Vol. IV. Morgan Kaufmann, 1993.

[15] G. Widmer. Plausible explanations and instance-based learning in mixed symbolic/numeric domains. Proc. 2nd Intl. Workshop on Multistrategy Learning, MSL-93, Harpers Ferry, W.VA., 1993.

[16] G. Widmer. Combining knowledge-based and instance-based learning to exploit qualitative knowledge. Informatica 17, Special Issue on Multistrategy Learning, 371–385, 1993.

[17] G. Widmer. Modeling the rational basis of musical expression. Computer Music Journal 18. The MIT Press, 1994 (in press).

Contact Person Igor Mozetič Austrian Research Institute for Artificial Intelligence (ARIAI) Schottengasse 3 A-1010 Vienna Austria Phone: +43 1 5336112 Fax: +43 1 5320652 E-mail: igor@ai.univie.ac.at