# Sample Error vs. True Error

$\newcommand{\error}{\operatorname{error}}$I'm reading Mitchell's Machine Learning and am on Chapter 5, evaluating hypotheses. In it, he defines sample error and true error:

The sample error, denoted $\error_s(h)$ of hypothesis $h$ with respect to target function $f$ and data sample $S$ is :

$$\error_s(h)=\frac{1}{n}\sum\limits_{x \in S}{\delta(f(x), h(x))}$$

where $n$ is the number of examples in $S$, and the quantity $${\delta(f(x), h(x))} = \begin{cases} 1 & \text{if }f(x) \neq h(x) \\ 0 & \text{otherwise} \end{cases}$$

The true error, denoted $\error_D(h)$ of hypothesis with respect to target function $f$ and distribution $D$, is the probability that $h$ will misclassify an instance drawn a random according to $D$:

$$\error_D(h)= \mathbb{P}(f(x) \neq h(x))$$

1. What is the distribution $D$ referred to here?

2. It seems like true error is really just looking at the proportion of examples that $h$ misclassifies. I'm a little confused about why $D$ is being introduced here at all...

I like to think of this as being related to Empirical Risk Minimization. That is to say, what happens when you only have a small dataset that was generated by some distribution P, and you learn a hypothesis to predict something on that dataset; is that hypothesis's error on the dataset indicative of it's error you might see on any other data generated by P? With that in mind:

1) The distribution D is the distribution that actually generated your data. This is the same distribution that would have generated your data sample that you use for calculating the sample error, however you might not necessarily know what this distribution is all the time (that's another story).

2) It might be helpful to think of the true error as kind of like the general error described above – what is the error that we can expect to see on any random sample from that distribution?

I could also have the wrong intuition here, and if so would love clarification.

I don't have enough reputation to comment under NBartley's answer, but the answer for 1 is correct. The distribution $D$ is the distribution that actually generated your data.

1. Yes, it is exactly the proportion of errors that h misclassifies. However, that depends on the distribution of the data. For a simple example, suppose you have three classes, and you can always classify class 1 perfectly, but you can't really distinguish between class 2 and 3, so you have a 50% chance of misclassifying members of those classes. Then, if you have a high chance of seeing class 1, you will have a low error rate, but if you have a high chance of seeing members of class 2 or class 3 you will have a high error rate. Of course, in general, it may be more complicated than that, as your error rate likely is not constant over classes. That is, you will probably have some data points that are obviously in class 1, but some other points may be members of class 1 that look more like members of class 2, etc. Anyways, the point is that the proportion of examples that h misclassifies depends on the distribution of the examples, and that's why you need $D$.

Here Sample Error is the error Calculated w.r.t Data Sample Set S. Whereas, True Error is the error Calculated w.r.t Data Distribution D. Here we can see that Sample Error is 0.2 (i.e 1 out of 5) from the OUR SAMPLE circle & True Error is 0.2 (i.e 10 out of 20) from all the DATA DISTRIBUTION