Основы теории байесовских сетей

А. Л. Тулупьев, С. И. Николенко,  
А. В. Сироткин

ОСНОВЫ ТЕОРИИ 
БАЙЕСОВСКИХ СЕТЕЙ

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ИНФОРМАТИКИ  
И АВТОМАТИЗАЦИИ РОССИЙСКОЙ АКАДЕМИИ НАУК

Учебник

© Санкт-Петербургский  
 
государственный университет, 2019

© А. Л. Тулупьев, С. И. Николенко, 
 
А. В. Сироткин, 2019

УДК 004.8 + 519.2
ББК 22.17
         Т82

Реценз ен ты: д-р физ.-мат. наук, проф. Н. В. Хованов (С.-Петерб. гос. ун-т); д-р физ.-мат. наук, 
проф. А. И. Шашкин (ВГУ)

Рекомендовано к печати  
учебно-методической комиссией математико-механического факультета  
Санкт-Петербургского государственного университета

Тулупьев А. Л., Николенко С. И., Сироткин А. В.
Основы теории байесовских сетей: учебник. — СПб.: Изд-во С.-Петерб. 
ун-та, 2019. — 399 с. 
ISBN 978-5-288-05892-9

Цель данного учебника — ознакомить читателя с байесовскими сетями доверия как логико-вероятностной графической моделью баз фрагментов знаний с неопределен ностью, 
которую можно использовать в интеллектуальных системах, поддерживающих принятие 
решений, а также с алгебраическими байесовскими сетями, позволяющими обработку не 
только скалярных, но и интервальных оценок вероятностей, и с их приложе ниями. В основу учебника положен курс лекций, разработанный и читаемый авторами для студентов 
магистратуры СПбГУ. Настоящее издание полностью обеспечивает программу учебной 
дисциплины «Теория байесовских сетей» Санкт-Петербургского государственного университета, которая входит в вариативную часть первого семестра обучения по основной 
образовательной программе высшего образования магистратуры «Математическое обеспечение и администрирование информационных систем».
Учебник адресован студентам и аспирантам, специализирующимся в области математики и информатики, а также специалистам, в круг профессиональных интересов которых входят теория и практические приложения байесовских сетей.

УДК 004.8+519.2 
ББК 22.17

Т82

ISBN 978-5-288-05892-9

Издание подготовлено при частичной финансовой поддержке  
Грантового конкурса Стипендиальной программы  
Владимира Потанина 2016/2017» (проект ГК170001610).

Оглавление

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

Глава 1.
Математическая статистика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
§ 1.1.
Теорема Байеса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
§ 1.2.
Максимальная апостериорная гипотеза . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
§ 1.3.
Байесовские классификаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
§ 1.4.
Корреляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
§ 1.5.
Критерий χ2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26

Глава 2.
Графы смежности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
§ 2.1.
Основные понятия теории графов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
§ 2.2.
Графы смежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
§ 2.3.
Деревья, цепи и циклы смежности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34

Глава 3.
Матричное исчисление. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
§ 3.1.
Произведение и степень Кронекера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
§ 3.2.
Особые семейства векторов и матриц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39

Глава 4.
Вероятностная логика. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
§ 4.1.
Пропозициональная логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
§ 4.2.
Вероятность пропозициональной формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
§ 4.3.
Недоопределённые вероятностные меры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
§ 4.4.
Логика рассуждений о вероятностях. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
§ 4.5.
Логика недоопределённых вероятностных мер. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 4.6.
Матрично-векторная трактовка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
§ 4.7.
Случайные бинарные последовательности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
§ 4.8.
Теория потенциалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65

Глава 5.
Тропинчатые модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
§ 5.1.
Принципы Райхенбаха. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
§ 5.2.
Типы причинно-следственных связей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
§ 5.3.
Подход Райта к причинно-следственным моделям . . . . . . . . . . . . . . . . . . . . . . . . .
70
§ 5.4.
Линейная рекурсивная модель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
§ 5.5.
Принципы декомпозиции Райта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82

