Adaptive Production Systems

ABSTRACT

Adaptive production systems are defined and used to illustrate adaptive techniques in produc­ tion system construction. A learning paradigm is described within the framework of adaptive produc­ tion systems, and is applied to a simple rote learning task, a nonsense syllable association and discrimination task, and a serial pattern acquisi­ tion task. It is shown that with the appropriate production building mechanism, all three tasks can be solved using similar adaptive production system learning techniques.

D. A. Waterman

Department of Psychology Carnegie-Mellon University

define the successor function are created and then used to calculate the desired sum. The verbal association task is a PS implementation of EPAM (Feigenbaum, 1963). Instead of &rowing an EPAM discrimination net, the system creates a set of PR's equivalent to such a net. The series completion task consists of predicting the next symbols in a sequence, such as AABBAABB ·· llere PR's are created which represent hypotheses about which symbol con­ texts lead to which new symbols, i.e., "two A's al­ ways lead to a B." These rules constitute the con­ cept of the series and are used to predict new symbols.

I . INTRODUCTION

This paper presents results in the design and use of adaptive production systems (PS's). A PS (Newell & Simon, 1972; Newell, 1973) is a collec­ tion of production rules (PR's), that is, condition­ action pairs, C => A, where the left side is a set of conditions relevant to a data base or working memory (WM) and the right side is a list of actions which can modify WM. The PS's to be discussed are written in PAS-II (Waterman & Newell, 1973; Water­ man, 1973) and each is a set of ordered PR's. The control cycle consists of selecting one PR from the set and executing its actions. The first rule (in the ordered set) whose conditions match ~t is the one selected. After the actions of the selected rule are executed the cycle repeats. This process continues until no conditions match.

An adaptive PS is one which can modify its own PR's. There are three ways this can take place: by adding new rules, deleting old rules, and chang­ ing existin& rules; however, the PS's described here use only addition of new rules.

We now postulate a common machinery for learn­ ina: (1) a PS interpreter for ordered PS's, (2) a PS representation for learning pro&rams, (3) PR actions for building rules and adding them to the system, and (4) the learning technique of adding new PR's above error-causing rules to correct the errors. Three learning tasks are investigated: arithmetic, verbal association, and series comple­ tion.

The proarams for the tasks are written as short PS's which access a single WM composed of an ordered set of memory elements (ME's). When PR's "fire," i.e., their actions are executed, they modify WM by adding, deleting, or rearranging ME's. Such changes may cause different rules to fire on the next cycle and new memory modifications to be made. Thus the system uses WM as a buffer for holding initial data and intermediate results. Most actions modify ~1. Some modify the PS by assembling WM elements into a PR and addin& it to the PS. These actions give the PS its self-modification capability.

The arithmetic task consists of learnin& to add two intesers &iven only an ordering over the set of intesers. From this ordering, PR's which

II. PAS-II PRODUCTION SYSTEM

The PAS-II PS interpreter is modeled after PSG (Newell, 1972, 1973) . PR's in PAS consist of condi­ tion-action pairs, where the condition side is a set of conditions with implicit MEMBER and AND functions and the action side is an ordered list of independ­ ent actions. A rule to deposit (C) and (D) into WM if it already contains (A) and (B) is: (A) (B) => (DEP (C)) (DEP (D)), where the action DEP deposits its argument into WM. The control cycle of the PS interpreter consists of two mechanisms: RECOGNIZE and ACT. A cycle is defined to be a single RECOGNIZE-ACT sequence, and is repeated un­ til either no rules match WM or a PS halting action is executed.

RECOGNIZE. RECOGNIZE selects a rule to be executed. When many rules match WM a conflict oc­ curs, as RECOGNIZE must produce one rule for ACT to work on. Conflict resolution consists of applying a scheme to select one rule from those that match WM. The only conflict resolution used here is priority ordering. Thus the rule reco&nized is the highest priority rule whose conditions match WM.

