机器算法验证 - 随机搜索的“惊人隐藏力量”？ - 吾爱随笔录

随机搜索的“惊人隐藏力量”？

机器算法验证神经网络采样优化随机过程梯度下降

2022-01-31 01:28:38

我有以下问题将随机搜索优化与梯度下降优化进行比较：

基于此处提供的（惊人的）答案Optimization when Cost Function Slow to Evaluate，我意识到随机搜索非常有趣：

随机搜索

即使成本函数的评估成本很高，随机搜索仍然很有用。随机搜索很容易实现。研究人员唯一的选择是设置您希望结果位于某个分位数中的概率 ；其余的使用基本概率的结果自动进行。 $p$ $q$

假设您的分位数是，并且您希望模型结果位于所有超参数元组的前 % 的尝试的元组都不在该窗口中的概率（因为它们是从同一分布中独立随机选择的），因此至少一个元组在该区域中的概率是。综上所述，我们有 $q = 0.95$ $p=0.95$ $100\times (1-q)=5$ $n$ $q^n = 0.95^n$ $1 - 0.95^n$

$1 - q^{n} \geq p ⟹ n \geq \frac{\log (1 - p)}{\log (q)}$ $1 - q^n \ge p \implies n \ge \frac{\log(1 - p)}{\log(q)}$

在我们的具体情况下产生。 $n \ge 59$

这个结果就是为什么大多数人推荐尝试的元组进行随机搜索的原因。值得注意的是，当参数数量适中时与高斯过程不同，查询元组的数量不会随着要搜索的超参数的数量而变化；事实上，对于大量的超参数，基于高斯过程的方法可能需要多次迭代才能取得进展。 $n=60$ $n=60$

由于您对结果有多好有一个概率特征，因此该结果可以成为说服您的老板相信进行额外实验将产生边际收益递减的有说服力的工具。

使用随机搜索，您可以在数学上证明： 无论您的函数有多少维，有 95% 的概率只需要 60 次迭代即可获得所有可能解决方案中前 5% 的答案！

假设您的优化函数有 100 种可能的解决方案（这不取决于维数）。解决方案的一个示例是。 $(X_1 = x_1, X_2 = x_2.... X_n = x_n)$
前 5% 的解决方案将包括前 5 个解决方案（即提供您要优化的函数的 5 个最低值的 5 个解决方案）
次迭代” 中至少遇到前 5 个解决方案之一的概率 $n$ $\boldsymbol{1 - [(1 - 5/100)^n]}$
如果你想要这个概率，你可以解出： $\boldsymbol{1 - [(1 - 5/100)^n] = 0.95} $= 0.95$ $n$
因此，次迭代！ $\boldsymbol{n = 60}$

但令人着迷的是，无论存在多少解决方案次迭代仍然有效。例如，即使存在 1,000,000,000 个解决方案 - 您仍然只需要 60 次迭代即可确保在所有解决方案的前 5% 中遇到解决方案的概率为 0.95！ $\boldsymbol{n = 60}$

$\boldsymbol{1 - [(1 - ( (0.05 \times 1000000000) /1000000000 )^{n} )] = 0.95}$
" " 仍然是 60 次迭代！ $\boldsymbol{n}$

我的问题：基于随机搜索的这种惊人的“隐藏力量”，并进一步考虑到随机搜索比梯度下降快得多，因为随机搜索不需要您计算多维复杂损失函数的导数（例如，神经网络) ：为什么我们使用梯度下降而不是随机搜索来优化神经网络中的损失函数？

我能想到的唯一原因是，如果优化值的排名分布是“严重的负偏态”，那么前 1% 可能明显优于前 2%–5%，并且需要的迭代量在前 1% 中遇到解决方案也会显着增加：

但是即使有这样的优化分数分布，梯度下降仍然有它的优势吗？梯度下降（或随机梯度下降）真的有能力与随机搜索的这种“隐藏力量”竞争吗？如果满足某些条件，由于其有吸引力的理论特性（例如，收敛性）——梯度下降是否有能力比随机搜索更快地达到最佳解决方案（不是最佳 5%，而是最佳解决方案）？或者在具有非凸和噪声目标函数的实际应用中，梯度下降的这些“有吸引力的理论特性”是否通常不适用，并且再次 - 随机搜索的“惊人的隐藏能力”再次获胜？

