【机器学习】SVM支持向量机（一）

介绍

支持向量机（Support Vector Machine, SVM）是一种监督学习模型，广泛应用于分类和回归分析。SVM 的核心思想是通过找到一个最优的超平面来划分不同类别的数据点，并且尽可能地最大化离该超平面最近的数据点（支持向量）之间的间隔。这使得 SVM 具有良好的泛化能力，即能够很好地处理未见过的数据。

SVM 的工作原理

• 线性可分情况：
  • 在最简单的情况下，如果数据集是线性可分的，SVM 试图找到一个最佳的直线（在二维空间中）或超平面（在多维空间中），它能将两个类别完全分开。
  • 这个超平面的选择不仅取决于它可以正确分类训练数据，还在于它能够使两类样本到超平面的距离最大。这样的决策边界被称为最大间隔超平面。
• 非线性可分情况：
  • 当数据不是线性可分时，可以通过核函数（Kernel Function）将原始特征映射到更高维度的空间，在这个新的空间中寻找线性分离的可能性。
  • 常见的核函数包括多项式核、径向基函数（RBF Kernel）、Sigmoid 核等。选择合适的核函数对于提高 SVM 的性能至关重要。
• 软间隔与正则化：
  • 现实世界的数据往往存在噪声或者异常值，严格的线性分割可能会导致过拟合问题。因此，引入了软间隔的概念，允许一些数据点位于错误的一侧。
  • 正则化参数 C 控制着对误分类的惩罚程度；较小的 C 值意味着更宽的间隔但可能更多的容许误差，而较大的 C 则追求更高的准确率但可能导致过拟合。
• 支持向量：
  • 决定最终超平面位置的关键数据点称为支持向量。这些点位于间隔边界上，或者是在软间隔设定下违反边界的点。
  • 只有支持向量影响了模型的学习过程，其他不在间隔内的点对构建超平面没有贡献。
• 多分类问题：
  • 对于多于两个类别的分类任务，可以采用一对多（One-vs-Rest, OvR）或一对一（One-vs-One, OvO）的方法构建多个二分类器，然后根据投票或其他策略确定最终类别标签。

SVM 的优点

• 高效率：在高维空间表现良好，即使当特征数量超过样本数量时也能有效工作。
• 强大的数学基础：基于凸优化理论，保证了全局最优解的存在性和唯一性。
• 适用于小规模数据集：不需要大量的训练数据即可获得较好的效果。
• 灵活性：通过不同的核函数可以适应各种类型的数据分布。

SVM 的局限性

• 计算复杂度：随着训练样本数目的增加，训练时间和内存消耗也会显著增长。
• 对参数敏感：如核函数的选择、正则化参数 C 和核参数（例如 RBF 的 gamma 参数），需要仔细调整以达到最佳性能。
• 解释性差：相比于决策树之类的算法，SVM 提供的模型通常难以直观理解。

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||}=\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)式\\ & \\ & w^T\cdot x_i+b\le 1y=-1(2)式\end{array}$$

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

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

所以在计算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||s.ty\cdot (w^T\cdot x_i+b)\ge 1,i=1,2,\cdots ,n$$

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

3、拉格朗日乘数法、KKT条件、对偶

3.1、拉格朗日乘数法

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

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

