Process-Oriented Estimation of Generalization Error

1 Introduction

Overfitting avoidance is a central problem in machine learning. If a learner is sufficiently powerful, whatever representation and search methods it uses, it must guard against selecting a model that fits the training data well but captures the underlying phenomenon poorly. Cur­ rent methods to address this problem fall into two broad categories. Data-oriented evaluation uses separate data to learn and validate models, and includes methods like cross-validation [Breiman et al., 1984; Stone, 1974], the bootstrap [Efron and Tibshirani, 1993], and reduced­ error pruning [Brunk and Pazzani, 1991] . It has several disadvantages: it is often computationally intensive, re­ duces the data available for learning, can be unreliable if the validation set is small, and is itself prone to overfit­ ting if a large number of models is compared [Ng, 1997]. Representation-oriented evaluation seeks to avoid these problems by using the same data for training and v~li­ dation, but a priori penalizing some models. Baye~tan approaches in general fall into this category (e.g., [Chick­ ering and Heckerman, 1997]). Representation-oriented measures typically contain two terms, one reflecting fit to the data, and one penalizing model complexity (e.g., [Rissanen, 1978]). This approach is only appropriate when the simpler models are truly the more accurate ones, and there is mounting evidence that this is typ­ ically not the case [Domingos, 1998a; Jensen and Co­ hen, 1998]. Structural risk minimization [Vapnik, 1995; Shawe-Taylor et al. , 1996] and PAC learning [Kearns and Vazirani 1994] are representation-oriented methods that ' . seek to bound the difference between training and generalization error using a function of the model space's (effective) dimension. This typically produces bounds that are overly broad, and requires severely restricting the model space.

We believe the limitations of representation-oriented evaluation stem from ignoring the search process by which candidate models 1 are obtained. A learner with an unlimited model space can avoid overfitting as long as it attempts only a limited number of models (even if it is not possible a priori tci predict which). Intu­ itively, the more search has been performed to obtain a model, the higher its expected generalization error ~or a given training-set error. In a recent paper [Domm­ gos, 1998b] we made this intuition precise and applied the resulting formulas to the CN2 rule learner [.Clark and Niblett , 1989], obtaining systematic improvements in generalization error and theory size. However, for the sake of simplicity the treatment in [Domingos, 1998b] made two rather artificial assumptions: that all error rates are a priori equally likely, and that a model's gen­ eralization error can be roughly estimated by treating all previously-generated models as having similar gen­ eralization errors. In this paper we remove these two assumptions, interpret the result, and successfully apply it to CN2.

2 Process-Oriented Evaluation

Suppose learner Lm consists of drawing m hypotheses at random (independently) from some model space, andre­ turning the one with lowest error on a training sampleS. Let hm; be the ith hypothesis generated by Lm. If hm,;'s true er~or rate is Em,i and S consists of n independently drawn examples, the number of errors em,i committed by hm,i on S is a binomially distributed variable with parameters nand Em,i:

1 By "model" we mean model structure and parameter values.

Let B(em,i ln, Em,i) be the probability that the number of errors is greater than em,i:

Notice that this notation is the opposite of the usual notation for a cumulative distribution function (i.e., B(eln, E) = 1 - BinomiaLcdf(eln, E)). It will be more convenient for what follows.

The probability of Lm returning a hypothesis hm that misclassifies em training examples is the probability that at least one of the m hypotheses hm,i makes em errors, and all the others make em or more errors. Equivalently, it is the probability that all hypotheses hm,i make more than em - 1 errors, minus the probability that they all make more than em errors:

where~ = (Em,1, ... , Em,i, .. . , Em,m)· By Bayes' theo­ rem:

Let hm,c be the hypothesis with lowest error (i.e., the "chosen" hypothesis, so that learner Lm returns hm,c and em = em,c)· Our goal· is to predict hm = hm,c's true error rate Em = Em,c from em. For this purpose, we marginalize Equation 4 over all the em,i save em,c: 2

where the integral is multiple, over all components of tm save Em,c· The expected value of Em,c can now be computed by integration:

2 This is where we previously assumed that \:/; fm,i = fm,c and dropped the prior p(€,.,) .

Substituting Equation 3 into 5 and 5 into 6, using the as­ sumption of independent hypotheses, and assuming the same prior p(Em,i) for all hypotheses, we obtain the fol­ lowing expression:

For all but the smallest n, F » f (Equations 7, 8, 1 and 2). Thus, using the binomialexpansion of (F + f)m we obtain that (F + f)m - pm ~ mf pm-1, (F + f)m-1 - pm-1 ~ (m -1)/ pm-2' and (F + f)m-1 ~ pm-1. Sub­ stituting these into Equation 11 and simplifying, we ob­ tain:

Let E~~ = em/n be the maximum likelihood estimate of Em,c: For sufficiently large n, Eb[Em,c] ~ E~,~ (Equa­ tion 9, given a well-behaved prior p(Em,c), i.e., as long as p(Em,c) -:j:. 0 in the neighborhood of Em,c = em/n). Let E:!:,:~or = J 0 1 Em,cP( Em,c) dEm,c be the prior expected value of Em,c· Suppose a beta or similarly bell-shaped prior is used [Bernardo and Smith, 1994]; this is what makes in­ tuitive sense for error rates. In general em/n (the inflec­ tion point of B(emln, Em,c) as a function of Em,c) will fall below E:!:,:~or (the peak of the prior), since em will tend to zero as more hypotheses are generated and the one with lowest error selected. Then, for sufficiently large n, B(emln, Em,c) ~ 1 over the entire range where p(Em,c ) is significantly greater than zero (leaving out only the left tail of the distribution) , and EB(Em,c] ~ E:!:,:~or (Equa­ tion 10). Making these substitutions we finally obtain (omitting the c indexes, since Em = Em,c):

This formula is quite similq.r to the well-known Laplace correction or m-estimate [Cestnik, 1990]. Its role for the number of hypotheses is similar to the m-estimate's role for the number of examples. The m-estimate grad­ ually changes from the maximum likelihood estimate to the prior as the number of examples decreases; similarly, Equation 13 gradually uncovers the prior as the number of hypotheses generated increases. The intuitive mean­ ing of Equation 13 is clear: when a learner generates a series of hypotheses and returns the one with lowest training-set error, the more hypotheses it generates the less sure we are that the observed error corresponds to the true error, and the more weight should be given to the a priori expected error.

This result is intuitively satisfying, because it gives a mathematical basis for increasing model uncertainty as the amount of search performed increases. However, Equation 13 as it stands is of limited practical use, be­ cause it converges very rapidly to E;;,rior as more in­ dependent hypotheses are generated. As a result, for all but the earliest few hypotheses, the error estimate EJEmln, em] is quite insensitive to the empirical error Em L. This effect, however, is at least partly due to the fact that hypothesis dependences are being ignored, and as a result the empirical error of one hypothesis carries no information about the true error of another. In par­ ticular, only the empirical error of the chosen hypothe­ sis carries information about its true error, resulting in the chosen hypothesis' expected error being the unal­ loyed prior in all a priori possible situations where the minimum empirical error is not the chosen hypothesis' (Equation 3) . In practical learners, on the other hand, the hypotheses generated are typically very strongly de­ pendent. Thus, in general, all the empirical errors ob­ served will carry information about the true error of the chosen hypothesis, and Equation 13 should converge cor­ respondingly slower to the prior term E;;,rior. We pro­ pose to model this by replacing m in Equation 13 by a slower-growing function of m, which can be thought of as the "effective number of independent hypotheses attempted." For example, attempting ten hypotheses with given dependences between them may be equiv­ alent (with respect to the convergence of Equation 13 to E;;,rior) to attempting two independent hypotheses. Thus, Equation 13 provides a simple way of combin­ ing data-oriented, representation-oriented and process­ oriented information when estimating generalization er­ ror: E~ L is the data-oriented component (the model's empirical error), E;;,rior is the representation-oriented component (a function of the model's form) , and m is the process-oriented component (a function of the search process that led to the model).

3 Application to Rule Induction

Most rule induction systems employ a set covering or "separate and conquer" search strategy [Michalski, 1983;

Clark and Niblett, 1989] . Rules are induced one at a time, and each rule starts with a training set composed of the examples not covered by any previous rules. A rule is induced by adding conditions one at a time, starting with none (i.e., the rule initially covers the entire in­ stance space). The next condition to add is chosen by attempting all possible conditions. Conditions on sym­ bolic attributes are typically of the form ai· = Vij, where Vij is a possible value of attribute ai. Conditions on nu­ meric attributes are typically of the form ai ::;; Vij or ai > Vij, where the thresholds Vij are usually values of the attribute that appear in the training set. In the beam search process :.tsed by many rule learners, at each step the best b versions of the rule according to some eval­ uation function are selected for further specialization. AQ [Michalski, 1983] continues adding conditions until the rule is "pure" (i.e., until it covers examples of only one class). This can lead to severe overfitting. The lat­ est version of the CN2 system [Clark and Niblett, 1989; Clark and Boswell, 1991] uses a simple and effective Bayesian method to combat this: induction of a rule stops when no specialization improves its error rate, and the latter is computed using a Laplace correction or m­ estimate. If nr is the number of examples covered by a ruler, and er is the number of those examples it misclas­ sifies, the conventional estimate of the rule's error rate is er 1 nr, but its m-estimate is:

where Eo is the rule's a priori error, which CN2 takes to be the error obtained by random guessing if all classes are equally likely: Eo = ( c-1) I c, where cis the number of classes. This prior value is given a weight of m examples (i.e., the behavior of Equation 14 is equivalent to having m additional examples covered by the rule, one of each class). CN2 uses m=c. As conditions are added, the rule covers fewer and fewer examples, and Er tends to Eo. Thus a rule making more misclassifications may be preferred if it covers more examples, causing induction to stop earlier and reducing overfitting. Clark and Boswell [1991 J found this version of CN2 to be more accurate than C4.5 [Quinlan, 1993] on 10 of the 12 benchmark datasets they used for testing. However, this scheme ignores that, as more and more conditions are attempted, the probability of finding one that appears to reduce the rule's error merely by chance increases. This will lead the m-estimate to underestimate the chosen condition's true error, and CN2 to overfit. The upward correction made to Er should increase with the number of conditions attempted. The process-oriented evaluation framework described in the previous section allows us to do this in a systematic way, as follows.

Equation 13 can be used to compare the hypotheses returned by k learners £ 1 , ... , Lm, ... , Lk , and choose the one with lowest predicted error. It can also be used to compare successive stages of the same learner, by taking Lm 2 to be the result of continuing the search of learner Lm 1 (m1 < m2) with m2 - m1 more hypotheses. In particular, the successive stages can be the successive versions of a rule returned by CN2 or a similar "sep­ arate and conquer" rule learner. A natural choice for the prior expected error f.;=:,r~or for all rule versions is the default error rate, obtained by always predicting the most frequent class in the training set. The choice of slower-growing function of m is less obvious. One pos­ sibility ism'= logm (form> 1), based on an analogy with decision tree induction. When learning a tree using an algorithm like C4.5, each new hypothesis is obtained by modifying the previous one in only a fraction of the instance space (the fraction corresponding to the node currently being expanded), and this fraction becomes exponentially smaller as induction progresses. Only an entire new level of the decision tree corresponds to an entirely new hypothesis. Since the depth of the tree grows approximately with the logarithm of the number of nodes, we can take the equivalent number of indepen­ dent hypotheses attempted m' to be proportional to the logarithm of the total number of hypotheses attempted m. Since a rule corresponds to a path through a decision tree, both in its content and in the way it is induced by a system like CN2, we can apply a similar line of reasoning to the number of rules attempted. 3

Let each hypothesis be one version of the rule at­ tempted during the beam search. Equation 13 does not need to be computed for every rule version generated during the beam search. This would introduce a prefer­ ence for adding some conditions instead of others, which is unlikely to produce good results unless there is do­ main knowledge supporting such preferences. Instead, Equation 13 can be computed only once for each round. One round consists of generating every possible one-step specialization of each rule version in the beam, and se­ lecting the b best. Thus, if there are a attributes and v is the maximum number of values of any attribute

3 In the experiments described below, the results were not sensitive to the base of the logarithms used. Base 2, base e and base 10 all yielded practically indistinguishable error rates and theory sizes. The results reported are for base 2.

(in the worst case, v = n for numeric attributes), one round corresponds to O(bav) rule versions. Let mk be the total number of rule versions generated up to, and including, round k. Round 1 consists of the initial rule with no conditions, and m1 = 1. Induction stops when E[€mklnmk,emk]2: E[€mk_1 lnmk-t>emk_1 ], fork> 1.

4 Experiments

In order to test the effectiveness of process-oriented eval­ uation, default and process-oriented versions of CN2 were compared on the benchmark datasets previously used by Clark and Boswell (1991]. 4 The process-oriented versions were implemented by adding the necessary fa­ cilities to the CN2 source code. Details of the earlier version of POE and its implementation can be found in [Domingos, 1998b]. CN2's Laplace estimates are still used to choose the best b specializations in each round. This is preferable to using uncorrected estimates, since as implemented POE has no preference between hypotheses within the same round, and this is also a factor in avoid­ ing overfitting. However, the Laplace correction distorts the value of €:;; L used in Equation 13. This will be par­ ticularly pronounced when there are many classes, since CN2 uses m = c. In order to minimize this problem, m = 2 was used with POE. 5

The experimental procedure of [Clark and Boswell, 1991] was followed. Each dataset was randomly divided into 67% for training and 33% for testing, and the error rate and theory size (total number of conditions) were measured for default CN2, CN2-POE1 (the earlier ver­ sion) and CN2-POE2 (the version described in this pa­ per). This was repeated 20 times. The average results and their standard deviations are shown in Table 1; 6