3

Глава 6.
БСД: основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
§ 6.1.
Направленный граф причинно-следственных связей . . . . . . . . . . . . . . . . . . . . . .
83
§ 6.2.
Условие марковости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
§ 6.3.
Понятие d-разделимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
§ 6.4.
Правило декомпозиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
§ 6.5.
Правило декомпозиции со свидетельствами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93

Глава 7.
БСД: преобразование структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
§ 7.1.
Доменные, моральные и триангулярные графы . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
§ 7.2.
Дерево смежности и дерево сочленений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
§ 7.3.
Построение дерева сочленений и триангуляция. . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Глава 8.
БСД: алгоритмы пропагации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
§ 8.1.
Алгоритм первичной пропагации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
§ 8.2.
Алгоритм пропагации свидетельств. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
§ 8.3.
Некоторые возможности ускорения алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
§ 8.4.
Стохастическое моделирование. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Глава 9.
Обучение причинно-следственных моделей. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
§ 9.1.
Абдукция и сложности перебора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
§ 9.2.
Выявление структуры условной независимости. . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
§ 9.3.
Марковская эквивалентность. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
§ 9.4.
Алгоритм PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
§ 9.5.
Причинно-следственные связи и регрессии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Глава 10.
Обучение структур зависимостей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
§ 10.1.
Обучение локальной структуры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
§ 10.2.
Вывод байесовской метрики Дирихле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
§ 10.3.
Алгоритм K2 Купера и Герсковица. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
§ 10.4.
MDL-обучение глобальных структур. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
§ 10.5.
Метрический подход к выявлению паттернов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
§ 10.6.
CaMML: глобальная структура и MML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
§ 10.7.
Стохастический поиск в CaMML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

Глава 11.
Локальный вывод в АБС . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
§ 11.1.
Фрагмент знаний АБС . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
§ 11.2.
Непротиворечивость фрагмента знаний. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
§ 11.3.
Локальный априорный вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
§ 11.4.
Локальный апостериорный вывод и свидетельства . . . . . . . . . . . . . . . . . . . . . . . . 200
§ 11.5.
Структура матрицы T ⟨i,j⟩ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
§ 11.6.
Апостериорный вывод над интервальными оценками. . . . . . . . . . . . . . . . . . . . . . 206
§ 11.7.
Недетерминированные свидетельства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

Глава 12.
Глобальный вывод в АБС. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
§ 12.1.
Степени непротиворечивости. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
§ 12.2.
Апостериорный вывод: общая схема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
§ 12.3.
Апостериорный вывод: стохастическое свидетельство . . . . . . . . . . . . . . . . . . . . . 225
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Глава 13.
Вероятностная семантика байесовских сетей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
§ 13.1.
Распределения в дереве смежности БСД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
§ 13.2.
Распределения при условной независимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
§ 13.3.
Преобразование БСД в АБС: пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Глава 14.
Цикл в АБС. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
§ 14.1.
Основные обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
§ 14.2.
Выделение подцепи из цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
§ 14.3.
Преобразование цикла в цепь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
§ 14.4.
Сложность обработки цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

Глава 15.
Направленный цикл в БСД. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
§ 15.1.
Основные обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
§ 15.2.
Преобразование в цикл ФЗ АБС . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
§ 15.3.
Подход Гиббса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
§ 15.4.
Непротиворечивость направленного цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Глава 16.
Обучение АБС и поддержка принятия решений. . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
§ 16.1.
Синтез согласованных баз фрагментов знаний. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
§ 16.2.
Локальное обучение АБС . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
§ 16.3.
Глобальное обучение АБС. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
§ 16.4.
Чувствительность локального априорного вывода . . . . . . . . . . . . . . . . . . . . . . . . . 304
§ 16.5.
Чувствительность локального апостериорного вывода. . . . . . . . . . . . . . . . . . . . . 308
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

