SVM从入门到发疯

Apr 3, 2021

零、前言

支持向量机（Support vector machine, SVM）是一种用于二分类的线性分类器，区别于感知机，SVM使用中定义在特征空间上的间隔最大化分类器。支持向量机可以处理线性分类，引入核技巧后，支持向量机则成为一个非线性分类器。当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间的到的向量之间的内积。此时等价于在高维特征空间中学习一个线性分类器。

优化方面，支持向量机的学习目标是间隔最大化，本质上一个凸二次规划问题，也等价于正则化的合叶损失函数（Hinge loss）最小化问题。

下文以线性分类器开始，引入间隔最大化的目标函数，接着介绍硬间隔SVM和加入松弛因子的软间隔SVM，然后讨论用于求解带不等式约束优化问题的KKT条件、SVM目标函数的原始问题（Prime form）向对偶形式（Dual form）的转换，在此基础上，讨论在SVM中引入核技巧的方式，最后，对序列最小化算法（SMO）进行简单的介绍。

一、由线性分类器到间隔最大化

回顾线性分类问题：

输入：$D={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)},\quad x_i \in \mathbb{R}^D, y_i\in{-1,1},i=1,2,…,n$

参数：$W,b$

我们可以非常容易的找到一组参数$W,b$，由二者确定一个平面$W^T x+b=0$，使得对于正样本，我们有$W^T x_i+b \ge 0, y_i=1$；对于负样本，有$W^T x_i+b<0, y_i=-1$，因此有$(W^T x_i+b)y_i \ge 0$。

由于数据线性可分，我们可以找到无数组参数$W,b$，使得在给定数据集$D$上，满足上述条件。那么，这里就引出了一个问题，我们如何确定哪一个平面才是最优的呢？或者说，满足什么样条件的超平面才叫做“优”呢？

liner_problem

图1 线性分类问题

由上图可知，平面$1,2,3$都可以将正负样本完全分开，如果我们稍微调整一下距离平面$1$或$3$比较近的样本的位置，使其约过超平面，则平面$1,3$必须重新移动以满足$(W^T x_i+b)y_i \ge 0$的条件，而平面$2$对这种情况则更鲁棒一些。也就是说，直观上看平面$2$似乎是最优的，因为平面$1,3$对噪声不够鲁棒。

这里我们似乎找到了一些有关如何衡量“平面是更优的”的一个思路：对那些距离超平面近的点的波动不敏感。

接下来引入SVM的思想：

上文中讨论了当超平面将正负样本完全分开时，满足$(W^T x_i+b)y_i \ge 0$，这里定义函数间隔$\hat{\gamma}$：$\hat{\gamma}=(w^Tx+b)y$，数据集$D$中，所有样本的函数间隔最小值定义为超平面$ W,b$关于数据集$D$的函数间隔。

函数间隔存在一个问题，即它的值随$W,b$的变化而变化，考虑一种情况，当我们等比例将$W,b$放大为原来的两倍时，平面位置并没有发生移动，但超平面关于数据集的函数间隔却变成了原来的二倍。

针对上述情况，SVM中引入了几何间隔，它在函数间隔中考虑了$W$的模：$\gamma=\frac{\hat{\gamma}}{\Vert W \Vert}$，如果$\Vert W \Vert=1$，则函数间隔等于几何间隔，如果等比例改变$W,b$，函数间隔也随该比例变化，但几何间隔不变。

SVM的基本想法是，寻找一个超平面满足以下两个条件：

使得正负样本能够完全被分开
几何间隔最大

如前述，满足条件1的超平面有无数个，但满足条件2的超平面则是唯一的。

二、硬间隔和软间隔

2.1 线性可分数据

直观地考虑，距离超平面越近的点，其几何间隔越小，同时也越难正确分类，SVM的目标则是：不仅能够将正负样本完全分开，且能够以尽可能大的置信度将最难的样本正确分类。

上述SVM的基本想法，可以表示为如下的带约束最优化问题：

\[\max_\limits{w,b}\ \ \gamma\qquad s.t.\ \ y_i(\frac{w}{\Vert w \Vert}\cdot x_i + \frac{b}{\Vert w \Vert}) \ge \gamma,\ \ i=1,2,...,N\]

