Когда нажать «стоп»

Три способа не дать сети зубрить

В уроках 18 и 19 мы учились замечать переобучение: откладывать часть данных и смотреть, как модель ведёт себя на них. Это градусник. Теперь нужно лекарство.

Откуда берётся болезнь, известно с урока 12: Feed Forward Neural Network с достаточным числом скрытых нейронов приближает любую непрерывную функцию. Значит, ей по силам приблизить и шум в обучающей выборке. Когда весов много, а данных мало или они шумные, сеть не выучивает закономерность, а запоминает примеры — в конспекте это названо memorize rather than learn.

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

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

У нейросетей эти три идеи называются early stopping, weight decay и dropout. Конспект (стр. 150) даёт им родовые имена: training control, model complexity control и randomization / model averaging.

У профессора этот блок открывается титульным слайдом "Preventing Neural Networks Overfitting" (лекция 3, слайд 11), а родовое имя каждого метода стоит прямо в заголовке его слайдов. Early stopping — "Limiting Overfitting by Cross-validation" (слайд 12), weight decay — "… by Weights Regularization" (слайды 14–15), dropout — "… by Stochastic Regularization" (слайды 17–22). Эти три подзаголовка стоит помнить дословно: так методы могут быть названы в экзаменационном вопросе.

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

Early stopping ограничивает, как долго сеть учится. Weight decay — насколько большими вырастают веса. Dropout — насколько нейроны опираются друг на друга. Все три — способы применить бритву Оккама из урока 17: из моделей, объясняющих данные, предпочесть самую простую.

Термин effective capacity взят из конспекта, на слайдах его нет. Там та же мысль сказана проще: регуляризация ограничивает «freedom» модели, чтобы уменьшить overfitting (лекция 3, слайд 14).

Четвёртого лекарства в списке нет. Подбор гиперпараметров (урок 21) — не лекарство, а способ выбрать дозу каждого из трёх: patience, коэффициент \(\gamma\), долю выключаемых нейронов. Сегодня — первое и самое дешёвое средство.

Две кривые: как переобучение выглядит во времени

Чтобы вовремя остановиться, нужен прибор. У профессора он умещается на одном слайде — "Early Stopping: Limiting Overfitting by Cross-validation" (лекция 3, слайд 12). Вся процедура там — четыре строки:

1. "Hold out some data" — отложить часть данных: это validation set из урока 18;
2. "Train on the training set" — вести спуск только по оставшимся данным;
3. "Perform cross-validation on the hold out set" — по ходу обучения считать ошибку на отложенных данных;
4. "Stop train when validation error increases" — остановить обучение, когда эта ошибка пошла вверх.

Слово cross-validation здесь не означает K-fold из урока 19. Профессор называет так любое использование training dataset и для обучения, и для оценки ошибки на новых данных, а первым вариантом у него идёт hold-out (лекция 3, слайд 6). Здесь именно он: одно разбиение, одно обучение.

Первые три строки и есть прибор. После каждой эпохи \(k\) error function считают дважды — на данных, по которым идёт спуск, и на отложенном validation set, который в вычислении градиента не участвует. Четвёртой строкой займётся следующий раздел.

Здесь записана Sum of Squared Errors; для классификации на её месте стояла бы cross-entropy, остальное не меняется. В выборках разное число примеров, поэтому перед сравнением каждую сумму делят на размер своей выборки. На то, при каком \(k\) кривая достигает минимума, это не влияет.

На слайде у кривых нет отдельных букв. Обе отложены по одной оси \(E(x \mid w)\) — ошибка на данных \(x\) при весах \(w\) — и подписаны словами: "Training set error" и "Validation set error". Индексы train и val пришли из конспекта: с ними кривые удобнее различать в формулах. Буква \(k\) на слайде — "the number of gradient descent iterations". Ошибку на отложенных данных считают раз в эпоху, поэтому в этом уроке \(k\) нумерует эпохи; в batch gradient descent эпоха и есть одна итерация. Нарисуем обе величины против \(k\).

Training error убывает всё время. (С mini-batch — только «в среднем»: отдельные эпохи могут подпрыгивать, об этом урок 27.) Validation error сначала падает вместе с ней, а потом разворачивается. На слайде это одна фраза: у переобучающихся сетей — "a monotone training error trend (on average with SGD)", но в какой-то момент они "lose generalization" (лекция 3, слайд 12). Конспект называет такое расхождение the signature of overfitting.

