支持向量机

• 什么是支持向量机
• 核心思想（1）：硬（软）间隔最大化
• 核心思想（2）：支持向量和间隔边界
• 核心思想（3）：对偶算法
  • 无约束最小化
  • 对偶问题的引入：拉格朗日乘子
  • Wolfe dual Lagrangian function
  • KKT条件
  • 软间隔条件下的对偶问题
• 核心思想（4）：合页损失函数（Hinge Loss ）
• 核心思想（5）：核函数
• 延伸：SMO算法
• 实际应用和代码展示
• SVM相关面经和其他资料
• 小结

什么是支持向量机？

支持向量机（Support Vector Machine, SVM）是一种二类分类器。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使其成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的**合页损失函数（Hinge Loss）**的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机以及非线性支持向量机。当数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器；当数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，也就是线性支持向量机，也叫做软间隔支持向量机；当数据线性不可分时，通过使用核技巧（kernel trick）以及软间隔最大化，学习非线性支持向量机。

核心思想：硬（软）间隔最大化、合页损失函数、决策边界、核函数

第一部分：硬（软）间隔最大化

首先，考虑一个二分类问题，我们假设给定一个特征空间上的训练数据集

$T = \{ (x_1,y1), (x_2,y_2), \cdots, (x_N,y_N)\}$

其中，$x_i = R^n, y_i = \{+1,-1\}, i = 1,2,\cdots,N$，$x_i$ 为第 $i$ 个特征向量，也称为实例，$y_i$ 为 $x_i$ 的类标记，我们的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类，分离超平面对应方程 $w\cdot x+b = 0$，它由法向量 $w$ 和截距 $b$ 决定，分离超平面将特征空间划分成两部分，一部分为正类（$y_i = +1$），一部分是负类（$y_i = -1$）。法向量指向的一侧为正类，另一侧为负类。

一般来说，在训练集线性可分，存在无穷个分离超平面进行分类，感知机利用误分类最小的策略，求分离超平面，这时解有无穷多个。线性可分支持向量机可以利用间隔最大化求最优分离超平面，这时，解是唯一的！

下面来说说间隔最大化，最直观的解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

具体来说，这个问题可以表示为下面的约束最优化问题：

$\max_{w,b} \quad \gamma$

$s.t. \quad y_i \Big(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}\Big)\geq\gamma, \quad i=1,2,\cdots,N$

我们希望最大化超平面 $(w,b)$ 关于训练数据集的几何间隔 $\gamma$，约束条件表示的是超平面关于美国训练样本点的几何间隔至少是 $\gamma$。

注意到函数间隔的取值并不影响最优化的解。事实上，假设将 $w$ 和 $b$ 按比例改变，这是函数间隔也按相应的比例改变，所以没影响，这样我们可以取 $\gamma = 1$。将其代入上面的式子，注意到最大化 $\frac{1}{||w||}$ 和最小化 $\frac{1}{2}||w||^2$ 是等价的，那么我们可以把问题转化成一个凸二次规划问题

十分重要！

$\min_{w,b} \quad \frac{1}{2}||w||^2$

$s.t. \quad y_i(w\cdot x_i+b) - 1 \geq 0, \quad i=1,2,\cdots,N$

下面来说一下什么是硬（软）间隔，我们知道SVM本质就是最大化margin，但是面对如下图所示的一些overlapping或者说是异常点，我们很难找到一个合适的决策边界来分类，但是我们如果绝对遵从正确分类的话，会造成下图右边的图片所示的情况，但是这明显有悖于我们全局边际最大化的初衷，自然我们要做些取舍，我们要允许错误分类（misclassification）从而保证全局最优化。

再从数学层面上解释为什么要引入软间隔最大化，是因为在面对线性不可分数据时，上述的不等式约束 $\quad y_i(w\cdot x_i+b) - 1 \geq 0, \quad i=1,2,\cdots,N$ 并不能都成立。

那为了解决这个问题，我们对每个样本点 $(x_i,y_i)$ 引入松弛变量 $\xi_i \geq 0$，使得函数间隔加上松弛变量大于等于1，这样，约束条件变为

