Переобучение и двойной спуск

Школьная U-кривая обещает: слишком простая модель недоучивается, слишком сложная запоминает шум, где-то посередине — золотая середина. Обещание верное, но неполное. Если продолжить ось сложности за точку, где модель впервые проходит ровно через все обучающие ответы, ошибка на тесте иногда снова падает — и падает ниже прежнего минимума. Разберёмся, откуда берётся пик, почему за ним бывает второй спуск и чего из этого категорически не следует.

Три слагаемых на реальных данных

Возьмём велопрокат из урока 49: два года почасовых записей. Будем считать истинной функцией $f(h)$ среднее число поездок в час $h$ за все 730 дней — по каждому часу набралось столько наблюдений, что среднее устойчиво. Обучающей выборкой назовём один случайно выбранный реальный день: 24 точки, по одной на час. Задача — восстановить $f$ полиномом степени $d$.

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

$$\operatorname{bias}^2(h)=\bigl(\mathbb E[\widehat f(h)]-f(h)\bigr)^2,$$ $$\operatorname{variance}(h)=\mathbb E\bigl[(\widehat f(h)-\mathbb E[\widehat f(h)])^2\bigr],$$ $$\mathbb E\bigl[(Y-\widehat f(h))^2\bigr] =\operatorname{bias}^2(h)+\operatorname{variance}(h)+\sigma^2(h).$$

Первые два слагаемых — про модель, третье — про мир. Вывод короткий: если $Y=f(h)+\varepsilon$ с $\mathbb E\varepsilon=0$, то

$$\mathbb E\bigl[(Y-\widehat f)^2\bigr] =\mathbb E\bigl[(f-\widehat f)^2\bigr]+\mathbb E[\varepsilon^2],$$

а первое слагаемое, в свою очередь, распадается прибавлением и вычитанием среднего прогноза $\bar f=\mathbb E[\widehat f]$:

$$\mathbb E\bigl[(f-\widehat f)^2\bigr] =(f-\bar f)^2+\mathbb E\bigl[(\widehat f-\bar f)^2\bigr].$$

Здесь $\sigma^2$ — разброс реальных дней вокруг своего часового среднего; это не выдумка, а измеренная величина: в среднем по часам $\sigma^2\approx16\,310$ поездок$^2$, то есть типичное отклонение около 128 поездок. Никакая модель этого не уберёт.

Что происходит с двумя другими слагаемыми, видно на рисунке. Смещение падает с $16\,565$ (степень 0, то есть одна горизонтальная прямая) до $1\,465$ при степени 12. Разброс растёт в обратную сторону: с $702$ до $6\,901$. Их сумма — единственная часть ошибки, которой мы управляем, — минимальна при степени 7 и равна $6\,381$.

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

Что значит «пройти через все точки»

Полином степени $n-1$ проходит через любые $n$ точек с различными абсциссами: система на коэффициенты — это система Вандермонда, у неё единственное решение. Определитель этой системы не равен нулю при попарно различных узлах:

$$\det V=\prod_{i<k}(x_k-x_i)\ne0 .$$

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

$$\dim\{w:\;Zw=y\}=p-\operatorname{rank}Z .$$

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

Пик: эксперимент на реальных цифрах

Теперь честный опыт. Берём набор рукописных цифр digits (8×8 пикселей), $n=100$ обучающих объектов, у 20% из них метка заменена на случайную — имитация неаккуратной разметки. Модель: $p$ случайных признаков $z_j(x)=\max(0,\,w_j^\top x+b_j)$ с фиксированными случайными $w_j,b_j$, поверх них — обычный метод наименьших квадратов по one-hot ответам. Меняем только $p$, всё остальное держим постоянным; каждая точка усреднена по восьми независимым розыгрышам — выборки и случайных признаков сразу.

$$\widehat W=\arg\min_{W}\;\|ZW-Y\|_F^2, \qquad Z\in\mathbb R^{n\times p}.$$

При $p\le n$ это обычные нормальные уравнения, при $p>n$ — интерполяция с выбором среди множества решений:

$$Z^\top Z\widehat w=Z^\top y \quad(p\le n), \qquad \widehat w=Z^\top(ZZ^\top)^{-1}y \quad(p>n).$$

Результат: при $p=30$ ошибка на тесте $37{,}5\%$ — это классический минимум. Дальше она растёт и при $p=n=100$ достигает $88{,}4\%$, то есть модель угадывает хуже, чем при $p=10$. Затем — второй спуск: $32{,}6\%$ при $p=300$ и $26{,}7\%$ при $p=2000$. Ошибка на обучении при этом обращается в нуль начиная с $p=85$ и больше нуля не покидает.

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

