AdaBoost算法原理及其代码实现

前言

AdaBoost算法是基于Boosting思想的一种集成学习算法，是Boosting家族中最著名的算法之一。本文将介绍AdaBoost算法的原理，从二分类问题到多分类问题，再到回归问题，并且介绍其sklearn代码实现。

AdaBoost算法流程

从Boosting开始

AdaBoost算法是基于Boosting思想的，所以我们先来回顾一下Boosting思想的框架，如下图

接下来，我们要在这个框架上填上具体内容，而上述框架缺失的有弱学习器，更新权重，结合策略，需要注意的是AdaBoost算法与Boosting一样，并不是一种具体的算法，而是一种思想，也就是说，我们这里并不会将所有缺失的内容填满，而是留下弱学习器不填。可以理解为，AdaBoost算法是Boosting的一个子集，其确定了更新权重的方法与结合策略，但是没有确定弱学习器。

二分类问题

与一些机器学习算法一样，AdaBoost算法也是从二分类问题开始发展的。由于更新权重的策略并不是一个简单的问题，因此我们这里先给出整个AdaBoost算法的流程，后续再追根溯源。

假设我们的训练样本为

$$T=\{(x,y_1),(x_2,y_2),\ldots,(x_m,y_m)\}$$

其中$y_i \in \{ -1, 1 \}$，也就是二分类变量。

在AdaBoost算法中，每个样本是有权重的，并且权重在训练过程中逐轮更新，因此我们定义第$k$轮的样本权重为

$$D(k)=(w_{k1},w_{k2},\ldots ,w_{km}) \quad i=1,2...m$$

权重之和为1，并且，初始权重为$\frac{1}{m}$，也就是

$$D(1) = (w_{11},w_{12},\ldots ,w_{1m}) = (\frac1m,\frac1m,\ldots \frac1m)$$

现在我们临时插入结合策略的方案，AdaBoost采用加权平均法，记第$k$轮训练出的弱学习器为$G_k(x)$，则最终的强学习器为

$$f(x)=\mathrm{sign}(\sum_{k=1}^{K}\alpha_{k}G_{k}(x))$$

注：$\mathrm{sign}(x)$为符号函数，也可以写为$\mathrm{sgn}(x)$，其定义为

$$\mathrm{sign}(x) = \begin{cases} 1 & x>0 \\ 0 & x=0 \\ -1 & x<0 \\ \end{cases}$$

可以看出，如果出现$x=0$，则会出现错误，虽然一般不会出现该情况，但是保险起见，我们可以修改定义为

$$\mathrm{sign}(x) = \begin{cases} 1 & x\ge0 \\ -1 & x<0 \\ \end{cases}$$

而AdaBoost算法的思路就是通过每一次训练的弱学习器的误差，确定该弱学习器的权重$\alpha_{k}$，并且更新下一次训练所用的样本权重$D(k+1)$，这也很好理解，如果一个弱学习器的准确率高，则权重自然要高，反之亦然，而一个样本被本轮弱学习器误判，则这个样本在下一轮训练中应该得到重视，因此该样本的权重会提高，反之亦然。

最后，我们来看AdaBoost是如何具体实现学习器权重的计算与样本权重的更新的，首先是误差的定义，分类问题的误差就是判断的正确与否，一般的误差率计算公式为

$$\frac1m\sum_{i=1}^m I(G_k(x_i)\neq y_i)$$

但是这里我们需要将样本权重也考虑进去，也就是第$k$个弱学习器的误差率为

$$e_k = \sum_{i=1}^mw_{ki}I(G_k(x_i)\neq y_i)$$

这才能起到权重高的样本被更多关注的目的。

注：$I(x)$为示函数，其定义为

$$I(G_k(x_i)\neq y_i) = \begin{cases} 1 & G_k(x_i) \neq y_i \\ 0 & G_k(x_i) = y_i \\ \end{cases}$$

接着，我们可以计算第$k$个弱学习器的权重为

$$\alpha_k=\frac{1}{2}\mathrm{ln}\frac{1-e_k}{e_k}$$

而样本权重的更新公式为

$$w_{k+1,i} = \frac{w_{ki}}{Z_{K}} e^{-\alpha_{k}y_{i}G_{k}(x_{i})}$$

其中$Z_k$为规范化因子，其值为

