Минимизация эмпирического риска

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

(Перенаправлено с Эмпирический риск)
Перейти к: навигация, поиск

Содержание

Эмпирический риск (Empirical Risk) — это средняя величина ошибки алгоритма на обучающей выборке.

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

Определения

Задача обучения по прецедентам

Пусть X — множество описаний объектов, Y — множество допустимых ответов. Предполагается, что существует неизвестная целевая зависимость — отображение y^{*}:\: X\to Y, значения которой известны только на объектах конечной обучающей выборки X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}.

Задача обучения по прецедентам состоит в том, чтобы построить алгоритм a:\: X\to Y, который приближал бы неизвестную целевую зависимость как на элементах выборки, так и на всём множестве X.

Функция потерь и эмпирический риск

Вводится функция потерь {\mathcal L}(y,y'), характеризующая величину отклонения ответа y=a(x) от правильного ответа y'=y^{*}(x) на произвольном объекте x\in X.

Вводится модель алгоритмов A= \{a:\: X\to Y\}, в рамках которой будет вестись поиск отображения, приближающего неизвестную целевую зависимость.

Эмпирический риск — это функционал качества, характеризующий среднюю ошибку алгоритма a на выборке X^m:

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

Метод минимизация эмпирического риска заключается в том, чтобы в заданной модели алгоритмов A найти алгоритм, доставляющий минимальное значение функционалу эмпирического риска:

a = \mathrm{arg}\min_{a\in A} Q(a,X^m).

Разновидности функций потерь

В задачах классификации наиболее естественным выбором является пороговая функция потерь

{\mathcal L}(y,y') = [y'\neq y].

Когда функция потерь разрывна, минимизация эмпирического риска оказывается сложной задачей комбинаторной оптимизации. Во многих практически важных случаях эта сводится к поиску максимальной совместной подсистемы в системе неравенств (число неравенств совпадает с число объектов обучения m) и является NP-полной.

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

В задачах регрессии наиболее типичным выбором является квадратичная функция потерь

{\mathcal L}(y,y') = (y'-y)^2.

Достоинства и недостатки метода

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

Основной недостаток — явление переобучения, которое возникает практически всегда при использовании метода минимизации эмпирического риска.

Разновидности моделей алгоритмов

  • Линейные модели классификации
  • Линейные модели регрессии
  • Нелинейные модели классификации
  • Нелинейные модели регрессии

Литература

  1. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с.  (подробнее)
  2. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с.  (подробнее)
  3. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p.  (подробнее)

См. также

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%8D%D0%BC%D0%BF%D0%B8%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%80%D0%B8%D1%81%D0%BA%D0%B0»
Личные инструменты