выборка Гиббса

Алгоритм Монте-Карло

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

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

Как и в случае с другими алгоритмами MCMC, выборка Гиббса генерирует цепь Маркова выборок, каждая из которых коррелирует с близлежащими выборками. В результате, необходимо соблюдать осторожность, если требуются независимые выборки. Как правило, выборки из начала цепочки ( период выгорания ) могут неточно представлять желаемое распределение и обычно отбрасываются.

Введение

Выборка Гиббса названа в честь физика Джозайи Уилларда Гиббса , в связи с аналогией между алгоритмом выборки и статистической физикой . Алгоритм был описан братьями Стюартом и Дональдом Геманами в 1984 году, примерно через восемь десятилетий после смерти Гиббса, ^[1] и стал популярен в статистическом сообществе для вычисления распределения маргинальной вероятности, особенно апостериорного распределения. ^[2]

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

Выборка Гиббса применима, когда совместное распределение неизвестно явно или его трудно сделать напрямую, но условное распределение каждой переменной известно и его легко (или, по крайней мере, легче) сделать. Алгоритм выборки Гиббса генерирует экземпляр из распределения каждой переменной по очереди, в зависимости от текущих значений других переменных. Можно показать, что последовательность выборок представляет собой цепь Маркова , а стационарное распределение этой цепи Маркова — это как раз искомое совместное распределение. ^[3]

Выборка Гиббса особенно хорошо подходит для выборки апостериорного распределения байесовской сети , поскольку байесовские сети обычно определяются как набор условных распределений.

Выполнение

Выборка Гиббса в своей базовой инкарнации является частным случаем алгоритма Метрополиса–Гастингса . Суть выборки Гиббса в том, что при наличии многомерного распределения проще сделать выборку из условного распределения, чем маргинализировать путем интегрирования по совместному распределению . Предположим, что мы хотим получить выборки -мерного случайного вектора . Мы действуем итеративно: ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle \mathbf {X} =(X_{1},\dots ,X_{n})}$

• Начните с некоторого начального значения . ${\displaystyle \mathbf {X} ^{(0)}}$
• При наличии выборки , чтобы получить следующую выборку , мы можем сделать выборку каждого компонента из распределения , обусловленного всеми выбранными до сих пор компонентами: мы делаем выборку на для всех , и на для . Другими словами, мы делаем выборку в соответствии с распределением . ${\displaystyle \mathbf {X} ^{(i)}=\left(x_{1}^{(i)},\dots ,x_{n}^{(i)}\right)}$ ${\displaystyle \mathbf {X} ^{(i+1)}=\left(x_{1}^{(i+1)},x_{2}^{(i+1)},\dots ,x_{n}^{(i+1)}\right)}$ ${\displaystyle x_{j}^{(i+1)}}$ ${\displaystyle X_{j}}$ ${\displaystyle X_{\ell }^{(i+1)}}$ ${\displaystyle \ell \leq j-1}$ ${\displaystyle X_{\ell }^{(i)}}$ ${\displaystyle j+1\leq \ell \leq n}$ ${\displaystyle x_{j}^{(i+1)}}$ ${\displaystyle P\left(X_{j}=\cdot |X_{1}=x_{1}^{(i+1)},\dots ,X_{j-1}=x_{j-1}^{(i+1)},X_{j+1}=x_{j+1}^{(i)},\dots ,X_{n}=x_{n}^{(i)}\right)}$

Характеристики

Если проводится такой отбор проб, то сохраняются следующие важные факты:

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

При проведении отбора проб:

• Начальные значения переменных могут быть определены случайным образом или с помощью какого-либо другого алгоритма, например, максимизации ожидания .
• На самом деле нет необходимости определять начальное значение для первой выбранной переменной.
• Обычно вначале игнорируют некоторое количество образцов (так называемый период выгорания ), а затем рассматривают только каждый образец при усреднении значений для вычисления ожидания. Например, можно проигнорировать первые 1000 образцов, а затем усреднить каждый 100-й образец, отбросив все остальные. Причина этого в том, что (1) стационарное распределение цепи Маркова является желаемым совместным распределением по переменным, но может потребоваться некоторое время для достижения этого стационарного распределения; (2) последовательные образцы не являются независимыми друг от друга, а образуют цепь Маркова с некоторой степенью корреляции. Иногда алгоритмы могут использоваться для определения величины автокорреляции между образцами и значения (периода между образцами, которые фактически используются), вычисленного из этого, но на практике в этом задействовано изрядное количество « черной магии ». ${\displaystyle n}$ ${\displaystyle n}$
• Процесс имитации отжига часто используется для уменьшения поведения « случайного блуждания » на ранней стадии процесса выборки (т. е. тенденции медленно перемещаться по пространству выборки с высокой степенью автокорреляции между выборками, а не быстро, как хотелось бы). Другими методами, которые могут уменьшить автокорреляцию, являются свернутая выборка Гиббса , заблокированная выборка Гиббса и упорядоченная сверхрелаксация ; см. ниже.

Соотношение условного распределения и совместного распределения

Более того, условное распределение одной переменной при всех остальных пропорционально совместному распределению, т.е. для всех возможных значений : ${\displaystyle (x_{i})_{1\leq i\leq n}}$ ${\displaystyle \mathbf {X} }$

${\displaystyle P(X_{j}=x_{j}\mid (X_{i}=x_{i})_{i\neq j})={\frac {P((X_{i}=x_{i})_{i})}{P((X_{i}=x_{i})_{i\neq j})}}\propto P((X_{i}=x_{i})_{i})}$

«Пропорционально» в данном случае означает, что знаменатель не является функцией и, таким образом, одинаков для всех значений ; он образует часть константы нормализации для распределения по . На практике, чтобы определить природу условного распределения фактора , проще всего разложить совместное распределение в соответствии с индивидуальными условными распределениями, определенными графической моделью по переменным, проигнорировать все факторы, которые не являются функциями (все из которых вместе со знаменателем выше составляют константу нормализации), а затем восстановить константу нормализации в конце, если необходимо. На практике это означает выполнение одной из трех вещей: ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$

1. Если распределение дискретное, вычисляются отдельные вероятности всех возможных значений, а затем они суммируются для нахождения константы нормализации. ${\displaystyle x_{j}}$
2. Если распределение непрерывно и имеет известную форму, то константа нормировки также будет известна.
3. В других случаях константу нормализации обычно можно игнорировать, поскольку большинство методов выборки не требуют ее.

Вывод

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

Наиболее вероятное значение желаемого параметра ( мода ) затем может быть просто выбрано путем выбора значения выборки, которое встречается чаще всего; это по сути эквивалентно максимальной апостериорной оценке параметра. (Поскольку параметры обычно непрерывны, часто необходимо «бинировать» выбранные значения в один из конечного числа диапазонов или «бинов», чтобы получить значимую оценку моды.) Однако чаще выбирается ожидаемое значение ( среднее или среднее) выбранных значений; это байесовский оценщик , который использует дополнительные данные обо всем распределении, которые доступны из байесовской выборки, тогда как алгоритм максимизации, такой как максимизация ожидания (EM), способен возвращать только одну точку из распределения. Например, для унимодального распределения среднее (ожидаемое значение) обычно похоже на моду (наиболее распространенное значение), но если распределение смещено в одном направлении, среднее будет смещено в этом направлении, что фактически учитывает дополнительную массу вероятности в этом направлении. (Если распределение является многомодальным, ожидаемое значение может не возвращать значимую точку, и любая из мод обычно является лучшим выбором.)

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

Контролируемое обучение , неконтролируемое обучение и полуконтролируемое обучение (также известное как обучение с пропущенными значениями) можно реализовать, просто зафиксировав значения всех переменных, значения которых известны, и выполнив выборку из оставшихся.

Для наблюдаемых данных будет одна переменная для каждого наблюдения, а не, например, одна переменная, соответствующая выборочному среднему или выборочной дисперсии набора наблюдений. Фактически, обычно не будет вообще никаких переменных, соответствующих таким понятиям, как «выборочное среднее» или «выборочная дисперсия». Вместо этого в таком случае будут переменные, представляющие неизвестное истинное среднее и истинную дисперсию, и определение выборочных значений для этих переменных автоматически происходит в результате работы сэмплера Гиббса.

