Concept Learning by Experiment

1. Introduction

ltlch of the emphasis in current research on con­ cept learning and rule induction is based on two assl.llllptions. Firstly, all that needs to be known to learn a concept can be obtained directly from examples given to it, without reference to previously learnt knowledge. Secondly, a sufficient number of examples to learn the concept is available, and all examples are presented simultaneously.

Relatively little attention has been given to developing systems which are able to improve their performance over time by using knowledge that has been learnt before. Two except ions are [ Winston70a) and [Cohen78a].

The usual task for a learning program is: Given a set of positive instances and a set of negative instances, produce a concept description which di&­ tinguish&s between these two sets. The program pas­ sively accepts its input and otherwise does not interact with the envirorment. Furthermore, it is expected that the concept will be learnt in one se s­ sion.

A program has been developed which learns con­ cepts by searching a knowledge base which is augmented each time a new concept is learnt. A concept descrip­ tion may be treated as a program which may be execu­ ted. The output will be the description.of an object which is an instance of the concept. A trial concept may be tested by executing the description as an experiment to see if the desired result is produced.

2. Representing Concepts

Suppose a trainer gives the program a description of an object which characterizes the concept to be learnt. For example, an instance of "on-top-of" is,

S1 · <shape: sphere; colour: red> B1 · · <shape: box; colour:green>

E1 · <top: S1; bottom: B1>

Objects are descr:fbed by a list of attr:fbute/value pairs.

The description language used is based on first order predicate calculus (with quantifiers). It evol­ ved from DL [Banerji69a) and CODE [Cohen78a]. A description of E1 as a concept may be,

Concept Learning by Experiment

Claude Sammut

School of Electrical Engineering and Computer Science Univeristy of New South Wales P.O. Box 1, Kensington, N.s.w., Australia, 2033.

[Xl: [3X2, X3: top of Xl is X2 & bottom of Xl is X3 & shape of X2 is sphere & colour of X2 is red & shape of X3 is box & colour of X3 is red (1) (2) (3) (4) (5) (6)

A concept description may include references to pre­ viously learnt concepts, · for example, "flat(X3)". "Flat" is a concept already learnt and is true if applied to the shape of X3 which, in the example, is the box B1.

The equivalence relation "is" need be the only built in relation known to the system. All other relations can be constructed using "is" and referring to other concepts.

3. The Generalization Process

Suppose the following concepts are already known,

flat · [Xl: shape of Xl is box I shape of Xl is table has-shape · [X1: shape of Xl is sphere I shape of Xl is pyramid I flat(Xl) has-colour · [Xl: colour of Xl is red I colour of Xl is blue I colour of Xl is green I phys-obj - [Xl: has- shape( Xl) & has-colour ( Xl)

"has-shape" and "has-colour" specify the range of values acceptable as shapes and colours. "flat" is a sd>set of shapes. "phys-obj" states that a physical object is a thing which has shape and colour.

If we examine the de script ion of El we see that statement (3) matches the first disjunct of "has­ shape". That is, S1 is an instance of objects \o'hich possess the property "shape". Thus a generalization of (3) is

has- shape ( X2)

Similarly, {4) can be gener&l.ized to

Now, statements (7) and {8) together match sta tements in "phys-obj", therefore we can deduce the

We can go through the same process with X3:

Note that we have not tested whether any of these generalizations are relevant to the concept which the trainer wants the program to learn. In the following sec tion we descr:lbe how the program tests its general­ izat ions.

4. Using Concept Descriptions as Programs

of ": Consider the following description of "on-top-

[X1:

[:IX2, X3: top of X1 is X2

• & bottom of X1 is X3
• & phys-obj(X2)
• & flat(X3)
• & phys-obj (X3)

If I assert that [ X: on-top-of(X)], that is, X is an "on-top-of" situation, then the program will construct x. In other words the program will find an instance of "on-top-of". It does this by attempting to prove the assertion by a process similar to resolution theo rem proving.

During the learning process, when the program wishe s to test its trial concept, it generates an ins tance of this trial and shows it to the trainer · The description of "on-top-of" given above is the correc t one. However, suppose that in the process of maki ng generalize tiona, the program tries phys-obj (X3) without the qualification "flat(X3)". In this case, the object which is constructed may have a pyramid on the bot tom which is not allowed.

s. An Examp l e of Learning

Given E1 as a positive instance, the program tries to produce a generalized description of "on­ top- of". The first generalize tion will involve the replacement of statement (3) by (7). In order to test its generalization, it proposes to the trainer an alternative "on-top-of" situs tion:

S2 · <shape: pyramid; colour: red>

E2 - <top: S2; bottom: B1>

Note that when a statement such as {3) has been repla­ ced, the object construction algorithm ensures that S2 will not be a sphere. Since this a good example of on-top-of, the generalization is correct.

In fact the specification of X2 can be general­ ized to any physical object. However, if the prog.ram allows X3 to have any shape, then the following object may be construe ted:

P1 · <shape: pyramid; colour: green>

E3 · <top: 51; bottom: P1>

With a pyramid on the bot tom, E3 does not describe a stable structure, therefore the trainer rej ects this alternative.

The program now makes a new generalization which attempts to explain why a pyramid cannot support another object. That is the generalization must be restric ted so that only objects which may support other objects are allowed. This restriction proces s looks at the statements which have been replaced by the incorrect generalization to determine how to spec ify the sti>set. In this example i t is necessar y to return "flat(X3)" to the concept description.

6· Conclusion

The learning process may be regarded a s a fo rm of automatic programming. The algorithm demonstrated here, although simple, is capable of learning quit e compl ex concepts, including list reversal and other abstract recursive concepts. Once "reverse" is known, the system can actually perform a list reversal on given input data.

Since each disjunct of separately, it is possible description over a period of ted by another lear ning task. a concept is l earnt to build the complete time, possibly interrup-