拟蒙特卡罗子模块 (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] 我们知道，低差异减少了积分误差的界限。对于行为良好的函数，在 \(n\) 个 QMC 点上对函数 \(f\) 求平均可以实现接近 \(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 检验（或自举 t 检验 [8]）可以对平均值给出近似的置信区间。一些 RQMC 方法产生的均方根误差实际上是 \(o(1/n)\)，并且小于在非随机化 QMC 中看到的速率。直观的解释是，误差是许多小误差的总和，并且随机误差以确定性误差不会的方式相互抵消。RQMC 在奇异的被积函数上也有优势，或者由于其他原因，这些被积函数不能黎曼可积。
(R)QMC 无法克服巴赫瓦洛夫维度诅咒（参见 [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\) 上，根据哈代和克劳斯定义，都具有无限变差。
加扰网是一种 RQMC，具有一些有价值的鲁棒性特性 [12]。如果被积函数是平方可积的，那么它们会得到方差 \(var_{SNET} = o(1/n)\)。对于每个平方可积被积函数，\(var_{SNET} / var_{MC}\) 都有一个有限的上界。加扰网满足 \(L^p\) 中的 \(f\) 的强数律，其中 \(p>1\)。在某些特殊情况下，存在中心极限定理 [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. “Monte Carlo Book: the Quasi-Monte Carlo parts.” 2019.
Niederreiter, Harald. “Random number generation and quasi-Monte Carlo methods.” Society for Industrial and Applied Mathematics, 1992.
Dick, Josef, Frances Y. Kuo, and Ian H. Sloan. “High-dimensional integration: the quasi-Monte Carlo way.” Acta Numerica no. 22: 133, 2013.
Aho, A. V., C. Aistleitner, T. Anderson, K. Appel, V. Arnol’d, N. Aronszajn, D. Asotsky et al. “W. Chen et al.(eds.), “A Panorama of Discrepancy Theory”, Sringer International Publishing, Switzerland: 679, 2014.
Hickernell, Fred J. “Koksma-Hlawka Inequality.” Wiley StatsRef: Statistics Reference Online, 2014.
Owen, Art B. “On dropping the first Sobol’ point.” arXiv:2008.08051, 2020.
L’Ecuyer, Pierre, and Christiane Lemieux. “Recent advances in randomized quasi-Monte Carlo methods.” In Modeling uncertainty, pp. 419-474. Springer, New York, NY, 2002.
DiCiccio, Thomas J., and Bradley Efron. “Bootstrap confidence intervals.” Statistical science: 189-212, 1996.
Dimov, Ivan T. “Monte Carlo methods for applied scientists.” World Scientific, 2008.
Caflisch, Russel E., William J. Morokoff, and Art B. Owen. “Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension.” Journal of Computational Finance: no. 1 27-46, 1997.
Sloan, Ian H., and Henryk Wozniakowski. “When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?.” Journal of Complexity 14, no. 1 (1998): 1-33.
Owen, Art B., and Daniel Rudolf, “A strong law of large numbers for scrambled net integration.” SIAM Review, to appear.
Loh, Wei-Liem. “On the asymptotic distribution of scrambled net quadrature.” The Annals of Statistics 31, no. 4: 1282-1324, 2003.
Sloan, Ian H. and S. Joe. “Lattice methods for multiple integration.” Oxford University Press, 1994.
Dick, Josef, and Friedrich Pillichshammer. “Digital nets and sequences: discrepancy theory and quasi-Monte Carlo integration.” Cambridge University Press, 2010.
Dick, Josef, F. Kuo, Friedrich Pillichshammer, and I. Sloan. “Construction algorithms for polynomial lattice rules for multivariate integration.” Mathematics of computation 74, no. 252: 1895-1921, 2005.
Sobol’, Il’ya Meerovich. “On the distribution of points in a cube and the approximate evaluation of integrals.” Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 7, no. 4: 784-802, 1967.
Halton, John H. “On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals.” Numerische Mathematik 2, no. 1: 84-90, 1960.
Faure, Henri. “Discrepance de suites associees a un systeme de numeration (en dimension s).” Acta arithmetica 41, no. 4: 337-351, 1982.
Niederreiter, Harold, and Chaoping Xing. “Low-discrepancy sequences and global function fields with many rational places.” Finite Fields and their applications 2, no. 3: 241-273, 1996.
Hong, Hee Sun, and Fred J. Hickernell. “Algorithm 823: Implementing scrambled digital sequences.” ACM Transactions on Mathematical Software (TOMS) 29, no. 2: 95-109, 2003.
Dick, Josef. “Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands.” The Annals of Statistics 39, no. 3: 1372-1398, 2011.
Niederreiter, Harald. “Multidimensional numerical integration using pseudorandom numbers.” In Stochastic Programming 84 Part I, pp. 17-38. Springer, Berlin, Heidelberg, 1986.
Hickernell, Fred J. “Obtaining O (N-2+e) Convergence for Lattice Quadrature Rules.” In Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 274-289. Springer, Berlin, Heidelberg, 2002.
Owen, Art B., and Seth D. Tribble. “A quasi-Monte Carlo Metropolis algorithm.” Proceedings of the National Academy of Sciences 102, no. 25: 8844-8849, 2005.
Chen, Su. “Consistency and convergence rate of Markov chain quasi Monte Carlo with examples.” PhD diss., Stanford University, 2011.
Joe, Stephen, and Frances Y. Kuo. “Constructing Sobol sequences with better two-dimensional projections.” SIAM Journal on Scientific Computing 30, no. 5: 2635-2654, 2008.