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

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Переобучение (англ. overfitting) — явление в машинном обучении, при котором модель чрезмерно приспосабливается к обучающей выборке, включая содержащиеся в ней случайные отклонения, шум и нерепрезентативные особенности. В результате модель показывает низкую ошибку на известных примерах, но хуже работает на новых данных.^[1]^[1]

Основная цель обучения по прецедентам состоит не в запоминании обучающих объектов, а в построении алгоритма, способного правильно обрабатывать ранее не наблюдавшиеся данные. Такое свойство называется обобщающей способностью (англ. generalization ability).

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

Противоположное явление называется недообучением (англ. underfitting). При недообучении модель оказывается слишком простой или недостаточно обученной и не выявляет закономерности даже в обучающих данных.

Постановка задачи

Пусть задано множество объектов $X$ и множество допустимых ответов $Y$ . В задаче классификации множество $Y$ обычно конечно, а в задаче регрессии ответы чаще всего являются вещественными числами.

Обучающая выборка имеет вид

$X^\ell=\{(x_i,y_i)\}_{i=1}^{\ell},\quad x_i\in X,\quad y_i\in Y.$

Предполагается, что пары $(x_i,y_i)$ получены независимо из некоторого неизвестного распределения $P(x,y)$ . По обучающей выборке требуется построить алгоритм

$a:X\to Y,$

который будет правильно предсказывать ответы не только на обучающих объектах, но и на новых объектах из того же распределения.

Для измерения качества предсказания используется функция потерь

$L(a(x),y),$

которая показывает, насколько предсказание $a(x)$ отличается от правильного ответа $y$ .

В задаче регрессии часто применяется квадратичная функция потерь:

$L(a(x),y)=(a(x)-y)^2.$

В задаче классификации может использоваться индикатор ошибки:

$L(a(x),y)=[a(x)\ne y],$

где выражение в квадратных скобках равно единице, если условие выполнено, и нулю в противном случае.

Эмпирический и истинный риск

Средняя ошибка алгоритма на обучающей выборке называется эмпирическим риском (англ. empirical risk):

$\hat R_{X^\ell}(a)=\frac{1}{\ell}\sum_{i=1}^{\ell}L(a(x_i),y_i).$

Многие методы машинного обучения основаны на принципе минимизации эмпирического риска (англ. empirical risk minimization). Из заданного семейства алгоритмов $A$ выбирается алгоритм, для которого эмпирический риск минимален:

$\hat R_{X^\ell}(a)\to\min_{a\in A}.$

Однако конечной целью обучения является минимизация истинного, или среднего, риска:

$R(a)={\rm E}_{(x,y)\sim P}L(a(x),y).$

Истинный риск представляет собой среднюю ошибку алгоритма на новых объектах, порождённых распределением $P(x,y)$ . Поскольку это распределение неизвестно, точное значение истинного риска обычно вычислить невозможно.

Разность между истинным и эмпирическим риском называется разрывом обобщения (англ. generalization gap):

$G_{X^\ell}(a)=R(a)-\hat R_{X^\ell}(a).$

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

Формально переобучение удобно определять относительно двух алгоритмов. Алгоритм $a_1$ переобучен по сравнению с алгоритмом $a_2$ , если он лучше описывает обучающую выборку, но обладает большей истинной ошибкой:

$\hat R_{X^\ell}(a_1)<\hat R_{X^\ell}(a_2),\qquad R(a_1)>R(a_2).$

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

Сложность модели

Способность семейства моделей описывать различные зависимости называется ёмкостью модели (англ. model capacity). Чем выше ёмкость, тем более сложные зависимости может представить модель.

В зависимости от типа алгоритма сложность модели может определяться:

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

В статистической теории обучения сложность класса алгоритмов может характеризоваться VC-мерностью (англ. Vapnik–Chervonenkis dimension). Типичные оценки обобщающей способности имеют вид^[1]

$R(a)\leq \hat R_{X^\ell}(a)+C\sqrt{\frac{h\ln(2\ell/h)+\ln(2/\delta)}{\ell}},$

где $h$ — мера сложности семейства алгоритмов, $\ell$ — объём обучающей выборки, $\delta$ — допустимая вероятность нарушения оценки, а $C$ — постоянная, зависящая от используемой теоремы.

Из подобных оценок следует, что обобщающая способность зависит не только от ошибки на обучении, но и от соотношения между сложностью модели и объёмом данных.

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

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

Смещение и разброс

Классическое объяснение переобучения связано с компромиссом между смещением и разбросом (англ. bias–variance trade-off).

Рассмотрим задачу регрессии, в которой данные порождаются согласно модели

$y=f(x)+\varepsilon,$

где случайный шум удовлетворяет условиям

${\rm E}(\varepsilon|x)=0,\qquad {\rm E}(\varepsilon^2|x)=\sigma^2.$

Пусть $\hat f_D$ — модель, построенная по случайной обучающей выборке $D$ . Для квадратичной функции потерь ожидаемая ошибка в точке $x$ раскладывается на три слагаемых:^[1]

${\rm E}_{D,\varepsilon}(y-\hat f_D(x))^2=\sigma^2+({\rm E}_D\hat f_D(x)-f(x))^2+{\rm E}_D(\hat f_D(x)-{\rm E}_D\hat f_D(x))^2.$

Первое слагаемое $\sigma^2$ соответствует неустранимому шуму в данных.

Второе слагаемое является квадратом смещения (англ. bias). Оно характеризует систематическое отличие среднего предсказания модели от истинной зависимости.

Третье слагаемое называется разбросом или дисперсией модели (англ. variance). Оно показывает, насколько сильно результат обучения меняется при замене одной обучающей выборки другой.

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

В классической постановке недообучение связывают с большим смещением, а переобучение — с большим разбросом. Однако такое объяснение не полностью описывает поведение современных сильно параметризованных моделей.

Причины переобучения

Недостаточный объём выборки

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

Проблема усиливается с ростом числа признаков. В пространстве высокой размерности обучающие объекты располагаются разреженно, поэтому модель может строить сложные зависимости, опираясь на небольшое число наблюдений. Это связано с явлением, называемым проклятием размерности (англ. curse of dimensionality).

Избыточная сложность модели

Если семейство моделей существенно сложнее восстанавливаемой зависимости, в нём могут существовать модели, почти безошибочно описывающие обучающие данные, но нестабильные вне обучающей выборки.

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

Шум и ошибочные ответы

Реальные данные могут содержать:

ошибки измерения;
ошибочные метки классов;
выбросы;
пропущенные значения;
дубликаты;
противоречивые наблюдения.

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

Избыточное число признаков

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

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

Слишком продолжительное обучение

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

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

Многократный подбор гиперпараметров

Гиперпараметры (англ. hyperparameters) определяют структуру модели и процесс её обучения. К ним относятся глубина дерева, коэффициент регуляризации, скорость обучения, число слоёв, размер пакета и другие величины.

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

Нерепрезентативность данных

Обучающая выборка должна отражать условия, в которых модель будет применяться. Если некоторые группы объектов представлены недостаточно или отсутствуют, алгоритм может использовать закономерности, характерные только для собранных данных.

Такую ситуацию следует отличать от сдвига распределения (англ. distribution shift), при котором распределение эксплуатационных данных отличается от распределения обучающей выборки.

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

Примеры

Полиномиальная регрессия

Пусть наблюдения имеют вид

