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

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

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

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

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

Введение

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

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

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

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

Выполнение

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

1. Начнем с некоторого начального значения . ${\displaystyle \mathbf {X} ^{(0)}}$
2. Нам нужен следующий образец. Назовите следующий образец . Поскольку это вектор, мы выбираем каждый компонент вектора из распределения этого компонента, обусловленного всеми другими компонентами, выбранными до сих пор. Но есть одна загвоздка: мы ставим условия для компонентов s до , а затем ставим условия для компонентов s, начиная с до . Для этого мы отбираем компоненты по порядку, начиная с первого компонента. Более формально, для выборки мы обновляем ее в соответствии с распределением, указанным . Мы используем значение, которое имел компонент-й в образце-м, а не в образце-м. ${\displaystyle \mathbf {X} ^{(i+1)}}$ ${\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 \mathbf {X} ^{(i+1)}}$ ${\displaystyle x_{j-1}^{(i+1)}}$ ${\displaystyle \mathbf {X} ^{(i)}}$ ${\displaystyle x_{j+1}^{(i)}}$ ${\displaystyle x_{n}^{(i)}}$ ${\displaystyle x_{j}^{(i+1)}}$ ${\displaystyle p\left(x_{j}^{(i+1)}|x_{1}^{(i+1)},\dots ,x_{j-1}^{(i+1)},x_{j+1}^{(i)},\dots ,x_{n}^{(i)}\right)}$ ${\displaystyle (j+1)}$ ${\displaystyle i}$ ${\displaystyle (i+1)}$
3. Повторите указанные выше действия . ${\displaystyle k}$

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

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

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

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

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

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

Более того, условное распределение одной переменной с учетом всех остальных пропорционально совместному распределению:

${\displaystyle p(x_{j}\mid x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})={\frac {p(x_{1},\dots ,x_{n})}{p(x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})}}\propto p(x_{1},\dots ,x_{n})}$

«Пропорционально» в данном случае означает, что знаменатель не является функцией и, следовательно, одинаков для всех значений ; он является частью константы нормализации распределения по . На практике для определения характера условного распределения фактора проще всего факторизовать совместное распределение по отдельным условным распределениям, заданным графической моделью по переменным, игнорировать все факторы, не являющиеся функциями от (все из которых , вместе со знаменателем, указанным выше, составляют константу нормализации), а затем при необходимости восстановите константу нормализации в конце. На практике это означает выполнение одной из трех вещей: ${\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})}$

Эти шаги определяют обратимую цепь Маркова с желаемым инвариантным распределением . Это можно доказать следующим образом. Определим if для всех и обозначим через вероятность перехода от к . Тогда вероятности перехода равны ${\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 являются членами экспоненциального семейства . Для получения дополнительной информации см. статью о составных распределениях или Liu (1994). ^[5]

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

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

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

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

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

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

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

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

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

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

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

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

• Сэмплер Гиббса с упорядоченной сверхрелаксацией отбирает заданное нечетное количество возможных значений на любом заданном шаге и сортирует их вместе с единственным значением в соответствии с некоторым четко определенным порядком. Если это s- ^й наименьший элемент в отсортированном списке, то он выбирается как s- ^й по величине в отсортированном списке. Для получения дополнительной информации см. Нил (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) имеет вероятность ½, но два других вектора (0,1) и (1,0) имеют вероятность нуль. Выборка Гиббса окажется в ловушке одного из двух векторов с высокой вероятностью и никогда не достигнет другого. В более общем смысле, для любого распределения по многомерным векторам с действительными значениями, если два конкретных элемента вектора идеально коррелированы (или идеально антикоррелированы), эти два элемента застрянут, и выборка Гиббса никогда не сможет измениться. их.

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

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

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

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

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

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

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

Примечания

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

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

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