Семплирование по Гиббсу

Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайя Гиббса.

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

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

Алгоритм

Пусть есть совместное распределение $p(x_1,...,x_d)$ $d$ случайных величин, причем $d$ может быть очень большим. Пусть на шаге $t$ мы уже выбрали какое-то значение $X = \{x^t_i\}$. На каждом шаге делаются следующие действия:

1. Выбирается индекс $i: (1 \le i \le d$).
2. $x^{t+1}_i$ выбирается по распределению $p(x_i | x^{t}_1,...,x^{t}_{i-1},x^{t}_{i+1},...,x^t_n)$, а для остальных индексов значение не меняется: $x^{t+1}_j = x^t_j$ (j≠i).

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

Ссылки

Гиббс в байесовских сетях - the BUGS Project

См. также

• Алгоритм Метрополиса-Гастингса
• Выборка по значимости