2.    Формируется выборка для переменной Rain с учетом текущих значений переменных марковского покрытия: в данном случае выборка берется из P(Rain| Cloudy=false, Sprinkler=true, WetGrass= true). Предположим, что эта операция приводит к получению Rain=true. Новым текущим состоянием становится [false, true, true, true].

Каждое состояние в пространстве состояний, посещенное в ходе этого процесса, представляет собой выборку, которая вносит свой вклад в оценку вероятности переменной запроса Rain. Если в данном процессе посещаются 20 состояний, в которых переменная Rain принимает истинное значение, и 60 состояний, в которых переменная Rain становится ложной, то ответом на запрос становится . Полный алгоритм показан в листинге 14.6.

Листинг 14.6. Алгоритм МСМС приближенного вероятностного вывода в байесовских сетях

Обоснование правильности работы алгоритма МСМС

В этом разделе будет показано, что алгоритм МСМС возвращает согласованные оценки для апостериорных вероятностей. Материал, изложенный в данном разделе, является весьма формальным, но основное утверждение в нем несложно: ^ процесс формирования выборок переходит в "динамическое равновесие", в котором в конечном итоге доля времени, проведенного в каждом состоянии, точно пропорциональна апостериорной вероятности этого состояния. Такое замечательное свойство является следствием конкретной переходной вероятности, с которой данный процесс переходит из одного состояния в другое и которая определена условным распределением, заданным с учетом марковского покрытия переменной, для которой формируется выборка.