A Rule-Based Task Generation System

A RULE - RASED TASK GFNERATION SYSTEM

D. H. Sleeman

University of Leeds, U.K. (Visiting Scientist, Dept of Computer Science, CMU, session 1980/1)

ABSTRACT

Considerable attention has been given to creating hypotheses which cover a set of instances. However, todate the related problem of generating a .t..a.il to refine the hypothesis set has so far received very little attention . A task -generator has been implemented for a rule-based modelling system, LMS, Leeds Modelling System . Here we discuss how an analogous task -generator could be used with systems which do n.lLt.. constrain their hypothesis-space as strongly as LMS.

Considerable attention has been given to creating hypotheses which cover a set of instances, [1], [2]. [3], [4], [6), [7), [8] and [10] . However, todate the related problem of general ing a .t.lli. to ··efine the hypotheses set has so far received very little attention . Mitchell (7] is amoung the few peop 1e to address this issue, and indicates how a problem generator would fit within the Version Space approach. Most workers have made the same basic assumption that we have made in our earlier Modelling work [10], namely that the set of examples provided ~ be sufficiently rich to discriminate between all likely hypotheses. Obviously this assumption becomes less viable as the number of potential hypotheses increases.

This task generator has been created as part of a system which models student's problem solving. LMS, Leeds Modelling System, presents the student with a task, is presented with the student's response and from this, hypothesizes models to explain the student's performance. (Indeed. LMS represents each student model as an ordered production set; ordered, in the sense that the first rule which is satisfied, fires. See figure 2 for TRACEs of typical models). In our work we have paid particular attention to the ii~ of the search space and have shown that by .~;.Q~!Ul.t.r..a.t..in~ on D..aLtiklllli rule ( s) it is poss i b 1 e to achieve very major reductions in the size of search space(s). In an earlier paper we discussed an algorithm for the systematic search of a hypothesis-space [12), and the need to create for each domain-rule a discriminatory problem-type, or Problem Template . Here we show how these techniques can also be applied to systems where .the search has ruu been so systematic. The task-generator described here is for the Algebra domain, but we beleive that the approach outlined has considerable generality.

lnclrwd, we clai·m that the Task (,enor.llor descrihecl here is suitabl() for domains in which the objective is to transform au initial state into either a pre-specified (goal) state or at le<tst one with specified chac·acter ist ics. (Generators for other task-types, for example the tasks described by Klahr, [5] and Siegler, [9) , will be discussed in a subsequent paper) . Further. it has been assumed that the domain knowledge has been formulated as a set of CONDITION -ACTION rules; that the tasks will be processed using the same matching-execution cycle as used here, namely the first satisfied rule fires .

~ l~~ Algebra QQmAin .

Figure Ia gives a styalized form of the rules used to evaluate/solve Algebra tasks, and figure 1b gives the set of associated mal-rules which have been noted in an earlier analysis of protocols , and used in a Modelling experiment, [11). Styali7ed rules have been used for Task Gene··at ion as they capture a 11 the .ll.llii.O...t..ial issues . but avoid some of the messier detail. (Clearly, it would be possible to implement an algorithm to generate the 'real' rules from the styalized ones) . Figure 2 gives 'TRACFs' of pairs of correct and 'buggy' models solving typical problems , and hence indicates the types of discriminatory tasks which the task -generation algorithm must create.

~ Rule-based laAk generatoc.

This analysis, further assumes that the model- and task-generation algorithms make use of the following classification for the CONDITION part of the rules:

a ) f.Q.llUl..t..i.iU I n t era c t il!.n la.iw.!U!..Q B..u.lu

Suppose the conditions of Rule 1 is Cl C2 . .. Cm Cn and the conditions of Rule 2 is Cm Cn Cs Cz, then both Rules would be able to fire, if the problem presented contained a pattern of the form:-

As we are dealing with ULdat~Q production sets. the order of the rules determines which fires (first) . And hence such a pattern would potentially discriminate between the models ( ... Rl ... R2 ... ) and ( . .. R2 ... Rl. .. ) . [Whether or not the example does discriminate depends on the actions of the 2 rules] .

An example of such a pair of rules is ADDSUB NUM +/ - NUM MULl NUN · NUN

