Concept Formation over Explanations and Problem-Solving Experience

1 Introduction: Principles of Memory Organization

An increasingly well-accepted view in psychology and AI is that problem solving is a process of classifica­ tion. Performance improves by learning patterns that discriminate between problem-solving choices. Produc­ tion system models of learning and problem solving (e.g., [Langley, 1985]) make the 'problem solving as catego­ rization' view explicit, as do models of case-based rea­ soning [Kolodner, 1987] . Another paradigm concerned with learning and problem solving is explanation-based learning [Mitchell et at., 1986; Minton, 1988]. Each of these three strategies aims to improve the efficiency with which knowledge is accessed and reused in novel problem-solving situations.

Of these three approaches to improving problem­ solving performance, we will focus on explanation-based learning, though the general approach that we describe is relevant to other paradigms as well . In particular, we have looked at explanation-based learning as a model of learning to solve algebra story problems [Mayer, 1981] . Consider the problem,

"A train leaves a station and travels east at 72 km/h. Three hours later a second train leaves and travels east at 120 km/h. How long will it take to overtake the first train'?"

*This research was supported by NASA Ames grant NCC 2-645. We thank the reviewers for useful comments.

A learner with a set of primitive rules that consti­ tute domain-specific knowledge (e.g., Distance = Rate · Time) and general algebraic knowledge (e.g., a·b = c --> a = c/b) forms a solution to this overtake prob­ lem that is abbreviated in Figure 1. The time until overtake {Time = Distance / Rate) may be obtained from the distance that must be made up by the faster train {D = D1 + ~d, where D1 is the distance traveled by the first train before the second train starts) , and the relative rate of travel of the second train (R = R2 - R1). Explanation-based learning will generalize the arguments (i.e., by turning them to variables in a con­ trolled way) of this AND-tree solution trace so that it can be reused on future problems.

Unfortunately, even after variablization, the applica­ bility of this solution trace will be highly limited. Con­ sider a second opposite-direction problem,

"Two trains leave the same station at the same time. They travel in opposite directions. One train travels 64 km/h and the other 104 km/h. In how many hours will they be 1008 km apart'?"

which has a solution structure almost identical in form to the solution of Figure 1; it differs only in the structure of the boxed subtree. Nonetheless, the earlier solution cannot be used to solve the new problem unless the basic EBG process is altered. Flann and Dietterich [1989] and others [Hirsh, 1988; Pazzani, 1988] suggest the utility of performing Induction over Explanations (loE) which can generalize an explanation beyond simple variabliza­ tion. loE does this by superimposing a set of AND-tree explanations, and pruning subtree structures that are not shared by all trees. For example, performing loE over the explanation trees for an opposite-direction and overtake problems would yield a tree structure with the boxed rightmost subtree of Figure 1 severed.

Using loE, the common substructure of multiple ex­ planations can be reused in a wider va~iety of situ­ ations . The substructure does not provide the com­ plete explanation, but it ideally provides a sizable chunk that can be completed using the primitive rules of the original domain theory. Thus, induction over ex­ planations abstracts redundant substructures out, thus promising to improve the efficiency with which applica­ ble learned knowledge can be found and reused.However, unconstrained induction can remove all the benefits of explanation-based learning. Consider that there may be radically different explanations of why oat-bran cereal and baked fish are health-food. Abstracting out the common substructure might yield an 'explanatory' sub­ structure heal th-food(x), which is a trivial statement of the ta~get concept. Thus, on one hand maxima~ly­ operational explanations provide a complete explanatiOn for new situations, but it is difficult to find apphcable ex­ planations since redundant structures must be searched multiple times. Conversely, maximally-general struc­ tures (e.g., cup(x), health-food(x)) ma~e it easy ~o find applicable past 'experience', but nothmg useful IS gleaned in having done so.

The tradeoffs of an explanation-based memory are closely related to tradeoffs traditionally found in induc­ tive concept formation [Fisher, 1987; Lebowitz, 1982; Kolodner, 1987]. Ideal object concepts are those where many features are predictable (i.e., favoring specific con­ cepts), but many features are also pre_dic~ive (~-e._, fa,vor­ ing general concepts). Our concern w1th prediction ac­ curacy in explanation-based. learning may seem at odds with the traditional view that efficiency is the critical performance dimension in explanation-based lear~ing . However, choices in a domain theory search constitute predictions; informed and accurate decisions at choi~e points result in an efficient search, while erroneous deci­ sions are the cause of backtracking and inefficiency. The hypothetical curve of Figure 2 illustrates performance trends that might be expected. Maximizing predictive­ ness (generality) will underfit the data, necessitating un­ informed prediction (e.g., uninformed search through a domain theory) . Conversely, maximizing predictability (operationality) will overfit the dat~ and introduce r~­ dundancies into the search for apphcable past experi­ ence. An ideal abstraction should be relatively unique and easily identified; it can then predict a sizable por­ tion of the complete explanation structure; the domain theory is only required to complete the proof (e.g., of relative rate).

