ТОЧНЫЙ ВЕРОЯТНОСТНЫЙ ВЫВОД В БАЙЕСОВСКИХ СЕТЯХ
Вероятностный вывод с помощью перебора
Как говорилось в главе 13, любую условную вероятность можно вычислить, суммируя элементы из полного совместного распределения. Более конкретно следует указать, что ответ на запрос Р(х|е) можно получить с использованием уравнения 13.6, которое мы повторяем здесь для удобства:
Р(х|е) = а Р(Х,е) = а Р(Х,е,у)
у
Итак, любая байесовская сеть создает исчерпывающее представление полного совместного распределения. А именно, в уравнении 14.1 показано, что термы Р(х,е,у) в совместном распределении можно записать в виде произведений условных вероятностей, взятых из сети. Поэтому & на любой запрос можно найти ответ с помощью байесовской сети, вычисляя суммы произведений условных вероятностей из этой сети.
В листинге 13.2 был приведен алгоритм Enumerate-Joint-Ask, обеспечивающий вероятностный вывод путем перебора элементов полного совместного распределения, который принимает на входе полное совместное распределение Р и выполняет в нем поиск значений. Этот алгоритм несложно модифицировать так, чтобы он принимал на входе байесовскую сеть Ьп и "отыскивал" элементы совместного распределения, умножая соответствующие элементы таблиц СРТ, взятые из сети Ьп.
Рассмотрим запрос Р [Burglary] JohnCalls=true, MaryCalls= true). Скрытыми переменными для этого запроса являются Earthquake и Alarm. Из уравнения 13.6, используя начальные символы имен переменных для сокращения длины выражений, можно получить следующее:
В таком случае выражение в терминах элементов таблицы СРТ может быть получено с учетом семантики байесовских сетей (уравнение 14.1). Для упрощения получим соответствующее выражение только для случая Burglary = true:
Для вычисления этого выражения необходимо сложить четыре терма, каждый из которых вычисляется путем умножения пяти чисел. В наихудшем случае, когда приходится находить сумму почти по всем переменным, сложность этого алгоритма для сети с п булевыми переменными равна 0(п2п).
Некоторое упрощение может быть достигнуто на основе следующих простых наблюдений: терм Р(Ь) представляет собой константу и может быть перенесен за пределы выражений суммирования по а и е, а терм Р(е) — перенесен за пределы выражения суммирования по а. Поэтому получаем следующее:
P(b\j,m) = а Р(Ь)Г Р(е) P(a\b,e)P(j\a)P(m\a) (14.3)
е a
Это выражение можно вычислить, последовательно обрабатывая в цикле его переменные и перемножая в ходе этого элементы таблицы СРТ. При каждом суммировании необходимо также выполнить цикл по возможным значениям переменной. Структура этих вычислений показана на рис. 14.8. Используя числа, приведенные на рис. 14.2, получим выражение Р(Ь| j,m) =ахО . 00059224. Соответствующее вычисление для -ib приводит к получению выражения осхО .0014919, поэтому имеет место следующее:
P(B\j,m) = а <0.00059224,0.0014919> « <0.284,0.71б>
Таким образом, вероятность взлома, при условии, что поступили звонки от обоих соседей, составляет около 28%.
Процесс вычисления выражения, приведенного в уравнении 14.3, показан в виде дерева синтаксического анализа выражения на рис. 14.8. В алгоритме Enumeration-Ask, приведенном в листинге 14.1, вычисление подобных деревьев осуществляется с использованием рекурсии в глубину. Таким образом, пространственная сложность алгоритма Enumeration-Ask зависит от количества переменных только линейно; по сути этот алгоритм вычисляет суммы по полному совместному распределению, даже не формируя его явно. К сожалению, его временная сложность для сети с п булевыми переменными всегда составляет 0(2П); это лучше по сравнению с оценкой 0{п2п) для простого подхода, описанного выше, но все еще довольно велика. В отношении дерева, приведенного на рис. 14.8, необходимо сделать еще одно замечание — в нем явно показаны повторяющиеся подвыражения, вычисляемые с помощью этого алгоритма. Произведения P{j\a)P{m\a) и Р(j | -.а) Р(т| -.а) вычисляются дважды, по одному для каждого значения е. В следующем разделе описан общий метод, позволяющий избежать таких избыточных вычислений.
Листинг 14.1. Алгоритм перебора для получения ответов на запросы в байесовских сетях
function Enumeration-Ask(X, е, bn) returns распределение по X inputs: X, переменная запроса
е, наблюдаемые значения переменных Е Ьп, байесовская сеть с переменными
{X} и Е и У} /* У - скрытые переменные */
Q{X) <— распределение по X, первоначально пустое for each значение xi переменной X do
дополнить е значением xi переменной X
Q(xi) <— Enumerate-All(Vars[bn], e) return Normalize(Q{X) )
function Enumerate-All(vars, e) returns действительное число if Empty?(vars) then return 1.0
Y <— First(vars)
if переменная Y имеет значение у в множестве е
then return P{y\parents{Y) ) XEnumerate-All (Rest (vars) , e) else return j P {y\ parents (Y) )xEnumerate-All (Rest (vars) , ey)
где ey представляет собой множество e, дополненное значением Y = у