统计学习方法-7 支持向量机-1

支持向量机（support vector machine，SVM）属于二分类判别模型，以感知机为基础，但有别于感知机：
（1）、感知机只要求正确划分数据集，对解的唯一性不做要求
（2）、SVM不仅要求正确划分数据集，而且要求间隔最大，因而解具有唯一性（下文证明）

支持向量机不是一个算法，而是一套算法，从特殊到一般依次为：
（1）、线性可分支持向量机（硬间隔最大化）
（2）、线性支持向量机（软间隔最大化）
（3）、非线性支持向量机（软间隔 + 核函数技巧）

补：支持向量机本质上是求解凸二次规划的最优化算法，通过求得最优解，找到正确划分训练集且间隔最大的分离超平面。

回顾二次规划的一般形式：目标函数为二次凸函数，约束条件均为线性
分离超平面

SVM的假设空间

1 线性可分支持向量机

1.1 定义目标函数（原问题推导）：

运用反证法和凸函数定义，证明解的唯一性：

定义间隔边界：

间隔边界

注：
1、在决定分离超平面时只有支持向量起作用，其他样本点不起作用；
2、如果移动支持向量，那么解将改变；
3、如果移动甚至去掉其他样本点，解不变。

1.2 从原问题到对偶问题
对偶化有两个好处：
（1）、更容易求解
（2）、可以自然的引入核函数，推广到非线性支持向量机

引：回顾凸优化中，从原问题到对偶问题的推导过程

从原问题到拉格朗日函数再到对偶函数（凹函数）
再到对偶问题（凸问题）

因此，对于线性可分SVM，我们有：

那么，对于满足Slater（充分）条件和KKT（必要）条件的最优化问题，可以通过解KKT条件求出对偶问题和原问题的最优解（从Slater到KKT的推导过程此处略，具体参见Boyd凸优化第五章），那么，线性可分SVM的KKT条件可以归纳为：

注：alpha > 0 的样本点即为支持向量，根据互补松弛性条件，此时对应的样本点 x 在间隔边界上。

未完待续