半监督学习的流形总则化改进算法

半监督学习的流形总则化改进算法

0半监督学习过程事实上，收集无标记样本比收集有标记样本更简单。如果把有标签样本和无标签样本共同作为学习的样本集合,这种学习就是半监督学习。在模式识别的方法中,如果能够利用无标签数据的学习来提高识别性能,将具有更好的实用性。文献在全局风险最小化(OverallRiskMinimization,ORM)下引入了半监督支持向量机(S3VM),与传统的支持向量机(SupportVectorMachine,SVM)相比,在性能上有了明显的提高,但它的求解计算却十分复杂,尤其不便于新数据的加入。目前最主要的研究成果是直推式支持向量机(TSVM),该算法是在半监督学习问题上的一种扩展,但它存在训练速度慢、回溯式学习多、学习性能不稳定,主要针对分类问题等缺点。文献提出了一种改进算法PTSVM,通过成对标注和标记重置的办法改进了TSVM的性能,但其计算相对复杂,且主要针对分类问题。文献中提到了流形正则化的一种算法,此算法比TSVM算法在学习性能上又进了一步,但是从文章中可以看出,该算法也主要针对分类问题。目前,很多研究都在分类问题上都取得了进步,但对于回归问题的研究相对较少。本文提出了一种流形正则化算法,主要针对半监督学习中的回归问题,有效解决了传统TSVM中过多的回溯式学习问题,与支持向量回归相比,该算法在学习精度上有明显提高,即使输入数据带有噪音时,也能表现其优越性。1传统正则化因子ty为了简单起见,假定回归模型的输出为一维,其实这并不失一般性。给定包含l个由输入和输出组成的训练集:(xi,di)(i=1,…,l,di∈R)。对于线性模型y=f(x)=b-wTx,传统的正则化方法认为,当xi∈Rn时:f=argminy∈l2l∑i=1ϕi(di-yi)+δ⋅yΤy/2(1)f=argminy∈l2∑i=1lϕi(di−yi)+δ⋅yTy/2(1)其中,y=(y1,y2,…,yl)T,yl=f(xl)为模型的输出;而l∑i=1ϕi(di-yi)∑i=1lϕi(di−yi)为惩罚项,ϕi(·)为非负的一元凸函数,δ·yTy/2为传统正则化项,δ为yTy的传统正则化因子。由半监督学习理论,样本点(xi,di)(i=1,2,…,l)为已知的,而对于xi(i=l+1,l+2,…,L),其目标值di是未知而需要求解的。这种情况下,根据流形正则化理论,在高维空间中,数据一般被认为是嵌在低维的流形上的,特别是在输入数据维数比较高的情况下。根据维数灾理论可以知道,样本在高维总是非常稀疏的,这样要达到理想的泛化效果,就有必要使用流形上的正则化项,即在式(1)的基础上加入式(2):wΤw/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2(2)wTw/2+a/2∑i=1L∑j=1Lhij(yi−yj+wT(xi−xj))2(2)其中,hij为样本xi和xj相邻程度,比如,如果j∈Ni,Ni是和xi相邻的K个最近样本点的集合,那么hij可以有三种取值情况:1)hij=1;2)hij=exp(-‖xj-xi‖2/σ);3)hij=1/‖xj-xi‖2;否则hij=0。a为流形上的正则化因子。那么我们的优化目标是:f=argminywΤw/2+δ⋅yΤy/2+a/2+L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1ϕi(di-yi)(3)f=argminywTw/2+δ⋅yTy/2+a/2+∑i=1L∑j=1Lhij(yi−yj+wT(xi−xj))2+∑i=1lϕi(di−yi)(3)其中,y=(y1,y2,…,yl,yl+1,…,yL)T,这时yi+wTxi=b,其中b为一常数,i=1,…,l一般不再成立。可以看到,a充分大的时候,(x,y)在y+wTx=b的超平面上;a较小的时候,则(x,y)在y+wTx=b的平面上上下波动。需要特别说明的是,在建立最终的优化目标中,由于利用已知的有限样本数据来估计潜在的未知流形,估计的结果很难完全准确,这样在式(3)中加入传统的正则化项是完全有必要的。式(3)的优化问题是一个严格凸优化的问题,因此存在全局唯一最小点,这样就避免了存在局部最小等问题。2矩阵求取基本参数下面使用最小化目标函数式(3)来求解半监督学习的问题,以达到整个算法的实现和求解最终结果的目的。为了在推导过程中方便使用对偶定理,可以引入变量ξi,使得di-yi=ξi,其中i=1,2,…,l。这样目标函数变为等式约束下的优化问题:f=argminywΤw/2+δ⋅yΤy/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1ϕi(ξi)(4)s.t.di-yi=ξi;i=1,2,⋯,lf=argminywTw/2+δ⋅yTy/2+a/2∑i=1L∑j=1Lhij(yi−yj+wT(xi−xj))2+∑i=1lϕi(ξi)(4)s.t.di−yi=ξi;i=1,2,⋯,l其中,y=(y1,y2,…,yl,yl+1,…,yL)T。由式(4),利用Lagrange乘子法可得:L(w,y,λ)=wΤw/2+δ⋅yΤy/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1ϕi(ξi)+l∑i=1λi(di-ξi-yi)=12zΤ[(Ι00δ⋅Ι)+a⋅(XΙ)V(XΤΙ)〗z-zΤμ+L(w,y,λ)=wTw/2+δ⋅yTy/2+a/2∑i=1L∑j=1Lhij(yi−yj+wT(xi−xj))2+∑i=1lϕi(ξi)+∑i=1lλi(di−ξi−yi)=12zT[(I00δ⋅I)+a⋅(XI)V(XTI)〗z−zTμ+l∑i=1λidi+l∑i=1(ϕi(ξi)-λiξi)(5)∑i=1lλidi+∑i=1l(ϕi(ξi)−λiξi)(5)其中:z=(wy)X=(x1,x2,⋯,xL)V=L∑i=1L∑j=1(ei-ej)hij(ei-ej)Τλ=(λ1,λ2,⋯,λl)Τμ=(0,⋯,0,nλ1,⋯,λl,0,⋯,0L-1)Τz=(wy)X=(x1,x2,⋯,xL)V=∑i=1L∑j=1L(ei−ej)hij(ei−ej)Tλ=(λ1,λ2,⋯,λl)Tμ=(0,⋯,0,nλ1,⋯,λl,0,⋯,0L−1)TI表示单位矩阵,它的位数根据上下文确定,后面所出现的I也类似。记H=(hij),则V=diag(He)+diag(HTe)-H-HT,其中e=(1,…,1)T:A=(Ι00δ⋅Ι)+α(XΙ)V(XΤΙ)(6)这时式(5)转化为:L(w,y,λ)=12zΤAz-zΤμ+l∑i=1λidi+l∑i=1(ϕi(ξi)-λiξi)(7)L(λ)=-12μΤA-1μ+l∑i=1λidi-l∑i=1ϕ*i(λi)其中,ϕ*i(·)为ϕ(·)的共轭,即ϕ*i(λi)=minξiλiξi-ϕi(ξi)利用矩阵求逆引理:(A+BC)-1=A-1-A-1B(I+CA-1B)-1CA-1,对式(6)中A可得:A-1=(1-δ⋅XCXΤ-XC-CXΤB)其中:B=1δ(Ι-C)C=V((δ/a)⋅Ι+δ⋅XΤXV+V)-1(8)注意到μ=(0,…,0,λT,0,…,0)T前面的n个分量为零,这样对偶优化问题可以写为:L(λ)=-12λΤB(1:l,1:l)λ+l∑i=1λidi-l∑i=1ϕ*i(λi)其中,B(1:l,1:l)表示取矩阵B的前l阶主子矩阵,即前l行和前l列构成的矩阵。注意B=((1/a)·I+XTXV)((δ/a)·I+δ·XTXV+V)-1,这样在计算时可以避免溢出的问题。由式(8)可以看出,C的计算仅仅需要两个样本的内积。这样就可以利用在支持向量机中使用的核函数技术或者称为核技巧,将原始输入空间的样本x映射到高维甚至无穷维的特征空间得到ψ(x),然后使用核函数的方法,使得K(xi,xj)=(ψ(xi),ψ(xj)),其中(·,·)表示特征空间中的两个向量的内积。本文使用的是Gauss核函数K(xi,xj)=exp(-‖xi-xj‖2/ρ2),其中ρ为Gauss核参数。至于其他有关核函数的理论可以参考文献。不妨记为B(1:l,1:l)=D-L-LT=D-G,其中,D表示对角矩阵,而L和LT表示为下三角部分和上三角部分,G=L+LT。这时我们设计的优化算法为:λ(t+1)=φ(G·λ(t)+d)或者写成分量形式有:λi(t+1)=φi(di+l∑j=1,j≠igijλj(t));i=1,2,…,l而φi(ζ)=argmaxλ{λζ-(12diiλ2+ϕ*i(λ))},那么现在针对于回归问题再继续讨论:ϕi(ξ)为常用的支持向量回归的ε-不敏感误差损失函数:ϕ(ξ)ε={|ξ|-ε,|ξ|>ε0,|ε|≤ε其中ε>0。然后经过一些列的演算,可以得到迭代时的函数φi(ζ)如下:φ(ξ)ε={0,|ζ|≤ε(ζ-ε)/dii,ζ>ε(ζ+ε)/dii,ζ<ε其中dii是D的对角线上第i个元素。在求出λ之后,令η=(λ1,⋯,λl,0,⋯,0L-l)Τ有w=-XCη,y=(1/δ)η-(1/δ)Cη,求得实际输出值。经过以上推导,算法步骤如下:1)输入带已知输出的样本点(xi,di)(i=1,2,…,l)和不带已知输出的数据xi(i=l+1,l+2,…,L),记X=(x1,x2,x3,…,xL)。2)求X的相邻矩阵hij,H=(hij),V=diag(He)+diag(HTe)-H-HT,e=(1,…,1)T。3)求B=((1/a)·I+XTXV)((δ/a)·I+δ·XTXV+V)-1,其中Kij=K(xi,xj),然后取B矩阵的前l行和前l列得B(1:l,1:l)=D-L-LT=D-G,其中,D表示对角矩阵,而L和LT表示为下三角部分和上三角部分,G=L+LT。4)在时刻t,对i=1,2,…,l,依次计算λi(t+1)=φi(di+l∑j=1,j≠igijλj(t)),利用迭代计算出λ每一个分量。然后对于最终求得的λ=(λ1,λ2,…,λl)T,根据η=(λ1,⋯,λl,0,⋯,0L-l)Τ,求得η。5)根据y=(1/δ)η-(1/δ)Cη,求得最终的学习结果。3试验结果主要针对回归问题进行试验,根据以上的算法步骤,以Matlab为试验平台,可以直观地看到试验结果,以便证实本算法的可行性、有效性及其优越性。为了使试验具有说服力,同时还采用网上通用的SVM工具箱(SVM_SteveGunn)作为支持向量机的试验工具,并且选择与本算法相同的参数。3.1求相邻矩阵时的-不敏感误差损失的函数,如果以较低的方式计算其为了输入直观,先选取嵌入在二维空间中的y=x3一维流形上的采样作为输入样本点,选取函数z=1/(x2+y2+1)+γ·n(其中y=x3,n为噪音项,称γ为噪音系数)作为输出,输入点(x,y)就在y=x3这个一维的流形上。其中噪音项n是均值为0,方差为1的正态分布上的随机向量(下文提到的噪音项n与此相同)。选取γ=0.02,已知样本点x的取值范围在-1和1之间且间隔0.02,未知样本点的取值范围在-0.99和0.99之间且间隔0.04。选取相邻矩阵hij=exp(-‖xj-xi‖2/σ),σ=5;求C时使用的Gauss核参数ρ=0.1,δ=0.005,a=10;求函数φi(ζ)时使用的ε-不敏感误差损失函数,其中ε=0.005。如图1,实线为期望输出曲线,实心圆点为SVM学习后的输出曲线,空心方块为本算法学习后的输出曲线。很明显,输出具有噪音时,学习后的曲线也能较好地达到期望输出效果,从图1中也可以看到本算法的学习精度要高于SVM的学习精度,并且经过计算,此算法的相对误差为0.83%,而使用SVM的相对误差为3.62%。图2表示为求φi(ζ)时使用ε-不敏感误差损失函数中的ε,在有噪音和无噪音时对平均误差的影响。在有噪音的图2(a)中,ε很小或稍大,平均误差都会增大,此时ε不能取零;而无噪音时如图2(b),ε取得越小越好,此时ε可以取零。在图3(a)中,随着噪音的增加,平均误差是逐渐增加的,没有突变的发生,那么我们认为该算法具有较强的抗干扰能力。图3(b)为求相邻矩阵H时用到的σ对平均误差的影响。在本文算法推导中已经介绍hij的三种取值情况,从图中可以看到随着σ的增大,hij的取值很快退到第一种情况,达到了理想的效果。由此可见,在文献中提到的基于选择第二种邻域函数所得到的结论,在回归问题中并不适用。本文算法是对文献相关内容的一个改进。3.2svm的输出函数为c.n,为2.在上一个试验中,输入数据位于一个严格的一维流形上,但在很多实际应用中,输入数据本身是带有噪音的,这些输入就不一定严格在一个流形上,这时选取x=sin(θ)+β·n,y=cos(θ)+β·n作为二维输入,其中n为噪音项,β为噪音系数,θ为参数。已知样本点的θ取0到2π之间间隔0.04的值,未知样本点的θ取-π到π之间,间隔0.04的值,β=0.02。选取输出函数z=1/(x·y+1)+γ·n(n为噪音项,γ为噪音系数),γ=0.03。选取相邻矩阵hij=exp(-‖xj-xi‖2/σ),σ=3;求C时使用的Gauss核参