Question

1. 提升方法(boosting) 是一种常用的统计学习方法。在分类问题中，它通过改变训练样本的权重学习多个分类器，并将这些分类器们进行线性组合来提高分类的能力。

2. 提升方法的基本思想是：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断要好。类似于”三个臭皮匠顶一个诸葛亮“。

3. 提升方法的理论基础是：强可学习与弱可学习是等价的。

   在概率近似正确（probably approximately correct,PAC）学习的框架下：

   • 强可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它并且正确率很高，那么称这个概念是强可学习的。
   • 弱可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么称这个概念是弱可学习的。

   可以证明：强可学习与弱可学习是等价的。

   即：若在学习中发现了 ”弱学习算法“ ，则可以通过某些办法将它提升为 ”强学习算法“。

4. 对于分类问题而言，求一个比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）要容易得多。

5. Boosting 就是一族可以将弱学习器提升为强学习器的算法。

   这族算法的工作原理类似：

   • 先从初始训练集训练出一个基学习器。
   • 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注。
   • 然后基于调整后的样本分布来训练下一个基学习器。
   • 如此重复，直到基学习器数量达到事先指定的值M 。
   • 最终将这M个基学习器进行加权组合。

2.1 AdaBoost 算法

1. Boosting族算法最著名的代表是AdaBoost算法。

2. AdaBoot算法两个核心步骤：

   • 每一轮中如何改变训练数据的权值？

     AdaBoost算法提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

     于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。

   • 最后如何将一系列弱分类器组合成一个强分类器？

     AdaBoost 采用加权多数表决的方法：

     • 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
     • 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

3. AdaBoost算法有两个特点：

   • 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用。

     • 因此AdaBoost要求基本学习器能够对特定的数据分布进行学习，这一般是在学习的时候为每个训练样本赋予一个权重。
     • 对于无法接受带权样本的基本学习算法，则可以通过“重采样法”来处理：即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样的样本集对基本学习器进行训练。
     • 一般而言这两者没有显著的优劣差别。

   • 利用基本分类器的线性组合 $ MathJax-Element-60 $ 构成最终分类器：

     $ H(\mathbf {\vec x})=\text{sign}(f(\mathbf {\vec x}))=\text{sign}\left(\sum_{m=1}^{M}\alpha_mh_m(\mathbf {\vec x})\right ) $

     其中：

     • $ MathJax-Element-150 $ 的符号决定实例 $ MathJax-Element-189 $ 的分类。
     • $ MathJax-Element-150 $ 的绝对值表示分类的确信度。

4. AdaBoost 算法具有自适应性，即它能够自动适应弱分类器各自的训练误差率，这也是它的名字（适应的提升）的由来。

2.1.1 算法

1. AdaBoost算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-43 $
     • 弱学习算法

   • 输出：集成分类器 $ MathJax-Element-124 $

   • 算法步骤：

     • 初始化训练数据的权值分布 $ MathJax-Element-125 $ 。

     • 对 $ MathJax-Element-152 $

       • 使用具有权值分布 $ MathJax-Element-127 $ 的训练数据集学习，根据输入的弱学习算法得到基本分类器： $ MathJax-Element-48 $ 。

       • 计算 $ MathJax-Element-133 $ 在训练数据集上的分类误差率： $ MathJax-Element-50 $ 。

         它就是所有误分类点的权重之和。其中权重越大的误差分类点，其在误差率中占比越大。

       • 若 $ MathJax-Element-51 $ ，算法终止，构建失败！

       • 计算 $ MathJax-Element-133 $ 的系数： $ MathJax-Element-53 $ 。

         该系数表示 $ MathJax-Element-133 $ 在集成分类器中的重要性。它是 $ MathJax-Element-134 $ 的单调减函数，说明误差越小的基本分类器，其重要性越高。

         根据系数大于零要求 $ MathJax-Element-56 $ 。

       • 更新训练数据集的权值分布： $ MathJax-Element-135 $ 。其中：

         $ w_{m+1,i}=\frac{w_{m,i}}{Z_m}\exp(-\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i)) $

         $ MathJax-Element-58 $ 为规范化因子，它使得 $ MathJax-Element-137 $ 成为一个概率分布 。

     • 构建基本分类器的线性组合： $ MathJax-Element-60 $ ，于是得到集成分类器： $ MathJax-Element-70 $ 。

