Kernel Learning for Sample Constrained Black-Box Optimization
样本受限黑盒优化的核学习

Rajalaxmi Rajagopalan, Yu-Lin Wei, Romit Roy Choudhury
拉贾拉克希米·拉贾戈帕兰、魏玉林、罗米特·罗伊·乔杜里

Department of Electrical & Computer Engineering
电气与计算机工程系

University of Illinois Urbana-Champaign
伊利诺伊大学厄巴纳-香槟分校

{rr30,yulinlw2,croy}@illinois.edu

Black box optimization (BBO) focuses on optimizing unknown functions in high-dimensional spaces. In many applications, sampling the unknown function is expensive, imposing a tight sample budget. Ongoing work is making progress on reducing the sample budget by learning the shape/structure of the function, known as kernel learning. We propose a new method to learn the kernel of a Gaussian Process. Our idea is to create a continuous kernel space in the latent space of a variational autoencoder, and run an auxiliary optimization to identify the best kernel. Results show that the proposed method, Kernel Optimized Blackbox Optimization (KOBO), outperforms state of the art by estimating the optimal at considerably lower sample budgets. Results hold not only across synthetic benchmark functions but also in real applications. We show that a hearing aid may be personalized with fewer audio queries to the user, or a generative model could converge to desirable images from limited user ratings.
黑盒优化（BBO）专注于在高维空间中优化未知函数。在许多应用中，对未知函数进行采样成本高昂，导致样本预算紧张。当前的研究正通过学习函数的形状/结构（即核学习）来降低样本预算。我们提出了一种学习高斯过程核的新方法，其核心思想是在变分自编码器的潜在空间中构建连续核空间，并通过辅助优化确定最佳核。实验结果表明，所提出的核优化黑盒优化方法（KOBO）能以显著更低的样本预算估计最优解，性能优于现有技术。这一优势不仅体现在合成基准函数上，也适用于实际应用场景：例如助听器可通过更少的用户音频查询实现个性化配置，或生成模型能基于有限的用户评分收敛到理想图像。

Many problems involve the optimization of an unknown objective function. Examples include personalizing content $x$ to maximize a user’s satisfaction $f\left(x\right)$ ,or training deep learning models with hyperparameters $x$ to maximize their performance $f\left(x\right)$ . Function $f\left(x\right)$ is unknown in these cases because it is embedded inside the human brain (for the case of personalization) or too complex to derive (for hyper-parameter tuning). However,for any chosen sample $x_i$ ,the value of $f\left(x_i\right)$ can be evaluated. For hearing-aid personalization, say, evaluating the function would entail playing audio with some hearing-compensation filter $x_i$ and obtaining the audio clarity score $f\left(x_i\right)$ from the user.
许多问题都涉及对未知目标函数的优化。例如：通过个性化内容 $x$ 来最大化用户满意度 $f\left(x\right)$ ，或通过超参数 $x$ 训练深度学习模型以最大化其性能 $f\left(x\right)$ 。在这些情况下，函数 $f\left(x\right)$ 是未知的，因为它要么内置于人脑中（个性化场景），要么过于复杂而无法推导（超参数调优场景）。然而对于任何选定样本 $x_i$ ，都可以评估 $f\left(x_i\right)$ 的值。以助听器个性化为例，评估该函数需要播放带有听力补偿滤波器 $x_i$ 的音频，并从用户处获取音频清晰度评分 $f\left(x_i\right)$ 。

Bayesian methods like Gaussian Process Regression (GPR) are de facto approaches to black-box optimization (BBO). Using a set of function evaluations, conventional GPR (Frazier 2018) learns a probabilistic surrogate model $\hat{f}\left(x\right)$ for $f\left(x\right)$ . The optimum is estimated on this surrogate as ${\hat{x}}^{\ast }=$ $\mathrm{argmin}-\hat{f}\left(x\right)$ . In most BBO problems, $f\left(x\right)$ is expensive to evaluate,hence a strict sample or query budget $B$ is of interest. Techniques that lower this budget have garnered recent attention. One idea is to exploit domain knowledge about
高斯过程回归（GPR）等贝叶斯方法是黑箱优化（BBO）的实际标准方法。传统 GPR（Frazier 2018）通过一组函数评估值，学习得到目标函数 $f\left(x\right)$ 的概率代理模型 $\hat{f}\left(x\right)$ ，并在此代理模型上将最优值估计为 ${\hat{x}}^{\ast }=$ $\mathrm{argmin}-\hat{f}\left(x\right)$ 。大多数 BBO 问题中， $f\left(x\right)$ 的评估成本高昂，因此严格的样本或查询预算 $B$ 至关重要。降低该预算的技术近期备受关注，其中一种思路是利用领域知识——

Figure 1: KerGPR in VAE latent space gives $K^{\ast }$ to $f$ GPR
图 1：VAE 潜在空间中的 KerGPR 为 $f$ GPR 提供 $K^{\ast }$

the rough shape of $f\left(x\right)$ ,i.e.,select a GPR kernel that models this shape. With humans,for example, $f\left(x\right)$ may have a staircase structure as they may not perceive differences in certain neighborhoods of $x$ ,but their ratings may change just outside that neighborhood. If GPR's surrogate model $\hat{f}\left(x\right)$ captures this staircase structure in its kernel,sample efficiency can improve. However, in the absence of domain knowledge,can the optimal $GPR$ kernel ${\mathbf{K}}^{\ast }$ be learnt,using the same sample queries used to estimate $x^{\ast }$ ?
$f\left(x\right)$ 的粗略形状，即选择一个能够模拟该形状的高斯过程回归（GPR）核函数。以人类为例， $f\left(x\right)$ 可能呈现阶梯状结构，因为他们可能无法感知 $x$ 某些邻近区域的差异，但他们的评分可能会在该邻近区域之外发生变化。如果 GPR 的代理模型 $\hat{f}\left(x\right)$ 在其核函数中捕捉到这种阶梯状结构，采样效率可以得到提高。然而，在缺乏领域知识的情况下，能否利用用于估计 $x^{\ast }$ 的相同样本查询来学习最优的 $GPR$ 核函数 ${\mathbf{K}}^{\ast }$ 呢？

A growing body of research (Grosse et al. 2012)(Kim and Teh 2016)(Teng et al. 2020) is concentrating on kernel learning. One effective approach is Automatic Statistician (AS) (Duvenaud et al. 2013) where authors compose complex kernels by combining simple ones through a context-free grammar and design a search method over the countably infinite complex kernels (more in Section 5). Subsequent improvements over AS have used Hellinger distance as a measure of kernel similarity (Malkomes, Schaff, and Garnett 2016). This similarity metric guides an optimization-based search over the space of composite kernels. To reduce search complexity, (Gardner et al. 2017) exploits additive structures in the search space and employs MCMC methods to discover kernels. All these techniques operate on discrete spaces, delivering a categorical composition of simple kernels.
越来越多的研究（Grosse 等人，2012 年；Kim 和 Teh，2016 年；Teng 等人，2020 年）正聚焦于核学习。其中一种有效方法是“自动统计学家”（Automatic Statistician，简称 AS）（Duvenaud 等人，2013 年），该研究通过上下文无关文法将简单核组合成复杂核，并设计了一种在可数无限复杂核空间上的搜索方法（详见第 5 节）。后续对 AS 的改进采用了 Hellinger 距离作为核相似性度量（Malkomes、Schaff 和 Garnett，2016 年），该相似性指标引导了基于优化的复合核空间搜索。为降低搜索复杂度，（Gardner 等人，2017 年）利用搜索空间中的可加结构，采用 MCMC 方法来发现核函数。所有这些技术均在离散空间操作，最终输出简单核的类别组合结果。

