Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия
Рассмотрена общая схема алгоритма распространения вероятностей для байесовских сетей. Построен унифицированный алгоритм распространения доверия для нечетких байесовских сетей доверия, который базируется на новых принципах обхода узлового дерева, является более прозрачным и быстродействующим. Описана...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84592 |
| 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. — № 2. — С. 102-112. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860256243438845952 |
|---|---|
| author | Парасюк, И.Н. Костукевич, Ф.В. |
| author_facet | Парасюк, И.Н. Костукевич, Ф.В. |
| citation_txt | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия / И.Н. Парасюк, Ф.В. Костукевич // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 102-112. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассмотрена общая схема алгоритма распространения вероятностей для байесовских сетей. Построен унифицированный алгоритм распространения доверия для нечетких байесовских сетей доверия, который базируется на новых принципах обхода узлового дерева, является более прозрачным и быстродействующим. Описана структура этого алгоритма и исследованы условия его корректной работы. Описаны результаты моделирования основных операций с размытыми потенциалами, заданными над нечеткими байесовскими сетями доверия.
Розглянута загальна схема алгоритма розповсюдження ймовірностей над нечіткими байєсівськими мережами довіри. Побудовано уніфікований алгоритм розповсюдження довіри на основі розмитих потенціалів. Доведена коректність виконання цього алгоритма та вказані умови йогo застосування, за яких цей алгоритм є найбільш ефективним.
A general scheme of belief propagation algorithms above the fuzzy Bayesian networks of belief is considered. The new belief propagation algorithm is built on the basis of fuzzy potentials. Correctness of this implementation of algorithms is proved and conditions of his applications at which this algorithm is most effective are indicated.
|
| first_indexed | 2025-12-07T18:49:25Z |
| format | Article |
| fulltext |
102 Компьютерная математика. 2010, № 2
Рассмотрена общая схема алгорит-
ма распространения вероятностей
для байесовских сетей. Построен
унифицированный алгоритм рас-
пространения доверия для нечетких
байесовских сетей доверия, кото-
рый базируется на новых принципах
обхода узлового дерева, является
более прозрачным и быстро-
действующим. Описана структура
этого алгоритма и исследованы
условия его корректной работы.
Описаны результаты моделиро-
вания основных операций с раз-
мытыми потенциалами, заданными
над нечеткими байесовскими сетя-
ми доверия.
____________________
© И.Н. Парасюк,
Ф.В. Костукевич, 2010
ÓÄÊ 681.3
È.Í. ÏÀÐÀÑÞÊ, Ô.Â. ÊÎÑÒÓÊÅÂÈ×
ÎÁ ÎÄÍÎÌ
ÝÔÔÅÊÒÈÂÍÎÌ ÀËÃÎÐÈÒÌÅ
ÐÀÑÏÐÎÑÒÐÀÍÅÍÈß ÂÅÐÎßÒÍÎÑÒÅÉ
 ÍÅ×ÅÒÊÈÕ ÁÀÉÅÑÎÂÑÊÈÕ ÑÅÒßÕ
