跳转至

SVM

支持向量机（SVM, support vector machine）一般是二分类模型。其基本形式是定义在特征空间上间隔最大的线性分类器。它在感知机的基础上增加了间隔最大的策略损失，也是主要区别

SVM 是核技巧应用的一个经典案例，用于处理非线性的数据集；除此之外它在很多方面的使用效果也相当出色（CV，NLP，推荐系统，时序分析等等）

SVM 的损失策略为间隔最大化，可形式化为一个求解凸二次规划的问题。其学习算法是凸二次规划的最优化算法，转化为拉格朗日对偶问题联系 KKT 条件求解

借助 SVM 的对偶形式，我们还可以借助核技巧 / 核方法（kernel trick / kernel method）来应对非线性情形

分类

  • 监督学习方法
  • 非概率模型
  • 参数化模型
  • 判别学习方法

基本形式

SVM 的基本形式与感知机类似，但随着后面优化求解，可以推导出更适合的推理形式

假设样本写作列向量，即

\[ \mathbf{x} = [x^{(1)},x^{(2)},···,x^{(p)}]^\mathrm{T} \]

SVM 有

\[ y = f(\mathbf{x};\mathbf{w},b) = sgn(\mathbf{w}^\mathrm{T}\mathbf{x}+b) \]

损失策略

首先是核心目标：最大化一个叫做间隔的东西，我们可以推导出它与参数 \(\mathbf{w}\) \(b\) 之间的关系

间隔直观上就是 SVM 在样本空间意味的超平面在法向量指向上能自由移动的“多少”，且能对数据分布有较好的分割。当超平面移动时，最先遇到并“顶住”的样本点被称为“支持向量（support vector）”，它们某种程度上决定了 SVM 学习收敛的最后形式，也是 SVM 名字的由来

类似于感知机，对于二分类样本点 \(y_i=1\) 与 \(y_j=-1\)，我们自然希望

\[ \begin{aligned} &\mathbf{w}^\mathrm{T}\mathbf{x}_i+b \geq 1, \quad y_i = 1\\ &\mathbf{w}^\mathrm{T}\mathbf{x}_j+b \leq -1, \quad y_j = -1 \end{aligned} \]

于是我们可以定义间隔 \(M\) 为 超平面 \(\mathbf{w}^\mathrm{T}\mathbf{x}+b=1\) 与 \(\mathbf{w}^\mathrm{T}\mathbf{x}+b=-1\) 之间的距离，设 \(\mathbf{x}^+\) 与 \(\mathbf{x}^-\) 分别是两平面上的点，且 \(\mathbf{x}^+ - \mathbf{x}^-\) 与 \(\mathbf{w}\) 平行，则有

\[ \begin{aligned} M = \Vert&\mathbf{x}^+ - \mathbf{x}^-\Vert\\ \Downarrow\\ M = \Vert&\lambda\mathbf{w}\Vert = \lambda\Vert\mathbf{w}\Vert \end{aligned} \]

我们需要求出 \(\lambda\)

\[ \begin{aligned} \mathbf{w}^\mathrm{T}\mathbf{x}^++b &= 1\\ \mathbf{w}^\mathrm{T}\mathbf{x}^-+b &= -1\\ \Downarrow\\ \mathbf{w}^\mathrm{T}(\mathbf{x}^+ - \mathbf{x}^-) &= 2\\ \Downarrow\\ \lambda\mathbf{w}^\mathrm{T}\mathbf{w} &= 2 \end{aligned} \]

故 \(\lambda = 2 / \mathbf{w}^\mathrm{T}\mathbf{w}\)，反代回 \(M\) 表达式

\[ M = \frac{2\Vert\mathbf{w}\Vert}{\mathbf{w}^\mathrm{T}\mathbf{w}} = \frac{2}{\sqrt{\mathbf{w}^\mathrm{T}\mathbf{w}}} \]

到此我们已经获得了需要优化的策略目标，最小化 \(M\) 即最大化 \(\mathbf{w}^\mathrm{T}\mathbf{w}\)

但仅有间隔最大是不行的，我们还需要让 SVM 能正确分类，因此需要添加各种约束，从数据集上看，大致可分为 hard SVM（线性可分），soft SVM（线性不可分）以及核方法使用的情形（非线性）

线性可分 | hard SVM

\[ \begin{aligned} &\min \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}\\ s.t. \quad &y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)\geq1, \quad i = 0,1,··,n \end{aligned} \]

