Эмпирический риск: учимся по выборке

Истинный риск — средняя потеря на будущих объектах. Таблица даёт лишь конечное среднее. Для заранее фиксированной модели оно честно колеблется вокруг риска; для модели, выбранной по той же таблице, возникает систематический оптимизм. Урок о том, чем именно отличается число в отчёте от того качества, которое сервис покажет завтра.

Число, которое печатают в отчёте

В конце любой работы появляется строка вида «ошибка на тесте 15,4%». Она выглядит как измерение длины стола: взяли, приложили линейку, записали. На самом деле у неё три разных источника неопределённости, и ни один не виден в самой цифре.

Первый: тестовая выборка конечна, и другая случайная выборка того же размера дала бы другое число. Второй: если модель выбиралась по тем же данным, число систематически занижено — не случайно, а всегда в одну сторону. Третий: даже безупречно измеренный риск относится к тому распределению, из которого пришли данные, а завтрашний мир может быть другим.

Мы разберём все три на одной реальной таблице. Это велопрокат Capital Bikeshare: 17 379 часовых записей за 2011–2012 годы — те же данные, на которых в уроке 49 строилась регрессия. Задачу возьмём двухклассовую: назовём час «загруженным», если число поездок выше медианы (142 поездки), и будем предсказывать этот признак по времени суток, погоде и типу дня. Потеря — индикатор ошибки, значение $0$ или $1$; это удобно, потому что такая потеря ограничена, и к ней применимы точные неравенства.

Риск и его выборочная тень

Зафиксируем правило $f$ — до того, как мы посмотрели на тестовые данные, — и потерю $\ell$. Истинный риск

$$R(f)=\mathbb E_{(X,Y)\sim P}\,\ell\bigl(f(X),Y\bigr)$$

усредняет потерю по неизвестному распределению $P$ будущих объектов. Это число существует, но недоступно: оно требует знания $P$. Доступно другое — эмпирический риск на независимой выборке $D=\{(x_i,y_i)\}_{i=1}^{n}$:

$$\widehat R_n(f)=\frac1n\sum_{i=1}^{n}\ell\bigl(f(x_i),y_i\bigr).$$

Ключевое свойство: если строки независимы и распределены как будущее, то каждое слагаемое имеет среднее $R(f)$, а значит

$$\mathbb E\,\widehat R_n(f)=R(f).$$

Оценка несмещённая. Это радует ровно до тех пор, пока не вспомнишь, что мы наблюдаем не среднее по вселенным, а одно-единственное значение.

Разброс тени считается сразу. Для потери $0/1$ слагаемые — испытания Бернулли с вероятностью успеха $R(f)$, поэтому

$$\operatorname{Var}\widehat R_n(f)=\frac{R(f)\bigl(1-R(f)\bigr)}{n},$$ $$\operatorname{se}=\sqrt{\frac{R(1-R)}{n}} .$$

Стандартная ошибка убывает как $1/\sqrt n$: чтобы вдвое сузить облако, нужно вчетверо больше строк. Это тот же закон, что управлял выборочным средним в уроке 44, и та же логика, что стоит за доверительными интервалами урока 46.

Насколько дрожит оценка

Проверим на данных. Обучим логистическую регрессию на 4000 случайных строках и объявим её замороженной. Оставшиеся 13 379 строк будем считать «всем будущим миром»: доля ошибок на них, $R(f)=0{,}154$, играет роль истины. Теперь станем многократно вынимать из этого мира тестовые выборки размеров 50, 200 и 2000 и каждый раз считать долю ошибок.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Числа стоит прочувствовать. При $n=200$ типичное отклонение — два с половиной процентных пункта, а приближённый интервал

$$R\pm1{,}96\sqrt{\frac{R(1-R)}{n}}=[0{,}104;\;0{,}203]$$

шириной в десять пунктов. Две команды, отчитавшиеся «10,5%» и «20,0%», могли тестировать одну и ту же модель.

Гливенко: почему эмпирическому вообще можно верить

Вопрос, стоящий под всем уроком, старше машинного обучения: имеет ли право конечная таблица говорить о бесконечной генеральной совокупности? Ответ дал советский математик Валерий Иванович Гливенко (1897–1940). В 1933 году он доказал, что эмпирическая функция распределения

