本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
拟牛顿算法是一种二阶优化算法，它改善了牛顿法中需要计算Hessian矩阵的缺点，降低了实现难度
本文讲解拟牛顿算法的思想、迭代公式、算法流程，并对相关公式进行推导与详细讲解
通过本文，可以快速了解拟牛顿算法是什么、有什么特点，以及它的具体迭代公式和算法流程
本节介绍拟牛顿算法的思想，快速了解拟牛顿法是什么
拟牛顿算法是什么
拟牛顿法并不是某个优化算法，而是从牛顿法中延伸出来的一类型优化算法
牛顿法的迭代公式如下：
在牛顿法中，每次都使用泰勒展开来获得当前点附近的近似二次曲面
这使得牛顿法需要计算Hession矩阵H，并在迭代公式中计算Hession矩阵的逆
因此，拟牛顿法为了避开计算，它将牛顿法中所用的二次曲面的条件放松
如图所示，拟牛顿法并不要求二次曲面在点附近完全的近似目标函数
而是只要求：
（1）在点与目标函数相切
（2）在点与目标函数导数一致(即曲率一致)
（3）二次曲面取得的是极小值
实际就是限制二次曲面的切点、开口宽度、开口方向
可以注意到，拟牛顿法并没有改变牛顿法中的切点，因此它们所用的二次曲面的常数项、一次项是一致的
因此，从数学的角度来理解，也可以认为拟牛顿法是找另一个矩阵来替代牛顿法中的Hession矩阵或
拟牛顿法除了获取二次曲面的方法与牛顿法略为不同之外，其余地方与牛顿法一致
本节展示拟牛顿算法中的原理推导，以及迭代公式
拟牛顿法-公式推导
拟牛顿算法的核心就是如何找出符合条件的二次曲面，它要求：
（1）在点与目标函数相切
（2）在点与目标函数导数一致(即曲率一致)
（3）二次曲面取得的是极小值
因此，根据上述条件，拟牛顿算法的相关推导如下：
在处与相切的二次曲面可以表示为：
它的导数为：
令它的导数为0，即：
通过上式可求得它的最小解取值为：
因此，第k次的迭代量为：
事实上，在这里要求二次曲面在处的导数与一致
因此有：
即要求满足：
同时，为了保证迭代量是一个下降量，还需要求是正定矩阵
拟牛顿法的相关证明
为什么拟牛顿法中，B为正定矩阵时，h就一定是一个下降量呢？
推导下如：
不妨将 简记为，则有：
当B是正定矩阵时，也是正定，由可得， 这说明h与G方向不同
而梯度G是上升方向，所以自然就是一个下降方向了
拟牛顿法-迭代公式
拟牛顿法的迭代公式
拟牛顿法与牛顿法的迭代公式是类似的，用了其它矩阵来替代Hession矩阵的逆
拟牛顿法的迭代公式如下：
其中，是目标函数在处的梯度
对于，需满足如下条件：
(1)
该式称为拟牛顿条件
其中， ，即第k-1次的迭代量
，即第k-1次迭代后梯度的增量
(2) 是正定矩阵
要求是正定矩阵，是为了保障迭代量一定是下降量
的取值方法不是固定的，不同的拟牛顿算法，就有不同的取值方法
值得注意的是，拟牛顿法还有另一种表示形式，
它将上述公式中的替换为，此时拟牛顿法就相当于用替代牛顿法中的Hession矩阵
拟牛顿法的迭代步长
拟牛顿法虽然提供了迭代点，但这更多时候仅仅作为一个迭代方向
就牛顿法而言，它的迭代点未必是下降的，而拟牛顿算法的二次曲面更加的不准确，它的迭代点更加不可信
且拟牛顿法的二次曲面依赖于上一个迭代点，当迭代步长过大时，往往会使得曲面更加不准确
因此，拟牛顿法一般会配以步长搜索算法，来确保拟牛顿法的稳定性
由于拟牛顿算法的迭代方向h是一个下降方向，即步长足够小时，朝该方向一定会下降
因此，拟牛顿法在配合步长搜索算法后，可以保障每次迭代都是下降的，也就确定了算法的稳定性
常用的步长搜索算法有：线性搜索算法、可信域搜索算法等等
本节展示拟牛顿算法的算法流程
拟牛顿法-算法流程
拟牛顿法的算法流程
拟牛顿算法的流程与牛顿算法类似，具体如下：
不同的拟牛顿算法在计算B时会略有不同，所以算法流程也会有所差异
常见的拟牛顿算法有：DFP算法，BFGS算法，L-BFGS算法
其中，BFGS算法是最常用的拟牛顿算法，而L-BFGS算法则可认为是BFGS的"节省内存版本"
好了，以上就是拟牛顿算法的原理与公式介绍了~
End
评论
