Taking the Human Out of the Loop: A Review of Bayesian Optimization
将人类移出循环：贝叶斯优化综述

Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams and Nando de Freitas
博巴克·沙赫里亚里、凯文·斯威斯基、王紫瑜、瑞安·P·亚当斯与南多·德弗雷塔斯

Abstract-Big data applications are typically associated with systems involving large numbers of users, massive complex software systems, and large-scale heterogeneous computing and storage architectures. The construction of such systems involves many distributed design choices. The end products (e.g., recommendation systems, medical analysis tools, real-time game engines, speech recognizers) thus involves many tunable configuration parameters. These parameters are often specified and hard-coded into the software by various developers or teams. If optimized jointly, these parameters can result in significant improvements. Bayesian optimization is a powerful tool for the joint optimization of design choices that is gaining great popularity in recent years. It promises greater automation so as to increase both product quality and human productivity. This review paper introduces Bayesian optimization, highlights some of its methodological aspects, and showcases a wide range of applications.
摘要-大数据应用通常与涉及大量用户、复杂软件系统及大规模异构计算和存储架构的系统相关联。构建此类系统需做出众多分布式设计决策。其最终产物（如推荐系统、医疗分析工具、实时游戏引擎、语音识别器）因而包含大量可调配置参数。这些参数常由不同开发者或团队指定并硬编码至软件中。若进行联合优化，这些参数可带来显著改进。贝叶斯优化作为一种强大的联合优化设计决策工具，近年来日益受到青睐。它有望实现更高程度的自动化，从而提升产品质量与人类生产效率。本综述论文介绍了贝叶斯优化，重点阐述其方法论特点，并展示广泛的应用场景。

Design problems are pervasive in scientific and industrial endeavours: scientists design experiments to gain insights into physical and social phenomena, engineers design machines to execute tasks more efficiently, pharmaceutical researchers design new drugs to fight disease, companies design websites to enhance user experience and increase advertising revenue, geologists design exploration strategies to harness natural resources, environmentalists design sensor networks to monitor ecological systems, and developers design software to drive computers and electronic devices. All these design problems are fraught with choices, choices that are often complex and high-dimensional, with interactions that make them difficult for individuals to reason about.
设计问题在科学和工业活动中无处不在：科学家设计实验以深入了解物理和社会现象，工程师设计机器以更高效地执行任务，药物研究人员设计新药以对抗疾病，公司设计网站以提升用户体验并增加广告收入，地质学家设计勘探策略以利用自然资源，环保人士设计传感器网络以监测生态系统，开发者设计软件以驱动计算机和电子设备。所有这些设计问题都充满了选择，这些选择往往复杂且高维度，其中的相互作用使得个人难以进行推理。

For example, many organizations routinely use the popular mixed integer programming solver IBM ILOG CPLEX ${}^1$ for scheduling and planning. This solver has 76 free parameters, which the designers must tune manually - an overwhelming number to deal with by hand. This search space is too vast for anyone to effectively navigate.
例如，许多组织在日常调度和规划中广泛使用流行的混合整数规划求解器 IBM ILOG CPLEX ${}^1$ 。该求解器拥有 76 个自由参数，设计者必须手动调整——这一庞大数量令人难以手工应对。其搜索空间之广阔，已超出人工有效探索的范围。

More generally, consider teams in large companies that develop software libraries for other teams to use. These libraries have hundreds or thousands of free choices and parameters that interact in complex ways. In fact, the level of complexity is often so high that it becomes impossible to find domain experts capable of tuning these libraries to generate a new product.
更广泛地说，考虑大型公司中为其他团队开发软件库的团队。这些库包含数百乃至数千个以复杂方式相互作用的自由选项和参数。实际上，其复杂程度往往高到难以找到能够调优这些库以生成新产品的领域专家。

As a second example, consider massive online games involving the following three parties: content providers, users, and the analytics company that sits between them. The analytics company must develop procedures to automatically design game variants across millions of users; the objective is to enhance user experience and maximize the content provider's revenue.
第二个例子涉及大型在线游戏中的三方：内容提供商、用户以及位于二者之间的分析公司。分析公司必须开发自动化设计程序，为上百万用户生成游戏变体；其目标是提升用户体验并最大化内容提供商的收益。

The preceding examples highlight the importance of automating design choices. For a nurse scheduling application, we would like to have a tool that automatically chooses the 76 CPLEX parameters so as to improve healthcare delivery. When launching a mobile game, we would like to use the data gathered from millions of users in real-time to automatically adjust and improve the game. When a data scientist uses a machine learning library to forecast energy demand, we would like to automate the process of choosing the best forecasting technique and its associated parameters.
上述例子凸显了自动化设计选择的重要性。对于护士排班应用，我们希望有一个工具能自动选择 76 个 CPLEX 参数，从而优化医疗服务提供。在发布手机游戏时，我们希望利用从数百万用户实时收集的数据自动调整并改进游戏体验。当数据科学家使用机器学习库预测能源需求时，我们希望能自动化选择最佳预测技术及其相关参数的过程。

Any significant advances in automated design can result in immediate product improvements and innovation in a wide area of domains, including advertising, health-care informatics, banking, information mining, life sciences, control engineering, computing systems, manufacturing, e-commerce, and entertainment.
自动化设计领域的任何重大进展都能立即带来产品改进，并在广告、医疗保健信息学、银行、信息挖掘、生命科学、控制工程、计算系统、制造业、电子商务及娱乐等多个广泛领域中推动创新。

Bayesian optimization has emerged as a powerful solution for these varied design problems. In academia, it is impacting a wide range of areas, including interactive user-interfaces [26], robotics [101], [110], environmental monitoring [106], information extraction [158], combinatorial optimisation [79], [159], automatic machine learning [16], [143], [148], [151], [72], sensor networks [55], [146], adaptive Monte Carlo [105], experimental design [11] and reinforcement learning [27].
贝叶斯优化已成为解决这些多样化设计问题的有力方案。在学术界，它正影响着广泛领域，包括交互式用户界面[26]、机器人学[101][110]、环境监测[106]、信息提取[158]、组合优化[79][159]、自动化机器学习[16][143][148][151][72]、传感器网络[55][146]、自适应蒙特卡洛[105]、实验设计[11]以及强化学习[27]。

When software engineers develop programs, they are often faced with myriad choices. By making these choices explicit, Bayesian optimization can be used to construct optimal programs [74]: that is to say, programs that run faster or compute better solutions. Furthermore, since different components of software are typically integrated to build larger systems, this framework offers the opportunity to automate integrated products consisting of many parametrized software modules.
当软件工程师开发程序时，他们常常面临无数选择。通过将这些选择明确化，贝叶斯优化可用于构建最优程序[74]：即运行更快或能计算出更优解决方案的程序。此外，由于软件的不同组件通常被集成以构建更大系统，这一框架为自动化集成由多个参数化软件模块组成的产品提供了可能。

Mathematically, we are considering the problem of finding a global maximizer (or minimizer) of an unknown objective function $f$ :
从数学角度，我们考虑的是寻找一个未知目标函数 $f$ 的全局最大化器（或最小化器）的问题：

where $\mathcal{X}$ is some design space of interest; in global optimization, $\mathcal{X}$ is often a compact subset of ${\mathbb{R}}^d$ but the Bayesian optimization framework can be applied to more unusual search spaces that involve categorical or conditional inputs, or even combinatorial search spaces with multiple categorical inputs. Furthermore, we will assume the black-box function $f$ has no simple closed form,but can be evaluated at any arbitrary query point $\mathbf{x}$ in the domain. This evaluation produces noise-corrupted (stochastic) outputs $y\in \mathbb{R}$ such that $\mathbb{E}\left[y\mid f\left(\mathbf{x}\right)\right]=f\left(\mathbf{x}\right)$ . In other words,we can only observe the function $f$ through unbiased noisy point-wise observations $y$ . Although this is the minimum requirement for Bayesian optimization, when gradients are available, they can be incorporated in the algorithm as well; see for example Sections 4.2.1 and 5.2.4 of [99]. In this setting, we consider a sequential search algorithm which,at iteration $n$ ,selects a location ${\mathbf{x}}_{n+1}$ at which to query $f$ and observe $y_{n+1}$ . After $N$ queries,the algorithm makes a final recommendation ${\bar{\mathbf{x}}}_N$ , which represents the algorithm's best estimate of the optimizer.
其中 $\mathcal{X}$ 代表某个感兴趣的设计空间；在全局优化中， $\mathcal{X}$ 通常是 ${\mathbb{R}}^d$ 的紧致子集，但贝叶斯优化框架可应用于更特殊的搜索空间，如包含分类或条件输入的空间，甚至具有多个分类输入的组合搜索空间。此外，我们假设黑盒函数 $f$ 无简单闭合形式，但可在定义域内任意查询点 $\mathbf{x}$ 处进行评估。该评估会生成带噪声（随机）的输出 $y\in \mathbb{R}$ ，满足 $\mathbb{E}\left[y\mid f\left(\mathbf{x}\right)\right]=f\left(\mathbf{x}\right)$ 。换言之，我们只能通过无偏噪声点观测 $y$ 来观察函数 $f$ 。尽管这是贝叶斯优化的最低要求，但当梯度可用时，也可将其纳入算法中，例如参见文献[99]的第 4.2.1 节和 5.2.4 节。在此设定下，我们考虑一种顺序搜索算法：在第 $n$ 次迭代时，选择查询位置 ${\mathbf{x}}_{n+1}$ 以评估 $f$ 并观测 $y_{n+1}$ 。经过 $N$ 次查询后，算法给出最终推荐值 ${\bar{\mathbf{x}}}_N$ ，代表其对优化器的最佳估计。