2. 为防止过拟合，AdaBoost 通常会加入正则化项。该正则化项称作步长或者学习率，定义为 $ MathJax-Element-62 $ 。

   考虑正则化项之后，模型的更新方式为： $ MathJax-Element-63 $ 。

2.1.2 算法解释

1. AdaBoost 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

   这是通过更新训练数据集的权值分布 $ MathJax-Element-121 $ 来实现的。其中：

   $ w_{m+1,i}=\frac{w_{m,i}}{Z_m}\exp(-\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i))\\ Z_m=\sum_{i=1}^{N}w_{m,i}\exp(-\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i)) $
   • 对于正确分类样本， $ MathJax-Element-65 $ 下一轮权重为： $ MathJax-Element-66 $
   • 对于错误分类样本， $ MathJax-Element-67 $ 下一轮权重为： $ MathJax-Element-68 $

   两者比较，误分类样本的权重是正确分类样本的权重的 $ MathJax-Element-69 $ 倍。于是误分类样本在下一轮学习中权重更大。

2. 集成分类器 $ MathJax-Element-70 $ 结合 $ MathJax-Element-180 $ 个基本分类器的方式为加权表决。

   • 系数 $ MathJax-Element-74 $ 表示了基本分类器 $ MathJax-Element-133 $ 的重要性。其中：

     $ \alpha_m=\frac 12 \log \frac{1-e_m}{e_m}\\ e_m = \sum_{i=1}^{N}w_{m,i}I(h_m(\mathbf{\vec x}_i) \neq \tilde y_i) $

   • 由于 $ MathJax-Element-74 $ 是分类误差率 $ MathJax-Element-134 $ 的单调递减函数，因此：

     • AdaBoost 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
     • AdaBoost 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

2.1.3 误差分析

1. 定理一：AdaBoost算法集成分类器的训练误差上界为：

   $ \frac 1N \sum_{i=1}^{N}I(H(\mathbf{\vec x}_i) \neq \tilde y_i) \le \frac 1N \sum_{i=1}^{N}\exp(-\tilde y_if(\mathbf{\vec x}_i))=\prod_{m=1}^{M}Z_m\\ Z_m=\sum_{i=1}^{N}w_{m,i}\exp(-\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i)) $

   这一定理说明：可以在每一轮选取适当的 $ MathJax-Element-114 $ 使得 $ MathJax-Element-95 $ 最小，从而使得训练误差下降最快。

2. 定理二：二类分类 AdaBoost 的训练误差界：

   $ \prod_{m=1}^{M}Z_m=\prod_{m=1}^{M}\left[2\sqrt{e_m(1-e_m)} \;\right]=\prod_{m=1}^{M}\sqrt{(1-4\gamma_m^{2})} \le \exp(-2\sum_{m=1}^{M}\gamma_m^{2}) $

   其中 $ MathJax-Element-78 $ 。

3. 推论：若存在 $ MathJax-Element-79 $ ，对所有 $ MathJax-Element-80 $ 有 $ MathJax-Element-81 $ ，则有：

   $ \frac 1N \sum_{i=1}^{N}I(H(\mathbf{\vec x}_i)\neq \tilde y_i) \le \exp(-2M\gamma^{2}) $

   这表明在此条件下 AdaBoost 的训练误差是以指数速率下降的。

4. 上述定理都只是关于训练误差的分析，实际应用中更关系测试集的误差。

   AdaBoost 算法也会出现过拟合，此时训练误差为 0 但是测试集的误差较大。

5. 当AdaBoost 的基础分类器比较复杂时，AdaBoost 很容易陷入过拟合。

   但是当AdaBoost 的基础分类器比较简单时，AdaBoost 反而难以陷入过拟合。这也是为什么AdaBoost 的基础分类器经常选择使用树桩的原因。

2.3 AdaBoost 多分类

