統(tǒng)計機器學習-線性支持向量機與軟間隔最大化

假設給定一個特征空間上的訓練數據集
T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}
其中，x_i\in\mathcal X=\textbf R^n，y_i\in\mathcal Y=\{+1,-1 \}，i=1,2,\cdots,N，x_i為第i個特征向量，也稱為實例，y_i為x_i的類標記，當y_i=+1時，稱x_i為正例；當y_i=-1時，稱x_i為負例，(x_i,y_i)稱為樣本點。再假設訓練數據集不是線性可分的。通常情況是，訓練數據中有一些特異點，將這些特異點除去后，剩下大部分的樣本點組成的集合是線性可分的。

線性不可分意味著某些樣本點(x_i,y_i)不能滿足函數間隔大于等于1的約束條件。為了解決這個問題，可以對每個樣本點(x_i,y_i)引進一個松弛變量\xi_i\geq0，使函數間隔加上松弛變量大于等于1。這樣，約束條件變?yōu)?br> 1-\xi_i-y_i(w\cdot x_i+b)\leq0
目標函數由原來的最小化\frac12||w||^2變成最小化
\frac12||w||^2+C\sum_{i=1}^N\xi_i
C是對誤分類的懲罰，C越大，對誤分類懲罰越大。相對于線性可分支持向量機的硬間隔最大化，這叫做軟間隔最大化。

于是線性不可分支持向量機的學習的原始問題為凸二次規(guī)劃問題：
\min_{w,b,\xi}\frac12||w||^2+C\sum_{i=1}^N\xi_i\tag1

\mathrm{s.t.}\ \ 1-\xi_i-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N\tag2

-\xi_i\leq0,\ \ i=1,2,\cdots,N\tag3

可以證明w的解是唯一的，但b的解可能不唯一，而是存在于一個區(qū)間。證明略。

假如w^*，b^*是最優(yōu)化問題(1)-(3)的解，則得到的超平面為
w^*\cdot x+b^*=0\tag4
分類決策函數為
f(x)=\mathrm{sign}(w^*\cdot x+b^*)\tag5
稱為線性支持向量機。

對偶的學習算法

由原始問題(1)-(3)，首先構建拉格朗日函數
L(w,b,\xi,\alpha,\mu)=\frac12||w||^2+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))-\sum_{i=1}^N\mu_i\xi_i\tag6
其中\alpha_i\geq0，\mu_i\geq0，于是原始問題可以寫成
\min_{w,b,\xi}\max_{\alpha,\mu}L(w,b,\xi,\alpha,\mu)
則對偶問題為
\max_{\alpha,\mu}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)
首先求解內部極小化問題，求L(w,b,\xi,\alpha,\mu)對w，b，\xi的偏導并使其等于0：
\nabla_wL(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0

\nabla_bL(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N\alpha_iy_i=0

\nabla_{\xi_i}=C-\alpha_i-\mu_i=0

得
w=\sum_{i=1}^N\alpha_iy_ix_i\tag7

\sum_{i=1}^N\alpha_iy_i=0\tag8

C-\alpha_i-\mu_i=0\tag9

將公式(7)-(9)代入(6)得到
L(w,b,\xi,\alpha,\mu)=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i
于是原始的問題(1)-(3)的對偶問題可以寫成
\max_{\alpha}-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \tag{10}

\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag{11}

C-\alpha_i-\mu_i=0\tag{12}

\alpha_i\geq0\tag{13}

\mu_i\geq0,\ \ i=1,2,\cdots,N\tag{14}

對其進一步改寫，由公式(12)得
\mu_i=C-\alpha_i
代入公式(14)得
\alpha_i\leq C
所以公式(12)-(14)可以簡寫為
0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N
再對目標函數取相反數，得到對偶問題
\min_{\alpha}\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i \tag{15}

\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag{16}

0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag{17}

定理

設\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)是對偶問題(15)-(17)的一個解，若存在\alpha^*的一個分量\alpha_j^*，0\lt\alpha_j^*\lt C，則原始問題(1)-(3)的解w^*,b^*可按下式得到：
w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{18}

b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)\tag{19}

證明略。

于是分離超平面可以寫成
\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0
分類決策函數
f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y(x\cdot x_i)+b^*\bigg)

線性支持向量機學習算法

輸入：訓練數據集T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}，其中，x_i\in\mathcal X=\textbf R^n，y_i\in\mathcal Y=\{-1,+1\}，i=1,2,\cdots,N；

輸出：分離超平面和分類決策函數。

（1）選擇懲罰參數C\gt0，構造并求解凸二次規(guī)劃問題
\min_{\alpha}\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i

\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0

0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N

求的最優(yōu)解\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)。

（2）計算w^*=\sum_{i=1}^N\alpha_iy_ix_i

選擇\alpha^*的一個分量\alpha_j^*適合條件0\lt\alpha_j^*\lt C，計算
b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)
（3）求得分離超平面
w^*\cdot x+b^*=0
分類決策函數：
f(x)=\mathrm{sign}(w^*\cdot x)+b^*

支持向量

由公式
w^*=\sum_{i=1}^N\alpha_i^*y_ix_i
得知\alpha_i^*\neq0的樣本點x_i能夠影響支持向量機的參數。而0\leq\alpha_i^*\leq C，所以支持向量為0\lt\alpha_i^*\leq C的樣本點x_i。這些支持向量分布在間隔邊界上、間隔邊界與分離超平面之間或者在分離超平面誤分一側。若\alpha_i^*\lt C，則\xi_i=0（由KKT條件可以推出，由于\xi^*的結果不影響分離超平面，所以一般也不去算，其計算過程略），支持向量恰好落在間隔邊界上；若\alpha_i^*=C，0\lt\xi_i\lt1，則分類正確，支持向量在間隔邊界與分離超平面之間；若\alpha_i^*=C，\xi_i=1，則x_i在分離超平面上；若\alpha_i^*=C，\xi_i\gt1，則x_i在分離超平面誤分一側。

合頁損失函數

線性支持向量機的學習還等價于最小化以下目標函數：
\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2\tag{20}
證明過程略。其中目標函數的第一項是經驗損失或經驗風險，第二項是正則化項。函數
L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+
稱為合頁損失函數。下標"+"表示ReLU函數，由于函數形狀像一個合頁，故名合頁損失函數。合頁損失函數相比感知機的0-1損失，不僅要求分類正確，還要求確信度足夠高時（函數間隔大于等于1）損失才是0，所以支持向量機的學習比感知機有更高的要求。

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容