Error of a Classifier

From Point to Prediction

A machine-learning learner ultimately needs to produce a way to make predictions. That way is called a prediction rule: a function that takes a domain point and maps it to a label. Once the rule exists, it can be applied to new domain points, such as future papayas, to predict their labels.

Reading h : X → Y

The notation h : X → Y describes the direction of the prediction rule. The symbol X represents the domain of possible input points, and Y represents the set of labels. The rule h accepts a point x from X and produces the label h(x) in Y. The input point is transformed into the label that will be used as its prediction; the rule does not return another domain point.

Rules and Learned Hypotheses

Prediction rule is the general concept: any function that takes a domain point and maps it to a label. A learning algorithm is a procedure that produces such a rule. If A denotes the learning algorithm and S denotes the training sequence, then A(S) denotes the hypothesis returned by A after receiving S. Thus, a hypothesis is a particular prediction rule selected from the training sequence, while prediction rule describes the kind of object the learner must produce.

Where Classification Error Comes From

A classifier is evaluated over randomly selected data points, not by inspecting only one prediction. The distribution D determines how likely the possible domain points are to be selected. The correct labeling function f determines the correct label for a domain point. For a point x, the classifier's prediction is h(x), while the correct label is f(x). An error occurs exactly when h(x) does not equal f(x).

Tracing Correct and Incorrect Outcomes

To evaluate one point, follow the same comparison every time. First, select x according to D. Next, obtain the classifier's prediction h(x). Then, obtain the correct label f(x). If the two labels match, this point is not an error. If they differ, this point is an error.

Combining Point Probabilities

For a finite set of possible points, calculate classifier error by identifying which points are incorrectly predicted and combining the probabilities of those points. Points with matching predicted and correct labels contribute no error. The total error is therefore the probability mass assigned by D to the points where h(x) does not equal f(x).

Names for the Same Quantity

In this context, generalization error, risk, and true error are synonymous names for classifier error. Each refers to the probability that the prediction rule gives an incorrect label on a randomly selected data point. The quantity depends on both the distribution D and the correct labeling function f, because D determines which points are likely to be selected and f determines which labels are correct.

Common Interpretation Mistakes

• Treating h(x) as the correct label

  h(x) is the classifier's predicted label. The correct label is f(x).

  Fix: Compare h(x) with f(x) to determine whether the prediction is correct.

• Confusing one prediction with classifier error

  Classifier error is a probability over randomly selected domain points, not merely the outcome for one point.

  Fix: Use the distribution D and combine the probabilities of all points where h(x) does not equal f(x).

• Ignoring the distribution D

  The error depends on the probability that a random point is one of the incorrectly classified points.

  Fix: Weight the incorrect outcomes by their probabilities under D.

• Treating A and A(S) as interchangeable

  A denotes the learning algorithm, while A(S) denotes the hypothesis it returns after receiving training sequence S.

  Fix: Use A for the algorithm and A(S) for the particular prediction rule produced from S.

Apply the Error Test

Key Takeaways

1. A prediction rule is a function that maps domain points in X to labels in Y.
2. In h : X → Y, h is the rule, X is the domain of inputs, and Y is the label set.
3. A learning algorithm A receiving a training sequence S returns the hypothesis A(S), which is a particular prediction rule.
4. A point is misclassified when h(x) does not equal the correct label f(x).
5. Classifier error is the probability of misclassification under D; in this context, generalization error, risk, and true error are equivalent names.