# [Note] CS229 Lecture 6 : Support Vector Machine

---

上一篇: https://hackmd.io/@ChiuChiuCircle/cs229_5

---

Online lecture: https://youtube.com/playlist?list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU&si=vuAUi_ytVYB1Jc8V

Main notes: https://cs229.stanford.edu/main_notes.pdf
Other resources: https://github.com/maxim5/cs229-2018-autumn/tree/main

---

## Margins
還記得在二元分類中，
機率$p(y=1\vert x;\theta)是由h_\theta(x)=g(\theta^Tx)$所控制的，
當$h_\theta(x)\ge0.5\ \ \ (\theta^Tx\ge0)$ 則預測值將會輸出$1(positive)$。

我們在得到結果時，
會希望模型對答案的肯定度越高越好(cross entropy越小越好)，
所以當$y=1\ \ 時\ \ \theta^Tx\gg0$，
或是當$y=0\ \ 時\ \ \theta^Tx\ll0$，
這個$\theta$就能被稱作適合此訓練資料(informally)。

上面這張圖展現了二元分類，
分隔兩類是**決策邊界(decision boundary)**，又稱為**separating hyperplane**。

我們可以看到，
A跟C雖然都在同一類，
但A比C在分類上更有信心(margin比較大)。

所以現在看來，
最大化margins是我們優化預測的好方法。

## Notation
我們之前的$y=\{0,1\}$，現在$y=\{-1,1\}$。
並且將分類器如此表示:
$$h_{w,b}(x)=g(w^Tx+b)$$
>$w:$ parameters
>$b:$ bias

之前我們用$\theta$表示參數，
現在改用$w取代\begin{bmatrix}\theta_1...\theta_d\end{bmatrix}^T$表示參數；
而$b是常數項，相當於\theta_0$，
所以可以發現，
$x_0(=1)$項被去掉了，
然後把$\theta_0提出為b$。

而在這裡$g(z)=1\ \ i\!f\ \ z\ge0$，
反之$g(z)=-1$

## Functional margin
對於training example $(x^{(i)},y^{(i)})$，
functional margin的定義如下:
$$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$$

>$\hat{\gamma}^{(i)}:$ functional margin

從此式子我們可以發現，
由於

$y=1\ i\!f\ (w^Tx^{(i)}+b)\ge0$，
$y=-1\ i\!f\ (w^Tx^{(i)}+b)<0$，

所以當**分類正確時$\hat{\gamma}^{(i)}>0，\textbf{反之}\hat{\gamma}^{(i)}<0$**。

另外，對於$g(z)$還有一個性質，
如果我們將$w,b$都乘上一個數字並不會改變結果，
即$g(w^Tx^{(i)}+b)=g(2w^Tx^{(i)}+2b)$，
也就是不會改變$h_{w,b}(x)$；
但是$\hat{\gamma}^{\prime(i)}=2\hat{\gamma}^{(i)}$。

由於這個性質，
**縮放$w,b$** 會更動functional margin的大小，
所以施行標準化(normalization)便是合理的操作，
>:::spoiler 標準化
>注意這裡的標準化是指線性代數裡的標準化
>https://medium.com/ai%E5%8F%8D%E6%96%97%E5%9F%8E/preprocessing-data-%E6%95%B8%E6%93%9A%E7%89%B9%E5%BE%B5%E6%A8%99%E6%BA%96%E5%8C%96%E5%92%8C%E6%AD%B8%E4%B8%80%E5%8C%96-9bd3e5a8f2fc
>:::
我們後面會再提到。

剛剛上面的functional margin是對於第$i$筆資料，
對於有n筆資料的資料集$S=\{(x^{(i),y^{(i)}})\,;\,i=1,...,n\}$，
我們定義:
$$\hat{\gamma}=\min_{i=1,...,n}\hat{\gamma}^{(i)}$$
>$\hat{\gamma}:$ 整個資料集的functional margin

## Geometric margin

**注意w垂直於決策平面**
>:::spoiler why?
>https://stackoverflow.com/questions/10177330/why-is-weight-vector-orthogonal-to-decision-plane-in-neural-networks
>:::
A點是其中一個$y=1$ (X)的training example，
它跟決策平面的距離是$\gamma^{(i)}$，
現在我們要有一種方法能找出$\gamma^{(i)}$。

B點是在決策邊界上的一點，
滿足$w^Tx+b=0$，
且B為$x^{(i)}-\gamma^{(i)}\cdot\frac{w}{||w||}$，

>::: spoiler 範數||n||
>簡單來說就是向量長度。
>
>設有一向量$x=(x_1,x_2,...,x_d)^T$，
>則定義:
>$$\Vert x\Vert_2:=\sqrt{\sum^d_{i=1}x_i^2}$$
>$\Vert x\Vert_2$稱為歐基里德範數(畢氏定理)，
>為了方便我們將其寫為$\Vert x\Vert$
>:::

>:::spoiler Why?
>雖然我們將$x_i$ (A、B)以"點"的形式化在圖上，
>但$x$其實是以向量形式存的，
>也就是原點到圖上資料點所形成之向量。
>
>$\frac{w}{\Vert w\Vert}$表示$w$的單位向量(unit-length vector)，
>也就是跟$w$方向相同，長度為1的向量。
>所以$\gamma^{(i)}\cdot\frac{w}{||w||}$是長度為$\gamma^{(i)}$，方向為$w$之方向的向量。
>
>剩下的就是向量加減法了
>:::

所以我們寫出:
$$w^T(x^{(i)}-\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})$$
現在就跟functional margin一樣，
在預測正確時$\gamma^{(i)}>0$，反之$<0$。
並且可以發現:
$$\gamma^{(i)}=\frac{\hat{\gamma}^{(i)}}{\Vert w\Vert}$$

>$\hat{\gamma}^{(i)}:$ functional margin
>$\gamma^{(i)}:$ geometric margin

geometric margin其實就是functional margin的**標準化結果**，
而且$\gamma^{(i)}$不會隨$w$改變，
這樣我們就能對$w,b$做任意調整。

最後，
我們同樣定義了對於整個dataset的geometric margin:
$$\gamma=\min_{i=1,...,n}\gamma^{(i)}$$

## Optimal margin classifier
自己讀(講義放上面了)
結論是經過縮放$\hat{\gamma}$ 後 :
$$min_{w,b}\ \ \ \ \ \frac{1}{2}\Vert w\Vert^2 $$
$$s.t.\ \ \ y^{(i)}(w^Tx^{(i)}+b)\ge1$$