A continuous space of kernels naturally lends itself to optimization methods. Our contribution is in designing such a continuous kernel space and running an auxiliary optimization on it to discover ${\mathbf{K}}^{\ast }$ . To this end,we first synthesize many discrete kernels by adding or multiplying a set of simple "basis" kernels, and then use a variational autoencoder (VAE) to learn a low-dimensional continuous manifold for the discrete kernels. This manifold lives in the latent space of the VAE, as shown by the orange region in Figure 1. Conventional optimization on this latent kernel space is difficult since we lack an objective function, but given a kernel, we can evaluate its effectiveness using model evidence (i.e., how well a given kernel agrees with available samples from $f\left(x\right))$ . Thus,optimizing over the kernel space can also be designed as a blackbox optimization problem, hence we run a kernel space GPR (KerGPR) to output an optimal ${\mathbf{K}}^{\ast }$ . The main GPR module,Function $GPR$ ,uses ${\mathbf{K}}^{\ast }$ to model the surrogate function $\hat{f}\left(x\right)$ ,and queries the surrogate at more points. The new model evidence is then passed back to KerGPR (see Fig. 1) to update the optimal kernel. The iteration terminates when the query budget is expended. Function $GPR$ then outputs the minimum of the surrogate $\hat{f}\left(x\right)$ . Results show that KOBO consistently outperforms SOTA methods (namely MCMC (Gardner et al. 2017), BOMS (Malkomes, Schaff, and Garnett 2016), and CKS (Duve-naud et al. 2013)) in terms of the number of queries needed to reach the optimal. The gain from kernel learning is also significant compared to the best static kernels. Experiments are reported across synthetic benchmark functions and from real-world audio experiments with $U=6$ users. Volunteers were asked to rate the clarity of audio clips,and using $B\le$ 25 ratings, KOBO prescribed a personalized filter that maximized that user's personal satisfaction. The performance gain is robust across extensive experiments, suggesting that KOBO could be deployed in real-world black-box applications where sample-budget is of prime concern.
核的连续空间自然适用于优化方法。我们的贡献在于设计这样一个连续的核空间，并在其上运行辅助优化以发现 ${\mathbf{K}}^{\ast }$ 。为此，我们首先通过添加或乘上一组简单的“基”核来合成许多离散核，然后使用变分自编码器（VAE）为离散核学习一个低维连续流形。如图 1 中橙色区域所示，该流形存在于 VAE 的潜在空间中。由于缺乏目标函数，传统的潜在核空间优化较为困难，但给定一个核时，我们可以通过模型证据（即给定核与 $f\left(x\right))$ 的可用样本的吻合程度）评估其有效性。因此，核空间优化也可以设计为一个黑盒优化问题，为此我们运行核空间高斯过程回归（KerGPR）以输出最优的 ${\mathbf{K}}^{\ast }$ 。主 GPR 模块函数 $GPR$ 使用 ${\mathbf{K}}^{\ast }$ 建模代理函数 $\hat{f}\left(x\right)$ ，并在更多点上查询该代理。新的模型证据随后反馈给 KerGPR（见图 1）以更新最优核。 当查询预算耗尽时，迭代终止。函数 $GPR$ 随后输出代理模型 $\hat{f}\left(x\right)$ 的最小值。结果表明，在达到最优解所需的查询次数方面，KOBO 始终优于最先进的算法（即 MCMC（Gardner 等人 2017）、BOMS（Malkomes、Schaff 和 Garnett 2016）和 CKS（Duvenaud 等人 2013））。与最佳静态核函数相比，核学习带来的增益也十分显著。实验数据涵盖合成基准函数和真实音频实验（涉及 $U=6$ 名用户）。志愿者需对音频片段清晰度进行评分，基于 $B\le$ 25 份评分数据，KOBO 能生成最大化用户个人满意度的个性化滤波器。该性能增益在大量实验中表现稳健，表明 KOBO 可部署在样本预算至关重要的现实黑箱应用中。

Copyright © 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
版权所有 © 2025，美国人工智能促进协会（www.aaai.org）。保留所有权利。

Consider an unknown real-valued function $f:\mathcal{H}\to \mathbf{R}$ where $\mathcal{H}\subseteq {\mathbf{R}}^N,N\ge 500$ . Let $x^{\ast }$ be the minimizer of $f\left(x\right)$ . We aim to estimate $x^{\ast }$ using a budget of $B$ queries. Thus, the optimization problem is,
考虑一个未知实值函数 $f:\mathcal{H}\to \mathbf{R}$ ，其中 $\mathcal{H}\subseteq {\mathbf{R}}^N,N\ge 500$ 。设 $x^{\ast }$ 为 $f\left(x\right)$ 的最小化解。我们的目标是在 $B$ 次查询的预算限制下估计 $x^{\ast }$ 。因此，该优化问题可表述为：

where $Q$ is the number of times the objective function is evaluated/queried,and the sample budget is $B\ll N$ . Function $f$ may be non-convex,may not have a closed-form expression, and its gradient is unavailable (hence, a black-box optimization problem). Bayesian approaches like GPR suit such problems but require choosing a kernel to model the function structure; a poor choice incurs more queries for optimization. Since queries can be expensive (e.g., when users need to answer many queries, or a NeuralNet needs re-training for each hyper-parameter configuration), lowering $Q$ is of growing interest. Kernel learning aims to address this problem.
其中 $Q$ 表示目标函数被评估/查询的次数，样本预算为 $B\ll N$ 。函数 $f$ 可能是非凸的，可能没有闭式表达式，且其梯度不可得（因此属于黑盒优化问题）。高斯过程回归（GPR）等贝叶斯方法适用于此类问题，但需要选择核函数来建模函数结构；若核函数选择不当会导致优化过程需要更多查询。由于查询可能代价高昂（例如用户需要回答大量查询，或神经网络需要对每个超参数配置重新训练），降低 $Q$ 的需求日益增长。核学习正是为了解决这一问题。

Bayesian optimization (BO) (Frazier 2018) broadly consists of two modules: (1) Gaussian Process Regression that learns a Gaussian posterior distribution of the likely values of $f\left(x\right)$ at any point of interest $x$ . (2) Acquisition function,a sampling strategy that prescribes the point at which $f$ should be evaluated (or sampled) next. We briefly discuss GPR to motivate the kernel learning problem.
贝叶斯优化（BO）（Frazier 2018）主要由两个模块组成：(1) 高斯过程回归，用于学习目标函数 $f\left(x\right)$ 在任意关注点 $x$ 处可能取值的高斯后验分布；(2) 采集函数，作为一种采样策略，指示下一步应评估（或采样） $f$ 的位置。我们将简要讨论 GPR 以引出核学习问题的动机。

Figure 2: Row 1 shows simple (or base) kernels (Duvenaud et al. 2013). Row 2 shows corresponding surrogates drawn from a GP with the above kernel.
图 2：第一行展示基础核函数(Duvenaud 等, 2013)，第二行显示从具有上述核函数的高斯过程(GP)中抽取的对应代理模型。

GPR Prior & Posterior: GPR generates a probabilistic surrogate model by defining a Gaussian distribution $\left(\mathcal{N}\left(\mu ,\mathbf{K}\right)\right)$ over infinite candidate functions. At initialization, i.e., when no function-sample are available, the prior distribution over the candidate functions is defined by $\mu =\mathbf{0}$ and a covariance matrix $\mathbf{K}$ . This matrix is computed using a kernel function $k$ as, ${\mathbf{K}}_{ij}=k\left(x_i,x_j\right)$ . The kernel essentially favors candidate functions that are similar to the kernel's own shape/structure; these candidates are assigned a higher likelihood. An expert with domain knowledge about the structure of $f\left(x\right)$ can choose the kernel judiciously, resulting in better surrogate functions $\hat{f}\left(x\right)$ . Better $\hat{f}\left(x\right)$ will ultimately reduce the number of queries needed to optimize the objective $f\left(x\right)$ .
高斯过程回归（GPR）先验与后验：GPR 通过定义一个覆盖无限候选函数的高斯分布 $\left(\mathcal{N}\left(\mu ,\mathbf{K}\right)\right)$ 来生成概率代理模型。初始化时（即尚无任何函数样本可用时），候选函数的先验分布由 $\mu =\mathbf{0}$ 和协方差矩阵 $\mathbf{K}$ 定义。该矩阵通过核函数 $k$ 计算得出，表达式为 ${\mathbf{K}}_{ij}=k\left(x_i,x_j\right)$ 。核函数本质上倾向于选择与自身形状/结构相似的候选函数，并为这些候选分配更高的似然值。若专家对 $f\left(x\right)$ 的结构具备领域知识，可审慎选择核函数，从而获得更优的代理函数 $\hat{f}\left(x\right)$ 。更好的 $\hat{f}\left(x\right)$ 最终将减少优化目标 $f\left(x\right)$ 所需的查询次数。