$y_i=\sin x_i+\varepsilon_i,$

где $\varepsilon_i$ — случайный шум. Для приближения зависимости используется полиномиальная модель

$p_m(x)=a_0+a_1x+\ldots+a_mx^m.$

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

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

Следовательно, полином высокой степени может иметь почти нулевую обучающую ошибку, но плохо приближать исходную зависимость вне обучающих точек.

Дерево решений

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

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

Для управления сложностью дерева применяют:

ограничение максимальной глубины;
ограничение числа листьев;
минимальное число объектов в листе;
минимальное уменьшение ошибки при разбиении;
отсечение дерева (англ. pruning).

Линейная регрессия

В линейной регрессии переобучение может возникать при большом числе признаков, особенно если признаки сильно коррелированы или число параметров сравнимо с числом наблюдений.

При использовании метода наименьших квадратов минимизируется функционал

$Q(w)=\sum_{i=1}^{\ell}(y_i-w^Tx_i)^2\to\min_w.$

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

Нейронные сети

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

Однако способность к запоминанию (англ. memorization) не означает обязательного переобучения. Большая нейронная сеть может одновременно иметь почти нулевую обучающую ошибку и высокое качество на новых данных.

На обобщающую способность нейронной сети влияют:

архитектура;
алгоритм оптимизации;
начальные значения параметров;
нормы весов;
аугментация данных;
регуляризация;
структура обучающих данных;
момент остановки обучения.

Поэтому число параметров нейронной сети само по себе не позволяет однозначно определить степень переобучения.

Диагностика

Разделение данных

Обычно исходный набор данных разделяют на три части:

обучающая выборка (англ. training set) используется для настройки параметров модели;
контрольная выборка (англ. validation set) используется для выбора модели, гиперпараметров и момента остановки обучения;
тестовая выборка (англ. test set) используется только для итоговой оценки качества.

Характерные сочетания ошибок:

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

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

Кривые обучения

Кривые обучения (англ. learning curves) показывают зависимость ошибки от числа итераций, размера обучающей выборки или сложности модели.

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

Увеличивающийся разрыв между обучающей и контрольной ошибками является одним из основных практических признаков переобучения.

Кривые, построенные в зависимости от объёма выборки, помогают определить, полезен ли дополнительный сбор данных. Если контрольная ошибка продолжает уменьшаться с ростом выборки, увеличение количества примеров, вероятно, улучшит качество модели.

Скользящий контроль

Если объём данных невелик, оценка качества может сильно зависеть от конкретного разделения на обучение и контроль. Для получения более устойчивой оценки используется скользящий контроль (англ. cross-validation).

При $k$ -блочном скользящем контроле выборка делится на $k$ непересекающихся частей. Алгоритм $k$ раз обучается на $k-1$ частях и проверяется на оставшейся части.

Оценка ошибки имеет вид

$\hat R_{\rm CV}=\frac{1}{k}\sum_{j=1}^{k}\hat R_{D_j}(a_{-j}),$

где $a_{-j}$ — алгоритм, обученный без использования блока $D_j$ .

Скользящий контроль уменьшает зависимость результата от одного случайного разбиения, но не предотвращает переобучение автоматически.^[1]

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

В таких случаях применяется вложенный скользящий контроль (англ. nested cross-validation). Во внутреннем цикле выбираются гиперпараметры, а во внешнем цикле оценивается качество выбранной процедуры.

Проверка устойчивости

Переобученная модель часто чувствительна к небольшим изменениям данных. Для проверки устойчивости можно:

повторять обучение на различных разбиениях выборки;
изменять начальные значения параметров;
исключать небольшую часть объектов;
добавлять небольшой шум к признакам;
сравнивать результаты на различных временных периодах;
оценивать разброс метрик качества.

Большой разброс результатов между повторными экспериментами может указывать на высокую дисперсию модели.

Методы борьбы с переобучением

Увеличение объёма данных

При увеличении числа независимых и репрезентативных наблюдений модели становится сложнее приспособиться к случайным особенностям отдельных объектов.

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

Простое увеличение числа объектов не помогает, если новые данные содержат те же систематические ошибки или не отражают условия реального применения модели.

Улучшение качества данных

Предварительная обработка может включать:

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

Ошибочные метки особенно опасны для моделей высокой сложности, поскольку такие модели способны их запоминать.

Аугментация данных

Аугментация данных (англ. data augmentation) заключается в создании дополнительных обучающих примеров с помощью преобразований исходных объектов.

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

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

Упрощение модели

Сложность модели можно уменьшить непосредственно:

сократить число признаков;
уменьшить степень полинома;
ограничить глубину дерева;
уменьшить число слоёв или нейронов;
объединить редкие категории;
удалить слабозначимые параметры;
использовать более сильные предположения о структуре зависимости.

Упрощение модели уменьшает разброс, но при чрезмерном ограничении может привести к недообучению.

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

Регуляризация (англ. regularization) добавляет к эмпирическому риску штраф за сложность модели:

$\hat R_{X^\ell}(a)+\lambda\Omega(a)\to\min_{a\in A},$

где $\Omega(a)$ — регуляризатор, а $\lambda\geq 0$ — коэффициент регуляризации.

Чем больше $\lambda$ , тем сильнее ограничивается модель. При слишком малом значении регуляризация почти не влияет на результат, а при слишком большом модель может недообучиться.

Для линейных моделей часто используется $L_2$ -регуляризация, также называемая штрафом за норму весов:

$\Omega(w)=\|w\|_2^2=\sum_{j=1}^{p}w_j^2.$

Она ограничивает величину коэффициентов и делает модель менее чувствительной к изменениям выборки.

При $L_1$ -регуляризации используется штраф

$\Omega(w)=\|w\|_1=\sum_{j=1}^{p}|w_j|.$

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

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

Ранняя остановка (англ. early stopping) применяется к моделям, обучаемым итеративно. После каждой итерации вычисляется ошибка на контрольной выборке. Обучение прекращается, если контрольное качество перестаёт улучшаться.

Сохраняются параметры, соответствующие наименьшей контрольной ошибке, а не последней выполненной итерации.^[1]

Ранняя остановка ограничивает способность модели приспосабливаться к шуму и может рассматриваться как форма регуляризации.

Метод случайных отключений

Метод случайных отключений (англ. dropout) применяется при обучении нейронных сетей. На каждой итерации часть нейронов случайно исключается из вычислений.

Для активации $h_j$ можно записать

$r_j\sim{\rm Bernoulli}(q),\qquad \tilde h_j=\frac{r_j}{q}h_j,$

где $q$ — вероятность сохранения нейрона.

Случайное отключение мешает нейронам чрезмерно приспосабливаться друг к другу и приближённо соответствует совместному обучению большого числа различных подсетей.^[1]

Ансамблирование

Ансамблевые методы объединяют предсказания нескольких моделей. Для задачи регрессии простое усреднение имеет вид

$\bar a(x)=\frac{1}{M}\sum_{m=1}^{M}a_m(x).$

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

К методам, уменьшающим переобучение за счёт усреднения, относятся бэггинг (англ. bagging) и случайный лес (англ. random forest).

Ансамблирование не устраняет систематическую ошибку, если все модели используют одинаковые ложные закономерности.

Отбор и преобразование признаков

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

Методы понижения размерности, например метод главных компонент, преобразуют исходные признаки в пространство меньшей размерности.

