# 機器學習 03：支援向量機
###### tags: `ML model`, `SVM`
## SVM分類
- **線性SVM**
找到一個決策邊界（decision boundary）讓兩類之間的邊界（margins）最大化，使其可以完美區隔開來。
以向量形式：
決策邊界是節測函數等於 0 的集合，而決策函數等於 1 和 -1 的點，會左右形成一個邊距，所以 SVM 的訓練過程也是尋找適當的 w 和 b 找出最寬的邊距及避免邊距違規（margin violation，實例可以在街道中間或錯誤的那邊）。
若在兩條邊界各取一點 $x_-$ 和 $x_+$，則我們要求的就是 margin 最大寬度 = $x_-$ 和 $x_+$ 於法向量的投影，也就是 $Max(\frac{2}{|\vec W|}$)。
而要求 $Max(\frac{2}{|\vec W|}$) 也就是微分要趨近於 0：
$Max(\frac{2}{|\vec W|}$) = $Min(\frac{2}{|\vec W|}$)' = $Min(\frac{-2}{|\vec W|^2}$) = $Min(\frac{1}{2}|\vec W|^2) = Min(\frac{1}{2}W^TW)$
此外 SVM 對特徵的尺度很敏感：
- **硬邊距分類（hard margin classification）**
嚴格要求所有實例必須在街道外，稱為硬邊距分類，但此做法有兩個缺點
1. 只能處理可線性分割的資料
2. 對離群值敏感
在左圖中，無法找到硬邊距；而右圖的決策邊界與沒有離群值的資料有很大的差異。
**硬邊距分類的分類目標為：$Min (\frac{1}{2}W^TW)$**
- **軟邊距分類（soft margin classification）**
避免這些問題是使用更靈活的模型，除了要讓街道盡量寬大之外，也要放寬邊距違規實例數（margin violation，實例可以在街道中間或錯誤的那邊）。
因此 SVM 有一個超參數為：對於誤差項的懲罰係數 C，當 C 上升，邊距違規數量下降。而同時若 SVM 過擬合時，可以降低 C 來將它正則化。
**軟邊距分類的分類目標為：$Min(\frac{1}{2}W^TW + C \sum\limits_{i=1}^mζ^{(i)})$，其中 $ζ^{(i)}$ 為第 i 個實例允許違規邊距的程度。**
---
以 sklearn 實現：
```python=
import numpy as np
from sklearn import datasets
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC
iris = datasets.load_iris()
X = iris["data"][:, (2, 3)] # petal length, petal width
y = (iris["target"] == 2).astype(np.float64) # Iris virginica
svm_clf = Pipeline([
("scaler", StandardScaler()),
# 務必將 loss 設為 hinge（用於最大間格分類）
("linear_svc", LinearSVC(C=1, loss="hinge", random_state=42)),
])
svm_clf.fit(X, y)
```
---
- **非線性 SVM 分類**
最簡單的做法可用 PolynomialFeatures 將特徵轉換成高維特徵，並搭配 StandardScaler 和 LinearSVC。
話雖如此，在多項式次數很低的情況下，這個方法無法處理很複雜的資料；在次數很高的情況下，會建立大量特徵讓模型過於緩慢。
- 多項式 kernal
這是一種不必實際加入許多多項式特徵，就可以得到一樣結果的數學技術。
```python=
from sklearn.svm import SVC
poly_kernel_svm_clf = Pipeline([
("scaler", StandardScaler()),
# degree：幾次多項式
# coef0 (r)：控制模型受高次多項式和低次多項式的影響程度
("svm_clf", SVC(kernel="poly", degree=3, coef0=1, C=5))
])
poly_kernel_svm_clf.fit(X, y)
```
如果模型過擬合，可以降低多項是次數，如果欠擬合，可以增加多項式次數。
- 高斯 RBF Kernal
- **核函數Kernal Trick**
核函數是在數據的每一類中選定一組點（稱為 Landmark 點），然後計算每一個數據點與這個 Landmark 點的相似度，這種相似度的定義方式就稱為核函數。高斯 RBF Kernal 為：
<font size=5>**$$RBF = e^{-\gamma||x-l||^2} = e^{-\gamma \times Distance^2}$$**</font>
其中**超參數 $\gamma$ 為正則化參數，類似上面提到的 C，如果過擬合就要降低它（$\gamma$ 越大越容易得到封閉決策邊界）**。
Kernal Trick 目標具體而言就是計算決策函數，其中 θ 為特徵，f 為相似度函數，計算每一個點與其他 Landmark 的相似度，當 x 和 landmark 十分接近時，特徵值為約等於 1；當 x 和 landmark 距離很遠時，特徵值為約等於 0：
訓練集中的每一個點都需要被當成 Landmark 點，即假設訓練集中有（A，B，C，D，E）五個點，當把 A 作為訓練對象時，BCDE 四個點均為 Landmark 點，此時要分別計算 A 點與 BCDE 四點的相似度，然後分別乘以對應的 θ 值（該值為提前預設，並在模型訓練的過程中不斷更新）並相加，當最後的和大於等於 0 時，我們把A點歸類為 y = 1，否則歸類為 y = 0。**SVM 的訓練過程，就是不斷尋找 θ 最小值的過程。而決策線就是集合所有 y = 0的點**。
以 sklearn 實現：
```python=
rbf_kernel_svm_clf = Pipeline([
("scaler", StandardScaler()),
("svm_clf", SVC(kernel="rbf", gamma=5, C=0.001))
])
rbf_kernel_svm_clf.fit(X, y)
```
---
### SVM回歸
SVM回歸的目標不是控制邊距違規並在兩個類別之間找到最寬的街道，而是盡量將所有實例放在街道上面，同時控制街道之外的實例。而控制街道寬度的超參數是 $ε$
以 sklearn 實現：
```python=
from sklearn.svm import SVR
svm_poly_reg = SVR(kernel="poly", degree=2, C=100, epsilon=0.1, gamma="scale")
svm_poly_reg.fit(X, y)
```
也可以使用 kernelized SVM 來處理非線性回歸任務：
以 sklearn 實現：
```python=
from sklearn.svm import SVR
svm_poly_reg = SVR(kernel="poly", degree=2, C=100, epsilon=0.1, gamma="scale")
svm_poly_reg.fit(X, y)
```
---
## 計算複雜度
雖然 SVC 支援 kernal trick，但由於時間複雜度介於 $O(m^2 \times n)$ ~ $O(m^3 \times n)$，代表當訓練實例變多時，速度會急遽下降。<font color="#f00">**因此這個演算法非常適合複雜的小型或中型資料集，尤其是特徵很稀疏的情況**</font>。
| 類別 | 時間複雜度 | 支援離合訓練 | 需要縮放 | kernal trick |
| --------- | ---------- | ------------ | -------- | ------------ |
| LinearSVC | $O(m \times n)$ | 否 | 是 | 無 |
| SGDClassifier | $O(m \times n)$| 是 | 是 | 無 |
| SVC | $O(m^2 \times n)$ ~ $O(m^3 \times n)$ | 否 | 是 | 有 |
---
### reference
1. 精通機器學習，使用 Scikit-Learn, Keras 與 Tensorflow－Aurelien Greon
2. [機器學習-支撐向量機(support vector machine, SVM)詳細推導](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E6%94%AF%E6%92%90%E5%90%91%E9%87%8F%E6%A9%9F-support-vector-machine-svm-%E8%A9%B3%E7%B4%B0%E6%8E%A8%E5%B0%8E-c320098a3d2e)
3. [[吴恩达机器学习笔记]12支持向量机4核函数和标记点kernels and landmark](https://blog.csdn.net/u013555719/article/details/82469039)
4. [SVM纯讲解（无数学公式讲解）](https://zhuanlan.zhihu.com/p/54551404)
Sign in with Wallet
Connect another wallet