$$Z_k = \sum_{i=1}^mw_{ki} e^{-\alpha_ky_iG_k(x_i)}$$

其为作用为保证样本权重之和为1。

注：这里的弱学习器权重与样本权重的更新给出的很突兀，后文会给出其详细推导的

现在我们来总结一下AdaBoost算法处理二分类问题的步骤

输入：训练数据集$T$，弱学习器，训练次数

输出：强学习器

(1) 初始化训练集权重$D(1) = (w_{11},w_{12},\ldots ,w_{1m}) = (\frac1m,\frac1m,\ldots \frac1m)$

(2) 对于第$k$轮训练，使用带权重$D(k)$的训练集进行训练，得到弱学习器$G_k(x)$

(3) 计算$G_k(x)$的误差率$e_k = \sum_{i=1}^mw_{ki}I(G_k(x_i)\neq y_i)$

(4) 计算$G_k(x)$的权重$\alpha_k=\frac{1}{2}\mathrm{ln}\frac{1-e_k}{e_k}$

(5) 更新权重为$w_{k+1,i} = \frac{w_{ki}}{Z_{K}} e^{-\alpha_{k}y_{i}G_{k}(x_{i})}$，其中$Z_k = \sum_{i=1}^mw_{ki} e^{-\alpha_ky_iG_k(x_i)}$

(6) 当完成全部训练后，得到强学习器$f(x)=\mathrm{sign}(\sum_{k=1}^{K}\alpha_{k}G_{k}(x))$

AdaBoost算法的解释

向前分布算法

现在我们来推导学习器权重与样本权重更新公式。首先，我们要简单介绍一下向前分布算法，对于加法模型

$$f(x) = \sum_{m=1}^M \beta_m b(x;\gamma_m)$$

其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数。

对于该加法模型，给定损失函数$L(y,f(x))$，求解以下优化问题

$$\min_{\beta_m,\gamma_m}\sum_{i=1}^NL\left(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m)\right)$$

显然，这是一个复杂的问题。但是注意到，我们可以对其做如下分解

$$f(x) = f_{m-1}(x) + \beta_M b(x;\gamma_M)$$

同理，$f_{m-1}(x)$也可以做该分解。对此，我们可以想到，从$\beta_1 b(x;\gamma_1)$开始，从前向后逐步学习每一组参数，也就是每一步只需要求解优化问题

$$\min_{\beta,\gamma}\sum_{i=1}^NL\left(y_i,\beta b(x_i;\gamma)\right)$$

这就是向前分步算法。

AdaBoost算法的推导

可以注意到，AdaBoost算法所训练出的模型也是一个加法模型

$$f(x) = \sum_{k=1}^{K} \alpha_{k} G_{k}(x)$$

定义其损失函数为指数损失函数，即

$$L(y,f(x)) = e^{-yf(x)}$$

注：损失函数就是用于衡量预测值$f(x)$与真实值$y$之间误差的函数，例如回归问题中最常用的$L(y,f(x)) = (y - f(x))^2$，而指数损失函数为分类问题中最常用的损失函数，可以注意到，当分类正确时，其值为$e^{-1}$，当分类错误时，其值为$e^1$，分类错误时的损失函数值大。

在第$k$轮训练中会得到的学习器为

$$f_k(x) = f_{k-1}(x) + \alpha_{k} G_{k}(x)$$

我们需要求解$\alpha_{k}$与$G_{k}(x)$，其优化问题为

$$\arg\min L = \arg\min_{\alpha_k,G_k} \sum_{i=1}^N e^{-y_i(f_{k-1}(x_i)+\alpha_k G_k(x_i))} = \arg\min_{\alpha_k,G_k} \sum_{i=1}^N e^{-y_i f_{k-1}(x_i)} e^{-y_i \alpha_k G_k(x_i)}$$

记$w_{ki} = e^{-y_i f_{k-1}(x_i)}$，上述优化问题可写为

$$\arg\min_{\alpha_k,G_k} \sum_{i=1}^N w_{ki} e^{-y_i \alpha_k G_k(x_i)}$$

可以注意到，$w_{ki}$其实就是样本权重，其计算公式与本次训练需要求解的$\alpha_{k}$与$G_{k}(x)$无关，而只与上一次训练得到的学习器，也就是$f_{k-1}$有关。通过简单的证明可以得到其与上一小节所给的样本权重更新公式是相同的，证明如下

