Multiple Convergence: An Approach to Disjunctive Concept Acquisition

I Introduction

The learning problem addressed is concept acquisition from examples, as formulated in [MITC82). This entails developing a concept description to summarize training objects, each classified as a positive or negative instance of the target concept. The summary description is con­ strained to admit every positive instance and to reject all negative training. These are called the completene"" and con3i3tency requirements [MicH83). The concern of most machine learning research in inductive concept acquisition has been the determination of characteridic de,criptionJ, which represent concepts by summarizing the properties that hold true for all instances of the concept [DIET83]. Characteristic descriptions are typically encoded as a sin­ gle conjunction of maximally specific features.

A. Classical Concepts

Cla,,ical concept de,criptionJ are composed of features that are individually necessary, and jointly sufficient, for classification of objects as concept instances [SMIT81). Be­ cause of their single-conjunction form, the characteristic

descriptions produced by most existing concept acquisi­ tion systems resemble classical concept descriptions.

· Support for this research was provided in part by the Army Research Office under grant number ARO DAAG29-84-K-0060.

Multiple Convergence:

An Approach to Disjunctive Concept Acquisition ·

Kenneth S. Murray

Department of Computer Sciences The University of Texas at Austin Austin, Texas 78712

Unfortunately, a single conjunction of necessary and sufficient features is not suitable to represent many con­ cepts in natural domains. Figure 1 illustrates this with a simple example of learning about trees. After two posi­ tive training instances, a classical concept description is adequate. However, when a negative instance is encoun­ tered, the existing classical description is found overly­ general and must be refined into a disjunction. No single conjunction can satisfy both the completeness and consis­ tency requirements for the given training and language.'

Learning systems that produce only classical concept descriptions reflect the assumption that concepts are in­ dependently 3eparable. A concept is independently sepa­ rable when the independent determination of admissible values for each feature is sufficient to distinguish all pos­ itive instances of the concept from all negative instances. Concept acquisition under this assumption can be charac­ terized by the following two steps:

1. for each attribute, find the set of values valid for the target concept
2. take the cartesian product of all sets defined by step 1

This approach fails when the attributes of the target con­ cept interact, and the values allowed for an attribute in one context may not be valid in another. Unless all neces­ sary feat ural correlations are present in the representation language, a system limited to classical concept descrip­ tions cannot learn these concepts.

CONCEPT TO BE LEARNED: tree

REPRESENTATION LANGUAGE:

TRAINING:

instance 1: poBitive; [leaf, apple]

characteristic summary: [lea/, apple)

instance 2: poaitive; [needle, cone)

characteristic summary: [foliage, aeed)

instance 3: negative; [need/e ,pear)

characteristic summary: [/ea/, apple) OR [needle, cone)

Figure 1: Learning About Trees

B. Disjunctive Concepts

Disjunctive concept descriptions are necessary when the representation language is insufficiently expressive to produce a complete and consistent classical description. This situation arises when either of two anomalies occurs:

1. incompletene$$ condition: a positive instance is en­ countered, but the concept description cannot be generalized to admit it without also admitting neg­ ative training
2. inconsistency condition: a negative instance is en­ countered, but the concept description cannot be specialized to reject it without also rejecting posi­ tive training

A disjunctive concept description resolves these dilemmas by relaxing the completeness requirement for the individ­ ual· disjuncts. Each disjunct summarizes some subset of positive training while remaining consistent with all nega­ tive training. Collectively, the disjuncts satisfy both com­ pleteness and consistency. Identification using disjunctive concept descriptions requires classifying an object as an example of the concept when any disjunct admits it.

II Multiple Convergence

Multiple convergence enables acquisition of character­ istic descriptions for disjunctive concepts. It differs from existing strategies in the way concepts are represented and how disjuncts are created and updated, allowing each dis­ junct to emerge as an independent concept representing a specialization of the target concept. Multiple convergence has been implemented in the learning system HYDRA.

A. Representing Disjunctive Concepts

