[机器学习西瓜书] 第06章 支持向量机 笔记

人工智能AI|计算机 ComputerScience

   
   

@ZYX 写于2020年08月10日

第06章 支持向量机

6.1 间隔与支持向量

  • 训练样本集 $D=\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\}, y_{i} \in \{-1,+1\}$
  • 最基本的想法就是基于训练集 $D$ 在样本空间中找到一个划分超平面,将不同类别分开
    • 可能有很多
    • 应该去找位于两类训练样本正中间
      • 因为该超平面对训练样本局部扰动容忍性最好
  • 在样本空间中,划分超平面可通过如下线性方程来描述:
    [6.1] $w^{T}x+b=0$

    • 法向量 $w=(w_{1};w_{2};\dots;w_{d})$ 决定了超平面的方向
    • 位移项 $b$ 决定了超平面与原点之间的距离
    • 划分超平面 可表达为 $(w,b)$
    • 样本空间中任意点 $x$ 到超平面 $(w,b)$ 的距离
      [6.2] $r=\frac{|w^{T}x+b|}{||w||}$
    • 假设超平面能正确分类,则令
      [6.3] $\begin{cases} w^{T}x+b\ge +1 &\text{, } y_{i}=+1; \\ w^{T}x+b\le -1 &\text{, } y_{i}=-1; \end{cases}$
  • 支持向量 (support vector)
    图6.2 支持向量与间隔

    • 距超平面最近的这几个训练样本点使式[6.3]成立, 称为支持向量(support vector)
    • 间隔(margin)
      • 两个异类支持向量到超平面的距离之和
        $\gamma = \frac{2}{||w||}$ , 称为间隔(margin)
    • 最大间隔(maximum margin)
      • 欲找到具有最大间隔(maximum margin)的划分超平面
      • 找到能满足式[6.3]中约束的参数 $w$ 和 $b$ , 使得 $\gamma$ 最大,即
        [6.5] $\begin{aligned} &\max_{w,b} \frac{2}{||w||} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
  • 支持向量机
    • 为了最大化间隔,仅需最大化 $||w||^{-1}$,等价于最小化 $||w||^{2}$。可重写[6.5] 为
      $\begin{aligned} &\min_{w,b} \frac{1}{2}||W||^{2} \\ &\text{s.t. } y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$

      • 这就是支持向量机(Support Vector Machine,简称SVM)的基本型

