Substantial Constructive Induction Using Layered Information Compression: Tractable Feature Formation in Search

SUBSTANTIAL CONSTRUCTIVE INDUCTION USING LAYERED INFORMATION COMPRESSION: TRACTABLE FEATURE FORMATION IN SEARCH

Larry Rendell Department of Computer Science, University of IJiinois at Urbana-Champaign, 1304 West Springfield Avenue, Urbana, Illinois 61801

ABSTRACT

This paper addresses a problem of induction (generalization learning) which is more difficult than any comparable work in AI. The subject of the present research is a hard problem of new terms, a task of realistic constructive induction.

While the approach is quite general, the system is analyzed and tested in an environment of heuristic search where noise management and incremental learning are neces­ sary. Here constructive induction becomes feature formation from data represented in elementary form . A high-level attribute or feature such as "piece advantage" in checkers is much more abstract than an elementary descriptor or primi­ tive such as contents of a checkerboard square. Features have often been used in evaluation functions; primitives are usually too detailed for this.

To create abstract features from primitives (i.e. to res­ tructure data descriptions), a new form of clustering is used which involves layering of know ledge and in variance of util­ ity relationships related to data primitives and task goals. The scheme, which is both model- and data-driven, requires little background, domain-specific knowledge, but rather constructs it. The method achieves considerable generality with superior noise management and low computational complexity. Although the domains addressed are difficult, initial experimental results are encouraging. 1

I INTRODUCTION

A fundamental problem in AI is the automation of inductive inference [3 , 15, 25]. 2 Induction can be described as generali­ zation from particular cases [2, 6, 15], a~ learning categoriza­ tions from examples or observation [15, 18, 19], as intelligent compression of massive data [25,30,31], or as discovering regular, coherent characterizations of events or objects [15, 22 25]. 3 Whatever the interpretation, induction begins either with objects or with partially formed groupings, and creates one or more classes. These meaningful sets are also called categories or concepts. A concise representation of knowledge is imperative for reasons of space and time efficiency: in practical application, detailed information is simply too expensive either to store or to acquire, while induction of classes allows prediction of details [6, 23, 25, 30].

1. This work was supported in part by an operating grant from the Natural Sciences and Engineering Research Council of Ca­ nada.

2. The problem of induction is also a basic study outside of AI. It has occupied scholars in philosophy [5], psychology [13], pat­ tern recognition [2, 3, 9, 29, 31], and other fields [30] .

3. Formally: Given a set S of individual objects, induction is the inference of a larger class or hypothesis T, such that S C T. Since T is a generalization it may not be true; associated with T is its credibilit y, the estimated veracity of the induction .

Automated induction is crucial. For example, in an expert system, computer generalization means mechanized knowledge acquisition, which may reduce costs. Present expert systems are prone to unexpected error, whereas induc­ tion would increase reliability and obviate maintenance. Even in its primitive state, automated induction has outper­ formed knowledge engineering approaches [17].

A- Views of Inductive Difficulty

Unfortunately, induction is inherently difficult [I, 6, 30]. Noisy and sparsely distributed data offer little help in distin­ guishing hypothetical classes or concepts, and there are many hypotheses which are plausible, useful, sensible, or credible.

Inductive multiplicity can be understood in various ways. First, a credible hypothesis may be sought in a space of category descriptions. In this view of induction, search is conducted through a set of expressions which are systemati­ cally related to one another to facilitate their explicit forma­ tion (such expressions are otherwise only implicit, because of their immense number) [2 , 6,30]. In this search formaliza­ tion, exploration of plausible hypotheses must cope with exponential growth of their explicit representations.

The most abstract view of the inductive problem involves classification [30,31] . The number of ways of com­ bining objects into classes is extreme. If a small 10 X 10 grid of bits encodes letters of the alphabet, the number of different classes is 271 2100 1, and very few of these are credible. A view of induction which is intuitively close to the classification perspective is the feature space representation, illustrated in Fig. I.

A third way of analyzing the difficulty of induction con­ siders the quantitative problem as a qualitative one [15, 18, 23]. Class formation often requires restructuring of data: objects must be reorganized by transforming descrip­ tion variables. This means a change of knowledge represen­ tation (constructive induction, the problem of new terms), which is particularly difficult to automate [6, 25]. Fig.l com­ pares constructive induction with the simpler selective induc­ tion which needs no reorganization. 1

4. By selective induction we mean a case in which one or a few neighborhoods in feature space can easily be partitioned . Michalski's definition of this term [15] is more precise, but it ex­ cludes some cases we would want to call simple, such as classes discriminated by linear decision functions.

