SVM

1995 年, 基于统计学习的理论基础发展出了一种新的通用的学习方法——支持向量机 (SVM). 可以说 SVM 是统计学习理论在算法领域应用的集中体现. SVM 的提出, 一举解决了第二代神经网络的结构选择和局部最小值 (过拟合与欠拟合) 等问题, 使第二代神经网络的发展进入了又一个低潮期. 以统计学习方法为基础的 SVM 被应用于机器学习的各个领域, 成为最通用的万能分类器.

线性支持向量机

有 $\mathcal{X} = \{x_1,x_2,\cdots,x_m: x_i \in ℝ^n\}$ , $\mathcal{Y} = \{y_1,y_2,\cdots,y_m\}$ , 数据空间 $V = \mathcal{X \times Y}$ . 以下 $i \in \{1, 2, \cdots, m \}$ , 分离超平面为 $w^T x + b = 0$

SVM 的目的是最大化间隔 (margin), 对于线性可分的数据集, 模型假设为
$\begin{cases} \displaystyle\min_{w} & ||w||^2/2 \\ \operatorname{s.t.} & {y_i(w^T x_i+b)} \geq 1 \end{cases}$

考虑到存在线性不可分的数据集, 引入了变量 $\xi_i \geq 0$ , 且 $\frac{\xi_i}{||w||}$ 表示点 $x_i$ 到离它最近的边界的距离, 模型便改写为
$\begin{cases} \displaystyle{\min_{w,C}} & ||w||^2/2 + C \sum_i \xi_i \\ \operatorname{s.t.} & {y_i(w^T x_i + b)} \geq 1 - \xi_i \end{cases} ⇔ \displaystyle{\min_{w, C}} \; ||w||^2/2 + C \sum_i \max(0, 1 - y_i(w^T x_i + b))$