${}^1$ http://www.ibm.com/software/commerce/optimization/cplex-optimizer/

In the context of big data applications for instance, the function $f$ can be an object recognition system (e.g.,deep neural network) with tunable parameters $\mathbf{x}$ (e.g.,architectural choices, learning rates, etc) with a stochastic observable classification accuracy $y=f\left(\mathbf{x}\right)$ on a particular dataset such as ImageNet. Because the Bayesian optimization framework is very data efficient, it is particularly useful in situations like these where evaluations of $f$ are costly,where one does not have access to derivatives with respect to $\mathbf{x}$ ,and where $f$ is non-convex and multimodal. In these situations, Bayesian optimization is able to take advantage of the full information provided by the history of the optimization to make this search efficient.
在大数据应用的背景下，函数 $f$ 可以是一个具有可调参数 $\mathbf{x}$ （如架构选择、学习率等）的对象识别系统（例如深度神经网络），在特定数据集（如 ImageNet）上具有随机可观测的分类准确率 $y=f\left(\mathbf{x}\right)$ 。由于贝叶斯优化框架的数据效率非常高，它特别适用于评估 $f$ 成本高昂、无法获取关于 $\mathbf{x}$ 的导数以及 $f$ 非凸且多模态的情况。在这些情况下，贝叶斯优化能够充分利用优化历史提供的完整信息，使搜索过程更加高效。

Fundamentally, Bayesian optimization is a sequential model-based approach to solving problem (1). In particular, we prescribe a prior belief over the possible objective functions and then sequentially refine this model as data are observed via Bayesian posterior updating. The Bayesian posterior represents our updated beliefs - given data - on the likely objective function we are optimizing. Equipped with this probabilistic model, we can sequentially induce acquisition functions ${\alpha }_n:\mathcal{X}\mapsto \mathbb{R}$ that leverage the uncertainty in the posterior to guide exploration. Intuitively, the acquisition function evaluates the utility of candidate points for the next evaluation of $f$ ; therefore ${\mathbf{x}}_{n+1}$ is selected by maximizing ${\alpha }_n$ ,where the index $n$ indicates the implicit dependence on the currently available data. Here the "data" refers to previous locations where $f$ has been evaluated, and the corresponding noisy outputs.
本质上，贝叶斯优化是一种基于序列模型的求解方法（1）。具体而言，我们首先对可能的目标函数设定先验信念，随后通过贝叶斯后验更新随着观测数据的积累逐步修正该模型。贝叶斯后验反映了在给定数据条件下，我们对所优化目标函数可能形态的最新认知。借助这一概率模型，我们可以序列化地推导出采集函数 ${\alpha }_n:\mathcal{X}\mapsto \mathbb{R}$ ，该函数利用后验分布中的不确定性来指导探索过程。直观上，采集函数评估候选点对目标函数进行下一次评估 $f$ 的效用值，因此通过最大化 ${\alpha }_n$ 来选择 ${\mathbf{x}}_{n+1}$ ，其中下标 $n$ 表示对当前可用数据的隐式依赖关系。此处的"数据"指代先前已评估过的 $f$ 位置点及其对应的含噪声输出结果。

In summary, the Bayesian optimization framework has two key ingredients. The first ingredient is a probabilistic surrogate model, which consists of a prior distribution that captures our beliefs about the behavior of the unknown objective function and an observation model that describes the data generation mechanism. The second ingredient is a loss function that describes how optimal a sequence of queries are; in practice, these loss functions often take the form of regret, either simple or cumulative. Ideally, the expected loss is then minimized to select an optimal sequence of queries. After observing the output of each query of the objective, the prior is updated to produce a more informative posterior distribution over the space of objective functions; see Figure 1 and Algorithm 1 for an illustration and pseudo-code of this framework. See Section 4 of [64] for another introduction.
总之，贝叶斯优化框架有两个关键组成部分。第一个组成部分是概率代理模型，它包括一个先验分布（用于捕捉我们对未知目标函数行为的信念）和一个描述数据生成机制的观测模型。第二个组成部分是损失函数，用于描述一系列查询的最优程度；在实践中，这些损失函数通常采用简单或累积遗憾的形式。理想情况下，通过最小化期望损失来选择最优的查询序列。在观察到每个目标查询的输出后，先验分布会被更新，从而在目标函数空间上生成信息量更大的后验分布；关于该框架的图示和伪代码，请参见图 1 和算法 1。另见文献[64]的第 4 节以获取另一种介绍。

One problem with this minimum expected risk framework is that the true sequential risk, up to the full evaluation budget, is typically computationally intractable. This has led to the introduction of many myopic heuristics known as acquisition functions, e.g., Thompson sampling, probability of improvement, expected improvement, upper-confidence-bounds, and entropy search. These acquisition functions trade off exploration and exploitation; their optima are located where the uncertainty in the surrogate model is large (exploration) and/or where the model prediction is high (exploitation). Bayesian optimization algorithms then select the next query point by maximizing such acquisition functions. Naturally, these acquisition functions are often even more multimodal and difficult to optimize, in terms of querying efficiency, than the original black-box function $f$ . Therefore it is critical that the acquisition functions be cheap to evaluate or approximate: cheap in relation to the expense of evaluating the black-box $f$ . Since acquisition functions have analytical forms that are easy to evaluate or at least approximate, it is usually much easier to optimize them than the original objective function.
这种最小期望风险框架的一个问题是，真实的序列风险（直到用尽全部评估预算）通常在计算上是难以处理的。这导致了许多近视启发式方法（称为采集函数）的引入，例如 Thompson 采样、改进概率、期望改进、上置信界和熵搜索。这些采集函数在探索和利用之间进行权衡；其最优解位于代理模型不确定性较大（探索）和/或模型预测值较高（利用）的区域。贝叶斯优化算法随后通过最大化这些采集函数来选择下一个查询点。自然，就查询效率而言，这些采集函数通常比原始黑盒函数 $f$ 更加多峰且难以优化。因此，关键的是采集函数的评估或近似成本要低廉：相对于评估黑盒 $f$ 的费用而言足够廉价。 由于采集函数具有易于评估或至少可近似计算的解析形式，通常优化它们比优化原始目标函数要容易得多。

Algorithm 1 Bayesian optimization
算法 1 贝叶斯优化

for $n=1,2,\dots$ do  对于 $n=1,2,\dots$ 执行

select new ${\mathbf{x}}_{n+1}$ by optimizing acquisition function $\alpha$
通过优化采集函数 $\alpha$ 来选择新的 ${\mathbf{x}}_{n+1}$

${\mathbf{x}}_{n+1}=\underset{\mathbf{x}}{\arg max}\alpha \left(\mathbf{x};{\mathcal{D}}_n\right)$

query objective function to obtain $y_{n+1}$
查询目标函数以获取 $y_{n+1}$

augment data ${\mathcal{D}}_{n+1}=\left\{{\mathcal{D}}_n,\left({\mathbf{x}}_{n+1},y_{n+1}\right)\right\}$  增强数据 ${\mathcal{D}}_{n+1}=\left\{{\mathcal{D}}_n,\left({\mathbf{x}}_{n+1},y_{n+1}\right)\right\}$

update statistical model  更新统计模型

end for  结束循环

In this paper, we introduce the ingredients of Bayesian optimization in depth. Our presentation is unique in that we aim to disentangle the multiple components that determine the success of Bayesian optimization implementations. In particular, we focus on statistical modelling as this leads to general algorithms to solve a broad range tasks. We also provide an extensive comparison among popular acquisition functions. We will see that the careful choice of statistical model is often far more important than the choice of acquisition function heuristic.
本文深入介绍了贝叶斯优化的核心要素。我们的阐述独树一帜，旨在剖析决定贝叶斯优化实现成功与否的多重组件。特别地，我们聚焦于统计建模，因其能衍生出解决广泛任务的通用算法。我们还对主流采集函数进行了全面比较。我们将看到，统计模型的精心选择往往比采集函数启发式策略的选择更为关键。

We begin in Sections II and III, with an introduction to parametric and non-parametric models, respectively, for binary- and real-valued objective functions. In Section IV, we will introduce many acquisition functions, compare them, and even combine them into portfolios. Several practical and implementation details, including available software packages, are discussed in Section V. A survey of theoretical results and a brief history of model-based optimization are provided in Sections VI and VII, respectively. Finally, we introduce more recent developments in Section VIII.
我们首先在第二、三节分别介绍针对二元和实值目标函数的参数化与非参数化模型。第四节将引入多种采集函数进行对比，甚至将其组合成投资组合。第五节讨论包括可用软件包在内的多项实践与实现细节。第六、七节分别综述理论成果和基于模型的优化简史。最后在第八节介绍最新研究进展。

