网站建设一下需要多少费用,市场营销的概念,网站开发流程的三个部分,网站开发 足球球队信息提升方法之AdaBoost算法
作为非数学专业出身看到密密麻麻的数学公式刚开始真的是非常头疼。算法的物理逻辑的时候尚能理解#xff0c;但是涉及到具体的数学公式实现就开始懵逼了#xff1a;为什么要用这个公式#xff0c;这个公式是怎么推到的#xff0c;这个公式达到什么…提升方法之AdaBoost算法
作为非数学专业出身看到密密麻麻的数学公式刚开始真的是非常头疼。算法的物理逻辑的时候尚能理解但是涉及到具体的数学公式实现就开始懵逼了为什么要用这个公式这个公式是怎么推到的这个公式达到什么样的效果 这里结合自己的理解和画图用最直白的语言对每个公式作用进行解剖。 一、AdaBoost核心概念总结
提升方法是将弱学习算法提升为强学习算法的统计学习方法。在分类学习中提升方法通过反复修改训练数据的权值分布构建一系列基本分类器弱分类器并将这些基本分类器线性组合构成一个强分类器。代表性的提升方法是AdaBoost算法。重点是更新分类器的参数和训练集的权重见下2 AdaBoost模型是弱分类器的线性组合 f(x)∑Mm1αmGm(x)f(x)∑m1MαmGm(x)f(x)=∑^M_{m=1}\alpha _mG_m(x) MMM表示该提升树共有M" role="presentation" style="position: relative;">MMM个弱分类器组成Gm(x)Gm(x)G_m(x)表示第mmm个弱分类器
#x03B1;m" role="presentation" style="position: relative;">αmαm\alpha_m为第mmm个弱分类器的参数（反应该分类器的重要性）
AdaBoost算法的特点是通过迭代每次学习一个基本分类器。每次迭代中，核心思想是：提高那些被前一轮分类器错误分类数据的权值，而降低那些被正确分类的数据的权值。最后，AdaBoost将基本分类器的线性组合作为强分类器，其中给分类误差率小的基本分类器以大的权值，给分类误差率大的基本分类器以小的权值。
AdaBoost的训练误差分析表明，AdaBoost的每次迭代可以减少它在训练数据集上的分类误差率，这说明了它作为提升方法的有效性。（每次迭代误差递减且误差0#x2264;#x03F5;lt;0.5" role="presentation" style="position: relative;">0≤ϵ0.50≤ϵ0.50≤\epsilon AdaBoost算法的一个解释是该算法实际是前向分步算法的一个实现。在这个方法里模型是加法模型损失函数是指数损失算法是前向分步算法时的二分类学习方法。每一步中极小化损失函数。提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中最有效的方法之一。 AdaBoost是一种典型的提升树算法。 通过上面的总结我们看到AdaBoost是一个神奇的算法以精妙的方式通过更新数据集的权重以及各个弱分类器的参数组合成一个强分类器。那么它具体是怎么做到的呢
二、AdaBoost算法推导
输入训练数据集T(x1,y1),(x2,y2),...,(xN,yN)T(x1,y1),(x2,y2),...,(xN,yN)T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}其中xi∈X⊆Rn,yi∈Y{−1,1}xi∈X⊆Rn,yi∈Y{−1,1}x_i\in X ⊆R^n,y_i\in Y=\{-1,1\}弱学习算法Gm(x)Gm(x)G_m(x);
输出最终强化算法分类器G(x)G(x)G(x) 1初始化训练数据总和为1的权值分布初始权重为归一化后的均值既1N1N\frac 1N
D1(w11,...,w1i,...w1N),w1i1N,i1,2,...ND1(w11,...,w1i,...w1N),w1i1N,i1,2,...N
D_1=(w_{11},...,w_{1i},...w_{1N}),w_{1i}=\frac 1N, i=1,2,...N 2对m1,2,...Mm1,2,...Mm=1,2,...M弱分类器的个数a使用具有权值分布的DmDmD_m的训练数据集学习得到基本分类器(数据集XXX到{-1,1}的映射)
Gm(x):X#x2212;gt;{#x2212;1,1}" role="presentation" style="text-align: center; position: relative;">Gm(x):X−{−1,1}Gm(x):X−{−1,1}G_m(x):X->\{-1,1\} b计算Gm(x)Gm(x)Gm(x)在训练数据集上的分类误差率公式不够简洁明了其实总结下来非常好理解误差率ememe_m误分类样本的权值之和
em∑Ni1P(Gm(xi)≠yi)∑Ni1wmiI(Gm(xi)≠yi)em∑i1NP(Gm(xi)≠yi)∑i1NwmiI(Gm(xi)≠yi)
e_m=∑^N_{i=1}P(G_m(x_i)≠y_i)=∑^N_{i=1}w_{mi}I(G_m(x_i)≠y_i)我们来考虑下误差ememe_m的取值空间由于训练集权制之和为1因此误差0≤em≤10≤em≤10≤e_m≤1。但是这样还不够。因为我们在选择分裂阈值的时候会选择一个最优或局部最优的取值来分裂且当em0.5em0.5e_m=0.5是表明该分裂阈值对预测无贡献。因此最终得到的ememe_m的实际取值应小于em≤0.5em≤0.5e_m≤0.5。所以最终0≤em≤0.50≤em≤0.50≤e_m≤0.5且每次迭代误差ememe_m递减。这点对下面的参数理解很重要。
c计算Gm(x)Gm(x)G_m(x)的系数:(这里对数为自然对数)
αm12log1−ememαm12log1−emem
\alpha_m=\frac 12log\frac{1-e_m}{e_m} 那么问题来了为什么要用这个公式来计算更新每个基分类器的参数我们先画个图出来观察下这个函数。其中y轴为αmαm\alpha _mx轴为误差ememe_m 由2-b我们得到误差ememe_m的取值范围为0≤em0.50≤em0.50≤e_m结合该图可以可知0αm10αm10。另外可以发现通过该函数的转换弱分类器Gm(x)Gm(x)G_m(x)的误差的越小参数αmαm\alpha_m越大。即实现了给分类误差率小的基本分类器以大的权值给分类误差率大的基本分类器以小的权值
d更新训练数据集的权值分布该权值决定数据集的重要性并让误差的计算变得简单
Dm1(wm1,1,...,wm1,i,...wm1,N)Dm1(wm1,1,...,wm1,i,...wm1,N)
D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...w_{m+1,N}) wm1,iwmiZmexp(−αmyiGm(x−i)),i1,2,...Nwm1,iwmiZmexp(−αmyiGm(x−i)),i1,2,...N
w_{m+1,i}=\frac {w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x-i)),i=1,2,...N这里yi{−1,1}yi{−1,1}y_i=\{-1,1\} 为真实值Gm(xi){−1,1}Gm(xi){−1,1}G_m(x_i)=\{-1,1\}为预测值。当预测正确时yiGm(xi)yiGm(xi)y_iG_m(x_i)为1反之为-1。令δmiαmyiGm(xi)δmiαmyiGm(xi)\delta_{m_i}=\alpha_my_iG_m(x_i)θmiwmiZmθmiwmiZm\theta_{mi}=\frac {w_{mi}}{Z_m}(把它看作一个用于归一化权值的加权平均常数)。权重wm1,iwm1,iw_{m+1,i}的更新函数可以简化为wm1,iθmiexp(δmi),i1,2,...Nwm1,iθmiexp(δmi),i1,2,...Nw_{m+1,i}=\theta_{mi}exp(\delta _{mi}),i=1,2,...N画出ywm1,iexp(δmi)ywm1,iexp(δmi)y=w_{m+1,i}=exp(\delta_{mi})的图形来看一下由于0αm10αm10所以−1δm,i1−1δm,i1-1。且使得预测错误的数据集样本点更新后的权重变大预测正确的权值变小然后对所有权值进行归一化。这就是该函数实现的作用。(图中y1是当αα\alpha无限接近于0时的情况解释为当αmαm\alpha_m权值越大权重wm1,iwm1,iw_{m+1,i}更新改变的效果越明显。)这里ZmZmZ_m是规范化因子目的是使各数据集的权重进行归一化。理解为ZmZmZ_m更新后的各数据集权重之和。 Zm∑Ni1wmiexp(−αmyiGm(xi))Zm∑i1Nwmiexp(−αmyiGm(xi))Z_m=∑^N_{i=1}w_{mi}exp(-\alpha_my_iG_m(x_i))
3构建基本分类器的新型组合f(x)∑Mm1αmGm(x)f(x)∑m1MαmGm(x)f(x)=∑^M_{m=1}\alpha_mG_m(x)即
G(x)sign(f(x))sign(∑Mm1αmGm(x))G(x)sign(f(x))sign(∑m1MαmGm(x))
G(x)=sign(f(x))=sign(∑^M_{m=1}\alpha_mG_m(x)) * 函数sign()sign()sign()的意义是将正数判别为1负数判别为-1最终达到分类的目的。如图参数αmαm\alpha_m公式及权重wm1,iwm1,iw_{m+1,i} 其实是通过前向分步算法分别得到的αmαm\alpha_m和Gm(x)Gm(x)G_m(x)并使得fm(x)fm(x)f_m(x)再训练数据集TTT上的指数损失最小。具体的推导过程可参考《统计学习方法》–李航 第145～146页
三、AdaBoost算法实现步骤上面解释了AdaBoost算法的具体内容。这里写出它的分布实现步骤再对上文算法加深下理解：（1）假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器G1(x)" role="presentation" style="position: relative;">G1(x)G1(x)G_1(x)。 2AdaBoost反复学习基本分类器在每一轮m1,2,…,Mm1,2,…,Mm＝1,2,…,M顺次地执行下列操作 a使用当前分布DmDmD_m加权的训练数据集学习基本分类器Gm(x)Gm(x)G_m(x) b计算基本分类器Gm(x)Gm(x)G_m(x)再加权训练数据集上的分类误差率即误分类样本的权值之和。这里要注意wmiwmiw_{mi}表示第mmm轮中第i" role="presentation" style="position: relative;">iii个实例的权值且权值之和为1即∑Ni1wmi1∑i1Nwmi1∑^N_{i=1}w_{mi}=1 emP(Gm(xi)≠yi)∑Gm(xi)≠yiwmiemP(Gm(xi)≠yi)∑Gm(xi)≠yiwmie_m=P(G_m(x_i)≠y_i)=∑_{G_m(x_i)≠y_i}w_{mi} c计算基本分类器Gm(x)Gm(x)G_m (x)的系数αmαm\alpha_m。alphamalphamalpha_m表示Gm(x)Gm(x)G_m(x)在最终分类器中的重要性。由上面2-c可知当em≤1/2em≤1/2e_m≤1/2时alpham≥0alpham≥0alpha_m≥0并且αmαm\alpha_m随着ememe_m的减小而增大所以分类误差率越小的分类器在最终分类器中的作用越大。 d更新训练数据的权值分布为下一轮作准备。式2-d的权重更新函数可以写成 由此可知被基本分类器Gm(x)Gm(x)G_m (x)误分类样本的权值得以扩大而被正确分类样本的权值却得以缩小。两相比较误分类样本的权值被放大e(2αm)em1−eme(2αm)em1−eme^{(2\alpha_m)}=\frac{e_m}{1-e_m} 倍。因此误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据而不断改变训练数据权值的分布使得训练数据在基本分类器的学习中起不同的作用这是AdaBoost的一个特点。 3线性组合f(x)f(x)f(x)实现MMM个基本分类器的加权表决。系数#x03B1;m" role="presentation" style="position: relative;">αmαm\alpha_m 表示了基本分类器Gm(x)Gm(x)G_m (x)的重要性这里所有αmαm\alpha_m 之和并不为1。f(x)f(x)f(x)的符号决定实例x的类f(x)f(x)f(x)的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。 提升方法是即采用加法模型即基数函数的线性组合与前向分步算法以决策树为基函数的提升方法称为提升树boosting tree。对分类问题决策树是二叉分类树对回归问题决策树是二叉回归树。 喜欢本文的伙伴请关注我的博客http://ihoge.cn
