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

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

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

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

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

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

Учебник

© Санкт-Петербургский  
 
государственный университет, 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

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

Рассмотрим это выражение подробнее. Для успешного применения формулы Байеса нам придётся дать имена отдельным её частям и понять, что
они означают в философском смысле.
Формула p(x|y) выражает нашу цель — условную вероятность события x
(или, если x и y — случайные величины, того или иного значения случайной
величины x) при условии, что событие y произошло (соответственно, при
данном фиксированном значении случайной величины y). Это апостериорная вероятность x — от слов a posteriori, т. е. вероятность «после опыта»,
после того как мы узнали значение y.
Соответственно, априорная (a priori) вероятность — это значение вероятности x до того момента, как мы зафиксировали y. В формулировке теоремы
Байеса присутствует априорная вероятность p(x) события x — апостериорная вероятность ей прямо пропорциональна.
Величина p(y|x) в числителе правой части формулы Байеса называется правдоподобием x при заданном y. Именно поэтому гипотезы, которые мы в следующем параграфе назовём максимальными апостериорными гипотезами, часто называют гипотезами максимального правдоподобия 1. Если быть точным, функция правдоподобия — это функция вида
fa(y) = p(x = a|y). Теорема Байеса утверждает, что апостериорная вероятность события прямо пропорциональна его правдоподобию.
А вот p(y) не имеет своего специального названия, её можно назвать
маргинальной вероятностью, но это просто означает, что она не является
условной. Эта вероятность и вовсе играет здесь вспомогательную роль. Подсчитать её обычно или совсем просто, или совсем сложно, и в любом случае
для поиска максимальной апостериорной гипотезы не обязательно: достаточно просто подсчитать произведения p(y|x)p(x) для разных значений x, а
затем вспомнить, что p(x|y) — распределение вероятностей, а значит,
a
p(x = a|y) =
a
p(y|x = a)p(x = a) = 1.

Иначе говоря, в теореме Байеса p(y) просто играет роль нормировочной
константы. Теорему часто прямо в таком виде и записывают:

p(x = a|y = b) =
p(y = b|x = a)p(x = a)
a′ p(y = b|x = a′)p(x = a′).

1Термин не используется в учебнике, чтобы не внести путаницу. Дело в том, что основная масса литературы по машинному обучению написана на английском языке, и в ней
уже устоялся даже не просто термин maximal a posteriori, а его аббревиатура MAP.

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

Мы завершим этот параграф одним любопытным применением теоремы
Байеса.

П р и м е р 1.1. Тест с ошибкой

Обратимся к самой классической области применения статистики и байесовского вывода — к медицинской диагностике. Пусть некий тест на какую-нибудь болезнь
имеет вероятность успеха 95 %, причём ошибки в нём могут быть в любую сторону, 5 % — вероятность и позитивной, и негативной ошибки. Пусть болезнь имеется
всего у 1 % респондентов (отложим на время то, что они разного возраста и профессий). И наконец, пусть некий человек получил позитивный результат теста (тест на
наличие заболевания). С какой вероятностью он действительно болен?
Если задать этот вопрос достаточно большой группе людей, то, по нашим наблюдениям, б´ольшая часть присутствующих проголосует за то, что человек болен с
вероятностью более 80 %, и уж точно почти все будут уверены, что человек скорее
болен, чем нет. Согласны ли вы с этой оценкой?
Обозначим через t результат теста, через d — наличие болезни. Итак:

p(d = 1) = p(d = 1|t = 1)p(t = 1) + p(d = 1|t = 0)p(t = 0).

Используем теорему Байеса:

p(d = 1|t = 1) =
p(t = 1|d = 1)p(t = 1)

p(d = 1|t = 1)p(t = 1) + p(d = 1|t = 0)p(t = 0) =

=
0.95 × 0.01

0.95 × 0.01 + 0.05 × 0.99 = 0.16.

Вот такой пример, на первый взгляд, парадоксальный: получается, что среди
имеющих позитивный результат теста со столь высокой степенью надёжности реально больны лишь около 16 %!

На самом деле этот пример несложно интуитивно объяснить. Вероятность ошибки теста в 5 раз больше априорной вероятности наткнуться на
больного пациента. Поэтому ситуация «больной пациент, правильный тест»
будет встречаться гораздо реже ситуации «здоровый пациент, ошибка в тесте». Но практика показывает, что интуиция эта далеко не всегда эффективна даже у людей, казалось бы, прошедших курсы теории вероятностей.
Надеемся, что наш читатель в такие ловушки уже не попадётся.

