支持向量機(jī)/SVM（Support Vector Machine）

SVM，曾經(jīng)是最為流行的機(jī)器學(xué)習(xí)算法，可以用于分類問題、回歸問題及異常點(diǎn)檢測問題。不僅如此，SVM的算法動機(jī)可以通過計算學(xué)習(xí)理論或者統(tǒng)計學(xué)習(xí)理論進(jìn)行理解，使其有充分的理論保障。

算法釋義

對于二分類問題，類似于感知機(jī)，SVM 算法要尋找特征空間中的一個超平面將正反樣本分開，但是SVM需要尋找一個唯一的超平面使得離該平面最近的點(diǎn)的距離最大，也就是說 SVM 的解相當(dāng)于感知機(jī)的解空間中泛化誤差最小解。

重要概念

這里首先以硬間隔的二分類 SVM 介紹，然后將其推廣到軟間隔分類、多分類和回歸 SVM 。

函數(shù)間隔和幾何間隔

函數(shù)間隔就是特征空間中點(diǎn)到超平面的距離，即：
margin_f(x) = y(w^Tx + b)
我們知道對于同一個超平面，可能有不同的表示，因此即使對于同一個超平面，不同的 w 的取值也會造成不同的函數(shù)間隔的值，所以我們需要使用一個更能反映真是距離的變量，這里我們引入幾何間隔的概念：
margin_g(x) = \frac {y(w^Tx + b)} {||w||}
通過使函數(shù)間隔除以 w 向量的二范數(shù)，幾何間隔只和超平面和特征空間中的點(diǎn)有關(guān)，和超平面的表示方式無關(guān)。

SVM 基本形式

首先確定假設(shè)空間，即線性二元分類器：
f(x) = sign(w^Tx + b)

用 marginmin 表示訓(xùn)練樣本中離超平面最小的幾何間隔，要使最小的幾何間隔最大，相當(dāng)于求下列函數(shù)：
arg \max_{w} \left(\min_n { \frac {y(w^Tx_n + b)} {||w||}} \right)

由于最小化問題與 ||w|| 的取值無關(guān)，可以將上式中的 ||w|| 提出：
arg \max_{w} \left( \frac 1 {||w||} \min_n { {y(w^Tx_n + b)} } \right)

內(nèi)層的最小化問題就變成了最小化函數(shù)間隔，這里固定最小化之后的函數(shù)間隔為 1，從而原問題變?yōu)椋?br> \begin{align} &arg \max_{w} \frac 1 {||w||} \\ &s.t.\,\, y(w^Tx_n + b) ≥ 1, n = 1,2,...,N \end{align}

按照通常習(xí)慣，把最大化問題改為最小化問題，為了便于求解，把二范數(shù)改為向量內(nèi)積，最終得到 SVM 模型的基本形式，即：
\begin{align} &arg \min_{w} \frac 1 2 w^Tw \\ &s.t.\,\, y_n(w^Tx_n + b) ≥ 1, n = 1,2,...,N \end{align}

SVM 對偶形式

利用拉格朗日乘子，把帶條件的最優(yōu)化問題，轉(zhuǎn)變?yōu)椴粠l件的最優(yōu)化問題，然后根據(jù)拉格朗日對偶性，得到極小極大問題的對偶形式，即極大極小問題（要使兩個問題的解相等，那么要使解滿足 KTT 條件）：
\begin{align} &L(w, b, α) = \frac 1 2 w^Tw + \sum_{n=1}^N {α_n(1 - y_n(w^Tx_n + b))}, \\ &\min_{w,b} \max_{α} L(w, b, α) \\ &\max_{α} \min_{w,b} L(w, b, α) \end{align}

對于內(nèi)層的極小問題，令其對 w 和 b 的導(dǎo)數(shù)分別等于零，從而求得內(nèi)層極小問題的解：
\begin{align} & \nabla_w L(w, b, α) = w - \sum_{n=1}^N α_ny_nx_n = 0 \\ & \nabla_b L(w, b, α) = -\sum_{n=1}^N α_ny_n = 0 \\ & 解得：\\ & w = \sum_{n=1}^N α_ny_nx_n \\ & \sum_{n=1}^N α_ny_n = 0 \\ & 帶入極大極小問題，然后加負(fù)號把最大化問題變?yōu)樽钚』瘑栴}：\\ & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}

KTT 條件

對于約束最優(yōu)化問題，其一般形式是：
\begin {align} & \min_x f(x) \\ & s.t. \,\, c_i(x) ≤ 0, i=1,2,...,k \\ & \,\,\,\,\,\,\,\,\,\,\,\, h_j(x) = 0, j=1,2,...,l \end {align}

加上拉格朗日乘子變成無約束的最優(yōu)化問題：
\begin{align} &L(x, α, β) = f(x) + \sum_{i=1}^k {α_ic_i(x)} + \sum_{j=1}^l {β_jh_j(x)}, 其中α_i ≥ 0\\ &\min_{x} \max_{α, β} L(x, α, β) \\ &\max_{α, β} \min_{x} L(x, α, β) \end{align}

上述極小極大問題的解要和極大極小問題的解一樣，需要滿足 KTT 條件：
\begin{align} & \nabla_{x^*} L(x^*, α^*, β^*) = 0 \\ & α_i^*c_i(x^*) = 0, i=1,2,...,k \\ & c_i(x^*) ≤ 0, i=1,2,...,k \\ & α_i^* ≥ 0, i=1,2,...,k \\ & h_j(x^*) = 0, j=1,2,...,l \\ \end{align}

