机器算法验证 - 为什么贝叶斯优化在 20 多个维度上表现不佳？ - 吾爱随笔录

为什么贝叶斯优化在 20 多个维度上表现不佳？

机器算法验证机器学习神经网络贝叶斯正态分布优化

2022-01-30 01:30:14

我最近一直在研究贝叶斯优化，并就这个话题做了以下笔记：

与确定性函数不同，现实世界的函数是使用物理测量构建的
测量总是会有误差（例如人为误差、设计和实验误差、随机误差、测量误差）——如果您在相同条件下但在未来时间记录相同的测量，这些测量很可能与以前不同测量
因此，基于物理测量的目标函数自然是“不稳定的”——两个人可能会记录相同的测量结果，最终得到不同的值，并因此得到两个不同的目标函数。
“嘈杂”函数也是“不稳定”函数——如果我们对这个“嘈杂函数”进行顶级优化，由于记录测量时的固有误差，优化结果可能与我们正在研究的自然系统不对应。这意味着在某种意义上，我们正在处理一个更复杂版本的“苹果和橘子”。
贝叶斯优化试图通过使用记录的测量作为“钉子”并通过高斯过程的形式在这些测量上安装“马戏团帐篷”来解决这个问题。这种行为类似于“概率平滑”，并试图在统计上解释存在的测量中所有可能的未捕获变化 - 假设“数据生成过程”被高斯过程很好地表示的假设在某种程度上是正确的。
因此，贝叶斯优化试图“消除”目标函数中的噪声/变化/误差，为最终的优化解决方案添加自然的“鲁棒性”。这一切意味着贝叶斯优化有可能给我们带来更好的结果。

贝叶斯优化的优点：

鲁棒性（如上所述）
不要求目标函数是可微的（即在离散和组合优化问题中有用）
由于它不计算导数，因此与基于梯度的优化方法相比，它具有更“计算效率”的潜力。

贝叶斯优化的缺点：

需要用高斯过程很好地建模真正的目标函数
从经验上观察到在高维目标函数（即高于 20 维）上表现不佳 - 但是，我不明白为什么。

我经常听到有人声称贝叶斯优化在 20 多个维度上表现不佳，但我一直无法理解为什么会这样。我尝试在网上查阅一些参考资料：

1） “具有稀疏轴对齐子空间的高维贝叶斯优化”（Eriksson et al 2021）

“高维 BO 提出了一个特殊的挑战，部分原因是维数的诅咒使得难以定义以及推断合适的代理模型类别。”
过于僵化的模型类不太可能捕获目标函数的足够特征。灵活性和简约性之间的妥协是必不可少的。”

2）《使用低维特征空间的高维贝叶斯优化》（Moriconi et al, 2020）

“然而，BO（贝叶斯优化）实际上仅限于优化 10-20 个参数。为了将 BO 扩展到高维，我们通常对目标的分解做出结构性假设和/或利用问题的内在低维性，例如通过“使用线性投影。我们可以通过非线性投影实现更高的压缩率，但学习这些非线性嵌入通常需要大量数据。这与相对较小评估预算的 BO 目标相矛盾。”

3） “贝叶斯优化教程”（Frazier，2018）

“它（贝叶斯优化）最适合对小于 20 的连续域进行优化”
“输入 x 在 Rd 中，d 的值不太大。在 BayesOpt 的大多数成功应用中，通常 d ≤ 20。”

我的问题：在这些论文中，他们没有解释为什么“20 维”似乎是决定贝叶斯优化性能开始恶化的条件的相关阈值。

有人可以解释为什么说“20 维”是贝叶斯优化的最大阈值吗？
尽管提供了一些解释来解释贝叶斯优化在更高维度上的难度 - 有人可以帮助我更详细地理解这一点吗？

参考：
使用稀疏轴对齐子空间的高维贝叶斯优化( PDF )
贝叶斯优化教程( PDF )
使用低维特征空间的高维贝叶斯优化( PDF )

3个回答

老实说，这是因为在 20 多个维度上，一切都表现不佳。贝叶斯优化在这里并不特别。

试图在很多维度上优化任何函数是很困难的，因为高维空间的体积随着维度的数量呈指数增长。考虑一条线段 $[0, k]$ ; 有长度 $k$ . 单位平方？有面积 $k^2$ . 等等。因此，当您寻找可能的解决方案时，您必须搜索的空间量会非常、非常、快速地增加。我建议查找“维度诅咒”一词以获取更多信息。

无论您使用什么算法，这始终是正确的——除非您愿意对该函数的形状做出一些强有力的简化假设。例如，梯度下降在高维度上可以做得很好——只要你的函数是可微的。如果你有一个函数，其中除 minimum 之外的某个地方的梯度为 0，那么你就完蛋了。

贝叶斯优化是完全一样的。您链接的论文指出，如果您的函数具有有趣的结构，您可以通过选择好的先验来利用它。也就是说，您需要假设稀疏性（其中只有少数维度很重要，其余维度可以忽略）或可微性，在这种情况下您可以使用梯度增强的高斯过程。但如果你没有那种结构，你就完蛋了。

至于 20 个维度，这是经验法则。没有“阈值”或任何东西，但它会以指数方式迅速变得困难。

