# 修改目標

從 Pocket 最初的目標：

$$
\min_{b,\mathbf{w}} \sum_{n=1}^{N}[[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{z}_{n}+b)]]
$$

我們領悟了他的精隨，得到了新的 SVM 目標：

$$
\begin{align}
\text{Objective: }&\min_{b,\mathbf{w}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}[[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{z}_{n}+b)]]\\
\text{s.t.: }&y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge1\text{ for correct n}\\
&y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge -\infty \text{ for incorrect n}\\
\end{align}
$$

>$y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge -\infty$ 代表預測錯誤，是個負數

或者可以把 subject 改一下，更精簡：

$$
\begin{align}
\text{Objective: }&\min_{b,\mathbf{w}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}[[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{z}_{n}+b)]]\\
\text{s.t.: }&y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1-\infty[[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{z}_{n}+b)]]\\
\end{align}
$$

但是跟布林式子打了這麼多次交道，非常清楚這個非線性的東西很難處理，必須做一些轉換，否則之前建立的各種 SVM 都用不了。

並且上面的 subject 其實只能要求「犯錯的數量」，而不能要求「犯錯的程度」；也就是我們無法知道犯大錯或犯小錯。

# 違規量 $\xi_{n}$

$\xi_{n}$ 是各個點「違規的量」。如果是分對的點，包含邊上，其違規量是 0；如果是分錯的點，或者是在邊界內的點，就算違規。

也就是說：

$$
\xi_{n}\ge 0
$$

所以我們有了以下新的 Objective 跟 Constraints：

$$
\begin{align}
\text{Objective: }&\min_{b,\mathbf{w},\boldsymbol{\xi}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\xi_{n}\\
\text{s.t.: }&y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1-\xi_{n}\\
&\forall\ n\ ,\xi_{n}\ge 0
\end{align}
$$

可以發現我們將 $[[y_{n}\ne sign(\mathbf{w}^{T}\mathbf{z}_{n}+b)]]$ 替換成了 $\xi_{n}$。

而突然冒出的 $y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1-\xi_{n}$，是因為當初 $y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1$ 可以確保距離最小的點，其長度公式為 $\frac{1}{\left\|\mathbf{w}\right\|}$。

但現在有些違規的點，需要幫他加上違規量：

$$
\xi_{n}+y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1
$$

把他們推回邊界以內；如此我們便又可以確保距離最小的點，其長度公式一樣為 $\frac{1}{\left\|\mathbf{w}\right\|}$。

然後最後再多加上 $C\sum_{n=1}^{N}\xi_{n}$ 就可以了。

現在的 QP 有 $\tilde{d}+1+N$ 個變數，因為多了 $\xi_{n}$；限制則變為 $2N$ 個。

# Lagrange function

回想 [dual SVM 時提到過的](https://hackmd.io/@ShawnNTU-CS/HybC95v22#Lagrange-Function)，要建立 Lagrange function，就要將限制移項後加到 Objective 裡面：

$$
\color{red}{0\ge 1-\xi_{n}-y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)}\\
\color{blue}{0\ge -\xi_{n}}\\
\mathcal{L}(b,\mathbf{w},\boldsymbol{\xi},\color{red}{\boldsymbol{\alpha}},\color{blue}{\boldsymbol{\beta}})=\min_{b,\mathbf{w},\boldsymbol{\xi}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\xi_{n}+\color{red}{\sum_{n=1}^{N}\alpha_{n}(1-\xi_{n}-y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b))}+\color{blue}{\sum_{n=1}^{N}\beta_{b}(-\xi_{n})}
$$

# Lagrange Dual

然後就是一樣的推導方式，我們可以得到我們想要的 Lagrange Dual：

$$
\max_{\alpha_{n}\ge0,\beta_{n}\ge0}\left(\min_{b,\mathbf{w},\boldsymbol{\xi}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\xi_{n}+\color{red}{\sum_{n=1}^{N}\alpha_{n}(1-\xi_{n}-y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b))}+\color{blue}{\sum_{n=1}^{N}\beta_{b}(-\xi_{n})}\right)
$$

然後一樣計算出梯度，並帶入來化簡式子。

$$
\frac{\partial\mathcal{L}}{\partial\xi_{n}}=C-\alpha_{n}-\beta_{n}=0\\
\Rightarrow C-\alpha_{n}=\beta_{n}
$$

可以發現，$\beta_{n}$ 可以用 $C-\alpha_{n}$ 替換掉；並且由於 $\beta_{n}\ge0$，所以可以知道：

$$
C\ge\alpha_{n}\ge0
$$

$$
\max_{\alpha_{n}\ge0,\beta_{n}\ge0}\left(\min_{b,\mathbf{w}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\color{red}{\sum_{n=1}^{N}\alpha_{n}(1-y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b))}\right)
$$

在替換掉了 $\beta_{n}$ 之後，就變成是跟之前 dual SVM 中 objective 一模一樣的東西，只是 $\alpha_{n}$ 多了上限。

所以一樣使用傳統藝能，可以得到：

$$
\frac{\partial\mathcal{L}}{\partial b}=0\Rightarrow \sum_{n}^{N}\alpha_{n}y_{n}=0\\
\frac{\partial\mathcal{L}}{\partial w_{i}}=0\Rightarrow \mathbf{w}=\sum_{n}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}\\
$$

