Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях
Рассмотрены общие схемы алгоритмов распространения доверия для байесовских сетей. Основное внимание уделено свойствам вероятностных и нечетких потенциалов. Авторами построены новые алгоритмы распространения доверия для потенциалов, определенных над байесовскими сетями с детерминированными состояниям...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6231 |
| 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: | Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях / И.Н. Парасюк, Ф.В. Костукевич // Компьютерная математика. — 2009. — № 1. — С. 67-75. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-6231 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-62312025-02-23T20:17:14Z Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях Нечіткі потенціали та питання про їх застосування в алгоритмах розповсюдження довіри на баєсівських мережах Fuzzy potentials and their application problems in belief propagation algorithms on bayesian networks Парасюк, И.Н. Костукевич, Ф.В. Системный анализ Рассмотрены общие схемы алгоритмов распространения доверия для байесовских сетей. Основное внимание уделено свойствам вероятностных и нечетких потенциалов. Авторами построены новые алгоритмы распространения доверия для потенциалов, определенных над байесовскими сетями с детерминированными состояниями. Описаны структуры этих алгоритмов, условия их корректной работы, полученные при моделировании основных операций с потенциалами, заданными над нечеткими множествами. Розглянуто загальні схеми алгоритмів розповсюдження довіри на баєсівських мережах. Побудовано нові алгоритми розповсюдження довіри на основі нечітких потенціалів. Доведена коректність виконання цих алгоритмів та вказані умови їх застосування, при яких ці алгоритми є найбільш ефективними. The most effective schemes of algorithms of belief propagation on Bayesian network are investigated. The new algorithms based on the fuzzy sets theory are constructed. Their structures and correct operation conditions, obtained during modeling the main operations with potentials given on fuzzy sets, are described. 2009 Article Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях / И.Н. Парасюк, Ф.В. Костукевич // Компьютерная математика. — 2009. — № 1. — С. 67-75. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/6231 681.3 ru application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Парасюк, И.Н. Костукевич, Ф.В. Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| description |
Рассмотрены общие схемы алгоритмов распространения доверия для байесовских сетей. Основное внимание уделено свойствам вероятностных и нечетких потенциалов. Авторами построены новые алгоритмы распространения доверия для потенциалов, определенных над байесовскими сетями с детерминированными состояниями. Описаны структуры этих алгоритмов, условия их корректной работы, полученные при моделировании основных операций с потенциалами, заданными над нечеткими множествами. |
| format |
Article |
| author |
Парасюк, И.Н. Костукевич, Ф.В. |
| author_facet |
Парасюк, И.Н. Костукевич, Ф.В. |
| author_sort |
Парасюк, И.Н. |
| title |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| title_short |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| title_full |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| title_fullStr |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| title_full_unstemmed |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| title_sort |
нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Системный анализ |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/6231 |
| citation_txt |
Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на байесовских сетях / И.Н. Парасюк, Ф.В. Костукевич // Компьютерная математика. — 2009. — № 1. — С. 67-75. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT parasûkin nečetkiepotencialyivoprosyihprimeneniâvalgoritmahrasprostraneniâdoveriânabajesovskihsetâh AT kostukevičfv nečetkiepotencialyivoprosyihprimeneniâvalgoritmahrasprostraneniâdoveriânabajesovskihsetâh AT parasûkin nečítkípotencíalitapitannâproíhzastosuvannâvalgoritmahrozpovsûdžennâdovírinabaêsívsʹkihmerežah AT kostukevičfv nečítkípotencíalitapitannâproíhzastosuvannâvalgoritmahrozpovsûdžennâdovírinabaêsívsʹkihmerežah AT parasûkin fuzzypotentialsandtheirapplicationproblemsinbeliefpropagationalgorithmsonbayesiannetworks AT kostukevičfv fuzzypotentialsandtheirapplicationproblemsinbeliefpropagationalgorithmsonbayesiannetworks |
| first_indexed |
2025-11-25T03:42:12Z |
| last_indexed |
2025-11-25T03:42:12Z |
| _version_ |
1849732245783314432 |
| fulltext |
Компьютерная математика. 2009, № 1 67
Рассмотрены общие схемы алго-
ритмов распространения доверия
для байесовских сетей. Основное
внимание уделено свойствам веро-
ятностных и нечетких потенциа-
лов. Авторами построены новые
алгоритмы распространения дове-
рия для потенциалов, определенных
над байесовскими сетями с детер-
минированными состояниями. Опи-
саны структуры этих алгоритмов,
условия их корректной работы,
полученные при моделировании ос-
новных операций с потенциалами,
заданными над нечеткими множе-
ствами.
© И.Н. Парасюк,
Ф.В. Костукевич, 2009
ÓÄÊ 681.3
È.Í. ÏÀÐÀÑÞÊ, Ô.Â. ÊÎÑÒÓÊÅÂÈ×
ÍÅ×ÅÒÊÈÅ ÏÎÒÅÍÖÈÀËÛ
È ÂÎÏÐÎÑÛ ÈÕ ÏÐÈÌÅÍÅÍÈß
 ÀËÃÎÐÈÒÌÀÕ
