基于高斯过程的贝叶斯优化算法基础题
字数 4763 2025-12-07 07:59:36

基于高斯过程的贝叶斯优化算法基础题

题目描述：考虑一个我们不知道解析表达式、但可以在任意点进行（有噪声或近似）评估的函数 \(f(x)\)，目标是找到其全局最小值（或最大值）。这是一个典型的高维、非凸、评估代价高昂的黑箱函数优化问题。要求使用贝叶斯优化（Bayesian Optimization, BO）框架，特别是以高斯过程（Gaussian Process, GP）作为代理模型，来解决此问题。我们将通过一个具体的一维示例，详细阐述其算法步骤、原理和实现逻辑。

题目分解与核心思想

贝叶斯优化是一种序列模型优化（Sequential Model-Based Optimization, SMBO）方法，适用于目标函数评估成本高、无导数信息的优化问题。其核心思想是：

  1. 构建代理模型：利用已有采样点，构建一个概率模型（常用高斯过程）来近似未知的目标函数。这个模型不仅给出预测值，还给出预测的不确定性（方差）。
  2. 通过采集函数决策：定义一个采集函数（Acquisition Function），它利用代理模型的预测和不确定性，在“探索”（在不确定性高的区域采样）和“利用”（在预测值好的区域采样）之间进行权衡，以决定下一个最佳采样点。
  3. 迭代更新：在选定的新点评估真实目标函数，将该数据加入历史观测集，更新代理模型，重复此过程直至满足停止条件。

解题步骤详解

步骤1：问题形式化与初始化

我们假设目标是最小化黑箱函数 \(f(x)\)，定义在域 \(\mathcal{X}\) 上（例如 \(x \in [0, 1]\)）。

  1. 初始采样：由于没有任何先验信息，我们先随机（或通过拉丁超立方采样）选择 \(n_{\text{init}}\) 个初始点 \(X_{\text{init}} = \{x_1, ..., x_{n_{\text{init}}}\}\)，并评估得到对应的函数值 \(y = f(X_{\text{init}})\)（可能含观测噪声 \(y = f(x) + \epsilon\)）。
  2. 目标：迭代地选择下一个采样点 \(x_{n+1}\)，使得经过 \(N\) 次总评估后，我们找到的点 \(x^*\) 的函数值 \(f(x^*)\) 尽可能小。

步骤2：构建高斯过程（GP）代理模型

高斯过程为函数 \(f(x)\) 提供了一个先验分布，并在观察到数据后，通过贝叶斯推理得到后验分布。

  1. GP定义：GP完全由其均值函数 \(m(x)\) 和协方差函数（核函数） \(k(x, x')\) 定义。我们通常设先验均值为常数（例如零），即 \(f(x) \sim \mathcal{GP}(0, k(x, x'))\)。
  2. 核函数选择：最常用的是平方指数（径向基函数，RBF）核：

\[ k(x_i, x_j) = \sigma_f^2 \exp\left(-\frac{1}{2l^2} (x_i - x_j)^2\right) + \sigma_n^2 \delta_{ij} \]

其中：
* $ \sigma_f^2 $ 是信号方差，控制函数值的变化幅度。
* $ l $ 是长度尺度，控制函数的平滑程度。
* $ \sigma_n^2 $ 是噪声方差（如果观测有噪声），$ \delta_{ij} $ 是克罗内克函数。
  1. 后验分布：给定观测数据 \(\mathcal{D}_{1:t} = \{(x_i, y_i)\}_{i=1}^{t}\)，对于任意新点 \(x_*\)，函数值 \(f(x_*)\) 的后验分布仍然是高斯分布：

\[ f(x_*) | \mathcal{D}_{1:t} \sim \mathcal{N}(\mu_t(x_*), \sigma_t^2(x_*)) \]

其中后验均值和方差为：

\[ \mu_t(x_*) = \mathbf{k}_*^T (\mathbf{K} + \sigma_n^2 \mathbf{I})^{-1} \mathbf{y} \]

\[ \sigma_t^2(x_*) = k(x_*, x_*) - \mathbf{k}_*^T (\mathbf{K} + \sigma_n^2 \mathbf{I})^{-1} \mathbf{k}_* \]

