A Formalization of Explanation-Based Macro-operator Learning

1 Introduction

Explanation-Based Learning (EBL) treats learning as improving the efficiency of a problem solver [Dejong and Mooney, 1986, Mitchell et al., 1986]. The standard EBL systems start with complete and correct, if inefficient, problem solvers. Learning involves taking a set of exam­ ples, i.e., problem-solution pairs, as input and produc­ ing an efficient problem solver as output. The examples provide information about the problem distribution and eliminate the need to search for solutions.

While there are satisfactory formal models of empir­ ical learning based on variants of Probably Approxi­ mately Correct (PAC) learning [Valiant, 1984, Haus­ sler, 1990], EBL systems are not theoretically well­ understood. There are some practical problems in EBL which can be directly attributed to the lack of adequate theoretical understanding. Firstly, there is no clear defi­ nition of "success" for EBL systems. Because of this reason there hasn't been a rational method to decide when to stop learning. Any satisfactory formalization of EBL should specify what it means to succeed and should pro­ vide an effective method to recognize success. Secondly, it is known that EBL systems do not always lead to per­ formance improvement with learning. After learning a large number of rules, they might face what is called the "utility problem," i.e., the problem of complexity of using the learned knowledge [Minton, 1990]. Since the utility problem can far outweigh the reduction in search due to learning, a successful formalization should take this into account and characterize the sufficient condi­ tions for a guaranteed performance improvement.

This paper introduces a variation of the formal frame­ work for performance improvement learning of [N atara­ jan and Tadepalli, 1988]. We call this framework Proba­ bly Approximately Correct (PAC) Problem Solving. Us­ ing this framework, we analyze two forms of macro­ operator learning, namely, Macro Caching and Serial Parsing. One of the main results of this paper is an explication of the biases exhibited by these two forms of EBL. In particular, Macro Caching and Serial Parsing implement two distinct biases: (a) the sparse solution space bias and (b) the macro table bias. The sparse so­ lution space bias says that most problems in the domain can be solved by a small number of operator sequences. The macro table bias says that the solution to a prob­ lem can be constructed by serially composing a set of macro-operators that solve a series of subproblems. We show that when a domain and the hypothesis space of the learning system satisfy these biases, it leads to an exponential speedup in problem solving. Somewhat sur­ prisingly, the analysis also reveals that it is not necessary to compute the preconditions of macro-operators in or­ der to obtain this speedup. The theoretical predictions of our analysis are confirmed by an implementation of Serial Parsing in the domain of Eight Puzzle.

The main contribution of this paper is a successful integration of EBL work with PAC learning. It also extends Korf's work on macro-operator learning [Korf, 1985] to incremental learning by observation. Our work also suggests that the utility problem in EBL can be solved by building learning programs that implement bi­ ases which exploit the domain structure.

The rest of the paper is organized as follows: Section 2 introduces PAC Problem Solving. Sections 3 and 4

describe Macro Caching and Serial Parsing, respectively. Section 5 presents experimental results in the Eight Puz­ zle domain. Section 6 discusses the related work, and the final section summarizes the contributions.

2 Probably Approximately Correct Problem Solving

In order to formally analyze EBL, we need to precisely define what it means for EBL, or any other speedup learning method, to succeed. The problem definition in [Mitchell et al., 1986] is not sufficient for our pur­ poses, because it does not address the issue of learning from multiple examples. This section presents a defi­ nition which draws from the earlier formal frameworks presented in [Natarajan and Tadepalli, 1988].

The key difference between purely empirical learning and EBL is that an EBL system is also provided with a "domain theory," which, we assume, is in the form of a set of goals and operators. However, this domain theory is too inefficient to use directly to solve problems. The operationality constraint of EBL [Mitchell et al., 1986] may be viewed as defining a hypothesis space of poten­ tial efficient problem solvers, one of which is the target problem solver. In this paper, we view the problem of performance improvement as learning an efficient, ap­ proximate problem solver from the domain theory and the example solutions of some target problem solver in the hypothesis space.

Define a problem domain D to be the tuple (S, G, 0}, where