6.2 对偶问题

  • 对[6.6]使用拉格朗日乘子法可得到其对偶问题(dual problem)
    • 对[6.6]的每条约束添加拉格朗日乘子 $\alpha_{i} \ge 0$,则该问题的拉格朗日函数可写为
      [6.8] $L(w,b,\alpha)=\frac{1}{2}||w||^{2}+\sum^{m}_{i=1}\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$

      • 其中 $\alpha=(\alpha_{1};\alpha_{2};\dots;\alpha_{m})$
      • 令 $w$ 和 $b$ 的偏导为零,得
        • [6.9]
          $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
        • [6.10]
          $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
      • 将[6.9]代入[6.8],可消去 $w$ 和 $b$。再考虑[6.10]的约束,就得到[6.6]的对偶问题
        [6.11] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j} \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
      • 解出 $\alpha$ 后,求出 $w$ 与 $b$ 得到模型
        [6.12] $\begin{aligned} f(x)&=w^{T}x+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}x^{T}_{i}x+b \end{aligned}$
  • KKT条件
    • 从对偶问题[6.11]解出的 $\alpha_{i}$ 是[6.8]中的拉格朗日乘子, $\alpha_{i}$ 恰对应着训练样本 $(x_{i},y_{i})$
      • SMO(Sequential Minimal Optimization) 求解算法
        • 基本思路: 先固定 $\alpha_{i}$ 之外的所有参数,然后求向上的极值
          • 因为有约束 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$
            • 若固定 $\alpha_{i}$ 之外的其他变量,则 $\alpha_{i}$ 可由其他变量导出.
        • 每次选择两个变量 $\alpha_{i}$ 和 $\alpha_{j}$,并固定其他参数
        • 在参数初始化后, SMO不断执行如下两步直至收敛:
          1. 选取一对需更新的变量 $\alpha_{i}$ 和 $\alpha_{j}$
            • 只需选取的 $\alpha_{i}$ 和 $\alpha_{j}$ 中有一个不满足KKT条件[6.13],目标函数就会在选代后减小
            • SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量
              • KKT 条件违背的程度越大,则更新后可能导致的函数值减幅越大.
              • SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大
          2. 固定 $\alpha_{i}$ 和 $\alpha_{j}$ 以外的参数,求解[6.11],更新$\alpha_{i}$ 和 $\alpha_{j}$
            • 仅考虑 $\alpha_{i}$ 和 $\alpha_{j}$ 时,[6.11]中的约束可重写为
              [6.14] $\alpha_{i}y_{i}+\alpha_{j}y_{j}=c, \alpha_{i} \ge 0, alpha_{j} \ge 0$

              • $c=-\sum_{k \not = i,j}\alpha_{k}y_{k}$ 是使 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$ 成立的常数
            • 消去[6.11]中的变量 $\alpha_{j}$,则得到一个关于 $\alpha_{i}$ 的单变量二次规划问题
              • 这样的二次规划问题具有闭式解,于是不必调用数值优化算法即可高效地计算出新的 $\alpha_{i}$ 和 $\alpha_{j}$
      • 如何确定偏移项b
        • 到对任意支持向量$(x_{s}, y_{s})$,都有 $y_{s}f(x_{s})=1$,即
          [6.17] $y_{s}(\sum_{i \in s}\alpha_{i}y_{i}x^{T}_{i}x_{s}+b)=1$

          • 其中 $S=\{ i| \alpha_{i}>0 , i=1,2,\dots,m \}$ 为所有支持向量的F标集
        • 现实任务中, 使用所有支持向量求解的平均值
          [6.18] $b=\frac{1}{|S|}\sum_{s\in S}(y_{s}-\sum_{i\in S}\alpha_{i}y_{i}x^{T}_{i}x_{s})$
    • 因为[6.6]中有不等式约束,因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件,即要求
      [6.13] $\begin{cases} &\alpha_{i}\ge 0; \\ &y_{i}f(x_{i})-1\ge 0; \\ &\alpha_{i}(y_{i}f(x_{i})-1)=0 \end{cases}$

      • 对任意训练样本,总有$\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1$
        • 若 $\alpha_{i}=0$,则该样本将不会在[6.12]的求和中出现,也就不会对 $f(x)$ 有任何影响
        • 若 $\alpha_{i}>0$,则有 $y_{i}f(x_{i})=1$,所对应的样本点位于最大间隔边界上,是一个支持向量
        • 这显示出支持向量机的一个重要性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关

