Просмотр кода страницы Ранняя остановка

<noinclude>{{к удалению|2023-02-27}}</noinclude>
В [[машинное обучение|машинном обучении]], '''ранняя остановка''' — форма [[Регуляризация (математика)|регуляризации]], используемая для избежания [[переобучение|переобучения]] при обучении модели с помощью итеративного метода, например, такого, как [[градиентный спуск]]. При использовании подобных методов модель обновляется после каждой итерации для того, чтобы лучше соответствовать обучающим данным и до определенного момента это улучшает производительность модели также и на данных, не входящих в обучающий набор, но после этого момента улучшение соответствия модели обучающим данным происходит за счёт увеличения [[ошибка обобщения|ошибки обобщения]]. Правила ранней остановки являются руководством по определению того, как много итераций может пройти, перед переобучением модели и они используются во множестве методов машинного обучения.

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

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

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

=== Регуляризация ===
{{Main|Регуляризация (математика)}}
Регуляризация в контексте машинного обучения обозначает процесс изменения алгоритма обучения для предотвращения процесса переобучения. Обычно этот процесс использует некоторый вид плавного ограничения обучаемой модели.<ref>{{Cite journal|doi=10.1162/neco.1995.7.2.219|issn=0899-7667|volume=7|issue=2|pages=219–269|last=Girosi|first=Federico|author2=Michael Jones|author3=Tomaso Poggio|title=Regularization Theory and Neural Networks Architectures|url=https://archive.org/details/sim_neural-computation_1995-03_7_2/page/219|journal=Neural Computation|date=1995-03-01|citeseerx=10.1.1.48.9258|s2cid=49743910}}</ref> Гладкость может быть достигнута явно, с использованием фиксированного числа параметров модели, или дополнением модели функцией потерь, как в [[Метод регуляризации Тихонова|методе регуляризации Тихонова]]. Регуляризация Тихонова, вместе с {{iw|регрессия главного компонента|регрессией главного компонента|en|principal component regression}} и множеством других схем регуляризации, находятся в одной группе спектральной регуляризации — регуляризации с использованием фильтра. Ранняя остановка также принадлежит этому классу методов.

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

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

=== Ранняя остановка в [[Статистическая теория обучения|статистической теории обучения]] ===
Ранняя остановка может быть использована для регуляризации проблем [[непараметрическая регрессия|непараметрической регрессии]], встречающихся в машинном обучении. Для данного входного пространства <math>X</math>, выходного пространства <math>Y</math> и экземпляров, полученных с помощью неизвестной вероятностной меры <math>\rho</math>, при <math>Z = X \times Y</math>, необходимо аппроксимировать ''регрессионную функцию'' <math>f_{\rho}</math>, 

: <math> f_\rho(x) = \int_Y y \, d\rho(y\mid x),\, x \in X,</math>

где <math>\rho(y\mid x)</math> является условным распределением <math>x</math> вызванным <math>\rho</math>.<ref name="smale_learning_2007">{{Cite journal|doi=10.1007/s00365-006-0659-y|issn=0176-4276|volume=26|issue=2|pages=153–172|last=Smale|first=Steve|author2=Ding-Xuan Zhou|title=Learning Theory Estimates via Integral Operators and Their Approximations|journal=Constructive Approximation|date=2007-08-01|citeseerx=10.1.1.210.722|s2cid=5977083}}</ref>Одним из распространенных подходов для аппроксимации регрессионной функции является использование функций {{iw|Гильбертово пространство с воспроизводящим ядром|гильбертова пространства с воспроизводящим ядром|en|reproducing kernel Hilbert space}}.<ref name="smale_learning_2007" /> Эти пространства могут быть бесконечномерными, в том смысле, что они могут предоставить решения, которые переобучат обучающие наборы любого размера. Регуляризация, таким образом, особенно важна для этих методов. Одним из подходов регуляризации проблем непараметрической регрессии является применение правила ранней остановки к итеративной процедуре, например, такой как градиентный спуск.

Правила ранней остановки, предлагаемые для этих проблем, основаны на анализе верхней границы ошибки обобщения как функции числа итераций. Они дают предписания для количества необходимых итераций, которое может быть вычислено перед запуском процесса поиска решения<ref name="yao_early_2007">{{Cite journal|doi=10.1007/s00365-006-0663-2|issn=0176-4276|volume=26|issue=2|pages=289–315|last=Yao|first=Yuan|author2=Lorenzo Rosasco|author3=Andrea Caponnetto|title=On Early Stopping in Gradient Descent Learning|journal=Constructive Approximation|date=2007-08-01|citeseerx=10.1.1.329.2482|s2cid=8323954}}</ref>
<ref name="raskutti_early_2011">{{Cite conference|doi=10.1109/Allerton.2011.6120320|conference=2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)|pages=1318–1325|last=Raskutti|first=G.|author2=M.J. Wainwright|author3=Bin Yu|title=Early stopping for non-parametric regression: An optimal data-dependent stopping rule|book-title=2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)|year=2011}}</ref>.

