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

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

(Различия между версиями)
Перейти к: навигация, поиск
(См. также: дополнение)
(Литература)
Строка 76: Строка 76:
== Литература ==
== Литература ==
-
# ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
+
# {{П:Hastie 2001 The Elements of Statistical Learning}}
# ''Vapnik V.N. '' Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [http://lib.mexmat.ru/books/9220]
# ''Vapnik V.N. '' Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [http://lib.mexmat.ru/books/9220]
 +
# {{П:Воронцов 2010 Комбинаторная теория}}
{{Stub}}
{{Stub}}

Версия 21:56, 1 мая 2010

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

Сложность

Оценки Вапника-Червоненкиса, размерность Вапника-Червоненкиса

Критерий Акаике

Оценки, основанные на самоограничении (self-bounding)

Оценки, основанные на последовательности выборов (microchoice bounds)

Оценки, основанные на расслоении семейства алгоритмов (shell bounds)

Разделимость

Оценки, основанные на отступах (margin-based bounds)

Устойчивость

Устойчивость алгоритма обучения (algorithmic stability)

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

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

См. также

Ссылки

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

Литература

  1. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p.  (подробнее)
  2. Vapnik V.N. Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [1]
  3. Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с.  (подробнее)
Личные инструменты