还是老规矩，这一篇博客是对SVM进行介绍，下一篇博客就是使用SVM进行具体的使用。

SVM介绍

首先介绍SVM是什么，SVM（support vector machine）名为支持向量机，又名支持向量网络，是一个非常经典且高效的分类模型，是一种监督式的学习方法。

从名字上面来理解，SVM分为两个部分，”支持向量（support vector）”以及“机（machine）”。“machine”很简单的理解，就是算法的意思，那么“support vector”是什么呢？ 这个现在不进行介绍，待我慢慢的引入。

线性分类

在介绍SVM之前，我们得先对线性分类器进行介绍。下面是一个二维平面的的分类问题，红色代表类别为+1，蓝色的代表类别是-1。中间的线就代表分割这两类问题的超平面。对于分类问题来说，红色和蓝色的点都是数据集中已知的，而我们的目的就是找到一个最适合的超平面，将数据进行分类。

对于线性二分类模型，给定一组数据\(\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}\)， 其中\(\boldsymbol{x}_{i} \in \mathbb{R}^{d}, y \in\{-1,1\}\)，二分类任务的目标是希望从数据中学得一个假设函数\(h: \mathbb{R} \rightarrow\{-1,1\}\)，使得\(h(x_i) = y_i\)

那么问题来了，我们如何去寻找一个能够将\(y_i = \pm1\)划分开的超平面？首先我们可以设超平面的函数是：

这里有一个值得注意的点，下面的这个公式会在后面的推导中经常用到。

尽管有很多的问题都是线性不可分的，但是呢，目前我们只讨论线性可分问题，到后面我们再讨论如何将非线性问题转成线性问题。因此，暂时我们不需要去纠结如果是非线性问题怎么办。

我们可以直观的从图中进行感受，这样的超平面是有多个的，那么如何寻找一个最合适的超平面呢（也就是寻找最合适的\(w^{\mathrm{T}}\) 和\(b\)）？接下来引出间隔的概念来寻找最合适的超平面。

间隔

如下图所示，超平面\(\begin{equation}f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\end{equation}\)，则\(x\)为\(x_0\)到超平面的投影，\(x_0\)对应的类别是\(y_0\)，\(w\)为超平面的法向量，\(\gamma\)为\(x_0\)到超平面的距离（带正负号）。

因此

这样我们就推出了间隔的表达式\(\tilde{\gamma} = y_0\gamma\)。对于给定的数据集，我们当然是希望数据集中的数据离超平面越远越好，因为这样所能够容忍的误差也就越大。那么这个远如何来确定呢？接下来让我们讨论什么是最大间隔分类器。

最大间隔分类器

如果我们给定如下的数据集，那么对于下面的数据集，哪一些最不可能分类成功呢？毋庸置疑的，就是最靠近\(\begin{equation}f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\end{equation}\)超平面的数据点(比如下图中被红色和黄色圈出来的点)。而被圈出来的点也就是被称之为“支持向量”。因为在模型中我们考虑他们就可以了。

首先我们假设支持向量分布在\(\omega^Tx+b=\pm 1\)超平面上，这里取值为1只是为了方便，该值并不影响后面的优化结果。很显然，支持向量到超平面\(\omega^Tx+b=\pm 1\)的距离为\(\frac{1}{\|\omega\|}\)。两侧的距离加起来就是\(\frac{2}{\|\omega\|}\)。在前面我们说过，我们希望距离越大越好，也就是说\(\frac{2}{\|\omega\|}\)越大越好，同时对于数据集中数据的分布满足\(y(\omega^T+b)x \geqslant 1\)。因此，我们得到了如下的优化问题：

为了方便后续的推导，该优化问题等价于：

拉格朗日乘子法（Lagrange multipliers）

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引拉格朗日乘子，可将有 \(d\)个变量与\(k\)个约束条件的最优化问题转化为具有\(d+k\)个变量的无约束优化问题求解。下面让我们来进行推导。

拉格朗日乘子法推导

