СИНТЕЗ ВТОРИЧНОЙ СТРУКТУРЫ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ: ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ И СТАТИСТИЧЕСКАЯ ОЦЕНКА ЕГО СЛОЖНОСТИ
Аннотация:
Предложен улучшенный алгоритм синтеза вторичной структуры алгебраических байесовских сетей, представленной в виде минимального графа смежности. Алгоритм отличается от предложенных ранее тем, что основывается на принципе инкрементализации, использует лишь особым образом отобранные ребра, исходящие из новой вершины, исключает оставшиеся избыточные ребра с помощью жадного алгоритма. Корректность работы инкрементального алгоритма обоснована математическим доказательством. Сравнение вычислительной сложности нового (инкрементального) алгоритма и двух известных (жадного и прямого) произведено с помощью статистических оценок сложности, построенных на основе выборки значений отношения времени работы программных реализаций двух сравниваемых алгоритмов. Теоретические оценки сложности жадного и прямого алгоритмов были получены ранее, но непригодны для осуществления компаративного анализа, поскольку опираются на скрытые характеристики вторичной структуры, которые можно вычислить лишь при ее построении. Для минимизации влияния случайных факторов при вычислении отношений использовано усредненное время работы программной реализации, полученное за счет K ее запусков на одном и том же наборе нагрузок. Выборка значений отношений сформирована для M таких наборов одинаковой мощности N. По выборке вычислены среднее геометрическое со статистиками, характеризующими разброс: границы 97% доверительного интервала, а также первый и третий квартили. Приведено описание алгоритмов стохастической генерации набора нагрузок заданной мощности, а также сбора статистических данных и вычисления статистических оценок отношения времени работы прямого и жадного алгоритма ко времени работы инкрементального алгоритма. Выполнена серия экспериментов, в которых N изменяется в диапазоне 1, 2…9, 10, 26, 42… 170. Результаты серии экспериментов, визуализированные с помощью графиков с использованием библиотеки Highcharts, показали, что инкрементальных алгоритм по скорости превзошел прямой и жадный алгоритмы, причем на диапазоне мощностей наборов нагрузок 10–170 этот вывод статистически достоверен (уровень 97%). Разработанный инкрементальный алгоритм предназначен для использования в решении задач машинного обучения алгебраических байесовских сетей.
Ключевые слова:
Постоянный URL
Статьи в номере
- ТЕНДЕНЦИИ РАЗРАБОТКИ ДЕТОНАЦИОННЫХ ДВИГАТЕЛЕЙ ДЛЯ ВЫСОКОСКОРОСТНЫХ ВОЗДУШНО-КОСМИЧЕСКИХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ И ПРОБЛЕМА ТРОЙНЫХ КОНФИГУРАЦИЙ УДАРНЫХ ВОЛН Часть I. Исследования детонационных двигателей
- АНАЛИЗ ОСОБЕННОСТЕЙ ВЫБОРА ИСХОДНОЙ ОПТИЧЕСКОЙ СХЕМЫ ДЛЯ РАСЧЕТА НЕИЗОБРАЖАЮЩИХ ОПТИЧЕСКИХ СИСТЕМ
- ПРИМЕНЕНИЕ МЕТОДОВ ХЕМОМЕТРИКИ ДЛЯ АНАЛИЗА БИОАЭРОЗОЛЕЙ ПРОТОЧНО-ОПТИЧЕСКИМ МЕТОДОМ
- МЕТОДИКА АВТОМАТИЗАЦИИ ЦЕНТРИРОВКИ ЛИНЗОВЫХ КОМПОНЕНТОВ ПРИ СБОРКЕ ОБЪЕКТИВОВ РАЗЛИЧНЫХ КОНСТРУКЦИЙ
- МЕТОД СОЗДАНИЯ СФЕРИЧЕСКИХ ПАНОРАМ ИЗ ИЗОБРАЖЕНИЙ, ПОЛУЧЕННЫХ ВСЕНАПРАВЛЕННЫМИ ОПТИКО-ЭЛЕКТРОННЫМИ СИСТЕМАМИ
- СИСТЕМА СПЕКТРАЛЬНОЙ ОПТИЧЕСКОЙ КОГЕРЕНТНОЙ ТОМОГРАФИИ БЛИЖНЕГО ИНФРАКРАСНОГО ДИАПАЗОНА С ПЕРЕСТРАИВАЕМОЙ ДЛИНОЙ ВОЛНЫ И ЛИНЕЙНЫМ ПОЛЕМ ОСВЕЩЕНИЯ
- МЕТОД БЭКСТЕППИНГА ДЛЯ СТРУКТУРНО НЕОПРЕДЕЛЕННЫХ ОБЪЕКТОВ
- ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ ТРАЕКТОРИЙ СВОБОДНОГО ДВИЖЕНИЯ НЕПРЕРЫВНОЙ СИСТЕМЫ В ФОРМЕ ПОСЛЕДОВАТЕЛЬНОЙ ЦЕПОЧКИ ОДНОТИПНЫХ АПЕРИОДИЧЕСКИХ ЗВЕНЬЕВ
- СПЕКТРАЛЬНЫЕ ХАРАКТЕРИСТИКИ СВЕТОДИОДОВ СРЕДНЕГО ИНФРАКРАСНОГО ДИАПАЗОНА НА ОСНОВЕ InAs(Sb,P)
- МОДЕЛИРОВАНИЕ ЧУВСТВИТЕЛЬНОГО ЭЛЕМЕНТА ДАТЧИКА ТЕМПЕРАТУРЫ НА ОСНОВЕ СИЛИКАТНОГО СТЕКЛА С НАНОЧАСТИЦАМИ НАТРИЯ
- (НЕ-) КОНФИДЕНЦИАЛЬНОСТЬ ИНФОРМАЦИИ В МОБИЛЬНЫХ ПРИЛОЖЕНИЯХ. ВОЗМОЖНОСТИ КЛИЕНТОВ И ПОЛЬЗОВАТЕЛЕЙ (на англ. яз.)
- ПРИНЦИПЫ ИНДИКАЦИИ МАРШРУТНЫХ ТРАЕКТОРИЙ ПОЛЕТА ЛЕТАТЕЛЬНОГО АППАРАТА НА ЭКРАНЕ БОРТОВЫХ СРЕДСТВ ОТОБРАЖЕНИЯ ИНФОРМАЦИИ
- МЕТОД ИСПРАВЛЕНИЯ ОШИБОК ВСТАВКИ И УДАЛЕНИЯ В НАБОРЕ ЧТЕНИЙ НУКЛЕОТИДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
- ВЫБОР ВАРИАНТА ПОСТРОЕНИЯ МНОГОУРОВНЕВОГО ЗАЩИЩЕННОГО ДОСТУПА К ВНЕШНЕЙ СЕТИ
- ВЛИЯНИЕ НЕИДЕНТИЧНОСТИ МИКРОФОНОВ НА ХАРАКТЕРИСТИКИ МИКРОФОННЫХ РЕШЕТОК
- АВТОМАТИЗИРОВАННЫЙ ЛАЗЕРНО-УЛЬТРАЗВУКОВОЙ МЕТОД КОНТРОЛЯ КАЧЕСТВА ПАЯНЫХ СОЕДИНЕНИЙ СОПЕЛ КАМЕР ЖИДКОСТНЫХ РАКЕТНЫХ ДВИГАТЕЛЕЙ
- РОБАСТНАЯ МОДИФИКАЦИЯ МЕТОДА ЛАССО ДЛЯ ПОЛНОГЕНОМНОГО ПОИСКА АССОЦИАЦИЙ С УЧЕТОМ ЦЕЛЕВЫХ ЗНАЧЕНИЙ ФЕНОТИПА
- ЭТАЛОННЫЕ РЕШЕНИЯ УРАВНЕНИЙ СТОКСА С ПЕРЕМЕННОЙ ВЯЗКОСТЬЮ В ЦИЛИНДРИЧЕСКИХ И СФЕРИЧЕСКИХ КООРДИНАТАХ ДЛЯ ТЕСТИРОВАНИЯ АЛГОРИТМОВ
- ИНФОРМАЦИОННАЯ МОДЕЛЬ МЕНТАЛЬНОГО ВРАЩЕНИЯ ФИГУР
- РЕШЕНИЕ ТЕСТОВЫХ ЗАДАЧ НЕСТАЦИОНАРНОЙ ОДНОМЕРНОЙ ГАЗОВОЙ ДИНАМИКИ ПРИ ПОМОЩИ WENO-СХЕМ
- МОДЕЛИРОВАНИЕ ПРОЦЕССА АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ФОРМИРОВАНИЕМ ПРОФЕССИОНАЛЬНЫХ НАВЫКОВ ОПЕРАТОРА ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ
- ИССЛЕДОВАНИЕ ОПТИЧЕСКИХ И ЛЮМИНЕСЦЕНТНЫХ СВОЙСТВ КАЛИЕВО-АЛЮМОБОРАТНЫХ СТЕКОЛ, АКТИВИРОВАННЫХ ИОНАМИ ХРОМА Cr3+
- ДИКТОРО-ЗАВИСИМЫЕ ПРИЗНАКИ ДЛЯ РАСПОЗНАВАНИЯ СПОНТАННОЙ РЕЧИ