準蒙地卡羅子模組 (scipy.stats.qmc)#
此模組提供準蒙地卡羅生成器和相關的輔助函數。
準蒙地卡羅#
引擎#
|
一個用於子類化的通用準蒙地卡羅取樣器類別。 |
|
用於生成（擾亂）Sobol' 序列的引擎。 |
|
Halton 序列。 |
|
拉丁超立方取樣 (LHS)。 |
|
Poisson 圓盤取樣。 |
|
從多項分佈進行 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 點上取平均值，對於表現良好的函數 [2]，可以實現接近 \(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 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 視為在 \([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.