The Discovery of the Equator or Concept Driven Learning

THE DISCOVERY OF THE EQUATOR or CONCEPT DRIVEN LEARNING

Werner Emde I Christopher U. Habel I Claus-Rainer Rollinger Technische Universitaet Berlin PROJEKT KIT , Se kr. FR 5-8 Franklinstr . 28129 D-1000 Berlin 10 (Fed. Rep. Germany)

ABSTRACT

This paper presents a model-driven method for machine learning of inference rules, which involves both: 'learning by induction' and 'learning by being told'. By the use of higher concepts (like transitivity and conversity) attributes of and relations among two-place predicates are discovered by induction. This new knowledge is represented as metafacts which can be transformed into inference rules if needed. The relations among meta facts are expressed as meta rules. The higher concept of support sets correspond to the domains for which meta facts are true. The process of restructuring support sets in order to resolve contradictions (and to make inference rules more precise) is discussed.*

I INTRODUCTION

In the area of expert-systems the acquisition of knowledge is known to be a problem machine learning as a discipline is one result of that. An AI-system which models a special part of the world has to be seen as a knowledge based system. Its implementation presupposes the analysis of that domain, and in most cases, these domains are not as well-known as they should be. So we are dealing not just with a specific problem of expert systems but with a general AI problem.

If we divide knowledge into facts and rules, the process of discovering inference-rules is the more interesting one, because these inference-rules express the ways of thinking in a specific domain.

This paper presents a method for machine learning of inference rules which involves both 'learning by induction' and 'learning by being told'. Concern the latter, it is assumed that the generalizations depend on the ordering of the facts told to the system (or to a human being) (see section 3). The former corresponds to higher concepts which are

used to structure a new domain described by facts.

II LEARNING HIGHER CONCEPTS

One of the main classes of inferences is defined

* The work of the first and third author has been supported by the BMFT (Bundesministerium fuer Forschung und Technologie) under grant (PT 135.01). The second author has been supported by the German Research Foundation (DFG).

by "semantic relations among words" (cp. [8]). Using Miller's "conceptual entailment" relation (->) among sentential concepts the meaning of lexical concepts can be described. For instance, some aspects of the meaning of the predicative concept "colder-than" can be explained with entailment-relations (e.g. transitivity):

(1) colder-than(x,y) & colder-than(y,z) -> colder-than(x,z)

Johnson-Laird [5] had in mind the problem of transitivity or non-transitivity of 'right-of' when argueing against meaning postulates and the existence of transitivity rules for such predicative concepts as "colder-than" or "right­ of". He especially stressed the fact that the transitivity of "right-of" depends on some properties of the arguments of the predicative concept .

We still propose the higher concept "transitivity" specifying two-place predicative concepts, since such higher concepts are needed for reasons. of cognitive economy. One component of them are rule schemata (p,q =variables for predicative concepts) as exemplified in Fig. 1.

