6。1 間隔與支援向量

開倍速觀看影片之後，對課本所說的會更加了解。支援向量機講解：https：//www。bilibili。com/video/av77638697？p=6

給定一個數據集D={（x 1，y 1），（x 2，y 2），……，（x m，y m）}，y i∈{-1，+1}。對於分類學習來說，最基本的想法就是找出一個超平面，能夠把不同類別的樣本分開。

資料集 對於上圖的分類，我們會想用一個超平面劃分兩類，

超平面劃分兩類 可以看出，劃分兩類的超平面有多種，那我們應該選擇哪一種呢？直覺上，我們會選擇超平面1（紅色線）。因為該超平面對訓練樣本區域性擾動的“容忍性”好。如果選擇超平面3，當有一個正例在超平面3的上方之外的話，那麼就會分類錯誤，超平面3就不容忍這個正例，所以說超平面1的容忍性好。換句話說，就是超平面1所產生的分類結果是最魯棒的，就是對新樣例的泛化能力強。

在樣本空間中，超平面的線性方程如下：

超平面線性方程其中w = （w 1，w 2，……，w d）為法向量，決定了

超平面的方向

；b為位移項（截距），決定了

超平面與原點

之間的距離。劃分超平面最終由w和b確定，記為（w，b）。樣本空間中樣本點到超平面的距離如下：

點到平面的距離公式假設超平面（w，b）能將訓練樣本正確分類，則對於（x i，y i）∈D，若y i=1，則w T x i+b>0；若y i=-1，則有w T x i+b <>

由於上面這個轉換詳解過於複雜，可以看影片詳解，這裡不作說明。對於距離超平面最近的樣本點，我們稱為

"支援向量"

。兩個

異類支援向量到超平面的距離之和

稱為間隔，如下

間隔

支援向量與間隔 為了儘可能劃分類別正確，我們可以轉化為找到具有

"最大間隔"

的超平面，即找到w和b，使得γ最大，即

而最大化間隔，就需要最大化||w||-1，相當於最小化||w||2，則目標可以重寫為

這就是支援向量機（SVM）的基本模型。6。2 對偶問題

原始問題與對偶問題以及KKT條件的關係解釋https：//blog。csdn。net/fkyyly/article/details/86488582

原始問題與對偶問題的影片講解：https：//www。bilibili。com/video/av77638697？p=11

原始問題轉化為對偶問題：https：//www。bilibili。com/video/av77638697？p=12上面這三個連結對於對偶問題有較好的解釋。

原始問題

對於上式，是一個凸函式二次規劃的問題。我們可以對上式使用

拉格朗日乘子法

得到原始問題的對偶問題。

對每個約束條件新增拉格朗日乘子αi，且αi≥0，則該問題的最佳化函式為

先求最佳化函式對於w和b的極小值即，對w和b求偏導，令偏導為0，有

對w和b求偏導 接著將w代入最佳化函式得到

可以看出，對w和b求偏導之後代入，再考慮對b求偏導得到的約束，就得到了對偶問題

得到對偶問題 得到最佳化函式只剩下α作為引數，只要求最佳化函式的極大值，就可以求出α，進而求出w和b，再代入我們的模型，就可以了，假設我們的模型是f（x） = w T x+ b，則

上述過程要滿足KKT條件

KKT條件 對於對偶問題，我們該如何求解α呢？我們用的就是

SMO演算法

SMO基本思路

：先固定αi之外的所有引數，然後求αi上的極值。

SMO步驟:

每次選擇兩個變數αi和αj，並固定其他引數，分別對αi和αj求偏導為0，得到αi和αj，若符合約束條件就不用算，若不符合約束條件，再更新αi和αj，代入對偶問題的目標函式，直到符合條件。

SMO步驟 可以看出，SMO固定了其他的引數，僅僅考慮αi和αj，因此對偶問題中的約束條件可以重寫為

