SVM自学SMO高效优化算法思维导图

基于最大间隔分割数据、寻找最大间隔、SMO高效优化算法、利用完整Platt SMO算法加速优化、在复杂数据上应用核函数

SVM自学SMO高效优化算法思维导图

• 基于最大间隔分割数据
  • 优点
    • 泛化错误率低
    • 计算开销不大
    • 结果易解释
  • 缺点
    • 对参数调节和核函数选择敏感
    • 原始分类器不加修改仅适用于处理二类问题
  • 使用数据类型
    • 数值型
    • 标称型
  • 线性可分
    • 画一条直线可将两组数据点分开
  • 超平面
    • 分类的决策边界
  • 间隔
    • 点到分隔面的距离
      • 点到分隔面的间隔
    • 数据集中所有点到分隔面的最小间隔的2倍
      • 分类器（数据集）的间隔
  • 支持向量
    • 离分隔超平面最近的那些点
    • 最大化支持向量到分隔面的距离
• 寻找最大间隔
  • 点到分隔超平面的距离
    • b：类似Logistic回归中的截距w0
  • 分类器求解的优化问题
    • 使用类似单位阶跃函数的函数得到f(wTx+b)
    • u<0时f(u)输出-1，否则1
      • 取-1和1方便数学上的处理
    • 间隔计算
      • 该值>=1，是约束条件
    • 找到具有最小间隔的数据点
      • 需要对间隔最大化
      • 求解困难
        • 给定一些约束条件求最优值
        • 拉格朗日乘子法
          • 约束条件
    • 松弛变量
      • 前述假设为数据100%线性可分
      • 约束条件改为
        • 常数C控制“最大化间隔”和“保证大部分点的函数间隔小于1.0”两个目标的权重
  • SVM一般框架
    • 收集数据
      • 任意方法
    • 准备数据
      • 数值型数据
    • 分析数据
      • 有助于可视化分隔超平面
    • 训练算法
      • SVM大部分时间为训练
      • 主要通过两个参数调优
    • 测试算法
      • 简单的计算过程
    • 使用算法
      • 几乎所有问题都可以用SVM
      • 本身是一个二类分类器，对多类需修改
• SMO高效优化算法
  • 二次规划求解工具
    • 用于在线性约束下优化具有多个变量的二次目标函数的软件
    • 缺点
      • 需要强大的计算能力
      • 实现上十分复杂
  • Platt的SMO算法
    • 序列最小优化
    • 思想
      • 将大优化问题分解成多个小优化问题
    • 优点
      • 时间短
    • 目标
      • 求出一系列alpha和b
      • 一旦求出这些alpha，很容易计算出权重向量w并得到分隔超平面
    • 工作原理
      • 每次循环中选择两个alpha进行优化处理
      • 一旦找到一对合适的alpha，则增大其中一个减少另一个
        • 合适：符合条件
          • 两个alpha必须在间隔边界之外
          • 两个alpha还没有进行过区间化处理或不再边界上
  • 应用简化版SMO算法处理小规模数据集
    • 特点
      • 跳过外循环确定要优化的最佳alpha对的步骤
      • 代码少
      • 执行速度慢
    • 步骤
      • 在数据集遍历每个alpha
      • 在剩下的alpha集合中随机选择另一个alpha，构成alpha对
      • 注意
        • 总是同时改变两个alpha
    • 伪代码
      • 创建一个alpha向量并初始化为0向量
      • 当迭代次数小于最大迭代次数时（外循环）
        • 对数据集中每个数据向量（内循环）
          • 如果该数据向量可优化
            • 随机选择另一个数据向量
            • 同时优化两个向量
            • 如果都不能被优化，退出内循环
        • 如果所有向量都没被优化，增加迭代次数，继续下一次循环
    • 数组过滤
      • 只对NumPy类型有用
      • alphas[alpha>0]
• 利用完整Platt SMO算法加速优化
  • alpha值的选择
    • 第一个
      • 两种方式交替
        • 在所有数据集上进行单遍扫描
        • 在非边界alpha中实现单遍扫描
          • 非边界alpha
            • 不等于边界0或C的值
          • 过程
            • 建立alpha值列表
            • 对列表进行遍历
            • 跳过已知不会改变的alpha值
    • 第二个
      • 最大优步长
        • 建立一个全局的缓存保存误差值
        • 从中选择使得步长（Ei-Ej）最大的alpha值
  • 分类
    • 基于alpha值得到超平面，包括w的计算
      • 最终起作用的只有支持向量
    • 对数据进行分类处理
• 在复杂数据上应用核函数
  • 利用核函数将数据映射到高维空间
    • 核函数
      • 想象成wrapper/interface
      • 从一个特征空间到另一个特征空间的映射
    • SVM优化
      • 利好
        • 所有运算都可以写成内积
    • 核技巧（核“变电”）
      • 将内积替换成核函数的方式
  • 径向基核函数
    • 径向基
      • 向量作为自变量
      • 能够基于向量距离运算输出一个标量
    • 下面用径向基核函数的高斯版本
    • 公式
      • 
        • 用户定义的用于确定“到达率”（函数值跌到0）的速度参数
  • 在测试中使用核函数
    • 支持向量的数目存在一个最优值
      • 太少：得到一个很差的决策边界
      • 太多：近乎k近邻
• 示例：手写识别问题回顾
  • 参考
    • 多分类
      • A Comparison of Methods for Multiclass Support Vector Machines
    • v-SVM
      • Pattern Recognition
  • 注意
    • 最小的训练错误率不对应于最小的支持向量数目
    • 线性核函数效果并不特别糟