Отбор признаков должен выполняться только внутри обучающей части данных. Если признаки отбираются до разделения выборки, информация из контрольных объектов может попасть в процесс обучения.

Корректное оценивание качества

Для предотвращения скрытого переобучения необходимо:

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

Утечка данных

Утечка данных (англ. data leakage) возникает, когда в обучение или вычисление признаков попадает информация, которая не будет доступна в момент реального предсказания.

Примеры утечки данных:

нормировка всех объектов до разделения на обучение и контроль;
отбор признаков по полной выборке;
использование будущих значений во временном ряду;
включение в признаки результата, вычисленного после наступления предсказываемого события;
попадание одинаковых или почти одинаковых объектов в обучающую и тестовую выборки.

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

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

Переобучение в глубоком обучении

Классическое представление предполагает U-образную зависимость тестовой ошибки от сложности модели. При малой сложности ошибка велика из-за недообучения, затем достигает минимума, а после дальнейшего усложнения возрастает вследствие переобучения.

Для некоторых современных моделей наблюдается более сложная зависимость, называемая двойным спуском (англ. double descent).^[1]

При приближении к порогу интерполяции (англ. interpolation threshold), на котором модель впервые получает почти нулевую обучающую ошибку, тестовая ошибка может увеличиться. При дальнейшем увеличении числа параметров она в некоторых случаях снова уменьшается.

Это явление показывает, что:

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

Неявная регуляризация (англ. implicit regularization) возникает, когда метод оптимизации предпочитает определённые решения даже при отсутствии явного штрафа в функционале качества.

Например, градиентные методы могут выбирать среди множества решений модели с определёнными свойствами норм параметров.

Двойной спуск не означает исчезновения проблемы переобучения. Сильно параметризованная модель по-прежнему может запоминать шум, быть неустойчивой и терять качество при изменении распределения данных.

Отличие от связанных явлений

Недообучение

При недообучении ошибка велика как на обучающей, так и на контрольной выборке. Возможные причины:

модель слишком проста;
использованы неинформативные признаки;
обучение остановлено слишком рано;
регуляризация слишком сильна;
алгоритм оптимизации не достиг подходящего решения.

При переобучении обучающая ошибка, напротив, обычно мала.

Запоминание данных

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

Современные нейронные сети способны запоминать отдельные объекты и одновременно выявлять общую структуру данных.

Сдвиг распределения

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

Переобучение относится к неспособности обобщать данные из исходного распределения, тогда как сдвиг распределения связан с изменением самого источника данных.

Ошибка спецификации модели

Ошибка спецификации модели (англ. model misspecification) возникает, если выбранное семейство моделей не соответствует структуре задачи.

Например, линейная модель может использоваться для описания существенно нелинейной зависимости. Такое несоответствие чаще приводит к недообучению, однако неверно выбранные признаки и предположения могут также создавать нестабильные зависимости.

Практическое значение

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

Риск переобучения особенно велик при следующих условиях:

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

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

См. также

Примечания

Литература

Vapnik V. N. The Nature of Statistical Learning Theory. 2nd ed. Springer, 2000.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer, 2009.
Goodfellow I., Bengio Y., Courville A. Deep Learning. MIT Press, 2016.
Geman S., Bienenstock E., Doursat R. Neural Networks and the Bias/Variance Dilemma // Neural Computation. 1992. Vol. 4, no. 1. P. 1–58.
Stone M. Cross-Validatory Choice and Assessment of Statistical Predictions // Journal of the Royal Statistical Society. Series B. 1974. Vol. 36, no. 2. P. 111–133.
Tibshirani R. Regression Shrinkage and Selection via the Lasso // Journal of the Royal Statistical Society. Series B. 1996. Vol. 58, no. 1. P. 267–288.
Prechelt L. Early Stopping — But When? // Neural Networks: Tricks of the Trade. Springer, 2012. P. 53–67.
Srivastava N., Hinton G., Krizhevsky A., Sutskever I., Salakhutdinov R. Dropout: A Simple Way to Prevent Neural Networks from Overfitting // Journal of Machine Learning Research. 2014. Vol. 15. P. 1929–1958.
Zhang C., Bengio S., Hardt M., Recht B., Vinyals O. Understanding Deep Learning Requires Rethinking Generalization // International Conference on Learning Representations, 2017.
Belkin M., Hsu D., Ma S., Mandal S. Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off // Proceedings of the National Academy of Sciences. 2019. Vol. 116, no. 32. P. 15849–15854.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B5%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5»

Категории: Машинное обучение | Обучение по прецедентам | Регуляризация