Once the function $f$ has been observed for a set of samples $\mathcal{X}=\left\{x_1,x_2,\dots ,x_K\right\}$ ,i.e.,we know $\mathcal{F}=$ $\left\{f\left(x_1\right),f\left(x_2\right),\dots ,f\left(x_K\right)\right\}$ ,the prior is updated to form the posterior distribution (Eqn. 2) over the candidate functions. The posterior mean $\mu$ is the most likely surrogate of the function $f$ .
当在样本集 $\mathcal{X}=\left\{x_1,x_2,\dots ,x_K\right\}$ 上观测到函数 $f$ （即已知 $\mathcal{F}=$ $\left\{f\left(x_1\right),f\left(x_2\right),\dots ,f\left(x_K\right)\right\}$ ）后，先验分布将更新形成候选函数的后验分布（公式 2）。后验均值 $\mu$ 是函数 $f$ 最可能的代理表示。

where, $\mu =\left\{\mu \left(x_1\right),\mu \left(x_2\right),\dots ,\mu \left(x_K\right)\right\},{\mathbf{K}}_{ij}=k\left(x_i,x_j\right)$ ,and $k$ represents a kernel function.
其中 $\mu =\left\{\mu \left(x_1\right),\mu \left(x_2\right),\dots ,\mu \left(x_K\right)\right\},{\mathbf{K}}_{ij}=k\left(x_i,x_j\right)$ 和 $k$ 表示核函数。

Predictions: To make predictions $\hat{\mathcal{F}}=f\left(\hat{\mathcal{X}}\right)$ at new points $\hat{\mathcal{X}}$ ,GPR uses the current posterior (Eqn. 2) to define the conditional distribution of $\hat{\mathcal{F}}$ as: $P\left(\hat{\mathcal{F}}\mid \mathcal{F},\mathcal{X},\hat{\mathcal{X}}\right)\sim$ $\mathcal{N}\left({\hat{\mathbf{K}}}^T{\mathbf{K}}^{-1}\mathcal{F},\widehat{\hat{\mathbf{K}}}-{\hat{\mathbf{K}}}^T{\mathbf{K}}^{-1}\hat{\mathbf{K}}\right)$ The details and proof of all the above are clearly explained in (Wang 2020)).
预测：要在新点 $\hat{\mathcal{X}}$ 处进行预测 $\hat{\mathcal{F}}=f\left(\hat{\mathcal{X}}\right)$ ，高斯过程回归使用当前后验分布（方程 2）来定义 $\hat{\mathcal{F}}$ 的条件分布： $P\left(\hat{\mathcal{F}}\mid \mathcal{F},\mathcal{X},\hat{\mathcal{X}}\right)\sim$ $\mathcal{N}\left({\hat{\mathbf{K}}}^T{\mathbf{K}}^{-1}\mathcal{F},\widehat{\hat{\mathbf{K}}}-{\hat{\mathbf{K}}}^T{\mathbf{K}}^{-1}\hat{\mathbf{K}}\right)$ 。上述所有内容的详细说明和证明均清晰阐述于（Wang 2020）中。

Kernels model the possible shape of the unknown function based on a set of observations(X,F)of the unknown function. Figure 2 illustrates example kernels on the top row; the bottom row shows candidate functions that GPR can derive using the corresponding kernel. In general, a class of kernels $\mathcal{K}$ produces a family of (GPR) surrogates that fit the function observations(X,F). Of course,each surrogate is associated to a likelihood which can improve with additional observations.
核函数基于对未知函数的一组观测(X,F)来建模其可能的形状。图 2 顶部展示了示例核函数；底部行显示高斯过程回归(GPR)利用相应核函数可推导出的候选函数。通常，一类核函数 $\mathcal{K}$ 会生成一组拟合函数观测(X,F)的(GPR)代理模型。当然，每个代理模型都关联一个似然值，该值可随新增观测而提升。

The goal of kernel selection is to select one kernel ${\mathbf{K}}^{\ast }\in \mathcal{K}$ that best explains the function observations(X,F). Let’s denote $\mathcal{L}:\mathcal{K}\to \mathbf{R}$ to be a model evidence that measures how well a kernel $\mathbf{K}$ fits the observations. We assume that evaluating $\mathcal{L}\left(\mathbf{K}\right)$ for all kernels in $\mathcal{K}$ is too expensive. The kernel selection problem is then,
核选择的目标是选出最能解释函数观测(X,F)的核函数 ${\mathbf{K}}^{\ast }\in \mathcal{K}$ 。设 $\mathcal{L}:\mathcal{K}\to \mathbf{R}$ 为衡量核函数 $\mathbf{K}$ 与观测数据拟合程度的模型证据。我们假定对 $\mathcal{K}$ 中所有核函数评估 $\mathcal{L}\left(\mathbf{K}\right)$ 的代价过高。因此核选择问题可表述为：

This problem is difficult to optimize with Bayesian approaches when the kernel space $\mathcal{K}$ is discrete (Parker and Rardin 2014). This is because the function $\mathcal{L}\left(\mathbf{K}\right)$ is only defined at the feasible points and cannot be queried arbitrarily. In contrast, it is possible to deduce a continuous function's behavior in a neighborhood of a point; in the discrete case, the behavior of the objective may change significantly as we move from one feasible point to another. This motivates transforming the problem in Eqn. 3 into a problem in continuous space on which optimization can be applied.
当核空间 $\mathcal{K}$ 为离散时（Parker 和 Rardin 2014），该问题难以用贝叶斯方法优化。这是因为函数 $\mathcal{L}\left(\mathbf{K}\right)$ 仅在可行点处定义，无法任意查询。相比之下，我们可以推导连续函数在某点邻域内的行为；而在离散情况下，目标函数的行为可能随着从一个可行点移动到另一个而发生显著变化。这促使我们将方程 3 中的问题转化为连续空间上的优化问题。

In this paper,the "model evidence" $\mathcal{L}$ is chosen to be GPR posterior in Eqn. 2 as it generates the surrogate that best describes the observations informed by the chosen kernel.
本文选择方程 2 中的高斯过程回归（GPR）后验作为"模型证据" $\mathcal{L}$ ，因为它生成的代理模型能最佳地反映由选定核函数所启发的观测数据。

Intuition and Overview: Our prime objective is to create a continuous space $\mathcal{Z}$ corresponding to the discrete space $\mathcal{K}$ ,thus simplifying the optimization in Eqn. 3. We propose to achieve this using a Variational Autoencoder (VAE) which can take discrete inputs $\left(\mathbf{K}\in \mathcal{K}\right)$ and learn (encoder) a continuous latent space $\mathcal{Z}$ from which the inputs can be faithfully reconstructed (decoder). If a large number of discrete kernels are created and represented sufficiently using a scheme that offers some notion of mutual similarity between kernels (i.e.,representations defining a kernel space $\mathcal{K}$ ),then we expect the VAE to give us a continuous representation of such kernels $\mathcal{Z}$ . This approach satisfies our objective since VAEs are expected to ensure continuity and completeness of their latent space, i.e., (i) two close points in the latent space cannot decode to completely different results, and (ii) a point sampled from the latent space must decode to a valid result. When the VAE is trained, we have successfully transformed the discrete optimization in $\mathcal{K}$ (Eqn. 4) to an easier continuous one in $\mathcal{Z}$ .
直觉与概述：我们的主要目标是创建一个与离散空间 $\mathcal{K}$ 对应的连续空间 $\mathcal{Z}$ ，从而简化方程 3 中的优化过程。为此，我们提出采用变分自编码器（VAE）来实现这一目标——该模型能够接收离散输入 $\left(\mathbf{K}\in \mathcal{K}\right)$ ，并通过编码器学习出一个连续的潜在空间 $\mathcal{Z}$ ，进而通过解码器忠实地重构输入数据。若我们创建大量离散核并通过某种能体现核间相似性的表示方案（即定义核空间 $\mathcal{K}$ 的表示方法）充分表征它们，则 VAE 有望为我们提供此类核的连续表示 $\mathcal{Z}$ 。该方法满足我们的目标，因为 VAE 能确保潜在空间的连续性和完备性，即：(i) 潜在空间中相邻的两个点不会解码出完全不同的结果；(ii) 从潜在空间采样的点必须能解码出有效结果。当 VAE 训练完成后，我们便成功将 $\mathcal{K}$ （方程 4）中的离散优化问题转化为 $\mathcal{Z}$ 中更易处理的连续优化问题。

