博客
DREAM 算法的核心组件：子空间采样与交叉概率

DREAM 算法的核心组件：子空间采样与交叉概率

May 11, 2019

DREAM 算法的卓越性能使其在复杂参数估计和不确定性分析等领域中崭露头角。然而，DREAM 算法的成功并非偶然，而是源于其精心设计的核心组件：子空间采样技术和交叉概率。这两个组件不仅大大提高了算法在高维空间中的效率，还赋予了算法强大的自适应能力，使其能够在各种复杂问题中表现出色。

子空间采样的原理和实现

子空间采样是 DREAM 算法的一个关键创新，它巧妙地解决了高维参数空间采样的效率问题。在传统的 MCMC 方法中，每次迭代都会更新所有维度的参数，这在高维问题中可能导致接受率急剧下降，使得算法效率低下。子空间采样通过每次只更新参数向量的一个子集，大大提高了算法在高维空间中的性能。

子空间采样的基本思想

子空间采样的核心思想是：在每次提出新的候选点时，不是同时更新所有维度，而是随机选择一部分维度进行更新。这种策略有几个重要优势：

  1. 提高接受率：由于只有部分维度发生变化，候选点与当前点的差异通常较小，这增加了被接受的概率。在高维空间中，这一特性尤为重要，因为它有助于链在参数空间中更流畅地移动。

  2. 更有效的参数空间探索：通过在不同迭代中关注不同的参数子集，算法能够更灵活地探索复杂的参数空间。这种方法允许算法在保持某些参数固定的情况下探索其他参数，有助于发现参数间的复杂相互作用。

  3. 适应参数间的相关性：在许多实际问题中，不同参数之间可能存在复杂的相关性。子空间采样允许算法捕捉这些条件依赖关系，因为它可以在固定某些参数的同时探索其他参数。

子空间采样的实现细节

在 DREAM 算法中，子空间采样的实现涉及以下几个关键步骤：

  1. 维度选择：对于 $d$ 维参数向量，算法首先要决定在本次迭代中更新哪些维度。这通常通过引入一个二元向量来实现，其中 $1$ 表示该维度将被更新，$0$ 表示保持不变。

  2. 概率控制： 维度的选择不是完全随机的，而是受交叉概率 $CR$ 控制。对于每个维度，算法生成一个 $[0,1]$ 之间的随机数。如果这个随机数小于 $CR$，则选择更新该维度。

  3. 差分进化操作： 对于被选中更新的维度，算法使用差分进化的变异策略生成新的候选值。具体来说，它从其他链中随机选择几对状态，计算它们之间的差值，并将这个差值添加到当前链的相应维度上。

  4. 维度锁定： 为确保至少有一个维度被更新，算法会随机选择一个维度并强制更新，即使该维度对应的随机数大于 $CR$。

这个过程可以用以下数学表达式来描述：

设 $x_t$ 为当前状态，$x^*$ 为候选状态，则子空间采样可表示为：

$$ x_i^* = \begin{cases} x_{t,i} + \Delta E_i, & \text{if } r_i < CR \text{ or } i = j \\ x_{t,i}, & \text{otherwise} \end{cases} $$

其中，$i$ 表示维度索引，$r_i$ 是 $[0,1]$ 之间的随机数，$j$ 是随机选择的强制更新维度，$\Delta E_i$ 是通过差分进化计算的更新量。

子空间采样的这种实现方式不仅简单高效，而且保留了 DREAM 算法的核心特性——差分进化策略。它允许算法在高维空间中进行有效探索，同时通过控制更新维度的数量来维持较高的接受率。这种平衡对于算法在复杂问题中的表现至关重要。

子空间采样如何提高效率

想象一个复杂的地形，我们试图在其中找到最高点。传统方法相当于每次都尝试在所有方向上同时移动，这在高维空间中极易迷失方向。相比之下，子空间采样就像是每次只选择几个方向进行探索，这不仅降低了每步决策的复杂度，还能更灵活地适应地形的局部特征。

子空间采样的一个显著优势是提高了候选点的接受率。在高维问题中，全维度更新常常导致候选点与当前点相差甚远，降低了被接受的概率。子空间采样通过限制每次更新的维度数，使得候选点与当前点的差异控制在较小范围内。这就像是在复杂地形中采取小步快走的策略，既能保持移动的灵活性，又不会因为大幅跳跃而频繁跌入低谷。

此外，子空间采样为算法提供了一种自然的方式来平衡全局探索和局部精细化。在参数空间的不同区域，算法可能需要采取不同的策略。例如，在平坦区域，大尺度的探索可能更有效；而在峰值附近，小幅度的精细调整则更为重要。子空间采样通过动态选择更新的维度和数量，使算法能够自适应地在这两种行为之间切换。

