A Formal Approach to Learning From Examples

1. Introduction

Learning from examples is an important yet basic subarea of machine learning. For this approach. a learning system receives information concerning a domain of application in the form of facts . or ground atomic formulae. On the basis of this information the learning system induces general statements characterising the domain. and hence hypothesises relations among the known relations in the domain. These hypotheses are phrased independently of any particular individuals. Further facts may enable other hypotheses to be formed while falsifying existing hypotheses. Thus the consistency of the set of hypothesised statements must continually be maintained as new information is discovered. and the question arises as to how a set of hypotheses may be modified as falsifying instances are encountered.

The early work of Patrick Winston [Winston 75] provides a good example of such an approach. In Winston's system. descriptions of concepts are formed from a set of carefully chosen examples of the concept and "near misses". A near miss is an ex~mple .that is quite similar to an instance of the concept. but d11fers m a small number of significant details. Relevant features that the concept (presumably) must have are extracted from the positive examples. while negative information is extracted from the near misses. Thus from positive examples the. program might infer that an arch must have two supports. while from a negative example it might infer that the supports must not be touching. As examples are received. the definition of In this paper a formal. foundational approach to learning from examples is presented. The overall aim is to investigate the underlying formal aspects of such learning. In contrast to previ­ ous work. pragmatic concerns dealing with notions of evidence. confirmation and justification of hypotheses are ignored insofar as is possible. The goal of this paper then is to characterise the. hypotheses that may potentially be formed. The question of what hypotheses may justifiably be formed is not addressed. Thus for example if we have a set of black ravens and know of no non-black ravens. we could hypothesise that ravens are black. However the approach at hand gives no indication as to when such a hypothesis should be formed or what constitutes adequate evidence for such an assertion. So the goal is to determine for­ mal criteria which prescribe the set of potential conjectures. rather than to determine pragmatic criteria whereby an accept­ able set of conjectures may be formed. A similar distinction can be made in a deductive system. where an underlying logic specifies what could be derived. but not what slwuld be derived.

The remainder of this section expands on these ideas and surveys related work. In the second section. a language for expressing conjectures is introduced. and formal systems are developed for guiding the formation of conjectures. These sys­ tems lead immediately to a procedure for restoring the con­ sistency of a set of conjectures. Extensions to the approach are brietly described in the third and fourth sections. and in the fifth section the approach is compared with representative AI systems for learning from examples. Further details. proofs of theorems. etc. may be found in [Delgrande 85].

1.1. The Approach

The domain of application is assumed to be describable as a collection of individuals and relations on these individuals. Further. it is assumed that some portion of the domain. described by a finite set of ground atomic formulae (or. infor­ mally. "facts"), is known by the learning system. As time progresses the learning systenf will presumably encounter new information, and so the set of known ground atomic formulae will monotonically increase. Initially I assume that this (increasing) set of ground formulae is all that is known about the domain.

Hypotheses are proposed and modified on the basis of this finite , monotonically increasing set of ground instances. The hypotheses are expressed in a language. HL. that is a simple vari­ ant of the language of elementary algebra. The criteria for pro­ posing a hypothesis are straightforward: there is a reason to do so (i.e. some notion of evidence is satisfied) and the hypothesis is not known to be false. These criteria though are far too simplis­ tic. and in general the resultant set of hypotheses will be incon­ sistent.

These difficulties are circumvented in the following manner. With each term in a sentence of HL we can associate two subsets of the ground instances. consisting of those known to satisfy the term and those known to not. Thus to the term "black raven" we can associate the set of individuals known to be black and a raven. and the set known to be either non-black or non-raven. These (pairs of) sets interrelate in various ways: for­ mal systems are developed to precisely characterise relations between terms in HL by means of these sets. From these sys­ tems. ground instances whose truth values are unknown can be iteratively located so that determining their truth value leads to a convergence of the hypothesis set to consistency . These "know­ able but unknown ground instances" are composed of constants and predicates symbols that occur in the set of known ground atomic formulae. Informally they correspond to unknown but potentially knowable "facts" in the domain. The capability of testing individuals for membership in a relation. where both individuals and relation have been encountered in the set of known ground atomic formulae . proves essential for restoring consistency in a set of hypotheses.

The approach is clearly a restriction of the general problem of induction. However . induction. as such. plays a relatively minor role: it is used to suggest an initial (and usually incon­ sistent) set of hypotheses. which then are modified using strictly deductive techniques. The set of hypotheses that may be formed is shown to be perhaps surprisingly general and in fact (with respect to expressiveness) subsumes a number of existent sys­ tems for learning from examples.

