SVM通常用對偶問題來求解，這樣的好處有兩個：1、變量只有N個（N為訓(xùn)練集中的樣本個數(shù)），原始問題中的變量數(shù)量與樣本點(diǎn)的特征個數(shù)相同，當(dāng)樣本特征非常多時，求解難度較大。2、可以方便地引入核函數(shù)，求解非線性SVM。求解對偶問題，常用的算法是SMO，徹底地理解這個算法對初學(xué)者有一定難度，本文嘗試模擬算法作者發(fā)明該算法的思考過程，讓大家輕輕松松理解SMO算法。文中的“我”擬指發(fā)明算法的大神。
001、初生牛犢不怕虎
最近，不少哥們兒向我反映，SVM對偶問題的求解算法太低效，訓(xùn)練集很大時，算法還沒有蝸牛爬得快，很多世界著名的學(xué)者都在研究新的算法呢。聽聞此言，我心頭一喜：“兄弟我揚(yáng)名立萬的機(jī)會來了！”
我打開書，找出問題，看到是這個樣子的：
2.PNG
這明顯就是一個凸二次規(guī)劃問題嘛，還不好解？等等，哥們說現(xiàn)有算法比較慢，所以我絕對不能按照常規(guī)思路去思考，要另辟蹊徑。
蹊徑啊蹊徑，你在哪里呢？
我冥思苦想好幾天，都沒有什么好辦法，哎！看來揚(yáng)名立萬的事兒要泡湯了。放下書，我決定去湖邊（注：是瓦爾登湖不？）散散心，我已經(jīng)在小黑屋關(guān)得太久了。
010、得來全不費(fèi)工夫
正午時分，一絲風(fēng)也沒有，湖邊零零散散的小情侶在呢喃私語，只有苦逼的我單身一個，我坐在湖邊的一塊大石上，平靜的湖面映出我胡子拉碴憔悴的臉，我心里苦笑：“湖想必是可憐我，映出個對影陪我。”“對影？？？！！！”我心頭一道亮光閃過，猶如干裂的土地聽到第一聲驚雷！我突然有了新的思路！
我瘋狂地跑回屋里，身后是一對對受驚的小情侶怨恨的眼神。
我開始整理自己的思緒：
這個問題如果作為單純的凸二次規(guī)劃問題來看，很難有什么新的辦法，畢竟凸二次規(guī)劃已經(jīng)被研究得透透了。但它的特殊之處在于：它是另一個問題的對偶問題，還滿足KKT條件，怎么充分利用這個特殊性呢？
我隨機(jī)找一個α=（α1，α2，...，αN）。假設(shè)它就是最優(yōu)解，就可以用KKT條件來計算出原問題的最優(yōu)解（w,b），就是這個樣子：
w.PNG
b.PNG
進(jìn)而可以得到分離超平面：
CodeCogsEqn.gif
按照SVM的理論，如果這個g(x)是最優(yōu)的分離超平面，就有：
kkt.PNG
姑且稱這個叫 g(x)目標(biāo)條件 吧。
根據(jù)已有的理論，上面的推導(dǎo)過程是可逆的。也就是說，只要我能找到一個α，它除了滿足對偶問題的兩個 初始限制條件 ：
3.PNG
由它求出的分離超平面g(x)還能滿足 g(x)目標(biāo)條件 ，那么這個α就是對偶問題的最優(yōu)解！！！
至此，我的思路已經(jīng)確定了：首先，初始化一個α，讓它滿足對偶問題的兩個 初始限制條件，然后不斷優(yōu)化它，使得由它確定的分離超平面滿足 g(x)目標(biāo)條件 ，在優(yōu)化的過程中始終確保它滿足 初始限制條件 ，這樣就可以找到最優(yōu)解。
我不禁感到洋洋得意了，哥們我沒有按照傳統(tǒng)思路，想著怎么去讓目標(biāo)函數(shù)達(dá)到最小，而是想著怎么讓α滿足 g(x)目標(biāo)條件 ，牛X！我真他媽牛X！哈哈！！
011、中流擊水停不住
具體怎么優(yōu)化α呢？經(jīng)過思考，我發(fā)現(xiàn)必須遵循如下兩個基本原則：
- 每次優(yōu)化時，必須同時優(yōu)化α的兩個分量，因?yàn)橹粌?yōu)化一個分量的話，新的α就不再滿足 初始限制條件 中的 等式條件 了。
- 每次優(yōu)化的兩個分量應(yīng)當(dāng)是違反 g(x)目標(biāo)條件 比較多的。就是說，本來應(yīng)當(dāng)是大于等于1的，越是小于1違反 g(x)目標(biāo)條件 就越多，這樣一來，選擇優(yōu)化的兩個分量時，就有了基本的標(biāo)準(zhǔn)。
好，我先選擇第一個分量吧，α的分量中有等于0的，有等于C的，還有大于0小于C的，直覺告訴我，先從大于0小于C的分量中選擇是明智的，如果沒有找到可優(yōu)化的分量時，再從其他兩類分量中挑選。
現(xiàn)在，我選了一個分量，就叫它α1吧，這里的1表示它是我選擇的第一個要優(yōu)化的分量，可不是α的第1個分量。
為啥我不直接選兩個分量呢？
我當(dāng)時是這么想的，選擇的兩個分量除了要滿足違反 g(x)目標(biāo)條件 比較多外，還有一個重要的考量，就是經(jīng)過一次優(yōu)化后，兩個分量要有盡可能多的改變，這樣才能用盡可能少的迭代優(yōu)化次數(shù)讓它們達(dá)到 g(x)目標(biāo)條件 ，既然α1是按照違反 g(x)目標(biāo)條件 比較多來挑選的，我希望選擇α2時，能夠按照 優(yōu)化后讓α1、α2有盡可能多的改變 來選。
你可能會想，說的怪好聽的，倒要看你怎么選α2？
經(jīng)過我一番潛心思考，我還真找到一個選α2的標(biāo)準(zhǔn)！！
我為每一個分量算出一個指標(biāo)E，它是這樣的：
E.PNG
我發(fā)現(xiàn)，當(dāng)|E1-E2|越大時，優(yōu)化后的α1、α2改變越大。所以，如果E1是正的，那么E2越負(fù)越好，如果E1是負(fù)的，那么E2越正越好。這樣，我就能選到我的α2啦。
啥，你問這是為什么？
這個回頭再說，現(xiàn)在要開始優(yōu)化我的α1、α2啦。
100、 無限風(fēng)光在險峰
怎么優(yōu)化α1、α2可以確保優(yōu)化后，它們對應(yīng)的樣本能夠滿足 g(x)目標(biāo)條件 或者違反 g(x)目標(biāo)條件 的程度變輕呢？我這人不貪心，只要優(yōu)化后是在朝著好的方向發(fā)展就可以。
本以為峰回路轉(zhuǎn)，誰知道峰回之后是他媽一座更陡峭的山峰！我心一橫，你就是90度的山峰，哥們我也要登它一登！！
在沉思中，我的眼睛不經(jīng)意地瞟見了對偶問題：
2.PNG
靈光一閃，計上心來！
雖然我不知道怎樣優(yōu)化α1、α2，讓它們對應(yīng)的樣本違反 g(x)目標(biāo)條件 變輕，但是我可以讓它們優(yōu)化后目標(biāo)函數(shù)的值變小啊！使目標(biāo)函數(shù)變小，肯定是朝著正確的方向優(yōu)化！也就肯定是朝著使違反 g(x)目標(biāo)條件 變輕的方向優(yōu)化，二者是一致的啊！！
我真是太聰明了！
此時，將α1、α2看做變量，其他分量看做常數(shù)，對偶問題就是一個超級簡單的二次函數(shù)優(yōu)化問題：
10.png
其中：
11.png
12.png
至此，這個問題已經(jīng)變得超級簡單了！
舉例來說明一下，假設(shè)y1和y2都等于1，那么第一個限制條件就變成了
13.png
首先，將α1=K-α2代入目標(biāo)函數(shù)，這時目標(biāo)函數(shù)變成了關(guān)于α2的一元函數(shù)，對α2求導(dǎo)并令導(dǎo)數(shù)為0可以求出α2_new。
然后，觀察限制條件，第一個條件α1=K-α2相當(dāng)于
0≦K-α2≦C
進(jìn)而求得：
K-C≦α2≦K，再加上原有的限制
0≦α2≦C，可得
max（K-C，0）≦α2≦min（K，C）
如果α2_new就在這個限制范圍內(nèi)，OK！求出α1_new，完成一輪迭代。如果α2_new不在這個限制范圍內(nèi)，進(jìn)行截斷，得到新的α2_new_new,據(jù)此求得α1_new_new，此輪迭代照樣結(jié)束！！
