УДК 004.42
ББК 32.973
П91
П91 Ави Пфеффер
Вероятностное программирование на практике. / Пер. с англ. Слинкин
А. А. – М.: ДМК Пресс, 2017. – 462 с.: ил.
ISBN 978-5-97060-410-6
Книга представляет собой введение в вероятностное программирование
для программистов-практиков. Описан вероятностный вывод, где алгоритмы
помогают прогнозировать использование социальных сетей. Приведены
примеры построения фильтра спама, диагностики ошибок в вычислительной
системе, восстановления цифровых изображений. Представлен функциональный
стиль программирования для анализа текстов, объектно-ориентированных
моделей и моделей с открытой вселенной.
Издание рассчитано на широкий круг читателей: специалистов по анализу
данных и машинному обучению, программистов, студентов вузов и др.
УДК 004.42
ББК 32.973
Original English language edition published by Manning Publications Co., Rights and
Contracts Special Sales Department, 20 Baldwin Road, PO Box 261, Shelter Island, NY
11964. © 2016 by Manning Publications Co. All rights reserved. Russian-language edition
copyright © 2016 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена
в какой бы то ни было форме и какими бы то ни было средствами без письменного
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку
вероятность технических ошибок все равно существует, издательство не может гарантировать
абсолютную точность и правильность приводимых сведений. В связи
с этим издательство не несет ответственности за возможные ошибки, связанные с
использованием книги.
ISBN 978-1-61729-233-0 (англ.)
ISBN 978-5-97060-410-6 (рус.)
© 2016 by Manning Publications Co.
© Оформление, перевод на русский язык,
издание, ДМК Пресс, 2017
Стр.5
ОГЛАВЛЕНИЕ
Предисловие..........................................................................13
Вступление. ........................................................................... 15
Благодарности........................................................................ 17
Об.этой.книге..........................................................................19
Структура книги ...........................................................................................20
О коде и упражнениях ..................................................................................21
Об авторе ..........................................................................................................21
Автор в сети .................................................................................................22
Об иллюстрации на обложке .............................................................................22
ЧАСТЬ.I
Введение.в.вероятностное.программирование.и.систему.Figaro...... 23
Глава.1..О.вероятностном.программировании.в.двух.словах........... 24
1.1. Что такое вероятностное программирование? ............................................24
1.1.1. Как мы высказываем субъективное суждение? ...................................25
1.1.2. Системы вероятностных рассуждений помогают принимать решения 26
1.1.3. Система вероятностных рассуждений может рассуждать тремя
способами ...................................................................................................28
1.1.4. Система вероятностного программирования: система вероятностных
рассуждений, выраженная на языке программирования ..............................32
1.2. Зачем нужно вероятностное программирование? ......................................37
1.2.1. Улучшенные вероятностные рассуждения ...........................................37
1.2.2. Улучшенные языки имитационного моделирования ............................38
1.3. Введение в Figaro, язык вероятностного программирования ......................40
1.3.1. Figaro и Java: построение простой системы вероятностного
программирования ......................................................................................43
1.4. Резюме .......................................................................................................48
1.5. Упражнения ................................................................................................48
Глава.2..Краткое.руководство.по.языку.Figaro............................... 50
2.1. Введение в Figaro .......................................................................................50
2.2. Создание модели и выполнение алгоритма вывода на примере Hello World 52
2.2.1. Построение первой модели ................................................................53
2.2.2. Выполнение алгоритма вывода и получение ответа на запрос ............54
Стр.7
Оглавление
7
2.2.3. Построение моделей и задание наблюдений ......................................55
2.2.4. Анатомия построения модели .............................................................56
2.2.5. Повторяющиеся элементы: когда они совпадают,
а когда различаются? ...................................................................................58
2.3. Базовые строительные блоки: атомарные элементы ..................................59
2.3.1. Дискретные атомарные элементы ......................................................60
2.3.2. Непрерывные атомарные элементы....................................................61
2.4. Комбинирование атомарных элементов с помощью составных ..................64
2.4.1. Элемент If ...........................................................................................64
2.4.2. Элемент Dist .......................................................................................65
2.4.3. Составные версии атомарных элементов ...........................................66
2.5. Построение более сложных моделей с помощью Apply и Chain ...................67
2.5.1. Элемент Apply .....................................................................................67
2.5.2. Элемент Chain ....................................................................................70
2.6. Задание фактов с помощью условий и ограничений ...................................73
2.6.1. Наблюдения ........................................................................................73
2.6.2. Условия ..............................................................................................74
2.6.3. Ограничения .......................................................................................75
2.7. Резюме .......................................................................................................78
2.8. Упражнения ................................................................................................78
Глава.3..Создание.приложения.вероятностного..
программирования.................................................................. 80
3.1. Общая картина ...........................................................................................80
3.2. Выполнение кода ........................................................................................83
3.3. Архитектура приложения фильтра спама ....................................................86
3.3.1. Архитектура аналитического компонента ............................................86
3.3.2. Архитектура компонента обучения ......................................................90
3.4. Проектирование модели почтового сообщения ..........................................92
3.4.1. Выбор элементов ................................................................................93
3.4.2. Определение зависимостей ...............................................................95
3.4.3. Определение функциональных форм ..................................................97
3.4.4. Использование числовых параметров .............................................. 100
3.4.5. Работа с дополнительными знаниями ............................................... 102
3.5. Разработка аналитического компонента ................................................... 104
3.6. Разработка компонента обучения ............................................................. 108
3.7. Резюме ..................................................................................................... 112
3.8. Упражнения .............................................................................................. 113
ЧАСТЬ.II
Написание.вероятностных.программ........................................ 115
Глава.4..Вероятностные.модели.и.вероятностные.программы....... 116
4.1. Определение вероятностной модели........................................................ 117
Стр.8
8
Оглавление
4.1.1. Выражение общих знаний в виде распределения вероятности
возможных миров ...................................................................................... 117
4.1.2. Подробно о распределении вероятности .......................................... 120
4.2. Использование вероятностной модели для ответа на запросы ................. 121
4.2.1. Применение условий для получения апостериорного
распределения вероятности ...................................................................... 122
4.2.2. Получение ответов на запросы ......................................................... 124
4.2.3. Применение вероятностного вывода ................................................ 126
4.3. Составные части вероятностных моделей ................................................ 127
4.3.1. Переменные ..................................................................................... 127
4.3.2. Зависимости .................................................................................... 129
4.3.3. Функциональные формы ................................................................... 134
4.3.4. Числовые параметры ........................................................................ 138
4.4. Порождающие процессы .......................................................................... 140
4.5. Модели с непрерывными переменными ................................................... 144
4.5.1. Бета-биномиальная модель .............................................................. 145
4.5.2. Представление непрерывных переменных ........................................ 146
4.6. Резюме ..................................................................................................... 150
4.7. Упражнения .............................................................................................. 150
Глава.5..Моделирование.зависимостей.с.помощью.байесовских.
и.марковских.сетей................................................................ 152
5.1. Моделирование зависимостей ................................................................. 153
5.1.1. Направленные зависимости ............................................................. 153
5.1.2. Ненаправленные зависимости .......................................................... 159
5.1.3. Прямые и косвенные зависимости .................................................... 162
5.2. Байесовские сети ..................................................................................... 163
5.2.1. Определение байесовской сети ........................................................ 163
5.2.2. Как байесовская сеть определяет распределение вероятности ........ 166
5.2.3. Рассуждения с применением байесовской сети ............................... 166
5.3. Изучение примера байесовской сети ........................................................ 169
5.3.1. Проектирование модели диагностики компьютерной системы ......... 169
5.3.2. Рассуждения с помощью модели диагностики компьютерной
системы ..................................................................................................... 174
5.4. Применение вероятностного программирования для обобщения
байесовских сетей: предсказание успешности продукта ................................. 179
5.4.1. Проектирование модели для предсказания успешности продукта .... 180
5.4.2. Рассуждения с помощью модели для предсказания успешности
продукта .................................................................................................... 185
5.5. Марковские сети ...................................................................................... 187
5.5.1. Определение марковской сети ......................................................... 187
5.5.2. Представление марковских сетей и рассуждения с их помощью ....... 191
5.6. Резюме ..................................................................................................... 195
5.7. Упражнения .............................................................................................. 195
Стр.9
Оглавление
9
Глава.6..Использование.коллекций.Scala.и.Figaro.для.построения.
моделей. ............................................................................. 198
6.1. Работа с коллекциями Scala ...................................................................... 199
6.1.1. Моделирование зависимости многих переменных от одной ............. 200
6.1.2. Создание иерархических моделей .................................................... 203
6.1.3. Моделирование одновременной зависимости от двух переменных .... 205
6.2. Работа с коллекциями Figaro ..................................................................... 208
6.2.1. Почему коллекции Figaro полезны? ................................................... 208
6.2.2. Иерархическая модель и коллекции Figaro ........................................ 210
6.2.3. Совместное использование коллекций Scala и Figaro ....................... 212
6.3. Моделирование ситуаций с неизвестным числом объектов ...................... 215
6.3.1. Открытая вселенная с неизвестным числом объектов ....................... 215
6.3.2. Массивы переменной длины ............................................................. 216
6.3.3. Операции над массивами переменной длины ................................... 217
6.3.4. Пример: прогнозирование продаж неизвестного числа новых
продуктов................................................................................................... 218
6.4. Работа с бесконечными процессами ........................................................ 220
6.4.1. Характеристика Process .................................................................... 220
6.4.2. Пример: моделирование состояния здоровья во времени ................ 222
6.4.3. Использование процесса .................................................................. 224
6.5. Резюме ..................................................................................................... 225
6.6. Упражнения .............................................................................................. 226
Глава.7..Объектно-ориентированное.вероятностное..
моделирование..................................................................... 228
7.1. Объектно-ориентированные вероятностные модели ................................ 229
7.1.1. Элементы объектно-ориентированного моделирования ................... 230
7.1.2. Еще раз о модели принтера .............................................................. 232
7.1.3. Рассуждения о нескольких принтерах ............................................... 236
7.2. Добавление связей в объектно-ориентированные модели ....................... 240
7.2.1. Описание общей модели на уровне классов ..................................... 240
7.2.2. Описание ситуации ........................................................................... 243
7.2.3. Представление модели социальной сети на Figaro ........................... 246
7.3. Моделирование реляционной неопределенности и неопределенности
типа ................................................................................................................ 249
7.3.1. Коллекции элементов и ссылки ......................................................... 249
7.3.2. Модель социальной сети с реляционной неопределенностью .......... 252
7.3.3. Модель принтера с неопределенностью типа ................................... 254
7.4. Резюме ..................................................................................................... 257
7.5. Упражнения .............................................................................................. 257
ГЛАВА.8..Моделирование.динамических.систем......................... 259
8.1. Динамические вероятностные модели...................................................... 260
8.2. Типы динамических моделей .................................................................... 261
Стр.10
10
Оглавление
8.2.1. Марковские цепи .............................................................................. 261
8.2.2. Скрытые марковские модели ............................................................ 265
8.2.3. Динамические байесовские сети ...................................................... 268
8.2.4. Модели с нестационарной структурой .............................................. 272
8.3. Моделирование систем, работающих неопределенно долго .................... 277
8.3.1. Универсумы в Figaro ......................................................................... 277
8.3.2. Использование универсумов для моделирования постоянно
работающих систем ................................................................................... 279
8.3.3. Следящее приложение ..................................................................... 281
8.4. Резюме ..................................................................................................... 284
8.5. Упражнения .............................................................................................. 284
ЧАСТЬ.III
Вывод.................................................................................. 287
Глава.9..Три.правила.вероятностного.вывода............................. 288
9.1. Цепное правило: построение совместных распределений по условным
распределениям вероятности ......................................................................... 290
9.2. Правило полной вероятности: получение ответов на простые запросы
из совместного распределения ....................................................................... 294
9.3. Правило Байеса: вывод причин из следствий ........................................... 297
9.3.1. Понимание, причина, следствие и вывод .......................................... 297
9.3.2. Правило Байеса на практике ............................................................. 299
9.4. Байесовское моделирование.................................................................... 301
9.4.1. Оценивание асимметрии монеты ...................................................... 303
9.4.2. Предсказание результата следующего подбрасывания .................... 307
9.5. Резюме ..................................................................................................... 312
9.6. Упражнения .............................................................................................. 312
Глава.10..Факторные.алгоритмы.вывода................................... 314
10.1. Факторы ................................................................................................. 315
10.1.1. Что такое фактор? ........................................................................... 315
10.1.2. Факторизация распределения вероятности с помощью цепного
правила ...................................................................................................... 318
10.1.3. Задание запросов с факторами с помощью правила полной
вероятности ............................................................................................... 320
10.2. Алгоритм исключения переменных ......................................................... 324
10.2.1. Графическая интерпретация ИП ...................................................... 325
10.2.2. Исключение переменных как алгебраическая операция .................. 329
10.3. Использование алгоритма ИП ................................................................. 332
10.3.1. Особенности ИП в Figaro ................................................................. 332
10.3.2. Проектирование модели, эффективно поддерживающей ИП .......... 334
10.3.3. Приложения алгоритма ИП ............................................................. 338
10.4. Распространение доверия ...................................................................... 342
Стр.11
Оглавление
11
10.4.1. Основные принципы РД .................................................................. 342
10.4.2. Свойства циклического РД .............................................................. 343
10.5. Использование алгоритма РД ................................................................. 345
10.5.1. Особенности РД в Figaro ................................................................. 346
10.5.2. Проектирование модели, эффективно поддерживающей РД .......... 347
10.5.3. Приложения алгоритма РД .............................................................. 349
10.6. Резюме ................................................................................................... 350
10.7. Упражнения ............................................................................................ 350
Глава.11..Выборочные.алгоритмы............................................ 353
11.1. Принцип работы выборочных алгоритмов ............................................... 354
11.1.1. Прямая выборка.............................................................................. 355
11.1.2. Выборка с отклонением .................................................................. 360
11.2. Выборка по значимости .......................................................................... 363
11.2.1. Как работает выборка по значимости .............................................. 364
11.2.2. Выборка по значимости в Figaro ...................................................... 367
11.2.3. Полезность выборки по значимости ................................................ 368
11.2.4. Приложения алгоритма выборки по значимости ............................. 370
11.3. Алгоритм Монте-Карло по схеме марковской цепи ................................. 373
11.3.1. Как работает MCMC ........................................................................ 374
11.3.2. Алгоритм MCMC в Figaro: алгоритм Метрополиса-Гастингса........... 378
11.4. Настройка алгоритма МГ ........................................................................ 382
11.4.1. Специальные схемы предложения .................................................. 384
11.4.2. Избежание жестких условий ........................................................... 388
11.4.3. Приложения алгоритма МГ ............................................................. 389
11.5. Резюме ................................................................................................... 391
11.6. Упражнения ............................................................................................ 392
Глава.12..Решение.других.задач.вывода.................................... 394
12.1. Вычисление совместных распределений ................................................ 395
12.2. Вычисление наиболее вероятного объяснения ....................................... 397
12.2.1. Вычисление и запрос НВО в Figaro .................................................. 400
12.2.2. Использование алгоритмов для ответа на запросы НВО ................. 402
12.2.3. Приложения алгоритмов НВО ......................................................... 409
12.3. Вычисление вероятности фактов ............................................................ 410
12.3.1. Наблюдение фактов для вычисления вероятности фактов .............. 411
12.3.2. Выполнение алгоритмов вычисления вероятности фактов .............. 414
12.4. Резюме ................................................................................................... 415
12.5. Упражнения ............................................................................................ 415
Глава.13..Динамические.рассуждения.и.обучение.параметров...... 417
13.1. Мониторинг состояния динамической системы ...................................... 418
13.1.1. Механизм мониторинга .................................................................. 419
13.1.2. Алгоритм фильтрации частиц .......................................................... 421
Стр.12
12
Оглавление
13.1.3. Применения фильтрации ................................................................ 424
13.2. Обучение параметров модели ................................................................ 425
13.2.1. Байесовское обучение .................................................................... 426
13.2.2. Обучение методом максимального правдоподобия и МАВ.............. 430
13.3. Дальше вместе с Figaro ........................................................................... 439
13.4. Резюме ................................................................................................... 440
13.5. Упражнения ............................................................................................ 440
Приложение.А..Получение.и.установка.Scala.и.Figaro................... 443
A.1. Использование sbt .................................................................................... 443
A.2. Установка и запуск Figaro без sbt .............................................................. 444
A.3. Сборка из исходного кода ........................................................................ 445
Приложение.B..Краткий.обзор.систем.вероятностного.
программирования................................................................ 447
Предметный.указатель........................................................... 450
Стр.13