---
# System prepended metadata

title: SVM (Support Vector Machine)
tags: [李宏毅]

---

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
            ![](https://i.imgur.com/jlGWCFz.png)
        * 但是這樣不可微分，所以改 minimize 另一個可微分的 loss function
            ![](https://i.imgur.com/CrG93gP.png)
        * square loss 就是當 label = 1 時，f(x) 越接近 1 就 loss 越小，label = -1 時，f(x) 越接近 -1 loss 越小
            ![](https://i.imgur.com/IuPlBil.png)
        * 然而單純的 square loss 如果 f(x) 和 ŷ 相乘很大，所以用 sigmoid + square loss。當 ŷ = 1 時 sigmoid(f(x)) 越接近 1 loss 越小；當　ŷ = -1 時 sigmoid(f(x)) 越接近 0 loss 越小
            ![](https://i.imgur.com/WQ0rray.png)
        * sigmoid + cross entropy。sigmoid(f(x)) 代表一個 distribution，ŷ 也是一個 distribution，兩個 distribution 的 cross entropy 就是 loss。它好還要更好，比較不抗 outlier
            ![](https://i.imgur.com/S3hsjfw.png)
        * Hinge loss。當 f(x) 好過一定程度，loss 就會是 0，例如當 ŷ = 1 時，f(x) 正很大。它只要及格就好，比較抗 outlier
            ![](https://i.imgur.com/Ytc32IE.png)
        * 由於 sigmoid + square loss 在 ŷf(x) 很大的時候 loss 差異反而很小，所以不好 train。反之 sigmoid + cross entropy 因為在 ŷf(x) 很大時差異就很大，所以好 train。因此喜歡用 sigmoid + cross entropy
            ![](https://i.imgur.com/VOlZy9q.png)
    3. gradient descent for training
* Linear SVM
    1. Function (model)
        * f(x) 就是 linear function
            ![](https://i.imgur.com/CROoCf4.png)
    2. loss function
        * 使用 Hinge loss
            ![](https://i.imgur.com/89mBamD.png)
        * 有菱菱角角的東西，所以在一些點不可微，但是可以用 gradient descent 做 optimization
        * 單看下面兩個紅框框是不等於的，但是如果今天是要 minimizing loss function 就符合。所以現在目標是在有下面紅框的兩個 constraint 的條件下 minimize loss function，這可以用 Quadratic Programming 去解
            ![](https://i.imgur.com/JiYo8tS.png)
    3. Training
        * gradient descent。在 Hinge loss function 對 w 的每個維度做偏微分，用 ŷf(x) 大小來判斷微分的結果
            ![](https://i.imgur.com/PAsmaz7.png)
        * 所以每次的 gradient descent 等於是 data point 的 linear combination，不過因為用 Hinge loss，有些 c 輸出是 0，對 w 沒有影響，因此把對 w 有影響到 data point 稱作 support vector
            ![](https://i.imgur.com/OxHaAac.png)
        * 把 sigma 拿掉，就會變成 `w = ɑ 矩陣 * X 矩陣`，而 f(x) 變成 `f(x) = ɑ 矩陣 * X 矩陣 * x`，其中 X 矩陣 * x 的每一 row 做 inner product 的步驟就是 Kernel Function
            ![](https://i.imgur.com/gb8ho1v.png)
        * 因此不需要真的知道 x 是多少才可以算 loss，只要知道 kernal function K(x, z) 就可以了，這招就叫 Kernel Trick
            ![](https://i.imgur.com/sWlaOZm.png)
* Kernel Trick
    * 用在 transform 後的 inner product，比一般的方法快
    * 一般的方法
        * 假設要算 `K(x, z) = f(x) * f(z)`，直接代進去算連國中生也會。這邊可以注意到這個 case 最後的結果是 `(x*z)^2`，但是 inner product 要算的量從 2 變成 3
            ![](https://i.imgur.com/CcFa0vq.png)
    * Kernel Trick 的方法
        * 直接做 `(x*z)^2`，在高維的時候節省很多運算量
        * ex. Radial Basis Function Kernel，比起算有無限多維度的 `f(x) * f(z)`，不如直接算 `exp(-1/2 |x - z|)`
            ![](https://i.imgur.com/haGbW1g.png)
        * ex. Sigmoid Kernel，直接算 `K(x, z) = tanh(x * z)`，比算泰勒展開式的 inner product 快
            ![](https://i.imgur.com/kzi0MTR.png)
    * 不是所有 function 都可以用 Kernel Trick 解，但是可以用 Mercer's theory 確認可不可以