Спектр объясняет катастрофу

Запишем сингулярное разложение из урока 38: $Z=U\Sigma V^\top$. Решение наименьших квадратов раскладывается по правым сингулярным векторам:

$$\widehat w=\sum_{j}\frac{u_j^\top y}{\sigma_j}\,v_j.$$

Если ответ $y$ содержит шумовую составляющую, её проекция на $u_j$ делится на $\sigma_j$. Малое сингулярное число работает как усилитель шума. Норма решения и ошибка по шуму записываются одной и той же суммой:

$$\|\widehat w\|^2=\sum_j\frac{(u_j^\top y)^2}{\sigma_j^2}, \qquad \mathbb E\|\widehat w-w^\ast\|^2=\sigma_\varepsilon^2\sum_j\frac{1}{\sigma_j^2}.$$

Одно почти нулевое $\sigma_j$ портит обе суммы независимо от того, сколько хороших направлений рядом.

Измерения на нашем опыте: наименьшее сингулярное число матрицы признаков равно $0{,}270$ при $p=30$, падает до $0{,}0027$ при $p=100$ — в сто раз! — и возвращается к $1{,}106$ при $p=2000$. Число обусловленности $\varkappa=\sigma_{\max}/\sigma_{\min}$ в точке порога равно $8\,337$ против $66$ в переопределённом режиме. Норма решения ведёт себя так же: $8{,}06$ при $p=30$, $358{,}7$ при $p=100$ и $2{,}55$ при $p=2000$ — в $141$ раз меньше пика.

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

Фаддеевы: обусловленность старше нейросетей

За тридцать лет до первых разговоров о переобучении сетей ленинградские математики Дмитрий Константинович Фаддеев и Вера Николаевна Фаддеева написали книгу, с которой в СССР начиналась вычислительная линейная алгебра, — «Вычислительные методы линейной алгебры» (1960, расширенное издание 1963). Там уже сказано всё, что нужно нам сегодня: у системы бывает не только решение, но и чувствительность решения; мера этой чувствительности — число обусловленности; а нормальные уравнения $Z^\top Zw=Z^\top y$, которыми мы считаем МНК, возводят обусловленность в квадрат, потому что $\varkappa(Z^\top Z)=\varkappa(Z)^2$.

$$\frac{\|\Delta w\|}{\|w\|}\;\le\;\varkappa(Z)\,\frac{\|\Delta y\|}{\|y\|}, \qquad \varkappa(Z)=\frac{\sigma_{\max}}{\sigma_{\min}}.$$

Подставим наш опыт: при $p=100$ имеем $\varkappa\approx8\,337$, значит, относительная ошибка в метках может усилиться в тысячи раз. Ровно это и показывает пик на рис. 59.2. Тот же язык даёт и определение «правильного» интерполятора. Псевдообратная матрица и псевдорешение записываются через сингулярное разложение:

$$Z^{+}=V\Sigma^{+}U^\top, \qquad \Sigma^{+}_{jj}=\begin{cases}1/\sigma_j,&\sigma_j>0,\\[2pt]0,&\sigma_j=0,\end{cases}$$ $$\widehat w=Z^{+}y=\arg\min_{w\in\arg\min\|Zw-y\|}\|w\| .$$

В. Н. Фаддеева, кроме того, была одним из первых советских программистов-вычислителей: она переводила матричные методы на язык машинных программ, когда «машина» означала шкаф с лампами.

Минимальная норма — скрытое правило выбора

При $p>n$ интерполяторов бесконечно много. Какой из них получит ученик? Ответ зависит не от функции потерь (она у всех нулевая), а от алгоритма. Градиентный спуск из нулевой инициализации для квадратичной ошибки движется только в подпространстве строк матрицы $Z$ и приходит к

$$\widehat w=\arg\min_{Zw=y}\|w\|_2 .$$

Причина проста: шаг спуска всегда лежит в строках матрицы,

$$w_{t+1}-w_t=-\eta\,Z^\top r_t\in\operatorname{Row}(Z),$$

поэтому и предел лежит там же, а в аффинном множестве $\{Zw=y\}$ ровно одна точка принадлежит $\operatorname{Row}(Z)$ — она и есть минимальная по норме. Это и называют неявной регуляризацией (implicit bias): формально мы ничего не штрафовали, но траектория оптимизации выбрала конкретное решение. Тот же предел даёт ridge при $\lambda\to0$:

$$\lim_{\lambda\to0}\widehat w_\lambda =\arg\min_{Zw=y}\|w\|_2 .$$

Простейший пример. Один объект $x=(1,1)$ с ответом $y=1$ задаёт уравнение $w_1+w_2=1$. Ему удовлетворяют $(1,0)$, $(0,1)$, $(10,-9)$ — на новом объекте $(1,0)$ они предскажут $1$, $0$ и $10$. Нулевая ошибка на обучении не определила функцию. Минимальную норму находим по формуле для одного уравнения $a^\top w=b$:

$$\widehat w=\frac{b}{\|a\|^2}\,a =\frac{1}{2}(1,1)=(0{,}5;\,0{,}5), \qquad \|\widehat w\|=\frac{1}{\sqrt2}\approx0{,}707 .$$

Лаборатория двойного спуска

Сорок обучающих объектов, восьмимерный вход, ответ порождён небольшой сетью и зашумлён. Ведите ползунок $p$ слева направо и следите за двумя панелями сразу.

Сначала поставьте шум $\sigma=0$: пик станет заметно ниже — интерполировать чистый сигнал не страшно. Верните $\sigma=0{,}3$: у $p=n=40$ облако прогнозов разлетается, красные точки вылетают за рамку, норма весов вырастает на порядки. Пройдите дальше, к $p=800$: ошибка на тесте становится меньше, чем в лучшей точке слева от порога. Наконец включите ridge $\lambda=1$ — пик исчезает совсем, и кривая превращается в скучную монотонную линию. Это главный практический вывод: катастрофа у порога узкая и лечится, а «чем больше, тем лучше» — не закон природы, а следствие того, какой интерполятор выбирает алгоритм.

Ridge срезает пик

Проверим то же самое на цифрах. Добавим к задаче штраф $\lambda\|W\|_F^2$ из урока 51:

$$\widehat W_\lambda=\arg\min_W\|ZW-Y\|_F^2+\lambda\|W\|_F^2,$$ $$\widehat w_\lambda=\sum_j\frac{\sigma_j}{\sigma_j^2+\lambda}(u_j^\top y)\,v_j .$$

Множитель $\sigma_j/(\sigma_j^2+\lambda)$ вместо $1/\sigma_j$ ограничивает усиление. Проверим два предела и максимум:

$$\frac{\sigma}{\sigma^2+\lambda}\xrightarrow[\sigma\to0]{}0, \qquad \frac{\sigma}{\sigma^2+\lambda}\approx\frac1\sigma \quad\text{при }\sigma^2\gg\lambda,$$ $$\max_{\sigma>0}\frac{\sigma}{\sigma^2+\lambda}=\frac{1}{2\sqrt\lambda} \quad\text{при }\sigma=\sqrt\lambda .$$

Никакое направление не усиливается сильнее, чем в $1/(2\sqrt\lambda)$ раз, — вот и весь секрет исчезнувшего пика. Измерения: пик $88{,}4\%$ при $\lambda=0$ становится $44{,}9\%$ при $\lambda=0{,}01$ и $20{,}9\%$ при $\lambda=1$. Более того, лучшая точка регуляризованной кривой ($20{,}0\%$ при $p=130$) лучше лучшей точки всей нерегуляризованной кривой ($26{,}7\%$ при $p=2000$).

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

Двойной спуск по числу объектов

Все три оси удобно свести к одному отношению

$$\gamma=\frac{p}{n}, \qquad\text{порог: }\gamma=1 .$$

Пик живёт при $\gamma=1$, и до него можно дойти как справа (увеличивая $p$), так и слева (увеличивая $n$).

Ось сложности — не единственная. Зафиксируем $p=300$ случайных признаков и будем менять размер обучающей выборки $n$. Порог теперь пересекается с другой стороны, и получается контринтуитивная картина: при $n=80$ ошибка $34{,}6\%$, при $n=300$ (то есть ровно $n=p$) — $86{,}6\%$, при $n=900$ — $8{,}4\%$. Добавление данных временно ухудшает модель.

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

Шум меток: что именно ломается

Формально испорченная разметка — это подмена ответа с вероятностью $\rho$:

$$\tilde y_i=\begin{cases}y_i,&\text{с вероятностью }1-\rho,\\[2pt] \text{случайный класс},&\text{с вероятностью }\rho,\end{cases}$$ $$\mathbb P(\tilde y_i\ne y_i)=\rho\Bigl(1-\frac1K\Bigr) =0{,}2\cdot0{,}9=0{,}18 \quad (K=10,\ \rho=0{,}2).$$

