支持向量机(SVM)算法原理

machine-learning

---

本文主要介绍SVM的原理以及相关算法的简单推导，其中包括SVM原理，最初表达式，标准形式以及对偶形式(二次规划问题)，核函数以及软间隔。

什么是支持向量机

对于线性可分的数据，支持向量机就是条直线（对于高维数据点就算一个超平面），将不同类别的样本分开。但是能讲样本分开的平面有很多，怎样才算最完美的呢？最直观的想法是寻找对样本局部扰动容忍度最好的的超平面，这样的超平面可以通过下面条件找到。
1. 我们需要找到数据点中距离分割超平面距离最近的点（找最小）
2. 然后尽量使得距离超平面最近的点的距离的绝对值尽量的大（求最大）

这里数据点到超平面的距离就是间隔(margin)，当间隔越大，分类器就越稳健。
那些距离分割屏幕最近的点就是支持向量(Support Vectors)，如下图所示：

求解支持向量机

这部分总结如何求得超平面

划分超平面

在样本空间中，划分超平面可通过如下线性方程来描述：

$$w^Tx + b = 0$$ 其中$w = (w_1;w_2;...;w_d)$为法向量，决定了超平面的方向；$b$为位移项，决定了超平面与远点的距离。显然，不同的$w$和$b$确定不同的分个面。样本空间中任意一点$x$到超平面$(w, b)$的距离可写为 $$d = \frac{|w^Tx + b|}{||w||}$$ 假设超平面能将训练样本正确分类，如果数据点在分割平面上方则$w^Tx + b > 0$；数据点在分割平面下方，则$w^Tx + b < 0$。这样我们在表示任意数据点到分割面的距离就会很麻烦，但是我们通过将数据标签设为+1/-1将距离公式统一： $$d = y_i\cdot\frac{(w^Tx + b)}{||w||}$$

目标函数

我们现在已经有了间隔的公式，我们需要找到一组最好的$w$和$b$确定的分割超平面使得支持向量距离此平面的间隔最大。

直接形式

直接使用公式表示：

$$\arg\max_{w, b}\{\min_n\left(y_i\cdot\frac{(w^Tx_i + b)}{||w||}\right)\}$$
通俗翻译下就是现在数据点中找到距离分割平面最近的点(支持向量)，然后优化w和b来最大化支持向量到分割超平面的距离。

直接优化上面的式子很困难，我们需要做一些处理，使得同样的优化问题可以使我们用方便的优化算法来求解。

等比例改变参数w和b

首先看下分割超平面的一个性质。当我们等比例的扩大或缩小$w$和$b$并不会改变超平面的位置。例如对于位于三维空间中的二维平面$3x+2y+z+5=0$, $w=[3,2,1]^T$, $b=5$，我们扩大或者缩小$w$和$b$并不会影响平面，即$32+y+12z=0$与原始平面相同。
但是成比例改变$(w, b)$后，间隔也成比例的改变。

几何间隔和函数间隔

函数间隔：$\hat{\gamma}_i = y_i(w^Tx_i + b)$
几何间隔：$\gamma_i = \frac{y_i(w^Tx_i + b)}{||w||}$
这里给函数间隔的法向量除以$||w||$，以规范化，使得间隔确定。

标准形式

这里定义超平面$(w,b)$关于训练数据集的几何间隔为超平面关于所有样本点$(x_i, y_i)$的几何间隔最小值，即

$$\gamma = \min_n(\gamma_i) = \min_n(\frac{\hat{\gamma}}{||w||})$$ 我们的优化目标是最大化间隔，这里可以把最小化部分放到约束条件中，表示为： $$\arg\max_{w, b}\frac{\hat{\gamma}}{||w||}$$ subject to $$y_i\cdot(w^Tx_i + b) ≥ \hat{\gamma}, i = 1,2,...,k$$ 函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解。事实上，假设将$w$和$b$成比例改变为$\lambda w$和$\lambda b$，这时函数间隔变为$\lambda \hat{\gamma}$。函数间隔的这一改变对上面优化问题的不等式约束没有影响，对目标函数的优化也没有影响。这样，就可以取$\hat{\gamma} = 1$，代入上面的最优化问题，注意到最大化$\frac{1}{||w||}$和最小化$\frac{1}{2}{||w||}^2$是等价的，于是就得到下面的线性可分支持向量机的最优化问题 $$\arg\min_{w, b}\frac{1}{2}{||w||}^2$$ subject to $$y_i\cdot(w^Tx_i + b) ≥ 1, i = 1,2,...,k$$ 这是一个凸二次规划问题。能直接用现成的优化计算包求解，但我们可以有更高效的办法。

