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

Метод в машинном обучении

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть и задан набор образцов ${\displaystyle X\subseteq \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]}$

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

Раннее прекращение буста

Повышение относится к семейству алгоритмов, в которых набор слабых обучающихся (обучающихся, которые лишь незначительно коррелируют с истинным процессом) объединяются для создания сильного обучающегося . Для нескольких алгоритмов повышения (включая AdaBoost ) было показано , что регуляризация посредством ранней остановки может обеспечить гарантии согласованности , то есть того, что результат алгоритма приближается к истинному решению, когда количество выборок стремится к бесконечности. ^{[5] [6] [7]}

L ₂ -бустирующий

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

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

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

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

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

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

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

Рекомендации

1. Джирози, Федерико; Майкл Джонс; Томазо Поджо (1 марта 1995 г.). «Теория регуляризации и архитектуры нейронных сетей». Нейронные вычисления . 7 (2): 219–269. CiteSeerX  10.1.1.48.9258 . дои : 10.1162/neco.1995.7.2.219. ISSN  0899-7667. S2CID  49743910.
2. Смейл, Стив; Дин-Сюань Чжоу (1 августа 2007 г.). «Оценки теории обучения с помощью интегральных операторов и их аппроксимаций». Конструктивная аппроксимация . 26 (2): 153–172. CiteSeerX 10.1.1.210.722 . doi : 10.1007/s00365-006-0659-y. ISSN  0176-4276. S2CID  5977083. 
3. Яо, Юань; Лоренцо Росаско; Андреа Капоннетто (1 августа 2007 г.). «О ранней остановке в обучении градиентному спуску». Конструктивная аппроксимация . 26 (2): 289–315. CiteSeerX 10.1.1.329.2482 . дои : 10.1007/s00365-006-0663-2. ISSN  0176-4276. S2CID  8323954. 
4. Раскутти, Г.; М. Дж. Уэйнрайт; Бинь Ю (2011). «Ранняя остановка непараметрической регрессии: оптимальное правило остановки, зависящее от данных». 2011 49-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton) . 2011 49-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton). стр. 1318–1325. doi : 10.1109/Allerton.2011.6120320.
5. Вэньсинь Цзян (февраль 2004 г.). «Последовательность процессов для AdaBoost». Анналы статистики . 32 (1): 13–29. дои : 10.1214/aos/1079120128 . ISSN  0090-5364.
6. Бюльманн, Питер; Бинь Ю (01.06.2003). «Усиление с потерей L₂: регрессия и классификация». Журнал Американской статистической ассоциации . 98 (462): 324–339. дои : 10.1198/016214503000125. ISSN  0162-1459. JSTOR  30045243. S2CID  123059267.
7. Тонг Чжан; Бинь Ю (01 августа 2005 г.). «Усиление с ранней остановкой: конвергенция и последовательность». Анналы статистики . 33 (4): 1538–1579. arXiv : math/0508276 . Бибкод : 2005math......8276Z. дои : 10.1214/009053605000000255. ISSN  0090-5364. JSTOR  3448617. S2CID  13158356.
8. Пречелт, Лутц; Женевьева Б. Орр (1 января 2012 г.). «Ранняя остановка — но когда?». В Грегуаре Монтавоне; Клаус-Роберт Мюллер (ред.). Нейронные сети: хитрости . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 53–67. дои : 10.1007/978-3-642-35289-8_5. ISBN 978-3-642-35289-8.