拉格朗日对偶问题与支持向量机学习笔记(2)

2023-02-27 15:42 作者:ZJU前校长-吴朝晖院士 0人读过 | 我要投稿

本部分主要讲解线性可分的SVM的思想与推导过程，以及非线性可分的情况下的SVM处理方法。

关于本部分使用的拉格朗日对偶模型，可以参考另一篇文章“拉格朗日对偶问题与支持向量机学习笔记(1)”。

本文参考了“https://blog.csdn.net/weixin_44378835/article/details/110732412?utm_source%20=%20app”这篇博文和其他一些博文，进行了一定的缩减，在部分地方添加了自己的想法和更详细的推导过程。

2 支持向量机（SVM）

2.1 SVM的基本思想

当我们对线性可分的两个类别进行二分类时，往往可以得到无穷多个符合条件的超平面。我们希望从中选出“最好”的一个超平面，而评价好坏的标准就是“分类间隔”，也就是在不改变分类结果的前提下超平面可以进行平移的范围，也就是下图中的 $d$ 。显然，分类间隔应当越大越好，因为我们不能排除样本偏差带来的影响；分类间隔越大，未被我们采样的潜在区域中的样本被错误分类的概率越小。

值得注意的是，分类间隔的大小取决于那些离决策边界最近的点。因此，为了找到最合适的决策边界，我们只需要关注少数距离边界近的点，而这些少数点就是“支持向量”；这是有很大好处的，因为在样本点很多的时候这可以大大减少计算量。

基于上述讨论，我们希望最大化决策边界与支持向量之间的距离。

记支持向量 $x_s$ 与判别函数 $G(x)%3Dw%5ETx%2Bw_0$ 距离为 $r$ ，则 $r%3D%20%5Cfrac%20%7B%7CG(x_s)%7C%7D%20%7B%7C%7Cw%7C%7C%7D%EF%BC%8Cd%3D2r%3D%5Cfrac%20%7B2%7CG(x_s)%7C%7D%20%7B%7C%7Cw%7C%7C%7D$ 。要最大化 $d$ ，可以固定 $%7CG(x_s)%7C$ 求最小的 $%7C%7Cw%7C%7C$ ，也可以固定 $%7C%7Cw%7C%7C$ 求最大的 $%7CG(x)%7C$ 。支持向量机算法选择固定 $%7CG(x)%7C$ 求最小的 $%7C%7Cw%7C%7C$ 。

由于 $%7C%7Cw%7C%7C$ 本身不方便求最小值，转而求 $%7B%5Cfrac%201%202%7C%7Cw%7C%7C%5E2%7D$ 的最小值（显然 $%7B%5Cfrac%201%202%7C%7Cw%7C%7C%5E2%7D$ 随着 $%7C%7Cw%7C%7C$ 单调递增，且 $%7B%7C%7Cw%7C%7C%5E2%7D$ 可以写成 $%7Bw%5ETw%7D$ 这种向量内积的形式，相对而言更好求最小值；此外，由于之后要用到KKT条件， $%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D$ 求导后直接变 $w$ ，所以乘 $%5Cfrac%201%202$ ）

根据设定（固定 $%7CG(x_s)%7C$ 求最小的 $%7C%7Cw%7C%7C$ ），令 $%7CG(x_s)%7C%3D1$ ，则所有的样本点的判别函数的绝对值都满足 $%7CG(x)%7C%20%5Cgeq%201$ 。使用指示变量 $sgn(%C2%B7)$ 来指示 $G(x)$ 的符号： $G(x)$ 为正时 $sgn(G(x))$ 等于1， $G(x)$ 为负时 $sgn(G(x))$ 等于-1。

综上，建立如下优化模型来表示SVM算法(样本点共l个)：

$%5Cdisplaystyle%7Bmin%20%5Cquad%20%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D%5C%5C%20s.t.%20%5Cquad%20sgn(G(x%5E%7B(1)%7D))(w%5ETx%5E%7B(1)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%20%5Cquad%20sgn(G(x%5E%7B(2)%7D))(w%5ETx%5E%7B(2)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%20...%5C%5C%20%5Cquad%20sgn(G(x%5E%7B(l)%7D))(w%5ETx%5E%7B(l)%7D%2Bw_0)%20%5Cgeq%201%5C%5C%7D$

根据内积的定义， $%5Cfrac%201%202%7B%7C%7Cw%7C%7C%5E2%7D$ 是一个凸函数，因此上述优化问题是一个凸优化问题。回顾上文中提到的KKT条件，这个优化问题的 strong duality成立（d* = p*)。基于上述考虑，我们接下来只需建立此问题的对偶问题，并找出满足KKT条件的点，则满足条件的点就是本问题的最优解。

原问题的对偶问题为：

$max_%5Calpha%20min_%7Bw%EF%BC%8Cw_0%7DL(w%2Cw_0%2C%5Calpha)%20%3D%20%7B%5Cfrac%201%202%7Bw%5ETw%7D%7D%20-%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20%5Cbigg(sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)-1%20%5Cbigg)$