学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量的对偶算法。这样的优点：

• 对偶问题往往更容易求解
• 自然引入核函数，进而推广到非线性分类问题

首先构建拉格朗日函数。为此，对每个不等式约束引进拉格朗日乘子$\alpha_i \ge 0, i=1,2,...,N$，定义拉格朗日函数：

$$L(w,b,a) = \frac{1}{2}{||w||}^2-\sum^N_{i=1}\alpha_i[y_i\cdot(w^Tx_i + b) - 1] \tag{1}$$ 其中$\alpha_i > 0$。

根据拉格朗日函数对偶性，原始问题的对偶问题是极大极小问题：

$$\max_\alpha\min_{w,b}L(w,b,\alpha)$$ 所以，为了求解问题的解，需要先求$L(w,b,\alpha)$对$w,b$的极小，再求对$\alpha$的极大。

(1) 求$\min_{w,b}L(w,b,\alpha)$

将拉格朗日函数$L(w,b,\alpha)$分别对$w, b$求偏导数令其等于0：

$$\nabla_w L(w,b,\alpha) = w - \sum_{i=1}^N\alpha_iy_ix_i = 0$$ $$\nabla_b L(w,b,\alpha) = \sum_{i=1}^N\alpha_iy_i = 0$$ 得 $$w = \sum_{i=1}^N\alpha_iy_ix_i\tag{2}$$ $$\sum_{i=1}^N\alpha_iy_i = 0\tag{3}$$ 将式$(2)$代入朗格朗日函数$(1)$并利用式$(3)$，即得 $$\begin{align*}L(w,b,\alpha) &= \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum^N_{i=1}\alpha_i\left[y_i\cdot\left(\left(\sum_{j=1}^N\alpha_iy_jx_j\right)x_i + b\right) - 1\right] + \sum_{i=1}^N\alpha_i \\ & = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i\end{align*}$$ 即 $$\min_{w,b}L(w,b,\alpha) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i$$

(2) 求$\min_{w,b}L(w,b,\alpha)$对$\alpha$的极大

$$\max_\alpha-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i$$ subject to $$\sum_{i=1}^N\alpha_iy_i = 0$$ $$\alpha_i \ge 0, i=1,2,...,N$$ 将上式的目标函数由极大转换成极小，就得到下面与之等价的对偶最优化问题 $$\min_\alpha\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_i\tag{5}$$ subject to $$\sum_{i=1}^N\alpha_iy_i = 0$$ $$\alpha_i \ge 0, i=1,2,...,N$$ 从对偶问题解出的$\alpha_i$是原式中的拉格朗日乘子。注意到原式中有不等式约束，因此上述过程需要满足KKT条件，即要求 $$\left\{\begin{aligned}&\alpha_i \ge 0 \\ &y_if(x_i) - 1 \ge 0 \\&\alpha_i(y_if(x_i) - 1) = 0\end{aligned}\right.$$ 于是，对于训练数据$(x_i,y_i)$，总有$\alpha_i = 0$或$y_if(x_i) = 1$。若$\alpha_i = 0$，则该样本不会出现在上述求和公式中，也就不会对$f(x)$产生任何影响；若$\alpha_i > 0$则必有$y_if(x_i) = 1$，所对应样本点位于最大间隔上，是一个支持向量。这里显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量相关。

那么如何求解式(5)不难发现，这是一个二次规划问题，可使用通用的二次规划算法求解；然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高校的算法，SMO(Sequential Minimal Optimization)是其中一个著名的代表。详细的算法原理参看这篇文章

核函数

在上面的讨论中，我们都是假设训练样本是线性可分的。即存在一个划分超平面能将训练样本正确分类。然而现实任务中，原始样本空间中也许并不存在一个能正确划分两类样本的超平面。

对这一点问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个空间内线性可分。

令$\phi(x)$表示将$z$映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

$$f(x) = w^T\phi(x) + b$$ ，然后对偶形式中也有数据向量的乘积，于是便可以进行替换: $$\langle x_i, x_j\rangle \to \langle \phi(x_i), \phi(x_j)\rangle$$ 式(5)变为 $$\min_\alpha\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(\phi(x_i)\cdot \phi(x_j)) - \sum_{i=1}^N\alpha_i$$ 求解上式涉及到计算$\phi(x_i)\cdot \phi(x_j)$，这是样本$x_i$与$x_j$映射到特征空间之后的内积。由于特征空间维数很高，甚至可能是无穷维，因此直接计算$\phi(x_i)\cdot \phi(x_j)$通常是困难的。为了避开这个障碍，可以设想这样一个函数： $$K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j)$$ 即$x_i$与$x_j$在特征空间的内积等于他们在原始样本空间中通过函数$K(\cdot,\cdot)$计算的结果。有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积。