This paper shows that inductive methods of concept formation [Gennari et al. , 1989] can abstract redun­ dancy out of explanations and organize shared substruc­ ture(s) to improve the efficiency of finding explanations for reuse. Section 2 describes our system, EXOR (EXpla­ nation ORganizer), which clusters and classifies explana­ tions based on shared structure. In section 3 we report experimental results which illustrate that ExoR effec­ tively improves problem-solving efficiency in a domain of algebra story problems. Sections 4 and 5 analyzes the strengths and weaknesses of the approach, and de­ tails its relation to ongoing research in explanation-based learning.

2 Concept Formation over Explanations

Our system, ExoR, performs concept formation over ex­ planations. We use the domain of algebra story problems [Mayer, 1981] to describe and evaluate our system. In particular, ExoR embeds loE within a control structure for building abstraction hierarchies that was inspired by Lebowitz's (1982) UNIMEM and Fisher's (1987) COBWEB. Figure 3 gives an example of the type of abstraction hi­ erarchy formed by ExoR over algebra story problems that span 16 types (e.g., overtake, opposite direction, roundtrip) taken from Mayer [Mayer, 1981] . Solutions to these problems range from very similar to quite differ­ ent. The domain theory includes formulae like those de­ scribed above with a variety of ways for solving the quan­ tities: Distance, Time, and Rate. Within each node of the abstraction hierarchy is a generalized-explanation subtree that is common to all descendents of the node. If there is no common substructure over the entire set of observed explanations, then the root of the hierarchy will be empty.

To incorporate an explanation into a classification tree, the explanation is compared to the explanation substructure of a node of the abstraction hierarchy (ini­ tially the root) and the remainder of the loE procedure is applied to generalize the new explanation and the node's substructure. If this results in a generalization that is equivalent to the node's generalized explanation, then the new explanation must be more specific than the node's partial explanation; in this case classification of the explanation proceeds to the children of the node.

If IoE yields a structure that is more general than the current node, then the node's explanation structure is not more general than the new explanation; in this case, the new explanation is made a sibling of the node. Of course to be useful the hierarchy must not simply be used t~ store explanations, but it should facilitate ex­ planation construction. In this case, ExoR solves a tar­ get concept (e .g. , distance) using a problem statement of operational predicates and the classification tree. If the subexplanation stored at the node is applicable to the new problem and the variable instantiation constraints (if any exist) can be satisfied by the new problem then one of the node's children is selected for investigation.

Figure 4 illustrates the basic classification process. As search down the classification tree proceeds, EXOR extends the solution to the current problem using the subexplanations that are stored at each node along the path. If a contradiction occurs between a node's partial explanation and the known conditions of the problem statement , then the node is abandoned, its conditions (the partial explanation) are retracted, and search con­ trol looks to a sibling of the node. That is, control re­ turns to the node's parent and another child is explored. If all of a node's children result in contradictions then an attempt is made to complete the partial explanation ac­ cumulated thus far by using the domain theory. This 'last resort ' is represented in Figure 4 by the 'house-shaped', dashed boxes that emanate from examined nodes. If this fails then the node is abandoned as above (i.e ., its con­ ditions are retracted and backtracking returns control to the node's parent).

Figure 4 indicates that classification is not necessa_r­ ily deterministic. Some search of the tree (and _d~mam theory) is still required, though we hope that th1s 1s less than an uninformed search of the domain theory. To direct classification, a measure of category utility [Gluck and Corter, 1985] is used to rank the promise of children under a node. In addition to storing a partial explana­ tion at a node, which is true of all of the node's descen­ dents, we store statistics on the distribution of opera­ tional predicates of explanations stored under the node - statistical trends in operational predicates can be used to heuristically guide the selection of nodes from which ExoR builds an explanation for the current problem.

