1、支持向量机SVM

对两类样本点进行分类，如下图，有a线、b线、c线三条线都可以将两类样本点很好的分开类，我们可以观察到b线将两类样本点分类最好，原因是我们训练出来的分类模型主要应用到未知样本中，虽然a、b、c三条线将训练集都很好的分开类，但是当三个模型应用到新样本中时，b线抗干扰能力最强，也就是泛化能力最好，样本变化一些关系不大，一样能被正确的分类。那么如何确定b线的位置呢？我们可以使用支持向量机SVM来确定b线的位置。

支持向量机（support vector machines,SVM）是一种二分类算法，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，如果对应的样本特征少，一个普通的SVM就是一条线将样本分隔开，但是要求线到两个类别最近样本点的距离要最大。

如上图所示，b线就是我们根据支持向量机要找到的分割线，这条线需要到两个类别最近的样本点最远，图上的距离就是d，由于这条线处于两个类别的中间，所以到两个类别的距离都是d。

支持向量机SVM算法就是在寻找一个最优的决策边界（上图中的两条虚线）来确定分类线b，所说的支持向量（support vector）就是距离决策边界最近的点（上图中p1、p2、p3点，只不过边界穿过了这些点）。如果没有这些支持向量点，b线的位置就要改变，所以 SVM就是根据这些支持向量点来最大化margin，来找到了最优的分类线（machine，分类器） ，这也是SVM分类算法名称的由来。

2、构建SVM目标函数

接着上面的分类问题来分析，假设支持向量机最终要找的线是$l_2$，决策边界两条线是$l_1$和$l_3$，那么假设$l_2$的方程为$w^T\cdot x+b=0$，这里$w$表示$(w_1,w_2{)}^T$，$x$表示$(x_1,x_2{)}^T$，我们想要确定$l_2$直线，只需要确定w和b即可，此外，由于$l_1$和$l_3$线是$l_2$的决策分类边界线，一定与$l_2$是平行的，平行就意味着斜率不变，b变化即可，所以我们可以假设$l_1$线的方程为$w^T\cdot x+b=c$，$l_3$线的方程为$w^T\cdot x+b=-c$。

【知识补充】：

• 二维空间点$(x_1,y_1)$到直线$Ax+By+C=0$的距离公式是：

$$d=\frac{|A{x}_1+B{y}_1+C|}{\sqrt{A^2+B^2}}$$

• 两条平行线$Ax+By+C_1=0$与$Ax+By+C_2=0$之间的距离公式为：

$$d=\frac{|C_1-C_2|}{\sqrt{A^2+B^2}}$$

我们希望的是决策边界上的样本点到$l_2$直线的距离d越大越好。我们可以直接计算$l_1$或$l_3$上的点到直线$l_2$的距离，假设将空间点扩展到n维空间后，点$x_i=(x_1,x_2,\cdots ,x_n)$到直线$w^T\cdot x+b=0$（严格意义上来说直线变成了超平面）的距离为：

$$d=\frac{|w^T\cdot x_i+b|}{||w||}$$

以上$||w||=\sqrt{w_1^2+w_2^2+\cdots +w_n^2}$，读作“w的模”。

由于$l_1$、$l_2$和$l_3$三条直线平行，d也是两条平行线之间的距离，我们可以根据两条平行线之间的距离公式得到d值如下：

$$d=\frac{|C-0|}{||w||}=\frac{|-C-0|}{||w||}=\frac{|C|}{||w||}=\frac{|w^T\cdot x_i+b|}{||w||}$$

我们可以看到无论计算点到直线的距离还是两个平行线之间的距离，最终结果是一致的。对于$l_1$直线$w^T\cdot x+b=c$，我们可以相对应成比例的缩小各项的系数，例如变成$\frac{w^T}{2}\cdot x+\frac{b}{2}=\frac{c}{2}$，这条直线还是原来本身的直线，现在我们可以把它变成$\frac{w^T}{c}\cdot x+\frac{b}{c}=\frac{c}{c}=1$，即改写后的$l_1$直线$w^T\cdot x+b=1$还是原来的直线，同理，对于$l_3$直线我们也可以变换成$w^T\cdot x+b=-1$，所以上图可以改变成如下：

那么变换之后的d可以根据两条平行线之间的距离得到：

$$d=\frac{1}{||w||}$$

我们希望决策边界上的点到超平面$l_2$距离d越大越好。我们将$l_3$上方的点分类标记为“1”类别，将$l_1$下方的点分类标记为“-1”类别，那么我们可以得到如下公式：

$$\{\begin{array}{rl}& w^T\cdot x_i+b\ge 1y=1(1)\mathrm{式}\\ \\ & w^T\cdot x_i+b\le -1y=-1(2)\mathrm{式}\end{array}$$

两式两侧分别乘以对应的类别可以合并为一个式子：

$$y\cdot (w^T\cdot x_i+b)\ge 1(3)\mathrm{式}$$

所以在计算d的最大值时，是有限制条件的，这个限制条件就是(3)式。

所以对于所有样本点我们需要在满足$y\cdot (w^T\cdot x_i+b)\ge 1$条件下，最大化$d=\frac{1}{||w||}$，就是最小化$||w||$，等效于最小化$\frac{1}{2}||w|{|}^2$，这样转换的目的就是为了后期优化过程中求导时方便操作，不会影响最终的结果，所以在支持向量机SVM中要确定一个分类线，我们要做的就是在$y\cdot (w^T\cdot x_i+b)\ge 1$条件下最小化$\frac{1}{2}||w|{|}^2$，记为:

$$min\frac{1}{2}||w|{|}^{2}s.t.y\cdot (w^T\cdot x_i+b)\ge 1,i=1,2,\cdots ,n$$

以上n代表样本总数，缩写$s.t$表示“Subject to”是“服从某某条件”的意思，上述公式描述的是一个典型的不等式约束条件下的二次型函数优化问题，同时也是支持向量机的基本数学模型，这里我们称支持向量机的目标函数。

3、拉格朗日乘子法

3.1、拉格朗日乘子法

拉格朗日乘数法主要是将有等式约束条件优化问题转换为无约束优化问题 ，拉格朗日乘数法如下：

假设$x=[x_1,x_2,\cdots ,x_n]$是一个n维向量，$f(x)$和$h(x)$含有x的函数，我们需要找到满足$h(x)=0$条件下$f(x)$最小值，如下：

$$minf(x)s.t.h(x)=0$$

可以引入一个自变量$\lambda$，其可以取任意值，则上式严格等价于下式：

$$L(x,\lambda )=f(x)+\lambda h(x)$$

$L(x,\lambda )$叫做Lagrange函数（拉格朗日函数），$\lambda$叫做拉格朗日乘子（其实就是系数）。令$L(x,\lambda )$对x的导数为0，对$\lambda$的导数为0，求解出$x,\lambda$ 的值，那么x就是函数$f(x)$在附加条件$h(x)$下极值点。

以上就是拉格朗日乘数法，通俗理解拉格朗日乘数法就是将含有等式条件约束优化问题转换成了无约束优化问题构造出拉格朗日函数$L(x,\lambda )$，让$L(x,\lambda )$对未知数x和$\lambda$进行求导，得到一组方程式，可以计算出对应的x和$\lambda$结果，这个x对应的$f(x)$函数值就是在条件$h(x)=0$下的最小值点。

拉格朗日函数转换成等式过程的证明涉及到导数积分等数学知识，这里不再证明。

参考文章：

拉格朗日函数转换推导

3.2、KKT条件

假设我们面对的是不等式条件约束优化问题，如下：

假设$x=[x_1,x_2,\cdots ,x_n]$是一个n维向量，$f(x)$和$h(x)$是含有x的函数，我们需要找到满足$h(x)\le 0$条件下$f(x)$最小值，如下：

$$minf(x)s.th(x)\le 0---\mathrm{式}\mathrm{①}$$

针对上式，显然是一个不等式约束最优化问题，不能再使用拉格朗日乘数法，因为拉格朗日乘数法是针对等式约束最优化问题。

那我们可以考虑加入一个“松弛变量”${\alpha }^2$让条件$h(x)\le 0$来达到等式的效果，即使条件变成$h(x)+{\alpha }^2=0$，这里加上${\alpha }^2$的原因是保证加的一定是非负数，即：${\alpha }^2\ge 0$，但是目前不知道这个${\alpha }^2$值是多少，一定会找到一个合适的${\alpha }^2$值使$h(x)+{\alpha }^2=0$成立，所以将①式改写成如下：

$$minf(x)s.th(x)+{\alpha }^2=0---\mathrm{式}\mathrm{②}$$

以上②式变成了等式条件约束优化问题，我们就可以使用拉格朗日乘数法来求解满足等式条件下$f(x)$最小值对应的x值。

通过拉格朗日乘数法，将②式转换为如下：

$$L(x,\lambda ,\alpha )=f(x)+\lambda (h(x)+{\alpha }^2)$$

但是上式中$\lambda$值必须满足$\lambda \ge 0$，由于$L(x,\lambda ,\alpha )$变成了有条件的拉格朗日函数，这里需要求$minL(x,\lambda ,\alpha )$ 对应下的x值 。至于为什么$\lambda \ge 0$，这里证明涉及到很多几何性质，这里也不再证明。参考文章：KKT不等式约束

所以将上式转换成如下拉格朗日函数：

$$minL(x,\lambda ,\alpha )=f(x)+\lambda (h(x)+{\alpha }^2)\lambda \ge 0---\mathrm{式}\mathrm{③}$$

以上我们可以看到将不等式条件约束优化问题加入“松弛变量”转换成等式条件约束优化问题，使用拉格朗日乘数法进行转换得到$L(x,\lambda ,\alpha )$，下面我们可以对拉格朗日函数$L(x,\lambda ,\alpha )$对各个未知数$x,\lambda ,\alpha$进行求导，让对应的导数为零，得到以下联立方程组 $g$：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial x}=\frac{\partial f(x)}{\partial x}+\lambda \frac{\partial h(x)}{\partial x}=0---\mathrm{式}\mathrm{④}\\ \\ & \frac{\partial L}{\partial \lambda }=h(x)+{\alpha }^2=0---\mathrm{式}\mathrm{⑤}\\ \\ & \frac{\partial L}{\partial \alpha }=2\lambda \alpha =0---\mathrm{式}\mathrm{⑥}\\ \\ & \lambda \ge 0---\mathrm{式}\mathrm{⑦}\end{array}$$

