开发者学堂课程【机器学习算法 ：求解 SVM 分类超平面】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/535/detail/7267
求解 SVM 分类超平面
内容介绍
一、解决间隔优化问题
二、SMO 算法
三、求解超平面
一、解决间隔优化问题
回到 SVM 本质问题，如何通过求极值的方式找到最优分类超平面。
优化问题转换为求解下列有约束的目标函数即带有不等式约束条件的目标函数求极值：
按照第二章所学，将有约束的目标函数转换为无约束的拉格朗日函数，然后固定μ，要让 L（ω，γ，μ）对 ω，γ 最小化，即对 ω，γ 求偏导，令其等于0。
将 ω 的值带入：
此时，拉格朗日函数只包含了一个变量 μ，求出 μ 即可求出 ω，γ
求μ，则需要求系列不等式约束的极大值，即：
但是由于问题并没有简单化，反而更复杂，又需要在不等式约束条件下求极值，这个时候需要二次规划问题，可以使用通用的二次规划算法来求解但是问题规模正比于训练样本数，开销很大。通常会采用序列最小优化算法(Sequential Minimal Optimization ，SMO)解决。
二、SMO 算法
SMO 是一种启发式算法，其基本思想是，如果所有分量的解都满足KKT条件，那么这组解就是最优解。如果不满足，选择两个分量，固定其他分量，针对这两个分量构建一个二次凸规划问题，然后关于这个二次规划的问题的解就更接近原始的二次规划的解。SMO 的高效主要是将多个参数的求优化问题转化为固定其他参数后仅优化两个参数的问题。
固定除 μi 和 μj 以外的参数，求解带不等式约束的函数极值，得到更新后的 μi 和 μj 固定变量后，不等式约束条件为：
实际上最终需要求的是这个式子，可以得到 μ 的值
三、求解超平面
通过 SMO 算法求得 μ 后，即可得到超平面的表达函数：
有了分类超平面的表达式，在做分类的时候就很简单，如果有一个点，需要判断他是哪一类，将点带到表达式中即可求得 F（x）的值就可以知道点的归属分类。
将需要判断分类的点 x 和训练样本计算内积，得到 f(x) 的值，判断点 x 的归属分类。因为只有当训练样本为支持向量的时候，μi 才不为0，所以实际计算量并不大。
