Improving Efficiency by Learning Intermediate Concepts

1 Introduction

Knowledge is necessary but not sufficient for intelligent behavior. In addition, knowledge must be stored in some form that lets it be used effectively. One of the central goals of machine learning is to devise mechanisms that transform knowledge from inefficient forms into more ef­ ficient ones. Most research on this topic has focused on explanation-based learning [Mitchell et al. , 1986, DeJong and Mooney, 1986], which augments a domain theory with rules that are more 'operational' than the original ones. Such operational rules let one bypass in­ termediate concepts, producing shallower proofs on fu­ ture cases with the same structure.

In this paper, we show that more operational knowl­ edge does not always lead to more efficient behavior. In addition, we describe an alternative approach that involves the introduction of new intermediate concepts into the domain theory - effectively the inverse of op­ erationalization. We show that, at least in some do­ mains, this form of learning leads to more efficient forms of knowledge than do explanation-based methods.

In the following section we describe RINCON (Retain­ ing INtermediate CONcepts), a learning system that implements our approach to the transformation of do­ main knowledge. After this, we report experiments with the system on two natural domains. Finally, we show how RINCON provides a framework for integrating explanation-based learning, incremental concept forma­ tion, representation change, and pattern matching.

2 Overview of RINCON

2.1 Representation and organization

RINCON is a system that forms domain theories from examples with the goal of maximizing classification ef­ ficiency. Instances are represented as conjunctions of n-ary predicates, allowing one to represent not only at­ tributes, but also relations [Vere, 1975] . For example, father(A,B) /\ female(B) expresses a father-daughter relationship. Instances also contain a class label that is used for supervised learning.

Instances and concepts are stored hierarchically in a domain theory that is partially ordered according to the generality of the concepts. Figure 1 shows a simple hier­ archy of concepts from a domain theory for family rela­ tionships. The highest-level concepts in the domain the­ ory are the primitive features (predicates) used to repre­ sent instances. The lowest-level concepts correspond to the classes found in the training examples and may be disjunctive. The learned internal concepts must be con­ junctive, appearing in the head of only one rewrite rule. All concepts are expressed in terms of higher-level con­ cepts in the domain theory. For example, Figure 1 shows primitive features used to describe the concept brother, which is used to describe the concept uncle .

2.2 The performance system

The domain theory is used to classify instances. Given an instance and a concept, RINCON determines if the instance is described by the concept. If the concept is relational (conjunctions of n-ary predicates), then the system also determines all of the ways (different bind­ ings) in which the instance is a member of the concept. The matching process is goal directed, starting with the concept to be determined and recursively finding all matches for each subconcept composing the concept. 1 Each time a concept node is matched, the resulting bind­ ings are stored with that concept's node. By storing all matches for all relevant subconcepts, time may be saved if the bindings are needed again. The match algorithm is shown in Table 1.

function match(concept, instance) if concept has not already been matched then if concept is a primitive feature then store all matches of concept with features from instance else for each disjunct in concept do match-disjunct (disjunct, instance) store matches from all disjuncts in the node concept return stored bindings function match-disjunct (disjunct, instance) let bindings be the list containing the empty list for each concept used in disjunct while bindings is not empty do let bindings be the join of each bindings list in bindings with each binding in match(concept , instance) return bindings

As an example of how internal concepts can improve overall match efficiency, consider the following simple domain theory for the concept uncle: 2

uncle(X,Y) <- male(X) A sibling(X,Z) A mother(Z,Y) uncle(X,Y) <- male(X) A sibling(X,Z) A father(Z,Y).

Now suppose this domain theory is used to determine all of the uncle relations in the instance male(pat) A sibling(pat,john) A father(john,jean) A male(frank) A sibling(frank,marie) A mother(marie,jean) . Since there are two uncles in the instance, the matcher would have to re-join the bindings from the male and sibling concepts. Instead, suppose the domain theory included the concept brother:

uncle(X,Y) uncle(X,Y) brother(X,Y) <- brother(X,Z) A mother(Z,Y) <- brother(X,Z) A father(Z,Y) <- male(X) A sibling(X,Y).

