Boosting算法族一 Adaboost

发表于 | 分类于

前言

Boosting 是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本受到更多关注，然后基于调整过后的分布来训练下一个基学习器，如此反复进行，直到基学习器数目达到事先指定的值 \(T\) ,最终将这 \(T\) 个基学习器进行加权组合。

加法模型和向前分布算法

Boosting算法族的基本特点是:

  • 1.加法模型
  • 2.向前分步算法

加法模型的意思是最终得到的模型，是若干个基函数的加和。

\[f(x) = \sum_{m=1}^{M}\beta_mb(x;\gamma_m)\]

其中，\(b(x;\gamma_m)\) 称为基函数，\(\gamma_m\) 为第 \(ｍ\) 个基函数的参数，\(\beta_m\) 为基函数的系数。

在给定训练数据和损失函数 \(L(y,f(x))\) 的条件下学习加法模型 \(f(x)\) 就成为风险极小化问题，即损失函数极小化问题

\[\min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L(y_i, \sum_{m=1}^{M}\beta_mb(x_i;\gamma_m))\]

随后该问题可以简化为:　从前向后，每一步只学习一个基函数及其系数，逐渐逼近上式，即: 每步只优化如下损失函数:

\[ \min_{\beta, \gamma} \sum_{i=1}^{N}L(y_i, \beta b(x_i;\gamma))\]

输入: \(T=\{\}\)
损失函数: \(L(y,f(x))\)
基函数集: \(\{b(x;\gamma)\}\) 输出: 加法模型 \(f(x)\)
算法步骤:
  初始化 \(f_0(x)=0\)
  for \(m=1, 2, 3, ... ,M\) do
    极小化损失函数 \(\arg\min_{\beta,\gamma}\sum_{i=1}^{N}L(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))\)
    更新 \(f_m(x) = f_{m-1}(x) + \beta_m b(x;\gamma_m)\)
  end for
输出: 加法模型 \(f(x)=f_M(x)=\sum_{m=1}^{M}\beta_m b(x;\gamma_m)\)

向前分布算法是加法模型的一个学习方法。

AdaBoost

AdaBoost 算法

AdaBoost 是Boosting家族一个比较著名的代表。基本算法如下（其中 \(y_i \in \{-1, +1\}\)，\(f\) 是真实函数）:

输入: 训练集 \(D=\{({\boldsymbol x}_1,y_1),({\boldsymbol x}_2,y_2),...,({\boldsymbol x}_m,y_m)\}\)
    基学习算法 \(\mathfrak{L}\)
    训练轮数 \(T\)
过程:
\(\mathcal{D}_1 = \frac{1}{m}\)
for \(t=1,2,...,T\) do
   \(h_t=\mathfrak{L}(D, \mathcal{D}_t)\)
   \(\epsilon_t=P_{x\sim\mathcal{D}_t}(h_t({\boldsymbol x}) \neq f(\boldsymbol x))\)
   if \(\epsilon_t > 0.5\) then break
   \(\alpha_t=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t})\)
   \(\begin{aligned} \mathcal{D}_{t+1}({\boldsymbol x}) = \frac{\mathcal{D}_t({\boldsymbol x})}{Z_t} \times\begin{cases} exp(-\alpha_t) \quad if h_t(\boldsymbol x) = f(\boldsymbol x)\\ exp(\alpha_t) \quad if h_t(\boldsymbol x) \neq f(\boldsymbol x) \end{cases} = \frac{\mathcal{D}_t({\boldsymbol x})exp(-\alpha_t f({\boldsymbol x})h_t({\boldsymbol x}))}{Z_t} \end{aligned}\)
end for
输出: \(H(\boldsymbol x)=sign(\sum_{t=1}^{T}\alpha_th_t({\boldsymbol x}))\)

Adaboost 算法的推导