Building on this intuition, KOBO's kernel learner is composed of 3 modules as shown in Figure 3:
基于这一思路，KOBO 的内核学习器由如图 3 所示的 3 个模块组成：

(1) Kernel Combiner creates composite kernels $\mathbf{K}\in \mathcal{K}$ that form the discrete kernel space $\mathcal{K}$ .
(1) 内核组合器创建复合内核 $\mathbf{K}\in \mathcal{K}$ ，形成离散内核空间 $\mathcal{K}$ 。

(2) Kernel Space Variational Autoencoder (KerVAE) trained on kernels generated by Kernel Combiner transforms discrete kernel space $\mathcal{K}$ to continuous space $\mathcal{Z}$ .
(2) 基于核组合器生成的内核训练的核空间变分自编码器（KerVAE）将离散核空间 $\mathcal{K}$ 转换为连续空间 $\mathcal{Z}$ 。

(3) Kernel Space GPR (KerGPR): Optimizes model evidence (Eqn. 4) on $\mathcal{Z}$ ; this gives $z^{\ast }$ which decodes to the optimal kernel ${\mathbf{K}}^{\ast }$ .
(3) 内核空间 GPR (KerGPR)：在 $\mathcal{Z}$ 上优化模型证据（公式 4）；由此得到 $z^{\ast }$ ，解码后获得最优内核 ${\mathbf{K}}^{\ast }$ 。

Figure 3 connects all the modules to give a complete overview of KOBO. The main objective function (Eqn. 1) is optimized with a Function GPR ( $f$ GPR). $f$ GPR uses a simple Square-Exponential (SE) kernel to obtain a batch of observations ${\mathcal{D}}_n$ . The model evidence is then passed to the kernel learning pipeline. The Kernel Combiner takes simple kernels and observations ${\mathcal{D}}_n$ as inputs,and outputs a discrete space of composite kernels ${\mathbf{K}}_{\mathcal{C}}\in \mathcal{K}$ . This is guided by a context-free-grammar described later. The KerVAE is trained on this discrete space and generates the corresponding continuous latent space $\mathcal{Z}$ . KerGPR running on $\mathcal{Z}$ optimizes the model evidence (from $f$ GPR) to find the optimal kernel ${\mathbf{K}}^{\ast }$ which is prescribed to $f$ GPR. $f$ GPR uses this ${\mathbf{K}}^{\ast }$ to obtain a new batch of observations ${\mathcal{D}}_{n+1}$ and update model evidence, which is again passed to the kernel learning pipeline. The cycle iterates until $f$ GPR has expended the sample budget $B$ . At this point, $f$ GPR outputs the minimum of its surrogate model. The following discussions expand on Kernel Combiner, KerVAE, and KerGPR.
图 3 将所有模块连接起来，完整展示了 KOBO 的架构。主目标函数（公式 1）通过函数 GPR（ $f$ GPR）进行优化。 $f$ GPR 采用简单的平方指数（SE）核来获取一批观测数据 ${\mathcal{D}}_n$ 。随后，模型证据被传递至核学习管道。核组合器以简单核和观测数据 ${\mathcal{D}}_n$ 作为输入，输出一个由复合核 ${\mathbf{K}}_{\mathcal{C}}\in \mathcal{K}$ 构成的离散空间，该过程受后文所述的无上下文语法指导。KerVAE 在此离散空间上训练，生成对应的连续潜在空间 $\mathcal{Z}$ 。运行于 $\mathcal{Z}$ 的 KerGPR 通过优化模型证据（来自 $f$ GPR）来寻找最优核 ${\mathbf{K}}^{\ast }$ ，并将其指定给 $f$ GPR 使用。 $f$ GPR 利用此 ${\mathbf{K}}^{\ast }$ 获取新一批观测数据 ${\mathcal{D}}_{n+1}$ 并更新模型证据，该证据再次传入核学习管道循环迭代，直至 $f$ GPR 耗尽样本预算 $B$ 。此时， $f$ GPR 输出其代理模型的最小值。下文将详细讨论核组合器、KerVAE 和 KerGPR。

Figure 3: System flow: $\mathrm{KOBO}$ iterates across $fGPR$ on top and KerGPR below that runs in the KerVAE latent space. The blue arrow denotes the model evidence input to KerGPR, and the red arrow denotes the optimal kernel ${\mathbf{K}}^{\ast }$ supplied by KerGPR to $f$ GPR.
图 3：系统流程： $\mathrm{KOBO}$ 在上层迭代遍历 $fGPR$ ，其下方是在 KerVAE 潜在空间中运行的 KerGPR。蓝色箭头表示输入到 KerGPR 的模型证据，红色箭头表示由 KerGPR 提供给 $f$ GPR 的最优内核 ${\mathbf{K}}^{\ast }$ 。

Complex kernels ${\mathbf{k}}_{\mathcal{C}}$ can be expressed as operations on the context-free grammar of base kernels $\mathcal{B}$ (Hopcroft,Mot-wani, and Ullman 2001; Duvenaud et al. 2013). Given $\mathcal{B}=\{A,B,C,D,E\}$ ,and a set of operators $\mathcal{O}=$ $\{$ add,multiply,end,... $\}$ ,the Kernel Combiner generates a composite kernel ${\mathbf{k}}_{\mathcal{C}}$ by drawing kernels from $\mathcal{B}$ and operators from $\mathcal{O}$ with probabilities $p_{\mathcal{B}},p_{\mathcal{O}}$ . An example ${\mathbf{k}}_{\mathcal{C}}=$ $A\ast C+B\ast D$ . In general,to form a kernel space $\mathcal{K}$ ,the Kernel Combiner develops a unique representation for each ${\mathbf{k}}_C$ .
复杂内核 ${\mathbf{k}}_{\mathcal{C}}$ 可表示为对基础内核 $\mathcal{B}$ 的上下文无关文法进行操作（Hopcroft、Motwani 和 Ullman 2001；Duvenaud 等 2013）。给定 $\mathcal{B}=\{A,B,C,D,E\}$ 及运算符集合 $\mathcal{O}=$ （ $\{$ 如加、乘、结束等 $\}$ ），内核组合器通过以概率 $p_{\mathcal{B}},p_{\mathcal{O}}$ 从 $\mathcal{B}$ 抽取内核、从 $\mathcal{O}$ 抽取运算符，生成复合内核 ${\mathbf{k}}_{\mathcal{C}}$ 。示例见 ${\mathbf{k}}_{\mathcal{C}}=$ $A\ast C+B\ast D$ 。通常，为构建内核空间 $\mathcal{K}$ ，内核组合器会为每个 ${\mathbf{k}}_C$ 开发唯一表示形式。

Grammar-based Representation: Given a composite kernel ${\mathbf{k}}_{\mathcal{C}}$ ,its grammar-based representation is a vector $r_c$ ,designed as follows. Let $\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D},\mathbf{E}$ be five base kernels in $\mathcal{B}$ . These are simple kernels like Square-exponential,Periodic,Rational Quadratic,etc. Any composite kernel ${\mathbf{k}}_{\mathcal{C}}$ created from the base kernels is expressed in the form of Eqn. 5. The code $r_c$ is then the vector of indices,i.e., $r_c=$ $\left[a_1,b_1,c_1,d_1,e_1,a_2,b_2,c_2,d_2,e_2,a_3,b_3,c_3,d_3,e_3\right].$
基于文法的表示：给定复合内核 ${\mathbf{k}}_{\mathcal{C}}$ ，其基于文法的表示是一个向量 $r_c$ ，设计如下。设 $\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D},\mathbf{E}$ 为 $\mathcal{B}$ 中的五个基础内核，例如平方指数核、周期核、有理二次核等。任何由基础内核创建的复合内核 ${\mathbf{k}}_{\mathcal{C}}$ 均以公式 5 的形式表达。代码 $r_c$ 即为索引向量，即 $r_c=$ $\left[a_1,b_1,c_1,d_1,e_1,a_2,b_2,c_2,d_2,e_2,a_3,b_3,c_3,d_3,e_3\right].$ 。