• S = A set of states.
• G = A set of goals, where each goal is described by a procedure that recognizes a set of states in S.
• 0 = A set of operators {o1 , 02, . . . }, where each o; is a total function 1 from S to S.

The combination of goals G and the operators 0 is called the specification of D .. Let us denote the result of applying an operator o on a states by o(s).

A problem is a pair (s, g}, where s E Sis a state and g E G, a goal. A problem {s, g) is solvable if there is a sequence of operators f3 = (o1 , ... , od), and a sequence of states (so, ... , sd), such that (a) s = so,(b) for all i from 1 to d, s; = o;(s;_l), and (c) sd satisfies the goal g.

In the above case, f3 is a solution sequence of (s, g), and dis the length of the solution sequence {3. The maximum of lengths of description of all s;, i E 0 ... d is called the step length of the solution sequence.

Notice that our domain specification is not as "ex­ plicit" as typical EBL programs require them to be. The operators need not be described in the STRIPS formal­ ism, and goals need not be logical formulae. In fact, they need not be declaratively represented at all, but may be described by procedures whose run time is reasonably bounded. Thus, our learning frameworf< requires the learning techniques to be more independent of the oper­ ator representation than the standard EBL techniques.

1 This can be extended to partial functions by assuming that any operator, when applied to a state in which it is not applicable, will lead to a "dead state."

This allows choosing the operator representation which is best suited to the domain rather than being constrained by the needs of the learning technique.

Secondly, unlike the standard EBL approaches, our goals and operators are not parameterized. At first glance, this appears to seriously limit the power of EBL. Somewhat surprisingly, this is not the case. This is be­ cause, for most domains, the maximum number of pos­ sible instantiations of any parameterized operator (or macro-operator) must be bounded by a polynomial fac­ tor so that the cost of instantiating it is not exorbi­ tant . This means that every parameterized operator (or macro-operator) can be replaced with at most a poly­ nomial (in the length of the state description) num­ ber of non-parameterized operators. To take a domain like chess as an example, every parameterized opera­ tor (e.g., move pawn) can be replaced with n x n non­ parameterized operators (e.g., move pawn from e2 to e4), where n is the length of the state description, i.e., the number of squares on the chess board. Since, as our later definitions show, our formalization ignores all poly­ nomial factors in sample size, learning time, and prob­ lem solving time, our results do not change whether the operators are parameterized or not. A parameterized model was considered and similar results were proved in [Tadepalli, 1990]. For simplicity of exposition, this paper considers only non-parameterized operators.

A problem solver f for D is a deterministic program that takes as input a problem, (s, g), and computes its solution sequence, if such exists.

A hypothesis space H is a set of problem solvers.

An example for a domain D is a pair ( (s, g), /3), where f3 is a solution sequence of (s, g).

A meta-domain M is any set of domains.

A learning algorithm for M is an algorithm that takes as input the specification of any domain D E M and some number of examples of problem solving with a tar­ get problem solver in H and computes as output an ap­ proximation for a problem solver for D.

The learning protocol is as follows: First, the do­ main specification is given to the learner. The teacher then selects a problem distribution from a set of al­ lowed distributions and a target problem solver from the hypothesis space. The learning algorithm has ac­ cess to a routine called SOLVED-PROBLEM. At each call, SOLVED-PROBLEM randomly chooses a problem in the input domain, solves it using the target problem solver, and returns the example (the (problem solution) pair). The learning algorithm must output an approxi­ mate problem solver with a high probability after seeing a reasonable number of examples. The problem solver need only be approximately correct in the sense that it may fail to produce correct solutions with a small prob­ ability.

Definition 1 Formally, an algorithm A is a learning algorithm for a meta-domain M in a hypothesis space H with respect to a set of problem distributions r' if for any domain D E M, any choice of a problem distribution P in r, and any target problem solver f E H,

1. A takes as input the specification of a domain D E

• M, an error parameter f. , and a confidence param­ eter 6,
• A may call SOLVED-PROBLEM, which returns ex­ amples (x , f(x)) forD, where x is chosen with prob­ ability P(x) from S x G. The number of oracle calls of A and its running time must be polynomial in the ~aximum problem size n, ~, t, and the length of its znput.
• For all D E M and distributions P E r, with prob­ ability at least (1 - 6) A outputs a program f' that approximates f 1 in the sense that ExeAP(x) ~ f., where .6. = { x If fails on x while f succeeds}.
• 4- There is a polynomial R such that, for a maxi­ mum problem size n , ~ ~ t, maximum length I and maxtmum step length r of any solution output by SOLVED-PROBLEM, and an upper bound t on the running times of programs in D on inputs of size n, if A outfuls f', the run time off' is bounded by R(n, /, r, t, <· 6 ).

This framework is very similar to that introduced in [Natarajan and Tadepalli, 1988]. The main difference is the idea of the hypothesis space which is not present in [Natarajan and Tadepalli, 1988]. Another difference is that it uses a less powerful SOLVED-PROBLEM oracle than the USEFUL oracle of [Natarajan and Tadepalli, 1988] which is capable of generating optimal solutions for any problem. We also insist that SOLVED-PROBLEM must solve all problems using the same target problem solver chosen from the hypothesis space.

The first two conditions in Definition 1 require that the learning algorithm must terminate and output the prob­ lem solver within reasonable computational time limits. The third condition requires that with probability at least. 1- 6, the learning algorithm should output an ap­ proximate problem solver for the domain. The problem solver is approximate in the sense that it is allowed to fail to find a solution with a probability less than f. while the target problem solver succeeds when tested on problems chosen according to the same distribution that was used in training. Note that the problem solver might find any correct solution and not necessarily the same solution that the target problem solver would have found. This is one reason why this framework is not subsumed by that of PAC learning of functions described in (Natara­ jan, 1989] . The final condition is to ensure that the problem solver output by the learning algorithm scales reasonably well .

We call this framework Probably Approximately Cor­ rect (PAC) Problem Solving.

3 Macro Caching

In this section we describe Macro Caching and charac­ terize the sufficient conditions for it to be a learning al­ gorithm for a meta-domain.

We define a macro-operator (or a macro) to be any se­ quence of operators. Macro Caching consists of verifying that an operator sequence solves the problem by execut­ ing_ it (the "explanation" step of EBL) and storing the ~ntue operator sequence from the start to the goal state m the example as a single macro. Unlike the standard

Input domain specification DE M , error parameter f., confidence parameter 6 Test-counter:= 0 i := 1 While Test-counter~ H2In( i + 1) + In t} do Let SOLVED-PROBLEM() return (problem (s, g), solution (3) If (s, g) is solvable by the current problem solver Then Increment the Test-counter by 1. Else Begin End While; Reset the Test-counter to 0. Update the problem solver by learning from ( ( s, g) , (3) i := i + 1 End; Output current problem solver;

implementations of EBL, our algorithms do not rely on precondition computation. Thus, a macro may only be viewed as a potential solution sequence, which must be tested at the problem solving time. The problem solver works by applying each macro to the current state and testing whether it succeeds. If some macro succeeds in achieving the goal, it returns the macro; otherwise it fails.

The idea is to pick enough examples so that after ex­ tracting the macros from these examples, one is reason­ ably certain that the learned problem solver is probably approximately correct. One difficulty remains, however. The number of examples necessary for successful learn­ ing depends on the the number of necessary macros, and we do not a priori know this number. Hence, a differ­ ent approach called "stochastic testing," used in [An­ gluin, 1988], is adapted to our problem. The idea is to stochastically determine whether learning is complete by testing the program on randomly selected examples. In this "on-line" model , the program is tested as it is be­ ing trained, and the learning is terminated as soon as it succeeds on enough number of consecutive random ex­ amples. The testing scheme, described in Table 1 has a slightly better bound on the number of test exa~ples than that of [Angluin, 1988].

Definition 2 A problem solver f for a domain D and a problem distribution P satisfies a sparse solution space bias if there is a set of operator sequences m 1 such that, on any pr~blem x E D such that P(x) > 0, f(x) E m1 , a~d lmJ I ts bounded by a polynomial Q in the problem szze n.

Intuitively, the sparse solution space bias implies that there is a small number of operator sequences out of which solutions can be selected, so that the simple strat­ egy of remembering all of them and trying them one by one would work well . The small number of op­ erator sequences might be due to (a) the small number of problems that have a non-zero probability in the given problem-distribution (sparseness of problem dis­ tribution) or (b) the large number of states that satisfy the goal (high density of goal states), or a combination of both. To give an example of the second case, if a goal in the blocks world is to achieve a state in which there is a clear block on the table, it can be achieved by one of three macros: a null macro, a macro which puts the block being held in hand on table, and another macro which picks up a block on the top of a tower and places it on the table. This works for an exponential number of (in fact, all) initial states because an exponential number of states also satisfy the goal.

Theorem 3 If H is defined by the set of problem solvers that satisfy the sparse solution space bias for all domains D in M and all distributions p in r I then stochastic testing with M aero Caching is a learning algorithm for M in H with respect to r.

Proof(sketch): Notice that, at any stage i, the learner has to succeed on ~(21n( i + 1) + In!) randomly chosen test problems for the learner to terminate. At any stage i, the probability that the learner succeeds on all its tests when its macros are not, in fact, adequate to solve a randomly chosen problem with a probability greater than 1-ds less than (1-€)tC2ln(i+1)+Int), which turns out to be less than (;: 1 )~. So, if the program terminates at some stage j, the probability that we have a problem solver whose probability offailure is greater than € is less than or equal to L:i=1 u:1p < J/=o u:1p di < 6.

By the sparse solution space bias, the number of macros necessary to solve the domain is bounded by a polynomial Q(n, t). Since the lack of each such macro can cause at most one failure in our algorithm, the number of failures i satisfies i ~ Q(n, t). Hence, the total number of iterations of the while loop, and the total number of examples needed is bounded by Q(~,t) (21n( Q( n, t) + 1) +In!), which is a polynomial. It can be seen that the program runs in polynomial time.·

Macro Caching's main limitation is due to its assump­ tion that a small number of macros can solve most prob­ lems in the problem-space. For example, it does not work in domains like Rubik's Cube and Eight Puzzle, where each macro can solve at most one problem, and the problem distribution is not sparse.

4 Serial Parsing

This section describes how EBL can succeed for arbitrary problem distributions by exploiting a problem-space structure called serial decomposability [Korf, 1985].

Here we make the assumption that states are representable as vectors of discrete valued features, (v1, ... , vn}, where the maximum number of values a fea­ ture can take is bounded by a polynomial in n.

In Rubik's Cube, the variables are cubie names, and their values are cubie positions. In Eight Puzzle, the variables are tiles, and their values are tile positions. Note that the above assumption makes it difficult to rep­ resent domains with relations, e.g., the blocks world.

A domain is serially decomposable for a given total or­ dering on the set of features if the effect of any operator in the domain on a feature value is a function of the val­ ues of only that feature and all the features that precede it [Korf, 1985].

Rubik's Cube is serially decomposable for any ordering offeatures (also called "totally decomposable"). In Eight Puzzle, the effect of an operator on any tile depends only on the positions of that tile and the blank in the original state. Hence Eight Puzzle is serially decomposable for any ordering that orders the blank as the first feature.

Note that serial decomposability is a property of the domain as well as its representation. If Eight Puzzle is represented with positions as variables and tiles as their values, then it is not serially decomposable.

We assume that there is a single, fixed goal state de­ scribed by (gb ... , Yn}. 2

Korf defines a macro table as a set of macros Mj,i such that if Mj,i is used in a solvable state s where the features 1 thru i - 1 have their goal values, Y1, ... , Yi-1 and the feature i has a value j, then the resulting state is guaranteed to have goal values Y1, ... , g; for features 1 thru i.

Korf showed that if a domain is serially decomposable and every state reachable from a solvable state is also solvable, then it has a macro table [Korf, 1985] . If a domain is serially decomposable for the feature ordering (1, . . . , n}, then any move sequence that takes a state (g1, . . . , Yi-1 1 j, s;+l, ... } to (g1, ... , g;, t;+l, ... ) can be used as a macro Mj ,; , since the values of features 1 thru i in the goal state only depend on their values in the initial state, and not on the values of other features.

If a full macro table with appropriately ordered fea­ tures is given, then it can be used to construct solutions from any initial state without any backtracking search [Korf, 1985].

Definition 4 A problem solver f satisfies a macro table bias for a domain D in M if there is a feature ordering 0 = (1, . .. , n} such that, (a) D is serially decompos­ able for 0, and (b) f constructs all its solutions using a macro table M as follows: for each feature i from 1 to n, macros M;,; are successively applied, where j is the value of feature i in the state before applying the macro.

Since each application of macro Mj,i guarantees that the features 1 thru i will have their goal values, any solvable problem is solved in n macro applications by such problem solver. Korf's learning program builds a macro table by exhaustively searching for a correct en­ try for each cell in the table [Korf, 1985] . Thus, Korf's work might be characterized as "learning by doing." Our method, called Serial Parsing, extends his work to incre­ mental learning of macro tables by observation.

Instead of Macro Caching, the stochastic testing algo­ rithm now calls Serial Parsing to extract the macros in a solution sequence. For a goal (g1 , ... ,gn}, Serial Pars­ ing proceeds from the beginning, varying i from 1 thru n, applying the operators in the solution to the cur­ rent state ("explanation" step of EBL), and collecting each operator subsequence that occurs between a state

2 This can be generalized with parameterization.

Input problem ~s 0 ,g), where s = (s~, ... ,s~}, and g = (g1, ... ,gn}, and solution f3 = (o1, ... , od} For each k, let sk := ok(Ok-1( ... (o1(s 0 )) ... )) Operator index k := 0 Current feature i := 1 Current value (of feature i) j := s~ macro :="" Do until k > d or i > n If(st, ... ,sf} = (g1 , ... ,g;} Then Begin Let Mj,i :=macro i := i + 1 j := s~ macro:='"' End Begin; Else Begin End Do; k := k + 1; macro := macro.ok End Begin; Output macro table M

