Ранняя остановка - Early stopping

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

Фон

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

Переоснащение

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

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

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

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

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

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

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

Ранняя остановка в теории статистического обучения

Ранняя остановка может использоваться для регуляризации проблем непараметрической регрессии, встречающихся в машинном обучении . Для заданного входного пространства, , выходное пространство, , и образцов , взятых из неизвестных вероятностных мере, на , цель подобных проблем заключается в аппроксимации функции регрессии , , задаются ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle \ rho}$${\ Displaystyle Z = X \ раз Y}$${\ displaystyle f _ {\ rho}}$

${\ displaystyle f _ {\ rho} (x) = \ int _ {Y} y \, d \ rho (y \ mid x), \, x \ in X,}$

где - условное распределение в, индуцированное . Один из распространенных вариантов аппроксимации функции регрессии - использование функций из гильбертова пространства воспроизводящего ядра . Эти пространства могут быть бесконечномерными, в которых они могут предоставлять решения, которые превосходят обучающие наборы произвольного размера. Поэтому регуляризация особенно важна для этих методов. Одним из способов регуляризации задач непараметрической регрессии является применение правила ранней остановки к итерационной процедуре, такой как градиентный спуск. ${\ Displaystyle \ rho (у \ середина х)}$${\ displaystyle x}$${\ displaystyle \ rho}$

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

Пример: потеря наименьших квадратов

(По материалам Yao, Rosasco and Caponnetto, 2007 г.)

Пусть и Учитывая набор образцов ${\ Displaystyle X \ substeq \ mathbb {R} ^ {n}}$${\ Displaystyle Y = \ mathbb {R}.}$

${\ displaystyle \ mathbf {z} = \ left \ {(x_ {i}, y_ {i}) \ in X \ times Y: i = 1, \ dots, m \ right \} \ in Z ^ {m} ,}$

взяты независимо от , минимизировать функционал ${\ displaystyle \ rho}$

${\ displaystyle {\ mathcal {E}} (f) = \ int _ {X \ times Y} (f (x) -y) ^ {2} \, d \ rho}$

где, - член воспроизводящего ядра гильбертова пространства . То есть минимизировать ожидаемый риск для функции потерь наименьших квадратов. Поскольку зависит от неизвестной вероятностной меры , ее нельзя использовать для вычислений. Вместо этого рассмотрите следующий эмпирический риск ${\ displaystyle f}$${\ displaystyle {\ mathcal {H}}}$${\ displaystyle {\ mathcal {E}}}$${\ displaystyle \ rho}$

${\ displaystyle {\ mathcal {E}} _ {\ mathbf {z}} (f) = {\ frac {1} {m}} \ sum _ {i = 1} ^ {m} \ left (f (x_ {i}) - y_ {i} \ right) ^ {2}.}$

Пусть и будет t -ой итерацией градиентного спуска, применяемой к ожидаемому и эмпирическому рискам, соответственно, где обе итерации инициализируются в начале координат, и обе используют размер шага . Образуют итерации популяции , которая сходится к , но не может быть использована в вычислении, в то время как форма образца итерация , которые , как правило , сходится к переобучению раствора. ${\ displaystyle f_ {t}}$${\ displaystyle f_ {t} ^ {\ mathbf {z}}}$${\ displaystyle \ gamma _ {t}}$${\ displaystyle f_ {t}}$${\ displaystyle f _ {\ rho}}$${\ displaystyle f_ {t} ^ {\ mathbf {z}}}$

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

${\ displaystyle {\ mathcal {E}} (f_ {t} ^ {\ mathbf {z}}) - {\ mathcal {E}} (f _ {\ rho})}$

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

${\ displaystyle {\ mathcal {E}} (f_ {t} ^ {\ mathbf {z}}) - {\ mathcal {E}} (f _ {\ rho}) = \ left [{\ mathcal {E}} (f_ {t} ^ {\ mathbf {z}}) - {\ mathcal {E}} (f_ {t}) \ right] + \ left [{\ mathcal {E}} (f_ {t}) - { \ mathcal {E}} (f _ {\ rho}) \ right]}$

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

Раннее прекращение разгона

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

L _{2 -} усиление

Методы повышения имеют тесную связь с методами градиентного спуска, описанными выше, и могут рассматриваться как метод повышения, основанный на потерях: L ₂ Boost . ${\ displaystyle L_ {2}}$

Ранняя остановка на основе валидации

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

1. Разделите обучающие данные на обучающий набор и набор проверки, например, в пропорции 2 к 1.
2. Тренируйтесь только на обучающем наборе и время от времени оценивайте ошибку для каждого примера на проверочном наборе, например, после каждой пятой эпохи.
3. Остановите обучение, как только ошибка в наборе проверки станет выше, чем при последней проверке.
4. Используйте веса, которые сеть имела на предыдущем шаге в результате обучающего прогона.
   -  Лутц Прешельт, Ранняя остановка - Но когда?

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

Смотрите также

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

использованная литература