# Learning Multi-Layered GBDT Via Back Propagation

Zhendong Zhang
School of Electronic Engineering, Xidian University
Xi’an, 710071, China
<EMAIL_ADDRESS>
###### Abstract

Deep neural networks are able to learn multi-layered representation via back
propagation (BP). Although the gradient boosting decision tree (GBDT) is
effective for modeling tabular data, it is non-differentiable with respect to
its input, thus suffering from learning multi-layered representation. In this
paper, we propose a framework of learning multi-layered GBDT via BP. We
approximate the gradient of GBDT based on linear regression. Specifically, we
use linear regression to replace the constant value at each leaf ignoring the
contribution of individual sample to the tree structure. In this way, we
estimate the gradient for intermediate representations, which facilitates BP
for multi-layered GBDT. Experiments show the effectiveness of the proposed
method in terms of performance and representation ability. To the best of our
knowledge, this is the first work of optimizing multi-layered GBDT via BP.
This work provides a new possibility of exploring deep tree based learning and
combining GBDT with neural networks.

##  1 Introduction

Deep neural networks have achieved outstanding breakthrough of machine
learning in recent years [12]. Feature engineering is important for
traditional machine learning methods that lack the ability to learn
intermediate representation from raw data. However, deep neural networks can
learn good representations from raw data [1], which is believed to be one of
the key advantages beyond traditional methods. This is achieved by
constructing multi-layered neural networks and learning hierarchical
representations. Although many learning strategies have been proposed for
training deep neural networks such as target propagation [19] and layer-wise
greedy training [14], back propagation (BP) [23] with stochastic gradient
descent is still the dominant approach. BP is used to compute the gradients of
parameters layer by layer in the inverse direction. On the other hand, tree
based ensembles such as random forest [3] and gradient boosting decision trees
(GBDT) [10, 4] (we just name a few representative works) are still the best
choice of modeling tabular data because of not only their performance but also
their computational efficiency and interpretability. However, there are no
hierarchical representations of these models which limit their expressiveness.
How can we construct multi-layered tree ensembles?

Recently, researchers have explored this issue popularly. Zhou and Feng [28]
proposed a deep forest framework, which was the first attempt to construct a
multi-layered model using tree ensembles. They introduced fine-grained
scanning and cascading operations and constructed a multi-layered structure
with adaptive model complexity. However, the representation learning ability
of deep forest was difficult to explicitly examine. Later, Feng et al. [9]
proposed the first multi-layered structure called mGBDT using gradient
boosting decision trees as building blocks per layer with an explicit emphasis
on its representation learning ability. mGBDT was learned via target
propagation. Specifically, targets were approximated and propagated by a set
of inverse functions corresponding to the forward functions. Both inverse and
forward functions were constructed by GBDT. Such explorations showed the
feasibility of learning hierarchical tree ensembles. Their results
demonstrated that tree ensembles were beneficial from multi-layered
representations. Several methods of differentiable and probabilistic decision
trees have been proposed [11, 18, 22, 13, 25, 8]. The probability of going to
the left branch was determined by the inner product between inputs and learned
tree parameters. Training this kind of decision trees was similar to training
neural networks. For traditional decision trees used in GBDT, the left branch
and right branch were split by a threshold along one of the features in a
deterministic manner. Since probability decision trees are different from the
ones used in GBDT in terms of hypothesis space and training methodology, [11,
18, 22, 13, 25, 8] are outside the scope of this work.

Researchers also have explored combining GBDT with neural networks. [17]
distills the learned representations of GBDT into deep neural networks. In
[15], the inputs are first processed by GBDT then processed by graph neural
networks. GBDT is learned via the gradients provided by graph neural networks.
Although the accuracy is improved, the combination mechanism is restricted.

In this work, we focus on traditional decision trees. We learn multi-layered
GBDT via BP which is different from mGBDT. Since GBDT is non-differentiable
and non-parametric, it seems impossible to apply BP to GBDT. Our solution to
this problem is as follows: we replace the constant value at each leaf with
linear regression, called piece-wise linear GBDT (GBDT-PL) in a recent work
[24]. We first learn the structure of each regression tree, and use it to
decide the set of inputs belonging to each leaf. We apply linear regression to
each leaf to obtain the optimal linear parameters $\mathbf{w}$. Then, we
express the gradient of output w.r.t its input in terms of $\mathbf{w}$ (see
Section 3 for details). Note that this is an approximated gradient because the
true gradient depends on not only the linear parameters but also the structure
of trees. When samples for training become massive, it is reasonable to assume
individual sample has little effect on the structure of trees. In fact, a
series of works indicates that the true gradient is not necessary for updating
parameters [2, 5, 20]. When we stack multi layers of GBDT, the gradient
information can be propagated from the final output to the input layer by
layer via BP. Then, we update the variables of hidden layers along the
direction of gradient descent and re-train GBDT to fit those updated hidden
variables. Although we could compute the gradient of $\mathbf{w}$ in a similar
way, it is unnecessary to do that during the BP process. We obtain
$\mathbf{w}$ by linear regression after the structure of trees is learned,
instead of gradient descent. We call the proposed method as GBDT-BP. We
evaluate GBDT-BP in terms of performance and representation learning ability
on both synthetic data and real-world data. Compared with existing methods,
our main contributions and novelties are as follows:

  * •