Intuitively, category utility is a measure of the pre­ dictability and predictiveness of a new problem's oper­ ational predicates relative to a category - i.e. , a classi­ fication tree node. The predictability of a predicate Fk relative to a category (node) N, is given as P(FkiN, ): the probability that Fk will participate in an explana­ tion stored under N, . The predictiveness of a predicate is given by P(NilFk): the probability that an explana­ tion with Fk will be stored under N, . Recalling the dis­ cussion from Section 1, category utility is a tradeoff be­ tween these two factors : Lk P(Fk)P(N,JFk)P(FkiN, ), where P(Fk) weights the importance of the tradeoff for the most frequently observed predicates. When a prob­ lem statement is presented to ExoR, candidate nodes are ranked by their category utility scores over the op­ erational predicates. The highest scoring nodes are in­ vestigated first. Contradictions may still arise, causing ExoR to abandon a proposed node, but the inductive assumption is that the distribution of operational pred­ icates provides considerable heuristic guidance.

3 Experimental Results

ExoR's ability to improve problem-solving efficiency in the domain of 48 algebra problems was tested. A subset of 32 problems were selected for training and 16 were selected for testing. At intermittent points in training (i .e., every four problems), the performance of the ExoR classification tree was evaluated. In particular, we com­ pared the total number of predicates instantiated using a domain theory search (no learning), an Eso-like sys­ tem, and the heuristically-guided EXOR tree search over the 16 test problems. 1

Figure 5 illustrates the total number of predicates in­ stantiated during a domain theory search and an ExoR classification tree search as training proceeds over the 32 training problems. The experiment has been run ten times with different random orderings of the data. The dashed horizontal line reflects the total work performed from domain theory search alone (i.e., no learning) over the 16 test problems. The amount of work performed by ExoR trees is also graphed, but recall from the de­ scription of the explanation-construction procedure that search using an ExoR classification tree stems from two sources. First, ExoR searches a path in the classification tree to find a maximally-specific node that appears to be applicable to the new problem. The partial explanation at such a maximally-specific node may not contradict the operational (observed) predicates of the new prob­ lem, but the partial explanation may not be successfully extended by any of the node's children. However, before a node is abandoned, a final effort is made to extend the partial explanation using the domain theory; these (nested) domain theory searches are the second source of search. The shaded (lower, increasing) area reflects search in tree nodes; the upper (decreasing) curve gives the total amount of search required to solve all 16 test problems including the domain theory search (i.e., the difference between the upper and lower curves) to com­ plete partial solutions. Thus, ExoR reduces the over­ all effort required to solve problems (i.e., the decreasing curve); the effort that is required is increasingly borne by the ExoR classification tree, while the domain theory plays a corresponding smaller role as training proceeds.

1 There are many dimensions over which we could have compared performance (and did): the total number of rules examined, and the total number of backtracks. We report predicate instantiations, as this is the most granular dimen­ sion. We did not choose to systematically investigate cpu time since the 'no learning' condition and our Eso imple­ mentation take direct advantage of the Prolog interpreter in applying rules, while ExoR includes some overhead that is implementation-based, and not of theoretical consequence. This is not to say that all of our system's overhead is sim­ ply implementation-based. For example, the use of category utility and probabilistic matching are legitimate theoretical concerns in terms of rule match cost. Future work will have to untangle theoretical from implementation overhead. Suffice it to say that currently ExoR and Eso appear comparable in terms of cpu time, though this is a dubious comparison in favor of Eso. See Segre, Elkan, and Russell [1990) for a good summary of possible performance dimensions.

The efficiency of EBG has not been graphed, but it was tested on the same data. After 32 training prob­ lems, Eso required 1352.6 predicate instantiations to solve 16 test problems . This is considerably more than either the domain theory alone or Ex oR. Ex oR's relative success stems from its ability to exploit shared partial solutions. For example, ExoR can exploit the general­ ized solution from an 'opposite direction' and 'overtake' problem to partially solve a 'closure' problem; some­ thing that EBG can not do. This limitation of Eso is magnified when there are many explanations that dif­ fer in very minor ways. For example, suppose that an opposite-direction problem describes a car traveling east and the other traveling west, and there are domain the­ ory inference rules that tell us that east and west are opposite-directions, as are north and south. Eso will not be able to exploit the solution to the first prob­ lem in its attempt to solve a new problem, which is iden­ tical to the first, except that the cars are traveling north and south. In fact, the great similarity between prob­ lems may lead to a considerable amount of redundant search until a contradiction is found . This was the case with many of the problems in our domain, thus the poor performance of Eso. However, EBG proves quite ade­ quate on problems that structurally match previously­ observed problems. In the following section we will dis­ cuss this and other issues of explanation-based learning, and the manner ,in which these limitations are addressed by ExoR using lessons adapted from inductive learning.