在 SVM 中 KTT 條件即：
\begin{align} & α_i^*(1-y_i(w^{*T}x_i + b)) = 0, i=1,2,...,N \\ & 1-y_i(w^{*T}x_i + b) ≤ 0, i=1,2,...,N \\ & α_i^* ≥ 0, i=1,2,...,N \\ \end{align}

SVM 學(xué)習(xí)算法

(1) 構(gòu)造求解約束最優(yōu)化問題：
\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}

(2) 通過 α 的解求出 w, b 的解：
\begin{align} & w^* = \sum_{n=1}^N α^*_ny_nx_n \\ & 根據(jù)\,KTT\,條件，選擇α^*一個不為零的分量α^*_j > 0：\\ & b^* = y_j - w^*x_j = y_i - \sum_{n=1}^N α^*_ny_nx_n^Tx_j \end{align}

(3) 求得分類決策函數(shù)：
f(x) = sign(w^{*T}x + b^*)

核函數(shù)

對于線性可分的問題，我們可以直接使用原始的 SVM 進(jìn)行分類，但是很多時候訓(xùn)練集數(shù)據(jù)是線性不可分的，這個時候我可以考慮使用特征轉(zhuǎn)換，把輸入特征空間通過映射函數(shù) Φ 映射到另一個特征空間：
\phi(x)： X \rightarrow H
然而很多時候?qū)ふ乙粋€合適的映射函數(shù) Φ 是很困難的，而且尋找到 Φ 之后還需要先做特征轉(zhuǎn)換，再求轉(zhuǎn)換后的特征的內(nèi)積，那有沒有更簡單的辦法呢？首先定義核函數(shù)：
\kappa(x_i, x_j) = \phi(x_i) · \phi(x_j)
我們能不能在只有核函數(shù) κ 不知道映射函數(shù) Φ 的情況下，求 SVM 呢？注意看我們求解特征轉(zhuǎn)換后的 SVM 的形式：
\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_j \kappa(x_i, x_j) - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}

而且解出來的分類決策函數(shù)：
f(x) = sign( \sum_{n=1}^N α^*_ny_n \kappa(x_n, x) + b^*)

不難發(fā)現(xiàn)，上述過程中映射函數(shù) Φ 仿佛消失了，那是不是說明我們只需要定義一個核函數(shù)，就可以解 SVM 了呢？其實不然，因為我們還要保證這樣的核函數(shù)是能夠映射的，換句話說，必須要存在某種映射關(guān)系使得該核函數(shù)存在。而這種保證的充要條件就是核函數(shù)必須為正定核，這里就不展開了。
常見的核函數(shù)有
(1) 多項式核函數(shù)( p 次多項式核)：
\kappa(x_i, x_j) = (x_i^Tx_j + 1)^p
(2) 高斯核函數(shù)：
\kappa(x_i, x_j) = e^{-\frac {||x_i - x_j||^2} {2σ^2} }

SVM 推廣

軟間隔的 SVM

有時候訓(xùn)練集數(shù)據(jù)近似線性可分但是不是線性可分的，也有的時候因為噪點(diǎn)的存在，使得 SVM 的結(jié)果存在過擬合，這個時候就可以使用軟間隔的 SVM，所謂軟間隔，就是在原始 SVM 的假設(shè)上稍稍放寬其限制條件，讓某些點(diǎn)的函數(shù)間隔可以小于1，即在約束條件上加一個松弛變量：
y_n=(w^Tx_n+b) ≥ 1 - ξ_n

這里 ξn ≥ 0，然后對于每一個松弛變量，支付一個代價 ξn，故將目標(biāo)函數(shù)變?yōu)椋?br> \frac 1 2 w^Tx + C \sum_{n=1}^N ξ_n

從而，軟間隔的 SVM 有如下基本形式：
\begin{align} &arg \min_{w} \frac 1 2 w^Tw + C \sum_{n=1}^N ξ_n \\ &s.t.\,\, y_n(w^Tx_n + b) ≥ 1 - ξ_n, n = 1,2,...,N \\ & \,\,\,\,\,\,\,\,\,\,\,\, ξ_n ≥ 0, n = 1,2,...,N \end{align}

將其轉(zhuǎn)換為拉格朗日對偶問題，有：
\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, C≥α_n≥0, n=1,2,...,N \end{align}

在軟間隔 SVM 中 KTT 條件為：
\begin{align} & α_i^*(1-y_i(w^{*T}x_i + b) - ξ_i) = 0, i=1,2,...,N \\ & 1-y_i(w^{*T}x_i + b) - ξ_i ≤ 0, i=1,2,...,N \\ & α_i^* ≥ 0, i=1,2,...,N \\ \end{align}

多分類 SVM

One versus the rest （一對剩余）
如果有 K 個類別，那么訓(xùn)練 K 個二分類 SVM 分類器，然后綜合這 K 個訓(xùn)練器的預(yù)測結(jié)果給出預(yù)測
One versus one （一對一）
如果有 K 個類別，那么每兩個類的樣本和到一塊訓(xùn)練 1 個二分類 SVM 分類器，一共 K (K - 1) / 2個分類器，然后綜合這些訓(xùn)練器的預(yù)測結(jié)果給出預(yù)測

回歸 SVM

pass

參考文獻(xiàn)

《Pattern Recognition and Machine Learning》，Bishop

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容