浏览本文须要的背景知识点：集成学习、拉格朗日乘数法、一丢丢编程常识

一、引言

  后面一节咱们学习了随机森林算法（Random Forest Algorithm），讲到了其中一种集成学习的办法——Bagging 算法，这一节咱们来学习另一种集成学习的办法——晋升算法 )¹（Boosting Algorithm），同时介绍其中比拟常见的算法——自适应加强算法 ²（Adaptive Boosting Algorithm / AdaBoost Algorithm）

二、模型介绍

Boosting 算法

  Boosting 算法也是一种集成学习，与 Bagging 算法不同的是，每次训练更关注训练出的预计器中分类谬误或者回归误差大的样本，即每次训练都是依据上次训练的后果调整不同的样本权重，直到最初的输入小于预设的阈值。

图 2 -1

  图 2-1 展现了提醒算法的具体流程，其与 Bagging 算法的区别在于：其一，Bagging 算法的每个预计器绝对独立且权重都雷同，而 Boosting 算法的每个预计器都依赖于上一个预计器同时权重也不同。其二，个别状况下 Bagging 算法能够减小方差、而 Boosting 算法则是减小偏差。

  Boosting 算法中比拟有代表性的算法就是自适应加强算法（Adaptive Boosting Algorithm / AdaBoost Algorithm）

AdaBoost 算法

  AdaBoost 算法是由 Yoav Freund 和 Robert E. 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。

AdaBoost 算法步骤如下：

<hr/>

初始化样本权重向量 ω_1

$$
\begin{aligned}
\omega_{1,i} &= \frac{1}{N} \quad i = 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 \ne h_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_i h_i(x)\right)
\end{aligned}
$$

<hr/>

多分类

  假如训练集 T = {X_i, y_i}，i = 1，…，N，y 的取值有 M 种可能，h(x) 为预计器，预计器的数量为 K。

AdaBoost-SUMME 算法步骤如下：

<hr/>

初始化样本权重向量 ω_1

$$
\begin{aligned}
\omega_{1,i} &= \frac{1}{N} \quad i = 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 \ne h_k(X_i))
\end{aligned}
$$

  计算第 k 次的预计器权重 α_k

$$
\begin{aligned}
\alpha_k &= \ln \frac{1 – e_k}{e_k} + \ln (M – 1) \\
\end{aligned}
$$

  计算第 k+1 次的权重向量 ω_{k+1}

