Building Robust Learning Systems by Combining Induction and Optimization

1 Introduction

Research on methods for learning concepts from examples occupies a central position in the discipline of machine learning (Michalski, Carbonell, & Mitchell, 1983). Among those who study the problem of learning from ex­ amples, it is now widely recognized that each concept de­ scription language and search strategy has an inherent in­ ductive bias. Mitchell (1980) defined inductive bias as "any basis for choosing one generalization over another, other than strict consistency with the observed training in­ stances." In our research, we give the term inductive bias a functional defmition. Given a set of examples, an induc­ tive bias is a function that produces a hypothesis, mapping points from a space of input representations to points in a space of output representations. In this paper we focus on inductive systems that produce functions that map a set of input values to a single output function value. A partial list of inductive systems conforming to this restriction in­ cludes: neural nets (Rumelhart & McClelland, 1986), re­ gresssion (Box, Hunter, & Hunter, 1978), decision-trees (Rendell1983; Quinlan 1983; Breiman, Friedman, Olshen, & Stone, 1984), logic-based approaches (Michalski, 1983), and exemplar-based approaches (Smith & Medin, 1981).

The best inductive bias for a given problem depends heavily on the user's objectives (i.e., hypothesis credibility metric). For instance, if the predominant objective is to produce a hypothesis that is easy to comprehend, a good inductive bias might represent hypotheses as English sentenc­ es or graphic representations. In other cases, when predic­ tive accuracy is the primary concern, neural nets, decision trees, and mathematical equations may be preferable. Given the diversity of user objectives, it is clear that no single in­ ductive bias can be optimal for all situations.

*This research was sponsored in part by the National Science Fmmdation (DMC-8657116) and by the Applied Intelligent Sys­ tems Group of Digital Equipment Corporation.

To address this problem, our research seeks to produce a robust inductive system in accordance with the methodology first described in Rendell, Seshu, and Tcheng's (1987) dis­ cussion of the Variable-Bias Management System (VBMS). The original VBMS paper laid out three methods for devel­ oping robust learning systems: integration, optimization, and meta-learning. Integration involves the representation of unique inductive biases as points in a multi-dimensional space (inductive bias space). Optimization is a method for searching inductive bias space. Meta-learning is a method for selecting an appropriate bias optimization strategy based on characteristics of the current problem.

In this paper we present the results of tangible progress towards integration and optimization. To integrate existing inductive biases, we developed the Competitive Relation Leamer (CRL), a system that manages a set of diverse induc­ tive biases to produce hybrid concept representations. To optimize inductive bias, we developed an optimization algo­ rithm called the Induce and Select Optimizer (ISO) and ap­ plied it to the problem of optimizing CRL's inductive bias.

In what follows, we first suggest that well known deci­ sion-tree building algorithms such as ID3 (Quinlan, 1986), PLS1 (Rendell, 1983), and CART (Breiman et al., 1984), as well as recently developed hybrids like Utgoffs perceptron trees (1988), can all be viewed as partial instantiations of an abstract class of algorithms we call recursive splitting algo­ rithms. Second, we describe CRL, a generalized recursive splitting algorithm (Tcheng, Lambert, & Lu, 1989) that provides a framework for integrating multiple methods for function approximation (learning strategies), multiple meth­ ods for breaking problems into subproblems (decomposition strategies), and multiple methods for selecting the best set of subproblems to solve (decomposition evaluation functions). Next we argue that optimization is the appropriate metho­ dology for searching CRL's bias space. After a general dis­ cussion of optimization, we describe the details of ISO. Fi­ nally, we present experimental results that illustrate the cap­ abilities of both CRL and ISO. In concluding, we outline plans for applying the combined system to a large database of real-world learning problems and for learning meta-level rules for selecting inductive bias optimization strategies.

2 The CRL System