举一个例子来说明。$令 x=[x_1, x_2, x_3]^T,y=[y_1, y_2, y_3]^T$，我们定义$\phi(x)=[x_1x_1,x_1x_2,x_1x_3,x_2x_1,x_2x_2,x_2x_3,x_3x_1,x_3x_2,x_3x_3]$，将原始数据从三维空间映射到九维空间中，让我们来计算$\phi(1,2,3) \cdot \phi(4,5,6)$：

$$\begin{split} \phi(1,2,3)&=[1,2,3,2,4,6,3,6,9]^T\\ \phi(4,5,6)&=[16,20,24,20,25,30,24,30,36]^T\\ \phi(1,2,3) \cdot \phi(4,5,6) &=1\times16+2\times 20 + 3\times 24 + 2\times 20 + 4 \times 25 + 6 \times 30 + 3 \times 24 + 6 \times 30 + 9\times 36\\ &=16+40+72+40+100+180+72+180+324\\ &=1024 \end{split}$$
可以看出计算相当繁琐，嗯，我们来尝试找找对应的核函数：
$$\begin{split} \phi(x)\cdot \phi(y)&=[x_1x_1,x_1x_2,x_1x_3,x_2x_1,x_2x_2,x_2x_3,x_3x_1,x_3x_2,x_3x_3]^T\cdot [y_1y_1,y_1y_2,y_1y_3,y_2y_1,y_2y_2,y_2y_3,y_3y_1,y_3y_2,y_3y_3] \\ &= x_1y_1x_1y_1+x_1y_1x_2y_2+x_1y_1x_3y_3+x_2y_2x_1y_1+x_2y_2x_2y_2+x_2y_2x_3y_3\\&+x_3y_3x_1y_1+x_3y_3x_2y_2+x_3y_3x_3y_3\\ &=(x_1y_1+x_2y_2+x_3y_3)^2\\ &=(x^Ty)^2\\ &=K(x,y) \end{split}$$
通过上面的推导，我们发现虽然维度转化的过程较为繁琐复杂，但是矢量点积的结果确实相当简洁，这一次我们直接用核函数计算：
$$\begin{split} K(x,y)=K((1,2,3),(4,5,6))=(1\times 4 + 2\times 5 + 3\times 6)^2=(32)^2=1024 \end{split}$$
相比于从低维映射到高维空间再进行矢量积运算，核函数大大简化了计算的过程，使得向更高维转化变为了可能，我们不需要知道低维空间的数据是怎样映射到高维空间的，我们只需要知道结果是怎么计算出来的。

显然，如果知道合适映射$\phi(\cdot)$的具体形式，则可写出核函数$K(\cdot)$，但在现实任务中我们通常不知道$\phi(\cdot)$是什么形式，什么样的函数能做核函数呢？这里有一个定理：只要一个对称函数所对应的核矩阵是半正定的，它就能作为核函数使用。下表列出了几种常用的核函数。