This domain theory would be more efficient to use since the work of matching the brother concept would only be done once when matching against the two definitions for uncle. The next section describes how one can acquire such internal concepts.

1 This differs from logic programming. Instances in RIN­ CON may contain variables but are treated as constants by the matcher. Hence, it does not perform unification.

2 Another type of uncle is the husband of an aunt.

2.3 The RINCON learning algorithm

The RINCON system begins with an initial domain the­ ory and incrementally extends it to incorporate new in­ stances. At present, the learned theory does not go beyond the data; it simply organizes the instances ac­ cording to the existing domain theory and any learned intermediate concepts. RINCON's goal is to produce do­ main theories that maximize the classification efficiency for both seen and unseen instances. Table 2 presents the algorithm for learning new intermediate concepts.

function incorporate (instance, concept, theory) match (concept, instance) if no bindings exist for concept then let matched be the most specific concepts in theory that do match instance let notmatched be the most general concepts in theory that do not match instance rewrite instance in terms of concepts in matched add instance to theory let G be all maximally specific generalizations of instance with concepts in notmatched let NewG be the generalization in G that can be used to re-express the most number of concepts in theory add NewG to theory re-express all concepts in theory in terms of NewG return theory

RINCON's learning algorithm carries out incremental hill climbing [Gennari et a/., 1989] through the space of domain theories. The system starts by matching the new instance against the concept with the same label. If the instance is described by the domain theory, then no learning occurs and the existing theory is retained. Oth­ erwise, it collects the most specific concepts that match the instance and the most general concepts that do not match the instance. The system then re-expresses .the in­ stance in terms of the concepts it does match and adds it to the domain theory as a new disjunct for its con­ cept class. The re-expressed instance is then generalized [Vere, 1975] with each concept in the set of most general concepts it does not match. Each of these generaliza­ tions is a candidate for a new internal concept. RIN­ CON's evaluation function selects the generalization that can be used to re-express the most concepts in the do­ main theory. The selected generalization is then added to the theory and used to re-express all of the concepts in the domain theory that it can.

As an example, assume the following domain theory, which contains only one instance:

uncle(walter,jim) <- male(walter) A sibling(walter,carol) A mother(carol,jim).

uncle(pat,jean) <- male(pat) A sibling(pat,john) A father(john,jean)

it finds that the concept uncle in the domain theory does not match this instance. The system then ·finds the most specific concepts in the theory that do match (male, sibling, and father), and the most general con­ cepts that do not match (uncle). RINCON then rewrites the instance using the highest-level concepts matched. Since these are simply the primitive features, the in­ stance description remains unchanged. The instance is then added to the domain theory and is generalized with all of the lowest-level concepts that do not match, in this case uncle . The only maximally specific generalization is male(X) A sibling(X,Y), which is added to the domain theory. This generalization is used to rewrite both of the uncle definitions to produce the following domain theory: 3

RINCON continues processing new instances, extending the domain theory to incorporate each new instance.

3 Experimental evaluation of RINCON

The goal of RINCON is to improve the efficiency of match­ ing instances. Since the system currently does no induc­ tion, classification accuracy is irrelevant. Instead, the natural unit of measure is the amount of work required to match or reject an instance. We measure work in terms of the number of join operations performed in the match process. A join occurs when two lists of bindings are combined to form a new consistent bindings list (which might be empty if the bindings are inconsistent). For attribute-value representations the join of N attributes is N - 1, since multiple bindings are never produced. The number of joins provides a reasonable measure of work since at least one join occurs whenever a concept node in the hierarchy is matched (see match-disjunct in Table 1). Also, the time required to perform a join is bounded by a constant for any given domain.

As a baseline for comparison in all of our experiments we measured the work performed by a corresponding do­ main theory with no intermediate concepts. 4 This 'flat' domain theory is simply an extensional description of all the observed instances.

