一、简介

支持向量机（support vector machines）是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

• 当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机；
• 当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机；
• 当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机；

二、支持向量机原理

1、间隔最大化和支持向量

首先我们先来了解下什么是线性可分。
如果一个线性函数能够将样本分开，称这些数据样本是线性可分的。我们看一个简单的二维空间的例子，O代表正类，X代表负类，样本是线性可分的，但是很显然不只有这一条直线可以将样本分开，而是有无数条，我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。

线性可分严格的数学定义是：
$D_0$D0​和 $D_1$D1​是 n 维欧氏空间中的两个点集。如果存在 n 维向量 w 和实数 b，使得所有属于$D_0$D0​的点 $x_i$xi​ 都有 $wx_i+b>0$wxi​+b>0 ，而对于所有属于 $D_1$D1​的点$x_j$xj​ 则有 $wx_j+b<0$wxj​+b<0 ，则我们称 $D_0$D0​和$D_1$D1​ 线性可分。
最大间隔超平面
从二维扩展到多维空间中时， $D_0$D0​和 $D_1$D1​完全正确地划分开的$wx_i+b=0$wxi​+b=0 就成了一个超平面。

为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

• 两类样本分别分割在该超平面的两侧；
• 两侧距离超平面最近的样本点到超平面的距离被最大化了。
  支持向量
  
  样本中距离超平面最近的一些点，这些点叫做支持向量。

2、线性可分支持向量机原理推导

下面我们开始计算间隔，其实间隔就等于两个异类支持向量的差在 w 上的投影，即：

其中${\vec{x}}_{+}$x+​和${\vec{x}}_{-}$x−​分别表示两个正负支持向量，因为${\vec{x}}_{+}$x+​和${\vec{x}}_{-}$x−​满足 $y_i(w^Tx_i+b)=1$yi​(wTxi​+b)=1，即：

推出：

代入公式（4）中可以得到：

至此，我们求得了间隔，SVM的思想是使得间隔最大化，也就是：

显然，最大化 $\frac{2}{∣∣w∣∣}$∣∣w∣∣2​相当于最小化 ||w||，为了计算方便，将公式（6）转化成如下：

公式（7）即为支持向量机的基本型。

对偶问题

公式（7）本身是一个凸二次规划问题，可以使用现有的优化计算包来计算，但我们选择更为高效的方法。对公式（7）使用拉格朗日乘子法得到其对偶问题，该问题的拉格朗日函数可以写为：

公式（8）分别对 w 和 b求偏导：

令其分别为0，可以得到：

将公式（9）（10）代入公式（8），可得：

此时，原问题就转化为以下仅关于 $\alpha$α 的问题：

解出 $\alpha$α 之后，根据公式（9）可以求得 w ， 进而求得 b，可以得到模型：

上述过程的KKT条件为：

我们分析一下，对于任意的训练样本 $(x_i,y_i)$(xi​,yi​)
若$α_i=0$αi​=0 则其不会在公式（13）中的求和项中出现，也就是说，它不影响模型的训练；
若${{\alpha }_{i}}>0$αi​>0，则$y_if(x_i)−1=0$yi​f(xi​)−1=0 ，也就是$y_if(x_i)=1$yi​f(xi​)=1​，即该样本一定在边界上，是一个支持向量。

这里显示出了支持向量机的重要特征：当训练完成后，大部分样本都不需要保留，最终模型只与支持向量有关。

3、非线性支持向量机和核函数

对于非线性问题，线性可分支持向量机并不能有效解决，要使用非线性模型才能很好地分类。先看一个例子，如下图，很显然使用直线并不能将两类样本分开，但是可以使用一条椭圆曲线（非线性模型）将它们分开。非线性问题往往不好求解，所以希望能用解线性分类问题的方法求解，因此可以采用非线性变换，将非线性问题变换成线性问题。

这种情况的解决方法就是：将二维线性不可分样本映射到高维空间中，让样本点在高维空间线性可分，比如：

如果原始空间维数是有限的，即属性是有限的，那么一定存在一个高维特征空间是样本可分。令
ϕ(x)表示将 x 映射后的特征向量，于是在特征空间中，划分超平面所对应的的模型可表示为：

$f(x)={{w}^{T}}\phi (x)+b$f(x)=wTϕ(x)+b （14）
于是有最小化函数：

其对偶问题为：

若要对公式（16）求解，会涉及到计算$\phi ({{x}_{j}})^Tϕ(x_j​)$ϕ(xj​)Tϕ(xj​​)，这是样本 $x_i和x_j$xi​和xj​ 映射到特征空间之后的内积，由于特征空间的维数可能很高，甚至是无穷维，因此直接计算 $ϕ(x_i​)^Tϕ(x_j​)$ϕ(xi​​)Tϕ(xj​​)通常是困难的，于是想到这样一个函数：

