准蒙特卡洛子模块 (scipy.stats.qmc)#
此模块提供准蒙特卡洛生成器和相关的辅助函数。
准蒙特卡洛#
引擎#
|
一个通用的准蒙特卡洛采样器类，用于子类化。 |
|
用于生成（加扰的）Sobol'序列的引擎。 |
|
Halton 序列。 |
|
拉丁超立方抽样 (LHS)。 |
|
泊松盘采样。 |
|
从多项分布进行 QMC 采样。 |
|
从多元正态分布 \(N(\mu, \Sigma)\) 进行 QMC 采样。 |
辅助函数#
|
给定样本的差异度。 |
|
基于给定样本的几何属性的差异度。 |
|
使用新样本更新中心差异度。 |
|
将样本从单位超立方缩放到不同的边界。 |
准蒙特卡洛简介#
准蒙特卡洛 (QMC) 方法 [1], [2], [3] 提供 \(n \times d\) 个在 \([0,1]\) 中的数字数组。它们可以用来代替 \(U[0,1]^{d}\) 分布中的 \(n\) 个点。与随机点相比，QMC 点旨在减少间隙和聚集。这可以通过差异度量来量化 [4]。从 Koksma-Hlawka 不等式 [5]，我们知道低差异度会减少积分误差的界限。对函数 \(f\) 在 \(n\) 个 QMC 点上取平均值，对于表现良好的函数，可以实现接近 \(O(n^{-1})\) 的积分误差 [2]。
大多数 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\) 个点共同保留其低差异度。我们可以对 RQMC 点进行 \(R\) 个独立的复制，以查看计算的稳定性。从 \(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 MC 更好的效果，(R)QMC 需要积分函数具有一定的平滑度，大致在每个方向上的混合一阶导数 \(\partial^d f/\partial x_1 \cdots \partial x_d\) 必须是可积分的。例如，对于任何维度 \(d = 2\)，在超球体内部为 1 而在超球体外部为 0 的函数，在 Hardy 和 Krause 的意义上具有无限变化。
加扰网格是一种具有一些有价值的鲁棒性属性的 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，然后返回。它对于为格子规则生成周期函数非常有用 [14]，有时它会提高收敛速度 [24]。
将 QMC 方法应用于马尔可夫链蒙特卡洛 (MCMC) 并非易事。我们可以将 MCMC 视为在 \([0,1]^{d}\) 中使用 \(n=1\) 个点，用于非常大的 \(d\)，其中遍历结果对应于 \(d \to \infty\)。 [25] 中提出了一个方案，并且在严格的条件下，已经显示出改进的收敛速度 [26]。
回到 Sobol’ 点：有许多版本取决于所谓的方向数。这些是搜索的结果并以表格形式列出。一套非常广泛使用的方向数来自 [27]。它在维度上可扩展至 \(d=21201\)。
参考文献#
Owen, Art 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 国际出版社，瑞士：679，2014。”
Hickernell, Fred J.“Koksma-Hlawka 不等式。”Wiley StatsRef：在线统计参考，2014。
Owen, Art B.“关于删除第一个 Sobol’ 点。”arXiv:2008.08051，2020。
L'Ecuyer, Pierre 和 Christiane Lemieux。“随机化准蒙特卡洛方法的最新进展。” 在不确定性建模中，第 419-474 页。Springer，纽约，纽约，2002。
DiCiccio, Thomas J. 和 Bradley Efron。“自举置信区间。”统计科学：189-212，1996。
Dimov, Ivan T. “应用科学家的蒙特卡洛方法。”世界科学，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.“在评估多维积分中某些准随机点序列的效率。”《数值数学》第 2 卷，第 1 期：84-90，1960。
Faure, Henri。“Discrepance de suites associees a un systeme de numeration (en dimension 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。“使用伪随机数的多维数值积分。”在随机规划 84 第一部分中，第 17-38 页。Springer，柏林，海德堡，1986。
Hickernell, Fred J.“获得格子求积规则的 O (N-2+e) 收敛性。”在 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 科学计算杂志》第 30 卷，第 5 期：2635-2654，2008。