Например, Бобцов

ПРЕОБРАЗОВАНИЕ АЦИКЛИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ ДОВЕРИЯ В АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ

Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети 21
УДК 004.8
А. Л. ТУЛУПЬЕВ
ПРЕОБРАЗОВАНИЕ АЦИКЛИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ ДОВЕРИЯ В АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ
Приведены основные шаги в схеме алгоритма по преобразованию баз фрагментов знаний с неопределенностью, представленных в формате ациклических байесовских сетей доверия (т.е. со структурой полидерева), в базы фрагментов знаний, представленных в формате алгебраических байесовских сетей. Преобразование осуществляется путем последовательного расчета тензоров совместной вероятности на основе тензоров условной вероятности, хранящихся в узлах байесовской сети доверия. Процесс завершается переходом от тензоров совместной вероятности к оценкам вероятности на идеалах конъюнктов. Ключевые слова: байесовские сети, вероятностная семантика, модели знаний с неопределенностью, логико-вероятностный вывод.
Одним из видов генерации новых знаний в условиях неопределенности по сведениям, уже накопленным в базах фрагментов знаний (БФЗ) интеллектуальных информационных систем, является логико-вероятностный вывод. Его алгоритмический аппарат особенно хорошо развит для байесовских сетей доверия (БСД) [1], однако такие сети имеют существенные
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 3

22 А. Л. Тулупьев

ограничения, касающиеся как их структуры, так и вида оценок вероятностей, в них использующихся. В стадии разработки находится теория алгебраических байесовских сетей (АБС) [2, 3], позволяющая справиться с частью тех ситуаций, которые невозможно обработать в байесовских сетях доверия [3].
Для того чтобы достижения в теории АБС можно было применить в базах фрагментов знаний, которые построены на основе байесовских сетей доверия, необходимо разработать алгоритмы преобразования БСД в АБС. Цель настоящей статьи — описание схемы такого алгоритма для случая байесовской сети доверия без циклов (структура такой сети имеет вид полидерева [1]). Предварительно введем определения двух названных типов байесовских сетей (в рамках логико-вероятностного подхода [3]), используя терминологию и обозначения, принятые в работе [2]. Основы применяемых теорий и свойства объектов, упоминаемых в настоящей статье, детально представлены в монографии [3].
Байесовская сеть доверия — это ациклический направленный граф с тензорами услов-
ных вероятностей вида p ( z | x1...xm ) в узлах. В узлах, не имеющих родителей, эти тензоры
условных вероятностей вырождаются в тензоры совместных (или маргинальных) вероятно-
стей вида p ( z ) . Если в БСД со структурой полидерева для некоторого узла z известны веро-

ятности его узлов-родителей p ( x1 ), ..., p ( xm ) , то можно вычислить совместные вероятности

вида

m
p ( zx1...xm ) = p ( z | x1...xm ) p ( x1...xm ) = p ( z | x1...xm )∏ p ( xi ). i=1
Последний переход возможен в силу определения байесовской сети и с учетом того, что

между узлами x1, ..., xm нет путей, кроме пути, проходящего через z. Отсутствие таких путей

объясняется тем, что рассматриваемая БСД обладает структурой полидерева [1]. Также мож-

но вычислить и вероятность вида

m

p ( z ) = ∑ p ( z | x1...xm ) p ( x1...xm ) = ∑ p ( z | x1...xm )∏ p ( xi ).

x1...xm

x1...xm

i=1

Эта формула позволяет распространить процесс дальше по направленным ребрам поли-

дерева и рассчитывать соответствующие совместные вероятности для каждого узла БСД.

Алгебраическая байесовская сеть — это набор идеалов конъюнктов, которым приписана

оценка вероятности [2]. Напомним, что идеал конъюнктов — это множество всех подцепочек

некоторой заданной цепочки конъюнкций. Например, для заданной цепочки конъюнкций

zx1x2 идеал конъюнктов будет содержать пустой конъюнкт и конъюнкты z, x1, zx1, x2 , zx2 ,

x1x2 , zx1x2 , zx1x2 . Идеал конъюнктов с оценками вероятности их истинности называется

фрагментом знаний.

В первую очередь, заметим, что по вероятностям вида p ( zx1...xm ) можно рассчитать ве-

роятности всех конъюнктов, образованных над цепочкой zx1...xm . Таким образом, узел z бай-

есовской сети доверия будет сопоставлен с фрагментом знаний алгебраической байесовской

сети, образованным над утверждением z из самого узла и утверждениями x1, ..., xm из узлов-

предков. Полученный фрагмент знаний окажется связанным по отдельности с каждым фраг-

ментом знаний, приписанным узлу-родителю. При этом рассматриваемый фрагмент знаний и

фрагмент знаний из узла-родителя будут иметь лишь один общий элемент, и он будет из

множества x1, ..., xm . Следовательно, по исходной байесовской сети доверия будет получен

набор фрагментов знаний, обладающий структурой, которая является ненаправленным дере-

вом, а значит, будет сформирована ациклическая алгебраическая байесовская сеть.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 3

Динамические системы с переменной структурой и размерностью

23

СПИСОК ЛИТЕРАТУРЫ

1. Pearl J. Probabilistic Reasoning in Intelligent Systems. N.Y.: Morgan Kaufmann Publ., 1988. 552 p.

2. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Изв. вузов. Приборостроение. 2006. Т. 49, № 7. С. 20—26.

3. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.

Александр Львович Тулупьев

Сведения об авторе — канд. физ.-мат. наук, доцент; Санкт-Петербургский институт инфор-
матики и автоматизации РАН, лаборатория прикладной информатики; E-mail: alt@iias.spb.su

Рекомендована кафедрой технологий программирования СПбГУ ИТМО

Поступила в редакцию 15.02.08 г.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 3