1. 标准的AdaBoost算法只适用二类分类问题，可以将它推广到多分类问题。 有两种算法：

   • SAMME 算法：该算法不需要个体分类器输出类别的概率。
   • SAMME.R 算法：该算法需要个体分类器输出类别的概率。

2.3.1 SAMME 算法

1. SAMME算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-99 $
     • 弱学习算法

   • 输出：集成分类器 $ MathJax-Element-124 $

   • 算法步骤：

     • 初始化训练数据的权值分布 $ MathJax-Element-84 $ 。

     • 对 $ MathJax-Element-152 $

       • 使用具有权值分布 $ MathJax-Element-127 $ 的训练数据集学习，根据输入的弱学习算法得到基本分类器： $ MathJax-Element-104 $ 。

       • 计算 $ MathJax-Element-133 $ 在训练数据集上的分类误差率： $ MathJax-Element-89 $ 。

       • 计算 $ MathJax-Element-133 $ 的系数： $ MathJax-Element-91 $ 。

         因为系数 $ MathJax-Element-92 $ ，因此要求 $ MathJax-Element-93 $ 。

       • 更新训练数据集的权值分布： $ MathJax-Element-135 $ 。其中：

         $ w_{m+1,i}=\frac{w_{m,i}}{Z_m}\exp\left( -\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i) \right)\\ Z_m=\sum_{i=1}^{N}w_{m,i}\exp(-\alpha_m\tilde y_ih_m(\mathbf{\vec x}_i)) $

         其中 $ MathJax-Element-95 $ 为规范化因子，它使得 $ MathJax-Element-137 $ 成为一个概率分布。

     • 构建基本分类器的线性组合，于是得到集成分类器： $ MathJax-Element-97 $ 。

2. 当 $ MathJax-Element-98 $ 时SAMME算法退化为标准的AdaBoost算法。

2.3.2 SAMME.R算法

1. SAMME.R算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-99 $
     • 弱学习算法

   • 输出：集成分类器 $ MathJax-Element-124 $

   • 算法步骤：

     • 初始化训练数据的权值分布 $ MathJax-Element-125 $ 。

     • 对 $ MathJax-Element-152 $

       • 使用具有权值分布 $ MathJax-Element-127 $ 的训练数据集学习，根据输入的弱学习算法得到基本分类器： $ MathJax-Element-104 $ 。

       • 计算 $ MathJax-Element-133 $ 在训练数据集上的加权概率估计：

         $ p_{m,i}^{(k)}=w_{m,i}p(\tilde y_i=c_k\mid\mathbf {\vec x}_i), i=1,2,\cdots,N;k=1,2,\cdots,K $

         其中：

         • $ MathJax-Element-106 $ 是 $ MathJax-Element-112 $ 的真实标记。
         • $ MathJax-Element-108 $ 是 $ MathJax-Element-112 $ 的权重。
         • $ MathJax-Element-110 $ 刻画基本分类器 $ MathJax-Element-116 $ 预测 $ MathJax-Element-112 $ 的输出为类别 $ MathJax-Element-117 $ 的概率的加权值。
           

       • 对 $ MathJax-Element-114 $ 和类别 $ MathJax-Element-117 $ ，定义：

         $ l_m^{(k)}(\mathbf{\vec x}_i)=(K-1)\left(\log p_{m,i}^{(k)}-\frac 1K\sum_{k'=1}^{K}\log p_{m,i}^{(k')}\right) ,k=1,2,\cdots,K $

         它刻画了： $ MathJax-Element-116 $ 预测的输出类别为 $ MathJax-Element-117 $ 的概率加权值的对数 $ MathJax-Element-118 $ ，距离所有概率加权值对数的均值 $ MathJax-Element-119 $ 的距离。

       • 更新训练数据集的权值分布： $ MathJax-Element-121 $ 。其中：

         $ w_{m+1,i}=w_{m,i}\exp\left(-\frac{K-1}{K} \sum_{k=1}^{K}\delta_{i}^{(k)}\log p_{m,i}^{(k)}\right)\\ \delta_{i}^{(k)}=\begin {cases} 1,& \text{if} \quad \tilde y_i=c_k \\ -\frac {1}{K-1} ,& \text{else} \end{cases} $

       • 归一化训练数据集的权值分布 $ MathJax-Element-121 $ ，使得权值之和为 1 。

     • 构建基本分类器的线性组合，于是得到集成分类器： $ MathJax-Element-122 $ 。

