支持向量机(support vector machine,SVM)属于二分类判别模型,以感知机为基础,但有别于感知机:
(1)、感知机只要求正确划分数据集,对解的唯一性不做要求
(2)、SVM不仅要求正确划分数据集,而且要求间隔最大,因而解具有唯一性(下文证明)
支持向量机不是一个算法,而是一套算法,从特殊到一般依次为:
(1)、线性可分支持向量机(硬间隔最大化)
(2)、线性支持向量机(软间隔最大化)
(3)、非线性支持向量机(软间隔 + 核函数技巧)
补:支持向量机本质上是求解凸二次规划的最优化算法,通过求得最优解,找到正确划分训练集且间隔最大的分离超平面。
回顾二次规划的一般形式:目标函数为二次凸函数,约束条件均为线性
分离超平面

1 线性可分支持向量机

1.1 定义目标函数(原问题推导):




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


定义间隔边界:

注:
1、在决定分离超平面时只有支持向量起作用,其他样本点不起作用;
2、如果移动支持向量,那么解将改变;
3、如果移动甚至去掉其他样本点,解不变。
1.2 从原问题到对偶问题
对偶化有两个好处:
(1)、更容易求解
(2)、可以自然的引入核函数,推广到非线性支持向量机
引:回顾凸优化中,从原问题到对偶问题的推导过程
从原问题到拉格朗日函数再到对偶函数(凹函数)
再到对偶问题(凸问题)
因此,对于线性可分SVM,我们有:

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

注:alpha > 0 的样本点即为支持向量,根据互补松弛性条件,此时对应的样本点 x 在间隔边界上。
未完待续
网友评论