【菜菜的sklearn课堂笔记】支持向量机-线性SVM用于分类的原理

视频作者：菜菜TsaiTsai 链接：【技术干货】菜菜的机器学习sklearn【全85集】Python进阶_哔哩哔哩_bilibili

本节要注意一下决策边界和决策边际的概念。以上一节的二维数据为例，决策边界是个超平面，二维里就是条线，而决策边际是两个虚线超平面的最短距离

线性SVM的损失函数详解

要理解SVM的损失函数，我们先来定义决策边界。假设现在数据总计有$N$个训练样本，每个训练样本$i$可以被表示为$(x_{i},y_{i})(i=1,2,\cdots,N)$，其中$x_{i}$是$(x_{1i},x_{2i},\cdots ,x_{ni})^{T}$这样的一个特征向量，每个样本总共含有$n$个特征。二分类标签$y_{i}$的取值是$(-1,1)$

如果$n$等于$2$，则有$i=(x_{1i},x_{2i},\cdots ,y_{i})^{T}$，分别由我们的特征向量和标签组成。此时我们可以在二维平面上，以$x_{2}$为横坐标，$x_{1}$为纵坐标，$y$为颜色，来可视化我们所有的$N$个样本

这里$n$是指数据的维度

我们让所有紫色点的标签为1，红色的标签为-1。我们要在这个数据集上寻找一个决策边界，在二维平面上，决策边界（超平面）就是一条直线。二维平面上的任意一条线可以被表示为 $$ x_{1}=ax_{2}+b $$ 我们将此表达式变换一下： $$ \begin{aligned} 0&=ax_{2}-x_{1}+b\ 0&=\begin{pmatrix}a & -1\end{pmatrix}\cdot \begin{pmatrix}x_{2} \ x_{1}\end{pmatrix}+b\ 0&=\omega^{T}x+b \end{aligned} $$ 其中$\begin{pmatrix}a & -1\end{pmatrix}$就是参数向量$\omega$，$x$就是特征向量，$b$就是截距 在一组数据下，给定固定的$\omega$和$b$，这个式子就可以是一条固定直线，在$\omega$和$b$不确定的状况下，这个表达式$\omega^{T}x+b=0$就可以代表平面上的任意一条直线。在SVM中，我们就使用这个表达式来表示我们的决策边界，我们的目标是求解能够让边际最大化的决策边界，所以我们要求解参数向量$\omega$和截距$b$ 如果在决策边界上任意取两个点$x_{a},x_{b}$，并代入决策边界的表达式，则有 $$ \begin{aligned} \omega^{T}x_{a}+b&=0\ \omega^{T}x_{b}+b&=0 \end{aligned} $$ 将两式相减，可以得到 $$ \omega^{T}\cdot (x_{a}-x_{b})=0 $$ 上式可以认为$\omega$和$x_{a}-x_{b}$垂直。$x_{a}$与$x_{b}$是一条直线上的两个点，相减后得到的向量方向是由$x_{b}$指向$x_{a}$，所以$x_{a}-x_{b}$的方向是平行于他们所在的直线，即决策边界的。而$\omega$和$x_{a}-x_{b}$相互垂直，所以参数向量$\omega$的方向必然是垂直我们的决策边界

注意$\omega$只能说垂直于$x_{a}-x_{b}$，实际上，例如本图，$\omega$可以朝上，也可以朝下，并且$\omega$的模长到此也没有规定，$\begin{aligned} \frac{\omega}{2}, -\omega\end{aligned}$只要是与$\omega$方向相同或相反的向量我们都可以认为是$\omega$，因为这些向量并不违反我们的假设 需要注意的是，如果我们改变$\omega$为$-\omega$，那么对应的，$b$也要变为$-b$，使整个决策边界不变

