3
$\begingroup$

Citing Bagging Predictors, Section 4 (emphasis mine):

Let each $(y, \mathbf{x})$ case in $\mathcal{L}$ be independently drawn from the distribution $P$. Suppose $y$ is numerical and $\phi(\mathbf{x}, \mathcal{L})$ the predictor. Then the aggregated predictor is

$$ \phi_A(\mathbf{x}, P) = E_{\mathcal{L}} \phi(\mathbf{x}, \mathcal{L}) $$

(......)

Now, the bagged estimate is not $\phi_A(\mathbf{x}, P)$, but rather

$$ \phi_B(\mathbf{x}) = \phi_A(\mathbf{x}, P_{\mathcal{L}}), $$

where $P_{\mathcal{L}}$ is the distribution that concentrates mass $1/N$ at each point $(y_n, \mathbf{x}_n) \in \mathcal{L}$, ($P_{\mathcal{L}}$ is called the bootstrap approximation to $P$). Then $\phi_B$ is caught in two currents: on the on hand, if the procedure is unstable, it can give improvement throught aggregation. On the other side, if the procedure is stable, then $\phi_B = \phi_A(x, P_\mathcal{L})$ will not be as accurate for data drawn from $P$ as $\phi_A(x, P) \simeq \phi(x, \mathcal{L})$.

I didn't get it. As far as I know, $\phi_A(x, P) \simeq \phi(x, \mathcal{L})$ regardless of the stability of procedures, so bootstrapping results in lower quality data (compared to iid sampling) in both cases.

However, a case study in Section 5 of the same paper even suggests bagging stable procedures results in larger prediction error, so I suppose bagging stable classifiers is indeed not a good idea, but why not?

$\endgroup$
0
4
$\begingroup$

Summary: bagging is a bias-variance tradeoff for the model, accepting some bias to reduce variance.

If there's nothing to gain by reducing variance, there can still be losses due to bias compared to training on $\mathcal L$.

We can check whether variance reduction leads to substantial improvements (also in situations where we cannot measure the corresponding bias) and thus restrict the use of aggregation to cases where we see substantial reduction in loss due to model instability.


Let's look at this in two steps:

  1. bootstrapping as resampling and
  2. aggregation.

Aggregation reduces variance. More precisely, the variance in the predictions that is due to the models being unstable wrt. exchanging a few training cases.
If the variance is negligible, aggregation doesn't help overall. But it also doesn't hurt: if all surrogate models yield equal predictions (as they do when stable), the aggregate prediction is always the same as the predicitons of each of the surrogate models. So at this level, the predictive ability is the same whether you aggregate stable surrogate models or not.

Things may be different wrt. to step 1, though. Consider training models $\phi (\mathbf x, \mathcal L)$ on the full dataset at hand $\mathcal L$ vsr. training models $\phi_b (\mathbf x, \mathcal L_B)$ on bootstrap samples of $\mathcal L$ ($\mathcal L_B$).
The bootstrap models $\phi_b$ can on average be worse than the models $\phi$ trained on the full dataset $\mathcal L$, i.e. they may be biased.

I'm not aware of papers that study this bias of the bootstrap models $\phi_b$, but:


Excursion: out-of-bootstrap estimation of generalization error

The same mechanism, namely that (non-aggregated) models $\phi_b (\mathbf x, \mathcal L_B)$ trained on bootstrap subsamples $\mathcal L_B$ are on average worse than models $\phi (\mathbf x, \mathcal L)$ trained on the full learning set $\mathcal L$, is also the source of bias for out-of-bootstrap estimates of generalization error (oob error).

The bias and variance properties of oob erros have been extensively studied (e.g. Kohavi, R.: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection, Mellish, C. S. (ed.) Artificial Intelligence Proceedings 14$^th$ International Joint Conference, 20 -- 25. August 1995, Montréal, Québec, Canada, Morgan Kaufmann, USA, , 1137 - 1145 (1995). is a famous paper on the topic. We also observed substantial bias for oob estimates for classification of spectroscopic data: Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G.: Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005). ).

