Fast relational learning using bottom clause propositionalization with artificial neural networks

Relational learning can be described as the task of learning first-order logic rules from examples. It has enabled a number of new machine learning applications, e.g. graph mining and link analysis. Inductive Logic Programming (ILP) performs relational learning either directly by manipulating first-order rules or through propositionalization, which translates the relational task into an attribute-value learning task by representing subsets of relations as features. In this paper, we introduce a fast method and system for relational learning based on a novel propositionalization called Bottom Clause Propositionalization (BCP). Bottom clauses are boundaries in the hypothesis search space used by ILP systems Progol and Aleph. Bottom clauses carry semantic meaning and can be mapped directly onto numerical vectors, simplifying the feature extraction process. We have integrated BCP with a well-known neural-symbolic system, C-IL²P, to perform learning from numerical vectors. C-IL²P uses background knowledge in the form of propositional logic programs to build a neural network. The integrated system, which we call CILP++, handles first-order logic knowledge and is available for download from Sourceforge. We have evaluated CILP++ on seven ILP datasets, comparing results with Aleph and a well-known propositionalization method, RSD. The results show that CILP++ can achieve accuracy comparable to Aleph, while being generally faster, BCP achieved statistically significant improvement in accuracy in comparison with RSD when running with a neural network, but BCP and RSD perform similarly when running with C4.5. We have also extended CILP++ to include a statistical feature selection method, mRMR, with preliminary results indicating that a reduction of more than 90 % of features can be achieved with a small loss of accuracy.     

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.     

一种自顶向下和自底向上相结合的ILP算法

归纳逻辑程序设计(ILP)是机器学习的一个重要分支,给定一个样例集和相关背景知识,ILP研究如何构建与其相一致的逻辑程序,这些逻辑程序由有限一阶子句组成。文章描述了一种综合当前一些ILP方法多方面优势的算法ICCR,ICCR溶合了以FOIL为代表的自顶向下搜索策略和以GOLEM为代表的自底向上搜索策略,并能根据需要发明新谓词、学习递归逻辑程序,对比实验表明,对相同的样例及背景知识,ICCR比FOIL和GOLEM能学到精度更高的目标逻辑程序。     

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

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

基于归结的最大一般理论特化

提出一种基于归结的并有关于背景适应吸示例的一致特化理论,该理论给出了最大一般特化假设的归结构造方法,可将其作为一种蕴涵意义下的一般理论特化框架。基于该理论,进一步提出ｋ一般特化概念以解决特化的可计算性问题,并相应地给出特化算法。有关实验表明,该理论与算法能够正确并有效地进行一阶理论特化。     

Learning probabilistic logic models from probabilistic examples

We revisit an application developed originally using abductive Inductive Logic Programming (ILP) for modeling inhibition in metabolic networks. The example data was derived from studies of the effects of toxins on rats using Nuclear Magnetic Resonance (NMR) time-trace analysis of their biofluids together with background knowledge representing a subset of the Kyoto Encyclopedia of Genes and Genomes (KEGG). We now apply two Probabilistic ILP (PILP) approaches—abductive Stochastic Logic Programs (SLPs) and PRogramming In Statistical modeling (PRISM) to the application. Both approaches support abductive learning and probability predictions. Abductive SLPs are a PILP framework that provides possible worlds semantics to SLPs through abduction. Instead of learning logic models from non-probabilistic examples as done in ILP, the PILP approach applied in this paper is based on a general technique for introducing probability labels within a standard scientific experimental setting involving control and treated data. Our results demonstrate that the PILP approach provides a way of learning probabilistic logic models from probabilistic examples, and the PILP models learned from probabilistic examples lead to a significant decrease in error accompanied by improved insight from the learned results compared with the PILP models learned from non-probabilistic examples.     

Diterpene structure elucidation from 13cnmr spectra with inductive logic programming

We present a novel application ofInductive Logic Programming (ILP) to the problem of diterpene structure elucidation from 13 CNMR spectra. Diterpenes are organic compounds oflow molecular weight with a skeleton of 20 carbon atoms. They are of significant chemical and commercial interest because oftheir use as lead compounds in the search for new pharmaceutical effectors. The interpretation of diterpene 13 CNMR spectra normally requires specialists with detailed spectroscopic knowledge and substantial experience in natural products chemistry, specifically knowledge on peak patterns and chemical structures. Given a database ofpeak patterns for diterpenes with known structure, we apply several ILP approaches to discover correlations between peak patterns and chemical structure. The approaches used include first - order inductive learning, relational instance based learning, induction oflogical decision trees, and inductive constraint logic. Performance close to that of domain experts is achieved, which suffices for practical use.     

