Bayesian optimization is a popular method for solving the problem of global optimization of an expensive-to-evaluate black-box function. It relies on a probabilistic surrogate model of the objective function, upon which an acquisition function is built to determine where next to evaluate the objective function. In general, Bayesian optimization with Gaussian process regression operates on a continuous space. When input variables are categorical or discrete, an extra care is needed. A common approach is to use one-hot encoded or Boolean representation for categorical variables which might yield a combinatorial explosion problem. In this paper we present a method for Bayesian optimization in a combinatorial space, which can operate well in a large combinatorial space. The main idea is to use a random mapping which embeds the combinatorial space into a convex polytope in a continuous space, on which all essential process is performed to determine a solution to the black-box optimization in the combinatorial space. We describe our combinatorial Bayesian optimization algorithm and present its regret analysis. Numerical experiments demonstrate that our method shows satisfactory performance compared to existing methods.
翻译:Bayesian 优化是解决全球优化昂贵到评估黑盒功能的流行方法。 它依赖于目标函数的概率替代模型, 并以此为基础建立获取功能以确定下一个目标函数。 一般而言, 与 Gaussian 进程回归的Bayesian 优化在连续空间运行。 当输入变量是绝对或离散的时, 需要额外小心。 一个共同的方法是, 使用单热编码或 Boolean 代表法来代表可能会产生组合式爆炸问题的绝对变量。 在本文中, 我们提出了一个在组合空间优化Bayesian 的方法, 可以在大型组合空间运行良好。 主要的想法是使用随机绘图, 将组合空间嵌入一个连续空间的连接点, 进行所有必要的操作, 以确定在组合空间黑盒优化的解决方案。 我们描述我们的组合式Bayes 优化算法, 并进行遗憾分析。 数字实验表明, 我们的方法与现有方法相比, 表现得令人满意。