21
$\begingroup$

My understanding is that even when following proper cross validation and model selection procedures, overfitting will happen if one searches for a model hard enough, unless one imposes restrictions on model complexity, period. Moreover, often times people try to learn penalties on model complexity from the data which undermines the protection they can provide.

My question is: How much truth is there to the statement above?

I often hear ML practicioners say: "At my company/lab, we always try every model available (e.g. from libraries like caret or scikit-learn) to see which one works best". I often argue that this approach can easily overfit even if they are serious about cross-validation and keep hold-out sets in any way they want. Moreover the harder they search, the more likely they may overfit. In other words, over-optimization is a real problem and there are no heuristics that can help you systematically fight against it. Am I wrong to think this way?

$\endgroup$
  • $\begingroup$ Are you asking about ML specifically or multivariate models in general? $\endgroup$ – rumtscho Jun 19 '16 at 13:36
  • $\begingroup$ @rumtscho everything in ML. $\endgroup$ – Amelio Vazquez-Reina Jun 19 '16 at 17:53
  • 1
    $\begingroup$ Thanks @CagdasOzgenc: "the larger the search space (the models considered), the poorer the result". Not sure what level of abstraction "search space" you are referring here to, but by "trying hard enough" I of course mean searching through more and more models, and thus increasing the complexity/search-space of the "meta-model" (if you wish) that we are trying to fit. $\endgroup$ – Amelio Vazquez-Reina Jun 19 '16 at 19:54
8
$\begingroup$

Not a whole answer, but one thing that people overlook in this discussion is what does Cross-Validation (for example) mean, why do you use it, and what does it cover?

The problem I see with searching too hard is that the CV that people are doing is often within a single model. Easy to do by setting a folds= argument of the model fitting procedure. But when you go to multiple models, and even multiple procedures for creating multiple models, you add another layer or two which you haven't wrapped in CV.

So they should be using nested CV. And they should also be using "Target Shuffling" (resampling/permutation testing) wrapped around their whole process to see how well their procedure would do if you break the relationship between dependent and independent variables -- i.e. how much better are you doing than random considering your entire process?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1. Doing model selection with single (or too few) layers of CV that run a grid search (model selection) can definitely lead to overfitting (for anyone interested, I recommend e.g. this and the sources therein). I had read about "Target Shuffling" (for other readers, I recommend this exposition), but never used it myself; I wonder if it can also be abused, (e.g. doing multiple tests leading to false positives eventually, and thus again searching "hard enough" (?)). $\endgroup$ – Amelio Vazquez-Reina Jun 20 '16 at 2:03
8
$\begingroup$

In my 4 or so years of experience, I've found that trying out every model available in caret (or scikit-learn) doesn't necessarily lead to overfitting. I've found that if you have a sufficiently large dataset (10,000+ rows) and a more or less even balance of classes (i.e., no class imbalance like in credit risk or marketing problems), then overfitting tends to be minimal. It's worth noting that my grid search on tuning parameters tends to be no more than 30 permutations per model. At the extreme end, if you used 100 or 1,000 permutations per model, you would probably overfit.

The way you've worded your question makes the answer pretty easy: at the extreme, yes, overfitting is likely if not certain. There is no silver bullet, and I doubt anyone would suggest otherwise. However, there is still a reasonably wide spectrum where the degree of overfitting is minimal enough to be acceptable. Having a healthy amount of unseen data in your validation holdout set definitely helps. Having multiple unseen validation holdout sets is even better. I'm fortunate enough to work in a field where I have large amounts of new data coming on a daily basis.