$$w_{ki} = e^{-y_i f_{k-1}(x_i)} = e^{-y_i (f_{k-2}(x_i) + \alpha_{k-1} G_{k-1}(x_i))} = e^{-y_i f_{k-2}(x_i)} e^{-y_i \alpha_{k-1} G_{k-1}(x_i)} = w_{k-1,i} e^{-y_i \alpha_{k-1} G_{k-1}(x_i)}$$

只需要再除以规范化因子，就是上述我们给出的样本权重更新公式了。现在我们已经推导出样本权重的计算公式了，接着往下看。

注：上述权重更新公式也可以写为

$$w_{k,i} = \begin{cases} \frac{w_{mi}}{Z_m} e^{-\alpha_m}, &G_m(x_i)=y_i \\ \frac{w_{mi}}{Z_m} e^{\alpha_m}, &G_m(x_i) \neq y_i \\ \end{cases}$$

并且，由于

$$- y_i G_k(x_i) = \begin{cases} -1 & y_i = G(x_i) \\ 1 & y_i\neq G(x_i) \\ \end{cases}$$

因此，可以得出$- y_i G_k(x_i) = 2I(y_i\neq G(x_i)) - 1$，则样本权重更新公式可改写为

$$w_{ki} = w_{k-1,i} e^{-y_i \alpha_{k-1} G_{k-1}(x_i)} = w_{k-1,i} e^{\alpha_{k-1}(2I(y_i\neq G(x_i)) - 1)} = w_{k-1,i} e^{2\alpha_{k-1}I(y_i\neq G(x_i))} e^{- \alpha_{k-1}}$$

由于$e^{- \alpha_{k-1}}$是常数，因此可以忽略（这在后面很多推导中都会用到），故$w_{ki} = w_{k-1,i} e^{2\alpha_{k-1}I(y_i\neq G(x_i))}$，这是AdaBoost.M1算法所使用的样本权重更新公式。

求解上述优化问题可以分为两步，首先是求解$G_k$，无论$\alpha_{k}$取何值，为了使得目标函数最小，$G_k$的目标都应该是误差率最小，也就是说

$$G_k^*(x) = \arg\min_{G_k} \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))$$

其中，$G_k^*(x)$为$G_k(x)$的最优解。

接着，将$G_k^*(x)$代入原优化问题，则该问题变为一个单变量优化问题

$$\arg\min_{\alpha_k} \sum_{i=1}^N w_{ki} e^{-y_i \alpha_k G_k^*(x_i)}$$

对其目标函数做变式

$$\sum_{i=1}^N w_{ki} e^{-y_i \alpha_k G_k^*(x_i)} = \sum_{y_i=G_k^*(x_i)} w_{ki} e^{-\alpha} + \sum_{y_i\neq G_k^*(x_i)} w_{ki} e^\alpha \\ = \sum_{y_i\neq G_k^*(x_i)} w_{ki} e^\alpha + \sum_{i=1}^N w_{ki} e^{-\alpha} - \sum_{y_i \neq G_k^*(x_i)} w_{ki} e^{-\alpha} = (e^{\alpha} - e^{-\alpha}) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) + e^{-\alpha} \sum_{i=1}^N w_{ki}$$

注：$\sum_{y_i\neq G_k^*(x_i)}$跟$\sum_{i=1}^N I(y_i\neq G(x_i))$是一样的，就是写法不同而已。

记上述目标函数为$L$，接着我们用正常的单变量优化问题的求解方法，对其求导并令其为0，将其对$\alpha$求导可得

$$\frac{\partial L}{\partial \alpha} = (e^{\alpha} + e^{-\alpha}) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) - e^{-\alpha} \sum_{i=1}^N w_{ki}$$

令其为0，可得

$$(e^{\alpha} + e^{-\alpha}) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) - e^{-\alpha} \sum_{i=1}^N w_{ki} = 0 \\ \Rightarrow \quad (e^{\alpha} + e^{-\alpha}) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) = e^{-\alpha} \sum_{i=1}^N w_{ki} \\ \Rightarrow \quad e^{\alpha} \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) = e^{-\alpha} \sum_{i=1}^N w_{ki} I(y_i = G(x_i)) \\ \Rightarrow \quad e^{2\alpha} = \frac{\sum_{i=1}^N w_{ki} I(y_i = G(x_i))}{\sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))} \quad \Rightarrow \quad 2\alpha = \mathrm{ln}\left( \frac{\sum_{i=1}^N w_{ki} I(y_i = G(x_i))}{\sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))} \right)$$

