svm理论和算法分析

《svm理论和算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：T=x1,y1，x2,y2，…，xN,yN其中，xi∈Rn,yi∈+1,-1,i=1,2,…,N,xi为第i个特征向量或实例，yi为xi的类标记，当yi=1时，称xi为正例，当yi=-1时，称xi为负例；xi，yi为样本点。假设训练数据集是线性可分的（存在硬间隔），那么学习的目标是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面方程w∙x+b=0，它由法向量w和截距b决定，可用w,b表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据

2、集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面，解唯一。一、模型推导1.函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w∙x+b=0确定的情况下，

3、w∙x+b

4、能够相对地表示（注意：真实距离为

5、w∙x+b

6、∥w∥）点x距离超平面的远近。而w∙x+b的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用标量yw∙x+b来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面w,b关于样本点xi

7、，yi的函数间隔为：γi=yiw∙xi+b超平面w,b关于训练数据集T的函数间隔：γ=mini=1,2,…,Nγi=mini=1,2,…,Nyiw∙xi+b2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，虽然超平面并没有改变，但函数间隔（它是w,b的线性函数）却依原比例同等改变。为了将w,b表示的超平面的唯一化，即每个超平面对应Rn+1中的唯一向量w,b，可以对法向量w加以规范化约束∥w∥=1，这时函数间隔称为几何间隔。超平面w,b关于样本点xi，yi的几何间隔为：γi=γi∥w∥=yiw∥w∥

8、∙xi+b∥w∥超平面w,b关于训练数据集T的几何间隔为：γ=mini=1,2,…,Nγi=mini=1,2,…,Nyiw∥w∥∙xi+b∥w∥3.间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大的确信度将它们分开。因此所要优

9、化的问题表示为：maxw,bγs.t.yiw∥w∥∙xi+b∥w∥≥γ,i=1,2,…,N改写为，maxw,bγ∥w∥s.t.yiw∙xi+b≥γ,i=1,2,…,Nγ的取值不影响最优化问题的解（如果w*,b*是最优解，那么λw*,λb*也是最优解，因此γ是变动的可以取到任意值，如果固定γ，w*,b*也就变得唯一了），令γ=1,等价变换为，maxw,b1∥w∥s.t.yiw∙xi+b≥1,i=1,2,…,N（目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化）等价变换为（标准无等式约束的凸二次规划，这是为了运算方便），minw,b12∥w∥

10、2s.t.1-yiw∙xi+b≤0,i=1,2,…,N凸二次规划问题存在全局最优解w*,b*。（4）分离超平面与分类决策函数分离超平面:w*∙x+b*=0分类决策函数:fx=signw*∙x+b*（5）支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即1-yiw∙xi+b=0，对于正例点，支撑向量在超平面w∙xi+b=1上，对于负例点，支撑向量在超平面w∙xi+b=-1上，没有实例点落在这两个平行的超平面（间隔边界）之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w，

11、等于2∥w∥。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入Lagrange乘子αi，1．Lagrange对偶函数：Lw,b,α=12∥w∥2-i=1Nαiyiw⋅xi+b+i=1Nαi其中α=α1,α2,…,αNT为拉格朗日乘子向量，αi≥0，i=1,2,…,N