Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.     

Advantages of decision lists and implicit negatives in Inductive Logic Programming

This paper demonstrates the capabilities offoidl, an inductive logic programming (ILP) system whose distinguishing characteristics are the ability to produce first-order decision lists, the use of an output completeness assumption as a substitute for negative examples, and the use originally motivated by the problem of learning to generate the past tense of English verbs; however, this paper demonstrates its superior performance on two different sets of benchmark ILP problems. Tests on the finite element mesh design problem show thatfoidl’s decision lists enable it to produce generally more accurate results than a range of methods previously applied to this problem. Tests with a selection of list-processing problems from Bratko’s introductory Prolog text demonstrate that the combination of implicit negatives and intensionality allowfoidl to learn correct programs from far fewer examples thanfoil. This research was supported by a fellowship from AT&T awarded to the first author and by the National Science Foundation under grant IRI-9310819. Mary Elaine Califf: She is currently pursuing her doctorate in Computer Science at the University of Texas at Austin where she is supported by a fellowship from AT&T. Her research interests include natural language understanding, particularly using machine learning methods to build practical natural language understanding systems such as information extraction systems, and inductive logic programming. Raymond Joseph Mooney: He is an Associate Professor of Computer Sciences at the University of Texas at Austin. He recerived his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1988. His current research interests include applying machine to natural language understanding, inductive logic programming, knowledge-base and theory refinement, learning for planning, and learning for recommender systems. He serves on the editorial boards of the journalNew Generation Computing, theMachine Learning journal, theJournal of Artificial Intelligence Research, and the journalApplied Intelligence.     

归纳逻辑程序设计综述

归纳逻辑程序设计是由机器学习与逻辑程序设计交叉所形成的一个研究领域,是机器学习的前沿研究课题。该文首先从归纳逻辑程序设计的问题背景、类型划分和搜索程序子句三个方面介绍了归纳逻辑程序设计系统的概貌;然后结合实验室的相关研究工作,回顾了归纳逻辑程序设计研究的发展;之后介绍了归纳逻辑程序设计领域中需要深入研究的若干问题,并提出了新的解决思路;最后是总结,以引起读者对归纳逻辑程序设计领域研究的进一步关注。     

归纳逻辑程序设计方法综述

归纳逻辑程序设计是机器学习与逻辑程序设计交叉所形成的一个研究领域,克服了传统机器学习方法的两个主要限制：即知识表示的限制和背景知识利用的限制,成为机器学习的前沿研究课题。首先从归纳逻辑程序设计的产生背景、定义、应用领域及问题背景介绍了归纳逻辑程序设计系统的概貌,对归纳逻辑程序设计方法的研究现状进行了总结和分析,最后探讨了该领域的进一步的研究方向。     

Well-founded semantics and stratification for ordered logic programs

This paper present an extension of traditional logic programming, called ordered logic (OL) programming, to support classical negation as well as constructs from the object-oriented paradigm. In particular, such an extension allows to cope with the notions of object, multiple inheritance and non-monotonic reasoning. The contribution of the work is mainly twofold. First, a rich wellfounded semantics for ordered logic programs is defined. Second, an efficient method for the well-founded model computation of a meaningful class of ordered logic programs, called stratified programs, is provided.     

Pruning Algorithms for Rule Learning

Pre-pruning and Post-pruning are two standard techniques for handling noise in decision tree learning. Pre-pruning deals with noise during learning, while post-pruning addresses this problem after an overfitting theory has been learned. We first review several adaptations of pre- and post-pruning techniques for separate-and-conquer rule learning algorithms and discuss some fundamental problems. The primary goal of this paper is to show how to solve these problems with two new algorithms that combine and integrate pre- and post-pruning.     

Inference of abduction theories for handling incompleteness in first-order learning

