DISCIPLE-1: Interactive Apprentice System in Weak Theory Fields

DISCIPLE-1: INTERACTIVE APPRENTICE SYSTEM IN WEAK THEORY F1ELDS

YVES KODRATOFP

LRI, Inf6reoce et Appm!tissage, Bit. 490, U.A. 410 du C.N.R.S. & Uoiversit6 Paris-Sud, F · 91405 Orsay

GHEORGHE TECUO

Research Institute for Computers aDd Informatics, 71316, Bd. Miciurin 8-10, Sector 1, Bucharest, Romania

ABSTRACT

The paper presents an interactive approach to teaming apprelllice sys­ tems for weak theory domains. The approach coosists of a combination of learning by analogy aDd learning by geoeralizing instances. Ooe main point of this approach is that it uses the explanatioos drawn from an example, bocb to reduce the version space of the rules to be leamed, aDd to generate oew examples, analogous to the given one. Aootber im· portant point is that it demoostraaes not only that over-geoenlizali.on is harmless but also useful aDd oecessary, when interacting with a user. It sllows to use the theory of the domain, though iDcomplete as it is, in order to extract the missing lalowledge by aSking "clever'' questioos to its user. This paper presents a first prototypical version of DISCIPLE aDd its use to the design of tecboologies for the maoufacturing of loudspeakers.

I INTRODUcnON

