[ML] 機器學習技法：第一講 linear SVM

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第一講 linear SVM (support vector machine)

根據 PLA
以下三個圖皆符合條件，但何者最好呢？相信大部分的人都會選擇右邊的圖，因為 margin 最大

基本 Model

$$\begin{array}{rl}\underset{b,\mathbf{w}}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}\\ subjectto& y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\ge 1foralln\end{array}$$ 注意：此時的 $\mathbf{w}$ 不包含 $w_0$，$\mathbf{x}$ 也不包含 $x_0=1$，而 $b=w_0$

首先，可以先想成，當線性可分時，要取出最大 margin 的那條線
而 margin 的定義，為所有資料點遠離線的最小距離
$$\begin{array}{rl}\underset{\stackrel{\mathbf{~}}{\mathbf{w}}}{max}& margin(\stackrel{\mathbf{~}}{\mathbf{w}})\\ subjectto& every{y}_n{\stackrel{\mathbf{~}}{\mathbf{w}}}^T{\mathbf{x}}_n>0\\ & margin(\stackrel{\mathbf{~}}{\mathbf{w}})=\underset{n=1,2,\cdots ,N}{min}distance({\mathbf{x}}_n,\stackrel{\mathbf{~}}{\mathbf{w}})\end{array}$$ 假設變數如下
$$\begin{array}{rl}\stackrel{\mathbf{~}}{\mathbf{w}}& =\left[\begin{array}{c}{w}_0=b\\ \mathbf{w}\end{array}\right]\\ \mathbf{x}& =\left[\begin{array}{c}{x}_1\\ ⋮\\ x_d\end{array}\right]\end{array}$$ 如何求距離呢？
如下圖，可看到距離即是 $\mathbf{x}-{\mathbf{x}}^{\prime }$ 投影在法向量的長度

法向量為 $\mathbf{w}$

$$\begin{array}{rl}{\mathbf{w}}^T{\mathbf{x}}^{\prime }& =-b\\ {\mathbf{w}}^T{\mathbf{x}}^{″}& =-b\\ \\ {\mathbf{w}}^T({\mathbf{x}}^{″}-{\mathbf{x}}^{\prime })& =0\end{array}$$ ${\mathbf{x}}^{″}-{\mathbf{x}}^{\prime }$ 即是平面上的向量
只有法向量的內積為 0，故 $\mathbf{w}$ 為法向量

