close

Вход

Забыли?

вход по аккаунту

?

Матричные уравнения локального логико-вероятностного вывода оценок истинности элементов в алгебраических байесовских сетях.

код для вставкиСкачать
УДК 004.8
Вестник СПбГУ. Сер. 1. 2012. Вып. 3
МАТРИЧНЫЕ УРАВНЕНИЯ ЛОКАЛЬНОГО
ЛОГИКО-ВЕРОЯТНОСТНОГО ВЫВОДА
ОЦЕНОК ИСТИННОСТИ ЭЛЕМЕНТОВ
В АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЯХ∗
А. Л. Тулупьев1 , А. В. Сироткин2
1. С.-Петербургский государственный университет,
д-р физ.-мат. наук, профессор, alexander.tulupyev@gmail.com
2. С.-Петербургский государственный университет,
мл. научн. сотр., alexander.sirotkin@gmail.com
1. Введение. Существуют различные подходы к построению баз фрагментов
знаний с вероятностной неопределенностью для интеллектуальных систем, ориентированных на поддержку принятия решений. Одним из подходов является парадигма
алгебраических байесовских сетей, предложенная В. И. Городецким в 1983 году [1–3]
(название предложено в [2] в 1993 г.).
В теории алгебраических байесовских сетей (АБС) математической моделью
фрагмента знаний (ФЗ) является идеал конъюнктов, или идеал цепочек конъюнкций, с оценками вероятности истинности входящих в него элементов. Определение
идеала конъюнктов будет дано ниже. Из набора ФЗ строится сама АБС.
Для формализации понятия вероятности истинности пропозициональной формулы используется способ, основанный на подходе Н. Нильссона [4].
Цель настоящей работы — дать на матрично-векторном языке формальное описание операций локального логико-вероятностного вывода в ФЗ АБС.
2. Базовые объекты и индексация. В первую очередь, зафиксируем конечное
множество атомарных пропозициональных формул (атомов) — алфавит A = {xi }n−1
i=0 .
Отметим, что для удобства мы будем вести нумерацию переменных с нуля. Определим над указанными атомами два набора «базовых» пропозициональных формул.
Первый набор формул — идеал цепочек конъюнкций (идеал конъюнктов) —
{xi1 xi2 . . . xik |0 6 i1 < i2 < . . . < ik 6 n − 1, 0 6 k 6 n} ,
где xi1 xi2 . . . xik означает конъюнкцию соответствующих переменных; сам знак конъюнкции мы для удобства опустим. Каждому из конъюнктов вида xi1 xi2 . . . xik можно
сопоставить число 2i1 +2i2 +. . .+2ik — номер конъюнкта. Более того, если представить
полученное число в двоичной записи, то переменная xi будет входить в конъюнкт
тогда и только тогда, когда i-й бит номера будет равен единице (нумеровать биты
предлагается, начиная с младшего разряда, считая его нулевым битом).
Для определения второго набора формул — множества квантов — будет полезным
следующее обозначение. Литерал (аргументное место) x̃i означает, что на его месте
в пропозициональной формуле может стоять либо xi , либо его отрицание x̄i . Тогда
n−1
множество квантов над алфавитом A = {xi }i=0 — Q = {x̃0 x̃1 . . . x̃n−1 }. Иными словами, квант — это конъюнкция, которая для любой переменной из алфавита содержит
∗ Работа выполнена при частичной финансовой поддержке РФФИ (грант № 09-01-00861-а).
c А. Л. Тулупьев, А. В. Сироткин, 2012
63
либо ее саму, либо ее отрицание. Для нумерации квантов мы воспользуемся способом, аналогичным нумерации конъюнктов. Выделим «положительную» часть кванта
(множество положительно означенных переменных) и рассмотрим ее как конъюнкт.
Номер этого конъюнкта и будет номером рассматриваемого кванта. Таким образом,
единице в двоичной записи номера соответствует положительное вхождение переменной, а нулю — отрицательное, при этом рассматриваются все n бит (то есть с учетом
лидирующих нулей).
После введения нумерации квантов и конъюнктов можно определить векторы
вероятностей квантов и конъюнктов:




1
p(q0 )
 p(c1 ) 
 p(q1 ) 




Pc = 
и
P
=


,
..
..
q




.
.
p(c2n −1 )
p(q2n −1 )
где ci — конъюнкт номер i, а qi — i-й квант. Появление единицы в первом случае
вполне оправдано, так как согласно определению c0 — пустой конъюнкт, соответствующий тождественной истине. После введения перенумерации и определения базовых
объектов (конъюнктов и квантов) перейдем к определению вероятности над пропозициональными формулами.
3. Оценки вероятностей над пропозициональными формулами. Пусть
F0 (A) — множество всех пропозициональных формул над заданным алфавитом A =
n−1
{xi }i=0 . Определим множество отличающихся формул как фактор-множество всех
формул по условию эквивалентности: F (A) = F0 (A)/ ≡. Над n атомарными переменn
ными подобных формул существует ровно 22 .
По теореме о совершенной нормальной дизъюнктивной форме любая пропозициональная формула может быть представлена в виде дизъюнкции конечного числа
квантов. Так как при любом зафиксированном означивании всех литералов x̃0 , x̃1 ,
. . . , x̃n−1 никакие два разных кванта не могут быть одновременно истинны, а, с другой стороны, один из них заведомо истинен, можно рассмотреть множество Q как
множество элементарных событий. Задав вероятность на квантах, можно, в свою
очередь, построить вероятностное пространство, на котором будет определена вероятность любой пропозициональной формулы [5–7]. За более подробным описанием
аксиоматики вероятностной логики можно обратиться, например, к [4, 8, 9].
Определение вероятности на элементах множества Q потребует следующих ограничений (фактически, речь идет о задании распределения вероятности на множестве
элементарных событий):
∀q ∈ Q p(q) > 0,
X
p(q) = 1.
(1)
(2)
q∈Q
Пользуясь введенными выше векторами, перепишем эти условия следующим образом:
Pq > 0;
(1, Pq ) = 1.
64
(3)
(4)
В алгебраических байесовских сетях мы, в основном, работаем не с квантами, а
с конъюнктами.
Теорема 1. Вероятности квантов и вероятности конъюнктов выражаются
друг через друга с помощью следующих соотношений:
где
Pq = In × Pc ,
(5)
Pc = Jn × Pq ,
(6)
1 −1
In = I1 ⊗ In−1 = I1 ⊗
=
а I1 =
;
0
1
1 1
[n−1]
[n]
Jn = J1 ⊗ Jn−1 = J1 ⊗ J1
= J1 , а J1 =
.
0 1
[n−1]
I1
[n]
I1 ,
Здесь и далее ⊗ обозначает кронекерово (тензорное) произведение матриц [10].
Доказательство. Доказательство приведенной теоремы можно найти в [8, 5,
11].
После применения приведенных в теореме соотношений ограничения (1)–(2) принимают вид
In × Pc > 0.
(7)
Здесь n — число атомов, а матрица In — матрица перехода от вероятностей квантов к
вероятностям конъюнктов, описанная в теореме. Заметим, что если вычислить вероятности квантов на основе вероятностей конъюнктов, удовлетворяющих условию (7),
то условия (1) и (2) будут выполнены автоматически [8].
Заметим, что (5) можно рассматривать как матрично-векторную запись формулы включений—исключений.
4. Непротиворечивость фрагмента знаний. Основным «конструкционным
блоком» АБС является фрагмент знаний (ФЗ); исследуем вопросы его непротиворечивости. ФЗ представляет с собой идеал конъюнктов с оценками истинности. При
этом можно выделить два основных случая.
1. Оценка вероятности истинности каждого конъюнкта задана скалярно (точечно); совокупность всех оценок представлена в виде вектора оценок Pc ; тогда для
проверки непротиворечивости достаточно проверить выполнение условий (7).
2. Заданы два вектора — верхние и нижние оценки вероятностей истинности
конъюнктов в идеале — P− и P+ ; мы говорим, что подобные оценки непротиворечивы, если
∀i : 1 6 i 6 2n − 1 ∀ε : P− [i] 6 ε 6 P+ [i]
∃Pc : P− 6 Pc 6 P+ & (Pc [i] = ε) & (In × Pc > 0) .
Здесь запись вида Pc [i] означает i-й элемент вектора Pc . Если выразить словами, то
для любой оценки любого конъюнкта (кроме нулевого, оценка для которого всегда
единица), лежащей в границах, определенных векторами P− и P+ , существует совокупность оценок вероятностей всех остальных конъюнктов, лежащих в границах,
определенных P− и P+ , и задающих непротиворечивый фрагмент знаний со скалярными оценками.
65
Как уже было сказано, в первом случае нам достаточно проверить по формуле
(7), непротиворечива оценка или нет. В случае с интервальными оценками вопрос не
только в том, что непротиворечивы они или нет, но и если противоречивы, то можно
ли их сузить до непротиворечивых. Решения этих двух вопросов взаимосвязаны. Для
проверки непротиворечивости необходимо решить серию задач линейного программирования (ЗЛП) [8]. Переменными данных задач будут точечные вероятности Pc , а
ограничения будут двух типов: P− 6 Pc 6 P+ и In × Pc > 0. Осталось определить
только целевые функции. Целевыми функциями будут максимизация и минимизация Pc [i] для каждого i : 1 6 i 6 2n − 1 (решать задачу для i = 0 не требуется,
так как по определению Pc [0] = 1). Решение этой серии ЗЛП позволяет определить,
непротиворечив ли ФЗ; в этом случае все ЗЛП будут разрешимы и соответствующие максимумы и минимумы совпадут с заданными границами. Если хотя бы одна
из ЗЛП дала результат, отличный от заданных границ, то соответствующие максимумы и минимумы дадут наибольший по включению набор интервальных оценок,
задающий непротиворечивый ФЗ и лежащий в указанных границах. А если хоть одна из ЗЛП оказалась неразрешима, то значит такого сужения не существует и ФЗ —
противоречив.
5. Локальный априорный вывод. Сформировав непротиворечивый ФЗ, перейдем к вопросу об оценивании вероятности произвольной пропозициональной формулы, заданной над теми же атомами, что и фрагмент знаний. Суть априорного
вывода — построение оценок для некоторой формулы на основе оценок другого набора формул. В контексте АБС наиболее естественно в качестве набора формул, уже
имеющих оценки, рассматривать элементы ФЗ. Мы не будем подробно останавливаться на вопросах обработки формул и переходу к их совершенной дизъюнктивной
нормальной форме (СДНФ), за этим можно обратиться к статье [12].
Рассмотрим пропозициональную формулу f , вероятность истинности которой
требуется оценить. Обозначим через Lf вектор, содержащий 2n элементов, каждый
из которых является единицей или нулем в зависимости от того, входит или не входит соответствующий по номеру квант в СДНФ формулы f (нумерация квантов была
описана в разделе 2).
Пусть задан фрагмент знаний с оценками истинности, то есть мы имеем ограничения вида P− 6 Pc 6 P+ , где Pc — вектор вероятностей конъюнктов, входящих в
ФЗ, а P− и P+ — векторы, состоящие из соответствующих нижних и верхних оценок.
Вероятность формулы f можно выразить следующим образом:
p(f ) = (Lf , Pq ).
Для перехода к вероятностям конъюнктов воспользуемся уже применявшейся
выше формулой (5) и получим
p(f ) = (Lf , In × Pc ) = (ITn × Lf , Pc ).
Таким образом, мы выразили вероятность произвольной формулы через вероятности конъюнктов. Чтобы оценить p(f ), построим задачу линейного программирования.
Переменными нашей ЗЛП, как и в случае поддержания непротиворечивости, будут элементы вектора Pc . Ограничениями будут P− 6 Pc 6 P+ , заданные в ФЗ, и
66
неравенства In ×Pc > 0, заданные аксиоматикой теории вероятностей. Целевая функция описывается выражением p(f ) = (ITn × Lf , Pc ). Решив ЗЛП, найдем максимум и
минимум целевой функции — это и будут искомые оценки вероятности формулы f .
Если же построенная ЗЛП не будет иметь решения, то это означает, что исходный
набор оценок был противоречив.
Кроме такого подхода к априорному выводу можно рассмотреть еще построение (или уточнение) оценок ФЗ на основе оценок произвольного набора формул, оно
происходит аналогично процессу поддержания непротиворечивости, только в ЗЛП
+
−
+
T
добавляется условие p−
f 6 (In × Lf , Pc ) 6 pf , где pf и pf — нижняя и верхняя
оценки вероятности формулы f . Более подробное описание ЗЛП в данном случае
можно найти в [8], а вопросы автоматизации обработки формул в указанном контексте и выбора представления данных для программной реализации были подробно
рассмотрены в [12].
6. Перестановки, переозначивания и свидетельства. Для описания последнего вида вывода нам потребуется описать логико-вероятностную модель свидетельств в теории АБС, а так же ввести ряд вспомогательных обозначений, которые
позволят нам изложить оставшийся материал тоже на матрично-векторном языке.
Под свидетельством мы понимаем новые «обусловливающие» данные, которые
поступили во фрагмент знаний, и с учетом которых нам требуется пересмотреть все
(или некоторые) оценки. Сама суть апостериорного вывода заключается в оценивании
условной вероятности элементов ФЗ относительно поступившего свидетельства.
Свидетельства, применяемые в теории АБС, разделяются на несколько видов:
• детерминированные свидетельства;
• стохастические свидетельства;
• неточные свидетельства.
В данной статье мы рассмотрим только детерминированное свидетельство; оставшиеся два случая могут быть сведены к пропагации серии детерминированных свидетельств [8]. Мы говорим, что на вход системы поступило детерминированное свидетельство, если новые сведения представимы в виде конъюнкции атомарных переменных и их отрицаний. Примерами таких свидетельств могут быть hx1 i, hx2 x̄3 i, hx1 x̄3 x4 i;
угловые скобки используются для обозначения того, что соответствующая конъюнкция рассматривается нами как свидетельство. Заметим, что такое свидетельство можно разбить на «положительный» и «отрицательный» конъюнкты. В первый входят
все положительно означенные атомарные переменные свидетельства, а во второй —
отрицательно. При этом и положительной, и отрицательной части можно сопоставить
индекс в соответствии с перенумерацией, приведенной во втором разделе настоящей
работы, и наши свидетельства можно будет записать следующими эквивалентными
обозначениями:
hx1 i = hx1 i = h2; 0i = h000102; 000002i ,
hx2 x̄3 i = hx2 , x̄3 i = h4; 8i = h001002; 010002i ,
hx1 x̄3 x4 i = hx1 x4 , x̄3 i = h18; 8i = h100102; 010002i .
Далее, мы полагаем, что нам поступило свидетельство hi; ji. В первую очередь,
обратим наше внимание к вектору вероятностей квантов и попробуем вычислить
67
условные вероятности квантов при условии поступившего детерминированного свидетельства. Для этого нам понадобится следующая матрица:
hi,ji
hi,ji
hi,ji
e
e
e
Hhi,ji = H
n−1 ⊗ Hn−2 ⊗ . . . H0
где
,
 +
 H , если xk входит в ci ;
