Artificial
Intelligence

14.2 Learning with Individuals and Relations

Learning in terms of individuals and relations allows for learning where the structure of relationships is important for prediction. The learning methods presented in Chapter 7 assumed that the feature values are meaningful; something useful could be predicted about a case by using the values of features. However, when the examples are about individuals and relations, the value of a property may be a meaningless name of an individual. It is only by considering the attributes of the individual that the name denotes, and its relationship to other individuals, that an agent is able produce meaningful predictions. The learned knowledge can also be applied to individuals that did not appear in the training set.

Because much of this work has been done in the context of logic programming, it is often 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 the set of ground instances of elements of A, called the positive examples, that are observed to be true.
• E^- is the 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. We assume that each hypothesis is a logic program.

The aim is to find a simplest hypothesis h∈H such that

B∧h E⁺ and
B∧h E^-.

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.

We, thus, want to find an element of the version space. 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.

For the rest of this section, assume that there is a single target n-ary relation whose definition we want to learn, and for which we use the predicate symbol t. That is, A={t(X₁,...,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 hypothesis and make it more complicated to fit the data. Because the logic program only states positive facts, the simplest hypothesis is the most general hypothesis, which is simply that t(X₁,...,X_n) is always true. This hypothesis implies the positive examples, but it also implies the negative examples, if any exist. This 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 simplest 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.

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

{t(X₁,...,X_n) ←}.

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

The following are three primitive specialization operators:

• Split a clause in G on condition c. Clause a←b in G is replaced by two clauses: a←b∧c and a←b∧¬c.
• Split a clause a←b in G on a variable X that appears in a or b. Clause a←b is replaced by the clauses
  a ←b ∧X=t₁.
  ...
  a ←b ∧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.

1: Procedure TDInductiveLogicProgram(t,B,E⁺,E^-,R)
2:           Inputs
3:                     t: an atom whose definition is to be learned
4:                     B: background knowledge is a logic program
5:                     E⁺: positive examples
6:                     E^-: negative examples
7:                     R: set of specialization operators
8:           Output
9:                     logic program that classifies E⁺ positively and E^- negatively or ⊥ if no program can be found
10:           Local
11:                     H is a set of clauses
12:           H←{t(X₁,...,X_n)←}
13:           while (there is e∈E^- such that B∪H e)
14:                     if (there is r∈R such that B∪r(H) E⁺) then
15:                               Select r∈R such that B∪r(H) E⁺
16:                               H ←r(H)
17:                     else
18:                               return ⊥
19:                     
20:           
21:           return H

Figure 14.1 shows a local search 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.

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.