Disagreement Regions and Classification Regret

Why Disagreement Is Where Regret Occurs

A plug-in classifier first estimates the probability of a positive label at each feature value, then thresholds that estimate to make a classification decision. Its errors matter for classification risk only where its decision differs from the decision based on the true probability. If both rules choose the same label at a feature value, their conditional risks there are identical—even if the estimated probability is inaccurate.

This observation can be made exact. The excess risk is an integral over the set where the two decisions disagree, and the contribution from each such point is weighted by how strongly the true conditional probability favors one label over the other. We will derive this identity and work through examples that distinguish the size of a disagreement region from the regret it produces.

Setup and Definitions

Let $(X,Y)$ be a test observation, where $Y\in\{0,1\}$. Define the binary regression function $\eta(x)=P(Y=1\mid X=x)$, using a measurable version of this conditional probability. A classifier $g$ is a measurable function taking values in $\{0,1\}$. Its classification risk is $R(g)=P(g(X)\ne Y)$.

The Bayes classifier chooses the label with the larger conditional probability. We use the tie convention $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$; either choice is optimal when $\eta(x)=1/2$. Given a measurable regression estimate $\hat\eta$, a plug-in classifier with the same tie convention is $\hat g(x)=\mathbf{1}\{\hat\eta(x)\ge 1/2\}$.

Definition: The disagreement region of $\hat g$ relative to $g^*$ is $D=\{x:\hat g(x)\ne g^*(x)\}$. The classification regret, or excess risk, is $\mathcal{E}(\hat g)=R(\hat g)-R(g^*)$. If $\hat\eta$ depends on a training sample $S$, these definitions apply conditionally on a fixed realized $S$; the test observation is taken to be independent of that training sample.

For a fixed training sample, $\hat\eta$ and $\hat g$ are fixed functions, so the risk identity below is an ordinary population statement. It can then be averaged over the training sample, provided the risks are measurable and integrable. This distinction prevents a random fitted rule from being treated as though it were independent of the data used to fit it.

Conditional Risk and the Exact Identity

At a fixed feature value $x$, predicting 0 has conditional error probability $\eta(x)$, because an error occurs exactly when $Y=1$. Predicting 1 has conditional error probability $1-\eta(x)$. Thus the conditional risk of any classifier is

P(g(X)\ne Y\mid X=x) = \eta(x)\mathbf{1}\{g(x)=0\} + (1-\eta(x))\mathbf{1}\{g(x)=1\}.

The Bayes decision selects the smaller of these two conditional error probabilities. The next result gives the precise cost of choosing the other label.

Theorem: Suppose $Y\in\{0,1\}$, $\eta(x)=P(Y=1\mid X=x)$, and $g$ is a measurable classifier. With $g^*(x)=\mathbf{1}\{\eta(x)\ge 1/2\}$, $$ R(g)-R(g^*) = E\!\left[|2\eta(X)-1|\mathbf{1}\{g(X)\ne g^*(X)\}\right]. $$ In particular, excess risk is nonnegative and receives no contribution from points where $g$ and $g^*$ agree.

Proof. Fix $x$. If $g(x)=g^*(x)$, their conditional risks are equal, so the conditional risk difference is zero. If $\eta(x)>1/2$ and the decisions disagree, then $g^*(x)=1$ and $g(x)=0$. Their conditional risks are respectively $1-\eta(x)$ and $\eta(x)$, so the difference is $2\eta(x)-1=|2\eta(x)-1|$. If $\eta(x)<1/2$ and the decisions disagree, then $g^*(x)=0$ and $g(x)=1$. Their conditional risks are respectively $\eta(x)$ and $1-\eta(x)$, giving difference $1-2\eta(x)=|2\eta(x)-1|$. When $\eta(x)=1/2$, both labels have conditional risk $1/2$; the difference is zero, whether or not the decisions agree. Thus, for every $x$, the conditional risk difference is $|2\eta(x)-1|\mathbf{1}\{g(x)\ne g^*(x)\}$. Taking expectations over $X$ gives the displayed identity. Its integrand is nonnegative, proving nonnegativity as well. $\square$

Applying the theorem to a plug-in classifier gives the central interpretation: the estimated threshold decision matters only on the disagreement region, and each point there contributes its true conditional penalty. A point close to the true threshold has a small penalty; a point farther from the threshold has a larger one. The identity itself requires no assumption about how $\hat\eta$ was constructed.

Corollary: For a fixed fitted estimate $\hat\eta$, with $\hat g(x)=\mathbf{1}\{\hat\eta(x)\ge 1/2\}$, $$ R(\hat g)-R(g^*) = \int_D |2\eta(x)-1|\,dP_X(x), \qquad D=\{x:\hat g(x)\ne g^*(x)\}. $$ If the estimate is based on a training sample $S$, the same equality holds for the conditional risks given $S$, with the corresponding fitted disagreement region $D_S$.

This statement concerns classification decisions, not the size of the regression estimation error by itself. An estimate can be numerically far from $\eta$ yet preserve the threshold decision, producing no regret at that point. Conversely, even a modest estimation error can reverse the decision near the threshold. The identity quantifies the resulting risk, rather than merely counting such reversals.

Worked Examples

Worked Example: A Disagreement at One Support Point