e hi,ji =
H− , если xk входит в cj ;
H
k
 ◦
H , иначе;
0 0
1 0
1 0
причем H+ =
; H− =
; H◦ =
.
0 1
0 0
0 1
При вычислении произведения Hhi,ji ×Pq мы как бы «вычеркиваем» вероятности
квантов, противоречащие поступившему свидетельству, заменяя их на нули. При этом
на каждой позиции будет стоять вероятность конъюнкции кванта и поступившего
свидетельства.
Теперь рассмотрим величину (1, Hhi,ji × Pq ). Она в точности соответствует вероятности поступившего свидетельства. Теперь для того чтобы получить условные
вероятности, осталось найти отношение совместной вероятности к вероятности свидетельства, то есть вычислить
1
(1, Hhi,ji
× Pq )
· Hhi,ji × Pq .
Таким образом мы нашли условные вероятности квантов. Для того чтобы получить
условные вероятности конъюнктов, нам необходимо умножить полученный вектор на
Jn . Кроме того, подставим в нашу формулу известное нам соотношение (5). Обознаhi;ji
чив вектор условных вероятностей конъюнктов через Pc , получим
Phi;ji
= Jn ×
c
1
· Hhi,ji × In × Pc .
(1, Hhi,ji × Pq )
По определению вектора Pc на нулевом месте всегда стоит единица. Это же утверhi;ji
ждение справедливо для Pc . Это значит, что если мы рассмотрим ненормированное
произведение
Jn × Hhi,ji × In × Pc ,
то на нулевой позиции полученного вектора будет стоять (1, Hhi,ji × Pq ), а значит,
нет необходимости вычислять эту величину отдельно.
Введем обозначение Thi,ji = Jn × Hhi,ji × In × Pc , тогда верно следующее.
Теорема 2. Матрица оператора ненормированного апостериорного вывода может быть вычислена по следующей формуле:
e hi,ji ⊗ T
e hi,ji ⊗ . . . T
e hi,ji ,
Thi,ji = T
n−1
n−2
0
где
+
причём T =
68
0 1
0 1
e hi,ji
T
k
;
 +
 T , если xk входит в ci ;
