SVM 支持向量机
写这篇博客时看到知乎一篇 16 年的文章，作者指出传统 SVM 在对一些稀奇古怪的样本进行分类时有比较好的效果，但是评论区纷纷表示：多来几层神经网络就搞定了。由于我知识储备有限，在此就简单讲讲我的理解。
SVM基本形式求解
给定一个二分类问题的训练样本集：
$D=(x_1,y_1),(x_2,y_2),…,(x_m,y_m),y_i∈−1,+1$1，
我们的目标是找到一条分界线/超平面2来将两类区分开，如下图：
- $w=(w_1,w_2,…,w_d)$ 为法向量，决定了超平面的方向
- $b$ 为位移项，决定了超平面与原点的距离。
如果一个超平面能够将训练样本正确分类，则我们希望这个超平面具有的性质是，对于 $(x_i,y_i)∈D$，有： $$ f(x) = \begin{cases} w^T x + b \geq 0, & y_i = +1; \ w^T x + b \leq 0, & y_i = -1. \end{cases} $$
换言之，在进行分类的时候，遇到一个新的数据点 $x$，将 $x$ 代入 $f(x)$ 中：
- 如果 $f(x)$ 小于 $0$ ，则将 $x$ 的类别赋为 $-1$
- 如果 $f(x)$ 大于 $0$ ，则将 $x$ 的类别赋为 $1$
接下来的问题是，如何确定这个超平面呢? SVM 算法的标准是使直线离两边的点间隔最大。
间距计算
点到超平面的距离公式3为：
$$\text{distance} = \frac{|w^T x + b|}{||w||}$$
注意到这个距离并未区分样本类别，于是令支持向量满足：
$y_i(w^T x_i + b) = λ = 1$4
此时得到间距：$\gamma =\frac{2}{||w||}$
最优化问题
$$\begin{aligned} \max & \frac{2}{||w||} \ ,\quad\text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i = 1,\ldots,n \end{aligned}$$
等价地，可以转化为：
$\begin{aligned} \min & \frac{1}{2}||w||^2 \ \quad\text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i = 1,\ldots,n \end{aligned}$
这是一个凸二次规划问题，可以使用拉格朗日对偶理论求解5。
求得模型
具体过程此处不题，得：$f(x)=w^{T}x+b= \sum_{i=1}^m\alpha_i y_i x_i^{T}x+b$