Learning Horn definitions: Theory and an application to planning

A Horn definition is a set of Horn clauses with the same predicate in all head literals. In this paper, we consider learning non-recursive, first-order Horn definitions from entailment. We show that this class is exactly learnable from equivalence and membership queries. It follows then that this class is PAC learnable using examples and membership queries. Finally, we apply our results to learning control knowledge for efficient planning in the form of goal-decomposition rules. Chandra Reddy, Ph.D.: He is currently a doctoral student in the Department of Computer Science at Oregon State University. He is completing his Ph.D. on June 30, 1998. His dissertation is entitled “Learning Hierarchical Decomposition Rules for Planning: An Inductive Logic Programming Approach.” Earlier, he had an M. Tech in Artificial Intelligence and Robotics from University of Hyderabad, India, and an M.Sc.(tech) in Computer Science from Birla Institute of Technology and Science, India. His current research interests broadly fall under machine learning and planning/scheduling—more specifically, inductive logic programming, speedup learning, data mining, and hierarchical planning and optimization. Prasad Tadepalli, Ph.D.: He has an M.Tech in Computer Science from Indian Institute of Technology, Madras, India and a Ph.D. from Rutgers University, New Brunswick, USA. He joined Oregon State University, Corvallis, as an assistant professor in 1989. He is now an associate professor in the Department of Computer Science of Oregon State University. His main area of research is machine learning, including reinforcement learning, inductive logic programming, and computational learning theory, with applications to classification, planning, scheduling, manufacturing, and information retrieval.     

The Variable Precision Rough Set Inductive Logic Programming Model and Strings

The Variable Precision Rough Set Inductive Logic Programming model (VPRSILP model) extends the Variable Precision Rough Set (VPRS) model to Inductive Logic Programming (ILP). The generic Rough Set Inductive Logic Programming (gRS-ILP) model provides a framework for ILP when the setting is imprecise and any induced logic program will not be able to distinguish between certain positive and negative examples. The gRS-ILP model is extended in this paper to the VPRSILP model by including features of the VPRS model. The VPRSILP model is applied to strings and an illustrative experiment on transmembrane domains in amino acid sequences is presented.     

Parallel and Sequential Algorithms for Data Mining Using Inductive Logic

Inductive logic is a research area in the intersection of machine learning and logic programming, and has been increasingly applied to data mining. Inductive logic studies learning from examples, within the framework provided by clausal logic. It provides a uniform and expressive means of representation: examples, background knowledge, and induced theories are all expressed in first-order logic. Such an expressive representation is computationally expensive, so it is natural to consider improving the performance of inductive logic data mining using parallelism. We present a parallelization technique for inductive logic, and implement a parallel version of a core inductive logic programming system: Progol. The technique provides perfect partitioning of computation and data access and communication requirements are small, so almost linear speedup is readily achieved. However, we also show why the information flow of the technique permits superlinear speedup over the standard sequential algorithm. Performance results on several datasets and platforms are reported. The results have wider implications for the design on parallel and sequential data-mining algorithms. Received 30 August 2000 / Revised 30 January 2001 / Accepted in revised form 16 May 2001     

Learning goal hierarchies from structured observations and expert annotations

We describe a relational learning by observation framework that automatically creates cognitive agent programs that model expert task performance in complex dynamic domains. Our framework uses observed behavior and goal annotations of an expert as the primary input, interprets them in the context of background knowledge, and returns an agent program that behaves similar to the expert. We map the problem of creating an agent program on to multiple learning problems that can be represented in a “supervised concept learning’’ setting. The acquired procedural knowledge is partitioned into a hierarchy of goals and represented with first order rules. Using an inductive logic programming (ILP) learning component allows our framework to naturally combine structured behavior observations, parametric and hierarchical goal annotations, and complex background knowledge. To deal with the large domains we consider, we have developed an efficient mechanism for storing and retrieving structured behavior data. We have tested our approach using artificially created examples and behavior observation traces generated by AI agents. We evaluate the learned rules by comparing them to hand-coded rules. Editor: Rui Camacho     

Hardness results for neural network approximation problems

