GBDT用于回归和分类

提升 (boosting) 方法实际采用加法模型 (即基函数的线性组合) 与前向分步算法。以决策树为基函数的提升方法被称为提升树 (boosting tree)。GBDT(Gradient Boosting Tree) 最早由 Friedman 在论文《Greedy Function Approximation: A Gradient Boosting Machine》中提出，既可以用来解决分类问题（决策树为二叉分类树），也可以用来解决回归问题（决策树为二叉回归树）。
GBDT 的加法模型定义为，
$$\begin{equation}f_M(x) = \sum_{m=1}^{M}T(x;\Theta_m)\tag{1}\end{equation}$$
其中，$x$ 为输入样本，$T(x;\Theta_M)$ 表示决策树，$\Theta_M$ 为决策树的参数。
通过最小化损失函数求解最优模型，
$$\begin{equation}f_M^* = \mathop\arg\min_{f_M}\sum_{i=0}^{N}L(y^{(i)}, f_M(x^{(i)}))\tag{2}\end{equation}$$
$f_M^*$ 不易直接求解，可以通过贪心法，迭代的求解局部最优解，即采用前向分步算法。
首先确定初始提升树 $f_0(x)=0$，第 $m$ 步的模型是，
$$\begin{equation}f_m(x) = f_{m-1}(x) + T(x;\Theta_{m})\tag{3}\end{equation}$$
其中，$f_{m-1}(x)$ 为当前模型，第 m 步的模型等于第 m - 1 步的模型加上第 m - 1 步的基评估器。通过极小化损失函数确定第 m 步的决策树的参数 $\Theta_m$，
$$\begin{equation}\hat{\Theta}_m=\mathop\arg\min_{\Theta_m}\sum_{i=1}^{N}L(y^{(i)}, f_{m-1}(x^{(i)})+T(x^{(i)};\Theta_m))\tag{4}\end{equation}$$
将 $L(y, f_m(x))$ 在 $f_{m-1}(x)$ 处一阶泰勒展开，得到，
$$\begin{equation}L(y, f_m(x))\approx L(y,f_{m-1}(x))+L^{‘}(y,f_{m-1}(x))T(x;\Theta_m)\tag{5}\end{equation}$$
类比梯度下降，要使 $L(y, f_m(x))$< $L(y,f_{m-1}(x))$，则可取 $T(x;\Theta_m)=-\eta L^{‘}(y,f_{m-1}(x))$，令 $\eta=1$，代入式 (3)，
$$\begin{equation}f_m(x) = f_{m-1}(x) – L^{‘}(y, f_{m-1}(x))\tag{6}\end{equation}$$
因此，求解决策树 $T(x;\Theta_m)$ 的参数 $\Theta_m$，即是利用损失函数 $L$ 的负梯度在当前模型（第 m 步的模型 $f_{m-1}(x)$）的值作为提升树算法中残差的近似值，拟合一个决策树,
$$\begin{equation}-[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}\tag{7}\end{equation}$$
注意如果损失函数定义为平方损失误差，那么拟合的就是残差。

回归问题

首先，计算 $f_0(x)$，
$$\begin{equation}f_0(x)=\arg\min_c\sum_{i=1}^NL(y^{(i)},c)\tag{8}\end{equation}$$
每一轮，对所有的样本计算残差的近似值，
$$\begin{equation}r_{m,i}=-[\frac{\partial L(y^{(i)},f(x^{(i)}))}{\partial f(x^{(i)})}]_{f(x)=f_{m-1}(x)}\tag{9}\end{equation}$$
使用所有的 $r_{m,i},i=1,\cdots,N$ 拟合一棵 CART，假设该决策树将输入样本划分到 $J_m$ 个区域（$J_m$ 个叶子结点），第 j 个叶子结点区域记作 $R_{m,j},j=1,\cdots,J_m$，对每一个叶子结点区域计算输出值 $c_{m,j}$，
$$\begin{equation}c_{m,j}=\arg\min_c\sum_{x^{(i)}}^{R_{m,j}}L(y^{(i)},f_{m-1}(x^{(i)})+c)\tag{10}\end{equation}$$
更新得到第 m 轮的模型，
$$\begin{equation}f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J_m}c_{m,j}I(x\in R_{m,j})\tag{11}\end{equation}$$

分类问题

需要注意的是，GBDT 解决分类问题，使用到的也是 CART 回归树。

多分类