$$F_n(t)=\frac1n\sum_{i=1}^{n}\mathbf 1\{X_i\le t\}$$

сходится к истинной $F(t)$ равномерно по $t$ с вероятностью единица:

$$\sup_{t\in\mathbb R}\bigl|F_n(t)-F(t)\bigr|\xrightarrow[n\to\infty]{\text{п.н.}}0 .$$

Слово «равномерно» здесь несёт весь вес. Закон больших чисел даёт сходимость $F_n(t)\to F(t)$ для каждого отдельного, заранее выбранного $t$. Гливенко утверждает больше: одновременно для всех $t$ — включая тот, который мы выберем уже после того, как увидим данные. Именно поэтому теорему называют основной теоремой статистики: она разрешает подглядывать.

Заменим индикатор $\mathbf 1\{X_i\le t\}$ на потерю $\ell(f(x_i),y_i)$, а семейство порогов $t$ — на семейство моделей $f\in\mathcal F$, и получится формулировка, которой машинное обучение живёт до сих пор:

$$\sup_{f\in\mathcal F}\bigl|\widehat R_n(f)-R(f)\bigr|\to0 .$$

Из такой равномерной сходимости следует, что минимизация эмпирического риска осмысленна. Отсюда прямая линия к работам Вапника и Червоненкиса 1971 года, с которыми мы встречались в уроке 32: они выяснили, для каких классов $\mathcal F$ равномерная сходимость выполняется, и ввели меру сложности класса. Гливенко предъявил случай, когда семейство — все пороги; дальнейшая теория отвечает на вопрос «а если семейство богаче».

Хёффдинг: сколько строк стоит уверенность

Скорость $1/\sqrt n$ — про типичное отклонение. Про большое отклонение говорит неравенство Хёффдинга: для независимых потерь $0\le\ell\le1$ и фиксированной $f$

$$P\bigl\{|\widehat R_n(f)-R(f)|\ge\varepsilon\bigr\}\le 2e^{-2n\varepsilon^{2}}.$$

Оно не требует нормальности и работает при любом $n$. Приравняв правую часть к $\delta$, получаем требование к объёму:

$$n\ \ge\ \frac{\ln(2/\delta)}{2\varepsilon^{2}} .$$

Подставим $\delta=0{,}05$. Для точности $\varepsilon=0{,}02$ нужно $n\ge4612$; для $\varepsilon=0{,}01$ — уже $n\ge18\,445$. Ровно вчетверо дороже за вдвое более острый ответ: цена точности квадратична.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

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

$$n\approx\frac{z^{2}R(1-R)}{\varepsilon^{2}} :$$

при $R\approx0{,}15$, $z=1{,}96$ и $\varepsilon=0{,}02$ она даёт 1225 строк — в 3,8 раза меньше хёффдинговских 4612.

Проклятие победителя

Теперь главное. Всё сказанное относилось к функции, зафиксированной до взгляда на данные. Реальная работа устроена иначе: мы обучаем много моделей и берём ту, у которой оценка меньше.

Обучим 120 логистических регрессий на реальном велопрокате — разные случайные подмножества признаков, разная сила регуляризации, разные куски обучающей части. Их истинные риски (посчитанные на большом отложенном пуле) лежат от $0{,}153$ до $0{,}356$ с медианой $0{,}200$. Дадим каждой валидационную выборку из 200 строк и выберем минимум наблюдённой ошибки:

$$\widehat m=\arg\min_{m}\widehat R_{\mathrm{val}}(f_m).$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Механика проста. Пусть все кандидаты имеют одинаковый истинный риск $R$, а оценки $\widehat R_m=R+\xi_m$ с независимым центрированным шумом. Тогда

$$\mathbb E\Bigl[\min_{m\le K}\widehat R_m\Bigr] =R+\mathbb E\Bigl[\min_{m\le K}\xi_m\Bigr]<R,$$

потому что минимум нескольких центрированных величин отрицателен в среднем. Для гауссовского шума со стандартным отклонением $\sigma$ приближённо

$$\mathbb E\bigl[\min_{m\le K}\xi_m\bigr]\approx-\sigma\sqrt{2\ln K}.$$