In real-life domains, learning systems often have to deal with various kinds of imperfections in data such as noise, incompleteness and inexactness. This problem seriously affects the knowledge discovery process, specifically in the case of traditional Machine Learning approaches that exploit simple or constrained knowledge representations and are based on single inference mechanisms. Indeed, this limits their capability of discovering fundamental knowledge in those situations. In order to broaden the investigation and the applicability of machine learning schemes in such particular situations, it is necessary to move on to more expressive representations which require more complex inference mechanisms. However, the applicability of such new and complex inference mechanisms, such as abductive reasoning, strongly relies on a deep background knowledge about the specific application domain. This work aims at automatically discovering the meta-knowledge needed to abduction inference strategy to complete the incoming information in order to handle cases of missing knowledge. Floriana Esposito received the Laurea degree in electronic Physics from the University of Bari, Italy, in 1970. Since 1994 is Full Professor of Computer Science at the University of Bari and Dean of the Faculty of Computer Science from 1997 to 2002. She founded and chairs the Laboratory for Knowledge Acquisition and Machine Learning of the Department of Computer Science. Her research activity started in the field of numerical models and statistical pattern recognition. Then her interests moved to the field of Artificial Intelligence and Machine Learning. The current research concerns the logical and algebraic foundations of numerical and symbolic methods in machine learning with the aim of the integration, the computational models of incremental and multistrategy learning, the revision of logical theories, the knowledge discovery in data bases. Application include document classification and understanding, content based document retrieval, map interpretation and Semantic Web. She is author of more than 270 scientific papers and is in the scientific committees of many international scientific Conferences in the field of Artificial Intelligence and Machine Learning. She co-chaired ICML96, MSL98, ECML-PKDD 2003, IEA-AIE 2005, ISMIS 2006. Stefano Ferilli was born in 1972. After receiving his Laurea degree in Information Science in 1996, he got a Ph.D. in Computer Science at the University of Bari in 2001. Since 2002 he is an Assistant Professor at the Department of Computer Science of the University of Bari. His research interests are centered on Logic and Algebraic Foundations of Machine Learning, Inductive Logic Programming, Theory Revision, Multi-Strategy Learning, Knowledge Representation, Electronic Document Processing and Digital Libraries. He participated in various National and European (ESPRIT and IST) projects concerning these topics, and is a (co-)author of more than 80 papers published on National and International journals, books and conferences/workshops proceedings. Teresa M.A. Basile got the Laurea degree in Computer Science at the University of Bari, Italy (2001). In March 2005 she discussed a Ph.D. thesis in Computer Science at the University of Bari titled “A Multistrategy Framework for First-Order Rules Learning.” Since April 2005, she is a research at the Computer Science Department of the University of Bari working on methods and techniques of machine learning for the Semantic Web. Her research interests concern the investigation of symbolic machine learning techniques, in particular of the cooperation of different inferences strategies in an incremental learning framework, and their application to document classification and understanding based on their semantic. She is author of about 40 papers published on National and International journals and conferences/workshops proceedings and was/is involved in various National and European projects. Nicola Di Mauro got the Laurea degree in Computer Science at the University of Bari, Italy. From 2001 he went on making research on machine learning in the Knowledge Acquisition and Machine Learning Laboratory (LACAM) at the Department of Computer Science, University of Bari. In March 2005 he discussed a Ph.D. thesis in Computer Science at the University of Bari titled “First Order Incremental Theory Refinement” which faces the problem of Incremental Learning in ILP. Since January 2005, he is an assistant professor at the Department of Computer Science, University of Bari. His research activities concern Inductive Logic Programming (ILP), Theory Revision and Incremental Learning, Multistrategy Learning, with application to Automatic Document Processing. On such topics HE is author of about 40 scientific papers accepted for presentation and publication on international and national journals and conference proceedings. He took part to the European projects 6th FP IP-507173 VIKEF (Virtual Information and Knowledge Environment Framework) and IST-1999-20882 COLLATE (Collaboratory for Annotation, Indexing and Retrieval of Digitized Historical Archive Materials), and to various national projects co-funded by the Italian Ministry for the University and Scientific Research.     

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

辩论的逻辑模型研究综述

辩论的逻辑模型是哲学、逻辑学和人工智能等多个领域的研究课题,在非单调推理、法律推理、决策支持和多Agent交互等领域有广泛应用。文中首先简要阐述辩论及辩论模型的基本概念。然后从对辩论建模和用辩论建模两个方面对目前的研究进行总结,分析现有的有影响的辩论模型特点及其存在的问题。最后,指出今后的研究方向和发展趋势。     

On the complexity of some inductive logic programming problems

The bounded ILP-consistency problem for function-free Horn clauses is described as follows. Given at setE ⁺ andE ^? of function-free ground Horn clauses and an integerk polynomial inE ⁺∪E ^?, does there exist a function-free Horn clauseC with no more thank literals such thatC subsumes each element inE ⁺ andC does not subsume any element inE ^?? It is shown that this problem is Σ ₂ ^P complete. We derive some related results on the complexity of ILP and discuss the usefulness of such complexity results.     

