Машинное обучение: основы

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Весна искусственного интеллекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Горький урок или повод для оптимизма? . . . . . . . . . . . . . . . . . . . . . . . . 13
План книги: о чём пойдёт речь далее . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
История книги и благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Глава 1. Что такое машинное обучение
1.1 Искусственный интеллект от Адама до Франкенштейна . . . . . . . . . . . 24
1.1.1 Ранняя история . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.1.2 Механические автоматы Средних веков и Нового времени . . . . . . . . 27
1.1.3 Ранняя математическая логика . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.2 AI как наука: тест Тьюринга и три волны хайпа . . . . . . . . . . . . . . . . . 34
1.2.1 Тест Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.2.2 Дартмутский семинар и первая волна хайпа . . . . . . . . . . . . . . . . . . 39
1.2.3 Машинный перевод и первая «зима искусственного интеллекта» . . . . 42
1.2.4 Обратное распространение ошибки и вторая волна хайпа . . . . . . . . . 47
1.3 Постановки задач искусственного интеллекта. . . . . . . . . . . . . . . . . . . 50
1.3.1 Классификация задач искусственного интеллекта . . . . . . . . . . . . . . 50
1.3.2 Обучение с учителем: регрессия и классификация . . . . . . . . . . . . . . 52
1.3.3 Обучение без учителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.4 Области искусственного интеллекта: какие бывают данные. . . . . . . . . 57
1.4.1 Извлечение признаков в машинном обучении . . . . . . . . . . . . . . . . . 57
1.4.2 Оверфиттинг и разные части датасета . . . . . . . . . . . . . . . . . . . . . . 58
1.4.3 Табличные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.4.4 Обработка последовательностей . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.4.5 Обработка изображений и более сложных типов данных . . . . . . . . 62
1.5 Как машинное обучение помогает другим наукам . . . . . . . . . . . . . . . 64
1.5.1 Физика и астрономия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.5.2 Математика. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.5.3 Химия и биология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.5.4 Науки о Земле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.5.5 Социальные науки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Глава 2. Основы байесовского вывода
2.1 Основы теории вероятностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.1.1 Введение: вероятностные пространства и распределения. . . . . . . . 77
2.1.2 Случайные величины и совместные распределения . . . . . . . . . . . . . 82
2.1.3 Условные вероятности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
2.1.4 Независимость и условная независимость . . . . . . . . . . . . . . . . . . . 87
2.1.5 Моменты случайной величины: ожидание и дисперсия. . . . . . . . . . . 91
*2.1.6 Как ещё можно ввести понятие вероятности . . . . . . . . . . . . . . . . . 94
2.2 Вероятности в машинном обучении: теорема Байеса . . . . . . . . . . . . . 100
2.2.1 Теорема Байеса в машинном обучении. . . . . . . . . . . . . . . . . . . . . . 100
2.2.2 Медицинский тест с двусторонней ошибкой . . . . . . . . . . . . . . . . . . 104
2.2.3 Разные виды ошибок и метрики качества классификации . . . . . . . 106
2.2.4 Задачи байесовского вывода. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
2.3 Байес в суде и сложности вероятностной интуиции . . . . . . . . . . . . . 115
2.3.1 Вероятностная интуиция — точнее, её отсутствие . . . . . . . . . . . . 115
2.3.2 Ошибка прокурора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
2.3.3 Ошибка адвоката . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
2.3.4 Парадокс Монти Холла и когнитивные искажения . . . . . . . . . . . . . 122
2.4 Монетка и сопряжённые априорные распределения . . . . . . . . . . . . . . 126
2.4.1 Монетка с точки зрения байесовского вывода . . . . . . . . . . . . . . . . . 126
2.4.2 Бета-распределения как апостериорные для монетки . . . . . . . . . . . . 129
2.4.3 Предсказательное распределение и правило Лапласа . . . . . . . . . . . . 132
2.4.4 Сопряжённые априорные распределения . . . . . . . . . . . . . . . . . . . . 134
2.4.5 Игральные кости и распределения, добавляющие разреженность . . . . 139
*2.5 Case study: монетки, подброшенные «горячей рукой» . . . . . . . . . . . . . 149
*2.5.1 Разоблачение эффекта «горячей руки» . . . . . . . . . . . . . . . . . . . . . . 149
*2.5.2 Разоблачение разоблачения эффекта «горячей руки». . . . . . . . . . . . . 151
*2.5.3 Выводы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2.6 Кризис воспроизводимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
2.6.1 Кризис воспроизводимости в психологии и социальных науках . . . . . 157
2.6.2 Почему результаты не воспроизводятся: p-значения и p-хакинг . . . . . 162
2.6.3 Сад расходящихся тропок и парапсихология. . . . . . . . . . . . . . . . . . 167
*2.6.4 Модель Иоаннидиса. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
2.6.5 Воспроизводимость в машинном обучении . . . . . . . . . . . . . . . . . . . 173
Глава 3. Теория вероятностей и оптимизация
3.1 Важные дискретные распределения . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3.1.1 Равномерное, биномиальное и геометрическое распределения . . . . . . 177
3.1.2 Биномиальное распределение Пуассона . . . . . . . . . . . . . . . . . . . . . 181
3.1.3 Распределение Пуассона и закон редких событий . . . . . . . . . . . . . . 183
3.1.4 Отрицательное биномиальное, гипергеометрическое распределения . 186
*3.1.5 Закон Ципфа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
3.2 Важные непрерывные распределения . . . . . . . . . . . . . . . . . . . . . . . . 196
3.2.1 Непрерывное равномерное распределение . . . . . . . . . . . . . . . . . . . 196
3.2.2 Нормальное распределение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
3.2.3 Логнормальное распределение и распределение Стьюдента . . . . . . . . 204
3.2.4 Гамма-распределение и экспоненциальное распределение . . . . . . . . . 207
3.3 Немецкие танки, датская камбала и биномиальные обезьяны . . . . . . . . 213
3.3.1 Выборка без замещения и военная разведка . . . . . . . . . . . . . . . . . . 213
3.3.2 Байесовский анализ и некорректные априорные распределения . . . . . 217
3.3.3 Как правильно ловить уток . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
*3.3.4 Пример Джейнса: урна с шарами и биномиальные обезьяны . . . . . . . . 228
3.4 Энтропия, KL-дивергенция и полное незнание . . . . . . . . . . . . . . . . . . . . . 238
3.4.1 Энтропия как мера неопределённости . . . . . . . . . . . . . . . . . . . . . . 238
3.4.2 Производные понятия: перекрёстная энтропия и KL-дивергенция . . . 243
3.4.3 KL-дивергенция в машинном обучении . . . . . . . . . . . . . . . . . . . . . 246
3.4.4 Информация Фишера и принцип максимума энтропии . . . . . . . . . . 251
*3.4.5 Априорные распределения Джеффриса . . . . . . . . . . . . . . . . . . . . . . 258
3.5 Оптимизация в машинном обучении . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
3.5.1 Машинное обучение и невыпуклая оптимизация . . . . . . . . . . . . . . . 265
3.5.2 Анализ градиентного спуска: проблемы с масштабом . . . . . . . . . . . . 267
3.5.3 Стохастический градиентный спуск . . . . . . . . . . . . . . . . . . . . . . . 273
3.5.4 Свойства стохастического градиентного спуска . . . . . . . . . . . . . . . . 275
Глава 4. Линейная регрессия
4.1 История вопроса и метод наименьших квадратов . . . . . . . . . . . . . . . . 280
4.1.1 История вопроса: почему «регрессия»? . . . . . . . . . . . . . . . . . . . . . 280
4.1.2 Метод наименьших квадратов . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
4.1.3 Коэффициент детерминации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
4.1.4 Функции признаков в линейной регрессии . . . . . . . . . . . . . . . . . . . 293
4.1.5 Локальные признаки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
4.2 Оверфиттинг и регуляризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
4.2.1 Оверфиттинг в регрессии с полиномиальными признаками. . . . . . . . 304
4.2.2 Гребневая регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
4.2.3 Лассо-регрессия. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
4.2.4 Геометрия регуляризации и другие её формы . . . . . . . . . . . . . . . . . 314
4.3 Вероятностная интерпретация линейной регрессии . . . . . . . . . . . . . . . 321
4.3.1 Правдоподобие линейной регрессии и гауссовский шум . . . . . . . . . . 321
4.3.2 Все вероятностные предположения линейной регрессии . . . . . . . . . . 324
4.3.3 Интерпретация коэффициентов: корреляция и причинность . . . . . . . 329
*4.3.4 Вероятностная робастная регрессия: другие распределения шума . . . . 335
*4.3.5 Другая робастная регрессия: RANSAC и оценка Тейла — Сена . . . . . . . 338
4.4 Байесовский вывод в линейной регрессии . . . . . . . . . . . . . . . . . . . . . . . . 346
4.4.1 Априорное и апостериорное распределения . . . . . . . . . . . . . . . . . . 346
4.4.2 Пример байесовского вывода в линейной регрессии . . . . . . . . . . . . . 351
4.4.3 Предсказательное распределение . . . . . . . . . . . . . . . . . . . . . . . . . 357
*4.4.4 Оценка Джеймса — Штейна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
4.5 Case study: линейная регрессия и коронавирус . . . . . . . . . . . . . . . . . 371
4.5.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
4.5.2 Линейная регрессия на логарифмической шкале . . . . . . . . . . . . . . . 372
4.5.3 Обучаем функцию распределения гауссиана . . . . . . . . . . . . . . . . . . 375
4.5.4 Анализ результатов и выводы. . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
Глава 5. Классификация
5.1 Постановка задачи, геометрия и вероятности . . . . . . . . . . . . . . . . . . . 381
5.1.1 Геометрия классификации: разделяющие поверхности . . . . . . . . . . . 381
5.1.2 Геометрия классификации для нескольких классов . . . . . . . . . . . . . 385
5.1.3 Линейный дискриминант Фишера . . . . . . . . . . . . . . . . . . . . . . . . 389
5.1.4 Порождающие модели для классификации: LDA и QDA. . . . . . . . . . 397
5.2 Логистическая регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
5.2.1 Как из линейной функции получить вероятности . . . . . . . . . . . . . . 405
5.2.2 Максимизация правдоподобия . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
5.2.3 Другие сигмоиды и пробит-регрессия . . . . . . . . . . . . . . . . . . . . . . 413
5.3 Байесовский вывод в логистической регрессии . . . . . . . . . . . . . . . . 416
5.3.1 Лапласовская аппроксимация . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
5.3.2 Обобщённое нормальное распределение и формула Стирлинга . . . . . 418
*5.3.3 Предсказательное распределение в логистической регрессии . . . . . 421
5.4 Ирисы Фишера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
5.4.1 Набор данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
5.4.2 Предварительный анализ данных . . . . . . . . . . . . . . . . . . . . . . . . . 428
5.4.3 Сравнение классификаторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
5.5 Общие замечания о классификаторах . . . . . . . . . . . . . . . . . . . . . . . . . 435
5.5.1 Несбалансированные классы и перевзвешенная ошибка . . . . . . . . . . 435
5.5.2 Калибровка классификаторов . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
5.5.3 Как изменить классификатор в новых условиях . . . . . . . . . . . . . . . 449
*5.5.4 Проспективные и ретроспективные исследования. . . . . . . . . . . . . . . 455
5.6 Порождающие модели и наивный Байес . . . . . . . . . . . . . . . . . . . . . . . . 460
5.6.1 Порождающие и дискриминирующие модели . . . . . . . . . . . . . . . . . 460
5.6.2 Вероятностные предположения наивного Байеса . . . . . . . . . . . . . . . 463
5.6.3 Правдоподобие и сравнение с логистической регрессией. . . . . . . . . . 465
5.6.4 Пример классификации текстов . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Глава 6. Несколько важных сюжетов
6.1 Ближайшие соседи и проклятие размерности . . . . . . . . . . . . . . . . . . . 478
6.1.1 Метод ближайших соседей. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
6.1.2 В чём проблема с ближайшими соседями? Проклятие размерности . . 483
6.1.3 Эффект кожуры апельсина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
6.2 Статистическая теория принятия решений. . . . . . . . . . . . . . . . . . . . . 494
6.2.1 Функция регрессии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
6.2.2 Анализ метода ближайших соседей . . . . . . . . . . . . . . . . . . . . . . . . 496
6.2.3 Минимизация ожидаемой ошибки предсказания . . . . . . . . . . . . . . . 498
6.2.4 Разложение на смещение, дисперсию и шум . . . . . . . . . . . . . . . . . . 500
6.3 Эквивалентные ядра и ядерные методы . . . . . . . . . . . . . . . . . . . . . . . 507
6.3.1 Другой взгляд на предсказания линейной регрессии . . . . . . . . . . . . 507
6.3.2 Эквивалентное ядро в линейной регрессии . . . . . . . . . . . . . . . . . . . 509
6.3.3 Ядерные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
6.4 Case study: байесовский вывод для гауссиана . . . . . . . . . . . . . . . . . . . 514
6.4.1 Выводы для фиксированного среднего и фиксированной точности . . . 514
6.4.2 Вывод для среднего и точности одновременно. . . . . . . . . . . . . . . . . 519
6.4.3 Маргинализация апостериорного распределения . . . . . . . . . . . . . . . 523
6.4.4 Предсказательное распределение для гауссиана . . . . . . . . . . . . . . . 525
6.5 Оценки p (D): эмпирический Байес и сравнение моделей . . . . . . . . . . 528
6.5.1 Маргинальное правдоподобие и подбор гиперпараметров . . . . . . . . . 528
6.5.2 Оценка p (D) как метод сравнения моделей . . . . . . . . . . . . . . . . . . 535
6.5.3 Байесовский информационный критерий. . . . . . . . . . . . . . . . . . . . 538
*6.5.4 Информационные критерии Такеучи и Акаике . . . . . . . . . . . . . . . 540
6.6 Экспоненциальное семейство . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
6.6.1 Определение и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
6.6.2 Моменты достаточных статистик . . . . . . . . . . . . . . . . . . . . . . . . . 557
6.6.3 Максимизация правдоподобия . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
6.6.4 Сопряжённые априорные и предсказательные распределения . . . 561
6.7 Обобщённые линейные модели . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
6.7.1 Определение GLM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
6.7.2 Примеры и максимизация правдоподобия . . . . . . . . . . . . . . . . . . . 565
6.7.3 Пуассоновская регрессия. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
6.7.4 Отрицательная биномиальная регрессия . . . . . . . . . . . . . . . . . . . . 574
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580

 Машинное обучение давно уже стало синонимом искусственного интеллекта. Оно проникло во многие аспекты нашей жизни и стало одной из важнейших областей современной науки. Эта книга — путеводитель по ключевым идеям машинного обучения. Вы узнаете, как методы машинного обучения получаются из основных принципов теории вероятностей, пройдёте путь от теоремы Байеса до обобщённых линейных моделей и узнаете в лицо тех китов, на которых стоит весь современный искусственный интеллект. Множество увлекательных кейсов, практических примеров и интересных задач — от анализа ретроспективных научных исследований до эффекта "горячей руки" в баскетболе — помогут разобраться в самых сложных концепциях. Кроме того, книга может лечь в основу базовых курсов по машинному обучению.