Classification Consistency from Forest Probability Estimates

From Probability Estimates to Class Decisions

A classifier turns information about class probabilities into a label. For a forest, the probabilities are themselves estimated from the training data and may also depend on the forest's random construction. The key link is that a small error in those probabilities limits how much worse the resulting classification risk can be than the Bayes risk. To make that link precise, we must specify whether a risk statement concerns one realized forest or averages over forest randomization.

Let $(X,Y)$ be a new observation, with $X$ taking values in a measurable predictor space and $Y\in\{1,\ldots,K\}$. Write $\eta_k(x)=P(Y=k\mid X=x)$ for a measurable version of the class-probability function. Thus $\sum_{k=1}^K\eta_k(x)=1$ for $P_X$-almost every $x$. A classifier $g$ is a measurable function from predictors to class labels, and its risk is $R(g)=P\{g(X)\ne Y\}$.

Definition: A Bayes classifier is any measurable rule $g^*$ satisfying $g^*(x)\in\arg\max_{1\le k\le K}\eta_k(x)$ for $P_X$-almost every $x$. Its risk $R^*=\inf_g R(g)$ is the Bayes risk. For a classifier $g$, the excess risk is $R(g)-R^*$, which is nonnegative.

Ties in the maximization can be resolved by any fixed measurable rule. Since the conditional probability of a correct decision at $x$, when choosing class $k$, is $\eta_k(x)$, the conditional error is $1-\eta_k(x)$. Consequently, $R(g)-R^*=E_X[\max_k\eta_k(X)-\eta_{g(X)}(X)]$. This identity is the starting point for the probability-estimation bound.

The Plug-in Excess-Risk Bound

Suppose the training data are $D_n$, and let $U_n$ denote any additional forest randomization, such as random feature choices or randomized subsampling. Write $\hat\eta_{n,k}(x;D_n,U_n)$ for the estimated probability of class $k$. A plug-in classifier chooses a class maximizing these estimates. If the estimates tie, fix a measurable tie-breaking rule.

For a realized training data set and a realized forest, abbreviate the estimates by $\hat\eta_k(x)$, and set $j^*\in\arg\max_k\eta_k(x)$ and $\hat j\in\arg\max_k\hat\eta_k(x)$. Then $\hat\eta_{j^*}(x)-\hat\eta_{\hat j}(x)\le 0$, by the definition of $\hat j$. This comparison gives the pointwise result.

Theorem: For any measurable probability estimates and their plug-in classifier $\hat g_n$, conditional on $D_n$ and $U_n$, $$ R(\hat g_n\mid D_n,U_n)-R^* \le 2E_X\!\left[\max_{1\le k\le K} \left|\hat\eta_{n,k}(X;D_n,U_n)-\eta_k(X)\right| \mid D_n,U_n\right]. $$ Here the conditional risk averages over a fresh test pair $(X,Y)$, independent of the training data and forest randomization. No independence among the trees is required for this inequality.

Proof. At a fixed $x$, insert the estimated probabilities between the true probabilities for the Bayes label and the label chosen by the plug-in rule:

\begin{aligned} \eta_{j^*}(x)-\eta_{\hat j}(x) ={}&\bigl(\eta_{j^*}(x)-\hat\eta_{j^*}(x)\bigr) +\bigl(\hat\eta_{j^*}(x)-\hat\eta_{\hat j}(x)\bigr)\\ &+\bigl(\hat\eta_{\hat j}(x)-\eta_{\hat j}(x)\bigr)\\ \le{}&\left|\eta_{j^*}(x)-\hat\eta_{j^*}(x)\right| +\left|\hat\eta_{\hat j}(x)-\eta_{\hat j}(x)\right|\\ \le{}&2\max_{1\le k\le K}|\hat\eta_k(x)-\eta_k(x)|. \end{aligned}

The first inequality uses $\hat\eta_{j^*}(x)-\hat\eta_{\hat j}(x)\le0$; the last holds because both absolute errors are among those in the maximum. The conditional excess-risk identity expresses the left side integrated over $X$. Integrating the pointwise inequality with respect to $P_X$ proves the result. $\square$

The factor of two comes from the possibility that the estimated probability is wrong both for the Bayes label and for the label selected by the estimate. The bound does not require a margin condition separating the largest class probability from the others. It can therefore be useful even when the best class is difficult to distinguish from its competitors.

Worked Example: A Two-Point Predictor Distribution

Let $X$ take values $a$ and $b$, with $P(X=a)=0.7$ and $P(X=b)=0.3$. Suppose there are two classes and $\eta(a)=(0.8,0.2)$, $\eta(b)=(0.45,0.55)$. Consider estimates $\hat\eta(a)=(0.65,0.35)$ and $\hat\eta(b)=(0.52,0.48)$.

At $a$, both the Bayes classifier and the plug-in classifier choose class 1. At $b$, the Bayes classifier chooses class 2, but the plug-in classifier chooses class 1. The Bayes risk is $0.7(0.2)+0.3(0.45)=0.14+0.135=0.275$. The plug-in risk is $0.7(0.2)+0.3(0.55)=0.14+0.165=0.305$. Thus its excess risk is $0.305-0.275=0.030$.

At $a$, the maximum absolute probability error is $\max(|0.65-0.8|,|0.35-0.2|)=0.15$. At $b$, it is $\max(|0.52-0.45|,|0.48-0.55|)=0.07$. The integrated error is $0.7(0.15)+0.3(0.07)=0.105+0.021=0.126$, so the theorem bounds the excess risk by $2(0.126)=0.252$. The bound is valid but conservative: it controls the cost of the probability errors without using the particular locations where those errors change the selected label.

