SVM算法笔记（2）

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

1.线性可分支持向量机

一般地，训练数据线性可分，存在无穷个分离超平面可将两类数据正确分开。

感知机利用误分类最小的策略，求得分离超平面，解有无穷多个。

线性可分支持向量机利用间隔最大化求最优分离超平面，解唯一。

定义1（线性可分支持向量机）：给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

以及相应的分类决策函数，称为线性可分支持向量机。

2.函数间隔和几何间隔

定义2（函数间隔）：对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点的函数间隔为：。

函数间隔表示分类预测的正确性及确信度。但在选择分离超平面时，只有函数间间隔还不够，因为直言成比例改变w和b，超平面并没有改变，但函数间隔却变了，因此需要对分离超平面的法向量w加约束条件，规范化||w||=1，使得间隔确定，函数间隔成为几何间隔。

超平面（w,b），法向量w，点A表示某一实例，在超平面正的一侧的情形，某类标记为。点A与超平面(w,b)的距离由线段AB给出，记作。。其中，||w||为w的范数。点A在超平面负的一侧，即，那么点与超平面的距离为。

当样本点被超平面（w,b）正确分类时，点与超平面（w,b）的距离是。

定义3（几何间隔）：对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点的几何间隔为。

定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点的几何间隔之最小值，即。

函数间隔和几何间隔关系:

若||w||=1，那么函数间隔和几何间隔相等；

若超平面参数w和b成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。

3.间隔最大化

支持向量机学习的基本想法：求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

间隔最大化：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。

• 最大间隔分离超平面

凸优化问题：指约束最优化问题。

其中目标函数f(w)和约束函数都是上的连续可微的凸函数，约束函数是上的仿射函数。

当目标函数f(w)是二次函数且约束函数是仿射函数时，上述凸最优化问题成为凸二次规划问题。

算法1（线性可分支持向量机学习算法——最大间隔法）：

输入：线性可分训练数据集T

输出：最大间隔分离超平面和分类决策函数

（1）构造并求解约束最优化问题：

，

求得最优解，。

（2）由此得到分离超平面：，分类决策函数

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

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

• 支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。

支持向量是使约束条件式等号成立的点，即

对的正例点，支持向量在超平面上

对的正例点，支持向量在超平面上。

与之间的距离称为间隔（margin）

间隔依赖于分离超平面的法向量w，等于

与称为间隔边界