# Infinite $\widetilde{d}$

回顧原本 QP 的內容：

$$
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{z}_{n}^{T}\right]},\ \color{green}{c_{n} = 1}, M=N
$$

但如果經過了特徵轉換：

$$
\phi(\mathbf{x}_{n})=\mathbf{z}_{n}\\
\Large{
\color{red}{\mathbf{x}_{n} \in \mathbb{R}^{d}},\color{purple}{\mathbf{z}_{n} \in \mathbb{R}^{\tilde{d}}}}\\
$$

$\color{red}{Q矩陣}$ 就必須面臨 $\widetilde{d}$ 的問題，也就是 $\widetilde{d}$ 可能會非常的多，甚至無限多個。

所以目前的 convex QP：

- 有 $\widetilde{d}+1$ 種變數
- 有 $N$ 個條件 constraints

所以我們希望有一種方法，可以去除掉對 $\widetilde{d}$ 的依賴性，將原本的 QP 轉換成另一種等價的 convex QP：

- 有 $N$ 種變數
- 有 $N+1$ 個條件 constraints

# Lagrange Multipliers

在 Logistic Regression 的時候，那時候是一個限制，用了一個 Lagrange Multiplier：

$$
\min_{\mathbf{w}}E_{aug}(\mathbf{w})=E_{in}(\mathbf{w})+\frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}
$$

經過了這項操作，對 $E_{aug}$ 來說原本 Logistic Regression 的條件就好像被隱藏了起來。

# Lagrange Function

那我們也來試試看，把原本 SVM 問題的條件給「藏起來」：

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

要把這 N 個條件藏起來，我們建立 Lagrange Function：

$$
\mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha})=
\underbrace{\frac{1}{2}\mathbf{w}^{T}\mathbf{w}}_{objective}+\sum_{n=1}^{N}\underbrace{\alpha_{n}\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)}_{constraint}
$$

我們就可以把原本的 SVM 轉化成看似沒有條件的問題：

$$
\min_{b,\mathbf{w}}\left(\max_{all\ \alpha\ge 0} \mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha})\right)=\min_{b,\mathbf{w}}\left(\infty \text{ if violate},\frac{1}{2}\mathbf{w}^{T}\mathbf{w} \text{ if feasible}\right)
$$

在上面的式子中，挑選 $b,\mathbf{w}$ 的時候就彷彿不受那 N 個限制一般

原因是因為我們透過 $max$，先將符合條件的人選篩選好了：

- 如果 「violate」：$\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)>0$
- 那麼 $max$ 就會一直追求最大的 $\alpha$，直到變成無限大
- 無限大就無法挑。
- 如果 「feasible」：$\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)\le 0$
- 由於已限制全部的 $\alpha\ge 0$，要讓 $\alpha\times\text{some negatives}$ 是最小值，那麼只能讓 $\alpha=0$
- 除非該點原本 $\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)= 0$

所以 Feasible 就會剩下原本的目標 $\frac{1}{2}\mathbf{w}^{T}\mathbf{w}$，max 就不見了；接著只要挑選最小的 $\frac{1}{2}\mathbf{w}^{T}\mathbf{w}$ 就好。

這樣子，我們就巧妙的將原本的限制給「藏在 $max$ 裡面」。

:::warning
上面可以發現，constraint 其實就是把原本 subject to 的內容，改成 $0\ge (...)$，$(...)$ 就是我們所要的 constraint。
這個方式再之後也會再次用到。
:::

# Lagrange Dual Problem

由於裡面是 $max$，所以對於任意的 $\alpha^{'}$ 來說，存在著大於等於的關係：

$$
\min_{b,\mathbf{w}}\left(\max_{all\ \alpha\ge 0} \mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha})\right) \ge \min_{b,\mathbf{w}}\mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha^{'}})
$$

而 $\alpha^{'}$ 的 BEST，也是任意的其中之一，所以我們可以給右邊取 $max$；當然 $\alpha^{'} \ge 0$：

$$
\min_{b,\mathbf{w}}\left(\max_{all\ \alpha\ge 0} \mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha})\right) \ge \underbrace{\max_{all\ \alpha^{'} \ge 0} \min_{b,\mathbf{w}}\mathcal{L}(b,\mathbf{w},\boldsymbol{\alpha^{'}})}_{Lagrange\ Dual\ Problem}
$$

