Metric-Based Methods for Adaptive Model Selection and Regularization.
We present a general approach to model selection and regularization that exploits unlabeled data to adaptively control hypothesis complexity in supervised learning tasks. The idea is to impose a metric structure on hypotheses by determining the discrepancy between their predictions across the distribution of unlabeled data. We show how this metric can be used to detect untrustworthy training error estimates, and devise novel model selection strategies that exhibit theoretical guarantees against over-fitting (while still avoiding under-fitting). We then extend the approach to derive a general training criterion for supervised learningyielding an adaptive regularization method that uses unlabeled data to automatically set regularization parameters. This new criterion adjusts its regularization level to the specific set of training data received, and performs well on a variety of regression and conditional density estimation tasks. The only proviso for these methods is that sufficient unlabeled training data be available.
Introduction
In supervised learning, one takes a sequence of training pairs hx
and attempts to infer a hypothesis function
prediction error err(h(x); y) on future test examples. This basic paradigm
covers many of the tasks studied in machine learning research, including: re-
gression, where Y is typically IR and we measure prediction error by squared
dierence or some similar loss; classication, where Y
is typically a small discrete set and we measure prediction error with the
misclassication loss err(^y;
where we assume, for example, that Y is a classication label from f0; 1g
Y is a probabilistic prediction in [0; 1], and we measure prediction error
using the log loss err(^y;
(also known as the
cross-entropy error [Bis95]).
Regardless of the specics of these scenarios, one always faces the classical
over-tting versus under-tting dilemma in supervised learning: If the
hypothesis is chosen from a class that is too complex for the data, there
is a good chance it will exhibit large test error even though its training
error is small. This occurs because complex classes generally contain several
hypotheses that behave similarly on the training data and yet behave
quite dierently in other parts of the domain|thus diminishing the ability
to distinguish good hypotheses from bad. (Note that signicantly different
hypotheses cannot be simultaneously accurate.) Therefore, one must restrict
the set of hypotheses to be able to reliably dierentiate between accurate
and inaccurate predictors. On the other hand, selecting hypotheses from an
overly restricted class can prevent one from being able to express a good
approximation to the ideal predictor, thereby causing important structure
in the training data to be ignored. Since both under-tting and over-tting
result in large test error, they must be avoided simultaneously.
This tradeo between over-tting and under-tting is a fundamental
dilemma in machine learning and statistics. In this paper, we are primarily
interested in investigating automated methods for calibrating hypothesis
complexity to given training data. Most of the techniques that have been
developed for this process fall into one of three basic categories: model se-
lection, regularization, and model combination.
In model selection one rst takes a base hypothesis class, H, decomposes it
into a discrete collection of subclasses H 0  H 1    organized in
a nested chain, or lattice) and then, given training data, attempts to identify
the optimal subclass from which to choose the nal hypothesis. There have
been a variety of methods proposed for choosing the optimal subclass, but
most techniques fall into one of two basic categories: complexity penalization
(e.g., the minimum description length principle [Ris86] and various statistical
selection criteria [FG94]); and hold-out testing (e.g., cross-validation and
bootstrapping [Efr79]).
Regularization is similar to model selection except that one does not impose
a discrete decomposition on the base hypothesis class. Instead a penalty
criterion is imposed on the individual hypotheses, which either penalizes their
parametric form (e.g., as in ridge regression or weight decay in neural net-work
training [CM98, Rip96, Bis95]) or penalizes their global smoothness
properties (e.g., minimizing curvature [PG90]).
Model combination methods do not select a single hypothesis but rather
take a weighted combination of base hypotheses to form a composite predic-
tor. Composing base functions in this way can have the eect of smoothing
out erratic hypotheses (e.g., as in Bayesian model averaging [Mac92] and
bagging [Bre96]), or increasing the representation power of the base hypothesis
class through linear combinations (e.g., as in boosting [FS97] and neural
network ensemble methods [KV95]).
All of these methods have shown impressive improvements over naive
learning algorithms in every area of supervised learning research. However,
one di-culty with these techniques is that they usually require expertise to
apply properly, and often involve free parameters that must be set by an
informed practitioner.
In this paper we introduce alternative methods for model selection and
regularization that attempt to improve on the robustness of standard ap-
proaches. Our idea is to use unlabeled data to automatically penalize hypotheses
that behave erratically o the labeled training set. In Section 3
we rst investigate how unlabeled data can be used to perform model selection
in nested sequences of hypothesis spaces. The strategies we develop are
shown to experimentally outperform standard model selection methods, and
are proved to be robust in theory. Then in Section 4 we consider regularization
and show how our proposed model selection strategies can be extended
to a generalized training objective for supervised learning. Here the idea is
to use unlabeled data to automatically tune the degree of regularization for a
given task without having to set free parameters by hand. We show that the
resulting regularization technique adapts its behavior to a given training set
and can outperform standard xed regularizers for a given problem. Note,
however, that we do not address model combination methods in this paper
[KV95], instead leaving this to future work.
The work reported here extends the earlier conference papers [Sch97,
SS00].
Metric structure of supervised learning
In this paper we will consider the metric structure on a space of hypothesis
functions that arises from a simple statistical model of the supervised learning
problem: Assume that the examples hx; yi are generated by a stationary joint
distribution P XY on X  Y . In learning a hypothesis function
we are primarily interested in modeling the conditional distribution P YjX .
However, here we will investigate the utility of using extra information about
the marginal domain distribution P X to choose a good hypothesis. Note
that information about P X can be obtained from a collection of unlabeled
training examples x are often in abundant supply in many
applications|for example, text processing and computer perception). The
signicance of having information about the domain distribution P X is that
it denes a natural (pseudo) metric on the space of hypotheses. That is, for
any two hypothesis functions f and g we can obtain a measure of the distance
between them by computing the expected disagreement in their predictions
Z
(1)
where err(^y; y) is the natural measure of prediction error for the problem at
hand (e.g., regression or classication) and ' is an associated normalization
function that recovers the standard metric axioms. Specically, we will be
interested in obtaining the metric properties: nonnegativity d(f; g)  0,
symmetry and the triangle inequality d(f; g)  d(f;
d(h; g). It turns out that most typical prediction error functions admit a
metric of this type.
For example, in regression we measure the distance between two prediction
functions by
Z
where the normalization function establishes the metric proper-
ties. In classication, we measure the distance between two classiers by
Z
where no normalization is required to achieve a metric. (In conditional density
estimation, one can measure the \distance" between two conditional
probability models by their Kullback-Leibler divergence, which technically is
not a metric but nevertheless supplies a useful measure [CT91].)
In each of these cases, the resulting distances can be e-ciently calculated
by making a single pass down a list of unlabeled examples. Importantly, these
denitions can be generalized to include the target conditional distribution
in an analogous manner:
Z Z
(2)
That is, we can interpret the true error of a hypothesis function h with respect
to a target conditional P YjX as a distance between h and P YjX . The signicance
of this denition is that it is consistent with the previous denition (1) and
we can therefore embed the entire supervised learning problem in a common
metric space structure.
To illustrate, in regression the denition (2) yields the root mean squared
error of a hypothesis
Z Z
and in classication it gives the true misclassication probability
Z Z
(In conditional probability modeling it gives the expected log loss|or KL-divergence
to P YjX |which again, yields a useful measure, although it is not
a metric.)
Together, denitions (1) and (2) show how we can impose a global metric
space view of the supervised learning problem (Figure 1): Given labeled
training examples hx the goal is to nd the hypothesis h
in a space H that is closest to a target conditional P YjX under the distance
measure (2). If we are also given a large set of auxiliary unlabeled exam- Figure 1
ples x 0
r , then we can also accurately estimate the distances between
alternative hypotheses f and g within H; eectively giving us (1)
r
r
That is, for su-ciently large r, the distances dened in (3) will be very close
to the distances dened in (1). However, the distances between hypotheses
and the target conditional P YjX (2) can only be weakly estimated using the
(presumably much smaller) set of labeled training data
d
which need not be close to (2). The challenge then is to approximate the
closest hypothesis to the target conditional as accurately as possible using
the available information (3) and (4) in place of the true distances (1) and
(2).
Below we will use this metric space perspective to devise novel model
selection and regularization strategies that exploit inter-hypothesis distances
measured on an auxiliary set of unlabeled examples. Our approach is applicable
to any supervised learning problem that admits a reasonable metric
structure. In particular, all of our strategies will be expressed in terms of
a generic distance measure which does not depend on other aspects of the
problem. (However, for the sake of concreteness, we will focus on regression
as a source of demonstration problems initially, and return to classication
and conditional density estimation examples near the end of the paper.)
3 Model selection
We rst consider the process of using model selection to choose the appropriate
level of hypothesis complexity to t to data. This, conceptually, is the
simplest approach to automatic complexity control for supervised learning:
the idea is to stratify the hypothesis class H into a sequence (or lattice)
of nested subclasses H 0  H 1  training data,
somehow choose a class that has the proper complexity for the given data.
To understand how one might make this choice, note that for a given training
sample we can, in principle, obtain the corresponding
sequence of empirically optimal functions h
d
The problem is to select one of these functions based on the observed training
errors d
however, that these errors
are monotonically decreasing (assuming we can fully optimize in each class)
and therefore choosing the function with smallest training error inevitably
leads to over-tting. So the trick is to invoke some other criterion beyond Figure 2
mere empirical error minimization to make the nal selection.
As mentioned, two basic model selection strategies currently predomi-
nate: complexity penalization and hold-out testing. However, neither of these
approaches attends to the metric distances between hypotheses, nor do they
oer an obvious way to exploit auxiliary unlabeled data. But by adopting the
metric space view of Section 2 we obtain an useful new perspective on model
selection: In our setting, the chain H 0  H 1      H can be interpreted as
a sequence of hypothesis spaces wherein we can measure the distance between
candidate hypotheses (using unlabeled data). Unfortunately, we still cannot
directly measure the distances from hypotheses to the target conditional P YjX
(just as before) and therefore must estimate them based on a small labeled
training sample. However, we can now exploit the fact that we have the
distances between functions in the sequence, and hence attempt to use this
additional information to make a better choice (Figure 2).
3.1
The rst intuition we explore is that inter-hypothesis distances can help us
detect over-tting in a very simple manner: Consider two hypotheses h k
and h k+1 that both have a small estimated distance to P YjX and yet have a
large true distance between them. In this situation, it should be clear that
we should be concerned about selecting the second hypothesis, because if
the true distance between h k and h k+1 is indeed large then both functions
cannot be simultaneously close to P YjX , by simple geometry. This implies that
at least one of the distance estimates to P YjX must be inaccurate, and we know
intuitively to trust the earlier estimate more than the latter (since h k+1 is
chosen from a larger class). In fact, if both d
really
were accurate estimates they would have to satisfy the triangle inequality
with the known distance d(h k ; h k+1 ); that is
d
Since these empirical distances eventually become signicant underestimates
in general (because the h i are explicitly chosen to minimize the empirical
distance on the labeled training set) the triangle inequality provides a useful
test to detect when these estimates become inaccurate. In fact, this basic
test forms the basis of a simple model selection strategy, TRI, that works
surprisingly well in many situations (Figure 3). Figure 3
3.2 Example: Polynomial regression
To demonstrate this method (and all subsequent methods we develop in this
paper) we rst consider the problem of polynomial curve tting. This is
a supervised learning problem where and the goal is to
minimize the squared prediction error, err(^y; Specically, we
consider polynomial hypotheses under the natural stratication
into polynomials of degree 0; etc. The motivation for
studying this task is that it is a classical well-studied problem, that still
attracts a lot of interest [CMV97, GRV96, Vap96]. Moreover, polynomials
create a di-cult model selection problem which has a strong tendency to
produce catastrophic over-tting eects (Figure 4). Another benet is that
polynomials are an interesting and nontrivial class for which there are e-cient
techniques for computing best t hypotheses. Figure 4
To apply the metric based approach to this task, we dene the metric d
in terms of the squared prediction error err(^y; with a square
root normalization discussed in Section 2. To evaluate the
e-cacy of TRI in this problem we compared its performance to a number of
standard model selection strategies, including: structural risk minimization,
SRM [CMV97, Vap96], RIC [FG94], SMS [Shi81], GCV [CW79], BIC [Sch78],
AIC [Aka74], CP [Mal73], and FPE [Aka70]. We also compared it to 10-fold
cross validation, CVT (a standard hold-out method [Efr79, WK91, Koh95]).
We conducted a simple series of experiments by xing a domain distribution
P X on xing various target functions f
(The specic target functions we used in our experiments are shown in Figure
5.) To generate training samples we rst drew a sequence of values,
computed the target function values f(x 1 ); :::; f(x t ), and added independent
Gaussian noise to each, to obtain the labeled training sequence
For a given training sample we then computed the series Figure 5
of best t polynomials h etc. Given this sequence,
each model selection strategy will choose some hypothesis h k on the basis of
the observed empirical errors. To implement TRI we gave it access to auxiliary
unlabeled examples x 0
r in order to compute the true distances
between polynomials in the sequence.
Our main emphasis in these experiments was to minimize the true distance
between the nal hypothesis and the target conditional P YjX . That is,
we are primarily concerned with choosing a hypothesis that obtains a small
prediction error on future test examples, independent of its complexity level. 1
To determine the eectiveness of the various selection strategies, we therefore
measured the ratio of the true error (distance) of the polynomial they
selected to the best true error among polynomials in the sequence h
etc. (This means that the optimum achievable ratio is 1.) The rationale for
doing this is that we wish to measure the model selection strategy's ability
to approximate the best hypothesis in the given sequence|not nd a better
function from outside the sequence. 2

Table

1 shows the results obtained for approximating a step function
corrupted by Gaussian noise. (The strategy ADJ
in the tables is explained in Section 3.3 below.) We obtained these results
by repeatedly generating training samples of a xed size and recording the
approximation ratio achieved by each strategy. These tables record the dis- Table 1
tribution of ratios produced by each strategy for training sample sizes of
respectively, using unlabeled examples to measure
inter-hypothesis distances|repeated over 1000 trials. The initial results appear
to be quite positive. TRI achieves median approximation ratios of 1.06
Prediction error is not the only criteria one could imagine optimizing in model selec-
tion. For example, one could be interested in nding a simple model of the underlying
phenomenon that gives some insight into its fundamental nature, rather than simply producing
a function that predicts well on future test examples [HC96]. However, we will
focus on the traditional machine learning goal of minimizing prediction error.
One could consider more elaborate strategies that choose hypotheses from outside the
sequence; e.g., by averaging several hypotheses together [KV95, OS96, Bre96]. However,
as mentioned, we will not pursue this idea in this paper.
and 1.08 for training sample sizes 20 and 30 respectively. This compares
favorably to the median approximation ratios 1.39 and 1.54 achieved by S-
RM, and 1.17 achieved by CVT in both cases. (The remaining complexity
penalization strategies, GCV, FPE, etc., all performed signicantly worse
on these trials.) However, the most notable dierence was TRI's robustness
against over-tting. In fact, although the penalization strategy SRM performed
reasonably well much of the time, it was prone to making periodic
but catastrophic over-tting errors. Even the normally well-behaved cross-validation
strategy CVT made signicant over-tting errors from time to
time. This is evidenced by the fact that in 1000 trials with a training sample
of size (Table 1) TRI produced a maximum approximation ratio of 2.18,
whereas CVT produced a worst case approximation ratio of 643, and the
penalization strategies SRM and GCV both produced worst case ratios of
percentiles were TRI 1.45, CVT 6.11, SRM 419, GCV
In fact, TRI's robustness against over-tting is not a surprise: One can
prove that TRI cannot produce an approximation ratio greater than 3 if we
make two simple assumptions: (i) that TRI makes it to the best hypothesis
hm in the sequence, and (ii) that the empirical error of hm is an underesti-
mate; that is, d
(Note that this second assumption is
likely to hold because we are choosing hypotheses by explicitly minimizing
d
Proposition 1 Let hm be the optimal hypothesis in the sequence h
(that is, be the hypothesis selected by
TRI. If (i) m  ' and (ii) d
Proof Consider a hypothesis h n which follows hm in the sequence, and
assume We show that h n must fail the triangle
test (5) with hm and therefore TRI will not select h n . First, notice that
the initial assumption about h n 's error along with the triangle inequality
imply that 3d(h
3 Although one might suspect that the large failures could be due to measuring relative
instead of absolute error, it turns out that all of these large relative errors also correspond
to large absolute errors|which we verify in Section 4.1 below.
now recall that d
(since the training errors are monotonically decreasing), and also,
by assumption, d
Therefore we have d(h
contradicts (5). Thus TRI will
not consider h n . Finally, since h ' cannot precede hm (by assumption (i)), h '
must satisfy
(Note that in Proposition 1, as well as Propositions 2 and 3 below, we
implicitly assume that we have the true inter-hypothesis distances d(h
which in principle must be measured on unlimited amounts of unlabeled data.
We discuss relaxing this assumption in Section 3.4 below.)
Continuing with the experimental investigation, we nd that the basic
avor of the results remains unchanged at dierent noise levels and for different
domain distributions P X . In fact, much stronger results are obtained
for wider tailed domain distributions like Gaussian (Table 2) and \di-cult"
target functions like sin(1=x) (Table 3). Here the complexity penalization Table 2

Table
methods (SRM, GCV, etc.) can be forced into a regime of constant catas-
trophe, CVT noticeably degrades, and yet TRI retains similar performance
levels shown in Table 1.
Of course, these results might be due to considering a pathological target
function from the perspective of polynomial curve tting. It is therefore
important to consider other more natural targets that might be better suited
to polynomial approximation. In fact, by repeating the previous experiments
with a more benign target function dierent
results. Table 4 shows that procedure TRI does not fare as well in this
case|obtaining median approximation ratios of 3.11 and 3.51 for training
sample sizes 20 and respectively (compared to 1.33 and 1.03 for SRM,
and 1.37 and 1.16 for CVT). A closer inspection of TRI's behavior reveals Table 4
that the reason for this performance drop is that TRI systematically gets
stuck at low even-degree polynomials (cf. Table 6). In fact, there is a simple
geometric explanation for this: the even-degree polynomials (after degree
all give reasonable ts to sin 2 (2x) whereas the odd-degree ts have a tail in
the wrong direction. This creates a signicant distance between successive
polynomials and causes the triangle inequality test to fail between the even
and odd degree ts, even though the larger even-degree polynomials give
a good approximation. Therefore, although the metric-based TRI strategy
is robust against over-tting, it can be prone to systematic under-tting in
seemingly benign cases. Similar results were obtained for tting a fth degree
target polynomial corrupted by the same level of Gaussian noise (Table 5).
This problem demonstrates that the rst assumption used in Proposition 1
above can be violated in natural situations (see Table 6). Consideration of Table 5

Table
this di-culty leads us to develop a reformulated procedure.
3.3 Strategy 2: Adjusted distance estimates
The nal idea we explore for model selection is to observe that we are actually
dealing with two metrics here: the true metric d dened by the joint
distribution P XY and an empirical metric ^
d determined by the labeled training
sequence Note that the previous model selection strategy
TRI ignored the fact that we could measure the empirical distance between
hypotheses d
on the labeled training data, as well as measure their
\true" distance d(h k ; h ' ) on the unlabeled data. However, the fact that we
can measure both inter-hypothesis distances actually gives us an observable
d and d in the local vicinity. We now exploit this observation
to attempt to derive an improved model selection procedure.
Given the two metrics d and ^
d, consider the triangle formed by two hypotheses
h k and h ' and the target conditional P YjX (Figure 6). Notice that
there are six distances involved|three real and three estimated, of which the
true distances to P YjX are the only two we care about, and yet these are the
only two that we do not have. However, we can now exploit the observed Figure 6
relationship between d and ^
d to adjust the empirical training error estimate
d
In fact, one could rst consider the simplest possible adjustment
based on the naive assumption that the observed relationship of the metrics
d and d between h k and h ' also holds between h ' and P YjX . Note that if this
were actually the case, we would obtain a better estimate of d(h simply
by re-scaling the training distance d
according to the observed ratio
(Since we expect ^
d to be an underestimate in general,
we expect this ratio to be larger than 1.) In fact, by adopting this as a
simple heuristic we obtain another model selection procedure, ADJ, which is
also surprisingly eective (Figure 7). This simple procedure overcomes some
of the under-tting problems associated with TRI and yet retains much of
TRI's robustness against over-tting. Figure 7
Although at rst glance this procedure might seem to be ad hoc, it turns
out that one can prove an over-tting bound for ADJ that is analogous to
that established for TRI. In particular, if we assume that (i) ADJ makes it to
the best hypothesis hm in the sequence, and (ii) the adjusted error estimate
d d
is an underestimate, then ADJ cannot over-t by a factor much
greater than 3.
Proposition 2 Let hm be the optimal hypothesis in the sequence h
and let h ' be the hypothesis selected by ADJ. If (i) m  ' and (ii)
d d
d
d
Proof By the denition of ADJ we have that
d d
since ADJ selects h ' in favor of hm . We show that this implies a bound on
test error d(h in terms of the optimum available test error
First, by the triangle inequality we have d(h
well as d
d
d
Note that by the denition of ADJ (and since m  ') this yields
d d
d
d
d
d
So from (9) and (8) and the assumption that d d
obtain
d
d
d d
d d
Simple algebraic manipulation then shows that
d
d
d
d
d
d
d
d
d
d
In this respect, not only does ADJ exhibit robustness against over-tting,
it also has a (weak) theoretical guarantee against under-tting. That is,
if we make the assumptions that: (i) the empirical distance estimates are
underestimates, and (ii) the adjusted distance estimates strictly increase the
empirical distance estimates; then if the true error of a successor hypothesis
hm improves the true error of all of its predecessors h ' by a signicant factor,
hm will be selected in lieu of its predecessors.
Proposition 3 Consider a hypotheses hm , and assume that (i) d
m. Then if
d
for all 0  ' < m (that is, d(h su-ciently small) it follows that
d d
d d
therefore ADJ will not choose
any predecessor in lieu of hm .
Proof By the triangle inequality we have d
and
d
d
Recall that by the denition of b b d we have
d d
d
d
for some 0  ' < m (specically, the ' leading to the largest
d d
Therefore by applying (11) to this particular ' we obtain
d d
d
d
The second step above follows from the assumption (i) that d
and the fact that d(h
Now, by applying (10) to both occurrences of d(h
d d
d
d
d
d
d
since
assumption (i)
d d
assumption (ii)
Therefore, although ADJ might not have originally appeared to be well
motivated, it possesses worst case bounds against over-tting and under-
tting that cannot be established for conventional methods. However, these
bounds remain somewhat weak: Table 6 shows that both ADJ and TRI
systematically under-t in our experiments. That is, even though assumption
(ii) of Proposition 1 is almost always satised (as expected), assumption
(ii) of Proposition 2 is only true one quarter of the time. Therefore,
Propositions 1 and 2 can only provide a loose characterization of the quality
of these methods. However, both metric-based procedures remain robust
against over-tting.
To demonstrate that ADJ is indeed eective, we repeated the previous
experiments with ADJ as a new competitor. Our results show that ADJ
robustly outperformed the standard complexity penalization and hold-out
methods in all cases considered|spanning a wide variety of target functions,
noise levels, and domain distributions P X . Tables 1{5 show the previous data
along with the performance characteristics of ADJ. In particular, Tables 4, 5
and 6 show that ADJ avoids the extreme under-tting problems that hamper
TRI; it appears to responsively select high order approximations when this is
supported by the data. Moreover, Tables 1{3 show that ADJ is still extremely
robust against over-tting, even in situations where the standard approaches
make catastrophic errors. Overall, this is the best model selection strategy we
have observed for these polynomial regression tasks, even though it possesses
a weaker guarantee against over-tting than TRI.
Note that both model selection procedures we propose add little computational
overhead to traditional methods, since computing inter-hypothesis
distances involves making only a single pass down the reference list of unlabeled
examples. This is an advantage over standard hold-out techniques like
CVT which repeatedly call the hypothesis generating mechanism to generate
pseudo-hypotheses|an extremely expensive operation in many applications.
Finally, we note that ADJ possesses a subtle limitation: the multiplicative
re-scaling it employs cannot penalize hypotheses that have zero training error.
(Therefore, we had to limit the degree of the polynomials to t 2 in the above
experiments to avoid null training errors.) However, despite this shortcoming,
the ADJ procedure turns out to perform very well in practice and most often
outperforms the more straightforward TRI strategy.
3.4 Robustness to unlabeled data
Before moving on to regularization, we brie
y investigate the robustness of
these model selection techniques to limited amounts of auxiliary unlabeled
data. In principle, one can always argue that the preceding empirical results
are not useful because the metric-based strategies TRI and ADJ might
require signicant amounts of unlabeled data to perform well in practice.
(However, the 200 unlabeled examples used in the previous experiments does
not seem that onerous.) In fact, the previous theoretical results (Propositions
assumed innite unlabeled data. To explore the issue of robustness to
limited amounts of unlabeled data, we repeated our previous experiments
but gave TRI and ADJ only a small auxiliary sample of unlabeled data to
estimate inter-hypothesis distances. In this experiment we found that these
strategies were actually quite robust to using approximate distances. Table 7
shows that small numbers of unlabeled examples were still su-cient for TRI
and ADJ to perform nearly as well as before. Moreover, Table 7 shows that
these techniques only seem to signicantly degrade once we consider fewer
unlabeled than labeled training examples. This robustness was observed Table 7
across the range of problems considered.
In fact, it is a straightforward exercise to theoretically analyze the robustness
of these procedures TRI and ADJ to approximation errors in the estimated
inter-hypothesis distances. In a model selection sequence h
there are only K(K 1)=2 pairwise distances that need to be estimated
from unlabeled data. This means that a straightforward \union bound" can
be combined with standard uniform convergence results [AB99] to obtain
an O
r
error bar on these estimates (at the 1 - condence level).
These error bars could easily be used to suitably adjust Propositions 1{3 to
account for the estimation errors. However, we do not pursue this analysis
here since it is straightforward but unrevealing.
Although the empirical results in this section are anecdotal, the paper
[SUF97] pursues a more systematic investigation of the robustness of these
procedures and reaches similar conclusions (also based on articial data).
Rather than present a detailed investigation of these model selection strategies
in more serious case studies, we rst consider a further improvement to
the basic method.
Regularization
One of the di-culties with model selection is that its generalization behavior
depends on the specic decomposition of the base hypothesis class one con-
siders. That is, dierent decompositions of H can lead to dierent outcomes.
To avoid this issue, we extend the previous ideas to a more general training
criterion that uses unlabeled data to decide how to penalize individual
hypotheses in the global space H. The main contribution of this section is
a simple, generic training objective that can be applied to a wide range of
supervised learning problems.
Continuing from above, we assume that we have access to a sizable collection
of unlabeled data which we now use to globally penalize complex
hypotheses. Specically, we formulate an alternative training criterion that
measures the behavior of individual hypotheses on both the labeled and unlabeled
data. The intuition behind our criterion is simple|instead of minimizing
empirical training error alone, we in addition seek hypotheses that
behave similarly both on and o the labeled training data. This objective
arises from the observation that a hypothesis which ts the training data well
but behaves erratically o the labeled training set is not likely to generalize
to unseen examples. To detect erratic behavior we measure the distance a
hypothesis exhibits to a xed \origin" function  (chosen arbitrarily) on both
data sets. If a hypothesis is behaving erratically o the labeled training set
then it is likely that these distances will disagree. This eect is demonstrated
in

Figure

8 for two large degree polynomials that t the labeled training data
well, but dier dramatically in their true error and their dierences between
on and o training set distance to a simple origin function. (Note that we will Figure 8
use trivial origin functions throughout this section, such as the zero function
or the constant function
y at the mean of the y labels.)
To formulate a concrete training objective we rst propose the following
tentative measures: empirical training error plus an additive penalty
d
and empirical error times a multiplicative penalty
d
d
In each case we compare the behavior of a candidate hypothesis h to the xed
origin . Thus, in both cases we seek to minimize empirical training error
d
(or times) a penalty that measures the discrepancy between
the distance to the origin on the labeled training data and the distance
to the origin on unlabeled data. The regularization eect of these criteria
is illustrated in Figure 8. Somewhat surprisingly, we have found that the
multiplicative objective (13) generally performs much better than (12), as it
more harshly penalizes discrepancies between on and o training set behavior.
Therefore, this is the form we adopt below.
Although these training criteria might appear to be ad hoc, they are not
entirely unprincipled. One useful property they have is that if the origin
function  happens to be equal to the target conditional P YjX , then minimizing
(12) or (13) becomes equivalent to minimizing the true prediction error
However, despite the utility of this technique, it turns out that
these initial training objectives have the inherent drawback that they subtly
bias the nal hypotheses towards the origin function . That is, both (12)
and (13) allow minima that have \articially" large origin distances on the
labeled data d
simultaneously small distances on unlabeled data
For example, this is illustrated in Figure 8 for a hypothesis function
g that minimizes (13) but is clearly attracted to the origin  at the right
end of the domain (o of the labeled training data). Of course, such a bias
towards  can be desirable if  happens to be near the target conditional
P YjX . In this sense,  could serve as a useful prior on hypotheses. However,
there is no reason to expect  to be anywhere near P YjX in practice, especially
when considering the trivial constant functions used in this paper.
Nevertheless, there is an intuitive way to counter this di-culty: to avoid
the bias towards , we introduce symmetric forms of the previous criteria
that also penalize hypotheses which are unnaturally close to the origin
the labeled data. That is, one could consider a symmetrized form of the
additive penalty (12)
d
as well as a symmetrized form of the multiplicative penalty (13)
d
d
d
These penalties work in both directions: hypotheses that are much further
from the origin on the training data than are penalized, but so are hypotheses
that are signicantly closer to the origin on the training data than
o. The rationale behind this symmetric criterion is that both types of erratic
behavior indicate that the observed training error is likely to be an
unrepresentative re
ection of the hypothesis's true error. The value of this
intuition is demonstrated in Figure 9, where the hypothesis f that minimizes
the symmetric criterion (15) is not drawn towards the origin inappropriately,
and thereby achieves a smaller true prediction error than the hypothesis g
that minimizes (13). Figure 9
These symmetric training criteria can also be given a technical justi-
cation: First, if the origin function  happens to be equal to the target
conditional minimizing either (14) or (15) comes very close to
minimizing the true prediction error d(h; P YjX ). To see this for the multiplicative
criterion (15), let h be the hypothesis that achieves the minimum
and note that if d
the criterion becomes equivalent
to d
the criterion becomes equivalent to d(h; P YjX )r 2 for
In the latter case, since h minimizes (15) we must have d(h; P YjX ) <
for the Bayes optimal hypothesis h  . But since h
is not directly optimized on the training set (it remains xed), we will usually
have
which means that d(h; P YjX )
will tend to be close to d(h  ; P YjX ). Thus, minimizing (15) will result in near
optimal generalization performance in this scenario. (Note that this property
would not hold for naively smoothed versions of this objective.)
In the more general case where the origin does not match the target,
the symmetric criteria will also still provably penalize hypotheses that have
small training error and large test error. To see this for (15), note that for
any hypothesis h
d
d
by the triangle inequality. Since  and P YjX are not optimized on the training
set we can expect d
sizes. Thus, (16)
shows that if d
(greater than k d(; P YjX ), k  3), then h's training error must be penalized
by a signicant ratio (at least k 1). By contrast, an alternative hypothesis g
that achieves comparable training error and yet exhibits balanced behavior
on and o the labeled training set (that is, such that d
will be strongly preferred; in fact, such a g cannot over-t by the same amount
as h without violating (16). Importantly, the Bayes optimal hypothesis h
will also tend to have d
it too does not depend on the training set. Thus, h  will typically achieve a
small value of the objective, which will force any hypothesis that has a large
over-tting error (relative to d(; P YjX )) to exhibit an objective value greater
than the minimum.
Note that the sensitivity of the lower bound (16) clearly depends on the
distance between the origin and the target. If the origin is too far from the
target then the lower bound is weakened and the criterion (15) becomes less
sensitive to over-tting. However, our experiments show that the objective
is not unduly sensitive to the choice of , so long as is not too far from the
data. In fact, even simple constant functions generally su-ce. 4
The outcome is a new regularization procedure that uses the training objective
(15) to penalize hypotheses based on the given training data and on
the unlabeled data. The resulting procedure, in eect, uses the unlabeled
data to automatically set the level of regularization for a given problem. Our
goal is to apply the new training objective to various hypothesis classes and
see if it regularizes eectively across dierent data sets. We demonstrate this
for several classes below. However, the regularization behavior is even sub-
tler: since the penalization factor in (15) also depends on the specic labeled
training set under consideration, the resulting procedure regularizes in a data
dependent way. That is, the procedure adapts the penalization to the particular
set of observed data. This raises the possibility of outperforming any
regularization scheme that keeps a xed penalization level across dierent
training samples drawn from the same problem. In fact, we demonstrate below
that such an improvement can be achieved in realistic hypothesis classes
on real data sets.
4.1 Example: Polynomial regression
The rst supervised learning task we consider is the polynomial regression
problem considered in Section 3.2. The regularizer introduced above (15)
turns out to perform very well in such problems. In this case, our training
4 One could easily imagine trying more complex origin functions such as low dimensional
polynomials or smooth interpolant functions. We did not explore these ideas in this paper,
primarily because we wished to emphasize the robustness of the method to even very simple
choices of origin. However, one extension that we did investigate was to use a set of origin
functions penalize according to the maximum ratio|but this did not yield
any signicant improvements.
objective can be expressed as choosing a hypothesis to minimize
is the set of labeled training data, fhx j ig r
j=1 is a set of
unlabeled examples, and  is a xed origin (which we usually just set to be
the constant function at the mean of the y labels). Note again that this
training objective seeks hypotheses that t the labeled training data well
while simultaneously behaving similarly on the labeled and unlabeled data.
To test the basic eectiveness of our approach, we repeated the experiments
of Section 3.2. The rst class of methods we compared against were
the same model selection methods considered before: 10-fold cross validation
CVT, structural risk minimization SRM [CMV97], RIC [FG94]; SMS [Shi81],
GCV [CW79], BIC [Sch78], AIC [Aka74], CP [Mal73], FPE [Aka70], and the
metric based model selection strategy, ADJ, introduced in Section 3.3. How-
ever, since none of the statistical methods, RIC, SMS, GCV, BIC, AIC, CP,
FPE, performed competitively in our experiments, we report results only for
GCV which performed the best among them. For comparison, we also report
results for the optimal model selector OPT* which makes an oracle choice of
the best available hypothesis in any given model selection sequence. In these
experiments, the model selection methods considered polynomials of degree
0 to t 2. 5
The second class of methods we compared against were regularization
methods, which consider polynomials of maximum degree (t 2) but penalize
individual polynomials based on the size of their coe-cients or their
smoothness properties. The specic methods we considered were: a standard
form of \ridge" penalization (or weight decay) which places a penalty
k a 2
on polynomial coe-cients a k [CM98], and Bayesian maximum a posteriori
inference with zero-mean Gaussian priors on polynomial coe-cients a k with
diagonal covariance matrix I [Mac92]. 6 Both of these methods require a
regularization parameter  to be set by hand. We refer to these methods as
REG and MAP respectively.
5 Note that we restricted the degree to be less than t 1 to prevent the maximum degree
polynomials from achieving zero training error, which as discussed in Section 3, destroys
the regularization eect of the multiplicative penalty.
6 We did not test the more elaborate approach to Bayesian learning of polynomials
described in [You77].
To test the ability of our technique to automatically set the regularization
level we tried a range of (fourteen) regularization parameters  for the xed
regularization methods REG and MAP. For comparison purposes, we also
report the results of the oracle regularizers, REG* and MAP*, which select
the best  value for each training set. Our experiments were conducted by
repeating the experimental conditions of Section 3.2. Specically, Table 8
repeats Table 1 (tting a step function), Table 9 repeats Table 3 (tting
sin(1=x)),

Table

repeats Table 4 (tting sin 2 (2x)), and Table 11 repeats

Table

5 (tting a fth degree polynomial). The regularization criterion based Table 8

Table

Table

Table
on minimizing (15) is listed as ADA in our gures (for \adaptive" regular-
ization). 7 We also tested ADA using dierent origin functions y,
y, 2 max y, 4 y, 8 max y to examine its robustness to , and also
tested the one-sided version of ADA (13) to verify the benets of the symmetrized
criterion (15) over (13).
The results once again are quite positive. The rst observation is that the
model selection methods generally did not fare as well as the regularization
techniques on these problems. Model selection seems prone to making catastrophic
over-tting errors in these polynomial regression problems, whereas
regularization appears to retain robust control. As noted, even the frequently
trusted 10-fold cross validation procedure CVT did not fare well in our
experiments. The only model selection strategy to perform reasonably well
(besides the oracle model selector OPT*) was the metric-based method ADJ,
which also exploits unlabeled data.
The new adaptive regularization scheme ADA performed the best among
all procedures in these experiments. Tables 8{11 show that it outperforms
the xed regularization strategies (REG and MAP) for all xed choices of
regularization parameter , even though the optimal choice varies across
problems (MAP was inferior to REG in these experiments, and therefore
we do not report detailed results). This demonstrates that ADA is able to
eectively tune its penalization behavior to the problem at hand. Moreover,
since it outperforms even the best choice of  for each data set, ADA also
demonstrates the ability to adapt its penalization behavior to the specic
7 We used a standard optimization routine (Matlab 5.3 \fminunc") to determine co-
e-cients that minimize (14) and (15). Although the nondierentiability of (15) creates
di-culty for the optimizer, it does not prevent reasonable results from being achieved.
Another potential problem could arise if h gets close to the origin . However, since we
chose simple origins that were never near P YjX , h was not drawn near  in our experiments
and thus the resultant numerical instability did not arise.
training set, not just the given problem. In fact, ADA is competitive with
the oracle regularizers REG* and MAP* in these experiments, and even
outperformed the oracle model selection strategy OPT* on two problems.
It is clear that ADA is fairly robust to the choice of , since moving  to
a distant constant origin (even up to eight times the max y value) did not
completely damage its performance. The results also show that the one-sided
version of ADA based on (13) is inferior to the symmetrized version in these
experiments, conrming our prior expectations.
4.2 Example: Radial basis function regression
To test our approach on a more realistic task, we considered the problem
of regularizing radial basis function (RBF) networks for regression. RBF
networks are a natural generalization of interpolation and spline tting tech-
niques. Given a set of prototype centers c 1 ; :::; c k , an RBF representation of
a prediction function h is given by

where is the Euclidean distance between x and center c i , and g is
a response function with width parameter . In this experiment we use a
standard local (Gaussian) basis function
Fitting with RBF networks is straightforward. The simplest approach is
to place a prototype center on each training example and then determine the
weight vector w that allows the network to t the training y labels. The best
weight vector can be obtained by solving for w in6 6 6 4
kx1 x1k
g
g
(the solution is guaranteed to exist and be unique for distinct training points
and most natural basis functions g, including the Gaussian basis used here
[Bis95]).
Although exactly tting data with RBF networks is natural, it has the
problem that it generally over-ts the training data in the process of replicating
the y labels. Many approaches therefore exist for regularizing RBF
networks. However, these techniques are often hard to apply because they
involve setting various free parameters or controlling complex methods for
choosing prototype centers, etc. [CM98, Bis95]. The simplest regularization
approaches are to add a ridge penalty to the weight vector, and minimize
where h is given as in (17) [CM98]. An alternative approach is to add a
non-parametric penalty on curvature [PG90], but the resulting procedure is
similar. To apply these methods in practice one has to make an intelligent
choice of the width parameter  and the regularization parameter . Un-
fortunately, these choices interact and it is often hard to set them by hand
without extensive visualization and experimentation with the data set.
In this section we investigate how eectively the ADA regularizer is able
to automatically select the width parameter  and regularization parameter
in an RBF network on real regression problems. Here the basic idea is
to use unlabeled data to make these choices automatically and adaptively.
We compare ADA (15) to a large number of ridge regularization procedures,
each corresponding to the penalty (18) with dierent xed choices of  and
(thirty ve in total). To apply ADA in this case we simply ran a standard
optimizer over the parameter space (; ) while explicitly solving for the w
vector that minimizes (18) for each choice of  and  (which involves solving
a linear system [CM98, Bis95]). Thus, given ,  and w we could calculate
and supply the resulting value to the optimizer as the objective to be
minimized (cf. Footnote 7).
To conduct an experiment we investigated a number of regression problems
from the StatLib and UCI machine learning repositories. 8 In our ex-
periments, a data set was randomly split into a training (1/10), unlabeled
(7/10), and test set (2/10), and then each of the methods was run on this
split. We repeated the random splits 100 times to obtain our results. Tables
12{15 show that ADA regularization is able to choose width and regularization
parameters that achieve eective generalization performance across Table 12

Table

Table

Table
a range of data sets. Here ADA performs better than any xed regularizer
on every problem (except BODYFAT), and even beats the oracle regularizer
REG* on all but one problem. This shows that the adaptive criterion is not
8 The URLs are lib.stat.cmu.edu and www.ics.uci.edu/mlearn/MLRepository.html.
only eective at choosing good regularization parameters for a given prob-
lem, it can choose them adaptively based on the given training data to yield
improvements over xed regularizers.
5 Classication
Finally, we note that the regularization approach developed in this paper
can also be easily applied to classication and conditional density estimation
problems. In conditional density estimation, one can use KL divergence as a
proxy distance measure and still achieve interesting results (however we do
not report these experiments here).
In classication, the label set Y is usually a small discrete set and we measure
prediction error by the misclassication loss, err(^y;
distances are measured by the disagreement probability d(f;
g(x)). Using this metric, our generic regularization objective (15) can be
directly applied to classication problems. In fact, we have applied (15) to
the problem of decision tree pruning in classication, obtaining the results
shown in Table 16. Unfortunately, the results achieved in this experiment are
not strong, and it appears that the techniques proposed in this paper may
not work as decisively for classication problems as they do for regression
and conditional density estimation problems. Table
We believe that the weakness of the proposed methods for classication
might have an intuitive explanation however: Since classication functions
are essentially histogram-like (i.e., piecewise constant), they limit the ability
of unlabeled data to detect erratic behavior o the labeled training sample.
This is because histograms, being
at across large regions, tend to behave
similarly in large neighborhoods around training points|to the extent that
distances on labeled and unlabeled data points are often very similar, even for
complex histograms. Coping with this apparent limitation in our approach
remains grounds for future research.
6 Conclusion
We have introduced a new approach to the classical complexity-control problem
that is based on exploiting the intrinsic geometry of the function learning
task. These new techniques seem to outperform standard approaches in a
wide range of regression problems. The primary source of this advantage is
that the proposed metric-based strategies are able to detect dangerous situations
and avoid making catastrophic over-tting errors, while still being
responsive enough to adopt reasonably complex models when this is supported
by the data. They accomplish this by attending to the real distances
between hypotheses. (Standard complexity-penalization strategies completely
ignore this information. Hold-out methods implicitly take some of this
information into account, but do so indirectly and less eectively than the
metric-based strategies introduced here.) Although there is no \free lunch"
in general [Sch94] and we cannot claim to obtain a universal improvement
for every complexity-control problem [Sch93], we claim that one should be
able to exploit additional information about the task (here, knowledge of P X )
to obtain signicant improvements across a wide range of problem types and
conditions. Our empirical results for regression support this view.
A substantial body of literature has investigated unlabeled data in the
context of supervised learning, although not in the same way we have considered
in this paper. Most work in this area adopts the perspective of
parametric probability modeling and uses unlabeled data as part of a maximum
likelihood (EM) or discriminative training procedure [MU97, CC96,
RV95, GS91, O'N78]. Another common idea is to supply articial labels to
unlabeled examples and use this data directly in a supervised training procedure
[BM98, Tow96]. Unlabeled examples can also be used to construct a
\cover" of the hypothesis space and improve some worst case bounds on generalization
error [LP96]. However, none of this previous research explicitly
uses unlabeled data for automated complexity control. Perhaps the closest
work in spirit to ours is [KV95] which uses unlabeled examples to calculate
optimal combination weights in an ensemble of regressors. The emphasis in
[KV95] is on model combination rather than model selection and regulariza-
tion, but nevertheless there appears to be a close relationship between their
ideas and ours.
An important direction for future research is to develop theoretical support
for our strategies|in particular, a stronger theoretical justication of
the regularization methods proposed in Section 4 and an improved analysis
of the model selection methods proposed in Section 3. It remains open as
to whether the proposed methods TRI, ADJ, and ADA are in fact the best
possible ways to exploit the hypothesis distances provided by P X . We plan
to continue investigating alternative strategies which could potentially be
more eective in this regard. For example, it remains future work to extend
the multiplicative ADJ and ADA methods to cope with zero training errors.
Finally, it would be interesting to adapt the approach to model combination
methods, extending the ideas of [KV95] to other combination strategies,
including boosting [FS97] and bagging [Bre96].

Acknowledgements

Research supported by NSERC, MITACS, CITO and BUL. Thanks to Yoshua
Bengio, Adam Grove, Rob Holte, John Laerty, Joel Martin, John Platt, Lyle
Ungar, Jason Weston and anonymous referees for very helpful comments at
various stages of this research.



--R

Neural Network Learning: Theoretical Foundations.
Statistical predictor information.
A new look at the statistical model identi
Neural Networks for Pattern Recognition.
Combining labeled and unlabeled data with co-training
Bagging predictors.
The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing pa- rameter
Learning from Data: Concepts
Comparison of VC- method with classical methods for model selection
Elements of Information Theory.
Smoothing noisy data with spline func- tions
Computers and the theory of statistics: Thinking the unthinkable.
The risk in ation criterion for multiple regression.
A decision-theoretic generalization of on-line learning and an application to boosting
Applications of model selection techniques to polynomial approximation.

A comparison of scienti
A study of cross-validation and bootstrap for accuracy estimation and model selection
Neural network ensembles

Bayesian interpolation.
Some comments on C p
A mixture of experts classi

Generating accurate and diverse members of a neural-network ensemble
Regularization algorithms for learning that are equivalent to multilayer networks.
Pattern Recognition and Neural Networks.
Stochastic complexity and modeling.
Learning from a mixture of labeled and unlabeled examples with parametric side information.
Estimating the dimension of a model.


A new metric-based approach to model selec- tion
An optimal selection of regression variables.
An adaptive regularization criterion for supervised learning.
Characterizing the generalization performance of model selection strategies.
Using unlabeled data for supervised learning.
The Nature of Statistical Learning Theory.
Computer Systems that Learn.
A Bayesian approach to prediction using polynomials.
--TR

--CTR
Yoshua Bengio , Nicolas Chapados, Extensions to metric based model selection, The Journal of Machine Learning Research, 3, 3/1/2003
Antonio Bahamonde , Gustavo F. Bayn , Jorge Dez , Jos Ramn Quevedo , Oscar Luaces , Juan Jos del Coz , Jaime Alonso , Flix Goyache, Feature subset selection for learning preferences: a case study, Proceedings of the twenty-first international conference on Machine learning, p.7, July 04-08, 2004, Banff, Alberta, Canada
unlabeled examples;model selection;regularization