Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Синтез вторичной структуры алгебраической байесовской сети: компромисс между сложностью и ацикличностью Работа выполнена при финансовой поддержке РФФИ, гранты № 12-01-00945-a, 12-01-31202-мол_а.

Фильченков А.А.

Аннотация

Ацикличность вторичной структуры алгебраической байесовской сети является необходимым требованием для осуществления алгоритмов логико-вероятностного вывода, однако при достижении возможности построить такую вторичную структуру возрастает и сложность осуществления алгоритмов.

В работе предлагается компромисс, который может быть достигнут между требованием ацикличности и ростом сложности алгоритмов логико-вероятностного вывода.

Введение

Алгебраическая байесовская сеть (АБС) -- это логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью [6, 7]. Другими словами, алгебраическая байесовская сеть, как и любая другая вероятностная графическая модель, декомпозирует многомерный случайный элемент [13] на совокупность случайных элементов меньшей размерности, причем задаваемые ими распределения вероятности за счет предположений условной независимости позволяют выразить случайное распределение исходного многомерного случайного элемента [8, 16]. Отличие АБС от других вероятностных графических моделей состоит в том, что они позволяют работать также и с интервальными оценками вероятности. В этом случае приходится говорить уже не просто о случайных элементах, а о семействах случайных элементов, поскольку интервальные оценки соотносятся с семейством вероятностных распределений.

Важную роль играет «топология» сети, т.е. граф, связывающий случайные элементы и отображающий условные независимости. В теории АБС такой граф называется ее вторичной структурой. Для поддержания целого ряда алгоритмов такой сети ее вторичная структура должна быть ациклична [4, 5]. Однако ацикличную вторичную структуру можно построить не над любой совокупностью случайных элементов, которые составляют первичную структуру АБС -- такие первичные структуры называются цикличными [10]. Известны алгоритмы, которые позволяют преобразовывать цикличную первичную структуру АБС к ацикличной, однако их применение приводит к росту размерности случайных элементов. От размерности случайного элемента (в случае интервальных оценок размерности всех случайных элементов из семейства совпадают) экспоненциально зависит сложность работы в том числе и тех алгоритмов, ради которых требуется ацикличность вторичной структуры [3] -- алгоритмов глобального логико-вероятностного вывода. Соответственно, требования ацикличности вторичной структуры и ограничения сложности работы алгоритмов логико-вероятностного вывод не могут быть удовлетворены.

В работе будет предложен компромисс, между двумя этими требованиями.

Первичная и вторичная структуры алгебраической байесовской сети

Вместо того, чтобы рассматривать случайные элементы (или семейства таких элементов), достаточно будет рассуждать лишь (упрощенно) о наборах переменных (в случае АБС речь идет об атомарных пропозициональных формулах), над которыми они построены На самом деле речь идет не «переменных», поскольку АБС использует логико-вероятностных подход и вероятности задаются над пропозициональными формулами, однако для формализации этого пояснения потребовалось ввести целую систему понятий, приведенную, например, в [6]..

Пусть задан некоторый алфавит Первичной структуре АБС будем сопоставлять набор подмножеств (подалфавитов) этого множества где -- некоторое подмножество множества индексов подалфавитов , причем элементы этого набора не поглощают друг друга и вместе покрывают

Набору подалфавитов соответствует гиперграф [1, 14] вершинами которого являются элементы а ребрами -- элементы Такой гипеграф является минимальным -- каждая его вершина входит в какое-либо ребро, каждое ребро содержит какую-либо вершин и не содержит никакое другое ребро.

Теперь рассмотрим ненаправленный граф, в котором каждой вершине приписан подалфавит из Подалфавит, соответствующий вершине, будем называть ее нагрузкой. Сепаратором двух вершин называется пересечение их нагрузок. Две вершины называются сочлененными, если их сепаратор непуст. Графом смежности называется граф, в котором каждое ребро проведено между сочлененными вершинами и между каждой парой сочлененных вершин существует путь (называемый магистральным путем), в котором нагрузка каждой вершин содержит сепаратор его концов. Вторичной структурой АБС может выступать только граф смежности [11].

Вторичная структура требуется в частности для осуществления глобального логико-вероятностного апостериорного вывода, который заключается в распространении влияния поступившего в сеть свидетельства [7] (т.е. последовательного осуществления апостериорного логико-вероятностного вывода). При этом сложность распространения влияния свидетельства (его пропагации) в каждый узел экспоненциально зависит от размера этого узла [3].

Преобразование первичной структуры алгебраической байесовской сети к ацикличной

Гиперграф называется ацикличным, если для него существует ацикличный граф смежности [15].

