Measuring the mistake

Run the one-neighbour rule on the ones and sevens: store 300 ones and 300 sevens, then score the rule on 600 further images that it never stored, and eighteen of them return the incorrect digit [S:51:339].

Eighteen is merely a count, and a count compares with nothing: is eighteen out of twenty unsatisfactory, and is eighteen out of sixty thousand acceptable? The identical count signifies different things on different sets, so the initial task is to divide by the size of the set. !Two price lists for one answer. On the left, the zero-one loss charges 0 for a correct name and 1 for any wrong one, so a near miss and a distant miss cost the same. On the right, the squared loss charges the square of the miss, so a miss by two costs four times a miss by one. The vertical axis is the charge; the horizontal axis on the right is the size of a numeric miss. Status: schematic.

The expense of one answer is its loss, which receives the answer that the rule produced and the answer that was true, and returns a number [S:27:266]. Write ℓ for the loss, ŷ for the answer the rule produced, and y for the answer that was true; the curly letter is an ell, not a one, and the hat marks a produced value. For digit names the natural price list charges one unit for a wrong answer and nothing for a correct one. That price list is the zero-one loss:

!The same eighteen wrong answers from the digit run on two sets. The left grid holds 600 rows, so the error rate is 18/600 = 0.03. The right grid holds 60, so the identical count gives 18/60 = 0.30. A count is not a rate until its denominator travels with it. Status: schematic.

It charges one for a wrong name and nothing for a right one, and it treats every wrong name identically.

A price list that reads only the answer the rule produced, and never the answer that was true, is not a loss at all. Charge one unit whenever the rule answers seven, and a rule that never answers seven pays nothing while getting every seven incorrect. The loss has to compare the two answers, which is why both arguments appear in its definition.

Charging the identical price for every mistake is a decision: a seven called a one and a seven called a nine cost the identical quantity, because digit names occupy no order. For a quantity such as a price, the squared loss is the price list $\ell (\hat{y},y)=(\hat{y}-y{)}^2$. A miss of two then costs four and a miss of one costs one, so being wrong by two is four times as severe, and the squared loss is the better choice.

Now calculate the average of the costs over a set of labelled examples: add them and divide by how many examples there are. Write h for the rule, so h(x_i) is the answer it gives on row i, and write S for the set of rows you average over. The bars in |S| mean the number of members of S, not an absolute value, and the sum runs over the rows in S rather than over an index range. The formula is:

The formula says: score every example in the set, add the costs, and divide by the number of examples. On the left, R̂_S(h) is read "R hat of h on S". R is the risk, the average over the whole world; the hat marks an estimate computed from a finite set; the subscript names that set. With the zero-one loss the sum counts the wrong answers, and the average is the error rate of the rule on that set. The general name for such an average is the empirical risk.

Worked example. The one-versus-seven run produces 18 incorrect answers in 600, so the error rate is 18 divided by 600, which equals 0.03, or 3 per cent. The zeros-versus-ones run, with the identical code and the identical number of stored images, produces 0 incorrect answers in 600, so its rate is 0.0. Three neighbours instead of one produce 14 incorrect answers, so their rate is 14 divided by 600, which is 0.0233 to four places.

Interpret the final division carefully: the rate is 2.33 per cent, and writing 2.3 per cent rounds it. The difference from 18 errors is four examples, which is 4 divided by 600, or 0.0067, approximately seven tenths of a single percentage point. Four examples in six hundred is a modest change, and whether it is a genuine improvement is a question this chapter cannot yet answer.

Two sizes break the reading rather than the arithmetic: on one example the rate is zero or one and nothing between, so it cannot distinguish a competent rule from a fortunate one. On an empty set there is nothing to average, and a program that returns zero there is reporting on a set it never scored.

A count without its denominator cannot be interpreted, and a rate without its set cannot be checked. "Three per cent wrong" is a report only when the reader can ask: three per cent of what, chosen how, and read how many times? The next section takes the final two questions, because they determine whether the number is a measurement at all.

