GBDT

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型：

$f_m(x)=\sum\limits_{m=1}^MT(x;\Theta_m)$

其中， $T(x;\Theta_m)$ 表示决策树； $\Theta_m$ 为决策树的参数； $M$ 为树的个数。

提升树算法采用前向分步算法。首先确定初始提升树 $f_0(x)=0$ ，第 $m$ 步的模型是

$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

其中， $f_{m-1}(x)$ 为当前模型，通过经验风险极小化确定下一棵决策树的参数 $\Theta_m$ ，

$\hat{\Theta}_m=\arg\min\limits_{\Theta_m}\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$

下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括平方误差损失函数的回归问题，用指数函数的分类问题，以及用一般损失函数的一般决策问题。

分类问题

将GBDT应用于回归问题，相对来说比较容易理解。因为回归问题的损失函数一般为平方差损失函数，这时的残差，恰好等于预测值与实际值之间的差值。每次拿一棵决策树去拟合这个差值，使得残差越来越小，这个过程还是比较intuitive的。而将GBDT用于分类问题，则显得不那么显而易见。

在说明分类之前，我们先介绍一种损失函数。与常见的直接求预测与真实值的偏差不同，这种损失函数的目的是最大化预测值为真实值的概率。这种损失函数叫做对数损失函数（Log-Likehood Loss），定义如下

$L(Y,P(Y|X))=-\log P(Y|X)$

对于二项分布， $y^*\in\{0,1\}$ ，我们定义预测概率为 $p(x)=P(y^*=1)$ ，即二项分布的概率，可得

$L(y^*,p(x))=\begin{cases} -\log(p(x)),\ \ \text{if}\ y^*=1\\ -\log(1-p(x)),\ \ \text{if}\ y^*=0 \end{cases}$

即，可以合并写成

$L(y^*,p(x))=-y_i\log(p(x))-(1-y_i)\log(1-p(x))$

即

$L(y^*,p(x))=-y_i\log\hat{y_i}-(1-y_i)\log(1-\hat{y_i})$

对于 $p(x)$ 与 $F(x)$ 的关系，我们定义为

$p(x)=\frac{e^{F(x)}}{e^{F(x)}+e^{-F(x)}}$

二分类

类似于逻辑回归、FM模型用于分类问题，其实是在用一个线性模型或者包含交叉项的非线性模型，去拟合所谓的对数几率 $\ln \frac{p}{1-p}$ 。而GBDT也是一样，只是用一系列的梯度提升树去拟合这个对数几率，实际上最终得到的是一系列CART回归树。其分类模型可以表达为：

$P(y=1|x)=\frac{1}{1+e^{-\sum^M_{m=0}h_m(x)}}$

其中， $h_m(x)$ 就是学习到的决策树。

清楚了这一点之后，我们便可以参考逻辑回归，单样本 $(x_i,y_i)$ 的损失函数可以表达为交叉熵：

$loss(x_i,y_i)=-y_i\log\hat{y_i}-(1-y_i)\log(1-\hat{y_i})$

假设第 $k$ 步迭代之后当前学习器为 $F(x)=\sum\limits_{m=0}^kh_m(x)$ ，将 $\hat{y_i}$ 的表达式带入之后，损失函数写为：

$loss(x_i,y_i|F(x))=y_i\log(1+e^{-F(x_i)})+(1-y_i)[F(x_i)+\log(1+e^{-F(x_i)})]$

可以求得损失函数相对于当前学习器的负梯度为：

$-\frac{\partial loss}{\partial F(x)}|_{x_i,y_i}=y_i-\frac{1}{1+e^{-F(x_i)}}=y_i-\hat{y_i}$

可以看到，同回归问题很类似，下一棵决策树的训练样本为： $\{x_i,y_i-\hat{y_i}\}_{i=1}^n$ ，其所需要拟合的残差为真实标签与预测概率之差。于是便有下面GBDT应用于二分类的算法：