§ 1.2. Максимальная апостериорная гипотеза
13

§ 1.2. Максимальная апостериорная гипотеза

Выделим несколько основополагающих компонентов алгоритмов машинного обучения. Во-первых, у каждого алгоритма есть некоторое множество гипотез, из которых он пытается выбрать наилучшую. Например, у
нейронных сетей с линейными нейронами множество возможных гипотез —
это множество линейных форм в пространстве с размерностью, соответствующей числу входов, а для сетей с нелинейными нейронами — множество
функций определённого вида.
Во-вторых, всякому алгоритму нужны данные, на основании которых
алгоритмы принимают свои решения. В отличие от множеств гипотез, которые могут быть весьма разнообразными, в качестве данных фактически
любой алгоритм готов принять любые данные, нужно только отформатировать их подходящим образом. Важно, что гипотезу выбирают так, чтобы она
максимально хорошо подходила под данные. Так, например, нейронные сети стараются минимизировать среднеквадратическую ошибку (отклонение
значений, вычисляемых сетью, от истинных значений обучаемой функции).
Эти два компонента в самом общем их виде — почти всё, что нам сейчас
потребуется. Стоит сделать только одно замечание: и гипотезы, и данные
помогут нам только в каких-либо предположениях. Вероятностные предположения всегда нужно вербализовывать, эксплицировать... Проще говоря, надо знать их заранее. Иногда получается, что предположения, которые
неявно требуются для того или иного вывода, на самом деле могут дать гораздо больше. А иногда получается, что даже довольно естественные предположения оказываются достаточно сильными, чтобы однозначно решить
требуемую задачу (нечто подобное рассмотрено в § 10.2).
Итак, предположим, что у нас есть некоторое множество гипотез H и
множество имеющихся данных D (от слова data). Тогда цель любого алгоритма машинного обучения — найти гипотезу, которая была бы наиболее
вероятной при имеющихся данных. Действительно, такое поведение было
бы оптимальным — ничего более эффективного ожидать невозможно. Математически это можно записать следующим образом.

Определение 1.1. Пусть H — множество гипотез, D — множество имеющихся данных. Гипотеза h ∈ H называется максимальной
апостериорной гипотезой (MAP, maximum a posteriori hypothesis), если

h = argmaxh∈Hp(h|D).

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

Перепишем это по теореме Байеса:

h = argmaxh∈Hp(h|D) = argmaxh∈H
p(D|h)p(h)

p(D)
= argmaxh∈Hp(D|h)p(h),

потому что p(D) от h не зависит.
Часто предполагают, что гипотезы изначально равновероятны:

p(hi) = p(hj)

для всех гипотез hi, hj ∈ H. Тогда предыдущее выражение можно переписать
ещё проще:

h = argmaxh∈Hp(D|h).

Эти выражения — суть поиска оптимальной гипотезы. По ним можно
сразу построить алгоритм поиска MAP-гипотезы: всего лишь нужно для
каждой гипотезы h ∈ H вычислить её апостериорную вероятность p(h|D), а
затем выбрать ту из них, для которой эта вероятность максимальна. Разумеется, мы не рекомендуем применять такой алгоритм на практике: в любой
хоть немного реалистичной задаче численность гипотез в множестве сравнима с числом элементарных частиц во Вселенной1.
Основная функция выражений для поиска максимальной апостериорной
гипотезы — не прямо практическая (хотя по ним и можно построить алгоритм). MAP-гипотеза нужна для того, чтобы сравнивать с ней другие алгоритмы и выяснять, когда они работают оптимально. Пример такого подхода
приведён в следующем параграфе.
Итак, чтобы найти максимальную апостериорную гипотезу, нужно научиться вычислять p(h) и p(D|h). Приведём конкретный пример такого расчёта. Пусть выполняются следующие условия:

1) в D нет шума (т. е. все тестовые примеры содержат правильные ответы);
2) целевая функция c содержится среди гипотез H;
3) нет априорных причин верить, что одна из гипотез более вероятна,
чем другая.

1Физики оценивают их численность как число порядка 2100. Иначе говоря, если гипотезами будут конфигурации строки из 100 бит (не так уж и много, эта сноска раз в
десять длиннее), то размер множества таких гипотез как раз будет порядка числа частиц
во Вселенной.