This paper focuses on Bayesian Optimization - typically considered with continuous inputs - for discrete search input spaces, including integer, categorical or graph structured input variables. In Gaussian process-based Bayesian Optimization a problem arises, as it is not straightforward to define a proper kernel on discrete input structures, where no natural notion of smoothness or similarity could be provided. We propose COMBO, a method that represents values of discrete variables as vertices of a graph and then use the diffusion kernel on that graph. As the graph size explodes with the number of categorical variables and categories, we propose the graph Cartesian product to decompose the graph into smaller sub-graphs, enabling kernel computation in linear time with respect to the number of input variables. Moreover, in our formulation we learn a scale parameter per subgraph. In empirical studies on four discrete optimization problems we demonstrate that our method is on par or outperforms the state-of-the-art in discrete Bayesian optimization.
翻译:本文侧重于 Bayesian 优化化, 通常与连续投入一起考虑, 用于离散搜索输入空间, 包括整数、 绝对值或图形结构化输入变量。 在 Gaussian 进程基础的 Bayesian 优化化中, 出现问题, 因为在离散输入结构上定义一个适当的内核并不简单, 无法提供光滑或类似的自然概念 。 我们建议COMBO, 一种代表离散变量值的方法, 作为图的顶端, 然后在该图上使用扩散内核。 由于图形大小随绝对变量和类别的数量而爆炸, 我们建议图形 Cartesian 产品将图形分解成较小的子图, 使直线时间计算输入变量的数量。 此外, 在我们的配方中, 我们从每个子图中学习一个比例参数。 在对四个离散优化问题的实验研究中, 我们证明我们的方法与离散 Bayes 优化中的状态不相容, 。