# Trying to figure out which the training set is

Can someone help me on this one? As can be seen in the screenshot, it says the loss is 1/2. Where's that 1/2 coming from? How can I replace the values in the h(s) function?

Source PDF

As can bee seen in the screenshot, it says the loss is 1/2. Where does that 1/2 is coming from?

What does the predictor $$h_S(\mathbf{x})$$ actually do? In simple English, it predicts the label from the training set if $$\mathbf{x}$$ is a member of the training set, and otherwise it predicts 0. Obviously, this predictor will perform quite well when evaluated on the training set. It will achieve a loss of 0.

But what happens if we evaluate this predictor not just on the training set, but on the entire distribution $$\mathcal{D}$$? Notice that the predictor will correctly predict any instance outside of the dotted blue square. Because this is a continuous area, there are an infinite number of points that $$h_S$$ will predict correctly.

Also notice that there are an infinite number of points that $$h_S$$ will predict incorrectly. Any point that is inside the blue square but was not found in the training set will incorrectly be predicted 0 instead of 1.

Since there are an infinite number of points where $$h_S$$ is incorrect, and an infinite number of points where $$h_S$$ is correct, the authors say that the loss is 1/2.

How can I replace the values in the h(s) function?

$$h_S(\mathbf{x})$$ is a memorization classifier. If it has already "seen" a data point during training, then it will regurgitate the classification of that point. Otherwise it just predicts 0.

So if you give $$h_S$$ a red point, it will predict 0. If you give it a blue point, it will predict 1. If you give it any other point in the square, it will predict 0.

• Wouldn't it be "The predictor will correctly predict any instance INSIDE the dotted blue area"? Instead of outside ? Dec 22, 2020 at 5:05
• @NaveganTeX I don't think so. The instances inside the dotted lines are 1s, but the predictor defaults to 0s. So for any instance inside the dotted lines that wasn't seen during training, the predictor will be incorrect. Dec 22, 2020 at 15:45

To clarify the proposed classifier (because I think it depends on some nonstandard notation): classify any point that is in the (finite) training set according to its true label. (Clearly this gives you an error rate of 0 on the training set.) For any point not in the training set, just predict label 0.

Now, consider a random new point in the gray square: it's the same as a point from the training set with probability 0, so assume it's not. Then our classifier predicts label 0. But the point has probability 1/2 (area of blue square over area of gray square) of being label 1. So the error rate of our classifier, on test data, is 1/2.

• I was blown away by that nonstandard notation, yes :) Dec 21, 2020 at 18:23