The rate is measured on examples you hold, and the number you desire is the rate on examples nobody has labelled yet. That second number has no name you can write down here, and pretending the first is the second is the most expensive confusion in the subject. The loss is also a decision, and a price list that ignores the true answer, or that charges the identical amount for a near miss and a distant one, measures the incorrect quantity.

The formal statement. A loss takes a predicted label and a true label and returns a non-negative number [S:27:266]. The risk of a predictor $h$ is the expected loss over the distribution that produces the pairs, written $R(h)$ [S:27:267]. The empirical risk on the $n$ rows you hold is the average loss on those rows:

Read it as: score every stored row, add the costs, and divide by the number of rows. The core carries a subscript naming the set; here the subscript drops because a single set is in play. The error rate is this quantity with the zero-one loss.

The proof. Suppose the rows are independent draws from the same distribution as the query, and suppose $h$ is fixed before the rows are drawn. Then the empirical risk is unbiased: the expectation of $\hat{R}(h)$ equals $R(h)$. The argument is linearity of expectation, since the expectation of a sum is the sum of the expectations and each term has expectation $R(h)$. That is the whole proof, and its one hypothesis does all the work. A predictor chosen after seeing the rows is not fixed, and the identity does not apply to it. Section 2.4 is the price of that sentence.

The edge case. The argument order is part of the definition. Mathematics for Machine Learning writes $\ell (y_n,{\hat{y}}_n)$, true label first [S:27:266]; the core writes the prediction first. For the zero-one loss and the squared loss the two orders return the same number, because both are symmetric in their arguments. For an asymmetric loss, such as one that charges more for a false alarm than for a missed case, the order changes the risk, and a reader who assumes symmetry reads a different number from the same table.

The edge case that averaging hides. A rule that always answers the most frequent label has an empirical risk equal to the share of rows carrying some other label. That share can be small while the rule is useless on the rows you care about. The average prices every row equally, and the deployment does not.

What the core left out. An error rate measured on $n$ rows is a random quantity, and its spread shrinks like $1/\sqrt{n}$. With the zero-one loss the standard error is $\sqrt{\hat{R}(1-\hat{R})/n}$. That formula, not the rate itself, decides whether four fewer errors in six hundred rows is a signal. The core said the chapter could not yet answer the question; this is the shape of the answer, and 2.5 uses it.

Original sources. The loss-and-risk formulation is section 8.2.2 of Mathematics for Machine Learning: a loss returns a non-negative number [S:27:266], the empirical risk averages it over the training rows, and the expected risk averages it over all data [S:27:267]. The 3 per cent figure for ones against sevens comes from Barber's digit experiment [S:51:339].

An open question. The loss you minimise and the quantity you are judged by need not coincide, and no general procedure connects the two. [S:27:267] states the design rule, that the loss should correspond to the performance measure of the task, and then reports that in practice there is often a mismatch. For a screening test, a missed case and a false alarm carry different costs, and the zero-one loss cannot tell them apart. What would settle a case: report the deployed decision rule's cost under the actual cost matrix, not under the proxy loss, and show whether the ranking of candidate rules changes. Until then a lower loss is evidence about the loss, and only sometimes evidence about the decision.

A frontier method. Proper scoring rules formalise when a loss rewards an honest probability rather than a lucky label. A loss is proper when the true distribution minimises it in expectation, and log loss and the Brier score both qualify [S:63:209]. This matters as soon as a predictor returns a probability, because the zero-one loss cannot distinguish a confident wrong answer from a hesitant one, and the average it reports hides the difference. It also gives a reason to prefer one loss over another that does not depend on how the numbers happen to come out on your rows.

What to read next. Read section 8.2.2 of [S:27:266] for the definitions and the mismatch remark, section 5.1.6 of [S:63:209] for proper scoring rules and the Brier score, and chapter 14 of [S:51:339] for the experiment the numbers come from. Taken in that order, the three readings answer one question each: what a loss is, which losses are honest, and how the numbers came out.