(g1, ... ,g;-1,j, ... ), and (g1, .. . ,gi-1,g;, .. . }, and storing it as the macro Mj,i· If the domain is serially decompos­ able for the feature ordering 1 ... n, this is guaranteed to yield correct macros. Note that the structure of the macro table eliminates the need to compute the precon­ ditions for macros.

For example, in Eight Puzzle, let r, 1, u, and d repre­ sent the primitive operators of moving a tile right, left, up, and down respectively. Macros are represented as strings made up of these letters. For notational ease, features (tiles) are labeled from 0 to 8, 0 standing for the blank and i for tile i. A macro Mj,i represents the sequence of moves needed to get the ith tile to the goal position from its current position j, while preserving the positions of all previous tiles including the blank. The positions are numbered by the tile numbers in the goal state, which is assumed to be fixed. The goal state and an example start state along with a solution are shown in Figure 1.

C?iven the problem and the solution in Figure 1, Senal Parser breaks down the solution as "dr - rdlu - druuldrdlu- uldrurdllurd- urdl" and extracts the macros: Ms o = "dr"; M2 1 = "rdlu" · M1 2 = "druuldrdlu" · 'M - '"' · M' - "" · M' :._ , 3,3 - , 4,4 - , 7,5 - "uldrurdllurd"; and M1, 6 = "urdl". From many ex­ amples the system constructs a table of macros. The problem solver works as described in Definition 4. It fails if the macro table is missing some necessary macro at any point.