To structure data, an expressive language such as predi­ cate logic is required, but there are tradeoffs between expres­ siveness and efficiency (at least with current models). 5 Greater expressive power causes a worse combinatorial explo­ sion in search.

B. Research Directions

One approach to the combinatorial problem of induc­ tion is to limit hypotheses by imposing constraints on their expression [15, 25 ,32]. These constraints may take various forms. A straightforward tactic is simply to limit the description language without confining its power too much. For example, many methods permit conjunctions but not dis­ junctions [7] . Another way of restricting candidate descrip­ tions is to use some criterion to narrow search. Examples of criteria include "simplicity", quality of "fit" to the data [1 5, 18], and "invariance" under transformation of task ele­ ments [8] . A relaxed form of invariance has long been used in statistics and pattern recognition, viz. "similarity" in clus­ ter analysis [1] . The author 's scheme involves a special kind of similarity constraint based on the domain environment. The precise form of this similarity has to do with success or "utility" in the performance of some task [21, 23, 24, 25]. 6 Overall , constraining search for abstract knowledge has seen only limited success in terms of efficiency, effectiveness, and extensibility [7 , 15, 32].

Generalization algorithms have been designed either for selective induction [6, 7, 15, 19, 21, 28] or for quite simple con­ structive induction [10, 15]. The true nature of this AI work has sometimes been obscure because little attention has been given to the usual methods of science: delineation of abstract phenomena, detection of relevant variables, measurement of prec ise relationships, and development of guiding principles. Unified views of inductive systems are scarce (though there are [6 , 7, 15, 25]). Furthermore, AI research often ignores ear­ lier germane results, including [2 , 30]. Consequently no stan­ dard exists for answering important questions such as: How difficult is the inductive task · being studied! How much knowledge is acquired autonomously, versus the amount given by the user! Similar questions have recently been con­ sidered elsewhere [11, 26].

C. Quantitative Analysis

While the current state of induction in AI is under­ standable (the field being new and difficult), the time may have come for a more rigorous approach. (See [5 , 12, 15, 26] for similar sentiments.) In keeping with this goal, the author has begun to pursue a means for comparing inductive tasks and systems. Based on [30,31], this involves a quantification of inductive difficulty, both for task domains and for learning systems. This attempt began in [22, 23, 25] .

