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

Материал из 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: @@
-{{TOCright}}
+'''Переобучение''' (англ. ''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>
-'''Градиент''' (англ. ''gradient'') — вектор, характеризующий направление и скорость наиболее быстрого локального возрастания [[Функция|скалярной функции]] нескольких переменных. Координатами градиента служат [[Частная производная|частные производные]] функции по всем её аргументам.
+Основная цель [[обучение по прецедентам|обучения по прецедентам]] состоит не в запоминании обучающих объектов, а в построении алгоритма, способного правильно обрабатывать ранее не наблюдавшиеся данные. Такое свойство называется '''обобщающей способностью''' (англ. ''generalization ability'').
-Если функция <tex>f:\mathbb{R}^n\to\mathbb{R}</tex> зависит от переменных <tex>x_1,\ldots,x_n</tex>, то её градиент имеет вид
+Малая ошибка на обучающей выборке сама по себе не означает, что модель обладает высокой обобщающей способностью. Основным признаком переобучения является существенная разница между ошибкой на обучающих данных и ошибкой на независимой контрольной или тестовой выборке.
-::<tex>\nabla f(x)=\left(\frac{\partial f}{\partial x_1}(x),\ldots,\frac{\partial f}{\partial x_n}(x)\right)^\top.</tex>
+Противоположное явление называется '''недообучением''' (англ. ''underfitting''). При недообучении модель оказывается слишком простой или недостаточно обученной и не выявляет закономерности даже в обучающих данных.
-Градиент является одним из основных понятий [[Математический анализ|математического анализа]], [[Численная оптимизация|численной оптимизации]] и [[Машинное обучение|машинного обучения]]. В задачах обучения моделей он показывает, как изменится [[Функция потерь|функция потерь]] при малом изменении каждого параметра. На вычислении градиента основаны [[Градиентный спуск|градиентный спуск]], [[Метод стохастического градиента|метод стохастического градиента]], [[Метод обратного распространения ошибки|обратное распространение ошибки]] и многие современные методы обучения [[Нейронная сеть|нейронных сетей]].
+== Постановка задачи ==
-В строгом смысле градиент определяется не только функцией, но и выбранным [[Скалярное произведение|скалярным произведением]] в пространстве. Привычный вектор частных производных соответствует стандартному евклидову скалярному произведению.
+Пусть задано множество объектов <tex>X</tex> и множество допустимых ответов <tex>Y</tex>. В задаче [[Классификация|классификации]] множество <tex>Y</tex> обычно конечно, а в задаче [[Регрессия|регрессии]] ответы чаще всего являются вещественными числами.
-== Мотивация ==
+Обучающая выборка имеет вид
-Для функции одной переменной [[Производная|производная]] <tex>f'(x)</tex> показывает скорость локального изменения функции. Если аргумент является вектором <tex>x\in\mathbb{R}^n</tex>, двигаться можно во множестве направлений, поэтому одной числовой производной недостаточно.
+::<tex>X^\ell=\{(x_i,y_i)\}_{i=1}^{\ell},\quad x_i\in X,\quad y_i\in Y.</tex>
-Градиент объединяет информацию о локальном изменении функции по всем координатам. Для малого приращения <tex>h\in\mathbb{R}^n</tex> выполняется приближение первого порядка
+Предполагается, что пары <tex>(x_i,y_i)</tex> получены независимо из некоторого неизвестного распределения <tex>P(x,y)</tex>. По обучающей выборке требуется построить алгоритм
-::<tex>f(x+h)\approx f(x)+\nabla f(x)^\top h.</tex>
+::<tex>a:X\to Y,</tex>
-Скалярное произведение <tex>\nabla f(x)^\top h</tex> приближённо показывает, насколько изменится функция при переходе из точки <tex>x</tex> в точку <tex>x+h</tex>.
+который будет правильно предсказывать ответы не только на обучающих объектах, но и на новых объектах из того же распределения.
-В машинном обучении вектор <tex>x</tex> обычно заменяется вектором параметров модели <tex>\theta</tex>, а функция <tex>f</tex> — функцией потерь <tex>\mathcal{L}(\theta)</tex>. Компонента
+Для измерения качества предсказания используется [[Функция потерь|функция потерь]]
-::<tex>\frac{\partial\mathcal{L}}{\partial\theta_j}</tex>
+::<tex>L(a(x),y),</tex>
-показывает локальную чувствительность потерь к изменению параметра <tex>\theta_j</tex>. Если эта производная положительна, малое увеличение параметра увеличивает потери в линейном приближении. Если производная отрицательна, малое увеличение параметра уменьшает потери.
+которая показывает, насколько предсказание <tex>a(x)</tex> отличается от правильного ответа <tex>y</tex>.
-Градиент позволяет ответить на три практически важных вопроса:
+В задаче регрессии часто применяется квадратичная функция потерь:
-* в каком направлении следует изменить параметры, чтобы уменьшить функцию потерь;
+::<tex>L(a(x),y)=(a(x)-y)^2.</tex>
-* насколько чувствительна функция к каждому параметру;
-* является ли рассматриваемая точка кандидатом на локальный экстремум.
-== Определение ==
+В задаче классификации может использоваться индикатор ошибки:
-=== Градиент в евклидовом пространстве ===
+::<tex>L(a(x),y)=[a(x)\ne y],</tex>
-Пусть функция <tex>f:U\subseteq\mathbb{R}^n\to\mathbb{R}</tex> дифференцируема в точке <tex>x\in U</tex>. '''Градиентом функции''' <tex>f</tex> в точке <tex>x</tex> называется вектор
+где выражение в квадратных скобках равно единице, если условие выполнено, и нулю в противном случае.
-::<tex>\nabla f(x)=\left(\frac{\partial f}{\partial x_1}(x),\ldots,\frac{\partial f}{\partial x_n}(x)\right)^\top.</tex>
+== Эмпирический и истинный риск ==
-Также употребляются обозначения <tex>\mathrm{grad}\,f(x)</tex>, <tex>\nabla_x f(x)</tex> и <tex>\frac{\partial f}{\partial x}</tex>. Последнее обозначение зависит от принятого соглашения: в разных источниках производная по вектору может записываться как строка или как столбец. В данной статье градиент считается вектором-столбцом.
+Средняя ошибка алгоритма на обучающей выборке называется [[Эмпирический риск|эмпирическим риском]] (англ. ''empirical risk''):
-Нижний индекс в записи <tex>\nabla_x f</tex> полезен, если функция зависит от нескольких групп переменных. Например, для функции <tex>f(x,\theta)</tex> выражения <tex>\nabla_x f</tex> и <tex>\nabla_\theta f</tex> обозначают градиенты по разным аргументам.
+::<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>f</tex> дифференцируема в точке <tex>x</tex>, то существует линейный функционал <tex>df_x</tex>, для которого
+Однако конечной целью обучения является минимизация истинного, или среднего, риска:
-::<tex>f(x+h)=f(x)+df_x(h)+o(\|h\|),\qquad h\to 0.</tex>
+::<tex>R(a)={\rm E}_{(x,y)\sim P}L(a(x),y).</tex>
-В евклидовом пространстве любой линейный функционал можно представить как скалярное произведение с некоторым вектором. Градиент определяется равенством
+Истинный риск представляет собой среднюю ошибку алгоритма на новых объектах, порождённых распределением <tex>P(x,y)</tex>. Поскольку это распределение неизвестно, точное значение истинного риска обычно вычислить невозможно.
-::<tex>df_x(h)=\langle\nabla f(x),h\rangle.</tex>
+Разность между истинным и эмпирическим риском называется '''разрывом обобщения''' (англ. ''generalization gap''):
-Для стандартного скалярного произведения это равенство принимает вид
+::<tex>G_{X^\ell}(a)=R(a)-\hat R_{X^\ell}(a).</tex>
-::<tex>df_x(h)=\sum_{j=1}^{n}\frac{\partial f}{\partial x_j}(x)h_j.</tex>
+Большое положительное значение разрыва обобщения означает, что ошибка на новых данных существенно выше ошибки на обучающей выборке, и может свидетельствовать о переобучении.
-Дифференциал и градиент связаны, но не являются одним и тем же объектом. Дифференциал является линейным функционалом, или ковектором (англ. ''covector''), а градиент — его векторным представлением относительно выбранного скалярного произведения.
+Формально переобучение удобно определять относительно двух алгоритмов. Алгоритм <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>
-Пусть скалярное произведение задаётся симметричной положительно определённой матрицей <tex>G</tex>:
+Следовательно, переобучение связано не просто с малой обучающей ошибкой, а с ухудшением качества на новых данных при дальнейшем приспособлении модели к обучающей выборке.
-::<tex>\langle u,v\rangle_G=u^\top Gv.</tex>
+== Сложность модели ==
-Градиент относительно этого скалярного произведения определяется условием
+Способность семейства моделей описывать различные зависимости называется '''ёмкостью модели''' (англ. ''model capacity''). Чем выше ёмкость, тем более сложные зависимости может представить модель.
-::<tex>df_x(h)=\langle\nabla_G f(x),h\rangle_G.</tex>
+В зависимости от типа алгоритма сложность модели может определяться:
-Отсюда следует
+* числом настраиваемых параметров;
+* степенью полинома;
+* глубиной [[Дерево решений|дерева решений]];
+* числом листьев дерева;
+* числом используемых признаков;
+* шириной и глубиной [[Нейронная сеть|нейронной сети]];
+* величиной коэффициентов модели;
+* гладкостью восстанавливаемой функции;
+* размерностью пространства допустимых решений.
-::<tex>\nabla_G f(x)=G^{-1}\nabla f(x),</tex>
+В статистической теории обучения сложность класса алгоритмов может характеризоваться [[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>\nabla f(x)</tex> — обычный евклидов градиент.
+::<tex>R(a)\leq \hat R_{X^\ell}(a)+C\sqrt{\frac{h\ln(2\ell/h)+\ln(2/\delta)}{\ell}},</tex>
-Таким образом, направление градиента зависит от выбранной геометрии пространства. Эта зависимость используется в предобусловленных методах (англ. ''preconditioning''), римановой оптимизации (англ. ''Riemannian optimization'') и методе естественного градиента (англ. ''natural gradient'').
+где <tex>h</tex> — мера сложности семейства алгоритмов, <tex>\ell</tex> — объём обучающей выборки, <tex>\delta</tex> — допустимая вероятность нарушения оценки, а <tex>C</tex> — постоянная, зависящая от используемой теоремы.
-== Геометрический смысл ==
+Из подобных оценок следует, что обобщающая способность зависит не только от ошибки на обучении, но и от соотношения между сложностью модели и объёмом данных.
-=== Производная по направлению ===
+При фиксированном размере выборки использование чрезмерно сложного семейства алгоритмов может увеличить риск переобучения. При увеличении объёма обучающих данных допустимая сложность модели обычно возрастает.
-Пусть <tex>v\in\mathbb{R}^n</tex> — направление движения. [[Производная по направлению]] (англ. ''directional derivative'') определяется как
+Число параметров не является универсальной мерой сложности. Две модели с одинаковым числом параметров могут обладать разной обобщающей способностью вследствие различий в архитектуре, ограничениях на параметры и алгоритме оптимизации.
-::<tex>D_vf(x)=\lim_{t\to 0}\frac{f(x+tv)-f(x)}{t}.</tex>
+== Смещение и разброс ==
-Для дифференцируемой функции
+Классическое объяснение переобучения связано с компромиссом между смещением и разбросом (англ. ''bias–variance trade-off'').
-::<tex>D_vf(x)=\nabla f(x)^\top v.</tex>
+Рассмотрим задачу регрессии, в которой данные порождаются согласно модели
-Если <tex>\|v\|_2=1</tex>, то из [[Неравенство Коши — Буняковского|неравенства Коши — Буняковского]] следует
+::<tex>y=f(x)+\varepsilon,</tex>
-::<tex>D_vf(x)\leq\|\nabla f(x)\|_2.</tex>
+где случайный шум удовлетворяет условиям
-Максимальное значение достигается при
+::<tex>{\rm E}(\varepsilon|x)=0,\qquad {\rm E}(\varepsilon^2|x)=\sigma^2.</tex>
-::<tex>v=\frac{\nabla f(x)}{\|\nabla f(x)\|_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>\nabla f(x)\ne 0</tex>. Следовательно, градиент направлен в сторону наиболее быстрого локального возрастания функции, а антиградиент <tex>-\nabla f(x)</tex> — в сторону наиболее быстрого локального убывания.
+::<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''). Оно характеризует систематическое отличие среднего предсказания модели от истинной зависимости.
-Множеством уровня (англ. ''level set'') функции называется множество
+Третье слагаемое называется '''разбросом''' или '''дисперсией модели''' (англ. ''variance''). Оно показывает, насколько сильно результат обучения меняется при замене одной обучающей выборки другой.
-::<tex>M_c=\{x\in\mathbb{R}^n\mid f(x)=c\}.</tex>
+Слишком простая модель обычно имеет большое смещение: она не может достаточно точно представить восстанавливаемую зависимость. Слишком гибкая модель может иметь большой разброс и существенно изменяться при небольшом изменении обучающих данных.
-Если <tex>\nabla f(x)\ne 0</tex>, градиент перпендикулярен касательным направлениям к поверхности уровня, проходящей через точку <tex>x</tex>. При движении вдоль поверхности уровня значение функции не меняется, поэтому для любого касательного вектора <tex>v</tex>
+В классической постановке недообучение связывают с большим смещением, а переобучение — с большим разбросом. Однако такое объяснение не полностью описывает поведение современных сильно параметризованных моделей.
-::<tex>\nabla f(x)^\top v=0.</tex>
+== Причины переобучения ==
-В двумерном пространстве градиент перпендикулярен линии уровня, а в трёхмерном — поверхности уровня.
+=== Недостаточный объём выборки ===
-=== Стационарные точки ===
+При малом числе обучающих объектов трудно отличить устойчивую закономерность от случайного совпадения. Алгоритм может обнаружить зависимость, которая присутствует только в конкретной выборке и не воспроизводится на новых данных.
-Точка <tex>x^\ast</tex> называется стационарной точкой (англ. ''stationary point''), если
+Проблема усиливается с ростом числа признаков. В пространстве высокой размерности обучающие объекты располагаются разреженно, поэтому модель может строить сложные зависимости, опираясь на небольшое число наблюдений. Это связано с явлением, называемым [[Проклятие размерности|проклятием размерности]] (англ. ''curse of dimensionality'').
-::<tex>\nabla f(x^\ast)=0.</tex>
+=== Избыточная сложность модели ===
-Для дифференцируемой функции обращение градиента в нуль является необходимым условием внутреннего локального минимума или максимума. Однако оно не является достаточным: стационарная точка может быть локальным минимумом, локальным максимумом, седловой точкой (англ. ''saddle point'') или частью плоской области функции.
+Если семейство моделей существенно сложнее восстанавливаемой зависимости, в нём могут существовать модели, почти безошибочно описывающие обучающие данные, но нестабильные вне обучающей выборки.
-Для классификации стационарных точек исследуют вторые производные и [[Вычисление матриц Якоби и Гессе|матрицу Гессе]].
+Например, глубокое дерево решений может выделить отдельный лист почти для каждого обучающего объекта. Такое дерево запоминает частные особенности выборки вместо построения устойчивых правил.
-== Связь с производной, якобианом и матрицей Гессе ==
+=== Шум и ошибочные ответы ===
-В литературе по машинному обучению термины «производная», «градиент», «якобиан» и «гессиан» иногда употребляются нестрого. Выбор объекта зависит от размерностей входа и выхода функции.
+Реальные данные могут содержать:
-{| class="wikitable"
+* ошибки измерения;
-! Отображение
+* ошибочные метки классов;
-! Объект первого порядка
+* выбросы;
-! Размерность
+* пропущенные значения;
-|-
+* дубликаты;
-| <tex>f:\mathbb{R}\to\mathbb{R}</tex>
+* противоречивые наблюдения.
-| [[Производная]] <tex>f'(x)</tex>
-| скаляр
-|-
-| <tex>f:\mathbb{R}^n\to\mathbb{R}</tex>
-| градиент <tex>\nabla f(x)</tex>
-| <tex>n\times 1</tex>
-|-
-| <tex>g:\mathbb{R}^n\to\mathbb{R}^m</tex>
-| [[Вычисление матриц Якоби и Гессе|матрица Якоби]] <tex>J_g(x)</tex>
-| <tex>m\times n</tex>
-|-
-| <tex>f:\mathbb{R}^n\to\mathbb{R}</tex>
-| [[Вычисление матриц Якоби и Гессе|матрица Гессе]] <tex>H_f(x)</tex>
-| <tex>n\times n</tex>
-|}
-Матрица Якоби, или якобиан (англ. ''Jacobian matrix''), функции <tex>g=(g_1,\ldots,g_m)^\top</tex> имеет вид
+Модель высокой сложности может приспособиться не только к содержательной зависимости, но и к ошибкам в данных. В предельном случае алгоритм запоминает соответствие между отдельными объектами и случайными ответами.
-::<tex>J_g(x)=\left(\begin{array}{c}\nabla g_1(x)^\top\\ \vdots\\ \nabla g_m(x)^\top\end{array}\right).</tex>
+=== Избыточное число признаков ===
-Матрица Гессе, или гессиан (англ. ''Hessian matrix''), скалярной функции представляет собой якобиан её градиента:
+Неинформативные признаки могут случайно коррелировать с целевой переменной на ограниченной выборке. При большом числе признаков вероятность обнаружения случайных корреляций возрастает.
-::<tex>H_f(x)=J_{\nabla f}(x)=\left[\frac{\partial^2f}{\partial x_i\partial x_j}\right]_{i,j=1}^{n}.</tex>
+Поэтому некорректно выполненный [[Отбор признаков|отбор признаков]] также может привести к переобучению. Если признаки выбираются с использованием всей выборки до разделения данных, информация о контрольных объектах косвенно попадает в процесс обучения.
-Если вторые частные производные непрерывны, матрица Гессе симметрична:
+=== Слишком продолжительное обучение ===
-::<tex>H_f(x)=H_f(x)^\top.</tex>
+При итеративной оптимизации модель обычно сначала выявляет наиболее устойчивые зависимости, а затем начинает приспосабливаться к менее значимым деталям и шуму.
-Градиент описывает локальный наклон функции, тогда как матрица Гессе описывает её локальную кривизну.
+Это особенно характерно для нейронных сетей, обучаемых с помощью [[Градиентный спуск|градиентного спуска]]. Ошибка на обучающей выборке может продолжать уменьшаться, тогда как ошибка на контрольной выборке после некоторого момента начинает возрастать.
-== Правила вычисления ==
+=== Многократный подбор гиперпараметров ===
-=== Линейность ===
+'''Гиперпараметры''' (англ. ''hyperparameters'') определяют структуру модели и процесс её обучения. К ним относятся глубина дерева, коэффициент регуляризации, скорость обучения, число слоёв, размер пакета и другие величины.
-Для дифференцируемых функций <tex>f</tex> и <tex>g</tex> и констант <tex>\alpha,\beta</tex>
+Если большое число конфигураций сравнивается на одной и той же контрольной выборке, информация об этой выборке постепенно используется при выборе модели. В результате модель может косвенно переобучиться под контрольные данные.
-::<tex>\nabla(\alpha f+\beta g)=\alpha\nabla f+\beta\nabla g.</tex>
+=== Нерепрезентативность данных ===
-=== Произведение функций ===
+Обучающая выборка должна отражать условия, в которых модель будет применяться. Если некоторые группы объектов представлены недостаточно или отсутствуют, алгоритм может использовать закономерности, характерные только для собранных данных.
-::<tex>\nabla(fg)=g\nabla f+f\nabla g.</tex>
+Такую ситуацию следует отличать от '''сдвига распределения''' (англ. ''distribution shift''), при котором распределение эксплуатационных данных отличается от распределения обучающей выборки.
-=== Частное функций ===
+Снижение качества при сдвиге распределения возможно даже для модели, которая не была переобучена на исходных данных.
-Если <tex>g(x)\ne 0</tex>, то
+== Примеры ==
-::<tex>\nabla\left(\frac{f}{g}\right)=\frac{g\nabla f-f\nabla g}{g^2}.</tex>
+=== Полиномиальная регрессия ===
-=== Сложная функция ===
+Пусть наблюдения имеют вид
-Пусть <tex>g:\mathbb{R}^n\to\mathbb{R}^m</tex>, <tex>\varphi:\mathbb{R}^m\to\mathbb{R}</tex>, а <tex>f(x)=\varphi(g(x))</tex>. Тогда [[Правило дифференцирования сложной функции|цепное правило]] (англ. ''chain rule'') записывается как
+::<tex>y_i=\sin x_i+\varepsilon_i,</tex>
-::<tex>\nabla_x f(x)=J_g(x)^\top\nabla_z\varphi(z)\big|_{z=g(x)}.</tex>
-Транспонирование якобиана необходимо для согласования размерностей. Цепное правило является математической основой [[Граф вычислений|вычислительных графов]] и [[Метод обратного распространения ошибки|обратного распространения ошибки]].
-=== Квадратичная форма ===
-Для функции
-::<tex>f(x)=\frac12x^\top Ax+b^\top x+c</tex>
-градиент равен
-::<tex>\nabla f(x)=\frac12(A+A^\top)x+b.</tex>
-Если матрица <tex>A</tex> симметрична, формула упрощается:
-::<tex>\nabla f(x)=Ax+b.</tex>
-Матрица Гессе этой функции равна
-::<tex>H_f(x)=\frac12(A+A^\top).</tex>
-=== Норма вектора ===
-Для <tex>x\ne 0</tex>
-::<tex>\nabla_x\|x\|_2=\frac{x}{\|x\|_2}.</tex>
-Для квадрата нормы
-::<tex>\nabla_x\frac12\|x\|_2^2=x.</tex>
-Последняя формула используется при дифференцировании квадратичных функций потерь и [[Регуляризация|регуляризаторов]]. Функция <tex>\|x\|_2</tex> не дифференцируема в точке <tex>x=0</tex>. В этой точке вместо градиента можно рассматривать субградиенты.
-== Градиенты по матрицам ==
-Параметры моделей машинного обучения часто представлены матрицами и многомерными массивами. Раздел математического анализа, рассматривающий производные по таким объектам, называют матричным дифференцированием (англ. ''matrix calculus'').
-Пусть <tex>f:\mathbb{R}^{m\times n}\to\mathbb{R}</tex>. Градиент по матрице <tex>W</tex> обычно определяется равенством
-::<tex>df=\mathrm{tr}\left((\nabla_Wf)^\top dW\right),</tex>
-где <tex>\mathrm{tr}</tex> — [[След матрицы|след матрицы]]. При таком соглашении матрица <tex>\nabla_Wf</tex> имеет ту же форму, что и <tex>W</tex>:
-::<tex>(\nabla_Wf)_{ij}=\frac{\partial f}{\partial W_{ij}}.</tex>
-Например, для функции
-::<tex>f(W)=\frac12\|WX-Y\|_F^2</tex>
-получается
-::<tex>\nabla_Wf=(WX-Y)X^\top,</tex>
-где <tex>\|\cdot\|_F</tex> — норма Фробениуса (англ. ''Frobenius norm'').
-Разные источники и программные библиотеки могут использовать разные соглашения о расположении производных. Поэтому при выводе формул необходимо проверять размерность каждого промежуточного выражения.
-== Примеры ==
-=== Функция двух переменных ===
+где <tex>\varepsilon_i</tex> — случайный шум. Для приближения зависимости используется [[Полиномиальная регрессия|полиномиальная модель]]
-Рассмотрим функцию
+::<tex>p_m(x)=a_0+a_1x+\ldots+a_mx^m.</tex>
-::<tex>f(x,y)=x^2+3xy+2y^2.</tex>
+Полином малой степени не способен описать изгибы синусоиды и недообучается. Полином умеренной степени приближает основную зависимость. Полином очень высокой степени может проходить почти через все обучающие точки, включая случайные отклонения, и образовывать сильные колебания между ними.
-Её частные производные равны
+По мере увеличения степени <tex>m</tex> ошибка на обучающей выборке обычно не возрастает, поскольку каждый следующий класс полиномов содержит предыдущий. Ошибка на новых данных сначала может уменьшаться, а затем возрастать.
-::<tex>\frac{\partial f}{\partial x}=2x+3y,\qquad\frac{\partial f}{\partial y}=3x+4y.</tex>
+Следовательно, полином высокой степени может иметь почти нулевую обучающую ошибку, но плохо приближать исходную зависимость вне обучающих точек.
-Следовательно,
+=== Дерево решений ===
-::<tex>\nabla f(x,y)=\left(\begin{array}{c}2x+3y\\3x+4y\end{array}\right).</tex>
+При построении дерева решений пространство объектов последовательно разбивается на области. Если не ограничивать глубину дерева и минимальное число объектов в листе, разбиение может продолжаться до почти полного разделения обучающих примеров.
-В точке <tex>(1,-1)</tex>
+Полученное дерево имеет низкую обучающую ошибку, но его правила могут зависеть от единичных объектов и случайного шума.
-::<tex>\nabla f(1,-1)=\left(\begin{array}{c}-1\\-1\end{array}\right).</tex>
+Для управления сложностью дерева применяют:
-Наиболее быстрое локальное возрастание происходит в направлении <tex>(-1,-1)</tex>, а наиболее быстрое убывание — в направлении <tex>(1,1)</tex>.
+* ограничение максимальной глубины;
+* ограничение числа листьев;
+* минимальное число объектов в листе;
+* минимальное уменьшение ошибки при разбиении;
+* '''отсечение дерева''' (англ. ''pruning'').
 === Линейная регрессия ===
-Пусть задана матрица признаков <tex>X\in\mathbb{R}^{m\times n}</tex>, вектор ответов <tex>y\in\mathbb{R}^m</tex> и вектор параметров <tex>w\in\mathbb{R}^n</tex>. Для модели [[Линейная регрессия|линейной регрессии]] и квадратичной функции потерь
+В [[Линейная регрессия|линейной регрессии]] переобучение может возникать при большом числе признаков, особенно если признаки сильно коррелированы или число параметров сравнимо с числом наблюдений.
-::<tex>\mathcal{L}(w)=\frac{1}{2m}\|Xw-y\|_2^2</tex>
+При использовании [[Метод наименьших квадратов|метода наименьших квадратов]] минимизируется функционал
-градиент равен
+::<tex>Q(w)=\sum_{i=1}^{\ell}(y_i-w^Tx_i)^2\to\min_w.</tex>
-::<tex>\nabla_w\mathcal{L}(w)=\frac1mX^\top(Xw-y).</tex>
+Если матрица признаков плохо обусловлена, небольшие изменения обучающих данных могут приводить к большим изменениям коэффициентов. Такая модель имеет высокий разброс и может давать нестабильные предсказания.
-Приравнивание градиента к нулю приводит к нормальным уравнениям
+=== Нейронные сети ===
-::<tex>X^\top Xw=X^\top y.</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>
-Если матрица <tex>X^\top X</tex> обратима, формально можно записать
+Однако способность к '''запоминанию''' (англ. ''memorization'') не означает обязательного переобучения. Большая нейронная сеть может одновременно иметь почти нулевую обучающую ошибку и высокое качество на новых данных.
-::<tex>w=(X^\top X)^{-1}X^\top y.</tex>
+На обобщающую способность нейронной сети влияют:
-На практике обратную матрицу обычно не вычисляют явно. Для численно устойчивого решения [[Метод наименьших квадратов|задачи наименьших квадратов]] используют QR-разложение, [[Сингулярное разложение|сингулярное разложение]] или специализированные методы решения систем линейных уравнений.
+* архитектура;
+* алгоритм оптимизации;
+* начальные значения параметров;
+* нормы весов;
+* аугментация данных;
+* регуляризация;
+* структура обучающих данных;
+* момент остановки обучения.
-=== Логистическая регрессия ===
+Поэтому число параметров нейронной сети само по себе не позволяет однозначно определить степень переобучения.
-Для бинарной [[Логистическая регрессия|логистической регрессии]]
+== Диагностика ==
-::<tex>p_i=\sigma(x_i^\top w),\qquad\sigma(z)=\frac{1}{1+\exp(-z)},</tex>
+=== Разделение данных ===
-средняя логарифмическая функция потерь имеет вид
+Обычно исходный набор данных разделяют на три части:
-::<tex>\mathcal{L}(w)=-\frac1m\sum_{i=1}^{m}\left[y_i\log p_i+(1-y_i)\log(1-p_i)\right].</tex>
+* '''обучающая выборка''' (англ. ''training set'') используется для настройки параметров модели;
+* '''контрольная выборка''' (англ. ''validation set'') используется для выбора модели, гиперпараметров и момента остановки обучения;
+* '''тестовая выборка''' (англ. ''test set'') используется только для итоговой оценки качества.
-Если <tex>p=(p_1,\ldots,p_m)^\top</tex>, то
+Характерные сочетания ошибок:
-::<tex>\nabla_w\mathcal{L}(w)=\frac1mX^\top(p-y).</tex>
+* '''недообучение:''' ошибка высока как на обучающей, так и на контрольной выборке;
+* '''хорошее обобщение:''' обе ошибки малы и незначительно отличаются друг от друга;
+* '''переобучение:''' ошибка на обучающей выборке мала, а ошибка на контрольной выборке существенно выше.
-Вектор <tex>p-y</tex> содержит различия между предсказанными вероятностями и истинными ответами, а умножение на <tex>X^\top</tex> распределяет эти ошибки между параметрами модели.
+Тестовая выборка не должна использоваться для выбора признаков, архитектуры или гиперпараметров. В противном случае оценка тестового качества становится смещённой.
-=== Softmax и перекрёстная энтропия ===
+=== Кривые обучения ===
-В задаче многоклассовой классификации модель часто выдаёт логиты (англ. ''logits'') <tex>z_1,\ldots,z_K</tex>. Вероятности классов вычисляются функцией softmax:
+'''Кривые обучения''' (англ. ''learning curves'') показывают зависимость ошибки от числа итераций, размера обучающей выборки или сложности модели.
-::<tex>p_k=\frac{\exp(z_k)}{\sum_{j=1}^{K}\exp(z_j)}.</tex>
+При итеративном обучении ошибка на обучающей выборке обычно уменьшается. Ошибка на контрольной выборке сначала также уменьшается, но после начала переобучения может возрастать.
-Для одного объекта с истинным классом <tex>y</tex> потеря перекрёстной энтропии (англ. ''cross-entropy loss'') равна
+Увеличивающийся разрыв между обучающей и контрольной ошибками является одним из основных практических признаков переобучения.
-::<tex>\ell(z,y)=-\log p_y.</tex>
+Кривые, построенные в зависимости от объёма выборки, помогают определить, полезен ли дополнительный сбор данных. Если контрольная ошибка продолжает уменьшаться с ростом выборки, увеличение количества примеров, вероятно, улучшит качество модели.
-Её производная по логиту <tex>z_k</tex> имеет вид
+=== Скользящий контроль ===
-::<tex>\frac{\partial\ell}{\partial z_k}=p_k-\mathbf{1}[k=y],</tex>
+Если объём данных невелик, оценка качества может сильно зависеть от конкретного разделения на обучение и контроль. Для получения более устойчивой оценки используется [[Скользящий контроль|скользящий контроль]] (англ. ''cross-validation'').
-где <tex>\mathbf{1}[k=y]</tex> — индикатор того, что <tex>k</tex> является истинным классом.
+При <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>
-=== Символьное дифференцирование ===
+Если результаты скользящего контроля многократно используются для выбора признаков и гиперпараметров, итоговая модель может переобучиться под саму процедуру оценивания.
-Символьное дифференцирование (англ. ''symbolic differentiation'') преобразует математическое выражение в новое выражение для его производной. Оно используется в системах компьютерной алгебры.
+В таких случаях применяется '''вложенный скользящий контроль''' (англ. ''nested cross-validation''). Во внутреннем цикле выбираются гиперпараметры, а во внешнем цикле оценивается качество выбранной процедуры.
-При работе с большими составными выражениями символьное дифференцирование может приводить к быстрому росту размера формул и многократному повторению одинаковых подвыражений.
+=== Проверка устойчивости ===
-=== Численное дифференцирование ===
+Переобученная модель часто чувствительна к небольшим изменениям данных. Для проверки устойчивости можно:
-Частную производную можно приближённо вычислить с помощью конечных разностей (англ. ''finite differences''):
+* повторять обучение на различных разбиениях выборки;
+* изменять начальные значения параметров;
+* исключать небольшую часть объектов;
+* добавлять небольшой шум к признакам;
+* сравнивать результаты на различных временных периодах;
+* оценивать разброс метрик качества.
-::<tex>\frac{\partial f}{\partial x_j}(x)\approx\frac{f(x+he_j)-f(x)}{h},</tex>
+Большой разброс результатов между повторными экспериментами может указывать на высокую дисперсию модели.
-где <tex>e_j</tex> — <tex>j</tex>-й базисный вектор, а <tex>h</tex> — малый шаг.
+== Методы борьбы с переобучением ==
-Центральная разность имеет вид
+=== Увеличение объёма данных ===
-::<tex>\frac{\partial f}{\partial x_j}(x)\approx\frac{f(x+he_j)-f(x-he_j)}{2h}.</tex>
+При увеличении числа независимых и репрезентативных наблюдений модели становится сложнее приспособиться к случайным особенностям отдельных объектов.
-Центральная разность обычно точнее односторонней, но требует двух вычислений функции для каждой координаты.
+Дополнительные данные особенно полезны, если обучающая и контрольная ошибки существенно различаются, а контрольное качество продолжает улучшаться с ростом выборки.
-Слишком большое значение <tex>h</tex> приводит к ошибке аппроксимации, а слишком малое — к накоплению ошибок округления при вычитании близких чисел. Для функции с <tex>n</tex> аргументами конечные разности требуют порядка <tex>n</tex> дополнительных вычислений функции.
+Простое увеличение числа объектов не помогает, если новые данные содержат те же систематические ошибки или не отражают условия реального применения модели.
-Поэтому численное дифференцирование редко применяется для обучения крупных моделей, но используется для проверки аналитически или автоматически вычисленного градиента.
+=== Улучшение качества данных ===
-=== Автоматическое дифференцирование ===
+Предварительная обработка может включать:
-Автоматическое дифференцирование (англ. ''automatic differentiation'', ''autodiff'') применяет цепное правило к последовательности элементарных операций программы.<ref name="Baydin">{{статья
+* исправление ошибочных ответов;
- |автор = Baydin A. G., Pearlmutter B. A., Radul A. A., Siskind J. M.
+* удаление дубликатов;
- |заглавие = Automatic Differentiation in Machine Learning: a Survey
+* анализ выбросов;
- |ссылка = https://www.jmlr.org/papers/v18/17-468.html
+* обработку пропущенных значений;
- |издание = Journal of Machine Learning Research
+* согласование единиц измерения;
- |год = 2018
+* проверку источников данных;
- |том = 18
+* устранение признаков, недоступных в момент предсказания.
- |номер = 153
- |страницы = 1—43
-}}</ref>
-В отличие от численных разностей, автоматическое дифференцирование не заменяет производную приближённой разностной формулой. В отличие от символьного дифференцирования, оно не обязано строить полное символьное выражение производной.
+Ошибочные метки особенно опасны для моделей высокой сложности, поскольку такие модели способны их запоминать.
-Вычисления представляются в виде [[Граф вычислений|графа вычислений]] (англ. ''computational graph''), вершины которого соответствуют операциям, а рёбра — передаваемым значениям.
+=== Аугментация данных ===
-Различают два основных режима автоматического дифференцирования.
+'''Аугментация данных''' (англ. ''data augmentation'') заключается в создании дополнительных обучающих примеров с помощью преобразований исходных объектов.
-'''Прямой режим''' (англ. ''forward mode'') эффективно вычисляет произведение матрицы Якоби на вектор:
+Для изображений применяются повороты, отражения, изменение масштаба, кадрирование и изменение яркости. Для звуковых сигналов могут использоваться временные сдвиги, изменение скорости и добавление шума.
-::<tex>J_f(x)v.</tex>
+Преобразования должны сохранять правильный ответ. Например, горизонтальное отражение изображения автомобиля обычно не изменяет его класс, тогда как отражение некоторых букв и цифр может изменить их значение.
-Такое произведение называют произведением якобиана на вектор (англ. ''Jacobian-vector product'', JVP).
+=== Упрощение модели ===
-'''Обратный режим''' (англ. ''reverse mode'') эффективно вычисляет произведение транспонированного якобиана на вектор:
+Сложность модели можно уменьшить непосредственно:
-::<tex>J_f(x)^\top u.</tex>
+* сократить число признаков;
+* уменьшить степень полинома;
+* ограничить глубину дерева;
+* уменьшить число слоёв или нейронов;
+* объединить редкие категории;
+* удалить слабозначимые параметры;
+* использовать более сильные предположения о структуре зависимости.
-Такое произведение называют произведением вектора на якобиан (англ. ''vector-Jacobian product'', VJP).
+Упрощение модели уменьшает разброс, но при чрезмерном ограничении может привести к недообучению.
-Для функции с большим числом входов и одним скалярным выходом <tex>f:\mathbb{R}^n\to\mathbb{R}</tex> обратный режим особенно эффективен: все компоненты градиента могут быть получены за один обратный проход после вычисления значения функции. Эта ситуация типична для машинного обучения, где параметров много, а итоговая функция потерь является скаляром.
+=== Регуляризация ===
-Обратный режим требует хранения промежуточных значений прямого прохода или их повторного вычисления. Поэтому возникает компромисс между расходом памяти и временем вычисления.
+[[Регуляризация|Регуляризация]] (англ. ''regularization'') добавляет к эмпирическому риску штраф за сложность модели:
-=== Обратное распространение ошибки ===
+::<tex>\hat R_{X^\ell}(a)+\lambda\Omega(a)\to\min_{a\in A},</tex>
-[[Метод обратного распространения ошибки|Обратное распространение ошибки]] (англ. ''backpropagation'') представляет собой применение обратного режима автоматического дифференцирования к вычислительному графу нейронной сети.
+где <tex>\Omega(a)</tex> — регуляризатор, а <tex>\lambda\geq 0</tex> — коэффициент регуляризации.
-На прямом проходе (англ. ''forward pass'') вычисляются активации слоёв и значение функции потерь. На обратном проходе (англ. ''backward pass'') локальные производные последовательно объединяются по цепному правилу.<ref name="Rumelhart">{{статья
+Чем больше <tex>\lambda</tex>, тем сильнее ограничивается модель. При слишком малом значении регуляризация почти не влияет на результат, а при слишком большом модель может недообучиться.
- |автор = Rumelhart D. E., Hinton G. E., Williams R. J.
- |заглавие = Learning representations by back-propagating errors
- |ссылка = https://doi.org/10.1038/323533a0
- |издание = Nature
- |год = 1986
- |том = 323
- |страницы = 533—536
- |doi = 10.1038/323533a0
-}}</ref>
-Обратное распространение не является методом оптимизации. Оно вычисляет градиент функции потерь. Обновление параметров выполняется отдельным алгоритмом, например [[Градиентный спуск|градиентным спуском]], [[Метод стохастического градиента|методом стохастического градиента]], методом моментов или Adam.
+Для линейных моделей часто используется <tex>L_2</tex>-регуляризация, также называемая штрафом за норму весов:
-== Градиент в оптимизации ==
+::<tex>\Omega(w)=\|w\|_2^2=\sum_{j=1}^{p}w_j^2.</tex>
-Подробнее о соответствующем алгоритме см. в статье [[Градиентный спуск]].
+Она ограничивает величину коэффициентов и делает модель менее чувствительной к изменениям выборки.
-Рассмотрим задачу безусловной минимизации
+При <tex>L_1</tex>-регуляризации используется штраф
-::<tex>\min_{\theta\in\mathbb{R}^n}\mathcal{L}(\theta).</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>
-::<tex>\theta_{t+1}=\theta_t-\eta_t\nabla\mathcal{L}(\theta_t),</tex>
+=== Ранняя остановка ===
-где <tex>\eta_t>0</tex> — шаг метода, или скорость обучения (англ. ''learning rate'').
+'''Ранняя остановка''' (англ. ''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>
-Пусть градиент функции является липшицевым (англ. ''Lipschitz continuous gradient'') с константой <tex>L</tex>:
+Ранняя остановка ограничивает способность модели приспосабливаться к шуму и может рассматриваться как форма регуляризации.
-::<tex>\|\nabla\mathcal{L}(x)-\nabla\mathcal{L}(y)\|_2\leq L\|x-y\|_2.</tex>
+=== Метод случайных отключений ===
-Тогда выполняется оценка
+'''Метод случайных отключений''' (англ. ''dropout'') применяется при обучении нейронных сетей. На каждой итерации часть нейронов случайно исключается из вычислений.
-::<tex>\mathcal{L}(y)\leq\mathcal{L}(x)+\nabla\mathcal{L}(x)^\top(y-x)+\frac{L}{2}\|y-x\|_2^2.</tex>
+Для активации <tex>h_j</tex> можно записать
-Подставляя <tex>y=x-\eta\nabla\mathcal{L}(x)</tex>, получают
+::<tex>r_j\sim{\rm Bernoulli}(q),\qquad \tilde h_j=\frac{r_j}{q}h_j,</tex>
-::<tex>\mathcal{L}(x-\eta\nabla\mathcal{L}(x))\leq\mathcal{L}(x)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla\mathcal{L}(x)\|_2^2.</tex>
+где <tex>q</tex> — вероятность сохранения нейрона.
-Следовательно, при <tex>0<\eta<2/L</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>
-Для гладких [[Выпуклая функция|выпуклых функций]] градиентный спуск имеет сублинейную скорость сходимости по значению функции. Для гладких сильно выпуклых функций при подходящем постоянном шаге достигается линейная сходимость.<ref name="Nocedal">{{книга
+=== Ансамблирование ===
- |автор = Nocedal J., Wright S. J.
- |заглавие = Numerical Optimization
- |ссылка = https://doi.org/10.1007/978-0-387-40065-5
- |издание = 2nd ed.
- |место = New York
- |издательство = Springer
- |год = 2006
- |isbn = 978-0-387-40065-5
-}}</ref><ref name="Boyd">{{книга
- |автор = Boyd S., Vandenberghe L.
- |заглавие = Convex Optimization
- |ссылка = https://web.stanford.edu/~boyd/cvxbook/
- |место = Cambridge
- |издательство = Cambridge University Press
- |год = 2004
- |isbn = 978-0-521-83378-3
-}}</ref>
-Для невыпуклых функций, типичных для глубоких нейронных сетей, малая норма градиента обычно означает лишь близость к стационарной точке и не гарантирует нахождения глобального минимума.
+[[Ансамбль алгоритмов|Ансамблевые методы]] объединяют предсказания нескольких моделей. Для задачи регрессии простое усреднение имеет вид
-== Полный, стохастический и мини-пакетный градиент ==
+::<tex>\bar a(x)=\frac{1}{M}\sum_{m=1}^{M}a_m(x).</tex>
-Во многих задачах машинного обучения функция потерь является средним по обучающей выборке:
+Если ошибки отдельных моделей не полностью совпадают, усреднение уменьшает разброс итогового предсказания.
-::<tex>\mathcal{L}(\theta)=\frac1m\sum_{i=1}^{m}\ell_i(\theta),</tex>
+К методам, уменьшающим переобучение за счёт усреднения, относятся [[Бэггинг|бэггинг]] (англ. ''bagging'') и [[Случайный лес|случайный лес]] (англ. ''random forest'').
-где <tex>\ell_i</tex> — потеря модели на <tex>i</tex>-м объекте.
+Ансамблирование не устраняет систематическую ошибку, если все модели используют одинаковые ложные закономерности.
-Полный градиент (англ. ''full-batch gradient'') равен
+=== Отбор и преобразование признаков ===
-::<tex>\nabla\mathcal{L}(\theta)=\frac1m\sum_{i=1}^{m}\nabla\ell_i(\theta).</tex>
+Удаление неинформативных и избыточных признаков может уменьшить сложность модели. Для этого применяются статистические критерии, регуляризация, методы последовательного добавления и удаления признаков.
-Его точное вычисление требует обработки всей обучающей выборки.
+Методы понижения размерности, например [[Метод главных компонент|метод главных компонент]], преобразуют исходные признаки в пространство меньшей размерности.
-В [[Метод стохастического градиента|стохастическом градиентном методе]] на каждой итерации используется один случайно выбранный объект или небольшая группа объектов — мини-пакет (англ. ''mini-batch'') <tex>B</tex>:
+Отбор признаков должен выполняться только внутри обучающей части данных. Если признаки отбираются до разделения выборки, информация из контрольных объектов может попасть в процесс обучения.
-::<tex>g_B(\theta)=\frac1{|B|}\sum_{i\in B}\nabla\ell_i(\theta).</tex>
+=== Корректное оценивание качества ===
-При равномерном случайном выборе мини-пакета
+Для предотвращения скрытого переобучения необходимо:
-::<tex>\mathbb{E}[g_B(\theta)]=\nabla\mathcal{L}(\theta).</tex>
+# разделять обучение параметров и выбор гиперпараметров;
+# не использовать тестовую выборку при разработке модели;
+# выполнять предварительную обработку только по обучающей части;
+# учитывать временную, групповую и пространственную структуру данных;
+# фиксировать метрики до начала основного сравнения;
+# использовать вложенный скользящий контроль при интенсивном подборе моделей;
+# сохранять независимый набор данных для окончательной проверки.
-Следовательно, мини-пакетный градиент является несмещённой случайной оценкой полного градиента. Его вычисление дешевле, но оценка содержит стохастический шум (англ. ''gradient noise'').
+== Утечка данных ==
-Увеличение размера пакета обычно уменьшает дисперсию оценки, но увеличивает стоимость одной итерации и объём необходимой памяти.
+'''Утечка данных''' (англ. ''data leakage'') возникает, когда в обучение или вычисление признаков попадает информация, которая не будет доступна в момент реального предсказания.
-Теоретической основой стохастических градиентных методов стала теория [[Стохастическая аппроксимация|стохастической аппроксимации]] (англ. ''stochastic approximation''), предложенная Гербертом Роббинсом и Саттоном Монро в 1951 году.<ref name="RobbinsMonro">{{статья
+Примеры утечки данных:
- |автор = Robbins H., Monro S.
- |заглавие = A Stochastic Approximation Method
- |ссылка = https://doi.org/10.1214/aoms/1177729586
- |издание = The Annals of Mathematical Statistics
- |год = 1951
- |том = 22
- |номер = 3
- |страницы = 400—407
- |doi = 10.1214/aoms/1177729586
-}}</ref>
-== Масштабирование и геометрия градиента ==
+* нормировка всех объектов до разделения на обучение и контроль;
+* отбор признаков по полной выборке;
+* использование будущих значений во временном ряду;
+* включение в признаки результата, вычисленного после наступления предсказываемого события;
+* попадание одинаковых или почти одинаковых объектов в обучающую и тестовую выборки.
-=== Разный масштаб параметров ===
+Утечка часто приводит к завышенной оценке качества. Она связана с переобучением, но не совпадает с ним.
-Если параметры или признаки имеют существенно различающиеся масштабы, компоненты градиента также могут сильно различаться. Траектория градиентного метода начинает колебаться поперёк узкой вытянутой области функции потерь, что замедляет сходимость.
+При утечке модель может показывать высокое тестовое качество не потому, что хорошо обобщает закономерность, а потому, что процедура проверки содержит недопустимую информацию об ответах.
-Для квадратичной функции поведение метода связано со спектром матрицы Гессе. Большое [[Число обусловленности|число обусловленности]] (англ. ''condition number'') означает, что кривизна функции сильно различается по направлениям.
+== Переобучение в глубоком обучении ==
-Для уменьшения этой проблемы применяются:
+Классическое представление предполагает 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>
-* изменение параметризации модели;
-* предобусловливание;
-* адаптивное масштабирование координат;
-* методы, использующие информацию о кривизне;
-* [[Метод Ньютона-Рафсона|метод Ньютона]];
-* квазиньютоновские методы (англ. ''quasi-Newton methods'').
-=== Естественный градиент ===
+При приближении к '''порогу интерполяции''' (англ. ''interpolation threshold''), на котором модель впервые получает почти нулевую обучающую ошибку, тестовая ошибка может увеличиться. При дальнейшем увеличении числа параметров она в некоторых случаях снова уменьшается.
-Обычный евклидов градиент зависит от параметризации модели. Разные системы параметров могут описывать одно и то же вероятностное распределение, но приводить к различным направлениям евклидова градиента.
+Это явление показывает, что:
-Естественный градиент (англ. ''natural gradient'') использует матрицу [[Информация Фишера|информации Фишера]] <tex>F(\theta)</tex>:
+* нулевая обучающая ошибка не равнозначна переобучению;
+* число параметров не полностью определяет эффективную сложность модели;
+* алгоритм оптимизации влияет на выбор решения среди множества интерполирующих моделей;
+* архитектура модели может содержать полезные ограничения;
+* существенную роль играет неявная регуляризация.
-::<tex>\widetilde{\nabla}\mathcal{L}(\theta)=F(\theta)^{-1}\nabla\mathcal{L}(\theta).</tex>
+'''Неявная регуляризация''' (англ. ''implicit regularization'') возникает, когда метод оптимизации предпочитает определённые решения даже при отсутствии явного штрафа в функционале качества.
-Такое направление учитывает локальную геометрию семейства вероятностных распределений, а не только евклидово расстояние между параметрами.<ref name="Amari">{{статья
+Например, градиентные методы могут выбирать среди множества решений модели с определёнными свойствами норм параметров.
- |автор = Amari S.
- |заглавие = Natural Gradient Works Efficiently in Learning
- |ссылка = https://doi.org/10.1162/089976698300017746
- |издание = Neural Computation
- |год = 1998
- |том = 10
- |номер = 2
- |страницы = 251—276
- |doi = 10.1162/089976698300017746
-}}</ref>
-Вычисление и обращение полной матрицы Фишера для крупных моделей обычно слишком дорого, поэтому применяются диагональные, блочно-диагональные и другие приближённые варианты.
+Двойной спуск не означает исчезновения проблемы переобучения. Сильно параметризованная модель по-прежнему может запоминать шум, быть неустойчивой и терять качество при изменении распределения данных.
-== Градиент при наличии ограничений ==
+== Отличие от связанных явлений ==
-Если параметры должны принадлежать допустимому множеству <tex>C</tex>, обычный шаг по антиградиенту может вывести точку за его пределы.
+=== Недообучение ===
-В проекционном градиентном методе (англ. ''projected gradient descent'') используется обновление
+При недообучении ошибка велика как на обучающей, так и на контрольной выборке. Возможные причины:
-::<tex>\theta_{t+1}=\Pi_C\left(\theta_t-\eta_t\nabla\mathcal{L}(\theta_t)\right),</tex>
+* модель слишком проста;
+* использованы неинформативные признаки;
+* обучение остановлено слишком рано;
+* регуляризация слишком сильна;
+* алгоритм оптимизации не достиг подходящего решения.
-где <tex>\Pi_C</tex> — проекция на множество <tex>C</tex>.
+При переобучении обучающая ошибка, напротив, обычно мала.
-Для ограничений в форме равенств и неравенств используются [[Множители Лагранжа|множители Лагранжа]], [[Условия Каруша — Куна — Таккера|условия Каруша — Куна — Таккера]], штрафные функции и барьерные методы.
+=== Запоминание данных ===
-Если допустимое множество является гладким многообразием, евклидов градиент проецируется на касательное пространство. Такой подход применяется в римановой оптимизации.
+Запоминание означает способность модели воспроизводить отдельные обучающие примеры или их ответы. Оно может быть механизмом переобучения, но не всегда приводит к плохому обобщению.
-== Негладкие функции ==
+Современные нейронные сети способны запоминать отдельные объекты и одновременно выявлять общую структуру данных.
-Градиент существует только в точках дифференцируемости. Многие функции, используемые в машинном обучении, являются негладкими.
+=== Сдвиг распределения ===
-Например, функция
+При сдвиге распределения обучающие и эксплуатационные данные порождаются различными распределениями. В этом случае качество может снизиться даже у корректно обученной модели.
-::<tex>f(x)=|x|</tex>
+Переобучение относится к неспособности обобщать данные из исходного распределения, тогда как сдвиг распределения связан с изменением самого источника данных.
-не имеет производной при <tex>x=0</tex>. Функция активации ReLU (англ. ''rectified linear unit'')
+=== Ошибка спецификации модели ===
-::<tex>\mathrm{ReLU}(x)=\max(0,x)</tex>
+Ошибка спецификации модели (англ. ''model misspecification'') возникает, если выбранное семейство моделей не соответствует структуре задачи.
-также не дифференцируема в нуле.
+Например, линейная модель может использоваться для описания существенно нелинейной зависимости. Такое несоответствие чаще приводит к недообучению, однако неверно выбранные признаки и предположения могут также создавать нестабильные зависимости.
-Для выпуклой функции вместо градиента можно использовать субградиент (англ. ''subgradient''). Вектор <tex>g</tex> является субградиентом выпуклой функции <tex>f</tex> в точке <tex>x</tex>, если
-::<tex>f(y)\geq f(x)+g^\top(y-x)</tex>
-для всех допустимых <tex>y</tex>.
-Множество всех субградиентов называется субдифференциалом (англ. ''subdifferential'') и обозначается <tex>\partial f(x)</tex>. В точках дифференцируемости
-::<tex>\partial f(x)=\{\nabla f(x)\}.</tex>
-Для функции <tex>f(x)=|x|</tex>
-::<tex>\partial f(0)=[-1,1].</tex>
-Методы оптимизации негладких функций рассматриваются в статье [[Субградиентные методы (оптимизация)]].
-Библиотеки автоматического дифференцирования обычно задают некоторое условное значение производной в отдельных точках негладкости. Такое вычислительное соглашение не означает, что классический градиент в этой точке существует.
-Негладкость также возникает в задачах с [[L1 регуляризация|L1-регуляризацией]] и [[LASSO-регрессия|LASSO-регрессией]]. Для таких задач часто применяются субградиентные и проксимальные методы (англ. ''proximal methods'').
-== Исчезающие и взрывающиеся градиенты ==
-В глубоких и [[Рекуррентная нейронная сеть|рекуррентных нейронных сетях]] градиент может содержать произведение большого числа матриц Якоби. Нормы таких произведений способны быстро стремиться к нулю или неограниченно возрастать.
-'''Исчезающий градиент''' (англ. ''vanishing gradient'') затрудняет передачу обучающего сигнала к ранним слоям или далёким моментам времени. Параметры получают крайне малые обновления, и модель плохо обучается долгосрочным зависимостям.
-'''Взрывающийся градиент''' (англ. ''exploding gradient'') приводит к чрезмерно большим обновлениям и численной неустойчивости. Результатом могут стать переполнение, бесконечные значения или появление значений <tex>\mathrm{NaN}</tex>.
-Проблема особенно выражена в рекуррентных сетях, где одна и та же матрица преобразования многократно участвует в цепном правиле. Теоретический анализ этих явлений был дан в работах Бенжио, Симара и Фраскони, а также Паскану, Миколова и Бенжио.<ref name="Bengio1994">{{статья
- |автор = Bengio Y., Simard P., Frasconi P.
- |заглавие = Learning Long-Term Dependencies with Gradient Descent Is Difficult
- |ссылка = https://doi.org/10.1109/72.279181
- |издание = IEEE Transactions on Neural Networks
- |год = 1994
- |том = 5
- |номер = 2
- |страницы = 157—166
- |doi = 10.1109/72.279181
-}}</ref><ref name="Pascanu">{{статья
- |автор = Pascanu R., Mikolov T., Bengio Y.
- |заглавие = On the Difficulty of Training Recurrent Neural Networks
- |ссылка = https://proceedings.mlr.press/v28/pascanu13.html
- |издание = Proceedings of the 30th International Conference on Machine Learning
- |год = 2013
- |том = 28
- |страницы = 1310—1318
-}}</ref>
-Для ограничения взрывающихся градиентов используется обрезка градиента (англ. ''gradient clipping''). При обрезке по норме можно использовать преобразование
-::<tex>g_{\mathrm{clip}}=\min\left(1,\frac{\tau}{\|g\|_2}\right)g,</tex>
-где <tex>\tau>0</tex> — заданный порог.
-Для уменьшения проблемы исчезающих градиентов применяются:
-* подходящая инициализация параметров;
-* функции активации без сильного насыщения;
-* нормализация активаций;
-* остаточные связи (англ. ''residual connections'');
-* архитектуры [[Долгая краткосрочная память|LSTM]] и GRU;
-* контроль спектральных свойств весовых матриц.
-== Проверка корректности градиента ==
-Ошибочный градиент может не приводить к немедленной ошибке программы, но способен вызвать неправильное или нестабильное обучение. Для проверки производных используется проверка градиента (англ. ''gradient checking'').
-Для координаты <tex>j</tex> центральная разностная оценка имеет вид
-::<tex>g_j^{\mathrm{num}}=\frac{f(x+he_j)-f(x-he_j)}{2h}.</tex>
-Её сравнивают с аналитическим или автоматически вычисленным значением
-::<tex>g_j^{\mathrm{analyt}}=\frac{\partial f}{\partial x_j}(x).</tex>
-Относительную ошибку можно оценивать выражением
-::<tex>\varepsilon_{\mathrm{rel}}=\frac{\|g^{\mathrm{num}}-g^{\mathrm{analyt}}\|_2}{\max\left(1,\|g^{\mathrm{num}}\|_2,\|g^{\mathrm{analyt}}\|_2\right)}.</tex>
-Проверку рекомендуется проводить:
-* в арифметике повышенной точности;
-* на небольших случайных входных данных;
-* вдали от точек негладкости;
-* при нескольких значениях шага <tex>h</tex>;
-* отдельно для каждой новой или нестандартной операции.
-Для модели с большим числом параметров можно проверять не каждую координату, а случайное направление <tex>v</tex>:
-::<tex>\frac{f(x+hv)-f(x-hv)}{2h}\approx\nabla f(x)^\top v.</tex>
-Такой подход называют проверкой производной по направлению.
-== Типичные ошибки ==
-=== Пропущенное транспонирование ===
-Для композиции <tex>f(x)=\varphi(g(x))</tex> градиент вычисляется как
-::<tex>\nabla_x f=J_g(x)^\top\nabla\varphi.</tex>
-Пропуск транспонирования приводит к несовместимости размерностей или к неверной формуле, которая может случайно выглядеть правильной в одномерном случае.
-=== Смешение суммы и среднего ===
-Функции потерь могут суммироваться или усредняться по объектам:
-::<tex>\mathcal{L}_{\mathrm{sum}}=\sum_{i=1}^{m}\ell_i,\qquad\mathcal{L}_{\mathrm{mean}}=\frac1m\sum_{i=1}^{m}\ell_i.</tex>
-Их градиенты различаются множителем <tex>m</tex>. Это влияет на эффективную скорость обучения и относительную силу регуляризации.
-=== Игнорирование зависимости промежуточной переменной ===
-Если <tex>z=z(x)</tex>, то производная выражения, содержащего <tex>z</tex>, должна учитывать зависимость <tex>z</tex> от <tex>x</tex>. Рассмотрение промежуточной переменной как константы разрывает вычислительный граф и приводит к вычислению частной, а не полной производной.
-В библиотеках автоматического дифференцирования такое поведение может возникать при явном отсоединении значения от вычислительного графа (англ. ''stop gradient'', ''detach'').
-=== Численно неустойчивые выражения ===
-Математически эквивалентные формулы могут иметь разную численную устойчивость. Например, прямое вычисление экспонент в softmax может вызвать переполнение.
-Устойчивая форма имеет вид
-::<tex>p_k=\frac{\exp(z_k-z_{\max})}{\sum_j\exp(z_j-z_{\max})},\qquad z_{\max}=\max_j z_j.</tex>
-Вычитание одной и той же константы из всех логитов не изменяет вероятности, но уменьшает риск переполнения.
-=== Интерпретация малого градиента как доказательства оптимальности ===
-Малая норма градиента может наблюдаться около локального минимума, локального максимума или седловой точки, на плоском участке функции, в области насыщения функции активации либо вследствие округления.
-Поэтому значение <tex>\|\nabla f\|</tex> следует рассматривать вместе со значением функции, кривизной, динамикой оптимизации и поведением модели на данных.
-=== Изменение параметров во время вычисления градиента ===
-Если промежуточные значения или параметры изменяются после прямого прохода, но до завершения обратного прохода, вычисленный градиент может перестать соответствовать исходной функции. Особенно осторожно следует использовать операции, изменяющие массивы на месте (англ. ''in-place operations'').
-== История ==
-Идеи, близкие к современному методу наискорейшего спуска (англ. ''steepest descent''), появились в работе Огюстена Луи Коши 1847 года «Méthode générale pour la résolution des systèmes d'équations simultanées». В ней решение системы уравнений связывалось с последовательным уменьшением вспомогательной функции.<ref name="Cauchy">{{статья
- |автор = Cauchy A.-L.
- |заглавие = Méthode générale pour la résolution des systèmes d'équations simultanées
- |ссылка = https://sites.mathdoc.fr/cgi-bin/oeitem?id=OE_CAUCHY_1_10_399_1
- |издание = Comptes rendus hebdomadaires des séances de l'Académie des sciences
- |год = 1847
- |том = 25
- |страницы = 536—538
-}}</ref>
-В 1951 году Герберт Роббинс и Саттон Монро предложили метод стохастической аппроксимации для нахождения корня уравнения по зашумлённым наблюдениям.<ref name="RobbinsMonro"/> Развитие этого подхода привело к современным стохастическим градиентным алгоритмам.
-В 1970 году Сеппо Линнайнмаа описал общий способ обратного накопления производных, соответствующий современному обратному режиму автоматического дифференцирования.<ref name="Baydin"/>
-Методы обратного вычисления производных развивались также в теории управления, динамическом программировании и других областях. Публикация Дэвида Румельхарта, Джеффри Хинтона и Рональда Уильямса 1986 года сыграла важную роль в распространении обратного распространения ошибки как практического способа обучения многослойных нейронных сетей.<ref name="Rumelhart"/>
-Обратное распространение ошибки существовало в различных формах до 1986 года. Поэтому работу Румельхарта, Хинтона и Уильямса корректнее связывать с популяризацией метода в нейронных сетях, а не с первоначальным открытием цепного правила или обратного автоматического дифференцирования.
 == Практическое значение ==
-Градиент используется не только для обновления параметров модели. Он также служит инструментом исследования и интерпретации алгоритмов машинного обучения.
+Переобучение является одной из основных причин, по которым модель показывает высокое качество в эксперименте, но неудовлетворительно работает после внедрения.
-Основные применения включают:
+Риск переобучения особенно велик при следующих условиях:
-* оптимизацию параметров моделей;
+* выборка имеет малый объём;
-* оценивание чувствительности функции к признакам и параметрам;
+* число признаков велико;
-* построение карт значимости (англ. ''saliency maps'');
+* данные содержат шум;
-* исследование состязательных примеров (англ. ''adversarial examples'');
+* метки классов ненадёжны;
-* оптимизацию входных данных;
+* проверяется большое число моделей;
-* решение обратных задач;
+* модель обладает высокой ёмкостью;
-* дифференцируемое программирование (англ. ''differentiable programming'');
+* тестовые данные многократно используются при разработке;
-* обучение вероятностных моделей;
+* условия эксплуатации отличаются от условий сбора обучающих данных.
-* [[Вариационный вывод|вариационный вывод]];
-* оптимизацию гиперпараметров;
-* анализ влияния обучающих объектов;
-* методы [[Обучение с подкреплением|обучения с подкреплением]], основанные на градиенте стратегии.
-При интерпретации градиентов необходимо учитывать масштаб признаков, параметризацию модели, насыщение нелинейностей и локальный характер производной. Большая компонента градиента означает высокую локальную чувствительность, но не обязательно высокую глобальную значимость соответствующего признака.
+Борьба с переобучением не сводится к одному методу. Она включает корректный сбор данных, независимое оценивание, выбор подходящей сложности модели, регуляризацию, анализ устойчивости и контроль всей процедуры вычислительного эксперимента.
 == См. также ==
-* [[Производная]]
+* [[Обучение по прецедентам]]
-* [[Частная производная]]
+* [[Минимизация эмпирического риска]]
-* [[Производная по направлению]]
-* [[Дифференциал функции]]
-* [[Вычисление матриц Якоби и Гессе]]
-* [[Градиентный спуск]]
-* [[Метод стохастического градиента]]
-* [[Субградиентные методы (оптимизация)]]
-* [[Метод обратного распространения ошибки]]
-* [[Граф вычислений]]
-* [[Метод Ньютона-Рафсона]]
-* [[Метод Ньютона-Гаусса]]
-* [[Линейная регрессия]]
-* [[Логистическая регрессия]]
 * [[Функция потерь]]
+* [[Скользящий контроль]]
 * [[Регуляризация]]
-* [[L1 регуляризация]]
+* [[Отбор признаков]]
-* [[LASSO-регрессия]]
+* [[Линейная регрессия]]
-* [[Переобучение]]
+* [[Полиномиальная регрессия]]
+* [[Дерево решений]]
 * [[Нейронная сеть]]
-* [[Численная оптимизация]]
+* [[Ансамбль алгоритмов]]
-* [[Выпуклая оптимизация]]
+* [[Бэггинг]]
+* [[Случайный лес]]
+* [[Метод главных компонент]]
+* [[Проклятие размерности]]
+* [[VC-мерность]]
 == Примечания ==
-<references/>
+<references />
 == Литература ==
-* {{книга
+# Vapnik V. N. [https://doi.org/10.1007/978-1-4757-3264-1 The Nature of Statistical Learning Theory]. 2nd ed. Springer, 2000.
- |автор = Nocedal J., Wright S. J.
+# 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.
- |заглавие = Numerical Optimization
+# Goodfellow I., Bengio Y., Courville A. [https://www.deeplearningbook.org/ Deep Learning]. MIT Press, 2016.
- |ссылка = https://doi.org/10.1007/978-0-387-40065-5
+# 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.
- |издание = 2nd ed.
+# 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.
- |место = New York
+# 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.
- |издательство = Springer
+# 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.
- |год = 2006
+# 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.
- |страниц = 664
+# 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.
- |isbn = 978-0-387-40065-5
+# 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.
-}}
-* {{книга
- |автор = Boyd S., Vandenberghe L.
- |заглавие = Convex Optimization
- |ссылка = https://web.stanford.edu/~boyd/cvxbook/
- |место = Cambridge
- |издательство = Cambridge University Press
- |год = 2004
- |страниц = 716
- |isbn = 978-0-521-83378-3
-}}
-* {{книга
- |автор = Goodfellow I., Bengio Y., Courville A.
- |заглавие = Deep Learning
- |ссылка = https://www.deeplearningbook.org/
- |место = Cambridge, Massachusetts
- |издательство = MIT Press
- |год = 2016
- |страниц = 800
- |isbn = 978-0-262-03561-3
-}}
-* {{книга
- |автор = Griewank A., Walther A.
- |заглавие = Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation
- |ссылка = https://doi.org/10.1137/1.9780898717761
- |издание = 2nd ed.
- |место = Philadelphia
- |издательство = Society for Industrial and Applied Mathematics
- |год = 2008
- |страниц = 438
- |isbn = 978-0-89871-659-7
-}}
-* {{статья
- |автор = Baydin A. G., Pearlmutter B. A., Radul A. A., Siskind J. M.
- |заглавие = Automatic Differentiation in Machine Learning: a Survey
- |ссылка = https://www.jmlr.org/papers/v18/17-468.html
- |издание = Journal of Machine Learning Research
- |год = 2018
- |том = 18
- |номер = 153
- |страницы = 1—43
-}}
-* {{статья
- |автор = Robbins H., Monro S.
- |заглавие = A Stochastic Approximation Method
- |ссылка = https://doi.org/10.1214/aoms/1177729586
- |издание = The Annals of Mathematical Statistics
- |год = 1951
- |том = 22
- |номер = 3
- |страницы = 400—407
- |doi = 10.1214/aoms/1177729586
-}}
-* {{статья
- |автор = Rumelhart D. E., Hinton G. E., Williams R. J.
- |заглавие = Learning representations by back-propagating errors
- |ссылка = https://doi.org/10.1038/323533a0
- |издание = Nature
- |год = 1986
- |том = 323
- |страницы = 533—536
- |doi = 10.1038/323533a0
-}}
-* {{статья
- |автор = Bengio Y., Simard P., Frasconi P.
- |заглавие = Learning Long-Term Dependencies with Gradient Descent Is Difficult
- |ссылка = https://doi.org/10.1109/72.279181
- |издание = IEEE Transactions on Neural Networks
- |год = 1994
- |том = 5
- |номер = 2
- |страницы = 157—166
- |doi = 10.1109/72.279181
-}}
-* {{статья
- |автор = Pascanu R., Mikolov T., Bengio Y.
- |заглавие = On the Difficulty of Training Recurrent Neural Networks
- |ссылка = https://proceedings.mlr.press/v28/pascanu13.html
- |издание = Proceedings of the 30th International Conference on Machine Learning
- |год = 2013
- |том = 28
- |страницы = 1310—1318
-}}
-* {{статья
- |автор = Amari S.
- |заглавие = Natural Gradient Works Efficiently in Learning
- |ссылка = https://doi.org/10.1162/089976698300017746
- |издание = Neural Computation
- |год = 1998
- |том = 10
- |номер = 2
- |страницы = 251—276
- |doi = 10.1162/089976698300017746
-}}
-[[Категория:Математический анализ]]
-[[Категория:Методы оптимизации]]
 [[Категория:Машинное обучение]]
-[[Категория:Энциклопедия анализа данных]]
+[[Категория:Обучение по прецедентам]]
+[[Категория:Регуляризация]]