The result of this section can now be stated and proved. Unlike Theorem 3, the next theorem is distribution-independent.

Theorem 5 If (a) H is the set of all problem solvers defined by the macro table bias for domains in M, Solution: drrdludruuldrdluuldrurdllurdurdl

Figure 1: A training example in Eight Puzzle

(b) the number of distinct feature values in D is bounded by a polynomial function of maximum problem size, and (c) the feature ordering of the target problem solver is input to the learner,

then stochastic testing with Serial Parsing is a learning algorithm for M in H.

Proof (sketch): We already saw that, if at some stage i, stochastic testing terminates, then, with a probability at least 1 - 6, it outputs a problem solver which has a probability of success of at least 1 - L We will now see that the number of examples and the running time of the algorithms are polynomially bounded.

Conditions (a) and (b) imply the existence of a macro table, whose size (number of macros in the table) is bounded by a polynomial in the problem-size. Condi­ tions (a) and (c) guarantee that the Serial Parser would learn at least one missing macro from the example when­ ever the macro-based problem solver fails to solve a prob­ lem. Hence, by arguments similar to those of Theorem 3, the examples are bounded by l.!lli(2ln(IMI+1)+ln t), which is a polynomial. It also f~llows that the learner runs in polynomial time. Since the macro-based problem solver never needs to backtrack, it runs in time polyno­ mial in all the relevant parameters.·

