支持向量机系列导航
本系列介绍支持向量机的基本概念、数学推导、核技巧以及实际使用。
先验知识
分离超平面定理
分离超平面定理：可以用超平面分离不相交的凸集．最基本的结果是分离超平面定理和支撑超平面定理．
**分离超平面定理 **如果$C$ 和$D$ 是不相交的两个凸集，则存在非零向量$a$ 和常数$b$，使得
$$ a^Tx\leq b, ;;;;\forall x\in C, ;;;;且; x^Tx \geq b,\forall x \in D $$
如下图，超平面${x|x^Tx=b}$分离了凸集 $C$和$D$
**严格分离定理 **设$C$ 是闭凸集，点 $x_0 \notin C$，则存在非零向量$a$ 和常数$b$，使得
$$ a^{\mathrm{T}} x<b, \forall x \in C, \quad \text { 且 } \quad a^{\mathrm{T}} x_{0}>b $$
上述严格分离定理要求点$x_0 \notin C,$ 当点$x_0$ 恰好在凸集$C$ 的边界上时，我们可以构造支撑超平面．
**定义：支撑超平面 **给定集合$C$ 及其边界上一点$x_0$，如果$a \neq 0$满足$a^Tx \leq a^Tx_0, ∀x ∈ C$，那么称集合
$$ \left{x \mid a^{\mathrm{T}} x=a^{\mathrm{T}} x_{0}\right} $$
为$C$在边界点$x_0$ 处的支撑超平面，如下图
因此，点$x_0$ 和集合$C$ 也被该超平面分开．从几何上来说，超平面${ x | aTx = a^Tx_0 }$ 与集合$C$ 在点$x_0$处相切并且半空间${x |a^Tx \leq a^Tx_0}$ 包含$C$．
根据凸集的分离超平面定理，我们有如下支撑超平面定理．
**支撑超平面定理 **如果$C$是凸集，则在$C$的任意边界点处都存在支撑超平面．
支撑超平面定理有非常强的几何直观：给定一个平面后，可把凸集边界上的任意一点当成支撑点将凸集放置在该平面上
整体脉络
SVM是一种二分类模型，基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使之区别于感知机(PLA)。若不能完全线性可分，则分两种情况
- 有少许误差导致
- 完全非线性可分
针对以上两类分别衍生出软间隔SVM 和 引入核函数的SVM
与感知机(PLA)区别与联系如下图：
$$ \begin{array}{ccc}\hline \text{线性可分}&\text{有一点点错误}&\text{严格非线性}\\hline \text{PLA}&\text{Pocket PLA}&\phi(\cdot)\text{+PLA}\\hline \text{Hard-Margin SVM}&\text{Soft-Margin SVM}&\phi(\cdot)\text{+Hard-Margin SVM}\\hline \end{array} $$
感知机器得到的超平面是有无数多个的，尽管每一个超平面都可以在训练集上将样本正确的分类，但有些超平面对某个噪声是很敏感的，就是他的鲁棒性并不是那么好。话句话说就是并不是每一个超平面都能在测试集上表现的很好。 我们的机器学习算法不仅关注训练误差，更要关注期望损失，或者说泛化误差。 所以支持向量机旨在找到一个最佳的超平面，这个超平面在训练集上，从几何的角度看，它处于最最中间，距离所有的样本间隔最大。
SVM的学习策略就是间隔最大化，可形式化为一个求解凸二次规划问题。学习算法就是凸二次规划的最优化算法。
支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case)、线性支持向量机（linear support vector machine）以及非线性支持向量机（non-linear support vector machine）。简单模型是复杂模型的基础，也是复杂模型的特殊情况。
当训练数据线性可分时，通过硬间隔最大化（hard margin maximization） ，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支待向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支待向量机。
参考
《最优化：建模、算法与理论》刘浩洋、户将、李勇锋、文再文编著
《统计学习方法》李航著