ganggouren
在非解构的一天
L-BFGS
我们先来看看维基百科中关于BFGS的描述：
In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems.
The BFGS method belongs to quasi-Newton methods, a class of hill-climbing optimizationtechniques that seek a stationary point of a (preferably twice continuously differentiable) function.
几个加粗关键词已经勾勒出BFGS方法的全貌，它是一种通过迭代进行数值优化（统称求极小值）的拟牛顿方法，可以搜索局部最优解。为了帮助理解，可以回忆硕士时学过的牛顿法解非线性方程（数值分析），区别在于后者是通过迭代寻根。牛顿法就是用泰勒展开去线性化非线性方程，以一阶泰勒展开为例：
方程求解的目标为：
而数值优化的目标为：
则只要保证：
就能保证每次迭代函数值都在下降，则可以构造迭代格式（α为搜索步长，标量）：
这就是梯度下降方法（Gradient Descent），这个公式也表明搜索方向一定要与梯度方向相反。梯度下降方法条件简单，但收敛速度慢，因此在二阶泰勒展开的基础上构造迭代格式，令一阶导数为0，则将目标从求最小值变为了方程寻根：
考虑高维情况，则二阶导数为Hessian矩阵，因此最后构造的迭代格式为：
至此快速完成了牛顿迭代方法的推导。但BFGS是一种拟牛顿法，接下来将说明为什么需要去“拟”牛顿。
问题的关键在于其中的Hessian矩阵。首先，求解Hessian矩阵需要原函数二阶可微，条件苛刻。其次，在高维情况计算Hessian矩阵及其逆矩阵代价很大。并且，天然的Hessian矩阵可能负定，使得搜索方向与梯度方向相同，不能保证函数下降。
但搜索方法并不需要确定某个精确的搜索方向，学者们不愿意舍弃二阶收敛速度的优势，通过割线法的思想（两点切线近似一点曲率），引入拟牛顿条件，并考虑构造Hessian矩阵或者其逆矩阵的近似矩阵，其中经过长期检验数值最稳定的构造方法就是BFGS方法。L-BFGS（Limited-memory BFGS）在BFGS的递推公式的基础上进一步近似，同时减少了对存储空间的需求。
当然，这种经典优化方法已被收录在了库中。python可直接调用scipy.optimize.minimize。
Bayesian Optimization
但现实中大部分问题都属于黑箱优化问题，无适当的函数表达式。黑箱优化方法很多，其核心为用各自逻辑去构建复杂的黑箱过程的代理模型（拟合）。
基于高斯过程回归的贝叶斯优化就是其中一种，最简单的训练模型可以通过最大似然估计实现，而优化的过程（Acquisition Function）可以采用EI（Expected Improvement）策略。这两个关键过程都有具体的函数表达式，从而可以考虑使用经典的优化算法求解。
最大似然估计
在1维算例中，似然函数的形状为：
似然函数局部最优点不多，函数光滑性良好，虽然单次L-BFGS搜索不太可能找到全局最优解，但基于分层抽样的思想，从多点开始搜索(multistart)，几乎总能够获取全局最优解。本例中将x轴分为了5段。
Acquisition Function
在1维算例中，EI的形状为：
EI与似然函数有很大差别，呈现出多峰(multimodal)特征，峰宽窄，有多个梯度为0的平台。并且随着模型样本点增加，该特征会越来越明显。因此即使是考虑了多点启动等方法，L-BFGS这类局部择优算法难以保证获取全局最优解，并且很可能滞留于平台，导致计算资源浪费。
该例中将x轴分为了5段，但最终判断为最优解的点并不是全局最优解。可以考虑以下几种方式进行优化：
1.增加抽样次数
2.使用其他全局优化算法
3.当EI的值为0时，重新搜索
但L-BFGS方法毕竟速度较全局优化方法快，大部分时候，至少能够接近最优解。本文仍使用L-BFGS+Multistart的方式进行尝试。
1维函数训练结果
训练结果良好，拟合曲线（虚线）与真实曲线（黑线）较接近，但下图的Acquisition Function峰值与上图候选点（绿点）的不对应也说明在模型训练的后期，L-BFGS方法确实很难找到Acquisition Function的全局最优解。
2维函数训练结果
使用branin函数（左图半透明）进行测试，训练结果良好。
测试
小范围测试后，通过更多次计算的统计结果来评估L-BFGS算法的适用程度。测试信息如下：
|
|
|
|
问题 |
似然函数最大值 Expected Improvement最大值 |
|
求解方法 （作为对比） |
L-BFGS（局部择优）+Multistart（5点） 遗传算法GA（全局最优） |
|
（贝叶斯优化） 测试函数 |
1维 2维（branin函数） |
|
重复次数 |
200 |
|
评价参数 |
时间：time 函数最小值：Min |
测试结果
1维函数
时间：L-BFGS比遗传算法快得多。
准确度：L-BFGS的结果稳定性稍劣于遗传算法，但两种算法的结果在最优解附近（-180至-170范围内）的频率都为0.9左右，差异很小。
2维函数
时间：L-BFGS算法仍然比遗传算法更快。
准确度：L-BFGS略高于遗传算法。
Conclusion
在低维算例的测试中，L-BFGS算法可以说是完胜遗传算法。
换一种角度思考，在Acquisition过程中，虽然不能保证每次都能选中理论最优点，但次优点也大概率是接下来几次Acquisition的最优点，仅仅是先后顺序发生了变化。而在后期时，由于EI的多峰和峰窄特性显著，局部择优方法才可能带来较大的问题。
同时，由于本测试算例的计算速度较快，因此整体时间主要受优化算法控制，当算例（如真实模型）计算缓慢时，为减少采样次数，应当更多考虑优化算法的准确性。
为了方便大家交流技术和互通行业资讯，
请添加我们“转自：非解构-公众号”微信，
加入相关讨论交流群。