If a composite kernel is,say, ${\mathbf{k}}_{\mathcal{C}}^{\prime }={\mathbf{A}}^2\ast \mathbf{E}+\mathbf{C}\ast \mathbf{D}$ , then its Grammar-based representation would be $r_c^{\prime }=$ $\left[2,0,0,0,1,0,0,1,1,0,0,0,0,0,0\right]$ . Note: elements of the code vectors can also be fractions.
若一个复合核函数为 ${\mathbf{k}}_{\mathcal{C}}^{\prime }={\mathbf{A}}^2\ast \mathbf{E}+\mathbf{C}\ast \mathbf{D}$ ，则其基于语法的表示形式应为 $r_c^{\prime }=$ $\left[2,0,0,0,1,0,0,1,1,0,0,0,0,0,0\right]$ 。注意：代码向量的元素也可以是分数形式。

This encoding scheme has two advantages: (1) Each code $r_c$ preserves its composition,i.e.,given the code vector $r_c$ , the base kernels and the operators used to construct ${\mathbf{k}}_{\mathcal{C}}$ can be interpreted. (2) The code space is continuous, hence, a code $r_c^{\prime \prime }=\left[2,1,0,0,1,0,0,1,1,0,0,0,0,0,0\right]$ - which is only a flip of the second element in $r_c^{\prime }-$ results in ${\mathbf{k}}_{\mathcal{C}}^{\prime \prime }=$ ${\mathbf{A}}^2\ast \mathbf{B}\ast \mathbf{E}+\mathbf{C}\ast \mathbf{D}$ . In general,a small change in the code produces a small modification to the kernel composition (which makes the VAE’s task: $\mathcal{K}\to \mathcal{Z}$ easier). Past work (Garrido-Merchán and Hernández-Lobato 2020)(Lu et al. 2018) have used one-hot encoding to represent kernel matrices, however, such one-hot schemes suffer from the lack of continuity (as shown in Figure 5(a) and (b) in the Appendix).
该编码方案具有两大优势：(1) 每个代码 $r_c$ 保留其组合性，即给定代码向量 $r_c$ 时，可解析出构建 ${\mathbf{k}}_{\mathcal{C}}$ 所用的基础核函数及运算符；(2) 代码空间具有连续性，因此当代码 $r_c^{\prime \prime }=\left[2,1,0,0,1,0,0,1,1,0,0,0,0,0,0\right]$ 仅翻转 $r_c^{\prime }-$ 中的第二个元素时，会得到 ${\mathbf{k}}_{\mathcal{C}}^{\prime \prime }=$ ${\mathbf{A}}^2\ast \mathbf{B}\ast \mathbf{E}+\mathbf{C}\ast \mathbf{D}$ 。一般而言，代码的微小变化仅会引起核函数组合的微小调整（这使得变分自编码器的任务 $\mathcal{K}\to \mathcal{Z}$ 更为容易）。先前研究（Garrido-Merchán 与 Hernández-Lobato 2020）（Lu 等人 2018）曾使用独热编码表示核矩阵，但此类独热方案存在缺乏连续性的缺陷（如附录图 5(a)(b)所示）。

However,the context-free grammar $r_c$ does not encode any information from the objective function to be modeled by the complex kernels. We add this to the representation next.
然而，上下文无关文法 $r_c$ 并未编码任何来自待建模目标函数的信息（这些目标函数将由复杂核函数处理）。我们将在后续表征中加入这一信息。

Data-based Representation: Given the available function observations(X,F),for each ${\mathbf{k}}_{\mathcal{C}}$ ,we compute the "distances" between its GPR covariance matrix $M_{\mathcal{C}}$ and the covariance matrix of each base kernel, $M_{b\in \mathcal{B}}$ (the covariance matrix is computed as ${\mathbf{K}}_{ij}=k\left(x_i,x_j\right),k(\cdot )$ is the kernel function and $x_i,x_j$ are any two observations). We use the Forbenius norm to compute the matrix distances. This representation is denoted as $r_d\in {\mathcal{R}}^{\left|\mathcal{B}\right|}$ .
基于数据的表征：给定可用的函数观测数据(X,F)，对于每个 ${\mathbf{k}}_{\mathcal{C}}$ ，我们计算其高斯过程回归协方差矩阵 $M_{\mathcal{C}}$ 与每个基核协方差矩阵 $M_{b\in \mathcal{B}}$ 之间的"距离"（协方差矩阵的计算方式为 ${\mathbf{K}}_{ij}=k\left(x_i,x_j\right),k(\cdot )$ 表示核函数， $x_i,x_j$ 为任意两个观测点）。我们采用弗罗贝尼乌斯范数计算矩阵距离。该表征记为 $r_d\in {\mathcal{R}}^{\left|\mathcal{B}\right|}$ 。

The function information is now encoded in $r_d$ as the covariance matrix is computed using the kernel and the function observations/samples. Kernels that model the function's data similarly need to be in the same neighborhood so that the model evidence is sufficiently smooth. Figure 5(c) and (d) (in the Appendix) shows the advantage of encoding the objective function's data in the kernel code.
函数信息现编码于 $r_d$ 中，因协方差矩阵是通过核函数与函数观测/样本计算得出。对函数数据建模方式相似的核函数需位于同一邻域，以保证模型证据足够平滑。附录中的图 5(c)和(d)展示了在核编码中嵌入目标函数数据的优势。

Thus,the kernel space $\mathcal{K}$ consisting of complex kernels is a subset of the space of all positive semi-definite (PSD) matrices $\mathbf{S},\mathcal{K}\subseteq \mathbf{S}$ . By restricting our search to $\mathcal{K}$ - not $\mathbf{S}$ - the kernels generated through context-free grammar compositions, we can scale the GPR covariance matrix as new function observations arrive (simple kernel functions have closed-form expressions that are expanded to complex kernels for any number of observations). Therefore, our kernel learning problem in Eqn. 3 becomes a kernel selection problem. The final representation of a composite kernel ${\mathbf{k}}_{\mathcal{C}}$ is $r=\left[r_c,r_d\right]$ . This is used to train the KerVAE to generate the continuous kernel space $\mathcal{Z}$ .
因此，由复杂核函数构成的内核空间 $\mathcal{K}$ 是所有半正定（PSD）矩阵空间 $\mathbf{S},\mathcal{K}\subseteq \mathbf{S}$ 的子集。通过将搜索范围限定在 $\mathcal{K}$ （而非 $\mathbf{S}$ ）——即通过上下文无关文法组合生成的核函数，我们可以在新函数观测数据到达时扩展高斯过程回归（GPR）协方差矩阵的规模（简单核函数具有闭式表达式，可扩展为适用于任意数量观测的复杂核函数）。因此，公式 3 中的核学习问题转化为核选择问题。复合核 ${\mathbf{k}}_{\mathcal{C}}$ 的最终表达式为 $r=\left[r_c,r_d\right]$ ，该表达式用于训练核变分自编码器（KerVAE）以生成连续核空间 $\mathcal{Z}$ 。

The KerVAE learns a continuous latent space $\mathcal{Z}$ of the discrete kernel space $\mathcal{K}$ and has two main components: (1) a probabilistic encoder that models $q_{\varphi }\left(z\mid x\right)\sim p_{\theta }\left(x\mid z\right)p\left(z\right)$ parameterized by $\varphi$ where $p\left(z\right)$ is the prior over the latent space,and (2) a decoder that models the likelihood $p_{\theta }\left(x\mid z\right)$ parameterized by $\theta$ . The parameters of $q_{\varphi }\left(z\mid x\right),p_{\theta }\left(x\mid z\right)$ are optimized by joint maximization of the ELBO loss (Kingma and Welling 2013),
KerVAE 通过以下两个主要组件学习离散核空间 $\mathcal{K}$ 的连续潜在空间 $\mathcal{Z}$ ：(1) 概率编码器建模由 $\varphi$ 参数化的 $q_{\varphi }\left(z\mid x\right)\sim p_{\theta }\left(x\mid z\right)p\left(z\right)$ （其中 $p\left(z\right)$ 表示潜在空间的先验分布），(2) 解码器建模由 $\theta$ 参数化的似然函数 $p_{\theta }\left(x\mid z\right)$ 。通过联合最大化 ELBO 损失函数（Kingma 与 Welling，2013）优化 $q_{\varphi }\left(z\mid x\right),p_{\theta }\left(x\mid z\right)$ 的参数。

