Алгоритм вероятностного вывода в байесовских сетях
Предлагается новый, более простой и точный алгоритм вероятностного вивода в байесовских сетях на основе обучающих данных.
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/12411 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритм вероятностного вывода в байесовских сетях / А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 107-111. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-12411 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-124112013-02-13T02:03:58Z Алгоритм вероятностного вывода в байесовских сетях Терентьев, А.Н. Бидюк, П.И. Коршевнюк, Л.А. Евристичні методи та алгоритми в системному аналізі та управлінні Предлагается новый, более простой и точный алгоритм вероятностного вивода в байесовских сетях на основе обучающих данных. Пропонується новий, простіший і точніший, алгоритм формування ймовірнісного виводу в байєсівських мережах на основі навчальних даних. A novel algorithm for formation of probabilistic inference in Bayes networks on the basis of the training data, which is more exact and simple compared to conventional ones, is offered. 2009 Article Алгоритм вероятностного вывода в байесовских сетях / А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 107-111. — Бібліогр.: 7 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/12411 62-50 ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| 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 |
http://dspace.nbuv.gov.ua/handle/123456789/12411 |
| citation_txt |
Алгоритм вероятностного вывода в байесовских сетях / А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 107-111. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT terentʹevan algoritmveroâtnostnogovyvodavbajesovskihsetâh AT bidûkpi algoritmveroâtnostnogovyvodavbajesovskihsetâh AT korševnûkla algoritmveroâtnostnogovyvodavbajesovskihsetâh |
| first_indexed |
2025-07-02T14:32:18Z |
| last_indexed |
2025-07-02T14:32:18Z |
| _version_ |
1836545987544350720 |
| fulltext |
© А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк, 2009
Системні дослідження та інформаційні технології, 2009, № 2 107
TIДC
ЕВРИСТИЧНІ МЕТОДИ ТА АЛГОРИТМИ
В СИСТЕМНОМУ АНАЛІЗІ ТА УПРАВЛІННІ
УДК 62-50
АЛГОРИТМ ВЕРОЯТНОСТНОГО ВЫВОДА
В БАЙЕСОВСКИХ СЕТЯХ
А.Н. ТЕРЕНТЬЕВ, П.И. БИДЮК, Л.А. КОРШЕВНЮК
Предлагается новый, более простой и точный алгоритм вероятностного вывода
в байесовских сетях на основе обучающих данных.
ВСТУПЛЕНИЕ
Применение технологий интеллектуального анализа данных становится все
более актуальным благодаря совершенствованию методов анализа и вычис-
лительных процедур, которые их реализуют. Это связано также с тем, что в
мире постепенно накапливаются большие объемы информации, требующие
надлежащей обработки и принятия решений. Успешное развитие любого
предприятия напрямую зависит от его способности адекватно и оперативно
реагировать на изменение внешней среды, а также умение прогнозировать
результаты тех или иных воздействий. Так, в отчете Ассоциации американ-
ских банкиров отмечается, что 45 из 100 крупнейших банков США уже вне-
дрили у себя системы интеллектуального анализа данных, и еще около 50
банков начали реализацию подобных проектов или планируют это сделать в
ближайшее время.
Среди разнообразных методов интеллектуального анализа байесовские
методы занимают одно из ведущих направлений. Благодаря универсально-
сти по отношению к используемым типам данных и решаемых практиче-
ских задач их можно использовать в различных областях человеческой жиз-
недеятельности — технике, экономике, финансах, информационных
технологиях, медицине, биологии и других направлениях [1,2]. Классы ре-
шаемых задач также самые разнообразные — классификация, прогнозиро-
вание, диагностика, оценивание, управление и т.п. Одним из самых пер-
спективных современных байесовских методов является байесовская сеть
(БС).
При построении БС необходимо решать задачи обучения, оптимизации
структуры сети и формирования вероятностного вывода. Задача вероятно-
стного вывода в БС является важной и сложной задачей, относящейся к
классу задач принятия решений. Один из методов формирования вероятно-
стного вывода в БС предложен в работе [3]. Однако для реализации метода
А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 108
необходимо привести структуру БС к виду объединенного дерева (junction
tree). Для этого нужно выполнить следующее.
1. Морализировать граф (структуру БС) — добавить дуги между несвя-
занными между собой предками каждой вершины сети.
2. Дезориентировать граф — направленные дуги заменить неориенти-
рованными ребрами.
3. Триангулировать граф — привести структуру графа к такому виду,
чтобы не было циклов длиной больше трех.
4. Морализированный триангулированный граф привести к виду графа
клик, т.е. к графу, состоящему из подграфов.
5. Граф клик привести к виду объединенного дерева.
И только после этого можно использовать алгоритм вероятностного вывода
в объединенном дереве, который основывается на прохождении λ и π со-
общений по дереву и последовательном пересчете таблиц условных вероят-
ностей.
В работе [4] предложен метод поглощающего исключения (bucket
elimination). Проблемой, возникающей при использовании этого метода, яв-
ляется обязательное наличие упорядоченного множества вершин, получение
которого является сложной вычислительной задачей. Более подробно анализ
проблемы и обзор методов формирования вероятностного вывода в БС рас-
смотрен в работах [5–7].
Очевидно, что существующие методы формирования вывода, предло-
женные в работах [3, 4], требуют серьезного преобразования структуры БС
и трудоемких подготовительных вычислений. Поэтому разработка методов,
позволяющих уменьшить вычислительную сложность, является актуальной
и востребованной при моделировании процессов различной природы сетями
Байеса.
ПОСТАНОВКА ЗАДАЧИ
Разработка метода вероятностного вывода в БС, состоящего из двух шагов.
На первом шаге выполняется вычисление матрицы эмпирических значений
совместного распределения вероятностей всей сети, на втором — вероятно-
стей всех возможных состояний не инстанциированных вершин.
АЛГОРИТМ ВЕРОЯТНОСТНОГО ВЫВОДА В БС НА ОСНОВЕ
ОБУЧАЮЩИХ ДАННЫХ
Входные данные, необходимые для алгоритма формирования вывода
1. Множество обучающих данных },...,{ 1 nddD = , …,{ )2()1(
iii xxd =
}, )(N
ix… (нижний индекс — номер наблюдения, верхний — переменной),
n — количество наблюдений, состоящих из N ( 2≥N ) переменных
)()2()1( ,...,, NXXX . Каждая j -я переменная ( Nj ,...,1= ) имеет =)( jA
}1,...,1,0{ )( −= jα ( 2)( ≥jα ) состояний.
Алгоритм вероятностного вывода в байесовских сетях
Системні дослідження та інформаційні технології, 2009, № 2 109
2. Структура байесовской сети g , представленная множеством из N
предков ( )()1( ,..., NΠΠ ). Для каждой вершины Nj ,...,1= , )( jΠ — это мно-
жество родительских вершин такое, что }{\},...,{ )()()1()( jNj XXX⊆Π
(вершина не может быть предком для самой себя — петли в графе должны
отсутствовать).
3. Множество инстанциированных вершин == )()()( ,,{ 11 vPPP XxX …
})( vPx= , т.е. вершин, находящихся в некотором определенном состоянии с
единичной вероятностью. Если множество инстанциированных вершин пус-
тое, то нужно использовать классический вероятностный вывод.
Алгоритм формирования вывода
Шаг 1.
По множеству обучающих данных вычисляется матрица эмпириче-
ских значений совместного распределения вероятностей всей сети
),...,( )()1( NXXP . По формуле
n
xXxXnxXxXP
NN
NN ],...,[),...,(
)()()1()1(
)()()1()1(
matrix
==
=== ,
где n — количество обучающих наблюдений; )()( jj Ax ∈ , а числитель вы-
числяется так:
∑
=
=====
n
j
N
j
N
j
NN xXxXIxXxXn
1
)()()1()1()()()1()1( ),...,(],...,[ ,
где функция 1)( =EI , когда предикат true=E , в противном случае
0)( =EI .
Шаг 2.
Перебираем последовательно все вершины БС. Если вершина не явля-
ется инстанциированной, то нужно вычислить значения вероятностей воз-
можных состояний этой вершины. Для этого делается последовательный
перебор всех строк матрицы эмпирических значений совместного распреде-
ления вероятностей сети. Если значения вершин строки совпадают со значе-
ниями инстанциированных вершин и состоянием анализируемой вершины,
то ),...,( )()1(
matrix
NXXP прибавляется к значению вероятности соответст-
вующего состояния вершины. После этого выполняется нормирование зна-
чений вероятностей ее состояний.
Алгоритм вычисления значений вероятностей всех возможных состоя-
ний неинстанциированных вершин
for 1=j to N if },...,{ )()( 1 vPPj XXX ∉ then
begin
0sum = ;
А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 110
)()( jj Ax ∈∀ do
begin
for 1=k to matrixstringlast __ do
begin
if )( )()(
matrix
11 PP xX = and…and )( )()(
matrix
vv PP xX = and )( )()(
matrix
jj xX = then
begin
),...,()()( )(
matrix
)1(
matrixmatrix
)()()()( Njjjj XXPxXPxXP +=== ;
end;
end;
)(sumsum )()( jj xXP =+= ;
end;
)()( jj Ax ∈∀ do
begin
sum
)()(
)()(
)()(
jj
jj xXPxXP =
==
end;
end;
Выходные данные
Выходными данными являются значения вероятностей всех возможных со-
стояний всех неинстанциированных вершин.
ВЫВОДЫ
Моделирование процессов различной природы и сложности при помощи БС
является одним из перспективных современных направлений в области ин-
теллектуального анализа данных. В работе предложен метод формирования
вероятностного вывода на основе БС с использованием обучающих данных.
Этот метод более простой с вычислительной точки зрения по сравнению с
такими методами, как вероятностный вывод в объединенном дереве [3] и
поглощающим исключением [4]. Благодаря использованию информации об
инстанциированных узлах достигается более высокая точность результата
по сравнению с классическим вероятностным выводом, который основыва-
ется на таблицах условных вероятностей. В дальнейшем необходима разра-
ботка более совершенных методов вероятностного вывода для БС с непре-
рывными вершинами, т.е. переменными, подчиняющимися стандартным
законам распределения, а также более интересного случая БС с неполными
обучающими данными. Описанная научно-исследовательская работа вы-
полнена в рамках гранта НТУУ «КПИ» 3/5-ГР.
Алгоритм вероятностного вывода в байесовских сетях
Системні дослідження та інформаційні технології, 2009, № 2 111
ЛИТЕРАТУРА
1. Tuzel O., Porikli F., Meer P. A Bayesian approach to background modeling //
TR2005-033. — Mitsubishi electric research laboratories, December 2005. —
8 p.
2. Yedidia J., Freeman W. and Weiss Y. Understanding belief propagation and its gen-
eralizations // TR-2001-22. — Mitsubishi electric research laboratories, January
2002. — 35 p.
3. Lokeswarappa K.G. Junction trees: motivation // Seminar CSE 714 on advanced top-
ics in machine learning, March 2005. — 57 p.
4. Dechter R. Bucket elimination: a unifying framework for reasoning // ACM
Press. — 1996. — 28, № 61. — P. 1–51.
5. Huang C., Darwiche A. Inference in belief networks: g procedural guide // Interna-
tional journal of approximate reasoning. — 1994. — 11. — P. 1–45.
6. Lepar V., Shenoy P. A Comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-
Shafer Architectures for computing marginals of Probability Distributions // Un-
certainty in artificial intelligence, San Francisco, CA. — 14. — 1999. — P. 328–
337.
7. Murphy K.P. Dynamic Bayesian networks: representation, inference and learning:
A PhD dissertation. — University of California, Berkeley, 2002. — 225 p.
Поступила 30.05.2007
|