$$
\begin{aligned}
\bar{\omega_{k+1,i}} &= \omega_{k,i}e^{\alpha_kI(y_i \ne h_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_i I(h_i(x) = m) \right)
\end{aligned}
$$

<hr/>

AdaBoost-SUMME.R 算法步骤如下：

<hr/>

初始化样本权重向量 ω_1

$$
\begin{aligned}
\omega_{1,i} &= \frac{1}{N} \quad i = 1,…,N
\end{aligned}
$$

遍历预计器的数量 K 次：

  在样本权重 ω_k 下计算加权类概率预计向量 P_k

$$
\begin{aligned}
p_k^m(x) = P(y = m \mid x)
\end{aligned}
$$

   计算第 k+1 次的权重向量 ω_{k+1}

$$
\hat{y} = \left\{
\begin{array}{c}
1 & y =m\\
-\frac{1}{M-1} & y \ne m
\end{array}\right. \quad m = 1,\dots,M
$$

$$
\begin{aligned}
\bar{\omega_{k+1,i}} &= \omega_{k,i}e^{-\frac{M-1}{M} \hat{y_i}^T \ln p_k(x) }
\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_k(x) &= (M – 1) \left(\ln p_k^m(x) – \frac{1}{M} \sum_{i = 1}^{M} \ln p_k^i(x) \right) \\
H(x) &= \underset{m}{\operatorname{argmax}} \left(\sum_{i = 1}^{K} h_i(x)\right)
\end{aligned}
$$

<hr/>

回归

  假如训练集 T = {X_i, y_i}，i = 1，…，N，h(x) 为预计器，预计器的数量为 K

AdaBoost.R2 算法步骤如下：

<hr/>

初始化样本权重向量 ω_1

$$
\begin{aligned}
\omega_{1,i} &= \frac{1}{N} \quad i = 1,…,N
\end{aligned}
$$

遍历预计器的数量 K 次：

  在样本权重 ω_k 下训练预计器 h(x)

  计算最大误差 E_k

$$
\begin{aligned}
E_k &= \max \mid y_i – h_k(X_i) \mid
\end{aligned}
$$

  计算第 k 次的误差率 e_k

$$
\begin{aligned}
e_{k,i} &= \frac{\mid y_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{\mid y_i – h_k(X_i) \mid}{E_k} } & 指数误差 \\
e_k & = \sum_{i = 1}^{N}\omega_{k,i} e_{k,i}
\end{aligned}
$$

  如果误差率 e_k 大于 0.5

    中断循环

  计算第 k 次的预计器权重 α_k

$$
\begin{aligned}
\alpha_k &= \frac{e_k}{1 – e_k}
\end{aligned}
$$

  计算第 k+1 次的权重向量 ω_{k+1}

$$
\begin{aligned}
\bar{\omega_{k+1,i}} &= \omega_{k,i}\alpha_k^{1 – e_{k,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) &= \inf \left\{y \in A: \sum_{h_i(x) \le y } \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}
$$

<hr/>

四、原理证实

AdaBoost 算法推导

  同算法步骤中的前提条件一样，假如训练集 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_i h_i(x) & (1) \\
H_k(x) &= \sum_{i = 1}^{k} \alpha_i h_i(x) & (2) \\
H_k(x) &= H_{k-1}(x) + \alpha_k h_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) + \alpha h(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) + \alpha h(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\alpha h(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\alpha h_k(X_i)} & (1) \\
Cost(\alpha) &= \sum_{i = 1}^{N} \bar{\omega_{k,i}} e^{-y_i\alpha h_k(X_i)} & (2) \\
&= \sum_{y_i = h_k(X_i)}^{N} \bar{\omega_{k,i}} e^{-\alpha} + \sum_{y_i \ne h_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 \ne h_k(X_i)}^{N} \bar{\omega_{k,i}} e^{-\alpha} – \sum_{y_i \ne h_k(X_i)}^{N} \bar{\omega_{k,i}} e^{-\alpha} + \sum_{y_i \ne h_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 \ne h_k(X_i)) & (5) \\
\end{aligned}
$$

式 4 -3

（1）对代价函数求导数并令其为零

（2）定义错误率 e_k 的表达式

（3）将错误率 e_k 带入（2）式

（4）两边同时乘以 exp(α)

（5）移项后整顿得

（6）求得最初的预计器权重 α 的表达式

$$
\begin{aligned}
\frac{\partial Cost(\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 \ne h_k(X_i)) = 0& (1) \\
e_k &= \frac{\sum_{i = 1}^{N}\bar{\omega_{k,i}} I(y_i \ne h_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 \ne h_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 \ne h_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} C e^{-y_i\alpha_kh_k(X_i)}}{\sum_{j = 0}^N \left(\omega_{k,j} C e^{-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 \ne h_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_i h_i(x)\right) & (4) \\
\end{aligned}
$$

式 4 -8

AdaBoost-SAMME 算法推导

  同算法步骤中的前提条件一样，假如训练集 T = {X_i, y_i}，i = 1，…，N，y 的取值有 M 种可能，h(x) 为预计器，预计器的数量为 K。

  为了适应多分类问题，AdaBoost-SAMME 算法将本来为数值的标签 y 转化成一个向量的模式，如式 4-9 所示：

$$
\hat{y} = \left\{
\begin{array}{c}
1 & y =m\\
-\frac{1}{M-1} & y \ne m
\end{array}\right. \quad m = 1,\dots,M
$$

式 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 \ne m
\end{array}\right. \quad m = 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) + \alpha h_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\alpha h_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\alpha h_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 \ne h_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\alpha h_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 \ne h_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 \ne h_k(X_i)}^{N} \bar{\omega_{k,i}} e^{-\frac{\alpha}{M-1}} – \sum_{\hat{y}_i \ne h_k(X_i)}^{N} \bar{\omega_{k,i}} e^{-\frac{\alpha}{M-1}} + \sum_{\hat{y}_i \ne h_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 \ne h_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{\partial Cost(\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 \ne h_k(X_i)) = 0& (1) \\
e_k &= \frac{\sum_{i = 1}^{N}\bar{\omega_{k,i}} I(y_i \ne h_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

  式 4-16 中预计器权重 α 的表达式后面的常数在进过归一化后对后果没有影响，前面的样本权重更新的公式一样也是简化后的后果。更多具体的算法阐明请参考原始论文——Multi-class AdaBoost⁷

AdaBoost-SAMME.R 算法推导

  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)) } \mid x) \\
s.t. \quad h_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)) } \mid x) & (1) \\
&= E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x) } \mid x) & (2) \\
&= E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x) } I(y = 1) \mid x) + \cdots + E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x) } I(y = M) \mid x) & (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}_i H_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x) } I(y = 1) \mid x) &= E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)}e^{-\frac{h^1(x)}{M-1} } I(y = 1) \mid x) & (1) \\
&= e^{-\frac{h^1(x)}{M-1}} E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)} I(y = 1) \mid x) & (2) \\
P(y = 1 | x) &= E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)} I(y = 1) \mid x) & (3) \\
E(e^{-\frac{1}{M} \hat{y}_i H_{k-1}(x)}e^{-\frac{1}{M}\hat{y}_ih(x) } I(y = m) \mid x) &= 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{\partial L(h(x), \lambda)}{\partial h^1(x)} &= -\frac{1}{M-1} e^{-\frac{h^1(x)}{M-1}} P(y = 1 | x) – \lambda = 0 \\
\frac{\partial L(h(x), \lambda)}{\partial h^2(x)} &= -\frac{1}{M-1} e^{-\frac{h^2(x)}{M-1}} P(y = 2 | x) – \lambda = 0 \\
& \cdots \\
\frac{\partial L(h(x), \lambda)}{\partial h^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} + \ln P(y = 1 | x) &= -\frac{h^2(x)}{M-1} + \ln P(y = 2 | x) & (2) \\
h^1(x) – h^2(x) &= (M – 1) (\ln P(y = 1 | x) – \ln P(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) (\ln P(y = 1 | x) – \ln P(y = 2 | x)) & (1) \\
h^1(x) – h^3(x) &= (M – 1) (\ln P(y = 1 | x) – \ln P(y = 3 | x)) & (2) \\
& \cdots \\
h^1(x) – h^M(x) &= (M – 1) (\ln P(y = 1 | x) – \ln P(y = M | x)) & (3) \\
(M – 1) h^1(x) – (-h^1(x)) &= (M – 1)((M – 1)\ln P(y = 1 | x) – \sum_{m \ne 1} \ln P(y = m | x))) & (4) \\
Mh^1(x) &= (M – 1)(M\ln P(y = 1 | x) – \sum_{m = 1}^{M} \ln P(y = m | x)) & (5) \\
h^1(x) &= (M – 1)(\ln P(y = 1 | x) – \frac{1}{M} \sum_{m = 1}^{M} \ln P(y = m | x)) & (6) \\
\end{aligned}
$$

