支持向量机（SVM）

• SVM 是一种监督学习二元分类器，通过核函数将线性不可分变成线性可分，同时在实践中也是小样本学习效果最好的算法。

支持向量

• 关于线性分类的概念请参考逻辑回归，对于不同的分类器可能会得到不同的拟合结果，例如

  

  线性分类器

  上图中是三个分类器得到的决策边界，对于蓝色和黄色分类器，不能将正负类别分开，拟合能力较弱，同时对于黑色分类器来说，其不仅可以达到分类效果，还满足距离两个类别的最近样本最远。而这两个类别中离决策边界最近的样本我们称其为支持向量，其与决策边界之间的距离称为 margin。

  当从二维扩展到多维空间时，决策边界将变成一个超平面，我们同样是寻找满足下面条件的拟合结果：

  1. 两类样本分别在超平面的两侧；
  2. 最大化支持向量与超平面之间的距离。

• 对于一个超平面我们可以用如下线性方程来描述

  $$\boldsymbol{w}^T\boldsymbol{x} + b = 0$$

  同时在$n$ 维空间中，点$\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ 到这个平面的距离为

  $$d = \frac{|\boldsymbol{w}^T\boldsymbol{x} + b|}{\Vert \boldsymbol{w}\Vert}$$

  其中$\Vert \boldsymbol{w}\Vert = \sqrt{w_1^2+w_2^2+\cdots+w_n^2}$，我们可以设支持向量到超平面的距离为$d$，其他样本到超平面的距离大于$d$。为了方便我们将正向类别定义为$y=1$，负向类别定义为$y=-1$，此时我们得到超平面的一个约束

  $$\begin{cases} \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert} \ge d &,y=1\\ \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert}\le -d &, y=-1 \end{cases}$$

  同时我们两边乘以$\Vert \boldsymbol{w}\Vert$变成

  $$\begin{cases} \boldsymbol{w}^T\boldsymbol{x} + b \ge \Vert \boldsymbol{w}\Vert d &,y=1\\ \boldsymbol{w}^T\boldsymbol{x} + b\le -\Vert \boldsymbol{w}\Vert d &, y=-1 \end{cases}$$

  因为$\Vert \boldsymbol{w}\Vert d$ 是正数，我们可以移走或者说令其等于 1 简化算式（这对后续的优化没有影响），并且合并两个算式，得到

  $$y(\boldsymbol{w}^T\boldsymbol{x} + b)\ge 1$$

  由于该式恒大于 0，故有$y(\boldsymbol{w}^T\boldsymbol{x} + b) = |\boldsymbol{w}^T\boldsymbol{x} + b|$，所以之前的距离公式可以改为

  $$d = \frac{y(\boldsymbol{w}^T\boldsymbol{x} + b)}{\Vert w\Vert}$$

  而我们的目标则是最大化这个距离，同时对于支持向量有$y(\boldsymbol{w}^T\boldsymbol{x} + b)=1$，所以最大化的目标为

  $$\gamma = \max(\frac{2}{\Vert \boldsymbol{w}\Vert})$$

  乘 2 的目的和 MSE 中乘 2 类似，不影响性质的情况下简化后续的运算。

  

  来源【机器学习】支持向量机 SVM

• 同时这里还可以进一步转换将目标变为求

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert)$$

  去除掉除法，同时为了去除模长的根号可以再添加一个平方变为

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert^2)$$

  其中$y^{(i)}(\boldsymbol{w}x^{(i)} + b)\ge 1$

拉格朗日乘数法

