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

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

(Различия между версиями)

Текущая версия

Содержание

1 Определения
2 Достоинства и недостатки метода
3 Разновидности моделей алгоритмов
4 Литература
5 См. также
6 Ссылки

Эмпирический риск (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.$

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

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

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

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

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

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

Литература

Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 416 с. (подробнее)
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. — 448 с. (подробнее)
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»

Категории: Незавершённые статьи | Теория вычислительного обучения

@@ Строка 45: / Строка 45: @@
 Когда функция потерь разрывна,
 минимизация эмпирического риска оказывается сложной задачей комбинаторной оптимизации.
-Во&nbsp;многих практически важных случаях эта сводится к поиску [[Задача поиска максимальной совместной подсистемы|максимальной совместной подсистемы]] в системе неравенств (число неравенств совпадает с число объектов обучения&nbsp;<tex>m</tex>) и является [[NP-полная задача|''NP''-полной]].
+Во&nbsp;многих практически важных случаях эта сводится к поиску [[Максимальная совместная подсистема|максимальной совместной подсистемы]] в системе неравенств (число неравенств совпадает с число объектов обучения&nbsp;<tex>m</tex>) и является [[NP-полная задача|''NP''-полной]].
 Наряду с пороговыми фукциями потерь используются всевозможные их ''непрерывные аппроксимации'',