In summary. I initially assume that:

1. the domain is describable as a set of ground atomic formu­ lae:
2. some finite subset of the ground atomic formulae is known:
3. the set of known ground atomic formulae is correct and error-free:
4. the set of known ground atomic formulae grows monotoni­ cally with time;
5. known individuals may be tested for membership in a known relation.

The first assumption is somewhat restrictive. and in section 4 is relaxed so that a learning system may be "told" arbitrary sentences. Also in the third section. the second assumption is relaxed to allow relations in the domain whose membership is completely known.

The third assumption is clearly unrealistic for any practical learning system. However. arguably the issue of how to deal with erroneous data is a pragmatic one. and is not relevant to our concerns here. Consider. as illustration. where we have some conjecture (say. "ravens are black") and encounter an albino. If we don't want to totally abandon our original hypothesis. then there seems to be two ways we can discharge the exception. First. we could amend the conjecture to something like "nor­ mally ravens are black". and perhaps also introduce "normally albino ravens are white". That is, one way or another. the excep­ tion is "excused". Second we could determine, or simply declare. that the observation is erroneous. However. this procedure of determining that an observation is incorrect, or otherwise excus­ ing it. is a pragmatic concern. and is distinct from our concern of what hypotheses "follow" potentially from a given set of ground atomic formulae.

1.2. Related Work

There has been much work in AI addressin~; the problem of learning from examples. including [Brown 73], [Buntine 86]. [Hayes-Roth 78]. [Mitchell 77]. [Shapiro 81]. [Solway and Riseman 77], [Vere 78] and [Winston 75]. [Michalski 83] is a partic­ ularly detailed approach to learning from examples. An exten­ sive survey of AI learning systems is given in [Dietterich et el 82]. while [Smith et al 77] describes a proposed model for learn · ing from examples and [Dietterich and Michalski 83] compares four particular generalisation programs. Typically such work is concerned with proposing and refining a description of a concept. and many of the above approaches detail particular rules or stra­ tegies for forming a general concept from a set of instances. Most of this work also assumes that the only information regarding a domain is in the form of examples. or instances. In contrast, the work at hand deals with characterising the hypotheses formable under a set of (arguably) minimal assump­ tions and hence is concerned with exploring intrinsic properties and limitations of such approaches. In addition. an extension of learning from examples to include learning by being told is addressed.

The work presented in [Morik 86] employs assumptions similar to those used here, in that very little is assumed about the domain of application. However. in this case the author is interested in the problem of acquiring an initial model of a domain, but presupposes an agent and learning algorithms to help in this initial investigation. Thus this work addresses the first step of a number of steps in a technique-specific approach to learning.

Most formal approaches to learning from examples have been concerned with inducing instances of a given type of formal language. The area of learning tlulory [Gold 67) studies systems that implement functions from evidential states to languages. A survey of such approaches is presented in [Angluin and Smith 82]. while [Osherson et el 83) gives recent results in this area. The key difference between such approaches and the present work is that no underlying formal grammar is assumed here, beyond that for elementary set theory.

2. Introducing Conjectural Information

2.1. Initial Considerations

The domain of application is assumed to be describable as a presumably infinite set of ground atomic formulae , formed from presumably infinite sets of individuals and predicates. At any point in time, the truth values of some subset of the ground atomic formulae are assumed to be known. Given a particular predicate then. all that can be known of it is a subset of those individuals (or tuples) which satisfy it and a subset of those individuals which do not. A predicate will be referred to as known if its truth value on a given individual (tuple) is known or can be determined. An individual will be referred to as known . if it is known to be or not be part of the extension of a known predicate. Informally. a known individual or predicate is one "encountered" by a learning system. The sets of tuples known to belong to the extension of a predicate and known to not belong to the extension are referred to as the known exten­ sion and the known antiextension respectively. So for a known n-place predicate P and known individuals a 1 , ··· , a. there are three possibilities:

1. P(a1, ... ,a.) is known to be true.
2. -.P(a1, . . . , a.) is known to be true.
3. Neither P(a1, . . . , a.) nor -.P(a1, ... , a. ) are known to be true.

Definition: For each known predicate symbol P define sets P+ and P_ by:

P.=l<al · · ···an> I P(a1, ··. , a.) isknowntobetrue}. P_=(<al, ... ,a. > I-.P(a1, .. . , a. ) is known to be true} .

Thus. to this point. the pair <P · . P_> expresses all that can be known about predicate P.

