Минимизация эмпирического риска
Материал из 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. (подробнее)
См. также
- Переобучение
- Теория вычислительного обучения
- Восстановление зависимостей по эмпирическим данным
- Теория Вапника-Червоненкиса
- Линейный классификатор