从上式⑥式可知 $\lambda \alpha =0$，我们分两种情况讨论：

1. $\lambda =0,\alpha \ne 0$

由于$\lambda =0$，根据③式可知，约束不起作用，你可以去掉约束，直接对$f(x)$ 求导，令导数为0，求极值就可以了，此时，$h(x)\le 0$，对求解极值无影响。

2. $\lambda \ne 0,\alpha =0$

由于$\lambda \ne 0$，根据③式可知$\lambda >0$。由于 $\alpha =0$，约束条件起作用，根据⑤式可知，$h(x)=0$。

综上两个步骤我们可以得到：

$\lambda \cdot h(x)=0$

约束条件起作用时，$\lambda >0,h(x)=0$；

约束条件不起作用时，$\lambda =0,h(x)\le 0$ ；

上面方程组 $ g$ 可以进行如下化简：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial x}=\frac{\partial f(x)}{\partial x}+\lambda \frac{\partial h(x)}{\partial x}=0\\ \\ & \lambda \cdot h(x)=0\\ \\ & \lambda \ge 0\end{array}$$

以上便是不等式约束优化问题的KKT（Karush-Kuhn-Tucker）条件 。

我们回到最开始要处理的问题上，根据③式可知，我们需要找到合适的$x,\lambda ,\alpha$值使$L(x,\lambda ,\alpha )$最小，但是合适的$x,\lambda ,\alpha$必须满足KKT条件。

我们对③式的优化问题可以进行优化如下：

$$minL(x,\lambda ,\alpha )=f(x)+\lambda (h(x)+{\alpha }^2)\lambda \ge 0---\mathrm{式}\mathrm{③}$$$$minL(x,\lambda ,\alpha )=f(x)+\lambda \cdot h(x)+\lambda {\alpha }^2$$

由于${\alpha }^2\ge 0$且$\lambda \ge 0$，$\lambda {\alpha }^2$一定大于零，根据上面KKT条件，$\alpha$ 对求最优化求解无影响，所以进一步可以简化为如下：

$$minL(x,\lambda )=f(x)+\lambda h(x)---\mathrm{式}\mathrm{⑧}$$

满足最小化⑧式对应的$x,\lambda$值一定也要满足KKT条件。

假设现在我们找到了合适的参数$x^{\ast }$值使$f(x^{\ast })$取得最小值P【注意：这里根据①式来说，计算$f(x)$的最小值，这里假设合适参数$x^{\ast }$值对应的$f(x^{\ast })$ 的值P就是最小值，不存在比这更小的值。 】 ，由于⑧式中$\lambda h(x^{\ast })$一定小于等于零，所以一定有：

$$L(x^{\ast },\lambda )=f(x^{\ast })+\lambda h(x^{\ast })\le P$$

也就是说一定有：

$$L(x^{\ast },\lambda )\le P$$

为了找到最优的$\lambda$值，我们一定要让$L(x^{\ast },\lambda )$接近P【接近的时候，就是两条曲线相交】，即找到合适的${\lambda }^{\ast }$最大化$L(x^{\ast },\lambda )$，可以写成$\underset{\lambda }{max}L(x^{\ast },\lambda )$，所以⑧式求解合适的$x,\lambda$值最终可以转换成如下：

$$\underset{x}{min}\underset{\lambda }{max}L(x,\lambda )=f(x)+\lambda h(x)s.t.\lambda \ge 0---\mathrm{式}\mathrm{⑨}$$

公式⑨可以这么描述：最小化关于 x 的最大化关于 λ 的 L(x, λ) 函数。

参考文章：KKT不等式约束

$f(x)=(x_1-2{)}^2+(x_2+2{)}^{2}s.t.g(x)=x_1^2+x_2^2-1\le 0$

$L(x,\lambda )=(x_1-2{)}^2+(x_2+2{)}^2+\lambda (x_1^2+x_2^2-1)$

