这大概是GBDT最初的想法

【文章最初发表了我个人的公众号上点击查看，分了上下两篇，这里重新整理了下，并把表述不清晰的地方做了修改。】

GBDT(Gradient Boosting Decision Tree)梯度提升决策树，看到Gradient不免会想到梯度下降（上升），所以我们从梯度下降开始聊。

梯度下降

这里有一波数据$x = \{x_1, x_2, x_3, …, x_n \}, y = {y_1, y_2, y_3, …, y_n}$, 假设$x$和$y$的关系是

$$y = f(x) + \epsilon$$

于是$\hat{y}_i = f(x_i)$,其中$\hat{y}_i$是预测值，机器学习的过程就是通过数据集$[\textbf{x}, y]$来确定$f(x)$的过程。我们会用一个损失函数来$L(y, f(x:\theta))$来描述实际值跟假设的函数$f(x)$计算出的预测值的差异，于是我们认为在数据集$[\textbf{x},y]$上，使得损失函数最小化的那个$f(x)$就是我们要找的最合适的函数，标记成$f^*(x)$，数学描述

$$F^* = \arg \min_{F} E_{y,x} L(y, F(x)) = \arg \min_{F}E_{x}[E_{y}(L(y, F(x))) | x]$$

上面用$F(x)$来表示更广义的函数，$f(x)$把它看成数学世界中某个具体的函数方便讨论后续问题。求解上述问题，我们一般会采用梯度下降，如果迭代M次，找到最优参数$\theta^{*}$的过程可以描述为

$$\theta^{*} = \theta_{0} + \sum_{i=1}^{M} – \alpha_{i}\nabla F(x; \theta_{i-1})$$

其中$-\nabla F(x; \theta_{i-1})$是负梯度方向，$\alpha_i$是步长，我们把公式写的更通用一点，对于迭代优化问题，获得系数$\theta^{*}$的过程是

$$\theta^{*} = \sum_{i=0}^{M}\theta_{i}$$

GB部分

上面我们在讨论的梯度下降的过程中，函数$f(x)$的参数个数，函数的形式我们事先是知道的，所以可以使用梯度下降对参数$\theta$进行迭代，即所谓的参数方法(parameteric method)。 现在如果我们把整个函数$f(x)$当作未知参数，函数的形式、参数个数都是未知的，用数据集$[\textbf{x}, y]$来找这个函数的过程，也就是所谓非参数方法(no-parametric method)，为了方便标记，我们把整个函数标记$F(x)$，于是我们预估值是

$$\hat{y} = F(x)$$

基于梯度下降的计算逻辑我们类比迭代求解$F(x)$的过程，最优函数$F^*(x)$如果迭代$M$次获得，那么它是

$$F^{*}(x) = \sum_{m=0}^{M}f_{m}(x)$$

这里的$f_{m}(x)$我们看作是每次迭代更新的那一部分，是不是有那味了，GBDT从形式上看就长这个样。上述形式其实也是加法模型，我们按ESL的标记，加法模型可以写成

$$Y = \alpha + \sum_{j=1}^{p}f_{j}(X_j) + \epsilon$$

加法模型的表达能力太强了，不做限制地学习下去，可以使经验损失函数趋近理论最小值，从而导致over-fitting，所以我们看到GBDT的各种实现XGBoost、LightGBM都在控制过拟合方面做了很多工作。仿照梯度下降的过程，求解$F^{*}(x)$的过程可以写成如下形式

$$F^{*}(x) = f_{0}(x) + \sum_{m=1}^{M}f_{m}(x)$$

其中$f_{0}(x)$是初始值，它应该是经过对全局的考虑之后给定的初始猜测，往往初始值给的好，可以稳准快地找到最优解。

公式右边剩下的$\sum_{m=1}^{M}f(x)$，按梯度下降过程写法分成两部分

$$f_{m}(x) = -\rho_{m}g_{m}(x)$$

$-g_{m}(x)$是当前迭代用到的负梯度方向，它是损失函数$\Phi(F(x))$对未知变量$F(x)$的偏导数，因为现在我们把$F(x)$整个看成是一个未知变量，根据导数定义

$$\frac{\partial L}{\partial F_{m-1}(x)} = \lim_{f_{m}(x) \rightarrow 0} \frac{L(y, F_{m-1}(x) + f_m(x)) – L(y, F_{m-1}(x)) }{f_m(x)}$$

于是$g_{m}(x)$是损失函数对未知变量$\textbf{F}(x)$的导数，而当前的$\textbf{F}(x)$是$F_{m-1}(x)$，Regression Tree采用的损失函数是Square Error

$$L(y, F(x)) = \frac{1}{2}||y – F(x)||^2$$

所以算出来的梯度是$\hat{y}-y$，即利用$F_{m+1}(x)$给出的预测值减去目标值就是$g_m$，当然损失函数还有很多比如还有MAE, corss entropy等，在另一篇文章会单独介绍这些不同的损失函数。

