Bayes Thresholding and the Classification Boundary

From Label Probabilities to a Decision Rule

In binary classification, a decision rule assigns one of two labels to each feature value. The rule should favor the label that is more probable at that value of the features. The comparison is local: it uses the conditional distribution of the label given the features, not the overall proportion of labels in the population.

Let $X$ be a feature-valued random variable taking values in a standard Borel space $\mathcal X$, and let $Y\in\{0,1\}$ be the label. A classifier is a measurable function $g:\mathcal X\to\{0,1\}$. Write $P_X$ for the distribution of $X$, and define the binary regression function by $\eta(x)=P(Y=1\mid X=x)$, using a measurable version of this conditional probability. The conditional probability of label 0 is then $1-\eta(x)$.

Definition: The Bayes classifier under ordinary zero-one misclassification is a classifier that minimizes $P(g(X)\ne Y)$ over measurable classifiers $g$. Its positive decision region is the set of feature values assigned label 1; its negative decision region is the set assigned label 0.

At a feature value $x$, the two labels have conditional probabilities $\eta(x)$ and $1-\eta(x)$. Comparing these probabilities gives the threshold $1/2$: label 1 is more probable when $\eta(x)>1/2$, while label 0 is more probable when $\eta(x)<1/2$. When the probabilities are equal, either label has the same conditional chance of being correct.

Definition: The threshold set is $T=\{x\in\mathcal X:\eta(x)=1/2\}$. The strict positive and negative regions are $G_+=\{x:\eta(x)>1/2\}$ and $G_-=\{x:\eta(x)<1/2\}$. The threshold rule assigns label 1 on $G_+$ and label 0 on $G_-$; it may assign either label on $T$.

Why Thresholding Gives a Bayes Classifier

The following result derives the rule by comparing the two possible conditional error probabilities. It also accounts for ties, where the optimal decision is not unique.

Theorem: For any measurable classifier $g$, its misclassification probability is $$ P(g(X)\ne Y) = E\!\left[\eta(X)\mathbf 1\{g(X)=0\} + (1-\eta(X))\mathbf 1\{g(X)=1\}\right]. $$ A classifier that assigns 1 on $G_+$, 0 on $G_-$, and either label on $T$ minimizes this probability. Every Bayes classifier agrees with these strict-region assignments $P_X$-almost surely.

Proof. Let $\mathbf 1\{g(X)\ne Y\}$ be the indicator of an error. Conditional expectation given $X$ yields

P(g(X)\ne Y) =E[\mathbf 1\{g(X)\ne Y\}] =E\!\left[E[\mathbf 1\{g(X)\ne Y\}\mid X]\right].

Because $g(X)$ is determined by $X$, if $g(X)=0$, an error occurs exactly when $Y=1$, with conditional probability $\eta(X)$. If $g(X)=1$, an error occurs exactly when $Y=0$, with conditional probability $1-\eta(X)$. This proves the displayed identity.

For each fixed $X=x$, the contribution is $\eta(x)$ if the rule chooses 0 and $1-\eta(x)$ if it chooses 1. If $\eta(x)>1/2$, then $1-\eta(x)<\eta(x)$, so choosing 1 gives the smaller contribution. If $\eta(x)<1/2$, then $\eta(x)<1-\eta(x)$, so choosing 0 gives the smaller contribution. At equality, both contributions are $1/2$.

Thus the threshold rule has a contribution no larger than that of any other classifier at every $x$, and integrating gives no larger overall misclassification probability. Moreover, choosing the nonpreferred label on a strict region increases the contribution there by $|2\eta(x)-1|>0$. A Bayes classifier therefore cannot make such choices on a set of positive $P_X$-probability. Choices on $T$ do not change the probability of error. $\square$

The theorem identifies the rule up to choices on the tie set and differences on $P_X$-null sets. In particular, if $P_X(T)=0$, then all Bayes classifiers agree $P_X$-almost surely. If the tie set has positive probability, different assignments there can still give the same minimum error.

Worked Examples of Thresholding

Worked Example: A Discrete Feature With a Tie

Suppose $X$ takes values $a,b,c$ with probabilities $0.2,0.5,0.3$, respectively, and the regression function is $\eta(a)=0.8$, $\eta(b)=0.5$, and $\eta(c)=0.2$. Find the decision regions and the Bayes error.

At $a$, $\eta(a)=0.8>1/2$, so the rule assigns label 1. At $c$, $\eta(c)=0.2<1/2$, so it assigns label 0. At $b$, the two labels have equal conditional probability, so either assignment is optimal. Hence $G_+=\{a\}$, $G_-=\{c\}$, and $T=\{b\}$.

The conditional error is $0.2$ at $a$, $0.5$ at $b$, and $0.2$ at $c$. Weighting by the probabilities of the feature values gives $$ 0.2(0.2)+0.5(0.5)+0.3(0.2) =0.04+0.25+0.06 =0.35. $$ The Bayes error is $0.35$, regardless of the label assigned at $b$. For example, assigning 0 at $b$ makes the rule choose 1 only at $a$; assigning 1 at $b$ adds $b$ to the positive region without changing the error.