Первичным графом гипеграфа называется граф, в котором множество вершин совпадает с множеством вершин гиперграфа и две вершины соединены ребром тогда и только тогда, когда они входят в какое-либо ребро гиперграфа. Первичный граф гиперграфа, соответствующего первичной структуре АБС, называется ее протоструктурой.

Цикл в графе называется простым, если в нем нет хорд, т.е. ребер между несмежными по циклу вершинами. Граф называется хордальным, если в нем нет простых циклов длины больше трех. Максимальным кликами графа называется максимальные по включению полный подграфы графа. Гиперграф называется конформным, если множество его ребер совпадает с множеством вершин максимальных клик его первичного графа. Гиперграф называется хордальным, если хордален его первичный граф.

Теорема [15]. Гиперграф ацикличен тогда и только тогда, когда он гиперграф конформен и хордален.

Для преобразования первичной АБС структуры к ацикличной необходимо последовательно триангулировать протоструктуру, то есть за счет добавления ребер устранить все простые циклы длины больше трех, а затем из множеств вершин, входящих в максимальные клики полученной протоструктуры, построить подалфавиты, которые составляют новую первичную структуры АБС. Такая первичная структура по построению будет ациклична. ацикличность алгебраическая байесовская сеть

Поскольку триангуляция осуществляется за счет добавления ребер, размер максимальных клик может увеличиться, причем неограниченно. Соответственно, максимальный размер максимальной клики также может увеличить, причем неограниченно. Поскольку размер максимальной клики равен размеру подалфавита, то он определяет размерность случайного элемента из первичной структуры.

Цикличность первичной структуре алгебраической байесовской сети

В предыдущем разделе было показано, что преобразование первичной структуры к ацикличной ведет к росту сложности алгоритмов логико-вероятностного вывода, поэтому допустимо не всегда. Соответственно, возникает потребность в работе с циклической первичной структурой, для которой пока не существует алгоритмов пропагации свидетельств по сети.

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

Соответственно, актуальным является вопрос о построении вторичной структуры такой сети, и он решается за счет построения минимальных по числу ребер графов смежности. По определению такие графы можно построить над любой первичной структурой АБС, и было показано, что множество таких графов совпадает с множеством деревьев смежности в случае ацикличности первичной структуры АБС [10]. Также были предложены алгоритмы синтеза таких графов [2, 9]

Таким образом, компромисс между ацикличностью и связностью может быть найден в фиксации верхней границы размера элементов первичной структуры и устранением некоторых циклов из первичной структуры таким образом, чтобы размер элементов первичной структуры не превысил зафиксированный. Затем над преобразованной первичной структурой следует в качестве вторичной структуры построить минимальный граф смежности.

В работе [12] были описаны методы устранения циклов, которые основаны на последовательном добавлении к первичной структуре новых элементов, которые устраняют особые циклы -- небратские полусиблинговые простые циклы. Метод позволяет устранить все циклы из первичной структуры. Если учесть ограничение на размер элемента, то можно добавлять лишь те элементы, размер которых не превосходит установленный. Таким образом, задача при поставленном ограничении будет решена.

Заключение

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

В работе был предложен подход, основанный на устранении лишь на устранении лишь некоторого числа циклов таким образом, чтобы размер элементов первичной структуры АБС не превысил зафиксированный, и последующим построением минимального по числу ребер графа смежности.

Литература

1. Зыков А.А. Гиперграфы // Успехи математических наук. 1974. № 6 (180). C. 86-154.

2. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 11. С. 142-157.

3. Сироткин А. В. Вычислительная сожность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 3(18). С. 188-214.

4. Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57-93.

5. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений).

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

7. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.

8. Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254-295.

9. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104-127.

10. Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. C. 110-119.

11. Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 65-74.

12. Фроленков К.В., Фильченков А.А. Методы устранения циклов вторичной структуры алгебраической байесовской сети // «Гибридные и синергетические интеллектуальные системы: теория и практика» (29 июня - 2 июля 2012 г., Калининград). Материалы 1-го международного симпозиума. Т. 2. Калининград: БФУ им. Канта.2012. С. 282-292.

13. Ширяев А.Н. Вероятность. М.: Наука, 1989. 640 с.

14. Щербина О.А. Локальные алгоритмы и древовидная декомпозиция для задач дискретной оптимизации) // Динамические системы: межвед. науч. сб. ТНУ, 2006. Вып. 20. С. 89-103.

15. Beeri C., Fagin R., Maier D., Yannakakis M. On the Desirability of Acyclic Database Schemes // Journal of the ACM. 1983. Vol. 30, iss. 3. P. 479-513.

16. Daphne Koller, Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. Cambridge: The MIT Press. 2009.

Размещено на Allbest.ru