准蒙特卡洛子模块 (scipy.stats.qmc)#

此模块提供准蒙特卡洛生成器和相关的辅助函数。

准蒙特卡洛#

引擎#

QMCEngine(d, *[, optimization, rng])

一个通用的准蒙特卡洛采样器类,旨在用于子类化。

Sobol(d, *[, scramble, bits, rng, optimization])

用于生成(扰动)Sobol 序列的引擎。

Halton(d, *[, scramble, optimization, rng])

Halton 序列。

LatinHypercube(d, *[, scramble, strength, ...])

拉丁超立方体抽样 (LHS)。

PoissonDisk(d, *[, radius, hypersphere, ...])

泊松盘抽样。

MultinomialQMC(pvals, n_trials, *[, engine, rng])

来自多项式分布的 QMC 采样。

MultivariateNormalQMC(mean[, cov, cov_root, ...])

来自多元正态分布 \(N(\mu, \Sigma)\) 的 QMC 采样。

辅助函数#

discrepancy(sample, *[, iterative, method, ...])

给定样本的差异。

geometric_discrepancy(sample[, method, metric])

给定样本基于其几何特性的差异。

update_discrepancy(x_new, sample, initial_disc)

用新样本更新中心差异。

scale(sample, l_bounds, u_bounds, *[, reverse])

将样本从单位超立方体缩放到不同边界。

准蒙特卡洛介绍#

准蒙特卡洛 (QMC) 方法 [1], [2], [3] 提供一个 \(n \times 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-检验(或自助 t-检验 [8])然后给出平均值的近似置信区间。一些 RQMC 方法产生的均方根误差实际上是 \(o(1/n)\) 并且小于未随机化的 QMC 中观察到的速率。一个直观的解释是,误差是许多小误差的总和,随机误差以确定性误差无法做到的方式相互抵消。RQMC 对奇异或由于其他原因无法 Riemann 积分的被积函数也具有优势。

(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\) 必须是可积的。例如,一个在超球内部为 1 外部为 0 的函数在任何维度 \(d = 2\) 时都具有 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 视为在非常大的 \(d\) 维度中使用 \(n=1\)\([0,1]^{d}\) 区域中的点,其遍历结果对应于 \(d \to \infty\)。一个提案在 [25] 中,在强条件下已证明收敛速度有所提高 [26]

回到 Sobol' 点:根据所谓的方向数有许多版本。这些是搜索的结果并已列表化。一组被广泛使用的方向数来自 [27]。它在维度上可扩展至 \(d=21201\)

参考文献#

[1]

Owen, Art B. “蒙特卡洛书籍:准蒙特卡洛部分。” 2019。

[2] (1,2,3)

Niederreiter, Harald. “随机数生成与准蒙特卡洛方法。” 工业与应用数学学会,1992。

[3]

Dick, Josef, Frances Y. Kuo, 和 Ian H. Sloan. “高维积分:准蒙特卡洛方法。” Acta Numerica 第 22 期: 133, 2013。

[4]

Aho, A. V., C. Aistleitner, T. Anderson, K. Appel, V. Arnol’d, N. Aronszajn, D. Asotsky 等人。“W. Chen 等人(编辑),“差异理论全景”,Springer International Publishing,瑞士: 679, 2014。

[5]

Hickernell, Fred J. “Koksma-Hlawka 不等式。” Wiley StatsRef: 统计参考在线, 2014。

[6]

Owen, Art B. “关于舍弃第一个 Sobol' 点。” arXiv:2008.08051, 2020。

[7]

L’Ecuyer, Pierre, 和 Christiane Lemieux. “随机化准蒙特卡洛方法的最新进展。” 在《不确定性建模》中,第 419-474 页。Springer, 纽约,NY,2002。

[8]

DiCiccio, Thomas J., 和 Bradley Efron. “Bootstrap 置信区间。” Statistical science: 189-212, 1996。

[9]

Dimov, Ivan T. “应用科学家的蒙特卡洛方法。” World Scientific, 2008。

[10]

Caflisch, Russel E., William J. Morokoff, 和 Art B. Owen. “使用布朗桥降低有效维度的抵押贷款支持证券估值。” Journal of Computational Finance: 第 1 期 27-46, 1997。

[11]

Sloan, Ian H., 和 Henryk Wozniakowski. “准蒙特卡洛算法何时对高维积分有效?” Journal of Complexity 14, no. 1 (1998): 1-33。

[12] (1,2)

Owen, Art B., 和 Daniel Rudolf, “扰动网积分的大数强定律。” SIAM Review,待出版。

[13]

Loh, Wei-Liem. “关于扰动网积分的渐近分布。” The Annals of Statistics 31, no. 4: 1282-1324, 2003。

[14] (1,2)

Sloan, Ian H. 和 S. Joe. “多重积分的格点方法。” Oxford University Press, 1994。

[15]

Dick, Josef, 和 Friedrich Pillichshammer. “数字网和序列:差异理论与准蒙特卡洛积分。” 剑桥大学出版社, 2010。

[16]

Dick, Josef, F. Kuo, Friedrich Pillichshammer, 和 I. Sloan. “用于多元积分的多项式格点规则的构造算法。” Mathematics of computation 74, no. 252: 1895-1921, 2005。

[17]

Sobol’, Il’ya Meerovich. “关于立方体中点的分布和积分的近似评估。” Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 7, no. 4: 784-802, 1967。

[18]

Halton, John H. “关于评估多维积分中某些准随机点序列的效率。” Numerische Mathematik 2, no. 1: 84-90, 1960。

[19]

Faure, Henri. “与数字系统相关的序列的差异 (在维度 s 中)。” Acta arithmetica 41, no. 4: 337-351, 1982。

[20]

Niederreiter, Harold, 和 Chaoping Xing. “低差异序列和具有许多有理点全局函数域。” Finite Fields and their applications 2, no. 3: 241-273, 1996。

[21]

Hong, Hee Sun, 和 Fred J. Hickernell. “算法 823:实现扰动数字序列。” ACM Transactions on Mathematical Software (TOMS) 29, no. 2: 95-109, 2003。

[22]

Dick, Josef. “高阶扰动数字网对平滑被积函数达到均方根误差的最佳速率。” The Annals of Statistics 39, no. 3: 1372-1398, 2011。

[23]

Niederreiter, Harald. “使用伪随机数进行多维数值积分。” 在《随机规划 84 第一部分》中,第 17-38 页。Springer, 柏林, 海德堡, 1986。

[24]

Hickernell, Fred J. “实现格点求积规则的 O (N-2+e) 收敛。” 在《2000 年蒙特卡洛和准蒙特卡洛方法》中,第 274-289 页。Springer, 柏林, 海德堡, 2002。

[25]

Owen, Art B., 和 Seth D. Tribble. “一种准蒙特卡洛 Metropolis 算法。” Proceedings of the National Academy of Sciences 102, no. 25: 8844-8849, 2005。

[26]

Chen, Su. “马尔可夫链准蒙特卡洛的一致性和收敛速度及示例。” 博士论文,斯坦福大学,2011。

[27]

Joe, Stephen, 和 Frances Y. Kuo. “构造具有更好二维投影的 Sobol 序列。” SIAM Journal on Scientific Computing 30, no. 5: 2635-2654, 2008。