显然，$\sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))$为误差率$e_k$，因此，学习器权重$\alpha_k$为

$$\alpha_k = \frac12 \mathrm{ln}\left( \frac{1 - e_k}{e_k} \right)$$

至此，我们完成了AdaBoost算法的完整推导。

多分类问题与回归问题

多分类问题

现在我们来将AdaBoost算法推广至多分类问题，这里我们介绍两个AdaBoost的扩展算法，分别为SAMME算法与SAMME.R算法。

SAMME算法

多分类变量

首先是对于多分类问题，输出$y$要如何修改，SAMME算法的处理方法是，将输出改为一个$1 \times R$的向量，其中$R$为该问题的类别数。我们记

$$y_i = (y_{i1}, y_{i2}, \ldots, y_{iR})$$

当样本属于第$k$类时，$y_{ik} = 1$，其他列均为$-\frac{1}{R-1}$，也就是说$y_i$的列和为0，例如样本属于第一类，则

$$y_i = (1, -\frac{1}{R-1}, \ldots, -\frac{1}{R-1})$$

同理，最终得到的强学习器的输出也应该为一个$1 \times R$的向量，这依旧可以写为加法模型

$$f(x) = \sum_{k=1}^{K} \alpha_{k} G_{k}(x)$$

其最终结果为整个向量的最大值对应的列数，也就是

$$F(x) = \max_{r}(f^{(r)}(x))$$

权重更新公式推导

接着，我们来进行SAMME算法的推导，这与上述推导基本相同，首先是损失函数定义为

$$L(y,f(x)) = e^{-\frac{1}{R}Yf(x)}$$

其优化问题可写为

$$\arg\min L = \arg\min_{\alpha_k,G_k} \sum_{i=1}^N e^{- \frac{1}{R} y_i(f_{k-1}(x_i)+\alpha_k G_k(x_i))} = \arg\min_{\alpha_k,G_k} \sum_{i=1}^N w_{ki} e^{- \frac{1}{R} y_i \alpha_k G_k(x_i)}$$

其中$w_{ki} = e^{- \frac{1}{R} y_i f_{k-1}(x_i)}$，故这里我们可以推导出样本权重的更新公式为

$$w_{ki} = e^{- \frac{1}{R} y_i f_{k-1}(x_i)} = e^{- \frac{1}{R} y_i (f_{k-2}(x_i) + \alpha_{k-1} G_{k-1}(x_i))} = e^{- \frac{1}{R} y_i f_{k-2}(x_i)} e^{- \frac{1}{R} y_i \alpha_{k-1} G_{k-1}(x_i)} = w_{k-1,i} e^{- \frac{1}{R} y_i \alpha_{k-1} G_{k-1}(x_i)}$$

而后该优化问题分两步解，同理最优$G_k$为

$$G_k^*(x) = \arg\min_{G_k} \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))$$

代入原优化问题，并对其目标函数进行变式

$$\sum_{i=1}^N w_{ki} e^{- \frac{1}{R} y_i \alpha_k G_k^*(x_i)} = \sum_{y_i=G_k^*(x_i)} w_{ki} e^{- \frac{1}{R - 1} \alpha} + \sum_{y_i\neq G_k^*(x_i)} w_{ki} e^{\frac{1}{(R - 1)^2} \alpha} \\ = \sum_{i=1}^N w_{ki} e^{- \frac{1}{R - 1} \alpha} - \sum_{y_i = G_k^*(x_i)} w_{ki} e^{- \frac{1}{R - 1} \alpha} + \sum_{y_i\neq G_k^*(x_i)} w_{ki} e^{\frac{1}{(R - 1)^2} \alpha} \\ = e^{- \frac{1}{R - 1} \alpha} \sum_{i=1}^N w_{ki} + (e^{\frac{\alpha}{(R - 1)^2}} - e^{- \frac{\alpha}{R - 1}}) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))$$

注：这里补充一下$y_i G_k(x_i)$的值，由于两者均为$1 \times R$向量，严格来讲应该写为$y_i G_k^T(x_i)$，两者相乘为一个数。当判断正确时，其值为

