Support vector machine (SVM)

meeting PV:

Support vector machine (SVM)

author:Puchi
date:2020.04.22

tags: ‘SVM’, ‘study group’

SVM (Hard margin)

  • SVM training時間遠低過DNN。
  • SVM可以將linear extend到non-linear（運用kernel trick）
  • 有統計理論support

    目標（問題解釋）：

給定一個training dataset
$$S={(x^i,y_i)|x^i\in R^n, y_i\in{-1,1},i=1,…,l}$$$$x_+\in A_+\quad iff\quad y=1 \quad and \quad x_-\in A_-\quad iff \quad y=-1.$$
想要從training data的資訊找出一個function f:R^n->R 使得
$f(x)>0 \rightarrow x\in A_+$ and $f(x)<0 \rightarrow x\in A_-$
目標：預測新進來的data的label

最原始的SVM在解的最佳化問題：

$$min_{ {\bf x},\gamma}\dfrac{1}{2}|{\bf w}|^2_2,$$$$s.t.\quad y_i({\bf w}^T{\bf x}_i+b)>=1,\quad i=1,…,n.$$

Primal form and Dual form

Primal form:
$$min_{ {\bf x},\gamma}\dfrac{1}{2}|{\bf w}|^2_2,$$$$s.t.\quad y_i({\bf w}^T{\bf x}_i+b)>=1,\quad i=1,…,n.$$

Dual form:
$$max_\alpha\quad 1^T\alpha-\dfrac{1}{2}{\bf\alpha}^TDAA^TD{\bf\alpha}$$$$s.t.\quad 1^TD{\bf\alpha}=0,\quad {\bf\alpha}\geq 0.$$

Dual form推導：

$$L(w,b,\alpha)＝\dfrac{1}{2}w^Tw+\alpha^T(1-D(Aw+1b)),\alpha\geq 0$$$$\dfrac{\partial}{\partial w}L(w,b,\alpha)=w-ATD\alpha=0$$$$\dfrac{\partial}{\partial b}L(w,b,\alpha)=a^TD\alpha=\sum_{i=1}^ly_i\alpha_i=0$$

Recall Dual form : $\max_{\alpha} \min_{w,b} L(w,b,\alpha) \quad s.t. \quad \alpha \geq 0.$

So, we have Dual form:
$$max\quad 1^T\alpha-\dfrac{1}{2}\alpha^TDAA^TD\alpha$$$$s.t.\quad 1^TD\alpha=0,\quad \alpha\geq 0.$$

值得注意的是：
$w=A^TD\alpha=\sum_{i=1}^{l}y_i\alpha_iA_i^T$，所以原 linear classifier $f$ 可以寫
$f(x)=\sum_{i=1}^n\alpha_iy_i{\bf x_i}{\bf x}^T_i+b \equiv \sum_{i=1}^nu_i{\bf x_i}{\bf x}^T_i+b$，且我們也可知用KKT condiction把b算回去。因此我們只要算出dual問題，就可帶回原本的問題。

為什麼要用Dual form去求解最佳化？
因為Dual的objective function整個是一個concave function,且限制條件只有一個，計算起來容易很多。（注意：$max$ $\theta(\alpha)$ iff $-min$ $-\theta(\alpha)$，解concave,convex問題是一樣的）

support vector的意義

$\alpha$與$w^Tx+b$相垂直，且$\alpha_i\geq 0$。
當$\alpha>0$代表這些限制條件是active constraint。對整個限制條件才有影響。
$\alpha_i=0$是inactive constraint,也就是$w^Tx+b$嚴格大於0，因此有這個限制或沒有限制都一樣。透過$\alpha_i$正負可知道。$\alpha_i=0$的對整個結果沒有影響。
support vector: $\alpha_i>0$，也就是在線上的。


(圖片來自老師SVM的投影片)

Remark

一個好的model應該要考慮到：
model bias, model variance都應該小

  1. Structural Risk Minimization
    training error (衡量model bias) +VC error bound （衡量 model variance）
    實驗誤差和
    $|w|_2$ 和VC bound成正比
    $min$ VC bound iff $min$ $\dfrac{1}{2}|w|_2^2$ iff max Margin

  2. KKT condiction

SMO (Sequential Minimal Optimization)