Conjectures are expressed in a language HL that is analo­ gous to that of elementary set theory except that. for contrast. operators and relations are subscripted with the character "h". Most of the subscripted symbols are familiar: however "I,. · is used for the (hypothesised) disjointness relation. and "a;/. ·.,.·. and "T/ for the converse. composition. and image operations. Note also that we will later distinguish the hypothesised equal­ ity of terms of HL. "=,. ", from strict equality of terms."=".

Definition: If P is the set of known predicate names. then the terms of HL are exactly those given by:

1. If P E P then P is a term of HL.
2. If 01, /3 are 2-place terms and y a 1-place term of HL. then « 1101, 01·11 /3 . and 01T11y are terms of HL.
3. If 01 and f3 are terms of HL. then so are 01n 11fj. 01U11 fj. and -.,.01.

Definition: The sentences of HL are exactly given by:

If 01. /3 are terms of HL. then 01=11/3. 01C11/3. ar=.,.(3. 011 11 /3 . 01~/3 . aft./3. 01~/3. 01!/3 E HL.

So. for example.

RiverU 11UzlceU ,.Sea r:.,. Geo_Feature

has the reading "the set of rivers. lakes. and seas is hypothesised to be contained in the set of geographical features" while

Uncle =11 (Brother.,.Parent) u,. (Husband.11Sister·,.Parent)

is the familiar definition of uncle.

The known extension and antiextension of a known predi­ cates are. by definition. known. From these. the known exten­ sions and antiextensions of general terms in HL can easily be determined. rhus. for example. the hypothetical intersection of P and Q is known to contain just those elements that both P and Q are true of. and is known to not contain just those elements that either P or Q is known to not be true of. For the hypothesised operations we obtain the extension/ antiextension pairs:

Proposition: ·

Complement:

.. ,.p is <P_, P.> .

Intersection: Pn,.Q is <P.nQ · . P_UQ_> .

Union:

PU,.Q is <P.uQ ·. p_nQ_> .

Converse:

« 11P is

<(<y.x>l <x.y> EP.}.(<y.x>l <x.y> EPJ> .

P T,. Q is

<(yl (3x)( <x.y> EP+ II x EQ.)}, ~>

for binary relation P and one-place predicate Q.

Composition: p.,.Q is

Image:

These operations generalise easily to ternary and higher-order predicates. Other operations. including domain and range. may clearly be defined in terms of these.

All that can be known about a term of HL is the known extension and· antiextension. On the basis of these sets we want to form conjectured relations between terms. Now. naively. iwo terms of HL may be conjectured to be equal when there is some reason to do so (i.e. some evidence criteria is satisfied) and there are no known counter:-examples. We obtain:

Definition:

for some "evidence function" f.

The only requirement that we place on I is that the intersection of a+ and 13. be non-empty . and that I be uniformly applied across hypothesised statements of equality . Conditions for con­ tainment and disjointness can also be easily specified:

Definition:

This approach to forming conjectures. of course. is hope­ lessly simplistic. For example. assume that SM means that one can supervise M.Sc. students. while SP and HP means that one can supervise Ph.D. students or has a Ph.D. (respectively). If all that is known is that

then if the evidence function I were simply equal to unity. we would have. according to our naive criteria:

This clearly is . inconsistent. A potential solution to this difficulty is to determine the truth values of select ground instances. where both the predicate and the individual are known. but where the truth value of the ground instance is not known. Thus. if HP(Mary) was determined to be true. then SPC 11 HP could be formed ; if HP(Mary) was determined to be false , then HP =,. SM could be weakened to HP c,. SM.

These considerations seem to imply that on occasion we need to be able to determine the value of some P(a1, ... , an). provided that P and a1, .·· , an are known. However, in general we would not want to determine the truth values of all known predicates applied to all combinations of known individuals. The reason for this is combinatorial: given p known n-place predicates and m individuals. there are pmn knowable ground instances. In the approach to be described. at most p(p-1 ) of these combinations need to be known for hypothesising relations.

While the previous example produced an inconsistency. we also may obtain hypothesised statements that are weaker than would be expected. Thus. according to the naive criteria. is is quite possible that there is evidence for a=,. /3 but not for .. ,.01 =11 -.,.(3. As will be seen. this difficulty cannot be rectified in any system based on our initial assumptions. So three questions arise:

1. How can "select · ground instances be determined for the· restoration of consistency?
2. How can we characterise the conjectures to which such a procedure for restoring consistency can be applied?
3. Given that the relations among hypotheses are weaker than the relations among corresponding statements of elemen­ ·tary algebra. in what ways are these relations weaker?

These questions are answered in the next two subsections by examining the algebra of the known extensions and antiexten­ sions of terms of HL.

2.2. An Algebra for Forming Hypothe~e~

Two terms of HL are defined to be (strictly) equal when their known extensions and antiextensions coincide. Containment ( ~) is introduced by the usual definition. Hence:

Definition: For 01, fj terms of HL.

The resultant algebra HLA is given by HLA - (H; ... ,.. n,. . u,.). where the carrier H is:

for a set of known individuals I. The pair of elements in an ele­ ment of H corresponds to a possible known extension/antiextension pair. Upper and lower bounds of H are given by:

Definition: 1 = <1.0> 0 = <0.1>

We obtain the following postulates:

Postulates:

• P2 anh(l3n.y) = (anhl3)nh'l' aUh(I3Uhy) = (aUh(3)Un'l'

• P8 01 = ... h ... hOI
• P9 -.h(aUhl3) = .... anh-.h13 ... h(anhl3) = -.hau .... hl3 PlO anh ... ha ~ I3Uh-.hfj

These postulates very nearly. but don't quite. characterise Boolean algebras. Instead of a postulate for a universal comple­ ment.

we obtain the weaker "Kieene" postulate PlO. However we retain postulates governing universal bounds (P7) and involution (P8) as well as De Morgan's laws (P9). The weakened comple­ ment arises from the fact that the known extension and antiex­ tension of a predicate typically do not together constitute the set of known individuals I. This algebra has been investigated under the names of normal involution lattices [Kalman .58) and Kleene algebras [Kleene .52).

To further characterise the conjectures. the propositional logic corresponding to HLA is derived in [Delgrande 8.5). and soundness and completeness results are obtained. An alterna­ tive. three-valued semantics for the logic is also provided. This development is not repeated here. However. it is worth noting that. unsurprisingly. negation in the logic. HLL. is weaker than in classical propositional logic: we lose reductio ad absurdum as a method of proof; also we lose the law of the excluded middle. Finally. it may be noted that HLL appears in [Rescher 69) as the system s;. However this system is mentioned only in passing. and no results concerning it are provided.

2.3. Restoring the Consistency of Hypotheses

This section examines how the consistency of a set of con­ jectures can be enforced and maintained in the face of contl.icting ground instances. The maintenance of consistency relies of the relationship between the naive criteria for forming conjectures in HL and conditions for equality of expressions of HLA. Consider for example the criteria for hypothesised equality:

and contrast it with strict equality:

For hypothesised equality we are not guaranteed. for example. transitivity of equality. So if we have P=hQ and Q=hR we are not guaranteed P=hR. For strict equality we of course have transitivity.

Now. in order to have asserted P=hQ. there must have been some set of individuals e which provided evidence for this hypothesis. Clearly. these instances will either also provide evi­ dence for P=hR (i.e. will satisfy the naive criteria). or if not, will refute both P=hR and Q=hR. and so. in any case. consistency can be restored. We can use a similar procedure for restoring the consistency of any set of hypotheses which should imply a cer­ tain conclusion in HLA but. for a particular case. do not. We obtain:

Theorem: Let a 1, ...· a ·. a E HL and assume a 1, . .. , a. have been hypothesised according to our naive criteria. and a is derivable from a 1, · . . , a. in HLA. Then ground instances can be determined from the set of confirming instances for a 1 , . . . , Oln that will either

1. refute one of a 1, . .. , a. or
2. allow a to be hypothesised.
3. allow some a' to be hypothesised where a' implies a in HLA.

Outline of Proof: Let the sequence of steps in a proof of a from a 1, . . . , a ·. be ~ 1 · ..· · ~m where ~m=a. I show that if there is evidence for ~ 1 ·... , ~;for 1 ~i<m then there- is evidence for ~i+l· or one of the original premisses. a 1 , .. . , a ·. can be falsified. "Evidence" is defined to consist of any metric that obeys the naive criteria of section 2.1. Since a proof is a sequence of steps from original premisses to desired conclusion. the theorem follows immediately. Note that it does not matter which proof of a from a 1, . . . , an is selected.

Alternative 3 in the theorem takes care of a "glitch" in the relation between strict equality and hypothesised equality of terms of HLA: hypothesised equality requires that the extensions of the terms in _question have a non-empty intersection. whereas strict equality simply requires that the extensions and antiexten­ sions coincide. Thus it is possible to have P=hQ. based on a set of individuals e. However such a set of individuals will not satisfy the naive criteria for -.hP=h-.hQ and so in this case we cannot use e to provide evidence for -.hJ>=h-.hQ. This is despite the fact that we can prove -.hP=-.hQ from P=Q in HLA.

The theorem guarantees for example that if we can hypothesise that

then we can locate individuals and predicates that will. via our criteria for evidence. allow the conclusion A !:hD to be hypothesised. or else will refute one of the premisses.

The proof of the theore,m is constructive, and leads immediately to a procedure whiCh will either locate evidence for a conjecture a that follows from supported premisses a1, . . · , a ·. or else will refute one of a1, .. . , a · . In the third alternative for the theorem. a specific sentence a' of HLA which . implies a is identified. The procedure is linear in the length of the proof of a. Since the evidence required for the naive criteria for forming conjectures is drawn from finite sets of individuals and relations. consistency can thus be restored in a set of conjec­ tures by repeatedly applying this procedure. Moreover. if we begin solely with a set of ground instances we will. by repeated application of our naive criteria for forming conjectures together with this procedure. arrive at a set of consistent conjectures.

This resolves the three questions posed at the end of section 2.1. First. the procedure derived from the above theorem shows how instances can be located for the restoration of consistency. Second. the conjectures to which the procedure can be applied are those that are governed by the postulates of HLA. Thirdly. then. the conjectures to which the procedure may be applied correspond precisely to the sentences of elementary algebra

(including composition. the converse. and the image). except that we do not have a universal complement. Moreover. this limita­ tion is unavoidable in this approach (or any approach based on the five assumptions listed in the introduction). However. we do retain involution. De Morgan's laws. laws concerning universal bounds. and the "Kleene" postulate.

3. HLA. Boolean Algebra. and Naive Set Theory

This section describes an extension to the approach wherein entities in the domain whose extensions are completely known are also considered. So far I have assumed that for a particular predicate in the domain. such as Red. only part of the extension and part of the complement of the extension can be known. The set of all red things (i.e. the extension of Red) cannot wholly be known by a learning system. While this seems reasonable for things such as Red. Bird. and Left_of, in other cases it is unrea­ sonable. For example. I may know that a particular stack of blocks is composed of the blocks (s1, ... ,sk}. In this case we could perhaps name this set stack Stackl and so Stackl = (s1, .. . ,sk} . The crucial point here. of course. is that all the members of Stackl are known. in contrast to the membership of Red, which cannot be completely known. Sets such as Stack!. whose extension is known, I will refer to as reducible. Sets such as Red, whose extension cannot be wholly known. I will refer to as irreducible. Reducible sets. clearly. correspond exactly with the familiar notion of "set". In this paper though I will be concerned only with sets with a finite extension.

So there are two questions of interest:

1. How can we formally characterise the irreducible sets?
2. How do the reducible and irreducible sets interrelate?

These questions are addressed by giving a set of axioms to characterise the set of allowable reducible and irreducible sets. .For both reducible and irreducible sets. the axioms developed parallel those in the system of Zermelo-Fraenkel [Fraenkel et al 73]. We obtain:

Notation:

The letters a. b. c. · · · will stand for reducible sets. The letters A. B. C. · · · will stand for irreducible sets. The letters · · · . x. y. z will stand for either reducible or irreducible sets.

Set Axioms:

Existence:

1. If aE I UP, (a} is a set.
2. ii) If a. b C IUP and anb ;:e 121 then (a. b) is an irreducible set.

Extensionality:

1. (a)(b)(x)(xE a= xE b)::::> a= b
2. ii) (A)(B)(x) ((xE A+ =: xE B+) A (xE A_=: xE B_)) ::::>A = B Pairing: (x)(y)(3a)(z)(zE a= (z=x V z=y))
3. Sum:
4. (a)(3b)(x)(xE b = (3c)(xE c fl cE a))
5. ii) (a)((3D)(DE a) ::::>

(3B)(x)[xE B+ ::

• CC3c)(xE c fl cE a)V(3C)(xE C+ACE a))]­ fl. [xE B_ = ~(3c)

((xE c fl cE a) fl (C)(xE G_ACE a))])