$$1 + (R - 1)\left( -\frac{1}{R - 1} \right)^2 = \frac{R}{R - 1}$$

当判断错误是，其值为

$$-\frac{2}{R - 1} + (R - 2)\left( -\frac{1}{R - 1} \right)^2 = -\frac{R}{(R - 1)^2}$$

因此，$y_i G_k(x_i)$的值为

$$y_i G_k(x_i) = \begin{cases} \frac{R}{R - 1} & y_i = G(x_i) \\ -\frac{R}{(R - 1)^2} & y_i\neq G(x_i) \\ \end{cases}$$

记其为$L$，对$\alpha$求导可得

$$\frac{\partial L}{\partial \alpha} = -\frac{1}{R - 1} e^{- \frac{1}{R - 1} \alpha} \sum_{i=1}^N w_{ki} + \left( \frac{1}{(R - 1)^2} e^{\frac{\alpha}{(R - 1)^2}} + \frac{1}{R - 1} e^{- \frac{\alpha}{R - 1}} \right) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))$$

令其为0可得

$$-\frac{1}{R - 1} e^{- \frac{1}{R - 1} \alpha} \sum_{i=1}^N w_{ki} + \left( \frac{1}{(R - 1)^2} e^{\frac{\alpha}{(R - 1)^2}} + \frac{1}{R - 1} e^{- \frac{\alpha}{R - 1}} \right) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) = 0 \\ \Rightarrow \quad \left( \frac{1}{(R - 1)^2} e^{\frac{\alpha}{(R - 1)^2}} + \frac{1}{R - 1} e^{- \frac{\alpha}{R - 1}} \right) \sum_{i=1}^N w_{ki} I(y_i\neq G(x_i)) = \frac{1}{R - 1} e^{- \frac{1}{R - 1} \alpha} \sum_{i=1}^N w_{ki} \\ \Rightarrow \quad \left( \frac{1}{R - 1} e^{\frac{R\alpha}{(R - 1)^2}} + 1 \right) \frac{\sum_{i=1}^N w_{ki} I(y_i\neq G(x_i))}{\sum_{i=1}^N w_{ki}} = 1 \quad \Rightarrow \quad \frac{1}{R - 1} e^{\frac{R\alpha}{(R - 1)^2}} = \frac{1 - e_k}{e_k} \\ \Rightarrow \quad \frac{R\alpha}{(R - 1)^2} = \mathrm{ln}(\frac{1 - e_k}{e_k}) + \mathrm{ln}(R - 1) \quad \Rightarrow \quad \alpha = \frac{(R - 1)^2}{R} \left( \mathrm{ln}(\frac{1 - e_k}{e_k}) + \mathrm{ln}(R - 1) \right)$$

故解得弱学习器权重为

$$\alpha_k = \frac{(R - 1)^2}{R} \left[ \mathrm{ln} \frac{1 - e_k}{e_k} + \mathrm{ln}(R - 1) \right]$$

权重更新公式的优化

可以注意到，上述推导出的弱学习器权重公式与样本权重更新公式均较复杂，为了降低计算量，我们可以对上述公式进行精简优化。首先是弱学习器权重公式，可以注意到$\frac{(R - 1)^2}{R}$为常数，因此可以忽略，记为

$$\alpha_k^* = \left[ \mathrm{ln}\frac{1 - e_k}{e_k} + \mathrm{ln}(R - 1) \right]$$

且$\alpha_k = \frac{(R - 1)^2}{R} \alpha_k^*$。注意到样本权重更新公式中也有$\alpha_k$，因此需要将其更新为

$$w_{k+1,i} = w_{ki} e^{- \frac{(R - 1)^2}{R^2} y_i \alpha_{k}^* G_{k}(x_i)}$$

上文我们提到过AdaBoost.M1算法将样本权重更新公式改写为示函数的形式，这里我们也可以做类似改动，由于

$$y_i G_k(x_i) = \begin{cases} \frac{R}{R - 1} & y_i = G(x_i) \\ -\frac{R}{(R - 1)^2} & y_i\neq G(x_i) \\ \end{cases}$$

可以得到