Our first experiment involved building a domain the­ ory from instances of mushrooms [Schlimmer, 1987] in which each instance was described as a conjunction of 23 attribute-value pairs. A total of 3,078 instances were available. The experiment began with an empty domain theory, to which RINCON incrementally added randomly chosen instances. After every ten instances were incorpo­ rated into the domain theory, we computed the average amount of work required for matching each of the previously seen instances. We also measured the average amount of work for matching the same number of mush­ room instances not described by the domain theory. Fig­ ure 2 presents the learning curves for the average work of matching an instance as a function of the number of instances stored in the domain theory. Each curve shows the average over 25 different runs.

3 We have named the new concept brother only for clarity.

4 This is equivalent to a domain theory containing only 'operational' definitions.

The figure shows that the domain theory containing intermediate concepts was on average more efficient at matching previously seen instances than was the corre­ sponding flat domain theory. Surprisingly, the flat the­ ory also required more match time to reject previously unseen instances than did the learned domain theory. This suggests that the learned theory contains interme­ diate concepts shared among all mushroom instances. Such intermediate concepts would save on the overall match time for unseen instances, since they would store bindings often needed in the match process .

The results presented in Figure 2 seem to run counter to the notion that operational domain theories are more efficient to use than those containing intermediate con­ cepts. However, for some instances the flat domain the­ ory is more efficient. At the end of each of the 25 ex­ periments, for each 100 mushroom instances processed, we computed the percentage of work saved by using the learned domain theory over the flat one. Figure 3 shows the distribution of instances as a function of the percent­ age of work saved. Although work is saved on average, intermediate concepts sometimes do reduce efficiency. This suggests a trade-off between retaining intermediate concepts and operationalizing concepts.

The mushroom experiments measured the efficiency of learned domain theories as a function of the number of instances processed. The size of each mushroom instance was constant. Our second experiment measured the effi­ ciency of learned domain theories as a function of the size of the instances matched while holding the number of in­ stances in the domain theory constant. This experiment involved using RINCON to organize the rules of a produc­ tion system. In this case, the 'instances' used to build the domain theory were the condition sides of produc­ tion rules. Unlike the mushroom domain, these instances were relational and contained variables. The production system solved multi-column subtraction problems [Lang­ ley and Ohlsson, 1984] such as 128- 39 using a set of nine rules. The rule set included such operators as subtract­ ing two numbers in a column, shif~ing attention from one column to another, and borrowmg ten from a col­ umn. The production rules were written such that ~nly one rule with one set of bindings ever matched agamst working memory.

The experiment consisted of running the pr?duction system on sets of subtraction problems of varymg co~­ plexity measured as the maximum number of columns m the pr;blem. Each problem was solved using the dom~in theory of rules built by RINCON and the c~rrespond~ng flat theory to find which rules matched agamst workmg memory. We computed the average work (number of joins) per production system cycle for both of the do­ main theories when solving each problem. Each cycle of the production system requires matching the rules in the domain theory against working memory.

Number of Columns

Figure 4. Average work/ cycle as a function of instance size.

The graph in Figure 4 shows the average amount of work per cycle as a function of instance size for both of the domain theories. Each point in the graph is the av­ erage over 25 different subtraction problems at a given level of problem complexity. The curves for the flat do­ main theory and for the domain theory built by RIN­ CON suggest that the average work per cycle is a linear function of the number of columns in the subtraction problem. This reflects the fact that the working mem­ ory increases linearly in the number of columns. Overall, the domain theory built by RINCON required about half as much work as the flat domain theory.

4 Discussion

The learning mechanism used in RINCON is closely re­ lated to methods used in four AI paradigms that have traditionally been viewed as quite diverse - explanation­ based learning, incremental concept formation, represen­ tation change, and pattern matching. Below we expand on these relations noting some directions for future re­ search.

4.1 Relation to explanation-based learning

Our approach to learning has much in common with work on explanation-based learning [Mitchell et al., 1986, DeJong and Mooney, 1986]. In both cases, do­ main knowledge is organized as a set of inference rules, recognition involves constructing a proof tree by chain­ ing off those rules, and learning alters the structure of the domain theory by adding new inference rules . More­ over, in both cases this process may affect the efficiency of recognition, but no induction is involved. 5