$\quad y_i(w\cdot x_i+b) \geq 1 - \xi_i$

同时，对每个 $\xi_i$，支付一个代价 $\xi_i$，目标函数由原来的 $\frac{1}{2}||w||^2$变成

$\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$

这里的 $C>0$ 称为惩罚函数，$C$ 越大对错误分类的惩罚越大，而最小化 $\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$ 的意义在于两点：使得 $\frac{1}{2}||w||^2$ 尽量小也就是间隔尽量大，同时使错误分类点的个数尽量小。

所以我们有

$\min_{w,b,\xi} \quad \frac{1}{2}||w||^2 + C\sum_{i=1}^{N}\xi_i$

$s.t. \quad \quad y_i(w\cdot x_i+b) \geq 1 - \xi_i, \quad i=1,2,\cdots,N$

第二部分：支持向量和间隔边界

支持向量

在线性可分的情况下，训练集的样本点钟与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是使约束条件等式成立的点，即：

$\quad y_i(w\cdot x_i+b) - 1 = 0, \quad i=1,2,\cdots,N$

对 $y_i = +1$ 的正例点，支持向量在超平面

$H_1 = w\cdot x+b=1$

上，对 $y_i = +1$ 的负例点， 支持向量在超平面

$H_1 = w\cdot x+b=-1$

上。如下图所示，在 $H_1$ 和 $H_2$ 上的点就是支持向量。

间隔边界

注意到 $H_1$ 和 $H_2$ 平行，并且没有实例点落在其间。$H_1$ 和 $H_2$ 的距离叫做间隔（margin）。间隔依赖于分离超平面的法向量 $w$， 等于 $\frac{2}{||w||}$。$H_1$ 和 $H_2$ 称为间隔边界。

再决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解；但是如果在间隔边界意外移动其他实例点，甚至去掉这些点，则解不会改变。也就是说解只跟支持向量相关！

由于支持向量在确定分离超平面起着决定性作用，所以支持向量机就由此而来。一般来说，支持向量的个数相对较少，所以支持向量机由很少的“重要”样本确定。

第三部分：对偶算法

这一部分是SVM最核心也是最理论的部分，所以分成几小部分展开。

• 无约束最小化
• 对偶问题的引入：拉格朗日乘子
• Wolfe dual Lagrangian function
• KKT条件
• 软间隔条件下的对偶问题

无约束最小化

我们之前所讨论的最小化问题是带有边界条件的，也就是我们要满足数据集里所有的点到分离超平面的距离都要超过 $\frac{1}{||w||}$。那么我们如果不考虑限制条件只单纯的对函数最小化，问题会简单一些，也就是无约束最小化（Unconstrained minimization）。

定理：令 $f: \Omega \rarr \mathbb{R}$ 为在点 $x^*$ 的连续二阶导函数。如果 $x^*$ 满足 $\nabla f(x^*) = 0$ 并且 $\nabla^2 f(x^*)$ 是正定的（positive definite），那么 $x^*$ 是一个局部最小点。（证明，第11页）

敲黑板！！!

也就是说，如果 $x^*$ 满足：

1. $f$ 在 $x^*$ 梯度为 0：
   $\nabla f(x^*) = 0$
   并且
