Incorporating Redundant Learned Rules: A Preliminary Formal Analysis of EBL

1 Motivation

General problem solving (a.k.a. deduction) is expensive. There can be a combinatorial number of potential "so­ lution paths" for a given query/ goal - as there can be many rules/operations which each reduce the goal to a new set of subgoals, and each of these subgoals can, it­ self, have many possible reductions, etc. [Genesereth and Nilsson, 1987].

There are several approaches to this problem. One in­ volves ordering the set of rules, so the first rule selected for a given (sub )goal is the one viewed as most cost ef­ fective. For example, given the KBa knowledge base, whose rules appear in Figures 1 and 2, we may specify that the rule Rpm should be used before the rule Rpf when determining Abe's parent - i.e., when seeking an x such that Parent (Abe x) holds. There can, of course, be many comprehensive "derivation strategies" - i.e., many ways of searching this knowledge base, each guar­ anteed to find a solution, if one exists. Our objective is to find the one which requires the least expected time. (We describe this "expected time" cost below.)

Another approach involves adding redundant infor­ mation to the knowledge base, in the form of a "new" rule. Using KBa again, we observe that the solution to the Guardian(Abe Bart) query involved the fact Father(Abe Bart) and the rules Rgp and Rpj· This suggests modifying our derivation system for subsequent

*This research was supported by an Operating Grant from the National Science and Engineering Research Council of Canada.

Figure 1: Rule Base associated with KBa

