SVM通常用對偶問題來求解，這樣的好處有兩個：1、變量只有N個（N為訓練集中的樣本個數），原始問題中的變量數量與樣本點的特徵個數相同，當樣本特徵非常多時，求解難度較大。2、可以方便地引入核函數，求解非線性SVM。求解對偶問題，常用的算法是SMO，徹底地理解這個算法對初學者有一定難度，本文嘗試模擬算法作者發明該算法的思考過程，讓大家輕輕鬆鬆理解SMO算法。文中的“我”擬指發明算法的大神。
001、初生牛犢不怕虎
最近，不少哥們兒向我反映，SVM對偶問題的求解算法太低效，訓練集很大時，算法還沒有蝸牛爬得快，很多世界著名的學者都在研究新的算法呢。聽聞此言，我心頭一喜：“兄弟我揚名立萬的機會來了！”
我打開書，找出問題，看到是這個樣子的：
2.PNG
這明顯就是一個凸二次規劃問題嘛，還不好解？等等，哥們說現有算法比較慢，所以我絕對不能按照常規思路去思考，要另闢蹊徑。
蹊徑啊蹊徑，你在哪裡呢？
我冥思苦想好幾天，都沒有什麼好辦法，哎！看來揚名立萬的事兒要泡湯了。放下書，我決定去湖邊（注：是瓦爾登湖不？）散散心，我已經在小黑屋關得太久了。
010、得來全不費工夫
正午時分，一絲風也沒有，湖邊零零散散的小情侶在呢喃私語，只有苦逼的我單身一個，我坐在湖邊的一塊大石上，平靜的湖面映出我鬍子拉碴憔悴的臉，我心裡苦笑：“湖想必是可憐我，映出個對影陪我。”“對影？？？！！！”我心頭一道亮光閃過，猶如干裂的土地聽到第一聲驚雷！我突然有了新的思路！
我瘋狂地跑回屋裡，身後是一對對受驚的小情侶怨恨的眼神。
我開始整理自己的思緒：
這個問題如果作為單純的凸二次規劃問題來看，很難有什麼新的辦法，畢竟凸二次規劃已經被研究得透透了。但它的特殊之處在於：它是另一個問題的對偶問題，還滿足KKT條件，怎麼充分利用這個特殊性呢？
我隨機找一個α=（α1，α2，...，αN）。假設它就是最優解，就可以用KKT條件來計算出原問題的最優解（w,b），就是這個樣子：
w.PNG
b.PNG
進而可以得到分離超平面：
CodeCogsEqn.gif
按照SVM的理論，如果這個g(x)是最優的分離超平面，就有：
kkt.PNG
姑且稱這個叫 g(x)目標條件 吧。
根據已有的理論，上面的推導過程是可逆的。也就是說，只要我能找到一個α，它除了滿足對偶問題的兩個
初始限制條件 ：
3.PNG
由它求出的分離超平面g(x)還能滿足 g(x)目標條件 ，那麼這個α就是對偶問題的最優解！！！
至此，我的思路已經確定了：首先，初始化一個α，讓它滿足對偶問題的兩個
初始限制條件 ，然後不斷優化它，使得由它確定的分離超平面滿足 g(x)目標條件 ，在優化的過程中始終確保它滿足 初始限制條件 ，這樣就可以找到最優解。我不禁感到洋洋得意了，哥們我沒有按照傳統思路，想著怎麼去讓目標函數達到最小，而是想著怎麼讓α滿足 g(x)目標條件 ，牛X！我真他媽牛X！哈哈！！
011、中流擊水停不住
具體怎麼優化α呢？經過思考，我發現必須遵循如下兩個基本原則：
- 每次優化時，必須同時優化α的兩個分量，因為只優化一個分量的話，新的α就不再滿足 初始限制條件 中的 等式條件 了。
- 每次優化的兩個分量應當是違反 g(x)目標條件 比較多的。就是說，本來應當是大於等於1的，越是小於1違反 g(x)目標條件 就越多，這樣一來，選擇優化的兩個分量時，就有了基本的標準。
好，我先選擇第一個分量吧，α的分量中有等於0的，有等於C的，還有大於0小於C的，直覺告訴我，先從大於0小於C的分量中選擇是明智的，如果沒有找到可優化的分量時，再從其他兩類分量中挑選。
現在，我選了一個分量，就叫它α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，此輪迭代照樣結束！！
閱讀更多 sandag 的文章
