Improved convergence rates for some kernel random forest algorithms

1.   Introduction

Random forests are a class of non-parametric statistic machine learning algorithms used for regression and classification tasks. Random forest algorithms have the capability to perform sparse tasks with high accuracy in high dimensions, avoiding overfitting. In particular, random forests are considered to be among the most accurate learning algorithm classes for general tasks. They are routinely used in many fields including bio-informatics ^[15], economics ^[30], biology ^[10], and linguistics ^[18].

The most widely used random forest algorithm was introduced by Breiman ^[13], who was inspired by the work on random subspaces of Ho ^[19], and geometrical feature selection of Amit and Geman ^[2]. In Breiman's random forest, the trees are grown based on the classification and regression trees (CART) procedure, where both splitting directions and training sets are randomized. However, despite the few parameters that need to be tuned ^[16,21], their mathematical properties are still areas of active research ^[6,22]. A significant distinction among the class of random forest algorithms consists in the way each individual tree is constructed, and, in particular, the dependence of each tree on the data set. Some of the researchers consider random forests designed independently from the data set ^[7,14,25].

In 2012, Biau ^[5] studied a random forest model proposed by Breiman, where the construction is independent of the data set, called in literature centered random forest. In ^[5] an upper bound on the rate of consistency of the algorithm and its adaption to sparsity were proven. More precisely, about the first item, for a data set of $n$ samples in a space of dimension $d,$ the convergence rate was $\mathcal{O}\left(n^{-\frac{1}{d \frac{4}{3}\log{2}+1}}\right).$ In 2021, Klusowski ^[20] improved the rate of convergence to $\mathcal{O}\left((n\log^{\frac{d-1}{2}} {n})^{ -(\frac{1+\delta}{d\log{2}+1})} \right),$ where $\delta$ is a positive constant that depends on the dimension of the feature space $d$ and converges to zero as $d$ approaches infinity. In addition, in the same paper, Klusowski proved that the rate of convergence of the algorithm is sharp, although it fails to reach the minimax rate of consistency over the class of the Lipschitz functions $\mathcal{O}\left(n^{\frac{-2}{d+2}} \right)$ ^[29]. There is also important work on the consistency of algorithms that depend on data ^[23,27,28]. For a comprehensive overview of both theoretical and practical aspects of the random forests, see ^[8], which surveys the subject up to 2016.

An important tool for algorithmically manipulating random forests is through kernel methods. Breiman ^[11] observed the connection between kernel theory and random forests by showing the equivalence between tree construction and kernel action. Later this was formalized by Geurts et al. in ^[17]. In the same direction Scornet in ^[26] defined Kernel Random Forest (KeRF) by modifying the original algorithm, and providing theoretical and practical results. In particular, in his important work, Scornet provided explicit kernels for some generalizations of algorithms, their rate of consistency, and comparisons with the corresponding random forests. Furthermore, Arnould et al. ^[3] investigated the trade-off between interpolation of several random forest algorithms and their consistency results.

In the first part of the paper, we provide the notation and the definitions of the centered and uniform random forests and their corresponding kernel-related formulations. In addition, we improve the rate of consistency for the centered KeRF algorithm. Let $k \ge 1$ be the depth of the trees used to estimate the target variable $Y$ (see Section 2 for definitions and notation).

Theorem 1. Suppose that $X = (X_1, \dots, X_d)$ and $Y$ are related by $\mathit{\boldsymbol{Y}} = m(\mathit{\boldsymbol{X}}) +\epsilon$ where: $\epsilon$ is a zero mean Gaussian noise with finite variance independent of $\mathit{\boldsymbol{X}}$, $\mathit{\boldsymbol{X}}$ is uniformly distributed in $[0, 1]^d$, and $m$ is a regression function, which we assume to be Lipschitz. Then, there exists a constant $\tilde{C}$ such that, for every $n > 1$ and for every $x \in [0, 1]^d$,

Here, $m(x) = \mathbb{E}\left[Y|X = x\right]$ is the predicted value of $Y$ for $X = x\in [0, 1]^d$, while $\tilde{m}^{Cen}_{\infty, n}(x)$ is the estimate for $m$ provided by the kernel version of the centered random forest algorithm.

Similarly, with $\tilde{m}^{Un}_{\infty, n}(x)$ playing for the uniform KeRF algorithm the role $\tilde{m}^{Cen}_{\infty, n}(x)$ had above, we have:

Theorem 2. Let $\mathit{\boldsymbol{X}}$, $\mathit{\boldsymbol{Y}}$, $m,$ and $\epsilon$ be as in Theorem 1, with $\mathit{\boldsymbol{Y}} = m(\mathit{\boldsymbol{X}}) +\epsilon.$ Then there exists a constant $\tilde{C}$ such that for every $n > 1,$ for every $x \in [0, 1]^d$

Moreover, in Section 4, we provide numerical examples and experiments concerning the tuning parameter $k,$ which is the tree depth of the two kernel-based random forest algorithms, by comparing the $L_{2}$-error for different values and under specific assumptions on the data set.

In the final part of the article, we consider the reproducing kernel $K$ used in the centered KeRF algorithm per se. It is rewarding looking at it as defined on the finite Abelian group $\mathbb{Z}_{2}^{kd}$, where, as above, $d$ is the dimension of the vector $X$ and $k$ is the depth of the tree. By using elementary Fourier analysis on groups, we obtain several equivalent expressions for $K$ and its group transform, we characterize the functions belonging to the corresponding Reproducing Kernel Hilbert Space (RKHS) $H_K$, we derive results on multipliers, and we obtain bounds for the dimension of $H_K$, which is much smaller than what one might expect.

2.   Notation

A usual problem in machine learning is, based on $n$ observations of a random vector $(X, Y) \in \mathcal{X}\times\mathbb{R} \subseteq \mathbb{R}^{d}\times\mathbb{R}$, to estimate the function $m(x) = \mathbb{E}(Y | X = x).$ In classification problems, $Y$ ranges over a finite set. In particular we assume that we are given a training sample $\mathcal{D}_{n} = \{(X_{1}, Y_{1}), ..., (X_{n}, Y_{n}) \}$ of independent random variables, where $X_{i} \in [0, 1]^{d}$ for every $i = 1, ..., n$ and $Y \in \mathbb{R}$ with a shared joint distribution $\mathbb{P}_{X, Y}.$ The goal is using the data set to construct an estimate $m_{n}: \mathcal{X} \subseteq [0, 1]^d \to \mathbb{R}$ of the function $m.$ Our convergence rate requires an a priori assumption on the regularity of the function $m.$ Following ^[26], we suppose that $m$ belongs to the class of $L$ Lipschitz functions,

Here, as is ^[26], we consider on $\mathbb{R}^d$ the distance

2.1.   The random forest algorithm

Next, we provide the general random forest framework by defining firstly the notion of a random tree. Additionally, we present two specific variations of the original random forest algorithm, namely, the centered and uniform random forest algorithms.

Let's assume $\Theta_{i}$ for $i = 1, ..., M$ is a collection of independent random variables, distributed as $\Theta.$ The random variables $\Theta_{i}$ correspond to sample the training set or select the positions for splitting. The detailed construction in the case of the centered random forest is performed in Appendix.

Definition 1. For the $j$-th tree in the forest, the predicted value x will be denoted by

Where $A_{n, \Theta_{j}, \mathcal{D}_{n}}(x)$ is the cell containing $x$ and $N_{n, \Theta_{j}, \mathcal{D}_{n}}(x)$ is the number of points that fall into the cell that $x$ belongs to.

For a fixed value of $x \in [0, 1]^d,$ the value of the tree is the empirical expectation of $Y$ in the unique cell containing $x$; which is, this is the hope, a good guess for the target value corresponding to $x.$

A random forest is a finite collection (average) of independent, finite random trees $\{{ \Theta}_1, \dots, {\Theta}_M\}.$

Definition 2. The finite $M$ forest is

From a modeling point of view, we let $M\to \infty$ and consider the infinite forest estimate

The convergence holds almost surely by the law of the large numbers conditionally on $\mathcal{D}_{n}$ ^[12] and [25, Theorem 3.1].

2.2.   Kernel random forest algorithm

In 2016, Scornet ^[26] introduced kernel methods in the random forest world (KeRF), producing a kernel-based algorithm, together with estimates on how this compares with the old one, described above.

To understand the intuition behind KeRF construction, we reformulate the random forest algorithm.

For all $x \in [0, 1]^d,$

Therefore we can define the weights of every observation $Y_{i}$ as

Hence it is clear that the value of weights changes significantly concerning the number of points in each cell. A way to overcome this nuisance is by simultaneously considering all tree cells containing $x$, as the tree is randomly picked in the forest.

For all $x \in [0, 1]^{d},$

This way, empty cells do not affect the computation of the prediction function of the algorithm.

It is proven in ^[26], that this representation has indeed a kernel representation.

Proposition 1. [26, Proposition 1] For all $x \in [0, 1]^{d}$ almost surely, it holds

where