此时，我们有决策边界。任意一个紫色的点$x_{p}$就可以被表示为： $$ \omega \cdot x_{p}+b=p $$ 由于紫色的点所代表的标签$y$是$1$，所以我们规定，$p>0$。同样的，对于人一个红色的点$x_{r}$而言，我们可以将它表示为 $$ \omega \cdot x_{r}+b=r $$ 由于红色点所代表的标签$y$是$-1$，所以我们规定，$r<0$。由此，如果我们有新的测试数据$x_{t}$，则$x_{t}$的标签就可以根据以下式子来判定 $$ y=\left{\begin{aligned}&1&if \quad \omega \cdot x_{t}+b>0\&-1& if \quad \omega \cdot x_{t}+b<0\end{aligned}\right. $$

核心误区：p和r的符号 注意，在这里，p和r的符号是我们人为规定的。在一些博客或教材中，会认为p和r的符号是由原本的决策边界上下移动得到。这是一种误解。 如果k和k'是由原本的决策边界平移得到的话，紫色的点在决策边界上方，$\omega \cdot x+b=0$应该要向上平移，直线向上平移的话是增加截距，也就是说应该写作$\omega \cdot x+b+一个正数=0$，那p在等号右边，就应该是一个小于0的数。向下平移同理，r应该是一个大于0的数。所以p和r的符号，不完全是平移的结果 有人说，“直线以上的点带入直线为正，直线以下的点带入直线为负”是直线的性质，这又是另一种误解。假设直线$y=x$，我们取点$(x,y)=(0,1)$，带入后为+1，如果我们将直线表达式写作$x-y=0$，则代入$(0,1)$后结果为-1。所以，一个点在直线的上方，究竟会返回什么样的符号，是跟直线的表达式的写法有关的，不是直线上的点都为正，直线下的点都为负。 我们规定了p和e的符号与标签的符号一致，所以有人会说，p和r的符号，由所代表的点的标签的符号决定。这不是完全错误的，但这种说法无法解释，为什么我们就可以这样规定。并且，标签可以不是{-1,1}，可以是{0, 1}，可以是{1,2}，两个标签之间并不需要是彼此的负数，标签的取值其实也是我们规定的。 实际上p和r的符号规定如下

紫色的点$x_{p}$是在决策边界的上方的，此时我将决策边界向上移动，形成一条过$x_{p}$的直线。根据我们平移的规则，直线向上平移，是在截距后加一个正数，则等号的右边是一个负数，假设这个数等于-3，则有： $$ \begin{aligned} \begin{pmatrix}a & -1\end{pmatrix}\cdot \begin{pmatrix}x_{2} \ x_{1}\end{pmatrix}+b&=-1\ 两边同时乘以-1&\ \begin{pmatrix}-a & 1\end{pmatrix}\begin{pmatrix}x_{2} \ x_{1}\end{pmatrix}+(-b)&=3\ \omega \cdot x+b&=3 \end{aligned} $$ 可以注意到，我们的参数向量由$(a,-1)$变成了$(-a,1)$，$b$变成了$-b$，但参数向量依旧可以被表示成$\omega$，只是它是原来的负数了，截距依旧可以被表示成$b$，只是如果它原来是正，它现在就是负数了，如果它原本就是负数，那它现在就是正数了。在这个调整中，我们通过将向上平移时产生的负号放入了参数向量和截距当中，这不影响我们求解，只不过我们求解出的参数向量和截距的符号变化了，但决策边界本身没有变化。所以我们依然可以使用原来的字母来表示这些更新后的参数向量和截距。通过这种方法，我们让$\omega \cdot x+b=p$中的p大于0。我们让p大于0的目的，是为了它的符号能够与我们的标签的符号一致，都是为了后续计算和推导的简便。

重点理解决策边界本身没有发生变化

为了推导和计算的简便，我们规定： 标签是{-1,1} 决策边界以上的点，标签都为正，并且通过调整$\omega$和$b$的符号，让这个点在$\omega \cdot x+b$上得出的结果为正。 决策边界以下的点，标签都为负，并且通过调整$\omega$和$b$的符号，让这个点在$\omega \cdot x+b$上得出的结果为负。 结论：决策边界以上的点都为正，以下的点都为负，是我们为了计算简便，而人为规定的。这种规定，不会影响对参数向量$\omega$和截距$b$的求解。

有了这个理解，剩下的推导就简单多了。我们之前说过，决策边界的两边要有两个超平面，这两个超平面在二维空间中就是两条平行线（就是我们的虚线超平面），而他们之间的距离就是我们的决策边际 。而决策边界位于这两条线的中间，所以这两条平行线必然是对称的。我们另这两条平行线被表示为： $$ \omega \cdot x+b=k \quad \omega \cdot x+b=-k $$ 两个表达式同时除以k，则可以得到 $$ \omega \cdot x+b=1 \quad \omega \cdot x+b=-1 $$

这就是我们平行于决策边界的两条线的表达式，表达式两边的1和-1分别表示了两条平行于决策边界的虚线到决策边界的相对距离。此时，我们可以让这两条线分别过两类数据中距离我们的决策边界最近的点，这些点就被称为“支持向量”，而决策边界永远在这两条线的中间，所以可以被调整。我们令紫色类的支持向量为$x_{p}$，红色类的支持向量为$x_{r}$，则我们可以得到： $$ \omega \cdot x_{p}+b=1 \quad \omega \cdot x_{r}+b=-1 $$ 两个式子相减，则有 $$ \omega \cdot (x_{p}-x_{r})=2 $$ 如上图所示，$x_{p}-x_{r}$可表示为两点之间的连线，二我们的边际d是平行于$\omega$的，所以我们现在，相当于是得到了三角形中的斜边，并且知道一条直角边的方向，所以，我们令上述式子两边同时除以$||\omega||$，则 $$ \begin{aligned} \frac{\omega \cdot (x_{p}-x_{r})}{||\omega||}&=\frac{2}{||\omega||}\ \frac{\omega}{||\omega||}(x_{p}-x_{r})&=\frac{2}{||\omega||}\ d&=\frac{2}{||\omega||} \end{aligned} $$

向量a乘以向量b方向上的单位向量，可以得到向量a在向量b方向上的投影的长度

大边界所对应的决策边界，那问题就简单了，要最大化$d$，就求解$\omega$的最小值，极值问题可以相互转化，我们可以把求解$\omega$的最小值转化为，求解以下函数的最小值： $$ f(\omega)=\frac{||\omega||^{2}}{2} $$ 只所以要在模长上加上平方，是因为模长的本质是一个距离，所以它是一个带根号的存在，我们对它取平方，是为了消除根号 我们的两条虚线表示的超平面，是数据边缘所在的点，所以对于任意样本$i$，我们可以把决策函数写作 $$ \begin{aligned} \omega \cdot x_{i}+b \geq 1 &\quad if \quad y_{i}=1\ \omega \cdot x_{i}+b \leq -1&\quad if \quad y_{i}=-1 \end{aligned} $$

个人理解，决策函数，就是求最值的时候，参数要满足的条件

整理一下，我们可以把两个式子整合成： $$ y_{i}(\omega \cdot x_{i}+b)\geq 1,i=1,2,\cdots,N $$ 在一部分教材中，这个式子被称为“函数间隔”。将函数间隔作为条件附加到我们的$f(\omega)$上，我们就得到了SVM的损失函数最初形态： $$ \left{\begin{aligned}&\mathop{\text{min }}\limits_{\omega,b} \frac{||\omega||^{2}}{2}\ & y_{i}(\omega \cdot x+b)\geq 1,i=1,2,\cdots,N\end{aligned}\right. $$ 到这里，我们就完成了对SVM第一层理解的第一部分：线性SVM做二分类的损失函数。

函数间隔与几何间隔

这只是另一种理解方法在许多教材中，推导损失函数的过程与我们现在所说的不同。许多教材会先定义如下概念来辅助讲解 对于给定的数据集$T$和超平面$(\omega,b)$，定义超平面$(\omega,b)$关于样本点$(x_{i},y_{i})$的函数间隔为 $$\gamma_{i}=y_{i}(\omega \cdot x_{i}+b)$$ 这其实是我们的虚线超平面的表达式整理过后的式子。函数间隔可以表示分类预测的正确性以及确信度。在这个函数间隔的基础上除以$\omega$的模长$||\omega||$来得到几何间隔 $$\gamma_{i}=y_{i}\left(\frac{\omega}{||\omega||} x_{i}+ \frac{b}{||\omega||}\right)$$ 几何间隔的本质其实是点$x_{i}$到超平面$(\omega,b)$，即到我们决策边界的带符号的距离

对于几何间隔，支持向量带进去$\gamma_{i}=k$，正确分类的点带进去对应的$\gamma_{i}>0$，虚线超平面之外分类正确的样本集$\gamma_{i}>k$

为什么几何间隔能够表示点到决策边界的距离？如果理解点到直线的距离公式，就可以很简单地理解这个式子。对于平面上的一个点$(x_{0},y_{0})$和一条直线$ax+by+c=0$，我们可以推导出点到直线的距离为： $$distance = \frac{|ax_{0}+by_{0}+c|}{\sqrt{a^{2}+b^{2}}}$$ 其中$(a,b)$就是直线的参数向量$\omega$，而$\sqrt{a^{2}+b^{2}}$其实就是参数向量$\omega$的模长$||\omega||$。而我们的几何间隔中，$y_{i}$的取值是$\left{-1,1\right}$，所以并不影响整个表达式的大小，只影响方向。而$\omega x+b=0$是决策边界，所以直线带入$x_{i}$后再除以参数向量的模长，就可以得到点$x_{i}$到决策边界的距离

线性SVM的拉格朗日对偶函数和决策函数

我们之前得到了线性SVM损失函数的最初形态： $$ \left{\begin{aligned}&\mathop{\text{min }}\limits_{\omega,b} \frac{||\omega||^{2}}{2}\ & y_{i}(\omega \cdot x+b)\geq 1,i=1,2,\cdots,N\end{aligned}\right. $$ 这个损失函数分为两部分：需要最小化的函数，以及参数求解后必须满足的约束条件。因此这是一个最优化问题。

将损失函数从最初形态转换为拉格朗日乘数形态

为什么要进行转换？

我们的目标是求解让损失函数最小化的$\omega$，但其实很容易看得出来，如果$||\omega||$为0，$f(\omega)$必然最小了。但是，$||\omega||=0$其实是一个无效的值。因为，首先，我们的决策边界是$\omega \cdot x+b=0$，如果$\omega$为0，这这个向量里包含的所有元素都为0，那就有$b=0$这个唯一值。然而，如果$b$和$\omega$都为0，决策边界就不再是一条直线了，函数间隔$y_{i}(\omega \cdot x_{i}+b)$就会为0，条件中$y_{i}(\omega \cdot x_{i}+b)\geq 1$就不可能实现，所以$\omega$不可以是一个0向量。可见，单纯让$\begin{aligned} f(\omega)=\frac{||\omega||^{2}}{2}\end{aligned}$为0，是不能求出合理的$\omega$的，我们希望能够找出一种方式，能够让我们的条件$y_{i}(\omega \cdot x_{i}+b)\geq 1$在计算中也被纳入考虑，一种业界认可的方法是使用拉格朗日乘数法

为什么可以进行转换？

我们的损失函数是二次的(quadratic)，并且我们损失函数中的约束条件在参数$\omega$和$b$下是线性的，求解这样的损失函数被称为“凸优化问题”(convex optimization problem)。拉格朗日乘数法正好可以用来解决凸优化问题，这种方法也是业界常用的，用来解决带约束条件，尤其是带有不等式的约束条件的函数的数学方法。首先第一步，我们需要使用拉格朗日乘数来将损失函数改写为考虑了约束条件的形式： $$ L(\omega,b,\alpha)=\frac{1}{2}||\omega||^{2}- \sum\limits_{i=1}^{N}\alpha_{i}(y_{i}(\omega \cdot x_{i}+b)-1)\quad (\alpha_{i}\geq 0) $$ 其中$\alpha_{i}$叫做拉格朗日乘数。此时此刻，我们要求解的就不只有参数向量$\omega$和截距$b$了，我们也要求解拉格朗日乘数$\alpha$，而我们的$x_{i}$和$y_{i}$都是我们已知的特征矩阵和标签。

怎样进行转换？

拉格朗日函数也分为两部分。第一部分和我们原始的损失函数一样，第二部分呈现了我们带有不等式的约束条件。我们希望，$L(x,\alpha)$不仅能由代表我们原有的损失函数$f(\omega)$和约束条件，还能够我们想要最小化损失函数来求解$x$的意图，所以我们要先以$\alpha$为参数，求解$L(x,\alpha)$的最大值，再以$x$为参数，求解$L(x,\alpha)$的最小值，因此我们的目标可以写作 $$ \mathop{\text{min }}\limits_{x}\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L(x,\alpha)\quad (\alpha_{i}\geq 0) $$

这里的$x$对于SVM来说就是$\omega$和$b$

这里引用一下白板推导里面的证明

简单来说，引入拉格朗日乘子是为了强制要求所有的约束条件必须被满足，当$x$违反约束条件时，$L(x,\alpha,\beta) \rightarrow +\infty$， 当$x$满足约束条件时，$L(x,\alpha,\beta) = f(x)$。

假设$f(x)，c_i(x)，h_j(x)$是定义在$R^n$上的连续可微函数。考虑约束最优化问题（极大化问题可以简单地转换为极小化问题，这里仅讨论极小化问题）： $$\begin{aligned} \min_{x \in R^n} \hspace{1em} & f(x)\ s.t. \hspace{1em} & m_i(x) \le 0, \hspace{1em} i=1,2,\cdots,k\ & n_j(x) = 0, \hspace{1em} j=1,2,\cdots,l \end{aligned}$$ 引入拉格朗日乘子后，得到拉格朗日函数 $$L(x,\alpha,\beta) = f(x) + \sum_{i=1}^{k} \alpha_{i} c_{i} (x) + \sum_{j=1}^{l} \beta_{j} h_{j} (x),\alpha_{i} \geq 0,\beta_{i} \in \mathbb{R}$$ 如果$x$违反$m_{i}(x)$约束，即$m_{i}(x)>0$，那么$\mathop{\text{max }}\limits_{\lambda}L \to +\infty$ 如果$x$符合$m_{i}(x)$约束，即$m_{i}(x)\leq 0$，那么$\mathop{\text{max }}\limits_{\lambda}L \ne +\infty$ 因此有 $$ \mathop{\text{min }}\limits_{x}\mathop{\text{max }}\limits_{\lambda}L=\mathop{\text{min }}\limits_{x}\left{\underbrace{\max L}{符合约束},\underbrace{+\infty}{违反约束}\right}=\mathop{\text{min }}\limits_{x}\mathop{\text{max }}\limits_{\lambda}L $$ 如果$x$违反$n_{j}(x)$约束，即$n_{j}(x)\ne 0$，那么$\mathop{\text{max }}\limits_{\beta}L \to +\infty$ 如果$x$符合$n_{j}(x)$约束，即$n_{j}(x)=0$，那么$\mathop{\text{max }}\limits_{\beta}L \ne +\infty$ 因此有 $$ \mathop{\text{min }}\limits_{x}\mathop{\text{max }}\limits_{\lambda}L=\mathop{\text{min }}\limits_{x}\left{\max L,+\infty\right}=\mathop{\text{min }}\limits_{x}\mathop{\text{max }}\limits_{\lambda}L $$

若把函数$L(x,\alpha,\beta)$带有拉格朗日乘子的部分当作一个惩罚项来看待，当符合约束的时候没有受到惩罚（因为此时拉格朗日乘子为0或约束项为0，惩罚项消失），当不符合约束的时候受到了极致的惩罚（拉格朗日乘子趋于无穷，惩罚项趋于$+\infty$），即加上了一个正无穷项，函数整体永远不可能取到最小值。因此就事项了约束条件同时被满足，对于本题，新的损失函数可以被定义为 $$ \mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L(\omega,b,\alpha)\quad (\alpha_{i}\geq 0) $$

将拉格朗日函数转换为拉格朗日对偶函数

为什么要进行转换

要求极值，最简单的方法还是对参数求导后让一阶导数等于0。我们先来试试看对拉格朗日函数求极值，在这里我们对参数向量$\omega$和截距$b$分别求偏导并且让他们等于0。这个求导过程比较简单： $$ \begin{aligned} L(\omega,b,\alpha)&=\frac{1}{2}||\omega||^{2}-\sum\limits_{i=1}^{N}\alpha_{i}(y_{i}(\omega \cdot x_{i}+b)-1)\ &这里跳步了,需要的话可以看白板推导的\ &=\frac{1}{2}\omega^{T}\omega-\sum\limits_{i=1}^{N}(\alpha_{i}y_{i}\omega \cdot x_{i})-\sum\limits_{i=1}^{N}\alpha_{i}y_{i}b+\sum\limits_{i=1}^{N}\alpha_{i} \end{aligned} $$ 对于$\omega$ $$ \begin{aligned} \frac{\partial L(\omega,b,\alpha)}{\partial \omega}&=\frac{1}{2}\cdot 2 \omega-\sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}\ &=\omega-\sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}\ 0&=\omega-\sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}\ \omega&=\sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i} \end{aligned} $$ 对于$b$ $$ \begin{aligned} \frac{\partial L(\omega,b,\alpha)}{\partial b}&=\sum\limits_{i=1}^{N}\alpha_{i}y_{i}\ 0&=\sum\limits_{i=1}^{N}\alpha_{i}y_{i} \end{aligned} $$ 由于两个求偏导结果中都带有位置的拉格朗日乘数$\alpha_{i}$，因此我们还是无法解出$\omega$和$b$，我们必须想出一种方法来求解拉格朗日乘数$\alpha_{i}$。运地是，拉格朗日函数可以被转换成一种只带有$\alpha_{i}$，而不带有$\omega$和$b$的形式，这种形式被称为拉格朗日对偶函数。在对偶函数下，我们就可以求解出拉格朗日乘数$\alpha_{i}$，然后带入到上面偏导为零推导出的两个式中来求解$\omega$和$b$。

