# SVM 原理詳解
## Linear SVM 線性可分離
**Defined:**
找到超平面，並使得$P_1,P_2$相等，且$P_1,P_2$的長度要為最長。
conclusion remark: 演算法在無限多超平面上須找出能夠最大距離的分界線，作為分類器。

**Example:**
S:training dataset = $f(\vec {x_i},\vec {y_i})_{i=1...10}$
Where i=1~5 is positive, i=6~10 is negative.
**SVM function:**
$$H=\vec {W}^t \vec x+b$$
需要找到一個具有最大p值得hyperplane
針對 i=1~5而言 $\vec {W}^t \vec x+b \ge 1$ ; 針對 i=1~5而言 $\vec {W}^t \vec x+b \le -1$

**subject to :**
$⇔$ Maximum function $p(\vec W)$, $p=\cfrac{2}{||\vec W||}$, where $p=p_1+p_2$
$⇔$ Minimal $\cfrac{1}{2}||\vec W||$ $⇔$ Minimal $\cfrac{1}{2}||\vec W||^2$
$⇔$ Minimal $\cfrac{1}{2}||\vec W||^t\vec W$
$y_i(\vec {W}^t \vec x+b) \ge 1$ , where $i$=1~10

## 最佳化問題(Constrained Optimization problem)
以SVM為例是為了求解 $\vec W$ 與 b
Minimum = $\cfrac{1}{2}||\vec W||^2$ => $f(\vec W)$ => 目標函數
**subject to :**
$y_i(\vec {W}^t \vec x+b)-1 \ge 0$ , $\forall i$ =1~10

### Lagrangian Method
Define: 給定一個拘束最佳化問題
Q = 目標函數, $\alpha$ * constrain1, $\beta$ * constrain2
$\alpha ,\beta \in$非負的值，則稱Lagrange
$$Q=f(\vec x)-\alpha h(\vec x)-\beta g(\vec x)$$ **where :** $$\alpha ,\beta \ge 0$$ **解開拘束最佳問題Step :**
1. 將Lagrange Q表示出來
2. 將Q對先前變數進行篇微分，令其為零
3. 將Step2結果帶回Q，消除先前變數求解$\alpha ,\beta$
4. 利用KT condition求解剩餘變數

**------範例------**

**STEP1 :**
$$Q=\cfrac{1}{2}||\vec W||^2 -\alpha _1[y_1(\vec {W}^t \vec x_1+b)-1] - ....-\alpha _n[y_n(\vec {W}^t \vec x_n+b)-1]$$
$$=\cfrac{1}{2}||\vec W||^2 - \sum^N_{i=1} \alpha _i[y_i(\vec {W}^t \vec x_i+b)-1]$$

