Explanation-based Generalization in a Logic-Programming Environment

I Introduction

Mitchell, Keller, and Kedar-Cabelli (1986) present a unifying framework for an explanation-based approach to generalization. Its underlying idea is to form an explana­ tion structure (such as a plan or a proof tree) for a spe­ cific situation, and generalize the explanation structure so that it applies to a wider range of situations. Ezplanation­ ba1ed generalization (EBG) uses a logical representation for knowledge, and an inferential view of problem solving. DeJong and Mooney (1986) suggest a more general term ezplanation-ba1ed learning (EBL), to also cover syst~ that may specialize knowledge using information from an explanation structure. They take a problem-space view of problem-solving, in which generalization is a method of acquiring schemata for problem solving.

·mscusaiona with Paul Roeenbloom, Devika Subramanian, Ray Mooney, Smadar Kedar-Cabelli, Stuart Russell , Rich Keller , Allen Van Gelder, and Michael Genesereth had a significant impact on this work. Comments by Paul Rosenbloom, Marianne Winslett, Stuart Russell, and Jane Hsu on earlier drafts of this paper were invaluable. MRS has been developed ~y the Logic Group at Stanford University; the EBG program was wr1tten on top of the existing MRS architec­ ture, and incorporates modified veraiona of Jeff Finger's RESIDUE method (Finger and Genesereth 1985). Computing resources were funded in part under NIH grant RR-00785 from the Division of Re­ search Resources Biomedical Research Technology Program. The ar­ rangement of facilities at lSI by Norm Sondheimer and Bob Neches for work on this paper is greatly appreciated.

II Framework

The logical framework of Mitchell, Keller, and Kedar­ Cabelli was taken as the appropriate starting point for this work. EBG takes knowledge (rules and facts) about a goal concept, an instance of the concept, and operationality of ~r~dic~tes. Given a specific instance of a concept (the trammg mltam:e), and knowledge about that concept (the domain theory), the task for EBG is to find a definition of the concept expressible in terms of operational predicates. It does this by using the domain theory to prove that the instance is an example of the goal concept, generalizing the proof to find an operational description of a larger class of instances that are verifiable examples of the goal.

III Example

This framework for EBG is illustrated using the Safe­ To-Stack example from Mitchell, Keller, and Kedar-Cabelli (1986). Given the following facts about two objects, Obj1 and Obj2, that satisfy Safe-To-Stack(Obj1,0bj2),

Dn(Dbj1,Dbj2) Isa(Obj1,Box) Isa(Dbj2,Endtable) Color(Obj1,Red) Color(Dbj2,Blue) Volume(Obj1,1) Density(Dbj1,0.1),

and rules about the safety of stacking one object on an­ other (with appropriate procedural attachment for "x" and"<"),*

Not(Fragile(y))-+Safe-To-Stack(x,y) Lighter(x,y)-+Safe-To-Stack(x,y) Volume(p1,v1)ADensity(p1,d1)Ax(v1,d1,w1) -+Weight (p1, w1) Isa(p1,Endtable)-+ieight (p1, 6) [Default Rule] ieight(p1,w1)Aieight(p2,w2)A<(w1,w2) -+Lighter(p1,p2), and facts about the operationality of predicates Dperational(Volume(p,v)) Dperational(Density(p,d)) Operational(Dn(x,y)) Operational(Color(p,c)) Dperational(Isa(x,o)) Operational(x(x,y,z)) Operational ( < (x, y)),

the EBG system should verify that the training instance is indeed a correct example of Safe-To-Stack, and general­ ize its verification to form a rule specifying a larger set of cases that are Safe-To-Stack:

Volume(v2,v37)ADensity(v2,v38) Ax (v37, v38, v33) Aisa(v3 ,Endtable) A< (v33, 6) -+Safe-To-Stack(v2,v3).

EBG constructs a proof that the example satisfies the goal, as in Figure 1. This proof is generalized, result­ ing in the generalized explanation structure for Safe-To­ Stack(v2,v3) shown in Figure 2. The conjunction of the operational predicates (Volume, Density, x, Isa, and <) in the generalized proof form a condition on the general­ ized goal predicate. Mooney and Bennett (1986) provides more detail on three other versions of EBG. Further detail on the implementation of EBG for this work follows.