Смещение растёт как $\sqrt{\ln K}$ — медленно, но неотвратимо, и падает вместе с $\sigma\propto1/\sqrt n$. Отсюда два рычага: меньше кандидатов или больше валидация.

Лаборатория: оценка как случайная величина

Начните в режиме «одна заранее фиксированная функция»: облако оценок симметрично окружает истинный риск, синяя и красная вертикали совпадают. Двигайте $n$ — облако сжимается как $1/\sqrt n$, но центр не сдвигается. Переключитесь на «минимум по $K$ кандидатам» при нулевом разбросе истинных рисков: все кандидаты одинаково хороши, поэтому выбор не приносит пользы, зато синяя вертикаль уползает влево — это чистая плата за перебор. Увеличьте разброс истинных рисков: теперь выбор частично осмыслен, но оптимизм не исчезает. Наконец, увеличьте $n$ при большом $K$: смещение уменьшится, но медленнее, чем хотелось бы, — как $\sqrt{\ln K}/\sqrt n$.

Три роли данных: train, validation, test

Отсюда следует организационная гигиена, знакомая по уроку 32, но теперь с точной причиной.

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

Validation выбирает гиперпараметры, признаки, архитектуру, порог. Его ошибка несмещённа для каждого отдельного кандидата и оптимистична для победителя.

Test оценивает замороженную процедуру ровно один раз. Он несмещён тогда и только тогда, когда ни одно решение не принималось с оглядкой на него.

Если данных мало, валидация циклическая: перекрёстная проверка меняет фолд местами и усредняет. Но внешний тест остаётся отдельным, и вложенная кросс-валидация — не роскошь: внутренний цикл выбирает, внешний оценивает.

Утечка: предобработка — часть модели

Среднее и дисперсия для стандартизации, словарь категорий, список отобранных признаков, заполнение пропусков, целевое кодирование — всё это параметры, оцениваемые по данным. Если они посчитаны до разбиения, тест уже поучаствовал в обучении, и оценка занижена.

Насколько занижена — вопрос не риторический. Возьмём модельный пример с фиксированным зерном (это синтетика, а не измерение мира): 120 объектов, 4000 совершенно случайных признаков и случайные метки, между которыми нет никакой связи. Отберём 20 признаков с наибольшей корреляцией с меткой по всей таблице, а потом честно посчитаем пятиблочную кросс-валидацию — получится ошибка $0{,}225$. Модель, «угадывающая» в трёх случаях из четырёх там, где угадать нечего. Если же отбор проводить внутри каждого фолда, ошибка становится $0{,}492$ — та самая монетка, которой данные и являются.

Независимость строк — содержательное условие

Формула $\mathbb E\widehat R=R$ опиралась на независимость строк. В таблицах это условие почти никогда не выполняется буквально. В велопрокате соседние часы делят погоду; часы одного дня — общий режим города; поездки одного пользователя похожи между собой.

Случайное перемешивание строк раскладывает почти одинаковые условия в train и test. Формально ничего не нарушено; содержательно метрика отвечает на вопрос «сумеем ли предсказать ещё один час из недели, которую мы уже видели», а не «сумеем ли предсказать следующий месяц».

Полезная поправка на зависимость: если строки собираются в кластеры размера $m$ с внутрикластерной корреляцией $\rho$, дисперсия среднего растёт примерно в

$$1+(m-1)\rho$$

раз — это так называемый design effect. При $m=24$ (часы одних суток) и скромной $\rho=0{,}2$ множитель равен $5{,}6$: эффективное число независимых наблюдений в пять с половиной раз меньше числа строк.

Единица разбиения следует из единицы обобщения

Сравним три разбиения одной и той же таблицы велопроката.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Разница между первым и вторым столбцом мала: часы внутри дня в этой задаче не так уж сильно похожи. Разница между вторым и третьим велика, и у неё есть физическая причина: сервис за год вырос. Среднее число поездок в час поднялось со $143{,}8$ до $234{,}7$ — в 1,63 раза, а доля «загруженных» часов (порог считался по всей истории) выросла с $0{,}410$ до $0{,}587$. Модель 2011 года попадает в другой мир.

Среднее прячет хвост

Риск — среднее. Среднее сжимает целое распределение потерь в одно число, и это сжатие теряет ровно то, что часто важнее всего.