4 Selective Utilization and Pruning

In addition to our experimental demonstrations, ExoR classification hierarchies also suggest natural approaches to specific issues in explanation-based learning. One of these concerns the selective utilization [Markovitch and Scott, 1989; Mooney, 1989] of learned knowledge. Un­ der what conditions should learned knowledge be ex­ ploited and when is it best to rely solely on the initial domain theory? Markovitch and Scott's LASSY accumu­ lates statistics on how frequently each antecedent of a rule will fail; learned rules are only used in attempts to prove antecedents that have succeeded sufficiently often (e. g., at least 50% of the time). The justification for this strategy is that if a subgoal is likely to fail then one should not search for a subproof in vain twice - once with learned rules and once with the domain theory from which the learned rules were constructed. Mooney's [1989] EGGS uses a technique that is similarly motivated. These approaches mitigate the utility problem and im­ prove efficiency, but nonetheless suffer from two limi­ tations. First, the likelihood of subgoal failures is only estimated within the context of a single (domain theory) rule; intuitively, one might expect that the likelihood of a subgoal failure would be dependent on the more com­ plete problem solving context. Second, LASSY and EGGS decide to make all learned rules available for examination or none; rather we believe that the relevance of learned rules will vary with problem solving context. It should be possible to ignore rules that are deemed irrelevant.

An EXOR classification hierarchy addresses both lim­ itations. Each node represents the status of the com­ plete problem-solving context. The system maintains statistics much like LASSY's number of backtracks (fail­ ures) at each node. Nodes with an unacceptable number of backtracks (e.g., greater than 50% of the time) are pruned [Quinlan, 1986]. If all of a node's children are pruned then this effectively identifies the problem solv­ ing contexts in which the system should rely exclusively on domain theory. Those children that do remain serve to identify learned extensions that have been previously applicable; learned rules that are not present in these children are not considered when attempting to extend the explanation from the current node. Figure 6 illus­ trates the classification process after pruning low utility nodes. Rather than overfit the problem solution, ExoR turns to the domain theory at 'suitable' levels of speci­ ficity.

5 Cost-Effective Features

In addition to pruning, we have also investigated a sec­ ond extension. Initially, ExoR's search procedure was guided by a category utility score computed solely over predicates that are known to be true from the prob­ lem statement. Thus, problem statements draw anini­ tial boundary of operationality [Braverman and Russell, 1988]. However, this boundary is not necessarily opti­ mal for purposes of efficiency. For example, recall from an earlier example that predicates such as east and west convey little information per se - it is the inferred predi­ cate, opposite-direction, that distinguishes solutions to which a problem corresponds. Thus, improved perfor­ mance is expected by combining some forward-chaining capabilities (e.g., inference from the problem statement to an appropriate boundary) with the backward chaining mechanisms that currently dominate Ex oR's processing.

The success of forward chaining depends on identify­ ing predicates (e.g., opposite-direction) that differen­ tiate categories of different problem solving experiences, thus better focusing the sear·ch for solutions to new prob­ lems. However, proving or disproving the truth of a pred­ icate requires effort as well. Thus, an ideal boundary of operationality includes predicates with greater effi­ ciency benefits than costs. We can formalize this notion in terms of the expected number of problem-solving steps (or predicates instantiated, or any of several other mea­ sures of cost) required to solve a problem with and with­ out knowledge of a predicate's truth. Let E(ciN) be the expected cost of solving an arbitrary problem beginning at node N of an ExoR classification tree. Assume that we investigate the children, Ci, of N in order of prob­ ability. Our inductive assumption is that children will successfully extend the current problem with roughly the same probability that they successfully classified earlier problems. Thus,

where P(Cmaz) ~ P(Cmaz-1) ~ ... ~ P(Cmaz-m), E( ciCi) is the expected cost (e.g., number of steps) of successfully finding the problem's solution under a child, Ci, and U ( ciCi) is the expected cost in an unsuccessful search of Ci for a solution to the problem. Thus, the cost of finding a solution in the second most probable subtree of N, Cmaz-1, includes the cost of having first searched the most probable node unsuccessfully. These quantities can be computed or at least approximated from the statistics that are maintained in the tree (e.g., P(Cj)) and from the structure of the tree itself (e.g. , E(cJCj)). Using similar constructions we can approxi­ mate the expected cost when the truth of a predicate F~c is known, E(cJN, F~c), and the expectation in the case of ·F~c , E(cJN, ·F~c).