The match mechanism assumes implicit MEMBER and AND notation and scans condition elements (CE's) in order from left to right to see if each element is in WM. When all the CE's in a rule match corresponding ME's, the ME's are brought to the front of memory (just before actions are exe­ cuted) in the order specified in the rule. A ME can match only one CE in any rule and the order of the ME's does not have to correspond to the order of the CE's. For example, the conditions (A) (B) (A) will match WM: (B) (A) (A), but not WM : (A) (B). ACE will match a ME if the ME contains all items the CE contains, in the same order, starting from the beginning of the ME. Thus CE (A T) wi ll match ME's (AT), and (AT E) but not (A), (T A), or (TAT). The match routine searches for the absence of a ME if the CE is preceeded by a minus sign (-). Thus (A) - (B) will match WM if it contains (A) but does not contain (1). Free variables can be used in the CE's and are denoted xl, x2, ·. · xn . When a match occurs each item in the ME which corresponds to a variable is bound to that variable. For example, with WM: (A) (B(L)) and PR: {xl) (B x2) => (DEP x2), xl is bound to A, and x2 to (L). The action taken will be to deposit (L) into WM.

ACT. ACT takes the rule specified by RECOGNIZE and executes all its actions, one at a time, in or­ der from left to right. Actions in a PS are criti­ cal since they determine the grain of the system. If the grain is too coarse a single action may em­ body all interesting activity, obscuring it from view. The criterion in defining actions is to make them primitive enough so the PS trace will exhibit the activity deemed interesting.

BASIC ACTIONS

(DEP !) : Deposit ~into front of ~M.

(RE~I a): Remove first occurrence of a from Jlt.l .

(REP a b n) : Replace a with bin nth-ME . --Default n is-1. - -

(SAY!) : Print~· Handles multiple arguments.

(CLEAR a) : All ME's except a are removed from ~'M.

(ATTEND): Read from terminal, to let user modify WI-I.

(STOP): Stop production system execution.

MODIFICATION ACTIONS

(COND a) : Deposits (COND a) into WM . Is the same as (DEP (COND a)).

(ACTION a): Deposits (ACTION a) into WM. Is the same as (DEP (ACTION a)).

(MARK a) : Marks each ME that just matched - the CE's of the rule containing (MARK a). Element e is marked by changing it to(!!) .

(USED) : Exactly equivalent to (MARK USED). (OLD): Exactly equivalent to (MARK OLD) .

(PROD a): Creates aPR from all ME's marked - (CONO .·. ) and (ACTION .. . ) and inserts it into the PS just in front of the first PR that contains an element identical to any arguments of PROD . If PROD has no arguments the rule is inserted at the front of the PS. If it has argument END, it is inserted at the end. In all cases all ME's marked (CONO ... ) and (ACTION ... ) are removed from Jlt.l .

SPECIAL ACTIONS

(SUCC) : Changes every ME beginning with a number by replacing that number with its successor.

(PERCEIVE a b): Breaks syllable a into letters and-tags the letters with b and a number specifying their order in a.

(OBSERVE a b) : Breaks word a into letters and tags the letters with b.

(PRODS abc d) : Here b is the hypothesized -period (initially 1), and cis the series. As in PROD, ME's marked (COND . .. ) and (ACTION . .. ) are combined and removed from WM to create a new rule. This rule is generalized accord­ ing to the template heuristic (see text) and placed just above the first rule containing a . The d is the number of rules already-added toPS by PRODS .

:.oh l c 1".\S I' 1 odtL·: ; ,,,

The three types of PAS actions are: basic, modification, and special, as shown in Tab~ They assume WM is an ordered list of ME's going from left to right. Thus DEP places ME's into WM at the left, and REP counts ME's starting from the left. The modification actions will now be illustrated.

WM: (B)(A)(C)(ACTION (SAY DONE)(STOP))(COND (C))

PS: 1. - (B) => (DEP (B))

2. (A) (B) => (MARK COND) (PROD (A))

3. (C) => (DEP (A))

When PS is fired, rule 2 is the first to match WM. The (MARK COND) marks (A) and (B) and memory becomes:

WM: (COND (A))(COND (B))(C)(ACTION (SAY DONE)(STOP)) (COND (C))

Then (PROD (A)) creates a PR out of the elements marked COND and ACTION, removes them from WM, and puts the new PR just above the first rule contain­ ing (A), rule 2.

WM: (C)

PS:

1. - (B) z> (DEP (B))

1.5. (A) (B) (C) => (SAY DONE) (STOP)

2. (A) (B) => (MARK COND) (PROD (A))

3. (C) => (DEP (A))

After the insertion of rule 1.5, execution con­ tinues, terminating with the firing of 1.5 .

Implicit actions are implemented in PAS, i.e., predecessors and successors on letters can be ac­ cessed implicitly by placing apostrophes before or after PR variables. Thus the value of xl' is the successor of the value of xl, and the value of ''xl is the double predecessor of the value of xl.

III. PRODUCTION SYSTEM FOR ADDITION

The addition PS is designed to illustrate adaptive techniques and to compare PS programming with conventional methods. It does not attempt to model data on human performance in this task. Figure 1 shows the ADD PS.

1. (READY) (ORDER XI) ·> (REP (READY) (COUNT XI)) (ATTEND)
2. (NXI)·(NN)··(SNN) ·> (DEP(NNXI))
3. (COUNT X I) (M X I) (NN X2) (N X3) ·> (SAY X2 IS THE ANSWER) (COND (M X I) (N X3)) (ACTION (STOP)) (ACTION (SAY X2 IS THE ANSWER)) (PROD) (STOP)
4. (COUNT) (NN) ·> (REP (COUNT) (S COUNT)) (REP (NN) (S NN) 2)
5. (ORDER Xl X2) ·> (REP (Xl X2) (X2)) (COND (S X3 XI)) (ACTION (REP (S X3 Xl) (X3 X2))) (PROD)

Figure 1. ADD: A Production System for Addition of Integers

When ATTEND is executed the system is given two integers, (M a) (N b). It calculates a+ b and prints the answer. The algorithm used is shown below.

1. add(m,n) = count+ 0; nn + n;
2. Ll if count= m then return(nn);
3. count+ succe~(count);

(2)

1. nn + successor(nn);
2. go(Ll).

Count and nn are local variables initialized to zero and n respectively. Count and nn are con­ tinuously incremented by one, using the successor function, until count equals m. At this point the answer is nn.

ADD performs these steps with some difference~. First, it has no successor function, so it creates a PR representation of that function. Second, once a sum is calculated it adds a rule that produces the answer directly the next time. Thus it builds the addition table for integers.

There is a direct mapping, however, between the code in (2) and that in Figure 1. Rules 1 and 2 in Figure 1 correspond to line 2.1. Rule 3 cor­ responds to 2.2, and rule 4 to 2.3 and 2.4. Rule 5 has no correspondent in (2) since the code assumes the existence of the successor function, while the PS creates it. Note that 2.5, the GOTO statement, has no correspondent in Figure 1. In ADD the func­ tion of the GOTO and label is handled by control cycle repetition, which permits looping, and memory modification, which in this case makes rules 1 and 2 inoperative. A trace of ADD solving 4 + 2 is shown in Figure 2.

IV. PRODUCTION SYSTEM IMPLEMENTATIONS OF EPAM

EPAM (Feigenbaum, 1963; Feigenbaum & Simon, 1964) is a program which simulates verbal learning behavior by memorizing three-letter nonsense ~ylla­ bles presented in associate pairs. The program learns to predict the correct response when gjven a stimulus syllable by growing a discrimination net composed of nodes which are tests on the values of certain attributes of the letters in the syl­ lable. Responses are stored at the terminal nodes, and are retrieved by sorting the stimuli down the net. A paired associate training sequence for this learning task is shown in Figure 3.

EPAMl. Figure 4 shows EPAMl. This program grows-a-P:S which is analogous to a discrimination net with tests for stimulus letters (i.e., "is the 3rd letter R?") at the intermediate nodes and com­ plete responses at terminal nodes.

·memory di1p"'y PI dilp"'y

MEMORY MODE

I . STM · (READY> (ORDER 0 I 2 3 4 55 7 8 II)

PS MODE

1. <READY) (ORDER X I> · > <REP <READY> <COUNT XI)) <ATTEND>
2. <N X I) - <NN> - (S NN> ·> (DEP <NN )(I))
3. <COUNT )(I) (M )(I) (NN X2) (N X3) ·> (SAY X2 IS THE ANSWER> <COND <M XI) (N X3)) (ACTION <STOP)) (ACTION <SAY X2 IS THE ANSWER)) (PROD> <STOP)
4. <COUNT> <NN> ·> <REP <COUNT) <S COUNT» <REP <NN> <S NN) 2)
5. <ORDER )(I X2) ·> <REP ()(I X2) (X2)) (COND <S X3 X I)) (ACTION (REP (S X3 X I) (X3 X2))) (PROD)

