Вероятностное программирование на практике

Ави Пфеффер
Вероятностное 
программирование 
на практике

M A N N I N G
SHELTER ISLAND
Practical
Probabilistic
Programming
AVI PFEFFER

Москва, 2017
Вероятностное
программирование
на практике
АВИ ПФЕФФЕР

УДК     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 (англ.)                        © 2016 by Manning Publications Co. 
ISBN 978-5-97060-410-6 (рус.)                          © Оформление, перевод на русский язык, 
	
                     издание, ДМК Пресс, 2017

Памяти любимой матушки, 
Клэр Пфеффер. 
Да будет память её благословенна.

ОГЛАВЛЕНИЕ
Предисловие.......................................................................... 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

Оглавление
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

Оглавление
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

Оглавление
Глава 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

Оглавление
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