is the proximity function of the $M$ forest.

The infinite random forest arises as the number of trees tends to infinity.

Definition 3. The infinite KeRF is defined as:

The extension of the kernel follows also in the infinite random forest.

Proposition 2. [26, Proposition 2] Almost surely for all $x, y \in [0.1]^{d}$

where

where the left-hand side is the probability that $x$ and $y$ belong to the same cell in the infinite forest.

2.3.   The centered random forest vs centered KeRF, and the uniform random forest vs uniform KeRF

In this paper, we say that an estimator function $m_{n}$ of $m$ is consistent if the following $L_{2}-$type of convergence holds,

as $n \to \infty.$

In the centered and uniform forest algorithms, the way the data set $\mathcal{D}_{n}$ is partitioned is independent of the data set itself.

2.3.1.   The centered random forest/centered KeRF

The centered forest is designed as follows:

$1)$ Fix $k \in \mathbb{N}.$

$2)$ At each node of each individual tree choose a coordinate uniformly from $\{ 1, 2, ..d\}.$

$3)$ Split the node at the midpoint of the interval of the selected coordinate.

Repeat steps 2) and 3) $k$ times. At the end, we have $2^{k}$ leaves, or cells. A toy example of this iterative process for $k = 1, 2$ is in Figures 1 and 2. Our estimation at a point $x$ is achieved by averaging the $Y_{i}$ corresponding to the $X_{i}$ in the cell containing $x.$

Scornet in ^[26] introduced the corresponding kernel-based centered random forest providing explicitly the proximity kernel function.

Proposition 3. A centered random forest kernel with $k \in \mathbb{N}$ parameter has the following multinomial expression [26, Proposition 5],

where $K^{Cen}_{k}$ is the kernel of the corresponding centered random forest.

2.3.2.   The uniform random forest/kernel random forest

Uniform random forest was introduced by Biau et al. ^[7] and is another toy model of Breinman's random forest as a centered random forest. The algorithm forms a partition in $[0, 1]^{d}$ as follows:

$1)$ Fix $k \in \mathbb{N}.$

$2)$ At each node of each individual tree choose a coordinate uniformly from $\{ 1, 2, ..d\}.$

$3)$ The splitting is performed uniformly on the side of the cell of the selected coordinate.

Repeat steps 2) and 3) $k$ times. At the end, we have $2^{k}$ leaves. Our final estimation at a point $x$ is achieved by averaging the $Y_{i}$ corresponding to the $X_{i}$ in the cell $x.$

Again Scornet in [26, Proposition 6] proved the corresponding kernel-based uniform random forest.

Proposition 4. The corresponding proximity kernel for the uniform KeRF for parameter $k \in \mathbb{N}$ and $x\in [0, 1]^d$ has the following form:

with the convention that

and by continuity we can extend the kernel also for zero components of the vector.

Unfortunately, it is very hard to obtain a general formula for $K^{Un}(x, y)$ but we consider instead a translation invariant KeRF uniform forest:

3.   Proofs of the main theorems

In this section, after providing some measure concentration type results ^[9], we improve the rate of consistency of the centered KeRF algorithm. The following lemmata will provide inequalities to derive upper bounds for averages of iid random variables. Lacking a reference, for completeness, we provide detailed proofs of these lemmata. Moreover, we assume for this article that all random variables are real-valued and $\lvert \lvert X \rvert\rvert_{L_{p}} \colon = (\mathbb{E}\lvert X \rvert^{p})^{\frac{1}{p}}$ and $\lvert \lvert X \rvert \rvert_{\infty} \colon = \inf\{ t \colon P(\lvert X \rvert\leq t) = 1 \}$.

Lemma 1. Let $X_{1}, ..., X_{n}$ be a sequence of real independent and identically distributed random variables with $\mathbb{E}(X_{i}) = 0.$ Assuming also that there is a uniform bound for the $L_{1}$-norm and the supremum norm i.e., $\mathbb{E}(\rvert X_{i} \lvert) \leq C,$ $\lvert \lvert X_{i} \rvert \rvert_{\infty} \leq CM$ for every $i = 1, ..., n.$ Then for every $t\in (0, 1)$

for some positive constant $\tilde{C}_{C}$ that depends only on $C.$

Proof. $\forall x \in [0, 1]$ one has that $e^x \leq 1+x+x^2.$ By using the hypothesis for every $\lambda \leq \frac{1}{CM},$

By the independence of the random variables $X_{i},$

Therefore, by Markov inequality

Finally if $C \geq \frac{1}{4}$ we choose, $\lambda = \frac{t}{2 C^2 M},$ otherwise for $\lambda = \frac{t}{16 C M}$