Обобщенные линейные модели (т. е. вариации линейной регрессии ) иногда можно обрабатывать с помощью выборки Гиббса. Например, пробит-регрессия для определения вероятности заданного бинарного (да/нет) выбора с нормально распределенными априорными значениями, размещенными над коэффициентами регрессии, может быть реализована с помощью выборки Гиббса, поскольку можно добавлять дополнительные переменные и использовать сопряженность . Однако логистическая регрессия не может обрабатываться таким образом. Одна из возможностей — аппроксимировать логистическую функцию смесью (обычно 7–9) нормальных распределений. Однако чаще вместо выборки Гиббса используется Метрополис-Гастингс .

Математическое образование

Предположим, что выборка взята из распределения, зависящего от вектора параметров длины , с априорным распределением . Может оказаться, что очень большое и численное интегрирование для нахождения предельных плотностей будет вычислительно затратным. Тогда альтернативный метод вычисления предельных плотностей заключается в создании цепи Маркова в пространстве путем повторения этих двух шагов: ${\displaystyle \left.X\right.}$ ${\displaystyle \theta \in \Theta \,\!}$ ${\displaystyle \left.d\right.}$ ${\displaystyle g(\theta _{1},\ldots ,\theta _{d})}$ ${\displaystyle \left.d\right.}$ ${\displaystyle \left.\theta _{i}\right.}$ ${\displaystyle \left.\Theta \right.}$

1. Выберите случайный индекс ${\displaystyle 1\leq j\leq d}$
2. Выберите новое значение для согласно ${\displaystyle \left.\theta _{j}\right.}$ ${\displaystyle g(\theta _{1},\ldots ,\theta _{j-1},\,\cdot \,,\theta _{j+1},\ldots ,\theta _{d})}$

Эти шаги определяют обратимую цепь Маркова с желаемым инвариантным распределением . Это можно доказать следующим образом. Определим, если для всех и обозначим вероятность перехода от к . Тогда вероятности перехода равны ${\displaystyle \left.g\right.}$ ${\displaystyle x\sim _{j}y}$ ${\displaystyle \left.x_{i}=y_{i}\right.}$ ${\displaystyle i\neq j}$ ${\displaystyle \left.p_{xy}\right.}$ ${\displaystyle x\in \Theta }$ ${\displaystyle y\in \Theta }$

${\displaystyle p_{xy}={\begin{cases}{\frac {1}{d}}{\frac {g(y)}{\sum _{z\in \Theta :z\sim _{j}x}g(z)}}&x\sim _{j}y\\0&{\text{otherwise}}\end{cases}}}$

Так

${\displaystyle g(x)p_{xy}={\frac {1}{d}}{\frac {g(x)g(y)}{\sum _{z\in \Theta :z\sim _{j}x}g(z)}}={\frac {1}{d}}{\frac {g(y)g(x)}{\sum _{z\in \Theta :z\sim _{j}y}g(z)}}=g(y)p_{yx}}$

поскольку является отношением эквивалентности . Таким образом, подробные уравнения баланса удовлетворяются, что означает, что цепь обратима и имеет инвариантное распределение . ${\displaystyle x\sim _{j}y}$ ${\displaystyle \left.g\right.}$

На практике индекс не выбирается случайным образом, и цепь циклически проходит по индексам по порядку. В общем случае это дает нестационарный марковский процесс, но каждый отдельный шаг все равно будет обратимым, а весь процесс все равно будет иметь желаемое стационарное распределение (пока цепь может получить доступ ко всем состояниям при фиксированном порядке). ${\displaystyle \left.j\right.}$

Семплер Гиббса в байесовском выводе и его связь с теорией информации

Пусть обозначают наблюдения, полученные из выборочного распределения , и будут априорной базой, поддерживаемой в пространстве параметров . Тогда одной из центральных целей байесовской статистики является аппроксимация апостериорной плотности ${\displaystyle y}$ ${\displaystyle f(y|\theta )}$ ${\displaystyle \pi (\theta )}$ ${\displaystyle \Theta }$