The principal factor motivating the design of CRL was the observation that the behavior of a recursive splitting algo­ rithm depends on three factors: (1) how predictions are made within regions of input space; (2) how candidate de­ compositions are generated; and (3) how candidate decom­ positions are evaluated (see also Breiman et al.., 1984). Analysis of traditional recursive splitting algorithms re­ veals that each method possesses only one learning strategy (i.e., a method for making predictions in each subregion), one decomposition strategy, and one decomposition evalua­ tion function. For example, 103 (Quinlan, 1983) creates n-way splits on nominal feature dimensions, selects the split that minimizes its entropy function, and assigns .the most frequently occurring class label to each subregiOn (i.e., leaf node). PLS1 creates binary splits perpendicular to scalar feature dimensions, chooses the decomposition that maximizes the difference in the output functions, and attaches the mean output value to each subregion. Utgoffs (1988) novel contribution lay in realizing that performance could be improved by putting more powerful predictors at the leaf nodes. His perceptron-tree algorithm first attempts to classify all instances with a perceptron (i.e., a network of threshold logic units). Failing that, it imposes n-way splits along nominal attribute dimensions, selects the split that minimizes its entropy function, and inserts perceptrons at the leaf nodes. Figure 1 summarizes how these algo­ rithms and CRL instantiate the three crucial component processes: prediction, decomposition, and evaluation.

Any fixed combination of prediction, decomposition, and evaluation strategies may be ideal for a particular class of problems, but will fail to provide optimal performance on others. The CRL system was designed to perform well across a wide range of problems. This robust performance is made possible by CRL's ability to manage multiple, competing component strategies. Such competition often results in the formation of hybrid concepts that simultane­ ously capitalize on the strengths and minimize the weak­ nesses of two or more distinct inductive biases (Schlimmer, 1987; Utgoff, 1988). The current implementation of CRL contains multiple learning strategies, multiple decomposi­ tion strategies, and multiple decomposition evaluation func­ tions. The design is modular, and new strategies can be add­ ed incrementally as long as they adhere to CRL's standard in­ put-output specifications. Below are relevant details of CRL's component strategies.

2.1 Learning Strategies

In traditional recursive splitting algorithms, predictions are made by traversing the decision tree with a given input ex­ ample and then simply returning the mean or mode of the output points in the specified subregion. Hypotheses gener­ ated by such algorithms take the form of discontinuous step­ functions. In contrast, were regression or a neural network used at the leaf nodes, at least two advantages would be reaped. The resulting hypothesis would provide a closer fit to continuous functions and fewer decompositions would be necessary. Expanding on this idea, CRL competitively ap­ plies a variety of learning strategies (i.e., inductive biases) at the leaf nodes to produce a hypothesis for each subregion. In addition to averaging, CRL can be made to fit subregions with several different models (i.e., statistical regression, neu­ ral nets, averaging, and exemplar based strategies). Compe­ tition provides the basis for choosing the learning strategy for each region that will be used to form the final hypothe­ sis. The availability of several learning strategies allows CRL to solve complex problems involving multiple mod­ els and it is one of the novel aspects of the CRL system. Beiow are the learning strategies currently implemented in CRL.

2.1.1 Mean and Mode

These strategies take either the mean or mode of all observed output vectors and return a constant hypothesis. Due to their limitations, the mean and mode learning strategies are almost always combined with one or more decomposition strategies.

2.1.2 Exemplar

The exemplar learning strategy is based on a psychological model of human concept acquisition (Smith & Medin, 1981). In the learning phase, the exemplar strategy random­ ly selects and remembers a specified number of ex~mples from the training set. In the performance phase, predictions are made by looking through all of the memorized examples and fmding the set of n-examples closest to the new exam­ ple in input space (based on normalized euclidean distance). The average of the n closest output points is returned as the predicted output value.

2.1.3 Regression Models

These learning strategies are based on the classical statistical regression model (Box, Hunter, & Hunter, 1978). CRL cur­ rently contains the linear, quadratic, logarithmic, and expo­ nential regression models.

2.1.4 Neural Net Models

The last of CRL's component learning strategies is a neural network. Neural networks are highly interconnected assem­ blies of simple computing elements which, when properly trained, can learn arbitrary input-output mappings. The particular system in CRL is a flexible model designed to let the user explore a wide range of architectures, connectiv­ ity patterns, and settings of other parameters. The network learns by the back-propagation of error signals (Rumelhart & McClelland, 1986).

2.2 Decomposition Strategies

The general idea of problem decomposition is of fundamen­ tal importance in problem solving (Newell & Simon, 1972). Equipped with a representation of the problem space and operators for moving around in that space, the problem solver's objective is to break down the given prob­ lem into subproblems whose solutions can be achieved by applying the available operators. In CRL, the operators are learning strategies and the difference to be reduced is the er­ ror of the overall hypothesis.

