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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Алгоритм[править | править вики-текст]

Пусть есть совместное распределение 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_d), а для остальных индексов значение не меняется: x^{t+1}_j = x^t_j (j≠i).

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

Пример[править | править вики-текст]

Пусть есть совместное распределение p(x_1,x_2,x_3) из трех случайных величин, каждая из которых находится в диапазоне от 0 до 10. Примем, что первоначальное значение вектора, от которого начнется итерационный процесс, будет X = \{5,2,7\}. Далее фиксируем x_2 и x_3, после чего рассчитываем по известной заранее формуле условную вероятность p(x_1 | x_2,x_3), т.е. p(x_1 | x_2=2,x_3=7), получая некоторый график плотности вероятности от переменной x_1. То, что изначально x_1 мы положили равным 5, забываем, больше это значение не понадобится. Теперь необходимо выполнить семплирование - сгенерировать новое случайное значение для x_1 в соответствии с полученной плотностью вероятности. Семплирование можно сделать, например, по алгоритму выборки с отклонением. Для этого генерируется случайное число с равномерным распределением от 0 до 10, после чего для этого сгенерированного числа вычисляется его вероятность по графику плотности вероятности p(x_1 | x_2=2,x_3=7). Например, пусть сгенерировалось случайное число 4 и по графику плотности его вероятность равна 0.2. Тогда, в соответствии с алгоритмом выборки с отклонением, мы принимаем это сгенерированное число с вероятностью 0.2. А для этого, в свою очередь, генерируем еще одно случайное число от 0 до 1 с равномерным распределением, и, если сгенерировалось число меньше 0.2, то мы принимаем число 4 как успешное. Иначе повторяем сначала - генерируем еще одно число (например выпадает 3), для него находим вероятность (например, 0.3), для него генерируем еще число от 0 до 1 (например, 0.1) и тогда уже принимаем окончательно, что на этой итерации x_1=3. Далее необходимо повторить все действия выше с величиной x_2, причем x_1 мы уже используем "новое" - в нашем примере равное 3. Так, рассчитываем плотность вероятности p(x_2 | x_1=3,x_3=7), генерируем снова случайное число на роль кандидата нового значения x_2, делаем выборку с отклонением и повторяем её в случае, если значение "отклонено". Аналогично действия повторяются для x_3 с новыми значениями x_1 и x_2. Первая итерация алгоритма семплирования по Гиббсу завершена. Через несколько сотен/тысяч таких итераций случайные значения должны прийти к максимуму своей плотности, который может быть расположен достаточно далеко от нашего первого приближения X = \{5,2,7\} и семплироваться в той области. Дальнейшая тысяча итераций может уже использоваться по назначению (для поиска математического ожидания, например) как образец значений искомого распределения, не зависящих от первоначального вектора X = \{5,2,7\}.

Ссылки[править | править вики-текст]

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

Пример семплирования по Гиббсу двумерного нормального распределения

См. также[править | править вики-текст]