60
$\begingroup$

Suppose we have someone building a predictive model, but that someone is not necessarily well-versed in proper statistical or machine learning principles. Maybe we are helping that person as they are learning, or maybe that person is using some sort of software package that requires minimal knowledge to use.

Now this person might very well recognize that the real test comes from accuracy (or whatever other metric) on out-of-sample data. However, my concern is that there are a lot of subtleties there to worry about. In the simple case, they build their model and evaluate it on training data and evaluate it on held-out testing data. Unfortunately it can sometimes be all too easy at that point to go back and tweak some modeling parameter and check the results on that same "testing" data. At this point that data is no longer true out-of-sample data though, and overfitting can become a problem.

One potential way to resolve this problem would be to suggest creating many out-of-sample datasets such that each testing dataset can be discarded after use and not reused at all. This requires a lot of data management though, especially that the splitting must be done before the analysis (so you would need to know how many splits beforehand).

Perhaps a more conventional approach is k-fold cross validation. However, in some sense that loses the distinction between a "training" and "testing" dataset that I think can be useful, especially to those still learning. Also I'm not convinced this makes sense for all types of predictive models.

Is there some way that I've overlooked to help overcome the problem of overfitting and testing leakage while still remaining somewhat clear to an inexperienced user?

$\endgroup$
  • $\begingroup$ Michael, I closed a duplicate thread from the ML site and merged the answers here. Please feel free to edit this question to reflect any changes you wanted to make--I don't want to undertake that for fear of inadvertently changing your meaning. $\endgroup$ – whuber Feb 22 '12 at 21:19
  • $\begingroup$ This question is old and has an accepted answer, but I can't get out of my head that the initial premise seems to be conflicted. If this is about learning exercises, then the best way to approach it is to let them fail and make an overfit model that subsequently doesn't predict well. (Perhaps keep a secret holdout dataset that you show them the error of their ways.) But it also sounds like you've got unqualified people making models that someone is going to take seriously and act upon and you're trying to minimize the damage at arms length. There are a LOT of subtleties, as you say. $\endgroup$ – Wayne Feb 7 '16 at 15:35
50
$\begingroup$

You are right, this is a significant problem in machine learning/statistical modelling. Essentially the only way to really solve this problem is to retain an independent test set and keep it held out until the study is complete and use it for final validation.

However, inevitably people will look at the results on the test set and then change their model accordingly; however this won't necessarily result in an improvement in generalisation performance as the difference in performance of different models may be largely due to the particular sample of test data that we have. In this case, in making a choice we are effectively over-fitting the test error.

The way to limit this is to make the variance of the test error as small as possible (i.e. the variability in test error we would see if we used different samples of data as the test set, drawn from the same underlying distribution). This is most easily achieved using a large test set if that is possible, or e.g. bootstrapping or cross-validation if there isn't much data available.

I have found that this sort of over-fitting in model selection is a lot more troublesome than is generally appreciated, especially with regard to performance estimation, see

G. C. Cawley and N. L. C. Talbot, Over-fitting in model selection and subsequent selection bias in performance evaluation, Journal of Machine Learning Research, 2010. Research, vol. 11, pp. 2079-2107, July 2010 (www)

