--- title: "Learning Procedures from Examples and by Doing" authors: - "David M. Neves" doi: "" url: "https://ijcai.org/proceedings/1985/120" pdf: "https://ijcai.org/proceedings/1985/0120.pdf" venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence" year: 1985 pages: "624-629" track: "Learning and Acquisition" keywords: --- # Learning Procedures from Examples and by Doing David M. Neves *Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 624-629. ## Abstract This paper de sc ribes a program that learns procedures hv examining worked-out ex~mples in a textbook ;md hv working problem s. Two kinds of production ( lf~lh<'ll) rules are created: ll'orl.ing .li"word rule s that produce an action when a procedure is executed ~nd dif/('r<'IIC<' rules that suggest operators from observed transformations. Durin g example leilrning . the progrllm examines tvvo states in an example, figures out the operator that produced the second state and creates a production with some part of the first line in the condition with the operator in the action. During learning 11\ wo rking problems , the program generates its own example trace by problem so lv ing and uses the same example learning techniques. ## Full text ## Abstract This paper describes a program that learns procedures hv examining worked-out ex~mples in a textbook ;md hv working problems. Two kinds of production ( lf~lh<'ll) rules are created: ll'orl.ing .li"word rules that produce an action when a procedure is executed ~nd dif/('r<'IIC<' rules that suggest operators from observed transformations. During example leilrning. the progrllm examines tvvo states in an example, fig­ ures out the operator that produced the second state and creates a pro­ duction with some part of the first line in the condition with the opera­ tor in the action. During learning 11\ working problems , the program generates its own example trace by problem solving and uses the same example learning techniques. ## lntruductiun ALEX 1 (Algebra example learner) is a program tlwt learned to solve simple linear algebraic equations bv examining worked-out examples and hv working test problems. The work (Neves, I 98 I) also included learning simple list nlgorithms, such as sorting and reversing a list. That work will not he reported here. An e~rlier version of the program was presented in Neves.(l978). Two important characteristics of these textbook examples (fi ·!icil\' condi ­ tions for learning, c.f. YanLehn, 1983) are that a. one procedure is taught per example and h. there are no hidden variables (however creating programs from examples or learning the commands of an operating system often requires the learner to induce variables that are not observable -- Dietterich. I 984). The subject matter for learning comes from a high school textbook (Stein and Crabill, I 972) on elementarv Algebra. The particular section of interest occurs after students are taught (in preceding chapters) exponents, the Distrihutiv·e Rule , factoring, and fractions. They then come to the lirst chapter in which the notion of solving an equation by manipulating svmhols is introduced. I will describe the contents of this section to giv·e an idea of what inform~tion is presented in this textbook, and which inform~tion ALEX uses to learn. I I The chapter on equ~tion fsolving tries to give ~n understanding of what an equ~tion is and wha1 operations can be applied to it by using ~ seesaw analogy wtth the equal stgn at the lulcrum. Only operattons which preserve the balance of the sees~w can he ~pplied to the equa­ tion. ALEX does not use this information. A problem with ~nalogy here is that it is difficult to draw the correspondence between a weight on a sees~w. and an operation on an equation for the novice user. Whit:h math operations preserve equation "weight"? The next part of the chapt~r sect ion teaches the legal operators of alge­ bra by showing examples of how thev work. These examples show how to add a number to both sides of an equation, how to subtract a number from both sides, how to multiply both sides by a number, and how to divide both sides by a number. The example for adding to both sides loob something like: ## Learning procedures from exam pies and b)· doing David M. Neves Computer Sciences Department University of Wisconsin -Madison Madison, WI 53706 ![Image](https://ijcai.org/proceedings/1985/fulltext/120/image_000000_a0d8b2a988ead5cf5984483982a294880e3f8b3b0267fb3c851ea94ce9611184.png) ALEX uses these examples to learn the legal operations in algebra. Next, the hook demonstrates the futility of solving for the unknown by randoml y plugging in numbers. ALEX does not use this information. Finally, the textbook presents a five step example that solves for the unknown (in the equation "3x - 4 = 0") using legal operations, such as adding a number to both sides of an equation. After thi s si ngle example six test problems are given and thi s section ends. The goal of this research is to demonstrate how learning can take place by looking at the examples and by working the problems. Examples especially are well suited for procedure instruction as they contain steps that will lead to the goal. Text (or teacher) expl~nation, on the other hand, can be misle~ding, incomplete, or false. Example learning will not generally result in a complete procedure however. The student must be prepared to use problem solving along with incomplete pro­ cedures in working the problems at the end of a section. Working problems can produce learning behavior hy having the student (or pro­ gr~m) generate an example trace through problem solving behavior. ## Basic ideas Here I will describe some of the basic ide~s behind the ALEX pro­ gram. A more detailed expl~nation follows this section. While learning from an example ALEX looks at two consecutive equ~ ­ tion lines at a time. The first line is viewed as having some operation applied to it to yield the next line. The task of the learner is to ll gure out the operation th~t took place and whv it was applied in th~t cir­ cumstance. Once the system has thi s knowledge~ worl.ing .li"ward pro­ duction rule is built with some part of the first line as the condition and the operator as the action. When done with those two lines the pro­ gram goes to the next pair of example lines, continuing until the end of the example. At the end of the ex~mple the procedure is indexed with a dif/i·rcnce production rule . The condition of thi s rule is made up of the difference between the first and last lines of the example. The action is the procedure name. ## Prfl('edure kn11wledge Procedural knowledge in ALEX is encoded as product ion rules (Newell & Simon, 1972 ; Anderson, 1983). Rules in ALEX are coded in an older version (0PS3) of the OPS famil y of production languages (Forgy, 1979). I will use a less formal, more English- like presentation of productions in thi s paper. Productions have been a popular medium for learning since Waterman (1975) because of their modularitv. l'he unit of knowledge is the production . A newly created production is added to the set of productions already in production memory. There is no need to look at the other productions in the set. Contrast thi s with a programming language where the placement of code has important implications for what action is produced. Produu ion S\'Stem l~ngu ~ges, such ~s OPS, ~re ll ~t. That is, anv pro­ duct ion can apply at am· point. To get some top-down control of the svstem some method must he developed that partitions the production s~ t so that only a few productions can apply. The usual way thi s is done (as is clone in ALEX) is to group the productions in subroutines (goal s) hv placing a goal name in the condition side of the production. When a subroutine of productions is to be called that name is placed in work ing memory. In addition to part itioning there must be some method of pass ing infor­ mation to the subroutines and of passing hack results. ALEX does thi s h~ emul :lting ~ tradition~! programming l~tngu ; tge control structure in its wor k in ~ memory. A subroutine ca ll generates a new node in menHl r\ . That node has Mtached to it several pieces of information: the name <;f the subroutine, a list of arguments, and the node of the sub­ routine that called it. When a subroutine finishes it attaches the result to that subroutine node. e.g. ## Ca ll - 145 ``` name divide-both-sides args (lx=2 , 3) ca lleclby Ca ll - 144 result ? ``` ## Declanllive knowledge Facts are stored in working memory. During example learning the example is stored in working memory. An example is made up of equation lines connected by a next relation. Each equation is represented as a tree structure (propositions) with the top node being the equation, the next level being the left side, the equal sign, and the ri ght side ; the level after that contains terms. Each side can contain I or mort! terms connected bv a next relation . For example Jx - 4 = 2 would have 3X before -4 on the left and a 2 on the right. ## Simple example learning Thi s st!ction presents some of the basic ideas behind example learning "' ithout the complications described in tht! next section. The production system has two kinds of productions for example learn­ ing. It has difference productions which are used during the learning and it has work ing forwa rd productions which are the results of the learning process. A difference production has some information about the difference between two lines on the condition side of the production and has an operator (which will cause that difference:!) on the action side:!. A working forward production is part of the subroutine of pro­ ductions. It is used when the subroutine is called. For example, work­ ing forward productions to solve for x are shown in Figure I. These producti on~ will move numbers from the left hand side to the right , will move terms with the:! unknown from the righ t side to the left , will com­ bine li ke terms, and will halt when the va lue of the unknown is found . When it is given an example the program starts at the first two lines and computes the difference between them. From thi s difference it deter­ mines which operation was applied to turn the first line into the second line. It then calculates why that operator was applied and creates a new working for.,.·ard production. After thi s it repeats tht! process on the next pair of lines in the example, until the end of the example is reached. At the end it creates a stopping production with the last line as the condition of the production rule (as in P5 above). These steps of example learning are called compute-difference, retrieve-operator , create-condition, and create-production he low. - Pl. II thert> is a number on the left hand side of an equation, tht!n subtract it from both sides. - P2 . If there is a term with "x" in it on the right hand side, then sub­ tract it from both sides. - PJ . If there are two like terms on the left (or right) hand side, then combine them. - P4. If the equation is " numl "'x= num2" then divide both sides by numl . - P5 . If the equation is " x = ntunl " then STOP. Figure I . A working forwa rd production system to solve for'· ## Computing the difference. The lirst thing ALEX does is to compute the difference between two consecut ive lines in the:! example. Thi s difference is a li st of terms that are in the lirst line but not in the second (i.e. terms that have been removed) and a list of terms that are in the second line but not in the lirst (i.e. terms that have added). For example, the two lines below: ``` X + 2 = 5 x+ 2 - 2 = 7 ``` produce a difference of (Add(- 2)) (Add (+ 7)) (Remove(+ 5)). The actual terms of the difference (e.g. (- 2)) are nodes in a network representation of the equation and contain ot her information, such as whether they are before or after the equal sign. ## Retrieving the open1tor Wht!n th t! difference is calculated it is plact!d in work ing memory. Then the difference productions are ca lled. These productions contai n difference information in the condition side:! and su1Jply an operator that produces that difference on the action side:!. One of the productions matches the difference and rt!turns an opt!rator . A difference:! produc­ tion to rt!cognize adding to both sides looks like: 01. If (Add (+ Numl )) and Numl is on the left and (Add (+ N um2)) and N um2 is on the right and N uml equal s Num2, Then the operator is add-to-both -s ides and the argument to the operator is Numl. If the two lint!s in the example are: '-5 = 10 '-5 + 5 = 10 + 5 then production Dl (above) will lire and assert that the operator used was add-to-both -sides with an argument of 5. ## Making the condition side I will talk more about thi s stage later . The condition side of the work­ ing forward production to be created wi ll contain some (or all) of the first of the two equation lines being looked at. In the least we must include the argument of the operator , plus some context information. ## Making the working forward rule Once:! we have an operator and condition side a work ing forward pro­ duction can be built and stored in production memory. A sample rule: Rl. If (- Numl) is on the left side, then add-to-both -sides(Numl ) ## The stopping and difference rules When ALEX reaches the last line of the example it creates a stopping production with the line as the condition side and the action of return ­ ing from the current production system subroutine. It also computes the difference between the first and last lines and create a difference production with the difference as the condition and the operator name as the action. ## Details uf ALEX The above desc ription is a basic introduction to learning from exam­ ples. In actual practice there are complications , such as skipped steps , and inability to retrieve an operator after calculating the difference between two lines. Figure 2 shows the top level of ALEX. Two lines are worked on at a time. In the description above, thi s step was described as if the lines were compared and an operator was retrieved. However, ALEX actu­ ally uses a means-ends subroutine. - TJ. Start with the first 2 lines of the example. - T2. Represent both lines. - TJ. Call means-ends(linel ,line2). - T4a If not at the end of the example then look at the next two lines and goto T2. - T4h If at the end of the example then create a difference production with the difference of the tirst and last lines of the example as the condition, and the name of the routine being learned as the ac­ tion. Stop. Figure 2. The top- level of the example learner. ## Means-Ends routine The means-ends routine places problem solving capabilities within the learning program. This routine (shown in Figure 3) takes two lines as input. Its goal is to apply operators to the first (and successi vely gen­ erated lines) until the second line is reached. The routine is modeled after the Newell, Shaw, and Simon (Newell and Simon, 1972) General Problem Solver (GPS) program. GPS is given operators, a table of connections (a table connecting differences to operators that produce those differences), a start and a goa l state. ALEX has no table of connections, but instead uses difference produc­ tions which connect operators to a group of changes (the difference). The means-ends routine below computes the difference between the two lines of the example and ca ll s get-appl y. Get-apply retrieves an opera­ tor (by using a difference production) that will reduce the difference between the two lines. After retrieving an operator get-apply applies the operator to the first line and returns the result (a new line for the first line). Now means-ends is called recursively with the new line to see if the goal line is reached. If this recursive call is successful (i.e. the goal line was reached) ALEX creates a working forward production with some part of the first line as the condition, and a ca ll to the opera­ tor as the action. If the recursi ve call to means-ends fails then ALEX calls get-appl y again to get and apply a different operator. ## I nput:two lines - M I Compute the difference between the two lines. - M2a If no difference, return success. - M2b If there is a difference, call get-apply. - M:la If get-apply is success ful call means-ends(new line. goa l line). - MJb If get -apply failed and thi s is an example, then tr:; a simpk transform~tion. - MJc If the simple tr~nsformation failed then return failure. - M:1d If the simple transformation was successful then build a work ing forward production, build a difference production, return the ne"' line. - M4a If means-ends failed , go to M2h (i .e. ca ll get-appl y :tgain ). - M4b If means-ends was successful then build a work ing forward pro­ duction and return the new line. Figure .1. The means-ends subroutine. ## Sl-ipped sleps One major reason for using means-ends to work through an example is that the book might have skipped steps in its presentation. For exam­ ple, suppose two steps in an examjJie are 2x - 4 = 10 and 2x = 14 . Several steps have been skipped. The full example is: 2x - 4 = 10 2x- 4 + 4 = 10 + 4 2x + 0 = 10 + 4 2x = 10 + 4 2x = 14 The means-ends routine fill s in the skipped steps by applying operators until the second line (2x = 14) is reached. These generated steps are used in the learning process just as though they were there in the origi ­ nal example. The novice user must fi ll in the skipped steps. The expert algebra prot>lem sol ver probably has an operator (add- to-both -s ides-&-simplifv) that goes directl y from the first to the second line abo,e. Thi s is an important operator to have because it gives purpose to the add-to-both ­ sides operator. Adding to both sides seems counter -productive hec;tuse it takes the problem solver away from the goa l of solving f(Jr the unk­ nown hy introducing two new terms. However, once simplification is done, it is seen that the operator is the first step in mm·ing a term from the left to the right hand side of the equation. Ski pped steps are a sig­ nal for the novice user (as they were to an earlier version of ALEX) to treat the skipped steps as a subroutine to he learned. This subroutine is indexed by a difference production created from the first and second lines of the example. ## Creating new Jrun~'f{Jrmations So far I have described get-appl y as retrieving an operator and applying it to the line. Sometimes a new transformational operator is being learned, such as in the example teaching to add to both sides below. x = 2, argument is 5 X + 5 = 2 + 5 In this example there is no operator to be recognized. Instead one is being taught. What ALEX does here (when it does not retrieve an operator) is to construct a new operator with call s to primiti ve s:;mhol manipulating functions such as "insert-after". The operator created above is a single production that inserts its argument in the left side of the equation and in the right side of the equation. Also a difference production is created so the operator will he recognized in the future. ALEX onl y creates a new transformation oper~tor when learning from an example. It is too dangerous to allow it to try to construct operators while problem solving because non-legal operators could he generated. Even when learning from examples it is possible to learn such opera­ tors. For example, ALEX could learn an operator (from 2x - 4 = 0 , 2, = 0 + 4) that moves a number from the left to the right , inverting its sign. It could also learn to delete equal terms on opposite sides of the equa l sign from (3 - 4 = 5x - 4, J = 5x). These are operators that e<tn he proven va lid mathematicall y, however their use may mask ignorance. Cr<'aling lh<' nmdilion side Creat ing the condition side of the production is difticult , and ALEX has some problems. here. Learning from examples is often associated with concept learning. Anderson, Kline, & Beasley (1980) call thi s llflling of a production by applying it to different situations . If an operator is seen to appl y in several different situations a general condition side can he constructed. If a production fires when it should not have fired, then it is puni shed and clauses have to he added to the condition to make it more specific. These tuning capabilities can take some time. ALEX does not have them. Instead, ALEX has several heuristics which do a good, hut not perfect, job in neating condition sides for produc­ tions. These are described below. Working forward productions call an operator with some arguments. The condition side of the working forward production must contain those ;trguments. The condition creator does a breadth-first search from the equation node of the fit·st of the two lines looking for the argument. When it finds the argument it places it , along with some of its context ( the path from the equation node to the argument) in the condition side. Thi s procedure is outlined below. - I . F ind a path from the current line to the argument. This path will he included in the production . Often thi s path leads from the equation node to a term within the equation. Sometimes the argument may occur elsewhere in the example (such as at the start of the example in the adding-to-both-sides example). The program now tries to specify enough of the path to make it unique, i .e. to distinguish thi s path from other potential paths from the equation node. - ;1. If there is no other path of thi s length (from the current equa­ tion node to the argument) then quit. - b. Otherwise check to see if the type (i.e. ISA property) of the argument is unique. If so, include the ISA property in the condi­ tion and quit. - c. Otherwise, check to see if the argument is in a special location in its li st (i .e. first location , last). If so, include that information and quit. - d. Otherwise , put in absolute location information . - 2 \_ Note which nodes in the network are equal and include this infor­ mation >n the condition. - .1. Add any constraints of the operator to the condition. Each opera­ tor needs a certain state configuration 10 operate successfully. This information is included in the difference production for that operator and is added to the working forward production being built. For example, canceling two terms requires that they be equal but of opposite signs ( + 5 + -5) . 4. General ize the condition by deleting all constants. ## The performance system ALEX uses two methods to work problems in the texthoo~. When it is given a problem to solve it first tries to use its working forward produc­ tions to solve the problem. If the goa l is re~ched then the problem is solved and the system halts. If the working forward rules are not suffi ­ cient to solve all the problem it will halt at some point , short of the goa l. Here the problem solving (means ends) component takes over and suggests an operator to try next. If thi s operator leads to the goa l then a working forward production is built so that problem solving will not have to be done in the future. ALEX starts out with slow problem solving behavior, graduall y working its way to fast expert (working for­ wa rd) behavior with experience in work ing problems . The perfor­ mance system will he di scussed in more detai l later . ## Traces of algebra learning This section describes how ALEX dealt with the 5 examples in the text­ book. Leaming 10 add 10 b01h sides ALEX first learns the legal Algebra operations , such as adding a number 10 both sides. It is given an example like: x = 2 (argument is 5) X + 5 = 2 + 5 It looks at the two lines and notes that two ( + 5)'s have been intro­ dtteed. It does not have an operator that will do thi s transformati on so it makes one with its primiti ve list operations. It creates a single produc­ tion procedure AI . A I . If the goal is add-to-both -sides argl is =equation, arg2 is = toadd - = Llerm is a left side term = Rterm is a right side term Then insert ( + =toadd) after = Llerm insert(+ =toadd) after =Rterm return from add-to-both-sides ALEX also creates a difference production (D I ) with the difference in the condition side and the add-to-both -sides name in the action side. - OJ . If the goal is get-action (Add ( + = Lterm)) (Add ( + = Rterm) ) ( = Lterm equal s = Rterm) = Llerm is a left side term. = Rterm is a ri ght side term Then the operator is add-to-both -sides the argument is = Llerm Leaming 10 di>·ide bolh sides ALEX next learns how to divide both sides by a number with the fol­ lowing example. No operator is found that will transform the first line to the second so the system must construct an operator (A2). - A2. If the goal is divide-both -sides arg2 is = di v = Ltenn is a lett side term = Rterm is a right side term Then replace = Lterm with (I = Llerm = div) replace = Rterm with (I = Rterm = div) return from divide-both -s ides The problem with production A2 is that it is dividing terms on both sides and not the sides themsel ves. The example is ambiguous because there is onl\ one term on a side. The production will not generate an error until it is applied to a side with more than one term. In that case it will di videjust one term , as in: ``` .1x - 4 = 5 ;divide hy 3 ``` ``` 3xl.\ - 4 = 5/l ``` It turns out this is an error generated by novice Algebra solvers as well (Davis & Cooney, 1978). The difference production created for dividing both sides (02) shows some propositions (under nmdilicms) on the action side. These an~ pro­ positions that are needed in order for the operator to successfu lly apply (i.e. in order to divide you need something to divide). When a working forward production is created from thi s rule these propositions are added to the condition side of that newly created rule. This is step 3 of the condition creation routine explained ;,hove. ``` 1>2. If the goal is get-act ion (Add (I =LtermR =div)) (Add (I = RtermR =div)) (Remove = LtermR) (Remove = RtermR) = LtermR is a left side term = RtermR is a right side term Then the operator is divide-both-sides the argument is = div the concliliollo are = LtermR is a left side term = RtermR is a right side term ``` ALEX also learns how to subtract both sides of an equation by a number and how to multiply both sides by a number . These produc· tions are simil;,r to the ones above for addition and division. ## Learn;ng to soh'£' for x ALEX now knows the lega l operators of Algebra. It next is given an e' ample to learn ll'h<'ll to use these operators in solving for the unk· llOWil. ``` I. .h+4=6 2. 3x + 4- 4 6- 4 3 . . h 6-4 4 . . h 2 ``` 5. 3x!J = 2/.1 6. X = 2/3 Lines I and 2 are processed first. The difference production for subtr;,ct-both-sides tires. suggesting a number was subtracted from both sides of the equation. The operator is applied to line I and line 2 is reached. The hypothesis is confirmed. To compute the condition side it searches the first line for a "4". the argument to the operator it found. It finds 4 on the left side of the equation and builds A4. A4. If the goal is solve-for-x - = Lterm is ( + = number I) = Lterm is a left side term Then subtract-both-sides(- =number!) ALEX has learned ll'h<'ll to use subtract-both -sides when solving for x. ALEX now examines lines 2 and 3. A difference production for de lete-terms tires . Thi s difference production was learned in previous chapters as part of instruction on simplification (it is given to the ALEX program). Delete-terms takes as input two equa l terms, but having dif­ ferent signs, and deletes them. A5 is built from l ines 2 and 3.: ``` J\5. II the goal is solve-for-x = Lterml is(+ = thing!) = Lterml is a left side term = Lterm2 is(- = thing!) = Lterm2 is a left side term Then delete-terms(= Lterml , = Lterm2) ``` Note here that the production is a bit too spec ific. It will not tire if two like terms are on the right hand side of the equation. Lines .1 and 4 show another arithmetic operation in progress. A pro­ duction that is very similar to A5 above is created. Lines 4 and 5 demonstrate when to divide both sides by a number . A difference production for di vide-both-sides fires and A6 is built. A6. If the goal is solve-for -x ``` = Lterm is(+ = numl '1' x) = Lterm is a left side term there is a term on the left and a term on the right ;dividing both sides requ i res there be something on the ;right hand side to di vide ``` Then di vide-both-sides(+ = numl ) The problem with A6 is that it is too general. There is a possibility that the rule could fire if there were more than I term in either side of the equation. The last two lines of the example suggest another simplification opera­ tor. Two numbers are canceled. Production A7 is built. - A7. If the goal is solve-for -x ``` =Lterm is (=tl * =t2) I = tl = Lterm is is a left side term ``` Then cancel( = Lterm) After tlni shing thi s example ALEX has b (i ncluding the stopping pro­ duction) worki ng forward productions that will solve the same problem shown to it as wel l as other similar probl ems . In add ition it has the 4 working forward productions which are lega l operations in A lgebra and their 4 difference productions. Solve-for-x also has a difference pro­ duction associated with it. ## Learning by dning After going through the example ALEX is given six problems to solve. These are: a. 6x - 5 = 0 b. x/7 + 4 = 0 c. 4x = 7 d. 5x + 7 = 0 e. x/2 = .1/8 f. 1/x = 2. Some of these problems can be soh·ed with just the working forward productions built from the example. Others wi ll require some problem solving. During that problem solving new learning can take place. Prohlem c is very similar to the example and is solvable with the exist ­ ing productions. Both sides of the equation are di vided by 4. then the two 4's on the left are canceled to yield x=7/4. Prohlem d is very nearly solved also. The problem comes with the too general production that divides both sides by a number. For the first step either both sides can be divided by 5 or 7 can be subt racted from both sides. Because OPS production system conflict resolution prefers productions with larger condition sides the incorrect (di vision) produc­ tion is picked. If the subtracting-from-both -sides routine is executed ( i .e. after backing up from the other production application) the prob­ lem is solved. The division production needs some di scr imination tun ­ ing (Anderson. Kline, & Beasley, 1980) which wou ld compare the problem state during a successfu l invocation of the production with the failure state. See the discussion at the end of the paper. Problem a is the first which requires some problem solving. It is simi ­ lar to the example except th~t a number is s ubtr~cted on the left side instead of bei ng ~dded. There is no production th~t !Ires, so the system enters into problem solving. ALEX now tries to reduce the difference between 6x - 5 = 0 and the goal (x = number). One difference is that the 5 needs to be deleted on the leti. An operator is retrieved (add­ inverse) that will do that but it is not a legal Algebra operator. A lega l operator is searched for that is simi lar to add- inverse and add- to-both­ sides is found and returned. Note that the process here is somewhat different from the table of con­ nections in GPS. The difference is that the operator retrieved might not he> legal in the domain being worked on. The reason a non lega l operator was found above was that the oper~tor was sensitive to the changes it causes -- i.e. one can get rid of ~ number by adding its illlerse. This knowledge came about through training in simplification (perhaps even when steps were sk ipped). The Algebra operators (;~dding- to- both -s ides, etc.) have not yet been indexed by the ch~nges they ultimatel y produce (i.e. moving a term from one side to another). Since adding-to-both-sides was retrieved during problem solving a new product ion is built that will apply add- to-both-sides if there is a neg~tive number on the left hand side of the equ~ti on . Problem a is finished up by di,iding both sides by 6 and simplifying. Problem b is x/7 + 4 = 0. The program starts out by subtracting 4 from both sides and simplifying. It is now at x/7 = -4 and starts to problem solve. ALEX compares its current state to the goal and sees that it shou ld get rid of the 7. As in the previous problem it retrieves an inverse operator that will do it (to multiply by 7) but it isn ' t legal in A lgebra. It then searches its memory for a lega l Algebra operator that is similar ~nd finds the operator multiply-both-sides. It successfull y carri es thi s out and builds the working forward production "If x/nl = n2 Then multiply both sides by nl ". Problem e (x/2 = :l/ 8) demonstrates what is ga ined in learning by doing. If no other test problems had been done before getting toe then some problem solving behavior would have been needed to solve it. However solving problem b has created a production that can be used in this problem. The first thing done is to fire a production, created in Problem b, that multiplies both sides by 2. Then simplification is done to give x = 6/8. Problem f (1/x = 2) is too hard for t11e problem solving system. It starts out by multipling both side2 by x to get x on the left hand side. After simplification it has x = 2x . It cannot get any closer to the goal from here. Later on in thi s chapter a whole sect ion is devoted to thi s kind of problem . The suggested solution is: ALEX would have to w~it for such an example to be able to solve it. ## Summary ALEX kMned to sol ve simple equations from two pages in a textbook. It first learned the four legal operators by look ing at ex~mples showi ng what they do. ALEX then learned when to use those oper~tors (as well as when to use simplification operators) by going through an example solving for x. ALEX was then given six problems to solve. Two of the si x problems can be solved wi th the working forward productions buill during example learn ing. ALEX needed 10 use problem solving to solve two of the other three problems. As it found an operator that would get it to the goa l it created a work ing forward production so that it would not have to prob­ lem solve agai n in similar situat ions. The third problem used a pro­ duction built during a previous problem and did not need problem solv­ ing. The last problem (1/x = 2) was too hard for ALEX . The solution involves some steps that take one away from the goa l of solving for x. Thi s problem is difficult for human beginners as well . ## Problems ## Creating Ihc condilion side There were both good and bad points on the development of the condi ­ tion side of the productions. The worst part was that there was no facil ­ ity for changing the condition side given feedback on how the produc­ tion did. This resulted in many productions that were too specific and a couple that were too general. One way to correct the general rules is to use a di scrimination procedure (Anderson, 198:1) on the general rule. In order for d i scrimin~tion to work the aberrant rule must be first be iden tified . One way of identi fyi ng the aberrant rule is to use a check procedure (substitute the correct answer for the unknown and see where equ~tion equality is violated). ll nfortu n~tel y, checking is is not taught until the next section of the equation chapter. The rule can ~ ! so be identified by comparing its application with one in an example. If it is !Ired in a very different situation then it is a canclid~te for change. In the case of di viding both sides above, the rule tires when there are two terms on the left hand side. This looks different from the equation in the example which h~s ~single term on the left. Once a bad rule has been identified it must be changed by comparing the situation of incorrect applicat ion with a situation of correct applica­ tion. In our case we have an instance of correct application in the worked-out example. If we compMe the example of dividing both sides (:lx = 2 to :lx/3 = 2/:1) wi th the incorrect applic~tion (5x + 7 = 0 in Problem d) we noti ce that the left side has an extra term (the 7). We change our rule (A6) by add ing that constra int (see the propos ition in italics below). ``` A6' If the goal is solve-for-x = Lterm is (+=numl * x) = Lterm is ~ left side term there is a term on the left and a term on the right ih<'l'c is only one lcji lwnd side 1<'1'111 Then divide-both-sides(+ = numi ) ``` T he best part of how condition creation was clone was that the program did not need many examples in order to form rules that wou ld work . The textbook onl y provides a single example of solvi ng an equation in this section . It is not unreasonable to expect that students (or program) have learned something about generalization in the mat hematics domain before com ing into equation solving. Experience with simplification shows that parti cular number constants are not important and neither are terms not directl y involved in the simplification. ## Goal sm sil i l'<' dil/(·rci iC<'.I. During problem solving ALEX made use of the fact that arithmetic operators were sensi ti ve to the changes they eventually produced. For example, to get rid of a number one can add its inverse. ALEX can learn to index operators this way if sk ipped steps are used. Another way of learning to index operators in thi s manner is to observe how well each operator gels one closer to the goal when either goi ng through an example or problem solvi ng. If an operator takes one away I rom lhe goal (such as adding 10 b01h sides of an equalion) !hen follow lhe '";unple tllllil al a stale lhal is closer lo lhe goa l. The is ana logous 1o an inqnisil ive sllldenl sayi ng "Whv was that opera10r applied? It doesn ' t seem to help gel me lo I he goal. " As the example is followed one of the steps will be closer to the goa l than the original step (see the skipped sleps example above for such a sequence). The ori ginal opera­ lor is then indexed bv the change il eventually brings about. ## Conclusion One of the main results of thi s resea rch is 10 show how learni ng, prob­ lem solvi ng, and performance can be combined into a single system. Learning from examples creates worki ng forward producl ions that can be used in the performance syslem. While learning one must some­ times problem solve 10 fill in skipped sleps. A lso, as new procedures are being learned !hey are indexed by their changes (i.e. a difference production is created). This means that the learni ng system can then recognize more complex examples and the problem solving system can bring 10 bear high level operators to work on difficu lt problems. ## Footnote 1 Special thanks go my Ph.D. comminee at Carnegie-Mellon (H.A. Simon , chairman; D . Klahr, .1. Greeno, and .1 . Larkin) for all thei r help in the area of learning and instruction as well as encouragement throughout. Thanks also to .lola .lakimi k and 10 an anonymous reviewer. The ALEX program was run on a KLIO compuler and was made up of about 70 OPS productions and 25 pages of UCI LiSil code. ## References 1. Anderson, .l . R. lile orchilecll•re or cognilion. Camb ridge, M A: H ar- va rd U ni vers ily Press, 1983. 2. Anderson, .J.R. , Kline, P., & Beas ley, C. M . Complex lear ning processes. In R. E. Snow, P. A . Federico, and W. E. Montague (Eds . ) . .-iptitudc. learning. and illslntclion: Cognilive process ww- IV . H'S. H i ll sdale, N J: Lawrence Erlbaum, 1980. 3. Davis, E . .l. & Coo ney, T . .l . Identi fy in g errors in solvin g certain linear eq uat ion s: So me findings and so me suggesti ons. AERA paper . 1978. 4. Dieneri ch, T.G. Learning about syste ms that co ntain slate variables. l'rvceedings vflhe 19154 AAAI, 96-100. 5. Forgy, C. The OPS4 Reference Manual. Departmenl of Co mputer Science, Ca rnegie-Mellon University, 1979. 6. N eves, D .M .. A computer prog ram th ai acq uires algebraic procedures by examining exa mples and by wo r ki ng on test problems . 1-'rvceeding; vr 1/ie Second Na1ional Cunfi•n•nn• or 1/ie Canadian Socielv./i>r Compulalimwl S111dies or lnlelligmcc, 1978 , 19 1-195. 7. Neves . D.M. , Learnin g procedures from e'a mples. Ph.D. Di sserta- ti on, D epartment of Psychology, C~rneg i e-Mel lon U ni versily , 198 1. 8. Newell, A. & Sim on, H. Human problem solving. E nglewood C liffs, N.l: Prenli<.:e-H all, 1972 . 9. Stein , S. K., & C rabill , C. D . Elemen/a rv al.~ebra : A guided inquiry. Boston, H oughton Mifflin Compa ny, 1972. 10. Waterman, D .A. Adaptive production system s. l'roaedings of IIi<' Founh IJCAI, 1975 , 296-303. 11. YanLehn, K., Felicity conditions for hum an skill acqui silion: va lidat- in g an A l -based theory , Rep . No., CI S-2 1, Xerox Palo A lto Research Center , 1983 .