If I'm in a position where I'm stuck with a static dataset of fewer than 2,000-3,000 observations (ex: medical data that's hard to come by), I generally only use linear models because I've frequently seen overfitting with gradient boosting and support vector machines on sufficiently small datasets. On the other hand, I've talked to a top Kaggler (top 5%) that said he builds tens of thousands of models for each competition and then ensembles them, using several thousand models in his final ensemble. He said this was the main reason for his success on the final leaderboards.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yep. I have worked with data that had observations in the millions. No matter what validation I tried (kfold, bootstrapping and even simple holdout), there was little variation in the models. As your data increases, the less care you need to take on how you validate. $\endgroup$ – Ricardo Cruz Jun 22 '16 at 9:38
  • $\begingroup$ In other words, no model has enough degrees of freedom to "memorize" millions of observations. $\endgroup$ – Ricardo Cruz Jun 22 '16 at 9:47
5
$\begingroup$

So much depends on scale. I wish I could count on having more than 2,000-3,000 cases like @RyanZotti typically has; I seldom have 1/10th that many. That's a big difference in perspective between "big data" machine learning folk and those working in fields like biomedicine, which might account for some of the different perspectives you will find on this site.

I'll present a heuristic explanation of my take on this problem. The basic issue in overfitting, as described on the Wikipedia page, is the relation between the number of cases and the number of parameters you are evaluating. So start with the rough idea that if you have M models you are choosing among and p parameters per model then you are evaluating something on the order of Mp parameters in total.

If there is danger of overfitting there are two general ways to pull back to a more generalizable model: reduce the number of parameters or penalize them in some way.

With adequately large data sets you might never come close to overfitting. If you have 20,000 cases and 20 different models with 100 parameters per model, then you might not be in trouble even without penalization as you still have 10 cases per effective parameter. Don't try that modeling strategy with only 200 cases.

Model averaging might be thought of as a form of penalization. In the example of the Kaggler cited by @RyanZotti, the number of cases is presumably enormous and each of the "several thousand" models in the final ensemble individually contributes only a small fraction of the final model. Any overfitting specific to a particular contributing model will not have a great influence on the final result, and the extremely large numbers of cases in a Kaggler competition further reduces the danger of overfitting.

So, as with so many issues here, the only reasonable answer is: "It depends." In this case, it depends on the relation between the number of cases and the effective number of parameters examined, together with how much penalization is being applied.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I agree with @ryan-zotti that searching hard enough does not necessarily lead to overfitting - or at least not to an amount so that we would call it overfitting. Let me try to state my point of view on this:

Box once said:

Remember that all models are wrong; the practical question is how wrong do they have to be to not be useful.

(Being perfect would require all the data, which in turn would eliminate the need for a model in the first place).

Models being wrong also comprises over- and underfitting$^1$. But we won't necessarily care about or even notice it. The question is which amount of the model deviating from reality can we a) measure at all and b) find acceptable to not call it over- or underfitting - because both will always apply a little to all model we will ever build. If our models in the end satisfy our requirements but e.g. over-/underfit just minimal, or over-/underfit on parts of (possible) data that is not considered in our application case we would accept it - it's not necessarily about preventing all over-/underfitting.

This boils down to a proper setup to measure/detect model error to decide if this is what we would want to have. So what we can do is make the process as robust as possible by trying to get data with minimal noise and representative+sufficient samples, to model, evaluate and select as best as possible, and to do all this in a reasonable way (e.g. few samples, many features $\rightarrow$ less complex model; select the least complex model with yet acceptable performance, etc.).

Because: in the end we will always have model error/over-/underfitting - it's the capability of detecting/measuring this error within our focus of interest to make reasonable choices that matters.


$^1$ a) each model has a bias and variance problem at the same time (we usually try to find the right trade-off to satisfy our needs). Models satisfying our requirements will necessarily still have bias and variance. b) Consider noisy data and non representative samples as reasons for overfitting. Each model will necessarily model noise as well as model a relation for which parts of the information is missing, so about which wrong assumptions will necessarily be made.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I think this is a very good question. I always want to observe the "U" shape curve in cross validation experiments with real data. However, my experience with real world data (~ 5 years in credit card transactions and education data) does not tell me over fitting can easily happen in huge amount (billion rows) real world data.

I often observe that you can try you best over fit the training set, but you cannot do too much (e.g., reduce the loss to 0), because the training set is really large and contains a lot of information and noise.

At the same time, you can try the most complicated model (without any regularization) on testing data, and it seems fine and even better than some with regularization.

Finally, I think my statements might be true only under the condition of you have billions data points in training. Intuitively, the data is much complex than you model so you will not over fit. For billion rows of data, even you are using a model with thousands of parameters, it is fine. At the same time you cannot afford the computation for building a model with million free parameters.

In my opinion this is also why neural network and deep learning got popular these days. Comparing to billions of images in Internet, any model you can afford training is not enough to over fit.

| cite | improve this answer | |
$\endgroup$

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.