背景
上一篇文章總結了linear hard SVM，解法很直覺，直接從SVM的定義出發，經過等價變換，轉成QP問題求解。這一講，從另一個角度描述hard SVM的解法，不那麼直覺，但是可以避免feature轉換時的資料計算，這樣就可以利用一些很高緯度（甚至是無限次元）的feature轉換，得到一些更精細的解。
拉格朗日乘子式
首先，回顧一下SVM問題的定義，如下：
這個公式是不是很奇怪，無端的多處了N個變量，但是再看下面的變化，就知道這個拉格朗日乘子式的厲害了。
什麼，SVM問題等于右邊那個min max？沒錯，雖然初看感覺不科學，但是仔細分析，的确如此。首先，由于，令f(w,b) = ，
當f(w,b) > 0，在w，b固定的情況下，，max會将放大到；
當f(w,b)0，那麼，那麼。
是以，綜合兩種情況，SVM問題與min max變換公式等價。是不是很奇妙，不得不佩服拉格朗日大神。
對偶變換
上面的問題中min max的形式不友善求解，不過可以通過一番變化，導出max min的形式，這樣就可以從内到外，先計算裡面的min，然後計算外面的max。這種變化叫對偶變化。
首先選任意一個固定的，并且，那麼有
兩邊通過w,b取min，等式仍然成立，即
有多重選擇，但是上面的不等式一緻成立，是以在衆多的選擇一個最大，上面的等式變形為，
這樣，min max就和max min建立了一定的聯系，但是由于是""，稱之為弱對偶（week duality）。""強對偶（strong duality）如何才能成立呢？需要滿足下面的條件，
原始問題是凸問題
原始問題線性可分
線性限制條件
太橋了，SVM問題完全符合上述限制，是以是對偶，這樣可以通過解右邊max min的問題來得到最終解！
問題化簡
經過上面的對偶變化，下面來一步一步的簡化我們的原始問題，
首先對b求偏導數,并且為0，有如下結果
帶入這個結果到上面的公司，化簡
接下啦，對w求偏導數，
是以，向量w為
将w帶入，并且去掉min，得到如下
執行到這裡，現在目标函數隻與有關，形式滿足QP，可以輕易得到，也就是得到w。但是在計算過程中，需要計算一個中間矩陣Q，次元為N*N，這個是主要計算開銷。上一講無需計算這個Q，因為Q的形式十分簡單。
問題來了，如何求解b，上面的目标函數中，在之前的簡化過程中消去了b，已經與b無關。
計算b
現在隻剩下最後一個問題，如何計算b? 在之前的簡化過程中消去了b，上面的QP解與無關。
KKT條件幫助我們解決這個問題。如果原始問題和對偶問題都有最優解，且解相同，那麼會滿足KKT條件。這也是一個充分必要條件，其中很重要的一點是complementary slackness(互補松弛性)，該條件有下面等式成立，
由于（對偶條件），且（原始條件），那麼兩者有一個不為0時，另外一個必然為0。是以，隻要找到一個，就可以利用這個性質計算出b，計算方法如下：
兩邊乘以,
理論來說，隻需要一個點就可以，但是實際上由于計算有誤差，可能會計算所有的b，然後求平均。并且這些可以計算出b的點，就是支援向量，因為他們滿足了原始問題中支撐向量的定義。但是，并不是所有的支撐向量，都有對應的。一般的，我們隻用的向量稱為支撐向量，而那些滿足支撐向量定義的向量稱之為候選支撐向量，有如下關系
并且，為了簡化計算，在計算w的時候，的計算均可以省去，如下
w的哲學
通過上面的計算，其實最後w是（）的線性組合。同樣的，PLA中w也是（）的線性組合。隻是SVM利用支撐向量求解這個線性組合，PLA使用錯誤的向量。同理，邏輯回歸，線性回歸也有類似規律，稱這種現象為"w represented by data"。
總結
本節使用對偶問題，從另外一個側面求解了SVM，并且資料學推導相對複雜，計算量也增加了許多，因為需要求解一個N*N次元的矩陣Q。但是，為什麼要做這些事情呢，hard linear SVM要簡單許多複？其實換成對偶問題是為了利用kernel做鋪墊，改kernel可以将次元轉化的計算省略，進而可以計算很複雜的轉化，這一點下一節讨論。
PS:劃線部分段落是由于包含公式，無法正常顯示，是以采用圖檔方式在下方顯示。
<b>聲明：如有轉載本博文章，請注明出處。您的支援是我的動力！文章部分内容來自網際網路，本人不負任何法律責任。</b>
本文轉自bourneli部落格園部落格，原文連結：http://www.cnblogs.com/bourneli/p/4199990.html，如需轉載請自行聯系原作者