Prediction Rule
Classifier error measures the probability of an incorrect prediction on a random data point.
One Prediction from Input to Label
A classifier becomes useful when it can take a new domain point and produce a label. The function that performs this job is called a prediction rule. If h is the rule and x is a domain point, applying h to x produces h(x), a label that the classifier predicts for that point.
The Function Signature
A prediction rule maps a domain point to a label. The notation h : X → Y expresses this direction: h is the rule, X is the domain of possible input points, and Y is the set of labels. The arrow indicates that inputs from X are mapped to outputs in Y.
For one particular point x in X, the rule produces one prediction h(x) in Y. The point itself is the input, while h(x) is the label used as the prediction. Passing the point through h does not describe how the point was selected; it describes how the rule transforms that point into a predicted label.
Where Error Comes From
To evaluate a classifier, compare its prediction h(x) with the correct label f(x). An error occurs exactly when h(x) does not equal f(x). Classifier error is the probability of this incorrect-prediction event when a data point is selected according to the underlying distribution D.
The Roles of D and f
The distribution D and the correct labeling function f contribute different information. D determines how domain points are selected or weighted when asking about a random data point. The function f assigns the correct label to a domain point. After those roles are established, h can be evaluated by checking whether its prediction agrees with f.
A Small Error Calculation
Weighted Incorrect Predictions
Suppose a random domain point can be x1, x2, or x3. Distribution D assigns probabilities 0.5, 0.3, and 0.2 to these points. The correct labels are f(x1) = red, f(x2) = blue, and f(x3) = red. A prediction rule gives h(x1) = red, h(x2) = red, and h(x3) = red. What is the classifier error?
- 1Compare x1
The prediction h(x1) is red and the correct label f(x1) is red, so x1 is not an error.
- 2Compare x2
The prediction h(x2) is red but the correct label f(x2) is blue, so x2 is an error.
- 3Compare x3
The prediction h(x3) is red and the correct label f(x3) is red, so x3 is not an error.
- 4Use D
Only x2 contributes to the error, and D assigns probability 0.3 to x2. Therefore the probability of an incorrect prediction is 0.3.
The classifier error is 0.3, because the only incorrect prediction occurs on a point selected with probability 0.3.
| Domain point | Probability under D | Correct label f(x) | Prediction h(x) | Incorrect? |
|---|---|---|---|---|
| x1 | 0.5 | red | red | No |
| x2 | 0.3 | blue | red | Yes |
| x3 | 0.2 | red | red | No |
The error is the probability assigned by D to the points where h(x) differs from f(x).
What do you think happens?
If the prediction for x3 changed from red to blue while its correct label remained red, would the classifier error increase, decrease, or stay the same?
Reveal answer
Increase
x3 would become an additional incorrect prediction, and D assigns probability 0.2 to x3. The error would therefore increase from 0.3 to 0.5.
Three Names for One Quantity
In this setting, generalization error, risk, and true error are synonymous names for the same quantity: the expected probability that the classifier gives an incorrect label on a randomly selected data point. Each name refers to comparing h(x) with f(x) while taking the distribution D into account.
Rule and Learned Hypothesis
Prediction rule is the general idea: a function that takes a domain point and maps it to a label. A learning algorithm produces a particular prediction rule. If A denotes the learning algorithm and S denotes its training sequence, then A(S) denotes the hypothesis returned by the algorithm after receiving S.
Mistakes to Avoid
Common mistake Treating classifier error as the result of one prediction
What it looks likeA classifier predicts one new point incorrectly, so its error is declared to be 1.
Why it failsClassifier error is a probability over randomly selected data points, not a description of only one prediction.
Do this insteadConsider all possible points and weight the incorrect ones according to distribution D.
Common mistake Ignoring the correct labeling function
What it looks likeA prediction is called correct because it seems plausible, without comparing h(x) with f(x).
Why it failsThe error condition is specifically h(x) does not equal f(x).
Do this insteadCompare the predicted label h(x) with the correct label f(x).
Common mistake Confusing D with f
What it looks likeThe distribution D is described as the function that assigns the correct label.
Why it failsD determines how domain points are selected or weighted, while f assigns their correct labels.
Do this insteadAsk two separate questions: how likely is this point under D, and what label does f give it?
Common mistake Reading h : X → Y backwards
What it looks likeLabels in Y are treated as inputs and domain points in X as outputs.
Why it failsThe notation expresses a mapping from domain points to labels.
Do this insteadRead it as h takes a point from X and produces a label in Y.
Common mistake Treating prediction rule and A(S) as unrelated ideas
What it looks likeA(S) is described as something other than a prediction rule because it was produced by a learning algorithm.
Why it failsA(S) is the particular hypothesis, or prediction rule, returned by algorithm A after receiving S.
Do this insteadUse prediction rule for the general function and A(S) for the particular rule returned from training.
Apply the Rule
A domain contains two possible points, x1 and x2. Distribution D assigns probability 0.7 to x1 and 0.3 to x2. The correct labels are f(x1) = green and f(x2) = yellow. A prediction rule gives h(x1) = yellow and h(x2) = yellow. Determine the classifier error and explain which point contributes to it.
Hints
- Compare h(x1) with f(x1), then compare h(x2) with f(x2).
- Only points where h(x) differs from f(x) contribute to the error.
- Use the probability assigned by D to the incorrect point.
To solve problems of this kind, trace the process in order: identify the point selected according to D, find its correct label using f, find the prediction produced by h, compare the two labels, and then account for the point's probability if they differ.
Summary
- 1A prediction rule is a function that maps a domain point to a label.
- 2In h : X → Y, h is the rule, X is the domain, and Y is the label set.
- 3An error occurs when h(x) does not equal the correct label f(x).
- 4Distribution D determines how likely each domain point is when measuring error.
- 5Generalization error, risk, and true error are synonymous names for the probability of an incorrect prediction in this setting.
- 6A learning algorithm A receiving training sequence S returns the particular hypothesis A(S), which is a prediction rule.
At a glance
- A prediction rule takes a domain point as input and returns a label as its prediction.
- Classifier error is the probability, under D, that the prediction h(x) differs from the correct label f(x).
- The notation h : X → Y describes a mapping from domain points to labels.
- Generalization error, risk, and true error refer to the same incorrect-prediction probability here.
- A learning algorithm produces a particular prediction rule, written A(S) when algorithm A receives training sequence S.