AdaBoost 训练学习器的线性组合 \[ H(\boldsymbol{x})=\sum_{t=1}^{T}\alpha_th_t(\boldsymbol{x}) \tag{1} \] 来最小化指数损失函数 (exponential loss function) \[ \ell_{exp}(H|\mathcal{D})=\mathbb{E}_{x\sim\mathcal{D}} [e^{-f(\boldsymbol{x})H(\boldsymbol{x})}] \tag{2} \] 若 \(H(\boldsymbol{x})\) 能另指数损失函数最小化，则考虑式 \((2)\) 对 \(H(\boldsymbol{x})\) 的偏导 \[ \frac{\partial\ell_{exp}(H|\mathcal{D})}{\partial H(\boldsymbol{x})}=-e^{-H(\boldsymbol{x})}P(f(\boldsymbol{x})=1|\boldsymbol{x})+e^{H(\boldsymbol{x})}P(f(\boldsymbol{x}) = -1 | \boldsymbol{x}) \tag{3} \] 另式 \((3)\) 为零可解得 \[ H(\boldsymbol{x})=\frac{1}{2}ln\frac{P(f(\boldsymbol{x})=1|\boldsymbol{x})}{P(f(\boldsymbol{x}) = -1 | \boldsymbol{x})} \tag{4} \] 因此，有 \[ \begin{aligned} sign(H(\boldsymbol{x}))&=sign(\frac{1}{2}ln\frac{P(f(\boldsymbol{x})=1|\boldsymbol{x})}{P(f(\boldsymbol{x}) = -1 | \boldsymbol{x})})\\ &= \begin{cases} 1 &\quad P(f(\boldsymbol{x})=1|\boldsymbol{x}) > P(f(\boldsymbol{x})=-1|\boldsymbol{x}) \\ -1 &\quad P(f(\boldsymbol{x})=1|\boldsymbol{x}) < P(f(\boldsymbol{x})=-1|\boldsymbol{x}) \end{cases} \\ &= \arg\min_{\mathcal{y}\in\{-1.1\}}P(f({x})=y|\boldsymbol{x}) \end{aligned} \tag{5} \] 这意味着 \(sign(H(\boldsymbol{x}))\) 达到了贝叶斯最优错误率。换言之，若指数函数最小化，则分类错误率也将最小化。这说明指数损失函数是分类任务原本 \(0/1\) 损失函数的一致的 (consistent) 替代损失函数。该函数连续可微，数学性质更好，因此我们用它替代 \(0/1\) 损失函数作为优化目标。

