Алгоритмы принятия решений

Микель Кохендерфер, Тим Уилер, Кайл Рэй

Алгоритмы принятия решений 

Algorithms  
for Decision Making

MYKEL J. KOCHENDERFER
TIM A. WHEELER
KYLE H. WRAY

The MIT Press
Cambridge, Massachusetts
London, England

Москва, 2023

Алгоритмы  
принятия решений

МИКЕЛЬ КОХЕНДЕРФЕР
ТИМ УИЛЕР
КАЙЛ РЭЙ

УДК 519.81
ББК 22.18
К75

Кохендерфер М., Уилер Т., Рэй К.
К75 
Алгоритмы принятия решений / пер. с англ. В. С. Яценкова. – М.: ДМК Пресс, 
2023. – 684 с.: ил. 

ISBN 978-5-93700-187-0

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

УДК 519.81
ББК 22.18

The rights to the Russian-language edition obtained through Alexander Korzhenevski Agency 
(Moscow).

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

ISBN 978-0-2620-4701-2 (англ.) 
 Copyright © 2022 Massachusetts 
Institute of Technology
ISBN 978-5-93700-187-0 (рус.) 
 © Перевод, оформление, издание, 
ДМК Пресс, 2023

Содержание

От издательства .........................................................................................14

Предисловие .................................................................................................15

Благодарности ............................................................................................16

1 
Введение ...............................................................................................17
1.1. Принятие решений .......................................................................................17
1.2. Области применения ....................................................................................18
1.2.1. Предотвращение столкновения самолетов .........................................19
1.2.2. Автоматизированное вождение...........................................................19
1.2.3. Скрининг рака молочной железы ........................................................19
1.2.4. Доля инвестиций и распределение портфеля .....................................20
1.2.5. Распределенное наблюдение за лесными пожарами .........................20
1.2.6. Исследование Марса .............................................................................21
1.3. Методы создания агентов .............................................................................21
1.3.1. Явное программирование ....................................................................22
1.3.2. Обучение с учителем ............................................................................22
1.3.3. Оптимизация .........................................................................................22
1.3.4. Планирование .......................................................................................22
1.3.5. Обучение с подкреплением ..................................................................23
1.4. История автоматизации принятия решений ..............................................23
1.4.1. Экономика .............................................................................................24
1.4.2. Психология ............................................................................................25
1.4.3. Нейробиология ......................................................................................25
1.4.4. Информатика ........................................................................................26
1.4.5. Инженерия .............................................................................................26
1.4.6. Математика ...........................................................................................27
1.4.7. Исследование операций ........................................................................28
1.5. Воздействие на общество .............................................................................28

1.6. Краткий обзор содержания книги ...............................................................30
1.6.1. Вероятностное рассуждение ................................................................30
1.6.2. Многостадийные задачи.......................................................................30
1.6.3. Неопределенность модели ...................................................................31
1.6.4. Неопределенность состояния ...............................................................31
1.6.5. Мультиагентные системы .....................................................................32

Часть I. Вероятностные рассуждения .........................................33

2 
 Формальное представление неопределенности ......34

2.1. Степени доверия и вероятности ..................................................................34
2.2. Распределения вероятностей .......................................................................35
2.2.1. Дискретные распределения вероятностей ..........................................35
2.2.2. Непрерывные распределения вероятностей ......................................36
2.3. Совместные распределения .........................................................................41
2.3.1. Дискретные совместные распределения.............................................41
2.3.2. Непрерывное совместное распределение ...........................................44
2.4. Условные распределения ..............................................................................47
2.4.1. Дискретные модели условных распределений ...................................48
2.4.2. Условные модели Гаусса........................................................................49
2.4.3. Линейные модели Гаусса ......................................................................49
2.4.4. Условные линейные модели Гаусса ......................................................50
2.4.5. Сигмовидные модели ...........................................................................50
2.4.6. Детерминированные переменные ......................................................51
2.5. Байесовские сети ...........................................................................................51
2.6. Условная независимость ...............................................................................54
2.7. Заключение ....................................................................................................57
2.8. Упражнения ...................................................................................................57

3 
Вероятностный вывод ................................................................62

