A Prototypical Approach to Machine Learning

ABSTRACT

This paper presents an overview of a research programme on machine learning which is based on the fundamental process of categorization.

A structure of a computer model designed to achieve categorization is outlined and the knowledge rep­ resentational forms and developmental learning associated with this approach are discussed.

Keywords: Learning, categorization, prototypes, knowledge representation.

INTRODUCTION

This paper gives an overview of the approach being taken to learning within a continuing research project. The project is concerned with developing an operational computer based model of learning,drawing on a psychological theory of categorization proposed by Rosch et al. (Rosch et al, 1976).

The type of learning that has attracted most attention in the A.I. literature is the learning of propositional rules about a given feature set to discriminate between categories (Michalski et al, 1983).

But the most difficult part of the work has already been accomplished when the relevant features for rule formation have been found. Further, these systems only deal efficiently with concepts naturally described in terms of conjunc­ tive features and do not respond kindly to 'noisy' data.

Following from this we feel it is necessary to develop a model of learning which addresses not only the questions of how to discriminate between categories using a given feature set but also the question of how such features are found. Efficient learning algorithms will depend upon the knowledge representation scheme upon which they operate: learning of logical rules fits naturally with a propositional knowledge base but not so well with an associative network knowledge base. We there­ fore decided to model the entire categorization process of knowledge representation, feature selection and discrimination as one integrated system. Because learning of categories influences the structure of knowledge in memory and this structure in turn affects higher levels of learning operating on it, studying categorization and re­ lated representations also has implications for

A PROTOTYPICAL APPROACH TO MACHINE LEARNING.

R. I. Phelps and P. B. Musgrove

Brunel University Polytechnic of the South Bank the operation of other types of learning. The development of a model for such an integrated system is a complex task and so a restricted domain of classification was chosen for this work. This is the domain of 2-D silhouettes of visual objects. Reasons for this choice are the primacy of visual perception in humans and the importance of recognition. A more detailed discussion of this approach are available in

(Phelps & Musgrove, . 1985a).

KNOWLEDGE REPRESENTATION

Some psychological evidence is available about the structure of categories. It has been argued that the most cognitively efficient and therefore most basic level of categorization is that level at which the categories produced provide the most distinct clusters, i.e. the level which maximizes the similarity of objects within a category and maximises the differences between objects in different categories. (Rosch et al, 1976) and (Tversky and Hemingway, 1984) provide evidence that this basic level of categorization is the most abstract level at which instances have similar shapes and parts and it is most abstract level at which a mental image (prototype) can re­ flect the appearance of the entire category.

The knowledge representation scheme adopted for objects and categories has been explicitly designed to fit in with the prototype theory, and is explained in greater detail in (Phelps & Musgrove, 198Sb). Marr's research in machine vision has taken the view that objects are most naturally segmented into convex parts (Marr 1982) and we have followed this line of thought but refined it so that parts need only be 'psuedo­ convex ' in the sense that further dividing them into more convex subparts does not significantly increase the measure of convexity. This approach is reported elsewhere in more detail (Phelps & Musgrove, in preparation).

The description of the visual image is achieved in stages. Firstly, the image is de-· scribed holistically by a set of descriptors in­ cluding such measures as principal axis, axis extension ratio, compactness (perimeter/area), size, etc., applied to the whole image (Barrow & Popplestone, 1971). The precise set of descrip­ tors used is unimportant as long as it contains a rough description of the shape. Only a rough description is necessary as more accurate descript­ ions are provided by successive stages. At the

I

