学习笔记|线性可分支持向量机学习的间隔最大算法
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言,线性可分分离超平面有无穷多个(等价于感知机,可参见学习笔记|感知机(二)),但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。
间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
1. 求解最大间隔分离超平面
下面考虑如何求得一个几何间隔最大的分离超平面,即最大间隔分离超平面。具体地,这个问题可以表示为下面的约束最优化问题:
即我们希望最大化超平面(ω,b)关于训练数据集的几何间隔γ,约束条件表示的是超平面(ω,b)关于每个训练样本点的几何间隔至少是γ。
考虑几何间隔和函数间隔的关系式(参见学习笔记|线性可分支持向量机的函数间隔和几何间隔),可将这个问题改写为
这是一个凸二次规划问题。
凸优化问题是指约束最优化问题
综上所述,就有下面的线性可分支持向量机的学习算法——最大间隔法。
线性可分支持向量机学习最大间隔法:
输出:最大间隔分离超平面和分类决策函数。
(1)构造并求解约束最优化问题:
(2)由此得到分离超平面:
分类决策函数
2. 支持向量和间隔边界
在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使约束条件式等号成立的点,即
在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。如果移动支持向量将改变所求的解;但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机。支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定。
参考文献
【1】统计学习方法(第2版),李航著,清华大学出版社
- 点赞
- 收藏
- 关注作者
评论(0)