ML：基礎技法學習
Package：scikit-learn
課程：
機器學習技法
簡介：第一講 linear SVM (support vector machine)
根據
PLA
以下三個圖皆符合條件，但何者最好呢？相信大部分的人都會選擇右邊的圖，因為 margin 最大
基本 Model
$$
\begin{align*}
\underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}\\
subject\ to &\ \ y_n(\mathbf{w}^T\mathbf{x}_n+b) \geq 1\ for\ all\ n
\end{align*}
$$
注意：此時的 \(\mathbf{w}\) 不包含 \(w_0\)，\(\mathbf{x}\) 也不包含 \(x_0=1\)，而 \(b=w_0\)
首先，可以先想成，當線性可分時，要取出最大 margin 的那條線
而 margin 的定義，為所有資料點遠離線的最小距離
$$
\begin{align*}
\underset{\mathbf{\tilde{w}}}{max} &\ \ margin(\mathbf{\tilde{w}})\\
subject\ to &\ \ every\ y_n\mathbf{\tilde{w}}^T\mathbf{x}_n > 0\\
&\ \ margin(\mathbf{\tilde{w}})=\underset{n=1,2,\cdots ,N}{min}\ distance(\mathbf{x}_n,\mathbf{\tilde{w}})
\end{align*}
$$
假設變數如下
$$
\begin{align*}
\mathbf{\tilde{w}} &=\begin{bmatrix}
w_0=b\\
\mathbf{w}
\end{bmatrix}\\
\mathbf{x}&=\begin{bmatrix}
x_1\\
\vdots \\
x_d
\end{bmatrix}
\end{align*}
$$
如何求距離呢？
如下圖，可看到距離即是 \(\mathbf{x}-{\mathbf{x}}'\) 投影在法向量的長度
法向量為 \(\mathbf{w}\)
$$
\begin{align*}
\mathbf{w}^T{\mathbf{x}}' &= -b\\
\mathbf{w}^T{\mathbf{x}}''&= -b\\
\\
\mathbf{w}^T({\mathbf{x}}''-{\mathbf{x}}') &= 0\\
\end{align*}
$$
\({\mathbf{x}}''-{\mathbf{x}}'\) 即是平面上的向量
只有法向量的內積為 0，故 \(\mathbf{w}\) 為法向量
$$
\begin{align*}
disance(\mathbf{x},b,\mathbf{w}) &= \left | \frac{\mathbf{w}^T}{\left \| \mathbf{w} \right \|} (\mathbf{x}-{\mathbf{x}}')\right |\\
&= \left | \frac{1}{\left \| \mathbf{w} \right \|} (\mathbf{w}^T\mathbf{x}-\mathbf{w}^T{\mathbf{x}}')\right |\\
&= \left | \frac{1}{\left \| \mathbf{w} \right \|} (\mathbf{w}^T\mathbf{x}+b)\right |\\
&= \frac{1}{\left \| \mathbf{w} \right \|} \left | \mathbf{w}^T\mathbf{x}+b\right |\\
\end{align*}
$$
因 \(y_n\) 只差在正負值，大小一樣，不影響 margin 取最小值，所以可用來拿掉絕對值
$$
\begin{align*}
disance(\mathbf{x}_n,b,\mathbf{w}) &= \frac{1}{\left \| \mathbf{w} \right \|} \left | \mathbf{w}^T\mathbf{x_n}+b\right |\\
\because y_n(\mathbf{w}^T\mathbf{x}+b) &> 0 \ and\ y_n=\pm Value \\
\underset{n=1,2,\cdots ,N}{min}\ distance(\mathbf{x}_n,\mathbf{\tilde{w}})
&\Rightarrow \underset{n=1,2,\cdots ,N}{min}\ \frac{1}{\left \| \mathbf{w} \right \|} y_n(\mathbf{w}^T\mathbf{x}_n+b)\\
\end{align*}
$$
故可重新定義 model
$$
\begin{align*}
\underset{b,\mathbf{w}}{max} &\ \ margin(b,\mathbf{w})\\
subject\ to &\ \ every\ y_n(\mathbf{w}^T\mathbf{x}_n+b) > 0\\
&\ \ margin(b,\mathbf{w})=\underset{n=1,2,\cdots ,N}{min}\ \frac{1}{\left \| \mathbf{w} \right \|} y_n(\mathbf{w}^T\mathbf{x}_n+b)
\end{align*}
$$
平面方程式，不因 scaling 而有所不同，如下平面是一樣的
\(\mathbf{w}^T\mathbf{x}_n+b=0 \Leftrightarrow 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}{\left \| \mathbf{w} \right \|}
$$
可再重新定義 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{align*}
\underset{b,\mathbf{w}}{max} &\ \frac{1}{\left \| \mathbf{w} \right \|}\\
subject\ to &\ \ \underset{n=1,2,\cdots ,N}{min}\ y_n(\mathbf{w}^T\mathbf{x}_n+b)=1
\end{align*}
$$
可以再被取代嗎？如下
$$
\begin{align*}
\underset{n=1,2,\cdots ,N}{min}\ y_n(\mathbf{w}^T\mathbf{x}_n+b)&=1\\
\overset{?}{\Rightarrow} y_n(\mathbf{w}^T\mathbf{x}_n+b)&\geq 1 \\
\end{align*}
$$
因 \(y_n(\mathbf{w}^T\mathbf{x}_n+b)\geq 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}{\left \| \mathbf{w} \right \|}\) 還最佳化
矛盾，故即使使用 \(y_n(\mathbf{w}^T\mathbf{x}_n+b)\geq 1\) 也不會令解落在 \(\underset{n=1,2,\cdots ,N}{min}\ y_n(\mathbf{w}^T\mathbf{x}_n+b)=1\) 之外
再將 max 改一下
$$
\begin{align*}
\underset{b,\mathbf{w}}{max} \ \frac{1}{\left \| \mathbf{w} \right \|} &\Rightarrow \underset{b,\mathbf{w}}{min} \ \left \| \mathbf{w} \right \|\\
&\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{align*}
$$
故得
$$
\begin{align*}
\underset{b,\mathbf{w}}{min} &\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}\\
subject\ to &\ \ y_n(\mathbf{w}^T\mathbf{x}_n+b) \geq 1\ for\ all\ n
\end{align*}
$$
SVM 命名簡單說明
可以看到只有在邊緣的點，才會影響得到的解
因此將這些點稱作 support vector，由這些點支撐出來的 margin
Linear Hard-Margin SVM Algorithm
SVM 優點
- 一種 Regularization
- 只是反過來求 \(\mathbf{w}^T\mathbf{w}\) 的最小值
- 條件為 \(E_{in}=0\) 甚至還多了相乘必須等於 1 的條件
- 降低 VC dimention
- 限定 \(margin(b,\mathbf{w})=\frac{1}{\left \| \mathbf{w} \right \|} \geq \rho \)
- 原本可以 shatter 的 dimention 會因此無法 shatter
- 若資料分佈在半徑為 \(R\) 的圓內，就二分法而言
$$d_{vc}(A_\rho )\leq min\ (\frac{R^2}{\rho ^2},d)+1\leq 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
留言
張貼留言