* $ \mathbf{K} $ 是 $ t \times t $ 的核矩阵，元素 $ K_{ij} = k(x_i, x_j) $。
* $ \mathbf{k}_* $ 是 $ t \times 1 $ 的向量，元素 $ k(x_i, x_*) $。
* $ \mathbf{y} = (y_1, ..., y_t)^T $。
  1. 超参数优化：在实际使用前，需要通过最大化边缘似然（证据）来优化核函数的超参数 \(\theta = (\sigma_f, l, \sigma_n)\)：

\[ \log p(\mathbf{y} | X, \theta) = -\frac{1}{2} \mathbf{y}^T (\mathbf{K}_{\theta} + \sigma_n^2 \mathbf{I})^{-1} \mathbf{y} - \frac{1}{2} \log |\mathbf{K}_{\theta} + \sigma_n^2 \mathbf{I}| - \frac{t}{2} \log 2\pi \]

步骤3：定义和优化采集函数

采集函数 \(\alpha(x; \mathcal{D}_{1:t})\) 基于当前的GP后验 \((\mu_t(x), \sigma_t(x))\) 构造，下一个采样点通过最大化采集函数得到：\(x_{t+1} = \arg\max_{x \in \mathcal{X}} \alpha(x)\)。
常用采集函数有：

  1. 期望改进（Expected Improvement, EI）：衡量在点 \(x\) 处，函数值相比当前最佳观测 \(y_{\text{best}} = \min(\mathbf{y})\) 的期望改进量。

\[ \text{EI}(x) = \mathbb{E}[\max(y_{\text{best}} - f(x), 0)] \]

利用GP后验，可解析计算：

\[ \text{EI}(x) = (y_{\text{best}} - \mu_t(x) - \xi)\Phi(Z) + \sigma_t(x) \phi(Z), \quad \text{若} \sigma_t(x) > 0 \]

其中 $ Z = \frac{y_{\text{best}} - \mu_t(x) - \xi}{\sigma_t(x)} $，$ \Phi $ 和 $ \phi $ 分别是标准正态分布的累积分布函数和概率密度函数。参数 $ \xi \geq 0 $ 用于平衡探索与利用。
  1. 置信上界（Upper Confidence Bound, GP-UCB）：

\[ \text{UCB}(x) = -\mu_t(x) + \beta_t \sigma_t(x) \]

对于最小化问题，我们取负均值（因为GP建模的是 $ f(x) $ 本身）。$ \beta_t $ 是一个随时间增加的参数，理论上能保证收敛。
  1. 概率改进（Probability of Improvement, PI）：相对简单，但容易陷入局部开发。

步骤4：迭代流程与算法实现

结合以上步骤，贝叶斯优化的算法循环如下：

  1. 输入：搜索空间 \(\mathcal{X}\)，黑箱函数 \(f\)，初始采样点数量 \(n_{\text{init}}\)，总评估预算 \(N\)。
  2. 初始化：在 \(\mathcal{X}\) 内随机采样 \(n_{\text{init}}\) 个点，得到初始数据集 \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n_{\text{init}}}\)。
  3. For \(t = n_{\text{init}}\) to \(N-1\) do：
    a. 拟合GP模型：使用当前数据集 \(\mathcal{D}\) 优化GP超参数，得到后验均值函数 \(\mu_t(x)\) 和方差函数 \(\sigma_t^2(x)\)。
    b. 优化采集函数：在定义域 \(\mathcal{X}\) 上，通过全局优化器（如多起点梯度下降、DIRECT、或随机搜索）找到最大化采集函数 \(\alpha(x)\) 的点 \(x_{t+1}\)。
    c. 评估目标函数：计算 \(y_{t+1} = f(x_{t+1})\)（可能带有噪声）。
    d. 更新数据集：\(\mathcal{D} \leftarrow \mathcal{D} \cup \{(x_{t+1}, y_{t+1})\}\)。
  4. 输出：从所有评估点中返回最佳点 \(x^* = \arg\min_{(x, y) \in \mathcal{D}} y\)。

示例演示