$L(w%2Cw_0%2C%5Calpha)$ 对 $w$ 求偏导： $%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%20%3D%20w%20-%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))x%5E%7B(i)%7D%3D0$

得到： $w%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))x%5E%7B(i)%7D%20%5Cquad%20%5Cquad(1)$

$L(w%2Cw_0%2C%5Calpha)$ 对 $w_0$ 求偏导： $%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w_0%7D%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0$

得到： $%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%20%5Cquad%20%5Cquad(2)$

将上述（1），（2）两个式子代入 $L(w%2Cw_0%2C%5Calpha)$ 的表达式，就可以求出 $min_%7Bw%2Cw_0%7DL(w%2Cw_0%2C%5Calpha)$ ，(推导略，这字实在太难打了)

$%7Bmin_%7Bw%2Cw_0%7DL(w%2Cw_0%2C%5Calpha)%20%3D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))x%5E%7B(i)T%7Dx%5E%7B(j)%7D%7D$

因此，对偶问题可以写成：

$max_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%7B%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))x%5E%7B(i)T%7Dx%5E%7B(j)%7D%20%5Cbigg)%5C%5C%20s.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%20%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

同时，由于 $L(w%2Cw_0%2C%5Calpha)$ 的最优解需要满足KKT条件，根据互补松弛性， $%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20%5Cbigg(sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)-1%20%5Cbigg)%3D0$ ，所以对于任意的 $i$ ，要么 $%5Calpha%5E%7B(i)%7D%3D0$ ，要么 $sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ ；当 $%5Calpha%5E%7B(i)%7D%3D0$ 时，根据（1）式，样本 $i$ 对最优的 $w$ 没有帮助；当 $sgn(G(x%5E%7B(i)%7D))(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ 时，样本 $i$ 的 $G(x%5E%7B(i)%7D)%3D(w%5ETx%5E%7B(i)%7D%2Bw_0)%3D1$ ，说明此样本 $i$ 就是支持向量。

由简化后的对偶模型求解出 $%5Calpha%5E%7B(i)%7D$ ，代入到式（1）中便获得了最优的 $w%3D%5Cdisplaystyle%5Csum%5E%7Bl_s%7D_%7Bs%3D1%7D%5Calpha%5E%7B(s)%7D%20sgn(G(x%5E%7B(s)%7D))x%5E%7B(s)%7D$ (仅依赖于支持向量)；再根据上面的方法找出支持向量，根据 $w%5ETx%5E%7B(s)%7D%2Bw_0%3D1$ 即可求出 $w_0$ 。

2.2 线性不可分时的 SVM

我们到目前为止讨论的都是线性可分的支持向量机。这个模型有解的一个前提条件是样本集是线性可分的。但实际上，很多问题的样本集并不是线性可分的，例如下面这样的样本集。

那么，我们要如何去处理这种情况呢？在具体探讨解决方案前，我们首先要明确一个问题，那就是造成样本集线性不可分的原因是什么。

实际上，有两种可能的原因会导致样本集线性不可分：

异常点带来的线性不可分：样本集的总体是线性可分的，但是由于抽样存在随机噪声，少数的异常样本点较大地偏离了总体，使得不存在一个超平面能够对两类样本进行分割。

问题本质上的线性不可分。在这种情况下，样本来自的总体就是线性不可分的，此时线性可分的SVM完全失效。

两种情况下，我们采取的补救措施也有所不同。

2.2.1 异常点带来的线性不可分——软间隔支持向量机

线性可分的支持向量机无法求解异常点带来的线性不可分，是因为它把距离分类间隔最近的点作为支持向量，从而异常点很可能会错误地被认为是支持向量，这导致了它无法容忍任何异常点。软间隔支持向量机的思想是通过引入松弛变量的方法，使得离群的异常点不会成为支持向量，从而在一定程度上容忍异常点。

具体的做法就是同时引入松弛变量 $%5Cxi%5E%7B(l_i)%7D%20%5Cgeq%200$ 和惩罚系数 $C%20%5Cgeq%200$ 。 $%5Cxi%5E%7B(l_i)%7D$ 的引入使得异常值点不会成为支持向量；但是 $%5Cxi%5E%7B(l_i)%7D$ 越大，则代价函数也越大，因为我们并不希望模型出现过多的离群点和错误分类。最理想的情况下，绝大多数支持向量外侧的样本(包括支持向量)，对应的松弛变量都应该是为0的。只有少数在支持向量内侧的异常点，才有一个尽可能小的松弛变量。

需要注意的是，惩罚系数 $C$ 是预先给定的，而松弛变量 $%5Cxi%5E%7B(l_i)%7D$ 则是通过优化获得的，因为我们在优化目标函数之前并不知道哪些样本点 $i$ 会成为离群点。

上述软间隔支持向量机优化问题的求解过程与线性支持向量机完全相同。最后得到的最优权向量，仍然由一组支持向量 $x%5E%7B(s)%7D$ 的线性组合所构成。

2.2.2 问题本质上的线性不可分——非线性支持向量机（核函数）

当需要分类的总体本就不是线性可分的时候，使用软间隔SVM也是无效的。

解决此类问题的方法是“广义线性化”。广义线性化就是将低维空间中的一个非线性分类问题往高维空间映射，从而转化为一个线性分类问题。例如下面这个一维空间中的非线性判别问题，通过映射到二维空间，就变成了一个线性判别问题。

假设存在这样一个从低维向高维的映射 $%5Cphi(%C2%B7)$ ，能够将低维的中线性不可分的样本 $x%5E%7B(i)%7D$ 映射为高维中线性可分的 $%5Cphi(x%5E%7B(i)%7D)$ 。注意到，尽管样本的判别函数也需要进行映射，但是因为样本的类别标签没有改变，所以判别函数的符号也没有改变。根据上文中的结论，我们只需求解如下模型中的 $%5Calpha$ 即可：

$%7Bmax_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)%20%5Cbigg)%5C%5Cs.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

