Conditional Zero-One Risk and the Bayes Sign

Why Conditional Risk Is the Starting Point

A binary classifier makes a decision at each feature value, but the cost of that decision depends on the conditional distribution of the label there. If the positive label is very likely at a particular \(x\), predicting negative has a different consequence than it would at a point where the two labels are nearly equally likely. The conditional zero-one risk makes this comparison explicit.

The key quantity is the regression function \(\eta(x)=P(Y=+1\mid X=x)\), where the labels are encoded as \(-1\) and \(+1\). Once \(\eta(x)\) is known, the two possible decisions have conditional risks \(\eta(x)\) and \(1-\eta(x)\). Their difference determines the preferred label, while their distance from each other determines the cost of choosing the other one.

Definition: Let \(X\) be a feature-valued random variable and \(Y\in\{-1,+1\}\) a binary label. Assume a regular conditional distribution of \(Y\) given \(X\) exists, as it does when the feature space is standard Borel. Let \(\eta(x)\) be a measurable version of \(P(Y=+1\mid X=x)\). A classifier is a measurable function \(g\) taking values in \(\{-1,+1\}\). Its conditional zero-one risk at \(x\) is \(R_x(g)=P(g(x)\ne Y\mid X=x)\). Its population risk is \(R(g)=P(g(X)\ne Y)\).

Conditional quantities involving \(x\) are understood using the chosen version of the conditional distribution; their values only need to be meaningful for \(X\)-almost every \(x\). The zero-one loss is \(1\) when a prediction disagrees with the label and \(0\) otherwise. Thus, at a fixed feature value, the conditional risk is simply the conditional probability of making an error.

Computing the Two Conditional Risks

At a given \(x\), the probability of the positive label is \(\eta(x)\), and the probability of the negative label is \(1-\eta(x)\). Predicting \(+1\) makes an error precisely when \(Y=-1\); predicting \(-1\) makes an error precisely when \(Y=+1\). Therefore,

R_x(+1)=1-\eta(x), \qquad R_x(-1)=\eta(x).

The smaller of these two numbers is the minimum achievable conditional risk. This comparison also identifies the Bayes decision: choose the label with larger conditional probability. When the probabilities are equal, both decisions minimize conditional risk.

Definition: A Bayes classifier for zero-one loss is any measurable classifier \(g^*\) that minimizes \(R_x(g)\) for \(X\)-almost every \(x\). One convenient tie convention is \(g^*(x)=+1\) when \(\eta(x)\ge 1/2\), and \(g^*(x)=-1\) when \(\eta(x)<1/2\). At points where \(\eta(x)=1/2\), either label is Bayes-optimal.

Worked Example: A Single Conditional Distribution

Suppose that at a particular feature value \(x\), the conditional probability of a positive label is \(\eta(x)=0.73\). Compute the risk of each decision, determine a Bayes decision, and find the conditional regret of the other decision.

Predicting \(+1\) is wrong only when \(Y=-1\), which has conditional probability \(1-0.73=0.27\). Thus \(R_x(+1)=0.27\). Predicting \(-1\) is wrong when \(Y=+1\), so \(R_x(-1)=0.73\). The Bayes decision is \(+1\), and the minimum conditional risk is \(0.27\).

The conditional regret of predicting \(-1\) is the excess over this minimum: \(0.73-0.27=0.46\). The posterior margin is \(|2\eta(x)-1|=|1.46-1|=0.46\), agreeing with the regret formula derived below.

Theorem: For any \(x\), the minimum conditional zero-one risk is \(R_x^*=\min\{\eta(x),1-\eta(x)\}=(1-|2\eta(x)-1|)/2\). With the tie convention above, for every classifier \(g\), \(R_x(g)-R_x^*=|2\eta(x)-1|\,\mathbf{1}\{g(x)\ne g^*(x)\}\). At a tie, the right-hand side is zero regardless of the chosen decision.

Proof. Write \(\eta=\eta(x)\) for the fixed feature value. The two possible conditional risks are \(\eta\) and \(1-\eta\), so their minimum is \(\min\{\eta,1-\eta\}\). Since \(\eta+(1-\eta)=1\), this minimum equals \((1-|\,\eta-(1-\eta)\,|)/2=(1-|2\eta-1|)/2\).

If \(\eta>1/2\), the Bayes decision is \(+1\), with risk \(1-\eta\). Choosing \(-1\) instead gives excess risk \(\eta-(1-\eta)=2\eta-1=|2\eta-1|\); choosing \(+1\) gives excess zero. If \(\eta<1/2\), the Bayes decision is \(-1\), with risk \(\eta\). Choosing \(+1\) gives excess \((1-\eta)-\eta=1-2\eta=|2\eta-1|\), while choosing \(-1\) gives zero excess. Finally, if \(\eta=1/2\), both decisions have risk \(1/2\), so the excess is zero for either decision, and \(|2\eta-1|=0\). These cases establish the identity. \(\square\)

Conditional Regret and the Posterior Margin

The quantity \(|2\eta(x)-1|\) is the posterior margin in this calculation. It measures how strongly the conditional label distribution favors one class over the other. A margin near zero means the two labels are nearly balanced, so choosing the less likely label costs little conditional risk. A margin near one means one label is highly probable, so choosing against it costs much more.

The theorem says that conditional regret has two factors: the posterior margin, and an indicator of whether the classifier disagrees with the Bayes decision. A wrong decision at a tie is not a meaningful error relative to Bayes optimality, because both labels minimize risk there. The zero margin correctly assigns that decision zero regret.

