模式识别小论文

模式识别课程小论文论文题目：梯度下降算法的学习学院：专业：学号：姓名：指导教师：二〇一二年十二月二十六日摘要梯度法，又名最速下降法。早的求解无约束多元函数极值的数值方法，早在1847年就已由柯西(Cauchy))提出。它是导出其他更为实用、更为有效的优化方法的理论基础。因此，梯度法是无约束优化方法中最基本的方法之一。梯度下降法，就是利用负梯度方向来决定每次迭代的新的搜索方向，使得每次迭代能使待优化的目标函数逐步减小。关键词：梯度下降法，负梯度，迭代1、引言：模式识别(PatternRecognition)是人类的一项基本智能，在日常生活中，人们经常在进行“模式识别”。随着20世纪40年代计算机的出现以及50年代人工智能的兴起，人们当然也希望能用计算机来代替或扩展人类的部分脑力劳动。模式识别在20世纪60年代初迅速发展并成为一门新学科。模式识别(PatternRecognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。2、梯度下降法原理：一个可微函数某点处的梯度给出了函数在该点的变化率取最大方向，梯度模等于这个方向的方向导数。负梯度方向给出了函数下降最快的方向。对于有极小值的函数来说，我们采用梯度下降法沿负梯度方向选择适当的步长进行搜索，求解函数的极小值点w*。采用最优化技术求线性判别函数中的增广权矢量时，首先需要构造准则函数。构造准则函数：)''()(xwxwkwJ(k0)（1）当0'xw时，0'2''xwxwxw；当0'xw时，0''xwxw，)(wJ有极小值0minwJ，所以对于已符号规范化的训练模式，应当寻求使)(wJ取极小时的w,因此时的w满足0'xw。令21k，求得准则函数的梯度xxwxwJwJ)'sgn(21)(（2）为防止)(wJ取极小值时出现0'xw的情况，这里令符号函数0',10',1)'sgn(xwxwxw由梯度下降法，增广权矢量的修正迭代公式为0;0)(',)(0)('),('sgn2)())(()()1(kkkkkkkkkkxkwxkwxkwkwxxkwxkwkwJkwkw若若（3）当k为常数时，上面准则下的梯度下降法的迭代公式与感知器训练算法是一致的。表明，感知器算法是梯度下降法的一种情况。k取常数时，这种梯度下降法也称为固定增量法。若取得较小，收敛速度就较慢；若取得较大，收敛加快，但当搜索接近极值点时可能产生过调引起振荡。一般的，k应随着搜索步数的增加而逐渐变小。在迭代过程中k随k而变化，则称为可变增量法。在迭代中，我们希望用kx修正)(kw，使)1(kw有0)1('kxkw迭代式kkxkwkw)()1(两边和kx数积并利用上式，可得步长应满足2)('kkkxxkw（4）在上述算法中，每次迭代时，我们只考虑用一个训练模式修正权矢量，实际上，我们也可以几个训练模式一起考虑。设分属1w和2w类的训练模式1x，2x…Nx已符号规范化，如果他们是线性可分的，则存在w使Nixwi...,2,1,0'（5）设在训练中只有一部分训练模式满足上述不等式，而另一些训练模式不满足不等式，这部分模式我们记为集合mX，即0'jxw,(mjXx)（6）我们构造准则函数mjXxjxwwJ)'()(（7）易知，)(wJ非负，因jx被错分，则必有0'jxw，亦即0'jxw。在求得最佳解*w之前的迭代过程中，总有mjXx（集合中的元素是渐少的）使0'jxw，即)(wJ总是大于零并逐渐变小。当所求得的*w使所有的不等式（5）成立，mX成为空集，)(wJ取其最小值0*)(minwJ。对于一次准则函数采用梯度下降法，梯度mjXxjxwwJwJ)()()(（8）梯度下降法迭代公式为mjXxjkkxkwwJkwkw)()()()1(（9）式中的mX是被)(kw错分类的模式集。这个迭代式称为批量修正，（3）式称为单样本修正。3、结束语通过对课程的学习，我对模式识别这门课程有了初步的认识。现在只是大概了解其概况，知道模式识别的基本过程和原理。还需要进一步的学习和理解。在这里特别感谢吴老师的指导，课堂上引领我们，还带领我们回顾以往的知识，了解自己的不足。附：用最速下降法求解问题：22112212minf(x)x2xx4xx3x取初始点(1)Tx(1,1)，通过Matlab编程实现求解过程。公用函数如下：1、functionf=fun(X)%所求问题目标函数f=X(1)^2-2*X(1)*X(2)+4*X(2)^2+X(1)-3*X(2);end2、functiong=gfun(X)%所求问题目标函数梯度g=[2*X(1)-2*X(2)+1,-2*X(1)+8*X(2)-3];end3、functionHe=Hess(X)%所求问题目标函数Hesse矩阵n=length(X);He=zeros(n,n);He=[2,-2;-2,4];End最速下降法function[x,val,k]=grad(fun,gfun,x0)%功能：用最速下降法求无约束问题最小值%输入：x0是初始点，fun和gfun分别是目标函数和梯度%输出：x、val分别是最优点和最优值，k是迭代次数maxk=5000;%最大迭代次数rho=0.5;sigma=0.4;k=0;eps=10e-6;while(kmaxk)g=feval(gfun,x0);%计算梯度d=-g;%计算搜索方向if(norm(d)eps)break;endm=0;mk=0;while(m20)if(feval(fun,x0+rho^m*d)feval(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*d;k=k+1;endx=x0;val=feval(fun,x0);end参考文献：[1]傅鹂，龚劬，刘琼荪，何中市.数学实验.北京：科学出版社.2000.[2]袁亚湘，孙文瑜.最优化理论与方法.北京：科学出版社，1997.[3]M.RafikovandJ.MBalthazar.Optimalcontrolprobleminpopulationdynamics,ComputationalandAppliedMathematics,2005.[4]ZoutendijkG.Nonlinearprogrammingcomputationalmethods[c].In:JAbadic(Ed.),IntergerandNonlincarProgramming[A].North-Holland,Amsterdam,1970.[5]陈小君，王德人，解无约束极小问题的一个并行共轭方向法[J].高等学校计算数学学报.1986.[6]孙即祥，现代模式识别，国防科技大学出版社长沙[M].2002.[7]栗塔山等编著，最优化计算原理与算法程序，长沙，国防科技大学出版社，2001.