$F_0(x)=h_0(x)=\log\frac{p_1}{1-p_1}$ ，其中是训练样本中y=1的比例，利用先验信息来初始化学习器
$\text{For}\ m=1,2\dots,M$ ：
- 计算 $g_i=\hat{y_i}-y_i$ ，并使用训练集 $\{(x_i,-g_i)\}^n_{i=1}$ 训练一棵回归树 $t_m(x)$ ，其中 $\hat{y_i}=\frac{1}{1+e^{-F_{m-1}(x)}}$
- 通过最小化损失函数找树的最优权重： $\rho_m=\mathop{\arg\min}\limits_p\sum\limits_iloss(x_i,y_i|F_{m-1}(x)+\rho t_m(x))$
- 考虑shrinkage，可得这一轮迭代之后的学习器 $F_m(x)=F_{m-1}(x)+\alpha\rho_m t_m(x)$ , $\alpha$ 为学习率
得到最终学习器： $F_m(x)$

多分类

模仿上面两类分类的损失函数，我们能够将 $K$ 类分类的损失函数定义为

$-\sum\limits_{k=1}^Ky_k\log p_k(x)$

其中， $p_k(x)=P(y_k=1|x_k)$ ，且将 $p_k(x)$ 与 $F_k(x)$ 关系定义为

$F_k(x)=\log p_k(x)-\frac{1}{K}\sum\limits_{l=1}^K\log p_l(x)$

或者，换一种表达方式

$p_k(x)=\frac{e^{F_k(x)}}{\sum_{i=1}^Ke^{F_i(x)}}$

即，对于多分类问题，则需要考虑以下softmax模型：

$P(y=1|x)=\frac{e^{F_1(x)}}{\sum_{i=1}^ke^{F_i(x)}}$ $P(y=2|x)=\frac{e^{F_1(x)}}{\sum_{i=2}^ke^{F_i(x)}}$ ... ...

其中 $F_1\dots F_k$ 是 $k$ 个不同的tree ensemble。每一轮的训练实际上是训练了 $k$ 棵树去拟合softmax的每一个分支模型的负梯度。可见，这k棵树同样是拟合了样本的真实标签与预测概率之差，与二分类的过程非常类似。

回归问题

已知一个训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\},\ x_i\in \mathcal{X}\subseteq R^n$ ， $\mathcal{X}$ 为输入空间， $y_i\in\mathcal{Y}\subseteq R$ ， $\mathcal{Y}$ 为输出空间。如果将输入空间 $\mathcal{X}$ 划分为 $J$ 个互不相交的区域 $R_1,R_2,\dots,R_J$ ，并且在每个区域上确定输出的常量 $c_j$ ，那么树可表示为

$T(x;\Theta)=\sum\limits_{j=1}^Jc_jI(x\in R_j)$

其中，参数 $\Theta=\{(R_1,c_1),(R_2,c_2),\dots,(R_J,c_J)\}$ 表示树的区域划分和各区域上的常数。 $J$ 是回归树的复杂度即叶结点个数。

回归问题提升树使用以下前向分布算法：

$f_0(x)=0$
$f_m(x)=f_{m-1}(x)+T(x;\Theta_m),\ \ m=1,2,\dots,M$
$f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_m)$

在前向分步算法的第 $m$ 步，给定当前模型 $f_{m-1}(x)$ ，需求解

$\hat{\Theta}_m=\arg\min\limits_{\Theta_m}\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$

得到 $\hat{\Theta}_m$ ，即第 $m$ 颗树的参数。当采用平方误差损失函数时，

$L(y,f(x))=(y-f(x))^2$

其损失变为

$L(y,f_{m-1}(x)+T(x;\Theta_m))=[y-f_{m-1}(x)-T(x;\Theta_m)]^2=[r-T(x;\Theta_m)]$

这里， $r=y-f_{m-1}(x)$ 即当前模型拟合数据的残差。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。

回归问题的提升树算法

输入：训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\},x_i\in\mathcal{X}\subseteq R^n,y_i\in\mathcal{Y}\subseteq R$

输出：提升树 $f_M(x)$

（1）初始化 $f_0(x)=0$

