Boosting

链接:
1. 线性回归总结
2. 正则化
3. 逻辑回归
4. Boosting
5. Adaboost算法

---

模型来源

提升算法是常用的有效的统计学习算法，属于迭代算法，它通过不断地使用一个弱学习器弥补前一个弱学习器的“不足”的过程，来串行地构造一个较强的学习器，这个强学习器能够使目标函数值足够小。从优化的角度分析，与一般的在参数空间搜索最优解的学习算法（如神经网络）类似，Boosting也是一个迭代搜索，且最优的算法，不同的是，它的搜索空间是学习器空间，或说函数空间（Function space），它的搜索方向是构造不断完善的强学习器，以达到目标函数（或说误差函数）足够小的目的。 Bagging也是一种常用的统计学习方法，两者经常放在一起对比，它们不同的是，Bagging将在Bootstrap采样得到的不同训练子集上的弱学习器的结果综合考虑，各个弱学习器的构建过程是并行的。而Boosting是通过串行地不断迭加弱学习器形成一个强学习器，是学习模型的提升过程。此外，Boosting迭代在降低训练误差的同时，使模型预测的确信度（margin）不断提高，是它获得较好泛化能力的主要原因，而Bagging主要是通过平均来降低模型的方差(variation).

example

为说明Boosting的主要过程，下面举一个简化的例子。 假设训练数据集为(x1,y1),(x2,y2),...,(xn,yn)我们的任务是寻找使这个回归问题的均方误差最小的模型F(x). 如果已经有一个初始的模型f,且f(x1)=0.8,但y1=0.9 ,f(x2)=1.4,但y2=1.3 …显然f是不完美的，我们可以采用不断完善f的方式,如不断在f的基础上增加模型（如决策树）h,即：f(x)←f(x)+h(x),使f 趋于F. 我们希望：

f(x1)+h(x1)=y1      ====>      h(x1)=y1−f(x1)
f(x2)+h(x2)=y2      ====>      h(x2)=y2−f(x2)
...                          ====>      ...
f(xn)+h(xn)=yn      ====>      h(xn)=yn−f(xn)

然而恰好满足上式的h可能不存在，但我们总可以找到使残差yi−f(xi)变小的h. 上述过程等价于拟合如下数据集：

(x1,y1−f(x1))
(x2,y2−f(x2))
...
(xn,yn−f(xn))

上述一次叠加h的过程就是Boosting的一次迭代。要使f足够接近F一般需要多次迭代。

依据损失函数的不同具体分类有：

损失函数

链接:关于AdaBoost的算法推导

Gradient Boosting

和Adaboost不同，Gradient Boosting 在迭代的时候选择梯度下降的方向来保证最后的结果最好。
损失函数用来描述模型的“靠谱”程度，假设模型没有过拟合，损失函数越大，模型的错误率越高
如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度方向上下降。

Grandient Boosting

import numpy as np
import matplotlib.pyplot as plt
from sklearn import ensemble
from sklearn import datasets
from sklearn.utils import shuffle
from sklearn.metrics import mean_squared_error
#########################################
# Load data
boston = datasets.load_boston()
X, y = shuffle(boston.data, boston.target, random_state=13)
X = X.astype(np.float32)
offset = int(X.shape[0] * 0.9)
X_train, y_train = X[:offset], y[:offset]
X_test, y_test = X[offset:], y[offset:]
########################################
# Fit regression model
params = {'n_estimators': 500, 'max_depth': 4, 'min_samples_split': 1,
          'learning_rate': 0.01, 'loss': 'ls'}
clf = ensemble.GradientBoostingRegressor(**params)
clf.fit(X_train, y_train)
mse = mean_squared_error(y_test, clf.predict(X_test))
print("MSE: %.4f" % mse)

Adaboost

Adaboost 迭代算法就3步：

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

给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)}，yi属于标记集合{-1,+1}，Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。

Adaboost的算法流程如下：
步骤1. 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：1/N。

