Inductive Learning of Categories from Examples Using Minimum Cost Representations

1. INTRODUCTION

1.1 Motivation

Machine acquisition of concepts from experience is an important goal for artificial intelli­ gence . Knowledge bases, the primary source of limitat ion as well as power in "expert systems" should be able to grow and thus permit the sys­ tems to improve (2). The automation of this growth of system knowledge is then of obvious interest. In this paper we focus on a simpli­ fied learning scenario where the concepts are restricted to be categories.

1. 2 Past Work

The process of learning categories from exam­ ples has been studied from several different approaches including (a) trainable pattern classi fiers working with real-valued features [6) and (b) discovery of classification rules using variable-valued logic [5], and (c) for­ mation of structural descriptions in terms of known substructures [7). Here we discuss the learning of categories in the simple mathema­ tical framework of countable sets as is done by Lenat [4] so as to make clear some of the computational issues involved.

1.3 Problem Formulation

The kind of learning we wish to understand is the acquisition of new "concepts" (categories of ob jects) and the continual refinement of the representations for known categories as new examples of old categories are encountered.

For example, suppose a person Sue previously un­ exposed to computers is shown a personal compu­ ter and told "This computer, the ACME 1, is a home system". Sue should then know that there is a category "computer", a category "home system" and that the ACHE 1 is an example of each. She may a lso be able to infer tha t the category "home system" is included in the ca tegory "computer" if the context supports that infer­ ence , e.g. if she had previously been told "Let's discuss types of computers". After being s hown several more home systems she may under­ s tand "home system" to be the set {ACME 1, Apple 15, JETSETTER, ACME 2}. Suppose she is then t old that the following are " cheapo's": {ACME 1, Apple 15, ACNE 2}. Being unf amiliar with the computer domain, we would not expect Sue to be able to distinguish the cheapo's f rom the non-cheapo's except by using the infor­ mation she has been told. tf Sue is thinking, we would naturally expect her to infer that JETSETTER is an example of a home system that is not a cheapo. In fact, if she remembers which are the home systems, then she has an easy method for remembering the cheapo's in:

cheapo's = (home systems) - {JETSETTER}.

We would like computer programs to make similar inferences in the course of learning categories.

2. MINIMUM COST REPRESENTATIONS

2. 1 Representation Scheme

Given a se t S of natural numbers, a r epr esenta­ tion for S written R(S) is any one of the fol­ lowing forms (as applicable) and C(R(S)), the cos t of R(S), is as given. (1) if Sis known to be empty, then R(S) = {} and C(R(S)) = 1. (2) if Sis a singleton, then R(S) ={a.} and J C(R(S)) = 1. (3) if S is the extension of an initial predicate, then R(S) = {xiP.(x)} and J C(R(S)) = 1.

(4) if S is a union of two other sets, then R(S) = (R(S 1 ) u R(S 2 )) and C(R(S)) =

C(R(S 1 )) + C(R(S 2 )) + 1.

(5) if S is an inter­

