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

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

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

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

Аннотация

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

Введение

Алгебраические байесовские сети (АБС) относятся к классу логико-вероятностных графических моделей [11, 19] и используются для представления сложных систем знаний с неопределенностью. Узлами алгебраической байесовской сети [2, 3] выступают сложные случайные элементы [16] (и даже семейства таких случайных элементов, единых по структуре, но различающихся по значениям параметров распределений) -- математические модели фрагментов знаний (фрагменты знаний) [2, 3]. Набор максимальных по включению фрагментов знаний (МФЗ) формирует первичную структуру алгебраической байесовской сети, а граф, построенный над ними -- ее вторичную структуру [4].

Проблема синтеза вторичной структуры АБС по ее первичной структуре сводится к задаче построения минимального графа смежности (МГС) по набору подалфавитов, над которыми построены фрагменты знаний [4, 5, 13, 18]. Для исследования как свойств минимальных графов смежности, так и численных характеристик осуществления алгоритмов глобального логико-вероятностного вывода [1] можно было бы изучать все минимальные графы смежности, однако это неэффективно, поскольку множество минимальных графов смежности велико [14, 15] и алгоритм синтеза этого множества затратен [6-9]. В работе [12] было предложено исследовать случайные выборки из этого множества. В ней же была поставлена задача построения минимального графа смежности случайным образом и предложен алгоритм рандомизированного синтеза такого графа с ненулевой вероятностью. Однако просто рандомизированного синтеза недостаточно: необходимо управлять распределением, которое задается работой алгоритма.

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

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

Глобальные структуры алгебраических байесовских сетей

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

В дальнейших рассуждениях будем опираться на алгоритм Прюфера [20] для построения алгоритма равновероятного синтеза минимального графа смежности. Рассмотрим ненаправленный граф из вершин, которым произвольным образом присвоены номера с по . Для удобства дальнейшей работы введем определение бирки.

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

Так как алгоритм Прюфера восстанавливает по коду Прюфера соответствующее коду дерево, а кодом может быть любая бирка, то перебирая каждую бирку и восстанавливая по ней дерево, мы переберем все деревья на данном множестве вершин.

Теорема [15]. Любая бирка Прюфера задает дерево, степени вершин которого равны числу вхождений номера вершины в кортеж , увеличенному на один.

В дальнейших рассуждениях будем обозначать степень вершины графа как . Если обозначить количество повторений индекса в коде Прюфера, то было показано [15], что

(1)

где -- вершина дерева, занумерованная индексом .

Полная формализация глобальных структур алгебраической байесовской сети может быть найдена в работах [10, 13, 16, 17]. В дальнейшем будем полагать, что первичная структура зафиксирована.

Схема алгоритма равновероятного синтеза минимального графа смежности

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

1. Построить множество всех сепараторов первичной структуры АБС. алгебраическая байесовская сеть графа

2. Для каждого построить сильное сужение

3. Разложить сужения на компоненты связности (владения) . Пронумеровать компоненты связность числами .

4. Задать код Прюфера диаметра : , определяющий однозначно дерево на элементах , причем сам код Прюфера генерируется с вероятностью

.

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

6. Объединить жилы .

Граф, полученный на последнем шаге работы алгоритма, является минимальным графом смежности по теореме о множестве минимальных графов смежности. Предложенный алгоритм генерирует минимальный граф смежности, согласно утверждению в работе [12]. Проверим, что любой граф из множества минимальных графов смежности может быть получен равновероятно при помощи предложенного алгоритма.

Теорема. Каждый элемент множества минимальных графов смежности выбирается равновероятно из множества всех минимальных графов смежности в результате работы алгоритма.

Доказательство. Пусть является элементом множества минимальных графов смежности. Результатом алгоритма является реализация случайного минимального графа смежности .

В дальнейшем верхним индексом * будем обозначать конкретную реализацию случайного элемента.

Покажем, что конкретный граф . выбирается из множества всех минимальных графов смежности равновероятно в результате работы алгоритма. Теорема о минимальных графах смежности [13, 16] утверждает, что, каждый минимальный граф смежности представляет собой пучок, т.е. объединение жил, выбранных по одной для каждого сепаратора. Обозначим через случайный элемент, отвечающий выбору жилы для сильного сужения при реализации алгоритма.

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

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

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

На шаге 4 алгоритма выписан вид вероятности

Согласно свойствам кода Прюфера, получим

Таким образом, введенный алгоритм генерирует каждую жилу равновероятно из всего множества жил для сильного сужения . Доказательство окончено.

Заключение

Для практической реализации алгоритма необходимо разработать математическую модель реализации кода Прюфера с конкретной, установленной на шаге 4 алгоритма, вероятностью.

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

Литература

1. Тулупьев А.Л. Апостериорные оценки вероятностей в алгебраических байесовских сетях // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2012. №. 2. С. 51-59.

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

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

4. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71-99.

5. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61.

6. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119-133.

7. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150-169.

8. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119-133.

9. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193-212.

10. Фильченков А.А. Иерархия глобальных структур алгебраической байесовской сети как система графов и гиперграфов // Научно-технический вестник информационных технологий, механики и оптики. 2013. Вып. 1(83). С. 75-80.

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

12. Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Тр. СПИИРАН. 2013. Вып. 2(25). С. 221-234.

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

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

15. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 15. С. 136-161.

16. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97-118.

17. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139-151.

18. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Управление глобальной структурой знаний в интеллектуальных системах, основанных на алгебраических байесовских сетях // Материалы конференции «Информационные технологии в управлении» (ИТУ-2012) (9-11 октября 2012 г., Санкт-Петербург). СПб.: ОАО «Концерн «ЦНИИ «Электроприбор». 2012. С. 25-33.

19. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009. 1208 p.

20. Prufer H. Neuer Beweis eines Satzes Uber Permutationen // Arch. Math. Phys. 1918. No. 27. P. 742-744.

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