Induction in an Abstraction Space: A Form of Constructive Induction

1. Introduction

The concept of abstraction has played an important and well-known role in artificial intelligence since the mid 1960's. The difficulty in making use of abstraction has al­ ways been the construction of an explicit mapping between the problem definition in the initial space and its definition in an abstraction space [1] . In this paper we report on the learning system MIRO which performs supervised concept formation in an abstraction space which is constructed by the process of deduction on rules composed of attribute­ value pairs. The mapping is exactly the set of proof struc­ tures used in this construction. It then performs induction over a language defined by the process of deduction rather than the language defined by the instances, to yield a new characteristic concept description. The set of descriptors (or predicates) which are consequences of this deduction is viewed as the abstraction space, the set of descriptors used to describe the instances is viewed as the initial space, and the set of proof structures is viewed as the mapping between the two spaces.

Stan Raatz Department of Computer Science Rutgers University New Brunswick, NJ 08903

This method can also be regarded as a form of construc­ tive induction in which "useful" patterns are encoded in the domain theory. However, we propose a strong form of deductive bias as a means of limiting the number of constructed descriptors. vVhile the concept description formed is not justifiable in the sense of explanation-based generalization (3,12], the descriptors from which it is com­ posed are justifiable.· The method is able to extend an incomplete domain theory with a set of rules that repre­ sent a disjunctive concept derived from a batch of training instances. These inductively derived rules may be used in the same way as the original domain theory, when a new batch of instances is presented, and can support incremen­ tal refinement of the concept.

We present empirical studies which yield evidence for the following conjectures about learning in an abstraction space (as opposed to learning in the initial space). First , such learning can be more efficient because the abstrac­ tion space can be by construction more compact than is the initial space. Both the Vapnik-Chervonenkis charac­ terization (16,17] of the complexity of learning from exam­ ples and our own studies suggest typical problems exist in which substantial speedup is expected. Second, learn­ ing in an abstraction space can reduce the number of fa.lse negative and false postive classifications because coinci­ dental patterns are filtered by the deduction process. We show evidence that a significant decrease in the number of misclassifications can be expected. The empirical stud­ ies mentioned are based on controlled, randomized, and exhaustive testing of many thousands of trials. This pa­ per is a summary version, prepared for this conference, of reference (4] which is available by request.

2. Construction of an Abstraction Space

In essence, the basic idea presented here is a two stage process: first, construct an abstraction space, and then apply an induction method over this space. We will de­ fine the method for domain theories of rules composed of descriptor-values and an induction method similar to the Aq algorithm (9], but it is important to emphasize that the concept of induction in an abstraction space is not restricted or dependent on these assumptions. We as­ sume that training instances are given in the initial space 1 = {0, 1}n and a specific instance xis given by a set

where for each x j E x ( 1 :::; j :::; l), x j is intepreted as descriptor x j is present in instance x and Xj is interpreted as descriptor x j is absent from instance x. For a set S = Pas UN eg of training instances, we say

is the initial concept de3cription language. Let Rr be the target concept and let the rule space n in which it is rep­ resented be all k-term-DNF formulae over L. vVe .refer to the learning problem in the initial 3pace 1 as the prob­ lem of forming a characteristic concept description for Rr using the descriptors in L.

Let D be a domain theory of rules composed of descrip­ tors as in

We assume that D does not contain a rule for deducing the "goal" concept Rr which characterizes the positive class. A bottom-up deduction procedure on the And/Or graph G D induced by D can be defined by the following rules: truth is propagated from node n 1 to node n2 along an Or­ edge in G D if n 1 is true, and truth is propagated from

nodes n 1 , . . . , nk to node m along an And-edge in G D if the nodes n 1 , .. . , nk are all true. Negation is represented by marking the edge from a negative literal as a negative edge and invoking a kind of negation as failure [2] rule: if a node labeled x cannot be marked true, then a node labeled x may be marked true, and that if a node labeled x can be marked true, then a node x cannot be marked true. Note that rules with negative consequents are not permitted in the domain theory. If instance x propagates truth to a descriptor x and the node labeled with x has no successor proven in the graph G0 for x, we say x is a maximally proven de3criptor, denoted x 1- x maximal.

