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

Ави Пфеффер

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

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