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

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

---

Версия 15:32, 28 сентября 2008

Содержание 1 Определения 1.1 Задача обучения по прецедентам 1.2 Функция потерь и эмпирический риск 1.3 Разновидности функций потерь 2 Достоинства и недостатки метода 3 Разновидности моделей алгоритмов 4 Литература 5 См. также 6 Ссылки

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Ограничение сложности модели
  • Метод структурной минимизации риска
  • Отбор признаков
• Наложение дополнительных ограничений на параметры модели
  • Регуляризация
  • Байесовская регуляризация

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

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

Литература

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

См. также

• Переобучение
• Теория вычислительного обучения
• Восстановление зависимостей по эмпирическим данным
• Теория Вапника-Червоненкиса
• Линейный классификатор

Ссылки