这其实就是告诉我们，我们求出了偏导不能直接带进去，因为我们要求的是$\mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}}L$，我们要先求$\mathop{\text{max }}\limits_{\alpha_{i}}L$，但能带进去的前提是函数是对于$\omega$和$b$，即出现$\mathop{\text{min }}\limits_{\omega,b}L$。也就是说如果想要带进去，那应该是$\mathop{\text{max }}\limits_{\alpha}\mathop{\text{min }}\limits_{\omega,b}L$，而这个形式就是下面我们要介绍的对偶形式

这样看其实白板推导这里顺序可能有点问题，偏导得到的$\omega$和$b$不能直接代入，因为证明了函数满足KKT条件才有对偶函数=原函数

为什么能够进行转换？

对于任何一个拉格朗日函数$L(x,\alpha)=f(x)+\sum\limits_{i=1}^{N}\alpha_{i}h(x)$，都存在一个与它对应的对偶函数$g(\alpha)$，只带有拉格朗日乘数$\alpha$作为唯一的参数。

这里拉格朗日函数的最优解就是$\mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}}L$，对偶函数的最优解就是$\mathop{\text{max }}\limits_{\alpha}\mathop{\text{min }}\limits_{\omega,b}L$ 正是因为对偶函数的形式中是先计算$\mathop{\text{min }}\limits_{\omega,b}L$，因此我们可以把对$L$求$\omega$和$b$的偏导带进去，因此就成为了只含$\alpha$的函数

