Random Forests and Kernels
Ruoqing Zhu
Last Updated: October 13, 2026
Roughly speaking, random forests (Breiman 2001) are CART models fitted in parallel with some randomness. There are several main components:
- Bootstrapping of data for each tree using the Bagging idea (Breiman 1996), and using the averaged result (for regression) or majority voting (for classification) of all trees as the prediction.
- At each internal node, we may not consider all variables. Instead, we consider
mtryrandomly selected variables to search for the best split. This idea was inspired by Ho (1998). - For each tree, we will not perform pruning. Instead, we simply stop when the internal node contains no more than
nodesizenumber of observations.
Later on, there were various versions of random forests that attempt to improve the performance, from both computational and theoretical perspectives. We will introduce them later.
1 Bagging Predictors
CART models may have difficulty dealing with non-axis-aligned decision boundaries. This can be seen from the example below, in a two-dimensional case. The idea of Bagging is that we can fit many CART models, each from a Bootstrap sample, i.e., sample with replacement from the original \(n\) observations. The reason that Breiman considered bootstrap samples is because they can approximate the original distribution that generates the data. But the end result is that since each tree may be slightly different from each other, when we stack them, the decision boundary can be smoother.
# generate some data
set.seed(2)
n = 1000
x1 = runif(n, -1, 1)
x2 = runif(n, -1, 1)
y = rbinom(n, size = 1, prob = ifelse((x1 + x2 > -0.5) & (x1 + x2 < 0.5) , 0.8, 0.2))
xgrid = expand.grid(x1 = seq(-1, 1, 0.01), x2 = seq(-1, 1, 0.01))Let’s compare the decision rule of CART and Bagging. For CART, the decision line has to be aligned to an axis. For Bagging, we use a total of 200 trees, specified by nbagg in the ipred package.
# fit CART
library(rpart)
rpart.fit = rpart(as.factor(y)~x1+x2, data = data.frame(x1, x2, y))
# we could fit a different tree using a bootstrap sample
# rpart.fit = rpart(as.factor(y)~x1+x2, data = data.frame(x1, x2, y)[sample(1:n, n, replace = TRUE), ])
pred = matrix(predict(rpart.fit, xgrid, type = "class") == 1, 201, 201)
contour(seq(-1, 1, 0.01), seq(-1, 1, 0.01), pred, levels=0.5, labels="",axes=FALSE)
points(x1, x2, col = ifelse(y == 1, "deepskyblue", "darkorange"), pch = 19, yaxt="n", xaxt = "n")
points(xgrid, pch=".", cex=1.2, col=ifelse(pred, "deepskyblue", "darkorange"))
box()
title("CART")
# fit Bagging
library(ipred)
bag.fit = bagging(as.factor(y)~x1+x2, data = data.frame(x1, x2, y), nbagg = 200, ns = 400)
pred = matrix(predict(prune(bag.fit), xgrid) == 1, 201, 201)
contour(seq(-1, 1, 0.01), seq(-1, 1, 0.01), pred, levels=0.5, labels="",axes=FALSE)
points(x1, x2, col = ifelse(y == 1, "deepskyblue", "darkorange"), pch = 19, yaxt="n", xaxt = "n")
points(xgrid, pch=".", cex=1.2, col=ifelse(pred, "deepskyblue", "darkorange"))
box()
title("Bagging")
2 Random Forests
Random forests are equipped with this bootstrapping strategy, but also with other randomness and mechanisms. A random forest can be controlled by several key parameters:
ntree: Number of trees, which mainly controls the stability. We typically want to fit a large number of trees.sampsize: How many samples to use when fitting each tree. In practice, we often use the training sample size if sampled with replacement.mtry: Number of randomly sampled variables to consider at each internal node. This needs to be tuned for adaptiveness to sparse signals (largemtry) or highly correlated features (smallmtry).nodesize: Stop splitting when the node sample size is no larger thannodesize. This works similarly to \(k\) in a KNN model. However, its effect can be greatly affected by other tuning parameters.
Using the randomForest package, we can fit the model. It is difficult to visualize this when p > 2. But we can look at the testing error.
# generate some data with larger p
set.seed(2)
n = 1000
p = 10
X = matrix(runif(n*p, -1, 1), n, p)
x1 = X[, 1]
x2 = X[, 2]
y = rbinom(n, size = 1, prob = ifelse((x1 + x2 > -0.5) & (x1 + x2 < 0.5), 0.8, 0.2))
xgrid = expand.grid(x1 = seq(-1, 1, 0.01), x2 = seq(-1, 1, 0.01))
# fit random forests with a selected tuning
library(randomForest)
## randomForest 4.7-1.2
## Type rfNews() to see new features/changes/bug fixes.
rf.fit = randomForest(X, as.factor(y), ntree = 1000,
mtry = 7, nodesize = 10, sampsize = 800)Instead of generating a set of labels for testing samples, let’s directly compare with the “true” decision rule, the Bayes rule.
# the testing data
Xtest = matrix(runif(n*p, -1, 1), n, p)
# the Bayes rule
BayesRule = ifelse((Xtest[, 1] + Xtest[, 2] > -0.5) &
(Xtest[, 1] + Xtest[, 2] < 0.5), 1, 0)
mean( (predict(rf.fit, Xtest) == "1") == BayesRule )
## [1] 0.7853 Random Forests and Kernel Weights
Random forests are widely viewed as a black-box prediction tool. They average many trees, each producing a piecewise constant fit. However, at a deeper level, every random forest predictor can be viewed as an (adaptive) kernel method. The idea of this kernel view was originally explored in Breiman (2000). More connections are explored in Lin and Jeon (2006), Scornet (2016), Athey et al. (2019) and many other papers. Here we provide a brief overview of this perspective.
A tree-induced kernel is defined as follows. Consider a single tree \(\cT\) built on the training data \(\{(X_i, Y_i)\}_{i=1}^n\), with the collection of terminal nodes \(\mathcal{L}=\{L_q:q=1,\ldots,T\}\). For any target point, if it falls into the terminal node \(L_q\), then the prediction is the average of outcomes of training points in the same node \(L_q\), i.e.,
\[ \frac{1}{n_{L_q}} \sum_{i: X_i \in L_q} Y_i = \sum_{i=1}^n \frac{1(X_i \in L_q)}{n_{L_q}} Y_i \]
where \(n_{L_q} = \sum_{i=1}^n 1(X_i \in L_q)\) is the number of training points in node \(L_q\). Hence, for any target point \(x\), a tree model predicts by searching for the terminal node it falls into and then using the node average. This can be expressed as a weighted average of all training outcomes
\[ \begin{aligned} \hat{f}_\cT(x) &= \sum_{i=1}^n \color{darkorange}{\sum_{q=1}^T \frac{1(X_i \in L_q)}{n_{L_q}} 1(x \in L_q)} Y_i \\ &= \sum_{i=1}^n \color{darkorange}{w_i(x)} Y_i \end{aligned} \]
And the forest prediction is
\[ \hat{f}_{RF}(x) = \frac{1}{B} \sum_{b=1}^B \hat{f}_{\cT_b}(x) = \sum_{i=1}^n \left( \frac{1}{B} \sum_{b=1}^B w_i^{(b)}(x) \right) Y_i. \]
in which \(\frac{1}{B} \sum_{b=1}^B w_i^{(b)}(x)\) can be regarded as the aggregated forest weight.
4 Random Forest Induced Kernel
In fact, we can also define the corresponding kernel function of a tree. For any two points \(x, z \in \RR^p\),
\[ K_\cT(x, z) = \sum_{q = 1}^T \frac{1}{n_{L_q}} 1(x \in L_q) 1(z \in L_q) \]
For \(x \in L_q\) with \(n_{L_q}>0\), the denominator \(n_{L_q}\) measures how much training data the node contains. More precisely,
\[ P_n(L_q) = \frac{n_{L_q}}{n} \]
is its empirical probability mass. Dividing by \(n_{L_q}\) gives equal weights to observations in the node, with total weight one.
This also connects tree prediction with a uniform kernel. For a rectangular node with finite, positive volume \(|L_q|\), define
\[ u_q(z) = \frac{1(z \in L_q)}{|L_q|}. \]
For \(x \in L_q\), kernel regression using \(u_q\) gives the same node average. To see this, the factor \(1/|L_q|\) appears in both the numerator and denominator and cancels:
\[ \begin{aligned} \hat{m}(x) &= \frac{\sum_{i=1}^n u_q(X_i)Y_i}{\sum_{i=1}^n u_q(X_i)} \\ &= \frac{\frac{1}{|L_q|}\sum_{i=1}^n 1(X_i \in L_q)Y_i} {\frac{1}{|L_q|}\sum_{i=1}^n 1(X_i \in L_q)} \\ &= \frac{\sum_{i=1}^n 1(X_i \in L_q)Y_i}{\sum_{i=1}^n 1(X_i \in L_q)} \\ &= \frac{1}{n_{L_q}}\sum_{i:X_i \in L_q}Y_i \\ &= \hat{f}_\cT(x). \end{aligned} \]
Thus a tree can be understood as a uniform-kernel smoother whose neighborhood is the leaf containing \(x\). The leaf’s coordinate widths act as adaptive bandwidths, although the leaf need not be centered at \(x\). This interpretation does not require uniformly distributed covariates: the node volume defines the uniform kernel, while the observed node count normalizes the regression weights.
The tree-induced kernel \(K_\cT\) is a positive definite kernel that is equivalent to the feature map
\[ \Phi_\cT(x) = \bigg( \frac{1(x \in L_1)}{\sqrt{n_{L_1}}}, \ldots, \frac{1(x \in L_T)}{\sqrt{n_{L_T}}} \bigg)^\top \]
And for random forests, the aggregated kernel is simply the average of individual tree kernels
\[ K_{RF}(x, z) = \frac{1}{B} \sum_{b=1}^B K_{\cT_b}(x, z), \]
which is a valid positive definite kernel as well. However, it is worth pointing out that a random forest is not an RKHS method at all since it does not optimize any regularized loss in an RKHS space. Instead the kernel is learned in an adaptive way from the data, and the kernel weights are not learned through a global optimization problem.
5 Adaptiveness of Random Forest Kernel
However, random forests can adapt pretty well in a high-dimensional, especially sparse setting. This is because of the greedy splitting rule selection. The adaptiveness works in a way that tends to ignore covariates that are not effective in explaining the variation of \(Y\). Hence, this makes the model similar to a kernel method on a low-dimensional space. The following example illustrates this effect in a two-dimensional case. We can see that the outcome is only related to the first dimension. Hence, when setting mtry = 2, we will almost always prefer to split on the first variable, making its neighbors very close to the target prediction point \((0, 0)^T\).
library(RLT)
##
## Attaching package: 'RLT'
## The following object is masked from 'package:randomForest':
##
## importance
# generate some data
set.seed(2)
n = 400
x1 = runif(n, -1, 1)
x2 = runif(n, -1, 1)
y = 2*x1 + 0.2*rnorm(n)
xgrid = expand.grid(x1 = seq(-1, 1, 0.01), x2 = seq(-1, 1, 0.01))
# fit forest
rf.fit = RLT(x = data.frame(x1, x2), y = y, model = "regression",
mtry = 2, nmin = 40, param.control = list(resample.track = TRUE))
# calculate kernel
rf.kernel = forest.kernel(rf.fit, X1 = data.frame("x1" = 0, "x2" = 0),
X2 = data.frame(x1, x2), vs.train = TRUE)$Kernel
# kernel weights
plot(x1, x2, pch = 19, yaxt="n", xaxt = "n", cex = (rf.kernel + 1)^0.15 - 0.7)
points(0, 0, col = "red", pch = 18, cex = 3)
The tuning parameter mtry has a very strong effect on controlling this greediness. When mtry is large, we will be very greedy on selecting the true signal variable to split. In a high-dimensional setting, we may only use a few variables before reaching a terminal node, making the model rely on only a few dimensions. When we use a very small mtry, the model behaves similarly to a regular kernel estimator with a good smoothing (small variance) property. However, since it is effectively randomly selecting a dimension to split, the bandwidth on each dimension would also be similar but large since we can only afford a few splits before the node size becomes too small. This can be seen from the following example, with mtry = 1.
# fit forest
rf.fit = RLT(x = data.frame(x1, x2), y = y, model = "regression",
mtry = 1, nmin = 40, param.control = list(resample.track = TRUE))
# calculate kernel
rf.kernel = forest.kernel(rf.fit, X1 = data.frame("x1" = 0, "x2" = 0),
X2 = data.frame(x1, x2), vs.train = TRUE)$Kernel
# kernel weights
plot(x1, x2, pch = 19, yaxt="n", xaxt = "n", cex = (rf.kernel + 1)^0.15 - 0.7)
points(0, 0, col = "red", pch = 18, cex = 3)
6 Variable Splitting and Local Bias
The previous example suggests that splitting on some variables is more useful than splitting on others. To understand why, we can first look at the approximation made within a single leaf. Let \(m(x)=\mathbb E[Y\mid X=x]\) be the regression function. For a fixed leaf \(L\), its population prediction is
\[ m_L=\mathbb E[Y\mid X\in L] =\mathbb E[m(X)\mid X\in L]. \]
At a point \(x\in L\), the approximation bias is \(m_L-m(x)\). Here we use the population mean to isolate the error from approximating a varying regression function by a constant. Estimating this mean from the training observations introduces additional sampling error.
For a simple illustration, suppose the covariates are independent and uniformly distributed on a rectangular domain, and the regression function is linear:
\[ m(x)=\sum_{j=1}^p\beta_j x_j. \]
Consider a rectangular leaf \(L=\prod_{j=1}^p[a_j,b_j]\). Let \(c_j=(a_j+b_j)/2\) be its midpoint and \(d_j=b_j-a_j\) be its width along coordinate \(j\). Conditional on \(X\in L\), the coordinates remain independent and uniform on their respective intervals. Hence,
\[ \mathbb E[X_j\mid X\in L]=c_j, \qquad \operatorname{Var}(X_j\mid X\in L)=\frac{d_j^2}{12}, \]
and the population prediction is \(m_L=\sum_{j=1}^p\beta_j c_j\). We can now calculate the squared approximation bias averaged over the leaf. The cross terms vanish because the centered coordinates are conditionally independent and have mean zero:
\[ \begin{aligned} \mathbb E[(m(X)-m_L)^2\mid X\in L] &=\mathbb E\!\left[\left\{\sum_{j=1}^p\beta_j(X_j-c_j)\right\}^2\,\middle|\,X\in L\right]\\ &=\sum_{j=1}^p\beta_j^2\mathbb E[(X_j-c_j)^2\mid X\in L]\\ &=\frac{1}{12}\sum_{j=1}^p\beta_j^2d_j^2. \end{aligned} \]
This gives a simple interpretation of the within-leaf approximation error. A wide leaf is problematic along a direction where the regression function changes substantially. In this example, a direction with \(\beta_j=0\) makes no contribution to the approximation error, even if the leaf remains wide in that direction.
When we split a node along coordinate \(j\), each child has a smaller \(d_j\), while the widths along the other coordinates remain the same. Thus the contribution \(\beta_j^2d_j^2/12\) becomes smaller. This creates a natural competition among the variables: a variable with a larger current contribution offers more room to reduce approximation error, but as we keep splitting along that direction, its remaining contribution decreases and another relevant variable may become more useful to split. The choice depends on both the strength of the signal and the current shape of the node.
However, further splitting also leaves fewer observations for estimating each node mean, so reducing approximation bias can come at the cost of greater estimation variance.
7 Mondrian Process and Forests
We have seen how the shape of a leaf affects local approximation error. To study the similarity produced by an entire random partition, we can calculate the probability that two points remain in the same leaf. A variant of random forests, called the Mondrian forests (Lakshminarayanan et al. 2014), uses a continuous-time random partition (Mondrian process) on axis-aligned rectangles (Roy and Teh 2008). Here we consider a Mondrian process on \([0,1]^p\). The partition is generated using the geometry of the nodes, without using the observed outcomes. The Mondrian process uses the following mechanism to grow each tree:
- Fix a budget parameter \(\lambda>0\), also called the lifetime of the Mondrian process.
- Initialize a global time \(t=0\) and the leaf set \(\mathcal{L} = \{[0,1]^p\}\).
- Iterate the following splitting process:
- For each current leaf \(L=\prod_{j=1}^p [a_j,b_j] \in \mathcal{L}\), define its \(\ell_1\) linear size \[ r(L)\;=\;\mathrm{lin}(L)\;=\;\sum_{j=1}^p (b_j-a_j). \]
- Draw independent waiting times \(E_L \sim \mathrm{Exp}(r(L))\) for all \(L\in\mathcal{L}\). Select the leaf with the smallest waiting time, and let \(\delta_t =\min_{L\in\mathcal{L}} E_L\).
- If \(t+\delta_t>\lambda\), stop without splitting. Otherwise, update the global time \(t \leftarrow t+\delta_t\).
- For the selected leaf \(L\), draw a split coordinate \(j\) with probability \((b_j-a_j)/r(L)\), and draw a split location uniformly on \([a_j,b_j]\).
- Split \(L\) into two children at this location and update the leaf set. Points on a split boundary are assigned to one child using a fixed convention.
Here \(\mathrm{Exp}(r)\) uses the rate parameterization, so \(\mathbb E[E_L]=1/r(L)\). A leaf with a larger linear size tends to split sooner. The waiting times are measured from the current global time \(t\), so the next split occurs at \(t+\delta_t\). In particular, the lifetime controls how long we run the process; it does not prescribe a fixed number of leaves.
Interestingly, the infinite-forest kernel associated with the probability of sharing a leaf can be computed exactly (Balog et al. 2016). To specify this kernel, let \(\cT_\lambda\) be a Mondrian tree stopped at lifetime \(\lambda\), and define
\[ \begin{aligned} J_\lambda(x,z) &=\mathbf 1\{x \text{ and } z \text{ are in the same leaf of }\cT_\lambda\},\\ K_{\infty,\lambda}(x,z) &=\mathbb E[J_\lambda(x,z)] =\Pr(x \text{ and } z \text{ are in the same leaf at time }\lambda). \end{aligned} \]
The expectation is over the random partitions, with \(x,z\in[0,1]^p\) fixed. We do not need a distributional assumption on the training covariates for this calculation. Recall that the earlier prediction kernel \(K_\cT(x,z)\) also contains the factor \(1/n_{L_q}\). The exact Laplace expression below applies to the same-leaf kernel; it does not directly give the kernel with those additional leaf-size weights.
The intuition of the proof is that the rate of separating two fixed points stays the same as the rest of the tree evolves. We will first explain the exponential clocks, then calculate this separation rate, and finally obtain the probability that the points remain together. To be more specific, let
\[ C_{xz}=\prod_{j=1}^p[\min\{x_j,z_j\},\max\{x_j,z_j\}], \]
be the rectangle spanned by \(x\) and \(z\). Let \(d_j=|x_j-z_j|\) be the gap along dimension \(j\), and let \(s=\|x-z\|_1=\sum_{j=1}^p d_j\) be the linear size of \(C_{xz}\). We first consider \(x\ne z\), so \(s>0\). When \(x=z\), the points are always in the same leaf and the kernel is 1.
First, we recall some properties of exponential distributions. Conditional on the current tree, define the total splitting rate
\[ R=\sum_{L\in\mathcal{L}}r(L). \]
The next split occurs when the first of the independent leaf clocks rings. Hence, for \(u\geq 0\),
\[ \begin{aligned} \Pr(\delta_t>u\mid\text{current tree}) &=\Pr(E_L>u\text{ for every }L\in\mathcal{L}\mid\text{current tree})\\ &=\prod_{L\in\mathcal{L}}e^{-r(L)u}\\ &=e^{-Ru}. \end{aligned} \]
Thus \(\delta_t\sim\mathrm{Exp}(R)\) conditional on the current tree. We can also calculate the probability that a particular leaf \(L\) is selected. Its clock must ring at some waiting time \(v\), while all the other clocks have not yet rung:
\[ \begin{aligned} &\Pr(L\text{ is selected},\ \delta_t\leq u\mid\text{current tree})\\ &\quad=\int_0^u r(L)e^{-r(L)v}\prod_{L'\ne L}e^{-r(L')v}\,dv\\ &\quad=\int_0^u r(L)e^{-Rv}\,dv\\ &\quad=\frac{r(L)}{R}(1-e^{-Ru}). \end{aligned} \]
Letting \(u\to\infty\) gives \(\Pr(L\text{ is selected}\mid\text{current tree})=r(L)/R\). The factorization also shows that the selected leaf and the waiting time are conditionally independent given the current tree.
Another important property is memorylessness. For \(E\sim\mathrm{Exp}(r)\) and \(a,u\geq 0\),
\[ \Pr(E>a+u\mid E>a) =\frac{e^{-r(a+u)}}{e^{-ra}} =e^{-ru}. \]
If a clock has not rung by time \(a\), its remaining waiting time has the same exponential distribution. This explains why the algorithm can redraw the clocks of unchanged leaves after another leaf splits. Equivalently, we could leave those clocks running and start new clocks only for the two new children.
Now suppose that \(x\) and \(z\) have not yet been separated, and let \(L^\ast\) be their shared leaf. Since the leaves are rectangles, \(L^\ast\) also contains the entire block \(C_{xz}\). Only a split of \(L^\ast\) can separate the two points. Given that \(L^\ast\) splits, we first choose a coordinate and then a cut location. Summing over the possible coordinates gives
\[ \begin{aligned} &\Pr(\text{separate }x,z\mid L^\ast\text{ splits},\text{ current tree})\\ &\quad=\sum_{j=1}^p \underbrace{\frac{b_j-a_j}{r(L^\ast)}}_{\text{choose coordinate }j} \underbrace{\frac{d_j}{b_j-a_j}}_{\text{cut between }x_j\text{ and }z_j}\\ &\quad=\frac{\sum_{j=1}^p d_j}{r(L^\ast)} =\frac{s}{r(L^\ast)}. \end{aligned} \]
The side lengths cancel because longer coordinates are more likely to be selected, but a uniform cut along a longer coordinate is less likely to fall inside a fixed gap. Multiplying this separation probability by the rate of splitting \(L^\ast\), we obtain
\[ \underbrace{r(L^\ast)}_{\text{leaf splitting rate}} \times \underbrace{\frac{s}{r(L^\ast)}}_{\text{separation probability per split}} =s. \]
This is the key cancellation. As the shared leaf shrinks, a cut becomes more likely to separate \(x\) and \(z\), but the leaf’s splitting clock becomes slower. For example, in one dimension, suppose the gap is \(0.2\). A containing interval of length 1 has splitting rate 1 and separation probability \(0.2\) per split. If a nonseparating cut leaves a containing interval of length \(0.5\), these become \(0.5\) and \(0.2/0.5=0.4\). The separation rate is still \(0.2\) in both cases.
We can obtain the same result from the competing clocks of the entire tree. The conditional probability that the next split separates the pair is
\[ \Pr(\text{next split separates }x,z\mid\text{current tree}) =\frac{r(L^\ast)}{R}\cdot\frac{s}{r(L^\ast)} =\frac{s}{R}. \]
Here we use the multiplication rule for conditional probabilities: first select the shared leaf, then make a separating cut within it. Since splits anywhere in the tree occur at rate \(R\), the separation rate is again \(R\cdot(s/R)=s\). Although \(R\) changes as the tree grows, this separation rate depends only on the fixed gaps between \(x\) and \(z\).
To turn this rate into a probability of remaining together, let \(T\) be the first separation time. For this calculation, we can imagine continuing the process beyond \(\lambda\) and then ask whether \(T>\lambda\). Conditional on the current tree at time \(t\) and on \(T>t\), the remaining waiting time for the shared leaf to split is \(W\sim\mathrm{Exp}(r(L^\ast))\). This is a waiting time from now, so a split in the next \(\Delta t\) corresponds to \(W\leq\Delta t\). Consequently,
\[ \begin{aligned} &\Pr(t<T\leq t+\Delta t\mid T>t,\text{ current tree})\\ &\quad=\Pr(W\leq\Delta t\mid\text{current tree}) \frac{s}{r(L^\ast)}+O((\Delta t)^2)\\ &\quad=(1-e^{-r(L^\ast)\Delta t})\frac{s}{r(L^\ast)}+O((\Delta t)^2)\\ &\quad=\left\{r(L^\ast)\Delta t+O((\Delta t)^2)\right\} \frac{s}{r(L^\ast)}+O((\Delta t)^2)\\ &\quad=s\Delta t+O((\Delta t)^2). \end{aligned} \]
The remainder accounts for two or more successive splits affecting the pair during this short interval. Every leaf in \([0,1]^p\) has splitting rate at most \(p\), so the probability of two such successive splits is of order \((\Delta t)^2\), uniformly over the current partition. Splits in other leaves do not affect the shared leaf’s clock.
Hence the instantaneous hazard, or rate per unit time of separation given that the pair is still together, is
\[ \lim_{\Delta t\to 0} \frac{\Pr(t<T\leq t+\Delta t\mid T>t,\text{ current tree})}{\Delta t} =s. \]
After a nonseparating cut, both points remain in one child, and the same calculation applies to that child. Thus the rate stays constant throughout the evolution of the tree. This justifies the separation-clock interpretation: at each stage, separating events have rate \(s\), while all other events together have rate \(R-s\). If \(R=s\), there is no background clock. The background rate may change after a split, while the separation rate remains the same.
In fact, this is also a standard survival analysis argument. Let \(S(t)=\Pr(T>t)\). Since the same short-interval calculation holds for every possible current partition, averaging over those partitions gives
\[ \begin{aligned} S(t+\Delta t) &=S(t)\Pr(T>t+\Delta t\mid T>t)\\ &=S(t)\{1-s\Delta t\}+O((\Delta t)^2). \end{aligned} \]
Subtracting \(S(t)\), dividing by \(\Delta t\), and taking the limit yields
\[ S'(t)=-sS(t),\qquad S(0)=1. \]
Solving this equation gives \(S(t)=e^{-st}\), which is the survival function of an exponential distribution with rate \(s\). Once two points are separated by a recursive partition, they cannot return to the same leaf. Hence sharing a leaf at lifetime \(\lambda\) is exactly the event \(T>\lambda\), and
\[ K_{\infty,\lambda}(x,z) =\Pr(T>\lambda) =e^{-\lambda s} =e^{-\lambda\|x-z\|_1}. \]
This makes the infinite Mondrian same-leaf kernel exactly the Laplace kernel with parameter \(\lambda\). The result also holds when \(x=z\), since both sides equal 1.
Finally, this gives a direct connection to the bandwidth of a kernel smoother. Writing \(h=1/\lambda\), we have \(K_{\infty,\lambda}(x,z)=\exp(-\|x-z\|_1/h)\). A larger lifetime gives the tree more time to split, leading to finer partitions and a narrower kernel. At lifetime 0 there are no cuts and every pair shares the same leaf; as \(\lambda\to\infty\), the similarity tends to 0 for every fixed pair \(x\ne z\).
The number of trees plays a different role. At a fixed lifetime, let \(J_\lambda^{(b)}(x,z)\) be the same-leaf indicator from the \(b\)th independently generated Mondrian tree. By the law of large numbers,
\[ K_{B,\lambda}(x,z) =\frac{1}{B}\sum_{b=1}^B J_\lambda^{(b)}(x,z) \xrightarrow[B\to\infty]{\mathrm{a.s.}} K_{\infty,\lambda}(x,z). \]
Thus \(\lambda\) controls the limiting kernel’s bandwidth, while \(B\) controls the Monte Carlo approximation to that kernel. Increasing the number of trees does not itself make the limiting kernel narrower. This calculation describes the similarity induced by the random partitions. To study regression error, we must also consider how observations and outcomes are used within those partitions. We next consider uniform random cuts with a fixed tree depth.
8 An Exact Kernel for Uniform Random Forests
We can also look at a uniform random forest for which part of the kernel can be calculated exactly. In Scornet (2016), the author considered trees with a fixed depth and obtained an explicit expression when one of the two points is the corner \(0=(0,\ldots,0)\). This gives a setting where the product of uniform random variables has a direct geometric interpretation. Here are the conditions:
- The domain is \([0,1]^p\).
- At each node, choose a coordinate uniformly from \(\{1,\ldots,p\}\).
- Choose the split point uniformly within the current range of that coordinate.
- Use independent coordinate choices and independent uniform cut proportions at different nodes.
- Grow a complete binary tree to depth \(k\). Every path from the root to a terminal node has exactly \(k\) splits, and there are \(2^k\) terminal nodes.
Here we fix the depth of every path, while a Mondrian tree is stopped at a specified lifetime. Let
\[ K_k(x,z)=\Pr(x\text{ and }z\text{ fall into the same terminal node}). \]
The probability is over the random tree, with \(x\) and \(z\) fixed. Thus \(K_k\) is already the infinite-forest same-leaf kernel, and the subscript \(k\) records the depth of each tree. Since we are only studying the random partition, this calculation does not require a distributional assumption on the training covariates.
Let’s first consider the one-dimensional case. Start with \([0,1]\) and follow the interval containing 0. If its current right endpoint is \(b\), a uniform cut can be written as \(bU\), where \(U\sim\mathrm{Uniform}(0,1)\). The child containing 0 is then \([0,bU]\). Therefore, if \(b_r\) is the right endpoint after \(r\) cuts along this path, we have
\[ \begin{aligned} b_0&=1,\\ b_1&=U_1,\\ b_2&=b_1U_2=U_1U_2,\\ b_r&=\prod_{\ell=1}^r U_\ell, \qquad U_\ell\overset{\mathrm{iid}}{\sim}\mathrm{Uniform}(0,1). \end{aligned} \]
We keep following the interval containing 0 regardless of whether the other point \(z\) is still inside it. Thus the product representation is unconditional. Since these intervals are nested, 0 and \(z\) remain together after \(r\) cuts exactly when \(z\leq b_r\). Define
\[ q_r(z)=\Pr(b_r\geq z),\qquad z\in[0,1]. \]
In one dimension, \(q_r(z)=K_r(0,z)\). This is where the corner assumption is useful: the left endpoint stays at 0, so the right endpoint alone determines whether \(z\) belongs to the interval.
Now take logarithms. For \(u\geq0\),
\[ \Pr(-\log U_\ell>u) =\Pr(U_\ell<e^{-u}) =e^{-u}. \]
Hence \(-\log U_\ell\sim\mathrm{Exponential}(1)\), using the rate parameterization. Independence then gives
\[ -\log b_r =\sum_{\ell=1}^r(-\log U_\ell) \sim\mathrm{Gamma}(r,1),\qquad r\geq1. \]
Further derivations use this distribution and the number of splits on each coordinate to characterize how quickly the effective kernel width shrinks as tree depth increases; see Scornet (2016). This connection between cell widths and approximation error also motivates the study of regression convergence rates.
Typically, because of all the randomness involved in a random forest, it is difficult to have an exact theoretical rate of convergence. However, given some simplifications, existing literature has provided some theoretical understanding. For example, Scornet (2016) considered a different model called the centered KeRF (Kernel based on Random Forests) and provided a convergence rate. The centered KeRF uses the following mechanism to grow each tree:
- The domain is \([0,1]^p\) and \(X\) is uniformly distributed.
- The regression function \(m(x)\) is Lipschitz.
- At each node, pick a coordinate uniformly at random from \(\{1,\dots,p\}\).
- The split is at the center of the chosen coordinate.
- The tree grows to full depth \(k\), so each cell is cut \(k\) times and there are exactly \(2^k\) terminal nodes.
Under this setting, the infinite forest kernel is able to achieve the rate of
\[ \E[(\hat{m}_{\infty,n}(x) - m(x))^2] \le C (\log n)^2 n^{-\frac{1}{3 + p \log 2}} \]
This is significantly slower than the classical minimax rate for Lipschitz functions \(n^{-2/(p+2)}\) under similar regularity conditions. However, this rate is obtained under a very simplified setting. In practice, random forests are known to be adaptive to low-dimensional structures (e.g., sparse signals) and can achieve much better performance than other nonparametric methods.