Let

The set LA is explicitly con3tructed as a set of pairs con­ sisting of a descriptor x and the proof that established x. We let LA be the ab3tract concept de3cription language and refer to the learning problem in an ab3traction 3pace A as the problem of forming a concept description for Rr using the descriptors in LA. The set of proofs or proof structures is the mapping from the initial to the abstrac­ tion space often mentioned in the literature [1] .

Recently, the Vapnik-Chervonenkis (VC) dimension has come be recognized as a useful metric for estimating the number of training instances required to attain a nearly correct concept description (see [17] for details). For a finite rule space n, the VC-dimension d is given by d = logiRI as developed in Rivest [16]. Our representation is k-term-DNF over n descriptors. There are 3n possible 1term-DNF rules and

possible k-term-DNF formulae. Thus the VC-dimension is just

which is approximately k(nlog3 -loge) [4] . Let kA stand for the value of k in the k-term-DNF representation of the abstraction space, kr for the value of k in the initial space, nA for the number of descriptors in the abstract language LA, and nr for the number of descriptors in the initial language L. Thus if kA < kr and nA < nr, the expected improvement in sample complexity when d is large is

If Rr E Rr implies that Rr E RA, it is thus possible for the number of samples required to learn a nearly correct concept to be significantly smaller in the abstraction space

than in the initial space. It remains to be seen if learning problems exist which exhibit this behavior. In section 4, we present empirical results which validate this claim.

3. Overview of Inductive Component

The inductive component reported here is directly ap­ plicable only to theories of rules composed of descriptor­ value pairs, but illustrates topics that are applicable in other types of domain theories. The inductive stage is based on the one-sided variant [7] of the candidate elimina­ tion (or version space) algorithm [10]. Deduction provides a means of constructing a language L that is ju3tijiably bi­ aud, in the sense that abstract descriptors are deductive consequents of the set of instance descriptors. This bias is exploited to its fullest if only maximal descriptors are admitted into L, and all instance descriptors are excluded. However, a maximally biased L may not be adequate for inducing a discriminant concept, even though the instance language is adequate. Since we cannot adjust the amount of bias in advance but prefer to use the strongest possible bias, we require an unbia3ed inductor capable of generating all discriminant concepts in L consistent with the training set. Candidate elimination is an efficient algorithm that meets this requirement. The algorithm is applied to a seed x. E Pas and to all negative instances to yield a set G of discriminant concept descriptions. Each element of G is a conjunction of descriptors drawn from a concept description language and an element of G covers a sub­ set of Pos including the seed. In general, this is a partial concept description that covers a subset of Pos , the posi­ tive training set. In case an empty G set is returned, one non-maximal descriptor is selected by a heuristic similar to Quinlan's decision tree heuristic [14] and added to L. This may be repeated until a nonempty G is returned, and a single conjunction C is selected that covers a subset of the positive instances. Select ion from the G set depends on a heuristic measure of credibility [15] which balances the number of instances covered by a conjunction with an extra-evidential component that measures the amount of domain knowledge in the proof structure of each instance.

In order to obtain a characteristic partial description, each discriminant partial description is specialized by the addition of descriptors from an augmented language into the conjunction. The specialization entails a search guided by the same heuristic measure used to select an element from the G set. The instances covered by each partial characteristic description are then removed from the set Pos. A complete concept description is a disjunction of partial concept descriptions. Since we require a complete description, candidate elimination is applied repeatedly in order to construct a disjunction of terms. A new seed is used and one partial concept description is selected from the G set on each cycle. The algorithm terminates when either a complete description is found, or some positive in­ stances remain which have been tried as seeds and cannot

be discriminated from the set Neg. We summarize the method in pseudo-code as follows.

Construct abstract language LA. set characteristic concept description R +-- 0; set L to all maximal descriptors in LA ; do while Pos =/= 0 Choose a seed x. E Pas; set G +-- 0; Invoke Candidate Elimination on x. U Neg, returning general version space G; do while G == 0 if All initial descriptors are already in L then Fail: indistinguishable instances else Select a descriptor and add to L; Restart Candidate Elimination with new L; end; Perform search from G, returning conjunction C; set R +-- R V C; set Pas +-- Pas - { xjx E Pos, x covered by C} end;

