Главная arrow книги arrow Копия Глава 14. Вероятностные рассуждения arrow Вероятностный вывод с помощью перебора
Вероятностный вывод с помощью перебора

Как говорилось в главе 13, любую условную вероятность можно вычислить, суммируя элементы из полного совместного распределения. Более конкретно следует указать, что ответ на запрос Р(х|е) можно получить с использованием уравнения 13.6, которое мы повторяем здесь для удобства:

Итак, любая байесовская сеть создает исчерпывающее представление полного совместного распределения. А именно, в уравнении 14.1 показано, что термы Р(х,е,у) в совместном распределении можно записать в виде произведений условных вероятностей, взятых из сети. Поэтому на любой запрос можно найти ответ с помощью байесовской сети, вычисляя суммы произведений условных вероятностей из этой сети.

В листинге 13.2 был приведен алгоритм Enumerate-Joint-Ask, обеспечивающий вероятностный вывод путем перебора элементов полного совместного распределения, который принимает на входе полное совместное распределение Ρ и выполняет в нем поиск значений. Этот алгоритм несложно модифицировать так, чтобы он принимал на входе байесовскую сеть bп и "отыскивал" элементы совместного распределения, умножая соответствующие элементы таблиц СРТ, взятые из сети bп.

Рассмотрим запрос Скрытыми переменными для этого запроса являются Earthquake и Alarm. Из уравнения 13.6, используя начальные символы имен переменных для сокращения длины выражений, можно получить следующее5:

В таком случае выражение в терминах элементов таблицы СРТ может быть получено с учетом семантики байесовских сетей (уравнение 14.1). Для упрощения получим соответствующее выражение только для случая Burglary = true:

Для вычисления этого выражения необходимо сложить четыре терма, каждый из которых вычисляется путем умножения пяти чисел. В наихудшем случае, когда приходится находить сумму почти по всем переменным, сложность этого алгоритма для сети с η булевыми переменными равна

Некоторое упрощение может быть достигнуто на основе следующих простых наблюдений: терм Р(b) представляет собой константу и может быть перенесен за пределы выражений суммирования по а и е, а терм Р(е) — перенесен за пределы выражения суммирования по а. Поэтому получаем следующее:

(14.3)