$$e^{- \frac{(R - 1)^2}{R^2} y_i \alpha_{k}^* G_{k}(x_i)} = \begin{cases} e^{\frac{1 - R}{R} \alpha_{k}^*} & y_i = G(x_i) \\ e^{\frac{1}{R} \alpha_{k}^*} & y_i\neq G(x_i) \\ \end{cases}$$

注意到$e^{\frac{1}{R} \alpha_{k}^*} = e^{\frac{1 - R + R}{R} \alpha_{k}^*} = e^{(\frac{1 - R}{R} + 1) \alpha_{k}^*} = e^{\frac{1 - R}{R} \alpha_{k}^*} e^{\alpha_{k}^*}$，因此可以写为

$$e^{- \frac{(R - 1)^2}{R^2} y_i \alpha_{k}^* G_{k}(x_i)} = e^{\frac{1 - R}{R} \alpha_{k}^*} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$$

也就是当$y_i = G(x_i)$时，后面的$e^{\alpha_{k}^* I(y_i\neq G(x_i))} = e^0 = 1$，故$e^{- \frac{(R - 1)^2}{R^2} y_i \alpha_{k}^* G_{k}(x_i)} = e^{\frac{1 - R}{R} \alpha_{k}^*}$，当$y_i\neq G(x_i)$时，$e^{\alpha_{k}^* I(y_i\neq G(x_i))} = e^{\alpha_{k}^*}$，故$e^{- \frac{(R - 1)^2}{R^2} y_i \alpha_{k}^* G_{k}(x_i)} = e^{\frac{1}{R} \alpha_{k}^*}$，其实就是改个写法，能理解吧。

再注意到，$e^{\frac{1 - R}{R} \alpha_{k}^*}$对于每一个样本$i$都是一样的，跟规范化因子$Z_k$一样，可以视作一个常数，因此可以忽略，故最终的样本权重更新公式为

$$w_{k+1,i} = w_{ki} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$$

标准化后为

$$w_{k+1,i} = \frac{w_{ki}}{Z_k} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$$

其中

$$Z_k = \sum_{i=1}^mw_{ki} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$$

至此我们就推导出了SAMME算法的样本权重更新公式及弱学习器权重公式，其余部分与一般的AdaBoost算法相同。总结一下就是

输入：训练数据集$T$，弱学习器，训练次数

输出：强学习器

(1) 初始化训练集权重$D(1) = (w_{11},w_{12},\ldots ,w_{1m}) = (\frac1m,\frac1m,\ldots \frac1m)$

(2) 对于第$k$轮训练，使用带权重$D(k)$的训练集进行训练，得到弱学习器$G_k(x)$

(3) 计算$G_k(x)$的误差率$e_k = \sum_{i=1}^mw_{ki}I(G_k(x_i)\neq y_i)$

(4) 计算$G_k(x)$的权重$\alpha_k = \left( \mathrm{ln}(\frac{1 - e_k}{e_k}) + \mathrm{ln}(R - 1) \right)$

(5) 更新权重为$w_{k+1,i} = \frac{w_{ki}}{Z_k} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$，其中$Z_k = \sum_{i=1}^mw_{ki} e^{\alpha_{k}^* I(y_i\neq G(x_i))}$

(6) 当完成全部训练后，得到强学习器$F(x) = \max_{r}(f^{(r)}(x))$，其中$f(x)=\sum_{k=1}^{K}\alpha_{k}G_{k}(x)$

SAMME.R算法

接着我们来介绍SAMME.R算法，这是一种SAMME算法的改进，其具有更快的收敛速度。SAMME.R算法将$\alpha_{k}G_{k}(x)$统一为$h_k(x)$，也就是说

$$f_k(x) = f_{k-1}(x) + h_k(x)$$

并且，SAMME.R算法引入了加权概率估计，用于代替误差率，记为$p(x)$。就是说，对于每一轮训练出的弱学习器$G_k(x)$，有对应的$p_k(x)$，其输出为$x$被分到每一类的概率。对于一个样本$x_i$，其标签为$y_i$，是一个$1 \times R$的向量，$R$为类别数，这里的$y_i$形式与SAMME算法相同，而$p_k(x_i)$，也为一个$1 \times R$的向量，其第$r$列记为$p_k^{(r)}(x_i)$，代表$x_i$被分到第$r$类的概率。

注：$p_k(x)$的计算也是带权重的