• iii) (A)(3C)(x)([xE C+:: (3B(xE B+fiBE A+)

V (3b)(xE bAbE A+))] fl C=IZI)

Power Set:

1. (a)(3b)(c)(cE b = cCa)
2. ii) (A)(3B)(c) ((cE B+ :: cCA+) A (cE B_ :: (cC(A+ UA_) A dtA+)))

Separation:

1. (a)(3b)(x)(xE b = iE a fl O'(x)) forb not free in 0', and 0' reducible or irreducible.
2. ii) (A)(3B)(x)((xE B+ :: (xEA+ A O'(x))) A (xE B_:: (xEA_ V ~O'(x))))

forB not free in 0', and 0' reducible or irreducible.

Regularity:(a)(a;:e!ZI ::::> (3x)(xE a A (y)(yE x ::::> y~a))) where for x irreducible. yE x means yE x+.

The axioms for irreducible sets are derived from intuitions similar to those motivating the axioms for the reducible sets. For extensionality. for example. we would want to say that two irreducible sets are equal just when their known extension and antiextension coincide. For the power set axiom. for every irreducible set A we know that the power set of A must contain the power set of A+: moreover. this is all that can be known to be in the power set. On the other hand. any set of elements not contained in A+ cannot be in the power set. and hence are in the antiextension. [Delgrande 85] contains an informal discussion and development of the other set axioms.