2. $f$ 在 $x^*$ 的海森矩阵（Hessian）是正定的：
   $z^T((\nabla^2 f(x^*))z>0, \forall z \in \mathbb{R}^n$
   其中
   $\nabla^2f(\mathbf x) = \begin{pmatrix}\frac{\partial^2f}{\partial x^2_1 } & \cdots & \frac{\partial^2f}{\partial x_1 \partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2f}{\partial x_n \partial x_1} & \cdots & \frac{\partial^2f}{\partial x^2_n}\end{pmatrix}$
   那么 $x^*$ 是一个局部最小点。

这里主要说一下海森矩阵

海森矩阵一般简写为 $H$， 但是我们在这里叫它 $\nabla^2 f(x^*)$，这里的 $\nabla^2$ 代表的是二阶偏导

我们把数据带进去是可以算出海森矩阵的，海森矩阵是一个关于一个标量函数的二阶偏导所构成的对称方阵，它描述了多变量函数的局部曲率。

下面说一下什么是正定

我们需要判断海森矩阵在 $x^*$ 是不是正定的。

定义：如果对于所有 $x \in \mathbb{R}^n$，如果 $x^TAx>0$，那么对称矩阵 $A$ （$A = A^T$）就叫作正定矩阵。

在这里我们把 $x$ 替换成 $z$， 把 $A$ 替换成 $\nabla^2 f(x^*)$，就得到

$z^T((\nabla^2 f(x^*))z>0, \forall z \in \mathbb{R}^n$

但是明显我们不能对于所有的 $z$ 进行尝试，好在我们有等价的满足条件来替换：

• $A$ 是正定矩阵
• $A$ 的所有特征值是正的
• $A$ 的所有主子式是正的
• 存在一个非奇异（可逆）矩阵 $B$ 使得 $A = B^TB$

具体如何判断请看这里!

如果我们能够找到所有满足以上两个条件的 $X$， 这里指的是向量，那么我们相当于找到了一个函数的局部最小值，但是局部最小值不等于全局最小值。

那么如何找到全局最小值呢？

1. 找到所有的局部最小值
2. 取最小的局部最小值

另一种方法是判定函数是不是凸函数，如果是的话，那么局部最小值就是全局最小值！如果有兴趣请看这里（强烈建议）

对偶问题的引入：拉格朗日乘子

那么终于来到了我们的主角：对偶问题

在数学优化理论中，对偶性意味着可以从原始问题或对偶问题（对偶性原理）这两个角度来看优化问题。对偶问题的解决方案为原始（最小化）问题的解决方案提供了下限。（维基百科）

什么是下限？

给个例子吧，加入我们有

$S = \{2,4,8,12\}$

• 因为1小于或等于2、4、8和12，所以我可以说1是S的下限。
• 例如，-3也是如此
• 即使它在S中，我们也可以称2为S的下限。

而且，因为2比任何其他下限大，所以我们可以给它起一个特殊的名字，我们称它为最大下限。

为什么要关心对偶呢？

是因为有时候解决对偶问题比解决原问题更加简单，如果你有一个最小化的问题，那么你也可以把他看做一个最大化问题。也就是当你在找这个问题的最小值时，其实这就是一个最小化问题的解的下界。

那么对偶的重要性体现在哪？

左边图中，我们可以看到在原问题中，我们要去对顶上的函数来最小化，它的最小值在 $P$ 处取到。如果我们来寻找一个对偶函数，我们就会分析下面这个图，其最大值在 $D$ 点取到，所以我们可以明确 $D$ 是一个下界，那么 $P-D$ 就是对偶间隙（duality gap），在这里，$P-D>0$ 也就是说存在弱对偶，而右边的图展示的是强对偶，也就是 $P-D=0$ 的情况。

之前介绍了无限制最优化问题的解决方法，下面说一下有限制条件的最优化问题解决方法。

一个最优化问题可以简单写成：

$\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)=0,\quad i=1,\dots ,p\\&&&h_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}$

这里，$f$ 称作目标函数，也叫损失函数，通过改变 $x$ 我们希望找到一个值 $x^*$ 使得 $f$ 在此达到最小值。

这里有 $p$ 个方程 $g_i$，其定义了等式约束，并且有 $m$ 个方程 $h_i$ 定义了不等式约束。

所以如何解决这种问题呢？

我们引入了拉格朗日乘子（Lagrange Multipliers），下面是维基百科中的英文解释。

In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints. (Wikipedia)

拉格朗日告诉我们如果要去寻找一个约束方程的最小值，那么我们需要去寻找使得 $\nabla f(x,y) = \lambda \nabla g(x,y)$。

那么 $\lambda$ 就是我们所说的拉格朗日乘子。注意到这个公式不要求梯度是有相同的方向的，因为 $\lambda$ 可以为负数，我们只需要保证他们是平行的，是因为这个方法不仅仅可以用来寻找最小值，也可以寻找最大值。

