> For the complete documentation index, see [llms.txt](https://luweikxy.gitbook.io/machine-learning-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/adaboost.md). # AdaBoost ## AdaBoost * [返回顶层目录](/machine-learning-notes/summary.md) * [返回上层目录](/machine-learning-notes/ensemble-learning.md) * [AdaBoost概述](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#AdaBoost概述) * [AdaBoost算法](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#AdaBoost算法) * [AdaBoost算法的训练误差分析](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#AdaBoost算法的训练误差分析) * [AdaBoost算法的解释](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#AdaBoost算法的解释) * [前向分布算法](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#前向分布算法) * [前向分步算法与AdaBoost](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#前向分步算法与AdaBoost) * [AdaBoost算法的优点](https://luweikxy.gitbook.io/machine-learning-notes/ensemble-learning/boosting/pages/-LpO5vGnBc3IrlC7bDUd#AdaBoost算法的优点) ## AdaBoost概述 由于Boosting算法在解决实际问题时有一个重大的缺陷，即他们都要求事先知道弱分类算法分类正确率的下限，这在实际问题中很难做到，后来Freund和Schapire提出了AdaBoost 算法，该算法的效率与Freund方法的效率几乎一样，却**不需要知道弱分类算法分类正确率的下限**，可以非常容易地应用到实际问题中。 AdaBoost是Boosting算法家族中代表算法，AdaBoost主要是在整个训练集上维护一个分布权值向量Dm，用赋予权重的训练集通过弱分类算法产生分类假设Gm，即基分类器，然后计算他的错误率，用得到的错误率去更新分布权值向量Dm，对错误分类的样本分配更大的权值，正确分类的样本赋予更小的权值。每次更新后用相同的弱分类算法产生新的分类假设，这些分类假设的序列构成多分类器。对这些多分类器用加权的方法进行联合，最后得到决策结果。 这种方法不要求产生的单个分类器有高的识别率，即不要求寻找识别率很高的基分类算法，**只要产生的基分类器的识别率大于0.5，就可作为该多分类器序列中的一员**。 ## AdaBoost算法 算法流程如下图所示，AdaBoost重复调用弱学习算法（多轮调用产生多个分类器），首轮调用弱学习算法时，按均匀分布从样本集中选取子集作为该次训练集，以后每轮对前一轮训练失败的样本，赋予较大的分布权值（Dm为第m轮各个样本在样本集中参与训练的权值），使其在这一轮训练出现的权值增加，即在后面的训练学习中集中对比较难训练的样本进行学习，从而得到M个弱的基分类器，G1, G2, ... , Gm，其中Gm有相应的权值wm，并且其权值大小根据该分类器的效果而定。最后的分类器由生成的多个分类器加权联合产生。 ![AdaBoost-algorithm-flowchart](/files/-M2XrmmlV4gcRSCqqohj) 现在叙述AdaBoost算法， 输入：训练数据集 $$ T={ (x\_1,y\_1), (x\_2,y\_2), ... , (x\_N,y\_N) } $$ 其中，每个样本点由实例与标记组成。实例xi∈X=R^n，yi∈Y={+1,-1}；弱学习算法； 输出：最终分类器G(x) （1）初始化训练数据的权值分布 $$ D\_1=(w\_{11}, ... , w\_{1i}, , ... ,w\_{1N}),\quad w\_{1i}=\frac{1}{N},\quad i=1,2,...,N $$ （2）对m=1,2,...,M （a）使用具有权值分布Dm的训练数据学习，得到基本分类器 $$ G\_m(x):\ X\rightarrow { -1, +1 } $$ （b）计算Gm(x)在训练数据集上的分类误差率 $$ e\_m=P(G\_m(x\_i)\neq y\_i)=\sum\_{i=1}^Nw\_{mi}I(G\_m(x\_i)\neq y\_i) $$ （c）计算Gm(x)的系数 $$ \alpha\_m=\frac{1}{2}\text{log}\frac{1-e\_m}{e\_m} $$ 这里的对数是自然对数 （d）更新训练数据集的权值分布 $$ \begin{aligned} D\_{m+1}&=(w\_{m+1,1},...,w\_{m+1,i},...,w\_{m+1,N})\\ w\_{m+1,i}&=\frac{w\_{mi}}{Z\_m}\text{exp}(-\alpha\_my\_iG\_m(x\_i)),\quad i=1,2,...,N\\ \end{aligned} $$ 这里，Zm是规范化因子 $$ Z\_m=\sum\_{i=1}^Nw\_{mi}\text{exp}(-\alpha\_my\_iG\_m(x\_i)) $$ 它使D(m+1)成为一个概率分布。 （3）构建基本分类器的线性组合 $$ f(x)=\sum\_{m=1}^M\alpha\_mG\_m(x) $$ 得到最终分类器 $$ G(x)=\text{sign}(f(x))=\text{sign}\left( \sum\_{m=1}^M\alpha\_mG\_m(x) \right) $$ 对AdaBoost算法做如下**说明**： **步骤（1）**假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第一步能够在原始数据上学习基本分类器G1(x)。 **步骤（2）**AdaBoost反复学习基本分类器，在每一轮m=1,2,...,M顺次地执行下列操作： （a）使用当前分布Dm加权的训练数据集，学习基本分类器Gm(x)。 （b）计算基本分类器Gm(x)在加权训练数据集上的分类误差率： $$ e\_m=P(G\_m(x\_i)\neq y\_i)=\sum\_{G\_m(x\_i)\neq y\_i}w\_{mi} $$ 这里，w(mi)表示第m轮中第i个实例的权值， $$ \sum\_{i=1}^Nw\_{mi}=1 $$ 。这表明，Gm(x)在加权的训练数据集上的分类误差率是被Gm(x)误分类样本的权值之和，由此可以看出数据权值分布Dm与基本分类器Gm(x)的分类误差率的关系。 （c）计算基本分类器Gm(x)的系数αm。αm表示Gm(x)在最终分类器中的重要性。由前面的αm的计算公式（位于算法第c步）可知，当em≤1/2时，αm≥0，并且αm随着em的减小而增大，所以**分类误差率越小的基本分类器在最终分类器中的作用越大**。 （d）更新训练数据的权值分布为下一轮作准备，前面算法第d步的w(m+1,i)可以写成 $$ \begin{aligned} w\_{m+1,i}= \left{\begin{matrix} &\frac{w\_{mi}}{Z\_m}\text{exp}(-\alpha\_m), &\quad G\_m(x\_i)=y\_i\\ &\frac{w\_{mi}}{Z\_m}\text{exp}(\alpha\_m), &\quad G\_m(x\_i)\neq y\_i\\ \end{matrix}\right. \end{aligned} $$ 由此可知，被基本分类器Gm(x)误分类的样本的权值得以扩大，而被正确分类的样本的权值却得以缩小。两相比较，误分类的样本的权值被放大了 $$ e^{2\alpha\_m}=\frac{1-e\_m}{e\_m} $$ 倍。因此，误分类样本在下一轮学习中起到更大的作用。**不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点**。 **步骤（3）**线性组合f(x)实现M个基本分类器的加权表决。系数αm表示了基本分类器Gm(x)的重要性，这里，所有αm之和并不为1。f(x)的符号决定实例x的类，f(x)的绝对值表示分类的确信度。**利用基本分类器的线性组合构建最终分类器是AdaBoost的另一个特点**。 下图是对AdaBoost分类过程中样本权值的变化及最终的f(x)的**形象表示**： ![Boosting-algorithm](/files/-M2Xrmmq3enyvCj7edQu) ## AdaBoost算法的训练误差分析 AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据及上分类误差率。关于这个问题有下面的定理： **AdaBoost的训练误差界** AdaBoost算法最终分类器的训练误差界为 $$ \frac{1}{N}\sum\_{i=1}^NI(G(x\_i)\neq y\_i)\leqslant\frac{1}{N}\sum\_i\text{exp}(-y\_if(x\_i))=\prod\_mZ\_m $$ 这里，G(x)，f(x)和Zm分别由上面已经给出。 **证明**：当G(x)≠yi时，yif(xi)<0，因而exp(-yif(xi))≥1。由此直接推导出前半部分。 后半部分的推导要用到Zm的定义式及其上式的变形： $$ w\_{mi}\text{exp}(-\alpha\_my\_iG\_m(x\_i))=Z\_mw\_{m+1,i} $$ 现推导如下： $$ \begin{aligned} &\frac{1}{N}\sum\_i\text{exp}(-y\_if(x\_i))\\ \=&\frac{1}{N}\sum\_i\text{exp}\left(-\sum\_{m=1}^M\alpha\_my\_iG\_m(x\_i)\right)\\ \=&\sum\_iw\_{1i}\prod\_{m=1}^M\text{exp}\left(-\alpha\_my\_iG\_m(x\_i)\right)\\ \=\&Z\_1\sum\_iw\_{2i}\prod\_{m=2}^M\text{exp}\left(-\alpha\_my\_iG\_m(x\_i)\right)\\ \=\&Z\_1Z\_2\sum\_iw\_{3i}\prod\_{m=3}^M\text{exp}\left(-\alpha\_my\_iG\_m(x\_i)\right)\\ \=&...\\ \=\&Z\_1Z\_2...Z\_{M-1}\sum\_iw\_{Mi}\text{exp}\left(-\alpha\_My\_iG\_M(x\_i)\right)\\ \=&\prod\_{m=1}^MZ\_m\\ \end{aligned} $$ 这一定理说明，可以在每一轮选取适当的Gm使得Zm最小，从而使训练误差下降最快。 **这里就有疑惑了，分类器Gm的选取原则不是应该是分类误差率最小吗？这里成了让Zm最小了？** **即分类器Gm的选取原则到底是：** * **分类误差率最小？** * **Zm最小？** **哪一个才对啊？其实，这两个本质是一样滴，不冲突。为啥？来看下面的解释：** **由下面的定理中对Zm的计算可知，** $$ Z\_m=\sqrt{1-4\gamma\_m^2} $$ **要使Zm最小，其实就是使γm最大。而γm又是什么呢？** $$ \gamma\_m=\frac{1}{2}-e\_m $$ **所以，要使γm最大，就要使em最小。而em是什么呢？大哥，em就是分类器Gm的分类误差率呀。所以，让Zm最小，就是要让em（分类误差率）最小，这两个是等价的，不冲突的，一致的。** 对二分类问题，有如下结果： **定理：二分类问题AdaBoost的训练误差界** $$ \prod\_{m=1}^MZ\_m=\prod\_{m=1}^M\[2\sqrt{e\_m(1-e\_m)}]=\prod\_{m=1}^M\sqrt{(1-4\gamma\_m^2)}\leqslant\text{exp}\left( -2\sum\_{m=1}^M\gamma\_m^2 \right) $$ 这里， $$ \gamma\_m=\frac{1}{2}-e\_m $$ 证明：由Zm的定义及em的定义得 $$ \begin{aligned} Z\_m&=\sum\_{i=1}^Nw\_{mi}\text{exp}\left(-\alpha\_my\_iG\_m(x\_i)\right)\\ &=\sum\_{y\_i=G\_m(x\_i)}w\_{mi}e^{-\alpha\_m}+\sum\_{y\_i\neq G\_m(x\_i)}w\_{mi}e^{\alpha\_m}\\ &=(1-e\_m)e^{-\alpha\_m}+e\_me^{\alpha\_m}\\ &=2\sqrt{e\_m(1-e\_m)}\\ &=\sqrt{1-4\gamma^2\_m}\\ \end{aligned} $$ 至于不等式 $$ \prod\_{m=1}^M\sqrt{(1-4\gamma\_m^2)}\leqslant\text{exp}\left( -2\sum\_{m=1}^M\gamma\_m^2 \right) $$ 则可先由exp(x)和sqrt(1-x)在点x=0的泰勒展开式推出不等式 $$ \sqrt{(1-4\gamma\_m^2)}\leqslant\text{exp}(-2\gamma\_m^2) $$ 进而得到该不等式。 **推论**：如果存在γ>0，对所有m有γm≥γ，则 $$ \frac{1}{N}\sum\_{i=1}^NI(G(x\_i)\neq y\_i)\leqslant\text{exp}(-2M\gamma^2) $$ 这表明在此条件下AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。 注意，AdaBoost算法不需要知道下界γ。这正是Freund与Schapire设计AdaBoost时所考虑到的。与一些早期的提升方法不同，Adaboost具有适应性，即它能适应若分类器各自的训练误差率。这也是它名称（自适应提升）的由来，Ada是Adaptive的简写。 ## AdaBoost算法的解释 AdaBoost算法还有另一个解释，即可以认为AdaBosst算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二分类学习方法。 ### 前向分布算法 考虑加法模型 $$ f(x)=\sum\_{m=1}^M\beta\_mb(x;\gamma\_m) $$ 其中，b(x;γm)为基函数，γm为基函数的参数，βm为基函数的系数。 显然，上面构建的基本分类器的线性组合 $$ f(x)=\sum\_{m=1}^M\alpha\_mG\_m(x) $$ 是一个加法模型。 在给定训练数据及损失函数L(y,f(x))的条件下，学习加法模型f(x)成为经验风险极小化即损失函数极小化问题： $$ \mathop{\text{min}}*{\beta\_m,\gamma\_m}\sum*{i=1}^NL\left( y\_i, \sum\_{m=1}^M\beta\_mb(x\_i;\gamma\_m) \right) $$ 通常这是一个复杂的优化问题，前向分布算法求解这一优化问题的想法是：廻学习的是加法模型，如果能够从前到后，每一步只需吸一个基函数及其系数，逐步逼近优化目标函数式，那么就可以建华优化的复杂度。具体地，每步只需优化如下损失函数： $$ \mathop{\text{min}}*{\beta,\gamma}\sum*{i=1}^NL(y\_i,\beta b(x\_i;\gamma)) $$ 给定训练数据集T={ (x1,y1), (x2,y2), ... , (xN,yN) }，xi∈X=R^n，yi∈Y={+1,-1}。损失函数L(y,f(x))和基函数的结合{ b(x;γ) }，学习加法模型f(x)的前项分布算法如下： **前向分步算法**： 输入：训练数据集集T={ (x1,y1), (x2,y2), ... , (xN,yN) }；损失函数L(y,f(x))；基函数集{ b(x;γ) }； 输出：加法模型f(x)。 （1）初始化f0(x)=0 （2）对m=1,2,...,M （a）极小化损失函数 $$ (\beta\_m,\gamma\_m)=\text{arg }\mathop{\text{min}}*{\beta,\gamma}\sum*{i=1}^NL(y\_i,f\_{m-1}(x\_i)+\beta b(x\_i; \gamma)) $$ 得到参数βm，γm （b）更新 $$ f\_m(x)=f\_{m-1}(x)+\beta\_mb(x; \gamma\_m) $$ （3）得到加法模型 $$ f(x)=f\_M(x)=\sum\_{m=1}^M\beta\_mb(x;\gamma\_m) $$ 这样，前向分步算法将同时求解m=1到M所有参数βm，γm的优化问题简化为主次求解各个βm，γm的优化问题。 ### 前向分步算法与AdaBoost 由前项分布算法可以推导出AdaBoost，用定理叙述这一关系。 **定理**：AdaBoost算法是前向分布加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。 证明：前向分布算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器。 $$ f(x)=\sum\_{m=1}^M\alpha\_mG\_m(x) $$ 由基本分类器Gm(x)及其系数αm组成，m=1,2,...,M。前向分布算法逐一学习基函数，这一过程与AdaBoos算法逐一学习基本分类器的过程一致。下面证明**前向分步算法的损失函数是指数损失函数**。 $$ L(y,f(x))=exp\[-y\ f(x)] $$ 时，其学习的具体操作等价于AdaBoost算法学习的具体操作。 假设经过m-1轮迭代，前向分布算法已经得到 $$ \begin{aligned} f\_{m-1}(x)&=f\_{m-2}(x)+\alpha\_{m-1}G\_{m-1}(x)\\ &=\alpha\_1G\_1(x)+...+\alpha\_{m-1}G\_{m-1}(x) \end{aligned} $$ 在第m轮迭代中，得到αm，Gm(x)和fm(x)。 $$ f\_m(x)=f\_{m-1}(x)+\alpha\_mG\_m(x) $$ 目标是使前向分布算法得到的αm和Gm(x)使fm(x)在训练数据集T上的指数损失最小，即 $$ (\alpha\_m,G\_m(x))=\text{arg }\mathop{\text{min}}*{\alpha,G}\sum*{i=1}^N\text{exp}\[-y\_i(f\_{m-1}(x\_i)+\alpha G(x\_i))] $$ 上式可以表示为 $$ (\alpha\_m,G\_m(x))=\text{arg }\mathop{\text{min}}*{\alpha,G}\sum*{i=1}^N\overline{w}\_{mi}\text{exp}\[-y\_i\alpha G(x\_i)] $$ 其中， $$ \overline{w}*{mi}=\text{exp}\[-y\_if*{m-1}(x\_i)] $$ 。因为 $$ \overline{w}\_{mi} $$ 既不依赖α也不依赖于G，所以与最小化无关。但其依赖于$f\_{m-1}(x)$，随着每一轮迭代而发生改变。 现证使上上式达到最小的α\*m和G\*m(x)就是AdaBoost算法所得到的αm和Gm(x)。求解上上式可分两步： 首先，求G\*m(x)。对任意α>0，使上上式最小的G(x)由下式得到： $$ G\_m^\*(x)=\text{arg }\mathop{\text{min}}*{G}\sum*{i=1}^N\overline{w}\_{mi}I(y\_i\neq G(x\_i)) $$ **注：这里为什么能和上上式是等效的？有待研究。** **有个启发（数学上不严谨，有待证明）就是，注意Zm的定义** $$ Z\_m=\sum\_{i=1}^Nw\_{mi}\text{exp}(-\alpha\_my\_iG\_m(x\_i)) $$ **和** $$ (\alpha\_m,G\_m(x))=\text{arg }\mathop{\text{min}}*{\alpha,G}\sum*{i=1}^N\overline{w}\_{mi}\text{exp}\[-y\_i\alpha G(x\_i)] $$ **是很类似的。也就是说** $$ \begin{aligned} &(\alpha\_m,G\_m(x))\\ \=&\text{arg }\mathop{\text{min}}*{\alpha,G}\sum*{i=1}^N\overline{w}*{mi}\text{exp}\[-y\_i\alpha G(x\_i)]\\ \approx &\text{arg }\mathop{\text{min}}*{\alpha,G}\ Z\_m\\ \end{aligned} $$ **而前面已经说过了，Zm就是Gm的分类误差率。所以当然能由分类误差率得到啊，因为这两者本来就是等价的嘛。** 此分类器G\*m(x)即为AdaBoost算法的基本分类器Gm(x)，因为它是使第m轮甲醛训练数据分类误差率最小的基本分类器。 之后，求α\*m，上上上式中， $$ \begin{aligned} &\sum\_{i=1}^N\overline{w}*{mi}\text{exp}\[-y\_i\alpha G(x\_i)]\\ \=&\sum*{y\_i=G\_m(x\_i)}\overline{w}*{mi}\text{exp}(-\alpha)+\sum*{y\_i\neq G\_m(x\_i)}\overline{w}*{mi}\text{exp}(\alpha)\\ \=&(e^{\alpha}-e^{-\alpha})\sum*{i=1}^N\overline{w}*{mi}I(y\_i\neq G(x\_i))+e^{-\alpha}\sum*{i=1}^N\overline{w}\_{mi} \end{aligned} $$ 将已求得的G\*m(x)带入上式，对α求导并使倒数为0，即得到使上上式最小的α。 $$ \alpha\_m^\*=\frac{1}{2}\text{log}\frac{1-e\_m}{e\_m} $$ 其中，em是分类误差率： $$ e\_m=\frac {\sum\_{i=1}^N\overline{N}*{mi}I(y\_i\neq G\_m(x\_i))} {\sum*{i=1}^N\overline{N}\_{mi}} ================================ \sum\_{i=1}^Nw\_{mi}I(y\_i\neq G\_m(x\_i)) $$ 这里的α\*m与AdaBoost算法第2（c）步的αm完全一致。 最后来看每一轮样本权值的更新。由 $$ f\_m(x)=f\_{m-1}(x)+\alpha\_mG\_m(x) $$ 以及 $$ \overline{w}*{mi}=\text{exp}\[-y\_if*{m-1}(x\_i)] $$ ，可得 $$ \overline{w}*{m+1,i}=\overline{w}*{m,i}\text{exp}\[-y\_i\alpha\_mG\_m(x)] $$ 这与AdaBoost算法第2（d）步的样本权重的更新，只相差规范化因子，因而等价。 ## AdaBoost算法的优点 * AdaBoost是一种有很高精度的分类器 * AdaBoost可以支持各种方式构建的弱分类器，如最简单的x\