Урок 63. Oracle inequalities и выбор модели

Выбор модели платит за просмотр кандидатов. Воображаемый oracle знает истинные риски и выбирает лучшего бесплатно; реальная процедура видит шумные оценки. Oracle inequality сравнивает их и явно добавляет цену поиска.

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

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

Пусть

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

Для одного фиксированного $m$ оценка может быть несмещённой. Минимум по $M$ шумным оценкам смещён вниз. Это тот же эффект, который появился при эмпирическом риске, теперь сделаем его явным.

Коробчатые диаграммы минимального validation риска для 1, 10, 100 и 1000 одинаковых моделей вокруг линии истинного риска — Рис. 63.1. Минимум шумных оценок опускается с числом кандидатов
Истинный риск всех кандидатов равен 0,1. По оси $x$ — число просмотренных моделей, по оси $y$ — выбранный minimum validation. Медиана минимума падает, хотя качество семейства не меняется.

Воображаемый oracle

Oracle знает распределение $P$ и выбирает

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

Мы хотим, чтобы риск реальной выбранной модели был близок:

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

Такую оценку называют oracle inequality. Константа $C$ показывает, насколько сравнение ослаблено, penalty — цену конечных данных и выбора. Хорошая процедура почти не хуже лучшего кандидата, даже не зная, кто он.

От концентрации к цене log M

Для loss в $[0,1]$ неравенство Хёффдинга даёт для фиксированного $m$ :

P\{|\widehat R_m-R_m|>\varepsilon\} \leq2e^{-2n\varepsilon^2}.

По union bound вероятность, что хотя бы одна из $M$ оценок отклонится сильнее, не превосходит

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

Приравнивая к $\delta$ , получаем одновременную границу

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

Если все оценки одновременно близки, риск выбранной модели не более чем примерно на $2\varepsilon$ хуже лучшего. Цена растёт как $\sqrt{\log M/n}$ : миллион кандидатов дороже одного, но не в миллион раз.

Графики penalty по числу моделей для нескольких объемов validation в логарифмическом масштабе — Рис. 63.2. Цена поиска растёт как корень из логарифма
По оси $x$ — $M$ от 1 до миллиона, по оси $y$ — $\sqrt{\log(2M/\delta)/(2n)}$ . Кривые для $n=500,2000,10000$ растут медленно по $M$ и заметно падают с объёмом.

Структурная сложность

Кандидаты не всегда конечны. Полиномы всех коэффициентов, деревья разных разбиений и нейросети образуют непрерывные классы. Вместо $\log M$ используют меры способности подогнать произвольные метки: VC dimension, Rademacher complexity, covering numbers.

Главная идея сохраняется: эмпирический риск плюс штраф за богатство класса. Structural risk minimization выбирает

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

по вложенным классам $\mathcal F_1\subset\mathcal F_2\subset\cdots$ . Больший класс лучше подгоняет train, но платит больше.

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

Увеличивайте число одинаковых кандидатов: observed best улучшается, true best остаётся на месте. Затем увеличьте validation — разрыв сокращается. Наконец добавьте небольшое реальное различие рисков и найдите объём, при котором процедура стабильно отличает сигнал от удачного шума.

Cross-validation тоже участвует в выборе

$K$ -fold CV уменьшает зависимость оценки от одного split, но если по нему выбирают гиперпараметры, итоговый minimum остаётся адаптивным. Nested cross-validation добавляет внешний цикл:

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

Внешний цикл оценивает всю процедуру выбора, а не один заранее известный гиперпараметр.

Внешние блоки данных, внутри каждого оставшегося train показаны внутренние folds выбора, стрелка к одному внешнему test — Рис. 63.3. Вложенная cross-validation
Большой прямоугольник делится на внешние folds. Для каждого внешнего test оставшаяся часть содержит собственный внутренний цикл. Гиперпараметр не видит внешний fold; поэтому итог оценивает поиск, включая его ошибки.

Ранжирование экспериментов как семейство

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

Журнал экспериментов делает поиск видимым. Заранее фиксированный лимит, отдельный confirmation set и воспроизведение результата на новом периоде уменьшают оптимизм. Публиковать следует не только победителя, но диапазон разумных кандидатов.

Текстовые модели

При классификации текстов перебирают n-grams, размер словаря, regularization, эмбеддинги и пороги. Случайный split по сообщениям одного автора позволяет запомнить стиль; group split по автору может резко изменить рейтинг моделей. Такое разбиение определяет само будущее, а не только очередной гиперпараметр.

Большая модель может победить на среднем validation, но проиграть по редкой группе. Если после просмотра выбрать метрику, где она выглядит лучше, семейство выбора расширилось. Нужен заранее заданный primary risk и guardrails из урока 55. Сама метрика является функцией потерь, поэтому её смена после результата равносильна добавлению новых кандидатов в поиск.

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

Model averaging и stacking иногда уменьшают цену жёсткого выбора. Если кандидаты ошибаются по-разному, средний прогноз имеет меньшую variance. Экспоненциальное взвешивание использует

w_m\propto e^{-\eta n\widehat R_m}.

Но веса тоже обучаются по данным. Stacking нуждается в out-of-fold предсказаниях, иначе meta-model увидит переобученные ответы train.

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

Leaderboard позволяет отправлять много решений и видеть score. Команда постепенно подгоняется к скрытому набору, даже без прямого доступа к строкам. Public/private split, лимит отправок и финальная переоценка на свежих данных защищают соревнование.

В production аналогичную роль играет постоянный мониторинг одной метрики с ручными изменениями системы. Отложенный shadow-период или рандомизированный эксперимент даёт новое подтверждение.

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

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

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

Отчёт должен позволить оценить все три части: объём и зависимость validation, число и родство кандидатов, способ выбора и независимую проверку. Oracle inequality учит не поклоняться лучшему числу в таблице.

Цена каталога кандидатов

Для ограниченной потери Hoeffding bound и union bound дают ориентир: одновременно для $M$ заранее перечисленных моделей с вероятностью не меньше $1-\delta$

R(f_m)\leq\widehat R(f_m) +\sqrt{\frac{\log(2M/\delta)}{2n}} \quad\text{для всех }m.

При $n=1000$ и $\delta=0{,}05$ добавка для одной модели около $0{,}043$ . Для $M=100$ она вырастает примерно до $0{,}064$ , а для $10\,000$ — до $0{,}080$ . Рост логарифмический, но не нулевой: большой каталог легче производит случайного победителя.

Граница груба и не учитывает сходство кандидатов. Сто learning rates одной архитектуры связаны сильнее ста разных pipeline, поэтому эффективная цена может быть меньше. Nested cross-validation оценивает её процедурно: внутренние fold выбирают кандидата, внешний fold видит только результат выбора.

Если после внешних fold исследователь меняет каталог, оценка снова начинает участвовать в поиске. Тогда нужен новый внешний цикл или честное описание адаптивности. Oracle inequality дисциплинирует журнал экспериментов: кто входил в каталог и какое наблюдение повлияло на его расширение.

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