Induction as a search procedure

Induction as a Search Procedure Stasinos Konstantopoulos Institute of Informatics & Telecommunications, NCSR ‘Demokritos’ P.O. BOX 60228, Ag. Paraskevi 15310, Greece Tel: +30 21 06503162, Fax: +30 21 06532175 Email: [email protected] Rui Camacho Faculdade de Engenharia da Universidade do Porto R. Dr Roberto Frias, s/m, 4200-465 Porto, Portugal Tel: +351 22 508 1849, Fax: +351 22 508 1443 Email: [email protected] and Laboratório de Inteligência Artificial e Ciências de Computadores, Rua de Ceuta, 118, 6o, 4150-190 Porto, Portugal Tel: +351 22 339 2090, Fax: +351 22 339 2099 Nuno A. Fonseca Laboratório de Inteligência Artificial e Ciências de Computadores, University of Porto R. Campo Alegre 823, 4150 Porto, Portugal Tel: +351 22 607 8830, Fax: +351 22 600 3654 Email: [email protected] Vítor Santos Costa COPPE/Sistemas, Universidade Federal do Rio de Janeiro, Brasil Centro de Tecnologia, Bloco H-319, Cx. Postal 68511, Rio de Janeiro, Brasil (CEP: 21945-970) Tel: +55 21 2562 8648, Fax: +55 21 2562 8676 Email: [email protected] 1 Induction as a Search Procedure Abstract This chapter introduces Inductive Logic Programming (ILP) from the perspective of search algorithms in Computer Science. It first briefly considers the Version Spaces approach to induction, and then focuses on Inductive Logic Programming: from its formal definition and main techniques and strategies, to priors used to restrict the search space and optimized sequential, parallel, and stochastic algorithms. The authors hope that this presentation of the theory and applications of Inductive Logic Programming will help the reader understand the theoretical underpinnings of ILP, and also provide a helpful overview of the State-of-the-Art in the domain. 1 INTRODUCTION Induction is a very important operation in the process of scientific discovery, which has been studied from different perspectives in different disciplines. Induction, or inductive logic, is the process of forming conclusions that reach beyond the data (facts and rules), i.e., beyond the current boundaries of knowledge. At the core of inductive thinking is the ‘inductive leap’, the stretch of imagination that draws a reasonable inference from the available information. Therefore, inductive conclusions are only probable, they may turn out to be false or improbable when given more data. In this chapter we address the study of induction from an Artificial Intelligence (AI) perspective and, more specifically, from a Machine Learning perspective, which aims at automating the inductive inference process. As is often the case in AI, this translates to mapping the ‘inductive leap’ onto a search procedure. Search, therefore, becomes a central element of the automation of the inductive inference process. We consider two different approaches to the problem of induction as a search procedure: Version Spaces is an informal approach, more in line with traditional Machine Learning approaches; by contrast, search-based algorithms for Inductive Logic Programming (ILP) rely on a formal definition of the search space. We compare the two approaches under several dimensions, namely, expressiveness of the hypothesis language underlying the space, completeness of the search, space traversal techniques, implemented systems and applications thereof. 2 Next, the chapter focuses on the issues related to a more principled approach to induction as a search. Given a formal definition and characterization of the search space, we describe the main techniques employed for its traversal: strategies and heuristics, priors used to restrict its size, optimized sequential search algorithms, as well as stochastic and parallel ones. The theoretical issues presented and exposed are complemented by descriptions of and references to implemented and applied systems, as well as real-world application domains where ILP systems have been successful. 2 A PRAGMATIC APPROACH: VERSION SPACES This section is structured into three parts. A first part presents a set of definitions and concepts that lay the foundations for the search procedure into which induction is mapped. In a second part we mention briefly alternative approaches that have been taken to induction as a search procedure and finally in a third part we present the version spaces as a general methodology to implement induction as a search procedure. 2.1 A Historical Road Map Concept Leaning is a research area of Machine Learning that addresses the automation of the process of finding (inducing) a description of a concept (called the ‘target concept’ or hypothesis) given a set of instances of such concept. Concepts and instances have to be expressed in a concept description language or hypothesis language (L). Given a set of instances of some concept it is usually a rather difficult problem to (automatically) induce the ‘target concept’. The major difficulty is that there may be a lot, if not an infinite, number of plausible conjectures (hypotheses) that are ‘consistent’ with the given instances. Automating the induction process involves the generation of the candidate concept descriptions (hypotheses), their evaluation, and the choice of ‘the best one’ according to some criteria. The concept learning problem is often mapped into a search problem, that looks for a concept description that explains the given instances and lies within the concept description language. An important step towards the automation of the learning process is the structuring of the elements of Lin a manner that makes it possible to perform systematic searches, to justifiably discard some ‘uninteresting’ regions of candidate descriptions, and to have a compact description of the search space. For this purpose, Machine Learning borrows from Mathematics the concept of a lattice, a partially ordered set with the property that all of its non-empty finite subsets have both a supremum (called join) and an infimum (called meet). A semi-lattice has either only a join or only a meet. The partial order can be any reflexive, anti-symmetric, and transitive binary relation. In Machine Learning a lattice is usually defined as follows: 3 Definition 1 A lattice is a partially ordered set in which every pair of elements a, b has a greatest lower bound (glb, aub) and least upper bound (lub, atb). and the partial ordering is based of the concept of generality, which places clauses along general– specific axes. Such a partial ordering is called a generalization ordering or a generalization model, and has the advantage of imposing a structure that is convenient for systematically searching for general theories and for focusing on parts of the structure that are known to be interesting. Different generalization models have been proposed in the Concept Learning literature; Mitchell (1997, p. 24), for example, defines generalization for a domain where instances (x) belong to a domain (X) of feature vectors and the target concept is encoded as a boolean-valued function (h): Definition 2 Let hjand hkbe boolean-valued functions defined over X. Then hjis more general than or equal to hk(we write hj>ghk) if and only if (∀x∈X)[hk(x) = 1 →hj(x) = 1]. Another popular definition of generality is based on the logical concept of semantic entailment: Definition 3 Given two clauses C1and C2, we shall call C1more general (more specific) than C2, and write C1>gC2(C1<gC2), if and only if C1entails C2(C2entails C1). with various syntactic logical operators suggested for the purpose of inferring entailment. We shall revisit this point in the context of Inductive Logic Programming in the following section. This suggestion that induction may be automated by carrying a search through an order space was independently suggested by Popplestone (1970) and Plotkin (1970). The search space of the alternative concept descriptions may be traversed using any of the traditional AI search strategies. In 1970 Winston (1970) describes a concept learning system using a depth-first search. In Winston’s system one example at a time is analysed and a single concept description is maintained as the current best hypothesis to describe the target concept. The current best hypothesis is tested against a new example and modified to become consistent with the example while maintaining consistency with all previously seen examples. An alternative search strategy, breadth-first search, was used in concept learning by Plotkin (1970), Michalski (1973), Hayes-Roth (1974) and Vere (1975). These algorithms already take advantage of the order in the search space. Plotkin’s work is revisited in Section 3.4.2 below, as it forms the basis for several developments in Inductive Logic Programming. 2.2 Introducing Version Spaces We now focus our attention on a general approach to concept learning, proposed by Mitchell (1978), called version spaces. A version space is the set of all hypotheses consistent with a set of training examples. In most applications the number of candidate hypotheses consistent with the 4 Candidate-Elimination Input: Examples (E) – positive (E+) and negative (E−). Output: The sets G and S. 1. G = set of maximally general hypotheses in H 2. S = set of maximally specific hypotheses in H 3.for all e∈E 4.if e∈E+then 5. remove from G any hypothesis inconsistent with e 6.for all s∈S 7.if s inconsistent with e then 8.remove s from S 9. add to S all minimal generalisations h of s such that 10.h is consistent with e and ∃g∈Gg<gh 11.remove any s ∈S such that ∃s0∈Ss<gs0 12.endif 13.end for all 14.endif 15.else (e ∈E−) 16. remove from S any hypothesis inconsistent with e 17.for all g∈G 18.if g inconsistent with e then 19. remove g from G 20. add to G all minimal specialisations h of g such that 21.h is consistent with e and ∃s∈Sh<gs 22.remove any g ∈G such that ∃g0∈Gg0<gg 23.endif 24.end for all 25.end for all 26.return S and G Figure 1: The Candidate-Elimination algorithm 5 examples is very large or even infinite. It is therefore impractical—or even infeasible—to store an enumeration of such candidates. The version space uses a compact and elegant representation of the set of candidate hypotheses. The representation takes advantage of the order imposed over such hypotheses and stores only the most general and most specific set of descriptions that limit the version space. In order to make a more formal presentation of the version spaces approach to concept learning let us introduce some useful definitions. Assume that the function tg(e)gives the ‘correct’ value of the target concept for each instance e. A hypothesis h(e)is said to be consistent with a set of instances (examples) Eiff it produces the same value of tg(e)for each example e∈E. That is: Consistent(h, E)≡ ∀e∈E,h(e) = tg(e)(1) Examples are of two kinds: positive and negative. Positive examples are instances of the target concept whereas negative examples are not. Let hypothesis space Hbe the set of all hypotheses that are part of hypothesis language L. Version space V SH,E with respect to hypothesis space Hand training set E, is the subset of H consistent with E. V SH,E ≡ {h∈H|Consistent(h, E)}(2) Since the set represented by the version space may be very large, a compact and efficient way of describing such set is needed. To fully characterize the version space Mitchell proposes to represent the most general and more specific elements, i.e., a version space is represented by the upper and lower boundaries of the ordered search space. Mitchell proposes also the CANDIDATEELIMINATION algorithm to efficiently traverse the hypothesis space. In the CANDIDATE-ELIMINATION algorithm the boundaries of the version space are the only elements stored. The upper boundary is called G, the set of the most general elements of the space, and the lower boundary S, the set of the most specific hypotheses of the version space. The upper (more general) boundary G, with respect to hypothesis space Hand examples E, is the set of the maximally general members of Hconsistent with E. G≡ {g∈H|Consistent(g, E)∧ ¬ (∃g0∈H)(g0>gg)∧Consistent(g0, E)}(3) where >gdenotes the ‘more general than’ relation. The lower (more specific) boundary S, with respect to hypothesis space Hand training set E, is the set of maximally specific members of H consistent with E. S≡ {s∈H|Consistent(s, E)∧ ¬ (∃s0∈H)(s >gs0)∧Consistent(s0, E)}(4) The CANDIDATE-ELIMINATION algorithm is outlined in Figure 1. The algorithm proceeds incrementally, by analysing one example at a time. It starts with the most general set Gcontaining all hypotheses from Lconsistent with the first example and with the most specific set Sof hypotheses 6 training version space instances S set G set <meat, yes, yes, yes> (positive – an eagle) {<meat, yes, yes, yes>} {<,,,>} <meat, no, yes, no> (negative – a wolf) {<meat, yes, yes, yes>} {<, yes, , >,<, , , yes>} <seeds, yes, no, yes> (positive – a dove) {<, yes, , yes>} {<, yes, , >,<, , , yes>} <insects, no, no, yes> (negative — a bet) {<, yes, , yes>} {<, yes, , >} <seeds, yes, no, no> (positive – an ostrich) {<, yes, , >} {<, yes, , >} Figure 2: Simple example of the CANDIDATE-ELIMINATION algorithm sequence for learning the concept of bird. from Lconsistent with the first example (the set with the first example only). As each new example is presented, Ggets specialized and Sgeneralized, thus reducing the version space they represent. Positive examples lead to the generalization of S, whenever Sis not consistent with a positive example. Negative examples prevent over-generalization by specializing G, whenever Gis inconsistent with the a negative example. When specializing elements of G, only specializations that are maximally general and generalizations of some element of Sare admitted. Symmetrically, when generalizing elements of S, only generalizations that are maximally specific and specializations of some element of Gare admitted. When all examples are processed, the hypotheses consistent with the presented data are the set of hypotheses from Lwithin the Gand Sboundaries. Some advantages of the version space approach with the CANDIDATE-ELIMINATION algorithm is that partial descriptions of the concepts may be used to classify new instances, and that each example is examined only once and there is no need for backtracking. The algorithm is complete, i.e., if there is a hypothesis in Lconsistent with the data it will be found. Version spaces and the CANDIDATE-ELIMINATION algorithm have been applied to several problems such as learning regularities in chemical mass spectroscopy (Mitchell, 1978) and control rules for heuristic search (Mitchell et al., 1983). The algorithm was initially applied to induce rules for the DENDRAL knowledge-based system that suggested plausible chemical structure of molecules based on the analysis of information of the molecule chemical mass spectroscope data. Finally, Mitchell et al. (1983) uses the technique to acquire problem-solving heuristics for the LEX system in the domain of symbolic integration. 7 2.3 A Simple Example The technique of version spaces is independent of the hypothesis representation language. According to the application, the hypothesis language used may be as simple as an attribute-value language or as powerful as First Order Logic. For illustrative purposes only (proof-of-concept) we present a very simple example using an attribute-value hypothesis language. We show an example of the CANDIDATE-ELIMINATION algorithm to induce a concept of a bird using five training examples of animals. The hypothesis language will be the set of 4-tuples encoding the attributes eats,has feathers, has claws and flies. The domains of such attributes are: eats={meat, seeds, insects}, has feathers={yes, no}, has claws={yes, no} and flies={yes, no}. The representation of an animal that eats meat, has feathers, does not have claws and flies is the 4-tuple: <meat, yes, no, yes>. We use the symbol _ (underscore) to indicate that any value is acceptable. We say that a hypothesis h1matches an example if every feature value of the example is either equal for the corresponding value in h1or h1has the symbol “_” for that feature (meaning “any value” is acceptable). Let us consider that a hypothesis h1is more general than hypothesis h2if h1matches all the instances that h2matches but the reverse is not true. Figure 2 shows the sequence of values of the sets S and G after the analysis of five examples, one at a time. The first example is a positive example, an eagle (<meat, yes, yes, yes>), and is used to initialize the S set. The G set is initialized with the most general hypothesis of the language, the hypothesis that matches all the examples: <_, _, _, _>. The second example is negative and is a description of a wolf (<meat, no, yes, no>). The second example is not matched by the element of S and therefore S is unchanged. However the hypothesis in the G set covers the negative example and has to be minimally specialized. Minimal specializations of <_, _, _, _> that avoid covering the working example are: <seed, _, _, _>,<insects, _, _, _>,<_, yes, _, _>, <_, _, no, _>,<_, _, _, yes>. Among these five specializations only the third and the fifth are retained since they are the only ones that cover the element of S. Analysing the third example (a dove – a positive example) leads the algorithm to minimally generalize the element of S since it does not cover that positive example. The minimal generalization of S’s hypothesis is <_, yes, _, yes>that covers all seen positive and is a specialization of at least one hypothesis in G. The forth example is negative and is a description of a bet (<insects, no, no, yes>). This examples forces a specialization of G. Finally the last example is a positive one (an ostrich – <seeds, yes, no, no>) that results in a minimal generalization of S. The final version space (delimited by the final S and G) defines bird as any animal that has a beak. 3 INDUCTIVE LOGIC PROGRAMMING THEORY Inductive Logic Programming (ILP) is the Machine Learning discipline that deals with the induction of First-Order Predicate Logic programs. Related research appears as early as the late 1960’s, 8 but it is only in the early 1990’s that ILP research starts making rapid advances and the term itself was coined.1 In this section we first present a formal setting for Inductive Logic Programming and highlight the mapping of this theoretical setting into a search procedure. The formal definitions of the elements of the search and the inter-dependencies between these elements are explained, while at same time the concrete systems that implement them are presented. It should be noted at this point that we focus on the, so to speak, mainstream line of ILP research, that most directly relates to ILP’s original inception and formulation. And that, even within this scope, it is not possible to describe in depth all ILP systems and variations, so some will only receive a passing reference. With respect to systems, in particular, we generally present in more detail systems were a concept or technique was originally introduced, and try to make reference to as many subsequent implementations as possible. 3.1 The Task of ILP Inductive Logic Programming systems generalize from individual instances in the presence of background knowledge, conjecturing patterns about yet unseen data. Inductive Logic Programming, therefore, deals with learning concepts given some background knowledge and examples 2. Both examples, background knowledge and the newly learnt concepts are represented as logic programs. Given this common ground, the learning process in ILP can be approached in two different ways. In descriptive induction one aims at at describing regularities or patterns in the data. In predictive induction one aims at learning theories that solve classification/prediction tasks. More precisely, let us assume there is some background knowledge B, some examples E, and a hypothesis language L. We define background knowledge to be a set of axioms about the current task that are independent of specific examples. We define the set of examples, or instances, or observations as the data we want to generalize from. Often, but not always, examples are divided into positive examples, or E+, and negative examples, or E−, such that E=E+∪E−. The task of descriptive ILP is finding a theory that explains the examples in the presence of the background. More formally, descriptive ILP is defined as follows: Definition 4 Given background knowledge B, examples E, and hypothesis language L, if the following prior condition holds: (Prior Necessity) Bdoes not explain E then the task of descriptive ILP is to find a maximally specific hypothesis H∈ L, such that: (Posterior Sufficiency) Hexplains B∧E if such a hypothesis exists. 9 learnOneRule( E,R0) Input: Examples E, used for evaluation. Initial rule R0. Output: A rule R. 1.BestRule =R=R0 2.while stopping criteria not satisfied do 3.NewRules =RefineRule(R) 4.GoodRules =PickRules(E, NewRules) 5.for r∈GoodRules 6.NewR =LearnOneRule(E, r) 7.if NewR better than BestRule 8.BestRule =NewR 9.endif 10.end for 11.end while 12.return BestRule Figure 5: A procedure which returns the best rule found that explains a subset of the positive examples in E. The starting point of the search R0is one of the extremities of the lattice, RefineRule() is the lattice traversal operator, and PickRules() combines the search strategy, the heuristics, and prior constraints of valid rules to generate an ordered subset of the NewRules set. semi-lattices) or bound by the other extremity. Regarding the extremities of the lattice, the maximally general clause (the top clause) of the generalization lattice is , the empty clause. The construction of the maximally specific clause varies with different ILP algorithms and generalization models, and can be saturation or least general generalization, or simply a ground example. Which one of the maximally general and the maximally specific assumes the rôle of the join and which of the meet depends on the direction of the search along the general–specific dimension. 3.2.3 The Elements of the Search We have identified the elements of the ILP search lattice, the mathematical construct that defines a search problem equivalent to the ILP task, as logically formulated before. With these elements in place, we can proceed to apply a lattice search strategy, a methodology for traversing the search space looking for a solution. Search strategies are typically driven not only by the shape of the search space, but also by a heuristics, which evaluates each node of the lattice and estimates its ‘distance’ from a solution. To recapitulate, in order to perform an ILP run, the following elements must be substantiated: •The hypothesis language, which is the set of eligible hypothesis clauses. The elements of 16 this set are also the elements that form the lattice. •A traversal operator that in-order visits the search space, following either the general-tospecific or the specific-to-general direction. •the top and bottom clause, the extremities of the lattice. The top clause is the empty-bodied clause that accepts all examples, and the bottom clause is a maximally specific clause that accepts a single examples. The bottom clause is constructed by a process called saturation. •The search strategy applied to the lattice defined by the three elements above. •The heuristics that drive the search, an estimator of a node’s ‘distance’ from a solution. Due to the monotonic nature of the definite programs, this distance can be reasonably estimated by an evaluation function that assigns a value to each clause related to its ‘quality’ as a solution. We now proceed to describe how various ILP algorithms and systems realize these five elements, and show the impact of each design decision on the system’s performance. The focus will be on the clause-level search performed by sequential-cover predictive ILP systems, but it should be noted that the same general methodology is followed by theory-level predictive ILP and (to a lesser extend) descriptive ILP algorithms as well. 3.3 Hypothesis Language One of the strongest, and most widely advertised, points in favour of ILP is the usage of prior knowledge to specify the hypothesis language within which the search for a solution is to be contained. ILP systems offer a variety of tools for specifying the exact boundaries of the search space, which modify the space defined by the background theory, the clausal theory that represents the concrete facts and the abstract, first-order generalizations that are known to hold in the domain of application. In more practical terms, the background predicates, the predicates defined in the background theory, are the building blocks from which hypothesis clauses are constructed. The background predicates should, therefore, represent all the relevant facts known about the domain of the concept being learnt; the ILP algorithm’s task is to sort though them and identify the ones that, connected in an appropriate manner, encode the target concept. Even ILP algorithms that go one step further and revise the background theory (cf. Section 3.8.2 below), rely on the original background to use as a starting point. Prior knowledge in ILP is not, however, restricted to the set of predefined concepts available to the ILP algorithm, but extends to include a set of syntactic and semantic restrictions imposed on the set of admissible clauses, effectively restricting the search space. Such restrictions cannot 17 be encoded in the background theory program of Definitions 5 and 5, but ILP systems provide external mechanisms in order to enforce them.4These mechanisms should be thought of as filters that reject or accept clauses—and, in some cases, whole areas of the search space—based on syntactic or semantic pre-conditions. 3.3.1 Hypothesis Checking As explained before, managing the ILP search space often depends on having filters that reject uninteresting clauses. The simplest, but crudest approach, is to include or omit background predicates. By contract, some ILP systems, e.g., ALEPH (Srinivasan, 2004), allow users to build themselves filters that verify whether the clause is eligible for consideration or whether it should be immediately dropped. Such a hypothesis checking mechanism allows the finest level of control over the hypothesis language, but is highly demanding on the user and should be complemented with tools or mechanisms that facilitate the user’s task. Hypothesis checking mechanisms can be seen as a way to bias the search language, and therefore usually known as the bias language. One very powerful such example are declarative languages such as antecedent description grammars, definite-clause grammars that describe acceptable clauses (Cohen, 1994; Jorge & Brazdil, 1995), or the DLAB language of clause templates (Dehaspe & De Raedt, 1996) used in CLAUDIEN (De Raedt & Dehaspe, 1996), one of the earliest descriptive ILP systems. As Cohen notes, however, such grammars may become very large and cumbersome to formulate and maintain; newer implementations of the CLAUDIEN algorithm (CLASSICCL, Stolle et al. 2005) also abandon DLAB and replace it with type and mode declarations (see below). Finally, note that hypothesis checking mechanisms can verify a variety of parameters, both syntactic and semantic. As an example of semantic parameter, it is common for ILP systems to discard clauses with very low coverage, as such clauses often do not generalize well. 3.3.2 Determinacy A further means of controlling the hypothesis language is through the concept of determinacy, introduced in this context by Muggleton & Feng (1990). Determinacy is a property of the variables of a clause and, in a way, specifies how ‘far’ they are from being bound to ground terms: a variable in a term is j-determinate if there are up to jvariables in the same term. Furthermore, a variable is ij-determinate if it is j-determinate and its depth is up to i. A clause is ij-determinate is all the variables appearing in the clause are ij-determinate. The depth of a variable appearing in a clause is recursively defined as follows : 18 Definition 7 For clause Cand variable vappearing in C, the depth of v,d(v), is d(v) = (0if vis in the head of C 1 + minw∈var(C,v)d(w)otherwise where var(C, v)are all the variables appearing in those atoms of the body of Cwhere valso appears. The intuition behind this definition is that depth increases by 1 each time a body literal is needed to ‘link’ two variables, so that a variable’s depth is the number of such links in the ‘chain’ of body literals that connects the variable with a variable of the head.5Simply requiring that the hypothesis language only include determinate clause, i.e., clauses with arbitrarily large but finite determinacy parameters, has a dramatic effect in difficulty of the definite ILP task, as it renders definite hypotheses PAC-learnable (De Raedt & Džeroski, 1994). Naturally, specifying smaller values for the determinacy parameters tightens the boundaries of the search space. Consider, for example, the following clause as a possible solution for our grandfather-learning example: C= grandfather(X, Y )←father(X, U)∧father(U, V )∧mother(W, V )∧mother(W, Y )(10) This clause perfectly classifies the instances of our example (Figure 3) and is 2,2-determinate.6 Although this clause satisfies the posterior requirements for a hypothesis, a domain expert might have very good reasons to believe that the grandfather relation is a more direct one, and that solutions should be restricted to 1,2-determinate clauses. Imposing this prior requirement would force a learning algorithm to reject clause C(Eq. 10) as a hypothesis and formulate a more direct one, for example: D= grandfather(X, Y )←father(X, U)∧parent(U, Y )(11) 3.3.3 Type and Mode Declarations Type and mode declarations are further bias mechanisms that provide ILP algorithms with prior information regarding the semantic properties of the background predicates as well as the target concept. Type and mode declarations were introduced in PROGOL (Muggleton, 1995) and have since appeared in many modern ILP systems, most notably including the CLASSICCL (Stolle et al., 2005) re-implementation of CLAUDIEN, where they replace the declarative bias language used in the original implementation. Mode declarations state that some literal’s variables must be bound at call time (input, +) or not (output, −) and thus restrict the ways that literals can combine to form clauses. Mode declaration also specify the places where constants may appear (constant, #). For example, with the following mode declarations in the background: B=     mode(grandfather(+,−)) mode(father(+,+)) mode(parent(+,+))      (12) 19 clause D(Eq. 11) can not be formulated, as variable Ycannot be bound in the parent/2 literal if it is unbound in the head. The desired ‘chain’ effect of input/output variables may be achieved with the following background: B=     mode(grandfather(+,−)) mode(father(+,−)) mode(parent(+,−))      (13) achieves the desired ‘chain’ effect of input/output variables: Xis bound in the head, so that father/2 can be applied to bind the unbound variable U, which in its turn can serve as input to parent/2. Modes are usually combined with recall bounds that restrict the number of possible instantiations of a literal’s variables for each mode of application: B=         mode(1,grandfather(+,+)) ∨mode(2,grandfather(+,−)) mode(1,father(+,+)) ∨mode(3,father(+,−)) mode(1,parent(+,+)) ∨mode(3,parent(+,−)) mode(1,female(+)) ∨mode(5,female(−))          (14) This background restricts the second mode of grandfather/2to two possible instantiations, so that hypothesis D(Eq. 11) becomes unattainable and a different solution has to be identified. Consider, for example: E= grandfather(X, Y )←father(X, U)∧parent(U, Y )∧female(Y)(15) Clause Efocuses on grandfathers of grand-daughters, and so satisfies the requirements of Eq. 14. Finally, mode declarations are extended with a rudimentary type system, such that different modes apply to different instances. To demonstrate, the following background knowledge: B=                    mode(2,grandfather(+M, −M)) ∨mode(2,grandfather(+F, −F)) mode(2,father(+M, −M)) ∨mode(2,father(+M, −F)) mode(2,parent(+M, −M)) ∨mode(2,parent(+M, −F)) ∨mode(2,parent(+F, −M)) ∨mode(2,parent(+F, −F)) mode(1,female(+F)) ∨mode(5,female(−F)) mode(1,male(+M)) ∨mode(5,male(−M))                    (16) admits hypotheses like D(Eq. 11) which cover up to two grandchildren of each gender. Note, however, that types in ILP systems are most often flat tags; they do not support the supertype– subtype hierarchy that is so fundamental to modern type systems. As a result, it is not, for example, possible to express the fact that that although the parent/2predicate can be instantiated for up to 2children of each gender, it can be instantiated for up to 3children of either gender, as this would require the definition of a person supertype for the Mand Ftypes. 20 3.4 Hypothesis Space Traversal As already seen above, the elements of the hypothesis language are organized in a lattice by a partial-ordering operator. In theory, it would suffice to have an operator that simply evaluates the relation between two given clause as ‘more general than’, ‘less general than’, or neither. This would, however, be impractical since it would require that the whole search space is generated and the relationship between all pairs of search nodes is evaluated before the search starts. Instead, ILP systems use generative operators which map a given clause into a set of clauses that succeed the original clause according to the partial ordering.7Using such a traversal operator only the fragment of the search space that is actually visited is generated as the search proceeds. There are three main desiderata for the traversal operator: •it should only generate clauses that are in the search space, •it should generate all the clauses that are in the search space, •it should be efficient and generate the most interesting candidate hypotheses first. Satisfying these points does not only involve the traversal operator, but also its interaction with the other elements of the search. Prior knowledge, in particular, defines the hypothesis language and thus the elements of the search space and operates on the assumption of a monotonic entailment structure of the search space: whenever C <gD, it must be that CD(Definition 3). This places the requirement that the traversal operator is a syntactic inference operator that mechanizes the process of validating semantic entailment. Deductive inference operators that deduce Dfrom C only when CDare called sound and those that deduce Dfrom Cfor all C, D where CDare called complete. A variety of sound first-order deductive inference operators have been proposed in the logic programming literature, each with their own advantages and limitations with respect to completeness and efficiency. ILP borrows the deductive operators from the logic programming community for searching in the general-to-specific direction and derives their inductive inversions for the specific-to-general direction. 3.4.1 Subsumption The earliest approaches to first-order induction were based on θ-subsumption (Plotkin, 1970), a sound deductive operator which deduces clause Bfrom clause Aif the antecedents of Aare a subset of the antecedents of B, up to variable substitution: Definition 8 If there is a substitution θsuch that Aθ ⊆B, then A θ-subsumes B(AB). 21 So, for example, given the clauses Cand D: C= mother(X, Y )←parent(X, Y )∧female(X) D= mother(sofia, Y )←parent(sofia, Y )∧female(sofia) ∧female(Y)(17) it is the case that CD, since Cθ ⊆Dfor θ={X/sofia}. And, indeed, it is also the case that C entails Dsince the mothers of daughters are a subset of mothers of children of either gender. In practice, θ-subsumption is a purely syntactic operator: using θ-subsumption to make a clause more specific amounts to either adding a literal or binding a variable in a literal to a term. Inversely, generalization is done by dropping literals, replacing ground terms with variables, or introducing a new variable in the place of an existing one that occurs more than once in the same literal. When searching in either direction (specific-to-general or general-to-specific) between a (typically very specific) clause {H, ¬B1,¬B2,...,¬Bn}and the most general clause {H}(where Hcontains no ground terms and all variables are different), the search space is confined within the power-set of {¬Bi} The FOIL algorithm (Quinlan, 1990) uses θ-subsumption to perform open-ended search. FOIL is the natural extension of the propositional rule-learning system CN2 (Clark & Niblett, 1989) to first order: it employs the same open-ended search strategy starting with an empty-bodied top clause and specializing it by adding literals. FOIL searches using a best-first strategy, where each step consists of adding all possible literals to the current clause, evaluating their quality, and then advancing to the next ‘layer’ of literals once the best clause at the current clause length has been identified. The list of candidate-literals at each layer consists of all background predicates with all possible arguments according to the current language, that is, new variables, variables already appearing in the body so far, and all constants and function symbols. FOIL allows some bias to constraint the search space. First, each new literal must have have at least one variable that already appears in the current clause. Second, FOIL supports a simple type system that restricts the number of constants, functions and variables that can be placed as arguments. 3.4.2 Relative Least General Generalization The direct approach of performing an open-ended θ-subsumption can generate search spaces with a very high branching factor. The problem is that whenever we expand a clause with a new literal we need to consider every literal allowed by the language, that is, every literal in the language for which we have input variables bound. This is especially problematic if the new literal can have constants as arguments: in this case, we always need to consider every constant in the (typed) language when we expand a clause with a literal. In order to achieve more informed search-coming, Muggleton & Feng (1990) introduced the concept of the bottom clause, the minimal generalization of a set of clauses. The process of achieving this idea is somewhat involved, but the original idea was based on Plotkin’s (1970) work on 22 inductive operators and, more specifically, work on defining the least general generalization (LGG) of two given terms as the most specific term that θ-subsumes them. Essentially, the LGG inverts unification by introducing variables that replace ground atoms in the original terms. See, as an example, the following clauses and their LGG: E1= grandfather(jArcadioBD,renata) E2= grandfather(jArcadioBD,amaranta) lgg(E1, E2) = grandfather(jArcadioBD, X) (18) LGG generalizes two (or more, by repeated application) terms in the absence of any background predicates that can be used to restrict the variables introduced. Plotkin (1971a) proceeds to define the relative least general generalization (RLGG) of a set of terms relative a set of background terms. RLGG generalizes the set of terms into a single ungrounded term and uses the background knowledge to restrict the possible bindings of the variables introduced. Plotkin’s original idea was to induce theories by applying the RLGG to a set of examples relative to the background: rlgg({Ei},{Bi}) = grandfather(X, Y )←father(X, Z)∧parent(X, Z)∧ parent(Z, Y )∧sibling(U, Z)∧female(U)... (19) where the Eiare the positive examples in Eq. 6 and the Biare the ground facts and all extensions of the intensionally defined predicates in Eq. 5. We only show a fragment of the full RLGG here; the full clause contains all possible ways to relate the argument Xwith the argument Y, but even the fragment shown here is already overly specific and—correct as this theory might be according to the data—a shorter theory can be identified that accurately classifies the examples. In general, Plotkin (1971a) notes that the RLGG can be very long even for ground clauses, and potentially infinite when ungrounded clauses are involved, prohibiting its practical application. Muggleton & Feng (1990) observe that the RLGG of the examples is an accurate but unnecessarily specific theory: thus, it should be considered a starting point to be further refined by searching in the space of clauses that can be found in the θ-subsumption lattice bounded between the RLGG bottom and an empty-bodied top clause. As a second step, and in order to avoid infinite RLGG bottoms, the hypothesis language is further restricted to ij-determinate definite clauses. Under the ij-determinacy restriction, the RLGG of a set of ground clauses (examples) relative to a set of background clauses is unique and finite. These ideas were originally implemented in GOLEM, an ILP system which alleviates Plotkin’s problem of unnecessarily specific and long hypotheses while at the same time bounding the search into clauses that take into account the totality of the background and the examples. This was a moment of paramount importance in ILP research, as it marked the transition from open-ended searches in semi-lattices to full-lattice searches; a development which, although by no means sufficient to guarantee termination, at least voided one of the possible causes of non-termination. 23 3.4.3 Inverse Resolution Although θ-subsumption search have been successfully used in the early days of ILP, it has been known that, as Plotkin (1971b) originally noted, θ-subsumption is not complete, or, in other words, it is not able to infer Bfrom Ain all cases where Aentails B; it naturally follows that inverse θ-subsumption is also not complete. Consider, for example, the following clauses: A= ancestor(X, Y )←parent(X, Z)∧ancestor(Z, Y ) B= ancestor(X, Y )←parent(X, Z)∧parent(Z, W)∧ancestor(W, Y )(20) where Brepresents a stricter form of ‘ancestry’ than A, so that all models of Aare also models of B. But, although AB, there is no variable substitution θsuch that Aθ ⊆B.8This incompleteness naturally propagates to inverse θ-subsumption as well: clause Bcannot be generalized into Aby inverse θ-subsumption (effectively, literal dropping and variable substitution) although Ais more general than B. In order to close the gap between true implication and θ-subsumption, ILP research has turned to complete deductive inference operators, like Robinson’s resolution rule. The Robinson resolution rule (1965) raises the propositional resolution rule to the first order, and is defined as follows: Definition 9 Clause Ris resolved from clauses C1and C2if and only if there are literals l1∈C1 and l2∈C2and substitution θsuch that: l1θ=¬l2θ R= (C1− {l1})θ∪(C2− {l2})θ By algebraically solving the equation in Definition 9 for C2, an inverse resolution operator can be defined which generalizes clause R, given background clause C1: C2= (R−(C1− {l1})θ1)θ−1 2∪¬l1θ1θ−1 2(21) where l1∈C1and θ1θ2is a factorization of the unifying substitution θfrom Definition 9, such that θicontains all and only substitutions involving variables from Ci. Such a factorization is always possible and unique, because C1and C2are distinct clauses, hence the variables appearing in C1 are separate from those appearing in C2. The above generalization operator was the basis of CIGOL (Muggleton & Buntine, 1988), one of the earliest successful ILP systems. CIGOL follows a sequential-covering strategy, with individual clause search proceeding in the specific-to-general direction. The starting point of the search is a ground positive example, randomly selected from the pool of uncovered positives, that is generalized by repeated application of inverse resolution. The advantage is that all and only consistent clauses are generated, allowing for a complete, yet focused search. 24 3.4.4 Mode-Directed Inverse Entailment While inverted resolution is complete, it disregards the background (modulo a single background clause at each application), so it does not provide for a focused search. RLGG-based search, on the other hand, does take into account the whole of the background theory, but it relies on inverting θ-subsumption, so it performs an incomplete search that can potentially miss good solutions. In order to combine completeness with the informedness of the minimal-generalization bottom, Muggleton (1995) explores implication between clauses and ways of reducing inverse implication to a θ-subsumption search without loss of completeness, and defines the inverse entailment operator, based on the following proposition: Lemma 1 Let C,Dbe definite, non-tautological clauses and S(D)be the sub-saturants of D. Then CDif and only if there exists C0∈S(D)such that CC0. where the sub-saturants of a clause Dare, informally,9all ungrounded clauses that can be constructed from the symbols appearing in Dand cannot prove the complement of D(i.e., do not resolve to any of the atoms in the Herbrand model of the complement of D). Inverse entailment starts by saturating a ground positive example into a bottom clause, an ungrounded clause which can prove only one ground positive example and no other. Because of Lemma 1, any clause which entails the original example will also θ-subsume the bottom clause; it is now sufficient to perform a θ-subsumption search in the full lattice between the empty-bodied top clause and the bottom clause without loss of completeness. Mode-directed inverse entailment (MDIE) is a further refinement of inverse entailment where the semantics of the background predicates are taken into consideration during saturation (see below). The search in MDIE is organized in the general-to-specific direction in the original PROGOL system (Muggleton, 1995), as well as in most other successful MDIE ILP systems, like, e.g., ALEPH (Srinivasan, 2004), INDLOG (Camacho, 2000), CILS (Anthony & Frisch, 1999), and APRIL (Fonseca, 2006) although the alternative direction has been explored as well (Ong et al., 2005). 3.5 Saturation Saturation is the process of constructing a bottom clause10 which constitutes the most-specific end of the search lattice in mode-directed inverse entailment. The most prominent characteristic of saturation is that it fills the ‘gap’ between θ-subsumption and entailment: the literals of the bottom clause are the sub-saturants of a clause C, hence identifying clauses that entail Camounts to identifying clauses that θ-subsume the bottom clause (Lemma 1). Saturation is performed by repeated application of inverse resolution on a ground example, called the seed. This introduces variables in place of the ground terms in a ‘safe’ manner: the bottom clause is guaranteed to include all of and only the sub-saturants of the seed. 25 each example can be approximated by combining the proof complexity with coverage results which estimate the compression achieved by the hypothesis and with the total (positive and negative) coverage, which is taken as a measure of the generality of the clause (idem., Section 3): Lproof = (P+N)·Cav + log 1 AccAcc ·(1 −Acc)1−Acc (31) where Acc is the observed accuracy P/ (P+N)and Cav the average proof complexity of the hypothesis over all the examples. It is easy to see that the logarithmic term (which represents the performance of the hypothesis) is dominated by the proof complexity term and the generality factor, so that it comes into consideration when comparing hypotheses with similar (semantic) generality and (syntactic) complexity characteristics. 3.7.4 Positive-Only Evaluation One other category of evaluation functions that should be particularly noted is those that facilitate learning in the absence of negative examples (positive examples only). Conventional semantic evaluation functions cannot be used because in this case, in the absence of negative examples, the trivial clause that accepts all examples will always score best. For this reason, positive-only evaluation functions balance positive coverage against a clause’s generality, to avoid favouring over-generalization. Generality can be estimated syntactically as well as semantically, as in the posonly function (Muggleton, 1996): PosOnlyC,Rall (P, R, L) = log P−Clog R+ 1.0 Rall + 2.0−L P(32) where (R+1.0)/(Rall +2.0) is a Laplace-corrected estimation of the clause’s generality. The estimation is made by randomly generating Rall examples and measuring the clause’s coverage Rover them. The formula is balancing between rewarding coverage (the first term) and penalizing generality (the second term), so as to avoid over-general clauses in the absence of negative data. The C parameter implements prior preference towards more general or more specific clauses and the third term implements syntactic bias towards shorter clauses, unless extended coverage compensates for the length penalty. 3.8 Other Approaches to ILP We have so far focused ILP systems that perform a clause-level search on a pre-defined, static search space. Although these systems form the mainstream of ILP research, other options have been explored as well, namely searching at the theory level and searching in a dynamic space. 32 3.8.1 Theory-level Search The sequential cover strategy has a profound impact on the size of the search space, as it restricts the search to the space of single clauses. It does so, however, at the risk of missing out on good solutions, since the the concatenation of good clauses is not necessarily a good theory: the best clause, given a set of positives, might leave a positives pool that is not easily separable, whereas a (locally) worse clause might allow for a better overall theory. This is especially true for systems that saturate examples to build the bottom clause, as the (random) choice of the seed is decisive for the search sub-space that will be explored. An unfortunate seed choice might ‘trap’ subsequent clausal searches with an unnecessarily difficult positives pool. In sequential-cover systems the problem can be somewhat alleviated by saturating multiple seeds; in the ALEPH system, to name one example, the user can specify the number of examples that must be saturated for each positives pool. After performing as many searches as there were bottom clauses constructed, the best clause is appended to the theory and the process re-iterates. Such techniques can improve the quality of the constructed theories, but not completely solve the problem, which can only be tackled by evaluating the theory as a whole at each step for the search. In theory-level searching the search space is the lattice formed by the set all admissible theories (as opposed to clauses), structured into a lattice by a theory-level traversal operator. It is immediately obvious that not only does search space become dramatically larger, but the traversal operator also gains more degrees of indeterminism, making the search even harder: the traversal operator can (a) specify or generalize a clause, (b) delete a clause altogether, or (c) start a new (top or bottom) clause. In order to handle the increase in the size and complexity of the search space ILP systems that support theory-level search, like ALEPH, exploit randomized search methods to improve efficiency. Randomized search methods and other efficiency optimizations used in ILP systems are further described below. 3.8.2 Dynamically Changing Search Spaces We end the section with an overview of algorithms that tackle dynamically changing search spaces, due to bias shift and background theory revision (background predicate invention and refinement). Descriptive ILP systems readily offer themselves to predicate invention, since they are oriented towards discovering ‘property clusters’ in the data and multi-predicate learning. Systems like CLAUDIEN (De Raedt & Dehaspe, 1996) propose predicates that separate such clusters, and also re-use these predicates in the definitions of subsequently constructed predicate clauses. Single-predicate learning, predictive ILP systems, on the other hand, typically assumed that the background predicates are both correct and sufficient to solve the problem, and no attempt is made to revise or supplement them. Some systems, however, do attempt background theory revision. SPECTRE (Boström, 1996), for example, attempts background theory refinement by examining the 33 SLD proof-trees generated during hypothesis matching. When pruning a background predicate’s proof-tree (effectively, specializing the predicate) eliminates negative coverage, the background predicate is amended accordingly. The same idea was further explored in the MERLIN2.0 system (Boström, 1998), this time attempting predicate invention, which expands the background theory with new predicates deemed useful for constructing a theory. MERLIN2.0 unfolds the SLD proof-trees of background predicates, and identifies new sub-predicates (in the semantic sense of predicates achieving a subset of the original predicate’s coverage) which improve accuracy when used to construct a theory. Inverse resolution also offers an opportunity for predicate invention: Muggleton (1988) proposes a predicate invention algorithm which asserts a predicate when its presence allows an— otherwise unattainable—inverse resolution step to proceed, if the generalization performed by this step evaluates well on the data. This idea was implemented in CIGOL (Muggleton & Buntine, 1988), an inverse-resolution ILP system, but was later abandoned as predictive ILP research moved towards inverse entailment systems that use θ-subsumption as their traversal operator. 3.8.3 Statistical Inductive Logic Programming A new line of ILP research that is being actively pursued combines statistical Machine Learning with ILP. One such approach (Muggleton, 2003) combines a symbolic ILP step with a numerical step to learn a Stochastic Logic Program (SLP). The structure of the SLP is learnt without taking the numerical parameters into account, which are subsequently estimated to fit the program. Another approach abandons the learning semantics discussed earlier in this section, and introduces learning from proofs. Under learning from proofs, the input is the proof trees of positive and negative derivations, which are used (in conjunction with a background theory) to build a statistical model of ‘good’ or ‘applicable’ derivations using. De Raedt et al. (2005) use a variant of Expectation Maximisation and Passerini et al. (2006) kernel-based methods to build the statistical model. 4 EFFICIENT INDUCTIVE LOGIC PROGRAMMING A crucial point for the applicability of ILP is its efficiency in terms of computational resources needed to construct a theory. As has been experimentally verified Železný et al. (2003), ILP systems’ run-times exhibit considerable variability, depending on the heuristics, the problem instance, and the choice of seed examples. The total execution time of an ILP system can be roughly divided into three major components: •time spent generating clauses, which can be a major concern for large real-world problems, and particularly in novel application domains where prior domain knowledge is fragmentary and the search space cannot be restricted without risking to exclude good solutions; 34 •time spent evaluating clauses, typically due to the size of the data, although Botta et al. (2003) have shown that there are circumstances under which evaluation can become extremely hard, even if model-spaces and datasets are quite small; and •time spent accessing the data, as some datasets can be extremely large, e.g., biological databases arising from sequencing animal and plant genomes. Constructing models of such data requires an ILP system to be able to efficiently access millions of data items. The relative weight of each component depends on the ILP system used, on the search algorithm, on the parameter settings, and on the data, but in most cases evaluating rule quality is responsible for most of the execution time. In this section we describe methods for improving the efficiency of ILP systems directly related to the three concerns raised above (large search spaces, large datasets, evaluation). Some of these methods are improvements and optimizations of the sequential execution of ILP systems, whereas some are stochastic approaches to search or parallelisms of the search strategy. Before proceeding, we provide a classification of the techniques regarding their correctness. In this context, a correct technique should be understood as yielding the same results as some reference algorithm that does not employ the technique. An approximately correct technique does not preserve correctness, but still gives results that are, with high probability, similar (in quality) to the results produced by the reference technique. 4.1 Reducing the Search Space In the Hypothesis Language section above, we have discussed a variety of tools that ILP systems offer for controlling the search space. More specifically, we have discussed how the search space is initially defined by the vocabulary provided by the background theory and then further refined by language bias such as hypothesis checking and pruning, determinacy constrains, and type-mode declarations. In the theoretic context of our previous discussion of these tools, they have been presented as a means of excluding potentially good solutions on grounds that the ILP algorithm cannot access through example-driven evaluation, like non-conformance with a theoretical framework. We shall here revisit the same tools in order to review them from a different perspective: instead of a means of excluding empirically good solutions that should be avoided on theoretical grounds, they are viewed as an optimization that excludes bad solutions before having to evaluate them in order to reject them. 4.1.1 Hypothesis Checking and Pruning We have seen how hypothesis checking can be used to impose syntactic as well as as semantic constraints on the hypothesis language. In many situations it is possible to capitalize on the mono35 tonicity of definite clause logic in order to direct the search away not from individual clauses, but from whole areas of the search space that are known to not contain any solutions. Consider, for example, a clause containing in its body literals that are known to be inconsistent with each other, say male(X)and female(X). Not only is such a clause bound to not cover any examples, but all its specializations can also safely ignored. In systems that support pruning, prior knowledge can be provided which, once such a clause in encountered during the search, prunes away the whole sub-space subsumed by the clause. Another method that takes advantage of prior expert knowledge to reduce the hypothesis language is redundancy declarations. Fonseca et al. (2004) propose a classification of redundancy in the hypothesis language and show how expert knowledge can be provided to an ILP system to in order reduce it. The technique is correct (if complete search is performed) and yields good results. Two things must be noted at this point: first that useful as they might be, semantic hypothesis checking and pruning are bound to make a smaller difference with respect to efficiency that their syntactic counterparts since they require the—potentially expensive—coverage computations to be carried out whereas purely syntactic checking can discard a hypothesis beforehand. And, second, that the hypothesis checking, pruning, and redundancy declarations must be provided by the domain expert. This task that can be tedious and error-prone and has not been successfully automated. 4.1.2 Determinacy and Type-mode Declarations Determinacy and type-mode declarations can also be used to state not a theoretical restriction, but an actual fact about the background theory. When used in this manner they are not excluding empirically possible—but otherwise unacceptable—solutions, but they are rather steering the search away from areas of the search that are known to be infertile. Consider, for example, the declarations in Eq. 16 above. While the type-mode declarations for the grandfather/2predicate are, as we have already discussed, enforcing a genuine restriction, the rest are stating actual facts about the semantics of the background predicates. So, for instance, the parent/2declaration is prohibiting the consideration of hypotheses like this one: C= grandfather(X, U)←father(X, Y )∧parent(Y, U)∧male(U)∧ parent(Y, V )∧male(V)∧parent(Y, W)∧male(W)(33) which only admits grand-fatherhood in the presence of three or more grand-sons. This clause is rejected because the background theory does not allow instantiations where three children are male. The clause can only succeed by unifying two of U, V, W and can be safely ignored: no ILP algorithm would have chosen this clause anyway, as the model of our example identical semantics can be achieved by a simpler clause. In general, providing the smallest determinacy values that will not leave any solutions out of the hypothesis space is a correct optimization of the ILP search. Similarly for type declarations, 36 where assigning incompatible types can help avoid evaluating obviously inconsistent clauses like, for example: D= grandfather(X, Y )←femaleX ∧father(X, Z)∧parent(Z, Y )(34) Prior knowledge of small, but safe, determinacy and type-mode parameters can significantly tighten the search space around the solutions. These semantic characteristics of the background theory are typically expected as user input, but research on their automatically extraction from the background has also been pursued (McCreath & Sharma, 1995). 4.1.3 Incremental Search Another approach is to not restrict the hypothesis language, but to incrementally consider larger and larger subsets thereof. The whole hypothesis language will only be considered if we cannot find a model within one of these subsets. Srinivasan et al. (2003) propose a technique that explores human expertise to provide a relevance ordering on the set of background predicates. The technique follows a strategy of incrementally including sets of background knowledge predicates in decreasing order of relevance and has shown to yield good results. Another technique that incrementally increases the hypothesis space is Incremental Language Level Search (ILLS) (Camacho, 2002). It uses an iterative search strategy to, starting from one, progressively increase the upper-bound on the number of occurrences of a predicate symbol in the generated hypotheses. This technique is correct if a complete search is performed and Camacho report substantial efficiency improvements on several ILP applications. 4.2 Efficient Evaluation As described above, hypotheses are evaluated by metrics that make reference to their coverage over the training data. Coverage is calculated by matching (or testing) all examples against the hypothesis; this involves finding a substitution such that the body of one of the hypothesis’ clauses is true given the example and background knowledge. An often used approach in ILP to match hypotheses is to use logical querying. The logical querying approach to clause matching involves the use of a Prolog engine to evaluate the clause with the examples and background knowledge. The execution time to evaluate a query depends on the number of examples, number of resolution steps, and on the execution time of individual literals. Thus, scalability problems may arise when dealing with a great number of examples or/and when the computational cost to evaluate a rule is high. Query execution using SLDNF resolution grows exponentially with the number of literals in the query (Struyf, 2004). Hence, evaluating a single example can take a long time. Several techniques have been proposed to improve the efficiency of hypotheses evaluation. Firstly, the evaluation of a hypothesis can be optimized by transforming the hypothesis into an 37 equivalent one that can be more efficiently executed (Santos Costa et al., 2000; Santos Costa, Srinivasan, et al., 2003). An important characteristic of these techniques is that the transformations between equivalent hypothesis are correct. The transformation can be done at the level of individual hypotheses (Santos Costa et al., 2000; Struyf & Blockeel, 2003) or at the level of sets of hypotheses (Tsur et al., 1998; Blockeel et al., 2002). A different method to speedup evaluation explores the existing redundancy on the sets of hypotheses evaluated: similar hypotheses are generated and evaluated in batches, called query packs (Blockeel et al., 2002), thus avoiding the redundant repetition of the same proof steps in different, but similar, hypotheses. Approximate evaluation is another well-studied way of reducing the execution time of hypothesis evaluation. Stochastic matching (Sebag & Rouveirol, 1997), or stochastic theorem proving, was tested with the PROGOL ILP system, and has yielded considerable efficiency improvements, without sacrificing predictive accuracy or comprehensibility. This approach was further pursued by Giordana et al. (2000), making the benefits of replacing deterministic matching with stochastic matching clearly visible. A variety of other approximate matching schemes (Srinivasan, 1999; Kijsirikul et al., 2001; DiMaio & Shavlik, 2004; Bockhorst & Ong, 2004) have also been successfully tried. Another technique, called lazy evaluation,13 of examples (Camacho, 2003) aims at speeding up the evaluation of hypotheses by avoiding the unnecessary use of examples in the coverage computations, yielding considerable reduction of the execution time. The rationale underlying lazy evaluation is the following: a hypothesis is allowed to cover a small number of negative examples (the noise level) or none. If a clause covers more than the allowed number of negative examples it must be specialized. Lazy evaluation of negatives can be used when we are interested in knowing if a hypothesis covers more than the allowed number of negative examples or not. Testing stops as soon as the number of negative examples covered exceeds the allowed noise level or when there are no more negative examples to be tested. Therefore, the number of negative examples effectively tested may be very small, since the noise level is quite often very close to zero. If the evaluation function used does not involve negative coverage in its calculations, then this produces exactly the same results (clauses and accuracy) as the non-lazy approach but with a reduction on the number of negative examples tested. One may also allow positive coverage to be computed lazily (lazy evaluation of positives). A clause is either specialized (if it covers more positives than the best consistent clause found so far) or justifiably pruned away otherwise. When using lazy evaluation of positives it is only relevant to determine if a hypothesis covers more positives than the current best consistent hypothesis or not. We might then just evaluate the positive examples until we exceed the best cover so far. If the best cover is exceeded we retain the hypothesis (either accept it as final if it is consistent or refine it otherwise) or we may justifiably discard it. We need to evaluate its exact positive cover only when accepting a consistent hypothesis. In this latter case we don’t need to restart the positive coverage 38 computation from scratch, we may simply continue the test from the point where we left it before. Storing intermediate results during the evaluation for later use (i.e., by performing a kind of a cache) can be a solution to reduce the time spent in hypothesis evaluation. The techniques that follow this method are categorized as: improving the evaluation of the literals of a hypothesis (Rocha et al., 2005), or by reducing the number of examples tested (Cussens, 1996; Berardi et al., 2004). All these techniques are correct and attempt to improve time efficiency at the cost of increasing memory consumption. 4.3 Handling Large Datasets The explanation semantics used to formulate the task at hand has a profound influence on how data is represented, stored, and manipulated and, subsequently, a great impact on the performance of an ILP system. Under learning from entailment, examples may relate to each other, so they cannot be handled independently. Therefore, there is no separation of either the examples (apart from being positive or negative) or the background knowledge. Learning from interpretations, on the other hand, assumes that that the data exhibits a certain amount of locality and each example is represented as sub-database, i.e., a separate Prolog program, encoding its specific properties. This allows ILP techniques that operate under this semantics to scale up well (Blockeel et al., 1999). Naturally, this assumption makes learning from interpretations weaker than learning from entailment, but applications and purposes for which this semantics is sufficient, benefit from its inherent scalability. Learning from subsets of data is another way of dealing with large datasets. For instance, windowing is a well known technique that learns from subsets of data. It tries to identify a subset of the original data from which a theory of sufficient quality can be learnt. It as been shown (Quinlan, 1993; Fürnkranz, 1998) that this technique increases the predictive accuracy and reduces the learning time. In ILP, studies shown that windowing reduces the execution time while preserving the quality of the models found (Srinivasan, 1999; Fürnkranz, 1997). 4.4 Search Algorithms The hypothesis space determines the set of possible hypotheses that can be considered while searching for a good hypothesis. Several approaches to reduce the hypothesis space were described above. On the other hand, the search algorithm defines the order by which the hypotheses are considered and determines the search space (i.e., the hypotheses effectively considered during the search). The search algorithm used can have a great impact on efficiency, however, it can also have an impact on the quality of the hypothesis found. A wide number of search techniques have been used in ILP systems, namely breadth-first search (in PROGOL), depth-first search (in ALEPH), beam-search (Džeroski, 1993; Srinivasan, 39 2004), heuristic-guided hill-climbing variants (Quinlan, 1990; Srinivasan, 2004), and simulated annealing (Srinivasan, 2004; Serrurier et al., 2004), just to mention a few. The choice of one in detriment of another has several effects (Russell & Norvig, 2003), namely on memory consumption, execution time, and completeness. More advanced search techniques have been exploited in ILP systems. A genetic search algorithm was proposed in (Tamaddoni-Nezhad & Muggleton, 2000) but the impact on efficiency was not reported. Probabilistically searching large hypothesis space (Srinivasan, 2000) restricts the search space by sacrificing optimality. It consists in randomly selecting a fixed-size sample of clauses from the search space which, with high probability, contains a good clause. The evaluation of the technique on three real world applications showed reductions in the execution time without significantly affecting the quality of the hypothesis found. However, this approach has difficulties with ‘needle in a haystack’ problems, where very few good hypotheses exist. Randomized rapid restarts (Železný et al., 2003) combines (local) complete search with the probabilistic search. It performs an exhaustive search up to a certain point (time constrained) and then, if a solution is not found, restarts into randomly selected location of the search space, The application of the RRR technique in two applications yielded a drastic reduction of the search time at the cost of a small loss in predictive accuracy (Železný et al., 2003). 4.5 Parallelism Parallelism provides an attractive solution for improving efficiency. ILP systems may profit from exploiting parallelism by decreasing learning time, handling larger datasets, and improving the quality of the induced models. The exploitation of parallelism introduces several challenges. Designing and validating a parallel algorithm is often harder than designing and validating sequential algorithms. Performance issues are complex: splitting work into too many tasks may introduce significant overheads, whereas using fewer tasks may result in load imbalance and bad speedups. There are three main strategies to exploit parallelism in ILP systems are (Fonseca et al., 2005): parallel exploration of the search space (Dehaspe & De Raedt, 1995; Ohwada et al., 2000; Ohwada & Mizoguchi, 1999; Wielemaker, 2003); parallel hypothesis evaluation (Matsui et al., 1998; Konstantopoulos, 2003); and parallel execution of an ILP system over a partition of the data (Ohwada & Mizoguchi, 1999; Graham et al., 2003). A survey on exploiting parallelism in ILP is presented in (Fonseca et al., 2005). An evaluation of several parallel ILP algorithms showed that a good approach to parallelize ILP systems is one of the simplest to implement: divide the set of examples by the computers/processors available; run the ILP system in parallel on each subset; in the end, combine the theories found into a single one (Fonseca et al., 2005; Fonseca, 2006). This approach not only reduced the execution time but also improved predictive accuracy. 40 5 APPLICATIONS In this section we briefly outline and provide references to various real-world applications of ILP, from medicine and biology, to language technology where ILP systems have made significant contributions to the discovery of new scientific knowledge. Although we discuss in more detail applications in the three main areas of Life Sciences, Language Processing, and Engineering, ILP has been used in a variety of other domains. Examples of important applications of ILP must, at the very least, include domains such as music (Pompe et al., 1996; Tobudic & Widmer, 2003), the environment (Džeroski et al., 1995; Blockeel et al., 2004), intelligence analysis (Davis, Dutra, et al., 2005), and mathematical discovery (Colton & Muggleton, 2003; Todorovski et al., 2004). 5.1 Life Sciences Inductive Logic Programming has been applied in a wide variety of domains of the Life Sciences, ranging over domains as diverse as Medical Support Systems (Carrault et al., 2003) and Computational Biochemistry (Srinivasan et al., 1994; Page & Craven, 2003). Clinical data is one of the major sources of challenging datasets for ILP. To cite but a few example applications we will mention successful work on the characterization of cardiac arrhythmias (Quiniou et al., 2001), intensive care monitoring (Morik et al., 1999), diagnosis support systems for rheumatic diseases (Zupan & Džeroski, 1998) or breast cancer (Davis, Burnside, et al., 2005). One of the major applications of Inductive Logic Programming so far has been in the area of Structure-Activity Relationships (SAR), the task of predicting the activity of drug molecules based on their structure. Early examples of this work include detecting mutagenic (Srinivasan et al., 1994) and carcinogenic (Srinivasan et al., 1997) properties in compounds. In the continuation, researchers have used ILP for 3D-SAR, where one uses a 3D description of the main elements in the compound to find pharmacophores that explain drug activity (Finn et al., 1998). Among the successful examples of ILP applications one can mention pharmacophores for dopamine agonists, ACE inhibitors, Thermolysin inhibitors, and antibacterial peptides (Enot & King, 2003). A related application with a different approach is the work in Diterpene structure elucidation by Džeroski et al. (1996). ILP has also made significant contributions to the expanding area of Bio-informatics and Computational Biology. One major interest in this area has been in explaining protein structure, including secondary structure (Muggleton, King, & Sternberg, 1992; Mozetic, 1998) and fold prediction (Turcotte et al., 2001). Another very exciting area of ILP research is helping understand cell machinery; the work of Bryant et al. (2001) should be mentioned as the seminal work on understanding metabolic pathways of yeast. Finally, in genetics, recent work has also achieved 41 Aclause is a disjunction of literals. All the variables in a clause are implicitly universally quantified. The empty clause and the logical constant false are represented by . A Horn clause is a disjunction of any number of negated literals and up to one non-negated literal, for example: h∨ ¬l1∨ ¬l2... ∨ ¬ln ¬l1∨ ¬l2... ∨ ¬ln h The positive literal is called the head of the clause and the negative literals (if any) are collectively known as the body. Horn clauses can be equivalently represented as sets of literals that are meant to be logically or’ed together or as Prolog clauses: {h, ¬l1,¬l2, . . . ¬ln}h←l1,l2, . . . ln. {¬l1,¬l2, . . . ¬ln} ⇐⇒ ⊥ ← l1,l2, . . . ln. {h}h. Adefinite Horn clause is a Horn clause with exactly one positive literal, for example: h∨ ¬l1∨ ¬l2... ∨ ¬ln h Asubstitution is a function that maps a set of variables to a set of terms or variables. We apply a substitution to a term by replacing all variables in the term with the terms or variables indicated by the mapping. We usually denote a substitution as a set of from/to pairs and we write Aθ to denote the result of applying substitution θto term A. For example, if θ={X/Z, Y/aureliano} and A= parent(X, Y )then Aθ = parent(Z, aureliano). Related to substitution is the concept of unification. Unification is the operation of making two terms identical by substitution. Such substitutions are called unifiers of the terms. The most general unifier is the unifier which minimally instantiates the two terms. Apredicate is a disjunction of definite Horn clauses where (a) no pair of clauses shares a common variable and (b) the heads of the clauses are the same up to substitution, i.e. they are terms with the same functor and arity. A program is a conjunction of predicates where no pair of predicates shares a common variable. The empty program and the logical constant true are represented by . The Herbrand base of a clause, predicate, or program is the set of all ground (variable-free) atoms composed from symbols found in the clause, predicate, or program. An interpretation is a total function from ground atoms to {true,false}. A Herbrand interpretation for program Pis an interpretation for all the atomic symbols in the Herbrand base of P. The valuation of a non-atomic clauses, predicates, and programs can be derived from the definitions of the logical connectives (conjunction, disjunction, negation, implication, existential and universal quantification) used to construct them from atoms. The logical connectives are set-theoretically defined in the usual manner (intersection, union, complement, etc) which we shall not re-iterate here. 48 We shall use the term interpretation to mean Herbrand interpretation. An interpretation Mfor Pis a model of Pif and only if Pis true under M. Every program Phas a unique minimal Herbrand model M+(P)such that every atom ain Pis true under M+(P)if and only if ais true under all models of P. Let Pand Qbe programs. We say that Pentails Q(PQ) if and only if every model of Pis also a model of Q. A clause, predicate, or program is satisfiable if and only if there exists a model for it. Equivalently, Pis satisfiable if and only if P2and unsatisfiable if and only if P . A query is a conjunction of positive literals. Posing a query Qto a program Pamounts to asking about the satisfiability of PQ; if the program P2Qis satisfiable then the query gets an affirmative answer. Computational algorithms for answering first-order logical queries rely on deductive methods which can infer semantic entailment by syntactic manipulation of the programs involved. Deductive inference that deduces Dfrom Conly when CD(according to the set-theoretic, semantic definitions of the logical symbols and connectives) is called sound and deductive inference that deduces Dfrom Cfor all C, D where CDis called complete. Tableaux methods and resolution and sound and complete deductive methodologies. Selection linear definite resolution (SLD resolution) is an algorithm for resolving define clause programs. SLD negation-as-failure resolution (SLDNF resolution) extends SLD resolution to normal clause programs, which admit negative literals as premises, but only under the closed world assumption (CWA). CWA is the assumption that statements that cannot be proved true, are not true. Prolog is a resolution engine that operates under the CWA to perform SLDNF resolution. Almost all ILP systems (and especially predictive ILP systems) rely on a Prolog implementation for inferring entailment relationships. Notes 1To the best of our knowledge, Muggleton was the first to use the term as the title of his invited talk at the first conference on Algorithmic Learning Theory (Tokyo, 1990). It is noteworthy that Muggleton & Feng presented a research paper on the ILP system GOLEM at the same conference where the term does not appear at all. The term ILP was formally introduced by Muggleton one year later at his landmark publication with the New Generation Computing journal (Muggleton, 1991). 2Arguably, this definition may nowadays be somewhat narrow. The representation and learning strategies used in ILP are germane to work such as relational instance based learning (Emde & Wettschereck, 1996; Horváth et al., 2001) and Analogical Prediction (Muggleton & Bain, 1999). ILP is also a key influence in the development of statistical relational learning, that often combines logical and statistical modelling. 3Inferring entailment is necessary for validating a hypothesis under learning from entailment semantics. Similarly, learning under interpretations requires a procedure for inferring whether an example is a model of a hypothesis. 4Only a second-order background theory would be able to represent such restrictions, and handling such a background theory would be far beyond the scope of current ILP. The external mechanisms currently used, effectively amount to ‘mildly’ second-order expressivity, that allows for certain kinds of restrictions to be represented and extralogically tested. It might, in theory, be possible to identify a logic which captures only and all of these restrictions and 49 thus incorporate them into the background theory. Such a line of research has not, however, been pursued by the ILP community which builds upon Logic Programming and first-order SLDNF resolution engines. 5Variable depth is defined as the shortest link path to a head variable in various of Muggleton’s publications, including the original definition (Muggleton & Feng, 1990, p. 8) and the Journal of Logic Programming article about the theory of ILP (Muggleton & De Raedt, 1994, p. 657). There is one notable exception, however, as Muggleton (1995, p 11) defines depth to be the longest path to the variable in his PROGOL article. The authors tested current ILP implementations, and found them conforming to the original definition. 6Variables Xand Yhave depth 0; variables Uand Whave depth 1; variable Vhas depth 2. 7Strictly speaking, traversal operators map conjunctions of clauses to sets of conjunctions of clauses. However, we typically focus on a single clause and perceive this mapping as being applied to one of the clauses in the conjunction in the presence of a background. 8Z/W is forced in order to unify the ancestor/2 literals, but then parent(W,Y) cannot unify with either parent(Z,Y) or parent(W,Z) unless we further substitute X/Z, which would render the heads ununifiable. 9Muggleton (1995, Section 6) offers a formal and complete exposition of this reduction of implication to a θsubsumption search and its logical foundations. 10Not to be confused with what is usually called bottom in logic programming, namely the empty predicate. There is an analogy, however, in that in the sense used here, the bottom is also the ‘most specific’ clause. 11For θ1={X/A, Y/B, Z/E, W/G}we get Aθ ⊆⊥1and Bθ ⊆⊥1. 12‘Pseudo’ in the sense that a true posterior probability can only be derived from a true prior probability, whereas here we only have an empirical approximation of the true prior. 13The term is used in the sense of making the minimal computation to obtain useful information. 14Many grammatical formalisms of greater computational complexity, for example, Head Phrase-driven Structure Grammar (HPSG), have also been proposed in the literature and gained wide acceptance. It is, however, the general consensus that grammatical formalisms beyond DCGs are justified on grounds of linguistic-theoretical conformance and compression on the grammar and that definite-clause grammars are powerful enough to capture most of the actual linguistic phenomena. 15The propositional theory describes syllable structure with 674 prevocalic and 456 postvocalic clauses. The firstorder theory comprises 13 and 93 clauses, resp. When no language-specific prior phonological knowledge is used, the exact numbers are: for the propositional theory 577 clauses for the prevocalic and 577 clauses for the postvocalic material, and for the first-order theory 145 and 36 clauses, resp. References Anthony, S., & Frisch, A. M. (1999, January). Cautious induction: An alternative to clause-at-atime induction in inductive logic programming. New Generation Computing,17(1), 25–52. Bayes, T. (1763). An essay towards solving a problem in the doctrine of chances. Philosophical Transactions of the Royal Society of London,53, 370–418. Berardi, M., Varlaro, A., & Malerba, D. (2004). On the effect of caching in recursive theory learning. In Proceedings of the 14th international conference on inductive logic programming (pp. 44–62). Berlin: Springer-Verlag. 50 Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Ramon, J., & Vandecasteele, H. (2002). Improving the efficiency of Inductive Logic Programming through the use of query packs. Journal of Machine Learning Research,16, 135–166. Blockeel, H., & De Raedt, L. (1998). Top-down induction of first-order logical decision trees. Artificial Intelligence,101(1–2), 285–297. Blockeel, H., Džeroski, S., Kompare, B., Kramer, S., Pfahringer, B., & Laer, W. V. (2004). Experiments in predicting biodegradability. Applied Artificial Intelligence,18(2), 157–181. Blockeel, H., Raedt, L. D., Jacobs, N., & Demoen, B. (1999). Scaling up inductive logic programming by learning from interpretations. Data Mining and Knowledge Discovery,3(1), 59–93. Bockhorst, J., & Ong, I. M. (2004). FOIL-D: Efficiently scaling FOIL for multi-relational data mining of large datasets. In Proceedings of the 14th international conference on inductive logic programming (pp. 63–79). Booij, G. (1995). The phonology of Dutch. Oxford: Clarendon Press. Boström, H. (1996). Theory-guided induction of logic programs by inference of regular languages. In Proc. of the 13th international conference on machine learning (pp. 46–53). San Francisco: Morgan Kaufmann. Boström, H. (1998). Predicate invention and learning from positive examples only. In Proceedings of the tenth european conference on machine learning (pp. 226–237). Berlin: Springer Verlag. Boström, H. (2000, June). Induction of recursive transfer rules. In J. Cussens & S. Džeroski (Eds.), Lecture notes in computer science: Vol. 1925. Learning Language in Logic (pp. 237– 246). Berlin: Springer-Verlag. Botta, M., Giordana, A., Saitta, L., & Sebag, M. (2003). Relational learning as search in a critical region. Journal of Machine Learning Research,4, 431–463. Bryant, C., Muggleton, S., Oliver, S., Kell, D., Reiser, P., & King, R. (2001). Combining Inductive Logic programming, Active Learning and robotics to discover the function of genes. Electronic Transactions on Artificial Intelligence,5(B1), 1–36. Burnage, G. (1990). CELEX: A guide for users. Cairns, C., & Feinstein, M. (1982). Markedness and the theory of syllable structure. Linguistic Inquiry,13. 51 Califf, M. E., & Mooney, R. J. (1999, July). Relational learning of pattern-match rules for information extraction. In Proceedings of the 17th national conference on artificial intelligence. Orlando, FL. Camacho, R. (1998). Inducing models of human control skills. In C. Nedellec & C. Rouveirol (Eds.), Lecture notes in computer science: Vol. 1398. ECML (pp. 107–118). Berlin: SpringerVerlag. Camacho, R. (2000). Inducing models of human control skills using machine learning algorithms. Unpublished doctoral dissertation, Department of Electrical Engineering and Computation, Universidade do Porto. Camacho, R. (2002). Improving the efficiency of ILP systems using an incremental language level search. In Annual machine learning conference of Belgium and the Netherlands. Camacho, R. (2003). As lazy as it can be. In P. Doherty, B. Tassen, P. Ala-Siuru, & B. Mayoh (Eds.), The eighth Scandinavian conference on Artificial Intelligence (SCAI ’03), Bergen, Norway, November 2003 (pp. 47–58). Carrault, G., Cordier, M., Quiniou, R., & Wang, F. (2003, July). Temporal abstraction and Inductive Logic Programming for arrhythmia recognition from electrocardiograms. Artificial Intelligence in Medicine,28(3), 231–63. Cestnik, B. (1990). Estimating probabilities: A crucial task in machine learning. In European conference on artificial intelligence (pp. 147–149). Chomsky, N. (1957). Syntactic structures. The Hague: Mouton. (first mention of trees and such) Clark, P., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning,3(4), 261–83. Cohen, W. W. (1994). Grammatically biased learning: Learning logic programs using an explicit antecedent description language. Artificial Intelligence,68, 303–366. Colton, S., & Muggleton, S. (2003). ILP for mathematical discovery. In T. Horváth (Ed.), Lecture notes in computer science: Vol. 2835. ILP (pp. 93–111). Berlin: Springer-Verlag. Craven, M., & Slattery, S. (2001, April). Relational learning with statistical predicate invention: Better models for hypertext. Machine Learning,43(1/2), 97–119. Cussens, J. (1993). Bayes and pseudo-Bayes estimates of conditional probabilities and their reliability. In Proceedings of the european conference on machine learning (ecml93) (pp. 136– 152). Berlin: Springer Verlag. 52 Cussens, J. (1996). Part-of-speech disambiguation using ILP (Tech. Rep. No. PRG-TR-25-96). Oxford University Computing Laboratory. Cussens, J. (1997). Part-of-speech tagging using progol. In S. Džeroski & N. Lavraˇ c (Eds.), Lecture notes in artificial intelligence: Vol. 1297. Proceedings of the 7th International Workshop on Inductive Logic Programming (pp. 93–108). Berlin: Springer-Verlag. Cussens, J. (2000). Stochastic logic programs: Sampling, inference and applications. In C. Boutilier & M. Goldszmidt (Eds.), Proceedings of the 16th annual conference on uncertainty in artificial intelligence. Morgan Kaufmann. Cussens, J., & Džeroski, S. (Eds.). (2000). Learning language in logic. Berlin: Springer-Verlag. Cussens, J., & Pulman, S. (2000). Experiments in inductive chart parsing. In J. Cussens & S. Džeroski (Eds.), Lecture notes in artificial intelligence: Vol. 1925. Learning Language in Logic. Berlin: Springer-Verlag. David, P. C., & Srinivasan, A. (2003, August). ILP: A short look back and a longer look forward. Journal of Machine Learning Research(4), 415–430. Davis, J., Burnside, E. S., Dutra, I. d. C., David, P. C., & Santos Costa, V. (2005). Knowledge discovery from structured mammography reports using inductive logic programming. In American medical informatics association 2005 annual symposium. Davis, J., Dutra, I. d. C., Page, C. D., & Santos Costa, V. (2005). Establishing identity equivalence in multi-relational domains. In Proceedings of the 2005 International Conference on Intelligence Analysis. Dehaspe, L., & De Raedt, L. (1995). Parallel inductive logic programming. In Proceedings of the MLnet familiarization workshop on statistics, machine learning and knowledge discovery in databases. Dehaspe, L., & De Raedt, L. (1996, July). DLAB:a declarative language bias for concept learning and knowledge discovery engines (Tech. Rep. No. CW 214). Leuven: Department of Computing Science, K.U.Leuven. Dehaspe, L., & De Raedt, L. (1997). Mining association rules in multiple relations. In S. Džeroski & N. Lavraˇ c (Eds.), Lecture notes in artificial intelligence: Vol. 1297. Proceedings of the 7th International Workshop on Inductive Logic Programming (pp. 125–132). Berlin: SpringerVerlag. Dehaspe, L., & Toironen, H. (2000). Relational data mining. In (pp. 189–208). Berlin: SpringerVerlag. 53 De Raedt, L. (1997). Logical settings for concept-learning. Artificial Intelligence,95(1), 187–201. De Raedt, L., & Blockeel, H. (1997). Using logical decision trees for clustering. In Proceedings of the 7th international workshop on inductive logic programming (pp. 133–140). Springer-Verlag. De Raedt, L., & Dehaspe, L. (1996). Clausal discovery (Tech. Rep. No. CW 238). Leuven: Department of Computing Science, K.U.Leuven. De Raedt, L., & Dehaspe, L. (1997). Learning from satisfiability. In Proceedings of the ninth dutch conference on artificial intelligence (NAIC’97) (pp. 303–312). De Raedt, L., & Džeroski, S. (1994). First-order jk-clausal theories are pac-learnable. Artificial Intelligence,70(1-2), 375–392. De Raedt, L., Kersting, K., & Torge, S. (2005). Towards learning stochastic logic programs from proof-banks. In Proceedings of the 23th national conference on artificial intelligence, (AAAI 2005) (pp. 752–757). DiMaio, F., & Shavlik, J. W. (2004). Learning an approximation to inductive logic programming clause evaluation. In Proceedings of the 14th international conference on inductive logic programming (pp. 80–97). Dolšak, B., Bratko, I., & Jezernik, A. (1994). Finite element mesh design: an engineering domain for ILP applications. In Proc. of the 4th international workshop on inductive logic programming (ILP-94), Bad Honnef/Bonn, Germany, September 12–14. Dolšak, B., Bratko, I., & Jezernik, A. (1997). Application of Machine Learning in finite element computation. In R. Michalski, I. Bratko, & M. Kubat (Eds.), Machine learning, data mining and knowledge discovery: Methods and applications. John Wiley and Sons. Džeroski, S. (1993). Handling imperfect data in inductive logic programming. In Proceedings of the 4th scandinavian conference on artificial intelligence (pp. 111–125). IOS Press. Džeroski, S., Dehaspe, L., Ruck, B., & Walley, W. (1995). Classification of river water quality data using machine learning. In Proceedings of the 5th international conference on the development and application of computer techniques to environmental studies. Džeroski, S., & Erjavec, T. (1997). Induction of Slovene nominal paradigms. In N. Lavrac & S. Džeroski (Eds.), Lecture notes in computer science: Vol. 1297. ILP (pp. 141–148). Berlin: Springer-Verlag. Džeroski, S., Jacobs, N., Molina, M., & Moure, C. (1998). ILP experiments in detecting traffic problems. In C. Nedellec & C. Rouveirol (Eds.), Lecture notes in computer science: Vol. 1398. ECML (pp. 61–66). Berlin: Springer-Verlag. 54 Džeroski, S., Schulze-Kremer, S., Heidtke, K., Siems, K., & Wettschereck, D. (1996). Applying ILP to diterpene structure elucidation from 13C NMR spectra. In Proceedings of the MLnet Familiarization Workshop on Data Mining with Inductive Logic Programing (pp. 12–24). Emde, W., & Wettschereck, D. (1996). Relational instance-based learning. In L. Saitta (Ed.), Proceedings of the 1996 international machine learning conference (p. 122-130). Enot, D. P., & King, R. D. (2003). Application of inductive logic programming to structure-based drug design. In N. Lavrac, D. Gamberger, H. Blockeel, & L. Todorovski (Eds.), Lecture notes in computer science: Vol. 2838. Proceedings of the 7th European Conference on Principles of Data Mining and Knowledge Discovery (pp. 156–167). Berlin: Springer-Verlag. Esposito, F., Malerba, D., & Semeraro, G. (1993). Automated acquisition of rules for document understanding. In Proceedings of the 2nd international conference on document analysis and recognition (pp. 650–654). Finn, P. W., Muggleton, S. H., Page, C. D., & Srinivasan, A. (1998). Pharmacophore discovery using the inductive logic programming system PROGOL. Machine Learning,30(2-3), 241-270. Fonseca, N. A. (2006). Parallelism in inductive logic programming systems. Unpublished doctoral dissertation, University of Porto. Fonseca, N. A., Santos Costa, V., Camacho, R., & Silva, F. (2004). On avoiding redundancy in Inductive Logic Programming. In R. Camacho, R. D. King, & A. Srinivasan (Eds.), Lecture notes in artificial intelligence: Vol. 3194. Proceedings of the 14th International Conference on Inductive Logic Programming, Porto, Portugal, September 2004 (pp. 132–146). Berlin: Springer-Verlag. Fonseca, N. A., Silva, F., Santos Costa, V., & Camacho, R. (2005). Strategies to paralilize ILP systems. In Lecture notes in ai. 15th International Conference on Inductive Logic Programming (ILP 2005), Bonn, August 2005 (pp. 136–153). Berlin: Springer-Verlag. (Best paper ILP 2005) Fürnkranz, J. (1997, August). Dimensionality reduction in ILP: a call to arms. In L. De Raedt & S. H. Muggleton (Eds.), Proceedings of the IJCAI-97 workshop on frontiers of inductive logic programming (pp. 81–86). Nagoya, Japan. Fürnkranz, J. (1998). Integrative windowing. Journal of Machine Learning Research,8, 129–164. Fürnkranz, J., & Flach, P. (2003). An analysis of rule evaluation metrics. In Proceedings of the 20th international conference on machine learning (icml-03). San Francisco: Morgan Kaufmann. 55 Giordana, A., Saitta, L., Sebag, M., & Botta, M. (2000). Analyzing relational learning in the phase transition framework. In Proceedings of the 17th international conference on machine learning (pp. 311–318). San Francisco: Morgan Kaufmann. Goadrich, M., Oliphant, L., & Shavlik, J. W. (2004). Learning ensembles of first-order clauses for recall-precision curves: A case study in biomedical information extraction. In R. Camacho, R. D. King, & A. Srinivasan (Eds.), Lecture notes in computer science: Vol. 3194. ILP (pp. 98–115). Berlin: Springer-Verlag. Graham, J., Page, C. D., & Kamal, A. (2003). Accelerating the drug design process through parallel inductive logic programming data mining. In Proceeding of the computational systems bioinformatics (csb’03). IEEE. Gunetti, D., & Ruffo, G. (1999). Intrusion Detection through Behavioral Data. In S. Wrobel (Ed.), Lecture notes in computer science. Proc. of The Third Symposium on Intelligent Data Analysis. Berlin: Springer-Verlag. Hayes-Roth, F. (1974). Schematic classification problems and their solution. Pattern Recognition, 6(2), 105-113. Horváth, T. (Ed.). (2003). Inductive logic programming: Proceeding of the 13th international conference, ILP 2003, Szeged, Hungary, September 29–October 1, 2003. Berlin: SpringerVerlag. Horváth, T., Wrobel, S., & Bohnebeck, U. (2001, April). Relational instance-based learning with lists and terms. Machine Learning,43(1/2), 53–80. Jorge, A., & Brazdil, P. (1995). Architecture for iterative learning of recursive definitions. In L. De Raedt (Ed.), Proceedings of the 5th international workshop on inductive logic programming (pp. 95–108). Department of Computer Science, Katholieke Universiteit Leuven. Kersting, K., & Raedt, L. D. (2001, November). Bayesian logic programs (Tech. Rep. No. 151). Georges-Koehler-Allee, D-77110, Freiburg: Institute for Computer Science, University of Freiburg. Kersting, K., & Raedt, L. D. (2002). Basic principles of learning bayesian logic progras (Tech. Rep. No. 174). Georges-Koehler-Allee, D-77110, Freiburg: Institute for Computer Science, University of Freiburg. Kijsirikul, B., Sinthupinyo, S., & Chongkasemwongse, K. (2001). Approximate match of rules using backpropagation neural networks. Machine Learning,44(3), 273–299. 56 King, R. D. (2004). Applying inductive logic programming to predicting gene function. AI Magazine,25(1), 57–68. King, R. D., Whelan, K. E., Jones, F. M., Reiser, P. G., Bryant, C. H., Muggleton, S. H., et al. (2004, January). Functional genomic hypothesis generation and experimentation by a robot scientist. Nature,427(6971), 247–252. Ko, C. (2000). Logic induction of valid behavior specifications for intrusion detection. In SP 2000: Proceedings of the 2000 IEEE symposium on security and privacy. Washington, DC, USA: IEEE Computer Society. Konstantopoulos, S. (2003, September). A data-parallel version of Aleph. In Proceedings of the workshop on parallel and distributed computing for Machine Learning, co-located with ECML/PKDD’2003. Dubrovnik, Croatia. Langley, P. (1996). Elements of machine learning. Morgan Kaufmann. Lavrac, N., & Džeroski, S. (Eds.). (1997). Proceedings of the 7th international workshop on inductive logic programming (ILP-97), Prague, Czech Republic, September 17-20, 1997. Berlin: Springer-Verlag. Lavraˇ c, N., Flach, P., & Zupan, B. (1999, June). Rule evaluation measures: A unifying view. In S. Džeroski & P. Flach (Eds.), Lecture notes in artificial intelligence: Vol. 1634. Proceedings of the 9th International Workshop on Inductive Logic Programming (pp. 174–185). Berlin: Springer-Verlag. Lloyd, J. W. (1997). Foundations of logic programming (2nd ed.). Berlin: Springer-Verlag. Malerba, D., Esposito, F., Altamura, O., Ceci, M., & Berardi, M. (2003). Correcting the document layout: A machine learning approach. In Icdar (p. 97-). IEEE Computer Society. Matsui, T., Inuzuka, N., Seki, H., & Itoh, H. (1998). Comparison of three parallel implementations of an induction algorithm. In 8th int. parallel computing workshop (pp. 181–188). Singapore. Matwin, S., & Sammut, C. (Eds.). (2003). Proceedings of the 12th international workshop on inductive logic programming (ilp 2002). Berlin: Springer Verlag. McCreath, E., & Sharma, A. (1995, November). Extraction of meta-knowledge to restrict the hypothesis space for ILP systems. In X. Yao (Ed.), Proceedings of the eighth australian joint conference on artificial intelligence (pp. 75–82). World Scientific. Michalski, R. S. (1973). Aqval/1-computer implementation of a variable-valued logic system vl1 and examples of its application to pattern recognition. In Proceeding of the first international joint conference on pattern recognition (p. 3-17). 57 Winston, P. H. (1970). Learning structural descriptions from examples. Unpublished doctoral dissertation, MIT. Wrobel, S. (1997). An algorithm for multi-relational discovery of subgroups. In Proceedings of the first european symposium on principles of data mining and knowledge discovery (pp. 78–87). Springer-Verlag. Zelle, J. M., & Mooney, R. J. (1996). Learning to parse database queries using Inductive Logic Programming. In dunno (Ed.), Proceedings of the 13th national conference on artificial intelligence, Portland, USA. Zupan, B., & Džeroski, S. (1998). Acquiring background knowledge for machine learning using function decomposition: a case study in rheumatology. Artificial Intelligence in Medicine,14(1– 2), 101-117. 64 Index A∗search, 9 background knowledge, 4 bottom clause, 8, 12, 15 clause, 5 Definite Horn, 5 clause body, 6 clause head, 6 concept language, 4 consistent, 6 Definite Semantics, 5 evaluation function, 11 example setting, 5, 6 explanation semantics, 4 foothill, 10 heuristic, 9 hypothesis language, 4 ILP, 4 descriptive, 5 non-monotonic, 5 predictive, 5 ILP setting, 4 explanatory, 5 normal, 5 strong, 5 Inductive Logic Programming, 4 inverse resolution, 14 language bias, 4 lattice, 7 learning from entailment, 4, 5 learning from interpretations, 4 local maxima, 10 local minima, 10 minimal Herbrand model, 6 most specific clause, 15 necessary, 6 normal semantics, 5 operator complete, 8 refinement, 7 sound, 8 overfitting, 16 overgeneralizing, 16 posonly, 18 posterior distribution, 18 Predicates, 6 preference bias, 11 prior distribution, 18 Programs, 6 RLGG, 22 Robinson’s Rule, 13 search best-first, 9 bottom-up, 8 breadth-first, 9 depth-first, 9 depth-limit, 9 greedy best-first, 9 iterative depth-first, 9 local, 10 hill-climbing search, 10 open-ended, 8 65 top-down, 8 seed, 15 semantic bias, 11 semi-lattice, 7 sequential cover, 7 sufficient, 6 syntactic bias, 11 top clause, 8, 12 66