Минимизация эмпирического риска
Материал из MachineLearning.
|
Эмпирический риск (Empirical Risk) — это средняя величина ошибки алгоритма на обучающей выборке.
Метод минимизации эмпирического риска (Empirical Risk Minimization, ERM) — это общий подход к решению широкого класса задач обучения по прецедентам, в первую очередь — задач обучения с учителем, включая задачи классификации и регрессии.
Определения
Задача обучения по прецедентам
Пусть — множество описаний объектов, — множество допустимых ответов. Предполагается, что существует неизвестная целевая зависимость — отображение , значения которой известны только на объектах конечной обучающей выборки .
Задача обучения по прецедентам состоит в том, чтобы построить алгоритм , который приближал бы неизвестную целевую зависимость как на элементах выборки, так и на всём множестве .
Функция потерь и эмпирический риск
Вводится функция потерь , характеризующая величину отклонения ответа от правильного ответа на произвольном объекте .
Вводится модель алгоритмов , в рамках которой будет вестись поиск отображения, приближающего неизвестную целевую зависимость.
Эмпирический риск — это функционал качества, характеризующий среднюю ошибку алгоритма на выборке :
Метод минимизация эмпирического риска заключается в том, чтобы в заданной модели алгоритмов найти алгоритм, доставляющий минимальное значение функционалу эмпирического риска:
Разновидности функций потерь
В задачах классификации наиболее естественным выбором является пороговая функция потерь
Когда функция потерь разрывна, минимизация эмпирического риска оказывается сложной задачей комбинаторной оптимизации. Во многих практически важных случаях эта сводится к поиску максимальной совместной подсистемы в системе неравенств (число неравенств совпадает с число объектов обучения ) и является NP-полной.
Наряду с пороговыми фукциями потерь используются всевозможные их непрерывные аппроксимации, что позволяет применять достаточно эффективные классические методы непрерывной оптимизации, в том числе градиентные методы. Более того, оказывается, что использование некоторых аппроксимаций способно улучшать обобщающую способность алгоритма классификации. Более подробно непрерывные аппроксимации рассматриваются в статье «Линейный классификатор».
В задачах регрессии наиболее типичным выбором является квадратичная функция потерь
Достоинства и недостатки метода
Основное достоинство заключается в том, что это конструктивный и универсальный подход, позволяющий сводить задачу обучения к задачам численной оптимизации.
Основной недостаток — явление переобучения, которое возникает практически всегда при использовании метода минимизации эмпирического риска.
- Ограничение сложности модели
- Наложение дополнительных ограничений на параметры модели
Разновидности моделей алгоритмов
- Линейные модели классификации
- Линейные модели регрессии
- Нелинейные модели классификации
- Нелинейные модели регрессии
Литература
- Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с. (подробнее)
- Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с. (подробнее)
- Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning, 2nd edition. — Springer, 2009. — 533 p. (подробнее)
См. также
- Переобучение
- Теория вычислительного обучения
- Восстановление зависимостей по эмпирическим данным
- Теория Вапника-Червоненкиса
- Линейный классификатор