Oracle inequalities и выбор модели

Выбор модели платит за просмотр кандидатов. Воображаемый оракул знает истинные риски и берёт лучшего бесплатно; реальная процедура видит только шумные оценки и потому переплачивает дважды: сначала слишком верит своему победителю, потом выбирает не того. Оракульное неравенство сравнивает две эти процедуры и выписывает цену поиска отдельной строкой.

Лучший из ста на контрольной

Сто моделей имеют одинаковый истинный риск в десять процентов. Каждую проверили на небольшой отложенной выборке. Оценки колеблются: восемь процентов, одиннадцать, девять. Минимум почти наверняка окажется заметно ниже десяти — хотя ни одна модель не лучше остальных ни на волос.

Проверим это не на словах. Возьмём реальные метки из коллекции SMS-спама (5572 сообщения), выберем случайные $n=200$ из них — в этой подвыборке доля спама составила 12% — и построим тысячу заведомо бесполезных классификаторов: каждый отвечает подбрасыванием монеты. Истинная точность каждого равна ровно $0{,}5$; это модельный приём с фиксированным seed, и мы честно об этом предупреждаем. Средняя точность тысячи монеток на этих метках вышла $0{,}500$ — ровно как обещано. Худшая монетка набрала $0{,}400$, а лучшая — $0{,}610$.

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

Для максимума $M$ независимых оценок есть простое приближение, которое мы будем использовать весь урок:

$$\mathbb E\max_{m\leq M}\widehat A_m\;\approx\;A+\sigma\sqrt{2\ln M}, \qquad \sigma=\sqrt{\frac{A(1-A)}{n}} .$$

При $A=0{,}5$ и $n=200$ оно даёт $0{,}576$ для десяти кандидатов, $0{,}607$ для ста и $0{,}631$ для тысячи — чуть выше измеренных $0{,}554$, $0{,}588$ и $0{,}614$, потому что приближение написано для непрерывного нормального распределения, а точность на двухстах примерах дискретна и слегка «слипается».

Формально пусть

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

Для одного заранее фиксированного $m$ оценка несмещена: $\mathbb E\widehat R_m=R_m$. Но математическое ожидание минимума не равно минимуму ожиданий, и неравенство идёт в опасную сторону:

$$\mathbb E\min_{m}\widehat R_m\;\leq\;\min_{m}\mathbb E\widehat R_m =\min_m R_m .$$

Это тот же эффект, который мы впервые встретили у эмпирического риска; теперь мы делаем его явным и, главное, измеримым.

Воображаемый оракул

Введём фигуру, которой в жизни не бывает. Оракул знает распределение $P$, видит истинные риски и выбирает

$$m^\star=\arg\min_{m\leq M}R(f_m).$$

Ему не нужна валидация, он не платит за просмотр и не ошибается. Наша процедура работает вслепую. Вопрос честного анализа звучит так: насколько дороже обходится слепота?

$$R(f_{\widehat m})\;\leq\;C\cdot\min_{m\leq M}R(f_m) +\operatorname{penalty}(M,n,\delta).$$

Такое утверждение называют оракульным неравенством. Константа $C$ показывает, насколько ослаблено сравнение (в лучших результатах $C=1$), а $\operatorname{penalty}$ — цену конечных данных и самого поиска. Хорошая процедура почти не хуже лучшего кандидата, хотя и не знает, кто он.

Ключевое слово — «сравниваемого». Оракул силён ровно настолько, насколько богат каталог. Если в списке нет ни одной приличной модели, оракульное неравенство будет выполнено безупречно и совершенно бесполезно: мы почти так же плохи, как лучший из плохих.

От концентрации к цене логарифма

Пусть потеря ограничена отрезком $[0,1]$. Неравенство Хёфдинга для одного фиксированного $m$ даёт

$$P\{|\widehat R_m-R_m|>\varepsilon\}\leq 2e^{-2n\varepsilon^2}.$$

По union bound (вероятность объединения не больше суммы вероятностей) вероятность того, что хотя бы одна из $M$ оценок отклонится сильнее, не превосходит

$$2M e^{-2n\varepsilon^2}.$$

Односторонний вариант вдвое дешевле и часто достаточен, если нас пугает только приукрашивание:

$$P\{R_m-\widehat R_m>\varepsilon\}\leq e^{-2n\varepsilon^2}.$$

Приравняв это к $\delta$ и разрешив относительно $\varepsilon$, получаем одновременную границу для всего каталога:

$$\varepsilon=\sqrt{\frac{\ln(2M/\delta)}{2n}} .$$

Здесь и появляется главная формула урока. Число кандидатов входит под логарифм, объём валидации — в знаменатель под корень. При $n=1000$ и $\delta=0{,}05$ добавка для одной модели равна $0{,}043$; для ста — $0{,}064$; для десяти тысяч — $0{,}080$. Каталог вырос в десять тысяч раз, цена — меньше чем вдвое.

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

Отсюда — простейшее оракульное неравенство. Если все оценки одновременно лежат в коридоре $\varepsilon$, то

$$R_{\widehat m}\leq\widehat R_{\widehat m}+\varepsilon \leq\widehat R_{m^\star}+\varepsilon \leq R_{m^\star}+2\varepsilon .$$

Три шага: первый — коридор для выбранного, второй — определение минимума ($\widehat m$ выиграл, значит его оценка не больше оценки $m^\star$), третий — коридор для оракульного кандидата. Константа $C$ здесь равна единице, а вся цена собрана в $2\varepsilon$.

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

$$\operatorname{opt}=R(f_{\widehat m})-\widehat R(f_{\widehat m}),\qquad \operatorname{reg}=R(f_{\widehat m})-\min_m R(f_m).$$

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

Каталог из ста двадцати: реальный перебор

Теперь без монеток. Возьмём тот же SMS-спам целиком, разделим: 3000 сообщений на обучение, 500 на валидацию, оставшиеся 2072 — честный test, к которому мы не прикоснёмся до самого конца. Переберём $M=120$ конфигураций наивного Байеса: два варианта n-грамм, три порога частоты слова, бинарные счётчики или обычные, десять значений сглаживания $\alpha$. Это ровно тот перебор, который делает любая живая команда.

Победитель показал на валидации ошибку $1{,}60\%$. На отложенном test та же модель дала $1{,}83\%$ — на $0{,}23$ процентного пункта хуже. Казалось бы, мелочь. Но у остальных 119 кандидатов средний разрыв оказался $-0{,}23$ пункта: типичная модель на test выступала даже лучше, чем на валидации. Смещение возникло не у моделей, а у победителя — потому что мы выбрали именно того, кому валидация польстила сильнее всех.

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

Полезно сопоставить масштабы. Стандартная ошибка одной оценки на валидации из 500 сообщений при уровне ошибки $1{,}6\%$ равна

$$\mathrm{se}=\sqrt{\frac{p(1-p)}{n}} =\sqrt{\frac{0{,}016\cdot0{,}984}{500}}=0{,}0056,$$

то есть $0{,}56$ пункта. Весь разброс валидационных ошибок по каталогу — $2{,}00$ пункта. То есть шум сопоставим с реальными различиями между конфигурациями: таблица результатов наполовину состоит из случайности.

Теоретическая гарантия для этого каталога равна $\varepsilon=\sqrt{\ln(240/0{,}05)/1000}=0{,}092$, то есть $9{,}2$ пункта. Наш фактический регрет — $0{,}43$ пункта, в двадцать раз меньше. Граница Хёфдинга честна, но чудовищно консервативна: она рассчитана на злейший случай, когда все 120 кандидатов независимы и максимально враждебны. В действительности сто двадцать почти одинаковых наивных Байесов ошибаются на одних и тех же сообщениях, и эффективное число независимых попыток куда меньше формального.

Немировский и язык оракульных неравенств

У этой дисциплины есть отчётливая московская линия. Аркадий Семёнович Немировский вместе с Давидом Борисовичем Юдиным в книге «Сложность задач и эффективность методов оптимизации» (1979) ввёл в обиход мысль, ставшую потом общим местом: сложность задачи следует измерять не числом параметров, а тем, сколько информации метод обязан получить, чтобы гарантировать заданную точность. Оттуда выросли и метод эллипсоидов, и зеркальный спуск, и вообще привычка формулировать результат в виде «наш алгоритм не хуже наилучшего мыслимого плюс явная добавка».

