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

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

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

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

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

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

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

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

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

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

Утверждение 2. Переобучение появляется именно вследствие минимизации эмпирического риска. Пусть задано конечное множество из D алгоритмов, которые допускают ошибки независимо и с одинаковой вероятностью. Число ошибок любого из этих алгоритмов на заданной обучающей выборке подчиняется одному и тому же биномиальному распределению. Минимум эмпирического риска — это случайная величина, равная минимуму из 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]