==== Пример: Метод наименьших квадратов ====
(Адаптировано из Yao, Rosasco and Caponnetto, 2007<ref name="yao_early_2007" />)

Пусть <math>X\subseteq\mathbb{R}^n</math> и <math>Y=\mathbb{R}.</math> Учитывая множество экземпляров

: <math>\mathbf{z} = \left \{(x_i,y_i) \in X \times Y: i = 1, \dots, m\right\} \in Z^m,</math>

взятых независимо из <math>\rho</math>, необходимо минимизировать функционал

: <math>
\mathcal{E}(f) = \int_{X\times Y} (f(x) - y)^2 \, d\rho
</math>

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

: <math>
\mathcal{E}_{\mathbf{z}}(f) = \frac{1}{m} \sum_{i=1}^m \left(f(x_i) - y_{i}\right)^2.
</math>

Пусть <math>f_{t}</math> и <math>f_t^{\mathbf{z}}</math> являются ''t'' повторами градиентного спуска примененного к ожидаемым и эмпирическим рискам, соответственно, в случае, когда обе итерации инициализированы в начале координат и используют размер шага <math>\gamma_{t}</math>. <math>f_{t}</math> формирует ''итерацию совокупленности'', которая сходится к <math>f_{\rho}</math>, но не может быть использована в вычислениях, пока <math>f_t^{\mathbf{z}}</math> формирует ''итерацию выборки'', которая обычно сходится к переобучаемому решению.

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

: <math>\mathcal{E}(f_t^{\mathbf{z}}) - \mathcal{E}(f_\rho)</math>

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

: <math>\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]</math>

Это уравнение представляет [[Дилемма смещения–дисперсии|дилемму смещения-дисперсии]], которая затем решается для нахождения оптимального правила остановки, которое может зависеть от неизвестного вероятностного распределения. Это правило связано с вероятностными границами ошибки обобщения. Анализ,приводящий к определению правила и границам ранней остановки описан в первоначальной статье.<ref name="yao_early_2007" /> На практике для получения адаптивного правила остановки, могут быть использованы различные методы управляемые данными, например такие, как перекрестная сверка.