我们定义：

$L(x,\lambda, \eta) = f(x)+\sum_{i=1}^{m}\lambda_i g_i(x) + \sum_{i=1}^{p} \eta_ih_i(x)$

那么原问题等价于无约束形式：

$\min_{x}\max_{\lambda,\eta}L(x,\lambda,\eta)\quad s.t. \quad \lambda_i \geq 0$

这是因为当满足原问题的不等式约束时， $\lambda_i = 0$ 才能取得最大值，直接等价于原问题，如果不满足原问题的不等式约束，那么最大值就为正无穷，由于需要取到最小值，所以这种情况不存在。

这个问题的对偶形式：

$\max_{\lambda,\eta}\min_{x}L(x,\lambda,\eta)\quad s.t. \quad \lambda_i \geq 0$

所以对偶问题是关于 $\lambda, \eta$ 的最大化问题。

由于：

$\max_{\lambda_i,\eta_j}\min_{x}L(x,\lambda_i,\eta_j) \leq \min_{x}\max_{\lambda_i,\eta_j}L(x,\lambda_i,\eta_j)$

证：显然有
$\min_{x}L \leq L \leq \max_{\lambda,\eta}$
于是显然有
$\max_{\lambda, \eta} \min_{x}L \leq L$
且
$\min_{x} \max_{\lambda, \eta} L \geq L$

Wolfe dual Lagrangian function

下面我们对原问题进行对偶转化，看看是否能在原有的拉格朗日方程的基础上减少一些变量。

还记得朗格朗日方程是：

$L(w,b,\alpha) = \frac{1}{2}||w||^2-\sum_{i=1}^{m}\alpha_i[y_i(w \cdot x_i + b) -1]$

拉格朗日原问题是：

$\min_{w,b} \max_{\alpha} L(w,b,\alpha)$
$subject \ to \quad a_i \geq 0, \ i = 1, \cdots, m$

对于求解最小值问题，我们对 $L$ 关于 $w$ 和 $b$。

$\begin{aligned} \nabla_wL &= w - \sum_{i=1}^{m}\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b} &= -\sum_{i=1}^{m}\alpha_iy_i = 0 \end{aligned}$

通过第一个等式，我们有

$w = \sum_{i=1}^{m}\alpha_iy_ix_i$

我们把上式带入 $L$ 中化简得到：

$W(\alpha,b) = \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j - b\sum_{i=1}^{m}\alpha_iy_i$

到此，我们已经把 $w$ 去除了，根据 $\frac{\partial L}{\partial b}=0$，我们有：

$W(\alpha) = \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j$

上式也称为 Wolfe dual Lagrangian function

问题也被转化为了 wolfe 对偶问题：

$\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j$

$subject \ to \quad \alpha_i \geq 0, \ for \ any \ i = 1, \cdots , m$

$\sum_{i=1}^{m}\alpha_iy_i=0$

我们可以看到，这样一来我们的目标方程 $W$ 就仅仅取决于朗格朗日乘子了！

KKT条件

因为我们解决的问题包含不等式约束条件，那么这里有个额外的条件我们不得不满足：解必须满足 Karsuh-Kuhn-Tucker (KKT) 条件。

简单说，如果一个解满足KKT条件，那么可以保证它就是一个最优解。

KKT条件是：

• Stationary condition:
  $\begin{aligned} \nabla_wL &= w - \sum_{i=1}^{m}\alpha_iy_ix_i=0 \\ \frac{\partial L}{\partial b} &= -\sum_{i=1}^{m}\alpha_iy_i = 0 \end{aligned}$平稳性条件告诉我们，所选点必须是固定点。这一点函数值不再增加或减少的地方。在没有约束的情况下，平稳性
  条件就是目标函数的梯度为零的点。当有约束时，我们使用拉格朗日方程的梯度。

• Primal feasibility condition:
  $y_i(w \cdot x_i + b) - 1 \geq 0 \quad for \ all \ i = 1, \cdots,m$这是为了满足原方程在有不等式约束的情况下成立。