Почему кривые расходятся? Пока сеть вытаскивает из данных закономерности, общие для обеих выборок, падают обе ошибки. Когда общее исчерпано, спуск не останавливается: он продолжает уменьшать \(E_{\mathrm{train}}\) за счёт особенностей конкретных обучающих примеров — их шума. У отложенных примеров шум свой, с обучающим никак не связанный. Подгонка под чужой шум им только вредит.

Отсюда определение. Лучшая модель — не последняя, а та, что стоит на дне кривой validation.

Первая строка — формула (54) конспекта. Третья — обозначение слайда: высота минимума подписана там на вертикальной оси как \(E_{ES}(x \mid w)\). В конспекте у этого числа своей буквы нет. Дальше оно встретится не раз, и писать его будем коротко: \(E_{ES}\).

Кривая \(E_{\mathrm{val}}(k)\) даёт оценку ошибки на новых данных прямо по ходу обучения, без единого повторного запуска. На слайде к ней приколото облачко "Online estimate of the generalization error" (лекция 3, слайд 12); конспект повторяет его, добавив слово true. «Online» — потому что оценка появляется во время обучения, а не после него. Облачко относится к кривой целиком, а не к одному числу \(E_{ES}\). Насколько можно верить кривой и насколько её минимуму, разберём в последнем разделе.

Признак переобучения — не маленькая training error, а расходящиеся кривые: training error падает, validation error растёт.

Patience и checkpoint: остановка с откатом

Формула (54) задаёт цель, а не алгоритм. Четвёртая строка слайда 12 лекции 3 — "Stop train when validation error increases" — уже алгоритм, но для гладкой кривой, какая на слайде и нарисована. Между ней и работающей процедурой стоят две трудности — те самые, что в задачке из начала урока.

Шум. Настоящая кривая validation не гладкая, а зубчатая: каждая эпоха заканчивается в слегка случайной точке, а отложенных примеров конечное число. Первый подъём почти наверняка зубец, а не разворот.

Причинность. Даже без шума минимум опознаётся только задним числом. Чтобы убедиться, что \(E_{\mathrm{val}}(57)\) — дно, нужно увидеть \(E_{\mathrm{val}}(58)\). К этому моменту веса уже другие.

Обе трудности снимает то, что знакомо по играм, — сохранение. Вернёмся к подготовке. Каждый вечер после занятий ты пишешь один и тот же пробный вариант, по которому не готовишься. Побит личный рекорд — «сохраняешься». Рекорд не побит \(P\) вечеров подряд — заканчиваешь и загружаешь последнее сохранение.

Теперь то же самое формулами. Рекорд к эпохе \(k\) — наименьшая validation error за всё прошедшее время:

Эпоха \(k\) считается улучшением, если \(E_{\mathrm{val}}(k) \lt E_{\mathrm{best}}(k-1)\); первая эпоха — улучшение всегда. Пусть \(k_{\mathrm{best}}\) — эпоха последнего улучшения. Обучение останавливается на первой эпохе, для которой \(k - k_{\mathrm{best}} \ge P\), и возвращает веса \(\vb{w}^{k_{\mathrm{best}}}\). Целиком процедура выглядит так:

best = +inf;  wait = 0
for k = 1, 2, ...:
    train one epoch
    e = E_val(w)
    if e < best:
        best = e;  wait = 0
        save checkpoint
    else:
        wait = wait + 1
    if wait >= P:  stop
restore checkpoint

EarlyStopping(monitor='val_loss',
              patience=10,
              restore_best_weights=True)

Пример из конспекта — с исправлением

На стр. 153 конспекта дана validation loss для эпох 10–17 и задан вопрос: когда остановится обучение с patience 2? Пройдём таблицу по правилу из предыдущего раздела. Эпоха 10 в конспекте отмечена как улучшение, так что рекорд перед ней был хуже 0.40.

1. Эпохи 10, 11, 12: каждая лучше всех предыдущих. Рекорд обновляется трижды, после эпохи 12 он равен 0.37. Веса эпохи 12 сохранены, счётчик обнулён.

   \[ E_{\mathrm{best}}(12) = 0.37, \quad k_{\mathrm{best}} = 12 \]

2. Эпоха 13: 0.375 больше рекорда. Сохранять нечего, счётчик растёт.

   \[ 0.375 \gt 0.37 \;\Rightarrow\; \texttt{wait} = 1 \]