Позже, в работах 1980–2000-х годов по адаптивному непараметрическому оцениванию и агрегации оценок, Немировский с соавторами сделал именно эту конструкцию рабочим инструментом: строится процедура, которая, не зная гладкости неизвестной функции, платит за незнание лишь логарифмический множитель по сравнению с оракулом, знающим её точно. Русская школа принесла сюда фирменную интонацию, знакомую нам ещё по задачам с ограничениями: не «модель хорошая», а «вот граница, вот что в неё входит, вот чем мы за неё платим».

Структурная сложность и вложенные классы

Кандидаты не всегда образуют конечный список. Полиномы всех степеней, деревья всех разбиений, нейросети всех весов — непрерывные классы, для которых $\ln M$ бессмыслен. Вместо него берут меры способности класса подогнать произвольные метки: VC-размерность, радемахеровскую сложность, числа покрытий (см. урок 32). Идея остаётся прежней:

$$R(f)\;\lesssim\;\widehat R(f)+\operatorname{pen}(\mathcal F,n,\delta).$$

Для класса с VC-размерностью $d$ типичная граница выглядит так:

$$R(f)\leq\widehat R(f)+ \sqrt{\frac{d\bigl(\ln\frac{2n}{d}+1\bigr)+\ln\frac4\delta}{n}} .$$

Сравните её с конечным случаем: там под корнем стоял $\ln M$, здесь — $d\ln n$. Размерность класса играет роль логарифма числа кандидатов, и это не метафора: класс с VC-размерностью $d$ ведёт себя на выборке из $n$ точек примерно как каталог из $(n/d)^d$ различимых моделей.

Структурная минимизация риска (SRM) упорядочивает классы по вложению $\mathcal F_1\subset\mathcal F_2\subset\cdots$ и выбирает

$$\widehat f=\arg\min_{k}\ \min_{f\in\mathcal F_k} \left[\widehat R(f)+\operatorname{pen}(k,n)\right].$$

Богатый класс подгоняет обучающую выборку лучше, но платит больший штраф. Проверим на реальном велопрокате. Возьмём 30 случайных часовых наблюдений и будем приближать спрос полиномом степени $k=1,\ldots,12$ от часа суток. За истину примем настоящую кривую среднего спроса, посчитанную по всем 17 379 записям датасета.

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

Обратите внимание на честный итог: штраф выбрал третью степень с отклонением $0{,}58$, тогда как наилучшая возможная была восьмая с $0{,}47$. Теоретический штраф оказался консервативен — он предпочёл недобрать гибкости, чем рискнуть. Это типично: границы худшего случая защищают от катастрофы вроде $1{,}10$ при $k=11$, но не настроены на тонкую оптимизацию. Отсюда правило практика: штрафом выбирают порядок величины сложности, валидацией — точное значение.

Парадокс Фридмана: качество из чистого шума

Отбор умеет создавать иллюзию не только модели, но и признаков. Классический опыт Дэвида Фридмана (1983) воспроизведём на реальной цели — логарифме числа поездок велопроката, — приставив к ней 500 столбцов чистого гауссова шума с фиксированным seed. Никакой связи с ответом в них нет по построению; это модельный эксперимент, и мы это подчёркиваем.

Разделим 200 наблюдений пополам. На первой сотне отберём столбцы с наибольшей по модулю корреляцией с ответом. Каждая выборочная корреляция при отсутствии связи имеет стандартное отклонение около $1/\sqrt n=0{,}1$, а максимум по пятистам независимым величинам ожидаемо равен

$$\max_{j\leq P}|\widehat\rho_j|\;\approx\; \frac{\sqrt{2\ln P}}{\sqrt n} =\frac{\sqrt{2\ln 500}}{10}=0{,}35 .$$

Измеренная величина — $0{,}31$, вполне «значимая» на вид. Обучим на отобранных столбцах регрессию и посмотрим, что она стоит на свежей сотне.

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

Напомним определение коэффициента детерминации, которым мы здесь мерим:

$$R^2=1-\frac{\sum_i(y_i-\widehat y_i)^2}{\sum_i(y_i-\bar y)^2} .$$