Глава 17.
Байесовские сети: примеры приложений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
§ 17.1.
Тест последовательных разведений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
§ 17.2.
Цикл стохастических предпочтений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
§ 17.3.
Генерация популяции в генетическом алгоритме . . . . . . . . . . . . . . . . . . . . . . . . . . 316
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

Глава 18.
Другие вероятностные графические модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
§ 18.1.
Скрытые марковские модели. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
§ 18.2.
Марковские сети. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
§ 18.3.
БСД и марковские сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
§ 18.4.
Модель Изинга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
§ 18.5.
Случайные булевские сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
Контроль усвоения материала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Приложение. Методическое обеспечение дисциплины «Теория байесовских сетей». . . . 352
1.
Аннотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
2.
Основные результаты обучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
3.
Примерный список вопросов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
4.
Перечень дидактических единиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
5.
Методические особенности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
6.
Рекомендуемые информационные источники . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
7.
Задания и темы для проектов и НИР . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
8.
Основные классы заданий. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378

Список иллюстраций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Введение

Проблема промышленного внедрения интеллектуальных систем поддержки принятия решений, использующих данные и знания с неопределенностью и способных их обрабатывать, становится все более актуальной [23].
Решению этой проблемы препятствуют, в частности, два так называемых
узких места:

1) дефицит моделей для представления данных и знаний с неопределенностью (uncertain knowledge representation bottleneck);
2) дефицит данных и знаний (knowledge bottleneck) [132].

Дефицит первого вида возникает по достаточно очевидной причине:
непонятно, как в формальных системах представить и систематически обрабатывать неопределенность (недоопределенность) наших знаний, с которой зачастую приходится сталкиваться на практике. Тривиальные решения,
которые сводятся просто к тому, чтобы отбросить знания (или данные) с
неполнотой, непригодны по двум причинам:

— во-первых, отнюдь не во всех предметных областях за разумное время можно получить «полные знания»;
— во-вторых, человек способен действовать и в условиях неполноты
знаний о складывающейся ситуации, поэтому задача обучить компьютер поступать так же — одна из важнейших задач искусственного
интеллекта.

Дефицит второго вида более острый. Есть предметные области, где просто не существует человека-эксперта. Кроме того, не все эксперты готовы делиться своим знанием. Наконец, при попытках организовать автоматическое
обучение по доступным базам данных вдруг обнаруживается, что данные из
баз неполны или частично недостоверны.
Чтобы поставить цель работы, рассмотрим формальные аспекты обозначенных узких мест с двух сторон.
С точки зрения искусственного интеллекта объектом исследования
изначально выступает совокупность знаний эксперта (или более широко —

7

Введение

совокупность экспертных знаний) о предметной области. В своих рассуждениях о ней эксперты не связывают «все объекты со всеми». Как правило,
их высказывания характеризуют либо одну сущность из предметной области, либо связи между двумя-четырьмя сущностями, не более. Таким образом, всю совокупность экспертных знаний — базу знаний (БЗ) — можно
разделить (декомпозировать) на фрагменты знаний (ФЗ), которые описывают связи между небольшим числом сущностей, но при этом очень подробно.
Фрагменты знаний могут иметь общие элементы, и в сумме они образуют
систему, которую точнее было бы назвать базой фрагментов знаний (БФЗ).
Фрагменты знаний и их системы, конечно, невозможно «напрямую»
представить в компьютерной программе или реляционной базе данных. В
первую очередь требуется решить вопросы о том, что является математической моделью фрагмента знаний и как из этих локальных моделей строится
глобальная — математическая — модель базы фрагментов знаний.
В теории байесовских сетей доверия (БСД) [160] математической моделью фрагмента знаний выступает тензор условных вероятностей, а математической моделью базы фрагментов знаний — собственно байесовская сеть
доверия, которая является ациклическим направленным графом с тензорами условных вероятностей в узлах. Заметим, что байесовской сети доверия
однозначно можно сопоставить единственное совместное распределение вероятностей означиваний всех элементов, стоящих в её узлах. Это свойство
либо задаётся в одной из версий определения БСД, либо выводится из свойства d-разделимости (direction dependent separation), входящего как требование в другую версию определения. (Формальные определения всех этих
объектов и понятий даны в соответствующих гл. 5 и 6.)
С точки зрения чистой математики байесовские сети доверия представляют собой способ косвенно задать совместное распределение вероятностей случайных бинарных (или многозначных) элементов. Прямо задать
данное распределение представляется невозможным в силу того, что при
этом потребовалось бы указать или оценить слишком много величин. Например, чтобы напрямую задать совместное распределение 100 бинарных
элементов, потребуется указать 2100 значений, что само по себе, конечно, абсолютно вычислительно неприемлемо (элементарных частиц во Вселенной,
по современным данным, значительно меньше).
Косвенно задать такое распределение можно, если совместное распределение вероятностей допускает декомпозицию, т. е. его можно (пусть хотя бы
гипотетически) восстановить по совокупности распределений, заданных над