非线性可分 | soft SVM

\[ \begin{aligned} &\min \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}+C\sum_{i=1}^n\varepsilon_i\\ s.t. \quad &\mathbf{w}^\mathrm{T}\mathbf{x}_i+b\geq1-\varepsilon_i, \quad y_i = 1;\\ &\mathbf{w}^\mathrm{T}\mathbf{x}_j+b\leq-1+\varepsilon_j, \quad y_j = -1;\\ &\varepsilon_i, \quad \varepsilon_j \geq 0 \end{aligned} \]

优化学习

正式进入 SVM 优化推导前，补一点凸优化的知识

拉格朗日对偶 | Lagrange Duality

在优化问题中，原始问题通常会带有很多约束条件，直接求解很困难，常常考虑将原始问题转化为它的对偶问题，通过求解对偶问题来得到原始问题的解

原始问题（Primal Problem）

\[ \begin{aligned} &\min_x f_0(x)\\ s.t. \quad &f_i(x)\leq0, \quad i = 1,2,···,m;\\ &h_j(x)=0, \quad j = 1,2,···,p \end{aligned} \]

原始问题不一定是凸问题， \(f\) 与 \(h\) 可以是一般函数

拉格朗日函数（Lagrangian function）

原始问题的拉格朗日函数为：

\[ L(x,\boldsymbol{\lambda},\mathbf{v}) = f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^pv_ih_i(x) \]

其中 \(x\in\mathcal{R}^n,\boldsymbol{\lambda}\in\mathcal{R}^m,\mathbf{v}\in\mathcal{R}^p\)

可以看到，拉格朗日函数相对于原始问题引入了两个新变量（向量），称为拉格朗日乘子

拉格朗日函数 \(L\) 如果看成是关于 \(x\) 的函数，那它其实就是对原始问题中目标函数与约束条件进行线性加权，目标函数的权系数是 1，约束条件的权系数是 \(\lambda_i\) 或 \(v_i\)

如果看成是关于 \(\lambda_i\) 或 \(v_i\) 的函数，则其余部分可看成常数，\(L\) 就可看作是一个关于 \(\lambda_i\) 或 \(v_i\) 的仿射函数（即最高次幂为1的多项式函数）

拉格朗日对偶函数（Lagrange dual function）

拉格朗日对偶函数（简称对偶函数）通过对拉格朗日函数关于 \(x\) 取下确界得到:

\[ g(\boldsymbol{\lambda},\mathbf{v}) = \inf_xL(x,\boldsymbol{\lambda},\mathbf{v}) \]

求解析式可先将 \(L\) 看成是关于 \(x\) 的函数，而将拉格朗日乘子看作常数，求出 \(L\) 的极小值点，再将该点回代，得到的关于 \(\boldsymbol{\lambda}\) 和 \(\mathbf{v}\) 的表达式就是对偶函数

对偶函数具有两条重要性质：

  • 对偶函数一定是凹函数，其凹性与原目标函数和约束函数凹凸与否无关

    证明：\(L(x,\boldsymbol{\lambda},\mathbf{v})\) 可以看作是一个无限的函数集，这个函数集中每个元素是 \(L(x_i,\boldsymbol{\lambda},\mathbf{v})\)，\(x\) 取遍其在定义域上的所有值得到不同的 \(x_i\)。针对不同的 \(x_i\)，\(L(x_i,\boldsymbol{\lambda},\mathbf{v})\) 都是关于 \(\boldsymbol{\lambda}\) 和 \(\mathbf{v}\) 的仿射函数，故有

    \[ g(\boldsymbol{\lambda},\mathbf{v}) = \inf_x\{L(x_1,\boldsymbol{\lambda},\mathbf{v}),L(x_2,\boldsymbol{\lambda},\mathbf{v}),···\} \]

    对仿射函数集取下界，得到的函数是凹函数

  • 对 \(\forall \lambda_i\geq0,\forall v\)，如果原问题最优解对应的目标函数值为 \(p^*\)，则 \(g(\boldsymbol{\lambda},\mathbf{v})\leq p^*\)

    证明：设原问题最优解为 \(x^*\)，有

    \[ \begin{aligned} L(x^*,\boldsymbol{\lambda},\mathbf{v}) &= f_0(x^*)+\sum_{i=1}^m\lambda_if_i(x^*)+\sum_{i=1}^pv_ih_i(x^*)\\ &\leq f_0(x^*) = p^* \end{aligned} \]

    又由 \(g(\boldsymbol{\lambda},\mathbf{v})\) 的定义，总有

    \[ g(\boldsymbol{\lambda},\mathbf{v}) \leq L(x^*,\boldsymbol{\lambda},\mathbf{v}) \leq p^* \]

