上篇我們探讨了線性支援向量機和線性可分支援向量機的原理，它們線上性可分的資料表現很好，但是沒辦法對線性不可分的資料進行分類。那麼有沒有一些技巧，讓支援向量機也能處理線性不可分的資料呢？本篇我們将探讨核技巧，以及應用核技巧的線性不可分支援向量機。
解決線性不可分問題的思路有兩種，第一種是換更複雜的模型，如用神經網絡模型；另一種是增加模型的複雜度，最常用的做法是，對特征進行升維。
1）多項式技巧
盡管線性SVM分類器在許多案例上表現出非常高效和出色，但是存在許多資料集并不是線性可分的。一種處理非線性可分的資料集的方式是增加更多的特征，比如多項式特征，在某些情況下可以變的線性可分。比如下圖中，左圖是隻含有一個特征x1的簡單資料集，該資料集不是線性可分的。但是如果你增加了第二個特征 x 2 = ( x 1 ) 2 x2 = (x1)^2 x2=(x1)2，将資料映射二維空間中，你會神奇的發現，我們可以利用線性分類器進行分類了。
多項式特征很容易實作，不僅僅在SVM中，在各種機器學習算法都有不錯的表現，但是在低次數的多項式不能處理非常複雜的資料集，而高次數的多項式又産生了巨大的特征數量，讓模型變得更複雜，同時也讓模型訓練變慢甚至無法訓練。
2）核技巧
非常幸運，有一個叫做核技巧（kernel trick）的神奇學習技巧。它可以像使用了增加多個多項式特征，甚至可以是高次數的多個多項式特征一樣，效果一樣的好，但它并不用增加任何的特征，不會産生特征爆炸問題。
核技巧的基本思想很簡單，即把低維空間的線性不可分資料，轉化到高維空間甚至無窮次元的空間，讓它變得線性可分。
核技巧具體的意義在于，我們隻需定義核函數 K ( x i , x j ) K(x_i,x_j) K(xi,xj)，對于低維中的 x i , x j x_i,x_j xi,xj,有 K ( x i , x j ) = ϕ ( x i ) ϕ ( x j ) ′ K(x_i,x_j)=\phi (x_i){\phi}(x_j)' K(xi,xj)=ϕ(xi)ϕ(xj)′，以避開分别計算 ϕ ( x ) \phi (x) ϕ(x)，甚至不用去關心 ϕ ( x ) \phi (x) ϕ(x)長什麼樣，我們直接求 ϕ ( x i ) ϕ ( x j ) ′ \phi (x_i){\phi}(x_j)' ϕ(xi)ϕ(xj)′的值，通常計算 ϕ ( x i ) ϕ ( x j ) ′ \phi (x_i){\phi}(x_j)' ϕ(xi)ϕ(xj)′更容易。通俗可以了解成，核函數可以讓模型好好享受在高維特征空間線性可分的紅利，卻避免了高維特征空間恐怖的内積計算量。是以，核函數需要特殊的構造，下面我們探讨下常用的核函數。
3）常用核函數
核函數的種類有很多，Scikit-Learn常用的核函數有一下幾種：
-
線性核函數
K ( x i , x j ) = x i ⋅ x j ′ K(x_i,x_j)=x_i\cdot x_j' K(xi,xj)=xi⋅xj′
-
多項式核函數
K ( x i , x j ) = ( γ x i ⋅ x j ′ + c ) d K(x_i,x_j)=(\gamma x_i\cdot x_j'+c)^d K(xi,xj)=(γxi⋅xj′+c)d
-
高斯核函數
K ( x i , x j ) = e x p ( − γ ∣ ∣ x i − x j ∣ ∣ 2 ) K(x_i,x_j)=exp(-\gamma ||x_i-x_j ||^2) K(xi,xj)=exp(−γ∣∣xi−xj∣∣2)
-
拉普拉斯核函數
K ( x i , x j ) = e x p ( ∣ ∣ x i − x j ∣ ∣ ) K(x_i,x_j)=exp(||x_i-x_j ||) K(xi,xj)=exp(∣∣xi−xj∣∣)
-
Sigmoid核函數
K ( x i , x j ) = t a n h ( γ x i ⋅ x j + c ) K(x_i,x_j)=tanh(\gamma x_i\cdot x_j +c) K(xi,xj)=tanh(γxi⋅xj+c)
對于核函數的選擇，可以根據資料本身進行選擇。如果特征的數量很大，跟樣本數量差不多，優先考慮使用線性核函數；如果特征數量比較小，樣本數量一般，不算大也不算小，優先考慮使用高斯核函數；如果特征的數量比較小，而樣本數量很多，可以考慮手工增加特征，使用用線性核函數。
在SVM中，選擇線性核函數和高斯核函數時，需要對資料進行歸一化處理。
4）線性不可分支援向量機
上篇我們講到線性可分支援向量機的目标函數為：
m i n i m i z e ∣ ∣ w ∣ ∣ 2 2 2 \qquad \ \qquad \qquad \qquad \qquad minimize\frac{||w||^2_2}{ 2} minimize2∣∣w∣∣22
s . t . \qquad \ \qquad \qquad \qquad \qquad s.t. s.t. ( w T x i + b ) y i ≥ 1 (w^Tx_i+b)y_i\geq 1 (wTxi+b)yi≥1
為了後面更直覺的探讨核技巧，我們現在用 ϕ ( x i ) \phi (x^i) ϕ(xi)代替 x i x^i xi， ϕ ( x i ) \phi (x^i) ϕ(xi)為映射到高維的函數。目标函數變為：
m i n i m i z e ∣ ∣ w ∣ ∣ 2 2 2 \qquad \ \qquad \qquad \qquad \qquad minimize\frac{||w||^2_2}{ 2} minimize2∣∣w∣∣22
s . t . \qquad \ \qquad \qquad \qquad \qquad s.t. s.t. ( w T ϕ ( x i ) + b ) y i ≥ 1 (w^T\phi (x_i)+b)y_i\geq 1 (wTϕ(xi)+b)yi≥1
由于目标函數 ∣ ∣ w ∣ ∣ 2 2 2 \frac{||w||^2_2}{ 2} 2∣∣w∣∣22是凸函數，同時限制條件不等式是仿射的，根據凸優化理論，我們可以通過拉格朗日函數将我們的優化目标轉化為無限制的優化函數，目标函數變為：
L ( w , b , α ) = ∣ ∣ w ∣ ∣ 2 2 2 + ∑ i = 1 m α i ( 1 − y i ( w T ϕ ( x i ) + b ) ) L(w,b,\alpha )=\frac{||w||^2_2}{ 2}+\sum _{i=1}^m\alpha_i (1- y_i(w^T\phi (x_i)+b)) L(w,b,α)=2∣∣w∣∣22+∑i=1mαi(1−yi(wTϕ(xi)+b))， α i ≥ 0 \alpha_i≥0 αi≥0
引入了朗格朗日乘子，我們的優化目标變成：
m i n w , b m a x α L ( w , b , α ) min_{w,b}max_\alpha L(w,b,\alpha) minw,bmaxαL(w,b,α)
目标函數滿足KKT條件，即滿足拉格朗日對偶，我們的優化問題可以轉化為等價的對偶問題來求解。即：
m a x α m i n w , b L ( w , b , α ) max_\alpha min_{w,b} L(w,b,\alpha) maxαminw,bL(w,b,α)
從上式中，我們可以先求目标函數對于w和b的極小值。接着再求拉格朗日乘子α的極大值。
∂ ( L ) ∂ ( w ) = w − ∑ i = 1 m α i y i ϕ ( x i ) = 0 ⇒ w = ∑ i = 1 m α i y i ϕ ( x i ) \frac{\partial(L)}{\partial(w)}=w-\sum _{i=1}^m\alpha_i y_i\phi (x_i)=0 \qquad \Rightarrow \qquad w=\sum _{i=1}^m\alpha_i y_i\phi (x_i) ∂(w)∂(L)=w−∑i=1mαiyiϕ(xi)=0⇒w=∑i=1mαiyiϕ(xi)
∂ ( L ) ∂ ( b ) = ∑ i = 1 m α i y i = 0 ⇒ ∑ i = 1 m α i y i = 0 \frac{\partial(L)}{\partial(b)}=\sum _{i=1}^m\alpha_i y_i=0 \qquad \Rightarrow \qquad \sum _{i=1}^m\alpha_i y_i=0 ∂(b)∂(L)=∑i=1mαiyi=0⇒∑i=1mαiyi=0
求出w和α 的關系，就可以帶入優化函數 L ( w , b , α ) L(w,b,α) L(w,b,α)消去w了。
L ( w , b , α ) = ∣ ∣ w ∣ ∣ 2 2 2 + ∑ i = 1 m α i ( 1 − y i ( w T ϕ ( x i ) + b ) ) L(w,b,\alpha )=\frac{||w||^2_2}{ 2}+\sum _{i=1}^m\alpha_i (1- y_i(w^T\phi (x_i)+b)) L(w,b,α)=2∣∣w∣∣22+∑i=1mαi(1−yi(wTϕ(xi)+b))
= 1 2 w T w − w T ∑ i = 1 m α i y i ϕ ( x i ) + ∑ i = 1 m α i − b ∑ i = 1 m α i y i =\frac{1}{ 2}w^Tw-w^T\sum _{i=1}^m\alpha_i y_i\phi (x_i)+\sum _{i=1}^m\alpha_i-b\sum _{i=1}^m\alpha_i y_i =21wTw−wT∑i=1mαiyiϕ(xi)+∑i=1mαi−b∑i=1mαiyi
= 1 2 w T ∑ i = 1 m α i y i ϕ ( x i ) − w T ∑ i = 1 m α i y i ϕ ( x i ) + ∑ i = 1 m α i − b 0 =\frac{1}{ 2}w^T\sum _{i=1}^m\alpha_i y_i\phi (x_i)-w^T\sum _{i=1}^m\alpha_i y_i\phi (x_i)+\sum _{i=1}^m\alpha_i-b0 =21wT∑i=1mαiyiϕ(xi)−wT∑i=1mαiyiϕ(xi)+∑i=1mαi−b0
= ∑ i = 1 m α i − 1 2 w T ∑ i = 1 m α i y i ϕ ( x i ) =\sum _{i=1}^m\alpha_i-\frac{1}{ 2}w^T\sum _{i=1}^m\alpha_i y_i\phi (x_i) =∑i=1mαi−21wT∑i=1mαiyiϕ(xi)
= ∑ i = 1 m α i − 1 2 ( ∑ i = 1 m α i y i ϕ ( x i ) ) T ∑ i = 1 m α i y i ϕ ( x i ) =\sum _{i=1}^m\alpha_i-\frac{1}{ 2}(\sum _{i=1}^m\alpha_i y_i\phi (x_i))^T\sum _{i=1}^m\alpha_i y_i\phi (x_i) =∑i=1mαi−21(∑i=1mαiyiϕ(xi))T∑i=1mαiyiϕ(xi)
= ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) \sum _{i=1}^m\alpha_i-\frac{1}{ 2}\sum _{i,j=1}^m\alpha_i\alpha_j y_iy_j\phi (x_i)^T\phi (x_j) ∑i=1mαi−21∑i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)
a r g m a x α = ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) argmax_\alpha = \sum _{i=1}^m\alpha_i-\frac{1}{ 2}\sum _{i,j=1}^m\alpha_i\alpha_j y_iy_j\phi (x_i)^T\phi (x_j) argmaxα=∑i=1mαi−21∑i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)
再對 α \alpha α求最大值，
a r g m a x α = ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) argmax_\alpha = \sum _{i=1}^m\alpha_i-\frac{1}{ 2}\sum _{i,j=1}^m\alpha_i\alpha_j y_iy_j\phi (x_i)^T\phi (x_j) argmaxα=∑i=1mαi−21∑i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)
s . t . s.t. s.t. ∑ i = 1 m α i y i = 0 \sum _{i=1}^m\alpha_i y_i=0 ∑i=1mαiyi=0 ，
α i ≥ 0 ， i = 1 , 2... m \alpha_i ≥0，i=1,2...m αi≥0，i=1,2...m
習慣求取最小值，添加負号，
a r g m i n α = 1 2 ∑ i , j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) − ∑ i = 1 m α i argmin_\alpha = \frac{1}{ 2}\sum _{i,j=1}^m\alpha_i\alpha_j y_iy_j\phi (x_i)^T\phi (x_j)-\sum _{i=1}^m\alpha_i argminα=21∑i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)−∑i=1mαi
s . t . s.t. s.t. ∑ i = 1 m α i y i = 0 \sum _{i=1}^m\alpha_i y_i=0 ∑i=1mαiyi=0 ，
α i ≥ 0 ， i = 1 , 2... m \alpha_i ≥0，i=1,2...m αi≥0，i=1,2...m
通過SMO算法，得到了最優解α∗，代入 w ， b w，b w，b中，得：
w ∗ = ∑ i = 1 m α i ∗ y i ϕ ( x i ) w^*=\sum _{i=1}^m\alpha_i^* y_i\phi (x_i) w∗=∑i=1mαi∗yiϕ(xi)
b ∗ = y i − ∑ i = 1 m α i ∗ y i ϕ ( x i ) ϕ ( x j ) b^*=y_i-\sum _{i=1}^m\alpha_i^* y_i\phi (x_i)\phi (x_j) b∗=yi−∑i=1mαi∗yiϕ(xi)ϕ(xj)
讓我們再回到目标函數 a r g m i n α = 1 2 ∑ i , j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) − ∑ i = 1 m α i argmin_\alpha = \frac{1}{ 2}\sum _{i,j=1}^m\alpha_i\alpha_j y_iy_j\phi (x_i)^T\phi (x_j)-\sum _{i=1}^m\alpha_i argminα=21∑i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)−∑i=1mαi
s . t . s.t. s.t. ∑ i = 1 m α i y i = 0 \sum _{i=1}^m\alpha_i y_i=0 ∑i=1mαiyi=0 ，
α i ≥ 0 ， i = 1 , 2... m \alpha_i ≥0，i=1,2...m αi≥0，i=1,2...m
正常情況下，我們需要知道映射函數 ϕ ( x ) \phi (x) ϕ(x)，并将資料映射到超級高的次元來計算特征的内積。這時候映射成的高維次元是爆炸性增長的，這個計算量實在是太大了，而且如果遇到無窮維的情況，就根本無法計算。
是以，我們在SVM中引入核函數的機制。我們定義核函數 K ( x i , x j ) = ϕ ( x i ) ϕ ( x j ) ′ K(x_i,x_j)=\phi (x_i){\phi}(x_j)' K(xi,xj)=ϕ(xi)ϕ(xj)′。我們在低維空間進行 K ( x i , x j ) K(x_i,x_j) K(xi,xj)計算，避免了在高維次元空間計算内積的恐怖計算量。從另一個角度可以認為 K ( x i , x j ) K(x_i,x_j) K(xi,xj)是去求 x i , y i i x_i,yi_i xi,yii之間的相似度，這個相似度函數即為核函數。
5）SVM小結
SVM算法的主要優點有：
- 由于SVM是一個凸優化問題，是以求得的解一定是全局最優而不是局部最優。
- 僅僅使用一部分支援向量來做超平面的決策，無需依賴全部資料。
- 不僅适用于線性線性問題還适用于非線性問題(用核技巧)。
- 分類準确率高，泛化能力強。
SVM算法的主要缺點有：
- SVM在樣本量非常大，核函數映射次元非常高時，計算量過大，耗時交久。
- 無法直接支援多分類，但是可使用多個二分類實作。
- SVM對缺失資料敏感
（歡迎轉載，轉載請注明出處。）
上一篇：支援向量機（Support Vector Machine）原理總結（一）
下一篇：Scikit-learn 支援向量機庫總結與簡單實踐
![簡單文檔分類——樸素貝葉斯算法樸素貝葉斯算法簡單文檔分類執行個體步驟總結樸素貝葉斯分類調用(sklearn)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)