模式识别小论文
模式识别课程小论文
梯度法,又名最速下降法。早的求解无约束多元函数极值的数值方法,
论文题目: 梯度下降算法的学习
学 院: 专 业: 学 号: 姓 名: 指导教师:
二〇一二年十二月二十六日
摘要
早在1847年就已由柯西(Cauchy))提出。它是导出其他更为实用、更为有效的优化方法的理论基础。因此,梯度法是无约束优化方法中最基本的方法之一。梯度下降法,就是利用负梯度方向来决定每次迭代的新的搜索方向,使得每次迭代能使待优化的目标函数逐步减小。
关键词:梯度下降法,负梯度,迭代
1、引言:模式识别(Pattern Recognition)是人类的一项基本智能,在日常生活中,人们经常在进行“模式识别”。随着20世纪40年代计算机的出现
以及50年代人工智能的兴起,人们当然也希望能用计算机来代替或扩展人类的部分脑力劳动。模式识别在20世纪60年代初迅速发展并成为一门新学科。模式识别(Pattern Recognition)是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。
2、梯度下降法原理:
一个可微函数某点处的梯度给出了函数在该点的变化率取最大方向,梯度模等于这个方向的方向导数。负梯度方向给出了函数下降最快的方向。对于有极小值的函数来说,我们采用梯度下降法沿负梯度方向选择适当的步长进行搜索,求解函数的极小值点w*。采用最优化技术求线性判别函数中的增广权矢量时,首先需要构造准则函数。
构造准则函数:J(w)k(w'xw'x) (k>0) (1)
当w'x0w'xw'x2w'x0;当w'x0w'xw'x0,J(w)有极小值Jminw0,所以对于已符号规范化的训练模式,应当寻求使J(w)取极小时的w,因此时的w满足w'x0。令k
J(w)
1
,求得准则函数的梯度 2
J1
xsgn(w'x)x (2) w2
为防止J(w)取极小值时出现w'x0的情况,这里令符号函数
1,w'x0
sgn(w'x)
1,w'x0
由梯度下降法,增广权矢量的修正迭代公式为
w(k1)w(k)kJ(w(k))
xksgnw'kxkxk (3) 2
w(k),若w'(k)xk0
w(k)kxk,若w'(k)xk0;k0
w(k)
k
当k为常数时,上面准则下的梯度下降法的迭代公式与感知器训练算法是一致的。表明,感知器算法是梯度下降法的一种情况。k取常数时,这种梯度下降法也称为固定增量法。若取得较小,收敛速度就较慢;若取得较大,收
敛加快,但当搜索接近极值点时可能产生过调引起振荡。一般的,k应随着搜索步数的增加而逐渐变小。在迭代过程中k随k而变化,则称为可变增量法。在迭代中,我们希望用xk修正w(k),使w(k1)有
w'(k1)xk0
迭代式w(k1)w(k)kxk两边和xk数积并利用上式,可得步长应满足
k
w'(k)xk
xk
2
(4)
在上述算法中,每次迭代时,我们只考虑用一个训练模式修正权矢量,实际上,我们也可以几个训练模式一起考虑。设分属w1和w2类的训练模式x1,x2…xN已符号规范化,如果他们是线性可分的,则存在w使
w'xi0,i1,2...,N (5)
设在训练中只有一部分训练模式满足上述不等式,而另一些训练模式不满足不等式,这部分模式我们记为集合Xm,即
w'xj0,(xjXm) (6)
我们构造准则函数
J(w)
xjXm
(w'x
j
) (7)
易知,J(w)非负,因xj被错分,则必有w'xj0,亦即w'xj0。在求得最佳解w*之前的迭代过程中,总有xjXm(集合中的元素是渐少的)使即J(w)总是大于零并逐渐变小。当所求得的w*使所有的不等式(5)w'xj0,
成立,Xm成为空集,J(w)取其最小值Jmin(w*)0。对于一次准则函数采用梯度下降法,梯度
J(w)
梯度下降法迭代公式为
J(w)
(xj) (8) wxjXm
w(k1)w(k)kJ(w)w(k)k
xjXm
x
j
(9)
式中的Xm是被w(k)错分类的模式集。这个迭代式称为批量修正,(3)式称为单样本修正。
3、结束语
通过对课程的学习,我对模式识别这门课程有了初步的认识。现在只是大概了解其概况,知道模式识别的基本过程和原理。还需要进一步的学习和理解。在这里特别感谢吴老师的指导,课堂上引领我们,还带领我们回顾以往的知识,了解自己的不足。
附:用最速下降法求解问题:
22
minf(x)x12x1x24x2x13x2取初始点x(1)(1,1)T,通过Matlab编程实现
求解过程。
公用函数如下:
1、function f= fun( X ) %所求问题目标函数
f=X(1)^2-2*X(1)*X(2)+4*X(2)^2+X(1)-3*X(2); end
2、function g= gfun( X ) %所求问题目标函数梯度
g=[2*X(1)-2*X(2)+1,-2*X(1)+8*X(2)-3]; end
3、function He = 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(k
g=feval(gfun,x0);%计算梯度
d=-g;%计算搜索方向 if(norm(d)
if(feval(fun,x0+rho^m*d)
x0=x0+rho^mk*d; k=k+1; end x=x0;
val=feval(fun,x0); end
参考文献:
[1]傅鹂,龚劬,刘琼荪,何中市.数学实验.北京:科学出版社.2000. [2]袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997.
[3]M.Rafikov and J.M Balthazar.Optimal control problem in population dynamics,Computational and Applied Mathematics,2005. [4]Zoutendijk
G.Nonlinear
programming
computational
methods
[c].In:J
Abadic(Ed.),IntergerandNonlincar Programming[A].North-Holland,Amsterdam,1970. [5]陈小君,王德人,解无约束极小问题的一个并行共轭方向法[J].高等学校计算数学学报.1986.
[6]孙即祥,现代模式识别,国防科技大学出版社 长沙[M]. 2002.
[7]栗塔山等编著,最优化计算原理与算法程序,长沙,国防科技大学出版社,2001.