Что такое машинное обучение

Банк решает, кому выдать кредит, магазин — сколько товара заказать, поисковик — какие десять страниц показать первыми. Ни одно из этих решений не следует из формулы, выведенной из первых принципов, но у каждого есть история: кредиты, которые вернули или не вернули, прошлые продажи, прошлые клики. Машинное обучение (machine learning) превращает такую историю в правило, которое предсказывает исход для нового случая. За пределами текстов и изображений бо́льшая часть этой работы ведётся на таблицах (цены, кредиты, отток, спрос, поисковое ранжирование), и основные рабочие инструменты — линейные модели, решающие деревья и градиентный бустинг; нейронные сети собраны из тех же частей: линейных отображений, функций потерь, градиентного спуска и регуляризации. На табличных данных среднего размера ансамбли деревьев по-прежнему обыгрывают глубокие сети (Grinsztajn, Oyallon and Varoquaux, 2022). Подогнать правило под историю — лёгкая часть. Трудная часть — обобщение (generalization): правило, безупречное на примерах, может оказаться бесполезным на следующем случае, а небрежная проверка может выдать бесполезное правило за безупречное. Эта заметка ставит задачу на языке курса теории вероятностей, показывает, почему ошибка на обучающих примерах оптимистична, и описывает план курса.

Обозначения. Объект (клиент, квартира, пара «запрос–документ») описывается вектором признаков $x \in \mathcal X$, обычно из $\mathbb R^d$; его целевая переменная (target) — $y \in \mathcal Y$. Пары порождаются неизвестным распределением $P$ на $\mathcal X \times \mathcal Y$, и обучающая выборка $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ содержит $n$ независимых наблюдений из него. Модель — функция $f$ из $\mathcal X$ в множество прогнозов, выбранная из семейства $\mathcal F$; обученная модель — $\hat f$. Функция потерь $L(y, \hat y) \ge 0$ — цена прогноза $\hat y$, когда верный ответ равен $y$.

От примеров к правилу#

Обучающая выборка — это таблица: одна строка на объект, один столбец на признак плюс столбец целевой переменной. Чтобы предсказывать цену квартиры, признаками могут быть площадь, район, этаж и год постройки, а целевой переменной — цена. Метод обучения с учителем (supervised learning) берёт таблицу и возвращает функцию $\hat f$, которая по признакам квартиры, не входившей в таблицу, выдаёт цену.

«Хорошо» нужно выразить числом. Функция потерь говорит, насколько плох один прогноз, например квадратичная ошибка $L(y, \hat y) = (y - \hat y)^2$, а эмпирический риск (empirical risk) модели — её средняя потеря на обучающей выборке:

$$\hat R_n(f) = \frac1n \sum_{i=1}^n L\big(y_i, f(x_i)\big) .$$

Большинство процедур обучения, от метода наименьших квадратов до градиентного бустинга, минимизируют его по семейству моделей: $\hat f = \arg\min_{f \in \mathcal F} \hat R_n(f)$ — это минимизация эмпирического риска (empirical risk minimization). Но важна нам потеря на следующем объекте — риск (risk)

$$R(f) = E_{(X, Y) \sim P}\, L\big(Y, f(X)\big) ,$$

математическое ожидание потери по распределению, которое порождает данные. Эмпирический риск — выборочное среднее потерь, и для модели, зафиксированной до того, как мы увидели данные, он является несмещённой оценкой риска. Если у потери конечное среднее по $P$, оценка сходится к риску по закону больших чисел. Если у потери ещё и конечная дисперсия $\sigma_L^2$, стандартная ошибка равна $\sigma_L/\sqrt n$, то есть имеет порядок $1/\sqrt n$, и центральная предельная теорема превращает её в погрешность; ограниченная потеря удовлетворяет обоим условиям, и тогда неравенство Хёфдинга даёт оценку при любом $n$.

Обученная модель не зафиксирована до того, как мы увидели данные: её выбрали именно потому, что она под них подходит. Разобранный пример. Простейшая модель игнорирует признаки и предсказывает одно число $c$. Четыре квартиры стоят 3, 5, 4 и 8 (миллионов). Квадратичную потерю минимизирует среднее, $c = \bar y = 5$, и его эмпирический риск равен $\frac14(4 + 0 + 1 + 9) = 3.5$. Равен ли 3.5 риск прогноза 5? Пусть цены имеют среднее $\mu$ и дисперсию $\sigma^2$. На новой квартире риск константы $\bar y$ равен $E(Y - \bar y)^2 = \sigma^2 + (\bar y - \mu)^2$, и его среднее по обучающим выборкам равно $\sigma^2 + \sigma^2/n$. Эмпирический риск равен $\frac1n \sum_i (y_i - \bar y)^2$, его среднее — $\frac{n-1}{n}\sigma^2$, смещённая оценка дисперсии из заметки об оценках. При $n = 4$:

$$E\,\hat R_n(\bar y) = 0.75\,\sigma^2, \qquad E\,R(\bar y) = 1.25\,\sigma^2 .$$

Уже модель с одним параметром выглядит на своих обучающих данных лучше, чем она есть, потому что параметр выбран под эти данные: разрыв равен $2\sigma^2/n$. У моделей с тысячами параметров разрыв может сравняться с самим риском.

Наилучший возможный прогноз#

Какую функцию мы выбрали бы, если бы знали $P$? Для квадратичной потери ответ — условное среднее $m(x) = E[Y \mid X = x]$, наилучший прогноз: для любой $f$ выполнено $R(f) = R(m) + E\,(m(X) - f(X))^2$. Его собственный риск, $R(m) = E\operatorname{Var}(Y \mid X)$, — это шум, который признаки не объясняют, неустранимая ошибка (irreducible error). Другие функции потерь выделяют другие характеристики условного распределения (другие потери — другие цели):

Функция потерь	$L(y, \hat y)$	Наилучший прогноз в точке $x$	Прочтение через правдоподобие (необязательное)
Квадратичная	$(y - \hat y)^2$	среднее $Y \mid X = x$	гауссовская
Абсолютная	$\lvert y - \hat y \rvert$	медиана $Y \mid X = x$	Лапласа
0–1	$[y \ne \hat y]$	самый вероятный класс
Кросс-энтропия	$-\log q(y \mid x)$	$q(\cdot \mid x) = P(Y = \cdot \mid X = x)$	категориальная

Третий столбец не требует никаких предположений о шуме. Условное среднее минимизирует ожидаемую квадратичную потерю для любого распределения с $E\,Y^2 < \infty$, гауссовского или нет, а условная медиана минимизирует ожидаемую абсолютную потерю, если $E\lvert Y \rvert < \infty$. Функция потерь решает, какую характеристику $Y \mid X = x$ мы оцениваем. Последний столбец — необязательное прочтение из заметки о методе максимального правдоподобия: с точностью до констант квадратичная, абсолютная потеря и кросс-энтропия — отрицательные логарифмы правдоподобия этих моделей шума, поэтому их минимизация — это метод максимального правдоподобия, если модель верна. Например, при экспоненциальном шуме метод наименьших квадратов по-прежнему оценивает условное среднее, но уже не совпадает с оценкой максимального правдоподобия. Не у каждой полезной функции потерь есть такое прочтение: у потери 0–1 его нет, а кусочно-линейная потеря (hinge loss) метода опорных векторов не является нормированным условным правдоподобием. Для классификации с потерей 0–1 наилучшее правило предсказывает самый вероятный класс; это байесовский классификатор (Bayes classifier), а его риск $R^* = E\big[1 - \max_k P(Y = k \mid X)\big]$ — байесовская ошибка (Bayes error).

Обученная модель уступает наилучшей по двум причинам. Обозначив в общем случае через $R^*$ наименьший возможный риск при выбранной функции потерь ($R(m)$ для квадратичной потери, байесовская ошибка для потери 0–1), а через $f^*_{\mathcal F}$ — лучшего представителя семейства, получаем

$$R(\hat f) - R^* = \underbrace{R(\hat f) - R(f^*_{\mathcal F})}_{\text{ошибка оценивания}} + \underbrace{R(f^*_{\mathcal F}) - R^*}_{\text{ошибка аппроксимации}} .$$

Слишком простое семейство не может приблизить $m$; слишком богатое для $n$ примеров семейство нельзя хорошо оценить по ним. Каждый метод этого курса выбирает точку на этом компромиссе, а заметка о смещении и разбросе делает его точным для квадратичной потери.

Типы задач#

Задача	Целевая переменная	Примеры	Типичная функция потерь или метрика
Регрессия	число	цена, спрос, время доставки	квадратичная или абсолютная ошибка
Бинарная классификация	один из двух классов	дефолт, отток, мошенничество	кросс-энтропия; точность (precision), полнота (recall), ROC-AUC
Многоклассовая, многометочная	один из $K$ классов или набор меток	тема статьи, теги	softmax-кросс-энтропия
Ранжирование	порядок объектов для запроса	поисковая выдача, рекомендации	попарные и списочные функции потерь, NDCG
Кластеризация	нет	сегменты клиентов	расстояние внутри кластера

