Ранняя остановка

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

Предыстория

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

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

Основная статья: Переоснащение

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

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

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

Основная статья: Регуляризация (математика)

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

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

Основная статья: Градиентный спуск

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

остановка на основании

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

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

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

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

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

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

(Адаптировано из Яо, Росаско и Капоннетто, 2007 г.) )

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

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

нарисовано независимо от $\rho$, минимизируем функционал

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

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

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

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

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

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

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

${\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 ₂ -усиление

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

Ранняя остановка на основе проверки

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

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

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

См. также

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