> 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\&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. 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.