Before embarking on a detailed introduction to Bayesian optimization, the following sections provide an overview of the many and varied successful applications of Bayesian optimization that should be of interest to data scientists.
在深入介绍贝叶斯优化之前，以下部分概述了众多且多样化的贝叶斯优化成功应用案例，这些内容对数据科学家颇具参考价值。

Fig. 1. Illustration of the Bayesian optimization procedure over three iterations. The plots show the mean and confidence intervals estimated with a probabilistic model of the objective function. Although the objective function is shown, in practice it is unknown. The plots also show the acquisition functions in the lower shaded plots. The acquisition is high where the model predicts a high objective (exploitation) and where the prediction uncertainty is high (exploration). Note that the area on the far left remains unsampled, as while it has high uncertainty, it is correctly predicted to offer little improvement over the highest observation [27].
图 1. 贝叶斯优化过程经过三次迭代的示意图。图中展示了基于目标函数概率模型估计的均值与置信区间。虽然实际目标函数未知，但图示中仍予以呈现。下方阴影区域绘制了采集函数，其峰值出现在模型预测目标值较高处（利用）及预测不确定性较大处（探索）。值得注意的是，最左侧区域虽存在高不确定性，但由于模型正确预测其改进空间低于当前最高观测值[27]，该区域始终未被采样。

1) $A/B$ testing: Though the idea of $\mathrm{A}/\mathrm{B}$ testing dates back to the early days of advertising in the form of so-called focus groups, the advent of the internet and smartphones has given web and app developers a new forum for implementing these tests at unprecedented scales. By redirecting small fractions of user traffic to experimental designs of an ad, app, game, or website, the developers can utilize noisy feedback to optimize any observable metric with respect to the product's configuration. In fact, depending on the particular phase of a product's life, new subscriptions may be more valuable than revenue or user retention, or vice versa; the click-through rate might be the relevant objective to optimize for an ad, whereas for a game it may be some measure of user engagement.
1) $A/B$ 测试：虽然 $\mathrm{A}/\mathrm{B}$ 测试的概念可以追溯到广告业早期的焦点小组形式，但互联网和智能手机的出现为网页和应用开发者提供了一个新平台，使其能够以前所未有的规模实施这些测试。通过将少量用户流量重定向至广告、应用、游戏或网站的试验性设计，开发者可以利用嘈杂的反馈来优化产品配置相关的任何可观测指标。实际上，根据产品生命周期的特定阶段，新订阅可能比收入或用户留存更有价值，反之亦然；点击率可能是广告需要优化的相关目标，而对游戏而言，则可能是用户参与度的某种衡量标准。

The crucial problem is how to optimally query these subsets of users in order to find the best product with high probability within a predetermined query budget, or how to redirect traffic sequentially in order to optimize a cumulative metric while incurring the least opportunity cost [88], [135], [38].
关键问题在于如何最优地查询这些用户子集，以便在预定的查询预算内以高概率找到最佳产品，或者如何顺序重定向流量以优化累积指标，同时将机会成本降至最低[88], [135], [38]。

2) Recommender systems: In a similar setting, online content providers make product recommendations to their subscribers in order to optimize either revenue in the case of e-commerce sites, readership for news sites, or consumption for video and music streaming websites. In contrast to $\mathrm{A}/\mathrm{B}$ testing, the content provider can make multiple suggestions to any given subscriber. The techniques reviewed in this work have been successfully used for the recommendation of news articles [97], [38], [153].
2) 推荐系统：在类似场景中，在线内容提供商向订阅用户推荐产品，以优化电子商务网站的收入、新闻网站的阅读量或视频音乐流媒体网站的消费量。与 $\mathrm{A}/\mathrm{B}$ 测试不同，内容提供商可以向任何特定订阅用户提出多项建议。本研究中回顾的技术已成功应用于新闻文章推荐[97]、[38]、[153]。

3) Robotics and Reinforcement learning: Bayesian optimization has also been successfully applied to policy search. For example, by parameterizing a robot's gait it is possible to optimize it for velocity or smoothness as was done on the Sony AIBO ERS-7 in [101]. Similar policy parameterization and search techniques have been used to navigate a robot through landmarks, minimizing uncertainty about its own location and map estimate [110], [108]. See [27] for an example of applying Bayesian optimization to hierarchical reinforcement learning, where the technique is used to automatically tune the parameters of a neural network policy and to learn value functions at higher levels of the hierarchy. Bayesian optimization has also been applied to learn attention policies in image tracking with deep networks [44]
3) 机器人学与强化学习：贝叶斯优化同样成功应用于策略搜索领域。例如，通过参数化机器人的步态，可针对速度或流畅性进行优化，如索尼 AIBO ERS-7 机器人上的实践[101]。类似策略参数化与搜索技术还被用于引导机器人穿越地标，同时最小化其自身位置及地图估计的不确定性[110][108]。文献[27]展示了贝叶斯优化在分层强化学习中的应用案例，该技术用于自动调整神经网络策略参数，并学习层次结构中更高层的价值函数。此外，贝叶斯优化亦应用于深度学习图像跟踪中的注意力策略学习[44]。

4) Environmental monitoring and sensor networks: Sensor networks are used to monitor environmentally relevant quantities: temperature, concentration of pollutants in the atmosphere, soil, oceans, etc. Whether inside a building or at a planetary scale, these networks make noisy local measurements that are interpolated to produce a global model of the quantity of interest. In some cases, these sensors are expensive to activate but one can answer important questions like what is the hottest or coldest spot in a building by activating a relatively small number of sensors. Bayesian optimization was used for this task and the similar one of finding the location of greatest highway traffic congestion [146]. Also, see [55] for a meteorological application.
4) 环境监测与传感器网络：传感器网络用于监测与环境相关的各类参数，如温度、大气、土壤及海洋中的污染物浓度等。无论是在建筑物内部还是全球范围内，这些网络通过带有噪声的局部测量数据进行插值，构建出目标量的全局模型。某些情况下，激活这些传感器成本高昂，但通过激活相对少量的传感器，即可解答诸如建筑物内最热或最冷区域位置等重要问题。贝叶斯优化技术已应用于此类任务，以及类似的高速公路最拥堵路段定位问题[146]。另见气象学应用案例[55]。

When the sensor is mobile, there is a cost associated with making a measurement which relates to the distance travelled by a vehicle on which the sensor is mounted (e.g., a drone). This cost can be incorporated in the decision making process as in [106].
当传感器为移动式时，测量成本与搭载传感器的载具（如无人机）移动距离相关。如文献[106]所示，此类成本可纳入决策流程予以考量。

5) Preference learning and interactive interfaces: The computer graphics and animation fields are filled with applications that require the setting of tricky parameters. In many cases, the models are complex and the parameters unintuitive for non-experts. In [28], [26], the authors use Bayesian optimization to set the parameters of several animation systems by showing the user examples of different parametrized animations and asking for feedback. This interactive Bayesian optimization strategy is particulary effective as humans can be very good at comparing examples, but unable to produce an objective function whose optimum is the example of interest.
5) 偏好学习与交互界面：计算机图形学和动画领域充斥着需要设置复杂参数的应用。在许多情况下，模型本身很复杂，参数对非专业人士而言难以直观理解。在文献[28]和[26]中，作者通过向用户展示不同参数化动画示例并收集反馈，利用贝叶斯优化为多个动画系统设定参数。这种交互式贝叶斯优化策略特别有效，因为人类擅长比较示例，却难以构建一个以目标示例为最优解的客观函数。

6) Automatic machine learning and hyperparameter tuning: In this application, the goal is to automatically select the best model (e.g., random forests, support vector machines, neural networks, etc.) and its associated hyperparameters for solving a task on a given dataset. For big datasets or when considering many alternatives, cross-validation is very expensive and hence it is important to find the best technique within a fixed budget of cross-validation tests. The objective function here is the generalization performance of the models and hyperparameter settings; a noisy evaluation of the objective corresponds to training a single model on all but one cross-validation folds and returning, e.g., the empirical error on the held out fold.
6) 自动机器学习和超参数调优：在此应用中，目标是自动选择最佳模型（如随机森林、支持向量机、神经网络等）及其相关超参数，以解决给定数据集上的任务。对于大型数据集或考虑多种替代方案时，交叉验证成本极高，因此在固定次数的交叉验证测试预算内找到最佳技术至关重要。此处的目标函数是模型和超参数设置的泛化性能；对目标的噪声评估对应于在除一个交叉验证折之外的所有数据上训练单个模型，并返回例如在保留折上的经验误差。

The traditional alternatives to cross-validation include racing algorithms that use conservative concentration bounds to rule out underperforming models [107], [113]. Recently, the Bayesian optimization approach for the model selection and tuning task has received much attention in tuning deep belief networks [16], Markov chain Monte Carlo methods [105], [65], convolutional neural networks [143], [148], and automatically selecting among WEKA and scikit-learn offerings [151], [72].
传统交叉验证的替代方法包括使用保守集中界限来排除表现不佳模型的竞赛算法[107]、[113]。近年来，贝叶斯优化方法在模型选择与参数调优任务中受到广泛关注，已应用于深度信念网络[16]、马尔可夫链蒙特卡洛方法[105]、[65]、卷积神经网络[143]、[148]的调参，以及自动选择 WEKA 和 scikit-learn 工具包中的算法[151]、[72]。

