An Augmented EBL and its Application to the Utility Problem

1 Introduction

EBL (Explanation-Based Learning) is a framework of deductive learning [Mitchell et al., 1986]. Given an ex­ ample of the goal concept, it builds an explanation, and learns a concept description as its generalization. It can learn justified generalizations from only one example when the domain theory is perfect, but,it does not work when the domain theory is imperfect. Several types of imperfectness have been pointed out, and they are called imperfect theory problems.

SBL {Similarity-Based Learning) is a framework of in­ ductive learning [Mitchell, 1982]. Given positive and negative examples, it extracts similarities, and learns a concept description as their generalization. It can learn something without any domain theories, but it re­ quires numerous examples, and learned descriptions are no more justified.

EBL and SBL have complemental features, and can be placed at both extremes in continuum of imperfectness. In real applications, we cannot expect perfect theories nor fully imperfect ones. Therefore, it is necessary to unify EBL and SBL to resolve their difficulties.

This paper attempts to solve imperfect theory prob­ lems of EBL by augmenting it to handle plural examples simultaneously [Yamamura et al., 1989a] [Yamamura, 1990a]. We augment EBL rather than SBL because SBL has no explicit domain theories and we want to avoid im­ plicit ones such as inductive bias.

Mitchell et. al. have pointed out three types of im­ perfectness i.e. incomplete, intractable and inconsistent theories [Mitchell et al., 1986]. We add non-operational one into them and look them as levels of imperfectness. This seems useful as an index of a class of learning. Up­ per part of figure 1 shows dependencies of these levels. SBL is placed at the most imperfect extreme. Tractabil­ ity requires completeness since an incomplete theory is useless if it ignores "difficulties" of that domain. Con­ sistency requires tractability since explanations of con­ sistency may not be build if it is intractable. Utility problem of conventional EBLs is placed below them.

There are many works on unifying EBL and SBL. Their domain theory can be placed in some level of im­ perfectness. For example, IOE (Induction On Explana­ tion) of [Flann et al., 1989] specializes a domain theory which is complete, tractable but inconsistent. Chunk­ ing macros for such as 8 puzzle from primitive operators which is complete but intractable [Laird et al., 1986]. [Bergadano et al., 1988] use SBL when an explanation can not be constructed from domain theory which is in­ complete.

Lower part of figure 1 summarizes our works on the augmented EBL. In this paper, we forcus on utility prob­ lem, then also discuss on other problems.

2 A ugmentated EBL

2.1 Generalization of Explanation Structures

In this paper, we assume logic program as a descrip­ tion language. A domain theory D is a finite set of defi-

Figure 2: a domain theory and examples.

nite clauses. An example E; is a finite set of ground unit clauses. A goal concept is a predicate, and is given as a ground negative clause +- G for each examples. A goal concept is explained or proved iff D U E; U { +- G} 1- D.

In the goal regression method [Mitchell et al., 1986], a conclusion of an EBG (Explanation-Based General­ ization) comes from the goal concept, and preconditions come from the facts. Constants are generalized into vari­ ables, and resolutions are undone. The following defini­ tion generalizes these operations.

Definition 1 (generalization of an explanation)

1. For a Horn clause C = A +- B1 1\ · · · 1\ Bn, let its equivalent copy be C' = A' +- B1' A· ·· 1\ Bn'· Then, following expression is an explanation structure.

C and C' are called its internal and external structure respectively.

1. For an explanation structure T, let C' be its external structure and u be a substitution. Then, the expression Tu, which has the same internal structure as T and has the external structure C' u, is called an instantiation of T . Inversely, Tis called an uninstantiation of Tu.

3. For two explanation structures S and T, let A' +­ Bl' 1\ · · · 1\ B/ 1\ · · · 1\ Bn' and B/ +- C1' 1\ · · · 1\ Cm' be their external structures respectively. Then, the ex­ pression U connected S and T at B/ is called a (binary)

resolvent of SandT. Inversely, S is called an unresolu­ tion of U, and Tis called its remainder.

4. An explanation structure S is more general than T, denoted by S :j T, iff there exists a sequence of unin­ stantiations and unresolutions from T to S.