Although the idea of combining GBDT and linear regression at leaves appears
earlier, this is the first work to explicitly point out that such a
combination leads to an approximately differentiable model.

  * •

This is the first work to learn multi-layered GBDT via BP which provides a new
possibility of exploring deep tree based learning and combining GBDT with
neural networks. In principle, GBDT-BP and neural networks can be combined in
arbitrary way.

##  2 Background

###  2.1 Back Propagation

Back propagation (BP), shorthand for ”backward propagation of errors”, is a
method to compute the gradients w.r.t. the weights of multi-layered neural
networks which has become the key ingredient of the training algorithm of deep
neural networks. Although BP is originally proposed for neural networks, in
principle it can be utilized to compute the gradients of any layer structured
differentiable models. Thus, we formalize the process of BP beyond neural
networks as follows.

Denote $\mathcal{L}$ as the final loss and $\mathbf{h}_{i}$ as the hidden
vector of $i$-th layer. Denote $f_{\mathbf{w}_{i}}$ as the feed forward
function of $i$-th layer parameterized by $\mathbf{w}_{i}$. That is,
$\mathbf{h}_{i}=f_{\mathbf{w}_{i-1}}(\mathbf{h}_{i-1})$. Given the gradients
of $\mathbf{h}_{i}$, BP computes the gradients of $\mathbf{h}_{i-1}$ and
$\mathbf{w}_{i-1}$ as follows:

$\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{i-1}}=\left(\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{h}_{i-1}}\right)^{T}\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{i}}$
(1)
$\frac{\partial\mathcal{L}}{\partial\mathbf{w}_{i-1}}=\left(\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{w}_{i-1}}\right)^{T}\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{i}}$
(2)

where $\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{h}_{i-1}}$ and
$\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{w}_{i-1}}$ are jacobians. From
(1), the gradients of the $i$-th layer are propagated to the $(i-1)$-th layer.
Then, the same rule is applied layer by layer until the inputs. In this way,
the gradients of $\mathbf{w}$ at all layers are obtained.

BP requires that the model is differentiable or the gradient can be evaluated
within acceptable computational complexity. A series of works is proposed to
overcome these limitations of BP in particular situations. [2] proposed
straight through estimator to learn binary variables. [20] proposed relaxation
methods to learn a particular discrete probability distribution. [5] proposed
the synthetic gradient which reduces the computation and communication
complexity for distributed training. Their model is updated using the
synthetic gradient instead of the true gradient. The effectiveness of these
works indicates that it is a good choice to use the approximated gradient when
the model is non-differentiable or the true gradient is too expensive to
evaluate.

###  2.2 Gradient Boosting Decision Trees

Boosting is a widely used strategy for ensemble learning [27]. Boosting
algorithms iteratively add weak learners into the final strong learner. The
construction of each weak learner is usually guided by the gradient of current
predictions, i.e. gradient boosting. When we choose decision trees as the weak
learner, we get gradient boosting decision trees. Formally, denote
$\mathcal{M}$ as the function of an individual tree. The prediction of GBDT is
the summation of all trees:

$\hat{y}=\sum_{i=1}^{N}\mathcal{M}_{i}(x)$ (3)

Given the first $N$ trees, the $(N+1)$-th tree is grown by fitting current
negative gradient w.r.t. $\hat{y}$. GBDT is first proposed in [10]. It is
still the best choice for modeling tabular data which spans a broad range of
real-world applications.

The most important problem of GBDT is how to split a node. The quality of
splitting is measured by some objectives. Thus, this problem is cast to
choosing suitable objectives. Traditional GBDTs use so-called “friedman mse”.
Recent implementations for GBDTs such as XGBoost [4] and LightGBM [16] use not
only the first order gradient but also the second order gradient to guide the
learning of each tree. [4] firstly derived the corresponding splitting
objective which is a generalization of “friedman mse”. When the second order
gradient is a constant, their proposed objective is equivalent of “friedman
mse”.

Another problem of GBDT is how to compute the predictions of each leaf. A
constant value is usually used. For traditional GBDT, this value equals the
mean of the negative gradient as follows:

$\frac{1}{N}\sum_{i\in leaf}-g_{i}$ (4)

where $N$ is the number of samples belonging to the same leaf and $g$ is the
gradient. For implementations using second order gradient, the leaf value
equals to the negative gradient weighted by second order gradient.

$\frac{-\sum_{i\in leaf}g_{i}}{\lambda+\sum_{i\in leaf}g^{\prime}_{i}}$ (5)

where $g^{\prime}$ is the second order gradient and $\lambda$ is the strength
of $L_{2}$ regularization. [6] replaced the constant leaf value with linear
regression to derive the corresponding spitting objective.

Figure 1: Flow of GBDT-BP with two hidden layers. We update the hidden
variables via gradient descant and retrain decision trees to fit the updated
ones. $x$ and $y$ are the input and output respectively. $h$ is the hidden
representation and $g$ is its gradient. $\alpha$ is the learning rate, while
$T$ is the GBDT model. The subscripts 1 and 2 indicate the number of layers.