7) Combinatorial optimization: Bayesian optimization has been used to solve difficult combinatorial optimization problems in several applications. One notable approach is called empirical hardness models (EHMs) that use a set of problem features to predict the performance of an algorithm on a specific problem instance [96]. Bayesian optimization with an EHM amounts to finding the best algorithm and configuration for a given problem. This concept has been applied to e.g., tuning mixed integer solvers [78], [159], and tuning approximate nearest neighbour algorithms [109]. Bayesian optimization has also been applied to fast object localization in images [163].
7) 组合优化：贝叶斯优化已被用于解决多个应用中的复杂组合优化问题。一种显著方法称为经验硬度模型（EHMs），其利用一组问题特征预测算法在特定问题实例上的性能[96]。基于 EHM 的贝叶斯优化相当于为给定问题寻找最佳算法及配置。该技术已应用于例如混合整数求解器调参[78][159]、近似最近邻算法调优[109]等场景。贝叶斯优化还被用于图像中的快速目标定位[163]。

8) Natural language processing and text: Bayesian optimization has been applied to improve text extraction in [158] and to tune text representations for more general text and language tasks in [162].
8) 自然语言处理与文本：贝叶斯优化已被应用于改进文本提取（见文献[158]），并调整文本表示以适用于更广泛的文本及语言任务（见文献[162]）。

The central idea of Bayesian optimization is to build a model that can be updated and queried to drive optimization decisions. In this section, we cover several such models, but for the sake of clarity, we first consider a generic family of models parameterized by $\mathbf{w}$ . Let $\mathcal{D}$ denote the available data. We will generalize to the non-parametric situation in the proceeding section.
贝叶斯优化的核心思想是构建一个可更新和查询以驱动优化决策的模型。本节将介绍几种此类模型，但为了清晰起见，我们首先考虑由参数 $\mathbf{w}$ 定义的通用模型族。设 $\mathcal{D}$ 表示现有数据。我们将在后续章节中推广到非参数化场景。

Since $\mathrm{w}$ is an unobserved quantity,we treat it as a latent random variable with a prior distribution $p\left(\mathbf{w}\right)$ ,which captures our a priori beliefs about probable values for $\mathrm{w}$ before any data is observed. Given data $\mathcal{D}$ and a likelihood model $p\left(\mathcal{D}\mid \mathbf{w}\right)$ ,we can then infer a posterior distribution $p\left(\mathbf{w}\mid \mathcal{D}\right)$ using Bayes’ rule:
由于 $\mathrm{w}$ 是一个未观测到的量，我们将其视为具有先验分布 $p\left(\mathbf{w}\right)$ 的潜在随机变量，该分布捕获了在观测任何数据前我们对 $\mathrm{w}$ 可能值的先验信念。给定数据 $\mathcal{D}$ 和似然模型 $p\left(\mathcal{D}\mid \mathbf{w}\right)$ 后，可利用贝叶斯规则推断后验分布 $p\left(\mathbf{w}\mid \mathcal{D}\right)$ ：

This posterior represents our updated beliefs about $\mathrm{w}$ after observing data $\mathcal{D}$ . The denominator $p\left(\mathcal{D}\right)$ is the marginal likelihood, or evidence, and is usually computationally intractable. Fortunately,it does not depend on $\mathbf{w}$ and is therefore simply a normalizing constant. A typical modelling choice is to use conjugacy to match the prior and likelihood so that the posterior (and often the normalizing constant) can be computed analytically.
该后验分布代表了我们在观测到数据 $\mathcal{D}$ 后对 $\mathrm{w}$ 的更新信念。分母 $p\left(\mathcal{D}\right)$ 是边际似然或证据，通常在计算上难以处理。幸运的是，它不依赖于 $\mathbf{w}$ ，因此仅是一个归一化常数。典型的建模选择是利用共轭性匹配先验与似然，从而能解析计算后验（通常包括归一化常数）。

We begin our discussion with a treatment of perhaps the simplest statistical model, the Beta-Bernoulli. Imagine that there are $K$ drugs that have unknown effectiveness,where we define "effectiveness" as the probability of a successful cure. We wish to cure patients, but we must also identify which drugs are effective. Such a problem is often called a Bernoulli (or binomial) bandit problem by analogy to a group of slot machines, which each yield a prize with some unknown probability. In addition to clinical drug settings, this formalism is useful for $\mathrm{A}/\mathrm{B}$ testing [135],advertising,and recommender systems [97], [38], among a wide variety of applications. The objective is to identify which arm of the bandit to pull, e.g., which drug to administer, which movie to recommend, or which advertisement to display. Initially, we consider the simple case where the arms are independent insofar as observing the success or failure of one provides no information about another.
我们首先讨论可能是最简单的统计模型——Beta-Bernoulli 模型。想象有 $K$ 种药物，其疗效未知，这里我们将“疗效”定义为成功治愈的概率。我们希望治愈患者，但同时也要识别哪些药物是有效的。这类问题常被称为 Bernoulli（或二项）老虎机问题，类比于一组每次以某种未知概率产生奖励的老虎机。除了临床药物场景，这种形式主义还适用于 $\mathrm{A}/\mathrm{B}$ 测试[135]、广告和推荐系统[97]、[38]等多种应用。目标在于确定拉动老虎机的哪个臂，例如，施用哪种药物、推荐哪部电影或展示哪条广告。最初，我们考虑简单情况，其中各臂相互独立，即观察一个臂的成功或失败不会提供关于另一个臂的任何信息。

Returning to the drug application, we can imagine the effectiveness of different drugs (arms on the bandit) as being determined by a function $f$ that takes an index $a\in 1,\dots ,K$ and returns a Bernoulli parameter in the interval(0,1). With $y_i\in \{0,1\}$ ,we denote the Bernoulli outcome of the treatment of patient $i$ ,and this has mean parameter $f\left(a_i\right)$ if the drug administered was $a_i$ . Note that we are assuming stochastic feedback, in contrast to deterministic or adversarial feedback [9],[10]. With only $K$ arms,we can fully describe the function $f$ with a parameter $\mathbf{w}\in {(0,1)}^K$ so that $f_{\mathbf{w}}\left(a\right)\text{:=}{w}_a$ .
回到药物应用的例子，我们可以将不同药物（赌博机上的臂）的疗效想象为由一个函数 $f$ 决定，该函数接收索引 $a\in 1,\dots ,K$ 并返回区间(0,1)内的伯努利参数。用 $y_i\in \{0,1\}$ 表示第 $i$ 位患者治疗结果的伯努利输出，若所施用药物为 $a_i$ ，则其均值参数为 $f\left(a_i\right)$ 。注意我们假设的是随机反馈，这与确定性或对抗性反馈[9][10]形成对比。当仅有 $K$ 个臂时，我们可以用参数 $\mathbf{w}\in {(0,1)}^K$ 完整描述函数 $f$ ，使得 $f_{\mathbf{w}}\left(a\right)\text{:=}{w}_a$ 成立。

Over time, we will see outcomes from different patients and different drugs. We can denote these data as a set of tuples ${\mathcal{D}}_n={\left\{(a_i,y_i)\right\}}_{i=1}^n$ ,where $a_i$ indicates which of the $K$ drugs was administered and $y_i$ is 1 if the patient was cured and 0 otherwise. In a Bayesian setting, we will use these data to compute a posterior distribution over $\mathbf{w}$ . A natural choice for the prior distribution is a product of $K$ beta distributions:
随着时间的推移，我们将观察到来自不同患者和不同药物的治疗结果。这些数据可以表示为一组元组 ${\mathcal{D}}_n={\left\{(a_i,y_i)\right\}}_{i=1}^n$ ，其中 $a_i$ 标识使用了 $K$ 种药物中的哪一种，而 $y_i$ 若患者痊愈则为 1，否则为 0。在贝叶斯框架下，我们将利用这些数据计算关于 $\mathbf{w}$ 的后验分布。先验分布的自然选择是 $K$ 个贝塔分布的乘积：

as this is the conjugate prior to the Bernoulli likelihood, and it leads to efficient posterior updating. We denote by $n_{a,1}$ the number of patients cured by drug $a$ and by $n_{a,0}$ the number of patients who received $a$ but were unfortunately not cured; that is
因为这是伯努利似然的共轭先验，且能实现高效的后验更新。我们用 $n_{a,1}$ 表示药物 $a$ 治愈的患者数量， $n_{a,0}$ 表示接受了 $a$ 治疗但遗憾未愈的患者数量；即

The convenient conjugate prior then leads to a posterior distribution which is also a product of betas:
这种便利的共轭先验随后导出的后验分布同样是一系列 Beta 分布的乘积：

Note that this makes it clear how the hyperparameters $\alpha ,\beta >0$ in the prior can be interpreted as pseudo-counts. Figure 2 provides a visualization of the posterior of a three-armed Beta-Bernoulli bandit model with a Beta(2,2)prior.
注意，这清晰地展示了先验中的超参数 $\alpha ,\beta >0$ 如何被解释为伪计数。图 2 展示了采用 Beta(2,2)先验的三臂 Beta-Bernoulli 老虎机模型后验分布的可视化结果。

