Вероятностные графовые модели. Принципы и приложения

Луис Энрике Сукар

Вероятностные графовые 
модели

Принципы и приложения

Probabilistic Graphical
Models

Principles and Applications

Luis Enrique Sucar

Москва, 2021

Луис Энрике Сукар

Вероятностные графовые 
модели

Принципы и приложения

УДК   004.021
ББК   32.973
С89

С89   Луис Энрике Сукар
Вероятностные графовые модели. Принципы и приложения / пер. 
с англ. А. В. Снастина. – М.: ДМК Пресс, 2021. – 338 с.: ил.

         ISBN 978-5-97060-874-6

В настоящее время вероятностные графовые модели широко распространены как мощная и вполне сформировавшаяся методика для выполнения 
умозаключений и выводов в условиях неопределенности. В отличие от 
некоторых узкоспециализированных методик, применявшихся в ранних 
экспертных системах, вероятностные графовые модели основаны на строгих 
математических принципах теории графов и теории вероятностей. Эта книга 
на современном уровне охватывает более широкий диапазон вероятностных 
графовых моделей, чем другие недавно опубликованные материалы в данной 
области: разнообразные классификаторы, скрытые марковские модели, марковские случайные поля, байесовские сети и их динамические, временные и 
причинно-следственные варианты, реляционные вероятностные графовые 
модели, графы решений и марковский процесс принятия решений. В книге представлены эти вероятностные графовые модели и соответствующие 
методы логического вывода и обучения в ясном и доступном стиле. Автор 
делится своим богатым опытом, накопленным в процессе активной практической работы в области использования вероятностных графовых моделей, и 
демонстрирует примеры их применения в разнообразных областях реальной 
деятельности: от биоинформатики до задач наблюдения за загрязнением 
воздуха и распознавания объектов.
Книга предназначена для студентов старших курсов и аспирантов, а также 
для ученых-исследователей и инженеров-практиков, работающих в других 
отраслях и интересующихся применением вероятностных моделей.

First published in English under the title Concise Computer Vision; Copyright © Springer-Verlag 
London, 2015. This edition has been translated and published under licence from Springer-Verlag 
London Ltd., part of Springer Nature. Springer-Verlag London Ltd., part of Springer Nature takes no 
responsibility and shall not be made liable for the accuracy of the translation. © 2020 by DMK Press. 
All rights reserved.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы 
то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев 
авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность 
технических ошибок все равно существует, издательство не может гарантировать абсолютную 
точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

ISBN 978-1-4471-6698-6 (англ.)            © Springer-Verlag London, 2015
ISBN 978-5-97060-874-6 (рус.)              © Оформление, перевод на русский язык, издание,
 
         ДМК Пресс, 2021

Посвящается моей семье – Дорис, Эдгару и Диане –
за их безграничную любовь и поддержку

Оглавление

Предисловие от издательства ...........................................................................................11
Вступительное слово ...........................................................................................................12
Предисловие .........................................................................................................................14
Благодарности ......................................................................................................................18
Список сокращений, принятых в книге ............................................................................20
Условные математические обозначения, используемые в книге ...............................23

Часть I. Теоретические основы ..........................................................................................25

Глава 1. Введение .................................................................................................................26

1.1 Неопределенность ....................................................................................................................26

1.1.1 Воздействие неопределенности ............................................................................................26

1.2 Краткая история ........................................................................................................................27
1.3 Основные вероятностные модели .....................................................................................28

1.3.1 Пример .............................................................................................................................................31

1.4 Вероятностные графовые модели .....................................................................................33
1.5 Представление, логический вывод и обучение ...........................................................35
1.6 Приложения ................................................................................................................................37
1.7 Обзор содержимого книги ....................................................................................................38
1.8 Материалы для дополнительного чтения .......................................................................39
Ссылки на источники ......................................................................................................................39

Глава 2. Теория вероятностей ............................................................................................41

2.1 Введение ......................................................................................................................................41
2.2 Основные правила ...................................................................................................................43
2.3 Случайные переменные .........................................................................................................45

2.3.1 Двумерные случайные переменные ....................................................................................49

2.4 Теория информации ................................................................................................................50
2.5 Материалы для дополнительного чтения .......................................................................53
2.6 Задания и упражнения ...........................................................................................................53
Ссылки на источники ......................................................................................................................54

Глава 3. Теория графов ........................................................................................................56

3.1 Определения ...............................................................................................................................56
3.2 Типы графов ................................................................................................................................57
3.3 Пути и циклы ..............................................................................................................................58
3.4 Изоморфизм графов ...............................................................................................................60
3.5 Деревья .........................................................................................................................................60
3.6 Клики .............................................................................................................................................63
3.7 Полное упорядочивание ........................................................................................................64
3.8 Алгоритмы упорядочивания и триангуляции ................................................................66

3.8.1 Поиск паросочетания максимальной мощности .............................................................66
3.8.2 Дополнение графа .......................................................................................................................66

Оглавление  7

