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

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

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

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

Содержание 1 О природе переобучения 2 Основные определения 3 Теоретические верхние оценки переобученности 4 Переобучение и сложность 5 Эмпирическое измерение переобучения 6 Ссылки 7 Литература

О природе переобучения

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

Пример 1 (абсурдный алгоритм) Легко предложить алгоритм обучения, который минимизирует эмпирический риск до нуля, но при этом абсолютно не способен обучаться. Получив обучающую выборку, он запоминает её и строит функцию, которая сравнивает предъявляемый объект с запомненными обучающими объектами. Если предъявляемый объект в точности совпадает с одним из обучающих, алгоритм выдаёт для него запомненный правильный ответ. Иначе выдаётся произвольный ответ (например, случайный или всегда один и тот же). Эмпирический риск равен нулю, однако этот алгоритм не восстанавливает зависимость и не обладает никакой способностью к обобщению. Отсюда вывод: для успешного обучения необходимо не только запоминать, но и обобщать.

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

Пример 2. Пусть задано конечное множество из D алгоритмов, которые допускают ошибки независимо, с одинаковой вероятностью. Дана конечная обучающая выборка. Число ошибок любого из этих алгоритмов на данной выборке подчиняется одному и тому же биномиальное распределение. Минимум эмпирического риска — это случайная величина, равная минимальному числу ошибок, где минимум берётся по D алгоритмам. Её ожидаемое значение, очевидно, уменьшается с ростом D. Соотвественно, увеличивается переобученность — разность вероятности ошибки и частоты ошибок на обучении.

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

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

Основные определения

Теоретические верхние оценки переобученности

Переобучение и сложность

Эмпирическое измерение переобучения

Ссылки

Overfitting — статья о переобучении в англоязычной Википедии.

Литература

1. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
2. Vapnik V.N. Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [1]