理论

支持向量机是一种二类分类模型。它的基本模型是定义在特征空间上的间隔(margin)最大的线性分类器。(间隔最大使它有别于感知机)

• 当训练样本线性可分时，通过硬间隔最大化学习到的分类器，叫线性可分支持向量机，也叫硬间隔支持向量机
• 当训练样本近似线性可分时，通过软间隔最大化学习到的分类器，叫线性支持向量机，也叫软间隔支持向量机
• 当训练样本线性不可分时，通过核技巧及软间隔最大化学习到的分类器，叫非线性支持向量机

上述三类支持向量机的求解，都是以间隔最大化为策略来确定待求分类器的目标函数(带约束的凸优化问题)，然后利用拉格朗日乘子法将带约束的原问题转为不带约束的原问题，接着利用拉格朗日的对偶性，将原问题等价地转为对偶问题(对偶问题易于求解，且带来内积，有利于利用核函数求解非线性问题)，最后通过SMO算法(利用KKT条件)求出对偶问题的最优解，从而得出原问题的最优解，即最终的最大间隔分离超平面。

顺口溜

SVM有三宝: 间隔、对偶、核技巧

数学描述

设特征空间的训练样本集记为

其中$x_i \in R^n,y_i\in \left\{ +1,-1 \right\},i=1,2,\cdots ,N$ ，$x_i$为第$i$个特征向量，$y_i$为$x_i$的类别标记。当$y_i=+1$时，$x_i$为正例；当$y_i=-1$时，$x_i$为负例。$\left( x_1,y_1 \right)$为样本点。

支持向量机的目标是在原特征空间的训练样本集上，通过间隔最大化的策略学习出一个分离超(平/曲)面$w^Tx+b=0$，使特征空间内的测试样本集通过分类决策函数$h\left( x \right) =\text{sign}\left( w^Tx+b \right)$被尽可能地正确分类。

硬间隔支持向量机

假设条件

• 特征空间中的训练数据集线性可分。即存在某个超平面能将数据集的正实例点和负实例点完全正确地划分到超平面的两侧。具体地，对所有$y_i=+1$的实例点，有$w^Tx+b>0$；对所有$y_i=-1$的实例点，有$w^Tx+b<0$。即只要有$y_i(w^Tx+b)>0$，则可保证所有正负实例点被正确地分类。

函数间隔与几何间隔

样本点$\left( x_1,y_1 \right)$到超平面$w^Tx+b=0$的函数间隔为

训练集$T$的函数间隔为所有样本点的函数间隔中最小的那个间隔，即

函数间隔可以表示分类的正确性(符号为正，分类正确)及确信度(大小)。当成比例改变$w$和$b$时，函数间隔也成比例的改变，但是超平面并没有改变。因此函数间隔无法唯一确定超平面。

基于上面的事实，进一步引出几何间隔以确定待求的超平面。

样本点$\left( x_1,y_1 \right)$到超平面$w^Tx+b=0$的几何间隔为

训练集$T$的几何间隔为所有样本点的函数间隔中最小的那个间隔，即

几何间隔是样本点到超平面的带符号的距离。当样本点被超平面正确分类时，几何间隔的符号为正，否则为负。

综上，几何间隔与函数间隔的关系为

(几何)间隔最大化

1. 最大几何间隔的分离超平面

   对线性可分的训练数据集来说，其分离超平面有无穷多个，但几何间隔最大的分离超平面是唯一的。几何间隔最大的分离超平面不仅将正负实例点分开，而且对离超平面最近的点也有足够大的确信度将其分开。上述分离超平面对未知的新实例会有较好的分类预测能力。其具体的数学描述如下：

   $$\underset{w,b}{\max}\gamma \ \qquad \ s.t.\ \qquad y_i\left( \frac{w}{\lVert w \rVert}\cdot x_i+\frac{b}{\lVert w \rVert} \right) \ge \gamma ,\ i=1,2,\cdots ,N$$

   上式表示最大化超平面关于训练样本集的几何间隔$\gamma$，且由几何间隔的定义知，每个样本点到分离超平面的几何间隔大于等于训练样本集到分离超平面的几何间隔。

   由几何间隔与函数间隔的关系，上述数学描述可改写为：

   $$\underset{w,b}{\max}\frac{\hat{\gamma}}{\lVert w \rVert}\ \qquad \ s.t. \ \qquad y_i\left( w\cdot x_i+b \right) \ge \hat{\gamma},\ i=1,2,\cdots ,N$$

   函数间隔$\hat{\gamma}$的取值并不影响上述最优化问题的解。为了方便推导计算，令$\hat{\gamma}=1$，又$\max \frac{1}{\lVert w \rVert}$与$\min \frac{1}{2}\lVert w \rVert ^2$是等价的，因此，最终的线性可分支持向量机的优化问题为：

   $$\underset{w,b}{\min}\frac{1}{2}\lVert w \rVert ^2 \qquad \ s.t. \qquad 1 - \ y_i\left( w\cdot x_i+b \right) \le 0,\ i=1,2,\cdots ,N \qquad \qquad \qquad (1)$$

   通过求出上述带约束的最优化问题的解$w^*,b^*$，可得最大间隔分离超平面$w^*\cdot x_i+b^*=0$及分类决策函数$h\left( x \right) =\text{sign}\left( w^*\cdot x_i+b^* \right)$