式 4 -26

  同理可得 h(x) 各个重量的后果

$$
\begin{aligned}
h^m(x) &= (M – 1)(\ln P(y = m | x) – \frac{1}{M} \sum_{m^{‘} = 1}^{M} \ln P(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\ln p_k(X_i)} & (3) \\
\end{aligned}
$$

式 4 -28

  这样就失去了算法步骤中的样本权重的更新公式，更多具体的算法阐明也请参考原始论文——Multi-class AdaBoost⁷

五、代码实现

应用 Python 实现 AdaBoost 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostc():
    """AdaBoost 分类算法"""

    def __init__(self, n_estimators = 100):
        # AdaBoost 弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """AdaBoost 分类算法拟合"""
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 预计器数组
        estimators = []
        # 预计器权重数组
        weights = []
        # 遍历预计器
        for i in range(self.n_estimators):
            # 初始化最大深度为 1 的决策树预计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 依照样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测训练集
            y_predict = estimator.predict(X)
            # 计算误差率
            e = np.sum(sample_weights[y_predict != y])
            # 当误差率大于等于 0.5 时跳出循环
            if e >= 0.5:
                self.n_estimators = i
                break
            # 计算预计器权重
            weight = 0.5 * np.log((1 - e) / e)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.exp(- weight * np.multiply(y, y_predict)))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = weights
        self.estimators = estimators

    def predict(self, X):
        """AdaBoost 分类算法预测"""
        y = np.zeros(X.shape[0])
        # 遍历预计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            weight = self.weights[i]
            # 预测后果
            predicts = estimator.predict(X)
            # 依照预计器的权重累加
            y += weight * predicts
        # 依据权重的正负号返回后果
        return np.sign(y)