·fire

I TRUE IN PS

OUTPUT FOR (ATTEND) · (dtp (m 4)(n 2)) STM, (N 2) (M 4) (COUNT 0) (ORDER 0 I 2 3 4 5 5 7 8 II)

2 TRUE IN PS STM' <NN 2) (N 2) (M 4) (COUNT 0)

(ORDER 0 I 2 3 4 5 6 7 8 II)

4 TRUE IN PS

STMo (S COUNT 0) (S NN 2) (N 2) (M 4) <ORDER 0 I 2 3 4 5 6 7 8 9)

5 TRUE IN PS NOW INSERTING .<S X3 0) ·> (REP <S X3 0) (X3 I)) ON LINE 0.5 STM, <ORDER I 2 3 4 5 8 7 I 9) <S COUNT O)<S NN 2) (N 2) <M 41

0.5 TRUE IN PS STM (COUNT I) <ORDER I 2 3 4 5 5 7 I II) <S NN 2) (N 2) (M 4)

5 TRUE IN PS NOW INSERTING

(S X3 I) · > <REP <S )(3 I) ()(3 2)) ON LINE 0.25 STM' (ORDER 2 3 4 56 7 8 9) <COUNT I) <S NN 2) <N 2) (M 4)

5 TRUE IN PS NOW INSERTING <S X3 2) ·> <REP <S )(3 2) ()(3 3)) ON LINE 0.13 STM (ORDER 3 4 5 6 7 8 9) (COUNT I) <S NN 21 (N 2) (M 4)

