C07. 稀疏核机

S07. 前言

• 重点
  • 支持向量机 ( Support Vector Machine, SVM )
  • 相关向量机 ( Relevance Vector Machine, RVM )
• 难点
  • 用于分类的 SVM
  • 用于回归的 RVM
• 学习基础
  • 最优化理论
    • 二次规划
    • 对偶表示
    • Lagrange 函数
    • 松弛变量
  • SVM ( 支持向量机 )
    • 支持向量
    • 边缘
  • Laplace 逼近
    • 高斯过程
  • 迭代重加权最小平方 ( IRLS )
• 学习要点
  • SVM 是稀疏核算法，属于决策类算法，不提供后验概率，对新数据的预测只需要依赖于训练数据点上的一个子集上计算的核函数。
  • RVM 也是稀疏核算法，是基于贝叶斯方法的，能够提供后验概率输出的，具有比 SVM 更加稀疏的解的算法。

S7.1. 最大边缘分类器

• 支持向量机中采用最大边缘解的理论基础
  • 计算学习理论 ( Computational Learning Theory )
  • 统计学习理论 ( Statistical Learning Theory )
  • 边缘 ( Margin ) ：定义为决策边界与任意样本之间的最小距离，决策边界与最近的数据点之间的垂直距离。
    • 决策边界被行为使边缘最大化的那个决策边界。
    • 最优超平面是有着最大边缘的超平面
      • 随着方差的减小，距离超平面较近的点对超平面的控制能力逐渐大于距离较远的点
      • 在极限情况下，超平面会变得与非支持向量的数据点无关
  • SVM 稀疏性的来源：边缘上的点被限制为激活；非边缘上的点限制为未激活。
• SVM 中重叠数据的分类问题
  • 面对不能线性可分的数据进行精确划分会导致较差的泛化能力
    • 允许部分训练数据点被误分类，从而提高泛化能力
      • 位于正确的边缘边界内部的点或者边缘界上的点
      • 位于正确的边缘边界外部的点
      • 位于决策边界上的点
      • 被错误分类的点
    • 放宽边缘的硬限制，得到一个软边缘 ( Soft Margin )
  • 训练 SVM 的方法
    • 限制条件定义一个凸区域，任意局部最优解也是全局最优解
    • 分块方法：将完全的二次规划问题分解为一系列小的二次规划问题
    • 顺序最小化优化 ( Sequential Minimal Optimization )
• 与 Logistic 回归的关系
  • 对于线性不可分的概率分布，用最小化正则化的误差函数可以重新表示 SVM。
  • 采用以下误差函数用来对误分类误差函数的连续近似
    • 铰链误差函数
    • Logistic Sigmoid 误差函数
    • 平方和误差函数
• 多类 SVM
  • 构建 K 个独立的 SVM，其中第 k 个模型在训练时，使用来自类别 $C_k$ 的数据作为正例，使用剩余的 $K-1$ 个类别的数据作为负例。这被称为「1 对剩余」( one-versus-the-rest ) 方法。是应用最广泛的方法。
    • 不同的分类器在不同的任务上训练，无法保证不同分类器产生的实数值具有恰当的尺度。
    • 训练集合不平衡。
  • 在所有可能的类别对之间训练 $\frac{K ( K-1 ) }{2}$ 个不同的二分类 SVM，然后将测试数据点分到具有最高「投票数」的类别中去。这被称为「1 对 1」( one-versus-one )
    • 会导致最终分类的歧义性
    • 对于较大的 K，需要比「1 对剩余」消耗更多的时间
      • 将每对分类器组织成有向无环图，即 DAGSVM。
  • 误差—修正编码，对「1 对 1」方法的推广。
    • 对于错误以及各个分类品质输出的歧义性具有鲁棒性
• 单一类别的 SVM
  • 解决与概率密度估计相关的无监督学习问题。
    • 不是用来对数据的概率密度建模
    • 只是想找到一个光滑的边界将高密度的区域包围出来
  • 解决方案
    • 将训练数据中的固定比例的数据从原始数据集中分离，同时最大化超平面与原点之间的距离 ( 边缘 )
    • 寻找特征空间中包含数据集的比例数据的最小球体。
• 回归问题的 SVM
  • 在简单的线性回归模型中，最小化一个正则化的误差函数
    • 为了得到稀疏解，二次误差函数被替换为 $\epsilon$—不敏感的函数 ( $\epsilon$-insensitive error function )，即固定不敏感区域 $\epsilon$ 的宽度
    • 固定位于管道数据点的比例 $\nu$