For example, consider a domain theory D shown in figure 2. In SLD resolution, a negative clause and a def­ inite clause are first unified then binarily resolved upon some literal. Figure 3 shows this inference scheme, where thick arrows denote rules and double lines denote ":" of definition 1. Dotted boxes denote internal structures of explanation structures. Internal structures holds the his­ tory of clause applications, and external structures holds the actual instantiation.

In conventional EBL on logic programming [Hirsh, 1987][Kedar-Cabelli et al., 1987][Prieditis et al., 1987], a generalization is defined as an inverse of one inference, i.e a pair of an unresolution and an uninstantiation. We consider them separately in order to handle generaliza­ tion of compound terms (or structured objects) because instantiations of heads of clauses affects inference effi­ ciency under a pure-Prolog interpretor. Figure 4 shows a full explanation structure for E1.

An EBG learned with an EBL system must be a the­ orem of that domain theory. For this constraint, we in­ troduce a concept of an obliged generalization.

Definition 2 (EBG)

1. An explanation T is an obliged generalization, iff the internal structure of T does not include any facts of a certain example and its external structure is a definite clause.

2. Obliged generalizations of an explanation for some example are called EBG. For an EBG, its external struc­ ture is called an EBG macro.

Figure 5 shows some of EBG macros of the explana­ tion of figure 4. m1 to m6 are all unresolved at line 0 to be definite clauses. m1 is less general than the obliged generalization i.e it includes facts of E1, then it is not valid in other examples. m2 is the obliged generalization {additionally unresolved at line 1). m3 is the most unin­ stantiation of m2. m4 is more unresolved than m2 {line 2). ms is the most uninstantiation of m4. m6 is general­ ized until the domain theory {line 3). Remark there are a number of generalizations from only one explanation.

2.2 Generalization Space

Since various generalizations are obtained from one explanation, various sets of various generalizations are obtained from plural examples. We call such a class of all sets of generalizations a generalization space.

Definition 3 (generalization space)

1. For an explanation T E T, let To be an unin­ stantiation ofT. Then T' = (T- {T}) U {To} is an uninstantiation of T. Similarly, let To be an unreso­ lution and T1, · · ·, Tn are its remainders. Then T' =

(T- {T}) U {To,···, Tn} is an unresolution ofT. 2. An explanation set S is more general than T, denoted by S ~ T, iff there exists a sequence of uninstantiations and unresolutions from T to S.

3. A class of all generalization of the obliged generaliza­ tion of an example set is called its generalization space.

For example, ~ of figure 2 is the same as E1 except the hero and the instrument. Figure 6 shows a part of the generalization space generated from { E1, E2}. Pred­ icates and constants are simplified in their initial. 0 is the obliged generalization that is only unresolved at the goal and facts of examples. 1 and 2 uninstantiate "john" and "tom" respectively. 3 uninstantiates both. 4 unre­ solves the weapon, and the same structure is extracted in there. "weapon{knife)" and "weapon(gun)" in 4 are the remainder of that unresolution. 5 is the most general, i.e the domain theory.

Thus, a generalization space contains all candidates that are learnable from given examples. Learning prob­ lem in the augmented EBL is to search a good general­ ization with some criteria in a generalization space.

2.3 Least EBG

A common generalization such as 4 of figure 6 can be thought of as "simirality" in SBL. We call the most spe­ cial common generalization the least EBG. It is known that least EBG is unique and computable incrementally regardless of example orderings.

Definition 4 (least EBG)

For EBGs T~, · · ·, Tn, T is a common EBG iff T ~ T1, · · · , T ~ Tn. The least generalization in common EBGs is called the least EBG.

Theorem 1 (features of the least EBG)

1. There is the least EBG for any set of EBGs.

2. Let T be the least EBG of T1, · · · , T,. and T' be the least EBG of Tk+l, ... ,Tn. Then, the least EBG ofT and T' is the least EBG of T1, · · · , Tn.

Proofs are given in [Yamamura, 1990a]. To prove the uniqueness, we used a lemma that the most gen­ eral unifier and the least uninstantiation commutes each other. If there are another minimal common generaliza­ tion, they are equivalent by this lemma. Computability is a corollary of uniqueness. Thus, the uniqueness of the least EBG closely relates with the uniqueness of the most general unifier. ms of figure 5 is a least EBG.

