文章目录

一、理论篇1、概述2、间隔与支持向量3、优化问题3.1 拉格朗日乘子法3.2 原始和对偶问题4、硬间隔SVM5、软间隔SVM6、核函数7、序列最小优化(SMO)算法8、模型选择9、总结

一、理论篇

1、概述

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

支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机以及非线性支持向量机。简单模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

2、间隔与支持向量

【例子】假如在下面的样本空间中，我们想寻找一个超平面，将不同类别的样本分开。但是我们发现将训练样本分开的超平面可能有很多，选择哪一个好呢?

其实，应选择正中间红色的超平面，因为它容忍性好，鲁棒性高，泛化能力最强。

我们把这个超平面方程定义为：wTx+b=0w^Tx+b=0wTx+b=0。

样本空间中任意点xxx到超平面wTx+b=0w^Tx+b=0wTx+b=0的距离为r=∣wTx+b∣∣∣w∣∣r=\cfrac{|w^Tx+b|}{||w||}r=∣∣w∣∣∣wTx+b∣​

假如超平面能够将样本正确分类，即当yi=+1y_i=+1yi​=+1时，wTxi+b>0w^Tx_i+b>0wTxi​+b>0；当yi=−1y_i=-1yi​=−1时，wTxi+b<0w^Tx_i+b<0wTxi​+b<0。

根据上面的两种情况，关系式yi(wTxi+b)>0y_i(w^Tx_i+b)>0yi​(wTxi​+b)>0永远成立。

如果当www和bbb变成它们原来的倍数时，wTx+b=0w^Tx+b=0wTx+b=0代表同一个超平面。为了后面能解出唯一解，我们需要缩放权重和偏差的比例。为了便于推导，选择一个合适的缩放比例，得到下面式子：

min⁡i=1,2,...,myi(wTxi+b)=1\min_{i=1,2,...,m}y_i(w^Tx_i+b)=1i=1,2,...,mmin​yi​(wTxi​+b)=1

证明如下：

(b,w)(b,w)(b,w)和(b/c,w/c)(b/c,w/c)(b/c,w/c)代表同一个超平面(c>0c>0c>0)，令

c=min⁡i=1,2,...,myi(wTxi+b)>0c=\min_{i=1,2,...,m}y_i(w^Tx_i+b)>0c=i=1,2,...,mmin​yi​(wTxi​+b)>0

将(b/c,w/c)(b/c,w/c)(b/c,w/c)代入上式的(b,w)(b,w)(b,w)得

min⁡i=1,2,...,myi(wTcxi+bc)=1cmin⁡i=1,2,...,myi(wTxi+b)=cc=1\min_{i=1,2,...,m}y_i(\frac{w^T}{c}x_i+\frac{b}{c})=\frac{1}{c}\min_{i=1,2,...,m}y_i(w^Tx_i+b)=\frac{c}{c}=1i=1,2,...,mmin​yi​(cwT​xi​+cb​)=c1​i=1,2,...,mmin​yi​(wTxi​+b)=cc​=1

由于(b,w)(b,w)(b,w)和(b/c,w/c)(b/c,w/c)(b/c,w/c)等价，则

min⁡i=1,2,...,myi(wTxi+b)=1\min_{i=1,2,...,m}y_i(w^Tx_i+b)=1i=1,2,...,mmin​yi​(wTxi​+b)=1

即yi(wTxi+b)≥1y_i(w^Tx_i+b)≥1yi​(wTxi​+b)≥1

如下图所示，距离超平面最近的这几个样本点使得上面式子的等号成立，我们称之为“支持向量”，两个异类支持向量到超平面的距离之和为γ=2∣∣w∣∣γ=\cfrac{2}{||w||}γ=∣∣w∣∣2​，我们称之为“间隔”。

我们的目标，就是要找到“最大间隔”的划分超平面，并且满足yi(wTxi+b)≥1y_i(w^Tx_i+b)≥1yi​(wTxi​+b)≥1约束的参数www和bbb，使得γγγ最大，即

max⁡w,b2∣∣w∣∣\max_{w,b}^{} \cfrac{2}{||w||}w,bmax​∣∣w∣∣2​s.t.yi(wTxi+b)≥1，i=1,2,...,ms.t.y_i(w^Tx_i+b)≥1，i=1,2,...,ms.t.yi​(wTxi​+b)≥1，i=1,2,...,m

上面的不等式约束可以等价为