如下图所示\(z=f(x,y)\)，\(g(x,y)=0\)，如果我们需要求\(z\)在\(g(x,y)\)条件下的极值。从几何角度来说，我们可以画出\(z = C_i\)的等高线，等高线与\(g(x,y)\)相切的点\((x_0,y_0)\)即为极值点。如下图所示：

因为在点\((x_0,y_0)\)取得极值，那么，\(\nabla{f(x_0, y_0)} // \nabla{g(x_0, y_0)}\)，也就是说此时梯度平行。也就是说\(({f_x}\'(x_0,y_0),{f_y}\'(x_0,y_0)) // ({g_x}\'(x_0,y_0),{g_y}\'(x_0,y_0))\)（这个是可以证明的，但是在这里就不证明了）因此有：

即：

如果此时我们有一个辅助函数\(L(x,y, \lambda)=f(x,y)+\lambda g(x,y)\)，对其求偏导然后求极值点可得：

显而易见公式\((6)\)和公式\((7)\)相等。因此我们对\(z = f(x,y)\)在条件\(f(x,y) = 0\)的条件下求极值\((x_0,y_0)\)的问题变成了求拉格朗日函数\(L(x,y, \lambda)=f(x,y)+\lambda g(x,y)\)偏导数为0的解。

KKT条件（Karush-Kuhn-Tucker Conditions）

上面我们讨论的是在等式约束条件下求函数极值的问题（也就是\(g(x,y)=0\)）but，如果如果是不等式条件下，我们应该如何来使用拉格朗日函数来求解呢？下面引出KKT条件。

什么是KKT条件呢？它是在满足一些有规则的条件下，一个非线性规划问题能有最优化解法的一个必要条件。也就是说优化问题在最优值处必须满足KKT条件。

例如我们有以下优化问题：

其拉格朗日函数为：

则其KKT条件为：

接下来让我们来解释一下为什么是这样的。（不一定是数学证明）。

下面我们只讨论\(f(x)\)在不等式\(g_i(x)<0\)条件下取\(min\)情况。这里可能有人会说，如果我要求\(max\)怎么办？很简单那，将\(f(x)\)取反即可，就变成了求\(min\)的情况。同样对于\(g_i(x) > 0\)的情况，我们取反就变成了\(g^{\’}(x) = -g_i(x) \lt 0\)。

对于上述讨论，有两种情况如下图（图中\(x^*\)代表极小值点）：

• 情况一：极小值点\(x^*\)在\(g_i(x)<0\)的区域内
• 情况二：极小值点\(x^*\)在\(g_i(x)=0\)上

首先我们先讨论情况二，对于情况二很好理解，此时的“不等式约束”变成了“等式约束”。那么其在极值点满足以下条件：

\(h(x)=0，g(x)=0\)我们很好理解，但是为什么我们对\(\mu\)还要进行限制呢？然后为什么限制还为\(\mu \geq 0\)呢？首先我们来考虑一下\(f(x)\)和\(g(x)\)在\(x^*\)点的梯度方向（首先\(f(x)\)和\(g(x)\)在\(x^*\)点的梯度方向肯定是平行的【梯度的方向代表函数值增加最快的方向】）。

• 对于\(f(x)\)来说，等值线大小由中心到周围逐渐增大，因此它的梯度方向指向可行域。为图中红色的箭头号。
• 对于\(g(x)\)来说，梯度方向肯定是指向大于0的一侧，那么就是要背离可行域。为图中黄色的箭头号。

在前面拉格朗日乘子法中我们有以下推导：

又因为\(g(x)\)和\(f(x)\)梯度方向相反，因此\(\lambda_0 \geq0\)。 因此对于\(公式9\)有\(\mu \geq 0\)。

接下来让我们来讨论情况一。情况一是极小值$x^* \(在\)g(x)$的可行域中，因此，我们可以将其看成没有不等式约束条件。那么其在极值点满足以下条件：

对比两种情况：

• 情况一：\(\mu = 0，g(x) \leq 0\)
• 情况二：\(\mu \geq 0，g(x)=0\)

综合情况一和情况二，可得到KKT条件为：

拉格朗日乘子法对偶问题

对于如下优化问题：

其拉格朗日函数为：

对于上述的优化问题（\(公式10\)）我们可以等价于（下面的称之为主问题）：

证明如下：

其中, 当\(g_i(x)\)不满足约束时, 即\(g_i(x)\gt0\), 我们可以令\(\mu=\infty\), 使得\(\mu_ig_i(x) = \infty\); 当\(h_j(x)\)不满足约束时, 即 \(h_j(x)\ne0\), 我们可以取\(\lambda_j = \infty\), 使得\(\lambda_jh_j(x) = \infty\)。当\(x\)满足约束时, 由于 \(\mu_i\ge0\)，\(g_i(x)\le0\), 则 \(\mu_ig_j(x)\le0\)，因此我们可以取最大值0。 实际上也就是说如果\(公式10\)存在最优解，则最优解必须满足KKT条件。

对于\(公式10\)其对偶问题为：

对偶问题是主问题的下界（他们两个具有弱对偶性）：

你可以记忆成“廋死的骆驼比马大”，还看到一个记忆方法为“宁为凤尾不为鸡头”。hhh

证明如下：

Slater 条件

前面我们讨论了弱对偶性，这里我们将进行讨论Slater条件，但是为什么我们要讨论Slater条件呢？原因很简单，我们想让上面的弱对偶问题转成强对偶问题。

Slater定理是说，当Slater条件成立且原问题是凸优化问题时，则强对偶性成立。这里有几个名词值得注意：

• 凸优化问题

  如果一个优化问题满足如下格式，我们就称该问题为一个凸优化问题：

  \[\begin{array}{}
  \text{min}&f(x)\\
  \text{s.t}&g_i(x)\le0,&i=1,…,m \\
  \text{ }&h_i(x)=0,&i=1,…,p
  \end{array}
  \]

  其中\(f(x)\)是凸函数，不等式约束\(g(x)\)也是凸函数，等式约束\(h(x)\)是仿射函数。

  1. 凸函数是具有如下特性的一个定义在某个向量空间的凸子集\(C\)（区间）上的实值函数\(f\)：对其定义域上任意两点\(x_1,x_2\)总有\(f\left(\frac{x_{1}+x_{2}}{2}\right) \leq \frac{f\left(x_{1}\right)+f\left(x_{2}\right)}{2}\)。

     

  2. 仿射函数

     仿射函数，即最高次数为1的多项式函数。

• 强对偶性

  弱对偶性是\(p* = \min _{x} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \ge \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \min _{x} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = g*\)，也就是\(p^* \ge g^*\)，则强对偶性是\(p^* = g^*\)。

说了这么多，那什么是Slater条件呢？

1. 原问题是凸优化问题
2. 存在\(x\)使得\(g(x) \le0\)严格成立。（换句话说，就是存在\(x\)使得\(g(x) \lt0\)成立）

值得注意的是线性支持向量机满足Slater条件（因为\(\frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}\)和\(1-y_{i}(w^Tx_i+b)\)均为凸函数），也就是它满足强对偶性。

