集成学习

个体学习器存在强依赖关系，必须串行生成的序列化方法： Boosting
个体学习器不存在强依赖，可同时生成的并行化方法： Bagging & 随机森林

AdaBoost

AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

具体说来，整个Adaboost 迭代算法就3步：

初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

Bagging与随机森林

根据Hoeffding定律，如果基学习器的误差相互独立，则集成学习的错误率以指数级别下降，因此，基本想法是希望做到个体学习器尽可能相互独立。

Bagging

基于Bootstrap方法，每次采样后将样本放入数据集（有可能再次被选中）（选中的样本使用自然对数逼近，为63%左右），然后对每个采样集合训练一个基学习器。

预测时，对分类问题采用简单投票法，对回归问题使用平均法。

同时，由于使用Boosttrap方法，可以用剩下的样本估计其泛化能力。

随机森林

传统决策树在选择划分属性时是在当前属性集合中选择一个最优属性，在RF中，随机选择k个属性集合，再选择最优属性进行分类。

与Bagging的区别：Bagging只对对样本进行了随机扰动，而随机森林对属性也进行了随机扰动。

GBDT

Gradient boosting(GB)

Gradient boosting的思想是迭代生多个（m个）弱的模型，然后将每个弱模型的预测结果相加，每一次都希望损失函数减小得尽可能快，也就是用负梯度方向
计算负梯度，用负梯度近似残差
- GBDT 在每一轮的迭代时对每个样本都会有一个预测值，此时的损失函数为均方差损失函数：
- $l(y_i,y^i) = \frac{1}{2}(y_i - y^i)^2$
- 负梯度为： $- \frac{\partial l(y_i,y^i)}{\partial y^i} = (y_i - y^i)$
- 因此，当损失函数选用均方损失函数是时，每一次拟合的值就是（真实值 - 当前模型预测的值），即残差。此时的变量是 $y^i$ ，即“当前预测模型的值”，也就是对它求负梯度。
如何选择特征？
- 遍历每个特征，对特征的每一个切分点进行选择，选择使得均方差最小的作为分裂点。
如何面对二分类问题？
- 首先将类别变为01，每次训练一棵树，得到的结果用logistic得到概率，并通过loss function拟合残差作为下一棵树的输入
如何面对多分类问题？
- 首先有K类，就训练K树。每个类的结果用一个向量表示（one-hot），例如[0,1,0]表示第二类。
- 每轮训练都同时训练K颗树，每一轮的每棵树只预测一个类，输入为[x,1/0]每棵树都给出一个预测值，然后用softmax产生每一类的概率。
- 根据loss function得到计算每个样本在每一类上的残差，用负梯度方向表示当前输入[x,y(x)]，再次迭代，每次同时训练出K棵树。
- 预测的时候得到K个预测值，用softmax得到属于每个类的概率进行预测。

XGBoost

模型函数

对于多个树的回归结果，直接相加作为最终的预测值。
回归树输出的是实数，可用于回归、分类、排序等任务中。对于分类问题，需要映射成概率，比如采用Logistic函数

目标函数

损失函数+正则项： $obj = \sum\limits_{i=1}^{n} L(y_i,\hat y_i^t) + \sum \limits_{i=1}^{t}\Omega(f_i)$
其中， $n$ 是样本的数量， $t$ 是树的数量

正则项

定义为： $\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum\limits_{j=1}^T w_j^2$
对每棵树的复杂度进行了惩罚：叶子节点个数（相当于在训练过程中做了剪枝）、叶节点分数
$\gamma, \lambda$ 越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。

损失函数

第 $t$ $t$ 次迭代后，模型的预测等于前 $t-1$ $t - 1$ 次的模型预测加上第 $t$ $t$ 棵树的预测，目标函数可以写做
- $obj = \sum\limits_{i=1}^n L(y_i,\hat{y_i}^{(t-1)} + f_t(x_i)) + \Omega(f_t)$
通过Taylor公式进行二次逼近，去除常数项，可以得到目标函数为
- $obj = \sum\limits_{i=1}^{n}[g_i f_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)$
- 其中 $g_i = \partial _{\hat{y}(t-1)}L(y_i,\hat{y}^{t-1})$ 表示对损失函数的一阶导， $h_i$ 表示二阶导
- 定义 $f_t(x) = w_{q(x_i)}$ 为这棵树对样本的预测值
因此，这样我们就得到了新生成的树的优化目标，写成树的形式： $w_j$ $w_{j}$ 表示第 $j$ $j$ 个叶子节点的值， $w_{q(x_i)}$ $w_{q (x_{i})}$ 是将第 $x_i$ $x_{i}$ 个样本映射到某个叶子节点，则可以表示为
- $obj =\sum\limits_{i=1}^{n}[g_i w_{q(x_i)} + \frac{1}{2}h_iw_{q(x_i)}^2] + \gamma T + \frac{1}{2} \lambda \sum\limits_{j=1}^T w_j^2$
再用示性函数将样本累加和叶子节点累加统计起来：
- $obj = \sum\limits_{j=1}^T[(\sum\limits_{i\in I_j}g_i) w_j + \frac{1}{2}(\sum\limits_{i\in I_j}h_i+\lambda) w_j^2] + \gamma T$
求导可以得到 $w_j = -\frac{G_j}{H_j + \lambda}$ $w_{j} = - H _{j} + λ G _{j}$ ，其中 $\sum\limits_{i\in I_j}g_i = G_j$ $i \in I_{j} \sum g_{i} = G_{j}$ ，对每个样本点而言，确定了损失函数后 $g_i,h_i$ $g_{i}, h_{i}$ 可以并行计算，得到最小损失为：
- $obj = -\frac{1}{2} \sum\limits _{j =1}^T \frac {G_j^2}{H_j+\lambda} + \gamma T$
因此目标为最小化该目标函数，值越小，树的结构越好

