《迭代优化》由会员分享，可在线阅读，更多相关《迭代优化（17页珍藏版）》请在金锄头文库上搜索。
1、汪婷婷 华东师范大学计算机系,梯度下降法 共轭梯度法(Conjugate Gradient Method) -最速下降法(Steepest Descent) 近似牛顿法(Quasi-Newton Method),ECNU, 2014,梯度下降法,ECNU, 2016,例如N=3，我们可得到如下的超平面,ECNU, 2014,梯度下降法,我们随机在超平面上取一个点，对应我们的初始值，然后每次改变一点，使J()也改变J()，只要能保证J0就一直更新直到J()不再减少为止。具体如下： 1. 随机初始化； 2. 对于每一个i选择合适的i，使得J(+)J()0,如果找不到这样的，则结束算法； 3. 对于
2、每一个i进行更新：i=i+i，回到第2步。 那么如何找到所谓合适的呢？由梯度的定义可以得到： 要如何保证J()0呢？ 我们只需另一个 这样的求取向量各个维度相对于J()的偏导数实际上就是求取J()的梯度。梯度表示J()变化最大的方向，想象一个球在上面的图中上方滚下来，而我们的做法是使他沿着最陡的方向滚。,ECNU, 2014,梯度下降法,梯度下降法(gradient descent)，完整算法如下： 由于每次计算梯度都需要用到所有N条训练数据，所以这种算法也叫批量梯度下降法(Batch gradient descent)。在实际情况中，有时候我们的训练数据数以亿计，那么这样的批量计算消耗太大了
3、，所以我们可以近似计算梯度，也就是只取M(MN)条 数据来计算梯度，这种做法是现在最流行的训练神经网络算法，叫mini-batch gradient descent。 最极端的，我们只用一条训练数据来计算梯度，此时这样的算法叫做随机梯度下降法(stochastic gradient descent)，适合数据是流式数据，一次只给一条训练数据。,ECNU, 2014,梯度下降法,举一个非常简单的例子，如求函数 的最小值。利用梯度下降的方法解题步骤如下： 1、求梯度， 2、向梯度相反的方向移动x，如下， 其中， 为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大
4、，则不能保证每一次迭代都减少，也不能保证收敛。 3、循环迭代步骤2，直到x的值变化到使得 在两次迭代之间的差值足够小，比如0.00000001，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时 已经达到局部最小值了。 4、此时，输出x，这个x就是使得函数最小时的的取值 。,ECNU, 2014,共轭梯度法,最速下降法(Steepest Descent),ECNU, 2014,共轭梯度法,我们可以发现，每一次走的步伐和上一次都是垂直的(事实上是可以证明的，在前面我推荐的文中有详细的证明:-)，这样必然有很多步伐是平行的，造成同一 个方向要走好几次。既然同一个方向要走好几次，能不能有什么办
5、法，使得同一个方向只走一次就可以了呢？,ECNU, 2014,共轭梯度法,何谓共轭(Conjugate) 共轭梯度法(CG)最早是为了解决大规模线性方程求解提出的，比如形式: 其中A是方形对称半正定的。如果A越大并且越稀疏，导致其他线性方程求解不可行的时候，CG方法就更奏效。对于两个非零向量d(i),d(j),如果满足 我们就称d(i),d(j)是关于A共轭的，也就是说其实共轭不共轭是相对于A而言。我们知道，如果两个向量正交，他们的内积为0，所以如果两个向量关于A是共轭的，我们也可以称这两个向量关于A是正交的。,ECNU, 2014,共轭梯度法,共轭梯度法求解线性方程组 假如我们已经找到n个两
6、两共轭的方向d(i)，如果将这些方向作为基，也就可以将Ax=b的解表示为d(i)的线性组合： 如果左右分别乘上A: 也就是,ECNU, 2014,共轭梯度法,现在问题就只在于如何找到这些神奇的共轭方向了，神奇之处在于这些共轭方向可以利用迭代方式求取，可以一次只求一个这样的方向向量d(k)，这也是该算法的核心之处。如果令 那么,ECNU, 2014,上一小节中利用 Steepest Method 的优化问题如果利 用CG就变成了如图： 二维的情况下，可以保证只走两步就达到收敛,共轭梯度法,机器学习算法中，我们碰到的大部分问题都是非线性的，上面我们只是讲解了线性共轭梯度法，那么它可以解决非线性优化
7、问题吗？很遗憾，不行，但是经过修改，可以利用共轭梯度法求取局部最优解，下面展示非线性共轭梯度法的大致轮廓,对于一个非线性目标函数J() 这里又出现了i,对于的研究，著名的方法有:Hestenes-Stiefel方法、Fletcher-Reeves方法、Polak-Ribire-Polyak 方法和Dai-Yuan方法，分别对应于：,ECNU, 2014,共轭梯度法,需要注意的是，非线性共轭梯度法并不能像解决线性系统那样，保证n步内收敛，一般我们迭代很多次直到|rk|r0|。像CG这样高效的方法，一般都有现成的工具库可以使用，只要我们提供目标函数的一次导函数和初始值，CG就能帮我们找到我们想要的
8、了,ECNU, 2014,近似牛顿法,我们高中的时候数学课本上介绍过牛顿求根法，具体的做法是：对于一个连续可导的函数f(x)，我们如何求取它的零点呢，看看维基百科是如何展示牛老师的方法: 如图所示，我们首先随机初始化x0，然后每一次利用曲线在当前xi的切线与横轴的交点作为下一个尝试点xi+1，具体更新公式： 直到f(xi)0为止。,ECNU, 2014,近似牛顿法,牛老师告诉我们一个求取函数0点的方法，那么对于我们本篇的优化问题有什么帮助呢?我们知道，函数的极值在于导数为0的点取得，那么我们可以利用牛老师的方法求得导数为0的点啊。我们目的是求取J()=0对应的，那么我们可以依样画葫芦（假设J(
9、)是二阶可导的）按照如下更新： 就是大名鼎鼎的Hession矩阵,ECNU, 2014,近似牛顿法,而牛顿法更新中: 涉及到Hession矩阵的求逆过程，对于一些参数比较多的模型，这个矩阵将非常巨大，计算也极其耗时，所以这就为什么实际项目中很少直接使用牛老师的方法 L-BFGS算法 BFGS算法就是一个比较著名的近似牛顿法。BFGS算法核心在于他利用迭代的方式(具体方式请参考上面推荐的博文，文章不长，可读性很强)近似求解Hession矩阵的逆，使得求解Hession 矩阵的逆变得不再是神话。而迭代的过程步骤是无限制的，这也会导致内存不足问题，所以工程上利用有限步骤来近似BFGS求解Hession的逆，就成了 Limit-BFGS算法。,ECNU, 2014,
