Выборка с обратным преобразованием - Inverse transform sampling

Метод обратного преобразования (также известный как выборки инверсии , то интеграл вероятности обратного преобразования , в метод обратного преобразования , Смирнов преобразования , или Золотое правило ) является основным методом для псевдо-случайного числа выборки , то есть, для генерации выборок числа в случайном из любого распределение вероятностей с учетом его кумулятивной функции распределения .

Выборка с обратным преобразованием берет однородные выборки числа от 0 до 1, интерпретируемых как вероятность, а затем возвращает наибольшее число из области распределения, такое что . Например, представьте, что это стандартное нормальное распределение с нулевым средним и единичным стандартным отклонением. В таблице ниже показаны образцы, взятые из равномерного распределения, и их представление в стандартном нормальном распределении.

Преобразование однородного образца в нормальный
.5 0
0,975 1,95996
0,995 2,5758
.999999 4,75342
1-2 -52 8,12589
Выборка с обратным преобразованием для нормального распределения

Мы случайным образом выбираем долю площади под кривой и возвращаем число в домене так, чтобы именно эта доля площади находилась слева от этого числа. Интуитивно мы вряд ли выберем число на дальнем конце хвостов, потому что в них очень мало области, что потребовало бы выбора числа, очень близкого к нулю или единице.

С вычислительной точки зрения этот метод включает в себя вычисление функции квантиля распределения - другими словами, вычисление кумулятивной функции распределения (CDF) распределения (которая отображает число в домене с вероятностью от 0 до 1), а затем инвертирование этой функции. Отсюда термин «инверсия» или «инверсия» в большинстве названий этого метода. Обратите внимание, что для дискретного распределения вычисление CDF в целом не слишком сложно: мы просто складываем индивидуальные вероятности для различных точек распределения. Однако для непрерывного распределения нам необходимо интегрировать функцию плотности вероятности (PDF) распределения, что невозможно сделать аналитически для большинства распределений (включая нормальное распределение ). В результате этот метод может быть неэффективным с вычислительной точки зрения для многих дистрибутивов, поэтому предпочтение отдается другим методам; тем не менее, это полезный метод для создания более универсальных пробоотборников, например, основанных на отборе отбракованных проб .

Для нормального распределения отсутствие аналитического выражения для соответствующей функции квантиля означает, что другие методы (например, преобразование Бокса – Мюллера ) могут быть предпочтительнее с вычислительной точки зрения. Часто бывает так, что даже для простых распределений метод выборки с обратным преобразованием может быть улучшен: см., Например, алгоритм зиккурата и выборку отклонения . С другой стороны, можно очень точно аппроксимировать функцию квантиля нормального распределения, используя полиномы умеренной степени, и на самом деле метод этого достаточно быстр, так что инверсионная выборка теперь является методом по умолчанию для выборки из нормального распределения. в статистическом пакете R .

Определение

Интегральная вероятность преобразование состояния , что , если это непрерывная случайная величина с функцией распределения , то случайная величина имеет равномерное распределение на [0, 1]. Обратное интегральное преобразование вероятности - это как раз обратное этому: в частности, если имеет равномерное распределение на [0, 1] и если имеет кумулятивное распределение , то случайная величина имеет то же распределение, что и .

График техники инверсии от до . В правом нижнем углу мы видим обычную функцию, а в левом верхнем - ее инверсию.

Интуиция

From , мы хотим сгенерировать с помощью CDF Мы предполагаем, что это строго возрастающая функция, что обеспечивает хорошую интуицию.

Мы хотим увидеть, сможем ли мы найти какое-нибудь строго монотонное преобразование , такое, что . Мы будем иметь

где последний шаг использовал то, когда равномерно на .

Итак, мы должны быть обратной функцией , или, что то же самое,

Следовательно, мы можем генерировать из

Метод

Схема обратного преобразования выборки. Обратную функцию можно определить как .
Анимация того, как выборка с обратным преобразованием генерирует нормально распределенные случайные значения из равномерно распределенных случайных значений

Проблема, которую решает метод выборки с обратным преобразованием, заключается в следующем:

Метод выборки с обратным преобразованием работает следующим образом:

  1. Сгенерируйте случайное число из стандартного равномерного распределения в интервале , например, из
  2. Найдите обратную величину желаемой функции CDF, например .
  3. Вычислить . Вычисленная случайная величина имеет распределение .

Выражаясь по-другому, случайная величина имеет распределение (или является распределенной ) при наличии непрерывной однородной переменной в и обратимой кумулятивной функции распределения .

Может быть дана трактовка таких обратных функций как объектов, удовлетворяющих дифференциальным уравнениям. Некоторые такие дифференциальные уравнения допускают явные решения в виде степенных рядов, несмотря на их нелинейность.

Примеры

Чтобы выполнить инверсию, мы хотим решить для
Отсюда мы будем выполнять шаги один, два и три.
  • В качестве другого примера мы используем экспоненциальное распределение с для x ≥ 0 (и 0 в противном случае). Решая y = F (x), получаем обратную функцию
Это означает, что если мы возьмем что-то из a и вычислим, это будет экспоненциальное распределение.
Идея проиллюстрирована на следующем графике:
Случайные числа y i генерируются из равномерного распределения между 0 и 1, то есть Y ~ U (0, 1). Они нарисованы в виде цветных точек на оси Y. Каждая из точек отображается в соответствии с x = F -1 (y), что показано серыми стрелками для двух примерных точек. В этом примере мы использовали экспоненциальное распределение. Следовательно, для x ≥ 0 плотность вероятности равна, а кумулятивная функция распределения равна . Поэтому . Мы можем видеть, что при использовании этого метода многие точки в конечном итоге близки к нулю, и только несколько точек в конечном итоге имеют высокие значения x - так же, как и ожидается для экспоненциального распределения.
Обратите внимание, что распределение не изменится, если мы начнем с 1-y вместо y. Поэтому для вычислительных целей достаточно сгенерировать случайные числа y в [0, 1], а затем просто вычислить

Доказательство правильности

Пусть F - непрерывная кумулятивная функция распределения , и пусть F −1 - ее обратная функция (с использованием точной нижней грани, поскольку CDF слабо монотонны и непрерывны справа ):

Утверждение: Если U является равномерной случайной переменной на (0, 1) , то есть F в качестве КОР.

Доказательство:

Усеченное распределение

Выборка с обратным преобразованием может быть просто расширена на случаи усеченного распределения на интервале без затрат на выборку отклонения: можно следовать тому же алгоритму, но вместо генерации случайного числа, равномерно распределенного между 0 и 1, генерировать равномерно распределенное между и , и потом снова бери .

Уменьшение количества инверсий

Чтобы получить большое количество выборок, необходимо выполнить такое же количество инверсий распределения. Один из возможных способов уменьшить количество инверсий при получении большого количества выборок - это применение так называемого стохастического коллокационного сэмплера Монте-Карло (SCMC-сэмплер) в рамках структуры полиномиального хаоса . Это позволяет нам генерировать любое количество выборок Монте-Карло с помощью всего лишь нескольких инверсий исходного распределения с независимыми выборками переменной, для которой инверсии доступны аналитически, например стандартной нормальной переменной.

Смотрите также

Рекомендации

  1. ^ Университет Аалто, Н. Хивёнен, Вычислительные методы в обратных задачах. Двенадцатая лекция https://noppa.tkk.fi/noppa/kurssi/mat-1.3626/luennot/Mat-1_3626_lecture12.pdf
  2. ^ Люк Devroye (1986). Генерация неоднородной случайной величины (PDF) . Нью-Йорк: Springer-Verlag.
  3. ^ https://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html
  4. ^ Штайнбрехер Г., Шоу, WT (2008). Квантильная механика. Европейский журнал прикладной математики 19 (2): 87–112.
  5. ^ Люк Devroye (1986). «Раздел 2.2. Инверсия путем численного решения F ( X ) =  U » (PDF) . Генерация неоднородной случайной величины . Нью-Йорк: Springer-Verlag.
  6. ^ LA Grzelak, JAS Witteveen, М. Суарес, и CW Oosterlee. Сэмплер Монте-Карло со стохастической коллокацией: высокоэффективный отбор образцов из «дорогих» распределений. https://ssrn.com/abstract=2529691