SMO算法(比较好的讲解)
转载请注明出处：http://blog.****.net/luoshixian099/article/details/51227754
本文力求简化SMO的算法思想，毕竟自己理解有限，无奈还是要拿一堆公式推来推去，但是静下心看完本篇并随手推导，你会迎刃而解的。推荐参看SMO原文中的伪代码。
1.SMO概念
上一篇博客已经详细介绍了SVM原理，为了方便求解，把原始最优化问题转化成了其对偶问题，因为对偶问题是一个凸二次规划问题，这样的凸二次规划问题具有全局最优解，如下：
其中表示训练样本数据，为样本特征,为样本标签，C为惩罚系数由自己设定。上述问题是要求解N个参数，其他参数均为已知，有多种算法可以对上述问题求解，但是算法复杂度均很大。但1998年，由Platt提出的序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解2个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。
2.SMO原理分析
2.1视为一个二元函数
为了求解N个参数，首先想到的是坐标上升的思路，例如求解,可以固定其他N-1个参数，可以看成关于的一元函数求解，但是注意到上述问题的等式约束条件,当固定其他参数时，参数也被固定，因此此种方法不可用。
SMO算法选择同时优化两个参数，固定其他N-2个参数，假设选择的变量为,固定其他参数,由于参数的固定，可以简化目标函数为只关于的二元函数，表示常数项(不包含变量的项)。
2.2视为一元函数
由等式约束得：，可见为定值。
等式两边同时乘以且，得
2.3对一元函数求极值点
上式中是关于变量的函数，对上式求导并令其为0得：
1.由上式中假设求得了的解，带回到(2)式中可求得的解，分别记为,优化前的解记为;由于参数固定，由等式约束有
2.假设SVM超平面的模型为,上一篇中已推导出的表达式,将其带入得表示样本的预测值,表示样本的真实值，定义表示预测值与真实值之差为
3.由于，因此
把(4)(6)(7)带入下式中：
化简得: 此时求解出的未考虑约束问题，先记为：
带入(5)式，并记得：
2.4对原始解修剪
上述求出的解未考虑到约束条件：
在二维平面上直观表达上述两个约束条件
最优解必须要在方框内且在直线上取得，因此;
当时，
当时，
经过上述约束的修剪，最优解就可以记为了。
2.5求解
由于其他N-2个变量固定，因此所以可求得
2.6取临界情况
大部分情况下，有。但是在如下几种情况下，需要取临界值L或者H.
- ,当核函数K不满足Mercer定理时，矩阵K非正定；
- ,样本与输入特征相同；
也可以如下理解，对(3)式求二阶导数就是,
当时，目标函数为凸函数，没有极小值，极值在定义域边界处取得。
当时，目标函数为单调函数，同样在边界处取极值。
计算方法：
即当和分别带入(9)式中，计算出和,其中
带入目标函数(1)内，比较与的大小，取较小的函数值对应的边界点。
其中
3.启发式选择变量
上述分析是在从N个变量中已经选出两个变量进行优化的方法，下面分析如何高效地选择两个变量进行优化，使得目标函数下降的最快。
第一个变量的选择
第一个变量的选择称为外循环，首先遍历整个样本集，选择违反KKT条件的作为第一个变量，接着依据相关规则选择第二个变量(见下面分析),对这两个变量采用上述方法进行优化。当遍历完整个样本集后，遍历非边界样本集()中违反KKT的作为第一个变量，同样依据相关规则选择第二个变量，对此两个变量进行优化。当遍历完非边界样本集后，再次回到遍历整个样本集中寻找，即在整个样本集与非边界样本集上来回切换，寻找违反KKT条件的作为第一个变量。直到遍历整个样本集后，没有违反KKT条件，然后退出。
边界上的样本对应的，在优化过程中很难变化，然而非边界样本会随着对其他变量的优化会有大的变化。
第二个变量的选择
SMO称第二个变量的选择过程为内循环，假设在外循环中找个第一个变量记为，第二个变量的选择希望能使有较大的变化，由于是依赖于,当为正时，那么选择最小的作为,如果为负，选择最大作为，通常为每个样本的保存在一个列表中，选择最大的来近似最大化步长。
有时按照上述的启发式选择第二个变量，不能够使得函数值有足够的下降，这时按下述步骤:
首先在非边界集上选择能够使函数值足够下降的样本作为第二个变量，
如果非边界集上没有，则在整个样本集上选择第二个变量，
如果整个样本集依然不存在，则重新选择第一个变量。
4.阈值b的计算
每完成对两个变量的优化后，要对b的值进行更新，因为b的值关系到f(x)的计算，即关系到下次优化时的计算。
1.如果，由KKT条件,得到,由此得：
由(5)式得，上式前两项可以替换为：
得出：
2.如果，则
3.如果同时满足,则
4.如果同时不满足，则以及它们之间的数都满足KKT阈值条件，这时选择它们的中点。（关于这个我不理解…）
建议参看SMO原文的伪代码
参考：
统计学习方法，李航
Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines，John C. Platt
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
本文转载自：http://blog.****.net/luoshixian099/article/details/51227754
个人理解：注意，每次更新的只有三个变量：αi,Ei(实际上是ui,即当前模型的预测值,因为每个样本点的真实值是不会改变的),b.
更新的变量里没有w,因为计算过程中不需要w的参与,我们并不需要计算出w再来计算每个样本点的预测值，因为从w的计算公式可以看出来，只需计算那些支持向量与样本点的内积即可，之所以这样做，而不是计算出w，再计算每个样本点的预测值，是因为引入核函数之后，就不需要，也很难计算w的值了，w对应的将是一个高维向量，计算起来相当麻烦，而且我们用到w的地方全都可以用低维空间的内积和核函数来代替，所以不更新w。
转载请注明出处：http://blog.****.net/luoshixian099/article/details/51227754
本文力求简化SMO的算法思想，毕竟自己理解有限，无奈还是要拿一堆公式推来推去，但是静下心看完本篇并随手推导，你会迎刃而解的。推荐参看SMO原文中的伪代码。
1.SMO概念
上一篇博客已经详细介绍了SVM原理，为了方便求解，把原始最优化问题转化成了其对偶问题，因为对偶问题是一个凸二次规划问题，这样的凸二次规划问题具有全局最优解，如下：
其中表示训练样本数据，为样本特征,为样本标签，C为惩罚系数由自己设定。上述问题是要求解N个参数，其他参数均为已知，有多种算法可以对上述问题求解，但是算法复杂度均很大。但1998年，由Platt提出的序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解2个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。
2.SMO原理分析
2.1视为一个二元函数
为了求解N个参数，首先想到的是坐标上升的思路，例如求解,可以固定其他N-1个参数，可以看成关于的一元函数求解，但是注意到上述问题的等式约束条件,当固定其他参数时，参数也被固定，因此此种方法不可用。
SMO算法选择同时优化两个参数，固定其他N-2个参数，假设选择的变量为,固定其他参数,由于参数的固定，可以简化目标函数为只关于的二元函数，表示常数项(不包含变量的项)。
2.2视为一元函数
由等式约束得：，可见为定值。
等式两边同时乘以且，得
2.3对一元函数求极值点
上式中是关于变量的函数，对上式求导并令其为0得：
1.由上式中假设求得了的解，带回到(2)式中可求得的解，分别记为,优化前的解记为;由于参数固定，由等式约束有
2.假设SVM超平面的模型为,上一篇中已推导出的表达式,将其带入得表示样本的预测值,表示样本的真实值，定义表示预测值与真实值之差为
3.由于，因此
把(4)(6)(7)带入下式中：
化简得: 此时求解出的未考虑约束问题，先记为：
带入(5)式，并记得：
2.4对原始解修剪
上述求出的解未考虑到约束条件：
在二维平面上直观表达上述两个约束条件
最优解必须要在方框内且在直线上取得，因此;
当时，
当时，
经过上述约束的修剪，最优解就可以记为了。
2.5求解
由于其他N-2个变量固定，因此所以可求得
2.6取临界情况
大部分情况下，有。但是在如下几种情况下，需要取临界值L或者H.
- ,当核函数K不满足Mercer定理时，矩阵K非正定；
- ,样本与输入特征相同；
也可以如下理解，对(3)式求二阶导数就是,
当时，目标函数为凸函数，没有极小值，极值在定义域边界处取得。
当时，目标函数为单调函数，同样在边界处取极值。
计算方法：
即当和分别带入(9)式中，计算出和,其中
带入目标函数(1)内，比较与的大小，取较小的函数值对应的边界点。
其中
3.启发式选择变量
上述分析是在从N个变量中已经选出两个变量进行优化的方法，下面分析如何高效地选择两个变量进行优化，使得目标函数下降的最快。
第一个变量的选择
第一个变量的选择称为外循环，首先遍历整个样本集，选择违反KKT条件的作为第一个变量，接着依据相关规则选择第二个变量(见下面分析),对这两个变量采用上述方法进行优化。当遍历完整个样本集后，遍历非边界样本集()中违反KKT的作为第一个变量，同样依据相关规则选择第二个变量，对此两个变量进行优化。当遍历完非边界样本集后，再次回到遍历整个样本集中寻找，即在整个样本集与非边界样本集上来回切换，寻找违反KKT条件的作为第一个变量。直到遍历整个样本集后，没有违反KKT条件，然后退出。
边界上的样本对应的，在优化过程中很难变化，然而非边界样本会随着对其他变量的优化会有大的变化。
第二个变量的选择
SMO称第二个变量的选择过程为内循环，假设在外循环中找个第一个变量记为，第二个变量的选择希望能使有较大的变化，由于是依赖于,当为正时，那么选择最小的作为,如果为负，选择最大作为，通常为每个样本的保存在一个列表中，选择最大的来近似最大化步长。
有时按照上述的启发式选择第二个变量，不能够使得函数值有足够的下降，这时按下述步骤:
首先在非边界集上选择能够使函数值足够下降的样本作为第二个变量，
如果非边界集上没有，则在整个样本集上选择第二个变量，
如果整个样本集依然不存在，则重新选择第一个变量。
4.阈值b的计算
每完成对两个变量的优化后，要对b的值进行更新，因为b的值关系到f(x)的计算，即关系到下次优化时的计算。
1.如果，由KKT条件,得到,由此得：
由(5)式得，上式前两项可以替换为：
得出：
2.如果，则
3.如果同时满足,则
4.如果同时不满足，则以及它们之间的数都满足KKT阈值条件，这时选择它们的中点。（关于这个我不理解…）
建议参看SMO原文的伪代码
参考：
统计学习方法，李航
Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines，John C. Platt
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
本文转载自：http://blog.****.net/luoshixian099/article/details/51227754
个人理解：注意，每次更新的只有三个变量：αi,Ei(实际上是ui,即当前模型的预测值,因为每个样本点的真实值是不会改变的),b.
更新的变量里没有w,因为计算过程中不需要w的参与,我们并不需要计算出w再来计算每个样本点的预测值，因为从w的计算公式可以看出来，只需计算那些支持向量与样本点的内积即可，之所以这样做，而不是计算出w，再计算每个样本点的预测值，是因为引入核函数之后，就不需要，也很难计算w的值了，w对应的将是一个高维向量，计算起来相当麻烦，而且我们用到w的地方全都可以用低维空间的内积和核函数来代替，所以不更新w。