##  3 Proposed Method

In this section, we describe the proposed method in a top-down manner. We
first provide the overall learning algorithm. Then, we show how to compute the
gradient of GBDT. Finally, we describe how to learn the linear regression at
each node. Implementation details are also discussed.

###  3.1 Overall Learning Algorithm

Consider a multi-layered structure with $L-1$ hidden layers. Denote
$\mathbf{h}_{i}\in\mathbf{R}^{d_{i}}$ where $i\in\\{0,1,2,\dots L\\}$ as the
hidden variables of $i$-th layer with dimension $d_{i}$. For convenience,
denote $\mathbf{h}_{0}$ and $\mathbf{h}_{L}$ as the input and the final output
layer respectively. Except for the input layer, each element of
$\mathbf{h}_{i}$ is obtained by a GBDT with $\mathbf{h}_{i-1}$ as its input.
That is, $\mathbf{h}_{i}$ is a concatenation of the outputs of $d_{i}$ GBDTs.
Note that we replace the constant prediction at each leaf with linear
regression to make GBDT approximate differentiable.

Given a differentiable loss $\mathcal{L}$, the gradient of $L$-th layer is
obtained directly. It is required to compute the gradient of all hidden
layers. Suppose that the jacobian of any two adjacent layers is given (we will
describe how to compute it for GBDT in Section 3.2). Then, we can compute the
gradient of all hidden layers via BP as in (1). Although the BP process is
similar to deep neural networks, the update rule is significantly different.
For neural networks, their parameters are updated directly by (stochastic)
gradient descent. Recall that there are linear parameters learned at each leaf
and thus the model becomes parametric. However, it is meaningless to apply
gradient descent to these parameters. It is meaningful only when the tree
structure is fixed. Unfortunately, the tree structure is dynamically changed
during training. Thus, it is unnecessary to compute the gradient of the linear
parameters and update them. We only update the hidden variables via gradient
descent as follows:

$\mathbf{h}_{i}\leftarrow\mathbf{h}_{i}-\alpha\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{i}}$
(6)

where $\alpha$ is the learning rate. Then, we clean previously learned GBDTs
and train new ones from scratch to fit the updated hidden variables based on
mean square error (MSE). Note that when we re-train new GBDTs to fit the
updated $\mathbf{h}_{i}$, $\mathbf{h}_{i-1}$ has not been updated yet. That
is, hidden variables and GBDTs are updated alternately layer by layer in the
inverse direction. We summarize GBDT-BP in Algorithm 1 and provide the flow of
GBDT-BP with two hidden layers in Fig. 1.

Algorithm 1 Learning multi-layered GBDT via back propagation

Input: Number of layers $L$, training dataset
$\\{\mathbf{h}_{0},\mathbf{Y}\\}$, final loss function $\mathcal{L}$, learning
rate $\alpha$ for hidden variables, learning rate $\beta$ for GBDT and number
of boosters $N_{i}$

Output: Multi-layered GBDTs

Initialize forward function $\mathcal{T}_{i}$ of layer $i$ for $i=0,1,\dots
L-1$

repeat

// Forward for computing hidden variables

for $i=0$ to $L-1$ do

$\mathbf{h}_{i+1}=\mathcal{T}_{i}(\mathbf{h}_{i})$

end for

// Backward for computing gradients

$\mathbf{g}_{L}\leftarrow\frac{\partial\mathcal{L}(\mathbf{h}_{L},\mathbf{Y})}{\partial\mathbf{h}_{L}}$

for $i=L$ to $1$ do

$\mathbf{g}_{i-1}\leftarrow\left(\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{h}_{i-1}}\right)^{T}\mathbf{g}_{i}$
// How to compute the jacobian is described in section 3.2 and 3.3

end for

// Update hidden variables and fit GBDTs from scratch

for $i=L$ to $1$ do

$\mathbf{h}_{i}\leftarrow\mathbf{h}_{i}-\alpha\mathbf{g}_{i}$

$\mathcal{T}_{i-1},\hat{\mathbf{h}}\leftarrow\\{\\},0$ // Initialize to an
empty list

for $j=1$ to $N_{i}$ do

$\mathbf{r}\leftarrow\hat{\mathbf{h}}-\mathbf{h}_{i}$ // Gradient of MSE

$\mathcal{M}\leftarrow RegressionTree(\mathbf{h}_{i-1},-\mathbf{r})$ // Fit
regression tree with variables of previous layer and negative gradient

$\hat{\mathbf{h}}\leftarrow\hat{\mathbf{h}}+\beta\mathcal{M}(\mathbf{h}_{i-1})$

Append $\mathcal{M}$ to $\mathcal{T}_{i-1}$

end for

end for

until convergence

Return: $\\{\mathcal{T}_{0},\mathcal{T}_{1},\dots\mathcal{T}_{L-1}\\}$

###  3.2 Gradient of GBDT Layer

