Learning Simple Arithmetic

LEARNING SIMPLE ARITHMETIC .

Pavel Brazdil Department of Artificial Intelligence University of Edinburgh Scotland

Sussman (1973) has shown that strategies could be reordered according to experience. In his ex­ amples no conflicts were experienced after reorder­ ing. we shall illustrate that conflicts do arise and present a way of trying to overcome them. The program written (ELS) accepts a set of partially ordered Horn clauses as input and a sequence of problems to solve. The search tree obtained is examined in order to generate a priority ordering for the clauses used. If conflicts are detected, ELS tries to determine the conditions under which the clauses involved should be applied. For ex­ ample, suppose the problem 3+2=X is to be solved and we are given the clauses:

assoc: Xl+(X2+X3)=X4 + (Xl+X2)+X3=X4.

subs : Xl+X2=X3 + Xl=XO, XO+X2=X3.

subz : Xl+X2=X3 + X2=XO, Xl+XO=X3.

sue:

0+1=1 +. 1+1=2 +. · ·. etc,

pred:

l=l+O + . 2=1+1 + . . ·· etc.

Generally, the problems are solved in a breadth first manner, but priority orderings between indi­ vidual clauses are r e spected. First all clauses that match the given subgoal are chosen. In our case both the clauses 'subs' and 'subz' match the initial goal 3+2=X, as this goal matches Xl+X2=X3. Both clauses are actually tried in the search, since initially there is no priority ordering specified between them. If it had been specified that 'subz<subs', only the clause 'subz' would have been tried.

Figure 1 shows a part of the search tree pro­ duced by ELS when solving the goal 3+2=X. The search tree contains a number of choice points. Every time a choice is made ELS makes a note of which clause was given preference. After a suc­ cessful solution has been reached (marked 'yes'), the preferences noted on the solution path are integrated with the existing priority orderings and then used to guide future searches.

The integration is not just a matter of adding the new orderings to the old ones as conflicting requirements can occur. In our example we have one such conflict. First we require 'subz<subs' and then 'subs<subz'. To resolve the conflict, ELS looks back into the search tree. It assumes that one of the variable assignments in the clause 'subs' (or 'subz') is critical. In order to make a good guess which is the critical assignment, it compares the application which lies on the solu­ tion path (marked 'allow') with an application which lies just off the solution path (marked 'avoid'). A new clause is generated on the basis of this comparison. Care is taken so that it would mismatch the application marked 'avoid', but further unnecessary specializations are avoided. In our case ELS generates the clause 'subs.l'. Thus:

allow subs:

avoid subs:

new subs.l:

(3+l)+l=X + ·.·

3+2=X + ···

(Yl+Y2)+X2=X3 + ··.

The new clause 'subs.l' is added to the original set of clauses together with the priority ordering 'subs.l<subS' and 'subs.l<subz', which replaces the priority ordering 'subs<subz'. The problem 3+2=X can now be solved without search. The knowledge thus acquired helps the system to solve a number of similar problems, such as l+4=X and (2+1)+5=X, which are both solved without search. The work described here is currently being ex.tended to the domain of simple equation solving.

Our work is also related to Waterman (1975). The key point in our approach is analysis of the past search for the purpose of conflict resolution. Initially only priority orderings are used to de­ scribe a solution path, but if a conflict is de­ tected, the old search tree is revisited in order to pull out more information about the clauses in­ volved in the conflict .