即 $x_i$xi​和$x_j$xj​ 在特征空间中的内积等于他们在原始样本空间中通过函数$\kappa ({{x}_{i}},{{x}_{j}})$κ(xi​,xj​)计算的函数值，于是公式（16）写成如下：

求解后得到：

这里的函数$\kappa ({{x}_{i}},{{x}_{j}})$κ(xi​,xj​)就是核函数，在实际应用中，通常人们会从一些常用的核函数里选择（根据样本数据的不同，选择不同的参数，实际上就得到了不同的核函数），下面给出常用的核函数：
线性核：

• 多项式核（d是多项式的次数，d=1是退化为线性核）：
  
• 高斯核（σ>0）：
  
• 拉普拉斯核（σ>0）：
  
• sigmiod核（β>0,θ>0）：
  
  此外，核函数也可以通过组合得到，在此不再赘述。

4、线性支持向量机（软间隔支持向量机）与松弛变量

1、软间隔

在实际应用中，完全线性可分的样本是很少的，如果遇到了不能够完全线性可分的样本，我们应该怎么办？比如下面这个：

于是我们就有了软间隔，相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，比如：

我们允许部分样本点不满足约束条件：

为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量 ，令 $ξ_i≥0$ξi​≥0,约束条件变为：

同时，对于每一个松弛变量 $ξ_i$ξi​≥0，支付一个代价 $ξ_i$ξi​,目标函数变为：

其中C > 0 为惩罚参数，C值大时对误分类的惩罚增大， C值小时对误分类的惩罚减小，公式（21）包含两层含义：使 $\frac{1}{2}||w|{{|}^{2}}$21​∣∣w∣∣2尽量小即间隔尽量大，同时使误分类点的个数尽量小，C是调和两者的系数。
有了公式（21），可以和线性可分支持向量机一样考虑线性支持向量机的学习过程，此时，线性支持向量机的学习问题变成如下凸二次规划问题的求解（原始问题）：

2、对偶问题

与线性可分支持向量机的对偶问题解法一致，公式（22）的拉格朗日函数为：

其中$α_i≥0$αi​≥0,$μ_i≥0$μi​≥0是拉格朗日乘子。
令L(w,b,α,ξ,μ) 对 $w,b,\xi$w,b,ξ的偏导数为0可得如下：

将公式（24）（25）（26）代入公式（23）得对偶问题：

解出 $\alpha$α 之后，根据公式（9）可以求得 w ， 进而求得 b，可以得到模型：

上述过程的KKT条件为：

我们分析一下，对于任意的训练样本 $({{x}_{i}},{{y}_{i}})$(xi​,yi​)，总有${{\alpha }_{i}}=0$αi​=0或者 ${{y}_{i}}f({{x}_{i}})-1+{{\xi }_{i}}=0$yi​f(xi​)−1+ξi​=0。

• 若 $α_i=0$αi​=0 ，则该样本不出现在公式（13）中，不影响模型。
• 若$α_i>0$αi​>0，必有${{y}_{i}}f({{x}_{i}})-1+{{\xi }_{i}}=0$yi​f(xi​)−1+ξi​=0 ，即${{y}_{i}}f({{x}_{i}})=1-{{\xi }_{i}}$yi​f(xi​)=1−ξi​，此时该样本为支持向量。由于
  $C={{\alpha }_{i}}+{{\mu }_{i}}（$C=αi​+μi​（公式26）
• 若${{\alpha }_{i}}<C$αi​<C， 则必有 ${{\mu }_{i}}>0$μi​>0，根据公式（28）知${{\xi }_{i}}=0$ξi​=0 ，即该样本恰好落在最大间隔的边界上；
• 若 ${{\alpha }_{i}}=C$αi​=C ，则${{\mu }_{i}}=0$μi​=0，此时若${{\xi }_{i}}\le 1$ξi​≤1 则该样本在最大间隔内部，若 ${{\xi }_{i}}>1$ξi​>1 则样本分类错误。

三、SVM优缺点

优点：

• 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
• 能找出对任务至关重要的关键样本（即：支持向量）；
• 采用核技巧之后，可以处理非线性分类/回归任务；
• 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

缺点：

• 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 ，其中 N 为训练样本的数量；
• 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 ；
• 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。

四、参考：

【1】https://zhuanlan.zhihu.com/p/77750026?utm_source=wechat_session
【2】https://blog.****.net/sinat_20177327/article/details/79729551?utm_medium=distribute.pc_relevant_right.none-task-blog-BlogCommendFromBaidu-3&depth_1-utm_source=distribute.pc_relevant_right.none-task-blog-BlogCommendFromBaidu-3