Some higher concepts and their rule schemata: transitivity trans (p) p(x,y) & p(y,z) -> p(x,z) conversity conv (p,q) parallelism par (p,q) p(x,y) <-> q(y,x) p(x,y) <-> q(x,y) Some positive characteristic situations: trans p(a,b) & p(b,c) & p(a,c) p(a,b) & p(b,c) & p(c,d) & p(a,d) conv p(a,b) & q(b,a) not (p(a,b) ) & not (q(b,a) par p(a,b) & q(a,b) not (p(a,b) ) & not (q(a,b) Some negative characteristic situations: trans p(a,b) & p(b,c) & not ( p(a,c) conv p(a,b) & not (q(b,a)) par p( a , b) & not ( q (a , b) ) Some meta-rules: MR1 trans(p) , conv(p,q) -> trans (q) MR2 trans(p) , par(p,q) -> trans (q)

Fig. 1: Some higher concepts

Inferential rules can be generated by the system with such rule schemata. Since humans possess additional higher concepts (e.g. for spatial relations such as "linearity" or .. on a circle"

etc.), we introduce an additional theoretical concept: Support-Sets. Using this term we are able to say: ··colder-than is transitive on GEOGRAPHICAL­ OBJECTS (GO's) ··. In a mor e formal way this can be described by

1. support set (transitivity (colder-than), GO's)

with the interpretation "the rule schema of 'trans' is to be applied only on GO.··

In this paper we concentrate on support sets; they are the basis for discovering concepts like the equator.

Presupposing the existence of such concepts in the human mind we define the notion "characteristic situation for higher concepts" (CS). We distinguish positive CS's (+CS) (considering positive evidence) and negative CS's (-CS) (considering negative evidence- counterexamples [9]).

These CS's correspond to the rule schemata and have to be regarded as empirical evidence for the exis t e nce (or nonexistence ) of the transitivity of p. In case we find positive evidence of this sort, i.e. of instantiations of +CS's of a higher relational concept, we may hypothesize this higher concept for the corresponding predicative concept, e.g. the transitivity of "colder-than", Knowledge of this kind, i.e. of the type 'h-c(p-i)', which is built up from predicate constants (p-i) and constants for higher concepts (h-e), constitutes metafacts. (Similar concepts are used in OMEGA [4].) Acquisition of inferences through the use of higher concepts can be integrated in the system in

the following way *

• searching in the knowledge base for CS's
• analyzing the support set depending on the empirical data
• hypothesizing rule schemata
• -working with the new rule schemata.

III A LEARNING PROTOCOL

In this example facts are given to the system (relations among geographical objects (cp. Fig. 2) of North and South America) in order to demonstrate its capability of discovering relevant attributes of the relations.

Figure 3 lists facts involving geographical r e lations given to the system in a first step. Its task is to learn the concepts 'north-of' and 'south-of'. The positive instances for characteristic situations are identified by numbers behind the facts.

* The basic me chanisms and the architecture of a system based on the ideas sketched above are described in more detail in [3].

north-of nor ( A,B-C) cl nor (B-C, O) c1,c5 nor ( 0, C) c1 nor ( A, C) cl nor ( c, M) c6 nor ( M,Pan) c2,c3 nor (Pan, E) c2,c4 nor ( M, E) c2 nor (Pan,Bol) c3 nor (Bol ,Arg) c3 nor ( M,Arg) c3 nor (Par ,Arg) south-of sou (C H,Arg) sou A, E) sou ( -E, Pan) c4 sou (Pan, H) sou ( H, M) sou ( M, C) c6 sou ( O,B-C) cS sou (Par,Bol) sou ( M, A) Fig. 3: The Instructional Data - Step 1: Geographical Relations

Having computed these facts the system has generalized that 'north-of' and 'south-of' are transitive and converse (cp. Fig. 4), using the positive instances for characteristic situations

and me tarules.

In the next step data on meteorological relations are provided: The system has to learn the concepts 'col' and 'war', Again, positive instances are identified by numbers:

* DIRECT refers to data which the system knows by direct instruction. The other subtypes of supporting data correspond to inferred knowledge: TRANS to 'trans (nor)', CONV to 'conv (nor, sou)', and CONV&TRANS to conversity and 'trans(sou)',

The additional metafacts generalized on the basis of the previous knowledge and the facts of step 2 are listed together with the sources in the next table (Fig. 6). The parallelism of 'nor' and 'war' and of 'sou' and 'col' as well as the conversity between 'nor' and 'war' and between 'sou' and 'col' are induced by the new facts. The transitivity hypotheses of 'col' and 'war is inferred by metarules (cp. Fig. 6).

By the use of the inference rules produced out of the rule schemata with the help of the metafacts, additional data can be inferred.

IV ANALYSES AND RESTRUCTURING OF SUPPORT SETS

At this stage, all the knowledge is consistent, because we offered only·a special subset: instances of meteorological relations from the northern hemisphere. Up to now this distinction is unknown to the system, so for the countries from the southern hemisphere it still infers that the climate is warmer in the south. Now the system is given a first set of counterexamples (3.a):

col (C H,Arg) war (Bol ,Arg) and a second set of counterexamples (3.b): war (Par,C H) col (Arg,Par) col (Par,Bol) Fig. 7: The Instructional Data Step 3: Counterexamples

These new instructions violate the parallelism between 'nor and 'col' or sou' and 'war', respectively, i.e. they are inconsistent with mf4 to mf7, but consistent with mf8 and mf9. Thus the support sets of these metafacts (up to now the whole set GO) have to be changed. In the beginning the counterexamples are treated simply as exceptions and thus the support set strategy Sssl (cp. Fig. 8) is used *

Sssl: If there are exceptions ( not empty Ex-Set) then reduce the support set:

Sup-Set(mf.i,new) = Sup-Set(mf.i,old) \ Ex-Set(mf.i,new) Sss2: If the Ex-Set is large (or relevant) then try to find regularities in Ex-Set. If possible, reanalyse the support set, probably with respect to other or new mf.j's: Sup-Set(mf.i,old) = JOIN(SUP-SET(mf.i,new), Sup-Set.2(mf.j,new), Ex-Set(mf.i,new))

Fig · . 8: Strategies for restructuring the support set

* 'Ex-Set ( mf4, 3.a )' means 'the Exception-Set of the metafact mf4 after instruction step 3.a'. The other formulas· have to be interpreted analogously. In the following we discuss only mf4 (as example); via conversity and some of the other mf's the counterexamples and thus mf5 and mf7 are treated in the same way.

Ex-Set ( mf4, 3.a ) = { C H, Arg, Bol } Ex-Set ( mf4, 3.b ) = { C-H, Arg, Bol, Par and therefore by Sup-Set~Strategy 1: Sup-Set mf4, 3.a ) GO - Ex-Set ( mf4, 3.a) Sup-Set ( mf4, 3.b ) = GO - Ex-Set ( mf4, 3. b)

How is it possible for the system to infer that the Ex-Set is a relevant one, or in other words, why is it reasonable to try new generalizations with respect to Ex-Set? There is an obvious answer to this question: Inconsistencies (between the new data and the old metafacts) were created by a specific part of the factual knowledge, namely the knowledge about temperatures ('war', 'col'), whereas the knowledge about geographical relations ('nor', 'sou') is of no concern here. Therefore the system looks for a regularity with respect to these knowledge items. Obviously (for man as well as machine) the relation

nor ( Sup-Set (mf.3,new) , Ex-Set (mf.3, new) )

holds. This could well be the natural reason for separating the Sup-Set and the Ex-Set. Now the system tries to generalize on Ex-Set with its usual methods. The results are the following:

GO.l Sup-Set (mf4, 3. b) {A,B-C,O,C,M,H,Pan,E} G0.2 Ex-Set (mf4, 3.b) {Bol,Par,Arg,C_H} metafact Sup-Set par (nor, col) mf4 GO.l par (sou, war) mf5 GO.l conv (nor, war) mf6 GO.l conv (sou, col) mf7 GO.l par (nor, war) mf4' GO. 2 par (sou, col) mf 5' G0.2 conv (nor, col) mf6' G0.2 conv (sou, war) mf?' G0.2 Fig. 9: The reanalysis of the Support-Sets

We conclude this section with a final step (step 4) of instructions:

It is easy to see that this new knowledge is consistent with the metafacts in Fig. 9; furthermore the system is able to find additional generalizations: it is possible to extend the Sup­ Set's to:

and analogously for the other mf.i's. This means that the Sup-Set's in question possess a non-empty intersection. On the other hand, the change from mf.i to mf.i' (i=4, .· ,7) is obviously a fundamental one. Therefore it is reasonable to view the intersection of the Sup-Set's as an area of particular interest. The system could read it this way:

There is a strange and interesting area on the continent where the relations between the concepts 'nor' and 'sou' on the one hand and, 'col' and 'war' on the other hand change drastically. If this change is a systematic one

(and not contingent) then it would be nice to give a name to this area. Since it is situated near Ecuador, 'ecuador-area' would be a nice name, wouldn't it? *

And herewith an AI-system has discovered the concept 'equator' ** (It should be ducked now!)

V CONCLUSIONS AND RELATED WORK

In the present paper we describe a method of learning inference rules by means of higher concepts of knowledge. The example used is an idealization with respect to the dichotomie (or rather spectrum) 'exact rules' -'rules of thumb'. We will deal with the latter case by using a concept of 'inexact reasoning'; thus the basic ideas described in this paper as 'higher concepts', 'support sets' and their analysis and restructering will be useful in this case, too.

Kindred learning concepts which influenced our work are learning by analogy [1], learning by clustering methods [7] and automatic theory formation [2].

We will conclude with two short remarks: First, the learning concepts described here have been given a first implementation in PROLOG by the KIT­ group at the Technical University of Berlin. Secondly, the system will be applied in a text­ understanding system (with knowledge about spatial and temporal relations).

* A clever system should do that, and we hope that our system is a clever one. But in the current state of implementation the system does not react in the sophisticated manner described above. It is only able to recognize that ''Something happens."

** As a difference to Lenats' AM [6] which is able to discover interesting mathematical concepts our system is more goal-oriented, is looking for concepts in order to resolve contradictions.