3.9 Материалы для дополнительного чтения .......................................................................67
3.10 Задания и упражнения.........................................................................................................68
Ссылки на источники ......................................................................................................................69

Часть II. Вероятностные модели ........................................................................................71

Глава 4. Байесовские классификаторы ............................................................................72

4.1 Введение ......................................................................................................................................72

4.1.1 Оценки классификатора ............................................................................................................73

4.2 Байесовский классификатор ................................................................................................74

4.2.1 Наивный байесовский классификатор ................................................................................75

4.3 Другие модели: TAN, BAN ......................................................................................................79
4.4 Частично наивные байесовские классификаторы ......................................................80
4.5 Многомерные байесовские классификаторы ...............................................................84

4.5.1 Многомерные классификаторы на основе байесовских сетей .................................85
4.5.2 Байесовские классификаторы на основе цепи ................................................................86

4.6 Иерархическая классификация ..........................................................................................88

4.6.1 Оценка цепного пути ..................................................................................................................89

4.7 Приложения ................................................................................................................................91

4.7.1 Визуальное определение кожи человека на изображениях ......................................91
4.7.2 Выбор лекарственных средств для лечения вируса иммунодефицита  
человека ..........................................................................................................................................94

4.8 Материалы для дополнительного чтения .......................................................................96
4.9 Задания и упражнения ...........................................................................................................96
Ссылки на источники ......................................................................................................................97

Глава 5. Скрытые марковские модели ...........................................................................100

5.1 Введение ...................................................................................................................................100
5.2 Марковские цепи ...................................................................................................................101

5.2.1 Оценка параметров .................................................................................................................. 104
5.2.2 Сходимость ................................................................................................................................... 105

5.3 Скрытые марковские модели ...........................................................................................106

5.3.1 Вычисление оценки.................................................................................................................. 109
5.3.2 Оценка состояния ...................................................................................................................... 111
5.3.3 Обучение....................................................................................................................................... 114
5.3.4 Расширения ................................................................................................................................. 116

5.4 Приложения .............................................................................................................................118

5.4.1 Алгоритм PageRank ................................................................................................................... 118
5.4.2 Распознавание жестов ............................................................................................................ 119

5.5 Материалы для дополнительного чтения ....................................................................122
5.6 Задания и упражнения ........................................................................................................122
Ссылки на источники ...................................................................................................................123

Глава 6. Марковские случайные поля ............................................................................125

6.1 Введение ...................................................................................................................................125
6.2 Марковские сети .................................................................................................................... 127

6.2.1 Регулярные марковские случайные поля........................................................................ 129

 Оглавление

6.3 Случайные поля Гиббса .......................................................................................................130
6.4 Логический вывод .................................................................................................................131
6.5 Оценка параметров ..............................................................................................................133

6.5.1 Оценка параметров с помощью данных с метками ................................................... 134

6.6 Условные случайные поля ..................................................................................................135
6.7 Приложения ............................................................................................................................. 137

6.7.1 Сглаживание изображений.................................................................................................... 137
6.7.2 Расширенная аннотация изображений ............................................................................ 139

6.8 Материалы для дополнительного чтения ....................................................................142
6.9 Задания и упражнения ........................................................................................................143
Ссылки на источники ...................................................................................................................144

Глава 7. Байесовские сети: представление и логический вывод ...............................146

7.1 Введение ....................................................................................................................................146
7.2 Представление ........................................................................................................................ 147

7.2.1 Структура ....................................................................................................................................... 148
7.2.2 Параметры .................................................................................................................................... 152

7.3 Логический вывод ..................................................................................................................158

7.3.1 Односвязные сети: алгоритм распространения доверия .......................................... 160
7.3.2 Многосвязные сети ................................................................................................................... 165
7.3.3 Приближенный логический вывод ..................................................................................... 174
7.3.4 Наиболее вероятное объяснение ....................................................................................... 177
7.3.5 Непрерывные переменные ................................................................................................... 178

7.4 Приложения ..............................................................................................................................180

7.4.1 Валидация информации ......................................................................................................... 180
7.4.2 Анализ надежности ................................................................................................................... 185

7.5 Материалы для дополнительного чтения .................................................................... 187
7.6 Задания и упражнения .........................................................................................................188
Ссылки на источники ...................................................................................................................189

Глава 8. Байесовские сети: обучение ..............................................................................191

8.1 Введение ...................................................................................................................................191
8.2 Обучение параметров .........................................................................................................191

8.2.1 Сглаживание ................................................................................................................................ 192
8.2.2 Неопределенность параметров ........................................................................................... 192
8.2.3 Недостаточный объем данных ............................................................................................. 194
8.2.4 Дискретизация ............................................................................................................................ 198

8.3 Обучение структуры .............................................................................................................200

8.3.1 Обучение дерева ....................................................................................................................... 200
8.3.2 Обучение полидерева ............................................................................................................. 203
8.3.3 Методики поиска с оценкой ................................................................................................. 204
8.3.4 Методики проверки независимости ................................................................................. 211

