# AdaBoost ## AdaBoost 为Boosting算法 Boosting基本流程 * 先从初始训练集**训练一个基学习器 G1**； * 再根据基学习器G1的表现对训练样本分布做调整：先前基学习器识别错的训练样本在后续受到更多关注）； * 基于调整后的训练样本分布，训练出一个新的基学习器G2 * 反复进行，直到达到**指定T个基学习器个数{G1,G2,...,GT}，最终将这T个加权结合**，变为一个强的集成学习器 $$ (G=a\_1*G\_1+a\_2*G\_2+...+a\_T\*G\_T) $$ ![img](https://images2015.cnblogs.com/blog/1042406/201612/1042406-20161204194331365-2142863547.png) ## Adaboost实现 Adaboost**既可以用作分类，也可以用作回归**。 ### 1.分类 理论上可以选择任何一个分类或者回归学习器作为其基础学习器，不过需要支持样本权重。 * 我们可以假设设计使用的基学习器是CART( * CART的优点就是可以分类和回归，这和AdaBoost一样，因此很适合做为其基础学习器，实际上，后面使用的sklearn对Adaboost的使用也是默认使用这个的。 #### 1）定义样本权重 * 假设我们的训练集样本是：$$D={(x\_1,y\_1),...,(x\_m,y\_m)}$$，为每个样本赋予一个权重$$w\_i$$ * 训练集在第 t 轮弱学习器的输出权重为：$$D\_t=(w\_{t1},w\_{t2},...,w\_{tm})$$ * 初始分布权重都一样大为：$$D\_0=(\frac{1}{m},\frac{1}{m},...,\frac{1}{m})$$ #### 2）定义第 t 轮弱学习器的误差 $$e\_t=P(h\_t(x\_i) \ne y\_i)=\sum\_{i=1}^m w\_{ti} I(h\_t(x\_i) \ne y\_i)$$ （还有另外一种，计算准确率，不过这样的话后面4）对样本权重的计算就改反了） （也就是说，学习器如这里的CART，**训练的时候还是不需要管其样本权重这个集成里面的概念的，其单独训练完成以后，样本权重最终使用的地方就在交叉验证等计算错误率的时候，乘上了权重**，就是我们的弱学习器的误差了） #### 3）定义第 t 轮学习器其本身的权重 （怎么来的后面解释推导） $$\alpha\_t=\frac{1}{2}log \frac{1-e\_t}{e\_t}$$ 可见，这里$$e\_t >0.5$$时，如0.6：$$log \frac{0.4}{0.6}<0$$，是非法的，此时要么终止学习，要么重新学习一个$$h\_t$$ #### 4）定义第 t轮学习器，权重分布D的更新方式 （怎么来的后面解释推导） $$ W\_{t+1}=W\_t.\frac{e^{-f(x)\alpha\_t h\_t(x)}}{E\_{x \sim D}\[e^{-f(x)\alpha\_t h\_t(x)}]} $$ （**分错的f(x)ht(x)0)权重越来越小**？？？因为这样得到的误差$$e\_k$$就会越来越接近真实的误差，得到真实的误差，就能计算出更真实的加权值$$\alpha\_k$$，这样多个学习器加权累积起来，就可能抵消前面学习器的错误影响，集成出一个更真实的分类模型） (如果2）是基于计算准确率的，那么这里就要反一下，比如去掉里面的负号，那么分错的样本权重越小，对的越大) #### 5）最终的强学习器 Adaboost分类采用的是加权表决法，按照4.1那T轮，根据上面1)-4)的计算后，最终的强分类器为 $$ H(x)=sign(\sum\_{t=1}^T\alpha\_th\_t(x)) $$ 即f(x)>0表示正例，....。看到这其实可以直接看结尾了，后面推导比较难。 #### 6）推导 **对 3）的推导** 思想，基于已知的样本权重（第一次设为均匀的1/m）分布训练，产生第 t 个基分类器，进而计算错误率 ，先假定权重已知，定义指数损失函数为：（西瓜书🍉8.9） $$ \begin{aligned} &\color{Red}{L\_{exp}}(\alpha\_th\_t|D\_t)=E\_{x \sim D\_t}\[e^{-f(x)\alpha\_t h\_t(x)}]\\ &=E\_{x \sim D\_t} \[e^{-\alpha\_t \prod (f(x)=h\_t(x))}+e^{\alpha\_t \prod (f(x) \ne h\_t(x))}]\\ &=e^{-\alpha\_t}P\_{x \sim D\_t}(f(x)=h\_t(x))+e^{\alpha\_t}P\_{x \sim D\_t}(f(x) \ne h\_t(x))\\ &=e^{-\alpha\_t}(1-\epsilon\_t)+e^{\alpha\_t} \epsilon\_t \end{aligned} $$ 因为上面最后的加法运算，**左边加的**$$e^{-\alpha\_t}$$**代表正确率，右边加的是**$$e^{\alpha\_t}$$**代表错误率** 所以，**我们希望**$$\alpha\_t$$**能尽可最小化**$$D\_t$$**分布下关于**$$\alpha\_t h\_t$$**的指数损失函数，即，上面左右加起来后的结果趋于极小**，因此转而对上面求导： $$ \begin{aligned} &\frac{\partial L\_{exp}(\alpha\_t h\_t|D\_t)}{\partial \alpha\_t}=\frac{\partial (e^{-\alpha\_t}(1-\epsilon\_t)+e^{\alpha\_t} \epsilon\_t)}{\partial \alpha\_t}\\ &=-e^{\alpha\_t}(1-\epsilon\_t)+e^{\alpha\_t}\epsilon\_t\\ &=(1-\epsilon\_t)-e^{2\alpha\_t}\epsilon\_t\\ &=0\\ \&so:\frac{1-\epsilon\_t}{\epsilon\_t}=e^{2\alpha\_t}\\ &\alpha\_t=\frac{1}{2}ln \frac{1-\epsilon\_t}{\epsilon\_t} \end{aligned} $$ 至此证明3）中那个每轮弱学习器，在算得损失后，自身在集成中占有的权重。 **对 4）的推导** 在学得集成学习器$$H\_{t-1}$$后，希望下一轮学到的基学习器能够纠正错误，**理想的就是纠正所有错误，也就是最小化指数损失函数**： $$ \begin{aligned} \&L\_{exp}(H\_{t-1}+h\_t|D)=E\_{x \sim D}\[e^{-f(x)(H\_{t-1}(x)+h\_t(x))}]\\ &=E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.e^{-f(x)h\_t(x)}] \end{aligned} $$ 根据$$e^x$$的泰勒展开式，得上式子有： $$ \begin{aligned} &\approx E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.(1-f(x)h\_t(x)+\frac{1}{2}(f(x)h\_t(x))^2)]\\ &=E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.(1-f(x)h\_t(x)+\frac{1}{2}(1)^2)]\\ &=E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.(\frac{3}{2}-f(x)h\_t(x))] \end{aligned} $$ 因此理想的下一个基学习器$$h\_t$$，为下式极大值对应的h: $$ \begin{aligned} h\_t(x)&=\mathop{\arg\min}*{h} L*{exp}(H\_{t-1}+h\_t|D)\\ &=\mathop{\arg \min}*{h} E*{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.(\frac{3}{2}-f(x)h\_t(x))]\\ &=\mathop{\arg\max}*{h} E*{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.f(x)h\_t(x)] \end{aligned} $$ 构造出分布新，第t轮时候权重的分布$$D\_t$$：（D为初始化时候的分布，） $$ D\_t=\frac{De^{-f(x)H\_{t-1}(x)}}{E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}]} $$ 加入当前集成学习期望(就是下面分母多的那个，是常数，对argmax无影响)，则ht可以变成D(x)分布到Dt(x)分布的转变： $$ \begin{aligned} \&h\_t(x)=\mathop{arg \max }*{h} E*{x \sim D}\[\frac{e^{-f(x)H\_{t-1}(x)}}{E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}]}f(x)h\_t(x)]\\ &=\mathop{arg \max}*{h}E*{x \sim D\_t}\[f(x)h\_t(x)] \end{aligned} $$ 因为： $$ f(x)h\_t(x)= \begin{cases} 1\\ -1 \end{cases} \=1-2\[\prod f(x) \ne h\_t(x)] $$ 所以还能等价变成最小化： $$ h\_t(x)=\mathop{arg \min}*{h}E*{x \sim D\_t}\[\prod f(x) \ne h\_t(x)] $$ 搞了这么多推算，竟然得出这么个无关的结论？即，理想的下一个学习器是： * **期望真实值f(x)！=预测值h(x)尽可能小** * 变成最小化这个Dt分布时的期望的时候的t轮弱学习器ht，是希望学到新弱学习器 不过，现在返回去，由上面的Dt分布，及关系**E(XY)=E(X)E(Y)**，就能**得到分布D的前后迭代更新形式**了， 由上面的公式 $$ D\_t=\frac{De^{-f(x)H\_{t-1}(x)}}{E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}]} $$ 得（这里把第t轮的权重也加进来了） $$ \begin{aligned} \&D\_{t+1}=\frac{De^{-f(x)H\_{t}(x)}}{E\_{x \sim D}\[e^{-f(x)H\_{t}(x)}]}=\frac{De^{-f(x)H\_{t-1}(x)}.e^{-f(x)\alpha\_th\_t(x)}}{\color{Red}{E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}.e^{-f(x)\alpha\_t h\_t(x)}]}} \\ &=\frac{De^{-f(x)H\_{t-1}(x)}.e^{-f(x)\alpha\_th\_t(x)}}{\color{Red}{E\_{x \sim D}\[e^{-f(x)H\_{t-1}(x)}]E\_{x \sim D}\[e^{-f(x)\alpha\_t h\_t(x)}]}} \end{aligned} $$ 解释一下其中符号，这些符号最终都是数字，能让分布转为一个概率： ![](/files/-LqBk-wmnT3xXxGCRbih) 所以，第4）步中的更新，只是把分布D写开了，写在一起就是上面那个更新形式。 而第一次迭代的分布D为均匀的1/m。 其它时候D中的**m个样本对应的权重按照4）**这个更新： （$$w\_{t+1}$$对应$$D\_{t+1}$$里面的每个权重，$$w\_{t}$$对应$$D\_{t}$$里面的每个权重） $$ W\_{t+1}=W\_t.\frac{e^{-f(x)\alpha\_t h\_t(x)}}{E\_{x \sim D}\[e^{-f(x)\alpha\_t h\_t(x)}]} $$ 至此，4）的证明结束。 #### 7）最终Adaboost分类流程 \> > > 数据集：D={(x1,y1),...,(xm,ym)} > > 1）设置分布D0=1/m > > 2）for t=1,2,....,T（T个弱学习器，这个自己指定） do: > > ``` > ht=Algri(D,Dt) //根据Dt样本权重分布，从数据集D中训练出弱模型，如CART > ``` > > epsilon\_t=P(ht(x)!=f(x)) //上面的2)节形式计算第t轮弱学习器误差\ > if epsilon\_t>0.5 then break //训练太差就不进一步学了，这样实际上得不到T个弱学习去，因此这种情况时，还可以从初始分布或者随机分布中学到ht。\ > 按照上面 3）节更新\ > 对分布Dt 中每个wti更新，按照4）节形式更新 3）end for > > 4\) 按照5）节中形式加权累积起来作为集成模型输出。 #### 8）代码跑起来 ```python from sklearn.model_selection import KFold from sklearn.model_selection import cross_val_score from sklearn.ensemble import AdaBoostClassifier from sklearn.tree import DecisionTreeClassifier from sklearn import datasets # 加载数据 dataset = datasets.load_breast_cancer() X = dataset.data Y = dataset.target seed = 1 # 10折交叉验证 kfold = KFold(n_splits=10, random_state=seed) # 指定弱（分类）学习器 # 这里指定CART(criterion='gini'表示用CART),设置弱分类器maxdepth=3 dtree = DecisionTreeClassifier(criterion='gini', max_depth=3) # dtree = dtree.fit(X, Y) # result = cross_val_score(dtree, X, Y, cv=kfold) # print(result.mean()) # base_estimator指定上面的CART model = AdaBoostClassifier(base_estimator=dtree, n_estimators=100, random_state=seed) result = cross_val_score(model, X, Y, cv=kfold) print('10折交叉验证的分数：',result.mean()) #10折交叉验证的分数： 0.9666040100250626 ``` ### 2.回归 和分类基本一样路子，只不过具体的误差计算，权重更新需要改一下，以适应分类类型，基本模子不变，因此简单写了。 #### 1）定义第 t 个弱学习器，训练集上的最大误差 $$ E\_t=max|y\_i-h\_t(x\_i)|,i=1,2,...,m $$ #### 2）样本的误差 第t轮，第i个样本的误差，**显然，这些都0<=，<=1** 相对误差： $$ e\_{ti}=\frac{|y\_i-h\_t(x\_i)|}{E\_t} $$ 平方误差： $$ e\_{ti}=\frac{|y\_i-h\_t(x\_i)|^2}{E\_t^2} $$ 指数误差： $$ e\_{ti}=1-exp(\frac{-y\_i+h\_t(x\_i)}{E\_t}) $$ #### 3）第 t 个弱学习器的误差 也就是这个误差怎么用，看你选了，公式的意思就是样本权重和样本误差加权和，作为整个训练集误差 $$ e\_t=\sum\_{i=1}^m w\_{ti}e\_{ti} $$ #### 4）第t个学习器权重 ​ 因为**回归问题误差是与真实值之间的差距而不是分类里面的是和否，A/B等等了**，因此没必要像上面分类那样推导出权重，这里按照启发为：误差率/正确率。其实这并不固定的 $$ \alpha\_t=\frac{e\_t}{1-e\_t} $$ （可见这里是错误率越高，$$h\_t$$ 权重越大。） #### 5）第 t 个弱学习器的第 i 个样本权重更新 Z就是简单的，**样本权重和学习器权重^样本正确度**加权和，这样更新后依旧可以表示一个分布 $$ w\_{t+1,i}=\frac{w\_{ti}}{Z\_t}\alpha\_t^{1-e\_{ti}},Z\_t=\sum\_{i=1}^mw\_{ti}\alpha\_t^{1-e\_{ti}} $$ #### 6）最终集成学习器为 $$h\_c(x)$$为T个$$\alpha\_th\_t(x)$$**乘积排列的中位数**（不是固定值，每次根据x不同不一样，比较回归你总不能和分类那样简单多数投票吧，当然得是均值了），T为弱学习器的个数 $$ h(x)=\sum\_{t=1}^T(ln\frac{1}{\alpha\_t})h\_c(x) $$ 可见，$$\alpha\_t$$越大，$$ln \frac{1}{\alpha\_t}$$越小，此时作用在hc上的权值越小 而4）说了，错误率越大$$\alpha\_t$$越大，因此，**错误率越大的作用在hc上越小**） #### 回归方面的使用： ```python from sklearn.model_selection import KFold from sklearn.model_selection import train_test_split import numpy as np from sklearn.ensemble import AdaBoostRegressor from sklearn.tree import DecisionTreeRegressor from sklearn.svm import LinearSVR from matplotlib import pyplot as plt from mpl_toolkits.mplot3d import Axes3D fig = plt.figure() plt.rcParams['font.sans-serif'] = ['SimHei'] # 用来正常显示中文标签 plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号 ax = Axes3D(fig) seed = 1 def load_data_regression(): # 构造X数据 c=np.random.rand(220) X =np.array([c+2*i for i in range(2)]).T # 构造y数据， y = 1 * x_0 + 2 * x_1 + 3，后面打印参数会发现，是一致的 y = np.dot(X, np.array([1, 2])) + 1 return train_test_split(X, y, test_size=0.2, random_state=0) X_train, X_test, y_train, y_test = load_data_regression() # 10折交叉验证 kfold = KFold(n_splits=10, random_state=seed) # 弱回归器：CART(criterion='gini'表示用CART),设置弱回归器maxdepth=3 dtree = DecisionTreeRegressor(max_depth=3) # model = AdaBoostRegressor(base_estimator=LinearSVR(epsilon=0.01, C=100), n_estimators=200, random_state=seed) model = AdaBoostRegressor(base_estimator=dtree, n_estimators=300, random_state=seed) model.fit(X_train, y_train) result = model.predict(X_test) # # 计算准确率 cnt1 = 0 cnt2 = 0 for i in range(len(y_test)): if abs(result[i] - y_test[i]) < 0.1: cnt1 += 1 else: cnt2 += 1 print("Accuracy: %.2f %% " % (100 * cnt1 / (cnt1 + cnt2))) ax.scatter(X_train[:, 0], X_train[:, 1], y_train, marker='o') ax.plot(X_test[:, 0], X_test[:, 1], result) plt.show() ``` ### Adaboost的正则化 为了防止Adaboost过拟合，通常也会加入正则化项，这个正则化项通常称为步长(learning rate)。定义为ν，对于前面的弱学习器的迭代： ![](https://private.codecogs.com/gif.latex?%5Clarge%20f_%7Bt%7D%28x%29%20%3D%20h_%7Bt-1%7D%28x%29%20\+%20%5Calpha_th_t%28x%29) 加入正则化v，**0\ 1）Adaboost作为分类器时，分类精度很高 > > 2）在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。 > > 3）作为简单的二元分类器时，构造简单，结果可理解。 > > 4）不容易发生过拟合 Adaboost的主要缺点有： > 1）对异常样本敏感，**异常样本在迭代中可能会获得较高的权重**，影响最终的强学习器的预测准确性。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/ml/ji-cheng/adaboost.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.