This sort of problem especially affects the use of benchmark datasets, which have been used in many studies, and each new study is implicitly affected by the results of earlier studies, so the observed performance is likely to be an over-optimistic estimate of the true performance of the method. The way I try to get around this is to look at many datasets (so the method isn't tuned to one specific dataset) and also use multiple random test/training splits for performance estimation (to reduce the variance of the estimate). However the results still need the caveat that these benchmarks have been over-fit.

Another example where this does occur is in machine learning competitions with a leader-board based on a validation set. Inevitably some competitors keep tinkering with their model to get further up the leader board, but then end up towards the bottom of the final rankings. The reason for this is that their multiple choices have over-fitted the validation set (effectively learning the random variations in the small validation set).

If you can't keep a statistically pure test set, then I'm afraid the two best options are (i) collect some new data to make a new statistically pure test set or (ii) make the caveat that the new model was based on a choice made after observing the test set error, so the performance estimate is likely to have an optimistic bias.

$\endgroup$
  • 1
    $\begingroup$ +1 I am impressed by how well this answer is informed by experience and how effectively it addresses the question. $\endgroup$ – whuber Dec 20 '11 at 11:50
  • 3
    $\begingroup$ cheers whuber, this has been my main research topic for a couple of years, and I have found that many model selection procedures widely used in machine learning are very fragile, and the more thoroughly they are evaluated, the less well they seem to work. It wouldn't surprise me that many methods used in machine learning don't work any better than older more simple methods, simply because of biased model selection procedures used during performance evaluation. The question is a really good one, it is important not to become part of the model selection procedure yourself by tinkering! $\endgroup$ – Dikran Marsupial Dec 20 '11 at 12:24
  • $\begingroup$ Very interesting. (I have also upvoted the question itself because your reply made me appreciate it better.) $\endgroup$ – whuber Dec 20 '11 at 14:15
  • 2
    $\begingroup$ (+1) Nice response. The use of several classifiers on the same dataset that yields to over-optimistic measure of test accuracy have been discussed in Optimal classifier selection and negative bias in error rate estimation: an empirical study on high-dimensional prediction, BMC MRM 2009, 9:85 (with some PDF slides here), with other discussion in Multiple-rule bias in the comparison of classification rules (Yousefi et al., Bioinformatics 2011, 27(12):1675). $\endgroup$ – chl Dec 20 '11 at 22:09
  • $\begingroup$ Thanks for the links to the papers, they look interesting. $\endgroup$ – Dikran Marsupial Dec 21 '11 at 12:34
15
$\begingroup$

One way to ensure this is to make sure you have coded up all of the things you do to fit the model, even "tinkering". This way, when you run the process repeatedly, say via cross-validation, you are keeping things consistent between runs. This ensures that all of the potential sources of variation are captured by the cross-validation process.

The other vitally important thing is to ensure that you have a representative sample, in both data sets. If your data set is not representative of the kind of data you expect to be using to predict, then there is not much that you can do. All modelling rests on an assumption that "induction" works - the things we haven't observed behave like the things we have observed.

As a general rule, stay away from complex model fitting procedures unless (i) you know what you are doing, and (ii) you have tried the simpler methods, and found that they don't work, and how the complex method fixes the problems with the simple method. "Simple" and "complex" are meant in the sense of "simple" or "complex" to the person doing the fitting. The reason this is so important is that it allows you to apply what I like to call a "sniff test" to the results. Does the result look right? You can't "smell" the results from a procedure that you don't understand.

NOTE: the next, rather long part of my answer is based on my experience, which is in the $N>>p$ area, with $p$ possibly large. I am almost certain that what follows below would not apply to the $N\approx p$ or $N<p$ cases

When you have a large sample, the difference between using and not using a given observation is very small, provided your modelling is not too "local". This is because the influence of a given data point is generally the order of $\frac{1}{N}$. So in large data sets, the residuals you get from "holding out" the test data set are basically the same as the residuals you get from using it in the training data set. You can show this using ordinary least squares. The residual you get from excluding the $i$th observation (i.e. what the test set error would be if we put the observation in the test set) is $e_i^{test}=(1-h_{ii})^{-1}e_i^\mathrm{train}$, where $e_i^\mathrm{train}$ is the training residual, and $h_{ii}$ is the leverage of the $i$th data point. Now we have that $\sum_ih_{ii}=p$, where $p$ is the number of variables in the regression. Now if $N>>p$, then it is extremely difficult for any $h_{ii}$ to be large enough to make an appreciable difference between the test set and training set errors. We can take a simplified example, suppose $p=2$ (intercept and $1$ variable), $N\times p$ design matrix is $X$ (both training and testing sets), and the leverage is

$$h_{ii}=x_i^T(X^TX)^{-1}x_i=\frac{1}{Ns_x^2} \begin{pmatrix}1 & x_i \end{pmatrix} \begin{pmatrix}\overline{x^2} & -\overline{x}\\ -\overline{x} & 1\end{pmatrix} \begin{pmatrix}1 \\ x_i\end{pmatrix} =\frac{1+\tilde{x}_i^2}{N}$$

Where $\overline{x}=N^{-1}\sum_ix_i$, $\overline{x^2}=N^{-1}\sum_ix_i^2$, and $s_x^2=\overline{x^2}-\overline{x}^2$. Finally, $\tilde{x}_i=\frac{x_i-\overline{x}}{s_x}$ is the standardised predictor variable, and measures how many standard deviations $x_i$ is from the mean. So, we know from the beginning that the test set error will be much larger than the training set error for observations "at the edge" of the training set. But this is basically that representative issue again - observations "at the edge" are less representative than observations "in the middle". Additionally, this is to order $\frac{1}{N}$. So if you have $100$ observations, even if $\tilde{x}_i=5$ (an outlier in x-space by most definitions), this means $h_{ii}=\frac{26}{100}$, and the test error is understated by a factor of just $1-\frac{26}{100}=\frac{74}{100}$. If you have a large data set, say $10000$, it is even smaller,$1-\frac{26}{10000}$, which is less than $1\text{%}$. In fact, for $10000$ observations, you would require an observation of $\tilde{x}=50$ in order to make a $25\text{%}$ under-estimate of the test set error, using the training set error.

So for big data sets, using a test set is not only inefficient, it is also unnecessary, so long as $N>>p$. This applies for OLS and also approximately applies for GLMs (details are different for GLM, but the general conclusion is the same). In more than $2$ dimensions, the "outliers" are defined by the observations with large "principal component" scores. This can be shown by writing $h_{ii}=x_i^TEE^T(X^TX)^{-1}EE^Tx_i$ Where $E$ is the (orthogonal) eigenvector matrix for $X^TX$, with eigenvalue matrix $\Lambda$. We get $h_{ii}=z_i^T\Lambda^{-1}z_i=\sum_{j=1}^p\frac{z_{ji}^2}{\Lambda_{jj}}$ where $z_i=E^Tx_i$ is the principal component scores for $x_i$.

If your test set has $k$ observations, you get a matrix version ${\bf{e}}_{\{k\}}^\mathrm{test}=(I_k-H_{\{k\}})^{-1}{\bf{e}}_{\{k\}}^\mathrm{train}$, where $H_{\{k\}}=X_{\{k\}}(X^TX)^{-1}X_{\{k\}}^T$ and $X_{\{k\}}$ is the rows of the design matrix in the test set. So, for OLS regression, you already know what the "test set" errors would have been for all possible splits of the data into training and testing sets. In this case ($N>>p$), there is no need to split the data at all. You can report "best case" and "worst case" test set errors of almost any size without actually having to split the data. This can save a lot of PC time and resources.

Basically, this all reduces to using a penalty term, to account for the difference between training and testing errors, such as BIC or AIC. This effectively achieves the same result as what using a test set does, however you aren't forced to throw away potentially useful information. With the BIC, you are approximating the evidence for the model, which looks mathematically like:

$$p(D|M_iI)=p(y_1y_2\dots y_N|M_iI)$$

Note that in this procedure, we cannot estimate any internal parameters - each model $M_i$ must be fully specified or have its internal parameters integrated out. However, we can make this look like cross validation (using a specific loss function) by repeatedly using the product rule, and then taking the log of the result:

$$p(D|M_iI)=p(y_1|M_iI)p(y_2\dots y_N|y_1M_iI)$$ $$=p(y_1|M_iI)p(y_2|y_1M_iI)p(y_3\dots y_N|y_1y_2M_iI)$$ $$=\dots=\prod_{i=1}^{N}p(y_i|y_1\dots y_{i-1}M_iI)$$ $$\implies\log\left[p(D|M_iI)\right]=\sum_{i=1}^{N}\log\left[p(y_i|y_1\dots y_{i-1}M_iI)\right]$$

This suggests a form of cross validation, but where the training set is constantly being updated, one observation at a time from the test set - similar to the Kalman Filter. We predict the next observation from the test set using the current training set, measure the deviation from the observed value using the conditional log-likelihood, and then update the training set to include the new observation. But note that this procedure fully digests all of the available data, while at the same time making sure that every observation is tested as an "out-of-sample" case. It is also invariant, in that it does not matter what you call "observation 1" or "observation 10"; the result is the same (calculations may be easier for some permutations than others). The loss function is also "adaptive" in that if we define $L_i=\log\left[p(y_i|y_1\dots y_{i-1}M_iI)\right]$, then the sharpness of $L_i$ depends on $i$, because the loss function is constantly being updated with new data.

I would suggest that assessing predictive models this way would work quite well.

$\endgroup$
  • 4
    $\begingroup$ +1 - good advice and interesting discussion of leverage (for large datasets). I tend to use datasets that are small, where over-fitting is likely, and in such situations it is often very easy to over-fit the marginal likelihood ("evidence"), and end up with a worse model than you start with. I suspect AIC and BIC are similarly "brittle". Essentially optimisation is the root of all evil in statistics, as any choice you make or parameter you tune based on a finite sample introduces the possibility of over-fitting. Marginalising is much safer, but generally computationally expensive. $\endgroup$ – Dikran Marsupial Dec 20 '11 at 16:58
  • 2
    $\begingroup$ +1 - especially on the third paragraph (use simple methods first). Reminds of the good ol' Pareto-Rule. If machine learners would keep that in mind before they publish their insufficient attempt to prove the superiority of their new bred algorithm ... $\endgroup$ – steffen Dec 21 '11 at 8:02
8
$\begingroup$

I suppose the only way to guarantee this is that someone else has the test data. In a client-consultant relationship this can be managed fairly easily: the client gives the consultant the training set upon which to build the models, and within this training set the consultant can split the data in whatever way necessary to ensure that overfitting doesn't occur; subsequently the models are given back to the client to use on their test data.

For an individual researcher, it stands to reason that best practice would therefore be to mimic this setup. This would mean hiving off some of the data to test, after all model selection has been performed. Unfortunately, as you say, this is not practised by many people, and it even happens to people who should know better!

However ultimately it depends on what the model is being used for. If you're only ever interested in prediction on that single dataset, then maybe you can overfit all you like? However if you are trying to promote your model as one that generalises well, or use the model in some real world application, then of course this of great significance.

There is a side issue which I thought I should mention, which is that even if you follow all the procedures correctly, you can still end up with models that are overfitted, due to the data not being truly i.i.d.. For example, if there are temporal correlations in the data, then if you take all of your training data from times 1-3, and test on time 4, then you may find that the prediction error is larger than expected. Alternatively there could be experiment-specific artefacts, such as the measurement device being used, or the pool of subjects in human experiments, that cause the generalisation of the models to be worse than expected.

$\endgroup$
  • $\begingroup$ Yes, I'm aware that it is surprisingly difficult to create a truly out-of-sample dataset as it is easy to accidentally end up with temporal correlations and what not. $\endgroup$ – Michael McGowan Feb 15 '12 at 17:22
  • 1
    $\begingroup$ Some companies do this as policy, implemented e.g. by having database view permissions set accordingly where some teams are test-data-privy and others are test-data-blind. $\endgroup$ – ijoseph Oct 9 '18 at 23:49
6
$\begingroup$

This is a very good question and a very subtle problem. Of course there are the bad intentioned mistakes, which derive from someone trying to deceive you. But there is a deeper question of how to avoid accidental leaking and avoid honest mistakes.

Let me list some operational good practices. They all stem from honest mistakes I've made at some point:

  • Separate your data into three groups: train, validate and test.
  • Understand the problem setup to be able to argue what is reasonable and what isn't. Understand the problem, many times subtle misunderstanding in what the data represents can lead to leaks. For example while no one would train and test on the same frame of one video, it is more subtle when two frames of the same video fall in different folds, two frames of the same video probably share the same individuals the same lighting and so on.
  • Be extremely careful with previously written cross validation procedures. More so with ones not written by you (LIBSVM is a big offender here).
  • Repeat every experiment at least twice before reporting anything, even if reporting to your office mate. Version control is your friend, before running an experiment commit and write down what version of the code you're running.
  • Be very careful when normalizing your data. Many times this leads to thinking you will have the full dataset on which you want to test at the same time, which again is often not realistic.
$\endgroup$
  • $\begingroup$ There was a question about training/evaluation sets and I gave a theoretical overview on that at machinelearning.stackexchange.com/a/196/114 - explaining stratified holdout, k-fold cross validation and repeated experiments. To my uneducated mind, those methods completely address the above question, and the rest is just "teacher's problem". Also, all the practices in your list seem to fix the "simply sloppy, unacceptable mistakes" and I don't see any subtleties there. I'm very keen to understand what am I missing - can you comment? $\endgroup$ – andreister Feb 16 '12 at 6:24
  • $\begingroup$ I agree that they all come from sloppiness. I had also mentioned that they are not theoretical at all (having said that they're operational). I've edited my post a little bit. $\endgroup$ – carlosdc Feb 16 '12 at 16:22
5
$\begingroup$

Many important points have been covered in the excellent answers that are already given.

Lately, I've developed this personal check list for statistical independence of test data:

  • Split data at highest level of data hierarchy (e.g. patient-wise splitting)
  • Split also independently for known or suspected confounders, such as day-to-day variation in instruments etc.
  • (DoE should take care of random sequence of measurements**)
  • All calculation steps beginning with the first (usually pre-processing) step that involves more than one patient* need to be redone for each surrogate model in resampling validation. For hold-out / independent test set valdiation, test patients need to be separated before this step.
    • This is regardless whether the calculation is called preprocessing or is considered part of the actual model.
    • Typical culprits: mean centering, variance scaling (usually only mild influence), dimensionality reduction such as PCA or PLS (can cause heavy bias, e.g. underestimate no of errors by an order of magnitude)
  • Any kind of data-driven optimization or model selection needs another (outer) testing to independently validate the final model.
  • There are some types of generalization performance that can only be measured by particular independent test sets, e.g. how predictive performance deteriorates for cases measured in future (I'm not dealing with time series forecasting, just with instrument drift). But this needs a properly designed validation study.
  • There's another peculiar type of data leak in my field: we do spatially resolved spectroscopy of biological tissues. The reference labelling of the test spectra needs to be blinded against the spectroscopic information, even if it is tempting to use a cluster analysis and then just find out which class each cluster belongs to (that would be semi-supervised test data which isn't independent at all).

  • Last but certainly not least: When coding resampling validation, I actually check whether the calculated indices into the data set to not lead to grabbing test rows from training patients, days etc.

Note that the "splitting not done in order to ensure independence" and "split before any calculation occurs that involves more than one case" can also happen with testing that claims to use an independent test set, and the latter even if the data analyst is blinded to the reference of the test cases. These mistakes cannot happen if the test data is withheld until the final model is presented.

* I'm using patients as the topmost hierarchy in data just for the ease of description.
** I'm analytical chemist: Instrument drift is a known problem. In fact, part of the validation of chemical analysis methods is determining how often calibrations need to be checked against validation samples, and how often the calibration needs to be redone.


FWIW: In practice, I deal with applications where

  • $p$ is in the order of magnitude of $10^2 - 10^3$,
  • $n_{rows}$ is usually larger than $p$, but
  • $n_{biol. replicates}$ or $n_{patients}$ is $\ll p$ (order of magnitude: $10^0 - 10^1$, rarely $10^2$)
  • depending on the spectroscopic measurement method, all rows of one, say, patient may be very similar or rather dissimilar because different types of spectra have signal-to-noise ratio (instrument error) also varying by an order of magnitude or so

Personally, I've yet to meet the application where for classifier development I get enough independent cases to allow setting aside a proper independent test set. Thus, I've come to the conclusion that properly done resampling validation is the better alternative while the method is still under development. Proper validation studies will need to be done eventually, but it is a huge waste of resources (or results will carry no useful information because of variance) doing that while the method development is in a stage where things still change.

$\endgroup$
2
$\begingroup$

If I remember correctly, some of the forecasting contests (such as Netflix or the ones on Kaggle) use this scheme:

There is a training set, with the "answers". There is test set #1, for which the researcher provides answers. The researcher finds out their score. There is test set #2, for which the researcher provides answers, BUT the researcher does not find out their score. The researcher doesn't know which prediction cases are in #1 and #2.

At some point, set #2 has to become visible, but you've at least limited the contamination.

$\endgroup$
2
$\begingroup$

In some cases, such as Biological sequence-based predictors, it is not enough to ensure that cases do not appear in more than one set. You still need to worry about dependency between the sets.

For example, for sequence-based predictors, one needs to remove redundancy by ensuring that sequences in different sets (including the different cross-validation sets) do not share a high level of sequence similarity.

$\endgroup$
2
$\begingroup$

I'd say "k-fold cross validation" is the right answer from the theoretical point of view, but your question seems more about organizational and teaching stuff so I'll answer differently.


When people are "still learning" it's often thought as if they're learning how to "quickly and dirtily" apply the algorithms and all the "extra" knowledge (problem motivation, dataset preparation, validation, error analysis, practical gotchas and so on) will be learned "later" when they're "more prepared".

This is utterly wrong.

  1. If we want a student or whoever to understand the difference between a test set and a training set, the worst thing will be to give the two sets to two different guys as if we think that "at this stage" the "extra knowledge" is harmful. This is like waterfall approach in software development - few months of pure design, then few month of pure coding, then few months of pure testing and a pity throwaway result in the end.

  2. Learning should not go as waterfall. All parts of learning - problem motivation, algorithm, practical gotchas, result evaluation - must come together, in small steps. (Like agile approach in software development).

Perhaps everyone here has gone through Andrew Ng's ml-class.org - I'd put his course as an example of a robust "agile", if you will, style of learning - the one which would never yield a question of "how to ensure that test data doesn't leak into training data".


Note that I may have completely misunderstood your question, so apologies! :)

$\endgroup$
  • $\begingroup$ Learning for the human being (that is, learning how to model in general) should not go as waterfall, but the learning for the model should. Otherwise bits of the test data will sneak into the training data, and your model is more prone to overfitting. $\endgroup$ – Michael McGowan Feb 15 '12 at 17:57
  • $\begingroup$ And I was thinking of it more from the software end. A user builds a model that gets 90% accuracy on training and 75% accuracy on testing. They then tweak some knobs and settings in the software and get 80% accuracy on "testing." They go back again and do more tweaks and get 85% accuracy on "testing." But this so-called "testing" dataset is no longer out-of-sample, and the model has been overfit to it. $\endgroup$ – Michael McGowan Feb 15 '12 at 17:59
  • $\begingroup$ Exactly. This is a human learning problem (teacher problem, if you will). It should be revealed as soon as possible, rather than hidden by artificial means of "ensuring X doesn't leak into Y" $\endgroup$ – andreister Feb 15 '12 at 18:04
  • $\begingroup$ People that should know better will still make this mistake. You can mitigate this effect to some degree in a software package with a workflow that implicitly or explicitly encourages good practices and discourages bad practices. That the human should know better is no reason to ignore the problem. $\endgroup$ – Michael McGowan Feb 15 '12 at 18:10
  • $\begingroup$ @MichaelMcGowan - you are also ignoring the benefits of leaking - that your algorithm has potentially been improved by using the test set (i.e. train + test is more data than train only). It is really just a different trade-off, improved accuracy vs improved measurement of accuracy. For mine the former is more important. $\endgroup$ – probabilityislogic Feb 1 '16 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.