${\displaystyle \pi (\theta |y)={\frac {f(y|\theta )\cdot \pi (\theta )}{m(y)}}}$

где предполагается, что предельное правдоподобие конечно для всех . ${\displaystyle m(y)=\int _{\Theta }f(y|\theta )\cdot \pi (\theta )d\theta }$ ${\displaystyle y}$

Для объяснения сэмплера Гиббса мы дополнительно предполагаем, что пространство параметров разлагается следующим образом: ${\displaystyle \Theta }$

${\displaystyle \Theta =\prod _{i=1}^{K}\Theta _{i}=\Theta _{1}\times \cdots \Theta _{i}\times \cdots \times \Theta _{K},\quad \quad (K>1)}$,

где представляет декартово произведение . Каждое компонентное параметрическое пространство может быть набором скалярных компонентов, подвекторов или матриц. ${\displaystyle \times }$ ${\displaystyle \Theta _{i}}$

Определите набор , который дополняет . Основными ингредиентами сэмплера Гиббса является -ое полное условное апостериорное распределение для каждого ${\displaystyle \Theta _{-i}}$ ${\displaystyle \Theta _{i}}$ ${\displaystyle i}$ ${\displaystyle i=1,\cdots ,K}$

${\displaystyle \pi (\theta _{i}|\theta _{-i},y)=\pi (\theta _{i}|\theta _{1},\cdots ,\theta _{i-1},\theta _{i+1},\cdots ,\theta _{K},y)}$.

Наглядное описание алгоритма выборки Гиббса ^[4]

Схематическое описание информационного равенства, связанного с сэмплером Гиббса на i-м шаге цикла ^[4]

Следующий алгоритм описывает типовой сэмплер Гиббса:

${\displaystyle {\text{Initialize: pick arbitrary starting value}}\,\,\theta ^{(1)}=(\theta _{1}^{(1)},\theta _{2}^{(1)},\cdots ,\theta _{i}^{(1)},\theta _{i+1}^{(1)},\cdots ,\theta _{K}^{(1)})}$

${\displaystyle {\text{Iterate a Cycle:}}\,}$

${\displaystyle \quad \quad {\text{Step 1. draw}}\,\,\theta _{1}^{(s+1)}\sim \pi (\theta _{1}|\theta _{2}^{(s)},\theta _{3}^{(s)},\cdots ,\theta _{K}^{(s)},y)}$

${\displaystyle \quad \quad {\text{Step 2. draw}}\,\,\theta _{2}^{(s+1)}\sim \pi (\theta _{2}|\theta _{1}^{(s+1)},\theta _{3}^{(s)},\cdots ,\theta _{K}^{(s)},y)}$

${\displaystyle \quad \quad \quad \vdots }$

${\displaystyle \quad \quad {\text{Step i. draw}}\,\,\theta _{i}^{(s+1)}\sim \pi (\theta _{i}|\theta _{1}^{(s+1)},\theta _{2}^{(s+1)},\cdots ,\theta _{i-1}^{(s+1)},\theta _{i+1}^{(s)},\cdots ,\theta _{K}^{(s)},y)}$

${\displaystyle \quad \quad {\text{Step i+1. draw}}\,\,\theta _{i+1}^{(s+1)}\sim \pi (\theta _{i+1}|\theta _{1}^{(s+1)},\theta _{2}^{(s+1)},\cdots ,\theta _{i}^{(s+1)},\theta _{i+2}^{(s)},\cdots ,\theta _{K}^{(s)},y)}$

${\displaystyle \quad \quad \quad \vdots }$

${\displaystyle \quad \quad {\text{Step K. draw}}\,\,\theta _{K}^{(s+1)}\sim \pi (\theta _{K}|\theta _{1}^{(s+1)},\theta _{2}^{(s+1)},\cdots ,\theta _{K-1}^{(s+1)},y)}$

${\displaystyle {\text{end Iterate}}}$