简而言之：基于随机搜索这种惊人的“隐藏力量”（和速度），为什么我们使用梯度下降而不是随机搜索来优化神经网络中的损失函数？

有人可以对此发表评论吗？

注意：基于大量坚持和赞扬随机梯度下降能力的文献，我假设随机梯度下降与随机搜索相比确实具有许多优势。

注意：由提供给此问题的答案产生的相关问题：没有免费午餐定理和随机搜索

4个回答

随机搜索的一个限制是在大空间上搜索极具挑战性。即使是很小的差异也会破坏结果。

Émile Borel 1913 年的文章“Mécanique Statistique et Irréversibilité”指出，如果一百万只猴子每天在打字机上花费十个小时，它们的写作质量极不可能与图书馆的内容相媲美。当然我们理解直觉：语言是高度结构化的（不是随机的），所以随机按键不会产生连贯的文本。即使是与语言极其相似的文本也可能因一个小错误而变得不连贯。

在估计模型方面，您需要同时正确估计所有内容。与事实相差甚远，则在模型中获得正确的斜率并不是很有意义。在大量维度中，例如在神经网络中，需要同时在数千或数百万个参数中找到一个好的解决方案。这不可能随机发生！ $\hat{\beta}_1$ $y = \beta_0 + \beta_1 x +\epsilon$ $\hat{\beta}_0$

这与维度灾难直接相关。假设您的目标是找到与真实解的距离小于 0.05 的解，真实解位于单位区间的中间。使用随机抽样，这个概率是 0.1。但是随着我们将搜索空间的维度增加到单位正方形、单位立方体和更高的维度，我们的“好解决方案”（与最优解决方案的距离小于 0.05 的解决方案）所占的体积会缩小，概率使用随机抽样找到该解决方案的可能性同样会缩小。（当然，增加搜索空间的大小但保持维数不变也会迅速降低概率。）

随机搜索的“诀窍”是它声称通过在维度增长时保持概率不变来打败这个过程。这必然意味着分配给“好解决方案”的体积相应地增加，以保持分配给事件的概率不变。这几乎不是完美的，因为我们半径内的解决方案的质量更差（因为这些解决方案与真实值的平均距离更大）。
您无法知道您的搜索空间是否包含一个好的结果。随机搜索的核心假设是你的搜索空间包含一个“足够好”的配置来解决你的问题。如果“足够好”的解决方案根本不在您的搜索空间中（可能是因为您选择的区域太小），那么找到该好的解决方案的概率为 0。随机搜索只能找到前 5% 的解决方案搜索空间中解中的正概率。

您可能认为扩大搜索空间是增加胜算的好方法。虽然它可能使搜索区域包含一个非常高质量的区域，但是随着搜索空间大小的增加，在该区域中选择某物的概率迅速缩小。
高质量的模型参数通常位于狭窄的山谷中。在考虑超参数时，超参数响应面通常是逐渐变化的。空间中有很大的区域，其中许多超参数值在质量方面基本相同。此外，少量的超参数对改进模型有很大的贡献；请参阅机器学习模型的性能示例，使其对超参数的一小部分子集比其他模型更敏感？

但在估计模型参数方面，我们看到了相反的现象。例如，回归问题的可能性在其最佳值附近显着达到峰值（假设您的观察结果多于特征）；此外，随着观察次数的增加，这些峰值变得越来越“尖”。峰值最优值对于随机搜索来说是个坏消息，因为这意味着“最优区域”实际上非常小，并且所有“接近未命中”值实际上都比最优值差得多。

为了在随机搜索和梯度下降之间进行公平比较，请设置迭代预算（例如，从随机搜索得出次普通梯度下降和反向传播的神经网络拟合的模型质量与次随机搜索迭代的模型进行比较。只要梯度下降不发散，我相信它会以高概率击败随机搜索。 $n=60$ $n$ $n$

