Это обратное преобразование, случайное блуждание Метрополис-Гастингс или Гиббс? Анализ, сосредоточенный на математической основе, реализации Python с нуля и плюсах и минусах каждого метода.

Введение в аппроксимационную выборку

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

— Распознавание образов и машинное обучение¹

Поскольку детерминированный вывод часто неразрешим с вероятностными моделями, как мы только что видели, теперь мы обратимся к методам аппроксимации, основанным на числовой выборке, которые известны как методы Монте-Карло. Ключевой вопрос, который мы рассмотрим с помощью этих методов, — это вычисление математического ожидания целевой функции f(z) с учетом распределения вероятностей p(z). Напомним, что простое определение ожидания задается как интеграл:

Как мы увидим, эти интегралы слишком сложны в вычислительном отношении, поэтому в этой статье мы обратимся к методам выборки.

В этой статье мы рассмотрим три основных метода выборки: обратное преобразование, цепь Маркова Монте-Карло (MCMC) и выборку Гиббса. Понимая основные статистические свойства и вычислительные требования этих методов, мы узнаем, что:

  • Выборка с обратным преобразованием лучше всего подходит для моделирования данных с высокой точностью из известных и простых распределений, особенно в малых размерностях.
  • Случайное блуждание Метрополис-Гастингс лучше всего подходит для сложных, мультимодальных или неизвестных распределений, где глобальное исследование и/или конвергенция являются приоритетом; в частности, алгоритм Метрополис — конкретный экземпляр Метрополиса-Гастингса — можно использовать для симметричных распределений.
  • Выборка Гиббса лучше всего подходит для задач большой размерности, где условные распределения легко выбирать, а эффективность является приоритетом.

Оглавление

  1. Выборка обратного преобразования
    • Как работает алгоритм?
    • Реализация на Python
    • Предпосылки
    • За и против
  2. Цепь Маркова Монте-Карло
    • Алгоритм Метрополиса-Гастингса
    • Особый пример: алгоритм Метрополиса для симметричного распределения
    • Плюсы/против
  3. Гиббс
    • Алгоритм
    • Условия
    • Отношения Гиббса с Метрополисом-Гастингсом
  4. Сравнение: плюсы и минусы трансформации против Мет-Гастингса и Гиббса

1. Метод преобразования: обратный CDF.

Выборка с обратным преобразованием, как следует из названия, использует обратную кумулятивную функцию распределения (CDF) целевого распределения для генерации случайных чисел, которые соответствуют желаемому распределению. Основная идея заключается в следующем:

  1. Сгенерировать однородное случайное число: мы рисуем число U из равномерного распределения между 0 и 1.
  2. Применить обратный CDF. Используя обратный CDF целевого дистрибутива, преобразуйте U в образец, соответствующий целевому дистрибутиву.

Вот краткая иллюстрация того, как образцы (синий) извлекаются из распределения (красный):

Обратная CDF — это вычислительно простой и обобщаемыйметод выборки из распределений, для которых мы знаем CDF, таких как нормальное, экспоненциальное, гамма или бета-распределение.

PDF, CDF и инверсный CDF

Говоря интуитивно, CDF — это совокупное значение PDF, равное интегралу PDF; затем мы берем обратную функцию CDF, чтобы получить окончательную обратную функцию CDF, используемую для этого метода.

Формально, если a является случайной величиной, то CDF a определяется следующим образом:

CDF F имеет следующие ключевые свойства:

  • F является непрерывным
  • F не убывает
  • F имеет диапазон 0 ≤ cdf(a) ≤ 1 для всех a ∈ R

Как работает обратный алгоритм CDF?

Алгоритм состоит из следующих ингредиентов:

Ввод:

  • U: U – это равномерная случайная величина, лежащая в диапазоне от 0 до 1.
  • Это служит входной вероятностью для обратного CDF и будет преобразовано в выборку из желаемого распределения.

Параметр:

  • F:CDF целевого дистрибутива.
  • С помощью F, мы можем просто вычислить его обратную величину, F^-1, и использовать ее для сопоставления входного значения с желаемым доменом.

Выход:

  • x: случайная выборка, полученная из целевого распределения.
  • Это генерируется путем применения обратного CDF к случайному числу из равномерного распределения (входные данные).

