機器學習演算法實踐-SVM核函數和軟間隔

01-24

前言

上文中簡單總結了對於線性可分數據的SVM的演算法原理，本文對於非線性可分以及有雜訊存在的時候我們需要對基本SVM演算法的改進進行下總結其中包括:

核函數在SVM演算法中的使用
引入鬆弛變數和懲罰函數的軟間隔分類器

SVM對偶問題

這裡稍微回顧下SVM最終的對偶優化問題，因為後面的改進都是在對偶問題的形式上衍生的。

標準形式

$min frac{1}{2} lVert w Vert ^{2}$

subject to $y_{i}(w^{T}x_{i} + b) ge 1$

對偶形式

$arg max limits_{alpha} sum_{i=1}^{N} alpha_{i} - frac{1}{2}sum_{i=1}^{N}sum_{j=1}^{N}y_{i}y_{j}alpha_{i}alpha_{j}langle x_{i}, x_{j} angle$

subject to $alpha_{i} ge 0$ , $sum_{i=1}^{N}alpha_{i}y_{i}=0$

其中 $w$ 和 $alpha$ 的關係: $w = sum_{i=1}^{N}alpha_{i}y_{i}x_{i}$

SVM預測

SVM通過分割超平面 $w^{T}x + b$ 來獲取未知數據的類型，將上述 $w$ 用 $alpha$ 替換得到

$h_{w, b}(x) = g(w^{T}x + b) = g(sum_{i=1}^{N}alpha_{i}y_{i} langle x_{i}, x angle + b)$

通過 $g(x)$ 輸出+1或者-1來獲取未知數據的類型預測.

核函數

對於分線性可分的數據我們通常需要將數據映射到高維空間中使得原本在低維空間線性不可分的數據在高維空間中線性可分。例如從一維映射到4維:

$x xrightarrow{phi(x)} left[egin{matrix} x \ x^{2} \ x^{3} \ x^{4} \ end{matrix} ight]$

然後對偶形式中也有數據向量的乘積，於是便可以進行替換:

$langle x_{i}, x_{j} angle ightarrow langle phi(x_{i}), phi(x_{j}) angle$

但是呢，有時候 $phi(x)$ 會使得 $x$ 維度太高，這樣計算內積的複雜度很高，計算起來就會很困難，這個時候我們便需要核函數來拯救我們的計算複雜度。

我們需要使用一個函數來代替向量內積,但是這個核函數是可以表示成向量內積的形式的，只不過在計算結果的時候我們直接求函數值就好了，不需要做內積運算。這樣複雜度會降低:

$K(x, z) = langle phi(x), phi(z) angle$

核函數例子

這裡總結下幾個例子來對核函數的作用加深下理解.

對於 $x, z in mathbb{R}^{n}$ , 我們令核函數為:

$K(x, z) = (x^{T}z)^{2} = (sum_{i=1}^{N}x_{i}z_{i})^{2} = sum_{i=1}^{N}sum_{j=1}^{N} (x_{i}x_{j})(z_{i}z_{j}) = langle phi(x), phi(z) angle$

對於 $x in mathbb{R}^{2}$ , 這個時候 $phi(x)$ 的作用就相當於:

$phi(x) = left[ egin{matrix} x_{1}x_{1} \ x_{1}x_{2} \ x_{2}x_{1} \ x_{2}x_{2} \ end{matrix} ight]$

那麼我們可以分析下，如果沒有引入核函數，我們需要計算維數為 $n^2$ 的向量的內積，其運算時間複雜度為 $O(n^2)$ 。但是通過核函數的引入我們不需要顯式的計算向量內積了，而是直接計算核函數 $(x^{T}z)^2$ 的值，計算核函數的值我們只需要計算一次維數為 $n$ 的向量內積和一次平方運算，時間複雜度為 $O(n)$ 。

可見，我們通過計算核函數，隱式的處理了一個維數很高的向量空間，降低了計算複雜度 $O(n^{2}) ightarrow O(n)$ 。

對於上面的核函數進行推廣，我們可以有核函數:

$K(x, z) = (x^{T}z + C)^{2} = (x^{T}z)^{2} + 2C(x^{T}z) + c^{2}$

對於 $x in mathbb{R}^{2}$ , 這時 $phi(x)$ 相當於:

$phi(x) = left[ egin{matrix} x_{1}x_{1} \ x_{1}x_{2} \ x_{2}x_{1} \ x_{2}x_{2} \ sqrt{2C}x_{1} \ sqrt{2C}x_{2} \ C \ end{matrix} ight]$

這樣我們將原本需要計算長度為 $n^{2} + n + 1$ 的向量內積改成了直接計算兩個長度為 $n$ 的向量內積以及一個求和一次乘積運算。複雜度從 $O(n^{2})$ 降到了 $O(n)$

更通用的形式可以寫成:

$K(x, z) = (x^{T}z + C)^{d}$

可見，在我們原始的SVM推導中，直接使用原始向量的內積便是這種形式的一種特殊形式，即 $C = 0, d = 1$

另外，可以直觀的看到，如果 $phi(x)$ 與 $phi(z)$ 的夾角比較小，則計算出來的 $K(x,z)$ 就會比較大，相反如果 $phi(x)$ 與 $phi(z)$ 的夾角比較大，則核函數 $K(x,z)$ 會比較小。所以核函數一定程度上是 $phi(x)$ 與 $phi(z)$ 相似度的度量。

高斯核函數(Gaussian kernel)

$K(x, z) = exp(-frac{lVert x - z Vert^{2}}{2sigma^{2}})$

通過高斯核函數的公式可以看出，如果 $x$ 和 $z$ 相差很小，則 $K(x,z)$ 趨近於1, 相反如果相差很大則 $K(x,z)$ 趨近於0。高斯核函數能夠將數據映射到無限維空間，在無限維空間中，數據都是線性可分的。

核函數的合法性

判定核函數的合法性需要構造一個矩陣，即核函數矩陣 $K$ 。

對於一個核函數 $K(x,z)$ 以及 $m$ 個訓練數據 $left{ x_{1}, x_{2}, …, x_{m} ight}$ , 核函數矩陣中的元素 $K_{i,j}$ 定義如下:

$K_{i, j} = K(x_{i}, x_{j})$

現在在這裡簡單推導下核函數有效的必要條件:

若 $K(x, z)$ 有效，則矩陣元素可寫成(矩陣為對稱矩陣)

$K_{i, j} = phi(x_{i})^{T}phi(x_{j}) = phi(x_{j})^{T}phi(x_{i}) = K_{i, j}$

對於向量 $z$ , 我們有:

$z^{T}Kz = sum_{i} sum_{j} z_{i}K_{i, j}z_{j} = sum_{i} sum_{j}z_{i}phi(x_{i})^{T}phi(x_{j})z_{j} = sum_{i} sum_{j} z_{i} (sum_{k}phi(x_{i})_{k} phi(x_{j})_{k}) z_{j}$