*Throughout this paper variables begin with lower-case letters and are assumed to be universally quantified. All relations, including<, are written in prefix form, and n-ary functions are written as n+l-ary relations, with the result as the additional n+lst argument .

IV Interleaved Explanation and Generalization

As just described, the task of EBG is to prove that an instance is an example of a concept, and generalize the proof to form an operational description of the con­ cept. These two stages, ezplanation and generalization, are typically done sequentially: after creating a proof, a generalization step forms the operational description from the proof. This work takes a different approach-the two stages are done simultaneously. The system attempts to prove that the instance is an example of the concept (such as Safe-To-Stack(Obj1,Dbj2) above) by backward chain­ ing on the goal through rules until training-instance facts are reached. However, each time a rule is used, it is simul­ taneously applied backward to the variablized goal concept (such as Safe-To-Stack(v2, v3) ), creating the generalized explanation structure in parallel with the instantiated ex­ planation structure.

EBG is started on a specific goal, such as Safe-To­ Stack(Dbj1,Dbj2). The first step is to find all rules that could potentially conclude this fact, namely all those whose consequent unifies with the goal concept. They are

Not(Fragile(y))-+Safe-To-Stack(x,y) and Lighter(x,y)-+Safe-To-Stack(x,y).

The first is tried {since it occurs earlier in the database), and generates the subtask lfot(Fragile(Obj2)) by unifying the consequent of the rule with Safe­ To-Stack(Obj1,0bj2) and applying the binding list thus formed to the antecedent of the rule. The antecedent be­ comes the new subtask. The generalized subtask Not (Fragile ( v2)) is generated in the same way, by unify­ ing the consequent of the rule with the generalized form of the original task, Safe-To-Stack(v2,v3)*, and applying the resulting bindings to the antecedent of the rule, re­ sulting in a new generalized subtask. Thus the generalized explanation structure is formed 'in parallel to the formation of the instantiated explanation structure.

Not (Fragile (Obj 2)) fails (for lack ofapplicable rules), so the system backtracks to the earlier goal Safe-To­ Stack(Obj1,0bj2), and its generalization, Safe-To­ Stack(v2,v3). The second rule is now tried, resulting in Lighter(Obj1,0bj2) and Lighter(v2,v3). The back­ ward-chaining process continues, at each step unifying both the current task and its generalization with the conse­ quents of rules and applying the resulting bindings to the antecedents to obtain new subtasks. Failure to prove a subtask causes backtracking to an earlier subtask for a dif­ ferent rule selection or variable binding. Backtracking also occurs if a subtask is proved, but yet the subtask's gen­ eralization is not operational, since EBG must generate an operational definition of the concept. Note that back­ tracking removes all record of failed attempts to prove the task, and thus erroneous proof paths Will affect neither the explanation structures, nor EBG's final learned rule.

·The generalized form of the first goal (Sah-To-Staelt(v2,v3) here) is created by simply taking the non-unified consequent of the rule used to backward chain from the instantiated initial goal.

The above description of backward-chaining on gener­ alized goals while creating the proof has one exception. If a generalized subtask is ever operational, but the instan­ tiated subtask requires further proof, the system merely continues normal proof of the subtask alone. This causes EBG to find more general operational definitions than it might otherwise form. The current generalized sub task be­ comes a terminal node in the developing generalized expla­ nation structure, without inclusion of any of the subtasks that occur below it. For example, if Weight is operational (i.e., Operational(Weight (p1, w1)) is· in the database for Safe-To-Stack), the resulting generalized explanation structure will be that of Figure 3.

The final step of EBG is to form the conjunction of terminal nodes of the generalized explanation structure, and create a rule with this conjunction as the antecedent and the top goal of the generalized explanation structure as its consequent. All bindings formed during creation of the generalized explanation structure are applied to this rule, to handle interacting subgoals correctly. The result­ ing rule is the final result of EBG. Thus

would be the rule learned for the preceding example in which Weight is operational.