From a viewpoint of extracting similarities, a general­ ization subspace that consists of least EBGs is interest­ ing. We call such a subspace a least EBG space.

Definition 5 (least EBG space)

1. For S !;; T, let To be the least EBG of S and T1,···,Tn be its remainder. Then T' = (T- S) U {To,···, Tn} is called a least EBG generalization ofT. 2. Sis more general by least EBG than T iff there exists a sequence of least EBG generalizations from T to S. 3. A class of all least EBG generalizations of the obliged generalization of an example set is called its least EBG

space.

0 and 4 of figure 6 are a least EBG generalization. In general, there are combinatorially many least EBG generalizations for more than three examples, and its size can much more increase if remainders are generalizable. However, the searching space is reduced from the raw generalization space.

3 An Approach to the Utility Problem

3.1 Operationality Criteria

Utility problem is a problem to learn more efficient pro­ gram under complete, tractable, consistent but non­ operational domain theories. A learner needs to improve performance without violating initial perfectness of the domain theory. We assume a pure-Prolog interpretor and learned EBGs are merely inserted before the domain theory.

Efficiency of EBGs are maesured with operationality criteria. There are several alternative levels to define operationality [Keller, 1988]. In many existing EBL, the most detailed level of CPU time is used. Here, we define them in more abstract level with maximizing usage de­ grees and minimizing backtrack numbers. They reflect on natural requirements to be an efficient program for pure-Prolog.

Definition 6 ( operationality criteria)

1. For a generalization S = (T - {T}) U {To,···, Tn}, its usage degree is a function s.t.

where !Til denotes the number of clauses used inTi. In general, when S :j T, the usage degree sums up all usage degrees through some generalization path.

2. For an example set £ and its generalization T, the backtrack number B(T, £) is the minimum of the sum of goal failures which occur during a macrotable of T reconstructs all explanations of £.

3. For two generalizations SandT of an example set£, Sis more operational than T iffU(S,£) ~ U(T,£) and B(S, £) ~ B(T, £).

Usage degree measures an applicablity or a storage cost. It increases when one macro becomes commonly used in more than two examples. Backtrack number measures an efficiency or a searching cost. It counts backtrackings when a problem solver re-construct expla­ nations for examples. These two measures show opera­ tionalityfgenerality trade-off of [Segre, 1987]. ·

In Figure 6, u denotes a usage degree and b denotes a backtracking number. The least EBG (4) is the most operational macrotable because its usage degree is the maximum and its backtracking number is the minimum.

Two measures of operationality criteria increases ac­ cording to generalization as shown in figure 6 but it is not monotonic. FQllowing fact holds in general.

Theorem 2 (partial monotonicity)

For S :j T :j £, U(S, £) 2! U(T, £). And if U(S, £) = U(T, £), then B(S, £) ~ B(T, £)

Proof was given in [Yamamura, 1990a]. The total monotonicity of usage degree is clear. To show the par­ tial monotonicity of backtracking number, we can con­ struct a macrotable of T that has less or equal back­ tracking number by arranging a macrotable of S.

The reason why backtrack number incleases partial monotonically is for ambiguous macros that have the same head but different bodies as shown in figure 6. Such ambiguous macros increase according to general­ ization. However, when they are generalized until the same structure, i.e. when the usage degree increases, this ambiguity is often reduced.

The partial monotonicity is not preferable feature to search operational EBGs efficiently. However, since they increase monotonically in subspaces of the same usage degree, their minimal generalizations seems to be useful. The least EBG is such a generalization. Figure 7 shows tipical generalization space.

Theorem 3 ( operationality of the least EBG)

A least EBG generalization is minimal in the subspace which consists of generalizatins of the same usage degree.

Proof is given in [Yamamura, 1990a]. To prove this, we have shown any generalization between the obliged generalization and a least EBG generalization have less usage degree. This theorem shows the utility of the least EBG.

3.2 Least EBG Learner

We have constructed a simple incremental learner to demonstrate the utility of least EBG. Figure 8 shows its top-level actions. (-) and ( +) denotes input and output variables of predicates respectively. Examples are given incrementally through example/2. Explanations are gen­ erated with solve/3 by learner itself. In that time, cur-

