# 李宏毅_ML_Lecture_20
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## ML Lecture 20: Support Vector Machine (SVM)
[課程連結](https://www.youtube.com/watch?v=QSEPStBgwRQ&index=29&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49)
### Outline

SVM有兩個特色：
1. Hinge Loss
2. Kernel Method

兩者相加就是SVM
### Binary Classification

最開始在提到Binary Classification的時候提到機器學習三步驟：
1. 找出一個Function set(Model)
* 當$f(x)$>0，則輸出+1
* 當$f(x)$<0，則輸出-1
2. 定義Loss function
3. 利用Gradient Descent優化

說明SVM的範例上會以+1、-1來表示，不同於說明Logistic Regression的時候以1、0表示，但意義相同。

註：$\hat{y}$代表實際label
### Step 2:Loss function

上圖橫軸是$\hat{y}$乘上$f(x)$，縱軸為loss：
1. $f(x)$、$\hat{y}$的值為+1、-1
2. $\hat{y}$為+1的時候$f(x)$愈大愈好
3. $\hat{y}$為-1的時候$f(x)$愈負愈好

也就是兩者同號的時候相乘要愈大愈好，愈往右兩者相乘愈大其loss愈小，理想上當兩者不同的時候輸出為0，相同的時候輸出為1，但這種loss是不可微，因此需要利用其它方式來表示loss function。

### Step 2:Loss function - Square loss

* loss function: $l(f(x^n),\hat{y}^n)=(\hat{y}^nf(x^n)-1)^2$
* $\hat{y}^n=1$，$f(x)$愈接近1愈好
* $(f(x^n)-1)^2$
* $\hat{y}^n=-1$，$f(x)$愈接近-1愈好
* $(-f(x^n)-1)^2=(f(x^n)+1)^2$

Square loss function的趨勢圖如紅線，但這種方式應用於binary classification是不合理的_{(見logistic課程說明)}，因為當$\hat{y}^nf(x^n)$相乘很大的時候竟然有很大的loss
### Step 2:Loss function - Sigmoid + Square loss

* loss function: $l(f(x^n),\hat{y}^n)=\sigma((\hat{y}^nf(x^n)-1))^2$
* $\hat{y}^n=1$，$\sigma(f(x))$愈接近1愈好
* $\sigma((f(x^n)-1))^2$
* $\hat{y}^n=-1$，$\sigma(f(x))$愈接近0愈好
* $\sigma((-f(x^n)-1))^2=(1-\sigma(f(x))-1)^2=(\sigma(f(x)))^2$

Sigmoid + Square Loss趨勢如藍線，但在Losgistic Regression提過，一般不會使用Square Loss，而是Cross entropy。
### Step 2:Loss function - Sigmoid + cross entropy

* loss function: $l(f(x^n),\hat{y}^n)=ln(1+exp(-\hat{y}^nf(x)))$

每一個$\sigma(f(x))$都代表一個distribution，distribution之間的cross entropy就是要優化的loss，趨勢如綠線。

直觀比較Sigmoid+cross entropy與Sigmoid+Square loss，當值由-2前進到-1的時候會發現，cross entropy有著比較大的變化，但對Square loss而言是沒有的顯著的影響，因此在train的時候會有很大的落差。
### Step 2:Loss function - hinge loss

* loss function: $l(f(x^n),\hat{y}^n)=max(0,1-\hat{y}^nf(x))$
* $\hat{y}^n=1$
* $max(0,1-f(x))$
* loss最小值為0
* 當$1-f(x)<0$則loss為0
* $f(x)>1$
* $max(0,1+f(x))$
* loss最小值為0
* 當$1+f(x)<0$則loss為0
* $f(x)<-1$

hinge loss趨勢如紫線，可以發現當$\hat{y}^nf(x)>1$之後它的loss就是0，再大都沒有幫助。但是對於同方向的結果_{(正正、負負)}而言，只有對還不夠，因為好還要更好，意思就是當$\hat{y}^nf(x)$沒有大於1的時候，它還是會存在penalty_(懲罰)來促使$\hat{y}^nf(x)>1$。

hinge loss為max(0,**1**)的原因在於，與cross entropy相同都希望是ideal loss的upper bound，透過minimize hinge loss來得到minimize ideal loss的效果。

普遍來說，hinge loss與cross entroyp之間的差異並沒有那麼顯著，但hinge loss會比較robust。
### Linear SVM

Linear SVM即線性SVM，其特性如下：
* function是很標準的$f(x)=w^Tx$
* loss function採用hinge loss
* 通常會加上正規項
* hinge loss與L2 Norm皆為convex function，兩者疊加依然為convex function
* 雖然表面看來很多地方不可微，但如同relu與maxout一般，依然是可以利用梯度下降來優化

SVM與Logistic Regression的差別就在於loss function的定義：
* lr: cross entropy
* linear svm: hinge loss

SVM的function並不一定要linear，因此也有deep svm_{(見上圖參考文件)}，只要你的loss fucntion使用hinge loss，就是一個deep svm
### Linear SVM - gradient descent

傳統上較少使用Gradient descent來優化SVM，一種方式稱為『Picasso』，上圖為推導過程。
### Linear SVM - another formulation

上面說明的SVM與平常所見不同，上圖推導以普遍所見SVM說明，將$l(f(x^n),\hat{y}^n)$以$\epsilon^n$替代，而$\epsilon^n=max(0, 1-\hat{y}^nf(x^n))$，在條件限制下可以調整如下：
* $\epsilon^n\geq 0$
* $\epsilon^n\geq 1-\hat{y}^nf(x^n)$

$\epsilon^n$是一個$(0, 1-\hat{y}^nf(x^n))$取大的值，因此可以調整如上兩個式子，如果不考慮Minimizing loss function的條件式的話這兩個式子就不會等價，因為任一個值都可以符合條件式，只有在目標Minimizing loss function下，才能讓式子等價。
### Dual Representation

實際上模型就是data point的Linear Combination_{(線性組合)}，上圖下方是對各學習參數做更新的數學式，假設有k維，它們的式子都一樣，只有最後的value不同_{$x^n_1,x^n_i,x^n_k$}。

將數學式以向量來表示，每次更新都是將$w-\eta\sum_nc^n(w)x^n$，$c^n(w)$為f對Loss Function的偏微分，這代表如果我們初始化$w$是一個zero vector，那每次的更新都是加入data points的Linear Combination，最後利用Gradiend Descent解出來的$w$就是$w$的Linear Combination，加上Hinge Loss的特性，當作用域在max為0的時候則$c^n(w)$為0，因此得到的解會是稀疏解(sparse)，代表很多data point對應的$\alpha^*$值為0，而值不為0的$x^n$即為support vectors。

並非所有的點都會被選擇為support vector，因此SVM的結果會較為rubust。

* cross entropy:
* 微分皆不為0
* 每一個data point都對結果造成影響
* hinge loss:
* 所得為稀疏解
* 僅值不為0的對結果有影響
### Dual Representation

直觀來看，我們已經知道W是data point的Linear Combination，這麼做的好處在於kernel trick，因此我們將式子調整以向量化來表示$w=X\alpha$。

首先，將$f(x)$套入上面向量化的數學式，$f(x)=w^Tx=\alpha^TX^Tx$，最終得到的會是一個scalar，即$f(x)=\sum_n\alpha_n(x^n\cdot x)=\sum_n\alpha_nK(x^n\cdot x)$，以向量化來計算不用太過擔心效率問題，加上hinge loss的特性為sparse，多數為0，再將$(x^n\cdot x)$帶入function$K$即kernel function。
### Dual Representation

定義好$f(x)$之後，我們就需要最小化loss，而$(x^n\cdot x)$並沒有參數，參數在$\alpha_n$，因此我們要找一個$\alpha_n$讓loss最小。

$L(f)=\sum_nl(f(x^n),\hat{y}^n)=\sum_nl(\sum_{n'}\alpha_{n'}K(x^{n'}, x^n),\hat{y}^n)$_{($n,n'$皆為所有的training data)}。

我們不再需要知道x的vector為何，只需要知道x與vector z的內積值即可，或者說我們只需要知道kernel function_{($K(x^{n'},x^n)$)}就可以做優化了，這就是**Kernel Trick**。

Kernel Trick並非只能應用於SVM，Linear Regression、Logistic Regression也可以，因此也可以有Kernel based的Linear Regression、Logistic Regression。
### Kernel Trick

之前課程提過，Linear Model有諸多限制，可能要對輸入的特徵做一些轉換，才能用Linear Model來處理，在NN中就是利用多個Hidden Layer來做Feature Transform。

假設一筆資料$x$，二維特徵，預計Feature Transform為$\phi(x)$_{(考慮$x_1,x_2$之間的關係)}之後再應用到Linear SVM。

將資料帶入Kernel Function之後會發現，$\phi(x)\cdot \phi(z)$的結果等同於Feature Transform之前的內積之後再平方的值。

這麼做的好處在於，直接在原始空間上的計算會比做完Feature Transform再做內積還要來的快。
### Kernel Trick

假設現在不是二維特徵，而是k維特徵並且考慮所有特徵兩兩之間的關係_(ck取2)，這時候利用Kernel Trick就可以輕鬆的算出結果，只需要計算$(x\cdot z)^2$就可以得到$\phi(x)\cdot \phi(z)$的結果。

### Radial Basis Function Kernel -rbf kernel

rbf kernel即$K(x,z)=\exp(-\dfrac{1}{2}||x-z||_2)$，以此衡量$x,z$之間的相似度，值愈大代表愈像，而rbf也可以代表兩個高維度向量做內積的結果=$\phi(x)\cdot\phi(z)$，而這兩個高維度向量的維度是無窮多維的。

但你根本做不到計算無窮多維的向量，可是你可以計算$K(x,z)=\exp(-\dfrac{1}{2}||x-z||_2)$，使用rbf kernel的時候就像是將資料投射到無窮多維的平面上去計算，因此也很容易overfitting
### Sigmoid Kernel

$K(x,z)=tanh(x\cdot z)$即$f(x)=\sum_n\alpha^ntanh(x^n\cdot x)$

當使用Sigmoid Kernel的時候，某種角度來看它就是一個One Hidden layer的神經網路，將$x^n$視為權重去做內積再加總得到output。
### Kernel Trick

有了Kernel Trick之後，我們不需要瞭解$\phi(x)$,$\phi(z)$到底長什麼樣子，只要能夠將$x,z$帶入Kernel Function，並且output一個數值來代表$x,z$在某一個高維平面上的vector的Inner Product就可以。

這一招在$x$屬結構性資料的時候有效，舉例來說，像是sequence，每一個sequence的長度都不一樣，這時候並不好用vector來描述它，因此你根本不知道$x,\phi x$長什麼樣子。

我們現在知道Kernel Function就是投影到高維空間之後的Inner Product，因此它是一個類似相似度_(similarity)的東西。

如果可以定義一個Function可以計算$x,z$之間的相似度，就有機會把它當做Kernel來使用，這可以利用`Mercer's theory`來驗證
### SVM related methods

* SVR:
* 當資料集進入範圍內的時候，它的loss即為0
* One-class SVM
* positive的資料自成一類，其它資料散佈於其它地方
### Deep Learning and SVM

SVM做的事就像是Deep Learning，而且它是可以學習的，只有一個Kernel Function的時候它就是一個One Hidden layer神經網路，將多個Kernel Function合併的時候就有多層了。