支持向量机引入

支持向量机系列导航

本系列介绍支持向量机的基本概念、数学推导、核技巧以及实际使用。

先验知识

分离超平面定理

分离超平面定理：可以用超平面分离不相交的凸集．最基本的结果是分离超平面定理和支撑超平面定理．

**分离超平面定理 **如果 $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）及软间隔最大化，学习非线性支待向量机。

参考

《最优化：建模、算法与理论》刘浩洋、户将、李勇锋、文再文编著

《统计学习方法》李航著