By replacing $X_{i}$ with $-X_{i}$ we conclude the proof. □

Lemma 2. Let $X_{1}, ..., X_{n}$ be a non-negative sequence of independent and identically distributed random variables with $\mathbb{E}(X_{i}) \leq 2,$ $\lvert \lvert X_{i} \rvert \rvert_{\infty} \leq M$ for every $i = 1, ..., n.$ Let also a sequence of independent random variables $\epsilon_{i}$ following normal distribution with zero mean and finite variance $\sigma^2,$ for every $i = 1, ..., n.$ We assume also that $\epsilon_{i}$ are independent from $X_{i}$ for every $i = 1, ..., n.$

Then for every $t\in (0, 1),$

with the positive constant $C$ depending only on $\sigma.$

Proof.

Finally, we select $\lambda = \frac{tn}{8 M \sigma^2},$ when $\sigma \geq \frac{1}{8}$ and $\lambda = \frac{tn}{M \sigma},$ when $\sigma \leq \frac{1}{8}$

Replacing $X_{i}$ with $-X_{i}$ we conclude the proof. □

Theorem 3.1. $\mathit{\boldsymbol{Y}} = m(\mathit{\boldsymbol{X}}) +\epsilon$ where $\epsilon$ is a zero mean Gaussian noise with finite variance independent of $\mathit{\boldsymbol{X}}$. Assuming also that $\mathit{\boldsymbol{X}}$ is uniformly distributed in $[0, 1]^d$ and $m$ is a Lipschitz function. Then there exists exists a constant $\tilde{C}$ such that for every $n > 1$, for every $x \in [0, 1]^d$

Proof. Following the notation in ^[26], let $x \in [0, 1]^d$, $\lVert m \rVert_{\infty} = \sup_{x \in [0, 1]^d} | m(x) |$, and by the construction of the algorithm

Let

and

Hence, we can reformulate the estimator as

Let $t \in (0, \frac{1}{2})$ and the event $C_{t}(x)$ where $\{A_{n}(x), B_{n}(x) \leq t\}.$

where the last inequality was obtained in [26, p.1496]. Moreover, in ^[26],

In order to find the rate of consistency we need a bound for the probability $\mathbb{P}(C_{t}^c(x)).$ Obviously,

We will work separately to obtain an upper bound for both probabilities.

Proposition 5. Let

a sequence of iid random variables. Then for any $t \in (0, 1),$

for some positive constant $\tilde{C}_{1}.$

Proof. It is easy to verify that $\mathbb{E} \tilde{X}_{i} = 0,$ and

hence, $\mathbb{E} \lvert \tilde{X}_{i} \rvert \leq 2.$

Finally,

By Lemma 1,

□

We need a bound for $\mathbb{P}\big(\lvert A_{n}(x) \rvert > t \big)$ where,

Proposition 6. Let

for $i = 1, ..., n$, then for every $t \in (0, 1),$

for some constant $C$ depending only on $\sigma, \lVert m \rVert_\infty.$

Proof.

Therefore,

Let

a sequence of iid random variables. It is easy to verify that $\tilde{Z_{i}}$ are centered and

Hence, $\mathbb{E}\lvert Z_{i} \rvert \leq 4 \lvert \lvert m \rvert \rvert_{\infty}.$ Finally,

By Lemma 1,

Furthermore, let

for $i = 1, ..., n$, a sequence of independent and identically distributed random variables. We can verify that for every for $i = 1, ..., n$:

Finally,

By Lemma 2 it is clear,

We conclude the proposition by observing

□

Finally, let us compute the rate of consistency of the algorithm-centered KeRF. By Propositions 5 and 6, one has that

for some constants $c_{3}, c_{4}$ independent of $k$ and $n.$

Thus,

We compute the minimum of the right-hand side of the inequality for $t \in (0, 1),$

Hence, the inequality becomes

For every $\epsilon_n \in (0, 2]$ it holds, $\log{x} \leq \frac{1}{\epsilon_n} x^{\epsilon_n}.$ Then one has that

We pick

thus,

for a constant $c'$ independent of $n$ and,

Therefore,

Finally,

and, for the second term, with the same arguments

for a constant $\tilde{c}$ independent of $\epsilon_n,$ hence,

and consequently,

Finally we finish the proof by selecting $\epsilon_n = \frac{1}{\log{n}},$ and

□

