ml97 Modelselection

Machine Learning, 27, 7–50 (1997)
°
c 1997 Kluwer Academic Publishers. Manufactured in The Netherlands.
An Experimental and Theoretical Comparison

of Model Selection Methods*
MICHAEL KEARNS [email protected]
AT&T Laboratories Research, Murray Hill, NJ
YISHAY MANSOUR [email protected]

Department of Computer Science, Tel Aviv University, Tel Aviv, Israel
ANDREW Y. NG [email protected]
Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA
DANA RON [email protected]

Laboratory of Computer Science, MIT, Cambridge, MA
Editor: Philip M. Long
Abstract. We investigate the problem of model selection in the setting of supervised learning of boolean functions
from independent random examples. More precisely, we compare methods for finding a balance between the
complexity of the hypothesis chosen and its observed error on a random training sample of limited size, when the
goal is that of minimizing the resulting generalization error. We undertake a detailed comparison of three well-
known model selection methods — a variation of Vapnik’s Guaranteed Risk Minimization (GRM), an instance of
Rissanen’s Minimum Description Length Principle (MDL), and (hold-out) cross validation (CV). We introduce a
general class of model selection methods (called penalty-based methods) that includes both GRM and MDL, and
provide general methods for analyzing such rules. We provide both controlled experimental evidence and formal
theorems to support the following conclusions:
• Even on simple model selection problems, the behavior of the methods examined can be both complex and
incomparable. Furthermore, no amount of “tuning” of the rules investigated (such as introducing constant
multipliers on the complexity penalty terms, or a distribution-specific “effective dimension”) can eliminate
this incomparability.
• It is possible to give rather general bounds on the generalization error, as a function of sample size, for penalty-
based methods. The quality of such bounds depends in a precise way on the extent to which the method
considered automatically limits the complexity of the hypothesis selected.
• For any model selection problem, the additional error of cross validation compared to any other method can
be bounded above by the sum of two terms. The first term is large only if the learning curve of the underlying
function classes experiences a “phase transition” between (1 − γ)m and m examples (where γ is the fraction
saved for testing in CV). The second and competing term can be made arbitrarily small by increasing γ.
• The class of penalty-based methods is fundamentally handicapped in the sense that there exist two types of
model selection problems for which every penalty-based method must incur large generalization error on at
least one, while CV enjoys small generalization error on both.
Keywords: model selection, complexity regularization, cross validation, minimum description length principle,
structural risk minimization, vc dimension
* This research was done while Y. Mansour, A. Ng and D. Ron were visiting AT&T Bell Laboratories.
8 M. KEARNS, ET AL.
1. Introduction
In the model selection problem (sometimes also known as complexity regularization), we

must balance the complexity of a statistical model with its goodness of fit to the training data.
This problem arises repeatedly in statistical estimation, machine learning, and scientific
inquiry in general. Instances of the model selection problem include choosing the best
number of hidden nodes in a neural network, determining the right amount of pruning to
be performed on a decision tree, and choosing the degree of a polynomial fit to a set of
points. In each of these cases, the goal is not to minimize the error on the training data, but
to minimize the resulting generalization error.
The model selection problem is coarsely prefigured by Occam’s Razor: given two hy-
potheses that fit the data equally well, prefer the simpler one. Unfortunately, Occam’s Razor
does not explicitly address the more complex, more interesting and more common problem
in which we have a simple model with poor fit to the data, and a complex model with good
fit to the data. Such a problem arises when the data is corrupted by noise, or when the
size of the data set is small relative to the complexity of the process generating the data.
Here we require not a qualitative statement of a preference for simplicity, but a quantitative
prescription — a formula or algorithm — specifying the relative merit of simplicity and
goodness of fit.
Many model selection algorithms have been proposed in the literature of several different
research communities, too many to productively survey here. Various types of analysis
have been used to judge the performance of particular algorithms, including asymptotic
consistency in the statistical sense (Vapnik, 1982; Stone, 1977), asymptotic optimality
under coding-theoretic measures (Rissanen, 1989), and more seldom, rates of convergence
for the generalization error (Barron & Cover, 1991). Perhaps surprisingly, despite the
many proposed solutions for model selection and the diverse methods of analysis, direct
comparisons between the different proposals (either experimental or theoretical) are rare.
The goal of this paper is to provide such a comparison, and more importantly, to describe
the general conclusions to which it has led. Relying on evidence that is divided between
controlled experimental results and related formal analysis, we compare three well-known
model selection algorithms. We attempt to identify their relative and absolute strengths
and weaknesses, and we provide some general methods for analyzing the behavior and
performance of model selection algorithms. Our hope is that these results may aid the
informed practitioner in making an educated choice of model selection algorithm (perhaps
based in part on some known properties of the model selection problem being confronted).
Outline of the Paper
In Section 2, we provide a formalization of the model selection problem. In this formal-

ization, we isolate the problem of choosing the appropriate complexity for a hypothesis or
model. We also introduce the specific model selection problem that will be the basis for our
experimental results, and describe an initial experiment demonstrating that the problem is
nontrivial. In Section 3, we introduce the three model selection algorithms we examine in
the experiments: Vapnik’s Guaranteed Risk Minimization (GRM) (Vapnik, 1982), an in-
A COMPARISON OF MODEL SELECTION METHODS 9
stantiation of Rissanen’s Minimum Description Length Principle (MDL) (Rissanen, 1989),

