支持向量機SVM（2）線性支持向量機字逗、軟間隔最大化

1 原理

1）背景

線性可分支持向量機基于硬間隔最大化鸯乃，所謂硬間隔最大化鲸阻，我理解的就是指這個間隔最大化是被嚴格要求的，不允許任何例外的樣本點跨過間隔邊界缨睡，因此這種方法是不適用于線性不可分數(shù)據(jù)的鸟悴，因為約束條件 $y_i(w^Tx_i+b)\geq1$ 是不能完全成立的，這樣一來線性可分支持向量機的適用性就大大降低了奖年，因此我們需要線性支持向量機和軟間隔最大化细诸。

2）原理

首先我們需要定義這里的線性不可分的含義，這里的線性不可分并不是指完全的線性不可分陋守，而是指一批訓(xùn)練數(shù)據(jù)中有少部分的異常點震贵，如果剔除這些異常點，剩下的大部分訓(xùn)練數(shù)據(jù)是線性可分的水评，即相當(dāng)于是本來線性可分的數(shù)據(jù)中加入了一些噪音猩系，噪音可能產(chǎn)生下圖兩種負面影響：

根據(jù)背景中的分析我們知道，對于這樣的數(shù)據(jù)中燥，線性可分支持向量機的問題是約束 $y_i(w^Tx_i+b)\geq1$ 太“硬”寇甸，太嚴格，數(shù)據(jù)無法滿足，那么如果我們把約束放寬松一點呢拿霉？我們把約束變?yōu)椋?/p>

$y_i(w^Tx_i+b)\geq1-\xi_i吟秩，\xi_i\geq 0$

式中， $\xi_i$ 是松弛變量绽淘，顧名思義它將約束條件變得寬松了涵防，這樣那些異常點也可以滿足約束了，但是其 $\xi_i$ 會比較大收恢，也就是要多“寬松”一些武学，如下圖所示，松弛變量表示了異常點到間隔邊界的函數(shù)間隔：

問題是伦意，約束變得寬松了怎么能保證分類的效果呢火窒？要知道支持向量機的優(yōu)勢就是其嚴格的約束使得分類超平面與兩個類別間隔最大且相等，為了彌補約束放松的缺點驮肉，引入“代價” $\xi_i$ 熏矿，即放松了多少約束，就有承受多大的代價离钝，因此目標(biāo)函數(shù)變?yōu)椋?/p>

$\min_{w,b,\xi}\;\frac{1}{2}||w||_2^2+C\sum_{i=1}^{m}\xi_i$

$s.t. \; y_i(w^Tx_i+b)\geq1-\xi_i票编，\;\xi_i\geq 0 ,\;\; i=1,2,...,m$

式中， $C>0$ 是懲罰參數(shù)卵渴， $C$ 越大對異常點的懲罰越大慧域，約束越嚴格， $C$ 的具體取值由實際應(yīng)用決定浪读。這里的目標(biāo)函數(shù)既要使 $\frac{1}{2}||w||_2^2$ 盡量小即間隔盡量大昔榴，又要使?jié)M足約束的樣本盡量多即誤分類點盡量少，這兩個目標(biāo)使互相矛盾的碘橘，由 $C$ 來控制二者的強弱關(guān)系互订。

綜上所述，對于有噪音的線性不可分數(shù)據(jù)痘拆，我們選擇放松其約束仰禽，相對于基于嚴格約束的硬間隔最大化來說，這種做法稱為軟間隔最大化纺蛆，解決這種線性不可分數(shù)據(jù)的分類問題吐葵，基于軟間隔最大化的支持向量機稱為線性支持向量機（看名字也能感受到線性支持向量機應(yīng)該包含線性可分支持向量機，線性可分支持向量機是松弛變量都為0的線性支持向量機特例）桥氏。

線性支持向量機模型：

$f(x)=sign(w^*x+b^*)$

$w^*x+b^*=0$ 為決策超平面折联，線性支持向量機看起來與線性可分支持向量機一樣，只是在決策超平面的計算思路上有些不同识颊。

2 支持向量機模型求解

1）目標(biāo)函數(shù)

$\min_{w,b,\xi}\;\frac{1}{2}||w||_2^2+C\sum_{i=1}^{m}\xi_i$

$s.t. \; y_i(w^Tx_i+b)\geq1-\xi_i，\;\xi_i\geq 0 , i=1,2,...,m$

2）轉(zhuǎn)化為對偶問題

轉(zhuǎn)化過程與線性可分支持向量機是一樣的，首先是拉格朗日乘子法：