然而，一方面，我们并不知道一个普适的方法来为所有的线性不可分总体寻找从低维向高维的映射 $%5Cphi(%C2%B7)$ ，我们甚至不知道 $%5Cphi(%C2%B7)$ 的维数应该是多少；另一方面，将低维特征映射到高维后模型计算量会指数型增长，带来计算上的困难。因此上述方法虽然看似很美好，但实际上是不可行的。但是，人们想出了一种方法，使得我们不用真的将所有向量从低维映射到高维，但仍能从一定程度上求解上述问题，这个方法就是核函数。

观察上面的这个优化目标，我们可以发现映射前与映射后的优化目标的唯一区别就在于将 $x%5E%7B(i)T%7Dx%5E%7B(j)%7D$ 变成了 $%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D$ 。也就是说，如果我们能够找到一个函数 $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)$ ，那么其实不用真的找到 $%5Cphi(%C2%B7)$ ，也不用真的进行映射，我们只要用 $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)$ 替换上式中的 $%5Cphi(x%5E%7B(i)%7D)%5ET%5Cphi(x%5E%7B(j)%7D)$ 并进行求解如下的优化问题，就能获得所需要的 $%5Calpha$ ：

$%7Bmax_%5Calpha%20%5Cbigg(%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20-%20%5Cfrac%7B1%7D%7B2%7D%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%20%5Cdisplaystyle%5Csum%5El_%7Bj%3D1%7D%5Calpha%5E%7B(i)%7D%5Calpha%5E%7B(j)%7Dsgn(G(x%5E%7B(i)%7D))sgn(G(x%5E%7B(j)%7D))K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%20%5Cbigg)%5C%5Cs.t.%20%5Cquad%20%5Cdisplaystyle%5Csum%5El_%7Bi%3D1%7D%5Calpha%5E%7B(i)%7D%20sgn(G(x%5E%7B(i)%7D))%3D0%5C%5C%5Calpha%5E%7B(i)%7D%20%5Cgeq%200%20%2C%20%5Cforall%20i%20%5Cin%20%5C%7B1%2C2%2C...%2Cl%5C%7D%7D$

尽管核函数与 $%5Cphi(%C2%B7)$ 一样，在实际上无论是形式还是参数都没有确定的选择方法，只能依靠经验进行尝试，但是核函数法仍然为我们带来了两个好处：

使用核函数并没有增加变量的维数，避免了由维数增加带来的求解困难。
相比于完全几乎完全没有规律的 $%5Cphi(%C2%B7)$ ，有几种特定形式的核函数被验证为是有效并且被广泛使用，便于我们进行尝试。

常用的核函数有以下这些：

线性核函数： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3Dx%5E%7B(i)T%7Dx%5E%7B(j)%7D$ ，形式简单，计算量小。
多项式核函数： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D(%5Cgamma%20x%5E%7B(i)T%7D%2B%5Czeta)%5EQ$ ，其中 $%5Cgamma%20%2C%5Czeta%2CQ$ 均可自由指定。其中γ对内积进行缩放，ζ进行加减上的调整，Q用于控制次数。
高斯核函数： $K(x%5E%7B(i)%7D%2Cx%5E%7B(j)%7D)%3D%5Cdisplaystyle%7Bexp(%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C2%7D%7B2%5Csigma%5E2%7D)%7D$
······