Диссертация (1149691), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

По построению вектор s⟨ ; ⟩ состоит из произведенияКронекера векторов размерности 2. Следовательно для построениявектора s⟨ ; ⟩ потребуется сделать 2 операций умножения. Далее, для вы­полнения операции скалярного произведения нам потребуется выполнить2 операций умножения элементов вектора s⟨ ; ⟩ на элементы вектора веро­ятностей элементов набора пропозиций-квантов Pq и 2 операций сложения.Таким образом, в целом для выполнения алгоритма решения первой задачиапостериорного вывода необходимо выполнить 2 +1 умножений и 2 сложе­ний.Доказательство. Однако, при рациональной реализации вычислений можно обратитьвнимание на то, что некоторые элементарные вектора, из которых стро­ится вектор s⟨ ; ⟩ , а именно вектора s+ и s− , содержат элементы равные 0.Появление данных векторов в произведении обусловлено наличием положи­тельно или отрицательно означенных пропозиций-квантов в поступающемсвидетельстве (иначе говоря их количество равно количеству атомов в по­ступающем свидетельстве).

Тогда количество нулевых элементов вектораs⟨ ; ⟩ будет равно 2 − , а ненулевых соответственно 2 − 2 − , при этом ихрасположение однозначно определяется формулой 3.38. При таком подходе(︁)︁для решения первой задачи нам потребуется выполнить 2 2 − 2 − умно­жений и 2 − 2 − сложений.Перейдем к решению второй задачи апостериорного вывода — вычис­лению апостериорных вероятностей элементов фрагмента знаний. Решениеданной задачи для фрагмента знаний над набором пропозиций-квантов опи­сывается уравнением 3.13. 92Теорема 3.6.2.Для решения второй задачи апостериорного выводатребуется сделать не более/вычитаний, где2 +2умножений/делений и2сложений­— количество атомов в свидетельстве, а—общее число атомов в алфавите ФЗ.Рассмотрим сперва числитель дроби: как и в первойзадаче апостериорного вывода для построения вектора s⟨ ; ⟩ нужно выпол­нить 2 операций умножения, а для вычисления произведения Адамара намнеобходимо произвести 2 операций умножения элементов вектора s⟨ ; ⟩ наэлементы вектора Pq .Как было отмечено ранее, результат первой задачи апостериорноговывода используется во второй задаче при вычислении нормирующего мно­жителя.

Однако, при вычислении вектора, стоящего в числителе дроби мыуже построили вектора s⟨ ; ⟩ , поэтому для вычисления нормирующего мно­жителя нам потребуется выполнить только 2 умножений и 2 сложений.Наконец, для того чтобы нормировать вектор, стоящий в числителе,нам необходимо каждый его элемент поделить на нормирующий множи­тель, стоящий в знаменателе дроби и по совместительству являющийсярешением первой задачи апостериорного вывода, что потребует 2 делений.Тогда, суммируя количество операций необходимых для вычисления выра­жений, стоящих в числителе и знаменателе мы получим, что для решениявторой задачи потребуется сделать 2 +2 операций умножения/деления и 2операций сложения.Доказательство. При решении второй задачи, также как и при решении первой, сто­ит учесть нулевые элементы вектора s⟨ ; ⟩ и использовать этот факт приоценке общего количества операций.

Как было показано в доказательстветеоремы 3.6.1 в векторе s⟨ ; ⟩ 2 − 2 − ненулевых элементов, а значит длявычисления произведения Адамара в числителе нам потребуется 2 − 2 −умножений. Тогда общее количество операций при корректном использова­нии структуры вектора s⟨ ; ⟩ будет равно 2 +2 − 2 − +2 умножений/деленийи 2 − 2 − сложений.Пропагация детерменированного свидетельства является простейшимслучаем задачи апостериорного вывода, но вместе с тем и наиболее удоб­ным для развития модели и ее первичного анализа. Теперь перейдем крассмотрению пропагации стохастического свидетельства, представленного 93фрагментом знаний с точечными оценками вероятностей. Решение даннойзадачи описано уравнением 3.15.Теорема 3.6.3.Длярешенияпервойзадачивслучаепропагациистохастического свидетельства в ФЗ с скалярными оценками ве­2роятностей нам потребуется выполнитьумножения и2(︁1+2 −)︁(︁)︁1 + 2 − +1операцийопераций сложения/вычитания, гдемощность алфавита, над которым построен ФЗ свидетельства, а—— мощность алфавита ФЗ, куда свидетельство поступает.Как было показано в работе [166], а также проиллюстри­ровано на рисунке 3.1, пропагация стохастического свидетельства рассмат­ривается как линейная комбинация серии пропагаций детерминированныхсвидетельств.

