机器学习之手把手实现，第 1 部分 支持向量机的原理和实现-2

look_w

最优化问题求解到此为止，已经将目标函数和约束条件转换成了极大极小化拉格朗日函数的问题了。首先求解关于拉格朗日函数的极小化问题。
对三个变量分别求偏导得：
将以上三式带入拉格朗日函数中得：
那么极大极小化拉格朗日函数转换成：
为求解方便，将极大转换成极小得：
核函数对于线性不可分问题，如图 2 所示，这类问题是无法用超平面划分正负样本数据的。倘若能将超平面换成超曲面，则可以将正负样本正确分类，如图 5 所示。
图 5. 超曲面分离正负样本我们知道曲面的公式是：
映射到新坐标如下：
可将超曲面在新坐标下表示成超平面：
也就是将在二维空间(x1,x2)下线性不可分的问题转换成了在五维空间(z1,z2,z3,z4,z5)下线性可分的问题。
得映射后新坐标下的内积：
有一核函数如下：
可知
何为核函数？核函数在低维空间中完成了映射到高维空间后的内积运算。这点非常有用，利用核函数，无需先将变量一一映射到高维空间再计算内积，而是简单得在低维空间中利用核函数完成这一操作。为什么说不用一一映射到高维空间很有用呢？原因就在于首先我们无法针对每种情况提供精确的映射函数，再者对于需要映射到无穷维的情况显然无法一一映射完成。
那么为什么是映射到高维后的内积运算呢？这是因为在上节中我们得到了如下目标函数：
正是因为该目标函数中包含自变量的内积运算，而映射到高维空间后的内积运算又恰好可以通过核函数在低维空间中直接求得，故而有了核函数的由来。较常用的核函数是高斯核，高斯核可以将低维空间映射到无穷维。
运用核函数后，最优化问题的目标函数和约束条件变为：
序列最小优化        (Sequential minimal optimization)到目前为止，优化问题已经转化成了一个包含 N 个 alpha 自变量的目标变量和两个约束条件。由于目标变量中自变量 alpha 有 N 个，为了便与求解，每次选出一对自变量        alpha，然后求目标函数关于其中一个 alpha 的偏导，这样就可以得到这一对 alpha 的新值。给这一对 alpha 赋上新值，然后不断重复选出下一对 alpha        并执行上述操作，直到达到最大迭代数或没有任何自变量 alpha 再发生变化为止，这就是 SMO 的基本思想。说直白些，SMO 就是在约束条件下对目标函数的优化求解算法。
为何不能每次只选一个自变量进行优化？那是因为只选一个自变量 alpha 的话，会违反第一个约束条件，即所有 alpha 和 y 值乘积的和等于 0。
下面是详细的 SMO 过程。假设选出了两个自变量分别是 alpha1 和 alpha2，除了这两个自变量之外的其他自变量保持固定，则目标变量和约束条件转化为：
将约束条件中的 alpha1 用 alpha2 表示，并代入目标函数中，则将目标函数转化成只包含 alpha2 的目标函数，让该目标函数对 alpha2 的偏导等于 0：
可求得 alpha2 未经修剪的值：
之所以说 alpha2 是未经修剪的值是因为所有 alpha 都必须满足大于等于 0 且小于等于 C 的约束条件，用此约束条件将 alpha2 进行修剪，修剪过程如下：
由此得：
分两种情况讨论：
情况 1.当 y1 等于 y2 时，有：
情况 2.当 y1 不等于 y2 时，有：
修剪后，可得 alpha2 的取值如下：
由 alpha2 和 alpha1 的关系，可得：
在完成 alpha1 和 alpha2 的一轮更新后，需要同时更新 b 的值，当 alpha1 更新后的值满足 0<alpha1<C 时，由 KKT 条件得：
由于篇幅有限，在此就不把推导过程一一列举，可得：
同样的道理，当 alpha2 更新后的值满足 0<alpha1<C 时可得：
若更新后的 alpha1 和 alpha2 同时满足大于 0 且小于 C 的条件，那么 b 就等于 b1 等于 b2;否则，b 取 b1 和 b2 的中点。
那么问题来了，如何选择 alpha1 和 alpha2 呢？
选择违背下列 KKT 条件推导结果的 alpha 作为 alpha1：
为了让每次变化尽可能大，alpha2 的选择满足如下式子最大，即步长最大化：
其中 E 是上面提到过的预测值和真实值差值的绝对值，也就是误差值。
按上述方法不断选择一对 alpha 并更新，直到达到最大迭代次数或所有 alpha 都不再变化，则停止迭代。有朋友就会问，求出 alpha 之后呢？如何判断新样本数据属于 1        还是-1 呢？
别忘了，在最优化求解一节，我们得到了如下：
若 f(x)大于 0，则新样本数据属于 1；否则，新样本数据属于-1。
可以见得，求出 alpha 后，所有问题都迎刃而解了。