0
$\begingroup$

Consider the following bootstrapping scheme, common with weak classifiers: 0. Given training data N samples by P predictors

  1. sample the training data with replacement k times (for a large k)
  2. fit unbiased strong classifier, e.g. Bayesian regression (or lasso), to each of the k data frames

Note that in step 1, sampling with replacement, for a large N, results in (e-1/e)*N unique rows.

Now let's think through the interpretation of item 1 in terms of simulated annealing. In the context of likelihood-based methods, score looks like exp((logLik + penalty)/T). for large N, penalty is much smaller than logLik and we can treat it as a second-order effect. We can then re-write the score as exp((sum_1..N(logLik_i)/T). If N is large, then sum_1..N(logLik_i)/T is approximately the same as sum_(subset of 1/T elements from 1..N)(logLik_i). In other words, simulated annealing is approximately a data sub-sampling scheme.

Because the # of unique rows after sampling with replacement is roughly 2/3N, we are roughly training the classifier on that many rows. Increasing the number of non-unique rows is approximately the same as training below T=1 and down to T = 2/3 in our annealing analogy. In other words, for a strong classifier where the features are meaningful and not expected to cancel out, sampling with replacement should lead to significant overtraining.

I have written a fairly clunky and partially proprietary script that I can't share here where I tested this assertion and, indeed, the ensemble of classifiers performs a lot better when training data for each model is reduced to only unique rows.

Questions:

  1. Does this make sense or does this sound crazy?
  2. Has anyone seen this written up? Could I ask for a link?
  3. If this hasn't been written up, what kind of journal would be good? Is Monte Carlo angle acceptable to the statistical audience or is there a better avenue of approach?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You are correct, when using bootstrap, each bootstrap sample would have $0.632N$ unique rows, so there's even the 0.632+ correction that can be used to account for that. Notice however that for a particular bootstrap sample, some particular rows would be repeated, while for other sample, it would be other rows, so in the end if you look at the collection of the results from different samples, they will "cancel out".

Regarding the comment that because of the highly correlated nature of the data, in some bootstrap samples you observe that the model is overfitting, you should ask yourself if in this case it is a "bug or a feature" of bootstrap? Bootstrap is a procedure that helps you learn about uncertainty of your model, given different samples, where the samples are taken from empirical distribution that is assumed to approximate the distribution of the population. Of course, repeated samples are extreme case, but this results seem to show that your model is prone to overfitting for some combinations of the data, hence this likely makes the standard error larger. This effect may be exaggerated by the procedure itself, but it seems to show important fact about limitations of your model.

You may also be interested in reading the What are examples where a "naive bootstrap" fails? thread, as well as other ones tagged as , and the references mentioned in Recommended reading for understanding when the bootstrap will fail?.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's a very nice little write-up, thanks! In my case the issues a different - both my predictors and my outcome are binary, predictors are correlated, and all of them are also imbalanced with small sample counts in the minor class; the bootstraps grossly overfit, as happens due to the combinatorics of that type of problem in small sample sizes - and, as we've discussed, bootstrapping, even with replacement, exacerbates that problem. In my first pass, I had to do two rounds of boosting to just match a single lasso in predictive performance. I wonder if I need to bias my sampling somehow! $\endgroup$
    – rimorob
    Jun 23, 2020 at 13:08
  • $\begingroup$ @rimorob see my edit where I refer to your comment. $\endgroup$
    – Tim ♦
    Jun 23, 2020 at 14:28
  • $\begingroup$ Undoubtedly, overfitting of the individual learners is indicative of the challenge of learning from imbalanced, correlated, low-n data. But I knew this a priori. The out-of-sample performance of an un-boosted learner, however, dramatically trails that of a single regression classifier. Further, even fairly large ensembles (I went 50->300) fail to "cancel out the errors" as I hoped they might. Going back to my monte carlo analogy, if we only had 1 unique sample per learner (T= # of rows), no learning would occur no matter ensemble size. Food for thought.... $\endgroup$
    – rimorob
    Jun 23, 2020 at 21:30
  • $\begingroup$ @rimorob bootstrap does not solve all problems and does not work for all cases, very small samples is one example where it fails. Bootstrap is for estimating things like standard errors and confidence intervals, in your case one of the problems with the model seems to be that it is prone to overfitting, hence this would make the intervals wider. Without knowing more about your data it is hard to comment on the exact nature of the problem. $\endgroup$
    – Tim ♦
    Jun 23, 2020 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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