fi!ll!ll 1

a) Rll!....E..S. ill .t..h.e. ALG..f.!!_RA li.o.!lliLi!l Lnll.lu.a1i.Y..e. ~t:.!.!l and s lightly styilli7 ed)

LEVEL PATTERN

'ACTION'

Where M, N and P are integers and where lhs , rhs etc are general patterns (which may be null·), where +/- means either + or - may occur and where SHD indicates the String Head. (Thus the state :

2·x + 5 + 6 = 9

caul d be matched by both the ADDSUB and NTORHS rules; which rule would f..ir..lt. depends on the .c..e.l..il..t....i.J or·der of the r ules within the model].

LEVEL PATTERN

'ACTION'

Using the same conventions as above .

1. shows (MULT AODSUB SOLVE FIN2) and (ADDSUB MULl SOLVE FIN2) solving

(The first line gives the initial state and all subsequent lines give the rule whi ch fires and the resulting state] .

1. shows (NTORHS ADDSUB SOLVE FIN2) and (MNTORHS ADDSUB SOLVE FIN2)

MULl ADDSUB SOLVE FIN2 NTORHS ADDSUB SOLVE FIN2 2X = 3 · 4 + 5 . 2X = 3 · 4 + 5 2X = 3 · 4 + 5 2X = 12 + 5 ADDSUB 2X = 3 · 9 2X = 17 MULl 2X = 27 X = 17/2 SOLVE X = 27/2 (17/2) FIN2 (27/2) solving 2X + 5 = 9 . 2X + 5 9 2X = 9 - 5 2X = 4 X = 2 ( 2) 2X + 2X = 2X = X = MNTORHS ADDSUB SOLVE FIN2 ( 7) 5 = 9 9 + 5 14 7

The discriminatory patterns, which we shall also refer to as Overlap Patterns, in this case being :

and NUM +/- NUM · NUM

NUM · NUM +/- NUM

b ) tlll.!l.:..in.Le.r..a..c.lillg_,._ nJ: Qr..d.e.r..:.l!l.I!~.L. Rul.u Non -in teracting rules are ones which l'!.b.llll.Y.ll..I: the pattern would not be in conflict, ie the patterns do NOT overlap . For example, if the conditions of Rl are C1 C2 C3 and of R2 are C1 C2 C4 then these would NOT compete.

c) Su.h.s.l!!!!.e.. Rule R 1 is said to subsuroe R2, if Rl 's condition set is an ordered sub-set(1) of R2's condition s (the effect of R1 being placed before R2 , in an ordered Pro~uction Set, is that the PS would act as if R2 did not occur (2)) . An example of a subsuming/subsumed p~ir from this domain is AOOSUB and HEARRANGE .

Nota that Subsumption and 'Non Int erac tion' ca n he decided by inspection of the CONDITION parts of the rules; potential internction/conflict depends critically on the form of the problem consider~d. and so has to be decided with respect to each problem type .

In order to generate a type of problem which woultl allow a rule to fit·e we need to use the rules in the QIUW.s.l.t.e. direction to which they are used to solve a problem . That is given the MULl rule :-

