0-1 Loss

A multiclass categorization problem asks us to learn a predictor h : X → [k]. The predictor takes an input from X and returns one output from [k]. This describes the prediction task: construct a rule that turns inputs into class predictions.

The two sides of h : X → [k] describe different parts of the prediction task. X is the input side: it supplies the objects that the predictor receives. [k] is the output side: it supplies the possible class labels that the predictor may return. The predictor's role is to connect one input with one output label.

Producing a label and evaluating that label are separate tasks. The predictor h produces an output in [k]. An evaluation rule then considers whether that output is correct for the example. The source description emphasizes this separation: the mapping tells us what the predictor does, while an evaluation rule tells us how to discuss the quality of its output.

The 0-1 loss evaluates a multiclass prediction through a correct-or-incorrect outcome. When the predicted class agrees with the true class, the loss records the correct outcome as 0. When the predicted class does not agree with the true class, the loss records the incorrect outcome as 1. The important idea is that the loss evaluates the returned label; it does not produce the label.

A single prediction produces one evaluation outcome. Across a collection of examples, these individual correct-or-incorrect outcomes provide a way to discuss how well the multiclass predictor performs. This is the performance perspective needed after the predictor has produced labels.

PAC learnability for multiclass predictors is considered with respect to the 0-1 loss. This means that the learning discussion evaluates a predictor through the correct-or-incorrect outcomes produced on examples. The predictor h remains the rule that maps inputs in X to labels in [k]; the 0-1 loss is the rule used to assess how well that predictor performs.