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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Базовые концепции машинного обучения

[править | править код]

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

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

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

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

[править | править код]

(Адаптировано из Yao, Rosasco and Caponnetto, 2007[3])

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

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

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

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

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

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

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

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

[править | править код]

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

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

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

[править | править код]

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

  1. Разделить обучающий набор данных на обучающий набор и проверочный набор, например в пропорции два к одному.
  2. Обучить только с использованием обучающего набора, иногда оценивая ошибки поэкземлярно с помощью проверочного набора, например после каждой пятой эпохи.
  3. Остановить обучение, после того как ошибка на проверочном наборе станет больше, чем она была во время последней проверки.
  4. Использовать веса сети из предыдущего шага в качестве результата обучения.
    Lutz Prechelt, Early Stopping – But When?

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

Примечания

[править | править код]
  1. Girosi, Federico; Michael Jones; Tomaso Poggio (1995-03-01). "Regularization Theory and Neural Networks Architectures". Neural Computation. 7 (2): 219—269. CiteSeerX 10.1.1.48.9258. doi:10.1162/neco.1995.7.2.219. ISSN 0899-7667. S2CID 49743910.
  2. 1 2 Smale, Steve; Ding-Xuan Zhou (2007-08-01). "Learning Theory Estimates via Integral Operators and Their Approximations". Constructive Approximation. 26 (2): 153—172. CiteSeerX 10.1.1.210.722. doi:10.1007/s00365-006-0659-y. ISSN 0176-4276. S2CID 5977083.
  3. 1 2 3 4 Yao, Yuan; Lorenzo Rosasco; Andrea Caponnetto (2007-08-01). "On Early Stopping in Gradient Descent Learning". Constructive Approximation. 26 (2): 289—315. CiteSeerX 10.1.1.329.2482. doi:10.1007/s00365-006-0663-2. ISSN 0176-4276. S2CID 8323954.
  4. Raskutti, G.; M.J. Wainwright; Bin Yu (2011). "Early stopping for non-parametric regression: An optimal data-dependent stopping rule". 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). pp. 1318—1325. doi:10.1109/Allerton.2011.6120320.
  5. Wenxin Jiang (February 2004). "Process consistency for AdaBoost". The Annals of Statistics. 32 (1): 13—29. doi:10.1214/aos/1079120128. ISSN 0090-5364.
  6. Bühlmann, Peter; Bin Yu (2003-06-01). "Boosting with the L₂ Loss: Regression and Classification". Journal of the American Statistical Association. 98 (462): 324—339. doi:10.1198/016214503000125. ISSN 0162-1459. JSTOR 30045243. S2CID 123059267.
  7. Tong Zhang; Bin Yu (2005-08-01). "Boosting with Early Stopping: Convergence and Consistency". The Annals of Statistics. 33 (4): 1538—1579. arXiv:math/0508276. Bibcode:2005math......8276Z. doi:10.1214/009053605000000255. ISSN 0090-5364. JSTOR 3448617. S2CID 13158356.
  8. 1 2 Prechelt, Lutz. Early Stopping — But When? // Neural Networks: Tricks of the Trade / Lutz Prechelt, Geneviève B. Orr. — Springer Berlin Heidelberg, 2012-01-01. — P. 53–67. — ISBN 978-3-642-35289-8. — doi:10.1007/978-3-642-35289-8_5.