而 $\alpha^{'}$ 只是個記號，可以改為 $\alpha$，這樣一來上面的動作就很像是把 $min$ 跟 $max$ 做了交換；而右手邊的就是所謂的「Lagrange Dual Problem」，原本的問題是「Primal Problem」

## weak duality

在最佳化領域， $\ge$ 這樣的關係叫做 weak duality。

## strong duality

有 weak 就有 strong，也就是 $=$。

但是，對「QP 問題」來說，要是強對偶，最佳化領域的專家證明了必須滿足：

- convex primal
- 原本的問題是 convex 的
- SVM 確實是 convex
- feasible primal
- $\phi$ 轉換後如果是 Separable，那就是有解的
- 也就是 $\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)\le 0$ 的部分
- [這個我們有給予保證](https://hackmd.io/iISbapICSbqs9aWnDVQpKQ?both#%E9%BB%9E%E5%88%B0%E8%B6%85%E5%B9%B3%E9%9D%A2%E7%9A%84%E8%B7%9D%E9%9B%A2)
- linear constraints
- 確實我們 QP 問題就是線性的 Constraints

這樣一來等號就會成立，換句話說，「primal-dual optimal」，對兩個問題都是最佳的解是存在的。

# Simplifications

有了右邊求 $min$ 的部分，由於他「可以任意挑選、沒有限制」，所以就可以使用梯度來進行化簡。

## $\frac{\partial \mathcal{L}(b,\mathbf{w},\mathbf{\alpha})}{\partial b}=0$

$$
\frac{\partial \mathcal{L}(b,\mathbf{w},\mathbf{\alpha})}{\partial b}=-\sum_{n=1}^{N}\alpha_{n}y_{n}=0
$$

這裡有個技巧，對原本的 $min$ 去多加 $\sum_{n=1}^{N}\alpha_{n}y_{n}=0$ 的 Constraint 並不會影響求最佳解，所以可以進行替換，並且讓 $min$ 少一個變數：

$$
\max_{all\ \alpha\ge 0}\left(\min_{b,\mathbf{w}}\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\sum_{n=1}^{N}\alpha_{n}\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)\right)\\
\Rightarrow \max_{all\ \alpha\ge 0,\sum_{n=1}^{N}\alpha_{n}y_{n}=0}\left(\min_{\mathbf{w}}\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\sum_{n=1}^{N}\alpha_{n}\left(1-y_{n}\mathbf{w}^{T}\mathbf{z}_{n}\right)\right)\\
$$

## $\frac{\partial \mathcal{L}(b,\mathbf{w},\mathbf{\alpha})}{\partial w_{i}}=0$

$$
\frac{\partial \mathcal{L}(b,\mathbf{w},\mathbf{\alpha})}{\partial w_{i}}=w_{i}-\sum_{n=1}^{N}\alpha_{n}y_{n}z_{n,i}=0\\
w_{i}=\sum_{n=1}^{N}\alpha_{n}y_{n}z_{n,i}
$$

所以一樣，再給他加上新限制：$\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}$

$$
\max_{all\ \alpha\ge 0,\sum_{n=1}^{N}\alpha_{n}y_{n}=0,\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}}\left(\min_{\mathbf{w}}-\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+\sum_{n=1}^{N}\alpha_{n}\right)\\
\Rightarrow
\max_{all\ \alpha\ge 0,\sum_{n=1}^{N}\alpha_{n}y_{n}=0,\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}}-\frac{1}{2}\left\|\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}\right\|^{2}+\sum_{n=1}^{N}\alpha_{n}
$$

