【十分钟 机器学习 系列课程】 讲义（52）:非线性支持向量机 序列最小最优化SMO算法（二）

欢迎回来。上期我们开启了介绍「序列最小最优化SMO算法」的新篇章，【十分钟 机器学习 系列课程】 讲义（51）:非线性支持向量机 序列最小最优化SMO算法（一）用一句话以概之，就是在「坐标下降法」的基础上，固定 个 值，经过一系列的简化，从而「在无约束」情况下，得到新迭代出的 与上一结果 之间的函数表达式。

当然，上期的公式超级多，以至于，公号第一次竟然识别不出了，所以大家看到好多是图片的形式。

可是，我们的优化问题中是存在约束条件的，那么这期，当然就是要「考虑约束条件啦」，这样得到的才是优化问题真正的解。

有了它，就能继续得到剩余 的迭代值，从而实现迭代的过程，能够最终找到所有参数的最优解。

先来复习一下约束条件有哪些：

❝

❞

接下来，就来看看考虑约束条件后，迭代后真正的 值。不妨将上一期得到的 记作未剪辑的参数，注意哦，这里的unc代表un cut。

壹 SMO算法中的迭代

1.考虑约束条件后的

注意哦，因为这里固定了 个 因此约束条件只对 和 有效，那么可以写成：

❝

❞

观察一下这三个条件： 条件(1)，是一条直线；条件(2)和(3)可以看出是一个线性约束，表示一个正方形，横轴代表 ，纵轴代表 。

接着，咱们就可以分情况讨论啦：

当  时

说明 或者 代入到第1个条件中，

对应的可以写成：

令 ，就是

各位可以看出，这时 和 之间的斜率就是 ，截距项为 。看来，这个约束条件就是一条 的动线，比如这样的：

当 时

意味着， 或者是 ，这样，对应的可以写成：

令 ，就是

对应的斜率就变成了 ，约束条件就是一条斜率为 ，截距项为 的动线，比如视频中这样

总结一下，就是下面的两条动线。

2.找到剪辑后的最优解

接下来，我们就该找到在这三个条件下的最优解，我们把考虑约束的过程称为「剪辑」，那么就有「未经剪辑」和「剪辑之后」。

❝

现在，请大家明确我们的目标就是，在三个条件下找到  的最优解。

❞

那么，我们分两种情况讨论一下，一种是同类的   ，一种是不同类的 。

当 时，从上面的推导，我们知道此时的约束条件就是：

❝

• 条件一
• 条件二
• 条件三

❞

那么我们不妨就画一下这三个条件，大家看，对于条件一而言， 这条动线和由条件二三组成的正方形产生的交点该怎么表示呢？

我们可以定义「左端的」交点为「P点」，「右端的」交点为「Q点」。 简单来看：

❝

对于「P点」而言，可以分别交于红线上。

对于「Q点」而言，可以分别交于蓝线上。

❞

我们考虑以下两种情况：

「第一种情况」： 斜率为-1的“1号”绿色直线，当约束在正方形内的时候，直线上约束内的是 线段， 点坐标为 ， 点坐标为 。

「第二种情况」： 斜率为-1的“2号”绿色直线在正方形的对角线右上角，当约束在正方形内的时候，约束内的是 线段， 点坐标为 ， 点坐标为 。

因为是交集，我们要取上面两种情况下 的约束区间，怎么找呢？

Step1 先找「约束区间的上界」

我们将其记为 (取 的首字母)，肯定得在 点中找，为什么呢？

❝

因为大家要始终把注意力集中在 上，它的最大值，肯定就是 的纵坐标为 时。

❞

对于 “1号直线” 而言，  动线和 轴的「交点P」的纵坐标都在 的范围内，而对于 “2号直线”，此时 点的纵坐标，会落在正方形外面，很明显此时 点的纵坐标是超过 的，这时，「就不满足 的约束条件了」。

那么，咱们一眼就能看出来，对于2号直线而言，此时P的纵坐标就得固定在 了，但是计算机却看不出来，「那就得用一些约束条件来实现这个目的了」！

于是取 点中 的最小值来满足约束，意味着对于2号直线 而言，此时P点的坐标为 ，而为了满足约束条件，我们要将它的纵坐标 和边界最大值 中取最小值：

那么 最大值，也就是：

即，

Step 2 再找到「约束区间的下界」

我们将其记为 (取 的首字母)，肯定得在 点中找，这时其实就在看 点的横坐标，同理，一种是“1号直线”中的，在 的范围内，另一种是“2号直线”， 点的横坐标在 以外，同理，我们也是一眼能看出，对于这种情况， 的横坐标就卡在 了，而怎么让计算机自己判断呢？

❝

很简单，和上面一样的思路，我们最终是要得到   的最小值。

❞

意味着对于2号直线 而言，此时Q点的坐标为 ，而为了满足约束条件，当它的横坐标多出 时，我们要取 ，说明对于纵轴 的最小值而言，代入曲线后，正是从1号直线中的 和 中取最大值，而这决定了 下界，也就是：

即，

当 时

类似地，当 时，下界可以写成：

当 时，上界 ，那么写成：

通过以上分析，这下就可以将 剪辑之前和剪辑之后的结果简要总结出来啦：

❝

「未经剪辑」

「剪辑之后」

❞

有小伙伴纳闷，刚才给出的 和 有两种表达式啊，用哪个？

这就不用担心啦，因为样本 和 我们是已知的，所以直接看 和 是不是同类就好啦。

贰 SMO算法的含义

1.权重参数和截距参数

搞清楚了考虑约束条件后的 和 的表达式，以此类推能求解出其余的 的值，然后设置收敛条件，就能求出 的最优解，接着代入到非线性支持向量机（或线性支持向量机）的分类函数中，就能求出最终的权重参数 :

把符合

从而得到最终的支持向量机的「决策函数」：

2.每次迭代需要计算什么

当然看完上面的思路，相信你已经明白了大致的思路，但是其实还有些细节值得我们关注。 比如经过第一轮更新后，从 变为 ，我们需要计算哪些值呢？我们分情况讨论一下。

若 则 属于支持向量

既然 是支持向量，那么就可以代入去更新 了。注意哦，这里表示根据第1个样本点更新的 ，不妨记为 ：

其中 应该代入的是：

整理一下:

仔细观察可以发现，后面两部分会在每次迭代时发生多次的重复计算，那么就无形中增加了工作量，怎么对这种情况进行优化呢？

那么大家还记得上期的 ，它代表了预测结果与观测结果之差。

也就是：

因为此处的求和式，是从 开始的，那么继续改成：

将 放入 的表达式中：

这样每次算一下迭代更新前后的 、 ，还有旧的 和 就行啦。

若 则 属于支持向量

同理，就可以知道：

假如说都满足条件呢？

若 则 都属于支持向量

很简单，此时这两个样本点都可以来更新参数：

若 可能是 或

那么可以平均得出截距项：

再说回 ，我们可以用刚才更新的参数进行更新，

其中 是所有支持向量的集合（S为Support 的首字母）。

好啦，这样我们就得到了非线性支持向量机的算法思路，并且根据SMO算法得出了优化问题的求解过程，那么下一期就说一说「如何选出更新的两个变量 和 」 能够让迭代更快更好，感兴趣的小伙伴也可以到B站点击视频继续学习，我们下期不见不散~