$$\begin{array}{rl}disance(\mathbf{x},b,\mathbf{w})& =|\frac{{\mathbf{w}}^T}{\Vert \mathbf{w}\Vert }(\mathbf{x}-{\mathbf{x}}^{\prime })|\\ & =|\frac{1}{\Vert \mathbf{w}\Vert }({\mathbf{w}}^T\mathbf{x}-{\mathbf{w}}^T{\mathbf{x}}^{\prime })|\\ & =|\frac{1}{\Vert \mathbf{w}\Vert }({\mathbf{w}}^T\mathbf{x}+b)|\\ & =\frac{1}{\Vert \mathbf{w}\Vert }|{\mathbf{w}}^T\mathbf{x}+b|\end{array}$$ 因 $y_n$ 只差在正負值，大小一樣，不影響 margin 取最小值，所以可用來拿掉絕對值 $$\begin{array}{rl}disance({\mathbf{x}}_n,b,\mathbf{w})& =\frac{1}{\Vert \mathbf{w}\Vert }|{\mathbf{w}}^T{\mathbf{x}}_{\mathbf{n}}+b|\\ \because y_n({\mathbf{w}}^T\mathbf{x}+b)& >0and{y}_n=\pm Value\\ \underset{n=1,2,\cdots ,N}{min}distance({\mathbf{x}}_n,\stackrel{\mathbf{~}}{\mathbf{w}})& \Rightarrow \underset{n=1,2,\cdots ,N}{min}\frac{1}{\Vert \mathbf{w}\Vert }{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\end{array}$$ 故可重新定義 model
$$\begin{array}{rl}\underset{b,\mathbf{w}}{max}& margin(b,\mathbf{w})\\ subjectto& every{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)>0\\ & margin(b,\mathbf{w})=\underset{n=1,2,\cdots ,N}{min}\frac{1}{\Vert \mathbf{w}\Vert }{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\end{array}$$ 平面方程式，不因 scaling 而有所不同，如下平面是一樣的
${\mathbf{w}}^T{\mathbf{x}}_n+b=0\iff 100{\mathbf{w}}^T{\mathbf{x}}_n+100b=0$
那麼利用一特別的 scaling 使得 最小的值為 1 (當為 1 時，$\mathbf{x}$ 其實就在邊界 )
$$\underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=1\Rightarrow margin(b,\mathbf{w})=\frac{1}{\Vert \mathbf{w}\Vert }$$ 可再重新定義 model，且因為 $\underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=1$
所以 $every{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)>0$ 可以去掉
$$\begin{array}{rl}\underset{b,\mathbf{w}}{max}& \frac{1}{\Vert \mathbf{w}\Vert }\\ subjectto& \underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=1\end{array}$$ 可以再被取代嗎？如下 $$\begin{array}{rl}\underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)& =1\\ \stackrel{?}{\Rightarrow }{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)& \ge 1\end{array}$$ 因 $y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\ge 1$ 比較寬鬆
要確保即使放鬆條件，解出來的解仍落在 $\underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=1$ 之中
試想一情況，假設解出來的解令 $y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=a>1$
那麼此時最佳解為 $(b,\mathbf{w})$，但因為 scaling 的關係，可得另一個解為 $(\frac{b}{a},\frac{\mathbf{w}}{a})$
結果發現後者比前者在 $\underset{b,\mathbf{w}}{max}\frac{1}{\Vert \mathbf{w}\Vert }$ 還最佳化
矛盾，故即使使用 $y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\ge 1$ 也不會令解落在 $\underset{n=1,2,\cdots ,N}{min}{y}_n({\mathbf{w}}^T{\mathbf{x}}_n+b)=1$ 之外
再將 max 改一下
$$\begin{array}{rl}\underset{b,\mathbf{w}}{max}\frac{1}{\Vert \mathbf{w}\Vert }& \Rightarrow \underset{b,\mathbf{w}}{min}\Vert \mathbf{w}\Vert \\ & \Rightarrow \underset{b,\mathbf{w}}{min}{\mathbf{w}}^T\mathbf{w}\\ & \Rightarrow \underset{b,\mathbf{w}}{min}\frac{1}{2}{\mathbf{w}}^T\mathbf{w}\end{array}$$ 故得 $$\begin{array}{rl}\underset{b,\mathbf{w}}{min}& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}\\ subjectto& y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)\ge 1foralln\end{array}$$

SVM 命名簡單說明

可以看到只有在邊緣的點，才會影響得到的解
因此將這些點稱作 support vector，由這些點支撐出來的 margin

Linear Hard-Margin SVM Algorithm

