论文阅读：加性模型解决高维贝叶斯优化问题

论文： High Dimensional Bayesian Optimization and Bandits via Additive Models

[!tldr] 本篇导读
本篇是一个非常经典的高维 BO 作品 ¹，也根植于统计学思维，读本篇论文的目的和想法有几个：

1. HDBO (High-Dimensional Bayesian Optimization) 仍然是具有很多问题的领域，同时也有很多高维统计的工具可供借鉴；
2. 本篇是高维 BO 的一个重要会议论文 (ICML)，引用量在 Web of Science 上有 230 左右，在没那么热门的 BO 领域当中已经算很高了.
3. 本篇适合我们衔接之前的 GP-UCB 方法，同时也和 Hastie 等大佬提出的 Generalized Additive Models ² 做到了 A+B ，所以对于统计背景的研究者而言，这篇的很多想法值得借鉴.

本篇的主要内容是提出了使用加性模型对付高维贝叶斯优化问题的思路，并在此基础上给出了 Add-GP-UCB 方法.

高维 BO 的困境

本部分相当于一个导读，高维 BO 的难度其实和高维统计的难度紧密挂钩，主要还是在几个对象上有比较具体的问题：

1. 代理模型的高维估计较为困难：非参模型（高斯过程等）在高维下的估计很困难，这点在高斯过程回归上体现的会很明显；
2. 采集函数优化困难：采集函数的优化在高维情况下会比较困难.

例如，在第二点上，优化采集函数可以理解为优化一个显式的非凸多峰函数，在 GP-UCB 的场景下，我们实际上就是最大化：

$$ \varphi_{t}(\boldsymbol{x}) = \mathrm{UCB}(\boldsymbol{x}) $$

它在一般场景下是非凸的，可能有多个峰值，如果是二维情况下，我们还尚可用一些多起点凸优化方法来处理，但是如果维度达到很高（例如一百维），此时光是优化这样的函数就足够消耗计算量.

为此，高维 BO 的推进需要简化上述的问题，现有的研究通常会选择一些下面的假设 ³：

1. 高维目标函数的变量实际上只有一个低维的子空间起作用，这种想法实际上就引入了高维统计当中的变量选择 (feature selection) 或者基于嵌入 (embedding) 的方法；
2. 高维目标函数实际上是一些低维函数的加性结构；

本文实际上引入的就是其中的第二点，也就是引入了加性结构.

问题建立

黑盒优化

设黑盒函数 $f: \mathcal{X}\to \mathbb{R}$ ，其中 $\mathcal{X} \subset \mathbb{R}^{D}$ ，一般设定为方体 $[0,1]^{D}$ （这种假设合理吗？），对于任意的 $\boldsymbol{x}\in \mathcal{X}$ ，我们采样 (query) 得到的都是带噪声的点：$f(\boldsymbol{x})+\varepsilon$ ；为了最大化，考虑设

$$ \boldsymbol{x}_{*} = \arg\max_{\boldsymbol{x}}f(\boldsymbol{x}) $$

在时间 $t$ ，考虑利用输入点 $\boldsymbol{x}_{t}$ ，当其不是最优点时，就会产生即时遗憾 (instantaneous regret)：

$$ r_{t} = f(\boldsymbol{x}_{*})-f(\boldsymbol{x}_{t}) $$

当时间从 $1$ 到 $T$ 时有累积遗憾：

$$ R_{T} = \sum\limits_{t=1}^{T} r_{t} = T f(\boldsymbol{x}_{*}) - \sum\limits_{t=1}^{T} f(\boldsymbol{x}_{t}) $$

目标很简单，就是让累计遗憾有次线性界：

$$ \lim_{T\to \infty} \frac{R_{T}}{T} = 0 $$

加性结构假设

本节是文中最为重要的假设：加性结构假设，也就是假设 $f$ 是一系列低维函数的和函数：

$$ f(\boldsymbol{x}) = \sum\limits_{i=1}^{M} f^{(i)}(\boldsymbol{x}^{(i)}) $$