• Dual feasibility condition:
  $\alpha_i \geq 0 \quad for \ all \ i = 1, \cdots,m$同理，这是为了满足对偶问题所需要的条件。

• Complementary slackness condition:
  $\alpha_i [y_i(w \cdot x_i + b) - 1 ]=0 \quad for \ all \ i = 1, \cdots,m$我们要满足 $\alpha_i=0$ 或者 $y_i(w \cdot x_i + b) - 1=0$，支持向量拥有正的拉格朗日乘子。

所以接下来一旦我们有了拉格朗日乘子，就可以计算 $w = \sum_{i=1}^{m}\alpha_iy_ix_i$，$b = y_i - w \cdot x_i$。此外，我们可以使用更稳定的方法来求 $b$ 而不直接去任意的支持向量 $x_i$

$b = \frac{1}{S}\sum_{i=1}^{S}(y_i-w \cdot x_i)$

其中 $S$ 是支持向量的总个数。

软间隔条件下的对偶问题

之前说过了硬软间隔最大化的目的以及他们的区别，简而言之，硬间隔最大化面对异常值特别敏感，很容易造成过拟合，而软间隔基于硬间隔加入了松弛变量，从而容许分类器有错误分类的情况，从而对全局的分类效果更佳。

既然说到了松弛变量 $\zeta$，那么我们之前的限制条件：

$y_i(w \cdot x_i + b) \geq 1$

变成了：

$y_i(w \cdot x_i + b) \geq 1-\zeta_i$

但如果 $\zeta_i$ 取值太大的话，那么限制条件就不起作用了，所以我们要修改损失函数来惩罚值较大的 $\zeta_i$。

$\min_{w,b,\zeta} \frac{1}{2}||w||^2+\sum_{i=1}^{m}\zeta_i$

$subject \ to \quad y_i(w \cdot x_i + b) \geq 1 - \zeta_i \quad for \ any \ i = 1, \cdots , m$

这里，我们把所有的 $\zeta_i$ 加起来放到了损失函数里面，相当于一个惩罚项。总而言之，这样得到的解就是可以满足间隔最大化同时有最小的误差的超平面。

还有个问题就是，我们要保证 $\zeta_i \geq 0$，此外我们要加上一个控制变量 $C$ 来对松弛变量做调整，因为有可能我们还需要硬间隔法的存在，$C$ 的大小会决定 $\zeta$ 有多重要！

最终，对于软间隔情况，我们有：

$\min_{w,b,\zeta} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}\zeta_i$

$subject \ to \quad y_i(w \cdot x_i + b) \geq 1 - \zeta_i \quad \zeta \geq 0 \quad for \ any \ i = 1, \cdots , m$

同理，我们对于软间隔情况有类似的对偶转换：

$\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j$

$subject \ to \quad 0 \leq \alpha_i \leq C, \ for \ any \ i = 1, \cdots , m$

$\sum_{i=1}^{m}\alpha_iy_i=0$

由于损失函数加入了 $C\sum_{i=1}^{m}\zeta_i$，如果 $\alpha_i$ 大于 $C$，在经过拉格朗日方程的变换后，正则项就为负数了，所以要小于等于 $C$。

重点！！！

• 当 $C$ 很小时，我们会得到较为大的间隔，也就是会允许错误分类
• 当 $C$ 很大时，我们会得到一个硬间隔分类器，并不容忍错误分类的情况
• 关键就在于如何选择一个最适合的 $C$ 使得噪音数据不会太多影响结果

那么如何选择 $C$ 呢？我们可以使用 grid search 和 cross validation。

延伸

2-Norm soft margin

$\min_{w,b,\zeta} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}\zeta_i^2$

$subject \ to \quad y_i(w \cdot x_i + b) \geq 1 - \zeta_i \quad \zeta \geq 0 \quad for \ any \ i = 1, \cdots , m$

nu-SVM

由于 $C$ 的范围被特征空间所影响，这个方法用了参数 $v$，其值在 0 到 1 之间变动。

$\max_\alpha \ -\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j$