学习策略

如何确定树的结构？
- 暴力枚举所有可能的树结构，选择损失值最小的 - NP难问题
- 贪心法，类似于决策树，每次求得增益最大的分裂点
- 近似方法，只求分位数点

贪心法

贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的（决策树都是这样做的）
对一个叶子节点进行分裂，分裂前后的增益定义为:
Gain的值越大，分裂后损失函数减小越多。所以当对一个叶节点分割时，计算所有候选(feature,value)对应的gain，选取gain最大的进行分割

近似算法

对于每个特征，只考察分位数点，减少计算复杂度
这里的分位数使用了以二阶导数 $h_i$ $h_{i}$ 作为权重得到的
- 这是因为 $obj = \sum \frac{1}{2}h_i (f_t(x_i) + \frac{g_i}{h_i})^2 + \Omega(f_t) + constant$
- 这个形式的loss说明了, $x_i$ 的loss也可以看做是以 $-\frac{g_i}{h_i}$ 作为label的均方误差，乘以大小为 $h_i$ 的权重，换句话说， $x_i$ 对loss的贡献权重为 $h_i$ 。
作者提出了两种近似算法。
- 一种是全局算法，即在初始化tree的时候划分好候选节点，并且在树的每一层都使用这些候选节点；
- 另一种是局部算法，即每一次划分的时候都重新计算候选节点。
- 这两者各有利弊，全局算法不需要多次计算候选节点，当需要一次获取较多的候选节点供后续树生长使用，而局部算法一次获取的候选节点较少，可以在分支过程中不断改善，即适用于生长更深的树，两者在effect和accuracy做trade off。

特点

行抽样（row sample）：bootstrap方法
列抽样（column sample）：借鉴随机森林
Shrinkage（缩减），即学习速率，防止过拟合
- 将学习速率调小，迭代次数增多，有正则化作用
支持自定义损失函数（需二阶可导）

总结

首先，XGBoost是加法模型。对每棵树的回归结果，直接相加作为最终的预测值
目标函数
- 对目标函数增加了正则项防止过拟合，抽象来说就是对每棵树的叶子结点个数、叶节点分数进行惩罚。
- 在第t次迭代时，可以写出其目标函数并使用泰勒公式进行二次逼近，去除常数项（前面已经生成的树）后得到新生成树的优化目标函数，目标为最小化该目标函数（包含每个样本关于损失函数的一阶导、二阶导、叶子结点数量等）
学习策略
- 可以直接暴力枚举可能的树结构，然后选择损失值最小的。这里采用了与决策树一样的贪心法，对一个叶子结点进行分类，计算分类前后的增益（也就是分裂后损失函数减少多少），选择最大的增益进行分割。
- 对于计算增益，可以便利所有特征的分割点，在这里使用了近似算法：对于每个特征，只考察以分位数点为分割点的增益，同时，这里的分位数使用了以二阶导为权重得到的

思考

gbdt的残差为什么用负梯度代替?
- 为了可以扩展到更复杂的损失函数中。只有在平方损失函数中求负梯度后是残差。
- boosting的目的是为了是损失函数最小化而不是更好的拟合训练数据。
XGBoost和GBDT有什么不同？
- 一般可以认为XGBoost是GBDT的改进版本
- XGBoost除了CART作为基分类器，还支持线性分类器
- 损失函数
  - GBDT每次关注的是负梯度方向，在平方损失函数中就是残差方向。
  - 可以自定义损失函数，且只需要二阶可导即可。
  - GBDT使用一阶梯度作为残差，而XGBoost使用二阶梯度，而XGBoost仍然比GBDT快，为什么？
    - 二阶梯度收敛更快，能够快的进行优化
- 正则化考虑
  - gboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。
  - Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。
  - 列抽样（column subsampling）。借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- xgboost工具支持并行。
  - 在训练之前，预先对数据进行了排序，保存为block结构，重复使用（利于并行计算）。
  - 每次并行计算特征的增益。
- 节点分裂
  - XGBoost在计算时，用贪心算法效率很低。因此，使用了一种可并行的近似直方图算法：先对数据进行排序，然后按照二阶导权重计算分位数点，只对分位数点计算增益。
- 增益的计算方式也不同（GBDT是GINI系数，XGBoost是object function推导而来）
- 工程实现，用block利于并行化，提高cache命中率等
XGBoost和随机森林有什么不同？
- 都是集成学习，都是树模型
- 随机森林是bagging模型，基模型之间是独立的，容易并行化，主要关注降低方差
- XGBoost是加法模型，基模型之间相互关联，主要关注于减小偏差
XGBoost计算海瑟矩阵相对于一阶梯度是否增大了计算量？
- 并没有，实际上利用二阶梯度能更快收敛

GBDT/XGboost 小记