这里每个 $\boldsymbol{x}^{(i)} \in \mathcal{X}^{(i)} = [0,1]^{d_{i}}$ ，可以将 $\mathcal{X}^{(i)}$ 理解为一个组 (Group) ，然后注意 $\left\lbrace \mathcal{X}^{(i)} \right\rbrace_{i=1}^{M}$ 都是不交的，也就是它们不会有相同的维度.

这里原文的符号有些不太好，使用的是并，也就会写成

$$ \boldsymbol{x} = \bigcup_{i=1}^{M} \boldsymbol{x}^{(i)},\quad \mathcal{X} = \bigcup_{i=1}^{M} \mathcal{X}^{(i)} $$

但是我就觉得这样的写法不太好，事实上应该视为一种向量的拼接，例如对于 $4$ 维，假设分组只有两组 $\mathcal{X}^{(1)}, \mathcal{X}^{(2)}$ ，$d_{1}=d_{2}=2$ ，此时就应该更像是：

$$ \begin{aligned} & \boldsymbol{x} = (x_{1}, x_{2}, x_{3}, x_{4}) \\ & \boldsymbol{x}^{(1)} = (x_{1}, x_{2}) \\ & \boldsymbol{x}^{(2)} = (x_{3}, x_{4}) \end{aligned} $$

进而 $\boldsymbol{x} = \boldsymbol{x}^{(1)}\oplus \boldsymbol{x}^{(2)}$ ，这里的 $\oplus$ 可以理解为向量（“字符串”）拼接，因此也就更符合我们的表达习惯.

此外，这里还有一个假设就是所有的 $d_{j}$ 都有一个 $d$ 的界，满足：

$$ d_{j} \leqslant d \ll D $$

这里 $d$ 的界很重要，会影响后面的遗憾界假设.

高斯过程假设

贝叶斯优化建立代理模型时，本文考虑的是用高斯过程，也就是

$$ f\sim \mathcal{GP}(\mu, \kappa) $$

然后 $\mu: \mathcal{X}^{n}\to \mathbb{R}$ 和 $\kappa: \mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 都是贝叶斯优化常见的内容，基于加性模型假设的时候，实际上还会对子函数有假设：

$$ f^{(j)} \sim \mathcal{GP}(\mu^{(j)}, \kappa^{(j)}) $$

其中 $\mu^{(j)}: \mathcal{X}^{n}\to \mathbb{R}$ 和 $\kappa^{(j)}: \mathcal{X}\times \mathcal{X}\to \mathbb{R}$ ，此时利用正态分布的可加性可以得到：

[!note] 观察
设 $y = f(\boldsymbol{x})+ \varepsilon$ ，其中 $\varepsilon\sim \mathcal{N}(0, \eta^{2})$ ，设 $\delta$ 为 Kronecker 记号，则有

$$ y \sim \mathcal{GP}(\mu(\boldsymbol{x}), \kappa(\boldsymbol{x}, \boldsymbol{x}')+ \eta^{2} \delta(\boldsymbol{x}, \boldsymbol{x}') ) $$

其中

