[學習筆記] 機器學習: 支援向量機 (Machine Learning: Support Vector Machines)

和 logistic regression 及 neural network 相比, support vector machines (SVM) 有時候能夠提出更簡潔, 更強大的方式, 來學習複雜的非線性函式.

我們以 logistic regression 為基礎來瞭解 support vector machine 的本質.



\(g(z) = \frac{1}{1+e^{-z}} \)

\(z = \theta^T x\)

\(h_{\theta}(x) = g(z) = g(\theta^T x) = \frac{1}{1+e^{-\theta^T x}}\)

對於 \(y = 1\) 的 training example, 我們希望 \(h_{\theta}(x) \approx 1 \rightarrow \theta^T x \gg 0 \)

對於 \(y = 0\) 的 training example, 我們希望 \(h_{\theta}(x) \approx 0 \rightarrow \theta^T x \ll 0 \)

\( Cost(h_{\theta}(x), y) = -y log(h_{\theta}(x)) - (1-y) log(1- h_{\theta}(x)) \)

\( = -y log(\frac{1}{1+e^{-\theta^T x}}) - (1-y) log(1- \frac{1}{1+e^{-\theta^T x}}) \)

If \(y = 1\), \( Cost(h_{\theta}(x), y) = -log(\frac{1}{1+e^{-z}}) \)
Logistic regression 的 cost function 為下圖黑色曲線, support vector machine 的 cost function \( cost_1(z) \) 為下圖橘色線段.

Support vector machine 的 cost function 以 2 條直線來取代 logistic regression 的 cost function 的曲線, 如此計算複雜度降低許多.


If \(y = 0\), \( Cost(h_{\theta}(x), y) = -log(1- \frac{1}{1+e^{-z}}) \)
Logistic regression 的 cost function 為下圖黑色曲線, support vector machine 的 cost function \( cost_0(z) \) 為下圖橘色線段.


Cost function for logistic regression:
\( \frac{1}{m}\sum_{i=1}^{m}[y^{(i)} (-log(h_{\theta}(x^{(i)}))) + (1-y^{(i)}) (-log(1- h_{\theta}(x^{(i)})))] + \frac{\lambda}{2m}\sum_{j=1}^{n}\theta_j^2 \)
Cost function for support vector machine:
\( C\sum_{i=1}^{m} [y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)})] + \frac{1}{2}\sum_{j=1}^{n}\theta_j^2 \)

1. m 是常數, 因此把它移除, 對於 minimize cost function 的結果並不會有影響.

2. \(C\) 的作用相當於 \( \frac{1}{\lambda} \) 的作用.
Hypothesis for support vector machine:
\( h_{\theta}(x) = \begin{cases}
1, \text{if } \theta^T x \geq 0 \\
0, \text{otherwise}
\end{cases}
\)

Large Margin Intuition


Cost function for support vector machine:
\( C\sum_{i=1}^{m} [y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)})] + \frac{1}{2}\sum_{j=1}^{n}\theta_j^2 \)


為了 minimize cost function:
if \(y = 1\), we want \(z = \theta^T x \geq 1 \) (not just \( \geq 0 \) ).

if \(y = 0\), we want \(z = \theta^T x \leq -1 \) (not just \( \lt 0 \) ).
假設 C 很大, 根據上述的 optimization objective, cost function 的第 1 個 summation 會趨近於 0, 留下第 2 個 summation:
\( \frac{1}{2}\sum_{j=1}^{n}\theta_j^2 \)
進一步的 optimization objective 是優化上述的 cost function.

因此 support vector machine 會有下圖所示的特性:


上圖是 linearly separable case, 如上圖所示, 綠色及黑色的 hypothesis function (or decision boundary) 都可以區分紅色及藍色的 examples, 但 support vector machine 所 learn 到的黑色的 hypothesis function 會有較大的 margin, 因此 support vector machines 有時也被稱為 large margin classifiers.

這樣的 margin 讓 support vector machine 有比較好的 robustness, 因為它有助於讓不同類別的 data 盡可能地分離開來.



上圖是有 outlier 的情況. 如果 C 過大, hypothesis function (or decision boundary) 會對於 outlier 過於 sensitive, 因此會是綠色線段. 如果 C 不過大, hypothesis function 則不會對於 outlier 過於 sensitive, 因此會是紫色線段.

透過 Landmark 及 Kernel 來為 SVM 定義 features




如果有如上圖的 training set, 我們想要找到一個 nonlinear decision boundary 來區分 positive 及 negative examples, 如圖中的藍色曲線.

