Bayesian Optimization over Permutation Spaces
Bayesian Optimization over Permutation Spaces
复制标题
DOI：
10.1609/aaai.v36i6.20604
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Aryan Deshwal;Syrine Belakaria;J. Doppa;D. Kim
中科院分区：
文献类型：
--
作者：
Aryan Deshwal;Syrine Belakaria;J. Doppa;D. Kim
在由d个对象的所有排列组成的输入空间上优化计算黑盒函数是许多现实世界应用中的重要问题。例如，在硬件设计中放置功能块，以通过仿真优化性能。总体目标是最小化函数求值的数量，以找到高性能的排列。使用贝叶斯优化（BO）框架解决这个问题的关键挑战是权衡统计模型的复杂性和捕获函数优化的易处理性。在本文中，我们提出并评估两个算法BO在置换空间（BOPS）。首先，BOPS-T采用高斯过程（GP）代理模型与肯德尔内核和一个可处理的采集函数优化方法来选择序列的排列进行评估。其次，BOPS-H采用了具有Mallow核的GP代理模型和启发式搜索方法来优化获取函数。我们从理论上分析了BOPS-T的性能，表明他们的后悔增长次线性。我们在多个合成和真实世界的基准测试中的实验表明，BOPS-T和BOPS-H在组合空间中的性能都优于最先进的BO算法。为了推动未来对这一重要问题的研究，我们向社区提供了新的资源和现实世界的基准。
Optimizing expensive to evaluate black-box functions over an input space consisting of all permutations of d objects is an important problem with many real-world applications. For example, placement of functional blocks in hardware design to optimize performance via simulations. The overall goal is to minimize the number of function evaluations to find high-performing permutations. The key challenge in solving this problem using the Bayesian optimization (BO) framework is to trade-off the complexity of statistical model and tractability of acquisition function optimization. In this paper, we propose and evaluate two algorithms for BO over Permutation Spaces (BOPS). First, BOPS-T employs Gaussian process (GP) surrogate model with Kendall kernels and a Tractable acquisition function optimization approach to select the sequence of permutations for evaluation. Second, BOPS-H employs GP surrogate model with Mallow kernels and a Heuristic search approach to optimize the acquisition function. We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for combinatorial spaces. To drive future research on this important problem, we make new resources and real-world benchmarks available to the community.