0.13 TRUE IN PS STM' <NN 3) (ORDER 3 4 5 8 7 8 9) (COUNT I) (N 2) (M 4)

4 TRUE IN PS STM, (S COUNT I) (S NN 3) (ORDER 3 4 5 8 7 8 9) (N 2) (M 4)

0.25 TRUE IN PS STM (COUNT 2) (S NN 3) (ORDER 3 4 5 6 7 8 9) (N 2) (M 4)

5 TRUE IN PS NOW INSERTING (S X3 3) · > (REP (S X3 3) (X3 4)) ON liNE 0.05 STM' <ORDER 4 5 6 7 8 9) <COUNT 2) (S NN 3) (N 2) (M 4)

0.05 TRUE IN PS STM' <NN 4) (ORDER 4 5 6 7 8 9) <COUNT 2) (N 2) (M 4)

4 TRUE IN PS STM' <S COUNT 2) (S NN 4) <ORDER 4 5 6 7 8 9) <N 2) <M 4)

0.13 TRUE IN PS STMo (COUNT 3) (S NN 4) <ORDER 4 5 6 7 8 9) <N 2) (M 4)

5 TRUE IN PS NOW INSERTING <S X3 4) ·> <REP (S X3 4) ()(3 5))

ON LINE 0.03 STM' (ORDER 5 8 7 8 9) <COUNT 3) <S NN 4) IN 2) <M 4)

0.03 TRUE IN PS STM, <NN 5) (ORDER 5 8 7 I 9) (COUNT 3) <N 2) (M 4)

4 TRUE IN PS STM' (S COUNT 3) (S NN 5) (ORDER 5 6 7 8 9) (N 2) (M 4)

0.05 TRUE IN PS STM, <COUNT 4) (S NN 5) (ORDER 5 8 7 8 II) (N 2) (M 4)

5 TRUE IN PS NOW INSERTING (S X3 5) ·> <REP (S X3 5) ()(3 8)) ON LINE 0.02 STM, (ORDER 6 7 8 9) (COUNT 4) (S NN 5> <N 2) (M 4)

0.02 TRUE IN PS STM, <NN 6) (ORDER 8 7 8 9) <COUNT 4) (N 2) <M 4)

3 TRUE IN PS

6 IS THE ANSWER

NOW INSERTING <M 4) (N 2) ·> (SAY 8 IS THE ANSWER) <STOP) ON LINE 0.01 STM' (COUNT 4) (M 4) (NN 6) (N 2) (ORDER 8 7 8 9)

·diep"'y

0.01. (M 4) (N 2) .,. (SAY 6 IS THE ANSWER)