Worked Example: Conditional and Population Regret on a Finite Feature Space

Let \(X\) take values \(a,b,c\) with probabilities \(0.2,0.5,0.3\), respectively, and suppose \(\eta(a)=0.9\), \(\eta(b)=0.5\), and \(\eta(c)=0.2\). Use the tie convention that predicts \(+1\) at \(b\). Compare the Bayes classifier with a classifier that predicts \(-1\) at \(a\), \(-1\) at \(b\), and \(+1\) at \(c\).

At \(a\), the Bayes decision is \(+1\), and its conditional risk is \(1-0.9=0.1\). At \(b\), either label is optimal and the risk is \(0.5\). At \(c\), the Bayes decision is \(-1\), with risk \(0.2\). The Bayes population risk is therefore \(0.2(0.1)+0.5(0.5)+0.3(0.2)=0.02+0.25+0.06=0.33\).

For the other classifier, the conditional risks at \(a,b,c\) are \(0.9,0.5,0.8\), respectively. Its population risk is \(0.2(0.9)+0.5(0.5)+0.3(0.8)=0.18+0.25+0.24=0.67\). The excess is \(0.67-0.33=0.34\).

The margin identity gives the same answer. At \(a\), the classifier disagrees with Bayes and the margin is \(|1.8-1|=0.8\), contributing \(0.2(0.8)=0.16\). At \(b\), it disagrees with the chosen tie convention, but the margin is zero, contributing \(0\). At \(c\), it disagrees with Bayes and the margin is \(|0.4-1|=0.6\), contributing \(0.3(0.6)=0.18\). The total regret is \(0.16+0+0.18=0.34\).

From Conditional Risk to Population Risk

The conditional calculation gives the population comparison by averaging over the feature distribution. The result is useful because it separates the local decision question from how often each feature region occurs.

Theorem: For any measurable classifier \(g\) and Bayes classifier \(g^*\), \(R(g)-R(g^*)=E[|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}]\). In particular, \(g^*\) minimizes population zero-one risk over all measurable classifiers.

Proof. Let \(L(g(X),Y)=\mathbf{1}\{g(X)\ne Y\}\). By the law of iterated expectation, \(R(g)=E[L(g(X),Y)]=E[E[L(g(X),Y)\mid X]]\). The inner conditional expectation is \(R_X(g)\), so \(R(g)=E[R_X(g)]\). Applying the same identity to \(g^*\) and subtracting gives \(R(g)-R(g^*)=E[R_X(g)-R_X(g^*)]\).

The pointwise theorem gives \(R_X(g)-R_X(g^*)=|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}\) almost surely. Substitution proves the displayed population identity. Its integrand is nonnegative, so \(R(g)\ge R(g^*)\) for every measurable \(g\), establishing population optimality. \(\square\)

Worked Example: A Continuous Posterior and a Threshold Rule

Let \(X\) be uniform on \([0,1]\), and let \(\eta(x)=x\). The Bayes classifier predicts \(-1\) for \(x<1/2\) and \(+1\) for \(x\ge 1/2\). Compute its population risk, then compute the risk and regret of the rule that predicts \(+1\) only when \(x\ge 0.7\).

The Bayes conditional risk is \(\min\{x,1-x\}\). Since \(X\) has uniform density one, its population risk is \(\int_0^{1/2}x\,dx+\int_{1/2}^1(1-x)\,dx=1/8+1/8=1/4\).

The rule with threshold \(0.7\) disagrees with Bayes on \(1/2\le x<0.7\). On that interval it predicts \(-1\) where the Bayes decision is \(+1\), so its conditional excess risk is \(|2x-1|=2x-1\). Its total regret is \(\int_{1/2}^{0.7}(2x-1)\,dx=[x^2-x]_{1/2}^{0.7}=(-0.21)-(-0.25)=0.04\). Therefore its population risk is \(0.25+0.04=0.29\).

Common Pitfall: Confusing Disagreement With Regret

A frequent mistake is to count every disagreement with a chosen Bayes classifier as equally costly. That ignores how uncertain the label is at the feature value. In the finite example, disagreement at \(a\) had margin \(0.8\), while disagreement at the tie \(b\) had margin zero. The two disagreements therefore contributed different amounts of regret.

Another mistake is to describe the margin as the distance from \(x\) to a geometric decision boundary. Here it is instead the absolute difference between the two conditional class probabilities: \(|\eta(x)-(1-\eta(x))|=|2\eta(x)-1|\). Feature-space geometry may influence where such values occur, but it is not the definition of the posterior margin. Finally, the tie convention only selects a convenient representative of the Bayes-optimal decisions; it does not make one label better than the other when \(\eta(x)=1/2\).

Key takeaway: Conditional zero-one risk is \(\eta(x)\) for a negative prediction and \(1-\eta(x)\) for a positive prediction. The Bayes decision selects the more probable label, and a wrong decision incurs conditional regret exactly \(|2\eta(x)-1|\); at a tie, that regret is zero.

Check Your Understanding

Use the conditional-risk formulas and the posterior-margin identity to answer these questions.

If \(\eta(x)=0.35\), calculate the risks of predicting each label, identify a Bayes decision, and find the regret of predicting \(+1\).
Why can a classifier disagree with a tie-convention Bayes classifier at \(\eta(x)=1/2\) while incurring zero conditional regret?
For \(\eta(x)=0.8\), what is the posterior margin, and what is the conditional regret of predicting \(-1\)?
State how conditional excess risk becomes population excess risk.
Explain why \(|2\eta(x)-1|\) is not, by definition, a distance in feature space.