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.     

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.     

An introduction to inductive programming

The research field of inductive programming is concerned with the design of algorithms for learning computer programs with complex flow of control (typically recursive calls) from incomplete specifications such as examples. We introduce a basic algorithmic approach for inductive programming and illustrate it with three systems: dialogs learns logic programs by combining inductive and abductive reasoning; the classical thesys system and its extension igor1 learn functional programs based on a recurrence detection mechanism in traces; igor2 learns functional programs over algebraic data-types making use of constructor-term rewriting systems. Furthermore, we give a short history of inductive programming, discuss related approaches, and give hints about current applications and possible future directions of research. A short, non-technical version of this paper appears in C. Sammut, editor, Encyclopedia of Machine Learning, Springer–Verlag, forthcoming. The paper was written while the first author was on sabbatical in 2006/2007 at Sabancı University in İstanbul, Turkey.     

归纳逻辑程序设计综述

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

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.     

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

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

Discovering rules to design newspapers: An inductive constraint logic programming approach

Inductive logic programming combines both machine learning and logic programming techniques. ILP uses first-order predicate logic restricted to Horn clauses as an underlying language. Thus, programs induced by an ILP system inherit the classical limitations of PROLOG programs. Constraint logic programming avoids some of the limitations of logic programming, and so ILP aims to induce programs that employ this paradigm. Current ILP systems that induce constrained logic programs extend systems based on the normal semantics ofILP. In this article we introduce IC-Log, a new system that induces constrained logic programs and relies on an extension ofa nonmonotonic semantics-based system. We then present an application of IC-Log in the field ofcomputer-aided publishing.     

Access to specific declarative knowledge by expert systems: The impact of logic programming

As part of the operation of an Expert System, a deductive component accesses a database of facts to help simulate the behavior of a human expert in a particular problem domain. The nature of this access is examined, and four access strategies are identified. Features of each of these strategies are addressed within the framework of a logic-based deductive component and the relational model of data.     

Learning programming via worked-examples: Relation of learning styles to cognitive load

This paper describes an experiment that compared learners with contrasting learning styles, Active vs. Reflective, using three different strategies for learning programming via worked-examples: Paired-method, Structure-emphasising, and Completion. The quality of the learners’ acquired cognitive schemata was assessed in terms of their post-test performance. The experiment investigated variations in learners’ cognitive load, taking both the learning strategies and the learners’ learning styles into account. Overall, the results of the experiment were inconsistent. In comparing the effects of the strategies during the learning phase, the study found significant differences in cognitive load. Unexpectedly, no differences were then detected either in cognitive load or in performance during the post-test (post-test). In comparing the effects of the learning styles during the learning phase and the transfer phase, medium effect sizes suggested that learning style may have had an effect on cognitive load. However, no significant difference was observed in performance during the post-test.     

An introduction to object-oriented programming with a didactic microworld: objectKarel

The objects-first strategy to teaching programming has prevailed over the imperative-first and functional-first strategies during the last decade. However, the objects-first strategy has created added difficulties to both the teaching and learning of programming. In an attempt to confront these difficulties and support the objects-first strategy we developed a novel programming environment, objectKarel, which uses the language Karel++. The design of objectKarel was based on the results of the extended research that has been carried out about novice programmers. What differentiates it from analogous environments is the fact that it combines features that have been used solely in them: incorporated e-lessons and hands-on activities; an easy to use structure editor for developing/editing programs; program animation; explanatory visualization; highly informative and friendly error messages; recordability. In this paper, we present the didactic rationale that dictated the design of objectKarel and the features of the environment, including the e-lessons. In addition, we present the results from the use of objectKarel in the classroom and the results of the students’ assessment of the environment.     

Valuing pilot projects in a learning by investing framework: An approximate dynamic programming approach

