Минимизация эмпирического риска (МЭР, англ. 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}).}$

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

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

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

Свойства

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

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

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

См. также

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

Примечания

Литература

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

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