SVM補(bǔ)充

決策邊界

Coursera 上 ML 的課程對 SVM 介紹有限，參看了周志華教授的《機(jī)器學(xué)習(xí)》一書后，補(bǔ)充了當(dāng)中對于 SVM 的介紹。

首先，我們考慮用更傳統(tǒng)的權(quán)值定義式來描述我們的 SVM 決策邊界（劃分超平面）：
$$w^{T}x+b=0\text{\hspace{1em}(1)}$$

其中， $w$ 表示權(quán)值向量，權(quán)值向量對應(yīng)了決策邊界的法向量。 $b$ 則表示偏置，也稱位移項(xiàng)，表示了決策邊界距坐標(biāo)原點(diǎn)的距離。我們可以將決策邊界記為 $(w,b)$ ，那么，樣本 $x$ 到?jīng)Q策邊界的距離為：
$$r=\frac{|w^T+b|}{||w||}\text{\hspace{1em}(2)}$$

我們將正樣本標(biāo)識(shí)為 1，負(fù)樣本標(biāo)識(shí)為 -1， 則 SVM 的期望預(yù)測可以重新描述為：
$$\{\begin{array}{l}{w}^T{x}^{(i)}+b\ge +1,if{y}^{(i)}=+1\\ w^T{x}^{(i)}+b\le ?1,if{y}^{(i)}=?1\end{array}\text{\hspace{1em}(3)}$$

亦即：
$$y^{(i)}(w^T{x}^{(i)}+b)\ge 1\text{\hspace{1em}(4)}$$

使等號成立的樣本稱之為“支持向量（Support Vectors）”，兩個(gè)異類的支持向量到?jīng)Q策邊界的距離之和為：
$$\gamma =\frac{2}{||w||}\text{\hspace{1em}(5)}$$

γ 被稱之為間隔。

在之前的篇章中我們知道，SVM 就是力圖是 $\gamma$ 足夠大，從而獲得更好的泛化能力：
$$\begin{gathered} \underset{w,b}{\max }\frac{2}{||w||} \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,2,...,m\text{\hspace{1em}(6)} \end{gathered}$$

我們可以轉(zhuǎn)化為如下的二次優(yōu)化問題：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}{||w||}^2 \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,2,...,m\text{\hspace{1em}(7)} \end{gathered}$$

硬間隔與軟間隔

下圖中，紅色的決策邊界表示了一種較硬的間隔劃分，這種劃分，能將所有正、負(fù)樣本區(qū)分開來：

硬間隔并不一定好，就像我們在回歸問題中提到的那樣，這只是對于訓(xùn)練樣本作出了極佳的擬合，但容易造成過度擬合。比如我們現(xiàn)在有了一個(gè)新的負(fù)樣本，他被錯(cuò)誤地分類為了正樣本：

而下圖則展示了一種較軟的間隔，這樣的決策邊界允許了一部分分類異常，避免了過擬合問題，但如果過軟，也容易造成欠擬合問題：

鑒于此，我們在優(yōu)化過程中，添加一個(gè)參數(shù) $C$ 來控制間隔的“軟硬”：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{||w|{|}^2}+C\sum _{i=1}^m?(y^{(i)}(w^T{x}^{(i)})?1) \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,2,...,m\text{\hspace{1em}(8)} \end{gathered}$$

其中， $?(z)$ 是損失函數(shù)，其衡量了樣本 $x$ 與真實(shí)值 $y^{(i)}$ 的近似程度，當(dāng) $C$ 取值越大時(shí)，為了最優(yōu)化問題，需要 $?(z)$ 越小，即各個(gè)樣本都要盡可能分類正確，這提高了訓(xùn)練準(zhǔn)確率，但也面臨過擬合的問題。

故而， $C$ 扮演了回歸問題中正則化參數(shù) $\frac{1}{\lambda }$ 的角色。當(dāng) C 的取值趨于 $\infty$ 時(shí)，模型就變?yōu)榱擞查g隔支持向量機(jī)。

常見的損失函數(shù)有：

名稱函數(shù)式

0/1 損失	$?(z)=\{\begin{array}{l}1,ifz<0\\ 0,otherwise\end{array}$
hinge 損失	$?(z)=max(0,1,?z)$
指數(shù)損失	$?(z)=exp(?z)$
對數(shù)損失	$?(z)=log(1+exp(?z))$

若采用 hinge 損失函數(shù)，則式 (8) 可以具體為：
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^{m}max(0,1?y^{(i)}(w^T{x}^{(i)}+b))\text{\hspace{1em}(9)}$$

引入 “松弛變量（slack variables）” ${\xi }^{(i)}\ge 0$ ，可以將式 (9) 改寫為：
$$\begin{gathered} \underset{w,b,{\xi }^{(i)}}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }^{(i)} \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1?{\xi }^{(i)} \\ {\xi }^{(i)}\ge 0,i=1,2,3,...,m\text{\hspace{1em}(10)} \end{gathered}$$

