《共轭梯度与牛顿混杂算法及在神经网络的应用.doc》由会员分享，可在线阅读，更多相关《共轭梯度与牛顿混杂算法及在神经网络的应用.doc（7页珍藏版）》请在三一文库上搜索。
1、共轨梯度与牛顿混杂算法及在神经网络的应用孟江王縦才洪留荣（中国矿业大学信电学院高科技应用研究所，徐州221008）E-mail： blGag摘要在Po痕11重启动共轨梯度法基础上，利用共純迭代过程产生的二阶导数信息，构造出半询点的牛顿方向，从而 得出-类快速人犯梯度法。川丁神经网络逼近非线性函数的学习结果衣明，该算法的收敛速度均崗J；使用和同构造公式 的共轨梯度算法.关谴词共轨梯度与牛顿混杂算法收敘速度神经网络文章编1002-8331-（2004）35-0084-03文献标i只码A 中图分类勺TP183Conjugate-Gradient-and-Newton Hybrid Method an
2、dApplication in Neural NetworkMeng Jiang Wang Yaocai Hong Liurong(Information and Electronics College>China University of Mining and TechnologyXuzhou 221008) Abstract： Based on the restart conjugate gradient method by Powell,the current point's Newton direction has been constructed according
3、to the information of second derivative in the course of co»jugatr-graclienl calculation> which produces Conjugate-Gradient-and-Newton Hybrid(CGNH)inetluxLTlic learning result applied in neural network to approach to nonlinear function shows that the rate of convergence of CGNH method is bet
4、ter than that of conjugate gradient method using the same constiucting equation.Keywords： Conjugate-Gradient-and-Newton Hybrid method.the rate of convergence»neural network作人简介：孟江（1977- 为，阿I：研究4 .研究方向为神经网络及控制艸论84 2004.35 计够机工程与应用1引言共辘梯度法是无约束优化方法的经典方法之一，JI冇算法 简便，存储空间小，适介处理大规模问题，近年来随着对大规模 优化问题的迫切
5、性，共牠梯度法愈发受到t视。II询共辄梯度 法的研究热点，集中住不同形式构造因了的收敛性分析，而通 过改进算法过程來提岛共純梯度法的收敛速度，除Powell的 “取启动策略以及Beale-Powell的三项取启动算法，儿f没 有任何突破性进展。论文从共純梯度法与拟牛顿法的内在联系出发，构造了一 类快速共純梯度法，梵基木思想足：通过询/V次共轨梯度迭代 产生的Hessian矩阵信息，构造出当前点的牛顿方向.在重启 动的共純梯度法基醐上，进行一步牛顿迭代，从而提高算法应 用于非线性函数下的收敛速度。2共純梯度法简介共馳梯度法通过构造共牠梯度向试，将崗维的II标曲数极 小问题转化为U标函数在若干共辘
6、方向的-维优化问题。 2.1共辘梯度法类型设/V维二次凸悄数/（X）的Hessian矩阵A对称正定，存 在向呈组观（戶i：/v）満足/r.h/ =o（当 详Q,则称向虽/为A- 共辘方向。若阿向虽（/产节，则称/,为共馳梯度方向。共轨梯度 法即按照共钝梯度方向依次迭代，依据二次终止性，最终达到 说数的极小点.衣I构ifiWT公式列衣构造因子八体形式在凸目标補数公式名称（其中加）下的收敛性PRP* h希确线拽鸞'1和Amrijo线搜< Polak-Kibierc-Polvak)9"II5 r董円具全局收欽性EK丽确线厠,与广义Wolfe(HrtclicrKccvcb )T
7、 II唸冏全尉收纹性DYBr桥确线搜Wolfe线搜知<uan)及般线捜董牌具全局收敛性DH杂交法B严min( B：' Wolfe ift拽蜜具全胡枚敛性阀(DY & HS)|)HBa =n>ax(0- 3,)且好于PRP冃前共轨梯度法的分析与研究大都基于以卜标准形式： =匕+otx厶_A=1（1）H中必为第&次的迭代状态向虽:&为共轨梯度构适过 程中九的梯度向貳,X产 俎）：为步长因子，属于一维优 化的求解问题，可分为桔确线搜索方法（如牛顿法、区间分割 等）和非粘确线搜索（如Wolfe线搜索、Armijo线搜索等）：0；为 构造因了，其构造公式卫以來
8、备受关注，因而具右不同的形 式，表1列举了目询成熟的几类公式.2.2共轨梯度法特性共純梯度法具令两大特性：（1）共犯梯度法的二次终止性叫A维二次函数，经过不超 过/V步的共轨梯度迭代一定收敛到函数的极小点；（2）各类共施梯度法满足-定搜索条件时，可满足全局收 敛性，但在非线性函数下，算法只有线性收敛速度叫共犯梯度向駅的定义为d：+/H =o若目标函数是非线 性函数/XX）时，其Hessian矩阵不是常矩阵，因而冇必要 进行适肖的近似.设函数光常连续，某迭代状态乙对应方向 厶，対应梯度为色：卜一点対应方向血小对应梯度为站。 根据中值定理，存在疋（0,1,使得：a 必（跖）=«x/h（
9、几-7Z 曲二 I 乙 +心）d,因而得到近似关系式（2）：【 71«* 必= 71（ Xg-Xk）a g“i -& =>i（ 2 >2.3重启动的共呃梯度法为了提高共轨梯度法的线件收敛速度.Powell提出了雨启 动技巧:经H A步共範方向迭代后,将当前点的负梯度方向作 为下 轮迭代的初始方向。山丁毎“步都冇-次用悌度方向 作为下降方向，理论匕无论持确还是非梧确线搜索都能够保证 J法收敛，其总体收敘与局部收敛应具有更好的性质，且具有 N步的超线性收敛速度叫即：存在某种程度的近似关系：当Hessian对称正定时，非零向量 组（& 和如-&）将构成空
10、间的两组基，则V可被式完全确 定，所以可利用此结论进行当前迭代点牛顿方向的构造.3.2当前点的Newton方向形式若通过式（4）得到V,则当前点的Newton方向可表示为 -gw）3.2.1两组妹的钢标变换式N次共純梯度迭代后，对当前点X枫的梯度向呈存在以F 关系：gw 6 Spanfgp »g%）和g、+i g Span如Lgr，加心卜展 开为坐标，得：iVg“产S z周=Z周般2场+Z、g、（ 5）i = I|V乩产工力）=>1+ 22+）> gv >（6）i « i其中F是g"在基闻下的坐标:力是在基下的坐 标.且 y=）i+）2+&quo
11、t;+）i、式（6）可化简为：g,Q吕弋占丹&（7）联芷式（5）和（7,得到两组基坐标的变换（）厂勺丿式：小一 w咗lF(10)il算机I.程打应川2004.3585Xk-X |式中，/为函数的极小点。但是Fletcher所给出的数值结果表明重启动的FR和PRP方法并没有比原先方法好参少，即虐启动策略在实际计算 中没有达到理论的收敛速度.究其说因，Powell重启动策略會 弃了算法搜痢中获得的二阶导数信息：另外雨开始的频率与 U标函数的性质育关。因此结合Beal的共純构造三项公式叫”产-gA+IV4+% d,文献2给出了修正Beale-Powell亟启动算法，即在非负鑫 数性和X 证明
12、r垛法在强woife线挫索卜在一般卄凸函 数卜具有全局收敛性。3共純梯度与牛顿混杂算法在前文论述的基础匕，卜面详细闸述共続梯度与牛顿混杂 算法（CGNII）的实现患路与基本过程。3.1当前点Hessian矩阵的近似形式当目标函数为二次形式，H其Hessian矩阵A二）对称正定时，A-共純向咸4线性无关，并冃梯度向昴&也无关， 即圍构成空间 组基:对II-零的g-gf,也构成空间的另-组 基g、d若A可逆，则式（2）可变形为；<（餉飞曲川吗式（3）恰是拟牛顿方法的初始思路，即绕开Hessian矩阵， 直接通过某种方式得到其逆矩阵，然后构造牛顿方向，进疔牛 顿迭代.对/V次共轨梯度迭
13、代后的当前点X、.可仿照上式构造类 似关系式：V（gX-X=X/ （戶 1：小（4）式中"与当询点XM的Ilzian矩阵逆矩阵11步可以得到I英中 Z=2l+i2+-*+iXo将式（9变形后代回到式（8）,得到两组基坐标的反向变换（Z厂力）式：322坐标与的表达式在共純梯度的构造过程中，采用特确线搜索有：d；&=0 （l</<A<Ar）（11）考虑式（11）,可在式（5）两端分别左乘/（A=l：yv）,有:Nk屆产工zd：矿工拥&i = ii s i得到坐标弓的农达式：（12）=2根据式（计算得到当前点梯度在基圍下的坐标勺后, 再通过式（10）转化为
14、基g.厂&下的坐标”然后进行牛顿方向 计算.在实际的数值计算中若次共馳迭代后，当询点梯度 般都年常小，可近似为gi a 0,即満足共牠迭代二次终止性山 文献的引理，得到以下关系式：£s=0 （l</<7<Af）（13）冈而避免了向童组Ww-g）与圍的坐标Z间的变换式：同 时>A；i3）也衣"JJ向址组恒卩i仃11-:交ri.o利川11-:交向虽性威，式（5）两端分别A:-乘*：（心1 ： A ）,得到坐标右的衣达式为：z产昭&（14）3.2.3当询点的牛顿方向表达式山渝文所述，可得到当前点的牛顿方向:NA.=-V工刀（阳飞）=一工炉兀
15、（15）/ = 1i = I英中,）；通过坐标转化公式（10）111 r得到。的计毎式（12）中所击变虽较多，而对大规模问题时击耍 存储空间较大.为此，考虑&、.|近似为零的实际经验，将式（4） 变形为：-Vg=Xj （j=l：N）（16）得到当前点牛顿方向川“的简化公式：“u灼7纬&詛启&竺（17）3.2.4 CGNH算法过程快速共钝梯度法的主耍过程；利用询沖次共钝梯度迭代 所获得的当前点Hwdan矩阵信息，构造出牛顿方向.根据h 述步骤进疗一步或石多步（设进牛顿迭代步参数NDsleps）顿 方向迭代后，返何到新状态进行币:启动共辄迭代，如此反复，最 终到达指定将度的
16、极小点。快速共辄梯度法的主耍过程:利用前"次共純梯度迭代 所获得的当前点Hessian矩阵信息，构造出牛顿方向.根据h 述步骤进行步或肩多步（设置牛顿迭代步参数NDsteps）牛顿 方向迭代后，返回到新状态进行重启动共純迭代，如此反复，最 终到达指定特度的极小点。CGNH算法详细流程见图I.图1 CGNH節法桥图考&不同性质的目标函数,可能导致其Hessian矩阵不可 逆，或向就组幺存在相关性，而导致 g 方向不足下降方向， 可增加判别下降方向修正步：,V/= 一“仏 if "：，,&肿0曲一曲冲else(18)4神经网络的CGNH学习11 H'J谋
17、差反向传播（Back Propagation算法是前馈神经网 络仃教师学习中普遍采用的刈效算法，构筑了神经网络发展史86 2004.35 计够机工程与应用 的里程碑但是粥法的局部计知收敛速度相半缓慢，存在局部 极小值等许多问题问。为克服以上缺点，尤其是提高收敛速度， 产生 Hl in'j 阶 VI 法，如 Ijevenlx-i g-Marquardt 法、拟 T 顿 < quasi- Newton）法等，该类算法确实提高了收敛速度，但需耍更复杂的 计算屋为代价。当处埋现实世界的人规模问邃时，往往矗以奏 效.共轨梯度法作为一类构造巧妙的算法，实现了高效性与收 敛性的収羅因此倍受青睐
18、。但山F算法IA1有的线件收敛性，因 此这里着重对CGNH算法在神经网络学习应用进行重点阐述。CGNH算法的神经网络训练函数茶于Malh-Works公司神 经网络T.具箱，按照图1所示的算法流程，垠后调试编制，得到 CGNH订;丿;的神经网络训练函数traincgnh.m.训练函数集成了 共純梯度的儿类基本公式，如PRP、HS、FR、DY等算法，以及基 本公式的杂交形式，如Touati-Ahmrd捉出的PH K-EK杂交 FRFR算法（Pk =max（0>minpA）.Gilbert 等的改进（pA=max（-pA »pjp fRg|Yminp.心及 Dai-Yuan 的 DY
19、-HS 算法（=max0«min（pA '）英中杂交克法DY-HS仅使用Wolfe线捜索就八冇全局 收敛件其学习效果可与P K P相媲美：特别对较闲难的优化问 题，其解建至优J： PKI-L因此在该文的仿罠实例中，分别将基 T- PRP 法的 CGNH 和 PRP堆 T DY-HS 法的 CGNH 和 DY- HS.il行了算法对比与分析，以期从定M的角度认识CGNH算 法的优势.4.1仿貞实例逼近非线 M.函数:y=0.9sin（ irx）cos（ 2irr）»训练样本集Q,刃口 w卜1,1卜等间距取值，间距为0.02 山x通过函数计算得到。共计101个样木.神经
20、网络结构：三层结构1-10-U总元激活函数:tansig函数。最大迭代次数：800次.对比算法:CGNH（PRP）与 PRP，CGNH（DY-HS）与 DY-HS 算法，収CGNH的牛顿迭代步NDslep*3° 4.2仿真结果在相同初始条件下绘大迭代800次，见图2.4.3结果分析图2所示.DY-HS算法结果明显好于PKP.印证了文献2 的论述。另外,CGNH分别在两类不同算法F都表现出良好的 特性，其收敛速度明显大于PRP与DY-HS： fifi着迭代次数的増 加，F隼速度的优势愈加明显；当运行相同迭代次数后.CGNH 的极小值人体等于相应算法极小值的1/2。5结论综上所述.CGN
21、H算法基J：重心动共純梯度，能够保证算 法的收敛性，算法推导中没有对共«构造n法的特别要求因 此可积极有效地利用性质好的构造公式,适应性很强.实例仿 真结果也从另外角度说明,CGNH算法具有极好的收敛速度。CGNH中的可调参数是牛顿迭代步NDsteps选择不同迭 代步对算法收敛速度的影响，以及如何根据H标函数的实际性 质进行启发式设世牛顿迭代步是今肓工作的-个方而：另外， 当网络规模较大时，按照4步取启策略势必影响整个算法的 效华，而基于Beale-Powell的重启动算法，其董启次数一般小 T-CGNH如何适应该类启动策略以及览法收敛性的数学证 明是另一重要内容。（收稿口期：200
22、4年5月）（下转172页）5分段存储CAM+SRAM方案的优缺点分段存储CAM-SRAM方案综合利用了 SKAM宽度大成 本低和CAM速度快的优点，在现右技术和实现成本Z间作r 折中，该方案的优点足：（1）路山茂找速度快：6个时钟周期完成对一个报头的査 衣，时间为60ns（时钟采用1 OOMhz时），等效分组转发率人T 5GI）ps«（2）路由存储数盘大：可存储5I2K条路山，满足核心路由 器的嬰求。（3）实现简单：比多块CAM并联的实现方案所用器件少， 因此破件实现也简单得多。（4）价格合理：比较时贵的CAM使用两块.SKAM比较便 宜，总的价格合理.该方案的缺点足：更新衣项相对时
23、间较长：更新表项需要11个时钟周 期，典型时间为110m（时钟采用1 OOMhz时）.表项更新相对复杂：表琐更新时要首先更新CAM中存 储的关键了，然后更新SKAM中“储的査农结果.相对多块CAM并联的实现方法复杂一点.笔者在设计实现时试图克服这些缺点，例如引入流水机 制，增加I査农速度：在无査衣请求的间隙进疔仓农更新，尽虽使 表项更新不影响系统的件能.该方案己经在国家“863”匝点项 目“叭6路由器”中得到了实现，取得了很好的效果。(收稿口期：2004年10月)参考文献1. Douglas E Comer.lntemetworking With TCP/IP V01: Principles.
24、 Pro- twols. Architectures2. Marcus Goncalves.Killv Niles.lPV6 NETWORK<3P GupUbS Lin.N Mckeown.Routing Lookups in Hardware al Memory Access Spee<14C|.In：Proceeding of IEEE INFOCOM 98,1998:801-8094. Willibald Doeringer Gunter Karjoth. Mehdi Nasselii.Routing on Ijoii- gest Matching Prefixes)JjJE
25、EE/ACM Transactions on Networking* 1996： 4(1):86-97A McAuley P Francis.East Kouting fable Ijookup Lsing CAMsC|. In：Proceedings uf INFOCOM 93 1993： 13827391（上接86页）(a)(b)图2 CGNH分别与PK1I)-HS対比曲线参考文献1.Powell 1 J D.Restart procedure for the conjugate gradient meth<Ml(J|. Math Program, 1977:2:241-2542戴啜
26、红克亚湘尊线性共钝梯度法|1I:海：I:海科学技术出版社， 20003. Grippo L» Lucidi S.A globally convergent version of the Polak-Bibiere conjugate gradient nwthods|R|.Technical Report 94-011 Jiist of Applied Mathematics* Beijing：Chinese Academy of Science* 19944. Dai Y H«Yuan Y.Convergence of the Fletcher-Reeves Method
27、 under A Generalized Wolfe Search!J |.Journal Computational Malhemalics of Chinese Universities* 1996； (2 )s 142 -1485. Dai Y H Yuan Y.A nonlinear Conjugate Gradient with a Strong Global Convergence PropertylJ.SIAM Journal of Optimization. 2000： 10:177-1826. Dai 、 JI. Some new properties of a nonlin
28、ear conjugate gradient method| K |.Kesearch “port ICM-98-010- Institute of Computational Matheniatics and Science/ Engineering Computing Beijing ： Chinese Academy of Science. 19987. 袁X湘 II线性规划数值h法海：上海科学技术出版礼.1993 &席少霖非线性最优化方法M北京：髙等教育卄I版补.19929. Cohen A.Rate of convergence of several conjugate gr
29、adient algorithni|J|. SIAM Numer J.Anal. 1972:9:248-25910. Elelcher R. Practical Methods of Optimization! M ).2nd edition Chichester：John Wiley & Sons. 198711 .Beale E M L.A derivative of conjugate gradient|C|.ln: Lootsma F A e<I.NutiM*ricul methods for nonlinear optimization London： Academic Press. 1972:39-4312.Haykin S冷叶世伟尊译.神婭网络康理町北京：机械I业出扳社, 2()04172 2004.35 计够机工程与应用