3. Эпоха 14 — место, где легко ошибиться. Ошибка 0.373 меньше вчерашней 0.375, но сравнивать надо с рекордом, а он по-прежнему 0.37.

   \[ 0.373 \gt 0.37 \;\Rightarrow\; \texttt{wait} = 2 \]

   При \(P = 2\) условие \(\texttt{wait} \ge P\) выполнено: обучение останавливается после эпохи 14.

4. При \(P = 4\) обучение продолжается. Эпохи 15 и 16 рекорд не бьют, счётчик доходит до 4: стоп после эпохи 16.

   \[ k - k_{\mathrm{best}} = 16 - 12 = 4 \ge P \]

5. В обоих случаях веса откатываются к checkpoint эпохи 12. Это согласуется с формулой (54): наименьшее число в таблице — 0.37.

   \[ k_{ES} = 12, \quad E_{ES} = 0.37 \]

Закономерность та же, что в виджете: стоп приходится на эпоху рекорда плюс \(P\). Больший patience стоит здесь только лишних эпох вычислений: возвращается всё равно эпоха 12.

Почему это регуляризация, если error function не тронута

В заголовках слайдов слово regularization стоит у weight decay и dropout, а early stopping подан как "Limiting Overfitting by Cross-validation" (лекция 3, слайд 12). Заголовок говорит, чем метод пользуется, а не что он делает с моделью. Конспект называет early stopping «built-in regularizer»: error function та же, архитектура та же. Что же тогда ограничено? Путь, который веса успевают пройти.

Обучение начинается с малых весов (почему — урок 25). При малых весах sigmoid и tanh работают на почти прямом участке возле нуля (урок 10), и вся сеть близка к линейной функции — простой. Извилистым функциям нужны большие веса, а до них надо дойти.

Один шаг спуска сдвигает веса на расстояние \(\eta\,\norm{\nabla E}\). Значит, за \(\tau\) шагов они не уйдут от старта дальше, чем на \(\eta\,\tau \cdot \max \norm{\nabla E}\). Мало шагов — малый радиус — в досягаемости только простые функции. Это и есть уменьшение effective capacity.

Поэтому рис. 2 так похож на U-образную кривую «сложность модели — ошибка» из урока 17: число эпох работает как ручка сложности. Конспект (стр. 151) проводит ту же параллель.

Рассуждение доводится до формулы. Возьмём одно направление в пространстве весов и посмотрим, какую долю пути к минимуму спуск проходит по нему за \(\tau\) шагов. Этот вывод выходит за рамки конспекта, но именно он отвечает на экзаменационное «why».

1. Возле минимума \(w^{*}\) ошибка вдоль одного направления — парабола с кривизной \(\lambda \gt 0\). Чем больше \(\lambda\), тем круче стенки: данные жёстко диктуют значение веса.

   \[ E(w) = E(w^{*}) + \tfrac{\lambda}{2}\,(w - w^{*})^2 \]

2. Шаг gradient descent из урока 13: градиент равен \(\lambda (w - w^{*})\), поэтому расстояние до минимума каждый раз умножается на одно и то же число.

   \[ w^{k+1} - w^{*} = (1 - \eta\lambda)\,(w^{k} - w^{*}) \]

3. Стартуем с нуля, \(w^{0} = 0\), и делаем \(\tau\) шагов. Множитель возводится в степень \(\tau\):

   \[ w^{\tau} = \bigl[\,1 - (1 - \eta\lambda)^{\tau}\,\bigr]\, w^{*} \]

   В квадратных скобках — пройденная доля пути. При большой \(\lambda\) она почти сразу равна 1, при малой растёт медленно.

4. Теперь другой способ. Weight decay (урок 22) не обрывает спуск, а добавляет к ошибке штраф \(\tfrac{\gamma}{2} w^2\) — с множителем \(\tfrac{1}{2}\), как в конспекте, — и спускается до конца. Приравняв производную суммы к нулю, получаем:

   \[ \lambda\,(\tilde{w} - w^{*}) + \gamma\,\tilde{w} = 0 \] \[ \tilde{w} = \frac{\lambda}{\lambda + \gamma}\, w^{*} \]

   Снова доля пути, зависящая от \(\lambda\).

