攻击样本生成算法之 L -BFGS（实质上是优化算法的合理实现）

转载自<a href="https://www.hankcs.com/ml/l-bfgs.html">https://www.hankcs.com/ml/l-bfgs.html</a>
<img alt="bfgs.png" height="0" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-a1de43f9f7bbd3100ab59627474cd588" width="0">译自<a href="http://aria42.com/blog/2014/12/understanding-lbfgs">《Numerical Optimization: Understanding L-BFGS》</a>，本来只想作为学习CRF的补充材料，读完后发现收获很多，把许多以前零散的知识点都串起来了。对我而言，的确比零散地看论文要轻松得多。原文并没有太多关注实现，对实现感兴趣的话推荐原作者的<a href="https://github.com/aria42/taskar/blob/master/optimize/newton.go">golang实现</a>。<img alt="梯度.png" height="0" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ec6e098bd832bcac5e353e2647b8c0fa" width="0">
数值优化是许多机器学习算法的核心。一旦你确定用什么模型，并且准备好了数据集，剩下的工作就是训练了。估计模型的参数（训练模型）通常归结为最小化一个多元函数<img alt="f(x).png" height="18" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-8a57318f33adc1e6a472d242ced3a4bb" width="33">，其中输入<img alt="CodeCogsEqn (3).png" height="11" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-0c4c3010720e61b61c079e2e4a6a7bdc" width="13">是一个高维向量，也就是模型参数。换句话说，如果你求解出：
<img alt="CodeCogsEqn (1).png" height="27" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-abb72ecb7ef81ab2b574c80ffb66348b" width="147">
那么<img alt="CodeCogsEqn (3).png" height="11" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-0c4c3010720e61b61c079e2e4a6a7bdc" width="13">*就是最佳的模型参数（当然跟你选择了什么目标函数有关系）。 
在这篇文章中，我将重点放在讲解L-BFGS算法的无约束最小化上，该算法在一些能用上批处理优化的ML问题中特别受欢迎。对于更大的数据集，则常用SGD方法，因为SGD只需要很少的迭代次数就能达到收敛。在以后的文章中，我可能会涉及这些技术，包括我个人最喜欢的AdaDelta 。
注：在整个文章中，我会假设你记得多元微积分。所以，如果你不记得什么是<a href="http://www.hankcs.com/ml/the-logistic-regression-and-the-maximum-entropy-model.html#h3-6">梯度</a>或海森矩阵，你得先复习一下。
<img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ec6e098bd832bcac5e353e2647b8c0fa">
<h2 id="h2-0">牛顿法</h2>
大多数数值优化算法都是迭代式的，它们产生一个序列，该序列最终收敛于<img alt="CodeCogsEqn (4).png" height="15" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-70deaeeb03e133c27f66cbda46ed51e2" width="18">，使得<img alt="f(x).png" height="18" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-8a57318f33adc1e6a472d242ced3a4bb" width="33">达到全局最小化。假设，我们有一个估计<img alt="屏幕快照 2016-08-11 下午8.10.12.png" height="22" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-e1bb43d8ea2074fb06987eac37a55162" width="24">，我们希望我们的下一个估计<img alt="屏幕快照 2016-08-11 下午8.11.00.png" height="18" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-fdf78a30f65f68fe9b0171593bc1272b" width="40">有这种属性：<img alt="屏幕快照 2016-08-11 下午8.11.27.png" height="22" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-59c5eac5d8f98e8faf39f309876d6c7b" width="115">。
牛顿的方法是在点<img alt="屏幕快照 2016-08-11 下午8.10.12.png" height="22" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-e1bb43d8ea2074fb06987eac37a55162" width="24">附近使用二次函数近似<img alt="屏幕快照 2016-08-11 下午8.13.06.png" height="33" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-73198780439de52e7d193551bb546e56" width="17">。假设<img alt="屏幕快照 2016-08-11 下午8.13.06.png" height="33" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-73198780439de52e7d193551bb546e56" width="17">是二次可微的，我们可以用<img alt="屏幕快照 2016-08-11 下午8.13.06.png" height="33" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-73198780439de52e7d193551bb546e56" width="17">在点<img alt="屏幕快照 2016-08-11 下午8.14.16.png" height="22" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-34ac7f3b45c0803f58cb9750e6527bf7" width="21">的泰勒展开来近似<img alt="屏幕快照 2016-08-11 下午8.13.06.png" height="33" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-73198780439de52e7d193551bb546e56" width="17">。
<img alt="屏幕快照 2016-08-11 下午8.15.12.png" height="44" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-1dbcacd7993bc44035aa3f079b3d4dce" width="396">
其中，<img alt="屏幕快照 2016-08-11 下午8.17.05.png" height="22" src="https://b