min⁡w,b12wTw\min_{w,b}^{}\cfrac{1}{2}w^Tww,bmin​21​wTws.t.yi(wTxi+b)≥1，i=1,2,...,ms.t.y_i(w^Tx_i+b)≥1，i=1,2,...,ms.t.yi​(wTxi​+b)≥1，i=1,2,...,m

这就是支持向量机的基本型，即SVM的最终优化问题，也被称之为硬间隔SVM原始问题。

由于目标函数是一个关于www的二次函数，通常这类问题称作二次规划（QP）。

3、优化问题

3.1 拉格朗日乘子法

最优规划分为无约束规划和约束规划两种，其表现形式如下所示：

无约束规划：min⁡xf(x)\min_{x}^{}f(x)xmin​f(x)

约束规划：

min⁡xf(x)\min_{x}^{} f(x)xmin​f(x)s.t.①gi(x)≤0，i=1,2,...,ks.t.①g_i(x)≤0，i=1,2,...,ks.t.①gi​(x)≤0，i=1,2,...,k②hi(x)=0，i=1,2,...,l②h_i(x)=0，i=1,2,...,l②hi​(x)=0，i=1,2,...,l

约束规划比无约束规划问题难，而拉格朗日量可以将约束规划转换成无约束规划，具体定义如下：（拉格朗日函数）

L(x,α,β)=f(x)+∑i=1kαigi(x)+∑i=1lβihi(x)L(x,α,β)=f(x)+\sum_{i=1}^kα_ig_i(x)+\sum_{i=1}^lβ_ih_i(x)L(x,α,β)=f(x)+i=1∑k​αi​gi​(x)+i=1∑l​βi​hi​(x)

拉格朗日量是x,α,βx,α,βx,α,β的函数，α≥0α≥0α≥0。

如果对于LLL只在α,βα,βα,β（没有包括xxx）上求最大值θθθ，那么θθθ其实是xxx的一个函数，记作θ(x)θ(x)θ(x)：

θ(x)=max⁡α,β:αi≥0L(x,α,β)θ(x)=\max_{α,β:α_i≥0}L(x,α,β)θ(x)=α,β:αi​≥0max​L(x,α,β)

我们会发现，其实无约束最小化θ(x)θ(x)θ(x)等价于有约束最小化f(x)f(x)f(x)，具体证明如下。

情况1：当xxx违反边界条件（gi(x)>0,hi(x)≠0g_i(x)>0,h_i(x)≠0gi​(x)>0,hi​(x)​=0）时

θ(x)=max⁡α,β:αi≥0L(x,α,β)=max⁡α,β:αi≥0[f(x)+∑i=1kαigi(x)+∑i=1lβihi(x)]=∞θ(x)=\max_{α,β:α_i≥0}L(x,α,β)=\max_{α,β:α_i≥0}[f(x)+\sum_{i=1}^kα_ig_i(x)+\sum_{i=1}^lβ_ih_i(x)]=∞θ(x)=α,β:αi​≥0max​L(x,α,β)=α,β:αi​≥0max​[f(x)+i=1∑k​αi​gi​(x)+i=1∑l​βi​hi​(x)]=∞

情况2：当xxx满足边界条件（gi(x)≤0,hi(x)=0g_i(x)≤0,h_i(x)=0gi​(x)≤0,hi​(x)=0）时

θ(x)=max⁡α,β:αi≥0L(x,α,β)=max⁡α,β:αi≥0[f(x)+∑i=1kαigi(x)]=f(x)θ(x)=\max_{α,β:α_i≥0}L(x,α,β)=\max_{α,β:α_i≥0}[f(x)+\sum_{i=1}^kα_ig_i(x)]=f(x)θ(x)=α,β:αi​≥0max​L(x,α,β)=α,β:αi​≥0max​[f(x)+i=1∑k​αi​gi​(x)]=f(x)

综上所述，