如果$L(x,\alpha)$的最优解存在并可以表示为$\mathop{\text{min }}\limits_{x}L(x,\alpha)$，并且对偶函数的最优解也存在，并可以表示为$\mathop{\text{max }}\limits_{\alpha}g(\alpha)$，则我们可以定义对偶差异，即拉格朗日函数的最优解与其对偶函数的最优解之间的差值 $$ \Delta =\mathop{\text{min }}\limits_{x}L(x,\alpha)-\mathop{\text{max }}\limits_{\alpha}g(\alpha) $$ 如果$\Delta =0$，则称$L(x,\alpha)$与其对偶函数之间存在强对偶关系(strong duality property)，此时我们就可以通过求解其对偶函数的最优解来替代求解原始函数的最优解。那强对偶关系什么时候存在呢？则这个拉格朗日函数必须满足KKT(Karush-Kuhn-Tucker)条件： $$ \begin{aligned} \frac{\partial L}{\partial x_{i}}&=0,\forall_{i}=1,2,\cdots ,d\ h_{i}(x)&\leq 0,\forall_{i}=1,2,\cdots,N\ \alpha_{i}&\geq 0,\forall_{i}=1,2,\cdots,N\ \alpha_{i}h_{i}(x)&=0,\forall_{i}=1,2,\cdots,N \end{aligned} $$ 这里的条件其实都比较好理解。首先是所有参数的一阶导数必须为0，然后约束条件中的函数本身需要小于等于0，拉格朗日乘数需要大于等于0，以及约束条件乘以拉格朗日乘数必须等于0，即不同$i$的取值下，两者之中至少有一个为0。 当所有限制都被满足，则拉格朗日函数$L(x,\alpha)$的最优解与其对偶函数的最优解相等，我们就可以将原始的最优化问题转换成为对偶函数的最优化问题。 而不难注意到，对于我们的损失函数$L(\omega,b,\alpha)$而言，KKT条件都是可以操作的。如果我们能够人为让KKT条件全部成立，我们就可以求解出$L(\omega,b,\alpha)$的对偶函数来解出$\alpha$ 之前我们已经让拉格朗日函数上对参数$\omega$和$b$的求导为0，得到了式子： $$ \begin{aligned} \sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}&=\omega\ \sum\limits_{i=1}^{N}\alpha_{i}y_{i}&=0 \end{aligned} $$ 并且在我们的函数中，我们通过先求解最大值再求解最小值的方法使得函数天然满足： $$ \begin{aligned} -(y_{i}(\omega \cdot x_{i}+b)-1)&\leq 0\ \alpha_{i}&\geq 0 \end{aligned} $$ 所以接下来，我们只需要再满足一个条件： $$ \alpha_{i}(y_{i}(\omega \cdot x_{i}+b)-1)=0 $$ 这个条件很容易满足，能够让$y_{i}(\omega \cdot x_{i}+b)-1=0$的就是落在虚线超平面上的样本点，即我们的支持向量，所有不是支持向量的样本点则必须满足$\alpha_{i}=0$

