Derive: Learning a Rule From Examples

Define $h$ in three parts. At each stored input set $h(x_i)=y_i$. At the new input set $h(x^{\ast })=y^{\ast }$. At every other input set $h(x)=0$, or any other fixed label. On each stored row the prediction equals the recorded label, so the zero-one loss is 0. The empirical risk is the average of $n$ zeros, which is 0. Now replace $y^{\ast }$ by a different label $y^{\prime }$ and define a second predictor $h^{\prime }$ in the same way. Both $h$ and $h^{\prime }$ have empirical risk 0 on $S$, and they disagree at $x^{\ast }$. The empirical risk minimisation problem asks for a candidate with the smallest average loss on the stored rows, so it gives the same value, 0, to both candidates and cannot choose between them. Section 2.1 says the table constrains a predictor at six places and is silent at the seventh; this construction proves the general form of that statement. Something beyond the table has to choose: a restriction on the class, a tie rule, or a prior preference. Section 2.6 calls that restriction the hypothesis class, and it is the first of the four questions.

Let $x_i$ be the feature value of row $i$. When the query is $x_i$, the distance to row $j$ is $|x_i-x_j|$. Row $i$ itself gives distance 0, and every other row gives a distance above 0 unless $x_j=x_i$. If all feature values are different, row $i$ is the only row at distance zero, so the rule returns $y_i$ and row $i$ is correct. The training error is zero. Now suppose a feature value repeats. Let $f(i)$ be the smallest index $j$ with $x_j=x_i$. Every row with that feature value ties at distance zero, and the smaller-index rule chooses $f(i)$, so the rule returns $y_{f(i)}$ for row $i$. Row $i$ is correct exactly when $y_i=y_{f(i)}$. The training error is therefore $$\frac{1}{n}\#\{i:y_i\ne y_{f(i)}\}.$$ For the six rows, the first occurrences are row 1 at feature 1, row 2 at feature 2, row 4 at feature 3 and row 6 at feature 4. Row 3 repeats feature 2 with label 0, while the first row at feature 2 carries label 1, so row 3 is wrong. Row 5 repeats feature 3 with label 1, the same label as row 4, so row 5 is correct. All first occurrences are correct. One row of six is wrong, and the training error rate is $1/6=0.167$. The zero training error of section 2.4 is therefore a consequence of distinct feature values, not a property of the rule that survives every table.

After scaling, the distance from the query to $A$ is $\sqrt{(s\cdot 0-s\cdot 0{)}^2+(12-0{)}^2}=12$. The distance from the query to $B$ is $\sqrt{(s\cdot 1-s\cdot 0{)}^2+(0-0{)}^2}=s$. The two distances are equal when $s=12$. At $s=1$, $B$ is at distance 1 and $A$ is at distance 12, so the rule returns $B$'s label, which is 1. At $s=100$, $A$ is at distance 12 and $B$ is at distance 100, so the rule returns $A$'s label, which is 0. The table, the labels and the query did not change; only the unit of the first feature changed. This is a counterexample to the idea that the nearest neighbour is a fact about the data. A distance is a weighted claim about which differences matter, and changing the unit changes the weights. Section 2.2's ski and snowboard example is the same failure with centimetres and millimetres; here the flip happens at a scale you can compute.