We compute the jacobian of two adjacent GBDT layers to propagate the gradient
as follows. We first formalize a single regression tree. Here, it is not our
interest how the tree structure is determined. We suppose the tree structure
is fixed. Denote $\mathcal{M}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ as the
function of a tree as follows:

$\mathcal{M}(\mathbf{x})=\sum_{i\in leaf}\mathcal{I}(\mathbf{x}\in
i)f_{\mathbf{w}_{i}}(\mathbf{x})$ (7)

where $leaf$ is a set of leaves, $\mathcal{I}$ is the indicator function and
$f_{\mathbf{w}_{i}}$ is the function of leaf $i$. That is, we first decide
which leaf an input belongs to, then we compute the prediction of that leaf.
The gradient of $\mathcal{M}$ w.r.t its input is as follows:

$\frac{\partial\mathcal{M}(\mathbf{x})}{\partial\mathbf{x}}=\sum_{i\in
leaf}\mathcal{I}(\mathbf{x}\in i)\frac{\partial
f_{\mathbf{w}_{i}}(\mathbf{x})}{\partial\mathbf{x}}+\frac{\partial\mathcal{I}(\mathbf{x}\in
i)}{\partial\mathbf{x}}f_{\mathbf{w}_{i}}(\mathbf{x})$ (8)

The indicator function should be fixed if we suppose the tree structure is
fixed. This means $\frac{\partial\mathcal{I}(\mathbf{x}\in
i)}{\partial\mathbf{x}}=0,\forall i\in leaf$. That is, an individual sample
has no effect on the tree structure. This is not true but it is a good
approximation as the training samples become massive. Then, the gradient is
simplified as:

$\frac{\partial\mathcal{M}(\mathbf{x})}{\partial\mathbf{x}}=\sum_{i\in
leaf}\mathcal{I}(\mathbf{x}\in i)\frac{\partial
f_{\mathbf{w}_{i}}(\mathbf{x})}{\partial\mathbf{x}}$ (9)

Note that if $f$ is a constant function, the gradient degrades to 0. In this
case, we are not able to learn multi-layered GBDT via BP. This is why we
replace the constant value with linear regression. We have derived the
gradient of an individual regression tree. Since the prediction of GBDT is the
summation of the predictions of all regression trees, the gradient of GBDT is
easily obtained. Denote $\mathcal{T}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ as
the function of GBDT. Then, we get:

$\frac{\partial\mathcal{T}}{\partial\mathbf{x}}=\sum_{i}\frac{\partial\mathcal{M}_{i}}{\partial\mathbf{x}}$
(10)

Suppose given $\mathbf{h}_{i-1}$, $j$-th element of $\mathbf{h}_{i}$ is
predicted by $j$-th GBDT, i.e. $\mathcal{T}^{j}$. Then, the jacobian is as
follows:

$\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{h}_{i-1}}=\left(\frac{\partial\mathcal{T}^{0}}{\partial\mathbf{h}_{i-1}},\frac{\partial\mathcal{T}^{1}}{\partial\mathbf{h}_{i-1}},\dots\frac{\partial\mathcal{T}^{d_{i}}}{\partial\mathbf{h}_{i-1}}\right)^{T}$
(11)

Once we get the jacobian, we can propagate the gradient of multi-layered GBDT
using (1).

###  3.3 Linear Regression at Leaves

Figure 2: Example of incremental feature selection. Each circle is a leaf,
while numbers in a circle are the selected features for that leaf.

The jacobian depends on leaf functions, and we describe how to learn leaf
functions. As mentioned earlier, the parameters of each leaf are learned by
linear regression. In [6], all dimensions of inputs are used for linear
regression. However, the drawbacks of such a strategy are obvious, as
addressed in [24]. First, the computational cost is relatively high. Second,
given samples in a leaf, not all dimensions are useful for predicting their
targets, thus such a strategy has a high risk of over-fitting. Feature
selection is required. In this work, we follow the incremental feature
selection proposed in [24]. Given a leaf, we trace back its decision path. For
each node in the decision path, there is a dimension used to split. We collect
all splitting dimensions that appeared in the decision path. Then, we only use
those dimensions to learn the linear regression model. As shown in Fig. 2, the
number of selected dimensions is no more than the depth of trees. Those
dimensions are relevant to the targets. Another useful trick for linear
regression is extending the feature dimensions based on some transforms, which
increases the capacity of linear regression.

Denote $\mathbf{x}\in\mathbb{R}^{d}$ as a sample with $d$ dimensions. Here, we
suppose these $d$ dimensions are already captured by incremental feature
selection. Denote $\mathbf{X}\in\mathbb{R}^{n\times d}$ as a collection of $n$
samples belonging to the same leaf. Denote $\mathbf{y}\in\mathbb{R}^{n}$ as
their current targets (negative residuals). Denote $\phi$ as the feature
extending function. Then, the objective of linear regression is as follows:

$\Arrowvert\phi(\mathbf{X})\mathbf{w}-\mathbf{y}\Arrowvert_{2}^{2}+\frac{\lambda}{2}\mathbf{w}^{T}\mathbf{w}$
(12)

where $\lambda$ is the strength of $L_{2}$ regularization. The solution of
(12) is as follows:

$\mathbf{w}^{*}=[\phi(\mathbf{X})^{T}\phi(\mathbf{X})+\lambda\mathbf{I}]^{-1}\phi(\mathbf{X})^{T}\mathbf{y}$
(13)

Then, the predictions of this leaf is as follows:

$f_{\mathbf{w}^{*}}(\mathbf{x})=\phi(\mathbf{x})^{T}\mathbf{w}^{*}$ (14)

The gradient of the leaf function is as follows:

$\frac{\partial
f_{\mathbf{w}^{*}}(\mathbf{x})}{\partial\mathbf{x}}=\left(\frac{\partial\phi(\mathbf{x})}{\partial\mathbf{x}}\right)^{T}\mathbf{w}^{*}$
(15)

It is easy to choose a differentiable $\phi$. From Sections 3.2 and 3.3, we
get the jacobian of GBDT layers and thus back propagation is operational.

###  3.4 Implementation Details

For each regression tree, we use $DecisionTreeRegressor$ in scikit-learn
package [21] which splits a node based on “friedman mse”. Although recent
second order based implementations show better performance, there is no
significant difference in our case because MSE is used as the loss function to
fit hidden variables. Although [6] developed a novel splitting objective for
linear regression at leaves, we still use “friedman mse” for a fair comparison
and easy implementation. The splitting objective is not the goal of this work.
For feature extending function, we set $\phi$ as follows:

$\phi(\mathbf{x})=[1,\mathbf{x},\mathbf{x}^{2}]$ (16)

Other choices for feature extending can be possible.

Momentum is commonly used when training neural networks with stochastic
gradient descent to speed up the learning process. We introduce this technique
into GBDT-BP as follows. Denote $\mathbf{m}_{i}$ as the momentum of
$\mathbf{h}_{i}$ as follows:

$\mathbf{m}_{i}\leftarrow\mu\mathbf{m}_{i}+(1-\mu)\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{i}}$
(17)

When we update $\mathbf{h}_{i}$, we replace its gradient with $\mathbf{m}_{i}$
in (6). We set $\mu=0.5$ and $\alpha=0.5$ in all experiments. Hidden variable
$\mathbf{h}$ is initialized as random Gaussian noise.

(a) Circle (b) Epoch $2$ (c) Epoch $4$ (d) Epoch $6$ (e) Epoch $11$ (f) Epoch
$13$ (g) Epoch $17$ (h) Epoch $23$

Figure 3: Progress of hidden representations on $Circle$. We train a 2-2-2
multi-layered GBDT for binary classification to learn meaningful hidden
representations.

(a) Curve (b) Epoch $2$ (c) Epoch $4$ (d) Epoch $6$ (e) Epoch $10$ (f) Epoch
$15$ (g) Epoch $25$ (h) Epoch $47$

Figure 4: Progress of final reconstructions on $Curve$. We train a 3-2-3
multi-layered GBDT as an auto-encoder to learn the 2D manifold of 3D data.

##  4 Experiments

Table 1: RMSE comparison for fitting a random neural network function. Method | RMSE | Constant Leaf | Multi Layer
---|---|---|---
GBDT | 0.01867 $\pm$ 0.00023 | $\surd$ | $\times$
XGBoost | 0.01886 $\pm$ 0.00018 | $\surd$ | $\times$
GBDT-PL | 0.01861 $\pm$ 0.00022 | $\times$ | $\times$
GBDT-BP | 0.01775 $\pm$ 0.00026 | $\times$ | $\surd$
Table 2: Classification accuracy on Income Prediction and Protein Localization datasets. NN is fully connected neural networks, while ∗ indicates the result is reported from literature [9].  Method | Income Prediction | Protein Localization | Drug Consumption | MNIST-3000
---|---|---|---|---
XGBoost | 0.8721 | 0.5951 $\pm$ 0.0341 | 0.7040 $\pm$ 0.0251 | 0.9242
GBDT-MO | 0.8730 | 0.6079 $\pm$ 0.0303 | 0.7047 $\pm$ 0.0237 | 0.9263
GBDT-PL | 0.8726 | 0.6037 $\pm$ 0.0308 | 0.6962 $\pm$ 0.0265 | 0.9254
NN | 0.8543∗ | 0.5907 $\pm$ 0.0268∗ | 0.6954 $\pm$ 0.0291 | 0.9305
mGBDT | 0.8742∗ | 0.6160 $\pm$ 0.0323∗ | 0.6990 $\pm$ 0.0321 | 0.9284
GBDT-BP | 0.8741 | 0.6186 $\pm$ 0.0296 | 0.7063 $\pm$ 0.0306 | 0.9317
Table 3: Classification accuracy on Protein Localization dataset with varying number of layers. The dimension of all hidden layers is 16. NN is fully connected neural networks, while ∗ indicates that the result is reported from literature [9]. Hidden Layer | NN∗ | mGBDT∗ | GBDT-BP
---|---|---|---
1 | 0.5803 $\pm$ 0.0316 | 0.6160 $\pm$ 0.0323 | 0.6186 $\pm$ 0.0296
2 | 0.5907 $\pm$ 0.0268 | 0.5948 $\pm$ 0.0268 | 0.5938 $\pm$ 0.0382
3 | 0.5901 $\pm$ 0.0270 | 0.5897 $\pm$ 0.0312 | 0.5882 $\pm$ 0.0461
4 | 0.5768 $\pm$ 0.0286 | 0.5782 $\pm$ 0.0229 | 0.5751 $\pm$ 0.0291

