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

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....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

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