Mathematically, a decomposition is a function that maps every point in the parent region of input space to one subregion indexed by a subproblem number. For example, if 11 and 12 are input features, Equation (1) represents a simple binary decomposition function of the sort generated by PLSl.

In general, a decomposition function may be defined over any or all of the input feature dimensions and may map ex­ amples to two or more subregions. In traditional recursive splitting algorithms, only one algorithm for generating de­ composition functions (i.e., a decomposition strategy) is available. Because many decomposition strategies exist, CRL allows the user to specify a set of them to use in par­ allel. Below are the decomposition strategies currently de­ fmedin CRL.

2.2.1 Distance Decomposition Strategy

This decomposition strategy is a slight variation on that used by PLS 1. First, the minimal hyper-rectangle that contains all the points in input space is calculated. Then a set of candidate decompositions is generated by splitting each input feature dimension at n evenly spaced points.

2.2.2 Population Decomposition Strategy

The major disadvantage of the distance decomposition strat­ egy is that it is insensitive to the actual distribution of ex­ amples in input space. In the worst case, many of the de­ compositions generated will divide input space into two re­ gions, one containing all but one of the examples and the , other containing a single example. To avoid this problem, we have developed a method for generating decompositions which partitions input space into regions based on popula­ tion density. The result is that more densely populated re­ gions of input space undergo proportionately more decom­ position (Kadie, 1988).

2.2.3 Hyperplane Decomposition Strategy

All of the previously mentioned decomposition strategies in­ sert region boundaries perpendicular to attribute dimensions. Instead of a single attribute test, this strategy generates arbi­ trarily placed hyperplane decomposition functions (see Brei­ man et al .. , 1984). The position of the hyperplane is con­ trolled by a parameter which determines how many randomly selected input points will be used to compute the location of an origin. If this parameter is set to oo, all hyper-planes pass through the centroid of the input space vectors and the population tends to be divided equally. If this parameter is set to 1, the hyperplanes pass through a single, randomly se­ lected point (not necessarily the center), yielding a greater variety of decompositions. Once the origin has been cho­ sen, the orientation of the hyperplane is randomly deter­ mined.

2.3 Decomposition Evaulation Functions

Recursive splitting algorithms, such as ID3, typically rely on mathematical measures of a subregion's entropy to evalu­ ate decompositions. Decomposition evaluation functions of this sort favor splits that partition the input space into mini­ mally entropic regions. The logic behind such a strategy (based on information theory) predicts that regions of low entropy will be easier to learn. ·As such, entropy measures are indirect measures of the overall hypothesis error reduc­ tion that a given decomposition will bring about. In con­ trast to the entropy-based heuristic, the CRL approach to de­ composition evaluation is to measure directly the overall er­ ror reduction of a candidate decomposition by actually evalu­ ating competing learning strategies in the newly created sub­ regions (see Fig. 2). CRL's decomposition evaluation func­ tions consist of two components, a hypothesis error metric and a error validation strategy.

2.3.1 Hypothesis Error Metrics

A CRL hypothesis error metric is a function taking the actual example and predicted output vector as input andre­ turns a value indicating the error of the prediction. General purpose hypothesis error metrics include average deviation, standard error, entropy, and vector difference. The user can also define domain-specific error metrics. For example, when CRL is used to create diagnostic rules, the relative cost of false positives and false negatives can be built into the error metric and thus used to bias decomposition accord­ ingly. This advantage is unavailable to systems that use only general error metrics because such metrics are insensi­ tive to the type of misclassifications that may result from a given split.

2.3.2 Error Validation Strategies