$L(w,b,\xi,\lambda,\mu) = \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum\limits_{i=1}^{m}\mu_i\xi_i$

目標(biāo)函數(shù)的優(yōu)化轉(zhuǎn)變?yōu)椋?/p>

$\min_{w,b,\xi}\; \max_{\lambda,\mu} L(w,b,\xi,\lambda,\mu)$

通過拉格朗日對偶將其轉(zhuǎn)化為等價的對偶問題：

$\max_{\lambda,\mu}\;\min_{w,b,\xi} L(w,b,\xi,\lambda,\mu)$

通過求導(dǎo)求里面的極小值部分：

$\frac{\partial L}{\partial w} = 0 \;\rightarrow w-{m}\lambda_iy_ix_i=0\;\rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \;\rightarrow \sum_{i=1}^m\lambda_iy_i=0$

$\frac{\partial L}{\partial \xi_i} = 0 \;\rightarrow C-\lambda_i-\mu_i=0$

代入原式可得：

$\begin{align} J(\lambda,\mu)&=\min_{w,b}\; L(w,b,\xi,\lambda,\mu) \\& = \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum\limits_{i=1}^{m}\mu_i\xi_i 　 \\&= \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] + \sum\limits_{i=1}^{m}\lambda_i\xi_i \\& = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1] \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - w^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - \sum\limits_{i=1}^{m}\lambda_iy_ib + \sum\limits_{i=1}^{m}\lambda_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\lambda_iy_ix_i^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - b\sum\limits_{i=1}^{m}\lambda_iy_i + \sum\limits_{i=1}^{m}\lambda_i \\& = -\frac{1}{2}\sum\limits_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j + \sum\limits_{i=1}^{m}\lambda_i \\& = \sum\limits_{i=1}^{m}\lambda_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\lambda_i\lambda_jy_iy_jx_i^Tx_j \end{align}$

以上這些推導(dǎo)的每個步驟處理的原理就不細說了祥款，想弄明白的話可以看上一篇線性可分支持向量機

$J(\lambda,\mu)$ 完全是關(guān)于參數(shù) $\lambda,\mu$ 的函數(shù)清笨，因此：
$\max_{\lambda,\mu}\;\min_{w,b,\xi} L(w,b,\xi,\lambda,\mu) =\max_{\lambda,\mu}\;J(\lambda,\mu)=\max_{\lambda}\;\sum_{i=1}^{m}\lambda_i-\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j$

$s.t. \sum_i^m \lambda_iy_i=0,\;C-\lambda_i-\mu_i=0,\;\lambda_i\geq0,\;\mu_i\geq0$

轉(zhuǎn)化為：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;0\leq\lambda_i\leq C$

與線性可分支持向量機基本上是一樣的，只是約束不同刃跛，求出上式取得極小值時對應(yīng)的 $\lambda$ 向量就可以求出 $w$ 和 $b$ 了抠艾，這里同樣需要用到SMO算法來求 $\lambda$ 。

3）線性支持向量機的算法過程