queries: When asked to prove Guardian("' 'Y) (for any "' and -y), this "smarter" system will immediately per­ form the data base retrieval of Father("' 'Y), and only if this fails, consider the other possible retrievals and rule-based reductions (e.g., using Rgp, etc.). This corre­ sponds to combining the rules Rgp and Rpf to produce the new rule

R 9 r Father(p q) => Guardian(p q)

which is incorporated into the set of rules, forming KB'a +- I<Ba U {R91 }. Furthermore, this (redundant) rule is placed first, in that this system will try this new rule first in subsequent queries, before the other rules are attempted. This is the basis for the recent Explanation­ Based Learning (EBL) systems [Mitchell et al., 1986, DeJong and Mooney, 1986], as well as Chunking [Rosen­ bloom and Newell, 1982], etc.

The objective of these learning systems is efficiency: to improve the overall future performance of the sys­ tem. Of course, this requires some information about these anticipated future events - especially about which questions will be posed and with what probabilities, and about the probability that certain assertions will be in the knowledge base (I<B) when those queries occur.

Many systems implicitly employ the "obvious" as­ sumption that "the future will mirror the past" - that the future questions will correspond to the questions asked until now. This suggests preserving every observed rule-sequence as a new redundant rule. Recent empirical evidence [Minton, 1988], however, has exposed some of the problems inherent in this "save all redundant rules" approach: these new rules can slow down the overall per­ formance of the complete system. That is, it is not al­ ways advantageous to incorporate a proposed redundant rule into an existing knowledge base.

This paper addresses this important issue: how to de­ cide whether to add in a new redundant rule. It as­ sumes, as given, the a priori likelihood that any given database retrieval will succeed. (We may know, for ex­ ample, that there is a 10% chance that the data base retrieval "Father("' 1 )" will succeed, for any plausible pair of constants, <"-, 1>. 1 ) It shows how to use this likelihood information to determine both whether a new rule should be added; and if so, where in the derivation strategy that rule should appear.

The next section presents the framework for this anal­ ysis. Section 3 lists our results, including both the claim that the general problem is NP-hard, and descriptions of linear time algorithms which can solve the problem for some situations. Section 4 ties this work back to EBL systems.

2 Framework

This section first provides a quick description of deriva­ tion strategies and their expected costs, in general. It then focuses on the difficulties of incorporating redun­ dancies (read "EEL-generated rules"), within this frame­ work.

Derivation Strategies: Given a specific query, u, and collection of rules - like those shown in Figure 1 - we define a derivation strategy as an ordering which speci­ fies when to follow which rules (to reduce the subgoal) and when to perform data base lookups. For exam­ ple, one strategy for answering the query "Guardian(Abe Bart)" from KBa would be

• Lookup Guardian(Abe Bart) from (the set of facts in) KBa . If that succeeds, it returns "Yes" and is done. Otherwise:
• Use R 9 p to reduce this goal to Parent(Abe Bart).
• Lookup Parent (Abe Bart) from KBa. If that succeeds, it returns "Yes" and is done. Otherwise:
• Use Rpf to reduce this subgoal to Father(Abe Bart).
• Lookup Father(Abe Bart) from KBa. If that succeeds, it returns "Yes" and is done. Otherwise:
• Use Rpm to reduce the Parent(Abe Bart) subgoal to Mother(Abe Bart).
• Lookup Mother(Abe Bart) from KBa. If that succeeds, it returns "Yes"; otherwise, it returns "No". (Either way, it is now done.)

We write this strategy as 81 = (L 9 Rgp Lp Rpj Lj Rpm Lm}, where Rxy (now) represents the reduction using the Rxy rule, and the Ly steps refer to lookups of the y-related propositions. We will continue to refer to Rxy steps as "reductions", and to Ly steps as "lookups"; collectively, these are called "steps".

We can use this same strategy, mutatis mutandis, to address any query of the form "Guardian("' 1 )". While this approach holds for any arbitrary "' and 1, we will focus on the situation where each is some (unspeci­ fied) constant (as opposed to an existentially quantified variable 2 ) .

1 N.b., this report simply assumes that we have these probability values, and is not concerned with how they were obtained. [Likuski, 1988], as well as [Smith, 1989, Treitel, 1986], present various ways of estimating these val­ ues. E.g., one method involves examining the number of as­ sertions present in the knowledge base: as in "none are of the form Parent(···), 10% are Father(···)", etc. Of course, this also makes certain assumptions about the set of anticipated queries. There are ways of using other types of knowledge to find more accurate estimates.

The expected cost of a strategy is the (weighted) sum of the expected number of lookups plus the expected num­ ber of reductions. We assume that each lookup costs "d'' cost-units, and each reduction step, "i" cost-units. Of course, the cost of following a strategy depends critically on the successes of the lookups, which in turn depend on which facts appear in the knowledge base. If all of 0 1 's lookups fail, this overall strategy will require 3i + 4d steps. The expected cost is usually less: Assuming there is a 0% chance that Lp will succeed, (i .e., there are no facts of the form "Parent(K 1)" in KBa), and a 1%, 10% and 25% chance that L 9 , LJ and Lm, respectively, will succeed, 3 then the expected cost is

There can, of course, be many strategies for a given goal within a given KB. One could, for example, not bother trying to retrieve Parent ( · · ·) from KBa, and fol­ low the Rpm rule and its associated Mother(···) lookup before RpJ and Father(· ··). The expected cost of this alternative strategy, 82 = (L 9 Rgp Rpm Lm Rpj L 1}, is E(02) = d + (1- 0.01)[i + i + d + (1- 0.25)[i + d + (10.10)0]] = 2.7225i + 2.7325d, which is strictly less than E(01) for any values of i and d.

Nothing forces us to consider lookups before reduc­ tions. The 03 = (R 9 p Rpm Lm RpJ Lj L 9 } strategy, for example, does not bother to perform the (low proba­ bility) Guardian(· ··) lookup until the end. Its cost E(03 ) = 2.75i + 2.425d can be yet less expensive. If i = 1 and d = 2, then E(83) = 7.6 < 8.1685 = E(82), meaning this 0 3 is the best strategy yet.

This framework allows us to evaluate different strate­ gies. As we are only considering complete strategies - those which are guaranteed to find an answer, if there is one - all strategies are equally likely to succeed. As such, the best strategy will be one with the least ex­ pected cost.

The number of possible strategies is exponential in the number of allowed steps - even for the tiny K Ba knowledge base, there are over 7! = 5,040 possible strate­ gies, of which 42 are "depth-first" . 4 [Smith, 1989], how­ ever, shows how to compute the optimal derivation strat­ egy in a time (approximately) proportional to the num­ ber of rules, for any disjunctive, irredundant knowledge base. 5 Disjunctive means that all of the rules are of the form A=>C; Smith excludes rules of the form A&B=>C.

2 Here, we would seek one answer to a query, rather than all solutions. Hence, the question "Parent(Abe x)" would seek one parent of Abe, rather than all of his parents.

3 We assume that these probabilities are independent.

4 The next section defines this subset, and shows 'it must include an optimal strategy.

5 That algorithm involves sorting the set of m options at each goal - hence requiring an additional factor of 0( m log( m) ). In general, though, m ~ the number of rules.

He also disallows embedded function symbols and recur­ sive rules. 6 Irredundant means that there is at most one derivation path which connects any goal with any data base assertion. This means that the inference graph - the graph whose nodes are (sub )goals and whose arcs represent the rules which link a goal to its children; see Figure 2 - is a tree, rather than a more general directed acyclic graph ("dag").

Dealing with Redundant Knowledge Bases: Many I<Bs, especially those extended using EBL techniques, are redundant. This paper extends Smith's results to deal with such I<Bs- i.e., it describes how to find an optimal strategy for answering a given query from a re­ dundant knowledge base. The above mentioned I<B(; knowledge base is redundant because its inference graph (shown in Figure 3) includes two paths which join the query Guardian("' 1) to the lookup Father("' 1) - one using (Rgp Rpf}, and the other, (R 9 1} . We refer to the pair of nodes <Guardian ( · · ·), Father ( · · ·) > as a "A Y pair". We say, furthermore, that the "upward arcs" from the Y node (here, the Rpf and Rgf ascend­ ing from Father(···)) are redundant with one another, 7 and that Rgj is a direct (redundant) rule between Father and Guardian.

This paper deals only with disjunctive KBs, and as­ sumes that each of the arguments in the antecedent or the conclusion of any rule is a variable (rather than a constant). Hence, it considers rules like Father(p q)=>Guardian(p q), but not Father(Fred q)=>Guardian(q Mark) . 8

3 Finding the Optimal Strategy m a Redundant KB

As mentioned earlier, there are an exponential number of possible strategies for a given query from any knowledge base, and a fortiori, from a redundant knowledge base. This section describes how to find an optimal deriva­ tion strategy in such situations, in general, and shows a linear-time algorithm which applies in some particu­ lar situations. Subsection 3.1 first addresses the task of finding an optimal strategy for a single query, and states that even this task is NP-hard in general. Subsection 3.2 then discusses (read "presents negative results for") the more general case, when there is a (known) distribution of different queries. The next section ties this analysis back to EBL systems.

6 This restricted class does include much of the relevant information in standard hierarchies, making it an important case for AI systems.

7 We assume that our strategy-finding system knows which arcs are redundant. This is quite reasonable within the EBL context.

8 This minor restriction is for pedagogical reasons only; [Likuski, 1988] deals with the general case.

3.1 Optimal Strategies for a Single Query

Use Depth-First Strategy: At any time during the derivation process, there is a frontier of subgoals yet to "expand", by using one or more reduction or lookup steps. A strategy could, conceivably, expand goals "be­ low" the current frontier- e.g., consider (Rgp Lm ... ) . We need not consider such derivation strategies, as there will always be less expensive "depth-first deriva­ tion strategies", which only expand the subgoals on this frontier. In fact, [Likuski, 1988, Lemma 3.1] proves it is sufficient to consider only strategies which consist of only "reduction chains", where each reduction chain is a sequence of reduction steps, which each reduce the subgoal found immediately before, followed by a lookup of the final subgoal. (E.g., the sequence (Rgp Rpm Lm} is a reduction chain, as Rpm reduces the Parent ( · · ·) subgoal produced by the Rgp step; and Lm reduces the Mother(···) subgoal produced by this Rpm step. How­ ever, (Rgp Rpm Rpj Lm} is not, as Rpf does not reduce the Mother ( · · ·) produced by the prior step, Rpm .)

(The proof involves forming a depth-first strategy by "moving back" any step which interrupts a reduction chain in any non-depth-first strategy, and observing that the expected cost of the new depth-first strategy must be at least as good as the original one.)

Hence, we need only consider these "depth-first deriva­ tion strategies", and so can write any strategy, 0, as a sequence of reduction chains, (r1 r2 · · · rk} , where each r; is a reduction chain. For example, 03 can be written as ( (Rgp Rpm Lm}, (Rpf LJ}, (L9 } }.

Use Irredundant Derivation Strategy: A derivation strategy is redundant if it includes the same step more than once; e.g., 04 = (Rgj L1 Rgp Rpm Lm Rpf L1 L9 } is redundant as it includes Lj(i.e., asks for Fa the~··)) twice. It never makes sense to use a redundant derivation strategy to solve a specific query, as there is always an irredundant strategy which is function­ ally equivalent (i.e., will find an answer whenever the redundant strategy does) and which takes strictly less time [Likuski, 1988, Lemma 3.3]. Here, 0s = (R91 L1 Rgp Rpm Lm L9} is su~h a reduced, irredundant strategy for 0 4. (Notice 0 5 IS a subsequence of 04, which omits both the second L f lookup, and the no­ longer-useful Rpf reduction step.)

Use Irredundant Derivation Spaces: Let RS(0) map the strategy 0 into the set of rules it uses - e.g., RS(03 ) = { R 9 p, Rpm, RpJ }. Notice the _rule set of an irredundant strategy corresponds to an Irredun­ dant knowledge base, which means we can use [Smith, 1989]'s algorithm to find the optimal strategy i~ linear time. Hence, we can reduce the problem of findmg the "optimal derivation strategy" to the problem of finding the "optimal derivation space" (where each "derivation space" is the rule set plus the needed lookup steps).

Unfortunately, there can be an exponential number of derivation spaces. Consider, for example, the "trellis" inference graph, formed from the rules

shown in Figure 4. It has Fib(n) irredundant deriva­ tion spaces which connect the goal An+2(~~:) to the LA! lookup. ("Fib(m)" is mth Fibanocci number.)

Fortunately, there are often ways of selecting the op­ timal space:

Prefer Space containing a Direct Rule: Let 0 be the optimal derivation strategy associated with the top­ level goal u within the irredundant knowledge base, KB; and iet {R172 R23 · · · Rn>-. L>-.} be a reduction chain from this query to a lookup, L>-.. Now let Ru>-. be an ad­ ditional "direct rule" (not in the initial KB) wh_ic? im­ mediately connects this u with the .A lookup. (This IS the type of rule which most EBL processes would. ge~erate, after solving u. The R 91 rule is an example, as It duectly connects the Guardian(···) query with the Father(···) lookup.) Notice the set RS(0) - { Rn>-.} + { Ru>-.} is an irredundant derivation space; let 0' be the opti­ mal strategy for this space. [Likuski, 1988, Lemma_ 3.2] proves that E(0') :::; E(0), which means tha~ an opti~al derivation strategy (and therefore, the optimal denva­ tion space) will include the direct rule. (This is good news for EBL fans, as these direct rules are exactly what EBL systems generate!)

