{%hackmd Hyaw8Gm6n %}

# 更胖的超平面

- PLA 是從可以用的超平面中隨機挑選
- 未來有可能再次拿到跟原資料相同的點，但有可能會受 Noise 影響
- 如果有些資料離超平面很接近，那他就很有可能會發生 Flipped。

這時候會需要一個「比較胖」的超平面，在所有可以用的超平面中，離最近的點的距離是最大。

胖平面比較可以抵抗上面所述的問題，比較抗干擾、Robust、強壯。

# 點到超平面的距離

令 $\mathbf{x}^{'}$ 是平面上的點，$\mathbf{x}$ 是一個在平面外的資料點，那麼點到超平面的距離就是 $\mathbf{x}-\mathbf{x}^{'}$ 向量在超平面的單位法向量 $\mathbf{w}$ 的投影：

$$
\left|\frac{\mathbf{w}^{T}}{\left\|\mathbf{w}\right\|}\left(\mathbf{x}-\mathbf{x}^{'}\right)\right|=\frac{1}{\left\|\mathbf{w}\right\|}\left|\mathbf{w}^{T}\mathbf{x}+b\right|
$$
>內積得到的是投影長度

推導時要記住，超平面上的點滿足：

$$
\mathbf{w}^{T}\mathbf{x}+b=0
$$

而此處我們有一個強制的要求，就是超平面可以完美正確的區分出每個點，也就是這些資料是線性可分的，因此可以知道：

$$
y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right) >0
$$

所以我們可以把惱人的絕對值去掉，變成：

$$
\frac{1}{\left\|\mathbf{w}\right\|}y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)
$$

# 問題的轉換

有了距離公式，那我們所要的就是：

- 既可以分出全部的點
- 並且離平面最近的點的距離可以最大

的 $\mathbf{w}$ 跟 $b$。

但是這樣我們的要求中有 min 又有 max：

$$
\max_{b,\mathbf{w}}\ \min_{n=1,...,N}\frac{1}{\left\|\mathbf{w}\right\|}y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)
$$

根據過往的經驗，這種東西我們很難去處理。

於是我們靈光一想，等比例放大縮小 $\mathbf{w}^{T}\mathbf{x}_{n}+b=c$ 對我們要的 $\mathbf{w},b$ 不會有影響，所以我們改要求

$$
\min_{n=1,...,N}y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)=1
$$

因為這樣求最大值會變的很簡單：

$$
\max_{b,\mathbf{w}}\frac{1}{\left\|\mathbf{w}\right\|}
$$

但是 min 依舊是不知道要怎麼辦。

這時候邏輯大師上線，我們想想有甚麼條件可以導致最小值是 1，答案就是全部資料的值要大於等於 1：

$$
\forall n,y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\ge 1
$$

因為在這個前提下，最小值必定等於 1：

- 如果最小值大於 1，那麼依舊可以等比例給他縮小到 1
- 也就是說可以找到比最小值更小的值，跟最小值大於 1 矛盾。

:::warning
所以如果有某個條件很難達成，不如來想想有哪些前提必定會得到該條件，而有可能該前提蠻好處理的。
:::