In Section IV, we will introduce various strategies for selecting the next arm to pull within models like the Beta-Bernoulli, but for the sake of illustration, we introduce Thompson sampling [150], the earliest and perhaps the simplest nontrivial bandit strategy. This strategy is also commonly known as randomized probability matching [135] because it selects the arm based on the posterior probability of optimality, here given by a beta distribution. In simple models like the Beta-Bernoulli, it is possible to compute this distribution in closed form, but more often it must be estimated via, e.g., Monte Carlo.
在第四节中，我们将介绍在诸如 Beta-Bernoulli 等模型中选择下一次拉取臂的各种策略，但为了便于说明，我们引入汤普森采样[150]——这是最早且可能最简单的非平凡赌博机策略。该策略也常被称为随机概率匹配[135]，因为它基于最优性的后验概率（此处由 Beta 分布给出）来选择臂。在 Beta-Bernoulli 这类简单模型中，可以闭式计算出该分布，但更多情况下需通过蒙特卡洛等方法进行估计。

Fig. 2. Example of the Beta-Bernoulli model for A/B testing. Three different buttons are being tested with various colours and text. Each option is given 2 successes (click-throughs) and 2 failures as a prior (top). As data are observed, each option updates its posterior over $w$ . Option A is the current best with 5 successes and only 1 observed failure.
图 2. Beta-Bernoulli 模型在 A/B 测试中的应用示例。测试了三种不同颜色和文字的按钮选项。每个选项初始设定为 2 次成功（点击通过）和 2 次失败作为先验（顶部）。随着数据被观测，每个选项会更新其后验分布 $w$ 。选项 A 当前表现最佳，有 5 次成功且仅观察到 1 次失败。

After observing $n$ patients in our drug example,we can think of a bandit strategy as being a rule for choosing which drug to administer to patient $n+1$ ,i.e.,choosing $a_{n+1}$ among the $K$ options. In the case of Thompson sampling,this can be done by drawing a single sample $\tilde{\mathbf{w}}$ from the posterior and then maximizing the resulting surrogate $f_{\tilde{\mathbf{w}}}$ ,i.e.,
在我们的药物示例中观察了 $n$ 名患者后，可以将赌博策略视为一种规则，用于决定对第 $n+1$ 名患者施用哪种药物，即在 $K$ 个选项中选择 $a_{n+1}$ 。在汤普森采样的情况下，这可以通过从后验分布中抽取单个样本 $\tilde{\mathbf{w}}$ ，然后最大化所得的替代 $f_{\tilde{\mathbf{w}}}$ 来实现，即

For the Beta-Bernoulli,this corresponds to simply drawing $\tilde{\mathbf{w}}$ from (6) and then choosing the action with the largest ${\tilde{w}}_a$ . This procedure, shown in pseudo-code in Algorithm 2, is also commonly called posterior sampling [127]. It is popular for several reasons: 1) there are no free parameters other than the prior hyperparameters of the Bayesian model, 2) the strategy naturally trades off between exploration and exploitation based on its posterior beliefs on $\mathbf{w}$ ; arms are explored only if they are likely (under the posterior) to be optimal, 3) the strategy is relatively easy to implement as long as Monte Carlo sampling mechanisms are available for the posterior model, and 4) the randomization in Thompson sampling makes it particularly appropriate for batch or delayed feedback settings where many selections $a_{n+1}$ are based on the identical posterior [135],[38].
对于 Beta-Bernoulli 模型，这相当于直接从(6)式中抽取 $\tilde{\mathbf{w}}$ ，然后选择具有最大 ${\tilde{w}}_a$ 的动作。这一过程在算法 2 中以伪代码形式展示，通常也被称为后验采样[127]。它受欢迎的原因有几个：1)除了贝叶斯模型的先验超参数外没有其他自由参数，2)该策略基于其后验信念自然地平衡了探索与利用；只有当某臂在后验概率下可能最优时才会被探索，3)只要后验模型支持蒙特卡洛采样机制，该策略相对容易实现，4)汤普森采样中的随机化使其特别适合批量或延迟反馈场景，其中许多选择 $a_{n+1}$ 基于相同的后验分布[135],[38]。

In many applications, the designs available to the experimenter have components that can be varied independently. For example, in designing an advertisement, one has choices such as artwork, font style, and size; if there are five choices for each, the total number of possible configurations is 125 . In general, this number grows combinatorially in the number of components. This presents challenges for approaches such as the independent Beta-Bernoulli model discussed in the previous section: modelling the arms as independent will lead to strategies that must try every option at least once. This rapidly becomes infeasible in the large spaces of real-world problems. In this section, we discuss a parametric approach that captures dependence between the arms via a linear model. For simplicity, we first consider the case of real-valued outputs $y$ and generalize this model to binary outputs in the succeeding section.
在许多应用中，实验者可用的设计方案包含可独立变化的组件。例如，在设计广告时，可以选择如艺术品、字体样式和大小等元素；若每项有五种选择，则可能的配置总数达 125 种。一般而言，这一数量会随组件数量呈组合式增长。这对诸如前一节讨论的独立 Beta-Bernoulli 模型等方法提出了挑战：将各选项视为独立处理将导致策略必须至少尝试每个选项一次。这在现实问题的大规模空间中很快变得不可行。本节中，我们讨论一种通过线性模型捕捉选项间依赖关系的参数化方法。为简化起见，我们首先考虑实值输出的情况 $y$ ，并在后续章节中将此模型推广至二元输出。

Algorithm 2 Thompson sampling for Beta-Bernoulli bandit
算法 2：Beta-Bernoulli 老虎机的汤普森采样

Require: $\alpha ,\beta$ : hyperparameters of the beta prior
需确保： $\alpha ,\beta$ ：beta 先验的超参数

Initialize $n_{a,0}=n_{a,1}=i=0$ for all $a$
初始化 $n_{a,0}=n_{a,1}=i=0$ ，对所有 $a$

repeat  重复

for $a=1,\dots ,K$ do  对于 $a=1,\dots ,K$ 执行

${\tilde{w}}_a\sim \mathrm{Beta}\left(\alpha +n_{a,1},\beta +n_{a,0}\right)$

end for  结束循环

$a_i=\arg \underset{a}{max}{\tilde{w}}_a$

Observe $y_i$ by pulling arm $a_i$
通过拉动臂 $a_i$ 观察 $y_i$

if $y_i=0$ then  如果 $y_i=0$ 则

$n_{a_i,0}=n_{a_i,0}+1$

else  否则

$n_{a_i,1}=n_{a_i,1}+1$

end if  结束条件

$i=i+1$

until stopping criterion reached
直至达到停止标准

As before, we begin by specifying a likelihood and a prior. In the linear model, it is natural to assume that each possible arm $a$ has an associated feature vector ${\mathbf{x}}_a\in {\mathbb{R}}^d$ . We can then express the expected payout (reward) of each arm as a function of this vector,i.e., $f\left(a\right)=f\left({\mathbf{x}}_a\right)$ . Our objective is to learn this function $f:{\mathbb{R}}^d\mapsto \mathbb{R}$ for the purpose of choosing the best arm,and in the linear model we require $f$ to be of the form $f_{\mathbf{w}}\left(a\right)={\mathbf{x}}_a^T\mathbf{w}$ ,where the parameters $\mathbf{w}$ are now feature weights. This forms the basis of our likelihood model, in which the observations for arm $a$ are drawn from a Gaussian distribution with mean ${\mathbf{x}}_a^T\mathbf{w}$ and variance ${\sigma }^2$ .
如前所述，我们首先指定似然函数和先验分布。在线性模型中，自然假设每个可能的手臂 $a$ 都有一个对应的特征向量 ${\mathbf{x}}_a\in {\mathbb{R}}^d$ 。然后，我们可以将每个手臂的预期收益（奖励）表达为该向量的函数，即 $f\left(a\right)=f\left({\mathbf{x}}_a\right)$ 。我们的目标是学习这个函数 $f:{\mathbb{R}}^d\mapsto \mathbb{R}$ 以选择最佳手臂，而在线性模型中，我们要求 $f$ 的形式为 $f_{\mathbf{w}}\left(a\right)={\mathbf{x}}_a^T\mathbf{w}$ ，其中参数 $\mathbf{w}$ 现在是特征权重。这构成了我们似然模型的基础，在该模型中，手臂 $a$ 的观测值是从均值为 ${\mathbf{x}}_a^T\mathbf{w}$ 、方差为 ${\sigma }^2$ 的高斯分布中抽取的。

We use $\mathbf{X}$ to denote the $n\times d$ design matrix in which row $i$ is the feature vector associated with the arm pulled in the $i$ th iteration, ${\mathbf{x}}_{a_i}$ . We denote by $\mathbf{y}$ the $n$ -vector of observations. In this case,there is also a natural conjugate prior for $\mathbf{w}$ and ${\sigma }^2$ : the normal-inverse-gamma, with density given by
我们使用 $\mathbf{X}$ 表示 $n\times d$ 设计矩阵，其中第 $i$ 行是与第 $i$ 次迭代中拉动的手臂相关联的特征向量 ${\mathbf{x}}_{a_i}$ 。我们用 $\mathbf{y}$ 表示观测值的 $n$ 向量。在这种情况下，对于 $\mathbf{w}$ 和 ${\sigma }^2$ 也存在一个自然的共轭先验：正态-逆伽马分布，其密度函数由下式给出