可以發現 $min$ 就這樣不見了。

# Karush-Kuhn-Tucker (KKT) conditions

經過上面的一番化簡，我們來整理一下，如果 $(b,\mathbf{w},\alpha)$ 是最佳解，則可推得：

- primal feasible：
- $y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b)\ge 1$
- 也就是上面提到過，滿足強對偶的條件之一，必須要是線性可分
- dual feasible：
- $\alpha_{n} \ge 0$
- 這是我們給予 Lagrange Multipliers 的限制
- 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}$
- 這是根據 dual 的式子中，梯度等於 0 而得到的限制
- primal-inner optimal
- $\alpha_{n}\left(1-y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\right)=0$
- 這是先前根據 primal 的式子中，可行解法的條件；也就是去除了無限大。
- 而且可以有趣的發現，這兩者必須至少其中一人等於 0
- 所以有可能兩個都等於 0
- **這件事情又叫做「Complementary Slackness」**

而如果有某個 $(b,\mathbf{w},\boldsymbol{\alpha})$ 滿足這四個條件，那麼他就會是最佳解；也就是說最佳解跟四個條件互為充分必要：

$$
\text{Optimal } \Leftrightarrow \text{ Four conditions}
$$

---

# Dual Formulation of SVM

所以我們就有了 Dual SVM 的公式：

$$
\max_{all\ \alpha\ge 0,\sum_{n=1}^{N}\alpha_{n}y_{n}=0,\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}}-\frac{1}{2}\left\|\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}\right\|^{2}+\sum_{n=1}^{N}\alpha_{n}
$$

跟Logistic Regression 的時候一樣，我們喜歡的是 $min$ 跟 $\sum$，所以我們給他修改為：

$$
\min_{\alpha}\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{M}\alpha_{n}\alpha_{m}y_{n}y_{m}\mathbf{z}_{n}^{T}\mathbf{z}_{m}-\sum_{n=1}^{N}\alpha_{n}\\
subject\ to\ \ \sum_{n=1}^{N}\alpha_{n}y_{n}=0,\alpha_{n}\ge 0
$$

也就是整體加了負號，並把長度寫成 $\sum\sum$ 的形式；並且為了專心解 $\boldsymbol{\alpha}$ ，我們把那些限制當作隱藏的限制，式子表達得更簡潔。

上面的式子就是 standard hard-margin SVM dual。

## Solve with QP

這個式子就是我們成功轉換出的等價 Convex QP 問題，可以證明他的 convex 性質。
既然是 QP 問題，那就一樣丟給 QP 去解就行了，所以我們來列出 QP 所需的各個部分：

$$
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}=
\boldsymbol{\alpha};\
\color{red}{\mathbf{q_{n,m}}=y_{n}y_{m}\mathbf{z}_{n}\mathbf{z}_{m}};\
\color{orange}{
\mathbf{p} = \mathbf{-1}_{N}}\\
\color{blue}{\mathbf{a}^{T}_{\ge}=\mathbf{y}},\color{blue}{\mathbf{a}^{T}_{\le}=-\mathbf{y}},\color{blue}{\mathbf{a}^{T}_{n}=\mathbf{I}_{N}}\\
\color{green}{c_{\ge}= 0} ,\color{green}{c_{\le}= 0},\color{green}{c_{n}= 0}
$$

其中線性 constraint 中 $\le$ 跟 $\ge$ 的部分，是為了湊出 $\sum_{n=1}^{N}\alpha_{n}y_{n}=0$，但是有些寫得很好的 QP 工具包，會直接提供 $=$ 的 QP 工具，只要詳細閱讀使用手冊就好。

:::warning
切記要詳細閱讀使用手冊，因為不等式方向可能會不一樣...
:::

## Special QP Solver

其實跟 Linear SVM 一樣，$\mathbf{Q}$ 矩陣式需要被特別關照的對象，因為在這裡，他會是一個 $N\times N$ 矩陣，如果 $N$ 很大，那會不得了。

