Introduction to Support Vector Machine
1992年， Guyon, Boser,和Vapnik在其論文「A training algorithm for optimal margin classifiers」中，使用Kernel trick來架構non-linear classifiers。
下面會來跟大家分享論文的內容，原本想說以前看過軒田大大的影片，但後來發現懂概念到要和大家講解每一條公式還有好大一段差距。
Linear Separability
線性可分的概念其實就是可以透過一條直線完整的分開兩個不同的資料集，如下圖綠點和紅點清楚的被一條直線分開。
Which Line Is Best
這時我們遇到第二個問題，要怎麼去衡量說哪條直線的分割方式是最佳的呢？憑直覺我們可以選出最左邊的分割方式應該是最好，量化上，我們可以用每個點跟直線距離加總最大來衡量這是不是一條最穩固的線。
Fat Hyperplane
我們可以把剛剛說點到平面距離加總最大的這件事，想像成是這個平面有最大的邊界，所以現在想要求一個最穩的線性可分平面，就是求一個有最胖邊界的平面。
Large-Margin Separating Hyperplane
接下來要大家看一些數學的部分，為了這些數學公式又重新再看軒田大大的影片好多次，現在我們的問題是要最大化margin，而margin就是距離平面最近的那點到平面的距離。
如果我們現在有一個超平面 wTx + b = 0，假設 x’ 與 x’’ 都在這個超平面上，只要把x和x’這段距離乘上cos在化簡一下就可以得到下面那條公式。
因為是一個可以分開訓練資料的超平面，因此已有 yn(wTXn+ b) > 0 這個條件，也因此距離公式中的 |wTx+b| 可以用 yn(wTXn + b) 來取代，這樣會比較容易求解。
把剛剛的公式再整理一下，公式如下圖，這邊我們發現margin還是太長一串。
針對 wTx + b = 0 這個超平面，我們對這個超平面進行縮放其實是沒有任何影響，我們將 wTx + b 進行放縮，讓它跟 yn 相乘會是 1，也就是 yn(wTXn + b) = 1。
現在 margin(b,w) 可以轉換成 1 除以 w 的長度，我們只要求讓這個值最大的平面就可以了，接著經過 Lagrange， 將問題轉換成對偶SVM，二次規劃求解(這邊的數學公式就先跳過，怕大家最後都睡著)。
Dual Representation
這邊參考李宏毅老師的講解，其實 w 解出來就是每個資料點的線性組合，而α 則是每個資料點的係數，當α > 0代表該點被選作support vector，α本身是一個很稀疏的矩陣，因為大多數的α均為0，這也是SVM比較robust的原因，假如新增的點只要不被選為support vector，對模型就不會有影響。
Kernel Trick
這邊進入到本篇論文的精華，透過下面這個例子我們可以知道，以後透過kernel function就可以達到以前必須先把點轉到高維再做內積。
Common Kernel Function
在一般使用上，gaussian function是最常被使用的，poly kernel因為參數太多在使用上較為不便，最後如果要自己定義kernel function，則必須要去確認是否符合mercer’s condition。
Experimental Results
論文中使用了手寫辨識的資料集，發現錯誤率比BPN低很多，使用gaussian kernel後最低可以到達1.3%。
Conclusion & Future work
作者提到說更高的多項式kernel和使用更大γ的gaussian kernel可以增加模型的準確率，但也必須去做cross validation確保over fitting，另外hard margin為了要達到線性可分的平面可能必須要過度的去適應模型，所以作者也在隔年提出soft margin，藉由犧牲掉一些正確率。
Reference
