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