拉格朗日对偶问题（Lagrange dual problem）

根据对偶函数的重要性质，对 \(\forall \lambda_i\geq0,\forall v\)，\(g(\boldsymbol{\lambda},\mathbf{v})\) 是原问题最优值 \(p^*\) 的一个下界，最好的下界就是最大化对偶函数，因此构造原问题的对偶问题：

\[ \begin{aligned} \max_{\boldsymbol{\lambda},\mathbf{v}} g(\boldsymbol{\lambda},\mathbf{v})\\ s.t. \quad \lambda_i\geq0 \end{aligned} \]

因为 \(g(\boldsymbol{\lambda},\mathbf{v})\) 是凹函数，故拉格朗日对偶问题一定是凸问题，其对应的最优解为 \(\boldsymbol{\lambda}^*\)，\(\mathbf{v}^*\)（最优拉格朗日乘子），若对应的最优值为 \(d^*\)，则总有 \(d^* \leq p^*\)

  • \(d^* \leq p^*\) 时，称为弱对偶（weak duality）
  • \(d^* = p^*\) 时，称为强对偶（strong duality）
  • \(p^* - d^*\) 称为对偶间隙（duality gap）

当原问题是凸问题且强对偶时，KKT 条件是 \(x^*\)，\(\boldsymbol{\lambda}^*\)，\(\mathbf{v}^*\) 为最优解的充要条件

SVM 优化的情形

线性可分 | hard SVM

\[ \begin{aligned} &\min \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}\\ s.t. \quad &y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)\geq1, \quad i = 0,1,··,n \end{aligned} \]

好在原问题是凸问题，并且强对偶，这意味着我们转化为对偶问题后的最优解也能保证在原问题上是最优解

首先得到原始问题的拉格朗日函数

\[ L(\mathbf{w},b,\boldsymbol{\alpha}) = \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}+\sum_{i=1}^n\alpha_i(1-y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)) \]

将拉格朗日乘子 \(\boldsymbol{\alpha}\) 视为常数，求极小值

对 \(\mathbf{w}\)，\(b\) 分别求一阶导零点

\[ \begin{aligned} \nabla_{\mathbf{w}}L(\mathbf{w},b,\boldsymbol{\alpha}) = \mathbf{w}-\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i = 0\\ \nabla_bL(\mathbf{w},b,\boldsymbol{\alpha}) = -\sum_{i=1}^n\alpha_iy_i = 0 \end{aligned} \]

回代进 \(L(\mathbf{w},b,\boldsymbol{\alpha})\)，有拉格朗日对偶函数

\[ \begin{aligned} g(\boldsymbol{\alpha}) &= \frac{1}{2}(\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i)^\mathrm{T}(\sum_{j=1}^n\alpha_jy_j\mathbf{x}_j)-\sum_{i=1}^n\alpha_iy_i(\sum_{j=1}^n\alpha_jy_j\mathbf{x}_j)^\mathrm{T}\mathbf{x}_i+\sum_{i=1}^n\alpha_i\\ &= \frac{1}{2}\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i^\mathrm{T}\sum_{j=1}^n\alpha_jy_j\mathbf{x}_j-\sum_{i=1}^n\alpha_iy_i(\sum_{j=1}^n\alpha_jy_j\mathbf{x}_j^\mathrm{T}\mathbf{x}_i)+\sum_{i=1}^n\alpha_i\\ &= \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j-\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j+\sum_{i=1}^n\alpha_i\\ &= -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j+\sum_{i=1}^n\alpha_i\\ \end{aligned} \]

故

\[ g(\boldsymbol{\alpha}) = \sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j \]

于是我们得到拉格朗日对偶问题

\[ \begin{aligned} \max &\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j\\ s.t. \quad &\sum_{i=1}^n\alpha_iy_i = 0;\\ &\alpha_i\geq0, \quad i=1,2···,n \end{aligned} \]

该形式比原始问题更好求解，因为存在有效的算法找到最优解 \(\alpha_i^*\)