Реализация Python

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

С помощью стандартных методов вычислительной интеграции мы обнаруживаем, что целевой CDF F(x) равен:

Обратный этому CDF:

Мы сгенерируем 5000 выборок, используя метод Inverse CDF:

import numpy as np
import matplotlib.pyplot as plt

# Inverse CDF for the exponential distribution with lambda = 1
def inverse_cdf(p):
    return -np.log(1 - p)

# Generate 1000 sample values using inverse CDF
uniform_samples = np.random.uniform(0, 1, 1000)
transformed_samples = inverse_cdf(uniform_samples)

# Generate x values and true PDF
x_values = np.linspace(0, np.max(transformed_samples), 1000)
pdf_values = np.exp(-x_values)

Требования для работы обратного алгоритма CDF

Метод обратного CDF делает ключевое предположение:

  • CDF F является обратимым: CDF F должен быть обратимым, то есть каждый вход в F должен иметь уникальный вывод

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

  1. Функции констант. Любая константная функция в виде f(x) = c, где c — константа, не является обратимой, поскольку каждый входной сигнал отображается в тот же результат, и, следовательно, функция не является взаимно однозначной.

2.Некоторые квадратичные функции. Например, f(x) = x^2 необратима, поскольку ее отношение «многие к одному» (рассмотрим f(x) = 1, x может быть 1 или -1).

3. Некоторые тригонометрические функции: например, f(x) = sin(x) не обратимы во всей своей области определения, поскольку они периодические, хотя и с ограниченными областями определения. их можно сделать обратимыми.

Почему работает обратный CDF?

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

Преимущества

  1. Алгоритмическая простота: его очень легко реализовать с использованием данных меньшей размерности, что обеспечивает широкую область применения в различных областях и задачах.
  2. Точность выборки. Если предположить, что CDF и его инверсия представляют собой точное целевое распределение, этот метод обеспечивает относительно высокую точность по сравнению с другими методами, такими как MCMC, который мы скоро увидим.

Недостатки

  1. Вычислительная сложность. Для некоторых дистрибутивов обратный CDF может не иметь выражения в замкнутой форме, что делает вычисления сложными или дорогостоящими.
  2. Трудности с высокой размерностью. Его может быть сложно применить в многомерных пространствах, особенно с зависимостями между переменными.
  3. Ограничение обратимости: каждый раз, когда CDF необратим, этот метод становится недействительным. Это исключает ряд функций, как мы видели выше.
  4. Ограничено известными дистрибутивами: для обратного CDF требуется точная форма CDF, что ограничивает его применение только известными дистрибутивами.

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

Учитывая эти преимущества и недостатки, давайте теперь рассмотрим другую структуру случайной выборки, которая устраняет эти ограничения: Цепь Маркова Монте-Карло (MCMC).

2. Цепь Маркова Монте-Карло (MCMC)

Как мы только что увидели, метод обратного преобразования CDF сильно ограничен, особенно смногомерными пространствами выборки. Цепь Маркова Монте-Карло (MCMC), с другой стороны, хорошо масштабируется в зависимости от размерности, что позволяет нам осуществлять выборку из гораздо большего семейства распределений.

Как работает алгоритм Метрополиса-Гастингса?

Интуитивно понятно, что алгоритм работает следующим образом: Как и в случае с обратным CDF, у нас есть целевое распределение, из которого мы делаем выборку. Однако нам нужен дополнительный ингредиент: текущее состояние z*, и q(z|z*) зависит от z*, создавая цепь Маркова с выборками z¹, z², z³,. Каждая выборка принимается в цепочку только в том случае, если она удовлетворяет определенному критерию, который мы определим ниже, поскольку этот критерий различается в разных вариантах алгоритма.

Давайте формализуем это в более алгоритмическую структуру.

Алгоритм работает циклично, и каждый цикл состоит из следующих шагов:

  1. Создайте образец z* из распределения предложений.
  2. Примите выборку с вероятностью. Затем мы примем это значение с вероятностью принятия, которая в Метрополис-Хастингс определяется как:

где

  • z* — текущее состояние.
  • z^T — предлагаемое новое состояние.
  • p(z*) — вероятность состояния z* в соответствии с желаемым распределением.
  • p(z^T) — вероятность состояния z^T в соответствии с желаемым распределением.

Логика этого порога приемлемости заключается в том, что он гарантирует, что более вероятные состояния (в соответствии с желаемым распределением) посещаются чаще.

Это наиболее обобщенная версия алгоритма; если известно, что распределение предложений симметрично, это означает, что вероятность предложить переход из состояния x в x' такая же, как и вероятность предложения перехода из x ' до x,т.е. q(x′|x) = q(x|x′) , то мы можем использовать частный случай Метрополиса-Гастингса, который требует более простого порога приемлемости.

Алгоритм Метрополиса для симметричных распределений

Это особый алгоритм MCMC, который мы решили использовать если распределение предложений симметрично, т. е. q(z⁰ | z¹) = q(z¹ | z⁰) для всех значений 1 и 0, что интерпретируется как « вероятность перехода из любого состояния А в состояние В равна вероятности перехода из В в А». Итак, каждый шаг алгоритма выглядит следующим образом:

  1. Создайте выборку z* из распределения предложений.
  2. Примите выборку с вероятностью:

Метрополис-Гастингс и алгоритмы мегаполиса

Давайте посмотрим на алгоритмы бок о бок. Как мы видели ранее, единственная разница — это порог приемлемости; все остальные шаги алгоритмов выполняются одинаково:

Преимущества

  1. Сходимость к равновесному распределению. В некоторых случаях случайное блуждание может прийти к желаемому равновесному распределению, хотя в многомерных пространствах это, вероятно, занимает много времени.
  2. Низкие вычислительные затраты. Случайное блуждание часто требует меньше вычислительных ресурсов по сравнению с другими сложными методами выборки, что делает его подходящим для задач, где эффективность вычислений является приоритетом.
  3. Универсальность применения. Благодаря большому сходству с естественными закономерностями случайное блуждание находит применение в самых разных областях:
    • Физика: броуновское движение молекул в жидкостях и газах.
    /> • Сетевой анализ
    • Финансовые рынки: для моделирования движения цен на акции
    • Популяционная генетика

Недостатки:

  1. Чувствительность к инициализации. Производительность алгоритма может зависеть от выбора начальных значений, особенно если инициализированные значения находятся далеко от областей с высокой плотностью.
  2. Ловушки локальности. В зависимости от сложности распределения предложений алгоритм может застрять в локальных оптимумах и столкнуться с трудностями при переходе к другим областям распределения.

Теперь, имея в виду алгоритм Метрополиса-Гастингса, давайте посмотрим на другой его частный случай: выборку Гиббса.

3. Выборка Гиббса

Выборка Гиббса — это особый случай Метрополиса-Гастингса, где всегда принимается каждый шаг. Давайте сначала посмотрим на сам алгоритм выборки Гиббса.

Как работает алгоритм Гиббса?

Идея относительно проста, и ее лучше всего проиллюстрировать, если сначала рассмотреть микропример, включающий выборку из распределения p(z1, z2, z3) по трем переменным. Алгоритм будет состоять из следующих шагов:

  1. На временном шаге T инициализируйте начальные значения, чтобы:

2. Нарисуйте новое значение для z1:.

3. Нарисуйте новое значение для второй позиции z2 из условия:

4. Наконец, нарисуйте новое значение для последней позиции z3:

5. Повторите этот процесс, циклически меняя три переменные z1…z3, пока не достигнет определенного удовлетворительного порога.

Обобщенный алгоритм

Формально алгоритм представлен сначала инициализацией стартовых позиций, а затем выполнением T последовательных шагов.

Условия, при которых Гиббс правильно выполняет выборку из целевого распределения

  1. Инвариантность. Целевое распределение p(z) инвариантно для каждого шага Гиббса, и, следовательно, p(z) инвариантно для всей цепи Маркова.
  2. Эргодичность. Если все условные распределения ненулевые, то подразумевается эргодичность, поскольку любая точка в пространстве z достижима за конечное число шагов.
  3. Достаточная приработка. Как мы видели на примере любого метода, требующего случайной инициализации, первые несколько выборок зависят от инициализации, и зависимость ослабевает после многих итераций.