• 利用 Quadratic Programming 解 (程式語言都有 QP Solver 的套件)
  

  
  $$\begin{array}{rl}\left[\begin{array}{c}b\\ \mathbf{w}\end{array}\right]& =\mathbf{u}\\ \\ \mathbf{w}& =\left[\begin{array}{cc}{\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}\\ b& =\left[\begin{array}{cc}1& {\mathbf{0}}_{1\times d}\end{array}\right]\mathbf{u}\\ \\ \frac{1}{2}{\mathbf{w}}^T\mathbf{w}& =\frac{1}{2}(\left[\begin{array}{cc}{\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}{)}^T\left[\begin{array}{cc}{\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}\\ & =\frac{1}{2}{\mathbf{u}}^T\left[\begin{array}{c}{\mathbf{0}}_{1\times d}\\ {\mathbf{I}}_{d\times d}\end{array}\right]\left[\begin{array}{cc}{\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}\\ & =\frac{1}{2}{\mathbf{u}}^T\left[\begin{array}{cc}0& {\mathbf{0}}_{1\times d}\\ {\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}\\ & =\frac{1}{2}{\mathbf{u}}^T\left[\begin{array}{cc}0& {\mathbf{0}}_{1\times d}\\ {\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}+{\mathbf{0}}_{1\times d+1}\mathbf{u}\\ & =\frac{1}{2}{\mathbf{u}}^T\mathbf{Q}\mathbf{u}+{\mathbf{p}}^T\mathbf{u}\\ \\ y_n({\mathbf{w}}^T{\mathbf{x}}_n+b)& =y_n((\left[\begin{array}{cc}{\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right]\mathbf{u}{)}^T{\mathbf{x}}_n+\left[\begin{array}{cc}1& {\mathbf{0}}_{1\times d}\end{array}\right]\mathbf{u})\\ & =y_n({\mathbf{u}}^T\left[\begin{array}{c}{\mathbf{0}}_{1\times d}\\ {\mathbf{I}}_{d\times d}\end{array}\right]{\mathbf{x}}_n+\left[\begin{array}{cc}1& {\mathbf{0}}_{1\times d}\end{array}\right]\mathbf{u})\\ & =y_n({\mathbf{u}}^T\left[\begin{array}{c}0\\ {\mathbf{x}}_n\end{array}\right]+\left[\begin{array}{cc}1& {\mathbf{0}}_{1\times d}\end{array}\right]\mathbf{u})\\ & =y_n(\left[\begin{array}{cc}0& {\mathbf{x}}_n^T\end{array}\right]\mathbf{u}+\left[\begin{array}{cc}1& {\mathbf{0}}_{1\times d}\end{array}\right]\mathbf{u})\\ & =y_n\left[\begin{array}{cc}1& {\mathbf{x}}_n^T\end{array}\right]\mathbf{u}\\ & ={\mathbf{a}}_n^T\mathbf{u}\\ \\ c_n& =1\\ M& =N\end{array}$$
• 演算法
1. $Q=\left[\begin{array}{cc}0& {\mathbf{0}}_{1\times d}\\ {\mathbf{0}}_{d\times 1}& {\mathbf{I}}_{d\times d}\end{array}\right];\mathbf{p}={\mathbf{0}}_{1\times d+1};{\mathbf{a}}_n^T=y_n\left[\begin{array}{cc}1& {\mathbf{x}}_n^T\end{array}\right];c_n=1$
2. $\left[\begin{array}{c}b\\ \mathbf{w}\end{array}\right]\Leftarrow \mathrm{QP}(\mathbf{Q},\mathbf{p},\mathbf{A},c)$
3. 得 $g_{svm}(\mathbf{x})=sign({\mathbf{w}}^T\mathbf{x}+b)$ with $\left[\begin{array}{c}b\in \mathbb{R}\\ \mathbf{w}\in {\mathbb{R}}^d\end{array}\right]$
• 字詞說明
• hard-margin => 線性可分，無違反的資料
• linear => 原始的 $x_n$，無經過任何轉換
• 非線性做法
• ${\mathbf{z}}_n=\mathbf{\Phi }({\mathbf{x}}_n)$

SVM 優點

• 一種 Regularization 
• 只是反過來求 ${\mathbf{w}}^T\mathbf{w}$ 的最小值
• 條件為 $E_{in}=0$ 甚至還多了相乘必須等於 1 的條件
• 降低 VC dimention
• 限定 $margin(b,\mathbf{w})=\frac{1}{\Vert \mathbf{w}\Vert }\ge \rho$
• 原本可以 shatter 的 dimention 會因此無法 shatter
  
• 若資料分佈在半徑為 $R$ 的圓內，就二分法而言
  $$d_{vc}(A_{\rho })\le min(\frac{R^2}{{\rho }^2},d)+1\le d+1$$
• 降低非線性的複雜度

程式碼

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
 
# 建立 40 筆資料
np.random.seed(0)
# np.r_ 詳細說明 https://www.ptt.cc/bbs/Python/M.1490169034.A.2D4.html
# np.r_ 的功能為新建立一個 row 陣列
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
Y = [0] * 20 + [1] * 20
 
# C 越大表示越無法容忍錯誤，故設定一很大的值 for hard margin
g_svm = svm.SVC(kernel='linear', C=1e10)
# 訓練
g_svm.fit(X, Y)
 
# 得到係數，為 wx+b
w = g_svm.coef_[0]
b = g_svm.intercept_[0]
# 直線方程式 y=a1*x+b1
a1 = -w[0] / w[1]
b1 = -b / w[1]
xx = np.linspace(-5, 5)
yy = a1 * xx + b1
 
# 得到第一個 support vectors
p = g_svm.support_vectors_[0]
# 斜率不變，求截距為 b1 = y-a1*x
yy_down = a1 * xx + (p[1] - a1 * p[0])
 
# 得到最後一個 support vectors，與上面相反的 y
p = g_svm.support_vectors_[-1]
# 斜率不變，求截距為 b1 = y-a1*x
yy_up = a1 * xx + (p[1] - a1 * p[0])
 
# 畫圖
plt.plot(xx, yy, 'k-')
plt.plot(xx, yy_down, 'k--')
plt.plot(xx, yy_up, 'k--')
 
# 畫出所有點
plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=plt.cm.Paired)
# 將 support vector 標示出來
plt.scatter(g_svm.support_vectors_[:, 0], g_svm.support_vectors_[:, 1], color='g', linewidths=3, linestyle='-', s=100, facecolors='none')
 
plt.show()

參考資料

sklearn.svm.SVC