Classification Trees as Cellwise Bayes Decisions

From a Partition to Classification Decisions

A classification tree divides the feature space into regions and assigns one class label to each region. Even with the regions fixed, choosing their labels is a statistical decision: a cell may contain observations from both classes, so its label should reflect their conditional proportions. The key quantity is the probability of class 1 within that cell.

Let $X$ be a feature vector taking values in a standard Borel space $\mathcal X$, and let $Y\in\{0,1\}$ be the class label. Assume their joint distribution is fixed. Write $\eta(x)=P(Y=1\mid X=x)$ for a measurable version of the conditional class probability. A classifier is a measurable function $g:\mathcal X\to\{0,1\}$, and its misclassification risk is $R(g)=P(g(X)\ne Y)$.

Definition: A finite measurable partition $\Pi=\{A_1,\ldots,A_M\}$ of $\mathcal X$ consists of disjoint measurable cells whose union is $\mathcal X$. A classifier is cellwise constant for $\Pi$ if it assigns the same label to every point in each cell. For a cell with $P(X\in A_j)>0$, its conditional class probability is $$ q_j=P(Y=1\mid X\in A_j)=E[\eta(X)\mid X\in A_j]. $$

The equality defining $q_j$ follows from iterated conditioning: the event $X\in A_j$ is determined by $X$, so averaging the conditional probability $\eta(X)$ over that event gives the cell’s class-1 proportion. Cells of probability zero do not affect risk and may be assigned either label.

If a cell is assigned label 0, its conditional error probability is $q_j$. If it is assigned label 1, its conditional error probability is $1-q_j$. Thus the population-optimal cellwise decision is to choose the more probable class in that cell. When $q_j=1/2$, either label has the same conditional risk.

Definition: The cellwise-majority classifier for $\Pi$ assigns label 1 on $A_j$ when $q_j\ge 1/2$, and label 0 when $q_j<1/2$. Any fixed convention at $q_j=1/2$ is valid. This is the risk-minimizing classifier among those that are constant on each cell.

Why the Cellwise Rule Is Optimal Within Its Class

The optimality claim is a direct consequence of comparing the two possible conditional error probabilities on each cell. The theorem also gives the risk of the best classifier constrained by the partition.

Theorem: For a cell $A_j$ of positive probability, the minimum conditional risk among its two constant labels is $\min(q_j,1-q_j)$. Consequently, the minimum risk over all classifiers constant on the cells of $\Pi$ is $$ R_\Pi=\sum_{j:P(X\in A_j)>0}P(X\in A_j)\min(q_j,1-q_j). $$ A cellwise-majority classifier attains this risk.

Proof. Fix a cell $A_j$ with positive probability and consider a classifier that assigns it the constant label $c\in\{0,1\}$. Conditional on $X\in A_j$, an error occurs with probability $P(Y=1\mid X\in A_j)=q_j$ if $c=0$, and with probability $P(Y=0\mid X\in A_j)=1-q_j$ if $c=1$. The smaller of these two values is $\min(q_j,1-q_j)$, attained by a majority label; if they are equal, both labels attain it. Total risk is the sum of the conditional risks weighted by their cell probabilities, because the cells are disjoint and cover the feature space. Choosing a minimizing label separately in every cell therefore attains the displayed sum, and no other cell-constant classifier can have smaller risk. $\square$

The unrestricted Bayes classifier makes its decision using $\eta(x)$ at each feature value, rather than using only the cell average $q_j$. One choice is $g^*(x)=1$ when $\eta(x)\ge 1/2$, and $g^*(x)=0$ otherwise. Its risk is $R^*=E[\min\{\eta(X),1-\eta(X)\}]$. A fixed partition may force a single label across points that lie on opposite sides of the threshold $1/2$; that restriction is the source of its excess risk.

Two Exact Forms of Excess Risk

The first expression for excess risk measures where the cellwise rule disagrees with the pointwise Bayes decision. At a feature value $x$, predicting 0 has conditional error $\eta(x)$, while predicting 1 has conditional error $1-\eta(x)$. The smaller of these is the Bayes conditional error.