Какое отношение это имеет к Метрополис-Гастингс?

В Метрополис-Хастингс мы определили порог приемлемости следующим образом:

Таким образом, шаги предложения Метрополиса-Гастингса всегда принимаются, как мы видели в алгоритме Гиббса.

Вариации

Поскольку метод Гиббса обновляет одну переменную за раз, между последовательными выборками существуют сильные зависимости. Чтобы преодолеть эту проблему, мы могли бы использовать промежуточную стратегию для выборки из групп переменных вместо отдельных переменных, известную как блокировка Гиббса.

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

4. Плюсы и минусы: обратный CDF против Метрополиса-Гастингса против Гиббса

Теперь, когда мы рассмотрели, как работает каждый алгоритм и области его применения, давайте подведем итог определяющим характеристикам каждого метода.

1. Выборка обратного преобразования

  • Размер данных: лучше всего подходит для наборов данных среднего размера.
  • Время: обычно эффективно для одномерных распределений.
  • Сложность данных: используйте для простых распределений, где кумулятивная функция распределения (CDF) и ее обратная функция известны и их легко вычислить.
  • Считайте, что следует избегать, если: осуществляется выборка многомерных переменных/распределений.
  • Самое большое преимущество: высокая точность, если CDF точно отражает целевое распределение.
  • Требование: CDF должен быть известен и обратим.

2. Метрополис-Гастингс (MCMC)

  • Размер данных: масштабируемый и подходит для больших наборов данных.
  • Время: может потребовать больших вычислительных ресурсов в зависимости от сложности целевого распределения.
  • Сложность данных: идеально подходит для сложных или мультимодальных рассылок.
  • Основные преимущества:
     – можно выполнять выборку из распределения, не зная его константы нормализации (полная форма).
     – отлично подходит для исследования глобальной структуры распределения и гарантирует сходимость.
  • Недостаток:может страдать от очень медленной сходимости при
    - сложном или мультимодальном целевом распределении, поскольку алгоритм может застрять в локальных режимах и испытывать трудности с переходом между ними;
    - переменные сильно коррелированы;
    - пространства большой размерности;
    — неправильные начальные значения или выбор размера шага

3. Выборка Гиббса

  • Размер данных: подходит как для небольших, так и для больших наборов данных.
  • Время: зачастую более эффективно, чем случайное блуждание Метрополис-Гастингс, поскольку не требует шагов принятия/отклонения.
  • Сложность данных. Лучше всего использовать при работе с многомерными распределениями, где можно выполнить выборку из условного распределения каждой переменной.
  • Основные преимущества:
    – Легко вычисляет условные распределения;
    – Менее подвержен ловушкам локальных минимумов по сравнению со случайным блужданием.
  • Требования:
    - Эргодичность цепи Маркова
    - Полные условные распределения должны быть известны и понятны.

В итоге:

Заключение

Спасибо, что остаетесь со мной до сих пор! В этой статье мы рассмотрели 3 ключевых метода аппроксимационной выборки: обратный CDF, Metropolis Hastings MCMC и Gibbs Sampling MCMC. Мы изучили, как работает каждый алгоритм, его преимущества и недостатки, а также типичные варианты использования.

Инверсный CDF предоставляет простой метод выборки из известного распределения, когда его CDF обратим. Он эффективен в вычислительном отношении, но менее подходит для многомерных или сложных распределений.
Metropolis Hastings MCMC предлагает более общий подход, позволяющий осуществлять выборку из распределений, с которыми иначе сложно справиться. Однако он требует больше вычислительных ресурсов и может быть чувствителен к настройке таких параметров, как распределение предложений.
Выборка Гиббса MCMC особенно эффективна, когда совместное распределение сложное, но его можно разбить на более простые условные распределения. Он широко используется в машинном обучении, хотя сходимость может быть медленной и требует большого объема памяти для многомерных задач.

[1] Бишоп, CM (2016). Распознавание образов и машинное обучение (перепечатка первого издания 2006 г. в мягкой обложке (исправлено в 8-м издании 2009 г.)). Спрингер Нью-Йорк.

*Если не указано иное, все изображения созданы автором.