The axiomatisation then provides a set of constraints that bound the irreducible sets and. moreover. specifies how they may interrelate. As well it provides a primitive basis for defining and justifying the hypothetical operations of the previous section. For example. it is easily shown using the axioms of separation and extensionality that:

Theorem:

(A)(B)(3C)(x)((xE C+ :: xEA+ fl xEB+)

A (xE C_ = xEA_ V xEB_)) and Cis unique. So for any two irreducible sets there is a third set whose known extension consists of elements common to the known extensions of the first two sets and whose known antiextension consists of elements in either of the known antiextensions of the two sets. In addition, this third set is unique. This in turn justifies the definition:

Thus. AnhB is <A.nB ·. A_UB_>. The other hypothetical operations can be similarly defined. However. we can go beyond this. and consider what we would obtain from applying an operator to a reducible and an irreducible set. For example. for intersection we obtain:

Definition: A nhb = c iff (x)(xE c :: (xE b fl xE A+))·

Thus Anhb is the reducible set A+nb. Thus the result of inter­ secting a known set of blocks with the (irreducible) predicate Red is the subset of the blocks known to be red.

Lastly. we can consider an extension of the language HL where predicates that apply to sets of objects can be related to those that apply to only single (pairs of) objects. For example. the notion of hypothesised transitive closure is introduced into HLA in [Delgrande 85]. The system augmented by the transitive closure is general enough to allow for the expression of (the oft­ cited example of) an arch. Thus we can express hypotheses con­ cerning arches. for example. that a stack of objects is a set of objects that satisfies the transitive closure of the On relation and. conversely. any set of objects so bounded is hypothesised to be a stack. From this an arch could be defined as an object consisting of two pillars which are stacks. a lintel which is on top of the pillars where the pillars are not touching. and so on. The limita­ tions of the previous section of course still apply. and so any such hypotheses are bound by the relations of HLA.