5. See [23[ for a discussion of representation languages. Im­ portant issues include equivalences of superficially different representations, and the distinction between languages appropriate for expression of concepts and languages useful for concept forma· lion. The current paper and [25[ examine structures for mediation between data and concepts.

6. Task-related utility is used as the criterion for clustering in the original probabilistic learning system PLSJ. This system has produced unique results such as convergence to optimal heuristics [21, 24, 25[. PLSI can handle noisy environments and incremental learning. The system is efficient.

The idea is simple: since induction creates a class T from a set of objects S, the difficulty of the generalization task depends on the nature of the information compression from cases S to concept T . 7 First, the more cases T must cover, the harder it is to describe T accurately while differentiating S from negative instances of the concept (see the approximation of conceptual knowledge as amount of information compreuion in [22, 25]). Secondly, if the attri­ butes describing S do not support straightforward selective induction (as in Fig.1a), but must instead be redefined by constructive induction (Fig. 1 b), then inductive difficulty depends on the kind of reconstruction required. When exam­ ined in the light of these measures, many systems (such as [10, 17, 21]) perform only a moderate amount of induction. In these systems, the total number of possible generalizations is confined to be relatively small from the outset.

D. Substantial Induction

In contrast to these simplified approaches, the current research attempts a very difficult task. Not only is the required amount of information compression very large, but, more important, a large degree of constructive induction is needed. In the proposed system, little domain-specific gui­ dance is provided by the user or program. This scheme is conceptually compact and appears tractable.

The method is related to a successful system for selec­ tive induction PLSJ. 6 One aspect common to PLS1 and the new system PLSO is the observation of a goal-oriented meas­ ure, the utility. The utility divergence, a function of "features" of objects, and also based on data patterns, is the criterion for induction. When PLSI uses utility for categori­ zation (conceptual clustering), various efficiencies and other advantages ensue. The scheme has been incremental and insensitive to noise since its inception [20, 21, 24] .

Retaining these valuable and unusual characteristics, PLSO implements a new form of constructive induction unlike other systems in important respects: although the inductive difficulty is great, little background knowledge is given, the language of concept expression is quite general, the algo­ rithms have low computational complexity, and the approach appears extensible. These claims will be elaborated.

7. This is a simplification. More than one class T may be in­ volved, or the set of objects S may already be partially formed into categories. For present purposes these details may be ignored wi thout affecting the essence of ind·1ctive difficulty.

II AN EXAMPLE IN HEURISTIC SEARCH

This section illustrates some of the above ideas and relates them to a hard problem of constructive induction. We intro­ duce task utility for inductive guidance, and layered abstrac­ tion of task knowledge. In later sections, these terms and those in the diagrams will be more carefully defined.

A. Goal-Directed Information Compression

An example of a product of induction is the concept of pair adjacency: two diagonally juxtaposed, friendly men in checkers (Figs. 2 & 3). In the description of such a concept, certain spatial patterns are essential (adjacency) while other aspects are immaterial (location of the pattern and presence of extraneous pieces). Other "useful" concepts in checkers are piece advantage, mobility, center control, etc. These are useful because they relate to winning, and the ultimate con­ cept in a game is the strength or utility for one player. Util­ ity is the most abstract concept desired.

Figure 3. The three level information structure of PLSO. Shown is the construction of a feature r which counts the number of diagonal juxtapositions or two friendly pieces in checkers. This begins with a detailed description or board configurations in terms or 32 primi­ tives ei giving the contents of individual squares. (See Fig. 2 for detail.) When subspaces such as e 10 eu and e 10 e 1 g are examined, and utilities are CLUSTERed after superposition of subspaces, important structural patterns emerge having common utility descriptors (UD's). A patt ern class results (level 2). Eventually a class may be generalized using a group or transformations (level 3).

Here we may express utility using an evaluation function H. Objects assessed by H are 6tate6 or board configurations 8. To evaluate board 8 , H combines pair adjacency, piece advantage, and other feature6 . In terms of generalization, states are elementary object descriptions, the utility value given by H is the most concise description, and feature values are intermediate between objects and their utilities.

B. Layers of Abstraction

As it happens, a resolution of roughly 100 distinct utility cla88t:B is sufficient to differentiate among moves in the game of checkers (see the discussions in [22, 25]). Fig. 4 reflects this; here utility values lie in the interval (0, 1] and are given to two decimal places. In contrast, an object (board configuration or state) is a vector of 32 primitivu indicating the contents of each permissible square (black king, black man, vacant, red man, red king; or -2,-1,0,1,2), and there are roughly 102° legal states. Full inductive learning would require the assignment of each of these configurations to its

e"

0/0

0/0

0/0

13/46

12/15

p. man

0/0

0/0

2/5

4/10

o. kin&

p. kins

p. man

0/0

p. kin&

0/1

2/6

0/0

0/0

8/60

3/g

0/0

3/7

0/0

1/3

0/0

o. kina proper utility class, for an average of about 1020 I 100 = 1018 in each class. In terms of primitives, a logic description of such a class would be highly irregular, involving a combina­ tion of an immense number of terms.

Utility classes are much easier to describe in terms of predefined features. As Fig. 4 illustrates, the num her of classes at the feature level is very roughly 10 6 -- this is the size of a typical feature space [25 ,28]. Utility bears a smooth relationship to features, so the induction required is merely selective (Fig.1a), and only a few simple descriptions are needed (Fig. 5). 9 In contrast, raw data descriptions in the form of primitive vectors are more detailed (having 10 20 values as opposed to 10 6 ). Moreover, utility-primitive rela­ t ionships are discontinuous, so the much more difficult con­ struc tive induction is needed (see Figs. 1 and 3).

C. Automated Feature Construction

This paper begins to explore a method for discovery of features from primitives, a problem hardly addressed previ­ ously (but see [8, 9, 19]). Conceptually and experimentally, t he approach appears tractable and error resilient. A lay­ ered, "divide and conquer" approach restricts complexity, not just "generating and testing" hypotheses, but rather con­ structing simple ones from previously validated components.

9 . Because most of the "knowledge" resides so regularly in the features , an evaluation function can often be a linear combination of them. See !25!.

How can utility-primitive relationships be captured and generalized! Induction is infeasible without some guidance from regularities, assumed or else discovered [32]. One tech­ nique , curve fitting, is often inadequate even in selective induction when features are the starting point [6, 25, 28] . A more flexible approach is to record information in feature space cells, as in Fig.5 [21 , 28]. An important tool for induc­ ing this knowledge is the method of cluatering.

ill CLUSTERING, A TOOL FOR INDUCTION

Clustering classifies data so that events or object3 are aimilar within any class, but dissimilar across classes [1] .. This tech­ nique has been used in successful learning systems by Michal­ ski [15, 17, 18], and earlier by the author [20, 21 , 25], who ori­ ginated a form of conceptual cludering. This kind of cluster­ ing t akes into account not only feature values, but also forms of concepts (e.g. feature space rectangles) and aspects of the environment (e.g. observed utility). Michalski has emphasized concept constraints, and the author has stressed relationships between task domain and inductive algorithms. These are dual aspects: model- and data-drivenness.

In this section we describe general characteristics of clustering, and then examine PLSJ's algorithm for selective induction as a preliminary for PLSO's more powerful con­ structive induction.

A. Mutual Data Support

Clustering has several desirable properties. Within ascribed boundaries of a cluster, missing data presumably share characteristics of the1r neighbors, so the process can be predictive (see Figs. 1a and 5). Once a class is formed, its determining data may be dismissed, so storage and computa­ tion can be economical. If statistics is employed, susceptibil­ ity to error may be low and credibility may improve as a result of clustering the data. Further, the structure used for clustering may concisely describe a concept that emerges automatically as information is compressed [15, 25] .

As an example of these characteristics, consider the left­ most rectangle of Fig. 5. Because of the imposed rectangular shape, the description of this "concept" is simple and easily stored: (0 s f 1 s 4) n (0 s f 2 s 2). Moreover the associ­ ated utility u = 0.2 may have come from many data: out of perhaps N = 100 objects observed in this rectangle, g = 20 of them may have been "successful". If a few observations were in error, the value of u =gIN = 20 I 100 = 0.2 would still be close to the "true" utility (here a probability). As long as the utility does not vary too much within the rectangle's boundaries (a case of selective induction), u may relate to any enclosed point, observed or unobserved. As an added benefit, u may be more accurate because it has been measured over many "similar" objects. We call this impor­ tant coincidence of information compression, concept forma­ tion, and accuracy improvement mutual data 8Upport [25].

B. Goal-Directed Clustering Using Utility

Mutual data support arises in the statistical technique of clustering. In [20, ,21, 25], the author introduced a special kind of clustering which employs not just attributes or features of an object, but also the quality or utility of that object in the task environment. 10 This clustering criterion is central in the family of probabili8tic learning system8 (PLS) [22 , 24 , 25]. 11 In PLS1, the utility u is a probability: the number g of "good" objects contributing to task success, divided by the total number N of observed objects: the utility

E.g., the object might be a state in a problem or game, and success might mean appearing in a solution or win.

C. Regions as Clusters of Similar Utility

PLS1 clusters utility, thereby associating state descrip­ tions of common quality. The cluster or region R is a triple (r , u, E) , feature space volume r having utility u with error factor E (this codes the interval [u/ E, uE]). Because utility bears a smooth relationship to typical features, clustering may profitably be constrained as a partition of feature space, the region set (see Fig. 5). The region set is suitable for selec­ tive induction (Fig. 1a); it is a compressed representation of the utility surface in this augmented feature space.

Characteristics of regions (e.g. rectangle size and shape) are consistent with data encountered: a region set remains small enough to economize resources but large enough to express important knowledge. To accomplish this, PLS1 employs a utility revision rule for correcting values of u, a specialization rule for refining cells r, and generalization and reorganization operators for otherwise modifying regions.

Various unusual or unique advantages result . Computa­ tion is inexpensive, and more autonomous than Samuel's sig­ nature table method [28]. The algorithms automatically pro­ duce an effect similar to a criterion using "similarity" and "fit" (see [21, 24, 25] and compare [15, 18]). Results include efficient discovery of optimal heuristics.

D. Region Refinement and Credibility

Here we consider in detail the PLS1 refinement operator for splitting regions: the algorithm CLUSTER[21, 25]. A region R is dichotomized when utility data within it are found to diverge. The criterion for splitting involves a dis­ similarity (distance) measure d . If u 1 and u 2 are the two util­ ities for a tentative dichotomy, and E 1 and E 2 their errors, then d = llogu 1 - logu 2 l - log(E 1 E 2 ). The dissimilarity dis computed for all boundary insertions parallel to any feature space axis. If the largest d is positive, the corresponding split is retained . The process is repeated until additional refinement is unwarranted by the data (until d s 0).

10. See Anderberg ]1, pp. 194 ff.j ror discussion or "external cri­ teria" in clustering.

11. The original PLSJ bas been extended to become a more stable, powerrul and efficient learning system PLSe ]24, 25], but here we rerer to both as PLSI.

Notice that larger d means more assuredly dissimilar regions. If the values of d are summed for successive per­ manent splits of R, the result is a measure of reliability (cred­ ibility) of the complete clustering operation, the discrimina­ tion assurance D. D increases with the quotient u 1 / u 2 , and inversely with the error E. One factor affecting the error E is sample size N (number of observed objects): as N increases, E decreases and D improves.

As an example, consider Fig. 5, and suppose that the two leftmost rectangles resulted from ( 0 s f, s 6) n ( 0 s f 2 s 2 ). Assume that the sample size N in each new rectan­ gle is 100, and that the error f. is log [1 + 1 / V N ]. Then the total discrimination assurance D is just the dissimilarity d = llog[20/100] - log[1/100]i - log[(l.l)(l.l)] = - 1.6 - 4.6 - 0.2 = 2.8. If the sample size were 10, D would be 2.5, still a high credibility. We shall c;onsider D again in Section V.

While very useful for creating an evaluation function from typical features [21, 25], CLUSTER is inadequate for manipulating primitives, since their utility relationships are so disorderly (i.e. constructive induction is required -- see Fig. 1 ). Nevertheless, CLUSTER forms the basis for a more powerful algorithm in the feature formation system PLSO.

IV STRUCTURES FOR COMPLEX CLUSTERING

Automatic construction of an evaluation function from features is difficult [22 ,25, 28], yet just a small part of the whole inductive problem. The main problem, formation of features from primitives, should perhaps be subdivided, since gradual information compression is easier [31].

In PLSO, feature creation is automated using three stages. Each uses a characteristic knowledge structure which progressively generalizes the level below; each stage imposes constraints, reduces complexity, extracts meaning, and increases regularity. The basis for generalization at each level is similarity of utility relationships in subobjects (i.e. invariance of utility surfaces in augmented primitive space).

To illustrate PLSO knowledge structures, their relation­ ships, and their conformation into features, consider the example of Figs. 2 & 3. Here the subobjects are squares of the checker board, and the illustrative concept C to be learned is pair adjacency, i.e. the diagonal juxtaposition of two men (some degree of insurance against being jumped). The feature f to be created is the number of instances of C.

We shall follow the hypothetical generation of f at each of the three knowledge levels. Linearly index the thirty-two elementary measures ei as is standard in checkers. Suppose ei(B) = 0 means board 8 has no piece currently occupying position i, w bile ei(B) = k indicates the presence of a man if k=1, or of a king if k=2 (with corresponding negative values if the piece is the opponent's). The feature f is the num her of cases in which ei > 0, ej > 0, for diagonally adjacent i,j.

Creation of f requires the discovery that the condition (ei > 0 and ej > 0) is similarly good for these adjacent i, j pairs. For example, the utility of simultaneously pos1t1ve values of e 10 and e14 is about equal to the utility of the same condition on e16 and e19 (see Fig. 3}. A prerequisite for mechanizing this inference is some language to express utility in the two dimensional subspace determined by ei and ej, separate from any other coordinate ek.

A. Knowledge Levell: Subobject Relationships

To permit this structuring, knowledge level 1 uses pro­ jections of then-dimensional primitive space (here n=32). A 8Ub8pace 8pecifier {SS} is a string ei ei ... ei of length s s n. I 2 S Our illustrative example f can be expressed using a uniform combination of SS's, all with s=2. For example, one mem her of the adjacency concept is e10 e 14 (Fig. 2). Paired with each SS ei, ei 2 ·· . ei 5 is its utility de1criptor (UD}, a region set expressing utility relationships in this primitive 1ubspace. An SS together with its UD is a primitive pattern. Fig. 2 and level 1 of Fig. 3 show two primitive patterns, one for the sub­ space specifier e 10 e 14 , and the other for the SS e16e19.

A primitive pattern is a compressed representation of the function u(e), where u is the utility, and e is the full primitive vector. The compression is of two types: projection of primitive space into subspaces, and approximation of u as a step function . The subspaces are indicated as subspace specifiers (SS's), and the step function is expressed as a util­ ity descriptor (a UD is a primitive region set).

The purpose of knowledge level 1 is to compress utility relationships concise forms distinguishing striking aspects of objects. Consider Fig. 2 again. The SS's e10e 14 and e16e19 are both meaningful as subobject pair~. These two SS's represent similar structures, one just a translation of the other, so their UD's are somewhat alike. Primitive patterns may stand out like this, based on small, biased domain sam­ ples. We shall return to small sample effects in Section V.

B. Level 2: Pattern Classes of Similar Structures

Knowledge level 2 facilitates search for similar subobject structures: those exhibiting similar utility behavior are merged, eventually to produce a sensible feature. Regulari­ t.ies are recorded in a pattern clau, a union of primitive pat­ terns, i.e. a set of SS's with a common UD (Fig. 3}. In our example, SS's would arise consisting of two adjacent coordi­ nates, such as e10 e14 , e16 e19, and e22 e26 . These would be placed in a distinctive pattern class because their individual UD's are similar and can be combined (details are given later). This category would indicate indistinguishable utility behavior of each component SS and also nonseparability of e 10 e14 into single coordinates e10 and e 14 , etc.; i.e. the primitives are meaningful as pair~.

The overall purpose of knowledge level 2 is to unify similar primitive structures (e.g. patterns of checkerboard squares) as functionally equivalent subobjects, i.e. to cluster SS's whose associated utility descriptors agree when superim­ posed . Correspondence of UD's strengthens knowledge about utility-primitive relationships, since more information is present in the union (mutual data support). These regu­ larized pattern classes become prospective feature elements. Little information is wasted since only the strong patterns survive or even appear.

C. Knowledge Level 3: Pattern Groups

Knowledge level 9 is the most advanced structure for feature formation. Here we discuss it only briefly.

A level 2 pattern class is augmented by a set of transfor­ mation operators which, when applied to subspace specifiers in the class, reproduce extant members and fill in "missing" SS's. Operators are selected which give the "best" closure in this induction of the pattern group. The feature f requires translation and rotation (of 90 · ). Several pairs like e10 ew etc., might be needed for confidence in the general transfor­ mation, which induces a group of 56 primitive patterns.

An alternative formalization for knowledge level 3 is grammatical inference (9]. The above example would become a single production rule.

D. Summary of Layered Knowledge

At the lowest knowledge level, data are CLUSTERed to distinguish prominent utility surfaces in primitive subspaces. Discriminating combinations of primitives (SS's) are identified, and their utility relationships are condensed as utility descriptors (UD's).

At the second level, these results are consolidated into sets of corresponding primitive subspaces having mutually similar utility surfaces (UD's). As a consequence of matching and coalescing utility relationships, important structure in domain subobjects is identified and extracted. This structure creation emerges from clu1tering utility 8urfacu.

At the third knowledge level, individual primitive pat­ terns of a given class are used to induce a complete group: a general rule is discovered for transforming one member of the class into another, and missing elements are inferred. As explained below, utility in variances help to generate these compound structures incrementally and efficiently.

V REALISTIC CONSTRUCTIVE INDUCTION

This section outlines feature creation from the knowledge structures just described and considers the reduced computa­ tional complexity resulting from their restriction.

A. Feature Formation

Features are produced from pattern classes (knowledge level 2) or from pattern groups (level 3}. In either case, the associated utility descriptor (UD) for the category provides information about a formative feature f, defined thus: An object x to be assessed by f is first mapped into primitive space, then for each SS ei 1 ei 2 ··· ei 5 of the class, the utility given by the UD is summed. For our illustrative feature f, a pattern class might include e10 e 14 , e16 e19, and e22 e26. Suppose (i) e10(x) = -1 (enemy piece), e 14 (x) = 0 (clear square), while (ii) e16(x) = e19(x) = 1 and (iii) e22(x) = e26(x) = 1 (all friendly pieces). Typical utilities given by the UD for (i) might be u = 0.001, but for (ii) and (iii), u = 0.1 (Fig. 3, level 2}. Then f(x) is the sum of these, or .201. Since juxtaposed friendly men have higher utility, f becomes a measure of the "pair adjacency" for the entire checker board (if f is formed from a pattern group), or from parts of the board (if only a pattern class is known)P Thus, generation of a feature is straightforward. The main difficulty is efficient creation of reasonable knowledge structures preceding this ultimate step.

B. Restricted Use or Primitives

Even using exhaustive search, knowledge acquisition at level 3 is relatively inexpensive for current domains (although not generally [28]}. Here we will focus on levels 1 and 2, which, combinatorially, are extremely complex. The number of possible subspace specifiers (SS's) is 232 for checkers, and finding appropriate SS's is only one step in the induction. However the problem may be simplified.

In PLSO, the explicit creation of an SS may begin with straightforward primitive CLUSTERing which determines various ground values and structures (Da, VDa, etc. -- see Section III). Since not all variables differentiate utility in a practical (small) data set, this ground processing reduces the effective dimensionality (by about two thirds in trial experi­ ments). The remaining primitives are active for current data. The fact that only some primitives are active accounts for the phenomenon or useful information extraction in ground CLUSTERing; even though abstract features are con­ founded at the primitive level, structures do arise for small data sets. Moreover, strong patterns appear first.

Utility-primitive relationships are reinforced through comparison with other formative subobject structures (i.e. with similar components of the board). To discover mean­ ingful patterns among these subobjects (i.e. among subspaces of primitive space), certain arrangements A of variables from the active set S are considered. Let the size of S be n; each A is a relation [27] over sk, where ksn. For example, sup­ pose S = {e 2 ,e6,e10,e14,e15} is the active set. Then n=5. For k=2, one A is {(e 2 , e6), (e10, e 14 ), (e 10 ,e15)}. The pair (e 2 ,e6) determines the SS e 2 e6, etc., and A defines a 6uperpo8ition of primitive subspaces, i.e. a clau of SS's (here the class is SSA = { e 2 e6, e10ew e 10 e15 }, a precursor of f) .

C. Mutual Data Support (or Structuring

Given a superposition A of active variables, CLUSTER (Section III) is now run with overlaid primitives treated as one. E.g., for SSA, e 2 and e10 would be identified. Because of this equivalence, the sample sizes N (Section III) are effectively increased (by a factor roughly equal to the number or superpositions-- it is patterns within states-- subobjects -­ that are counted). Since larger N implies lower errors, the discrimination assurance D is higher in cases where primitive patterns coincide; i.e. when utilities match up in the overlaid dimensions, and merged UD's support each other (see Figs. 2 & 3). If, instead, utility behavior differs, the mutual support is weaker, and if misalignment is extreme, D is even lower than the ground value Da.

The simple example of Fig. 6 shows three cases of super­ position, in three tables. The leftmost is ground clustering (no overlaying) with subspace specifier e10e 14 ew In the first row, (e10,e 14 ,e16) = (0, 1, 1) indicates that the tenth square is blank, and that the fourteenth and sixteenth squares both contain a friendly man. This structure has a sample size N of only 5. In the third row of this leftmost table, (1 , 1, 0) has N = 8. Note that in row one, e 10 = 0, while in row three, e16 = 0. In no other row is either variable zero.

12. A feature is tentative until enough support is found for its determinative pattern class. This support increases gradually as experience is gained (additional data result in more regions per UD and in more patterns per class). Once defined, features are in­ dependently assessed and selected by PLSI [21, 25].

The center table shows identification of e10 with e16. In the first row of this table, N is the sum of the N values from the first and third rows of the leftmost table. This gives a sample size of 13 for e10 or e16 equal to zero and e 14 = l. The other table entries are computed similarly.

Recall from Section III that utility u = g/N, and that D is the sum of utility dissimilarities when rectangles are split. Comparing the central and rightmost tables, we see that the discrimination assurance D should be substantial in the cen­ tral table but likely zero in the rightmost one. Thus the rightmost overlay is rejected. Since the center case has util­ ity values similar to the ground case, but the quantities are larger in the center overlay, D is higher there. Hence the superposition of e10 with e16 is supported (these two variables are "similar").

This is 6mall 8ample 8imilarity, which has been verified in experiments. When various superpositions are examined, certain of them are found to stand out, i.e. to have high D's; these become components of pattern classes. In summary, overlaid CLUSTERing extracts utility commonalities in com­ ponents or the object (board description), and thereby dis­ covers and strengthens patterns of meaningful structure.

D. Constrained, yet General Constructive Induction

Without some guidance, examining superpositions 1s extremely complex: the number of trials is 0(21n"l), where n is the number of active primitives. The value of n may be reduced by screening inactive variables with ground CLUS­ TERing (Subsection B), but more important, trials need not be exhaustive. They can be uniformly guided by general heuristics. Intrinsic bonds in primitive variables manifest in poorer D's when elements of the combination are unduly superimposed. This discovery of small sample diuimilarity is illustrated above and in Fig.6, where e10 and e14 are distinguished. Such a discovery disqualifies the superposition { {e 10 },{e 14 }} as part of any other trial, which means that only pair8 need be overlaid in preliminary testing. The complex­ ity of this is O(n2).

. ., N . ., After pairs of small sample ~imilar pnmat1Ve8 are formed (e.g. A 1 = { {e 10 } , {e 16 } }, A 2 = { {e 14 }, {e 19 } }, etc.), CLUSTERing is subsequently reapplied to classify pairs of simil ar primit.ives into larger sets (at this point, overlays are still one-dimensional). In this way, similar patterns emerge and cluster into mutually diuimilar sets.

Finally, general SS 's are constructed by appropriate selection. For example, if there are two dissimilar sets S 1 = { e 10 , e 16 , e 22 } and S 2 = { e 2 , e 14 , e 19 , e 26 , e 30 }, one SS class would be { e 10 e 14 , e 16 e 19 , e 22 e 26 }, thus preserving primitive dissimilarity in distinct dimensions w bile identifying similar primitives and thereby creating structural pattern classes.

These algorithms have been programmed and tested with the fifteen puzzle. 13 The 15 primitives used were city block distances of individual tiles from their home positions. (This gives a 10% information compression advantage com­ pared with the 80% of high level features -- see [25].) The first feature induced was the total distance score fd . Experiments show that discrimination assurance D is a good meas­ ure for trial superpositions. When data were gathered using breadth-first search , fd was created and no other pattern classes formed . In contrast, after fd emerged to guide search, D values were less uniform in overlays, and other pattern classes began to arise.

E. PLSO Outlook and Summary

One question about PLSO methodology is its generality. We can gain some insight by considering, for example, Samuel's features for checkers. Several of these, such as piece advantage, guard, etc., would present no problem. Others, though, such as mobility, would require more sophis­ ticated transformations (or additional knowledge levels) for efficient induction. Not only games and puzzles, but also various real-world applications seem either to conform to the general PLSO approach as it stands, or else to possible exten­ sions of the system.

To summarize: Feature formation is straightforward once appropriate knowledge structures have been created. In limiting the huge quantity of possible structures [30], PLSO imposes few arbi t rary constraints (compare [7]), but rather the data help to simplify search Structural patterns (primi­ tive su bspaces -- SS 's) and goal-directed information (utility relationships -- UD's) are meaningfully combined using a credibility measure (discrimination assurance D) to assess candidate hypotheses (overlays).

This process creates a change of knowledge repre8enta­ tion -- to meaningful object component~ expressed as classes and groups of structures together with information about their utility. Intrinsic bonds among primitive components become explicit. PLSO is designed for any cases in which componP.nts of objects may be identified (whenever translations, rotations, etc., leave utility invariant). This applies to a large class of problems since goal-direction and invariance (similarity of object components) are prevalent.

13. Other ideas have not yet been programmed . One involves comparison with predicted D's assuming perfect superposition (i .e. full aligned utiliiy surfaces). Still another heuristic involves gui­ dance from pattern classes already forming: since PLSO is incremen­ tal, current data may be compressed preferentially to match extant primitive patterns and classes -- by searching for supporting super­ positions, e.g. those hav ing the same SS length as established classes.

VI CONCLUSIONS

While still formative, PLSO is a general, substantial, and promising learning system for realistic constructive induction. Its superior capability can be quantified (Section II). When assessed according to criteria for constructive induction [7], PLSO appears solid. The three level knowledge repre6enta­ tion is adequate for domains considered and exten6ible to oth­ ers. The rules of generalization are powerful, suited to prob­ lems not previously explorable. Heuristics are general across domains. This stochastic scheme is in6en6itive to error. Finally, PLSO is efficient; it effectively reduces computational complexity (e.g. from double exponential to polynomial in an important part of the problem -- see Section V).

To improve effici ency, PLSO feature creation uses a "divide and conquer" scheme having three stages, each of which builds from elements verified at the level below . Structures are generated, assessed, and improved so that the generate-and-test cycle of inductive inference is meaningfully constrained . Each of the three stages is both model- and data-driven : general heuristics speed formation of hypotheti­ cal concepts, and task utility determines the more credible ones.

The basis for this constructive induction is clustered utility surfaces. lnvariance of utility relationships in primi­ tive description spaces leads to a new form of clustering which creates new knowledge ~tructure8. Progressive struc­ turing relies on mutual data support during clustering of util­ ity surfaces: informat ion is simultaneously regularized and reinforced. Mutual data support is important: it is the simul­ taneous occurrence of concept formation, noise management, accuracy improvement, and complexity reduction.

The computational complexity of the generalization problem may be reducible from intractably exponential to practically polynomial.