假设我们要最小化函数 \(f(x) = (6x-2)^2 \sin(12x-4)\)，定义域 \(x \in [0, 1]\)。这是一个有多个局部极小值的函数。

  1. 初始化：随机选3个点，例如 \(x = [0.1, 0.5, 0.9]\)，计算对应的 \(y\) 值。
  2. 第一次迭代：
    • 用这3个点拟合GP，得到整个区间上每个点的后验均值（预测曲线）和95%置信区间（均值 ± 1.96 * 标准差）。
    • 计算EI采集函数，它在当前最佳点（假设是 \(x=0.1\)）附近较低（因为不确定性小），在未探索区域（如 \(x=0.3\) 或 \(x=0.7\)）较高（因为不确定性大）。
    • 最大化EI，假设得到 \(x_4 = 0.3\)。评估 \(f(0.3)\) 并加入数据集。
  3. 后续迭代：
    • 用4个点重新拟合GP，置信区间在已采样点周围变窄，预测更准确。
    • 再次最大化EI，新点可能会在预测值低且有一定不确定性的区域产生。
    • 重复此过程。通常经过10-20次迭代，GP的预测能较好地近似真实函数，并且采样点会集中在全局最优点（此函数在 \(x \approx 0.757\) 处有全局最小值）周围。

关键要点与讨论

  • 探索 vs. 利用：采集函数的设计是核心。EI是实践中非常鲁棒和高效的选择。
  • 计算成本：主要开销在于每次迭代中GP的矩阵求逆（\(O(t^3)\)）和优化采集函数（需全局优化，但目标相对平滑）。
  • 高维扩展：在高维空间，GP的核函数需要精心设计，且搜索空间呈指数增长，使得采集函数优化和GP拟合都更具挑战性。常用方法包括使用加性核、随机嵌入或与局部搜索结合。
  • 优势：贝叶斯优化特别适用于评估代价高昂的问题（如超参数调优、实验设计、模拟优化），因为它能用尽可能少的评估找到较优解。

通过以上步骤，你不仅理解了贝叶斯优化的算法流程，也掌握了其核心组件：高斯过程回归、采集函数以及序列决策的框架。这是解决无导数黑箱优化问题的一种强大工具。