Первые четыре задачи — задачи обучения с учителем: обучающая выборка содержит значения целевой переменной. Ранжирование отличается тем, что потеря зависит сразу от нескольких объектов: список хорош, если релевантные документы идут первыми, каковы бы ни были оценки. В задачах обучения без учителя (unsupervised learning) целевой переменной нет вовсе; кроме кластеризации, к ним относятся оценка плотности, поиск аномалий и понижение размерности — темы раздела об обучении без учителя.

Подогнать легко, обобщить трудно#

Самое гибкое семейство содержит все функции, и в нём идеальная подгонка под обучающую выборку существует всегда: запоминающая модель (memorizer) возвращает $y_i$ на вопрос об $x_i$ и некоторое значение по умолчанию на всё остальное. Её эмпирический риск равен нулю. При непрерывных признаках новый объект почти никогда не совпадает с обучающим, поэтому запоминающая модель отвечает на любой новый вопрос значением по умолчанию: она ничему не научилась. Богатое семейство переобучается (overfits) менее крайним образом, и рисунок показывает как. Многочлены растущей степени подгоняются методом наименьших квадратов к 12 точкам синусоиды с шумом дисперсии $0.09$ (та же постановка, что в примере со смещением и разбросом); обе кривые — точные математические ожидания по шуму:

Рисунок

Ошибка на обучении падает, ошибка на новых данных — нет

Ошибка на обучении падает с каждым добавленным коэффициентом: 0.541 для константы, 0.067 при степени 3, 0.015 при степени 9 и ровно 0 при степени 11, когда многочлен проходит через все 12 точек. Ошибка на новых данных падает, лишь пока модель слишком проста для синусоиды: она минимальна при степени 3 (0.121), а затем растёт до 0.208 при степени 9, 0.421 при степени 10 и 3.16 при степени 11. Начиная со степени 5 многочлен может почти точно повторить синусоиду, и ожидаемая ошибка на обучении равна $\sigma^2 (n - p)/n$ для $p = \text{степень} + 1$ коэффициентов: каждый коэффициент поглощает одно направление шума, $0.09/12 = 0.0075$ ошибки на обучении на коэффициент. Этот поглощённый шум и есть то, в чём модель ошибается на новых данных.

Теория вероятностей говорит, сколько данных нужно для проверки. Для одной модели, зафиксированной заранее, неравенство Хёфдинга ограничивает отклонение её потери на валидации от риска; для лучшей из $K$ кандидатов, выбранной на той же валидационной выборке, оценка платит $\ln K$ за выбор (первая оценка обобщающей способности). Заметка о валидации превращает это в практику: обучающая, валидационная и тестовая выборки, кросс-валидация и погрешность результата.

Курс как мост#

Дополнительный материал: на какие разделы теории вероятностей опирается каждый метод и где его используют курсы NLP и генеративных моделей. Остальная часть заметки на него не опирается.

Этот курс стоит между курсом теории вероятностей и двумя курсами, которые на нём строятся, — NLP и генеративными моделями. Каждый метод вводится вместе с теорией вероятностей, на которой он стоит, и в каждой заметке сказано, где его используют следующие курсы. Основные линии:

Инструмент теории вероятностей	Чем он становится здесь	Где его используют NLP и генеративные модели
Математическое ожидание	риск как ожидаемая потеря; градиент по мини-батчу как оценка ожидаемого градиента (градиентный спуск)	любая целевая функция обучения — эмпирический риск
Концентрация, ЗБЧ, ЦПТ, бутстрэп	обобщение, валидация и её погрешность, смещение отбора, метрики	оценка качества и утечки в NLP
Условное математическое ожидание	цель метода наименьших квадратов и ближайших соседей; разложение на смещение и разброс
Метод максимального правдоподобия	квадратичная ошибка, прочитанная как гауссовское правдоподобие; кросс-энтропия в логистической регрессии и softmax; EM-алгоритм	классификаторы текстов, языковые модели, кросс-энтропия и KL
Байесовский вывод	гребневая регрессия и лассо как априорные распределения (регуляризация); сглаженное целевое кодирование	затухание весов при дообучении
Многомерное нормальное распределение	PCA, смеси гауссиан, геометрия ближайших соседей в большой размерности	автоэнкодеры и VAE, семантический поиск

Две линии начинаются в самом этом курсе: обратное распространение ошибки, которым обучаются рекуррентные сети и трансформеры курса NLP и все сети курса генеративных моделей, и обучение ранжированию, которое оценивает фрагменты в семантическом поиске и генерации с извлечением.

Рисунок

Курс как мост: от вероятности к NLP и генеративным моделям

Карта курса#

