AdaBoost算法笔记

date
Aug 6, 2022
Last edited time
Sep 25, 2022 05:11 AM
status
Published
slug
AdaBoost算法笔记
tags
ML
summary
摸鱼了一段时间…
type
Post
origin
https://www.notion.so/lazurite/AdaBoost-79f76753414d4e778c909fc862219ccd
Field
Plat
基础概念强可学习与弱可学习提升方法AdaBoost 算法算法流程算法示例AdaBoost 算法的训练误差分析向前分布算法加法模型向前分布算法 向前分布算法与AdaBoost

基础概念

强可学习与弱可学习

历史上，Kearns和Valiant首先提出了“强可学习”(strongly learnable) 和“弱可学习”( weakly learnable)的概念。指出:在概率近似正确( probably approximately correct, PAC)学习的框架中，一个概念(一个类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的; 如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

提升方法

对于分类问题而言,给定一个训练样本集，求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。
提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器(又称为基本分类器)，然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

AdaBoost 算法

假设给定-一个二类分类的训练数据集
其中，每个样本点由实例与标记组成。实例 ,标记 , 是实例空间， 是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。

算法流程

  1. 初始化训练数据的权值分布:
  1. 对
    1. 使用具有权值分布 的训练数据集学习，得到基本分类器:
    2. 计算 在训练数据集上的加权分类误差率
        3. 在加权训练数据集上的加权分类误差率是被 误分类样本的权值之和.
    3. 计算 的系数:
        4. 当 且 时, , 因此错误率越低的分类器在最终分类器中起的作用越大.
    4. 更新训练数据集的权值分布:
        5. 其中, 为归一化因子使 符合概率分布.
        这一步更新训练数据的权值分布为下一轮训练做准备, 更新的权值可以写作 , 即误分类样本在下一轮的学习中将会占有更大的权重.
  1. 构建基本分类器的线性组合
      2. 得到最终的分类器:
      这一步使用线性组合 实现 个基本分类器的加权表决. 系数 表示了基本分类器 的重要性, 这里的 , 的符号决定了实例 的类别, 的绝对值表示分类的置信度.

算法示例

序号
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
1
1
1
-1
-1
-1
1
1
1
-1
  1. 初始化数据权值分布
  1. 进行第一轮训练, .
    1. 在权值分布为 的训练数据上，阈值 取 时分类误差率最低，故基本分类器为
    2. 计算 在训练数据上的加权分类误差率: .
    3. 计算 的系数: .
    4. 更新训练数据的权值分布:
      分类器 在训练数据集上有 3 个误分类点.
  1. 进行第二轮训练, .
    1. 在权值分布为 的训练数据上,阈值 是 时分类误差率最低，基本分类器为
    2. 在训练数据集上的加权分类误差率: .
    3. 计算得到 .
    4. 更新训练数据的权值分布:
      分类器 在训练数据集上有 3 个误分类点.
  1. 进行第三轮训练, .
    1. 在权值分布为 的训练数据上,阈值 是 时分类误差率最低，基本分类器为
    2. 在训练数据集上的加权分类误差率: .
    3. 计算得到 .
    4. 更新训练数据的权值分布:
      最终的分类器 在训练数据集上有 0 个误分类点.
则: 最终的分类器为: .
 

AdaBoost 算法的训练误差分析

  • 定理
      1. AdaBoost 算法最终分类器的训练误差界为:
          2. 这一定理说明，可以在每一轮选取适当的 使得 最小，从而使训练误差下降最快。
      1. 二类分类问题 AdaBoost 的训练误差界
          2. 这里的 .
  • 推论
      1. 如果存在 , 对所有 有 , 则
          2. 这表明在此条件下AdaBoost的训练误差是以指数速率下降的。
      注意，AdaBoost 算法不需要知道下界 ,这正是设计 AdaBoost 时所考虑的。与一些早期的提升方法不同，AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来，Ada是Adaptive的简写。

向前分布算法

加法模型

其中, 为基函数, 为基函数的参数, 为基函数的参数. 显然, 模型 为一个加法模型.
在给定训练数据及损失函数 的条件下，学习加法模型 成为经验风险极小化即损失函数极小化问题:
通常这是一一个复杂的优化问题。前向分步算法(forward stagewise algorithm)求解这一优化问题的想法是: 如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数, 那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数:

向前分布算法

给定训练数据集 , , 。损失函数 和基函数的集合 , 学习加法模型 的前向分步算法如下:
  1. 初始化 .
  1. 对于
    1. 极小化损失函数
        2. 得到参数 .
    2. 更新 .
  1. 得到加法模型
这样，前向分步算法将同时求解从 到 所有参数 的优化问题简化为逐次求解各个 的优化问题。

向前分布算法与AdaBoost

我们可以使用向前分步算法推导出 AdaBoost, 可以说 AdaBoost 算法是向前分布加法算法的特例, 这时, 模型是由基本分类器组成的加法模型, 损失函数是指数函数.
当 时, 在 AdaBoost 的第 轮迭代过程中, .
极小化损失函数可以写为:
令 , 则上式可以写为:
  1. 的计算
      2. 由于 , .
      由于 , , 两个函数对于 的单调性相同, 因此相互替代不影响 .
      则 .
  1. 的计算
      2. 另外,
      将 带入公式, 可以得到 , 求导得到: .
  1. 更新权值分布
      2. 由 以及 , 可以得到
      而在 AdaBoost 当中: . 与上式只差了一个归一化因子.

© Lazurite 2021 - 2023