We first evaluate GBDT-BP on two synthetic datasets: _Circle_ and _Curve_. We
train GBDT-BP on them in supervised setting and unsupervised setting,
respectively. Then, we compare the function approximation capability of GBDT-
BP by fitting a random neural network. Finally, we evaluate GBDT-BP on three
tabular datasets and _MNIST_ 111http://yann.lecun.com/exdb/mnist/. All tabular
datasets are from UCI [7]: _Income Prediction_
222http://archive.ics.uci.edu/ml/datasets/Adult, _Protein Localization_
333http://archive.ics.uci.edu/ml/datasets/Yeast, and _Drug Consumption_
444https://archive.ics.uci.edu/ml/datasets/
Drug+consumption+%28quantified%29. _Income Prediction_ and _Protein
Localization_ are also used in [9], and we choose them for a fair comparison.
We obtain the best performance by adjusting the depth of trees and the number
of boosters as [9]. GBDT-BP is convergent within 60 epochs for all datasets.

We denote $\mathcal{U}$ is a uniform distribution, while $\mathcal{N}$ is a
normal distribution.

###  4.1 Synthetic Data

_Circle_ : This dataset is used for binary classification as shown in Fig.
3(a). The angle of each point is sampled from $\mathcal{U}(0,2\pi)$. The
radius of blue points is sampled from $\mathcal{U}(0.8,1.0)$, while the radius
of red points is sampled from $\mathcal{U}(0.4,0.6)$. In this way, we generate
$10000$ points for training. We build a single hidden layer GBDT-BP model with
structure $2\rightarrow 2\rightarrow 1$. The maximum tree depth is set to 6
and the number of boosters per GBDT is set to 8. We show how hidden
representations progress in Fig. 3. It is obvious that the learned hidden
representations make the classification easier. At the end of the progress, we
can completely separate them by a single node of a decision tree.

_Curve_ : This dataset is used for self-reconstruction as shown in Fig. 4(a).
Each 3D point is sampled by:

$[t,\mathcal{N}(0,0.05)+\sin t,\mathcal{N}(0,0.05)+\cos t]$ (18)

where $t$ is $\mathcal{U}(-1,1)$. Those points belong to a 2D manifold.

We generate $10000$ points for training. We train a GBDT-BP auto-encoder with
structure $3\rightarrow 2\rightarrow 3$. The maximum tree depth is set to 5
and the number of boosters per GBDT is set to 32. We provide how final
reconstructions progress in Fig. 4. As shown in the figure, the 2D manifold is
successfully captured. Those results indicate that GBDT-BP is feasible in both
supervised setting and unsupervised setting. Moreover, it learns meaningful
hidden representations of data.

_Random neural network_ : We check the function approximation capability of
GBDT-BP by fitting it to a random neural network function. Specifically, the
input $\mathbf{x}\in\mathbb{R}^{32}$ is sampled from $\mathcal{U}(0,1)$. Its
corresponding target is computed by the following random initialized neural
network:

$Dense(32,16)\rightarrow ReLU\rightarrow Dense(16,1)$

We generate 6000 pairs of samples, and split them into training and test sets
by 10-fold cross-validation555We randomly split the samples into 10 folds. At
each time, we use one of those folds as test set, while we use the others as
training set. We repeat this process 10 times until all folds are used as test
set. We report mean and standard deviation of the results.. We compare GBDT-BP
with GBDT, XGBoost and GBDT-PL. Here, GBDT-PL is implemented by us as the
building block of GBDT-BP. We measure the performance in terms of root mean
square error (RMSE). The GBDT-BP model has a single hidden layer with 32
variables. The numbers of boosters are 40 and 200 for the first and second
layer. For single-layered models, we select the best RMSE within 2000
boosters. GBDT-BP is significantly better than others. From Table 1, it can be
observed that linear regression at leaves has no remarkable effects on the
performance. Thus, it can be concluded that the performance gain is
contributed by multi-layered representations.

###  4.2 Real Data

For real data, we compare GBDT-BP with GBDT-PL, XGBoost, fully connected
neural networks (NN) trained with back propagation, and mGBDT. Experimental
results are presented in Table 2. On every dataset, we keep the experimental
settings as same for all methods.

_Income Prediction_ : This dataset consists of 32561 training samples and
16281 test samples each of which contains social background of a person. We
predict whether this person makes over 50K a year based on its background.
After one-hot coding for categorical attributes, we get 113 features of each
sample as [9]. We train a GBDT-BP model with structure $113\rightarrow
32\rightarrow 1$.