We consider the problem of efficiently learning in two-layer neural networks. We investigate the computational complexity of agnostically learning with simple families of neural networks as the hypothesis classes. We show that it is NP-hard to find a linear threshold network of a fixed size that approximately minimizes the proportion of misclassified examples in a training set, even if there is a network that correctly classifies all of the training examples. In particular, for a training set that is correctly classified by some two-layer linear threshold network with k hidden units, it is NP-hard to find such a network that makes mistakes on a proportion smaller than c/k² of the examples, for some constant c. We prove a similar result for the problem of approximately minimizing the quadratic loss of a two-layer network with a sigmoid output unit.     

A comparative study on ILP-based concept discovery systems

Inductive Logic Programming (ILP) studies learning from examples, within the framework provided by clausal logic. ILP has become a popular subject in the field of data mining due to its ability to discover patterns in relational domains. Several ILP-based concept discovery systems are developed which employs various search strategies, heuristics and language pattern limitations. LINUS, GOLEM, CIGOL, MIS, FOIL, PROGOL, ALEPH and WARMR are well-known ILP-based systems. In this work, firstly introductory information about ILP is given, and then the above-mentioned systems and an ILP-based concept discovery system called C²D are briefly described and the fundamentals of their mechanisms are demonstrated on a running example. Finally, a set of experimental results on real-world problems are presented in order to evaluate and compare the performance of the above-mentioned systems.     

基于高阶逻辑的复杂结构归纳学习研究

归纳学习的目的在于发现样例与离散的类之间的映射关系,样例及归纳的映射都需用某个形式化语言描述.归纳学习器采用的形式化语言经历了属性-值语言、一阶逻辑、类型化的高阶逻辑三个阶段,后者能克服前二者在知识表达及学习过程中的很多缺点.本文首先阐述了基于高阶逻辑的复杂结构归纳学习产生的历史背景;其次介绍了基于高阶逻辑的编程语言--Escher的知识描述形式及目前已提出的三种学习方法;复杂结构的归纳学习在机器学习领域的应用及如何解决一些现实问题的讨论随后给出; 最后分析了复杂结构归纳学习的研究所面临的挑战性问题.     

Learning from interpretation transition

We propose a novel framework for learning normal logic programs from transitions of interpretations. Given a set of pairs of interpretations (I,J) such that J=T _P (I), where T _P is the immediate consequence operator, we infer the program P. The learning framework can be repeatedly applied for identifying Boolean networks from basins of attraction. Two algorithms have been implemented for this learning task, and are compared using examples from the biological literature. We also show how to incorporate background knowledge and inductive biases, then apply the framework to learning transition rules of cellular automata.     

A Prolog simulator for deterministic P systems with active membranes

In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate, the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in Reference.¹⁰ Andrés Cordón-Franco: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Mathematical Logic, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical (software implementation) point of view. Miguel A. Gutiérrez-Naranjo: He is an assistant professor in the Computer Science and Artificial Intelligence Department at University of Sevilla, Spain. He is also a member of the Research Group on Natural Computing of the University of Seville. His research interest includes Machine Learning, Logic Programming and Membrane Computing, both from a theoretical and a practical point of view. Mario J. Pérez-Jiménez, Ph.D.: He is professor of Department of Computer Science and Artificial Intelligence at University of Seville, where he is the head of the Group of Research on Natural Computing, He has published 8 books of Mathematics and Computation, and more than 90 scientific articles in prestigious scientific journals. He is member of European Molecular Computing Consortium. Fernando Sancho-Caparrini: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Complex Systems, DNA Computing, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical point of view.     

Pharmacophore Discovery Using the Inductive Logic Programming System PROGOL

This paper presents a case study of a machine-aided knowledge discovery process within the general area of drug design. Within drug design, the particular problem of pharmacophore discovery is isolated, and the Inductive Logic Programming (ILP) system progol is applied to the problem of identifying potential pharmacophores for ACE inhibition. The case study reported in this paper supports four general lessons for machine learning and knowledge discovery, as well as more specific lessons for pharmacophore discovery, for Inductive Logic Programming, and for ACE inhibition. The general lessons for machine learning and knowledge discovery are as follows.1. An initial rediscovery step is a useful tool when approaching a new application domain.2. General machine learning heuristics may fail to match the details of an application domain, but it may be possible to successfully apply a heuristic-based algorithm in spite of the mismatch.3. A complete search for all plausible hypotheses can provide useful information to a user, although experimentation may be required to choose between competing hypotheses.4. A declarative knowledge representation facilitates the development and debugging of background knowledge in collaboration with a domain expert, as well as the communication of final results.