約束條件重寫 其中的c

c的含義 透過重寫之後的約束條件，我們可以將對偶問題中的目標函式的αj消去，只剩下αi一個變數，這時我們的約束只有KKT裡面的αi≥0，對αi求導為0，得到αi，再求出a j，透過這樣子我們可以更高效的求出a i和a j。求出α之後，代入

就可以計算出w了。那麼b該如何計算呢？

使用所有支援向量求解的平均值

設支援向量表示為（x s，y s）設S= { i | αi>0，i = 1，2，3……，m}為所有支援向量的下標集。

b的求解公式

支援向量機的程式碼實現：https：//blog。csdn。net/qq_43608884/article/details/88658216

6。3 核函式

在前面的討論中，我們假設訓練樣本都是線性可分的，上述SVM也只是在處理線性可分的資料。事實上，我們很多資料都是非線性可分的。

對於非線性的情況，SVM 的處理方法是選擇一個

核函式 κ(⋅,⋅)

，透過將資料對映φ到高維空間，來解決在原始空間中線性不可分的問題。

具體來說，線上性不可分的情況下，支援向量機首先在低維空間中完成計算，然後透過核函式將輸入空間對映到高維特徵空間，最終在高維特徵空間中構造出最優分離超平面，從而把平面上本身不好分的非線性資料分開。如圖所示，一堆資料在二維空間無法劃分，從而對映到三維空間裡劃分：

類似，原始問題為

原始問題 對偶問題為

對偶問題 其中，紅色方框裡面的式子，表示的是樣本x i和x j對映到特徵空間之後的內積，當屬性空間的維數很大時，直接計算內積是很困難的，因此，有

即x i和x j在

屬性空間

中的內積等於在

原始樣本空間

中透過函式K（·，·）計算的結果。這裡的

函式K(·,·)，就是核函式

。於是，對偶問題可以重寫為

對偶問題重寫 最終可以得到

常用的核函式K（·，·）有以下幾種常用核函式

關於核函式，有下面三個關係：

若k 1和k 2為核函式，則對於任意正數γ1和γ2，其線性組合γ1 k 1+γ2 k 2也為核函式 若k 1和k 2為核函式，則核函式的直積也為核函式

核函式的直積 若k 1和k 2為核函式，則對於任意函式g（x）

也是核函式對文字資料通常採用線性核，情況不明時可先嚐試高斯核。高斯核函式

支援向量機的非線性程式碼實現https：//blog。csdn。net/kt513226724/article/details/80413018

6。4 軟間隔與正則化

在上述中的支援向量機中，我們要求所有樣本都要滿足約束，即都被劃分正確，這叫做

"硬間隔"

。可實際上，很難確定合適的核函式使得樣本在特種空間中線性可分，不允許分類錯誤的樣本。緩解這一個問題的辦法就是允許支援向量機在一些樣本上出錯，為此，引入

"軟間隔"

。

軟間隔 軟間隔允許某些樣本不滿足約束條件，也要讓這些樣本很少。則最佳化目標可以寫為

其中C是一個常數，可以理解為問題正則化時加入的引數。當C趨於無窮大時，所有樣本均滿足原來硬間隔的約束條件；當C取有限值時，允許一些樣本不滿足約束。而式子中的

損失函式然而

"0/1損失函式"

的不可微、不連續，數學性質較差，於是我們可以用其他函式替代損失函式，稱為

"替代損失函式"

，通常數學性質較好，通常有以下三種替代損失函式：

替代損失函式

下面我們使用hinge損失函式來最佳化目標。

首先對訓練集的每個樣本（x i，y i）引入一個

鬆弛變數

ξi≥0，使函式間隔加上鬆弛變數大於等於1，也就是說，約束條件變為