However, the basic operations used in the two frame­ works differ radically. Explanation-based learning mod­ ifies the knowledge base through a 'knowledge compi­ lation' mechanism. The structure of an explanation is compiled into a new inference rule; this lets the per­ formance system bypass intermediate terms on future cases with the same structure, giving shallower expla­ nations. In contrast, our approach creates new inter­ mediate terms, leading to deeper explanation structures on future cases. One can view RINCON's mechanism for creating new terms as a 'decompilation' process - the inverse operation of that in explanation-based systems.

Our experimental results indicate it is sometimes bet­ ter to operationalize than to introduce intermediate con­ cepts. An obvious extension to RINCON would be to include a mechanism for knowledge compilation in addi­ tion to that for new term creation. Upon encountering a previously unseen situation, the system would extend the knowledge base, generating new terms in the pro­ cess. Upon recognizing a previously seen case, it would construct a compiled rule for matching the instance in a single inference step. To determine whether the compiled or uncompiled knowledge was more efficient, the system would keep statistics on each rule, eventually eliminating ones with low utility [Minton, 1988]. Such an extension would constitute an important step towards unifying in­ ductive and analytic approaches to learning.

4.2 Relation to incremental concept formation

Gennari, Langley, and Fisher [1989] have reviewed work on incremental concept formation . In this framework one incrementally induces a taxonomy of concepts, which can then be used in classifying new instances and in making predictions. Each instance is sorted through the taxon­ omy, altering the knowledge base in passing.

Such learning can be characterized as an incremental form of hill climbing, in that only a single concept hierarchy is retained in memory. Examples of concept for­ mation systems include Levinson's [1985] self-organizing system, Lebowitz's [1987] UNIMEM, Fisher's [1987] CoB­ WEB, and Gennari et al.'s [1989] CLASSIT.

5 In incremental mode, one can view RINCON as changing the deductive closure of its knowledge base, since it accepts new instances as input . However, the system does not move beyond the instances it is given.

The learning method in RINCON can be viewed as a form of incremental concept formation. The domain the­ ory constitutes a taxonomy, with primitive predicates as the most general concepts, instances as the most specific concepts, and defined terms as concepts of intermediate generality. New instances are 'sorted' down this concept hierarchy, and new concepts are introduced in the pro­ cess . RINCON's search control is an incremental form of hill climbing, preferring new terms that will be used by more existing concepts.

However, there are also some important differences be­ tween the two approaches. Research on concept forma­ tion has typically focused on attribute-value representa­ tions, whereas RINCON employs a relational formalism. Most concept formation methods construct disjoint tax­ onomies, whereas RINCON forms a nondisjoint hierarchy in which a concept may have multiple parents. Finally, most earlier methods have employed partial matching techniques in the classification process, which let them make predictions about unseen data. In contrast, our approach uses complete matching and thus only sum­ marizes the observed instances.

The last difference suggests extensions to RINCON that would let it move beyond the data to make predictions about unseen instances (i.e., to do induction). The cur­ rent system allows disjunctions only at the final level of the concept hierarchy, but the basic learning operator can be extended to create disjuncts at any level. The in­ troduction of multiple disjuncts into a concept definition leads to coverage of unseen instances. A more radical ap­ proach involves deleting these structures entirely, so one need not match against them at all. In either case, the system would need to collect statistics to estimate the desirability of such drastic actions.

4.3 Relation to representation change

Another active area of machine learning research fo­ cuses on changing representations by introducing new terms into the language of concept descriptions. For in­ stance, given a primitive set of features , a learning sys­ tem might define new terms as conjunctions or disjunc­ tions of these features, and then attempt to induce a con­ cept description over this extended language. A variety of researchers have taken this general approach to repre­ sentation change in induction [Fu and Buchanan, 1984, Schlimmer, 1987, Muggleton, 1987, Pagallo and Haus­ sler, 1988, Rendell, 1988].

RINCON's learning method involves a variety of rep­ resentation change. When the system introduces a new concept into its domain theory, it redefines existing con­ cepts using this term. Also, it uses these intermediate terms during the matching process to redescribe new in­ stances . The more concepts in which an intermediate term is used, the more efficiently the system matches or rejects new instances. Thus, the change in representa­ tion has a definite impact on performance.