2. 支持向量和间隔边界

   在线性可分情况下，训练数据集的样本点中与分离超平面的几何间隔最近的样本点称为支持向量。即满足如下等式的点

   $$y_i\left( w^*\cdot x_i+b^* \right) - 1 = 0$$

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

   $$H_1:w^*\cdot x_i+b^*=1$$

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

   $$H_2:w^*\cdot x_i+b^*=-1$$

   $H_1$与$H_2$平行，且没有实例点落在它们之间。在$H_1$与$H_2$之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度($H_1$与$H_2$的距离)称为间隔(margin)，大小为$\frac{2}{\lVert w \rVert}$， $H_1$与$H_2$称为间隔边界。

   综上可知，分离超平面的确定只与支持向量有关，与其他实例点无关。即如果在间隔边界以外移动其他实例点，甚至去掉这些点，则分离超平面是不会改变的。

对偶算法

式$(1)$是一种带约束的凸优化问题，下面通过拉格朗日法求解式$(1)$的优化问题。

首先通过拉格朗日法将带约束的优化问题，转为无约束的优化问题(原问题)，接着利用拉格朗日的对偶性，通过求解对偶问题(dual problem)得到原始问题(primal problem)的最优解。

针对式$(1)$构造拉格朗日函数

其中$\alpha =\left( \alpha _1,\alpha _2,\cdots ,\alpha _N \right) ^T$为拉格朗日乘子向量。则式$(1)$可等效地转为如下的无约束原问题

并将式$(2)$的最优值记为$p^*$，表示原问题的最优值。

根据拉格朗日的对偶性，式$(2)$的对偶问题为

并将式$(3)$的最优值记为$d^*$，表示对偶问题的最优值。

由弱对偶的性质可知$d^* \le p^*$。又我们需通过求解对偶问题来等价地求解原问题，则需保证强对偶性，即$d^* = p^*$。而强对偶性需保证下面两个条件同时成立

• 优化问题为凸优化问题(求解 取最小值的目标函数为凸函数的一类优化问题)
• 优化问题满足KKT条件，从而保证在不等约束下，优化问题可以取到最优值

为了求解式(3)的对偶问题，需先求$L\left( w,b,\alpha \right)$对$w,b$的极小，再求对$\alpha$的极大。

(1) 求$\underset{w,b}{\min}L\left( w,b,\alpha \right)$，即

将推出的结论代入$L\left( w,b,\alpha \right)$后得:

即

(2) 求$\underset{w,b}{\min}L\left( w,b,\alpha \right)$对$\alpha$的极大，即

至此，已经将最初的原始问题$(1)$转换为相应的对偶问题$(4)$。

将式$(4)$的目标函数由求极大值转换为求极小值，可得如下等价的对偶最优化问题：

式$(5)$的优化问题可通过序列最小优化(SMO)算法求得最优解$\alpha ^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},\cdots ,\alpha _{N}^{*} \right) ^T$ ，由$\alpha ^*$可求得原问题$(1)$的最优解$w^*,b^*$。具体地，有如下定理：

设$\alpha ^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},\cdots ,\alpha _{N}^{*} \right) ^T$是对偶优化问题$(5)$的最优解，则存在下标$j$，使得$\alpha _{j}^{*} > 0 $，那么原问题$(1)$的最优解$w^*,b^*$可表示为:

证明:

由上述分析可得原问题$(1)$满足KKT条件，即

由此易得

$w^*=\sum_{i=1}^N{\alpha _{i}^{*}y_ix_i}$ (在已知$w^*$的条件下，只需选取$\alpha^*$的一个分量即可求出$b^*$)

