数值优化的交互式教程
原文： http://www.benfrederickson.com/numerical-optimization/ 作者：Ben Frederickson
数值优化是机器学习的核心技术之一。对于许多问题，很难直接找出最佳解决方案，但设置一个衡量解决方案效果的损失函数相对容易 - 然后最小化该函数的参数以找到解决方案。
当我第一次尝试学习javascript时，我最终写了一堆数值优化程序。因为无论如何我都有这些代码，我认为提供这些算法如何工作的一些交互式可视化可能会很有趣。
这篇文章很酷的一点是代码都在浏览器中运行，这意味着您可以交互式地为每个算法设置超参数，更改初始位置，并更改正在调用的函数以更好地了解这些算法工作。
如果你想要检查它，这篇文章的所有代码都在github上，它既有最小化功能，也有所有可视化。
内尔德 - 米德 Nelder-Mead
假装你不记得任何微积分，甚至任何基本代数。你有一个功能，并告诉你需要找到最低值。
一个简单的尝试就是对相对靠近的两个点进行采样，然后重复从最大值开始：
0.png
迭代11/21，损失= 1.30662
这种方法中的明显问题是使用固定的步长：它不能接近真正的最小值而不是步长，因此它不会收敛。当显然步长应该更大时，它也会花费太多时间进入最小值。
为了克服这些问题，Nelder-Mead方法根据新点的丢失动态调整步长。如果新点比任何先前看到的值更好，它会扩展步长以加速到底部。同样，如果新点更糟，它会收缩步长以收敛最小值。
在通常的设置是一半时，收缩的步长和双步长扩大时。对于上面的一维情况，这就像一个疾驰的搜索大小加倍，直到它包含最小值，当它切换到收缩然后进行二分搜索时。
这种方法可以很容易地扩展到更高维度的例子中，所需要的只是比维度多一点 - 然后反映其余点的最差点以降低步骤。看看这个等高线图，看看它如何在2个维度中工作：
1.png
单击此图中的任意位置以使用新的初始位置重新启动。此方法将在该点处生成三角形，然后在每次迭代时将触发器翻转到最小值，根据设置根据需要进行扩展或收缩。
虽然这种方法非常简单，但它实际上在低维函数上运行得相当好。
像这样的任何直接搜索方法的最大缺点是它们都开始在更高维度函数上表现得非常糟糕。对于如上所述的1维和2维示例，Nelder-Mead表现良好 - 但机器学习模型可以增长到数百万甚至数十亿甚至数十亿的参数，并且这种方法对于具有十几个参数的简单问题不起作用。
其中一个问题是找出要走的方向：这在二维空间中并不太难，但随着维数的增长而呈指数级变得更加困难。
梯度下降
这导致了最陡峭下降的路径，看起来有点像一个球从山上滚向当地的最小区域之一：
2.png
这种方法的问题在于设置学习率。如果您将速率设置得太低， Gradient Descent将永远找到解决方案，需要采取许多微小的步骤来解决问题。设置学习率太高，它会在最小值附近疯狂振荡而不会收敛。更糟糕的是，最佳学习速率会因功能而异，因此没有一个值可以实现良好的默认值。
一个线搜索，并确保梯度充分不上不下，以防止过量服用小步-能在每次迭代这样既损失总是被降，以防止它从超调极小修改学习率。在此处启用行搜索会导致迭代次数减少，每次迭代可能需要对额外功能点进行采样。
即使使用线搜索，Gradient Descent仍然会遇到像Rosenbrocks Function这样的功能。问题是有时候最好的方向不是沿着渐变，你还需要考虑函数的曲率。
共轭梯度
共轭梯度方法试图通过将先前的搜索方向与当前梯度包括在一起以提出新的更好的搜索方向来估计被最小化的函数的曲率。
Jonathan Shewchuk撰写了一篇名为“没有痛苦痛苦的共轭梯度方法的介绍”的伟大论文，在那里他深入描述了共轭梯度法的工作原理。唯一的问题是，它比这整篇文章要长得多 - 而且它甚至没有开始谈论非线性案例，直到第四十二页（这给了我噩梦，他有什么令人痛苦的痛苦版本一定要学习就好了。
您可以在下面看到此方法的进度。采用的实际方向为红色，每次迭代的渐变用黄色箭头表示。在某些情况下，使用的搜索方向与渐变几乎相差90度，这解释了为什么Gradient Descent在此函数上存在此类问题：
3.png
另一个例子
到目前为止的例子只有1维或2维函数，这些函数对于优化来说并不是很有趣。他们还没有研究实际数据 - 这是大多数机器学习问题的正常情况。我认为作为最后一个例子，看看这些算法如何对多维缩放问题进行处理会很有趣。
这里的挑战是将一些点之间的距离矩阵转换为最接近所需距离的每个点的坐标。这样做的一种方法是最小化以下功能：
我在这里使用的数据是北美主要城市之间的距离，目标是使用这些数据来建立这些城市的地图。通过20个城市之间的距离涉及最小化40个参数的功能：
4.png
这种可视化非常清楚地展示了几件事：
- Nelder-Mead方法完全失败了超过10个城市，甚至在此之前与其他方法相比都在挣扎。
- 如果您具有适当的学习率，则梯度下降效果很好，但最佳学习率随城市数量而变化。将学习率设置得太高会导致这种情况不会收敛，而太低则会导致它永远消失。
- 使用具有渐变下降的线搜索会导致锯齿形图案，使用“共轭渐变”方法对其进行平滑处理。
进一步阅读
如果你已经阅读了这篇文章，你可能已经发现，这篇文章只是一个借口让我在我误入歧途的学习语言的过程中弄乱了一些javascript代码。我之前所说的一切都已经说过，通常是比我更有说服力的人。
Nocedai和Wright写了一本关于数值优化的优秀书籍，这是我对大部分内容的参考。虽然它是一个很好的资源，但我还是提到了其他一些未涵盖的技术。
塞巴斯蒂安·鲁德（Sebastian Ruder）写了一篇关于梯度下降方法的精彩概述，这些方法 更深入，尤其是在用于训练深度神经网络的大型稀疏模型上的随机梯度下降的情况下。
一种很酷的导数自由优化方法是贝叶斯优化。Eric Brochu，Mike Vlad Cora和Nando de Freitas写了一篇关于贝叶斯优化的精彩介绍。贝叶斯优化的一个有趣的应用是超参数调整 - 甚至有一家公司SigOpt为此目的提供贝叶斯优化作为服务。