由函数间隔和几何间隔的关系，优化问题可以转化为：

\[\max_\limits{w,b}\ \ \frac{\hat{\gamma}}{\Vert w \Vert}\qquad s.t.\ \ y_i(w \cdot x_i + b) \ge \hat{\gamma},\ \ i=1,2,...,N\]

由于函数间隔的取值对约束条件没有影响，对优化目标也没有影响，这里可以将几何间隔取值为1，代入上式，产生一个等价的优化问题：

\[\max_\limits{w,b}\ \ \frac{1}{\Vert w \Vert}\qquad s.t.\ \ y_i(w \cdot x_i + b) \ge 1,\ \ i=1,2,...,N\]

最大化$\frac{1}{\Vert w \Vert}$和最小化$\Vert w\Vert^2$是等价的，因此将上述问题转化为一个凸二次规划问题（Convex QP）：

\[\min_\limits{w,b}\ \ \frac{1}{2} \Vert w \Vert^2\qquad s.t.\ \ y_i(w \cdot x_i + b) \ge 1,\ \ i=1,2,...,N\]

至此便得到了硬间隔的SVM的优化目标。

在上述硬间隔SVM的约束条件中，$y_i(w \cdot x_i + b) \ge 1$表示所有样本点到超平面的函数间隔均大于等于1，即超平面附近几何间隔小于1的区域不允许存在样本点。

2.2 线性不可分数据

上述学习目标对线性不可分的数据是不可用的（不等式约束不成立），如何将其扩展为支持线性不可分数据呢？可以修改其为软间隔，即在不等式约束条件中为每个样本点加入一个间隔松弛因子$\xi_i$：

\[y_i(w \cdot x_i + b) \ge 1-\xi_i\]

同时，对于引入的松弛变量，在目标函数中同步引入对其的惩罚：

\[\frac{1}{2} \Vert w \Vert^2 + C\sum_\limits{i=1}^N \xi_i\]

$C \gt 0$表示惩罚因子，$C$越大，对于误分类点的惩罚越大。

软间隔SVM的学习问题可以写为：

\[\min_\limits{w,b,\xi}\ \ \frac{1}{2} \Vert w \Vert^2 + C\sum_\limits{i=1}^N \xi_i\qquad s.t.\ \ y_i(w \cdot x_i + b) \ge 1,\quad \xi_i\ge 0,\quad i=1,2,...,N\]

这是一个凸二次规划问题，解$(w,b,\xi)$存在，可证明$w$唯一，但$b$不唯一，存在于一个区间。

求解得到最优参数$(w^\star,b^\star)$后，即得到分离超平面$w^\star \cdot x+b^\star=0$，通过符号函数来做决策：$f(x)=sign(w^\star\cdot x+b^\star)$。

三、KKT条件

KKT条件（Karush-Kuhn-Tucker conditions）是非线性规划问题取得最优解的必要条件，KKT条件将拉格朗日乘数法由等式约束问题推广到不等式约束问题。

3.1 等式约束优化

考虑如下包含等式约束的一般问题：

\[\min f(x)\quad s.t.\ \ g_i(x)=0,\ \ i=1,2,...,R\]

通过引入拉格朗日条件，将其转化为无约束优化问题：

\[L =f(x)+\sum_\limits{i=1}^R\lambda_ig_i(x)\]

目标函数转化为$\min_\limits{x,\lambda}L(x,\lambda)$，分别计算$L$对$x$和对$\lambda_i$的偏导数：

\[\nabla_xL=\frac{\partial L}{\partial x}=\nabla f + \lambda \nabla g=\mathbb{0}\] \[\nabla_{\lambda_i} L=\frac{\partial L}{\partial \lambda_i}=g_i(x)=0\]

上两式分别称为定常方程式和约束条件，解上述$R+1$个方程即可得到$x^\star$和$\lambda$。

3.2 不等式约束优化

考虑如下包含不等式约束的一般问题：

