Диссертация (1149691), страница 7
Текст из файла (страница 7)
. },34включая пустую.} ,где1 2 . . . {1 2 . . . |06 1 6 2 6. . . 6−10,66означает конъюнкцию соответствующих переменных (конъюнкт); сам знак конъюнкции мы для удобства опустим.Прежде чем ввести определение множества квантов укажем определение понятий аргументного места и кванта:Определение 2.2.2 ([142]). Литерал (аргументное место) x — это пропозициональная формула, которая может принимать одно из двухозначиваний атома˜ ∈ {,¯}.Определение 2.2.3 ([142]).Квантом над алфавитомназывается конъюнкция литералов˜0 ˜1˜ −1 . . .
. ={ } =0−1Иначе говоря, этоконъюнкция для любого атома из алфавита, содержащая либо егосамого, либо его отрицание.−1 — =Тогда множество квантов над алфавитом = { } =0{˜0˜1 . . . ˜ −1}. В дальнейшем мы будем говорить о классах цепочек конъюнкций, таким образом, мы будем работать с фактор множеством () =0 ()/ ≡. Фактор множество содержит классы эквивалентных пропозициональных формул, построенных над алфавитом . Заметим также,что любая пропозициональная формула ∈ 0 по теореме о совершенной дизъюнктивной нормальной форме (СДНФ) единственным образомпредставима в виде дизъюнкции некоторого множества квантов из , сточностью до перестановки этих формул [142]:∀ ∈0∃! ⊆( ): ≡⋁︁∈(2.1).Для удобства работы с описанными множествами введем нумерациюна них основываясь на следующем правиле: каждому кванту ˜0 ˜1 . .
. ˜ −1 поставим в соответствие двоичную запись, в которой на –м месте будет стоять1, если –й литерал означен положительно и 0 иначе. Аналогично занумеруем конъюнкты и дизъюнкты: каждому конъюнкту 0 1 . . . и дизъюнкту0 ∨ 1 ∨ . . . ∨ поставим в соответствие сумму 2 1 + 2 2 + . . . + 2[138].
Заметим, что если представить полученное в результате суммирования число ввиде двоичной записи и дополнить лидирующими нулями до n знаков получим, что –й атом входит в конъюнкт или дизъюнкт тогда и только тогда,35когда на –й бит числа равен 1. Таким образом, мы получим биективноеотображение множества квантов на множество конъюнктов и множество дизъюнктов . Рассмотрим введенную систему упорядочиванияна примере множеств элементов фрагмента знаний над тремя атомарнымипропозициональными формулами {1 ,2 ,3 }.Таблица 1 — Нумерация элементов идеала конъюнктов инабора квантов№ №(двоичная система) Conjunct Quant0000¯1 ¯2 ¯310011 20102 3011 1 2 41003 5101 1 3 6110 2 3 7111 1 2 3 1 ¯2 ¯3¯1 2 ¯31 2 ¯3¯1 ¯2 31 ¯2 3¯1 2 31 2 3Возможность упорядочивания элементов идеала конъюнктов и множества квантов, их нумерации и построения векторов вероятностныхоценок существенно упрощает программную реализацию за счет очевиднойвозможности представления вышеуказанных векторов в виде индексированных массивов.2.2.2Фрагмент знанийДля объединения утверждений в совокупности в теории алгебраических байесовских сетей используется декомпозиция данных на фрагменты знаний [142].
Под фрагментом знаний подразумевается множествоутверждений, достаточно тесно связанных между собой, при этом самифрагменты могут быть довольно слабо связаны. Эксперты в предметнойобласти обычно задают зависимости между парами-тройками атомарных36утверждений, именно поэтому для уменьшения количества вычисляемыхвероятностей используется разбиение на фрагменты знаний.Рисунок 2.1 — Фрагмент знаний над алфавитомОпределение 2.2.4 ([138]).={, , }Математической моделью фрагмента зна с неопределенностью назовем упорядоченную пару ⟨ Pc⟩, где — идеал конъюнктов над множеством атомов={}, длякаждого элемента которого определена функцияиз в интервалний,1 2 .
. . [0; 1].Далее слова математическая модель мы будем опускать, поэтому придальнейшем использование слов фрагмент знаний стоит подразумеватьматематический термин. В свою очередь сам идеал конъюнктов, над которым строится фрагмент знаний называется носителем. В качестве носителяможет выступать не только идеал конъюнктов, но и другой базис пространства формул, который можно преобразовать к множеству квантов,например, идеал дизъюнктов. Говоря о функции , мы подразумеваем, чтоона является вероятностью истинности пропозиций, что накладывает нанее некоторые ограничения, разобранные в разделе 2.3. Фрагменты знаниймогут быть трех видов, в зависимости от типа функции : бинарные, скалярные и интервальные.В случае интервальных оценок вероятностей фрагментом знаний называют структуру вида ⟨ ,⟩, где — идеал конъюнктов над множествоматомов = { 1 2 .
. . , для каждого элемента которого определена функция из во множество интервалов вида {[; ] : , ∈ [0; 1], 6 }. Вданном случае интервалы являются множествами допустимых значенийдля вероятностей конъюнктов.37Отметим, что фрагмент знаний с бинарными оценками вероятностейявляется частным случаем фрагмента знаний со скалярными оценками,который в свою очередь может быть обобщен до фрагмента знаний с интервальными оценками. Допустим, у нас определен фрагмент знаний соскалярными оценками ⟨ ,⟩, где : ∀ ∈ () = , тогда в ФЗ с интервальными оценками, обобщающем данный ФЗ, будет определена функция : ∀ ∈ () = [, ], где ∈ [0,1].
Фрагмент знаний можно также задать на матрично-векторном языке. Для этого введем вектор Pc такой чтоPc [] = ( ), где — конъюнкт из с номером . Аналогично для фрагмента знаний с интервальными оценками введем векторы нижних и верхних+−−оценок вероятностей конъюнктов P+c и Pc , такие что ( ) = [Pc []; Pc []].Тогда фрагменты знаний со скалярными и интервальными оценками мож+но определить как ⟨ ,Pc ⟩ и ⟨ ,P−c , Pc ⟩ соответственно.2.3Непротиворечивость оценок вероятностиВ предшествующем разделе мы описали локальную структуру алгебраической байесовской сети, теперь рассмотрим вопрос локальной непротиворечивости фрагмента знаний. Аксиоматика вероятностной логикинакладывает [149] некоторые ограничения как на вероятности квантов, таки на вероятности конъюнктов, не позволяя означивать их произвольнымобразом.
Дадим формальное определение непротиворечивости фрагментазнаний.Определение 2.3.1 ([142]). Фрагмент знаний со скалярными оценками⟨ ,Pc⟩ непротиворечив тогда и только тогда, когда существует вероятность(), ,заданная над множеством пропозициональных формултакая, что∀ ∈( ) = (). Непротиворечивость фрагмента знаний подразумевает истинность предикатаConsistent[⟨ ,Pc ⟩].Определение 2.3.2 ([82]). Фрагмент знаний с интервальнымими ⟨ ,Pc ⟩ непротиворечив тогда и только тогда, когда дляконъюнкта∈и любогоε∈( ) найдется функцияоценкалюбого( ) =,ε 38εи( )⟨,,ε ∃⟩,εConsistent[⟨ ,⟩]ε () = ε)&(Consistent⟨, ε ⟩).— непротиворечивый.:→ [0; 1] : (,⟨ ⟩,∈,∀ε ∈,Определение 2.3.3 ([83]).ками⇔Фрагмент знаний с интервальными оценсогласуем тогда и только тогда, когда существуетсогласованный (непротиворечивый) фрагмент знаний с интервальными оценками⟨,′⟩, такой что ∀ ∈′() ⊆ ().Ранее мы ввели такие понятия как множества квантов и конъюнктов, а также ввели вероятность на множестве квантов, идеала конъюнктови множестве пропозициональных формул.
Учитывая все вышесказанное,можно сделать вывод, что фрагменту знаний соответствует 3 множества:множество квантов, множество конъюнктов и множество дизъюнктов. Навсех трех множествах определена нумерация, а также задана вероятность.Векторы вероятностей элементов идеала конъюнктов, идеала дизъюнктови вектор вероятностей квантов над атомарными пропозициональными формулами записываются следующим образом:⎛Pc =1⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝( 1)...
⎛⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠и Pq =( 2 −1 ) ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎟⎟⎟⎟⎟⎟⎟.⎟⎟⎟⎠( 1)... (2.2)( 2 −1 ) ⎞( 0) Например, для фрагментов знаний, построенных над двумя и тремяатомами, векторы вероятностей квантов м конъюнктов будут выглядетьследующим образом:⎛Pc =⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝1( 1) ( 2) ⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠( 2 1) ⎛⎞( ¯2 ¯1 )⎟⎜ и Pq =⎜⎜⎜⎜ ⎜⎜⎜⎜ ⎜⎝⎟⎟⎟⎟⎟⎟,⎟⎟⎟⎠( ¯2 ¯1 )( 2 ¯1 )( 2 1) 39⎛Pc =⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝1( 1) ( 2) ( 2 1) ( 3) ( 3 1) ( 3 2) ⎞⎞⎛⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝и Pq =( 3 2 1)(¯3 ¯2 ¯1 )⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟.⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠(¯3 ¯2 ¯1 )(¯3 2 ¯1 )(¯3 2 1 )(3 ¯2 ¯1 )(3 ¯2 ¯1 )(3 2 ¯1 )( 3 2 1) Появление 1 на первой позиции вектора Pc обусловлено тем, что 0 —пустой конъюнкт, соответствующий тождественной истине.
При анализепроцессов локального логико-вероятностного вывода вектор Pc рассматривается как представление фрагмента знаний с оценками вероятностиистинности его элементов, а вектор Pq оказывается необходим как в математических выкладках, так и при последующей алгоритмической реализации.Эти векторы выражаются друг через друга с помощью соотношений [152]:Pq = I Pc , Pc = J Pq , где векторы I и J обратные друг другу и мо[ ] ,I =гутбытьзаданыспомощьюрекуррентныхсоотношенийI=I1 1⎞⎞⎛⎛⎜1 1 ⎟⎜1 −1⎟[ ]⎟⎟⎜= J1 ,J1 = ⎜⎠ Воспользовавшись побитовыми операциями⎠,J⎝⎝0 10 1можно вычислить [94; 166] конкретный элемент I или J по следующимформулам:⎧⎪⎪⎨0, & ̸= ,I (, ) = ⎪⎪⎩(−1)bits( )−bits( ) , & = ,⎧⎪⎪⎨0, & ≠ ,J (, ) = ⎪⎪⎩1, & = .(2.3)Вводя вероятность на множестве квантов и множестве пропозициональных формул, мы вводили некоторые ограничения.
Перепишем их наматрично-векторном языке с использованием введенных векторов: Pq >0 и (1,Pq ) = 1. (Здесь и далее под записью двух векторов в круглыхскобках через запятую будем подразумевать скалярное произведение векторов). Однако, так как при работе с алгебраическими байесовскими сетямимы чаще имеем дело с вероятностями конъюнктов чем квантов, то намсначала требуется перейти к вероятностям над квантами, а затем проверить, что получившиеся вероятности неотрицательны. Воспользовавшись40вышеуказанными соотношениями получим ограничение: I Pc > 0. Условиенормировки ((1,Pq ) = 1) будет выполнено в данном случае автоматически [139], исходя из построения матриц J и I :(1,I Pc ) = Pc (I 1) = 1.Определение 2.3.4 ([166]).(2.4)Ограничения, накладываемые условиями,перечисленными выше, на вектора вероятностейPqиPcбудут называться ограничениями, вытекающими из аксиоматики теориивероятностей и обозначатьсяℰ.Теперь, введя некоторый матрично-векторный аппарат, переформулируем предыдущие определения непротиворечивости на матрично-векторном языке [160].Определение 2.3.5 ([134]).
Фрагмент⟨ ,Pc⟩ является непротиворечивым,знаний со скалярными оценкамиесли выполняются условияℰ.Определение 2.3.6 ([134]). Фрагмент знаний с интервальными оцен+ками ⟨ ,P−c , Pc ⟩ является непротиворечивым тогда и только тогда,−++когда ∀ : 1 6 6 2 −1 ∀ε : P−c [] 6 ε 6 Pc []∃Pc : (P 6 P 6 P )&(Pc [] =ε)&(I Pc > 0).Определение 2.3.7 ([134]). Фрагмент знаний с интервальными оцен+ками ⟨ ,P−c , Pc ⟩ согласуем тогда и только тогда, когда существуетнепротиворечивый фрагмент знаний с интервальными оценками⟨P− ,P+ ⟩,,такой, чтоP− > P−cиP+ 6 P+c.В случае фрагмента знаний со скалярными оценками, ограничений,вытекающих из аксиоматики теории вероятностей, вполне достаточно длянепротиворечивости фрагмента знаний. Однако, в случае с интервальнымфрагментом знаний нам потребуется ввести еще один вид ограничений.Определение 2.3.8 ([134]).Ограничениями, вытекающими предметной области для фрагмента знаний с интервальными оценками⟨ P−c,чать,P+c⟩.будем называть ограничения вида+P−c 6 Pc 6 Pcи обозна41Для удобства работы с ограничениями введено свое особое обозначение для объединения множеств ограничений [146; 166]: ℛ = ∪ℰ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
