The Effect of Rule Use on the Utility of Explanation-Based Learning

1. Introduction

The utility problem in explanation-based learning concerns the ability of learned mles or plans to actually improve the performance of a problem solving system [Minton87]. The concern that too much learned information might eventually degrade problem solving performance was initially expressed in the work on learning macro-operators in STRIPS [Fikes72]. Since then, several studies have found that the unrestricted learning and use of rules or macro-operators can degrade rather than improve overall performance [Markovitch88, Minton85, Minton88a]. This decrease in performance is due to time wasted trying to apply learned rules or macro-operators in situations in which they are incapable of efficiently solving the problem at hand. However, other experiments have revealed only overall performance improvement from explanation-based learning even though no attempt was made to limit the number or form of learned rules [0'Rorke87, Shavlik88].

· This research was supported by the Department of Comput­ er Sciences and University Research Institute of the University of Texas at Austin.

This paper presents experimental results and informal analysis that may help explain this apparent contradiction in the existing empirical data. The proposed explanation relies on the fact that how learned rules are actually used in prob­ lem solving can greatly affect their tendency to improve or degrade overall performance. This focus on the use of acquired knowledge differs from previous attempts at addressing the utility problem, which have focused on for­ getting or selectively retaining learned knowledge or on translating it into a more efficient form [Markovitch88, Minton85, Minton88b].

The paper is organized as follows. Section 2 describes the performance system under investigation, a Hom-clause theorem prover that learns macro-rules (com­ positions of existing rules). Section 3 presents the basic experimental methodology used to examine the effect of learning on performance and describes the problem sets used in the experiments. Section 4 compares two approaches to using learned rules. It shows that unrestricted use of macro-rules can degrade overall performance; how­ ever, limiting chaining on learned rules can help alleviate the negative impact of learning and lead to overall perfor­ mance improvement. Section 5 shows how different search techniques such as depth-first and breadth-first can greatly affect the impact of learning on performance by changing how learned rules are used. Section 6 concludes and presents some problems for future research.

2. The Performance System

Unfortunately, comparing different explanation-based learning systems is difficult because they generally employ different underlying performance elements and knowledge representation schemes. However, a performance element that has been used in a number of systems is a backward­ chaining, depth-first, Hom-clause theorem prover (like Pro­ log) [Hirsh87, Kedar-Cabelli87, Mooney88, Prieditis87], a general, well-understood, and popular performance system in AI.

The system used in the current experiments is a ver­ sion of EGGS [Mooney86, Mooney88] that includes a Hom-clause theorem prover as a performance component. When EGGS finds a proof for a query by chaining together several existing rules, the proof is generalized using stan­ dard explanation-based techniques [DeJong86, Mitchell86] and compiled into a macro-rule. In the system's list of available rules for each predicate, learned rules are placed before the original rules in the domain theory so that using learned rules is preferred to solving a problem from scratch. However, new rules are placed at the end of the set of learned rules so that rules learned from problems encoun­ tered earlier in system's experience are tried first (since they probably represent more typical problems). This approach has been empirically found to work better than adding new rules to the beginning of the list of learned rules [Shavlik88].

The Hom clauses initially given to EGGS as a domain theory are simply assumed to be a set of declarative facts rather than a well-ordered Prolog program which is guaranteed to terminate (as in PROLEARN [Prieditis87] and PROLOG-EBG [Kedar-Cabelli87]). In order to prevent depth-first search from getting lost (possibly in an infinite recursion), the theorem prover is given a depth bound that limits the number of rules it is allowed to chain together. Another feature of the system is the ability to heuristically order the antecedents of learned rules in an attempt to make them more efficient. Antecedents that have a greater per­ centage of variables that are likely to be already bound (by occurring in the consequent or a previous antecedent) are positioned earlier in the list.

3. Experimental Methodology

The effect of learning on performance is empirically examined by having both learning and non-learning systems solve a sequence of problems in a particular domain and comparing their performance. The learning system learns rules from its solutions which are available for solving sub­ sequent problems in the sequence. Since search is limited by a depth-bound, not all problems will necessarily be solved. Consequently, performance is compared by measuring both the number of problems solved and the total effort expended on the complete problem set (in terms of both CPU time and search nodes generated). Time spent on the generalization and learning process itself is generally minimal (less than 0.1% of the overall time) and is not reported. This simple methodology seems cleaner and fairer than a complicated methodology involving stages in which learning is turned on and off on different selected sets of problems (e.g. [Minton88a]). All experiments were run on a Texas Instruments Explorer II with 12 MB of main memory.

Two problem domains are used to test EGGS and compare its performance with learning to its performance without learning. One problem domain is proving theorems in propositional logic. The problem set used in this domain consists of 52 problems from Principia Mathematica [Whitehead13] that were first used in experiments with the Logic Theorist (LT) [Newell63]. Experiments on this prob­ lem set with an explanation-based learning version of L T (EBL-L T) [O'Rorke87] showed overall performance improvement due to learning even though no attempt was made to limit the number of learned rules. For use in EGGS, all implies in the theorems were rewritten in terms of not (--,) and or rv )) and the system was given the follow­ ing domain theory for constructing proofs.

1. Theorem(-,(x Y x) Y x)
2. Theorem(-,x Y (yYx))
3. Theorem(-.(x Yy) Y (yY x))
4. Theorem(-,(x Y (y Y z)) Y (y Y (x Y z)))
5. Theorem(-,(-.x Yy) Y (-.(z Yx) Y (z Yy)))
6. Theorem(-,yYx) A Theorem(y) ~ Theorem(x)
7. Theorem(-, x Yy) A Theorem(-,yYz) ~ Theorem( -,x Y z)

The other problem domain used to test the system is blocks-world planning. Standard blocks-world problems can be solved with a Hom-clause theorem prover by stating them as theorems in situation calculus. The blocks-world theory used for the current experiments is a simplified ver­ sion of the rules used to test the BAGGER system [Shavlik88]. Since blocks-world problems are quite difficult to solve using a theorem prover and axioms in situation calculus, the problem sets are restricted to building stacks of one to three blocks given a randomly generated scene with five blocks. The procedure described in [Shavlik88] is used to randomly generate problems and ini­ tial states. Complete problem sets are produced by ran­ domly generating a sequence of 30 stacking problems.

Although a Hom-clause theorem prover is a weak problem solver and can perform quite poorly in certain domains (e.g. planning domains), this does not affect its sui­ tability as a performance element for a learning system. The goal of learning is to improve performance and a weak problem solver simply has more room for improvement. The important factor is not absolute performance but the relative performance of learning and non-learning systems.

4. Full Versus Limited Use of Learned Rules

One approach to using learned rules is to treat them exactly like rules in the original domain theory. As a result, learned rules can be combined arbitrarily with domain rules and with other learned rules. This approach may seem promising since it allows for the greatest possible use of learned information. Unfortunately, it can quickly lead to a great deal of effort being spent trying to use a learned rule before eventually giving up and trying another path in the search tree. Minton has referred to the fact that, in the gen­ eral case, matching the antecedents of a learned rule to a set of facts is NP-Complete [Minton88b]. Using arbitrary theorem proving to prove them is, of course, even worse (i.e. undecidable).

Consider the following case in which unrestricted use of learned rules is applied to blocks-world problems. First, given the situation shown in Figure la, the system is asked to build a three block tower on Table-2. It solves the prob­ lem (transfer(A,Table-2), transfer(B,A), transfer(C,B)) and learns a rule for building a tower of three blocks on a table by inverting an existing tower of three blocks on another table. Next, it is given the same goal with the initial state shown in Figure lb. Since the goal matches the consequent of the rule that was just learned, the system backward­ chains on this rule and tries to achieve its antecedents. This requires constructing a tower of three blocks that can then be inverted. The system will waste a great deal of effort trying to achieve this subgoal before eventually finding it is impossible and attempting to solve the problem from scratch. The result is a significant decrease in performance due to learning. Since the antecedents of a learned rule fre­ quently involve more constraints than the original goal, using arbitrary problem solving to achieve them is generally much more trouble than it is worth.

In logic theorem proving, since learned rules are sim­ ply generalized theorems (facts) rather than rules with antecedents, one might suspect that such problems do not arise. However, matching a subgoal to a learned fact may require that variables in the subgoal be bound to particular formulae. These bindings may cause problems in subse­ quent subgoals and cause the system to backtrack on the decision to use the learned fact (after possibly having wasted a lot of time trying to use it). For example, imagine the system has learned the fact: Theorem(-,x V (x V y)). Given the problem Theorem(P V ....,P), the system might use rule 6 above to generate the subgoals: Theorem(-,x V (P V ....,P)) and Theorem(x). If the first subgoal is matched to the learned theorem, then the second subgoal becomes: Theorem(P). The system may waste a great deal of time trying to prove this impossible subgoal which was generated due to the attempt to use the learned fact. Consequently, even the use of learned facts that do not have any antecedents may cause considerable wasted effort.

In order to prevent the possibility of spending too much time trying to use learned rules, limiting the use of what is learned is perhaps a better alternative. An extreme approach is to only allow a learned rule to be used if it com­ pletely solves the problem at hand without being combined with other rules. In other words, the problem solver is not allowed to backchain on the antecedents of learned rules nor is it allowed to use a learned rule (or fact) to solve a subgoal, since both of these actions may result in a great deal of wasted effort if the learned information is not actu­ ally relevant. This is a very strict schema-based or script­ based approach; a learned plan either solves a problem com­ pletely or it is simply not used.

Table 1 presents empirical data (CPU time and search nodes generated) on various versions of the EGGS system proving 52 logic theorems from the Principia with depth bounds of 3 and 4. The conditions shown are: no learning, learning with unrestricted use of learned facts (Full-use), and learning with no chaining with learned facts (Limited­ use). Full-use learning takes more time than the non­ learning version; however, it solves more problems. This is an ambiguous result with respect to the effectiveness of this method. Some clear advantage of full-use learning is shown by the fact that the full-use version with a depth-bound of three expends less than a tenth of the effort of the non­ learning version with a depth-bound of four and yet solves three more problems. However, the results are hard to inter­ pret since both search effort and correctness vary. On the other hand, limited-use learning is incapable of solving more problems than no-learn since, unlike full-use learning, it does not use learned rules to search even deeper into the search tree defined by the original domain theory. How­ ever, learned rules can be used to more quickly handle prob­ lems solvable by the original theory within the depth bound. The data in Table 1 shows that limited-use learning does increase speed relative to no learning without changing correctness and that its relative advantage increases with the size of the search space (i.e. the depth bound).

Correctness can be completely controlled by using only the problems that can be solved by the original domain theory within the given depth-bound. In this case, only the time to solve the problems varies and can be used as the basis of a fair comparison. Table 2 presents data in which correctness has been controlled in this manner. These results clearly show the negative effects of full-use learning and the advantage of limited-use learning. For a depth bound of three, full-use is 1.1 times as slow as no-learn while limited-use is 1.4 times as fast. For a depth bound of four, full-use is 2.4 times as slow as no-learn while limited­ use is 2.0 times as fast. The fact that the speedup actually increases with the size of the search space for limited-use while it decreases for full-use underlines the conclusion that limited-use learning is best.

An issue that has been raised regarding the L T prob­ lems is that, as a sequence of problems from the Principia, they are explicitly ordered so that later problems build on earlier ones [Minton88b]. In order to address this issue and present a more detailed picture of the performance of the various methods, Figure 2 shows cumulative time curves for random orderings of the problems. Cumulative time is the the total time spent solving all problems up to that point. The curves are for the 48 problems solvable by all versions with a depth bound of four. Each curve is the average of five random orderings of the problems. Not surprisingly, the full-use learning system performs even poorer on ran­ domly ordered problem sets. For the full set, full-use takes on average 4.9 times as long as no-learn while limited-use takes 0.46 as long. One would not expect problem ordering to have an effect on limited-use learning since if the rule learned from problem A is capable of completely solving problem B, then the same rule can be learned from problem B and applied to problem A if the order of the two problems is reversed.

Figure 3 shows cumulative time curves for the blocks-world domain. These curves are the average of five randomly generated sets of 30 stacking problems. All prob­ lems can theoretically be solved within the depth-bound of 7 supplied to all systems. However, due to time constraints, the full-use learning version was stopped after it had spent about 15 hours on a problem set. In this time, it never got past the third or fourth problem in the set. Backward chain­ ing on the antecedents of a learned rule consistently caused the system to get lost in a huge search space. In order to increase the applicability of learned rules in the limited-use case, a minimal amount of chaining is allowed with learned rules. Specifically, a few efficient rules for concluding vari­ ous static properties of blocks can be used to prove the antecedents of learned rules. Unlike the abysmal perfor­ mance of full-use learning, on average the limited-use ver­ sion solves all 30 problems in one third the time of the no learning version. 1

Therefore, avoiding or severely limiting chaining with learned rules is clearly preferable to the unrestricted use of learned rules. The explanation-based learning experiments on blocks-worlds problems presented in [Shavlik88] also allowed only very limited chaining on learned rules. The current experiments indicate that the limited use of learned rules was crucial to the overall beneficial effects of learning obtained in these experiments.

5. The Effect of Search Methods

Although the previous section presents data that unrestricted acquisition and use of learned rules degrades performance on the Principia problems, experiments with EBL-L T on this .problem set showed only positive effects of learning [O'Rorke87]. Limiting the use of learned rules in the manner discussed in the previous section does not explain this apparent contradiction since EBL-LT treated learned theorems just like the initial axioms in the domain theory.

1 The average number of search nodes explored to solve all 30 problems is 1,184,512 for no-learn and 426,556 for limited-use learning.

There are a number of differences between EBL-LT and EGGS that could account for the inconsistent results. For example, unlike EGGS, EBL-LT is only capable of con­ structing linear proof trees and it is allowed to learn from unproven theorems. However, a difference between the two systems that greatly affects the use of learned rules is the fact that EBL-LT uses breadth-first search while EGGS (like Prolog) uses depth-first. When a learned rule is tried with a depth-first theorem prover, the system exhaustively tries to prove its antecedents and may waste a great deal of time if they cannot be proven. A breadth-first prover, on the other hand, pursues all paths "in parallel" and does not spend an inordinate amount of time first trying to exhaust the use of learned rules before eventually resorting to the initial domain theory (like depth-first does). Like the approach described in the previous section, breadth-first search limits the use of learned rules compared to depth-first search.

A breadth-first Hom-clause theorem prover is used to test the hypothesis that switching from depth-first to breadth-first search can change the effect of learning on per­ formance. Table 3 presents data on the performance of a breadth-first prover given the L T domain theory and prob­ lem set used in the previous experiments. In order to limit run-time, each system is only allowed to generate a certain number of search nodes for each problem. If this limit is exceeded, the system gives up and goes on to the next prob­ lem. Results are presented for limits of 1000, 3000, and 5000 nodes per problem. Unlike the results reported for depth-first search, the learning system shows significant improvement in performance compared to the non-learning version. The learning system solves about twice as many problems in 1/2 to 1/3 the time and its relative performance improves as the search space gets larger. Comparing the data in Tables 1 and 3 shows that breadth-first search with learning can solve more problems with less search than depth-first with limited-use learning. However, breadth-first takes more time per search node because of the extra memory operations required. It is also important to notice that without learning, the performance of breadth-first search in terms of both run-time and search is significantly worse than depth-first since it requires more memory and cannot take advantage of rule-ordering. The overall poor performance of breadth-first search on problems requiring relatively deep proofs prevented the possibility of running it on blocks-world problems.

6. Conclusions and Future Research

The data and informal analysis presented in this paper demonstrate that the use of learned information can have a large impact on the utility of explanation-based learning. Previous research on the utility problem has focused on the amount or form of learned information rather than on its use in problem solving. Unconstrained use of learned rules can clearly lead to degraded performance. However, appropri­ ately limiting the use of learned information can help avoid the negative effects of learning and help insure overall per­ formance improvement. Various properties of the perfor­ mance element can have a significant impact on how learned information is used and consequently on the effect of learning on performance. For example, allowing chain­ ing on learned rules in a depth-first system leads to degraded performance while allowing chaining on learned rules in a breadth-first system does not. Therefore, it is unwise to generalize utility results on one performance sys­ tem to different performance systems.

One important area for future research is finding a workable compromise between the extremes of full use and no-chaining on learned rules. A good compromise will allow greater use of learned knowledge while avoiding the problems with unrestricted use. Allowing a limited amount of chaining with learned rules (as in the experiments with the blocks-world) is one promising approach. In domains like logic theorem proving where learned information takes the form of facts or theorems instead of rules with antecedents, methods are needed for being able to effec­ tively use these facts as lemmas. Sometimes a subgoal can be satisfied by a learned theorem without the risk of creating other difficult subgoals. A problem only arises if matching the subgoal to a learned theorem creates bindings for vari­ ables in the subgoal that may not satisfy the remaining antecedents (see section 4). Therefore, a good approach may be to allow a subgoal to be proven by matching a learned fact only if the match does not bind any variables occurring in the subgoal. This would allow the use of lem­ mas without the risk of having to eventually backtrack on this decision. Initial experiments with this approach on the L T problems have given promising results.

As shown by the above experiments, both depth-first and breadth-first search strategies have advantages and disadvantages with respect to being a successful search stra­ tegy for a system which learns macros. Depth-first iterative-deepening [Korf85] exhibits some of the advan­ tages of both depth-first and breadth-first and may be a good strategy for a learning system. Some additional specific issues which need further study are the effect of the