4. Validation

A synthetic problem domain was invented that would exhibit sufficiently high dimensionality and disjunctiveness to represent difficult problems for a selective induction al­ gorithm. The domain represents household cooking imple­ ments (e.g. soup bowls, forks) with an instance language of

28 observable, structural features. Many of the interesting classes that are representable in this language share func­ tional properties (e.g. insulated against heat) that are not included in the instance language. We invented a domain theory of 36 rules that represents such a functional prop­ erty as the consequent of a rule, or chain of rules grounded in the instance language. These included four rules that could be interpreted as defining a class (glass , cup, plate, cooking vessel), but did not include any rules defining the target class for our learning experiments.

Training instances were created by pseudorandom me­ chanical generation of structure and features, in order to preclude the introduction of unconscious bias by the in­ vestigators. Several thousand rather bizarre objects re­ sulted, and these were screened and mechanically sorted into training classes by using a classification rule base that was unknown to the learning program. A total of 78 usable instances resulted, of which 30 "spoons" were chosen for a pool of positive training instances. All remaining instances were used in the negative pool. An average instance of "spoon" has 14 features, and an average instance of any type has 15 features . The target concept is exactly repre­ sented by an 8-term-DNF expression in instance space.

A single learning trial consists of choosing k, 2 ::::; k ::::; 20, positive and k negative training instances from each pool, running MIRO to give a set of classification rules (i .e. a characteristic concept description), and then testing that

concept against 10 positive and 10 negative instances cho­ sen randomly from each pool excluding training instances used in that trial. By varying k from 2 through 20 by 2 we obtain a series. Each point in an error rate curve re­ ported here is an average of 10 series. Figure 4.1 presents the false negative (solid line) and false positive (dotted line) error rates obtained in the initial feature space, using no domain theory. Here the false negative rate has not stabilized after 16 positive and negative instances, beyond which these trials often could not be completed due to ex­ hausting LISP virtual memory. This explosion of memory use is clearly visible from figure 4.2, which plots growth of the version space G set during candidate elimination. The independent axes are the number of training instances (horizontal) and the number of negative instances elimi­ nated (projection of a..xis perpendicular to the page). The dependent vertical axis shows the average size of G. We see clearly that induction is very underconstrained, owing to the highly disjunctive nature of the target concept when represented in the initial feature space.

100-

..,_

The following experiment defines the performance base­ line for MIRO in our synthetic domain, using a concept description language that was constructed as described in section 3 to exclude any initial descriptors. The resulting error rates in figure 4.3, now extended through 20 training instances , reach low plateaus far more rapidly. An aver­ age concept was observed to converge at 1-term 3-DNF around 4 training instances, and essentially no cases of G set collapse were observed. The effect of fully exploiting deductive bias is more visible in figure 4.4, which shows a slow growth in the G set as more training instances are used. These experiments suggest that an appropriate do­ main theory can reduce both the dimensionality and dis­ junctiveness of a learning problem, even though very little effort was made to engineer a "correct" or "complete" do­ main theory.

100-

..,_

5. Relationship to Other Work

The work reported in this paper is directly related to constructive induction as mentioned in the introduction, and to recent attempts to integrate explanation-based and inductive learning. However, there are important differ­ ences. Reference [4] also contains numerous other compar­ isons to work that is indirectly related, such as learning by analogy and various extensions to and uses of explanation­ based learning, such as [11] . Lebowitz [8] develops a sys­ tem UNIMEM which searches a database of voting records for empirical generalizations, and verifies these general­ izations via a domain theory. He proposes an inductive method that is used to control the search space for a ver­ sion of a deductive method. This work can be considered the dual of the work reported in this paper, in the sense that we use a deductive technique to formulate a situa­ tion for induction. However, the work is very different in details, is presented by example and explanation, and nei­ ther includes an algorithm nor empirical studies. Pazzani, Dyer and Flowers [13] describe a system OCCAM in which causal theories are preferred to correlational or inductive information in forming generalizations, which are subse­ quently used to suggest additional causal and intentional relationships. The work is also not directly related, since OCCAM does not have a uniform language that is used in both the deductive and inductive stages, that is, it is not actually a form of constructive induction. Flann and Diet­ terich [6] propose a general learning architecture that uses a multiple representation strategy: the system translates task training examples into a "natural" representation for induction and then translates the learned concept back into the appropriate task representation. The paradigm is illustrated by the system Wyl which learns concepts in board games such as checkers and chess. It is similar to the work reported in this paper because in Wyl all possible board positions consistent with a functional description of a concept in logic are constructively generated, but the architecture upon which vVyl is based appears to be more general.