• 要求解上述目标的最小值，我们可以使用高数中的拉格朗日乘数法来求解目标函数在约束条件下的最小值。

  当然高数中的约束一般是一个等式，而这里是一个不等式，所以还要引入一个新东西：松弛变量，它的作用是将不等式变为等式再求解。

  我们的目标函数以及约束函数为

  $$f(\boldsymbol{w}) = \frac{1}{2}\Vert w\Vert^2\\ g_i(\boldsymbol{w}) = 1 - y^{(i)}(\boldsymbol{w}^Tw^{(i)}+b)\le 0$$

  引入松弛变量$a_i^2$，得到$h_i(\boldsymbol{w}, a_i) = g_i(w) + a_i^2$。此时我们得到拉格朗日函数

  $$L(\boldsymbol{w}, \lambda, a) = f(\boldsymbol{w}) + \sum_{i=1}^n{\lambda_i[g_i(\boldsymbol{w})+a_i^2]},\ \ \lambda_i\ge 0$$

  然后就是解拉格朗日方程了，这里还涉及到 KKT 乘子的证明，不在这里展开，可能会在数学基础中单独讲。总之最后得到的目标转化为

  $$\min\limits_{\boldsymbol{w}} \max\limits_\lambda L(\boldsymbol{w}, \lambda),\ \ \lambda_i\ge 0$$

对偶问题

• 对于上述问题，我们可以寻找它的对偶问题

  $$\max\limits_\lambda\min\limits_{\boldsymbol{w}} L(\boldsymbol{w}, \lambda),\ \ \lambda_i\ge 0$$

  假设存在函数$f$ 满足$\min\max f\ge \max\min f$，即最大值中的最小值也比最小值中的最大值要大，这被称为弱对偶关系。

  同时存在强对偶关系，即满足

  $$\min \max f = \max \min f$$

  如果$f$ 是凸优化问题，则强对偶性成立，之前的提到的 KKT 条件是强对偶性的充要条件。

SVM 求解

• 利用强队偶性再次转化目标后，我们可以对其中的拉格朗日函数求解了，这里也跳一些内容，结果为

  $$\max\limits_\lambda[\sum_{j=1}^n\lambda_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n{\lambda_i\lambda_j}y^{(i)}y^{(j)}(x^{(i)}\cdot x^{(j)})], \ \ \sum_{i=1}^n\lambda_iy^{(i)} = 0\ \ \lambda_i\ge 0$$

  这个问题可以用 SMO 算法求解，不是这里的重点，同跳过。

软间隔

• 上述讲了一大堆，实际上都是要求数据完全线性可分的情况，但有时我们会遇到一些线性不可分的情况，例如

  

  来源【机器学习】支持向量机 SVM

  此时我们放宽 SVM 的条件，增加软间隔，也就是允许个别样本出现在间隔带内（距离小于$d$），例如

  

  来源【机器学习】支持向量机 SVM

  至于多软呢，将定义一个松弛变量$\xi_i\ge 0$，满足

  $$y^{(i)}(\boldsymbol{w}x^{(i)} + b)\ge 1 - \xi_i$$

  此时优化目标变成了

  $$\min\limits{\boldsymbol{w}}\frac{1}{2}\Vert \boldsymbol{w}\Vert^2 + C\sum_{i=1}^m\xi_i,\ \ y^{(i)}(\boldsymbol{w}x^{(i)} + b)\ge 1 - \xi_i$$

  其中$C$ 是一个大于 0 的常数，类似正则化，这里也是代表对错误样本的惩罚程度。后续的内容的化依然和上面一样使用拉格朗日乘数法求解。

  重要

  对于软间隔中的那部分样本依然也是支持向量，因为对支持向量的定义便是影响决策边界即超平面的样本，它们依然会影响所以也是支持向量。

核函数

• 对于非线性可分的数据，我们可以使用核函数将低维空间的数据映射到高维，这样线性不可分的数据将变得线性可分。（这个思路确实🐂🍺）

  线性不可分

  这是逻辑回归中圆形决策边界的例子，显然这是一个线性不可分的数据集，那么通过核函数我们可以进行升维后变为

  显然此时在低维中线性不可分的样本将其映射到更高维度的空间后，便可以通过 SVM 进行线性分类了。

  对于样本$\boldsymbol{x}$，用 $\phi(\boldsymbol{x})$ 表示升维后的新向量，则超平面方程变为

  $$f(\boldsymbol{x}) = \boldsymbol{w}^T\phi(\boldsymbol{x}) + b$$

  同时优化目标函数的对偶问题将变成

  $$\min\limits_\lambda\left[\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy^{(i)}y^{(j)}\left(\phi(x^{(i)})\cdot\phi(x^{(j)})\right) - \sum_{j=1}^n\lambda_i\right]$$

  其中$\sum_{i=1}^n\lambda_iy^{(i)} = 0, \ \lambda_i\ge 0,\ C-\lambda_i - \mu_i = 0$

