# 支持向量機 * [第一部分 線性可分的SVM推導](#第一節) * [第二部分 線性不可分的SVM推導](#第二節) * [第三部分 多類別的SVM推導](#第三節) * [第四部分 線性可分的SVM實驗](#第四節) * [第五部分 線性不可分的SVM實驗](#第五節) * [第六部分 多類別的SVM實驗](#第六節) <h5 id="第一節">第一部分：線性可分的SVM推導</h5> &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp要想理解SVM我們首先要從多維空間的平面方程說起。我們先從三維空間說起吧，然后我們再推廣到更高維空間。我們主要用到點法式方程。<br> &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp點法式方程: 點法式是通過平面的一個法向量和平面的一個點來確定一個平面的。法向量是與這個平面所有向量垂直的向量。那么要求法向量就相當簡單我們只需要取這個平面上的兩個向量a,b由于垂直向量點乘為0我們可以列出方程組an=0 bn=0 兩個式子就可以解出法向量n=(p,q,t) 然后我們知道一個點A(l,o,c) 根據點法式的原形得出平面方程 p(x-l)+q(y-o)+t(z-c)=0 化成一般式子：px + qy + tz + d = 0 其中d = -（pl + qo+ tc）如果d = 0證明平面過原點。否則不過原點（記住） 得到的一個個結論： 1. 平面**用向量表示為：N*X+d=0**（其中向量維度可以是任意維度d是標量） 好了準備工作做完我們開始正式進入主題。 現在我們有一批樣本每個樣本：X={x1, x2, x3.....}其中x1,x2,x3......等是每個樣本的屬性。因為這一節我們進行可線性分類的二分類問題。 假設： 我們的目標是求出兩個最大間隔的平面的中間的平面的方程（其中在那兩條直線上的樣本點就叫做支持向量）：  :-: 其中方程后面的1和-1表示：兩種類別用1和-1來分開（其中的1和-1只是為了方便推導，其實可以任意不同常數） 現在有了方程我們可以去求要優化的目標函數了。就是間隔的大小： 學過高等數學應該知道點到面的距離公式：  :-: 其中的向量是行向量 我們很容易得到間隔大小為： 好我們整理一下要優化的問題如下所示：  我們可變成等價的問題如下：  此問題是凸二次規劃問題能直接用現成的優化計算包求解，但我們有更高效的辦法。 注意：一定要搞明白這里面的變量和要優化的目標函數。這里的目標函數很明顯就是間隔值，自變量是W， b，一定注意X是確定的值。 這相當于求一個有約束函數的最值問題。我們首先想到的是拉格朗日乘子法。我們得到拉格朗日函數：  并對W和b求導為0可得到:  :-: 其中α>=0   注意：這里把對W，b有約束的優化的問題通過用拉格朗日函數求偏導為0，然后帶入目標函數，轉換成了對α有約束的優化問題。 ***** 分析： 因為上面的求拉格朗日函數時，是不等式約束，所以應該滿足KKT條件： 我們分析一下這幾個條件我們已經知道了每一個拉格朗日乘子α對應一個樣本，分析最后一個不等式，我們可以知道拉格朗日乘子α=0或者對應樣本yf(x)=1。如果α=0則該樣本不會出現拉格朗日函數中也就不會對要求的超平面方程起作用。若α>0則必有對應的樣本yf(x)=1，既該樣本在最大間隔邊界上。是一個支持向量。 重點：（當然前面的模型假設也很重要）整體思路先對Wb求最優化（KKT條件），然后求導為0.現在Wb變成只與變量拉格朗日乘子有關的。然后變成對拉格朗日乘子優化問題。求出后拉格朗日乘子后直接得到Wb既求解完畢。我們可以使用KKT條件分析：拉格朗日常數與每個樣本對應。如果拉格朗日乘子為0那么對應的樣本對求解W沒有作用。在圖像上的含義也就是沒有在最大間隔平面上。 ***** 下面就是想辦法求出拉格朗日乘子的算法。為了求這個我們換成了對偶問題。只與拉個朗日乘子一個變量有關（注意始終樣本使常量） 這里我們就不說怎么求解拉格朗日乘子了，可以去查資料，一個著名的方法師SMO。 如果仔細觀察我們還沒有給出求解b的過程呢。