$\{\begin{array}{rl}& \frac{\partial L}{\partial x_1}=2(x_1-2)+2\lambda x_1=0\\ \\ & \frac{\partial L}{\partial x_2}=2(x_2+2)+2\lambda x_2=0\\ \\ & \frac{\partial L}{\partial \lambda }=x_1^2+x_2^2-1=0\\ \\ & \lambda \cdot g(x)=0\\ \\ & \lambda \ge 0\end{array}$

解方程可得：

$\{\begin{array}{rl}& x_1=\frac{\sqrt{2}}{2}\\ \\ & x_2=-\frac{\sqrt{2}}{2}\\ \\ & \lambda =2\sqrt{2}-1\\ \\ & \cancel{\lambda =-2\sqrt{2}-1}\end{array}$

其中的$x_1$ 和 $x_2$ 就是最优解~

$\{\begin{array}{rl}& x_1=\frac{\sqrt{2}}{2}\\ \\ & x_2=-\frac{\sqrt{2}}{2}\end{array}$

3.3、对偶问题

原问题

$$minf(x)s.t.h(x)\le 0---\mathrm{式}\mathrm{①}$$

对原问题的约束条件整合【带KKT条件的拉格朗日函数】

$$\underset{x}{min}\underset{\lambda }{max}L(x,\lambda )=f(x)+\lambda h(x)s.t.\lambda \ge 0---\mathrm{式}\mathrm{⑨}$$

这个公式的理解：

最小化关于 x 的最大化关于 λ 的 L(x, λ) 函数，并满足 λ $\ge$ 0。 原问题要求我们先求最大值，后求最小值，这个求解过程往往不容易。原问题是一个凸二次规划问题，目标是最小化带有线性约束的二次函数。

$$min\frac{1}{2}||w|{|}^{2}s.t.y\cdot (w^T\cdot x_i+b)\ge 1,i=1,2,\cdots ,n$$

我们可以使用拉格朗日乘子法将这个问题转化为带有等式约束的拉格朗日函数，并使用 KKT 条件来求解最优解。但是，这个问题的求解往往非常复杂，尤其是当数据集非常大时，计算复杂度将非常高。

通过对原问题进行对偶转换，我们可以将原问题转化为一个只涉及内积的问题，从而减少计算复杂度。具体来说，我们将原问题中的变量 $x$ 替换为拉格朗日乘子 $\lambda$，然后通过对 $\lambda$ 求偏导数来得到对偶问题。对偶问题的目标是最大化带有约束的对偶函数，并且只涉及内积。

我们将原问题转换一下，其实就是把min和max对调了一下（可以理解为从不同的方向，进行求解）：

$$\underset{\lambda }{max}\underset{x}{min}L(x,\lambda )=f(x)+\lambda h(x)s.t.\lambda \ge 0---\mathrm{式}\mathrm{⑩}$$

式⑩称为原问题的对偶问题（对上面方程式⑨的求解等效求解式⑩）。

这个公式的理解：

最大化关于 λ 的最小化关于 x 的L(x, λ) 函数，并满足 λ $\ge$ 0

在许多情况下，原问题和对偶问题的解是相同的，因此，求解了式⑩对偶问题的解，即是解出了原问题式⑨的解。

但是原问题跟对偶问题并不完全是等价的，这里有一个强对偶性、弱对偶性的概念，弱对偶性是对于所有的对偶问题都有的一个性质。

这里给出一个弱对偶性的推导过程:

$$\underset{\lambda }{max}\underset{x}{min}L(x,\lambda )=\underset{x}{min}L(x,{\lambda }^{\ast })\le L(x^{\ast },{\lambda }^{\ast })\le \underset{\lambda }{max}L(x^{\ast },\lambda )=\underset{x}{min}\underset{\lambda }{max}L(x,\lambda )$$

其中 $x^{\ast },{\lambda }^{\ast }$是函数满足条件时对应的最优解，也就是说，原问题始终大于等于对偶问题:

$$\underset{\lambda }{max}\underset{x}{min}L(x,\lambda )\le \underset{x}{min}\underset{\lambda }{max}L(x,\lambda )$$

如果两个问题是强对偶的，那么这两个问题其实是等价的问题:

$$\underset{\lambda }{max}\underset{x}{min}L(x,\lambda )=\underset{x}{min}\underset{\lambda }{max}L(x,\lambda )$$

所有的下凸函数都满足强对偶性，SVM的目标函数即原问题是一个下凸二次规划问题，所以SVM原问题和其对偶问题是满足强对偶性，即两个问题是等价的。

【备注】：对弱对偶性推导的理解如下图所示：

4、目标函数优化【硬间隔】

通过2小节【构建SVM目标函数】我们知道SVM目标函数如下：

$$min\frac{1}{2}||w||s.t.y\cdot (w^T\cdot x_i+b)\ge 1,i=1,2,\cdots ,n$$

根据拉格朗日乘数法、KKT条件、对偶问题我们可以按照如下步骤来计算SVM目标函数最优的一组w值。

4.1、构造拉格朗日函数

将SVM目标函数转换为如下:

$$min\frac{1}{2}||w||s.t.1-y\cdot (w^T\cdot x_i+b)\ge 0,i=1,2,\cdots ,n$$

根据3.2【KKT条件】中的⑨式构建拉格朗日函数如下：

$$L=\underset{w,b}{min}\underset{\lambda \ge 0}{max}L(w,b,\lambda )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)]s.t.{\lambda }_i\ge 0---\mathrm{式}a$$

以上不等式转换成拉格朗日函数必须满足KKT条件，详见3.2【KKT条件】，这里满足的KKT条件如下：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial w}=0\\ \\ & \sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)]=0\\ \\ & \lambda \ge 0\end{array}$$

4.2、对偶转换

由于原始目标函数$\frac{1}{2}||w||$是个下凸函数，根据3.3【对偶问题】可知$L(w,b,\lambda )$一定是强对偶问题，所以可以将a式改写成如下b式：

$$\underset{\lambda }{max}\underset{w,b}{min}L(w,b,\lambda )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)]s.t{\lambda }_i\ge 0---\mathrm{式}b$$

针对b式，我们假设参数$\lambda$固定，使$L(w,b,\lambda )$对参数w和b进行求导得到如下：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i=0\\ \\ & \frac{\partial L}{\partial b}=\sum _{i=1}^n{\lambda }_i\cdot y_i=0\end{array}$$

进一步可以得到：

$$\{\begin{array}{rl}& \sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i=w\\ \\ & \sum _{i=1}^n{\lambda }_i\cdot y_i=0\end{array}---\mathrm{式}c$$

按照解方程组的思想，我们现在将以上计算得到的结果代入到b式中得到：

$$\begin{array}{rl}& \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)]\\ \\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n{\lambda }_i{y}_i(\sum _{j=1}^n{\lambda }_j{x}_j{y}_j\cdot x_i+b)\\ \\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{y}_i{\lambda }_j{y}_j(x_i\cdot x_j)-\sum _{i=1}^n{\lambda }_i{y}_{i}b\\ \\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)s.t\sum _{i=1}^n{\lambda }_i{y}_i=0,{\lambda }_i\ge 0\end{array}$$

即：

$$\begin{array}{rl}& \underset{\lambda }{max}L(w,b,\lambda )=\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)---\mathrm{式}d\\ \\ & s.t\sum _{i=1}^n{\lambda }_i{y}_i=0,{\lambda }_i\ge 0\end{array}$$

我们可以发现以上公式经过转换只含有$\lambda$的方程求极值问题，但是$\lambda$含有${\lambda }_i,{\lambda }_j,\cdots$这些未知数（注意不是2个），那么我们要求的一组w如何得到呢？只要针对以上公式得到$\lambda$值后，我们可以根据c式进一步求解到对应的一组w值。针对上式求极值问题，我们常用 SMO(Sequential Minimal Optimization) 算法求解${\lambda }_i,{\lambda }_j,\cdots$。

注意：d式中$(x_i\cdot x_j)$代表两个向量的点积，也叫内积，例如：$x_i=(x_{i1},x_{i2}),x_j=(x_{j1},x_{j2})$那么两个向量点积结果为$x_{i1}\ast x_{j1}+x_{i2}\ast x_{j2}$。

