Support Vector Machine(SVM)

支持向量機是機器學習中歷久不衰的分類演算法(classificaiton)，其為了防止overfitting提供了合理的數學理論證明，筆者將會從頭到尾完整的解釋支持向量機的數學推導以及核心思想。
在分類演算法中，我們的目的不外乎就是找一條最佳的直線(曲線)來將複數個label盡力的分開，達到分類的目的，那麼到底要如何找出最佳的線呢？
如上圖，對於紅點與藍點來說，最佳的分類線(gutter)一定位在兩條虛線之間，而支持向量機的目的，就是要找出一條位於正中央的綠線方程式\(y=ax+b\)，而兩條虛線的距離當然愈大愈好(最佳化)。
首先，假想於兩條虛線之間的綠線稱為決策邊界(Decision boundary)，我們給予這條綠線一個基準\(y_i=\vec{w}\bullet\vec{\mu}+b=0\)(也可以想像成\(y=ax+b\)這種簡單的形式)，這樣就使得大於該邊界的點為一類；小於則是另一類，這樣就能輕鬆的表示決策規則(Decision rule)，大於這規則就給予+，反之則是-，接著，要對正負號做更泛化的變形，使得在這決策規則之上，只有兩種情形，使得\(y_i\)只有\(\{-1,1\}\)兩種結果(當然也可以設\(\{-0.5,0.5\}\)為邊界值，只是\(\{-1,1\}\)在計算上較方便，在之後的推導上也容易)。