Обратите внимание, что сэмплер Гиббса работает по итеративной схеме Монте-Карло в цикле. Количество сэмплов, полученных с помощью вышеприведенного алгоритма, формирует цепи Маркова с инвариантным распределением, которое является целевой плотностью . ${\displaystyle S}$ ${\displaystyle \{\theta ^{(s)}\}_{s=1}^{S}}$ ${\displaystyle \pi (\theta |y)}$

Теперь для каждого определим следующие теоретико-информационные величины: ${\displaystyle i=1,\cdots ,K}$

${\displaystyle I(\theta _{i};\theta _{-i})={\text{KL}}(\pi (\theta |y)||\pi (\theta _{i}|y)\cdot \pi (\theta _{-i}|y))=\int _{\Theta }\pi (\theta |y)\log {\bigg (}{\frac {\pi (\theta |y)}{\pi (\theta _{i}|y)\cdot \pi (\theta _{-i}|y)}}{\bigg )}d\theta ,}$

${\displaystyle H(\theta _{-i})=-\int _{\Theta _{-i}}\pi (\theta _{-i}|y)\log \pi (\theta _{-i}|y)d\theta _{-i},}$

${\displaystyle H(\theta _{-i}|\theta _{i})=-\int _{\Theta }\pi (\theta |y)\log \pi (\theta _{-i}|\theta _{i},y)d\theta ,}$

а именно, апостериорная взаимная информация, апостериорная дифференциальная энтропия и апостериорная условная дифференциальная энтропия соответственно. Мы можем аналогично определить информационные теоретические величины , , и заменив и в определяемых величинах. Тогда справедливы следующие уравнения. ^[4] ${\displaystyle I(\theta _{-i};\theta _{i})}$ ${\displaystyle H(\theta _{i})}$ ${\displaystyle H(\theta _{i}|\theta _{-i})}$ ${\displaystyle i}$ ${\displaystyle -i}$ ${\displaystyle K}$

${\displaystyle I(\theta _{i};\theta _{-i})=H(\theta _{-i})-H(\theta _{-i}|\theta _{i})=H(\theta _{i})-H(\theta _{i}|\theta _{-i})=I(\theta _{-i};\theta _{i}),\quad (i=1,\cdots ,K)}$.

Взаимная информация количественно определяет уменьшение неопределенности случайной величины , как только мы узнаем , апостериори. Она исчезает тогда и только тогда, когда и являются незначительно независимыми, апостериори. Взаимную информацию можно интерпретировать как величину, которая передается с -го шага на -й шаг в течение одного цикла сэмплера Гиббса. ${\displaystyle I(\theta _{i};\theta _{-i})}$ ${\displaystyle \theta _{i}}$ ${\displaystyle \theta _{-i}}$ ${\displaystyle \theta _{i}}$ ${\displaystyle \theta _{-i}}$ ${\displaystyle I(\theta _{i};\theta _{-i})}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Вариации и расширения

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

Заблокированный сэмплер Гиббса

• Заблокированный сэмплер Гиббса группирует две или более переменных вместе и делает выборки из их совместного распределения, обусловленного всеми другими переменными, а не делает выборки из каждой по отдельности. Например, в скрытой марковской модели заблокированный сэмплер Гиббса может делать выборки из всех скрытых переменных, составляющих марковскую цепь , за один раз, используя алгоритм вперед-назад .

Свернутый сэмплер Гиббса

• Свернутый сэмплер Гиббса интегрирует ( маргинализирует по ) одну или несколько переменных при выборке для некоторой другой переменной. Например, представьте, что модель состоит из трех переменных A , B и C . Простой сэмплер Гиббса будет делать выборку из p ( A  |  B , C ), затем p ( B  |  A , C ), затем p ( C  |  A , B ). Свернутый сэмплер Гиббса может заменить шаг выборки для A выборкой, взятой из маргинального распределения p ( A  |  C ), с переменной B интегрированной в этом случае. В качестве альтернативы переменная B может быть полностью свернута, поочередно делая выборку из p ( A  |  C ) и p ( C  |  A ) и не делая выборку по B вообще. Распределение по переменной A , которое возникает при сворачивании родительской переменной B , называется составным распределением ; выборка из этого распределения, как правило, поддается обработке, когда B является сопряженным априорным распределением для A , особенно когда A и B являются членами экспоненциального семейства . Для получения дополнительной информации см. статью о сложных распределениях или Лю (1994). ^[5]