The set axioms then provide a more primitive basis for forming conjectures and. additionally. expand the expressiveness of the system. However. while the set of allowable individuals has been vastly expanded, the form of the conjectures is unchanged. The formal results of the last section still apply and. since in the intended model the property of being an indivi­ dual is decidable. the· overall system remains decidable.

4. Learning from Examples and Learning by Being Told

ln this section I consider where we have a knowledge base (KB) that consists of an arbitrary. consistent set of sentences that the system has been "told" are true. We now want to form hypotheses from the ground instances. but also taking these other sentences into account. Since we require that the KB be able to reason about knowledge and hypothesis. this part of the problem either requires or presupposes a theory of incomplete knowledge. I have taken the latter course. and adopted the theory given in [Levesque 81). This work presents a logical language KL that can refer both to application domains and to what a knowledge base might know about such domains. KL extends first-order logic (FOL) by adding a sentential operator K. where Ka can be read as "a is known to be true". KL is extended here to a language called HKL that is able to deal also with con­ jectural sentences. HKL extends KL by the addition of a senten­ tial operator H. where Ha can be read as "a is conjectured to be true". Using HKL we can express sentences such as "John or Bill is hypothesised to be a teacher" or "it is known that Mary is hypothesised to be a teacher". HKL is specified as follows:

Axiom Schemata

1. The axioms of FOL
2. Ka. where a is an axiom of FOL
3. K(a::::>/3) ::::> (Ka::::>K/3)
4. a:=Ka where terms of a are within the scope of a K or H
5. (x)Ka ::::> K(x)a
6. Ka :::> ( ~Ha A ~H-.a)
7. K(a::::>/3) :::> ( -.K/3 :::> (Ha::::>H/3))
8. H(a::::>/3) ::::> ( -.K/3 ::::> (Ka:::>H/3))
9. H(a::::>/3) ::::> ( -.K/3 ::::> (Ha::::>H/3))
10. ((x)(Ka V Ha) A (3x)~Ka) ::::> H(x)a