(

second stage the image is decomposed into its primary subparts. Each subpart is now described by a set of descriptors, and the 'joins' between subparts are also stored. This process is now re­ peated to any desired number of stages, the sub­ parts being successively divided and described in increasing detail.

ESTABLISHING CATEGORIES

Features are extracted from the representa­ tional descriptions and used to measure similarities between the representations. These similarity measures position objects in a representational space wherein the objects are examined for the existence of clusters. Clustering of this type is only sen­ sibly considered if the objects under consideration are all roughly of the same type. Thus a cow and a horse both have bodies, necks, heads and four legs and so a similarity rating is conciev­ able. However, cow and a tomato are so different that to attempt to devise a similarity measure is pointless. Hence there is an initial need to determine which of a set of objects may possibly cluster together and which are definitely in separate categories.

The hierarchical description of objects gives the possibility of extracting features at differ­ ent levels of detail. The first features to be considered are those at the holistic level. These will often by themselves be sufficient to rule out two objects from membership of the same category, because of an extreme difference in one or more of the measures. At this stage we only sort out obviously unlike objects: we do not wish to re­ gard a man with arms raised as totally different from a man with his arms at his sides, but he

should be differentiated from a bus.

The next stage of the categorization process is the identification of potential category member ship at the level of part descriptions. This stage operates separately on each set of objects identified as a potentiai category at the previous stage.

We allow objects A and B to be potential members of the same category if we can find a sub­ set of parts of A and a subset of parts of B which match and which account for most of the area of images A and B. When such matched subsets are found, any contiguous set of parts not in the subset is fused into one 'lumped' part. It may then be possible to match lumped parts of A and B , in which case these matched lumped parts are

added to the matched subsets.

If potential categories have been identified then an attempt is made to discover actual cate­ gories within each potential set by means of cluster analysis.

Each object may be represented (in part sub­ set form) as a point in a representational space (pll. · ·P1n· · ·Pkl' · ·Pknrl2' · .rk-lk) where Pij is the result of a measure j applied to part i and rij is the relationship between parts i and .i · A clustering algorithm has been developed

which will seek any convex clusters present among these points. In particular this algorithm allows clusters to intersect, thus allowing for the fact that some natural categories may not have sharp dividing lines between them. Further, it does not require the number of clusters present to be set nor does it require the alteration of parameters to give good results on different data sets. In these ways it represents an advance in automatic cluster detection over other existing algorithms. Details of this method, which is designed to emulate human performance in detecting dot clusters, are described elsewhere (Phelps, 1985). This algorithm is used to explore the cluster structures found using different subsets of the part and relationship measures as the axes of the space. The objective is to find a minimal set of these measures which provides a 'good' cluster structure.

If the object vectors display clustering then in most cases this will be due at least in part to the different clusters displaying differences in their parts. Thus the search for object clusters can in fact be largely carried out by searching for clusters within corresponding parts of the objects (pil···Pin).

If at least one cluster is found, the objects within it are members of the same category. The outcome of the process at this or further stages of processing is a partitioning of the object set into (possibly overlapping) classes, each con­ talnlng category members or candidates for member­ ship of a category. However, the category struc­ ture information we seek is only contained in clusters of objects found via the clustering al­ gorithm. It is the set of measures used to find each cluster and the position of the cluster with­ in this space which provide the operational notion of categories. Objects in a class where no cluster has been found or which have been classi­ fied as 'noise' points are uncategorized at this stage.

The above stage of processing can be repeated on the next level of the description hierarchy, 'parts of parts', and again repeated at more detailed levels until the description hierarchy ends.

ILLUSTRATIVE ANALYSIS

As an example of the scheme outlined above, consider a set of four silhouettes: two horses, a cow and a bird (wings closed), These have been broken down into their primary convex parts, but these do not necessarily correspond to the parts which we normally consider these animals to have. For example, one leg may occlude another, so in the cow the two front legs are considered as one convex part. In the horses, the area at which the two legs merge into the body and into each other has been separated out as a convex part. The back legs and tail of the cow have merged and been split into three convex regions. The labels given to the regions are for illustrative purpose only - it is not known to the algorithm at this stage that the regions of the two horses here labelled 'body' both correspond to the same part of the concept 'horse'. [TABLE 1].

The bird may be immediately differentiated from the others because of the great difference in the number of parts found. The cow and horses cannot be immediately distinguished and so an initial attempt must be made to match their part descriptions. The best match of corresponding subsets can be made by matching the largest parts (bodies), the next largest (heads) and one of the next largest (necks), which triples preserve roughly the same relationships between their parts and account for around 0.75 of their areas. With these subsets matched the front junctions and legs of a horse are contiguous and would be treated as one lumped part, as would the rear junctions and legs. Similarly, the front legs and hooves of the cow would be lumped as would the 3 rear leg parts and hooves.

The three matched parts are now considered individually to look for clustering within each part. For the bodies, the major difference is in area between cow and horses, which might form a clustering characteristic with a larger sample. There is little evidence of clustering from the head measures. For the necks there is evidence of higher compactness, lower elongation and higher area measures for the horses which again might form clustering characteristics. The triples would now be examined in a space with axes chosen from , body area, neck compactness, neck elongation, neck area plus interpart relations, such as direction between part centres.

In fact for these three animals, using the above four part measures, there is a clear indi­ cation of difference between the horses and the cow indicating a probable cluster structure.

Average values of the objects in each cluster go to form prototypes. In this case the proto­ typical horse silhouette would consist of the sim­ plified representation: body, neck, frontlegs, hindlegs, tail, together with their average measures and relations.

TABLE 1

Horse 1

Cow

Robin

The 3 rows give measures of 1) compactness, 2) elongation 3) proportional area in each case.

CONCLUSIONS

This is an (extremely brief) outline of the approach we are taking to machine learning. Al­ though it is presently limited to simple visual categorization it is hoped that by studying learning at this fundamental level we will provide a foundation for models of higher level learning, and that principles of organizations that emerge in categorization will also be incorporated there.