（2）对 $m = 1,2,\dots,M$

（a）按 $r_{mi}=y_i-f_{m-1}(x_i)$ 计算残差
（b）拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;\Theta_m)$
（c）更新 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

（3）得到回归提升树： $f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_m)$

举例如下

$x_i$	1	2	3	4	5	6	7	8	9	10
$y_i$	5.56	5.70	5.91	6.40	6.80	7.05	8.90	8.70	9.00	9.05

对于 $m = 1$ ：

求 $f_1(x)$ 即回归树 $T_1(x)$ ，首先通过以下优化问题：

$\min\limits_s[\min\limits_{c_1}\sum\limits_{x_i\in R_1}(y_i-c_1)^2+\min\limits_{c_2}\sum\limits_{x_i\in R_2}(y_i-c_2)^2]$

求解训练数据的切分点 $s$ ：

$R_1=\{x|x\leq s\}$ $R_2=\{x|x> s\}$

容易求得在 $R_1,R_2$ 内部使平方损失误差达到最小值的 $c_1,c_2$ 为

$c_1=\frac{1}{N_1}\sum\limits_{x_i\in R_1}y_i$ $c_2 = \frac{1}{N_2}\sum\limits_{x_i\in R_2}y_i$

这里 $N_1,N_2$ 是 $R_1,R_2$ 的样本点数

求训练数据的切分点。根据所给数据，考虑如下切分点：1.5, 2.5, 3.5, 4.5, 6.5, 7.5, 8.5, 9.5

对各切分点，求出相应的 $R_1,R_2,c_1,c_2$ 及 $m(s)=\min\limits_{c_1}\sum\limits_{x_i\in R_1}(y_i-c_1)^2+\min\limits_{c_2}\sum\limits_{x_i\in R_2}(y_i-c_2)^2$

例如，当 $s= 1.5$ 时， $R_1=\{1\}$ ， $R_2=\{2,3,\dots,10\}$ ， $c_1=5.56$ ， $c_2=7.50$ ，

$m(s)=\min\limits_{c_1}\sum\limits_{x_i\in R_1}(y_i-c_1)^2+\min\limits_{c_2}\sum\limits_{x_i\in R_2}(y_i-c_2)^2=0+15.72=15.72$

现将 $s$ 及 $m(s)$ 的计算结果列表如下

$s$	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
$m(s)$	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

由上表可知，当 $s = 6.5$ 时 $m(s)$ 达到最小值，此时 $R_1=\{1,2,\dots,6\}$ ， $R_2=\{7,8,9,10\}$ ， $c_1 = 6.24$ ， $c_2 = 8.91$ ，所以回归树 $T_1(x)$ 为

$T_1(x)=\begin{cases}6.24,\ \ x<6.5\\ 8.91,\ \ x\geq6.5\end{cases}$

$f_1(x) = T_1(x)$

用 $f_1(x)$ 拟合训练数据的残差 $r_{2i}=y_i-f_1(x),\ \ i=1,2,\dots,10$

$x_i$	1	2	3	4	5	6	7	8	9	10
$r_{2i}$	-0.68	-0.54	-0.33	0.16	0.56	0.81	-0.01	-0.21	0.09	0.14

用 $f_1(x)$ 拟合训练数据的平均损失误差： $L(y,f_1(x))=\sum\limits_{i=1}^{10}(y_i-f_1(x_i))^2=1.93$

对于 $m = 2$ ：

求 $T_2(x)$ ，方法与求 $T_1(x)$ 一样，只是拟合的数据为上一步的残差。可以得到

$T_1(x)=\begin{cases}-0.52,\ \ x<3.5\\ 0.22,\ \ \ \ \ x\geq3.5\end{cases}$

$f_2(x) = f_1(x)+T_2(x)=\begin{cases}-0.52+6.24=5.72,\ \ x<3.5\\ 6.24+0.22=6.46,\ \ \ \ \ 3.5\leq x<6.5\\ 8.91+0.22=9.13,\ \ \ \ \ \ x\geq6.5\end{cases}$