На выборке, где считались веса, знаменатель заведомо не меньше числителя, поэтому там $R^2\geq0$ автоматически. На чужих данных такой защиты нет — и именно поэтому отрицательный $R^2$ является не парадоксом, а диагнозом.

Лаборатория выбора

Начните с режима «все одинаковы» и нулевого разброса: истинный риск у всех один, но наблюдаемый минимум опускается тем ниже, чем больше кандидатов. Это и есть оптимизм — красный столбик в правой панели. Увеличивайте валидацию: столбик тает как $1/\sqrt n$. Затем включите «один лидер» и поставьте разброс в один-два пункта: следите за долей случаев, когда процедура действительно находит настоящего лучшего. При маленьком $n$ и большом $M$ лидер тонет в удачливых посредственностях; найдите объём, при котором процедура начинает уверенно его различать. И сравните две шкалы: фактический регрет почти всегда много меньше теоретической гарантии Хёфдинга.

Кросс-валидация тоже участвует в выборе

$K$-fold CV уменьшает зависимость оценки от одного разбиения: каждое наблюдение однажды побывает в контроле, а оценки усредняются,

$$\widehat R_{\mathrm{CV}}(f)=\frac1K\sum_{k=1}^K \widehat R^{(k)}\bigl(f^{(-k)}\bigr).$$

Это честнее одиночного split, но не спасает от нашей беды: если по $\widehat R_{\mathrm{CV}}$ выбирают гиперпараметры, то минимум по кандидатам снова смещён. Средство — вложенная кросс-валидация с двумя циклами:

1. внешний fold откладывается целиком и не участвует ни в чём;
2. внутри оставшихся данных внутренний CV перебирает гиперпараметры;
3. модель с выбранным гиперпараметром переобучается и проверяется на внешнем;
4. внешние результаты усредняются.

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

Итоговая оценка процедуры — среднее по внешним folds, а её цена в вычислениях растёт произведением:

$$\widehat R_{\mathrm{nested}}=\frac1{K_{\text{вне}}}\sum_{k=1}^{K_{\text{вне}}} \widehat R^{(k)}\Bigl(\widehat f^{(-k)}_{\widehat\lambda(k)}\Bigr), \qquad N_{\text{fit}}=K_{\text{вне}}\cdot K_{\text{внутр}}\cdot|\Lambda| .$$

Обратите внимание на $\widehat\lambda(k)$: выбранный гиперпараметр свой для каждого внешнего fold. Если они сильно расходятся между folds, это само по себе сигнал — выбор неустойчив, и сообщать «мы выбрали $\lambda=0{,}01$» без оговорок нельзя.

Главное отличие в том, что оценивается. Обычный CV оценивает модель с заранее известным гиперпараметром. Вложенный CV оценивает всю процедуру целиком, вместе с её правом ошибаться при выборе.

Сад расходящихся тропок

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

Именно здесь коварство: формально мы обучили одну модель, но выбирали её из ста восьмидесяти мыслимых веток. Гарантия $\varepsilon$ должна считаться по числу рассмотренных, а не по числу записанных вариантов.

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

При классификации текстов перебирают n-граммы, размер словаря, регуляризацию, эмбеддинги и пороги. Случайное разбиение по сообщениям одного автора позволяет модели запомнить стиль, а групповое разбиение по автору может резко изменить рейтинг моделей. Такое решение определяет само будущее, для которого мы строим прогноз, — оно не «ещё один гиперпараметр». Большая модель может выиграть по среднему и проиграть по редкой группе; если после просмотра результатов выбрать метрику, где она выглядит лучше, каталог кандидатов молча удвоился. Нужен заранее зафиксированный основной риск и guardrails из урока 55: сама метрика есть функция потерь, и её замена после результата равносильна добавлению новых кандидатов задним числом.

Правило одной стандартной ошибки

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

$$\widehat R_{\min}=\min_m\widehat R_m,\qquad \mathrm{se}=\sqrt{\frac{\widehat R_{\min}(1-\widehat R_{\min})}{n}},$$