2.4 Adaboost 回归

1. Adaboost 的回归问题有很多变种，这里介绍AdaBoost R2 算法。

2. AdaBoost R2 回归算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-123 $
     • 弱学习算法

   • 输出：集成回归器 $ MathJax-Element-124 $

   • 算法步骤：

     • 初始化训练数据的权值分布 $ MathJax-Element-125 $ 。

     • 对 $ MathJax-Element-152 $

       • 使用具有权值分布 $ MathJax-Element-127 $ 的训练数据集学习，根据输入的弱学习算法得到基本回归器： $ MathJax-Element-128 $ 。

       • 计算 $ MathJax-Element-133 $ 在训练数据集上的误差：

         $ E_m = \max_{\mathbf{\vec x}_i \in \mathbb D}|\tilde y_i - h_m(\mathbf{\vec x}_i)|\\ e_m=\sum_{i=1}^Nw_{m,i}\left(\frac {\tilde y_i - h_m(\mathbf{\vec x}_i) }{E_k}\right)^2 $

         它就是所有样本的回归误差的加权和。

         其中 $ MathJax-Element-130 $ 为误差绝对值的最大值，通过它来对所有的回归误差归一化。

       • 计算 $ MathJax-Element-133 $ 的系数： $ MathJax-Element-132 $ 。

         该系数表示 $ MathJax-Element-133 $ 在集成回归器中的重要性。

         它是 $ MathJax-Element-134 $ 的单调减函数，说明误差越小的基本回归器，其重要性越高。

       • 更新训练数据集的权值分布： $ MathJax-Element-135 $ 。其中：

         $ w_{m+1,i}=\frac{w_{m,i}}{Z_m} \alpha_m^{1-\left(\frac {\tilde y_i - h_m(\mathbf{\vec x}_i) }{E_m}\right)^2}\\ Z_m = \sum_{i=1}^N w_{m,i} \alpha_m^{1-\left(\frac {\tilde y_i - h_m(\mathbf{\vec x}_i) }{E_m }\right)^2} $

         $ MathJax-Element-136 $ 为规范化因子，它使得 $ MathJax-Element-137 $ 成为一个概率分布 。

     • 构建基本回归器的线性组合 ，于是得到集成回归器： $ MathJax-Element-138 $ 。
       

2.5 AdaBoost与加法模型

2.5.1 加法模型

1. AdaBoost 算法可以认为是：模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。

   其中指数损失函数为： $ MathJax-Element-139 $ 。

2. 考虑加法模型 $ MathJax-Element-140 $ ，其中 $ MathJax-Element-141 $ 为基函数、 $ MathJax-Element-142 $ 为基函数的参数、 $ MathJax-Element-143 $ 为基函数的系数。

   给定训练数据以及损失函数 $ MathJax-Element-148 $ 的条件下，根据经验风险极小化（即：损失函数极小化）准测来学习加法模型 $ MathJax-Element-150 $ ：

   $ \min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L\left(\tilde y_i,\sum_{m=1}^{M}\beta_mb(\mathbf {\vec x};\gamma_m)\right) $

3. 这是个复杂的最优化问题，通常可以采用前向分步算法求解。

   前向分步算法求解这一优化问题的思想是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，则可以简化优化的复杂度。

   具体地，每一步只需要优化如下的损失函数： $ MathJax-Element-146 $ 。

2.5.2 前向分布算法

1. 前向分步算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-147 $
     • 损失函数 $ MathJax-Element-148 $
     • 基函数集 $ MathJax-Element-149 $

   • 输出：加法模型 $ MathJax-Element-150 $

   • 算法步骤：

     • 初始化 $ MathJax-Element-151 $

     • 对 $ MathJax-Element-152 $

       • 极小化损失函数 $ MathJax-Element-153 $ ，得到参数 $ MathJax-Element-154 $ 。
       • 更新 $ MathJax-Element-155 $ 。

     • 最终加法模型 $ MathJax-Element-156 $ 。