• 计算学习理论，也叫统计学习理论
  • 概率近似正确 ( Probably Approximately Correct, PAC ) 学习框架
    • 目标是数据集的大小与泛化能力之间的关系
    • 提供满足准则所需要的最小数据集规模的界限
  • VC 维度：函数空间复杂度的度量，使得 PAC 框架可以扩展到包含无穷多个函数的空间
  • 在 PAC 框架中推导出的界限为最低标准，严重高估了得到给定泛化能力所需要的数据集的规模。
  • 提升 PAC 界限的紧致程度的方法是 PAC-Bayesian 框架，考虑了空间 F 上的函数的概率分布情况。

S7.2. 相关向量机

相关向量机 ( Relevance Vector Machine, RVM ) 是一个用于回归问题和分类问题的贝叶斯稀疏核方法，会有更加稀疏的模型，在测试集上的计算速度更快，保留了可比的泛化误差。

• 回归问题的 RVM
  • 回归问题的 RVM 基于的是线性模型 ( S03 )，因为先验概率不同，从而产生了稀疏解。
    • RVM 对于每个权参数 $w_i$ 都引入一个单独的超参数 $\alpha_i$，而不是共享的超参数
      • 对于超参数 $\boldsymbol{\alpha}$ 和 $\beta$ 的确定可以使用第二类最大似然法 ( 也叫证据近似 )。
        • 令要求解的边缘似然函数的导数等于零，得到超参数的重估计方程；
        • 使用 EM 算法，迭代求解超参数的值。
      • 当算法关于这些超参数最大化模型证据时，大部分都趋于无穷，对应的权参数的后验概率分布就集中在零附近。于是与这些参数相关联的基函数就不再对模型的预测产生作用，等价于被剪枝，从而产生了一个稀疏的模型。
      • 超参数不为零对应的输入变量 $x_n$ 就是相关向量，因为它们是通过自动相关性检测 ( Automatic Relevance Determination, ARD ) 的方法得到的。
      • 通过自动相关性检测得到的概率模型的稀疏性的方法是可以应用于任何表示成基函数的可调节线性组合形式的模型上。
  • 对于带有以数据点为中心的基函数的 RVM 进行数据以外的区域外插时，模型会对预测变得起来越确定 ( 即过拟合 )。
    • 可以使用高斯过程回归的预测分布来解决，但是计算代价过高。
  • RVM vs SVM
    • RVM：模型更加简洁，处理测试数据的速度加快，稀疏性的增大也没有减小泛化误差。( P244 F7.9 )
    • RVM：训练过程涉及到优化一个非凸函数，训练时间也更长。
• 通过对 RVM 的稀疏性分析得到一个更快的最优化超参数的方法
  • ( 通过学习算法进一步了解稀疏性的原理，看不懂也不影响 )
• 分类问题的 RVM：将权值的自动相关性确定 ( P220 S6.4.4. ) 先验应用到概率线性分类模型 ( P147 S4.3 )
  • 二分类问题：在 RVM 中，模型使用的是 ARD 先验，使用 Laplac 近似后验概率。
    • 初始化超参数向量 $\boldsymbol{\alpha}$；
    • 基于给定的超参数，对后验概率建立一个高斯近似，从而得到了对边缘似然的一个近似
    • 近似后的边缘似然函数的最大化 ( 迭代重加权最小平方，IRLS )，又引出了对超参数的重新估计
    • 持续这个过程直到收敛。
  • 多分类问题
    • 使用 Softmax 函数对 K 个线性模型进行组合
    • 使用 Laplace 近似用来最优化超参数
    • 模型和 Hessian 矩阵可以使用 IRLS 算法得到，训练代价相对较大
  • RVM vs SVM
    • RVM 的相关向量倾向于不在决策边界区域内，与 SVM 刚好相反。( P248 F7.12 )
    • RVM 做出了概率形式的预测
    • RVM 相对于 SVM 训练时间相对较长
      • RVM 避免了通过交叉验证确定模型复杂度的过程，从而补偿了训练时间的劣势
    • RVM 产生的模型更加稀疏，对于测试点进行预测的计算时间更短

S07. 小结

作者的重点不在描述 SVM，而是描述基于贝叶斯框架和 SVM 模型得到的 RVM，因此作者对于 SVM 的介绍细节较少，如果想先理解 SVM 建议参考 [^周志华，2018]，有了 SVM 的基础后再理解 RVM 的思想及优缺点会更加容易。