6.3 核函数

  • 非线性可分问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分
    • 如果原始空间是有限维,即属性数有限,那么一定存在一个高维特征空间使样本可分 【参见第12章】
  • 对偶问题
    • 令 $\phi(x)$ 表示将 $x$ 映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可表示为
      [6.19] $f(x)=w^{T}\phi(x)+b$

      • 其中 $w$ 和 $b$ 是模型参数
    • 类似[6.6],有
      [6.20] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{w} \\ &\text{s.t.} y_{i}(w^{T}\phi(x_{i})+b)\ge 1, i=1,2,\dots,m \end{aligned}$
    • 其对偶问题是
      [6.21] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(x_{i})^{T}\phi(x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$

      • 由于特征空间维数可能很高,因此直接计算 $\phi(x_{i})^{T}\phi(x_{j})$ 通常是困难的。为了避开这个障碍,可以设想这样一个函数:
        [6.22] $\kappa(x_{i},x_{j})=<\phi(x_{i}),\phi(x_{j})>=\phi(x_{i})^{T}\phi(x_{j})$

        • 即 $x_{i},x_{j}$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\kappa(\cdot,\cdot)$ 计算的结果
      • [6.21]可重写为
        $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}\kappa(x_{i},x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
      • 求解 $\alpha$ 后即可得到
        [6.24] $\begin{aligned} f(x)&=w^{T}\phi(x)+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\phi(x_{i})^{T}\phi(x_{j})+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\kappa(x_{i},x_{j})+b \end{aligned}$

        • 这里的函数 $\kappa(\cdot,\cdot)$ 就是核函数(kernel function)
        • [6.24]展式亦称支持向量展式(support vector expansion)
  • 定理6.1 (核函数)
    • 令 $\chi$ 为输入空间,$\kappa(\cdot,\cdot)$ 是定义在 $\chi \times \chi$ 上的对称函数
    • 则 $\kappa$ 是核函数 当且仅当 对于任意数据 $D=\{x_{1},x_{2},\dots,x_{m}\}$,核矩阵(kernel matrix) $K$ 总是半正定的:
      6.1矩阵
    • 对于一个半正定核矩阵,总能找到一个与之对应的映射$\phi$.
      换言之,任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间(Reproducing Kernel Hilbert Space ,简称RKHS)的特征空间.
  • 特征空间的好坏对支持向量机的性能至关重要
    表6.1 常用核函数
  • 此外,还可通过函数组合得到 例如:
    • 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数,则对于任意正数 $\gamma_{1}, \gamma_{2}$,其线性组合
      [6.25] $\gamma_{1}\kappa_{1} + \gamma_{2}\kappa_{2}$ 也是核函数;
    • 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数,则核函数的直积
      [6.26] $\kappa_{1} \otimes \kappa_{2}(x,z)=\kappa_{1}(x,z)\kappa_{2}(x,z)$ 也是核函数;
    • 若 $\kappa_{1}$ 为核函数,则对于任意函数 $g(x)$,
      [6.27] $\kappa(x,z)=g(x)\kappa_{1}(x,z)g(z)$ 也是核函数

6.4 软间隔与正则化

  • 在现实任务中,往往很难确定合适的核函数,使得训练样本在特征空间中线性可分
    • 即使恰好找到了某个核函数使训练集在特征空间中线性可分,也很难断定结果不是由于过拟合所造成的.
  • 缓解该问题的一个办法是允许支持向量机在一些样本上出错
  • 硬间隔
    • 支持向量机形式是要求所有样本均满足约束[6.3] ,即所有样本都必须划分正确,这称为硬间隔(hard margin)
  • 软间隔(soft margin)
    • 允许某些样本不满足约束
      [6.28] $y_{i}(w^{T}x_{i}+b)\ge 1$
    • 在最大化间隔的同时,不满足约束的样本应尽可能少
      • 于是,优化目标可写为
        [6.29] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\mathcal{l}_{0/1}(y_{i}(w^{T}x_{i}+b)-1)$

        • $C>0$ 是个常数
        • 当 $C$ 为无穷大时,式(6.29)迫使所有样本均满足约束(6.28)
          • 于是式(6.29) 等价于(6.6)
        • 当 $C$ 取有限值时,式(6.29)允许一些样本不满足约束
        • $\mathcal{l}_{0/1}$是”0/1损失函数”
          [6.30] $\mathcal{l}_{0/1}=\begin{cases}1 & \text{, if }z<0; \\ 0 & \text{otherwise} \end{cases}$

          • 然而,$\mathcal{l}_{0/1}$ 非凸、非连续,数学性质不太好
          • 人们通常用其他一些函数来代替,称为替代损失(surrogate loss)
            • 三种常用的替代损失函数:
              图 6.5 三种常见的替代损失函数: hi日ge损失、指数损失、对率损失

              • [6.31] hinge 损失: $l_{hinge}(z)=\max(0,1-z)$
              • [6.32] 指数损失(exponential loss): $l_{exp}(z)=e^{-z}$
              • [6.33] 对率损失(logistic loss): $l_{log}(z)=\log(1+e^{-z})$
          • 若采用hinge 损失,则式(6.29)变成
            [6.34] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\max(0, 1-y_{i}(w^{T}x_{i}+b))$
          • 引入”松弛变量” (s1ack variables) $\xi_{i} \ge 0$ ,可将式(6.34)重写为
            [6.35] $\begin{aligned}&\min_{w,b,\xi_{i}} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1-\xi_{i} \\ &\xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$
          • 这就是常用的”软间隔支持向量机”,这仍是一个二次规划问题
          • 于是类似式(6 .8) ,通过拉格朗日乘子法可得到式(6.35)的拉格朗日函数
            [6.36] $L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i}+\sum^{m}_{i=1}\alpha_{i}(1-\xi_{i}-y_{i}(w^{T}x_{i}+b))-\sum^{m}_{i=1}\mu_{i}\xi_{i}$

            • $\alpha \ge 0, \mu \ge 0$ 是拉格朗日乘子
          • 令 $L(w,b,\alpha,\xi,\mu)$ 对 $w$,$b$的偏导为零可得
            • [6.37]
              $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
            • [6.38]
              $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
            • [6.39]
              $C=\alpha_{i}+\mu_{i}$
          • 代入式(6.36) 即可得到式(6.35) 的对偶问题
            $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &0\le \alpha_{i}\le C, i=1,2,\dots,m \end{aligned}$

            • 将式(6.40)与(6.11)对比可看出,两者唯一差别就在对偶变量的约束不同
          • 对软间隔支持向量机, KKT 条件要求
            [6.41]
          • 于是,对任意训练样本$(x_{i},y_{i})$,总有 $\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1-\xi_{i}$
        • 这些替代函数产生的模型具有一个共性:
          • 优化目标中的第一项描述划分超平面的”间隔”大小
          • 另一项 $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 表述训练集上的误差
          • 可写为更一般的形式
            [6.42] $\min_{f}\Omega(f)+C\sum^{m}_{i=1}l(f(x_{i},y_{i}))$

            • $\Omega(f)$ 称为结构风险(structural risk)
              • 用于描述模型$f$ 的某些性质
            • $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 称为经验风险(empirical risk)
              • 用于描述模型与训练数据的契合程度
            • $C$ 用于对二者进行折中
          • 另一方面,该信息有助于削减假设空间,从而降低了过拟合风险
            • 从这个角度来说,式(6 .42) 称为正则化(regularization)问题
              • $\Omega(f)$ 称为正则化项
              • $C$ 则称为正则化常数

6.5 支持向量回归

图6.6 支持向量回归示意图.红色显示出ε- 间隔带, 落入其中的样本不计算损失
– 支持向量回归(Support Vector Regression,简称SVR)
– 假设我们能容忍 $f(x)$ 与 $y$ 之间最多有 $\epsilon$ 的偏差
– 于是,SVR问题可形式化为
[6.43] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}l_{\epsilon}(f(x_{i})-y_{i})$
– $C$ 为正则化常数
– $l_{\epsilon}$ 是 ε不敏感损失(ε insensitive loss)函数
[6.44] $\mathcal{l}_{0/1}=\begin{cases}0 & \text{, if }|z|<\epsilon; \\ |z|-\epsilon & \text{otherwise} \end{cases}$
– 引入松弛变量 $\xi_{i}$ 和 $\hat \xi_{i}$ ,可将式(6 .43)重写为
[6.45] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}(\xi_{i}+\hat \xi_{i}) \\ &\text{s.t.} f(x_{i})-y_{i}\le \epsilon+\xi_{i} \\ &y_{i}-f(x_{i})\le \epsilon+\xi_{i} \\ &\xi_{i}\ge 0, \hat \xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$