2018/12/8

Support Vector Machines (SVMs, 支撐向量機)

11 Support Vector Machines (SVMs,支撐向量機)

在線性分類中如果資料是線性可分離,則可用一直線將資料分類,但如果不是線性可分離,則無法用直線分離,必需擴大特徵的空間(增加維度),如引進二階或多階多項式,但增加維度會增加計算的複雜度,當特徵數大的時候計算可能會不可行。Support Vector Machines (SVMs, 支撐向量機)利用一種稱為kernel (核) 的觀念使計算的複雜度降低,同時又能達成非線性分類的功能。

要談SVMs就得先從分類器 (classifier) 的最大邊界 (Maximal margin) 談起,
分類器邊緣
上圖中的點線性可分離,圖中列出三條直線可用於將資料點依顏色分離,直線1旁緊隨著一個藍點及一個紫點,直線3下方有很多距離很近的紫點,這兩條線看來都不是很好,而直線 2離最接近的點的距離比直線 1 和 3都大,所以直3應較合適。和最接近的點的距離就是邊界值的大小,而最大邊界是指使此邊界值最大化。

當資料只有兩維的時候分類函數是個直線方程式,三維時是個平面,更多維時就稱超平面 (Hyperplane)  ,超平面和最接近的訓練點的垂直距離就稱最大邊界值。
最大邊界
上圖中實線和兩邊的虛線間的區域就是邊界區。

∎ Hard margin support vector classifier
在一組給定的資料中建構最大邊緣二元分類器就同等解下列最佳化的問題
$$\begin{equation} \min _{\boldsymbol{w},\gamma} \frac{1}{2}\left \| \boldsymbol{w} \right \|^2, \mbox{   subject to }(\boldsymbol{w}^T \boldsymbol{x}_i+\gamma)y_i\geq 1, \: \forall i=1,\cdots,n \end{equation}$$
其中 $n$ 是訓練點(實例)的數目, $\boldsymbol{w}$ 為為權重係數,$\gamma$ 是截距,$\boldsymbol{x}_i$ 是第$i$個實例的特徵,$y_i$ 為其 label,值為$+1$ 或$-1$.
 Hard margin
上圖中中間黑線為hyperplane,兩虛線為decision boundaries (決策界線) ,其間的距離為 $\frac{2}{\left \| \boldsymbol{w} \right \|}$。兩個分別標為1,2的點落在邊界上面,它們就稱為support vector (支撐向量) 。

∎ Soft margin support vector classifier
硬性的邊界策略不允許訓練落在邊界區裡,軟性的策略則可允許部份點落在邊界區裡,甚至是落到超平面的另一邊,一般講的 support vector classifier (SVC) 就是指這種軟性邊界決棗的分類器。最佳化的問題描述是
$$\begin{equation} \min _{\boldsymbol{w,\varepsilon},\gamma}\left [   \frac{1}{2} \left \| \boldsymbol{w}  \right \|^2 +C\sum_{i=1}^{n}  \varepsilon_i  \right]\mbox{   subject to }(\boldsymbol{w}^T \boldsymbol{x}_i+\gamma)y_i\geq 1- \varepsilon_i,  \varepsilon_i \geq 0,\: \forall i=1,\cdots,n \end{equation}$$ 其中$C>0$是個用以控制邊界錯誤的調節參數,而$\boldsymbol{\varepsilon}_i$ 是第$i$實例的錯誤量,此變量在最佳化領域亦稱為slack variable (鬆弛變量)。大的$C$值逼使$\sum \varepsilon_i$小,使得性能趨近於硬性決策。

Soft margin
上圖中點2,7,9落在邊界上,點1,8落在邊界的另邊但沒超過超平面,點11,12落到超平面的另邊,這些點都是支撐向量。上述最佳化方程式求解相當複雜,一般可透過所謂的對偶最佳化 (Dual optimization)求解,而其解僅包含訓練點間的內積(inner product),點$x$ 和${x}'$內積是定義成 $$\begin{equation} \left \langle \boldsymbol{x} , \boldsymbol{{x}}'  \right \rangle=\sum_{i=1}^{p}x_i{x}'_i \end{equation},$$ 其中 $p$ 是訓練點的維度。所以線性SVC可表示成 $$\begin{equation} f(\boldsymbol{x})=\gamma +\sum_{i=1}^{n}\alpha _i \left \langle \boldsymbol{x} , \boldsymbol{x}_i  \right \rangle \end{equation},$$ $\boldsymbol{x}_i$是只第 $i$ 個訓練點,而 $\boldsymbol{x}$ 是要帶入測試的點。而要估計$\gamma$ 和 $ \alpha _1, \cdots ,\alpha _n$ 僅需求所兩兩的內積。而$\alpha_i$中也僅有當成support vector 的點不為0,其他點的$\alpha_i$是0。