步骤2. 进行多轮迭代，用m = 1,2, ..., M表示迭代的第多少轮
a. 使用具有权值分布Dm的训练数据集学习，得到基本分类器（选取让误差率最低的阈值来设计基本分类器）：

b. 计算Gm(x)在训练数据集上的分类误差率

由上述式子可知，Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。
c. 计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的权重）：

由上述式子可知，em <= 1/2时，am >= 0，且αm随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。
d. 更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代

使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。
其中，Zm是规范化因子，使得Dm+1成为一个概率分布：

**步骤3. **组合各个弱分类器

从而得到最终分类器，如下：

#################################################
Adaboost的一个例子

下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。

求解过程：初始化训练数据的权值分布，令每个权值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分别对于m = 1,2,3, ...等值进行迭代。
拿到这10个数据的训练样本后，根据 X 和 Y 的对应关系，要把这10个数据分为两类，一类是“1”，一类是“-1”，根据数据的特点发现：“0 1 2”这3个数据对应的类是“1”，“3 4 5”这3个数据对应的类是“-1”，“6 7 8”这3个数据对应的类是“1”，9是比较孤独的，对应类“-1”。抛开孤独的9不讲，“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据，分别对应的类是1、-1、1，直观上推测可知，可以找到对应的数据分界点，比如2.5、5.5、8.5 将那几类数据分成两类。当然，这只是主观臆测，下面实际计算下这个具体过程。
迭代过程1
对于m=1，在权值分布为D1（10个数据，每个数据的权值皆初始化为0.1）的训练数据上，经过计算可得：
阈值v取2.5时误差率为0.3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.3），
阈值v取5.5时误差率最低为0.4（x < 5.5时取1，x > 5.5时取-1，则3 4 5 6 7 8皆分错，误差率0.6大于0.5，不可取。故令x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.4），
阈值v取8.5时误差率为0.3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.3）。

可以看到，无论阈值v取2.5，还是8.5，总得分错3个样本，故可任取其中任意一个如2.5，弄成第一个基本分类器为：

上面说阈值v取2.5时则6 7 8分错，所以误差率为0.3，更加详细的解释是：因为样本集中
0 1 2对应的类（Y）是1，因它们本身都小于2.5，所以被G1(x)分在了相应的类“1”中，分对了。
3 4 5本身对应的类（Y）是-1，因它们本身都大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。
但6 7 8本身对应类（Y）是1，却因它们本身大于2.5而被G1(x)分在了类"-1"中，所以这3个样本被分错了。
9本身对应的类（Y）是-1，因它本身大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。

从而得到G1(x)在训练数据集上的误差率（被G1(x)误分类样本“6 7 8”的权值之和）e1=P(G1(xi)≠yi) = 30.1 = 0.3*。
然后根据误差率e1计算G1的系数：

这个a1代表G1(x)在最终的分类函数中所占的权重，为0.4236。接着更新训练数据的权值分布，用于下一轮迭代：