且至少存在一个$\alpha _{j}^{*}>0$(用反证法假设$\alpha^{*}=0$,则$w^*=0$不是原问题的最优化解，矛盾),对此$j$根据KKT的对偶互补条件得:

又$y_{j}^{2}=1$且$w^*$已知，可得:

证毕。

综上，通过拉格朗日对偶法求得的分离超平面为

相应的分类决策函数为

remark(备注)

在由对偶问题的最优解$\alpha^*$反求原问题的最优解$w^*,b^*$时，$w^*,b^*$的确定只取决于训练数据中对应于$\alpha _{i}^{*}>0$的样本点，而与其他$\alpha _{i}^{*}=0$的样本点无关。训练数据中对应于$\alpha _{i}^{*}>0$的样本点称为支持向量。进一步地，由KKT互补条件可知，支持向量一定在间隔边界上。

软间隔支持向量机

假设条件

• 假设训练数据集不是线性可分的。即存在一些(少数)异常点(outlier)不能满足函数间隔大于等于1的约束条件。为了使学习到的分类器泛化性更强，允许有部分异常点不满足线性可分的条件，这样也可以防止过拟合问题的出现。(学习策略:在最大化间隔的同时，不满足约束的样本点尽可能的少)

数学描述

基于上述假设条件，可在原来线性可分支持向量机的目标函数$(1)$上，增加某种损失函数来表示可容忍的异常点的情况。一种是令损失函数为0/1损失函数,相应的目标函数可表示为

其中$C>0$表示惩罚超参数，$l_{0/1}$是0/1损失函数，且

当$C$为无穷大时，为了保证目标函数取得最小值，需要求$l_{0/1}=0$，即所有样本点严格满足硬间隔约束条件

当$C$取有限值时，允许部分样本点不满足硬间隔约束条件。

但由于$l_{0/1}$具有非凸、非连续的数学特性，导致目标函数不易求解，所以一般会采用以下的损失函数进行替代

• 合页(hinge)损失:$l_{hinge}\left( z \right) =\max \left( 0,1-z \right)$
• 指数损失:$l_{\exp}\left( z \right) =\exp \left( -z \right)$
• 对数损失:$l_{\log}\left( z \right) =\log \left( 1+\exp \left( -z \right) \right)$

这些函数都是凸、连续且是$l_{0/1}$的上界的函数。常见的软间隔支持向量机的目标函数采用合页损失，具体为 $\underset{w,b}{\min}\frac{1}{2}\lVert w \rVert ^2+C\sum_{i=1}^N{\max \left( 0,1-y_i\left( w\cdot x_i+b \right) \right)}$

忽略上述损失函数的视角，从松弛因子的视角看，即针对每一个样本点$(x_i,y_i)$引进一个松弛变量$\xi _i\ge 0$，使其函数间隔加上松弛变量大于等于1，这样式$(1)$中的约束条件变为:

目标函数变为

其中$C>0$表示惩罚超参数，$C$值越大对误分类的惩罚越大。式$(6)$表示使间隔尽量大的同时保证误分类点的个数尽量小，$C$是调和两者的系数。

式$(6)$是一种凸优化问题，因而解是存在的。可以证明$w$的解是唯一的，但$b$的解不唯一，存在于一个区间。

通过求解式$(6)$的带约束的凸优化问题的解$w^*,b^*$，可得最大间隔分离超平面为$w^*\cdot x_i+b^*=0$及分类决策函数$h\left( x \right) =\text{sign}\left( w^*\cdot x_i+b^* \right)$

对偶算法

与线性可分进行相似的处理。

首先，基于原问题式$(6)$的拉格朗日函数为

其中$\alpha _i\ge 0,\mu _i\ge 0$为拉格朗日乘子。

然后将原问题等价地转为对偶问题，经过相应转化后得到待求解的对偶问题的目标函数为:

式$(7)$的优化问题可通过序列最小优化(SMO)算法求得最优解$\alpha ^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},\cdots ,\alpha _{N}^{*} \right) ^T$ ，由$\alpha ^*$可求得原问题$(6)$的最优解$w^*,b^*,\xi^*$，进而确定分离超平面和决策函数。具体地，有如下定理：

设$\alpha ^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},\cdots ,\alpha _{N}^{*} \right) ^T$是对偶优化问题$(7)$的最优解，则存在下标$j$，使得$0 < \alpha _{j}^{*} < C $，那么原问题$(6)$的最优解$w^*,b^*$可表示为:

证明: 原问题$(6)$是凸优化问题，其最优解满足KKT条件，即

