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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 7: Строка 7:
''Эмпирическим риском'' называется средняя ошибка алгоритма на обучающей выборке.
''Эмпирическим риском'' называется средняя ошибка алгоритма на обучающей выборке.
-
Метод ''[[Минимизация эмпирического риска|минимизации эмпирического риска]]'' наиболее часто применяется для построения алгоритмов обучения.
+
Метод ''[[Минимизация эмпирического риска|минимизации эмпирического риска]]'' (empirical risk minimization, ERM) наиболее часто применяется для построения алгоритмов обучения.
-
{{S|Он состоит}} в том, чтобы в рамках заданной модели выбрать алгоритм, допускающей минимальное число ошибок на заданной обучающей выборке.
+
{{S|Он состоит}} в том, чтобы в рамках заданной модели выбрать алгоритм, имеющий минимальное значение средней ошибки на заданной обучающей выборке.
-
С переобучением метода минимизации эмпирического риска связано два утверждения, которые на первый взгляд могут показаться парадоксальными.
+
С переобучением метода ERM связано два утверждения, которые на первый взгляд могут показаться парадоксальными.
'''Утверждение 1.'''
'''Утверждение 1.'''
''Минимизация эмпирического риска не гарантирует, что вероятность ошибки на тестовых данных будет мала.''
''Минимизация эмпирического риска не гарантирует, что вероятность ошибки на тестовых данных будет мала.''
-
Легко предложить абсурдный алгоритм обучения, который минимизирует эмпирический риск до нуля, но при этом абсолютно не способен обучаться.
+
Легко строится контрпример — абсурдный алгоритм обучения, который минимизирует эмпирический риск до нуля, но при этом абсолютно не способен обучаться.
Алгоритм состоит в следующем.
Алгоритм состоит в следующем.
Получив обучающую выборку, он запоминает её и строит функцию, которая сравнивает предъявляемый объект с запомненными обучающими объектами.
Получив обучающую выборку, он запоминает её и строит функцию, которая сравнивает предъявляемый объект с запомненными обучающими объектами.
Строка 34: Строка 34:
Однако {{S|в реальной}} ситуации алгоритмы имеют различные вероятности ошибок, не являются независимыми,
Однако {{S|в реальной}} ситуации алгоритмы имеют различные вероятности ошибок, не являются независимыми,
{{S|а множество}} алгоритмов, из которого выбирается лучший, может быть бесконечным.
{{S|а множество}} алгоритмов, из которого выбирается лучший, может быть бесконечным.
-
Поэтому вывод количественных оценок переобученности является сложной задачей.
+
{{S|По этим}} причинам вывод количественных оценок переобученности является сложной задачей, которой занимается [[теория вычислительного обучения]].
-
{{S|Ею занимается}} [[теория вычислительного обучения]].
+
{{S|До сих пор}} остаётся открытой проблема сильной завышенности верхних оценок переобучения.
-
{{S|До сих пор}} остаётся открытой проблема чрезвычайной завышенности верхних оценок переобучения.
+
-
 
+
== Основные определения ==
== Основные определения ==
Строка 43: Строка 41:
== Теоретические верхние оценки переобученности ==
== Теоретические верхние оценки переобученности ==
-
== Переобучение и сложность ==
+
=== Сложность ===
 +
Оценки Вапника-Червоненкиса, ёмкость
 +
Критерий Акаике
 +
 
 +
=== Разделимость ===
 +
 
 +
=== Устойчивость ===
== Эмпирическое измерение переобучения ==
== Эмпирическое измерение переобучения ==
Строка 53: Строка 57:
# ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
# ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
# ''Vapnik V.N. '' Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [http://lib.mexmat.ru/books/9220]
# ''Vapnik V.N. '' Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [http://lib.mexmat.ru/books/9220]
 +
 +
[[Категория:Машинное обучение]]
 +
[[Категория:Теория вычислительного обучения]]

Версия 21:36, 4 апреля 2008

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

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

Содержание

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

Эмпирическим риском называется средняя ошибка алгоритма на обучающей выборке. Метод минимизации эмпирического риска (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]
Личные инструменты