3.1. Вывод в байесовских сетях ...........................................................................62
3.2. Вывод в наивных байесовских моделях ......................................................67
3.3. Исключение переменной суммированием-перемножением ....................70
3.4. Распространение доверия ............................................................................72
3.5. Вычислительная сложность ..........................................................................72
3.6. Прямая выборка ............................................................................................73
3.7. Выборка, взвешенная по правдоподобию ...................................................76
3.8. Выборка Гиббса .............................................................................................79
3.9. Вывод в гауссовых моделях ..........................................................................81
3.10. Заключение ..................................................................................................83
3.11. Упражнения .................................................................................................84

4 
Параметрическое обучение ....................................................90

4.1. Обучение по критерию максимального правдоподобия ...........................90

4.1.1. Оценки максимального правдоподобия для категориальных 
распределений .................................................................................................91
4.1.2. Оценки максимального правдоподобия для распределений  
Гаусса ................................................................................................................92
4.1.3. Оценки максимального правдоподобия для байесовских сетей .......93
4.2. Байесовское параметрическое обучение ....................................................96
4.2.1. Байесовское обучение для бинарных распределений ........................97
4.2.2. Байесовское обучение для категориальных распределений .............99
4.2.3. Байесовское обучение для байесовских сетей ..................................100
4.3. Непараметрическое обучение ....................................................................101
4.4. Обучение с отсутствующими данными .....................................................103
4.4.1. Подстановка данных ...........................................................................104
4.4.2. Алгоритм ожидания-максимизации .................................................107
4.5. Заключение ..................................................................................................109
4.6. Упражнения .................................................................................................110

5 
Структурное обучение ..............................................................116

5.1. Оценка байесовской сети ...........................................................................116
5.2. Поиск ориентированного графа ................................................................119
5.3. Марковские классы эквивалентности .......................................................123
5.4. Поиск частично ориентированного графа ................................................124
5.5. Заключение ..................................................................................................126
5.6. Упражнения .................................................................................................126

6 
Простые решения .........................................................................129

6.1. Ограничения рациональных предпочтений .............................................129
6.2. Функции полезности ...................................................................................131
6.3. Выявление полезности ...............................................................................132
6.4. Принцип максимальной ожидаемой полезности .....................................134
6.5. Сети принятия решений .............................................................................136
6.6. Полезность информации ............................................................................139
6.7. Иррациональность ......................................................................................141
6.8. Заключение ..................................................................................................143
6.9. Упражнения .................................................................................................143

Часть II. Задачи последовательного принятия  
решений ........................................................................................................148
7 
Методы точного решения.......................................................149

7.1. Марковские процессы принятия решений ................................................149
7.2. Оценка стратегии ........................................................................................153
7.3. Нахождение стратегии через функцию полезности .................................156
7.4. Итерация по стратегиям .............................................................................157
7.5. Итерация по критерию ...............................................................................159

7.6. Асинхронная итерация по критерию .........................................................162
7.7. Представление задачи в виде линейной программы ...............................164
7.8. Линейные системы с квадратичным вознаграждением ..........................166
7.9. Заключение ..................................................................................................170
7.10. Упражнения ................................................................................................171

8 
 Приближенное вычисление функции  
полезности ........................................................................................179

8.1. Параметрические представления ..............................................................179
8.2. Аппроксимация по ближайшему соседу ...................................................181
8.3. Ядерное сглаживание..................................................................................183
8.4. Линейная интерполяция ............................................................................185
8.5. Симплексная интерполяция ......................................................................188
8.6. Линейная регрессия ....................................................................................191
8.7. Регрессия на основе нейронной сети .........................................................195
8.8. Заключение ..................................................................................................196
8.9. Упражнения .................................................................................................196

9 
Онлайн-планирование .............................................................201

9.1. Планирование с отступающим горизонтом ..............................................201
9.2. Стратегия развертывания...........................................................................203
9.3. Прямой поиск ..............................................................................................204
9.4. Метод ветвей и границ ...............................................................................206
9.5. Разреженная выборка .................................................................................207
9.6. Поиск по дереву Монте-Карло ...................................................................209
9.7. Эвристический поиск ..................................................................................218
9.8. Эвристический поиск c разметкой ............................................................219
9.9. Планирование с открытым контуром .......................................................224
9.9.1. Прогнозирующее управление с детерминированной моделью ......226
9.9.2. Робастное прогностическое управление ...........................................228
9.9.3. Многовариантное прогностическое управление..............................229
9.10. Заключение ................................................................................................231
9.11. Упражнения ...............................................................................................231

10 Поиск стратегии ............................................................................236