跟[處裡 Logistic Regression 的時候](https://hackmd.io/@ShawnNTU-CS/Syyx9mE33#Cross-Entropy-Error)一樣，為了讓 max 的部分變成熟悉的 min 形式，所以換成倒數；並且避免了麻煩的根號，使用了平方，最後補個常數 $\frac{1}{2}$

因此最終我們的目標就變成：

$$
\begin{align}
\text{objective: }&\min_{b,\mathbf{w}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}\\
\text{subject to: }& y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\ge 1\\
&for\ n= 1,...N\\
\end{align}
$$

:::warning
Objective 跟 Subject to 這樣的寫法常見於最佳化領域中
:::

# 支持向量候選人

其實仔細去想可以發現，在資料當中只有某些點去定位了超平面的位置，也就是距離為最小值的那些點，其他的點並沒有貢獻。

那些點就很像支撐著超平面一樣，所以叫做支持向量候選人 Support Vector Candidates。

那到底這些候選人中誰才是真的 Support Vector，請見 [Dual SVM](https://hackmd.io/@ShawnNTU-CS/HybC95v22#Support-Vectors)。

# Quadratic Programming

在最後我們的要求是：

$$
\begin{align}
\text{objective: }&\min_{b,\mathbf{w}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}\\
\text{subject to: }& y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\ge 1\\
&for\ n= 1,...N\\
\end{align}
$$

這個東西在最佳化領域中其實已經存在解法，因為他的兩個條件：

- (convex) quadratic objective function of $(b,\mathbf{w})$
- linear constraints of $(b,\mathbf{w})$

滿足 Quadratic Programming 的要求，所以我們只要按照下面的形式，把對應的參數丟到寫好的工具包，就可以求出解了。

$$
optimal\ \mathbf{u}=QP(\mathbf{\color{red}{Q},\color{orange}{p},\color{blue}{A},\color{green}{c}})\\
\begin{align}
\text{objective: }&\min_{\mathbf{u}} \frac{1}{2}\mathbf{u}^{T}\color{red}{\mathbf{Q}}\mathbf{u}+\color{orange}{\mathbf{p}^{T}}\mathbf{u}\\
\text{subject to: }&\color{blue}{\mathbf{a}_{m}^{T}}\mathbf{u}\le \color{green}{\mathbf{c}_{m}}\\
&for\ m= 1,...M\\
\end{align}
$$

對應之後可以知道：

$$
\mathbf{u}=
\begin{bmatrix}
b \\
\mathbf{w}
\end{bmatrix};
\color{red}{
\mathbf{Q}=
\begin{bmatrix}
0 & \mathbf{0}_{d}^{T}\\
\mathbf{0}_{d}^{T} & \mathbf{I}_{d}
\end{bmatrix}};
\color{orange}{
\mathbf{p} = \mathbf{0}_{d+1}}\\
\color{blue}{\mathbf{a}^{T}_{n}=y_{n}\left[1,\mathbf{x}_{n}^{T}\right]},\ \color{green}{c_{n} = 1}, M=N
$$

# Linear SVM 跟 L2 Regularizer

原本：

- L2 要 Minimize 的是：
- $E_{in}$
- L2 的限制是：
- $\mathbf{w}^{T}\mathbf{w}\le C$

而 Linear SVM 可以發現：

- Linear SVM 要 Minimize 的是：
- $\mathbf{w}^{T}\mathbf{w}$
- Linear SVM 的限制是
- $E_{in}=0$ 跟 $y_{n}\left(\mathbf{w}^{T}\mathbf{x}_{n}+b\right)\ge 1\ for\ n= 1,...N$

所以可以說 Linear SVM 是 ‘weight-decay regularization’ within $E_{in} = 0$

# Restricts Dichotomies

由於 Linear SVM 要找的是比較胖的超平面，Large Margin Hyperplane，所以相較於原本普通的超平面，Dichotomies 會變少。

舉例來說二維的普通線和胖胖線，有三個點，普通線可以有 8 種 Dichotomies，但是胖胖線會因為太胖，導致某些 Dichotomies 並不存在。

而這些減少的 Dichotomies，根據 VC 理論，相信可以達到更好的 Generalization，也就是 $E_{in}$ 跟 $E_{out}$ 更接近。

## $d_{vc}(\mathcal{A}_{\rho})$

以前都是在討論一個 $\mathcal{H}$ 的 $d_{vc}$ 是多少，會表示為：

$$
d_{vc}(\mathcal{H})
$$

但是由於 Linear SVM 會因為 $\mathcal{A}_{\rho}$ 的不同，選擇不同胖度($\rho$)的 Large Margin Hyperplane，所以會改成討論因演算法不同而產生的 $d_{vc}$：

$$
d_{vc}(\mathcal{A}_{\rho})
$$

例如在二維平面上，有一些點，但是受限於單位圓上：

$$
\mathcal{X}=\text{unit circle in }\mathbb{R}^{2}
$$

假如我們要求 $\rho > \frac{\sqrt{3}}{2}$，或者說平面兩面的胖度是$\sqrt{3}$，並且圓上面只有三個點：

- 如果三個點構成之三角形為正三角形，則邊長為 $\sqrt{3}$
- 一旦 $\rho > \frac{\sqrt{3}}{2}$，稍微移動點的位置後，一定至少有一個邊的長度小於 $\sqrt{3}$

也就是說，$\mathcal{A}_{\frac{\sqrt{3}}{2}}$ 無法擊敗全部 3 個點，$d_{vc}<3$。

普遍來說，當資料點被限制在在半徑 $R$ 的超維球內時：

$$
d_{vc}(\mathcal{A}_{\rho})\le min(\frac{R^2}{\rho ^{2}},d)+1\le \underbrace{d+1}_{d_{vc}\ perceptron}
$$

# Feature Transform

Linear SVM 當然也可以對資料做 Feature Transform，並且 Large Margin Hyperplane「緩解」原本 $d_{vc}$ 太高的問題。

至於為甚麼會說是緩解，請看下一篇 Dual SVM。

---

:::info
看來得去修最佳化相關課程了
:::