Диссертация (1150625), страница 15
Текст из файла (страница 15)
Если фиксировано, то, во-первых, для всякого ̸ .. требуется дополнительно определять положение неполного набора (например, случайновыкидывать номера индексов из промежутка от 1 до ); во-вторых, если >> , то эффективность такого расслоения крайне невелика (по сути, оно становится неотличимым отнаивного Монте-Карло).812) Если также растёт с , то должен присутствовать этап перехода от одного значения к другому, что, как правило, означает отказ от предыдущего разбиения X1 , . .
. , X и ужеимеющегося набора точек, и генерация выборки из более „мелкого“ разбиения начинаетсязаново. Это неудобно как с алгоритмической точки зрения (появляются дополнительныепараметры), так и с точки зрения эффективности.Известно некоторое количество адаптивных алгоритмов, которые достаточно успешно справляются с поставленными проблемами. Наиболее известны MISER (Пресс У., Фаррар Г.
и др.,[65], [66]) и VEGAS (Лепаж Г., [67], [68]).Другим вариантом является переход к (рандомизированному) квази-Монте-Карло, которыйавтоматически гарантирует равномерную распределённость в смысле элементарных множеств(см. определение 4). В самом деле, последовательная генерация точек (например, из последовательности Соболя) может продолжаться до тех пор, пока не будет достигнута желаемая точность,что решает обе вышеозначенные проблемы.Ещё одна важная проблема в теории методов Монте-Карло и квази-Монте-Карло – отсутствие постепенного перехода между полностью случайными и квазислучайными структурами.Как уже отмечалось ранее, различие свойств этих классов конструкций имеет принципиальноезначение.
Более того, в некоторых задачах адаптация квази-Монте-Карло либо невозможна, либозатруднительна (мы рассмотрим одну такую задачу в следующем разделе).Далее мы рассмотрим алгоритм действия предлагаемой гибридной битовой рандомизации(далее HBR), который будет нами рассмотрен в контексте нескольких численных экспериментов.
Имея в виду это обстоятельство, мы сразу будем иметь в виду стандарт IEEE 754 [69] длячисел с плавающей точкой, а именно представление чисел с плавающей точкой двойной точности (binary64). В основе такого представления лежат 64 бита памяти, размеченные следующимобразом: 1 бит задаёт знак числа (sign), 11 битов определяют его основание (), а оставшиеся 52– мантиссу ( ∈ {0,1}, = 1, . . . , 52). Таким образом, запись числа имеет вид⎛(−1)sign ⎝1 +52∑︁⎞52− 2− ⎠ × 2−1023 .(3.11)=1Идея алгоритма заключается в том, что имеющийся квазислучайный набор может быть преобразован на уровне битовой структуры (представления (3.11)) путём замены некоторых битовпредставления на случайные.
В самом деле, пусть ∈ [0, 1] имеет двоичное представлениевида = 0.1 2 . . . 52 , получаемое из (3.11) тривиальным образом. Зафиксируем некоторое количество битов, которые останутся неизменными, а остальные поменяем случайным образом:˜ = 0.1 2 . . . ˜+1 . . . ˜52 , где ˜ ∈ {0,1} (т.е. 0 или 1 с вероятностью 0.5) и для всех этислучайные величины независимы в совокупности. Тогда случай = 0 соответствует, по сути,обычному Монте-Карло, = 52 сохраняет исходную квази-Монте-Карло последовательностьнетронутой, а все промежуточные значения обеспечат постепенный переход между этими двумя82структурами. Далее под обозначением () мы будем подразумевать действие такой процедуры с параметром .С точки зрения теории вероятностей, работа со случайными вещественными числами и ихконечными двоичными представлениями может быть описана в терминах дискретного вероятностного пространства.
Так, пусть под запись двоичного представления числа ∈ [0, 1] отведено бит (в практических вычислениях мы будем использовать случай = 52). Тогда естественнорассматривать вероятностное пространство Ω = {0.1 2 . . . , ∈ {0,1}}, где каждому из элементов соответствует одинаковая вероятность: ∀ ∈ Ω () =1.2Поэтому когда в контекстекомпьютерных вычислений говорят о моделировании случайной величины, равномерно распределённой на отрезке [0, 1], имеют в виду пространство (Ω, ).Теперь, пусть мы имеем фиксированный элемент этого пространства = 0.1 2 . . . .
Предлагаемая процедура смены − последних битов на случайные описывается как получениедругого элемента того же пространства ˜ = 0.1 2 . . . ˜+1 . . . ˜ , где, как уже упоминалось,˜ ∈ {0,1}. Докажем ряд утверждений о свойствах ˜.Утверждение 2. Если = (меняются все имеющиеся биты разложения), то ˜ есть случайнаявеличина, равномерно распределённая на множестве Ω.Доказательство. Каждый из новых битов представляет собой случайную величину, независимую от других битов и принимающую значения 0 или 1 с равной вероятностью. Очевидно, что свероятностью 1 выполнено ˜ ∈ Ω. Если рассмотреть произвольный элемент = 0.1 2 .
. . ∈ Ω,то (˜ = ) = (˜1 = 1 , . . . , ˜ = ) = (˜1 = 1 ) · . . . · (˜ = ) =1.2(3.12)Утверждение 3. Для произвольного < ˜ есть случайная величина, равномерно распределённая на множестве Ω = {0.1 2 . . . +1 . . . , ∈ {0,1}}.Доказательство.
Доказательство полностью аналогично предыдущему: фиксирование первых битов приводит к тому, что ˜ ∈ Ω c вероятностью 1. Точно так же для произвольного =0.1 2 . . . +1 . . . ∈ Ω (˜ = ) = (˜+1 = +1 , . . . , ˜ = ) = (˜+1 = +1 ) · . . . · (˜ = ) =12−,(3.13)что доказывает равномерность распределения, поскольку количество элементов в Ω в точностиравно 2− .К предлагаемой идее можно относиться как к способу рандомизации квазислучайных последовательностей.
Так, скрэмблинг Оуэна (определение 5) имеет ряд замечательных свойств,но обладает определённой вычислительной сложностью. Предлагаемая процедура крайне проста алгоритмически и предлагает гибкую параметрическую шкалу степени рандомизации. С83другой стороны, можно рассматривать этот алгоритм как способ генерации расслоенных выборок, опираясь на свойства распределённости квазислучайных последовательностей (например,(,,)-сетей). Оба этих тезиса будут проиллюстрированы далее.Чтобы продемонстрировать принцип работы гибридной битовой рандомизации при разныхзначениях параметра , мы далее приведём несколько рисунков, на которых изображен единичный гиперкуб в размерности = 2 и распределение точек случайной или квазислучайнойпоследовательности в нём.
Мы будем агрегировать количество точек, попадающих в двоичныеячейки квадрата различного объёма. Так, на рисунке 3.2 показана типичная случайная выборкаМонте-Карло (256 независимых реализаций случайной величины, имеющей равномерное распределение в [0,1]2 , объём каждой ячейки равен10.750.50.25001).25601102100121012000300020041110201101111102221030124211120103021020101221211210000100000110022103211212101111320022101231112121132203010130142011200110110012101011200010401211001221110311220340110011010021011110011121011020012210021110110301021031011002011000.250.50.751Рисунок 3.2: Распределение точек Монте-КарлоВ отличие от Монте-Карло, точки Соболя устроены таким образом, что пропорциональностьраспределения по ячейкам строго выполнена (рисунок 3.3). Это в точности отражает концепцию(,)-последовательности, отражённую определением 4.
Необходимо отметить, что рандомизация Оуэна 5, применённая к рассматриваемым точкам Соболя, сохраняет структуру рисунка 3.3.Теперь применим предлагаемую схему рандомизации с параметром = 3, результат которойприведён на рисунке 3.4. Визуально легко проследить, что такая структура является промежуточ-8410.750.50.250111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100.250.50.751Рисунок 3.3: Распределение точек Соболяной между Монте-Карло и квази-Монте-Карло. Более того, параметр подобран таким образом,что можно проследить сохранённые свойства распределённости по более крупным ячейкам: если провести объединение ячеек по четыре, то окажется, что структура равномерности на этомуровне будет соблюдена (этот эффект проиллюстрирован рисунком 3.6).Параметр позволяет варьировать размер ячеек, для которых строго соблюдаются свойствараспределённости.
Так, если для того же набора точек запустить предлагаемую процедуру с параметром = 4 или больше, мы снова получим картину равномерности, совпадающую с 3.3.Уменьшение параметра, наоборот, ведёт к укрупнению ячеек: так, при = 1 мы получим выборку, равномерно расслоенную только по четырём ячейкам, а именно [0, 12 ] × [0, 12 ], [0, 12 ] × [ 12 ,1],[ 12 ,1] × [0, 12 ] и [ 12 ,1] × [ 21 ,1].Аналогичную ситуацию можно наблюдать и при сдвиге параметра. Так, при агрегации поболее крупным ячейкам и = 2 (рисунок 3.5) равномерное расслоение не выполнено, но онобудет выполнено при = 3 (рисунок 3.6).Для рассматриваемого алгоритма крайне важной является исходная квазислучайная структура. Так, точки Соболя или другая произвольная (,)-последовательность обеспечивают описанные свойства распределённости расслоения, чего не произойдёт при использовании других8510.750.50.250000100113001013122122102102112002021011110111211200112111202100221101221012120111003201012011102021011111120202211211111111102001111102001030112021121111210030110202011201000102111110220031303011301021102110212002111112002020202022212011112111111001021021000.250.50.751Рисунок 3.4: Результат расслоения для = 3, мелкие ячейкиклассов low-discrepancy наборов.
Например, при использовании точек Холтона (эта последовательность является популярной альтернативой точкам Соболя; её определение дано в подразделе1.1.7) действие алгоритма будет иным. Это продемонстрировано рисунками 3.7 (исходное распределение) и 3.8 (конечное распределение при = 3), где отчётливо наблюдается несоблюдениесвойств строгой равномерности даже при объединении в достаточно крупные ячейки.3.3Гибридная битовая рандомизация в задаче численного интегрированияПрименим описанный алгоритм в простейшей задаче интегрирования. Возьмём уже рассмотренную ранее подынтегральную функцию „Морокофф-Кафлиш №1“ в размерности = 5. Иллюстрация работы алгоритма имеет тот же вид, что и в предыдущей главе: профили оценки стандартного отклонения при интегрировании различными методами.
Траектории „MC“ и „RQMC“,как и ранее, обозначают Монте-Карло и рандомизированный квази-Монте-Карло. Траектория„MC_strat“ отвечает за метод Монте-Карло с расслоением на 32 подмножества (полученных86146443546423435424132572756662234531425155365455544355242355354550.750.50.25000.250.50.751Рисунок 3.5: Результат расслоения для = 2, крупные ячейкиприменением правила бинарного рассечения единожды по всем пяти координатам).
Наконец,„Hybrid_k“ есть результат применения гибридной битовой рандомизации с параметром .Иллюстрация 3.9 демонстрирует следующие важные особенности сравниваемых алгоритмов:1) статическое расслоение („MC_strat“) быстро теряет эффективность с увеличением количества вычислений подынтегральной функции;2) поведение гибридной рандомизации соответствует предсказанному при значениях параметра , близких к краевым: вблизи = 0 оно повторяет Монте-Карло, при достаточнобольших – квази-Монте-Карло;3) для повторения траектории рандомизированного квази-Монте-Карло достаточно = 26(при дальнейшем увеличении траектории, по сути, идентичны, и поэтому не приведены);(︀)︀4) скорость убывания стандартного отклонения соответствует теоретической: −0.5 для(︀)︀MC, −1+ для RQMC;5) небольшой диапазон возможных параметров покрывает переход от MC к RQMC (по сути,достаточно перебрать 0 6 6 10).87144444444444444444444444444444444444444444444444444444444444444440.750.50.25000.250.50.751Рисунок 3.6: Результат расслоения для = 3, крупные ячейкиПомимо этого, все перечисленные особенности выполнены и для достаточно высоких размерностей: вариант = 20 указан на иллюстрации 3.10, что свидетельствует об универсальностиметода.Подводя промежуточный итог, отметим, что алгоритм использования гибридной битовой рандомизации в задачах численного интегрирования может служить заменой расслоению, причём,с одной стороны, он несложен с алгоритмической точки зрения (по сравнению с известной процедурой скрэмблинга, например), а с другой, остаётся эффективным с ростом размерности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