求出 \(\alpha_i^*\) 后，由之前一阶导条件，我们可以得到 \(\mathbf{w}\) 的训练结果

\[ \mathbf{w}^* = \sum_{i=1}^n\alpha_i^*y_i\mathbf{x}_i \]

对于偏置项 \(b\)，我在网上初步搜索得到的讲解也比较少，普遍思路是根据 SVM 以及样本反代

\[ \begin{aligned} b^* &= y'-(\mathbf{w}^*)^\mathrm{T}\mathbf{x}'\\ &= y'-\sum_{i=1}^n\alpha_i^*y_i\mathbf{x}_i^\mathrm{T}\mathbf{x}' \end{aligned} \]

注意这里样本选取有要求，可以看出该样本 \((\mathbf{x}',y')\)满足

\[ (\mathbf{w}^*)^\mathrm{T}\mathbf{x}'+b^* = y' \]

\(y'\) 取值要么 +1 要么 -1，即该样本应该是在我们之前定义 \(M\) 设的两个超平面上。换句话说，它应该是支持向量之一

非线性可分 | soft SVM

与线性可分形式相近

\[ \begin{aligned} \max &\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\mathrm{T}\mathbf{x}_j\\ s.t. \quad &\sum_{i=1}^n\alpha_iy_i = 0;\\ &C\geq\alpha_i\geq0, \quad i=1,2···,n \end{aligned} \]

其中 \(C\) 为超参

对偶形式的 SVM

支持向量

讨论一下 \(\alpha_i\) 与对应样本 \((\mathbf{x}_i,y_i)\) 之间关系，并说明支持向量到底是什么

对于 hard SVM 原问题以及其拉格朗日函数

\[ \begin{aligned} &\min \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}\\ s.t. \quad &y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)\geq1, \quad i = 0,1,··,n \end{aligned} \]
\[ L(\mathbf{w},b,\boldsymbol{\alpha}) = \frac{1}{2}\mathbf{w}^\mathrm{T}\mathbf{w}+\sum_{i=1}^n\alpha_i(1-y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)) \]

如果我们不考虑对偶形式，单纯从拉格朗日乘子法的视角观察，对于任一个样本带来的约束条件

\[ 1-y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b)\leq0 \]

若最优解在边界处取到，即 \(1-y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b) = 0\)，为满足解存在的必要条件，必有其对应的拉格朗日乘子 \(\alpha_i > 0\)，而对应的样本情况恰好是样本在定义间隔 \(M\) 的超平面之一上，即样本为支持向量

相对应的，若最优解在内部取到，即 \(1-y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i+b) < 0\)，为满足解存在的必要条件，必有其对应的拉格朗日乘子 \(\alpha_i = 0\)，对应的样本情况是样本落在定义间隔 \(M\) 的超平面两边，不为支持向量

于是我们可以知道支持向量就是具有如下特征的样本点：

  • 落在定义间隔 \(M\) 设定的两个超平面之一上，负责“顶住” SVM
  • 对应的拉格朗日乘子 \(\alpha_i > 0\)，其余 \(\alpha_i\) 均为 0
  • 真正对 SVM 最后收敛起决定作用

另外有用的是，整个样本集中， 支持向量往往占少部分（大部分 \(\alpha_i = 0\)），当我们采用对偶形式表达 SVM 时，在推理等方面可以获得方便

对偶 SVM

联系支持向量与拉格朗日乘子的关系，我们可以改写 SVM 的基本形式

\[ \begin{aligned} y &= sgn(\mathbf{w}^\mathrm{T}\mathbf{x}+b)\\ y &= sgn((\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i)^\mathrm{T}\mathbf{x}+b)\\ y &= sgn(\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i^\mathrm{T}\mathbf{x}+b) \end{aligned} \]

因为大部分 \(\alpha_i = 0\)，我们可以只让支持向量参与推理

\[ y = sgn(\sum_{i\in SV}\alpha_iy_i\mathbf{x}_i^\mathrm{T}\mathbf{x}+b) \]

核方法在 SVM 的应用

增加维度

有些情况下，在当前的维度空间我们无法得到可行的线性划分，但能得到一个非线性的划分，此时我们常常考虑增加样本的输入维度，例如

\[ y = \mathbf{x}^\mathrm{T}\boldsymbol{\theta},\quad \mathbf{x} = [1,x^{(1)},x^{(2)},···,x^{(p)}]^\mathrm{T} \]

