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

Интернет-магазин: 
www.dmkpress.com

Оптовая продажа: 
КТК «Галактика» 
books@alians-kniga.ru
www.дмк.рф

Особенности книги:

• представлена универсальная рабочая среда, включающая 
все основные классы ВГМ; 

• освещается практическое применение разнообразных методик; 

• рассматриваются все самые последние разработки в области ВГМ, включая многомерные байесовские классификаторы, реляционные графовые модели и причинно-следственные модели;

• в конце каждой главы предлагаются задания и упражнения 
для самостоятельного выполнения, а также направления и 
идеи для исследовательских или программных проектов.

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

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

9 785970 608746

ISBN 978-5-97060-874-6

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

'

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

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

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

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

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

Предисловие от издательства

Отзывы и пожелания

Мы всегда рады отзывам наших читателей. Расскажите нам, что вы 
думаете об этой книге – что понравилось или, может быть, не понравилось. Отзывы важны для нас, чтобы выпускать книги, которые будут для 
вас максимально полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на 
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». 
Также можно послать письмо главному редактору по адресу dmkpress@
gmail.com; при этом укажите название книги в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы 
в написании новой книги, заполните форму на нашем сайте по адресу 
http://dmkpress.com/authors/publish_book/ или напишите в издательство по адресу 
dmkpress@gmail.com.

Скачивание исходного кода примеров

Скачать файлы с дополнительной информацией для книг издательства «ДМК Пресс» можно на сайте www.dmkpress.com на странице с описанием соот ветствующей книги. 

Список опечаток

Хотя мы приняли все возможные меры для того, чтобы обеспечить 
высокое качество наших текстов, ошибки все равно случаются. Если вы 
найдете ошибку в одной из наших книг – возможно, ошибку в основном 
тексте или программном коде, – мы будем очень благодарны, если вы 
сообщите нам о ней. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. 
Если вы найдете какие-либо ошибки в коде, пожалуйста, сообщите о 
них главному редактору по адресу dmkpress@gmail.com, и мы исправим это 
в следующих тиражах.

Нарушение авторских прав

Пиратство в интернете по-прежнему остается насущной проблемой. 
Издательства «ДМК Пресс» и Springer очень серьезно относятся к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в 
интернете с незаконной публикацией какой-либо из наших книг, пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу 
элект ронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.

Вступительное слово

Вероятностные графовые модели и методы их использования для разумных рассуждений и выводов в условиях неопределенности появи лись в 
1980-х гг. в сообществах, занимающихся проблемами статистических 
выводов и искусственного интеллекта. Конференция по неопределенности в области искусственного интеллекта (UAI – Uncertainty in Artificial Intelligence) стала самым первым форумом, посвященным этой 
быстро развивающейся области исследований. На этой конференции 
UAI в 1992 году в Сан Хосе (San Jose) я впервые встретила Энрике Сукара (Enrique Sucar) – тогда мы оба были аспирантами, – он представлял 
свою работу по реляционным и временным (темпоральным) моделям 
для систем высокоуровневой обработки компьютерного зрения. За прошедшие с тех пор 25 лет Энрике внес впечатляющий вклад в эту область 
исследований: от фундаментальной работы по объективной вероятности до разработки усовершенствованных форм вероятностных графовых моделей, таких как временные байесовские сети и байесовские 
сети для вычисления вероятности событий, а также методики обучения 
вероятностных графовых моделей, например самая последняя работа 
Энрике по классификаторам типа байесовская цепь для многомерной 
классификации.
В настоящее время вероятностные графовые модели широко распространены как мощная и вполне сформировавшаяся методика для 
выполнения умозаключений и выводов в условиях неопределенности. 
В отличие от некоторых узкоспециализированных методик, применявшихся в ранних экспертных системах, вероятностные графовые модели основаны на строгих математических принципах теории графов и 
теории вероятностей. Их можно использовать для широкого диапазона 
задач, связанных с выводом и обоснованием результатов, в том числе 
задач прогнозирования, мониторинга, диагностики, оценки рисков и 
принятия решений. Существует множество эффективных алгоритмов 
как для логического вывода, так и для обучения, доступных в виде программного обеспечения с открытым исходным кодом и коммерческих 
программных продуктов. Более того, мощь и эффективность этих алгоритмов уже подтверждена их успешным практическим применением в 
огромном диапазоне областей задач реального окружающего нас мира. 
Энрике Сукар стал главным специалистом по практическому внедрению и утверждению вероятностных графовых моделей как эффективной и полезной технологии с учетом его работы в широком диапазоне 
прикладных областей. Это медицина, реабилитация и здравоохранение 
в целом, робототехника и машинное зрение, образование, анализ надежности и разнообразные промышленные приложения – от нефтедобычи до энергетики.

Вступительное слово  13

Первыми авторами, которые начали исследования байесовских сетей и с большим мастерством убедительно описали их в книгах, стали 
Джуда Перл (Judea Pearl) с книгой «Probabilistic Reasoning in Intelligent 
Systems» и Рич Неаполитан (Rich Neapolitan) с книгой «Probabilistic 
Reasoning in Expert Systems». Предлагаемая читателям монография 
Энрике Сукара представляет собой своевременное дополнение к комплекту литературы, изданной после книг Перла и Неполитана. Эта книга на современном уровне охватывает более широкий диапазон вероятностных графовых моделей, чем другие недавно опубликованные 
материалы в этой области: разнообразные классификаторы, скрытые 
марковские модели, марковские случайные поля, байесовские сети и 
их динамические, временные и причинно-следственные варианты, реляционные вероятностные графовые модели, графы решений и марковский процесс принятия решений. В книге представлены эти вероятностные графовые модели и соответствующие методы логического 
вывода и обуче ния в ясном и доступном стиле. Поэтому издание подходит для студентов старших курсов и аспирантов, а также для ученых-исследователей и инженеров-практиков, работающих в других отраслях и 
интересующихся применением вероятностных моделей. В этой книге 
Энрике делится своим богатым опытом, накопленным в процессе активной практической работы в области использования вероятностных 
графовых моделей, и демонстрирует примеры их применения в разнообразных областях реальной деятельности: от биоинформатики до 
задач наблюдения за загрязнением воздуха и распознавания объектов. 
Я искренне поздравляю Энрике с выходом этой книги и настоятельно 
рекомендую ее будущим читателям.

Энн Е. Николсон,
Мельбурн, Австралия,
май 2015 года

Предисловие

О чем эта книга

Вероятностные графовые модели уже превратились в мощный набор 
методик, используемых в нескольких предметных областях. В этой книге представлен общий вводный курс по вероятностным графовым моделям (probabilistic graphical models – PGM) с учетом их применения в 
инженерных дисциплинах. Здесь подробно рассматриваются главные 
принципы основных классов вероятностных графовых моделей: байесовские классификаторы, скрытые марковские модели, байесовские 
сети, динамические и временные байесовские сети, марковские случайные поля, диаграммы влияния и марковские процессы принятия 
решений. Кроме того, описано представление, процесс логического вывода и принципы обучения для всех этих методик. В книге также рассматриваются реальные приложения для каждого типа модели.
Некоторые характерные особенности этой книги:

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

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