(STOP) 0.02. (S X3 5) ·> <REP (S X3 5) (X3 6)) 0.03. <S X3 4) ·> <REP (S X3 4) (X3 5)) 0.05. (S X3 3) ·> <REP <S X3 3) (X3 4)) 0.13. <S X3 2) ·> (REP (S X3 2) ()(3 3)) 0.25. <S X3 I) ·> <REP <S X3 I) ()(3 2)) 0.5. (S X3 0) ·> <II!EP (S X3 0) ()(3 I))

Figure 2. Trace of ADD Production System on 4 + 2.

I. (READY) (STIM XI) ·> (REM (READY)) (PERCEIVE XI ?) 2. (READY) ·> (ATTEND STIM) . 3. (REPLY)· (RESP) ·> (ATTEND RESP) 4. (REPLY X I ) · (RESP X I ) ·> (REP REPLY WRONG) 5. (USED X I) (WRONG X2) ·> (REP USED COND) 6. · (RESP) ·> (DEP (REPLY ?)) (SAY f) (ATTEND RESP) 7. (X I X2 ?) (RESP X3) (WRONG X4) ·> (COND (XI X2 f)) (ACTION (USED) (DEP lREPLY X3)) (SAY X3)) (PROD (SAY X4)) (STOP) Figure 4. EPAMI: A Production System Implementation of EPAM EPAMl learning PAX-CON and PUM-JES is illus­ trated below. *fire 2 TRUE IN PS OUTPUT FOR (ATTEND STIM) · (dep (stim pax)) STM: (STIM PAX) (READY) I TRUE IN PS STM: (1 P ?) (3 X ?) (2 A ?) (STIM PAX) 6 TRUE IN PS ? OUTPUT FOR (ATTEND RESP) · (dep (reap con)) STM: (RESP CON) (REPLY ?) (I P ?) (3 X ?) (2 A ?) (STIM PAX) Initially WM (here called STM) contains (READY). Rule 2 fires and the system asks for the stimulus. Then 1 fires, adding stimulus components to memory. Next 6 fires and prints a question mark as the sys­ tem's reply to the stimulus, adds this reply to memory, and asks for the correct response. 4 TRUE IN PS STM1 (WRONG ?) (RESP CON) (I P ?) (3 X ?) (2 A ?) (STIM PAX) 7 TRUE IN PS NOW INSERTING (1 P ?) ·> (USED) (DEP (REPLY CON)) (SAY CON) ON LINE 5.5 STM: (I P ?) (RESP CON) (WRONG f) (3 X ?) (2 A f) (STIM PAX) . Since the reply (?) does not match the response (CON), 4 fires and changes the label REPLY to WRONG. Now 7 fires creating rule 5.5. ·initialize fire INITIALIZED 2 TRUE IN PS OUTPUT FOR (ATTEND STIM) · (dep (stim pum)) STM: (STIM PUM) (READY) I TRUE IN PS STM: (I P ?) (3 M f) (2 U ?) (STIM PUM) 5.5 TRUE IN PS CON STM: (REPLY CON) (USED (I P 7)) (3 M f) (2 U T) (STIM PUM)

Before the second pair of syllables is pre­ sented, memory is initialized back to (READY), and the system is restarted. Again 2 and 1 are fired to obtain and perceive the stimulus. But now 5.5 matches WM and causes (1 P ?) to be marked USED, and the system to reply CON and add the reply to memory. This is an example of stimulus general­ ization: the system confused PUM with PAX since it was only noticing first letters.

3 TRUE IN PS OUTPUT FOR (ATTEND RESP) · (dep (resp je1)) STM: (RESP JES) (REPLY CON) (USED (I P ?)) (3 M 7) (2 U ?) (STIM PUM) 4 TRUE IN PS STM: (WRONG CON) (RESP JES) (USED (I P f)) (3 M f) (2 U ?) (STIM PUM) 5 TRUE IN PS (2 U f) (STIM PUM) 7 TRUE IN PS NOW INSERTING (3 M ?) (I P ?) ·> (USED) (DEP (REPLY JES)) (SAY JES) ON LINE 5.3 STM: (3 M ?) (RESP JES) (WRONG CON) (2 U ?) (STlM PUM)