最大间隔分类器与拉格朗日乘子法

前面说了这么多，实际上也就是为这个地方做铺垫。我们可以将最大间隔分类问题转化成在KKT条件下的拉格朗日函数的极值问题，然后又因为其满足Slater条件，我们可以转化成强对偶问题。

在最大间隔分类中，我们得到如下结论：

其拉格朗日函数为：

其对偶问题（满足强对偶性）为：

然后我们来求：

上式对于\((\omega,b)\)属于无约束优化问题，令偏导为零可得：

代入\(公式(12)\)消去\((\omega,b)\)可得：

因此问题变成了寻找合适的\(\alpha\)使得\(公式(12)\)成立。

又因为\(公式（11）\)在极值点必定满足KKT条件。也就是说\(\alpha_i(1-y_{i}({w}^{\top} {x}_{i}+b))=0\)，当\(\alpha_i \gt 0\)时必有\(1-y_{i}({w}^{\top} {x}_{i}+b) =0\)。因此对于\(\alpha_i \gt0\)对应的样本是支持向量，对于非支持向量，则\(\alpha_i =0\)

对于\(公式13\)有：

然后我们可以求\(b\)了，对于支持向量有\(y_k =\omega^{\top}x+b\)，因此：

通过上面的推导，我们能够知道支持向量机的\((\omega,b)\)仅由支持向量决定。实践中, 为了得到对 $b \(更稳健的估计, 通常使用对所有支持向量求解得到\)b$的平均值。

