Leaf Occupancy and Vanishing Within-Leaf Noise

Why Leaf Occupancy Matters

A tree prediction at a query point is often the average of the responses in the leaf containing that point. If a leaf contains many estimation observations, averaging can reduce the effect of response noise. If it contains only one or two, the prediction can remain noisy even when the leaf is geometrically small. The relevant quantity for this part of the prediction is therefore the leaf's occupancy: how many observations contribute to its average.

Occupancy and geometry answer different questions. The count of observations controls how much independent response noise is averaged away. The diameter of the leaf controls how far apart the covariate values within it can be. Neither condition implies the other without additional assumptions on the data distribution and the partition. This tutorial isolates the occupancy calculation; it does not treat occupancy alone as a complete guarantee of predictive accuracy.

Leaf Averages and Their Noise

Definition: Let $x$ be a query point and let $A(x)$ be the leaf of a partition that contains $x$. For an estimation sample $(X_i,Y_i)_{i=1}^n$, the leaf occupancy is $$ N(x)=\sum_{i=1}^n \mathbf{1}\{X_i\in A(x)\}. $$ When $N(x)>0$, the leaf response average is $$ \hat{m}(x)=\frac{1}{N(x)}\sum_{i:X_i\in A(x)}Y_i. $$

To isolate response noise, write $Y_i=m(X_i)+\varepsilon_i$, where $m(X_i)=E[Y_i\mid X_i]$, $E[\varepsilon_i\mid X_i]=0$, and $\operatorname{Var}(\varepsilon_i\mid X_i)\leq \sigma^2$. The average separates into a within-leaf average of regression means and an average of errors:

\hat{m}(x) = \frac{1}{N(x)}\sum_{i:X_i\in A(x)}m(X_i) + \frac{1}{N(x)}\sum_{i:X_i\in A(x)}\varepsilon_i.

Call the second term the leaf noise average. The conditions used below are important: the partition must be honest with respect to the estimation responses, meaning its construction does not use those responses, and the errors must be conditionally independent across observations given the covariates and partition, with conditional means zero. We condition on the covariates and the partition, so the set of indices in the leaf is fixed. Honesty is what permits this response-noise calculation without selecting observations based on their errors.

Theorem: Suppose $N(x)=m_0>0$, the partition is honest with respect to the estimation responses, and, conditional on the covariates and partition, the errors in the leaf are independent with mean zero and variances at most $\sigma^2$. Then $$ \operatorname{Var}\left( \left. \frac{1}{m_0}\sum_{i:X_i\in A(x)}\varepsilon_i \right| X_1,\ldots,X_n,\ A \right) \leq \frac{\sigma^2}{m_0}. $$

Proof. Conditional on the covariates and partition, exactly $m_0$ indices contribute, and their errors have conditional mean zero. Conditional independence makes every cross-covariance between distinct errors equal to zero. Therefore the variance of their average is

\begin{aligned} \operatorname{Var}\left( \left. \frac{1}{m_0}\sum_{i:X_i\in A(x)}\varepsilon_i \right| X_1,\ldots,X_n,\ A \right) &= \frac{1}{m_0^2} \sum_{i:X_i\in A(x)} \operatorname{Var}(\varepsilon_i\mid X_1,\ldots,X_n,A)\\ &\leq \frac{1}{m_0^2}\,m_0\sigma^2 =\frac{\sigma^2}{m_0}. \end{aligned}

Thus the conditional variance of the noise average decreases at least at the inverse-occupancy rate. The result concerns only the noise average, conditional on the covariates and partition. It is not, by itself, a bound on the full prediction error or on variation caused by changing the partition. $\square$

Worked Example: Computing a Leaf's Conditional Noise Variance

A fixed honest leaf contains four estimation observations. Conditional on their covariates and the partition, their independent errors have variances $1$, $4$, $1$, and $2$. Find the variance of the leaf noise average and compare it with the uniform-variance bound.

The noise average is $(\varepsilon_1+\varepsilon_2+\varepsilon_3+\varepsilon_4)/4$. By conditional independence, its variance is the sum of the four error variances divided by $4^2$:

\operatorname{Var}\left( \left.\frac{\varepsilon_1+\varepsilon_2+\varepsilon_3+\varepsilon_4}{4} \right| X_1,\ldots,X_4,A \right) = \frac{1+4+1+2}{16} = \frac{8}{16} = 0.5.

The largest individual variance is $\sigma^2=4$, so the theorem's uniform bound is $4/4=1$. The calculated variance, $0.5$, satisfies that bound. The bound need not be exact: it allows every observation to have the largest permitted variance, even though only one of these four does.

When Occupancy Is Random

In a random sample, the number of observations in a particular leaf is itself random. A useful benchmark is a fixed region $A$ with probability $p=P(X\in A)>0$, independent of the estimation responses. If $X_1,\ldots,X_n$ are independent draws from the same distribution, then its occupancy $N=\sum_{i=1}^n\mathbf{1}\{X_i\in A\}$ has a binomial distribution with parameters $n$ and $p$. A variance bound involving $1/N$ must be treated carefully: $N$ can equal zero, and even when the average is defined, the expected inverse count is not simply the inverse of the expected count.

Result: If $N\sim\operatorname{Binomial}(n,p)$, then $$ E\left[\left.\frac{1}{N}\right|N>0\right] \leq \frac{2\{1-(1-p)^{n+1}\}} {(n+1)p\{1-(1-p)^n\}}. $$ In particular, if $p=p_n$ and $np_n\to\infty$, the right-hand side tends to zero.

Proof. For every integer $k\geq 1$, $1/k\leq 2/(k+1)$. Consequently,

E\left[\left.\frac{1}{N}\right|N>0\right] = \frac{E[\mathbf{1}\{N>0\}/N]}{P(N>0)} \leq \frac{2E[1/(N+1)]}{1-(1-p)^n}.

To evaluate the expectation in the numerator, expand the binomial probabilities and use $\binom{n}{k}/(k+1)=\binom{n+1}{k+1}/(n+1)$:

\begin{aligned} E\left[\frac{1}{N+1}\right] &=\sum_{k=0}^n\frac{1}{k+1}\binom{n}{k}p^k(1-p)^{n-k}\\ &=\frac{1}{(n+1)p} \sum_{j=1}^{n+1}\binom{n+1}{j}p^j(1-p)^{n+1-j}\\ &=\frac{1-(1-p)^{n+1}}{(n+1)p}. \end{aligned}

Substitution gives the claimed bound. Finally, when $np_n\to\infty$, $(1-p_n)^n\leq e^{-np_n}\to 0$, and also $(1-p_n)^{n+1}\to0$. The bound is therefore asymptotic to $2/\{(n+1)p_n\}$, which tends to zero. $\square$

Combining this result with the conditional variance theorem shows why growing occupancy is useful. Conditional on a nonempty leaf, the expected conditional variance of its noise average is at most $\sigma^2 E[1/N\mid N>0]$. If $np_n\to\infty$, this upper bound vanishes. The condition also ensures that the probability of an empty leaf, $(1-p_n)^n$, vanishes. These statements concern a fixed region or a region independent of the estimation responses; response-adaptive selection requires additional care.

Worked Example: A Random Leaf with Mean Occupancy Ten

Suppose a fixed leaf has probability $p=0.1$ under the covariate distribution, and the estimation sample has size $n=100$. Assume the conditional error variance is at most $9$. Bound the expected conditional noise variance given that the leaf is nonempty.

The occupancy is binomial with mean $np=10$. The inverse-occupancy result gives

\begin{aligned} E\left[\left.\frac{1}{N}\right|N>0\right] &\leq \frac{2(1-0.9^{101})}{101(0.1)(1-0.9^{100})}\\ &\approx \frac{2(0.9999761)}{10.1(0.9999734)} \approx 0.1980. \end{aligned}

The conditional variance theorem then bounds the expected conditional noise variance by $9(0.1980)\approx1.782$. This is a conservative bound, not an exact variance calculation. The probability the leaf is empty is $0.9^{100}\approx0.0000266$, so conditioning on a nonempty leaf excludes a small-probability event in this example.