Интерполятор обязан воспроизвести и эти $18\%$ заведомо неверных ответов.

Разложим наблюдения по уровню испорченных меток. Классический минимум деградирует ровно так, как подсказывает интуиция: $24{,}0\%$ при чистой разметке, $31{,}7\%$ при 10%, $37{,}5\%$ при 20% и $48{,}2\%$ при 40% шума. Точка после второго спуска ведёт себя так же ($8{,}7\%$, $17{,}3\%$, $26{,}7\%$ и $43{,}7\%$), но всегда остаётся лучше классического минимума: выигрыш переопределённого режима падает с $15{,}3$ пункта на чистых метках до $4{,}5$ пункта при 40% шума.

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

Двойной спуск по времени обучения

Третья ось — не размер модели и не размер выборки, а число шагов оптимизации. Обучим фиксированную модель ($p=400$, 30% испорченных меток) градиентным спуском и будем смотреть на тест по ходу дела: после 100 шагов ошибка $23{,}2\%$, к 20 000 шагов она вырастает до $40{,}8\%$ и там и остаётся, а ошибка на обучении к этому моменту равна нулю.

$$w_{t+1}=w_t-\eta\,Z^\top(Zw_t-y), \qquad \eta<\frac{2}{\sigma_{\max}^2}.$$

Координата решения вдоль $v_j$ после $t$ шагов и её «эффективный $\lambda$»:

$$c_j(t)=\frac{u_j^\top y}{\sigma_j}\Bigl[1-(1-\eta\sigma_j^2)^t\Bigr], \qquad \lambda_{\text{эфф}}\approx\frac{1}{\eta t}.$$

Это чистое запоминание шума во времени: сначала спуск ловит крупные сингулярные направления (сигнал), потом добирается до мелких (шум). Ранняя остановка из урока 61 — не хитрость, а способ выбрать точку до того, как оптимизация доберётся до опасных направлений; по действию она близка к ridge.

Как честно строить такую кривую

Кривая «качество против сложности» — научное утверждение, и её легко испортить незаметной подменой. При увеличении $p$ меняются не только параметры: другая скорость сходимости, другое число операций, иногда другой допустимый размер батча из урока 24. Если широкую модель учили дольше или с другим $\lambda$, ось графика смешивает модель и бюджет.

Минимальные требования к такому эксперименту:

• фиксировать всё, кроме одной оси, и говорить прямо, что именно фиксировано;
• показывать кривые при равных эпохах и при равных вычислениях — это разные картинки;
• для каждого размера настраивать $\lambda$ и шаг отдельно, иначе сравнение нечестно;
• повторять на нескольких выборках и нескольких розыгрышах признаков: один seed способен сдвинуть узкий пик или сгладить его;
• проходить сетку по $p$ достаточно мелко около $p\approx n$, иначе пик просто не попадёт в измерения.

Что из второго спуска не следует

Он не отменяет отложенную выборку: все приведённые числа получены именно на независимых данных, и без них ни один из выводов не был бы виден.

Он не оправдывает грязную разметку: при 40% испорченных меток даже переопределённая модель даёт $43{,}7\%$ ошибок против $8{,}7\%$ на чистых.

Он не обещает, что увеличение ширины улучшит качество: при фиксированном $\lambda=1$ ошибка от $p=130$ к $p=2000$ выросла с $20{,}0\%$ до $24{,}1\%$.

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

Что двойной спуск действительно даёт — это поправку к школьной метафоре. Число параметров и функциональная сложность — разные вещи; алгоритм выбора среди решений не менее важен, чем пространство решений; а «сложность» полезнее описывать не одним числом, а несколькими: нормой, спектром, эффективным рангом. Три величины, которые стоит писать в отчёте рядом с числом параметров:

$$\|\widehat w\|_2, \qquad \varkappa(Z)=\frac{\sigma_{\max}}{\sigma_{\min}}, \qquad r_{\text{эфф}}=\frac{\bigl(\sum_j\sigma_j^2\bigr)^2}{\sum_j\sigma_j^4}.$$

Последняя — эффективный ранг: он равен числу признаков, если спектр плоский, и близок к единице, если одно направление доминирует.

Формальные правила выбора модели ждут нас в уроке 63, а язык эмпирического риска, на котором всё это записывается, — в уроке 58.

Задачи