_Protein Localization_ : This dataset is a 10 class classification task that
contains 1484 samples. There are 8 measurements of a protein sequence in each
sample. Our goal is to predict protein localization sites with 10 possible
choices. We evaluate and compare the accuracies of different methods via
10-fold cross-validation. For a fair comparison, we use exactly the same set
of folds as [9]. We train a GBDT-BP model using structure $8\rightarrow
16\rightarrow 10$. We also examine the effect of layers on this dataset. The
dimension for each hidden layer is fixed to be 16. As shown in Table 3,
although the test accuracies decrease as the the number of layers increases,
the results are stable. The results demonstrate the effectiveness of GBDT-BP
when training deeper models.

_Drug Consumption_ : This dataset is a 7 class classification task that
contains 1885 samples. There are 12 measurements of people’s personality
information in each sample. Our goal is to predict when drugs are used by a
person: ”never”, ”over a decade ago”, ”in last decade”, ”in last year”, ”in
last month”, ”in last week”, or ”in last day”. We evaluate and compare the
accuracies of different methods via 10-fold cross-validation. We train a GBDT-
BP model using structure $12\rightarrow 32\rightarrow 7$.

_MNIST-3000_ : MNIST (Mixed National Institute of Standards and Technology) is
a popular dataset for evaluating machine learning algorithms. There are 50000
training samples and 10000 test samples. Each sample is a $28\times 28$ gray
image which expresses one of digits from 0 to 9. Because training mGBDT
consumes a lot of memory, we only use the first 3000 samples for training. We
call this dataset MNIST-3000. We reshape each image to a vector before fitting
it into models. We train a GBDT-BP model using structure $784\rightarrow
64\rightarrow 10$. Experimental results are presented in Table 2.

The proposed method achieves the best performance except on _Income
Prediction_. The proposed method is obviously better than single-layered GBDT.
This indicates the benefits of multi-layered structure. The proposed method is
obviously better than single-layered GBDT-PL. This indicates the performance
gain is mainly contributed by multi-layered structure instead of the piece-
wise linear function of leaves. The proposed method is competitive with or
sightly better than mGBDT. This indicates the feasibility of training GBDT via
back propagation.

(a) GBDT-BP (b) NN (c) GBDT-NN (d) NN-GBDT

Figure 5: We visualize the hidden representations on _Protein Localization_ using T-SNE. The clusters of GBDT-BP have larger margin compared with NN. The representations of GBDT-NN is similar to GBDT-BP and the representations of NN-GBDT is similar to NN. Table 4: Classification accuracy on Protein Localization. Method | Income Prediction | Protein Localization
---|---|---
NN | 0.8543 |  0.5907 $\pm$ 0.0268
GBDT-BP | 0.8741 |  0.6186 $\pm$ 0.0296
NN-GBDT | 0.8611 |  0.6020 $\pm$ 0.0257
GBDT-NN | 0.8748 | 0.6203 $\pm$ 0.0281

###  4.3 Combination of GBDT and NN

Back propagation with gradient descant becomes a dominant learning paradigm of
neural networks. Training GBDT with back propagation makes it possible to
jointly train a model which combines GBDT and NN. This provides more
flexibility to design novel machine learning models.

There are two natural ways to combine GBDT and NN. We first construct GBDT
layers, then we construct NN layers following GBDT layers. We call it GBDT-NN.
Or we first construct NN layers, the we construct GBDT layers following NN
layers. We call it NN-GBDT. In this section, we evaluate GBDT-NN and NN-GBDT
on _Income Prediction_ and _Protein Localization_. We train models with
structure $113\rightarrow 32\rightarrow 1$ on _Income Prediction_ and models
with structure $8\rightarrow 32\rightarrow 10$ on _Protein Localization_. For
NN-GBDT, the NN layer is updated by 15 stochastic gradient descant steps in
each epoch.

Experiments are shown in Table 4. The results indicate the feasibility of
combining NN and GBDT. GBDT-NN achieves the best performance. GBDT-NN is much
better than NN-GBDT. One possible reason is that the approximated gradient by
GBDT-BP is not accurate and it may mislead the updating of NN. Better gradient
estimation algorithms of GBDT are helpful in the future. We also visualize the
hidden representations on _Protein Localization_ using T-SNE in Figure 5. The
clusters of GBDT-BP have larger margin compared with NN. This indicates that
GBDT-BP learns better hidden representations than NN. Moreover, the
representations of GBDT-NN is similar to GBDT-BP and the representations of
NN-GBDT is similar to NN. This indicates that the earlier layers may have
greater impact on the representations.

##  5 Discussions

mGBDT is the most related work to GBDT-BP. We highlight two differences
between them: 1) The main difference is how hidden variables are updated.
mGBDT updates them via target propagation by fitting a set of inverse
functions; 2) The final layer of mGBDT is a fully connected neural network
layer. The mixture of GBDT and neural network makes it difficult to recognize
the contribution of each part. When we train GBDT-BP with a smaller batch size
than the full batch size, the performance is slightly decreased. Thus, we
train GBDT-BP with full batch size in this work. As mentioned in Section 3.1,
once the hidden representations are updated, we re-train GBDTs from scratch.
An alternative way is that we keep previously trained GBDTs and train new
GBDTs to fit the change of hidden representations. Our consideration is that
the change of hidden representations is not consistent, thus leading to the
redundancy of trees. Training GBDT-BP is time-consuming because 1) it requires
many epochs; and 2) it requires multiple GBDTs in hidden layers. For the first
reason, we may need better updating rules. For the second reason, we may use
recently proposed GBDT-MO [26] to learn multiple outputs simultaneously. We
leave faster training as future works.