4.3、SMO算法求解（了解）

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。下面我们只说SVM中如何利用SMO算法进行求解最终结果的，这里不再进行公式推导。

$$\begin{array}{rl}& \underset{\lambda }{max}L(w,b,\lambda )=\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)---\mathrm{式}d\\ \\ & s.t\sum _{i=1}^n{\lambda }_i{y}_i=0,{\lambda }_i\ge 0\end{array}$$

我们根据d式可以看到有 ${\lambda }_i,{\lambda }_j,i=1,2,\cdots ,n,j=1,2,\cdots ,n$ 很多参数，由于优化目标中含有约束条件：$\sum _{i=1}^n{\lambda }_i{y}_i=0$，此约束条件中$i=1,2,\cdots ,n$，$y_i$代表每个样本所属类别-1或者1。

根据SMO算法假设将${\lambda }_3,{\lambda }_4,\cdots ,{\lambda }_n$参数固定，那么${\lambda }_1,{\lambda }_2$之间的关系也确定了，可以将约束条件：$\sum _{i=1}^n{\lambda }_i{y}_i=0$改写成

$${\lambda }_1{y}_1+{\lambda }_2{y}_2+c=0---\mathrm{式}e$$

我们可以将上式中c看成是${\lambda }_3,{\lambda }_4,\cdots ,{\lambda }_n$乘以对应的类别$y$得到的常数，根据e式我们发现${\lambda }_1,{\lambda }_2$之间有等式关系，即：${\lambda }_2=\frac{-c-{\lambda }_1{y}_1}{y_2}$，也就是说我们可以使用${\lambda }_1$的表达式代替${\lambda }_2$，这样我们就可以将d式看成只含有${\lambda }_1\ge 0$这一个条件下最优化问题，并且我们可以将${\lambda }_2=\frac{-c-{\lambda }_1{y}_1}{y_2}$代入到d式，d式中只含有${\lambda }_1$一个未知数求极值问题，可以对函数进行求导，令导数为零，得到${\lambda }_1$的值，然后根据${\lambda }_1$的值计算出${\lambda }_2$的值。通过以上固定参数方式多次迭代计算得到一组$\lambda$值。

然后对其他的$\lambda$组【${\lambda }_3,{\lambda }_4$】，进行相同操作，多次执行，即可得到全部$\lambda$，for循环迭代优化，即可！

4.4、计算分割线w和b的值

根据4.2中的c式，如下：

$$\{\begin{array}{rl}& \sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i=w\\ \\ & \sum _{i=1}^n{\lambda }_i\cdot y_i=0\end{array}---\mathrm{式}c$$

我们可以知道获取了一组$\lambda$的值，我们可以得到一组w对应的值。根据4.1中的KKT条件：

$$\{\begin{array}{rl}& 1-y_i(w^T\cdot x_i+b)\le 0\\ \\ & \lambda (1-y_i(w^T\cdot x_i+b))=0---\mathrm{式}f\\ \\ & \lambda \ge 0\end{array}$$

根据f式中式可知，当$\lambda$ 不为0时，一定有$ 1-y_i(w^T\cdot x_i + b) = 0$，对于这样的样本就属于支持向量点，就在分类边界上，我们将对应的w代入到下式中

$$y_i(w^T\cdot x_i+b)=1---\mathrm{式}g$$

一定可以计算出b的值。我们将g式两边乘以$y_i$，得到

$$y_i^2(w^T\cdot x_i+b)=y_i$$

由于$y_i^2=1$，所以得到最终b的结果如下：

$$b=y_i-w^T\cdot x_i$$

假设我们有S个支持向量，以上b的计算可以使用任意一个支持向量代入计算即可，如果数据严格是线性可分的，这些b结果是一致的。对于数据不是严格线性可分的情况，参照后面的软间隔问题，一般我们可以采用一种更健壮的方式，将所有支持向量对应的b都求出，然后将其平均值作为最后的结果，最终b的结果如下：

$$b=\frac{1}{S}\sum _{i\in S}(y_i-w^T\cdot x_i)$$

S代表支持向量点的集合，也就是在边界上点的集合。

综上所述，我们可以的到最终的w和b的值如下：

$$\{\begin{array}{rl}& w=\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i\\ \\ & b=\frac{1}{S}\sum _{i\in S}(y_i-w^T\cdot x_i)\end{array}$$

确定w和b之后，我们就能构造出最大分割超平面：$w^T\cdot x+b=0$，新来样本对应的特征代入后得到的结果如果是大于0那么属于一类，小于0属于另一类。

5、软间隔及优化

5.1、软间隔问题

以上讨论问题都是基于样本点完全的线性可分，我们称为硬间隔如下图：

如果存在部分样本点不能完全线性可分，大部分样本点线性可分的情况，如下图所示：

那么我们就需要用到软间隔，相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，比如：

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

$$y\cdot (w^T\cdot x_i+b)\ge 1$$

为了度量这个间隔软到何种程度，我们为每个样本引入一个“ 松弛变量 ”${\xi }_i,{\xi }_i\ge 0$，（中文：克西）加入松弛变量后，我们的约束条件变成 $ y\cdot (w^T\cdot x_i +b) \ge 1 -\xi_i$，这样不等式就不会那么严格，数据点在不同的约束条件下的情况如下：

内部点：$y\cdot (w^T\cdot x_i+b)\ge 1$,即 ${\xi }_i=0$

边界点：$y\cdot (w^T\cdot x_i+b)=1$,即${\xi }_i=0$

正确误差点：$y\cdot (w^T\cdot x_i+b)=1-{\xi }_i$,即 $0<{\xi }_i<1$

错误误差点：$y\cdot (w^T\cdot x_i+b)=1-{\xi }_i$,即${\xi }_i\ge 1$

5.2、优化SVM目标函数（了解）

加入软间隔后我们的目标函数变成了：

$$min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_{i}s.t1-y(w^T\cdot x_i+b)-{\xi }_i\le 0,{\xi }_i\ge 0,i=1,2,\cdots ,n---\mathrm{式}h$$

其中C是一个大于0的常数，这里在原有的目标函数中加入$C\sum _{i=1}^n{\xi }_i$可以理解为错误样本的惩罚程度，我们希望在对应条件下$ min\frac{1}{2}||w||^2 + C\sum\limits_{i=1}^n\xi_i$\mathrm{变}\mathrm{小}，\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{也}\mathrm{是}\mathrm{希}\mathrm{望}$ C\sum\limits_{i=1}^n\xi_i$\mathrm{变}\mathrm{小}，\mathrm{当}C\mathrm{为}\mathrm{无}\mathrm{穷}\mathrm{大}，$\xi_i$\mathrm{必}\mathrm{然}\mathrm{无}\mathrm{穷}\mathrm{小}【0】，\mathrm{这}\mathrm{样}\mathrm{的}\mathrm{话}SVM\mathrm{就}\mathrm{变}\mathrm{成}\mathrm{一}\mathrm{个}\mathrm{完}\mathrm{全}\mathrm{线}\mathrm{性}\mathrm{可}\mathrm{分}\mathrm{的}SVM。\mathrm{如}\mathrm{果}C\mathrm{为}\mathrm{有}\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{值}\mathrm{时}，$\xi_i$对应的会有一个大于0的值，这样的SVM就是允许部分样本不遵守约束条件。

接下来我们对新的目标函数h式求解最优化问题，步骤与 4、最小化SVM目标函数【硬间隔】完全线性可分步骤完全一样。

1. 构造拉格朗日函数

将h式目标函数改写成如下：

$$min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_{i}s.t1-y(w^T\cdot x_i+b)-{\xi }_i\le 0,{\xi }_i\ge 0,i=1,2,\cdots ,n---\mathrm{式}h$$

构造拉格朗日函数如下：

$$\begin{array}{rl}\underset{w,b,\xi }{min}\underset{\lambda ,\mu }{max}L(w,b,\xi ,\lambda ,\mu )=& min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)-{\xi }_i]-\sum _{i=1}^n{\mu }_i{\xi }_i\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,n---\mathrm{式}i\end{array}$$

上式中${\lambda }_i,{\mu }_i$是拉格朗日乘子，$w,b,\xi$是我们要计算的主问题参数。

2. 对偶关系转换

目标函数是个下凸函数，对应的拉格朗日函数复合强对偶性，所以可以根据强对偶向，将对偶问题转换为：

$$\underset{w,b,\xi }{min}\underset{\lambda ,\mu }{max}L(w,b,\xi ,\lambda ,\mu )=\underset{\lambda ,\mu }{max}\underset{w,b,\xi }{min}L(w,b,\xi ,\lambda ,\mu )$$

即：

$$\begin{array}{rl}\underset{\lambda ,\mu }{max}\underset{w,b,\xi }{min}L(w,b,\xi ,\lambda ,\mu )=& \frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)-{\xi }_i]-\sum _{i=1}^n{\mu }_i{\xi }_i\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,n---\mathrm{式}j\end{array}$$