迅速获得更强有力的保证变得昂贵。你当然可以调整或来增加你会找到一个非常高质量的解决方案的保证，但是如果你算出算术，你会发现迅速变得非常大（也就是说，随机搜索很快变得昂贵）。此外，在公平的比较中，梯度下降同样会采取优化步骤，并且往往会找到比随机搜索更好的解决方案。 $p$ $q$ $n$ $n$

更多讨论，带有直观的说明：随机搜索是否取决于搜索的维数？

考虑一个具有 100 个权重的神经网络模型。如果我们只想得到正确的权重符号，暂时不要担心它们的大小。这些权重的符号有 2^100 种组合，这是一个非常大的数字。如果我们对 60 个随机权重向量进行抽样，我们将只看到该空间的一小部分，甚至不足以确信我们至少有一个解决方案，其中给定的七个权重具有正确的符号。因此，即使对于一个小型神经网络，随机抽样也很少有机会获得正确的权重符号。

当然，现在神经网络的结构意味着存在对称性，这意味着存在多个等效解决方案（例如，翻转神经元的所有输入权重及其输出权重的符号），但这并不能减少等价符号组合的数量非常多。

我怀疑部分问题确实是性能分布在最佳解决方案周围非常尖锐。因此，即使 60 个样本让您进入前 5% 的解决方案，如果搜索空间非常大，并且成本函数的最优值非常本地化，那么前 5% 的随机解决方案可能仍然是无稽之谈，您可能需要, 前 0.0005% 的解决方案或更好的解决方案以获得可接受的性能。

如果随机搜索是训练神经网络的一种有效方式，那么我希望有人会发现这一点，而不是大约 50 年的梯度下降。

随机搜索虽然对超参数搜索很有用，但主要是因为维度较低，并且模型是使用梯度下降对数据进行训练的，因此您要从一组看似不错的解决方案中进行选择，而不是随机解决方案。在这种情况下，大多数搜索空间都有很好的解决方案，并且成本函数的最优值不是高度本地化的（至少对于核学习方法而言不是）。

假设我们想用 1000 个字符的答案来回答您的问题。一种方法是对 60 1000 个字符、标点符号和空格元组进行采样。有 95% 的可能性，其中一个将在此字符限制内所有可能的 Stack Exchange 答案中最有用的 5% 内。

基本上，您指出的问题是，在所有可能解决方案的某个排名分位数内通常不是很有趣。通常，您有一些评估功能，您真正感兴趣的是最佳模型或某些当前模型与您的新参数集定义的模型之间的差异。当您优化超参数时，随机搜索很有用，因为（实际上，它并不总是有用）在超参数选择之后对参数的非随机优化已经将您限制在一类通常有用的模型中。

优化中有一个数学结果，它不像最初听起来那么有趣，称为“没有免费午餐定理”。它说对于离散问题（如@JonnyLomond 的回答），当随机搜索的性能在所有可能要优化的函数上进行平均时，没有算法可以击败随机搜索。也就是说，你有一个函数其中是一个有限的离散空间（如 1000 个字符串的空间），是一个数值的离散空间（如 1:10 或 1:1000000000 ）。只有有限多个这样的。 $f:\Omega\to L$ $\Omega$ $L$ $f$

您可以定义任何计算、等次尝试的算法，根据较早的结果选择，然后取作为你最好的结果。没有算法会优于进行平均的随机搜索。一种证明思想是将视为从等概率的可能函数中随机选择的。因为可以是任何东西，概率相等，所以在的评估独立于；你什么都学不到。 $f(\omega_1)$ $f(\omega_2)$ $n$ $\omega_{i+1}$ $\max_i f(\omega_i)$ $f$ $f$ $f$ $\omega_1,\ldots,\omega_i$ $f(\omega_{i+1})$

这个结果并不那么有趣，因为我们通常对所有可能的目标函数的平均性能不感兴趣。但这确实意味着随机搜索实际上并不是一个好的竞争对手的原因是因为我们关心的目标函数具有结构。有些具有平滑（或平滑）结构——接近最佳值的参数值比远离最佳值的参数值提供更好的输出。有时结构更复杂。但是（通常）有结构。

[no-free-lunch 定理也可能没有看起来那么有趣，因为它似乎没有连续参数空间的类似物]

其它你可能感兴趣的问题