Обоснование правильности работы алгоритма МСМС
В этом разделе будет показано, что алгоритм МСМС возвращает согласованные оценки для апостериорных вероятностей. Материал, изложенный в данном разделе, является весьма формальным, но основное утверждение в нем несложно: процесс формирования выборок переходит в "динамическое равновесие", в котором в конечном итоге доля времени, проведенного в каждом состоянии, точно пропорциональна апостериорной вероятности этого состояния. Такое замечательное свойство является следствием конкретной переходной вероятности, с которой данный процесс переходит из одного состояния в другое и которая определена условным распределением, заданным с учетом марковского покрытия переменной, для которой формируется выборка.
Предположим, что д(х->х' ) — вероятность того, что в этом процессе произойдет переход из состояния х в состояние х1. Эта переходная вероятность определяет информационную структуру, заданную на пространстве состояний, которая называется цепью Маркова. (Цепи Маркова играют также важную роль в главах 15 и 17.) Теперь предположим, что мы развернули цепь Маркова на t этапов, и допустим, что 7it (х) — вероятность того, что система находится в состоянии х во время t. Аналогичным образом, допустим, что nt+1 (х' ) — вероятность пребывания системы в состоянии х' во время t+1. Если дано значение 7it (х), то значение nt+1 (х1 ) можно рассчитать путем суммирования по всем состояниям, в которых система может находиться во время t, вероятностей пребывания в этом состоянии, умноженных на вероятности осуществления перехода в состояние х', следующим образом:
Цепь называется достигшей своего стационарного распределения (stationary distribution), если nt = nt+1. Назовем это стационарное распределение я; итак, его определяющим уравнением является следующее:
При некоторых стандартных допущениях7, касающихся распределения вероятностей перехода q, существует одно и только одно распределение п, удовлетворяющее этому уравнению при каждом конкретном значении q.
Уравнение 14.9 можно трактовать как утверждение, что в установившемся режиме ожидаемый "отток" из каждого состояния (т.е. его текущее "население") равен ожидаемому "притоку" из всех других состояний. Один из очевидных способов удовлетворения этого отношения состоит в достижении того, чтобы ожидаемый поток между любыми парами состояний был одинаковым в обоих направлениях. В этом состоит свойство детализированного равновесия, которое показано ниже.
ТЕ(Х) д(х—>х') = ТЕ(Х') д(х'—>х) для всех х, х1 (14.10)
Можно показать, что из этого свойства детализированного равновесия можно вывести свойство стационарности, получив суммы по х в уравнении 14.10. Получаем следующее соотношение:
ТЕ(Х) д(х-»х' ) = ТЕ(Х' ) д(х'-»х) = ТЕ(Х' ) д(х'—>х) = ТЕ(Х')
где возможен последний этап преобразования, поскольку гарантировано выполнение перехода из состояния х'.
Теперь мы покажем, что вероятность перехода д(х->х' ), определяемая на этапе формирования выборки в алгоритме МСМС-Ask, удовлетворяет уравнению детализированного равновесия со стационарным распределением, равным Р(х|е) (истинному апостериорному распределению по скрытым переменным). Мы проведем это доказательство в два этапа. Вначале определим цепь Маркова, в которой формирование выборки по каждой переменной обусловлено текущими значениями всех прочих переменных, и покажем, что это условие соответствует свойству детализированного равновесия. Затем мы просто констатируем, что для байесовских сетей формирование такой условной выборки эквивалентно условному формированию выборки по марковскому покрытию переменной (см. с. 1).
Допустим, что Xi — переменная, для которой должна быть сформирована выборка, и предположим, что — все скрытые переменные, отличные от XL. Их значениями в текущем состоянии являются Xi и Если будет выполнена выборка нового значения xL' для переменной xi9 обусловленного всеми прочими переменными, включая переменные свидетельства, то будет получено следующее:
д(х->х') = qr( (xi,Xi)-»(Xi ' ) = P(xi'|xi,e)
Это выражение для переходной вероятности называется формирователем выборок Гиббса (Gibbs sampler) и служит основой особенно удобной формы алгоритма МСМС. Теперь мы покажем, что формирователь выборок Гиббса находится в детализированном равновесии с истинной апостериорной вероятностью:
ТЕ(Х) g(x-x') = Р(х|е) P(xi'|x\,e) = P(xi, х\ | е) P(xL' | xi# е)
= P(xi |х\, е) P(xi I е) P(xi'|Xi,e) (использование цепного правила
после первого терма)
= P(xi |xi, е) P(xi1 ,xi I e) (использование цепного правила для
перехода в обратном направлении)
= 7Е(х' ) д(х'—>х)
Как указано на с. 1, переменная независима от всех других переменных, если дано ее марковское покрытие, поэтому имеет место следующее соотношение:
P(xi' |xi,e) = P(xi' \mb(Xi) )
где mb{Xi) обозначает значения переменных в марковском покрытии xi5 MB {Xi). Как показано в упр. 14.10, вероятность переменной, если дано ее марковское покрытие, пропорциональна вероятности переменной, если даны ее родительские переменные, умноженной на вероятность каждой дочерней переменной, если даны ее соответствующие родительские переменные:
P(xi' \mb{Xi) ) =
a P(xi' \parents(Xi) ) х J~J Р(у-> |parents(Yj) ) (14.11)
YjGChildrenfXi)
Поэтому для изменения значения каждой переменной xL необходимо выполнить такое количество операций умножения, которое равно количеству дочерних переменных переменной XL.
В этом разделе рассматривался только один простой вариант алгоритма МСМС — вариант, основанный на использовании формирователя выборок Гиббса.
В своей наиболее общей форме алгоритм МСМС представляет собой мощный метод вычислений с помощью вероятностных моделей, поэтому было разработано много вариантов этого алгоритма, включая алгоритм эмуляции отжига (см. главу 4), алгоритмы стохастической выполнимости (см. главу 7) и формирователь выборок Мет-рополиса— Гастингса, рассматриваемый в главе 15.
В главе 8 описывалось, какими преимуществами с точки зрения возможностей представления обладает логика первого порядка по сравнению с пропозициональной логикой. В логике первого порядка учитывается существование объектов и отношений между ними, и она позволяет выражать факты о некоторых или обо всех объектах в проблемной области. Это часто приводит к созданию представлений, намного более кратких, чем эквивалентные пропозициональные описания. Теперь отметим, что байесовские сети по существу являются пропозициональными: множество переменных в них является фиксированным и конечным, а каждая переменная имеет постоянную область определения, состоящую из возможных значений. В связи с этим применимость байесовских сетей становится ограниченной. Если бы можно было найти способ применения теории вероятностей в сочетании с выразительными возможностями представлений в логике первого порядка, то можно было бы рассчитывать на существенное расширение спектра задач, решаемых таким образом.
Основная идея, которая может привести к достижению этой цели, состоит в следующем: в пропозициональном контексте байесовская сеть задает распределения вероятностей по атомарным событиям, каждое из которых определяет значение для каждой переменной в сети. Таким образом, атомарное событие является моделью, или одним из возможных миров, в терминологии пропозициональной логики. А в контексте логики первого порядка модель (с ее интерпретацией) задает область определения объектов, отношения, которые имеют место между этими объектами, и отображения из констант и предикатов базы знаний в объекты и отношения модели. Поэтому вероятностная база знаний первого порядка должна задавать вероятности для всех возможных моделей первого порядка. Допустим, что \х(м) — вероятность, присвоенная модели Мс помощью базы знаний. Для каждого высказывания в логике первого порядка ф вероятность Р(ф) задается обычным образом, путем суммирования по всем возможным мирам, где высказывание ф является истинным:
Р(ф) = Ц(М) (14.12)
М:ф является истинным в М
До сих пор все, казалось бы, шло хорошо. Тем не менее есть одна проблема: множество моделей первого порядка является бесконечным. Это означает, что, во-первых, суммирование может быть неосуществимым, и, во-вторых, задача определения полного, согласованного распределения на бесконечном множестве миров может оказаться очень трудной.