使用j式对$w,b,\xi$求导，并令导数为零，得到如下关系：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i=0\\ \\ & \frac{\partial L}{\partial b}=\sum _{i=1}^n{\lambda }_i\cdot y_i=0\\ \\ & \frac{\partial L}{\partial \xi }=C\sum _{i=1}^{n}1-\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n{\mu }_i=0\end{array}$$

整理之后得到：

$$\{\begin{array}{rl}& w=\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i\\ \\ & 0=\sum _{i=1}^n{\lambda }_i\cdot y_i\\ \\ & C={\lambda }_i+{\mu }_i\end{array}$$

将以上关系代入到 j 式：

$$\begin{array}{rl}& \underset{\lambda ,\mu }{max}L(w,b,\xi ,\lambda ,\mu )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i+\sum _{i=1}^n{\lambda }_i[1-y_i(w^T\cdot x_i+b)-{\xi }_i]-\sum _{i=1}^n{\mu }_i{\xi }_i\\ \\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^n{\lambda }_i{\xi }_i+\sum _{i=1}^n{\mu }_i{\xi }_i+\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n{\lambda }_i{y}_i(\sum _{j=1}^n{\lambda }_j{x}_j{y}_j\cdot x_i+b)-\sum _{i=1}^n{\lambda }_i{\xi }_i-\sum _{i=1}^n{\mu }_i{\xi }_i\\ \\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{y}_i{\lambda }_j{y}_j(x_i\cdot x_j)\\ \\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{y}_i{\lambda }_j{y}_j(x_i\cdot x_j)\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,nC-{\lambda }_i-{\mu }_i=0---\mathrm{式}k\end{array}$$

我们发现上式中求$\underset{\lambda ,\mu }{max}L(w,b,\xi ,\lambda ,\mu )$与$\mu$没有关系，但是为什么可以消掉是因为$C={\lambda }_i+{\mu }_i$，所以在约束条件中一定有此条件，所以我们得到最终的目标函数可以写成如下：

$$\begin{array}{rl}\underset{\lambda }{max}& L(w,b,\xi ,\lambda ,\mu )=\underset{\lambda }{max}[\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)]\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,nC-{\lambda }_i-{\mu }_i=0---\mathrm{式}L\end{array}$$

推导到以上之后，我们发现结果和硬间隔结果一样，参照4.3 d式，只是结果中多了约束条件$C={\lambda }_i+{\mu }_i$。

3.求解结果

同样我们也可以利用SMO算法对式L求解得到一组合适的$\lambda$值和$\mu$值，由于综上所述，我们可以的到最终的w和b的值如下：

$$\{\begin{array}{rl}& w=\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i\\ \\ & b=\frac{1}{S}\sum _{i\in S}(y_i-w^T\cdot x_i)\end{array}$$

这里得到的w和b虽然和硬分割结果一样，但是这是加入松弛变量之后得到的w和b的值，根据L式的条件$C={\lambda }_i+{\mu }_i$和 ${\lambda }_i\ge 0,{\mu }_i\ge 0$，结合h式，C越大，必然导致松弛越小，如果C无穷大，那么就意味着模型过拟合，在训练SVM时，C是我们需要调节的参数。

那么确定w和b之后，我们就能构造出最大分割超平面：$w^T\cdot x+b=0$，新来样本对应的特征代入后得到的结果如果是大于0那么属于一类，小于0属于另一类。

5.3、SVM代码演练

二维超平面案例演示

• 构造数据

import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC # 分类算法
from sklearn import datasets
X,y = datasets.make_blobs(n_samples=100,# 样本量
                    n_features=2,# 二维数据，便于画图展示
                    centers=2,# 两类
                    random_state=3)# 随机数状态，固定了
display(X.shape,y.shape,np.unique(y))
plt.scatter(X[:,0],X[:,1],c=y)
plt.show()

• 建模

# kernel 表示核函数：linear，线性
svc = SVC(kernel = 'linear') 
svc.fit(X,y)
display(svc.score(X,y))
# 获取斜率和截距
w_ = svc.coef_# 特征两个
b_ = svc.intercept_
display(w_,b_)

• 绘制分离超平面

符号，使用什么表示，无影响

得到y关于x的方程

边界线的计算，算的就是截距

$w_1、w_2\mathrm{和}b\mathrm{是}\mathrm{上}\mathrm{面}\mathrm{计}\mathrm{算}\mathrm{出}\mathrm{来}\mathrm{的}\mathrm{斜}\mathrm{率}\mathrm{和}\mathrm{截}\mathrm{距}$

w = - w_[0,0]/w_[0,1]
b, = - b_/w_[0,1]
sv = svc.support_vectors_
x = np.linspace(-5,1,100)
y_result = w * x + b
plt.scatter(X[:,0],X[:,1],c = y)
plt.plot(x,y_result,color = 'red')
# 上边界和下边界
b1 = sv[0][1] - w * sv[0][0]
plt.plot(x, w * x + b1 ,color = 'blue',ls = '--')
b2 = sv[-1][1] - w * sv[-1][0]
plt.plot(x, w * x + b2, color = 'blue', ls = '--')

以乳腺癌为例，使用SVM进行建模训练

from sklearn.svm import SVC
from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import KNeighborsClassifier
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
X,y = datasets.load_breast_cancer(return_X_y=True)
display(X.shape,y.shape)

svc = SVC(kernel='linear')
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=42)
svc.fit(X_train,y_train)
svc.score(X_test,y_test)

%%time
model = SVC(kernel='linear')
scores = 0
for i in range(100):
    X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)
    model.fit(X_train,y_train)
    score = model.score(X_test,y_test)
    scores += score/100
print('100次随机拆分，SVC算法的平均得分是：',scores)

5.4、网格搜索最佳参数

网格搜索就是手动给定模型中想要改动的所有参数，程序自动使用穷举法来将所有的参数或者参数组合都运行一遍，将对应得到的模型做K折交叉验证，将得分最高的参数或参数组合当做最佳结果，并得到模型。