如果维度太低，我们考虑

\[ y = \phi(\mathbf{x})^\mathrm{T}\boldsymbol{\theta},\quad \phi(\mathbf{x}) = [1,x^{(1)},···,x^{(p)},(x^{(1)})^2,···,]^\mathrm{T} \]

这里拓展的维度项可以是任意的，上式只作为示意

一定存在高维线性可分吗？

如果数据被映射到足够高的维度，样本通常是线性可分的。VC（Vapnik-Chervonenkis）维数也给出过解释，这里只提及一下

核方法 | Kernel method

有对偶形式的 SVM

\[ y = sgn(\sum_{i=1}^n\alpha_iy_i\mathbf{x}_i^\mathrm{T}\mathbf{x}+b) \]

我们设计一个全新映射 \(\phi:\mathcal{R}^p \mapsto \mathcal{R}^k, k > p\) 来增加 SVM 输入空间的维度，则有

\[ y = sgn(\sum_{i=1}^n\alpha_iy_i\phi(\mathbf{x}_i)^\mathrm{T}\phi(\mathbf{x})+b) \]

注意到无论是拓展前后，\(\mathbf{x}_i^\mathrm{T}\mathbf{x}\) 与 \(\phi(\mathbf{x}_i)^\mathrm{T}\phi(\mathbf{x})\) 都是很优美的内积形式，我们可以考虑一些技巧，也就是所谓的 kernel trick，来进一步简化运算

常见的核 | Kernel

对于一些约定的基函数 \(\phi(\mathbf{x})\)，它们的内积可以写作更简洁的核函数形式

\[ K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^\mathrm{T}\phi(\mathbf{z}) \]

这相当于将基函数所展现的高维空间隐式的表达出来，同时减轻计算上的复杂程度，相当实用

  • Linear kernel（线性核）

    \[ K(\mathbf{x}, \mathbf{z}) = \mathbf{x}^\mathrm{T}\mathbf{z} \]

  • Polynomial kernel（多项式核）

    \[ K(\mathbf{x}, \mathbf{z}) = (1+\mathbf{x}^\mathrm{T}\mathbf{z})^d \]

    这里 \(d\) 视情况选取，例如如果选取 \(d = 2\)，对应的基函数便是

    \[ \phi(\mathbf{x}) = [1,\sqrt{2}x_1,···,\sqrt{2}x_p,x_1^2,···,x_p^2,\sqrt{2}x_1x_2,···,\sqrt{2}x_{p-1}x_p]^\mathrm{T} \]

    容易验证 \(K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^\mathrm{T}\phi(\mathbf{z})\)，且拓展后的维度 \(k = C_p^2+2p+1 > p\)，将原始数据映射到更高的维度，它包含了所有可能的二次项

  • Radial basis kernel （径向基核）

    \[ K(\mathbf{x}, \mathbf{z}) = e^{-r\Vert\mathbf{x}-\mathbf{z}\Vert^2} \]

    其中 \(r\) 是超参，其对应的基函数映射到无穷维空间

对偶 SVM 的 Kernel trick

回到开始我们为对偶 SVM 设计的维度拓展

\[ y = sgn(\sum_{i=1}^n\alpha_iy_i\phi(\mathbf{x}_i)^\mathrm{T}\phi(\mathbf{x})+b) \]

如果我们将其定义为多项式核的基函数，\(d\) 选取为 2，我们便可以不用处理额外的高维开销，而是将其内积巧妙的转化为核函数

\[ \begin{aligned} y &= sgn(\sum_{i=1}^n\alpha_iy_iK(\mathbf{x}_i,\mathbf{x})+b)\\ &= sgn(\sum_{i=1}^n\alpha_iy_i(1+\mathbf{x}_i^\mathrm{T}\mathbf{x})^2+b) \end{aligned} \]

对于优化形式，同样可以改写对偶问题

\[ \begin{aligned} \max &\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(\mathbf{x}_i,\mathbf{x}_j)\\ s.t. \quad &\sum_{i=1}^n\alpha_iy_i = 0;\\ &\alpha_i\geq0, \quad i=1,2···,n \end{aligned} \]

总结

核方法是一类把低维空间的非线性可分问题，转化为高维空间的线性可分问题的方法

核技巧利用核函数直接计算基函数内积，以避开计算基函数的高维映射，从而加速核方法

最后更新: 2024-01-12
创建日期: 2023-03-11

评论