Rules of Inference - Modus ponens and universal generalisa­ tion

The first five axiom schemata and the rules of inference are those of KL We obtain that knowledge and conjecture are closed under modus ponens (3. 7, 8. 9). and meta-knowledge is complete and accurate (4). Also if something is known. neither it nor its negation is conjecture (6). and generalisation applies analogously to conjecture and knowledge (5. 10). What this extension from KL to HKL buys us is a means of distinguishing and reasoning with sentences known to be true. from those that are only hypothesised to be true. In [Delgrande 85] an extension of the soundness and completeness results of [Levesque 81] (with respect to a possible worlds semantics) is provided.

HKL seems to have reasonable properties with respect to reasoning deductively with knowledge and hypothesis. There is a problem however with updating a KB (i.e. with "telling" a KB a new sentence). Consider where we have a known portion. KBt. of the KB and we want to form a hypothetical component. KBh. based on the known portion. Basically we want to "apply" HL to this KB to produce a hypothesised component. Thus for example if KB, is

then applying HL to what is known about the ground instances could yield:

or the equivalent hypothetical KB in HKL

The basic idea is that KBk. which is expressed in HKL. determines a set of ground instances and a set of sentences that are representable in HL By applying the procedure of section 2.3 for restoring consistency to these sets we obtain a set of hypotheses expressed in HL If KB = [KBt . KBh]. where initially KBh = 0 then we have the following procedure for forming a hypothetical component.

