ML：基礎技法學習
Package：scikit-learn
課程：
機器學習技法
簡介：第二講 dual SVM (support vector machine)
$$
\begin{align*}
\underset{b,\mathbf{w}}{min} &\ \ \ \frac{1}{2}\mathbf{w}^T\mathbf{w} \\
s. t. &\ \ \ y_n(\mathbf{w}^T\underset{\mathbf{\Phi} (\mathbf{x}_n)}{\underbrace{\mathbf{z}_n}}+b)\geq 1 \\
&\ \ \ for\ n=1,2,\cdots ,N
\end{align*}
$$
原始演算法
- \(Q=\begin{bmatrix}
0 & \mathbf{0}_{1\times \tilde{d}}\\
\mathbf{0}_{\tilde{d}\times 1} & \mathbf{I}_{\tilde{d}\times \tilde{d}}
\end{bmatrix};\
\mathbf{p}=\mathbf{0}_{1\times \tilde{d}+1};\
\mathbf{a}_n^T=y_n\begin{bmatrix}
1 & \mathbf{z}_n^T
\end{bmatrix};\
c_n=1\)
- \(\begin{bmatrix}
b\\
\mathbf{w}
\end{bmatrix}\Leftarrow \mathrm{QP}(\mathbf{Q},\mathbf{p},\mathbf{A},c)\)
- 得 \(g_{svm}(\mathbf{x})=sign(\mathbf{w}^T\mathbf{\Phi} (\mathbf{x})+b)\) with \(\begin{bmatrix} b\in \mathbb{R}\\ \mathbf{w} \in \mathbb{R}^\tilde{d}\end{bmatrix}\)
從上述式子，可發現 QP 需解 \(\tilde{d}+1\) 個變數 跟 N 個條件
但因特徵轉換，\(\tilde{d}\) 可能會很大甚至無限，導致計算過度複雜，甚至無法實現
所以此講的目的是，令變數的數量與資料量一樣，進而縮減其計算量，需搭配下一講
Dual Model
$$
\begin{align*}
\underset{\boldsymbol{\alpha}}{min} &\ \ \ \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\
subject\ to &\ \ \ \sum_{n=1}^{N}y_n \alpha _n=0;\\
&\ \ \ \alpha _n \geq0,for\ n=1,2,\cdots ,N
\end{align*}
$$
利用 Lagrange multipliers，隱藏限制條件，此處將 \(\lambda _n\) 用 \(\alpha _n\) 取代
$$
L(b,\mathbf{w},\boldsymbol\alpha)=\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n(\mathbf{w}^T\mathbf{z}_n+b))
$$
當 \(\underset{all\ \alpha _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\alpha)\) 會發現
- \((b,\mathbf{w})\) 違反限制條件時，會導致 \(1- y_n(\mathbf{w}^T\mathbf{z}_n+b)>0\)
又因 \(L(b,\mathbf{w},\boldsymbol\alpha) \) 針對 \(\alpha _n \) 取 max 的緣故，\(\alpha _n \) 越大越好，使得 \(L(b,\mathbf{w},\boldsymbol\alpha)\rightarrow \infty \)
- \((b,\mathbf{w})\) 符合限制條件時，會導致 \(1- y_n(\mathbf{w}^T\mathbf{z}_n+b) \leq 0\)
又因 \(L(b,\mathbf{w},\boldsymbol\alpha) \) 針對 \(\alpha _n \) 取 max 的緣故，\(\alpha _n \) 與 \(1- y_n(\mathbf{w}^T\mathbf{z}_n+b)\) 兩者至少有一個必須為 0，使得 \(L(b,\mathbf{w},\boldsymbol\alpha)\rightarrow \frac{1}{2}\mathbf{w}^T\mathbf{w} \)
故此式子與原本的求解一樣，如下，只是限制條件被隱藏到 max 中
$$
SVM\equiv \underset{b,\mathbf{w}}{min}\left (\underset{all\ \alpha _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\alpha) \right )=\underset{b,\mathbf{w}}{min}\left (\infty\ if\ violate;\frac{1}{2}\mathbf{w}^T\mathbf{w}\ if\ feasible \right )
$$
此時 \((b,\mathbf{w})\) 仍在式子最外面，如何把它跟裡面的 \(\alpha _n \) 交換呢？這樣才能初步得到 N 個變數的式子
任取一個 \(\boldsymbol{\alpha}'\) with \({\alpha}'_n \ge 0\)，因取 max 一定比任意還大，可得下式
\(\underset{b,\mathbf{w}}{min}\left (\underset{all\ \alpha _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\alpha) \right ) \geq \underset{b,\mathbf{w}}{min}\ L(b,\mathbf{w},\boldsymbol{\alpha}')\)
那如果對 \(\boldsymbol{\alpha}' \ge 0\) 取 max，也不影響此等式，如下
\(\underset{b,\mathbf{w}}{min}\left (\underset{all\ \alpha _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\alpha) \right ) \geq \underset{Lagrange\ dual\ problem}{\underbrace{\underset{all\ {\alpha}' _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ L(b,\mathbf{w},\boldsymbol{\alpha}') \right )\overset{\boldsymbol{\alpha}'=\boldsymbol\alpha}{\rightarrow} \underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ L(b,\mathbf{w},\boldsymbol\alpha) \right )}}\)
比較直覺的想法，就像是「從最大的一群中取最小」一定 \(\ge\) 「從最小的一群中取最大」
$$
\underset{original(primal))\ SVM}{\underbrace{\underset{b,\mathbf{w}}{min}\left (\underset{all\ \alpha _n \geq 0}{max}\ L(b,\mathbf{w},\boldsymbol\alpha) \right )}} \geq \underset{Lagrange\ dual}{\underbrace{ \underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ L(b,\mathbf{w},\boldsymbol\alpha) \right )}}
$$
目前的關係稱作 \(\ge\) weak duality
但這還不夠，最好是 \(=\) strong duality，才能初步得到 N 個變數的式子
幸運的是，在 QP 中，只要滿足以下條件，便是 strong duality
- convex primal (原來的問題為 convex)
- feasible primal (原來的問題有解的，也就是線性可分)
- linear constraints (限制條件為線性的)
對於 SVM 滿足這些條件並不困難，故解以下的式子，如同解原本的式子
$$
\underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ \underset{L(b,\mathbf{w},\boldsymbol\alpha)}{\underbrace{\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n(\mathbf{w}^T\mathbf{z}_n+b))}} \right )
$$
但如何把內部的 \((b,\mathbf{w})\) 拿掉呢？
內部的問題，當最佳化時，必定符合
$$
\begin{align*}
\frac{\partial L(b,\mathbf{w},\boldsymbol\alpha)}{\partial b}&=0=-\sum_{n=1}^{N}\alpha _ny_n \Rightarrow \sum_{n=1}^{N}\alpha _ny_n=0\\
\frac{\partial L(b,\mathbf{w},\boldsymbol\alpha)}{\partial \mathbf{w}}&=\mathbf{0}=\mathbf{w}-\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \Rightarrow \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n
\end{align*}
$$
從以上的這些條件，可得
$$
\begin{align*}
dual&=\underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n(\mathbf{w}^T\mathbf{z}_n+b)) \right )\\
&= \underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n\mathbf{w}^T\mathbf{z}_n-y_nb) \right )\\
&= \underset{all\ \alpha _n \geq 0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n\mathbf{w}^T\mathbf{z}_n)-\sum_{n=1}^{N}\alpha _ny_n\cdot b \right )\\
[\because \sum_{n=1}^{N}\alpha _ny_n=0] &= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n(1- y_n\mathbf{w}^T\mathbf{z}_n) \right )\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \sum_{n=1}^{N}\alpha _ny_n\mathbf{w}^T\mathbf{z}_n \right )\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right )\\
[\because \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n] &= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w}}{min}\ \ \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n- \mathbf{w}^T\mathbf{w} \right )\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w}}{min}\ \ -\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_{n=1}^{N}\alpha _n \right )\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\left (\underset{b,\mathbf{w}}{min}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n \right )\\
[\because no\ b, \mathbf{w}\ remove\ min] &= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{max}\ \ -\frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2+\sum_{n=1}^{N}\alpha _n\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2}\left \| \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n \right \|^2-\sum_{n=1}^{N}\alpha _n\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n^T\left (\sum_{m=1}^{N}\alpha _my_m\mathbf{z}_m \right ) -\sum_{n=1}^{N}\alpha _n\\
&= \underset{all\ \alpha _n \geq 0,\ \sum_{n=1}^{N}\alpha _ny_n=0,\ \mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n}{min}\ \ \frac{1}{2} \sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n\alpha _my_ny_m\mathbf{z}_n^T\mathbf{z}_m -\sum_{n=1}^{N}\alpha _n\\
\end{align*}
$$
將限制條件移出，\(\mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n\) 只是求 \(\mathbf{w}\) 並不限制 \(\boldsymbol\alpha\)，可得
$$
\begin{align*}
\underset{\boldsymbol{\alpha}}{min} &\ \ \ \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\
subject\ to &\ \ \ \sum_{n=1}^{N}y_n \alpha _n=0;\\
&\ \ \ \alpha _n \geq0,for\ n=1,2,\cdots ,N
\end{align*}
$$
KKT(Karush-Kuhn-Tucker) Optimality Conditins
若最佳解 \((b,\mathbf{w},\boldsymbol\alpha)\) 同時滿足兩邊 primal & dual
則同時滿足以下條件
- primal feasible
- \(y_n(\mathbf{w}^T\mathbf{z}_n+b) \ge 1\) (原來問題的條件)
- dual feasible
- \(\alpha _n \ge 0\) (對偶問題的條件)
- dual-inner optimal
- \(\sum_{n=1}^{N}y_n\alpha _n=0\)，\(\mathbf{w}=\alpha _ny_n\mathbf{z}_n\) (推導過程中得到的最佳化條件)
- primal-inner optimal
- \(\alpha _n(1-y_n(\mathbf{w}^T\mathbf{z}_n+b))=0\)
(原來問題取 max 得到的條件，兩者必定至少一個為 0)
- 事實上，若滿足以上條件的 \((b,\mathbf{w},\boldsymbol\alpha)\)，則必為最佳解
此為充要條件
Dual Hard-Margin SVM Algorithm
-
利用 Quadratic Programming 解
(程式語言都有 QP Solver 的套件，
建議選擇特別為 SVM 設計的)
$$
\begin{align*}
&\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha _n \alpha _m y_ny_m\mathbf{z}_n^T\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\
&=\frac{1}{2}\sum_{n=1}^{N}\alpha _n y_n\mathbf{z}_n^T\sum_{m=1}^{N} \alpha _m y_m\mathbf{z}_m-\sum_{n=1}^{N}\alpha _n\\
&=\frac{1}{2}(\alpha _1 y_1\mathbf{z}_1+\alpha _2 y_2\mathbf{z}_2+\cdots +\alpha _N y_N\mathbf{z}_N)^T(\alpha _1 y_1\mathbf{z}_1+\alpha _2 y_2\mathbf{z}_2+\cdots +\alpha _N y_N\mathbf{z}_N)-\sum_{n=1}^{N}\alpha _n\\
&=\frac{1}{2}(
\begin{bmatrix}y_1\mathbf{z}_1 & y_2\mathbf{z}_2 & \cdots & y_N\mathbf{z}_N\end{bmatrix}_{\tilde{d} \times N}\boldsymbol\alpha_{N \times 1})^T(\begin{bmatrix}y_1\mathbf{z}_1 & y_2\mathbf{z}_2 & \cdots & y_N\mathbf{z}_N\end{bmatrix}_{\tilde{d} \times N}\boldsymbol\alpha_{N \times 1})-\mathbf{1}_{N \times 1}^T\boldsymbol\alpha_{N \times 1}\\
&=\frac{1}{2}(\boldsymbol\alpha_{N \times 1})^T
\begin{bmatrix}y_1\mathbf{z}_1 \\ y_2\mathbf{z}_2 \\ \cdots \\ y_N\mathbf{z}_N\end{bmatrix}_{N \times \tilde{d}}\begin{bmatrix}y_1\mathbf{z}_1 & y_2\mathbf{z}_2 & \cdots & y_N\mathbf{z}_N\end{bmatrix}_{\tilde{d} \times N}\boldsymbol\alpha_{N \times 1}-(\mathbf{1}_{N \times 1})^T\boldsymbol\alpha_{N \times 1}\\
&= \frac{1}{2}\boldsymbol\alpha^T \mathbf{Q} \boldsymbol\alpha+\mathbf{p}^T\boldsymbol\alpha\\
\end{align*}
$$
\(=\) 可以看作兩個條件 \(\le\) 和 \(\ge\)
$$
\sum_{n=1}^{N}y_n \alpha _n=0
\Rightarrow
\left\{\begin{matrix}
\sum_{n=1}^{N}y_n \alpha _n \ge 0 \\
\sum_{n=1}^{N}y_n \alpha _n \le 0 \\
\end{matrix}\right.
\Rightarrow
\left\{\begin{matrix}
&\sum_{n=1}^{N}y_n \alpha _n \ge 0 \\
-&\sum_{n=1}^{N}y_n \alpha _n \ge 0 \\
\end{matrix}\right.
\Rightarrow
\left\{\begin{matrix}
&\mathbf{y}^T \boldsymbol\alpha \ge 0 \\
-&\mathbf{y}^T \boldsymbol\alpha \ge 0 \\
\end{matrix}\right.
\Rightarrow
\left\{\begin{matrix}
&\mathbf{a}_{\geq }^T \boldsymbol\alpha \ge c_{\geq } \\
&\mathbf{a}_{\leq }^T \boldsymbol\alpha \ge c_{\leq } \\
\end{matrix}\right.
$$
$$
\begin{align*}
\alpha _n &\geq0,for\ n=1,2,\cdots ,N\\
\mathbf{U}_n\boldsymbol\alpha &\geq0,for\ n=1,2,\cdots ,N\\
\mathbf{U}_1 &= \begin{bmatrix}1 & 0 & \cdots & 0\end{bmatrix}\\
\mathbf{U}_2 &= \begin{bmatrix}0 & 1 & \cdots & 0\end{bmatrix}\\
&\vdots \\
\mathbf{U}_N &= \begin{bmatrix}0 & 0 & \cdots & 1\end{bmatrix}\\
\mathbf{a}_n^T\boldsymbol\alpha &\geq c_n,for\ n=1,2,\cdots ,N\\
\end{align*}
$$
- dual SVM 的 \(Q\) 通常稱作 \(Q_D\)
- \(Q_D\) 內的值幾乎不為 0，需使用專門 for SVM 的 QP solver
- 如何得 \(\mathbf{w}\)
- \(\mathbf{w}=\sum_{n=1}^{N}\alpha _ny_n\mathbf{z}_n\)
- 如何得 b
- 任意 \(\alpha _n > 0\)，則 \(1-y_n(\mathbf{w}^T\mathbf{z}_n+b)=0\) (by KKT)
-
\(b = y_n-\mathbf{w}^T\mathbf{z}_n\)
$$
\begin{align*}
0&=1-y_n(\mathbf{w}^T\mathbf{z}_n+b)\\
y_nb &= 1-y_n\mathbf{w}^T\mathbf{z}_n\\
b &= \frac{1-y_n\mathbf{w}^T\mathbf{z}_n}{y_n}\\
if\ y_n&=\pm 1\\
b &= y_n-\mathbf{w}^T\mathbf{z}_n\\
\end{align*}
$$
- \(\alpha _n > 0\) 的意義
- 只有 \(\alpha _n > 0\) 才會影響 \(\mathbf{w}\) 的值
- \(\alpha _n > 0\) 的 \(\mathbf{z}_n\) 必定落在邊界，因 \(y_n(\mathbf{w}^T\mathbf{z}_n+b)=1\)
- 只有 \(\alpha _n > 0\) 的 \(\mathbf{z}_n\) 才稱作 support vectors
落在邊界上的 \(\mathbf{z}_n\) 不見得是 support vectors
- SV \(\subseteq \mathbf{z}_n\)位於邊界
SVM 概念
- 除了 SV 以外的資料皆是無用的
- \(\mathbf{w}_{svm}=\sum_{n=1}^{N}\alpha _n(y_n\mathbf{z}_n)\)
- \( \mathbf{w}\) 是由 SV 所表示出來
- \(\mathbf{w}\) 為 \(y_n \mathbf{z}_n\) 的線性組合
- 稱為 \(\mathbf{w}\) 可被資料所表示
- \( \mathbf{w}_0 =0\) 時，以下的演算法也是如此的
- 適用範圍
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
# phi = (x1, x2, x1^4)
Z = np.c_[X[:, 0], X[:, 1], X[:, 0]**4]
# C 越大表示越無法容忍錯誤，故設定一很大的值 for hard margin
g_svm = svm.SVC(kernel='linear', C=1e10)
# 訓練
g_svm.fit(Z, Y)
# 得到係數，為 wx+b
w = g_svm.coef_[0]
b = g_svm.intercept_[0]
# 方程式 y=(-w1*x-w3*x^4-b)/w2
xx = np.linspace(-5, 5)
yy = (-w[0] * xx -w[2] * (xx**4) - b)/ w[1]
# 得到第一個 support vectors
p = g_svm.support_vectors_[0]
# 參數不變，求截距為 b1 = -wx
yy_down = (-w[0] * xx -w[2] * (xx**4) + np.dot(w, [p[0], p[1], p[0]**4]))/ w[1]
# 得到最後一個 support vectors，與上面相反的 y
p = g_svm.support_vectors_[-1]
# 參數不變，求截距為 b = -wx
yy_up = (-w[0] * xx -w[2] * (xx**4) + np.dot(w, [p[0], p[1], p[0]**4]))/ w[1]
# 畫圖
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()
參考
【整理】深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件
sklearn.svm.SVC
留言
張貼留言