**STEP2 :** 先前變數為$\vec W , b$
$${∂Q\over ∂\vec W}=0$$
$$={∂\over∂\vec W}[{1\over 2}||\vec W||^2-\sum^N_{i=1} \alpha _i[y_i(\vec {W}^t \vec x_i+b)-1]$$
$$=\vec W-{∂\over ∂\vec W}\sum^N_{i=1} (\alpha _iy_i\vec {W}^t \vec x_i+\alpha _iy_ib-\alpha _iy_i)$$
$$=\vec W-\sum^N_{i=1}(\alpha _iy_i\vec x_i)=0$$
這邊$y_i,\vec x_i$ 是已知數，$\alpha _i$是未知數，$\vec W-\sum^N_{i=1} (\alpha _iy_i\vec x_i)=0$．．．．．．．$(1)$
$${∂Q\over ∂b}=0$$
$$-\sum^N_{i=1}\alpha_iy_i=0$$
$\sum^N_{i=1}\alpha_iy_i=0$．．．．．．．$(2)$

**STEP3 :** 將式子$(1),(2)$帶回到Q
$$Q=\cfrac{1}{2}||\vec W||^2 - \sum^N_{i=1} \alpha _i[y_i(\vec {W}^t \vec x_i+b)-1]$$
式子$(1)$帶入 $\vec W$
$${1\over2}||\vec W||^2 \Rightarrow {1\over2}\sum^N_{i=1}(\alpha _iy_i\vec x^t_i)\sum^N_{j=1}(\alpha _jy_j\vec x_j)$$

對 ${∂\over ∂\vec W}\sum^N_{i=1} (\alpha _iy_i\vec {W}^t \vec x_i+\alpha _iy_ib-\alpha _iy_i)$ 拆解
這裡$(1)$帶入 $\vec W$
$$\sum^N_{i=1}\alpha _iy_i\vec {W}^t \vec x_i=\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j\vec x^t_i \vec x_j$$

這裡$(2)$帶入 $\sum^N_{i=1}\alpha_iy_i=0$
$$\sum^N_{i=1}\alpha _iy_ib=0$$
這裡$(2)$帶入 $\sum^N_{i=1}\alpha_iy_i=0$，因為$y_i$不是1就是-1
$$\sum^N_{i=1}\alpha _iy_i=\sum^N_{i=1}\alpha _i$$
**Finally :**
$$Q=\sum^N_{i=1}\alpha _i - \sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j\vec x^t_i \vec x_j$$

**所以之前的問題改為下列對偶問題**
$${Maximum \over \alpha_1 \rightarrow \alpha_n}\sum^N_{i=1}\alpha _i - {1\over2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j\vec x^t_i \vec x_j$$
**subject to:**
$$\alpha_1 \ge 0$$ $$\sum^N_{i=1}\alpha_iy_i=0$$
**凸函數長這樣**

## Linear SVM 線性不可分離
目前世界上大多的問題皆為線性不可分離，但線性不可分離是以線性可分離的方式所延伸。


**<目標一>** 線性不可分離的作法依然是要找到:
$⇔$ maximize ρ (邊界距離${ρ_1 ,ρ_2}$)
$⇔$ maximize $2 \over {||W||}$
$⇔$ minimize ${1 \over 2}{||W||^2}$

**Define: 鬆弛變數(Slack Variable) ξ**
$ξ:$代表相對應的training data分類錯誤的一種指標
==$ξ>0$ 不代表data分類錯誤，但data分類錯誤代表 $ξ>0$==

~~positive data到H=1的距離 ，negative data到H=-1的距離~~
若positive data 在H=1的反側,則 $ξ>0$
若positive data 在H=-1的反側,則 $ξ>0$

**<目標二>** 希望找到一個hyperplane，使得 $ξ_1+ξ_2+...+ξ_n$之總和最小
∵$\sum_{i=1}^{10}ξ_i$ 越小代表training data分類錯誤越小
$⇒$ ==經驗風險最小化(Empirical risk minimization, ERM)==

$⇔$ minimize $\sum_{i=1}^{10}ξ_i$

**Subject to :**
- $ξ_i \ge 0, ∀_{i=1...10}$
- $ξ_i(\vec W^t x_i +b)-1-ξ_i \ge 0$

**------範例------**
|以$X_1$ 為例|
|:--
|$$\vec W^t \vec x_1+b \ge 1 - ξ_1 → 0$$ $$⇒ y_1(\vec W^t \vec x_1+b) - 1 + ξ_1 \ge 0$$

|以$X_5$ 為例
|:--
|$$\vec W^t \vec x_5+b \ge 1 → 不成立$$ $$\vec W^t \vec x_5+b \ge 1 - ξ_5 → 成立$$ $$⇒ y_5(\vec W^t \vec x_5+b) - 1 + ξ_5 \ge 0$$

|以$X_7$ 為例
|:--
|$$\vec W^t \vec x_7+b \le -1 + ξ_7 → 0$$ $$⇒ y_7(\vec W^t \vec x_7+b) - 1 + ξ_7 \le 0$$
|where $y_7 = -1$
|$$⇒ y_7(\vec W^t \vec x_7+b) + 1 - ξ_7 \ge 0$$

|以$X_{10}$ 為例
|:--
|$$\vec W^t \vec x_{10}+b \le -1 → 不成立$$ $$\vec W^t \vec x_{10}+b \le -1 + ξ_{10} → 成立$$ $$⇒ y_{10}(\vec W^t \vec x_{10}+b) - 1 + ξ_{10} \ge 0$$
|where $y_{10} = -1$
|$$⇒ y_{10}(\vec W^t \vec x_{10}+b) + 1 - ξ_{10} \ge 0$$

對這10筆training data皆要滿足以下條件
$$y_i(\vec W^t \vec x_i+b) + 1 - ξ_i \ge 0$$

**※線性不可分離的SVM問題，可由拘束最佳化問題來求解超平面之 $\vec W , b$**

Minimize : ${1\over 2}||\vec W||^2 + C \sum_{i=1}^Nξ_i$

==(這裡C為一個自定義常數，C越大ρ線寬越小)==

**Subject to :**

- $ξ_i(\vec W^t x_i +b)-1-ξ_i \ge 0$
- $ξ_i \ge 0, ∀_{i=1...10}$

### 利用 Lagrangian Method 推導出對偶問題
1. 寫出Lagrangian function $⇒$ Q
$$Q=\cfrac{1}{2}||\vec W||^2 + C \sum_{i=1}^Nξ_i - \sum^N_{i=1} \alpha _i[y_i(\vec {W}^t \vec x_i+b)-1+ξ_i] - \sum_{i=1}^Nβ_i ξ_i$$
其中 $α_i ,β_i$ 為非負整數值，皆為 Lagrangian mutipliers

**Note :**
- Q = 目標函數, $\alpha$ * constrain1, $\beta$ * constrain2
- ==$Q=\cfrac{1}{2}||\vec W||^2 + C \sum_{i=1}^Nξ_i$== 為目標函數
- ==$ξ_i(\vec W^t x_i +b)-1-ξ_i \ge 0$== 為約束一號
- ==$ξ_i \ge 0, ∀_{i=1...10}$== 為約束二號

2. 偏微分Q，並令其=0 ==(不懂就往上看線性SVM)==
$${∂Q \over ∂\vec W}=0, {∂Q \over ∂b}=0, {∂Q \over ∂ξ_i}=0$$
${∂Q \over ∂\vec W}=0 ⇒ \vec W = \sum^N_{i=1}(\alpha _iy_i\vec x_i)$
${∂Q \over ∂b}=0 ⇒ \sum^N_{i=1}\alpha_iy_i=0$
${∂Q \over ∂ξ_i}=0 ⇒ C - \alpha _i - \beta_i =0$

3. 帶回

$$Q=\sum^N_{i=1}\alpha _i - \sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j\vec x^t_i \vec x_j$$

**Subject to :**
$\sum^N_{i=1}\alpha_iy_i=0$
$α_i \ge 0, β \ge 0, C \ge α_i$ $⇒ 0 \le α_i \le C, ∀_{i=1...n}$

### 利用KT condition 求解最佳化問題中剩餘的變數
例如 SVM 中 hyperplane 的 b

**Theorem :** 若一個拘束行最佳化問題為
|$Min / Max$|$f(x)$
|:-----------|:--
|Subject to :|$g(x) \ge 0, h(x) \ge 0$
則其 **Kuhn–Tucker conditions (KT condition)** 為

令: ==Lagrange Multiplier $*$ constrain = 0==
其中 Lagrange Multiplier 與 constrain 只有一個為 0
$$ \alpha g(x) = 0, \beta h(x) = 0$$

#### 利用 KT condition求解 b
|SVM 的 KT condition 為||
|:--|:--
|$$\alpha _i[y_i(\vec {W}^t \vec x_i+b)-1+ξ_i]=0$$ | $$∀_{i=1...n}$$
|$$\beta_iξ_i=0 ⇔ (C-\alpha_i)ξ_i$$ |$${∂Q \over ∂ξ_i}=0 ⇒ C - \alpha _i - \beta_i =0$$ $$∀_{i=1...n}$$
又 $\alpha_{i...n} ∈ [0, C]⇒ 0 \le α_i \le C$

因此 $\alpha_i$ 有三種可能
- $\alpha_i = 0$
- $0 \lt α_i \lt C$
- $\alpha = C$

|$\alpha_i = 0$|
|:--|
|$$(c-\alpha_i)ξ_i=0⇒ξ_i=0$$
> $\vec x_i$ 在 $H=1$ 的上方，$y_i=1$
> $\vec x_i$ 在 $H=-1$ 的下方，$y_i=-1$
> ==表示 $\vec x_i$ 必定分類正確==

| $0 \lt α_i \lt C$||
|:--|:--
|$$ ∵ (c-\alpha_i)ξ_i=0⇒ξ_i=0$$
|$$\alpha _i[y_i(\vec {W}^t \vec x_i+b)-1+ξ_i]=0$$ $$y_i(\vec W^t x_i +b)-1= 0$$| where $\alpha_i≠0$, $ξ_i=0$
|$$b^*={1\over{y_i}}-\vec W^t \vec x_i$$
所以拿一筆training data $\vec x_i$, 且其 Lagrange multiplier $\alpha_i$ 的值， $0 \le α_i \le C$ 將 $\vec x_i$ 及其 class class 帶入上式，==即可求出超平面的b值最佳解==。
> $\vec {W}^t \vec x_i+b =1$, if $y_i=1$
> $\vec {W}^t \vec x_i+b =-1$, if $y_i=-1$

|$\alpha_i=C$||
|:--|:--
|$$ ∵ (c-\alpha_i)ξ_i=0⇒ξ_i > 0$$ | $$\vec x_i 在 H=1 的上方，y_i=1$$ $$\vec x_i 在 H=-1 的下方，y_i=-1$$
|$$\alpha _i[y_i(\vec {W}^t \vec x_i+b)-1+ξ_i]=0$$ $$y_i(\vec {W}^t \vec x_i+b)-1+ξ_i=0$$ $$b^*={{1-ξ_i}\over{y_i}}-\vec W^t \vec x_i$$

### Decision function
$\vec W^t,b$ 都解出來了!
若 $\vec x$ ∈ test data
$D(x)=\vec W^t \vec x+b$
> $\vec x$ 為 positive, if $D(x)>0$
> $\vec x$ 為 negative, if $D(x)<0$
> 又 $\vec W = \sum^N_{i=1}(\alpha _iy_i\vec x_i) = \alpha_1y_1\vec x_1$ + ... + $\alpha_ny_n\vec x_n$
for some $\alpha_i$ 可忽略，==只需計算$\alpha > 0$ 的項次==。

**Defined :**
若訓練資料的lagrange multiplier 大於 0，則此資料稱為支持向量(SVM)。

如果 $\vec x_i :$ training data.
$\vec x_i :$ support vector ⇔ $0 \lt \alpha_i \le C$
$\therefore$ support vector Set SV : { $\vec x_i ∣ 0 <\alpha_i \lt C$ }
$$D(x)=\sum^N_{i=1}(\alpha _iy_i\vec x_i)\vec x + b$$ $$= \sum^N_{x_i∈SV}(\alpha _iy_i\vec x_i)\vec x + b$$

**---------範例---------**
## XOR problem
找一個hyperplane 將 positive & megative class 分離

$x_1$ = $\begin {bmatrix} 1 \\ 1 \end {bmatrix}$，$y_1$ = 1，$x_2$ = $\begin {bmatrix} -1 \\ -1 \end {bmatrix}$，$y_2$ = 1

$x_3$ = $\begin {bmatrix} -1 \\ 1 \end {bmatrix}$，$y_3$ = -1，$x_4$ = $\begin {bmatrix} 1 \\ -1 \end {bmatrix}$，$y_4$ = -1

==但在此空間中找不到 hyperplane 可將兩類別進行分離==
如果定義函數 $\phi$ 使其 :

$\vec x \begin {bmatrix} f_1 \\ f_2 \end {bmatrix}$ 映射到 $\phi (\vec x) \begin {bmatrix} f_1 \\ \sqrt 2f_1f_2 \\ f_2 \end {bmatrix}$

$\vec Z_1 = \phi (\vec x_1) \begin {bmatrix} 1 \\ \sqrt 2 \\ 1 \end {bmatrix}$，$\vec Z_2 = \phi (\vec x_2) \begin {bmatrix} -1 \\ \sqrt 2 \\ -1 \end {bmatrix}$

$\vec Z_3 = \phi (\vec x_3) \begin {bmatrix} -1 \\ -\sqrt 2 \\ 1 \end {bmatrix}$，$\vec Z_4 = \phi (\vec x_4) \begin {bmatrix} 1 \\ -\sqrt 2 \\ -1 \end {bmatrix}$

在$R^3$ 的空間中兩分類卻變成了可線性分類，並存在一個hyperplane。
(以下為大約示例)

### **NonLiner SVM**
1. 將training data $\vec x_{=1...n}$，經由非線性映射到高維度空間中，稱該空間為feature space。

2. 在 feature space 中學習出一個==最佳的超平面(Optimal separating hyperplane，DSH)==

**Nonlinear SVM is formulated as :**
> Minimize : ${1\over 2}||\vec W||^2 + C \sum_{i=1}^Nξ_i$

**Subject to :**
> $ξ_i(\vec W^t \phi (\vec x_i) +b)-1-ξ_i \ge 0$
> $ξ_i \ge 0$

**Aim :** 求解 $\vec W, b$
1. 將Lagrange Q表示出來
2. 將Q對先前變數進行篇微分，令其為零
3. 將Step2結果帶回Q，消除先前變數求解$\alpha ,\beta$
4. 利用KT condition求解剩餘變數

**STEP 1 :**
$$Q=\cfrac{1}{2}||\vec W||^2 + C \sum_{i=1}^Nξ_i - \sum^N_{i=1} \alpha _i[y_i(\vec {W}^t \vec \phi (\vec x_i)+b)-1+ξ_i] - \sum_{i=1}^Nβ_i ξ_i$$
**STEP 2 :**
$${∂Q \over ∂\vec W}=0, {∂Q \over ∂b}=0, {∂Q \over ∂ξ_i}=0$$
$${∂Q \over ∂\vec W}=0 ⇒ \vec W = \sum^N_{i=1}(\alpha _iy_i \phi(\vec x_i))$$
$${∂Q \over ∂b}=0 ⇒ \sum^N_{i=1}\alpha_iy_i=0$$
$${∂Q \over ∂ξ_i}=0 ⇒ C - \alpha _i - \beta_i =0$$
**STEP 3 :**
$$Q=\sum^N_{i=1}\alpha _i - {1\over2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j \phi(\vec x_i) \phi(\vec x_j)$$

Subject to :
$$\sum^N_{i=1}\alpha_iy_i=0$$

$$α_i \ge 0, β \ge 0, C \ge α_i⇒ 0 \le α_i \le C, ∀_{i=1...n}$$
**STEP 4 :**
|KT condition
|:--
|$$\alpha _i[y_i(\vec {W}^t \phi(\vec x_i)+b)-1+ξ_i]=0$$ $$\beta_iξ_i=0 ⇔ (C-\alpha_i)ξ_i$$
如果 $\alpha_i =0，ξ_i=0$ 必定分類正確。

如果 $0 <\alpha_i \lt C，ξ_i=0$
$$b^*={1\over{y_i}}-\vec W^t \phi(\vec x_i)$$ $$b^*={1\over{y_i}}-\sum_{j=1}^N\alpha_j y_j\phi(\vec x_j) \phi(\vec x_i)$$

**$\therefore$ 若 $\vec x$ 是一筆test data，則決策函數為 :**
$$D(\vec x)=\vec w^t\phi(\vec x)+b$$ $$=\sum_{i=1}^N\alpha_i y_i\phi(\vec x_i)\phi(\vec x)+b^*$$

### **核函數(kernel function)**
$K(\vec x_i,\vec x_j)≡\phi(\vec x_i) \circ \phi(\vec x_j)=$ $\phi(\vec x_j)\circ \phi(\vec x_i)$
K稱之為核函數。

**通用核函數**
- 多項式核函數(Polynoniel kernel)
自定義參數 $p :$ =1 or 2 or 3 ...
$$K(\vec x_i,\vec x_j)≡\phi(\vec x_i)\circ \phi(\vec x_j)$$ $$=(1+\vec x_i^t \vec x_j)^p\\OR\\=(\vec x_i^t \vec x_j)^p$$

- 高斯核函數(Gaussion kernel)
自定義參數 $σ :$ 高斯的寬度 ( 0<σ<∞ )
$$K(\vec x_i,\vec x_j)≡\phi(\vec x_i)\circ \phi(\vec x_j)$$ $$=e^{||\vec x_i-\vec x_j||^2 \over {-2σ^2}}$$
**Note :** 高斯核函數也稱為輻射基底函數(Radial Basis function，RBF) or (RBF kernel)