Worked Example: A Multiclass Decision at One Predictor Value

At a fixed predictor value $x$, suppose the three class probabilities are $\eta(x)=(0.50,0.30,0.20)$, and the estimated probabilities are $\hat\eta(x)=(0.32,0.48,0.20)$. The Bayes choice is class 1, whereas the plug-in choice is class 2.

The conditional excess error at this $x$ is $\eta_1(x)-\eta_2(x)=0.50-0.30=0.20$. The absolute errors are $0.18$, $0.18$, and $0$, so their maximum is $0.18$. The pointwise bound gives $0.20\le2(0.18)=0.36$, as required. This verifies the bound for the selected labels even though the estimated probability of class 3 is exact.

Consistency, Including Forest Randomization

For each sample size $n$, define the integrated probability-estimation error for the realized data and forest by $$ A_n(D_n,U_n)=E_X\!\left[ \max_{1\le k\le K}|\hat\eta_{n,k}(X;D_n,U_n)-\eta_k(X)| \mid D_n,U_n\right]. $$ The expectation here is only over the predictor distribution of a fresh test observation. Since the conditional excess risk is also defined for a fixed $D_n,U_n$, the theorem yields the samplewise inequality $0\le R(\hat g_n\mid D_n,U_n)-R^*\le2A_n(D_n,U_n)$.

Consistency consequence: If $A_n(D_n,U_n)\xrightarrow{p}0$ under the joint randomness of the training data and forest, then $R(\hat g_n\mid D_n,U_n)-R^*\xrightarrow{p}0$. If instead the risk is averaged over forest randomization conditional on the training data, then $$ 0\le E_{U_n}[R(\hat g_n\mid D_n,U_n)-R^*\mid D_n] \le 2E_{U_n}[A_n(D_n,U_n)\mid D_n]. $$ In particular, $E_{D_n,U_n}[A_n(D_n,U_n)]\to0$ implies that the expected excess risk tends to zero.

The first implication follows directly from the samplewise inequality: for every $\varepsilon>0$, the event that the excess risk exceeds $\varepsilon$ is contained in the event $A_n>\varepsilon/2$. For the averaged statement, take conditional expectation over $U_n$ in the samplewise bound; the inequality is preserved because expectation preserves order. Taking expectation over $D_n$ then gives expected excess risk at most $2E[A_n]$. Thus the form of consistency conclusion must match the form of probability-estimation convergence being used.

Worked Example: Averaging Over Forest Randomization

Let $X$ be constant, with class probabilities $\eta=(0.6,0.4)$, and fix the training data. Suppose the forest randomization produces $\hat\eta=(0.6,0.4)$ with probability $1/2$ and $\hat\eta=(0.4,0.6)$ with probability $1/2$.

For the first realized forest, the plug-in classifier selects class 1 and has excess risk $0$. Its probability-estimation error is also $0$. For the second realized forest, the classifier selects class 2; its risk is $0.6$, compared with Bayes risk $0.4$, so its excess risk is $0.2$. The maximum probability error for that realization is $0.2$, and the realized bound reads $0.2\le2(0.2)=0.4$.

Averaging over the two forest realizations gives excess risk $0.5(0)+0.5(0.2)=0.1$. The average maximum probability error is $0.5(0)+0.5(0.2)=0.1$, so the averaged bound is $0.1\le2(0.1)=0.2$. This calculation distinguishes a bound for each realized forest from a bound for a risk averaged over randomization.

Why the Conditioning Matters

If the forest is randomized, conditioning only on $D_n$ does not generally fix its estimated probabilities or its classifier. A bound for the risk averaged over forest randomization must therefore also average the probability-estimation error over that randomization. By contrast, once both $D_n$ and $U_n$ are fixed, the risk averages only over a new test observation, so the right side averages only over $X$.

A common mistake is to write a risk averaged over $U_n$ on the left, while putting only $E_X$ of the estimation error on the right and treating that error as if it belonged to a fixed forest. In the preceding example, the risk averaged over the forest is $0.1$, but for the correctly classified realization the unaveraged right side is zero. That is not a valid bound for the averaged risk. The correction is to use either a risk and bound both conditional on $D_n,U_n$, or average both sides over $U_n$ conditional on $D_n$.

For forest probability estimates, earlier consistency results are relevant when they establish convergence of $A_n$, or of its expectation, to zero. The classification conclusion then follows from the plug-in inequality; it does not require a separate argument about which leaves or trees supplied the estimates. The conclusion is about risk approaching the Bayes risk, not necessarily about recovering the Bayes label at every predictor value: when class probabilities are close, small estimation changes can alter a label while incurring little excess risk.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

At a fixed $x$, explain why $\hat\eta_{j^*}(x)-\hat\eta_{\hat j}(x)\le0$, including when estimated probabilities tie.
For two classes, suppose $\eta(x)=(0.7,0.3)$ and $\hat\eta(x)=(0.45,0.55)$. Find the pointwise excess error and verify the pointwise bound.
State the conditioning required for a bound whose left side is the risk of one realized randomized forest.
If the risk is averaged over forest randomization conditional on the training data, what must happen to the probability-error term on the right side?
Why does $A_n\xrightarrow{p}0$ imply conditional excess risk converges to zero in probability?

Classification Consistency from Forest Probability Estimates

What You'll Learn