个人理解，这个条件也就是说明在取值符合条件的时候，惩罚项不起作用 同时，我们说到了不是支持向量的样本点则必须满足$\alpha_{i}=0$，因此我们求解参数$\omega$和$b$以及求解超平面的存在，只与支持向量相关，与其他样本点都无关

现在KKT的五个条件都得到了满足，我们就可以使用$L(\omega,b,\alpha)$的对偶函数来求解$\alpha$了

怎样进行转换？

首先让拉格朗日函数对参数$\omega$和$b$求导后的结果为0，本质是探索拉格朗日函数的最小值。然后将偏导的结果代入$L(\omega,b,\alpha)$，这里我们直接写结果，需要的可以看白板推导系列笔记

上面阐述过了为什么能代入，因为此时我们求解的是$\mathop{\text{max }}\limits_{\alpha_{i}}\mathop{\text{min }}\limits_{\omega,b}L(\omega,b,\alpha)$，先求的$\mathop{\text{min }}\limits_{\omega,b}L(\omega,b,\alpha)$，这里不再赘述

$$ \begin{aligned} L_{d}=\sum\limits_{i=1}^{N}\alpha_{i}- \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N} \alpha_{i}\alpha_{j}y_{i}y_{j}x_{i} \cdot x_{j} \end{aligned} $$ 函数$L_{d}$就是我们的对偶函数。对所有存在对偶函数的拉格朗日函数我们有对偶差异如下表示： $$ \Delta =\mathop{\text{min }}\limits_{x}L(x,\alpha)-\mathop{\text{max }}\limits_{\alpha}g(\alpha) $$ 则对于我们的$L(\omega,b,\alpha)$和$L_{d}$，我们则有 $$ \Delta =\mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L(\omega,b,\alpha)-\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L_{d} $$ 我们推导$L_{d}$的第一步就是对$L(\omega,b,\alpha)$求偏导并让偏导数都为0，所以我们求解对偶函数的过程其实是在求解$L(\omega,b,\alpha)$的最小值，所以我们又可以把公式写成： $$ \begin{gather} \Delta = \mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L(\omega,b,\alpha)-\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}\mathop{\text{min }}\limits_{\omega,b}L(\omega,b,\alpha)\ 由于满足KKT条件\ \mathop{\text{min }}\limits_{\omega,b}\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}L(\omega,b,\alpha)=\mathop{\text{max }}\limits_{\alpha_{i}\geq 0}\mathop{\text{min }}\limits_{\omega,b}L(\omega,b,\alpha) \end{gather} $$ 这就是众多博客和教材上写的，对偶函数与原始函数的转化过程的由来。如此，我们只需要求解对偶函数的最大值，就可以求出$\alpha$了。最终，我们的目标函数变化为： $$ \mathop{\text{max }}\limits_{\alpha_{i}\geq 0}\left(\sum\limits_{i=1}^{N}\alpha_{i}- \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i} \cdot x_{j}\right) $$