∎ Support vector machine (SVM)
如果我們在求解$\alpha_i$ 或解  Eq. (4)時用一kernel (核)取代Eq. (3)所定義的內積,kernel 可寫成 $K(\boldsymbol{x},\boldsymbol{x}')$,這種操作方式的  SVC 就是所謂的 SVM。若是
$$K(\boldsymbol{x},\boldsymbol{x}')=\sum_{i=1}^{p}x_i{x}'_i $$ 則SVM 就是SVC。常用的kernel 有
$$K(\boldsymbol{x},\boldsymbol{x}')=(1+\sum_{i=1}^{p}x_ix_i' )^d$$ 上式的形式是polynomial kernel of degree $d$。也常見 $$K(\boldsymbol{x},\boldsymbol{x}')=\exp (-\gamma\sum_{i=1}^{p}(x_i-x_i')^2 )$$ 上述的形式是radial kernel。一般可說若採用的kernel是非線性,那麼就是SVM,若是線性則是SVC。

∎ sklean 實例 下列程式import package
import pandas as pd
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
from sklearn.metrics import confusion_matrix
%matplotlib inline
def plot_svc(svc, X, y, h=0.02, pad=0.25):
    x_min, x_max = X[:, 0].min()-pad, X[:, 0].max()+pad
    y_min, y_max = X[:, 1].min()-pad, X[:, 1].max()+pad
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
    Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.2)
    plt.scatter(X[:,0], X[:,1], s=70, c=y, cmap=mpl.cm.Paired)
    # Support vectors indicated in plot by vertical lines
    sv = svc.support_vectors_
    plt.scatter(sv[:,0], sv[:,1], c='k', marker='x', s=100, linewidths='1')
    plt.xlim(x_min, x_max)
    plt.ylim(y_min, y_max)
    plt.xlabel('X1')
    plt.ylabel('X2')
    print('Number of support vectors: ', svc.support_.size)
上列最主要定義了一個plot_svc() function
from sklearn.svm import SVC
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
np.random.seed(5)
X = np.random.randn(20,2)
y = np.repeat([1,-1], 10)
# print(y)
X[y == -1] = X[y == -1]+1
plt.scatter(X[:,0], X[:,1], s=70, c=y, cmap=mpl.cm.Paired)
plt.xlabel('X1')
plt.ylabel('X2')
資料點
由圖看來並非線性可分離。
svc = SVC(C=1, kernel='linear')
svc.fit(X, y)
print(svc.support_.shape) 
print(svc.support_)
print(svc.coef_)
print(svc.intercept_)
plot_svc(svc, X, y)
(13,)
[10 11 13 14 15 16 17  0  1  2  4  6  8]
[[-0.73273926 -0.70326681]]
[0.57294413]
Number of support vectors:  13
SVC 輸出
叫用SVC並在constructer 宣告C=1以及 使用'linear' 為kernel。輸出顯示有13個support vectors。4,5,6行分別列印support 有那些點、權重係數以及截距。如果把C設小一點,則邊界區會變大,C值小則誤差的作用較少。調成0.1 得下圖
C調小邊界區變大
C調成0.1 邊界區變大,support 變成16個。若把kernel 改成radial function,在constructor 設C=1, kernel='rbf',
svc = SVC(C=1, kernel='rbf',gamma=5)
svc.fit(X, y)
print(svc.support_) 
plot_svc(svc, X, y)
[10 11 12 13 15 17 18 19  0  1  2  4  6  7  8  9]
Number of support vectors:  18
使用radial function
得support 是18點且兩類可用rbf分離開來,可見非線性的kernel可以解決不是線性可分離的問題。
參考文獻
http://www.science.smith.edu/~jcrouser/SDS293/labs/lab15-py.html

沒有留言:

張貼留言