
## 2. Inductive Logic Programming

Inductive logic programming (Muggleton & De Raedt, 1994) is situated in the intersection of machine learning or data mining on the one hand, and logic programming on the other hand. It shares with the former fields the goal of finding patterns in data, patterns that can be used to build predictive models or to gain insight in the data. With logic programming it shares the use of clausal first order logic as a representation language for both data and hypotheses. In the remainder of this text we will use some basic notions from logic programming, such as literals, conjunctive queries, and variable substitutions. We will use Prolog notation throughout the paper. For an introduction to Prolog and logic programming see Bratko (1990).

Inductive logic programming can be used for many different purposes, and the problem statements found in ILP papers consequently vary. In this article we consider the so-called learning from interpretations setting (De Raedt & Dzeroski, 1994; De Raedt, 1997). It has been argued elsewhere that this setting, while slightly less powerful than the standard ILP setting (it has problems with, e.g., learning recursive predicates), is sufficient for most practical purposes and scales up better (Blockeel et al., 1999).

We formulate the learning task in such a way that it covers a number of different problem statements.  More specifically, we consider the problem of detecting for a set of conjunctive queries for which instantiations of certain variables each query succeeds. These variables are called key variables, and a grounding substitution for them is called a key instantiation.

The intuition is that an example in the learning task is uniquely identified by a single key instantiation.

The link with ILP systems that learn clauses is then as follows. The search performed by an ILP system is directed by regularly evaluating candidate clauses. Let us denote such a candidate clause by Head(X) {{ Body(X,Y) where X represents a vector of variables appearing in the head of the clause and Y represents additional variables that occur in the body. We assume that the head is a single literal and that a list of examples is given, where each example is of the form Head(X)0 with 0 a substitution that grounds X. Examples may be labelled (e.g., as positive or negative), but this is not essential in our setting. While an example can be represented as a fact Head ( X ) θ when learning definite Horn clauses, we can also consider it just a tuple X0. Both notations will be used in this paper.

Intuitively, when positive and negative examples are given, one wants to find a clause that covers as many positive examples as possible, while covering few or no negatives. Whether a single example Head(X)0 is covered by the clause or not can be determined by running the query ? - Body (X, Y) 0. In other words, evaluating a clause boils down to running a number of queries consisting of the body of the clause. For simplicity of notation, we will often denote a conjunctive query by just the conjunction ( without the ?— symbol).

In some less typical ILP settings, the ILP algorithm does not search for Horn clauses but rather for general clauses, e.g., CLAUDIEN (De Raedt & Dehaspe, 1997) or for frequent patterns that can be expressed as conjunctive queries, e.g., WARMR(Dehaspe & Toivonen, 199).  These settings can be handled by our approach as well:  all that is needed is a mapping from hypotheses to queries that allow to evaluate these hypotheses. Such a mapping is defined by De Raedt and Dehaspe (1997) for Claudien; for Warmr it is trivial.