6
$\begingroup$

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?
$\endgroup$
7
$\begingroup$

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:

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

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, since they are trained over bootstrap samples obtained from the same base dataset, but 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.

$\endgroup$
  • $\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$ – OmegaD Feb 10 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 at 16:31
  • $\begingroup$ Fantastic! Thank you so much! $\endgroup$ – OmegaD Feb 10 at 16:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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