Occupancy Is Not Leaf Diameter

The occupancy calculations use the probability mass of the leaf, not its diameter. A leaf with large probability mass can contain many observations while still spanning a substantial range of covariate values. Conversely, a geometrically narrow leaf can have very little probability mass and receive few observations. The next examples make the distinction explicit for a uniform covariate on $[0,1]$, where the probability of an interval equals its length.

Worked Example: Many Observations Without Shrinking Diameter

Let $X$ be uniform on $[0,1]$, and consider the fixed leaf $A=[0,1/2]$ for every sample size $n$. Its diameter is $1/2$, which does not shrink. Its probability is $p=1/2$, so its occupancy has mean $n/2$.

If the errors are independent with conditional variance at most $1$, the conditional noise variance is at most $1/N$ whenever $N>0$. The probability of an empty leaf is $2^{-n}$, which tends to zero. Moreover, the binomial inverse-occupancy bound applies with $p=1/2$, and its upper bound tends to zero as $n\to\infty$. Thus noise in the leaf average can vanish even though the leaf diameter stays equal to $1/2$. This example says nothing about whether the average of the regression means in that leaf approximates $m(x)$ well for each query point.

Worked Example: Shrinking Diameter Without Growing Occupancy

Again let $X$ be uniform on $[0,1]$, but now take the leaf $A_n=[0,n^{-2}]$. Its diameter is $n^{-2}$, which tends to zero, while its probability is $p_n=n^{-2}$. The expected occupancy among $n$ observations is therefore

E[N]=np_n=\frac{1}{n}\longrightarrow 0.

In fact, the probability that the leaf contains even one observation is bounded by its expected count:

P(N\geq1)\leq E[N]=\frac{1}{n}\longrightarrow0.

So this leaf becomes narrower while being empty with probability tending to one. Its diameter alone cannot ensure that a response average exists, let alone that its noise variance vanishes. A partitioning procedure could avoid this particular mismatch, but such a guarantee would require assumptions beyond shrinking diameter.

What the Bound Does—and Does Not—Control

For a nonempty leaf, increasing occupancy reduces the response-noise variance of an equal-weight average under the stated conditional independence and variance assumptions. With random occupancy, a condition such as $np_n\to\infty$ makes the typical count large enough for the expected inverse count to vanish. This is the precise sense in which growing leaf occupancy controls within-leaf noise.

The result does not control the variation among the values $m(X_i)$ inside the leaf. Those values contribute to the leaf average even when every response error is zero. Nor does the conditional calculation account for variation in the partition or for dependence among errors. If the estimation responses are used to choose the leaf, conditioning on that choice may change the error distribution among selected observations; the honest-sample argument no longer applies automatically.

A common mistake is to treat a growing total number of leaves as proof that each leaf has high occupancy, or to treat a shrinking leaf diameter as proof that its response average has low variance. Neither follows. What enters the noise bound is the number of estimation observations in the particular query leaf. Geometry and occupancy are separate conditions: localization concerns the region's covariate values, while noise reduction concerns how many independent responses are averaged there.

Key takeaway: For an honest leaf average with conditionally independent errors of variance at most $\sigma^2$, the conditional response-noise variance is at most $\sigma^2/N(x)$. A growing occupancy can make this term vanish; shrinking leaf diameter alone does not guarantee it.

Check Your Understanding

Try to answer each question using the assumptions and distinctions developed above.

A leaf contains $m_0$ observations with independent errors of variance at most $v$. What is the conditional variance bound for their average, and which assumption eliminates cross-covariance terms?
For $N\sim\operatorname{Binomial}(n,p)$, why must an inverse-occupancy calculation address the event $N=0$?
If $np_n\to\infty$, what happens to the probability of an empty fixed leaf and to the bound on expected inverse occupancy given a nonempty leaf?
Can a fixed leaf with nonshrinking diameter have vanishing response-noise variance as the sample grows? Explain using its probability mass and occupancy.
Why does shrinking diameter fail to guarantee a low-noise leaf average? Give the role of the leaf's probability mass.
Name one source of prediction variation that the conditional response-noise bound does not control.