If Expert Systems have proven useful in many domains, their lppli­ cations are limited by their inability to acquire aDd to updale their lalowledge. This problem is largely recognized as the knowledge ac· quisition bonleneck of Expert Systems (Feigenbaum 1977), (Mitchell & A1. 1985), (Kodratoff 1986), etc... Recent Macbine Leaming achieve· ments ((Mitchell, Carbonell & Micbalsti 1985) offer oew solutions to the lalowledge acquisition problem aDd open a oew uea in the evolution of Expert Systems, that is, Expert Systems able of automatic lalowledge acquisition aDd learning, such as Learning Apprentice Systems (LAS). A LAS is an interactive lalowledge-based consultant that clirectly usimi· lates oew lalowledge by observing, analyzing aDd questioning about the problem solving steps contributed by their usen through their normal use of the system. The user gives to the system a problem to solve aod the expert sub-system starts solving this problem by showing the user all the problem solving steps. The user may agree or reject them. Therefore, in its Expert System mode, a LAS may· eocounter two situations.

Either the current problem-solving step (which we shall further call partial solution) is accepted by the user. Then, the cunent state of the lalowledge base is judged as satisfactory, aDd no learning will take place.

Or it is unable to propose any partial solution (or the solution it po­ poses is rejected by the user). Then, the user is compelled to give his

own solution.

Once this solution is given, a learning process will take place. The LAS will try to learn a geoeral rule so that, when faced with problema similar to the current one (which it bas been unable to solve), it will become able to propose a solution similar to the solution given by the user to the current problem. We ue developing a LAS, called DISCIPLE. spe­ cialized for weak theory domains. In this paper we desaibe the ~ ing mechanisms of DISCIPLE. To this p111p01e we use examples from Technology Design. The oext section is a brief desc::riptioo of this domain. The following .sectioos present the learning problem aDd the learning method of DISCIPLE.

II A WEAK THEORY DOMAIN

We have chosen, as a first domain to test our approach to interactive LASs, the domain of designing technologies for the manufacturing of loudspeakers. Before presenting in more details this domain we stress two of its important features. FU'Stly, the domain is ususlly too complex for an autonomous system. Secondly, small improvements in technology have important outcomes since a technology is usually used for a large nunber of products. Therefore the best solution is searched. A CODSe· quence of these features is that such a domain is most appropriately han­ dled with an interactive system as the expert (coosultant) sub-system of a LAS, where the user aDd the system cooperate in finding the best solu­ tion to the current problem.

Teclmology Design might well be viewed as successive decompositions of complex operations into simpler ones, aDd successive specializatioos of these simpler operations by choosing tools, materials or verifiers, which are in turo successively specialized. To design a technology, DISOPLE Deeds some lalowledge about the compooents of the loudspeakers, about the technological solutions for the manufacturing of loudspeakers, about the tools aDd the materials one can use to manufac­ ture loudspeakers. All this knowledge coostitutes the domain theory. This domain theory is inherently incomplete since we can not suppose that DISOPLE lalows sll the objects of the domain, all the properties of a given object. all the actions that can be performed for manufacturing loudspeakers, all the properties of the known actions (precooditioos, effects), all the ways of decomposing or specislizing a given action,

etc ...

ill THE LEARNING PROBLEM

In the domain we have chosen, DISCIPLE acts as an aid to a tech­ nology desigoer. The problem to be solved is that of planoing the manufacturing of a certain loudspeaker. The solution to this problem is a plan of actioos . for manufacturing the loudspeaker.

The problem-solving paradigm is problem-reduction. That is, DISCIPLE will successively decompose an action into simpler actions or specialize an action to a better defined ooe. In this way, DISOPLE will build a problem-11olving tree. This process continues untill the leaves of this tree ue elementary actions. They represent the solutiOn to the original

problem (the top of the problem-solving tree).

Let us suppose that, during planning the manufacturing of a loudspeak·

u, DISCIPLE eiiCoUllters the following problem

AJTACH sectors ON chassis-membrane-<Jsstmbly

for which it is unable to propose a satisfactory solution. Let us furtlur 11uppose that 1M user indicated 1M following solution to DISCIPLE:

APPLY mowicoll ON sectors,

PRESS sectors ON chassis-membrane-assembly

Note that APPLY and PRESS may be actioiiS previously unkown to 1M system alld, in such a cast, it knows nothing about them uctpt that they

are meaiiS of ATI'ACHing.

Now DISCIPLE knows a solution of the current probltm ATTACH sectors ON chassis-membrane-assembly 1- APPLY mowicoll ON sectors, PRESS sectors ON chassis-membrane-assembly.

This solution will further be seen as an example of a general rule to be learned.

In this paper (and in the present version of DISCIPLE) we use the fol­ lowing generalization method. We suppose that the above example represents with fidelity the structure of the general rule to be learned. In this ·case, learning a general rule reduces to learn the concepts ( instan­ tiated in the example by 'sectors', 'chassis-membrane-assembly' and 'mowicoll' ) for which the ATTACH action can be safely decomposed into a sequence of APPLY and PRESS actions.

Therefore, the rule DISCIPLE will try to learn has the following form:

IF x, y, and z satisfy <constraintr.> THEN ATTACH x ON y 1- APPLY z ON x, PRESS x ON y The learning problem addressed by DISCIPLE is therefore : Given an example rule, generalize it and find its domain of application.

IV 1HE LEARNING METIIOD

The learning starts by interpreting a user's solution as an instance of a more general rule to be learned.

Ftntly, in its Explanation-Based mode, DISCIPLE looks for plausible explanations of the validity of the user's solution. It is essential to the success of DISCIPLE that there should be a possible explanation in cerms of the relations between the objects referred at in the example. One must nevertheless be well aware that. working in a weak theory domain, those explanations may sometimes be irrelevant ( as opposed to the ones provided in well-formalized domain ), and have to be validaced · by the user.

Secondly, · DISCIPLE encers its Analogy-Based mode. The analogy relies on the concept of similarity of the explanations : two rules are analogous wben they are supporced by similar explanations, and two explanations are similar when they both are instances of the same (over}-generalized explanation. In its Analogy-Based mode, the work of DISCIPLE is two-fold. On the one hand it attempts to build such an over-generalization from the examples it has got. On the other hand, it consults its knowledge base in order to generate new instances of the current over-generalization. We shall use the following approximation : the explanation of the user's example will be said to be a sufficient coa­ dition to the rule application, and the over-generalization will be said to be a necessary condition to the rule application. In that way, they can be compared to the S-set and G-set of Mitchell's Version Space (Mitchell 1978).

Thirdly, DISCIPLE uses Similarity-Based Generalization from exam­ ples. Analogy does not garancee the validity of the generated condi­ tions, which must once more be validaced by the user. The generated examples rejected by the user will be treated as negative examples, and the accepted ones as positive examples. In the same way as other gen­ eralization algorithms ( see, for instance (Michalski 1983, Kodratoff & AI. 1984) ), positive examples will be used to generalize the set of sufficient conditions ( otherwise stated : to increase the S-set ). Negative ones will be used to particularize the necessary conditions. This part of DISCIPLE has not yet be fully worked out, it will not be further described here.

Finally, if it happens that the S-set and the G-set become identical, a necessary and sufficiem condition has been reached , and an exact rule has been learned. This is seldom the case, especially in fields with a weak theory. In general, we shall keep the necessary 3nd the sufficient conditions separately. We then say that we have obtained a SYM· BOLIC UNCERTAIN CONDmON for the application of the rule.

V EXPLANATION-BASED MODE

The system will try to explain why the solution indicated by the user is a good one. Since DISCIPLE does not have a complete domain theory, it is unable to find alone such a "complece" explanation. Recall, for instance, that APPLY may be an action previously unknown to the system. It does not mean that DISCIPLE is waiting for an explanation from the user, but simply that it will try to find an explanation with the user's help. More precisly, it will try to propose several partial explana­ tions, asking the user to validate them.

The heuristic used by DISCIPLE is that the explanation has to be expressible in terms of the relations between the objects from the rule instance ('sectors', 'chassis-membrane-assembly', 'mowicoll'). While, in general, there exist many relations between two objects, it is expected that, in the world of an Expert System, only the relations relevant to the domain of expertise are present.

Therefore, DISCIPLE will look in its knowledge base for the links con­ necting 'sectors', 'chassis-membrane-assembly' and 'mowicoll'. They are illustrated in the following network:

~- -

Some of these links may be relevant for the rule to be learned wben they are plausible pieces of explanation. Since DISCIPLE does not have the necessary knowledge to make the difference ·between the relevant and the irrelevant lints, it will have to rely on the user, by asking ques­ tions which are issued from a straithforward analysis of these links: DISCIPLE will initiate the following dialogue ( where the user's answers are put between · ).

Is it relevant for the solution that: mowicoll GLUES sectors ? · yes · mowicoll GLUES chassis-membrane-assembly ? · yes · sectors PART-OF loudspeaker? · no · chassis-membrane-assembly PART -OF loudspeaker ? · no ·

Making use of this new knowledge, DISCIPLE will find an "explana­ tion" represented by the following network.

DISCIPLE will have to consider all such networks as candidates for explanatioo. 1bis process may become somewhat cumbersome. Nevertheless, it is much easier for the user to agree or deny a partial explanatioo, than to give oneself an explanation, which should also be understandable for the system.

VI ANALOGY-BASED MODE

Two situations are said to be analogous when a mapping can be done between the causal networks of these two situations (Winston 1980, Kedar-Cabelli 1985). Tbe above network will be seen as a causal net­ work of the decomposition in example rule. A heuristic used by DISCI­ PLE to find similar explanations is: two explanations are similar when the edges of their networks are indexed by the same values.

For instance, the following network is similar with the above one.

DISCIPLE uses the similatity between networks, and proposes instan­ tiated rules to its user. Tbese rules are obtained by replacing the expla­ nation pattern of the example rule by similar ones.

For instance, DISCIPLE will propose the following new rule.

ATTACH centering-device ON chassis-assembly

1- APPLY neoprene ON centering-device,

PRESS centering-device ON chassis-assembly

Since the analogy is never proven to be valid, the user will have to vali­ date it One can estimate the similarity between two networks, or con­ cepts, by computing their "best generalizatioo" (Kodratoff & Tecuci 1986b ). Tbe less general is their generalizatioo, the best their similarity. In DISCIPLE, we slightly modified the approach referred at in (Kodratoff & Tecuci 1986b). Instead of starting a costly generalization algorithm of the AGAPE kind (Kodratoff & AI. 1984), DISCIPLE rather over-generalizes the explanation it disposes of, and states that any two instances of this over-generalization are similar. In DISCIPLE's present implementation state, this over-generalization is very elementary : tum constants into variables by giving the same variable name to all the occurences of a same constant. It is part of our planned improvements to DISCIPLE to refine this definition. We are quite aware that such a generalization may not be a necessary conditioo. This is part of the approximations of the present system to accept this lack: of precisioo.

It follows that the over-generalization of the above networks is

which will also be used as a necessary condition for the application of the rule.

Any example DISCIPLE will generate in the Analogy-Based mode will have an explanation which is an instance of the over-generalized expression.

At this point the learned rule has the following form

IF [necessary condition] ((z GLUES x)&;(z GLUES y))

[sufficient condition] ((x !SA sector)&;(y !SA chassis-membrane­

assembly)&:(z !SA mowicoll)&;

(z GLUES x)&:(z GLUES y))

THEN ATTACH x ON y 1- APPLY z ON x, PRESS x ON y. which is an intermediary form of the rule during its learning. One remarlcs that the necessary condition can always be deduced from the

sufficient one.

In the Analogy-Based mode, DISCIPLE will generate instances of the intermediate rule, such that these instance will satisfy the necessary con­ dition ( and that will not satisfy the sufficient conditioo ).

In the previous sections we have presented in some detail the learn­ ing mechanisms of DISCIPLE. It shares, of course, many features with LEAP (Mitchell & AI. 1985), both relying on the same design princi­ ples: the interactive nature of problem solving, the association of each example to a single problem solving step, the partition of control and basic domain knowledge. On the other hand there are also important differences between LEAP and DISCIPLE. LEAP utilizes explanation­ based generalization. Therefore, it produces justifiable generalizatioo from a single example, it allows rejecting incorrect training examples, it relies on a strong domain theory (VLSI design). DISCIPLE utilizes a combination of Explanation-Based learning, learning by analogy, and Similarity-Based learning. It relies on an incomplete and/or weak domain theory, it relies on user to reject incorrect training instances, it produces justifiable generalizations from examples. DISCIPLE learns not only generalizations but also particularizations of coocepts (DeJong & Mooney 1986). Also, it uses the same interface paradigm for both problem-solving and learning (it proposes solutions and the user accepts or rejects them).

Tbere are several weaknesses of DISCIPLE, that are currently under improvement. Tbe method of finding an explanation is not powerfull enough. Other sources of knowledge are needed, as well as meta-rules for finding far-off explanations. Tbe explanation-based method does not use goal regression. Tbe use of theorems in the Analogy-Based mode is quite limited. From the practical point of view, DISCIPLE shows one more very important weakness. Its analogy mechanism works through our over-generalization process, which actually reduces to turning con­ stants into variables. It follows that _giSCIPLE is of interest if, and mainly only if, the given rules are such that the same constants show in their conditions and in their actions.

DISCIPLE-I has been implemented in LELISP (Chailloux 1985) and we are running it on V AX-750, and MACINTOSH computers. Implementa­ tions on SUN and Explorer stations are under way.