《SVM理论和算法分析报告》由会员分享，可在线阅读，更多相关《SVM理论和算法分析报告（16页珍藏版）》请在金锄头文库上搜索。
1、 范文范例 指导参考 硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：T=x1,y1，x2,y2，xN,yN其中，xiRn, yi+1,-1,i=1,2,N, xi为第i个特征向量或实例， yi为xi的类标记，当 yi=1时，称xi为正例，当 yi=-1时，称xi为负例；xi，yi为样本点。假设训练数据集是线性可分的（存在硬间隔），那么学习的目标是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面方程wx+b=0，它由法向量w和截距b决定，可用w,b表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据集线
2、性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面，解唯一。一、模型推导1.函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面wx+b=0确定的情况下，|wx+b|能够相对地表示（注意：真实距离为|wx+b|w）点x距离超平面的远近。而wx+b的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用标量ywx+b来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面w,b关于样本点xi，yi的函数间隔为：i=yiwxi+b超
3、平面w,b关于训练数据集T的函数间隔：=mini=1,2,Ni=mini=1,2,Nyiwxi+b2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，虽然超平面并没有改变，但函数间隔（它是w,b的线性函数）却依原比例同等改变。为了将w,b表示的超平面的唯一化，即每个超平面对应Rn+1中的唯一向量w,b，可以对法向量w加以规范化约束w=1，这时函数间隔称为几何间隔。超平面w,b关于样本点xi，yi的几何间隔为：i=iw=yiwwxi+bw超平面w,b关于训练数据集T的几何间隔为：=mini=1,2,Ni=mini=1,2,
4、Nyiwwxi+bw3.间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大的确信度将它们分开。因此所要优化的问题 表示为：maxw,b s.t. yiwwxi+bw, i=1,2,N改写为，maxw,b ws.t. yiwxi+b, i=1,2,N的
5、取值不影响最优化问题的解（如果w*,b*是最优解，那么w*,b*也是最优解，因此是变动的可以取到任意值，如果固定，w*,b*也就变得唯一了），令=1,等价变换为，maxw,b 1ws.t. yiwxi+b1, i=1,2,N（目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化）等价变换为（标准无等式约束的凸二次规划，这是为了运算方便），minw,b 12w2s.t. 1-yiwxi+b0, i=1,2,N凸二次规划问题存在全局最优解w*,b*。（4）分离超平面与分类决策函数分离超平面:w*x+b*=0分类决策函数:fx=signw*x+b*（5）支撑向量与间隔边
6、界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即1-yiwxi+b=0，对于正例点，支撑向量在超平面wxi+b=1上，对于负例点，支撑向量在超平面wxi+b=-1上，没有实例点落在这两个平行的超平面（间隔边界）之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w，等于2w。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagr
7、ange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入Lagrange乘子i，1Lagrange对偶函数： Lw,b,=12w2-i=1Niyiwxi+b+i=1Ni其中=1,2,NT为拉格朗日乘子向量，i0，i=1,2,N。2.对偶问题：maxminw,bLw,b,（1） 求minw,bLw,b,wLw,b,=w-i=1Niyixi=0bLw,b,=-i=1Niyi=0得出w=i=1Niyixii=1Niyi=0带入拉格朗日函数，得出minw,bLw,b,=12i=1Nj=1Nijyiyjxixj-i=1Niyij=1Njyjxjxi+b+i=1Ni=-12i=1Nj
8、=1Nijyiyjxixj+i=1Ni（2）求maxminw,bLw,b, max-12i=1Nj=1Nijyiyjxixj+i=1Nis.t. i=1Niyi=0i0，i=1,2,N转换为求极小min12i=1Nj=1Nijyiyjxixj-i=1Nis.t. i=1Niyi=0i0，i=1,2,N根据对偶理论，对上述对偶优化存在，使w*，b*是原始问题的解，*是对偶问题的解，因此求解原始问题，可以转化为求解对偶问题。3.最优解根据KKT条件w*Lw*,b*,*=w*-i=1Ni*yixi=0-（a）b*Lw*,b*,*=-i=1Ni*yi=0-（b）i*yiw*xi+b*-1=0 , i=
9、1,2,N-（c）yiw*xi+b*-10, i=1,2,N-（d）i*0, i=1,2,N-（e）由（a）求得w*=i=1Ni*yixi其中至少有一个k*0（如果*=0，那么w*=0，b*无解，显然它不是原始最优化问题的解），结合KKT条件（c），得出ykw*xk+b*-1=0将w*带入KKT条件，得出yki=1Ni*yixi xk+b*=1两边同时乘以yk，由于yk2=1ykyki=1Ni*yixi xk+b*=yki=1Ni*yixixk+b*=ykb*=yk-i=1Ni*yixixk因此分类决策函数为fx=signi=1Ni*yixix+b*从w*，b*中可以看出它们仅仅依赖于k*0的
10、特征点，即支撑向量（因为ykw*xk+b*-1=0w*xk+b*=1，所有xk在分隔边界上）；软间隔线性支撑向量机一、模型推导如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点xi，yi引入一个松弛变量i0，使函数间隔加上松弛变量大于等于1.这样约束条件变为yiw*xi+b*1-i同时对每个松弛变量i，支付一个代价i，目标函数变成minw,b 12w2+Ci=1Ni这里，C0称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化上述目标函数有两层含义，要使的12w2尽量小即间隔尽量
11、大，同时使的误分类的点的个数尽量小，C是调和二者的系数。这时的间隔称为软间隔，因为间隔内含义特异点。原始优化问题：minw,b 12w2+Ci=1Nis.t. 1-i-yiwxi+b0, i=1,2,Ni0, i=1,2,N这仍是一个二次凸优化，存在全局最优解，w的解是唯一的，但b的解不唯一，b的解存在于一个区间。二、模型求解仍使用Lagrange对偶方法求解1.Lagrange函数Lw,b,=12w2+Ci=1Ni-i=1Niyiwxi+b-1+i-i=1Nii其中，i0，i0。2.对偶问题：max,minw,b,Lw,b,(1)求minw,b,Lw,b,wLw,b,=w-i=1Niyixi
12、=0bLw,b,=-i=1Niyi=0Lw,b,=C1T-T-T=0得出w=i=1Niyixii=1Niyi=0C-i-i=0带入拉格朗日函数，得出minw,b,Lw,b,=-12i=1Nj=1Nijyiyjxixj+i=1Ni注意它与无关。（2）求maxminw,b,Lw,b, max-12i=1Nj=1Nijyiyjxixj+i=1Nis.t. i=1Niyi=0i0，i=1,2,Ni0，i=1,2,NC-i-i=0，i=1,2,N消去i，转换为求极小min12i=1Nj=1Nijyiyjxixj-i=1Nis.t. i=1Niyi=0i0，i=1,2,N0iC（3）最优解根据KKT条件w*Lw*,b*,*,*,*=w*-i=1Ni*yixi=0-(a)b*Lw*,b*,*,*,*=-i=1Ni*yi=0-(b)*Lw*,b*,*,*,*=C1T-*-*=0-(c)i*yiw*xi+b*-1+i*=0 , i=1,2,N-(d)i*i*=0 , i=1,2,N-(e)i*0, i=1,2,N-(f)yiw*xi+b*-1+i*0, i=1,2,N-(g)i*0, i=1,2,N-