@@ Строка 1: / Строка 1: @@
-'''Обобщающая способность''' (generalization ability, generalization performance).
+'''Переобучение''' (англ. ''overfitting'') — явление в [[машинное обучение|машинном обучении]], при котором модель чрезмерно приспосабливается к обучающей выборке, включая содержащиеся в ней случайные отклонения, шум и нерепрезентативные особенности. В результате модель показывает низкую ошибку на известных примерах, но хуже работает на новых данных.<ref name="Goodfellow2016">Goodfellow I., Bengio Y., Courville A. [https://www.deeplearningbook.org/ Deep Learning]. MIT Press, 2016. Chapters 5, 7.</ref><ref name="Hastie2009">Hastie T., Tibshirani R., Friedman J. [https://doi.org/10.1007/978-0-387-84858-7 The Elements of Statistical Learning: Data Mining, Inference, and Prediction]. 2nd ed. Springer, 2009.</ref>
-Говорят, что [[алгоритм обучения]] обладает ''способностью к обобщению'', если вероятность ошибки на [[тестовая выборка|тестовой выборке]] достаточно мала или хотя бы предсказуема, то есть не сильно отличается от ошибки на [[обучающая выборка|обучающей выборке]].
-''Обобщающая способность'' тесно связана с понятиями ''переобучения'' и ''недообучения''.
-'''Переобучение''', '''переподгонка''' (overtraining, overfitting) — нежелательное явление, возникающее при решении задач [[обучение по прецедентам|обучения по прецедентам]], когда вероятность ошибки обученного алгоритма на объектах [[тестовая выборка|тестовой выборки]] оказывается существенно выше, чем средняя ошибка на [[обучающая выборка|обучающей выборке]].
+Основная цель [[обучение по прецедентам|обучения по прецедентам]] состоит не в запоминании обучающих объектов, а в построении алгоритма, способного правильно обрабатывать ранее не наблюдавшиеся данные. Такое свойство называется '''обобщающей способностью''' (англ. ''generalization ability'').
-Переобучение возникает при использовании избыточно сложных [[модель зависимости|моделей]].
-'''Недообучение''' — нежелательное явление, возникающее при решении задач [[обучение по прецедентам|обучения по прецедентам]], когда [[алгоритм обучения]] не обеспечивает достаточно малой величины средней ошибки на [[обучающая выборка|обучающей выборке]].
+Малая ошибка на обучающей выборке сама по себе не означает, что модель обладает высокой обобщающей способностью. Основным признаком переобучения является существенная разница между ошибкой на обучающих данных и ошибкой на независимой контрольной или тестовой выборке.
-Недообучение возникает при использовании недостаточно сложных [[модель зависимости|моделей]].
-== О природе переобучения ==
+Противоположное явление называется '''недообучением''' (англ. ''underfitting''). При недообучении модель оказывается слишком простой или недостаточно обученной и не выявляет закономерности даже в обучающих данных.
-''Эмпирическим риском'' называется средняя ошибка алгоритма на обучающей выборке.
+== Постановка задачи ==
-Метод ''[[Минимизация эмпирического риска|минимизации эмпирического риска]]'' (empirical risk minimization, ERM) наиболее часто применяется для построения алгоритмов обучения.
-{{S|Он состоит}} в том, чтобы в рамках заданной модели выбрать алгоритм, имеющий минимальное значение средней ошибки на заданной обучающей выборке.
-С переобучением метода ERM связано два утверждения, которые на первый взгляд могут показаться парадоксальными.
+Пусть задано множество объектов <tex>X</tex> и множество допустимых ответов <tex>Y</tex>. В задаче [[Классификация|классификации]] множество <tex>Y</tex> обычно конечно, а в задаче [[Регрессия|регрессии]] ответы чаще всего являются вещественными числами.
-'''Утверждение 1.'''
+Обучающая выборка имеет вид
-''Минимизация эмпирического риска не гарантирует, что вероятность ошибки на тестовых данных будет мала.''
-Легко строится контрпример — абсурдный алгоритм обучения, который минимизирует эмпирический риск до нуля, но при этом абсолютно не способен обучаться.
-Алгоритм состоит в следующем.
-Получив обучающую выборку, он запоминает её и строит функцию, которая сравнивает предъявляемый объект с запомненными обучающими объектами.
-Если предъявляемый объект в точности совпадает с одним из обучающих, то эта функция выдаёт для него запомненный правильный ответ.
-Иначе выдаётся произвольный ответ (например, случайный или всегда один и тот же).
-Эмпирический риск алгоритма равен нулю, однако он не восстанавливает зависимость и не обладает никакой способностью к обобщению.
-Вывод: ''для успешного обучения необходимо не только запоминать, но и обобщать''.
+::<tex>X^\ell=\{(x_i,y_i)\}_{i=1}^{\ell},\quad x_i\in X,\quad y_i\in Y.</tex>
-'''Утверждение 2.'''
+Предполагается, что пары <tex>(x_i,y_i)</tex> получены независимо из некоторого неизвестного распределения <tex>P(x,y)</tex>. По обучающей выборке требуется построить алгоритм
-''Переобучение появляется именно вследствие минимизации эмпирического риска.''
-Пусть задано конечное множество из ''D'' алгоритмов, которые допускают ошибки независимо и с одинаковой вероятностью.
-Число ошибок любого из этих алгоритмов на заданной обучающей выборке подчиняется одному и тому же [[биномиальное распределение|биномиальному распределению]].
-Минимум эмпирического риска — это случайная величина, равная минимуму из ''D'' независимых одинаково распределённых биномиальных случайных величин.
-Её&nbsp;ожидаемое значение уменьшается с&nbsp;ростом&nbsp;''D''.
-Соотвественно, с&nbsp;ростом&nbsp;''D'' увеличивается ''переобученность'' — разность вероятности ошибки и частоты ошибок на обучении.
-В данном модельном примере легко построить доверительный интервал переобученности, так как функция распределения минимума известна.
+::<tex>a:X\to Y,</tex>
-Однако в&nbsp;реальной ситуации алгоритмы имеют различные вероятности ошибок, не являются независимыми,
-а&nbsp;множество алгоритмов, из которого выбирается лучший, может быть бесконечным.
-По&nbsp;этим причинам вывод количественных оценок переобученности является сложной задачей, которой занимается [[теория вычислительного обучения]].
-До&nbsp;сих&nbsp;пор остаётся открытой проблема сильной завышенности верхних оценок переобучения.
-== Основные определения ==
+который будет правильно предсказывать ответы не только на обучающих объектах, но и на новых объектах из того же распределения.
-== Теоретические верхние оценки переобученности ==
+Для измерения качества предсказания используется [[Функция потерь|функция потерь]]
-=== Сложность ===
+::<tex>L(a(x),y),</tex>
-Оценки Вапника-Червоненкиса, [[ёмкость|размерность Вапника-Червоненкиса]]
-[[Критерий Акаике]]
+которая показывает, насколько предсказание <tex>a(x)</tex> отличается от правильного ответа <tex>y</tex>.
-Оценки, основанные на самоограничении (self-bounding)
+В задаче регрессии часто применяется квадратичная функция потерь:
-Оценки, основанные на последовательности выборов (microchoice bounds)
+::<tex>L(a(x),y)=(a(x)-y)^2.</tex>
-Оценки, основанные на расслоении семейства алгоритмов (shell bounds)
+В задаче классификации может использоваться индикатор ошибки:
-=== Разделимость ===
+::<tex>L(a(x),y)=[a(x)\ne y],</tex>
-Оценки, основанные на отступах (margin-based bounds)
-=== Устойчивость ===
+где выражение в квадратных скобках равно единице, если условие выполнено, и нулю в противном случае.
-Устойчивость алгоритма обучения (algorithmic stability)
-== Эмпирическое измерение переобучения ==
+== Эмпирический и истинный риск ==
-[[Скользящий контроль]]
+Средняя ошибка алгоритма на обучающей выборке называется [[Эмпирический риск|эмпирическим риском]] (англ. ''empirical risk''):
+::<tex>\hat R_{X^\ell}(a)=\frac{1}{\ell}\sum_{i=1}^{\ell}L(a(x_i),y_i).</tex>
+Многие методы машинного обучения основаны на [[Минимизация эмпирического риска|принципе минимизации эмпирического риска]] (англ. ''empirical risk minimization''). Из заданного семейства алгоритмов <tex>A</tex> выбирается алгоритм, для которого эмпирический риск минимален:
+::<tex>\hat R_{X^\ell}(a)\to\min_{a\in A}.</tex>
+Однако конечной целью обучения является минимизация истинного, или среднего, риска:
+::<tex>R(a)={\rm E}_{(x,y)\sim P}L(a(x),y).</tex>
+Истинный риск представляет собой среднюю ошибку алгоритма на новых объектах, порождённых распределением <tex>P(x,y)</tex>. Поскольку это распределение неизвестно, точное значение истинного риска обычно вычислить невозможно.
+Разность между истинным и эмпирическим риском называется '''разрывом обобщения''' (англ. ''generalization gap''):
+::<tex>G_{X^\ell}(a)=R(a)-\hat R_{X^\ell}(a).</tex>
+Большое положительное значение разрыва обобщения означает, что ошибка на новых данных существенно выше ошибки на обучающей выборке, и может свидетельствовать о переобучении.
+Формально переобучение удобно определять относительно двух алгоритмов. Алгоритм <tex>a_1</tex> переобучен по сравнению с алгоритмом <tex>a_2</tex>, если он лучше описывает обучающую выборку, но обладает большей истинной ошибкой:
+::<tex>\hat R_{X^\ell}(a_1)<\hat R_{X^\ell}(a_2),\qquad R(a_1)>R(a_2).</tex>
+Следовательно, переобучение связано не просто с малой обучающей ошибкой, а с ухудшением качества на новых данных при дальнейшем приспособлении модели к обучающей выборке.
+== Сложность модели ==
+Способность семейства моделей описывать различные зависимости называется '''ёмкостью модели''' (англ. ''model capacity''). Чем выше ёмкость, тем более сложные зависимости может представить модель.
+В зависимости от типа алгоритма сложность модели может определяться:
+* числом настраиваемых параметров;
+* степенью полинома;
+* глубиной [[Дерево решений|дерева решений]];
+* числом листьев дерева;
+* числом используемых признаков;
+* шириной и глубиной [[Нейронная сеть|нейронной сети]];
+* величиной коэффициентов модели;
+* гладкостью восстанавливаемой функции;
+* размерностью пространства допустимых решений.
+В статистической теории обучения сложность класса алгоритмов может характеризоваться [[VC-мерность|VC-мерностью]] (англ. ''Vapnik–Chervonenkis dimension''). Типичные оценки обобщающей способности имеют вид<ref name="Vapnik2000">Vapnik V. N. [https://doi.org/10.1007/978-1-4757-3264-1 The Nature of Statistical Learning Theory]. 2nd ed. Springer, 2000.</ref>
+::<tex>R(a)\leq \hat R_{X^\ell}(a)+C\sqrt{\frac{h\ln(2\ell/h)+\ln(2/\delta)}{\ell}},</tex>
+где <tex>h</tex> — мера сложности семейства алгоритмов, <tex>\ell</tex> — объём обучающей выборки, <tex>\delta</tex> — допустимая вероятность нарушения оценки, а <tex>C</tex> — постоянная, зависящая от используемой теоремы.
+Из подобных оценок следует, что обобщающая способность зависит не только от ошибки на обучении, но и от соотношения между сложностью модели и объёмом данных.
+При фиксированном размере выборки использование чрезмерно сложного семейства алгоритмов может увеличить риск переобучения. При увеличении объёма обучающих данных допустимая сложность модели обычно возрастает.
+Число параметров не является универсальной мерой сложности. Две модели с одинаковым числом параметров могут обладать разной обобщающей способностью вследствие различий в архитектуре, ограничениях на параметры и алгоритме оптимизации.
+== Смещение и разброс ==
+Классическое объяснение переобучения связано с компромиссом между смещением и разбросом (англ. ''bias–variance trade-off'').
+Рассмотрим задачу регрессии, в которой данные порождаются согласно модели
+::<tex>y=f(x)+\varepsilon,</tex>
+где случайный шум удовлетворяет условиям
+::<tex>{\rm E}(\varepsilon|x)=0,\qquad {\rm E}(\varepsilon^2|x)=\sigma^2.</tex>
+Пусть <tex>\hat f_D</tex> — модель, построенная по случайной обучающей выборке <tex>D</tex>. Для квадратичной функции потерь ожидаемая ошибка в точке <tex>x</tex> раскладывается на три слагаемых:<ref name="Geman1992">Geman S., Bienenstock E., Doursat R. [https://doi.org/10.1162/neco.1992.4.1.1 Neural Networks and the Bias/Variance Dilemma] // Neural Computation. 1992. Vol. 4, no. 1. P. 1–58.</ref>
+::<tex>{\rm E}_{D,\varepsilon}(y-\hat f_D(x))^2=\sigma^2+({\rm E}_D\hat f_D(x)-f(x))^2+{\rm E}_D(\hat f_D(x)-{\rm E}_D\hat f_D(x))^2.</tex>
+Первое слагаемое <tex>\sigma^2</tex> соответствует неустранимому шуму в данных.
+Второе слагаемое является квадратом '''смещения''' (англ. ''bias''). Оно характеризует систематическое отличие среднего предсказания модели от истинной зависимости.
+Третье слагаемое называется '''разбросом''' или '''дисперсией модели''' (англ. ''variance''). Оно показывает, насколько сильно результат обучения меняется при замене одной обучающей выборки другой.
+Слишком простая модель обычно имеет большое смещение: она не может достаточно точно представить восстанавливаемую зависимость. Слишком гибкая модель может иметь большой разброс и существенно изменяться при небольшом изменении обучающих данных.
+В классической постановке недообучение связывают с большим смещением, а переобучение — с большим разбросом. Однако такое объяснение не полностью описывает поведение современных сильно параметризованных моделей.
+== Причины переобучения ==
+=== Недостаточный объём выборки ===
+При малом числе обучающих объектов трудно отличить устойчивую закономерность от случайного совпадения. Алгоритм может обнаружить зависимость, которая присутствует только в конкретной выборке и не воспроизводится на новых данных.
+Проблема усиливается с ростом числа признаков. В пространстве высокой размерности обучающие объекты располагаются разреженно, поэтому модель может строить сложные зависимости, опираясь на небольшое число наблюдений. Это связано с явлением, называемым [[Проклятие размерности|проклятием размерности]] (англ. ''curse of dimensionality'').
+=== Избыточная сложность модели ===
+Если семейство моделей существенно сложнее восстанавливаемой зависимости, в нём могут существовать модели, почти безошибочно описывающие обучающие данные, но нестабильные вне обучающей выборки.
+Например, глубокое дерево решений может выделить отдельный лист почти для каждого обучающего объекта. Такое дерево запоминает частные особенности выборки вместо построения устойчивых правил.
+=== Шум и ошибочные ответы ===
+Реальные данные могут содержать:
+* ошибки измерения;
+* ошибочные метки классов;
+* выбросы;
+* пропущенные значения;
+* дубликаты;
+* противоречивые наблюдения.
+Модель высокой сложности может приспособиться не только к содержательной зависимости, но и к ошибкам в данных. В предельном случае алгоритм запоминает соответствие между отдельными объектами и случайными ответами.
+=== Избыточное число признаков ===
+Неинформативные признаки могут случайно коррелировать с целевой переменной на ограниченной выборке. При большом числе признаков вероятность обнаружения случайных корреляций возрастает.
+Поэтому некорректно выполненный [[Отбор признаков|отбор признаков]] также может привести к переобучению. Если признаки выбираются с использованием всей выборки до разделения данных, информация о контрольных объектах косвенно попадает в процесс обучения.
+=== Слишком продолжительное обучение ===
+При итеративной оптимизации модель обычно сначала выявляет наиболее устойчивые зависимости, а затем начинает приспосабливаться к менее значимым деталям и шуму.
+Это особенно характерно для нейронных сетей, обучаемых с помощью [[Градиентный спуск|градиентного спуска]]. Ошибка на обучающей выборке может продолжать уменьшаться, тогда как ошибка на контрольной выборке после некоторого момента начинает возрастать.
+=== Многократный подбор гиперпараметров ===
+'''Гиперпараметры''' (англ. ''hyperparameters'') определяют структуру модели и процесс её обучения. К ним относятся глубина дерева, коэффициент регуляризации, скорость обучения, число слоёв, размер пакета и другие величины.
+Если большое число конфигураций сравнивается на одной и той же контрольной выборке, информация об этой выборке постепенно используется при выборе модели. В результате модель может косвенно переобучиться под контрольные данные.
+=== Нерепрезентативность данных ===
+Обучающая выборка должна отражать условия, в которых модель будет применяться. Если некоторые группы объектов представлены недостаточно или отсутствуют, алгоритм может использовать закономерности, характерные только для собранных данных.
+Такую ситуацию следует отличать от '''сдвига распределения''' (англ. ''distribution shift''), при котором распределение эксплуатационных данных отличается от распределения обучающей выборки.
+Снижение качества при сдвиге распределения возможно даже для модели, которая не была переобучена на исходных данных.
+== Примеры ==
+=== Полиномиальная регрессия ===
+Пусть наблюдения имеют вид
+::<tex>y_i=\sin x_i+\varepsilon_i,</tex>
+где <tex>\varepsilon_i</tex> — случайный шум. Для приближения зависимости используется [[Полиномиальная регрессия|полиномиальная модель]]
+::<tex>p_m(x)=a_0+a_1x+\ldots+a_mx^m.</tex>
+Полином малой степени не способен описать изгибы синусоиды и недообучается. Полином умеренной степени приближает основную зависимость. Полином очень высокой степени может проходить почти через все обучающие точки, включая случайные отклонения, и образовывать сильные колебания между ними.
+По мере увеличения степени <tex>m</tex> ошибка на обучающей выборке обычно не возрастает, поскольку каждый следующий класс полиномов содержит предыдущий. Ошибка на новых данных сначала может уменьшаться, а затем возрастать.
+Следовательно, полином высокой степени может иметь почти нулевую обучающую ошибку, но плохо приближать исходную зависимость вне обучающих точек.
+=== Дерево решений ===
+При построении дерева решений пространство объектов последовательно разбивается на области. Если не ограничивать глубину дерева и минимальное число объектов в листе, разбиение может продолжаться до почти полного разделения обучающих примеров.
+Полученное дерево имеет низкую обучающую ошибку, но его правила могут зависеть от единичных объектов и случайного шума.
+Для управления сложностью дерева применяют:
+* ограничение максимальной глубины;
+* ограничение числа листьев;
+* минимальное число объектов в листе;
+* минимальное уменьшение ошибки при разбиении;
+* '''отсечение дерева''' (англ. ''pruning'').
+=== Линейная регрессия ===
+В [[Линейная регрессия|линейной регрессии]] переобучение может возникать при большом числе признаков, особенно если признаки сильно коррелированы или число параметров сравнимо с числом наблюдений.
+При использовании [[Метод наименьших квадратов|метода наименьших квадратов]] минимизируется функционал
+::<tex>Q(w)=\sum_{i=1}^{\ell}(y_i-w^Tx_i)^2\to\min_w.</tex>
+Если матрица признаков плохо обусловлена, небольшие изменения обучающих данных могут приводить к большим изменениям коэффициентов. Такая модель имеет высокий разброс и может давать нестабильные предсказания.
+=== Нейронные сети ===
+Современные нейронные сети часто содержат больше параметров, чем имеется обучающих объектов. Достаточно выразительная сеть способна запомнить даже случайно переставленные метки классов.<ref name="Zhang2017">Zhang C., Bengio S., Hardt M., Recht B., Vinyals O. [https://openreview.net/forum?id=Sy8gdB9xx Understanding Deep Learning Requires Rethinking Generalization] // International Conference on Learning Representations, 2017.</ref>
+Однако способность к '''запоминанию''' (англ. ''memorization'') не означает обязательного переобучения. Большая нейронная сеть может одновременно иметь почти нулевую обучающую ошибку и высокое качество на новых данных.
+На обобщающую способность нейронной сети влияют:
+* архитектура;
+* алгоритм оптимизации;
+* начальные значения параметров;
+* нормы весов;
+* аугментация данных;
+* регуляризация;
+* структура обучающих данных;
+* момент остановки обучения.
+Поэтому число параметров нейронной сети само по себе не позволяет однозначно определить степень переобучения.
+== Диагностика ==
+=== Разделение данных ===
+Обычно исходный набор данных разделяют на три части:
+* '''обучающая выборка''' (англ. ''training set'') используется для настройки параметров модели;
+* '''контрольная выборка''' (англ. ''validation set'') используется для выбора модели, гиперпараметров и момента остановки обучения;
+* '''тестовая выборка''' (англ. ''test set'') используется только для итоговой оценки качества.
+Характерные сочетания ошибок:
+* '''недообучение:''' ошибка высока как на обучающей, так и на контрольной выборке;
+* '''хорошее обобщение:''' обе ошибки малы и незначительно отличаются друг от друга;
+* '''переобучение:''' ошибка на обучающей выборке мала, а ошибка на контрольной выборке существенно выше.
+Тестовая выборка не должна использоваться для выбора признаков, архитектуры или гиперпараметров. В противном случае оценка тестового качества становится смещённой.
+=== Кривые обучения ===
+'''Кривые обучения''' (англ. ''learning curves'') показывают зависимость ошибки от числа итераций, размера обучающей выборки или сложности модели.
+При итеративном обучении ошибка на обучающей выборке обычно уменьшается. Ошибка на контрольной выборке сначала также уменьшается, но после начала переобучения может возрастать.
+Увеличивающийся разрыв между обучающей и контрольной ошибками является одним из основных практических признаков переобучения.
+Кривые, построенные в зависимости от объёма выборки, помогают определить, полезен ли дополнительный сбор данных. Если контрольная ошибка продолжает уменьшаться с ростом выборки, увеличение количества примеров, вероятно, улучшит качество модели.
+=== Скользящий контроль ===
+Если объём данных невелик, оценка качества может сильно зависеть от конкретного разделения на обучение и контроль. Для получения более устойчивой оценки используется [[Скользящий контроль|скользящий контроль]] (англ. ''cross-validation'').
+При <tex>k</tex>-блочном скользящем контроле выборка делится на <tex>k</tex> непересекающихся частей. Алгоритм <tex>k</tex> раз обучается на <tex>k-1</tex> частях и проверяется на оставшейся части.
+Оценка ошибки имеет вид
+::<tex>\hat R_{\rm CV}=\frac{1}{k}\sum_{j=1}^{k}\hat R_{D_j}(a_{-j}),</tex>
+где <tex>a_{-j}</tex> — алгоритм, обученный без использования блока <tex>D_j</tex>.
+Скользящий контроль уменьшает зависимость результата от одного случайного разбиения, но не предотвращает переобучение автоматически.<ref name="Stone1974">Stone M. [https://doi.org/10.1111/j.2517-6161.1974.tb00994.x Cross-Validatory Choice and Assessment of Statistical Predictions] // Journal of the Royal Statistical Society. Series B. 1974. Vol. 36, no. 2. P. 111–133.</ref>
+Если результаты скользящего контроля многократно используются для выбора признаков и гиперпараметров, итоговая модель может переобучиться под саму процедуру оценивания.
+В таких случаях применяется '''вложенный скользящий контроль''' (англ. ''nested cross-validation''). Во внутреннем цикле выбираются гиперпараметры, а во внешнем цикле оценивается качество выбранной процедуры.
+=== Проверка устойчивости ===
+Переобученная модель часто чувствительна к небольшим изменениям данных. Для проверки устойчивости можно:
+* повторять обучение на различных разбиениях выборки;
+* изменять начальные значения параметров;
+* исключать небольшую часть объектов;
+* добавлять небольшой шум к признакам;
+* сравнивать результаты на различных временных периодах;
+* оценивать разброс метрик качества.
+Большой разброс результатов между повторными экспериментами может указывать на высокую дисперсию модели.
+== Методы борьбы с переобучением ==
+=== Увеличение объёма данных ===
+При увеличении числа независимых и репрезентативных наблюдений модели становится сложнее приспособиться к случайным особенностям отдельных объектов.
+Дополнительные данные особенно полезны, если обучающая и контрольная ошибки существенно различаются, а контрольное качество продолжает улучшаться с ростом выборки.
+Простое увеличение числа объектов не помогает, если новые данные содержат те же систематические ошибки или не отражают условия реального применения модели.
+=== Улучшение качества данных ===
+Предварительная обработка может включать:
+* исправление ошибочных ответов;
+* удаление дубликатов;
+* анализ выбросов;
+* обработку пропущенных значений;
+* согласование единиц измерения;
+* проверку источников данных;
+* устранение признаков, недоступных в момент предсказания.
+Ошибочные метки особенно опасны для моделей высокой сложности, поскольку такие модели способны их запоминать.
+=== Аугментация данных ===
+'''Аугментация данных''' (англ. ''data augmentation'') заключается в создании дополнительных обучающих примеров с помощью преобразований исходных объектов.
+Для изображений применяются повороты, отражения, изменение масштаба, кадрирование и изменение яркости. Для звуковых сигналов могут использоваться временные сдвиги, изменение скорости и добавление шума.
+Преобразования должны сохранять правильный ответ. Например, горизонтальное отражение изображения автомобиля обычно не изменяет его класс, тогда как отражение некоторых букв и цифр может изменить их значение.
+=== Упрощение модели ===
+Сложность модели можно уменьшить непосредственно:
+* сократить число признаков;
+* уменьшить степень полинома;
+* ограничить глубину дерева;
+* уменьшить число слоёв или нейронов;
+* объединить редкие категории;
+* удалить слабозначимые параметры;
+* использовать более сильные предположения о структуре зависимости.
+Упрощение модели уменьшает разброс, но при чрезмерном ограничении может привести к недообучению.
+=== Регуляризация ===
+[[Регуляризация|Регуляризация]] (англ. ''regularization'') добавляет к эмпирическому риску штраф за сложность модели:
+::<tex>\hat R_{X^\ell}(a)+\lambda\Omega(a)\to\min_{a\in A},</tex>
+где <tex>\Omega(a)</tex> — регуляризатор, а <tex>\lambda\geq 0</tex> — коэффициент регуляризации.
+Чем больше <tex>\lambda</tex>, тем сильнее ограничивается модель. При слишком малом значении регуляризация почти не влияет на результат, а при слишком большом модель может недообучиться.
+Для линейных моделей часто используется <tex>L_2</tex>-регуляризация, также называемая штрафом за норму весов:
+::<tex>\Omega(w)=\|w\|_2^2=\sum_{j=1}^{p}w_j^2.</tex>
+Она ограничивает величину коэффициентов и делает модель менее чувствительной к изменениям выборки.
+При <tex>L_1</tex>-регуляризации используется штраф
+::<tex>\Omega(w)=\|w\|_1=\sum_{j=1}^{p}|w_j|.</tex>
+Такой штраф может обращать отдельные коэффициенты в ноль, выполняя отбор признаков. Соответствующий метод линейной регрессии называется [[LASSO]].<ref name="Tibshirani1996">Tibshirani R. [https://doi.org/10.1111/j.2517-6161.1996.tb02080.x Regression Shrinkage and Selection via the Lasso] // Journal of the Royal Statistical Society. Series B. 1996. Vol. 58, no. 1. P. 267–288.</ref>
+=== Ранняя остановка ===
+'''Ранняя остановка''' (англ. ''early stopping'') применяется к моделям, обучаемым итеративно. После каждой итерации вычисляется ошибка на контрольной выборке. Обучение прекращается, если контрольное качество перестаёт улучшаться.
+Сохраняются параметры, соответствующие наименьшей контрольной ошибке, а не последней выполненной итерации.<ref name="Prechelt2012">Prechelt L. [https://doi.org/10.1007/978-3-642-35289-8_5 Early Stopping — But When?] // Neural Networks: Tricks of the Trade. Springer, 2012. P. 53–67.</ref>
+Ранняя остановка ограничивает способность модели приспосабливаться к шуму и может рассматриваться как форма регуляризации.
+=== Метод случайных отключений ===
+'''Метод случайных отключений''' (англ. ''dropout'') применяется при обучении нейронных сетей. На каждой итерации часть нейронов случайно исключается из вычислений.
+Для активации <tex>h_j</tex> можно записать
+::<tex>r_j\sim{\rm Bernoulli}(q),\qquad \tilde h_j=\frac{r_j}{q}h_j,</tex>
+где <tex>q</tex> — вероятность сохранения нейрона.
+Случайное отключение мешает нейронам чрезмерно приспосабливаться друг к другу и приближённо соответствует совместному обучению большого числа различных подсетей.<ref name="Srivastava2014">Srivastava N., Hinton G., Krizhevsky A., Sutskever I., Salakhutdinov R. [https://jmlr.org/papers/v15/srivastava14a.html Dropout: A Simple Way to Prevent Neural Networks from Overfitting] // Journal of Machine Learning Research. 2014. Vol. 15. P. 1929–1958.</ref>
+=== Ансамблирование ===
+[[Ансамбль алгоритмов|Ансамблевые методы]] объединяют предсказания нескольких моделей. Для задачи регрессии простое усреднение имеет вид
+::<tex>\bar a(x)=\frac{1}{M}\sum_{m=1}^{M}a_m(x).</tex>
+Если ошибки отдельных моделей не полностью совпадают, усреднение уменьшает разброс итогового предсказания.
+К методам, уменьшающим переобучение за счёт усреднения, относятся [[Бэггинг|бэггинг]] (англ. ''bagging'') и [[Случайный лес|случайный лес]] (англ. ''random forest'').
+Ансамблирование не устраняет систематическую ошибку, если все модели используют одинаковые ложные закономерности.
+=== Отбор и преобразование признаков ===
+Удаление неинформативных и избыточных признаков может уменьшить сложность модели. Для этого применяются статистические критерии, регуляризация, методы последовательного добавления и удаления признаков.
+Методы понижения размерности, например [[Метод главных компонент|метод главных компонент]], преобразуют исходные признаки в пространство меньшей размерности.
+Отбор признаков должен выполняться только внутри обучающей части данных. Если признаки отбираются до разделения выборки, информация из контрольных объектов может попасть в процесс обучения.
+=== Корректное оценивание качества ===
+Для предотвращения скрытого переобучения необходимо:
+# разделять обучение параметров и выбор гиперпараметров;
+# не использовать тестовую выборку при разработке модели;
+# выполнять предварительную обработку только по обучающей части;
+# учитывать временную, групповую и пространственную структуру данных;
+# фиксировать метрики до начала основного сравнения;
+# использовать вложенный скользящий контроль при интенсивном подборе моделей;
+# сохранять независимый набор данных для окончательной проверки.
+== Утечка данных ==
+'''Утечка данных''' (англ. ''data leakage'') возникает, когда в обучение или вычисление признаков попадает информация, которая не будет доступна в момент реального предсказания.
+Примеры утечки данных:
+* нормировка всех объектов до разделения на обучение и контроль;
+* отбор признаков по полной выборке;
+* использование будущих значений во временном ряду;
+* включение в признаки результата, вычисленного после наступления предсказываемого события;
+* попадание одинаковых или почти одинаковых объектов в обучающую и тестовую выборки.
+Утечка часто приводит к завышенной оценке качества. Она связана с переобучением, но не совпадает с ним.
+При утечке модель может показывать высокое тестовое качество не потому, что хорошо обобщает закономерность, а потому, что процедура проверки содержит недопустимую информацию об ответах.
+== Переобучение в глубоком обучении ==
+Классическое представление предполагает U-образную зависимость тестовой ошибки от сложности модели. При малой сложности ошибка велика из-за недообучения, затем достигает минимума, а после дальнейшего усложнения возрастает вследствие переобучения.
+Для некоторых современных моделей наблюдается более сложная зависимость, называемая '''двойным спуском''' (англ. ''double descent'').<ref name="Belkin2019">Belkin M., Hsu D., Ma S., Mandal S. [https://doi.org/10.1073/pnas.1903070116 Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off] // Proceedings of the National Academy of Sciences. 2019. Vol. 116, no. 32. P. 15849–15854.</ref>
+При приближении к '''порогу интерполяции''' (англ. ''interpolation threshold''), на котором модель впервые получает почти нулевую обучающую ошибку, тестовая ошибка может увеличиться. При дальнейшем увеличении числа параметров она в некоторых случаях снова уменьшается.
+Это явление показывает, что:
+* нулевая обучающая ошибка не равнозначна переобучению;
+* число параметров не полностью определяет эффективную сложность модели;
+* алгоритм оптимизации влияет на выбор решения среди множества интерполирующих моделей;
+* архитектура модели может содержать полезные ограничения;
+* существенную роль играет неявная регуляризация.
+'''Неявная регуляризация''' (англ. ''implicit regularization'') возникает, когда метод оптимизации предпочитает определённые решения даже при отсутствии явного штрафа в функционале качества.
+Например, градиентные методы могут выбирать среди множества решений модели с определёнными свойствами норм параметров.
+Двойной спуск не означает исчезновения проблемы переобучения. Сильно параметризованная модель по-прежнему может запоминать шум, быть неустойчивой и терять качество при изменении распределения данных.
+== Отличие от связанных явлений ==
+=== Недообучение ===
+При недообучении ошибка велика как на обучающей, так и на контрольной выборке. Возможные причины:
+* модель слишком проста;
+* использованы неинформативные признаки;
+* обучение остановлено слишком рано;
+* регуляризация слишком сильна;
+* алгоритм оптимизации не достиг подходящего решения.
+При переобучении обучающая ошибка, напротив, обычно мала.
+=== Запоминание данных ===
+Запоминание означает способность модели воспроизводить отдельные обучающие примеры или их ответы. Оно может быть механизмом переобучения, но не всегда приводит к плохому обобщению.
+Современные нейронные сети способны запоминать отдельные объекты и одновременно выявлять общую структуру данных.
+=== Сдвиг распределения ===
+При сдвиге распределения обучающие и эксплуатационные данные порождаются различными распределениями. В этом случае качество может снизиться даже у корректно обученной модели.
+Переобучение относится к неспособности обобщать данные из исходного распределения, тогда как сдвиг распределения связан с изменением самого источника данных.
+=== Ошибка спецификации модели ===
+Ошибка спецификации модели (англ. ''model misspecification'') возникает, если выбранное семейство моделей не соответствует структуре задачи.
+Например, линейная модель может использоваться для описания существенно нелинейной зависимости. Такое несоответствие чаще приводит к недообучению, однако неверно выбранные признаки и предположения могут также создавать нестабильные зависимости.
+== Практическое значение ==
+Переобучение является одной из основных причин, по которым модель показывает высокое качество в эксперименте, но неудовлетворительно работает после внедрения.
+Риск переобучения особенно велик при следующих условиях:
+* выборка имеет малый объём;
+* число признаков велико;
+* данные содержат шум;
+* метки классов ненадёжны;
+* проверяется большое число моделей;
+* модель обладает высокой ёмкостью;
+* тестовые данные многократно используются при разработке;
+* условия эксплуатации отличаются от условий сбора обучающих данных.
+Борьба с переобучением не сводится к одному методу. Она включает корректный сбор данных, независимое оценивание, выбор подходящей сложности модели, регуляризацию, анализ устойчивости и контроль всей процедуры вычислительного эксперимента.
 == См. также ==
-* [[Расслоение и сходство алгоритмов (виртуальный семинар)]]
-* [[Слабая вероятностная аксиоматика]]
-* [[Полигон алгоритмов]]
-== Ссылки ==
+* [[Обучение по прецедентам]]
-[http://en.wikipedia.org/wiki/Overfitting Overfitting] — статья о переобучении в англоязычной Википедии.
+* [[Минимизация эмпирического риска]]
+* [[Функция потерь]]
+* [[Скользящий контроль]]
+* [[Регуляризация]]
+* [[Отбор признаков]]
+* [[Линейная регрессия]]
+* [[Полиномиальная регрессия]]
+* [[Дерево решений]]
+* [[Нейронная сеть]]
+* [[Ансамбль алгоритмов]]
+* [[Бэггинг]]
+* [[Случайный лес]]
+* [[Метод главных компонент]]
+* [[Проклятие размерности]]
+* [[VC-мерность]]
+== Примечания ==
+<references />
 == Литература ==
-# ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
-# ''Vapnik V.N. '' Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [http://lib.mexmat.ru/books/9220]
-{{Stub}}
+# Vapnik V. N. [https://doi.org/10.1007/978-1-4757-3264-1 The Nature of Statistical Learning Theory]. 2nd ed. Springer, 2000.
+# Hastie T., Tibshirani R., Friedman J. [https://doi.org/10.1007/978-0-387-84858-7 The Elements of Statistical Learning: Data Mining, Inference, and Prediction]. 2nd ed. Springer, 2009.
+# Goodfellow I., Bengio Y., Courville A. [https://www.deeplearningbook.org/ Deep Learning]. MIT Press, 2016.
+# Geman S., Bienenstock E., Doursat R. [https://doi.org/10.1162/neco.1992.4.1.1 Neural Networks and the Bias/Variance Dilemma] // Neural Computation. 1992. Vol. 4, no. 1. P. 1–58.
+# Stone M. [https://doi.org/10.1111/j.2517-6161.1974.tb00994.x Cross-Validatory Choice and Assessment of Statistical Predictions] // Journal of the Royal Statistical Society. Series B. 1974. Vol. 36, no. 2. P. 111–133.
+# Tibshirani R. [https://doi.org/10.1111/j.2517-6161.1996.tb02080.x Regression Shrinkage and Selection via the Lasso] // Journal of the Royal Statistical Society. Series B. 1996. Vol. 58, no. 1. P. 267–288.
+# Prechelt L. [https://doi.org/10.1007/978-3-642-35289-8_5 Early Stopping — But When?] // Neural Networks: Tricks of the Trade. Springer, 2012. P. 53–67.
+# Srivastava N., Hinton G., Krizhevsky A., Sutskever I., Salakhutdinov R. [https://jmlr.org/papers/v15/srivastava14a.html Dropout: A Simple Way to Prevent Neural Networks from Overfitting] // Journal of Machine Learning Research. 2014. Vol. 15. P. 1929–1958.
+# Zhang C., Bengio S., Hardt M., Recht B., Vinyals O. [https://openreview.net/forum?id=Sy8gdB9xx Understanding Deep Learning Requires Rethinking Generalization] // International Conference on Learning Representations, 2017.
+# Belkin M., Hsu D., Ma S., Mandal S. [https://doi.org/10.1073/pnas.1903070116 Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off] // Proceedings of the National Academy of Sciences. 2019. Vol. 116, no. 32. P. 15849–15854.
 [[Категория:Машинное обучение]]
-[[Категория:Теория вычислительного обучения]]
+[[Категория:Обучение по прецедентам]]
+[[Категория:Регуляризация]]