值得一提的是，由权值更新的公式可知，每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确。
即如果某个样本被分错了，则yi * Gm(xi)为负，负负得正，结果使得整个式子变大（样本权值变大），否则变小。
第一轮迭代后，最后得到各个数据新的权值分布D2= (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715,0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出，因为样本中是数据“6 7 8”被G1(x)分错了，所以它们的权值由之前的0.1增大到0.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到0.0715。
分类函数f1(x)= a1G1(x) = 0.4236G1(x)。
此时，得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点（即6 7 8）。
从上述第一轮的整个迭代过程可以看出：被误分类样本的权值之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。
迭代过程2
对于m=2，在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上，经过计算可得：
阈值v取2.5时误差率为0.16663（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.16663），
阈值v取5.5时误差率最低为0.07154（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.07153 + 0.0715），
阈值v取8.5时误差率为0.07153（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.0715*3）。

所以，阈值v取8.5时误差率最低，故第二个基本分类器为：

面对的还是下述样本：

很明显，G2(x)把样本“3 4 5”分错了，根据D2可知它们的权值为0.0715, 0.0715, 0.0715，所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。
计算G2的系数：

更新训练数据的权值分布：

D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大，其它被分对的样本的权值变小。f2(x)=0.4236G1(x) + 0.6496G2(x)此时，得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点（即3 4 5）。
迭代过程3
对于m=3，在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上，经过计算可得：
阈值v取2.5时误差率为0.10603（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.10603），
阈值v取5.5时误差率最低为0.04554（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.04553 + 0.0715），
阈值v取8.5时误差率为0.16673（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.16673）。

所以阈值v取5.5时误差率最低，故第三个基本分类器为：

依然还是原样本：

此时，被误分类的样本是：0 1 2 9，这4个样本所对应的权值皆为0.0455，
所以G3(x)在训练数据集上的误差率e3= P(G3(xi)≠yi) = 0.04554* = 0.1820。
计算G3的系数：

更新训练数据的权值分布：

D4 = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)。被分错的样本“0 1 2 9”的权值变大，其它被分对的样本的权值变小。
f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)
此时，得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此，整个训练过程结束。
现在，咱们来总结下3轮迭代下来，各个样本权值和误差率的变化，如下所示（其中，样本权值D中加了下划线的表示在上一轮中被分错的样本的新权值）：
训练之前，各个样本的权值被初始化为D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1)；
第一轮迭代中，样本“6 7 8”被分错，对应的误差率为e1=P(G1(xi)≠yi) = 3*0.1 = 0.3，此第一个基本分类器在最终的分类器中所占的权重为a1 = 0.4236。第一轮迭代过后，样本新的权值为D2= (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)；

第二轮迭代中，样本“3 4 5”被分错，对应的误差率为e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143，此第二个基本分类器在最终的分类器中所占的权重为a2 = 0.6496。第二轮迭代过后，样本新的权值为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)；

第三轮迭代中，样本“0 1 2 9”被分错，对应的误差率为e3= P(G3(xi)≠yi) = 0.04554 = 0.1820，此第三个基本分类器在最终的分类器中所占的权重为a3* = 0.7514。第三轮迭代过后，样本新的权值为**D4 **= (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)。

从上述过程中可以发现，如果某些个样本被分错，它们在下一轮迭代中的权值将被增大，反之，其它被分对的样本在下一轮迭代中的权值将被减小。就这样，分错样本权值增大，分对样本权值变小，而在下一轮迭代中，总是选取让误差率最低的阈值来设计基本分类器，所以误差率e（所有被Gm(x)误分类样本的权值之和）不断降低。
综上，将上面计算得到的a1、a2、a3各值代入G(x)中，G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]，得到最终的分类器为：
G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

2 Adaboost的误差界
通过上面的例子可知，Adaboost在学习的过程中不断减少训练误差e，直到各个弱分类器组合成最终分类器，那这个最终分类器的误差界到底是多少呢？
事实上，Adaboost 最终分类器的训练误差的上界为：

下面，咱们来通过推导来证明下上述式子。
当G(xi)≠yi时，yif(xi)<0，因而exp(-yif(xi))≥1，因此前半部分得证。
关于后半部分，别忘了：

整个的推导过程如下：

这个结果说明，可以在每一轮选取适当的Gm使得Zm最小，从而使训练误差下降最快。接着，咱们来继续求上述结果的上界。
对于二分类而言，有如下结果：

其中，

。
继续证明下这个结论。
由之前Zm的定义式跟本节最开始得到的结论可知：

而这个不等式

可先由e^x和1-x的开根号，在点x的泰勒展开式推出。
值得一提的是，如果取γ1, γ2… 的最小值，记做γ（显然，γ≥γi>0，i=1,2,...m），则对于所有m，有：

这个结论表明，AdaBoost的训练误差是以指数速率下降的。另外，AdaBoost算法不需要事先知道下界γ，AdaBoost具有自适应性，它能适应弱分类器各自的训练误差率 。
最后，Adaboost 还有另外一种理解，即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法

参考：
Boosting
Adaboost 算法的原理与推导(JUly)