$$ \mu(\boldsymbol{x}) = \sum\limits_{j=1}^{M} \mu^{(j)}(\boldsymbol{x}^{(j)}) ,\quad \kappa(\boldsymbol{x}, \boldsymbol{x}') = \sum\limits_{j=1}^{M} \kappa^{(j)}(\boldsymbol{x}^{(j)}, \boldsymbol{x}^{(j)\prime} ) $$

这里面，由于 $\kappa^{(j)}$ 的输入 $\mathcal{X}^{(j)}$ 是 $d_{j}$ 维的，因此我们之后称 $\kappa^{(j)}$ 是 $d_{j}$ 阶的.

基于这个性质，我们接下来讨论算法.

Add-GP-UCB 算法

Recap: GP-UCB

GP-UCB 算法是一个简单好用的算法，来源论文是 ICML 2010 ⁴ ，我们简单过一遍：我们令

$$ \boldsymbol{X} = (\boldsymbol{x}_{1},\cdots , \boldsymbol{x}_{t-1}) $$

设新的点为 $\boldsymbol{x}_{*}$ ，我们想得到 $f_{*} = f(\boldsymbol{x}_{*})$ 的后验分布，根据高斯过程回归的结论可以得到

$$ \begin{pmatrix} \boldsymbol{y} \\ f_{*}\end{pmatrix}\sim \mathcal{N}\left(\boldsymbol{0, \begin{pmatrix}\kappa(\boldsymbol{X}, \boldsymbol{X}) + \eta^{2} \boldsymbol{I} & \kappa(\boldsymbol{X}, \boldsymbol{x}_{*})^{\top} \\ \kappa(\boldsymbol{x}_{*}, \boldsymbol{X}) & \kappa(\boldsymbol{x}_{*}, \boldsymbol{x}_{*}) \end{pmatrix}}\right) $$

其中

$$ \kappa(\boldsymbol{x}_{*}, \boldsymbol{X}) = (\kappa(\boldsymbol{x}_{*}, \boldsymbol{x}_{1}), \cdots, \kappa(\boldsymbol{x}_{*}, \boldsymbol{x}_{t-1})) $$

写 $\Delta = \kappa(\boldsymbol{X}, \boldsymbol{X}) + \eta^{2} \boldsymbol{I}\in \mathbb{R}^{t\times t}$ ，有

$$ f_{*}\mid \boldsymbol{x}_{*}, \boldsymbol{X}, \boldsymbol{y} \sim \mathcal{N}(\kappa(\boldsymbol{x}_{*}, \boldsymbol{X}) \Delta^{-1}\boldsymbol{y},\quad \kappa(\boldsymbol{x}_{*} , \boldsymbol{x}_{*}) - \kappa(\boldsymbol{x}_{*}, \boldsymbol{X}) \Delta^{-1} \kappa(\boldsymbol{X}, \boldsymbol{x}_{*})^{\top}) \tag{2.1} $$

这里我们简单记为

$$ f_{*}\mid \boldsymbol{x}_{*}, \boldsymbol{X}, \boldsymbol{y} \sim \mathcal{N}(\mu_{t-1}(\boldsymbol{x}_{*}),\sigma^{2}_{t-1}(\boldsymbol{x}_{*})) $$

GP-UCB 算法的想法就是利用后验分布的参数来构建置信区间，取置信区间的上侧作为采集函数的值，这就是 GP-UCB ，UCB 代表的就是 Upper Confidence Bound ，GP 则是 Gaussian Process. UCB 的具体表达式为：

$$ \mathrm{UCB}(\boldsymbol{z}) = \mu_{t-1}(\boldsymbol{z}) + \sqrt{\beta_{t}} \sigma_{t-1}(\boldsymbol{z}) $$

算法流程如下：

这里面还有一个 $\beta_{t}$ 是参数，为什么会有这样的一个参数呢？原因是为了保证区间的覆盖概率保持在一个相对固定的值，通过动态调整使得区间灵活，保证覆盖概率.

对于这个老算法，它能达到相对不错的遗憾界：

[!note] 定理：GP-UCB 的遗憾界
令 $\delta\in (0,1)$ 且 $\beta_{t} = 2\log \left(\frac{|D|t^{2}\pi^{2}}{6\delta}\right)$ ，使用 GP-UCB 算法，对 $f\sim \mathcal{GP}(0, \kappa)$ 可以使得遗憾界高概率达到 $\mathcal{O}^{*}(T \gamma_{T} \log |D|)$ ，更具体的说：

$$ \mathbb{P} \left\lbrace R_{T} \leqslant \sqrt{C_{1} T \beta_{T} \gamma_{T}}, \quad \forall T \geqslant 1 \right\rbrace \geqslant 1 - \delta $$

其中 $C_{1} = 8/\log(1+\sigma^{-2})$ .

这里面，$\mathcal{O}^{*}$ 是 $\mathcal{O}$ 的一个变种，将对数常数因子压缩了，然后 $\gamma_{T}$ 是一个很重要的量：

[!note] 定义：最大信息增益 (Maximum Information Gain)
经过 $T$ 轮交互后，我们定义 $A = \left\lbrace \boldsymbol{x}_{1},\cdots , \boldsymbol{x}_{T} \right\rbrace \subset \mathcal{X}$ 为有限样本集合，此时 $\boldsymbol{f}_{A} = \left\lbrace f(\boldsymbol{x}) \right\rbrace_{\boldsymbol{x}\in A}$ 记为对应的函数值，$\boldsymbol{y}_{A} = \left\lbrace f(\boldsymbol{x}) + \varepsilon_{\boldsymbol{x}} \right\rbrace_{\boldsymbol{x}\in A}$ 也代表带噪声的观测，定义：

$$ \gamma_{T} = \max_{A \subset \mathcal{X}, |A| = T} I(\boldsymbol{y}_{A}; \boldsymbol{f}_{A}) $$

其中 $I$ 是 Shannon 理论的互信息，$\gamma_{T}$ 称为最大信息增益.

如果学过 ID3 决策树的读者，一定会想起决策树也有类似的定义，其实意义也是类似的.

首先要申明的是，这个概念有贝叶斯试验设计的背景 ⁵，这个在 GP-UCB 原文当中说明了 ⁴ ：

One approach to maximizing $f$ is to first choose points $\boldsymbol{x}_{t}$ so as to estimate the function globally well, then play the maximum point of our estimate. How can we learn about $f$ as rapidly as possible? This question comes down to Bayesian Experimental Design (henceforth “ED”; see Chaloner & Verdinelli 1995)

然后最大信息增益可以这么理解，根据原文的公式

$$ I(\boldsymbol{y}_{A}; \boldsymbol{f}_{A}) = H(\boldsymbol{y}_{A}) - H(\boldsymbol{y}_{A} \mid \boldsymbol{f}_{A}) = H(\boldsymbol{f}_{A}) - H(\boldsymbol{f}_{A} \mid \boldsymbol{y}_{A}) $$

实际上可以理解为在通过观测 $\boldsymbol{y}_{A}$ 之后，对 $\boldsymbol{f}_{A}$ 的不确定性减少了多少.

Add-GP-UCB 算法

本文的算法改进，就是将 GP-UCB 进行加性模型的改进，得到加性高斯过程上置信界 (Add-GP-UCB)：

$$ \widetilde{\varphi}_{t}(\boldsymbol{x}) = \mu_{t-1}(\boldsymbol{x}) + \beta_{t}^{\frac{1}{2}} \sum\limits_{j=1}^{M} \sigma_{t-1}^{(j)}(\boldsymbol{x}^{(j)}) \tag{add-gp-ucb} $$

注意这里面的各个参数实际上也是根据类似于 $(2.1)$ 的式子来的，这里加性模型的改版是：

$$ f_{*}^{(j)}\mid \boldsymbol{x}_{*}, \boldsymbol{X}, \boldsymbol{y} \sim \mathcal{N}(\kappa^{(j)}(\boldsymbol{x}_{*}^{(j)}, \boldsymbol{X}^{(j)}) \Delta^{-1}\boldsymbol{y},\quad \kappa^{(j)}(\boldsymbol{x}^{(j)}_{*} , \boldsymbol{x}^{(j)}_{*}) - \kappa^{(j)}(\boldsymbol{x}^{(j)}_{*}, \boldsymbol{X}^{(j)}) \Delta^{-1} \kappa(\boldsymbol{X}^{(j)}, \boldsymbol{x}_{*}^{(j)})^{\top}) $$

最后给出 Add-GP-UCB 算法：

这里的 Add-GP-UCB 算法实际上很简单，也就是根据加性模型拆分，对每个拆分的组进行采集函数 (GP-UCB) 的优化.

这种方法有什么好处呢？其实看到这个算法的时候就可以想到：

1. 这种益于并行，每个组是不交的，说明同步并行是相互之间不会有影响的；(这里是我个人的观察而非原文提及)
2. 单个采集函数维度降低，也更容易找到最优点.

这里简单分析一下计算量，$(\text{add-gp-ucb})$ 当中其实最大的麻烦之处在于后验方差的计算：

$$ \kappa(\boldsymbol{x}_{*} , \boldsymbol{x}_{*}) - \kappa(\boldsymbol{x}_{*}, \boldsymbol{X}) \Delta^{-1} \kappa(\boldsymbol{X}, \boldsymbol{x}_{*})^{\top} $$

这里面开销的大头在于乘积，$\Delta^{-1}$ 和 GP-UCB 一样为 $\mathcal{O}(t^{3})$ ，但是一次计算可以多次复用，所以可以不考虑求逆的差别.

• 对于 GP-UCB ：

  • 核向量 $\kappa(\boldsymbol{x}_{*}, \boldsymbol{X})$ 的计算本身就是 $\mathcal{O}(D t)$ 的计算量；
  • 乘积上，$\Delta^{-1}$ 和核向量的乘积是 $\mathcal{O}(t^{2})$ 的计算量.
  • 因此综合来看，计算量应该是 $\mathcal{O}(Dt + t^{2})$ .

• 对于 Add-GP-UCB：

  • 区别在于核向量的计算是 $\mathcal{O}(d_{j} t)$ ，然后 $d_{j}\leqslant d \ll D$ ，如果使用并行，那么实际上最后的计算量就会是：
  • $\mathcal{O}(dt+ t^{2})$

当然，论文提到的非常重要的一点是：虽然在 $t$ 逐渐增大时，$t^{2}$ 才是主导，但是每一轮的优化都需要考虑内层优化的迭代时间，对于 $D$ 维高维的情形，这将是灾难性的. 如果操作过其他白盒优化算法，就会知道高维函数的优化耗时远比低维多.

算法分析

有了 Add-GP-UCB ，还需要解决几个问题：

1. GP-UCB 的收敛性证明方法是否还可行？Add-GP-UCB 的遗憾界有何变化？
2. Add-GP-UCB 算法是对各个子函数进行优化，这种优化方法能否真正得到全局最优解？

下面从本文内容出发说明.

核函数选择

这里就是考虑使用最广泛的两个核函数：RBF 核 (SE 核) ：

$$ \kappa_{\sigma, h}(\boldsymbol{x}, \boldsymbol{x}') = \sigma \exp\left(- \frac{r^{2}}{2h^{2}}\right) $$

还有 Matérn 核：

$$ \kappa_{\nu, h}(\boldsymbol{x}, \boldsymbol{x}') = \dfrac{2^{1-\nu}}{\Gamma(\nu)} \left(\dfrac{\sqrt{2 \nu}r}{h}\right)^{\nu} B_{\nu}\left(\dfrac{\sqrt{2 \nu}r}{h}\right) $$

这里面 $r = \|\boldsymbol{x} - \boldsymbol{x}'\|_{2}$ .

[!note] 假设 1
令 $f$ 是核函数为 $\kappa$ 的高斯过程，并且 $\kappa(\cdot, \boldsymbol{x})$ 对任意 $\boldsymbol{x}$ 都是 $L$-Lipschitz 的，更进一步，对 $f$ 的偏导满足下面的高概率界，即存在 $a,b >0$ 使得：

$$ \mathbb{P}\left(\sup_{x} \left|\dfrac{\partial f(x)}{\partial x_{i}}\right| > J\right) \leqslant a \mathrm{e}^{- (J/b)^{2}} $$

这里的假设当中，对核函数的要求实际上 [[Matérn 核]] 与 SE 核都满足. 满足上述假设 1 后可以得到对最大信息增益的阶估计.

[!note] 定理：最大信息增益的阶
假定 $\kappa$ 有加性形式，然后对于每个 $\kappa^{(j)}$ 都满足假设 1，不妨假设 $\kappa(\boldsymbol{x}, \boldsymbol{x}')=1$ ，那么

1. 如果 $\kappa^{(j)}$ 都是 $d_{j}$ 阶的 SE 核，其中 $d_{j} \leqslant d$ ，那么有 $\gamma_{T}\in \mathcal{O}(Dd^{d} (\log T)^{d+1})$ .
2. 如果 $\kappa^{(j)}$ 都是 $d_{j}$ 阶的 Matérn 核，其中 $d_{j} \leqslant d$ 且 $\nu > 2$，那么有 $\gamma_{T}\in \mathcal{O}(D 2^{d} T^{\frac{d(d+1)}{2\nu + d(d+1)}} (\log T))$ .

有了 $\gamma_{T}$ 的界，其实这一块也相当于会在后面的遗憾界出现，它的出现使得为了遗憾界能达到次线性，核函数的参数是有一定要求的.

遗憾界

最终我们给出遗憾界，也就是：

[!note] 定理：Add-GP-UCB 的遗憾界
假定 $f$ 是由 $f^{(j)}\sim \mathcal{GP}(0, \kappa^{(j)}), \quad j=1,2,\cdots, M$ 构成的加性模型，令其中所有的核函数 $\kappa^{(j)}$ 都满足假设 1，更进一步，对于采集函数 $\widetilde{\varphi}_{t}$ 的优化，假定在时间 $t$ 时我们的准确程度达到 $\zeta_{0} t^{- \frac{1}{2}}$ ，选择 $\delta\in (0,1)$ 并令

$$ \beta_{t} = 2 \log \left(\frac{M \pi^{2} t^{2}}{2\delta}\right) + 2 d \log (D t^{3})\in \mathcal{O}(d\log t) $$

那么 Add-GP-UCB 可达到累积遗憾的界为：$R_{T}\in \mathcal{O}(\sqrt{D \gamma_{T} T \log T})$ ，并且简单遗憾则满足 $S_{T}\in \mathcal{O}(D \gamma_{T} \log T /T)$ ，在概率为 $> 1- \delta$ 的意义下有

$$ \forall T \geqslant 1 , \quad R_{T} \leqslant \sqrt{8 C_{1} \beta_{T} M T \gamma_{t}} + 2 \zeta_{0} \sqrt{T} + C_{2} $$

其中 $C_{1} = 1/\log(1+\eta^{-2})$ ，而 $C_{2}$ 则是依赖于 $a,b,D,\delta, L$ 和 $\eta$ 的常数.

看着很吓人，其实就是达到了次线性界，证明这里也不详细叙述了.

更实用的 Add-GP-UCB 算法

Add-GP-UCB 算法有个重要的问题在于需要提前知道加性模型的结构，但是对于一个黑盒函数，如果不知道表达式，还怎么可能知道它的加性结构呢？基于这种矛盾，作者提出来的方案是给出一个更实用的 Add-GP-UCB 算法 (Practical Add-GP-UCB).

对于加性模型，既然不能提前了解，那么根据过往对于高斯过程的书籍 ⁶ ，本文的主要想法有：

1. 核函数的超参数调优方法采取计算边际似然的方法；
2. 加性结构的分割方式考虑取 $\mathcal{O}(D)$ 这么多的可能方式，然后计算它们的边际似然，取最大的分割方式.

调参的不是每轮都调，而是每 $N_{cyc}$ 轮调，和图片当中的算法是一致的. 需要注意的是 $\beta_{t}$ 也是选用了相当简单易行的，但是又不是常数，这是遗憾界的分析带来的结果.

代码复现

这里没有多说的，我们在之后的博文给出 Code ，这里仅仅就说明一下一个细节就是本文沿袭了 2010 年一篇论文的方式 ⁷ ，使用 DiRect 算法来进行采集函数的优化.