DeJong and Mooney (1986) point out that there is of­ ten more than one way to prove that an example is indeed an instance of a concept, and each such differing proof can result in a different rule from EBG. Thus, for example, if the training-instance data for Obj2 included knowledge for concluding Not(Fragile(Obj2)), there would be two ways to prove Safe-To-Stack(Obj1,0bj2), and thus two rules could be created by EBG, depending on which proof was chosen. As discussed in Section VII, such selection is deterministically specified by the order of rules in the domain theory-whichever knowledge came first, fragility or weight, would succeed in creating a proof. However, logic programming systems often provide a means for find­ ing multiple results due to alternative inferential paths. In MRS, if the plural form of an inference method is se­ lected, MRS finds all conclusions that can be found with the specified inference method. Since EBG has been imple­ mented as an additional form of inference for MRS, EBGS was also implemented, to allow creation of all rules that can be formed from all possible proofs of the training in­ stance. Furthermore, meta-level knowledge can be used to specify which rule to select at any point, thus determin­ ing which explanation EBG will form, and hence what the final learned rule will be.

v Operationality

Operationality criteria are one of the inputs that Mitchell, Keller, and Kedar-Cabelli specify for their EBG, but the only operational definition they give for it is "The concept definition must be expressed in terms of the predi­ cates used to describe examples ... or other selected, easily evaluated, predicates from the domain theory." It is only a small extension to allow specification of any set of pred­ icates, such as including Weight in the example above. However, DeJong and Mooney (1986) and Mooney and Bennett (1986) point out that such simple selection of op­ erational predicates is insufficient, and provide examples in which operationality is a function of the proof struc­ ture. In one such example they define operationality to be predicates at terminal nodes of the generalized expla­ nation structure after all predicates that only support !sa facts are removed. This dynamic operationality cannot be supported in EBG as described by Mitchell, Keller, and Kedar-Cabelli.

Another example of dynamic operationality not in­ cluded in Mitchell, Keller, and Kedar-Cabelli (1986), nor in DeJong and Mooney (1986) or Mooney and Bennett (1986), is applying a theorem-prover to decide operational­ ity dynamically. Since explanation is interleaved with gen­ eralization, it becomes easy to prove operationality while the actual goal is being proved. For.example, an axioma­ tization of Keller's (1987) definition of operationality could be used to determine operationality dynamically, with pred­ icate definitions changing over time as problem solving oc­ curs. The axiomatization could even perform experimenta­ tion or look-ahead search to determine whether a specific predicate is operational. Finally, since operationality is now a problem-solving task, EBG can be applied to it as well, resulting in better operationality criteria, suited to the particular task at hand.

Deliberate reasoning about operationality allows the user to specify rules about operationality rather than rigidly listing a set of operational predicates. Such application of logic programming allows operationality to be defined in terms of proof progress, rather than of the final explanation structure. Thus operationality can change while doing ex­ planation. For example, if the logic-programming system provides caching of intermediate results, a rule such as "If a predicate succeeds n times, make it operational" (for some n) could be used to specify operationality.

The motivation for making operationality a provable property is the notion of meta-level reasoning in MRS. In MRS, proof strategies can be specified in a meta-level the­ ory. Thus, for example, a meta-level rule can specify to try one branch of a proof over another if it uses an arithmetic predicate. The vocabulary already exists within MRS to specify such properties, and hence it becomes easy to spec­ ify operationality rules such as

irithmetic-Predieate(pred(argl,····argn)) -+Dperational(pred(argl , .·. ,argn)).*

As another example, the rule specifying "If only one po­ tential path is possible at this point, make the current subtask operational" would use the same meta-level pred­ icates used by meta-level proof strategies in MRS. This notion of operationality is more robust than operational­ ity as specified by Mitchell, Keller, and Kedar-Cabelli.

This also highlights the difference between the EBG described here and that of DeJong and Mooney (1986) and Mooney and Bennett (1986). In their problem-space framework, they simultaneously generate both the in­ stance's explanation structure and the generalized expla­ nation structure. However, during creation of the general­ ized explanation structure they do not reason about opera­ tionality; only later, during the subsequent generalization stage, do they determine operationality and modify the explanation structure. ·· The generalization stage prunes the generalized explanation structure using operationality, and then uses the resulting abridged structure to form the rule. Thus, although much of the work of generalization is accomplished during explanation, they still separate ex­ planation and generalization.