应用 Python 实现 AdaBoost-SAMME 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostmc():
    """AdaBoost 多分类 SAMME 算法"""

    def __init__(self, n_estimators = 100):
        # AdaBoost 弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """AdaBoost 多分类 SAMME 算法拟合"""
        # 标签分类
        self.classes = np.unique(y)
        # 标签分类数
        self.n_classes = len(self.classes)
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 预计器数组
        estimators = []
        # 预计器权重数组
        weights = []
        # 遍历预计器
        for i in range(self.n_estimators):
            # 初始化最大深度为 1 的决策树预计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 依照样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 训练集预测后果
            y_predict = estimator.predict(X)
            incorrect = y_predict != y
            # 计算误差率
            e = np.sum(sample_weights[incorrect])
            # 计算预计器权重
            weight = np.log((1 - e) / e) + np.log(self.n_classes - 1)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.exp(weight * incorrect))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = weights
        self.estimators = estimators

    def predict(self, X):
        """AdaBoost 多分类 SAMME 算法预测"""
        # 加权后果汇合
        results = np.zeros((X.shape[0], self.n_classes))
        # 遍历预计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            weight = self.weights[i]
            # 预测后果
            predicts = estimator.predict(X)
            # 遍历标签分类
            for j in range(self.n_classes):
                # 对应标签分类的权重累加
                results[predicts == self.classes[j], j] += weight
        # 取加权最大对应的分类作为最初的后果
        return self.classes.take(np.argmax(results, axis=1), axis=0)

应用 Python 实现 AdaBoost-SAMME.R 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostmcr():
    """AdaBoost 多分类 SAMME.R 算法"""

    def __init__(self, n_estimators = 100):
        # AdaBoost 弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """AdaBoost 多分类 SAMME.R 算法拟合"""
        # 标签分类
        self.classes = np.unique(y)
        # 标签分类数
        self.n_classes = len(self.classes)
        # 初始化样本权重
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 预计器数组
        estimators = []
        # 论文中对 y 的定义
        y_codes = np.array([-1. / (self.n_classes - 1), 1.])
        # 将训练集中的标签值转换成论文中的矩阵模式
        y_coding = y_codes.take(self.classes == y[:, np.newaxis])
        # 遍历预计器
        for i in range(self.n_estimators):
            # 初始化最大深度为 1 的决策树预计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 依据样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测训练集标签值的概率
            y_predict_proba = estimator.predict_proba(X)
            # 解决概率为 0 的后果，防止取对数是后果为负无穷大的问题
            np.clip(y_predict_proba, np.finfo(y_predict_proba.dtype).eps, None, out=y_predict_proba)
            # 计算样本权重
            temp_weights = sample_weights * np.exp(- ((self.n_classes - 1) / self.n_classes) * np.sum(np.multiply(y_coding, np.log(y_predict_proba)), axis=1))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            estimators.append(estimator)
        self.estimators = estimators

    def predict(self, X):
        """AdaBoost 多分类 SAMME.R 算法预测"""
        # 后果汇合
        results = np.zeros((X.shape[0], self.n_classes))
        # 遍历预计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            # 预测标签值的概率
            y_predict_proba = estimator.predict_proba(X)
            # 同样须要解决零概率的问题
            np.clip(y_predict_proba, np.finfo(y_predict_proba.dtype).eps, None, out=y_predict_proba)
            # 对概率取对数
            y_predict_proba_log = np.log(y_predict_proba)
            # 计算 h(x)
            h = (self.n_classes - 1) * (y_predict_proba_log - (1 / self.n_classes) * np.sum(y_predict_proba_log, axis=1)[:, np.newaxis])
            # 累加
            results += h
        # 取累加最大对应的分类作为最初的后果
        return self.classes.take(np.argmax(results, axis=1), axis=0)