所以實際使用的時候，最好是使用專屬的「特殊 QP」來計算 Dual SVM 的解。這種特殊 QP 可能是：

- 不會直接把 Q 矩陣存起來，要用的時候才會把某一項算出來
- 減少記憶體的消耗
- 或是使用特殊的限制 special constraints

# Optimal $(b,\mathbf{w})$

有了 $\boldsymbol{\alpha}$ 之後，根據條件之一：

$$
\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}
$$

可以輕易的算出 $\mathbf{w}$。

至於 $b$，我們可以根據另一個條件：

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

我們有提到 Complementary Slackness，所以我們可以隨意找一個不為 0 的 $\alpha_{n}$，去計算出 $b$：

$$
1=y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\\
y_{n}=\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)\\
b=y_{n}-\mathbf{w}^{T}\mathbf{z}_{n}
$$

理論上任意一個 $\alpha$ 得到的 $b$ 應該都是一樣的，雖然可能會因為電腦的小數點位數問題而稍稍不同。

# Support Vectors

上面在求 $b$ 的時候，可以發現一件事情：

$$
y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)=1
$$

這不正告訴我們他是邊界上的點；並且這些點，**才是真正的 Support Vectors**，原因是因為他的 $\alpha_{n} > 0$，這些點才會告訴我們兩個重要的訊息：

$$
\mathbf{w}=\sum_{n=1}^{N}\alpha_{n}y_{n}\mathbf{z}_{n}=\sum_{SV}\alpha_{n}y_{n}\mathbf{z}_{n}
$$

$$
b=y_{n}-\mathbf{w}^{T}\mathbf{z}_{n} \text{ with any SV}(\mathbf{z}_{n},y_{n})
$$

也就是說，SVM 透過 dual optimal solution 找到 support vector，而這些 support vector 讓我們學到了最胖的超平面。

---

# Represented by data

在權重的公式中，其實可以發現老熟人 PLA 的身影：

$$
\mathbf{w}_{SVM}=\sum_{n=1}^{N}\alpha_{n}(y_{n}\mathbf{z}_{n}),\ \mathbf{w}_{PLA}=\sum_{n=1}^{N}\beta_{n}(y_{n}\mathbf{z}_{n})
$$

$\alpha_{n}$ 是從 dual solution 得來的，而 $\beta_{n}$ 是從 mistake corrections 得來得的。

這件事情，如果讓 GD/SGD-based LogReg/LinReg 也從 $\mathbf{w}=\mathbf{0}$ 出發，一樣可以得出類似的式子。

$\mathbf{w}$ 是 $\mathbf{z}_{n}$ 的線性組合這件事情，就是代表我們的權重可以被資料所表示。

而我們的 SVM 則更是只從那些 Support Vector 中所表達，因為 SVM 相信重要的是那些負責支撐的點；PLA 則是覺得重要的是那些犯錯的點。

# Summary

- Primal Hard-Margin SVM
- $\widetilde{d}+1$ 個變數，$N$ 個限制
- 適用於 $\widetilde{d}$ 較小的時候
- 物理意義：找出出特別縮放過的 $(b,\mathbf{w})$
- Dual Hard-Margin SVM
- $N$ 個變數，$N+1$ 個限制
- 適用於 $N$ 較小的時候
- 物理意義：找出 $\alpha$，並從中找到支撐向量重建出 $(b,\mathbf{w})$

兩者都可以找到最佳的胖胖超平面。

$$
g_{SVM}(\mathbf{x}) = sign(\mathbf{w}^{T}\phi(\mathbf{x})+b)
$$

# Without dependency on $\tilde{d}$

沒錯，還記得一開始我們的要求嗎，消除對 $\tilde{d}$ 的依賴。

但是從 $Q$ 矩陣中依舊可以發現，他還在。

那要怎麼辦？請見[下一章](https://hackmd.io/@ShawnNTU-CS/r1kk9fFn2)