Context-sensitive refinements for stochastic optimisation algorithms in inductive logic programming

We describe a new approach to the application of stochastic search in Inductive Logic Programming (ILP). Unlike traditional approaches we do not focus directly on evolving logical concepts but our refinement-based approach uses the stochastic optimization process to iteratively adapt the initial working concept. Utilization of context-sensitive concept refinements (adaptations) helps the search operations to produce mostly syntactically correct concepts. It also enables using available background knowledge both for efficiently restricting the search space and for directing the search. Thereby, the search is more flexible, less problem-specific and the framework can be easily used with any stochastic search algorithm within ILP domain. Experimental results on several data sets verify the usefulness of this approach.     

Improving inductive logic programming by using simulated annealing

In Inductive Logic Programming (ILP), algorithms that are purely of the bottom-up or top-down type encounter several problems in practice. Since a majority of them are greedy ones, these algorithms stop when finding clauses in local optima, according to the “quality” measure used for evaluating the results. Moreover, when learning clauses one by one, the induced clauses become less and less interesting as the algorithm is progressing to cover few remaining examples. In this paper, we propose a simulated annealing framework to overcome these problems. Using a refinement operator, we define neighborhood relations on clauses and on hypotheses (i.e. sets of clauses). With these relations and appropriate quality measures, we show how to induce clauses (in a coverage approach), or to induce hypotheses directly by using simulated annealing algorithms. We discuss the necessary conditions on the refinement operators and the evaluation measures to increase the effectiveness of the algorithm. Implementations (included a parallelized version of the algorithm) are described and experimentation results in terms of convergence of the method and in terms of accuracy are presented.     

Pairwise saturations in inductive logic programming

One of the main issues when using inductive logic programming (ILP) in practice remain the long running times that are needed by ILP systems to induce the hypothesis. We explore the possibility of reducing the induction running times of systems that use asymmetric relative minimal generalisation (ARMG) by analysing the bottom clauses of examples that serve as inputs into the generalisation operator. Using the fact that the ARMG covers all of the examples and that it is a subset of the variabilization of one of the examples, we identify literals that cannot appear in the ARMG and remove them prior to computing the generalisation. We apply this procedure to the ProGolem ILP system and test its performance on several real world data sets. The experimental results show an average speedup of \(36\,\%\) compared to the base ProGolem system and \(12\,\%\) compared to ProGolem extended with caching, both without a decrease in the accuracy of the produced hypotheses. We also observe that the gain from using the proposed method varies greatly, depending on the structure of the data set.     

Quantitative pharmacophore models with inductive logic programming

