【西瓜书】支持向量机（SVM）

支持向量机（Support Vector Machine，简称SVM）。

超平面

分类学习最基本的想法就是基于训练集合D在样本空间中找到一个划分超平面，将不同类别的样本分开。
但能将训练样本分开的划分超平面可能有很多，应该努力去找到哪一个呢？直观上看应该去找位于两类训练样本正中间的划分超平面，因为该划分超平面对训练样本局部扰动的“容忍”性最好。这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
在样本空间中划分超平面可通过如下线性方程来描述：
$w^Tx+b=0$ 其中： $w=(w_1;w_2;...;w_d)$ 为法向量，决定了超平面的方向；
$b$ 为位移项，决定了超平米与原点之间的距离。
划分超平面可以被法向量 $w$ 和位移 $b$ 确定，记为 $(w, b)$ 。样本空间中人一点 $x$ 到超平面 $(w, b)$ 的距离可写为：
$r=\frac{|w^Tx+b|}{||w||}$
超平面具有以下性质:
1. 法向量 $w$ 和位移项 $b$ 确定一个唯一超平面;
2. 超平面方程不唯一，因为当等倍缩放 $w$ 和 $b$ 时(假设缩放倍数为 α)，所得的新超平面方程 $αw^Tx + αb = 0$ 和 $w^Tx + b = 0$ 的解完全相同，因此超平面不变，仅超平面方程有变;
3. 法向量 $w$ 垂直于超平面;
4. 超平面将 n 维空间切割为两半，其中法向量 $w$ 指向的那一半空间称为正空间，另一半称为负空间，正空间中的点 $x^+$ 代入进方程 $wT x + + b$ 其计算结果大于 0，反之负空间中的点代入进方程其计算结果小于 0;
5. n 维空间中的任意点 x 到超平面的距离公式为 $r=\frac{|w^Tx+b|}{||w||}$ ，其中 $∥ w ∥$ 表示向量 w 的模。

支持向量机（SVM）

支持向量机所要求的超平面需要满足三个条件：
1. 能正确划分正负样本，
2. 要位于正负样本正中间，
3. 离正负样本都尽可能远。
距离超平面最近的这几个训练样本点使得上式的等号成立，它们被称为“支持向量 ” （support vector），两个异类支持向量到超平面的距离之和为：
$\gamma=\frac{2}{||w||}$ 它被称为“间隔”（margin）。
要找到具有“最大间隔”（maximum margin）的划分超平面，也就是要找到满足中约束的参数w和b，使得γ最大，即：
$\begin{align*} &\max_{w,b} \frac{2}{\|w\|} \\&s.t. \,\, y_i(w^Tx+b)\geqslant 1, \,\, i=1,2,...,m. \end{align*}$
为了最大化间隔，仅需最大化||w||^{(-1)，则等价于最小化||w||}2，于是上式可重写为：
$\begin{align*} &\min_{w,b} \frac{1}{2}{\|w\|}^2 \\&s.t. \,\, y_i(w^Tx+b)\geqslant 1, \,\, i=1,2,...,m. \end{align*}$
这就是支持向量机的基本型。

支持向量机求解

求解下式来得到大间隔划分超平面对应的模型：
$f(x)=w^Tx+b$ 其中w和b是模型参数，注意这个式子本身是一个凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包来求解。
针对这个问题，SVM提出了很多更高效的办法。
对偶问题：针对上式，使用拉格朗日乘子法可以得到“对偶问题”（dual problem）。
SVM的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。支持向量机这个名字强调了此类学习器的关键是如何从支持向量构建出解；同时也暗示着其复杂度主要与支持向量的数目有关。
为了避免在二次规划中，问题的规模正比于训练样本数造成的巨大开销，利用问题本身的特性提出了很多优化算法，SMO（Sequential Minimal Optimization）是著名的代表。

核函数

前面都是假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类，然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对于这样的问题可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
如果原始空间是有限维，即属性数有限，那么一定存在一个高位特征空间使样本可分。
$x_i$ 与 $x_j$ 在特征空间的内积等于它们在原始样本空间中通过函数 $κ (., .)$ 计算的结果。
$\kappa (x_i, y_i)=〈\phi (x_i),\phi (x_j)〉=\phi (x_i)^T\phi (x_j)$
将样本映射到特征空间之后的内积，这里的映射函数κ就是“核函数”（Kernel function）。
模型最优解可通过训练样本的核函数展开，这一展式也叫“支持向量展示”（support vector expansion）。

硬间隔、软间隔

之前假设训练样本在样本空间或特征空间中是线性可分的，然而在现实当中往往很难确定合适的核函数使训练样本在特征空间中可分。
缓解该问题的一个办法是允许支持向量机在一些样本上出错，因此引入了“软间隔”（soft margin）的概念。
所有样本都必须划分正确，这称为“硬间隔”（hard margin）。“软间隔”则是允许某些样本不满足约束。

支持向量回归

在回归问题中，对于给定样本，传统回归模型通常直接基于模型的输出与真实输出之间的差别来计算损失，仅当真实输出与模型输出完全相同时，损失才为0。
“支持向量回归”（support vector regression，简称SVR）假设我们容忍真实输出与模型输入之间最多有 ε 的偏差，即仅当两者之间的差别绝对值大于 ε 时才计算损失。