$h_k(x)$与样本权重更新公式均与$p_k(x)$有关，具体为

$$h_k^{(r)}(x) = (R - 1) \left[ \ln p_k^{(r)}(x) - \frac1R \sum_{j = 1}^{R} \ln p_k^{(j)}(x) \right]$$

这里的$h_k^{(r)}(x)$指$h_k(x)$的第$r$列。

$$w_{k+1,i} = w_{ki} e^{-\frac{R - 1}{R} y_i \ln p_k(x_i)}$$

故SAMME.R算法的流程为

输入：训练数据集$T$，弱学习器，训练次数

输出：强学习器

(1) 初始化训练集权重$D(1) = (w_{11},w_{12},\ldots ,w_{1m}) = (\frac1m,\frac1m,\ldots \frac1m)$

(2) 对于第$k$轮训练，使用带权重$D(k)$的训练集进行训练，得到弱学习器$G_k(x)$

(3) 计算$G_k(x)$的加权概率估计$p_k(x)$

(4) 计算$h_k^{ ( r ) }(x) = (R - 1) \left[ \ln p_k^{ ( r ) }(x) - \frac1R \sum_{j = 1}^{R} \ln p_k^{(j)}(x) \right] $

(5) 更新权重为$w_{k+1,i} = \frac{w_{ki}}{Z_k} e^{-\frac{R - 1}{R} y_i \ln p_k(x_i)}$，其中$Z_k = \sum_{i=1}^m w_{ki} e^{-\frac{R - 1}{R} y_i \ln p_k(x_i)}$

(6) 当完成全部训练后，得到强学习器$F(x) = \max_{r}(f^{(r)}(x))$，其中$f(x)=\sum_{k=1}^{K} h_k(x)$

回归问题

最后是如何使用AdaBoost处理回归问题，这里我们介绍AdaBoost.R2算法的流程

输入：训练数据集$T$，弱学习器，训练次数

输出：强学习器

(1) 初始化训练集权重$D(1) = (w_{11},w_{12},\ldots ,w_{1m}) = (\frac1m,\frac1m,\ldots \frac1m)$

(2) 对于第$k$轮训练，使用带权重$D(k)$的训练集进行训练，得到弱学习器$G_k(x)$

(3) 计算每个样本的误差$e_{ki} = \frac{|y_i-G_k(x_i)|}{E_k}$，其中$E_k = \mathrm{max}|y_i-G_k(x_i)|$，也可以使用不同的误差计算方法，如$e_{ki} = \frac{(y_i-G_k(x_i))^2}{E_k^2}$或$e_{ki} = 1 - e^{-\frac{|y_i-G_k(x_i)|}{E_k}}$

(3) 计算$G_k(x)$的误差率$e_k = \sum_{i=1}^m e_{ki}$

(4) 计算$G_k(x)$的权重$\alpha_k = \frac{1 - e_k}{e_k}$

(5) 更新权重为$w_{k+1,i}=\frac{w_{ki}}{Z_{k}}\alpha_{k}^{1-e_{kt}}$，其中$Z_{k}=\sum_{i=1}^{m}w_{ki}\alpha_{k}^{1-e_{kt}}$

(6) 当完成全部训练后，得到强学习器$f(x) = G_k^*(x)$，其中，$G_k^*(x)$是所有$\mathrm{ln}(\frac{1}{\alpha_{k}})$的中位数值乘以对应序号$k^*$所对应的学习器

这里需要额外解释一下最后一步，也就是结合策略的部分，这与分类算法是有较大区别的。这里我们所使用的权重其实是$\mathrm{ln}(\frac{1}{\alpha_{k}})$，我们选取权重的中位数，这可以避免欠拟合与过拟合，假设其中位数为$\mathrm{ln}(\frac{1}{\alpha_{h}})$，对应的弱学习器为$G_h(x)$，则$G_k^*(x) = \mathrm{ln}(\frac{1}{\alpha_{h}}) G_h(x)$。

sklearn代码实现

最后我们来介绍一下sklearn代码实现，运行环境为jupyter notebook，需要用到的库为

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns

from sklearn.ensemble import AdaBoostClassifier  # AdaBoost分类
from sklearn.ensemble import AdaBoostRegressor  # AdaBoost回归
from sklearn.tree import DecisionTreeClassifier  # 决策树分类
from sklearn.tree import DecisionTreeRegressor  # 决策树回归