The above theorem shows that Serial Parsing exploits serial decomposability, a problem-space structure which allows it to compress the potentially exponential number of solutions into ~ polynomial size macro table.

The macro table bias requires that the teacher's solu­ tions (provided by the SOLVED-PROBLEM) are com­ posed from a macro table. This assumption is needed in the proof because Serial Parser can only learn a macro if the solution contains that macro. This assumption may not be true in general because, every problem might have several solutions, some of which may not be obtained by composing macros from a macro table. In fact, this as­ sumption is most likely violated if the teacher gives only optimal solutions, because finding optimal solutions for the N x N generalization of Eighf Puzzle is intractable [Ratner and Warmuth, 1986]. Hence the macros learned from optimal solutions do not fit into macro tables. How­ ever, if the learner is allowed to ask queries, i.e., ask the teacher to solve carefully designed problems, it is possi­ ble to learn macro tables in polynomial time irrespective of how the teacher solves the problems by designing a problem for each cell in the macro table and storing the solution as a macro.

5 Experimental Results

Serial Parsing was implemented in the Eight Puzzle do­ main. The program SP (Serial Parser) was trained by randomly selecting a solvable problem (with uniform dis­ tribution), constructing a solution using a macro table, and giving them to the learner. SP was trained with stochastic testing for several values of f and 8. After each training session, it was also tested on 100 indepen­ dent random test examples to estimate the error rate. The results are shown in Table 3. Each row represents the averages after training the system 10 times with the same values off and 8.

