梯度下降法牛顿迭代法共轭梯度法

梯度下降法、牛顿迭代法、共轭梯度法（参见：神经网络-PGM-ANN-2009-C09性能优化）优化的目的是求出目标函数的最大值点或者最小值点，这里讨论的是迭代的方法梯度下降法首先，给定一个初始猜测值，然后按照等式kkkkΡαΧ1（1）或kkkkk)(1（2）逐步修改猜测。这里向量k代表一个搜索方向，一个大于零的纯量k为学习速度，它确定了学习步长。当用kkkkΡαΧ1进行最优点迭代时，函数应该在每次迭代时都减小，即)()(1kkFF考虑)()()(21)()()()(*2*****xxxFxxxxxFxFxFTT（3）的)(XF在kX的一阶泰勒级数展开：kTkkkkkgFFF)()()(1（4）其中，Tkg为在旧猜测值kX处的梯度kFgk)(（5）要使)()(1kkFF只需要（4）中右端第二项小于0，即0kTkkkTkgg（6）选择较小的正数k。这就隐含0kTkPg。满足0kTkPg的任意向量成为一个下降方向。如果沿着此方向取足够小步长，函数一定递减。并且，最速下降的情况发生在kTkPg最小的时候，容易知道，当kk-gP时kTkPg最小，此时，方向向量与梯度方向相反。在（1）式中，令kk-gP，则有kkkkgαΧ1（7）对于式（7）中学习速率k的选取通常有两种方法：一种是选择固定的学习速率k，另一种方法是使基于学习速率k的性能指数或目标函数)(1kXF在每次迭代中最小化，即沿着梯度反方向实现最小化：kkkkgXX1。注意：1、对于较小的学习速度最速下降轨迹的路径总是与轮廓线正交，这是因为梯度与轮廓线总是正交的。2、如果改变学习速度，学习速度太大，算法会变得不稳定，振荡不会衰减，反而会增大。3、稳定的学习速率对于任意函数，确定最大可行的学习速度是不可能的，但对于二次函数，可以确定一个上界。令特征函数为：cXdAXXFTT21)x(（8）那么梯度为dAXXF)(代入最速下降法公式（7）中daXAaIdAXaXgaXXkkkkkkkkkk）（)(1（9）在动态系统中，如果矩阵][aAI的特征值小于1，则该系统是稳定的。可用赫森矩阵A的特征值来表示该矩阵的特征值，假设A的特征值和特征向量分别为n21，，和nzzz,,21，那么iiizaIzaAI)(（10）于是，最速下降法的稳定条件为1iaI（11）如果二次函数有一个强极小点，则其特征值为正数，上式可以化为ia2由于该式对于赫森矩阵的所有特征值都成立则max2a（12）分析：最大的稳定学习速度与二次函数的最大的曲率成反比。曲率说明梯度变化的快慢。如果梯度变化太快，可能会导致跳过极小点，进而使新的迭代点的梯度的值大于原迭代点的梯度的值（但方向相反）。这会导致每次迭代的步长增大。4、沿直线最小化选择学习速率的另一种方法是ka使得每次迭代的性能指数最小化，即选择ka使得下式最小：)(kkkPaXF对任意函数的这种最小化需要线性搜索。对二次函数解析线性最小化是可能的。上式对ka的导数为：kXXTkkkXXTkkkkPXFPaPXFPaXFdadkk|)(|)()(2（13）令式（13）导数为零求得TkkkkTkkXXTkXXTkPAPPgPXFPPXFakkk|)(|)(2（14）这里kA为kX的赫森矩阵：kXXkXFA|)(2牛顿法牛顿法基于二阶泰勒级数：kkTkkTkkkkkXAXXgXFXXFXF21)()()(1（15）牛顿法的原理是求)(XF的二次近似的驻点，求这个二次函数对kX的梯度并令它等于0，则有0kkkXAg（16）解得：kTgAXkk于是，牛顿法定义为kkkgAXX11k（17）注意：牛顿法总是用一个二次函数逼近)(XF,然后求其驻点，因此此方法总能够一步找到二次函数的极小点，如果原函数为二次函数（有强极小点），它就能够实现一步极小化如果)(XF不是二次函数，则牛顿法一般不能在一步内收敛，是否收敛取决于具体的函数和初始点尽管牛顿法的收敛速度通常比最速下降法快，但其表现很复杂，除了收敛到鞍点的问题外，算法还可能震荡和发散，如果学习速率不太快或每步都实现线性极小化，最速下降法能保证收敛牛顿法的另一个问题是需要对赫森矩阵及其逆阵的计算和存储共轭梯度法牛顿法有一个性质成为二次终结法（quadratictemination），即它能在有限迭代次数内使得二次函数极小化，但这需要计算和存储二阶导数，当参数个数很大时，计算所有二阶导数是很困难的。假定对下述二次函数确定极小点：cXdAXXFTT21)x(（18）当且仅当jkAPPjTk,0时，称向量集合kP对于一个正定赫森矩阵A两两共轭。因为对称矩阵的特征向量是两两正交的。已经证明，如果存在沿着一个共轭方向集,,2,1nPPP的精确线性搜索序列，就能够在最多n此搜索内实现具有n个参数的二次函数的精确极小化。注意到对于二次函数，有AXFdAXXF)()(2（19）由于kkkkXAggg1，又有kkkkkPaXXX)(1，选择ka使函数)(XF在kP方向上极小化，则共轭条件可重写称jkPgAPXAPPajTkjTkjTkk,0（20）注意，第一次搜索方向0P是任意的，而1P是与0g垂直的任意向量。所以共轭向量集的数量是无限的。通常从最速下降法的方向开始搜索：00gP每次迭代都要构造一个与nggg,,10正交的向量kP。可以将迭代形式简化为1kkkkPgP（21）通常选择1-1-kTkTkPgggkk或1-1-kTkTkggggkk或1-1-1-kTkTkggggkk综上，算法可以归纳为：1、选择如00gP的与梯度相反的方向作为第一次搜索方向2、根据kkkkkPaXXX)(11进行下一步搜索，确定ka以使函数沿搜索方向极小化3、根据kkkkPgP111确定下一个搜索方向，计算1k4、如果算法不收敛，回到第2步算法比较梯度下降法形式简单，一般情况下都能够保证收敛，但是收敛速度慢牛顿法对于二次目标函数收敛速度快，但是不能够保证收敛，而且需要对赫森矩阵及其逆阵的计算和存储共轭梯度法结合了前面两种方法的性质，收敛速度快，不需要对赫森矩阵及其逆阵的计算和存储，但是形式比前两者复杂