Table 1: KOBO learning the ground truth kernel. $\{A,B,C,D,E\}=\{\mathrm{SE},\mathrm{PER},\mathrm{RQ},\mathrm{MAT},\mathrm{LIN}\}$
表 1：KOBO 学习真实核函数的过程 $\{A,B,C,D,E\}=\{\mathrm{SE},\mathrm{PER},\mathrm{RQ},\mathrm{MAT},\mathrm{LIN}\}$

The KerVAE is re-trained after accumulating $v$ function observations as the data representation $r_d$ is re-computed for every new set of observations ${\mathcal{D}}_v=\left({\mathcal{X}}_v,{\mathcal{F}}_v\right)$ . Once Ker-VAE is trained, KerGPR is used to determine the optimal kernel $z^{\ast }\in \mathcal{Z}$ . The KerVAE decoder decodes $z^{\ast }$ to $r_c^{\ast }$ and $r_c^{\ast }$ is easily mapped to ${\mathbf{K}}^{\ast }\in \mathcal{K}$ due to the grammar’s interpretability.
KerVAE 在积累 $v$ 个函数观测值后重新训练，因为数据表示 $r_d$ 会针对每组新观测值 ${\mathcal{D}}_v=\left({\mathcal{X}}_v,{\mathcal{F}}_v\right)$ 重新计算。一旦 Ker-VAE 训练完成，便使用 KerGPR 确定最优核函数 $z^{\ast }\in \mathcal{Z}$ 。KerVAE 解码器将 $z^{\ast }$ 解码为 $r_c^{\ast }$ ，且由于语法的可解释性， $r_c^{\ast }$ 能轻松映射到 ${\mathbf{K}}^{\ast }\in \mathcal{K}$ 。

KerGPR: Optimizing on KerVAE’s latent kernel space $\mathcal{Z}$ is also a black-box problem (similar to Eqn. 1) because the objective can only be evaluated for a given kernel $k$ (i.e., by first decoding a given $z$ to $k$ ,and computing $k$ ’s model evidence $\mathcal{L}\left(\mathbf{K}\right)$ in Eqn. 4). We use GPR to find $z^{\ast }$ in the latent space and decode to the optimal kernel ${\mathbf{K}}^{\ast }$ . Thus,our optimization objective is:
KerGPR：在 KerVAE 的潜在核空间 $\mathcal{Z}$ 上进行优化同样属于黑箱问题（类似于公式 1），因为目标函数仅能针对给定核 $k$ 进行评估（即需先将给定 $z$ 解码为 $k$ ，并计算 $k$ 在公式 4 中的模型证据 $\mathcal{L}\left(\mathbf{K}\right)$ ）。我们使用 GPR 在潜在空间中寻找 $z^{\ast }$ ，并解码得到最优核 ${\mathbf{K}}^{\ast }$ 。因此，我们的优化目标为：

where, Dec(.) is the KerVAE decoder that maps a point from $\mathcal{Z}$ to the $\mathcal{K}$ space. We use the simple SE kernel in KerGPR as it does not benefit from recursive kernel learning (explained in Technical Appendix). The optimal kernel ${\mathbf{K}}^{\ast }$ is then used by Function GPR ( $f$ GPR) - the GPR posterior in Eqn. 2 - to generate surrogates that closely model the unknown function structure.
其中 Dec(.)为 KerVAE 解码器，用于将 $\mathcal{Z}$ 中的点映射到 $\mathcal{K}$ 空间。由于递归核学习并无助益（技术附录中有说明），我们在 KerGPR 中采用简单的 SE 核函数。最优核 ${\mathbf{K}}^{\ast }$ 随后被函数 GPR（ $f$ GPR）——即公式 2 中的 GPR 后验——用于生成能精准建模未知函数结构的代理模型。

Metric: We use the metric of Regret, defined as the difference between the predicted and true minimum, $(f\left({\hat{x}}^{\ast }\right)-$ $f\left(x^{\ast }\right))$ . We compare KOBO’s regret against 5 popular base kernels $\mathcal{B}=\{\mathrm{SE},\mathrm{PER},\mathrm{RQ},\mathrm{MAT},\mathrm{LIN}\}$ which respectively denote Square-Exponential (SE), Periodic (PER), Rational Quadratic (RQ), Matérn (MAT), and Linear (LIN) kernels. All KOBO experiments are initialized with the SE kernel.
评估指标：我们采用遗憾值（Regret）作为指标，其定义为预测最小值与真实最小值之间的差异 $(f\left({\hat{x}}^{\ast }\right)-$ $f\left(x^{\ast }\right))$ 。我们将 KOBO 的遗憾值与 5 种常用基础核函数 $\mathcal{B}=\{\mathrm{SE},\mathrm{PER},\mathrm{RQ},\mathrm{MAT},\mathrm{LIN}\}$ 进行对比，它们分别代表平方指数（SE）、周期（PER）、有理二次（RQ）、马特恩（MAT）和线性（LIN）核函数。所有 KOBO 实验均以 SE 核函数初始化。

Synthetic Baseline Functions: We report results from 3 types of synthetic functions $f\left(x\right)$ that are popular benchmarks (Kim 2020) for black-box optimization: Staircase functions in $N=2000$ dimensions; they exhibit non-smooth structures (Al-Roomi 2015). $◼$ Smooth benchmark functions such as BRANIN commonly used in Bayesian optimization research (Sonja Surjanovic 2013). Periodic functions such as MICHALEWICZ that exhibit repetitions in their shape (Sonja Surjanovic 2013). The top row of Figure 4 visualizes these functions (more details on evaluation parameters in the Technical Appendix). All reported results are an average of 10 runs.
合成基准函数：我们报告了 3 类合成函数 $f\left(x\right)$ 的实验结果，这些函数是黑盒优化领域的常用基准测试（Kim 2020）：《1#维度中的阶梯函数，其表现出非平滑结构（Al-Roomi 2015）》；《2#平滑基准函数（如 BRANIN），常用于贝叶斯优化研究（Sonja Surjanovic 2013）》；以及呈现周期性形态的函数（如 MICHALEWICZ）（Sonja Surjanovic 2013）。图 4 顶部展示了这些函数的可视化（更多评估参数细节见技术附录）。所有报告结果为 10 次运行的平均值。

Results: Figures 4(bottom row) plots Regret for the Staircase, Smooth (BRANIN), and the MICHALEWICZ functions, respectively. KOBO minimizes Regret at significantly fewer function evaluations (or samples), especially for Staircase and MICHALEWICZ. For a smooth function like BRANIN, KOBO's gain is understandably less since the $SE$ and $PER$ kernels naturally fit the smooth shape. When real world functions exhibit complex (non-smooth) structures and when function evaluations are expensive, KOBO's advantage is desirable.
结果：图 4（底行）分别展示了阶梯函数、平滑函数（BRANIN）和 MICHALEWICZ 函数的遗憾值（Regret）。KOBO 在显著更少的函数评估（或采样）次数下实现了遗憾值最小化，尤其对于阶梯函数和 MICHALEWICZ 函数表现突出。而对于 BRANIN 这类平滑函数，KOBO 的优势相对较小，因为 $SE$ 和 $PER$ 核函数天然契合平滑形态。当现实世界的函数呈现复杂（非平滑）结构且函数评估成本高昂时，KOBO 的优势尤为可贵。

