用讲故事的办法帮你理解 SMO 算法( 二 ) _SMO

现在，我选了一个分量，就叫它α1吧，这里的1表示它是我选择的第一个要优化的分量，可不是α的第1个分量。
为啥我不直接选两个分量呢？
我当时是这么想的，选择的两个分量除了要满足违反 g(x)目标条件比较多外，还有一个重要的考量，就是经过一次优化后，两个分量要有尽可能多的改变，这样才能用尽可能少的迭代优化次数让它们达到 g(x)目标条件，既然α1是按照违反 g(x)目标条件比较多来挑选的，我希望选择α2时，能够按照优化后让α1、α2有尽可能多的改变来选。
你可能会想，说的怪好听的，倒要看你怎么选α2？
经过我一番潜心思考，我还真找到一个选α2的标准！！
我为每一个分量算出一个指标E，它是这样的：

文章插图
E.PNG
我发现，当|E1-E2|越大时，优化后的α1、α2改变越大。所以，如果E1是正的，那么E2越负越好，如果E1是负的，那么E2越正越好。这样，我就能选到我的α2啦。
啥，你问这是为什么？
这个回头再说，现在要开始优化我的α1、α2啦。
100、无限风光在险峰
怎么优化α1、α2可以确保优化后，它们对应的样本能够满足 g(x)目标条件或者违反 g(x)目标条件的程度变轻呢？我这人不贪心，只要优化后是在朝着好的方向发展就可以。
本以为峰回路转，谁知道峰回之后是他妈一座更陡峭的山峰！我心一横，你就是90度的山峰，哥们我也要登它一登！！
在沉思中，我的眼睛不经意地瞟见了对偶问题：

文章插图
2.PNG
灵光一闪，计上心来！
虽然我不知道怎样优化α1、α2，让它们对应的样本违反 g(x)目标条件变轻，但是我可以让它们优化后目标函数的值变小啊！使目标函数变小，肯定是朝着正确的方向优化！也就肯定是朝着使违反 g(x)目标条件变轻的方向优化，二者是一致的啊！！
我真是太聪明了！
此时，将α1、α2看做变量，其他分量看做常数，对偶问题就是一个超级简单的二次函数优化问题：

文章插图
10.png
其中：

文章插图
11.png

文章插图
12.png
至此，这个问题已经变得超级简单了！
举例来说明一下，假设y1和y2都等于1，那么第一个限制条件就变成了

文章插图
13.png
首先，将α1=K-α2代入目标函数，这时目标函数变成了关于α2的一元函数，对α2求导并令导数为0可以求出α2_new 。
然后，观察限制条件，第一个条件α1=K-α2相当于
0≦K-α2≦C
进而求得：
K-C≦α2≦K，再加上原有的限制
0≦α2≦C，可得
max（K-C，0）≦α2≦min（K，C）
如果α2_new就在这个限制范围内，OK！求出α1_new，完成一轮迭代。如果α2_new不在这个限制范围内，进行截断，得到新的α2_new_new,据此求得α1_new_new，此轮迭代照样结束！！