Analysis of an Extended Concept-Learning Task

ANALYSIS OF AN EXTENDED CONCEPT-LEARNING TASK

Richard M. Young, Gordon D. Plotkin (University of Edinburgh)

and

Reinhard F. Linz (University of Bonn)

Bruner, Goodnow and Austin (1956) descr ibe a "focussing strategy" for learni ng simple conjunctive concepts in a situation where the learner is shown a sequence of instances one at a time, each being an example or non-example of the concept to be learned. We consider the extension of this strategy to concepts in which the individual features are hierarchically structured, as is the case, for example, for the materials used by Winston (1975). The essence of the extended strategy is to represent an hypothesis by a pair of nodes in the hi erarchy, instead of just a single node. The "lower", more specialised node indicates the set of instanct:s that have already been inferred to be examples of the concept. The "urpcr", more abstract node indicates an inferred limit on how general the concept can be. Thus the nodes act as bounds between which the concept must lie, and represent respectively sufficient and necessary conditions for an instance to be an example of the concept.

We general ise thi s notion of an hierarch i cr~lly-structured feature by defining a description space (d-space) as an upper semilattice (D. ~. V), with a top element, T, sati:;fying a certain finiteness condition. We show that the Carte:;ian product of a nt11nbcr of these d-spaccs is itself a d-sp:.:ce. This provides us with a simple. uniform notation for rcfc;ring to concepts. instances and hypotheses.

We describe a simple nondeterministic algor ithm whi ch irupkments the "focussing stra tegy" for such a conjunctive descr iption space, and discnss aspects of its behaviour un the concept lc:~rning task ~ For example:

1. Due to the generality of the d-space idea. the algorithm dc:~ls uniforn.Jy with fea tures which in Winston's approach have to be treated as special cases. Predicates, relations (A SUPPORTS B), multi-valued dimensions (ORIENTATION) and tree-structured dimensions (SHAPE) all give rise to examples of a d-space.
2. Given appropriate assumptions, it can be proved (a) that the hypothesis generated by the algorithm is always consistent with the data, i.e. it includes all the examples ;_:;1cl excludes all the non-examples it has so far been shown, and (b) that given sufficient data, the algorithm c:orr<:ct ly learns the concept.
3. According to the algorithm, back-up occurs when the rc! ;;ti on between the lowe r and upper bounds is violated. The !owN node of a hypnthes is is ?.ffected only by pos itive exan1ples, and the upper node only by non-examples. This clarifies the role of negative iafo;·,nation and "near misses" in the concept learning. In p:Hticular, it can be shown that
4. . . Given a corpus of instances, the outcome of the k a;ninL! is indcp~ndent of the order in which they are pre::en tcd. Mnrcovcr ...
5. . .. If all the examples are presented before the i)On-ex~mpks , then th<:: learn ing is free of errors, i.e. the algorithm neve r needs to back up.

In the light of this analysis, we argue that Winston's program is il ·;df an attempt to usc a focussing st rategy to learn conjunct ive co!lccpts with hierarchically-structured features, and we clis<:uss var ious slwrtcomi ngs and issues not dealt

v:it.h in Win:;tnn's treatment.

REFl·:HENCES

Bruner. J. S., Coodnow, J. J. & Austin, G. A. A Study of Thinking . Wil ey, 1956.

Win ~: ton, P. II. Learning st ructural descriptions from r~a111plrs. In 1'. H. Wi11ston (Ed.}, The Psychology of Cumputer Visio11. McGraw .. llill, 1975.