Quasi-Monte-Carlo-Untermodul (scipy.stats.qmc)#
Dieses Modul stellt Quasi-Monte-Carlo-Generatoren und zugehörige Hilfsfunktionen bereit.
Quasi-Monte-Carlo#
Engines#
|
Eine generische Quasi-Monte-Carlo-Sampler-Klasse, die für die Unterklassifizierung gedacht ist. |
|
Engine zur Erzeugung von (ver etcétera) Sobol'-Sequenzen. |
|
Halton-Sequenz. |
|
Latin-Hypercube-Sampling (LHS). |
|
Poisson-Disk-Sampling. |
|
QMC-Sampling aus einer multinomialen Verteilung. |
|
QMC-Sampling aus einer multivariaten Normalverteilung \(N(\mu, \Sigma)\). |
Hilfen#
|
Diskrepanz einer gegebenen Stichprobe. |
|
Diskrepanz einer gegebenen Stichprobe basierend auf ihren geometrischen Eigenschaften. |
|
Aktualisiert die zentrierte Diskrepanz mit einer neuen Stichprobe. |
|
Skalierung von Stichproben vom Einheits-Hyperwürfel auf verschiedene Grenzen. |
Einführung in Quasi-Monte Carlo#
Quasi-Monte-Carlo (QMC)-Methoden [1], [2], [3] liefern ein \(n \times d\)-Array von Zahlen in \([0,1]\). Sie können anstelle von \(n\) Punkten aus der Verteilung \(U[0,1]^{d}\) verwendet werden. Im Vergleich zu zufälligen Punkten sind QMC-Punkte so konzipiert, dass sie weniger Lücken und Verdichtungen aufweisen. Dies wird durch Diskrepanzmaße quantifiziert [4]. Aus der Koksma-Hlawka-Ungleichung [5] wissen wir, dass eine niedrige Diskrepanz einen Grenzwert für den Integrationsfehler reduziert. Das Mitteln einer Funktion \(f\) über \(n\) QMC-Punkte kann bei gutartigen Funktionen einen Integrationsfehler nahe \(O(n^{-1})\) erzielen [2].
Die meisten QMC-Konstruktionen sind für spezielle Werte von \(n\) wie Zweierpotenzen oder große Primzahlen konzipiert. Die Änderung der Stichprobengröße um nur eins kann ihre Leistung beeinträchtigen, sogar ihre Konvergenzrate [6]. Zum Beispiel können \(n=100\) Punkte weniger Genauigkeit liefern als \(n=64\), wenn die Methode für \(n=2^m\) konzipiert wurde.
Einige QMC-Konstruktionen sind in \(n\) erweiterbar: Wir können eine weitere spezielle Stichprobengröße \(n' > n\) und oft eine unendliche Folge von steigenden speziellen Stichprobengrößen finden. Einige QMC-Konstruktionen sind in \(d\) erweiterbar: Wir können die Dimension erhöhen, möglicherweise bis zu einer Obergrenze, und das normalerweise ohne spezielle Werte für \(d\) zu benötigen. Einige QMC-Methoden sind sowohl in \(n\) als auch in \(d\) erweiterbar.
QMC-Punkte sind deterministisch. Das macht es schwierig, die Genauigkeit von Integralen abzuschätzen, die durch Mittelwerte über QMC-Punkte geschätzt werden. Randomisierte QMC (RQMC) [7]-Punkte werden so konstruiert, dass jeder Punkt einzeln \(U[0,1]^{d}\) ist, während die \(n\) Punkte kollektiv ihre geringe Diskrepanz beibehalten. Man kann \(R\) unabhängige Replikationen von RQMC-Punkten erstellen, um zu sehen, wie stabil eine Berechnung ist. Aus \(R\) unabhängigen Werten ergibt ein t-Test (oder Bootstrap-t-Test [8]) ungefähre Konfidenzintervalle für den Mittelwert. Einige RQMC-Methoden liefern eine quadratische Mittelwertabweichung (root mean squared error), die tatsächlich kleiner als \(o(1/n)\) ist und kleiner als die bei nicht-randomisiertem QMC beobachtete Rate. Eine intuitive Erklärung ist, dass der Fehler eine Summe vieler kleiner Fehler ist und sich zufällige Fehler aufheben, während deterministische Fehler dies nicht tun. RQMC hat auch Vorteile bei Integranden, die singulär sind oder aus anderen Gründen nicht Riemann-integrierbar sind.
(R)QMC kann Bakvalovs Fluch der Dimension (siehe [9]) nicht überwinden. Für jede zufällige oder deterministische Methode gibt es Worst-Case-Funktionen, die ihr in hohen Dimensionen eine schlechte Leistung bescheren. Eine Worst-Case-Funktion für QMC könnte an allen n Punkten 0 sein, aber überall sonst sehr groß. Worst-Case-Analysen werden in hohen Dimensionen sehr pessimistisch. (R)QMC kann eine große Verbesserung gegenüber MC erzielen, wenn die Funktionen, auf denen es angewendet wird, keine Worst-Case-Funktionen sind. Zum Beispiel kann (R)QMC besonders effektiv bei Integranden sein, die sich gut durch Summen von Funktionen von einigen wenigen ihrer Eingabevariablen gleichzeitig annähern lassen [10], [11]. Diese Eigenschaft ist oft eine überraschende Entdeckung über diese Funktionen.
Darüber hinaus erfordert (R)QMC, um eine Verbesserung gegenüber IID MC zu erzielen, eine gewisse Glattheit des Integranden. Ungefähr muss die gemischte erste Ableitung in jeder Richtung, \(\partial^d f/\partial x_1 \cdots \partial x_d\), integrierbar sein. Beispielsweise hat eine Funktion, die innerhalb der Hypersphäre 1 und außerhalb 0 ist, für jede Dimension \(d = 2\) eine unendliche Variation im Sinne von Hardy und Krause.
Verstückelte Netze sind eine Art von RQMC mit einigen wertvollen Robustheitseigenschaften [12]. Wenn der Integrand quadratisch integrierbar ist, erzielen sie eine Varianz von \(var_{SNET} = o(1/n)\). Es gibt eine endliche Obergrenze für \(var_{SNET} / var_{MC}\), die gleichzeitig für jeden quadratisch integrierbaren Integranden gilt. Verstümmelte Netze erfüllen ein starkes Gesetz der großen Zahlen für \(f\) in \(L^p\) für \(p>1\). In einigen Spezialfällen gibt es einen zentralen Grenzwertsatz [13]. Für ausreichend glatte Integranden können sie eine RMSE von fast \(O(n^{-3})\) erzielen. Siehe [12] für Referenzen zu diesen Eigenschaften.
Die Hauptarten von QMC-Methoden sind Gitterregeln [14] und digitale Netze und Sequenzen [2], [15]. Die Theorien treffen sich in polynomialen Gitterregeln [16], die digitale Netze erzeugen können. Gitterregeln erfordern eine Art von Suche nach guten Konstruktionen. Für digitale Netze gibt es weit verbreitete Standardkonstruktionen.
Die am weitesten verbreiteten QMC-Methoden sind Sobol'-Sequenzen [17]. Dies sind digitale Netze. Sie sind sowohl in \(n\) als auch in \(d\) erweiterbar. Sie können verstümmelt werden. Die speziellen Stichprobengrößen sind Zweierpotenzen. Eine weitere beliebte Methode sind Halton-Sequenzen [18]. Die Konstruktionen ähneln denen von digitalen Netzen. Die früheren Dimensionen haben deutlich bessere Gleichverteilungseigenschaften als spätere. Es gibt im Wesentlichen keine speziellen Stichprobengrößen. Sie gelten nicht als so genau wie Sobol'-Sequenzen. Sie können verstümmelt werden. Die Netze von Faure [19] werden ebenfalls häufig verwendet. Alle Dimensionen sind gleich gut, aber die speziellen Stichprobengrößen wachsen schnell mit der Dimension \(d\). Sie können verstümmelt werden. Die Netze von Niederreiter und Xing [20] haben die besten asymptotischen Eigenschaften, haben aber keine guten empirischen Leistungen gezeigt [21].
Höherwertige digitale Netze werden durch einen Ziffern-Verschachtelungsprozess in den Ziffern der konstruierten Punkte gebildet. Sie können höhere asymptotische Genauigkeiten bei höheren Glattheitsbedingungen an \(f\) erreichen und können verstümmelt werden [22]. Es gibt wenig oder keine empirische Arbeit, die zeigt, dass die verbesserte Rate erzielt wird.
Die Verwendung von QMC ist vergleichbar mit der Verwendung des gesamten Zeitraums eines kleinen Zufallszahlengenerators. Die Konstruktionen sind ähnlich und daher auch die Rechenkosten [23].
(R)QMC wird manchmal verbessert, indem die Punkte vor der Verwendung durch eine Baker-Transformation (Zeltfunktion) geleitet werden. Diese Funktion hat die Form \(1-2|x-1/2|\). Wenn \(x\) von 0 bis 1 läuft, geht diese Funktion von 0 auf 1 und dann zurück. Sie ist sehr nützlich, um eine periodische Funktion für Gitterregeln zu erzeugen [14], und manchmal verbessert sie die Konvergenzrate [24].
Es ist nicht einfach, QMC-Methoden auf Markov-Ketten-Monte-Carlo (MCMC) anzuwenden. Wir können MCMC als Verwendung eines Punktes \(n=1\) in \([0,1]^{d}\) für sehr große \(d\) betrachten, wobei ergodische Ergebnisse \(d \to \infty\) entsprechen. Ein Vorschlag findet sich in [25], und unter starken Bedingungen wurde eine verbesserte Konvergenzrate gezeigt [26].
Zurück zu Sobol'-Punkten: Es gibt viele Versionen, die von den sogenannten Richtungszahlen abhängen. Diese sind das Ergebnis von Suchen und werden tabelliert. Eine sehr weit verbreitete Sammlung von Richtungszahlen stammt aus [27]. Sie ist bis zur Dimension \(d=21201\) erweiterbar.
Referenzen#
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, und 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, und Christiane Lemieux. „Recent advances in randomized quasi-Monte Carlo methods.“ In Modeling uncertainty, pp. 419-474. Springer, New York, NY, 2002.
DiCiccio, Thomas J., und 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, und 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., und 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., und 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. und S. Joe. „Lattice methods for multiple integration.“ Oxford University Press, 1994.
Dick, Josef, und Friedrich Pillichshammer. „Digital nets and sequences: discrepancy theory and quasi-Monte Carlo integration.“ Cambridge University Press, 2010.
Dick, Josef, F. Kuo, Friedrich Pillichshammer, und 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, und 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, und 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., und 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, und Frances Y. Kuo. „Constructing Sobol sequences with better two-dimensional projections.“ SIAM Journal on Scientific Computing 30, no. 5: 2635-2654, 2008.