也就是说网格搜索用来获取最合适的一组参数，不需要我们手动一个个尝试。使用网格搜索由于针对每个参数下的模型需要做K折交叉验证最终导致加大了模型训练时间，所以一般我们可以在小的训练集中使用网格搜索找到对应合适的参数值，再将合适的参数使用到大量数据集中训练模型。例如:逻辑回归中使用正则项时，我们可以先用一小部分训练集确定合适的惩罚系数，然后将惩罚系数应用到大量训练集中训练模型。

SVC超参数介绍：

1. 核函数（kernel）: 常用的核函数有线性（linear）、多项式（poly）、径向基函数（Radial basis function，RBF）和sigmoid。核函数的选择将影响模型在特征空间中的映射方式。
2. 惩罚参数（C）: C是一个正则化参数，用于控制模型的复杂度。较小的C值会导致较大的间隔，但可能允许一些误分类。较大的C值会产生较小的间隔，试图最小化训练错误，但可能导致过拟合。
3. gamma（γ）: gamma仅在使用RBF、poly或sigmoid核时需要设置。它控制了单个训练样本的影响范围。较大的gamma值会导致更复杂的决策边界，而较小的gamma值会产生更简单的边界。

from sklearn.svm import SVC
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.model_selection import GridSearchCV
import pandas as pd
X,y = datasets.load_breast_cancer(return_X_y=True)

score = 0
search_space = {'C': np.logspace(-3, 3, 7)}
best_params = []
for i in range(100):
    X_train,X_test,y_train,y_test = train_test_split(X,y)
    model = SVC()
    gc = GridSearchCV(model, param_grid=search_space,cv=5)
    gc.fit(X_train,y_train)
    best_params.append(gc.best_params_['C'])
    best_model = gc.best_estimator_
    best_model.fit(X_train,y_train)
    score += best_model.score(X_test,y_test)
  
print('模型平均得分是：',score)

# 查看最佳参数
pd.value_counts(best_params)

5.5、SVM立体原理可视化

• 构造数据

import numpy as np
from sklearn.svm import SVC
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
rs = np.random.RandomState(256) # 种子，生成随机数字，固定了

X = rs.randn(300,2)

# y目标值，一三象限是1，二四象限是0
y = [1 if i > 0 else 0 for i in X[:,0] * X[:,1]]

plt.figure(figsize=(6,6))
plt.scatter(X[:,0],X[:,1],c = y)

• 建模

svc = SVC(kernel='rbf')

# 规律，一三象限是一个类别，二四象限是另一个类别
svc.fit(X,y)

• 预测

X1 = np.linspace(-3,3,200)
X2 = np.linspace(-3,3,180)

X1,X2 = np.meshgrid(X1,X2)

# 测试数据,36000个测试点，密密麻麻
X_test = np.column_stack([X1.ravel(),X2.ravel()])

plt.scatter(X_test[:,0],X_test[:,1])

• 可视化

# SVC对数据划分，直线划分两类
# 高维，超平面
# 不同点，距离超平面不同！
d = svc.decision_function(X_test)# 36000个距离
print(d.max(),d.min())

• 轮廓线

# 轮廓线
plt.figure(figsize=(6,6))
plt.contour(X1,X2,d.reshape(180,200))

• 轮廓面

# 轮廓面
plt.figure(figsize=(6,6))
plt.contourf(X1,X2,d.reshape(180,200))

• 3D距离可视化

plt.figure(figsize=(12,9))
ax = plt.subplot(111,projection = '3d')

ax.contourf(X1,X2,d.reshape(180,200))
ax.view_init(50,-60)

5.6、超参数筛选案例

• 加载数据

import numpy as np
from sklearn.svm import SVC
def read_data(path):
    with open(path) as f :
        lines=f.readlines()
    lines=[eval(line.strip()) for line in lines]
    X,y=zip(*lines)
    X=np.array(X)
    y=np.array(y)
    return X,y
    
X_train,y_train = read_data('./data/train_data')
display(X_train.shape)
X_test,y_test = read_data('./data/test_data')
display(X_test.shape)

• 建模预测

svc = SVC(kernel='sigmoid')
svc.fit(X_train,y_train.ravel())
svc.score(X_test,y_test.ravel())

• 超参数筛选

%%time
svc = SVC(kernel='sigmoid') 
# 不同C，效果不同啊：0.1,0.5,1,10……
params = {'C':np.logspace(-3,3,50),'tol':[0.0001,0.001,0.01,0.1,1]}
gc = GridSearchCV(estimator = svc,param_grid = params,cv = 5)
gc.fit(X_train,y_train.ravel())
print('最优超参数：',gc.best_params_)
best_model = gc.best_estimator_
best_model.fit(X_train,y_train)
best_model.score(X_test,y_test.ravel())

6、SVM Hinge Loss【了解】

软间隔情况下，SVM的目标函数如下：

$$min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_{i}s.t1-y(w^T\cdot x_i+b)-{\xi }_i\le 0,{\xi }_i\ge 0,i=1,2,\cdots ,n---\mathrm{式}h$$

其实这里我们说SVM的损失主要说的就是上式中的松弛变量${\xi }_i$损失，当所有样本总的${\xi }_i$为0时那么就是一个完全线性可分的SVM；如果SVM不是线性可分，那么我们希望总体样本的松弛变量$\sum _{i=1}^n{\xi }_i$越小越好。

根据h式的条件$ 1-y(w^T\cdot x_i +b) - \xi_i \le 0,\xi_i \ge 0$我们可以改写成如下：

$${\xi }_i\ge 1-y(w^T\cdot x_i+b),{\xi }_i\ge 0$$

根据下图结合以上两个条件我们可以继续改写成如下：

$${\xi }_i=max(0,1-y(w^T\cdot x_i+b))---\mathrm{式}m$$

上式等价于:

$${\xi }_i=\{\begin{array}{rl}& 0y(w^T\cdot x_i+b)\ge 1\\ \\ & 1-y(w^T\cdot x_i+b)y(w^T\cdot x_i+b)<1\end{array}$$

以上公式就是SVM的损失函数，称为“Hinge Loss”，也被叫做“合页损失函数”。其图像如下：

特点是当$y(w^T\cdot x_i+b)\ge 1$时损失为0。

我们可以将m式代入到h式得到新的目标函数，暂时先不关注约束条件，新的目标函数如下：

$$min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^{n}max(0,1-y(w^T\cdot x_i+b))$$

针对新的目标函数我们同样也是最小化整体目标函数。我们发现以上目标函数与逻辑回归L2正则化的损失函数在形式上非常类似，将上式可以改写成如下：

$$min\frac{1}{2}||w|{|}^2+LOSS$$

逻辑回归L2正则化损失函数如下：

$$J(\theta )=-\sum _{i=1}^n[y^{(i)}\ln (h_{\theta }(x^{(i)}))+(1-y^{(i)})\ln (1-h_{\theta }(x^{(i)}))]+\lambda \sum _{i=1}^n{w}_i^2$$

也可以改写成如下：

$$J(\theta )=LOSS+\lambda \sum _{i=1}^n{w}_i^2$$

如果将逻辑损失函数图像与“Hinge Loss”图像放在一起图像如下：

通过上图我们可以看出，在训练逻辑回归时，损失永远不为0，因此即使分类正确，逻辑回归仍然会不停的训练，以求得更小的损失和更大的概率，但是极有可能出现过拟合，这就是为什么我们需要在梯度下降中提前终止的原因。但是在SVM中，如果分类正确可以直接达到$\sum _{i=1}^n{\xi }_i=0$，不再进行对分类无益的训练，即学习到一定程度就不再学习。

7、核函数

7.1、非线性核函数

在前面SVM讨论的硬间隔和软间隔都是指的样本完全可分或者大部分样本点线性可分的情况。那么如果样本完全线性不可分如下图所示：

我们可以使用升维方式来解决这种线性不可分的问题，例如目前只有两个维度$x_1,x_2$，我们可以基于已有的维度进行升维得到更多维度，例如：$x_1,x_2,x_1{x}_2$，这样我们可以将以上问题可以转换成高维可分问题，如下图：

SVM中线性不可分问题就是非线性SVM问题，对这种问题我们可以将样本映射到高维空间，再通过间隔最大化的方式学习得到支持向量机。

7.2、核函数（kernel function）

假设原有特征有如下三个$x_1,x_2,x_3$，那么基于三个已有特征进行两两组合（二阶交叉）我们可以得到如下更多特征：

$$[x_1^2、x_1{x}_2、x_1{x}_3、x_2^2、x_2{x}_1、x_2{x}_3、x_3^2、x_3{x}_1、x_3{x}_2]$$

我们在训练模型时将以上组合特征可以参与到模型的训练中，其代价是运算量过大，比如原始特征有m个，那么二阶交叉的维度为$C_m^2$个，这种量级在实际应用中很难实现，那么有没有一种方式可以在升维的同时可以有效的降低运算量，在非线性SVM中，核函数就可以实现在升维的同时可以有效降低运算量，那么核函数是什么？

有两个向量$m=[m_1,m_2,m_3{]}^T,n=[n_1,n_2,n_3{]}^T$，我们分别对两个向量进行相同升维分别记为$\varphi m,\varphi n$：

$$\begin{array}{rl}& \varphi m=[m_1^2、m_1{m}_2、m_1{m}_3、m_2^2、m_2{m}_1、m_2{m}_3、m_3^2、m_3{m}_1、m_3{m}_2{]}^T\\ \\ & \varphi n=[n_1^2、n_1{n}_2、n_1{n}_3、n_2^2、n_2{n}_1、n_2{n}_3、n_3^2、n_3{n}_1、n_3{n}_2{]}^T\end{array}$$

之后计算两者内积如下：

$$\begin{array}{rl}\varphi m\cdot \varphi n& =m_1^2{n}_1^2+m_1{m}_2{n}_1{n}_2+m_1{m}_3{n}_1{n}_3+m_2^2{n}_2^2+m_2{m}_1{n}_2{n}_1\\ \\ & +m_2{m}_3{n}_2{n}_3+m_3^2{n}_3^2+m_3{m}_1{n}_3{n}_1+m_3{m}_2{n}_3{n}_2\\ \\ & =m_1^2{n}_1^2+m_2^2{n}_2^2+m_3^2{n}_3^2+2m_1{m}_2{n}_1{n}_2+2m_1{m}_3{n}_1{n}_3+2m_2{m}_3{n}_2{n}_3---\mathrm{式}o\end{array}$$

另外我们计算m和n的内积如下：

$$m\cdot n=m_1{n}_1+m_2{n}_2+m_3{n}_3$$

对结果进行平方得到：

$$\begin{array}{rl}(m\cdot n{)}^2& =(m_1{n}_1+m_2{n}_2+m_3{n}_3{)}^2\\ \\ & =m_1^2{n}_1^2+m_2^2{n}_2^2+m_3^2{n}_3^2+2m_1{m}_2{n}_1{n}_2+2m_1{m}_3{n}_1{n}_3+2m_2{m}_3{n}_2{n}_3---\mathrm{式}p\end{array}$$

【备注】：$(a+b+c{)}^2=a^2+b^2+c^2+2ab+2ac+2bc$

我们发现o式和p式结果一样，也就是

$$\varphi m\cdot \varphi n=(m\cdot n{)}^2---\mathrm{式}q$$

以上在m和n向量中只有3个元素时推导成立，那么在m和n中如果有多个元素时也一样成立。

我们发现，如果最终目标只是计算向量升维后的内积$\varphi m\cdot \varphi n$，根据q式可知，我们可以先计算原始向量的内积$m\cdot n$，再进行平方运算，而不需要真正的进行高运算量的升维操作。这种通过两个低维向量进行数学运算得到它们投影至高维空间时向量的内积方法叫做核方法，相应的算法叫做核函数，上面案例核函数记为：

$$K(m\cdot n)=\varphi m\cdot \varphi n=(m\cdot n{)}^2$$

以上核函数叫做多项式核函数，常用的核函数有如下几种，不同的核函数的区别是将向量映射到高维空间时采用的升维方法不同，不过高维向量都是不需要计算出来的。

• 线性核函数：

$$K(x_i\cdot x_j)=x_i^T\cdot x_j$$

• 多项式核函数：

$$K(x_i\cdot x_j)=(\alpha (x_i^T\cdot x_j)+c{)}^d\alpha ,c,d\mathrm{都}\mathrm{是}\mathrm{参}\mathrm{数}$$

• 高斯核函数：

$$K(x_i\cdot x_j)=e^{-\frac{||x_i-x_j|{|}^2}{2{\delta }^2}}$$

7.3、核函数在SVM中应用

在非线性SVM中，我们可以对原始特征进行升维，原有的超平面$w^T\cdot x+b=0$变成了$w^T\cdot \varphi x+b=0$，根据 L 式SVM目标函数：

$$\begin{array}{rl}\underset{\lambda }{max}& L(w,b,\xi ,\lambda ,\mu )=\underset{\lambda }{max}[\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j)]\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,nC-{\lambda }_i-{\mu }_i=0---\mathrm{式}L\end{array}$$

可知最终经过对偶处理后的目标函数如下：

$$\begin{array}{rl}\underset{\lambda }{max}& L(w,b,\xi ,\lambda ,\mu )=\underset{\lambda }{max}[\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(\varphi x_i\cdot \varphi x_j)]\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,nC-{\lambda }_i-{\mu }_i=0\end{array}$$

以上公式与l式不同的是只是将$x_i\cdot x_j$转换成了$\varphi x_i\cdot \varphi x_j$，这样我们可以将上式进而转换成下式：

$$\begin{array}{rl}\underset{\lambda }{max}& L(w,b,\xi ,\lambda ,\mu )=\underset{\lambda }{max}[\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j(x_i\cdot x_j{)}^2]\\ \\ & s.t{\lambda }_i\ge 0,{\mu }_i\ge 0i=1,2,\cdots ,nC-{\lambda }_i-{\mu }_i=0---\mathrm{式}r\end{array}$$

这样我们可以通过核函数将数据映射到高维空间，但是核函数是在低维上进行计算，而将实质上的分类效果表现在了高维空间上，来解决在原始空间中线性不可分的问题。

在SVM中我们可以使用常用的核函数：线性核函数、多项式核函数、高斯核函数来进行升维解决线性不可分问题，应用最广泛的就是高斯核函数，无论是小样本还是大样本、高维或者低维，高斯核函数均适用，它相比于线性核函数来说，线性核函数只是高斯核函数的一个特例，线性核函数适用于数据本身线性可分，通过线性核函数来达到更理想情况。高斯核函数相比于多项式核函数，多项式核函数阶数比较高时，内部计算时会导致一些元素值无穷大或者无穷小，而在高斯核函数会减少数值的计算困难。

综上，我们在非线性SVM中使用核函数时，先使用线性核函数，如果不行尝试换不同的特征，如果还不行那么可以直接使用高斯核函数。

非线性SVM使用核函数代码如下：

