## SCAICT 四月課程第二堂
### 機器學習理論與實作(二)
<br>雜項+支持向量機SVM(一)
---
## 簽到
![qrcode_docs.google.com](https://hackmd.io/_uploads/HJQRPNPCa.png)
---
## 二元分類
我們想要將O和X兩類分開來
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
圖中的分隔平面稱作決策邊界(decision boundary)
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
圖中的分隔平面也叫做超平面(hyperplane)
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
hyperplane不一定是一個平面,而是(n-1)維的空間
![hyperplane](https://hackmd.io/_uploads/rJzUGMlbR.png)
>n是特徵的維度
----
決策邊界一樣有hypothesis
$h_\theta(x)=g(\theta^Tx)=g(z)$
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
$g(z)指的是$**閾值函數**
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
例如當$z>0時g(z)=1,z<0時g(z)=0$
![下載 (67)](https://hackmd.io/_uploads/S1pUoflWA.png)
----
$g(z)$也能是sigmoid
即$g(z)=\frac{1}{1+e^{-z}}$
![下載 (64)](https://hackmd.io/_uploads/ByR3sMeW0.png)
----
這讓$g(z)$有點像是$x$屬於某類別的**可能性**
![下載 (64)](https://hackmd.io/_uploads/ByR3sMeW0.png)
---
## SVM
但現在有一種找出決策邊界的方法
支持向量機(SVM, Support Vector Machine)
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
### SVM的直覺
我們先假設數據在二維時線性可分
哪一條線最符合決策邊界?
![89762345](https://hackmd.io/_uploads/rJ3O-TyZR.png =50%x)
----
### SVM的直覺
很明顯A比較好
Why?
![89762345](https://hackmd.io/_uploads/rJ3O-TyZR.png =50%x)
----
### SVM的直覺
是不是因為這條線最大程度的分隔了兩類?
![87987987](https://hackmd.io/_uploads/BJGpTZ5gC.png =50%x)
----
### SVM的直覺
所以我們可以以最大化這個距離為目標
(最大化圖中箭頭長度)
![87987987](https://hackmd.io/_uploads/BJGpTZ5gC.png =50%x)
---
### 最大化間距
----
定義分類器
$h_{w,b}(x)=g(w^Tx+b)$
>$h_{w,b}(x):分類器$
>$g(z):閾值函數$
----
$h_{w,b}(x)=g(w^Tx+b)$
在這裡當$z\ge 0時g(z)=1,z<0時g(z)=-1$
----
### Functional Margin
$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$
>上標$i$表示第$i$筆資料
----
$$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$$
我們觀察一下,因為剛剛提到當$z\ge0$時$g(z)>0$
又$y\in\{-1,1\}$
所以如果決策邊界分類正確則$\hat{\gamma}^{(i)}>0$
----
$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$
![89762345](https://hackmd.io/_uploads/rJ3O-TyZR.png =50%x)
----
剛剛上面的functional margin是對於第$i$筆資料,
對於有n筆資料的資料集 :
$\hat{\gamma}=\min_{i=1,...,n}\hat{\gamma}^{(i)}$
>$\hat{\gamma}:$ 整個資料集的functional margin
----
因為有$\hat{\gamma}=\min_{i=1,...,n}\hat{\gamma}^{(i)}$
那我們現在可以實行最大化間距了嗎?
![87987987](https://hackmd.io/_uploads/BJGpTZ5gC.png =50%x)
----
應該不行喔?
因為$g$只受到$z$的正負號影響而與$z$大小無關
即$g(z)=g(2z)=g(nz)$
>$n\in\mathbb{N}$
----
也就是說$h_{w,b}(x)只是判斷x$在超平面的哪邊
![IMG_0741](https://hackmd.io/_uploads/HkmQWak-A.png =50%x)
----
$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$
所以最大化Functional margin會變成是在
**任意擴展$w,b$**
但這是沒有意義的
----
很像是只找的到B而無法找到A
![89762345](https://hackmd.io/_uploads/rJ3O-TyZR.png =50%x)
---
所以我們另外定義了一個東西
### Geometric Margin
----
**間距**的實質意義是資料點到超平面的距離
即A、B間的距離$\gamma^{(i)}$
![IMG_0742](https://hackmd.io/_uploads/BkjOLWGi6.jpg =50%x)
----
但是functional margin只是表示
「分類結果的可信度有多高」
$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$
----
先觀察超平面上的點B
滿足 $w^Tx_B+b=0$
且 $x_B=x_A-\gamma^{(i)}\cdot\frac{w}{\Vert w \Vert}$
![IMG_0742](https://hackmd.io/_uploads/BkjOLWGi6.jpg =50%x)
----
### 複習
$w(權重)和x(訓練資料)$都是向量
$w=\begin{bmatrix}
w_1\\w_2\ \\...\\ w_d\end{bmatrix},x=\begin{bmatrix}x_1\\x_2\\...\\x_d\end{bmatrix}$
----
### 複習
所以運算$w^Tx時其實就是在做w和x的內積$
$$\begin{aligned}w^Tx=\begin{bmatrix}
w_1\\w_2\ \\...\\ w_d\end{bmatrix}^T\times\begin{bmatrix}x_1\\x_2\\...\\x_d\end{bmatrix}=w_1x_1+w_2x_2+...+w_dx_d\end{aligned}$$
----
### $w$的方向
我們可以找到一向量符合$w^Tx+b=0$
$w$的方向垂直於超平面
![4678i](https://hackmd.io/_uploads/HyURxebZC.png)
----
$x_B=x_A-\gamma^{(i)}\cdot\frac{w}{\Vert w \Vert}$
其中$\frac{w}{\Vert w \Vert}$為$w$方向的單位向量
![IMG_0742](https://hackmd.io/_uploads/BkjOLWGi6.jpg =50%x)
----
$x_B=x_A-\gamma^{(i)}\cdot\frac{w}{||w||}$
![srthrth](https://hackmd.io/_uploads/S1V0Ok-ZC.png)
----
$w^Tx_B+b=0$
$x_B=x_A-\gamma^{(i)}\cdot\frac{w}{\Vert w \Vert}$
因為B在超平面上,所以我們寫出:
$$w^T(x_A-\gamma^{(i)}\frac{w}{\Vert w\Vert})+b=0$$
----
解$\gamma^{(i)}$:
$$\gamma^{(i)}=\frac{w^Tx^{(i)}+b}{\Vert w\Vert}=(\frac{w}{\Vert w \Vert})^Tx^{(i)}+\frac{b}{\Vert w\Vert}$$
----
上面都是在$y=1$時的推導,
為了在$y=-1$時使用,
我們調整一下定義(只是多乘上$y^{(i)}$):
$$\gamma^{(i)}=y^{(i)}((\frac{w}{\Vert w \Vert})^Tx^{(i)}+\frac{b}{\Vert w\Vert})$$
----
### 結論
geoetric margin只是functional margin的標準化結果
這樣我們就能避免$w,b$無限制的擴展了
$\gamma^{(i)}=y^{(i)}((\frac{w}{\Vert w \Vert})^Tx^{(i)}+\frac{b}{\Vert w\Vert})=\frac{\hat{\gamma}^{(i)}}{\Vert w\Vert}$
----
對於整個dataset的geometric margin:
$$\gamma=\min_{i=1,...,n}\gamma^{(i)}$$
現在這就是最小化目標了
----
由於$\gamma=\min_{i=1,...,n}\gamma^{(i)}$
所以我們取的間距是屬於離超平面最近的數據點
這些數據點就稱作「**支持向量Support Vector**」
![87987987](https://hackmd.io/_uploads/BJGpTZ5gC.png =50%x)
---
## 實作二元簡單SVM
https://github.com/ChiuDeYuan/SCAICT_lecture/blob/main/0420/simple_SVM.ipynb
----
## 參考
https://www.jeremyjordan.me/support-vector-machines/
----
## 沒了
### 作業放在dc
---
## 回饋表單
![qrcode_docs.google.com (1)](https://hackmd.io/_uploads/Sy98_NwRT.png)
{"title":"四月課程第二堂","contributors":"[{\"id\":\"8270ce89-c16d-4965-af18-50cdee721260\",\"add\":7282,\"del\":2338}]"}