Adaboost算法的原理推导及解释

前置知识：Boosting概述

Boosting方法的基本思想

该方法使用迭代方式完成对各个弱学习器的训练构造， 每次迭代对训练样本集的选择都与前面各轮的学习结果有关。

使用前面各轮学习结果更新当前各训练样本的权重，对前面被错误预测的赋予较大的权重，实现对当前训练样本集合数据分布的优化。

Boosting方法的的学习方法

Boosting 集成学习通常使用两种方式调整训练样本集的数据分布。

• 仅调整样本数据的权重，而不改变当前训练样本集合。

• 改变当前训练样本集合，将被前面弱学习器错误预测的样本复制到关于当前弱学习器的训练样本集合中重新进行训练。

在实际的模型训练中，常使用第一种方式调整训练样本的数据分布。第二种方式是复制被前面弱学习器错误预测样本到样本训练集当中重新进行训练。

而调整样本权重的基本思想是提高当前训练样本集合中被错误预测样本的权重，降低已被正确预测样本的权重，使得后续对的弱学习器的训练构造更加重视那些被错误预测的样本。

关于权重的理解（非常重要！！！）：

• 一方面，指的是分类错误率方向的影响，指的是计算学习器L对样本集D的分类错误率时候的样本比重，即假如样本d_j分类错误，本来该样本权重系数应该是1/n（n为样本集D的样本总数目），然后经过调整，d_j的权重系数修改为1/2；相应的d_i分类正确的样本权重修改为1/2。

• 另一方面，指的是模型参数训练优化方向的影响，指的是模型不断优化的梯度或者决策方向，朝着哪一个或者哪些方向去迭代优化，例如：${\mathbf{w}}_{\mathbf{i}+1}={\mathbf{w}}_{\mathbf{i}}+{\sum }_{\mathbf{k}=1}^{\mathbf{n}}{\mathbf{w}}_{\mathbf{i}\mathbf{k}}\phi \left({\mathbf{w}}_{\mathbf{i}\mathbf{k}}{\mathbf{X}}_{\mathbf{k}}\right)$，当模型参数的更新公式中涉及到输入样本时，权重将会影响模型参数的优化方向。

方法的流程如下：

• 对于n个样本的训练集，初始样本权重为1/n，则对所有被预测错误样本集Q，其整体权重等于ε。
• 若规定权重更新后Q的整体权重为1/2,则需将其初始权重ε乘以1/(2ε), 即ε*1/(2ε)=1/2。
• 为了保证更新后的概率之和为1,则剩余样本应乘以1/[2(1-ε)]。

例题：现有均匀分配权重样本集训练得到的分类器𝐶1，其分类结果如表所示。试更新该训练样本集的权重并求出分类器𝐶1基于更新权重后样本集的分类错误率。

依题意可知，共有60个分类正确样本、共40个分类错误样本，分类错误率为𝜀 =0.4。错误分类样本权重更新因子𝛼 = 1/(2𝜀)= 1.25，正确分类样本权重更新因子𝛽 = 1/[2(1 − 𝜀)]=5/6，则权重更新后分类结果 表所示，此时错误率𝜀′ = 0.5，结果如下表。

核心部分：Adaboost算法的原理推导和解释

Adaboost算法的基本思想

AdaBoost是一种具有自适应性质的Boosting集成学习算法，自适应性主要表现在自动提升被错误预测样本的权重，自动减少被正确预测样本的权重，使得弱学习器训练过程能够根据模型预测性能自动进行调整。

Adaboost算法的算法流程

现以二分类任务为例介绍该算法的具体过程：

