SVM (Support Vector Machine)
===
###### tags: `李宏毅`

* SVM 特色
* Hinge Loss
* 一般做 regression 會希望 output 跟 target 越近越好
* SVM 則是只要近到一個程度就好
* Kernel Method(Kernel Trick)
* deep learning vs SVM
* deep learning 的前幾個 layer 可以當成是 Feature transformation，最後的 layer 是 linear classifier
* SVM 也很相似，就是用 Kernel Function 做 feature transformation 轉到 high dimension，最後的 layer 也是一個 linear classifier，只是通常會用 hinge loss
* 其實 Kernel Function 是可以訓練的，而在訓練的 Kernel Function 就像是很多 layer 的 linear transform
* 一般的 binary classification
1. function set。有個 g(x)，其中又有個 f(x)，當 f(x) > 0 就輸出 +1，f(x) < 0 就輸出 -1。每個 input x 都會有個 label `ŷ = +1, -1`
2. loss function
* 理想的 loss function 大概如下，分類正確就 +1，反之 -1
* 但是這樣不可微分，所以改 minimize 另一個可微分的 loss function
* square loss 就是當 label = 1 時，f(x) 越接近 1 就 loss 越小，label = -1 時，f(x) 越接近 -1 loss 越小
* 然而單純的 square loss 如果 f(x) 和 ŷ 相乘很大，所以用 sigmoid + square loss。當 ŷ = 1 時 sigmoid(f(x)) 越接近 1 loss 越小；當　ŷ = -1 時 sigmoid(f(x)) 越接近 0 loss 越小
* sigmoid + cross entropy。sigmoid(f(x)) 代表一個 distribution，ŷ 也是一個 distribution，兩個 distribution 的 cross entropy 就是 loss。它好還要更好，比較不抗 outlier
* Hinge loss。當 f(x) 好過一定程度，loss 就會是 0，例如當 ŷ = 1 時，f(x) 正很大。它只要及格就好，比較抗 outlier
* 由於 sigmoid + square loss 在 ŷf(x) 很大的時候 loss 差異反而很小，所以不好 train。反之 sigmoid + cross entropy 因為在 ŷf(x) 很大時差異就很大，所以好 train。因此喜歡用 sigmoid + cross entropy
3. gradient descent for training
* Linear SVM
1. Function (model)
* f(x) 就是 linear function
2. loss function
* 使用 Hinge loss
* 有菱菱角角的東西，所以在一些點不可微，但是可以用 gradient descent 做 optimization
* 單看下面兩個紅框框是不等於的，但是如果今天是要 minimizing loss function 就符合。所以現在目標是在有下面紅框的兩個 constraint 的條件下 minimize loss function，這可以用 Quadratic Programming 去解
3. Training
* gradient descent。在 Hinge loss function 對 w 的每個維度做偏微分，用 ŷf(x) 大小來判斷微分的結果
* 所以每次的 gradient descent 等於是 data point 的 linear combination，不過因為用 Hinge loss，有些 c 輸出是 0，對 w 沒有影響，因此把對 w 有影響到 data point 稱作 support vector
* 把 sigma 拿掉，就會變成 `w = ɑ 矩陣 * X 矩陣`，而 f(x) 變成 `f(x) = ɑ 矩陣 * X 矩陣 * x`，其中 X 矩陣 * x 的每一 row 做 inner product 的步驟就是 Kernel Function
* 因此不需要真的知道 x 是多少才可以算 loss，只要知道 kernal function K(x, z) 就可以了，這招就叫 Kernel Trick
* Kernel Trick
* 用在 transform 後的 inner product，比一般的方法快
* 一般的方法
* 假設要算 `K(x, z) = f(x) * f(z)`，直接代進去算連國中生也會。這邊可以注意到這個 case 最後的結果是 `(x*z)^2`，但是 inner product 要算的量從 2 變成 3
* Kernel Trick 的方法
* 直接做 `(x*z)^2`，在高維的時候節省很多運算量
* ex. Radial Basis Function Kernel，比起算有無限多維度的 `f(x) * f(z)`，不如直接算 `exp(-1/2 |x - z|)`
* ex. Sigmoid Kernel，直接算 `K(x, z) = tanh(x * z)`，比算泰勒展開式的 inner product 快
* 不是所有 function 都可以用 Kernel Trick 解，但是可以用 Mercer's theory 確認可不可以