Whereas an error metric measures the error of a prediction based on a single example, a validation strategy uses the er­ ror metric to estimate the average hypothesis error across across an entire example set. CRL currently possesses three error validation strategies, resubstitution, test-sample, and v­ fold cross validation (Breiman et al., 1984). Resubstitution tests a hypothesis on the same examples that were used to create the hypothesis. Test-sample requires the user to divide the available examples into training and testing sets. Train­ ing examples are used to form the hypothesis, and testing examples are used to estimate the error of the hypothesis. V-fold cross validation is a method for estimating the error of a hypothesis, where the number of folds is the number of groups to partition the examples into. For example, if the number of folds is 10, then the examples are randomly partitioned into 10 equal-sized groups. Next, the examples from all but 1 of the subgroups are used to create a hypoth­ esis with the given learning strategy. The accuracy of the hypothesis is then estimated using the unseen group of ex­ amples as test cases. This process is repeated for each group of examples, and the average hypothesis error is cal­ culated. When more than one learning strategy is compet­ ing, v-fold cross validation prevents learning strategies with a high degree of freedom from unjustly dominating (e.g., by memorizing all the examples).

2.4 The CRL Algorithm

Figure 2 shows how CRL takes a given set of active learn­ ing and decomposition strategies and decides which will be used to form the final hypothesis. This method is a straightforward generalization of the simple recursive split­ ting algorithm - the difference being that CRL uses a best-first search (without backtracking) strategy to evaluate multiple learning and decomposition strategy combinations in parallel. CRL begins with a single input space region containing every example and estimates the error in the re­ gion. The error of a region is determined by applying each active learning strategy to the examples and recording the error of the most accurate hypothesis.

Next, the algorithm determines whether further decom­ position will reduce the overall hypothesis error. To do this, CRL applies all active decomposition strategies and evaluates the resulting candidate decompositions by com­ puting the error of the resulting regions in the manner de­ scribed above. The most valuable decomposition, the one that brings about the greatest overall error reduction, is used to create new subregions. This process is recursively applied to each subregion until one of the following three stopping criteria is met: (1) the error of the overall hy­ pothesis ceases to decrease more than a specified threshold; (2) the number of examples in a candidate subregion falls below a specified threshold; or (3) the time consumed ex­ ceeds a specified threshold.

From the user's perspective, the main advantage of CRL is that it creates an environment in which one can easily ex­ periment with a diverse set of learning strategies without having to recode data or jump from system to system. Un­ fortunately, the diversity of choices has a cost. With so many alternative inductive biases to choose from, finding the best bias for a problem is difficult One way around the problem of bias selection is to activate a large, representa­ tive set of CRL's learning and decomposition strategies and to let them compete. This approach can be immensely ex­ pensive - especially if the user wants to ensure that all sig­ nificantly different biases are tried. We do not advocate such a brute force solution. Instead, an independent optimization system can be used to search for the inductive bias that is optimal with respect to a given set of user objectives.

To say that optimization should be used to search induc­ tive bias space is insufficient because as many optimization biases as inductive biases exist. Therefore, to complete the definition of our methodology, we must decide on a frame­ work for optimization. In the following section, we de­ scribe both weak optimization methods, such as random search, and strong methods, which themselves employ in­ ductive biases to guide the search for the optimum. Rather than choosing between weak and strong methods, we eventu­ ally propose a methodology that allows us access to both.

3. Relating Optimization and Induction

3.1 What is Optimization?

From the perspective of decision making, optimization is the process of finding the best decision among a range of un­ tested alternatives (Buchanan, 1986). Optimization prob­ lems are defined in terms of a decision space and a means for evaluating candidate decisions (the evaluator, see Fig. 3).

For example, if the goal is to design an aircraft wing that produces maximal lift, the dimensions of the decision space are attributes of the wing design (e.g., material type, wing curvature, wing length, etc.). In this case, candidate deci­ sions can be evaluated either by building and testing the wing or by estimating the wing performance through com­ puter simulation. The goal of the optimization process is to find the best point in decision space using the least effort.

An optimizer takes as input a set of examples and em­ ploys some heuristic to generate new candidate decisions. A continuum of optimization biases ranges from the weak to the strong. Random selection of candidate decisions is a weak heuristic which can be quite effective when the cost of evaluating decision points is negligible. If the cost of evaluation is high, stronger (and less efficient) selection heuristics are justified. Strong selection heuristics employ some inductive bias to create a hypothesis that describes the objective surface over decision space (see Fig. 5). This hypothesis is used to guide further selection.