应用 Python 实现 AdaBoost.R2 算法

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class adaboostr():
    """AdaBoost 回归算法"""

    def __init__(self, n_estimators = 100):
        # AdaBoost 弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """AdaBoost 回归算法拟合"""
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 预计器数组
        estimators = []
        # 预计器权重数组
        weights = []
        # 遍历预计器
        for i in range(self.n_estimators):
            # 初始化最大深度为 3 的决策树预计器
            estimator = DecisionTreeRegressor(max_depth = 3)
            # 依据样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测后果
            y_predict = estimator.predict(X)
            # 计算误差向量（线性误差）errors = np.abs(y_predict - y)
            errors = errors / np.max(errors)
            # 计算误差率
            e = np.sum(np.multiply(errors, sample_weights))
            # 当误差率大于等于 0.5 时跳出循环
            if e >= 0.5:
                self.n_estimators = i
                break
            # 计算预计器权重
            weight = e / (1 - e)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.power(weight, 1 - errors))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = np.array(weights)
        self.estimators = np.array(estimators)

    def predict(self, X):
        """AdaBoost 回归算法预测"""
        # 论文中权重的定义
        weights = np.log(1 / self.weights)
        # 预测后果矩阵
        predictions = np.array([self.estimators[i].predict(X) for i in range(self.n_estimators)]).T
        # 依据预测后果排序后的下标
        sorted_idx = np.argsort(predictions, axis=1)
        # 依据排序后果顺次累加预计器权重，失去新的累积权重矩阵，相似累积散布函数的定义
        weight_cdf = np.cumsum(weights[sorted_idx], axis=1, dtype=np.float64)
        # 累积权重矩阵中大于其中中位数的后果
        median_or_above = weight_cdf >= 0.5 * weight_cdf[:, -1][:, np.newaxis]
        # 中位数后果对应的下标
        median_idx = median_or_above.argmax(axis=1)
        # 对应的预计器
        median_estimators = sorted_idx[np.arange(X.shape[0]), median_idx]
        # 取对应的预计器的预测后果作为最初的后果
        return predictions[np.arange(X.shape[0]), median_estimators]

六、第三方库实现

scikit-learn³ 实现自适应加强分类

from sklearn.ensemble import AdaBoostClassifier

# 自适应加强分类器 SAMME 算法
clf = AdaBoostClassifier(n_estimators = 50, random_state = 0, algorithm = "SAMME")
# 自适应加强分类器 SAMME.R 算法
clf = AdaBoostClassifier(n_estimators = 50, random_state = 0, algorithm = "SAMME.R")
# 拟合数据集
clf = clf.fit(X, y)

scikit-learn⁴ 实现自适应加强回归

from sklearn.ensemble import AdaBoostRegressor

# 自适应加强回归器
clf = AdaBoostRegressor(n_estimators = 50, random_state = 0)
# 拟合数据集
clf = clf.fit(X, y)

七、示例演示

  图 7-1 展现了应用自适应加强算法进行二分类的后果，红色示意标签值为 -1 的样本点，蓝色代表标签值为 1 的样本点。浅红色的区域为预测值为 -1 的局部，浅蓝色的区域则为预测值为 1 的局部

<center> 图 7 -1</center>

  图 7-2、图 7-3 别离展现了应用 SAMME 和 SAMME.R 算法进行多分类的后果，红色示意标签值为 0 的样本点，蓝色代表标签值为 1 的样本点，绿色代表标签值为 2 的样本点。浅红色的区域为预测值为 0 的局部，浅蓝色的区域则为预测值为 1 的局部，浅绿色的区域则为预测值为 1 的局部

<center> 图 7 -2</center>

<center> 图 7 -3</center>

  图 7-4 展现了应用自适应加强算法进行回归的后果

图 7 -4

八、思维导图

图 8 -1

九、参考文献

1. https://en.wikipedia.org/wiki…(machine_learning)
2. https://en.wikipedia.org/wiki…
3. https://scikit-learn.org/stab…
4. https://scikit-learn.org/stab…
5. https://www.face-rec.org/algo…
6. https://citeseer.ist.psu.edu/…
7. https://hastie.su.domains/Pap…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正

本文首发于——AI 导图 ，欢送关注