section, then R(S) = (R(S 1 n R(S 2 )) and

a complement, then R(S) = (-R(S 1 )) and

C(R(S)) = C(R(S 1 )) + 1.

The cos t Qf S is the minimum cost over all rep­ resentations of S. Our cost function, while arbitrarily chosen, yields cost values that roughly reflect the amount of symbology neces­ sary to store representations.

2.Z Updating ~Single Category

The amount of the change in cost for assimila­ tion of a new fact is bounded (when only one category is represented).. The following propo­ sition describes the cost change for updating S to s' according to s' = s u {ai} where ai' s.

where C(X) denotes the cost of X.

As will become clear from subsequent discussion, when several categories are simultaneously rep­ resented, an incremental change in one may affect the total cost of representation beyond

the bounds of proposition 1.

3. COMPUTATIONAL CONSIDERATIONS

3.1 Computing Minimum Cost Representations

Even the problem of transforming a list repre­ sentation of a category into a minimum cost representation is a nontrivial problem in combinatorial optimization. The computational complexity of this and related problems of minimum cost representation is of interest becaus e the high cost of such processing illus­ trates the subtlety in learning even simple concepts.

3.2 Multiple Categories

Suppose that there are initial predicates P 0 , ... , Pk and existing categories s 0 , ... ,Sm. Given a new category Sm+l we wish to find a minimum cost representation for {S 0 , ... , Sm+ 1 }. One approach is to find a

minimum cost rep. for Sm+l in terms of the rep's.

for s 0 , ... ,Sm. However it is ~ossible that the rep's. of some or all of s 0 , ... , Sm should change with the assimilation of sm+ 1 . We shall address this subsequently.

As we permit LS to handle multiple categories we need an additional representation form: R(S) = R(S 1 ). However we now must modify our cost rules so that any given category only gets charged once.

C(R(S)) = the number of occurrences of all of

the following in R(S):

and S is any category whose representation is charged separately. Note that the assimilation of new information may require changing repre­ sentations for old in"rormation.

3.3 Circularity in Representation

As category representations are updated, care must be taken to avoid circular representations . If at time 1 we have s 2 represented as or in terms of R(S 1 ), then we may not at a later time (2) change tfie representation of s 1 to be in terms of s2 unless s2 is first made . ~dependent of Sr. Prevention of circularity may be handled by maintaining a partial order on the categories, implemented as a directed acyclic graph. The algorithm below builds the repre­ sentation for a collection of categories in a non-circular way by representing the simplest (least costly) categories first and building up to "inherently costly" categories (those that would be expensive if expressed independently of other categories), thus progressiving through a "topological sort" of the partial order.

3.4 Brute-force Method

The "exhaustive" computation scheme follows: FINISHEDREPS + set of extensions of initial predicates ; I+ 1; WHILE categories remain to be represented DO BEGIN ADD representations for all categories having cost at most I (in terms of representations already in

FINISHEDREPS; I+ 1; END.

In order to determine whether (and how) a cate­ gory Si can be represented in terms of the members of FINISHEDREPS with a cost of I, we can simply generate all representations (finitely many when U is finite) and test to see if any represent the category under con­ sideration. It is not hard to see that the combinatorial explosion is severe here. If

the size of the universe is N, and the number of representations on FINISHEDREPS is q , then O((N + q)(I + l)/ 2 ) representations must be considered using this s cheme.

3.5 Reducing the Computational Effort

If q, the number of complete representations is much less than n, the size of the universe, then the following approach is economical. Combinations (of the existing q categories) of successively greater cost are generated using ~, u , and n but no singleton sets. The cate­ go ry Si which is to be represented, is "matched" to each of these categories as it is generated. In mat ching Si with an s. (set represented using some combination of existing

Categories), compute Sijl-si-sj, the set of numbers in Si missing from s 1 and Sijl=S 1 -s , the set of numbers which need to be remo­ ve! from sj in forming a representation for si in terms of s . 1 · We call dij·

The operation of determining the deficiency set and the excess set is analogous to a process referred to as "interference matching" [3]. The above algorithm can take advantage of an addi­ tional short cut (without changing its solu­ tions ). From I and C(R(S,)) the permissible deficiency plus excess isJ ·easily computed. As Sij l and Sij 2 are being computed it may be

apparent that the limit will be exceeded, At such a point, further consideration of Sj can be aborted for the current value of I.

3.6 Supporting Categories

In some cases a collection of categories may have their cost reduced by introduction of a new category. If we let our system construct one, we term it a supporting category. While we have heuristics to generate supporting cat­ egories that reduce costs in specific situat­ ions, the problem of finding them in general is an open one,

3.7 Extensions

Our study has primarily been concerned with sets of natural numbers. There exist straightforward means to represent and to compute costs for structured objects such as n-tuples, lab­ elled graphs and strings. Once again, comput­ ational complexity is a problem as one con­ fronts the problem of subgraph isomorphism (1].

4. IMPLEMENTATION

A preliminary implementation has shown that additional heuristics and/or parallel process­ ing are needed to make minimization of cost computationally feasible. Approximate solu­ tions would be acceptable in most AI appli­ cations and this area is open for future work.

5. CONCLUSION

The maintainance of a minimum cost represen­ tation for a set of categories is desirable be­ cause relationships among categories are clar­ ified and space requirements for the stored in­ formation are low. However, the complexity of computing -the representations is high. Some heuristics have been given here and more are needed to simplify such computations.