• 这时我们发现式子除了多了一层$\phi$ 外也没啥变化，那核函数到底是啥呢？

  将低维空间映射到高维后维度可能会很大（可能不止升一维），此时如果将全部样本的点乘两两计算一遍计算量太大。所以我们需要引入核函数

  核函数（kernel function）：是计算两个向量内积的函数，例如有核函数

  $$k(\boldsymbol{x}, \boldsymbol{y}) = (\phi(\boldsymbol{x}), \phi(\boldsymbol{y}))$$

  则$\boldsymbol{x}$ 与$\boldsymbol{y}$ 在特征空间的内积等于它们在原始样本空间通过函数$k(\boldsymbol{x},\boldsymbol{y})$ 的结果，就不再需要计算高维空间的内积了。也就是将优化目标中的$\phi$ 用核函数替换。

  例如对于一个多项式核函数$k(\boldsymbol{x}, \boldsymbol{y}) = (\boldsymbol{x}\cdot \boldsymbol{y} + 1)^2$

  带入样本点后变成

  $$k(\boldsymbol{x}, \boldsymbol{y}) = (x^{(i)}\cdot y^{(i)} + 1)^2$$

  展开后变成

  $$(x^{(i)}\cdot y^{(i)})^2 + 2x^{(i)}\cdot y^{(i)} + 1$$

  而如果使用$\phi$ 函数的话，则需要将向量映射为

  $$\boldsymbol{x}^{'} = (x_1^2, \dots, x_n^2,\sqrt{2}x_1,\dots,\sqrt{2}x_n, 1)$$

  进行计算内积才能与该多项式核函数达到相同效果

  $$\boldsymbol{x}^{'}\cdot \boldsymbol{y}^{'} = (x^{(i)}\cdot y^{(i)})^2 + 2x^{(i)}\cdot y^{(i)} + 1$$

• 核函数的本质就是定义了一个输入空间到高维特征空间的映射，使得我们不需要显式的进行映射后再进行内积而是可以直接得到同性质的结果。

  当然为什么核函数有这个性质呢，这涉及到希尔伯特空间的一些性质。看后续是否有机会单独开一篇记录。

  同时要注意核函数并不是 SVM 解决非线性分类的方案，只是用核函数避免了维数灾难的问题。

• 最后还要一提的是，核函数的选取是有些困难的，常见有三种核函数

  1. 线性核函数

     $$k(\boldsymbol{x}, \boldsymbol{y}) = \boldsymbol{x}^T\boldsymbol{y}$$

  2. 多项式核函数

     $$k(\boldsymbol{x}, \boldsymbol{y}) = (\boldsymbol{x}^T\boldsymbol{y})^d$$

  3. 高斯核函数

     $$k(\boldsymbol{x}, \boldsymbol{y}) = \exp\left(-\frac{\Vert \boldsymbol{x} - \boldsymbol{y}\Vert}{2\delta^2}\right)$$

     $\delta$ 也是需要手动确定的。

总结

• SVM 有严格的数学理论支持，不依靠统计方法，简化了通常的分类核回归问题，同时引入了支持向量的概念，集中关注对任务重要的关键样本，而不是和传统模型一样尝试拟合所有样本。

  同时 SVM 的复杂度取决于支持向量的数目而不是样本空间的维数，也是优点之一。

• 同样 SVM 也有缺点，其采用的 SMO 算法每次都需要挑选一对参数，时间复杂度较高训练时间较长。且使用核技巧时虽然避免了维数灾难但若需要存储核矩阵，需要$O(N^2)$ 的空间复杂度。

  当支持向量数目较多时，SVM 并不一定是一个好的选择，所以 SVM 在小样本任务上效果很好，但对于太大的样本任务表现并不一定很好。