Вероятностный вывод по методу моделирования цепи Маркова
В этом разделе описан алгоритм Монте-Карло с применением цепи Маркова (Markov chain Monte Carlo — MCMC), предназначенный для вероятностного вывода в байесовских сетях. Вначале опишем, какие действия выполняются в этом алгоритме, затем объясним, благодаря чему он работает и почему имеет такое сложное название.
Алгоритм МСМС
В отличие от других двух алгоритмов формирования выборок, которые вырабатывают каждое событие с нуля, в алгоритме МСМС каждое событие вырабатывается путем внесения случайного изменения в предыдущее событие. Поэтому сеть целесообразно рассматривать как находящуюся в конкретном текущем состоянии, заданном с помощью присваивания значения каждой переменной. Переход в следующее состояние осуществляется путем случайного формирования выборки значения для одной из переменных xL, отличных от переменных свидетельства, причем это значение обусловлено текущими значениями переменных в марковском покрытии переменной х (Напомним, что, как было сказано на с. 1, марковское покрытие переменной состоит из ее родительских переменных, дочерних переменных и родительских переменных дочерних переменных.) Поэтому в алгоритме МСМС предусмотрено случайное блуждание по пространству состояний (пространству возможных полных присваиваний), в котором каждый раз изменяется значение одной переменной, но значения переменных свидетельства остаются зафиксированными.
Рассмотрим запрос Р {Rain | Sprinkler= true, WetGrass= true), примененный к сети, которая показана на рис. 14.9, а. Для переменных свидетельства Sprinkler и WetGrass зафиксированы их наблюдаемые значения, а скрытые переменные Cloudy и Rain инициализированы случайным образом; допустим, что им присвоены значения true и false соответственно. Таким образом, начальным состоянием является [ true, true, false, true]. После этого повторно выполняются описанные ниже этапы.
1. Формируется выборка для переменной Cloudy с учетом текущих значений переменных марковского покрытия: в данном случае выборка берется из Р (Cloudy \ Sprinkler=true, Rain= false). (Вскоре мы покажем, как рассчитать это распределение.) Предположим, что результатом является Cloudy= false. В таком случае новым текущим состоянием становится [false, true, false, true].
2. Формируется выборка для переменной Rain с учетом текущих значений переменных марковского покрытия: в данном случае выборка берется из P(Rain\ Cloudy= false, Sprinkler=true, WetGrass= true). Предположим, что эта операция приводит к получению Rain=true. Новым текущим состоянием становится [false, true, true, true].
Каждое состояние в пространстве состояний, посещенное в ходе этого процесса, представляет собой выборку, которая вносит свой вклад в оценку вероятности переменной запроса Rain. Если в данном процессе посещаются 20 состояний, в которых переменная Rain принимает истинное значение, и 60 состояний, в которых переменная Rain становится ложной, то ответом на запрос становится Normalize (<20 , 60>) =<0 .25,0. 75>. Полный алгоритм показан в листинге 14.6.
Листинг 14.6. Алгоритм МСМС приближенного вероятностного вывода в байесовских сетях
function MCMC-Ask(X, е, bn, N) returns оценка значения Р{Х\е) local variables: N[X], вектор результатов подсчетов по X,
первоначально равный нулю Z, переменные в сети bn, отличные от переменных
свидетельства х, текущее состояние сети, первоначально скопированное из е
инициализировать х случайными значениями переменных из Z for j = 1 to N do
for each Zi in Z do
выполнить выборку значения переменной Zi в векторе х
из Р (Zi |mb{Zi) ) , если даны значения MB(Zi) в векторе х N[x] <— N[x]+1, где х представляет собой значение переменной X в множестве х return Normalize(N[X])