支援向量機(Support Vector Machine, SVM)是一種基於統計學習理論基礎的機器學習模型，針對小樣本、非線性、高維度與局部最小點等問題具有相對的優勢。這個概念其實早在1960-1990年代就由數學家Vapnic及Chervonenkis等人所提出，並建立了這套統計學習理論。除了在文字分類、圖像分類及醫學中分類蛋白質等領域有不錯的成效外，因具有計算速度快且空間成本低等優勢，在工業界也有廣泛的應用。
SVM能解決什麼問題?
SVM是一種線性分類器，同時卻也可以推展到解決非線性的分割問題。在下圖左是個線性可分的樣本，很多種模型都可以輕而一舉得達到好的分類結果。然而，一般來說，我們總是會遇到比較複雜的樣本，很可能是線性不可分(如下圖右)，甚至是高維度錯綜複雜的問題。然而，有了SVM，這些分類通通都不是問題!究竟，SVM是怎麼做到的呢?
SVM的運作原理
具象化來說，SVM就是將在低微度空間線性不可分的樣本映射到高維度空間去，找到一個超平面將這些樣本做有效的切割，而且，這個超平面兩邊的樣本要盡可能地遠離這個超平面。
接下來，我們從這個立方體的側面(粉紅色面)看過去，就會變成一個平面的樣子。這樣，不就變成線性可分了嗎? 是不是很簡單!
回過頭來，我們要探討的是，這條紅色的線(立方體圖裡面的超平面)是怎麼決定的呢? 在左圖中，我們可以看到，其實，有好多條線都一樣可以達到分類的效果，為什麼最後會選擇紅色這條線呢? 因為，這條線可以讓Margin最大化，當未來有新的樣本進入時，分類成功的機率也會比較高! 所以，在SVM中，我們就是要找到一個像紅色線一樣的超平面，讓兩邊樣盡可能的遠離這個平面，以達到最大化。
數學式子
到目前為止，相信大家對於SVM的運作方式已經有了清晰的輪廓。現在，我們將以數學式子分享這些運作背後的計算過程，以及介紹一些常用的核函數。有興趣的朋友歡迎跟著我們一起閱讀，對數學部分沒興趣的朋友也可以直接跳到結論，因為你已經了解SVM的運作原理了!
如何找到讓Margin最大的超平面?
我們簡單化上座標軸，假設這紅色的分隔線為$y=\bf{w^Tx} $ $ +b$，在這邊，$\bf{w}$代表權重向量，與我們的分隔線互為垂直。為了簡化，我們可以選擇標準化$\bf{w}$讓這條線為$\bf{w^Tx} $ $ +b=0$，則另外兩條虛線可以分別定義為 $\bf{w^Tx} $ $ +b=+k$ 與 $\bf{w^Tx}$ $+b=-k$ ，$k$為任意常數。
也就是說，這兩條虛線之間的距離為
$$\bf{\frac{w}{ ||w|| }\cdot (x_+ – x_-)} =\bf{\frac{w^T(x_+-x_-)}{||w||}}=\frac{k}{\bf{||w||}} $$
很清楚的，要讓Margin最大化，我們只要把上式最大化就可以了! 然而，要怎麼找到最適的$\bf{w}$呢? 我們可以透過先前學過的Gradient decent來解決這個問題。當然，因為這條線代表的其實是所謂的超平面，有可能我們是把樣本打到很高的維度，在這樣的情況下，Gradient decent的解法就會比較不具效率。因此，我們也可以透過將目標式等價的改寫，用其他的方法來求解。這部分比較複雜，方法也很多，有興趣的讀者可以參考Learning with Kernels.
核函數 (Kernel Function)
先前提到，當我們遇到在低維度線性不可分的問題時，可以透過將樣本映射到高維度的方式，找到一個最適的超平面。問題來了，要怎麼將樣本從低維度映射到高維度呢? 這時，我們就需要透過一個映射函數，而核函數正是這個映射函數的內積！
大家可能會困惑，有了映射函數，為什麼還需要核函數呢? 想像一下，如果我們要把原本僅在2維空間的樣本，映射到超高維度(比方說3000維)，要求解肯定會相當複雜且耗時。由於在求解時二次規劃算法只需要利用到映射的內績進行求解，所以我們會取而代之只計算內績即可，而這內積正是核函數啊！在Mercer’s theorem中又保證了每一個核函數會對應到一個相對應映射方法，所以如果我們採用不同的核函數，相當於採用了不同的映射方法，以下是一些常見的核函數:
多項式核函數:
$$ K(\bf{x_i,x_j})=(\bf{x_i \cdot x_j})^d$$
$$ K(\bf{x_i,x_j})=(1+ \bf{x_i \cdot x_j})^d$$
高斯核函數:
$$K(\bf{x_i,x_j})=exp(-\frac{||\bf{x_i-x_j}||^2}{2 \sigma^2})$$
Sigmoid核函數:
$$K(\bf{x_i,x_j})=tanh(\kappa(\bf{x_i \cdot x_j})+\theta)$$
在這邊，d為一整數，$\sigma, \kappa, \theta$屬於實數。
SVM的優缺點
最後，我們來總結一下SVM的優缺點。
優點:
1.使用核函數可以有效處理高維數據
2. 透過不同核函數的選擇，可以處理不同的資料
3. 決策函數由少量的支持向量決定，預測效率高
缺點:
1. 維度過高容易造成運算上的負擔
2.特徵遠大於樣本的情況下容易造成過度擬和的問題
在這個單元，我們認識了SVM的基本概念，以及其背後的運作原理，還有一些常用的核函數。下個單元，我們將一起用Python來實作SVM模型唷!
References
•Artificial Intelligence — A Modern Approach
• Learning with Kernels, Scholkopf and Smola
• Kernel Machines, Simon
•WikiPedia