Theorem 4. $\mathit{\boldsymbol{Y}} = m(\mathit{\boldsymbol{X}}) +\epsilon$ where $\epsilon$ is a zero mean Gaussian noise with finite variance independent of $\mathit{\boldsymbol{X}}$. Assuming also that $\mathit{\boldsymbol{X}}$ is uniformly distributed in $[0, 1]^d$ and $m$ is a Lipschitz function. Providing $k\to \infty$, there exists a constant $\tilde{C}$ such that for every $n > 1$, for every $x \in [0, 1]^d$

Proof. By arguing with the same reasoning as the proof of the centered random forest we can verify that

for some constants $c_{3}, c_{4}$ independent of $k$ and $n.$ The rate of consistency for the Uniform KeRF is the minimum of the right hand in the inequality in terms of $n$

We compute the minimum of the right-hand side of the inequality for $t \in (0, 1),$

Hence, the inequality becomes

For every $\epsilon_n \in (0, 2]$ it holds, $\log{x} \leq \frac{1}{\epsilon_n} x^{\epsilon_n}.$ Then one has that,

We pick

Therefore,

for a constant $c'$ independent of $n$ and,

Therefore,

Finally,

and, for the second term, with the same arguments

for a constant $\tilde{c}$ independent of $\epsilon_n$ hence,

and consequently,

Finally we finish the proof by selecting $\epsilon_n = \frac{1}{\log{n}},$ and

□

4.   Plots and experiments