\[\min f(x)\quad s.t.\ \ h_i(x) \le 0,\ \ i=1,2,...,R'\]

其中，$h_i(x)\le 0$称为原始可行性（Primal feasibility），定义可行域：$K=\mathrm{x} \in \mathbb{R}^n \mid h_i(\mathrm{x})\le 0$。假设$\mathrm{x}^\star$为满足约束条件的最优解，则可以根据$h_i(\mathrm{x})$的取值讨论：

1）$h_i(\mathrm{x})\lt 0 $，此时最优解位于$K$的内部，称为内部解（interior solution），此时约束条件无效（inactive），问题退化为无约束最优化问题，此时$\nabla f=0$，$\mu=0$；

2）$h_i(\mathrm{x})=0$，此时最优解位于$K$的边界上，称为边界解（boundary solution），此时约束生效（active），不等式约束变为等式约束$h_i(x)=0$。则可知$\mathrm{x}^\star$发生于$\nabla f \in span \nabla $，即存h在$\lambda$使得：$\nabla f =-\mu \nabla h$，梯度$\nabla f$指向可行域$K$内部，但$\nabla h$指向$K$的外部（因为$h_i(x)\le 0$），由于我们希望最小化$f$，因此，$\mu \ge 0$，称为对偶可行性（Dual feasibility）；

综合上述两种情况，有$\mu h(x)=0$，此条件称为松弛互补条件（complementary slackness）。

3.3 KKT条件

对于一般的非线性规划问题：

\[\begin{align} \min\ \ &f(x)\quad \\ s.t.\ \ &g_i(x)=0,\ \ i=1,2,...,R\\&h_j(x)\le 0,\ \ j=1,2,...,R' \end{align}\]

定义拉格朗日函数：

\[L(\mathrm{x},\{\lambda\},\{\mu\})=f(\mathrm{x}) + \sum_\limits{i=1}^R\lambda_i g_i(x) + \sum_\limits{j=1}^{R'}\mu_j h_j(x)\]

优化问题转化为：

\[\begin{align}\min\ \ &L\\s.t.\ \ &g_i(x)=0,\ \ i=1,2,...,R\\&h_j(x) \le 0,\ \ j=1,2,...,R' \\ &\mu_j h_j(x)=0,\ \ j=1,2,...,R' \\ &\mu_j \ge 0,\ \ j=1,2,...,R' \end{align}\]

以上条件称为KKT条件。

3.4 补充

根据参考$^4$，严格来说，上述条件还不能完全称为KKT条件，因为其缺少一个regularity条件：

$f,g_1,g_2,…,g_R,h_1,h_2,…,h_{R’}$可微且一阶导数连续，可行解$x^{\star}$满足：

\[\{\nabla h_i (x^\star):i=1,2,...,R \} \bigcup \{ \nabla g_j(x^\star):j\in I(x^\star) \}\]

是线性独立的。

也即是说，使用KKT条件之前，需要先验证是否满足regularity条件，否则无法保证KKT条件给出的结论一定成立。

KKT条件在非线性规划问题中非常重要，原因有以下两点：

我们可以通过KKT条件排除非最优：由于KKT条件是取最优解的必要条件，因此对于不满足KKT条件的解，一定不是最优解；
指导算法的设计：对于满足最优性条件的优化问题，可以针对性地设计算法，考虑如何收敛到最优性条件中。

KKT条件所涉及的内容比较多，这里略去其余部分，有兴趣可以参考文章$^{4,5}$。

四、原始问题和对偶问题

以硬间隔SVM为例，其学习问题可以表示为：

\[\min_\limits{w,b,\xi}\ \ \frac{1}{2} \Vert w \Vert^2\qquad s.t.\ \ y_i(w \cdot x_i + b) \ge 1,\quad i=1,2,...,N\]

这是一个凸二次规划问题，可以直接使用现有的数值优化包进行求解。

为了能够：

使原问题的求解更容易
自然地引入核函数，并将线性SVM推广到非线性分类问题

可以通过拉格朗日对偶性将原问题转化为对偶问题，具体地，为每一个不等式约束引入拉格朗日乘子$\alpha_i\ge 0, i=1,2,…,N$，定义拉格朗日函数：

\[L(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_\limits{i=1}^{N} \alpha_{i} y_{i}\left(w \cdot x_{i}+b\right)+\sum_\limits{i=1}^{N} \alpha_{i}\]

其中，$\alpha=(\alpha_1,\alpha_2,…,\alpha_N)$为拉格朗日乘子向量，根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：$\max_\limits{\alpha} \min_\limits{w,b} L(w,b,\alpha)$，为了求解对偶问题的解，可以先求$L$对$w,b$的极小，再求对$\alpha$的极大。

（1）首先，$L$分别对$w,b$求偏导并令为$0$，得到：

\[\nabla_{w} L(w, b, \alpha)=w-\sum_\limits{i=1}^{N} \alpha_{i} y_{i} x_{i}=0\] \[\nabla_{b} L(w, b, \alpha)=-\sum_\limits{i=1}^{N} \alpha_{i} y_{i}=0\]

可以得：

\[w=\sum_\limits{i=1}^N\alpha_iy_ix_i,\quad \sum_\limits{i=1}^N\alpha_iy_i=0\]

利用上述结果，代入拉格朗日函数，得：

\[\begin{aligned} L(w, b, \alpha) &=\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i}\left(\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j}\right) \cdot x_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \\ &=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i} \end{aligned}\]

（2）求$\min_\limits{w,b}L(w,b,\alpha)$对$\alpha$的极大（原始问题的对偶问题）：

\[\begin{array}{ll}\max_\limits{\alpha} & -\frac{1}{2} \sum_\limits{i=1}^{N} \sum_\limits{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_\limits{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_\limits{i=1}^{N} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N\end{array}\]

求解出对偶问题的解$\alpha^\star$后，可证明$^{1-Theorem\ 7.2}$，存在下标$j$，使得$\alpha^\star \gt 0$，并可按照下式求的原始问题的解$w^\star,b^\star$：

\[w^{*}=\sum_\limits{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}\] \[b^{*}=y_{j}-\sum_\limits{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x_{i} \cdot x_{j}\right)\]

简单总结一下原始问题向对偶问题的转化：SVM的原始问题是一个极小极大问题（最小化最大间隔），通过拉格朗日对偶性转化为极大极小问题。

一般情况下，原始问题存在最优解，而对偶问题的解一般是次最优的（sub-optimal），两者之间的差距称作对偶间隙（duality gap），如果原始问题和对偶问题的对偶间隙为0，则称这两个问题是强对偶的。可以通过强对偶条件判断问题是否是强对偶的：

强对偶条件：如果满足原问题是凸优化问题，并且至少存在绝对一个绝对可行点（可以让所有不等式约束都不取等号的可行点），那么就具有强对偶性（Slater’s condition）。

强对偶条件有如下推论：只有等式约束的凸优化问题与其对偶问题一定具有强对偶性（因为没有不等式约束）。

SVM的原始问题和其对偶问题是满足强对偶条件的，所以可以通过求解对偶问题的最优解，进而获得原问题的最优解。

五、核技巧

对于线性分类问题，线性分类支持向量机十分有效，但面对非线性分类问题，则需要使用非线性支持向量机，其核心是采用核技巧，即使用一个映射函数$\phi(\cdot)$，将原有数据映射到一个更高维度的空间中，使数据变得线性可分。

5.1 核函数的定义

设$\mathcal{X}$是输入空间（欧氏空间$\mathrm{R}^{n}$的子集或离散集合），设$\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射：

\[\phi(x):\mathcal{X} \rightarrow \mathcal{H}\]

使得对于所有的$x,z\in \mathcal{X}$，函数$K(x,z)$满足条件：

\[K(x,z)=\phi(x)^T\phi(z)\]

则称$K(x,z)$为核函数，$\phi(x)$为映射函数，上式中$\phi(x)^T\phi(z)$为$\phi(x)$和$\phi(z)$的内积。

5.2 核技巧

核技巧的想法是，在训练和预测时只定义核函数$K(x,z)$，不显式定义映射函数$\phi$，通常，直接计算$K(x,z)$比较容易，而通过$\phi(x)$和$\phi(z)$计算$K(x,z)$则不容易。注意到，$\phi$是输入空间$\mathrm{R}^n$到特征空间$\mathcal{H}$的影射，而特征空间一般是高维甚至是无穷维的，可以看到，对于给定的核$K(x,z)$，特征空间$\mathcal{H}$和映射函数$\phi$的取法并不唯一。

例如：假设样本$x=(x_1,x_2)$，$y=(y_1,y_2)$同属于二维空间，假设有映射函数$\phi$，将二者映射到三维空间中：

\[\phi(x)=(x_1^2,x_2^2,\sqrt{2}x_1 x_2)\] \[\phi(y)=(y_1^2,y_2^2,\sqrt{2}y_1 y_2)\]

现在计算这两个样本在三维空间中的内积：

\[K(x,y)=\phi(x)^T \phi(y)=x_1^2y_1^2 + x_2^2 y_2^2 +2x_1y_1x_2y_2=(x_1y_1+x_2y_2)^2=(x^Ty)^2\]

可以看到，在影射后的空间中计算向量内积时，不依赖$\phi(\cdot)$的形式，只在原空间上计算出内积即可。

这里，我们可以仅定义$K(x,y)=(x^Ty)^2$，不显式地定义映射函数$\phi$。从而达到，既能将样本映射到高维空间中，又能避免在高维空间中做复杂的计算的目的。

5.2 核技巧在SVM中的应用

回顾线性支持向量机的对偶问题为：

我们将目标函数记为:

\[W(\alpha)= -\frac{1}{2} \sum_\limits{i=1}^{N} \sum_\limits{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_\limits{i=1}^{N} \alpha_{i}\]

将其中的内积$x_i^Tx_j$使用核函数$K(x,y)=\phi(x)^T\phi(y)$代替，同时，分类决策函数式也写为：

\[\begin{aligned} f(x) &=\operatorname{sign}\left(\sum_{i=1}^{N_{s}} a_{i}^{*} y_{i} \phi\left(x_{i}\right) \cdot \phi(x)+b^{*}\right) \\ &=\operatorname{sign}\left(\sum_{i=1}^{N_{o}} a_{i}^{*} y_{i} K\left(x_{i}, x\right)+b^{*}\right) \end{aligned}\]

这个过程相当于，经过映射函数$\phi$，将原有的输入空间映射到一个新的特征空间，将输入空间中的内积$x_i^Tx_j$变为特征空间中的内积$\phi(x_i)^T\phi(x_j)$，并在新的特征空间中训练样本学习线性支持向量机，当核函数为非线性函数时，对应的支持向量机实际上也就成为了非线性分类器。

值得注意的是，核技巧本身并不局限于支持向量机，在一般的机器学习问题中，如果其目标函数包含$x_i^Tx_j$项，均可以使用核技巧。

5.3 正定核

已知映射函数$\phi$，可以通过$\phi(x)$和$\phi(y)$的内积求得核函数$K(x,z)$，那么如果在不构造$\phi(x)$的情况下，能否直接判断函数$K(x,z)$是否是核函数呢？也即，$K(x,z)$满足什么条件时才能成为核函数？

上文所提到的核函数也就是正定核，下文给出正定核的充要条件：

正定核的充要条件：设$K: \mathcal{X} \times \mathcal{X} \rightarrow \mathrm{R}$是对称函数，则$K(x,z)$为正定核函数的充要条件为：对任意$x_i\in \mathcal{X},i=1,2,…,m$，$K(x,z)$对应的Gram矩阵：

\[K=[K(x_i,x_j)]_{m \times m}\]

是半正定矩阵。有关正定核的证明可参考$^{1-7.3.2}$。

5.4 常用核函数

多项式核

$K(x,z)=(1+x^Tz)^d$
高斯核

$K(x,z)=\exp(\frac{-\Vert x-z\Vert^2}{2\sigma^2})$
线性核

$K(x,z)=x^Tz$

六、SMO算法

SVM的学习问题可以转化为凸二次规划问题的求解，它具有全局最优解，可以使用许多最优化算法来求解，但是当训练集样本容量很大时，这些算法往往变得低效，为了高效地对SVM学习问题进行求解，研究者提出了许多实现方案，序列最小化算法（sequential minimal optimization, SMO）就是其中一种。