Tutorials › Statistical Learning (Graduate) › Posterior Ties and Nonunique Bayes Classifiers

Home  /  Tutorials  /  Bayes Rules and Conditional Risk

Bayes Rules and Conditional Risk · Tutorial 56 of 989

Posterior Ties and Nonunique Bayes Classifiers

Learn how posterior ties create multiple minimizing class labels, when those choices yield genuinely different Bayes classifiers, and why the Bayes risk stays the same.

Beginner 9 min read

What You'll Learn

  • Compute the conditional zero-one risk of assigning each class label.
  • Identify the maximizing posterior labels and interpret ties.
  • Characterize Bayes classifiers as measurable choices among posterior maximizers.
  • Prove that tied minimizing labels have equal conditional and population risk.
  • Distinguish ties on positive-probability feature sets from ties on null sets.
  • Avoid confusing pointwise nonuniqueness with distinct classifiers up to almost-sure equality.

Why Posterior Ties Matter

Under zero-one loss, a classifier is penalized only when its predicted class differs from the true class. At a given feature value, the best label is therefore one with the largest conditional probability. Sometimes several labels share that largest probability. Each is an equally good decision at that feature value, but this pointwise fact does not always mean that there are multiple distinct classifiers in the probabilistic sense: changes on feature values that occur with probability zero do not change risk.

This tutorial makes both statements precise. We work with a finite set of class labels, derive the conditional risk of each decision, and show that every measurable choice among the posterior maximizers attains the same Bayes risk.

Conditional Risk and Posterior Maximizers

Let \(Y\) be the class label, taking values in \(\{1,\ldots,K\}\), and let \(X\) be the observed features. A deterministic classifier is a measurable function \(g\) that assigns a label \(g(X)\) to the observed features. Under zero-one loss, the loss for predicting \(a\) when the true label is \(y\) is \(I\{a\ne y\}\), where \(I\) is the indicator function.

Definition: For each label \(k\), the posterior class probability is \(\eta_k(x)=P(Y=k\mid X=x)\), using measurable versions of these conditional probabilities. The conditional risk of choosing label \(a\) at feature value \(x\) is \(r(a\mid x)=E[I\{a\ne Y\}\mid X=x]\). A posterior maximizer at \(x\) is any label in \(M(x)=\{k:\eta_k(x)=\max_{1\le j\le K}\eta_j(x)\}\). A tie occurs when \(M(x)\) contains more than one label.

The conditional risk follows directly from the definition of zero-one loss. If the chosen label is \(a\), an error occurs exactly when \(Y\ne a\). Thus the probability of error, conditional on \(X=x\), is one minus the probability that \(Y=a\).

$$ r(a\mid x)=\sum_{y=1}^K I\{a\ne y\}\eta_y(x) =1-\eta_a(x). $$

Consequently, minimizing conditional risk is equivalent to maximizing the posterior class probability. If several labels have the same maximum posterior probability, they all have the same conditional risk. The following result also describes which classifiers achieve the smallest population risk.

Theorem: Let \(g\) range over measurable classifiers with values in \(\{1,\ldots,K\}\). Its zero-one risk is \(R(g)=P(g(X)\ne Y)\), and the Bayes risk is \(R^*=E[1-\max_k\eta_k(X)]\). A classifier \(g\) attains \(R^*\) if and only if \(g(X)\in M(X)\) with probability one.

Proof. By conditioning on \(X\), the risk of \(g\) is the expectation of its conditional risk:

$$ R(g)=E[I\{g(X)\ne Y\}] =E[E[I\{g(X)\ne Y\}\mid X]] =E[1-\eta_{g(X)}(X)]. $$

For each \(x\), \(\eta_{g(x)}(x)\le\max_k\eta_k(x)\), so

$$ R(g)-R^* =E[\max_k\eta_k(X)-\eta_{g(X)}(X)]\ge 0. $$

This proves the lower bound and identifies \(R^*\) as the smallest possible risk: since there are finitely many labels and the posterior probabilities are measurable, choosing the smallest label in \(M(x)\) gives a measurable classifier attaining the bound. For any \(g\), the difference inside the expectation is a nonnegative random variable. Its expectation is zero if and only if it is zero with probability one. That equality holds exactly when \(g(X)\) is a posterior maximizer with probability one. This proves both directions. \(\square\)

What a Tie Changes—and What It Does Not

At a feature value \(x\) with a tie, the minimizing labels are exactly the elements of \(M(x)\). Their conditional risks are all \(1-\max_k\eta_k(x)\). Choosing one tied label rather than another changes the prediction at \(x\), but it does not change the conditional risk there.

The distinction between pointwise and population-level nonuniqueness is important. If two classifiers select different tied labels on a set of feature values having positive probability, they are genuinely different as random predictions, yet both can have Bayes risk. If they differ only on a set of probability zero, they are equal almost surely and have the same risk regardless. A tie at a particular value of \(x\) therefore does not by itself guarantee multiple classifiers that differ with positive probability.

Worked Example: A Binary Tie at One Feature Value

Suppose \(X\) takes values \(u\) and \(v\), each with probability \(1/2\). The posterior probabilities for labels 1 and 2 are \((0.5,0.5)\) at \(u\), and \((0.8,0.2)\) at \(v\). Find the Bayes decisions and risk, and determine whether the tie gives distinct Bayes classifiers.

At \(u\), both labels maximize the posterior probability. The conditional risk of either choice is \(1-0.5=0.5\). At \(v\), label 1 is the unique maximizer, and its conditional risk is \(1-0.8=0.2\).

A Bayes classifier must choose label 1 at \(v\), but may choose either label at \(u\). Its risk is therefore

$$ R^*=\frac12(0.5)+\frac12(0.2)=0.25+0.10=0.35. $$