$g_m(x)$确定以后，还有另一个参数$\rho_{m}$，它该如何确定呢？假如第$m$轮的基学习器$h(x, a_m)$，其中$a_m$是这个学习器的参数，对于GBDT来说，基学习器是一个棵Regression Tree，所以$a_m$是这棵树的划分和划分的平均值。步长$\rho_m$决定了在负梯度方向上行进的距离才能使本轮过后的损失最小，数学描述

$$\rho_m = \arg \min_{p} \sum_{i=1}^{N} L(y_i, F_{m-1}(x_i) + \rho h(x_i;a_m))$$

看着还挺复杂的，实际上$F_{m-1}(x+i)$和$h(x_i;a_m)$已经知道了，损失函数采用square error，是可导的，那么$\rho_m$是可以得到解析解的。

于是Gradient Boosting的过程如下：

再总结一下上述流程，为了最小化$L(y,F(x))$, Gradient Boosting将$F(x)$定义为

$$F(x) = \sum_{m=0}^{M}f_{m}(x)$$

$M$决定了有多少个基学习器参与串联，他们是顺序学习的，在第$m$轮学习的目标是截止到上一轮$L(y,F(x))$对$F(x)$的负梯度

$$-g_m(x) = – \left [ \frac{\partial L(y,F(x))}{\partial F(x)} \right ]_{F(x)=F_{m-1}(x)}$$

当损失函数采用Square Error的时候，学习的目标就是残差，就是距离最终的$y$还剩多好要去逼近$y-\hat{y}$，这个残差是一个向量。最终的那个$f_m$跟$-g_m$的方向大概一致，还有一步就是线性搜索，朝着负梯度方向行进一定的距离使得本轮迭代尽可能逼近目标$y$

$$\rho_m = \arg \min_{\rho} L(y, F_{m-1}(x) + \rho h(x;a)$$

于是本轮迭代成后，输出的预测值就是

$$F_m(x) = F_{m-1}(x) + \beta_m f_{m}(x)$$

眼尖的你看到有多了一个变量$\beta_m$，它用来控制每个基学习器的贡献，近一步约束每个学习器的能力来避免过拟合。

来个例子吧，如果损失函数采用Least-absolute-deviation (LAD):

$$L(y,F) = |y – F|$$

第m轮基学习器拟合的目标是

$$-g_m = \text{sign}(y – F_{m-1})$$

线性搜索部分

$$\rho_m = \arg \min_{\rho} \sum_{i=1}^{N} |y_i – F_{m-1}(x_i) – \rho h_m(x_i;a_m)|$$ $$= \arg \min_{\rho} \sum_{i=1}^{N} |h_m(x_i;a_m)|\cdot|\frac{y_i – F_{m-1}(x_i)}{h_m(x_i;a_m)} -\rho|$$

于是我们得到一个解析解

$$\rho_m=\text{middian}_{w} \left (\frac{y_i – F_{m-1}(x_i)}{h_m(x_i;a_m)} \right )_1^N$$

其中$w=|h_m(x_i;a_m)|$

DT部分

DT指的是基学习器使用Decision Tree（决策树），在GBDT中采用了Regression Tree（回归树），如果这棵树有$J$个叶子结点，数学表达形式是

$$h(x;\{b_j, R_j\}_{1}^{J})=\sum_{j=1}^{J}b_j1(x \in R_j)$$

$J$个叶子结点相当于把样本空间划分成了$J$个不相交的子空间，$R_j$表示第$j$个划分，$1(x)$如果$x$成立返回1不成立返回0，所以上述公式的意思是如果$x$在$R_j$的划分里，那就返回$b_j$。

第$m$轮迭代完成后，模型的预测值是

$$F_m(x) = F_{m-1}(x) + \rho_m \sum_{j=1}^{J} b_{jm} 1(x\in R_{jm})$$

$R_{jm}$是第$m$轮中学习到的树的第$j$个划分，回归树把样本划分成了$J$个不相交的空间，我们把每个空间看成一个独立的函数

$$F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J} r_{jm}1(x \in R_{jm})$$

其中$\rho_{m}b_{jm}$是$\gamma_{jm}$，于是每个空间可以独立执行上述优化问题，第$j$个空间的输出等于$\gamma_{jm}$是

$$\gamma_{jm} = \arg \min _{\gamma} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma)$$

如果损失函数是least square

$$\gamma _{jm} = \arg \min_{\gamma} \sum_{x_i \in R_{jm}} |y_i – F_{m-1}(x_i) – \gamma|$$

根据初中学到的知识，$\gamma_{jm}$是$\textbf{y} – F_{m-1}(\textbf{x})$的中位数的时候可以得到最小值。

如果损失函数是least square

$$\gamma _{jm} = \arg \min_{\gamma} \sum_{x_i \in R_{jm}} ||y_i – F_{m-1}(x_i) – \gamma||^2$$

依旧是初中知识，此时$\gamma_{jm}$是$\textbf{y} – F_{m-1}(\textbf{x})$的平均数的时候可以得到最小值。

这里有个Least absolute deviation的算法流程

参考文献：

1. Friedman J H . Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 2001, 29(5):1189-1232.

2. Jerome F ,  Robert T ,  Trevor H . Additive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)[J]. Ann. Statist.  2000.