ВВЕДЕНИЕ
1 Общие сведения о теории байесовских сетей
1.1 Байесовские сети 5
1.2 Формула Байеса и формула полной вероятности 6
1.3 Распространение свидетельств в байесовской сети без циклов 6
1.4 Циклы в Байесовских сетях доверия 7
1.5 Алгоритм пропагации свидетельств в байесовской сети с циклами 13
1.6 Пример построения простейшей байесовской сети доверия 15
2 Разработанные алгоритмы пропагации свидетельств 18
2.1 Измененный алгоритм пропагации 18
2.2 Общие формулы для распространения свидетельств 23
2.3 Применения формул для распространения свидетельств на конкретном
примере 25
2.4 Оценка сложности алгоритма 27
3 Апробации алгоритмов и их сравнение 28
3.1 Апробация алгоритмов на сети без циклов 28
3.2 Алгоритм пропагации в байесовских сетях с циклами 31
3.2.1 Подсчет вероятностей по алгоритму Николенко-Тулупьева-
Сироткина 32
3.2.2 Подсчет вероятностей по измененному алгоритму 35
3.2.3 Сравнение результатов работы алгоритма для байесовской сети с
циклами 40
ЗАКЛЮЧЕНИЕ 41
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Байесовские сети широко применяются в таких областях, как медицина, стратегическое планирование, финансы и экономика, а так же являются особенно полезными при разработке и анализе машинных алгоритмов обучения. Не все алгоритмы распространения свидетельств в байесовских сетях работают для сетей с циклами [1,2,3], поэтому разработка таких алгоритмов вполне актуальна.
Объектом исследования являются Байесовские сети.
Предметом исследования являются алгоритмы пропагации в байесовских сетях с циклами.
Целью данной научной работы является разработка алгоритма распространения свидетельств в байесовской сети с циклами.
Задачи исследования:
• Изучить научно-методическую литература по проблеме исследования;
• Проанализировать имеющиеся алгоритмы распространения свидетельств в байесовских сетях;
• Разработать собственный алгоритм распространения свидетельств в байесовских сетях;
• Сравнить разработанный и уже имеющиеся алгоритмы.
В ходе выполнения данной квалификационной работы были изучены теоретические источники по Байесовским сетям, рассмотрены существующие алгоритмы распространения свидетельств в сетях без циклов и с циклами.
В ходе изучения материала сделан вывод о том, что существующие алгоритмы пропагации для сетей с циклами, в большинстве своем, используют системы линейных уравнений. Количество этих систем напрямую зависит от количества циклов, и их предельная сложность сводится к факториалу от количества циклов. Главным недостатком известных алгоритмов принято следующая их особенность: если условные вероятности вершин цикла противоречат друг другу, то противоречие снимается изменением родительских, для цикла вершин.
В разработанном алгоритме распространения свидетельств в байесовских сетях с циклами несогласованность потомков не влияет на априорные вероятности их предков.
Апробации алгоритма выполнена как на искусственных примерах, так и на примерах из статей.
