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

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

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

Обратим наше внимание к вектору ве­роятностей конъюнктов и попробуем вычислить их условные вероятностипри условии поступившего детерминированного свидетельства. Определимвспомогательную матрицу T⟨ ; ⟩ [159; 161]. ̃︁ ⟨ ; ⟩̃︁ ⟨ ; ⟩̃︁ ⟨ ; ⟩T⟨ ; ⟩ = T−1 ⊗ T −2 ⊗ · · · ⊗ T0 , ̃︁где T⎛⎜⎜⎝⟨; ⟩ ⎞=⎧⎪⎪⎪⎪⎪⎪⎨T+ , еслиT− , если⎪⎪⎪⎪⎪⎪⎩(2.8) входит в ,входит в ,T+ =⎜⎜⎝T0 , иначе,0 1⎟0 1⎟⎠,⎞⎛⎞⎛T− =⎜⎜⎝1−100⎟⎟⎠,T0 =1 0⎟В принятых обозначениях уравнения, описывающие решение пер­0 1вой задачи апостериорного вывода примут следующий вид [158]:⎟⎠.(⟨ ; ⟩) = (T⟨ ; ⟩ Pc )[0].(2.9) Если поступившее свидетельство имело вероятность 0 (то есть (⟨ ; ⟩) =0), то такое свидетельство называют невероятным. В противном случаерешением второй задачи апостериорного вывода можно представить в сле­дующем виде [158]:P⟨c ; ⟩ = T⟨ ; ⟩ Pc,(T⟨ ; ⟩ Pc )[0] (2.10)где в левой части равенств стоят апостериорные вероятности конъюнктовпри поступившем детерминированном свидетельстве ⟨; ⟩, а [0] указываетна верхний компонент вектора, получающегося в результате произведенияT⟨ ; ⟩ Pc [94; 166].

482.5.4Фрагмент знаний над пропозициями-квантамиОднако в рамках теории алгебраических байесовских сетей в локаль­ном апостериорном выводе (выводе на основе поступившего свидетельства),а также при попытках распространить влияние свидетельства на сосед­ние фрагменты знаний (пропагировать свидетельство), зачастую возникаетнеобходимость манипулировать не только традиционно рассматривающи­мися фрагментами знаний над пропозициями-конъюнктами, но и надфрагментами знаний с пропозициями-квантами.С формальной точки зрения, фрагмент знаний над квантами родстве­нен традиционно рассматриваемому в теории АБС фрагменту знаний надидеалом конъюнктов с оценками вероятностей их истинности, однако требу­ет иной системы накладываемых на оценки вероятности ограничений, чтоне позволяет непосредственно воспользоваться формулами апостериорноговывода, полученными в предыдущем разделе и ранее.

В данном случае мыбудем работать либо с фрагментом знаний со скалярными оценками ⟨,Pq ⟩,+либо с фрагментом знаний с интервальными оценками ⟨,P−q , Pq ⟩, где —это носитель фрагмента знаний, то есть множество квантов, упорядоченныхсогласно принятой индексации. В случае фрагмента знаний с интервальны­+ми оценками допустимое значение Pq [] лежит в границах [P−q []; Pq []]. Вначале предыдущего раздела мы уже провели рассмотрение случая пропа­гации свидетельств во фрагмент знаний с бинарными оценками, поэтомуне будем вновь заострять внимание на данном случае и сразу начнем срассмотрения пропагации детерминированного свидетельства ⟨; ⟩ в фраг­мент знаний над пропозициями-квантами.Аналогично матрице T⟨ ; ⟩ для ФЗ над идеалом конъюнктов, для ЗФнад множеством пропозиций-квантов определена матрица H⟨ ; ⟩ ̃︁ ⟨ ; ⟩̃︁ ⟨ ; ⟩̃︁ ⟨ ; ⟩H⟨ ; ⟩ = H− 1 ⊗ H − 2 ⊗ · · · ⊗ H0 , (2.11)49̃︁где H⎛⎜⎜⎝⟨; ⟩ ⎞=⎧⎪⎪⎪⎪⎪⎪⎨H+ , еслиH− , если⎪⎪⎪⎪⎪⎪⎩входит в ,входит в ,⎞⎛H+ =H0 , иначе,⎜⎜⎝0 0⎟0 1⎟⎠,⎞⎛H− =⎜⎜⎝1 0⎟0 0⎟⎠,H0 =1 0⎟В принятых обозначениях уравнения, описывающие решение пер­0 1вой задачи апостериорного вывода примут следующий вид [166]:⎟⎠.(⟨ ; ⟩) = (1,H⟨ ; ⟩ Pq ).

(2.12)Тогда решение второй задачи апостериорного вывода можно представитьв следующем виде [166]:P⟨c ; ⟩ = H⟨ ; ⟩ Pq,(1, H⟨ ; ⟩ Pq ) (2.13)где в левой части равенств стоят апостериорные вероятности конъюнктовпри поступившем детерминированном свидетельстве ⟨; ⟩ [94]. Отметим,что матрица H⟨ ; ⟩ состоит из нулей, кроме некоторых позиций на диагона­ли, занятых единицами. 2.6Глобальные структурыСогласуясь с принципом декомпозиции, теория АБС предполагает раз­биение предметной области на набор подмножеств атомов (подалфавитов),над которыми строятся фрагменты знаний [156; 157]. Совокупность такихфрагментов знаний и составляет алгебраическую байесовскую сеть [156;166; 167].