4 With the exception of pole-and-cart, which is not avail­ able in the UCI repository [Blake et al., 1998] .

5 Simply changing m = c to m = 2 in default CN2 does not change its performance on the datasets used.

6 There are some differences between CN2's results and those reported in [Clark and Boswell, 1991] . This may be due

the results for CN2 and CN2-POE1 are from [Domin­ gos, 1998b].

Compared to CN2-POE1, CN2-POE2 roughly main­ tains accuracy (lower error in five datasets, higher in five, same in one; 0.2% lower error on average) while reduc­ ing theory size in most datasets (lower in seven, higher in four, 4.5 fewer conditions on average). This indicates that Equation 13 is successfully deleting unnecessary conditions that the previous method retained. Being in closed form, Equation 13 is also much more efficient to evaluate than the integrals in [Domingos, 1998b]. Ex­ periments on two larger UCI databases (shuttle and let­ ter) showed CN2-POE2 learning faster than CN2, while maintaining accuracy and reducing theory size.

5 Related Work

The literature on model selection and error estimation is very large, and we will not attempt to review it here. Several pieces of previous work take into account the number of hypotheses being compared, and so can be considered early steps towards process-oriented evalua­ tion. This includes notably systems that use Bonferroni corrections when testing significance (e.g., [Gaines, 1989; Jensen and Schmill, 1997]; see also [Klockars and Sax, 1986]). A key difference between these systems and what is proposed here is that they require a somewhat arbi­ trary choice of significance threshold, while this paper directly attempts to optimize the end goal (expected gen­ eralization error). Also, the Bonferroni correction does not take hypothesis dependencies into account, while the present framework offers (at least in principle) a way of doing so.

Quinlan and Cameron-Jones's [1995] "layered search" method for automatically selecting CN2's beam width can also be considered a form of process-oriented evalu­ ation. While layered search and the approach proposed here have similar aims, their biases differ: layered search limits the search's width, while the present method limits its length. The latter may be more effective in reducing the fragmentation and small disjuncts problems [Pagallo and Haussler, 1990; Holte et al., 1989]. The assumptions made here are also clearer than those implicit in Quinlan and Cameron-Jones's [1995] measure.

Freund [1998] recently proposed a form of process­ oriented evaluation that is closer to the PAC-learning framework. It is an extension of the statistical query model [Kearns, 1993] that attempts to obtain tighter bounds on generalization error by considering the tree of queries that the learner could make. While the gen­ eral algorithm to obtain these bounds has exponential computational cost in the number of queries made, Fre­ und proposes a specialized version for algorithms based on local search (e.g., CN2) that is more efficient, at the price of loosened bounds. How tight the bounds will be in either case is still an open question; no empirical test­ ing of Freund's [1998] method has been carried out so far. These bounds could be used for model selection by preferring the model with the lowest upper bound (for given parameters). However, as with Bonferroni correc­ tions, the result will in general depend on the choice of parameters, for which there is no clear criterion. While the approach proposed in the present paper directly ob­ tains an estimate of the generalization error, it would also be useful to have a confidence interval for it, and Freund's [1998] method may be a path to it.

to the fact that the default version of CN2 uses a beam size of 5, whereas Clark and Boswell used b = 20. The distribution version of CN2 may also differ from the one used in [Clark and Boswell, 1991].

Evaluating models that are the result of a search process, not just of fitting the parameters of a pre­ determined structure, has traditionally not been a con­ cern of statisticians. However, this is beginning to change [Chatfield, 1995].

6 Conclusion

Two main types of model selection are currently avail­ able. In data-oriented evaluation, a hypothesis's score does not depend on its form or how the hypothesis was found , but only on its performance on the data. In representation-oriented evaluation, the score depends on the data and on the hypothesis's form, but not on the search process that led to it. Recently [Domingos, 1998b] we argued that the latter cannot be ignored, and pro­ posed process-oriented evaluation (POE) . However, in [Domingos, 1998b] we assumed that all models searched had similar true error rates, and that all error rates were equally likely a priori. In this paper we removed these assumptions, and derived a simple approximation for the generalization error of the returned hypothesis as a function of the number of hypotheses searched. This approximation is a weighted average of the maximum likelihood estimate of the error and the prior expected error, that increasingly favors the prior as more models are attempted. This approximation gives a mathemati­ cal basis to the intuition that model uncertainty should increase with the amount of search conducted.

In the future we plan to: study the statistical proper­ ties of Equation 11, in particular when the sample size is not large enough to approximate it by Equation 13; compare the method proposed here with other forms of process-oriented evaluation (e.g., Bonferroni corrections and layered search); apply it to other learners; and study methods for accurately estimating the growth of the ef­ fective number of hypotheses m' in each of these learners.