上一章為大家介紹了支持向量機（Support Vector Machine，SVM）的理論基礎—統計學習理論的一些重要知識點，本章正式為大家介紹支持向量機算法。
支持向量機是在統計學習理論的VC維和結構風險最小化原理的基礎上發展起來的一種新的機器學習方法。SVM根據有限樣本的信息在模型的複雜性（即對特定樣本的學習精度）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折中，以期獲得最好的推廣能力。
結構風險最小化(Structural Risk Minimization，SRM）
統計學習理論從VC維的概念出發，推導出關於經驗風險和期望風險（真實風險的期望風險）之間關係的重要結論，稱為泛化誤差界，統計學習理論給出了以下估計真實風險的不等式。
估計真實風險的不等式
其中R(w)是真實風險，Remp(w)表示經驗風險，Φ(n/h)稱為置信風險（置信範圍）；n代表樣本數量，h是函數集合的VC維，Φ是遞減函數。
上述不等式（定理）說明，學習機器的期望風險由兩部分組成：
第一部分是經驗風險（學習誤差引起的損失），依賴於預測函數的選擇
第二部分稱為置信範圍，是關於函數集VC維h的增函數
顯然，如果n/h較大，則期望風險值由經驗風險值決定，此時為了最小化期望風險，我們只需最小化經驗風險即可；
相反，如果n/h較小，經驗風險最小並不能保證期望風險一定最小，此時我們必須同時考慮不等式右端的兩項之和，稱為結構風險。
結構風險最小化
一般的學習方法(如神經網絡)是基於 Remp(w) 最小，滿足對已有訓練數據的最佳擬和，在理論上可以通過增加算法（如神經網絡）的規模使得Remp(w) 不斷降低以至為0
但是,這樣使得算法（神經網絡）的複雜度增加，VC維h增加，從而Φ(n/h)增大，導致實際風險R(w)增加，這就是學習算法的過擬合(Overfitting).
大家如果想更好地理解結構風險最小化原則，可以先看一下前一篇文章《 第十章 支持向量機理論基礎》，裡面有一些關於統計學習理論主要知識的比較詳細的介紹。
分類問題的數學表示
2維空間上的分類問題⇨n維空間上的分類問題。
分類問題的數學表示
分類問題的學習方法
分類問題的學習方法
SVM分類問題大致有三種：線性可分問題、近似線性可分問題、線性不可分問題。
線性可分情形：最大間隔原理
對於線性可分的情況，l_到l0和l+到l0的距離和，利用兩條平行直線間的距離公式很容易得到距離（間隔）=2/||w||，最大化間隔就是求w的最小值。S.T.說明必須在滿足約束條件（正確分類）的前提下求w的最小值。
線性可分情形
模型求解：
原始問題是一個典型的線性約束的凸二次規劃問題，模型求解主要用到了運籌學裡面的方法，在這裡就不仔細展開了，求解的思想主要是：
第一步，在原始問題中引入拉格朗日乘子轉化為無約束問題（拉格朗日乘子法）;
第二步，根據最優化的一階條件將原始問題轉化為對偶問題;
第三步，根據KKT條件得到求得最優解時應滿足的條件.
KKT條件是拉格朗日乘子法的泛化，在有等式約束時使用拉格朗日乘子法，在有不等約束時使用KKT條件
支持向量：
在兩類樣本中離最優分類超平面最近且在平行於最優分類超平面的平面l_,l+上的訓練樣本就叫做支持向量，理解為它們支撐起了超平面l_和l+，所以稱為支持向量，數學含義如下。
支持向量
近似線性可分情形
近似線性可分情形
引入鬆弛變量
引入懲罰函數
即，C代表了經驗風險與置信風險的折中。
線性不可分情形
把尋找低維空間非線性的“最大超曲面”問題轉化為在高維空間中求解線性的“最大間隔平面”問題。即，把非線性可分的樣本映射到高維空間，使樣本線性可分。
線性不可分情形
線性不可分模型
線性不可分模型
模型（3）的求解，必須知道非線性映射Ф的具體形式，但實際工作上，給出Ф的具體形式往往是非常困難的。
線性不可分問題的求解
線性不可分問題的求解
核函數K(xi,xj)
K(xi,xj)=(Ф(xi),Ф(xj))=Ф(xi)*Ф(xj)是樣本xi,xj在特徵空間中的內積，稱為輸入空間X上的核函數。
對非線性問題, 可以通過非線性變換轉化為某個高維空間中的線性問題, 在變換空間求最優分類面. 這種變換可能比較複雜, 因此這種思路在一般情況下不易實現
為了避免從低維空間到高維空間可能帶來的維數災難問題，避免進行高維的內積運算
綜上考慮引入核函數。
利用核函數代替向高維空間的非線性映射，並且不需要知道映射函數
在最優分類面中採用適當的核函數就可以實現某一非線性變換後的線性分類,而計算複雜度卻沒有增加
通過計算K(xi,xj)的值可以避免高維空間的內積運算，這種內積運算可通過定義在原空間中的核函數來實現, 甚至不必知道變換的形式
SVM中不同的核函數將形成不同的算法，主要的核函數有三類：
SVM常見的核函數