Hence there is an obvious linear time algorithm for finding ~n optimal derivation strategy, for the simp~e case of adding a new direct redundant rule to a (previ­ ously irredundant) knowledge base: Add the new direct rule and remove the arc with which it was redundant. The~ use [Smith, 1989] to produce the optimal strategy for this new KB.

A straightforward extension allows us to find, in lin­ ear time, the optimal strategy for the u query from any "u-direct-rule-KB" -that is, from any knowledge base which has the property that every 1 node under the goal u includes a direct link (i.e., single rule) joining it to the goal u. (As examples: KBa is a "Guardian-direct­ rule-KB", vacuously, as it includes no 1 nodes; KB'a qualifies, as its only 1 node, Father( 11: r), connects to Guardian; but KBsa (Figure 5) is not a "~-direct­ rule-KB", as it includes the 1 node, B(~~:), which does not connect to �(~~:) .) Here, an optimal strategy for u can be found in the derivation space which excludes all of the non-direct links from each 1 node to u. (The algorithm involves propagating up so-calle_d "wor~h va~­ ues" along these direct rules whenever pos~1ble. [Lik_u~ki, 1988, Theorem 5.1] proves that this reqmres exammmg each rule at most once.)

Task is NP-hard: Unfortunately, the general "OptDS" task - of finding the optimal search strategy in an arbi­ trary redundant search space - is NP-hard. The proof reduces this task to the NP-complete "Exact Covering" task [Garey and Johnson, 1979]; and appears in full in [Greiner, 1989].

3.2 Optimal Strategies for Multiple Queries

The previous subsection dealt only with ~ single _query; in general, we may have a range of quenes. This sub­ section assumes that we know which queries our system will be asked. 9 We would like to define a single general strategy which works for any anticipated query, within a forest of inference graphs.

This leads to a related, but distinct, perspective of this "worth of EBL" issue. This subsection provides four ob­ servations about these systems, which basically illustrate the additional complexity of this situation.

When Not To Add Direct Rules: When considering only one query, we argued above that we should always use the derivation space which includes the direct rules (whose conclusion matches that qu~ry). Unfortun~t.ely, this derivation space is less expressive than the ongmal one as we have to remove some rule to "make room" for '

9 In general, we may also know the frequency of these queries - e.g., that 3% of our queries will be of the form �uardian(~ -y) where ~ and -y will be bound in the quer?', and that 8% will be of the form Mother ( ~ x) where ~ IS bound and x is free, etc.

the new direct one - i.e., to reduce the extended KB to be irredundant . For example, we had to remove Rpf to accommodate Rgf, forming KB(; = KBa- {Rp,} + {Rgf }. Notice this KB(; is not "complete", in that it can no longer use facts like Father(Abe Bart) to answer questions like Parent (Abe Bart) .

If we know that such Parent (Abe Bart) queries will be asked (and that facts like Father(Abe Bart) will be in the KB), then we cannot afford to actually change KBa into KB(;. Instead, we assume there is a strategy associated with each query, which controls the derivation - here, Guardian( K 'Y) 's strategy will include R91 but not Rpf, while Father ( K 'Y) 's strategy will include Rp1. (This is easy to implement using a system like MRS [Russell, 1985].)

We might consider a heuristic of performing such KB­ modifications (e.g., augmenting KBa with Rgf) only if this addition leads to a real benefit - i.e., if the opti­ mal strategy with the new rule is strictly better than the original optimal strategy, for the given query. Unfortu­ nately, this approach can miss really good strategies.

Consider asking the queries Guardian(Abe Bart) and Guardian(Abe Cici) from the KBa knowledge base, which includes Father(Abe Bart) and Mother(Abe Cici). We begin with the strategy which is optimal for our values of i and d, 63 = {Rgp Rpm Lm RpJ Lf L 9 ).

After the first query, the EBL system would propose the direct rule Rgf, and suggest adding it to KBa. No­ tice the optimal Guardian strategy, in this derivation space, is 66 = {Rgp Rpm Lm R 9 1 LJ L 9 ), whose ex­ pected cost matches E(63 ). Hence, the above heuris­ tic would veto this rule, and tell us to keep the original KBa, and continue using the original 6 3 strategy.

After solving the second query, this EBL system would propose the rule

and suggest adding it to KBa. As the optimal strategy using this new rule- 61 = {Rgm Lm R 9 p Rpf LJ L 9 ) - is better than 63 (as E(61) = 2.5i + 2.425d < E(63 ) ), we would then add this Rgm to KBa.

Notice we are still missing the big win, which in­ volves both new direct rules. Here, the optimal strategy would be 6 8 = {Rgm Lm Rgf LJ L 9 ), with expected cost E(68 ) = l.75i+ 2.425d, which is much less than E(67) as it no longer even considers the Parent ( · · ·) sub goal!

Use a Fixed Ordering of Steps? Consider an in­ ference graph which has the goal G(K) leading down to the (inferior) subgoal S(K), and let 6s (resp., 6a) be the optimal strategy for S (resp., G). It would be conve­ nient if ea necessarily "includes" es - i.e., if each of es steps appear in ea, and they all appear in the same order as they occur in e s.

This would mean, in particular, that after finding the optimal strategy for the "root" of an inference "tree", one could re-use that ordering on every node in that tree. For example, we could then "subset" the opti­ mal strategy for the Guardian( K 'Y) query to form the optimal strategy for Parent ( K 'Y) queries: while that strategy would include only Rpf and Rpm and the relevant lookups (but not Rgp), it would include these steps in the same order here as they appeared within Guardian( K 'Y) 's strategy.

This would greatly simplify the task of finding the optimal derivation strategies for a set of queries from a given KB: one need only find the strategy for each root of the "inference forest". It would also mean that a PROLOG system could achieve optimal performance by simply asserting its rules and data base facts in this order.

Fortunately, this "fixed ordering" property holds for any irredundant knowledge base; see [Likuski, 1988, Lemma 4.5]. Unfortunately, it does not hold for redun­ dant knowledge bases; see [Likuski, 1988, Lemma 4.6].

Use a Fixed Set of Rules? The situation is really even worse: not only might we have to find a different ordering on the steps as we go from one goal to its "superior" goal, we might, in fact, have to use a completely different derivation space! That is, there can be steps within 6s which do not even appear anywhere within ea.

Figure 5 is an example. The optimal strategy for S(K) is 6s = (Rs1 R12 R2A LA R2B LB)· No­ tice, however, the optimal strategy for G(K) is ea = {RaA LA Ras Rs3 R3B LB), which does not include any of 6s's reduction steps!

When are Efficient Algorithms Possible? While the general OptDS problem is NP-hard, we presented efficient (in fact, linear time) algorithms which work in some specific situations. This final portion sug­ gests a way of characterizing which situations may be tractable. 10

This fixed-ordering property is essential to [Smith, 1989]'s algorithm for finding optimal strategies. That algorithm works in a "bottom-up" fashion: propagating so-called "worth values" up from lookups, via reduction steps. It works in linear time because the decision of which step to use, at a given subgoal, depends only on these steps and their "children". As this property also holds in the "direct-rule" case, we could use (a trivially modified version of) Smith's algorithm here as well.

10 We assume, of course, that P "I N P - i.e., that all NP-hard problems are intractable.

Unfortunately, the above points show that redundant inference graphs, in general, need not have this nice property. That is, an optimal strategy found for an inferior S(K) node may be completely irrelevant, when seeking the optimal strategy for its superior G(K) node, meaning our algorithm would have backtrack to consider other possibilities, as it works its way up towards the top goal. We feel that this back-tracking is what leads to the intractability of the general task, which is why we expect there are efficient algorithms for finding optimal strate­ gies only in situations where the decisions made at one node are "honored" at all superior nodes.

4 Conclusions

This concluding section first ties this work back into the framework of EBL systems in general, and then lists some obvious extensions to this work.

Tie to EBL Systems: The positive result mentioned above- that a direct redundant rule (i.e., the result of an EBL system) can never slow down a derivation system - should be viewed as only a partial vindication of EBL systems and techniques. Below are four comments about this claim:

• Most EBL systems leave in both the direct rule, and the rules from which it was derived- e.g., both the derived RgJ and the pair R 9 p and RpJ. We showed that this is never efficient, even for the query itself.
• Most EBL systems move this new rule to the begin­ ning of the system's derivation strategy; this is not always the optimal place. (Recall that we added R91 towards the back of the 0 6 strategy. In fact, the expected cost of the strategy which includes RgJ in the front of the strategy is strictly worse than the original, pre-R 9 1 strategy, 0a!)
• Section 1 mentioned two ways of improving the ex­ pected cost of a derivation- ( 1) by determining the best strategy, and (2) by adding redundancies. As empirical evidence has shown that using (2) with­ out ( 1) can produce arbitrarily inefficient systems, this report has examined ways of combining both of these.
• This result applies only when the prior knowledge base is irredundant, and it only deals with a single query. As shown above, the situation is much more complicated when we consider multiple questions, and arbitrarily redundant knowledge bases.

Extensions: We have only scratched the surface of this analysis; there are many other areas to consider as well. The first obvious arena is handling conjunctive and re­ cursive knowledge bases. Another is to combine this ap­ proach with other control strategy mechanisms - in­ cluding conjunct ordering [Smith and Genesereth, 1985] and forward chaining [Treitel and Genesereth, 1987]. The third is to obtain more accurate empirical values. For example, we have assumed that the costs of reduc­ tions and lookups (read "i" and "d") are uniform. Pre­ liminary empirical observations show that these costs de­ pend on the number of variables, etc.

Results: This report takes seriously the view that Explanation-Based Learning is a method for improving the future performance of a reasoning system. This leads to the formal foundation for analysis presented in Sec­ tion 2, which is based on the expected cost for solv­ ing certain queries from a given knowledge base (based on a given distribution of facts). Section 3 uses this framework to describe both the complexities (read "NP­ hardness") inherent in this undertaking; and certain re­ stricted situations where efficient algorithms (based on [Smith, 1989]'s work) are possible. Section 4 uses this framework to understand why EBL systems do, and do not, succeed in their attempts to improve the perfor­ mance of their underlying systems.