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

СИНТЕЗ ВТОРИЧНОЙ СТРУКТУРЫ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ: ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ И СТАТИСТИЧЕСКАЯ ОЦЕНКА ЕГО СЛОЖНОСТИ

Аннотация:

Предложен улучшенный алгоритм синтеза вторичной структуры алгебраических байесовских сетей, представленной в виде минимального графа смежности. Алгоритм отличается от предложенных ранее тем, что основывается на принципе инкрементализации, использует лишь особым образом отобранные ребра, исходящие из новой вершины, исключает оставшиеся избыточные ребра с помощью жадного алгоритма. Корректность работы инкрементального алгоритма обоснована математическим доказательством. Сравнение вычислительной сложности нового (инкрементального) алгоритма и двух известных (жадного и прямого) произведено с помощью статистических оценок сложности, построенных на основе выборки значений отношения времени работы программных реализаций двух сравниваемых алгоритмов. Теоретические оценки сложности жадного и прямого алгоритмов были получены ранее, но непригодны для осуществления компаративного анализа, поскольку опираются на скрытые характеристики вторичной структуры, которые можно вычислить лишь при ее построении. Для минимизации влияния случайных факторов при вычислении отношений использовано усредненное время работы программной реализации, полученное за счет K ее запусков на одном и том же наборе нагрузок. Выборка значений отношений сформирована для M таких наборов одинаковой мощности N. По выборке вычислены среднее геометрическое со статистиками, характеризующими разброс: границы 97% доверительного интервала, а также первый и третий квартили. Приведено описание алгоритмов стохастической генерации набора нагрузок заданной мощности, а также сбора статистических данных и вычисления статистических оценок отношения времени работы прямого и жадного алгоритма ко времени работы инкрементального алгоритма. Выполнена серия экспериментов, в которых N изменяется в диапазоне 1, 2…9, 10, 26, 42… 170. Результаты серии экспериментов, визуализированные с помощью графиков с использованием библиотеки Highcharts, показали, что инкрементальных алгоритм по скорости превзошел прямой и жадный алгоритмы, причем на диапазоне мощностей наборов нагрузок 10–170 этот вывод статистически достоверен (уровень 97%). Разработанный инкрементальный алгоритм предназначен для использования в решении задач машинного обучения алгебраических байесовских сетей.

Ключевые слова:

Статьи в номере