Muggleton's [1987] DucE system employs constructive induction in much the same way as RINCON, but has more operators for introducing new concepts. However, before a new concept is actually retained, the user is required to either accept or reject the concept. DucE's main goal is to maximize the symbol reduction of the rule base while creating meaningful intermediate concepts. On the other hand, RINCON's main goal is to improve the domain theory's efficiency of recognizing instances. Also, RINCON processes instances incrementally and handles relational input whereas DucE is non-incremental and is limited to propositional calculus.

With the exception of Fu and Buchanan [1984], most earlier research on representation change has empha­ sized classification accuracy rather than efficiency. An­ other difference between RINCON and other approaches involves its use of a relational formalism rather than a feature-based language. However, our work to date has dealt only with introducing new conjunctive terms. Future versions of RINCON should introduce disjunctive relational terms as well, as do most other methods for representation change.

4.4 Relation to pattern matching

Research on production-system architectures has led to algorithms and data structures for efficient pattern matching. One of the best-known schemes involves rete networks [Forgy, 1982], a memory organization that al­ lows sharing of redundant conditions and storage of par­ tial matches. This technique leads to significant reduc­ tions in the match time required for certain large pro­ duction systems. 6

The rete network approach to matching has many sim­ ilarities to RINCON's scheme. In both cases, the perfor­ mance element stores partial matches at nodes in the network. More important, both methods construct in­ ternal nodes for this purpose, based on shared structures in the inputs. Finally, in both cases the resulting 'do­ main theory' is purely conjunctive, in that internal nodes have only one definition.

However, RINCON also differs in some significant ways from systems based on rete networks. First, Forgy's framework assumes a binary network, in which each in­ ternal node is defined as the conjunction of two other nodes. In contrast, our system can use an arbitrary number of nodes in its definitions. Second, methods for constructing rete networks typically detect shared structures only if they occupy the same positions in the condition sides of productions , and they automatically create nodes when they are found . RINCON carries out a more sophisticated search for shared structures, and it employs an evaluation function to select among alterna­ tive concepts that it might construct . Thus, our scheme can be viewed as a heuristic approach to constructing generalized rete networks, and future work should com­ pare the two methods empirically.

Levinson's [1985] work on self-organizing retrieval for graphs also extends Furgy's idea of improving retrieval efficiency by creating intermediate concepts. As in RINCON, intermediate concepts correspond to common structures found among the relational examples stored in the database. They may be added or deleted accord­ ing to a heuristic information-theoretic measure of re­ trieval efficiency. Levinson's experiments in the retrieval of chemical structures show that introducing intermedi­ ate concepts results in only a fraction of the database (on the order of the log of the number of elements in the database) being compared to the query structure dur­ ing retrieval. He also provides theoretical justification for this increase in efficiency. This reduction in search is critical in structured domains, in which the cost of comparison is potentially exponential in the size of the objects being compared.

6 Miranker [1987) has presented evidence that, in some cases, using intermediate nodes leads to slower matching. This corresponds to the 'flat' domain theory we used in our experiments; thus, our initial results side with rete networks.

5 Conclusion

RINCON incrementally learns domain theories from ex­ amples with the goal of maximizing classification effi­ ciency. The version described in this paper is only an initial step toward our goal of integrating inductive and explanation-based learning. We have focused here on as­ pects of the efficient use of knowledge, but future work should also address induction and the associated goal of maximizing classification accuracy.

Our preliminary results indicate that introducing in­ termediate concepts into a domain theory can increase overall match efficiency. This result seems counter to the work on explanation-based learning, which holds that operationalization is the key to efficiency. However, our results suggest that both views are correct. By adding an operationalization component to RINCON, we will be able to explore the efficiency tradeoff between opera­ tionalization and introducing new intermediate concepts .

Finally, the RINCON framework is also closely related to research in the areas of incremental concept forma­ tion, representation change, and pattern matching. Our work impacts each of these areas and provides a frame­ work for integrating these diverse fields.

Acknowledgements

We have benefited from discussions with Robert Levinson at the University of California, Santa Cruz. We would also like to thank Wayne lba, John Gennari , and Mike Pazzani for their discussions on this work .