STM: (COND (I P f)) (WRONG CON) (RESP JES) (3 M ?) Now memory contains a reply but no response, so 3 fires and elicits the correct response (JES) from the user. Rule 4 fires, since the reply differs from the response, marking the reply wrong. Next 5 fires, changing the USED label to COND. Finally 7 fires and creates a new rule with two condition elements, one from the COND already-fn memory and one from the COND inserted by rule 7. The two rules just added are: 5.3. (3 M ?) (I P 1) ·> (USED) (DEP (REPLY JES)) (SAY JES) 5.5. (I P ?) ·> (USED) (DEP (REPLY CON)) (SAY CON) PAX will now elicit the response CON, and PUM the response JES, as desired. EPAM2. Figure 5 shows EPAM2. This complete version-ol EPAM grows a PS in which response ~ rather than complete responses are stored in some terminal nodes. These cues (i.e., C N) are re­ trieved by dropping the stimulus through the net, and are then themselves dropped through the net to retrieve the responses stored in other term­ inal nodes.

I. (READY) (STIM X I) ·> (REM (READY)) (PERCEIVE X I ?) 2. (READY) ·> (ATTEND STIM) 3. (REPLY) · (RESP) ·> (ATTEND RESP) 4. (REPLY X I) · (RESP X I) ·> (REP REPLY WRONG) 5. (REPLY X I) (RESP X I) ·> (STOP) 6. (USED) (TEST X I) · (TEST X2) ·> (REP USED USED*) 7. (TEST X I) (TEST X2) (X3 X4 ?) ·> (REM (X3 X4 7)) 8. (TEST XI) (TEST X2) · (R·GEN) ·> (DEP (REPLY XI) (R·GEN)) (SAY XI) 9. · (RESP) c) (DEP (REPLY ?)) (SAY Y) (ATTEND RESP) I 0. (RESP X I) · (X2 X3 RESP) ·> (PERCEIVE XI RESP) II. (WRONG) (TEST X I) (STIM X I) · (R·GEN) ·> (DEP (R·GEN)) 12. (OLD X I) (R·GEN) ·> (REP OLD COND) (DEP (HOLD X I))

