The task of predicting which relations are true based on the truth of other relations has mainly been carried out in the framework of logic programming, and so is typically called inductive logic programming.

The input to an inductive logic programming learner includes the following:

• •

  $A$ is a set of atoms whose definitions the agent is learning.

• •

  $E^{+}$ is a set of ground instances of elements of $A$, called the positive examples, that are observed to be true.

• •

  $E^{-}$ is a set of ground instances of elements of $A$, called the negative examples, that are observed to be false.

• •

  $B$, the background knowledge, is a set of clauses that define relations that can be used in the learned logic programs.

• •

  $H$ is a space of possible hypotheses. $H$ is often represented implicitly as a set of operators that can generate the possible hypotheses. Each hypothesis is a logic program.

The aim is to find a simplest hypothesis $h\in H$ such that

That is, the hypothesis implies the positive evidence and does not imply the negative evidence. It must be consistent with the negative evidence being false.

The aim is to find an element of the version space, where the elements of the version space are logic programs. This is similar to the definition of abduction, in which the knowledge base in abduction corresponds to the background knowledge. The hypothesis space of inductive logic programming is the set of logic programs. The second condition corresponds to consistency.

Assume that there is a single target $A=\{t(X_1,\mathrm{\dots },X_n)\}$ The hypothesis space consists of possible definitions for this relation using a logic program.

There are two main strategies used in inductive logic programming:

• •

  The first strategy is to start with the simplest hypotheses and make them more complicated to fit the data. Because the logic program only states positive facts, the simplest hypothesis is the empty program, which specifies that $t(X_1,\mathrm{\dots },X_n)$ is always false. This is is the most specific hypothesis, but is not correct unless $E^{+}$ is empty. The second simplest hypothesis is the most general hypothesis, which is simply that $t(X_1,\mathrm{\dots },X_n)$ is always true. This hypothesis implies the positive examples, but it also implies the negative examples, if any exist. One strategy involves a general-to-specific search. It tries to find the simplest hypothesis that fits the data by searching the hypothesis space from the most general hypothesis to more complex hypotheses, always implying the positive examples, until a hypothesis that does not imply the negative examples is found.

• •

  The second strategy is to start with a hypothesis that fits the data and to make it simpler while still fitting the data. A hypothesis that fits the data is the set of positive examples. This strategy involves a specific-to-general search: start with the very specific hypothesis in which only the positive examples are true, and then generalize the clauses, avoiding the negative cases.

Here we expand on the general-to-specific search for definite clauses. The initial hypothesis contains a single clause:

A specialization operator takes a set $G$ of clauses and returns a set $S$ of clauses that specializes $G$. To specialize means that $S\vDash G$.

The following are three primitive specialization operators:

• •

  Split a clause in $G$ on condition $c$. Clause $a\leftarrow b$ in $G$ is replaced by two clauses: $a\leftarrow b\wedge c$ and $a\leftarrow b\wedge \mathrm{\neg }c$.

• •

  Split a clause $a\leftarrow b$ in $G$ on a variable $X$ that appears in $a$ or $b$. Clause $a\leftarrow b$ is replaced by the clauses

  	$a\leftarrow b\wedge X=t_1.$
  	$\mathrm{\dots }$
  	$a\leftarrow b\wedge X=t_k.$

  where the $t_i$ are terms.

• •

  Remove a clause that is not necessary to prove the positive examples.

The last operation changes the predictions of the clause set. Those cases no longer implied by the clauses are false.

These primitive specialization operators are used together to form the operators of $H$. The operators of $H$ are combinations of primitive specialization operations designed so that progress can be evaluated using a greedy look-ahead. That is, the operators are defined so that one step is adequate to evaluate progress.

The first two primitive specialization operations should be carried out judiciously to ensure that the simplest hypothesis is found. An agent should carry out the splitting operations only if they make progress. Splitting is only useful when combined with clause removal. For example, adding an atom to the body of a clause is equivalent to splitting on the atom and then removing the clause containing the negation of the atom. A higher-level specialization operator may be to split on the atom $prop(X,type,T)$ for some variable $X$ that appears in the clause, split on the values of $T$, and remove the resulting clauses that are not required to imply the positive examples. This operator makes progress on determining which types are useful.

Figure 15.2 shows a nondeterministic algorithm for the top-down induction of a logic program. It maintains a single hypothesis that it iteratively improves until finding a hypothesis that fits the data or until it fails to find such a hypothesis. The “choose” of line 15 can be implemented by search.

At each time step it chooses an operator to apply with the constraint that every hypothesis entails the positive examples. This algorithm glosses over two important details:

• •

  which operators to consider and

• •

  which operator to select.

The operators should be at a level so that they can be evaluated according to which one is making progress toward a good hypothesis. In a manner similar to decision tree learning, the algorithm can perform a myopically optimal choice. That is, it chooses the operator that makes the most progress in minimizing the error. The error of a hypothesis can be the number of negative examples that are implied by the hypothesis.