Theorem: For any measurable binary classifier $g$, $$ R(g)-R^*=E\!\left[|2\eta(X)-1|\,\mathbf 1\{g(X)\ne g^*(X)\}\right]. $$ The expression is unaffected by the choice of $g^*$ at points where $\eta(X)=1/2$, since the weight there is zero.

Proof. Conditional on $X=x$, the error probability of label 0 is $\eta(x)$, and that of label 1 is $1-\eta(x)$. The Bayes decision selects the smaller of these. If $g(x)=g^*(x)$, the conditional excess error is zero. If they disagree and $\eta(x)>1/2$, the Bayes decision is 1 and the excess from predicting 0 is $\eta(x)-(1-\eta(x))=2\eta(x)-1$. If they disagree and $\eta(x)<1/2$, the Bayes decision is 0 and the excess from predicting 1 is $(1-\eta(x))-\eta(x)=1-2\eta(x)$. In either disagreement case the excess is $|2\eta(x)-1|$. At a tie the difference is zero. Taking expectation over $X$ gives the result. $\square$

For the cellwise-majority rule, the same excess can also be calculated cell by cell. The next identity makes the role of within-cell variation explicit: a cell incurs no excess if its Bayes decision is constant throughout it, but can incur excess if it mixes feature values whose Bayes decisions differ.

Result: Let $g_\Pi$ be a cellwise-majority classifier and let $p_j=P(X\in A_j)>0$. Its excess risk over the unrestricted Bayes risk is $$ R(g_\Pi)-R^*= \frac12\sum_{j:p_j>0}p_j \left( E[|2\eta(X)-1|\mid X\in A_j]-|2q_j-1| \right). $$ Each summand is nonnegative.

Derivation. On cell $A_j$, the cellwise rule has conditional risk $\min(q_j,1-q_j)=(1-|2q_j-1|)/2$. The unrestricted Bayes risk conditional on that cell is $$ E[\min\{\eta(X),1-\eta(X)\}\mid X\in A_j] =\frac{1-E[|2\eta(X)-1|\mid X\in A_j]}{2}. $$ Subtracting the second quantity from the first gives the cell’s conditional excess risk. Multiplying by $p_j$ and summing over cells yields the displayed identity. For nonnegativity, the triangle inequality for conditional expectations gives $$ |2q_j-1| =\left|E[2\eta(X)-1\mid X\in A_j]\right| \le E[|2\eta(X)-1|\mid X\in A_j]. $$ Thus every cell’s contribution is nonnegative.

Worked Calculations

Worked Example: A Discrete Partition with One Mixed Cell

Suppose $X$ takes values $a,b,c$ with probabilities $0.2,0.3,0.5$, respectively, and $\eta(a)=0.9$, $\eta(b)=0.3$, and $\eta(c)=0.6$. Use the partition $A_1=\{a,b\}$, $A_2=\{c\}$. Find the cellwise decisions, their risk, the Bayes risk, and the excess risk.

The first cell has probability $0.2+0.3=0.5$, and its class-1 probability is $$ q_1=\frac{0.2(0.9)+0.3(0.3)}{0.5} =\frac{0.18+0.09}{0.5}=0.54. $$ It receives label 1. In the second cell, $q_2=0.6$, so it also receives label 1. The cellwise risk is therefore $$ R(g_\Pi)=0.5(1-0.54)+0.5(1-0.6)=0.23+0.20=0.43. $$

The Bayes classifier predicts 1 at $a$, 0 at $b$, and 1 at $c$. Its risk is $$ R^*=0.2(1-0.9)+0.3(0.3)+0.5(1-0.6) =0.02+0.09+0.20=0.31. $$ Thus the excess is $0.43-0.31=0.12$. Only $b$ is classified differently by the two rules; its probability times its excess conditional error is $0.3|2(0.3)-1|=0.3(0.4)=0.12$, confirming the disagreement formula.

Worked Example: A Tie Can Still Have Excess Risk

Let $X$ take two values $u,v$, each with probability $1/2$, and let $\eta(u)=0.9$, $\eta(v)=0.1$. Put both values in a single cell. Compute the cellwise and Bayes risks.

