Автореферат (1149689), страница 3

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

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

Приводится мотивация и краткая история развитиябайесовского подхода. Особое внимание уделено байесовским сетям доверия,родственным алгебраическим байесовским сетям — в тексте главы даны основ­ные шаги развития данной вероятностной графической модели и рассмотреныпримеры их промышленного применения в задачах классификации. В второмразделе первой главы описывается подход к декомпозиции данных, применяе­мый в вероятностных графических моделях и мотивация его использования вконтексте больших объемов данных с неопределенностью. Наконец, рассматри­ваются достоинства и недостатки каждой модели, дается обоснование выбораалгебраических байесовских сетей в качестве объекта исследования.Во второй главе вводятся основы необходимого теоретического аппарата,используемого в последующих главах диссертации.

Материалы данной главыв подавляющей части основаны на работах В.И. Городецкого, А.Л. Тулупьева,А.В. Сироткина и А.А. Фильченкова.Подробно рассматриваются локальная структура фрагмента знаний (ФЗ),множества, лежащие в ее основе и алгоритмы локального логико-вероятностно­го вывода, а именно проверка непротиворечивости, апостериорный и априорныйвывод. Решение задачи априорного вывода приведено для идеала конъюнктови пропозиций квантов.

Раздел, посвященный апостериорному выводу начина­ется с введения определения видов свидетельств и постановки двух задачапостериорного вывода — определения вероятности поступления свидетельстваи вычисления апостериорных оценок вероятностей элементов ФЗ. В рамках дан­ного раздела рассматриваются бинарные и скалярные вероятности элементовсвидетельства и фрагмента знаний. Решение задач апостериорного вывода припоступлении свидетельства ⟨ , ⟩ приводится для обоих типов ФЗ и описывает­ся, например, в случае набора пропозиций-квантов следующими уравнениями:(︀⟨; ⟩ Pq )︀ , P⟨; ⟩ = H⟨; ⟩ Pq ,(⟨ ; ⟩) = 1,Hq⟨; ⟩ Pq )⎧(1, H+⎨H , если входит в ,; ⟩̃︀ ⟨−̃︀ ⟨; ⟩̃︀ ⟨; ⟩ , H̃︀ ⟨; ⟩ = H− , если входит в ,где H⟨; ⟩ = H1 ⊗ H−2 ⊗ · · · ⊗ H0⎩ ∘H , иначе,(︁)︁(︁)︁(︁)︁001010+−∘H =0 1 , H = 0 0 , H = 0 1 , а ⊗ обозначает произведение Кро­некера.Последний раздел второй главы посвящен глобальным структурами АБС,а именно первичной, вторичной, третичной и четвертичной структурам.

Осо­бое внимание уделяется синтезу вторичной структуры (минимального графасмежности) как наиболее широко используемой в алгоритмах ЛВВ, а такженаходящей применение в иных ВГМ родственных АБС. Рассмотрены прямойи жадный алгоритмы генерации МГС, выделены их сильные и слабые стороны,а также предложены пути к улучшению описанных алгоритмов. Глава заверша­ется описанием и постановкой задачи глобального апостериорного вывода.8Приведенные алгоритмы и уравнения создают задел для исследований,результаты которых приведены в третьей главе настоящей работы.Третья глава содержит формулировку и доказательства теоретическихрезультатов, полученных соискателем.Первый параграф главы посвящен альтернативной модели ФЗ — идеалудизъюнктов ⟨,Pd ⟩.

Для вектора вероятностей идеала дизъюнктов Pd получе­ны матрицы перехода к векторам вероятностей идеала конъюнктов Pc и наборапропозиций-квантов Pq . Предложенные матрицы строятся как произведениеКронекера элементарных матриц размерности 2 × 2:Вектора вероятностей элементов идеала конъюнктов и на­бора пропозиций-квантов можно выразить через вектора вероятностей идеаладизъюнктов следующим образом:(︁′0 1)︁[] , Pc = K P′d , K = (︁1 0)︁[] ,Pq = L Pd , L =Утверждение 1.1 −11 −1где символ [] обозначает произведение Кронекера указанных матриц.Полученные результаты используются в последующих параграфах даннойглавы в рамках решения задач логико-вероятностного вывода.Во втором параграфе проводятся исследования задач апостериорного вы­вода для бинарных и скалярных оценок вероятностей в ФЗ и поступающемсвидетельстве.

Изложение структурировано по видам структур, лежащих воснове фрагментов знаний и типам оценок вероятностей. Для каждого изперечисленных видов ФЗ и свидетельств сформулированы и доказаны мат­рично-векторные уравнения для решения первой и второй задач апостериорноговывода. Ниже представлены описанные уравнения для случая фрагмента знанийнад набором пропозиций-квантов ⟨,Pq ⟩.Решение первой и второй задач апостериорного вывода в случаепоступления детерминированного свидетельства в ФЗ над набором пропозиций­квантов будет выражено следующими уравнениями:(︀ ⟨; ⟩)︀⟨; ⟩ = s⟨; ⟩ ∘ Pq , (⟨ ; ⟩) = s,Pq и Pq(s⟨;⟩ ,Pq )⎧+⎨s , если входит в ,⟨; ⟩ s⟨; ⟩ ⊗ · · · ⊗ ̃︀s⟨; ⟩ , ̃︀s⟨; ⟩ = s− , если входит в ,где s⟨; ⟩ = ̃︀s−1 ⊗ ̃︀−20⎩ ∘s , иначе,(︁ )︁0 , s− = (︁1)︁ , s∘ = (︁1)︁ , а символ ∘ обозначает произведение Адамара.s+ =Теорема 1.101Аналогичные результаты получены для фрагментов знаний над идеаламиконъюнктов и дизъюнктов для стохастического и детерминированного свиде­тельства.Как было показано ранее, отдельной важной задачей, на решение которойнаправлена теория АБС, является обработка данных с неопределенностью.

Вшестом параграфе диссертации соискатель предлагает подход к решению задачапостериорного вывода в случае неточного свидетельства и интервальных оце­нок вероятностей элементов фрагмента знаний. Описанный подход основан науравнениях вывода, сформулированных в предыдущем параграфе Для каждогоиз рассматриваемых случаев, сформулированы ограничения и построены задачилинейного программирования, решение которых дает апостериорные интерваль­ные оценки вероятности элементов фрагмента знаний.9Подобные ЗЛП сформулированы для всех комбинаций фрагмент зна­ний–свидетельство при наличии в одном из них интервальных оценок вероят­ностей.Апостериорные оценки вероятностей элементов набора про­позиций-квантов в случае поступления неточного свидетельства находятся врезультате решения ЗЛП, предложенныхниже.⎞⎛ ′(︂)︂2 −1′⎜ ∑︁min′ s⟨GInd(,),GInd(2 −1−,)⟩ ∘ D Pevq []⎟P⟨q; ⟩,min =min⎠,⎝Утверждение 2.PP⟨q; ⟩,max=Pevq − ≤Pevq ≤Pevq +,,=0ℛ⎞⎛ ′(︂)︂2 −1′∑︁⎜⟨GInd(,),GInd(2 −1−,)⟩ ∘ D Pev []⎟max⎠.q′ sev,+ ⎝maxevq − ≤Pevq ≤Pq,=0ℛДля каждого из векторов, используемых в нормирующих множителях,предложено разложение на вектора малой размерности.

Кроме того, описаналгоритм вычисления компонент векторов s⟨; ⟩ , r⟨; ⟩ , d⟨; ⟩ , используемых внормирующих множителях, на основании битовых операций с элементами сви­детельства.{︂)︀(︀)︀(︀1, если &˙ = и &˙ = ,s⟨; ⟩ [] =0, иначе.˙ означает побитовое логическоеВ данном выражении точка над символом &«И». Параграф завершается сводной таблицей с примерами вычислений векто­ров s⟨; ⟩ , r⟨; ⟩ , d⟨; ⟩ для различных комбинаций оценок вероятностей и типовфрагментов знаний.Следующий, шестой, параграф посвящен оценкам чувствительности пер­вой задачи апостериорного вывода (,̂︀) к вариации оценок вероятностиэлементов ФЗ .

Характеризуя степень колебания результата в зависимости отизменения входных данных, чувствительность имеет практическое предназна­чение и позволяют определить степень претенциозности к точности входныхданных, что сказывается на количестве входных данных необходимых на входсоответствующему алгоритму для получения результата заданной точности.Результаты исследований чувствительности сформулированы в виде теорем, по­стулирующих накрывающую и точную оценки чувствительности для каждогоиз трех видов ФЗ.Точная оценка чувствительности первой задачи апостериор­ного вывода при поступлении детерминированного свидетельства в фрагментзнаний с скалярными оценками истинности к допустимой вариации оценокистинности элементов фрагмента знаний находится как решение следующей за­дачи линейного программирования = min (︀ { − )︀,̂︀ ̂︀ − } и (P∘c ) = max (︀ { − )︀,̂︀ ̂︀ − }.P̂︀c I ≥0,Pc I ≥0, Pc ,P̂︀c ≤,P̂︀c I ≥0,P∘c I ≥0, P∘c ,P̂︀c ≤,Утверждение 3.⟨ ⟩ ((︀))︀̂︀⟨ , ⟩= r⟨ ; ⟩ ,P̂︀c((︀))︀̂︀⟨ , ⟩= r⟨; ⟩ ,P̂︀c , = r⟨; ⟩ ,Pc , , = r⟨; ⟩ ,P∘c ,⟨ ⟩Зачастую необходим простой подход, не требующий большого числа вычис­лений и позволяющий дать некоторую оценку чувствительности, что в частностипозволит в дальнейшем, при постановке экспериментов или опросе экспертовпланировать затраты на сбор информации.102.

Оценка чувствительности первой задачи апостериорного выво­да при поступлении детерминированного свидетельства в фрагмент знаний сскалярными оценками истинности к допустимой вариации оценок истинностиэлементов фрагмента знаний меньше либо равна произведению допустимой ва­риации оценок истинности на сумму элементов(︀)︀ вектора-редистрибьютора дляпоступившего свидетельства: (,̂︀) ≤ 1,r⟨; ⟩ .ТеоремаПомимо оценок чувствительности, в исследовании даются оценки слож­ности решения первой и второй задач апостериорного вывода для различныхтипов свидетельств и видов оценок вероятностей в ФЗ. Наиболее объемлющимслучаем является решение первой задачи в случае пропагации неточного сви­детельства в ФЗ с интервальными оценками вероятностей.

В этом случае длянахождения оценок свидетельства потребуется решить 2(+1) ЗЛП, включающихв себя 2(3(2 ) + 1) ограничений, вытекающих из аксиоматики теории вероятно­стей и предметной области, где — количество атомов, входящих в алфавитсвидетельства, а — мощность алфавита, над которым построен ФЗ.Последние два параграфа главы посвящены вторичной структуре АБС,а именно глобальному ЛВВ и алгоритмам синтеза структуры. Полученныематричный уравнения апостериорного вывода позволили построить в седьмомпараграфе данной главы уравнение, описывающее способ пропагации вирту­ального свидетельства между двумя фрагментами знаний в АБС. Ключевымобъектом в описываемом алгоритме является матрица Q, являющаяся проекци­ей вектора вероятностей первого ФЗ на вектор вероятностей ФЗ-сепаратора.Теоремаsepsep ,Pc⟨3.Вектор вероятностей элементов виртуального свидетельства⟩ над алфавитом sep , пропагируемогоиз фрагмента знаний ⟨1 ,P1c ⟩2над алфавитом 1 в фрагмент знаний ⟨2 ,Pc ⟩ над алфавитом 2 можно вы­−1 ̃︀1числить следующим образом: Psep= QP, где Q = ⊗=0 Q при том чтоc{︂ c +Q, если входит в sep ,̃︀ = - мощность алфавита 1 , а QQ+ =Q− , иначе,(︁1 0)︁ , Q− = (1 0) .0 1В заключительном параграфе главы описывается инкрементальный ал­горитм генерации минимального графа смежности (МГС) при добавлениивершины в первичную структуру.Особенностью применения инкрементально­го алгоритма к построению вторичной структуры АБС является то, что вкаждый из моментов времени мы переходим из предыдущего состояния суже имеющейся построенной вторичной структурой в новое, главным отличиемкоторого является новая вершина (фрагмент знаний), которую необходимо до­бавить в граф вторичной структуры.

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

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