There are four prior hyperparameters in this case, ${\mathbf{w}}_0,{\mathbf{V}}_0$ , ${\alpha }_0$ ,and ${\beta }_0$ . As in the Beta-Bernoulli case,this conjugate prior enables the posterior distribution to be computed easily, leading to another normal-inverse-gamma distribution, now with parameters
在此情况下存在四个先验超参数，分别是 ${\mathbf{w}}_0,{\mathbf{V}}_0$ 、 ${\alpha }_0$ 和 ${\beta }_0$ 。与 Beta-Bernoulli 情形类似，该共轭先验使得后验分布易于计算，从而得到另一个正态-逆伽马分布，此时参数为

Integrating out the weight parameter $\mathbf{w}$ leads to coupling between the arms and makes it possible for the model to generalize observations of reward from one arm to another.
对权重参数 $\mathbf{w}$ 进行积分处理会导致各臂间产生耦合，使得模型能够将观察到的某臂奖励信息泛化至其他臂。

In this linear model,Thompson sampling draws a $\tilde{\mathbf{w}}$ from the posterior $p\left(\mathbf{w}\mid {\mathcal{D}}_n\right)$ and selects the arm with the highest expected reward under that parameter, i.e.,
在此线性模型中，汤普森采样从后验分布 $p\left(\mathbf{w}\mid {\mathcal{D}}_n\right)$ 中抽取一个 $\tilde{\mathbf{w}}$ ，并选择在该参数下预期奖励最高的臂，即：

After arm $a_{n+1}$ is pulled and $y_{n+1}$ is observed,the posterior model can be readily updated using equations (9-12).
当拉动臂 $a_{n+1}$ 并观察到 $y_{n+1}$ 后，可利用方程(9-12)直接更新后验模型。

Various generalizations can be immediately seen. For example, by embedding the arms of a multi-armed bandit into a feature space denoted $\mathcal{X}$ ,we can generalize to objective functions $f$ defined on the entire domain $\mathcal{X}$ ,thus unifying the multi-armed bandit problem with that of general global optimization:
可以立即看出多种推广形式。例如，通过将多臂老虎机的臂嵌入到特征空间 $\mathcal{X}$ 中，我们可以推广到定义在整个域 $\mathcal{X}$ 上的目标函数 $f$ ，从而将多臂老虎机问题与一般全局优化问题统一起来：

In the multi-armed bandit, the optimization is over a discrete and finite set ${\left\{{\mathbf{x}}_a\right\}}_{a=1}^K\subset \mathcal{X}$ ,while global optimization seeks to solve the problem on,e.g.,a compact set $\mathcal{X}\subset {\mathbb{R}}^d$ .
在多臂老虎机问题中，优化是在离散且有限的集合 ${\left\{{\mathbf{x}}_a\right\}}_{a=1}^K\subset \mathcal{X}$ 上进行的，而全局优化则旨在解决如紧致集 $\mathcal{X}\subset {\mathbb{R}}^d$ 上的此类问题。

As in other forms of regression, it is natural in increase the expressiveness of the model with non-linear basis functions. In particular,we can use $J$ basis functions ${\varphi }_j:\mathcal{X}\mapsto \mathbb{R}$ , for $j=1,\dots ,J$ ,and model the function $f$ with a linear combination
与其他形式的回归分析类似，通过非线性基函数来增强模型的表达能力是很自然的。具体来说，我们可以使用 $J$ 基函数 ${\varphi }_j:\mathcal{X}\mapsto \mathbb{R}$ ，对于 $j=1,\dots ,J$ ，并用线性组合来建模函数 $f$ 。

where $\mathrm{\Phi }\left(\mathbf{x}\right)$ is the column vector of concatenated features ${\left\{{\varphi }_j\left(\mathbf{x}\right)\right\}}_{j=1}^J$ . Common classical examples of such ${\varphi }_j$ include radial basis functions such as
其中 $\mathrm{\Phi }\left(\mathbf{x}\right)$ 是拼接特征 ${\left\{{\varphi }_j\left(\mathbf{x}\right)\right\}}_{j=1}^J$ 的列向量。此类 ${\varphi }_j$ 的经典常见示例包括径向基函数，例如

where $\mathbf{\Lambda }$ and ${\left\{{\mathbf{z}}_j\right\}}_{j=1}^J$ are model hyperparameters,and Fourier bases
其中 $\mathbf{\Lambda }$ 和 ${\left\{{\mathbf{z}}_j\right\}}_{j=1}^J$ 为模型超参数，以及傅里叶基函数

with hyperparameters ${\left\{{\omega }_j\right\}}_{j=1}^J$ .
包含超参数 ${\left\{{\omega }_j\right\}}_{j=1}^J$ 。

Recently, such basis functions have also been learned from data by training deep belief networks [71], deep neural networks [93], [144], or by factoring the empirical covariance matrix of historical data [146], [72]. For example, in [34] each sigmoidal layer of an $L$ layer neural network is defined as ${\mathcal{L}}_{\ell }\left(\mathbf{x}\right)\text{:=}\sigma \left({\mathbf{W}}_{\ell }\mathbf{x}+{\mathbf{B}}_{\ell }\right)$ where $\sigma$ is some sigmoidal non-linearity,and ${\mathbf{W}}_{\ell }$ and ${\mathbf{B}}_{\ell }$ are the layer parameters. Then the feature map $\mathrm{\Phi }:{\mathbb{R}}^d\mapsto {\mathbb{R}}^J$ can be expressed as $\mathrm{\Phi }\left(\mathbf{x}\right)={\mathcal{L}}_L\circ \cdots \circ {\mathcal{L}}_1\left(\mathbf{x}\right)$ ,where the final layer ${\mathcal{L}}_L$ has $J$ output units. In [144], the weights of the last layer of a deep neural network are integrated out to result in a tractable Bayesian model with flexible learned basis functions.
近期，此类基函数也通过训练深度信念网络[71]、深度神经网络[93][144]或分解历史数据的经验协方差矩阵[146][72]从数据中学习得到。例如文献[34]中，将 $L$ 层神经网络的每个 S 型层定义为 ${\mathcal{L}}_{\ell }\left(\mathbf{x}\right)\text{:=}\sigma \left({\mathbf{W}}_{\ell }\mathbf{x}+{\mathbf{B}}_{\ell }\right)$ ，其中 $\sigma$ 为某种 S 型非线性函数， ${\mathbf{W}}_{\ell }$ 和 ${\mathbf{B}}_{\ell }$ 是层参数。此时特征映射 $\mathrm{\Phi }:{\mathbb{R}}^d\mapsto {\mathbb{R}}^J$ 可表示为 $\mathrm{\Phi }\left(\mathbf{x}\right)={\mathcal{L}}_L\circ \cdots \circ {\mathcal{L}}_1\left(\mathbf{x}\right)$ ，最终层 ${\mathcal{L}}_L$ 包含 $J$ 个输出单元。文献[144]则将深度神经网络最后一层的权重积分处理，从而得到具有灵活学习基函数的可处理贝叶斯模型。

Regardless of the feature map $\mathrm{\Phi }$ ,when conditioned on these basis functions,the posterior over the weights $\mathbf{w}$ can be computed analytically using (9-12). Let $\mathrm{\Phi }\left(\mathbf{X}\right)$ denote the $n\times J$ matrix where ${\left[\mathrm{\Phi }\left(\mathbf{X}\right)\right]}_{i,j}={\varphi }_j\left({\mathbf{x}}_i\right)$ ; then the posterior is as in Bayesian linear regression,substituting $\mathrm{\Phi }\left(\mathbf{X}\right)$ for the design matrix $\mathbf{X}$ .
无论特征映射 $\mathrm{\Phi }$ 如何，当以这些基函数为条件时，权重 $\mathbf{w}$ 的后验分布可通过(9-12)解析计算得出。设 $\mathrm{\Phi }\left(\mathbf{X}\right)$ 表示 $n\times J$ 矩阵，其中 ${\left[\mathrm{\Phi }\left(\mathbf{X}\right)\right]}_{i,j}={\varphi }_j\left({\mathbf{x}}_i\right)$ ；则该后验分布与贝叶斯线性回归中的形式相同，只需将设计矩阵 $\mathbf{X}$ 替换为 $\mathrm{\Phi }\left(\mathbf{X}\right)$ 。

While simple linear models capture the dependence between bandit arms in a straightforward and expressive way, the model as described does not immediately apply to other types of observations, such as binary or count data. Generalized linear models (GLMs) [119] allow more flexibility in the response variable through the introduction of a link function. Here we examine the GLM for binary data such as might arise from drug trials or $\mathrm{AB}$ testing.
虽然简单线性模型以直观且富有表现力的方式捕捉了赌博机臂间的依赖关系，但所述模型并不直接适用于其他类型的观测数据，如二分类或计数数据。广义线性模型（GLMs）[119]通过引入链接函数，使响应变量具有更大的灵活性。此处我们研究适用于药物试验或 $\mathrm{AB}$ 测试等二分类数据的 GLM。