ÄÎÂÅÐÈß
Введение. Для эффективного вероятност-
ного вывода на классических байесовских
сетях доверия Перлом был разработан алго-
ритм распространения вероятностей (дове-
рия), использующий трансформированную
байесовскую сеть в виде узлового дерева, в
котором для достижения согласованности по
разделяемым переменным между верши-
нами использовался метод передачи сообще-
ний [1]. По этой же схеме Шпигельхальтер и
Лауритцен разработали подобные алгоритмы
и реализовали их в широко известной систе-
ме HUGIN [2]. Алгоритм распространения
доверия (АРД) в задачах анализа сетей
доверия играет главную роль – он позволяет
вычислить состояние всей исследуемой си-
стемы, имеющее наибольшее значение
вероятности, т. е. найти оптимальное ее
состояние. Другая интересная задача, решае-
мая с помощью этого алгоритма, – это вычи-
сление маргинальной вероятности состояний
для некоторого подмножества элементов
исследуемой системы. Кроме того, АРД,
использующий трансформированную байе-
совскую сеть, осуществляет как априорный
(без свидетельств), так и апостериорный (со
свидетельствами) вероятностный вывод.
Представляется, что развитие АРД приме-
нительно к нечетким байесовским сетям
доверия будет способствовать более адекват-
ному оцениванию как причинно-следствен-
ных связей систем в условиях неопреде-
ленности и неполноты данных, так и апосте-
риорных оценок доверия для различных
конфигураций свидетельств. Такой подход
ОБ ОДНОМ ЭФФЕКТИВНОМ АЛГОРИТМЕ РАСПРОСТРАНЕНИЯ ВЕРОЯТНОСТЕЙ В НЕЧЕТКИХ ...
Компьютерная математика. 2010, № 2 103
продолжительное время используется, например, в системе [3], в основе которой
– нечеткие деревоподобные байесовские сети доверия с недетерминирован-
ными состояниями.
Настоящая статья посвящена вопросам построения унифицированного,
заметим, нерекурсивного АРД для нечетких сетей доверия. Кроме того,
созданный алгоритм является с технологической точки зрения более конструк-
тивным и прозрачным, имеет лучшие показатели временной сложности.
Определение нечеткой байесовской сети и узлового дерева. Случайные
переменные или их множества, здесь и далее, обозначаются большими буквами,
а их отдельные значения – малыми буквами: X=x означает, что переменная Х
получает значение х, или, что вектор переменных Х=(X1,…, Xn) получает вектор
значений x = (x1,…, xn). Область определения для Х обозначается dom(X);
||X||=|dom(x)| – количество возможных различных значений переменной Х.
Если Х = X1,…, Xn), тогда dom(X) является декартовым произведением над
областями определения переменных в Х, т. е. ||X||= ||i
i
|| X∏ . Оно образует
пространство состояний, а его элементы – так называемые конфигурации [2]).
Размытый (нечеткий) потенциал – это функция φ:dom(X)→M, где M –
область значений этой функции, состоящая из нечетких нормализованных чисел
[4]. Для обозначения области определения потенциала ϕ будем использовать
нижний индекс (например, ϕХ – это потенциал, определенный над dom(X)) или
записывать в виде dom(ϕ), а для обозначения области значений – Im (к примеру,
Im(ϕ) –область значений потенциала ϕ) . Обозначив Im(ϕ) символом M, можем
записать M ={ µ(t) | t∈R, µ(t):R→[0;1]}, где R – множество действительных
чисел, µ(t) – функции принадлежности определенного вида [3–5].
Для графического представления взаимосвязей между переменными, над
которыми определены размытые потенциалы, используется, согласно [2, 6],
байесовская сеть (БС) N=( X , G, Μ) , которая состоит из
1) ацикличного ориентированного графа G=(V, E) с вершинами V={v1,…,vn}
и дугами E=V×V (рис. 1);
2) множества переменных
1 n
( ,..., )v vX X X= , элементы которого сопо-
ставлены вершинам графа G, причем для каждой вершины сети определен
размытый потенциал
i i
( )v vXϕ , где i=1,…,n;
3) множества размытых потенциалов Ф={
1 n1 n( ) ( )
( | ),..., ( | )v pa v pav v
X X X Xϕ ϕ },
где Xpa(v) – родительские переменные для переменной Xv (если для вершины v
множество родительских переменных пусто, тогда ( )( | ) ( )v pa v vX X Xϕ = ϕ , такую
вершину называют маргиналом).
Применение АРД к трансформированной БС приводит к узловому дереву
[2, 7] со множеством клик и сепараторов. На рис. 2 показано узловое дерево
(УД) T
~
=( C
~
, S
~
), где C
~
– это множество клик, S
~
– множество сепараторов, для
БС (рис. 1). Клики представляют собой вершины этого дерева T
~
, а сепараторы
обозначают его ребра. Напомним, что ребро между двумя соседними кликами Сi
и Сj является их пересечением, т. е. S = Сi∩Сj, где S∈ S
~
.
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
104 Компьютерная математика. 2010, № 2
РИС. 1. Пример фрагмента байесовской сети (а) и соответствующего ему узлового дерева (б)
Приведем модельный пример для наглядного представления введенных
ключевых понятий нечеткой байесовской сети. Пусть A, В, С – переменные,
каждая из которых может находиться в одном из трех четких взаимно
независимых состояний: A=(a1, a2, a3), B=(b1, b2, b3), С=(c1, c2, c3). Связь
между этими переменными графически показана на рис. 1. Соответствующие
размытые потенциалы ϕ(А), ϕ(В) и фрагмент потенциала для переменной С,
представляющий собой распределение условных размытых оценок ϕ(C | B, A),
с функциями принадлежности треугольного типа, представлены на рис. 2.
Для потенциалов определены основные операции: комбинация(⊗),
проекция(↓) (маргинализация [2, 6]) и дополнительная – деление. Для размытых
потенциалов ϕ1 и ϕ2 комбинация, определенных над dom(X) и dom(Y)
соответственно, для произвольного z∈dom(X∪Y), поэлементное произведение
ϕ1⊗ϕ2 определяется, согласно [6], по формуле
1 2 1 2( )( ) ( ) ( )X Yz z zϕ ⊗ ϕ = ϕ ϕ , (1)
где zX и zY – проекция конфигурации z на dom(X) и dom(Y) соответственно.
Например, произведение потенциалов (рис. 2) на основе (1) создает потенциал,
фрагмент которого показан на рис. 3.
Проекция размытого потенциала X↓ϕ на Х определяется [7] как сумми-
рование или нахождение максимального значения над всеми переменными из
dom(φ), кроме Х. Применяя операцию sum-маргинализации [7] к потенциалу
ϕ(C | B,A) (см. рис. 1), получаем ( | , )= ( )A C B A A↓ϕ ϕ , а ( | , )= ( )B C B A B↓ϕ ϕ
(рис. 2). Применение max-маргинализации [7] к потенциалу позволяет найти
конфигурацию с наибольшей оценкой: сравнение оценок осуществляется на
основе сравнения их центров тяжести. Например, для потенциалов ϕ(A) и ϕ(B)
результатом max-маргинализации будет конфигурация A=a2 и В=b3
соответственно (рис. 2), а для ϕ(C | B, A) – (C=c3, B=b3, A=a1) с центром
тяжести 10,96. Применение операции max-маргинализации над размытым потен-
циалом позволяет находить оптимальную конфигурацию для всех переменных
БС, а реализация sum-маргинализации обеспечивает вычисление апостериорного
распределения каждой переменной отдельно.
A B
G
L M
C
I K
F
P
E D LIGKM
CGIK PLM
ABC DCG ECI FCK
б а
ОБ ОДНОМ ЭФФЕКТИВНОМ АЛГОРИТМЕ РАСПРОСТРАНЕНИЯ ВЕРОЯТНОСТЕЙ В НЕЧЕТКИХ ...
Компьютерная математика. 2010, № 2 105
РИС. 2. Размытые потенциалы переменных A,B,C
РИС. 3. Произведение размытых потенциалов переменных A,B,C
После создания узлового дерева T
~
=( C
~
, S
~
) (см. рис. 1, б) каждая его верши-
на инициализируется такими потенциалами: потенциал φ∈Φ присоединяется к
клике так, чтобы dom(φ)⊆C для C∈ C
~
Тогда над всеми φ∈Φ, которые
B=b
1
0
y
x
1
20 30 10
B=b2
0
y
x
1
30 50 10
B=b3
0
y
x
1
50 70 20
A=a1
0
y
x
1
30 50 20
A=a2
0
y
x
1
40 70
A=a3
0
y
x
1
50 30
C=c1,
A=a1,
B=b1 0
y
x
1
15 536
C=c3,
A=a1,
B=b1 0
y
x
1
16 606
C=c2,
A=a3,
B=b3 0
y
x
1
16 540
C=c2,
A=a1,
B=b1 0
y
x
1
13
775
C=c1,
A=a2,
B=b1 0
y
x
1
14 731
C=c3,
A=a3,
B=b3 0
y
x
1
25 771
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
106 Компьютерная математика. 2010, № 2
присоединяются к одной и той же клике, – выполняется операция комбинация
потенциалов. Например, для клики (ABC) (см. рис. 1, б) комбинируются
потенциалы φ(C | A, B), φ(A), φ(B), т. е. φ(ABC)= φ(C|A, B)•φ(A)•φ(B) (см. рис. 3).
Для ребра между кликами (ABC) и (CGIK) создается сепаратор φ(C)≡1.
Алгоритм распространения вероятностей. Предположим, что в резуль-
тате проведенных трансформаций сети доверия построено УД, к которому
нужно применить АРД. В основе этого алгоритма находится процедура
(алгоритм) вычисления значений потенциала одной клики на основе значений
потенциала соседних клик (такие вычисления называются передачей инфор-
мации, в данном случае нечеткой, между кликами). Различают две реализации
этой процедуры: алгоритм S-S (Shenoy-Shafer) и его разновидность – алгоритм
HUGIN [1, 2].
Причем, если процедура PASS_INFORMATION_S_S вызывается из клики Сi
для клики Сj, то алгоритм S–S вычисляет апостериорное распределение оценок
состояний тех переменных, которые входят в состав клики Сi. Чтобы вычислить
апостериорные распределения для всех переменных, необходимо выполнить
процедуру PASS_INFORMATION_S_S по направлению к другим кликам. При
этом все вычисления выполняются с теми значениями потенциалов, которые
были получены на этапе инициализации УД. Последнее условие значит, что
процедура PASS_INFORMATION_S_S нуждается во время выполнения в до-
полнительной памяти для отдельного сохранения результатов промежуточных
вычислений в сепараторах или в кликах.
Другой алгоритм – алгоритм HUGIN – является такой разновидностью
алгоритма S-S, которая не нуждается в дополнительной памяти, поскольку
хранит промежуточные вычисления в потенциалах соответствующих сепарато-
ров и клик. Это достигается, согласно [1, 2], введением операции деления одного
и того же сепаратора: новое значение сепаратора, полученное во время передачи
информации из клики Сi в клику Сj, делится на старое значение, которое было
вычислено на предыдущем шаге АРД во время передачи информации из клики
Сj в клику Сi.
Известно [8], что множество потенциалов, с операциями комбинация и мар-
гинализация, примеры которых указаны выше, образуют алгебру (Φ,D,⊗,↓),
позволяющую выполнять локальные вычисления для потенциалов над УД,
объединяя затем отдельные результаты в общий. Такая схема составляет основу
алгоритма распространения доверия [1, 2]. Далее, выполнение АРД делится на
два этапа (две фазы):
1) вычисление потенциала одной из клик УД (избранную произвольным
способом клику называют корневой) на основе потенциалов остальных клик УД
(рис. 4, а) – это выполнение процедуры COLLECT;
2) распространение вычислений на потенциалы остальных клик УД,
начиная от корневой клики, избранной на этапе 1 (рис. 4, б), – это выполнение
процедуры DISTRIBUTE.
ОБ ОДНОМ ЭФФЕКТИВНОМ АЛГОРИТМЕ РАСПРОСТРАНЕНИЯ ВЕРОЯТНОСТЕЙ В НЕЧЕТКИХ ...
Компьютерная математика. 2010, № 2 107
РИС. 4. Этапы выполнения АРД (корень УД – ( LIGKM )):
а) выполнение процедуры COLLECT; б) выполнение процедуры DISTRIBUTE
Процедура COLLECT вычисляет для переменных корневой клики общее
распределение нечетких вероятностей, которое учитывает все (непо-
средственные и опосредствованные) связи между всеми переменными БС и
наличие свидетельств, поэтому вычисления начинаются от листьев дерева и
заканчиваются в корневой вершине. Чтобы получить общее вероятностное рас-
пределение нечетких вероятностей для каждой оставшейся клики, выполняют
вычисления в обратном порядке (от корневой клики к листьям) с помощью
процедуры DISTRIBUTE. Используя рекурсивное описание обеих процедур,
COLLECT реализовывают с помощью алгоритма поиск в «глубину» [2, 6, 9],
а DISTRIBUTE – алгоритмом поиск в «ширину» [2, 6, 9]. Выполнение АРД
осуществляется как для сети доверия с априорными числовыми параметрами,
так и при наличии свидетельств (апостериорный вывод). В последнем случае
изменяются только оценки состояний. Порядок выполнения АРД остается
прежним.
После завершения выполнения АРД применяется операция sum-марги-
нализации к произвольной клике. Результатом применения является вероятно-
стное распределение для каждой переменной байесовской сети. Если применя-
ется max-маргинализация, тогда вычисляется наиболее вероятная конфигурация
всех переменных байесовской сети.
Вероятностный вывод в байесовских сетях доверия в общем случае является
NP-трудной задачей [8]. Поэтому повышение скорости работы АРД задача
весьма актуальна. В данной статье предлагается один из подходов к ее решению.
Он состоит в использовании эвристик, которые позволят избежать рекурсивных
вычислений.
Нерекурсивный алгоритм распространения вероятностей. Рассмотрим,
придерживаясь [10], алгоритмы обхода ориентированного графа – составных
частей алгоритмов распространения вероятностей. Технологически – это рекур-
сивные алгоритмы, реализующие обход ориентированного графа в «глубину» и
в «ширину», представленные единым обобщенным алгоритмом обхода графа с
запоминанием дуг. Содержательно схема работы таких алгоритмов такова.
б а
LIGK
CGI PL
AB DC EC FC
LIGK
CGI PL
AB DC EC FC
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
108 Компьютерная математика. 2010, № 2
Сначала посещается (маркируется) начальная вершина обхода, а затем в цикле,
с помощью дополнительной структуры данных, выполняется обход остальных
вершин графа. Алгоритм изменяет состояние непомеченной вершины тогда и
только тогда, когда она достижима из вершины, помещенной (маркированной)
на предыдущей итерации цикла. Если дополнительная структура данных явля-
ется стеком, то алгоритм маркирует достижимые вершины графа в порядке
поиска в «глубину», а если очередью, тогда достижимые вершины графа в
порядке поиска в «ширину». Такой алгоритм по временной сложности является
весьма эффективным – имеет место линейная зависимость от числа дуг графа,
достижимых из начальной вершины графа.
Для выполнения обхода УД, инициализированного размытыми потенци-
алами, с одновременным распространением доверия предложен модифици-
рованный алгоритм обхода графа с запоминанием ребер, который объединяет
все этапы АРД без использования рекурсивных вызовов процедур. Понятно, что
такой алгоритм будет не только более прозрачным, но и более быстрым.
Нерекурсивный АРД в своей работе использует следующие структуры
данных и процедуры:
1) структура данных Т –УД, например, рис. 1, б. Каждая из вершин дерева Т
может иметь одно из двух значений маркера: mark_false (неотмеченная) или
mark_true (отмеченная); в начале работы АРД – все вершины имеют значения
маркера mark_false; список вершин смежных с вершиной C обозначается Adj(C),
а их количество – count_Adj;
2) дополнительная структура данных Q – это список, содержащий указатель
на соответствующие вершины УД; над элементами списка Q допустимы следу-
ющие операции:
• push_frontQ(element) – вставить данные element в начало списка Q;
• pop_frontQ() – удалить данные element из начала списка Q;
• push_backQ(element) –вставить данные element в конец списка Q.
3) элементом element списка Q является структура данных, которая имеет
два информационных поля: а) element.child – для сохранения ссылки на
вершину-наследницу; б) element.parent – для сохранения ссылки на вершину-
родителя;
4) процедура mark(C) устанавливает для вершины С значение mark_true;
вершина, с которой начинается выполнение АРД, обозначается как Root;
5) процедура IsChild(C) возвращает значение true, если вершина С имеет
немаркированные смежные вершины-потомки;
6) процедура pass_message(Сj, Сi) реализует один из способов, описанных
выше, для пересылки сообщений между соседними кликами: каждой клике
соответствует размытый потенциал, полученный на этапе трансформации БС,
поэтому их комбинация и маргинализация выполняются согласно [5].
Сценарий выполнения АРД определяется списком Q, который имеет
информационное поле – Q.kind, получающее значение из множества
{"стек","очередь"}. Если во время вызова АРД установлено Q.kind="стек", тогда
над элементами Q выполняются операции push_frontQ и pop_frontQ, а если
ОБ ОДНОМ ЭФФЕКТИВНОМ АЛГОРИТМЕ РАСПРОСТРАНЕНИЯ ВЕРОЯТНОСТЕЙ В НЕЧЕТКИХ ...
Компьютерная математика. 2010, № 2 109
Q.kind="очередь ", тогда – операции pop_frontQ и push_backQ. Такая структура
позволяет правильно выбирать направление передачи сообщений между
кликами во время обхода УД.
При указанных выше условиях модифицированный АРД на языке С++
выглядит следующим образом:
Алгоритм распространения доверия (Т, Root, Q.kind)
1. Q=∅ ; // сначала список пуст
2. C=Root; // выбор корня УД
3. mitka_L: mark(C) // установка маркера
4. if (Q.kind == "очередь ") { // выбор сценария
выполнения
for (int i=0; i<count_Adj; i++) { // для всех смежных с С
вершин
Ci =Adj(C); pass_message(С, Сi) ; // переслать сообщениеi
element.child= Ci ; push_backQ(element); // добавить в конец списка Q
}
}
else {
for (int i=0; i<count_Adj; i++) { // для всех смежных с С
вершин
element.child=Ci ; element.parent=C ; //запомнить соседние
вершины
push_frontQ(element) ; // добавить в начало списка Q
}
5. while (Q<>∅) { // пока список Q не пуст
element= pop_frontQ() ; //получить элемент списка
C= element.child; //получить ссылку на
вершину-наследницу
if ( IsChild(C)==false ) mark(C) ; //если все потомки пройдены
– маркировать C
if (C.mark == mark_true) goto mitka_L; //перейти к следующей
вершине дерева Т
else pass_message(element.child, element.parent) ; // иначе –
переслать сообщение
}
К полученным в результате выполнения алгоритма размытым потенциалам
применяются вышеописанные операции маргинализации. Например, после
выполнения АРД и sum-маргинализации (свидетельства отсутствуют) перво-
начальные значения размытых оценок для переменных A, B (см. рис. 2)
изменятся так, как показано на рис. 5 (пунктиром показано начальная оценка,
а сплошной линией – результат вычислений):
Для БС (см. рис. 1 – фрагмент интерфейса авторской компьютерной
системы) при наличии свидетельств A=a1, C=c2 результат sum-маргинализации
показан на рис. 6, а, а max-маргинализации – на рис. 6, б (как видно из рис. 6, б,
наиболее вероятной апостериорной конфигурацией является конфигурация {a1,
b3, c2, d3, e3, f2, g3, i3, k2, l2, m2, p2}). В обоих случаях для получения
конечного результата выполняется дефузификация размытых оценок на основе
вычисления их центра тяжести, согласно [5].
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
110 Компьютерная математика. 2010, № 2
РИС. 5. Результаты распространения доверия на БС с размытыми потенциалами
а
б
РИС. 6. Результаты распространения доверия на БС с размытыми потенциалами
Корректность работы нерекурсивного АРД в нечеткой информацион-
ной среде. Корректность выполнения описанного выше нерекурсивного АРД
для нечетких сетей доверия вытекает из следующих фактов:
1) процедуры S–S и HUGIN для размытых потенциалов однозначно
соответствуют общим схемам алгоритмов [5, 8], сконструированных для
потенциалов алгебры (Φ,D,⊗,↓);
2) операции над размытыми потенциалами, согласно [5, 8] и принципа
расширения, сохраняют все свойства для корректного выполнения вычисления
над узловым деревом;
A=a2
0
y
x
1
20 64 7 40 70
A=a1
A=a3
0
y
x
1
12 50 30 35
B=b1
0
y
x
1
20 30 10 22 64 7
B=b3
0
y
x
1
50 70 20 36 143 4
0
y
x
1
30 50 20 18 57 5
B=b2
0
y
x
1
30 50 10 42 110 14
12
ОБ ОДНОМ ЭФФЕКТИВНОМ АЛГОРИТМЕ РАСПРОСТРАНЕНИЯ ВЕРОЯТНОСТЕЙ В НЕЧЕТКИХ ...
Компьютерная математика. 2010, № 2 111
3) нерекурсивный АРД выполняет в зависимости от параметра Q.kind обход
дерева в «глубину» или в «ширину», в соответствии с [10].
Количество операций, выполняемых нерекурсивным АРД при обходе УД
в «глубину» или в «ширину», линейно зависит от числа ребер УД. Таким
образом, для нерекурсивного АРД, более строго, временная сложность обхода
дерева составляет O(k), где, k – количество ребер дерева T, которые достигаются
во время обхода из вершины Root.
Поскольку дополнительная структура данных (список), используемый в
нерекурсивном АРД, содержит лишь указатели на вершины УД, то объем
памяти, который она занимает, пропорционален количеству вершин УД, т. е.
O(p(k+1)), где k – количество ребер в УД, p – количество байт, отводимых для
размещения в памяти указателя. Из этого следует, что построенный АРД исполь-
зует также и меньше оперативной памяти по сравнению с рекурсивными версиями
АРД, в которых отдельный вызов выполняется для каждой вершины УД.
Выводы. Таким образом, построен унифицированный алгоритм распростра-
нения вероятностей над нечеткими байесовскими сетями. Этот алгоритм
объединил все этапы распространения доверия, избежав при этом рекурсивных
вызовов для каждой клики узлового дерева. Построенный алгоритм основыва-
ется на модифицированном общем алгоритме обхода графа с запоминанием дуг
и дополнительной структуре данных, сохраняющей указатели на объекты.
Модифицированный алгоритм распространения вероятностей позволяет
вычислять априорные и апостериорные оценки состояний сложных систем на
основе размытых знаний о предметной области путем использования размытых
потенциалов. Для вычисления оценок доверия могут использоваться альтер-
нативные стратегии вывода, что позволяет сравнивать их результаты для разных
моделей одного процесса или системы. Построенный алгоритмы выполняется
корректно и требует меньших затрат вычислительных ресурсов по сравнению с
применением аналогичных рекурсивных алгоритмов распространения доверия.
Полученные результаты использованы при построении соответствующей
нечеткой информационной технологии моделирования состояний сложных сис-
тем в условиях неопределенности и размытости причинно-следственных связей.
Примеры, использованные в статье, являются результатом применения нерекур-
сивного алгоритма распространения вероятностей к модельным нечетким
байесовским сетям.
І.М. Парасюк, Ф.В. Костукевич
ПРО ОДИН ЕФЕКТИВНИЙ АЛГОРИТМ ПОШИРЕННЯ ЙМОВІРНОСТЕЙ
В НЕЧІТКИХ БАЙЄСІВСЬКИХ МЕРЕЖАХ ДОВІРИ
Розглянута загальна схема алгоритма розповсюдження ймовірностей над нечіткими байєсів-
ськими мережами довіри. Побудовано уніфікований алгоритм розповсюдження довіри на
основі розмитих потенціалів. Доведена коректність виконання цього алгоритма та вказані
умови йогo застосування, за яких цей алгоритм є найбільш ефективним.
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
112 Компьютерная математика. 2010, № 2
I.М. Parasyuk, F.V. Kostukevich
AN EFFECTIVE ALGORITHM FOR PROPAGATION OF PROBABILITIES
IN FUZZY BAYESIAN BELIEF NETWORKS
A general scheme of belief propagation algorithms above the fuzzy Bayesian networks of belief is
considered. The new belief propagation algorithm is built on the basis of fuzzy potentials.
Correctness of this implementation of algorithms is proved and conditions of his applications at
which this algorithm is most effective are indicated.
1. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. –
Morgan Kaufmann, San Mateo, CA, 1991. – 552 p.
2. Сowell R.G., Dawid A.P., Spiegelhalter D.J., Lauritzen S.L. Probabilistic Networks and Expert
Systems. – New York: Springer–Verlag, Inc., 1999. – 321 p.
3. Верьовка О.В., Парасюк И.Н. О распространении вероятностей в нечетких байесовских
сетях с недетерминированными состояниями // Кибернетика и системный анализ. – 2008.
– № 6. – С. 153–169.
4. Zadeh L.A., Fuzzy Sets, Information and Control, 1965. –8. – Р. 338–353.
5. Парасюк И.Н., Костукевич Ф.В. Нечеткие потенциалы и вопросы их применения в
алгоритмах распространения доверия на байесовских сетях // Компьютерная математика,
– 2009. – № 1. – C. 70–76.
6. Uffe B.Kjaerulff, Anders L.Madsen Bayesian Networks and Influence Diagrams. – Springer
Science+Business Media, LLC, 2008. – 318 p.
7. Парасюк И.Н., Костукевич Ф.В. Методы трансформации байесовской сети для постро-
ения узлового дерева и их модификация // Компьютерная математика. – 2008. –
№ 1. – C. 70–80.
8. Shenoy P.P. Valuation-based systems for discrete optimization. // In Uncertainty in Artificial
Intelligence (ed. P.P.Bonissone, M.Henrion,L.N.Kanal and J.F.Lemmer): North-Holland,
Amsterdam, The Netherlands. 1991. – N 6. – P. 385–400.
9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. под
ред. А. Шеня. – М.:МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 960 с.
10. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и
применение. – СПб.: БХВ-Петербург, 2003. – 1104 с.
Получено.15.04.2010
Îá àâòîðàõ:
Парасюк Иван Николаевич,
доктор технических наук, профессор, член-корреспондент НАН Украины,
зав. отделом Института кибернетики имени В.М. Глушкова НАН Украины,
E-Mail: ivpar1@i.com.ua
Костукевич Феликс Витальевич,
аспирант Института кибернетики имени В.М. Глушкова НАН Украины.
E-Mail: internat_m@fk.lutsk.ua
|
| id | nasplib_isofts_kiev_ua-123456789-84592 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T18:49:25Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Парасюк, И.Н. Костукевич, Ф.В. 2015-07-10T17:38:23Z 2015-07-10T17:38:23Z 2010 Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия / И.Н. Парасюк, Ф.В. Костукевич // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 102-112. — Бібліогр.: 10 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84592 681.3 Рассмотрена общая схема алгоритма распространения вероятностей для байесовских сетей. Построен унифицированный алгоритм распространения доверия для нечетких байесовских сетей доверия, который базируется на новых принципах обхода узлового дерева, является более прозрачным и быстродействующим. Описана структура этого алгоритма и исследованы условия его корректной работы. Описаны результаты моделирования основных операций с размытыми потенциалами, заданными над нечеткими байесовскими сетями доверия. Розглянута загальна схема алгоритма розповсюдження ймовірностей над нечіткими байєсівськими мережами довіри. Побудовано уніфікований алгоритм розповсюдження довіри на основі розмитих потенціалів. Доведена коректність виконання цього алгоритма та вказані умови йогo застосування, за яких цей алгоритм є найбільш ефективним. A general scheme of belief propagation algorithms above the fuzzy Bayesian networks of belief is considered. The new belief propagation algorithm is built on the basis of fuzzy potentials. Correctness of this implementation of algorithms is proved and conditions of his applications at which this algorithm is most effective are indicated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия Про один ефективний алгоритм поширення ймовірностей в нечітких байєсівських мережах довіри An effective algorithm for propagation of probabilities in fuzzy Bayesian belief networks Article published earlier |
| spellingShingle | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия Парасюк, И.Н. Костукевич, Ф.В. Оптимизация вычислений |
| title | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| title_alt | Про один ефективний алгоритм поширення ймовірностей в нечітких байєсівських мережах довіри An effective algorithm for propagation of probabilities in fuzzy Bayesian belief networks |
| title_full | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| title_fullStr | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| title_full_unstemmed | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| title_short | Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| title_sort | об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях доверия |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84592 |
| work_keys_str_mv | AT parasûkin obodnoméffektivnomalgoritmerasprostraneniâveroâtnosteivnečetkihbaiesovskihsetâhdoveriâ AT kostukevičfv obodnoméffektivnomalgoritmerasprostraneniâveroâtnosteivnečetkihbaiesovskihsetâhdoveriâ AT parasûkin proodinefektivniialgoritmpoširennâimovírnosteivnečítkihbaiêsívsʹkihmerežahdovíri AT kostukevičfv proodinefektivniialgoritmpoširennâimovírnosteivnečítkihbaiêsívsʹkihmerežahdovíri AT parasûkin aneffectivealgorithmforpropagationofprobabilitiesinfuzzybayesianbeliefnetworks AT kostukevičfv aneffectivealgorithmforpropagationofprobabilitiesinfuzzybayesianbeliefnetworks |