Although the objective is to produce a complete and consistent characteristic description of the target concept, multiple convergence maintains a discriminant description as well as a characteristic description of each concept it learns. The discriminant description summarizes negative training and defines criteria that all instances of the con­ cept must necessarily satisfy. The characteristic descrip­ tion summarizes positive training and represents hypothe­ sized $Ufficient criteria. As with FocussiNG [BUND85] and CANDIDATE ELIMINATION (M!TC78j, concept formation pro­ ceeds as a bi-directional convergence: the discriminant description progresses from general to specific with nega­ tive training while the characteristic description general­ izes with positive training.

Disjuncts formed in the discriminant description are used to define the disjuncts of the characteristic descrip­ tion. Intuitively, the discriminant description identifies regions of the feature space that can accommodate a clas­ sical description. Each disjunct of the discriminant defines such a region. A characteristic disjunct (i.e. a single con­ junction of generalized features) is developed to describe the positive instances within that region.

This process applied to the example from Figure 1 produces discriminant description [foliage, seed] for the first two training instances. After encountering the neg­ ative instance, the discriminant description is specialized into three disjuncts: [foliage, apple), [foliage, cone) , and [leaf, seed). Each of these defines a region of the fea­ ture space that can currently accommodate a classical description. For each region, a characteristic disjunct is developed to represent the positive training within that region, producing the characteristic disjuncts [leaf, apple) and [needle, cone), as shown in Figure 1.

Each associated pair of disjuncts from the discriminant and characteristic descriptions defines a version space [MITC78] for a hypothesized specialization of the target concept. As the version space of each disjunct con­ verges, it defines a classical description of a generalized exemplar. The target concept is represented by the dis­ junction of the surviving set of generalized exemplars. In the example of Figure 1, two generalized exemplars repre­ senting deciduous and coniferous trees (e.g. [leaf,fruitJ and ·[needle, cone)) will survive the convergence induced by exhaustive training.

B. Updating Disjunctive Concepts

Positive training instances are allocated to every dis­ junct that can be consistently generalized to admit them (as in [IBA 79]). This is motivated from a desire to remain insensitive to training order. Rather than make arbitrary decisions that may require subsequent backtracking, all alternative hypotheses are maintained.

When the existing discriminant concept description is found to admit a negative training instance, it is replaced with a minimal-specialization. This involves specializing each disjunct only to the extent necessary to reject the training instance, and then retaining only those new dis­ juncts not more specific than some other consistent dis­ criminant disjunct . Typically, this will introduce one or more new disjuncts into the discriminant description, and unlike other similar techniques (M!Tc78, IBA79, BUND85], disjuncts that fail to cover any existing positive instances are retained to avoid subsequent backtracking. Disjuncts of the characteristic description that admit the negative training instance must also be specialized. Furthermore, the characteristic description may need to be extended with new disjuncts to summarize the positive training ad­ mitted by new discriminant disjuncts.

Specializing and extending the characteristic descrip­ tion are tasks that have required most inductive learn­ ing systems to reprocess all prior positive training (e.g. STAR (MICH83j, and extensions to CANDIDATE ELIMINATION [MITC78] and FocussiNG [BuNo85]). Under multiple con­ vergence, the reprocessing of prior training can be con­ strained to consider only a portion of the past positive training instances. This is achieved by indexing positive instances under the disjuncts that admit them [IBA 79].

Each discriminant disjunct, d, found to admit a neg­ ative training instance is specialized to a set S of one or more new disjuncts. The reprocessing of past positive training to develop new characteristic summaries can be limited to those instances admitted by and indexed under d. This follows since each new disjunct s in S is a special­ ization of d, so the instances s admits must be a subset of the instances admitted by d. Therefore only the instances admitted by d need be considered when developing the new characteristic summary for s.

Reprocessing all the instances of an invalidated dis­ junct is avoided by retaining a trace of the prior character­ istic summaries along with the positive training instances. A new positive training instance and the prior character­ istic generalization are indexed under each new character­ istic summary. As the disjunct "fills up" with positive training, an exemplar generalization hierarchy emerges. The exemplar generalization hierarchy is always rooted at the current characteristic summary of the disjunct, and its leaves are the positive instances admitted by the disjunct.

This data structure can be used to enhance reprocess­ ing required by an inconsistency condition. For each s in S, a new characteristic summary is developed during an all-paths traversal of the exemplar generalization hier­ archy associated with d. Each path can terminate when a node is either admitted by or disjoint from the new disjunct s. When a node of the exemplar generalization graph is admitted by s, then the node itself can be repro­ cessed as a positive instance, and all the actual instances indexed under it can be ignored. Similarly, if the node is completely disjoint from s, then all instances indexed under the generalization must be irrelevant.

The multiple convergence approach to learning dis­ junctive concepts has been implemented in the ·learning system HYDRA. An overview of the concept acquisition algorithm of HYDRA is presented in Figure 2, and the ap­ proach is illustrated by an example of learning a necessar­ ily disjunctive concept in Figure 3.

REPEAT Await the next training instance, TI ; IF T I is positive THEN for each discriminant disjunct d that admits T I do minimally generalize the characteristic summary of d to admit TI; IF T I is negative THEN BEGIN minimally specialize the discriminant description to reject TI; for each new discriminant disjunct rf do reprocess prior positive training admitted by rf to produce a characteristic summary for rf END; Display the discriminant and characteristic descriptions;

UNTIL the teacher is satisified.

Figure 2: The Learning Algorithm of HYDRA

III Extending the Representation Language

Disjunctive concepts are inherently taxonomic and in­ troduce new generalization hierarchies rooted at the target concepts. Each node of the new generalization hierarchy is a list of attribute-value pairs representing an instance or generalization in the feature space of the concept. Since every attribute is defined by a pre-existing generalization hierarchy, the new hierarchy of a disjunctive concept can be viewed as an orthogonal generalization hierarchy. The nodes of the new hierarchy represent useful correlations of features. The links define context-sensitive generalizations of the features . Upon the conclusion of a training session, dialogue with the teacher enables naming the useful nodes in the hierarchy. The named nodes are then elevated to the status of concepts. This process is illustrated by the example of Figure 3. The resulting orthogonal general­ ization hierarchy for this example is presented in Figure 4.

Shifting the generalization biases of representation lan­ guages used for inductive concept formation has been rec­ ognized as an important research topic, but previously · only techniques to weaken the existing biases have been developed, [BuND85, UTGo86]. This involves focusing the internal disjunction provided by a generalization hierar­ chy by inserting a new node to segregate valid from invalid values of an attribute. The new generalization hierarchies introduced by disjunctive concepts represent an entirely new source of bias for generalization.

The new generalization hierarchies introduced by dis­ junctive concepts can enhance subsequent learning tasks. For example, consider learning about the concept Italian­ Expor£3 after having already defined vehicle. If provided with positive training examples [pedals, handlebars) and [engine, handlebars), the new generalization hierarchy en­ ables immediate generalization to vehicle (i .e. Italy ex­ ports vehicles) . Without prior knowledge of vehicles, this training would lead to the more conservative (and incor­ rect) generalization [power,handlebars) .

IV Conclusion

Introducing disjunction into our concept descriptions broadens the class of concepts our systems can learn. Mul­ tiple convergence has the advantage of producing classi~al concepts when appropriate, but is also able to describe a concept as a disjunction of generalized exemplars. This becomes necessary when the representation language is in­ sufficiently expressive to produce a single-conjunct sum­ mary that is both complete and consistent.

Many existing learning systems cannot learn disjunc­ tive concepts because they assume the target concept is. independently separable. Multiple convergence puts only tentative faith in this assumption, allowing generalization operators to proceed as if it were so, but enabling rela­ tively graceful recovery when the assumption fails.

Often the generalized exemplars of a disjunctive target concept themselves represent worthwhile concepts. For example, while learning about the disjunctive concept vehicle, multiple convergence also defines the concepts bicycle, ~ailboat, motorized vehicle, car, motorcycle, and ~hip. Therefore, multiple convergence emerges as an ap­ proach to learning multiple concepts simultaneously. By defining a generalization partial-ordering over the new concepts, disjunctive concepts enable rich extensions to the representation language.

ACKNOWLEDGEMENTS

I would like to thank Joe Ross, Ray Bareiss and espe­ cially Bruce Porter for their many insightful and encour­ aging comments.