加入鬆弛變數之後的約束條件 對比硬間隔最大化，可以看到我們對樣本到超平面的函式距離的要求放鬆了，之前是一定要大於等於1，現在只需要加上一個大於等於0的鬆弛變數能大於等於1就可以了。當引入了ξ之後，也是需要成本的，所以硬間隔到軟間隔的最佳化目標變為

硬間隔到軟間隔接著我們對軟間隔支援向量機進行目標函式的最佳化。透過拉格朗日乘子法得到

軟間隔的拉格朗日函式 對w、b和ξ求偏導為0，得到

將他們代入拉格朗日函式

代入過程 此時我們就得到了，原始問題的對偶問題，

對偶問題 接著用SMO演算法算出α，就可以得到w，然後再計算b，與硬間隔類似。對於上述過程，也需要滿足KKT條件

軟間隔支援向量機的KKT條件 對於訓練樣本（x i，y i），有1）若α=0，那麼y i（w T x i+b）-1≥0，即樣本在間隔邊界之外，即被正確分類。2）若03）若α=C，則μi=0，該樣本點是有可能正確分類、也有可能分類錯誤，此時考試ξi。① 如果0≤ξi≤1，那麼樣本點在超平面和間隔邊界之間，但是被正確分類。② 如果ξi=1，那麼樣本點在超平面上，無法被正確分類。③ 如果ξi＞1，樣本點被分類錯誤。

對於，允許誤差的最佳化目標函式，我們可以寫為更加一般的形式

Ω（f）稱為“結構風險”，用於描述模型f的某些性質；第二項的Σm l（f（x i），y i）稱為“經驗風險”，用於描述模型與訓練資料的契合度。C稱為正則化常數，用於對結構風險和經驗風險進行折中。上式被稱為“正則化問題”，Ω（f）稱為正則化項，C為正則化常數。6。5 支援向量迴歸（SVR）

上面講到的SVM是用於

分類任務

的，而對於

迴歸任務

，我們使用SVR。

SVM分類，就是找到一個平面，讓兩個分類集合的支援向量或者所有的資料離分類平面最遠；SVR迴歸，就是找到一個迴歸平面，讓一個集合的所有資料到該平面的距離最近。

SVR假設f（x）與y之間最多有ε的偏差，即以f（x）為中心，允許f（x）+ε和f（x）-ε的誤差，構建一個2ε的間隔。

SVR SVR的形式如下

SVR原始問題

不敏感損失函式 由於間隔帶的兩側鬆弛程度有所不同，所有引入鬆弛變數ξi和ξ^i，則原始問題重寫為

接著我們要求對偶問題。首先引入拉格朗日乘子，可以得到拉格朗日函式

令L對w、b、ξi、ξ^i的偏導為0，可得到

將它們代入L，可以得到對偶問題

SVR的對偶問題 上述過程中，要滿足KKT條件

KKT條件

將上面求得的w代入我們原來的模型f（x） = w T x+ b，得到SVR的解

由KKT可以看出，對每個樣本（x i，y i）有：1）（C - αi）ξi=0 ，2）αi（f（x i）- y i-ε - ξi）=0。於是透過SMO演算法得到αi之後，若0b 實際上，我們更常用的是：選取所有滿足0 <>SVR對映形式

6。6 核方法

對於SVM和SVR，它們的最佳化問題都是類似下面的式子

而SVR和SVM學得的模型總能表示為核函式K（x，x i）的線性組合，所以上式的模型也可以寫成為核函式的線性組合

上式模型的解 對於上面這個結論，就是

"表示定理"

表示定理人們基於核函式的學習方法，稱為

"核方法"

。最常見的，是透過引入核函式來將線性學習擴充套件為非線性。下面以“核線性判別分析”（KLDA）為例，演示如何引入核函式進行非線性擴充套件。

我們難以直到對映φ的具體形式，因此使用核函式K（x，x i）= φ（x i）Tφ（x）來表達對映和特徵空間F。把J（w）作為式子6。57中的損失函式，令Ω=0，有

由表示定理得，

再由式6。59得