Reading about deep leaning, I came across the following formula.

$$ \mbox{var} \left( \frac{1}{n} \sum_{i=1}^{n} X_i \right) = \rho \sigma^2 + \frac{1-\rho}{n} \sigma^2 $$

where $X_1, \dots, X_n$ are identically distributed random variables with pairwise correlation $\rho > 0$ and variance $\mbox{var}(X_i) = \sigma^2$.

  1. How to derive this?
  2. How does bootstrap aggregating alleviate the effect of overfitting, according to this formula? What is the relationsip?

By definition, we have

$$\operatorname{var}\left(\sum_{i=1}^n{X_i}\right)=\operatorname{cov}\left(\sum_{i=1}^n{X_i},\sum_{i=1}^n{X_i}\right)=\sum_{i=1}^n{\operatorname{var}(X_i)}+\sum_{i\neq j}\operatorname{cov}(X_i,X_j)$$

which is $n \operatorname{var}(X_i)+n(n-1)\operatorname{cov}(X_i,X_j)=n\sigma^2+n(n-1)\rho\sigma^2$, where $i\neq j$. Substituting this into the original equation yields the following:


Each $X_i$ can be thought of as a single decision mechanism, call it DM, (e.g. regressor). The variance of your decision was $\sigma^2$. By using bootstrap samples and aggregating your DMs' outputs, you end up with a decision variance as above, which is strictly smaller than $\sigma^2$ when $\rho \neq 1$ and $n\neq 1$. DMs will have some degree of correlation of course, because they are trained over bootstrap samples obtained from the same base dataset; however, the correlation between them most probably won't be equal to $1$. Overfitted mechanisms in general have large variance, so by aiming to decrease the variance of your DM, you actually address the problem of overfitting implicitly.

  • $\begingroup$ Fantastic! Thank you for so much for your answer. Quick question, in the term $n var(X_i) + n(n-1) cov(X_i,X_j)$ n and n-1 come from. Sorry if it is too obvious question. $\endgroup$ – Daksitha Withanage Feb 10 '19 at 16:15
  • 1
    $\begingroup$ @OmegaD There are $n^2$ pairs of $i,j$, where $n$ of them have $i=j$, and $n^2-n=n(n-1)$ of them have $i\neq j$. $\endgroup$ – gunes Feb 10 '19 at 16:31
  • $\begingroup$ @gunes This is a great answer, Can you please answer my question also. $\endgroup$ – Md. Sabbir Ahmed Apr 8 '20 at 14:23
  • $\begingroup$ I know that $\rho\geq -1/(B-1)$ but that does not imply that $\rho>0$ which is stated in the book? Say we have $B=3$ we have that $\rho$ can take the values $-0.5$ without violating anything. How come the proof is only for $\rho\geq 0$? $\endgroup$ – CutePoison Apr 14 '20 at 13:38
  • $\begingroup$ @CutePoison it is assumed $\rho>0$ in the OP and my proof is based on this assumption. I'm not aware in which book it is, so if you can share the link, I can at least read and comment on it. $\endgroup$ – gunes Apr 14 '20 at 14: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.