??图2-1展示了提示算法的具体流程，其与Bagging算法的区别在于：其一，Bagging算法的每个估计器相对独立且权重都相同，而Boosting算法的每个估计器都依赖于上一个估计器同时权重也不同。其二，一般情况下Bagging算法可以减小方差、而Boosting算法则是减小偏差。??Boosting算法中比较有代表性的算法就是自适应增强算法（AdaptiveBoostingAlgorithm/AdaBoostAlgorithm）
??AdaBoost算法是由YoavFreund和RobertE.Schapire在1995年提出的，同时还提出了AdaBoost.M1、AdaBoost.M2算法用于多分类问题，AdaBoost.R算法用于回归问题。后面陆续又有人提出了上述算法的变体AdaBoost-SAMME、AdaBoost-SAMME.R、AdaBoost.R2算法。??AdaBoost算法的基本步骤与Boosting算法一样，是Boosting算法的具体实现，其定义了每次循环如何更新样本权重以及最后如何将每个估计器结合起来。??由于笔者能力所限，本文只会介绍基础的AdaBoost算法和现在scikit-learn中所实现的AdaBoost-SAMME、AdaBoost-SAMME.R、AdaBoost.R2算法，其他的算法暂无法一一介绍，感兴趣的读者可以参考文末对应算法的论文原文。
??假设训练集T={X_i,y_i}，i=1，...，N，y_i可取-1，+1，h(x)为估计器，估计器的数量为K。
初始化样本权重向量ω_1
$$\begin{aligned}\omega_{1,i}&=\frac{1}{N}\quadi=1,...,N\end{aligned}$$
遍历估计器的数量K次：??在样本权重ω_k下训练估计器h(x)??计算第k次的误差率e_k
$$\begin{aligned}e_k&=\sum_{i=1}^{N}\omega_{k,i}I(y_i\neh_k(X_i))\end{aligned}$$
??如果误差率e_k大于0.5????中断循环??计算第k次的估计器权重α_k
$$\begin{aligned}\alpha_k&=\frac{1}{2}\ln\frac{1-e_k}{e_k}\\\end{aligned}$$
??计算第k+1次的权重向量ω_{k+1}
$$\begin{aligned}\omega_{k+1,i}&=\frac{\omega_{k,i}e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\omega_{k,j}e^{-y_j\alpha_kh_k(X_j)}\right)}\end{aligned}$$
结束循环
??最后的结合策略，采用加权后的结果取sign函数，得到最终的强估计器：
$$\begin{aligned}H(x)&=\operatorname{sign}\left(\sum_{i=1}^{K}\alpha_ih_i(x)\right)\end{aligned}$$
??假设训练集T={X_i,y_i}，i=1，...，N，y的取值有M种可能，h(x)为估计器，估计器的数量为K。
??计算第k次的估计器权重α_k
$$\begin{aligned}\alpha_k&=\ln\frac{1-e_k}{e_k}+\ln(M-1)\\\end{aligned}$$
$$\begin{aligned}\bar{\omega_{k+1,i}}&=\omega_{k,i}e^{\alpha_kI(y_i\neh_k(X_i))}\end{aligned}$$
??对权重向量ω_{k+1}进行归一化
$$\begin{aligned}\omega_{k+1,i}&=\frac{\bar{\omega_{k+1,i}}}{\sum_{j=1}^N\bar{\omega_{k+1,i}}}\end{aligned}$$
??最后的结合策略，采用正确分类的结果加权后取值最大的分类，得到最终的强估计器：
$$\begin{aligned}H(x)&=\underset{m}{\operatorname{argmax}}\left(\sum_{i=1}^{K}\alpha_iI(h_i(x)=m)\right)\end{aligned}$$
遍历估计器的数量K次：??在样本权重ω_k下计算加权类概率估计向量P_k
$$\begin{aligned}p_k^m(x)=P(y=m\midx)\end{aligned}$$
$$\hat{y}=\left\{\begin{array}{c}1&y=m\\-\frac{1}{M-1}&y\nem\end{array}\right.\quadm=1,\dots,M$$
$$\begin{aligned}\bar{\omega_{k+1,i}}&=\omega_{k,i}e^{-\frac{M-1}{M}\hat{y_i}^T\lnp_k(x)}\end{aligned}$$
??最后的结合策略，采用概率估计计算结果取值最大的分类，得到最终的强估计器：
$$\begin{aligned}h_k(x)&=(M-1)\left(\lnp_k^m(x)-\frac{1}{M}\sum_{i=1}^{M}\lnp_k^i(x)\right)\\H(x)&=\underset{m}{\operatorname{argmax}}\left(\sum_{i=1}^{K}h_i(x)\right)\end{aligned}$$
??假设训练集T={X_i,y_i}，i=1，...，N，h(x)为估计器，估计器的数量为K
遍历估计器的数量K次：??在样本权重ω_k下训练估计器h(x)??计算最大误差E_k
$$\begin{aligned}E_k&=\max\midy_i-h_k(X_i)\mid\end{aligned}$$
??计算第k次的误差率e_k
$$\begin{aligned}e_{k,i}&=\frac{\midy_i-h_k(X_i)\mid}{E_k}&线性误差\\e_{k,i}&=\frac{\left(y_i-h_k(X_i)\right)^2}{E_k^2}&平方误差\\e_{k,i}&=1-e^{-\frac{\midy_i-h_k(X_i)\mid}{E_k}}&指数误差\\e_k&=\sum_{i=1}^{N}\omega_{k,i}e_{k,i}\end{aligned}$$
$$\begin{aligned}\alpha_k&=\frac{e_k}{1-e_k}\end{aligned}$$
$$\begin{aligned}\bar{\omega_{k+1,i}}&=\omega_{k,i}\alpha_k^{1-e_{k,i}}\end{aligned}$$
??最后的结合策略，采用估计器权重的中位数对应的估计器的结果，得到最终的强估计器：
$$\begin{aligned}H(x)&=\inf\left\{y\inA:\sum_{h_i(x)\ley}\ln\left(\frac{1}{\alpha_i}\right)\ge\frac{1}{2}\sum_{i=1}^{K}\ln\left(\frac{1}{\alpha_i}\right)\right\}\end{aligned}$$
??同算法步骤中的前提条件一样，假设训练集T={X_i,y_i}，i=1，...，N，y_i可取-1，+1，h(x)为估计器，估计器的数量为K。
??AdaBoost算法的一种解释是加法模型，通过多个估计器h(x)加权以后得到最后的强估计器H(x)，如下所示：（1）第k-1轮的强估计器表达式（2）第k轮的强估计器表达式（3）第k轮的强估计器可以由第k-1轮的强估计器和第k轮的加权估计器来表示
$$\begin{aligned}H_{k-1}(x)&=\sum_{i=1}^{k-1}\alpha_ih_i(x)&(1)\\H_k(x)&=\sum_{i=1}^{k}\alpha_ih_i(x)&(2)\\H_k(x)&=H_{k-1}(x)+\alpha_kh_k(x)&(3)\\\end{aligned}$$
式4-1
??接下来我们来定义最后强估计器的代价函数，AdaBoost算法选用的是指数函数，相比于0/1函数具有更好的数学性质。（1）指数代价函数（2）带入式4-1中的（3）式（3）我们的目标就是找到最优的估计器权重α和估计器h(x)（4）定义一个新的变量ω，包含前一轮的强估计器等与α、h(x)无关的值（5）替换ω
$$\begin{aligned}Cost(H(x))&=\sum_{i=1}^{N}e^{-y_iH(X_i)}&(1)\\Cost(\alpha,h(x))&=\sum_{i=1}^{N}e^{-y_i(H_{k-1}(X_i)+\alphah(X_i))}&(2)\\\alpha_k,h_k(x)&=\underset{\alpha,h(x)}{\operatorname{argmin}}\sum_{i=1}^{N}e^{-y_i(H_{k-1}(X_i)+\alphah(X_i))}&(3)\\\bar{\omega_{k,i}}&=e^{-y_iH_{k-1}(X_i)}&(4)\\\alpha_k,h_k(x)&=\underset{\alpha,h(x)}{\operatorname{argmin}}\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-y_i\alphah(X_i)}&(5)\\\end{aligned}$$
式4-2
??我们先来看下估计器h(x)，在每次训练估计器后，估计器已经确定下来了，所以我们现在只需要关心每个估计器的权重α即可。（1）找到最优的估计器权重α使得代价函数的取值最小（2）代价函数Cost(α)（3）由于标签值可取正负1，根据预测值与标签值是否相同拆为两项（4）增加第二、三两项，不影响最后的结果（5）将（4）式中前两项和后两项分别合并得到
$$\begin{aligned}\alpha_k&=\underset{\alpha}{\operatorname{argmin}}\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-y_i\alphah_k(X_i)}&(1)\\Cost(\alpha)&=\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-y_i\alphah_k(X_i)}&(2)\\&=\sum_{y_i=h_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\alpha}+\sum_{y_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{\alpha}&(3)\\&=\sum_{y_i=h_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\alpha}+\sum_{y_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\alpha}-\sum_{y_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\alpha}+\sum_{y_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{\alpha}&(4)\\&=e^{-\alpha}\sum_{i=1}^{N}\bar{\omega_{k,i}}+(e^{\alpha}-e^{-\alpha})\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))&(5)\\\end{aligned}$$
式4-3
（1）对代价函数求导数并令其为零（2）定义错误率e_k的表达式（3）将错误率e_k带入（2）式（4）两边同时乘以exp(α)（5）移项后整理得（6）求得最后的估计器权重α的表达式
$$\begin{aligned}\frac{\partialCost(\alpha)}{\partial\alpha}&=-e^{-\alpha}\sum_{i=1}^{N}\bar{\omega_{k,i}}+(e^{\alpha}+e^{-\alpha})\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))=0&(1)\\e_k&=\frac{\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))}{\sum_{i=1}^{N}\bar{\omega_{k,i}}}&(2)\\0&=-e^{-\alpha}+(e^\alpha+e^{-\alpha})e_k&(3)\\0&=-1+(e^{2\alpha}+1)e_k&(4)\\e^{2\alpha}&=\frac{1-e_k}{e_k}&(5)\\\alpha&=\frac{1}{2}\ln\frac{1-e_k}{e_k}&(6)\\\end{aligned}$$
式4-4
（1）错误率e_k的定义（2）定义ω_k（3）得到错误率e_k的表达式
$$\begin{aligned}e_k&=\frac{\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))}{\sum_{i=1}^{N}\bar{\omega_{k,i}}}&(1)\\\omega_{k,i}&=\frac{\bar{\omega_{k,i}}}{\sum_{i=1}^{N}\bar{\omega_{k,i}}}&(2)\\e_k&=\sum_{i=1}^{N}\omega_{k,i}I(y_i\neh_k(X_i))&(3)\\\end{aligned}$$
式4-5
??接下来是ω的更新方法：（1）ω_{k+1}的定义（2）带入式4-1中的（3）式（3）替换为ω_k
$$\begin{aligned}\bar{\omega_{k+1,i}}&=e^{-y_iH_{k}(X_i)}&(1)\\&=e^{-y_i(H_{k-1}(X_i)+\alpha_kh_k(X_i))}&(2)\\&=\bar{\omega_{k,i}}e^{-y_i\alpha_kh_k(X_i)}&(3)\end{aligned}$$
式4-6
（1）式4-6中的（3）（2）两边同时除以归一化参数（3）分子按照式4-5中（2）式的定义替换，分母用式4-7中（1）式替换（4）分母再按照式4-5中（2）式的定义替换（5）由于ω的和为一个常数C（6）分子分母的常数C可以消除，得到ω的更新方表达式
$$\begin{aligned}\bar{\omega_{k+1,i}}&=\bar{\omega_{k,i}}e^{-y_i\alpha_kh_k(X_i)}&(1)\\\omega_{k+1,i}&=\frac{\bar{\omega_{k,i}}e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\bar{\omega_{k+1,j}}}&(2)\\&=\frac{\omega_{k,i}\sum_{j=0}^N\left(\bar{\omega_{k,j}}\right)e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\bar{\omega_{k,j}}e^{-y_j\alpha_kh_k(X_j)}\right)}&(3)\\&=\frac{\omega_{k,i}\sum_{j=0}^N\left(\bar{\omega_{k,j}}\right)e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\omega_{k,j}\left(\sum_{l=0}^N\bar{\omega_{k,l}}\right)e^{-y_j\alpha_kh_k(X_j)}\right)}&(4)\\&=\frac{\omega_{k,i}Ce^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\omega_{k,j}Ce^{-y_j\alpha_kh_k(X_j)}\right)}&(5)\\&=\frac{\omega_{k,i}e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\omega_{k,j}e^{-y_j\alpha_kh_k(X_j)}\right)}&(6)\\\end{aligned}$$
式4-7
??综合式4-1～式4-7可以得到AdaBoost算法的表达式：
$$\begin{aligned}e_k&=\sum_{i=1}^{N}\omega_{k,i}I(y_i\neh_k(X_i))&(1)\\\alpha_k&=\frac{1}{2}\ln\frac{1-e_k}{e_k}&(2)\\\omega_{k+1,i}&=\frac{\omega_{k,i}e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j=0}^N\left(\omega_{k,j}e^{-y_j\alpha_kh_k(X_j)}\right)}&(3)\\H(x)&=\operatorname{sign}\left(\sum_{i=1}^{K}\alpha_ih_i(x)\right)&(4)\\\end{aligned}$$
式4-8
??同算法步骤中的前提条件一样，假设训练集T={X_i,y_i}，i=1，...，N，y的取值有M种可能，h(x)为估计器，估计器的数量为K。??为了适应多分类问题，AdaBoost-SAMME算法将原本为数值的标签y转化成一个向量的形式，如式4-9所示：
式4-9
??下面用一个例子来说明式4-9的含义，假设标签y可取1，2，3，标签集y={2，1，2，3}，这时根据式4-9可以得到对应的转换后的标签集如式4-10所示：
$$\begin{array}{c}y\in\{1,2,3\}\\y=\{2,1,2,3\}\\\hat{y}_i=\left\{\begin{array}{c}1&y_i=m\\-\frac{1}{2}&y_i\nem\end{array}\right.\quadm=1,2,3\\\hat{y}=\begin{bmatrix}-\frac{1}{2}&1&-\frac{1}{2}\\1&-\frac{1}{2}&-\frac{1}{2}\\-\frac{1}{2}&1&-\frac{1}{2}\\-\frac{1}{2}&-\frac{1}{2}&1\end{bmatrix}\end{array}$$
式4-10
??同样将算法解释为加法模型，通过多个估计器h(x)加权以后得到最后的强估计器H(x)，代价函数使用指数函数（1）代价函数，这里比原始算法多了一个1/M，是为了后面计算方便，同时H(X_i)也是一个向量（2）带入式4-1中的（3）式（3）同样定义一个ω，包含前一轮的强估计器等与α无关的值（4）带入ω得到代价函数的表达式（5）目标为找到最优的估计器权重α使得代价函数的取值最小
$$\begin{aligned}Cost(H(x))&=\sum_{i=1}^{N}e^{-\frac{1}{M}\hat{y}_iH(X_i)}&(1)\\Cost(\alpha)&=\sum_{i=1}^{N}e^{-\frac{1}{M}\hat{y}_i(H_{k-1}(X_i)+\alphah_k(X_i))}&(2)\\\bar{\omega_{k,i}}&=e^{-\frac{1}{M}\hat{y}_iH_{k-1}(X_i)}&(3)\\Cost(\alpha)&=\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-\frac{1}{M}\hat{y}_i\alphah_k(X_i)}&(4)\\\alpha_k&=\underset{\alpha}{\operatorname{argmin}}\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-\frac{1}{M}\hat{y}_i\alphah_k(X_i)}&(5)\\\end{aligned}$$
式4-11
??我们先来看下代价函数中指数的部分，即预测值与标签值的点积，下面分两种情况讨论：??当预测值与标签值相同的时候，向量中1的位置一致，-1/(M-1)一共有M-1个，得到如下的点积结果：
$$\begin{aligned}1+\left(M-1\right)\left(-\frac{1}{M-1}\right)\left(-\frac{1}{M-1}\right)=\frac{M}{M-1}\\\end{aligned}$$
式4-12
??当预测值与标签值不相同的时候，向量中1的位置不一致，-1/(M-1)一共有M-2个，得到如下的点积结果：
$$\begin{aligned}\left(-\frac{1}{M-1}\right)+\left(-\frac{1}{M-1}\right)+\left(M-2\right)\left(-\frac{1}{M-1}\right)\left(-\frac{1}{M-1}\right)=-\frac{M}{(M-1)^2}\end{aligned}$$
式4-13
??综合上面两种情况，得到如下的结果：
$$\hat{y}_ih_k(X_i)=\left\{\begin{aligned}&\frac{M}{M-1}&\hat{y}_i=h_k(X_i)\\&-\frac{M}{(M-1)^2}&\hat{y}_i\neh_k(X_i)\end{aligned}\right.$$
式4-14
（1）代价函数Cost(α)（2）分两种情况带入式4-14（3）增加第二、三两项，不影响最后的结果（4）将（3）式中前两项和后两项分别合并得到
$$\begin{aligned}Cost(\alpha)&=\sum_{i=1}^{N}\bar{\omega_{k,i}}e^{-\frac{1}{M}\hat{y}_i\alphah_k(X_i)}&(1)\\&=\sum_{\hat{y}_i=h_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\frac{\alpha}{M-1}}+\sum_{\hat{y}_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{\frac{\alpha}{(M-1)^2}}&(2)\\&=\sum_{\hat{y}_i=h_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\frac{\alpha}{M-1}}+\sum_{\hat{y}_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\frac{\alpha}{M-1}}-\sum_{\hat{y}_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{-\frac{\alpha}{M-1}}+\sum_{\hat{y}_i\neh_k(X_i)}^{N}\bar{\omega_{k,i}}e^{\frac{\alpha}{(M-1)^2}}&(3)\\&=e^{-\frac{\alpha}{M-1}}\sum_{i=1}^{N}\bar{\omega_{k,i}}+(e^{\frac{\alpha}{(M-1)^2}}-e^{-\frac{\alpha}{M-1}})\sum_{i=1}^{N}\bar{\omega_{k,i}}I(\hat{y}_i\neh_k(X_i))&(4)\\\end{aligned}$$
式4-15
（1）对代价函数求导数并令其为零（2）定义错误率e_k的表达式（3）将错误率e_k带入（2）式（4）两边同时乘以exp(α/(M-1))（5）移项后整理得（6）求得最后的估计器权重α的表达式
$$\begin{aligned}\frac{\partialCost(\alpha)}{\partial\alpha}&=\left(-\frac{1}{M-1}\right)e^{-\frac{\alpha}{M-1}}\sum_{i=1}^{N}\bar{\omega_{k,i}}+\left(\left(\frac{1}{(M-1)^2}\right)e^{\frac{\alpha}{(M-1)^2}}+\left(\frac{1}{(M-1)}\right)e^{-\frac{\alpha}{M-1}}\right)\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))=0&(1)\\e_k&=\frac{\sum_{i=1}^{N}\bar{\omega_{k,i}}I(y_i\neh_k(X_i))}{\sum_{i=1}^{N}\bar{\omega_{k,i}}}&(2)\\e^{-\frac{\alpha}{M-1}}&=\left(\left(\frac{1}{M-1}\right)e^{\frac{\alpha}{(M-1)^2}}+e^{-\frac{\alpha}{M-1}}\right)e_k&(3)\\1&=\left(\left(\frac{1}{M-1}\right)e^{\frac{\alpha}{(M-1)^2}+\frac{\alpha}{M-1}}+1\right)e_k&(4)\\\frac{1-e_k}{e_k}&=\left(\frac{1}{M-1}\right)e^{\frac{M\alpha}{(M-1)^2}}&(5)\\\alpha&=\frac{(M-1)^2}{M}\left(\ln\left(\frac{1-e_k}{e_k}\right)+\ln(M-1)\right)&(6)\end{aligned}$$
式4-16
??AdaBoost-SAMME.R算法是AdaBoost-SAMME算法的变体，该算法是使用加权概率估计来更新加法模型，如式4-17所示：
$$\begin{aligned}H_k(x)=H_{k-1}(x)+h_k(x)\end{aligned}$$
式4-17
??代价函数使用的依然是指数函数，不同的是已经没有了估计器权重或者说每一个估计器的权重都为1，且改成了期望的形式，其中h(x)返回的是M维的向量，同时为保证求出的h(x)唯一，加上了向量的各个元素之和为0的限制条件。
$$\begin{array}{c}h_k(x)=\underset{h(x)}{\operatorname{argmax}}E(e^{-\frac{1}{M}\hat{y}_i(H_{k-1}(x)+h(x))}\midx)\\s.t.\quadh_k^1(x)+h_k^2(x)+\cdots+h_k^M(x)=0\end{array}$$
式4-18
??代价函数可以拆分成对每一类分别求期望后再相加：
$$\begin{aligned}Cost(h(x))&=E(e^{-\frac{1}{M}\hat{y}_i(H_{k-1}(x)+h(x))}\midx)&(1)\\&=E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x)}\midx)&(2)\\&=E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x)}I(y=1)\midx)+\cdots+E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x)}I(y=M)\midx)&(3)\\\end{aligned}$$
式4-19
??先来看看当y=1时，y*h(x)的结果：（1）当y=1时，转换后y的向量形式（2）计算点积的结果（3）合并最后的项（4）根据限制条件替换（5）得到化简后的结果
$$\begin{aligned}\hat{y}&=[1,-\frac{1}{M-1},\cdots,-\frac{1}{M-1}]&(1)\\\hat{y}_ih(x)&=h^1(x)+(-\frac{1}{M-1})h^2(x)+\cdots+(-\frac{1}{M-1})h^M(x)&(2)\\&=h^1(x)-\frac{h^2(x)+\cdots+h^M(x)}{M-1}&(3)\\&=h^1(x)-\frac{-h^1(x)}{M-1}&(4)\\&=\frac{Mh^1(x)}{M-1}&(5)\\\end{aligned}$$
式4-20
（1）带入式4-20（2）提出与期望无关的项（3）另后面的期望为P(y=1|x)（4）同理可以得每一类的期望结果
$$\begin{aligned}E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x)}I(y=1)\midx)&=E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{h^1(x)}{M-1}}I(y=1)\midx)&(1)\\&=e^{-\frac{h^1(x)}{M-1}}E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}I(y=1)\midx)&(2)\\P(y=1|x)&=E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}I(y=1)\midx)&(3)\\E(e^{-\frac{1}{M}\hat{y}_iH_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x)}I(y=m)\midx)&=e^{-\frac{h^m(x)}{M-1}}P(y=m|x)&(4)\\\end{aligned}$$
式4-21
??将上面的结果带入代价函数得：
$$\begin{aligned}Cost(h(x))&=e^{-\frac{h^1(x)}{M-1}}P(y=1|x)+\cdots+e^{-\frac{h^M(x)}{M-1}}P(y=M|x)&(1)\\&=\sum_{m=1}^{M}e^{-\frac{h^m(x)}{M-1}}P(y=m|x)&(2)\\\end{aligned}$$
式4-22
??这时可以使用拉格朗日乘数法来求解上述问题，其拉格朗日函数L如下：
$$\begin{aligned}L(h(x),\lambda)&=\sum_{m=1}^{M}e^{-\frac{h^m(x)}{M-1}}P(y=m|x)-\lambda\sum_{m=1}^{M}h^m(x)\\\end{aligned}$$
式4-23
??拉格朗日函数分别对h(x)的各个分量求导数：
$$\begin{aligned}\frac{\partialL(h(x),\lambda)}{\partialh^1(x)}&=-\frac{1}{M-1}e^{-\frac{h^1(x)}{M-1}}P(y=1|x)-\lambda=0\\\frac{\partialL(h(x),\lambda)}{\partialh^2(x)}&=-\frac{1}{M-1}e^{-\frac{h^2(x)}{M-1}}P(y=2|x)-\lambda=0\\&\cdots\\\frac{\partialL(h(x),\lambda)}{\partialh^M(x)}&=-\frac{1}{M-1}e^{-\frac{h^M(x)}{M-1}}P(y=M|x)-\lambda=0\\\end{aligned}$$
式4-24
??两两联立式4-24，分别求出各个分量的结果，下面以第一个为例：（1）联立导数中的第1，2式子（2）消掉相同的常数项再两边同时取对数（3）移项化简后得
$$\begin{aligned}-\frac{1}{M-1}e^{-\frac{h^1(x)}{M-1}}P(y=1|x)&=-\frac{1}{M-1}e^{-\frac{h^2(x)}{M-1}}P(y=2|x)&(1)\\-\frac{h^1(x)}{M-1}+\lnP(y=1|x)&=-\frac{h^2(x)}{M-1}+\lnP(y=2|x)&(2)\\h^1(x)-h^2(x)&=(M-1)(\lnP(y=1|x)-\lnP(y=2|x))&(3)\\\end{aligned}$$
式4-25
（1）～（3）同理可得（4）将（1）～（3）式累加起来根据限制条件化简（5）将最后一项补充完整（6）得到第一个分量的结果
$$\begin{aligned}h^1(x)-h^2(x)&=(M-1)(\lnP(y=1|x)-\lnP(y=2|x))&(1)\\h^1(x)-h^3(x)&=(M-1)(\lnP(y=1|x)-\lnP(y=3|x))&(2)\\&\cdots\\h^1(x)-h^M(x)&=(M-1)(\lnP(y=1|x)-\lnP(y=M|x))&(3)\\(M-1)h^1(x)-(-h^1(x))&=(M-1)((M-1)\lnP(y=1|x)-\sum_{m\ne1}\lnP(y=m|x)))&(4)\\Mh^1(x)&=(M-1)(M\lnP(y=1|x)-\sum_{m=1}^{M}\lnP(y=m|x))&(5)\\h^1(x)&=(M-1)(\lnP(y=1|x)-\frac{1}{M}\sum_{m=1}^{M}\lnP(y=m|x))&(6)\\\end{aligned}$$
式4-26
??同理可得h(x)各个分量的结果
$$\begin{aligned}h^m(x)&=(M-1)(\lnP(y=m|x)-\frac{1}{M}\sum_{m^{'}=1}^{M}\lnP(y=m^{'}|x))\\\end{aligned}$$
式4-27
??样本权重的更新如下，将h(x)带入更新方法中，可以看到更新方法只保留了前面一项，因为后面一项为每一类的p(x)求和，可以认为是一个常数，归一化以后不影响最后的结果。
$$\begin{aligned}\bar{\omega_{k,i}}&=e^{-\frac{1}{M}\hat{y}_iH_{k-1}(X_i)}&(1)\\\bar{\omega_{k+1,i}}&=\bar{\omega_{k,i}}e^{-\frac{1}{M}\hat{y}_ih_{k}(X_i)}&(2)\\&=\bar{\omega_{k,i}}e^{-\frac{M-1}{M}\hat{y}_i\lnp_k(X_i)}&(3)\\\end{aligned}$$
式4-28
使用Python实现AdaBoost算法
fromsklearn.ensembleimportAdaBoostRegressor#自适应增强回归器clf=AdaBoostRegressor(n_estimators=50,random_state=0)#拟合数据集clf=clf.fit(X,y)七、示例演示??图7-1展示了使用自适应增强算法进行二分类的结果，红色表示标签值为-1的样本点，蓝色代表标签值为1的样本点。浅红色的区域为预测值为-1的部分，浅蓝色的区域则为预测值为1的部分
??图7-2、图7-3分别展示了使用SAMME和SAMME.R算法进行多分类的结果，红色表示标签值为0的样本点，蓝色代表标签值为1的样本点，绿色代表标签值为2的样本点。浅红色的区域为预测值为0的部分，浅蓝色的区域则为预测值为1的部分，浅绿色的区域则为预测值为1的部分