您将找不到该陈述的理论/科学依据，因为没有！

优化的难度与很多事情有关，维度只是其中之一，很可能甚至不是很重要的。例如，如果您只是假设目标函数的连续性而不是可微性，那么域的维度问题无论如何都会变得完全没有实际意义。使用空间填充曲线，您可以随时重新参数化 $n$ 维函数到单个变量之一。

因此，很容易找到使用 BO 无法优化的一维函数。并且很容易找到数百甚至数千维的易于优化的函数，无论是贝叶斯还是其他。

那么为什么有些人会做出这样的陈述，而其他人为什么会相信呢？

我认为这有两个原因：

它们是（在研究人员感兴趣或知道的情况下）一个很好的启发式方法。
这些陈述的完整限定条件太长了，并且会包含太多复杂的“纯理论”限定条件。许多这些资格对于在该领域工作的人来说可能是“显而易见的”，他们“不言而喻”。

是的，一般来说，高维空间很困难，但是有几件事使得使用高斯过程的贝叶斯优化在那些棘手的问题上特别令人困惑。

在我看来，高维度让 BO 变得困难并不是一个单一的原因，而是由于多种因素的共同作用。

首先，贝叶斯优化是经典的高斯过程，使用类似于平方指数内核的东西。这是一个具有很大灵活性的内核，它在低维度上是完美的，但在高维度上可能会成为一种负担，因为它对点云的太多解释赋予了合理的概率质量。所以第一个问题是我们正在使用的模型已经在努力理解正在发生的事情。

这与另一个答案中的音量参数有关。由于 GP 明确依赖于距离，当所有点间距离都相等且较大时，GP 几乎没有区分能力。

看看当我们进入更高维度时，随机点之间的距离变化小于低维度：

[ “应用贝叶斯优化的高维高斯过程建模调查”，Mickaël Binois 和 Nathan Wycoff 着 ]

正如您所提到的，将结构放入内核函数中，以便我们学习映射到低维空间，在该空间上放置“标准”高斯过程是一个很好的方法。另一种选择是假设一个核函数，它以更节俭的方式组合来自输入维度的信息，例如David K. Duvenaud、Hannes Nickisch、Carl 的 Additive Gaussian Processes Part of Advances in Neural Information Processing Systems 24 (NIPS 2011) Rasmussen）或ANOVA 内核（“条件高斯过程的 ANOVA 分解，用于依赖输入的敏感性分析”Gaëlle Chastaing，Loic Le Gratiet）。

其次，我们不能忘记 BO 是一个嵌套优化过程：每次 BO 算法想要建议下一个优化点时，它必须解决整个空间上的整个子优化问题！与原始优化问题不同，我们的高斯过程定义的获取函数（其优化点是我们在外部搜索中的下一个候选点）通常具有已知的梯度和 Hessian，这确实有助于找到局部解决方案。

然而，获取函数是出了名的非凸函数，这意味着在高维空间中，无论我们能以多快的速度找到局部最优值，我们可能几乎没有机会在不付出大量努力的情况下找到接近全局最优值的任何东西。虽然这不会影响高斯过程对未知目标建模的能力，但它确实会影响我们利用其知识进行优化的能力。

当与内核恶作剧结合使用时，有时可以在较低维空间中优化采集函数，这可以使事情变得更容易（或者在实践中有时更难；线性降维意味着我们现在正在进行线性规划而不是无约束优化，也没有t vibe well with hyperbox 约束）。

第三是超参数估计风险。这些天最流行的是“可分离”、“ARD”、“张量积”或其他轴对齐的各向异性内核，它们看起来像 $k(\mathbf{x}_1,\mathbf{x}_2) = \sigma^2 e^{\sum_{p=1}^P \frac{(x_{1,p}-x_{2,p})^2}{2\ell_p}}$ ，所以我们有一个额外的东西来估计每个输入维度，估计高斯过程超参数是困难的，无论是从统计推断的角度还是数值分析的角度。

使用参数化映射到低维只会使估计风险变得更糟（但可能会被一个显着较低方差的函数类先验抵消）。

第四：计算时间。GP 以其小数据统计效率（在错误/数据方面）和大数据计算效率低下（在推理/秒方面）而闻名。在高维中，如果我们真的想找到一个全局最优值，我们可能不得不多次评估目标函数，因此有一个大数据集供我们的 GP 考虑。这根本不是 GPs 的历史利基，因为经典的、基于分解的 GP（即，您实际上取内核矩阵的 Cholesky 的地方）推断与 $n^3$ 所以很快就会变得棘手。

采集功能的优化也只会变得更加昂贵，因为 $n$ 也上升。请记住，您必须在每次优化迭代之间执行此操作。所以如果我们有一个优化预算 $10,000$ , 天真地我们需要从字面上做所有这些数值优化 $10,000-n_{\textrm{init}}$ 次（当然，在实践中，我们会一次评估一批点，并且每隔几次迭代才优化一次超参数）。

然而，在过去的几十年里，高维的大规模 GP 推理已经真正成熟，并且已经成为最近一些大规模 GP-BO 论文的引擎。

其它你可能感兴趣的问题

上一篇如何使用 DLM 和卡尔曼滤波进行预测下一篇MaxEnt、ML、Bayes等统计推断方法的比较