Обучим обычную линейную регрессию на числе поездок (не на классе) и посмотрим на распределение абсолютных ошибок на тесте:

$$\mathrm{MAE}=\frac1n\sum_{i=1}^{n}|y_i-\widehat y_i| .$$

Средняя ошибка — $93{,}1$ поездки, медианная — $70{,}6$, но верхний дециль начинается с $190{,}8$, а один процент худших часов ошибается на $439{,}2$ поездки и больше. Две модели с одинаковым MAE могут вести себя совершенно по-разному в этом хвосте.

Поэтому рядом со средним показывают медиану, квантили, худшую группу:

$$R_{\text{worst}}(f)=\max_{g\in G}\ \mathbb E\bigl[\ell(f(X),Y)\mid G=g\bigr].$$

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

Сдвиг распределения

Равенство $\mathbb E\widehat R=R$ относится к тому $P$, из которого пришла выборка. Различают три вида расхождений:

$$\text{covariate shift: } p_{\text{new}}(x)\ne p_{\text{old}}(x),\quad p(y\mid x)\ \text{сохранилось};$$ $$\text{label shift: } p_{\text{new}}(y)\ne p_{\text{old}}(y);$$ $$\text{concept shift: } p_{\text{new}}(y\mid x)\ne p_{\text{old}}(y\mid x).$$

Наш велопрокат демонстрирует всё сразу. Модель, обученная на части 2011 года, на отложенной части того же года ошибается в $0{,}168$ случаев, а на всём 2012-м — в $0{,}189$. Разрыв $0{,}021$ — не шум измерения: тестовых строк здесь тысячи, и стандартная ошибка на порядок меньше разрыва.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Перевзвешивание пытается пересчитать среднее к нужному распределению:

$$\widehat R^{\,w}=\frac{\sum_i w(x_i)\,\ell(f(x_i),y_i)}{\sum_i w(x_i)},$$ $$w(x)=\frac{p_{\text{new}}(x)}{p_{\text{old}}(x)} .$$

Оценка становится почти несмещённой, но платит дисперсией. Эффективный размер выборки

$$n_{\text{eff}}=\frac{\bigl(\sum_i w_i\bigr)^2}{\sum_i w_i^{2}}$$

в нашем примере равен 2414 при 5384 строках. Тысячи строк исчезают, не будучи удалёнными. Надёжнее собрать свежую размеченную выборку и заново очертить карту применимости.

Offline и online риск

Есть ещё расхождение, которого не видно ни в одной таблице: после запуска модель меняет среду. Рекомендательная система влияет на то, что пользователь вообще увидит; маршрутизатор — на пробки; фильтр — на то, какие обращения дойдут до оператора. Offline-тест меряет риск в мире без модели, online — внутри контура с ней:

$$R_{\text{offline}}=\mathbb E_{P_{\text{hist}}}\ell, \qquad R_{\text{online}}=\mathbb E_{P_{f}}\ell,$$

где $P_f$ зависит от самой $f$. Это уже не статистическая, а причинная разница, и решается она экспериментом — как в уроке 55.

Промежуточный режим — теневой (shadow): новая модель получает боевой поток и строит прогнозы, но не управляет действиями. Он ловит инженерные расхождения — задержку, пропуски, дрейф признаков между offline-конвейером и сервисом — без влияния на пользователя. Он не заменяет A/B, если вопрос про реакцию людей.

Что должно стоять рядом с числом

Эмпирический риск — наблюдение, а не печать качества. Осмысленный отчёт содержит:

1. Само число и интервал вокруг него (объём теста, стандартная ошибка).
2. Определение потери и популяции: на каких объектах, за какой период.
3. Схему разбиения и единицу независимости.
4. Число просмотренных кандидатов и правило остановки.
5. Сколько раз открывали тест.
6. Метрики по группам и хвост распределения потерь, а не только среднее.
7. Дату сбора данных и признаки сдвига с тех пор.

Формальный ответ на вопрос «сколько именно стоит перебор» даёт теория oracle inequality, к которой мы придём в уроке 63. Пока достаточно рабочего правила: любая цифра качества имеет адрес — распределение, потерю и процедуру, — и без этих трёх частей строка «ошибка 15,4%» не значит почти ничего.

Задачи