$$minf(x)s.th(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---式①$$

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

那我们可以考虑加入一个“松弛变量”${\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---式②$$

以上②式变成了等式条件约束优化问题，我们就可以使用拉格朗日乘数法来求解满足等式条件下$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$及为什么计算的是$minL(x,\lambda ,\alpha )$下对应的x值，这里证明涉及到很多几何性质，这里也不再证明。

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

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

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

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

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

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

由于$\lambda =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$。

上面方程组中的⑥式可以改写成$\lambda \cdot h(x)=0$。由于${\alpha }^2\ge 0$，所以将⑤式也可以改写成$h(x)\le 0$，所以上面方程组也可以转换成如下：

$$\{\begin{array}{rl}& \frac{\partial L}{\partial x}=\frac{\partial f(x)}{\partial x}+\lambda \frac{\partial h(x)}{\partial x}=0\\ & \\ & h(x)\le 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---式③$$

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

由于${\alpha }^2\ge 0$且$\lambda \ge 0$，$\lambda {\alpha }^2$一定大于零，所以进一步可以简化为如下：

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

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

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

也就是说一定有：

$$L(x,\lambda )\le P$$

为了找到最优的$\lambda$值，我们一定想要$L(x,\lambda )$接近P，即找到合适的$\lambda$最大化$L(x,\lambda )$，可以写成$\underset{\lambda }{\max }L(x,\lambda )$，所以⑧式求解合适的$x,\lambda$值最终可以转换成如下：

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

3.3、对偶问题

对偶问题是我们定义的一种问题，对于一个不等式约束的原问题：

$$\underset{x}{\min }\underset{\lambda }{\max }L(x,\lambda )s.t\lambda \ge 0$$

我们定义对偶问题为（对上面方程的求解等效求解下面方程）：

$$\underset{\lambda }{\max }\underset{x}{\min }L(x,\lambda )s.t\lambda \ge 0$$

其实就是把min和max对调了一下，当然对应的变量也要变换。

对偶问题有什么好处呢？对于原问题，我们要先求里面的max，再求外面的min。而对于对偶问题，我们可以先求里面的min。有时候，先确定里面关于x的函数最小值，比原问题先求解关于$\lambda$的最大值，要更加容易解。

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

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

$$\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 )$$

所有的下凸函数都满足强对偶性，也就是说所有下凸函数都满足上式。

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

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

$$min\frac{1}{2}||w||s.ty\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.t1-y\cdot (w^T\cdot x_i+b)\ge 0,i=1,2,\cdots ,n$$

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

$$\underset{w,b}{\min }\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)]s.t{\lambda }_i\ge 0---式a$$

以上不等式转换成拉格朗日函数必须满足KKT条件，详见3.2【KKT条件】，这里满足的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\\ & \\ & \lambda \ge 0\end{array}$$

4.2、对偶转换

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

$$\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---式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}---式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)---式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)---式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}_{+}{\lambda }_2{y}_2+c=0---式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}---式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---式f\\ & \\ & \lambda \ge 0\end{array}$$

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

$$y_i(w^T\cdot x_i+b)=1---式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属于另一类。

原理与可视化

# 超平面，怎么找到的

导包

import numpy as np
from sklearn.svm import SVC
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

创建数据

X = np.random.randn(3000,2) # 训练数据y = [1 if i > 0 else 0 for i in X[:,0] * X[:,1]]plt.scatter(X[:,0],X[:,1],c = y)

<matplotlib.collections.PathCollection at 0x189e97eb760>

建模学习

svc = SVC(kernel='poly',degree=2)# 高斯核函数，数据变换，变形，升维
svc.fit(X,y)
svc.score(X,y)

0.9943333333333333

创建预测数据

a = [2,3,5]
b = [1,4,7,9]print(a,b)

[2, 3, 5] [1, 4, 7, 9]

A,B = np.meshgrid(a,b)
print(A)
print('---------')
print(B)
plt.scatter(A,B)

[[2 3 5][2 3 5][2 3 5][2 3 5]]
---------
[[1 1 1][4 4 4][7 7 7][9 9 9]]<matplotlib.collections.PathCollection at 0x189e9270400>

f1 = np.linspace(-3,3,200)
f2 = np.linspace(-3,3,180)F1,F2 = np.meshgrid(f1,f2) # 网格交叉
X_test = np.column_stack([F1.ravel(),F2.reshape(-1)])plt.scatter(X_test[:,0],X_test[:,1])

<matplotlib.collections.PathCollection at 0x189ea04bb80>

算法预测

# 算法给我们的预测的类别
y_pred = svc.predict(X_test)plt.scatter(X_test[:,0],X_test[:,1],c = y_pred)

<matplotlib.collections.PathCollection at 0x189e98b30a0>

算法原理可视化【超平面】

d = svc.decision_function(X_test)
d

array([102.28708056, 101.26529785, 100.24339038, ..., 100.24339038,101.26529785, 102.28708056])

d.min()

-103.5053953169917

绘制轮廓线

plt.figure(figsize=(6,6))
plt.contour(F1,F2,d.reshape(180,200))# 等高线

<matplotlib.contour.QuadContourSet at 0x189eb1e1b50>

轮廓面

plt.figure(figsize=(6,6))
plt.contourf(F1,F2,d.reshape(180,200))

<matplotlib.contour.QuadContourSet at 0x189ed0713d0>

3D显示距离

plt.figure(figsize=(12,9))
ax = plt.subplot(111,projection = '3d')ax.contourf(F1,F2,d.reshape(-1,200))
ax.view_init(50,-30)