SVM理论与算法分析.docxVIP

硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：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表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面，解唯一。一、模型推导1.函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面wx+b=0确定的情况下，|wx+b|能够相对地表示（注意：真实距离为|wx+b|w）点x距离超平面的远近。而wx+b的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用标量ywx+b来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面w,b关于样本点xi，yi的函数间隔为：i=yiwxi+b超平面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,Nyiwwxi+bw3.间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大的确信度将它们分开。因此所要优化的问题 表示为：maxw,b s.t. yiwwxi+bw, i=1,2,N改写为，maxw,b ws.t. yiwxi+b, i=1,2,N的取值不影响最优化问题的解（如果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）支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即1-yiwxi+b=0，对于正例点，支撑向量在超平面wxi+b=1上，对于负例点，支撑向量在超平面wxi+b=-1上，没有实例点落在这两个平行的超平面（间隔边界）之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w，等于2w。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入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=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=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的特征点，即支撑向量（因为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尽量小即间隔尽量大，同时使的误分类的点的个数尽量小，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=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-(h)i*0, i=1,2,N-(i)由(a)求得w*=i=1Ni*yixi由（c）、（e）、（i）得出C-i*i*=0C-i*0再结合（f）得出如果i*0，那么yiw*xi+b*-1+i*=0；如果i*=0，yiw*xi+b*-1+i*不确定；-（k）由(j)，(k)得出如果0i*C，那么i*=0，yiw*xi+b*-1+i*=0，因此yiw*xi+b*=1；b*=yk-j=1Nj*yjxjxi由(j)，(g)得出如果i*=0，那么i*=0，yiw*xi+b*1；这说明xi位于间隔边界上或以外；由(j)，(k)得出如果i*=C，那么yiw*xi+b*=1-i*，i*0；此种情况下，进一步讨论：如果i*=0，那么xi在间隔边界上；如果0i*1，那么xi在分离超平面误分一侧；因此可以看出，软间隔的支撑向量（i*0）xi或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。3.支撑向量的另一种解释最小化以下目标函数：i=1N1-yiwxi+b+w2第一项是经验损失或经验风险，函数称为合页损失函数Lywx+b=1-yiwxi+b+，下标“+”表示以下取正值得函数。z+=z0 z0z0 也就是说，当样本点被正确分类且函数间隔大于1时，损失函数为0，否则（xi为支撑向量时）损失函数是1-yiwxi+b，第二项是系数为的w的L2范数，是正则化项；这两种优化是等价的（通过变量替换方法）；非线性支撑向量机对于分类问题是非线性的（线性模型无法将正负实例正确分开），可以利用核技巧，进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。用线性分类方法求解非线性分类问题问题分两步：首先使用一个变换将原空间的数据映射到新空间；然后再新空间里用线性分类学习方法从训练数据中学习分类模型；核技巧应用到支持向量机，其基本思想：通过一个非线性变换将输入空间（欧氏空间Rn或离散集合）对应于一个特征空间（希尔伯特空间H），使得在输入空间Rn中的超曲面模型对应于特征空间H中的超平面模型（支撑向量机），这样分类问题的学习任务通过在特征空间中求解线性支撑向量机就可以完成。一、非线性支撑向量机在线性支撑向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的內积，如果把这个內积xixj看作是希尔伯特空间中的两个特征的內积xi xj=Kxi,xj=xixj，其中xi=xi，xj=xj，那么对于在低维线性不可分的样本集xi，i=1,2,N，如果通过映射变换到高维希尔伯特空间xi，i=1,2,N变得线性可分（假设能找到这样的合适的映射），那么就可以使用核函数Kxi,xj代替计算xixj，这里xi，xj未知，但xi，xj，Kxi,xj已知。使用核函数后的对偶问题的目标函数成为：W=12i=1Nj=1NijyiyjKxixj-i=1Ni最优解成为w*=i=1Ni*yixib*=yk-j=1Nj*yjKxjxi分类决策函数成为fx=signi=1Ni*yiKxix+b*在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。二、核函数方法核函数：设X是输入空间（欧氏空间Rn的子集或离散集合），H为特征空间（希尔伯特空间），如果存在一个从X到H的映射，x:XH使得对所有x,zX，函数Kx,z满足条件Kx,z=xz则称Kx,z为核函数，x为映射函数，xz为x和z內积；（希尔伯特空间是完备化的內积空间，其中的每个元素是一个向量（可以无穷维），向量之间定义有內积运算，且空间关于內积诱导出的范数是完备的）核技巧的想法是：在学习与预测中只定义核函数Kx,z，而不显示地定义映射函数，因为通常直接计算Kx,z比较容易，而通过x和z计算Kx,z并不容易。注意，x是输入空间Rn到特征空间H的映射，特征空间H一般是高维的，甚至是无穷维的。我们需要的是特征空间中两个特征的內积结果，而不是特征的表示。如果我们能通过简单的函数Kx,z得到xz的內积，那就简化了问题，不用考虑的形式，这正是核函数的妙用之处。对于给定的核函数Kx,z，特征空间H（希尔伯特子空间）和映射函数的取法不唯一，因为核函数给出的是映射后的內积结果，所选取的映射过程可能是不同的。核函数判定定理：设K：XXR是对称函数，则Kx,z为正定核函数的充要条件是对任意xiX，i=1,2,m，Kx,z对应的Gram矩阵:K=Kxi,xjmm是半正定的。对于一个具体函数Kx,z来说，检验它是否为正定核函数并不容易，因为要去对任意有限输入集验证K对应的Gram矩阵是否为半正定。在实际问题中往往应用已有的核函数。常用核函数：（1）多项式核函数：Kx,z=xz+1p,对应的支撑向量机是一个p次多项式分类器；（2）高斯核函数：Kx,z=exp-x-z222，对应的支撑向量机是高斯径向基函数分类器；-（3）字符串核函数：1）基本定义：有限字符表;字符串s：s1s2s|s|, 字符串s的长度|s|，空字符串长度为0；字符串连接：st，s和t分别是字符串；长度为n的字符串集合n;所有字符串的集合：*=n=0n;s的子串u：给定一个指标序列i=i1,i2,i|u|,1i1i2|u|。2）映射定义：假设S是长度大于或等于n字符串的集合，s是S的元素，建立字符串集合S到特征空间Hn=Rn的映射ns，Rn表示定义在n上的实数空间，其每一维对应一个字符串un，映射ns将字符串s对应于空间中Rn的一个向量，其在u维上的取值为nsu=i:si=uli，这里，0HL2new，uncH2new，uncL由y11new+y22new=y11old+y22old得出y1y11new+y22new=y1y11old+y22old1new=1old+y1y22old-2new（2）变量的（启发式）选择方法： SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。1）第一个变量的选择SMO称选择第1个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量。具体地，检验训练样本点xi，yi是否满足KKT条件，即（具体推导见软间隔SVM文章）如果i*=0，那么i*=0，yiw*xi+b*1；如果0i*C，那么i*=0，yiw*xi+b*-1+i*=0，因此yiw*xi+b*=1；如果i*=C，那么yiw*xi+b*=1-i*，i*0；i=0yij=1NjyjKxjxi+b10iCyij=1NjyjKxjxi+b=1i=Cyij=1NjyjKxjxi+b1该检验是在范围内进行的。在检验过程中，外层循环首先遍历所有满足条件0iC的样本点，即在间隔边界上的支撑向量点，检验它们是否满足KKT条件；如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足KKT条件；2）第二个变量的选择SMO称选择第2个变量的过程为内层循环。假设在外层循环中已经找到第1个变量1，现在要在内层循环中找第2个变量2。第2个变量的选择的标准是希望能使2有足够大的变化（这样新的1也会有足够大的变化，从而尽快趋向满足KKT条件的值）。从上面的推导中可以发现，2new依赖于|E1-E2|，为了加快计算速度，一种简单的做法是选择2，使其对应的|E1-E2|最大。因为1已定，E1也是确定的。如果E1是正，那么选择最小的Ei作为E2；如果如果E1是负，那么选择最大的Ei作为E2；（为了节省时间，将所有的Ei值保存在一个列表中）；在特殊情况下，如果内层循环通过以上方法选择的2不能使目标函数有足够的下降，那么采用以下启发式规则继续选择2；遍历在间隔边界上的支撑向量点，依次将其对应的变量作为2试用，直到目标函数有足够的下降。若找不到合适的2，那么遍历训练数据集；若仍找不到合适的2，则放弃第1个1，再通过外层循环寻求另外的1。3）计算阈值b和差值Ei每次完成两个变量的优化后，都要重新计算阈值b和Ei，使用迭代的方法更新b；根据定义预测误差 E1=j=1NyjjKj1+b-y1，展开得E1=j=3NyjjKj1+bold-y1+1oldy1K11+2oldy2K21E1+y1-j=3NyjjKj1=1oldy1K11+2oldy2K21+bold-（f）下面讨论如何迭代更新b，即获得bnew：显然每次更新完1new，2new后bnew的选择应该使得KKT条件成立；a).如果01newC时，由KKT条件可知:y1i=1NiyiKxix1+b=1i=1NiyiKxix1+b=y1b1new=y1-i=1NiyiKxix1=y1-i=3NiyiKxix1-1newy1K11-2newy2K21y1-i=3NiyiKxix1=b1new+1newy1K11+2newy2K21带入（f），得出E1+b1new+1newy1K11+2newy2K21=1oldy1K11+2oldy2K21+boldb1new=bold-E1-y1K111new-1old-y2K212new-2old- -（g）同样，如果02newC，那么b2new=bold-E2-y1K121new-1old-y2K222new-2old-（h）b).如果1new=0时，由KKT条件可知:y1i=1NiyiKxix1+b1y1i=3NiyiKxix1+1newy1K11+2newy2K21+b1带入（f），得出y1E1+y1-1oldy1K11-2oldy2K21-bold+1newy1K11+2newy2K21+bnew1y1bnew-bold+E1+y1+y1K111new-1old+y2K212new-2old1y1bnewy1bold-E1-y1K111new-1old-y2K212new-2old同样，如果2new=0时，那么y2bnewy2bold-E2-y1K121new-1old-y2K222new-2oldC).如果1new=C时，由KKT条件可知:y1i=1NiyiKxix1+b1y1i=3NiyiKxix1+1newy1K11+2newy2K21+b1带入（f），得出y1E1+y1-1oldy1K11-2oldy2K21-bold+1newy1K11+2newy2K21+bnew1y1bnew-bold+E1+y1+y1K111new-1old+y2K212new-2old1y1bnewy1bold-E1-y1K111new-1old-y2K212new-2old同样，如果2new=C时，那么y2bnewy2bold-E2-y1K121new-1old-y2K222new-2old综上可以得出结论：如果01newC或02newC，那么取bnew=b1new或b2new；（可以证明两者相等）；否则如果1new=2new=0或C，那么1old=2old=0或C，这种情况应该排除；因此1new2new，如果1new, 2new中一个是0，另一个是C，那么b1new和b2new以及它们之间的数都是符合KKT条件的阈值，这时选择它们的中点作为bnew；在每次完成两个变量的优化后，还必须更新对应的Ei值，并将它们保存在列表中，Ei值得更新要用到bnew值，以及所有支撑向量对应的j：Einew=S