(SIR1 NUM STR2) => (STR1 NUM · NUM ST~2) the algorithm checks if NUM is contained 1n the input str ing , and if so replaces it by the string NUM · NUM, (STRi are strings which can be null). To initiate the generation algorithm we need to specify an initial string, a set of rules which can be used in .\lll.!utr..a.t.i2n [Tlll.dll. and a terminating condition (number of iterations, rules which the final pattern must activate etc.). Figure 3 shows the performance of the system when given the initial state, (Still NIJM) . RuiP. St!L (t·11JI I SOl VF FIN2) and thu critereon that MULT and then SOL VF must be activated.

3 . 1 I.M .algllr.ilhm !.2 Sll.MJ:ll1ll. il £r.2!Ll.e.!!1 !.2 .dillr...iminll1ll. 12tll'!.e..e.n .2. mllJ!ti..s.

The basis of this approach is the discrimination between 2 model s. However, if one has N models than it would be sensible to choose a feature , say the presP.n ce/absen ce of a partitular rule which, as neat·ly as puss ible. splits the hypothesis space into 2, and to use the algorithm outlined in thi s section with 2 models, one of which has the chosen feature and one that does not .

Note that if one is systematically exploring a rule-space, as do both versions of LMS , (10), (12), then tbe only variants encountered should be rule/mal-rules and the ordering of the rules . However, what follows is a more general analysis which is needed if the space is not being searched systematically. In general, there are 2 cases which need to be distinguished between namel y:

A. M!.l.l!.e..Ls. wltli.!! !!.axe. .t.!!.e. Hlmll. r.ul.u ll..u.1 _dj_fill.H1 lllli 2L.!I.e.J:.!Ut ·

Initially, we need to model, the sub - set of rules interact with other rules . models were: distinguish in ftakh which can potentially Suppose that the 2

(F!N2 SOl VF ADDSUB MUll) (MULl AOOSUR SOLVf FIN2)

f&n!U'i!tclll.!l QJ . .a P.J:J!.ll.l.e.!!! f.QL L"!ULI S.Ql.VE El~Z.l~ s..t..actiny fTQ!!l l!Hl. 12-'l..S.J!;. fM.ill (SUD NUM).

The Names On The Arcs show The Rules Used To Create The Next String . The starred configurations are returned by the system as ones which meet the critereon specified. (NB a slightly simplified version of FIN2 has been used) .

Then the 2 rules which ~2Ml~ interact are ADDSUB and MULT: these rules are ordered differently in these Models and so the algorithm would attempt to generate a problem which discriminates between the 2 orderings of the rules, MULT and ADOSUB. (If they are D..QJ. ordered differently then a discrimination is lli21 possible: eg (FIN2 SOLVE ADDSUB MULl) and (ADD SUB MULl F I N2 SOLVE) .are equivalent models).

The initial algorithm to create such a Template attempts to create a task which activates all the rules contained in the models and which contains the Overlap Pattern, OPij. In effect, the models being considered contain just one additional rule to the model considered in figure 3, and so we can anticipate the fQrm of the resultant tree. Such a search is essentially breadth first, and so as at each level several rules can be applied the number of active nodes increases rapidly . A much 'tidier' approach is to produce Problem-Templates fo1· the 'basic' models, that is for:

(ADDSUB SOLVE FIN2)

( MUI T SOl VF Fl N2)

and the11 IIH~1·ely to ll_X_lt!!'! thPse Problem T"mplates to 'accommodate' the addiLional rule, ie ~lUI Tor AOOSUB: in fiuure 4 we 1 ist the Pis ge11eratod for this domain's rules and associated mal - rules . (In an earliur papur , [P], we discuss the creation of such Pis. as well as the UHneration of Pls to discriminate between interacting pairs of rules eg ADDSUB and M2NTORHS).

The revised algorithm, to discriminate between 2 models, calculates the Overlap Pattern(s) and attempts to 'extend' the Problem Template for rule i, Pli, by using Rj in generative mode. The template is accepted if it contains OPij and if it satisfies Ri and Rj. Similarly, the algorithm attempts to extend Plj using Ri in generative mode; the analogous tests are applied. For this example, as we have noted, the Overlap Patterns are:

NUM +/- NUM · NUM

NUM · NUM +/- NUM

and the discriminatory tasks created by extending the PTs for the ADDSUB and the MULl rules are:

NUM · X NUM · NUM +/- NUM

NUM · X · NUM +/- NUM · NUM

[In general there may be M pairs of wrongly ordered rules. in w~ich case the discriminoting problem should satisfy the above condition for .!l_,_1!:.h pair. In practice. one might p1·efe1' to generate a problem to discriminate between a single pair, and to work with the 'refined' models subsequently].

This algorithm considers rules which are known nll.l to interact. There are 2 basic cases to be considered here, namely:

1. where the CONDITIONs of rules, Ri and Rj, are different, (3).
2. where the ACTIONs of the rule-pair are different.

The algorithm treats rules which differ in ~t~ their CONDITION and ACTION parts, as . if only their CONDITION parts differ (as it· is eas1er to verify discrimination has been achieved in this case). [Rules which have identical CONDITION and ACTION parts should NOT occur and are reported as data errors]. For the moment, we shall assume there is only one rule pair to be discriminated between in the two models (this approach may be generalized later).

The 2 sub-algorithms are:

Different ~i1i2n fa£1

If we use the notation that C(Ri) is the condition part of the ith rule and PTi its Problem Template, then:

If C(Rl) is not satisfied by PT2 then PT2 discriminates.

Similarly, if C(R2) is D..QJ. satisfied by PTl then PTl discriminates.

If both of the above tests fail, then check that the a~iQn~ of the 2 rules differ: if they are the same, report an error as discrimination will not be achieved with the current PTs. [Subsequently, we plan to implement an algorithm which will extend the PTs to ensure discrimination in such cases].

SD'ill i!.IJI! .Yli.Uj_<!!! l![ f.t:!!b]~Jm leJ!!Itl.ilt..v:; I.!l!:. 1...h.!l ll.!l!!l . .Un Rill~­ (NB the mal - rules use the PT of the 'parent' I'Ule.)

FIN2

SOLVE

ADDSUil

(I · X NUM II NUM)

(NUM · X · NlJM +/- NUM)

MULT

(NUM · X · NUM)

( NUM · X · NlJ~I · NUM)

XADOSUII

(NlJM · X +I- NUM · X ~ +1- NUM)

NTORIIS

(+/- NUM · X +I - NUM · +/- NUM)

XTOLHS

(NUM · X NUM - NUM · X)

RrARRANGE

(NUM +I- NUM · X NUM)

BRA I

(NUM · X NUM · < NUM >)

BRA2

(NUM · X · NUM · < NUM · X +I- NUM >)

Note the Pls returned by the algorithm do NOT contain SHD: however, this is present in the intermediary f.lLr..ms so that the expressions can be syrnbollically evaluated by FIN2 and SOLVE.

Thu s this problem reduces to that of ensuring that appropriate Templates have been provided as data or subsequently 'grown'.

Rules which have the same CONDITION-part but IU f.f J! r:.inu ACTION parts ar·e · .i'l.5..sJ!'I!'lrt to l.Je di sti ugtri sht!d by the differ·ing actions, (4). Thus for NlilllltS/WJTOIOIS it is assumed that problems as soc iated with NTORHS would give different results with MNTOIUIS. (And so the problem template for NTOR~S does not need extension to covHr thrs mal -rule; also see figure 2) .

If the models to be distinguished between, are such that they fall within .Qtl!! class A and R, then at pres ent the algorithm consider s case 0 before cas e A. Subsequently we may upgrade the a lgor ithm so that both types can be considered simultaneously; although we have some re se rvations about the use of such 'complex' examples.

To summarize if we have models: (ADDSUB SOLVE FIN2) (XADDSUB SOLVE FIN2)

this would be classified as an instance of the algori thm . Ba

(NTORIIS (MNTORIIS ADDSUR SOlVE FIN2) FIN2 SOLVE ADDSUR)

would l.J e classified algorithm. as an instance of the Bb

(NTORIIS ADDSUI3 SOLVE FIN2) ( SOl VF FIN2 ~1 2 NTORIIS AOOSUR)

would be c las si fied as an instance of Ba and A M2tJTOR ~ S and AOOSUR potentIally interact. as

Whereas

(MUI T NTORIIS AOOSUB SOLVE FIN2) (ADilSUTl MNTORIIS MUI T SOLVE FIN2)

is an example which falls into classes A and B (Tlb) , as MUIr and ADil SUTl potentially inter'act and because NIORIIS and MNTOHHS have different actions .

The other assumption which we have made so far is that no additional rules have to be in cluded in the rule - set in order to generate a di scr iminatory problem . It is possible to envisage si tuations, where this is not a valid a ss u"~tion, but we have been happy to make this ass umption in order to 'contain' what is potentially an enormous search space. However, it i s onl y necessa ry to add additional rules to the genera tion set if the initial sear ch fails. (In the limit a ll the domain r·ules should be contained in the 'gener·ative' rule - set) .

So far we have rrQ1 implemented a Template In s tant iator for this domain ; this is .. not a very demanding ta sk, but neither is it a very rewarding one as similar implementat ions have been done many timus bef ore . However, such an implementation is nHililtHI to take full advantage of any on - 1 ine nuHIHIIiny capabil i ty.

• 1 . C1 C2 subsumes C1 C2 C3 whereas C2 C1 does not .
• 2 . Note carefully this use of SUBSUME . We are using SUBSUME only to discuss rule-CONDITIONs .
• 3 . In order to make a comparison between different rules (mal-rules), it may be necessary to introduce a standardized notation for the variables . Eg the first parameter becoming $p1 etc .
• 4 . For the moment, we are ignoring numerical degeneracy which sometimes occurs; indeed, with a large set of models it is diffi cult to choose problems tu avoid it completely : For the pre sent , our only solution 1s to bring s uch degeneracy to the i nvestiga t or 's attention when the models evaluate .S.ll.~.i.fiJ; prolllems .

Jaime Carbonell, Pat Langley . N. S . Sridharan and K. R. James (Leeds) for helpful comments on earlier drafts .

To Leeds for granting Sabbatical leave which has enabled me to concentrate on this work; and to CMU for providing facilities and a very stimulating enviroment in which to continue it .

RF FERENCES

1. Buchanan. B.G. 1974. Scientific Theory f or·rna t ion by cornputer, in f.L.QJ;El~J !!.!J S. .a.f .1.1!1~. !i.l)lQ 8tiY.iiO.J;!Id S.l.ll.dy, lus.U..t.v.l.Jt l!1l l.:.l.!!.!llWllf. Qr..i.!.'!!.l..il.l~d illr.n.i.!ul ff..!1 . .1&.!i.s..\LS. .
2. Burton , R. R. 1981. Diagnosing bugs in a s irnpl e procedural ski 11 . In l.n.!JiJ.li !Uill..l. lu1Q£in~ SY..s..l.~.s.. ed . D. Sleeman and J . S . Brown , New York ~ Academic Press .
3. 3 . Cohen, B. L. & Sammut, C.A . 1978 . CONFUCIUS: A Structural Concept learning Sy stern. A.u..s..l.r..al.i.an C..Omu.u.l..e..r. J..Q.w:.n.aL l.lL Pfl 138- 143.
4. 4 . Hayes - Roth, F. & McDermott, J . 197B . An inferen ce matching techniques for Induct ive Abstr·actions, l:Al:M..... .2.1. pp401 - 410 .
5. 5 . Klahr, D. and development Strateg ies , f.s.yc hology, pp Wallace, J . G. 1970. The of serial completion l!.!:ili.s...IJ. .Jll..!I..C.!l..a .a.f 243 - 257.
6. Mi chal sk i, R. (1979) . Pattern Recognition as Rule -Guided Induc tive T nfer·ence, HJE lCll!lJHI~.l..i!l.nS. li.Jl fa.t.t.ll.f.ll AllillY. .S..is. i.l!JJ! t1aJ;..!.U.llll l11 ~.!I.J.lill.ll.DJ;lL pp 77

• 7 . Mitchell, T.M . an approach to Thesis, Dept Stanford. 1978 . Version Spaces: Concept Lear·n i ng . Ph. 0. of Computer Science,
• Quinlan, J .R. 1979 . Discovering Rules by Induction from la r ge collections of Examples . In (ed) O.Michie, .EAJLe.tl ~tljt~ in .tM Mllr.lL . .e.J..!l.tlJ:.ll.D.i.l;. .au . Edinburgh: EUP, pp 168 - 201 .
• 9 . Siegler, R.S . 1978 . The Scientific Reasoning, in IhinKin~~ what develops, Siegler . Hillsdale, NJ: LEA . Origins of C.hil.d..c..e.n..:.. ed R.S.
• Sleeman , O.H. and Smith, M. J . 1981. Modelling Student's ~.al. pp 171-187. Problem Solving, AI
• Sleeman, O.H. 1981 . Assessing aspects of competence in Basic Algebra . In lnWli~.IUl.t J .. uJ&Li~ S~tl.em.s., e d. O.Sleeman and J.S. Brown, · New York: Academic Press.
• Sleeman, D.H. (to appear) . A Rule -based Modelling system .