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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Вероятность переобучения)
(О природе переобучения)
Строка 13: Строка 13:
''Эмпирическим риском'' называется средняя ошибка алгоритма на обучающей выборке.
''Эмпирическим риском'' называется средняя ошибка алгоритма на обучающей выборке.
Метод ''[[Минимизация эмпирического риска|минимизации эмпирического риска]]'' (empirical risk minimization, ERM) наиболее часто применяется для построения алгоритмов обучения.
Метод ''[[Минимизация эмпирического риска|минимизации эмпирического риска]]'' (empirical risk minimization, ERM) наиболее часто применяется для построения алгоритмов обучения.
-
{{S|Он состоит}} в том, чтобы в рамках заданной модели выбрать алгоритм, имеющий минимальное значение средней ошибки на заданной обучающей выборке.
+
{{S|Он состоит}} в том, чтобы в рамках заданной [[модель|модели]] выбрать алгоритм, имеющий минимальное значение средней ошибки на заданной обучающей выборке.
С переобучением метода ERM связано два утверждения, которые на первый взгляд могут показаться парадоксальными.
С переобучением метода ERM связано два утверждения, которые на первый взгляд могут показаться парадоксальными.
Строка 40: Строка 40:
а множество алгоритмов, из которого выбирается лучший, может быть бесконечным.
а множество алгоритмов, из которого выбирается лучший, может быть бесконечным.
По этим причинам вывод количественных оценок переобученности является сложной задачей, которой занимается [[теория вычислительного обучения]].
По этим причинам вывод количественных оценок переобученности является сложной задачей, которой занимается [[теория вычислительного обучения]].
-
До сих пор остаётся открытой проблема сильной завышенности верхних оценок переобучения.
+
До сих пор остаётся открытой проблема сильной завышенности верхних оценок ''вероятности переобучения''.
 +
 
 +
'''Утверждение 3.'''
 +
''Переобучение связано с избыточной сложностью используемой [[модель|модели]]. Всегда существует оптимальное значение сложности модели, при котором переобучение минимально.''
== Определения ==
== Определения ==

Версия 22:22, 4 мая 2010

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

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

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

Содержание

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

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

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

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

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

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

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

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

Определения

Основные обозначения:

X^m=\{x_1,\ldots,x_m\} — подмножество (выборка) объектов из множества объктов \mathbb{X},
A — множество алгоритмов,
\mathcal{L}:\: A\times \mathbb{X} \to \mathbb{R} — функция потерь, значение \mathcal{L}(a,x) есть величина потерь, возникающих при применении алгоритма a к объекту x.

Средней потерей алгоритма a на выборке X^m называется величина

Q(a,X^m) = \frac1m \sum_{i=1}^m \mathcal{L}(a,x_i).

Пусть \mathbb{X} — вероятностное пространство. Ожидаемой потерей алгоритма a называется величина

P(a) = \mathbb{E}\mathcal{L}(a,x).

Если функция \mathcal{L} бинарная (возвращяет либо 0, либо 1), то Q(a,X^m) называется частотой ошибок, а P(a)вероятностью ошибки алгоритма a.

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

Определение. Методом обучения (или алгоритмом обучения) называется отображение \mu:\: \mathbb{X}^\m \to A, которое произвольной обучающей выборке X^m ставит в соответствие некоторый алгоритм a = \mu(X^m).

Вероятность переобучения (частотное определение)

Определение. Переобученностью алгоритма a = \mu(X^m) относительно контрольной выборки X^k называется разность

\delta(a,X^m,X^k) = Q(a,X^k)-Q(a,X^m).

Определение. Вероятностью переобучения называется вероятность того, что величина переобученности превысит заданный порог \varepsilon:

Q_\eps(\mu,X^{m+k}) = \mathbb{P} \bigl[ \delta(a,X^m,X^k) \geq \varepsilon \bigr],

где вероятность \mathbb{P} можно понимать в смысле равномерного распределения на множестве всех C_{m+k}^m разбиений выборки X^L = X^m \sqcup X^k на наблюдаемую обучающую X^m и скрытую контрольную X^k.

Вероятность переобучения может быть измерена эмпирически методом Монте-Карло, см. также скользящий контроль:

\hat Q_\eps(\mu,X^{m+k}) = \frac1N\sum_{n=1}^N \bigl[ \delta(a,X_n^m,X_n^k) \geq \varepsilon \bigr],

где X^L = X_n^m \sqcup X_n^kN случайных разбиений заданной выборки X^L на обучающую подвыборку X_n^m и контрольную подвыборку X_n^k,\; n=1,\ldots,N.

Вероятность переобучения (вероятностное определение)

Определение. Переобученностью алгоритма a = \mu(X^m) называется разность

\delta(a,X^m) = P(a)-Q(a,X^m).

Определение. Вероятностью переобучения называется вероятность того, что величина переобученности превысит заданный порог \varepsilon:

P_\eps(\mu,X^m) = \mathbb{P} \bigl[ \delta(a,X^m) \geq \varepsilon \bigr],

где \mathbb{P} — вероятность в пространстве случайных незавичимых выборок X^m, взятых из одного и того же неизвестного распределения.

Недостатки вероятностного определения:

  • Сложность эмпирического измерения P_\eps при неизвестной вероятностной мере.
  • Большинство верхних оценок для P_\eps выводятся через оценки для Q_\eps с помощью Леммы о симетризации. При это снижается точность оценок.


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

Сложность

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

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

Оценки, основанные на самоограничении (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 с.  (подробнее)
Личные инструменты