Choosing label 1 at \(u\) and choosing label 2 at \(u\) produce two classifiers that disagree whenever \(X=u\), an event of probability \(1/2\). Both choose a posterior maximizer at each feature value, so both have risk \(0.35\). Here the tie produces genuinely distinct Bayes classifiers, not merely different assignments at an irrelevant point.

Worked Example: A Multiclass Tie and the Bayes Risk

Let \(X\) take values \(a\) and \(b\), with \(P(X=a)=1/3\) and \(P(X=b)=2/3\). At \(a\), let the posterior probabilities for labels 1, 2, and 3 be \((0.45,0.45,0.10)\). At \(b\), let them be \((0.10,0.35,0.55)\). Find the minimizing labels and calculate the Bayes risk.

At \(a\), labels 1 and 2 tie for the largest posterior probability, \(0.45\). The conditional risk of either is \(1-0.45=0.55\). At \(b\), label 3 is the unique maximizer, with conditional risk \(1-0.55=0.45\).

The classifier must choose label 3 at \(b\), but may choose either label 1 or label 2 at \(a\). Averaging the conditional risks over the two feature values gives

$$ R^*=\frac13(0.55)+\frac23(0.45) =\frac{11}{60}+\frac{18}{60} =\frac{29}{60}. $$

For either choice at \(a\), the contribution from that feature value is \((1/3)(0.55)=11/60\); the contribution from \(b\) is \((2/3)(0.45)=18/60\). Thus the two classifiers have the same risk, \(29/60\), even though they predict different labels whenever \(X=a\), an event of probability \(1/3\).

Ties on Sets of Probability Zero

A posterior tie can occur at a feature value that the random variable \(X\) reaches with probability zero. Such a tie affects the pointwise set \(M(x)\), but it cannot change population risk by changing a classifier only there. The next example makes the distinction explicit.

Worked Example: A Tie at a Single Point

Let \(X\) be uniform on \([0,1]\), and suppose there are two labels with \(\eta_1(x)=x\) and \(\eta_2(x)=1-x\). These are valid conditional probabilities because they are nonnegative and sum to one for every \(x\in[0,1]\). The posterior probabilities tie at \(x=1/2\), where both equal \(1/2\). At every other point there is a unique maximizing label.

A Bayes classifier chooses label 2 for \(x<1/2\) and label 1 for \(x>1/2\). Either label may be assigned at \(x=1/2\). For the indicated choices, the conditional error is \(x\) below \(1/2\) and \(1-x\) above \(1/2\). Since \(X\) is uniform, the risk is

$$ R^*=\int_0^{1/2}x\,dx+\int_{1/2}^1(1-x)\,dx =\frac18+\frac18 =\frac14. $$

The single point \(x=1/2\) has probability zero under the uniform distribution. Assigning either label there leaves the calculated risk unchanged. The two classifiers differ at that point as functions, but their predictions are equal almost surely. Thus this example has pointwise nonuniqueness without distinct Bayes classifiers up to almost-sure equality.

Result: Two Bayes classifiers that differ only on a feature set of probability zero are equal almost surely and have identical risk. If two Bayes classifiers differ on a set of positive probability, then that set must consist, up to a null set, of feature values with multiple posterior maximizers.

Justification. Suppose \(g\) and \(h\) are both Bayes classifiers. By the theorem, both select posterior maximizers with probability one. If they differ on a set of positive probability, then at almost every point in that set both labels \(g(X)\) and \(h(X)\) maximize the posterior probabilities. Since the labels differ, the maximum must be attained by more than one label there. Conversely, if a tie set has positive probability, selecting different maximizing labels on that set (while making the same maximizing choices elsewhere) gives Bayes classifiers that differ with positive probability. With finitely many labels, these choices can be made measurably by partitioning the tie set according to the labels selected. \(\square\)

Common Mistake: Treating a Tie-Breaking Rule as a Unique Answer

A common mistake is to say that a Bayes classifier must choose a particular label whenever posterior probabilities tie—for example, always choosing the smallest label—and then conclude that the Bayes classifier is unique. Choosing the smallest maximizing label is a valid convention for specifying one classifier, but the convention does not make the other maximizing labels suboptimal. At a tie, each maximizing label has conditional risk \(1-\max_k\eta_k(x)\), so any measurable choice among them is equally good.

The correction is to distinguish a rule for resolving ties from the set of risk-minimizing decisions. A tie-breaking convention can make an implementation reproducible. To claim uniqueness up to almost-sure equality, however, one must check whether there are ties on a set of positive probability. Ties only on a null set do not create distinct classifiers in that sense.

Key takeaway: Under zero-one loss, Bayes classifiers choose posterior-maximizing labels. Every such choice has the same conditional risk at a tie, and the population Bayes risk is unchanged. Nonuniqueness matters at the classifier level only when the tied choices differ on a feature set of positive probability.

Check Your Understanding

Use the posterior probabilities and feature distribution in each question to reason about minimizing labels and risk.

  1. At a feature value \(x\), three labels have posterior probabilities \((0.2,0.5,0.3)\). What is the conditional risk of choosing each label, and which label minimizes it?
  2. At a feature value \(z\), two labels have posterior probabilities \((0.4,0.4,0.2)\). Identify all minimizing labels and their conditional risk.
  3. Suppose two Bayes classifiers differ only at a feature value that has probability zero. Are they distinct up to almost-sure equality? Explain.
  4. If a tie set has positive probability, why can choosing different tied labels produce distinct Bayes classifiers with the same risk?
  5. Why does a convention that selects the smallest maximizing label not establish that the Bayes classifier is unique?

Previous

Next

Back to Tutorials
Clinical Biostats