Putting these quantities together, it is useful to for­ ward chain in an attempt to verify a predicate if

where E(cp F~c) is the expected cost to prove the predi­ cate F~c, P(F~cJN) is the probability that we will be able to prove the truth of F~c and 1- P(F~cJN) is the proba­ bility that it is not true. In general, knowing the com­ plement to be true can also be predictive of a particular course of action, and ExoR exploits this knowledge as well. P(F~cJN) can be approximated by the proportion of explanations stored under N that contain F~c and the proportion that do not. E(cp F~c) and E(cp -,Fie) are currently approximated from the domain theory: how many rules contain F~c as an consequent and how many rule combinations can conclude F~c - assuming that the combinations that are responsible for concluding F~c are equiprobable, the expected cost is proportional to ap­ proximately 1/2 the cardinality of this set. Intuitively, the greater the branching factor and distance of F~c from the initial operational (problem statement) boundary, the greater the cost of inferring it. 2

Notice that the utility offorward chaining on a partic­ ular predicate F~c varies with the problem-solving con­ text (i.e., node N) ; we only expend work on inferring F~c when it will help distinguish N 's descendents. Once identified, statistics on these predicates are used in the category utility calculation to bias search in the most promising directions.

Table 1 shows the result of the ExoR's performance after the 32 training examples with forward chaining and pruning. These extensions reduce the search within the ExoR tree by 6.1% and the saving from the domain theory search to complete a partial solution is 22.3%. The total savings from forward chaining and pruning is 11.8%.

6 Concluding Remarks

ExoR abstracts redundant explanation substructures and organizes them hierarchically for reuse, thus yield­ ing advantages in terms of problem-solving efficiency.

2 Notice that E(cp Fk) is not conditioned on N, though this is clearly a preferable strategy; explanations under N may exhibit a relatively small number of combinations to proveN. Thus, we wish to approximate E(cp FkiN) in the future.

More generally, our research seeks to unify principles of inductive and explanation-based learning. First, tra­ ditional explanation-based concerns with efficiency can be cast in terms of the traditional inductive perfor­ mance dimension of prediction accuracy: accurate pre­ diction along search choice points result in a more ef­ ficient search [Carlson et al., 1990; Fisher and Chan, 1990]. To some extent this relationship was recognized in earlier work that treated search-control learning as a problem of concept induction [Mitchell et at., 1983; Langley, 1985]. However, we have strengthened this connection in several ways. Notably, principles of fea­ ture predictiveness and predictability, which play a con­ siderable role in inductive concept formation systems [Lebowitz, 1982; Kolodner, 1987; Fisher, 1987], are also used to identify informative, cost-effective predicates and to guide the search for relevant past experience with these predicates. Second, too much emphasis on feature predictability (specificity) can lead to data overfitting in explanation-based learning, as well as in inductive sys­ tems [Quinlan, 1986; Fisher and Chan, 1990] where it has been a long recognized problem. Pruning in EBL contexts, as with inductive systems, mitigates the prob­ lem. Finally, ExoR's inductively-motivated approach addresses some specific research concerns in EBL, no­ tably the problem of selective utilization [Mooney, 1989; Markovitch and Scott, 1989] and identifying appropri­ ate boundaries of operationality [Braverman and Russell , 1988].

A second research direction is to extend Ex oR to other domains, particularly fault diagnosis. Many engineering projects (e.g., designing a purifier/pump system) con­ struct a fault tree [Malasky, 1982], which is an AND/OR structure that describes the events (singly and in com­ bination) that may lead to a top-level fault (e.g., loss of pump flow) . Search for causes in this AND/OR space is analogous to a domain theory search, and is thus amenable to speedup. As a human-engineered artifact however, there are often inconsistencies in the fault tree. Thus, we plan to use the fault tree as an initial domain theory, but to use ExoR to organize experience and more efficiently guide diagnosis; logical inconsistencies may re­ main or they may be 'pruned' out, but in any case ex­ planation patterns that better reflect the system's true behavior will come to statistically dominate ExoR's rea­ soning. Thus, this approach to inconsistent domain the­ ories is similar in intent to systems like Towell, Shavlik, and Noordewier's [Towell et al., 1990] neural net/EBL system, albeit with very different approaches to the in­ ductive learning component .