ПРЕОБРАЗОВАНИЕ АЦИКЛИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ ДОВЕРИЯ В АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ
Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети 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
УДК 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