\[ \begin{equation} \begin{aligned} y_i=\vec{w}\bullet\vec{\mu}+b=0&\Rightarrow \left\{ \begin{array}{r@{\;=\;}l} &\vec{w}\bullet\vec{\mu}+b>0 & ,\mbox{Then}\;+\\ &\vec{w}\bullet\vec{\mu}+b<0 & ,\mbox{Then}\;- \end{array} \right.\\ &\vec{w}為平面參數，\vec{\mu}為\vec{x}的向量\\ &\Rightarrow \left\{ \begin{array}{r@{\;=\;}l} &\vec{w}\bullet\vec{x_+}+b\geq1\\ &\vec{w}\bullet\vec{x_−}+b\leq-1 \end{array} \right.\\ \mbox{such that }y_i&= \left\{ \begin{array}{r@{\;=\;}l} +1 & ,\mbox{For + examples}\\ -1 & ,\mbox{For − examples} \end{array} \right. \end{aligned} \end{equation} \]

接著將\(y_i\)分別乘上自己的所屬方程式，發現兩條方程式其實一模一樣的，只是正負號的戲法而已，經過移項就能夠整理出一個真正的決策邊界，接著將大於去除，因為正中央的線才是需要的，得到了正中央的Gutter。

\[ \begin{equation} \left\{ \begin{array}{r@{\;=\;}l} y_i(\vec{w}\vec{x_i}+b)\geq1\\ y_i(\vec{w}\vec{x_i}+b)\geq1 \end{array} \right. \Rightarrow y_i(\vec{w}\vec{x_i}+b)-1\geq0\\ y_i(\vec{w}\vec{x_i}+b)-1=0, \mbox{for }x_i\mbox{ in gutter} \end{equation} \]

求得Gutter之後，我們還必須決定它與兩條虛線的距離，也就是兩條虛線的寬度要愈寬愈好，這裡就是SVM最重要的思想，最佳化問題，必須求得寬度極大值(Maximum)，首先假設寬度為一個\((\vec{x_+}-\vec{x_-})\)倍單位向量，將\(y_i(\vec{w}\vec{x_i}+b)-1=0\)帶入整理，得到我們需要進行最佳化的值\(\frac{2}{||\vec{w}||}\)。

\[ \begin{align} \mbox{width}&=(\vec{x_+}-\vec{x_-})\bullet\frac{\vec{w}}{||\vec{w}||}\\ &=\frac{\vec{x_+}\vec{w}-\vec{x-}\vec{w}}{||\vec{w}||}\\ &=\frac{(1-b)-(-1-b)}{||\vec{w}||}\\ &=\frac{2}{||\vec{w}||} \end{align} \]

接著是有點麻煩的步驟，我們目前是在有條件的情況下求極值，也就是在\(y_i(\vec{w}\vec{x_i}+b)-1=0\)的條件下對\(Max\frac{2}{||\vec{w}||}\)求最大值，在這裡就必須介紹一位偉大的數學家Lagrange，他最偉大的發明就是Lagrange multiplier(拉格朗日乘數)，例如說一個方程式有兩個變數的時候，其中必須滿足的條件就是對\(f(x,y)\)偏微必須為0，其中又提到若在約束條件\(g(x,y)\)下，對\(f(x,y)+\lambda g(x,y)\)偏微能找到\(f(x,y)\)在\(g(x,y)\)下的極值，代替\(\frac{\partial{f}}{\partial{x}}=\frac{\partial{f}}{\partial{y}}=0\)在\(g(x,y)\)上求極值的條件，其中\(\lambda\)就是乘數，若約束條件為複數個時，則是各個約束條件的乘數。

\[ \frac{\partial{f}}{\partial{x}}=\frac{\partial{f}}{\partial{y}}=0\\ \begin{equation} \left\{ \begin{array}{r@{\;=\;}l} &\frac{\partial{f}}{\partial{x}}+\lambda\frac{\partial{g}}{\partial{x}}=0\\ &\frac{\partial{f}}{\partial{y}}+\lambda\frac{\partial{f}}{\partial{y}}=0\\ &g(x,y)=0 \end{array} \right. \end{equation} \]

這裡要對\(Max\frac{2}{||\vec{w}||}\)做一點手腳，最大最小化的轉換是為了後面Lagrange multiplier偏微的方便。

\[ Max\frac{2}{||\vec{w}||}\Rightarrow Max\frac{1}{||\vec{w}||}\Rightarrow Min||\vec{w}||\Rightarrow Min\frac{1}{2}||\vec{w}||^2 \]

接著就能套入Lagrange multiplier的公式，求得極值的條件之後，就能帶回原本的Lagrange並整理，最後的結果就是SVM的核心，由\(\vec{x_i}\bullet\vec{x_j}\)得知，最佳化取決於對樣本的點積(內積)。

\[ L=\frac{1}{2}||\vec{w}||^2+ \sum\lambda_i[y_i(\vec{w}\bullet\vec{x_i}+b)-1]\\ \begin{equation} \begin{aligned} &\left\{ \begin{array}{r@{\;=\;}l} &\frac{\partial{L}}{\partial{\vec{w}}}=\vec{w}+\sum\lambda_iy_i\vec{x_i}=0\\ &\frac{\partial{L}}{\partial{\vec{w}}}=\sum\lambda_iy_i=0 \end{array} \right.\\ \Rightarrow &\left\{ \begin{array}{r@{\;=\;}l} &\vec{w}=-\sum\lambda_iy_i\vec{x_i}\\ &\sum\lambda_iy_i=0 \end{array} \right. \end{aligned} \end{equation}\\ \begin{aligned} L&=\frac{1}{2}(-\sum\lambda_iy_i\vec{x_i})(-\sum\lambda_jy_j\vec{x_j})+ (\sum\lambda_iy_i\vec{x_i})(\sum\lambda_iy_i\vec{x_i})+ \sum\lambda_iy_ib- \sum\lambda_i\\ &=\frac{1}{2}\sum_i\sum_j\lambda_i\lambda_jy_iy_j\vec{x_i}\vec{x_j}- \sum\lambda_i \end{aligned} \]

將\(\vec{w}\)帶入決策規則會比較好理解，表示決策規則取決於一個樣本點與另一未知點的點積，到這裡是對於線性可分割的部分。

\[ \begin{align} &\vec{w}\bullet\vec{\mu}+b=0\\ &(-\sum\lambda_iy_i\vec{x_i})\bullet\vec{\mu}+b=0\\ &-\sum\lambda_iy_i\underline{\vec{x_i}\bullet\vec{\mu}}+b=0 \end{align} \]

以上是針對在超平面上，線性可分割(linearly separable)的部分，若遇到像下圖這種線性不可分割(linearly inseparable)的例子，就必須跳到更高維度去觀察，才有辦法解決。

上面提到，最大化取決於點積，以\(\phi\)表示點\(x\)轉化至高維上的點，所以在高維上，一樣是以兩點的點積\(K\)來決定最大化，其中要如何選擇一個適當的核函數(kernel)又是一個問題，針對不同的問題有不同的核函數，這就是經驗上的差距了，對於線性可分割如Linear核；線性不可分割如RBF、sigmoid、polynomial等等，對於數據做’升維’的處理，就是核函數處理非線性厲害之處。

\[ K(x_i,x_j)=\phi(\vec{x_i})\bullet\phi(\vec{x_j})\;to\;max\\ (\phi(\vec{x_i})\bullet\phi(\vec{\mu})) \]

以下是吳恩達的見解：
1. 如果Feature的數量很大，跟樣本數量差不多，這時候選用LR或者是Linear Kernel的SVM
2. 如果Feature的數量比較小，樣本數量一般，不算大也不算小，選用SVM+Gaussian Kernel(RBF)
3. 如果Feature的數量比較小，而樣本數量很多，需要手工添加一些feature變成第一種情况
每個核函數都對應著各自的變換，如何採用適當的核函數只能利用實驗和經驗來驗證了(https://www.youtube.com/watch?v=3liCbRZPrZA&feature=share)。
set.seed(5)
data(iris)
x <- iris[1:150, c("Sepal.Length", "Sepal.Width", "Species")]
plot(x[,1:2],col = x[,3])

library(e1071)
model1 <- svm(Species ~ ., data=x, kernel="linear")
decisionplot(model1, x, class = "Species", main = "SVM (linear)")

model2 <- svm(Species ~ ., data=x, kernel = "radial")
decisionplot(model2, x, class = "Species", main = "SVM (RBF)")

model3 <- svm(Species ~ ., data=x, kernel = "polynomial")
decisionplot(model3, x, class = "Species", main = "SVM (polynomial)")

model <- svm(Species ~ ., data=x, kernel = "sigmoid")
decisionplot(model, x, class = "Species", main = "SVM (sigmoid)")