在AdaBoost算法中，关于 \(\alpha_t\) ，\(h_t\) 基于 \(\mathcal{D}_t\) 产生后，该基分类器权重 \(\alpha_t\) 应使 \(\alpha_th_t\) 最小化损失函数。 \[ \begin{aligned} \ell_{exp}(\alpha_th_t|\mathcal{D}_t)&=\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t}[e^{-f(\boldsymbol{x})\alpha_th_t(\mathcal{x})}] \\ &=\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t}[e^{-\alpha_t}\mathbb{I}(f(\boldsymbol{x})=h_t(\boldsymbol{x}))+e^{\alpha_t}\mathbb{I}(f(\boldsymbol{x})\neq h_t(\boldsymbol{x}))] \\ &=e^{-\alpha_t}P_{\boldsymbol{x}\sim\mathcal{D}_t}(f(\boldsymbol{x})=h_t(\boldsymbol{x})) + e^{\alpha_t}P_{\boldsymbol{x}\sim\mathcal{D}_t}(f(\boldsymbol{x})\neq h_t(\boldsymbol{x}))\\ &=e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t \end{aligned} \tag{6} \] 其中 \(\epsilon_t=P_{\boldsymbol{x}\sim\mathcal{D}_t}(h_t(\boldsymbol{x})\neq f(\boldsymbol{x})\) 则其导数 \[ \frac{\partial\ell_{exp}(\alpha_th_t|\mathcal{D}_t)}{\partial\alpha_t}=-e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t \tag{7} \] 令其为零可得到算法中的权重更新公式 \[ \alpha_t=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t}) \tag{8} \] AdaBoost 在获取 \(H_{t-1}\) 之后样本分布将进行调整，使下一轮的 \(h_t\) 能够纠正 \(H_{t-1}\) 的全部错误，即最小化 \[ \begin{aligned} \ell_{exp}(H_{t-1}+h_t|\mathcal{D}) &= \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}} [e^{-f(\boldsymbol{x})(H_{t-1}(\boldsymbol{x}) + h_t(\boldsymbol{x}))}]\\ &=\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}e^{-f(\boldsymbol{x})h_t(\boldsymbol{x}))}] \end{aligned} \tag{9} \] 注意到 \(f^2(\boldsymbol{x})=h_t^2(\boldsymbol{x})=1\)，则对 \(e^{-f(\boldsymbol{x})h_t(\boldsymbol{x}))}\) 进行泰勒展开。 \[ \begin{aligned} \ell_{exp}(H_{t-1}+h_t|\mathcal{D}) &\simeq \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}(1-f(\boldsymbol{x})h_t(\boldsymbol{x})+\frac{f^2(\boldsymbol{x})h_t^2(\boldsymbol{x})}{2})]\\ &=\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}(1-f(\boldsymbol{x})h_t(\boldsymbol{x})+\frac{1}{2})] \end{aligned} \tag{10} \] 于是，理想的基学习器 \[ \begin{aligned} h_t(\boldsymbol{x}) &=\mathop{\arg\min}_{h}\ell_{exp}(H_{t-1}+h|\mathcal{D})\\ &=\mathop{\arg\min}_{h}\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}(1-f(\boldsymbol{x})h(\boldsymbol{x})+\frac{1}{2})]\\ &=\mathop{\arg\max}_{h} \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})} f(\boldsymbol{x})h(\boldsymbol{x})]\\ &=\mathop{\arg\max}_{h} \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[\frac{e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}]} f(\boldsymbol{x})h(\boldsymbol{x})] \end{aligned} \tag{11} \] \(\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}]\) 为常数，令 \(\mathcal{D}_t\) 表示一个分布 \[ \mathcal{D}_t(\boldsymbol{x}) = \frac{\mathcal{D}(\boldsymbol{x})e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}]} \tag{12} \] 由数学期望的定义，其等价于令 \[ \begin{aligned} h_t(\boldsymbol{x})&=\arg\max_h \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[\frac{e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}]} f(\boldsymbol{x})h(\boldsymbol{x})] \\ &=\arg\max_h \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t}[f(\boldsymbol{x})h(\boldsymbol{x})] \end{aligned} \tag{13} \] 由于 \(f(\boldsymbol{x})h(\boldsymbol{x} \in \{-1, +1\})\) ，有 \[ f(\boldsymbol{x})h(\boldsymbol{x})=1-2\mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x})) \tag{14} \] 则理想的基学习器 \[ h_t(\boldsymbol{x})=\arg\min_h \mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}_t} [\mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x}))] \tag{15} \] 由此可见，理想的基学习器 \(h_t(x)\) 能在 \(\mathcal{D}_t\) 下最小化误差。因此弱分类器应基于分布 \(\mathcal{D}_t\) 训练，且分类误差应小于 \(0.5\) 。这在一定程度上类似于“残差逼近”的思想，考虑到 \(\mathcal{D}_t\) 与 \(\mathcal{D}_{t+1}\) 的关系，有 \[ \begin{aligned} \mathcal{D}_{t+1}(\boldsymbol{x}) &= \frac{\mathcal{D}(\boldsymbol{x})e^{-f(\boldsymbol{x})H_{t}(\boldsymbol{x})}} {\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t}(\boldsymbol{x})}]}\\ &= \frac{\mathcal{D}(\boldsymbol{x})e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}e^{-f(\boldsymbol{x})\alpha_th_t(\boldsymbol{x})}} {\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t}(\boldsymbol{x})}]}\\ &=\mathcal{D}_{t}(\boldsymbol{x})e^{-f(\boldsymbol{x})\alpha_th_t(\boldsymbol{x})} \frac{\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}]} {\mathbb{E}_{\boldsymbol{x}\sim\mathcal{D}}[e^{-f(\boldsymbol{x})H_{t}(\boldsymbol{x})}]} \end{aligned} \tag{16} \] 即为算法中的样本分布更新公式。

于是由式 \((8)\) 和 式 \((16)\) 可见，我们从基于加法模型分步向前优化指数损失函数的角度推导出了AdaBoost算法。

算法特性

AdaBoost算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法” (re-weighting) 实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。需要注意的是Boosting学习器在每一轮训练都要检查当前生成的基学习器是否满足基本条件 (例如AdaBoost每一轮都要检测基学习器是否比随机猜测好)，一旦条件不满足当前基学习器即被抛弃，且学习过程停止。

从偏差-方差分解的角度看，Boosting算发主要关注降低偏差，因此Boosting算法族能基于泛化能力相当弱的学习器构建出来很强的集成。

参考文献