One difficulty with ignoring operationality during ex­ planation generation is that situations can arise in which an explanation is generated from which no operational con­ cept definition can be created, yet other explanations exist from which operational definitions can be formed. Since in this work operationality is determined during the explana­ tion process, such situations do not occur. As soon as a branch terminates without an operational definition, back­ tracking will occur to try to find an alternate proof for the branch from which an operational concept definition can be generated. It is impossible to generate a complete ex­ planation structure without simultaneously ending with a generalized explanation structure that has an operational definition of the goal concept.

*This uses the ability to quantify over predicates in MRS.

**The generalized explanation structure is actually represented as an overgeneral explanation structure, with a binding list to suffi­ ciently specialize the structure. Since operationality may change the binding list as well, it must also be modified during generalization.

VI Search Control

Mitchell, Keller, and Kedar-Cabelli include an exam­ ple of learning search control for integration operators. Their domain theory includes the following rules:·

Useful(op,x)~Not(Solved(x))ASolvable(op(x)) Solvable (x) ~ 3op[Solved(op(x))VSolvable(op(x))] Matches(x, "f<any-fn>dx")-.Not (Solved(x)) Matches(x, "<any-fn> ")-.Solved(x) Matches(op(x),y)~Matches(x,Regress(y,op))

where Regreu in the last rule propagates y through op. The goal concept is u .. ful(Op3,x)-to learn search con­ trol for Op3. However, the actual definition for Op3 is never given. The hidden definition of Regreu is the source of all resulting knowledge of Op3.

A footnote of Mitchell, Keller, and Kedar-Cabelli {1986) remarks: "Notice that the regression here involves propagating constraints on problem states through prob­ lem solving operators. This is a difFerent regression step from the second step [generalization] of the EBG process, in which the goal concept is regressed through the domain theory rules used in the explanation structure." They are saying that for this task the Regress predicate is necessary in addition to EBG's own regression, since it is a differ­ ent form of regression. The correct distinction, however, is not that they are difFerent regressions, but rather that they are regressing through difFerent knowledge represen­ tations. Rosenbloom and Laird {1986) point out that "the EBG implementation of search-control acquisition requires the addition of general interpretive rules to enable search with the task operators and the regression of the solution property through them, while Soar makes use of the same goal/problem-space/chunking approach as is used for the rest of the processing." Basically, they are saying that Soar has only one way to represent knowledge, and thus only has one form of regression possible. Likewise here, the strict enforcement of a logical representation forces repre­ sentation of all knowledge, including operators, as rules in logic, with only a single form of regression.

Thus the distinction is not that Soar uses problem spaces, but rather that Soar consistently uses a single rep­ resentation. Mapping this back to EBG, using a single rep­ resentation scheme to represent all information uniformly allows use of a single form of regression. Here this means representing all information about operators, such as Op3, explicitly as rules in logic. A domain theory for integration satisfying this uniform representation constraint* is

·Their domain theory has been modified a bit here for greater clarity.