from sklearn.datasets import load_wine  # 红酒数据集
from sklearn.datasets import load_boston  # 波士顿房价数据集

from sklearn.model_selection import train_test_split  # 切分数据

from scipy import stats

import warnings
warnings.filterwarnings("ignore")

使用红酒数据集与波士顿房价数据集作为示例数据

# 读取数据
wine = load_wine()
boston = load_boston()

分类

对于分类问题，使用AdaBoostClassifier函数，其使用的就是我们上文所提到的SAMME与SAEEM.R算法，其参数列表如下

参数	说明
base_estimator	弱学习器，需要支持样本权重，常用CART决策树与MLP。默认为DecisionTreeClassifier(max_depth=1)。
n_estimators	训练次数，也就是弱学习器数量，在任何集成学习算法中都是重要的参数。
learning_rate	学习率，默认为1，较大的学习率可以完成模型的快速收敛，较小的学习率可以使得模型的学习更加的精细。learning_rate和n_estimators之间存在权衡关系，一般较小的学习率要配合较大的训练次数。
algorithm	分类问题独有的参数，选择使用的算法，可填**{‘SAMME’, ‘SAMME.R’}，默认为’SAMME.R’**。
random_state	随机数种子

其中，我们需要补充一下学习率，学习率就是在原有模型的基础上增加一个参数$v$，模型变为

$$f(x) = \sum_{k=1}^{K} v \alpha_{k} G_{k}(x)$$

很自然的可以得到，模型的更新公式变为

$$f_k(x) = f_{k-1}(x) + v \alpha_{k} G_{k}(x)$$

其默认为1，就是我们原本的模型。当其大于1时，会加快学习速度，例如模型原本需要50次训练才能收敛，但是调大$v$后可能只需要30次，适合用于粗调，验证模型的效果（当然，其实一般不会调大的，因为默认的1已经是一个很大的学习率了）。而当其小于1时，会减慢学习速度，但是由于每一个弱学习器的贡献变小了，这也会使得模型变得跟精细，适合用于精调。

下面我们来看看AdaBoost的demo，首先划分数据

# 提取特征与标签
data = pd.DataFrame(wine.data)
data.columns = wine.feature_names
target = pd.DataFrame(wine.target)
target.columns = ['class']
# 划分训练集与测试集
Xtrain, Xtest, Ytrain, Ytest = train_test_split(data, target, test_size=0.2)

然后进行建模

# AdaBoost
clf = AdaBoostClassifier(base_estimator=DecisionTreeClassifier(max_depth=2)
                         , n_estimators=100
                         , learning_rate=0.5
                         , algorithm='SAMME.R'
                         , random_state=1008)
clf.fit(Xtrain, Ytrain)
clf.score(Xtest, Ytest)

当然，AdaBoost也继承了一些基础模型的属性，例如

clf.feature_importances_  # 特征重要性
clf.classes_  # 类标签
clf.n_classes_  # 类数量

回归

对于回归问题，使用AdaBoostRegressor函数，其使用的是我们上文讲过的AdaBoost.R2算法，其参数列表为，其大多数参数同分类问题

参数	说明
base_estimator	弱学习器
n_estimators	训练次数
learning_rate	学习率
loss	损失函数，可填**{‘linear’, ‘square’, exponential}，默认为’linear’**。分别对应我们上文提到的三种误差计算方式。
random_state	随机数种子

下面我们跑一个demo

# 提取特征与标签
data = pd.DataFrame(boston.data)
data.columns = boston.feature_names
target = pd.DataFrame(boston.target)
target.columns = ['MEDV']
# 划分训练集与测试集
Xtrain, Xtest, Ytrain, Ytest = train_test_split(data, target, test_size=0.2)

# AdaBoost
clf = AdaBoostRegressor(base_estimator=DecisionTreeRegressor(max_depth=4)
                       , n_estimators=100
                       , learning_rate=0.5
                       , random_state=1008)
clf.fit(Xtrain, Ytrain)
clf.score(Xtest, Ytest)

总结

本文介绍了AdaBoost算法的原理，从最初的二分类问题开始，到解决多分类问题的SAEEM与SAEEM.R算法，再到解决回归问题的AdaBoost.R2算法，并介绍其sklearn代码实现。