因此我們可能會選擇類似如下的 hypothesis function:
\( h_{\theta}(x) = \begin{cases}
1, \text{if } \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1 x_2 + \theta_4 x_1^2 + \theta_5 x_2^2 +... \geq 0 \\
0, \text{otherwise}
\end{cases}
\)
我們採用下列的 notation:
\( f_1 = x_1, f_2 = x_2, f_3 = x_1 x_2, f_4 = x_1^2, f_5 = x_2^2, ... \)
我們要怎麼選擇合適的 features \( f_1, f_2, f_3, ...\) 呢?



假設我們設定了 3 個 landmark (先以 3 為例, 數量可以延伸), 對於 training example \(x\), 我們根據 \(x\) 和 landmarks \(l^{(1)}, l^{(2)}, l^{(3)}\) 的距離 (proximity) 來計算新定義的 features.
\( f_1 = similarity(x, l^{(1)}) = exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2}) \)

\( f_2 = similarity(x, l^{(2)}) = exp(-\frac{||x-l^{(2)}||^2}{2\sigma^2}) \)

\( f_3 = similarity(x, l^{(3)}) = exp(-\frac{||x-l^{(3)}||^2}{2\sigma^2}) \)

similarity function: kernel, 也可以表示為 \( k(x, l^{(i)}) \)

上述的 exponential term: Gaussian kernel

Octave implementation:
function sim = gaussianKernel(x1, x2, sigma)
d = x1-x2;
sim = exp(-(d'*d)/(2*sigma^2));
Gaussian kernel 的作用:
\( f_1 = similarity(x, l^{(1)}) = exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2}) = exp(-\frac{\sum_{j=1}^{n}(x_j-l_j^{(1)})^2}{2\sigma^2}) \)

如果 \( x \) 很接近 \( l^{(1)} \), \(f_1 \approx exp(-\frac{0^2}{2\sigma^2}) \approx 1 \)

如果 \( x \) 距離 \( l^{(1)} \) 很遠, \(f_1 \approx exp(-\frac{(large number)^2}{2\sigma^2}) \approx 0 \)


我們根據新的方式定義了 3 個 landmark 及 hypothesis function \( \theta_0 + \theta_1 f_1 + \theta_2 f_2 + \theta_3 f_3 \).
Predict "1" when \( \theta_0 + \theta_1 f_1 + \theta_2 f_2 + \theta_3 f_3 \geq 0 \)

假設經過 minimize cost function 後, learn 到 parameters \( \theta_0 = -0.5, \theta_1 = 1, \theta_2 = 1, \theta_3 = 0 \)

Decision boundary 將如下圖所示, 距離 landmark \(l^{(1)}, l^{(2)}\) 較近的部分 predict 為 1, 否則 predict 為 0:


選擇 landmark 的方式


給定 training examples \( (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), ..., (x^{(m)}, y^{(m)}) \),

我們選擇 \( l^{(1)} = x^{(1)}, l^{(2)} = x^{(2)}, ..., l^{(m)} = x^{(m)} \).

給定 example x:
\( f_1 = similarity(x, l^{(1)}) \)

\( f_2 = similarity(x, l^{(2)}) \)

...

\( f_m = similarity(x, l^{(m)}) \)

\( f =
\begin{bmatrix}
f_0 = 1
\\f_1
\\f_2
\\...
\\f_m
\end{bmatrix} \)
對於 training example \( (x^{(i)}, y^{(i)}) \):
\( f_1^{(i)} = similarity(x^{(i)}, l^{(1)}) \)
\( f_2^{(i)} = similarity(x^{(i)}, l^{(2)}) \)
...
\( f_i^{(i)} = similarity(x^{(i)}, l^{(i)}) = exp(-\frac{0}{2\sigma^2}) = 1 \)
...
\( f_m^{(i)} = similarity(x^{(i)}, l^{(m)}) \)

\(x^{(i)} \in \mathbb{R}^{n+1} \)

\( f^{(i)} =
\begin{bmatrix}
f_0^{(i)} = 1
\\f_1^{(i)}
\\f_2^{(i)}
\\...
\\f_m^{(i)}
\end{bmatrix} \)

Hypothesis function for SVM


Predict "y=1" if \( \theta^T f \geq 0 \).
\( \theta^T f = \theta_0 f_0 + \theta_1 f_1 + \theta_2 f_2 + ... + \theta_m f_m \)

\( f \in \mathbb{R}^{m+1} \)

\( m \in \mathbb{R}^{m+1} \)
Training:
找出一組 \( \theta \), 使得 cost function 是 minimized:

\( C\sum_{i=1}^{m} [y^{(i)} cost_1(\theta^T f^{(i)}) + (1-y^{(i)}) cost_0(\theta^T f^{(i)})] + \frac{1}{2}\sum_{j=1}^{n}\theta_j^2 \)

因為在 SVM, features 數 (n) = training example 數 (m), 上式的第二的 summation term n 可替換為 m:

\( C\sum_{i=1}^{m} [y^{(i)} cost_1(\theta^T f^{(i)}) + (1-y^{(i)}) cost_0(\theta^T f^{(i)})] + \frac{1}{2}\sum_{j=1}^{m}\theta_j^2 \)

SVM parameters


\(C = \frac{1}{\lambda} \)
Large C (small \(\lambda\)): 較容易 overfitting. Lower bias, higher variance.

Small C (large \(\lambda\)): 較容易 underfitting. Higher bias, lower variance.
\(\sigma^2\)
Large \(\sigma^2\): Features \(f_i\) 變化較平緩. 較容易 underfitting. Higher bias, lower variance.

Small \(\sigma^2\): Features \(f_i\) 變化較陡峭. 較容易 overfitting. Lower bias, higher variance.

SVM 應用層面的考量


使用 SVM software package (e.g. liblinear, libsvm, ...) 求解 parameters \( \theta \).

需要選擇:

1. parameters \(C\)

2. kernel (similarity function)

No kernel ("linear kernel"):
Predict "y=1" if \(\theta^T x \geq 0\), i.e. \(theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n \geq 0\)

在這種情況下, SVM 等同於 standard linear classifier.

當 features 數量 (n) 大, 而 training examples 數量 (m) 小的時候, 採用 linear kernel, 可以簡單地把 training examples 區分開來, 避免採用太高 order 的 polynomials 導致 overfitting.
Gaussian kernel:
\( f_i = exp(-\frac{||x-l^{(i)}||^2}{2\sigma^2}) \text{, where } l^{(i)} = x^{(i)} \)

需要選擇 \(\sigma^2\)

\( x \in \mathbb{R}^n \), 當 \(n\) 小, 而 training examples 數量 (m) 大的時候, 此時我們可能需要比較複雜的 non-linear decision boundary, 便可以考慮採用 Gaussian kernel.
並不是所有的 similarity functions \(similarity(x, l)\)對於 SVM 來說都是合適的 kernel.
因為 SVM 在實作時為了 optimization, 假設 similarity function 必須滿足 "Mercer's Theorem". 如果沒有滿足這個條件, 計算得到的結果會有很大的偏差.
Linear kernel 和 Gaussian kernel 是比較常用的 kernel, 除此之外, 其他的 kernel (較少被使用) 包含:
Polynomial kernel:
\(k(x,l) = (x^T l + constant)^{degree} \)
String kernel, chi-square kernel, histogram intersection kernel, ...

Multi-class classification




\( y \in \{1, 2, 3, ..., K\} \)

許多 SVM packages 提供了 multi-class classification 的能力.

如果採用的 SVM packages 沒有 multi-class classification 的能力, 可以採用 one vs all method 來處理.
Train K SVMs, 對於第 i 個 SVM, 用來把 y=i 和其他 training examples 切分出來, 而得到 \(\theta^{(i)}\).

判斷新的 input 屬於哪一個類別的方式: 看哪一個 i 使得 \( (\theta^{(i)})^T x \) 最大, 則 input 屬於 class i.

Logistic regression vs. SVMs


\(n\): number of features

\(m\): number of training examples

\( x \in \mathbb{R}^{n+1} \)

If \(n\) is large (relative to \(m\)) (\(n \ge m\)):
例如: \(n = 10000, m = 10 \sim 1000\).

採用 logistic regression, 或是 SVM without a kernel ("linear kernel").
If \(n\) is small, \(m\) is intermediate:
例如: \(n = 1 \sim 1000, m = 10 \sim 10000\).

採用 SVM with Gaussian kernel.
If \(n\) is small, \(m\) is large:
例如: \(n = 1 \sim 1000, m \geq 50000\).

如果 \(m\) 太大, SVM 的執行速度會很慢.

可設法建立較多的 features, 然後採用 logistic regression 或是 SVM without a kernel.
對於上述的情況, 大部分的情況下 neural network 都可以運作得很好, 但可能需要花費比較多的時間 training, 特別是在最適合 SVM with Gaussian kernel 發揮的那段 regime.

SVM 處理的 optimization problem 是 convex optimization problem, 因此 SVM 能夠找到 global minimum.

延伸閱讀


[Coursera] Machine Learning: Support Vector Machines, by Andrew Ng, Stanford University