Я. Гудфеллоу, И. Бенджио, А. Курвилль

500 

 
Методы Монте-Карло
ческий. Чтобы произвести 
предковую выборку
, мы просто выбираем значение каждой 
случайной величины в порядке топологической сортировки при условии ее родите-
лей, для которых выборка уже гарантированно произведена (см. раздел 16.3). Пред-
ковая выборка определяет эффективный однопроходный метод получения выборки.
В энергетической модели порочный круг можно разорвать посредством выборки 
с применением марковской цепи. Основная идея марковской цепи – взять состояние 
x
, начинающееся с произвольного значения. С течением времени мы случайным об-
разом изменяем 
x
. В конечном итоге 
x
приближается к истинной выборке из 
p
(
x
). 
Формально говоря, марковская цепь определяется случайным состоянием 
x
и пере-
ходным распределением 
T
(
x
′
| 
x
), задающим вероятность того, что случайное из-
менение переведет состояние 
x
в состояние 
x
′
. Под выполнением марковской цепи 
понимается многократный переход из состояния 
x
в состояние 
x
′
в соответствии 
с распределением 
T
(
x
′
| 
x
).
Для теоретического осмысления принципов работы MCMC-методов полезно бу-
дет перепараметризовать задачу. Сначала сосредоточимся на случае, когда множество 
состояний случайной величины 
x
счетно. Тогда любое состояние можно представить 
целым положительным числом 
x
. Различные целые значения 
x
можно затем отобра-
зить на различные значения 
x
в исходной задаче.
Посмотрим, что произойдет, если параллельно выполнять бесконечно много мар-
ковских цепей. Все состояния марковских цепей выбираются из некоторого распре-
деления 
q
(
t
)
(
x
), где 
t
– число уже произведенных шагов. В начальный момент 
q
(0)
– не-
которое распределение, которое мы использовали для произвольной инициализации 
x
для каждой марковской цепи. Затем на 
q
(
t
)
оказывают влияние все уже произведен-
ные шаги марковской цепи. Наша цель – добиться, чтобы 
q
(
t
)
(
x
) сходилось к 
p
(
x
).
Поскольку мы перепараметризовали задачу в терминах целого положительного 
x
, 
то можем описать распределение вероятности 
q
с помощью вектора 
v
– такого, что
q
(x = 
i
) = 
v
i
.
 
(17.17)
Посмотрим, что происходит, когда состояние 
x
одной марковской цепи изменяется 
на 
x
′
. Вероятность, что новым состоянием будет 
x
′
, равна
 
(17.18)
Пользуясь целочисленной параметризацией, мы можем представить действие опе-
ратора перехода 
T
с помощью матрицы