=== Ранняя остановка в бустинге ===
[[Бустинг]]ом называется семейство алгоритмов, в которых множество '''слабых моделей''' (моделей, слабо описывающих истинный процесс) комбинируются для создания '''сильной модели'''. Было показано, что для некоторых алгоритмов бустинга (включаюших [[AdaBoost]]), регуляризация с помощью ранней остановки может предоставить гарантии [[Состоятельность (статистика)|состоятельности]], то есть, того, что результат алгоритма будет достигать истинного решения по при стремлении количества выборок к бесконечности.<ref>{{Cite journal|doi=10.1214/aos/1079120128|issn=0090-5364|volume=32|issue=1|pages=13–29|last=Wenxin Jiang|title=Process consistency for AdaBoost|url=https://archive.org/details/sim_annals-of-statistics_2004-02_32_1/page/n20|journal=The Annals of Statistics|date=February 2004|doi-access=free}}</ref><ref>{{Cite journal|issn=0162-1459|volume=98|issue=462|pages=324–339|last=Bühlmann|first=Peter|author2=Bin Yu|title=Boosting with the L₂ Loss: Regression and Classification|url=https://archive.org/details/sim_journal-of-the-american-statistical-association_2003-06_98_462/page/n67|journal=Journal of the American Statistical Association|date=2003-06-01|jstor=30045243|doi=10.1198/016214503000125|s2cid=123059267}}</ref><ref>{{Cite journal|issn=0090-5364|volume=33|issue=4|pages=1538–1579|last=Tong Zhang|author2=Bin Yu|title=Boosting with Early Stopping: Convergence and Consistency|url=https://archive.org/details/sim_annals-of-statistics_2005-08_33_4/page/1538|journal=The Annals of Statistics|date=2005-08-01|jstor=3448617|doi=10.1214/009053605000000255|arxiv=math/0508276|bibcode=2005math......8276Z|s2cid=13158356}}</ref>

==== L{{sub|2}}-бустинг ====
Методы бустинга, имеющие тесные связи с методами ранней остановки для непараметрической регрессии с помощью градиентного спуска можно считать методом бустинга основанного на функции потерь <math>L_{2}</math>: ''L{{sub|2}}Boost''.<ref name="yao_early_2007" />

== Ранняя остановка, основанная на проверке ==
Данные правила ранней остановки работают при разделении первоначального обучающего набора на новый обучающий набор и проверочный набор. Ошибка на проверочном наборе используется вместо [[ошибка обобщения|ошибки обобщения]] для определения момента, в который началось переобучение. Правила наиболее часто используются в обучении [[нейронная сеть|искусственных нейронных сетей]]. Пречелт дает следующее обобщение реализации ранней остановки, основанной на [[метод удержания|методе удержания]]:<ref name="prechelt_early_2012">{{Cite book|last=Prechelt|first=Lutz|author2=Geneviève B. Orr|editor=Grégoire Montavon|editor2=Klaus-Robert Müller|chapter=Early Stopping — But When?|title=Neural Networks: Tricks of the Trade|url=https://archive.org/details/neuralnetworkstr00mlle|publisher=Springer Berlin Heidelberg|date=2012-01-01|pages=[https://archive.org/details/neuralnetworkstr00mlle/page/n60 53]–67|isbn=978-3-642-35289-8|doi=10.1007/978-3-642-35289-8_5|editor2-link=Klaus-Robert Müller|url-access=limited|series=Lecture Notes in Computer Science}}</ref>

{{Quotation|<nowiki />
# Разделить обучающий набор данных на обучающий набор и проверочный набор, например в пропорции два к одному.
# Обучить только с использованием обучающего набора, иногда оценивая ошибки поэкземлярно с помощью проверочного набора, например после каждой пятой эпохи.
# Остановить обучение, после того как ошибка на проверочном наборе станет больше, чем она была во время последней проверки.
# Использовать веса сети из предыдущего шага в качестве результата обучения.|Lutz Prechelt|''Early Stopping – But When?''}}

Более сложные формы используют [[Перекрёстная проверка|перекрёстную проверку]] — многократное разделение данных на обучающий и проверочный наборы, вместо одногократного разделения. Но даже эта простая процедура осложняется на практике тем фактом, что ошибка пожет колебаться во время обучения, создавая множество локальных минимумов. Это осложнение привело к созданию множества правил для определения истинного начала переобучения.<ref name="prechelt_early_2012" />

== См. также ==
* [[Переобучение]], ранняя остановка является одним из методов, используемых для предотвращения переобучения
* [[Ошибка обобщения]]
* [[Регуляризация (математика)]]
* [[Статистическая теория обучения]]
* [[Бустинг]]
* [[Перекрёстная проверка]]
* [[Нейронная сеть]]

== Примечания ==
{{примечания}}

[[Категория:Искусственные нейронные сети]]