综上，我们想计算出合适的\(\omega\)和\(b\)，就必须计算出\(\alpha_i\)，然后我们就可以得到支持向量，在然后我们我们通过支持向量和\(\alpha_i\)就可以计算出\(\omega\)和\(b\)。

至于怎么求\(\alpha_i\)，我们使用可以使用后面介绍的SMO算法求解，首先我们来介绍一下核方法。

核技巧

在前面的讨论中，我们对样本的考虑都是线性可分的。但是实际上，大部分的情况下，数据都是非线性可分的。比如说异或问题。在前面的章节神经网络中，我们是通过使用增加一层隐层来解决这个问题，那么对于SVM我们应该怎么解决呢？SVM中使用核技巧（kernel trick）来解决非线性问题。

既然在原始的特征空间\(\mathbb{R}^{d}\)不是线性可分的，支持向量机希望通过一个映射\(\phi: \mathbb{R}^{d} \rightarrow \mathbb{R}^{\tilde{d}}\), 使得数据在新的空间\(\mathbb{R}^{\tilde{d}}\)是线性可分的。可以证明（但是我证明不出），当\(d\)有限时, 一定存在\(\tilde{d}\), 使得样本在空间$ \mathbb{R}^{\tilde{d}}$中线性可分。

核函数

令\(\phi(x)\)为\(x\)映射后的特征向量，因此划分的超平面可以表示为\(f(x)=\phi(x)+b\)。同时\(公式（11）\)可以改为：

然后\(公式14\)可以写成如下的形式：

求解\(公式15\)面临一个很大的问题，那就是\(\phi(\boldsymbol{x}_{i}^{\top})\)和\(\phi(\boldsymbol{x}_{j})\)很难计算（一般来说它们都是高维的甚至无穷维），首先需要计算特征在\(\mathbb{R}^{\tilde{d}}\)的映射，然后又要计算在他的内积，复杂度为$$\mathcal{O}(\tilde{d})$$。因此我们通过使用核技巧，将这两步并将复杂度降低到\(\mathbb{R}^{d}\)。即核技巧希望构造一个核函数\(\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)\)，使得：

实际上核函数不仅仅只用于SVM，对于所有涉及到向量内积的运算，我们都可以使用核函数来解决。

因此\(公式15\)可以改写成：

对于核函数来说，我们可以自己造，但是通常我们会从一些常见的核函数中进行选择：根据不同问题选择不同的参数。下图是是一些常见的核函数。

软间隔

前面我们讨论的情况都是超平面都是能够完美的将数据进行分开（即使是非线性数据，我们使用核函数进行骚操作然后进行分割），这种所有样本都满足约束的情况称之为硬间隔（hard margin），但实际上数据是有噪音的，如果使用核函数进行骚操作，然后在找到一个线性可分超平面，可能就会造成模型过拟合，同样也可能我们找不到合适的核函数。因此，我们将标准放宽，允许一定的“错误”，称之为软间隔（soft margin）：

我们希望在优化间隔的同时，允许错误样本的出现，但是我们同样希望出现错误的样本越少越好。因此优化目标\(公式（5）\)可写成：

其中\(C \gt 0\)是一个常数，\(\ell_{0 / 1}\)是“0/1损失函数”。

可以很简单的知道，\(C\)取无穷大时，\(公式（16）\)迫使所有样本均满足约束。当\(C\)取有限值时，允许一些样本不满足约束。but，还是有些问题，\(\ell_{0 / 1}\)是非凸，非连续的一个函数，会使得上式\((16)\)变得不好求解，因此人们通常使用其他的函数来替代\(\ell_{0 / 1}\)，称之为“替代损失(surrogate loss)”。下面是几种常用的替代损失函数：