Worked Example: A One-Dimensional Threshold Location

Let $X$ take values in $[-2,4]$, and suppose $$ \eta(x)=\frac{1}{1+\exp(-(2x-3))}. $$ Find the threshold set and the positive and negative regions on the support of $X$.

The denominator is positive, so $\eta(x)>1/2$ exactly when $\exp(-(2x-3))<1$. Since the exponential function is increasing, this is equivalent to $-(2x-3)<0$, or $x>3/2$. Equality holds at $x=3/2$. Therefore $$ T=\{3/2\},\qquad G_-=[-2,3/2),\qquad G_+=(3/2,4]. $$ The threshold classifier assigns label 0 to values below $3/2$ and label 1 to values above it, with either choice at $3/2$. The support restriction matters: these regions describe decisions only for feature values that $X$ can take.

Worked Example: A Circular Threshold Set

Suppose $X=(X_1,X_2)$ is supported on the closed disk $x_1^2+x_2^2\le 4$, and on that disk $$ \eta(x_1,x_2)=\frac12+\frac{x_1^2+x_2^2-1}{8}. $$ Find the threshold set and the two strict decision regions. First check that this is a valid regression function on the stated support.

On the disk, $0\le x_1^2+x_2^2\le4$. The smallest value of $\eta$ is $1/2-1/8=3/8$, and the largest is $1/2+3/8=7/8$. Both lie in $[0,1]$, so the formula gives valid probabilities.

Solving $\eta(x_1,x_2)=1/2$ gives $x_1^2+x_2^2=1$, the unit circle. If $x_1^2+x_2^2<1$, then $\eta<1/2$, so the negative region is the open unit disk. If $1<x_1^2+x_2^2\le4$, then $\eta>1/2$, so the positive region is the part of the support outside the unit circle. Either label is optimal on the circle itself.

Threshold Set and Geometric Boundary

The equation $\eta(x)=1/2$ defines a threshold set, but it need not describe exactly the geometric boundary of a decision region. To discuss a geometric boundary, the feature space must also have a topology. For example, when $\mathcal X$ is a subset of Euclidean space, the topological boundary of a region consists of points every neighborhood of which meets both that region and its complement.

When $\eta$ is continuous, the topological boundary of $G_+=\{x:\eta(x)>1/2\}$ is contained in $T$. Indeed, if $\eta(x)>1/2$, continuity gives a neighborhood of $x$ throughout which $\eta>1/2$, so $x$ is an interior point of $G_+$, not its boundary. If $\eta(x)<1/2$, continuity gives a neighborhood disjoint from $G_+$, so $x$ is not in its boundary either. A boundary point must therefore satisfy $\eta(x)=1/2$. $\square$

The containment can be strict. If $\eta$ equals $1/2$ throughout an open region, that region belongs to $T$ but may contain no boundary points of $G_+$. Conversely, without continuity, a topological boundary point need not have $\eta(x)=1/2$. It is useful to state whether “decision boundary” means the threshold set itself or the topological boundary of a particular decision region.

Common Pitfalls and Why the Boundary Matters

Thresholding at the overall prevalence. The relevant comparison is between $\eta(x)$ and $1/2$, not between $\eta(x)$ and $P(Y=1)$. The prevalence does not tell us which label is more probable at a given feature value.
Treating ties as forced decisions. At $\eta(x)=1/2$, neither label is preferred under zero-one misclassification. A convention can select a label, but that convention does not make the other choice worse.
Assuming the threshold set is always a smooth curve or surface. It may be empty, irregular, disconnected, or large. Its geometric form depends on the regression function and the feature space.
Ignoring the feature distribution. The threshold rule is defined by $\eta$, but changes on feature values with zero probability do not affect overall misclassification probability. The meaningful uniqueness claim is generally almost sure, not pointwise everywhere.

The threshold set matters because it marks where the more probable label changes, when such a change occurs. In practice, a fitted regression function can be thresholded to produce a classifier, and its estimated level set can be used to describe where predictions switch. A level set alone does not establish that predictions switch across it: the function’s values on either side, and the distribution of $X$, also matter.

Key takeaway: Under zero-one misclassification, compare the two conditional label probabilities. The Bayes rule assigns label 1 where $\eta(x)>1/2$, label 0 where $\eta(x)<1/2$, and either label at equality. The threshold set is defined by equality; its relation to a geometric boundary requires additional structure such as continuity.

Check Your Understanding

Use the definitions and derivation above to answer these questions.

If $\eta(x)=0.65$, what label does the threshold rule assign, and what is its conditional probability of error?
Can two classifiers that disagree on a set of positive probability both be Bayes classifiers? State the condition on that set that permits this.
For a continuous regression function, why must every topological boundary point of $\{x:\eta(x)>1/2\}$ belong to the threshold set?
Give one reason the threshold set might be larger than the topological boundary of the positive region.
Why does the marginal probability $P(Y=1)$ not replace the one-half threshold in the Bayes rule?