基于高斯过程的贝叶斯优化算法基础题 题目描述：考虑一个我们不知道解析表达式、但可以在任意点进行（有噪声或近似）评估的函数 \( f(x) \)，目标是找到其全局最小值（或最大值）。这是一个典型的高维、非凸、评估代价高昂的黑箱函数优化问题。要求使用贝叶斯优化（Bayesian Optimization, BO）框架，特别是以高斯过程（Gaussian Process, GP）作为代理模型，来解决此问题。我们将通过一个具体的一维示例，详细阐述其算法步骤、原理和实现逻辑。 题目分解与核心思想 贝叶斯优化是一种序列模型优化（Sequential Model-Based Optimization, SMBO）方法，适用于目标函数评估成本高、无导数信息的优化问题。其核心思想是： 构建代理模型 ：利用已有采样点，构建一个概率模型（常用高斯过程）来近似未知的目标函数。这个模型不仅给出预测值，还给出预测的不确定性（方差）。 通过采集函数决策 ：定义一个采集函数（Acquisition Function），它利用代理模型的预测和不确定性，在“探索”（在不确定性高的区域采样）和“利用”（在预测值好的区域采样）之间进行权衡，以决定下一个最佳采样点。 迭代更新 ：在选定的新点评估真实目标函数，将该数据加入历史观测集，更新代理模型，重复此过程直至满足停止条件。 解题步骤详解 步骤1：问题形式化与初始化 我们假设目标是最小化黑箱函数 \( f(x) \)，定义在域 \( \mathcal{X} \) 上（例如 \( x \in [ 0, 1 ] \)）。 初始采样 ：由于没有任何先验信息，我们先随机（或通过拉丁超立方采样）选择 \( n_ {\text{init}} \) 个初始点 \( X_ {\text{init}} = \{x_ 1, ..., x_ {n_ {\text{init}}}\} \)，并评估得到对应的函数值 \( y = f(X_ {\text{init}}) \)（可能含观测噪声 \( y = f(x) + \epsilon \)）。 目标 ：迭代地选择下一个采样点 \( x_ {n+1} \)，使得经过 \( N \) 次总评估后，我们找到的点 \( x^* \) 的函数值 \( f(x^* ) \) 尽可能小。 步骤2：构建高斯过程（GP）代理模型 高斯过程为函数 \( f(x) \) 提供了一个先验分布，并在观察到数据后，通过贝叶斯推理得到后验分布。 GP定义 ：GP完全由其均值函数 \( m(x) \) 和协方差函数（核函数） \( k(x, x') \) 定义。我们通常设先验均值为常数（例如零），即 \( f(x) \sim \mathcal{GP}(0, k(x, x')) \)。 核函数选择 ：最常用的是平方指数（径向基函数，RBF）核： \[ k(x_ i, x_ j) = \sigma_ f^2 \exp\left(-\frac{1}{2l^2} (x_ i - x_ j)^2\right) + \sigma_ n^2 \delta_ {ij} \] 其中： \( \sigma_ f^2 \) 是信号方差，控制函数值的变化幅度。 \( l \) 是长度尺度，控制函数的平滑程度。 \( \sigma_ n^2 \) 是噪声方差（如果观测有噪声），\( \delta_ {ij} \) 是克罗内克函数。 后验分布 ：给定观测数据 \( \mathcal{D} {1:t} = \{(x_ i, y_ i)\} {i=1}^{t} \)，对于任意新点 \( x_* \)，函数值 \( f(x_ ) \) 的后验分布仍然是高斯分布： \[ f(x_ ) | \mathcal{D} {1:t} \sim \mathcal{N}(\mu_ t(x ), \sigma_ t^2(x_ )) \] 其中后验均值和方差为： \[ \mu_ t(x_ ) = \mathbf{k}_ ^T (\mathbf{K} + \sigma_ n^2 \mathbf{I})^{-1} \mathbf{y} \] \[ \sigma_ t^2(x_ ) = k(x_ , x_ ) - \mathbf{k}_ ^T (\mathbf{K} + \sigma_ n^2 \mathbf{I})^{-1} \mathbf{k}_ * \] \( \mathbf{K} \) 是 \( t \times t \) 的核矩阵，元素 \( K_ {ij} = k(x_ i, x_ j) \)。 \( \mathbf{k} * \) 是 \( t \times 1 \) 的向量，元素 \( k(x_ i, x * ) \)。 \( \mathbf{y} = (y_ 1, ..., y_ t)^T \)。 超参数优化 ：在实际使用前，需要通过最大化边缘似然（证据）来优化核函数的超参数 \( \theta = (\sigma_ f, l, \sigma_ n) \)： \[ \log p(\mathbf{y} | X, \theta) = -\frac{1}{2} \mathbf{y}^T (\mathbf{K} {\theta} + \sigma_ n^2 \mathbf{I})^{-1} \mathbf{y} - \frac{1}{2} \log |\mathbf{K} {\theta} + \sigma_ n^2 \mathbf{I}| - \frac{t}{2} \log 2\pi \] 步骤3：定义和优化采集函数 采集函数 \( \alpha(x; \mathcal{D} {1:t}) \) 基于当前的GP后验 \( (\mu_ t(x), \sigma_ t(x)) \) 构造，下一个采样点通过最大化采集函数得到：\( x {t+1} = \arg\max_ {x \in \mathcal{X}} \alpha(x) \)。 常用采集函数有： 期望改进（Expected Improvement, EI） ：衡量在点 \( x \) 处，函数值相比当前最佳观测 \( y_ {\text{best}} = \min(\mathbf{y}) \) 的期望改进量。 \[ \text{EI}(x) = \mathbb{E}[ \max(y_ {\text{best}} - f(x), 0) ] \] 利用GP后验，可解析计算： \[ \text{EI}(x) = (y_ {\text{best}} - \mu_ t(x) - \xi)\Phi(Z) + \sigma_ t(x) \phi(Z), \quad \text{若} \sigma_ t(x) > 0 \] 其中 \( Z = \frac{y_ {\text{best}} - \mu_ t(x) - \xi}{\sigma_ t(x)} \)，\( \Phi \) 和 \( \phi \) 分别是标准正态分布的累积分布函数和概率密度函数。参数 \( \xi \geq 0 \) 用于平衡探索与利用。 置信上界（Upper Confidence Bound, GP-UCB） ： \[ \text{UCB}(x) = -\mu_ t(x) + \beta_ t \sigma_ t(x) \] 对于最小化问题，我们取负均值（因为GP建模的是 \( f(x) \) 本身）。\( \beta_ t \) 是一个随时间增加的参数，理论上能保证收敛。 概率改进（Probability of Improvement, PI） ：相对简单，但容易陷入局部开发。 步骤4：迭代流程与算法实现 结合以上步骤，贝叶斯优化的算法循环如下： 输入 ：搜索空间 \( \mathcal{X} \)，黑箱函数 \( f \)，初始采样点数量 \( n_ {\text{init}} \)，总评估预算 \( N \)。 初始化 ：在 \( \mathcal{X} \) 内随机采样 \( n_ {\text{init}} \) 个点，得到初始数据集 \( \mathcal{D} = \{(x_ i, y_ i)\} {i=1}^{n {\text{init}}} \)。 For \( t = n_ {\text{init}} \) to \( N-1 \) do ： a. 拟合GP模型 ：使用当前数据集 \( \mathcal{D} \) 优化GP超参数，得到后验均值函数 \( \mu_ t(x) \) 和方差函数 \( \sigma_ t^2(x) \)。 b. 优化采集函数 ：在定义域 \( \mathcal{X} \) 上，通过全局优化器（如多起点梯度下降、DIRECT、或随机搜索）找到最大化采集函数 \( \alpha(x) \) 的点 \( x_ {t+1} \)。 c. 评估目标函数 ：计算 \( y_ {t+1} = f(x_ {t+1}) \)（可能带有噪声）。 d. 更新数据集 ：\( \mathcal{D} \leftarrow \mathcal{D} \cup \{(x_ {t+1}, y_ {t+1})\} \)。 输出 ：从所有评估点中返回最佳点 \( x^* = \arg\min_ {(x, y) \in \mathcal{D}} y \)。 示例演示 假设我们要最小化函数 \( f(x) = (6x-2)^2 \sin(12x-4) \)，定义域 \( x \in [ 0, 1 ] \)。这是一个有多个局部极小值的函数。 初始化 ：随机选3个点，例如 \( x = [ 0.1, 0.5, 0.9 ] \)，计算对应的 \( y \) 值。 第一次迭代 ： 用这3个点拟合GP，得到整个区间上每个点的后验均值（预测曲线）和95%置信区间（均值 ± 1.96 * 标准差）。 计算EI采集函数，它在当前最佳点（假设是 \( x=0.1 \)）附近较低（因为不确定性小），在未探索区域（如 \( x=0.3 \) 或 \( x=0.7 \)）较高（因为不确定性大）。 最大化EI，假设得到 \( x_ 4 = 0.3 \)。评估 \( f(0.3) \) 并加入数据集。 后续迭代 ： 用4个点重新拟合GP，置信区间在已采样点周围变窄，预测更准确。 再次最大化EI，新点可能会在预测值低且有一定不确定性的区域产生。 重复此过程。通常经过10-20次迭代，GP的预测能较好地近似真实函数，并且采样点会集中在全局最优点（此函数在 \( x \approx 0.757 \) 处有全局最小值）周围。 关键要点与讨论 探索 vs. 利用 ：采集函数的设计是核心。EI是实践中非常鲁棒和高效的选择。 计算成本 ：主要开销在于每次迭代中GP的矩阵求逆（\( O(t^3) \)）和优化采集函数（需全局优化，但目标相对平滑）。 高维扩展 ：在高维空间，GP的核函数需要精心设计，且搜索空间呈指数增长，使得采集函数优化和GP拟合都更具挑战性。常用方法包括使用加性核、随机嵌入或与局部搜索结合。 优势 ：贝叶斯优化特别适用于评估代价高昂的问题（如超参数调优、实验设计、模拟优化），因为它能用尽可能少的评估找到较优解。 通过以上步骤，你不仅理解了贝叶斯优化的算法流程，也掌握了其核心组件：高斯过程回归、采集函数以及序列决策的框架。这是解决无导数黑箱优化问题的一种强大工具。