模糊决策树算法与清晰决策树算法的比较研究

ID3算法是一种典型的决策树归纳算法,这种算法在假定示例的属性值和分类值是确定的前提下,使用信息熵作为启发式建立一棵清晰的决策树。针对现实世界中存在的不确定性,人们提出了另一种决策树归纳算法,即模糊决策树算法,它是清晰决策树算法的一种推广。这两种算法在实际应用中各有自己的优劣之处,针对一个具体问题的知识获取过程,选取哪一种算法目前还没有一个较明确的依据。该文从5个方面对这两种算法进行了详细的比较,指出了属性为连续值时这两种算法的异同及优缺点,其目的是在为解决具体问题时怎样选择这两种算法提供一些有用的线索。     

A new deductive approach to planning

We introduce a new deductive approach to planning which is based on Horn clauses. Plans as well as situations are represented as terms and, thus, are first-class objects. We do neither need frame axioms nor state-literals. The only rule of inference is the SLDE-resolution rule, i.e. SLD-resolution, where the traditional unification algorithm has been replaced by anE-unification procedure. We exemplify the properties of our method such as forward and backward reasoning, plan checking, and the integration of general theories. Finally, we present the calculus and show that it is sound and complete. An earlier version of this paper was presented at the German Workshop on Artificial Intelligence, 1989.     

The Appropriateness of Predicate Invention as Bias Shift Operation in ILP

The task of predicate invention in Inductive Logic Programming is to extend the hypothesis language with new predicates if the vocabulary given initially is insufficient for the learning task. However, whether predicate invention really helps to make learning succeed in the extended language depends on the language bias currently employed.In this paper, we investigate for which commonly employed language biases predicate invention is an appropriate shift operation. We prove that for some restricted languages predicate invention does not help when the learning task fails and we characterize the languages for which predicate invention is useful. We investigate the decidability of the bias shift problem for these languages and discuss the capabilities of predicate invention as a bias shift operation.     

The Multi-agent Learning Model Based on Dynamic Fuzzy Logic

Machine Learning is one of the key problems of Artificial Intelligence, and the agent learning has become an important branch of machine learning. One of the main characters of intelligent agent is that it can adapt to the unknown environment. The ability to learn is the key property of agent. Because the learning act of agent is dynamic and fuzzy, this paper uses the conception of Dynamic Fuzzy Logic （DFL）tl]. Based on DFL, this paper first presents two single-agent learning algorithms, namely, single-agent leaning algorithm based on DFL with immediate reward and single-agent learning algorithm based on DFL with mediate reward. Then the paper gives a multi-agent learning model based on DFL, namely a multi-agent learning model planned on a whole. Furthermore, this paper validates that the model is useful by an example.     

基于论辩的Agent非单调推理

现有的Agent信念修正、慎思、手段-目的推理等理论和方法大多基于经典一阶逻辑,对不完全的、不一致的知识,缺乏有效的处理机制。基于论辩的Agent非单调推理(包括认识推理和实践推理)理论和方法有望弥补这个不足。不过,作为一个新的研究方向,其基本概念、理论、方法及存在的关键性问题尚有待于澄清和梳理。文中首先介绍论辩的基本概念。在此基础上,分析基于论辩的Agent非单调推理的最新研究进展。最后,讨论存在的关键性问题并指出可能的研究方向。     

Bottom-Up Induction of Feature Terms

The aim of relational learning is to develop methods for the induction of hypotheses in representation formalisms that are more expressive than attribute-value representation. Most work on relational learning has been focused on induction in subsets of first order logic like Horn clauses. In this paper we introduce the representation formalism based on feature terms and we introduce the corresponding notions of subsumption and anti-unification. Then we explain INDIE, a heuristic bottom-up learning method that induces class hypotheses, in the form of feature terms, from positive and negative examples. The biases used in INDIE while searching the hypothesis space are explained while describing INDIE's algorithms. The representational bias of INDIE can be summarised in that it makes an intensive use of sorts and sort hierarchy, and in that it does not use negation but focuses on detecting path equalities. We show the results of INDIE in some classical relational datasets showing that it's able to find hypotheses at a level comparable to the original ones. The differences between INDIE's hypotheses and those of the other systems are explained by the bias in searching the hypothesis space and on the representational bias of the hypothesis language of each system.