Suppose $X$ takes values $a,b,c$ with probabilities $0.2,0.5,0.3$, respectively. The true regression probabilities are $\eta(a)=0.80$, $\eta(b)=0.55$, and $\eta(c)=0.20$. A fitted estimate gives $\hat\eta(a)=0.70$, $\hat\eta(b)=0.40$, and $\hat\eta(c)=0.10$. Find the two classifiers and the regret.

At $a$, both probabilities exceed $1/2$, so both rules predict 1. At $b$, the true probability exceeds $1/2$ but the estimate is below $1/2$, so $g^*(b)=1$ and $\hat g(b)=0$. At $c$, both are below $1/2$, so both rules predict 0. Hence $D=\{b\}$.

The weight at $b$ is $|2(0.55)-1|=0.10$. Since $P(X=b)=0.5$, the regret is $\mathcal{E}(\hat g)=0.5(0.10)=0.05$. For a direct check, the Bayes risk is $0.2(0.20)+0.5(0.45)+0.3(0.20)=0.325$. The plug-in risk is $0.2(0.20)+0.5(0.55)+0.3(0.20)=0.375$. Their difference is $0.375-0.325=0.05$, as given by the identity.

Worked Example: Regret Over an Interval

Let $X$ be uniform on $[0,1]$, and suppose $\eta(x)=0.2+0.6x$. Consider the estimate $\hat\eta(x)=0.08+0.6x$. Calculate the disagreement region and the regret.

The true threshold is reached when $0.2+0.6x=0.5$, which gives $x=0.5$. Thus the Bayes classifier predicts 1 for $x\ge 0.5$. The estimated threshold is reached when $0.08+0.6x=0.5$, giving $x=0.7$. The plug-in classifier predicts 1 for $x\ge 0.7$. They disagree on $[0.5,0.7)$; the endpoints do not affect the risk under a uniform distribution.

On this interval, $2\eta(x)-1=2(0.2+0.6x)-1=1.2x-0.6$, which is nonnegative. Therefore \[ \mathcal{E}(\hat g) = \int_{0.5}^{0.7}(1.2x-0.6)\,dx = \left[0.6x^2-0.6x\right]_{0.5}^{0.7}. \] At $x=0.7$, the expression is $0.6(0.49)-0.42=-0.126$; at $x=0.5$, it is $0.15-0.30=-0.15$. The difference is $-0.126-(-0.15)=0.024$. Thus the regret is $0.024$, entirely contributed by the interval on which the decisions disagree.

Worked Example: Disagreement Probability Is Not Regret

Suppose $X$ has two possible values, $u$ and $v$, with probabilities $0.7$ and $0.3$. Let $\eta(u)=0.49$, $\eta(v)=0.90$, while $\hat\eta(u)=0.90$, $\hat\eta(v)=0.51$. Compare the probability of disagreement with the regret.

At $u$, the Bayes rule predicts 0 and the plug-in rule predicts 1. At $v$, both predict 1. Therefore $D=\{u\}$, and $P(X\in D)=0.7$. The pointwise regret weight at $u$ is $|2(0.49)-1|=0.02$, so the total regret is $0.7(0.02)=0.014$.

A direct risk calculation confirms this result. The Bayes risk is $0.7(0.49)+0.3(0.10)=0.373$, while the plug-in risk is $0.7(0.51)+0.3(0.10)=0.387$. The difference is $0.014$. Although disagreement occurs with probability $0.7$, its risk contribution is small because the true probability at the disagreement point is close to $1/2$. At $v$, the estimate is substantially below the truth, but it preserves the decision, so it contributes zero regret.

Reading the Identity Correctly

The integral identity separates two features of plug-in performance: where decisions are reversed and how costly each reversal is under the true conditional distribution. The probability $P(X\in D)$ records how often the decisions differ. Regret instead averages the conditional penalty $|2\eta(X)-1|$ over that region. These quantities answer different questions and need not be close.

A common mistake is to say that regret equals the probability of disagreement, or to conclude that a large disagreement region must imply large regret. That reasoning drops the weight in the exact identity. The correction is to calculate $\int_D |2\eta(x)-1|\,dP_X(x)$: disagreement is necessary for a positive pointwise contribution, but its contribution is scaled by the true conditional risk gap. At a true tie, $\eta(x)=1/2$, the weight is zero even if the selected labels differ.

For a data-dependent estimate, this interpretation first applies conditional on its training sample. Averaging the conditional identity over training samples gives the corresponding expected regret, with both the fitted disagreement region and the true weighting accounted for. No claim that every fitted classifier has the same disagreement region is needed.

Key takeaway: Plug-in classification regret is supported only on the disagreement region. Its exact value is the probability-weighted average of the true conditional risk gap over that region, not the region's probability alone.

Check Your Understanding

Use the disagreement-region identity to answer these questions.

At a feature value $x$, the plug-in and Bayes classifiers both predict 1. What is their conditional risk difference there, even if $\hat\eta(x)\ne\eta(x)$?
If the classifiers disagree at a point where $\eta(x)=0.63$, what is the pointwise excess conditional risk?
Why can disagreement on a set with substantial probability still produce small regret?
In the continuous example, what decision does each classifier make for $x=0.6$, and what is the conditional excess risk there?
Explain why a regression estimate can be inaccurate at a point without contributing to classification regret at that point.