For generalization error, we can nicely and unambiguously refer to this bias as a pessimistic bias because out-of-bootstrap on average yields too high error compared to the true error of the model trained on the whole data set $\phi (\mathbf x, \mathcal L)$.

This bias for generalization error is actually caused by an unbiased estimate of generalization error of biased predictions by the surrogate models $\phi_b(\mathbf x, \mathcal L_B)$ (which are the very same models that are aggregated in bagging). We may also call the models themselves biased, but how such a model bias looks inside the model depends a lot on what model we are talking about. But this can take the form of the model's internal parameters (e.g. coefficients) being on average off of the parameters corresponding to the true underlying relationship.


Back to bagging:

Intuitively, the underlying reason for the worse (average) performance of $\phi_b (\mathbf x, \mathcal L_B)$ compared to the performance of $\phi (\mathbf x, \mathcal L)$ is that subsampling $\mathcal L \mapsto \mathcal L_B$ looses a bit of information by substituting some data points by copies of other cases. A copy of an already known case usually doesn't add a "full case's worth of information". The consequence of that is that the models trained on $\mathcal L_B$ are on average a bit worse than those trained on $\mathcal L$.

I'd argue this bias is tied to the learning curve of the algorithm/application combination, i.e. to whether adding more (real) data points to $\mathcal L$ leads to substantial improvement of the model (on average/expectation).

So, aggregating helps to stabilize models. But to get the models to aggregate, bootstrap resampling accepts a bias for each single model. Thus,

  • bagging helps iff the stabilization (reduction in performance loss due to model variance) is larger than the loss in performance due to the bias of the models based on bootstrap resampled variants of the whole data set at hand.
  • bagging hurts iff the bias is larger than the reduction in variance for out-of-bag or out-of-bootstrap, the bias will not show here.

The resulting heuristic is to go for bagging only if the out-of-bootstrap predictions are in fact unstable. This is easy to assess: compare the out-of-bag error to the out-of-bootstrap error - the calculations for this are of negligible additional effort.
Out-of-bag and out-of-bootstrap error estimates are subject to exactly the same bias compared to the true performance of $\phi (\mathbf x, \mathcal L)$, though.

That bias will in practice be more difficult to measure: considering that model instability is a concern in small sample size situations, a sufficiently precise estimate of the performance of $\phi (\mathbf x, \mathcal L)$ may not be available.


Note: if in the first place you do cross validation instead of out-of-bootstrap and find model instability, you can also aggregate cross validation surrogate models instead of bagging (and calculate aggregatedd cross validation error in analogy to out-of-bag error).

$\endgroup$
4
  • $\begingroup$ Nice answer, but could you explain why does bootstrapping introduce "pessimistic bias"? Also, are you talking about the bias of estimation of the generalization error, or the bias of the estimation of the parameter in interest? $\endgroup$ – nalzok Jul 1 '19 at 14:25
  • $\begingroup$ @nalzok: Please have a look whether the explanation is clear now. As for what bias: we have 3 biases here that are closely connected. 1. the sub/surrogate models are biased compared to the model trained on the whole data set. (This is maybe a rather vague concept in general, but for particular models can be "nailed down" e.g. to the average of the coefficients of $\phi_b$ not being the coefficients of $\phi$ (nor being the true coefficients that describe the underlying relationship) 2. This bias of the models leads to biased predictions: ... $\endgroup$ – cbeleites unhappy with SX Jul 1 '19 at 15:28
  • $\begingroup$ their predictions (for the same case) are on average different from the predictions of models trained on $\mathcal L$. 3. This directly becomes a bias for generalization error estimation. Biases 1 and 2 are the same for oob error and bagging. In addition, the distinction between 1 and 2 is often kind of handwaving, because for predictive models we often don't care whether coefficients/model internals are stable (1) as long as the predictions (2) are. $\endgroup$ – cbeleites unhappy with SX Jul 1 '19 at 15:28
  • $\begingroup$ Wrt your terminology the parameter of interest may be either the prediction or the innards of the model for the bagging discussion. $\endgroup$ – cbeleites unhappy with SX Jul 1 '19 at 15:29

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.