支持向量机总结

支持向量机的优化目标为在约束下，最大化geometric margin：$\gamma$

$$\begin{aligned} \max _{\gamma, w, b} &\quad \gamma \\ \text { s.t. } &\quad y^{(i)}\left(w^{T} x^{(i)}+b\right) \geq \gamma, \quad i=1, \ldots, m \\ &\quad \|w\|=1 \end{aligned}$$

其中约束$\|w\|=1$是non-convex的，我们稍作改进

$$\begin{aligned} \max _{\gamma, w, b} &\quad \frac{\hat{\gamma}}{\|w\|} \\ \text { s.t. } &\quad y^{(i)}\left(w^{T} x^{(i)}+b\right) \geq \hat{\gamma},\quad i=1, \ldots, m \end{aligned} \\$$

（functional margin和geometric margin的关系是：$\gamma = \frac{\hat{\gamma}}{\|w\|}$）
虽然我们摆脱了非凸的约束$\|w\|=1$，但是objective function: $\frac{\hat{\gamma}}{\|w\|}$依然是非凸的。我们没有任何现成的软件能求解这种优化问题。

为了解决以上问题，我们把functional margin固定为1: $\hat{\gamma}=1$，经过改进，现在 $\frac{1}{2}\|w\|^{2}$ 是一个凸二次函数(convex quadratic objective)，并且只有线性约束（linear constraints）。能够用commercial quadratic programming (QP software)求解。

$$\begin{aligned} \min _{\gamma, w, b} &\quad \frac{1}{2}\|w\|^{2} \\ \text { s.t. } &\quad y^{(i)}\left(w^{T} x^{(i)}+b\right) \geq 1, \quad i=1, \ldots, m \end{aligned}$$

---

接下来我们讨论拉格朗日对偶，这将引导我们导出optimization problem的对偶形式

（1）这将允许我们使用Kernel，可以在非常高维的空间有效工作。

（2）对偶形式还允许我们推导出一种有效的算法来解决上述优化问题，这种算法通常比通用QP软件做得好得多。