and Cross Validation (CV).
Section 4 describes our controlled experimental comparison of the three algorithms. Using
artificially generated data from a known target function allows us to plot complete learning
curves for the three algorithms over a wide range of sample sizes, and to directly compare
the resulting generalization error to the hypothesis complexity selected by each algorithm.
It also allows us to investigate the effects of varying other natural parameters of the problem,
such as the amount of noise in the data. These experiments support the following assertions:
the behavior of the algorithms examined can be complex and incomparable, even on simple
problems, and there are fundamental difficulties in identifying a “best” algorithm; there is
a strong connection between hypothesis complexity and generalization error; and it may be
impossible to uniformly improve the performance of the algorithms by slight modifications
(such as introducing constant multipliers on the complexity penalty terms).
In Sections 5, 6 and 7 we turn our efforts to formal results providing explanation and
support for the experimental findings. We begin in Section 5 by upper bounding the error of
any model selection algorithm falling into a wide class (called penalty-based algorithms)
that includes both GRM and MDL (but not cross validation). The form of this bound
highlights the competing desires for powerful hypotheses and controlled complexity. In
Section 6, we upper bound the additional error suffered by cross validation compared to
any other model selection algorithm. This quality of this bound depends on the extent to
which the function classes have learning curves obeying a classical power law. Finally, in
Section 7, we give an impossibility result demonstrating a fundamental handicap suffered
by the entire class of penalty-based algorithms that does not afflict cross validation. In
Section 8, we give a summary and offer some conclusions.
2. Definitions
Throughout the paper we assume that a fixed boolean target function f is used to label
inputs drawn randomly according to a fixed distribution D. For any boolean function h, we
define the generalization error1
def
²(h) = ²f,D (h) = P rx∈D [h(x) 6= f (x)] (1)
We use S to denote the random variable S = hx1 , b1 i, . . . , hxm , bm i, where m is the sample
size, each xi is drawn randomly and independently according to D, and bi = f (xi ) ⊕ ci ,
where the noise bit ci ∈ {0, 1} is 1 with probability η; we call η ∈ [0, 1/2) the noise rate.
In the case that η 6= 0, we will sometimes wish to discuss the generalization error of h with
respect to the noisy examples, so we define
def
²η (h) = P rx∈D,c [h(x) 6= f (x) ⊕ c], (2)
where c is the noise bit. Note that ²(h) and ²η (h) are related by the equality
²η (h) = (1 − η)²(h) + η(1 − ²(h))
= (1 − 2η)²(h) + η. (3)
10 M. KEARNS, ET AL.
Thus, ²η (h) is simply a “damped” version of ²(h), and both quantities are minimized by the
same h. For this reason, we use the term generalization error informally to refer to either
quantity, making the distinction only when it is important.
We assume a nested sequence of hypothesis classes (or models)2 F1 ⊆ · · · ⊆ Fd ⊆ · · ·.
The target function f may or may not be contained in any of these classes, so we define
def def
hd = argminh∈Fd {²(h)} and ²opt (d) = ²(hd ) (4)
def
(similarly, ²ηopt (d) = ²η (hd )), where we assume for simplicity that there exists a minimum
value of ²(h) achievable by a function in the class Fd . If this were not the case we could
slightly alter the definition of ²(h) so that it have some bounded precision. The function
hd is the best approximation to f (with respect to D) in the class Fd , and ²opt (d) measures
the quality of this approximation. Note that ²opt (d) is a non-increasing function of d since
the hypothesis function classes are nested. Thus, larger values of d can only improve the
potential approximative power of the hypothesis class. Of course, the difficulty is to realize
this potential on the basis of a small sample. Note that in these definitions, we can think of
the function class index d as an abstract measure of the complexity of the functions in Fd .
With this notation, the model selection problem can be stated informally: on the basis of
a random sample S of a fixed size m, the goal is to choose a hypothesis complexity d, ˜ and a
hypothesis h̃ ∈ Fd˜, such that the resulting generalization error ²(h̃) is minimized. In many
treatments of model selection, including ours, it is explicitly or implicitly assumed that the
model selection algorithm has control only over the choice of the complexity d, ˜ but not
over the choice of the final hypothesis h̃ ∈ Fd˜. It is assumed that there is a fixed algorithm
that chooses a set of candidate hypotheses, one from each hypothesis class. Given this set
of candidate hypotheses, the model selection algorithm then chooses one of the candidates
as the final hypothesis.
To make these ideas more precise, we define the training error
def
²̂(h) = ²̂S (h) = |{hxi , bi i ∈ S : h(xi ) 6= bi }|/m, (5)
and the version space
{²̂(h0 )}}.
def
VS (d) = VS S (d) = {h ∈ Fd : ²̂(h) = min
0
(6)
h ∈Fd
Note that VS (d) ⊆ Fd may contain more than one function in Fd — several functions
may minimize the training error. If we are lucky, we have in our possession a (possibly
randomized) learning algorithm L that takes as input any sample S and any complexity
value d, and outputs a member h̃d of VS (d) (using some unspecified criterion to break ties
if |VS (d)| > 1). More generally, it may be the case that finding any function in VS (d)
is intractable, and that L is simply a heuristic (such as backpropagation or ID3) that does
the best job it can at finding h̃d ∈ Fd with small training error on input S and d. In this
paper we will consider both specific problems for which there is an efficient algorithm L
for selecting a function from the version space, and the more abstract case in which L may
be arbitrary. In either case, we define
def def
h̃d = L(S, d) and ²̂(d) = ²̂L,S (d) = ²̂(h̃d ). (7)
Note that we expect ²̂(d), like ²opt (d), to be a non-increasing function of d — by going to
a larger complexity, we can only reduce our training error. Indeed, we may even expect
there to be a sufficiently large value dmax (determined by the sequence of function classes,
the learning algorithm, the target function and distribution) such that ²̂(dmax ) = 0 always.
We can now give a precise statement of the model selection problem. First of all, an
instance of the model selection problem consists of a tuple ({Fd }, f, D, L), where {Fd } is
the hypothesis function class sequence, f is the target function, D is the input distribution,
and L is the underlying learning algorithm. The model selection problem is then: Given the
sample S, and the sequence of functions h̃1 = L(S, 1), . . . , h̃d = L(S, d), . . . determined
by the learning algorithm L, select a complexity value d˜such that h̃d˜ minimizes the resulting
generalization error. Thus, a model selection algorithm is given both the sample S and the
sequence of (increasingly complex) hypotheses derived by L from S, and must choose one of
these hypotheses. Notice that “special” model selection criteria that incorporate knowledge
about the behavior of the learning algorithm L may be appropriate in certain cases; however,
we hold that good general model selection algorithms should at least perform reasonably
well in the case that L is actually a training error minimization procedure.
The current formalization suffices to motivate a key definition and a discussion of the
fundamental issues in model selection. We define
def
²(d) = ²L,S (d) = ²(h̃d ). (8)
Thus, ²(d) is a random variable (determined by the random variable S) that gives the
true generalization error of the function h̃d chosen by L from the class Fd . Of course,
²(d) is not directly accessible to a model selection algorithm; it can only be estimated or
guessed in various ways from the sample S. A simple but important observation is that no
model selection algorithm can achieve generalization error less than mind {²(d)}. Thus the
behavior of the function ²(d) — especially the location and value of its minimum — is in
some sense the essential quantity of interest in model selection.
The prevailing folk wisdom in several research communities posits the following picture
for the “typical” behavior of ²(d), at least in the optimistic case that the learning algorithm L
implements training error minimization. (In the ensuing discussion, if there is classification
noise the quantities ²ηopt and ²η should be substituted for ²opt and ²). First, for small values
of d (d << m), ²(d) is large, due simply to the fact that ²opt (d) is large for small d, and
²(d) ≥ ²opt (d) always holds. At such small d, training errors will be close to generalization
errors (that is, ²̂(h) ≈ ²(h) for all h ∈ Fd — also known as uniform convergence, or small
“variance”3 ), and VS (d) will contain only functions whose true generalization error is near
the best possible in Fd . But this best generalization error is large, because we have poor
approximation power for small d (that is, we have a strong “bias”). For large values of
d (usually d ≈ m), ²(d) is again large, but for a different reason. Here we expect that
²opt (d) may actually be quite small (that is, we have a weak “bias”, and Fd contains a good
approximation to the target function f ). But because Fd is so powerful, VS (d) will contain
many poor approximations as well (that is, VS (d) contains functions h with ²̂(h) << ²(h)
— so uniform convergence does not hold in Fd , or we have large “variance”)4 .
As a demonstration of the validity of this view, and as an introduction to a particular model

selection problem that we will examine in our experiments, we call the reader’s attention
to Figure 1. In this model selection problem (which we shall refer to as the intervals model
selection problem), the input domain is simply the real line segment [0, 1], and the hypothesis
class Fd is simply the class of all boolean functions over [0, 1] in which we allow at most
d alternations of label; thus Fd is the class of all binary step functions with at most d/2
steps. For the experiments, the underlying learning algorithm L that we have implemented
performs training error minimization. This is a rare case where efficient minimization is
possible; we have developed an algorithm based on dynamic programming that runs in
nearly linear time, thus making experiments on large samples feasible. The sample S was
generated using the target function in F100 that divides [0, 1] into 100 segments of equal
width 1/100 and alternating label. (Details of the algorithm and the experimental results of
the paper are provided in the Appendix.) In Figure 1 we plot ²(d), and ²η (d) (which we can
calculate exactly, since we have chosen the target function) when S consists of m = 2000
random examples (drawn from the uniform input distribution) corrupted by noise at the rate
η = 0.2. For our current discussion it suffices to note that ²(d) (similarly, ²η (d), which is
a linear function of ²(d)) does indeed experience a nontrivial minimum. Not surprisingly,
this minimum occurs near (but not exactly at) the target complexity of 100.
In Figure 2, we instead plot the difference ²̂(d) − ²η (d) for the same experiments. Notice
that there is something tempting about the simplicity of this plot. More precisely, as a
function of d/m it appears that ²̂(d) − ²η (d) has an initial regime (for d << p 100, or for
this m, d/m < 100/2000 = 0.05) with behavior that is approximately Θ( d/m), and a
later regime (for d/m >> 0.05) in which the behavior is linear in d/m. Unfortunately,
the behavior near the target complexity d = 100 does not admit easy characterization.
Nevertheless, Figure 2 demonstrates why one might be tempted to posit a “penalty” for
complexity that is a function of d/m, and to simply add this penalty to ²̂(d) as a rough
approximation to ²η (d).
According to Figure 1 and conventional wisdom, the best choice of d˜ should be an
intermediate value (that is, not d˜ ≈ 0 or d˜ ≈ m). But how should we choose d˜ when the
most common empirical measure of generalization ability — the function ²̂(d) — simply
decreases with increasing d, and whose straightforward minimization will therefore always
result in a large value of d that causes overfitting? This is the central question raised by the
model selection problem, and many answers have been proposed and analyzed. We review
three of them in the following section.
We conclude this section with a list of the various error measures that were presented in
the section, and which are used extensively throughout the paper.
• ²(h) denotes the generalization error of a hypothesis h with respect to the target function
def
f and the distribution D. Namely, ²(h) = P rx∈D [h(x) 6= f (x)]. Similarly, for noise
def
rate η > 0, ²η (h) = P rx∈D,c [h(x) 6= f (x) ⊕ c], where c is the noise bit which is 1
with probability η, and 0 with probability 1 − η.
def
• ²̂(h) is the training error of h on sample S. Namely, ²̂(h) = ²̂S (h) = |{hxi , bi i ∈ S :
h(xi ) 6= bi }|/m, where m is the size of S.
• ²opt (d) is the minimum generalization error taken over all hypotheses in Fd . Namely,
def def def
²opt (d) = ²(hd ), where hd = argminh∈Fd {²(h)}. Similarly, ²ηopt (d) = ²η (hd ).
• ²(d) is the generalization error of the hypothesis chosen by the learning algorithm L,
in hypothesis class Fd , given sample S, and ²̂(d) is the training error of the chosen
def def
hypothesis. Namely, ²(d) = ²L,S (d) = ²(h̃d ), and ²̂(d) = ²̂L,S (d) = ²̂(h̃d ), where
h̃d = L(S, d). ²η (d) is defined analogously.
3. Three Algorithms for Model Selection
The first two model selection algorithms we consider are members of a general class that
we shall informally refer to as penalty-based algorithms (and shall formally define shortly).
The common theme behind these algorithms is their attempt to construct an approximation
to ²(d) solely on the basis of the training error ²̂(d) and the complexity d, often by try-
ing to “correct” ²̂(d) by the amount that it underestimates ²(d) through the addition of a
“complexity penalty” term.
In Vapnik’s Guaranteed Risk Minimization (GRM) (Vapnik, 1982), d˜ is chosen according
to the rule
n ³ p ó
d˜ = argmind ²̂(d) + (d/m) 1 + 1 + ²̂(d)m/d (9)
where we have assumed that d is the Vapnik-Chervonenkis dimension (Vapnik & Chervo-
nenkis, 1971; Vapnik, 1982), of the class Fd ; this assumption holds in the intervals model
selection problem. Vapnik’s original GRM actually multiplies the second term inside the
argmin{·} above by a logarithmic factor intended to guard against worst-case choices from
VS (d), and thus has the following form:
( ¡ ln 2m ¢Ã s !)
d +1 ²̂(d)m
d˜ = argmind ²̂(d) + d
1+ 1 + ¡ ln 2m ¢ (10)
m d d +1
However, we have found that the logarithmic factor renders GRM uncompetitive on the
ensuing experiments, and hence in our experiments we only consider the modified and quite
competitive rule given in Equation (9) whose spirit is the same. The origin of this rule can
be summarized informally as follows (where for sake of simplicity we ignore all logarithmic
factors): it haspbeen shown (Vapnik, 1982) that with high probability for every d p and for
every h ∈ Fd , d/m is an upper bound on |²̂(h) − ²(h)| and hence |²̂(d) − ²(d)|
p ≤ d/m.
In fact, the stronger uniform convergence property holds: |²̂(h) − ²(h)| ≤ d/m for all
h ∈ Fd ; the analogous
p statement holds for ²̂(h) and ²η (h) in the η 6= 0 case. Thus, by
simply adding d/m to ²̂(d), we ensure that the resulting sum upper bounds ²(d), and if
we are optimistic we might further hope that the sum is in fact a close approximation to
²(d), and that its minimization is therefore tantamount to the minimization of ²(d). The
actual rule given in Equation (9) is slightly more complex than this,pand reflects a refined
bound on |²̂(d) − ²(d)| that varies from d/m for ²̂(d) close to 0 to d/m otherwise.
The next algorithm we consider, the Minimum Description Length Principle (MDL) (Ris-
sanen, 1978; Rissanen, 1986; Rissanen, 1989; Barron & Cover, 1991, Quinlan & Rivest,
1989) has rather different origins than GRM. MDL is actually a broad class of algorithms
with a common information-theoretic motivation, each algorithm determined by the choice
of a specific coding scheme for both functions and their training errors. This two-part
code is then used to describe the training sample S. The familiar MDL motivation re-
gards each potential hypothesis function as a code for the labels in the sample S, assuming
the code recipient has access only to the inputs in S: thus, the “best” hypothesis is the
one minimizing the total code length for the labels in the given coding scheme (the num-
ber of bits needed to represent the hypothesis function, plus the number of bits needed
to represent the labels given the hypothesis function). To illustrate the method, we give
a coding scheme for the intervals model selection problem 5 . Let h be a function with
exactly d alternations of label (thus, h ∈ Fd ). To describe the behavior of h on the sam-
ple S = {hxi , bi i}, where we assume, without loss of generality, that the examples are
ordered, we can simply specify the d inputs where ¡mh¢ switches value (that is, the indices
i such that h(xi ) 6= ¡h(x
¢ i+1 )) 6
. This takes log d bits; dividing by m to normalize,
we obtain (1/m) log d ≈ H(d/m) (Cover & Thomas, 1991), where H(·) is the binary
m
def
entropy function (i.e. H(p) = − (p log p + (1 − p) log(1 − p)) ). Now given h, the labels
in S can be described simply by coding the mistakes of h (that is, those indices i where
h(xi ) 6= f (xi )), at a normalized cost of H(²̂(h)). Technically, in the coding scheme just
described we also need to specify the values of d and ²̂(h) · m, but the cost of these is neg-
ligible. Thus, the version of MDL that we shall examine for the intervals model selection
problem dictates the following choice of d: ˜
d˜ = argmind∈[0,m/2] {H(²̂(d)) + H(d/m)}. (11)
In the context of model selection, GRM and MDL can both be interpreted as attempts to
model ²(d) by some function of ²̂(d) and d. More formally, a model selection algorithm of
the form
d˜ = argmind {G(²̂(d), d/m)} (12)
shall be called a penalty-based algorithm where G(·, ·) is referred to as a penalty-based

function7 . Notice that an ideal penalty-based function would obey G(²̂(d), d/m) ≈ ²(d)
(or at least G(²̂(d), d/m) and ²(d) would be minimized by the same value of d).
The third model selection algorithm that we examine has a different spirit than the penalty-
based algorithms. In cross validation (CV) (Stone, 1974; Stone, 1977), rather than attempt
to reconstruct ²(d) from ²̂(d) and d, we instead settle for a “worse” ²(d) (in a sense made
precise shortly) that we can directly estimate. More specifically, in CV we use only a fraction
(1 − γ) of the examples in S to obtain the hypothesis sequence h̃1 ∈ F1 , . . . , h̃d ∈ Fd , . . .
— that is, h̃d is now L(S 0 , d), where S 0 consists of the first (1 − γ)m examples in S. Here
γ ∈ [0, 1] is a parameter of the CV algorithm whose tuning we discuss briefly later. For
simplicity we assume that γm is an integer. CV chooses d˜ according to the rule
d˜ = argmind {²̂S 00 (h̃d )} (13)

where ²̂S 00 (h̃d ) is the error of h̃d on S 00 , the last γm examples of S that were withheld
in selecting h̃d . Notice that for CV, we expect the quantity ²(d) = ²(h̃d ) to be (perhaps
considerably) larger than in the case of GRM and MDL, because now h̃d was chosen on
the basis of only (1 − γ)m examples rather than all m examples. For this reason we
def
wish to introduce the more general notation ² γ (d) = ²(h̃d ) to indicate the fraction of the
sample withheld from training. CV settles for ² γ (d) instead of ²0 (d) in order to have an
independent test set with which to directly estimate ² γ (d).
In practice, it is typical to use various forms of multi-fold cross validation, in which many
(either disjoint or overlapping) training set/test set splits are selected from the original
sample, and the test set errors are averaged. The main advantage of multi-fold methods
is that each sample point is used for training on some splits; the main disadvantage is
the computational expense, and that the test sets are no longer independent. While we
expect that for many problems, this lack of independence does not introduce diminished
performance, we are unable to prove our general theoretical results for multi-fold methods,
and thus concentrate on the basic cross-validation method outlined above. For this reason it
is probably fair to say that we err on the side of pessimism when evaluating the performance
of CV-type algorithms throughout the investigation.
4. A Controlled Experimental Comparison
Our results begin with a comparison of the performance and properties of the three model
selection algorithms in a carefully controlled experimental setting — namely, the intervals
model selection problem. Among the advantages of such controlled experiments, at least in
comparison to empirical results on data of unknown origin, are our ability to exactly measure
generalization error (since we know the target function and the distribution generating the
data), and our ability to precisely study the effects of varying parameters of the data (such
as noise rate, target function complexity, and sample size), on the performance of model
selection algorithms. The experimental behavior we observe foreshadows a number of
important themes that we shall revisit in our formal results.
We begin with Figure 3. To obtain this figure, a training sample was generated from
the uniform input distribution and labeled according to an intervals function over [0, 1]
consisting of 100 intervals of alternating label and equal width8 ; the sample was corrupted
with noise rate η = 0.2. In Figure 3, we have plotted the true generalization errors (measured
with respect to the noise-free source of examples) ²grm , ²mdl and ²cv (using test fraction
γ = 0.1 for CV) of the hypotheses selected from the sequence h̃1 , . . . , h̃d , . . . by each the
three algorithms as a function of the sample size m, which ranged from 1 to 3000 examples.
As described in Section 2, the hypotheses h̃d were obtained by minimizing the training
error within each class Fd . Details of the code used to perform these experiments is given
in the appendix.
Figure 3 demonstrates the subtlety involved in comparing the three algorithms: in partic-
ular, we see that none of the three algorithms outperforms the others for all sample sizes.
Thus we can immediately dismiss the notion that one of the algorithms examined can be
said to be optimal for this problem in any standard sense. Getting into the details, we see
that there is an initial regime (for m from 1 to slightly less than 1000) in which ²mdl is the
lowest of the three errors, sometimes outperforming ²grm by a considerable margin. Then
there is a second regime (for m about 1000 to about 2500) where an interesting reversal of
relative performance occurs, since now ²grm is the lowest error, considerably outperform-
ing ²mdl , which has temporarily leveled off. In both of these first two regimes, ²cv remains
the intermediate performer. In the third and final regime, ²mdl decreases rapidly to match
²grm and the slightly larger ²cv , and the performance of all three algorithms remains quite
similar for all larger sample sizes.
Insight into the causes of Figure 3 is given by Figure 4, where for the same runs used
to obtain Figure 3, we instead plot the quantities d˜grm , d˜mdl and d˜cv , the value of d˜
chosen by GRM, MDL and CV respectively (thus, the “correct” value, in the sense of
simply having the same number of intervals as the target function, is 100). Here we
see that for small sample sizes, corresponding to the first regime discussed for Figure 3
above, d˜grm is slowly approaching 100 from below, reaching and remaining at the target
value for about m = 1500. Although we have not shown it explicitly, GRM is incurring
nonzero training error throughout the entire range of m. In comparison, for a long initial
period (corresponding to the first two regimes of m), MDL is simply choosing the shortest
hypothesis that incurs no training error (and thus encodes both “legitimate” intervals and
noise), and consequently d˜mdl grows in an uncontrolled fashion. It will be helpful to
compute an approximate expression for d˜mdl during this “overcoding” period. Assuming
that the target function is s equally spaced intervals, an approximate expression for the
number of intervals required to achieve zero training error is
def
d0 = 2η(1 − η)m + (1 − 2η)2 s. (14)
For the current experiment s = 100 and η = 0.2. Equation (14) can be explained as follows.
Consider the event that a given pair of consecutive inputs in the sample have opposite labels.
If the two points belong to the same interval of the target function, then this event occurs
if and only if exactly one of them is labeled incorrectly, which happens with probability
2η(1 − η). If the two points are on opposite sides of a target switch in the target function,
then this event occurs either if both of them are labeled correctly or if both of them are
labeled incorrectly, which happens with probability η 2 + (1 − η)2 . Since the expected
number of pairs of the first type is m − s, and the expected number of pairs of the second
type is s, we obtain (ignoring dependencies between the different pairs) that the expected
number of switch points in the sample is roughly
2η(1 − η)(m − s) + (η 2 + (1 − η)2 )s = 2η(1 − η)m + (1 − 4η + 4η 2 )s (15)

= 2η(1 − η)m + (1 − 2η) s = d0 . (16)
2
In the first regime of Figures 3 and 4, the overcoding behavior d˜mdl ≈ d0 of MDL is
actually preferable, in terms of generalization error, to the initial “undercoding” behavior
of GRM, as verified by Figure 3. Once d˜grm approaches 100, however, the overcoding
of MDL is a relative liability, resulting in the second regime. Figure 4 clearly shows that
the transition from the second to the third regime (where approximate parity is achieved)
is the direct result of a dramatic correction to d˜mdl from d0 (defined in Equation (14)) to
the target value of 100. Finally, d˜cv makes a more rapid but noisier approach to 100 than
d˜grm , and in fact also overshoots 100, but much less dramatically than d˜mdl . This more
rapid initial increase again results in superior generalization error compared to GRM for
small m, but the inability of d˜cv to settle at 100 results in slightly higher error for larger m.
In a moment, we shall further discuss the interesting behavior of d˜grm and d˜mdl , but first
we call attention to Figures 5 to 12. These figures, which come in pairs, show experiments
identical to that of Figures 3 and 4, but for the smaller noise rates η = 0.0, 0.1 and the
larger noise rates η = 0.3, 0.4; these plots also have an increased sample size range,
m = 1 . . . 6500. (Thus, the scale of these figures is different from that of Figures 3 and 4.)
Notice that as η increases, the initial period of undercoding by GRM seems to increase
slightly, but the initial period of overcoding by MDL increases tremendously, the result
being that the first regime of generalization error covers approximately the same values of
m (about 1 to 1000), but the second regime covers a wider and wider range of m, until at
η = 0.4, d˜mdl has not corrected to 100 even at m = 6500 (further experiments revealed
that m = 15000 is still not sufficient).
The behavior of the lengths d˜grm and d˜mdl in Figure 4 can be traced to the form of the
total penalty functions for the two methods. For instance, in Figures 13, 14, and 15, we
plot the total MDL penalty H(²̂(d)) + H(d/m) as a function of complexity d for the fixed
sample sizes m = 500, 2000 and 4000 respectively, again using noise rate η = 0.20. At
m = 500, we see that the rather dramatic total penalty curve has its global minimum at
approximately d = 200, which as expected (we are in the MDL overcoding regime at this
small sample size) is d0 , the point of consistency with the noisy sample. However, a small
local minimum is already developing near the target value of d = 100. By m = 2000, this
local minimum is quite pronounced, and beginning to compete with the global consistency
minimum (which for this noise rate and sample size has now moved out to approximately
d0 = 650). At m = 4000, the former local minimum at d = 100 has become the global
minimum.
The rapid transition of d˜mdl that marks the start of the final regime of generalization error
discussed above (approximate parity of the three methods) is thus explained by the switch-
ing of the global total penalty minimum from d0 to d = 100. From the expression given in
Equation (14) we can infer that this switching of the minimum is governed by a competi-
tion between the quantities H(2η(1 − η) + (s/m)(1 − 2η)2 ) and H(η) + H(s/m). The
first quantity is the expected value of the total penalty of MDL for the choice d = d0
(where the hypothesis chosen is consistent with the data and no training error is in-
curred), while the second quantity is the total penalty of MDL for the (correct) choice
d = ¡ s. As an interesting digression,
¢ in Figures 16, 17 and 18, we plot the difference
H 2η(1 − η) + (s/m)(1 − 2η)2 − (H(η) + H(s/m)) as a function of η for s/m = 0.01
and s/m = 0.04. Note that if this function is negative, we predict that MDL will prefer
d = d0 (overcoding), and if it is positive, we predict that MDL will prefer d = s. For
s/m = 0.01, we see that the function is positive for small noise rates and negative for
larger noise rates. Thus, make the intuitively reasonable prediction that for this value of
the ratio s/m, increasing the noise rate can only degrade the behavior, by forcing the re-
versal of the global minimum from d = s to d = d0 . Curiously, however, the difference
exhibits nonmonotonic behavior as a function of s/m. For the case s/m = 0.04, this non-
monotonicity has a subtle but dramatic effect, since it causes the difference to move from
negative to positive at small η. Thus we predict that for very small values of η (less than
0.015), by increasing the noise rate slightly (that is, by adding a small amount of additional
classification noise), we can actually cause the global minimum to shift from d = d0 to
d = s, and consequently improve the resulting generalization error. These predictions are
in fact confirmed by experiments we conducted.
In Figures 19, 20, and 21, we give plots of the total GRM penalty for the same three
sample sizes and noise rate. Here the behavior is much more controlled — for each sample
size, the total penalty has the same single-minimum bowl shape, with the minimum starting
to the left of d = 100 (the minimum occurs at roughly d = 40 for m = 500), and gradually
moving over d = 100 and sharpening for large m.
A natural question to pose after examining these experiments is the following: is there
a penalty-based algorithm that enjoys the best properties of both GRM and MDL? By this
we would mean an algorithm that approaches the “correct” d value (whatever it may be
for the problem in hand) more rapidly than GRM, but does so without suffering the long,
uncontrolled “overcoding” period of MDL. An obvious candidate for such an algorithm
is simply a modified version of GRM or MDL, in which we reason (for example) that
perhaps the GRM penalty for complexity is too large for this problem (resulting in the
initial reluctance to code), and we thus multiply the complexity penalty term in the GRM
rule (the second term inside the argmin{·}) in Equation (9) by a constant less than 1 (or
analogously, multiply the MDL complexity penalty term by a constant greater than 1 to
reduce overcoding). The results of an experiment on such a modified version of GRM
are shown in Figures 22 and 23, where the original GRM performance is compared to a
modified version in which the complexity penalty is multiplied by 0.5. Interestingly and
perhaps unfortunately, we see that there is no free lunch: while the modified version does
indeed code more rapidly and thus reduce the small m generalization error, this comes at the
cost of a subsequent overcoding regime with a corresponding degradation in generalization
error (and in fact a considerably slower return to d = 100 than MDL under the same
conditions)9 . The reverse phenomenon (reluctance to code) is experienced for MDL with
an increased complexity penalty multiplier, as demonstrated by Figures 24 and 25. This
observation seems to echo recent results (Schaffer, 1994; Wolpert, 1992) which essentially
prove that no learning algorithm can perform well on all problems. However, while these
results show that for any given learning algorithm there exist learning problems (typically
in which the target function is chosen randomly from a large and complex space) on which
the performance is poor, here we have given an explicit and very simple learning problem
on which no simple variant of GRM and MDL can perform well for all sample sizes.
Let us summarize the key points demonstrated by these experiments. First, none of
the three algorithms dominates the others for all sample sizes. Second, the two penalty-
based algorithms seem to have a bias either towards or against coding that is overcome
by the inherent properties of the data asymptotically, but that can have a large effect on
generalization error for small to moderate sample sizes. Third, this bias cannot be overcome
simply by adjusting the relative weight of error and complexity penalties, without reversing
the bias of the resulting rule and suffering increased generalization error for some range of
m. Fourth, while CV is not the best of the algorithms for any value of m, it does manage to
fairly closely track the best penalty-based algorithm for each value of m, and considerably
beats both GRM and MDL in their regimes of weakness. We now turn our attention to our
formal results, where each of these key points will be developed further.
5. A Bound on the Error for Penalty-Based Algorithms
We begin our formal results with a bound on the generalization error for penalty-based
algorithms that enjoys three features. First, it is general: it applies to practically any
penalty-based algorithm, and holds for any model selection problem (of course, there is a
price to pay for such generality, as discussed below). Second, for certain algorithms and
certain problems the bound can give rapid rates of convergence to small error. Third, the
form of the bound is suggestive of some of the behavior seen in the experimental results.
Our search for a bound of this type was inspired by work of Barron and Cover (1991),
Barron and Cover give bounds of a similar form (which they call the index of resolution)
on the generalization error of MDL in the context of density estimation.
For a given penalty-based algorithm, let G be the function that determines the algorithm
as defined in Equation (12). In Theorem 1 we give a bound on the generalization error of
such an algorithm, where the only restriction made on the algorithm is that G be continuous
and increasing in both its arguments. The bound we give consists of two terms. The
first term, denoted by RG (m), is a function of the sample size, m, and as m → ∞ it
approaches the minimum generalization error achievable in any of the classes Fd . This
minimum value, by definition, is a lower bound on the generalization error achieved by
any possible method. Since the bound we give applies to quite a wide range of model
selection algorithms, we are not able to provide a general statement concerning the rate of
convergence of RG (m) to the optimal error, and this rate strongly depends on the properties
of G. The general form of RG (m) (as a function of G as well as m) is described in the
proof of Theorem 1. Following the proof we discuss what properties must G have in
order that RG (m) converge at a reasonable rate to the optimal error. We also give several
examples of the application of the theorem in which the exact form of RG (m) and hence its
convergence rate become explicit. The second term in the bound is a function of m as well,
and it decreases very rapidly as m increases. However, it is also an increasing function of
the complexity chosen by the penalty-based algorithm, and thus, similarly to the first term,
is dependent on the properties of G. We return to discuss this bound following the formal
theorem statement below. We state the bound for the special but natural case in which the
underlying learning algorithm L is training error minimization. Towards the end of this
section we present a straightforward analogue for more general L (Theorem 2). In addition,
we give a generalization of Theorem 1 to the noisy case (Theorem 3). In both theorems
the bound given on the generalization error has a very similar form to the bound given in
Theorem 1.
Theorem 1 Let ({Fd }, f, D, L) be an instance of the model selection problem in which

L performs training error minimization, and where d is the VC dimension of Fd . Let
G : <×< → < be a function that is continuous and increasing in both its arguments, and let
²G (m) denote the random variable whose value is the generalization error of the hypothesis
chosen by the penalty-based model selection algorithm d˜ = argmind {G(²̂(d), d/m)} on a

training sample of size m. Then for any given δ > 0, with probability at least 1 − δ
˜ m, δ) ,
²G (m) ≤ RG (m) + β(d, (17)
where RG (m) approaches mind {²opt (d)} as m → ∞, and where β(·, ·, ·) is defined as
follows: for d < m,
s
def d ln 2em 9m
d + ln δ
β(d, m, δ) = 2 (18)
m
def
and for d ≥ m, β(d, m, δ) = 1.
Before proving Theorem 1, let us further discuss the form of the bound given in S the
theorem. The first term, RG (m), approaches the optimal generalization error within Fd
in the limit of large m, and the second term directly penalizes large complexity. If we want
the sum of the two terms in the bound to be meaningful, then we should be able to give a
bound on β(d, ˜ m, δ) that decays to 0 with m, preferably as rapidly as possible. In other
words, we must be able to argue that the complexity of the hypothesis chosen is limited.
If we can do so, then combined with the bound on the first term we have a proof of the
method’s statistical consistency (that is, approach to the optimal error in the large sample
limit), and may even have a nice rate of approach to the optimal error. If we cannot do so,
then we are forced to consider the possibility that our method is simply fitting the sample,
and incurring large error because as a result. Such a possibility was clearly realized in the
experimental results for MDL, where a long period of unbounded hypothesis complexity
directly caused a long period of essentially constant generalization error as a function of
m. We return to this issue after the proof of Theorem 1.
In order to prove Theorem 1, we shall need to following uniform convergence bound
which is due to Vapnik (1982).
Uniform Convergence Bound Let Fd be a hypothesis class with VC dimension d < m.
Then, for every m > 4 and for any given δ > 0, with probability at least 1 − δ,
s ¡ ¢
d ln 2md + 1 + ln δ
9
|²(h) − ²̂(h)| < 2 (19)
m
for every h ∈ Fd . If the sample is noisy, then the same bound holds for ²η (h)10 .
Proof of Theorem 1: Since d˜ is chosen to minimize G(²̂(d), d/m), we have that for every
d
³ ´
˜ d/m
G ²̂(d), ˜ ≤ G (²̂(d), d/m) . (20)
Using the uniform convergence bound stated above we have that for any given d < m, with
probability at least 1 − δ/m,
s
d ln 2em 9m
d + ln δ
|²(h) − ²̂(h)| < 2 (21)
m
for all h ∈ Fd . Thus, with probability at least 1 − δ, the above holds for all d < m. For
d ≥ m we can use the trivial bound that for every h, |²(h)−²̂(h)| ≤ 1, and together we have
that with probability at least 1−δ, for every d, and for all h ∈ Fd , |²(h)−²̂(h)| < β(d, m, δ),
where β(·, ·, ·) was defined in the statement of Theorem 1. If we now use the fact that G(·, ·)
is increasing in its first argument, we can replace the occurrence of ²̂(d) ˜ on the left-hand
side of Equation (20) by ²(d) ˜ − β(d, ˜ m, δ) to obtain a smaller quantity. Similarly, since
def
²̂(d) ≤ ²̂(hd ) (recall that hd = argminh∈Fd {²(h)}), and ²̂(hd ) ≤ ²(hd ) + β(d, m, δ) =
²opt (d) + β(d, m, δ), we can replace the occurrence of ²̂(d) on the right-hand side by
²opt (d) + β(d, m, δ) to obtain a larger quantity. This gives
³ ´
˜ − β(d,
G ²(d) ˜ m, δ), d/m
˜ ≤ G (²opt (d) + β(d, m, δ), d/m) . (22)
Now because G(·, ·) is an increasing function of its second argument, we can further weaken
Equation (22) to obtain
³ ´
G ²(d)˜ − β(d, ˜ m, δ), 0 ≤ G (²opt (d) + β(d, m, δ), d/m) . (23)
If we define G0 (x) = G(x, 0), then since G(·, ·) is increasing in its first argument, G−1
0 (·)
is well-defined, and we may write
˜ ≤ G−1 (G (²opt (d) + β(d, m, δ), d/m)) + β(d,
²(d) ˜ m, δ). (24)
0
Now fix any small value τ > 0. For this τ , let d0 be the smallest value satisfying ²opt (d0 ) ≤
mind {²opt (d)} + τ — thus, d0 is sufficient complexity to almost match the approxima-
tive power of arbitrarily large complexity. Examining the behavior of G−1 0
0 (G(²opt (d ) +
0 0 0
β(d , m, δ), d /m)) as m → ∞, we see that the arguments approach the point (²opt (d ), 0),
and so
G−1 0 0 0 −1 0
0 (G(²opt (d ) + β(d , m, δ), d /m)) −→ G0 (G(²opt (d ), 0)) (25)
= ²opt (d0 ) ≤ min{²opt (d)} + τ (26)
by continuity of G(·, ·), as desired. By defining
© ª
RG (m) = min G−1
def
0 (G (²opt (d) + β(d, m, δ), d/m)) (27)
d
we obtain the statement of the theorem.

Given the definition of RG (m) in Equation (27), we can now examine the two terms
RG (m) and β(d, ˜ m, δ) more carefully and observe that they may be thought of as competing.
In order for RG (m) to approach mind {²opt (d)} rapidly and not just asymptotically (that
is, in order to have a fast rate of convergence), G(·, ·) should not penalize complexity too
strongly, which is obviously at odds with the optimization of the term β(d, ˜ m, δ). For
α
example, consider G(²̂(d), d/m) = ²̂(d) + (d/m) for some power α > 0. Assuming
d ≤ m, this rule is conservative (large penalty for complexity) for small α, and liberal
(small penalty for complexity) for large α. Thus, to make β(d, ˜ m, δ) small we would like α
˜
to be small, to prevent the choice of large d. However, by definition of RG (m) we have that
for the function G in question RG (m) = mind {²opt (d) + β(d, m, δ) + (d/m)α }, which
increases as α decreases, thus encouraging large α (liberal coding).
Ideally, we might want G(·, ·) to balance the two terms of the bound, which implicitly
involves finding an appropriately controlled but sufficiently rapid rate of increase in d. ˜
The tension between these two criteria in the bound echoes the same tension that was seen
experimentally: for MDL, there was a long period of essentially uncontrolled growth of d˜
(linear in m), and this uncontrolled growth prevented any significant decay of generalization
error (Figures 3 and 411 ). GRM had controlled growth of d,˜ and thus would incur negligible
error from our second term — but perhaps this growth was too controlled, as it results in
the initially slow (small m) decrease in generalization error.
To examine these issues further, we now apply the bound of Theorem 1 to several penalty-
based algorithms. In some cases the final form of the bound given in the theorem statement,
while easy to interpret, is unnecessarily coarse, and better rates of convergence can be
obtained by directly appealing to the proof of the theorem.
We begin with a simplified GRM variant (SGRM), defined by G(²̂(d), d, m) = ²̂(d) +
β(d, m, δ). Note that SGRM does not have the exact form required in Theorem 1. However,
as we shall show below, its generalization error can be bounded easily using the same
techniques applied in the proof of Theorem 1. We³first observe that we can avoid
´ weakening
˜ ˜ ˜
Equation (22) to Equation (23), because here G ²(d) − β(d, m, δ), d, m = ²(d). ˜ Thus
the dependence on d˜ in the bound disappears entirely, resulting in the following bound in
²sgrm (m): With probability at least 1 − δ,
²sgrm (m) ≤ min {²opt (d) + 2β(d, m, δ)} . (28)

d
This is not so mysterious, since SGRM penalizes strongly for complexity (even more so
than GRM). This bound expresses the generalization error as the minimum of the sum of
the best possible error within each class Fd and a penalty for complexity. Such a bound
seems entirely reasonable, given that it is essentially the expected value of the empirical
quantity we minimized to choose d˜ in the first place. Furthermore, if ²opt (d) + β(d, m, δ)
approximates ²(d) well, then such a bound is about the best we could hope for. However,
there is no reason in general to expect this to be the case.
As an example of the application of Theorem 1 to MDL we can derive the following
bound on ²mdl (m) (where for any x > 1 we define H(x) to be 1): With probability at least
1 − δ,
© ª
²mdl (m) ≤ min H−1 (H (²opt (d) + β(d, m, δ)) + H(d/m)) + β(d˜mdl , m, δ) (29)
d
≤ min {H (²opt (d) + β(d, m, δ)) + H(d/m)} + β(d˜mdl , m, δ) (30)

d
≤ min {H(²opt (d)) + H(β(d, m, δ)) + H(d/m)} + β(d˜mdl , m, δ) (31)

d
≤ min {H(²opt (d)) + 2H(β(d, m, δ))} + β(d˜mdl , m, δ) (32)

d
where we have used H−1 (y) ≤ y to get Equation (30) and H(x + y) ≤ H(x) + H(y) to
get Equation (31). Again, we emphasize that the bound given by Equation (32) is vacuous
without a bound on d˜mdl , which we know from the experiments can be of order m. However,
by combining this bound with an analysis of the behavior of d˜mdl for the intervals problem
as discussed in Section 4 (see Equation (14) and the discussion following it), it is possible
to give an accurate theoretical explanation for the experimental findings for MDL.
As a final example, we apply Theorem 1 to a variant of MDL in which the penalty for
coding is increased over the original, namely G(²̂(d), d/m) = H(²̂(d)) + 1/λ2 H(d/m)
where λ is a parameter that may depend on d and m. Assuming that we never choose d˜
whose total penalty is larger than 1 (which holds if we simply add the “fair coin hypothesis”
˜
q F1 ), we have that H(d/m) ≤ λ . Since H(x) ≥ x, for all 0 ≤ x ≤ 1/2, it follows that
2
to
˜ ≤ λ. For any δ ≥ exp(−λ2 m) we then have that
d/m
s
d˜ ln(2em) + mλ2 ln m √
˜ m, δ) < 2
β(d, = O(λ ln m) . (33)
m
If λ is some decreasing function of m (say, m−α for some 0 < α < 1), then the bound on
˜ given by Theorem 1 decreases at a reasonable rate.
²(d)
We conclude this section with two generalizations of Theorem 1. The first is for the case in
which the penalty-based algorithm uses a learning algorithm L which does not necessarily
minimize the training error, and the second is for the case in which the sample is corrupted
by noise.
For Theorem 2 we need the following definition. We say that a learning algorithm L is
adequate if it has the following property. There exists a function µL : N × N × [0, 1] →
[0, 1], such that for every given δ, with probability at least 1 − δ, |²̂L (d) − ²̂opt (d)| ≤
def
µL (d, m, δ) for all d, where ²̂opt = minh∈Fd {²̂(h)}. That is, ²̂opt is the minimum training
error (on the sample S) achievable in Fd . Furthermore, as m → ∞, µL (d, m, δ) → µ̄L ,
where µ̄L is some constant which depends on L. Thus, if µ̄L is not very large, then in
the limit of large m, L does not perform much worse than the training error minimization
algorithm. We would like to note that many other definitions of adequacy are appropriate,
and can lead to statements similar to the one in Theorem 2 below.

L is an adequate learning algorithm, and where d is the VC dimension of Fd . Let G :
< × < → < be a function that is continuous and increasing in both its arguments, and let
chosen by the penalty-based model selection algorithm d˜ = argmind {G(²̂(d), d/m)} on a
training sample of size m. Then
˜ m, δ/2)
²G (m) ≤ RG (m) + β(d, (34)
where RG (m) approaches mind {²opt (d)} + µ̄L as m → ∞, and is defined as follows:
© ª
RG (m) = min G−1
def
0 (G (²opt (d) + µL (d, m, δ/2) + β(d, m, δ/2)) , d/m) (35)
d
def
where G0 (·) = G(·, 0).
Proof Sketch: The proof is very similar to the proof of Theorem 1 and hence we need
only³point out the´ differences. As in the proof of Theorem 1 we have that for any value of
˜ ˜
d G ²̂(d), d/m ≤ G (²̂(d), d/m). It is still true that with probability at least 1 − δ/2,
˜ is bounded from below by ²(d)
²̂(d) ˜ + β(d,˜ m, δ/2), however, we cannot bound ²̂(d)
by ²opt (d) + β(d, m, δ/2) since it is not true any longer that ²̂(d) is the minimal error
achievable in Fd . Instead we have that with probability at least 1 − δ/2, for every d,
²̂(d) ≤ ²̂opt (d) + µ(d, m, δ/2), and hence with probability at least 1 − δ, ²̂(d) ≤ ²opt (d) +
µ(d, m, δ/2) + β(d, m, δ/2). The rest of the proof follows as in Theorem 1 where we get
that for every d
˜ ≤ G−1 (G (²opt (d) + µ(d, m, δ/2) + β(d, m, δ/2), d/m)) + β(d,
²(d) ˜ m, δ/2).
0
(36)
Using our assumption on the adequacy of L we have that as m → ∞,

© ª
min G−10 (G (²opt (d) + µ(d, m, δ/2) + β(d, m, δ/2), d/m)) → min{²opt (d)} + µ̄L ,
d
(37)
as required.

L performs training error minimization, and where d is the VC dimension of Fd . Let
G : <×< → < be a function that is continuous and increasing in both its arguments, and let
output by the penalty-based model selection algorithm d˜ = argmind {G(²̂(d), d/m)} on a
training sample of size m, and in the presence of noise at rate η. Then
1 ˜ m, δ)
²G (m) ≤ RG (m, η) + β(d, (38)
1 − 2η
where RG (m, η) approaches mind {²opt (d)} as m → ∞, and is defined as follows:
1 © ª
min G−1
def
RG (m, η) = 0 (G ((1 − 2η)²opt (d) + η + β(d, m, δ)) , d/m) − η
1 − 2η d
(39)
def
where G0 (·) = G(·, 0).
Proof Sketch: The proof of Theorem 3 follows the same sequence of inequalities as
the proof of Theorem 1, except that each occurrence of ²(·) should be exchanged with
²η (·), and each occurrence of ²opt (·) should be exchanged with ²ηopt (·). Thus, similarly to
Equation (24), we have that
¡ ¡ ¢¢
˜ ≤ G−1 G ²η (d) + β(d, m, δ), d/m + β(d,
²η (d) ˜ m, δ). (40)
0 opt
If we now apply the equality ²η (h) = (1 − 2η)²(h) + η we get that for every d
˜ ≤ 1 h −1 i
˜ m, δ) − η.
²(d) G0 (G ((1 − 2η)²opt (d) + η + β(d, m, δ), d/m)) + β(d,
1 − 2η
(41)
Again, similarly to the proof of Theorem 1, we have that as m → ∞,

© ª
min G−1 0 (G ((1 − 2η)²opt (d) + η + β(d, m, δ), d/m)) → (1 − 2η) min{²opt (d)} + η,
d
(42)
and thus we get the desired bound. Note that the rate of convergence of of RG (m, η) to
the optimal error depends now on the size of η as well as on G. The same is true for the
penalty complexity term in the bound. It is not very surprising, that as η approaches 1/2,
the bound worsens.
6. A Bound on the Additional Error of CV
In this section we state a general theorem bounding the additional generalization error
suffered by cross validation compared to any polynomial complexity model selection algo-
rithm M . By this we mean that given a sample of size m, algorithm M will never choose
a value of d˜ larger than mk for some fixed exponent k > 1. We emphasize that this is a
mild condition that is met in practically every realistic model selection problem: although
there are many documented circumstances in which we may wish to choose a model whose
complexity is on the order of the sample size, we do not imagine wanting to choose, for
instance, a neural network with a number of nodes exponential in the sample size. For the
next theorem, recall that the parameter γ ∈ [0, 1] denotes the fraction of examples withheld
for testing by the CV algorithm, and that we assume that γm is an integer.
Theorem 4 Let M be any polynomial complexity model selection algorithm, and let
({Fd }, f, D, L) be any instance of model selection. Let ²m (m) and ²cv (m) denote the
generalization error of the hypotheses chosen by M and CV respectively. Then for any
given δ > 0, with probability at least 1 − δ:
Ãs !
ln(m/δ)
²cv (m) ≤ ²m ((1 − γ)m) + O . (43)
γm
In other words, the generalization error of CV on m examples is at most

p the generalization
error of M on (1 − γ)m examples, plus the “test penalty term” O( ln(m/δ)/(γm)).
Proof: Let S = (S 0 , S 00 ) be a random sample of m examples, where |S 0 | = (1 − γ)m
and |S 00 | = γm. Let dmax = ((1 − γ)m)k be the polynomial bound on the complexity
selected by M , and let h̃01 ∈ F1 , . . . , h̃0dmax ∈ Fdmax be determined by h̃0d = L(S 0 , d).
By definition of CV, d˜ is chosen according to d˜ = argmind {²̂S 00 (h̃0d )}. For a given h̃0d , we
know by Hoeffding’s Inequality (Hoeffding, 1963) that for any α > 0,
h¯ ¯ i
¯ ¯
P r ¯²(h̃0d ) − ²̂S 00 (h̃0d )¯ > α < 2 exp(−2α2 γm). (44)
The probability that some h̃0d deviates by more than α from its expected value is therefore
bounded by 2mk exp(−2α2 γm). It follows that for any given δ, with probability at least
1 − δ over the draw of S 00 ,
Ãs !
0 0 ln(m/δ)
|²(h̃d ) − ²̂S 00 (h̃d )| = O (45)
γm
for all d ≤ dmax . Therefore with probability at least 1 − δ

Ãs !
0 ln(m/δ)
²cv = min{²(h̃d )} + O . (46)
d γm
But as we have previously observed, the generalization error of any model selection algo-
rithm (including M ) on input S 0 is lower bounded by mind {²(h̃0d )}, and our claim directly
follows.
Note that the bound of Theorem 4 does not claim ²cv (m) ≤ ²m (m) for all m (which would
mean that cross validation is an optimal model selection algorithm). The bound given is
weaker than this ideal in two important ways. First, and perhaps most importantly, ²m ((1 −
γ)m) may be considerably larger than ²m (m). This could either be due to properties of the
underlying learning algorithm L, or due to inherent phase transitions (sudden decreases)
in the optimal information-theoretic learning curve (Seung, Sampolinsky, & Tishby, 1992,
Haussler, Kearns, Seung, & Sampolinsky, 1994) — thus, in an extreme case, it could be
that the generalization error that can be achieved within some class Fd by training on m
examples is close to 0, but that the optimal generalization error that can be achieved in Fd
by training on a slightly smaller sample is near 1/2. This is intuitively the worst case for
cross validation — when the small fraction of the sample saved for testing was critically
needed for training in order to achieve nontrivial performance — and is reflected in the first
term of our bound. Obviously the risk of “missing” phase transitions can be minimized by
decreasing the test fraction γ, but only at the expense of increasing the test penalty term,
which is the second way in which our bound falls short of the ideal. However, unlike the
potentially unbounded difference ²m ((1 − γ)m) − ²m (m), our bound on the test penalty
can be decreased without any problem-specific knowledge by simply increasing the test
fraction γ.
Despite these two competing sources of additional CV error, the bound has some strengths
that are worth discussing. First of all, the bound does not simply compare the worst-case
error of CV to the worst-case error of M over a wide class of model selection problems; the
bound holds for any fixed model selection problem instance ({Fd }, f, D, L). We believe
that giving similarly general bounds for any penalty-based algorithm would be extremely
difficult, if not impossible. The reason for this belief arises from the diversity of learning
curve behavior documented by the statistical mechanics approach (Seung, Sampolinsky, &
Tishby, 1992, Haussler, Kearns, Seung, & Sampolinsky, 1994), among other sources. In the
same way that there is no universal learning curve behavior, there is no universal behavior
for the relationship between the functions ²̂(d) and ²(d) — the relationship between these
quantities may depend critically on the target function and the input distribution (this point
is made more formally in Section 7). CV is sensitive to this dependence by virtue of its
target function-dependent and distribution-dependent estimate of ²(d). In contrast, by their
very nature, penalty-based algorithms propose a universal penalty to be assigned to the
observation of error ²̂(h) for a hypothesis h of complexity d.
A more technical feature of Theorem 4 is that it can be combined with bounds derived for
penalty-based algorithms using Theorem 1 to suggest how the parameter γ should be tuned.
For example, letting M be the SGRM algorithm described in Section 5, and combining
Equation (28) with Theorem 4 yields
p
²cv (m) ≤ ²sgrm ((1 − γ)m) + ln(2dmax (m)/δ)/2γm (47)
s
ln(2dmax (m)/δ)
≤ min {²opt (d) + 2β(d, (1 − γ)m, δ)} + (48)
d 2γm
If we knew the form of ²opt (d) (or even had bounds on it), then in principle we could
minimize the bound of Equation (48) as a function of γ to derive a recommended training/test
split. Such a program is feasible for many specific problems (such as the intervals problem),
or by investigating general but plausible bounds on the approximation rate ²opt (d), such
as ²opt (d) ≤ c0 /d for some constant c0 > 0. For a detailed study of this line of inquiry,
see Kearns (Kearns,1995). Here we simply note that Equation (48) tells us that in cases
for which the power law decay of generalization error within each Fd holds approximately,
the performance of CV will be competitive with GRM or any other algorithm. This makes
perfect sense in light of the preceding analysis of the two sources for additional CV error:
in problems with power law learning curve behavior, we have a power law bound on
²m ((1 − γ)m) − ²m (m), and thus CV “tracks” any other algorithm closely in terms of
generalization error. This is exactly the behavior observed in the experiments described in
Section 4, for which the power law is known to hold approximately.
We conclude this section with a noisy version of Theorem 4, whose correctness directly
follows from the proof of Theorem 4, together with the equality ²η (h) = (1 − 2η)²(h) + η.
Theorem 5 Let M be any polynomial complexity model selection algorithm, and let
({Fd }, f, D, L) be any instance of model selection. Let ²m (m) and ²cv (m) denote the
expected generalization error of the hypotheses chosen by M and CV respectively when the
sample is corrupted by noise at rate η. Then for any given δ > 0, with probability at least
1−δ
µ ¶
1 p
²cv (m) ≤ ²m ((1 − γ)m) + O ln(m/δ)/(γm) . (49)
1 − 2η
7. Limitations on Penalty-Based Algorithms
Recall that our experimental findings suggested that it may sometimes be fair to think of
penalty-based algorithms as being either conservative or liberal in the amount of coding
they are willing to allow in their hypothesis, and that bias in either direction can result in
suboptimal generalization that is not easily overcome by slight adjustments to the form of the
rule. In this section we develop this intuition more formally, giving a theorem demonstrating
some fundamental limitations on the diversity of problems that can be effectively handled
by any fixed penalty-based algorithm. Briefly, we show that there are (at least) two very
different forms that the relationship between ²̂(d) and ²(d) can assume, and that any penalty-
based algorithm can perform well on only one of these. Furthermore, for the problems we
choose, CV can in fact succeed on both. Thus we are doing more than simply demonstrating
that no model selection algorithm can succeed universally for all target functions, a statement
that is intuitively obvious. We are in fact identifying a weakness that is special to penalty-
based algorithms. However, as we have discussed previously, the use of CV is not without
pitfalls of its own. We therefore conclude the paper in Section 8 with a summary of the
different risks involved with each type of algorithm.
Theorem 6 For any sample size m, there are model selection problem instances
({F1d }, f1 , D1 , L) and ({F2d }, f2 , D2 , L) (where the algorithm L performs empirical er-
ror minimization for the respective function classes in both instances) and a constant λ
(independent of m) such that for any penalty-based model selection algorithm G, either
1 (m) ≥ min{²1 (d)} + λ

²G
d
or
2 (m) ≥ min{²2 (d)} + λ.

²G
d
Here ²i (d) is the generalization error ²(d) for instance i ∈ {1, 2}, and ²G
i (m) is the expected
generalization error of algorithm G for instance i. Thus, on at least one of the two model
selection problems, the generalization error of G is lower bounded away from the optimal
value mind {²i (d)} by a constant independent of m.
Proof: For ease of exposition (and deviating from our conventions in the rest of the paper),
in the proof we use ²̂i (d) and ²i (d) (i ∈ {1, 2}) to refer to the expected values. Thus, ²̂i (d)
is the expected training error of the function in Fid that minimizes the training error, and
²i (d) is the expected generalization error of this same function.
We start with a rough description of the properties of the two problems (see Figure 26).
In Problem 1, the “right” choice of d is 0, and any additional coding directly results in larger
generalization error; but the training error, ²̂1 (d), decays steadily with d. The idea is that
even though the training error suggests that we make progress towards approximating the
unknown target by increasing the complexity of our hypothesis, in reality we are best off
by choosing the simplest possible hypothesis.
In Problem 2, a large amount of coding is required to achieve nontrivial generalization
error; but the training error remains large as d increases (until d = m/2, when the training
error drops rapidly). The idea here is that the training error suggests that we make little or
no progress towards approximating the unknown target by increasing the complexity of our
hypothesis, even though that is exactly what we should do for optimal generalization.
Thus in both problems, the training error is a misleading indicator of generalization. The
proof exploits the fact that if a penalty-based algorithm manages to compensate for the
misleading behavior of the training error in one problem, it cannot do so in the other (since
the relationship between training and generalization error in the two problems is reversed).
More precisely, we will arrange things so that Problem 1 has the following properties:
1. The expected training error ²̂1 (d) lies above the linear function f (d) = η1 (1 − η1 ) −
d/(2m), whose y-intercept is η1 (1−η1 ), and whose x-intercept is 2η1 (1−η1 )m ≤ m/2;
2. The expected generalization error ²1 (d) is minimized at d = 0, and furthermore, for
any constant c we have ²1 (cm) ≥ c/2.
Here η1 will be the rate at which classification noise corrupts the examples for Problem 1.
We will next arrange that Problem 2 will obey:
1. The expected training error ²̂2 (d) = a1 for 0 ≤ d ≤ 2η1 (1 − η1 )m ≤ m/2, where
η1 (1 − η1 ) > a1 ;
2. The expected generalization error ²2 (d) is lower bounded by a1 for 0 ≤ d < m/2, but
²2 (m/2) = 0.
In Figure 26 we illustrate the conditions on ²̂(d) for the two problems, and also include
hypothetical instances of ²̂1 (d) and ²̂2 (d) that are consistent with these conditions (and are
furthermore representative of the “true” behavior of the ²̂(d) functions actually obtained for
the two problems we define in a moment).
We can now give the underlying logic of the proof using the hypothetical ²̂1 (d) and ²̂2 (d).
Let d˜1 denote the complexity chosen by G for Problem 1, and let d˜2 be defined similarly.
First consider the behavior of G on Problem 2. In this problem we know by our assumptions
on ²2 (d) that if G fails to choose d˜2 ≥ m/2, ²G 2 ≥ a1 , already giving a constant lower
bound on ²G 2 for this problem. This is the easier case; thus let us assume that d˜2 ≥ m/2,
and consider the behavior of G on Problem 1. Let us define d0 by ²̂1 (d0 ) = a1 . Referring
to Figure 26, we see that for 0 ≤ d ≤ d0 we have ²̂1 (d) ≥ ²̂2 (d), and thus
For 0 ≤ d ≤ d0 , G(²̂1 (d), d/m) ≥ G(²̂2 (d), d/m) (50)
(because penalty-based algorithms assign greater penalties for greater training error or
greater complexity). Since we have assumed that d˜2 ≥ m/2, we know that
˜ d˜2 /m)
For d < m/2, G(²̂2 (d), d/m) ≥ G(²̂2 (d), (51)
and in particular, this inequality holds for 0 ≤ d ≤ d0 . On the other hand, by our choice of
²̂1 (d), ²̂1 (d˜2 ) = 0 (and thus ²̂2 (d˜2 ) ≥ ²̂1 (d˜2 )). Therefore,
G(²̂2 (d˜2 ), d˜2 /m) ≥ G(²̂1 (d˜2 ), d˜2 /m) . (52)
Combining the three inequalities above (Equations (50), (51) and (52)), we have that
For 0 ≤ d ≤ d0 , G(²̂1 (d), d/m) ≥ G(²̂1 (d˜2 ), d˜2 /m) (53)
from which it directly follows that in Problem 1, G cannot choose 0 ≤ d˜1 ≤ d0 . From the
definition of f (d) in our first condition on Problem 1, it follows that d0 ≥ 2(η1 (1 − η1 ) −
1 ≥ ²1 (d0 ) ≥ η1 (1−η1 )−a1 ,

a1 ) m. Using the second condition on Problem 1 we get that ²G
and thus we have a constant lower bound on ²G1 .
Now we describe the two problems used in the proof, and briefly argue why they have
the desired properties. We are in fact already familiar with the first problem: the class
F1d is simply the class of all d-alternation functions over [0, 1], the target function is the
0-alternation function that classifies all examples as negative, the input distribution D1 is
uniform over [0, 1], and we may choose any constant noise rate η1 . Now clearly under
these settings we have ²opt opt
1 (0) = ²1 (0) = 0 (where we let ²i (d) denote ²opt (d) for
problem i), and ²1 (d) > 0 for any d > 0 (because the noise in the sample will cause us
to code “false alternations”). Furthermore, each additional false interval that is coded will
result in an additional Θ(1/m) generalization error, thus resulting in the desired property
²1 (cm) ≥ c/2. Finally, we obviously expect ²̂1 (0) = η1 , and using the same argument
applied in the explanation of Equation (14) (where in our case s = 0), we have that the
expected number of label alternations required to achieve training error 0 is 2η1 (1 − η1 )m.
Furthermore, for every d < 2η1 (1 − η1 )m, ²̂1 (d + 2) ≤ ²̂1 (d) − 1/m (since by adding
two switch points, at least one additional sample point can be labeled consistently). Hence,
²̂1 (d) must lie above the linear function whose slope is −1/(2m) and whose x-intercept is
2η1 (1 − η1 )m, as required.
For the second problem, let us begin with the input space {0, 1}N for some value N >>
m. The function class F2d consists of all parity functions in which only the variables
m/2
x1 , . . . , xd are permitted to appear, the target function f ∈ F2 is f (~x) = x1 ⊕· · ·⊕xm/2 ,
and the input distribution D2 is uniform over {0, 1} . The noise rate η2 = 0 (larger values
N
will work as well). Under these settings, it holds (since the probability of disagreement
between every two different parity functions is 1/2) that ²opt 2 (d) = 1/2 for 0 ≤ d <
m/2
m/2, thus implying that ²2 (d) ≥ 1/2 in the same range. Furthermore, since f ∈ F2 ,
opt
²2 (m/2) = 0 and with high probability (for a large enough sample) ²2 (m/2) = 0 and
²̂2 (d) ≈ 1/2 for 0 ≤ d < m/2. Note that we have almost satisfied the desired conditions
on Problem 2, using the value a1 = 1/2; however, the conditions on Problem 2 and the
lower bound argument given above require further that η1 (1 − η1 ) > a1 . We can easily
arrange this final condition by simply scaling down a1 , by adding a “special” point to the
domain on which all functions in F2d agree (details are omitted). Referring to Figure 26,
notice that the “optimal” setting of a1 is determined by the trade-off between a1 (which
lower bounds the error of algorithms failing on Problem 2) and d0 /m (which lower bounds
the error of algorithms failing on Problem 1). This concludes the proof of Theorem 6.
There are a number of limitations to Theorem 6, including the fact that the two problems
must be “tuned” for a particular sample size m, and the fact that Problem 2 relies on the
dramatic properties of the parity learning curve, which one might argue are atypical of
learning curves found in practice. However, we believe that the essential message of the
theorem remains relevant:
• There is no universal (that is, holding for all target functions, distribution, and hypothesis
classes) relationship between training and generalization error.
• By their very nature, penalty-based algorithms implicitly assume a particular relation-

ship between training and generalization error.
• If the assumed relationship is not accurate for the problem under consideration, gener-
alization error may suffer, possibly severely.
8. Conclusions
Based on both our experimental and theoretical results, we offer the following conclusions:
Model selection algorithms that attempt to reconstruct the curve ²(d) solely by examining
the curve ²̂(d) often have a tendency to overcode or undercode in their hypothesis for
small sample sizes, which is exactly the sample size regime in which model selection
is an issue. Such tendencies are not easily eliminated without suffering the reverse
tendency.
There exist model selection problems in which a hypothesis whose complexity is close
to the sample size should be chosen, and in which a hypothesis whose complexity is
close to 0 should be chosen, but that generate ²̂(d) curves with insufficient information
to distinguish which is the case. The penalty-based algorithms cannot succeed in both
cases, whereas CV can.
The error of CV can be bounded in terms of the error of any other algorithm. The only cases
in which the CV error may be dramatically worse are those in which phase transitions
occur in the underlying learning curves at a sample size larger than that held out for
training by CV.
Thus we see that both types of algorithms considered have their own Achilles’ Heel. For
penalty-based algorithms, it is an inability to distinguish two types of problems that call for
drastically different hypothesis complexities. For CV, it is phase transitions that unluckily
fall between (1 − γ)m examples and m examples.
Finally, we wish to remark that although we have limited our attention here to the case
of supervised learning of boolean functions, we believe that many of the principles uncov-
ered (such as the limitations of penalty-based algorithms, and the tracking abilities of cross
validation) will be applicable to practically any learning setting in which there is a model
minimizing an expected loss (generalization error) must be derived from independent ob-
servations from a source. A prime example for further investigation would be distribution
learning with respect to the Kullback-Liebler divergence (log loss), where ²opt -based upper
bounds for MDL-like rules are already known (Barron & Cover, 1991), yet there also exist
phase transitions for natural problems (Haussler, Kearns, Seung, & Sampolinsky, 1994).
Acknowledgments
We give warm thanks to Yoav Freund and Ronitt Rubinfeld for their collaboration on various
portions of the work presented here, and for their insightful comments. Thanks to Sebastian
Seung and Vladimir Vapnik for interesting and helpful conversations. Y. Mansour would
like to acknowledge the support of The Israel Science Foundation administered by The
Israel Academy of Science and Humanities and a grant of the Israeli Ministry of Science
and Technology. D. Ron would like to acknowledge the support of the Eshkol Fellowship
and the National Science Foundation Postdoctoral Research Fellowship.
Appendix: Experimental Details
All experimental results described in this paper are obtained for the intervals model selection
problem. Recall that in this problem, the function class Fd consists of all boolean functions
over the domain [0, 1] which have at most d alternations of label. There are two main
reasons for choosing this problem for our investigation. The first is that the complexity of
the hypothesis functions is unlimited; in particular, it is not hard to show that the Vapnik-
Chervonenkis dimension of Fd is d, and thus as d increases we allow arbitrarily complex
functions. The second reason is that this is one of the few cases in which training error
minimization is feasible12 . (A number of papers provide evidence for the intractability of
training error minimization for a variety of natural function classes (Pitt & Valiant, 1988,
Blum & Rivest, 1989, Kearns, Schapire, & Sellie, 1992).)
More precisely, there is an algorithm that on input an arbitrary sample S = {hxi , bi i}
(where xi ∈ [0, 1] and bi ∈ {0, 1}) and complexity value d, outputs a function in VS S (d).
The algorithm is based on dynamic programming, and a straightforward implementation
yields a running time that is O(dm2 ). However, we have developed a more sophisticated
implementation, described below that yields a running time of O(m log m). The algorithm
was implemented in the C++ programming language on an SGI Challenge XL with 8 150
MHz processors and 1 gigabyte of RAM. This implementation allowed execution of the
training error minimization algorithm on samples of size up to m ≈ 15000 in only a few
seconds of real time.
The fast training error minimization code was the heart of a more elaborate experimental
tool that offered the following features:
• The user specifies a target intervals function over [0, 1] in a file that indicates the values
at which the function changes label. Thus, a file containing the values 0.15, 0.40,
0.75 specifies the boolean function that is 1 on the interval [0, 0.15), 0 on the region
[0.15, 0.40), 1 on the region [0.40, 0.75) and 0 on the region [0.75, 1.0].
• The user specifies the sample size m, and the noise rate η with which the labels in
the sample will be corrupted with noise. The user also specifies one or more model
selection algorithms, such as GRM, MDL or CV.
• A random sample S of size m of the specified target function corrupted by the specified
noise rate is then generated by the program (inputs are drawn according to the uniform
distribution). For each value of d from 0 to m, S and d are then given to the training error
minimization code. This code returns a function h̃d ∈ VS S (d). If VS S (d) contains
functions giving different labelings to S, the code chooses the least in a lexicographic
ordering. The hypothesis selected from VS S (d) always has its label alternation points
exactly midway between sample inputs.
• For each h̃d , the true generalization error ²(h̃d ) is computed with respect to the specified
target function, thus allowing exact computation of the curve ²(d).
• For each h̃d , the total penalty assigned to h̃d by the chosen model selection algorithm is
computed from h̃d , S and d. Minimization of this total penalty with respect to d is then
performed by the code, resulting in the hypothesis h̃d˜ chosen by the specified model
selection algorithm. The error of this hypothesis can then be compared with that of
other model selection algorithms, as well as the optimal value mind {²(d)}.
The experiments given in the paper were all performed using a target function of 100
regions of equal width and alternating label. The code provides an option for repeated trials
at each sample size, which was used extensively in the experiments. The code produces plot
files that were averaged where appropriate. The postscript plots shown were generated by
reading the plot files generated by the code into the Xmaple system, which allows postscript
output.
An Efficient Training Error Minimization Algorithm
Let S = {(x1 , b1 ), . . . , (xm , bm ) be a labeled sample, where xi ∈ [0, 1] and bi ∈ {+, −}.
Assume without loss of generality that x1 < x2 < . . . < xm . We next show how to find a
hypothesis hd with d intervals that has minimum training error on S. We represent such a
hypothesis by a partition of the (ordered) examples in S into d consecutive subsequences,
S1 , . . . , Sd , where Sk = xik , xik +1 , . . . , xik+1 −1 . With each subsequence Sk , the hypoth-
esis associates a label `(Sk ) ∈ {+, −}, such that `(Sk ) 6= `(Sk+1 ). The hypothesis can
be defined on [0, 1] by using (xik −1 + xik )/2, for every 2 ≤ k ≤ d, as its d − 1 switch
points, and labeling the intervals consistently with `(·). We say that a hypothesis having i
intervals is optimal if it has minimum training error among all hypotheses with (exactly) i
intervals. We next show how to transform any optimal hypothesis having i intervals into
one having i − 2 intervals. We later discuss how this transformation can be used in order to
find an optimal hypothesis hd with d intervals, for every 1 ≤ d ≤ t, where t is the minimal
number of intervals of a hypothesis consistent with the sample.
Given an optimal i–intervals hypothesis hi , let S1 , . . . , Si , be the partition of the sample
into subsequences associated with hi , and let ì (·) be the corresponding labeling of the
subsequences. With each subsequence we associate an advantage, a(Sk ), which is defined
to be the number of examples in Sk whose label equals ì (Sk ), minus the number of examples
in Sk whose label differs from ì (Sk ). intuitively, the advantage of a subsequence measures
how advantageous it is to keep it labeled by its current label (or, equivalently, how damaging
it is to flip its label). In order to transform hi into an optimal i − 2–intervals hypothesis,
hi−2 , we do the following.
Let Sk , 1 < k < i, be a subsequence which has minimum advantage among all subse-
quences but the two external subsequences, S1 and Si . If a(Sk ) ≤ a(S1 ) + a(Si ) then
we flip the label of Sk . Namely, the new i − 2–intervals hypothesis, hi−2 , is associated
with the same partition and labeling of sample subsequences as hi , except, that it has a
single subsequence in place of the three subsequences Sk−1 , Sk and Sk+1 , and the label
of this subsequence equals ì (Sk−1 ) (= ì (Sk+1 ). If a(S1 ) + a(Si ) < a(Sk ), then hi−2
is obtained by flipping the labels of both S1 and Si , again decreasing the number of subse-
quences (and intervals) by two. The reason for this seemingly less natural modification is
that by flipping the label of a single external subsequence, the number of intervals is only
reduced by only 1, while we want to maintain the parity of the number of intervals.
Lemma 1 For every i, 3 ≤ i ≤ t, given an optimal hypothesis hi which has i–intervals,

hi−2 is an optimal hypothesis with i − 2 intervals.
Proof: Assume contrary to the claim that there exists a hypothesis gi−2 with i−2 intervals
which has strictly smaller training error than hi−2 . Thus ²̂(gi−2 ) < ²̂(hi−2 ) = ²̂(hi )+amin ,
where amin is the advantage of the subsequence(s) flipped when transforming hi into hi−1 .
We shall show that if such a hypothesis gi−2 exists then we could obtain a hypothesis gi
with i intervals which has strictly smaller error than hi , contradicting the optimality of
hi . Let T1 , . . . , Ti−2 be the sample subsequences associated with gi−2 , and for each Tj ,
1 ≤ j ≤ i−2, let `g (Tj ) be the label gi−2 assigns to Tj . Assume, without loss of generality,
that gi−2 cannot be improved by local changes. Namely, that the examples at the beginning
and the end of each subsequence (except perhaps for x1 and xm ) have the same label as
the subsequence. Note that this must be true for hi due to its optimality. Since gi−2 has
two intervals less than hi , some of its subsequences must contain subsequences of hi , and
furthermore, there must be disagreements in their labeling. More precisely, we consider
the following two cases:
1. Some Tj contains an internal subsequence Sk of hi , such that `g (Tj ) 6= ì (Sk ). Namely,

Tj is of the form RSk R0 , where R and R0 must be non-empty subsequences, since by
the optimality of hi , Sk must begin and end with examples labeled ì (Sk ), while the
opposite is true for Tj . But we know that a(Sk ) ≥ amin , and hence by breaking Tj into
three subsequences, R, Sk and R0 , and labeling Sk by ì (Sk ) we obtain an i–intervals
hypothesis gi such that
²̂(gi ) = ²̂(gi−2 ) − a(Sk ) < ²̂(hi−2 ) − amin = ²̂(hi )
contradicting the optimality of hi .
2. If Item 1 does not hold then it is not hard to verify by simple counting, that it must be
the case that both `g (T1 ) 6= ì (S1 ), and `g (Ti−2 ) 6= ì (Si ) in which case we create two
corresponding new intervals, resulting in a hypothesis gi such that ²̂(gi ) < ²̂(hi ).
Thus, in both cases we reach a contradiction to the optimality of hi , and the lemma follows.
Given any 1 ≤ d ≤ t, we find an optimal hypothesis which has d intervals as follows. Let
S1 , . . . , St be the minimal partition of the sample into single-labeled subsequences, and let
`t (Sk ) be the label of the examples in Sk . Clearly, a hypothesis ht defined based on this
partition and labeling, is consistent with the sample and is hence optimal. In case d has
the same parity as t, then starting from the optimal t–intervals hypothesis ht , we obtain a
sequence of hypotheses ht−2 , . . . , hd , where hi is an optimal i–intervals hypotheses, by
applying the transformation described above (t − d)/2 times. In case d has parity opposite
to t, we need to start with an optimal hypothesis having t − 1 intervals. It is not hard to
verify that such a hypothesis is very similar to the consistent one, except that one of the
external subsequences, S1 or St , is merged into a single subsequence with its neighboring
subsequence S2 (respectively, St−1 ). The label of the resulting subsequence is the label of
the latter subsequence.
Finally, we address the question of the running time of the algorithm. Note that by setting
d = 1, we can get all optimal hypotheses with an odd number of intervals, and by setting
d = 0 we get all optimal hypotheses with an even number of intervals. In both cases
we perform m/2 iterations (where in each iteration we transform an optimal i–intervals
hypothesis into an optimal i − 2–intervals hypothesis). If we keep the subsequences both in
a doubly-linked list, and in a heap (according to their advantage), we can implement each
iteration in O(log(m)) time, resulting in an O(m log m)-time algorithm.
Notes
1. Except in circumstances where confusion may result, for brevity we shall adopt the notational convention of
leaving implicit the many dependencies of the various quantities we define. Thus, we suppress the obvious
dependence of ²(h) on f and D, the dependence of empirical quantities on the random sample S, and so on.
2. Such a nested sequence is called a structure by Vapnik (1982), and is sometimes, but not always, the setting
in which model selection methods are examined.
3. We put the terms “bias” and “variance” in quotes in this paragraph to distinguish our informal use of them
from their related but more precise statistical counterparts.
4. A common way of informally expressing this behavior is to say that for small d, the functions in VS (d)
“underfit” the sample S, meaning that Fd is not sufficiently expressive to capture the underlying regularities
of f exposed by S, and for large d, the functions in VS (d) “overfit” the sample S.
5. We stress that our goal here is simply to give one instantiation of MDL. Other coding schemes are obviously
possible, including perhaps some that would yield better performance on the ensuing experiments. Further-
more, since we will make use of certain approximations in the calculation of the code lengths, it is perhaps
more accurate to think of the resulting model selection rule as “MDL-inspired” rather than MDL in the strictest
sense of the term. Nevertheless, we feel that the experimental results are indicative of the type of behavior
that is possible for MDL-style rules, and furthermore, several of our formal results will hold for essentially all
MDL instantiations.
6. Notice that in this encoding, we are actually using the sample inputs to describe h. It is not difficult to see that
under the assumption that the inputs are uniformly distributed in [0, 1], this can be replaced by discretizing
[0, 1] using a grid of resolution 1/p(m), for some polynomial p(·), and using the grid points to describe the
switches of h.
7. With appropriately modified assumptions, all of the formal results in the paper hold for the more general form
G(²̂(d), d, m), where we decouple the dependence on d and m. However, the simpler coupled form will
usually suffice for our purposes.
8. Similar results hold for a randomly chosen target function.
9. Similar results are obtained in experiments in which every occurrence of d in the GRM rule is replaced by an
“effective dimension” c0 d for any constant c0 < 1.
10. In fact, Vapnik (1982, page 160) gives a more general statement concerning the uniform estimation of proba-
bilities from their frequencies in a class of events of limited VC dimension.
11. Note that the plots in the figures are based on noisy data, while Theorem 1 assumes there is no noise. However,
as can be observed from Theorem 3, the bound on ²G (m) is the noisy case, is similar in structure to the bound
in the noise-free case.
12. This is important in light of our earlier assertion that a good model selection algorithm should at least perform
well when the underlying learning algorithm implements training error minimization, and we do not wish any
of our experimental results to be artifacts of the unknown properties of heuristics such as backpropagation or
ID3.
References
Barron, A. R., & Cover, T. M. (1991). Minimum complexity density estimation. IEEE Transactions on Information
Theory, 37, 1034–1054.
Blum, A., & Rivest R. L. (1989). Training a 3-node neural net is NP-Complete. In David S. Touretzky, editor,
Advances in Neural Information Processing Systems I, (pp. 494–501). Morgan Kaufmann, San Mateo, CA.
Cover T., & Thomas J. (1991). Elements of Information Theory. Wiley.
Haussler, D., & Kearns, M., & Seung, S., & Tishby, N. (1994). Rigourous learning curve bounds from statistical
mechanics. In Proceedings of the Seventh Annual ACM Confernce on Computational Learning Theory, (pp.
76–87).
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American
Statistical Association, 58, 13–30.
Kearns, M. (1995). A bound on the error of cross validation, with consequences for the training-test split. In
Advances in Neural Information Processing Systems 8. The MIT Press.
Kearns, M., & Schapire, R., & Sellie, L. (1992). Toward efficient agnostic learning. In Proceedings of the 5th
Annual Workshop on Computational Learning Theory, (pp. 341–352).
Pitt, L., & Valiant, L. (1988). Computational limitations on learning from examples. Journal of the ACM, 35,
965–984.
Quinlan, J., & Rivest, R. (1989). Inferring decision trees using the minimum description length principle. Infor-
mation and Computation, 80, 227–248.
Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14, 465–471.
Rissanen, J. (1986). Stochastic complexity and modeling. Annals of Statistics, 14, 1080–1100.
Rissanen, J. (1989). Stochastic Complexity in Statistical Inquiry, volume 15 of Series in Computer Science. World
Scientific.
Schaffer, C. (1994). A conservation law for generalization performance. In Proceedings of the Eleventh Interna-
tional Conference on Machine Learning, (pp. 259–265).
Seung, H. S., & Sompolinsky, H., & Tishby, N. (1992). Statistical mechanics of learning from examples. Physical
Review, A45, 6056–6091.
tone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical
Society B, 36, 111–147.
tone, M. (1977). Asymptotics for and against cross-validation. Biometrika, 64, 29–35.
Vapnik, V. (1982). Estimation of Dependences Based on Empirical Data. Springer-Verlag.
Vapnik, V., & Chervonenkis, A. (1971). On the uniform convergence of relative frequencies of events to their
probabilities. Theory of Probability and its Applications, 16, 264–280.
Wolpert, D. (1992). On the connection between in-sample testing and generalization error. Complex Systems, 6,
47–94.
Figure 1. Experimental plots of the functions ²(d) (lower curve with local minimum), ²η (d) (upper
curve with local minimum) and ²̂(d) (monotonically decreasing curve) versus complexity d for a
target function of 100 alternating intervals, sample size 2000 and noise rate η = 0.2. Each data point
represents an average over 10 trials. The flattening of ²(d) and ²η (d) occurs at the point where the
noisy sample can be realized with no training error. ; by convention, our algorithm never adds more
p Vapnik model of ²(d)
alternations of label than necessary to achieve zero training error. Note that the
as the sum of ²̂(d) plus a complexity penalty term of the approximate form d/m is fairly accurate
here; see Figure 2.
Figure 2. Plot of ²η (d) − ²̂(d) versus complexity d for the same experiments used to obtain Figure 1.
As function of d/m it appears that ²̂(d) − ²η (d) has an initial regime
p(for d << 100, or for this m,
d/m < 100/2000 = 0.05) with behavior that is approximately Θ( d/m), and a later regime (for
d/m >> 0.05) in which the behavior is linear in d/m.
Figure 3. Experimental plots of generalization errors ²mdl (m) (most rapid initial decrease), ²cv (m)
(intermediate initial decrease) and ²grm (m) (least rapid initial decrease) versus sample size m for
a target function of 100 alternating intervals and noise rate η = 0.20. Each data point represents an
average over 10 trials. Note that the “shelf” of ²mdl is approximately at the noise rate η = 0.20,
since MDL is coding all the noisy labels. Also, note by comparing the above plot to the plots in
Figures 9 and 11 that the performance of MDL relative to the other two methods is degrading as the
noise rate increases.
Figure 4. Experimental plots of hypothesis lengths d˜mdl (m) (most rapid initial increase), d˜cv (m)
(intermediate initial increase) and d˜grm (m) (least rapid initial increase) versus sample size m for a
target function of 100 alternating intervals and noise rate η = 0.20. Each data point represents an
average over 10 trials.
Figure 5. Experimental plots of generalization errors ²mdl (most rapid initial decrease), ²cv (interme-
diate initial decrease) and ²grm (least rapid initial decrease) as a function of sample size for a target
function of 100 alternating intervals and noise rate η = 0.0. Each data point represents an average
over 10 trials. Note the similar performance for the three methods in this noise-free case, where there
is no danger of “overcoding”.
Figure 6. Experimental plots of hypothesis lengths d˜mdl (most rapid initial increase), d˜cv (interme-
diate initial increase) and d˜grm (least rapid initial increase) as a function of sample size for a target
over 10 trials. In this noise-free case, all three methods rapidly settle on the target length.
Figure 7. Experimental plots of generalization errors ²mdl (most rapid initial decrease), ²cv (interme-
diate initial decrease) and ²grm (least rapid initial decrease) as a function of sample size for a target
over 10 trials. Note the appearance of a second regime in the relative behavior of MDL and GRM
with the introduction of noise.
over 10 trials. Note the correspondence between MDL’s rapid decay in ²mdl shortly after m = 2000
and the rapid drop of d˜mdl to the target value of 100.
Figure 9. Experimental plots of generalization errors ²mdl (most rapid initial decrease), ²cv (inter-
mediate initial decrease) and ²grm (least rapid initial decrease) as a function of sample size for a
target function of 100 alternating intervals and noise rate η = 0.30. Each data point represents an
average over 10 trials. Notice the increasing variance of CV performance as the noise rate increases;
this variance disappears asymptotically, but shows clearly at small sample sizes.
over 10 trials. In this and the other plots, the apparent quantization of d˜mdl during its transition
down to the target value of 100 is an artifact of the averaging; on any given run, the method will
choose between one of the two competing local minima at d = 100 and the point of consistency with
the sample. The 11 quantized values for d˜mdl observed during this transition simply represent the
number of times (0, . . . , 10) that one of the minima can be visited out of 10 trials.
Figure 11. Experimental plots of generalization errors ²mdl (top plot), ²cv (intermediate plot) and
²grm (bottom plot) as a function of sample size for a target function of 100 alternating intervals and
noise rate η = 0.40. Each data point represents an average over 10 trials. At this large noise rate,
²mdl fails to transition from its shelf at η even by m = 15000.
Figure 12. Experimental plots of hypothesis lengths d˜mdl (top plot), d˜cv (intermediate plot) and
d˜grm (bottom plot) as a function of sample size for a target function of 100 alternating intervals and
noise rate η = 0.40. Each data point represents an average over 10 trials.
Figure 13. MDL penalty as a function of complexity d for a single run on 500 examples of a target
function of 100 alternating intervals and noise rate η = 0.20. Notice the appearance of a local
minimum near the target length of 100.
Figure 14. MDL total penalty H(²̂(d)) + H(d/m) versus complexity d for a single run on 2000
examples of a target function of 100 alternating intervals and noise rate η = 0.20. There is a local
minimum at approximately d = 100, and the global minimum at the point of consistency with the
noisy sample.
Figure 15. MDL total penalty H(²̂(d)) + H(d/m) versus complexity d for a single run on 4000
examples of a target function of 100 alternating intervals and noise rate η = 0.20. The global
minimum has now switched from the point of consistency to the target value of 100.
Figure 16. Plot of the function H(2η(1 − η) + (s/m)(1 − 2η)2 ) − H(η) − H(s/m) as a function
of η for s/m = 0.01. Positive values predict that MDL will choose the “correct” complexity d = s,
while negative values predict that MDL will “overcode” by choosing d = d0 . For this value of s/m,
increasing the noise rate can only cause degradation of performance. However, note the nonmonotonic
behavior.
Figure 17. Plot of the function H(2η(1 − η) + (s/m)(1 − 2η)2 ) − H(η) − H(s/m) as a function
of η for s/m = 0.04. Note the behavior near 0, and see Figure 18.
Figure 18. Detail of Figure 17 for small η. Here the nonmonotonic behavior has an interesting effect:
increasing the noiserate may actually cause the value of d chosen by MDL to move from d = d0 to
the superior d = s.
Figure 19. GRM penalty as a function of complexity d for a single run on 500 examples of a target
function of 100 alternating intervals and noise rate η = 0.20.
p
Figure 20. GRM total penalty ²̂(d) + (d/m)(1 + 1 + ²̂(d)m/d) versus complexity d for a single
run on 2000 examples of a target function of 100 alternating intervals and noise rate η = 0.20.
Figure 21. GRM penalty as a function of complexity d for a single run on 4000 examples of a target
function of 100 alternating intervals and noise rate η = 0.20.
Figure 22. Experimental plots of generalization error ²grm (m) using complexity penalty multipliers
1.0 (slow initial decrease) and 0.5 (rapid initial decrease) on the complexity penalty term (d/m)(1 +
p
1 + ²̂(d)m/d) versus sample size m on a target of 100 alternating intervals and noise rate η = 0.20.
Each data point represents an average over 10 trials.
Figure 23. Experimental plots of hypothesis length d˜grm (m) using complexity penalty multipliers
1.0 (slow initial increase) and 0.5 (rapid initial increase) on the complexity penalty term (d/m)(1 +
p
1 + ²̂(d)m/d) versus sample size m on a target of 100 alternating intervals and noise rate η = 0.20.
Each data point represents an average over 10 trials.
Figure 24. Experimental plots of generalization error ²mdl using complexity penalty multipliers 1.0
(rapid initial decrease) and 1.25 (slow initial decrease) as a function of sample size on a target of 100
alternating intervals and noise rate η = 0.20. Each data point represents an average over 10 trials.
Figure 25. Experimental plots of hypothesis length d˜mdl using complexity penalty multipliers 1.0
(rapid initial increase) and 1.25 (slow initial increase) as a function of sample size on a target of 100
alternating intervals and noise rate η = 0.20. Each data point represents an average over 10 trials.
The adjustment to the rule here seems only to have caused damage, since the only effect is to keep
d˜grm at 0 (undercoding) until m is close to 2000, and then to rapidly approach 100 from below,
whereas in the unmodified (constant penalty multiplier 1.0) rule d˜grm approached 100 from above
at approximately the sample sample size, but achieved nontrivial generalization error in the initial
overcoding region. Some simple calculations indicate that even if the constant is increased only to the
value 1.0000001, the approach to 100 from below will still not commence until m > 2000. Larger
values for the constant will of course only perform even more poorly.
Figure 26. Figure illustrating the proof of Theorem 6. The dark lines indicate typical behavior for
the two training error curves ²̂1 (d) and ²̂2 (d), and the dashed lines indicate the provable bounds on
²̂1 (d). We use the notation d 0 to indicate the intersection point d0 of the proof.
Received November 29, 1995

Accepted November 5, 1996
Final Manuscript November 5, 1996

ml97 Modelselection

Uploaded by

Copyright:

Available Formats

ml97 Modelselection

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ml97 Modelselection

Uploaded by

Copyright:

Available Formats

Machine Learning, 27, 7–50 (1997)

An Experimental and Theoretical Comparison

YISHAY MANSOUR [email protected]

DANA RON [email protected]

Editor: Philip M. Long

In the model selection problem (sometimes also known as complexity regularization), we

Outline of the Paper

In Section 2, we provide a formalization of the model selection problem. In this formal-

stantiation of Rissanen’s Minimum Description Length Principle (MDL) (Rissanen, 1989),

and the version space

As a demonstration of the validity of this view, and as an introduction to a particular model

3. Three Algorithms for Model Selection

d˜ = argmind∈[0,m/2] {H(²̂(d)) + H(d/m)}. (11)

d˜ = argmind {G(²̂(d), d/m)} (12)

shall be called a penalty-based algorithm where G(·, ·) is referred to as a penalty-based

d˜ = argmind {²̂S 00 (h̃d )} (13)

4. A Controlled Experimental Comparison

2η(1 − η)(m − s) + (η 2 + (1 − η)2 )s = 2η(1 − η)m + (1 − 4η + 4η 2 )s (15)

5. A Bound on the Error for Penalty-Based Algorithms

Theorem 1 Let ({Fd }, f, D, L) be an instance of the model selection problem in which

chosen by the penalty-based model selection algorithm d˜ = argmind {G(²̂(d), d/m)} on a

we obtain the statement of the theorem.

²sgrm (m) ≤ min {²opt (d) + 2β(d, m, δ)} . (28)

≤ min {H (²opt (d) + β(d, m, δ)) + H(d/m)} + β(d˜mdl , m, δ) (30)

≤ min {H(²opt (d)) + H(β(d, m, δ)) + H(d/m)} + β(d˜mdl , m, δ) (31)

≤ min {H(²opt (d)) + 2H(β(d, m, δ))} + β(d˜mdl , m, δ) (32)

Theorem 2 Let ({Fd }, f, D, L) be an instance of the model selection problem in which

Using our assumption on the adequacy of L we have that as m → ∞,

Theorem 3 Let ({Fd }, f, D, L) be an instance of the model selection problem in which

Again, similarly to the proof of Theorem 1, we have that as m → ∞,

6. A Bound on the Additional Error of CV

In other words, the generalization error of CV on m examples is at most

for all d ≤ dmax . Therefore with probability at least 1 − δ

7. Limitations on Penalty-Based Algorithms

1 (m) ≥ min{²1 (d)} + λ

2 (m) ≥ min{²2 (d)} + λ.

For 0 ≤ d ≤ d0 , G(²̂1 (d), d/m) ≥ G(²̂2 (d), d/m) (50)

G(²̂2 (d˜2 ), d˜2 /m) ≥ G(²̂1 (d˜2 ), d˜2 /m) . (52)

For 0 ≤ d ≤ d0 , G(²̂1 (d), d/m) ≥ G(²̂1 (d˜2 ), d˜2 /m) (53)

1 ≥ ²1 (d0 ) ≥ η1 (1−η1 )−a1 ,

• By their very nature, penalty-based algorithms implicitly assume a particular relation-

Appendix: Experimental Details

An Efficient Training Error Minimization Algorithm

Lemma 1 For every i, 3 ≤ i ≤ t, given an optimal hypothesis hi which has i–intervals,

1. Some Tj contains an internal subsequence Sk of hi , such that `g (Tj ) 6= `i (Sk ). Namely,

²̂(gi ) = ²̂(gi−2 ) − a(Sk ) < ²̂(hi−2 ) − amin = ²̂(hi )

contradicting the optimality of hi .

Received November 29, 1995

You might also like