• 对于训练样本集𝐷 = 𝑋₁, 𝑦₁ , 𝑋₂, 𝑦₂ , ⋯ , (𝑋_𝑛, 𝑦_𝑛)，其中𝑦_𝑖𝜖−1, +1，由 AdaBoost 集成学习算法构造集成模型的基本步骤如下：

  （1）令𝑖=1并设定弱学习器的数目𝑚。使用均匀分布初始化训练样本集的权重分布，令𝑛维向量𝑤^𝑖表示第𝑖次需更新的样本权重，则有：𝑤¹= (𝑤₁₁, 𝑤₁₂, ⋯ , 𝑤_1𝑛)^𝑇 =(1/n, 1/n, …, 1/n)^T。 （w₁₂代表第1次迭代，第2个样本对应的样本权重，一个样本的权重主要影响的是模型不断优化的梯度或者决策方向，朝着哪一个或者哪些方向去迭代优化，例如：${\mathbf{w}}_{\mathbf{i}+1}={\mathbf{w}}_{\mathbf{i}}+{\sum }_{\mathbf{k}=1}^{\mathbf{n}}{\mathbf{w}}_{\mathbf{i}\mathbf{k}}\phi \left({\mathbf{w}}_{\mathbf{i}\mathbf{k}}{\mathbf{X}}_{\mathbf{k}}\right)$，当模型参数的更新公式中涉及到输入样本时，权重将会影响模型参数的优化方向）

  （2）使用权重分布为𝑤^𝑖的训练样本集𝐷_𝑖学习得到第𝑖个弱学习器𝑓_i 。

  （3）计算𝑓_𝑖在训练样本集𝐷_𝑖上的分类错误率𝑒_𝑖：
  $${\mathbf{e}}_{\mathbf{i}}=\sum _{\mathbf{k}=1}^{\mathbf{n}}{\mathbf{w}}_{\mathbf{i}\mathbf{k}}\mathbf{I}\left({\mathbf{f}}_{\mathbf{i}}\left({\mathbf{X}}_{\mathbf{k}}\right)\ne {\mathbf{y}}_{\mathbf{k}}\right)$$
  （4）确定弱学习器𝑓_𝑖的组合权重𝛼_𝑖。由于弱学习器𝑓_𝑖的权重取值应与其分类性能相关，对于分类错误率𝑒_𝑖越小的𝑓_𝑖，则其权重𝛼_𝑖应该越大，故有${\alpha }_{\mathbf{i}}=\frac{1}{2}\ln \frac{1-{\mathbf{e}}_{\mathbf{i}}}{{\mathbf{e}}_{\mathbf{i}}}$。

  （5）依据弱学习器𝑓_𝑖对训练样本集𝐷_𝑖的分类错误率𝑒_𝑖更新样本权重，更新公式为${\mathbf{w}}_{\mathbf{i}+1,\mathbf{j}}=\frac{{\mathbf{w}}_{\mathbf{i}\mathbf{j}}{\mathbf{e}}^{\left(-{\alpha }_{\mathbf{i}}{\mathbf{y}}_{\mathbf{j}}{\mathbf{f}}_{\mathbf{i}}\left({\mathbf{X}}_{\mathbf{j}}\right)\right)}}{{\mathbf{z}}_{\mathbf{i}}}$，其中为${\mathbf{z}}_{\mathbf{i}}={\sum }_{\mathbf{j}=1}^{\mathbf{n}}{\mathbf{w}}_{\mathbf{i}\mathbf{j}}{\mathbf{e}}^{\left(-{\alpha }_{\mathbf{i}}{\mathbf{y}}_{\mathbf{j}}{\mathbf{f}}_{\mathbf{i}}\left({\mathbf{X}}_{\mathbf{j}}\right)\right)}$归一化因子，保证更新后权重向量是概率之和等于1。（其中y_j∈1,-1，而f_i(X_j)∈1，-1，如果第i次迭代，分类正确，则相对之前的权重降低了$\sqrt{\frac{{\mathbf{e}}_{\mathbf{i}}}{1-{\mathbf{e}}_{\mathbf{i}}}}$；否则，权重则提升了$\sqrt{\frac{1}{{\mathbf{e}}_{\mathbf{i}}}-1}$。）

  （6）若𝑖 < 𝑚，则令𝑖 = 𝑖 + 1并返回步骤（2），否则执行步骤（7）。

  （7）对于𝑚个弱分类器𝑓₁, 𝑓₂, ⋯ , 𝑓_𝑚，分别将每个𝑓_𝑖按权重𝛼_𝑖进行组合： G = s i g n ( ∑ i = 1 m α i f i ( X ) ) \\mathbfG=\\mathbfsign\\left( \\sum_\\mathbfi=1^\\mathbfm\\mathbf\\alpha _\\mathbfi\\mathbff_\\mathbfi\\left( \\mathbfX \\right) \\right) G=sign(∑查看详情

  em算法的原理推导及解释(代码片段)

  文章目录EM算法的原理推导及解释前置知识：极大似然估计(MaximumLikelihood）核心部分：期望最大化算法(ExpectationMaximum)实例：EM求解“三硬币”模型的完整推导及解释EM算法的原理推导及解释本质上，EM算法针对... 查看详情

  adaboost算法的原理与推导——转载及修改完善

  《Adaboost算法的原理与推导》一文为他人所写，原文链接： http://blog.csdn.net/v_july_v/article/details/40718799另外此文大部分是摘录李航的《统计学笔记》一书，原书下载链接：http://vdisk.weibo.com/s/z4UjMcqGpoNTw?from=page_100505_profile&wvr=6... 查看详情

  机器学习集成学习（boosting）——adaboost提升算法（理论+图解+公式推导）

  ...待着您的光临~文章目录​​一、集成学习​​​​二、AdaBoost算法​​​​1.Boosting提升方法​​​​2.AdaBoost算法思想​​​​3.AdaBoost原理解释​​​​4.构造损失函数，求解参数​​​​5.前向分步算法​​2021人工智能领域新... 查看详情

  模糊c–均值聚类算法的原理解释及推导

  文章目录模糊𝑐–均值聚类算法的原理解释及推导前置知识：𝑘–均值聚类的缺陷核心部分：模糊𝑐–均值聚类基本思想：原理推导：算法流程及实例分析：模糊𝑐–均值聚类算法的原理解... 查看详情

  模糊c–均值聚类算法的原理解释及推导

  文章目录模糊𝑐–均值聚类算法的原理解释及推导前置知识：𝑘–均值聚类的缺陷核心部分：模糊𝑐–均值聚类基本思想：原理推导：算法流程及实例分析：模糊𝑐–均值聚类算法的原理解... 查看详情

  adaboost算法的原理与推导

   0引言  一直想写Adaboost来着，但迟迟未能动笔。其算法思想虽然简单“听取多人意见，最后综合决策”，但一般书上对其算法的流程描述实在是过于晦涩。昨日11月1日下午，邹博在我组织的机器学习班第8次课上... 查看详情

  机器学习笔记_prml_adaboost算法的原理与推导

  转自：http://blog.csdn.net/v_july_v/article/details/40718799 Adaboost算法的原理与推导 1Adaboost的原理1.1Adaboost是什么     AdaBoost，是英文"AdaptiveBoosting"（自适应增强）的缩写，由YoavFreund和Robert 查看详情

  李航统计学习方法--8.提升方法(详细推导)

  目录​​8.1提升方法AdaBoost算法​​​​8.1.1提升方法的基本思路​​​​8.1.2AdaBoost算法​​​​8.2AdaBoost算法的训练误差分析​​​​8.3AdaBoost算法的解释​​​​8.3.1前向分步算法​​​​8.3.2前向分步算法与AdaBoost​​​​8.4... 查看详情

  支持向量机(svm)的原理推导及解释

  文章目录支持向量机(SVM)的原理推导及解释1.线性可分支持向量机(linearsupportvectormachineinlinearlyseparablecase)2.线性支持向量机(linearsupportvectormachine)3.非线性支持向量机(non-linearsupportvectormachine)支持向量机(SVM)的原理推导及解释支持向... 查看详情

  bp算法的原理解释和推导

  BP算法的原理解释和推导已知的神经网络结构：且已知的条件：a(j)=f(z(j))\\mathbfa^\\left(\\mathbfj\\right)=\\mathbff\\left(\\mathbfz^\\left(\\mathbfj\\right)\\right)a(j)=f(z(j))z(j)=W(j)a 查看详情

  bp算法的原理解释和推导

  BP算法的原理解释和推导已知的神经网络结构：且已知的条件：a(j)=f(z(j))\\mathbfa^\\left(\\mathbfj\\right)=\\mathbff\\left(\\mathbfz^\\left(\\mathbfj\\right)\\right)a(j)=f(z(j))z(j)=W(j)a(j−1)+b(j) 查看详情

  adaboost算法原理分析和实例+代码（简明易懂）

  Adaboost算法原理分析和实例+代码（简明易懂）【尊重原创，转载请注明出处】http://blog.csdn.net/guyuealian/article/details/70995333  本人最初了解AdaBoost算法着实是花了几天时间，才明白他的基本原理。也许是自己能力有限吧，很... 查看详情

  独立成分分析ica原理及公式推导示例

  ...alysis）前言独立成分分析ICA是一个在多领域被应用的基础算法。ICA是一个不定问题，没有确定解，所以存在各种不同先验假定下的求解算法。相比其他技术，ICA的开源代码不是很多，且存在黑魔法–有些步骤并没有在论文里... 查看详情

  机器学习——提升方法adaboost算法，推导过程

  0提升的基本方法　　对于分类的问题，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类的分类规则（强分类器）容易的多。提升的方法就是从弱分类器算法出发，反复学习，得到一系列弱分类器（... 查看详情

  图像算法研究---adaboost算法具体解释

  本篇文章先介绍了提升放法和AdaBoost算法。已经了解的可以直接跳过。后面给出了AdaBoost算法的两个样例。附有详细计算过程。1、提升方法（来源于统计学习方法）  提升方法是一种经常使用的统计学习方法，应用十分广... 查看详情

  特别翔实的adaboost分类算法讲解转的(代码片段)

  .../9332370.html作为(曾)被认为两大最好的监督分类算法之一的adaboost元算法(另一个为前几节介绍过的SVM算法)，该算法以其简单的思想解决复杂的分类问题，可谓是一种简单而强大的算法，本节主要简单介绍adaboost元算法，并以实例看... 查看详情

  机器学习实战第7章——利用adaboost元算法提高分类性能(代码片段)

  将不同的分类器组合起来，这种组合结果被称为集成方法或元算法（meta-algorithm）。使用集成方法时会有多种形式：（1）可以是不同算法的集成（2）可以是同一种算法在不同设置下的集成（3）数据集不同部分分配给不同分类器... 查看详情