[机器学习] 超参数优化算法-SuccessiveHalving, BH与BOHB

2024-07-08 14:26:56　　点击量：

机器学习中模型性能的好坏往往与超参数(如batch size,filter size等)有密切的关系。最开始为了找到一个好的超参数，通常都是靠人工试错的方式找到"最优"超参数。但是这种方式效率太慢，所以相继提出了网格搜索(Grid Search, GS) 和 随机搜索(Random Search,RS)。

但是GS和RS这两种方法总归是盲目地搜索，所以贝叶斯优化(Bayesian Optimization,BO) 算法闪亮登场。BO算法能很好地吸取之前的超参数的经验，更快更高效地最下一次超参数的组合进行选择。但是BO算法也有它的缺点，如下：

• 对于那些具有未知平滑度和有噪声的高维、非凸函数，BO算法往往很难对其进行拟合和优化，而且通常BO算法都有很强的假设条件，而这些条件一般又很难满足。
• 为了解决上面的缺点，有的BO算法结合了启发式算法(heuristics)，但是这些方法很难做到并行化

在自动机器学习(Automatic Machine Learning, AutoML)任务中评价往往通过 k 折交叉验证获得，在大数据集的机器学习任务上，。这也影响了优化算法在自动机器学习问题上的效果。所以一些的方法被提出来，其中多保真度优化(Multi-Fidelity Optimization)[1]就是其中的一种。而多臂老虎机算法(Multi-armed Bandit Algorithm, MBA)是多保真度算法的一种。在此基础上，有两种主流的优化策略：

在贝叶斯方法中，目标函数的估计非常昂贵。 有没有更便宜的方法来估计目标函数？ 多保真优化方法就是答案。 我会告诉你：

SuccessiveHalving算法：假设有nn组超参数组合，然后对这nn组超参数均匀地分配预算并进行验证评估，根据验证结果淘汰一半表现差的超参数组，然后重复迭代上述过程直到找到最终的一个最优超参数组合。

连续减半试图为最有前途的方法提供最多的预算。 它假设所有配置都可以提前停止并且可以获得验证分数。

想象一下，您有 N 个不同的配置和 B个预算（例如时间）。 在每次迭代中，如下图所示，连续减半保留了最好的一半配置，并丢弃了一半不好的算法。 它将一直持续到我们只有一个配置。 此方法将在达到其预算的最大值时完成。

连续减半最初是在 Non-stochastic Best Arm Identification and Hyperparameter Optimization?由 Kevin Jamieson 和 Ameet Talwalkar 撰写的

在连续减半策略中， 我们将参数化为一个变量，即预算。根据BOHB论文的阐述，我们可以根据不同的场景定义不同的budget，举例如下：

1. 迭代算法的迭代数(如：神经网络的epoch、随机森林，GBDT的树的个数)

2. 机器学习算法所使用的样本数

3. 贝叶斯神经网络中MCMC链的长度

4. 深度强化学习中的尝试数

举例说明，我们定义budgetmax=1, budgetmin=18, η=2?(?= 2) 。在这里的语义表示使用100×budget%的样本。

1. 首先我们从配置空间(或称为超参空间)随机采样8个配置，实例化为8个机器学习模型。

2. 然后用1/8的训练样本训练这8个模型并在验证集得到相应的损失值。

3. 保留这8个模型中loss最低的前4个模型，其余的舍弃。

4. 依次类推，最后仅保留一个模型，并且其(可以用全部的样本进行训练)

连续减半有什么问题？

在连续减半中，我们需要在开始时选择多少配置和需要多少削减之间进行权衡。

1.Hyperband是什么

Hyperband 是随机搜索的一种变体，但使用一些 探索-利用?理论来为每种配置找到最佳时间分配。 您可以查看此 研究论文?以获取更多参考。

在介绍Hyperband之前我们需要理解怎样的超参数优化算法才算是好的算法，如果说只是为了找到最优的超参数组合而不考虑其他的因素，那么我们那可以用穷举法，把所有超参数组合都尝试一遍，这样肯定能找到最优的。但是我们都知道这样肯定不行，因为我们还需要考虑时间，计算资源等因素。而这些因素我们可以称为Budget,用𝐵表示。

假设一开始候选的超参数组合数量是𝑛，那么分配到每个超参数组的预算就是𝐵/𝑛。所以Hyperband做的事情就是在𝑛与𝐵/𝑛做权衡(tradeoff)。

上面这句话什么意思呢？也就是说如果我们希望候选的超参数越多越好，因为这样能够包含最优超参数的可能性也就越大，但是此时分配到每个超参数组的预算也就越少，那么找到最优超参数的可能性就降低了。反之亦然。所以Hyperband要做的事情就是预设尽可能多的超参数组合数量，并且每组超参数所分配的预算也尽可能的多，从而确保尽可能地找到最优超参数。

2.Hyperband算法

Hyperband算法对 Jamieson & Talwlkar(2015)提出的SuccessiveHalving算法做了扩展。是对连续减半算法的扩展， 一种基于 Bandit 的超参数优化方法?