輸入：樣本 $T=(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ 桨昙， $x$ 為 $n$ 維特征向量检号， $y\in[+1,-1]$ ；

輸出： $w,b$ 蛙酪，支持向量機模型 $f(x)=sign(w^Tx+b)$ 齐苛。

確定懲罰系數(shù) $C>0$ ，確定目標(biāo)函數(shù)：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\;0\leq\lambda_i\leq C$

使用SMO優(yōu)化目標(biāo)函數(shù)桂塞，得到對應(yīng)的 $λ^*$ 凹蜂；

根據(jù) $λ^*$ 找到樣本中的共k個支持向量，計算參數(shù) $w,b$ ：

$w^* = \sum_{i=1}^{m}λ_i^*y_ix_i$

$b^*=\frac{1}{k}\sum_i^k (y_i-w^Tx_i)$

得到支持向量機模型 $f(x)=sign(w^{*T}x+b^*)$ 阁危。

注意：
（1）第三步計算參數(shù) $b$ 的公式

這里的求b公式看起來跟線性可分支持向量是一樣的玛痊，其實是有區(qū)別的，在上一篇中我們說過線性可分支持向量機的 $b$ 是存在且唯一的狂打，而線性支持向量機的 $b$ 不唯一擂煞，正是因為這里的 $b$ 是考慮了松弛變量 $ξ_i$ 的，實際上求出來 $b_i=b^0+ξ_i$ 趴乡，這就是為什么 $b$ 值有多個对省，因為不同支持向量的 $ξ_i$ 是不相等的。

（2）第三步需要找的樣本中的支持向量浙宜，怎么判斷樣本點是不是支持向量呢官辽？

我們知道，所謂支持向量粟瞬，就是最靠近分類超平面的同仆，能夠影響我們確定分類超平面的樣本點。

我們從代數(shù)上理解裙品，在計算超平面參數(shù) $w$ 的那個式子可知俗批，只要使 $λ_i^*>0$ 的樣本點就會對超平面參數(shù) $w$ 產(chǎn)生影響，即為支持向量市怎，由KKT條件知岁忘， $λ_i(w^Tx_i+b-1+\xi_i)=0$ ，故此時 $w^Tx_i+b-1+\xi_i=0$ 区匠，KKT條件中還有一條 $\mu_i\xi_i=0$ 干像，所以可知：

$0<λ_i<C$ 時帅腌， $\mu_i=C-λ_i>0$ ，故 $\xi_i=0$ 麻汰，支持向量 $i$ 不需要松弛變量速客，即支持向量在間隔邊界上，如下圖 $x_1$ 五鲫；
$λ_i=C$ 時溺职， $\mu_i=C-λ_i=0$ ，故 $\xi_i>0$ 位喂，支持向量 $i$ 在間隔邊界上之外浪耘，如果 $1>\xi_i>0$ ，則支持向量 $i$ 還在分類邊界與間隔邊界之間塑崖，還可以被正確分類七冲，如下圖 $x_2$ ；如果 $\xi_i>1$ 弃舒，則到了分類邊界另一側(cè)癞埠，被錯誤分類了，如下圖 $x_3$ 聋呢。

3 從合頁損失函數(shù)理解線性支持向量機

以上我們討論的支持向量機的目標(biāo)函數(shù)都是從間隔最大化的角度來理解的苗踪，我們還可以通過合頁損失函數(shù)的角度來理解其目標(biāo)函數(shù)：

$\min_{w, b}\;[1-y_i(w \cdot x + b)]_{+} + \lambda ||w||^2$

$[z]_+=\begin{cases} z,\; z>0 \\ \\ 0 ,\;z\leq 0 \end{cases}$

式中， $[1-y_i(w \cdot x + b)]_{+}$ 是經(jīng)驗風(fēng)險削锰，成為稱為合頁損失函數(shù)（hinge loss function）通铲； $\lambda ||w||^2$ 是L2范數(shù)表示的結(jié)構(gòu)風(fēng)險，也就是正則項器贩。損失函數(shù) $[1-y_i(w \cdot x + b)]_{+}$ 在樣本點 $(x_i,y_i)$ 被正確分類且函數(shù)間隔大于1時值為0颅夺，否則損失函數(shù)值為 $1-y_i(w \cdot x + b)$ ，這個值是大于0的蛹稍。

在下圖中吧黄，綠色的函數(shù)即為合頁損失函數(shù)，因為其形狀像一個合頁唆姐，故名為合頁損失函數(shù)拗慨。下圖中還可以看出其他多種模型損失和函數(shù)間隔的關(guān)系：

對于0-1損失函數(shù)，如果正確分類奉芦，損失是0赵抢，誤分類損失1，如下圖黑線声功，可見0-1損失函數(shù)是不可導(dǎo)的烦却；
對于感知機模型，感知機的損失函數(shù)是 $[?yi(w\cdot x+b)]+$ 先巴，這樣當(dāng)樣本被正確分類時其爵，損失是0冒冬，誤分類時，損失是 $?yi(w\cdot x+b)$ 摩渺，如下圖紫線窄驹；
對于邏輯回歸和最大熵模型對應(yīng)的對數(shù)損失，損失函數(shù)是 $log[1+exp(?y(w\cdot x+b))]$ , 如下圖紅線所示：

多種損失函數(shù)的圖像

*圖像來自博客劉建平Pinard

4 線性支持向量機小結(jié)

線性支持向量機通過軟間隔最大化的方式证逻，處理因噪聲導(dǎo)致的線性不可分數(shù)據(jù)的分類問題，究其根本抗斤，只是在線性可分數(shù)據(jù)基礎(chǔ)上做了一點妥協(xié)囚企，并不是真的可以處理線性不可分數(shù)據(jù)的分類問題，對于真的非線性可分的問題瑞眼，應(yīng)該怎么辦呢龙宏？我們接下來看看基于核函數(shù)的非線性支持向量機。

主要參考

《統(tǒng)計學(xué)習(xí)方法》李航
劉建平Pinard

支持向量機SVM（2）線性支持向量機吴超、軟間隔最大化

支持向量機SVM（2）線性支持向量機、軟間隔最大化

1 原理

1）背景

2）原理