SVM理论和算法分析报告

理范文范例指导参考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)为样本点。假设训练数据集是线性可分的(存在硬间隔)，那么学习的目标是在特征空间找到一个分离超平面，能将实特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小大化求最优分离超平面，超平面(,)关于样本点(，)的函数间隔为：=(∙+)超平面(,)关于训练数据集T的函数间隔：==(∙+)==(∙+)2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，虽然超平面并没有改变，但函数间隔(它是(w,b)的线性函数)却依原比例同等改变。为了将(w,b)表示的超平面的唯一化，即每个超平面对应Rn+1中的唯一向量(w,b)，可以对法向量w加以规化约束∥w∥=1，这时函数间隔称为几何间隔。超平面(,)关于样本点(，)的几何间隔为：==(∙+)间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点(离超平面最近的点)也有足够多大..(∙+)≥,=,,…,,,∥∥..(∙+)≥,=,,…,的取值不影响最优化问题的解(如果w∗,b∗是最优解，那么λw∗,λb∗也是最优解，因此是变动的可以取到任意值，如果固定，w∗,b∗也就变得唯一了)，令=1,等价变换为，理范文范例指导参考,∥∥..(∙+)≥,=,,…, (目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化)等价变换为(标准无等式约束的凸二次规划，这是为了运算方便)，∥∥,..,..−(∙+)≤,=,,…,(4)分离超平面与分类决策函数分离超平面:∗∙+∗=分类决策函数:()=(∗∙+∗)(5)支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量=上，对于负例点，支撑向量在超平面∙+=−上，没有实例点落在这两个平行的超平面是使约束条件等号成立的点，即−(∙+)=，对于正例点，支撑向量在超平面=上，对于负例点，支撑向量在超平面∙+=−上，没有实例点落在这两个平行的超平面 (间隔边界)之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w，等于。∥∥量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中angei(,,)=∥∥−(⋅+)+maxminL(w,b,α)(1)求(,,)∇bL(w,b,α)=−αiyi=0理(,,)=(∙)−∑((∑)∙+)+∑==−(∙)+(2)求(,,),(−(∙)+)=..∑=((∙)−)=..∑=由(a)求得∗=∑其中至少有一个α∗>其中至少有一个α∗>0(如果α∗=0，那么w∗=0，b∗无解，显然它不是原始最优化问题的解)，结合KKTk条件(c)，得出yk(w∗∙xk+b∗)−1条件(c)，得出将∗带入KKT条件，得出Nyk((∑αyixi)∙xk+b∗)=1理范文范例指导参考ykyk((αyixi)∙xk+b∗)=ykαyi(xi∙xk)+b∗=yk∗=−(∙)因此分类决策函数为范文范例指导参考如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点(xi，yi)引入一个松弛变量ξi≥0，使函数间隔加上松弛变量大于等于1.这样约束条件变为(∗∙+∗)≥−∥∥+ξi这里，C>0称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化上述目标函数有两层含义，要使的1∥w∥2尽量小即间隔尽量大，同时使的误分类的点的个数尽2量小，C是调和二者的系数。这时的间隔称为软间隔，因为间隔含义特异点。∥∥+..−−(∙+)≤=,,…,≥,=,,…,这仍是一个二次凸优化，存在全局最优解，w的解是唯一的，但b的解不唯一，b的解存在于一个区间。(,,,,)=∥∥+−((⋅+)−+)−==2.对偶问题：(,,,,∑αiyi=0理理范文范例指导参考(,,,,)=−(∙)+(2)求(,,,,)(−(∙)+)=..∑=−−=，=,,…,消去μi，转换为求极小((∙)−)=..∑=≤≤(3)最优解∗α(yi(w∗∙xi+b∗)−1+)=0,i=1,2,…,N---------------------(d)i∗∗=0,i=1,2,…,N-------------------------------------------------(ei∗≥0,i=1,2,…,N----------------------------------------------------(f)yi(w∗∙xi+b∗)−1+≥0,i=1,2,…,N--------------------------(g)∗=∑由(c)、(e)、(i)得出再结合(f)得出(−)=−≥由(d)，(h)得出理范文范例指导参考∗=−∑(∙)；此种情况下，进一步讨论：如果=，那么在间隔边界上；如果<<1，那么分类正确，在间隔边界与分离超平面之间；如果=，那么在分界面上；如果>1，那么在分离超平面误分一侧；因此可以看出，软间隔的支撑向量(∗>0)或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。量的另一种解释N值得函数。yiwxyiwxib数为λ的w的L2数，是正则化项；这两种优化是等价的(通过变量替换方法)；理(希尔伯特空间是完备化的內积空间，其中的每个元素是一个向量(可以无穷维)，向量之间定义有內积运(希尔伯特空间是完备化的內积空间，其中的每个元素是一个向量(可以无穷维)，向量之间定义有內积运对于分类问题是非线性的(线性模型无法将正负实例正确分开)，可以利用核技巧，进行一个非线性变换，线性问题的方法求解原来的非线性问题。技巧应用到支持向量机，其基本思想：通过一个非线性变换将输入空间(欧氏空间Rn或离散集合)对应于一个特征空间(希尔伯特空间H)，使得在输入空间Rn中的超曲面模型对应于特征空间H中的超平面模型(支撑向量机)，这样分类问题的学习在线性支撑向量机的对偶问题中，无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实 ∑()=(∙)−∑∗=∑∗=−∑(∙)()=(∑(∙)+∗)函数，核函数选择的有效性需要通过实验验证。X(欧氏空间Rn的子集或离散集合)，H为特征空间(希尔伯特空间)，如果存在一算，且空间关于內积诱导出的数是完备的)理范文范例指导参考对于给定的核函数K(x,z)，特征空间H(希尔伯特子空间)和映射函数的取法不唯一，因为核函数给出核函数判定定理：设K：X×X→R是对称函数，则K(x,z)为正定核函数的充要条件是对任意xi∈X，i=对于一个具体函数K(x,z)来说，检验它是否为正定核函数并不容易，因为要去对任意有限输入集验证K对应的Gram矩阵是否为半正定。在实际问题中往往应用已有的核函数。--------------------------------------------------------------------------------------------------------------(3)字符串核函数：1)基本定义：所有字符串的集合：Σ∗=⋃0Σn;s的子串u：给定一个指标序列i=(i1,i2,…,i|u|),1≤i1<i2<⋯<i|u|≤|s|,u=s(i)=s(i1)s(i2)…s(i|u|)，其长度记作l(i)=i|u|−i1+1，如果i是连续的，则l(i)=|u|；否则l(i)>||。2)映射定义： [()]=∑:()=()， ()是表示通过指标序列i，表示的一个s的子串，这个子串可以不连续；()=u表示s的子串()asd为有两个asd，序号分别为236,246;3)核函数kn(s,t)=∑[()][()]=∑∑()()∈∈(i,j):s(i)=t(j)=u它给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上，两个字符串相同的子串越多，它们就越相似，字符串核函数的值就越大，字符串核函数可以由动态规划快速计算。支撑向量机的学习问题可以形式化为求解凸二次规划问题，具有全局最优解，并且有很多最优化算法可以用于求解这一问题。但是当训练样本容量很大时，这些算法往往变得非常低效。序列最小最优化算法，由范文范例指导参考量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，子问题s.t.αiyi=0iCi1,2,…,N由于y∗y=i=2如果α2确定，那么α1也随之确定，所以子问题中同时更新两个变量。优化子问题：SMO失一般性，假(1)求解两变量二次规划的解析方法：不等式约束(盒子约束)条件的限制：22范文范例指导参考11221122122111221122122112212212212由(a),(b)得出：如果=，那么=(,+−)≤≤(+,)=---------(c)12212221212由(a),(d)得出：如果≠，那么=(,−)≤≤(−+,)=---------(e)1下面忽略不等式约束，求取迭代解αnew，unc：2N+y2α2(∑yiαiKi2)NN+(−α2y2)(∑yiαiKi1)+y2α2(∑yiαiKi2)对α2求导理理范文范例指导参考N(∑yiαiKi1)2N(∑yiαiKi1)2++y2(∑yiαiKi2)NNiKiNNii=3ii=3α2(Kα2(K11+K22−2K12)−y2(y2−y1+K11−K12+(∑yiαiKi1)−(∑yiαiKi2))ii=3αew，uncαew，unc(K11+K22−2K12)=y2(y2−y1+K11−K12+(∑yiαiKi1)−(∑yiαiKi2))ii=3NN=y2(y2−y1+K11αldy1+K11αldy2−K12αldy1−K12αldy2+(∑yiαiKi1)−(∑yiαiKi2))ii=3dKii1NNNNii1ii1理 NN=(K11+K22−2K12)αld+y2((∑yiαiKi1−y1)−(∑yiαiKi2−y2))ii=1的预测与真实输出y之差；那么NNαew，unc(K11+K22−2K12)=(K11+K22−2K12)αld+y2((∑yiαiKi1−y1)−(∑yiαiKi2−y2))11221222111221222122(K+K−2K)2new，unc=22(K+K−2K)2112212−E2)y2(E1−E2)12∥φ(x)−φ(x)12αew=αnew，unc2{L,αnew，unc>2L≤αnew，unc≤Hαnew，unc<2112211221122112211122111221112211122=+(−)(2)变量的(启发式)选择方法：T1)第一个变量的选择其对应的变量作为第1个变量。具体地，检验训练样本点(xi，yi)是否满足KKT条件，即(具体推导见软间Nαi=0⇔yi(∑αjyjK(xj∙xi)+b)≥1j=1N0<αi<⇔yi(∑αjyjK(xj∙xi)+b)=1j=1Nαi=C⇔yi(∑αjyjK(xj∙xi)+b)≤1j=1范文范例指导参考该检验是在围进行的。在检验过程中，外层循环首先遍历所有满足条件0<αi<的样本点，即在间隔边界上的支撑向量点，检验它们是否满足KKT条件；如果这些样本点都满足KKT条件，那么遍历整个训练集，2)第二个变量的选择SMO外层循环中已经找到第1个变量，现在要在层循环中找第2个变量。第2个变量的选择的标准是希望能使有足够大的变化(这样新的α1也会有足够大的变化，那么选择最大的Ei作为E2；(为了节省时间，将所有的Ei值保存在一个列表中)；在特殊情况下，如果层循环通过以上方法选择的不能使目标函数有足够的下降，那么采用以下启发式规则继续选择；遍历在间隔边界上的支撑向量点，依次将其对应的变量作为试用，直到目标函数有足那么选择最大的Ei作为E2；(为了节省时间，将所有的Ei值保存在一个列表中)；在特殊情况下，如果层循环通过以上方法选择的不能使目标函数有足够的下降，那么采用以下启发式规则继续选择；遍历在间隔边界上的支撑向量点，依次将其对应的变量作为试用，直到目标函数有足过3)计算阈值b和差值E1=yjαjKj1+bold−y1+αldy1K11+αldy2K21aKKT知:E1+y1−∑=3aKKT知:y1(αiyiK(xi∙x1)+b)=1i=1αiyiK(xi∙x1)+b=y1i=1=−(∙)=−(∙)−−=y1−αiyiK(xi∙x1)=bew+αewy1K11+αewy2K21i=3带入(f)，得出b).如果=时，由KKT条件可知:Ny1(∑αiyiK(xi∙x1)+b)≥1Ni=1y1(αiyiK(xi∙x1)+αewy1K11+αewy2K21+b)≥1i=3理理范文范例指导参考带入(f)，得出y1(E1+y1−αldy1K11−αldy2K21−bold+αewy1K11+αewy2K21+bnew)≥1y1(bnew−bold+E1+y1+y1K11(αew−αld)+y2K21(αew−αld))≥1≥(−−(−)−(−))≥(−−(−)−(−))Ny1(∑αiyiK(xi∙x1)+b)≤1i=1Ny1(∑αiyiK(xi∙x1)+αewy1K11+αewy2K21+b)≤1i=3带入(f)，得出y1(E1+y1−αldy1K11−αldy2K21−bold+αewy1K11+αewy2K21+bnew)≤1y1(bnew−bold+E1+y1+y1K11(αew−αld)+y2K21(αew−αld))≤1≤(−−(−)−(−))2≤(−−(−)−(−))2如果<<或<<，那么取=或；(可以证明两者相等)；或，那么==或，这种情况应该排除；在每次完成两个变量的优化后，还必须更新对应的值，并将它们保存在列表中，值得更新要用到bnew值，以及所有支撑向量对应的