Реализация свернутого сэмплера Гиббса

Схлопывание распределений Дирихле

В иерархических байесовских моделях с категориальными переменными , такими как скрытое распределение Дирихле и различные другие модели, используемые в обработке естественного языка , довольно часто происходит сворачивание распределений Дирихле , которые обычно используются в качестве априорных распределений по категориальным переменным. Результат этого сворачивания вводит зависимости между всеми категориальными переменными, зависящими от данного априорного распределения Дирихле, и совместное распределение этих переменных после сворачивания является распределением Дирихле-мультиномиала . Условное распределение данной категориальной переменной в этом распределении, обусловленное другими, принимает чрезвычайно простую форму, которая делает выборку Гиббса еще проще, чем если бы сворачивание не было сделано. Правила следующие:

1. Сворачивание априорного узла Дирихле влияет только на родительские и дочерние узлы априорного узла. Поскольку родительский узел часто является константой, нам обычно нужно беспокоиться только о дочерних узлах.
2. Свертывание априорного распределения Дирихле вводит зависимости между всеми категориальными потомками, зависящими от этого априора, но не создает дополнительных зависимостей между любыми другими категориальными потомками. (Это важно иметь в виду, например, когда имеется несколько априорных распределений Дирихле, связанных одним и тем же гипераприором. Каждое априорное распределение Дирихле может быть независимо свернуто и влияет только на своих прямых потомков.)
3. После сворачивания условное распределение одного зависимого потомка по другим принимает очень простую форму: вероятность увидеть заданное значение пропорциональна сумме соответствующего гиперприора для этого значения и количеству всех других зависимых узлов, принимающих то же значение. Узлы, не зависящие от того же априора, не должны учитываться. То же правило применяется в других итеративных методах вывода, таких как вариационный Байес или максимизация ожидания ; однако, если метод включает в себя ведение частичных подсчетов, то частичные подсчеты для рассматриваемого значения должны быть просуммированы по всем другим зависимым узлам. Иногда это суммированное частичное подсчет называется ожидаемым подсчетом или аналогичным образом. Вероятность пропорциональна полученному значению; фактическая вероятность должна быть определена путем нормализации по всем возможным значениям, которые может принимать категориальная переменная (т. е. сложения вычисленного результата для каждого возможного значения категориальной переменной и деления всех вычисленных результатов на эту сумму).
4. Если заданный категориальный узел имеет зависимых потомков (например, когда он является скрытой переменной в смешанной модели ), значение, вычисленное на предыдущем шаге (ожидаемое количество плюс априорное, или что бы ни вычислялось), должно быть умножено на фактические условные вероятности ( а не вычисленное значение, пропорциональное вероятности!) всех потомков с учетом их родителей. Подробное обсуждение см. в статье о распределении Дирихле-мультиномиал .
5. В случае, когда членство в группе узлов, зависящих от заданного априорного распределения Дирихле, может динамически меняться в зависимости от некоторой другой переменной (например, категориальной переменной, индексированной другой скрытой категориальной переменной, как в тематической модели ), те же самые ожидаемые числа все еще вычисляются, но должны быть сделаны осторожно, чтобы был включен правильный набор переменных. См. статью о распределении Дирихле-мультиномиал для более подробного обсуждения, в том числе в контексте тематической модели.

Сворачивание других сопряженных априорных распределений

В общем случае, любое сопряженное априорное распределение может быть свернуто, если его единственные потомки имеют сопряженные с ним распределения. Соответствующая математика обсуждается в статье о составных распределениях . Если есть только один дочерний узел, результат часто будет предполагать известное распределение. Например, сворачивание дисперсии с обратным гамма-распределением из сети с одним гауссовым потомком даст распределение Стьюдента . (В этом отношении сворачивание как среднего, так и дисперсии одного гауссовского потомка все равно даст распределение Стьюдента, при условии, что оба они сопряжены, т. е. гауссовское среднее, обратная гамма-дисперсия.)

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

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

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

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

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

