Error rates and optimal classifiers

Section of Statistical classifiers and discriminant analysis, part of Statistical learning

Type	Section
Taught in	Statistical classifiers and discriminant analysis
Part	Statistical learning

Imagine two normal class distributions with overlapping support, both having positive prior probability. At a measurement where their weighted densities agree, the posterior probabilities are both 1/2. Every rule using only that measurement has conditional error 1/2 there. More training observations can improve the estimates of the distributions. The overlap of the two class distributions remains. Additional informative measurements can change the problem. Bayes error is the floor for the information currently available.

A rule \eta always returns a class, and that class may be the wrong one. For G classes there are G^2-G ordered pairs of distinct classes, and each pair is a different kind of mistake. Let R_h\subset\mathbb{R}^p be the region that the rule assigns to class h. The regions are disjoint and cover the space. The rate at which the rule predicts class h when the true class is g is

e_{gh}(\eta)=\mathbb{P}\bigl(\eta(X)=h\bigm|Y=g\bigr) =\int_{R_h}f_g(\mathbf{x})\,d\nu, \qquad g,h\in\{1,\ldots,G\},

where \nu is the appropriate measure on \mathbb{R}^p. Adding the mistakes that leave class g gives the class-specific error rate,

\mathrm{Err}_g(\eta) =\mathbb{P}\bigl(\eta(X)\ne g\bigm|Y=g\bigr) =\int_{\cup_{h\ne g}R_h}f_g(\mathbf{x})\,d\nu =1-\int_{R_g}f_g(\mathbf{x})\,d\nu.

To average class-specific errors, weight by the target prevalences: \mathrm{Err}(\eta)=\sum_g\pi_g\mathrm{Err}_g(\eta). For a fixed rule and fixed class-conditional distributions, changing only the prevalences leaves the class-specific rates unchanged. If the rule is also changed to reflect the new prevalences, its decision regions move and those rates can change. Keep the rule fixed when making the first comparison.

To decide which rule is best, specify a loss. Write c_{gh} for the cost of predicting class h when the true class is g, with c_{gg}=0, so a correct label is costless. The first choice treats every mistake as equally unwanted: c_{gh}=1 whenever g\ne h. Under that choice the overall error rate is the risk, up to the unit of cost. Multiplying every cost by the same positive constant multiplies every risk by that constant and does not change which class is chosen. The unit cost is the wrong loss when one mistake is several times as costly as another. That case is taken up once the equal-cost rule is in hand.

The true class is coded as a binary vector \mathbf{y} of length G, with a 1 in the position of the true class, so the second of three classes is \mathbf{y}=(0,1,0)^\top. Write y_g for its gth element, and write Q[g,h]=0 when g=h and Q[g,h]=1 otherwise.

Definition 1 (Zero–one loss and risk) Let (X,Y) be a new point drawn from the target distribution. The zero–one loss of the classifier is

l\bigl(Y,\eta(X)\bigr) = \begin{cases} 0, & \eta(X)=Y,\\ 1, & \eta(X)\ne Y, \end{cases} =\sum_{g=1}^{G} Y_g\, Q\bigl[g,\eta(X)\bigr].

The conditional risk at X=\mathbf{x} is the expected loss over Y drawn from its conditional distribution, which is multinomial with a single trial and probabilities \tau_1(\mathbf{x}),\ldots,\tau_G(\mathbf{x}).

Article: Zero–one loss and risk →

Under zero–one loss the sum over classes charges 0 to the predicted class and 1 to every other class, and \mathbb{E}(Y_g\mid\mathbf{x})=\tau_g(\mathbf{x}) because Y_g is the indicator of class g. The expectation therefore collapses to one minus the posterior of the class that was chosen:

\begin{align*} \mathbb{E}\bigl[l\bigl(Y,\eta(\mathbf{x})\bigr)\bigm|X=\mathbf{x}\bigr] &=\sum_{g=1}^{G}\tau_g(\mathbf{x})\,Q\bigl[g,\eta(\mathbf{x})\bigr]\\ &=\sum_{g\ne\eta(\mathbf{x})}\tau_g(\mathbf{x}) =1-\tau_{\eta(\mathbf{x})}(\mathbf{x}). \end{align*}

The conditional risk equals the posterior probability that the predicted class is wrong. Zero–one loss did that work: every wrong class contributes its posterior, and the correct class contributes nothing. No normality was used. In most cases every class density is positive at \mathbf{x}, so every posterior is positive and every rule has some conditional risk there. The rule itself is deterministic, so at each \mathbf{x} it names one class.

Theorem 1 (Bayes-optimal rule) A rule that minimises the conditional risk for every \mathbf{x} is a Bayes rule, also called a Bayes-optimal or minimum-risk rule. Under zero–one loss it is

\eta(\mathbf{x})=B(\mathbf{x})=\arg\max_{g\in\{1,\ldots,G\}}\tau_g(\mathbf{x}).

Article: Bayes-optimal rule →

At a fixed \mathbf{x}, predicting h incurs conditional error 1-\tau_h(\mathbf{x}). Choose a largest posterior to make this as small as possible. Integrating that pointwise inequality over X proves optimality for overall error as well. Ties can be resolved by any fixed convention; the risk is the same.

This result concerns the true joint distribution and the specified loss. A fitted classifier uses estimated probabilities and need not attain the bound. Its training error can fall below the Bayes risk, because training error reuses the observations that built the rule. The bound concerns a fresh observation.

Unequal costs

Main article: Classification with unequal costs

When a missed case and a false alarm are different events, the loss has to say so. A correct classification is still taken to cost nothing. What moves the rule is the ratio of the costs of the two mistakes. Scaling every cost by the same positive constant scales the risk and leaves the minimiser unchanged, so a false negative several times as costly as a false positive is fully described by that ratio.

For general costs c_{gh}, with c_{gg}=0, the loss on a new observation (\mathbf{x},\mathbf{y}) is l(\mathbf{y},\eta(\mathbf{x}))=\sum_g y_g\, c_{g,\eta(\mathbf{x})}. The same expectation as before, now with cost c_{gh} in place of 1, gives the conditional risk

\mathbb{E}\bigl[l\bigl(Y,\eta(\mathbf{x})\bigr)\bigm|X=\mathbf{x}\bigr] =\sum_{g\ne\eta(\mathbf{x})}\tau_g(\mathbf{x})\,c_{g,\eta(\mathbf{x})}.

At each \mathbf{x}, choose the predicted class that makes this sum smallest:

\eta(\mathbf{x})=B(\mathbf{x}) =\arg\min_{h\in\{1,\ldots,G\}}\sum_{g\ne h}\tau_g(\mathbf{x})\,c_{gh}.

For two classes the comparison simplifies. The rule predicts class 1 when \tau_2(\mathbf{x})\,c_{21}<\tau_1(\mathbf{x})\,c_{12}, which is \tau_1(\mathbf{x})/\tau_2(\mathbf{x})>c_{21}/c_{12}. The threshold on the posterior odds moves toward the class whose misclassification costs more. Equal costs put the threshold at 1 and recover the maximum-posterior rule. The posteriors themselves still come from Bayes’ theorem. Only the cutoff has changed.

Error rates and optimal classifiers

Unequal costs

Used in

See also