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.
Exercise 9.1 #
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.