网站网站开发设计,推广收款码平台有哪些,在线玩的网页小游戏,做调查网站怎样换IPAdaboost 算法介绍
1. 集成学习
集成学习#xff08;ensemble learning#xff09;通过构建并结合多个学习器#xff08;learner#xff09;来完成学习任务#xff0c;通常可获得比单一学习器更良好的泛化性能#xff08;特别是在集成弱学习器#xff08;weak learner…
Adaboost 算法介绍
1. 集成学习
集成学习ensemble learning通过构建并结合多个学习器learner来完成学习任务通常可获得比单一学习器更良好的泛化性能特别是在集成弱学习器weak learner时。
目前集成学习主要分为2大类
一类是以bagging、Random Forest等算法为代表的各个学习器之间相互独立、可同时生成的并行化方法
一类是以boosting、Adaboost等算法为代表的个体学习器是串行序列化生成的、具有依赖关系它试图不断增强单个学习器的学习能力。
2. Adaboost 算法详解
2.1 Adaboost 步骤概览 初始化训练样本的权值分布每个训练样本的权值应该相等如果一共有 N N N个样本则每个样本的权值为 1 N \frac{1}{N} N1) 依次构造训练集并训练弱分类器。如果一个样本被准确分类那么它的权值在下一个训练集中就会降低相反如果它被分类错误那么它在下个训练集中的权值就会提高。权值更新过后的训练集会用于训练下一个分类器。 将训练好的弱分类器集成为一个强分类器误差率小的弱分类器会在最终的强分类器里占据更大的权重否则较小。
2.2 Adaboost 算法流程
给定一个样本数量为 m m m的数据集 T { ( x 1 , y 1 ) , … , ( x m , y m ) } T \left \{\left(x_{1}, y_{1}\right), \ldots,\left(x_{m}, y_{m}\right) \right \} T{(x1,y1),…,(xm,ym)} y i y_i yi 属于标记集合 { − 1 , 1 } \{-1,1\} {−1,1}。
训练集的在第 k k k个弱学习器的输出权重为 D ( k ) ( w k 1 , w k 2 , … w k m ) ; w 1 i 1 m ; i 1 , 2 … m D(k)\left(w_{k 1}, w_{k 2}, \ldots w_{k m}\right) ; \quad w_{1 i}\frac{1}{m} ; i1,2 \ldots m D(k)(wk1,wk2,…wkm);w1im1;i1,2…m
初始化训练样本的权值分布每个训练样本的权值相同 D ( 1 ) ( w 11 , w 12 , … w 1 m ) ; w 1 i 1 m ; i 1 , 2 … m D(1)\left(w_{1 1}, w_{1 2}, \ldots w_{1 m}\right) ; \quad w_{1 i}\frac{1}{m} ; i1,2 \ldots m D(1)(w11,w12,…w1m);w1im1;i1,2…m
进行多轮迭代产生 T T T个弱分类器。 使用权值分布 $D(t) $的训练集进行训练得到一个弱分类器 G t ( x ) : χ → { − 1 , 1 } G_{t}(x) : \quad \chi \rightarrow\{-1,1\} Gt(x):χ→{−1,1}
计算 G t ( x ) G_t(x) Gt(x) 在训练数据集上的分类误差率其实就是被 $G_t(x) $误分类样本的权值之和: e t P ( G t ( x i ) ≠ y i ) ∑ i 1 m w t i I ( G t ( x i ) ≠ y i ) e_{t}P\left(G_{t}\left(x_{i}\right) \neq y_{i}\right)\sum_{i1}^{m} w_{t i} I\left(G_{t}\left(x_{i}\right) \neq y_{i}\right) etP(Gt(xi)yi)i1∑mwtiI(Gt(xi)yi)
计算弱分类器 Gt(x) 在最终分类器中的系数(即所占权重) α t 1 2 ln 1 − e t e t \alpha_{t}\frac{1}{2} \ln \frac{1-e_{t}}{e_{t}} αt21lnet1−et更新训练数据集的权值分布用于下一轮t1迭代 D ( t 1 ) ( w t 1 , 1 , w t 1 , 2 , ⋯ w t 1 , i ⋯ , w t 1 , m ) D(t1)\left(w_{t1,1} ,w_{t1,2} ,\cdots w_{t1, i} \cdots, w_{t1, m}\right) D(t1)(wt1,1,wt1,2,⋯wt1,i⋯,wt1,m) w t 1 , i w t , i Z t × { e − α t i f G t ( x i ) y i e α t i f G t ( x i ) ≠ y i w t , i Z t exp ( − α t y i G t ( x i ) ) w_{t1,i}\frac{w_{t,i}}{Z_{t}} \times \left\{\begin{array}{ll}{e^{-\alpha_{t}}} {\text { if } G_{t}\left(x_{i}\right)y_{i}} \\ {e^{\alpha_{t}}} {\text { if } G_{t}\left(x_{i}\right) \neq y_{i}}\end{array}\right. \frac{w_{t,i}}{Z_{t}} \exp \left(-\alpha_{t} y_{i} G_{t}\left(x_{i}\right)\right) wt1,iZtwt,i×{e−αteαtifGt(xi)yiifGt(xi)yiZtwt,iexp(−αtyiGt(xi))
其中 Z t Z_t Zt是规范化因子使得 D ( t 1 ) D(t1) D(t1)成为一个概率分布和为1 Z t ∑ j 1 m w t , i exp ( − α t y i G t ( x i ) ) Z_{t}\sum_{j1}^{m} w_{t,i} \exp \left(-\alpha_{t} y_{i} G_{t}\left(x_{i}\right)\right) Ztj1∑mwt,iexp(−αtyiGt(xi))
集成 T T T个弱分类器为1个最终的强分类器 G ( x ) sign ( ∑ t 1 T α t G t ( x ) ) G(x)\operatorname{sign}\left(\sum_{t1}^{T} \alpha_{t} G_{t}(x)\right) G(x)sign(t1∑TαtGt(x))
3. 算法面试题
3.1 Adaboost分类模型的学习器的权重系数 α \alpha α怎么计算的
Adaboost是前向分步加法算法的特例分类问题的时候认为损失函数指数函数。 当基函数是分类器时Adaboost的最终分类器是 f ( x ) ∑ m − 1 M α m G m ( x ) f m − 1 ( x ) α m G m ( x ) f(x)\sum_{m-1}^{M}{\alpha_mG_m(x)}f_{m-1}(x){\alpha_mG_m(x)} f(x)m−1∑MαmGm(x)fm−1(x)αmGm(x) 目标是使前向分步算法得到的 α \alpha α和 G m ( x ) G_m(x) Gm(x)使 f m ( x ) f_m(x) fm(x)在训练数据集T上的指数损失函数最小即 ( α , G m ( x ) ) a r g m i n α , G ∑ i 1 N e x p [ − y i ( f m − 1 ( x i ) α G ( x i ) ) ] (\alpha, G_m(x))arg min_{\alpha, G}\sum_{i1}^{N}exp[-y_i(f_{m-1}(x_i)\alpha G(x_i))] (α,Gm(x))argminα,Gi1∑Nexp[−yi(fm−1(xi)αG(xi))] 其中 w ^ m i e x p [ − y i f m − 1 ( x i ) ] . \hat{w}_{mi}exp[-y_i f_{m-1}(x_i)]. w^miexp[−yifm−1(xi)].为了求上式的最小化首先计算 G m ∗ ( x ) G_m^*(x) Gm∗(x),对于任意的 α 0 \alpha 0 α0,可以转化为下式 G m ∗ a r g m i n G ∑ i 1 N w ^ m i I ( y i ≠ G ( x i ) ) G_{m}^*argmin_{G}\sum_{i1}^{N}\hat{w}_{mi}I(y_i \neq G(x_i)) Gm∗argminGi1∑Nw^miI(yiG(xi)) 之后求 α m ∗ \alpha_m^* αm∗,将上述式子化简得到 ∑ i 1 N w ^ m i e x p [ − y i α G ( x i ) ] ∑ y i G m ( x i ) w ^ m i e − α ∑ y i ≠ G m ( x i ) w ^ m i e α ( e α − e − α ) ∑ i 1 N w ^ m i I ( y i ≠ G ( x i ) ) e − α ∑ i 1 N w ^ m i \sum_{i1}^{N}\hat{w}_{mi}exp[-y_i \alpha G(x_i)] \sum_{y_i G_m(x_i)}\hat{w}_{mi}e^{-\alpha}\sum_{y_i \neq G_m(x_i)}{\hat{w}_{mi}e^{\alpha}} (e^{\alpha} - e^{- \alpha})\sum_{i1}^{N}\hat{w}_{mi}I(y_i \neq G(x_i)) e^{- \alpha}\sum_{i1}^{N}\hat{w}_{mi} i1∑Nw^miexp[−yiαG(xi)]yiGm(xi)∑w^mie−αyiGm(xi)∑w^mieα(eα−e−α)i1∑Nw^miI(yiG(xi))e−αi1∑Nw^mi
将已经求得的 G m ∗ ( x ) G_m^*(x) Gm∗(x)带入上式面对 α \alpha α求导并等于0得到最优的 α \alpha α. a m ∗ 1 2 l o g 1 − e m e m a_m^*\frac{1}{2} log{\frac{1-e_m}{e_m}} am∗21logem1−em 其中 e m e_m em是分类误差率: e m ∑ i 1 N w ^ m i I ( y i ≠ G m ( x i ) ) ∑ i 1 N w ^ m i ∑ i 1 N w ^ m i I ( y i ≠ G m ( x i ) ) e_m\frac{\sum_{i1}^{N}\hat{w}_{mi}I(y_i \neq G_m(x_i))}{\sum_{i1}^{N}\hat{w}_{mi}}\sum_{i1}^{N}\hat{w}_{mi}I(y_i \neq G_m(x_i)) em∑i1Nw^mi∑i1Nw^miI(yiGm(xi))i1∑Nw^miI(yiGm(xi))
3.2 Adaboost能否做回归问题
Adaboost也能够应用到回归问题相应的算法如下: 输入: T ( x i , y 1 ) , ( x i , y 1 ) , . . . , ( x N , y N ) T{(x_i, y_1),(x_i, y_1),...,(x_N, y_N)} T(xi,y1),(xi,y1),...,(xN,yN), 弱学习器迭代次数 M M M。 输出强分类器 f ( x ) f(x) f(x). 初始化权重 D ( 1 ) w 11 , w 12 , . . . , w 1 N ; w 1 i 1 N ; i 1 , 2 , . . , N D(1){w_{11},w_{12},...,w_{1N}}; w_{1i}\frac{1}{N}; i1,2,..,N D(1)w11,w12,...,w1N;w1iN1;i1,2,..,N 根据 m 1 , 2 , . . . , M m1,2,...,M m1,2,...,M; 学习得到 G m ( x ) G_m(x) Gm(x) 计算训练集上最大误差 E m m a x ∣ y i − G m ( x i ) ∣ , i 1 , 2 , . . , N E_mmax|y_i-G_m(x_i)|, i1,2,..,N Emmax∣yi−Gm(xi)∣,i1,2,..,N 计算样本的相对平方误差: e m i ( y i − G m ( x i ) ) 2 E m 2 e_{mi}\frac{(y_i-G_m(x_i))^2}{E_m^2} emiEm2(yi−Gm(xi))2 计算回归误差率: e m ∑ i 1 N w m i e m i e_m\sum_{i1}^{N}w_{mi}e_{mi} emi1∑Nwmiemi 计算学习器系数: α m e m 1 − e m \alpha_m\frac{e_m}{1-e_m} αm1−emem 更新样本权重 w m 1 , i w m i Z m α m 1 − e m , i w_{m1,i}\frac{w_{mi}}{Z_m}{\alpha_{m}^{1-e^{m,i}}} wm1,iZmwmiαm1−em,i 其中 Z m Z_m Zm是规范化因子 Z m ∑ i 1 m w m i α m 1 − e m , i Z_m\sum_{i1}^{m}w_{mi}{\alpha_{m}^{1-e^{m,i}}} Zmi1∑mwmiαm1−em,i 得到强学习器 f ( x ) ∑ m 1 M G m ∗ ( x ) f(x)\sum_{m1}{M}G_{m}^*(x) f(x)m1∑MGm∗(x)
注: 不管是分类问题还是回归问题根据误差改变权重就是Adaboost的本质可以基于这个构建相应的强学习器。
3.3 boosting和bagging之间的区别,从偏差-方差的角度解释Adaboost
集成学习提高学习精度降低模型误差模型的误差来自于方差和偏差其中bagging方式是降低模型方差一般选择多个相差较大的模型进行bagging。boosting是主要是通过降低模型的偏差来降低模型的误差。其中Adaboost每一轮通过误差来改变数据的分布使偏差减小。
3.4 为什么Adaboost方式能够提高整体模型的学习精度
根据前向分布加法模型Adaboost算法每一次都会降低整体的误差虽然单个模型误差会有波动但是整体的误差却在降低整体模型复杂度在提高。
3.5 Adaboost算法如何加入正则项? f m ( x ) f m − 1 ( x ) η α m G m ( x ) f_m(x)f_{m-1}(x)\eta \alpha_{m}G_{m}(x) fm(x)fm−1(x)ηαmGm(x)
3.6 Adaboost使用m个基学习器和加权平均使用m个学习器之间有什么不同
Adaboost的m个基学习器是有顺序关系的第k个基学习器根据前k-1个学习器得到的误差更新数据分布再进行学习每一次的数据分布都不同是使用同一个学习器在不同的数据分布上进行学习。加权平均的m个学习器是可以并行处理的在同一个数据分布上学习得到m个不同的学习器进行加权。
3.7 Adaboost和GBDT之间的区别
相同点
Adaboost和GBDT都是通过减低偏差提高模型精度都是前项分布加法模型的一种
不同点:
Adaboost每一个根据前m-1个模型的误差更新当前数据集的权重学习第m个学习器
GBDT是根据前m-1个的学习剩下的label的偏差修改当前数据的label进行学习第m个学习器一般使用梯度的负方向替代偏差进行计算。
3.8 Adaboost的迭代次数(基学习器的个数)如何控制
一般使用earlystopping进行控制迭代次数。
3.9 Adaboost算法中基学习器是否很重要应该怎么选择基学习器
sklearn中的adaboost接口给出的是使用决策树作为基分类器一般认为决策树表现良好其实可以根据数据的分布选择对应的分类器比如选择简单的逻辑回归或者对于回归问题选择线性回归。
3.10 MultiBoosting算法将Adaboost作为Bagging的基学习器Iterative Bagging将Bagging作为Adaboost的基学习器。比较两者的优缺点
两个模型都是降低方差和偏差。主要的不同的是顺序不同。MultiBosoting先减低模型的偏差再减低模型的方差这样的方式 MultiBoosting由于集合了BaggingWaggingAdaBoost可以有效的降低误差和方差特别是误差。但是训练成本和预测成本都会显著增加。 Iterative Bagging相比Bagging会降低误差但是方差上升。由于Bagging本身就是一种降低方差的算法所以Iterative Bagging相当于Bagging与单分类器的折中。
3.11 训练过程中每轮训练一直存在分类错误的问题整个Adaboost却能快速收敛为何
每轮训练结束后AdaBoost 会对样本的权重进行调整调整的结果是越到后面被错误分类的样本权重会越高。而后面的分类器为了达到较低的带权分类误差会把样本权重高的样本分类正确。这样造成的结果是虽然每个弱分类器可能都有分错的样本然而整个 AdaBoost 却能保证对每个样本进行正确分类从而实现快速收敛。
3.12 Adaboost 的优缺点
优点能够基于泛化性能相当弱的的学习器构建出很强的集成不容易发生过拟合。
缺点对异常样本比较敏感异常样本在迭代过程中会获得较高的权值影响最终学习器的性能表现。
