一句话介绍

支持向量机是一种分类模型，求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

---

0.支持向量

要理解什么是支持向量（support vector），首先需要理解以下几个概念：

如果我们有一堆数据（二维），在二维平面上分布如下图所示：

我们可以用一条直线将这堆数据分成两个部分：

【当这堆数据维数是3维，这条直线就成了平面；当数据维数更高，这条分隔线就成了超平面】以下统称超平面，数学表达为：

$w^\cdot x + b^=0$

要说明的是，仅仅把这堆数据分离开，也许有无数个超平面可以做到；

我们做一些规范，最大几何间隔的分离超平面，是唯一且存在的。

很明显，分隔之后，有的点离这个超平面近，有的远，最近点到超平面的距离，称为间隔，这个最近的样本点的实例就被称为支持向量【本定义适用于线性可分情况下】。

支持向量在确定分离超平面中起决定性作用（不移动支持向量，分离超平面就不会变化），所以把这种分类模型称为支持向量机。

相关重要概念：

类标记概念：可以理解为因变量，但是这个量更准确地说是观测值、实际值，而不是由函数计算出来的

函数间隔：该点的类标记和超平面函数值的乘积$\hat \gamma_i=y_i(w\cdot x_i+b)$【表示分类预测的正确性和确信度】

几何间隔：规定$L||w||=1$（L2范数）情况下的函数间隔$\gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$【实例点到超平面的带符号的距离】

硬间隔最大化：线性可分的训练数据集——线性可分支持向量机

软间隔最大化：训练数据集近似线性可分——线性支持向量机

1.线性可分支持向量机

找最大间隔分离超平面：该超平面对训练数据集的几何间隔至少应大于某个值；

凸优化问题 P116 与凸二次规划问题

最大间隔法

in：可分训练数据集，x 和对应的类标记 y

out：最大间隔分离超平面（参数 w 和 b），分类决策函数（$sign$函数）

间隔边界

与最大间隔分离超平面相平行的平面中，有两个超平面 H1 和 H2 之间没有任何实例点，这两个超平面就是间隔边界，中间的距离就是间隔。

线性可分支持向量机的对偶算法

使用拉格朗日乘子法进行问题的转化，注意我们的目标：要使间隔最大——也就是$||w||^2$尽可能小

分类决策函数：$f(x)=sign(\Sigma_{i=1}^N\alpha_i^y_i(x\cdot x_i)+b^)$只依赖于输入x和训练样本输入的内积

本方法中，将训练数据中对应于$\alpha^*_i>0$的样本点称为支持向量【这里的是$\alpha_i$拉格朗日乘子】

本方法核心思想是拉格朗日乘子法，在使用的过程中，将约束条件从几何间隔转化为了$\alpha_i$的约束

2.线性支持向量机

训练样本线性不可分——软间隔最大化

其实主要是有少量的“特异点”（outlier），将这些点去除之后，剩下的样本就线性可分了。

我们并不能直接去除这些特异点，但是可以放宽标准，增加一个松弛变量，一来放宽限制，二来在目标函数中进行惩罚，确保误分类的样本尽量少。

线性支持向量机包含线性可分支持向量机

如果假设此处的分离超平面是$w^\cdot x+b^=0$，那么 w 的解是唯一的，但是 b 的解可能不唯一，而是存在一个区间

下图表示软间隔的支持向量：

合页损失函数

在本问题中，还有一种以合页损失函数表示的目标函数：

$\Sigma_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2$

其中前半部分称为合页损失函数(hinge loss function)：$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$

其中$[z]_+=\left { \begin{aligned} z , z>0 \ 0, z \leq 0\end{aligned} \right.$

该函数特性就是

• 如果样本点被正确分类且函数间隔大于1，那么损失是0
• 其他情况下，损失是$1-y_i(w\cdot x_i+b)$

下图中：

• 左侧水平线是 0-1损失 的一部分【真正的二类分类问题】
• 虚线斜线是合页损失函数（不带1时）
• 实现是完整的合页损失函数，只有当确信度足够高时，损失才是0，要求更高

3.非线性支持向量机与核函数

非线性可分问题：如果能用一个超曲面将正负类正确分开，则称非线性可分问题

求解思路：进行非线性变换，将非线性问题变换为线性问题然后进行求解

核技巧

基本想法

• 通过一个非线性变换将输入空间（欧式空间或者离散空间）对应于一个特征空间（希尔伯特空间）
  使得输入空间中的超曲面模型对应于特征空间中的超平面模型
• 在特征空间中求解线性支持向量机

核函数

从输入空间 X 到 特征空间 H 的映射关系为$\phi(x)$

则输入空间中的两个量的核函数值应该是映射函数的内积$K(x,z)=\phi(x)\cdot \phi(z)$，K 是核函数

给定核函数，特征空间和映射关系的取法不唯一

非线性支持向量机

只需要将线性支持向量机对偶形式中的内积换成核函数即可，当然实际计算过程过程麻烦了很多

4.序列最小最优化方法

支持向量机的学习问题可以转化为求解凸二次规划问题，但样本容量较大时，算法会变得低效；

支持向量及的高效实现方法之一：序列最小最优化 SMO 算法

分两步：

（1）选择变量的启发式方法，将原问题不断分解为子问题

（2）求解两个变量二次规划的解析方法

直到所有变量满足KKT条件为止