T− , если xk входит в cj ;
=
 ◦
T , иначе;
1 −1
1 0
−
◦
T =
;
T =
.
0
0
0 1
Доказательство. Напомним, что матрицы In , In и Hhi,ji × In представляют
собой кронекерово произведение матриц небольшой размерности. Учитывая это и
используя свойство кронекерова произведения, получаем
Thi,ji = Jn × Hhi,ji × In × Pc =
hi,ji
hi,ji
hi,ji
e
e
e
= (J1 ⊗ . . . ⊗ J1 ) × (H
n−1 ⊗ Hn−2 ⊗ . . . H0
=
=
e hi,ji × I1 ) ⊗ (J1 ×
(J1 × H
n−1
hi,ji
e
e hi,ji
e hi,ji .
T
n−1 ⊗ Tn−2 ⊗ . . . T0
e hi,ji
H
n−2
) × (I1 ⊗ . . . ⊗ I1 ) =
e hi,ji × I1 ) =
× I1 ) ⊗ . . . ⊗ (J1 × H
0
e hi,ji = J1 × H
e hi,ji × I1 . Осталось воспользоваться определением матриц I1 ,
Откуда T
k
k
hi,ji
e
e hi,ji ,
J1 и H
и, проведя элементарные вычисления, получить значения матриц T
k
k
указанные в теореме.
Собрав все вышесказанное, мы получаем, что:
=
Phi;ji
c
(Thi,ji
1
· Thi,ji × Pc .
× Pc )[0]
(8)
Мы описали процесс пропагации детерминированного свидетельства. Заметим,
что в более ранних работах [8, 13] процесс пропагации детерминированного свидетельства предлагалось делать в несколько шагов:
1) замена переменных таким образом, чтобы поступившее свидетельство содержало только положительную часть;
2) пропагация положительно означенного свидетельства;
3) обратная замена переменных.
Такой подход естественен, так как пропагацию положительно означенного свидетельства можно легко провести, не переходя от вероятностей конъюнктов к вероятностям квантов. Благодаря доказанной выше теореме, мы уже знаем, что пропагацию
положительного свидетельства hm; 0i можно провести, домножив исходные оценки
на Thm,0i и поделив на нормировочный коэффициент.
Покажем, как провести указанную замену, и докажем, что при таком подходе
результат совпадет с доказанным выше.
Пусть задан непротиворечивый вектор вероятностей Pc над множеством атомарных пропозиций {x0 , x1 , . . . , xn−1 }. Как, имея эти данные, выразить через него вектор
h−1i
Pc , который представляет собой вектор вероятностей, аналогичный Pc , но построенный над множеством атомов {x̄0 , x1 , . . . , xn−1 }? Верхний индекс вида h−ki мы будем
использовать для обозначения атомарных пропозиций, получающих отрицательное
означивание, при этом само k — максимальный индекс конъюнкта, состоящий только
из отрицательно означенных атомов, входящих в свидетельство.
Теорема 3. Оценки вероятностей конъюнктов, после замены части атомарных переменных на их отрицания, могут быть найдены по формуле
Ph−ki
= Bh−ki × Pc ,
c
где
e h−ki ⊗ B
e h−ki ⊗ . . . B
e h−ki ,
Bh−ki = B
n−1
n−2
0
69
причем
e h−ki
B
i
 1



