摘要：一是什么是解无约束非线性规划问题最常用的方法，具有收敛速度快内存开销少等优点，在机器学习各类算法中常有它的身影。在的一阶泰勒展开为二阶泰勒展开为去掉最后的余项，得到最速下降法算法的一个前提条件就是在连续可微，并且在处的导数不为。
本文由作者林洋港授权网易云社区发布。
一、 L-BFGS是什么
L-BFGS是解无约束非线性规划问题最常用的方法，具有收敛速度快、内存开销少等优点，在机器学习各类算法中常有它的身影。简单的说，L-BFGS和梯度下降、SGD干的同样的事情，但大多数情况下收敛速度更快，这点在大规模计算中很重要。下图是深度学习Autoencoder模型不同优化方法的比较。
二、 L-BFGS“之前”的那些方法
这里的“之前”并不是说L-BFGS问世之前就已经存在的方法，而是指为了更好的理解L-BFGS需要了解的其他方法。无约束问题定义：
我们先从泰勒展开开始，这可以说是本文介绍的所有方法的基础。f在的一阶泰勒展开为
二阶泰勒展开为
去掉最后的余项，得到
2.1 最速下降法（Gradient descent）
CD算法的一个前提条件就是f在连续可微，并且在处的导数不为0。由公式1可知当第二项<0时f的值将下降。由Cauchy-Schwartz不等式可得
为最速下降方向。因此迭代公式为
满足
2.2 牛顿法（Newton method）
由于f的极值点就是满足f的导数为0，根据公式2，得到
假设Hesse矩阵可逆，由上式可得牛顿法迭代公式
牛顿法具有二次终止性的特点，即经过有限次迭代必达到极小点。例如，对于二次凸函数
A是对称正定矩阵，取任意初始点，根据公式3有
显然经过1次迭代即达到极值点。
但牛顿法要求f二次连续可微，并且Hesse矩阵满足可逆和正定两个条件；同时，牛顿方向不一定每次迭代都是下降方向。
阻尼牛顿法是牛顿法的修正，与牛顿法的区别是迭代公式增加了牛顿方向上的一维搜索，即
其中
是一维搜索得到的步长，满足
2.3 拟牛顿法（Quasi-Newton Method）
牛顿法每次迭代都需要计算处的Hesse矩阵的逆，同时Hesse矩阵也不一定是正定的。人们又提出了拟牛顿法，其基本思想是用不包含二阶导数的矩阵来近似Hesse矩阵的逆。将f在处展开成2阶泰勒级数并取近似，即
设Hesse矩阵可逆，可得
设近似矩阵为根据上述，必须满足
公式7称为拟牛顿条件。的不同构造方法，决定了不同的拟牛顿方法。
当时n阶对称正定矩阵时，满足牛顿条件的也必须是n阶对称正定矩阵。因此的一般构造策略为：取为任意n阶对称正定矩阵（通常为单位矩阵I），然后通过下式求出
称为校正矩阵。
DFP算法将校正矩阵定义为：
至此，根据公式4、5、6、7、10、11可以由得出并且不需要每次迭代计算Hesse矩阵。
BFGS算法用矩阵近似公式8中的Hesse矩阵，从而得到
将q与p互换，分别取代由DFP公式可以得到
令，从而得到BFGS公式：
从公式11和公式12可以看出，拟牛顿法每次迭代只需要根据前次迭代的即可以计算出，不需要求出Hesse矩阵的逆。
2.4 L-BFGS（limited-memory BFGS）
BFGS算法中每次迭代计算需要前次迭代得到的矩阵，该矩阵的存储空间至少为N(N+1)/2，N为特征维数，对于高维的应用场景，需要的存储空间将是非常巨大的。L-BFGS的基本思想就是通过存储前m次迭代的少量数据来替代前一次的矩阵。令y=q，s=p，公式12可以改写成
公式13展开并取前m项的近似，可得
由于ρ、V、s、y这些变量都最终可以由q、p两个向量计算得到，因此，我们只需存储最后m次的q、p向量即可算出加上对角阵H0，总共需要存储2*m+1个N维向量（实际应用中m一般取4到7之间的值，因此需要存储的数据远小于Hesse矩阵）。
注：公式4中步长的确定需要使用一维搜索，顾名思义，一维搜索就是沿着直线方向寻找使得目标函数值最小的参数值。一维搜索具体又分为精确一维搜索和非精确一维搜索，具体可参看相关文献。
三、 其他相关方法
由于L-BFGS是建立在目标函数的2阶泰勒展开基础上的，其前提条件就是函数的2阶导不为0。在机器学习中一般如果用L2正则都是可以满足这个条件的。如果用的是L1正则，则目标函数可能出现2阶导为0的情况。对于使用L1正则的情况，可以使用OWL-QN方法（Orthant-Wise Limited-memory Quasi-Newton），它是基于L-BFGS修改的。
据说百度首创了Shooting算法，收敛速度比L-BFGS快得多，目前还不知道怎么做的。
此外，Chih-Jen Lin（LIBSVM作者）提出的信赖域牛顿方法（Trust Region Newton Method），其收敛速度也比L-BGFS快，他开发的另一个针对大规模线性分类的软件LIBLINEAR用的就是这种优化方法。
此外，Chih-Jen Lin（LIBSVM作者）提出的信赖域牛顿方法（Trust Region Newton Method），其收敛速度也比L-BGFS快，他开发的另一个针对大规模线性分类的软件LIBLINEAR用的就是这种优化方法。
免费领取验证码、内容安全、短信发送、直播点播体验包及云服务器等套餐
更多网易技术、产品、运营经验分享请访问网易云社区。
文章来源： 网易云社区
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/25378.html
摘要：实验基础其实实现该功能的主要步骤还是需要计算出网络的损失函数以及其偏导数，具体的公式可以参考前面的博文八。生成均匀分布的伪随机数。 前言： 现在来进入sparse autoencoder的一个实例练习，参考Ng的网页教程：Exercise:Sparse Autoencoder。 这个例子所要实现的内容大概如下：从给定的很多张自然图片中截取出大小为8*8的小patches图片共10000张...
摘要：下面介绍一些值得注意的部分，有些简单解释原理，具体细节不能面面俱到，请参考专业文章主要来源实战那我们直接从拿到一个问题决定用神经网络说起。当你使用时可以适当减小学习率，跑过神经网络的都知道这个影响还蛮大。 神经网络构建好，训练不出好的效果怎么办？明明说好的拟合任意函数(一般连续)(为什么？可以参考http://neuralnetworksanddeeplearning.com/)，说好的足够...
摘要：现在，人脸识别的克星反人脸识别问世了。多伦多大学教授和研究生的团队开发了一种算法，可以动态地破坏人脸识别系统。因此，成功的攻击需要同时欺骗所有对象方案。算法对抗生成器训练给定人脸检测置信度的对抗成功率。 论文地址：https://joeybose.github.io/assets/adversarial-attacks-face.pdf在一些社交媒体平台，每次你上传照片或视频时，它的人脸识别...
阅读 2431·2023-04-25 19:31
阅读 2175·2021-11-04 16:11
阅读 2762·2021-10-08 10:05
阅读 1468·2021-09-30 09:48
阅读 2269·2019-08-30 15:56
阅读 2351·2019-08-30 15:56
阅读 2130·2019-08-30 15:53
阅读 2179·2019-08-30 15:44