We introduce a general discrete time dynamic framework to value pilot project investments that reduce idiosyncratic uncertainty with respect to the final cost of a project. The model generalizes different settings introduced previously in the literature by incorporating both market and technical uncertainty and differentiating between the commercial phase and the pilot phase of a project. In our model, the pilot phase requires N$N$ stages of investment for completion. With this distinction we are able to frame the problem as a compound perpetual Bermudan option. We work in an incomplete markets setting where market uncertainty is spanned by tradable assets and technical uncertainty is idiosyncratic to the firm. The value of the option to invest as well as the optimal exercise policy are solved by an approximate dynamic programming algorithm that relies on the independence of the state variables increments. We prove the convergence of our algorithm and derive a theoretical bound on how the errors compound as the number of stages of the pilot phase is increased. We implement the algorithm for a simplified version of the model where revenues are fixed, providing an economic interpretation of the effects of the main parameters driving the model. In particular, we explore how the value of the investment opportunity and the optimal investment threshold are affected by changes in market volatility, technical volatility, the learning coefficient, the drift rate of costs and the time to completion of a pilot stage.     

Pattern recognition: An alternative to parameter identification in adaptive control

Practical models used in identification of process control processes must be too simplistic to give precise control information. However, these models can be used for adaptation if they are continuously readapted. But the identification then lacks the precision which might justify the analytic elaboration. One alternative has been to use pattern recognition as a means for allowing a computer system to characterize transient response computing readapted parameters which cause the control behavior to approach a desired transient ‘shape’. The paper summarizes work using pattern features as a basis for practice and theory.     

Guiding students to the right questions: adaptive navigation support in an E‐Learning system for Java programming

Rapid growth of the volume of interactive questions available to the students of modern E‐Learning courses placed the problem of personalized guidance on the agenda of E‐Learning researchers. Without proper guidance, students frequently select too simple or too complicated problems and ended either bored or discouraged. This paper explores a specific personalized guidance technology known as adaptive navigation support. We developed JavaGuide, a system, which guides students to appropriate questions in a Java programming course, and investigated the effect of personalized guidance a three‐semester long classroom study. The results of this study confirm the educational and motivational effects of adaptive navigation support.     

Combining predictions in pairwise classification: An optimal adaptive voting strategy and its relation to weighted voting

Weighted voting is the commonly used strategy for combining predictions in pairwise classification. Even though it shows good classification performance in practice, it is often criticized for lacking a sound theoretical justification. In this paper, we study the problem of combining predictions within a formal framework of label ranking and, under some model assumptions, derive a generalized voting strategy in which predictions are properly adapted according to the strengths of the corresponding base classifiers. We call this strategy adaptive voting and show that it is optimal in the sense of yielding a MAP prediction of the class label of a test instance. Moreover, we offer a theoretical justification for weighted voting by showing that it yields a good approximation of the optimal adaptive voting prediction. This result is further corroborated by empirical evidence from experiments with real and synthetic data sets showing that, even though adaptive voting is sometimes able to achieve consistent improvements, weighted voting is in general quite competitive, all the more in cases where the aforementioned model assumptions underlying adaptive voting are not met. In this sense, weighted voting appears to be a more robust aggregation strategy.     

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance.     

Discovery and prediction capabilities in metal-based nanomaterials: An overview of the application of machine learning techniques and some recent advances

The application of machine learning (ML) techniques to metal-based nanomaterials has contributed greatly to understanding the interaction of nanoparticles, properties prediction, and new materials discovery. However, the prediction accuracy and efficiency of distinctive ML algorithms differ with different metal-based nanomaterials problems. This, alongside the high dimensionality and nonlinearity of available datasets in metal-based nanomaterials problems, makes it imperative to review recent advances in the implementation of ML techniques for these kinds of problems. In addition to understanding the applicability of different ML algorithms to various kinds of metal-based nanomaterials problems, it is hoped that this work will help facilitate understanding and promote interest in this emerging and less explored area of materials informatics. The scope of this review covers the introduction of metal-based nanomaterials, several techniques used in generating datasets for training ML models, feature engineering techniques used in nanomaterials-machine learning applications, and commonly applied ML algorithms. Then, we present the recent advances in ML applications to metal-based nanomaterials, with emphasis on the procedure and efficiency of algorithms used for such applications. In the concluding section, we identify the most common and efficient algorithms for distinctive property predictions. The common problems encountered in ML applications for metal-based nanoinformatics were mentioned. Finally, we propose suitable solutions and future outlooks for various challenges in metal-based nanoinformatics research.