在看人工神经网络的时候,经常有些书提及一些提高或改善网络学习效率的方法。这里面包括很多,有很多从其它学科借鉴过来的想法,知识。其中,共轭梯度下降法就是一个比较常见,它属于二阶技术,也经常被用到无约束优化的情形下。
在神经网络的书中,这个方法总是被赋予很少的笔墨,但过于简短的描述常带来更多的疑惑。起码我没有那么多书去查阅,记下点什么是个更好的选择,一是从中能读到很有启发的产生过程,二是弥补这慢慢记忆衰退的大脑。(每天脑袋里有那么多东西跑来跑去,过目不忘,算了吧)
我这篇内容主要来自:An Introduction to the Conjugate Gradient Method Without the Agonizing Pain
, 很容易搜到,因为很多地方引用。原文的笔者是因为各个教科书(不管是什么地方啦)对此方法阐述的含含糊糊不满意,遂萌生了自己要把它解释清楚的强烈冲动,呵呵。
先阐明下应用场景:它解决的是优化问题,理念很简单,从二次型优化出发。
二次型优化有时候不是很明显有谷底嘛(以此种为例),解一下方程不就成了。但共轭梯度下降法作为一种迭代方法,而不是直接求解,当然是因为矩阵计算比较费劲,比较耗内存。但共轭梯度下降适合的是稀疏矩阵
,毕竟它需要迭代好几步的,如果矩阵比较稠密,最好的方式,你还是因式分解系数矩阵去计算吧,用不上这种逼近算法了,处理矩阵的时间可能和迭代的时间差别不大,且分解完后,求解相当方便。
给一个二次型形式: f(x) = 1/2 x'Ax - b'x + c, f'(x) = 1/2 A'x + 1/2Ax + b
A是矩阵,b是向量。当A是正定对阵矩阵的时候,f(x)在当A(x)=b的时候被最小化。其实A不对阵也无所谓,因为1/2(A' + A),这个可是对称的。
为什么正定对称矩阵有如此好的性质,讨论的时候中意它,负定,奇异非正定等都有不同的图形表象
?考虑任意点p,以及最优点x=A''b(这里仍然用''表示逆矩阵)。
f(p) = f(x) + 1/2(p-x)'A(p-x),当p!=x时,很显然f(p) = f(x).
一个点下降最快的方向 -f'(xi) = b - Axi
, 我们以ei = xi - x
,来标记我们离最终想要结果间的偏差。那么ri = b - Axi就标记我们离正确的b有多远,很容易注意到 ri = -f'(xi) = -Aei
。每一次看到r记号
,记得它等同梯度
就行了。
假设我们从x0点开始,我们沿着梯度下降的方向走,那么需要找到下一个点x1 = x0 + ar(0)
. 那么问题来了,每一次我们应该迈多大步,也就是要求那个a,这里a在一些式子里的名字叫做学习率
。
------
上面一直说的是最速下降,结合图来说一下,上了一张大图,好像是模式分类里自己贴的最大图了。当我们寻找梯度方向的时候,梯度的方向首先是垂直于(a)图的等高线的,(b)图的二次型才是真是的函数图像。
最开始看的时候,我脑袋里面一直认为最速下降方向是往最低点的方向指。直到自己在文章的引导表述里觉得有些说不通,无奈亲手代入点解了下结果,才发现自己错了,梯度的方向是如(a)图里的实线方向,平行于x1,x2平面的。(a)图一直认为最简单,都没在意,教训啊。况且对x的求导得出的结果就是关于x1,x2的一次的, 肯定是平行于坐标平面,说简单点就是解出来的f'(x)就是平面上一点。
(b)图里的平面和抛物面的交线是个抛物线,梯度下降的候选点就在这条抛物线上。到哪个点最低,好像大家在(c)图上一眼就看的出来,但程序不知道啊,会试图在这条抛物线上(也等同于就是在梯度下降的那条实线上)做搜索。当上面的学习率式子对a求导的时候,会得到
d(f(x1))/da = f'(x1)'r(0)
。
这个结果一出,自然而然,与上一个点的梯度方向垂直的点是最速下降的。这个点自然是抛物线上的最低点的,不用怀疑。
直接引用结果了哈, a = r(0)'r(0)/r(0)'Ar(0)
在最速下降这一块,得到的式子也就是这个 x(i+1) = x(i) + a(i)r(i)
如果两边都乘以-A,再加上b,那么上式就变成下式
r(i+1) = r(i) - a(i)Ar(i)
这样有什么好处呢,因为变换前的式子的最速下降算法的最大开销在于每次的矩阵乘法运算
,包括两次,一次求r(i),一次求a(i), 变换后的话就可以只有一次矩阵乘法[Ar(i)]就可以了,保存起来第二次调用直接用。当然r(0)那一次矩阵运算还是免不掉的。
一点点最速下降也写了这么多文字,不过还是记详细点好。自己作为寥寥的几个看官,再次回到这页面的时候若想追究些细节还有迹可循。
文章分几节来写比较好,所以分割此篇作为(1)。
还是会往共轭下降方向走,下面会从特征向量方向切入。
分享到:
相关推荐
具有全局收敛性的新型HS-DY谱共轭梯度算法,全笑林,朱胜坤,针对无约束优化问题,提出一种基于HS方法和DY方法的新型谱共轭梯度方法.新型谱共轭梯度方法在迭代过程中不依赖任何线搜索而产生充�
大数据-算法-几类共轭梯度算法的研究.pdf
云计算-基于预处理共轭梯度法的给水管网水力计算及应用.pdf
大数据-算法-非线性共轭梯度法的全局收敛性研究.pdf
共轭梯度法,最速下降法,共轭方向法与众多优化方法的直观理解。华南理工大学---最优化
本文对迭代盲目去卷积复原方法进行了研究,提出了基于频域共轭梯度法的交替迭代优化复原算法,在频域上构造了关于目标图像和点扩展函数频谱的误差代价函数,将共轭梯度法引入到频谱误差代价函数的极小化过程中,并将...
完整的二维非线性共轭梯度反演源代码,作者是Mackie 和Rodi
利用共轭梯度法和含有两个方向调控参数的谱共轭梯度法,结合LS方法与CD方法给出混合的共轭参数和相应的谱参数,建立采用标准Wolfe线搜索的谱共轭梯度算法,证明了算法满足下降性和全局收敛性,数值试验显示算法是有效的,...
为了有效地求解二次规划逆问题,提出了一种求解其对偶问题的子问题的光滑化信赖域共轭梯度法。该方法采用增广拉格朗日法求解其对偶问题,引入光滑函数将对偶问题的子问题转换成连续的无约束优化问题,将信赖域法与共...
使用非线性共轭梯度法求解优化问题,使用matlab编程求解,是最优化方向的基本代码
matlab共轭梯度法求目标函数的最小极值-共轭梯度-王.rar 我是地球物理专业的一名学生,把自己实习的作业发上来大家分享下
共轭梯度法共轭梯度法原理共轭梯度法原理共轭梯度法原理共轭梯度法原理
针对基本人工鱼群算法运算精度低和效率差的缺点,将共轭梯度法引入基本人工鱼群算法中,得到改进的人工鱼群算法。算法对每条人工鱼分别进行聚群算子和追尾算子,若更新结果没有得到改善,则利用共轭梯度法进行更新。...
matlab预处理共轭梯度法求解线性方程组的函数文件
共轭梯度法中CD(Dixon)法的 MATLAB代码
共轭梯度法的matlab代码
梯度下降法 和 共轭梯度下降 python实现.zip
用精确线搜索的共轭梯度法,求问题的极小点
基于共轭梯度法的详细案例,共轭梯度法是最优化方法的其中一种优化方案。通过变分法求解线性方程组。方向是在求出梯度方向的前提下,添加正则项,使得前后两次方向互为共轭所得出的方向向量。