此文是学习林轩田老师的机器学习技法第一课——Linear Support Vector Machine——的课堂笔记，有关 SVM 公式推导。
参考
（单层）感知器
感知器 (Perceptron) 利用超平面
$$\mathbf{w} \cdot \mathbf{x} = b $$
进行二元分类。其中，$\mathbf{x} = (x_1, x_2, …, x_n)$，$\mathbf{w} = (w_1, w_2, …, w_n)$。
一个数据 $(\mathbf{x},y)$ 中，$\mathbf{x}$ 作为输入，一个特征向量，可代表一个实体，而输出 $y \in {-1, 1}$ 则标记该实体的类别。Perceptron 希望找到一个超平面，即确定参数 $\mathbf{w}, b$， 能对一组数据 ${(\mathbf{x_1}, y_1), (\mathbf{x_2}, y_2),…,(\mathbf{x_n}, y_n),}$ 进行分类，使得对每组 $(\mathbf{x}, y)$ 都有：当 $y > 0$ 时，$\mathbf{w} \cdot \mathbf{x} > b$, 否则，$\mathbf{w} \cdot \mathbf{x} < b$。
例子，考虑输入为二维向量，每个数据表现为一个点，而超平面视作一条直线，Perceptron 所做的是，对多个数据点，找到一条直线将有不同标记（-1或1）的点分开。
公式推导
SVM 在 Perceptron 上更进一步，不仅要求能够找到一个超平面，而且要求这个超平面能能够尽量容忍误差。就 Perceptron 一节所举例子，SVM 要求该直线尽可能远离数据点，使得如果数据点因为误差而偏移，该直线也可能正确分类。
这可以理解成要求向量到超平面的距离尽可能大。在 超平面 的 点与超平面距离与 SVM 一节中已经说明距离可以表示为
$$
d = \left| \frac{\mathbf{w \cdot x}}{\mathbf{|w|}} - \frac{b}{\mathbf{|w|}} \right| = \frac {1} {|\mathbf{w}|} |\mathbf{w \cdot x} - b|
$$
这时，目标可以转换成求使“最小的 d” “最大” 的 $\mathbf{w}, b$，“最小的d”指所有向量与某组 $\mathbf{w}, b$ 所确定的超平面的距离的最小值，“最大” 则指所有 $\mathbf{w}, b$ 组各自对应的 “最小的 d ” 中最大的。翻译成符号：
$$
\max_{b, \mathbf{w}} margin(b, \mathbf{w}) \\
subject\ to \ every\ y_n(\mathbf{w^T xn} - b) > 0 \\
margin(b, \mathbf{w}) = \min{n=1,..,N} \frac {1}{|\mathbf{w}|} |\mathbf{w^T x_n} - b|
$$
其中，margin 可理解成距离，subject to 表示限制。即要求在可分类的情况下，求解出每组 $(b, \mathbf{w})$ 最小的距离，再选取其中最大的。注：$\min$ 内部，$n$ 作为变量，而 $\max$ 内部， $\mathbf{w}, b$ 作为变量。
课程中将其转换为二次规划（Quadratic programming）问题求解。
去绝对值，$|\mathbf{w^T x_n} - b|$ 转换成 $y_n(\mathbf{w^T x_n} - b)$。
令 $y_n(\mathbf{w^T x_n} - b)=1$（可以等于任一大于0常数），考虑到
$\mathbf{w}, b$ 作为求解变量可以乘以一个常数 k 进行放缩同时保持超平面不变，而 $|\mathbf{w}|$ 会抵消 k 带来的影响并保持 margin 不变，所以这步变换与原式等价。这使得
$$margin = \min_{n=1,..,N} \frac {1}{|\mathbf{w}|} $$
而且，这可以去除限制 $y_n(\mathbf{w^T xn} - b) > 0$，变换为：
$$
\max{b, \mathbf{w}} \frac {1}{|\mathbf{w}|} \\
subject\ to \ [\min_{n=1,..,N} y_n(\mathbf{w^T x_n} - b)]=1
$$
令 $y_n(\mathbf{w^T x_n} - b) \ge 1$，要求对于所有的 $n$ 都成立（上步仅要求最小值处成立）。这是合乎情理的，因为对于被放缩的某组 $\mathbf{w}, b$，距离最小值为1，则该组所有值都应不小于1。好处是限制条件不必做最小化操作。课程中也给出证明，说明此步与原式等价，在此不赘述。
求最大值变为求最小值，去掉倒数与绝对值。最终变换成一个所谓简单的二次规划问题为
$$
\min_{b, \mathbf{w}} \mathbf{w^T w} \\
subject\ to \ y_n(\mathbf{w^T x_n} - b) \ge 1
$$
支持向量
所谓支持向量，即距离最佳超平面最近的向量。它们“支持”了最佳超平面，而丢失其他向量对最佳超平面没有影响。对最佳 $(\mathbf{w}, b)$ 支持向量满足：
$$y(\mathbf{w^T x} - b) = 1$$
更强容错能力
直觉上认为 SVM 有更强的容错能力。课程中比较了一般正则仳与 SVM：
| | minimize | constraint|
|:—–:|:—–:|:——-:|
regularization | $E{in}$ | $\mathbf{w^T w} \le C$
SVM | $\mathbf{w^T w}$ | $E{in} = 0$ [and more]
可看出 SVM 实际上做了与正则化相似的工作，而正则化能提高模型的容错能力。