提到了连续减半方法在选择数量配置和分配预算之间进行权衡。 为了解决这个问题，HyperBand 提出了在不同预算下频繁执行连续减半的方法，以找到最佳配置。 在下图中，您可以看到 HyperBand 与随机搜索相比具有更好的性能。

BOHB 是最先进的超参数优化算法， BOHB: Robust and Efficient Hyperparameter Optimization at Scale?由 Stefan Falkner、Aaron Klein 和 Frank Hutter BOHB 算法背后的想法是基于一个简单的问题——为什么我们要重复连续减半？ ?

BOHB 不是在连续减半之上的盲目重复方法，而是使用贝叶斯优化算法。 事实上，BOHB 结合了 HyperBand 和 BO 以有效地使用这两种算法。?

BOHB 是一种多保真优化方法，这些方法取决于预算，因此找到相应的预算很重要。 另一方面，BOHB 是健壮、灵活和可扩展的。 如果您需要更详细的信息，您可能需要查看 博客文章?由 André Biedenkapp 和 Frank Hutter 撰写的关于 BOHB

此外， HpBandSter?是 BOHB 和 HyperBand 的一个很好的实现。 找到它的文档 在这里?。

如下是Hyperband算法步骤：

您可以在 automl.org 的 HpBandSter?GitHub 页面中 HyperBand?。 如果您对如何使用这个 Python 工具感到好奇，请查看 文档?。

• r: 单个超参数组合实际所能分配的预算；
• R: 单个超参数组合所能分配的最大预算；
• 𝑠𝑚𝑎𝑥: 用来控制总预算的大小。上面算法中𝑠𝑚𝑎𝑥=?𝑙𝑜𝑔𝜂(𝑅)?,当然也可以定义为𝑠𝑚𝑎𝑥=?𝑙𝑜𝑔𝜂(𝑛𝑚𝑎𝑥)?
• B: 总共的预算,𝐵=(𝑠𝑚𝑎𝑥+1)𝑅
• 𝜂: 用于控制每次迭代后淘汰参数设置的比例
• get_hyperparameter_configuration(n):采样得到n组不同的超参数设置
• run_then_return_val_loss(t,ri):根据指定的参数设置和预算计算valid loss。𝐿表示在预算为𝑟𝑖的情况下各个超参数设置的验证误差
• top_k(𝑇,𝐿,?𝑛𝑖/𝜂?):第三个参数表示需要选择top k(𝑘=𝑛𝑖/𝜂)参数设置。

注意上述算法中对超参数设置采样使用的是均匀随机采样，所以有算法在此基础上结合贝叶斯进行采样，提出了BOHB:Practical Hyperparameter Optimization for Deep Learning

3.Hyperband算法例子

文中给出了一个基于MNIST数据集的示例，并将迭代次数定义为预算(Budget),即一个epoch代表一个预算。超参数搜索空间包括学习率，batch size,kernel数量等。

令𝑅=81,𝜂=3，所以𝑠𝑚𝑎𝑥=4, B=(4+1)×81

下图给出了需要训练的超参数组和数量和每组超参数资源分配情况。

由算法可以知道有两个loop，其中inner loop表示SuccessiveHalving算法。再结合下图左边的表格，每次的inner loop，用于评估的超参数组合数量越来越少，与此同时单个超参数组合能分配的预算也逐渐增加，所以这个过程能更快地找到合适的超参数。

右边的图给出了不同𝑠对搜索结果的影响，可以看到𝑠=0或者𝑠=4并不是最好的，所以并不是说𝑠越大越好。

BOHB（贝叶斯优化和超频带）混合了超频带算法和贝叶斯优化。 您可以查看这篇 文章?以供进一步参考。

平等的基础上进行实验，使用 HpBandSter?，它具有 BOHB 的实现，HyperBand 和 RandomSearch 作为优化器。 官方示例可以在 这里?。 基于这个例子，我们在 Pytorch 中有一个小型 CNN，它将针对 MNIST?数据集进行调整。 我基于三个不同的优化器运行了这个示例：

对于每个优化器，我使用了以下预算：

这意味着我们已经运行了不同的组合，至少 26 次实验来检查优化器的能力（BOHB、Hyperband、随机搜索）。 此外，通过这个例子，我们希望根据以下超参数找到 CNN 的最佳配置。

在这里，您可以看到 n_iteration=3 和 max_budget=3 的优化器之间的鲜明对比。 我发现如果我增加迭代次数，所有优化器最终都会获得最佳性能，但是当预算有限时，BOHB 可以做得更好。

HyperBand and BOHB: Understanding State of the Art Hyperparameter Optimization Algorithms - neptune.aihttps://neptune.ai/blog/hyperband-and-bohb-understanding-state-of-the-art-hyperparameter-optimization-algorithms

机器学习超参数优化算法-Hyperband - marsggbo - 博客园

Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization

AutoML | BOHB: Robust and Efficient Hyperparameter Optimization at Scale