基本概念

劃分超平面：通過一個線性方程來分類訓練樣本

支持向量：使劃分超平面的劃分結(jié)果正確的距離超平面最近的訓練樣例

間隔： 兩個異類支持向量到超平面的距離之和

SVM（支持向量機）基本型

如何為這個分類學習器找到一個超平面

按照一貫的先限定模型，再用訓練樣本和算法確定參數(shù)的方法，我們先為劃分超平面限定一個模型

X是多個不同屬性的值構成的向量

W是為每個屬性賦予的權重值所構成的向量

b為位移項，決定了超平面與原點之間的距離

所以這個超平面可擴展為

在能將訓練樣本分類正確的前提下找到對訓練樣本局部擾動容忍性(最魯棒)的超平面

我們需要運算一個條件極值

當這個超平面使各類訓練樣本集到它的距離之和最大時，該超平面作為閾值最合適，但為了使樣本被正確分類我們還需要一個約束條件。

樣本空間中任意點到超平面的距離可由平面內(nèi)點到直線的距離公式推廣而來

分母為向量w的模

我們?nèi)藶橐?guī)定被劃分為正類的標志值為1，負類為-1

被劃分正確的訓練樣本滿足

(一個訓練集線性可分）

當我們令

兩個異類支持向量到超平面的距離和

所以該目標超平面滿足條件

為了方便計算，等價于

（svm的基本型）

求解這個基本型可得到滿足條件的參數(shù)w和b，即正確且唯一的模型

如何求解

二次規(guī)劃問題：目標函數(shù)二次項，限制條件一次項

而svm的基本型很明顯就是一個二次規(guī)劃問題，我們采用拉格朗日乘子法求解

因此我們可以得到關系式

把關系式代入原拉格朗日函數(shù)

因此求解原問題就變成了求解對偶問題

而原模型可根據(jù)關系式變形為

由于原問題有不等式約束，所以其對偶問題需要增加KKT條件

顯然，這個條件的解為

觀察剛剛得到的線性模型表達式可知，最終模型僅與支持向量有關。

通用的二次規(guī)劃算法不夠高效，在這里我們

采用SMO：先固定兩個乘子之外的所有參數(shù)，然后求這兩個乘子上的極值.為什么是兩個而不是一個，因為我們之前計算出 當原函數(shù)值最大時所有乘子和其對應標志值的乘積之和為0，所以如果每次選擇一個作為變量，則這個乘子可由其他已經(jīng)被固定的乘子導出。

如何選取這兩個參數(shù)

直觀來看，KKT 條件違背的程度越大，則 變量更新后可能導致的目標函數(shù)值減幅越大.也就是逼近解的速度越快，第二個變量應選擇一個使目標函數(shù)值減小最快的變量，但 由于比較各變量所對應的目標函數(shù)值減幅的復雜度過高，因此 SMO 采用了一 個啟發(fā)式:使選取的兩變量所對應樣本之間的間隔最大. 種直觀的解釋是，這 樣的兩個變量有很大的差別，與對兩個相似的變量進行更新相比，對它們進行 更新會帶給目標函數(shù)值更大的變化.

用約束條件

消去其中一個變量，得到一個關于ai的單變量二次規(guī)劃問題，求解得到ai aj

對于b,我們使用所有樣本求解的平均值（注意這里標志值y只能是1，-1）所以最終b的表達式為

即可確定目標參數(shù)及超平面線性方程。

處理非線性問題

如果樣本空間非線性可分，則svm基本型的限制條件不成立

將樣本高維映射可使樣本在這個特征空間內(nèi)線性可分(降維打擊）

例如：

映射后的模型可表示為

例如：

而我們要找的超平面則相應的也從二維變成五維

針對處理非線性問題改造svm基本型

同理可得其對偶問題

為了簡化運算，我們用核函數(shù)替換

核函數(shù):用一個函數(shù)通過低維的向量值直接計算出高維向量的內(nèi)積 而不需要知道高維向量的具體形態(tài)

核函數(shù)使高維映射又變回低維運算

怎么確定核函數(shù)?

核函數(shù)成立的充要條件：

1.可替換

2.半正定

只要一個對稱函數(shù)所對應的核矩陣半正定，就能作為核函數(shù)使用

常用的核函數(shù)

軟間隔與正則化

由于在現(xiàn)實任務中往往很難確定合適的核函數(shù)使得訓練樣本在特征空間中線性可分;退一步說即使恰好找到了 某個核函數(shù)使訓練集在特征空間中線性可分，也很難斷定這個貌似線性可分的結(jié)果不是由于過擬合所造成的

所以我們允許支持向量機在一些樣本上出錯.

這種不要求所有樣本被正確分類的向量機形式被稱為軟間隔，即不滿足約束

因此我們原來構造的拉格朗日函數(shù)就不適用，但為了使優(yōu)化目標變?yōu)?在最大化間隔的同時，不滿足約束的樣本也要盡可能少，我們將原來的條件函數(shù)映射成一個損失函數(shù)，使其大小與不被正確分類的標志數(shù)量成正比

因此優(yōu)化目標可寫為

顯然，求解該函數(shù)需要綜合考慮間隔大，出錯少兩個條件，分別稱為結(jié)構風險(間隔）和經(jīng)驗風險（誤差）

為了易求解，我們通常采用數(shù)學性質(zhì)更好的函數(shù)替代，稱為"替代損失"

被劃分錯誤的樣本距離超平面越遠 損失函數(shù)的自變量z越小，1-z越大

這個約束條件由損失函數(shù)的定義推導而來

這同樣是一個二次規(guī)劃問題，同理可得到它的對偶問題及KKT條件

由KKT條件用同樣的方法可推出軟間隔支持向量機的 最終模型僅與支持向量有關。

同樣用smo求解得到超平面

優(yōu)化目標由間隔大小和誤差程度構成，可寫為更一般的形式

稱為正則化問題

支持向量回歸

假設我們能容忍 f(x) 與 y之間最多有 一定 的偏差，即僅當 f(x) 與 y 之間的差別絕對值大于這個值時才計算損失

用不敏感損失函數(shù)衡量損失程度，SVR 問題可形式化為

引入松弛變量

同樣用拉格朗日乘子法得到對偶問題和其KKT條件

由求偏導得到的關系式可將超平面擴展為

考慮上面提到的非線性可分情況下的特征映射形式，則表示為

總結(jié)

這章討論了在4種情況下如何確定支持向量機

1.硬間隔 即樣本訓練集不允許有誤差

首先確定兩個條件，1）被分類正確2）間隔最大，于是得到一個條件極值的運算，接著用拉格朗日乘子法得到關系式，變形成對對偶問題的求解，加入KKT條件，最后用SMO對對偶問題求解。

2.線性不可分 即無法用一個線性模型對訓練樣本進行分類

用高維映射的方法解決這個問題，將樣本從原始空間映射到一個更高維的特征空間，使其線性可分，為了簡化計算我們引入核函數(shù)，用以代替高維特征空間中樣本的內(nèi)積。只要一個對稱函數(shù)所對應的核矩陣半正定，就能作為核函數(shù)使用。

3. 軟間隔 即允許部分樣本不滿足約束（不被正確分類）

在這個問題上引入損失函數(shù)以衡量樣本不滿足約束的程度，綜合考慮兩個維度進行優(yōu)化（結(jié)構風險和經(jīng)驗風險），接著便用和解決硬間隔一樣的推算方法得到軟間隔問題的超平面，將軟間隔的目標優(yōu)化寫為更一般的形式則得到正則化問題。

4.回歸問題

有別于傳統(tǒng)回歸模型，支持向量回歸假設我們能容忍一定的偏差，在這個偏差之外才被認為錯誤，因此在構造目標優(yōu)化時引入不敏感損失函數(shù)。接著又是一樣的推算方法得到SVR的解型，同樣的在考慮特征映射時引入核函數(shù)。