Графы смежности интенсивно используются в алгебраических байесовских сетях (далее АБС) в качестве вторичной структуры [9,11,16,30,33]. Такой объект оказался необходим потому, что ряд алгоритмов локального и глобального вывода, использующие рекуррентный подход, требуют, чтобы вторичной структурой был ациклический минимальный граф смежности [1, 8, 10, 12-14]. Однако предложенная стуктура сложна в построении, что заметно усложняет работу с динамически изменяющимися данными. Инкрементальный, а также использующий подобные методы декре- ментальный алгоритмы, рассматриваемые в данной работе, применяются для перестроения вторичной структуры АБС, что позволяет динамически изменять структуру графа смежности, не прибегая к полному перестроению графа. Это существенно сказывается на времени работы подобных алгоритмов вывода [2,5]. Кроме того, минимальный граф смежности легче визуализировать, равно как и легче выявлять скрытые закономерности, им представленные.
При сложившейся практике обмена данными [15,32] между программным компонентом, реализующим графический пользовательский интерфейс, и «блоком вычислений» — программным компонентом, обеспечивающим построение сложной системы из заданных составляющих, — типичный сценарий работы предполагает формирование набора составляющих, отправку набора в блок вычислений, формирование сложной системы, отправку данных в графический пользовательский интерфейс для визуального представления сформированной системы. Особенно это справедливо для клиент-серверных систем с так называемым «тонким» клиентом.
Однако этот типичный сценарий ведёт ко всё более длительному ожиданию оператора, когда набор составляющих растёт, поскольку зачастую вычислительная сложность алгоритмов синтеза экспоненциально зависит от объема исходных данных или оказывается ещё большей.
Одним из возможных путей решения или, по крайней мере, смягчения обозначенной проблемы является инкрементализация и дектремента- лизация алгоритмов, которая нацелена на использование того, что было построено на предшествующих шагах работы с программой.
Иначе говоря, на практике при работе с большим набором данных, в котором имеются связи, зависимости и отношения, часто ставится задача изменения подобного набора данных таким образом, чтобы имеющиеся ранее связи, зависимости и отношения либо сохранялись прежними, либо время, затрачиваемое на их перестроение, было бы близким к минимальному [24,31,34,35,37]. Трудозатраты на выполнение таких операций играют важную, а порой и критическую роль, когда речь идет о real-time-системах или о системах, для которых важна высокая степень доступности. Таким образом, возникает вопрос, как избежать полного перестроения системы после каждого небольшого изменения исходного набора данных.
В рассматриваемом случае — примере минимального графа смежности как сложной системы — осуществляется попытка использовать уже построенный минимальный граф смежности и либо дополнить его новой вершиной, либо обеднить одной из существующих вершин с соблюдением требований структуры, подробно описанных во 2-м разделе.
Таким образом, теоретической целью данной работы является разработка инкрементальных и декрементальных алгоритмов, ускоряющих построение глобальных структур алгебраических байесовских сетей при работе с динамически изменяющимися данными.
Таже в данной работе есть технологическая цель: создание системы анализа и синтеза вторичной структуры алгебраических байесовских сетей в виде комплекса программ, который позволял бы пользователям наглядно изучать поведение глобальных структур АБС при поступлении в сеть новых данных, а также проводить различного рода вычисления, важные в контексте вероятностных графических моделей. Такая система могла бы пригодиться при изучении и преподавании теории алгебраических байесовских сетей. Пользователи системы получат возможность быстро и удобно работать с такой сложной структурой, как граф смежности, и для этого им не понадобится изучать особенности программной реализации подобных алгебраических структур. Также необходимо отметить, что настоящая выпускная квалификационная работа бакалавра является проектной, то есть выполняется совместно с коллегами (Романовым Артемом Витальевичем, Березиным Алексеем Ивановичем), кроме того, тесно связана с выпускной квалификационной работой бакалавра Мальчевской Екатерины Андреевны.
Для удобства изложения сначала раскрывается теоретическая часть данной работы (главы 3-5), а затем практическая (глава 6), при этом все используемые определения вынесены в главу 2.
В данной работе рассмотрены три алгоритма, существенно ускоряющие синтез [2,5] нового минимального графа смежности при изменении первичной структуры исходного минимального графа смежности.
Вышеуказанные алгоритмы особенно удобны для интерактивных программных систем, когда минимальный граф смежности строится в диалоге с пользователем. Последний ожидает от системы достаточного быстродействия, полагая, что небольшое изменение в данных, в частности, при добавлении или удалении вершины, влечет умеренное изменение минимального графа смежности.
Разработана система анализа и синтеза вторичной структуры АБС, реализующая все предъявленные к ней требования.
Все задачи выполнены. Все цели достигнуты.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