由式$(8)$可求得$w^*$，由式$(9)$–$(15)$可知，若存在$ 0 < \alpha _{j}^{*} < C$，则$\mu _{i}^{*} > 0,\xi _{i}^{*} = 0,y_i\left( w^*\cdot x_i+b^* \right) -1+\xi _{i}^{*} = 0$，从而有$y_i\left( w^*\cdot x_i+b^* \right) = 1$。两边同时乘以$y_i$并移项可得$b^*$。证毕。

综上，通过拉格朗日对偶法求得的分离超平面为

相应的分类决策函数为

支持向量

在线性不可分的情况下，将对偶问题$(7)$中的最优解$\alpha ^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},\cdots ,\alpha _{N}^{*} \right) ^T$中对应于$\alpha _{i}^{*}>0$的样本点$\left(x_i,y_i\right)$称为支持向量(软间隔支持向量)。具体支持向量的位置，有如下几种情况：

• 当$\alpha _{i}^{*}<C$时，由式$(9)$和式$(11)$可得$\mu _{i}^{*} > 0,\xi _{i}^{*} = 0$，从而有$y_i\left( w^*\cdot x_i+b^* \right) = 1$，即支持向量$x_i$恰好落在间隔边界上
• 当$\alpha _{i}^{*}=C， 0 < \xi _{i}^{*} < 1$时，分类正确，支持向量$x_i$在间隔边界与分离超平面之间
• 当$\alpha _{i}^{*}=C， \xi _{i}^{*} = 1$时，分类正确，分类错误，支持向量$x_i$在分离超平面上
• 当$\alpha _{i}^{*}=C， \xi _{i}^{*} > 1$时，分类正确，分类错误，支持向量$x_i$在分离超平面误分一侧

非线性支持向量机

假设条件

• 特征空间内的样本集无法在原特征空间内无法用线性分类器进行正确分类，只能利用非线性模型(分离超曲面)才能进行有效的分类。

核技巧

基于上述非线性情况，可通过一种非线性变换将原空间(欧式空间)中的输入特征映射到另一个高维空间(希尔伯特空间)，在高维空间中的样本集可利用线性模型进行分类。这就是核技巧在支持向量机中的应用。

下面给出核函数的定义:

若存在一个从欧式空间到希尔伯特空间的映射$\phi \left( x \right) :\mathcal{X}\mapsto \mathcal{H}$，使得对所有的$x,z \in \mathcal{X} $函数$K\left( x,z \right) $满足条件$K\left( x,z \right) =\phi \left( x \right) \cdot \phi \left( z \right)$，则称$K\left( x,z \right) $为核函数。其中$\phi \left( x \right) \cdot \phi \left( z \right)$表示$\phi \left( x \right)$和$\phi \left( z \right)$的内积。

说明

在SVM中运用核技巧时，无需显式地定义或求出映射函数$\phi \left( x \right)$，只需在训练和预测时提前指定一种核函数$K\left( x,z \right) $即可。(其为待调整的超参数)

具体地，核函数在SVM中的应用体现在将对偶问题和分类决策函数中实例的内积替换成核函数即可

也就是说，在核函数$K\left( x,z \right) $给定的条件下，可利用解线性分类问题的方法求解非线性分类问题的支持向量机。参数的学习是隐式地在原特征空间上进行的，不需要显式的定义高维空间和映射函数，这样的技巧称为核技巧。在实际应用中，往往依赖领域知识直接选择核函数，并在后期不断的调整优化。

正定核

上面提到的核函数默认是正定核函数。下面给出正定核的判定定理:

$K\left( x,z \right) $为正定核函数的充要条件是：在原空间中的特征样本集中，对任意的$x_i, i=1,2,…,N$,$K\left( x,z \right) $对应的Gram/Kernel矩阵

为半正定矩阵。

常用核函数

• 多项式核函数(polynomial kernel function)
  • 线性核是特殊的多项式核
• 高斯核函数(Gaussian kernel function),也叫RBF(Radial Basis Function) kernel
  • 使用前需将特征正规化
• sigmoid kernel
  • 相当于无隐层的神经网络
• 余弦相似核
  • 衡量两个输入向量的相似性，常用于比较两段文本的语义是否相似
• Chi-squared kernel
  • 衡量两个概率分布的相似性
  • 输入数据必须是非负的，并且使用了$L1$归一化

序列最小优化(SMO)算法

为什么不能利用梯度下降法进行求解?

SVM中有约束，无法直接对某一个变量进行更新，而SMO是利用KKT条件，在相关约束条件下将N个变量的优化问题进行分解求解，每次依此更新两个变量，直到更新完所有变量使其都满足KKT条件，从而得到最终的最优解。具体见支持向量机原理(四)SMO算法原理