Введение
9

небольшими наборами случайных элементов. Например, если всё распределение однозначно восстанавливается по распределениям над каждой парой
соседних бинарных элементов, то для 100 бинарных элементов потребуется
указать лишь 199 величин — колоссальный выигрыш по сравнению с 2100.
Цели учебника следующие:

1) исследовать байесовские сети доверия как логико-вероятностную
графическую модель баз фрагментов знаний с неопределённостью,
которую можно использовать в интеллектуальных системах, поддерживающих принятие решений, т. е. описать её вероятностную семантику, операции первичной пропагации и пропагации свидетельства,
способы автоматического (машинного) обучения её структуры и параметров;
2) произвести её сравнение с алгебраическими байесовскими сетями
(АБС) — ещё одной логико-вероятностной графической моделью,
позволяющей обработку не только скалярных, но и интервальных
оценок вероятностей [3];
3) привести примеры приложений байесовских сетей и кратко охарактеризовать другие виды вероятностных графических моделей.

В учебнике в значительной степени используются, уточняются, систематизируются и развиваются определения, результаты и система обозначений,
сложившиеся в более ранних работах авторов, в частности [22,36,38,42–44,
46,55,56,61] и др.
Сложившаяся структура учебника полностью соответствует структуре
рабочей программы учебной дисциплины «Теория байесовских сетей», читаемой студентам магистратуры по направлениям «Математическое обеспечение и администрирование информационных систем» и «Фундаментальная информатика и информационные технологии». Она учитывает требования последовательности и дозированности изложения материала, а также
сложность и связь его фрагментов с разными математическими теориями. В
частности, по этой причине освещение особых вопросов из теории графов и
матричного исчисления выделены в небольшие по объёму самостоятельные
гл. 2 и 3.

Г л а в а 1
Математическая статистика

Значительная часть учебника посвящена автоматическому обучению
(машинному обучению) вероятностных моделей знаний с неопределенностью; описать алгоритмы этого обучения — одна из основных его целей (см.
также работу [22], где мы излагаем основные методы машинного обучения).
Однако стоит отметить, что многие из этих методов и алгоритмов можно без
труда отнести к математической статистике: она тоже оперирует с данными,
и результат работы соответствующих алгоритмов тем лучше (точнее), чем
больше данных им предоставить. Да и не нужно «трогать, пока работает»:
если в реальном приложении можно просто обучить линейную регрессионную модель или проверить несколько гипотез хи-квадратом, зачем «огород
городить» и придумывать особые алгоритмы представления недоопределённых данных и их автоматического обучения, которые наверняка всё равно
сойдутся к тому же самому?
В этой главе мы вводим те основные понятия математической статистики, которые будут активно использоваться дальше, в главах об автоматическом обучении байесовских сетей доверия и родственных им объектов.

§ 1.1. Теорема Байеса

Нашим основным инструментом станет теорема Байеса:

p(x ∧ y) = p(x|y)p(y) = p(y|x)p(x).

Отсюда следует, что если p(y) ̸= 0, то

p(x|y) = p(y|x)p(x)

p(y)
.

10