文档介绍：支持向量机(SVM)简明学****教程
一、最优分类超平面
给定训练数据,其中,。
若,称为第一类的,;若,称为第二类的,。
若存在向量和常数,使得(1),则该训练集可被超平面分开。
(一)、平分最近点法
求两个凸包集中的最近点,做的垂直平分面x,即为所求。
,则,。
求,
所以,只需求出最小的。
算法:1)求解;2)求最优超平面。
(二)、最大间隔法
附加条件,加上(1)式。记,。
使(2)
可以说明在(2)下可以得到一个最优超平面,且该超平面是唯一的。
如何快速生成一个最优超平面???
考虑等价问题:求权向量和,使,且最小。
这种写法已经包含最大间隔。
事实上,而,故,。
所以(2)式可以转化为求解:
(3)
总结,求最优超平面,只需求解:
(QP1)
对(QP1)构造lagrange函数:
令,其中为lagrange乘子。
下求的鞍点:
1)、; 2)、。
将2)代入中,且目标改为。
则
所以,(QP1)的对偶问题为: (DQP1)
由KKT条件,。若存在时,有,此时,,则
几何意义:,是与超平面距离最近的向量,称其为支持向量。他在构造超平面中起到及其重要的作用。
SVM算法1(线性可分SVM分类机)
1)、求解规划问题(DQP1)
2)、求和,得到分类超平面。
3)、分类器:。
(三)、软间隔分类超平面
针对样本数据线性不可分的情况。此时。
解决方案:软化约束(通过添加松弛因子)。,其中,。
显然,当充分大时,软约束总是成立的,但不应该取太大。所以将加入到目标中,得到(QP2):
(QP2)
其中,为正的惩罚参数。
显然,QP2包含了QP1的,(取)。另外,QP2的鲁棒性好(稳定性好)
同样,对(QP2)构造lagrange函数:
令。
1)、; 2)、;
3)、。
代入中,得。
所以,(QP2)的对偶问题为: (DQP2)
对于,由KKT条件。当时,,则。
(四)、支持向量机
对于本质线性不可分问题,有两种方法:(1)构造非线性分类器;(2)将样本点射到高维特征空间,再用线性分类器。
例1:不可分
映射:,则可分。
基本思想:,
例2:对于圆,故。但复杂性增大,如,则二次特征空间。
(问题:推广性如何评价,技术上如何处理高维数据???)
1)、核函数
设,,。(注可为无穷)
考虑在Hilbert空间中内积的一个一般表达式:。
根据Hilbert-Schmidt理论,可以是满足下面一般条件的任意对称函数(Courant and Hilbert,1953)
定理(Mercer)要保证中的对称连续函数能以正的系数展开成
正定。()
2)支持向量机
训练样本,,则。
求上的超平面将分开(若可分),则最大间隔超平面:
(QP3)
其对偶问题为:
(DQP3)
设(DQP3)有解,则,,()。
从而,决策函数为。
算法(可分的SVM)
(1)、选样本; (2)、选核函数,用Mercer定理判断; (3)、计算,由(DQP3); (4)、代入决策函数应用。(错误率高可转(2)重来)
同样,对特征映射后的样本点线性可分难于判断,可引人松弛变量:
(QP4)
其对偶问题为: (DQP4)
则,()。