多分类时，假设类别总数为 K，损失函数为对数损失，
$$\begin{equation}L(y,f(x))=-\sum_{k=1}^{K}y_k\log p_k(x)\tag{12}\end{equation}$$
其中，y 为 one hot 编码，若 $y_k=1$ 则表示该样本的类别为 k。
多分类时，每一轮都会为每一个类别训练一棵 CART 树，即每一轮都会训练 K 个 CART 回归树 ，因此对于每一个类别 k，都会有一个预测模型 $f_k(x)$，因此样本 x 属于类别 k 的预测概率为，
$$\begin{equation}p_k(x) = \frac{exp(f_k(x))}{\sum_{l=1}^K exp(f_l(x))}\tag{13}\end{equation}$$
在第 m - 1 轮，训练关于类别 k 的决策树 $T_{m,k}(x)$，利用损失函数的负梯度在当前模型 $f_{k-1}(x)$ 的值，来拟合决策树 $T_{m,k}(x)$，对于第 i 个样本，伪残差为，
$$\begin{equation}\begin{aligned}r_{m,k,i}&=-[\frac{\partial L(y^{(i)},f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1,k}(x)}\\&=\sum_{l^{‘}=1,l^{‘}\neq k}^{K}-y^{(i)}_{l^{‘}}\frac{exp(f_{m-1,k}(x_i))}{\sum_{l=1}^{K}exp(f_l(x^{(i)})}+y_k^{(i)}(1-\frac{exp(f_{m-1,k}(x_i))}{\sum_{l=1}^{K}exp(f_l(x^{(i)})})\\&=y^{(i)}_k-p_{m-1,k}(x^{(i)})\end{aligned}\tag{14}\end{equation}$$
用伪残差去拟合决策树，得到第 m 轮关于类别 k 的基评估器 $T_{m,k}(x)$，假设 $T_{m,k}(x)$ 将输入样本划分到 $J_{m,k}$ 个区域（即 $J_{m,k}$ 个叶子结点），计算第 j 个区域的输出值 $c_{m,k,j}$，
$$\begin{equation}c_{m,k,j}=\arg\min_{c}\sum_{x^{(i)}\in R_{m,k,j}}L(y^{(i)},f_{m-1,k}(x^{(i)})+c)\tag{15}\end{equation}$$
原论文给出了近似解（这一步不会推导），
$$\begin{equation}c_{m,k,j} = \frac{K-1}{K} \; \frac{\sum\limits_{x^{(i)} \in R_{m,k,i}}r_{m,k,j}}{\sum\limits_{x^{(i)} \in R_{m,k,j}}|r_{m,k,i}|(1-|r_{m,k,i}|)}\tag{16}\end{equation}$$
更新得到第 m 轮的模型
$$\begin{equation}f_{m,k}(x)=f_{m-1,k}(x)+\sum_{j=1}^{J_{m,k}}c_{m,k,j}I(x\in R_{m,k,j})\tag{17}\end{equation}$$

二元分类

使用对数损失函数计算 loss
$$\begin{equation}L(y,f(x))-y\log \hat{y} – (1-y)\log (1-\hat{y})\tag{18}\end{equation}$$
其中，$\hat{y}=p(y=1|x)=\frac{1}{1+exp(-f(x))}$。
第 m 轮，关于样本 i 的伪残差为 $r_{m,i}=y^{(i)}-\hat{y}^{(i)}_{m-1}$，拟合第 m 轮的决策树，计算第 j 个叶子结点区域的输出，得到近似值，
$$\begin{equation}c_{m,j}=\frac{\sum_{x^{(i)}\in R_{m,j}}r_{m,i}}{\sum_{x^{(i)}\in R_{m,j}}(y^{(i)}-r_{m,i})((1-y^{(i)}-r_{m,i}))}\tag{19}\end{equation}$$
注意到，如果 $y^{(i)}=1$，则 $r_{m,i}>0$, 如果 $y^{(i)}=0$，则 $r_{m,i}<0$，因此式 (19) 可写为，
$$\begin{equation}c_{m,j}=\frac{\sum_{x^{(i)}\in R_{m,j}}r_{m,i}}{\sum_{x^{(i)}\in R_{m,j}}|r_{m,i}|(1-|r_{m,i}|)}\tag{20}\end{equation}$$

1. Friedman, J.H. (2001) Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics, 29, 1189-1232. https://doi.org/10.1214/aos/1…
2. 李航，《统计学习方法》
3. https://zhuanlan.zhihu.com/p/…
4. https://zhuanlan.zhihu.com/p/…
5. https://zhuanlan.zhihu.com/p/…