对应的图如下：

下面将以\(hinge函数\)为例子介绍软间隔支持向量机的推导。

软间隔支持向量机推导

\(\text {hinge函数}：\ell_{\text {hinge}}(z)=\max (0,1-z)\)等价于：

\(\xi_{i}\)我们称之为松弛变量（slack variable），样本违背约束越远，则松弛变量值越大。因此优化目标式\((5)\)可以写成：

同样在这里\(C\)越大，代表我们希望越多的样本满足约束。软间隔的拉格朗日函数为：

其KKT条件为：

其对偶问题为：

\(\min _{\boldsymbol{w}, b, \boldsymbol{\xi}} \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta})\)的优化属于无约束的优化问题，我们通过将偏导置零的方法得到\((\boldsymbol{w}, b, \boldsymbol{\xi})\)的最优值：

因为\(\beta_{i}=C -\alpha_{i} \ge0\)，因此我们约束\(0 \le \alpha_i \le C\)，将\(\beta_{i}=C -\alpha_{i},{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)\)，代入式\((18)\)可得：

如果我们将式\((17)\)看成如下一般形式：

对于\(\Omega(f)\)我们称之为“结构风险（structural risk）”，第二项\(\sum_{i=1}^{m} \ell\left(f\left(\boldsymbol{x}_{i}\right), y_{i}\right)\)称之为“经验分享（empirical risk）“，而\(C\)的作用就是对两者进行折中。

SMO算法

前面说了这么多，终于终于，我们要开始说SMO（Sequential minimal optimization，序列最小化）算法了。首先说一下这个算法的目的，这个算法就是用来求\(\alpha_i\)的。SMO算法是一种启发式算法，基本思路是如果所有变量的解都满足最优化问题的KKT条件，则该最优化问题的解就得到了。

对于式\((19)\)如果我们将\(\phi({x}_{i})^{\top} {\phi}(\boldsymbol{x}_{j})\)使用核函数来表示则有：

假如我们选择\(\alpha_1,\alpha_2\)作为变量(至于为什么不是只选择一个变量是因为存在\(\sum_{i=1}^{N} \alpha_{i} y_{i}=0\)这个约束条件)，固定其他变量\(\alpha_{i}(i=3,4, \cdots, N)\)，则式\((20)\)问题可以变成：

在式\((21)\)中省略了\(\sum_{i=3}^N\alpha_i\)这个式子，是因为该式为常数项。

因为\(\alpha_{1} y_{1}+\alpha_{2} y_{2} = 常数，y_1 = \pm1,y_2=\pm1\)，因此有：

我们可以将式\((22)\)用图表示出来：

因为\(\alpha_1\)和\(\alpha_2\)存在线性关系，这样两个变量的最优化问题成为了实质上单变量的最优化问题，因此，我们可以看成其为变量\(\alpha_2\)的最优化问题。

设\(式(22)\)的初始可行解为\(\alpha_{1}^{\text {old }}, \alpha_{2}^{\text {old }}\)，最优解为\(\alpha_{1}^{\text {new }}, \alpha_{2}^{\text {new}}\)。对于\(\alpha_i^{new}\)来说，其取值范围必须满足：

• 情况1：\(L=\max \left(0, \alpha_{2}^{\text {old }}-\alpha_{1}^{\text {old }}\right), \quad H=\min \left(C, C+\alpha_{2}^{\text {old }}-\alpha_{1}^{\text {old }}\right)\)
• 情况2：\(L=\max \left(0, \alpha_{2}^{\text {old }}+\alpha_{1}^{\text {old }}-C\right), \quad H=\min \left(C, \alpha_{2}^{\text {old }}+\alpha_{1}^{\text {old }}\right)\)

设我们计算出来的\(\alpha_2\)为\(\alpha_2^{new,unc}\)，则有：

那么问题就回到了如果我们有\(\alpha_2^{old}\)我们如何得到\(\alpha_2^{new,unc}\)呢？

首先我们设一个超平面函数\(g(x)\)如下：

然后我们令

