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

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

Аннотация:

Предмет исследования. Алгебраические байесовские сети относятся к классу вероятностных графических моделей, являющихся представлением баз знаний с неопределенностью. Отличительной особенностью алгебраических байесовских сетей является наличие глобальных структур, среди которых присутствуют первичная и вторичная, которые используются в различных видах логико-вероятностного вывода непосредственно, а также третичная и четвертичная, участвующие в задачах автоматического синтеза, идентификации свойств вторичной структуры и, опосредованно, в решении задач машинного обучения указанных сетей. Существующие алгоритмы изменения четвертичной структуры требуют ее полного перестроения при изменении первичной структуры. Эта особенность замедляет синтез глобальных структур, рассеивает внимание пользователя, вынужденного заново анализировать всю перестроенную структуру, а не концентрироваться лишь на тех изменениях, которые были непосредственно обусловлены ограниченной модификацией исходных данных, что снижает привлекательность алгебраических байесовских сетей как модели для обработки и визуализации данных в целом. Цель исследования. Работа направлена на локализацию изменений четвертичной структуры при добавлении и удалении вершины из первичной структуры или, иначе говоря, на обеспечение ограничения таких изменений лишь необходимыми из них за счет устранения недостатка существующих алгоритмов, выраженного в избыточном перестроении всей структуры. Для достижения поставленной цели решается задача инкрементализации алгоритма перестроения четвертичной структуры. Метод. Предлагаемый подход основан на свойствах инкрементализации алгоритмов, позволяющих сократить объем вычислений за счет использования результата, полученного на предыдущем шаге алгоритма. Все рассуждения, проводимые в работе, изложены на языке теории графов, чтобы использовать устоявшуюся систему терминов и классических результатов. Основные результаты. В работе представлены инкрементальный и декрементальный алгоритмы изменения четвертичной структуры при добавлении или удалении вершины из первичной структуры алгебраической байесовской сети, снабженные доказательством корректности и листингами. Приведенные в работе алгоритмы строятся на основании полученных ранее инкрементальных алгоритмов для третичной структуры. Также в работе проводится подробный анализ множества сепараторов на каждом этапе работы алгоритмов. Теоретическая и практическая значимость. Полученные алгоритмы развивают теорию глобальных структур алгебраических байесовских сетей, в частности, и теорию вероятностных графических моделей в целом. Кроме того, они создают задел для поиска инвариантного представления системы связей внутри алгебраической байесовской сети в отличие от существующего подхода, при котором эти связи выражены во вторичной структуре, которая может оказаться не единственной даже при фиксированной первичной структуре. Исключение манипуляций с множеством вторичных структур заметно упростит и сделает обозримой визуализацию такого сложного объекта, как алгебраические байесовские сети, и, возможно, улучшит вычислительные характеристики алгоритмов логико-вероятностного вывода в сети, а также позволит переформулировать задачи машинного обучения алгебраических байесовских сетей, исключив из них необходимость синтеза множества разных объектов сложной структуры с фактически одинаковой семантикой. Также можно ожидать, что полученные инкрементальные алгоритмы ускорят вычислительные процессы по перестроению и анализу свойств всех четырех глобальных структур алгебраических байесовских сетей.

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

Постоянный URL

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

Содержание © 1993–2024 Университет ИТМО
Разработка © 2015 Университет ИТМО