Here is a derivation from the free "Learning From Data" course, lecture 13 on validation. Here is a link to it.

Now, I'm stuck figuring out how he developed the third lane, the one about the variance. I tried to develop it myself and got stuck.

Here is what I've been trying:

$E_{val}(h) = \dfrac{1}{k}(\Sigma(e(h(x_k),y)))$

this is just the definition of the error that the professor gave, and I understand it. It's on the end of the first line.


$var[E_val] = var[\dfrac{1}{k}(\Sigma(e(h(x_k),y)))]$

by the definition of variance:

$var[\dfrac{1}{k}(\Sigma(e(h(x_k),y)))] = E[(\dfrac{1}{k}(\Sigma(e(h(x_k),y))) - E[\dfrac{1}{k}(\Sigma(e(h(x_k),y)))])^2]$

after some playing with the algebra I came to this:


As you can see, this is nothing like what he got. Will anyone explain this to me?

  • $\begingroup$ Did the professor state a priori that the random variables $(x_k, y_k)$ are independent of each other? $\endgroup$ – Hans Nov 29 '17 at 20:06

The property used here is the formula for the variance of a linear combination of random variables, which you can see here for example: https://en.wikipedia.org/wiki/Variance#Basic_properties

$Var\left( \sum_ia_iX_i \right) = \sum_ia_i^2Var(X_i) + \sum_{i \neq j}a_ia_jCov(X_i,X_j)$

The statement on the slide requires that the points in the validation set are drawn independently, which ensures that the covariance terms in that formula are 0. He mentions this just before the timestamp you linked to.

In case it's unclear, the $a_i$ above are all equal to $1/K$ in your case. The random variable $X_i$ is $e(h(x_i),y)$.

  • 1
    $\begingroup$ Thank You. I have not been aware of this formula. $\endgroup$ – Moran Reznik Nov 29 '17 at 20:21

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.