1. Let G ={gIg is a ground atomic formula and KBkf-­ HKrgl .
2. Apply the procedure of section 2.3 to G to obtain a consistent set of conjectures C expressed in HL
3. Let KBh be the translation of the sentences of C into sentences of HKL: exclude any of those provable in KB, .

There is generally a straightforward translation of sen­ tences from HL to HKL and, given this. the above procedure can be constructed in a straightforward manner. However it proves to be the case that unless KB, is equivalent to a set of ground instances. this procedure may result in inconsistency. The difficulty is that the procedure of section 2.3 relies on the existence of knowable ground instances whose truth value is unknown. However in first-order logic. and so in HKL. it is pos­ sible to attribute a property to an unknown individual. and this attribution may lead to inconsistency here. For example. con­ sider where all that is known is

Hence. for the corresponding relations in the domain. either P¢Q or R¢S. If we apply the procedure for restoring consistency to the known ground instances and sentences that can be expressed in HL. we obtain

which. of course. when translated into HKL. is inconsistent with the origina,l sentences.

While this last result appears somewhat limiting. things in practice may not be too bad. Several considerations are relevant. First. the assumptions underlying HL are those that presumably underlie any system that learns from examples. Hence the prob­ lems addressed here arguably are the problems that must be addressed by any system that learns from examples. or else must be discharged by means of a priori decisions by the system designers. Second. while applying the procedure to a general KB may lead to inconsistency. it need not necessarily do so. :If it does. it may be possible that pragmatic considerations can be used to resolve or skirt a particular inconsistency.

S. Comparison with Learning Systems

This section compares the present approach with related work on learning from examples. Three systems are particularly relevant and serve to place the present work within the field. The early work of John Seely Brown [Brown 73] on automatic theory formation is a direct precursor to mine. Patrick Winston"s dissertation [Winston 75] on learning structural descriptions from examples is a well-known early AI learning system and serves as a good representative of approaches to learning from examples. Ehud Shapiro"s work [Shapiro 81] is similar to mine in broad outline. except that the author makes substantial assumptions concerning how the domain of applica­ tion is described.

The task of Brown·s system is to propose definitions for a set of binary relations based on knowledge of the extensions of the relations. The system begins with a set of binary relations R = {R 1 .... , Rnl and a database containing the complete exten­ sion for each R,E R. Hence there is no notion of modifying a definition in light of later knowledge. A procedure is given for proposing definitions of the relations. However the body of a definition is restricted to be the disjunction of compositions of relations. This format though is adequate for a variety of domains. including that of kinship relations. The system is heuristic and was intended for direct implementation. Thus it dealt with matters such as efficiently searching for possible definitions. proposing definitions in a "simplest first" manner. etc. No analysis is carried out with regard to what may be conjec­ tured. nor is an algorithmic analysis of the system given. In contrast I have not addressed implementation issues. but rather have attempted to address general problems of hypothesis for­ mation . and thus issues dealing with characterising a set of con­ jectures and maintaining the consistency of a set of conjectures.

Winston's work was briefly described in the introduction. Basically Winston is concerned with the pragmatic aspects of a learning system, and concentrates on techniques to speed the learning process. In some sense then his approach is complemen­ tary to the one taken here. The system of section 3 subsumes the conjectures that may be formed in Winston's system: thus anything that can be formed in his system can also be conjec­ tured in HL. (Winston actually gives a semantic net representa­ tion for his concepts. This representation however is clearly equivalent to a set of binary relations. and is useful mainly as a notational or implementational device.) However, in HL the set of formable conjectures and the means of restoring consistency are precisely laid out whereas Winston does not address these issues.

Shapiro's work is. superficially. the most similar to that presented here. Shapiro assumes that a domain is described by a stream of ground instances: based on the ground instances. a set of conjectured axioms for the domain is proposed and refined. A general. incremental algorithm for proposing a set of rules which imply the known ground instances is developed. The algorithm has tuneable parameters that determine the complexity of the structure of a hypothesis. The key difference between Shapiro's work and the work at hand· is that Shapiro makes substantial assumptions about the way the domain is described. In particu~ Jar, the domain is assumed to be describable by a set of rules in the form of restricted Horn clauses. In addition the user is given some control over the form of the hypotheses. These assump­ tions allow an elegant algorithm for inducing rules for a wide class of problems to be derived. In the approach at hand. in con­ trast, the emphasis is on what may potentially be formed. rather than what can efficiently be induced.

6. Conclusion

This work develops a formal. unified. and general (but basic) framework for investigating learning from examples. A primary goal was to keep the approach as general as possible and independent of any particular domain, representation scheme. or set of learning techniques. Hence, for example, there is no res­ triction placed on the ordering of the ground instances nor is there any assumption that the input examples have been already aggregated into complex entities such as arches. Neither is there any restriction with regard to introducing new ("known") predi­ cate names during the learning process. Also, no agent is assumed to exist. to help direct or focus the acquisition process.

Presumably the issues addressed here are common to. and are relevant to. -any system for learning from examples (at least any system that satisfies the five assumptions given in the intro­ duction). Hence the framework may be appropriate as both a basis for the development of systems that Jearn from examples, and perhaps as a neutral point from which such systems may be viewed and compared. However only a set of formal issues have been addressed. and the concern has been with what conjectures may potentially be formed. rather than with which of those con­ jectures should in fact be held. Pragmatic issues concerned with the justification of conjectures. strength of evidence, and degrees of confirmation. to name just a few, are outside the scope of this work.

Formal systems are developed for introducing and main­ taining the consistency of conjectures. An exact specification of what conjectures may potentially be formed is provided, and it is shown how the consistency of a set of conjectures can be restored in the face of conflicting instances. The system illus­ trates that a reasonably rich and expressive set of conjectures can be derived using only a minimal set of assumptions. Two extensions to the system are described. First the system is aug­ mented to allow relations in the domain whose extension is com­ pletely known; to this end an axiomatisation of the (so-called) reducible and irreducible sets is provided. Also addressed is learning from examples, but where the system may be told arbi­ trary sentences in addition to the ground instances. The first extension does not affect the formal results previously obtained: the second is limiting. in that it may give rise to problems with inconsistency ihat have to be resolved by pragmatic means.

The expressiveness of the system is indicated by the fact that it is as at least as general as a number of existing systems. including [Brown 73], [Hayes-Roth 78] , [Vere 78]. and [Winston 75]. Results concerning decidability lend credence to the possi­ bility that learning systems based directly on this approach and, in particular. incorporating the procedure for restoring con­ sistency. may be efficiently implementable. In addition, given the generality of the approach. it is possible that the framework could also provide an appropriate starting point for an investiga­ tion of other types of learning systems. That is, the approach could conceivably be extended by incorporating further assump­ tions concerning the domain, underlying representation scheme. or an agent to assist in the learning.

The approach as it stands may have immediate practical applications. As a specific example. database systems often use integrity constraints to partly maintain consistency and reliabil­ ity. However. given a large number of relations. it is an arduous task to specify all integrity constraints and to ensure that the set is consistent. The approach then seems suited to the task of automatically proposing and verifying such constraints. This possibility is explored in [Delgrande 8 7].

Acknowledgement

This paper is based on my doctoral dissertation in the Department of Computer Science at the University of Toronto. I would like to thank my supervisor. John Mylopoulos. for his guidance , as well as Graeme Hirst. David Israel. and Hector Levesque. Financial assistance from the Province of Ontario and the Department of Computer Science, University of Toronto. is gratefully acknowledged.