The generalized linear model introduces a link function $g$ that maps from the observation space into the reals. Most often,we consider the mean function $g^{-1}$ ,which defines the expected value of the response as a function of the underlying linear model: $\mathbb{E}\left[y\mid \mathbf{x}\right]=g^{-1}\left({\mathbf{x}}^T\mathbf{w}\right)=f\left(\mathbf{x}\right)$ . In the case of binary data, a common choice is the logit link function, which leads to the familiar logistic regression model in which $g^{-1}\left(z\right)=1/\left(1+\exp \{z\}\right)$ . In probit regression,the logistic mean function is replaced with the CDF of a standard normal. In either case,the observations $y_i$ are taken to be Bernoulli random variables with parameter $g^{-1}\left({\mathbf{x}}_i^T\mathbf{w}\right)$ .
广义线性模型引入了链接函数 $g$ ，它将观测空间映射到实数域。最常见的是考虑均值函数 $g^{-1}$ ，它定义了响应变量作为底层线性模型函数的期望值： $\mathbb{E}\left[y\mid \mathbf{x}\right]=g^{-1}\left({\mathbf{x}}^T\mathbf{w}\right)=f\left(\mathbf{x}\right)$ 。对于二分类数据，常用选择是 logit 链接函数，这导致了熟悉的逻辑回归模型，其中 $g^{-1}\left(z\right)=1/\left(1+\exp \{z\}\right)$ 。在 probit 回归中，逻辑均值函数被标准正态分布的累积分布函数替代。无论哪种情况，观测值 $y_i$ 都被视为参数为 $g^{-1}\left({\mathbf{x}}_i^T\mathbf{w}\right)$ 的伯努利随机变量。

Unfortunately, there is no conjugate prior for the parameters $\mathbf{w}$ when such a likelihood is used and so we must resort to approximate inference. Markov chain Monte Carlo (MCMC) methods [4] approximate the posterior with a sequence of samples that converge to the posterior; this is the approach taken in [135] on the probit model. In contrast, the Laplace approximation fits a Gaussian distribution to the posterior by matching the curvature of the posterior distribution at the mode. For example in [38], Bayesian logistic regression with a Laplace approximation was used to model click-throughs for the recommendation of news articles in a live experiment. In the generalized linear model, Thompson sampling draws a $\tilde{\mathbf{w}}$ from the posterior $p\left(\mathbf{w}\mid {\mathcal{D}}_n\right)$ using MCMC or a Laplace approximation, and then selects the arm with the highest expected reward given the sampled parameter $\tilde{\mathbf{w}}$ , i.e., $a_{n+1}=\arg \underset{a}{max}{g}^{-1}\left({\mathbf{x}}_a^T\tilde{\mathbf{w}}\right)$ .
遗憾的是，当采用此类似然函数时，参数 $\mathbf{w}$ 并不存在共轭先验分布，因此我们不得不依赖于近似推断方法。马尔可夫链蒙特卡罗（MCMC）方法[4]通过生成一系列收敛于后验分布的样本来近似后验分布；文献[135]在概率模型中就采用了这一方法。相比之下，拉普拉斯近似通过匹配后验分布在众数处的曲率，用高斯分布来拟合后验分布。例如，文献[38]在实时新闻推荐点击率建模中使用了基于拉普拉斯近似的贝叶斯逻辑回归。在广义线性模型中，汤普森抽样通过 MCMC 或拉普拉斯近似从后验分布 $p\left(\mathbf{w}\mid {\mathcal{D}}_n\right)$ 中抽取一个样本 $\tilde{\mathbf{w}}$ ，然后选择给定采样参数 $\tilde{\mathbf{w}}$ 时期望奖励最高的臂，即 $a_{n+1}=\arg \underset{a}{max}{g}^{-1}\left({\mathbf{x}}_a^T\tilde{\mathbf{w}}\right)$ 。

There are various strategies beyond Thompson sampling for Bayesian optimization that will be discussed in succeeding sections of the paper. However, before we can reason about which selection strategy is optimal, we need to establish what the goal of the series of sequential experiments will be. Historically, these goals have been quantified using the principle of maximum expected utility. In this framework, a utility function $U$ is prescribed over a set of experiments $\mathbf{X}\text{:=}{\left\{{\mathbf{x}}_i\right\}}_{i=1}^n$ , their outcomes $\mathbf{y}\text{:=}{\left\{y_i\right\}}_{i=1}^n$ ,and the model parameter $\mathbf{w}$ . The unknown model parameter and outcomes are marginalized out to produce the expected utility
在贝叶斯优化领域，除汤普森采样外，论文后续章节还将探讨多种策略。然而，在论证何种选择策略最优之前，我们需明确这一系列序贯实验的目标。历史上，这些目标常通过最大期望效用原则来量化。该框架下，效用函数 $U$ 被定义在一组实验 $\mathbf{X}\text{:=}{\left\{{\mathbf{x}}_i\right\}}_{i=1}^n$ 、其实验结果 $\mathbf{y}\text{:=}{\left\{y_i\right\}}_{i=1}^n$ 及模型参数 $\mathbf{w}$ 之上。通过边缘化未知模型参数与结果，最终计算出期望效用值。

which is then maximized to obtain the best set of experiments with respect to the given utility $U$ and the current posterior. The expected utility $\alpha$ is related to acquisition functions in Bayesian optimization, reviewed in Section IV. Depending on the literature, researchers have focussed on different goals which we briefly discuss here.
随后通过最大化该期望效用，可得到针对给定效用函数 $U$ 与当前后验分布的最优实验组合。期望效用 $\alpha$ 与贝叶斯优化中的采集函数密切相关，详见第四节综述。根据文献差异，研究者们关注的目标各有侧重，我们将在此简要讨论。

1) Active learning and experimental design: In this setting, we are usually concerned with learning about $\mathrm{w}$ ,which can be framed in terms of improving an estimator of $\mathbf{w}$ given the data. One popular approach is to select points that are expected to minimize the differential entropy of the posterior distribution $p\left(\mathbf{w}\mid \mathbf{X},\mathbf{y}\right)$ ,i.e.,maximize:
1) 主动学习与实验设计：在此情境下，我们通常关注如何更好地理解 $\mathrm{w}$ ，这可以转化为在给定数据条件下改进对 $\mathbf{w}$ 的估计问题。一种常见方法是选择预期能最小化后验分布 $p\left(\mathbf{w}\mid \mathbf{X},\mathbf{y}\right)$ 微分熵的数据点，即最大化：

In the Bayesian experimental design literature, this criterion is known as the $D$ -optimality utility and was first introduced by Lindley [98]. Since this seminal work, many alternative utilities have been proposed in the experimental design literature. See [37] for a detailed survey.
在贝叶斯实验设计文献中，该准则被称为 $D$ 最优性效用，最初由 Lindley[98]提出。自这一开创性工作以来，实验设计领域已提出许多替代性效用函数。详见[37]的详细综述。

In the context of $\mathrm{A}/\mathrm{B}$ testing,following this strategy would result in exploring all possible combinations of artwork, font, and sizes, no matter how bad initial outcomes were. This is due to the fact that the $D$ -optimality utility assigns equal value to any information provided about any advertisement configuration, no matter how effective.
在 $\mathrm{A}/\mathrm{B}$ 测试场景中，遵循此策略将导致探索所有可能的艺术品、字体和尺寸组合，无论初始结果多不理想。这是因为 $D$ 最优性效用对任何广告配置提供的信息赋予同等价值，无论其效果如何。

In contrast to optimal experimental design, Bayesian optimization explores uncertain arms $a\in \{1,\dots ,K\}$ ,or areas of the search space $\mathcal{X}$ ,only until they can confidently be ruled out as being suboptimal. Additional impressions of suboptimal ads would be a waste of our evaluation budget. In Section IV, we will introduce another differential entropy based utility that is better suited for the task of optimization and that partially bridges the gap between optimization and improvement of estimator quality.
与最优实验设计不同，贝叶斯优化仅探索那些尚未能明确排除为次优的不确定选项 $a\in \{1,\dots ,K\}$ 或搜索空间区域 $\mathcal{X}$ ，直到可以确信它们非最优为止。对次优广告的额外曝光将浪费我们的评估预算。在第四节中，我们将引入另一种基于微分熵的效用函数，它更适用于优化任务，并部分弥合了优化与估计器质量提升之间的鸿沟。

2) Multi-armed bandit: Until recently, the multi-armed bandit literature has focussed on maximizing the sum of rewards $y_i$ ,possibly discounted by a discount factor $\gamma \in (0,1]$ :
2) 多臂老虎机：直至最近，多臂老虎机文献主要关注于最大化奖励总和 $y_i$ ，可能通过折扣因子 $\gamma \in (0,1]$ 进行折现：

When $\gamma <1$ ,a Bayes-optimal sequence $\mathbf{X}$ can be computed for the Bernoulli bandit via dynamic programming, due to Gittins [59]. However, this solution is intractable for general reward distributions, and so in practice sequential heuristics are used and analyzed in terms of a frequentist measure, namely cumulative regret [92], [135], [146], [38], [127].
当 $\gamma <1$ 时，对于伯努利老虎机，由于 Gittins[59]的研究，可通过动态规划计算出贝叶斯最优序列 $\mathbf{X}$ 。然而，该解决方案对于一般奖励分布而言计算上不可行，因此实践中采用序列启发式方法，并以频率派指标——累计遗憾[92]、[135]、[146]、[38]、[127]进行分析。

