GBDT
引言
GBDT 全称是 Gradient Boosting Decision Tree，是一种常用的 Ensemble Learning 算法。由于其出色的表现以及 XGBoost 的出现，近些年在 Kaggle 等竞赛中大放异彩。
优点：
缺点：
GBDT 作为一种 Ensemble Learning 算法，本质也就是融合多个弱分类器进行决策。从 GBDT 的名字可以看出，它包含两个概念：GB（Gradient Boosting） 和 DT（Decision Tree）。因此，GBDT 使用的弱分类器就是 Decision Tree，而融合的方法叫做 Gradient Boosting。但是在介绍 Gradient Boosting 前，我们先回顾一下相关的 Boosting 算法。
Boosting
Boosting介绍
- 基本思想
Boosting方法基于这样一种思想：
对于一个复杂任务来说，将多个专家的判定进行适当的综合得出的判断，要比其中任何一个专家单独的判断好。很容易理解，就是”三个臭皮匠顶个诸葛亮”的意思…😄😄😄。
- 历史由来
历史上，Kearns和Valiant首先提出了”强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。他们指出：
在概率近似正确（probably approximately correct，PAC）学习框架中：
①. 一个概念（一个类，label），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；
②. 一个概念（一个类，label），如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。
Schapire后来证明了: 强可学习和弱可学习是等价的。 也就是说，在PAC学习的框架下，一个概念是强可学习的 充分必要条件 是这个概念是弱可学习的。 表示如下：
强可学习⇔弱可学习
如此一来，问题便成为：在学习中，如果已经发现了”弱学习算法”，那么能否将它提升为”强学习算法”？ 通常的，发现弱学习算法通常要比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。关于提升方法的研究很多，最具代表性的当数AdaBoost算法（是1995年由Freund和Schapire提出的）。
- Boosting学习思路
对于一个学习问题来说（以分类问题为例），给定训练数据集，求一个弱学习算法要比求一个强学习算法要容易的多。Boosting方法就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合弱分类器，得到一个强分类器。Boosting方法在学习过程中通过改变训练数据的权值分布，针对不同的数据分布调用弱学习算法得到一系列弱分类器。
这里面有两个问题需要回答：
- 在每一轮学习之前，如何改变训练数据的权值分布？
- 如何将一组弱分类器组合成一个强分类器？
具体不同的boosting实现，主要区别在弱学习算法本身和上面两个问题的回答上。
针对第一个问题，Adaboost算法的做法是：
提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。
如此，那些没有得到正确分类的样本，由于其权值加大而受到后一轮的弱分类器的更大关注。
第二个问题，弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地：
加大 分类误差率小 的弱分类器的权值，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
AdaBoost算法的巧妙之处就在于它将这些学习思路自然并且有效地在一个算法里面实现。
前向分步加法模型Forward Stagewise Additive Modeling
- 加法模型（addtive model）
GBDT算法可以看成是由K棵树组成的加法模型：
$$
\hat{y}i = \sum{k=1}^K f_k(x_i), f_k \in F \tag 0
$$
其中$F$为所有树组成的函数空间，以回归任务为例，回归树可以看作为一个把特征向量映射为某个score的函数。该模型的参数为：$\Theta={f_1,f_2, \cdots, f_K }$。于一般的机器学习算法不同的是，加法模型不是学习d维空间中的权重，而是直接学习函数（决策树）集合。
上述加法模型的目标函数定义为：$Obj=\sum_{i=1}^n l(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k)$ ，其中 $\Omega$ 表示决策树的复杂度，那么该如何定义树的复杂度呢？比如，可以考虑树的节点数量、树的深度或者叶子节点所对应的分数的$L2$范数等等。
- 前向分步算法
如何来学习加法模型呢？
解这一优化问题，可以用前向分布算法（forward stagewise algorithm）。因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数（结构），逐步逼近优化目标函数，那么就可以简化复杂度。这一学习过程称之为Boosting。具体地，我们从一个常量预测开始，每次学习一个新的函数，过程如下：
$$
\begin{split}
\hat{y}_i^0 &= 0 \
\hat{y}_i^1 &= f_1(x_i) = \hat{y}_i^0 + f_1(x_i) \
\hat{y}_i^2 &= f_1(x_i) + f_2(x_i) = \hat{y}_i^1 + f_2(x_i) \
& \cdots \
\hat{y}i^t &= \sum{k=1}^t f_k(x_i) = \hat{y}_i^{t-1} + f_t(x_i) \
\end{split}
$$
那么，在每一步如何决定哪一个函数$f$被加入呢？指导原则还是最小化目标函数。
在第$t$步，模型对$x_i$的预测为：$\hat{y}i^t= \hat{y}i^{t-1} + f_t(x_i)$，其中$f_t(x_i)$为这一轮我们要学习的函数（决策树）。这个时候目标函数可以写为：
$$
\begin{split}
Obj^{(t)} &= \sum{i=1}^nl(y_i, \hat{y}i^t) + \sum{i=i}^t \Omega(f_i) \
&= \sum{i=1}^n l\left(y_i, \hat{y}i^{t-1} + f_t(x_i) \right) + \Omega(f_t) + constant
\end{split}\tag{1}
$$
举例说明，假设损失函数为平方损失（square loss），则目标函数为：
$$
\begin{split}
Obj^{(t)} &= \sum{i=1}^n \left(y_i - (\hat{y}i^{t-1} + f_t(x_i)) \right)^2 + \Omega(f_t) + constant \
&= \sum{i=1}^n \left[2(\hat{y}_i^{t-1} - y_i)f_t(x_i) + f_t(x_i)^2 \right] + \Omega(f_t) + constant
\end{split}\tag{2}
$$
其中，$(\hat{y}_i^{t-1} - y_i)$ 称之为残差（residual）。因此，使用平方损失函数时，GBDT算法的每一步在生成决策树时只需要拟合前面的模型的残差。
泰勒公式：设$n$是一个正整数，如果定义在$a$一个包含的区间上的函数$f$在$a$点$n+1$处次可导，那么对于这个区间上的任意 $x$ 都有：
$\displaystyle f(x)=\sum _{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n+R_ n(x)$，其中的多项式称为函数在$a$处的泰勒展开式，$R_ n(x)$是泰勒公式的余项且是$(x-a)^ n$的高阶无穷小。—-维基百科
根据泰勒公式把函数$f(x+\Delta x)$在点$x$处二阶展开，可得到如下等式：
$$
f(x+\Delta x) \approx f(x) + f’(x)\Delta x + \frac12 f’’(x)\Delta x^2 \tag 3
$$
由等式(1)可知，目标函数是关于变量$\hat{y}_i^{t-1} + f_t(x_i)$的函数，若把变量$\hat{y}i^{t-1}$看成是等式(3)中的$x$，把变量$f_t(x_i)$看成是等式(3)中的$\Delta x$，则等式(1)可转化为：
$$
Obj^{(t)} = \sum{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) + constant \tag 4
$$
其中，$g_i$定义为损失函数的一阶导数，即$g_i=\partial_{\hat{y}^{t-1}}l(y_i,\hat{y}^{t-1})$；$h_i$定义为损失函数的二阶导数，即$h_i=\partial_{\hat{y}^{t-1}}^2l(y_i,\hat{y}^{t-1})$。
假设损失函数为平方损失函数，则$g_i=\partial_{\hat{y}^{t-1}}(\hat{y}^{t-1} - y_i)^2 = 2(\hat{y}^{t-1} - y_i)$，$h_i=\partial_{\hat{y}^{t-1}}^2(\hat{y}^{t-1} - y_i)^2 = 2$，把$g_i$和$h_i$代入等式(4)即得等式(2)。
由于函数中的常量在函数最小化的过程中不起作用，因此我们可以从等式(4)中移除掉常量项，得：
$$
Obj^{(t)} \approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \tag 5
$$
由于要学习的函数仅仅依赖于目标函数，从等式(5)可以看出只需为学习任务定义好损失函数，并为每个训练样本计算出损失函数的一阶导数和二阶导数，通过在训练样本集上最小化等式(5)即可求得每步要学习的函数，从而根据加法模型等式(0)可得最终要学习的模型。
在给定训练数据及损失函数$L(y,f(x))$的条件下，学习加法模型$f(x)$成为经验风险极小化即损失函数极小化的问题：
$$
\min_{\beta_k, \gamma_k} \quad \sum_{i=1}^{M} L \left[y^{(i)}, \sum_{k=1}^{K} \beta_k b(x^{(i)}; \gamma_k)\right] \qquad(ml.1.6.2)
$$
通常这是一个复杂的优化问题。前向分布算法（forward stagwise algorithm）求解这一优化问题的思路是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式($ml.1.6.1$)，那么就可以简化优化的复杂度。 具体地，每步只需优化如下损失函数：
$$
\min_{\beta, \gamma} \quad \sum_{i=1}^{M} L(y^{(i)}, \beta b(x^{(i)}; \gamma)) \qquad(n.ml.1.6.1)
$$
给定训练数据集$D={(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \cdots, (x^{(M)}, y^{(M)})}, x^{(i)} \in \mathcal{X} \subseteq R^n, y^{(i)} \in \mathcal{Y} = $ ${-1, +1}$。损失函数$L(y,f(x))$和基函数的集合${b(x; \gamma)}$，学习加法模型$f(x)$的前向分步算法如下：
$$
{ \ \quad 输入：训练数据集D={(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \cdots, (x^{(M)}, y^{(M)})}; 损失函数L(y, f(x));\ \qquad\quad 基函数集{b(x, \gamma)}； \ \quad 输出：加法模型f(x)。 \ \quad 计算过程：\ \qquad (1). 初始化f_0(x) = 0 \ \qquad (2). 对于k=1,2,\cdots,K \ \qquad\qquad (a). 极小化损失函数 \ \qquad\qquad\qquad (\beta_k, \gamma_k) = \arg \min_{\beta, \gamma} \sum_{i=1}^{M} L(y^{(i)}, f_{k-1}(x^{(i)}) + \beta b(x; \gamma)) \quad(n.ml.1.6.2)\ \qquad\qquad 得到参数\beta_k, \gamma_k. \ \qquad\qquad (b). 更新 \ \qquad\qquad\qquad f_k(x) = f_{k-1}(x) + \beta_k b(x; \gamma_k) \qquad(n.ml.1.6.3) \ \qquad (3). 得到加法模型 \ \qquad\qquad\qquad f(x) = f_K(x) = \sum_{k=1}^{K} \beta_k b(x; \gamma_k) \qquad(n.ml.1.6.4) \ }
$$
GBDT和Random Forest的区别简要
我们再简要说明一下另外一类集成学习的方法，Bagging
Bagging，装袋。但是这名字其实是由Bootstrap Aggregating（加速聚合）而来。指的是用并行的方案生成各个各个学习器的方案。
简单的Bagging方案
随机森林-一种Bagging基础上的变体
具体而言，Random Forest通过随机抽样、随机选取特征来产生一棵树，最后通过每棵树的结果做线性结合来产生最终的预测结果。由于每棵树的生成过程不依赖于其他树（和GBDT明显区别，GBDT每棵树的产生需要依赖上一层树的结果），所以树的生成是并行的（这也是其成为Bagging的原因）。在RF中，每棵树都是几乎完全长成（但是仅仅预测了部分样本），树的深度会很大。
Boosting方法，每棵树是不能完全长成的，只需要一部分特征就去完成残差的一个迭代降低。个人认为，这特别适合解决这类问题：部分样本就用部分特征就能描述，而另外的样本可能需要其他的特征来描述，比如股票的样本有很多类型的股票，我们有的朋友对一种类型比较擅长，另外的朋友对别的类型比较擅长。