子空间采样还特别适合处理具有不同尺度和敏感性的参数。在许多实际问题中，不同参数对模型输出的影响程度可能相差甚远。子空间采样允许算法更频繁地更新那些敏感的、影响较大的参数，同时减少对不太重要参数的无谓调整。这种有选择性的更新策略不仅提高了计算效率，还有助于算法更快地捕捉到问题的本质特征。

值得注意的是，子空间采样的效果与交叉概率（CR）的设置密切相关。适当的 CR 值能够使子空间采样发挥最大效用。例如，在处理高度非线性问题时，较小的 CR 值可能更有利，因为它允许算法进行更细致的局部探索。反之，在参数间相关性较强的问题中，较大的 CR 值可能更有助于捕捉参数间的复杂依赖关系。

总的来说，子空间采样通过在高维探索和计算效率之间取得平衡，显著提升了 DREAM 算法的整体性能。它不仅使算法能够有效应对维数灾难，还为处理各种复杂问题提供了灵活而强大的工具。

交叉概率的作用和设置

交叉概率（Crossover Rate，CR）是 DREAM 算法中另一个至关重要的组件，它与子空间采样紧密相连，直接影响算法的性能和行为。理解 CR 的作用和如何正确设置它，对于充分发挥 DREAM 算法的潜力至关重要。

CR 的基本概念

$CR$ 是一个介于 $0$ 和 $1$ 之间的值，它在每次迭代中用于决定参数向量的每个维度是否应该被更新。具体来说：

  • 对于参数向量的每个维度，算法生成一个 $[0,1]$ 之间的随机数。
  • 如果这个随机数小于 $CR$，则该维度会被选中进行更新。
  • 如果随机数大于或等于 $CR$，则该维度在本次迭代中保持不变。

数学表达式： $$ x_i^* = \begin{cases} x_i^t + \Delta E_i, & \text{if } r_i < CR \text{ or } i = j \\ x_i^t, & \text{otherwise} \end{cases} $$ 其中，$x_i^*$ 是新候选点的第 $i$ 个维度，$x_i^t$ 是当前点的第 $i$ 个维度，$r_i$ 是 $[0,1]$ 间的随机数，$j$ 是随机选择的至少更新一个的维度。

CR 对算法性能的影响

CR 的选择对 DREAM 算法的性能有着多方面的影响：

  1. 更新维度的数量： CR 直接控制了每次迭代中平均被更新的维度数量。较大的 CR 值意味着更多的维度会被同时更新，这使得算法的行为更接近传统的全维度 MCMC 方法。较小的 CR 值则意味着每次只有少数维度被更新，这更符合子空间采样的初衷。
  2. 接受率的影响： CR 值的选择会显著影响候选点的接受率。较小的 CR 通常会导致较高的接受率，因为每次只有少量维度发生变化，候选点与当前点的差异较小。相反，较大的 CR 可能导致接受率降低，特别是在高维问题中。
  3. 参数空间的探索效率： 较小的 CR 值有利于算法在局部区域进行精细探索，因为每次只小幅调整少数参数。较大的 CR 值则有助于算法进行更广泛的全局探索，因为它允许在多个维度上同时进行大幅度调整。
  4. 对参数相关性的适应： 在具有强相关性的参数空间中，适当的 CR 设置可以帮助算法更好地捕捉参数间的依赖关系。例如，如果某些参数高度相关，较大的 CR 值可能更有利，因为它允许这些相关参数同时更新。
  5. 算法的收敛速度： CR 的选择会影响算法的收敛速度。过小的 CR 可能导致算法收敛缓慢，因为需要更多的迭代才能充分探索整个参数空间。过大的 CR 则可能导致算法在高维空间中迷失，难以找到好的解。

CR 的最优设置

确定 $CR$ 的最优值是一个复杂的问题，因为最佳的 $CR$ 值通常依赖于具体问题的特征，如问题的维度、参数的相关性、目标函数的景观等。以下是一些设置 $CR$ 的指导原则：

  1. 维度相关性： 经验表明，$CR$ 的最优值与问题的维度 $d$ 有关。一个常用的经验公式是：$CR = 1 - (1/d)$ 这意味着平均每次会更新一个维度。这个设置在许多情况下表现良好，特别是在处理中等维度的问题时。
  2. 自适应策略： 鉴于 $CR$ 的最优值难以预先确定，DREAM 算法引入了自适应 $CR$ 策略。算法维护一组不同的 $CR$ 值，并根据它们产生的采样效果动态调整使用概率。这种方法允许算法在运行过程中自动找到最合适的 $CR$ 值。
  3. 问题特征考虑： 对于特定类型的问题，可能需要根据问题的特征调整 $CR$ 策略。例如，在处理高度非线性或多模态问题时，可能需要使用较小的 $CR$ 值来提高局部探索能力。
  4. 与其他参数的交互： $CR$ 的设置还需要考虑 DREAM 算法中其他参数的影响，如差分进化的缩放因子。这些参数之间的相互作用会共同影响算法的性能。

