ПРИБЛИЖЕННЫЙ ВЕРОЯТНОСТНЫЙ ВЫВОД В БАЙЕСОВСКИХ СЕТЯХ
Исходя из того, что точный вероятностный вывод в больших многосвязных сетях является неосуществимым, важно предусмотреть методы приближенного вероятностного вывода. В настоящем разделе описаны рандомизированные алгоритмы выборки (называемые также алгоритмами Монте-Карло), обеспечивающие получение приближенных ответов, точность которых зависит от количества сформированных выборок. В последние годы алгоритмы Монте-Карло нашли широкое распространение в компьютерных науках для получения оценочных значений величин, которые трудно вычислить точно. Например, алгоритм эмуляции отжига, описанный в главе 4, представляет собой метод Монте-Карло для задач оптимизации. В этом разделе нас интересует применение методов выборки для вычисления апостериорных вероятностей. Здесь описаны два семейства алгоритмов: непосредственная выборка и выборка с помощью цепи Маркова. Два других подхода (вариационные методы и метод циклического распространения) упоминаются в библиографических и исторических заметках, приведенных в конце данной главы.
Методы непосредственной выборки
Примитивной операцией в любом алгоритме выборки является формирование выборок из известного распределения вероятностей. Например, подлинная монета может рассматриваться как случайная переменная Coin со значениями
В процессе случайного формирования выборки простейшего типа для байесовских сетей, рассматриваемом в этом разделе, вырабатываются события, не имеющие связанных с ними свидетельств, которые могут быть зарегистрированы в сети. Идея этого метода состоит в том, что выборка должна формироваться последовательно по каждой переменной, в топологическом порядке. Распределение вероятностей, из которого берется выборка значения, обусловливается значениями, уже присвоенными родительским переменным этой переменной. Соответствующий алгоритм приведен в листинге 14.3. Проиллюстрируем его работу на примере сети, приведенной на рис. 14.9, а, предполагая, что имеет место упорядочение [Cloudy, Sprinkler, Rain, WetGrass], как описано ниже.
Листинг 14.3. Алгоритм формирования выборки, который вырабатывает события на основании байесовской сети
function Prior-Sample(bn) returns событие, выработанное путем применения операции формирования выборки к априорному распределению, заданному в виде сети Ьп inputs: Ьп, байесовская сеть, задающая совместное распределение P(Xi,...,Xn)
х <— событие с п элементами for i = 1 to п do
xi <— случайная выборка из Р (Xi\parents (Xi) ) return x
1. Выборка из распределения Р (Cloudy) =<0 . 5 , 0 . 5>; предположим, что она возвращает true.
2. Выборка из распределения Р (Sprinkler | Cloudy true) =<0 .1, 0 . 9>; предположим, что она возвращает false.
3. Выборка из распределения Р {Rain | Cloudy true) =<0 . 8 , 0 . 2>; предположим, что она возвращает true.
4. Выборка из распределения В (WetGrass \ Sprinklerfalse, Rain= true) =<0 . 9, 0 . 1>; предположим, что она возвращает true.
В данном случае алгоритм Prior-Sample возвращает событие [ true, false, true, true].
Можно легко показать, что алгоритм Prior-Sample формирует выборки на основе априорного совместного распределения, которое задано рассматриваемой сетью. Прежде всего предположим, что SPS(xi,..., хп) представляет собой вероятность того, что конкретное событие сформировано алгоритмом Prior-Sample. Достаточно лишь проанализировать сам процесс формирования выборки, чтобы убедиться в справедливости следующего соотношения, поскольку каждый этап формирования выборки зависит только от значений родительских переменных:
п
SpS(xi...xn) = J~J P(xi \parents(Xi) ) i = l
Это выражение должно показаться читателю весьма знакомым, поскольку оно определяет также вероятность события в соответствии с представлением совместного распределения в байесовской сети, как указано в уравнении 14.1. Поэтому получаем следующее:
Sps(xi...xn) = P(Xi...Xn)
Благодаря такому простому факту задача получения ответов на вопросы с помощью выборок решается очень просто.
В любом алгоритме формирования выборки ответы вычисляются путем подсчета фактически сформированных выборок. Предположим, что общее количество выборок равно N, а также допустим, что N(xlf ...,хп) — частота конкретного события х1,..., хп. Следует полагать, что эта частота сойдется в пределе к ее ожидаемому значению, соответствующему вероятности сформированной выборки:
п • Nps(xlf ... , Хп) f 1Л А л.
lim -- = SpS(xi, ...,хп) = P(xi,...,xn) (14.4)
Например, рассмотрим событие, полученное ранее: [ true, false, true, true]. Вероятность формирования выборки для этого события такова:
SPS (true,false, true, true) = 0.5x0.9x0.8x0.9 = 0.324
Поэтому следует полагать, что в пределе, при очень больших значениях N, около 32,4% выборок будут относиться к этому событию.
В последующем изложении мы будем использовать знак приближенного равенства (~) для обозначения соотношения, имеющего именно этот смысл, — что оцениваемая вероятность становится точной при больших пределах количества выборок. Такая оценка называется согласованной. Например, может быть получена согласованная оценка вероятности любого частично заданного события х1,..., хт, где т < п, следующим образом:
P(xi,...,xm) » NPS(xlt...,xm) /N (14.5)
Это означает, что вероятность события можно оценить с помощью деления количества выборок частично заданного события на количество всех событий, полученных в процессе формирования выборок. Например, если на основании сети с описанием опрыскивателя (см. рис. 14.9, а) сформирована 1000 выборок и для 511 из них справедливо выражение Rain=true, то оценка вероятности дождя, которая записывается какР {Rain= true), равна 0,511.