Ярусный подход к представлению байесовских сетей
Предлагается ярусный подход к представлению байесовских сетей, который позволяет отслеживать существующие в них информационные взаимосвязи, обеспечивает содержательную интерпретацию полученных результатов и обосновывает корректность избранного порядка перебора каузальных отношений. Подход позволяет...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84571 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Ярусный подход к представлению байесовских сетей / О.В. Веревка, И.Н. Парасюк // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 83-93. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860069982494261248 |
|---|---|
| author | Веревка, О.В. Парасюк, И.Н. |
| author_facet | Веревка, О.В. Парасюк, И.Н. |
| citation_txt | Ярусный подход к представлению байесовских сетей / О.В. Веревка, И.Н. Парасюк // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 83-93. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Предлагается ярусный подход к представлению байесовских сетей, который позволяет отслеживать существующие в них информационные взаимосвязи, обеспечивает содержательную интерпретацию полученных результатов и обосновывает корректность избранного порядка перебора каузальных отношений. Подход позволяет избежать дублирования вычислений в пределах доступного объема памяти и может быть использован для создания методов анализа нечетких байесовских сетей при параллельной организации вычислений.
Пропонується ярусний підхід до представлення байєсівських мереж, який дозволяє відстежувати наявні в них інформаційні взаємозв’язки, забезпечує змістовну інтерпретацію отриманих результатів та обґрунтовує коректність обраного порядку перебору каузальних відношень. Підхід дозволяє уникнути дублювання обчислень у межах доступного обсягу пам’яті та може бути використаний для створення методів аналізу нечітких байєсівських мереж при паралельній організації обчислень.
The multilevel approach to the Bayesian networks presantation is proposed. It allows to watch present informative intercommunications, provides the content interpretation of the obtained results and proves the correctness of the chosen order of causal relation surplus. The approach allows avoiding duplication of calculations within the limits of accessible memory and can be used for creation of the methods for fuzzy Bayesian networks analysis in parallel calculations.
|
| first_indexed | 2025-12-07T17:09:30Z |
| format | Article |
| fulltext |
Компьютерная математика. 2010, № 1 83
Ýêñïåðòíûå ñèñòåìû,
ìåòîäû èíäóêòèâíîãî
âûâîäà
Предлагается ярусный подход к
представлению байесовских се-
тей, который позволяет отсле-
живать существующие в них ин-
формационные взаимосвязи, обес-
печивает содержательную ин-
терпретацию полученных резуль-
татов и обосновывает коррект-
ность избранного порядка пере-
бора каузальных отношений. Под-
ход позволяет избежать дублиро-
вания вычислений в пределах дос-
тупного объема памяти и может
быть использован для создания
методов анализа нечетких байе-
совских сетей при параллельной
организации вычислений.
О.В. Веревка, И.Н. Парасюк,
2010
ÓÄÊ 681.3: 06.51
Î.Â. ÂÅÐÅÂÊÀ, È.Í. ÏÀÐÀÑÞÊ
ßÐÓÑÍÛÉ ÏÎÄÕÎÄ
Ê ÏÐÅÄÑÒÀÂËÅÍÈÞ
ÁÀÉÅÑÎÂÑÊÈÕ ÑÅÒÅÉ
Процесс решения задач на байесовских сетях
(БС) обычно происходит в два этапа: на пер-
вом этапе оцениваются вероятности для всех
переменных сети, на втором – осуществляет-
ся перераспределение и оценивание вероят-
ностей переменных с учетом поступившей
информации о состояниях некоторого под-
множества переменных данной сети. При этом
базовой информацией в процессах оценивания
служат априорные вероятностные оценки кау-
зальных отношений типа «родители → дети»,
которые, обычно, задаются экспертно.
Компьютеризация процессов оценивания
вероятностей переменных сети является
ключевой проблемой, в общем случае даже в
четком информационном пространстве слож-
ной не только с вычислительной точки зре-
ния (по вычислительной сложности она от-
носится к NP-сложным задачам). Важными
также являются содержательная интерпрета-
ция полученных результатов, обоснование
корректности избранного порядка перебора
каузальных отношений, исключение дубли-
рования в вычислениях в пределах доступно-
го объема памяти и др. Современные подхо-
ды к компьютеризации этих процессов осно-
ваны на трансформации графа сети в узловое
дерево [1, 2]. Они позволяют существенно
уменьшить объем вычислений, что весьма
примечательно, однако не решает других,
вышеотмеченных, вопросов, которые при
переходе в нечеткое информационное про-
странство еще в большей степени обостря-
ются, поскольку в этих случаях появляется
добавочное измерение функции принадлеж-
ности, что существенно увеличивает объемы
вычислений и усложняет логику зависи-
мостей в сети.
О.В. ВЕРЕВКА, И.Н. ПАРАСЮК
Компьютерная математика. 2010, № 1 84
Следовательно, разработка новых эффективных способов представления БС,
которые позволяли бы в комплексе решать перечисленные проблемы, включая
возможность привлечения многопроцессорных комплексов с параллельной ор-
ганизацией вычислений, является весьма актуальной и интересной задачей.
В данной работе предлагается подход к представлению БС, основанный на
ярусной структуризации графа. Разработанный как основа для создания БС в
нечетком информационном пространстве, он позволяет отслеживать информа-
ционные потоки и естественным образом определяет их взаимодействие, позво-
ляя реализовать сеть с параллельной организацией вычислений.
Базовым является понятие яруса вершин: это множество вершин одного по-
коления, которое определяется одинаковым максимальным расстоянием от кор-
невых (начальных) вершин сети. Вычисления выполняются последовательно
снизу вверх от старших, т. е. более близких к корневым вершинам, ярусов до
самых младших. Переход на следующий ярус выполняется исключительно по-
сле полной отработки предыдущего и при вычислениях последовательно ис-
пользуются уже просчитанные промежуточные оценки условных вероятностей
для вершин-предков из старших ярусов. Используется следующая система обо-
значений для оценок вероятностей событий, заданных в скобках: P
~
– начальные
экспертные оценки; Р – вычисляемые априорные оценки; Р∗ – апостериорные
оценки.
1. Структурирование матрицы смежности вершин
Пусть G – ориентированный ацикличный граф с множеством вершин
V(G) = {an} GN
n 1= и матрицей смежности вершин M(G) = {µnm} GN
n 1=
GN
m 1= , где µnm = 1,
если в графе G присутствует ориентированное ребро (аn, ат), и µnm = 0 в про-
тивном случае. Назовем корневой цепью для вершины аn каждый ориентирован-
ный маршрут с концом в аn и началом в корневой вершине, из которой аn дости-
жима. Для вершины аn определим ярусный показатель λ(аn) как максимальную
длину корневых цепей для аn.
Далее будем рассматривать структурированное представление сети G как
ориентированного ациклического графа, для которого определены следующие
характеристики:
1) количество ярусов (L+1) и последовательность их мощностей k0, k1, ..., ;lk
2) множество вершин V(G) = {vn} GN
n 1= , NG = ∑
=
L
l
lk
0
. Вершина vn находится в
состоянии Vn , Vn ∈{V nj
n } n
n
J
j 1= , Jn ≥ 2, причем допустимые состояния {V nj
n } n
n
J
j 1=
образуют полную группу (случай Jn = 2 наиболее важен). Для каждой из вершин
определен ярусный показатель λ(vn). Вершины {vn} 0
1
k
n= являются корневыми
ЯРУСНЫЙ ПОДХОД К ПРЕДСТАВЛЕНИЮ БАЙЕСОВСКИХ СЕТЕЙ
Компьютерная математика. 2010, № 1 85
(λ(vn) = 0), они образуют нулевой ярус мощностью k0. Вершины {vn} l
l
K
Kn 11 += −
,
где Kl =∑
=
l
t
tk
0
, l = L,1 образуют l-й ярус (λ(vn) = l ) мощностью ;lk
3) матрица смежности Ω(G) = {ωnm} GN
n 1=
GN
m 1= вершин V(G) в блочном пред-
ставлении:
v1 …
0Kv 10 +Kv … 1Kv … 11+−mKv …
mKv … 11+−LKv …
LKv
v1
…
0Kv
0
БЛОК01
…
БЛОК0m
…
БЛОК0L
10 +Kv
…
1Kv
0
0
…
БЛОК1m
…
БЛОК1L
… 0 0 … … … …
11+−lKv
…
lKv
0
0
…
БЛОКlm
…
БЛОКlL
… 0 0 … … … …
11+−LKv
…
LKv
0
0
0
0
0
0
БЛОКlm – прямоугольная матрица {ωij} l
l
K
Ki 11+= −
m
m
K
Kj 11+= −
размерностью
kl × kт, которая при l ≥ т (т. е. все блоки главной диагонали и ниже) полностью
заполнена нулями;
4) матрица достижимости Θ(G) = {θmn} GN
n 1=
GN
m 1= вершин V(G) в аналогичном
блочном представлении, где θmn = 1, если в графе G можно построить ориенти-
рованный маршрут из вершины vm в vn, и θmn = 0 в противном случае;
5) исходная экспертная информация. Для корневых вершин {vn} 0
1
k
n= заданы
априорные оценки вероятностей { P
~
(Vn = V nj
n )} n
n
J
j 1= , всего ∑
=
0
1
(
k
n
nJ – 1) оценок
(далее используется обозначение P
~
(V nj
n ) = P
~
(Vn = V nj
n )).
О.В. ВЕРЕВКА, И.Н. ПАРАСЮК
Компьютерная математика. 2010, № 1 86
Введем обозначение pr(vn) для множества родителей некорневой вершины
vn. Задана совокупность прямых связей в сети P
~
(vn / pr(vn)) – оценки условных
вероятностей допустимых состояний вершины vn относительно допустимых со-
стояний ее родителей [{ P
~
(V nj
n / ∩
1
1
[
−
=
lK
m
V mj
m ⊗ωmn])} m
m
J
j 1= ] n
n
J
j 1= , где сочетание сим-
волов [V mj
m ⊗ωmn] означает следующее: соответствующее допустимое состояние
вершины vm присутствует в представленном идентификаторе оценки условной
вероятности как компонент пересечения условий при ωmn ≠ 0 (vm ∈ pr(vn))
и отсутствует в противном случае (всего ∑
+= −
l
l
K
Kn
nJ
11
( – 1) ∑
−
=
1
1
ω
lK
m
mmnJ оценок).
В условии состояния обязательно присутствует хотя бы одна вершина предыду-
щего яруса (Kl–2 +1≤m≤ Kl–1).
Структурированное представление сети G по матрице смежности M(G) вер-
шин {an} GN
n 1= можно получить следующим образом.
Начальный шаг. Номер яруса L:= 0.
K–1 := 0. Выберем среди вершин {an} GN
n 1= корневые (для корневой вершины
ат ∀ GNn ,1= µnm = 0 ). Пусть оказалось k0 корневых вершин {a 0
ji
} 0
1
k
j= . Присво-
им каждой корневой вершине по дополнительному альтернативному имени,
U0(G) = {a 0
ji
} 0
1
k
j= = {vj} 0
1
k
j= . Будем считать, что корневые вершины имеют ярус-
ный показатель λ(vn) = 0 и образуют нулевой ярус мощностью k0. Исключаем их
из дальнейшего рассмотрения,
W(G) := V(G)\U0(G). I 0 = {
0
ji } 0
1
k
j= . K0 := K–1 + k0.
Основной шаг. Номер яруса L:= L + 1.
Выберем среди W(G) вершины, ярусный показатель которых равен L (для
такой вершины ат ∀ GNn ,1= , n ∉∪
1
0
−
=
L
l
lI , µnm = 0). Пусть оказалось kL таких
вершин {a L
ji
} Lk
j 1= . KL := KL–1 + kL. Присвоим каждой вершине a L
ji
по дополни-
тельному альтернативному имени, UL(G) = {a L
ji
} Lk
j 1= = {vj} L
L
K
Kj 11+= −
. Будем счи-
тать, что вершины UL(G) образуют L-й ярус мощностью kL, для них λ(vn) = L,
и исключаем их из дальнейшего рассмотрения,
W(G) := W(G)\UL(G). IL = {
L
ji } Lk
j 1= .
ЯРУСНЫЙ ПОДХОД К ПРЕДСТАВЛЕНИЮ БАЙЕСОВСКИХ СЕТЕЙ
Компьютерная математика. 2010, № 1 87
Если W(G) ≠ ∅, повторяем основной шаг.
Если W(G) = ∅, то KL=NG, вершины V(G) графа G распределены в (L+1)
ярус, на l-м ярусе находится kl вершин {vj} l
l
K
Kj 11+= −
. Переставим строки и столб-
цы M(G) = {µnm} GN
n 1=
GN
m 1= в соответствии с индексами альтернативных имен
вершин с упорядочением по возрастанию.
В случае 0 ≤ l < т ≤ L БЛОКlm – прямоугольная матрица
{ωij} l
l
K
Ki 11+= −
m
m
K
Kj 11+= −
размерностью kl × kт и имеет следующий вид:
БЛОКlm
11+−mKv … jKm
v +−1
…
mKv
11+−lKv
ω 1,1 11 ++ −− ml KK =
= µ li1
mi1
... ω jKK ml ++ −− 11 ,1 =
= µ li1
m
ji
...
ω
ml KK ,11 +−
= µ li1
m
mki
… ... ... ... ... ...
tKl
v +−1
ω 1, 11 ++ −− ml KtK =
= µ l
ti
mi1
... ω jKtK ml ++ −− 11 , =
= µ l
ti
m
ji
...
ω
ml KtK ,1 +−
= µ l
ti
m
mki
… ... ... ... ... ...
lKv ω 1, 1+−ml KK = µ l
lki
mi1
... ω jKK ml +−1, = µ l
lki
m
ji
... ω
ml KK , = µ l
lki
m
mki
Обычно наиболее плотно заполненными в матрице смежности являются
блоки с разностью 1 между вторым и первым индексами, регламентирующие
связь между двумя последовательными ярусами; блоки при т > l + 1 могут
состоять исключительно из нулей.
Аналогичную блочную структуру имеет также матрица достижимости
Θ(G) = {θmn} GN
n 1=
GN
m 1= вершин графа G. Очевидно, для вершины vn, находящейся
на l-м, l ≥ 1, ярусе, каждый из предыдущих l ярусов представлен хотя бы одной
вершиной. Матрицу достижимости вершин Θ(G) можно получить из матрицы их
смежности Ω(G) следующим образом.
Для n = LK,1 :
для 1≤ m ≤ K0 ( {БЛОК0, l}
L
l 1= ) θmn := ωmn;
для K0 + 1≤ m ≤ KL θmn := 0.
Для l = L,2 :
для (Kl–2+1≤ m ≤ Kl–1)∧(Kl–1+1≤ n ≤ Kl) ( {БЛОКl–1, l}
L
l 2= ) θmn := ωmn.
О.В. ВЕРЕВКА, И.Н. ПАРАСЮК
Компьютерная математика. 2010, № 1 88
Для l = L,2 :
для n = ll KK ,11 +− :
для m = 12 ,1 −− + ll KK :
если ωmn = 1, то ∀k = 2,1 −lK θkn := max{ωkn, θkm}.
Для вершины vn, находящейся на l-м, l ≥ 1, ярусе, назовем множеством дос-
тижимости ψ(vn) упорядоченное по возрастанию индекса множество вершин
старших ярусов, из которых можно попасть в vn: ψ(vn) = {[vm ⊗ θmn]} 1
1
−
=
lK
m . Соче-
тание символов [vm ⊗ θmn] означает, что вершина vm присутствует в последова-
тельности ψ(vn) при θmn ≠ 0 и отсутствует в противном случае. Очевидно, все
ярусы от нулевого до (l – 1)-го представлены хотя бы одной вершиной. Множе-
ство достижимости ψ(vn) определяет путь, который следует преодолеть, чтобы
достигнуть вершины vn из корневых вершин. ψ
⌣
(vn) = {ψ(vn) ∪ vn}. Назовем
вершины ориентированного графа независимыми, если их множества достижи-
мости не пересекаются, и зависимыми в противном случае.
2. Порядок распространения априорных вероятностей в структуриро-
ванной байесовской сети в точечном информационном пространстве
Структурированные матрица смежности Ω(G) и матрица достижимости
Θ(G) вершин V(G) = {vn} GN
n 1= – основа для планирования вычислительного про-
цесса при ярусном подходе. Рассмотрим принципиальную схему априорного
оценивания вероятностей для всех переменных БС.
Пусть ψ(vn) = {v
tn } nT
t 1= , Тn ≥ 1 – множество достижимости вершины vn,
не являющейся корневой (λ(vn) ≥ 1), и G(vn) ⊆ G – соответствующий множеству
ψ
⌣
(vn) подграф графа G. Назовем v
∗n ∈ ψ(vn) истоком для вершины vn, если
– v
∗n – разделяющая вершина графа G(vn) либо корневая вершина;
– на цепях, соединяющих n∗
ν с ,nν разделяющих в G(vn) вершин нет.
Таким образом, истоки вершины – это самые молодые разделяющие верши-
ны графа G(vn), которые входят в множества достижимости родительских вер-
шин или являются ими. Истоки, отличные от корневых вершин, аккумулируют
всю информацию относительно своего множества достижимости, необходимую
для определения текущей оценки. Если ярусный показатель λ ( n∗
ν ) ≥ 1, спра-
ведливы следующие утверждения, полезные для выявления истоков.
1. ∀({vk}
( )
0 1
vn
K
k K
λ ∗
= + , vk ∈ψ(vn) \ψ
⌣
( nν
∗
) ) и ∀(vs∈ψ(v n∗
)): θsk = 0.
2. ∀({vk}
( )
( ) 1
vn
vn
K
k K
λ
λ ∗
= + , vk ∈ψ(vn) ) и ∀(vs∈ψ(v n∗
)): ωsk = 0.
ЯРУСНЫЙ ПОДХОД К ПРЕДСТАВЛЕНИЮ БАЙЕСОВСКИХ СЕТЕЙ
Компьютерная математика. 2010, № 1 89
Под родительской трансформацией Ψ pr (vn) множества истоков Ψ(vn) вер-
шины vn будем понимать множество, состоящее из ее родительских вершин и
тех истоков, которые входят в множество достижимости более чем одной роди-
тельской вершины.
Назовем реализацией {[V mj
m ⊗ θmn]} 1
1
−
=
lK
m множества достижимости ψ(vn) со-
бытие, когда вершины ψ(vn) сети пребывают в каких-то фиксированных кон-
кретных состояниях. Заметим, что события
{[V mj
m ⊗ θmn] 1
1
−
=
lK
m } = { ∩
1
}[{
−≤
=
l
m
Km
j
mm VV ⊗ θmn]},
во-первых, не пересекаются при разных комплектах индексов {jm} 1
1
−
=
lK
m , и, во-
вторых, образуют полную группу. Оценку P(V
∗
n ) вероятности того, что вершина
vn c ярусным показателем l = λ(vn) ≥ 1 находится в состоянии V
∗
n , целесообразно
получить как сумму оценок вероятностей при всех возможных реализациях
множества достижимости ψ(vn), т. е как сумму по {jm = mJ,1 } 1
1
−
=
lK
m оценок веро-
ятностей (V
∗
n ; {[V mj
m ⊗ θmn]} 1
1
−
=
lK
m ):
P(V
∗
n ) = ∑ ∑
=⊗ =⊗
−
−−
1
11
1
,111θ 1θ
(...
J
j
J
j
n
n
lK
nlKlK
VP = V
∗
n ; { ∩
1
}[{
−≤
=
l
m
Km
j
mm VV ⊗ θmn]}) =
= ∑ ∑
=⊗ =⊗
−
−−
1
11
1
,111θ 1θ
(...
J
j
J
jn
lK
nlKlK
P V
∗
n ; { ∩
1
[
−≤ l
m
Km
j
mV ⊗ θmn]}),
где обозначение ∑
=⊗
m
mnm
J
j 1θ
означает, что суммирование по соответствующему
индексу jm выполняется лишь при θmn = 1, т. е. при vm ∈ ψ(vn). Оценка вероятно-
сти реализации P(V
∗
n ; {[V mj
m ⊗θmn]} 1
1
−
=
lK
m ) вычисляется по формуле умножения
вероятностей для пересечения событий, сгруппированных в соответствии с
ярусной принадлежностью:
V
∗
n , {[V mj
m ⊗θmn], m = 12 ,1 −− + ll KK },…, {[V mj
m ⊗θmn], m = 0,1 K }.
О.В. ВЕРЕВКА, И.Н. ПАРАСЮК
Компьютерная математика. 2010, № 1 90
При этом оценки вероятности для состояний вершин, принадлежащих
одному ярусу, относительно всех предыдущих определяются произведением
априорных оценок состояний этих вершин относительно соответствующих
состояний их родителей:
P(V
∗
n ; {[V mj
m ⊗ θmn], m ≤ Kl–1}) =
= P(V
∗
n ∩{[V mj
m ⊗ θmn], m = 12 ,1 −− + ll KK }∩…∩{[V mj
m ⊗ θmn], m = 0,1 K }) =
:= P
~
(V
∗
n /{[ ∩
1
1
[
−
=
lK
m
V mj
m ⊗ωmn]})× ∏
−
− +=
1
2 1
l
l
K
Km
P
~
({[V mj
m ⊗θmn]}/{ ∩
2
1
[
−
=
l
s
K
s
j
sV ⊗ωsm]}) ×…×
× ∏
+=
1
0 1
({[
~
K
Km
j
m
mVP ⊗ θmn]} / {∩
0
1
[
K
s
j
s
sV
=
⊗ ωsm] }) ×∏
=
0
1
({[
~
K
m
j
m
mVP ⊗ θmn]} =
= P
~
(V
∗
n /{[ ∩
1
1
[
−
=
lK
m
V mj
m ⊗ωmn]})×∏ ∏
−
= +=
−−
−−
2
0 1
1
2
({[
~
l
t
K
Km
tl
tl
P V mj
m ⊗θmn]}/{ ∩
tl
s
K
s
j
sV
−−
=
2
1
[ ⊗ωsm]})×…×
×∏
=
0
1
({[
~
K
m
j
m
mVP ⊗ θmn]}.
В сильно связанных графах истоками являются корневые вершины, и при-
веденные соотношения реализуются в полном объеме. Другой крайностью яв-
ляются деревья, у которых каждая отцовская вершина – исток для сыновней.
Для рационального выполнения вычислений в общем случае производится пе-
реход от оценивания вероятности состояния вершины по всему множеству дос-
тижимости к ее определению по множеству истоков или его родительской
трансформации. Представить это можно следующим образом. Последовательно,
от корневого яруса вверх, анализируются связи всех вершин одного яруса. Для
каждой вершины определяется множество истоков и его родительская транс-
формация. Составляется реестр вспомогательных оценок: это все условные ве-
роятности родителей относительно истоков, оставшихся в родительской транс-
формации множества истоков их сыновних вершин, а также, если отцовские
вершины принадлежат одному ярусу и зависимы или имеют несколько сынов-
них вершин, условные при наличии взаимозависимости или безусловные оценки
их совместной вероятности. Вспомогательные оценки сохраняются также и для
апостериорного оценивания. {Вероятность текущего состояния сыновней вер-
шины} оценивается как сумма произведений трех (или двух, если все истоки
являются отцовскими вершинами) сомножителей вида {априорная условная ве-
роятность текущего состояния сыновней вершины относительно состояний от-
цовских вершин} × {условная вероятность состояний отцовских вершин относи-
тельно состояний выделенных истоков} × {безусловная вероятность состояний
истоков}.
ЯРУСНЫЙ ПОДХОД К ПРЕДСТАВЛЕНИЮ БАЙЕСОВСКИХ СЕТЕЙ
Компьютерная математика. 2010, № 1 91
3. Пример простой сети
В заключение рассмотрим вычисление априорных оценок для простой сети
с высокой степенью связности, показанное на рис. 1. NG = 11, V(G) = {vn}
11
1=n .
Сеть бинарна, ∀n = 11,1 Jn = 2, Vn ∈{V
1
n , V
2
n }, так что P
~
(V
2
n ) = 1 – P
~
(V
1
n )
и P
~
(V
2
n /при условии ...) = 1 – P
~
(V
1
n /при том же условии). Символ 2,1
nV озна-
чает, что соответствующие оценки вероятностей рассматриваются для обоих
состояний V1
n и V 2
n .
РИС. 1. Пример структурированной
байесовской сети
L = 3, k0 = 3, k1 = 3, k2 = 2, k3 = 3.
Заданы априорные оценки
{ P
~
( 1,2
nV )}
3
1=n ;
{ P
~
( 1,2
nV / 2,1
1V , 2,1
2V )}
6
4=n ;
P
~
( 2,1
7V / 2,1
4V , 2,1
5V );
P
~
( 2,1
8V / 2,1
2V , 2,1
4V , 2,1
5V );
P
~
( 2,1
9V / 2,1
1V , 2,1
7V );
P
~
( 2,1
10V / 2,1
6V , 2,1
8V );
P
~
( 2,1
11V / 2,1
3V , 2,1
8V ).
Матрица смежности вершин
Ω(G) = {ωmn}
11
1=n
11
1=m .
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11
v1 1 1 1 0 0 1 0 0
v2 1 1 1 0 1 0 0 0
v3
0
0 0 0 0 0 0 0 1
v4 1 1 0 0 0
v5 1 1 0 0 0
v6
0
0
0 0 0 1 0
v7 1 0 0
v8
0 0 0
0 1 1
v9
v10
v11
0
0
0
0
Матрица достижимости вершин
Θ(G) = {θmn}
11
1=n
11
1=m .
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11
v1 1 1 1 1 1 1 1 1
v2 1 1 1 1 1 1 1 1
v3
0
0 0 0 0 0 0 0 1
v4 1 1 1 1 1
v5 1 1 1 1 1
v6
0
0
0 0 0 1 0
v7 1 0 0
v8
0 0 0
0 1 1
v9
v10
v11
0
0
0
0
v4 v7
v1 v9
v5
v2 v8
v6 v10
v3 v11
О.В. ВЕРЕВКА, И.Н. ПАРАСЮК
Компьютерная математика. 2010, № 1 92
Сохраняемые вспомогательные оценки, которые обусловливает:
– первый ярус. Вершины {vn}
6
4=n с множествами истоков {Ψ(vn)}
6
4=n = {v2, v1},
принадлежащих одному ярусу. Следует определить {Р( 2,1
2V , 2,1
1V )};
– второй ярус. Вершины v7 и v8 с множествами истоков Ψ (v7) = Ψ (v8) = {v2, v1},
Ψ pr (v7) = Ψ pr (v8) = {v5, v4; v2, v1}, отцовские вершины v5 и v4 расположены на
одном ярусе. Следует определить {Р( 2,1
5V , 2,1
4V / 2,1
2V , 2,1
1V )};
– третий ярус. Вершины {vn}
11
9=n с множествами истоков Ψ(v9) = {v2, v1},
Ψ(v10) = {v2, v1}, Ψ(v11) = {v8; v3}; Ψpr(v9) = {v7; v1}, Ψpr(v10) = {v8; v6; v2, v1},
Ψpr(v11) = {v8; v3}. Следует определить {Р( 2,1
7V / 2,1
1V )} и, поскольку отцовские
вершины v8 и v6 принадлежат различным ярусам, {Р( 2,1
8V / 2,1
2V , 2,1
1V )}.
Последовательность вычислений.
Нулевой ярус. Р( 2,1
2V , 2,1
1V ):= P
~
( 2,1
2V ) × P
~
( 2,1
1V ).
Первый ярус. Р(V nj
n ) := ∑
=
2
1, 12
(
~
jj
P V nj
n / V 2
2
j
, V 1
1
j
) × Р(V 2
2
j
, V 1
1
j
), n = 6,4 ;
Р( 2,1
5V , 2,1
4V / 2,1
2V , 2,1
1V ) := P
~
( 2,1
5V / 2,1
2V , 2,1
1V ) × P
~
( 2,1
4V / 2,1
2V , 2,1
1V ).
Второй ярус.
Р(V 7
7
j
/V 1
1
j
) := ∑ ∑
= =
2
1,
2
145 2
(
~
jj j
P V 7
7
j
/V 5
5
j
, V 4
4
j
) × Р(V 5
5
j
, V 4
4
j
/V 2
2
j
, V 1
1
j
) × P
~
(V 2
2
j
),
Р(V 8
8
j
/V 2
2
j
, V 1
1
j
) := ∑
=
2
1, 45
(
~
jj
P V 8
8
j
/V 5
5
j
, V 4
4
j
; V 2
2
j
) × Р(V 5
5
j
, V 4
4
j
/V 2
2
j
, V 1
1
j
);
Р(V 7
7
j
) :=∑
=
2
11
(
j
P V 7
7
j
/V 1
1
j
) × P
~
(V 1
1
j
),
Р(V 8
8
j
) := ∑
=
2
1, 12
(
jj
P V 8
8
j
/ V 2
2
j
, V 1
1
j
) × Р(V 2
2
j
, V 1
1
j
).
Третий ярус. Р(V 9
9
j
) := ∑ ∑
= =
2
1
2
17 1
(
~
j j
P V 9
9
j
/ V 7
7
j
, V 1
1
j
) × Р(V 7
7
j
/ V 1
1
j
) × P
~
(V 1
1
j
),
Р(V 10
10
j
) := ∑ ∑ ∑
= = =
2
1
2
1
2
1,8 6 12
(
~
j j jj
P V 10
10
j
/ V 8
8
j
, V 6
6
j
) × Р(V 8
8
j
/ V 2
2
j
, V 1
1
j
) ×
ЯРУСНЫЙ ПОДХОД К ПРЕДСТАВЛЕНИЮ БАЙЕСОВСКИХ СЕТЕЙ
Компьютерная математика. 2010, № 1 93
× P
~
(V 6
6
j
/ V 2
2
j
, V 1
1
j
) × Р(V 2
2
j
, V 1
1
j
),
Р(V 11
11
j
) := ∑ ∑
= =
2
1
2
18 3
(
~
j j
P V 11
11
j
/ V 8
8
j
, V 3
3
j
) × Р(V 8
8
j
) × P
~
(V 3
3
j
).
Заключение. Отметим, что изложенная методика построения алгоритмов
априорного оценивания вероятностей переменных байесовской сети применима
также для построения алгоритмов апостериорного оценивания.
О.В. Верьовка, І.М. Парасюк
ЯРУСНИЙ ПІДХІД ДО ПРЕДСТАВЛЕННЯ БАЙЄСІВСЬКИХ МЕРЕЖ
Пропонується ярусний підхід до представлення байєсівських мереж, який дозволяє відстежу-
вати наявні в них інформаційні взаємозв’язки, забезпечує змістовну інтерпретацію отрима-
них результатів та обґрунтовує коректність обраного порядку перебору каузальних відно-
шень. Підхід дозволяє уникнути дублювання обчислень у межах доступного обсягу пам’яті
та може бути використаний для створення методів аналізу нечітких байєсівських мереж при
паралельній організації обчислень.
О.V. Verovka, I.M. Parasjuk
THE MULTILEVEL APPROACH TO THE BAYESIAN NETWORKS PRESANTATION
The multilevel approach to the Bayesian networks presantation is proposed. It allows to watch pre-
sent informative intercommunications, provides the content interpretation of the obtained results and
proves the correctness of the chosen order of causal relation surplus. The approach allows avoiding
duplication of calculations within the limits of accessible memory and can be used for creation of
the methods for fuzzy Bayesian networks analysis in parallel calculations.
1. Pearl J. Probabilistic Reasoning Intelligent Systems: Networks of Plausible Inference. – Mor-
gan Kaufmann, San Mateo, CA, 1991. – 552 p.
2. Парасюк И.Н., Костукевич Ф.В. Методы трансформации байесовской сети для построе-
ния узлового дерева и их модификация // Компьютерная математика. – 2008. – № 1. –
С. 70–80.
Получено 09.10.2009
Îá àâòîðàõ:
Веревка Ольга Викторовна,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
Парасюк Иван Николаевич,
доктор технических наук, профессор, член-корреспондент НАН Украины,
заведующий отделом Института кибернетики имени В.М. Глушкова НАН Украины.
e-mail: ivpar1@i.com.ua
|
| id | nasplib_isofts_kiev_ua-123456789-84571 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T17:09:30Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Веревка, О.В. Парасюк, И.Н. 2015-07-10T14:43:32Z 2015-07-10T14:43:32Z 2010 Ярусный подход к представлению байесовских сетей / О.В. Веревка, И.Н. Парасюк // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 83-93. — Бібліогр.: 2 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84571 681.3: 06.51 Предлагается ярусный подход к представлению байесовских сетей, который позволяет отслеживать существующие в них информационные взаимосвязи, обеспечивает содержательную интерпретацию полученных результатов и обосновывает корректность избранного порядка перебора каузальных отношений. Подход позволяет избежать дублирования вычислений в пределах доступного объема памяти и может быть использован для создания методов анализа нечетких байесовских сетей при параллельной организации вычислений. Пропонується ярусний підхід до представлення байєсівських мереж, який дозволяє відстежувати наявні в них інформаційні взаємозв’язки, забезпечує змістовну інтерпретацію отриманих результатів та обґрунтовує коректність обраного порядку перебору каузальних відношень. Підхід дозволяє уникнути дублювання обчислень у межах доступного обсягу пам’яті та може бути використаний для створення методів аналізу нечітких байєсівських мереж при паралельній організації обчислень. The multilevel approach to the Bayesian networks presantation is proposed. It allows to watch present informative intercommunications, provides the content interpretation of the obtained results and proves the correctness of the chosen order of causal relation surplus. The approach allows avoiding duplication of calculations within the limits of accessible memory and can be used for creation of the methods for fuzzy Bayesian networks analysis in parallel calculations. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Экспертные системы, методы индуктивного вывода Ярусный подход к представлению байесовских сетей Ярусний підхід до представлення байєсівських мереж The multilevel approach to the Bayesian networks presantation Article published earlier |
| spellingShingle | Ярусный подход к представлению байесовских сетей Веревка, О.В. Парасюк, И.Н. Экспертные системы, методы индуктивного вывода |
| title | Ярусный подход к представлению байесовских сетей |
| title_alt | Ярусний підхід до представлення байєсівських мереж The multilevel approach to the Bayesian networks presantation |
| title_full | Ярусный подход к представлению байесовских сетей |
| title_fullStr | Ярусный подход к представлению байесовских сетей |
| title_full_unstemmed | Ярусный подход к представлению байесовских сетей |
| title_short | Ярусный подход к представлению байесовских сетей |
| title_sort | ярусный подход к представлению байесовских сетей |
| topic | Экспертные системы, методы индуктивного вывода |
| topic_facet | Экспертные системы, методы индуктивного вывода |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84571 |
| work_keys_str_mv | AT verevkaov ârusnyipodhodkpredstavleniûbaiesovskihsetei AT parasûkin ârusnyipodhodkpredstavleniûbaiesovskihsetei AT verevkaov ârusniipídhíddopredstavlennâbaiêsívsʹkihmerež AT parasûkin ârusniipídhíddopredstavlennâbaiêsívsʹkihmerež AT verevkaov themultilevelapproachtothebayesiannetworkspresantation AT parasûkin themultilevelapproachtothebayesiannetworkspresantation |