from sklearn import svm
from sklearn import datasets
from sklearn.model_selection import train_test_split as ts

X,y = datasets.load_wine(return_X_y=True)

#split the data to  7:3
X_train,X_test,y_train,y_test = ts(X,y,test_size=0.3)
print(y_test)
# select different type of kernel function and compare the score

# kernel = 'rbf'
clf_rbf = svm.SVC(kernel='rbf')
clf_rbf.fit(X_train,y_train)
score_rbf = clf_rbf.score(X_test,y_test)
print("The score of rbf is : %f"%score_rbf)

# kernel = 'linear'
clf_linear = svm.SVC(kernel='linear')
clf_linear.fit(X_train,y_train)
score_linear = clf_linear.score(X_test,y_test)
print("The score of linear is : %f"%score_linear)

# kernel = 'poly'
clf_poly = svm.SVC(kernel='poly')
clf_poly.fit(X_train,y_train)
score_poly = clf_poly.score(X_test,y_test)
print("The score of poly is : %f"%score_poly)

7.4、非线性核函数

• 数据构建

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
X,y = datasets.make_circles(n_samples=100,factor=0.7)

X += np.random.randn(100,2)*0.03

display(X.shape,y.shape)
plt.figure(figsize=(5,5))
cmap = ListedColormap(colors = ['blue','red'])
plt.scatter(X[:,0],X[:,1],c = y,cmap = cmap)

• 建模预测核函数对比

svc = SVC(kernel='linear')
svc.fit(X,y)
print('线性核函数：',svc.score(X,y))

svc = SVC(kernel='rbf')
svc.fit(X,y)
print('高斯核函数：',svc.score(X,y))

svc = SVC(kernel='poly',degree = 2)
svc.fit(X,y)
print('高斯核函数：',svc.score(X,y))

7.5、支持向量机回归问题

• 数据构建

import numpy as np
from sklearn.svm import SVR
import matplotlib.pyplot as plt
X = np.linspace(0,2*np.pi*2,100).reshape(-1,1)
y = np.sin(X)
plt.scatter(X,y)

• 不同核函数建模对比

# 线性核函数
svr = SVR(kernel='linear')
svr.fit(X,y.ravel())
y_ = svr.predict(X)
plt.scatter(X,y)
# 绘制预测结果
plt.plot(X,y_,color = 'red')

# 高斯核函数
svr = SVR(kernel='rbf')
svr.fit(X,y.ravel())

y_ = svr.predict(X)
plt.scatter(X,y)

# 绘制预测结果
plt.plot(X,y_,color = 'red')

# 多项式核函数
svr = SVR(kernel='poly',degree=2)
svr.fit(X,y.ravel())
y_ = svr.predict(X)
plt.scatter(X,y)
# 绘制预测结果
plt.plot(X,y_,color = 'red')

7.6、SVM-天猫双十一销量预测

• 数据构造

import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVR
X = np.arange(2009,2020) - 2008
y = np.array([0.5,9.36,52,191,350,571,912,1207,1682,2135,2684])
plt.scatter(X,y,color = 'red')
# 划分份数多，画图，曲线平滑
X_test = np.linspace(2009,2019,100).reshape(-1,1) - 2008

• 建模拟合

# 线性核函数
svr = SVR(kernel = 'linear')
svr.fit(X.reshape(-1,1),y)
y_ = svr.predict(X_test)
plt.scatter(X,y,color = 'red')
plt.plot(X_test.ravel(),y_,color = 'green')
svr.coef_

# 高斯核函数
svr = SVR(kernel = 'rbf')
svr.fit(X.reshape(-1,1),y)
y_ = svr.predict(X_test)
plt.scatter(X,y,color = 'red')
plt.plot(X_test.ravel(),y_,color = 'green')

# 多项式核函数
svr = SVR(kernel = 'poly',coef0=20,degree = 3)
svr.fit(X.reshape(-1,1),y)
y_ = svr.predict(X_test)
plt.scatter(X,y,color = 'red')
plt.plot(X_test.ravel(),y_,color = 'green')

8、支持向量机SVM特点

8.1、抗干扰能力强

根据一些样本点，我们可以通过拉格朗日乘数法、KKT条件、对偶问题、SMO算法计算出支持向量机SVM的分类线$w^T\cdot x+b=0$,其中

$$\{\begin{array}{rl}& w=\sum _{i=1}^n{\lambda }_i\cdot x_i\cdot y_i\\ \\ & b=\frac{1}{S}\sum _{i\in S}(y_i-w^T\cdot x_i)\end{array}$$

S代表的是边界上的样本点。得到的分割下如下图所示：

我们可以看出SVM在训练过程中找到的是两类点的分割线，计算样本中有少量异常点，在训练模型时依然能很正确的找到中间分割线，因为训练SVM时考虑了全量数据，确定这条线的b时只与支持向量点（边界上的点）有关。同样在测试集中就算有一些样本点是异常点也不会影响其正常分类，SVM具有抗干扰能力强的特点。

此外，由于训练SVM需要所有样本点参与模型训练，不然不能确定这条线，所以当数据量大时，SVM训练占用内存非常大。这是SVM模型的缺点。

8.2、二分类及多分类

SVM同样支持多分类，我们可以将一个多分类问题拆分成多个二分类问题，例如有A,B,C三类，我们使用SVM训练时可以训练3个模型，第一个模型针对是A类和不是A类进行训练。第二个模型针对是B类和不是B类进行训练。第三个模型针对是C类和不是C类进行训练。这样可以解决多分类问题。

9、SVM人脸识别实战

9.1、加载数据

import numpy as np
from sklearn.svm import SVC
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.decomposition import PCA
from sklearn.metrics import accuracy_score
from sklearn import datasets
from sklearn.model_selection import GridSearchCV
# 加载人脸数据，labled faces wild
data = datasets.fetch_lfw_people(resize=1,min_faces_per_person=70)
X = data['data']
y = data['target']
faces = data['assets']
display(X.shape,faces.shape,y.shape)
target_names = data['target_names']
target_names

9.2、数据查看

index = np.random.randint(0,1288,size = 1)[0]
face = X[index].reshape(125,94)
name = y[index] # 根据索引获取，名字

print(target_names[name])

display(face.shape)
plt.imshow(face,cmap = 'gray')

9.3、数据降维

%%time
# 进行数据的降维
pca = PCA(n_components=0.95)
X_pca = pca.fit_transform(X)
display(X.shape,X_pca.shape)

9.4、超参数筛选

svc = SVC()
X_train,X_test,y_train,y_test = train_test_split(X_pca,y,test_size=0.2,random_state=512)
params = {'C':np.logspace(-3,3,20),'kernel':['rbf','poly','linear'],'tol':[0.01,0.001,0.0001]}
gc = GridSearchCV(estimator = svc,param_grid = params,cv = 5)
gc.fit(X_train,y)

9.5、最佳模型复训

svc = gc.best_estimator_
svc.fit(X_train,y_train)
print('训练数据得分：',svc.score(X_train,y_train))
print('测试数据的得分：',svc.score(X_test,y_test))

9.6、可视化模型预测结果

plt.figure(figsize=(5 * 2, 10 * 3))
for i in range(50):
    plt.subplot(10,5,i + 1) # 子视图
    plt.imshow(faces_test[i],cmap = 'gray')
    plt.axis('off') # 刻度关闭
    # 是数字
    true_name = target_names[y_test[i]].split(' ')[-1]
    predict_name = target_names[y_pred[i]].split(' ')[-1]
    plt.title('True:%s\nPred:%s' % (true_name,predict_name))