Каждый шаг либо отвечает на ограничение предыдущего, либо, в последних строках, меняет задачу:

Провал	Ответ
Запоминание обучающей выборки не обобщается	риск и валидация: эта заметка, данные, признаки и утечки, валидация
Похожие входы должны получать похожие ответы, но сходство во многих измерениях почти бессмысленно	метод ближайших соседей и проклятие размерности
У голосования соседей нет глобальной структуры	метод наименьших квадратов
Замкнутая формула слишком дорога или не существует	градиентный спуск, стохастические и адаптивные оптимизаторы
При большом числе признаков подгонка гонится за шумом	регуляризация
Метод наименьших квадратов на метках классов позволяет лёгким точкам сдвигать границу	линейные классификаторы и суррогатные функции потерь
Нужны вероятности, а не только сторона прямой	логистическая регрессия
Доля правильных ответов скрывает важные ошибки	метрики классификации
Лучшая разделяющая прямая не единственна, а прямые слишком просты	метод опорных векторов, ядра
Больше двух классов или несколько меток сразу	многоклассовая и многометочная классификация
Прямая не может выразить взаимодействия признаков	решающие деревья
Почему гибкие модели переобучаются?	разложение на смещение и разброс
Одно дерево неустойчиво	бэггинг и случайный лес
Усреднение не исправляет смещение	градиентный бустинг
Признаки приходится конструировать вручную	нейронные сети, обратное распространение ошибки, обучение глубоких сетей
Меток нет вовсе	кластеризация, смеси распределений и EM, понижение размерности, поиск аномалий
Ответ — порядок, а не метка	обучение ранжированию, рекомендательные системы

Заметки сгруппированы в семь разделов: постановка задачи обучения (эта заметка и три следующие), линейная регрессия, линейная классификация, деревья и ансамбли, нейронные сети, обучение без учителя и задачи за пределами классификации. После курса читатель должен уметь превратить бизнес-вопрос в задачу обучения с учителем с целевой переменной, признаками и метрикой; построить схему валидации, которая соответствует применению модели и ловит утечки; обучать и отлаживать линейные модели, деревья и бустинг и выводить их градиенты; выбирать между бустингом и нейронной сетью для конкретного набора данных; читать код обучения на scikit-learn или PyTorch, понимая, что делает каждая строка.

Что изменилось#

	Программа, написанная вручную	Модель, выученная по примерам
Правило	пишет человек, понимающий процесс	выбирается из семейства $\mathcal F$ минимизацией $\hat R_n$
Что нужно	знание механизма	примеры из распределения будущих случаев
Что значит «правильно»	проходит заданные случаи	малый риск $R(f)$ на новых случаях
Как проверяется	тесты по спецификации	потеря на отложенных данных с погрешностью
Типичный сбой	ошибка в коде	переобучение, утечка, изменение распределения

Ограничения#

• Новые данные должны быть похожи на старые. Все гарантии касаются пар из того же распределения $P$. Новый рынок, кризис или политика, которая реагирует на собственные прогнозы модели, меняют $P$, и риск, измеренный на валидации, больше не действует.
• Функция потерь — это выбор. Модель минимизирует ту функцию потерь, которую ей дали; в задаче с 1% мошенничества правило «никогда не предсказывать мошенничество» уже даёт долю правильных ответов (accuracy) 99%, так что по этой метрике бесполезная модель может оказаться выше полезной.
• Прогноз — не причинность. Модель $P(Y \mid X)$ говорит, каким обычно бывает $Y$, когда наблюдается $X$, а не каким $Y$ станет, если $X$ изменить: модель оттока ранжирует клиентов, которые, скорее всего, уйдут, но не говорит, какое предложение их удержит.
• Метки стоят денег. Обучению с учителем нужна целевая переменная для каждого обучающего примера, и сбор её значений часто оказывается самой дорогой частью проекта.

Что нужно запомнить#

• Задача обучения с учителем — это таблица признаков $x$ и целевых значений $y$, семейство моделей и функция потерь; обучение минимизирует эмпирический риск $\hat R_n(f) = \frac1n\sum_i L(y_i, f(x_i))$.
• Важен риск $R(f) = E\,L(Y, f(X))$ на новых данных; для модели, зафиксированной заранее, и потери с конечной дисперсией $\hat R_n$ оценивает его с ошибкой порядка $1/\sqrt n$.
• Ошибка обученной модели на обучающей выборке оптимистична: уже для подогнанной константы $E\hat R_n = \frac{n-1}{n}\sigma^2$ против риска $\frac{n+1}{n}\sigma^2$.
• Наилучший возможный прогноз — $E[Y \mid X]$ для квадратичной потери и самый вероятный класс для потери 0–1; их риск — неустранимая ошибка и байесовская ошибка.
• Функция потерь определяет наилучший прогноз при любом шуме: среднее для квадратичной ошибки, медиану для абсолютной, самый вероятный класс для потери 0–1. Некоторые распространённые потери можно прочитать и как отрицательные логарифмы правдоподобия (квадратичная ошибка — гауссовский шум, кросс-энтропия — категориальная модель); не каждая полезная потеря такова.
• Чем богаче семейство, тем ниже ошибка на обучении; ошибка на новых данных сначала падает, потом растёт. Измерить её можно только на отложенных данных.