Figure 8: the top-level of the learner.

rent macrotable Cur MT is inserted before the domain theory and used.

lebg...space/3 generates whole LEBG space GenSp from CurMT U {Expl}. operational/2 select the most operational EBG from GenSp. We assume that back­ tracking number has higher priority than usage degree. Learner proceeds to next example with selected N xtMT by tail recursion.

Least EBG learner simply generates the whole least EBG space. Its size exponentially increases with the number of explanations of the current least EBG set. Remark that it is not the number of examples. Examples are summarized into least EBGs and learner can keep its efficiency. This is a practice of the theorem 1.

Least EBG learner is implemented on SICStus Prolog on Sun4. In next section, we demonstrate least EBG learner in two extreme cases.

3.3 Learning in a Recursive Theory

3.3.1 Deterministic Recursion

Consider the well known linear recursive predicate member /2 shown in Figure 9. The learner is given n examples whose target element is at first, at second, · · ·, at n-th place. In much of existing EBLs, its per­ formance often becomes wrong because it generates the same number of macros as examples like LEBG1 [Priedi­ tis et al., 1987]. On the other hand, least EBG learner learns original domain theory because it has no back­ tracking and maximum usage degree like LEBG2. The usage degree of LEBG2 becomes n(n- 1)/2- 2 for n examples. Offcourse LEBG1 also has no backtracking, but usage degree, which reflects someway matching effi­ ciency, remains minimum.

It is important for a learner to learn nothing when there are nothing to learn. In fact, following theorem

Figure 9: least EBGs of a deterministic recursive theory.

holds.

Theorem 4 (learning a deterministic recursion)

If a domain theory solves any examples without back­ tracking, least EBG learner learns least EBG of no back­ tracking and of the maximum usage degree, regardless of example orderings.

Proof We show this by induction. It is clear for one ex­ ample. Fork example, assume the learner has LEB�~c of no backtracking and of the maximum usage degree. For (k + 1)-th example, we show contradiction if there does not exists LEBGk+l of no backtracking from the union of LEB�~c and that example. The clauses that causes backtracking must have the same rules in their root of their explanation structures, because original do­ main theory have some backtrackings if they have dif­ ferent rules. Then, their least EBG generalization will reduce this ambiguity because original domain theory have no backtrackings and least EBGs are less general than it. Thus least EBG of no backtracking is found, and it has the maximum usage degree from theorem 2. Q.E.D.

This theorem is applicable for domain theories that contains some redundant non-recursive clauses, such as "hate(W,W) :- depressed(W)" in previous section. Much of existing speed-up learning pointed out that un­ winding such redundant clauses contribute to improve efficiency[Subramanian et al., 1990]. This theorem ex­ tends this facts into deterministic recursive theories.

3.3.2 Non-linear Recursion

We show another extreme. Consider ancestor/2 that search transitive relation shown in figure 10. The learner is given examples of all of six discendants of a. Original domain theory causes infinite branch for "+- ancestor( a,/)" and "+- ancestor(a,g)".

Much of existing EBLs learn exhaustive cache of all example like LEBG1. It is a kind of rote learning but the most operational least EBG because the slightest generalization causes backtracking like LEBG2. Espe­ cially, self-unwindings of transitive rule make situation

Figure 10: least EBGs of a non-linear recursive theory.

Figure 12: a negative example and the MSV.

worse. [Subramanian et al., 1990] have pointed out there exists such a situation that the generalization-to-n in non-linear recursive theories misleads efficiency. The ex­ ample of ancestor/2 supports this from a viewpoint of operationality.

Unfortunately, since our simple least EBG learner does not generate whole least EBG space of given ex­ amples, it is sensitive in example orderings in such a domain. However, it does not generate LEBGs that cause infinite branch, given such as { +- ancestor( a,!), +- ancestor(a,d)}, and merely caches them. Therefore, least EBG learner is sufficiently useful in such a domain.

4 Approaches to Other Imperfect Theory Problems

4.1 Inconsistent Theory and EBG Version Space