θ(x)={∞gi(x)>0,hi(x)≠0f(x)gi(x)≤0,hi(x)=0θ(x)=\begin{cases} ∞& \text{$g_i(x)>0,h_i(x)≠0$}\\ f(x)& \text{$g_i(x)≤0,h_i(x)=0$}\\ \end{cases}θ(x)={∞f(x)​gi​(x)>0,hi​(x)​=0gi​(x)≤0,hi​(x)=0​

因此，无约束最小化θ(x)θ(x)θ(x)等价于有约束最小化f(x)f(x)f(x)，其数学表达形式如下所示：

约束规划f(x)f(x)f(x)：min⁡xf(x)\min_{x}^{} f(x)xmin​f(x)s.t.①gi(x)≤0，i=1,2,...,ks.t.①g_i(x)≤0，i=1,2,...,ks.t.①gi​(x)≤0，i=1,2,...,k②hi(x)=0，i=1,2,...,l②h_i(x)=0，i=1,2,...,l②hi​(x)=0，i=1,2,...,l

无约束规划θ(x)θ(x)θ(x)：

min⁡xθ(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β)\min_{x}^{}θ(x)=\min_x\max_{α,β:α_i≥0}L(x,α,β)xmin​θ(x)=xmin​α,β:αi​≥0max​L(x,α,β)

结论：对于一个约束规划问题，将其用拉格朗日量转换成容易求解的无约束规划问题即可，两者是等价的。

3.2 原始和对偶问题

上面介绍的无约束规划形式被叫作“原始形式(Primal)”，与其对应的是“对偶形式(Dual)”。

原始问题：先在ααα，βββ上求最大值，再在xxx上求最小值。

min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β)\min_{x}^{}θ_P(x)=\min_x\max_{α,β:α_i≥0}L(x,α,β)xmin​θP​(x)=xmin​α,β:αi​≥0max​L(x,α,β)

对偶问题：先在xxx上求最小值，再在ααα，βββ上求最大值。

max⁡α,β:αi≥0θD(x)=max⁡α,β:αi≥0min⁡xL(x,α,β)\max_{α,β:α_i≥0}^{}θ_D(x)=\max_{α,β:α_i≥0}\min_xL(x,α,β)α,β:αi​≥0max​θD​(x)=α,β:αi​≥0max​xmin​L(x,α,β)

下面的不等式恒成立：（最大的最小值永远大于或等于最小的最大值）

min⁡xθP(x)≥max⁡α,β:αi≥0θD(x)\min_{x}^{}θ_P(x)≥\max_{α,β:α_i≥0}^{}θ_D(x)xmin​θP​(x)≥α,β:αi​≥0max​θD​(x)

min⁡xmax⁡α,β:αi≥0L(x,α,β)≥max⁡α,β:αi≥0min⁡xL(x,α,β)\min_x\max_{α,β:α_i≥0}L(x,α,β)≥\max_{α,β:α_i≥0}\min_xL(x,α,β)xmin​α,β:αi​≥0max​L(x,α,β)≥α,β:αi​≥0max​xmin​L(x,α,β)

原始与对偶关系的证明：【略】

上面的不等式具有的特性被称为弱对偶性，即对偶问题的最优解永远小于或等于原始问题的最优解。在实际问题中，如果有以下3个额外条件，则有强对偶等式：

min⁡xmax⁡α,β:αi≥0L(x,α,β)=max⁡α,β:αi≥0min⁡xL(x,α,β)\min_x\max_{α,β:α_i≥0}L(x,α,β)=\max_{α,β:α_i≥0}\min_xL(x,α,β)xmin​α,β:αi​≥0max​L(x,α,β)=α,β:αi​≥0max​xmin​L(x,α,β)

其中3个条件是

{①原始问题的目标函数是凸函数②原始问题有解③线性限制条件\begin{cases} ①& \text{原始问题的目标函数是凸函数}\\ ②& \text{原始问题有解}\\ ③& \text{线性限制条件}\\ \end{cases}⎩⎪⎨⎪⎧​①②③​原始问题的目标函数是凸函数原始问题有解线性限制条件​

强对偶条件意味着原始问题和对偶问题的最优解是一样的。假设x∗x^*x∗，α∗α^*α∗，β∗β^*β∗是最优解，它们满足KKT条件。

结论：如果满足强对偶条件，则可以不好解的原始问题转换成好解的对偶问题，再用KKT条件求解。

4、硬间隔SVM

回顾硬间隔SVM原始问题：

min⁡w,b12wTw\min_{w,b}^{}\cfrac{1}{2}w^Tww,bmin​21​wTws.t.yi(wTxi+b)≥1，i=1,2,...,ms.t.y_i(w^Tx_i+b)≥1，i=1,2,...,ms.t.yi​(wTxi​+b)≥1，i=1,2,...,m

支持向量机的基本型属于一个凸二次规划问题，我们通过使用拉格朗日乘子法转化为无约束规划问题，即对每一条约束添加拉格朗日乘子αi≥0α_i≥0αi​≥0，则该问题的拉格朗日函数可以写为

令L(w,b,α)L(w,b,α)L(w,b,α)对www和bbb的偏导为零可得

将上面两个式子代入L(w,b,α)L(w,b,α)L(w,b,α)，将www和bbb消去，可得

【原问题转化为对偶问题】

所以

由此可以求出最优解α∗α^*α∗，求出该值后将其带入可以得到：

根据上面的推导得到硬间隔SVM对偶问题：

min⁡α(12∑i=1m∑k=1mαiαky(i)y(k)x(i)(x(k))T−∑i=1mαi)\min_{α}(\cfrac{1}{2}\sum_{i=1}^m\sum_{k=1}^mα_iα_ky^{(i)}y^{(k)}x^{(i)}(x^{(k)})^T-\sum_{i=1}^mα_i)αmin​(21​i=1∑m​k=1∑m​αi​αk​y(i)y(k)x(i)(x(k))T−i=1∑m​αi​)s.t.∑i=1mαiy(i)=0，αi≥0，i=1,2,...,ms.t.\sum_{i=1}^mα_iy^{(i)}=0，α_i≥0，i=1,2,...,ms.t.i=1∑m​αi​y(i)=0，αi​≥0，i=1,2,...,m

SVM的原始问题和对偶问题都是二次规划问题，但是求解的变量个数和约束条件个数都不同。

mmm是向量个数而nnn是维度，如果数据在低维度下线性不可分，需要转到高维度空间中，那么nnn可能是非常大的。求解原始问题会很低效，因此会将其转换成对偶问题，后者需要求解的变量个数为mmm，只跟数据个数有关。

注意由原始可行性、对偶可行性和互补松弛三个条件推出的关系式：

{①y(i)(wTx(i)+b)≥1②αi≥0③αi[1−y(i)(wTx(i)+b)]=0\begin{cases} ①& \text{$y^{(i)}(w^Tx^{(i)}+b)≥1$}\\ ②& \text{$α_i≥0$}\\ ③& \text{$α_i[1-y^{(i)}(w^Tx^{(i)}+b)]=0$}\\ \end{cases}⎩⎪⎨⎪⎧​①②③​y(i)(wTx(i)+b)≥1αi​≥0αi​[1−y(i)(wTx(i)+b)]=0​

由上式可知，

（1）如果①式中取严格大于号，意味着x(i)x^{(i)}x(i)没有落在边界上，即不是支持向量SV，要使③式成立，那么αi=0α_i=0αi​=0。

（2）如果②式中取严格大于号，要使③式成立，那么y(i)(wTx(i)+b)=1y^{(i)}(w^Tx^{(i)}+b)=1y(i)(wTx(i)+b)=1，即x(i)x^{(i)}x(i)是支持向量SV，落在了边界上。

5、软间隔SVM

线性不可分有两种情况，按照程度可分为两类：

（1）线性轻度不可分【解决方法：引入软间隔SVM】；

（2）线性重度不可分【解决方法：引入核函数（+软间隔SVM）】。

硬间隔SVM要求所有的数据都要分类正确，在此前提下再最小化wTww^TwwTw。但是在现实中，很难找到这样完美的数据集。为了缓解这个问题，引入了软间隔SVM，它会容忍一些错误的发生，将发生错误的情况加入目标函数中，希望能得到一个分类错误情况越少越好的结果。

硬间隔SVM和软间隔SVM的区别就是后者多了ξξξ(松弛变量)和CCC(惩罚因子，C＞0C＞0C＞0)。当进行完SVM后会有一个缓冲带，在硬间隔SVM中没有数据点在缓冲带里面，但在软间隔SVM中则不一样。如果定义“数据点进入缓冲带这一现象”为违规，那么软间隔SVM分类有3种不同现象：

①分类正确；②分类正确但违规；③分类错误（一定违规）。而参数ξξξ用于衡量数据违规的程度。

为了简化分析，令ui=yi(wTxi+b)u_i=y_i(w^Tx_i+b)ui​=yi​(wTxi​+b)，则ui≥1−ξiu_i≥1-ξ_iui​≥1−ξi​。

（1）当ξi=0ξ_i=0ξi​=0时，ui≥1u_i≥1ui​≥1，该点没有违规且分类正确（该点到分隔线的距离大于或等于最大间隔）；

（2）当0<ξi≤10<ξ_i≤10<ξi​≤1时，ui≥u_i≥ui​≥小于1的正数，该点违规但分类正确（该点到分隔线的距离小于最大间隔）；

（3）当ξi>1ξ_i>1ξi​>1时，ui≥u_i≥ui​≥负数，该点违规且分类错误（只有ui>0u_i>0ui​>0才代表分类正确）。

上图用ξξξ来记录违规数据距离边界的距离，并将这个距离纳入最优化的标准中。

但我们不希望ξξξ太大，因为这意味着有某个数据分类错得太离谱，因此需要用CCC来惩罚太大的ξξξ。

惩罚参数CCC控制缓冲带的宽度（最大间隔的长度）。

①值大的CCC对误分类的惩罚增大，代表“宁可边界窄一点，也要违规甚至出错的数据少点”，CCC无穷大就是硬间隔SVM的情况。

②值小的CCC误分类的惩罚减小，代表“宁可边界宽一点，即使牺牲分类精度也无所谓。

最小化目标函数包含两层含义：一方面使间隔尽量大，另一方面使误分类点的个数尽量小，CCC是调和二者的系数。

【原问题转化为对偶问题】

推导过程如下：

（1）构造拉格朗日函数：

（2）对w,b,ξw,b,ξw,b,ξ求偏导：

（3）将三个式子带入LLL中：

（4）对上式求关于ααα的极大：

（5）整理（消去μiμ_iμi​，只留下αiα_iαi​），得到对偶问题：

【硬间隔和软间隔SVM两者的对偶问题的唯一的区别就是αiα_iαi​的取值范围不同】

【软间隔支持向量机KKT条件】

6、核函数

线性不可分有两种情况，按照程度可分为两类：

（1）线性轻度不可分【解决方法：引入软间隔SVM】；

（2）线性重度不可分【解决方法：引入核函数（+软间隔SVM）】。

Q：若不存在一个能正确划分两类样本的超平面, 怎么办?

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

设样本xxx映射后的向量为φ(x)φ(x)φ(x)，划分超平面为f(x)=wTφ(x)+bf(x)=w^Tφ(x)+bf(x)=wTφ(x)+b。

→存在的问题：

（1）维度灾难

上面式子方框的地方要使用映射后的样本向量做内积；假如最初的特征是nnn维的，我们把它映射到n2n^2n2维，然后再计算。这样需要的时间从原来的的O(n)O(n)O(n)，变成了O(n2)O(n^2)O(n2)。

（2）如何选择合理的非线性转换？

→解决的办法：引入核函数（核技巧）

基本想法：不显式地设计核映射，而是设计核函数。

我们可以构造核函数使得运算结果等同于非线性映射，同时运算量要远远小于非线性映射。

常用核函数：

【核函数的注意事项】

(1)核函数选择成为SVM的最大变数；

(2)经验：文本数据使用线性核，情况不明使用高斯核；

(3)核函数的性质：

①核函数的线性组合仍为核函数；

②核函数的直积仍为核函数；

③设K(x1,x2)K(x_1,x_2)K(x1​,x2​)为核函数，则对于任意函数g(x)g(x)g(x)，

转换函数无穷无尽，可以从低维xxx空间转到高维zzz空间（多项式核）甚至无穷维度zzz空间（高斯径向基函数核）。但维度越高，得到的SVM越容易过拟合数据。

【核函数举例】

假设定义两个向量： x=(x1,x2,x3),y=(y1,y2,y3)x=(x1,x2,x3), y=(y1,y2,y3)x=(x1,x2,x3),y=(y1,y2,y3)

定义高维映射方程：φ(x)=(x1x1,x1x2,x1x3,x2x1,x2x2,x2x3,x3x1,x3x2,x3x3)φ(x)=(x1x1,x1x2,x1x3,x2x1,x2x2,x2x3,x3x1,x3x2,x3x3)φ(x)=(x1x1,x1x2,x1x3,x2x1,x2x2,x2x3,x3x1,x3x2,x3x3)

假设x=(1,2,3),y=(4,5,6)x=(1,2,3),y=(4,5,6)x=(1,2,3),y=(4,5,6)

φ(x)=(1,2,3,2,4,6,3,6,9)φ(x)=(1,2,3,2,4,6,3,6,9)φ(x)=(1,2,3,2,4,6,3,6,9)

φ(y)=(16,20,24,20,25,36,24,30,36)φ(y)=(16,20,24,20,25,36,24,30,36)φ(y)=(16,20,24,20,25,36,24,30,36)

求内积<φ(x),φ(y)>=16+40+72+40+100+180+72+180+324=1024<φ(x),φ(y)>=16+40+72+40+100+180+72+180+324=1024<φ(x),φ(y)>=16+40+72+40+100+180+72+180+324=1024

定义核函数：K(x,y)=(<x,y>)2K(x,y)=(<x,y>)^2K(x,y)=(<x,y>)2

K(x,y)=(4+10+18)2=1024K(x,y)=(4+10+18)^2=1024K(x,y)=(4+10+18)2=1024

同样的结果，使用核方法计算容易得多。

7、序列最小优化(SMO)算法

8、模型选择

（1）多项式核函数：K(x,x′)=(ζ+γxTx′)QK(x,x')=(ζ+γx^Tx')^QK(x,x′)=(ζ+γxTx′)Q；

（2）高斯径向基函数核：K(x,x′)=exp(−γ×∣∣x−x′∣∣2)K(x,x')=exp(-γ×||x-x'||^2)K(x,x′)=exp(−γ×∣∣x−x′∣∣2)。

在使用SVM时，根据不同的数据特征，一般都会使用软间隔SVM加上一个核函数。多项式核首先需要设定多项式次数QQQ来控制模型，之后还要调节参数γγγ和ζζζ。当参数比较多时，选择起来比较麻烦，因此通常会选用高斯径向基函数核。软间隔SVM里的超参数CCC和高斯径向基函数核里的超参数γγγ用（交叉）验证数据集来调节。

高斯径向基函数核的超参数γγγ值越大，越容易产生过拟合。

软间隔SVM里的超参数CCC值越大，越容易产生过拟合。

sklearn中提供了两种调参方法：网格追踪法和随机追踪法。

9、总结

SVM分类遇到的3类数据：

类型①：线性可分（在理论上存在，在实际中罕见，引出硬间隔SVM）；

类型②：线性轻度不可分（存在少量异常值，引出软间隔SVM）；

类型③：线性重度不可分（不可能线性分类，必须要提升维度，引出空间转换）。

在类型①数据中，硬间隔SVM本着“分离平面到数据间隔越远越好”的原则，由以下3步推导完成。

(1)推导出最近点到超平面的距离的表达式，将其定义为间隔。

(2)最大化间隔得到一个约束规划问题，用分类正确而且点都在间隔之内当约束条件。

(3)通过数学技巧将困难的约束规划问题转换成容易的凸二次规划问题。

该凸二次规划问题是硬间隔SVM原始问题，接着利用拉格朗日量推出其对偶问题，并且根据强对偶关系，发现“对偶问题的最优解”和“原始问题的最优解”一致。从表面上看，对偶问题要比原始问题复杂，但推导硬间隔SVM对偶问题的原因有3个：

(1)原始问题的解和数据的维度有关，而对偶问题的解只和数据的个数有关，通常在低维度线性重度不可分的情况下会转换到高维度(甚至无限维度)，那么对偶问题的计算负担会小很多。

(2)对偶问题的解含有内积表达式，而核技巧在“不触碰高维空间”的情况下计算高维向量内积最在行。

(3)在现实中，软间隔SVM最常用，而它和硬间隔SVM对偶问题只差一个上界限制条件，前者可以由后者快速推导出。

软间隔SVM用于处理类型②的线性轻度不可分数据，将数据由低维升到高维空间的转换函数用于处理类型③的线性重度不可分数据，但是处理完后可能数据还是线性不可分的，只不过从重度变为轻度了，最后还要用软间隔SVM来处理。

为了避免犯数据窥探的错误，以及能处理所有种类(线性可分或线性不可分)的数据，可以使用空间转换函数加上软间隔SVM。使用空间转换函数加上软间隔SVM是将一个强鲁棒性的线性模型和采用核函数做非线性转换进行结合。从算法角度来看：

①当用转换函数将数据从低维空间提升到高维空间时，可以用核技巧来降低计算量。

②软间隔SVM在数据很大时直接用二次规划很慢，可以用序列最小优化(SMO)来降低计算量。

要计算软间隔SVM和核函数里的超参数，就用网格追踪法或随机追踪法选取最小的(交叉)验证误差对应的超参数。

下面是SVM的总结图：

【SVM的优点】

• 训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生多拟合；

• SVM训练出来的模型完全依赖于支持向量，即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。

• 一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化。