Three-dimensional models, or pharmacophores, describing Euclidean constraints on the location on small molecules of functional groups (like hydrophobic groups, hydrogen acceptors and donors, etc.), are often used in drug design to describe the medicinal activity of potential drugs (or ‘ligands’). This medicinal activity is produced by interaction of the functional groups on the ligand with a binding site on a target protein. In identifying structure-activity relations of this kind there are three principal issues: (1) It is often difficult to “align” the ligands in order to identify common structural properties that may be responsible for activity; (2) Ligands in solution can adopt different shapes (or `conformations’) arising from torsional rotations about bonds. The 3-D molecular substructure is typically sought on one or more low-energy conformers; and (3) Pharmacophore models must, ideally, predict medicinal activity on some quantitative scale. It has been shown that the logical representation adopted by Inductive Logic Programming (ILP) naturally resolves many of the difficulties associated with the alignment and multi-conformation issues. However, the predictions of models constructed by ILP have hitherto only been nominal, predicting medicinal activity to be present or absent. In this paper, we investigate the construction of two kinds of quantitative pharmacophoric models with ILP: (a) Models that predict the probability that a ligand is “active”; and (b) Models that predict the actual medicinal activity of a ligand. Quantitative predictions are obtained by the utilising the following statistical procedures as background knowledge: logistic regression and naive Bayes, for probability prediction; linear and kernel regression, for activity prediction. The multi-conformation issue and, more generally, the relational representation used by ILP results in some special difficulties in the use of any statistical procedure. We present the principal issues and some solutions. Specifically, using data on the inhibition of the protease Thermolysin, we demonstrate that it is possible for an ILP program to construct good quantitative structure-activity models. We also comment on the relationship of this work to other recent developments in statistical relational learning. Editors: Tamás Horváth and Akihiro Yamamoto     

Foundation of logic programming based on inductive definition

A logical system of inference rules intended to give the foundation of logic programs is presented. The distinguished point of the approach taken here is the application of the theory of inductive definitions, which allows us to uniformly treat various kinds of induction schema and also allows us to regardnegation as failure as a kind of induction schema. This approach corresponds to the so-called least fixpoint semantics. Moreover, in our formalism, logic programs are extended so that a condition of a clause may be any first-order formula. This makes it possible to write a quantified specification as a logic program. It also makes the class of induction schemata much larger to include the usual course-of-values inductions.     

Lifting symmetry breaking constraints with inductive logic programming

Machine Learning - Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. Most of the existing approaches are instance-specific and focus on the...     

Model transformation by example using inductive logic programming

Model transformation by example is a novel approach in model-driven software engineering to derive model transformation rules from an initial prototypical set of interrelated source and target models, which describe critical cases of the model transformation problem in a purely declarative way. In the current paper, we automate this approach using inductive logic programming (Muggleton and Raedt in J Logic Program 19-20:629–679, 1994) which aims at the inductive construction of first-order clausal theories from examples and background knowledge.

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.     

Generating protein three-dimensional fold signatures using inductive logic programming.

Inductive logic programming (ILP) has been applied to automatically discover protein fold signatures. This paper investigates the use of topological information to circumvent problems encountered during previous experiments, namely (1) matching of non-structurally related secondary structures and (2) scaling problems. Cross-validation tests were carried out for 20 folds. The overall estimated accuracy is 73.37+/-0.35%. The new representation allows us to process the complete set of examples, while previously it was necessary to sample the negative examples. Topological information is used in approximately 90% of the rules presented here. Information about the topology of a sheet is present in 63% of the rules. This set of rules presents characteristics of the overall architecture of the fold. In contrast, 26% of the rules contain topological information which is limited to the packing of a restricted number of secondary structures, as such, the later set resembles those found in our previous studies.     

Recognition of hand-printed characters based on structural description and inductive logic programming

Character recognition systems can contribute tremendously to the advancement of the automation process and can improve the interaction between man and machine in many applications, including office automation, cheque verification and a large variety of banking, business and data entry applications. The main theme of this paper is the automatic recognition of hand-printed Arabic characters using machine learning. Conventional methods have relied on hand-constructed dictionaries which are tedious to construct and difficult to make tolerant to variation in writing styles. The advantages of machine learning are that it can generalize over the large degree of variation between writing styles and recognition rules can be constructed by example.

The system was tested on a sample of handwritten characters from several individuals whose writing ranged from acceptable to poor in quality and the average correct recognitions rate obtained using cross-validation was 86.65%.     

An efficient ordering-based ensemble pruning algorithm via dynamic programming

Although ordering-based pruning algorithms possess relatively high efficiency, there remains room for further improvement. To this end, this paper describes the combination of a dynamic programming technique with the ensemble-pruning problem. We incorporate dynamic programming into the classical ordering-based ensemble-pruning algorithm with complementariness measure (ComEP), and, with the help of two auxiliary tables, propose a reasonably efficient dynamic form, which we refer to as ComDPEP. To examine the performance of the proposed algorithm, we conduct a series of simulations on four benchmark classification datasets. The experimental results demonstrate the significantly higher efficiency of ComDPEP over the classic ComEP algorithm. The proposed ComDPEP algorithm also outperforms two other state-of-the-art ordering-based ensemble-pruning algorithms, which use uncertainty weighted accuracy and reduce-error pruning, respectively, as their measures. It is noteworthy that, the effectiveness of ComDPEP is just the same with that of the classical ComEP algorithm.     

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.     

A framework for ICAI systems based on inductive inference and logic programming

The main components of an Intelligent Computer-Assisted Instruction (ICAI) system are the expertise, the student model and tutoring strategies. The student model manages what the student dose and dose not understand, and the performance of an ICAI system depends largely on how well the student model approximates the human student. We propose a new framework for ICAI systems which uses the inductive inference for constructing the student model from the student’s behavior. In the framework, both the expertise and the student model are represented as Prolog programs, which enables to express the meta-knowledge that is the knowledge of how to use the knowledge. Since the construction of the student models is performed independently of the expertise, the framework is domain-independent. Therefore, an ICAI system for any subject area can be built with the framework. As an example, the ICAI system teaching chemical reaction is presented together with a sample performance. The authors believe that the new framework for ICAI systems based on logic programming and inductive inference could be a breakthrough of the future ICAI systems.     

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.