The cell class probability is $q=(0.9+0.1)/2=0.5$. The cell is tied, so either constant label has conditional error $0.5$; its risk is $R(g_\Pi)=0.5$. The Bayes classifier predicts 1 at $u$ and 0 at $v$, giving $$ R^*=\tfrac12(1-0.9)+\tfrac12(0.1)=0.05+0.05=0.10. $$ The excess risk is $0.50-0.10=0.40$. The cellwise formula gives the same answer: $E[|2\eta(X)-1|\mid A]=0.8$, whereas $|2q-1|=0$, so the excess is $\tfrac12(0.8-0)=0.4$. A tie in the cell average means the two constant labels perform equally; it does not imply that either matches the pointwise Bayes decisions.

Worked Example: A Continuous Feature and a Boundary-Crossing Cell

Let $X$ be uniform on $[0,1]$, let $\eta(x)=x$, and partition the interval into $A_1=[0,0.4)$ and $A_2=[0.4,1]$. Determine the cellwise rule and compare its risk with the Bayes risk.

The first cell has probability $0.4$, with conditional mean class probability $q_1=(1/0.4)\int_0^{0.4}x\,dx=0.2$, so its label is 0. The second has probability $0.6$, and $$ q_2=\frac{1}{0.6}\int_{0.4}^{1}x\,dx =\frac{(1-0.4^2)/2}{0.6} =\frac{0.42}{0.6}=0.7, $$ so its label is 1. The cellwise risk is the integral of $\eta(x)$ on the first cell plus the integral of $1-\eta(x)$ on the second: $$ R(g_\Pi)=\int_0^{0.4}x\,dx+\int_{0.4}^{1}(1-x)\,dx =0.08+0.18=0.26. $$

The Bayes rule changes from label 0 to label 1 at $x=0.5$, and its risk is $$ R^*=\int_0^{0.5}x\,dx+\int_{0.5}^{1}(1-x)\,dx =0.125+0.125=0.25. $$ The excess is $0.01$. The rules disagree only on $0.4\le x<0.5$, where the excess weight is $1-2x$; indeed $\int_{0.4}^{0.5}(1-2x)\,dx=0.01$.

Interpretation and a Common Pitfall

The partition retains only cell membership when assigning labels. Its decision depends on the average $q_j$, whereas the unrestricted decision depends on the full variation of $\eta(X)$ within the cell. If every point in a cell has the same Bayes label, the cellwise-majority decision agrees with that label, apart from irrelevant ties at $\eta=1/2$. If the cell contains points with Bayes labels on both sides of the threshold, the constant decision may disagree on some points and incur excess risk. The exact formula quantifies that loss rather than treating every cell as equally difficult.

Common pitfall: treating a cell average as a pointwise probability. A learner might compute $q_j\ge 1/2$ and conclude that every feature value in $A_j$ has $\eta(x)\ge 1/2$, so the cellwise rule must be Bayes-optimal there. That reasoning is incorrect: an average above $1/2$ does not prevent some values from lying below $1/2$. The correction is to distinguish the cell-level decision, based on $q_j$, from the pointwise Bayes decision, based on $\eta(x)$. Their disagreement, weighted by $|2\eta(x)-1|$, is precisely the cellwise classifier’s excess risk.

Key takeaway: For binary classification on a fixed partition, the optimal constant label in a cell is its conditional majority class. Its excess risk is exactly the weighted cost of disagreement with the pointwise Bayes rule, or equivalently the gap between the average absolute signal within a cell and the absolute signal of its average.

Check Your Understanding

Use the cellwise and pointwise risk formulas to answer these questions.

If a cell has $q_j=0.35$, which label minimizes its conditional misclassification risk, and what is that risk?
Why can a cell with $q_j=1/2$ have substantial excess risk over the Bayes rule?
State the excess-risk contribution of a cell in terms of $p_j$, $E[|2\eta(X)-1|\mid X\in A_j]$, and $q_j$.
When does a cellwise-constant rule agree with the pointwise Bayes rule throughout a cell, except possibly at ties?
For a feature value where $g$ and $g^*$ disagree and $\eta(x)=0.8$, what is the conditional excess error?