Семплер Гиббса с упорядоченной сверхрелаксацией

• Сэмплер Гиббса с упорядоченной сверхрелаксацией выбирает заданное нечетное число значений-кандидатов для на любом заданном шаге и сортирует их вместе с единственным значением для в соответствии с некоторым четко определенным порядком. Если является s ^-м наименьшим в отсортированном списке, то выбирается как s ^-й наибольший в отсортированном списке. Для получения дополнительной информации см. Neal (1995). ^[6] ${\displaystyle x_{j}^{(i)}}$ ${\displaystyle x_{j}^{(i-1)}}$ ${\displaystyle x_{j}^{(i-1)}}$ ${\displaystyle x_{j}^{(i)}}$

Другие расширения

Также возможно расширить выборку Гиббса различными способами. Например, в случае переменных, условное распределение которых нелегко выбрать, можно использовать одну итерацию выборки среза или алгоритм Метрополиса–Гастингса для выборки из рассматриваемых переменных. Также возможно включить переменные, которые не являются случайными величинами , но значение которых детерминировано вычисляется из других переменных. Обобщенные линейные модели , например, логистическая регрессия (также известная как « модели максимальной энтропии »), могут быть включены таким образом. (BUGS, например, допускает этот тип смешивания моделей.)

Виды отказов

Есть два способа, при которых выборка Гиббса может не сработать. Первый — когда есть острова высоковероятностных состояний, между которыми нет путей. Например, рассмотрим распределение вероятностей по 2-битным векторам, где векторы (0,0) и (1,1) каждый имеют вероятность ⁠1/2⁠ , но два других вектора (0,1) и (1,0) имеют нулевую вероятность. Выборка Гиббса попадет в ловушку одного из двух векторов с высокой вероятностью и никогда не достигнет другого. В более общем смысле, для любого распределения по многомерным действительным векторам, если два конкретных элемента вектора идеально коррелируют (или идеально антикоррелируют), эти два элемента застрянут, и выборка Гиббса никогда не сможет их изменить.

Вторая проблема может возникнуть даже тогда, когда все состояния имеют ненулевую вероятность и есть только один остров высоковероятных состояний. Например, рассмотрим распределение вероятностей по 100-битным векторам, где вектор из всех нулей встречается с вероятностью ⁠1/2⁠ , и все остальные векторы равновероятны, и поэтому имеют вероятность каждого. Если вы хотите оценить вероятность нулевого вектора, будет достаточно взять 100 или 1000 образцов из истинного распределения. Это, скорее всего, даст ответ, очень близкий к ⁠ ${\displaystyle {\frac {1}{2(2^{100}-1)}}}$1/2⁠ . Но вам, вероятно, придется взять больше образцов из выборки Гиббса, чтобы получить тот же результат. Ни один компьютер не смог бы сделать это за всю жизнь. ${\displaystyle 2^{100}}$

Эта проблема возникает независимо от того, насколько длителен период выжигания. Это происходит потому, что в истинном распределении нулевой вектор встречается в половине случаев, и эти появления случайным образом смешиваются с ненулевыми векторами. Даже небольшая выборка будет видеть как нулевые, так и ненулевые векторы. Но выборка Гиббса будет попеременно возвращать только нулевой вектор в течение длительных периодов (примерно подряд), а затем только ненулевые векторы в течение длительных периодов (примерно подряд). Таким образом, сходимость к истинному распределению чрезвычайно медленная, требующая гораздо больше, чем шагов; выполнение такого количества шагов вычислительно невыполнимо за разумный период времени. Медленную сходимость здесь можно рассматривать как следствие проклятия размерности . Подобную проблему можно решить путем блочной выборки всего 100-битного вектора сразу. (Это предполагает, что 100-битный вектор является частью большего набора переменных. Если этот вектор — единственное, что выбирается, то блочная выборка эквивалентна тому, чтобы вообще не выполнять выборку Гиббса, что по гипотезе было бы сложно.) ${\displaystyle 2^{99}}$ ${\displaystyle 2^{99}}$ ${\displaystyle 2^{99}}$

