AutoML | 动态算法配置 - AutoML 机器学习

图片来源：Ina Lindauer

超参数优化是一种强大的方法，可以在许多不同的问题上实现最佳性能。然而，解决此问题的传统方法都忽略了许多算法的迭代性质。动态算法配置 (DAC) 能够泛化先前的优化方法，并处理需要在多个时间步调整的超参数优化。为了能够使用这个框架，我们需要从将算法视为黑盒的传统观点转变为更接近灰盒甚至白盒的观点，从而释放具有 DAC 的 AI 算法的全部潜力。
我们用于 DAC 的基准库提供了几个目标算法的此类灰盒和白盒版本，这些算法来自多个领域，包括 AI 规划、进化计算和深度学习。

博客文章

动态算法配置

AI 规划的动态算法配置

AI 规划利用启发式方法来搜索表现良好的解决方案。对于可以使用 AI 规划解决的各种不同问题领域，用户可以从多种启发式方法中进行选择。其中一些启发式方法更适合某些问题实例和领域。因此，在 AI 规划中采用组合方法来尝试选择最适合手头问题的启发式方法已变得很常见。然而，这些方法没有考虑到在搜索过程中不同的启发式方法可能更合适。

可以使用动态算法配置来学习根据规划系统的某些内部统计信息在启发式方法之间切换。例如，跟踪显示启发式方法本身如何执行的简单统计信息允许 DAC 学习能够在搜索过程中在启发式方法之间切换的动态策略。从理论和经验上，我们可以证明这种灵活的动态策略能够胜过理论上最佳的算法选择器。

已解决的问题实例数量。RL 对应于学习的 DAC 策略。RND 和 ALT 是两个手工制作的动态策略。在 Barman 和 Childsnack 问题域中，DAC 策略（第一列）优于理论上最佳的算法选择器（最后一列）。

进化算法的动态算法配置

在 CMA-ES 中，步长控制着种群在搜索空间中移动的速度。大的步长允许您快速跳过不感兴趣的区域（探索），而小的步长允许更集中的遍历感兴趣的区域（利用）。手工制作的启发式方法通常会根据某些进展指标来权衡小步长和大步长。直接学习在什么情况下哪个步长更可取，将使我们能够比手工制作的启发式方法更灵活地行动。为了学习这种动态配置策略，一种方法是通过使用强化学习进行动态算法配置。

通过使用 DAC，我们可以学习能够泛化到训练设置之外的策略。DAC 策略可以将学习到的步长适应转移到更高维度的函数、更长的 CMA-ES 优化轨迹以及其他函数类。

人工函数上的动态算法配置

在我们在动态算法配置 (DAC) 方面的早期工作中，我们介绍了该框架本身，并提出了将动态配置形式化为上下文马尔可夫决策过程 (cMDP)。基于这种形式化，我们提出了基于强化学习的解决方案并对其进行了评估。
为了正确研究这些方法的有效性和局限性，我们引入了人工基准测试，这些基准测试具有非常低的计算开销，同时能够使用完全控制所有方面和环境特征的方式评估 DAC 策略。具体来说，我们设计了Sigmoid 和 Luby 基准测试。

Sigmoid，顾名思义，基于 sigmoid 函数 $latex sig(t) = \frac{1}{1 + e^{-t}}$。

影响 sigmoid 函数的缩放因子（此处 $latex \alpha$）的效果，所有函数都具有拐点 $latex 0$。（原始来自 Wikimedia）

然而，为了允许在此基准测试中存在问题实例的概念，我们引入了上下文特征的概念。
这些特征（在其他设置中称为元特征）使我们能够轻松区分一个问题实例与另一个问题实例。
例如，“高度”特征可以帮助您区分山峰。