由Microsoft的人提出，是早期的一種非常知名的加速計算SVM的方法，當然也可以用quadratic programming的方法來計算，但比較慢。(quadratic programming方法包含：Newton method, steepest descent, …等)
若對SMO詳細推倒有興趣，可參考這篇論文。

  • 回想我們原本的最佳化問題(引用李育杰老師的投影片)：

  • SMO核心想法：每次只挑出兩個 $\alpha_i, \alpha_j$ 搭配做更新，其餘固定不動。為什麼是兩個呢？因為需要有人來搭配，一個增加、一個減少，去固定改變的量(以下圖片引用李育杰老師的投影片)

經過一連串轉換後，原本的問題就轉變為以下(詳細數學推導可以去看論文，以下圖片引用李育杰老師的投影片)：

  • 演算法流程：
    以下演算法引用自此投影片



Soft-Margin SVM (nonseparable case)

為什麼需要Soft-margin SVM?因為有些問題，他不是linearly separable，也就是找不到$w,b$使得資料完全被分乾淨。（也就是說，primal problem是infeasible，Dual problem是umbounded）

因此我們給每一個training data都給一點點調整量$\xi_i$，即可。
$$y_i(w^Tx^i+b)\geq 1-\xi_i,\quad \xi_i\geq 0, \forall i.$$

但仍希望調整量越少越好（除此之外，也記得：原始問題是讓margin越大越好）

1-norm soft margine:

  • Primal form:

    $$\min \quad \dfrac{1}{2}|w|^2+C\sum_{i=1}^n\xi_i,$$$$s.t.\quad y_i(w^Tx_i+b)\geq 1-\xi_i,$$ $$\qquad \xi_i\geq 0, i=1,…,n.$$

Remark:
$1^T\xi$ (1 norm measure of error vector) 就是training error

  • Dual form:

    $$\max \sum_{i=1}^n\alpha_i-\dfrac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_j y_i y_j <x_i,x_j>$$
    $$s.t.\quad 0\leq\alpha_i\leq C, i=1,…,n,$$ $$ \sum_{i=1}^n\alpha_i y_i=0.$$

We call $\xi_i\geq 0$ the slack variable.

2-norm soft margin

  • Primal form:

    $$\min \quad \dfrac{1}{2}|w|^2+\dfrac{C}{2}\sum_{i=1}^n\xi_i^2,$$$$s.t.\quad y_i(w^Tx_i+b)\geq 1-\xi_i.$$

  • Dual form: （詳細推導可看此）

    Remark

    我們稱 $C$ 為 weighted varialbe。
    當我們做SVM的最佳化時，其實我們希望：

  1. 讓margin分越開越好
  2. 讓slack variable不要太大（不希望讓太多太遠的也跑進來）

當 $C$ 調大時，只要有一點的$\xi_i$，就會讓目標函數放很大。亦即「很看重training error」，因此若有overfitting的現象，須將 $C$ 調小。

Remark:

1-Norm SVM:
$$min\quad |w|_1+C1^T\xi$$$$D(Aw+1b)+\xi\geq 1 $$$$\xi\geq 0$$

等價於
$$min \quad 1s+C1^T\xi$$$$D(Aw+1b)+\xi\geq 1 $$$$-s\leq w\leq s$$$$\xi\geq 0$$

以下截圖自Model selection for support vector machines via uniform design：


Non-linear SVM


（圖片來自李育杰老師的投影片）

有些資料，在原始空間可能沒辦法很容易的用linear classifier去分開。
Non-linear SVM的想法來自將原資料映射到某個較高維度的空間，在那個高維度空間去做分類（把資料轉換後，再做SVM的意思）。

藉著 $\phi$ 將原資料做完映射後，classifier長相：
classifier for primal form: $$f(x)=(\sum_{j=1}^? w_j\phi_j(x))+b$$

dual form:
$$f(x)=(\sum_{i=1}^l\alpha_iy_i<\phi(x^i),\phi(x)>)+b=(\sum_{i=1}^l\alpha_iy_iK(x^i,x))+b$$

Kernel


此圖來自李育杰老師投影片

我們可以把kernel想像成「用不同的方式去描述資料」，kernel matrix裡的每k個row，就是第k筆資料與其他資料之間的相似度。（有n筆training資料,kernel matrix的size就是nxn）

常見的kernel function (以下截圖自此):

