SVM通常用對偶問題來求解建峭，這樣的好處有兩個：1琉挖、變量只有N個（N為訓練集中的樣本個數）启泣，原始問題中的變量數量與樣本點的特征個數相同，當樣本特征非常多時示辈，求解難度較大寥茫。2、可以方便地引入核函數矾麻，求解非線性SVM纱耻。求解對偶問題，常用的算法是SMO险耀，徹底地理解這個算法對初學者有一定難度弄喘，本文嘗試模擬算法作者發(fā)明該算法的思考過程，讓大家輕輕松松理解SMO算法甩牺。文中的“我”擬指發(fā)明算法的大神蘑志。
001、初生牛犢不怕虎
最近贬派，不少哥們兒向我反映急但，SVM對偶問題的求解算法太低效，訓練集很大時搞乏，算法還沒有蝸牛爬得快波桩，很多世界著名的學者都在研究新的算法呢。聽聞此言查描，我心頭一喜：“兄弟我揚名立萬的機會來了突委！”
我打開書，找出問題冬三，看到是這個樣子的：
這明顯就是一個凸二次規(guī)劃問題嘛，還不好解缘缚？等等勾笆，哥們說現有算法比較慢，所以我絕對不能按照常規(guī)思路去思考桥滨，要另辟蹊徑窝爪。
蹊徑啊蹊徑弛车，你在哪里呢？
我冥思苦想好幾天蒲每，都沒有什么好辦法纷跛，哎！看來揚名立萬的事兒要泡湯了邀杏。放下書贫奠，我決定去湖邊（注：是瓦爾登湖不？）散散心望蜡，我已經在小黑屋關得太久了唤崭。
010、得來全不費工夫
正午時分脖律，一絲風也沒有谢肾，湖邊零零散散的小情侶在呢喃私語，只有苦逼的我單身一個小泉，我坐在湖邊的一塊大石上芦疏，平靜的湖面映出我胡子拉碴憔悴的臉，我心里苦笑：“湖想必是可憐我微姊，映出個對影陪我酸茴。”“對影柒桑？弊决？？？尽Ｆ！”我心頭一道亮光閃過界逛，猶如干裂的土地聽到第一聲驚雷昆稿！我突然有了新的思路！
我瘋狂地跑回屋里息拜，身后是一對對受驚的小情侶怨恨的眼神溉潭。
我開始整理自己的思緒：
這個問題如果作為單純的凸二次規(guī)劃問題來看，很難有什么新的辦法少欺，畢竟凸二次規(guī)劃已經被研究得透透了喳瓣。但它的特殊之處在于：它是另一個問題的對偶問題，還滿足KKT條件赞别，怎么充分利用這個特殊性呢畏陕？
我隨機找一個α=（α1，α2仿滔，...惠毁，αN）犹芹。假設它就是最優(yōu)解，就可以用KKT條件來計算出原問題的最優(yōu)解（w,b）鞠绰，就是這個樣子：
進而可以得到分離超平面：
按照SVM的理論腰埂，如果這個g(x)是最優(yōu)的分離超平面，就有：
姑且稱這個叫g(x)目標條件吧蜈膨。
根據已有的理論屿笼，上面的推導過程是可逆的。也就是說丈挟，只要我能找到一個α刁卜，它除了滿足對偶問題的兩個初始限制條件：
由它求出的分離超平面g(x)還能滿足g(x)目標條件，那么這個α就是對偶問題的最優(yōu)解Ｊ镅省；着俊！
至此例朱，我的思路已經確定了：首先孝情，初始化一個α，讓它滿足對偶問題的兩個初始限制條件洒嗤，然后不斷優(yōu)化它箫荡，使得由它確定的分離超平面滿足g(x)目標條件，在優(yōu)化的過程中始終確保它滿足初始限制條件渔隶，這樣就可以找到最優(yōu)解羔挡。
我不禁感到洋洋得意了，哥們我沒有按照傳統(tǒng)思路间唉，想著怎么去讓目標函數達到最小绞灼，而是想著怎么讓α滿足g(x)目標條件，牛X呈野！我真他媽牛X低矮！哈哈！被冒！
011军掂、中流擊水停不住
具體怎么優(yōu)化α呢？經過思考昨悼，我發(fā)現必須遵循如下兩個基本原則：
每次優(yōu)化時蝗锥，必須同時優(yōu)化α的兩個分量，因為只優(yōu)化一個分量的話率触，新的α就不再滿足初始限制條件中的等式條件了玛追。
每次優(yōu)化的兩個分量應當是違反g(x)目標條件比較多的。就是說闲延，本來應當是大于等于1的痊剖，越是小于1違反g(x)目標條件就越多，這樣一來垒玲，選擇優(yōu)化的兩個分量時陆馁，就有了基本的標準。
好合愈，我先選擇第一個分量吧叮贩，α的分量中有等于0的，有等于C的佛析，還有大于0小于C的益老，直覺告訴我，先從大于0小于C的分量中選擇是明智的寸莫，如果沒有找到可優(yōu)化的分量時捺萌，再從其他兩類分量中挑選。
現在膘茎，我選了一個分量桃纯，就叫它α1吧，這里的1表示它是我選擇的第一個要優(yōu)化的分量披坏，可不是α的第1個分量态坦。
為啥我不直接選兩個分量呢？
我當時是這么想的棒拂，選擇的兩個分量除了要滿足違反g(x)目標條件比較多外伞梯，還有一個重要的考量，就是經過一次優(yōu)化后帚屉，兩個分量要有盡可能多的改變谜诫，這樣才能用盡可能少的迭代優(yōu)化次數讓它們達到g(x)目標條件，既然α1是按照違反g(x)目標條件比較多來挑選的涮阔，我希望選擇α2時猜绣，能夠按照優(yōu)化后讓α1、α2有盡可能多的改變來選敬特。
你可能會想掰邢，說的怪好聽的，倒要看你怎么選α2伟阔？
經過我一番潛心思考辣之，我還真找到一個選α2的標準！皱炉！
我為每一個分量算出一個指標E怀估，它是這樣的：
我發(fā)現，當|E1-E2|越大時，優(yōu)化后的α1多搀、α2改變越大歧蕉。所以，如果E1是正的康铭，那么E2越負越好惯退，如果E1是負的，那么E2越正越好从藤。這樣催跪，我就能選到我的α2啦。
啥夷野，你問這是為什么懊蒸？
這個回頭再說，現在要開始優(yōu)化我的α1悯搔、α2啦骑丸。
100、 無限風光在險峰
怎么優(yōu)化α1鳖孤、α2可以確保優(yōu)化后者娱，它們對應的樣本能夠滿足g(x)目標條件或者違反g(x)目標條件的程度變輕呢？我這人不貪心苏揣，只要優(yōu)化后是在朝著好的方向發(fā)展就可以黄鳍。
本以為峰回路轉，誰知道峰回之后是他媽一座更陡峭的山峰平匈！我心一橫框沟，你就是90度的山峰，哥們我也要登它一登Ｔ鎏俊忍燥！
在沉思中，我的眼睛不經意地瞟見了對偶問題：
靈光一閃隙姿，計上心來梅垄！
雖然我不知道怎樣優(yōu)化α1、α2输玷，讓它們對應的樣本違反g(x)目標條件變輕队丝，但是我可以讓它們優(yōu)化后目標函數的值變小啊欲鹏！使目標函數變小机久，肯定是朝著正確的方向優(yōu)化！也就肯定是朝著使違反g(x)目標條件變輕的方向優(yōu)化赔嚎，二者是一致的氨旄恰ｋ食凇！
我真是太聰明了侠畔！
此時结缚，將α1、α2看做變量践图，其他分量看做常數掺冠，對偶問題就是一個超級簡單的二次函數優(yōu)化問題：
其中：
至此，這個問題已經變得超級簡單了码党！
舉例來說明一下，假設y1和y2都等于1斥黑，那么第一個限制條件就變成了
首先揖盘，將α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，此輪迭代照樣結束５癯痢集乔！
至此，我終于找到了一個新的求解SVM對偶問題的方法坡椒，在SVM這塊土地上扰路，種上了一棵自己的樹！揚名立萬也就是水到渠成啦肠牲！
