迭代算法（精选8篇）
迭代算法 篇1
1 CORDIC迭代算法简介
CORDIC[1,2]主要应用于直角坐标与极坐标的数值相互转换,其在特征值,快速傅里叶运算[3]的定点运算[4,5]有重要意义。CORDIC迭代算法的基本原理如图1所示:
初始向量V0逆时针旋转角度θ后得到向量V1,则V0与V1存在数学关系(1):
在实际的工程应用中,所有浮点数据都需要转化为二进制数据在计算机处理,为方便运算取每一次旋转的角度θi正切值为2的倍数,即θi=tan-1(2-i),则迭代运算式可以表示为公式(2):
其中di表示矢量旋转的方向,取-1表示朝逆时针方向旋转,取1表示朝顺时针方向旋转。很多研究已经证明,对于迭代次数大于6的CORDIC运算,基本收敛于一个常数,这样上式的运算在计算机处理中就可以用简单的加法和移位来实现了。简写迭代公式并引入角度分量可以得到公式(3):
其中i=0,1……N-1,N为最大迭代循环数;arctan(2-i)=θ(i),迭代完成后需要在X,Y上分别乘上KN。整个旋转过程可以表示为一系列与旋转角度集相关的角度不断偏摆,从而不断逼近所需旋转角度的循环迭代过程。这样CORDIC算法基本上可以实现数学运算中所需的函数运算。
2 两种模式迭代算法
CORDIC算法最初主要用于平面直角坐标系(X,Y)和极坐标系(R,θ)之间的自由坐标变换,其迭代算法有两种操作模式:旋转模式迭代[6]和向量模式迭代[7]。旋转模式为将极坐标数据转换为直角坐标数据,而向量模式则将直角坐标的数据转换为极坐标数据。
2.1 旋转模式
旋转模式下,设定初始值(X0,Y0)=(R,0),Z0=θ,dn=sign(Zn),,当N→∞时,Zn→0。经过n次迭代后的三个累加器结果
由等式(4)得到极坐标系(R,θ)到平面直角坐标(X,Y)的转换。由于迭代只支持第一象限的转换,为支持四个象限的矢量都能转换到平面直角坐标,需要将初值转换到第一象限。其原则是根据表1进行初值变换,转换到第一象限。
旋转模式迭代流程如图2:首先设置好初始值,随后更新迭代次数n,根据公式更新Xn,Yn,dn以及Zn的值,这里更新Zn的值需要查表法来计算。接着可以根据Zn的值与门限阀值比较,如果Zn小于或者等于门限阀值,则停止迭代。当然这里也可以设置迭代次数,当迭代次数达到设置的值后,强行停止迭代。完成迭代后,Xn与Yn分别乘以Kn,更新得到极坐标对应的数据。
2.2 向量模式
向量模式是将平面直角坐标的数转换为极坐标的数,在向量模式下,首先设定初始值(X0,Y0),Z0=0,,当N→∞时,Yn→0。经过n次迭代后的三个累加器结果
由此得到平面直角坐标(X,Y)到极坐标系(R,θ)的转换。向量模式算法实现流程如图3,同样为在向量模式下支持四个象限的平面直角坐标都能转换到极坐标,当X0<0,需要多重复两次i=0的迭代运算。开始迭代流程如下:首先设置好初始值,随后更新迭代次数n,根据公式更新Xn,Yn,dn以及Zn的值,同样这里更新Zn的值需要查表法来计算。与旋转模式一样在这里更新Zn的值需要查表法来计算。但与旋转模式不一样,向量模式里迭代次数是根据Yn的值与门限阀值比较,如果Yn小于或者等于门限阀值,则停止迭代。当然这里也可以设置迭代次数,当迭代次数达到设置的值后,强行停止迭代。完成迭代后,Xn与Yn分别乘以Kn,更新得到直角坐标对应的数据。
3 仿真与结论分析
在进行CORDIC定点算法仿真前,首先需要建立一个查找表如2(LUT)存储角度值θ(i)。下表以定点位宽N=14为例,在旋转模式下进行不同迭代次数仿真。
CORDIC为移位相加算法,每一次迭代需要两次移位(2-i),一次查找表(查θ(i)),三次加法(di为符号系数)。
对CORDIC算法来说,一个粗略的精度估计为:K位精度需要K次迭代[8]。图4对不同迭代结果的误差进行了对比。从仿真结果可发现,14位精度的定点运算,迭代10次到12次,运算误差都在千分之一以上。而迭代14次或者15次,误差基本都在千分之一以下,且迭代14次与15次性能大部分点重合。因此在保证CORDIC定点性能前提下,最小迭代次数可以选择与精度位数相同的次数进行迭代。
4 结束语
从算法流程可知,快速傅里叶蝶形算法中旋转因子计算中,ROM不直接存储旋转因子的值,而是存储少量的单位旋转角度值,再通过CORDIC流水线循环迭代,得到所需的旋转角度值θ;无需复数乘法器,每步运算可分解为简单的移位、相加来完成;为了保证CORDIC计算精度,需要考虑旋转因子位宽与迭代次数关系,如果迭代次数多大,影响CORDIC运算的复杂度,次数不足,则影响CORDIC运算的精度。本文仿真验证了迭代次数与位宽的关系。当然后续也可以利用门限阀值对迭代性能做进一步研究。
摘要：在实际的工程应用中,经常需要计算角度的三角函数运算,比如计算流水线型快速傅里叶变换处理器蝶形运算中的旋转因子,采用CORDIC迭代加法器,性能与直接采用乘法器相比性能损失很小,但可以大大节约数字面积。CORDIC的定点化运算中,迭代次数是算法的重要指标之一,其关系到算法的复杂度及计算误差。算法迭代次数与要求的数据精度相关,该文将实现CORDIC算法的旋转模式,利用迭代不同次数得到的值与精确值的误差进行比较来确定CORDIC算法需要进行的迭代次数。这样在节约计算量的同时,保证计算精度不受较大影响,从而在节约计算量的前提下保证CORDIC算法的性能。
关键词：CORDIC,定点化算法,旋转模式,向量模式
参考文献
[1]Andraka R.A Survey of Cordic Algorithms for FPGA BasedComputers[C].Proceedings of the ACM/SIGDA 6th Internation-al Symposium on Field Programmable Gate Arrays(FPGA'98),1998.
[2]耿丹.CORDIC算法研究与实现[J].论文与技术报告:2007(S1):39-40.
[3]彭清兵,李方军.基于CORDIC算法的FFT处理器设计[J].工程应用技术与实现,2011(23):208-209.
[4]孙明革,陈靖.CORDIC算法在定点DSP中的应用[J].吉林化工学院学报,2012(5):61-62.
[5]Martin Uhlmann,Keshab K P.A high-speed CORDIC algo-rithm and architecture for DSP application[J].IEEE,2005,52:1-5.
[6]Granado J,Torralba A,Chavez J,et al.Optimization ofCORDIC cells in the backward circular rotation mode[J].AEU-International Journal of Electronics and Communications,2007,61:337-340
[7]王建军,徐力,安鹏.基于CORDIC的频偏估计幅角计算算法[J].技术与方法,2014(7):77-78.
[8]梁源,王兴华.一种基于贪婪算法的CORDIC改进算法[J].电讯技术,2014(3):313-314.
迭代算法 篇2
Monte-Carlo统计迭代图像重建算法
线性衰减系数图像重建是层析γ扫描(TGS)的一个核心问题.本文从粒子输运方程出发,应用Monte-Carlo方法,提出了一种基于Monte-Carlo方法的`统计迭代图像重建算法.模拟结果表明,与一般TGS图像重建算法相比,该重建算法的重建图像误差大为减小,能够满足TGS装置的要求.
作 者：张全虎 隋洪志 吕峰 李泽 作者单位：中国原子能科学研究院,放射化学研究所,北京,102413 刊 名：原子能科学技术 ISTIC EI PKU英文刊名：ATOMIC ENERGY SCIENCE AND TECHNOLOGY 年，卷(期)： 37(6) 分类号：O242.2 关键词：层析γ扫描 线性衰减系数 Monte-Carlo方法 图像重建 迭代法观测迭代的插值滤波算法 篇3
虽然卡尔曼滤波器(KF)能够很好的处理线性滤波问题。然而在现实世界中我们所面对的问题大多是非线性问题。为解决非线性滤波问题,众多学者进行了大量的研究并取得了不少的成果。在众多研究成果中较为典型的算法有扩展卡尔曼滤波器(Extended Kalman filter),Unscented卡尔曼滤波(Unscented Kalman filter),基于Bayes理论的粒子滤波器(Particle filter),和基于Stirling,s内插公式的插值滤波器(DDF)。
EKF简单容易实现特点使其被大量应用到现实工程中,但EKF实现性差,估计精度差的缺点限制了其进一步的应用。PF算法虽然有着较高的跟踪精度但其庞大的计算量和粒子退化问题限制其在现实工程应用。2000年由Magnus Nrgaard等人提出的DDF算法,该算法和EKF相类似:算法简单,容易实现。但与EKF相比DDF采用Stirling插值公式进行线性化处理,避免了求解微分应算过程,在非线性程度较高的系统中DDF的跟踪精度要好于EKF。
但标准DDF算法被应用到初始化误差大或弱观测性条件下的非线性系统,常出现收敛速度慢,稳定性不足及跟踪精度低等问题。为此本文对一阶DDF算法上进行改进。在一阶DDF观测更新过程中加入迭代过程取代近似条件估计用于量测预测数据更新。仿真结果表明该算法在大噪声,及初始误差较大的情况下有着更优的跟踪精度和收敛速度。
1插值滤波器
考虑如下非线性系统∑:
其中xk∈ℜn为n×1状态向量,yk∈ℜm为m×1观测向量。wk∈ℜq为q×1过程噪声,而vk∈ℜr为r×1观测噪声。并假设噪声序列均为高斯白噪声其均值和方差为:
DDF算法和EKF十分的相似,不同的是DDF采用Stirling插值公式对系统进行线性化处理而非泰勒公式,从而避免了求解Jacobin矩阵,在状态数据更新上和EKF完全一样,只是在对协方差进行更新的时候可以采取更为简单的方法:通过更新协方差的平方Cholesky因子来完成。DDF算法如下描述:
计算平方Cholesky因子:
其中Sx为x的协方差0P的平方Cholesky因子,Sw为过程噪声w的协方差Q的平方Cholesky因子,Sv为量测噪声v的协方差R的平方Cholesky因子。
sx,p表示为Sx的第p列,相同的定义其他几个因子则有下面等式:
上述式子中h为一区间长度参数在高斯环境下一般有h=3,xk+1为预测状态向量有下述式子计算得到:
Sx-(k+1)为平方Cholesky因子由(10)进行通过Householder三角变换转换得到:
量测数据更新:
Sv(k+1)也需要进行通过Householder三角变换转换。
则量测和状态的相关矩阵为:
计算增益进行数据更新:
在对协方差更新上注意到式子(9),(10),(12),(13)及(14)之间的关系则在协方差更新中有:
所以使用协方差的平方Cholesky因子(可以由(19)通过Householder三角变换转换得到)更新来取代协方差进行更新可以简化计算。
上述即为DDF算法,详细的推导过程可以参见文献。
2迭代内插滤波器
2.1观测迭代
DDF和EKF一样,在量测预测更新上由ˆy(k|k-1)=g(ˆx(k|k-1),k)得到,这样就由于使用ˆx(k|k-1)来代替x(k)从而无法避免的引入了对观测的误差,同时对非线性量测方程进行内插公式线性化的时候也不可避免的增加了观测的误差。
为了解决上述问题,本文在观测中加入一个迭代过程来取代单纯的近似条件均值估计,用于代替x(k)的xˆk,j通过迭代过程不断的逼近x(k)减小量测预测更新过程的误差,提高算法的鲁棒性及跟踪性能。
式子中的ey,j和ex,j有如下定义
算法通过上述条件不等式来判断xˆk,j是否达到精度要求从而判断是否结束本次迭代。迭代从xˆk,0开始直至满足不等式子要求,或者达到最大迭代次数N结束迭代,进入下一时刻的估计。
2.2 IDDF算法
本算法和DDF算法的最大差别在于量测更新,本算法通过迭代环节减小了量测更新的误差具体如下:
假设系统方程为(1)则:
1.初始化算法参数:j=1,Pk,j=Pk,xˆkj,=xˆk。
2.计算平方Cholesky因子:
3.状态和协方差计算:
4.量测及相关协方差更新:
5.计算增益进行数据更新:
6.定义如下等式:
7.判断是否结束迭代:
如果j≤N下不等式成立,则使j=j+1重复上述算法过程直至不等式不成立或j>N。
8.数据更新:在上述不等式不成立
当不等式于j>N依然成立时取:
上述即为IDDF算法,要注意的是如Sx,j+1等平方Cholesky因子必须要进行Householder三角变换转换。
2.3 IDDF收敛性
假设
由于Pk,j+1,Pk-,j及Pkv,jv为正定,则那么根据(36)式将有
在j=1,2,L<∞下成立。又因为Pk,j+1,Pk-,j的每个元素均有界,所以:
成立。则根据(36),(48)及(49)可以得到:
成立。与(47)矛盾。所以可知假设(47)不成立(50)成立。
假设κk,j→0当j>N时成立,则从(36)及(38)可以知道有:
成立,即说明随着迭代过程,算法是收敛的。和标准DDF算法比较,该算法通过修正量测提高对状态估计的精度,同时在初始化值和最优值相距较远时,算法自动校正状态及协方差矩阵以加快收敛速度。
由于Pk,j+1,Pk-,j及Pkv,jv为正定,则那么根据(36)式将有:
在j=1,2,L<∞下成立。又因为Pk,j+1,Pk-,j的每个元素均有界,所以:
成立。则根据(36),(48)及(49)可以得到:
成立。与(47)矛盾。所以可知假设(47)不成立(50)成立。
假设κk,j→0当j>N时成立,则从(36)及(38)可以知道有:
成立,即说明随着迭代过程,算法是收敛的。和标准DDF算法比较,该算法通过修正量测提高对状态估计的精度,同时在初始化值和最优值相距较远时,算法自动校正状态及协方差矩阵以加快收敛速度。
3仿真实验
假设如下非线性模型:
在上述模型中wk为高斯噪声其方差为Qk=diag⎡⎣0.220.32⎤⎦,时间间隔T=0.2s。xk中的变量分别表示为x方向的位移和速度,y方向的位移和速度。
其中量测包括方向角θk及方向角变化率θ&k,量测方程如下:
其中rk=xk2+yk2,nθk及nθ&k为独立高斯噪声其方差为Rk=diag⎡⎣0.120.82⎤⎦,对上述系统进行M=150独立实验仿真。
均方根误差为:
由下述仿真实验数据可以看出IDDF算法在精度和稳定性上的表现都要比DDF和EKF优秀。
4结论
DDF算法在应对非线性程度高的滤波问题上的不仅在精度上而且在稳定性都要优于EKF。在DDF基础上的改进算法IDDF其精度,稳定性则要好于DDF。IDDF虽然提高了算法的精度及稳定性,但其增加的迭代过程,将加大算法的计算负担。同时对DDF这中改进算法也只适用于高斯噪声的环境,在面对非高斯噪声环境也是无能为力。
摘要：针对非线性跟踪系统中由于弱观测性,大的初始化误差使的系统出现不稳定、跟踪收敛速度慢,鲁棒性能差的问题,本文在内插公式滤波器的基础上提出了基于观测迭代插值滤波器。该算法在插值滤波器基础上,利用观测迭代过程来取代单纯的近似条件估计进行预测,减小观测函数线性化所带来的误差影响具有更精确的状态和协方差估计性能。仿真结果表明该算法在大噪声和大初始化误差条件下拥有比传统算法更高的跟踪精度,和更快的收敛速度。
关键词：非线性滤波,插值滤波器,迭代插值滤波器
参考文献
[1]Kotecha,J.H,Djuric,P.M,Gaussian Particle Filtering[J].IEEE Transactions on Signal Processing.2003.
[2]Julier S J,Uhlmann J K.A New Method for The Nonlinear Transformation of Means and Covariances in Filters and Estimators[J].IEEE Transactions on Automatic Control,2000.
[3]Julier S J,Uhlmann J K.Unscented Filtering and Nonlinear Estimation[J].Proceedings of the IEEE.2004.
[4]袁泽建,郑南宁,贾新春.高斯-厄米特粒子滤波器[J].电子学报.2003.
[5]Ngarrd M,Poulsen N M,Ravn O.New Developments in State Estimation for Nonlinear System[J].Automatica.2000.
迭代重建算法的研究进展 篇4
关键词：CT,辐射剂量,迭代算法,滤波反投影算法,自适应统计迭代重建技术,图像质量
0前言
随着螺旋CT技术的发展,尤其是多层螺旋CT的出现,临床疾病的诊断水平得到了很大的提高,然而辐射剂量对被照射人群存在潜在的危害性也逐渐被人们所关注[1]。有报道指出,全球医疗所致的年人均辐射剂量在过去10~15年里大约增加了1倍,尤其在高度发达的国家这种情况更为突出[2,3]。CT检查被认为是造成医源性辐射最重要的原因[4]。因此,如何在保证图像质量满足临床诊断要求的同时,减少受检者的辐射剂量,已成为当今影像学的一个重要的研究方向。扫描技术参数的优化是以往解决该问题的主要方法[5,6],近年来,重建算法的改进成为CT低剂量研究的一个重要方向。
1 CT图像重建算法的发展
常用的CT图像重建算法主要有两类:解析算法(Analytic Reconstruction,AR)和迭代算法(Iterative Reconstruction,IR)。解析算法具有分辨率高、成像速度快等优点,对采集数据的完备性要求也比较高。在解析算法中,以滤波反投影算法(Filtering Back-Projection,FBP)最具代表性,应用也最为广泛[7]。根据原始数据中的噪声特点,采用滤波函数作用在原始数据上,对整个频域内的信号进行滤波处理,去除易造成噪声和伪影的信息,选择对成像最为重要的信息,通过滤波处理后重建的图像的噪声得到了很大的改善。
自CT被引入临床以来,FBP算法一直都被作为CT图像重建方法的基础和“金标准”[8],但该算法要求投影数据完备并且精确定量,并且该算法易受统计波动的影响,投影数据量如果不足时,重建的图像质量就会明显下降,因此为保证完备的投影数据量以保证能重建出达到临床诊断要求的图像,该算法对CT的辐射剂量也要求较高。此外,FBP算法在数据重建中,对数据采集过程做了很多简化和假定,包括:测量信号无光子统计波动和电子噪音;X射线球管的焦点无穷小点;探测器由位于每个小室中心的点构成;重建的体素也是没有几何形状和大小的无穷小点。由于在重建过程中没有真实还原X射线的采集过程,并且忽略了统计噪声,FBP算法不是一个精确的CT图像重建方法。
迭代算法(Iterative Reconstruction,IR)可以有效地克服FBP算法所固有的问题,迭代算法在CT发展的早期就已经出现,但由于计算量较大,以及早期计算机技术的限制,在很长一段时间内发展停滞不前。近年来,得益于计算机技术的飞速进步,迭代算法重新成为研究的热点。迭代算法的基本原理是:对于某个重建视角,首先在估计的物体图像上通过“前向投影”模拟一个综合投影,这是对沿着该视角的衰减的第一次估计,但存在较大误差。这种估计尽可能地模拟真实CT系统中X射线光子穿过物体并到达探测器的过程,通过将X射线光子的初始位置设置在一个小区域而非单独的点来模拟有限的焦点大小;在X射线光子和物体相互作用的建模过程中,通过计算光子在轻微不同方向和位置进入体素的路径长度来考虑了重建像素的大小和尺寸(而不是一个假想的点);采用相同的方式,探测器单元的大小和形状通过探测器响应函数来建模[9],见图1。将综合投影与探测器采集的实际测量值进行比较检验,两者之间的差异代表了当前估计需要校正的误差,并对当前估计得到的图像进行校正。再将校正后的图像带入模型进行下一次综合投影模拟,并与实际测量值再次进行检验和校正。通过如此的反复迭代计算,对图像信息进行不断地检验和修正,直到误差降到最低,将修正的图像确定为最终的重建图像。在图像校正过程中,除了采用建立系统光学模型,还采用了系统统计模型,该模型分析每一个独立光子的统计波动的特征,并与正确的统计分布进行比较,有效地降低了统计波动引起的图像噪声,见图2。
2 自适应统计迭代技术(Adaptive Statistical Iterative Reconstruction,ASiR)
2008年,GE公司首先推出基于系统统计模型的自适应统计迭代重建技术(Adaptive Statistical Iterative Reconstruction,ASiR),ASiR重建技术通过首先建立噪声性质和被扫描物体的模型,并利用迭代的方法对噪声加以校正和抑制,得到更清晰的图像,见图3。ASiR技术可以显著降低重建图像的噪声,改善图像质量,与FBP算法相比,下降了约50%的扫描剂量[10]。自ASiR重建技术推出并应用于临床之后,多家CT制造商均在加紧迭代重建算法的研究,陆续推出类似技术:西门子公司(Iterative Reconstruction in Image Space,IRIS)[11]、飞利浦公司(iDose4技术)[12]和东芝公司(Adaptive Iterative Dose Reduction,AIDR)。ASiR技术在原始数据空间利用系统统计噪声模型来消除统计波动造成的图像噪声影响。IRIS技术是在图像数据空间利用迭代技术降低图像噪声。iDose4技术在原始数据空间降低噪声的同时,试图保持传统FBP技术重建图像的噪声谱特征,以更好地符合医生传统的读片习惯。AIDR技术可以自适应地计算最佳迭代次数以加快重建过程。临床研究证实第一代统计迭代重建技术在保证同样图像质量和相似重建速度的前提下,剂量可以降低30%~65%[13]。
继第一代迭代重建技术推出并取得良好的临床应用之后。2011年,GE公司推出模型基础的迭代重建技术(Model-Based Iterative Reconstruction,MBIR)。与第一代迭代重建技术不同的是,MBIR技术除了建立系统统计模型之外,还建立了系统光学模型,体素、X射线光子初始位置和探测器几何因素均通过模型进行模拟,见图4,真实地还原了X射线从投射到采集的过程,其中计算量最大的部分是系统光学模型的建立,其价值主要体现在提高重建图像的空间分辨率。此外,为了进一步提高模型的准确性,还加入了去除硬化伪影和金属伪影的技术。除了显著地减小噪声和降低剂量以外,该技术可以自适应地识别区分重建组织的类型,如骨(高频信息)和软组织(低频信息)等,并保留了图像的细节信息,空间分辨率和对比度进一步提高。已经发布的模体实验证实,与FBP技术相比,MBIR技术在保证同样图像质量的前提下,剂量可以降低67%~82%[13]。该技术在临床CT影像的表现如何,还需要进一步研究。
基于优化迭代的博弈树算法 篇5
机器博弈是人工智能研究的一个重要方面, 人类对机器博弈的研究衍生了大量的研究成果, 这些成果对更广泛的领域产生了重要影响。
从1990年末, 诺曼·施瓦茨科普夫利用美军的超级计算机对“沙漠风暴”行动进行战略模拟到1997年IBM公司的超级计算机“深蓝”与当时的国际象棋世界冠军卡斯帕罗夫进行了一场大肆渲染的比赛, 基于博弈树搜索技术的机器博弈已经取得了长足的发展, 并且形成了一整套提高搜索效率的办法。而且, 由于博弈技术衍生而来的多种应用, 在航空调度、天气预报、资源勘探、军事博弈、金融 (经济) 调控等领域, 也取得了大量引人瞩目的成果。
“二人零和、全信息、非偶然”是博弈中最简单的一种情况, 但是通过对它的研究仍然可以取得很多有用的成果, 并且在复杂情况下, 对原有的成果进行适当的变换, 就能应用于复杂的形式。当今世界上的主要机器博弈技术包括以下几种:基于α-β剪枝的极小窗口搜索、历史启发规则、置换表技术和基于多次搜索的迭代算法。它们各有优缺点, 并且存在着一定的互补作用。
文章将对各种技术进行细致的分析, 然后利用它们之间相互补充的关系, 提出一种改进的算法, 并且通过具体的实验数据说明改进的算法确实提高了搜索效率。
1 传统搜索算法分析
在基础的α-β算法中, 存在着四个主要的问题。第一, 算法为了保证分析的节点值落在估计的范围内, 采取了全窗口搜索的策略——一般在区间 (-∞, +∞) 进行, 这样的策略使得区间的收敛速度较慢, 在极端情况下和极大极小算法的时间复杂度相同;第二, 研究发现α-β算法的效果对于节点的排列相当敏感, 在节点排列顺序良好的情况下, 算法的效率可以大大优于节点排列不好时的情况, 但是基础的α-β算法却没有提供任何意义上的排序手段去改善分析节点前, 搜索树的节点排列顺序;第三, α-β算法是基于递归模式完成的, 但是在算法分析的书中通过分析, 确定简单的递归模式会存在致命的问题, 导致同一节点的重复计算, 降低了算法的效率;第四, 博弈事件本身存在着一定的特点:在不同阶段, 局面的复杂性会存在明显的变化 (一般情况下随着时间的推移局面将越来越简单) ;这样在相同的硬件条件和相同的时间开销下, 在简单局面下就可以分析更多的层次来得到更加好的行动, 但是基础的α-β算法却没有考虑到这些, 仍然按照指定的深度进行搜索, 从而不能充分利用硬件资源。
1.1 极小窗口搜索
为了使得算法一开始就在一个较小的窗口内进行收敛, 存在着两个主要的算法:渴望搜索和极小窗口搜索。渴望搜索的基本思想是:在指定深度为n的情况下, 进行两次搜索。第一次在全窗口模式下计算深度为n-1的博弈树, 并且将得到的最佳步骤值X作为n层博弈树最佳步骤值的估计。然后在X两边取一个小窗口 (X-window, X+window) 进行计算。极小窗口搜索则是基于如下假设:假定第一个节点是最佳的行动, 其后继则次之, 直到另外一个节点被证明是最佳的。在搜索时利用极小窗口 (v, v+1) 进行, 这样可以大大提高搜索中剪枝的效率。极小窗口搜索在一般情况下是优于渴望搜索的, 其原因有两点:极小搜索是基于本层的节点, 这样它不会像渴望搜索那样在不同层次最优解值有巨大变化的情况下, 效率下降 (水平效应) ;其二极小搜索是在 (v, v+1) 中进行的, 它不需要像渴望搜索一样估计具体的窗口大小 (因为窗口的大小在渴望搜索中是很容易受到估值函数的影响的, 而搜索的命中几率却又依赖窗口的大小) 。根据基于象棋模型的研究发现, 在估值函数一样的情况下, 极小窗口搜索比一般的α-β算法效率提高了很多, 就是和渴望搜索相比也是占优势的。进一步测试发现极小窗口搜索在局面动荡情况下比渴望搜索能体现出更好的性能, 这是因为动荡的局面下, 水平效应会更加明显 (所谓动荡的局面就是类似在棋类中连续交换子力的情况) 。所以在一般的博弈算法中, 极小窗口搜索使用频率是高于渴望搜索的。
但是极小窗口存在的问题也是显而易见的:当节点的顺序不好的时候, 它的收敛速度会受到很大的影响 (这是α-β算法的一个特性) 。造成这个结果的原因是因为搜索中没有存储节点的历史信息, 不能在搜索之前对节点进行排序, 帮助搜索的进行。
1.2 历史启发搜索
上面指出, 研究发现α-β算法的收敛效率对于节点的排列相当敏感, 节点排列顺序的优劣直接影响α-β算法的剪枝效率。一个直接的说明就是:当测试棋类活动中对称点的相同行动时 (比如象棋中用左右两个炮分别使用“当头炮”作为开局) , α-β算法的效果就会有明显的差异。根据Knuth和Moore所做的研究表明, 在节点最理想的情况下搜索的节点数目约是最不理想情况下的平方根的2倍左右。所以在搜索之前能够对节点进行排序, 然后再进行搜索, 对剪枝时的收敛是有很大帮助的。历史启发规则就是为了在搜索前根据其他子树搜索的信息, 排列现有的节点。J·Schaeffer研究发现, 在α-β算法中对一个好的行动进行如下的定义:
· 由其产生的节点本身引发了剪枝
· 由其产生的节点是其兄弟节点中最佳者
然后根据节点所在层次给予这样的行动一定的得分 (具体的得分J·Schaeffer认为应该是2depth——depth是节点和叶子节点的距离) , 在搜索其他子树时, 按照行动的优劣重新排列所产生的节点, 就能够保证剪枝算法的高效进行。在实际环境的测试中, 数据证明利用了历史启发的搜索, 在相同博弈树中所花的时间比单纯的α-β算法随着深度增加带来指数级的减少, 从而也更加证明了节点的排列对剪枝效果是有很大影响的。
但是历史启发搜索有两个小的问题:第一, 它的历史仅仅局限于一次搜索, 不能从以前的搜索中带来启发, 所以在最上层的节点是没有历史信息可以用的。需要注意的是在博弈中, 最上层的节点所代表的行动才是真正可以实施的行动, 所以让最上层节点也有相应的历史信息是能够更好地提高剪枝效率的。第二, 对重复局面的多次分析。由于一个好的行动在不同子树中产生的节点都可能是其所在子树的最佳行动, 所以历史启发搜索会多次去分析这个节点, 并且调用其相应的估值函数。在估值函数简单或者高效的情况下, 问题不那么明显;但是, 当估值函数复杂时情况就会变得糟糕。
1.3 置换表
在基础的α-β算法存在的第三个问题是由于递归方法引起的。这是因为递归有时会有一个致命的弱点, 那就是最简单的直接递归实现, 会随着层次的增加带来时间指数级别的增长。在斐波纳契数的简单递归实现中, 就会有这样的问题。
程序1 斐波纳契数 (递归实现)
从上面的代码可以得知, 之所以时间会按照指数级别增加, 是因为在计算n时需要计算n-1和n-2, 在计算n-1时又要计算n-2, 同一个值可能在不同子树中被计算很多次。所以, 如果在搜索中记录分析过的局面, 在不同子树碰到同样局面时, 不再分析而是直接用存储的结果, 将会有利于搜索速度的上升, 而且随着搜索深度的上升, 命中率也将提高。置换表就是在这样的思想中加入的。置换表运用了哈希技术, 实现了节点的高效存储和读取, 在置换表的作用下, α-β算法的效率得到明显提升, 而且深度越大, 效果越明显 (这是因为随着搜索层次的增加, 命中概率也会增加的原因) 。
置换表算法也存在两个问题:1) 不能进行小窗口剪枝, 因为这个算法是基于基础α-β算法的, 搜索范围是全窗口。2) 没有运用历史启发, 它只是简单地记录分析过的局面, 而没有给予它相应的得分信息。
1.4 迭代深化
在硬件允许的条件下, 计算的层次越深考虑到的情况也就会越多。迭代深化就是一个不断求精的过程, 由从低到高的顺序进行对同一局面一系列的分析而构成, 同时通过计算搜索用的总时间, 来决定是否继续搜索 (这个时间依赖于具体博弈事件) 。这样做的好处是显而易见的:第一, 如刚才的分析所说, 博弈事件在不同阶段内复杂度会有较大的差异, 在复杂阶段由于考虑的因素较多, 所以搜索深度在较浅的情况下, 时间花费已经很高;但是在局势简单的情况下, 分析相同的层次时间花费就会下降。在局势简单时, 利用迭代可以在相同的时间内分析更多的层次, 甚至可以发现隐藏的动荡局面。第二, 第n-1层的结果可以对第n层的结果进行历史启发, 在一定程度上加快收敛的速度。通过测试迭代算法, 发现迭代算法不但在一层的搜索中优于α-β算法, 而且因为在简单局势下可以分析更多的情况, 在分析精度上也超过了基础的α-β算法。
但是迭代算法也存在着明显的缺点:最大问题在于, 在迭代中搜索的次数过于密集, 从深度1一直分析到深度n, 期间存在着大量的重复搜索;同时由于没有使用节点排序等技术, 在确定的层次中搜索效率低于上面的三种技术。
2 算法改善
2.1 算法建模
上面的四种技术各有各的优点, 但同时也存在着缺点。根据查看各自的特点, 合理整合它们, 是可以得到更加优秀的搜索算法的。首先分析一下每个技术对算法改善的程度。
从表1中可以清楚地看到, 历史启发搜索在同样的情况下对搜索效率的提升是最高的;极小窗口也有很好的效果, 而且极小窗口搜索可以解决历史启发收敛速度慢的特点 (这里指α-β剪枝和极小窗口剪枝的区别) , 所以将原来使用基础α-β的历史启发搜索代替为使用极小窗口的历史启发搜索会取得更好的效果。同时, 置换表也可以加入其中, 记录分析过的局面, 加快节点的分析速度。所以算法的基本思想是以极小窗口搜索算法为基础, 然后在其中加入历史启发的思想来进行节点排列, 提高收敛的速度, 同时应用置换表技术, 避免相同局面节点的重复分析。接下来, 用迭代深化多次调用这样的组合, 从而取得令人满意的效果。加入迭代算法的理由是:对于最上层的节点, 不论是历史启发还是置换表都不可能提供有利于最上层节点分析的内容。加入迭代算法后这个问题就能得到很好的解决。首先, 迭代可以产生浅层分析的最佳步骤, 作为深层分析中最上层节点排序的依据;其次, 迭代算法引起的置换表信息变化, 也可以被深层的分析应用;最后, 由于极小窗口搜索就是基于第一个节点是最佳节点的假设, 所以它能够提升极小窗口搜索算法的效率。
这个思想虽然很好, 但是仍然没有最大程度地利用迭代带来的好处。因为既然可以返回最优节点的结果, 为什么就不能返回次优节点的结果或者前面n个较好节点的结果呢?所以, 在迭代搜索前加入了一个节点数组记录, 用于记录所有第一层节点在上一次迭代中的得分可以起到返回多个节点分析值的结果。需要指出的是, 这个和历史启发算法中的得分含义是不同的。历史启发中的得分只可能是0或者正整数, 但是在用于记录第一层节点中节点得分的值可能是正、负或者零。它们的含义是:正, 说明在浅层的搜索中, 这样的行动能够带来对本方有利的局面;负, 说明在浅层的搜索中, 这样的行动能够带来对本方不利的局面;零, 说明这样的行动在上层中或者是双方均衡的局面, 或者是因为剪枝而没有分析的局面。在迭代n层时, n-1层的记录就能被用于排列第一层的节点, 从而在前几个节点中就能包含着最优的行动, 导致整棵博弈树迅速收敛。图1描述了加入了第一层节点全部排列的思想后程序的流程图。
2.2 算法分析
在完成后, 测试阶段发现了上述算法的两个问题:第一, 在和没有加入迭代深化思想的算法比较, 速度没有明显的优势, 而且在搜索深度较浅的情况下甚至不如原来的算法;第二, 算法在局面平稳阶段效果较好, 但是当局面不稳定时就会变差。
经过比较发现, 第一个问题是因为迭代太密带来的。跟踪发现, 第n层和第n-1层的时间比约为10∶1到10∶3, 虽然第n-1层的搜索结果对于第n层有良好的启发作用, 但是因为这10%-30%的额外开销, 抵消了原有的优势!进一步研究发现, 算法在平稳阶段和动荡阶段的差别是由于水平效应引起的 (在平稳阶段, 相邻深度的估计值相差较小, 到了动荡阶段, 相邻深度的估计值相差就会变大) 。所以迭代中不使用原来的从n-1到n的策略, 而是使用从n-2到n的策略, 这样可以大大减少第n-1层带来的开销, 同时一定程度上防止水平效应带来的问题 (因为当层次相差2时, 最后的行动方是相同的) 。综上所述改善后的算法有如下特点:算法继承了极小窗口、历史启发、置换表和迭代搜索的优点, 同时也弥补了原来存在的不足, 更加重要的是算法消耗了一个很小的内存用来记录博弈树第一层节点的优劣值, 就能对原来不能改善的搜索树第一层节点进行有效排序, 加快了搜索效率。
2.3 实验结果
在完成了上述的分析和调试后, 在基于PIII 866MHZ处理器, 196MB RAM, 操作系统为Microsoft Windows2000的环境下测试了这个算法的效率 (模型是象棋程序) , 从表2可以看出, 它不仅比原来的算法有了明显的改善, 就是比它们当中几个的联合也要强, 而且随着深度的增大, 效果更加明显, 这正是第一层节点排序和减少迭代次数带来的好处。
3 结 语
论文中提出的基于优化迭代的博弈树算法不但综合了原有算法的优点, 并且通过适当的加强对博弈效率和博弈精度也有所加强, 实验数据可以证明改善后的算法确实起到了良好的效果。
摘要：博弈是诸如下棋、打牌、战争等一类竞争性智能活动的通称。通过对机器博弈的研究衍生了大量实用的研究成果。分析当今国际上主流的加快博弈树搜索效率的算法, 根据它们的优缺点建立一种基于优化迭代的新算法, 并且通过实验数据证明算法的优势。
关键词：α-β剪枝,历史启发,迭代深化,极小窗口搜索,置换表
参考文献
[1]George F Luger.Artificial Intelligence:Structures and Strategies forComplex Problem Solving.Fifth Edition.机械工业出版社, 2005.
[2]NilsJ.Nilsson.Artificial Intelligence:A new Synthesis.机械工业出版社, 2000.
[3]Rivest.R.L Game Tree Searching by MinMax Approximation.Aritfi-cial Intelligence, 1998, 34 (1) .
[4]Jonathan Schaeffer.The history heuristic and alpha-beta search en-hancements in practice.IEEE Transactions on Pattern Analysis andMachine Intelligence, November 1989, pami-11 (1) :1203-1212.
[5]Ken Auer, Erik Meade, Gareth Reeves.The Rules of the Game.XP/Ag-ile Universe, 2003:35-42.
[6]Robert Sedgewick.Algorithms in C++Parts 1-4 Fundamentals, DataStructures, Sorting, Searching.中国电力出版社, 2004.
[7]Kishimoto A, Schaeffer J.Distributed Game-Tree Search using Transpo-sition Table Driven Work Scheduling.Proceedings of the 2002 Interna-tional Conference on Parallel Processing (31st ICPP 02) , Univ.of To-ronto, August 2002
一种改进的迭代硬阈值算法 篇6
关键词：压缩感知,重构算法,迭代硬阈值,匹配追踪
传统信号采集和处理的过程必须满足奈奎斯特采样定理, 即要求采样频率必须大于等于信号最高频率的两倍, 而实际应用中采样频率一般是信号最高频率的五到十倍。随着信息技术的不断发展, 需要处理的数据量不断增大、信号频率不断升高, 采用基于奈奎斯特采样定理的传统信号处理方式将对采样系统提出很高的要求。Cadens、Donoho等于2006年提出的压缩感知 (compressed sensing, CS) 理论[1,2]充分利用信号的稀疏特性或者可压缩特性, 能够以远低于奈奎斯特采样频率的频率实现对信号的同时压缩和采样。该理论指出, 对于稀疏信号以及在某种变换基下可以稀疏表示的信号, 可以通过选取合适的观测矩阵, 得到远小于信号长度的非自适应线性投影, 然后通过求解相应的优化问题, 即可从少量的投影值中精确重构出原始信号。压缩感知主要包括三个步骤:信号的稀疏表示、观测矩阵的选取和信号的重构, 其中信号重构部分所使用的重构算法直接影响信号压缩重构的效果和速度。因此, 研究压缩感知重构算法具有重要的意义。
目前, 压缩感知常用的算法主要分为两类:①基于最优化l1-范数的线性规划算法, 通过将非凸问题转化为凸问题来逼近原始信号, 主要包括基追踪算法 (basis pursuit, BP) [3]、迭代阈值算法 (iterative thresholding, IT) [4]、迭代硬阈值算法 (iterative hard thresholding, IHT) [5];②基于最优化l0-范数的贪婪迭代算法, 通过局部最优化来迭代逼近原始信号, 主要包括匹配追踪算法 (matching pursuit, MP) [6]、正交匹配追踪算法 (orthogonal matching pursuit, OMP) [7]、压缩采样匹配追踪算法 (compressive sampling matching pursuit, Co Sa MP) [8]、子空间追踪算法 (subspace pursuit, SP) [9]。其中迭代硬阈值算法在每次循环中求出多个重构原子, 具有复杂度低、收敛速度快的优点, 但重构精度受初始条件和观测矩阵影响较大;而压缩匹配追踪算法具有较高的重构精度, 但重构复杂度较高、收敛速度慢。现结合迭代硬阈值算法和压缩采样匹配追踪算法提出一种改进的迭代硬阈值算法 (modified iterative hard thresholding, MIHT) , 仿真结果表明本文提出的MIHT算法能够很好解决IHT算法在初始条件为0的情况下, 重构效果不佳的问题, 该算法同时具有重构精度高和收敛速度快的优点。
1 压缩感知简介
压缩感知理论的核心是通过选取合适的观测矩阵, 把一个高维的稀疏信号或者可以稀疏表示的信号投影到一个低维空间上, 然后通过求解优化算法, 由低维投影值重构出原始高维信号。具体地, 假设原始信号x为N×1的离散信号, Ψ是一个N×N的正交变换基 (Ψ的每一列为一个基向量ψi) , 则x可以由Ψ表示为:
式 (1) 中, α为x在Ψ下的投影系数。当系数α为K-稀疏时, 即‖α‖0=K<<N, 时, 认为信号x可以通过变换基Ψ进行稀疏表示。
压缩感知理论指出, 对于这样可以稀疏表示的高维信号x∈RN×1, 可以通过选取合适的观测矩阵Φ∈RM×N对其进行非自适应线性观测, 得到低维观测值y∈RM×1 (M<<N)
由于M<<N, 即方程组的数目远小于未知数的数目, 所以由y重构出x的过程是欠定的。但是, 由于x是K-稀疏的, 所以当观测值数目M满足M=CK (C为经验值) 时, 可以通过求解最优化l0-范数精确重构出原始信号[10], 即
以上求解l0-范数的过程是NP难解的, 而贪婪迭代类算法为求解该问题的近似解提供了有利的工具。同时, Baraniuk在文献[11]中指出, 当观测矩阵Φ满足约束等距性 (restricted isometry principle, RIP) 时或者观测矩阵Φ与变换基矩阵Ψ不相关时, 可以通过求解最优化l1-范数代替最优化l0-范数得到原始信号, 如式 (4) 所示。
线性规划类算法就是通过求解最优化l1-范数得到近似解。
定理1 (RIP性质) 对于K稀疏信号x和观测矩阵A, 如果存在一个常数σK (称为约束等距常数) , 使下式成立
那么, 说A满足RIP性质, 就可以由少数投影值y=Ax中精确重构出原始信号。
2 改进的迭代硬阈值 (MIHT) 算法
文献[5]提出的硬阈值迭代算法 (IHT) 属于线性规划算法, 是通过求解式 (4) 最优化l1-范数得到近似解, 其采用如下寻优迭代公式
式 (6) 中, HK (a) 是一个非线性操作, 其结果是保留a中幅值最大的K个元素, 其他元素都置为0;μ是一个大于0小于等于1的经验值;通常取初始条件x[0]=0。根据式 (6) , 可以把式 (4) 等价为求解式 (7) 所示的最小值
IHT算法致力于在每次迭代中直接寻找K个最大元素, Blumensath在文献[12]中指出, 该算法要达到较好的收敛效果, 测量矩阵Φ除了要满足RIP性质之外还必须满足条件‖Φ‖2<1。IHT算法在满足条件的情况下, 虽然能达到比较快的收敛速度, 但是其重构精度受初始条件x[0]的值影响很大, 只有在特定的x[0]下才能达到较高的重构精度[12]。所以, 通常把IHT算法与其他算法, 如BP、MP算法等, 结合使用, 先由BP或MP算法迭代得到一个合适的初始条件, 然后再通过IHT算法得到最优解。但是, 这样会增加整个重构过程的复杂度, IHT算法本身收敛速度快的优势就得不到体现。
针对以上问题, 对IHT算法本身进行了改进, 引入Co Sa MP算法中原子回溯的思想, 把IHT算法每次迭代中x更新的方式修改为式 (8) 、式 (9) 和式 (10)
式中, x[n]表示第n次迭代得到的稀疏解, xC表示只留下x中由索引集C所索引的元素, 这里的索引集C为当前迭代索引集与上次迭代索引集的合集, 即引入了原子回溯的思想, 在引入原子回溯思想之后, 能够大大降低每次迭代过程中寻找的最佳索引集出错的概率, 提高重构精度。
MIHT算法流程如下
输入:测量矩阵T=ΦΨ, 其中Φ为观测矩阵, Ψ为变换基矩阵, 测量值y, 信号稀疏度K;
输出:重构稀疏解x_rec, 索引集F;
初始化:初始残差r0=y, 初始支撑集F0=[], 初始稀疏解x0=0, 初始迭代次数it=1;
步骤1判断迭代是否停止:如果it≤K, 则转步骤2;否则转步骤6;
步骤2求最大索引集:Sit=max (|TT*rit-1|, K) , 即求测量矩阵的列与上次残差乘积绝对值最大的K个值对应的索引集, 转步骤3;
步骤3原子回溯:Cit=union (Sit, Fit-1) , 本次迭代求得的最大索引集与上次迭代所得索引集合并, 此步的目的是降低每次迭代过程中所得到索引集出错的概率, 提高算法的重构精度;转步骤4;
步骤4信号估计:xr=zeros (N, 1) , xr (C) =T (:, C) T*[y-T (:, C) *xi-1 (:, C) ], xi=xi-1+u*xr, 此步的目的是根据步骤3所得索引集对稀疏解进行更新, 这里u为经验值, 常取u=0.5;转步骤5;
步骤5更新索引集和残差:Fi=max (xi, K) , ri=y-T*xi;it=it+1并转步骤1;
步骤6输出稀疏解和索引集:F=FK, x_rec (F) =xK (F) 。
2.1 MIHT算法收敛性证明
定理2 (文献[5]和文献[8]中证明) 。对于所有的索引集Γ和s=|Γ|满足RIP性质的观测矩阵Φ, 则式 (11) 、式 (12) 和式 (13) 式成立
由以上定理, 可以得到MIHT算法收敛性的证明, 如下所示 (这里不考虑观测过程中引入的误差)
因为比x更接近。其中, e[n+1]为第n+1次迭代得到的近似解与原始信号的误差。把式 (8) 和式 (9) 带入式 (14) 可以得到式 (15)
式 (15) 中CnCn+1表示从集合Cn中去除所有包含在集合Cn+1中的元素, 所以有Cn+1∩ (CnCn+1) =0, 且满足|Cn∪Cn+1|≤3K。
又因为σ2K≤σ3K (σ2K和σ3K分别为观测矩阵Φ的2K和3K-RIP系数, K为原始信号x稀疏度) 以及正交且满足, 所以有
所以有
如果, 则有
即该算法收敛。
2.2 MIHT算法复杂度分析
IHT算法的运算复杂度主要由每次迭代过程中对信号估计以及精确重构需要的总的迭代次数所决定, 其中对信号的估计主要体现在使用寻优迭代公式 (6) 对稀疏解进行更新, 且标准的IHT算法通常取迭代次数为固定值K, 所以IHT算法的计算复杂度近似为O (KMN) , 这里只考虑乘积运算。对于本文提出的MIHT算法, 其每次迭代过程的运算量不仅包括对信号的估计, 还包括对残差的更新。但是, 相比于IHT算法中的整个测量矩阵Φ的所有N列都要参与运算, MIHT算法在对信号进行估计的时候只需要测量矩阵Φ中的2K列进行运算。所以, IHT算法在每次迭代过程中的运算复杂度近似为O (MN) +2O (KM) , 当迭代次数同样取K次时, 总的运算复杂度为O (KMN) +2O (KKM) 。可以看出, MIHT算法的复杂度略大于IHT算法, 但是通常稀疏度K远远小于信号原始长度N, 所以当M很小时, 可以认为MIHT具有和IHT算法基本相同的运算复杂度。
3 仿真结果对比及分析
为了仿真验证MIHT算法的性能, 分别对一维稀疏信号和二维图像进行了重构, 并把MIHT算法与Co Sa MP和IHT算法进行比较。
3.1 一维信号
为了验证算法的性能, 首先对一维信号进行了稀疏重构, 采用长度为N=256, 稀疏度为K=8的多频率正弦信号作为测试信号, 观测矩阵采用文献[13]中所述的由伪随机序列组成的观测矩阵, 因为该观测矩阵不仅满足RIP性质, 同时满足IHT算法对观测矩阵的要求‖Φ‖2<1, 稀疏基矩阵为离散傅里叶变换基。图1所示是压缩比为M/N=1/8时的重构效果图, 即测量值数目M=32, 仿真结果显示重构误差为1.31%, 说明MIHT算法对此一维信号的相对误差很小, 重构效果很好。
同时, 在相同条件下, 给出了重构概率和运行时间随测量值数目变化曲线, 如图2和图3所示, 由于文献[13]中的观测矩阵要求N必须是M的整数倍, 所以把信号长度N扩充到1 024, 并取M分别为32, 64, 128, 256和512。从图2中可以看出, 随着测量值数目的不断增大, 三种算法的重构概率也增加, 这是因为测量值数目越大, 测量值中所包含的原始信号的信息就越多, 就越有利于重构。同时, MIHT算法的重构虽然不如Co Sa MP算法, 但是相比于IHT算法得到了很大的改进, 尤其是当测量值数目M取值比较小的时候, 这说明MIHT算法与IHT算法相比, 能够达到更高的压缩比和更好的重构效果。
从图3可以看出, IHT算法和MIHT算法的运行时间要明显小于Co Sa MP算法的运行时间, 同时MIHT算法的运行时间并没有比IHT算法增加很多, 这是因为, 与IHT算法相比, MIHT由于增加了求残差以及残差与观测矩阵乘积的步骤, 会使时间增加, 但同时对于x的更新方式, 由IHT算法中完整的M×N观测矩阵与x相乘变为仅仅让M×2K的重建原子集与x相乘, 这又会导致运行时间减少, 所以与IHT算法相比, MIHT算法运行时间增加的并不明显。
3.2 图像信号
为了验证MIHT算法对二维图像信号的适用性, 对256×256的标准Lena图像进行了压缩重构, 观测矩阵仍然为文献[13]中所述的由伪随机序列组成的观测矩阵, 采用离散小波变换基对信号进行稀疏表示, 压缩比为M/N=1/4时三种算法比较结果如图4所示。从图中可以看出, 对于这里所采用的图像信号, MIHT算法略好于Co Sa MP和IHT算法。为了更好地比较各个算法对Lena图像的重构性能, 表1给出了不同算法所得到的重建图像的峰值信噪比PSNR、相对误差和重构时间。从表1中可以看出MIHT算法对Lena图像重构的PSNR最高, 运行时间处于IHT算法和Co Sa MP算法之间。
4 小结
排序框架下梯度下降迭代本体算法 篇7
从机器学习的角度来研究本体算法, 最早是将谱图理论的相关知识和本体相结合[4—6]:将高维流形中图拉普拉斯算子转化为低维本体图拉普拉斯矩阵, 通过逼近算法得到本体图拉普拉斯矩阵次小特征值对应的特征向量, 进而将整个本体图映射到一维实数空间中。从而本体图中每个顶点都被映射成了对应实数, 它们之间的相似度转化为它们在一维实数空间上的几何距离, 即实数间的差值。文献[7, 8]从统计学习理论的角度对此类算法进行了收敛性分析, 其中文献[7]将连续函数空间CS作为相似度函数的假设空间, 而文献[8]将Lipchitz s空间作为其相似度函数的备选空间。
近年来, 各种学习算法被用于本体相似度计算和本体映射的获得。由于本体图中所有顶点对的相似度可以构成一个对称相似度矩阵, 因此文献[9]将矩阵学习的思想引入本体相似度计算中, 提出基于核矩阵优化的本体相似度计算方法;文献[10]对基于最优ROC曲线的k-部排序本体算法进行了理论分析。
最近, 文献[11]提出了在二部排序学习框架下的梯度下降迭代算法。受到文献[11]的启发, 将梯度下降迭代模型的思想用于本体相似度计算和本体映射, 得到一般排序框架下梯度下降迭代本体算法。该算法从本体图的实际考虑, 其样本集由专家选定的边集合E来决定。
1 排序框架下的梯度下降迭代本体算法
首先, 本体图中每个顶点与之相关的所有信息用一个多维向量来表示。为了方便表示, 在不引起混淆的前提下用v来表示顶点以及该顶点对应的向量。进而, 分别为输入输出空间, 其中V独立随机服从未知分布ρ。给定。本体学习算法的目标是通过S的学习得到本体排序函数, 它将本体图中每个顶点映射成实数轴上的点。
对于排序算法而言, 其实例对应的排序得分的大小关系要尽量符合客观事实。因此本体图中任意两个顶点v, v'∈V, 它们在排序函数f下对应实数的大小关系应该和它们的标记的大小关系相一致。引入本体排序亏损函数l:用来衡量不一致的情况下 (即, sgn[f (v) -f (v') ]≠sgn (y-y') , 其中符号函数出于算法光滑性的需要, l是非负实值凸函数且l (f, (v, y) , (v, y') ) 关于 (v, y) 和 (v', y') 对称。
在给定本体排序亏损函数l的条件下, 本体排序函数f的质量通过用如下期望误差来衡量
在实际计算中, 由于概率分布ρ未知, 因此用如下经验误差来替换上述期望误差
式中F为可测本体排序函数空间, 即假设空间。为对称半正定核函数。与K相关联的再生核希尔伯特空间HK定义为, 其中内积〈·〉K定义为〈Kv, Kv'〉K=K (v, v') 。设。对于任意v∈V及任意再生核希尔伯特空间中的函数f∈HK, 有。
与再生核希尔伯特空间关联的本体排序算法可表示为如下经验模型
它的期望模型对应为
这里, λ‖f‖2HK称为平衡项, λ为平衡参数, 该项的作用是控制最优函数的光滑性, 防止其剧烈上下震荡, 从而提高算法的泛化性。根据亏损函数l的凸性可知, 其左偏导上是非递减的。
设为步长, {ηt}为步长序列。排序框架下的梯度下降本体算法可作如下迭代表示
上述算法中, 对于给定m个顶点的样本集, 需要对每一对样本点进行排序值的比较, 可知比较的次数为。可用一个边集合E (顶点对集合) 来取代样本集S中两两顶点的比较, 也就是说, 只对边集合中涉及的边对应的顶点对进行比较, 看它们对应实数的大小关系是否和它们的标记的大小关系一致, 这样的比较次数为E中边的数量, 即|E|。从而迭代计算模型 (3) 可边为
这里E中的边不一定是原本体图中的边。也就是说, E其实是本体图中一些顶点对构成的集合。但 (vi, vj) ∈E并不意味着 (vi, vj) 是原本体图G中的一条边。
2 排序框架下梯度下降迭代本体算法的描述
通过以上排序框架下梯度下降本体算法的分析可知, 当模型 (4) 中的一些参数被确定后, 只需要迭代优化计算模型 (4) 即可得到最优本体排序函数。由此, 得到将该模型应用于本体相似度计算和本体映射的具体算法步骤描述如下。
算法1
排序框架下梯度下降本体相似度函数迭代计算
步骤1
向量化本体图中每个概念对应顶点的相关信息。从而将V表示成高维空间的子集。
步骤2
从本体图中选取部分顶点对构成E。
步骤3
确定步长t和步长序列{ηt}。
步骤4
通过迭代求解优化模型式 (4) 得到最优本体排序函数f。
步骤5
根据步骤4得到的最优排序函数f将G中每个顶点映射到实数轴中对应点, 两顶点对应概念的相似度由它们对应实数轴上的距离来判断。
算法2
排序框架下梯度下降本体映射迭代算法
步骤1
将需要作映射的本体O1, O2, …, Oc的图结构分别用本体图G1, G2, …, Gc表示, 并令G=G1+G2+…+Gc。通过向量化顶点信息将V映射到高维空间的子集。
步骤2~步骤4:
与算法1一致。
步骤5
通过所得排序函数f确定G中每个顶点在实数轴中的对应点, 来自不同本体分支的顶点对应概念的相似度通过它们对应实数在实数轴上距离来判定。
步骤6
依据上述步骤5得到的概念对应顶点之间的相似度, 选择域值参数或其他恰当的本体映射策略生成不同本体间的映射。
3 实验分析
3.1 算法1在植物学中的应用
第一个实验采用植物本体PO (http://www.plantontology.org) 作为数据来验证算法1的效率。该本体是一个植物学词典, 它描述植物的解剖学和形态学, 以及在其发展阶段的所有植物。建立PO本体的目的是为从植物基因组学和遗传学的实验数据集上进行跨物种的查询建立有效的语义框架。PO本体结构是一个树型分层结构, 最上层为“plant anatomical entity”和“plant structure development stage”, 其中“plant anatomical entity”又分为“plant anatomical space”, “plant structure”和“portion of plant substance, 而“plant structure development stage”又分为若干个子类。所有的植物学相关概念逐层被细分。在查询时, 可根据专业关键词进行语义查询, 也可通过专业的植物学代码进行查询。其本体图大致分层结构图1所示。
由于算法模型是基于排序方法的, 因此采用P@N[12]平均准确率来对实验结果进行评价。其中步长t=3, 步长序列ηt的元素值均取1, 参数λ取0.1, 选取部分顶点对构成E。另外, 将基于快速排序方法的本体算法[13]和基于标准排序方法的本体算法[14]也分别作用于植物学PO本体, 并采用相同的P@N平均准确率对实验结果进行评价。对上述三种算法得到P@N平均准确率进行比较, 部分实验数据如表1所示。
通过表1的数据对比可知, 排序框架下梯度下降迭代本体相似度算法对于植物学PO本体的效率要高于基于快速排序技术的本体相似度算法和基于标准排序方法的本体相似度算法。
3.2 算法2在计算机软件本体中的应用
算法2的效率采用计算机软件本体作为本体数据来验证。图2和图3分别描述了两个计算机软件本体的结构。
由于排序算法一般只关注最相似的N个结果, 本实验使用与实验1相同的P@N平均准确率进行评价。步长t取2, 步长序列和平衡参数的选取和实验1一致, 同时选取大约1/3顶点对构成E。此外, 被用于算法1中的基于快速排序方法的本体算法和基于标准排序方法的本体算法也分别作用于计算机软件本体O2和O3。表2给出了三种算法下P@N平均准确率的部分数据。
通过表2的P@N数据对比可知, 排序框架下梯度下降迭代本体映射算法对于计算机软件本体的效率在N=1, 3, 5的情况下都要高于基于快速排序技术的本体映射算法和基于标准排序方法的本体映射算法。
4 总结
基于线性SGD的两层迭代算法 篇8
SGD算法的时间复杂度和迭代次数线性相关,和训练集的大小无关,即其所用到的仅仅是整个训练集的子集。本文的核心思想是通过对整个训练集的筛选,得到一个远远小于原始训练集的子集,在这个子集上进行最终的SGD算法的训练。
本文结构内容如下:第一部分描述基于线性SGD的两层迭代算法;第二部分为实验部分,阐明了本算法的有效性与可行性。
1 基于线性SGD的两层迭代算法
目标函数为:
对(1)求梯度可得:
2 基于线性SGD的两层迭代算法
因为SGD算法的运行时间和迭代次数有关,与训练样例的个数无关。所以,可以找到包含关键训练样例的训练子集来训练SVM分类器,而不是用整个训练集。
基于线性SGD的两层迭代算法思路如下:
首先可以用SGD算法对整个训练集进行训练,此时可得到一个分类器,即第一层SGD迭代。
根据SVM模型,只有位于支持超平面上的以及分错的训练样例对超平面的训练起作用,其它远离支持超平面且正确分类的训练样例对超平面的训练不起作用。
然后,通过第一步训练出来的分类器将位于支持超平面两侧的关键训练样例筛选出来,由此获得的新训练集的大小将远远小于原始训练集的大小。
最后,在新的训练集上用SGD算法完成最终SVM分类器的训练,即第二层SGD迭代。
对于关键样例该如何筛选呢?
位于支持超平面上的训练样例满足如下条件:
但严格符合上述条件的关键样例个数太少,不足以完成第二层SGD迭代。所以,应该扩大选择范围,让条件(5)上下有些弹性:
其中,a,b>0为筛选器的弹性参数。
3 实验结果与分析
为了验证基于线性SGD的两层迭代算法的可行性,本文准备了2个常用数据集,以供和Pegasos-SGD进行算法结果精确度上的对比。
covtype.binary训练样例522911个,测试样例58101个;mnist训练样例60000个,测试样例10000个。covtype.binary实验中设置为10-6[4],mnist实验中设置为2×10-4[5]。关于弹性参数(a,b)的设置,covtype.binary实验取固定值(0.1,0.1);mnist实验中分别取值为:(0.1,4)、(0.1,0.1)、(0.01,0.1)、(0.05,0.05)。
每种参数的实验都重复进行5次,实验结果展示如下:第一行是SGD过程的迭代次数,第二行是Pegasos-SGD算法的测试精度,第三行是线性SGD两层迭代算法的测试精度,第四行是线性SGD两层迭代算法第二步所选出的训练集的个数。
实验结果表明,线性SGD两层迭代算法的预测精度与Pegasos-SGD算法的预测精度大致相等。证明了线性SGD两层迭代算法的可行性。
4 结语
本文通过将SGD算法与样例选择相结合,成功的提出来一个线性SGD两层迭代算法。在此基础上,进一步需要研究的是将线性SGD两层迭代算法扩展到核方法,以减少带核SGD的训练与预测时间。并且,对于第二步样例筛选时,弹性参数a和b的如何取值才能让算法的预测效果达到最优也是一个有待研究的问题。这两方面的工作正在进行中。
摘要：近年来,随机梯度下降算法用于求解SVM模型的原问题得到了人们的广泛关注。随机梯度下降算法每次只处理一个训练样例,它可以快速训练出线性可分数据集的SVM分类器。由于随机梯度下降算法的运算时间与迭代次数呈线性相关关系,而与训练集样例的个数无关,所以文章提出了一个基于线性SGD的两层迭代算法,在算法的第二步,可以筛选出一个远远小于原始训练集的子训练集来完成最终SVM的训练。
关键词：随机梯度下降,支持向量机,两层迭代
参考文献
[1]Cortes C,Vapink V:Support Vector Networks.Machine Learning,1995,20(3):273-297.
[2]Tong Zhang.Solving Large Scale Linear Prediction Problems Using Stochastic Gradient Descent Algorithms,International Conference,2004:919-926.
[3]Jyrki Kivinen,Alexander J.Smola,and Robert C.Williamson.Online Learning with Kernels,in IEEE Transactions on Signal Processing,vol.100,NO.10,(10)2010.
[4]Shalev-Shwartz,Y.Singer,N.Srebro,and A.Cotter.Pegasos:Primal Estimated Sub-gradient Solver for SVM.Mathematical Programming,2011,127(1):3-30.