то выбирают простейшую модель из множества $\{m:\widehat R_m\leq\widehat R_{\min}+\mathrm{se}\}$. В нашем SMS-каталоге $\mathrm{se}=0{,}56$ пункта, и в коридор $[1{,}60\%;\ 2{,}16\%]$ попадают $52{,}5\%$ конфигураций — больше половины каталога. Убедительной причины предпочесть именно победителя нет, и разумно взять самую простую и быструю из этой половины.

Ещё точнее сравнение делает парный бутстрэп. Пересэмплируем валидацию с возвращением $B$ раз и считаем долю повторов, где кандидат $A$ обошёл $B$:

$$\widehat p_{A\succ B}=\frac1B\sum_{b=1}^B \mathbf 1\bigl\{\widehat R^{(b)}_A<\widehat R^{(b)}_B\bigr\}.$$

Важно, что оба кандидата оцениваются на одном и том же пересэмплированном наборе: общий шум выборки сокращается, и остаётся разница именно между моделями. Если $\widehat p_{A\succ B}$ близка к $0{,}5$, спор беспредметен.

Агрегация вместо выбора одного

Иногда выбирать вовсе не обязательно. Если кандидаты ошибаются по-разному, усреднение прогнозов уменьшает разброс: для $M$ моделей с попарной корреляцией ошибок $\rho$ и одинаковой дисперсией $\sigma^2$

$$\operatorname{Var}\Bigl(\frac1M\sum_m\widehat y_m\Bigr) =\sigma^2\left(\rho+\frac{1-\rho}{M}\right).$$

При $\rho=0$ разброс падает в $M$ раз, при $\rho=1$ не падает вовсе. Экспоненциальное взвешивание — компромисс между усреднением и выбором:

$$w_m\propto e^{-\eta n\widehat R_m},\qquad \widehat f=\sum_m w_m f_m .$$

Предельные случаи видны сразу:

$$\lim_{\eta\to0}w_m=\frac1M,\qquad \lim_{\eta\to\infty}w_m=\mathbf 1\{m=\widehat m\}.$$

При $\eta\to\infty$ вес целиком уходит победителю (жёсткий выбор), при $\eta\to0$ получается равномерное среднее. Для таких агрегирующих процедур и доказаны самые сильные оракульные неравенства: риск смеси не превосходит риска лучшего кандидата плюс $O(\ln M/n)$ — логарифм здесь стоит уже без корня, и это ощутимо дешевле.

Когда test перестаёт быть test

Публичный leaderboard позволяет отправлять решения и видеть счёт. Команда постепенно подгоняется к скрытому набору, даже не имея доступа к строкам: каждая отправка — бит информации о тестовых метках. После сотни отправок эффективный каталог кандидатов — сотня, и по нашей формуле при $n=2000$ цена подгонки составляет уже $0{,}046$, а типичный оптимизм максимума

$$\sqrt{\frac{\ln M}{2n}}=\sqrt{\frac{\ln100}{4000}}=0{,}034 .$$

Отсюда конструкция соревнований: public/private split, лимит отправок, финальная переоценка на приватной части.

В production ту же роль играет постоянный мониторинг одной метрики при непрерывно меняющейся системе. Каждое ручное изменение, принятое «потому что график пошёл вверх», — ещё один кандидат в невидимом каталоге. Спасает рандомизированный эксперимент или теневой период на свежих данных: новое подтверждение стоит дороже, чем новая переоценка старого.

Практическое неравенство

Теоретический штраф почти всегда слишком консервативен для тонкого выбора — мы видели это дважды: $9{,}2$ пункта гарантии против $0{,}43$ фактического регрета на спаме и третья степень вместо восьмой на велопрокате. Но структура рассуждения остаётся рабочей в любом отчёте:

$$\text{будущий риск}\;\lesssim\; \text{лучший наблюдаемый риск} +\text{неопределённость оценки} +\text{цена поиска}.$$

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

Оракульное неравенство учит простой дисциплине: не поклоняться лучшему числу в таблице. Оно всегда состоит из двух частей — качества и удачи, — и вторая растёт вместе с длиной вашего списка. Мы уже знаем, как измерять неопределённость оценки и как отличать переобучение от честного обучения; теперь у нас есть третья координата — цена самого поиска. В следующий раз, когда рядом с моделью появится число, задайте не один вопрос, а два: «сколько получилось?» и «из скольких выбирали?».

Задачи