Cumulative regret is a frequentist measure defined as
累计遗憾是一个频率派指标，其定义为

where $f_{\mathbf{w}}^{\star }\text{:=}\underset{a}{max}{f}_{\mathbf{w}}\left({\mathbf{x}}_a\right)$ denotes the best possible expected reward. Whereas the $D$ -optimality utility leads to too much exploration, the cumulative regret encourages exploitation by including intermediate selections $a_i$ in the final loss function $R_n$ . For certain tasks,this is an appropriate loss function: for example, when sequentially selecting ads, each impression incurs an opportunity cost. Meanwhile, for other tasks such as model selection, we typically have a predetermined evaluation budget for optimization and only the performance of the final recommended model should be assessed by the loss function.
其中 $f_{\mathbf{w}}^{\star }\text{:=}\underset{a}{max}{f}_{\mathbf{w}}\left({\mathbf{x}}_a\right)$ 表示最佳预期奖励。尽管 $D$ 最优性效用会导致过度探索，但累积遗憾通过将中间选择 $a_i$ 纳入最终损失函数 $R_n$ 来鼓励利用。对于某些任务，这是一个合适的损失函数：例如，在顺序选择广告时，每次展示都会产生机会成本。而对于其他任务（如模型选择），我们通常有预定的评估预算用于优化，且损失函数应仅评估最终推荐模型的性能。

Recently, there has been growing interest in the best arm identification problem, which is more suitable for the model selection task [104], [30], [7], [51], [50], [72]. When using Bayesian surrogate models, this is equivalent to performing Bayesian optimization on a finite, discrete domain. In this so-called pure exploration settings, in addition to a selection strategy,a recommendation strategy $\rho$ is specified to recommend an arm (or ad or drug) at the end of the experimentation based on observed data. The experiment is then judged via the simple regret,which depends on the recommendation $\overline{a}=\rho \left(\mathcal{D}\right)$ :
近来，最佳臂识别问题引发了越来越多的关注，该问题更适用于模型选择任务[104]、[30]、[7]、[51]、[50]、[72]。当采用贝叶斯代理模型时，这等同于在有限离散域上执行贝叶斯优化。在此类纯探索场景中，除了选择策略外，还需指定推荐策略 $\rho$ ，以便根据观测数据在实验结束时推荐一个臂（或广告/药物）。实验效果通过简单遗憾度来评判，该指标取决于推荐结果 $\overline{a}=\rho \left(\mathcal{D}\right)$ ：

In this section, we show how it is possible to marginalize away the weights in Bayesian linear regression and apply the kernel trick to construct a Bayesian non-parametric regression model. As our starting point, we assume the observation variance ${\sigma }^2$ is fixed and place a zero-mean Gaussian prior on the regression coefficients $p\left(\mathbf{w}\mid {\mathbf{V}}_0\right)=\mathcal{N}\left(0,{\mathbf{V}}_0\right)$ . In this case, we notice that it possible to analytically integrate out the weights, and in doing so we preserve Gaussianity:
本节将展示如何边缘化贝叶斯线性回归中的权重，并应用核技巧构建贝叶斯非参数回归模型。我们首先假设观测方差 ${\sigma }^2$ 固定，并对回归系数 $p\left(\mathbf{w}\mid {\mathbf{V}}_0\right)=\mathcal{N}\left(0,{\mathbf{V}}_0\right)$ 施加零均值高斯先验。此时可解析地积分掉权重，同时保持高斯性：

As noted earlier, it can be useful to introduce basis functions $\varphi$ and in the context of Bayesian linear regression we in effect replace the design matrix $\mathbf{X}$ with a feature mapping matrix $\mathrm{\Phi }=\mathrm{\Phi }\left(\mathbf{X}\right)$ . In Equation (22),this results in a slightly different Gaussian for weights in feature space:
如前所述，引入基函数 $\varphi$ 在贝叶斯线性回归背景下非常有用，实际上我们是用特征映射矩阵 $\mathrm{\Phi }=\mathrm{\Phi }\left(\mathbf{X}\right)$ 替代了设计矩阵 $\mathbf{X}$ 。在方程(22)中，这导致特征空间中的权重呈现略微不同的高斯分布：

Note that ${\mathbf{\Phi }\mathbf{V}}_0{\mathbf{\Phi }}^T\in {\mathbb{R}}^{n\times n}$ is a symmetric positive semidefinite matrix made up of pairwise inner products between each of the data in their basis function representations. The celebrated kernel trick emerges from the observation that these inner products can be equivalently computed by evaluating the corresponding kernel function $k$ for all pairs to form the matrix $\mathbf{K}$
注意 ${\mathbf{\Phi }\mathbf{V}}_0{\mathbf{\Phi }}^T\in {\mathbb{R}}^{n\times n}$ 是一个对称半正定矩阵，由数据在其基函数表示下的两两内积构成。著名的核技巧源于这样一个观察：这些内积可以通过评估相应核函数 $k$ 来等价计算，从而形成矩阵 $\mathbf{K}$ 。

The kernel trick allows us to specify an intuitive similarity between pairs of points,rather than a feature map $\mathbf{\Phi }$ ,which in practice can be hard to define. In other words, we can either think of predictions as depending directly on features $\mathbf{\Phi }$ ,as in the linear regression problem,or on kernels $k$ ,as in the lifted variant, depending on which paradigm is more interpretable or computationally tractable. Indeed,the former requires a $J\times J$ matrix inversion compared to the latter’s $n\times n$ .
核技巧让我们能够直接定义点对之间的直观相似性，而非依赖于实践中可能难以明确构建的特征映射 $\mathbf{\Phi }$ 。换言之，我们可以选择将预测视为直接依赖于特征 $\mathbf{\Phi }$ （如线性回归问题所示），或依赖于核函数 $k$ （如升维变体所示），具体取决于哪种范式更易解释或计算上更可行。实际上，前者需要进行 $J\times J$ 矩阵求逆运算，而后者仅需 $n\times n$ 。

Note also that this approach not only allows us to compute the marginal likelihood of data that have already been seen, but it enables us to make predictions of outputs ${\mathbf{y}}_{\star }$ at new locations ${\mathbf{X}}_{\star }$ . This can be done by observing that
还需注意的是，这种方法不仅能计算已观测数据的边缘似然，还能对新位置 ${\mathbf{X}}_{\star }$ 的输出值 ${\mathbf{y}}_{\star }$ 进行预测。其原理可通过观察得出：

Both the numerator and the denominator are Gaussian with the form appearing in Equation (23), and so the predictions are jointly Gaussian and can be computed via some simple linear algebra. Critically,given a kernel $k$ ,it becomes unnecessary to explicitly define or compute the features $\mathrm{\Phi }$ because both the predictions and the marginal likelihood only depend on $\mathbf{K}$ .
分子和分母均为式(23)所示的高斯形式，因此预测值联合服从高斯分布，可通过简单线性代数计算。关键在于，给定核函数 $k$ 后，无需显式定义或计算特征 $\mathrm{\Phi }$ ，因为预测值与边缘似然仅依赖于 $\mathbf{K}$ 。

By kernelizing a marginalized version of Bayesian linear regression, what we have really done is construct an object called a Gaussian process. The Gaussian process $\mathrm{GP}\left({\mu }_0,k\right)$ is a non-parametric model that is fully characterized by its prior mean function ${\mu }_0:\mathcal{X}\mapsto \mathbb{R}$ and its positive-definite kernel,or covariance function, $k:\mathcal{X}\times \mathcal{X}\mapsto \mathbb{R}$ [126]. Consider any finite collection ${}^2$ of $n$ points ${\mathbf{x}}_{1:n}$ ,and define variables $f_i\text{:=}f\left({\mathbf{x}}_i\right)$ and $y_{1:n}$ to represent the unknown function values and noisy observations, respectively. In Gaussian process regression, we assume that $\mathbf{f}\text{:=}{f}_{1:n}$ are jointly Gaussian and the observations $\mathbf{y}\text{:=}{y}_{1:n}$ are normally distributed given $\mathbf{f}$ ,resulting in the following generative model:
通过对贝叶斯线性回归的边缘化版本进行核化处理，我们实际上构建了一个称为高斯过程的对象。高斯过程 $\mathrm{GP}\left({\mu }_0,k\right)$ 是一种非参数模型，完全由其先验均值函数 ${\mu }_0:\mathcal{X}\mapsto \mathbb{R}$ 和正定核（即协方差函数） $k:\mathcal{X}\times \mathcal{X}\mapsto \mathbb{R}$ [126]所表征。考虑任意有限集合 ${}^2$ 中的 $n$ 个点 ${\mathbf{x}}_{1:n}$ ，并定义变量 $f_i\text{:=}f\left({\mathbf{x}}_i\right)$ 和 $y_{1:n}$ 分别表示未知函数值和含噪声的观测值。在高斯过程回归中，我们假设 $\mathbf{f}\text{:=}{f}_{1:n}$ 是联合高斯的，且观测值 $\mathbf{y}\text{:=}{y}_{1:n}$ 在给定 $\mathbf{f}$ 的条件下服从正态分布，由此得到以下生成模型：