实现 CR 的自适应机制

DREAM 算法的一个重要创新是引入了CR的自适应机制。这种机制允许算法在运行过程中自动调整 $CR$ 值，以适应问题的特征和当前的采样状态。自适应 CR 的基本思想是：

  1. 多 $CR$ 值池： 算法维护一组预定义的 $CR$ 值，通常覆盖从接近 $0$ 到接近 $1$ 的范围。
  2. 性能评估： 对于每个 $CR$ 值，算法记录使用该 $CR$ 值生成的候选点的性能。性能可以通过多种指标衡量，如接受率、目标函数改善程度、或者链的跳跃距离。
  3. 概率更新： 根据各个 $CR$ 值的性能，算法定期更新选择每个 $CR$ 值的概率。表现较好的 $CR$ 值会获得更高的选择概率。
  4. 动态选择： 在每次迭代中，算法根据更新后的概率分布随机选择一个 $CR$ 值使用。

这种自适应机制使得 DREAM 算法能够在不同阶段和问题的不同区域使用最合适的 $CR$ 值。例如，在早期阶段，算法可能倾向于使用较大的 $CR$ 值来快速探索参数空间，而在后期则可能更多地使用较小的 $CR$ 值来进行精细搜索。

通过这种方式，DREAM 算法能够在全局探索和局部精细化之间取得平衡，从而在各种复杂问题中表现出色。理解和正确设置 $CR$，或实现有效的 $CR$ 自适应机制，是充分发挥 DREAM 算法潜力的关键。

下一步：候选人，你被“接受”了吗？

本文深入探讨了 DREAM 算法的两个核心创新：子空间采样和交叉概率。我们详细分析了这两个组件如何协同工作，有效解决高维参数空间中的采样难题。子空间采样通过智能地选择更新的维度子集，显著提高了算法在复杂问题中的探索效率。而 CR 作为一个关键参数，不仅控制了采样的粒度，还为算法提供了在全局探索和局部精细化之间动态平衡的能力。

然而，DREAM 算法的创新性远不止于此。在接下来的文章中，我们将聚焦于算法的另一个关键环节：候选点的生成与接受机制。这个过程涉及差分进化策略在采样中的巧妙应用，以及如何通过精心设计的接受准则来保证样本的代表性和链的收敛性。我们将详细探讨这些机制如何在保持链的稳定性的同时，促进对高概率区域的有效探索。

参考文献

  1. Vrugt, J. A., Ter Braak, C. J. F., Diks, C. G. H., Robinson, B. A., Hyman, J. M., & Higdon, D. (2009). Accelerating Markov chain Monte Carlo simulation by differential evolution with self-adaptive randomized subspace sampling. International Journal of Nonlinear Sciences and Numerical Simulation, 10(3), 273-290.

  2. Ter Braak, C. J. F., & Vrugt, J. A. (2008). Differential Evolution Markov Chain with snooker updater and fewer chains. Statistics and Computing, 18(4), 435-446.

  3. Laloy, E., & Vrugt, J. A. (2012). High‐dimensional posterior exploration of hydrologic models using multiple‐try DREAM (ZS) and high‐performance computing. Water Resources Research, 48(1).

  4. Vrugt, J. A. (2016). Markov chain Monte Carlo simulation using the DREAM software package: Theory, concepts, and MATLAB implementation. Environmental Modelling & Software, 75, 273-316.

  5. Gelman, A., & Rubin, D. B. (1992). Inference from iterative simulation using multiple sequences. Statistical Science, 7(4), 457-472.

  6. Roberts, G. O., & Rosenthal, J. S. (2001). Optimal scaling for various Metropolis-Hastings algorithms. Statistical Science, 16(4), 351-367.

  7. Haario, H., Saksman, E., & Tamminen, J. (2001). An adaptive Metropolis algorithm. Bernoulli, 7(2), 223-242.

  8. Brooks, S. P., & Gelman, A. (1998). General methods for monitoring convergence of iterative simulations. Journal of Computational and Graphical Statistics, 7(4), 434-455.

  9. Andrieu, C., & Thoms, J. (2008). A tutorial on adaptive MCMC. Statistics and Computing, 18(4), 343-373.

  10. Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341-359.

差分进化自适应 Metropolis 算法的诞生：优化与采样的融合DREAM 算法的候选点生成与接受机制