名称	表达式	参数
线性核	$K(x_i,x_j) = x_i^Tx_j$
多项式核	$K(x_i,x_j) = (x_i^Tx_j)^d$	d >=1 为多项式的次数
高斯核	$K(x_i,x_j) = exp\left(-\frac{||x_i-x_j||^2}{2\sigma^2}\right)$	$\sigma>0$为高斯核的带宽
拉普拉斯核	$K(x_i,x_j) = exp\left(-\frac{||x_i-x_j||}{\sigma}\right)$	$\sigma>0$
Sigmoid核	$K(x_i,x_j) = \tanh(\beta x_i^Tx_j + \theta)$	$\tanh$为双曲正切函数，$\beta>0, \theta < 0$

我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及到输入与训练数据的内积。在对偶问题的目标函数中的内积$\langle x_i,x_j \rangle$可用核函数$K(x_i,x_j) = \phi(x_i)\cdot\phi(x_j)$来替代。此时的对偶的目标函数为

$$\min_\alpha\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^N\alpha_i$$ 同样，分类决策函数中的内积也可以用核函数来替代，而分类决策函数成为 $$f(x) = sign\left(\sum_{i=1}^N\alpha_iy_i\phi(x_i)\cdot\phi(x) + b\right) = sign\left(\sum_{i=1}^N\alpha_iy_iK(x_i, x) + b\right)$$

软间隔与正则化

在前面的讨论中，我们一直假定训练样本在样本空间或者特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。也有可能造成线性不可分的原因可能是存在一些噪声点的影响，完全按照原始的约束条件

$$yi(wTxi+b)≥1$$ ，意味着所有数据点距离分割平面的距离都大于1，可能会使SVM发生较大的误差，如下图

缓解办法是允许支持向量机在一些样本上出错。为此，要引入“软间隔”的概念。具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束，即所有样本都必须划分正确，这成为“硬间隔”，而软间隔则是允许某些样本不满足约束。为了能让达到此目的，我们可以引入一个松弛变量$ξ_i≥0$来允许错误的分类发生，也就是允许有间隔小于1的数据点出现, 即:

$$y_i(w^Tx_i+b)≥1−ξi$$

加入惩罚后，目标最优化间隔函数变为:

$$\arg\min_{w,b,ξ}\frac{1}{2}||w||^2 + C\sum_{i=1}^{N}ξ_i$$
subject to $$y_i(w^T+b)≥1−ξ_i \\ ξ_i≥0,i=1,…,N$$
其中$C$为惩罚因子来衡量惩罚的程度, $C$越大表明离群点越不被希望出现。

这仍是一个二次规划问题，于是，通过拉格朗日乘子法可得到下列朗格朗日函数

$$L(w,b,\alpha,ξ,\mu) = \frac{1}{2}{||w||}^2 + C\sum_{i=1}^{N}ξ_i +\sum^N_{i=1}\alpha_i[1 - ξ_i - y_i(w^Tx_i + b)] - \sum_{i=1}^N\mu_iξ_i$$ 其中$\alpha_i \ge 0, \mu_i \ge 0$是拉格朗日乘子。

令$L(w,b,\alpha,ξ,\mu)$对$w,b,ξ_i$的偏导为零可得

$$w = \sum_{i=1}^N\alpha_iy_ix_i\\ 0 = \sum_{i=1}^N\alpha_iy_i\\ C = \alpha_i + \mu_i$$

然后将上式回代，我们求此问题的对偶问题:

$$\min_\alpha\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_i\tag{5}$$ subject to $$\sum_{i=1}^N\alpha_iy_i = 0$$ $$0 \le \alpha_i \le C, i=1,2,...,N$$

可见，软间隔SVM的目标函数形式同硬间隔的形式相同，唯一不同的就在于$\alpha_i$的范围。

参考文档

机器学习-周志华
统计学习方法-李航
机器学习算法实践-支持向量机(SVM)算法原理
支持向量机