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

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

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

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

Введение

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

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

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

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

Выполнение

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

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

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

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

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

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

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

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

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

$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})$

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

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

Вывод

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

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

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

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

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

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

Математическая основа

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

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

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

$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}}$

Так

$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}$

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

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

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

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

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

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

Чтобы объяснить сэмплер Гиббса, мы дополнительно предполагаем, что пространство параметров $\Theta$ разлагается как

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

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

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

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

Графическое описание алгоритма выборки Гиббса.

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

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

${\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)})$

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

$\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)$

$\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)$

$\quad \quad \quad \vdots$

$\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)$

$\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)$

$\quad \quad \quad \vdots$

$\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)$

${\text{end Iterate}}$

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

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

$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 ,$

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

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

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

$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)$.

Взаимная информация $I(\theta _{i};\theta _{-i})$ количественно определяет уменьшение неопределенности случайной величины $\theta _{i}$ как только мы узнаем $\theta _{-i}$, апостериорно. Оно исчезает тогда и только тогда, когда $\theta _{i}$ и $\theta _{-i}$ маргинально независимы, задние. Взаимная информация $I(\theta _{i};\theta _{-i})$ можно интерпретировать как величину, передаваемую от $i$-й шаг к $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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Режимы отказа

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

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

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

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

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

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

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

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

Ссылки

• Бишоп, Кристофер М. (2006), Распознавание образов и машинное обучение , Springer, ISBN  978-0-387-31073-2
• Болстад, Уильям М. (2010), Понимание вычислительной байесовской статистики , Джон Уайли 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, doi : 10.2307/2289776 , JSTOR   2289776 , MR   1141740
• Гельман А. , Карлин Дж.Б., Стерн Х.С., Дансон Д., Вехтари А., Рубин Д.Б. (2013), Байесовский анализ данных , третье издание. Лондон: Чепмен и Холл .
• Левин, Дэвид А.; Перес, Юваль ; Уилмер, Элизабет Л. (2008), « Марковские цепи и времена смешивания », Американское математическое общество .
• Роберт, CP; Казелла, Г. (2004), Статистические методы Монте-Карло (второе издание), Springer-Verlag.