Figure 4: Comparison of KOBO and conventional BO using SE, PER, RQ, and Matérn kernels (Bottom Row) for (a) Staircase, (b) Smooth Branin, and, (c) Periodic Michalewicz functions (Top Row).
图 4：KOBO 与传统贝叶斯优化（使用 SE、PER、RQ 及 Matérn 核函数）的对比（底行），分别针对(a)阶梯函数、(b)平滑 Branin 函数及(c)周期性 Michalewicz 函数（顶行）。

Another Metric: Since $\mathrm{KOBO}$ learns the kernel in the latent space, we will use Model Evidence in addition to Regret. Model Evidence is the normalized probability of generating the observed data $\mathcal{D}$ given a kernel model $\mathbf{K}$ ,i.e., $\log \left(P\left(\mathbf{f}\mid \mathcal{X},\mathbf{K}\right)\right)/\left|\mathcal{D}\right|$ (Malkomes,Schaff, and Garnett 2016). Computing the exact model evidence is generally intractable in GPs (Rasmussen, Williams et al. 2006)(MacKay et al. 1998). We use the Bayesian Information Criterion (BIC) to approximate the model evidence as $\log \left(P\left(\mathbf{f}\mid \mathcal{X},\mathbf{K}\right)\right)=-\frac{1}{2}{\mathbf{f}}^T{\mathbf{K}}^{-1}\mathbf{f}-\frac{1}{2}\log \left({\left(2\pi \right)}^N\left|\mathbf{K}\right|\right)$ ,where $N$ is the dimensions of the input space $\mathcal{H}\subseteq {\mathbf{R}}^N$ .
另一项指标：由于 $\mathrm{KOBO}$ 在潜在空间中学习核函数，我们将除遗憾值外还采用模型证据。模型证据是在给定核模型 $\mathbf{K}$ 的情况下生成观测数据 $\mathcal{D}$ 的归一化概率，即 $\log \left(P\left(\mathbf{f}\mid \mathcal{X},\mathbf{K}\right)\right)/\left|\mathcal{D}\right|$ （Malkomes, Schaff 和 Garnett 2016）。在高斯过程中精确计算模型证据通常不可行（Rasmussen, Williams 等 2006）（MacKay 等 1998）。我们使用贝叶斯信息准则（BIC）将模型证据近似为 $\log \left(P\left(\mathbf{f}\mid \mathcal{X},\mathbf{K}\right)\right)=-\frac{1}{2}{\mathbf{f}}^T{\mathbf{K}}^{-1}\mathbf{f}-\frac{1}{2}\log \left({\left(2\pi \right)}^N\left|\mathbf{K}\right|\right)$ ，其中 $N$ 表示输入空间 $\mathcal{H}\subseteq {\mathbf{R}}^N$ 的维度。

We will plot Regret against the number of "Function Evaluations" (on the X axis), but for Model Evidence, we will plot it against the number of "Latent Evaluations". Recall that Model Evidence is the metric used in the latent space of KerVAE to find the "best" kernel ${\mathbf{K}}^{\ast }$ . Hence "Latent Evaluations" denotes the number of latent space samples $z$ and the corresponding kernels $\mathrm{Dec}\left(z\right)=\mathbf{K}$ sampled by KerGPR to find ${\mathbf{K}}^{\ast }$ . This reflects the computation overhead of KOBO.
我们将以"函数评估次数"（X 轴）为横坐标绘制遗憾值曲线，而对于模型证据，则以"潜在评估次数"为横坐标。需注意模型证据是 KerVAE 在潜在空间中用于寻找"最佳"核函数 ${\mathbf{K}}^{\ast }$ 的指标。因此"潜在评估次数"表示 KerGPR 为寻找 ${\mathbf{K}}^{\ast }$ 所采样的潜在空间样本 $z$ 数量及对应核函数 $\mathrm{Dec}\left(z\right)=\mathbf{K}$ 数量，这反映了 KOBO 的计算开销。

(1) MCMC: The MCMC kernel search (Gardner et al. 2017; Abdessalem et al. 2017) applies the Metropolis-Hastings algorithm (Gardner et al. 2017) on the space of composite kernels ${\mathbf{k}}_{\mathcal{C}}$ ,using model evidence as the function. The proposal distribution is defined as: given a kernel $\mathbf{k}$ ,it is either added or multiplied to a kernel from $\mathcal{B}$ (chosen with $p$ ).
(1) MCMC 方法：MCMC 核搜索（Gardner 等人 2017；Abdessalem 等人 2017）在复合核空间 ${\mathbf{k}}_{\mathcal{C}}$ 上应用 Metropolis-Hastings 算法（Gardner 等人 2017），以模型证据作为目标函数。其提议分布定义为：给定一个核 $\mathbf{k}$ ，将其与从 $\mathcal{B}$ 中选取的核（通过 $p$ 选择）进行加法或乘法运算。

(2) CKS: The Automatic Statistician/Compositional Kernel Search (CKS) (Duvenaud et al. 2013) method takes advantage of the fact that complex kernels are generated as context-free grammar compositions of positive semi-definite matrices (closed under addition and multiplication); the kernel selection is then a tree search guided by model evidence. CKS searches over the discrete kernel space $\mathcal{K}$ using a greedy strategy that, at each iteration, chooses the kernel with the highest model evidence. This kernel is then expanded by composition to a set of new kernels. The search process repeats on this expanded list.
(2) CKS 方法：自动统计学家/组合核搜索（CKS）（Duvenaud 等人 2013）利用复杂核作为正定半矩阵（在加法和乘法下封闭）的上下文无关文法组合生成这一特性，将核选择转化为由模型证据引导的树搜索。CKS 在离散核空间 $\mathcal{K}$ 上采用贪婪策略进行搜索，每次迭代选择具有最高模型证据的核，然后通过组合运算将该核扩展为一组新核，并在扩展后的列表上重复搜索过程。

(3) BOMS: The Bayesian Optimization for Model Search (BOMS) (Malkomes, Schaff, and Garnett 2016), unlike CKS' greedy strategy, is a meta-learning technique, which, conditioned on observations $\mathcal{D}$ ,establishes similarities among the kernels in $\mathcal{K}$ ,i.e.,BOMS constructs a kernel between the kernels ("kernel kernel"). Like KOBO, BOMS performs BO in $\mathcal{K}$ by defining a Gaussian distribution: $P\left(g\right)=$ $\mathcal{N}\left(g;{\mu }_g,{\mathbf{K}}_g\right)$ ,where $g$ is the model evidence, ${\mu }_g$ is the mean,and ${\mathbf{K}}_q$ is the covariance (defined by "kernel kernel" function). ${\mathbf{K}}_g$ is constructed by defining a heuristic similarity measure between two kernels: Hellinger distance.
（3）BOMS：贝叶斯优化模型搜索（Bayesian Optimization for Model Search，BOMS）（Malkomes、Schaff 与 Garnett 2016）与 CKS 的贪婪策略不同，它是一种元学习技术。该方法基于观测数据 $\mathcal{D}$ 建立 $\mathcal{K}$ 中核函数间的相似性关系，即 BOMS 构建了核函数之间的核（"核的核"）。与 KOBO 类似，BOMS 通过在 $\mathcal{K}$ 中定义高斯分布进行贝叶斯优化： $P\left(g\right)=$ $\mathcal{N}\left(g;{\mu }_g,{\mathbf{K}}_g\right)$ ，其中 $g$ 为模型证据， ${\mu }_g$ 为均值， ${\mathbf{K}}_q$ 为由"核的核"函数定义的协方差矩阵。 ${\mathbf{K}}_g$ 通过定义启发式核函数相似性度量（Hellinger 距离）构建。

Results: Figure 5(Row 1) shows that KOBO lowers Regret faster than all SOTA baselines for the three benchmark functions. For Staircase, KOBO attains the global minimum in about 17 function evaluations in contrast to MCMC, which incurs 28, BOMS 32, and CKS 43. For Michalewiez, KOBO attains the minimum in about 10 fewer samples than MCMC. While BOMS and CKS do not attain the minimum but get close to it. However, KOBO's performance gain is not as pronounced for Branin due to its smooth structure as evidenced in Figure 4.
结果：图 5（第一行）显示，针对三个基准测试函数，KOBO 比所有 SOTA 基线方法更快降低遗憾值。在阶梯函数优化中，KOBO 约用 17 次函数评估即达到全局最小值，而 MCMC 需要 28 次、BOMS 需 32 次、CKS 需 43 次。对于 Michalewicz 函数，KOBO 比 MCMC 少用约 10 次采样即达到最小值，BOMS 和 CKS 虽未达到最小值但接近最优。然而由于 Branin 函数的平滑特性（如图 4 所示），KOBO 在该函数上的性能优势并不显著。

