Диссертация (1149691), страница 21
Текст из файла (страница 21)
Построим матрицу Q = Q+ ⊗ Q− ⊗ Q+ = ,⎛⎛1Тогда Psepc = QPc =⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎞1 0 0 0 0 0 0 0⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠0 1 0 0 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 0⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎞1 0 0 0 0 0 0 0⎟0 1 0 0 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 01( 1) ( 2) ( 1 2) ( 3) ( 1 3) ( 2 3) ⎟⎟⎟⎟⎟⎟.⎟⎟⎟⎠⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎛=⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝1( 1) ( 3) ⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠( 1 3) ( 1 2 3) 3.93.9.1Элементы синтеза глобальных структурАлгоритм синтеза минимального графа смежностиВторичная структура АБС, с одной стороны, позволяет осуществитьряд других операций машинного обучения, включая обучение параметровили локальное обучение, а с другой стороны, даже вне контекста машинногообучения эта структура используется во всех видах глобального логиковероятностного вывода.
Все эти операции возможны только тогда, когдавторичная структура АБС в определенном смысле минимальна и не содержит циклов.В теории АБС в качестве вторичной структуры сети используетсяграф смежности [139; 166; 167], причем в ряде контекстов обработки и преобразования АБС требуется применение минимального графа смежностиили даже дерева смежности (т.е. графа смежности без циклов). Алгоритмы синтеза минимального графа смежности по первичной структуре120АБС (в данном случае достаточно говорить о корректном наборе нагрузоквершин) были предложены [115; 116; 171; 176], однако их реализации оказались недостаточно быстрыми как для оператора, строящего вторичнуюструктуру при последовательном внесении вершин, так и для разного родаалгоритмов, работающих перебором и на каждом своем шаге удаляющихили вносящих одну вершину в граф [104; 105; 167; 171].Особенностью применения инкрементального алгоритма к построению вторичной структуры АБС является то, что в каждый из моментоввремени мы переходим из предыдущего состояния с уже имеющейся построенной вторичной структурой в новое, главным отличием которогоявляется новая вершина (фрагмент знаний), которую необходимо добавитьв граф вторичной структуры.
В то время как традиционные алгоритмыпредоставляют единственное решение для конкретной постановки задачи, инкрементальный алгоритм позволяет адаптировать уже имеющуюсяструктуру и рассчитан на использование в меняющихся условиях с ограничениями на ресурсы и время [66].Синтез минимального графа смежности — вторичной структуры АБС— в настоящем разделе описан в виде алгоритма, отличающегося тем, что,во-первых, он основывается на принципе инкрементализации, во-вторых,использует лишь особым образом отобранные ребра, исходящие из новойвершины, и, в-третьих, исключает избыточные ребра с помощью жадногоалгоритма.
Корректность работы инкрементального алгоритма обоснованаматематическим доказательством.Подробное рассмотрение шагов и доказательство корректности алгоритма дано в [120], которая в свою очередь основывается на совместнойпубликации [103]. Вкладом соискателя является доказательство корректности алгоритма, а его построение — совместный результат с соавторами.Функция (,)(листинг 3.1) [103] соединяетграф смежности с новой вершиной ребрами так, чтобы получался новыйграф смежности без избыточных ребер.Листинг 3.1 — Вспомогательная функцияinput : = ⟨ , ⟩ , voutput : function GetVerticesToConnect = ∅′ [103].1215=∅ = ⟨ , ⟩foreach ( in )sep = ∩ if ( sep = ∅ )continue ;AddAllowed = true ;′′10foreach ( in .
)if ( sep ⊆ ) thenAddAllowed = false ;break ;if ( sep ⊃ )˙ = ∖ {(,)}if ( AddAllowed ) = ∪ {(,)}1520return.′Корректность работы кода на строках 10–17 сводится к рассмотрениютрех случаев соотношения сепаратора из строки 6 с сепараторами из множества . Эти случаи подробно рассмотрены в [80; 103; 107]. На основеуказанного анализа сепаратора принимается решение о внесении или невнесении нового ребра в пополняемый граф смежности [103].Теорема 3.9.1 ([103]).ности,ℎ̸=&ℎ ∈/ ℎ },′ℎ=⟨ ,— новая вершина. Тогдасмежности, где′ПустьаДоказательство.′⟩′— минимальный граф смеж= ∪ , = {ℎ : ℎ= ∪ {{,} : ∈ }′=∈⟨′ , , ℎ′⟩ является графом∩ ̸= ∅ ∀ ′ ∈ :,ℎДоказательство подробно рассмотрено в работе [103].Инкрементальный алгоритм на листинге 3.2 [103] использует указанную теорему.Листинг 3.2 — Инкрементальный алгоритм добавления вершины вминимальный граф смежности [103].input : = ⟨ , ⟩ , voutput : = ⟨ , ⟩function SmartIncremental = ′′′′1225′=∪foreach ( in GetVerticesToConnect ( , ) ) = ∪ {{, }}′10′= ⟨ , ⟩while ( true )edge = ∅′′′foreach ( in )if ( e.
RemoveAllowed ) thenedge = ebreak foreach′1520if ( edge == ∅ )break while25if ( PathExists ( , , . , . ) ) then = ∖ elseedge . RemoveAllowed = false′′return′′Детальный разбор этого инкрементального алгоритма предлагаетсяв [103].В публикациях [101; 103—105; 108] показано, что реализация инкрементальных алгоритмов такого рода существенно превосходит по скорости работы прямые и жадные алгоритмы синтеза минимальных графовсмежности. Сравнение реализации алгоритмов производилось с помощьювычислительных экспериментов результаты которых обрабатывались соответствующими статистическими методами.Несмотря на то что в данном разделе основное внимание уделено автоматизации построения вторичной структуры алгебраической байесовскойсети, стоит отметить, что данные алгоритмы могут быть применимы такжепри построении графовых баз данных [29; 171], превосходящих [74] реляционные, в частности, в решении таких задач, как внесение изменений всхему базы и удовлетворение ограничений [11; 22; 173].
В этих областях активно проводятся исследования, нацеленные на их сближение с областьюприменения графовых структур. Отметим, что эти исследования имеют123прямое практическое применение, поскольку оптимизация запросов к базе данных [55] является немаловажным фактором работоспособности всейинформационной системы в целом.Полученные в данном разделе результаты, использующие инкрементальный подход, могут способствовать не только увеличению быстродействия алгоритмов синтеза глобальных структур, но и уменьшению объемапакетов, пересылаемых клиентов веб-приложения серверу и обратно. С одной стороны, скорость современных сетей позволяет пересылать намногобольшие объемы данных и данное улучшение может быть не столь заметно на небольших объемах, однако, в случае сложной структуры, данноеизменение может дать некоторое ускорение в обработке запроса.3.9.2Синтез четвертичной структурыСуществующие алгоритмы перестроения четвертичной структурыпри изменении первичной структуры АБС основываются на полном перестроении [171], что является избыточным, замедляет синтез глобальныхструктур, рассеивает внимание пользователя, вынужденного заново анализировать всю перестроенную структуру, а не концентрироваться лишьна тех изменениях, которые были непосредственно обусловлены ограниченной модификацией исходных данных, что снижает привлекательностьАБС как модели для обработки и визуализации данных в целом.
Взаимосвязанность структур, а также размеры моделей при больших объемахданных существенно усложняют полное перестроение каждой из структурпри изменении количества вершин, а при небольших изменениях в модели (добавление или удаление нескольких вершин) возможность «налету»перестроить модель позволяет ускорить обработку данных [121].
Обоснованность инкрементализации была показана на примере алгоритма синтезавторичной структуры АБС [103].Основой для синтеза четвертичной структуры является третичнаяструктура, таким образом, для перестроения четвертичной структуры сперва нужно изменить соответствующим образом третичную структуру. В124данном параграфе сфокусируемся на данном шаге перестроения четвертичной структуры. Как было показано, четвертичная структура являетсямножеством посиблинговых графов для каждого сепаратора из третичнойструктуры, поэтому для ее перестроения нам понадобятся следующие множества:– множество новых сепараторов NewSeps.
Данное множество позволит построить набор полусиблинговых графов по сыновьямсепараторов, чтобы затем добавить их в четвертичную структуру;– множество вершин третичной структуры Parents, у которых изменилось число сыновей. Данные изменения позволят перестроитьсоответствующую вершину полусиблингово графа;– множество сепараторов OldSeps, входящих в новую вершину, которые уже присутствуют в третичной структуре. Это множествоважно, так как в ранее построенном полусиблинговом графе, содержащем данные сепараторы, могут появиться новые ребра.Отдельно рассмотрим случай когда третичная структура остается неизменной: в данном случае изменения в четвертичной структуре могут бытьвыражены лишь новыми ребрами в полусиблинговых графах.Возвращая помимо новой третичной структуры все три указанныхвыше множества, мы получим на вход алгоритма изменения четвертичнойструктуры все сепараторы, полусиблинговые графы которых изменились имножество новых сепараторов для которых нужно построить полусиблинговые графы.
Данный результат позволяет применить инкрементальныйподход к алгоритму синтеза четвертичной структуры, описанный подробно в работе [121].3.10Выводы по главеВ этой главе были сформулированы и обоснованы основные результаты диссертационного исследования.125Так, была изучена альтерантивная модель фрагмента знаний, идеалдизъюнктов, и предложены матрицы перехода от вектора оценок вероятностей идеала дизъюнктов к вектору оценок вероятностей идеала конъюнктови множества пропозиций-квантов.Была предложена матрично-векторная запись решения первой и второй задач апостериорного вывода для фрагментов знаний над идеаломконъюнктов, дизъюнктов и множеством пропозиций-квантов. Рассмотрены задачи поступления новых обуславливающих данных, представленныхдетерминированным или стохастическим свидетельством. Вышеупомянутые утверждения сформулированы и доказаны в виде теорем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