对于 Sigmoid，上下文特征是缩放因子 $latex s_{i, h}$ 和拐点 $latex p_{i, h}$，它们取决于手头的问题实例 $latex i$ 和超参数维度 $latex h$。有了这些特征，我们可以构建沿着时间轴 $latex t$ 移动并表现出不同缩放因子的复杂 Sigmoid 函数。此外，通过基于超参数维度构建上下文特征，我们可以研究动态配置策略在同时配置多个参数方面的能力。
结果 Sigmoid 如下：$latex sig(t; s_{i, h},p_{i, h})= \frac{1}{1 + e^{-s_{i, h}\cdot(t – p_{i, h})}}$。

第二个基准测试 Luby 基于 luby 序列，即 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,…；正式地，第 t 个值在序列中可以计算为

$latex l_t = \left\{\begin{array}{ll}2^{k-1}& \mathrm{if }\,t = 2^k – 1,\\l_{t – 2^{k – 1} + 1}& \mathrm{if }\,2^{k-1}\leq t < 2^k – 1.\end{array}\right.$

同样，我们可以引入上下文特征来修改原始序列。例如，我们引入了“短有效序列长度” $latex L$。这个值告诉我们有多少个正确的动作需要被执行，才能认为一个实例被解决。任何不正确的选择都需要至少一个额外的动作来抵消错误的选项。

如果您想使用建议的基准测试和一些可以学习解决它们的简单 RL 代理进行试验，
请查看源代码。您还可以查看 ECAI’20 的视频演示

我们小组关于 DAC 的完整出版物列表

S. Adriaensen 和 A. Biedenkapp 和 G. Shala 和 N. Awad 和 T. Eimer 和 M. Lindauer 和 F. Hutter
自动化动态算法配置
发表于： 人工智能研究杂志 (JAIR) 2023
链接到源代码

A. Biedenkapp 和 D. Speck 和 S. Sievers 和 F. Hutter 和 M. Lindauer 和 J. Seipp
学习用于开放列表选择的领域无关策略
发表于： 人工智能规划与强化学习研讨会 (PRL @ ICAPS’22)

A. Biedenkapp 和 N. Dang 和 M. S. Krejca 和 F. Hutter 和 C. Doerr
受理论启发的参数控制基准，用于动态算法配置
发表于： 遗传与进化计算会议 (GECCO’22) 的论文集
荣获最佳论文奖 (GECH 分组)
链接到源代码

T. Eimer 和 A. Biedenkapp 和 M. Reimer 和 S. Adriaensen 和 F. Hutter 和 M. Lindauer
DACBench：动态算法配置的基准库
发表于： 第三十届国际人工智能联合会议 (IJCAI’21)
链接到 DACBench 的源代码和配套博客文章。
链接到 IJCAI’21 的视频演示。

D. Speck 和 A. Biedenkapp 和 F. Hutter 和 R. Mattmüller 和 M. Lindauer
通过动态算法配置学习启发式选择
发表于： 第三十一届自动化规划与调度国际会议 (ICAPS’21)
链接到源代码和数据，使用 DAC 在 AI 规划中切换启发式方法。
指向视频演示，该演示是PRL@ICAPS’20研讨会论文的一个版本。

G. Shala 和 A. Biedenkapp 和 N. Awad 和 S. Adriaensen 和 M. Lindauer 和 F. Hutter
CMA-ES 中的学习步长自适应
收录于：第十六届自然启发式问题求解国际会议 (PPSN’20) 会议论文集
指向源代码和数据以及训练好的策略和配套的博客文章。
指向 PPSN’20 的视频海报演示。
A. Biedenkapp 和 H. F. Bozkurt 和 T. Eimer 和 F. Hutter 和 M. Lindauer
动态算法配置：新型元算法框架的基础
收录于：第二十四届欧洲人工智能会议 (ECAI’20) 会议论文集
指向 DAC 在人工基准测试中的源代码。指向配套的博客文章。
指向 ECAI’20 的视频演示。
A. Biedenkapp 和 H. F. Bozkurt 和 F. Hutter 和 M. Lindauer
面向算法控制的白盒基准
收录于：DSO Workshop@IJCAI’19
注意：在这项早期工作中，我们将 DAC 称为“算法控制”