In order to prevent overfitting and to lighten the model, several ways to simplify DF architecture have been investigated. [16] considers RF whose complexity varies through the network, and combines it with a confidence measure to pass high confidence instances directly to the output layer. Other directions towards DF architecture simplification are to play on the nature of the RF involved [3] (using Extra-Trees instead of Breiman's RF), on the number of RF per layer [10] (implementing layers of many forests with few trees), or even on the number of features passed between two consecutive layers [18] by relying on an importance measure to process only the most important features at each level. The simplification can also occur once the DF architecture is trained, as in [11] selecting in each forest the most important paths to reduce the network time-and memory-complexity. Approaches to increase the approximation capacity of DF have also been proposed by adjoining weights to trees or to forests in each layer [20, 21] , replacing the forest by more complex estimators (cascade of ExtraTrees) [2] , or by combining several of the previous modifications notably incorporating data preprocessing [9] . Overall, the related works on DF exclusively represent algorithmic contributions without a formal understanding of the driving mechanisms at work inside the forest cascade.
Contributions. In this paper, we analyze the benefit of combining trees in network architecture both theoretically and numerically (on simulated and real-world datasets). We show in particular that much lighter configuration can be on par with DF default configuration, leading to a drastic reduction of the number of parameters in few cases. For most datasets, considering DF with two layers is already an improvement over the basic RF algorithm. However, the performance of the overall method is highly dependent on the structure of the first random forests, which leads to stability issues. By establishing tight lower and upper bounds on the risk, we prove that a shallow tree-network may outperform an individual tree in the specific case of a well-structured dataset if the first encoding tree is rich enough. This is a first step to understand the interest of extracting features from trees, and more generally the benefit of tree networks.
Agenda. DF are formally described in Section 2. Section 3 is devoted to the numerical study of DF, by evaluating the influence of the number of layers in DF architecture, by showing that shallow sub-models of one or two layers perform the most, and finally by understanding the influence of tree depth in cascade of trees. Section 4 contains the theoretical analysis of the shallow centered tree network. For reproducibility purposes, all codes together with all experimental procedures are to be found at https://github.com/Ludovic-arnould/Deep-Forest.
Deep Forest [25] is a hybrid learning procedure in which random forests are used as the elementary components (neurons) of a neural network. Each layer of DF is composed of an assortment of Breiman's forests and Completely-Random Forests (CRF) [25] and trained one by one. In a classification setting, each forest of each layer outputs a class probability distribution for any query point x, corresponding to the distribution of the labels in the node containing x. At a given layer, the distributions output by all forests of this layer are concatenated, together with the raw data. This new vector serves as input for the next DF layer. This process is repeated for each layer and the final classification is performed by averaging the forest outputs of the best layer (without raw data) and applying the argmax function. The overall architecture is depicted in Figure 1 .
Deep Forests contain an important number of tuning parameters. Apart from the traditional parameters of random forests, DF architecture depends on the number of layers, the number of forests per layer, the type and proportion of random forests to use (Breiman or CRF) . In [25] , the default configuration is set to 8 forests per layer, 4 CRF and 4 RF, 500 trees per forest (other forest parameters are set to sk-learn [17] default values), and layers are added until 3 consecutive layers do not show score improvement.
Due to their large number of parameters and the fact that they use a complex algorithm as elementary bricks, DF consist in a potential high-capacity procedure. However, as a direct consequence, Figure 1 : Deep Forest architecture (the scheme is taken from [25] ) the numerous parameters are difficult to estimate (requiring specific tuning of the optimization process) and need to be stored which leads to high prediction time and large memory consumption. Besides, the layered structure of this estimate, and the fact that each neuron is replaced by a powerful learning algorithm makes the whole prediction hard to properly interpret.
As already pointed out in the Related works paragraph, several attempts to lighten the architecture have been conducted. In this paper, we will propose and assess the performance of a lighter DF configuration on tabular datasets. Remark 1. Deep Forest [25] was first designed to handle images. To do so, a pre-processing network called Multi Grained Scanning (MGS) based on convolution methods is first applied to the original images. Then the Deep Forest algorithm runs with the newly created features as inputs.
In order to understand the benefit of using a complex architecture like Deep Forests, we compare different configurations of DF on six datasets in which the output is binary, multi-class or continuous, see Table 1 for description. All classification datasets belong to the UCI repository, the two regression ones are Kaggle datasets (Housing data and Airbnb Berlin 2020) 1 In what follows, we propose a light DF configuration. We show that, in most cases (particularly in classification), our light configuration performance is comparable to the performance of the default DF architecture of [25] , thus questioning the relevance of deep models. Therefore, we analyze the influence of the number of layers in DF architectures, showing that DF improvements mostly rely on the first layers of the architecture. Finally, to gain insights about the quality of the new features created by the first layer, we consider a shallow tree network for which we evaluate the performance as a function of the first-tree depth.
Setting. We compare the performance of the following DF architectures on the datasets summarized in Table 1: (i) the default setting of DF introduced by [25] and described in the above section, (ii) the best DF architecture obtained by grid-searching over the number of forests per layer, the number of trees per forest, and the maximum depth of each tree in the forests;
(iii) a new light DF architecture, composed of 2 layers, 2 forests per layer (one RF and one CRF) with only 50 trees of depth 30 trained only once.
Results. The results are presented in Figures 2 and 3 . Each bar plot respectively corresponds to the average accuracy or the average R 2 score over 10 tries for each test dataset; the error bars stand for accuracy or R 2 standard deviation. The description of the resulting best DF architecture for each dataset is given in As highlighted in Figure 2 , the performance of the light configuration for classification datasets is comparable to the default and the best configurations, while being much more computationally efficient (faster to train, faster at prediction, cheaper in terms of memory). This should be qualified by the yardstick of dataset regression results (see Figure 3 ). Indeed, for this type of problems, each forest in each layer output a scalar compared to the classification tasks in which the output is a vector whose size equals the number of classes. Therefore in regression, the extracted representation at each layer is simplistic thus requiring a deeper architecture.
Overall, for classification tasks, the small performance enhancement of deep forests (Default or Best DF) over our light configuration should be assessed in the light of their additional complexity. This questions the usefulness of stacking several layers made of many forests, resulting into a heavy architecture. We further propose an in-depth analysis of the contribution of each layer to the global DF performance.
Setting. On all the previous datasets, we train a DF architecture by specifying the number p of layers. Unspecified hyper-parameters are set to default value (see Section 2) . For each p, we consider the truncated sub-models composed of layer 1, layer 1-2, . . ., layer 1-p, where layer 1-p is the original DF with p layers. For each value of p, we consider the previous nested sub-models with 1, 2, . . . , p layers, and compute the predictive accuracy of the best sub-model.
. We only display results for the Adult dataset in Figure 4 (all the other datasets show similar results, see Appendix S1.3). We observe that adding layers to the Deep Forest does not significantly change the accuracy score. Even if the variance changes by adding layer, we are not able to detect any pattern, which suggests that the variance of the procedure performance is unstable with respect to the number of layers. Heatmap counting the optimal layer index over 10 tries of a default DF with 1 (Breiman) forest per layer (left) or 4 forests (2 Breiman, 2 CRF) per layer (right), with respect to the maximal number of layers. The number corresponding to (m, n) on the x-and y-axes indicates how many times out of 10 the layer m is optimal when running a cascade network with a number n of layers.
Globally, we observe that the sub-models with one or two layers often lead to the best performance (see Figure 5 for the Adult dataset and Appendix S1.3 for the other ones). When the dataset is small (Letter or Yeast), the sub-model with only one layer (i.e. a standard RF) is almost always optimal since a single RF with no maximum depth constraint already overfits on most of these datasets. Therefore the second layer, building upon the predictions of the first layer, entails overfitting as well, therefore leading to no improvement of the overall model. Besides, one can explain the predominance of small sub-models by the weak representability power created by each layer: on the one hand, each new feature vector size corresponds to the number of classes times the number of forests which can be small with respect to the number of input features; on the other hand, the different forests within one layer are likely to produce similar probability outputs, especially if the number of trees within each forest is large. The story is a little bit different for the Housing dataset, for which the best submodel is between 2 and 6. As noticed before, this may be the result of the frustratingly simple representation of the new features created at each layer. Eventually, these numerical experiments corroborate the relevance of shallow DF as the light configuration proposed in the previous section.
We note that adding forests in each layer decreases the number of layers needed to achieve a pre-specified performance. This is surprising and is opposed to the common belief that in deep neural networks, adding layers is usually better than adding neurons in each layer.
In order to finely grasp the influence of tree depth in DF, we study a simplified version: a shallow CART tree network, composed of two layers, with one CART per layer.
Setting. In such an architecture, the first-layer tree is fitted on the training data. For each sample, the first-layer tree outputs a probability distribution (or a value in a regression setting), which is referred to as "encoded data" and given as input to the second-layer tree, with the raw features as well. For instance, if we consider binary classification data with classes 0 and 1, with raw features (x 1 , x 2 , x 3 ), the input of the second-layer tree is a 5-dimensional feature vector (x 1 , x 2 , x 3 , p 0 , p 1 ), with p 0 and p 1 the predicted probabilities by the first-layer tree for the classes 0 and 1 respectively.
For each dataset of Table 1 , we first determine the optimal depth k of a single CART tree via 3-fold cross validation. Then, for a given first-layer tree with a fixed depth, we fit a second-layer tree, allowing its depth to vary. We then compare the resulting shallow tree networks in three different cases: when the (fixed) depth of the first tree is (i) less than k , (ii) equal to k , and (iii) larger than k . We add the optimal single tree performance to the comparison. Figure 6 : Adult dataset. Accuracy of a two-layer tree architecture w.r.t. the second-layer tree depth, when the first-layer (encoding) tree is of depth 2 (top), 9 (middle), and 15 (bottom). rtree is a single tree of respective depth 2 (top), 9 (middle), and 15 (bottom), applied on raw data. For this dataset, the optimal depth of a single tree is 9 and the tree with the optimal depth is depicted as rtree 9 in each plot. The green dashed line indicates the median score of the rtree. All boxplots are obtained by 10 different runs.
Results. Results are displayed in Figure 6 for the Adult dataset only (see Appendix S1.2 for the results on the other datasets). Specifically noticeable in Figure 6 (top), the tree network architecture can introduce performance instability when the second-layer tree grows (e.g. when the second-layer tree is successively of depth 7, 8 and 9).
Furthermore, when the encoding tree is not deep enough (top), the second-layer tree improves the accuracy until it approximately reaches the optimal depth k . In this case, the second-layer tree compensates for the poor encoding, but cannot improve over a single tree with optimal depth k . Conversely, when the encoding tree is more developed than an optimal single tree (bottom)overfitting regime, the second-layer tree may not lead to any improvement, or worse, may degrade the performance of the first-layer tree. Figure 7 : Adult dataset. Focus on the first levels of the second-layer tree structure when the first layer tree is of depth 9 (optimal depth). Raw features range from X[0] to X [13] , X [14] and X [15] are the features built by the first-layer tree.
On all datasets, the second-layer tree is observed to always make its first cut over the new features (see Figure 7 and the ones in the Appendix S1.2 to visualize the constructed tree network structure). In the case of binary classification, a single cut of the second-layer tree along a new feature yields to gather all the leaves of the first tree, predicted respectively as 0 and 1, into two big leaves, therefore reducing the predictor variance (cf. Figure 6 (middle and bottom)). Furthermore, when considering multi-label classification with n classes , the second-layer tree must cut over at least n classes features to recover the partition of the first tree (see Figure S15 ). Similarly, in the regression case, the second tree needs to perform a number of splits equal to the number of leaves of the first tree in order to recover the partition of the latter.
In Figure 6 (middle), one observes that with a first-layer tree of optimal depth, the second-layer tree may outperform an optimal single tree, by improving both the average accuracy and its variance. We aim at theoretically quantifying this performance gain in the next section.
In this section, we focus on the theoretical analysis of a simplified tree network in a binary classification setting.
Chessboard data generation. Let k be an even integer and p ∈ (1/2, 1]. The data set D n is assumed to be composed of i.i.d. pairs (X 1 , Y 1 ), . . . , (X n , Y n ), with the same distribution as the generic pair (X, Y ). The variable X is assumed to be uniformly distributed over [0, 1] 2 and, for all
This distribution corresponds to a chessboard structure: for each cell, which is of size 2 −k /2 × 2 −k /2 , either the true proportion of 1 is p > 1/2 or the true proportion of 0 is p > 1/2, depending on the parity of i + j (which pinpoints the cell location). Note that the distribution is parameterized by k and p, and that 2 k corresponds to the total number of cells. Such a distribution is depicted in Figure 8 . This type of dataset has already been studied within RF frameworks in [5] and despite its simplicity, highlights some interesting properties of tree-based methods.
Notations. Given a decision tree, we will denote by C n (X) the cell of the tree containing X and N n (C n (X)) the number of data points falling into C n (X). The prediction of such a tree at point X Figure 8 : Chessboard data distribution in black and white as described above for k = 6. Partition of the (first) encoding tree of depth 4, 6, 8 (from left to right) is displayed in blue. The optimal depth of a single centered tree for this chessboard distribution is 6. is given byr
with the convention 0/0 = 0, i.e. the prediction for X in a leaf with no observations is set to zero.
A shallow centered tree network. We want to theoretically analyze the benefits of using two trees in cascade and determine, in particular, the influence of the first (encoding) tree on the performance of the whole shallow tree network. To show the variance reduction property of the second tree already emphasized in the previous section, we need to go beyond the classical 0 − 1 loss and consider instead this problem as a probability estimation one (regression setting). To this aim, we let r(x) = E[Y |X = x] be the regression function and we consider, for any function f , its quadratic risk defined as
where the expectation is taken over (X, Y, D n ).
Definition 1 (Shallow centered tree network). The shallow tree network consists in two trees in cascade:
• (Encoding layer) The first-layer tree is a cycling centered tree of depth k. It is built independently of the data by splitting recursively on the first and second variables, at the center of the cells. The tree construction is stopped when all cells have been cut exactly k times. For each point X, we extract the empirical meanȲ Cn(X) of the outputs Y i falling into the leaf C n (X) and we pass the new featureȲ Cn(X) to the next layer, together with the original features X.
• (Output layer) The second-layer tree is a centered tree of depth k for which a cut can be performed at the center of a cell along a raw feature (as done by the encoding tree) or along the new featureȲ Cn(X) . In this latter case, two cells corresponding to {Ȳ Cn(X) < 1/2} and {Ȳ Cn(X) ≥ 1/2} are created.
The resulting predictor composed of the two trees in cascade, of respective depth k and k , trained on the data (X 1 , Y 1 ), . . . , (X n , Y n ) is denoted byr k,k ,n .
The two cascading trees can be seen as two layers of trees, hence the name of the shallow tree network. Note in particular thatr k,0,n (X) is the prediction given by the first encoding tree only and outputs, as a classical tree, the mean of the Y i falling into a leaf containing X. When considering two trees in cascade, the predictorr k,k ,n (X) may output the mean of the Y i with the X i falling into a union of the first-tree leaves containing X.
We first study the risk of the shallow tree network in the infinite sample regime. The results are presented in Lemma 1.
Lemma 1. Assume that the data follows the chessboard distribution described above. In the infinite sample regime, the following holds for the shallow tree networkr k,k ,n (Definition 1):
(i) For any k < k (shallow encoding tree), the risk of the shallow tree network is minimal for a second-layer tree of depth k ≥ k whose k first cuts are performed along raw features only.
(ii) For any k ≥ k (deep encoding tree), the risk of the shallow tree network is minimal for a second-layer tree of depth k ≥ 1 whose first (and only) cut is performed along the new featurē Y Cn(X) .
The proof of Lemma 1 is given in Appendix S3. In the infinite sample regime, Lemma 1 shows that the pre-processing is useless when the encoding tree is shallow (k < k ): the second tree cannot leverage on the partition of the first one and needs to build a finer partition from zero.
Lemma 1 also provides an interesting perspective on the second-layer tree which either acts as a copy of the first-layer tree or can simply be of depth one. We believe that in this latter case, the shallow network may benefit from the variance reduction of the second-layer tree, which gathers similar cells and averages their prediction to build the output. Indeed, this has been empirically observed when dealing with two layers of CART trees.
Main results. With this in mind, we move towards the finite sample regime to study the variance reduction phenomenon, and motivated by Lemma 1, we consider a second-layer tree of depth one, whose first cut is performed along the new featureȲ Cn(X) at 1/2.
To study the interest of using a shallow tree network instead of a single tree, we first establish upper and lower bounds for a single centered tree of depth k < k and k ≥ k respectively.
Proposition 2 (Risk of a single tree). Assume that the data is drawn according to the chessboard distribution with parameters k and p > 1/2. Consider the predictorr k,0,n corresponding to a single centered tree of depth k ∈ N . Then, 1. if k < k , (i) an upper-bound on the excess risk reads as
(ii) a lower-bound on the excess risk reads as
(i) an upper-bound on the excess risk reads as
(ii) a lower-bound on the excess risk reads as
The proof of Proposition 2 is given in Appendix S4. First, note that our bounds are tight in both cases (k < k and k ≥ k ) since the rate of the upper bounds match that of the lower ones. The first statement in Proposition 2 quantifies the bias of a shallow tree of depth k < k : the term (p − 1/2) 2 appears in both the lower and upper bounds, which means that no matter how large the training set is, the risk of the tree does not tend to zero. The second statement in Proposition 2 proves that the risk of a tree deep enough (k ≥ k ) tends to zero with n. In this case, the bias is null and the risk is governed by the variance term which is O(2 k /n)-term (note that n/2 k is the average number of points in each cell). In all bounds, the term (1 − 2 −k ) n corresponding to the probability of X falling into an empty cell is classic and cannot be eliminated for centered trees, whose splitting strategy is independent of the dataset.
However, we are not interested in the performance of the single tree but in the improvements that the shallow tree network can bring to an individual tree. Note that stacking two layers of trees together still leads to a partition-type estimator with axis-aligned splits. However, it allows to build more complex partitions since it may gather cells of the first tree that are disconnected. This may lead to an improvement of the resulting estimator, by reducing the variance in the corresponding cell collections. Proposition 3 quantifies this phenomenon by establishing upper and lower bounds on the risk of the shallow tree network for k < k and k ≥ k .
Proposition 3 (Risk of a shallow tree network). Assume that the data is drawn according to the chessboard distribution with parameters k and p > 1/2. Consider the predictorr k,1,n corresponding to two trees in cascade (see Definition 1). Then, 1. if k < k , (i) an upper-bound on the excess risk reads as
(ii) a lower-bound on the excess risk reads as
(i) an upper-bound on the excess risk reads as
(ii) a lower-bound on the excess risk reads as
where 0 < ρ k,p < 1 depends only on p and k and given that n ≥
The proof of Proposition 3 is given in Appendix S5. Note that, in both cases, the rate of the upper bounds match that of the lower ones, highlighting the tightness of these bounds.
As for the single tree studied in Proposition 3, the shallow tree network suffers from a bias term (p − 1/2) 2 as soon as the first-layer tree is not deep enough. In such a shallow tree network, the flaws of the first-layer tree transfer to the whole network. However, there may exist a benefit from using this network when the first-layer tree is deep enough. In this case, the risk of the shallow tree network is O(1/n) whereas that of a single tree is O(2 k /n). In presence of complex and highly structured data (large k and similar distribution in different areas of the input space, as for the chessboard distribution), the shallow tree network benefits from a variance reduction phenomenon by a factor 2 k (as highlighted by Proposition 3 and Proposition 2).
In Figure 9 , we numerically evaluate the risk R(r k,1,n ), and its average value exactly lies between the theoretical upper and lower bounds, that end up being merged. Risk lower bound upper bound mean risk risk boxplot Figure 9 : Illustration of the theoretical bounds of Proposition 3, when the first-layer tree is of depth k = 6 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation.
In this paper, we study both numerically and theoretically DF and its elementary components. We show that stacking layers of trees (and forests) may improve the predictive performance of the algorithm. However, most of the improvements rely on the first DF-layers. We show that the performance of a shallow tree network (composed of single CART) depends on the depth of the first-layer tree. When the first-layer tree is deep enough, the second-layer tree may build upon the new features created by the first tree by acting as a variance reducer.
To quantify this phenomenon, we propose a first theoretical analysis of a shallow tree network (composed of centered trees) closely related to DF procedure. Our study exhibits the crucial role of the first (encoding) layer: if the first-layer tree is biased, then the entire shallow network inherits this bias, otherwise the second-layer tree acts as a good variance reducer. One should note that this variance reduction cannot be obtained by averaging many trees, as in RF structure: the variance of an averaging of centered trees with depth k is of the same order as one of these individual trees [4, 12] , whereas two trees in cascade (the first one of depth k and the second of depth 1) may lead to a variance reduction by a 2 k factor. This highlights the benefit of tree-layer architectures over standard ensemble methods. We thus believe that this first theoretical study of this shallow tree network paves the way of the mathematical understanding of DF.
First-layer tree, and more generally the first layers in DF architecture, can be seen as a data-driven encoder. Since preprocessing is nowadays an important part of all machine learning pipelines, we believe that our analysis is interesting beyond the framework of DF. S1 Additional figures S1.1 Additional figures to Section 3.2
Best configuration hyperparam.
Mean optimal sub-model (10 tries Figure S10 : Adult dataset. Accuracy of a two-layer tree architecture w.r.t. the second-layer tree depth, when the first-layer (encoding) tree is of depth 2 (top), 9 (middle), and 15 (bottom). rtree is a single tree of respective depth 2 (top), 9 (middle), and 15 (bottom), applied on raw data. For this dataset, the optimal depth of a single tree is 9 and the tree with the optimal depth is depicted as rtree 9 in each plot. The green dashed line indicates the median score of the rtree. All boxplots are obtained by 10 different runs. Figure S11 : Adult dataset. Second-layer tree structure of depth 4 when the first-layer tree is of depth 9 (optimal depth). Raw features range from X[0] to X [13] , X [14] and X [15] are the features built by the first-layer tree. Figure S12 : Higgs dataset. Accuracy of a two-layer tree architecture w.r.t. the second-layer tree depth, when the first-layer (encoding) tree is of depth 2 (top), 9 (middle), and 15 (bottom). rtree is a single tree of respective depth 2 (top), 9 (middle), and 15 (bottom), applied on raw data. For this dataset, the optimal depth of a single tree is 9 and the tree with the optimal depth is depicted as rtree 9 in each plot. The green dashed line indicates the median score of the rtree. All boxplots are obtained by 10 different runs. Figure S13 : Higgs dataset. Second-layer tree structure of depth 5 when the first-layer tree is of depth 2 (low depth). Raw features range from X[0] to X [13] , X [14] and X [15] are the features built by the first-layer tree. Figure S18 : Yeast dataset. Second-layer tree structure of depth 4 when the first-layer tree is of depth 3 (optimal depth). Raw features range from X[0] to X [7] . The features built by the first-layer tree range from X [8] to X [17] . Figure S20 : Airbnb dataset. Second-layer tree structure of depth 28 when the first-layer tree is of depth 26 (optimal depth). We only show the first part of the tree up to depth 5. Raw features range from X[0] to X [12] , X [13] is the feature built by the first-layer tree. Figure S21 : Housing dataset. R 2 score of a two-layer tree architecture w.r.t. the second-layer tree depth, when the first-layer (encoding) tree is of depth 3 (top), 7 (middle), and 12 (bottom). rtree is a single tree of respective depth 3 (top), 7 (middle), and 12 (bottom), applied on raw data. For this dataset, the optimal depth of a single tree is 9 and the tree with the optimal depth is depicted as rtree 7 in each plot. The green dashed line indicates the median score of the rtree. All boxplots are obtained by 10 different runs. Figure S36 : Illustration of the theoretical bounds of Proposition 2, when the first-layer tree is of depth k = 4 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation. Figure S37 : Illustration of the theoretical bounds of Proposition 2, when the first-layer tree is of depth k = 6 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation. Figure S38 : Illustration of the theoretical bounds of Proposition 3, when the first-layer tree is of depth k = 2 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation. Note that in such a case, the theoretical lower bound is constant and equal to the bias term. Figure S39 : Illustration of the theoretical bounds of Proposition 3, when the first-layer tree is of depth k = 4 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation. Note that the lower bound and the upper bound are merged. Figure S40 : Illustration of the theoretical bounds of Proposition 3, when the first-layer tree is of depth k = 6 (when k = 4) and p = 0.8. We draw a sample of size n (x-axis), and a shallow tree network r k,1,n is fitted for which the theoretical risk is evaluated. Each boxplot is built out of 20 000 repetitions. The outliers are not shown for the sake of presentation.
Lemma S4. Let Z be a binomial B(n, p), p ∈ (0, 1], n > 0. Then,
2n + 1
(vii) Let Z be a binomial B(n, 1 2 ), n > 0. Then,
Proof. The reader may refer to [4, Lemma 11 ] to see the proof of (ii), (iii) and the right-hand side of (i). The left-hand side inequality of (i) can be found in [7, Section 1.].
(iv) The first two inequalities rely on simple analysis :
To go on, we adapt a transformation from [7, Section 2.] to our setting: after the change of variable (1 − p + pe −t ) = e −r . Let's prove that
It holds that log(1 + x) ≤ 2x 2+x when −1 < x ≤ 0, therefore
and then dividing by rp 2 ,
which proves (1).
Equation (1) leads to
Note that Γ(1/2) = √ π. After the change of variable u = √ rn, we obtain :
which ends the proof of (iv).
(v).(a) We recall that p = 1/2. An explicit computation of the expectation yields :
We use that for all m ∈ 2N * ,
and
where the last inequality can be obtained via a series expansion at n = ∞. Replacing the terms by their bounds, we have :
which ends the proof of this item (v)(a).
(v).(b) We also begin with an explicit computation of the expectation :
The computation of the upper bound relies on the following inequalities : ∀m ∈ 2N * ,
as well as
πn where the last bound can be found via a series expansion at n = ∞. Replacing all terms by their bound and simplifying roughly gives the result.
Lemma S5 (Uniform Bernoulli labels: risk of a single tree). Let K be a compact in R d , d ∈ N. Let X, X 1 , ..., X n , n ∈ N * be i.i.d random variables uniformly distributed over K, Y, Y 1 , ..., Y n i.i.d Bernoulli variables of parameter p ∈ [0, 1] which can be considered as the labels of X, X 1 , ..., X n . We denote by r 0,k,n , k ∈ N * a single tree of depth k. Then we have, for all k ∈ N * ,
Proof. (i) In the case k = 0, r 0,0,n simply computes the mean of all the (Y i )'s over K:
(ii)
Noticing that N n (C n (X)) is a binomial B(n, 1 2 k ), we obtain the upper bound using Lemma S4 (i) :
the lower bound is immediately obtained by applying Lemma S4, (i):
S3 Proof of Lemma 1
First, note that since we are in an infinite sample regime, the risk of our estimators is equal to their bias term. We can thus work with the true distribution instead of a finite data set.
(i) When k < k , the first tree is biased, since the optimal depth is k . The second tree has access to the raw features or to the new feature created by the first tree. Since, for all leaves C of the first tree, P[Y = 1|X ∈ C] = 0.5, the new feature created by the first tree is non-informative (since it is constant, equal to 0.5). Therefore, the second-layer may use only raw feature and is consequently optimal if and only if k ≥ k .
(ii) When k ≥ k , the first tree is unbiased since each of its leaves is included in only one chessboard data cell. Splitting on the new feature in the second-layer tree induces a separation between cells for which P[Y = 1|X ∈ C] = p and cells for which P[Y = 1|X ∈ C] = 1 − p since p = 1/2. Taking the expectation of Y on this two regions leads to a shallow tree network of risk zero.
1. Assume that k < k . Recall that if a cell is empty, the tree prediction in this cell is set (arbitrarily) to zero. Thus, E (r k,0,n (X) − r(X)) 2 = E (r k,0,n (X) − r(X)) 2 1 Nn(Cn(X))>0 + E (r(X)) 2 1 Nn(Cn(X))=0 ,
where E (r(X)) 2 1 Nn(Cn(X))=0 = E (r(X)) 2 1 Nn(Cn(X))=0 1 X∈B + E (r(X)) 2 1 Nn(Cn(X))=0 1 X∈W
We now study the first term in (16) , by considering that X falls into B (the same computation holds when X falls into W). Letting (X , Y ) a generic random variable with the same distribution as (X, Y ), one has
where we used the fact that E [Y |X ∈ C n (X)] = 1/2 as in any leaf there is the same number of black and white cells. Moreover, conditional to N n (C n (X)), Xi∈Cn(X) Y i is a binomial random variable with parameters B(N n (C n (X)), 1 2 ). Hence we obtain :
The same computation holds when X falls into W. Indeed, the left-hand side term in (22) is unchanged, as for the right-hand side term, note that (
Injecting (26) into (16), we have E (r k,0,n (X) − r(X)) 2 (27)
Noticing that N n (C n (X)) is a binomial random variable B(n, 1 2 k ), we obtain the upper and lower bounds with Lemma S4 (i):
and,
Gathering all the terms gives the result,
and E (r k,0,n (X) − r(X)) 2 ≥ p − 1 2 2 + 2 k 4(n + 1)
2. As in the proof of 1., we distinguish the case where the cell containing X might be empty, in such a case the tree will predict 0: E (r k,0,n (X) − r(X)) 2 ) = E (r k,0,n (X) − r(X)) 2 1 Nn(Cn(X))>0 + E (r(X)) 2 1 Nn(Cn(X))=0 (33) = E (r k,0,n (X) − r(X)) 2 1 Nn(Cn(X))>0 + (
We denote by L 1 , ..., L 2 k the leaves of the tree. Let b ∈ {1, . . . , 2 k } such that L b belongs to B.
We have
Remark that the above computation holds when X ∈ W after replacing p by (1 − p), B by W and L b by L w : indeed when Y is a Bernoulli random variable, Y and 1 − Y have the same variance. Hence, using Equation (34), the computation in (40) and its equivalence for W, we obtain E (r k,0,n (X) − r(X)) 2 )
since N n (L b ) and N n (L w ) are both binomial random variables B(n, 1 2 k ). Therefore, as in the proof of 1., we can conclude using Lemma S4 (i) :
Let k ∈ N. Denote by L k = {L i,k , i = 1, . . . , 2 k } the set of all leaves of the encoding tree (of depth k). We let LB k be the set of all cells of the encoding tree containing at least one observation, and such that the empirical probability of Y being equal to one in the cell is larger than 1/2, i.e.
Accordingly, we let the part of the input space corresponding to LB k as
S5.1 Proof of 1. (i) (lower-bound for the case k < k )
Recall that k < k . In this case, each leaf of the encoding tree is contains half black square and half white square (see Figure 8a) . Hence, the empirical probability of Y being equal to one in such leaf is close to 1/2. Recalling that our estimate is r k,1,n , we have
Note that X / ∈B k ∪W k is equivalent to X belonging to an empty cell. Besides, the prediction is null by convention in an empty cell. Therefore, the sum of the last two terms in (41) can be written as
To begin with we focus on the first two terms in (41). We deal with the last two terms at the very end as similar computations are conducted.
Regarding the left-hand side term in (43),
since p > 1/2 and, by definition ofB k ,
Now, regarding right-hand side term in (43), we let
where N 1 , ..., N 2 k denote the number of data points falling in each leaf L 1 , . . . , L 2 k of the encoding tree. Hence,
The cross-term is null according to the definition of ZW k , and since (ZW k −N n (W k )) is (N 1 , ..., N 2 k ,W k )measurable. Therefore,
where I n and J n can be respectively identified as variance and bias terms. Indeed,
is the variance of a binomial random variable B(N n (W k ), 1 2 ) conditioned to be lower or equal to N n (W k )/2. According to Technical Lemma S6, we have
Regarding J n ,
we deduce
and 1 2 ) conditioned to be lower or equal to N n (W k )/2. Using Lemma S4 (vi), we obtain :
Therefore,
since, according to Cauchy-Schwarz inequality,
Overall
All together, we obtain
We apply Lemma S4(i)(iv) to N n (W k ) which is a binomial B(n, p ) where p = P(X ∈W k |W k ) :
N n (W k ) W k ≤ 2 (n + 1)p ,
We deduce that I n + J n ≤ (p − 1 2 ) 2 + 2 k/2+2 (p − 1 2 ) √ πn · p + 2 (n + 1) · p 2 k + 1 2 + 2 k+2 π + 2 3k/2+2 π √ π + 3 · 2 2k+2 π 2 .
Finally, E (r k,1,n (X) − p) 2 1 X∈B 1 X∈B k + E (r k,1,n (X) − p) 2 1 X∈B 1 X∈W k ≤ p − 1 2 2 P X ∈B k , X ∈ B + E (I n + J n )P X ∈W k , X ∈ B|W k
Since for allB k , there is exactly the same number of black cells and white cells inB k , we have P X ∈W k , X ∈ B|W k = P X ∈W k |W k 2 , yielding E (r k,1,n (X) − p) 2 1 X∈B 1 X∈B k + E (r k,1,n (X) − p) 2 1 X∈B 1 X∈W k (62)
where ε 1 (k) =
The two intermediate terms of (41) can be similarly bounded from above. Indeed,
where, by definition ofW k ,
The first term in (66) can be treated similarly as above:
where
and the cross-term in (67) is null according to the definition of ZB k . Regarding I n , note that
is the variance of a binomial random variable B(N n (B k ), 1 2 ) conditioned to be strictly larger than N n (B k )/2. According to Technical Lemma S6, we have
To obtain the last inequality, notice that P B(N n (B k ), 1/2) > N n (B k )/2 = 1 2 − 1 2 P B(N n (B k ), 1/2) = N n (B k )/2 ≥ 1 2 1 − 1 π(n/2 + 1/4) ≥ 1 4
as soon as n ≥ 4. Regarding J n , we have
For all j, such that L j ⊂B k , E Xi∈Lj Y i | N j ,B k is a binomial random variable B(N j , 1 2 ) conditioned to be larger than (N j + 1)/2 . Then, according to Technical Lemma (vii)
.
Hence,
for N j ≥ 1. Thus,
All together, we obtain
The computation is similar to (62), with p = P X ∈B k |B k :
I n + J n ≤ p − 1 2 2 + 2 k/2+3 (p − 1 2 ) √ πn · p + 2 k + 1 + 2 k+2 π p − 1 2 + 2 3k/2+2 π + 2 2k+2 π 2 2 (n + 1)p ≤ p − 1 2 2 + 2 k/2+3 (p − 1 2 ) √ πn · p + 2 2k+3 π 2 (n + 1)p (1 + ε 2 (k)) with ε 2 (k) = π 2 2 (2k+3) 2 k + 1 + 2 k+2 π (p − 1/2) + 2 3k/2+2 π . Finally, E (r k,1,n (X) − (1 − p)) 2 1 X∈W 1 X∈B k + E (r k,1,n (X) − (1 − p)) 2 1 X∈W 1 X∈W k ≤E (I n + J n )P X ∈ W, X ∈B k |B k + p − 1 2 2 P X ∈ W, X ∈W k ≤E p − 1 2 2 + 2 k/2+3 (p − 1 2 ) √ πn · p + 2 2k+3 π 2 (n + 1)p (1 + ε 2 (k)) P X ∈ W, X ∈B k |B k + p − 1 2 2 P X ∈ W, X ∈W
Since for allB k , there is exactly the same number of black cells and white cells inB k , we have
yielding E (r k,1,n (X) − (1 − p)) 2 1 X∈W 1 X∈B k + E (r k,1,n (X) − (1 − p)) 2 1 X∈W 1 X∈W k (76)
πn + 2 2k+3 2 · π 2 (n + 1)
(1 + ε 2 (k)).
Gathering (42), (64) and (77), we have E (r k,1,n (X) − r(X)) 2 ≤ p − 1 2 2 + 2 k/2+3 (p − 1 2 ) √ πn + 7 · 2 2k+2 π 2 (n + 1) (1 + ε(k)) + p 2 + (1 − p) 2 2 1 − 1 2 k n where ε(k) = 6ε1(k)+ε2(k) 7 .
S5.2 Proof of 1. (ii) (lower-bound for the case k < k )
We have, according to (42), E (r k,1,n (X) − r(X)) 2 = E (r k,1,n (X) − r(X)) 2 1 Nn(Cn(X)>0) + E (r(X)) 2 1 Nn(Cn(X)=0) = E (r k,1,n (X) − r(X)) 2 1 Nn(Cn(X)>0) + p 2 + (1 − p) 2 2 P (N n (C n (X) = 0) .
(78)
We deduced Line (128) from the fact that Z 2 j is a positive random variable, (129) from Lemma (S4) (v), Line (130) from the fact that p > 1/2 and Line (131) from the inequality (3) on the binomial coefficient. Injecting (124) and (132) into (119) yields
where the last inequality relies on the fact that the N j , L j ⊂ B are i.i.d, with b ∈ 1, ..., 2 k be the index of a cell included in B. N j is a binomial random variable B(n, 2 −k ).
From the inequality Line (118), we deduce that as soon as n ≥ for any a ∈ R.
Choosing a = E [S], we obtain 