# Inductive reasoning

# 9. Inductive reasoning#

*Induction* is a form of reasoning which infers general rules from specific observations. For instance, given the following \(Theory\)

```
bird(tweety). bird(polly).
has_feathers(tweety). has_beak(polly).
```

we might want to infer a \(Hypothesis\) explaining why both Tweety and Polly fly:

```
flies(X):-bird(X).
```

There is a strong similarity between induction and abduction: if the \(Examples\), which induction seeks to explain, are the ground facts `flies(tweety)`

and `flies(polly)`

then the following relation holds:

The main difference with abduction is that \(Hypothesis\) is allowed to be a set of clauses, rather than a set of ground facts as in abduction.

Given this similarity, we will try to adopt the abductive meta-interpreter developed in Section 8.3 to perform induction. We assume that the set of possible hypotheses is given by means of the predicate `inducible/1`

.

```
% induce(E,H) <- H is inductive explanation of E
induce(E,H):-induce(E,[],H).
induce(true,H,H):-!.
induce((A,B),H0,H):-!,
induce(A,H0,H1),
induce(B,H1,H).
induce(A,H0,H):-
/* not A=true, not A=(_,_) */
clause(A,B),
induce(B,H0,H).
induce(A,H0,H):-
element((A:-B),H0), % already assumed
induce(B,H0,H). % proceed with body of rule
induce(A,H0,[(A:-B)|H]):- % A:-B can be added to H
inducible((A:-B)), % if it's inducible, and
not element((A:-B),H0), % if it's not already there
induce(B,H0,H). % proceed with body of rule
```

Whenever a clause is added to the inductive hypothesis, we proceed by constructing an inductive explanation of its body.

Suppose `inducible/1`

is defined as follows:

```
inducible((flies(X):-bird(X),has_feathers(X),has_beak(X))).
inducible((flies(X):-has_feathers(X),has_beak(X))).
inducible((flies(X):-bird(X),has_beak(X))).
inducible((flies(X):-bird(X),has_feathers(X))).
inducible((flies(X):-bird(X))).
inducible((flies(X):-has_feathers(X))).
inducible((flies(X):-has_beak(X))).
inducible((flies(X):-true)).
```

These facts state that every clause with `flies/1`

in its head and some of the predicates in \(Theory\) in its body is a possible inductive hypothesis. We can use `induce/2`

to find out which of these clauses account for the fact that Tweety and Polly fly:

```
?-induce(flies(tweety),H).
H = [(flies(tweety):-bird(tweety),has_feathers(tweety))];
H = [(flies(tweety):-bird(tweety))];
H = [(flies(tweety):-has_feathers(tweety))];
H = [(flies(tweety):-true)];
No more solutions
?-induce(flies(polly),H).
H = [(flies(polly):-bird(polly),has_beak(polly))];
H = [(flies(polly):-bird(polly))];
H = [(flies(polly):-has_beak(polly))];
H = [(flies(polly):-true)];
No more solutions
```

We can combine the answers to these queries in order to find a single clause which explains **both** `flies(tweety)`

and `flies(polly)`

. One way to do this is by *generalisation*, as will be explained later. Another way is to process all the examples at once.

Change `induce/3`

so that it handles a list of examples rather than a single example. Moreover, the inductive hypothesis should contain uninstantiated clauses, so that the same clause can be used to explain several examples.

However, a serious problem with this approach is the impracticality of listing every possible hypothesis by means of the predicate `inducible/1`

. In general, the inductive hypothesis can consist of several clauses, and might be recursive. The *hypothesis space* of possible sets of clauses is typically very large, and even infinite when functors are involved. This space needs to be searched in a systematic manner. Another complication is the possibility of *overgeneralisations* like the clause `flies(X):-true`

. In order to prevent overgeneralisation, *negative examples* need to be included in the induction process (here: non-flying objects). For these reasons, induction requires a more sophisticated search strategy than abduction. We will take a closer look at the structure of the search space in the next section. Then, we will develop two programs that can induce definitions for predicates like `append/3`

from examples.