Inconsistent theory is distinctive in analytic problems such as classification and diagnosis. It is natural to look inconsistency as failures in classification or diag­ nosis. We assume that training examples are given with judgements whether they are positive or negative, and define a domain theory is inconsistent iff some negative examples are provable as positive examples. A learner with the inconsistent theory must change its competence rather than performance. We assume a learner swaps rules which conclude the goal concept with EBGs. These assumptions are similar to [Flann et al., 1989].

A learning task is to find EBGs s.t. prove positive examples but never prove negative examples. In SBL, such generalizations make a range called a version space. We show an EBG space of this paper have the same structure as a version space, and that when the number of disjunctives, i.e the number of macros, are bounded ton, its MSV is a least EBG generalization [Yamamura et al., 1990b].

For example, consider a domain theory which have a tree structured conceptual hierarchy. Figure 11 shows such a domain theory as an and-or tree. This is a re­ finement of D of figure 2 where small-w denotes "small weapon" and so on. This domain theory is inconsistent. Figure 12 shows one of provable negative examples. Ea says that a king might not kill himself with a cannon if he were depressed. To exclude this example, a learner must specialize the domain theory to constrain instru­ ments for self-destructions to small weapons. The MSV of the !-bounded EBG version space is the least EBG as shown in figure 12 It includes all small weapons but excludes any big weapons.

IOE of [Flann et al., 1989] is the MSV of !-bounded version space. Thus, the EBG version space is thought of as an extention of IOE to n disjunctives. IVSM of [Hirsh, 1989] also uses the concept of version space. His version space is defined on features output by EBL, and is used also for incomplete theory. Our version space is defined directory on an EBG space, and we use more knowledge intensive method for incomplete theory.

4.2 Intractable Theory and Knowledge Compilation

The intractable theory problem is distinctive in synthetic problems such as planning and design. For example, op­ erator definitions of 8-puzzle are complete and consistent for any state transitions, but it is intractable to build a solution only with them. There often exists some strate­ gies to solve any problems without search, such as a con­ cept of serially decomposable subgoals in 8-puzzle [Korf, 1985]. A learning task for intractable theory problem is a knowledge compilation to find such strategies.

We have developed two kinds of approaches. One is to extract correct macros from instructed solution from a teacher under domain theory of primitive operators for problem solving domain that has serially decompos­ able subgoals such as 8 puzzle [Yamamura et al., 1989b]. Least EBG is used to extract correct macros. However, it often falls into a difficulty of SBL that a learner re­ quires numerous negative examples until convergence. It means that the computational load shifts from EBL to SBL to resolve the imperfectness of the domain theory.

Another is to extend the interpretor to consider de­ cision level or control level domain theory like [Minton et al., 1987]. By this, intractable theory problem at ob­ ject level can be regarded as another kind of imperfect theory problem at decision level. We have developed de­ cision level domain theory for problem solving domain that has serially decomposable subgoals [Yamamura et al., 1990b]. This approach is a kind of knowledge com­ pilation.

4.3 Incomplete Theory and Knowledge Transfer

For the incomplete theory problem, we have proposed an approach in classification problems using a background theory in addition to the domain theory and examples [Araki et al., 1990]. A background theory consists of a commonsense knowledge such as text books or dictio­ naries. A learning task is to extend the domain theory by transferring knowledge from the background theory based on similarities of examples. The least EBG can be also used to extract similarities. Remark that without a background theory, the learning task is degenerated into SBL when the domain theory is the most incom­ plete one, i.e. null. We have given a solution only for a constrained class of domain theories. Otherwise, it soon falls into difficulties of SBL.

IVSM of [Hirsh, 1989) uses pure SBL method when the domain theory is incomplete. Our approach aims more knowledge intensive method since it seems more natural that there exists somewhat relevant knowledge in the background knowledge when the domain theory is incomplete.

5 Conclusion

In this paper, we proposed an augmentation of EBL to handle plural examples simultaneously under imper­ fect domain theories for unifying SBL and EBL. We presented solutions to utility problem with least EBGs which extract similarities of plural examples. There re­ main many prt>blems in more imperfect theories, and the augmentation brings together intrinsic difficulties of SBL. However, in real application, useful expertise for learning seems often ignored because they do not fit with existing frameworks. Therefore, knowledge intensive ap­ proaches like the augmented EBL seems important.