10.1. Приблизительная оценка стратегии ........................................................236
10.2. Локальный поиск ......................................................................................238
10.3. Генетические алгоритмы ..........................................................................241
10.4. Метод перекрестной энтропии ................................................................242
10.5. Эволюционные стратегии ........................................................................244
10.6. Изотропные эволюционные стратегии ...................................................248
10.7. Заключение ................................................................................................250
10.8. Упражнения ...............................................................................................251

11  Нахождение градиента стратегии  ..................................255

11.1. Конечная разность ....................................................................................255
11.2. Градиент регрессии ...................................................................................258
11.3. Отношение правдоподобия ......................................................................260
11.4. Предстоящее вознаграждение .................................................................263
11.5. Вычитание базисного значения ...............................................................266
11.6. Заключение ................................................................................................270
11.7. Упражнения ................................................................................................270

12  Оптимизация методом градиентного спуска 
по стратегиям .................................................................................273

12.1. Обновление стратегии методом градиентного подъема .......................273
12.2. Ограниченное обновление градиента .....................................................275
12.3. Метод натурального градиента ................................................................277
12.4. Метод поиска в доверительной области ..................................................280
12.5. Зажатие замещенной цели .......................................................................285
12.6. Заключение ................................................................................................288
12.7. Упражнения ................................................................................................289

13 Методы «актор–критик» .........................................................292

13.1. Определение актора и критика ................................................................292
13.2. Обобщенная оценка преимуществ ..........................................................294
13.3. Градиент детерминированной стратегии ...............................................298
13.4. Метод «актор–критик» с поиском по дереву Монте-Карло ...................301
13.5. Заключение ................................................................................................303
13.6. Упражнения ...............................................................................................304

14 Проверка стратегии ....................................................................306

14.1. Оценка показателей качества стратегии .................................................306
14.2. Моделирование редких событий .............................................................312
14.3. Анализ робастности системы ...................................................................315
14.4. Анализ компромиссов ..............................................................................317
14.5. Состязательный анализ ............................................................................319
14.6. Заключение ................................................................................................322
14.7. Упражнения ................................................................................................322

Часть III. Неопределенность модели .........................................325

15  Исследование среды и использование знаний........326

15.1. Задача однорукого бандита ......................................................................326
15.2. Оценка байесовской модели ....................................................................328
15.3. Стратегии ненаправленного исследования ............................................330
15.4. Стратегии направленного исследования ................................................332

15.5. Оптимальные стратегии исследования ...................................................336
15.6. Исследование с несколькими состояниями ............................................338
15.7. Заключение ................................................................................................338
15.8. Упражнения ...............................................................................................339

16 Методы на основе моделей ...................................................343
16.1. Модели максимального правдоподобия .................................................343
16.2. Схемы обновления модели .......................................................................346
16.2.1. Полное обновление ...........................................................................346
16.2.2. Рандомизированное обновление .....................................................347
16.2.3. Приоритетный механизм обновления ............................................347
16.3. Исследование .............................................................................................349
16.4. Байесовские методы .................................................................................352
16.5. Адаптивные по Байесу марковские процессы принятия решений .......355
16.6. Апостериорная выборка ...........................................................................356
16.7. Заключение ................................................................................................358
16.8. Упражнения ...............................................................................................359

17  Свободные методы обучения с подкреплением ....362
17.1. Инкрементное вычисление среднего значения распределения ............362
17.2. Q-обучение .................................................................................................365
17.3. Алгоритм SARSA ........................................................................................367
17.4. Следы приемлемости ................................................................................369
17.5. Формирование вознаграждения ..............................................................371
17.6. Аппроксимация функции полезности действия .....................................371
17.7. Воспроизведение опыта ............................................................................375
17.8. Заключение ................................................................................................378
17.9. Упражнения ................................................................................................378

18. Имитационное обучение ........................................................383
18.1. Поведенческое копирование ....................................................................383
18.2. Агрегация наборов данных ......................................................................386
18.3. Итеративное обучение путем стохастического смешивания ................389
18.4. Обратное обучение с подкреплением с максимальной разницей ........392
18.5. Обратное обучение с подкреплением с максимальной энтропией ......396
18.6. Генеративно-состязательное имитационное обучение .........................399
18.7. Заключение ................................................................................................400
18.8. Упражнения ...............................................................................................400

Часть IV. Неопределенность состояния ...................................405

19 Убеждения .........................................................................................406
19.1. Начальные убеждения ..............................................................................406
19.2. Фильтр дискретных состояний ................................................................407