Figure 5(Row 2) compares Model Evidence for the same benchmarks. For Staircase, KOBO's KerGPR achieves significantly higher Model Evidence in 20 iterations compared to MCMC,i.e.,KOBO’s optimal kernel ${\mathbf{K}}^{\ast }$ better explains the observed data. For Branin, KOBO can match the Model Evidence of baselines, and performs modestly better for Michalewiez. The results illustrate that KOBO's performance is superior because a continuous search space learned by KerVAE simplifies the KerGPR optimization to determine ${\mathbf{K}}^{\ast }$ ,implying that KOBO presents an efficient search of the discrete kernel space $\mathcal{K}$ in contrast to sub-optimal search techniques like greedy search (CKS), or heuristic metrics for kernel optimization (BOMS).
图 5（第二行）比较了相同基准测试下的模型证据。对于 Staircase 案例，KOBO 的 KerGPR 在 20 次迭代中取得了显著高于 MCMC 的模型证据值，这表明 KOBO 的最优核 ${\mathbf{K}}^{\ast }$ 能更好地解释观测数据。在 Branin 函数上，KOBO 能与基线模型的证据值持平；而在 Michalewicz 函数上表现略优。这些结果表明 KOBO 的优越性能源于 KerVAE 学习的连续搜索空间简化了 KerGPR 优化过程以确定 ${\mathbf{K}}^{\ast }$ ，意味着 KOBO 实现了离散核空间 $\mathcal{K}$ 的高效搜索，与次优技术（如贪婪搜索 CKS）或启发式核优化指标（BOMS）形成鲜明对比。

Synthetic Functions: If we knew the objective function $f\left(x\right)$ ,we could verify if ${\mathbf{K}}^{\ast }$ has learnt its structure. To test this, we sample a function from a GP with a known kernel $K^{+}$ and pretend that to be $f\left(x\right)$ ; we check if KOBO’s ${\mathbf{K}}^{\ast }$ converges to $K^{+}$ . Table 1 reports results from $3N$ - dimensional synthetic functions,shown in the top row $(N=$ 2000). These synthetic objective functions were sampled from a GP that uses different but known kernels. The subsequent rows show KerVAE’s learnt kernel after $Q$ observations/queries. With more $Q$ ,KerGPR closely matches the ground truth kernel.
合成函数分析：若已知目标函数 $f\left(x\right)$ ，便可验证 ${\mathbf{K}}^{\ast }$ 是否习得其结构。为此，我们从具有已知核函数 $K^{+}$ 的高斯过程中采样函数并视作 $f\left(x\right)$ ，检验 KOBO 的 ${\mathbf{K}}^{\ast }$ 是否收敛于 $K^{+}$ 。表 1 展示了 $3N$ 维合成函数的实验结果（顶部行 $(N=$ 2000），这些合成目标函数采样自采用不同但已知核函数的高斯过程。后续行显示 KerVAE 在 $Q$ 次观测/查询后习得的核函数。随着 $Q$ 增加，KerGPR 与真实核函数的匹配度显著提升。

Figure 5: Comparison of KOBO, MCMC, CKS, and BOMS for Staircase (Col 1), Branin (Col 2), and Michalewiez (Col 3) functions: (Row 1) Regret (Row 2) Model Evidence.
图 5：KOBO、MCMC、CKS 与 BOMS 在阶梯函数（第 1 列）、Branin 函数（第 2 列）和 Michalewicz 函数（第 3 列）上的对比：（第 1 行）遗憾值（第 2 行）模型证据。

Learning Real-world ${\mathrm{CO}}_2$ Emission Data: Figure 6’s blue curve plots real ${\mathrm{CO}}_2$ emissions data over time (Thoning, Tans,and Komhyr 1989). We test if KOBO’s ${\mathbf{K}}^{\ast }$ can learn the structure of this blue curve from partial data. Figure 6(a,b,c) show results when KOBO has observed the first 20%, $40\mathrm{\%}$ ,and $60\mathrm{\%}$ of the data,respectively. With the first $20\mathrm{\%}$ , ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}+\mathrm{RQ}$ ,hence $\mathrm{KOBO}$ ’s red curve captures the periodic structure of the early data. When the first $40\mathrm{\%}$ of the data is observed, KOBO captures the downward linear trend of the ${\mathrm{CO}}_2$ data resulting in ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}+\mathrm{PER}+\mathrm{LIN}$ . With $60\mathrm{\%}$ of the data, ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}\ast \mathrm{RQ}+\mathrm{PER}\ast \mathrm{LIN}+$ LIN models the interplay between the function's periodic structure and linear trends. A conventional Periodic kernel (PER), shown in black in Figure 6(c), is only able to capture the periodic structure, not the upward linear trend, even with 60% of the data.
学习真实世界 ${\mathrm{CO}}_2$ 排放数据：图 6 中的蓝色曲线绘制了随时间变化的真实 ${\mathrm{CO}}_2$ 排放数据（Thoning、Tans 和 Komhyr 1989）。我们测试 KOBO 的 ${\mathbf{K}}^{\ast }$ 能否从部分数据中学习这条蓝色曲线的结构。图 6(a,b,c)分别展示了当 KOBO 观测到前 20%、 $40\mathrm{\%}$ 和@4%数据时的结果。仅用前 $20\mathrm{\%}$ 数据时， ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}+\mathrm{RQ}$ 因此 $\mathrm{KOBO}$ 的红色曲线捕捉到了早期数据的周期性结构。当观测到前 $40\mathrm{\%}$ 数据时，KOBO 捕捉到了 ${\mathrm{CO}}_2$ 数据的下行线性趋势，从而得到 ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}+\mathrm{PER}+\mathrm{LIN}$ 。在拥有 $60\mathrm{\%}$ 数据的情况下， ${\mathbf{K}}^{\ast }=\mathrm{SE}\ast \mathrm{PER}\ast \mathrm{RQ}+\mathrm{PER}\ast \mathrm{LIN}+$ 线性模型（LIN）刻画了函数周期性结构与线性趋势间的交互作用。传统的周期核（PER）如图 6(c)黑色曲线所示，即便使用 60%数据，也只能捕捉周期性结构而无法反映上升的线性趋势。

(1) Audio: We apply KOBO to audio personalization for real volunteers. We deliberately corrupt audio played to the user with the aim of helping the user pick a filter $h^{\ast }$ that cancels the effect of the corruption - equalization - and recovers the original audio; hence maximizing the user's audio satisfaction. Therefore, a GPR employed in the space of all audio filters $\mathcal{H}$ ,maximizes the user’s satisfaction $f\left(h\right)$ at $h^{\ast }$ . At each iteration,the corrupted audio is filtered with a new $h^{\prime }$ (recommended by GPR) and played to the user. The user's rating (0 to 10) of the perceived audio quality serves as the func-
（1）音频：我们将 KOBO 技术应用于真实志愿者的音频个性化处理。通过刻意对用户播放的音频施加干扰，旨在帮助用户选择能抵消干扰效果的滤波器 $h^{\ast }$ （均衡处理），从而恢复原始音频并最大化用户的听觉满意度。因此，在全体音频滤波器空间 $\mathcal{H}$ 中采用高斯过程回归（GPR），可在 $h^{\ast }$ 时刻最大化用户满意度 $f\left(h\right)$ 。每次迭代时，系统会用 GPR 推荐的新滤波器 $h^{\prime }$ 对干扰音频进行滤波后播放给用户。用户对感知音频质量给出的评分（0-10 分）将作为函...

Table 2: Audio personalization results (the $U=3$ volunteers (rest in Appendix) did not know which kernel was in use).
表 2：音频个性化实验结果（参与测试的 $U=3$ 名志愿者（其余见附录）并不知晓所采用的具体核函数）。