Графы смежности интенсивно используются в алгебраических байесов-ских сетях (далее АБС) в качестве вторичной структуры [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] нового минимального графа смежности при изменении первич-ной структуры исходного минимального графа смежности.
Вышеуказанные алгоритмы особенно удобны для интерактивных про-граммных систем, когда минимальный граф смежности строится в диалоге с пользователем. Последний ожидает от системы достаточного быстродей-ствия, полагая, что небольшое изменение в данных, в частности, при добав-лении или удалении вершины, влечет умеренное изменение минимального графа смежности.
Разработана система анализа и синтеза вторичной структуры АБС, ре-ализующая все предъявленные к ней требования.
Все задачи выполнены. Все цели достигнуты.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