13. (USED X I) (USED*) (R-GEN) ·> (REP USED COND) (DEP (HOLD X I )) 14. (R-GEN) (COND (X I X2 't)) (X I X2 RESP) ·> (REM (X I X2 RESP)) 15. (X I X2 RESP) (RESP X3) (WRONG X4) - (DONE) ·> (COND (X I X2 ?)) (ACTION (OLD) (OEP (REPLY X3)) (SAY X3)) (PROD (SAY X4) (TEST X4)) (DEP (DONE)) 16. (USED* X I) ·> (REP USED* COND) 17. (OLD) (DONE) - (TEST) ·> (REP OLD COND) 18. (R-GEN) (HOLD (XI X2?)) ·> (REM (HOLD (XI X2 ?))) (ACTION (DEP (X I X2 ?))) 19. (R-GEN) (XI X2 RESP) (STIM X3) (WRONG X4) ·> (ACTION (OEP (TEST X3))) (ACTION (USED) (DEP (X I X2 ?))) (PROD (DEP (TEST X3))) (STOP) 20. (XI X2 ?) (X3 X4 RESP) (STIM X5) (WRONG X6) ·> (COND (XI X2 ?)) (ACTION (USED) (DEP (X3 X4 T)) (DEP (TEST XS))) (PROD (SAY X6)) (STOP)

Figure S. EPAM2: A Production System Implementation of EPAM

EPAM2 was given the stimulus-response pairs of Figure 3 and produced the output shown in Figure 6. There were two instances of stimulus generalization, two of response generalization, one of both stimulus and response generalization, and two of stimulus-response confusion.

Figure 6. EPAM2 Output for Three Training Trials (SG: stimulus generalization error, RG: response generalization error, SR: stimulus-response confusion).

The PR's learned by EPAM2 and the correspond­ ing discrimination net are shown in shorthand notation* in Figure 7. Note that the condition elements are analogous to intermediate nodes and the response elements to the terminal nodes in the net, and the path through the net from the top to a terminal node corresponds to the sequence of conditions tested in the PS to obtain a response.

*Conditions, like (1 P), are elements denoting a letter and its location in the syllable, and are ordered (first, third, second) according to syl­ lable location. Actions are response words like CON, or partial response cues like (1M).

V. PRODUCTION SYSTEM FOR SERIES COMPLETION

Computer models of series completion (Simon & Kotovsky, 1963; Klahr & Wallace, 1970; Williams, 1972) have been complex programs with structures quite dissimilar from those of more basic learning models. Here we provide a common structure for these learning tasks. The essence of their common­ ality is (1) an ordered PS representation of what is learned, and (2), the technique of adding new PR's above the error-causing rules to correct errors. A PS will now be described which can solve complex letter series completion tasks which require the use of~· successor, or predecessor operations on the alphabet.

Learning Technique

PR's are created which represent hypotheses about what symbols come next given a current con­ text of symbols. These hypotheses are tested by checking the given series to see if the current set of PR's (the learned PS) correctly predicts each symbol in the series given the partial series up to that symbol. When every symbol is correctly predicted, the system uses the learned PS and the entire problem series to predict the next symbol in the series.

For the series CABCAB the rule C A + B would be learned. This means "if the last two letters of the partial series are CA, the next is B."

Before being added to the system, rules are gener­ alized to take into account the relevant letter relationships. The problem is that rules can be generalized many ways, each being a hypothesis about which letter relationships are relevant for the series. The variations on C A + B are shown below.

The first rule above means "any letter followed by A leads to B", the second is "C followed by any letter leads to B", and the third "any letter followed by A leads to the predecessor of that letter."

If for every new rule the system arbitrarily picked a generalization, intending to backtrack to try the others when an error occurred, a huge tree of possibilities would be generated, making the problem unsolvable. The solution is to use tree-pruning heuristics to limit the number of generalizations at each step. The PS to be des­ cribed uses one powerful heuristic, the template heuristic.

The template heuristic consists of hypothe­ sizing period size, and recognizing only relations between letters which occupy the same relative position within the period, while generalizing on all letters. For example, if given the series ACABA with period 2, then the relations looked for are shown by the arrows below.

Learning proceeds as follows: period size is hypothesized and the series goes through a parti­ tion-prediction cycle . Generalized rules are added, and the cycle is performed once for each period hypothesis. A period hypothesis is false if:

1. no relation is found between letters occupying the same relative position within the period
2. or (2) the number of inter-period rules added exceeds the period size hypothesis.

When the period hypothesi s is false , it is increased by 1, and the cycle starts over. Table 2 shows this procedure for the series ABHBCICD. In line 1 we see the default rule xl + xl (always considered to generate an error) and the parti­ tioned series. Everything to the left of the slash (/) is the current context . Context A is dropped through the rules and A is predicted. This is not valid (-), as the actual next letter is B. Now the system takes context A and next letter B to form A+ B, generalizes it to get

1. (READY) (SERIES X I) ·> (REP READY CONT) (DEP (PNUM 2) (COUNTS 0)) (OBSERVES XI T)
2. (READY) ·> (ATTEND SERIES) (DEP (PERIOD I))
3. (COUNT) (COUNTS X I) ·> (REM (COUNT)) (REP XI XI')
4. (0 X I T) ·> (SUCC)
5. (FAIL) (PERIOD XI) (SERIES X2) ·> (ERASE)
6. (CLEAR) (DEP (READY) (PERIOD X I') (SERIES X2))
7. (PERIOD X I) (COUNTS X I') (SERIES X2) ·> (ERASE) (CLEAR) (DEP (READY) (PERIOD X I') (SERIES X2))
8. (NEXT Xl) · (X2 T) · (ACTION) ·> (SAY XI) (DEP (MATCH) (XI T)) (STOP)
9. (NEXT XI) (USED) (ACTION (USED) (DEP (NEXT XI))) · (MATCH)· (ERROR) ·> (DEP (MATCH))
10. (X I X2 T) (NEXT) · (DONE) ·> (DEP (OLD (X I X2 T))) (DEP (DONE))
11. I 0. (USED (X I X2 !)) ·> (REP USED OLD) . (DEP (X I X2 T))
12. 11 . (OLD (X I X2 ?)) ·> (REP OLD COND)
13. (MATCH) (NEXT X 1) (SERIES X2) (LOC X3) ·> (REP (NEXT XI) CONT 2) (REM (MATCH) (DONE) (LOC X3)) (PROD (SERIES X2))
14. (LOC X 1) (NEXT X2) (PERIOD X3) (SERIES X4) (COUNTS X5) ·> (REM (LOC Xl) (DONE) (ERROR)) (REP (NEXT X2) CONT) (PRODS (LOC X 1) X3 X4 X5)
15. (CONT) (X 1 T) (PNUM X2) (X3 1) ·> (REP X 1 (0 X I) 2) (REP X2 X2' 3) (REM (CONT)) (ACTION (k!SED) (DEP (NEXT X3)) (DEP (LOC X2)))
16. (CONT) (Xl f) ·> (REP XI (0 Xl) 2) (REM (CONT))
17. (1 X 1 ?) ·> (DEP (NEXT X 1) (LOC 1))

Figure 8. Production System for Series Completion Task xl + xl', and places it above the error-causing (default) rule as shown. In line 2 the number of rules added (2) exceeds the peri od size hypothesis (1) so a new size hypothesis (2) is made in line 3. In line 4 the rule cannot be generalized since no relation can be found between A and H*, thus size 3 is hypothesized in line 5. Line 11 completes the learning cycle and line 12 illustrates the PS making its first actual extension to the series . The concept of the se.ries is now embodied in the numbered rules (the inter-period rules). Thus we say that xi x2 x3 + xl' is the concept learned by the system, and the series predicted by thi s con­ cept is ABHBCICDJDEK ·· ·

Production System

Figure 8 shows the PS for letter series com­ pletion. Rules 1 and 2 provide initialization, rule 16 acts as the default rule, and rule 13 adds productions to the system. Figure 9 shows concepts learned using the 15 series from Simon and Kotovsky (1963). The correct predictions are made in all cases. For more on seri al pattern acquisition see Waterman (1975).

*The system does not search for relations higher than triple predecessor or successor.

VI. CONCLUSION

The PAS-II system has been described and used to illustrate adaptive techniques in production system construction. The focus has been on the machinery needed to implement self-modification within a PS framework. It has been demonstrated that using a simple production building action in an ordered PS leads to relatively short, straight­ forward programs.

Moreover, it has been shown that one can create a learning paradigm which applies to (1) simple rote learning tasks such as learning the addition table, (2) more involved learning tasks like nonsense syl­ lable association and discrimination, and (3) com­ plex induction tasks such as inducing the concept of a serial pattern. In all three cases the para­ digm consisted of creating an ordered PS represen­ tation of the concept learned by adding new PR's (or hypotheses) above the error-causing rules.

Adaptive PS's are quite parsimonious; that is, the system which learns the concept is represented in the same way as the concept being learned. Both are represented as PR's in a single PS. This elim­ inates the need for two types of control in the system; one for activating the learning mechanism and another for accessing the concept learned. The concepts learned are not passive, static structures which must be given a special interpretation, but rather -are self-contained programs which are execut­ ed automatically in the course of executing the learning mechanism.

The ADD PS is somewhat different from the PS's for verbal learning or sequence prediction. This is because ADD is self-modifying but not really adaptive in the strict sense of the word. It creates new rules, not on the basis of external feedback, but rather on the basis of internal information, i.e., the ordering on the set of integers. Furthermore, rules are added only when needed to solve the problem at hand. This is a good example of an explicit view of predetermined developmental potential. The system has the cap­ acity to develop the addition table or the succes­ sor function on integers but does so only when the environment demands it.

The EPAM and series completion PS's are extremely compact pieces of code which perform sizable amounts of information processing. Their power comes from the strong pattern matching cap­ abilities inherent in the PS interpreter and from the primitive but highly useful memory modification and system building actions employed. The compact­ ness is due, in part, to the use of ordered PR's, since much information concerning rule applica­ bility is implicit in the location of the rules. With ordered rules the system can use the simple heuristic "add a new rule immediately above the one that made the error" to great advantage.

Finally, the analogy between an ordered PS and a discrimination net has been made clear, i.e., that the condition elements are non-terminal nodes in the net, the action elements are terminal nodes, and the searches through the conditions in the PS are analogous to the paths from the top element to the terminal elements in the net.

ACKNOWLEDG!ENTS

The author thanks David Klahr, Dick Hayes, Herbert Simon, and Allen Newell for their sug­ gestions concerning this paper. This work was supported by NIH MH-07722, and by ARPA (1-58200-8130).