lpply(op,problem,nevproblem) ASolvable(nevproblem) -.Useful(op,problem) Integrate(problem,ansver)-.Solvable(problem) lny-Fn(problem)-.Integrate(problem,problem) 3op[lpply(op,problem,nevproblem) Aintegrate(nevproblem,ansver)] -.Integrate(problem,ansver) lny-Fn(f1)Alny-Fn(f2)Aintegrate(Jf2,ansver) -.Integrate(x(f1,Jf2),x(f1,ansver)) Real(k)AUnprovable(·(k, -1) >A+(k,1,m) m -.lpply(Op9,Jxk,xm) lny-Fn(f)AReal(r) -.lpply(Op3,fx (r,f), x (r,Jf) ).

This database does two things. In addition to making the definitions of operators {such as Op3 and Op9) explicit, it also makes the notion of state explicit. Rather than hav­ ing functional application of operators within predicates {such as Solvable), Apply is used as a separate conjunct to create explicitly the state to which predicates will be applied.

Given that Op3 is useful for J7x 2 dx (i.e., Useful(Op3,J x (7 ,x2)) ), as well as proper definitions for lny-Fn, operationality, etc., the rule learned by EBG, sim­ plified by removing duplicate conjuncts, is

lny-Fn(xY49 )AReal(v33)Alny-Fn(v33) AReal(v49)AUnprovable(=(v49,-1)) v48 A+(v49 ,1, v48) Alny-Fn( ~) -.Useful(Op3,J x (v33,xv49) ). This is equivalent·· to the simpler rule Real(v33)AReal(v49)AUnprovable(=(v49,-1)) -.Useful(Op3,J x (v33,xv49) ),

which is similar to the rule of Mitchell, Keller, and Kedar­ Cabell {1986). ··· Note that the matching predicates of Mitchell, Keller, and Kedar-Cabelli {1986), Matches(x,y), are done implicitly with unification, and that regression through operators is done by the same mechanism as re­ gression through rules {since the operators are rules).

0 The domain theory has been simplified somewhat for presentation.

·· All other conjuncts of the original antecedent will be true if the antecedent of this simpler rule is true. Prieditis and Mostow (1987) discuss how to use partial evaluation to generate such simplifications automatically.

···The difference, as in Rosenbloom and Laird (1986), is in the rep­ resentation of integration problems and the applicability of operators to them. The difference is not significant.

VII Imperfect Domain Theories

Mitchell, Keller, and Kedar-Cabelli point out the re­ liance EBG has on the user-provided domain theory and identify the issue of imperfect domain theories as a topic for future work. They recognize three sources of imper­ fection in a domain theory: incompleteness, intractability, and inconsistency. Rosenbloom and Laird (1986) discuss two further sources, incorrectness and defeasibility of do­ main theories. The precision of a logical view of EBG greatly clarifies these issues, and suggests solutions to some of these issues.

As recognized by Mitchell, Keller, and Kedar-Cabelli, and Rosenbloom and Laird, the existence of a default rule to compute the weight of an endtable in the Safe-To-Stack example causes difficulties for application of EBG. Use of this default rule makes EBG learn an overgeneral rule, since the learned rule has hidden the fact that it was only relevant when the second object's weight was otherwise unprovable. The learned rule will thus allow concluding Safe-To-Stack for endtables that are not Safe-To-Stack using the original domain theory. This form of inconsis­ tency raised by Mitchell, Keller, and Kedar-Cabelli is the same as the defeasibility issue raised by Rosenbloom and Laird. · In logic they become the issue of nonmonotonicity.

A theory is monotonic if adding new facts will never invalidate a previously proved fact. H new facts can inval­ idate previous results, the theory is nonmonotonic. Until now domain theories have been viewed as theories in a for­ mal sense. However, when given to a theorem prover, the needs of efficiency outweigh the needs of theory, and extra­ logical notions such as rule order and default rules must be added. These added computation devices cause monotonic theories to become nonmonotonic.

The Safe-To-Stack example has such nonmonotonic­ ity. The order of rules in a database specifies what order the rules will be used in attempting a proof. By ordering the rules in the correct way, a rule can be made to serve as a default, to be used if other means of proof (tried earlier since they occurred earlier in the database) fail. Thus, for example, the endtable weight rule was placed after the vol­ ume times density weight rule to cause the endtable rule to serve as a default rule.

The cause of these difficulties is the fact that some rules conflict-that more than one rule can be used at the same time for some instances, and that different conclu­ sions can be reached using these different rules. In such cases conflict re$olution is necessary to decide which rule to select. The example of rule order above is one simple example of a conflict resolution strategy. The difficulty for EBG is that this extra information is not an explicit part of the domain theory, and is thus hidden from the EBG process, which therefore cannot incorporate this informa­ tion into the learned rule. EBG is only as correct as the information given to it. Since knowledge of the default sta­ tus of the endtable weight rule is kept hidden from EBG, it has no way to learn a correct rule.*

· A theory is defeasible if the addit ion of knowledge can change results.

This view of the problem suggests a solution. H the difficulty is that information is hidden, the solution is to make this information explicit. There are two ways to do this. The first is to incorporate conflict resolution decisions into the explanation structure, so that EBG can form rules from all information used in verifying the instance. The do­ main theory would in effect contains all rules and facts for conflict resolution, and conflict resolution decisions will be incorporated into the explanation structure. Thus the ex­ planation structure would include failing branches, which may be used in one of two ways. EBG could learn a rule with an added conjunct saying that Weight ( v3, v39) is not provable using the volume-times-density Weight rule. It might alternatively learn a rule with an added conjunct corresponding to the specific reason for the failing branch in the explanation, Unprovable(Volume(v3)).

As discussed below, such addition of conflict reso­ lution decisions into the explanation structure will often cause EBG to create over-specialized rules. Furthermore, conflict-resolution strategies such as rule order are often difficult to encode explicitly for use in the explanation structure. In these cases a second choice, reformulating the domain theory, becomes appropriate. The goal of such reformulation should be to remove all need for conflict · res­ olution, namely, to eliminate overlap in conflicting rules. This can be done using predicates about provability. For example; the following reformulated domain theory for the Safe-To-Stack example makes the nonmonotonicity of the default rule explicit:

Not(Fragile(y))-+Safe-To-Stack(x,y) Lighter(x,y)-+Safe-To-Stack(x,y) Volume(pi, vi) 1\Density(pi,di)/\ X (vi, di, vi) -+Weighti (pi, vi) Isa(pi,Endtable)/\Unprovable(Weighti(pi,w)) -+Weight(pi,5) Weighti(pi,w)-+Weight(pi,w) Weight (pi, w1) /\Weight (p2, w2)/\< (wi, w2) -+Lighter(pi,p2).

(Note that the volume-times-density weight rule now con­ cludes the new predicate Weighti rather than Weight.) Given a database with these rules, EBG will learn the cor­ rect rule:

· Lewis (1987) has discussed a similar concept of the safety of production-system learning mechanisms. When priority schemes are used to order productions, the result of composing two productions may be inconsistent with respect to the original production system.

Volume(v2,v48)~Density(v2,v49)

~X (v48, v49, v42)~Isa(v3,Endtable) ~Unprovable(Weight1(v3,v61))~<(v42,6) ~safe-To-Stack(v2,v3).

Failure to compute the endtable weight has become ex­ plicit in the Unprovable(Weight1(v3,v61)) conjunct of the new rule.

Finally, note that conflict resolution schemes can be used to serve two different purposes. In the Safe-To-Stack example there are two cases of rule conflict. The first is the two different ways to conclude Safe-To-Stack(x,y): Unprovable (Fragile (y)) and Lighter (x, y). In this case rule order has no impact on the correctness of the results of EBG; rule order will only influence the speed with which the system reaches conclusions. On the other hand, the rule order of the two Weight rules embodies domain knowl­ edge: the second rule is a default rule, and it is only correct to try it if the first rule fails. It is only this second use of conflict resolution, when it embodies domain knowledge, that can cause EBG to overgeneralize. Thus only some conflicting rules need be reformulated to remove the con­ flict. Likewise, only some conflict resolution decisions need be included in the explanation structure. Although in both cases EBG learns correct rules when all conflicting rules are addressed, the learned rules will often be over-specialized. ·

VIII Conclusion

This paper has described an implementation of explanation-based generalization (EBG) within a logic­ programming environment, in which generalization is done · in parallel with explanation generation. All aspects of EBG are viewed in logic, which clarifies issues of EBG. Operationality becomes a provable property requiring ex­ plicit reasoning. Additionally, logical representation of do­ main operators unifies regression of constraints through operators with regression of goals through domain rules. Finally, overgeneralization by EBG is better understood when viewed from a logic standpoint. Making those in­ consistencies in a domain theory that are due to nonmono­ tonicity explicit, either by incorporating conflict resolution decisions into the explanation structure, or by making rules mutually exclusive, removes the cause of overgeneralization for EBG.

*Soar (Laird, Rosenbloom, and Newell 1987) has solved this by providing two forms of preference6 (Soar's version of conflict resolu­ tion) . Necessity preferences (Laird, Rosenbloom, and Newell 1986) are used to specify those preferences that embody knowledge of the goal test. The backtracing mechanism used in Soar ignores all pref­ erences except necessity preferences, which are incorporated into the learned chunks.