支持向量机的多分类

两种方法

• OVR(one versus rest):当有$k$个类别时，训练$k$个SVM($f_i\left( x \right) =w_i\cdot x+b_i,i=1,2,\cdots ,k$)。当预测某个样本点$sx_j$的类别时，取$f_i\left( x_j \right)$值最大的那个类别做为预测类别。
  • 这种方法在训练时会出现样本不均衡的问题，不是很实用
• OVO(one versus one):当有$k$个类别时，任选其中的两个类别进行训练，最终得到$C_{k}^{2}=\frac{k\left( k-1 \right)}{2}$个SVM。当预测某个样本点的类别时，选取出现次数最多的类别做为预测类别。
  • 这种方法虽好，但当类别数很多时，待训练的模型数会比较多

支持向量机中的回归问题

支持向量机也可以用于回归问题。不过其训练复杂度为$O\left( N^3 \right)$,不适合训练样本集比较多的回归。

具体分析过程与分类问题相似，只是目标函数的约束条件有所不同而已。(支持向量机原理(五)线性支持回归)

SVM总结

优缺点

SVM算法是一个很优秀的算法，在集成学习和神经网络之类的算法没有表现出优越性能前，SVM基本占据了分类模型的统治地位。目前在大数据时代的大样本背景下,SVM由于其在大样本时有着超级大的计算量，热度有所下降，但是仍然是一个常用的机器学习算法。

SVM算法的主要优点有：

• 解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。

• 仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据。

• 有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题。

• 样本量不是海量数据的时候，分类准确率高，泛化能力强。

SVM算法的主要缺点有：

• 如果特征维度远远大于样本数，SVM表现一般。

• SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用。

• 非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数。

• SVM对缺失数据敏感。

SVM与LR(逻辑回归)的对比

• 两者的目标损失函数不同
  • LR为logistical loss，基于统计概率的，受数据分布的影响，与具体的取值无关，因此在训练前无需对数据进行normalization，通过极大似然估计的方法估计出参数的值；每一个样本点对模型参数的确定都有影响；
  • SVM为hinge loss，基于几何距离的，因此训练前需对数据进行normalization，其通过间隔最大化确定模型参数；模型的确定只依赖于少数的被称为支持向量的样本，非支持向量样本点的变动(增加/删除/移动)不会影响模型的参数；

• SVM的损失函数自带正则项($\frac{1}{2}\lVert w \rVert ^2$),是一种结构风险最小化模型(结构风险最小化指在训练误差和模型复杂度之间寻求平衡，防止过拟合，从而达到真实误差的最小化)，而LR必须另外在损失函数上添加正则项

• 在解决非线性问题时，SVM采用核函数的机制，而LR通常不采用核函数的方法(理论可以，但是由于LR中每个样本点都参与核计算,计算量过大)

使用情况参考：

当你的数据非常非常大然后完全跑不动SVM的时候，跑逻辑回归。SVM适合于小样本学习。

1、如果特征量相对于样本量来说比较大，此时可以应用逻辑回归，或LinearSVM。

2、如果特征量比样本量少，而样本量又不是特别大的话，此时可以应用SVM+Gaussian Kernel。

3、如果特征量比样本量少，而样本量又特别大的话，此时可以应用逻辑回归或LinearSVM。

展望

在工业界实际使用中，SVM用的不多，速度慢并且效果也很难保证，用好的特征+LR+regularization可以取得不错的效果，上线后响应速度快。

SVM是个被理论证明得很好的理论，实际应用挺弱的，还不如用一些简单的模型来说更好。如果真要取得更好的效果，建议学习一下Gradient Boosting Decision Tree，RandomForest等算法，提高分类的的Precision和Recall，SVM终归太偏理论了，不能说在工业界没有用，但是以现在的发展前景来看，SVM会慢慢被淡化的。

实战

使用SVM进行人脸识别

• svm.ipynb

使用SVM检测蘑菇🍄是否有毒

• mushrooms.csv
• SVM-Mushroom.ipynb

参考

• 统计学习方法
• 支持向量机原理篇之手撕线性SVM
• 我也支持向量机
• 机器学习-白板推导系列（六）-支持向量机SVM
• 深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件
• 机器学习：SVR支持向量机回归
• 【机器学习】SVR支持向量机回归
• 支持向量机原理(五)线性支持回归
• LR与SVM的异同
• SVM和logistic回归分别在什么情况下使用