Boosting算法（提升法)

（1）函数模型：Boosting的函数模型是叠加型的，即

F(x)=∑i=1kfi(x;θi)$$F(x)=\sum _{i=1}^k{f}_i(x;{\theta }_i)$$

（2）目标函数：选定某种损失函数作为优化目标

E{F(x)}=E{∑i=1kfi(x;θi)}$$E\{F(x)\}=E\{\sum _{i=1}^k{f}_i(x;{\theta }_i)\}$$

（3）优化算法：贪婪地逐步优化，即

θ∗m=argminθmE{∑i=1m−1fi(x;θ∗i)+fm(x;θm)}$${\theta }_m^{\ast }=\arg \underset{{\theta }_m}{min}E\{\sum _{i=1}^{m-1}{f}_i(x;{\theta }_i^{\ast })+f_m(x;{\theta }_m)\}$$

需要解决的问题

对于Boosting算法，需要解决两个问题：

1. 如何调整训练集，使得在训练集上训练的弱分类器得以进行；
2. 如何将训练得到的各个弱分类器联合起来形成强分类器。

特点：

1. Boosting是一种框架算法，拥有系列算法，如AdaBoost，GradientBoosting，LogitBoost等算法。
2. Boosting系列算法的主要区别在于其三要素选取的函数不同
3. 可以提高任意给定学习算法准确度
4. 训练过程为阶梯状，弱分类器按次序一一进行训练（实现上可以做到并行），弱分类器的训练集按照某种策略每次都进行一定的转化。最后以一定的方式将弱分类器组合成一个强分类器。
5. Boosting中所有的弱分类器可以是不同类的分类器

图示：

---

AdaBoost算法

算法的实现：

1、若为Adaboost分类，函数模型使用CART分类树；若为Adaboost回归，函数模型使用CART回归树。

2、损失函数为“指数损失函数”

3、针对Boosting需要解决的两个问题，AdaBoost算法采用了以下策略：

1. 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；
2. 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。

特点

1. 核心思想：针对同一个训练集训练不同的弱分类器，然后把这些弱分类器根据权值集合起来，构造一个更强的最终分类器。
2. Adaboost算法是Boosting系列算法之一，强分类器输出结果的是弱分类器输出结果的加权平均。
3. Adaboost算法有两个权值，分别为样本权值和弱分类器权值，其主要特征就是在于样本权值的更新和弱分类器权值的更新。
4. Adaboost中所有的弱分类器必须是同一种分类器，不能在同一个Adaboost算法的迭代步骤中使用不同的弱分类器。
5. 弱分类器可并行实现。

算法的优缺点

Adaboost的主要优点有：

1. Adaboost作为分类器时，分类精度很高
2. 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
3. 作为简单的二元分类器时，构造简单，结果可理解。
4. 不容易发生过拟合

Adaboost的主要缺点有：

1. 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。
   　　　　

权值更新规则

样本权值更新：

对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突显出来，从而得到一个新的样本分布。

弱分类器权值更新：

对于准确率较高的弱分类器，加大其权重；对于准确率较低的弱分类器，减小其权重。

适用范围

1. 用于二分类或多分类的应用场景
2. 用于做分类任务的baseline

算法过程

将样本权值被更新过的新数据集送给下层弱分类器进行训练，最后将每次训练得到的弱分类器根据弱分类器权重融合起来，从而得到强分类器。

1. 给定训练样本集S，其中X和Y分别对应于正例样本和负例样本； T为训练的最大循环次数；
2. 初始化样本权重为1/n ，即为训练样本的初始概率分布；
3. 第一次迭代：
   (1) 训练样本的概率分布相当下，训练弱分类器；
   (2) 计算弱分类器的错误率；
   (3) 选取合适阈值，使得误差最小；
   (4) 更新样本权重；
   经T次循环后，得到T个弱分类器，按更新的弱分类器权重叠加，最终得到的强分类器。

---

Gradient Boosting算法

算法的实现：

1、函数模型为CART回归树模型

2、损失函数一般为“对数损失函数”或“指数损失函数”
Gradient Boosting算法即梯度提升算法，

3、优化算法采用梯度下降

4、针对Boosting需要解决的两个问题，Gradient Boosting算法采用了以下策略：

1. 将残差作为下一个弱分类器的训练数据，每个新的弱分类器的建立都是为了使得之前弱分类器的残差往梯度方向减少。
2. 将弱分类器联合起来，使用累加机制代替平均投票机制。

特点

1. 核心思想：每个新的弱分类器的建立是为了使得之前弱分类器的残差往梯度方向减少，然后把弱分类器进行累加得到强分类器。
2. GBDT算法是Boosting系列算法之一，强分类器的输出结果是弱分类器输出结果的累加。
3. GBDT中所有的弱分类器只能是CART回归树
4. 弱分类器无法并行实现

算法的优缺点

GBDT主要的优点有：

1. 可以灵活处理各种类型的数据，包括连续值和离散值。
2. 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
3. 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

GBDT的主要缺点有：

1. 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

适用范围

1. GBDT几乎可用于所有的回归问题（线性/非线性）
2. 亦可用于二分类问题（设定阈值，大于阈值为正例，小于阈值为反例）
3. 不太适用于多分类问题

算法过程

1. 对数据拟合一个简单的线性回归或决策树
2. 计算误差残差。实际目标值减去预测目标值
3. 将误差残差的新模型作为具有相同输入变量的目标变量
4. 将预测的残差添加到先前的预测中[y_predicted2 = y_predicted1 + e1_predicted]
5. 在剩余的残差上拟合另一个模型。即[e2 = y-y_predicted2]并重复步骤2到5，直到它开始过拟合或残差总和变成恒定。

工作过程实例

以年龄预测为例，A,B,C,D四个人，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：

现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：

在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。

换句话说，现在A,B,C,D的预测值都和真实年龄一致了。Perfect!：

A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14

B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16

C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24

D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26