Код#

Оптимизм подогнанной константы в симуляции и ошибки многочленов с рисунка — точно и в симуляции:

import numpy as np
from numpy.polynomial import legendre as L

rng = np.random.default_rng(0)

# a constant prediction fitted to n = 4 values: its training error against its risk on new data (sigma^2 = 1)
n, sims = 4, 200_000
y = rng.normal(size=(sims, n))
c = y.mean(axis=1)                                          # the fitted constant, y-bar
train = ((y - c[:, None]) ** 2).mean(axis=1)                # empirical risk of y-bar on its own sample
risk = 1 + c ** 2                                           # E(Y - c)^2 for a new Y ~ N(0, 1)
print(round(float(train.mean()), 3), round(float(risk.mean()), 3))   # 0.751 1.25: (n-1)/n and (n+1)/n
print(np.mean([3, 5, 4, 8]), np.mean((np.array([3, 5, 4, 8]) - 5) ** 2))  # 5.0 3.5: the toy example

# polynomials fitted to 12 equally spaced points of sin(2 pi x) + N(0, 0.3^2): exact expected errors
m, s2, n = (lambda x: np.sin(2 * np.pi * x)), 0.09, 12
x = np.linspace(0, 1, n)
gx, gw = L.leggauss(200); gx, gw = (gx + 1) / 2, gw / 2      # quadrature on [0, 1] for a new X ~ U(0, 1)
def expected_errors(deg):
    Phi = L.legvander(2 * x - 1, deg)
    A = np.linalg.pinv(Phi)                                 # y -> coefficients
    G = L.legvander(2 * gx - 1, deg) @ A                    # y -> predictions on the quadrature grid
    train = (((m(x) - Phi @ A @ m(x)) ** 2).sum() + s2 * (n - deg - 1)) / n
    test = s2 + gw @ (G @ m(x) - m(gx)) ** 2 + s2 * gw @ (G ** 2).sum(axis=1)
    return train, test
for deg in (0, 1, 3, 5, 9, 10, 11):
    print(deg, *np.round(expected_errors(deg), 3))
# 0 0.541 0.598 | 1 0.329 0.318 | 3 0.067 0.121 | 5 0.045 0.128 | 9 0.015 0.208 | 10 0.008 0.421 | 11 0.0 3.158

# the same numbers by simulation for degree 3: 20,000 training sets, each scored on 1,000 fresh points
P = L.legvander(2 * x - 1, 3)
Y = m(x) + 0.3 * rng.normal(size=(20_000, n))
coef = np.linalg.lstsq(P, Y.T, rcond=None)[0]
xt = rng.random(1000)
Yt = m(xt) + 0.3 * rng.normal(size=(20_000, 1000))
print(round(float(((Y - (P @ coef).T) ** 2).mean()), 3), round(float(((Yt - (L.legvander(2 * xt - 1, 3) @ coef).T) ** 2).mean()), 3))
# 0.067 0.122

Дальше#

Постановка предполагала, что каждый объект приходит в виде вектора чисел и что обучающие строки — независимые наблюдения из того распределения, с которым модель встретится. Настоящие данные приходят таблицами с категориями, пропусками, датами и свободным текстом, а проще всего нарушить второе предположение, позволив информации о целевой переменной просочиться в признаки. Следующая заметка превращает сырые столбцы в признаки и показывает, как утечка выдаёт бесполезную модель за отличную.

Литература#

• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 1: введение.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Глава 2 (статистическая теория решений, раздел 2.4), раздел 7.2 (сложность модели и ошибка на тесте), раздел 7.4 (оптимизм ошибки на обучении).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Глава 2 (минимизация эмпирического риска и переобучение), глава 5 (компромисс между смещением и сложностью).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Раздел 1.1 (подгонка полиномиальной кривой).
• L. Grinsztajn, E. Oyallon, G. Varoquaux. Why do tree-based models still outperform deep learning on tabular data? NeurIPS Datasets and Benchmarks Track, 2022.