Layered Concept-Learning and Dynamically Variable Bias Management

1. Representational Bias

Given a language such as DNF logic, the specific elements of the language (e.g. function symbols or attributes) and con­ straints on it (e.g. few disjuncts) are the biases that the user or system may control. The manifestation of bias as a variable number of disjuncts (Utgoff, 1986) is a special case of an imposed model: In uncertain environments, "number of dis­ juncts" becomes the number of peaks in the utility function. Additional constraints may confine the functional form (e.g. a linear combination of features - see Rendell, 1983). While functional forms such as the number of disjuncts are straight­ forward to modify, not all representational biases are easy to implement. For example, the choice of features is a complex research problem (Porter, 1986).

2. Algorithmic Bias

Given a hypothesis language having a particular representat ional bias, a concept learning algorithm is designed to search in an associated space for credible hypotheses that approximate the target concept. Since the learned concept may depend on details of the search, algorithms and algorithm components are also biases. Just as hypotheses space contains the desired concept, "algorithm space" contains the desired algorithm for finding it. (We could think of algorithm space as being the subpace of the entire bias space that has to do with algorithms only.) Just as the target concept for the current domain problem is extracted from hypotheses space, a . well- behaved algorithm for the current learning problem is extracted from algorithm space.

Depending on our representation of algorithm space, it could be more or less grainy. A very grainy algorithm space might contain a few fixed concept learning systems, such as AQ, ID3, PLSl , etc. (Michalski, l983; Quinlan, 1983; Ren­ dell , 1983). In contrast, a refined algorithm space might con­ tain system components (such as operators for hypothesis transformation). In the simple (grainy) case. a completed. algo­ rithm would be selected · as a unit; in the complex I refined) case, the algorithm would be constructed from its components.

B. Initial Implementation

To initiate testing of variable-bias management, we wanted to begin with one of the simpler kinds of bias. We decided to begin with algorithmic biases and have the VMBS try to choose an entire learning system from a coarse algo­ rithm space. Unlike Utgoff's (1986) STABS, VMBS bases its choices on characteristics of the problem domain (although the characteristics so far are simple and syntactic).

1. First Experiment: Bias as Algorithm

In the first experiment VMBS selects one of three learning systems AQ15, ASSISTANT, and PLSl (which are dissussed in Rendell et al., 1987a). The choice is based on the behavior of these· three systems as a function of number of training events and number of features. In other words, problem space here is only two- dimensional: the number of events is on one axis, and the number of features in each event is on the other.

Table I shows results involving a lymphography data base, using the learning systems AQ15, ASSISTANT, and PLSl. Initially, VBMS tries each algorithm on each problem, until sufficient experience is accumulated (at this time the criterion for "sufficient experience" is user- supplied, although full auto­ mation will simply be information-theoretic).

The credibility measure should reflect performance, and should be include concept accuracy and processing time (meas­ ures for these are standard -- see Rendell et al., 1987a). To keep the first experiment simple, our uniform measure of cred­ ibility is just the number of user-CPU-seconds (on a VAX780 running under UNIX -- all programs were written in Pascal). In this c'ase we normalize credibility ll by just taking the quo­ tient: number of seconds used by the fastest algorithm over the number of seconds used by the given algorithm. In this case, with only three algorithms, a triplet of jl-values is associ­ ated with each point in problem space. Call these values ~J 1 (AQ15), !l 2 (ASSISTANT), and !l 3 (PLSl), and the resulting JJ­ vector ll ·

VBMS divides problem space by splitting it into orthogo­ nal rectangles, making the splits having the highest dissimilar­ ity rating (like the basic PLSl algorithm). To calculate the dissimilarity rating, VBMS first averages the }J 's for each of the three algorithms in the proposed regions. Call these aver­ ages for two tentative subrectangles jJ. 1 and jJ.'i ( 1 :::; i S 3). Next, VBMS calculates ·

I (This is based on an information- theoretic measure and should generally include an error term; see Rendell, 1983.)

2. Results of Initial Experiment

As shown in Fig. 1, VBMS split problem space into 3 rec­ tangles. The first split is perpendicular to the number-of­ attributes axis. The eight points with 14 or more event attri­ butes have an average p. of (0.03, 0.65, 1.00}, and the 3 other points have an average p.' of (0.11 , 1.00, 0.36). The dissimilar­ ity value is d = log 8 :::::::: 3.

The second split occurs with problems of 150 events (and 14 or more attributes) and problems with fewer events (but 14 or more attributes). These two regions have average p. 's of (0.03, 0.56, 1.00) and (0.04, 0.79, 1.00). The dissimilarity value is log 2.6 :::::::: 1.6. If we insist that each region have at least two points, none of the other possible splits have dissimi­ larity ratings higher than log 1.2 < 0.5.

Henceforth, VBMS expects PLSl to be twice as fast as ASSISTA.I\IT in problems with fewer than 140 events and more than 12 attributes, and it expects PLSl to be only about 20% faster for problems with 150 events and more than 12 attri­ butes. Finally, in problems with fewer than 14 attributes, VBMS expects ASSISTA.L'IT to run three times as fast as PLSl .

In future problems, VBMS can use the best algorithm for the problem to perform faster learning (the differences can be much larger than 3 to 1 -- see Rendell et al. , 1987a). The overhead for running VBMS is insignificant. Since VBMS uses fewer resources, it performs better than its subsidiary algo­ rithms. VBMS dynamically choses biases and learns to associ­ ate them with classes of problems.

VI. SUMMARY AND CONCLUSIONS

Since induction is so complex, concept formation is feasible only by reducing the search space through the use of selective biases. Biases appear in many different forms (e.g. abstracted features, acceptable concept descriptions, etc.) and are usually fixed into the design of a system. Since any fixed bias is too restrictive for some problems and too slow for others, biases should be dynamic -- for generally efficient and effective (robust) learning, we need better methods for managing bias mechanically.

Previous work on dynamic bias has been quite limited. Ctgoff's (1986) STABB includes a variable bias, but only in a form that does not learn to associate bias with knowledge about problems.

We have outlined a robust multiple -space model of learn­ ing and proposed a design for a variable- bias management sys­ tem VBMS . In this model of knowledge and meta- knowledge, learning can be viewed as a parallel search across event. hypothesis, and bias spaces. The VBMS is specifically designed to learn biases and to induce their relationships to classes of problems, and thereby to support flexible learning across different problem domains. Unlike most other learning sys­ tems,. the VBMS learns at different levels.

An inductive algorithm performs better when it outputs hypotheses of higher credibility using fewer resources. Even in initial implementation involving a coarse "algorithm space," we have shown that VBMS perJorms better any of its subsidi­ ary algorithms alone. By dynamically adjusting its bias, VBMS can select and use a strong bias appropriate to a given induction problem. Thus it can combine the efficiency of a strong bias with the generality of a weak one.

VBMS is a robust framework for probabilistic, multilay­ ered learning. Extensions include elaboration of problem space and bias space using analogy and other semantic information. These and other refinements (and algorith'ms for the system) are discussed in (Rendell et al., 1987b).