Prediction Rule

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

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

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

• Treating classifier error as the result of one prediction

  Classifier error is a probability over randomly selected data points, not a description of only one prediction.

  Fix: Consider all possible points and weight the incorrect ones according to distribution D.

• Ignoring the correct labeling function

  The error condition is specifically h(x) does not equal f(x).

  Fix: Compare the predicted label h(x) with the correct label f(x).

• Confusing D with f

  D determines how domain points are selected or weighted, while f assigns their correct labels.

  Fix: Ask two separate questions: how likely is this point under D, and what label does f give it?

• Reading h : X → Y backwards

  The notation expresses a mapping from domain points to labels.

  Fix: Read it as h takes a point from X and produces a label in Y.

• Treating prediction rule and A(S) as unrelated ideas

  A(S) is the particular hypothesis, or prediction rule, returned by algorithm A after receiving S.

  Fix: Use prediction rule for the general function and A(S) for the particular rule returned from training.

Apply the Rule

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

1. A prediction rule is a function that maps a domain point to a label.
2. In h : X → Y, h is the rule, X is the domain, and Y is the label set.
3. An error occurs when h(x) does not equal the correct label f(x).
4. Distribution D determines how likely each domain point is when measuring error.
5. Generalization error, risk, and true error are synonymous names for the probability of an incorrect prediction in this setting.
6. A learning algorithm A receiving training sequence S returns the particular hypothesis A(S), which is a prediction rule.