RBF kernel （Radial basis or Gaussian) $k(x,y)=e^{-\beta|x-y|^2}=e^{-\frac{|x-y|^2}{2\sigma^2} }, \sigma\in \mathbb R\setminus{0}.$

  • $\beta$大小 v.s. RBF kernel:
    [圖一] x軸為 $$x$$, y軸為 $$e^{-\beta\|x-0\|^2}$$
    [註]：圖片來源在此

  • 距離與kernel值的關係:

    [圖二]

[註]：圖片來源在此

可想像成用不同方式描述一筆資料（用和其他筆資料的相似度）。

  • Mercer condiction

    如果kernel function滿足Mercer condiction,就一定有相對應的non linear map。

SSVM (Smooth Support Vector Machine)

SSVM在解的最佳化問題：

$$\min_{(w,b)\in R^{n+1} }\dfrac{C}{2}|p((1-D(Aw+{\bf 1}b),\beta))|^2_2+b^2$$
重點：SSVM使用一個二次可微分的函數去近似原本的plus function，因此可以使用newton method去解這個最佳化問題，且SSVM是一個strongly convex的問題，因此有唯一解。

式子推導

  1. constraint 轉成 unconstraint

    我們可透過以下方法將原本的constraint的問題轉成unconstraint問題。

Remark: 加上b只是為了數學上確保是strongly convex function (有unique solution).
$\xi=0$ or 小於$0$: 函數不用調整
因為少了constraint，變數從原本的n+1+l變成n+1

  1. 原本不是二次可微分的的plus function 轉換成二次可微分的p函數

從上圖可以清楚看到 Plus function $(*)_+$ 不是二次可微分(紅色的圈圈點，不可微分)，所以不能用newton method去計算這個最佳化問題。我們會想去找一個二次可微的函數去近似plus function，讓我們能夠用newton method去解這個問題。

事實上，在訊號處理的領域常用sigmoid function去近似step function。而step function的積分就是plus function。因此希望透過sigmoid function的積分來近似plus function。

Remark:

Sigmoid function: $\dfrac{1}{1+e^{-\beta x} }$
Sigmoid function的積分：
$$p(x,\beta)\equiv x+\dfrac{1}{\beta}log(1+e^{-\beta x})$$

SSVM在做的事就是用$p(x,\beta)$這個二次可微分的函數來取代原本的plus function。（這裡一直強調二次可微，主要是因為牛頓法需要二次可微）。

在此使用 Newton Armoijo Algorithm （之後再詳細寫）

Remark:原本牛頓法其實就是$\lambda=1$時。
從$\lambda=1$開始試，直到滿足Armijo rule為止。Armijo rule直觀的意思就是保證從原本的點走到新的點要下降一定的量。

此方法保證：不論起始值多少，都可在有限步找到解。
且一定會在有限步求出解。（通常只要 6-8 iterations 就可收斂。）

我們現在知道SSVM是一個好算的方法，那我們再回頭去看要怎麼用SSVM去解non-linear SVM呢？先看一下原始的SVM:

注意：在這裡講的Dual指的是用 dual variable去替換primal variable。但我們仍然是在解primal problem。

extend到non linear:我們其實就是把$AA^T$用kernel去做替換（實際上原本的SVM就是linear kernel。）

我們可以仔細觀察一開始的SVM和經過dual varible替換後，式子的差別，事實上我們只差在input，因此我們解最佳化時，其實我們只需要改變我們的input就好。（求出classifier的參數後，記得代入的點也要先經過kernel轉換。）

RSVM (Reduced Support Vector Machine)

從上面我們知道，nonlinear SVM 的 classifier就是：$$f(x)=\sum_{i=1}^l \alpha_ik(x,A_i)+b，$$其實這個classifier就像是一個由$\beta={1}\bigcup{k(.,x^i)}_{i=1}^l$這組basis做線性組合而成的函數（注意$\alpha_i$個數就是training data的個數）

因此RSVM在想的事情就是用subset of $\beta$，其實也就是從原本的training data裡面抽出一些點，來從kernel看相似度。


(李育杰老師投影片)

註：當$l$越多，VC dimention就越大，因為你可以用更多的組合來組出classifier，但也可能造成overfitting。

Different tools for SVM

可直接參考這篇文章：
https://blog.csdn.net/weixin_43746433/article/details/97808078

Reference

paper

paper list:

about loss function:

SMO:

  • Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines

Powered by Hexo and Hexo-theme-hiker

Copyright © 2020 - 2021 DSMI Lab's website All Rights Reserved.

UV : | PV :