1
=
1



0
0
, если x̃i = x̄i ,
−1 0
, если x̃i = xi .
1
h−1i
h−1i
Доказательство. Рассмотрим Pq = In × Pc и Pq
= In × Pc . Заметим, что
h−1i
векторы Pq и Pq
отличаются только порядком элементов. Построим соответствующую матрицу переходов

 0 1
0
0
0


1 0




0
1


0
0
0


h−1i
1
0
A
=
.


.
.

. 0 
0
0




0 1
0
0
0
1 0
В общем случае матрица
Ah−ki = Ãn−1 ⊗ . . . ⊗ Ã0 ,
где
 0



1
Ãi =
1



0
1
, если x̃i = x̄i ,
0 0
, если x̃i = xi .
1
Здесь x̃i = x̄i соответствует случаю, когда i-я переменная переозначивается (i-й бит
k равен единице). Заметим, что если мы изменим матрицу Ãi с одного возможного
значения на другое, то для матрицы A такая замена приведет к перестановке строчек. При этом строки, «отвечающие» за вхождение xi , поменяются со строчками,
«отвечающими» за вхождение x̄i . Можно так же показать, что матрица Ah−ki будет
содержать по одной единице в каждой строке, при этом i–я строка будет содержать
единицу в столбце с номером (i ∧ ¬k) ∨ (¬i ∧ k), логические операции здесь следует
читать как побитовые.
Матрица Ah−ki задает нам переозначивание на квантах. Построим на ее основе
матрицу Bh−ki , определяющую оператор переозначивания на конъюнктах:
Ph−ki
= Jn × Pqh−ki = Jn × (Ah−ki × Pq ) =
c
= Jn × (Ah−ki × (In × Pc )) = (Jn × Ah−ki × In ) × Pc ;
получаем, что
Bh−ki = Jn × Ah−ki × In × Pc =
e h−ki ⊗ A
e h−ki ⊗ . . . A
e h−ki ) × (I1 ⊗ . . . ⊗ I1 ) =
= (J1 ⊗ . . . ⊗ J1 ) × (A
n−1
n−2
0
h−ki
h−ki
h−ki
e
e
e
= (J1 × A
n−1 × I1 ) ⊗ (J1 × An−2 × I1 ) ⊗ . . . ⊗ (J1 × A0
=
70
e h−ki
B
n−1
⊗
e h−ki
B
n−2
⊗
e h−ki ,
...B
0
× I1 ) =
откуда можно вывести, что
 1
0


, если x̃i = x̄i ,

1 −1 B̃i =
1
0


, если x̃i = xi .

0
1
Что и требовалось доказать.
Мы описали оператор преозначивания, действующий на вероятности конъюнктов.
Теорема 4. Пусть задан непротиворечивый фрагмент знаний со скалярными
оценками, и поступило детерминированное свидетельство, содержащее отрицательно означенные атомы. Тогда результаты пропагации через переозначивание
будут совпадать с результатами пропагации с помощью матрицы T.
Доказательство. Благодаря свойствам кронекерова произведения нам достаточно проверить, что
T− = Bh−1i × T+ × Bh−1i .
Подставив числа легко увидеть, что это так:
1 −1
1
0
0 1
1
0
=
×
×
.
0
0
1 −1
0 1
1 −1
Формула (8) дает нам точное выражение для апостериорной вероятности элементов ФЗ при поступившем свидетельстве, если исходные оценки были скалярные
(то есть оценки вероятности конъюнктов имели вид Pc [l] = pl , где pl — числа из интервала [0; 1]). Если оценки были не скалярные, а интервальные, то нам потребуется
решать серию ЗЛП [8].
Пусть задан ФЗ с оценками P− и P+ , тогда опишем ЗЛП для получения апостериорной вероятности на элементах ФЗ. Полученная формула однородна по Pc ,
то есть, если подставить вместо него λ · Pc , где λ > 0, то результат не изменится.
Рассмотрим в качестве переменных нашей ЗЛП λ · Pc [l] и обозначим их через d[l].
Очевидно, что d[0] = λ. Над новыми переменными можно выписать ограничения
вида d[l] 6 λP+ [l] и λP− [l] 6 d[l], кроме этого мы должны включить ограничения
In × d > 0. Кроме указанных ограничений, добавим ограничения (Thi,ji × Pc )[0] = 1
и λ > 0. Внеся это ограничение, мы ничего не потеряем, так как всегда можно подобрать такое λ > 0, что это будет верно, а в силу однородности мы не исключим не
hi,ji
одного возможного значения для элементов Pc
(подробнее применительно к АБС
можно посмотреть в [8], а применительно к общему случаю сведения задачи гиперболического программирования к ЗЛП — в [14]). Последнее ограничение позволяет
hi,ji
hi,ji
переписать выражение для Pc , а именно Pc = Thi,ji × d.
Теперь нам осталось только решить полученные ЗЛП и найти при заданных
hi,ji
условиях максимумы и минимумы для элементов Pc [l], они и будут оценками апостериорной вероятности.
7. Заключение. Мы рассмотрели все основные виды локального логиковероятностного вывода в АБС: поддержание непротиворечивости, априорный и апостериорный виды вывода, — представив соответствующие формулы для вычислений
на матрично-векторном языке. Полученные ЗЛП могут быть без особых трудностей
71
решены на ЭВМ, более того, матричные и векторные структуры, описанные в статье,
имеют достаточно простое и эффективное машинное представление в виде массивов.
Однако открытым остается вопрос, можно ли упростить предложенные матричные
операции и, тем самым, сократить вычислительную сложность алгоритмов.
Литература
1. Городецкий В. И. Байесовский вывод. Препринт № 149. Л.: ЛИИАН, 1991. 38 с.
2. Городецкий В. И. Алгебраические байесовские сети — новая парадигма экспертных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной
техники и автоматизации РАН. Т. 2. М.: РАН, 1993. С. 120–141.
3. Городецкий В. И., Тулупьев А. Л. Формирование непротиворечивых баз знаний с
неопределенностью // Изв. РАН. Сер. Теория и системы управления. 1997. Т. 5. C. 33–42.
4. Nilsson N. J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 47. Amsterdam: Elsevier Science Publishers B. V., 1986. P. 71–87.
5. Тулупьев А. Л. Алгебраические байесовские сети: локальный логико-вероятностный
вывод: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Изд-во «Анатолия», 2007. 80 c.
6. Тулупьев А. Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Издво С.-Петерб. ун-та, 2008. 140 c.
7. Тулупьев А. Л., Сироткин А. В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационноизмерительные и управляющие системы. 2008. Т. 6, № 10. С. 85–87.
8. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
9. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та,
2009. 400 c.
10. Беллман Р. Введение в теорию матриц. М.: Наука. Гл. редакция физико-математической литературы, 1969. 368 с.
11. Тулупьев А. Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Т. 1, № 1. С. 57–93.
12. Сироткин А. В., Тулупьев А. Л. Локальный априорный вывод в алгебраических
байесовских сетях: комплекс основных алгоритмов // Труды СПИИРАН. Вып. 5. 2007. СПб.:
Наука, 2007. С. 100–111.
13. Тулупьев А. Л. Алгебраические байесовские сети: логико-вероятностный подход к
моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 c.
14. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями: учеб. пособие. Л.: Изд-во Ленингр. ун-та, 1984. 175 с.
Статья поступила в редакцию 26 апреля 2012 г.
72
1/--страниц
Пожаловаться на содержимое документа