准蒙特卡罗子模块 (scipy.stats.qmc)#
此模块提供准蒙特卡罗生成器及相关辅助函数。
准蒙特卡罗#
引擎#
|
一个通用的准蒙特卡罗采样器类，用于子类化。 |
|
用于生成（打乱的）Sobol序列的引擎。 |
|
Halton 序列。 |
|
拉丁超立方采样 (LHS)。 |
|
泊松盘采样。 |
|
从多项分布中进行QMC采样。 |
|
从多元正态分布 \(N(\mu, \Sigma)\) 进行QMC采样。 |
辅助工具#
|
给定样本的差异。 |
|
基于几何属性的给定样本的差异。 |
|
用新样本更新中心差异。 |
|
从单位超立方体到不同边界的样本缩放。 |
准蒙特卡罗方法简介#
准蒙特卡罗 (QMC) 方法 [1], [2], [3] 提供了一个 \(n imes d\) 的数组，数组中的数在 \([0,1]\) 范围内。它们可以用来替代来自 \(U[0,1]^{d}\) 分布的 \(n\) 个点。与随机点相比，QMC 点的设计目的是减少间隙和聚集。这一点通过差异度量 [4] 来量化。根据 Koksma-Hlawka 不等式 [5]，我们知道低差异减少了积分误差的界限。对于行为良好的函数 [2]，在 \(n\) 个 QMC 点上平均函数 \(f\) 可以实现接近 \(O(n^{-1})\) 的积分误差。
大多数 QMC 构造是为 \(n\) 的特殊值设计的，例如 2 的幂或大素数。即使将样本大小改变一个，也可能降低它们的性能，甚至它们的收敛速度 [6]。例如，如果方法是为 \(n=2^m\) 设计的，那么 \(n=100\) 点可能比 \(n=64\) 提供更低的精度。
一些 QMC 构造在 \(n\) 上是可扩展的：我们可以找到另一个特殊的样本大小 \(n' > n\)，并且通常是一个递增的特殊样本大小的无限序列。一些 QMC 构造在 \(d\) 上是可扩展的：我们可以增加维度，可能达到某个上限，并且通常不需要 \(d\) 的特殊值。一些 QMC 方法在 \(n\) 和 \(d\) 上都是可扩展的。
QMC 点是确定性的。这使得很难估计通过 QMC 点平均值估计的积分的准确性。随机化 QMC (RQMC) [7] 点被构造为每个点单独是 \(U[0,1]^{d}\)，而集体上 \(n\) 个点保留其低差异性。可以制作 \(R\) 个独立的 RQMC 点副本，以查看计算的稳定性。从 \(R\) 个独立值中，t 检验（或 bootstrap t 检验 [8]）然后给出均值的近似置信区间。一些 RQMC 方法产生的均方根误差实际上是 \(o(1/n)\)，并且小于未随机化 QMC 中看到的速率。直观的解释是，误差是许多小误差的总和，随机误差以一种确定性误差不会的方式相互抵消。RQMC 在积分函数是奇异的或由于其他原因无法黎曼可积的情况下也有优势。
(R)QMC 无法击败 Bahkvalov 的维度诅咒（参见 [9]）。对于任何随机或确定性方法，都存在在高维度下性能不佳的最坏情况函数。QMC 的最坏情况函数可能在所有 n 个点上为 0，但在其他地方非常大。最坏情况分析在高维度下变得非常悲观。(R)QMC 在使用非最坏情况函数时，相比 MC 可以带来巨大的改进。例如，(R)QMC 在积分函数可以被一些输入变量的少量函数的和很好地近似时，特别有效 [10]，[11]。这一特性通常是关于这些函数的惊人发现。
此外，为了在独立同分布（IID）蒙特卡罗方法上有所改进，（R）QMC要求被积函数具有一定的平滑性，大致上每个方向的混合一阶偏导数，即 \(\partial^d f/\partial x_1 \cdots \partial x_d\)，必须是可积的。例如，在超球体内为1而在其外为0的函数，在任何维度 \(d = 2\) 下，根据哈代和克劳斯的定义，其变差是无限的。
混沌网络是一种具有一些有价值鲁棒性特性的RQMC [12]。如果被积函数是平方可积的，它们给出的方差为 \(var_{SNET} = o(1/n)\)。对于每个平方可积的被积函数，\(var_{SNET} / var_{MC}\) 有一个有限的共同上限。当 \(p>1\) 时，混沌网络满足 \(L^p\) 中 \(f\) 的强大数定律。在某些特殊情况下，存在中心极限定理 [13]。对于足够光滑的被积函数，它们可以达到接近 \(O(n^{-3})\) 的RMSE。关于这些特性的参考文献，请参见 [12]。
QMC方法的主要类型是格规则 [14] 和数字网及序列 [2], [15]。这些理论在多项式格规则 [16] 中相遇，后者可以生成数字网。格规则需要某种形式的搜索以获得良好的构造。对于数字网，有广泛使用的默认构造。
最广泛使用的 QMC 方法是 Sobol’ 序列 [17]。这些是数字网。它们在 \(n\) 和 \(d\) 方面都是可扩展的。它们可以被扰乱。特殊的样本大小是 2 的幂。另一种流行的方法是 Halton 序列 [18]。它们的构造类似于数字网。较早的维度比后面的维度具有更好的均匀分布特性。基本上没有特殊的样本大小。它们不被认为像 Sobol’ 序列那样准确。它们可以被扰乱。Faure 的网 [19] 也被广泛使用。所有维度都同样好，但特殊的样本大小随着维度 \(d\) 的增长而迅速增加。它们可以被扰乱。Niederreiter 和 Xing 的网 [20] 具有最好的渐近性质，但在经验性能上并未表现出良好效果 [21]。
高阶数字网是通过构造点数字的数字交错过程形成的。在 \(f\) 上给出更高的平滑条件时，它们可以达到更高的渐近精度，并且可以进行混洗 [22]。目前几乎没有或没有实证工作显示可以达到的改进率。
使用QMC就像使用一个小随机数生成器的整个周期。构造是相似的，因此计算成本也是相似的 [23]。
(R)QMC 有时在使用前通过面包师变换（帐篷函数）处理点来改进。该函数的形式为 \(1-2|x-1/2|\)。当 \(x\) 从 0 到 1 时，该函数从 0 到 1 再回到 0。这对于生成晶格规则的周期函数非常有用 [14]，有时它还能提高收敛速度 [24]。
将准蒙特卡罗（QMC）方法应用于马尔可夫链蒙特卡罗（MCMC）并非易事。我们可以将MCMC视为在非常大的 \(d\) 下使用 \([0,1]^{d}\) 中的 \(n=1\) 个点，其遍历结果对应于 \(d \to \infty\)。一个建议见 [25]，在强条件下已证明收敛速度有所提高 [26]。
回到Sobol’点：有许多版本取决于所谓的方向数。这些是搜索的结果，并且已制表。一个非常广泛使用的方向数集合来自 [27]。它在维度上可扩展到 \(d=21201\)。
引用
欧文, 阿特 B. “蒙特卡罗书籍: 准蒙特卡罗部分.” 2019.
Dick, Josef, Frances Y. Kuo, 和 Ian H. Sloan. “高维积分：准蒙特卡罗方法。” Acta Numerica 第22期: 133, 2013.
Aho, A. V., C. Aistleitner, T. Anderson, K. Appel, V. Arnol’d, N. Aronszajn, D. Asotsky 等人。“W. Chen 等人（编辑），《离散理论全景》”，Sringer International Publishing, 瑞士：679, 2014。
Hickernell, Fred J. “Koksma-Hlawka 不等式。” Wiley StatsRef: 统计参考在线, 2014.
Owen, Art B. “关于丢弃第一个Sobol’点。” arXiv:2008.08051, 2020.
L’Ecuyer, Pierre, 和 Christiane Lemieux. “随机化准蒙特卡罗方法的最新进展.” 在 Modeling uncertainty 中, pp. 419-474. Springer, 纽约, NY, 2002.
DiCiccio, Thomas J., 和 Bradley Efron. “Bootstrap置信区间.” 统计科学: 189-212, 1996.
Dimov, Ivan T. 《应用于科学家的蒙特卡罗方法》. World Scientific, 2008.
Caflisch, Russel E., William J. Morokoff, 和 Art B. Owen. “使用布朗桥降低有效维度的抵押支持证券估值。”《计算金融杂志》：第1期 27-46, 1997.
Sloan, Ian H., 和 Henryk Wozniakowski. “何时准蒙特卡罗算法对高维积分有效？” 《复杂性杂志》14, 第1期 (1998): 1-33.
Loh, Wei-Liem. “关于扰动网积分的渐近分布。” 《统计年鉴》31, 第4期: 1282-1324, 2003.
Dick, Josef, 和 Friedrich Pillichshammer. 《数字网与序列：差异理论与准蒙特卡罗积分》. 剑桥大学出版社, 2010.
Dick, Josef, F. Kuo, Friedrich Pillichshammer, 和 I. Sloan. “用于多元积分的多项式格规则的构造算法.” 计算数学 74, 第252期: 1895-1921, 2005.
Sobol’, Il’ya Meerovich. “关于立方体中点的分布及积分的近似求值。” 计算数学与数学物理杂志 7, 第4期: 784-802, 1967.
Halton, John H. “关于在评估多维积分中使用某些准随机点序列的效率。” Numerische Mathematik 2, 第1期: 84-90, 1960.
Faure, Henri. “与一个数系相关的序列差异（在s维中）。” 《Acta arithmetica》 41, 第4期: 337-351, 1982.
Niederreiter, Harold, 和 Chaoping Xing. “低差异序列和具有许多有理点的全局函数域.” 有限域及其应用 2, 第3期: 241-273, 1996.
Hong, Hee Sun, 和 Fred J. Hickernell. “算法 823: 实现混洗数字序列.” ACM 数学软件交易 (TOMS) 29, 第2期: 95-109, 2003.
Dick, Josef. “高阶混洗数字网实现了平滑被积函数的最优均方根误差率。”《统计年鉴》39, 第3期: 1372-1398, 2011.
Niederreiter, Harald. “使用伪随机数的多维数值积分。” 在 Stochastic Programming 84 第一部分，第 17-38 页。Springer, 柏林, 海德堡, 1986 年。
Hickernell, Fred J. “获得 O (N-2+e) 收敛的格点求积规则。” 见 Monte Carlo 和准 Monte Carlo 方法 2000，第 274-289 页。Springer, 柏林, 海德堡, 2002。
Owen, Art B., 和 Seth D. Tribble. “一种准蒙特卡罗 Metropolis 算法.” 《美国国家科学院院刊》 102, 第25期: 8844-8849, 2005.
Chen, Su. “马尔可夫链准蒙特卡罗的一致性和收敛速度及其示例。” 博士论文，斯坦福大学，2011年。
Joe, Stephen, 和 Frances Y. Kuo. “构建具有更好二维投影的Sobol序列.” SIAM Journal on Scientific Computing 30, no. 5: 2635-2654, 2008.