I have a question on how one would theoretically compute the out of sample error of a given hypothesis in a data learning problem. I've been working through Learning From Data: A Short Course (http://amlbook.com), and in the introductory chapter, the out of sample error of a hypothesis $h:\mathcal{X} \rightarrow \mathcal{Y}$ is defined as follows:

$$E_{out}(h) = P[h(\mathbf{x}) \neq f({\mathbf{x}}) ]$$

Where $f:\mathcal{X} \rightarrow \mathcal{Y}$ is the target function mapping inputs $\mathbf{x} \in \mathcal{X}$ to the output space $\mathcal{Y}$. The book states that this quantity depends on the particular probability distribution over $\mathcal{X}$ that is relevant to the problem. My question is, given some known probability distribution (i.e. a density function $p(\mathbf{x}): \mathcal{X} \rightarrow \mathbb{R}$), and assuming you know the target function $f$ and the hypothesis $h$, how would you go about computing this quantity? Is there even a way to do so in general, or does the specific distribution need to be known?

I realize this is not very practical of a question, but I'm just having a hard time conceptualizing this quantity and seeing how it might be computed may help me understand the statement better.


1 Answer 1


If you know the density $p$, then evaluating $E_\text{out}$ amounts to integrating $p$ over the sub-region of $\mathcal{X}$ where $h(\mathbf{x}) \neq f(\mathbf{x})$. For a very simple example, suppose $\mathcal{X} = \mathcal{Y} = \{0, 1\}$, and define $h$, $f$, and $p$ as follows:

$\mathbf{x}$ $h(\mathbf{x})$ $f(\mathbf{x})$ $p(\mathbf{x})$
0 1 0 1/3
1 1 1 2/3

Then hopefully it's clear that $E_\text{out}(h) = 1/3$. In practice, $p$ is generally unknown, and $E_\text{out}$ is instead estimated by collecting a test set and counting the number of examples where $h(\mathbf{x}) \neq f(\mathbf{x})$.


Your Answer

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

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