Response surface fitting (Box et al., 1978) is an exam­ ple of a strong optimization strategy which uses an induc­ tive bias to aid in the selection of new candidate decisions. Response surface fitting typically uses polynomial regres­ sion to estimate the relationship between decision variables and objective score. To generate new candidate decisions, the selector component of a response surface fitting algo­ rithm first calculates the decision point maximizing its polynomial hypothesis and then selects that point as the next decision to evaluate. For each selected point, an ob­ jective score is calculated by the evaluation function and as­ sociated with the decision space point to form an example for the next iteration of polynomial regression. The pro­ cess continues until some stopping criterion is met (e.g., the objective score ceases to increase or resources are ex­ hausted).

3.2 The Induce and Select Optimizer

Recognizing that a versatile optimization system ought to posess both the strong and weak methods described above, we designed the Induce and Select Optimizer (ISO). The ISO framework is schematically represented in Figure 4.

As its name suggests, ISO includes two main compo­ nents: an inducer and a selector. The role of the inducer is to describe, for the selector's benefit, the objective surface over decision space (see Fig. 5). Optimization strategies such as response surface fitting use induction, but they are equipped with only one inductive bias (e.g., quadratic re­ gression). This is fine if the objective surface over deci­ sion space happens to be similar to a quadratic function. If it is not, however, using the induced quadratic hypothesis to guide the selection of new decisions adds little benefit, and may actually impede progress toward the optimum. ISO escapes this limitation because its inducer manages a collection of competing inductive biases. With many in­ ductive biases to choose from, the inducer within ISO has a much higher probability of accurately describing the objec­ tive surface over decision space. ISO is, therefore, much more likely to find a strong optimization method.

The second component of ISO is its selector. Selection is the process of using both the examples and the induced hypothesis to guide the selection of new candidate decisions. In ISO, selection is based on two control parameters called novelty and performance. A high novelty setting causes ISO to prefer points in decision space that are maximally distant from those already attempted. If novelty were the only consideration, ISO would ignore the induced hypothesis describing the objective surface over decision space, and in­ stead perform random, non redundant search. If performance were the only consideration, ISO would attend only to the induced hypothesis, choosing new candidate decisions that maximize that hypothesis. In this way, the novelty and per­ formance parameters allow ISO to exhibit both strong and weak optimization biases.

4 Optimizing Inductive Bias With ISO

The availability in CRL of multiple decomposition strate­ gies, learning strategies, and decomposition evaluation func­ tions increases the size of the inductive bias space through which ISO may search. Here we encounter a classic trade­ off. Larger search-spaces are more likely to contain better solutions, but they are also more difficult to search. In this section we describe how ISO optimizes hypothesis credibili­ ty over CRL's inductive bias space.

Conceptually, CRL's bias space is a feature space defined by a set of variables that jointly specify which learning and decomposition strategies to use, their control parameters, the hypothesis error metric, how the hypothesis error is to be measured, and the minimum error reduction needed to justify a decomposition. Simply put, a point in bias space com­ pletely determines CRL's hypothesis formation behavior.

By selecting which component processes are eligible to be considered, the experimenter defines the region of CRL's inductive bias space in which ISO can seek an optimum. In the first stage of optimization, ISO probes randomly in bias space. Each probe (X) is evaluated by forming a hypothesis with the prescibed inductive bias. The bias point (X) is as­ sociated with the achieved hypothesis credibility (0) to form an example. These examples are fed to the induction com­ ponent of ISO. The inducer within the optimizer outputs a hypothesis (O(X)) that describes the credibility surface over bias space. The selector component of the optimizer uses O(X) and the existing examples to select the next point in bias space to evaluate. This process is the same as that de­ scribed in Figures 4 and 5, but the decision space is CRL's inductive bias space, and the objective surface is defined in terms of hypothesis credibility (e.g., accuracy, evalution cost, formation cost, comprehensibility, etc.).

5 Experimental Results

CRL's task in this example is to predict the surface roughness of a machined part based on the control parameters of the cutting tool and on the dimensions of the work piece. Examples were generated by a mechanistic simulator for the turning process (Boothroyd, 1975). The simulator mapped four input variables- feed rate (F), depth of cut (D), nose radius (N), and work piece diameter (W) to one output variable - surface roughness (S). Noise was added to the examples so they would more closely approximate real world observations.

