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 :

• 重寫成二次規劃 :

二次規劃 : 解出向量 $\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}$ ，可以用來定義分類超平面