То есть для каждого пропагируемого детерминированногосвидетельства нам потребуется умножить получающийся в результате его(свидетельства) пропагации скаляр на вероятность указанного детермини­рованного свидетельства. Тогда, к количеству операций, необходимых длярешения первой задачи, описанной в теореме 3.6.1 добавится 2 умноженийи 2 операций сложения, что даст в общей сумме 2 + 2 +1 умножений и2 + 2 сложений/вычитаний.Доказательство.Перейдем ко второй задаче апостериорного вывода в случае стохасти­ческого свидетельства.Теорема 3.6.4.Для решения второй задачи в случае пропагации сто­хастического свидетельства в ФЗ с скалярными оценками вероятно­стей нам потребуется выполнитьи2(︁1+2 −)︁2(︁)︁1 + 2 − +2 умножений/деленийсложений/вычитаний, , где— мощность алфавита,над которым построен ФЗ свидетельства, а— мощность алфави­та ФЗ, куда свидетельство поступает.При доказательстве данной теоремы воспользуемся ре­зультатом для второй задачи апостериорного вывода, полученному длядетерминированного свидетельства, полученному в теореме 3.6.1 и анало­гично теореме 3.6.3 добавим к оценке лишь необходимое число операцийумножения (2 ) и сложения (2 ).

Суммарное число операций, необходимоедля вычисления вектора апостериорных вероятностей не будет превышать2 + 2 +2 умножений/делений и 2 + 2 операций сложения/вычитания.Доказательство.94Однако, как было показано в параграфе 3.4, операциями сложени­я/умножения удается ограничиться только в случае скалярных оценоквероятностей в ФЗ и в поступающем свидетельстве. Если же в ФЗ илив свидетельстве присутствуют неточные данные (данные с неопределенно­стью), выраженные интервальными оценками вероятностей, то решениемявляется ЗЛП с накладываемыми на нее ограничениями и ℰ (подробнееограничения описаны в параграфе 2.5).Теорема 3.6.5.Для решения первой задачи апостериорного вывода вслучае поступления детерминированного свидетельства в ФЗ с ин­тервальными оценками вероятностей потребуется решитьвключающих в себя2ЗЛП,3 (2 )+1 ограничений, вытекающих из аксиомати­ки теории вероятностей и предметной области, гдеатомов, входящих в свидетельство, а— количество— мощность алфавита, надкоторым построен ФЗ.Доказательство оценки будет основываться на ЗЛП, по­строенной в уравнении 3.28.

Рассмотрим сперва множество ограничений.Множество ограничений (ограничения, вытекающие из предметной обла­сти) соответствует 2 +1 ограничениям, а множество ℰ по построению дает2 + 1 ограничений. В результате объединения мы получим 3 (2 ) + 1 огра­ничений.Количество ЗЛП объясняется естественным образом, исходя из то­го, что нам необходимо найти минимум и максимум линейной комбинации(︁)︁s⟨ ; ⟩ ,Pq .Доказательство. Теорема 3.6.6.Для решения второй задачи апостериорного вывода вслучае поступления детерминированного свидетельства в ФЗ с ин­тервальными оценками вероятностей потребуется решитьвключающих в себя2ЗЛП,3 (2 )+2 ограничений, вытекающих из аксиомати­ки теории вероятностей и предметной области, гдеатомов, входящих в свидетельство, а— количество— мощность алфавита, надкоторым построен ФЗ.Решение второй задачи изначально представляется за­дачей квадратичного программирования из-за наличия переменной в чис­лителе и знаменателе целевой функции.

Однако, в уравнении 3.29 даннаяДоказательство.95задача сводится алгебраическими преобразованиями к ЗЛП, с дополнитель­ными ограничениями на равенство знаменателя единице. Таким образом, кусловиям, перечисленным в теореме 3.6.3, добавится 1 условие на равенствознаменателя единице, что и даст постулируемые 3 (2 ) + 2 ограничений. Ко­личество решаемых ЗЛП при этом не изменится и останется равным 2.Как в случае скалярных оценок вероятностей в ФЗ, так и в случаеинтервальных оценок, случаи пропагации детерминированного и стоха­стического свидетельств похожи. С точки зрения количества задаваемыхограничения случай пропагации стохастического свидетельства идентиченслучаю пропагации детерминированного свидетельства и отличается лишьколичеством ЗЛП — их в случае стохастического свидетельства придетсярешить 2 +1 (для каждого детерминированного свидетельства, на которыемы декомпозируем вектор вероятностей ФЗ, представляющего стохасти­ческое свидетельство).

Характеристики

Список файлов диссертации