1 概述

支持向量机（support vector machines，SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。支持向量机还包括核技巧，这使它成为我实质上的非线性分类器。支持向量机的学习策略是间隔最大化，可形式划为一个求解凸二次规划（convex quadratic programing）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
支持向量机学习包含构建由简至繁的模型：

• 线性可分支持向量机（linear support vector machine in linearly separable case）
  • 又称为应间隔支持向量机
  • 间隔最大化（hard margin maximization）
• 线性支持向量机（linear support vector machine）
  • 又称为软间隔支持向量机
  • 软间隔最大化（soft margin maximization）
• 非线性支持向量机（non-linear supoort vector machine）

  2 算法

  2.1 线性可分支持向量机与硬间隔最大化

  线性可分支持向量机

  定义2.1（线性可分支持向量机）给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题得到的分流超平面为
  (2.1)
  以及相应的分类决策函数
  (2.2)
  称为线性可分支持向量机。

函数间隔和几何间隔

定义2.2（函数间隔）对于给定的训练数据集和超平面，定义超平面关于样本点的函数间隔为
(2.3)
定义超平面关于训练数据集的函数间隔为超平面关于中所有样本点的函数之间隔之最小值，即
(2.4)

定义2.2（几何间隔）**对于给定的训练数据集和超平面，定义超平面关于样本点的几何间隔为
(2.5)

定义超平面关于训练数据集的函数间隔为超平面关于中所有样本点的几何之间隔之最小值，即
(2.6)
超平面关于样本点的几何间隔一般是实例点到超平面的带符号的距离（signed distance），当样本点被超平面正确分类是就是实例点到超平面的距离。

从函数间隔和几何间隔的定义（式(2.3)~式(2.6)）可知，函数间隔和几个间隔有下面的关系：
(2.7)
(2.8)
如果，那么函数间隔和几何间隔相等。如果超平面参数和成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。

间隔最大化

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

1. 最大间隔分离超平面

算法2.1（线性可分支持向量机学习算法——最大间隔法）
输入：训练数据集，其中，，；
输出：最大间隔分离超平面和分类决策函数
（1）构造并求解约束最优化问题：

（2）由此得到分离超平面：

分类决策函数

2.最大间隔分离超平面的存在唯一性

线性可分训练数据集的最大间隔分离超平面是存在且唯一的。
定理2.1（最大间隔分离超平面的存在是唯一的）若训练数据集线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

3.支持向量和间隔边界

在决定分离超平面时只有支持向量起作用，而其它实例点并不起作用。如果移动支持向量将改变所有的解；然是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称为支持向量机。支持向量机的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

学习的对偶算法

定理2.2 设是对偶最优化问题(2.22)~(2.24)的解，则存在下标，使得，并可按下式求得原始最优化问题(2.13)~(2.14)的解：
(2.25)
(2.26)
算法2.2（线性可分支持向量机的算法）
输入：训练数据集，其中，，；
输出：分离超平面和分类决策函数

定义2.4（支持向量） 考虑原始最优化问题(2.13)~(2.14)及对偶最优化问题(2.22)~(2.24)，将训练数据集中对应于的样本点的实例称为支持向量。

2.2 线性支持向量机与软间隔最大化

2.3

2.4

3 实现

4 实践

5 问题集合

6 继续阅读

详见《统计机器学习》第二版参考文献

CHANGELOG

2021年01月06日16:13:02
第一版更新，参考自《统计机器学习》第二版 -