支持向量機理論演算法與拓展
『壹』 支持向量機(SVM)基本原理
看了很多關於SVM的博客，但是常常只能保存書簽之後看，有時候有的博客就突然沒了，這里就作為搬運工總結一下之後自己看吧。主要內容來自於：
支持向量機通俗導論（理解SVM的三層境界）
線性回歸
給定數據集 , 其中, ,線性回歸試圖學習到一個線性模型,盡可能地輸出正確標記.
如果我們要用線性回歸演算法來解決一個分類問題,(對於分類,y 取值為 0 或者 1),但如果你使用的是線性回歸,那麼假設函數的輸出值可能遠大於 1,或者遠小於 0,就算所有訓練樣本的標簽 y 都是 0 或 1但是如果演算法得到的值遠大於 1 或者遠小於 0 的話,就會感覺很奇怪。所以我們在接下來的要研究的演算法就叫做邏輯回歸演算法,這個演算法的性質是:它的輸出值永遠在 0 到 1 之間。
所以邏輯回歸就是一個分類演算法,這個演算法的輸出值永遠在 0 到 1 之間.
我們先看二分類的LR,具體做法是:利用sigmoid 函數,將每一個點的回歸值映射到0,1之間.sigmoid函數特性如下:
如圖所示,令 , 當 z > 0 , z 越大, sigmoid 返回值越接近1(但永遠不會超過1). 反之,當z < 0時,z 越小, sigmoid 返回值越接近0(但永遠不會小於0).
支持向量機 ，因其英文名為support vector machine，故一般簡稱SVM，通俗來講，它是一種二類分類模型，其基本模型定義為 特徵空間 上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。
線性分類器
給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：
logistic回歸目的是從特徵學習出一個0/1分類模型，而這個模型是將特性的線性組合作為自變數，由於自變數的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數）將自變數映射到(0,1)上，映射後的值被認為是屬於y=1的概率。
假設函數:
其中x是n維特徵向量，函數g就是logistic函數。
圖像為：
在超平面w x+b=0確定的情況下，|w x+b|能夠表示點x到距離超平面的遠近，而通過觀察w x+b的符號與類標記y的符號是否一致可判斷分類是否正確，所以，可以用(y (w*x+b))的正負性來判定或表示分類的正確性。於此，我們便引出了函數間隔（functional margin）的概念。
定義函數間隔 （用表示）為
而超平面(w，b)關於T中所有樣本點(xi，yi)的函數間隔最小值（其中，x是特徵，y是結果標簽，i表示第i個樣本），便為超平面(w, b)關於訓練數據集T的函數間隔：
但這樣定義的函數間隔有問題，即如果成比例的改變w和b（如將它們改成2w和2b），則函數間隔的值f(x)卻變成了原來的2倍（雖然此時超平面沒有改變），所以只有函數間隔還遠遠不夠。
事實上，我們可以對法向量w加些約束條件，從而引出真正定義點到超平面的距離--幾何間隔（geometrical margin）的概念。
假定對於一個點 x ，令其垂直投影到超平面上的對應點為 x0 ，w 是垂直於超平面的一個向量， 為樣本x到超平面的距離，如下圖所示：
根據平面幾何知識，有
其中||w||為w的二階范數（范數是一個類似於模的表示長度的概念）， 是單位向量（一個向量除以它的模稱之為單位向量）。
又由於x0 是超平面上的點，滿足 f(x0)=0，代入超平面的方程 ,可得 ，即
隨即讓此式 的兩邊同時乘以 ，再根據 和 ，即可算出 ：
為了得到 的絕對值，令 乘上對應的類別 y，即可得出幾何間隔（用 表示）的定義：
從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以||w||，而且函數間隔y (wx+b) = y f(x)實際上就是|f(x)|，只是人為定義的一個間隔度量，而幾何間隔|f(x)|/||w||才是直觀上的點到超平面的距離。
對一個數據點進行分類，當超平面離數據點的「間隔」越大，分類的確信度（confidence）也越大。所以，為了使得分類的確信度盡量高，需要讓所選擇的超平面能夠最大化這個「間隔」值。這個間隔就是下圖中的Gap的一半。
通過由前面的分析可知：函數間隔不適合用來最大化間隔值，因為在超平面固定以後，可以等比例地縮放w的長度和b的值，這樣可以使得 的值任意大，亦即函數間隔 可以在超平面保持不變的情況下被取得任意大。但幾何間隔因為除上了 ，使得在縮放w和b的時候幾何間隔的值 是不會改變的，它只隨著超平面的變動而變動，因此，這是更加合適的一個間隔。換言之，這里要找的最大間隔分類超平面中的「間隔」指的是幾何間隔。
於是最大間隔分類器（maximum margin classifier）的目標函數可以定義為
同時需滿足一些條件，根據間隔的定義，有
回顧下幾何間隔的定義 ，可知：如果令函數間隔 等於1（之所以令等於1，是為了方便推導和優化，且這樣做對目標函數的優化沒有影響），則有 = 1 / ||w||且 ，從而上述目標函數轉化成了：
相當於在相應的約束條件 下，最大化這個1/||w||值，而1/||w||便是幾何間隔。
據了解，
由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。
那什麼是拉格朗日對偶性呢？簡單來講，通過給每一個約束條件加上一個拉格朗日乘子 ,（Lagrange multiplier），定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）
然後令：
容易驗證，當某個約束條件不滿足時，例如 ，那麼顯然有 （只要令 即可）。而當所有約束條件都滿足時，則最優值為 ，亦即最初要最小化的量。
因此，在要求約束條件得到滿足的情況下最小化 ，實際上等價於直接最小化 （當然，這里也有約束條件，就是 ≥0,i=1,…,n） ，因為如果約束條件沒有得到滿足， 會等於無窮大，自然不會是我們所要求的最小值。
具體寫出來，目標函數變成了：
這里用 表示這個問題的最優值，且和最初的問題是等價的。如果直接求解，那麼一上來便得面對w和b兩個參數，而 又是不等式約束，這個求解過程不好做。不妨把最小和最大的位置交換一下，變成：
交換以後的新問題是原始問題的對偶問題，這個新問題的最優值用 來表示。而且有 ≤ ，在滿足某些條件的情況下，這兩者相等，這個時候就可以通過求解對偶問題來間接地求解原始問題。
換言之，之所以從minmax 的原始問題，轉化為maxmin 的對偶問題，一者因為 是 的近似解，二者，轉化為對偶問題後，更容易求解。
下面可以先求L 對w、b的極小，再求L對 的極大。
KKT條件
≤ 在滿足某些條件的情況下，兩者等價，這所謂的「滿足某些條件」就是要滿足KKT條件。
要讓兩者等價需滿足strong ality （強對偶），而後有學者在強對偶下提出了KKT條件，且KKT條件的成立要滿足constraint qualifications，而constraint qualifications之一就是Slater條件。所謂Slater 條件，即指：凸優化問題，如果存在一個點x，使得所有等式約束都成立，並且所有不等式約束都嚴格成立（即取嚴格不等號，而非等號），則滿足Slater 條件。對於此處，Slater 條件成立，所以 ≤ 可以取等號。
一般地，一個最優化數學模型能夠表示成下列標准形式：
其中，f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數量。
KKT條件的意義：它是一個非線性規劃（Nonlinear Programming）問題能有最優化解法的必要和充分條件。
而KKT條件就是指上面最優化數學模型的標准形式中的最小點 x* 必須滿足下面的條件：
我們這里的問題是滿足 KKT 條件的（首先已經滿足Slater條件，再者f和gi也都是可微的，即L對w和b都可導），因此現在我們便轉化為求解第二個問題。
也就是說，原始問題通過滿足KKT條件，已經轉化成了對偶問題。而求解這個對偶學習問題，分為3個步驟：首先要讓L(w，b，a) 關於 w 和 b 最小化，然後求對 的極大，最後利用SMO演算法求解對偶問題中的拉格朗日乘子。
對偶問題求解的3個步驟
將以上結果代入之前的L：
得到：
具體推導過程是比較復雜的，如下所示：
最後，得到：
「倒數第4步」推導到「倒數第3步」使用了線性代數的轉置運算，由於ai和yi都是實數，因此轉置後與自身一樣。「倒數第3步」推導到「倒數第2步」使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運演算法則。最後一步是上一步的順序調整。
從上面的最後一個式子，我們可以看出，此時的拉格朗日函數只包含了一個變數，那就是 （求出了 便能求出w，和b，由此可見，則核心問題：分類函數 也就可以輕而易舉的求出來了）。
上述式子要解決的是在參數上 求最大值W的問題，至於 和 都是已知數。要了解這個SMO演算法是如何推導的，請跳到下文第3.5節、SMO演算法。
總結
讓我們再來看看上述推導過程中得到的一些有趣的形式。首先就是關於我們的 hyper plane ，對於一個數據點 x 進行分類，實際上是通過把 x 帶入到 算出結果然後根據其正負號來進行類別劃分的。而前面的推導中我們得到:
因此分類函數為：
這里的形式的有趣之處在於，對於新點 x的預測，只需要計算它與訓練數據點的內積即可（表示向量內積），這一點至關重要，是之後使用 Kernel 進行非線性推廣的基本前提。此外，所謂 Supporting Vector 也在這里顯示出來——事實上，所有非Supporting Vector 所對應的系數 都是等於零的，因此對於新點的內積計算實際上只要針對少量的「支持向量」而不是所有的訓練數據即可。
為什麼非支持向量對應的 等於零呢？直觀上來理解的話，就是這些「後方」的點——正如我們之前分析過的一樣，對超平面是沒有影響的，由於分類完全有超平面決定，所以這些無關的點並不會參與分類問題的計算，因而也就不會產生任何影響了。
回憶一下我們通過 Lagrange multiplier得到的目標函數：
注意到如果 xi 是支持向量的話，上式中紅顏色的部分是等於 0 的（因為支持向量的 functional margin 等於 1 ），而對於非支持向量來說，functional margin 會大於 1 ，因此紅顏色部分是大於零的，而 又是非負的，為了滿足最大化， 必須等於 0 。這也就是這些非Supporting Vector 的點的局限性。
至此，我們便得到了一個maximum margin hyper plane classifier，這就是所謂的支持向量機（Support Vector Machine）。當然，到目前為止，我們的 SVM 還比較弱，只能處理線性的情況，不過，在得到了對偶al 形式之後，通過 Kernel 推廣到非線性的情況就變成了一件非常容易的事情了(通過求解對偶問題得到最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題」)。
事實上，大部分時候數據並不是線性可分的，這個時候滿足這樣條件的超平面就根本不存在。在上文中，我們已經了解到了SVM處理線性可分的情況，那對於非線性的數據SVM咋處理呢？對於非線性的情況，SVM 的處理方法是選擇一個核函數 κ(⋅,⋅) ，通過將數據映射到高維空間，來解決在原始空間中線性不可分的問題。
具體來說，在線性不可分的情況下，支持向量機首先在低維空間中完成計算，然後通過核函數將輸入空間映射到高維特徵空間，最終在高維特徵空間中構造出最優分離超平面，從而把平面上本身不好分的非線性數據分開。如圖所示，一堆數據在二維空間無法劃分，從而映射到三維空間里劃分：
而在我們遇到核函數之前，如果用原始的方法，那麼在用線性學習器學習一個非線性關系，需要選擇一個非線性特徵集，並且將數據寫成新的表達形式，這等價於應用一個固定的非線性映射，將數據映射到特徵空間，在特徵空間中使用線性學習器，因此，考慮的假設集是這種類型的函數：
這里ϕ：X->F是從輸入空間到某個特徵空間的映射，這意味著建立非線性學習器分為兩步：
首先使用一個非線性映射將數據變換到一個特徵空間F，
然後在特徵空間使用線性學習器分類。
而由於對偶形式就是線性學習器的一個重要性質，這意味著假設可以表達為訓練點的線性組合，因此決策規則可以用測試點和訓練點的內積來表示：
如果有一種方式可以在特徵空間中直接計算內積〈φ(xi · φ(x)〉，就像在原始輸入點的函數中一樣，就有可能將兩個步驟融合到一起建立一個非線性的學習器，這樣直接計演算法的方法稱為核函數方法：
核是一個函數K，對所有x，z，滿足 ，這里φ是從X到內積特徵空間F的映射。
來看個核函數的例子。如下圖所示的兩類數據，分別分布為兩個圓圈的形狀，這樣的數據本身就是線性不可分的，此時咱們該如何把這兩類數據分開呢(下文將會有一個相應的三維空間圖)？
事實上，上圖所述的這個數據集，是用兩個半徑不同的圓圈加上了少量的噪音生成得到的，所以，一個理想的分界應該是一個「圓圈」而不是一條線（超平面）。如果用 和 來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：
注意上面的形式，如果我們構造另外一個五維的空間，其中五個坐標的值分別為 ，那麼顯然，上面的方程在新的坐標系下可以寫作：
關於新的坐標 ，這正是一個 hyper plane 的方程！也就是說，如果我們做一個映射 ，將 按照上面的規則映射為 ，那麼在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類演算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。
再進一步描述 Kernel 的細節之前，不妨再來看看上述例子在映射過後的直觀形態。當然，你我可能無法把 5 維空間畫出來，不過由於我這里生成數據的時候用了特殊的情形，所以這里的超平面實際的方程是這個樣子的（圓心在 軸上的一個正圓）
因此我只需要把它映射到 ，這樣一個三維空間中即可，下圖即是映射之後的結果，將坐標軸經過適當的旋轉，就可以很明顯地看出，數據是可以通過一個平面來分開的
核函數相當於把原來的分類函數：
映射成：
而其中的 可以通過求解如下 al 問題而得到的：
這樣一來問題就解決了嗎？似乎是的：拿到非線性數據，就找一個映射
『貳』 支持向量機（SVM）
支持向量機（support vector machine），故一般簡稱SVM，通俗來講，它是一種二分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，這族分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。SVM在很多諸如文本分類，圖像分類，生物序列分析和生物數據挖掘，手寫字元識別等領域有很多的應用。
支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。
假設給定一些分屬於兩類的2維點，這些點可以通過直線分割， 我們要找到一條最優的分割線，如何來界定一個超平面是不是最優的呢?
如圖：
在上面的圖中，a和b都可以作為分類超平面，但最優超平面只有一個，最優分類平面使間隔最大化。 那是不是某條直線比其他的更加合適呢? 我們可以憑直覺來定義一條評價直線好壞的標准:
距離樣本太近的直線不是最優的，因為這樣的直線對雜訊敏感度高，泛化性較差。 因此我們的目標是找到一條直線（圖中的最優超平面），離所有點的距離最遠。 由此， SVM演算法的實質是找出一個能夠將某個值最大化的超平面，這個值就是超平面離所有訓練樣本的最小距離。這個最小距離用SVM術語來說叫做間隔(margin) 。
描述：給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：
例如：現在有一個二維平面，平面上有兩種不同的數據，分別用圈和叉表示。由於這些數據是線性可分的，所以可以用一條直線將這兩類數據分開，這條直線就相當於一個超平面，超平面一邊的數據點所對應的y全是-1 ，另一邊所對應的y全是1。
我們令分類函數為：
當f(x) 等於0的時候，x便是位於超平面上的點，而f(x)大於0的點對應 y=1 的數據點，f(x)小於0的點對應y=-1的點，如下圖所示：
一個點距離超平面的遠近可以表示分類預測的確信或准確程度，如何確定這個超平面呢？從直觀上而言，這個超平面應該是最適合分開兩類數據的直線。而判定「最適合」的標准就是這條直線離直線兩邊的數據的間隔最大。所以，得尋找有著最大間隔的超平面。
補充知識點： 點到平面的距離
支持向量機學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面.。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個(等價於感知機)，但是幾何間隔最大的分離超平面是唯一的。這里的間隔最大化又稱為硬間隔最大化。
間隔最大化的直觀解釋是:對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點(離超平面最近的點)也有足夠大的確信度將它們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。
按照我們前面的分析，對一個數據點進行分類， 當它的margin越大的時候，分類的confidence越大。 對於一個包含n個點的數據集，我們可以很自然地定義它的margin為所有這n個點的margin值中最小的那個。於是，為了使得分類的confidence高，我們希望所選擇的超平面hyper plane能夠最大化這個margin值。讓所選擇的超平面能夠最大化這個「間隔」值，這個間隔就是下圖中的Gap的一半：
為什麼用幾何間隔求最大的分離超平面而不用函數間隔？
例題：
我們構造了約束最優化問題，就是下面這個：
此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。
補充知識點： 拉格朗日乘子法學習
拉格朗日KKT條件
KKT條件介紹
拉格朗日對偶
通過給每一個約束條件加上一個拉格朗日乘子（Lagrange multiplier）α，定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）：
求解這個式子的過程需要拉格朗日對偶性的相關知識。
例題：
接下來談談線性不可分的情況，因為 線性可分這種假設實在是太有局限性 了。下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。
要想在這種情況下的分類器，有兩種方式， 一種是用曲線 去將其完全分開，曲線就是一種 非線性 的情況，跟之後將談到的 核函數 有一定的關系：
另外一種還是用直線，不過不用去保證可分性 ，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了。這種學習的時候學到了「雜訊」的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌。
我們可以為分錯的點加上一點懲罰，對一個分錯的點的 懲罰函數 就是 這個點到其正確位置的距離：
對於線性不可分的情況，我們可以用核函數讓空間從原本的線性空間變成一個更高維的空間 ， 在這個高維的線性空間下，再用一個超平面進行劃分 。 這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的：
上圖是一個線性不可分的圖，當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：
用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。
形象說明：例如世界上本來沒有兩個完全一樣的物體，對於所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，是在不行我們還可以加入頁碼，可以加入擁有者，可以加入購買地點，可以加入筆記內容等等。當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。
核函數定義：
核技巧在支持向量機中的應用：
常用核函數：
非線性支持向量機學習演算法：
支持向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以致無法使用。所以，如何高效地實現支持向量機學習就成為一一個重要的問題。目前人們已提出許多快速實現演算法.本節講述其中的序列最小最優化(sequential minimal optimization, SMO)演算法。
上述問題是要求解N個參數(α1,α2,α3,...,αN)，其他參數均為已知，序列最小最優化演算法(SMO)可以高效的求解上述SVM問題，它把原始求解N個參數二次規劃問題分解成很多個子二次規劃問題分別求解，每個子問題只需要求解2個參數，方法類似於坐標上升，節省時間成本和降低了內存需求。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。
整個SMO演算法包括兩部分，求解兩個變數的 二次規劃 問題和選擇這兩個變數的 啟發式 方法。
上面求得的(α1)new和(α2)new是在η>0的情況下求得的：
當時為了推導公式我們直接默認它是大於0了，現在我們需要重新審視這一項（η）。這一項是原來關於的二次項的系數。我們可以分下面三種情況討論：
（1）當η>0時 ：這個二次函數開口向上，所以要求這個二次函數的最小值，如果說極值點不在計算出的可行域的范圍內，就要根據這個極值點和可行域邊界值的關系來得到取最小值的地方：
①如果這個極值點在可行域左邊，那麼我們可以得到這個可行域內二次函數一定在單增，所以此時L應該是那個取最小值的地方。就如大括弧的第三種情況。
②如果這個極值點在可行域右邊，那麼此時可行域內一定單減，所以此時H就是那個取最小值的地方，就是大括弧里的第一種情況。
（2）當η=0時： 這個二次函數就變成了一個一次函數，那麼不管這個一次函數的單調性怎樣，最小值一定是在邊界處取到。所以到時候計算可行域的兩個邊界的值，看哪個小就用哪個。
（3）當η<0時: 這個二次函數開口向下，那麼此時怎麼得到取最小值的點呢？很容易就能想到：最小值也是在可行域的邊界處取到。很容易理解，此時開口向下，當極值點在區間內時，最小值只能在端點處取，因為極值點處是最大的。而當極值點在區間外時，區間內一定是單調的，此時最小值也只能在端點處取。通過計算比較邊界處的目標函數值，哪個小取哪個。
通過以上判斷求出(α2)new以後，再根據公式求出(α1)new，然後帶入目標函數（1）中。即如下過程：
上述分析是在從N個變數中已經選出兩個變數進行優化的方法，下面分析如何高效地選擇兩個變數進行優化，使得目標函數下降的最快。
『叄』 支持向量機原理
支持向量機方法的基本思想是：定義最優線性超平面，並把尋找最優線性超平面的演算法歸結為求解一個凸規劃問題。進而基於Mercer核展開定理，通過非線性映射φ，把樣本空間映射到一個高維乃至於無窮維的特徵空間（Hilbert空間），使在特徵空間中可以應用線性學習機的方法解決樣本空間中的高度非線性分類和回歸等問題（Nello Cristianini，2005）。簡單地說就是升維和線性化。一般的升維都會帶來計算的復雜化。這里自然發生的兩個問題是如何求得非線性映射φ和解決演算法的復雜性。SVM方法巧妙地解決了這兩個難題：由於應用了核函數的展開定理，所以根本不需要知道非線性映射的顯式表達式；由於是在高維特徵空間中應用線性學習機的方法，所以與線性模型相比不但幾乎不增加計算的復雜性，而且在某種程度上避免了「維數災」。另外，SVM是一種有堅實理論基礎的新穎的小樣本學習方法。它基本上不涉及概率測度的定義及大數定律等，因此不同於現有的統計方法。從本質上看，它避開了從歸納到演繹的傳統過程，實現了高效的從訓練樣本到預報樣本的「轉導推理」（transctive inference），大大簡化了通常的分類和回歸等問題。SVM的最終決策函數只由少數的支持向量所確定，計算的復雜性取決於支持向量的數目，而不是樣本空間的維數，這在某種意義上避免了「維數災」。如果說神經網路方法是對樣本的所有因子加權的話，SVM方法是對只佔樣本集少數的支持向量樣本「加權」。當預報因子與預報對象間蘊涵的復雜非線性關系尚不清楚時，基於關鍵樣本的方法可能優於基於因子的「加權」。少數支持向量決定了最終結果，這不但可以幫助我們抓住關鍵樣本、「剔除」大量冗餘樣本，而且註定了該方法不但演算法簡單，而且具有較好的「魯棒」性。由於有較為嚴格的統計學習理論做保證，應用SVM方法建立的模型具有較好的推廣能力。SVM方法可以給出所建模型的推廣能力的確定的界，這是目前其它任何學習方法所不具備的。
隨著支持向量機理論的深入研究，出現了許多變種的支持向量機，如Sheng-wei Fe（2009）提出的兩類重要的預測技術：分類和回歸。其中分類問題預測要求觀察值是離散的，而回歸問題主要針對決策屬性值是連續的情況，它通過學習訓練樣本集建立一個回歸器，然後在條件屬性給定的情況下進行預測。
支持向量機回歸分為線性回歸和非線性回歸，其原理如下：
（1）支持向量機線性回歸
設樣本集為：（x1，y1），…，（xi，yi），x∈Rn，y∈R，回歸函數用下列線性方程來表示：
f（x）=w·x＋b （4.14）
假設所有訓練數據在ε精度下如圖4.5所示無誤差地用線性函數擬合，即
基坑降水工程的環境效應與評價方法
圖4.5 支持向量機回歸
考慮到允許誤差的情況，引入鬆弛因子ξi，
基坑降水工程的環境效應與評價方法
其中常數C＞0，表示對超出誤差ε的樣本的懲罰程度，ξi，
基坑降水工程的環境效應與評價方法
得到其對偶問題為：
基坑降水工程的環境效應與評價方法
基坑降水工程的環境效應與評價方法
基坑降水工程的環境效應與評價方法
可以得到回歸函數為：
其中，αi，
（2）支持向量機非線性回歸
以上討論的是線性問題，對於非線性問題，把輸入樣本xi通過ψ：x→H映射到高維特徵空間H（可能是無窮維）。當在特徵空間中構造最優超平面時，實際上只需進行內積運算，而這種內積運算是可以用原空間中的函數來實現的，沒有必要知道ψ的形式。因為只要核函數K（xi，xj）滿足Mercer條件，它就對應某一變換空間的內積即K（xi，xj）=ψ（i）·ψ（xj）。這一點提供了可能導致的「維數災難」問題解決方法。
由線性支持向量回歸可知，二次規劃的拉格朗日目標函數：
基坑降水工程的環境效應與評價方法
其對偶形式：
基坑降水工程的環境效應與評價方法
可以得到回歸函數為：
基坑降水工程的環境效應與評價方法
傳統的擬合方法通常是在線性方程後面加高階項。由此增加的可調參數增加了過擬合的風險。支持向量回歸用核函數即能作非線性回歸，達到了「升維」的目的，增加的可調參數很少，過擬合仍能控制。
『肆』 數據挖掘-支持向量機
支持向量機（support vector machine，SVM）是一種出色的分類技術，也可以用於回歸分析（SVR）。這種技術可以很好的應用於高維數據，避免維度災難等問題。
SVM有一個特點就是使用訓練集中的一個子集來表示決策邊界，該子集稱作 支持向量 。
SVM的核心目標是找到分類中的最大邊緣超平面，讓其作為決策邊界，那麼什麼是最大邊緣超平面呢？
但是可以發現，這種超平面有無數多個（圖中就能看到有好多個），如果有一些未知的點需要預測分類，那麼他們可能未必會被這些超平面完美的分隔：
以最下側的超平面為例，如果我們有未知的點按照藍色排布，那麼可以看到，最下側的這個超平面完全不能分類所有藍色點的「-」號，那麼如果它作為決策邊界，泛化能力就不是很好。
我們肯定要從這些超平面中選一個最合理的作為決策邊界，使得未知的點盡量的能被正確預測分類，那麼肯定是上圖中間的這個超平面最好了，我們目測就可以得到結果，因為 它離兩邊這些點的距離圍成的面積應該是最大的，而且兩邊的面積基本是差不多的 。（個人理解）所以應該能裝得下更多的未知點，也就能得到最好的泛化效果。
為了不用肉眼觀測，能量化的得到這個結果，我們可以定義 最大邊緣超平面 。
下圖中有兩個決策邊界， 和 ，其中每個決策邊界都對應著兩個超平面(記作 )。其中 是由 進行兩側平移，直到接觸到最近的一個訓練集的點停止，生成的，同理 也是。
我們把兩個超平面（同一個決策邊界生成的）之間的距離叫做分類器的邊緣，那麼下圖中，顯然 生成的兩個超平面距離應該是最大的， 就叫做 最大邊緣超平面 （ 雖然是決策邊界，但是決策邊界都是超平面）。
通常來說，較大邊緣的超平面具有更好的泛化誤差，如果邊緣比較小，那麼決策邊界的輕微擾動都可能對分類產生顯著影響。
SVM演算法的核心就是設計最大化決策邊界邊緣的分類器，以保證最壞情況下泛化誤差最小 。
假設有一個包含 個訓練樣本的二元分類問題，每個樣本表示為一個二元組 , 其中 ，對應於第i個樣本的屬性集（一個樣本有多個屬性/特徵）,設y有-1和1兩個類別，則一個 線性分類器的決策邊界 可以寫成如下形式：
其中的 為參數， 是法向量（垂直於決策邊界）的向量，代表著超平面的方向，而 代表超平面與原點之間的距離（可以用一次函數的公式來理解）。
為什麼 一定會垂直於決策邊界呢？我們設有兩個點 是決策邊界上的兩點，那麼有：
二者相減有：
因為 肯定是平行於決策邊界的，那麼為了保證內積為0， 肯定要垂直於決策邊界。
根據以上的決策邊界，則肯定有：
如果上方的點是1類，下方是-1類，則有：
如果我們能得到 ，那麼就可以用這個公式對未知點進行預測分類。代入公式，如果 就是1類，反之則為-1類。
接下來我們的任務就是如何求這兩個參數，首先，既然是求最大邊緣超平面，我們要把決策邊界的邊緣算出來。
根據上圖，考慮那些離決策邊界最近的方形和圓形，我們可以得到兩個平行的超平面表示如下：
決策邊界的邊緣就是這兩個超平面的距離。
參考上圖的 ，不難得出邊緣 為：
其中 是w的2范數。
很顯然，我們想要讓這個 最大，那麼就要讓 最小。
於是，接下來我們的求參數目標就明確了。
由於 肯定是非負的，我們可以改寫一下
這個式子，讓它變成求 的最小值。
既然要求最小值，就需要有另外一個約束條件，否則是沒辦法求的，我們來看之前總結的線性SVM分類器的公式：
由於 和 是決策邊界的兩個超平面，我們從上圖中可以看出，所有的點（除了這兩個超平面經過的點以外，經過的點是離決策邊界最近的點），都肯定有 和 。
我們把y引入進來，那麼這兩個式子就能合到一起寫為：
注意不要和之前總結的公式中的 弄混，那個條件是最終預測分類的公式，也就是表明只要在決策邊界的上方就可以進行分類，而現在的>=1是在已知訓練集的情況下求模型的參數。
綜合以上的式子，我們可以得到求參數的基本式：
目標函數是二次的，而約束在參數 和 上是線性的，因此這是一個凸優化問題， 不存在局部優化的問題 。
求這一套公式的最小值，需要用到 拉格朗日乘數法 ，這個我也不是很明白，就按照網路的定義往裡套：
雖然我們這里的附加條件是大於等於1的，不過不妨改寫一下試試，則有：
其中的 就是 拉格朗日乘子 ，理論上來說，拉格朗日乘子可以為任何值。
如果約束條件是=0的話，我們就可以直接對 和 求偏導數，讓他們等於0，就能求得參數。
但是目前條件並不是等於0的，而是大於等於0的。
處理不等式約束一種方法就是變換成一組等式約束，根據KKT條件，可以限制拉格朗日乘子飛赴，把之前的約束變換為：
該約束表明，除非訓練樣本滿足方程 ，否則拉格朗日乘子必須為0。
結合上面展示決策邊界和超平面的圖，我們可以想到，滿足這個方程的樣本，肯定都在決策邊界生成的兩個超平面上。這些樣本處的拉格朗日乘子肯定夠大於0，而其他樣本的拉格朗日乘子，肯定等於0，因此問題得到簡化。 因為參數的確定僅依賴於這些在超平面上的樣本。
這些在超平面上的樣本，被稱作 支持向量 ，這也就是支持向量機的命名緣由。
有了以上的修改後的約束，我們可以在 對 和 求偏導，並讓他們等於0.
我們已知，這個時候的 和 是有滿足條件的最優解的，把這兩個式子代入原公式，就能得到 的最小值（當然此時因為不知道拉格朗日乘子，我們是求不出來的），代入公式可得：
該函數叫做對偶拉格朗日函數。
用這個函數，就是把之前求w和b的公式變換成了求拉格朗日乘子的公式，同時需要注意，這個式子中是求拉格朗日對偶函數的最大化問題。
我們可以用二次規劃法或者SMO方法來求拉格朗日乘子。
二次規劃演算法比較通用，但是計算量比較大，SMO演算法的核心就是把復雜的式子變換成比較簡易的之後，用二次規劃來計算。
SMO的基本思路是：先固定 之外的所有參數，然後求 上的極值，由於存在約束 ，如果固定了 之外的其他變數，則能求出 。
那麼對偶函數里有兩個λ，我們就可以固定這兩個λ之外的參數，之後求解 。
其中有一個λ不滿足KKT條件，則目標函數就會在迭代後減小，違背程度越大，變數更新後導致的目標函數值就越大。 所以SMO先選取違背KKT條件最大的變數，第二個變數選擇使目標函數值見效最快的變數，使選取的兩個變數對應樣本之間的間隔最大。
然後可以變換為簡單的二次規劃問題：
找到一組λ後，就可以用原公式求得 的解，決策邊界可以表示為：
之後b可以通過 求解。
因為λ通過數值計算得到，因此可能存在誤差，則b可能不唯一。通常我們可以用b的 平均值 作為決策邊界的參數。
如圖所示，這組數據集有兩個特徵 和一個 標簽，我們要對其進行建模分類，可以得到有兩個拉格朗日乘子（支持向量上的），其他的均為0.
我們可以得到 有：
第一個 是針對 的參數，以此類推。
有了 ，可以求得 有：
可以根據兩個b求平均值，得到b=7.93，因此就能得到分類的模型。
如果需要做預測，把對應點的x向量代入到模型中，求得結果為1的話，就是方形類，其他為圓形類。
上面討論的模型最終都會生成一條直線，也就是線性的模型，那麼往往需要判斷非線性的如何處理呢，這里需要引入核函數的技術。
要把SVM應用到非線性決策邊界的數據集上，就要把數據集從原來的坐標空間x變換到新的坐標空間中。
我們假定存在一個合適的函數 來變化給定的數據集，那麼變換之後，我們就可以根據 來構建線性決策邊界（類似於換元法，回憶一下）。變換之後，線性決策邊界具有以下的形式：
根據線性SVM的參數計算公式，我們把公式裡面的 換成 ，即可求解。
不過這種方式往往會涉及到向量對的點積，計算比較麻煩，當特徵數較多時，可能會造成維度災難的問題，因此我們要引入核函數。
核函數是一種使用原屬性集計算變換後的空間中的相似度的方法，簡而言之就是，我們如果按照上一段說的演算法，則我們需要先計算 ，然後再計算參數，而我們運用核函數，可以直接計算oldsymbol{x}就可以達到變換屬性集的目的。
我們令 ，這樣就可以把映射的函數變成了原屬性集的計算。 就是核函數。
但是這個 一般我們是不知道的，因此我們要找尋幾種通用的函數，讓他們可以實現 的功能，以便模擬非線性的決策邊界。
這里我們引入一個 Mercer定理 ， 所有的核函數都必須滿足Mercer定理。
通常有如下幾種核函數：
我們也可以通過核函數的組合來形成新的核函數：
我們直到一般演算法都要防止過擬合，防止雜訊帶來的模型泛化能力下降，那麼SVM的防止過擬合方法就是軟邊緣。
此外，根據KKT條件，可以變換約束如下：
注意，上述三個式子中的 是非零的，當且僅當訓練樣本位於直線 上或者 。另外對於誤分類的訓練樣本， 都為0.
我們按照正常優化的演算法，對 , , 求偏導數，可以得到參數：
代入原公式，可以得到只包括拉格朗日乘子的對偶拉格朗日函數。
這個式子看上去跟不加軟邊緣的對偶函數是一樣的，但是約束是不同的。
軟邊緣的對偶函數約束為
之後就可以用二次規劃或者SOM求參數值了，從而得到模型。
這就是帶軟邊緣的SVM。
以上提到的都是二元分類的辦法，那麼多分類可以參考常用的多分類處理，用一對一方法，如果有多分類問題，我們可以分解為K（K-1）/2個二類分類器，每一個分類器用來區分一對類 。（注意這里的y都是單獨的類，不是一堆類別的集合）
當為 構建分類器時，其他不屬於這兩類的點都被忽略掉。
之後針對需要預測分類的樣本，我們用不同的分類器進行分類，最後進行投票，得到結果。
以上就是SVM（用於分類的支持向量機）的內容，最後看看該演算法的特點：
『伍』 支持向量機學習演算法
支持向量機學習演算法主要有以下五種：
（1）獲取學習樣本（xi，yi），i=1，2…，其中xi∈Rn，y∈任 ｛1，-1｝l，對樣本進行預處理；
（2）選擇進行非線性變換的核函數及對錯分（誤差）進行懲罰的懲罰因子c；
（3）形成二次優化問題用優化方法（如：Chuknlng演算法、內點演算法、SMO演算法）；
（4）獲得a，a*及b0的值，代入方程中，獲得分類或函數擬合的支持向量機；
（5）將需預測或分類的數據代入支持向量機方程中獲得結果。
基坑降水環境影響評價參數選取降水方式、岩土性質、水文地質邊界、基坑側壁狀態、邊載分布、後續使用年限、基礎型式、差異沉降8級，目標輸出模式對應4個級別：優等級（Ⅰ）、良好級（Ⅱ）、中等級（Ⅲ）、差級（Ⅳ）。
用一對多多類支持向量機水質分類法：有四類等級要劃分，於是在抽取訓練集的時候，分別抽取I所對應的向量作為正集，其餘所對應的向量作為負集；Ⅱ所對應的向量作為正集，其餘所對應的向量作為負集……，這四個訓練集分別進行訓練得到四個分類器。然後，利用這四個訓練結果文件對測試集分別進行測試，最後每個測試都有一個結果，最終的結果便是這四個值中最大的一個。
利用支持向量機進行基坑降水環境影響評價就是尋找影響基坑降水環境系統和孕災環境系統的指標和基坑降水環境影響等級之間的關系，可建立以下四個分類函數：
基坑降水工程的環境效應與評價方法
『陸』 支持向量機
支持向量機(Suport Vector Machine,常簡稱為SVM），是一個監督式學習的方式。支持向量機屬於一般化線性分類器，這類分類器的特點是能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機機也被稱為最大邊緣區分類器。
藍色和紅色的線圈出來的點就是所謂的支持向量，離分界線最近的點，如果去掉這些點，直線多半要改變位置。Classifier Boundary就是決策函數f(x)，在兩個類的中間。紅色和藍色之間的間隙就是我們要的最大化分類的間隙。
有拉格朗日乘子法的地方，必然是一個組合優化問題。比如
這是一個帶等式約束的優化問題，有目標值，有約束條件，不能直接求導。可以使用拉格朗日方法，把這個約束乘以一個系數加到目標函數中去，這樣相當與既考慮了原目標函數，也考慮了約束條件。然後分別對x求導等於0，
把它帶點菜約束條件中去，可以看到，2個變數兩個等式，最終可再帶回去求x就可以了。更高一層，帶有不等式的約束問題怎麼辦？需要用更一般化的拉格朗日乘子法，即KKT條件，來求解這個問題。
任何原始問題約束條件無非最多三種，等式約束，大於號約束，小於號約束，而這三種最終通過將約束方程簡化成兩類：約束方程等於0和約束方程小於0。
假設原始問題約束條件為下例所示：
那麼把約束條件變個樣子
現在拿到目標函數中去變成
那麼KKT條件的定理是什麼呢？就是如果一個優化問題在轉變成
其中g是不等式約束，h是等式約束。那麼KKT條件就是函數的最優值，它必定滿足下面條件：
這三個等式很好理解，重點是第三個句子不好理解，因為我們知道在約束條件變完或，所有的 ，且求和還要為0。那麼為什麼KKT的條件是這樣的呢？
某次的g(x)在為最優解起作用，那麼它的系數值（可以）不為0，如果某次g(x)沒有為下一次的最優解起作用，那麼它的系數就必須為0。
函數間隔
對於給定的訓練數據集T合超平面(w,b)，定義超平面(w,b)關於樣本點 的函數間隔為
函數間隔可以表示分類預測的正確性及確信度。但是選擇超平面時，只有函數間隔是不夠的，因子只要成比較改變 和b，超平面並沒有改變，但函數間隔卻擴大了。
幾何間隔
對於給定的訓練數據集T和超平面 ，定義超平面 關於樣本點 的幾何間隔為 ,其中 為 的 范數。
如果 ，那麼函數間隔和幾何間隔相等。如果超平面參數 成比例地改變（超平面沒有改變），函數間隔也成比例改變，而幾何間隔不變。
支持向量機的基本想法是求解能夠正確分訓練數據集並且幾何間隔最大的分離超平面。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個（等價於感知機），但是幾何間隔最大的分離超平面時唯一的。這里的間隔最大化被稱為硬間隔最大化。
間隔最大化的直觀解釋是：對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點（離超平面最近的點）也有足夠大的確信度將他們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。
下面考慮如何求一個幾何間隔最大的分離超平面，即最大間隔分離超平面。具體地，這個問題可以表示為下面的約束最優化問題：
即我們希望最大化超平面 關於訓練數據集的集合間隔 ，約束條件表示的是超平面 關於每個訓練樣本點的集合間隔至少是
考慮幾何間隔和函數間隔的關系式，可將這個問題改成為
函數間隔 並不影響最優化問題的解。事實上，假設將 成比例改變為 ,這時函數間隔變成 。函數間隔的改變對最優化問題的不等式約束沒有影響，對目標函數的優化也沒有影響，也就事實說，它產生一個等價的最優化問題。這樣，就可以取 。將 代入上面的最優化問題。注意最大化 和最小化 是一樣的。
於是就得到下面的線性可分支持向量機學習的最優化問題
這是一個凸二次規劃問題(contex quadratic programming)問題。
凸優問題是指約束最優化問題
其中，目標函數 和約束函數 都是 上的可連續可微的凸函數，約束函數 是 的仿射函數。當木匾函數是 是二次函數且約束函數 是仿射函數時，上述的凸優化問題成為凸二次規劃問題。
如果求出約束最優化問題的解 ，那麼就可以得出最大間隔分離超平面 及決策函數 ，即線性可分支持向量機模型。
為了求解線性可分支持向量機的最優化問題，將它作為原始最優化問題，應用到拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解，這就是線性可支持向量機的對偶演算法(al algorithm)。這樣做的優點，一是對偶問題往往根據容易求解；二是自然引入核函數，進而推廣到非線性可分類問題。
首先構建拉格朗日函數(Lagrange function)。為此，對每一個不等式約束引入拉格朗日乘子(Lagrange multiplier) 定義拉格朗日函數：
其中 為拉格朗日乘子向量。
根據拉格朗日對偶性，原始問題的對偶問題是極大極小問題
為了得到對偶函數問題的解，需要先求 對 的極小，再求 的極大
(1)求
將拉格朗日函數 分別對 求偏導數並令其等於0
將（1）代入拉格朗日函數，並利用(2)，即可得
即
(2)求 對 的極，即對偶問題
將公式(3)的目標函數由極大值轉換成求極小，就得到下面與之等價的對偶最優化問題
(3)解
假設 是對偶最優化問題的解，則存在下標使得 ，並求按下式求得原始最優化的解
根據KKT條件成立，即得
因此
,且至少存在一個 ，假設 ,那麼 不是原始問題的解,所以
那麼分離的超平面可以寫成
決策函數可以寫成
由此可以看出，分類決策函數只依賴於輸入x和訓練樣本輸入的內積，式（8）稱為線性可分支持向量機的對偶形式。
案例
訓練數據正例點是 ，負例點是 ，試用線性可分支持向量機
解：根據所給數據，對偶問題是
解這一優化問題，將 代入目標函數並記為
對 求偏導令其為0，易知 處取極值，該點不滿足約束條件 ，所以最小值應在邊界上達到。
當 ，當 ，於是
這樣, 對應的實例點 是支持向量，計算可得 ,
分離超平面為
分離決策函數為
線性可分問題的支持向量機學習方法，對線性不可分訓練數據是不適用的，因為這時上述方法中的不等式約束不能都成立。 線性不可分意味著不能滿足函數間隔大於等於1的約束條件 。為了解決這個問題，對每個樣本點 都引入一個鬆弛變數 ，使得函數間隔加上變數大於等於1，這樣約束條件變為
同時對於每個鬆弛變數 ，支付一個代價 ,目標函數由原來的 變成
C>0為懲罰參數，一般由應用問題解決，C值大時對誤分類的懲罰增大，C值小時對誤分類的懲罰減小。最小化木匾函數有2層意思：使得 盡量小，即間隔盡量大，同時使誤分類點的個數盡量小，C是調和兩者的系數
非線性分類問題是指通過非線性模型才能很好地進行分類的問題。非線性問題往往不好求解，希望通過線性分類問題的方法解決這個問題，所採取的方法是進行一個非線性變換，將非線性問題變成線性問題，通過解變換後的線性問題的方法求解原來的非線性問題。
用線性分類方法求解非線性分類問題分兩步：首先使用一個變換將原來空間的數據映射到新空間；然後在新空間里用線性分類學習方法從訓練數據中學習分類模型。核技巧就屬於這樣的方法。
設X是輸入空間（歐氏空間 的子集或離散集合），又設H為特徵向量（希伯而空間H），如果存在一個從X到H的映射
使得對所有 ，函數 滿足條件
則稱K(x,z)為核函數， 為映射函數， 。通常計算K(x,z)比較容易，而通話 計算K(x,z)並不容易。
是輸入空間到特徵空間的迎神，特徵空間一般是高維的，甚至是無窮維，可以看到，對於給定的核K(x,z)，特徵空間H和映射函數 的取法並不唯一，可以取不同的特徵空間，即便是在同一特徵空間也可以取不同的映射。
在對偶目標函數中的內積 可以用核函數 來代替，此時對偶問題的目標函數成為
這等價於經過映射函數 將原來的輸入空間變換到一個新的特徵空間，將輸入空間中的內積 變換成特徵空間中的內積 ，在新的特徵空間里從訓練樣本中學習線性支持向量機。學習是隱式地在特徵空間進行的，不需要顯式地定義特徵空間和營業日函數。在實際應用中，往往依賴領域知識直接選擇核函數。
對應的支持向量機是一個p次多項式分類器，在此情形下，分類決策函數成為
對應的支持向量機是高斯徑向基函數(radial basis function)分類器。在此情形下，分類決策函數成為
核函數不僅可以定義在歐式空間，還可以定義在離散數據的集合上。比如，字元串核函數是定義在字元串集合上的核函數。字元串核函數在文本分類、信息檢索、生物信息學等方面都有應用。
兩個字元串s和t上的字元串核函數是基於映射 的特徵空間中的內積：
字元串核函數 給出了字元串s和t中長度等於n的所有子串組成的特徵向量的餘弦相似度。直觀上看，兩個字元串相同的字串越多，它們就越相似，字元串核函數的值就越大。字元串核函數可以由動態規劃快速地計算。
支持向量機的學習問題可以形式化為求解凸二次規劃問題，這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以至無法使用。
序列最小最優化(sequential minimal optimization,SMO)演算法，是一種啟發式演算法，其基本思路是：如果所有變數的解都滿足此最優化問題的KKT條件，那麼這個最優化問題的解就得到了。因為KKT條件是該最優化問題的充分必要條件。否則，選擇兩個變數，固定其他變數，針對這兩個變數構建一個二次規劃問題。這個二次規劃問題的目標是使函數值變得更小。重要的是，這時子問題可以通過解析方法求解，這樣就可以大大提高整個演算法的計算速度。子問題有兩個變數，一個是違反KKT條件最嚴重的那一個，另一個由約束條件自動確定。如此，SMO演算法將原問題不斷分解為子問題並對子問題求解，進而達到求解原問題的目的。
假設兩個變數是 ，其他變數 是固定的，於是SNO的最優化問題的子問題可以寫成。
其中， 是常數，目標函數中省略不含 的常數項。
為了求解兩個變數的二次規劃問題，約束可以用二維空間中的圖形表示
不等式約束(7.3)使得 在盒子[0,C] [0,C]內，等式約束(7.2)使 在平行於盒子[0,C] [0,C]的對角線的直線上。因此要求的是目標函數在一條平行於對角線的線段上最優值。這使得兩個變數的最優化問題成為實質上的單變數最優化文圖，不訪考慮為變數 的最優化問題。
假設初始化可行解為 ，最優化解為 ，並且假設沿著約束方向未經剪輯時 的最優解為
由於 需滿足不等式約束(7.3)，所以最優值 的取值范圍必須滿足條件
其中，L與H是 所在對角線段端點的界，如果
如果 ，則
下面首先要求沿著約束方向未經剪輯即未考慮不等式約束(7.3)時 的最優解 ，然後在解決剪輯後 的解 ，我們用定理來描述這個結果
令
當i=1,2時， 為函數g(x)對輸入 的預測值與真實輸出 之差
定理 最優化問題(7.1)~(7.3)沿著約束方向未經剪輯時的解是
其中
是輸入空間到特徵空間的映射
經剪輯後的 的解是
由 是
『柒』 svm演算法是什麼
SVM演算法中文翻譯為支持向量機，它的英文全稱是Support Vector Machine。
之所以叫作支持向量機，是因為該演算法最終訓練出來的模型，由一些支持向量決定。所謂的支持向量，也就是能夠決定最終模型的向量。SVM演算法最初是用來解決二分類問題的，而在這個基礎上進行擴展，也能夠處理多分類問題以及回歸問題。
SVM演算法的歷史
早在1963 年，著名的前蘇聯統計學家弗拉基米爾·瓦普尼克在讀博士期間，就和他的同事阿列克謝·切爾沃寧基斯共同提出了支持向量機的概念。
但由於當時的國際環境影響，他們用俄文發表的論文，並沒有受到國際學術界的關注。直到 20 世紀 90 年代，瓦普尼克隨著移民潮來到美國，而後又發表了SVM 理論。此後，SVM 演算法才受到應有的重視。如今，SVM 演算法被稱為最好的監督學習演算法之一。