這就構(gòu)成 “軟間隔支持向量機(jī)”。

松弛變量，顧名思義，就是控制每個(gè)樣本受到約束的程度。 ξ(i) 越大，則受約束程度越小（越松弛）。

• 當(dāng) ${\xi }^{(i)}>1$ ，則 $max(0,1?y^{(i)}(w^T{x}^{(i)}+b))>1$ ，即 $y^{(i)}$ 與 $(w^T{x}^{(i)}+b))$ 異號，分類錯(cuò)誤。
• 當(dāng) ${\xi }^{(i)}=0$ ，則 $max(0,1?y^{(i)}(w^T{x}^{(i)}+b))=0$ ，即 $1?y^{(i)}(w^T{x}^{(i)}+b)=0$ ，樣本落在了最大間隔邊界上。
• 當(dāng) $0<{\xi }^{(i)}\le 1$ ，則 $max(0,1?y^{(i)}(w^T{x}^{(i)}+b))\le 1$ ，即 $0\le 1?y^{(i)}(w^T{x}^{(i)}+b))\le 1$ ，樣本落在了最大間隔與決策邊界之間。

對偶問題

對于式 (10) 的優(yōu)化模型，應(yīng)用拉格朗日乘子法獲得的拉格朗日函數(shù)如下：
$$L(w,b,a,\xi ,\mu )=\frac{1}{2}|||{|}^2+C\sum _{i=1}^m{\xi }^{(i)}+\sum _{i=1}^m{a}^{(i)}(1?{\xi }^{(i)}?y_i(w^T{x}_i+b))?\sum _{i=1}^m{\mu }^{(i)}{\xi }^{(i)}\text{\hspace{1em}(11)}$$

其中， ${\alpha }^{(i)}\ge 0，{\mu }^{(i)}\ge 0$ 是拉格朗日乘子。

令 $L(w,b,\alpha ,\xi ,\mu )$ 對 $w$ ， $b$ ， ${\xi }^{(i)}$ 的偏導(dǎo)為 0 可得：
$$w=\sum _{i=1}^m{a}^{(i)}{y}^{(i)}{x}^{(i)}\text{\hspace{1em}(12)}$$$$0=\sum _{i=1}^m{a}^{(i)}{y}^{(i)}\text{\hspace{1em}(13)}$$$$C=a^{(i)}+{\mu }^{(i)}\text{\hspace{1em}(14)}$$

將其帶入 (1) 式中，得：
$$f(x)=w^{T}x+b=\sum _{i=1}^m{a}^{(i)}{y}^{(i)}(x^{(i)}{)}^{T}x+b\text{\hspace{1em}(15)}$$

將式 (12) - (14) 代入式 (11) 中，就得到了式 (10) 的 對偶問題：
$$\begin{gathered} \underset{a}{\max }\sum _{i=1}^m{a}^{(i)}?\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{a}^{(i)}{a}^{(j)}{y}^{(i)}{y}^{(j)}(x^{(i)}{)}^T{x}^{(j)} \\ s.t.\sum _{i=1}^m{a}^{(i)}{y}^{(i)}=0,0\le {\alpha }^{(i)}\le C,i=1,2,...,m\text{\hspace{1em}(16)} \end{gathered}$$

對于軟間隔支持向量機(jī)，KKT 條件要求：
$$?\begin{array}{l}{a}^{(i)}\ge 0,{\mu }^{(i)}\ge 0,\\ y^{(i)}f(x^{(i)})?1+{\xi }^{(i)}\ge 0,\\ a^{(i)}(y^{(i)}f(x^{(i)})?1+{\xi }^{(i)})=0,\\ {\xi }^{(i)}\ge 0,{\mu }^{(i)}{\xi }^{(i)}=0\end{array}\text{\hspace{1em}(17)}$$

由式$a^{(i)}(y^{(i)}f(x^{(i)})?1+{\xi }^{(i)})=0$可得，對于任意訓(xùn)練樣本$(x^{(i)},y^{(i)})$，總有 $a^{(i)}=0$ 或者 $y^{(i)}f(x^{(i)})=1?{\xi }^{(i)}$。

• 若 $a^{(i)}=0$，由 $C={\mu }^{(i)}+a^{(i)}$ 得 ${\mu }^{(i)}=C$，進(jìn)而得 ${\xi }^{(i)}=0$：
  $$y^{(i)}f(x^{(i)})?1\ge 0\text{\hspace{1em}(18)}$$

  • 此時(shí)， $x^{(i)}$ 不會(huì)對模型 $f(x)$ 產(chǎn)生影響。