6. Conclusions

We have presented evidence that induction defined over an abstraction space constructed via the process of deduc­ tion can result in substantial speedup for some induction problems, and that it is also possible for the number of false negative and false positive classifications to be re­ duced. In addition, it can be shown [5] that even with injection of 25% of attribute noise into the training set, the method presented here is able to construct a "cor­ rected" characteristic concept description, and that with certain "ad hoc" assumptions, the method can accept do­ main theories in the Horn subset of first-order logic.

7. References

1. Amarel , S., On Representations of Problems of Reason­ ing About Actions, in Machine Intelligence 3 (Michie, D., ed.), Edinburgh University Press, Edinburgh (1968), 131-171. Also, in Readings in Artificial Intelligence, Tioga Press, Palo Alto, CA, 1981.
2. Clark, K. , Negation as Failure, in Logic and Databases, Gallaire and Minker (eds.) , Plenum Press, NY (1978), 293-322.
3. DeJong, G. and Mooney, R., Explanation-based Learn­ ing: An Alternate View, Machine Learning 1:2, 145176, 1986.
4. Drastal, G. and Raatz, S. , Empirical Results on In­ duction in an Abstraction Space, Department of Com­ puter Science DCS-TR-248 Rutgers University, Novem­ ber 1988.
5. Drastal, G., Raatz, S., and Meunier, R., Error Correc­ tion in Constructive Induction, submitted to this con­ ference.
6. Flann. N. and Dietterich, T., Selecting Appropriate Representations for Learning from Examples, AAAI-86, Philadelphia, PA, 460-466.
7. Haussler, D., Bias, version spaces and Valiant's learning framework, Proceedings 4th International Workshop on Machine Learning, 324-336, Irvine, CA, 1987.
8. Lebowitz, M., Integrated Learning: Controlling Expla­ nation, Cognitive Science 10 (1986), 219-240.
9. Michalski , R., AQVAL-1, Computer Implementation of a Variable valued Logic System VL1 and Examples of its Application to Pattern Recognition, in Proceedings 1' 1 International Joint Conference on Pattern Recognition, Washington DC (1973), 3-17.
10. Mitchell, T., Version spaces: An approach to concept learning. Ph.D. thesis, Department of Electrical Engi­ neering, Stanford University, 1978.
11. Mitchell, T. , Toward Combining Empirical and Ana­ lytic Methods for Learning Heuristics, in Human and Artificial Intelligence, Elithorn and Banerji (eds.), North-Holland Publishing Co., Amsterdam.
12. Mitchell, T., Keller, R., and Kedar-Cabelli , S., Explanation-based Generalization: A Unifying View, Machine Learning 1:1, 47-80, 1986.
13. Pazzani, M., Dyer, M., and Flowers, M., The Role of Prior Theories in Generalization, AAAI-86, Philadel­ phia, 545-550.
14. Quinlan, J ., Induction of decision trees, Machine Learn­ ing 1:1, 81-106, 1986.
15. Rendell, L., A general framework for induction and a study of selective induction, Machine Learning 1:2, 177226, 1986.
16. Rivest, R., Notes on Machine Learning, unpublished draft.
17. Vapnik, V., and Chervonenkis, A. , On the uniform con­ vergence of relative frequencies of events to their prob­ abilities, Theory of Probability and its Applications 16, 264-280, 1971.