$subject \ to \quad 0 \leq \alpha_i \leq \frac{1}{m},$

$\sum_{i=1}^{m}\alpha_iy_i=0$

$\sum_{i=1}^{m}\alpha_i \geq v \quad \ for \ any \ i = 1, \cdots , m$

第四部分：合页损失函数（Hinge Loss）

那么我们继续说说 $C$ 的作用，它控制着支持向量机如何控制误差，

我们把支持向量机和逻辑回归的损失函数做一下对比：

• Logistic Regression
  $\min_{\theta}\frac{1}{m}\Big[\sum_{i=1}^{m}y^{(i)}(-log \ h_\theta(x^{(i)})+(1-y^{(i)})(-log(1-h_\theta(x^{(i)})))\Big]+\frac{\lambda}{2m}\sum_{j=1}^{n}\theta_j^2$
• SVM
  $\min_{\theta}C\Big[\sum_{i=1}^{m}y^{(i)}(cost_1(\theta^Tx^{(i)})+(1-y^{(i)})(cost_0(\theta^Tx^{(i)})\Big]+\frac{1}{2}\sum_{j=1}^{n}\theta_j^2$

注意到这里 $m$ 被去掉了，在第一部分我们提到了为什么，这里不再赘述，现在我们要研究的是 $cost_1$ 和 $cost_2$ 分别是什么。

如上图所示，当 $\theta^Tx^{(i)} \geq 1$，损失函数为 $0$，并且 $y^{(i)} = 1$；当 $\theta^Tx^{(i)} \leq -1$，损失函数为 $0$，并且 $y^{(i)} = 0$。

所以问题被转换成：

$\min_\theta \frac{1}{2}\sum_{j=1}^{n}\theta_j^2$
$$

$s.t. \quad\left\{ \begin{aligned} \theta^Tx^{(i)} &\geq 1 \quad if \ y^{(i)}=1\\ \theta^Tx^{(i)} &\leq -1 \quad if \ y^{(i)}=0 \end{aligned} \right.$

第五部分：核函数（kernel）

特征转换

思考一下，我们可以对非线性可分的数据进行分类么？也就是我们如果不能用一条直线或者一个平面对数据进行分类，我们要做的就是特征转换（feature transformation）。

举个例子，我们对于二维的向量 $(x_1,x_2)$，要把它转换为一个三维的向量，类似于我们通过方程 $\phi: \mathbb R^2 \rarr \mathbb R^3$ 实现多项式的转换。

$\phi(x_1,x_2) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)$

但是我们怎么确定要去选哪种转换方法呢？

这极大程度上取决于我们的数据集。选对正确的转换方法是成功之匙，但是并没有一个很明确的规定可以帮助我们确定选哪种转换方法，建议阅读一下scikit-learn的资料来加深对数据预处理的理解。

什么是核函数？

刚才我们提到了如何处理非线性可分的数据集，但是一大缺点就是我们必须对数据集中所有的点都进行转换，如果数据量太大的话，这个过程将会十分复杂，核函数应运而生！

在前一部分讨论支持向量机的对偶问题时，我们在 Wolfe 对偶拉格朗日方程中得到了满足 KKT 条件的拉格朗日乘子，其中我们是不需要计算每个训练样本的具体值的，我们实际只需要计算一对训练样本的点积 $x_i \cdot x_j$

$W(\alpha) = \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i \cdot x_j$

那么是否有一种办法在不对向量进行转化就能求出这个值呢？

核函数就是来干这个的！实际上，核函数就是可以返回另一个更高维的空间里的点积的函数。

Kernel Trick

那么我们可以定义一个核函数为 $K(x_i,x_j) = x_i \cdot x_j$，所以我们可以重新写出软间隔对偶问题如下：

$\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i K(x_i,x_j)$

$subject \ to \quad 0 \leq \alpha_i \leq C, \ for \ any \ i = 1, \cdots , m$

$\sum_{i=1}^{m}\alpha_iy_i=0$

核函数的种类

• 线性核函数（Linear kernel）
  $K(x,x') = x \cdot x'$
• 多项式核函数（Polynomial Kernel）
  $K(x,x') = (x \cdot x' +c)^d$
• 高斯核函数（RBF or Gaussian kernel）
  $K(x,x') = exp(-\gamma||x-x'||^2)$
  我们还记得核函数是可以通过转换维度来计算点积，那么高斯核函数是可以将点积映射到 $\mathbb R^\infty$ 空间，证明在这里。
  我们可以调节参数 $\gamma$，当 $gamma$ 特别小，模型跟线性SVM差不多，如果特别大，模型就会被每个支持向量严重影响（过拟合）。

• 其他

那么我们应该选用什么核函数最好呢？很抱歉这个也是没有固定方法的，一般来说，我们会先尝试高斯核函数（RBF），核函数作为一种表示两个向量间相似程度大小的方法，我们也可以自定义核函数来实现。

延伸：SMO算法

我们已经知道如何解决SVM最优化问题了，然而实际当中我们会用一个更好的方法来更快地解决这个问题：SMO算法。大多数机器学习的包都会用到SMO算法或其变式。

SMO算法解决下面的问题

$\min_\alpha \ \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i K(x_i,x_j) - \sum_{i=1}^{m}\alpha_i$

$subject \ to \quad 0 \leq \alpha_i \leq C, \ for \ any \ i = 1, \cdots , m$

$\sum_{i=1}^{m}\alpha_iy_i=0$

注意我们把之前的最大化改成最小化，并加了一个负号。这个就是之前我们的核函数化后的软间隔公式。下面是用 Python 实现的代码

def kernel(x1, x2): 
	return np.dot(x1, x2.T) 
def objective_function_to_minimize(X, y, a, kernel): 
	m, n = np.shape(X) 
	return 1 / 2 * np.sum([a[i] * a[j] * y[i] * y[j]* kernel(X[i, :], X[j, :]) 
	for j in range(m) 
	for i in range(m)])\ 
	- np.sum([a[i] for i in range(m)])

在我们处理非常大的数据集时，在利用凸优化包时常常会包含大量的矩阵运算，从而随着矩阵规模变大花费太多时间甚至超出存储范围。

SMO算法的核心思想

当我们求解SVM对偶问题时，我们可以随便改变拉格朗日乘子 $\alpha$ 的值只要我们满足限制条件。但是每次都更新 $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_m)$ 里的每一个又太慢了。

那么SMO算法的核心就是：给定一个 $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_m)$，我们只允许改变其中的两个 $\alpha$，一直调试直到损失函数返回其最小值，然后我们再挑其他两个 $\alpha$ 并重复此步骤。最终，我们就会求得原问题的损失函数的最小值。

SMO的一大优势在于求解两个拉格朗日乘子是可以求其分析解的。因此，尽管SMO 执行了更多的子优化问题，每一个子问题都会更快的被解决。

补充内容：

• CS 229, Autumn 2009 The Simplified SMO Algorithm
• Fast Training of Support Vector Machines using Sequential Minimal Optimization by John C. Platt （原论文）
• Sequential Minimal Optimization for SVM （理论推导）
• 机器学习算法实践-SVM中的SMO算法

强烈建议阅读前三个！

实际应用和代码展示

• Python

  • SVM in scikit-learn
  • In-Depth: Support Vector Machines

• R

  • SVM in R
  • SVM in R from DataCamp

SVM相关面经和其他资料

• 面经

  • 25 Questions to test a Data Scientist on Support Vector Machines
  • Support Vector Machines Interview Questions by Sasken Rams
  • 知乎SVM面经

• 其他资料

  • SVM in StatQuest
  • Understanding Support Vector Machine(SVM) algorithm from examples (along with code)
  • SVM的优缺点

小结

我们在本节中深度探讨了其原理、核心思想、数学推导、延伸算法以及代码实现。支持向量机（SVM）作为一个在特征空间里寻找最大间隔的线性分类器，由于分类结果仅跟支持向量有关，无需依赖全部数据，并在特征维度大于样本数时依然有很好的效果，通过使用核函数来灵活解决各种非线性的分类回归问题。