##  6 Conclusions and Future Works

We have proposed a method of learning multi-layered GBDT via back propagation.
We have achieved this by replacing the constant leaf value with linear
regression and approximating its derivatives. We have provided new
probabilities of learning deep tree based ensembles. Experiments on both
synthetic and real-world datasets verify that the proposed method outperforms
single-layered GBDT in terms of both performance and representation ability.
Moreover, the proposed method supports both supervised and unsupervised
learning.

## References

  * [1] Y. Bengio, A. Courville, and P. Vincent.  Representation learning: A review and new perspectives.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013.
  * [2] Y. Bengio, N. Léonard, and A. Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  arXiv preprint arXiv:1308.3432, 2013.
  * [3] L. Breiman.  Random forests.  Machine Learning, 45(1):5–32, 2001.
  * [4] T. Chen and C. Guestrin.  Xgboost: A scalable tree boosting system.  In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794. ACM, 2016.
  * [5] W. M. Czarnecki, G. Świrszcz, M. Jaderberg, S. Osindero, O. Vinyals, and K. Kavukcuoglu.  Understanding synthetic gradients and decoupled neural interfaces.  In Proceedings of the International Conference on Machine Learning, pages 904–912, 2017.
  * [6] L. de Vito.  Linxgboost: Extension of xgboost to generalized local linear models.  arXiv preprint arXiv:1710.03634, 2017.
  * [7] D. Dheeru and E. Karra Taniskidou.  UCI machine learning repository, 2017.
  * [8] J. Feng, Y.-X. Xu, Y. Jiang, and Z.-H. Zhou.  Soft gradient boosting machine.  arXiv preprint arXiv:2006.04059, 2020.
  * [9] J. Feng, Y. Yu, and Z.-H. Zhou.  Multi-layered gradient boosting decision trees.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3555–3565, 2018.
  * [10] J. H. Friedman.  Greedy function approximation: a gradient boosting machine.  Annals of Statistics, pages 1189–1232, 2001.
  * [11] N. Frosst and G. Hinton.  Distilling a neural network into a soft decision tree.  arXiv preprint arXiv:1711.09784, 2017.
  * [12] I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio.  Deep learning, volume 1.  MIT press Cambridge, 2016.
  * [13] H. Hazimeh, N. Ponomareva, P. Mol, Z. Tan, and R. Mazumder.  The tree ensemble layer: Differentiability meets conditional computation.  In International Conference on Machine Learning, pages 4138–4148. PMLR, 2020.
  * [14] G. E. Hinton.  A practical guide to training restricted boltzmann machines.  In Neural networks: Tricks of the trade, pages 599–619. Springer, 2012.
  * [15] S. Ivanov and L. Prokhorenkova.  Boost then convolve: Gradient boosting meets graph neural networks.  In International Conference on Learning Representations, 2020.
  * [16] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu.  Lightgbm: A highly efficient gradient boosting decision tree.  In Advances in Neural Information Processing Systems, pages 3146–3154, 2017.
  * [17] G. Ke, Z. Xu, J. Zhang, J. Bian, and T.-Y. Liu.  Deepgbm: A deep learning framework distilled by gbdt for online prediction tasks.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 384–394, 2019.
  * [18] P. Kontschieder, M. Fiterau, A. Criminisi, and S. Rota Bulo.  Deep neural decision forests.  In Proceedings of the IEEE Conference on Computer Vision, pages 1467–1475, 2015.
  * [19] D.-H. Lee, S. Zhang, A. Fischer, and Y. Bengio.  Difference target propagation.  In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 498–515. Springer, 2015\.
  * [20] C. J. Maddison, A. Mnih, and Y. W. Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  arXiv preprint arXiv:1611.00712, 2016.
  * [21] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [22] S. Popov, S. Morozov, and A. Babenko.  Neural oblivious decision ensembles for deep learning on tabular data.  In Proceedings of the International Conference on Learning Representations, 2020.
  * [23] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning representations by back-propagating errors.  Nature, 323(6088):533, 1986.
  * [24] Y. Shi, J. Li, and Z. Li.  Gradient boosting with piece-wise linear regression trees.  arXiv: Learning, 2018.
  * [25] R. Tanno, K. Arulkumaran, D. Alexander, A. Criminisi, and A. Nori.  Adaptive neural trees.  In International Conference on Machine Learning, pages 6166–6175. PMLR, 2019.
  * [26] Z. Zhang and C. Jung.  Gbdt-mo: Gradient-boosted decision trees for multiple outputs.  IEEE Transactions on Neural Networks and Learning Systems, 2020\.
  * [27] Z.-H. Zhou.  Ensemble learning.  Encyclopedia of Biometrics, pages 411–416, 2015.
  * [28] Z.-H. Zhou and J. Feng.  Deep forest: towards an alternative to deep neural networks.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 3553–3559, 2017.