（ 保证能看晕系列）SVM系列（三）hard-margin 求解实例 + SMO算法 详细原理

本节主要解决怎么算拉格朗日系数的问题，和大多数的SMO算法的介绍不同的是，每一步都有详细的过程和说明。希望能对你有一定的理解上的帮助。进入本节之前，确保你已经看懂了以下内容：

SVM系列（一）hard-margin SVM 详细原理  https://blog.****.net/Lee_Yu_Rui/article/details/107420870

SVM系列（二）soft-margin SVM 详细原理以及一点点的kernel SVM https://blog.****.net/Lee_Yu_Rui/article/details/107436175

hard-margin 求解实例

到目前为止，三种SVM的原理都已经阐述明白。可能你发现，好像还没有算出来呢？先以一个简单的低维度数据为例看一下整个的求解过程，

                                                         

                                                           s.t.         and                                           

总结KKT条件，在整个过程中的限制条件：按照（11）可得

                                                         , , , 

                                                         

                                                         

                                                                                                                                    

求出满足KKT条件的u，然后就可以得到w,b,若存在（xk,yk）满足

                                                          

                                                                                                              

则最终的分类决策函数

                                                                                                             

题就是，求下图的最大间隔分离超平面，求解过程下面都给了，最后要计算b的地方简单提一下，就是将在直线中的点带入即可，任何一个都行，就是u不等于零的哪一个都可以

最后的结果是右边的红色和黄色部分，与我们最开始的直观看见的直线方程一致

SMO 算法

通过以上实例，我们已经看到了利用拉格朗日推导得到的SVM的可行性，但是实例中的数据太简单了，就两个特征，一眼都能看出来，但是现实中，这种问题不会存在，我们会处理具有超多特征数量的数据集，那这时候就没有办法用刚刚的方法了。所以就提出来了一种SMO算法，两篇SVM之后终于到了这个（保证能看晕的系列了）有条件的请拿出你正经的草纸，一起推导把...我尽量让你能坚持到最后，其实一点都不难，一点也不难........

（1）基本思想

将N 个参数的二次规划问题，拆成多个子二次规划问题，在每个子二次规划问题中只优化两个参数，剩余N-2个参数固定，然后不断迭代指导最终的目标函数满足条件。

（2）待求问题

如果这里就懵圈了，建议退回“SVM系列（一）hard-margin SVM 详细原理”和“SVM系列（二）soft-margin SVM 详细原理以及一点点的kernel SVM”，以下过程假设你们（一）和（二）都会

                                                      

                                                         s.t.         and                                              (1)

总结KKT条件，在整个过程中的限制条件:

                                               , ,

                                              , 

                                                     ,

                                                      ，

                                                      ,                                                                 (2)

其中：                                                             

                                                      

                                                       

（3）得到关于和的目标函数

（4）消去，只保留

（5）求令目标值最小时候的

（6）考虑约束条件下的和

（7）b,w,E的更新

关于坑1的填土方案 

关于这个式子形式就不写了，直接网上找来了一个

 参数的启发式选择

最后一部分就是 这两个u选啥，当然你可以随便选，然后重复迭代。也可以选择最有影响的u，所以参数的选择原则就是：先”找到“不满足KKT条件的都给它“快速”干掉，注意这里说的找到和干掉，这里第一步找到的外层循环就是为了“找到”，第二步的u1就是为了把u2快速干掉，使其满足KKT

最终使得目标函数有足够的下降，如果没成功，那就只能遍历数据集合了，以非边界的集合为先，不行再找所有样本集，再不行就只能换u2了

希望看你看到了这里，针对每一步都给了详细的过程和具体的推导，over