The first column shows f which is set to be the same as 6. The second column shows the total number of examples used until after the last macro was learned. The third column shows the number of examples used for stochastic testing after the last macro was learned. The fourth column shows the total number of examples used. The fifth column shows the total number of macros learned. The sixth column shows the error rate after learning was complete, averaged over 100 independent test problems. The final column shows the CPU msecs for solving a single problem after learning was complete, averaged over 100 problems. · (The measurements were taken on a sun SPARCstation 1 with 8MB of real mem­ ory.)

The full macro table contains 35 macros. In most cases all 35 macros were learned even when f and 8 were set to high values. The number of examples increased with decreasing f and 8, as can be expected. The most im­ portant thing to notice is that the system was able to learn the full macro table with approximately 30 train­ ing examples. With Macro Caching , 9!/2 macros and many more examples would have been required for per­ fect learning!

It is clear from tpe last column that our program did not suffer from the utility problem. The CPU time was fairly constant with decreasing f and 8. After learning was complete, SP was able to solve any randomly cho­ sen solvable problem in less than 8 msecs of CPU time. The two main reasons for the speed of SP are : (a) the macro-based problem solving is linear in the length of the solution, and (b) the operators and goals are repre­ sented efficiently and avoid the overhead of the logical representations.

6 Discussion and Related Work

Recently, there have been a few formal frameworks pro­ posed to capture performance improvement learning. For example, [Cohen, 1989] analyzes a "Solution Path Caching" mechanism and shows that organizing the so­ lution sequences of the examples in a tree and restricting the search of the problem solver to this tree improves the performance of the problem solver with a high probabil­ ity. Solution Path Caching is similar to Macro Caching in that they both can be shown to be polynomial-time learning algorithms for domains defined by sparse solu­ tion space bias. By defining learning as producing a polynomial-time problem solver as opposed to simply running faster than the original problem solver, we have more stringent conditions on successful learning in our framework. Hence, Solution Path Caching (like Macro Caching but unlike Serial Parsing) fails to learn (by our definition) in domains like Eight Puzzle.