同时引进记号：

因此式\((22)\)可以改写成：

又因为\(\alpha_{1} y_{1}+\alpha_{2} y_{2}=\varsigma,\quad y_iy_i = 1\)，因此\(\alpha_1\)可以表示为：

代入式\((24)\)中，我们有：

然后，我们对\(\alpha_2\)求导数：

令其导数为0可得：

又因为\(\varsigma=\alpha_{1}^{\mathrm{old}} y_{1}+\alpha_{2}^{\mathrm{old}} y_{2}\)代入式\((25)\)可得：

令：

因此式\((26)\)可化简为：

同时有：

因为我们已经得到\(\alpha_2^{new}\)，根据\(\alpha_1^{new}\)和\(\alpha_2^{new}\)之间的线性关系，我们可以就可以得到\(\alpha_1^{new}\)了。

我们每次完成两个变量的优化之后，都需要重新更新阈值。具体更新可以看下面部分。

SMO变量的选择方法

通过前面部分我们知道SMO算法就是选择两个变量进行优化，其中至少有一个变量是违反了KKT条件（假如没有违反的话，我们也就没必要进行计算了）。我们可以使用\(\alpha_1\)代表第一个变量，\(\alpha_2\)代表第二个变量。

1. 第一个变量的选择

   我们称第一个变量的选择为外层循环，外层循环在训练样本中选择违反KKT条件最严重的样本点。对于KKT条件，我们可以转成以下的形式：

   \[\begin{equation}\begin{aligned}
   \alpha_{i} &=0 \Leftrightarrow y_{i} g\left(x_{i}\right) \geqslant 1 &\quad(1)\\
   0<\alpha_{i} &<C \Leftrightarrow y_{i} g\left(x_{i}\right)=1 &\quad(2)\\
   \alpha_{i} &=C \Leftrightarrow y_{i} g\left(x_{i}\right) \leqslant 1 &\quad(3)\\
   其中g(x_{i}) &= \sum_{j=1}^{N}\alpha_{j}y_{j}K(x_{i},x_{j})+b\\
   \end{aligned}\end{equation} \tag{28}
   \]

   证明如下：

   对于上式\((1)\)：

   \[\begin{equation}\begin{aligned}
   &\because\alpha_i = 0,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\
   &\therefore \beta_i = C,\therefore\xi_i = 0\\
   又&\because 由KTT条件可知：1-\xi_i\le y_ig(x_i)，\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\
   &\therefore y_ig(x_i) \ge 1
   \end{aligned}\end{equation}
   \]

   对于上式\((2)\)：

   \[\begin{equation}\begin{aligned}
   &\because0<\alpha_{i} <C ,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\
   &\therefore 0 \lt\beta_i \lt C,\therefore\xi_i = 0\\
   又&\because 由KTT条件可知：1-\xi_i\le y_ig(x_i)，\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\
   &\therefore y_ig(x_i) = 1-\xi_i = 1
   \end{aligned}\end{equation}
   \]

   对于上式\((3)\)：

   \[\begin{equation}\begin{aligned}
   &\because\alpha_i = C,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\
   &\therefore \beta_i = 0，\xi_i \ge0\\
   又&\because 由KTT条件可知：1-\xi_i\le y_ig(x_i)，\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\
   &\therefore y_ig(x_i) = 1-\xi_i \le 1
   \end{aligned}\end{equation}
   \]

   当然我们也可以给定一定的精度范围\(\varepsilon\)，此时KKT条件就变成了：

   \[\begin{equation}\begin{array}{l}
   a_{i}=0 \Leftrightarrow y_{i} g\left(x_{i}\right) \geq 1-\varepsilon \\
   0<a_{i}<C \Leftrightarrow 1-\varepsilon \leq y_{i} g\left(x_{i}\right) \leq 1+\varepsilon \\
   a_{i}=C \Leftrightarrow y_{i} g\left(x_{i}\right) \leq 1+\varepsilon
   \end{array}\end{equation}
   \]

   然后我们通过变形后的KKT条件，获得违背的样本点违背最严重的作为第一个变量就