Программное обеспечение

• Программное обеспечение OpenBUGS ( байесовский вывод с использованием выборки Гиббса ) выполняет байесовский анализ сложных статистических моделей с использованием метода Монте-Карло для цепей Маркова .

• JAGS ( еще один сэмплер Гиббса ) — это программа GPL для анализа байесовских иерархических моделей с использованием метода Монте-Карло на основе цепей Маркова.

• Church — это бесплатное программное обеспечение для выполнения вывода Гиббса над произвольными распределениями, заданными как вероятностные программы.

• PyMC — это библиотека Python с открытым исходным кодом для байесовского обучения общих вероятностных графических моделей .
• Turing — это библиотека Julia с открытым исходным кодом для байесовского вывода с использованием вероятностного программирования .

Примечания

1. Geman, S. ; Geman, D. (1984). «Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений». Труды IEEE по анализу образов и машинному интеллекту . 6 (6): 721–741. doi :10.1109/TPAMI.1984.4767596. PMID  22499653.
2. Гельфанд, Алан Э.; Смит, Адриан Ф.М. (1990-06-01). «Подходы к расчету предельных плотностей на основе выборки». Журнал Американской статистической ассоциации . 85 (410): 398–409. doi :10.1080/01621459.1990.10476213. ISSN  0162-1459.
3. Гельман, Эндрю и Карлин, Джон Б. и Стерн, Хэл С. и Дансон, Дэвид Б. и Вехтари, Аки и Рубин, Дональд Б. (2014). Байесовский анализ данных . Том 2. FL: CRC press Boca Raton.{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Ли, Се Юн (2021). «Сэмплер Гиббса и вариационный вывод с восхождением координат: обзор теории множеств». Communications in Statistics - Theory and Methods . 51 (6): 1549–1568. arXiv : 2008.01006 . doi : 10.1080/03610926.2021.1921214. S2CID  220935477.
5. Лю, Цзюнь С. (сентябрь 1994 г.). «Коллапсированный сэмплер Гиббса в байесовских вычислениях с приложениями к проблеме регуляции генов». Журнал Американской статистической ассоциации . 89 (427): 958–966. doi :10.2307/2290921. JSTOR  2290921.
6. Нил, Рэдфорд М. (1995). Подавление случайных блужданий в цепях Маркова Монте-Карло с использованием упорядоченной сверхрелаксации (технический отчет). Университет Торонто, кафедра статистики. arXiv : bayes-an/9506004 . Bibcode : 1995bayes.an..6004N.

Ссылки

• Бишоп, Кристофер М. (2006), Распознавание образов и машинное обучение , Springer, ISBN 978-0-387-31073-2
• Болстад, Уильям М. (2010), Понимание вычислительной байесовской статистики , John Wiley ISBN 978-0-470-04609-8 
• Casella, G.; George, EI (1992). «Объяснение сэмплера Гиббса». The American Statistician . 46 (3): 167. CiteSeerX  10.1.1.554.3993 . doi :10.2307/2685208. JSTOR  2685208.(Содержит краткое изложение и множество ссылок.)
• Гельфанд, Алан Э.; Смит, Адриан Ф.М. (1990), «Подходы к расчету предельных плотностей на основе выборки», Журнал Американской статистической ассоциации , 85 (410): 398–409, doi :10.2307/2289776, JSTOR  2289776, MR  1141740
• Гельман, А. , Карлин Дж. Б., Стерн Х. С., Дансон Д., Вехтари А., Рубин Д. Б. (2013), Байесовский анализ данных , третье издание. Лондон: Chapman & Hall .
• Левин, Дэвид А.; Перес, Юваль ; Вильмер, Элизабет Л. (2008), « Цепи Маркова и времена перемешивания », Американское математическое общество .
• Роберт, К. П.; Каселла, Г. (2004), Статистические методы Монте-Карло (второе издание), Springer-Verlag.