Practise: Learning a Rule From Examples

Row 3 has no label, so it becomes a second query and drops out of the stored set. Row 7 has a word where a number belongs, so no query can be compared with it, and it drops out too. The two spoiled rows are different rows, so the stored set falls from 9 to $9-2=7$. Those seven rows carry $7\times 4=28$ feature numbers. The query row's missing feature does not change the stored count, but it does stop the query from being placed in the table at all, because the table requires the same four features in the same order on every row.

For $A$, the differences are $2-1=1$ and $3-2=1$. Their squares are 1 and 1, the sum is 2, and the distance is $\sqrt{2}=1.414$. For $B$, the differences are $2-4=-2$ and $3-6=-3$. Their squares are 4 and 9, the sum is 13, and the distance is $\sqrt{13}=3.606$. The nearer row is $A$, at distance 1.414, so the one-neighbour rule answers with $A$'s label, which is 0. Squaring removes the signs, so the direction of each difference does not matter.

Rule A's error rate is $7/250=0.028$. Rule B's error rate is $9/360=0.025$. Rule A is worse, because $0.028>0.025$. The gap is $0.028-0.025=0.003$, which is three tenths of one percentage point. The raw counts point the other way: B has more wrong answers (9 against 7). The counts are measured on different denominators, so they cannot be compared until each is divided by its own number of rows. The comparison also belongs to these two sets of rows, not to new rows from either source.

The differences are $-1$, $0$ and $-3$. Their squares are $1$, $0$ and $9$. The sum is $1+0+9=10$, and the average over three rows is $10/3=3.333$. The middle row is free because the prediction equals the truth there. The first row is off by one and costs 1; the third row is off by three and costs 9, so it carries most of the total. A price list that charged the size of the difference instead would give $(1+0+3)/3=1.333$, which is why the choice of loss changes the number the report contains.

Score each row against the rule built from all four. The row at 1 is nearest to itself and is correct. The first row at 2 is nearest to itself; the second row at 2 ties with it at distance zero, and the smaller index belongs to the first row, so both rows at 2 receive the label 0. The first is correct; the second has true label 1 and is wrong. The row at 3 is nearest to itself and is correct. One row of four is wrong, so the training error rate is $1/4=0.25$. Without the duplicate, every row would be nearest to itself and the rate would be zero. The duplicate with two different labels is the only thing that breaks that argument.

Before the copy, the nearest stored row to each test query is the row at 5, with label 1. The true labels are 0, 0 and 0, so all three answers are wrong and the rate is $3/3=1$. Copy $(6,0)$ into the training set. The query at 6 now has an exact copy at distance zero and is answered 0, which is correct. The query at 7 is 1 away from the copy at 6 and 2 away from the row at 5, so it is answered 0 and is correct. The query at 8 is 2 away from the copy at 6 and 3 away from the row at 5, so it is answered 0 and is correct. The reported rate falls from 1 to $0/3=0$. The rule did not improve; the test set stopped being a test set when one of its rows entered the training set.

At $k=1$ the nearest row carries label 1, so the answer is 1. At $k=3$ the vote is 1, 0, 0: label 0 has two votes and label 1 has one, so the answer is 0. At $k=5$ the vote is 1, 0, 0, 1, 1: label 1 has three votes and label 0 has two, so the answer is 1. The three answers are 1, 0 and 1. The table and the query do not change between the three runs; only the number of neighbours allowed to speak changes. At $k=5$ the rule reads every stored row, so its answer no longer depends on the query at all.

The rule answers 1 when the feature exceeds 3. On the training rows it answers 0, 0, 0, 1, 1, which matches all five labels, so the training error is zero. On the test rows at 6, 7 and 8 it answers 1, 1, 1. The true labels are 1, 0 and 1, so the row at 7 is wrong and the other two are right. The test error rate is $1/3=0.333$. The four questions of section 2.6 separate this rule from the nearest-neighbour rule: its class is the set of cuts between consecutive feature values, its loss is the zero-one loss, its search keeps the cut with the fewest training errors, and its performance is read on rows the search never touched.