8.4 Объединение экспертных знаний и имеющихся данных .....................................212
8.5 Приложения .............................................................................................................................213

8.5.1 Модель загрязнения воздуха в Мехико-сити ................................................................ 214

8.6 Материалы для дополнительного чтения .................................................................... 217

Оглавление  9

8.7 Задания и упражнения ........................................................................................................ 217
Ссылки на источники ...................................................................................................................219

Глава 9. Динамические и временные байесовские сети .............................................221

9.1 Введение ...................................................................................................................................221
9.2 Динамические байесовские сети ....................................................................................222

9.2.1 Логический вывод ..................................................................................................................... 223
9.2.2 Обучение....................................................................................................................................... 224

9.3 Временные сети событий ...................................................................................................226

9.3.1 Байесовские сети с временными узлами ........................................................................ 226

9.4 Приложения .............................................................................................................................233

9.4.1 Динамические байесовские сети: распознавание жестов ....................................... 233
9.4.2 Байесовская сеть с временными узлами: прогнозирование  
вариантов мутаций ВИЧ ........................................................................................................ 238

9.5 Материалы для дополнительного чтения ....................................................................242
9.6 Задания и упражнения ........................................................................................................242
Ссылки на источники ...................................................................................................................243

Часть III. Модели принятия решений ..............................................................................245

Глава 10. Графы принятия решений ...............................................................................246

10.1 Введение .................................................................................................................................246
10.2 Теория принятия решений ............................................................................................... 247

10.2.1 Основы теории принятия решений ................................................................................. 247

10.3 Деревья решений ................................................................................................................251
10.4 Диаграммы влияния ...........................................................................................................254

10.4.1 Моделирование ....................................................................................................................... 254
10.4.2 Оценка ......................................................................................................................................... 256
10.4.3 Расширения ............................................................................................................................... 261

10.5 Приложения ...........................................................................................................................262

10.5.1 Медработник, принимающий теоретические решения .......................................... 262

10.6 Материалы для дополнительного чтения .................................................................266
10.7 Задания и упражнения ......................................................................................................266
Ссылки на источники ...................................................................................................................268

Глава 11. Марковские процессы принятия решений ...................................................269

11.1 Введение .................................................................................................................................269
11.2 Моделирование ...................................................................................................................270
11.3 Вычисление оценки ...........................................................................................................273

11.3.1 Итерация значения ................................................................................................................ 273
11.3.2 Итерация стратегии ............................................................................................................... 274

11.4 Факторизованные марковские процессы принятия решений .........................275

11.4.1 Абстракция................................................................................................................................. 277
11.4.2 Декомпозиция .......................................................................................................................... 278

11.5 Частично наблюдаемые марковские процессы принятия решений .............279
11.6 Приложения ...........................................................................................................................280

11.6.1 Управление электростанцией ............................................................................................ 280

 Оглавление

11.6.2 Согласование задач робота ................................................................................................ 283

11.7 Материалы для дополнительного чтения ..................................................................289
11.8 Задания и упражнения......................................................................................................289
Ссылки на источники ...................................................................................................................291

Часть IV. Реляционные и причинно-следственные модели ........................................293

Глава 12. Реляционные вероятностные графовые модели ........................................294

12.1 Введение .................................................................................................................................294
12.2 Логика ......................................................................................................................................296

12.2.1 Логика высказываний ........................................................................................................... 296
12.2.2 Логика предикатов первого порядка ............................................................................. 297

12.3 Вероятностные реляционные модели ........................................................................300

12.3.1 Логический вывод .................................................................................................................. 302
12.3.2 Обучение .................................................................................................................................... 302

12.4 Марковские логические сети .........................................................................................302
12.4.1 Логический вывод ...........................................................................................................305

12.4.2 Обучение .................................................................................................................................... 305

12.5 Приложения ...........................................................................................................................306

12.5.1 Моделирование студента .................................................................................................... 306

12.6 Вероятностная реляционная модель студента ........................................................ 307

12.6.1 Визуальные грамматики ...................................................................................................... 310

12.7 Материалы для дополнительного чтения ..................................................................312
12.8 Задания и упражнения......................................................................................................313
Ссылки на источники ...................................................................................................................314

Глава 13. Графовые причинно-следственные модели ................................................316

13.1 Введение .................................................................................................................................316
13.2 Причинно-следственные байесовские сети .............................................................318
13.3 Обоснование причин .........................................................................................................320

13.3.1 Прогноз ....................................................................................................................................... 320
13.3.2 Контрфактуальный анализ .................................................................................................. 322

13.4 Обучение причинно-следственных моделей ..........................................................323
13.5 Приложения ...........................................................................................................................325

13.5.1 Обучение причинно-следственной модели для синдрома дефицита  
внимания и гиперактивности .............................................................................................. 325

13.6 Материалы для дополнительного чтения ................................................................. 327
13.7 Задания и упражнения ...................................................................................................... 327
Ссылки на источники ...................................................................................................................328

Словарь терминов ..............................................................................................................329

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