Greiner and Likuski formalize EBL as adding redun­ dant learned rules to a horn-clause knowledge base to hasten query-processing [Greiner and Likuski , 1989]. This model is extended to recursive domain theories in [Subramanian and Feldman, 1990]. They conclude that learning macro-rules in EBLin such domains is not prof­ itable in general unless strong assumptions are made about the problem distribution. While our result on Macro Caching is consistent with their conclusion, we also show that the structure of the problem-space can be exploited to make learning profitable in other domains.

Serial decomposability is just one example of a problem-space structure. [Etzioni, 1990] describes an­ other kind of problem-space structure called "non­ recursive explanations" which explains the successful performance of PRODIGY in a number of domains. When this structure is present, the size of the explana­ tion of a control heuristic is independent of the solution length. Somewhat surprisingly, Etzioni also found that examples were not the key reason for PRODIGY's suc­ cessful performance [Etzioni, 1990]. Etzioni's program STATIC matches PRODIGY's performance by statically analyzing the problem-space without using any exam­ ples. Thus, even though [Etzioni, 1990] explains why PRODIGY works, it fails to explain the role of exam­ ples in EBL-type systems in distribution-independent learning. This paper shows that EBL can gain from the problem-space structure as well as examples. The exam­ ples play two roles: first, they provide distribution infor­ mation that determines which macros are worth learn­ ing, and second, they help the learner avoid expensive search for macros.

Serial Parsing is given the order in which subgoals are achieved. In systems like SOAR that successfully learn macros using EBL, the goal ordering is implicitly given by defining the subgoals such that they include one an­ other [Laird et al., 1986]. In [Tadepalli, 1991], a method called Batch Parsing is described which learns the sub­ goal ordering along with macros for the subgoals. The basic idea here is to learn the macro table column by col­ umn, using multiple examples to disambiguate the fea­ ture that corresponds to a given column. [Chalasani et al., 1991] describes algorithms that detect serial and total decomposability by experimentation.

One consequence of our formalization is that it blurs the distinction between EBL and empirical learning. To the extent that the output of an EBL method depends on examples, EBL is also an empirical method. We showed that EBL systems also have syntactic biases in that their performance is based on some assumptions about the structure of the target problem solver. The main dif­ ference between the "empirical" and the "explanation­ based" approaches seems to be that the EBL .systems also have a "semantic bias" in that their hypothesis space is also constrained by consistency with their domain the­ ory.

7 Conclusions

The main contribution of this paper is an integration of EBL with formal machine learning. The most important result of our analysis is an explication of the biases that allow EBL methods to guarantee performance improve­ ment in the limit. Conditions which were thought neces­ sary for EBL to work, e.g., declarative representation of operators, were found to be not so crucial from our anal­ ysis. On the other hand, the structure of the problem­ space and the distribution of problems were found to be very important . Our paper also integrated Korf's work on macro-operator learning with the EBL work.

Our work suggests that the best way to solve the util­ ity problem is to implement a bias that exploits the do­ main structure. In the future, it is worthwhile to inves­ tigate the kinds of biases that occur in natural domains and implement them in new learning algorithms. As in empirical learning, this means that the program is then not suitable for domains which do not satisfy this bias. We think that the best way to address this gener­ ality issue is to build a variety of learning systems which are appropriate for domains with different problem-space structures.

Acknowledgments

I am indebted to Balas Natarjan for his generous help and advice throughout this work. I thank Prasad Cha­ lasani, Tom Dietterich, Oren Etzioni, Nick Flann, Srid­ har Mahadevan, Tom Mitchell, Balas Natarajan, and Armand Prieditis for many fruitful discussions. I also thank them, Barney Pell, and the anonymous reviewers of this paper for their comments. I thank Walter Rudd for his generous support and encouragement.