For this problem, the user's objective was defined in terms of two factors: hypothesis accuracy (in terms of the variance between predicted and actual outputs) and hypothe­ sis formation time. Accuracy was measured by training ISO on 200 examples and testing on 1000 different exam­ ples. For each trial, both training and testing examples were randomly selected. Hypothesis formation time was controlled by an ISO control parameter that placed an upper limit on the amount of CPU time that could be used to form any single hypothesis. For the results reported below, the time limit was 600 CPU seconds (on a SUN/3 180 with 24 Meg).

Figure 6 shows the two best CRL hypotheses produced during the optimization process. Figure 7 shows CRL's performance improvement over time with a 95% confidence interval for the mean hypothesis error superimposed. The minimum possible error was 100 because of the amount of noise added to the examples. The actual function used by the turning simulator to predict surface roughness is given in Equation (2).

Note that only 2 of the 4 input variables were actually arguments to the target function, and that CRL did not pos­ sess a learning strategy that could adequately solve the problem without decomposition.

The Best CRL Hypothesis ...

Figure 6. The two best hypotheses produced by CRL.

To form a basis for comparison, the problem was also at­ tempted with PLSI, a neural network, and linear regression, where each of these strategies received optimization roughly equivalent (in CPU seconds) to that received by CRL. The accuracies of the best hypotheses from each method are sum­ marized in Figure 8.

I

6 Conclusions and Future Research

The work presented here reflects initial progress toward our ultimate goal: an inductive system which takes as input a problem description (consisting of examples and the user's objectives), returns the hypothesis which is optimal with re­ spect to those objectives, and improves its performance over time by learning from problem solving experience. There is more work to be done before such a system is a reality.

Obvious extensions to the existing implementation in­ clude the addition of more component strategies. We plan to add logic-based learning strategies such as AQ (Michalski, 1983), more sophisticated decomposition strategies (that go beyond binary splits), improved selection strategies for ISO (e.g., genetic optimizers (Holland, 1975) and simple hill climbing), and facilities for feature selection and construc­ tion.

Beyond adding component strategies to the existing framework, the framework itself needs to be expanded before the system will learn from its own experience. For exam­ ple, we have shown how an optimizer can be used to find a good inductive bias for a particular problem. However, opti­ mizers themselves have biases such as the method for gener­ ating an initial candidate decision to evaluate. ISO begins the optimization process by generating a candidate decision randomly. The system would be more efficient, however, if it possessed meta-level knowledge relating problem charac­ teristics (e.g., number of examples, number of features, type of features, problem domain, maximum hypothesis forma­ tion time, etc.) to good points in inductive bias space at which to begin optimization.

To gain this added efficiency, we are currently in the pro­ cess of implementing the third component of the VBMS framework: meta-learning. Meta-knowledge takes the form of hypotheses that relate problem characteristics to optimal points in inductive bias space (or at least good points at which to begin further optimization). There are at least two approaches to learning this relationship: (1) The sys­ tem could take problem-description/optimal-bias pairs (saved from past experience) as examples and do induction as usual to learn Best-Bias(Problem). To select a bias point for a particular problem, the system just evaluates this function with the current problem description as its ar­ gument; or (2) The system could take problem/bias/ objective-score triples (saved from optimization experience) and induce the function describing the objective surface over problem/bias space [i.e., Objective(Problem, Bias)]. To use this function to select the best starting point in in­ ductive bias space, one replaces the problem argument with the current problem description and optimizes Objec­ tive(Bias) in the usual manner. Eventually, we plan to test these meta-learning strategies on a large database of real­ world machine learning problems (Aha, 1989).

In closing, it is important to emphasize that this partic­ ular implementation is just the beginning of a much larger project. It reflects, for the most part, the work of a small group of researchers working primarily on engineering problems. Achieving the three design goals of VBMS (integration, optimization, and meta-learning [Rendell et al, 1987]) was relatively easy in such a small, focused group. The challenge over the long term, however, is to achieve these design goals at the level of entire scientific commu­ nities. In this paper, we have taken some small steps to­ ward that end.

Acknowledgements

Special thanks to Dr. Guangming Zhang for help in run­ ning the turning simulator. Thanks also to David Lambert and Dr. Barbara O'Keefe for helpful comments on an earlier draft. Funding for this research was provided in part by the Applied Intelligent Systems Group of Digital Equipment Corporation, by the National Science Foundation (DMC8657116).