求解拉格朗日对偶函数极其后续过程

到了这一步，我们就需要使用梯度下降，SMO或者二次规划(QP，quadratic programming)来求解我们的 ，数学的难度又进一步上升。考虑到这一过程对数学的要求已经远远超出了我们需要的程度，更是远远超出我们在使用sklearn时需要掌握的程度，如何求解对偶函数中的$\alpha$在这里就不做讲解了。 但大家需要知道，一旦我们求得了$\alpha$值，我们就可以使用求导后得到的式子求解$\omega$，并可以使用$\omega$的表达式和决策边界的表达式结合，得到下面的式子来求解 ： $$ \sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}\cdot x+b=0 $$ 当我们求得特征向量$\omega$和$b$，我们就得到了我们的决策边界的表达式，也就可以利用决策边界和其有关的超平面来进行分类了，我们的决策函数就可以被写作 $$ f(x_{test})=sign(\omega \cdot x_{test}+b)=sign \left(\sum\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}\cdot x_{test}+b\right) $$ 其中$x_{test}$是任意测试样本，$sign(h)$是$h>0$时返回$1$，$h<0$时返回$-1$的符号函数 到这里，我们可以说我们完成了对SVM的第二层理解的大部分内容，我们了解了线性SVM的四种相关函数：损失函数的初始形态，拉格朗日函数，拉格朗日对偶函数以及最后的决策函数。熟练掌握以上的推导过程，对理解支持向量机会有极大的助益，也是对我们数学能力的一种完善。