Диссертация (1149691), страница 20
Текст из файла (страница 20)
Аналогично рассмотренному в разделе 2.5 локальномуслучаю пропагации свидетельства мы положим скалярные оценки во всехфрагментах знаний рассматриваемой сети. Предположим, что в один изфрагментов знаний рассматриваемой АБС поступило стохастическое свидетельство, выраженное фрагментом знаний ⟨ ev ,Pevc ⟩. Основные шагиалгоритмы распространения виртуального свидетельства были приведеныв разделе 2.6. Ниже на рисунке 3.2 проиллюстрировано распространениесвидетельства внутри ациклической АБС, представленной деревом.Перейдем к первому шагу алгоритма — пропагации свидетельствав первый ФЗ. Следуя алгоритму и воспользовавшись формулой, предложенными в предыдущем параграфе мы абстрагируемся от связи данногоФЗ с остальной АБС и рассмотрим пропагацию свидетельства в ФЗ сточки зрения локального апостериорного вывода. Результатом пропагациисвидетельства в первый ФЗ будут переозначенные оценки вероятности истинности элементов идеала конъюнктов P1c (здесь в верхнем индексесоответствует сокращенному «a posterior»).В работе по вторичной структуре АБС было показано [32; 140],что пересечение двух фрагментов знаний (сепаратор) также являетсяфрагментом знаний, построенным над идеалом конъюнктов.
Определениесепаратора подразумевает, что вероятности всех элементов, принадлежащих сепаратору совпадают в двух ФЗ, соединяемых им. Данный факт, вчастности, приводит к тому, что типы оценок любых двух ФЗ в рассматриваемой АБС одинаковы (скалярные или интервальные). После проведенияпервого этапа апостериорного вывода и переозначивания оценок в первомфрагменте знаний была нарушена непротиворечивость АБС, так как конъюнкты, принадлежащие сепаратору, имеют с одной стороны оценки P1cкак конъюнкты, принадлежащие первому ФЗ, а с другой стороны P2c , какэлементы второго ФЗ.
Рассматривая ФЗ, построенный над элементами, принадлежащие сепаратору, с точки зрения второго ФЗ можно сказать, чтоновые оценки P1c являются своего рода новой информацией, поступающей,,,114а)б)в)г)Рисунок 3.2 — Распространение свидетельства в ациклической АБСво второй ФЗ, называемой «виртуальным свидетельством». Для того чтобывосстановить консистентность АБС нам необходимо пропагировать виртуальное свидетельство во второй ФЗ, тем самым провести апостериорныйвывод и переозначить оценки вероятностей элементов идеала конъюнктов.Для формирования виртуального свидетельства необходимо из вектора вероятностей идеала конъюнктов первого ФЗ P1c s извлечь толькоте значения вероятностей элементов, которые соответствуют конъюнктам,принадлежащим обоим ФЗ, то есть формируют вектор вероятностей идеалаконъюнктов сепаратора.
Для выделения необходимых значений из вектора,115вероятностей элементов идеала конъюнктов первого ФЗ обратимся к связивекторов Pc и Pq — они связаны следующей формулой Pc = J Pq . Поскольку все элементы в векторе вероятностей истинности элементов идеалаконъюнктов отсортированы в соответствии с введенным ранее правилом нумерации конъюнктов и квантов, то, зная алфавиты первого и второго ФЗ,не составит труда определить на каких позициях в векторе вероятностейэлементов идеала конъюнктов первого ФЗ находятся искомые значения.Приведем ниже соответствующий алгоритм, описанный в [100].Пусть алфавит, над которым построен первый ФЗ — 1 , алфавит,над которым построен второй ФЗ — 2 , а алфавит ФЗ-сепаратора двухданных ФЗ — 1 ∩ 2 = sep . Ниже приведен рисунок, иллюстрирующийФЗ-сепаратор над алфавитом sep = {, }, принадлежащий двум ФЗ.Рисунок 3.3 — Сепаратор, построенный на пересечении фрагментов знанийРассмотрим строчки матрицы J и отметим, что при умножении строки J [] на вектор P1q мы получаем -й элемент P1c .
Тогда выделим вотдельную матрицу строки J [], такие, что элементы идеала конъюнктов,значения которых записаны в соответствующих строках P1c [] , составляютидеал конъюнктов ФЗ-сепаратора элементов. Умножив данную матрицуна вектор P1q мы получим искомое подмножество оценок вероятностей истинности элементов идеала конъюнктов первого ФЗ, являющееся в своюочередь вектором оценок вероятностей элементов идеала конъюнктов виртуального свидетельства (ФЗ-сепаратора).Для того, чтобы выделить строки матрицы J , удовлетворяющие указанному условию в отдельную матрицу необходимо домножить J слева наматрицу Q размерности × , где и — мощности идеалов конъюнктов sep и 1 соответственно, а элементы матрицы задаются следующим116⎧⎪⎪⎨правилом [96]: Q[, ] = ⎪1, 1 [ ] == sep [],Последним шагом этапа форми0, иначе.рования виртуального свидетельства осталось умножить данную матрицуна P1q и получить искомое подмножество вектора P1c — Pc .
Таким образом,вектор вероятностей сепаратора можно выразить через вектор вероятно1стей первого ФЗ как Psepc = QPc .Наконец последним шагом алгоритма необходимо пропагировать свидетельство ⟨ sep ,Psepc ⟩ во второй ФЗ.Суммируя все вышесказанное запишем уравнение для пропагациивиртуального свидетельства и следующего за ней переозначивания оценоквероятностей элементов идеала конъюнктов:⎪⎩′′2 ∑︁−1 T⟨GInd( ) GInd(2 −1− )⟩ P2c1(︂)︂ I QP [],P2c =′c=0 r⟨GInd( ) GInd(2 −1− )⟩ ,P2c, ,,,, ,,(3.56)где P1c и P2c — вектора вероятностей элементов идеалов конъюнктов первого и второго ФЗ соответственно;P2c — вектор апостерионых вероятностей элементов идеала конъюнктоввторого ФЗ; — мощность идеала конъюнктов сепаратора;Q — матрица проекции вектора вероятностей элементов идеала конъюнктовпервого ФЗ на вектор вероятностей элементов идеала конъюкнтов сепаратора;GInd(,) — индекс конъюнкта с номером из идеала конъюкнтов над алфавитом sep в идеале конъюнктов над алфавитом 2 .После получения переозначенных оценок вероятностей истинностиэлементов идеала конъюнктов второго фрагмента знаний необходимо вернуться к шагу формирования виртуального свидетельства и аналогичнымобразом пропагировать новое сформированное свидетельство далее до техпор пока оценки элементов идеалов конъюнктов не будут переозначены вовсех ФЗ в данной сети.Однако, предложенный выше подход имеет недостаток матрично-векторного представления в алгоритме формирования матрицы Q, что вдальнейшем может усложнять анализ чувствительности и устойчивости,117рассматриваемой модели.
Данный недостаток возможно устранить предложив алгоритм вычисления матрицы Q, основанный на матрично-векторныхоперациях, аналогично матрицам J , I , T,H и другим.Теорема 3.8.1 ([78]).Вектор вероятностей элементов виртуальногосвидетельства можно вычислить следующим образом:1Psepc = QPc ,где⎧Q =−1 Q⊗ =0⎪⎪⎨Q+ ,если⎪⎪⎩Q− ,иначе,̃︁,при том чтовходит вsep,- мощность алфавита⎞⎛1 ,а̃︁Q=(︂)︂⎜1 0 ⎟−+⎟⎜= 1 0 .Q =⎝⎠,Q0 1Для доказательства несколько видоизменим матрицуQ− , добавив к ней строчку из 2х нулей, чтобы результирующаяматрица Q⎞⎛⎜1 0 ⎟⎟была квадратной и диагональной по построению: Q− = ⎜⎠. Рассмотрим⎝0 0диагональ матрицы Q подробнее.
Она состоит из 0 и 1, при этом единицыв данной матрицы показывают какие из оценок вероятностей в вектореP1c окажутся неизменными в векторе Psepc , нули — какие заменятся нулями. Рассмотрим на каких позициях на диагонали матрицы Q оказываютсянули: по построению каждое перемножение матриц произведением Кронекера увеличивает размерность матрицы вдвое, тогда можно заметить, чтоединственная возможность для появления 0 на диагонали матрицы Q это0, стоящий на диагонали матрицы Q− . Тогда отметим, что по построениюматрица Q− находящаяся на позиции в произведении Кронекера дает ну˙ −1 = 2 −1 , где &˙ обозначает побитовоели на всех позициях Q[,], где &2«И».
Отметим также, что по построению и в соответствии с операциямиперемножения матриц Pc [] = Q[]P1c , где Q[] — -я строка матрицы Q.˙ −1 = 2 −1 . Из выражеТеперь рассмотрим множество таких что &2ния выше понятно, что это все такие числа, в двоичной записи которых наместе − 1 стоит единица. Обратимся к нумерации конъюнктов и отметим,что все такие соответствуют номерам конъюнктов, в которых присутствует атом с номером . Например, рассмотрим ФЗ над 3 атомами —{1, 2, 3} и отметим все конъюнкты, соответствующие записи выше, приусловии, что = 2:Доказательство.118Таблица 4 — Пример выделения конъюнктов из идеалаконъюнктов над атомами {1 ,2 ,3 }№ №(двоичная система) Conjunct0000100120103011 41005101 6110 7111 121 231 32 31 2 3Таким образом, добавление матрицы Q− на позицию в произведении Кронекера «зануляет» в результирующем векторе Psepc все конъюнкты , для которых не выполняется условие ∀ ∈ : ∈ sep .Однако, при таком построении матрицы Q вектор Psepc будет одинаковой размерности с вектором P1c за счет присутствующих нулевыхэлементов.
Отметим, что так как все элементы вектора P1c положительные,то данные элементы появляются за счет умножения вектора Pc на строкиматрицы Q, в которых присутствуют только 0. Такие строки по построению могут появиться только благодаря второй строке матрицы Q− .
Тогдаизбавимся от второй строки матрицы Q− — такой шаг позволит нам получить вектор Psepc нужной размерности, а следовательно мы получим то, чтои требовалось доказать.Полученных теоретических результатов оказывается достаточно дляпроведения численных экспериментов, однако очевидна необходимостьдальнейшего развития матричного подхода и его финализации, а такжедальнейшего распространения результатов на АБС, построенные над альтернативными моделями ФЗ. Приведем ниже пример для пояснения. Пустьпервый ФЗ построен над атомами {1 , 2 , 3 }, а ФЗ сепаратор над атомами119⎛{13 }.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