Очень важным предположением является ограниченность раз­мера подалфавита. Это позволяет свести экспоненциальный рост к линей­ному [156; 166]. Алгебраическая сеть характеризуется двумя объектами:первичной и вторичной структурой.Таким образом, одной из особенностей байесовских сетей являетсяналичие как локальной структуры (фрагмента знаний), так и множестваглобальных структур, среди которых — первичная, вторичная, третичная ичетвертичная структуры [169; 178]. Первичная и вторичная структуры необ­ходимы для проведения глобального вывода, в то время как третичная и50четвертичная структуры служат другим целям: выявлению ацикличностивторичной структуры, построению всего множества минимальных графовсмежности, а также поиску наиболее эффективной вторичной структуры.2.6.1Первичная структураПервичной структурой является множество построенных над под­множествами атомов из заданного алфавита и связанных между собойфрагментов знаний.

Между фрагментами знаний, построенными над 1и 2 , существует связь, если пересечение 1 и 2 не пусто.Лемма 2.6.1 ([174]). Непустое пересечение двух идеалом конъюнктов⟨1, 1⟩ и ⟨2, 2⟩ является в свою очередь идеалом ⟨1∩2, 1∩2⟩Каждому фрагменту знаний соответствует уникальный набор атомов,над которым он построен, поэтому двоичную запись, в которой на -й пози­ции стоит 1, когда -й атом входит в данный фрагмент знаний, и 0, когданет, можно использовать для индексации фрагментов знаний [170].2.6.2Вторичная структураАлгебраическая байесовская сеть подразумевает связность фрагмен­тов знаний, так как в противном случае она разбивается на несколькокомпонент связности и рассматривается как различные АБС. Вторичнаяструктура АБС описывает механизм связей [147] между фрагментами зна­ний, формируя особый граф, вершинами которого являются фрагментызнаний, а ребрами выступают связи между ними [177]. Тогда дадим опреде­ление алгебраической байесовской сети через набор фрагментов знаний.Определение 2.6.1 ([140]).

Алгебраическая байесовская сеть —это набор ∘ фрагментов знаний, такой, что : ∘ = { } ==1 ={( ,Pc −,Pc +)} ==1 .,,51Рисунок 2.2 — Вторичная структура АБСОпределение 2.6.2 ([140]).ской сетиНосителемsupp( )алгебраической байесов­будет объединение идеалов конъюнктов, лежащих воснове фрагментов знаний, вошедших в сеть:supp( ) =⋃︀= .=1Над всеми вершинами АБС определены операции пересечения, объ­единения и дополнения, удобно реализуемые с помощью побитовых опера­ций.

В качестве веса вершины рассматривается подмножество алфавитаатомов, над которыми построен соответствующий фрагмент знаний, авес ребра определяется как фрагмент знаний, образованный пересечениемфрагментов, лежащих на концах ребра. Для конечного определения вторич­ной структуры алгебраической байесовской сети дадим определение графасмежности.Определение 2.6.3 ([140]).Граф смежности — это ненаправленныйсвязный граф, для которого выполняются следующие два условия:521. Между каждой парой узлов, веса которых содержат общиеэлементы, существует путь без самопересечений, такой,что в веса каждого из узлов этого пути входят все элемен­ты, общие для начального и конечного узлов;2.

Вес одного узла не входит полностью в вес никакого другогоузла.Таким образом, вторичной структурой АБС является граф смежности(в случае отсутствия циклов — дерево смежности [172]; логико-вероятност­ный вывод в циклах рассмотрен в [145]) с фрагментами знаний в узлах.По каждой первичной структуре АБС можно построить множество вто­ричных структур.2.6.3Синтез вторичной структурыВторичная структура АБС, с одной стороны, позволяет осуществитьряд других операций машинного обучения, включая обучение парамет­ров или локальное обучение, а с другой стороны, даже вне контекстамашинного обучения эта структура используется во всех видах глобаль­ного логико-вероятностного вывода [139]; кроме того, вторичная структураиспользуется для хранения и визуализации АБС. В связи с этим требует­ся развивать алгоритмический аппарат синтеза, обработки, преобразованийи визуализации вторичной структуры. Отметим, что графы смежности, ав частности минимальные графы смежности (МГС), в том виде как онииспользуются в АБС, находят применение и в ряде других областей —например, таблицы реляционных баз данных, а также в сетях передачиданных [173].

Однако графы смежности являются сложной системой, чтозакономерно создает определенные сложности при разработке оптималь­ных алгоритмов генерации МГС. Особенно явно проблема быстродействияалгоритма генерации МГС встает в примерах с большим числом вершин вАБС, что делает задачу разработки и совершенствования таких алгорит­мов актуальной.53Для синтеза рассматриваемой структуры — минимального графасмежности, используются алгоритмы, которые можно логически разделитьна два типа. К первому типу алгоритмов относятся прямой и жадный алго­ритмы [115; 116], ко второму — основанные на инкрементальном подходе.Пусть задан конечный алфавит символов , а непустые множествасимволов (без повторов) — слова — рассматриваются как возможные значе­ния нагрузок вершин графов (в основном, графов смежности) и их ребер.Пусть [104] имеется набор вершин = {1 , 2 , . .

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

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