5. Когда доли совпадают? Когда \((1 - \eta\lambda)^{\tau} = \gamma / (\lambda + \gamma)\). Возьмём логарифм обеих частей:

   \[ \tau \ln(1 - \eta\lambda) = -\ln\Bigl(1 + \frac{\lambda}{\gamma}\Bigr) \]

   Для пологих направлений \(\eta\lambda\) и \(\lambda / \gamma\) малы, а при малом \(x\) верно \(\ln(1 + x) \approx x\):

   \[ \tau\,\eta\lambda \approx \frac{\lambda}{\gamma} \;\Rightarrow\; \tau \approx \frac{1}{\eta\,\gamma} \]

   Кривизна \(\lambda\) сократилась: один и тот же \(\gamma\) подходит для всех пологих направлений сразу. Если штраф записан без \(\tfrac{1}{2}\), как \(\gamma \sum_q w_q^2\) на слайде профессора (лекция 3, слайд 15) и в уроке 22, в ответе появится двойка: \(\tau \approx 1 / (2\eta\gamma)\).

Мало шагов — сильная регуляризация, много шагов — слабая: \(\gamma \approx 1 / (\eta\,\tau)\).

Картина у обоих способов одна: то, что данные диктуют уверенно, проходит почти без потерь; то, о чём данные молчат, остаётся возле нуля. Именно в пологих направлениях сеть и подгоняется под шум. Если на курсе Applied Statistics тебе встречалась ridge regression, это тот же механизм: сжатие сильнее всего вдоль направлений с малой дисперсией данных.

Цена и мелкий шрифт

Стр. 154 конспекта подводит баланс метода. Вот он, с уточнением в каждой строке минусов.

Данные, отданные на validation, можно вернуть: когда \(k_{ES}\) найден, сеть обучают заново на объединении training и validation ровно \(k_{ES}\) эпох. Следить при этом уже не за чем — останавливаются по счётчику. Это тоже эвристика: данных стало больше, и лучшее число эпох могло сдвинуться.

И главное предупреждение конспекта: «Be careful: it's a heuristic!» Гарантии, что найден настоящий минимум, нет. Алгоритм видит только шумную кривую и может остановиться и раньше, и позже — смотря как легли шум, начальные веса и learning rate. Найденная эпоха — приближение к минимуму кривой обобщения, и на практике этого хватает.

Чему нельзя верить в числе \(E_{ES}\)

В последнем опыте обнаружилась странность: validation error в checkpoint стала ниже, а модель — хуже. Это не случайность одного прогона. Эпоху выбрали потому, что на ней число оказалось самым маленьким. А самым маленьким оно оказывается чаще всего там, где шум измерения отклонился вниз.

Теперь облачко слайда 12 лекции 3 — "Online estimate of the generalization error" — читается точно. Оно приколото к кривой, и про кривую это правда: при \(k\), назначенном заранее, \(E_{\mathrm{val}}(k)\) шумит, но не льстит. Это первый режим виджета. Льстит одно-единственное число — минимум \(E_{ES}\), потому что его выбирали по тем же данным. Слова unbiased на слайде нет, так что слайд и гистограмма друг другу не противоречат.

На следующем слайде профессор пользуется именно этим числом (лекция 3, слайд 13). У сети с \(J^{(1)}\) нейронами в скрытом слое оно записано как \(E_{ES}^{J^{(1)}}(x \mid w)\) и подписано "Generalization error with J neurons in 1 layer", а размер слоя выбирают по таким числам: "Chose model with best validation error". Одно и то же число названо там и generalization error, и validation error: вторая служит оценкой первой. Для сравнения моделей между собой \(E_{ES}\) годится: validation set и определён на слайдах как данные для model selection (лекция 3, слайд 5). Как устроен такой выбор, расскажет урок 21.

Вывод практический. Для выбора момента остановки test set не нужен — хватает validation. Но итоговое число для отчёта берут с test set, который не участвовал ни в спуске, ни в выборе эпохи (урок 18): на том же слайде 5 это названо final model assessment. Это тот же эффект, что с лучшим результатом cross-validation в уроке 19.

Вернёмся к задачке

Инструкцию конспекта «остановиться прямо перед ростом» выполнить нельзя, и не нужно. Строку слайда "Stop train when validation error increases" выполнить можно, но буквально она работает только на гладкой кривой, какая на слайде и нарисована. На настоящей, шумной кривой её читают с двумя поправками. Первая: не реагировать на первый рост, а ждать \(P\) эпох без нового рекорда — так переживаются зубцы вроде скачка на рисунке 18. Вторая: не пытаться угадать минимум заранее, а пройти мимо него и вернуться — к копии весов, сохранённой в момент рекорда, то есть к весам эпохи \(k_{ES}\).

А пример конспекта спотыкается на слове «улучшение»: им названа эпоха 14, которая лучше вчерашней, но хуже рекорда. Отсюда ответ 17 вместо 14.