Intro
- 尋找最大Margin的超平面 : $\text{fatness}(\mathbf{w}) = \min_{n=1,…,N} \text{distance}(\mathbf{x}_n, \mathbf{w})$
- 標準型式 : Hard-Margin SVM
Distance
- 先做投影 : $\text{distance}(\mathbf{x}, b, \mathbf{w}) = \frac{|\mathbf{w}^T (\mathbf{x} - \mathbf{x}’)|}{|\mathbf{w}|}$
- 化簡完之後 : $= \frac{|\mathbf{w}^T \mathbf{x} + b|}{|\mathbf{w}|}$
分離條件
- 對於所有點 $n$ 須滿足 : $y_n(\mathbf{w}^T \mathbf{x}_n + b) > 0$ (正確分類)
- 距離 : $\frac{y_n(\mathbf{w}^T \mathbf{x}_n + b)}{||\mathbf{w}||}$
因為有縮放不變，可以設條件 $y_n(\mathbf{w}^T \mathbf{x}_n + b) = 1$ ，這樣margin就變成 $\frac{1}{||\mathbf{w}||}$
- 最終的目標為最小化 $||\mathbf{w}||$
SVM with QP Solver
SVM : $$ \begin{aligned} \text{Optimal } (b, \mathbf{w}) &= ? \ \min_{b, \mathbf{w}} & \frac{1}{2} \mathbf{w}^T \mathbf{w} \ \text{subject to } & y_n (\mathbf{w}^T \mathbf{x}_n + b) \ge 1, \quad \text{for } n = 1, 2, …, N \end{aligned} $$
重寫成二次規劃 : $$ \begin{aligned} \text{Optimal } \mathbf{u} &\leftarrow \text{QP}(Q, \mathbf{p}, A, \mathbf{c}) \ \min_{\mathbf{u}} & \frac{1}{2} \mathbf{u}^T Q \mathbf{u} + \mathbf{p}^T \mathbf{u} \ \text{subject to } & \mathbf{a}_m^T \mathbf{u} \ge c_m, \quad \text{for } m = 1, 2, …, M \end{aligned} $$
二次規劃 : 解出向量 $\mathbf{u}$，使目標函數 $\frac{1}{2} \mathbf{u}^T Q \mathbf{u} + \mathbf{p}^T \mathbf{u}$ 在滿足約束 $A \mathbf{u} \ge \mathbf{c}$ 的情況下達到最小
- 變數對應 :
- 向量 $\mathbf{u}$ : $\mathbf{u} = \begin{bmatrix} b \ \mathbf{w} \end{bmatrix}$ ，維度 = $d+1$
- $Q$ 矩陣 : 左上角=0, 右上角和左下角是 $1 \times d$ 和 $d \times 1$ 的零向量, 右下角為單位矩陣
- $p$ 向量 : 零向量 (沒有 $b$ 或 $\mathbf{w}$ 的一次項)
- $A$ 矩陣和 $\mathbf{c}$ 向量 : SVM約束
- $a_i^T$ 向量 : $y_i [1, \mathbf{x}_i^T]$
- $c_i=1$
呼叫 QP Solver : $\mathbf{u}^* = \text{QP}(Q, \mathbf{p}, A, \mathbf{c})$, 取得 $\mathbf{u}^{*}$ 就是 $\begin{bmatrix} b^* \ \mathbf{w}^* \end{bmatrix}$ ，可以用來定義分類超平面