In the following section, we summarize the rates of convergence for the centered KeRF and the uniform KeRF, and we compare them with the minimax rate of convergence over the class of the Lipschitz functions ^[29]. In addition, we provide numerical simulations where we compare the $L_2-$error for different choices of the tree depth. All experiments performed with the software Python (https://www.python.org/), mainly with the numpy library, where random sets uniformly distributed in $[0, 1]^d$ have been created, for various examples for the dimension $d$ and the function $Y.$ For every experiment the set is divided into a training set (80 %) and a testing set (20 %); then the $L_2-$error $(\sum_{ X_{i} \in \; \text{test set} } (\tilde{m}(X_i) -Y_i)^2)$ and the standard deviation of the error is computed.

For the centered KeRF we compare three different values of tree depth, which from theory provide different convergence rates. First, the choice of $k$ in [26, Theorem 1] that provides the previous convergence rate; second, the selection of $k$ as it was delivered from the Theorem 1.1; and, third, the case where the estimator, in probability, interpolates the data set, but the known convergence rate is slow [3, Theorem 4.1], $O(\log{n}^{-\frac{d-5}{6}})$ for the dimension of the feature space $d > 5.$

For the uniform KeRF, we compare the two values of tree depth as they were derived from ^[26] and Theorem 2 nevertheless, it is not known if the uniform-KeRF algorithm converges when our estimator function interpolates the data set. Of course, in practice, since real data might violate the assumptions of the theorems, one should try cross-validation for tuning the parameters of the algorithms.

Comparing the rates of consistency for centered KeRF and the depth of the corresponding trees:

● Scornet in [26, Theorem 1] rate of convergence:

● New rate of convergence:

● Minimax ^[29] rate of consistency over the class of Lipschitz functions: $n^{\frac{-2}{d+2}}$ functions.

Thus, theoretically, the improved rate of consistency is achieved when trees grow at a deeper level compared with the parameter selection in [26, Theorem 1].

As it is evident from Figure 3, the improvement in the convergence rate is more significant in the low dimensional feature space scenarios. The constant $\tilde{C} = \tilde{C}(d)$ of Theorem 1 depends on the dimension $d$ of the space. The convergence rates in the literature do not try to have a good estimate for $\tilde{C}$, and they are significant for fixed values of $d$ only.

Finally, we note that Klusowski's rate of convergence in ^[20], $\mathcal{O}\left((n\log^{\frac{d-1}{2}} {n})^{ -(\frac{1+\delta}{d\log{2}+1})} \right),$ where $\delta$ is a positive constant that depends on the dimension of the feature space $d$ and converges to zero as $d$ approaches infinity, is sharp and better than the one in Theorem 1 $\mathcal{O}\left(n^{-\bigl(\frac{1}{1+d \log{2}}\bigr)}(\log{n}) \right)$ for small values of $d.$ For large values of $n$ and $d$ the two estimates are essentially the same, but for now, we do not know if in general, the rate of convergence of the centered KeRF is not improvable.

Comparing the rates of convergence for uniform KeRF and the depth of the corresponding trees:

● Scornet in [26, Theorem 2] rate of convergence:

● New rate of convergence:

● Minimax ^[29] rate of convergence for the consistency over the class of Lipschitz functions: $n^{\frac{-2}{d+2}}$ functions.

Thus, theoretically, as in the case of centered random KeRF, the improved rate of consistency is achieved when trees grow at a deeper level compared with the parameter selection in [26, Theorem 2].

The same considerations on the dependence of the constant $\tilde{C}$ on $d$ we made for the centered KeRF hold in the uniform KeRF case, as it is evident in Figure 4. Moreover, as of now, it is still unknown to us if the convergence rate of the uniform KeRF can be improved.

Finally, numerical simulations of the $L_{2}-$error of the centered KeRF-approximation for three different values of $k$ in Figure 5 are reported with the standard deviation of the errors in Figure 6. In Appendix, more simulations and plots for different target functions and for both algorithms are illustrated.

5.   Conclusions

In this paper, we have obtained improved rates of convergence for two kernel-based random forests, the centered KeRF and the uniform KeRF. In addition, we provided numerical simulations for both algorithms concerning the parameters of the methods. Finally, we explored the reproducing kernel Hilbert space related to the centered KeRF providing bounds for the dimension of the aforementioned space.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The first author was funded by the PhD scholarship PON-DOT1303154-3, the second author was partially funded by project GNAMPA 2022 "HOLOMORPHIC FUNCTIONS IN ONE AND SEVERAL VARIABLES" and by Horizon H2020-MSCA-RISE-2017 project 777822 "GHAIA".

Conflict of interest

All authors declare no conflicts of interest in this paper.

Appendix

In this last section, we provide more experiments of low dimensional regression examples with additive noise, regarding the centered and the uniform KeRF. In particular, we calculate and compare the $L_2-$errors and the standard deviations against different sample sizes for different values of the parameter $k$ of the estimator. Moreover, in the following subsection, we study the corresponding RKHS produced by the kernel

defined in the abelian group $\mathbb{Z}_{2}^{kd}.$ To conclude we recall some notation for finite abelian groups, necessary to define the aforementioned RKHS and estimate its dimension.

Appendix A.   Analysis of the kernel

We provide here an alternative description of the centered random forest algorithm, where the dyadic tiling of the hypercube motivates us to define the kernel in the abelian group $\mathbb{Z}^{kd}_{2}$. First, we define a Random Tree $\Theta$. Start with a random variable $\Theta^0$, uniformly distributed in $\{1, \dots, d\}$, and split

where

where for $l = 0, 1$ the splitting was performed in the $\Theta^0$-th coordinate. Choose then random variables $\Theta^{1, l}$ ($l = 0, 1$), distributed as $\Theta^0$, and split each

where, as before, the splitting is performed at the $\Theta_1$-th coordinate, and $I^{\Theta^0, \Theta^1}_{l, 0}$ is the lower half of $I^{\Theta^0}_l$. Iterate the same procedure $k$ times. In order to do that, we need random variables $\Theta^{j; \eta_0, \dots, \eta_j}$, with $\eta_l\in\{1, \dots, d\}$ and $j = 1, \dots, k$. We assume that all such random variables are independent. It is useful think of ${\bf \Theta} = \{\Theta^{j; \eta_0, \dots, \eta_j}\}$ as indexed by a $d$-adic tree, and, in fact, we refer to ${\bf \Theta}$ as a random tree in $[0, 1]^d$. We call cells, or leaves, each of the $2^k$ rectangles into which $[0, 1]^d$ is split at the end of the $k^{th}$ subdivision.

On Figure A1 we see the $L_{2}-$error of the centered KeRF-approximation for a three dimensional feature space and on Figure A2 the standard deviation of the errors.

Figures A3 and A4 show the $L_{2}-$error and the standard deviation for the uniform KeRF in a two dimensional feature space and Figures A5 and A6 present a three dimensional example respectively.

Appendix B.   A reproducing kernel from the centered KeRF

B.1. The Fourier analysis of the kernel

The kernel in the centered KeRF defines a RKHS $H_K$ structure on a set $\Gamma$ having $2^{kd}$ points ^[4]. In fact, $\Gamma$ has a group structure, and Fourier analysis can be used. Much research is done in RKHS theory, and in this section (see ^[1]), we study the structure of $H_K$ in itself. A priori, $H_K$ might have any dimension less or equal to $\# \Gamma$. We show in fact that its dimension is much lower than that, a fact which is somehow surprising, and we believe it is interesting in itself. Furthermore, we prove that there are no nonconstant multipliers in the space $H_K.$ For completeness we provide definitions and notation on Fourier analysis on Abelian groups in Appendix C.

We identify every real number $x \in [0, 1]$ with its binary expression $x = 0.x_{1}x_{2}x_{3}...$ with $x_{i} \in \{ 0, 1\}$ for $i \in \mathbb{N}.$ Here we consider the group

The kernel $K:\Gamma\times\Gamma\to\mathbb{C}$ corresponding to the kernel $K^{cen}_{k}$ is,

where $\binom{k}{l}$ is the multidimensional binomial coefficient, $\chi_E$ is the characteristic function of the set $E$, and $a-b$ is the difference in the group $\mathbb{Z}_2^{kd}$. Incidentally, (B.2) shows that the kernel $K$ can be viewed as a convolution kernel on the appropriate group structure. For the last equality, we consider the binary representation of a number in $(0, 1]$ whose digits are not definitely vanishing. The fact that $0$ does not have such representation is irrelevant since the probability that one of the coordinates of the data vanishes is zero.

We now compute the anti-Fourier transform $\mu = \check{\varphi}$. We know that $\sharp(\Gamma) = 2^{kd}$, and that the characters of $\mathbb{Z}_2^{kd}$ have the form

Hence,

The last expression vanishes exactly when for all $l$, there are some $1\le j\le d$, and some $k_j+1\le i\le k$ such that $x^j_i = 1$, due to the presence of the factor $(-1)^{a^j_i x^j_i} = (-1)^{a^j_i}$ which takes values $\pm1$ on summands having, two by two, the same absolute values.

If, on the contrary, there is $l$ such that for all $1\le j\le d$, and $k_j+1\le i\le k$, we have that $x^j_i = 0$, then $\mu(x)\ne0$. Since $|l| = k$ and there are $kd$ binary digits involved in the expression of $x$, the latter occurs exactly when the binary matrix representing $x$ has a large lower region in which all entries are $0$. More precisely, the number of vanishing entries must be at least

The number $N(d, k)$ of such matrices is the dimension of $H_K$, the Hilbert space having $K$ as a reproducing kernel.

Next, we prove some estimates for the dimension of the RKHS.

We summarize the main items in the following statement.

Theorem B.1. Let $K:\Gamma\times\Gamma\to\mathbb{C}$ be the kernel in (B.2), $K(a, b) = \varphi(a-b)$, and let

Then,

(i) As a linear space, $H_K = L_{E_K}$, where

(ii) For $x\in E_K$,

To obtain the expression on (B.8), we used the fact that

B.2. Some properties of $H_K$

Linear relations. Among all functions $\psi:\Gamma\to\mathbb{C}$, those belonging to $H_K$ (i.e., those belonging to $L_{E_K}$) are characterized by a set of linear equations,

Multipliers. A multiplier of $H_K$ is a function $m:\Gamma\to\mathbb{C}$ such that $m\psi\in H_K$ whenever $\psi\in H_K$.

Proposition B.1. The space $H_K$ has no nonconstant multiplier.

In particular, it does not enjoy the complete Pick property, which has been subject of intensive research for the past twenty-five years ^[1].

Proof. The space $H_K$ coincides as a linear space with $L_{E_K}$. Let $\Lambda_E = \check{L_E}$, which is spanned by $\{\delta_x:\ x\in E\}$. Observe that, since $0 = (0|\dots|0)\in E_K$, the constant functions belong to $H_K$, hence, any multiplier $m$ of $H_K$ lies in $H_K$; $m = m\cdot 1\in H_K$.

Suppose $m$ is not constant. Then, $\check{m}(a)\ne0$ for some $a\in E_K$, $a\ne0$. Let $a$ be an element in $E_K$ such that $\check{m}(a)\ne0$. Since $H_K\ni m\cdot\widehat{\delta_x}$ for all $x$ in $E_K$, and $m\cdot\widehat{\delta_x} = \widehat{\check{m}\ast\delta_x}$, we have that the support of $\check{m}\ast\delta_x$ lies in $H_K$. Now,

hence, we have that, for any $x$ in $E_K$, $y = x-a$ lies in $E_K$ as well. This forces $a = 0$, hence $m$ to be constant. □

B.3. Bounds for dimension and generating functions

Theorem B.2. For fixed $d\ge 1$, we have the estimates:

Proof. Let $l_{1}, l_{2}, ..., l_{d}$ such that

where $m$ is a parameter and let also $\lambda = \lvert j : l_{j} \geq 1 \rvert = \lvert \{ \text{stop 1-digits} \} \rvert = \lvert \{ \text{back-entries} \} \vert$ where $\lvert \cdot \rvert$ denotes the size of the sets, and of course we have that $0 \leq m \leq k$ and $0\leq \lambda \leq d, m.$ Goal to obtain a bound for

and

Let $A(m, \lambda)$ the m-th coefficient of $x$ in the polynomial

and $2^{m} A(m, \lambda)$ is the m-th coefficient of $x,$ for the fraction $\frac{(2x)^{\lambda}}{(1-2x)^{\lambda}},$ therefore $2^{m-\lambda} A(m, \lambda)$ is the m-th coefficient of $\frac{x^{\lambda}}{(1-2x)^{\lambda}}.$ Let's see the first sum, $B(m, d)$ is the m-th coefficient of $x$:

Again by the same combinatoric argument we are looking the $k$-th coefficient of the function

Back to the estimate, Let $a_{k}$ the coefficient of the power series centered at $z = 0.$

After some calculations since $r$ is fixed one has that the maximum is achieved for $\theta = 0.$ So

Our estimation finally becomes:

Thus an estimate for the dimension of $H_K$ is

Another estimate about the dimension of $H_K$. For $f(z) = \sum_{n = 0}^\infty a_n z^n$, we have

Consider the function

in $|z| < 1/2$ and let $r = \frac{1-1/k}{2}$. Then,

Thus,

Recursively working out the generating function one gets the estimates in (B.10). □

Appendix C.   Some results from Fourier analysis on finite groups

Following the notation of ^[24], we recall here the basic notions of Fourier theory for a finite, abelian group $G$, which we employed above. Here, $G$ is endowed with its counting measure. The dual group $\Gamma = \widehat{G}$ of $G$ is populated by labels $a$ for homomorphisms $\gamma_a:G\to\mathbb{T} = \{e^{i t}:\ t\in\mathbb{R}\}$. Given a function $f:G\to\mathbb{C}$, its Fourier transform $\widehat{f}:\Gamma\to\mathbb{C}$ is defined as

We make $\Gamma$ into a (finite), additive group by setting

It turns out that they have the same number of elements, $\sharp(G) = \sharp(\Gamma)$. Some basic properties are:

where

We write

The unit element of convolution in $G$ is $\delta_0$.

In the other direction, for $\varphi, \psi:\Gamma\to\mathbb{C}$ we define

and similarly to above, $\widehat{\check{\varphi}\check{\psi}} = \varphi\ast\psi$. The unit element on convolution in $\Gamma$ is $\sharp(\Gamma)\delta_0$.

A function $\varphi$ on $\Gamma$ is positive definite if

Theorem C.1. [Bochner's theorem] A function $\varphi:\Gamma\to\mathbb{C}$ is positive definite if and only if there exists $\mu:G\to\mathbb{R}_+$ such that $\varphi = \widehat{\mu}$.

The theorem holds in great generality, and its proof in the finite group case is elementary. We include it because it highlights the relationship between the measure $\mu$ on $G$ and the positive definite function (the kernel) $\varphi$.

Proof. If

Only if, since for all $b$ in $\Gamma$,

we have

by the assumption. □

We now come to reproducing kernels on $\Gamma$ which are based on positive definite functions $\varphi:\Gamma\to\mathbb{R}_+$. Set

and set

where $H_K$ is the Hilbert space having $K$ as reproducing kernel. We wish to have a more precise understanding of it.

We start by expressing the norm of an element on $H_K$ is several equivalent ways,

In other terms,

is an isometry of $H_K$ onto $L^2(\mu)$. This will become important later, when we verify that for our kernels $\text{supp}(\mu)$ is sparse in $G$. In fact, $\text{dim}(H_K) = \sharp(\text{supp}(\mu))$.

Corollary C.1. As a linear space, $H_K$ is determined by $\mathit{\text{supp}}(\mu)$:

Let $E\subseteq G$. We denote

Next, we look for the natural orthonormal system provided by the Fourier isometry (C.11). Fr $x\in G$, let $\check{c_x} = \mu(x)^{-1/2}\delta_x$: $\{\check{c_x}:\ x\in E: = \text{supp}(\mu)\}$ is a orthonormal system for $L^2(\mu)$, and so $\{e_x:\ x\in E\}$ is an orthonormal basis for $H_K$, where

and

Let's verify that we obtain the reproducing kernel from the o.n.b. as expected,

Remark C.1. Since any finite, abelian group can be written as the direct product of cyclic groups,

its dual $\Gamma$ can be written in the same way, because $\widehat{\mathbb{Z}_m}\equiv\mathbb{Z}_m$. From the Fourier point of view, the only difference is that, if on $G$ we consider the counting measure, then on $\Gamma$ we consider normalized counting measure, as we did above.