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

редактировать

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

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

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

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

Содержание

1 Введение
2 Реализация
- 2.1 Связь условного распределения и совместного распределения
3 Вывод
4 Математические основы
5 Варианты и расширения
- 5.1 Блокированный сэмплер Гиббса
- 5.2 Свернутый сэмплер Гиббса
  - 5.2.1 Реализация свернутого сэмплера Гиббса
    - 5.2.1.1 Свертывание распределений Дирихле
    - 5.2.1.2 Свертывание других конъюгированных приоров
- 5.3 Сэмплер Гиббса с упорядоченным избыточным расслаблением
- 5.4 Другие расширения
6 Режимы отказа
7 Программное обеспечение
8 Примечания
9 Ссылки

Введение

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

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

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

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

Реализация

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

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

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

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

При выполнении выборка:

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

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

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

p (xj ∣ x 1,…, xj - 1, xj + 1,…, xn) = p (x 1,…, xn) p (x 1,…, xj - 1, xj + 1,…, xn) ∝ p (x 1,…, xn) {\ 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})}

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

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

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

Вывод

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

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

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

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

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

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

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

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

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

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

pxy = {1 dg (y) ∑ z ∈ Θ: z ∼ jxg (z) x ∼ jy 0 в противном случае {\ 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 {else}} \ end {cases}}}

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) pxy = 1 dg (x) g (y) ∑ z ∈ Θ: z ∼ jxg (z) Знак равно 1 dg (y) g (x) ∑ z ∈ Θ: z ∼ jyg (z) = g (y) pyx {\ 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}}

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

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

Варианты и расширения

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

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

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

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

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

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

Свертывающиеся распределения Дирихле

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

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

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

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

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

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

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

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

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

сэмплер Гиббса с упорядоченным избыточным расслаблением

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

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

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

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

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

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

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

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

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

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

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

PyMC3 - это библиотека Python с открытым исходным кодом для байесовского обучения общей вероятностной графической модели.

Примечания

Ссылки

Бишоп, Кристофер М. (2006), Распознавание образов и машинное обучение, Springer, ISBN 978-0-387-31073-2
Bols тэд, Уильям М. (2010), Понимание вычислительной байесовской статистики, Джон Вили ISBN 978-0-470-04609-8
Casella, G.; Джордж, Э. И. (1992). «Объясняя сэмплер Гиббса». Американский статистик. 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.
Levin, David A.; Перес, Юваль ; Уилмер, Элизабет Л. (2008), «Цепи Маркова и время смешения », Американское математическое общество.
Роберт, К.П.; Казелла, Г. (2004), Статистические методы Монте-Карло (второе издание), Springer-Verlag.

=== !!! == Знак равно <2>Y \ in \ Theta <2><3>{\ 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)} <3><4>{\ displaystyle x_ {j-1} ^ {(i + 1)}} <4><5>(i + 1) <5><6>k <6><7>\ left.g \ right. <7><8>g (\ theta _ {1}, \ ldots, \ theta _ {d}) <8><9>x \ in \ Theta <9><10>x_ {j} ^ {{{ (i)}} <10><11>{\ displaystyle \ mathbf {X} ^ {(i)} = \ left (x_ {1} ^ {(i)}, \ dots, x_ {n} ^ {( i)} \ right)} <11><12>n <12><13>i <13><14>\ left.j \ right. <14><15>\ left.k \ right. <15><16>\ left. \ Theta _ {i} \ right. <16><17>{\ displaystyle x_ {j + 1} ^ {(i)}} <17><18>g (\ theta _ {1 }, \ ldots, \ theta _ {{j-1}}, \, \ cdot \,, \ theta _ {{j + 1}}, \ ldots, \ theta _ {d}) <18><19>{\ displaystyle x_ {n} ^ {(i)}} <19><20>{\ frac {1} {2 (2 ^ {{100}} - 1)}} <20><21>{\ mathbf {X}} = (x_ {1}, \ точки, x_ {n}) <21><22>{\ displaystyle \ mathbf {X} ^ {(i + 1)} = \ left (x_ {1} ^ {(я + 1)}, x_ {2} ^ {(i + 1)}, \ точки, x_ {n} ^ {(i + 1)} \ right)} <22><23>{\ displaystyle p (x_ {1}, \ dots, x_ {n})} <23><24>{\ d isplaystyle \ mathbf {X} ^ {(i)}} <24><25>x_ {j} ^ {{(i + 1)}} <25><26>\ left.p _ {{xy}} \ right. <26><27>2 ^ {{99}} <27><28>\ left.d \ right. <28><29>\ left. \ Theta \ right. <29><30>x_ {j } ^ {{(i-1)}} <30><31>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}} <31><32>2 ^ {{100}} <32><33>x_ {j} <33><34>{\ displaystyle \ mathbf {X} ^ {(i + 1)}} <34><35>\ left.x_ {i } = y_ {i} \ right. <35><36>{\ displaystyle (j + 1)} <36><37>\ left.X \ right. <37><38>1 \ leq j \ leq d <38><39>\ left. \ Theta _ {j} \ right. <39><40>\ theta \ in \ Theta \, \! <40><41>p _ {{xy}} = {\ begin {case} {\ frac {1} {d}} {\ frac {g (y)} {\ sum _ {{z \ in \ Theta: z \ sim _ {j} x}} g (z)}} x \ sim _ {j} y \\ 0 {\ text {else}} \ end {cases}} <41><42>i \ neq j <42><43>x \ sim _ {j} y <43><44>{\ 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})} <44>html