代码以图示为准
每轮执行推荐时,调用 advisor 的 get_suggestions 接口:
def suggest(self, suggestion_history, n_suggestions):
history_container = self.parse_suggestion_history(suggestion_history)
next_configs = self.advisor.get_suggestions(n_suggestions, history_container)
next_suggestions = [self.convert_config_to_parameter(conf) for conf in next_configs]
return next_suggestions
代码以图示为准
决赛算法介绍
赛题理解
决赛问题在初赛的基础上,对每个超参数配置提供 14 轮的多精度验证结果,供算法提前对性能可能不佳的配置验证过程执行早停。同时,总体优化预算时间减半,最多只能全量验证 50 个超参数配置,因此问题难度大大增加。如何设计好的早停算法,如何利用多精度验证数据是优化器设计的关键。
我们对本地公开的两个数据集进行了探索,发现了一些有趣的性质:
- 对于任意超参数配置,其第 14 轮的奖励均值位于前 13 轮置信区间内的概率为 95%。
- 对于任意超参数配置,其前 13 轮中任意一轮的均值比第 14 轮均值大的概率为 50%。
- 对于任意超参数配置,其 14 轮的置信区间是不断减小的,但均值曲线是任意波动的。
我们也对两两超参数配置间的关系进行了探索,比较了两两配置间前 13 轮的均值大小关系和第 14 轮的均值大小关系的一致性,发现:
- 在所有超参数配置之间,部分验证(1-13 轮)和全量验证(14 轮)均值大小关系一致的概率大于 95%。
- 在空间中最终性能前 1% 的超参数配置之间,这种一致性大约在 50% 到 70% 之间。
下图为 data-30 空间中最终奖励排名前 2 的超参数和随机 8 个超参数的奖励 - 轮次关系:
图:data-30 搜索空间中 2 个最好配置和 8 个随机配置的奖励 - 轮数曲线,包含置信上界(蓝色)、均值(红色)、置信下界(绿色)曲线。
我们在比赛开源代码仓库中提供了上述 “数据探索” 代码。
上述数据探索结果表明,根据前 13 轮的置信区间,我们可以推测第 14 轮奖励均值的位置。利用前 13 轮的均值大小关系,我们可以估计第 14 轮最终均值的大小关系,但是由于数据噪音的存在,排名靠前的超参数配置大小关系无法通过部分验证结果预估。由此我们设计了两种早停算法,分别是基于置信区间的早停和基于排名的早停,将在下一部分详细描述。
过于激进的早停策略在比赛中仍然存在问题。如果使用贝叶斯优化只对全量验证数据建模,由于总体优化预算时间很少,早停会减少可用于建模的数据量,使得模型不能得到充分训练。为解决这一问题,我们引入插值方法,增加模型可训练数据。
基于以上考量,最终我们的决赛算法在初赛贝叶斯优化算法的基础上,前期执行完整贝叶斯优化使模型得到较为充分的拟合,后期使用早停技术与插值法,加速超参数验证与搜索过程。下面将对早停模块做详细介绍。
算法核心技术——早停模块介绍
早停方法
由于超参数配置之间的部分验证轮次均值大小关系与最终均值大小关系存在一定的相关性,我们受异步多阶段早停算法 ASHA[5]的启发,设计了基于排名的早停算法:一个超参数如果到达需要判断早停的轮次,就计算其性能均值处于历史中同一轮次的超参数性能均值的排名,如果位于前 1/eta,则继续验证,否则执行早停。
依据 95% 置信区间的含义,我们还设计了另一种早停方法,即使用置信区间判断当前超参数配置是否仍有验证价值。如果某一时刻,当前验证超参数的置信区间上界差于已完全验证的性能前 10 名配置的均值,则代表至少有 95% 的可能其最终均值差于前 10 名的配置,故进行早停。使用本地数据验证,以空间中前 50 名的配置对前 1000 名的配置使用该方法进行早停,早停准确率在 99% 以上。
经过测试,结合贝叶斯优化时两种方法效果近似,我们最终选择使用基于排名的早停方法。无论是哪种方法,都需要设计执行早停的轮次。早停越早越激进,节省的验证时间越多,但是得到的数据置信度越低,后续执行插值时训练的模型就越不准确。为了权衡早停带来的时间收益和高精度验证带来的数据收益,我们选择只在第 7 轮(总共 14 轮)时判断每个配置是否应当早停。早停判断准则依据 eta=2 的 ASHA 算法,即如果当前配置均值性能处于已验证配置第 7 轮的后 50%,就进行早停。
以下代码展示了基于排名的早停方法。首先统计各个早停轮次下已验证配置的性能并进行排序(比赛中我们使用早停轮次为第 7 轮),然后判断当前配置是否处于前 1/eta(比赛中为前 1/2),否则执行早停:
# 基于排名的早停方法,prune_eta=2,prune_iters=[7]
def prune_mean_rank(self, iteration_number, running_suggestions, suggestion_history):
# 统计早停阶段上已验证配置的性能并排序
bracket = dict()
for n_iteration in self.hps['prune_iters']:
bracket[n_iteration] = list()
for suggestion in running_suggestions suggestion_history:
n_history = len(suggestion['reward'])
for n_iteration in self.hps['prune_iters']:
if n_history >= n_iteration:
bracket[n_iteration].append(suggestion['reward'][n_iteration - 1]['value'])
for n_iteration in self.hps['prune_iters']:
bracket[n_iteration].sort(reverse=True) # maximize
# 依据当前配置性能排名,决定是否早停
stop_list = [False] * len(running_suggestions)
for i, suggestion in enumerate(running_suggestions):
n_history = len(suggestion['reward'])
if n_history == CONFIDENCE_N_ITERATION:
# 当前配置已完整验证,无需早停
print('full observation. pass', i)
continue
if n_history not in self.hps['prune_iters']:
# 当前配置不处于需要早停的阶段
print('n_history: %d not in prune_iters: %s. pass %d.'
% (n_history, self.hps['prune_iters'], i))
continue
rank = bracket[n_history].index(suggestion['reward'][-1]['value'])
total_cnt = len(bracket[n_history])
# 判断当前配置性能是否处于前1/eta,否则早停
if rank / total_cnt >= 1 / self.hps['prune_eta']:
print('n_history: %d, rank: %d/%d, eta: 1/%s. PRUNE %d!'
% (n_history, rank, total_cnt, self.hps['prune_eta'], i))
stop_list[i] = True
else:
print('n_history: %d, rank: %d/%d, eta: 1/%s. continue %d.'
% (n_history, rank, total_cnt, self.hps['prune_eta'], i))
return stop_list
代码以图示为准
基于置信区间的早停方法可见我们的比赛开源代码库。
数据建模方法
对于贝叶斯优化的数据建模,我们尝试了多精度集成代理模型 MFES-HB[6]拟合多精度观测数据。该方法虽然能应对低精度噪声场景,但在决赛极其有限的优化时间限制内,可能无法快速排除噪声的干扰,导致效果不如仅使用最高精度数据建模。
我们最终选择只利用最高精度数据进行建模。为了弥补早停造成的高精度数据损失,我们引入插值方法,增加用于模型训练的数据量,具体来说,就是对早停的配置,设置一个完整验证时的性能均值,插入优化历史执行建模。对于插入值的选取,我们使用已完整验证配置的最终均值中位数进行插值。
以下为插值代码示例:
def set_impute_value(self, running_suggestions, suggestion_history):
value_list = []
for suggestion in running_suggestions suggestion_history:
n_history = len(suggestion['reward'])
if n_history != CONFIDENCE_N_ITERATION:
continue
value_list.append(suggestion['reward'][-1]['value'])
self.impute_value = np.median(value_list).item()