{%hackmd @kk6333/theme-sty1 %}

###### tags: `Machine learning`
# SVM ( Support Vector Machine )

在神經網路未開始流行時，SVM 可謂最流行的機器學習演算法
因為其有著良好的統計理論解釋性，所以廣受眾人喜愛

## 1. 演算法定義

SVM 與線性回歸有所相似，可以把 SVM 想成是一條線性回歸稱 **HyperPlane**，
並從 HyperPlane 向兩邊延伸出另外兩條相同的回歸線，線之間的距離稱為 **Margin**
利用此二回歸線便可將 Data 分類 ( 這裡是二分類 )


:::info
**HyperPlane 可以寫成下式線性回歸**

$$g(x)=w^Tx+b=0$$

> 另外兩條邊界線則會假設等於 -1、+1

$$g(x)=w^Tx+b=+1$$

$$g(x)=w^Tx+b=-1$$

也就是說可以用 $g(x)$ 來分類

$$g(x) \ge 1 \quad x\in{class 1}$$

$$g(x) \le -1 \quad x\in{class 2}$$

:::

<br>

## 2. Loss function

為了找到最好的權重，我們的目標就是要最大化 ( Maximize ) Margin 來分類
利用這個目標來訂定 Loss Function

:::warning
首先我們要知道兩件事

1. w 向量 ( 權重向量 ) 會**垂直方程式本身**，也可以稱為法向量
2. g(x) 算出的意義是指 **x 離 HyperPlane 的距離 ( 但並非實際數值距離 )**
:::

知道以上兩件事就可設定 Loss function

:::info
> 要算出實際離 HyperPlane 的距離要用 $g$ 在除上 $w$ 長度

$$z=\frac{g(x)}{|w|}$$

> 目標可以寫成下式

$$max( \frac{g(x)}{|w|})$$

> 但為了方便計算，通常會將最大化任務轉換為最小化任務，這裡用倒數表示
> 因為 g(x) 我們不可調整 ( 視為常數 ) ，所以省略 $g(x)$

$$J(\omega)=|w|$$

> $J(\omega)$ 代表 loss function
> 為了方便之後微分，再對他做一點手腳

$$J(\omega)=\frac{1}{2}|w|^2$$

> 目標變為

$$min(J(\omega))=min(\frac{1}{2}|w|^2)$$

:::

<br>

## 3. Optimization

有了 Loss Function 就可以來最小化 loss 並更新權重了
這邊所用的優化方法會用到 [拉格朗日乘數 ( Lagrange Multiplie )](/1Q1vfKamS3y126q3KhX-pQ) 中的 KKT 方法

:::info
> 約束函數會定義為以下式
> 也就是當預測正確時，$h(x)$ 會小於 0，反之大於 0，用此方法描述 Margin 的約束

$$h(x)=1-yg(x) = 1-y( w^Tx+w_0 )$$

$$
\begin{cases}
y=+1 \quad ,x\in{class1} \\
y=-1 \quad ,x\in{class2} \\
\end{cases}
$$

> 之後再套上 KKT

$$L(x,\lambda) = J(w) + \sum_i^n \lambda_i h(x)$$

<font color=red>$$L(x,\lambda) = J(w) + \sum_i^n \lambda_i ( 1 - y( w^Tx+w_0 ) )$$</font>

> 這樣就得到在 Margin 約束下的 $J(w)$ 函數，並可以進行優化 ( 偏微分 )
>

<font color=red>$$\frac{\partial{J}}{\partial{w}}=w-\sum \lambda_iy_ix_i \Rightarrow \sum \lambda_iy_ix_i=w$$</font>

<font color=red>$$\frac{\partial{J}}{\partial{w_0}}=-\sum\lambda_iy_i=0 \Rightarrow \sum \lambda_iy_i=0$$</font>

> 即得到新的權重
:::

<br>

## 4. 資料非線性分佈
上述所做的計算都是假設我們的 Data x 呈現線性分佈
但實際的資料通常都不會如此，而會夾雜很多非線性因素

要解決這個問題的其中一種方式是，在 loss 中加入一個鬆弛變量 ( $\xi$ ) ，使 Margin 有更多彈性


:::info
> Loss Function 改寫成以下式

<font color=red>$$J(\omega)=\frac{1}{2}|w|^2+C\sum_i^n \xi_i $$</font>

> 之後在用前面講的優化方式進行優化

:::

**當然 SVM 還有很多其他方式可以解決非線性問題，像是將 Model 升級一個維度**

{%youtube 3liCbRZPrZA %}

## 5. reference

[【机器学习】支持向量机 SVM（非常详细）](https://zhuanlan.zhihu.com/p/77750026)

[[資料分析&機器學習] 第3.4講：支援向量機(Support Vector Machine)介紹](https://medium.com/jameslearningnote/%E8%B3%87%E6%96%99%E5%88%86%E6%9E%90-%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E7%AC%AC3-4%E8%AC%9B-%E6%94%AF%E6%8F%B4%E5%90%91%E9%87%8F%E6%A9%9F-support-vector-machine-%E4%BB%8B%E7%B4%B9-9c6c6925856b)

[SVM with polynomial kernel visualization](https://www.youtube.com/watch?v=3liCbRZPrZA)