Подмодуль квази-Монте-Карло (scipy.stats.qmc)#
Этот модуль предоставляет генераторы квази-Монте-Карло и связанные вспомогательные функции.
Квази-Монте-Карло#
Движки#
|
Универсальный класс квази-Монте-Карло сэмплера, предназначенный для наследования. |
|
Движок для генерации (скремблированных) последовательностей Соболя. |
|
Последовательность Халтона. |
|
Латинский гиперкубический сэмплинг (LHS). |
|
Дискретизация Пуассона. |
|
QMC выборка из мультиномиального распределения. |
|
QMC выборка из многомерного нормального распределения \(N(\mu, \Sigma)\). |
Вспомогательные функции#
|
Несогласованность заданной выборки. |
|
Несогласованность заданной выборки на основе её геометрических свойств. |
|
Обновить центрированное расхождение с новым образцом. |
|
Масштабирование выборки из единичного гиперкуба к различным границам. |
Введение в квази-Монте-Карло методы#
Методы квази-Монте-Карло (QMC) [1], [2], [3] предоставить \(n \times d\) массив чисел в \([0,1]\). Они могут использоваться вместо \(n\) точки из \(U[0,1]^{d}\) распределение. По сравнению со случайными точками, точки QMC спроектированы так, чтобы иметь меньше пробелов и скоплений. Это количественно оценивается мерами несоответствия [4]. Из неравенства Коксмы-Хлавки [5] мы знаем, что низкая дисперсия уменьшает границу погрешности интегрирования. Усреднение функции \(f\) над \(n\) Точки QMC могут достичь ошибки интегрирования близкой к \(O(n^{-1})\) для хорошо обусловленных функций [2].
Большинство конструкций QMC предназначены для специальных значений \(n\) такие как степени двойки или большие простые числа. Изменение размера выборки даже на единицу может ухудшить их производительность, даже их скорость сходимости [6]. Например \(n=100\) точки могут давать меньшую точность, чем \(n=64\) если метод был разработан для \(n=2^m\).
Некоторые конструкции 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 также имеет преимущества для подынтегральных функций, которые являются сингулярными или, по другим причинам, не являются интегрируемыми по Риману.
(R)QMC не может преодолеть проклятие размерности Бахвалова (см. [9]). Для любого случайного или детерминированного метода существуют наихудшие функции, которые дадут ему плохую производительность в высоких размерностях. Наихудшая функция для QMC может быть 0 во всех n точках, но очень большой в других местах. Анализы наихудшего случая становятся очень пессимистичными в высоких размерностях. (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}\) которое выполняется одновременно для каждой квадратно интегрируемой подынтегральной функции. Скремблированные сети удовлетворяют усиленному закону больших чисел для \(f\) в \(L^p\) когда \(p>1\). В некоторых особых случаях существует центральная предельная теорема [13]. Для достаточно гладких подынтегральных функций они могут достигать среднеквадратичной ошибки почти \(O(n^{-3})\). См. [12] для ссылок об этих свойствах.
Основными видами методов QMC являются правила решеток [14] и цифровые сети и последовательности [2], [15]. Теории сходятся в полиномиальных решетчатых правилах [16] которые могут генерировать цифровые сети. Для решётчатых правил требуется некоторый поиск хороших конструкций. Для цифровых сетей существуют широко используемые конструкции по умолчанию.
Наиболее широко используемые методы QMC — это последовательности Соболя [17]. Это цифровые сети. Они расширяемы в обоих \(n\) и \(d\)Они могут быть скремблированы. Специальные размеры выборок являются степенями 2. Другой популярный метод — последовательности Холтона [18]. Конструкции напоминают цифровые сети. Ранние измерения имеют гораздо лучшие свойства равномерного распределения, чем поздние. По сути, нет специальных размеров выборок. Они не считаются такими же точными, как последовательности Соболя. Их можно скремблировать. Сети Фора [19] также широко используются. Все размерности одинаково хороши, но специальные размеры выборок быстро растут с увеличением размерности \(d\). Они могут быть скремблированы. Сети Нидеррайтера и Синга [20] имеют наилучшие асимптотические свойства, но не показали хорошей эмпирической производительности [21].
Цифровые сети высшего порядка формируются процессом чередования цифр в цифрах построенных точек. Они могут достигать более высоких уровней асимптотической точности при более высоких условиях гладкости на \(f\) и они могут быть перемешаны [22]. Существует мало или совсем нет эмпирических работ, показывающих, что улучшенная скорость достигается.
Использование QMC похоже на использование всего периода небольшого генератора случайных чисел. Конструкции схожи, и поэтому вычислительные затраты также схожи [23].
(R)QMC иногда улучшается путем пропускания точек через преобразование пекаря (палаточную функцию) перед их использованием. Эта функция имеет вид \(1-2|x-1/2|\). Как \(x\) переходит от 0 к 1, эта функция переходит от 0 к 1 и обратно. Она очень полезна для создания периодической функции для решёточных правил [14], и иногда это улучшает скорость сходимости [24].
Непросто применить методы QMC к Марковским цепям Монте-Карло (MCMC). Мы можем рассматривать MCMC как использование \(n=1\) точка в \([0,1]^{d}\) для очень больших \(d\), с эргодическими результатами, соответствующими \(d \to \infty\). Одно предложение в [25] и при строгих условиях была показана улучшенная скорость сходимости [26].
Возвращаясь к точкам Соболя: существует много версий в зависимости от так называемых направляющих чисел. Они являются результатом поисков и табулированы. Очень широко используемый набор направляющих чисел происходит от [27]. Расширяем по размерности до \(d=21201\).
Ссылки#
Owen, Art B. «Monte Carlo Book: the Quasi-Monte Carlo parts.» 2019.
Нидеррайтер, Харальд. "Генерация случайных чисел и методы квази-Монте-Карло." Общество промышленной и прикладной математики, 1992.
Дик, Йозеф, Франсес Ю. Куо и Иэн Х. Слоан. «Высокоразмерное интегрирование: квази-Монте-Карло подход.» Acta Numerica № 22: 133, 2013.
Ахо, А. В., К. Айстлейтнер, Т. Андерсон, К. Аппель, В. Арнольд, Н. Аронсайн, Д. Асоцкий и др. “В. Чен и др.(ред.), “Панорама теории несоответствия”, Sringer International Publishing, Швейцария: 679, 2014.
Хикернелл, Фред Дж. «Неравенство Коксмы-Хлавки». 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.
ДиЧиччо, Томас Дж. и Брэдли Эфрон. «Доверительные интервалы бутстрепа». 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.
Слоан, Иан Х. и Хенрик Возняковски. «Когда алгоритмы квази-Монте-Карло эффективны для многомерных интегралов?». Journal of Complexity 14, № 1 (1998): 1-33.
Оуэн, Арт Б. и Даниэль Рудольф, «Сильный закон больших чисел для интегрирования с перемешанной сеткой». SIAM Review, в печати.
Loh, Wei-Liem. “On the asymptotic distribution of scrambled net quadrature.” The Annals of Statistics 31, no. 4: 1282-1324, 2003.
Слоан, Иэн Х. и С. Джо. «Методы решеток для многократного интегрирования.» Oxford University Press, 1994.
Дик, Йозеф, и Фридрих Пилихшаммер. "Цифровые сети и последовательности: теория несоответствия и квази-Монте-Карло интегрирование." Cambridge University Press, 2010.
Дик, Йозеф, Ф. Куо, Фридрих Пилихсхаммер и И. Слоан. «Алгоритмы построения полиномиальных решетчатых правил для многомерного интегрирования». Математические вычисления 74, № 252: 1895-1921, 2005.
Соболь, Илья Меерович. "О распределении точек в кубе и приближенном вычислении интегралов." Журнал вычислительной математики и математической физики 7, № 4: 784-802, 1967.
Халтон, Джон Х. «Об эффективности некоторых квазислучайных последовательностей точек при вычислении многомерных интегралов». Numerische Mathematik 2, № 1: 84-90, 1960.
Фор, Анри. «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.
Дик, Йозеф. «Высокоупорядоченные скремблированные цифровые сети достигают оптимальной скорости среднеквадратичной ошибки для гладких интеграндов». Анналы статистики 39, № 3: 1372-1398, 2011.
Нидеррайтер, Харальд. «Многомерное численное интегрирование с использованием псевдослучайных чисел». В Stochastic Programming 84 Part I, стр. 17-38. Springer, Berlin, Heidelberg, 1986.
Хикернелл, Фред Дж. «Получение сходимости O (N-2+e) для квадратурных правил решетки». В Monte Carlo and Quasi-Monte Carlo Methods 2000, стр. 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.
Чен, Су. «Согласованность и скорость сходимости метода Монте-Карло с квазислучайными цепями Маркова на примерах». Дисс. PhD, Стэнфордский университет, 2011.
Джо, Стивен и Фрэнсис Ю. Куо. «Построение последовательностей Соболя с лучшими двумерными проекциями». SIAM Journal on Scientific Computing 30, № 5: 2635-2654, 2008.