В этом разделе описан алгоритм Монте-Карло с применением цепи Маркова

(Markov chain Monte Carlo— MCMC), предназначенный для вероятностного вывода в байесовских сетях. Вначале опишем, какие действия выполняются в этом алгоритме, затем объясним, благодаря чему он работает и почему имеет такое сложное название.

Алгоритм МСМС

В отличие от других двух алгоритмов формирования выборок, которые вырабатывают каждое событие с нуля, в алгоритме МСМС каждое событие вырабатывается путем внесения случайного изменения в предыдущее событие. Поэтому сеть целесообразно рассматривать как находящуюся в конкретном текущем состоянии, заданном с помощью присваивания значения каждой переменной. Переход в следующее состояние осуществляется путем случайного формирования выборки значения для одной из переменных, отличных от переменных свидетельства, причем это значение обусловлено текущими значениями переменных в марковском покрытии переменной. (Напомним, что, как было сказано на с. 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].