所以最終在 QP 當中，只有差在 $0\le\alpha_{n}\le C$ 這部分，也就是要多補一些東西而已。

## KKT Condition

- primal feasible：
- $y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\ge 1-\xi_{n}$
- $\xi_{n}\ge0$
- dual feasible：
- $\alpha_{n} \ge 0$
- $\beta_{n} \ge 0$
- dual-inner optimal
- $\sum_{n=1}^{N}\alpha_{n}y_{n}=0$ 和 $\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}$
- $\beta_{n}=C-\alpha_{n}$
- primal-inner optimal
- $\alpha_{n}\left(1-\xi_{n}-y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\right)=0$
- $\beta_{n}(-\xi_{n})=0$
- 同樣有「Complementary Slackness」

# $b$ 的值

解出了 $\alpha_{n}$ 之後，$\beta_{n},\mathbf{w}$ 都可以輕鬆算出。

至於 $b$ 跟 $\xi_{n}$，來看看兩者的方程：

$$
\alpha_{n}\left(1-\xi_{n}-y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\right)=0\\
\Rightarrow y_{n}-y_{n}\xi_{n}-\mathbf{w}^{T}\mathbf{x}_{n}=b\\
$$

會發現想要知道 $b$，就要先知道 $\xi_{n}$，但如果只單看這個方程，會發現想要知道 $\xi_{n}$ ，就要先知道 $b$；也就是陷入了循環。

為此，我們需要考慮第二條：

$$
\beta_{n}(-\xi_{n})=0\\
\Rightarrow (C-\alpha_{n})\xi_{n}=0
$$

可以發現，只要知道 $\alpha_{n}$ 似乎就好辦事許多，於是開始分段討論：

## $\alpha_{n}>0$ / Support Vector

跟之前的定義一樣，$\alpha_{n}>0$ 的就是支撐向量，但是由於 $\xi$ 的關係，所以有兩種支撐向量：

- $C>\alpha_{n}>0$：此時可以確定 $\xi_{n}=0$，也就是說
- $y_{n}-\mathbf{w}^{T}\mathbf{x}_{n}=b$
- 這時有個特殊的名稱 **「free SVM」**
- $C=\alpha_{n}$
- 只能確定 $\xi_{n}=1-y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)$
- 所以有可能 $\xi_{n}=0$，但是是極少數情況。
- 這時有個特殊的名稱 **「bounded SVM」**

所以 $b$ 就變成是只要從 free SVM 中隨便選一個就可以算出來。

但是極少數的情況會沒有 free SVM，這時候 $b$ 會由一堆東西限制住，只要滿足這些限制和 KKT 條件的 $b$ 就會是可行的解。

:::danger
待補
:::

## $\alpha_{n}=0$

這時候可以確定 $\xi_{n}=0$，也就是說：

$$
y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\ge 1
$$

也就是那些分對的點；當然極少情況會是在邊界的點。

# Model Selection

算出了 $\alpha$，找到了 $b$，然後搭配之前的 Kernel function，就成了實際中常用的 SVM，通常 SVM 沒有特別說明的話大多是 Soft-margin，然後再看是搭配哪種 Kernel function。

如果是 Gaussian Kernel，那麼一個 model 需要調的參數就是 $(C,\gamma)$，所以一樣會有選擇問題；所以一樣使用 Validation 搭配 grid value 來進行選擇。

:::info
grid value 就像是以 [-1,1]X[-1,1] 的四種組合以網格的方式列出。
:::

# Leave-One-Out

Leave-One-Out 在使用了 dual SVM 方法底下，可以得到有趣的結論：

$$
E_{loocv}\le\frac{\#SV}{N}
$$

因為如果我們對 N 個點做 SVM 得到 $\alpha_{n}$：

- 如果要對第 n 個點做 Validation，所對應的 $\alpha_{n}=0$
- 代表他是分對的點，因此就算把該點扣除去做 SVM，得到的 $\alpha$ 跟原本一樣
- 如果第 n 個點所對應的 $\alpha_{n} \ne 0$
- 代表該點是 SV，如果扣除他的話可能會得到不一樣的結果
- 也就是說 $g^{-}$ 跟 $g$ 在第 n 個點上要嘛一樣要嘛不一樣

> [可以回顧上面](https://hackmd.io/oJS56aBkQZ-fR1dCWRK6Eg#alpha_ngt0--Support-Vector)

所以之前 Validation 在推導 $\underset{\mathcal{D}}{\mathcal{E}} E_{loocv}(g^{-}) \approx \overline{E_{out}(g^{-})}$ 的時候：

- 對於非 SV 的點：
- $e_{non-SV}=err(g^{-},non-SV)=err(g,non-SV)=0\\$
- 對於 SV 的點：
- $e_{SV}= 1\ or\ 0$

所以如果 $g^{-}$ 跟 $g$ 在 SV 的點上預測的都不一樣：

$$
E_{loocv}=\frac{\# SV}{N}
$$

這就是為甚麼 Support Vector 的數量會成為 $E_{loocv}$ 的一個上界的原因。

而 #SV 的好處就是，一旦得到 $\alpha$ 後就可以直接知道，所以可以在第一時間作為「安全檢查」，把危險的模型先去除掉；接著再用 Cross Validation 找出最適合的模型。