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

Базовые концепции машинного обучения 
Некоторые базовые концепции машинного обучения, необходимые для описания методов ранней остановки.

Переобучение 

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

Регуляризация 

Регуляризация в контексте машинного обучения обозначает процесс изменения алгоритма обучения для предотвращения процесса переобучения. Обычно этот процесс использует некоторый вид плавного ограничения обучаемой модели. Гладкость может быть достигнута явно, с использованием фиксированного числа параметров модели, или дополнением модели функцией потерь, как в методе регуляризации Тихонова. Регуляризация Тихонова, вместе с  и множеством других схем регуляризации, находятся в одной группе спектральной регуляризации — регуляризации с использованием фильтра. Ранняя остановка также принадлежит этому классу методов.

Методы градиентного спуска 

Методы градиентного спуска являются итеративными методами оптимизации первого порядка. Каждая итерация обновляет приближенное решение для проблемы оптимизации делая шаг в направлении отрицательного градиента целевой функции. Соответствующим образом выбирая размер шага, так что метод может стать сводимым к локальному минимуму целевой функции. При использовании градиентного спуска в машинном обучении функция потерь отражает ошибку модели на обучающем наборе и затем минимизирует эту функцию.

Ранняя остановка основанная на аналитическом результате

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

 

где  является условным распределением  вызванным .Одним из распространенных подходов для аппроксимации регрессионной функции является использование функций . Эти пространства могут быть бесконечномерными, в том смысле, что они могут предоставить решения, которые переобучат обучающие наборы любого размера. Регуляризация, таким образом, особенно важна для этих методов. Одним из подходов регуляризации проблем непараметрической регрессии является применение правила ранней остановки к итеративной процедуре, например, такой как градиентный спуск.

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

Пример: Метод наименьших квадратов 
(Адаптировано из Yao, Rosasco and Caponnetto, 2007)

Пусть  и  Учитывая множество экземпляров

 

взятых независимо из , необходимо минимизировать функционал

 

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

 

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

Мы хотим контролировать разницу между ожидаемым риском итерации выборки и минимальным ожидаемым риском, то есть, ожидаемым риском функции регрессии:

 

Разница может быть перезаписана как сумма двух терминов: разница в ожидаемом риске между итерациями выборки и совокупности, и разница между итерацией совокупности и функцией регрессии:

 

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

Ранняя остановка в бустинге 
Бустингом называется семейство алгоритмов, в которых множество слабых моделей (моделей, слабо описывающих истинный процесс) комбинируются для создания сильной модели. Было показано, что для некоторых алгоритмов бустинга (включаюших AdaBoost), регуляризация с помощью ранней остановки может предоставить гарантии состоятельности, то есть, того, что результат алгоритма будет достигать истинного решения по при стремлении количества выборок к бесконечности.

L-бустинг 
Методы бустинга, имеющие тесные связи с методами ранней остановки для непараметрической регрессии с помощью градиентного спуска можно считать методом бустинга основанного на функции потерь : LBoost.

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

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

См. также 
 Переобучение, ранняя остановка является одним из методов, используемых для предотвращения переобучения
 Ошибка обобщения
 Регуляризация (математика)
 Статистическая теория обучения
 Бустинг
 Перекрёстная проверка
 Нейронная сеть

Примечания 

Искусственные нейронные сети