• 若 $0<a^{(i)}<C$，則有 $y^{(i)}f(x^{(i)})?1+{\xi }^{(i)}=0$，由 $C={\mu }^{(i)}+a^{(i)}$ 得 ${\mu }^{(i)}>0$，進(jìn)而得 ${\xi }^{(i)}=0$，綜合得：
  $$y^{(i)}f(x^{(i)})?1=0\text{\hspace{1em}(19)}$$

  • 此時(shí)，樣本 $x^{(i)}$ 為支持向量。

• 若 $a^{(i)}=C$，則有 $y^{(i)}f(x^{(i)})?1+{\xi }^{(i)}=0$，由 $C={\mu }^{(i)}+a^{(i)}$ 得 ${\mu }^{(i)}=0$，此時(shí) ${\xi }^{(i)}>0$，得：
  $$y^{(i)}f(x^{(i)})?1\le 0\text{\hspace{1em}(20)}$$

  • 此時(shí)，樣本 $x^{(i)}$ 落在最大間隔與決策邊界之間 $({\xi }^{(i)}\le 0)$，或者分類錯(cuò)誤 $({\xi }^{(i)}>1)$。亦即，樣本異常，仍然不會(huì)被模型 $f(x)$ 考慮。

綜上，我們不但可以將 KKT 條件寫為：

$$\begin{gathered} a^{(i)}=0?y^{(i)}f(x^{(i)})\ge 1 \\ 0<a^{(i)}<C?y^{(i)}f(x^{(i)})=1 \\ {a}^{(i)}=C?y^{(i)}f(x^{(i)})\le 1\text{\hspace{1em}(21)} \end{gathered}$$

并且，還能夠知道，采用了 hinge 損失函數(shù)的最終模型 $f(x)$ 僅與支持向量有關(guān)。

核函數(shù)

假定我們面臨的數(shù)據(jù)呈現(xiàn)下面這樣的分布：

顯然，這不是一個(gè)線性可分的問題，在邏輯回歸中，我們會(huì)通過多項(xiàng)式擴(kuò)展來創(chuàng)建新的高維特征，從而將低維度的線性不可分問題轉(zhuǎn)換為了高維度的線性可分問題。

在 SVM 中，仍然是考慮將低維不可分問題轉(zhuǎn)換到高維度可分問題：

$$f(x)=w^T?(x)+b\text{\hspace{1em}(22)}$$

$?(x)$ 對應(yīng)了 $x$ 的高維度特征向量。

此時(shí)，SVM 優(yōu)化模型的對偶問題為：

$$\begin{gathered} \underset{a}{\max }=\sum _{i=1}^m{a}^{(i)}?\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{a}^{(i)}{a}^{(j)}{y}^{(i)}{y}^{(j)}?(x^{(i)}{)}^T?(x^{(i)}) \\ s.t.\sum _{i=1}^m{a}^{(i)}{y}^{(i)}=0, \\ 0\le a^{(j)}\le C,i=1,2,3,...,m\text{\hspace{1em}(23)} \end{gathered}$$

令 $\kappa (x^{(i)},x^{(j)})$ 表示 $x^{(i)}$ 與 $x^{(j)}$的內(nèi)積：

$$\kappa (x^{(i)},x^{(j)})=??(x^{(i)},?(x^{(j)}))?=?(x^{(i)}{)}^T?(x^{(j)})\text{\hspace{1em}(24)}$$

函數(shù) $\kappa$ 即表示了核函數(shù)（kernel function），引入核函數(shù)后，優(yōu)化模型可以寫為：
$$\begin{gathered} \underset{a}{\max }=\sum _{i=1}^m{a}^{(i)}?\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{a}^{(i)}{a}^{(j)}{y}^{(i)}{y}^{(j)}\kappa (x^{(i)},x^{(j)}) \\ s.t.\sum _{i=1}^m{a}^{(i)}{y}^{(i)}=0, \\ 0\le a^{(j)}\le C,i=1,2,3,...,m\text{\hspace{1em}(26)} \end{gathered}$$

求解后，得到模型：

$$f(x)=w^T?(x)+b=\sum _{i=1}^m{a}^{(i)}{y}^{(i)}{y}^{(j)}?(x^{(i)}{)}^T?(x)+b=\sum _{i=1}^m{a}^{(i)}{y}^{(i)}{y}^{(j)}\kappa (x,x^{(i)})+b\text{\hspace{1em}(27)}$$

參考資料

• 《機(jī)器學(xué)習(xí)》
• 支持向量機(jī)通俗導(dǎo)論（理解 SVM 的三層境界）
• 支持向量機(jī)

總結(jié)

以上是生活随笔為你收集整理的5.5 SVM补充-机器学习笔记-斯坦福吴恩达教授的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。