ÐÀÑÏÐÎÑÒÐÀÍÅÍÈß ÄÎÂÅÐÈß
ÍÀ ÁÀÉÅÑÎÂÑÊÈÕ ÑÅÒßÕ
Введение. Интерес к вероятностным моде-
лям в виде байесовских сетей и к методам их
эффективной компьютеризации чрезвычайно
велик, так как они позволяют оценивать и
прогнозировать состояния сложных систем
[1]. Правда, использующиеся для этих целей
методы ориентированы на четкую (точеч-
ную) информацию в виде оценок вероятно-
стей и потенциалов, которая, как показывает
опыт, не всегда адекватно может отображать
реалии и сужает альтернативы в принятии
решений. Весьма интересно использовать
для этих целей нечеткую информацию [2],
тем более, что положительный опыт такого
подхода имеется, например, в [3].
В данной работе введено понятие нечетких
потенциалов, проведен сравнительный ана-
лиз вероятностных распределений, а также
приведены новые алгоритмы распростране-
ния доверия над байесовскими сетями, ис-
пользующие нечеткие входные данные.
Определение потенциалов и операций
над ними. Случайные переменные или их
множества, здесь и далее, обозначаются
большими буквами, а их отдельные значе-
ния – малыми буквами: X = x означает, что
переменная Х получает значение х, или век-
тор переменных Х = (X1,…,Xn), получает
вектор значений x = (x1,…,xn). Область оп-
ределения для Х обозначается dom(X); ||X||=
= |dom(x)| определяет количество возмож-
ных различных значений переменной Х.
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
Компьютерная математика. 2009, № 1 68
Если Х = (X1,…,Xn), тогда dom(X) – декартовное произведение (такое произ-
ведение называют пространством состояний, а его элементы – конфигурациями
[4]) над областями определения переменных в Х, т. е. ||X||=∏
i
iX|| || .
Потенциал – это функция φ:D → K, где D – пространство состояний и К –
множество значений потенциала. Если сумма значений потенциала над обла-
стью его определения равна 1, то такой потенциал называется нормализован-
ным. Множество потенциалов обозначается Φ. Для обозначения области опре-
деления потенциала ϕ используют нижний индекс (например, ϕХ – потенциал,
определенный над dom(X)) или записывают dom(ϕ).
Для графического представления взаимосвязей между потенциалами вве-
дем, по аналогии с [4], обобщенное определение байесовской сети (БС) N =
= (X, G, P) (рис. 1, а), состоящей из:
– ациклического орграфа G = (V, E) с узлами V = {v1,…,vn} и дугами E = V×V;
– множество случайных переменных X, которые представлены узлами
графа G;
– множества потенциалов Φ ={Φ(Xv,Xpa(v))} для каждой переменной Xv∈X,
Xpa(v) – множество соответствующих ей родительских переменных.
Согласно [1, 5], БС N = (X, G, P) возможно трансформировать в соответст-
вующее узловое деревом T~ = ( C~ , S~ ) (рис. 1, б), где C~ – множество клик, S~ –
множество сепараторов. Клики – представляют собой вершины дерева T~ , а се-
параторы – обозначают ребра этого дерева. Ребро между двумя соседними кли-
ками Сi и Сj является их пересечением, т. е. S = Сi ∩Сj, где S∈ S~ .
а б
РИС. 1. Для БС (а), узловое дерево T~ (б)
Узловое дерево Т = (С,S) состоит из множества клик С = {{GADBE},
{CGAD}, {IGDBE}, {KIGB}, {LKIG}, {FKB}} и множества сепараторов
S ={{GAD}, {GDBE}, {IGB}, {KIG}, {KB}}.
A B
G I K
C D F E
L
KIG K B
GADBE
CGAD
IGDBE
FKB LKIG
GAD GDB
IGB
KIGB
НЕЧЕТКИЕ ПОТЕНЦИАЛЫ И ВОПРОСЫ …
Компьютерная математика. 2009, № 1 69
Определение 1.1. БС называется вероятностной [1], если для каждого ее уз-
ла потенциал P определяется как функция P : D → R+, где R+ – множество неот-
рицательных действительных чисел. Такой потенциал называют вероятностным
распределением. Например, для узла F (рис. 1, а) потенциал определяется через
условное вероятностное распределение P(F | B), заданное над пространством
F × B, состоящим из взаимно исключающих конфигураций.
Определение 1.2. БС назовем нечеткой, если для каждого ее узла нечеткий
потенциал ,μ согласно [2, 6], определяется как функция принадлежности
μ : D→[0;1]. Например, для узла БС F (рис. 1, а), каждому элементу пространст-
ва F × B соответствует неотрицательное действительное число μF×B, в интервале
от 0 до 1 включительно, называемое степенью принадлежности. В отличие от
вероятностного распределения P(F|B) потенциал μF×B, заданный над простран-
ством F × B, представляет распределение возможностей, что является расшире-
нием по отношению к вероятностному потенциалу P(F | B).
Для потенциалов определены две основные операции: комбинация и проек-
ция (маргинализация [1, 6]). Комбинация потенциалов, обозначаемая “⊗”, – это
бинарная операция Φ⊗Φ→Φ, которая должна быть ассоциативной, коммутатив-
ной. Для операции ⊗ должен существовать нейтральный элемент е, такой, что
φ⊗e = e⊗φ = φ. Проекция потенциала – также бинарная операция Φ⊗D→Φ, ко-
торая сокращает область определения потенциала, а именно: если область опре-
деления φ – dom(ϕ), то проекция φ на подпространство X ⊆ dom(ϕ), обозначае-
мая ϕ↓X, определена над Х ∩ dom(ϕ). Основное свойство проекции – транзитив-
ность; кроме того – проекция дистрибутивна относительно операции ⊗.
Определение 2.1. Для вероятностных потенциалов P1 и P2, определенных
над dom(X) и dom(Y) соответственно, для произвольного z∈dom(X ∪ Y) поэле-
ментное произведение P1⊗P2 определяется, согласно [1], по формуле:
(P1⊗P2)(z) = P1(zX)P2(zY), (1)
где zX и zY – проекция конфигурации z на dom(X) и dom(Y) соответственно.
Проекция вероятностного потенциала P↓X на Х определяется, как суммирова-
ние (или нахождение максимального значения) над всеми переменными из
dom(P), кроме Х. Например, для клики узлового дерева {GADBE} (рис. 1, б), над
которой определен потенциал P(GADBE), проекция P↓G(z) =
)dom(
max
Pz∈
P(zG,zADBE),
где zG и zADBE – проекция конфигурации z на dom(G) и dom(ADBE) соот-
ветственно.
Определение 2.2. Для нечетких потенциалов 1 2иμ μ комбинация ⊗ – по-
элементная операция, определяемая для произвольного z∈dom(X ∪ Y) на основе
выбранного подхода [2, 6]:
теоретико-множественного, т. е.
(μ1 ⊗ μ2)(z) = min(μ1(zX), μ2(zY)); (2)
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
Компьютерная математика. 2009, № 1 70
алгебраического
(μ1 ⊗ μ2)(z) = (μ1 (zX) μ2 (zY) / max(μ1 (zX) μ2 (zY)), (3)
(μ1 ⊗ μ2)(z) = (μ1 (zX) μ2 (zY) / 1– (1 – μ1 (zX))(1 – μ2(zY))), (4)
где zX и zY – проекция конфигурации z на dom(X) и dom(Y) соответственно.
Например, для нечетких потенциалов поэлементное алгебраическое умно-
жение (μLGIK μKGI) – обобщение умножения вероятностных потенциалов (PLGIK
PKGI), а применение теоретико-множественного умножения к этим нечетким
потенциалам, позволяет избежать получения очень малых чисел, получаемых
при умножении соответствующих вероятностных потенциалов.
Проекция нечеткого потенциала μ↓X определяется, как нахождение макси-
мального значения над всеми переменными из dom(P), кроме Х:
μ↓X =
dom( )
max
Yz ∈ μ
μ(zX,zY). (5)
Применение операции max над нечетким потенциалом позволяет находить
степень принадлежности каждого элемента конфигурации или максимальную
степень принадлежности среди всех конфигураций, что является обобщением
операций суммирования и максимизации вероятностного потенциала.
Для двух потенциалов ϕ1 и ϕ2, имеет место деление ϕ1 ÷ ϕ2, если они при-
надлежат частично упорядоченному множеству потенциалов Φ, т. е ϕ2 ≤ ϕ1, и
существует такой потенциал ψ, что
2 1ϕ ⊗ψ→ ϕ , (6)
где dom(φ2) ∪ dom(ψ) ⊆ dom(φ1). Множество потенциалов Φ называется частич-
но упорядоченным, если для двух произвольных из Φ потенциалов ϕ1 и ϕ2 из
того, что dom(ϕ2) ⊆ dom(ϕ1), следует ϕ2 ≤ ϕ1.
Определение 3.1. Для вероятностных потенциалов поэлементное деление
определяется формулой
(ϕ1÷ϕ2)(z) =
1
1 2 2
0, если ( ) 0,
( ) / ( ), если ( ) 0,
0, в других случаях.
X
X Y Y
z
z z z
ϕ =⎧
⎪ϕ ϕ ϕ ≠⎨
⎪
⎩
(7)
На основе формулы (7) для вероятностных потенциалов вводится определе-
ние условной вероятности [1].
НЕЧЕТКИЕ ПОТЕНЦИАЛЫ И ВОПРОСЫ …
Компьютерная математика. 2009, № 1 71
Определение 3.2. Для нечетких потенциалов 1 2иμ μ деление согласно (7),
возможно в том случае, если операция ⊗ определена алгебраическим способом и
существует функция ,μ удовлетворяющая условие (6). Например, деление не-
четких потенциалов для всех сепараторов из множества S~ (рис. 1, б) в алгорит-
ме HUGIN возможно, если операция ⊗ определена согласно (4).
Схемы алгоритма распространения нечеткого доверия. После создания
узлового дерева T~ = ( C~ , S~ ) (рис. 1, б) – каждая его вершина инициализируется
потенциалами: каждый потенциал φ∈Φ присоединяется к клике так, чтобы
dom(φ) ⊆ C для C ∈ C~ . Тогда все φ ∈ Φ, которые присоединяются к одной и той
же клике – перемножаются. Например, для клики (FKB) узлового дерева (рис. 1)
выбирают потенциалы, полностью определенные над ней: φ(K|F), φ(F|B), φ(B),
тогда, для каждой комбинации состояний, значения потенциала вычисляются по
формуле φ(FKB) = φ(K|F)•φ(F|B)•φ(B). Для всех сепараторов и клик, к которым
потенциалы не присоединялись, последние инициализируются единицей.
Доказано в [6], что множество потенциалов с операциями ⊗ и ↓, обладаю-
щими всеми вышеперечисленными свойствами, образуют алгебру (Φ, D, ⊗, ↓),
позволяющую выполнять локальные вычисления для потенциалов над узловым
деревом, объединяя затем отдельные результаты в общий. Такая схема называ-
ется алгоритмом распространения доверия (АРД). Выполнение АРД (после ини-
циализации) делится на два этапа (две фазы): выполнение процедуры COLLECT
и DISTRIBUTE. Процедура COLLECT вычисляет для переменных корневой
клики общее распределение вероятностей, которое учитывает все (непосредст-
венные и опосредствованные) связи между всеми переменными БС и наличие
свидетельств, поэтому вычисления начинаются от листьев дерева и заканчива-
ются в корневой вершине. Чтобы получить общее вероятностное распределение
вероятностей для каждой оставшейся клики – выполняют вычисления в обрат-
ном порядке (от корневой клики – к листьям) с помощью процедуры
DISTRIBUTE. После завершения АРД, применяя соответствующие операции
проекции к произвольной клике, можно получить вероятностное распределение
для каждой переменной БС или наиболее вероятную конфигурацию состояний.
Используя рекурсивное описание процедуры COLLECT, ее реализовывают
с помощью алгоритма «поиск в глубину», а процедуру DISTRIBUTE – алгорит-
мом «поиск в ширину» [7]. Для реализации основной процедуры, входящей в
состав процедур COLLECT и DISTRIBUTE, которая выполняет вычисления для
одной клики на основе результатов вычислений в соседних кликах, применяют
один из двух алгоритмов: более общий – алгоритм S – S [5] и специализирован-
ный (с использованием операции деления) – алгоритм HUGIN [6].
Пусть в качестве потенциалов рассматриваются нечеткие потенциалы ,μ
определенные теоретико-множественным способом, и АРД вызывается из клики
Сi, для клики Сj. Тогда алгоритм S – S имеет следующую структуру (потенциалы
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
Компьютерная математика. 2009, № 1 72
φ вычисляются на основе функций соответствия и хранят результаты промежу-
точных вычислений):
Алгоритм PASS_INFORMATION(Сi, Сj)
if клика Сj имеет смежные клики Ck ≠ Сi, then
ϕ: = 1;
for each смежной кликой Ck ≠ Сi:ϕ: = min(ϕ,ϕk→j);
ϕj→i: =
ij CC \
max (min(ϕ, μj))
else ϕj→i: =
ij CC \
max (μj).
После выполнения алгоритма PASS_INFORMATION(Сi, Сj), ребро ведущее
из смежной клики Сj в корневую клику Сi содержит потенциал (сообщение) ре-
курсивно вычисленный на основе всех остальных клик узлового дерева.
Алгоритм HUGIN в ходе вычислений использует промежуточную структу-
ру данных в узловом дереве – сепаратор S (ребро, соединяющее смежные клики
и сохраняющее потенциал, область определения которого dom(Ci ∩ Cj). По-
скольку общая структура HUGIN-алгоритма использует операцию деления по-
тенциалов, то конструкция алгоритма, с применением для нечетких потенциалов
операций (2), (4) и (7), будет следующей.
Алгоритм PASS_INFORMATION (Сi, Сj).
1. Вычислить проекцию клики Сj на Сi , т. е. потенциал сепаратора S:
*μS : = )(μmax
\ j
j
C
SC
.
2. Вычислить коэффициент обновления сепаратора:
if μS = 0 then iCμ : = 0
else iCμ : = iCμ ⋅ **
*
μμμμ
μμ
SSSS
SS
⋅+−
⋅ (следует из формул (4, 6)).
3. Заменить старый потенциал – новым: μS: = *μS .
Результатом роботы алгоритма станут обновленные потенциалы клики Сi и
сепаратора S.
Корректность работы АРД в нечеткой информационной среде и моде-
лирование операций над нечеткими потенциалами. Нетрудно убедиться, что
вышеописанные АРД с нечеткой информацией, т. е. на основе учета функций
принадлежности, выполняются корректно. Доказательством этому являются
следующие факты:
НЕЧЕТКИЕ ПОТЕНЦИАЛЫ И ВОПРОСЫ …
Компьютерная математика. 2009, № 1 73
– схемы алгоритмов S – S и HUGIN для функций принадлежности однознач-
но соответствуют общим схемам алгоритмов [6], сконструированных для потен-
циалов алгебры (Φ, D, ⊗, ↓);
– операции над функциями принадлежности (определенные теоретико-
множественным или алгебраическим способом) являются частичным случаем
потенциала, принадлежащего алгебре (Φ, D, ⊗, ↓), и имеют все свойства потен-
циала, позволяющего корректно выполнять вычисления над узловым деревом.
Из этого следует, что алгоритмы АРД в нечеткой информационной среде
выполняются корректно (по ангалогии с соответствующими алгоритмами для
вероятностных потенциалов).
Уместно отметить, что выбор операций над нечеткими потенциалами, явля-
ется достаточно сложным и вместе с тем весьма принципиальным и важным во-
просом для реализации АРД. Поскольку функция min не имеет обратной функ-
ции (по аналогии как операция деления – обратная к операции умножения), по-
этому ее использование ограничено алгоритмом S – S. Недостатком данного ал-
горитма, как указывается в [1], являются вычисления потенциалов, имеющих
достаточно большие области определения. С другой стороны, при использова-
нии вероятностной модели над потенциалами выполняются операции умноже-
ния, тогда как при использовании нечетких моделей – замена операции умноже-
ния на операцию min, ускоряет выполнение АРД. Таким образом, применение
теории нечетких множеств к алгоритму S – S позволяет уменьшить время вы-
числений, сохранив одновременно корректность модели.
Особенность использования АРД HUGIN – наличие операции деления не-
четких потенциалов. Моделирование вычислений потенциалов, где операция ⊗
определялась алгебраическим путем, показало, что, согласно аксиоматическому
определению операций [2], значения функции min можно аппроксимировать ал-
гебраическими функциями (рис. 2). Здесь представлены следующие определения
операции ⊗ для двух произвольных функций принадлежности 1 0и ,μ μ где
значение 0μ – фиксированное и равно 0,6:
MIN:= min( 1 2,μ μ ); F2:= 1 0, ;μ μ
01μμ:3 =F ; 1 0 1 0 0 14 : μ μ μ μ (1 μ )(1 μ ).F = + − −
Для определения ⊗ возможно также использовать семейства функций (се-
мейства Франка, семейство Хамакера и др. [2]). Возможность выбора наиболее
подходящей для конкретной задачи функции обеспечивает достаточную гиб-
кость и эффективность на практике.
И.Н. ПАРАСЮК, Ф.В. КОСТУКЕВИЧ
Компьютерная математика. 2009, № 1 74
РИС. 2. Апроксимация функции min алгебраическим способом
Выводы. Таким образом, нами построены новые алгоритмы моделирования
состояний сложных систем на основе размытых знаний о предметной области
путем реализации процесса распространения доверия для нечетких потенциалов,
определенных над байесовскими сетями с детерминированными состояниями.
Анализ построенных алгоритмов, показал, что такие алгоритмы выполняют-
ся корректно и требует меньших затрат вычислительных ресурсов по сравнению
с применением аналогичных алгоритмов для вероятностных моделей.
Полученные результаты найдут свое применение при построении соответст-
вующей нечеткой информационной технологии моделирования сложных систем.
І.М. Парасюк, Ф.В. Костукевич
НЕЧІТКІ ПОТЕНЦІАЛИ ТА ПИТАННЯ ПРО ЇХ ЗАСТОСУВАННЯ
В АЛГОРИТМАХ РОЗПОВСЮДЖЕННЯ ДОВІРИ НА БАЄСІВСЬКИХ МЕРЕЖАХ
Розглянуто загальні схеми алгоритмів розповсюдження довіри на баєсівських мережах.
Побудовано нові алгоритми розповсюдження довіри на основі нечітких потенціалів. До-
ведена коректність виконання цих алгоритмів та вказані умови їх застосування, при яких
ці алгоритми є найбільш ефективними.
НЕЧЕТКИЕ ПОТЕНЦИАЛЫ И ВОПРОСЫ …
Компьютерная математика. 2009, № 1 75
I.М. Parasyuk, F.V. Kostukevich
FUZZY POTENTIALS AND THEIR APPLICATION PROBLEMS IN BELIEF PROPAGATION
ALGORITHMS ON BAYESIAN NETWORKS
The most effective schemes of algorithms of belief propagation on Bayesian network are investi-
gated. The new algorithms based on the fuzzy sets theory are constructed. Their structures and cor-
rect operation conditions, obtained during modeling the main operations with potentials given on
fuzzy sets, are described.
1. Сowell R.G., Dawid A.P., Spiegelhalter D.J., Lauritzen S.L. Probabilistic Networks
and Expert Systems. – Springer–Verlag, New York, Inc., 1999. – 321 p.
2. Bellman R.E., Gierts M. On the analitical formalism of theory of fuzzy sets."Inform.
Sci.", 1973. – 5, N 2. – Р. 149–156.
3 Верьовка О.В., Парасюк И.Н. О распространении вероятностей в нечетких байе-
совских сетях с недетерминированными состоянииями // Кибернетика и систем-
ный анализ. – 2008. – № 6. – С. 153–169.
4. Kjaerulff Uffe B., Madsen Anders L. Bayesian Networks and Influence Diagrams. –
Springer Science+Business Media, LLC, 2008. – 318 p.
5. Парасюк И.Н., Костукевич Ф.В. Методы трансформации байесовской сети для
построения узлового дерева и их модификация // Компъютерная математика. –
2008. – № 1. – C. 70–80.
6. 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. – № 6. – P. 385–400.
7 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ : Пер. с англ.
под ред. А. Шеня. – М.: МЦНМО:БИНОМ. Лаборатория знаний, 2004. – 960 с.
Получено 11.12.2008
Oá àâòîðàõ:
Парасюк Иван Николаевич,
член-корреспондент НАН Украины,
заведующий отделом Института кибернетики имени В.М. Глушкова НАН Украины,
E-Mail: ivpar1@i.com.ua
Костукевич Феликс Витальевич,
аспирант Института кибернетики имени В.М. Глушкова НАН Украины.
E-Mail: internat_m@fk.lutsk.ua
|