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

Минимизация эмпирического риска (МЭР, англ. Empirical risk minimization, ERM) — это принцип статистической теории обучения, который определяет семейство обучающихся алгоритмов и который задаёт теоретические границы результативности.

Основания

Рассмотрим следующую ситуацию, которая является основной установкой многих задач контролируемого обучения. Мы имеем два пространства объектов ${\displaystyle X}$ и ${\displaystyle Y}$ и хотели бы натренировать функцию ${\displaystyle \ h:X\to Y}$ (часто именуемую гипотезой), которая ставит объект ${\displaystyle y\in Y}$ в соответствие объекту ${\displaystyle x\in X}$. Для этого мы имеем в распоряжении тренировочный набор из ${\displaystyle n}$ экземпляров ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$, где ${\displaystyle x_{i}\in X}$ является входом, а ${\displaystyle y_{i}\in Y}$ является соответствующим ответом, который мы хотим получить от ${\displaystyle \ h(x_{i})}$.

Выражаясь более формально, предположим, что существует совместное распределение ${\displaystyle P(x,y)}$ над ${\displaystyle X}$ и ${\displaystyle Y}$, и что тренировочный набор состоит из ${\displaystyle n}$ экземпляров ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$, выбранных из независимых случайно распределённых величин из ${\displaystyle P(x,y)}$. Заметим, что допущение о совместном распределении позволяет симулировать неопределённость в предсказании (например, из-за шума в данных), поскольку ${\displaystyle y}$ не является детерминированной функцией от ${\displaystyle x}$, а скорее случайной величиной с условным распределением ${\displaystyle P(y|x)}$ для фиксированного ${\displaystyle x}$.

Предположим также, что нам дана неотрицательная вещественнозначная функция потери ${\displaystyle L({\hat {y}},y)}$, которая измеряет то, насколько отличается предсказание ${\displaystyle {\hat {y}}}$ гипотезы от истинного выхода ${\displaystyle y.}$ Риск^[англ.], ассоциированный с гипотезой ${\displaystyle h(x)}$, определяется тогда как математическое ожидание функции потери:

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$

Часто в качестве функции потери в теории используется 0-1 функция потери: ${\displaystyle L({\hat {y}},y)=I({\hat {y}}\neq y)}$, где ${\displaystyle I(\dots )}$ означает индикатор.

Высшей целью обучающегося алгоритма является отыскание гипотезы ${\displaystyle h^{*}}$ в фиксированном классе функций ${\displaystyle {\mathcal {H}}}$, для которых риск ${\displaystyle R(h)}$ минимален:

${\displaystyle h^{*}=\arg \min _{h\in {\mathcal {H}}}R(h).}$

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

В общем случае риск ${\displaystyle R(h)}$ не может быть вычислен, поскольку распределение ${\displaystyle P(x,y)}$ неизвестно для обучающего алгоритма (эта ситуация называется агностическим обучением). Однако мы можем вычислить аппроксимацию, именуемую эмпирическим риском, путём усреднения функции потери на тренировочном наборе:

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

Принцип минимизации эмпирического риска (МЭР) ^[1] утверждает, что обучающийся алгоритм должен выбирать гипотезу ${\displaystyle {\hat {h}}}$, которая минимизирует риск:

${\displaystyle {\hat {h}}=\arg \min _{h\in {\mathcal {H}}}R_{\text{emp}}(h).}$

Тогда обучающийся алгоритм, определённый принципом МЭР состоит в решении вышеуказанной задачи оптимизации.

Свойства

Вычислительная сложность

Известно, что минимизация эмпирического риска для задачи классификации с 0-1 функцией потери является NP-трудной даже для такого относительно простого класса функций задач, как линейные классификаторы^[2]. Хотя она может быть эффективно решена, когда минимальный эмпирический риск равен нулю, то есть данные линейно сепарабельны.

На практике автоматически обучающиеся алгоритмы справляются с этим либо путём выпуклой аппроксимации до 0-1 функции потери (подобно кусочно-линейной функции потерь^[англ.] для машин опорных элементов), которую проще оптимизировать, либо выдвижением допущения о распределении ${\displaystyle P(x,y)}$ (а тогда обучающийся алгоритм перестаёт быть агностическим).

См. также

• Метод максимального правдоподобия

Примечания

1. Vapnik, 1992, с. 831–838.
2. Feldman, Guruswami, Raghavendra, Wu, 2012, pp. 1558-1590.

Литература

• Vapnik V. Principles of Risk Minimization for Learning Theory // Advances in neural information processing systems. — 1992.
• Feldman V., Guruswami V., Raghavendra P., Yi Wu. Agnostic Learning of Monomials by Halfspaces is Hard // SIAM Journal on Computing. — 2012. — Т. 41, вып. 6. — С. 1558—1590. — doi:10.1137/120865094.

Литература для дальнейшего чтения

• Vapnik V. The Nature of Statistical Learning Theory. — 2000. — (Information Science and Statistics). — ISBN 978-0-387-98780-4.